Serre's A Course in Arithmetic gives essentially the following proof of the three-squares theorem, which says that an integer $a$ is the sum of three squares if and only if it is not of the form $4^m (8n + 7)$ : first one shows that the condition is necessary, which is straightforward. To show it is sufficient, a lemma of Davenport and Cassels, using Hasse-Minkowski, shows that $a$ is the sum of three rational squares. Then something magical happens:

Let $C$ denote the circle $x^2 + y^2 + z^2 = a$. We are given a rational point $p$ on this circle. Round the coordinates of $p$ to the closest integer point $q$, then draw the line through $p$ and $q$, which intersects $C$ at a rational point $p'$. Round the coordinates of $p'$ to the closest integer point $q'$, and repeat this process. A straightforward calculation shows that the least common multiple of the denominators of the points $p'$, $p''$, ... are strictly decreasing, so this process terminates at an integer point on $C$.

Bjorn Poonen, after presenting this proof in class, remarked that he had no intuition for why this should work. Does anyone have a reply?

Edit: Let me suggest a possible reformulation of the question as follows. Complete the analogy: Hensel's lemma is to Newton's method as this technique is to _____________________.

  • $\begingroup$ I don't have any intuition for why this works (other than a vague idea that one should look at other classes of algorithm with similar analysis), but I do just want to say that this is a fantastic proof. $\endgroup$ Oct 29 '09 at 17:35
  • 3
    $\begingroup$ The lemma that Serre attributed to Davenport and Cassels was actually the magical one, not the criterion for being a sum of 3 rational squares. In any case, as explained in my answer below, Serre later discovered that it was known long before Davenport and Cassels... $\endgroup$ Dec 31 '09 at 23:13

The intuition for this method of passing from a rational solution to an integral solution seems pretty simple to me: passing from a rational solution to a nearby integral point (not necessarily a solution) is passing to a point whose denominators are 1, so you can anticipate that when you intersect the line through your rational solution and the nearby integral point with whatever curve or surface contains your solutions, the second intersection point on that line will have denominators that have moved closer to 1. That is, connecting a rational solution with some integral point will spit out a new solution whose denominators are somewhere between the denominators of your solution and the denominators of the integral point you used to produce the line.

