Euler, Erdős

Today, I'll translate the proof for a theorem by André Schinzel that gives a circle with \(n\) integer coordinates (also known as Lattice Points) on its circumference, for any given \(n\). The theorem was published in L'Enseignement Mathématique in 1958 and can be found here.

Lemma. For any non-negative integer \(k\), \( x^2 + y^2 = 5^k \) has \(4(k+1)\) integer solutions.

Proof: When decomposing number \(n\) into the sum of two squares, it helps to use Gaussian Integers \({\mathbb Z}[i]\) because it is equivalent to factoring \(n\). For instance, \(1^2+2^2=(1+2i)(1-2i)\). So, \(5^k = (1+2i)^k(1-2i)^k\). Lastly, for any \(0\le j \le k\), \[ \begin{aligned} 5^k &= \left( (1+2i)^j (1-2i)^{k-j} \right)\left( (1+2i)^{k-j} (1-2i)^{j} \right) \\ &= (a_j+b_ji)(a_j-b_ji) \\ &= a_j^2 + b_j^2 = (-b_j)^2 + (a_j)^2 \\ &= (b_j)^2 + (-a_j)^2 = (-a_j)^2 + (-b_j)^2 \end{aligned} \] and \(a_j,b_j>0\). Since there are \(k+1\) choices for \(j\) and, for each \(j\), there are \(4\) integer solutions. There must be at least \(4(k+1)\) integer solutions to the equation \(x^2+y^2=5^k\).

It is easy to check that any factoring of \(5\) is of the form \(i^m(1+2i)(1-2i)\) for some \(m\). Therefore, we exhausted all solutions and the equation has precisely \(4(k+1)\) solutions. \(\Box\)

Schinzel's Theorem. For any given positive integer \(n\), there is a circle in the plane which has \(n\) lattice points on its circumference. Particularly, this circle is an example of one solution: \[ \begin{cases} \left(2x-1\right)^2+(2y)^2=5^{k-1}, \quad & n=2k \\ \left(3x-1\right)^2+(3y)^2=5^{2k}, \quad & n =2k+1 \end{cases} \]

Proof: Suppose \(n=2k\). According to the lemma, the circle \(x^2+y^2=5^{k-1}\) has \(4k\) lattice points. Since \(5^{k-1}\) is odd, then only one of \(x\) and \(y\) is even. Restricting \(y\) to be even discards half of the points. Therefore \((2u-1)^2+(2v)^2=5^{k-1}\) has \(2k=n\) lattice points.

Otherwise, let \(n=2k+1\). The lemma implies \(x^2+y^2=5^{2k}\) has \(4(2k+1)\) lattice points. Note that \(5^{2k} \equiv 1 \pmod 3\). So only one of \(x\) and \(y\) is a multiple of \(3\). The restriction \(y \equiv 0 \pmod 3\) discards half the points. Since there is also a bijection between solutions \((3u-1,3v)\) and \((3u'+1,3v)\), namely, \(u'=-u\), then the restriction \(x=3u-1\) discards half of the remaining points. Therefore \((3u-1)^2+(3v)^2=5^{2k}\) has \(2k+1=n\) lattice points. \(\Box\)

Fig 1. A Few Examples