# What is the simplest ellipse that goes through exactly 13 lattice points?

The ellipse $-30 x + 3 x^2 - 10 y - 3 x y + 4 y^2$ goes through exactly 11 lattice points.

Another such ellipse is $4 - 30 x + 2 x^2 - 5 y - x y + 3 y^2$. What is the simplest ellipse that goes through exactly 13 lattice points?

1. Here are simple ellipses that go through exactly
2. 5 lattice points through 12 lattice points.
4. ---
5. $x + 4 x^2 - 8 y + 5 x y + 4 y^2$
6. $-1 + x^2 - x y + y^2$
7. $-3 - 13 x + 2 x^2 + x y + 3 y^2$
8. $-2 - 3 x + x^2 - 2 x y + 2 y^2$
9. $-7 x + x^2 - x y + y^2$
10. $-9 x + x^2 + 2 y^2$
11. $4 - 30 x + 2 x^2 - 5 y - x y + 3 y^2$
12. $-1 - 6 x + x^2 - x y + y^2$
13. $−9 x^2−11 x y−13 x−4 y^2+17 y−4$
14. $5 x−10 x^2−6 y−15 x y−6 y^2$
15. $12+12 x−9 x^2+11 y+5 x y−y^2$
16. $−10x^2−20 x y−20 x−11 y^2+11 y$
17. ???

There is a Shinzel circle that goes through exactly 13 points, but it is very likely not a minimal solution. For circles, here are the best-known sizes for smallest Lattice Circles that go through a particular number of points. I don't have an answer for 13 points here, either.

-
What is "simple" for you and how do you select your points? I think lattice points just means that no 3 points are on a line? –  Listing Oct 2 '11 at 18:48
Integer lattice points on a cartesian grid, such as (0,0) and (1,1). Simple can be either by area, or by maximal coefficient. If there is another ellipse meeting the requirements with a smaller area and smaller maximal coefficient, it wouldn't be the simplest. –  Ed Pegg Oct 2 '11 at 18:59
I suspect this problem is quite difficult since it's closely related to counting rational points on a circle (i.e. how many Gaussian integers are there for a fixed norm? See "Unsolved Problems" at en.wikipedia.org/wiki/Gaussian_integer ). –  Bill Cook Oct 2 '11 at 19:02
IN a circle is different than ON a circle. I've added a link on Schinzel circles -- for any $n$, a circle passing through exactly $n$ points is given by Schinzel's method. But this is almost never the simplest solution. –  Ed Pegg Oct 2 '11 at 19:14
Are your solutions for 5 through 12 the "simplest" solutions (whatever that means for you)? –  TonyK Oct 2 '11 at 20:36

(Updated)

I will show images first (explanation - after):

And a few ellipses with 36, 48 lattice points:

