# 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}$ ,

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:

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