Minimum distance between adjacent concentric circles that cross integer lattice points - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T08:09:56Z http://mathoverflow.net/feeds/question/73024 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73024/minimum-distance-between-adjacent-concentric-circles-that-cross-integer-lattice-p Minimum distance between adjacent concentric circles that cross integer lattice points wolfrevo 2011-08-17T01:53:16Z 2011-08-17T04:08:50Z <p>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.</p> <p>A = { [$m$, $n$] | $m$ and $n$ are positive integer numbers} is a set of 2-D lattice points</p> <p>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. </p> <p>The problem is:</p> <p>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} ? </p> <p>The problem can be also described as: </p> <p>What is the explicit forms of asymptotics of the minimum distance between two adjacent concentric circles that cross integer lattice points?</p> <p>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.</p> <p>Thank you!</p> http://mathoverflow.net/questions/73024/minimum-distance-between-adjacent-concentric-circles-that-cross-integer-lattice-p/73026#73026 Answer by Noam D. Elkies for Minimum distance between adjacent concentric circles that cross integer lattice points Noam D. Elkies 2011-08-17T03:01:35Z 2011-08-17T04:08:50Z <p>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$.</p> <p>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 &mdash; presumably a <em>square</em> cavity &mdash; 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.</p> <p>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 <em>do</em> 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}$.</p> <p>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 &lt; \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 &lt; x^{2k}$ so $\log \prod_i p_i^2 &lt; 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 &mdash; unless somebody can provide a reference for a paper that already proved such a result &mdash; it looks like more effort than one expects to exert on a MathOverflow question...</p> <p><strong>EDIT</strong> A quick Google search turned up a reference:</p> <blockquote> <p>Heini Halberstam: Gaps in Integer Sequences, <em>Math. Magazine</em> <strong>56</strong> #3 (May 1983), 131-140</p> </blockquote> <p>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" (<em>Acta Arith,</em> <strong>29</strong> (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 <em>Advances in Math.</em> <strong>46</strong> (1982), 1-2.</p>