# Sequences of very well distributed integers

The set of integers $$\mathbb{Z}$$ has a peculiar property: it is extremely well-distributed modulo any positive integers. For an integer $$m > 1$$ and integer $$a$$, put $$\mathbb{Z}(a; m) = \{n \in \mathbb{Z}: n \equiv a \pmod{m} \}$$. Then for any interval $$I \subset \mathbb{R}$$, integer $$a$$, and positive integer $$m$$, one has the estimate

$$\displaystyle \#(I \cap \mathbb{Z}(a;m)) = \frac{|I|_{\mathbb{R}}}{m} + O(1),$$

where $$|\cdot|_{\mathbb{R}}$$ denotes the length of the interval $$I$$. Moreover, the implied constant in the big-$$O$$ is independent of $$m$$ and $$I$$: indeed, one has the sharper estimate that

$$\displaystyle |\#(I \cap \mathbb{Z}(a;m)) - |I|_\mathbb{R} m^{-1} | \leq 1.$$

In general, this kind of well-distribution cannot be expected for subsequences of integers, even when adjusted for "impossible" congruence classes. For example, even under GRH the best one can hope for for the analogous statement for primes is the estimate

$$\displaystyle \sum_{\substack{y < p < x \\ p \equiv a \pmod{q}}} \log p = \frac{x - y}{\phi(q)} + O_\epsilon \left(q^{-1/2} x^{1/2 + \epsilon}\right),$$

and while this is comparable to the integer case when $$q$$ is close in size to $$x$$ this is very bad if $$q$$ is tiny compared to $$x$$. Moreover this is a wide open problem: it is in some sense even stronger than GRH.

Let $$g$$ be a multiplicative function satisfying $$g(p^k) = p^k(1 - \kappa p^{-1})$$ for all primes $$p$$ and positive integers $$k$$ for some absolute constant $$\kappa$$. Indeed, the indentity function corresponds to the case when $$\kappa = 0$$ and the Euler $$\phi$$-function corresponds to the case $$\kappa = 1$$. For a given positive integer $$m$$ and an integer $$a$$, put $$S(a; m) = \{n \in S : n \equiv a \pmod{m}\}$$. We say that a subsequence $$S \subset \mathbb{Z}$$ is well-distributed if there is such a function $$g$$ such that for all $$m \in \mathbb{N}$$ and $$a \in \mathbb{Z}$$, we have for any interval $$I \subset \mathbb{R}$$ either $$\# (I \cap S(a; m)) = O(1)$$ or we have

$$\displaystyle \# (I \cap S(a;m)) = \frac{|I|_\mathbb{R}}{g(m)} + O_{g,\epsilon }\left(|I|_\mathbb{R}^\epsilon \right),$$

the implied constant depending at most on $$g$$ and $$\epsilon$$ but otherwise independent of $$I,m$$.

Does this property more or less characterize the integers? Are there any other natural sequences which can be shown to have this property?

• @ChristianRemling indeed! Thanks for catching the (honestly glaring) mistake. I have fixed the problem in the question. – Stanley Yao Xiao Aug 1 at 14:46
• Presumably $\#(I \cap {\mathbb Z})$ in your final display should be something else. Also, discrepancy theory results such as Roth's discrepancy theorem mathscinet.ams.org/mathscinet-getitem?mr=168545 will provide obstructions to any set that isn't close to full density or zero density from being as equidistributed as you wish here. – Terry Tao Aug 1 at 21:19
• @TerryTao yes the last display suffered the same issue as the early part of the question, which has now been fixed. Thank you for the reference – Stanley Yao Xiao Aug 2 at 0:17
• You may also wish to look at Granville and Soundararajan "An uncertainty principle for arithmetic sequences" which shows that general sifted sets must either be poorly distributed in short intervals, or poorly distributed in arithmetic progressions. This is a generalization of the Maier type results on primes. – Lucia Aug 2 at 0:39