Holzer reduction and some modifications

Hi All, This week I managed to implement Holzer’s reduction and change the behaviour of DE module a little bit.  First let’s take a look at Holzer’s reduction.

Holzer Reduction

Holzer reduction is concerned with reducing solutions of the quadratic ternary nonrmal equation ax^2 + by^2 +cz^2 = 0. The Holzer’s theorem says that if the above equation is solvable there is always a solution (x, y, z) such that x \leq \sqrt{|bc|}, y \leq \sqrt{|ac|}, z \leq \sqrt{|ab|}. The algorithm for this is explained in [1]. Below is a rough sketch. Before applying the algorithm we have to make abc square free and we assume that a, b positive and c is negative(We can always select a, b, c in such a way that this is the case). Suppose there is a solution (x_{0}, y_{0}, z_{0}) that is not Holzer reduced.

  • If c is even set k = c /2 and let u_{0}, v_{0} be any solution to the equation k = uy_{0} - vx_{0}.
  • If c is odd, c is odd let k = 2c and  let u_{0}, v_{0} be any solution to the equation c = uy_{0} - vx_{0}.
  • Let w be the nearest integer to -(aux_{0} + bvy_{0})/(cz_{0}).
  • Then the following expressions for x, y, z gives a solution such that z < z_{0}.
    x = (x_{0}(au_{0}^2 + bv_{0}^2 + cw^2) - 2u_{0}(au_{0}x_{0} + bv_{0}y_{0} + cwz_{0})) / k
    y = (y_{0}(au_{0}^2 + bv_{0}^2 + cw^2) - 2v_{0}(au_{0}x_{0} + bv_{0}y_{0} + cwz_{0})) / k
    z = (z_{0}(au_{0}^2 + bv_{0}^2 + cw^2) - 2w(au_{0}x_{0} + bv_{0}y_{0} + cwz_{0}))) / k

Continuing this manner one would find a solution such that z_{0} \leq \sqrt{|ab|}.

Some changes to DE module

I made some changes to the structure of DE module too. Now every type of equation returns a tuple ordered according to the sorted order of variable names used in the equation. Quadratic ternary forms and linear equations returns only one tuple, the parametric solution,  and quadratic binary equation returns a set of tuples. This format may be changed in future. The most important change I did to the DE module is that, now before solving any given equation, DE module checks whether that can be factored and If so, solves those factors separately. For example, given the equation y^2 - 7xy + 4yz = 0, it will solve y = 0 and y-7x+4z = 0 separately and combine those results. Also I managed to implement a general method for testing that would check whether the solutions returned by various methods satisfy the original equation. So I hope to get rid of the other redundant methods like check_ternary_quadratic(), solution_ok_quadratic() in the test file. A thank should go to Aaron for proposing such a methodology.

Future work

Pernici has pointed out that some of the solution methodologies in quadratic binary form can be improved so that they take less time. He also has done a great job in implementing the solutions for quadratic congruence x^2 \equiv a (mod \ b). I hope to use those results when his PR gets merged into master. He proposed a method due to cornacchia to improve the speed of the solutions but after a little surveying, I found that implementing solutions for ax^2 + bxy + cy^2 = N can be used to improve the speed. Current algorithms for solving binary quadratic equation ax^2 + bxy + cy^2 + dx + ey + f = 0 employs a general solving method so it miss out some speed enhancements for the special case ax^2 + bxy + cy^2 = N . My plan is if ax^2 + bxy + cy^2 + dx + ey + f = 0 can be converted to the form ax^2 + bxy + cy^2 = N, then solve it using methods for that, otherwise apply the general method. I found a good reference [2] for this. A huge thank should go to Pernici for pointing out the improvements.

References

[1] Efficient Solution of Rational Conices, J. E. Cremona and D. Rusin, Mathematics of Computation, Volume 00, Number 0.
[2] Binary Quadratic Forms: An Algorithmic Approach, J. Buchmann and U. Vollmer, Springer-Verlag, Berlin, Heidelberg, 2007.

Advertisements

