8
$\begingroup$

How many points of the integer lattice ${\mathbb Z}^2$ can an axis-parallel ellipse of radius $r$ contain on its boundary? (that is, we consider ${\mathbb Z}^2$ as lying in ${\mathbb R}^2$). Alternatively, this appears to be very similar to the question of how many points can the boundary of any axis-parallel ellipse contain from an $r\times r$ section of the integer lattice.

Let us say that the ellipse is defined as $(ax-b)^2+(cy-d)^2=r^2$. If $a,b,c,d$ are integers, we can reduce the problem to asking for the number of integer solutions to of an equation of the form $ax^2+by^2=r^2$ with integers $a,b$. This is known to have at most $r^{\frac{c}{\lg \lg r}}$ solutions, for some constant $c$. Does a similar bound exist for every axis-parallel ellipse?

In case it helps, I mainly care about the case where $a,b,c,d$ are not much larger than $r$.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Perhaps this might help? Cilleruelo, Javier, and Antonio Cordoba. "Lattice points on ellipses." Duke Mathematical Journal 76.3 (1994): 741-750. PDF download of preliminary version. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 22, 2015 at 0:12
  • $\begingroup$ Thank you Joseph. It is an interesting result, but unfortunately they consider only ellipses with a center at the origin. Non-integer centers seem to me as the main difficulty here. $\endgroup$
    – Adam Sheffer
    Commented Sep 22, 2015 at 1:00
  • $\begingroup$ Can you link or sketch the proof of $r^{c/\log\log r}$? $\endgroup$
    – Xiaoyu He
    Commented Sep 22, 2015 at 3:30
  • 1
    $\begingroup$ Sure. See for example Equation (11.9) in Section 11.2 of "Topics in Classical Automorphic Forms" by Iwaniec. By this formula the number of solutions to $ax^2+bxy+cy^2=r$ (under several additional conditions) is $\sum_{d|r}\left(\frac{b^2-4ac}{d}\right)$ times a small constant. The number of divisors or $r$ is at most $r^{c/\lg\lg r}$ and this is obviously an upper bound for above sum. $\endgroup$
    – Adam Sheffer
    Commented Sep 22, 2015 at 3:44

1 Answer 1

Reset to default
3
$\begingroup$

For general ellipses I doubt you can do much better than Bombieri-Pila sort of bounds:

MR1016893 (90j:11099) Reviewed 
Bombieri, E.; Pila, J.
The number of integral points on arcs and ovals. 
Duke Math. J. 59 (1989), no. 2, 337–357. 
11P21 (11D99)

(you should check out the many papers that cite this, as well, but most of them seem to be interested in higher degrees/dimensions).

For integer coefficients, the best seems to be

Lattice points on Ellipses Cilleruelo and Cordoba, DMJ 1994

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .