Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The ellipse $-30 x + 3 x^2 - 10 y - 3 x y + 4 y^2$ goes through exactly 11 lattice points. ellipse through 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. Lattice circles

share|improve this question
3  
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
2  
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
1  
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
show 1 more comment

2 Answers 2

up vote 11 down vote accepted

(Updated)

I will show images first (explanation - after):

ellipse with 3 lattice points (by square) ellipse with 4 lattice points

ellipse with 5 lattice points ellipse with 6 lattice points

ellipse with 7 lattice points (by axis) ellipse with 7 lattice points (by square)

enter image description here enter image description here

enter image description here enter image description here

enter image description here enter image description here

enter image description here enter image description here

enter image description here enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

And a few ellipses with 36, 48 lattice points:

enter image description here

enter image description here

enter image description here


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}

share|improve this answer
add comment

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:

enter image description here

(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$

enter image description here

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$

enter image description here

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):

enter image description here

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]}]
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.