5 Comments

  1. For k = uy0 – vx0 to have a solution, doesn’t gcd(x0, y0) need to divide k?

    • Sorry Aaron for the late reply.

      Suppose there is a solution (x_0, y_0, z_0) to the equation ax**2 + by**2 + cz**2 = 0. We can assume that gcd(x_0, y_0, z_0) = 1. (Otherwise we divide by the gcd). Given this, we can prove that gcd(x_0, y_0) should equal 1.

      Suppose gcd(x_0, y_0) = d > 1, since ax_0**2 + by_0**2 + cz_0**2 = 0, d**2 divides cz_0**2, so gcd(cz_0**2, d) > 1. This implies gcd(c, d**2) > 1 or/and gcd(z_0**2, d**2) > 1. Since abc is square free, so is c and this forces gcd(z_0**2, d**2) to be grater than 1, which consequently implies gcd(z_0, d) > 1. So we have, gcd(x_0, y_0, z_0) > 1, which is a contradiction. So gcd(x_0, y_0) = 1.

      • Thanks (you have a typo in there that tripped me up for a bit: it should say “gcd(cz_0**2, d**2) > 1” I think.

        So my next question is, how do you ensure that abc is squarefree with a, b > 0 and c < 0? I guess the answer to the second part is obvious, because one of a, b, c must have a different sign or else (0, 0, 0) would be the only solution, so by a multiplication by -1 and/or rearrangement of variables you can get it to that form.

        But say you have x**2 + 2*y**2 – 2*z**2 = 0 (a = 1, b = 2, c = -2). Then abc = -4 is not squarefree, but (0, 1, 1) is a nontrivial solution, so it definitely is solvable.

  2. Hi Aaron, I don’t see a reply option to your last comment so I post this separately.

    Yes, that should be gcd(cz_{0}^2, d^2) > 1. It’s a typo. Sorry for that.

    Given an input equation of the form ax^2 + by^2 + cz^2 = 0, we can construct a new equation a_{1}x^2 + b_{1}y^2 + c_{1}z^2 = 0 such that a_{1}, b_{1}, c_{1} are square free and pairwise prime. We should apply this procedure when solving x^2 + 2y^2 - 2z^2 = 0 since gcd(2, 2) > 1.

    If gcd(a, b, c) > 1 then we divide all the coefficients by gcd(a, b, c).

    Now Suppose any of the coefficients a, b, c is not square free, say a = k^2a' for some k > 1 and a' square free. Instead of solving the original equation we solve a'x^2 + by^2 + cz^2 = 0 and reconstruct the solutions for the original equation. We should do the same thing for b and c. Since 1, 2, -2 are all square free in your example we don’t need to carry out this step.

    Now lets assume we have an equation with the coefficients a,b,c being square free. Suppose any two of the coefficients, say a and b are not pairwise prime, i.e gcd(a, b) = g > 1. So we have a = ga', b = gb' with gcd(a', b') = 1 and gcd(g, c) = 1 (Since gcd(a, b, c) = 1). Since ax^2 + by^2 + cz^2 = 0 we get that, g | cz^2. Since gcd(g, c) = 1 we should have g | z^2. Now suppose g = d^2g' where g' is square free, we can conclude that dg' | z. Let z = dg'z'. Substituting in the original equation we get, 0 = ax^2 + by^2 + cz^2 = ga'x^2 + gb'y^2 + c(dg'z')^2 = d^2g'a'x^2 + d^2g'b'y^2 + cd^2g'^2z'^2. By simplifying we end with a'x^2 + b'y^2 + cg'z^2 = 0. Now we do the same if either gcd(a', cg') or gcd(b', cg') > 1. We solve the equation we get after going through these procedures instead of the original equation and recover the solutions for the original equation after that.

    Suppose gcd(a', g') = p > 1. we have p | g', p | a' so p^2 | a'g' i.e p^2 | a. Since a is square free, this is not possible. So we should have gcd(a', g') = 1. Also we know that gcd(g, c) = 1. Using these two facts we get gcd(a', cg') = gcd(a', c) = gcd(a'g, c) = gcd(a, c). Similarly we can see that gcd(b', cg') = gcd(b, c). So our process for making two coefficients pairwise prime does not affect the gcd of other coefficient pairs.

    In your example, x^2 + 2y^2 - 2z^2 = 0, we can conclude that 2 | x. So we set x = 2x' and we get the new equation 2x'^2 + y^2 - z^2 = 0. Now this meets our requirements so we solve this and reconstruct the solutions for the original. In Diophantine module, I implemented methods, `square_factor()`, `pairwise_prime()` and `reconstruct()` to carry out this whole process.

    Phew, that was a long answer.

  3. Thanks for your responses. For your future examples, it might be informative to take a concrete example and work through it as you go along.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: