## 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