11
$\begingroup$

Consider a disk of radius $r$ centered at $(x,y)$, where $(x,y)$ is chosen from the uniform distribution on $[0,1) \times [0,1)$, and let the random variable $N$ be the number of lattice points in the disk. The expected value of $N$ is clearly $\pi r^2$, but what is the variance of $N$, and why?

I have the impression that the solution (published by Kendall in the mid-20th century and perhaps found earlier by others) is straightforward, involving the Fourier transform of the indicator function of the disk (or rather a doubly-periodic union of disjoint copies of the disk), and using nothing more arcane that Parceval's identity and Bessel functions, but I haven't been able to find the details anywhere on the web, and I'm not enough of an analyst to work them out myself.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ It's not clear to me whether you know the bibliographic details for Kendall: it's David G. Kendall, On the number of lattice points inside a random oval, Quart. J. Math., Oxford Ser. 19 (1948) 1–26, MR0024929 (9,570b). $\endgroup$
    – Gerry Myerson
    Aug 3, 2011 at 0:43
  • $\begingroup$ @Gerry, while that is the right reference, I believe Kendall's article "On the number of points of a given lattice in a random hypersphere" is also worth looking at in terms of a more general result and exposition. $\endgroup$
    – Gjergji Zaimi
    Aug 3, 2011 at 1:01
  • $\begingroup$ This is probably a grotty way to do it but I guess you could compute the expected value of N^2 by summing over pairs of lattice points (p,q) the proportion of circles enclosing both p and q. $\endgroup$
    – JSE
    Aug 3, 2011 at 1:37
  • $\begingroup$ I was aware of both of these articles, but my library access is limited at the moment, and neither article is available over the Internet for free, so I was hoping to find something on the web that would provide the details I need. (This seems like a reasonable hope; if the argument is really as straightforward as I describe, one could imagine some bright undergraduate presenting it as part of a senior thesis.) $\endgroup$
    – James Propp
    Aug 3, 2011 at 4:24
  • $\begingroup$ Is qjmath.oxfordjournals.org/content/os-19/1/1.full.pdf not freely accessible? $\endgroup$
    – Gerry Myerson
    Aug 3, 2011 at 5:23

3 Answers 3

Reset to default
1
$\begingroup$

Let G = Fourier transform of char fn of disc of radius R.

Number of points within the disc is (Poisson summation) the sum of G at lattice points n in Z^2.

Shifting the disc by a vector x in R^2/Z^2 multiplies the contribution of lattice point n by e^{2 pi i n.x}.

Since these are orthonormal as functions of x (in R^2/Z^2), the variance is the sum of squares of values of G at nonzero lattice points.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The anonymous poster's answer is quite helpful, but it's only the first part of the analysis. Can anyone tell me how to evaluate the sum of the values of G at nonzero lattice points, or at least determine how quickly it goes to infinity with r? $\endgroup$
    – James Propp
    Aug 3, 2011 at 15:47
0
$\begingroup$

Actually, a more recent, and probably more useful reference is:

Distribution of the error term for the number of lattice points inside a shifted circle PM Bleher, Z Cheng, FJ Dyson… - Communications in mathematical physics, 1993 - Springer

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Igor: Judging from its first page (viewable at springerlink.com/content/78617554p6g8kkr1 ), I would guess that the paper of Bleher et al. is concerned with much subtler issues than the ones that interest me at present. Or does the article recapitulate Kendall's argument in some early expository section? $\endgroup$
    – James Propp
    Aug 3, 2011 at 4:20
0
$\begingroup$

It is obvious that the variance is of the order of Cr^2 (variance =E(X-Y)^2 and (X-Y) counts the lattice points that are in the symmetric difference of two disks of radius r whose centers are offset by about a unit distance...). But I guess you want the constant C?

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm actually more interested in the exponent than in the constant, AND I love coupling arguments, so I'd like to see if Manjunath's approach can be pushed through to give $Ar^2 \leq Var(N) \leq Br^2$ for positive constants $A,B$. But I don't see it (in either direction, though I suspect Markoff's inequality will give us something). Sure, the symmetric difference has small area, but it could still have lots of lattice points in it. (Minor quibble: variance equals HALF of $E((X-Y)^2)$ where $X,Y$ are independent draws from the distribution of interest.) $\endgroup$
    – James Propp
    Aug 4, 2011 at 14:49
  • $\begingroup$ OK, I've thought a little bit harder in the past 5 hours, and I see how to get the upper bound now, by coordinatizing points in the symmetric difference radially and circumferentially. If the region is radially narrow enough, two distinct lattice points that belong to it can't be too close circumferentially. So we can get a deterministic bound of the form constant-times-$r$ on the number of lattice points in the symmetric difference. So the variance is at most constant times $r^2$. But how do we get a lower bound? $\endgroup$
    – James Propp
    Aug 4, 2011 at 20:29
  • $\begingroup$ We have $E|X-Y| \asymp r$ with some universal constants (at least for $r>1$), we get $2Var(X) = E(X-Y)^2 \geq (E|X-Y|)^2$. $\endgroup$
    – Omer
    Aug 8, 2011 at 23:33
  • $\begingroup$ What's the geometrical argument for $E|X-Y| \asymp r$? I don't see it. $\endgroup$
    – James Propp
    Aug 9, 2011 at 2:44
  • $\begingroup$ hmmm. good point. $\endgroup$
    – Omer
    Aug 10, 2011 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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