# On circles and ellipses drawn on an infinite planar square lattice

Consider a plane with a square lattice formed by all points with both coordinates as integers. As can be easily seen, a simple parabola can be found that passes through infinitely many of the square lattice points. However,

1. Given any positive integer n, can we always find a sufficiently large circle drawn on the plane that passes through at least n lattice points? Can such circles be found if the center is not to be a lattice point? What if we require the circle to pass through exactly n lattice points?

2. Question 1 has a natural restatement if instead of circles, we look at ellipses (either all with a given eccentricity e or with e that can be freely chosen). The ellipses need not be axis parallel.

3. And what can one say if the lattice of points has as unit cell not a square but a general parallelogram?

Note 1: Lattice points on the boundary of an ellipse discusses a related question.

Additional Question (added after Prof. Elkies's affirmative answer to questions 1 to 3): What happens in 3D and higher dimensions?

• For your first question in 1), Wikipedia states that for a given integer $n$ there exist $n$ different pythagorean triples with the same hypothenuse. This would mean that we can always find a sufficiently large circle that passes through at least $n$ lattice points if the center is at a lattice point. en.wikipedia.org/wiki/Pythagorean_triple#Special_cases – araomis Jan 18 at 18:41
• If a circle passes through 3 points with rational coordinates then the center must have rational coordinates. (The center can be obtained by intersecting the perpendicular bisectors which are given by rational equations) – Gjergji Zaimi Jan 18 at 19:04

(1-2) Yes. For each integer $$n > 0$$ the circle $$x^2 + y^2 = 13^{n-1}$$ passes through exactly $$4n$$ lattice points, namely those with $$z := x+iy = \zeta (3+2i)^a (3-2i)^b$$ with $$a,b$$ nonnegative integers such that $$a+b=n-1$$, and $$\zeta \in \{1, i, -1, -i\}$$. Given $$(a,b)$$, exactly one of the four choices of $$\zeta$$ makes $$x \equiv 2y+1 \bmod 5$$ (because $$\{1, i, -1, -i\}$$ is a complete set of nonzero residues modulo $$2+i$$, and $$z \notin (2+i){\bf Z}[i]$$). So the circle $$(2x-y+1)^2 + (x+2y)^2 = 13^{n-1}$$ passes through exactly $$n$$ lattice points. The left-hand side $$(2x-y+1)^2 + (x+2y)^2$$ is also $$5(x^2+y^2) + 4x - 2y + 1 = 5 \left[ \Bigl(x + \frac25\Bigr)^{\!2} + \Bigl(y - \frac15\Bigr)^{\!2} \right],$$ so we have a circle centered at $$(x,y) = (-2/5, 1/5)$$.

(3) Yes. Use the construction of (2), and (if you don't accept a circle as a special case of an ellipse) apply a linear change of variable such as replacing $$y$$ by $$x+y$$.

• Thanks very much! Will some more general claim on the lines: "for any n and for any planar lattice, conics of any type (ellipse, parabola, hyperbola) may be found that pass thru exactly n lattice points" hold? – Nandakumar R Jan 19 at 6:06
• You're welcome. For the "more general" question --  Ellipse, yes: start with the circle that works for the square lattice, and apply a linear transformation to take the square lattice to "any planar lattice". Parabola and hyperbola, I don't think so: once such a conic has a few integral points (probably 5 is enough) it has infinitely many. In the hyperbolic case this will come down to a Fermat-Pell equation. – Noam D. Elkies Jan 19 at 15:43
• Thanks again. That the conics have different behaviors w r to the integer lattice is a surprise! – Nandakumar R Jan 22 at 6:23

Such circles are known as Schinzel Circles. See also Kulikowski's Theorem for the sphere. According to zbmath Kulikowski proved his theorem in arbitrary dimension.

• Thanks very much for those pointers! Just one further query: Kulikowski's proof (as given in Honsberger's 'Gems') shows how to construct a sphere such that exactly n points lie on it but those points are all coplanar. Is there a way to show the existence of a sphere in a 3D lattice such that it passes thru exactly n points, say, in general position, for any n? – Nandakumar R Jan 19 at 18:35
• Yes, but the easiest way to do that is not very exciting: start with a Schinzel circle (or some variant such as the one I gave) with n-1 points, make it the intersection of R^2 with a large sphere in R^3 whose center has a positive z-coordinate, and use the lattice generated by Z^2 and the north pole . . . – Noam D. Elkies Jan 22 at 4:41
• Thank you. I guess this gets n-1 of the 3D lattice points except the north pole on one plane. How could one possibly get a sphere to pass through n lattice points such that no 4 of them are coplanar? – Nandakumar R Jan 22 at 6:35