Skip to main content
12 of 18
added 16 characters in body

Congruential equidistribution in infinite sets or sequences of positive integers

Let $S$ be an infinite set of positive integers, $N_S(z)$ be the number of elements of $S$ less than or equal to $z$, and let

$$D_S(z, n, p)= \sum_{k\in S,k\leq z}\chi(k\equiv p\bmod{n}).$$

Here $\chi$ is the indicator function, and $z, p, n$ are positive integers, with $p<n$ and $n>1$. If

$$\lim_{z\rightarrow\infty} \frac{D_S(z,n,p)}{N_S(z)} = \frac{1}{n}$$

for all $n>1$, regardless of $p$, then the set $S$ is said to be congruentially equidistributed, or in other words, free of congruential restrictions.The exact same concept, referred to as "uniformly distributed in $Z$", is discussed in chapter 5 in the book Uniform Distribution of Sequences by Kuipers and Niederreiter (1974), see here.

Examples

Here $p_k$ denotes the $k$-th prime, with $p_1=2$. The set $S_1$ of all $k+p_k$ seems to be congruentially equidistributed. But the set of all primes is not. The set of squares and the set of cubes are not. If $\alpha$ is irrational, then the set consisting of all $\lfloor \alpha p_k \rfloor$ where the brackets represent the floor function, is congruentially equidistributed: this is a known result. The set $S_2$ consisting of all $(p_{k+1}+p_{k+2})/2$ is also congruentially equidistributed, it seems.

Question

If $S$ contains enough elements, say

$$N_S(z) \sim \frac{a z^b}{(\log z)^c} \mbox{ as } z\rightarrow\infty$$

where $a, b, c$ are non-negative real numbers with $\frac{1}{2}< b \leq 1$, is it true that $S+S=\{x+y,$ with $x, y \in S\}$ contains all the positive integers except a finite number of them?

This statement would be true if $S$ was a random set having the same distribution of elements. More precisely, in that case, as a result of the Borel-Cantelli lemma, $S+S$ almost surely contains all the positive integers but a finite number of them. See the last paragraph in my answer to my previous MO question here, for a justification.

Connection to Goldbach conjecture

If $a=1, b=1, c=1$, we are dealing with numbers that are distributed just like prime numbers, so this is connected to the Goldbach conjecture (GC). The set $S_1$ (see example above) seems congruentially equidistributed, thus proving that every large enough integer is the sum of two elements of $S_1$, might be much less difficult than proving GC. The set of primes is NOT congruentially equidistributed, presumably making GC harder to prove. Note that $S_1$ is more sparse than the set of primes. Both $S_1$ and $S_2$ (see example) also have $a=1,b=1, c=1$. So an alternative to GC, easier to prove, could be:

All large enough integer $z$ can be written as $z=x+y$ with $x,y\in S_2$.

Even if you replace primes by super-primes in $S_2$, you would still (I guess) keep the congruential equidistribution, and thus the conjecture would still presumably be easier to prove than GB, even though super-primes are far rarer than primes. Note that for super-primes, $a=1, b = 1, c = 2$.

I also posted a shorter version of this question on MSE, here.