# Schinzel's Theorem

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