15
$\begingroup$

Consider origin-centered circles $C(r)$ of radius $r \le 1$. I am seeking to learn how many rational points might lie on $C(r)$, where each rational point coordinate has height $\le h$. For example, these are the rationals in $[0,1]$ with $h \le 5$: $$ \left( 0,\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5}, \frac{2}{3},\frac{3}{4},\frac{4}{5},1 \right) $$ Rational points of height $\le h$ have both coordinates from this list, multiplied by $\pm 1$.

Q. What is the growth rate of the maximum number of rational points of height $\le h$ on $C(r)$, $r \le 1$, as a function of $h$?

Here is a bit of data up to $h=20$:


          HeightsPlot
For example, for $h=7$, $C(\frac{5}{7})$ passes through these $12$ points: $$ \left( -\tfrac{4}{7} , -\tfrac{3}{7} \right), \left( -\tfrac{3}{7} , -\tfrac{4}{7} \right), \left( 0 , -\tfrac{5}{7} \right), \left( \tfrac{3}{7} , -\tfrac{4}{7} \right), \left( \tfrac{4}{7} , -\tfrac{3}{7} \right), \left( \tfrac{5}{7} , 0 \right), $$ $$ \left( \tfrac{4}{7} , \tfrac{3}{7} \right), \left( \tfrac{3}{7} , \tfrac{4}{7} \right), \left( 0 , \tfrac{5}{7} \right), \left( -\tfrac{3}{7} , \tfrac{4}{7} \right), \left( -\tfrac{4}{7} , \tfrac{3}{7} \right), \left( -\tfrac{5}{7} , 0 \right) $$ If I've calculated correctly, no circle passes through more than $12$ points of height $\le 7$. Circles that achieve these maxima are illustrated below.
          RationalCircles
          Background points are the rational points of height $h \le 20$.
Added. Since the radii that achieve the maxima I found for $13 \le h \le 20$ are all exactly $1$, it may be that the question can be reduced to counting the number of rational points of height $\le h$ on just specifically $C(1)$.
Answered. Lucia's answer matches even the small-$h$ data I gathered:
          RatPtsLucia


$\endgroup$
  • 3
    $\begingroup$ I think if we look at the lattice points on circle $C(hr)$, we can obtain some good upper bound and approximately rate change. So, I think we have $$\pi(hr)^2-\pi\sqrt{2}hr+\frac{\pi}{2}\leq R(hr)\leq \pi(hr)^2+\pi\sqrt{2}hr+\frac{\pi}{2},$$ where $R(hr)$ shows the total number of lattice points in the circle $C(hr)$. I think $R(hr)$ is good lower and upper bound for your question and so when $h$ tend to infinity, the average number of such points you want tend to $\pi$. $\endgroup$ – Shahrooz Janbaz Sep 28 '15 at 20:39
  • 3
    $\begingroup$ Each point on $C(1)$ correspond to Pythagorean Triple $2mn$, $m^2-n^2$, $m^2+n^2\le h$. $\endgroup$ – Alexey Ustinov Sep 29 '15 at 3:27
10
$\begingroup$

I'll content myself with counting the number of points on $C(1)$ (which should surely be close to the maximum) -- the answer is quite nice, it is about $ \frac{4}{\pi } h$.

To see this, note that we are counting essentially Pythagorean triples $u^2-v^2, 2uv, u^2+v^2$, with $u^2+v^2\le h$ and we may suppose that $u$ and $v$ are non-negative, that $u$ and $v$ are coprime, and that $u^2+v^2$ is odd. The lattice point count we need is four times this number, since we must also count the lattice point $(2uv/(u^2+v^2),(u^2-v^2)/(u^2+v^2))$ (in addition to $((u^2-v^2)/(u^2+v^2),2uv/(u^2+v^2))$, and we must also allow the $2uv/(u^2+v^2)$ coordinate to be negative).

Thus to summarize we want $$ 4 \sum_{n\le h, n \text{ odd }} R(n), $$ where $R(n)$ is the number of ways of writing $n$ as $u^2+v^2$ with both $u$ and $v$ non-negative and coprime (taking care to set $R(1)$ to be $1$). A little number theory, going back to Fermat, gives that $R(n)$ is a multiplicative function with $R(2^k)=0$ (so we don't have to worry about $n$ odd anymore), $R(p^k)=2$ for $p\equiv 1\pmod 4$ and $k\ge 1$, and $R(p^k)=0$ if $p\equiv 3\pmod 4$. For example if $h=20$, then $R(1)=1$, $R(5)=2$, $R(13)=2$, and $R(17)=2$ and the rest are zero, and the number here is $28$ as in the numerics.

From here a standard argument (or one can do this via counting lattice points in a circle) leads to the asymptotic $$ 4 \sum_{n\le h} R(n) \sim 4 \frac{1}{2} \prod_{p\equiv 1 \pmod 4} \Big(1+\frac{2}{p}+\frac{2}{p^2}+\ldots \Big) \Big(1-\frac 1p\Big) \prod_{p\equiv 3\pmod 4} \Big(1-\frac 1p\Big) h, $$ and the above simplifies (using $1-1/3+1/5-1/7+\ldots =\pi/4$ and $1/1^2+1/3^2+1/5^2+\ldots = \pi^2/8$) to give $$ \sim 2 \frac{\pi/4}{\pi^2/8} h = \frac{4}{\pi} h. $$

One should be able to refine this to count lattice points on other circles as well, and thus show that radius $1$ does achieve the maximum.

$\endgroup$
  • $\begingroup$ Beautiful! ${}$ $\endgroup$ – Joseph O'Rourke Sep 29 '15 at 11:45

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.