# Congruential equidistribution, prime numbers, and Goldbach conjecture

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 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. It is related to the concept of equidistribution modulo 1 in the following way: the sequence $$x_k$$ is equidistributed modulo 1 if and only if the sequence $$\lfloor n x_k\rfloor$$ is congruentially equidistributed modulo $$n$$ for all integers $$n\geq 2$$. The brackets represent the floor function.

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$$ is congruentially equidistributed: this is a known result. It is also true for the set of all $$\lfloor \alpha \beta^k \rfloor$$ if $$\alpha$$ is a normal number in base $$\beta$$ (here $$\alpha > 0$$, $$k=1,2,\cdots$$ and $$\beta>2$$ is an integer), and for the set of all $$\lfloor k \log k \rfloor$$ where $$k$$ is an integer $$>0$$ (this set has same density as the set of primes). The set $$S_2$$ consisting of all $$(p_{k+1}+p_{k+2})/2$$ is also congruentially equidistributed, it seems.

Question

If $$S$$ is congruentially equidistributed and 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 GC, 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.

• For what it's worth, uniform distribution of sequences of integers is discussed at some length in Kuipers and Niederreiter, Uniform Distribution of Sequences. – Gerry Myerson Jul 11 '20 at 1:01
• Chapter 5, section 1 discuss the same kind of equidistribution and call it "uniformly distributed in $Z$". See page 305 at web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf. Theorem 1.2 page 306 provides a criterion, similar to Weyl, to chek if a sequence / set of integers is congruentially equidistributed. – Vincent Granville Jul 11 '20 at 2:05
• Version 18 of this question. – Gerry Myerson Jul 14 '20 at 2:59
• @Gerry: there are little typos I catch over time like I wrote GB instead of GC, that was the last revision. Not sure if I should leave these typos or not, as they count for a large number of the revisions, yet they don't have impact on the understanding on my post. What is your suggestion? – Vincent Granville Jul 14 '20 at 4:16
• My suggestion is, get it right the first time. – Gerry Myerson Jul 14 '20 at 5:48

If $$S$$ is congruentially equidistributed and contains enough elements .... is it true that $$S+S$$ contains all the positive integers except a finite number of them?
Let $$S=\bigcup_{n=1}^\infty \{2^{2n},2^{2n}+1,\dots, 2^{2n+1}-1\}.$$ It is easy to show that $$S$$ is congruentially equidistributed and $$S+S\not\ni 2^{2n}$$ for each positive integer $$n$$.
• Looks like more conditions must be imposed on $S$ otherwise the result is not true in general. – Vincent Granville Jul 19 '20 at 20:41