# Minimum distance between adjacent concentric circles that cross integer lattice points

This problem looks simple, but I searched around and couldn't find any similar problems or related resources. Hope someone could provide a clue or at least a hint of what class of prolbems it belongs to.

A = { [$m$, $n$] | $m$ and $n$ are positive integer numbers} is a set of 2-D lattice points

R = { $r$ | $r^2$ = $m^2$ + $n^2$ } is a set whose elements are the distance between the origin and the lattice points in the set A.

The problem is:

If we sort all the $r$ from set R and use these sorted $r$ to creat a series C = {$r{_1}$, $r{_2}$, $r{_3}$..., $r{_N}$}, where $r_i$ $\in$ R and $N\to\infty$, so that $r{_1}$ $\leq$ $r{_2}$ $\leq$ $r{_3}$... $\leq$ $r{_N}$, and we define $\Delta$$r{_i} = r_i$$_+$$_1 - r{_i}, what is the explicit forms of asymptotics of \Delta$$r_i$, such as $\Delta$$r_i \propto \frac{1}{r_i} ? The problem can be also described as: What is the explicit forms of asymptotics of the minimum distance between two adjacent concentric circles that cross integer lattice points? The motivation of this problem is that: integers m and n determine the electromagnetic resonance frequency r in a 2-D rectangular cavity, so \Delta$$r_i$ is the distance between two adjacent resonance frequencies.

Thank you!

-
You may want to look up the Gauss Circle Problem, which asks for the number of lattice points in a circle of radius $r$ centered at the origin, $\pi r^2 + E(r)$. Upper bounds on the error estimates give you crude upper bounds on the gaps between distances to lattice points. For example, the bound $E(r) = O(r^{131/208})$ tells you that $\Delta r_i = O(r_i^{131/208}/r_i) = O(r_i^{-77/208})$. The best this could possibly do, if someone solved the Gauss Circle Problem, would be a little worse than $O(r_i^{-1/2})$. However, the methods may be of interest. – Douglas Zare Aug 17 '11 at 4:12
@D.Zare: Halberstam's paper notes this connection too (though the best exponent known in 1983 was probably worse). – Noam D. Elkies Aug 17 '11 at 4:33

There cannot be an asymptotic answer, because $\Delta r_i$ can be as small as $c/r_i$ (with $c \rightarrow 1/2$ as $i \rightarrow \infty$), but $\Delta r_i$ is of order $(\log r_i)^{1/2} / r_i$ on average. Equivalently, $\Delta(r_i^2)$ can be as small as $1$ but is of order $\sqrt{\log r_i}$ on average. One can also construct gaps of length $\gg \log r_i / \log \log r_i$.

Clearly $\Delta(r_i^2)$ can be no smaller than $1$ because each $r_i^2$ is an integer. A difference of $1$ is easily attained. The proposer of the question asked about positive $m,n$, but the application to eigenmodes of a 2-dimensional cavity — presumably a square cavity — must allow $m=0$ or $n=0$ as well, and then it's clear that $r_i^2 = n^2 + 0^2$ and $r_{i+1}^2 = n^2 + 1^2$ works. Even if you insist on nonzero $m,n$, differences of 1 are easy to construct; e.g. if $n^2 = a^2 + b^2$ then $r_i^2 = a^2 + b^2$ and $r_{i+1}^2 = n^2 + 1^2$ differ by 1.

On the other hand, while the number of solutions of $m^2 + n^2 \leq r_0^2$ in positive $m,n$ is asymptotic to $\pi r_0^2 / 4$ as $r_0 \rightarrow \infty$, the set $R$ of possible $r$ values is not quite as dense as this suggests, because there's a lot of "degeneracy" (repetition) in the values of $m^2+n^2$; equivalently, as $x \rightarrow \infty$, the proportion of integers in $[1,x]$ that can be written as $m^2 + n^2$ goes to zero, so for those that do have such a representation the average number of representations must go to $\infty$. Indeed if $p$ is a prime congruent to $3 \bmod 4$ then no multiple of $p$ can be $m^2+n^2$ unless both $m$ and $n$ are multiples of $p$, which makes $m^2+n^2$ a multiple of $p^2$. This gives $p-1$ forbidden residues $\bmod p^2$. For any finite set $P$ of such primes, we deduce an upper bound $\beta_P := \prod_{p\in P} (1 - p^{-1} + p^{-2})$ on the density of integers representable as sums of two squares; since by Dirichlet the sum of $1/p$ over all such primes diverges, we find that $\log\beta_P$ can be made arbitrarily negative by taking $P$ large enough, which means that the density is less than any positive number, and is thus zero. A more refined analysis shows that the density in $[1,x]$ decays as $1/\sqrt{\log x}$.

Another way to use a finite list $p_1,\ldots,p_k$ of primes congruent to $3 \bmod 4$ is to choose for each of them one of the forbidden residues, i.e. some $r(p_i)$ that's divisible by $p_i$ but not by $p_i^2$, and consider the simultaneous congruences $N+i \equiv r(p_i) \bmod p_i^2$. By Chinese Remainder, there's a solution $N < \prod_{i=1}^k p_i^2$, which gives $k$ consecutive integers none of which is the sum of two squares. If we use all the $3 \bmod 4$ primes up to $x$, we get $k \sim x / 2 \log x$, and $\prod_i p_i^2 < x^{2k}$ so $\log \prod_i p_i^2 < 2k \log x \sim x$, whence we've constructed a "$\log/\log \log$" gap as claimed. There may be enough freedom in the choices we've made (including the order of the $p_i$) to squeeze a bit more out of this argument, but — unless somebody can provide a reference for a paper that already proved such a result — it looks like more effort than one expects to exert on a MathOverflow question...

EDIT A quick Google search turned up a reference:

Heini Halberstam: Gaps in Integer Sequences, Math. Magazine 56 #3 (May 1983), 131-140

The "$\log / \log\log$" bound (with the same Chinese Remainder) argument appears on page 136, followed by an asymptotic formula $A(x) \sim (\pi/\sqrt{12}) (x / \sqrt{\log x})$ for the number $A(x)$ of sums of two squares less than $x$. This formula is attributed to Landau 1908, though there's no paper of Landau in the bibliography. The bibliography does cite Iwaniec's "On the half-dimensional sieve" (Acta Arith, 29 (1976), 69-95) for an alternative approach, and also a two-page paper "On the gaps between numbers that are sums of two squares" by I.Richards in Advances in Math. 46 (1982), 1-2.

-