We will consider ellipses with format $a_{11} x^2 + a_{12} xy + a_{22} y^2 + a_{13}x +a_{23} y + a_{33} = 0$, where
1) $0 < a_{11} \le a_{22}$ (otherwise we can make exchange $x' = y$, $y'=x$);
2) $a_{12} \le 0$ (otherwise we can replace $y' = -y$).

We'll denote:
$a$ $-$ semi-major axis;
$b$ $-$ semi-minor axis;
$S$ $-$ square;
$M = \max \{ |a_{11}|, |a_{12}|,|a_{22}|,|a_{13}|,|a_{23}|,|a_{33}| \}$;
$\Sigma = |a_{11}|+|a_{12}| + |a_{22}| + |a_{13}| + |a_{23}| + |a_{33}|$.

I see 2 (or more) kinds of "smallness":
A. by semi-major axis ($a$);
B. by square ($S$);
(C). (by max coefficient);
(D). (by sum of coefficients).

A. Priorities to minimize: $a \rightarrow S \rightarrow M \rightarrow \Sigma \rightarrow |a_{13}|+|a_{23}| \rightarrow \max\{|a_{13}|,|a_{23}|\} \rightarrow (a_{13} \le 0)$ ;

B. Priorities to minimize: $S \rightarrow a \rightarrow M \rightarrow \Sigma \rightarrow |a_{13}|+|a_{23}| \rightarrow \max\{|a_{13}|,|a_{23}|\} \rightarrow (a_{13} \le 0)$;

For example, if we will have big amount of ellipses with the same $a$ and $S$, then we will choose ellipse(s) with smallest $M$. If there are a few ellipses with the same $a$, $S$, $M$, $\Sigma$, then we'll choose ellipse(s) with smallest sum $|a_{13}|+|a_{23}|$. ... while we will get 1 ellipse.

How to calculate $a, S$, if we know ellipse formula?
We will denote $$I_1 = 2a_{11}+ 2a_{22} > 0,$$ $$I_2 = \left| \begin{array}{cc} 2a_{11} & a_{12} \\ a_{12} & 2a_{22} \end{array} \right| = 4a_{11}a_{22}-a_{12}^2 > 0,$$ $$I_3 = - \left| \begin{array}{ccc} 2a_{11} & a_{12} & a_{13} \\ a_{12} & 2a_{22} & a_{23} \\ a_{13} & a_{23} & 2a_{33} \end{array} \right| > 0;$$ then we can rewrite ellipse equation: $$a_{11} x^2 + a_{12} xy + a_{22} y^2 = \frac{I_3}{I_2};$$ let $\lambda_a, \lambda_b$ are roots of equation $$\left| \begin{array}{cc} 2a_{11}-\lambda & a_{12} \\ a_{12} & 2a_{22}-\lambda \end{array} \right| = \lambda^2 - I_1 \lambda + I_2 = 0,$$ so,
$\lambda_a = (a_{11}+a_{22})+\sqrt{(a_{22}-a_{11})^2+a_{12}^2}$,
$\lambda_b = (a_{11}+a_{22})-\sqrt{(a_{22}-a_{11})^2+a_{12}^2}$,
then
$\displaystyle a = \frac{\sqrt{I_3 \lambda_a}}{I_2}$,     $\displaystyle b = \frac{\sqrt{I_3 \lambda_b}}{I_2}$,     $\displaystyle S = \pi a b = \pi \frac{I_3}{I_2 \sqrt{I_2}}$.

Here is the table of smallest (by $a$ or by $S$) ellipses with $n$ lattice points (up to $n=25$).

\begin{array}{|l|l|l|r|r|} \hline Lattice & formula & \min a / & a & S \\ points & & \min S & & \\ \hline 3 & x^2 +xy + y^2 -x-y=0 & S & 0.81649658 & 1.20919958 \\ \hline 4 & x^2 + y^2 -x-y=0 & a, S & 0.70710678 & 1.57079633 \\ \hline 5 & 2x^2 -xy + 2y^2 -x+y-3=0 & a, S & 1.46059349 & 5.19139671 \\ \hline 6 & x^2 -xy + y^2 -1=0 & a, S & 1.41421356 & 3.62759873 \\ \hline 7 & 2x^2 -xy + 2y^2 -5x-4y-6=0 & a & 2.92118697 & 20.76558682 \\ & 2x^2 -xy + 4y^2 -7x-7y-7=0 & S & 3.09818451 & 20.38568713 \\ \hline 8 & x^2+y^2-x-y-2=0 & a, S & 1.58113883 & 7.85398163 \\ \hline 9 & x^2-xy+3y^2-7x-6y=0 & a, S & 4.81580610 & 38.75014739 \\ \hline 10 & x^2-xy+4y^2-5x-5y-6=0 & a, S & 4.17287179 & 25.95698353 \\ \hline 11 & 3x^2-3xy+4y^2-21x-21y-10=0 & a, S & 8.00878321 & 123.82952163 \\ \hline 12 & x^2+y^2-5x-5y=0 & a & 3.53553391 & 39.26990817 \\ & x^2-xy+y^2-2x-2y-3=0 & S & 3.74165739 & 25.39319110 \\ \hline 13 & 2x^2-xy+3y^2-31x-26y-25=0 & a, S & 11.67004201 & 319.90071698 \\ \hline 14 & x^2-xy+4y^2-12x-9y-13=0 & a, S & 8.34574359 & 103.82793410 \\ \hline 15 & 2x^2-xy+5y^2-39x-36y-41=0 & a, S & 13.28106447 & 340.53118449 \\ \hline 16 & x^2+y^2-7x-7y-8=0 & a, S & 5.70087713 & 102.10176124 \\ \hline 17 & 2x^2-xy+3y^2-51x-51y-54=0 & a, S & 20.21310568 & 959.70215095 \\ \hline 18 & x^2-xy+y^2-7x-7y=0 & a, S & 9.89949494 & 177.75233769 \\ \hline 19 & 2x^2-xy+3y^2-61x-61y-6=0 & a, S & 23.34008401 & 1279.60286793 \\ \hline 20 & 2x^2-xy+2y^2-27x-27y-29=0 & a & 13.46600658 & 441.26871995 \\ & x^2+5y^2-31x-25y-12=0 & S & 16.83745824 & 398.30699525 \\ \hline 21 & 2x^2-xy+5y^2-81x-81y-8=0 & a, S & 26.56212894 & 1362.12473794 \\ \hline 22 & 4x^2-2xy+9y^2-194x-179y-30=0 & a & 31.84451541 & 2050.29169319 \\ & x^2-xy+10y^2-73x-61y-24=0 & S & 40.56562661 & 1609.78378121 \\ \hline 23 & 2x^2-xy+3y^2-105x-105y-54=0 & a & 40.42621136 & 3838.80860378 \\ & 3x^2-3xy+4y^2-120x-121y-3=0 & S & 44.04830766 & 3745.84302935 \\ \hline 24 & x^2+y^2-17x-17y-18=0 & a & 12.74754878 & 510.50880621 \\ & x^2-xy+y^2-9x-9y-10=0 & S & 13.49073756 & 330.11148429 \\ \hline 25 & 3x^2-xy+8y^2-279x-271y-84=0 & a, S & 57.49719096 & 6287.89822644 \\ \hline \cdots & \cdots & \cdots & \cdots & \cdots \\ \end{array}

-

After playing a bit around with mathematica (very simply bruteforce script) I found

$-9 x^2-11 x y-13 x-4 y^2+17 y-4 = 0$

to be an ellipse with 13 lattice points. To see the number of lattice points I used this:

Count[Flatten[
Table[-9 x^2-11 x y-13 x-4 y^2+17 y-4 == 0, {x, -27,
3}, {y, -3, 40}]], True]


Which returns 13 in this case. I took the minimal and maximal values for x and y from the picture:

(I admit it is a bit bigger than your examples for 12 :-) )

