Distribution of square roots mod 1

Question

I was wondering about the distribution of $\sqrt{p}$ mod $1$ this morning, as one does while brushing one's teeth. I remembered the paper of Elkies and McMullen (Duke Math. J. 123 (2004), no. 1, 95–139.) about $\sqrt{n}$ mod $1$, but hadn't really thought about it before.

Question 1: is $\sqrt{p}$ equidistributed mod $1$, as $p$ varies over all prime numbers? Is this known? Within range of current techniques?

Question 2: What about subtler statistics of $\sqrt{p}$ (and $\sqrt{n}$) mod $1$?

I made three plots, giving histograms of $\sqrt{n}$ mod $1$ (for natural numbers up to 100,000) and $\sqrt{p}$ mod $1$ (for primes up to 1 million) and (for comparison) a histogram of 100,000 samples drawn uniformly at random from {0,1,...,999}. Here they are for your enjoyment.

There's some wild stuff going on, I think!

Question 2(a): What's up with these sharp peak/valleys at rational numbers, in the distribution of $\sqrt{n}$ mod $1$? They are especially prominent at fractions of the form $a / 2^{e}$. How tall are these peaks near rational numbers? They persist when sampling from the primes, i.e., in the distribution of $\sqrt{p}$ mod $1$ too.

Question 2(b): Outside of those funky spots in 2(a), the distribution of $\sqrt{n}$ mod $1$ is far flatter than one would expect, e.g., from samples drawn uniformly at random as displayed in the bottom histogram. This must have been noticed and quantified before... what's the relevant quantitative result here?

Question 2(c): The distribution of $\sqrt{p}$ mod 1 displays the same funky spots near rational numbers, but otherwise seems much closer (in noise-volume) to the random samples at the bottom. Maybe for a larger sample, the funkiness goes away... I don't know. Explanations or conjectures are welcome.

Question 3: These seem like natural images to look at. If you know a reference where others have drawn such pictures or studied similar phenomena, I'd love to take a look!

-------------Update after answers below-----------------

It looks like the answer to Question 1 is YES. Lucia's answer below explains this, and also some of the flatness evident in the $\sqrt{n}$ distribution mod 1.

Igor and Aaron discuss the "spikes" around rational numbers. This seems related to binning: if our bins have width 1/1000, we see spikes at multiples of 1/2, 1/4, 1/5, 1/10, etc., related to divisors of 1000. Here's a new picture, which might help us understand the behavior of the distribution of $\sqrt{n}$ mod 1 near rational numbers. I've intentionally drawn the bins so that their endpoints lie on rational numbers with denominator up to 60. (I call this Farey-binning). This seems to bring the "spikes" around rational numbers down to the same size (independent of denominator).

I think I'll accept Lucia's answer soon, because it answers the most direct Question 1. But more insights are welcome.

Answer 1

You can certainly use Vinogradov's method to show that $\sqrt{p}$ is equidistributed $\pmod 1$. I haven't thought about more subtle properties, such as the gap spacing considered by Elkies and McMullen (or your other questions).

For the equidistribution, by Weyl's criterion it is enough to show cancellation in sums of the form $$ \sum_{n\le x} \Lambda(n) e(k\sqrt{n}) $$ for non-zero integers $k$. This is exactly the kind of sum to which Vinogradov's method applies. For example, see Exercise 2 on page 348 of Iwaniec-Kowalski which invites you to show that this sum is $\ll_k x^{\frac 56+\epsilon}$. Sums like this also appeared in the IHES paper of Iwaniec, Luo and Sarnak, where they show that better bounds for this sum (like $O(x^{\frac 12+\epsilon})$) have implications for the Riemann hypothesis for $GL(2)$ $L$-functions.

One should expect the exponential sum over primes above to be on the scale of $O(x^{\frac 12+\epsilon})$. This is in keeping with the plots for $\sqrt{p}$ looking like random noise. To see why $\sqrt{n}$ looks different and more flat, note that the number of $n\le N^2$ with $\{ \sqrt{n} \} \in (\alpha,\beta)$ is given by $$ \sum_{k\le N} \sum_{(k+\alpha)^2 < n <(k+\beta)^2} 1 = \sum_{k\le N} (\lfloor 2k\beta+\beta^2 \rfloor - \lfloor 2k \alpha + \alpha^2\rfloor). $$ Since the distribution of $\{ 2k\alpha+\alpha^2\}$ (and similarly for $\beta$) is extremely regular, one should expect this to be nailed down much more precisely than for primes.

