# Solutions of the “tiling equation” $N = 2K^2 - M^2$

Let $N \$ be a positive integer, which is a square times a product of distinct primes, each of which is either 2 or is congruent to $\pm 1$ mod 8. Then I wish to show that there are positive $K$ and $M$ with $M < K$ such that $N = 2K^2 - M^2$. The equation is obviously related to the quadratic form $f(x,y,z) = Nx^2 +y^2 -2 z^2$. One can use the Hasse-Minkowski theorem to show that this equation always has a nontrivial rational solution.

We want integer solutions with $x=1$, $y > 0$, and $y < z$. The problem divides into two parts: show there is a solution with $x=1$, i.e. an integer solution to the original equation, and then show that there is a solution satisfying the desired bound.

Here is what I tried:

Corollary 6.3.6, p. 345 of Cohen volume 1, tells us how all rational solutions can be parametrized in terms of a given solution, which is pretty interesting, but not helpful, since you need one solution to start with.

Prop. 6.3.12 tells how to find one solution, and indeed one in which (x,y,z) are integers. The equation six lines above 6.3.12 (p. 351) and the displayed equation in the middle of that page together give a bound on the size of $x$, something like $3/2$ times the cube root of $N$. But they do not give a bound on $y$ and $z$. These would come out of the LLL algorithm used in the proof, so bounding the solution might be a matter of understanding that algorithm. But anyway, this line of reasoning doesn't address the first part of the problem, the existence of an integer solution with $x=1$.

In case someone asks why I care about this, the equation comes up in my work on tiling a triangle by congruent triangles.

-
Solutions for the squarefree case give solutions for the general problem. It may also be possible to combine solutions from relatively prime N. Do you have any results in the case N is a prime of the necessary form? Gerhard "Ask Me About System Design" Paseman, 2012.01.23 –  Gerhard Paseman Jan 23 '12 at 16:30
Yes, we can assume N is square free, but I don't know how to combine solutions for different primes, nor how to solve the equation even if N is prime. I tested it by computer and empirically it does have solutions. –  Michael Beeson Jan 23 '12 at 16:44
google for Brahmagupta identity. This reduces the problem to prime values of N, and for these it is a well known theorem. –  Franz Lemmermeyer Jan 23 '12 at 17:11
(1) Thanks for pointing out that identity. It reduces the problem of finding an integer solution to the case $N$ prime, but it doesn't seem that the inequality $0 < y < z$ is preserved. (2) Where can I find this "well known theorem"? I don't find it in Cohen volume 1. There is a book by Cox, primes of the form $s^2 + ny^2$, but in that book $n$ is always positive. –  Michael Beeson Jan 23 '12 at 17:29
If $(M,K)$ works then so does $(3M \pm 4K, 2M \pm 3K)$ [this corresponds to the fundamental positive unit $3 \pm 2 \sqrt{2}$ in ${\bf Z}(\sqrt{2})$]. Now iterate until $|M/K|$ is minimal. –  Noam D. Elkies Jan 23 '12 at 17:39

I recommend you get Binary Quadratic Forms by Duncan A. Buell.

Theorem 4.23 on page 74 is, when $p$ is an odd prime with $(\Delta | p) = 1,$ and $b$ is any integral solution to $b^2 \equiv \Delta \pmod {4p},$ the $p$ is primitively represented by the binary quadratic forms belonging to the classes of $\langle p, b, \ast \rangle$ and its opposite $\langle p, -b, \ast \rangle$

In you case, the discriminant $\Delta$ of $x^2 - 2 y^2$ is 8. There are no imprimitive forms of this discriminant, so we may ignore the word "primitively." On page 30, we find that there is only one equivalence class of forms of this discriminant. As a result, any prime $p \equiv \pm 1 \pmod 8$ is represented by $x^2 - 2 y^2.$

How to find a representation? Using TONELLI-SHANKS solve $b^2 \equiv 8 \pmod p.$ If $b$ is odd, replace it by $p-b$ to get an even value, so now $b^2 \equiv 8 \pmod {4p}.$ That is, $b^2 = 8 + 4 p t,$ Which is to say $$b^2 - 4 pt = 8.$$ So we have an indefinite form, almost certainly not "reduced," $$\langle p, b, t \rangle.$$ Pages 21-26 in Buell tell you everything necessary about indefinite reduced forms, with some positive discriminant $D$ not a square, and some coefficients $\langle a, b, c \rangle$ with $b^2 - 4 a c = D,$ the form is reduced if $$0 < b < \sqrt D \; \; \mbox{and} \; \; \sqrt D - b < 2 |a| < \sqrt D + b$$ The reduced form of discriminant 8 are $\langle 1,2,-1 \rangle$ and $\langle -1,2,1 \rangle,$ these being equivalent.

Finally, on page 22, we have Proposition 3.3, any indefinite form is equivalent to a reduced form of the same discriminant. Furthermore, in the body of the proof, Buell shows exactly how to get from non-reduced $\langle p, b, t \rangle$ to one of the reduced forms mentioned, also resulting in a 2 by 2 matrix of determinant 1, let us call it $R,$ which provides the (invertible) change of variables. Inverting $R$ tels us how to get from the reduced form to $\langle p, b, t \rangle.$ A little extra care lets us find a solution to $v^2 - 2 w^2 = p.$