Are you really interested in the smallest area now or the smallest coefficients? If you want I can investigate a bit more and see what I can do...

For the bruteforcer I just take this formula, look for the x-region of the ellipse and test the points to be integers.. the code is REALLY ugly so I will not put it here, but the idea is simple.

Edit: Here is one with 14:

$5 x - 10 x^2 - 6 y - 15 x y - 6 y^2 = 0$

Here is one with 15:

$12 + 12 x - 9 x^2 + 11 y + 5 x y - y^2 = 0$

Here 16:

$-10 x^2-20 x y-20 x-11 y^2+11 y = 0$

For bigger instances I ported the source to C because it is faster. I believe in a few hours it can try all coefficients also for high numbers of lattice points. Here is the source if you want to give it a try: http://pastebin.com/R3hLbWVA (I felt it would blow this answer if I paste it in). Could not find one for 17 yet, you can use the program to generate all formulas for small coefficients though (to see if it is possible). Also numerical errors might occur therefore I verify the results with mathematica.

I will stop looking for now, just for the enjoyment here is one with 36 lattice points (it seems to be much easier to find ones with an even amount of lattice points):

$-10 x^2+14 x y+20 x-5 y^2+15 y=0$

Image(ugly):

Also the source to generate the images:

ContourPlot[
20 x - 10 x^2 + 15 y + 14 x y - 5 y^2 == 0, {x, -3, 206}, {y, -3,
300}, GridLines -> {Range[-3, 206], Range[-3, 300]}]

-
Yikes, it's huge! But that's now the best known solution. I am interested in 14, 15, 16, and so on as well. I imagine 17 and 19 will be hard. Very nice! I've been wondering about this one. –  Ed Pegg Oct 2 '11 at 22:56
I found a smaller one :-) just updated it –  Listing Oct 2 '11 at 22:57
Very nice. I've added your ellipses to my table. I'm starting to suspect that my solution for 11 points isn't optimal, since it has higher coefficients than your 13 and 15. –  Ed Pegg Oct 2 '11 at 23:15
You can use my source to generate them. Note that you could easily change it to look for multimple amounts of lattice points. –  Listing Oct 2 '11 at 23:16