Finally, suppose for example that $\alpha=a/q$ is a rational number (in lowest terms) with small denominator $q$, which let us assume odd for simplicity. Write $\alpha^2 = b/q + c/q^2$ with $0<c <q$. Note that $\{ 2k\alpha+\alpha^2\}$ will run over $c/q^2$, $1/q+c/q^2$, $\ldots$, $(q-1)/q+c/q^2$, and its average value will be $(q-1)/(2q) + c/q^2$. This can be noticeably different from the average value of $\{ x\}$, which is $1/2$, explaining the "spikes" near small rational numbers.

Answer 2

Here is an insight on what happens for the bin $[0.5,0.501]$

$n^2+n+\frac14=(n+\frac12)^2$ and $(n+\frac12+\frac3{8n+5})^2=n^2+n+1-\frac{3(8n+7)}{4(8n+5)^2}.$

So, until $\frac3{8n+5} \lt \frac1{1000},$ the bin in question will remain empty. That happens at $n=375$ when $\sqrt{375^2+375+1}=\sqrt{141001}=375.5009986671\cdots$ falls in that bin.

Since you only went out to $100000 \lt 317^2$ that bin was empty. Even if you went further, it would still be behind most of the others. The previous bin $[0.499,0.5]$ gets filled relatively high. Intuitively, the repulsion at $\frac12$ causes that. I'll explain a bit more at the end.

I think you will find that the spikes are especially high at bins starting with a fraction $\frac{a}{b}$ such that $b$ is a small divisor of $\frac1{1000}.$

Here is a similar plot with bins of width $\frac1{840}$ so $\frac{a}{b}$ starts a bin for $b=2,3,4,5,6,7,8,10,12$ and another where , if I did it right, each such fraction is the center of bin. I had expected a bigger spike for $\frac13$ in the first and am not sure how well I understand the second.

Here are some final thoughts: Suppose there are $N$ bins of width $\frac1N.$ Then as $n$ goes from $t^2$ to $t^2+2t+1$ there will be $2t+2$ new fractional data points. They will be very nearly evenly spaced since $$t+\frac{k}{2t}-\frac{k^2}{8t^3} \lt \sqrt{t^2+k} \lt t+\frac{k}{2t}.$$

Provided that $\frac{1}{2t}$ is larger than $ \frac1{N} $ by a bit,some of the bins will get one new thing and others none. In your calculation you went past $n=316^2$ but not all the way to $317^2.$ Since you had bin widths $\frac1{1000}$ that means that on the last full pass about $630$ bins got one new thing and the other $370$ did not. The bin $[0.5,0.501]$ is missed on each pass. However the bin $[0.499,0.5]$ gets something on pass $125$ with $\sqrt{125^2+125}=\sqrt{15750}=125.499004\cdots$ and every pass after that. So it ends up with about $317-125=192$ things. The average number is $100.$

LATER

Here are some plots which might be helpful. The first is all the points $(\frac{k}{2t},t)$ for $1 \lt t \lt 100$ and $1 \leq k \leq 2t-1.$ So pretty much like a Farey plot and with a vertical column above each small denominator rational.

The second is all the points $(\frac{k}{2t}-\frac{k^2}{8t^3},t).$ This looks like the first one with a leftward tug so the vertical columns are replaced by a curve having that column as an assymptote.

The graph we care about for this question is visually indistinguishable from the second. That would be the points $(\sqrt{t^2+k}-t,t).$

Note that $$\frac{k}{2t}-\frac{k^2}{8t^3} \lt \sqrt{t^2+k} \lt \frac{k}{2t}-\frac{k^2}{8t^3}+\frac{k^3}{16t^5}.$$

Farey Bins

For a rational number $\frac{a}b$ and integer $n$ we have $|\sqrt{n}-\frac{a}b|$ no smaller than about $\frac2{b^2\sqrt{n}}.$ This pushes (the fractional part of) square roots away from rational numbers with a force which is relatively stronger when the denominator is smaller. This is why if one wants the fractional part of $\sqrt{n}$ to be within $\frac{1}{1000}$ of $\frac12$ one needs $\sqrt{n}$ over $125.$ In fact $\sqrt{125^2+125}=125.5-0.000996$ and to be within $\frac{1}{1000}$ from above turns out to require $\sqrt{n}$ over $375.$