Of course intuition is one thing and checking the details is another: you choose the integral point nearby and the math has to work out to show the denominators really get smaller in the second solution you produce. For instance, this method of proving the 3-square theorem goes through without a problem for a similar 2-square theorem (if an integer is a sum of two rational squares than it's a sum of two integral squares by the same method, replacing the sphere x^2 + y^2 + z^2 = a with the circle x^2 + y^2 = a). But this intuitive way of creating an integral solution from a rational solution breaks down if you apply it to the 4-square theorem: the inequalities in the proof just barely fail to work (sort of like doing division with remainder and finding the remainder is as big as the divisor instead of smaller).

The intuition also breaks down if you slightly change the expression x^2 + y^2 (sticking to two variables). Consider x^2 + 82y^2 = 2 and the rational solution (4/7,1/7). Its nearest integral point in the plane is (1,0), and the line through these intersects the ellipse in (16/13,-1/13), so the denominator has gone up. There actually are no integral solutions to x^2 + 82y^2 = 2. Or if we take x^3 + y^3 = 13 and the rational solution (2/3,7/3), its nearest integral point in the plane is (1,2), the line through these meets the curve again in (7/3,2/3), whose nearest integral point in the plane is (2,1), the line through them meets the curve in (2/3,7/3),...

A few years ago when I was giving some lectures on the method of descent, I worked out some examples of this geometric "three-square" theorem (start with an equation a = x^2 + y^2 + z^2 where a is an integer and x, y, and z are rational and produce in a few steps an equation where x, y, and z are integral) and I noticed in my initial examples that the denominators in each new step did not merely drop, but dropped as factors, e.g., if the common denominator at first was 15 then at the next step it was 5 and then 1. Maybe the denominators always decreas through factors like this? Nope, eventually I found a case where they don't: if you start with

13 = (18/11)^2 + (15/11)^2 + (32/11)^2

then the integral point nearest (18/11,15/11,32/11) is (2,1,3) and the line through these two points meets the sphere 13 = x^2 + y^2 + z^2 in the new point (2/3,7/3,8/3), so the denominator has fallen from 11 to 3, which is not a factor. (At the next step you will terminate in the integral solution (0,3,2).)

  • 2
    $\begingroup$ Hi KConrad; yes, the lcm of the denominators gets closer to 1 at each step (as Qiaochu said already in the question statement). The unanswered question is whether there is a conceptual proof of this that is any clearer than the proofs given so far. For example, can one make it conceptually clear why the relevant hypothesis on the quadratic form is that the absolute value of its value at the "error vector" in the lattice point approximation should be between 0 and 1? $\endgroup$ Jan 16 '10 at 2:00
  • 5
    $\begingroup$ When I gave this proof in a lecture (to students at the Ross Program at Ohio State in 2003), Markus Rost was in the audience. He brought to my attention that instead of speaking about the second point of intersection of a line with a circle, you could speak about reflections (for circles, not ellipses!). This led me to write up the details of the argument using the language of reflections, and although it only works up to a sum of 3 squares in Z, it goes through for n squares in F[T]. Look here: math.uconn.edu/~kconrad/blurbs/linmultialg/sumsquareQF(T).pdf Is that helpful? $\endgroup$
    – KConrad
    Jan 16 '10 at 4:11
  • 2
    $\begingroup$ OK, thank you. I hadn't thought about the function field case before - it's interesting that you get a stronger result in that case! $\endgroup$ Jan 16 '10 at 5:40
  • 5
    $\begingroup$ It's stronger only because of the non-archimedean behavior of the degree on F(T), and that removes the surprise for me. What happens is that in Q, a sum of k numbers that are each at most 1/4 is less than 1 only for k = 1, 2, and 3, but in F(T) any finite sum of rational functions with degree below some bound also has degree below that bound. $\endgroup$
    – KConrad
    Jan 16 '10 at 6:26
  • 1
    $\begingroup$ Very late comment, but I think the computation in $\mathbb{Z}^4$ still works if you round to the nearest point in $\mathbb{Z}^4 \cup \left( \mathbb{Z}^4 + (1/2,1/2,1/2,1/2) \right)$. $\endgroup$ Aug 24 '18 at 14:33

A few days ago Serre told me about some modest improvements to the proof, based on Weil's book Number theory: an approach through history from Hammurapi to Legendre and on a 1998 letter from Deligne to Serre; I will paraphrase these below.

According to Weil (p. 292), the ``magical'' argument is due to an amateur mathematican: L. Aubry, Sphinxe-Oedipe 7 (1912), 81--84. Here is a generalization that allows for a clearer proof.

Lemma: Let $f = f_2+f_1+f_0 \in \mathbf{Z}[x_1,\ldots,x_n]$, where $f_i$ is homogeneous of degree $i$. Suppose that for every $x \in \mathbf{Q}^n-\mathbf{Z}^n$, there exists $y \in \mathbf{Z}^n$ such that $0<|f_2(x-y)|<1$. If $f$ has a zero in $\mathbf{Q}^n$, then it has a zero in $\mathbf{Z}^n$.

Proof: If $x=(x_1,\ldots,x_n) \in \mathbf{Q}^n$, let $\operatorname{den}(x)$ denote the lcm of the denominators of the $x_i$. By iteration, the following claim suffices: If $x \in \mathbf{Q}^n - \mathbf{Z}^n$ and $y \in \mathbf{Z}^n$ satisfy $0<|f_2(x-y)|<1$, and the line $L$ through $x$ and $y$ intersects $f=0$ in $x,x'$, then $\operatorname{den}(x')<\operatorname{den}(x)$. By an affine change of variable over $\mathbf{Z}$, we may assume that $y$ is $0$ and that $L$ is the $x_1$-axis. By restricting to $L$, we reduce to proving the following: given $f(t)=At^2+Bt+C \in \mathbf{Z}[t]$ with zeros $x,x' \in \mathbf{Q}$ such that $0<|Ax^2|<1$, we have $\operatorname{den}(x')<\operatorname{den}(x)$. Proof: Factor $f$ over $\mathbf{Z}$ as $E(Dt-N)(D't-N')$ with $x=N/D$ and $x'=N'/D'$ in lowest terms. Then $0<|Ax^2|<1$ implies $0<|A|<D^2$. On the other hand, $DD'$ divides $EDD'=A$, so $DD' \le |A| < D^2$. Hence $D'<D$.

  • 6
    $\begingroup$ Here's a strange application: let p = 1 mod 4 be prime, and let f_2 be the norm form of the quadratic number field K with discriminant p. If K is norm-Euclidean, then the negative Pell equation f_2 = -1 is solvable. $\endgroup$ May 23 '10 at 14:44
  • 1
    $\begingroup$ For some recent papers related to the work of Aubry and successors, see Clark, Euclidean quadratic forms and ADC forms: I. Acta Arith. 154 (2012), no. 2, 137–159; Clark & Jagy, Euclidean quadratic forms and ADC forms II: integral forms. Acta Arith. 164 (2014), no. 3, 265–308; and Dacar, Euclidean quadratic forms are ADC forms: a short proof, arxiv.org/abs/1310.2093 $\endgroup$ Sep 15 '15 at 1:35
  • $\begingroup$ I want to point out that the key condition $\forall x \exists y : 0 < |f_2(x-y)| < 1$ basically says that the balls of radius $1$ in the $f_2$ norm, centered at $\mathbb{Z}^n$, cover $\mathbb{R}^n$. In other words, the key computation in two dimensions is the same as checking that the Gaussian integers are Euclidean. $\endgroup$ Aug 24 '18 at 14:32

