MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 11 down vote accepted

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.

share|cite|improve this answer

Your Answer


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.