If one wants to bin to study this I would suggest taking the small denominator fractions as roughly the centers of bins. Below are two graphs illustrating this. I suggest using mediants as the bin boundaries. For example, sorting the frasctions in [0,1] with denominator up to $30$ by size, three consecutive ones are $\frac{13}{29},\frac9{20}, \frac{5}{11}.$ For the bin around $\frac{9}{20}$ I would take boundaries $\frac{13+9}{29+20}=\frac{22}{49}$ and $\frac{9+5}{20+11}=\frac{14}{31}.$ Note that the "center" $\frac9{20}$ is only about a bit more than a third of the way from the left endpoint to the right. This is because the $11$ pushes harder then the $29.$ This is one of the more extreme examples.

At any rate, the first graph below uses bins around the $277$ fractions in lowest terms $\frac{a}b$ with $1 \leq a \lt b \lt 30.$ Into the bins I put all $B=100806$ irrational fractional parts $\sqrt{t^2+k}-t$ for $1 \leq t \leq 2k$ and $1 \leq t \leq 316.$ The count $c$ is is then normalized to the ratio of $\frac{c}{B}$ to the expected value $\frac{B}{w}$ where $w$ is the width of the bin. I left a little space between bins. The maximum discrepancy is $ 0.060188$ and the average is $0.01477$

The second graph is the same thing except each bin is split at the rational it surrounds. The left part is colored red and the right part green. It seems that usually, but not always, it is as with $\frac12,$ the left half is over $1$ and the rights half under. I haven't looked into the details more closely. The variation is about three times as large. The maximum deviations for the left and right halves are $.1763188$ and $.160645$ while the average discrepancies are $0.047085$ and $0.045767.$

Answer 3

For the spikes, note that in your picture, the predicted number of points in the bin around 0 is 100, but there are 300 squares in your range. Similarly, there are 75 quarter-squares (where by quarter squares I mean numbers of the form $(n^2-1)/4,$ etc, so I think it explains some of the rational spiking.

Answer 4

It is known that the distribution of the pair correlations of $\sqrt{n}$ mod 1 is asympotitically Poissonian (that is, "random"). See [1]. Note that having Poissonian pair correlations implies being equidistributed [2], so this is a stronger result than the equidistribution result.

I don't know if a similar result is known for $\sqrt{p}$. Also, I don't know about results for higher correlations or neighbor spacings.

You might also want to check the related paper [3].

[1] El-Baz, Daniel; Marklof, Jens; Vinogradov, Ilya. The two-point correlation function of the fractional parts of \sqrt{n} is Poisson. Proc. Amer. Math. Soc. 143 (2015), no. 7, 2815–2828.

[2] https://arxiv.org/abs/1612.05495

[3] https://www.maths.bris.ac.uk/~majm/bib/nato.pdf

Answer 5

Here are some quick details about the imbalance at $\frac12,$ It shouldn't be hard to generalize. Suppose specifically that there are $1000$ equal size bins on $[0,1].$ On pass $t$ we put the fractional parts of the $2t$ irrational square roots $\lfloor\sqrt{t^2+k}\rfloor$ for $1 \le k \le 2t$ into the appropriate bins.

On each pass most bins get as many new things as on the previous pass. Exactly two bins get one more thing than before. On pass $t$ the following can be shown to happen for the bins $A=[0.499,0.5]$ and $B=[0.5,0.501]:$ For $0 \leq t \leq 124$ neither one gets anything. Let $t=125+500q+r$

• For $0 \leq r \leq 249$ $A$ gets $q+1$ new things but $B$ only gets $q.$
• For $250 \leq r \leq 499$ both $A$ and $B$ get $q+1$ new things.

Let $|A|$ and $|B|$ denote the counts in the bins after a certain pass. Then it follows that

• For $0 \leq r \leq 249,$ $|A|-|B|=250(q+1)$ and $\frac{|A|}{|B|}=\frac{q}{q-1}.$

• For $250 \leq r \leq 499,$ $|A|-|B|$ is increasing and $\frac{|A|}{|B|}$ is decreasing.