I have never understood this proof either. What in my mind makes it very odd is that a very similar argument can sometimes be used to prove in some sense the exact opposite---that certain equations have solutions with denominators as big as you like. For example the proof in Cassels' "elliptic curves" book that x^3+y^3=9 has infinitely many rational solutions goes like this: "find one point (e.g. (2,1)). Now draw the line tangent to the curve through that point, giving a new point (the 3rd point of intersection of the line and the curve), compute the denominators of the new point and observe that they are bigger than those of the old curve. Hence doing this procedure infinitely often produces infinitely many points". You're doing the "new points from old" trick but this time the denominators are getting provably worse rather than provably better.


The Lemma in the aswer by Bjorn Poonen can be sharpened to give an exact relationship between $\mathrm{den}(x)$ and $\mathrm{den}(x')$.

Lemma 1. $~$Let $f=f_2+f_1+f_0\in\mathbb{Z}[X]=\mathbb{Z}[X_1,\ldots,X_n]$ ($n\geq 1$), with each $f_i$
homogeneous of degree $i$. Let $y,v\in\mathbb{Z}^n$, where $v$ is primitive and $f_2(v)\neq0$, and define $F=AT^2+BT+C:=f(y+Tv)\in\mathbb{Z}[T]$. Suppose that the two zeros $t$ and $t'$ of $F$ are rational, so that the two rational points $x=y+tv$ and $x'=y+t'v$ are zeros of $f$. If $x=a/b$ and $x'=a'/b'$ are the reduced representations (with $b,b'>0$), and $x\neq y$ (which is certainly true if $x\notin\mathbb{Z}^n$), then \begin{equation*} b' \,=\, \mathrm{sgn}(A)\cdot \frac{f_2(x-y)} {\mathrm{gcd}(A,B,C)\,\mathrm{gcd}(a-by)^2}\cdot b~; \tag{1} \end{equation*} exchanging $x$ and $x'$ gives the analogous identity (provided $y\neq x'$).

Remark. $~$For any $u=(u_1,\ldots,u_n)\in\mathbb{Z}^n$ we write $\mathrm{gcd}(u):=\mathrm{gcd}(u_1,\ldots,u_n)$.

Proof. $~$Since $tv=x-y=(a-by)/b=(c/b)v$, where $c=\pm\,\mathrm{gcd}(a-by)$ and $\mathrm{gcd}(c,b)=1$, we have $t=c/b$, and similarly $t'=c'/b'$ with $c'=\pm\,\mathrm{gcd}(a'-b'y)$ and $\mathrm{gcd}(c',b')=1$. The leading coefficient of $F$ is $A=f_2(v)=(b/c)^2f_2(x-y)$ ($c\neq 0$ because $a-by=b(x-y)\neq 0$).
By Gauss lemma $F=d(bT-c)(b'T-c')$ with $d=\mathrm{sgn}(A)\cdot\mathrm{gcd}(A,B,C)$.
Then $dbb'=A=(b/c)^2f_2(x-y)$ gives us $b'$ expressed as in the lemma.$~$ Done.

The Lemma in Bjorn Poonen's post is an immediate consequence.

Lemma 1 is about the geometric background of Davenport-Cassels lemma: it relates the reduced representations of two rational zeros of $f$ that lie on an integral line $L=y+\mathbb{Q}v$ whose direction vector $v$ is an anisotropic vector of the quadratic form $f_2$. (An integral line is an affine line in $\mathbb{Q}^n$ that contains an integral point and hence infinitely many integral points.) It is not required that one or the other of the two zeros is non-integral, the lemma says something interesting even when both zeros are integral. Also, the two zeros may coincide, in which case the line $L$ is tangent to the quadric $\{f=0\}$.

If we actually write out the other identity mentioned in the lemma and then compare the two identities, we obtain the identity (supposing $y\neq x,x'$) \begin{equation*} f_2(x-y)f_2(x'-y) \,=\, \bigl(\mathrm{gcd}(A,B,C)\,\mathrm{gcd}(a-by)\,\mathrm{gcd}(a'-b'y)\bigr)^2~.\tag{2} \end{equation*} It is not in the least surprising that $f_2(x-y)f_2(x'-y)$ is a square: if $q$ is any quadratic form on a vector space $V$ over some field $K$, and $u\in V$ and $\lambda,\mu\in K$, then it is trivial that $q(\lambda u)q(\mu u)=\bigl(\lambda\mu q(u)\bigr)^2$. It may seem slightly surprising that $f_2(x-y)f_2(x'-y)$ is a square of an integer, but this is a consequence of $A=dbb'$: in the situation of the lemma the trivial identity satisfied by a general quadratic form reads \begin{equation*} f_2(x-y)f_2(x'-y) \,=\, \Bigl(\frac{c}{b}\,\frac{c'}{b'}f_2(v)\Bigr)^2~, \end{equation*} and substituting $f_2(v)=A=dbb'$ yields \begin{equation*} f_2(x-y)f_2(x'-y) \,=\, (dcc')^2 \,=\, C^2 \,=\, f(y)^2 \end{equation*} (this time without the restriction $y\neq x,x'$). Let $L_{\mathbb{Z}}$ denote the set of all integral points on the line $L$: $L_{\mathbb{Z}}:=L\cap\mathbb{Z}^n=y+\mathbb{Z}v$. For any $z\in L_{\mathbb{Z}}$ the identity (2) still holds when $y$ is replaced by $z$, but we must be careful and write it as \begin{equation*} f_2(x-z)f_2(x'-z) \,=\, \bigl(\mathrm{gcd}(A,B_z,C_z)\,\mathrm{gcd}(a-bz)\,\mathrm{gcd}(a'-b'z)\bigr)^2~, \end{equation*} because the coefficients $B_z$ and $C_z$ of $F_z=f(z+Tv)$ depend on $z$. However, note that the coefficient $A_z=A=f_2(v)$, as well as the greatest common divisor of the coefficients of $F_z$ (the content of $F_z$), $\mathrm{gcd}(A,B_z,C_z)=\left|A\right|/bb'=\left|d\right|$, do not depend on $z$. For $z\in L_{\mathbb{Z}}$ we define $c(z),c'(z)\in\mathbb{Z}$ by $x-z=\bigl(c(z)/b\bigr)v$ and $x'-z=\bigl(c'(z)/b'\bigr)v$. Since $\mathrm{gcd}(a-bz)=\left|c(z)\right|$ and $\mathrm{gcd}(a'-b'z)=\left|c'(z)\right|$, we have \begin{equation*} f_2(x-z)f_2(x'-z) \,=\, \bigl(d\,c(z)\,c'(z)\bigr)^2 \,=\, C_z^2 \,=\, f(z)^2~, \qquad\quad z\in L_{\mathbb{Z}}\,. \end{equation*} Remark. $~$Idiot me! This is just a very special case of the general power-of-a-point theorem, which does not rely on specific factorization properties of integers and is almost trivial to prove:

Let $K$ be a field, let $f\in K[X] = K[X_1,\ldots,X_n]$ be of degree $m$ (where $m, n\geq 1$), and denote by $f_m$ the homogeneous component of $f$ of degree $m$. Let $L$ be an affine line in $K^n$ with a direction vector $v$, where $f_m(v)\neq 0$. Let $y\in L$, and define $F_y := f(y+Tv)\in K[T]$, a polynomial of degree $m$. Suppose that $F_y$ has $m$ zeros (counting multiplicities) $t_1$, $\ldots$, $t_m$ in $K$. Then the points $x_i=y+t_iv\in L$, $1\leq i\leq m$, are zeros of $f$, the multiset of the $x_i$'s does not depend on the choice of $y\in L$, and \begin{equation*} f_m(y-x_1)f_m(y-x_2)\cdots f_m(y-x_m) \,=\, f(y)^m~. \end{equation*}

The independence is easy: if $z=y+sv$, then $F_z$ has the zeros $t_i-s$, whence $z+(t_i-s)v = y+t_iv = x_i$. The leading coefficient of $F_y$ is $f_m(v)$ and its constant term is $f(y)$. From $F_y=f_m(v)(T-t_1)\cdots(T-t_m)$ we get $f(y)=(-1)^m t_1\cdots t_m f_m(v)$, whence $f_m(y-x_1)\cdots f_m(y-x_m) = \bigl((-t_1)\cdots(-t_m)f_m(v)\bigr)^m = f(y)^m$.

We digress. Let's return to the situation in Lemma 1.

We regard the point $y$ as fixed, serving as an origin of $L_{\mathbb{Z}}$. Let us determine $c(z)$ for a general point $z=y+kv\in L_{\mathbb{Z}}$, $k\in\mathbb{Z}$: from \begin{equation*} \frac{c(y+kv)}{b}\,v \,=\, x-(y+kv) \,=\, (x-y)-kv \,=\, \frac{c(y)-kb}{b}\,v \end{equation*} we see that \begin{equation*} c(y+kv) \,=\, c(y) - kb~. \tag{3} \end{equation*} For any $z\in L_{\mathbb{Z}}$ we have \begin{equation*} f_2(x-z) \,=\, \frac{c(z)^2}{b^2}f_2(v) \,=\, \frac{c(z)^2}{b^2}\,dbb' \,=\, \frac{db'}{b}\,c(z)^2 \,=\, \frac{e_0}{b_0}\,c(z)^2~, \tag{4} \end{equation*} where $b_0=b/\mathrm{gcd}(b,db')$ and $e_0=db'/\mathrm{gcd}(b,db')$. Since $\mathrm{gcd}\bigl(b,c(z)\bigr) = 1$, and hence $\mathrm{gcd}\bigl(b_0,c(z)\bigr) = 1$, it follows that \begin{equation*} \mathrm{den}\bigl(f_2(x-z)\bigr) \,=\, b_0 \qquad\quad \text{for every $z\in L_{\mathbb{Z}}$}\,. \end{equation*} Combining (3) and (4) we obtain \begin{equation*} f_2\bigl(x-(y+k)v\bigr) \,=\, \frac{e_0}{b_0}\bigl(c(y)-kb\bigr)^2~, \qquad\quad k\in\mathbb{Z}\,. \end{equation*} In the special case $x=x'$, when the line $L$ is a tangent of the quadric $\{f=0\}$, we have $b=b'$, whence \begin{equation*} f_2(x-z) \,=\, d\,c(z)^2~, \qquad\quad z\in L_{\mathbb{Z}}\,, \end{equation*} thus $f_2(x-z)$ is an integer for every integral point $z$ in $L$.

The discussion above has demonstrated that the identity (1) and its brethren have uses unrelated to Davenport-Cassels lemma. Now we return to applications of (1) to Davenport-Cassels lemma and (a little way) beyond it. The assumptions $x\in\mathbb{Q}^n\setminus\mathbb{Z}^n$ and $0<\left|f_2(x-y)\right|<1$ imply the premises $f_2(v)\neq 0$ and $x\neq y$ of Lemma 1 and then yield the instantaneous result $b'<b$. But besides the $f_2(x-y)$ in the numerator on the right hand side of (1) there are also the factors $\mathrm{gcd}(A,B,C)$ and $\mathrm{gcd}(a-by)^2$ in the denominator whose product can be greater than $1$ and can help make $b'$ smaller than $b$ even when $\left|f_2(x-y)\right|\geq 1$. This leads to the idea of walking with Aubry 'on the far side': when there is no integral point $y$ satisfying $\left|f_2(x-y)\right|\geq 1$ we may still find an integral point $y$ so that we can make a step along the line $L$ from a zero $x=a/b$ of $f$ to a zero $x'=a'/b'$ of $f$ with $b'<b$. The folowing two examples attest that this idea actually works.

But first, a definition. A quadratic form $q$ on $\mathbb{Q}^n$ is said to be Euclidean if for every $x\in\mathbb{Q}^n\setminus\mathbb{Z}^n$ there exists $y\in\mathbb{Z}^n$ such that $0 < \left|q(x-y)\right| < 1$.

For the first example let $q(X_1,X_2,X_3)=X_1^2+X_2^2+5X_3^2$ and $f(X)=q(X) - m$, where $m$ is a positive integer. The positive-definite quadratic form $q$ is not Euclidean on $\mathbb{Q}^3$, since for any $x\in\mathbb{Z}^3+\bigl(\frac{1}{2},\frac{1}{2},\frac{1}{2}\bigr)$ and any $y\in\mathbb{Z}^3$ we have $q(x-y)\geq 7/4$. Consider the set $F$ of all points $x$ in the cube $\bigl\{(x_1,x_2,x_3)\in\mathbb{R}^3 \bigm| 0\leq x_1,x_2,x_3\leq \frac{1}{2}\bigr\}$ at which $q(x)\geq 1$; the set $F$ ('the far side') is shown as the darker shaded part of the cube in the following figure:

Walk on the far side (5)

The function $q(1-x_1,1-x_2,1-x_3)$ of a point $(x_1,x_2,x_3)$ in the set $F$ attains its largest value $8-2\sqrt{5}$ at the point $P=\bigl(0,0,1/\sqrt{5}\bigr)$.
$\quad$Suppose that $x\in\mathbb{Q}^3\setminus\mathbb{Z}^3$ is a zero of $f$, and let $y:=\mathrm{round}(x)$. If $q(x)<1$ (we certainly have $q(x)>0$) then fine, we make a step to the next zero of $f$ with smaller denominator this side of the Euclidean horizon. Otherwise $q(x-y)\geq 1$, we are on the far side, and must tread more carefully. Let $x=a/b=(a_1,a_2,a_3)/b$ be the reduced representation. We claim that since $q(x)=m$ is an integer, the denominator $b$ is odd. Suppose that $b$ is even; then at least one of $a_1$, $a_2$, $a_3$ is odd, and so in $q(x)=q(a)/b^2$ the numerator $q(a)$ is congruent to $1$, $2$, or $3$ modulo $4$, while the denominator is divisible by $4$, contradiction. Note that $b$ being odd implies $0 \leq \left|x_i-y_i\right| < \frac{1}{2}$, $i=1,2,3$. Now we choose an integral point $z$, close to the integral point $y$. If $a_1-by_1$ is even, then we set $z_1:=y_1$. If $a_1-by_1$ is odd, we let $z_1$ be a second closest integer to $x_1$ (there are two possible choices for $z_1$ iff $x_1$ is an integer, and we may choose either of them); then $z_1=y_1\pm1$, $a_1-bz_1$ is even, and $\left|x_1-z_1\right|=1-\left|x_1-y_1\right|$. In either case we have $\left|x_1-z_1\right|\leq1 - \left|x_1-y_1\right|$. The coordinates $z_2$ and $z_3$ are chosen analogously. We step to the next zero $x'=a'/b'$ of $f$ along the line laid through the points $x$ and $z$. Since $\bigl(\left|x_1-y_1\right|,\left|x_2-y_2\right|,\left|x_3-y_3\right|\bigr)\in F$, it follows that $$q(x-z)\leq q\bigl(1-\left|x_1-y_1\right|,1-\left|x_2-y_2\right|,1-\left|x_3-y_3\right|\bigr) \leq 8-2\sqrt{5} < 4~.$$ By the choice of the point $z$ all three coordinates of $a-bz$ are even, thus $\mathrm{gcd}(a-bz)\geq 2$, and Lemma 1 tells us that $b'<b$.

For the second example we consider $q(X_1,X_2,X_3)=X_1^2+X_2^2+2X_3^2$ and $f(X)=q(X)-m$ with $m$ a positive integer. The quadratic form $q$ is barely non-Euclidean: for every $x\in\mathbb{Q}^3\setminus\mathbb{Z}^3$ there is $y=\mathrm{round}(x)\in\mathbb{Z}^3$ such that $q(x-y)\leq 1$. The problem is that there exist points $x$ for which $q(x-y)=1$ is the best we can do: if $x\in M := \mathbb{Z}^3+\bigl(\frac{1}{2},\frac{1}{2},\frac{1}{2}\bigr)$, then $q(x-y)\geq 1$ for any $y\in\mathbb{Z}^3$. Note that $q(x)$ is an odd integer for every $x\in M$, thus there do exist integers $m$, all of them odd, so that $f$ has rational zeros, but woe, it also has a rational zero, with all three coordinates precisely halfway between consecutive integers, at which we get stuck, because there is no Euclidean step from it to another zero. On the other hand, if $m$ is even we never get stuck, there is always a Euclidean step from a non-integral zero; that is, though $f$ is not Euclidean, it is 'conditionally' Euclidean on the set of its zeros.
$\quad$Now suppose that $m$ is odd and that $f$ has rational zeros, and that we walked ourselves into a point $x=a/2\in M$. In this case the trick we have used in the preceding example does not work, because $\mathrm{gcd}(a-2y)^2\leq f_2(x-y)$ for any $y\in\mathbb{Z}^3$; we must seek help from the other factor $\mathrm{gcd}(A,B,C)$ in the denominator on the right hand side of (1). Note that we can round the point $x$ to any of the eight integral points $x+\frac{1}{2}(\delta_1,\delta_2,\delta_3)$, where $\delta_1,\delta_2,\delta_3\in\{-1,1\}$; let $y$ be one of these eight points. We have $v=(\delta_1,\delta_2,\delta_3)$, and $F(T) = f(y+Tv) = q(v)T^2 + 2\langle y,v\rangle T + q(y) - m$, where $\langle\text{-},\text{-}\rangle$ is the bilinear form associated with the quadratic form $q$, $\langle X,Y\rangle = X_1Y_1+X_2Y_2+2X_3Y_3$. The leading coeffient $A=q(v)=4$ is even, the next coefficient $B=2\langle y,v\rangle$ is also even, thus it remains to make $C=q(y)-m$ even. But this is easy: choose $\delta_1$ and $\delta_2$ so that one of $y_1$, $y_2$ is even and the other one is odd. Such a choice makes $\mathrm{gcd}(A,B,C)\geq 2$, and since $q(x-y)=1$, we can step to a zero $x'=a'/b'$ of $f$ with $b'<2$, that is, to an integral zero (whence $\mathrm{gcd}(A,B,C)=2$).

  • $\begingroup$ What do you mean by $gcd(a-by)$? $\endgroup$ Sep 21 '15 at 17:36
  • $\begingroup$ @Felipe Voloch - If $u\in\mathbb{Z}^n$, then $\gcd(u)$ is a shorthand for $\gcd(u_1,\ldots,u_n)$. $\endgroup$
    – chizhek
    Sep 21 '15 at 18:02
  • 2
    $\begingroup$ Every time you edit your answer, you bump the question to the front page. Please avoid multiple edits. $\endgroup$ Sep 22 '15 at 15:33
  • 2
    $\begingroup$ Thank you for your insight and contribution. I'll say quickly though that Felipe has a point: while sometimes an edit is important, tiny cosmetic edits can become an annoyance to others if there are too many. As a piece of friendly advice: for cosmetic adjustments, consider also using a text editor offline until you are quite satisfied with the appearance. Answers can always be revisited and edited if something more important comes up. $\endgroup$
    – Todd Trimble
    Sep 22 '15 at 15:42
  • $\begingroup$ @Felipe Voloch - My current problem is that refresh in preview stops working after I edit a line or two, and then shows the LaTeX code. I resorted to preparing large chunks of the answer offline, which I then paste into the editor, blindly, since refresh usually stops working at once. And then what: I can only see what the thing looks like (it looks different offline) by posting the answer. This is in IE; in Firefox and Chrome the refresh does not work at all. I wasted hours searching the net for solution, tried a lot of things, nothing helped. Any hints? "Bump the question to the front page"? $\endgroup$
    – chizhek
    Sep 22 '15 at 16:39

Okay, this is a crazy line of thought even for me, but there are a lot of number-theoretic or combinatorial algorithms where the proof of correctness proceeds along essentially the same lines. A solution is shown to be equivalent to some parameter equalling 1 (or 0). The parameter can usually take only integer values at any point in the set of potential solutions. We then apply an iterative algorithm and show that at each iteration, if we don't already have a solution, the parameter strictly decreases. Then the algorithm must eventually terminate at a solution.

Examples: The greedy algorithm for Egyptian fraction representations, and (kind of) the Gale-Shapley stable marriage algorithm.

I don't really know enough in this area to speak with any kind of certainty, but you're looking for a real-valued analogue of something like this -- I suspect it's probably linear programming, or some generalization thereof. Maybe interior point methods?

  • $\begingroup$ Right, but I don't have an intuition for any of those algorithms either, except the ones that boil down to the Euclidean algorithm. $\endgroup$ Oct 29 '09 at 18:01
  • $\begingroup$ I mean, a lot of the time what you do at each step is improve the solution locally in a way so obvious as to be almost stupid -- the miracle that occurs/meta-algorithm to consider is that the small local improvements don't eventually start cancelling each other out. I don't see an easy way to fit the three-squares theorem into this paradigm, though. $\endgroup$ Oct 29 '09 at 18:20

Perhaps not what you're looking for, but superficially this looks like a minimization procedure under constraint: rounding to the closest integer point means minimizing the Euclidean distance to the integer lattice, then the straight line to C means projecting back on the constraint manifold. (I'll try to see which one procedure in particular, could be simply gradient descent.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.