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

Question

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.
3. What is an ellipse for 13 points? (Answers added)

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.

Answer 1

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 (area);
$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 \mathrm{Lattice} & \mathrm{equation} & \min a / & a & S \\ \mathrm{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}

Answer 2

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]}]