# 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