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.


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.


Fig 1. A Few Examples

One thought on “Schinzel's Theorem

Comments are closed.