The fact that $x^2 - 2 y^2$ integrally represents all primes $p \equiv \pm 1 \pmod 8$ is due to people such as Lagrange (Franz would know). Lagrange would have seen this material in the way I describe, if you can find it see Introduction to the Theory of Numbers by Leonard Eugene Dickson.

I have software I wrote that takes an indefinite form and reduces it, then shows the entire "chain" or "cycle" of reduced equivalent forms. Email me if you would like a copy (it is in C++). Also, your name seems very familiar, perhaps you are Marvin Greenberg's friend who wrote to me once or twice? Not sure.

A note about speed. This all works very rapidly. It is essentially finding the repeated part of a continued fraction for a quadratic irrational. Indeed, the special thing about reduced forms is that the continued fraction for the largest root is purely periodic.

EDIT, 25 January 2012: I finally got the reduction step cleaned up with a nice printout. I find a pretty example, $p = 159287$ and $45991^2 \equiv 8 \pmod {159287}.$ Then $159287 - 45991 = 113296$ is even, and the constructed indefinite form of discriminant $D = 8$ is $$\langle 159287, \; 113296, \; 20146 \rangle.$$ The reduction step is this: we find the (unique) integral $\delta$ such that $$\sqrt D - 2 |c| < -b + 2 c \delta < \sqrt D.$$ Then the next form is $$\langle c, \; -b + 2 c \delta , \; a - b \delta + c \delta^2 \rangle.$$

The change of variables matrix is just $$\left( \begin{array}{cc} 0 & -1 \\\ 1 & \delta \end{array} \right)$$ As we follow through several steps, we just keep a running account of the matrix. At the end, we have the matrix, written on the right, that takes the original form to the resulting reduced form. The inverse takes the reduced form back. Here is the output:

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./indefCycle Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 159287 113296 20146 0 form 159287 113296 20146 delta 2 1 form 20146 -32712 13279 delta -2 2 form 13279 -20404 7838 delta -2 3 form 7838 -10948 3823 delta -2 4 form 3823 -4344 1234 delta -2 5 form 1234 -592 71 delta -5 6 form 71 -118 49 delta -2 7 form 49 -78 31 delta -2 8 form 31 -46 17 delta -2 9 form 17 -22 7 delta -2 10 form 7 -6 1 delta -2 11 form 1 2 -1 85 -101 -239 284 To Return 284 101 239 85 0 form 1 2 -1 delta -2 1 form -1 2 1 delta 2 2 form 1 2 -1 minimum was 1rep 1 0 disc 8 dSqrt 2.8284271247 M_Ratio 8 Automorph, written on right of Gram matrix: -1 -2 -2 -5 Trace: -6 gcd(a21, a22 - a11, a12) : 2 ========================================= jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$


The matrix of the form $\langle 1, \; 2, \; -1 \rangle$ is $$\left( \begin{array}{cc} 1 & 1 \\\ 1 & -1 \end{array} \right)$$ and the part about returning is $$\left( \begin{array}{cc} 284 & 239 \\\ 101 & 85 \end{array} \right) \cdot \left( \begin{array}{cc} 1 & 1 \\\ 1 & -1 \end{array} \right) \cdot \left( \begin{array}{cc} 284 & 101 \\\ 239 & 85 \end{array} \right) = \left( \begin{array}{cc} 159287 & 56648 \\\ 56648 & 20146 \end{array} \right),$$ which says that $$284^2 + 2 \cdot 284 \cdot 239 - 239^2 = 159287$$ and applying $$\left( \begin{array}{cc} 1 & 1 \\\ 0 & 1 \end{array} \right) \cdot \left( \begin{array}{c} 284 \\\ 239 \end{array} \right) = \left( \begin{array}{c} 523 \\\ 239 \end{array} \right)$$ tells us that $$523^2 - 2 \cdot 239^2 = 159287.$$

-
Right, the hardest part of this is factoring $N$. –  Noam D. Elkies Jan 23 '12 at 22:45
Noam, yes, for a single prime the illustrated procedure gives you a reduced form that represents it, and reversing gives the representation. If the class number is 1 that wraps up that part of the story. It appears that Tonelli-Shanks is also fast, the only uncertain thing is finding a quadratic nonresidue, and a GRH says that is rapid as well. –  Will Jagy Jan 23 '12 at 23:18
You can even get the square root of 2 modulo a prime $p$ in deterministic polynomial time using Schoof's algorithm... If $p \equiv -1 \bmod 8$ then $-1$ is a quadratic nonresidue; if $p \equiv +1 \bmod 8$, the trace of the CM elliptic curves of discriminant $-4$ and $-8$ yields square roots of $-1$ and $-2 \bmod p$, and their product is a square root of $2$. Yes you'd never do it that way in practice but it's still asymptotically faster than factoring. –  Noam D. Elkies Jan 24 '12 at 0:03
Thanks, Noam, I don't believe I knew of Schoof's algorithm. I'm gradually working up the energy to write a good program for my mathoverflow.net/questions/23943/… which amounts to: take a long string of consecutive numbers, all of which are represented by at least one positive binary form of discriminant $-q$ for my choice of prime $q \equiv 7 \pmod 8,$ for each number find all reduced forms that actually do represent it. See if the whole string is represented by a single form... Easy mathematics, long program. –  Will Jagy Jan 24 '12 at 0:26