7
$\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$.

$\endgroup$
  • 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 Sep 22 '15 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 Sep 22 '15 at 1:00
  • $\begingroup$ Can you link or sketch the proof of $r^{c/\log\log r}$? $\endgroup$ – Xiaoyu He Sep 22 '15 at 3:30
  • $\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 Sep 22 '15 at 3:44
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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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