1
$\begingroup$

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. 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.

$\endgroup$
  • 2
    $\begingroup$ For what it's worth, uniform distribution of sequences of integers is discussed at some length in Kuipers and Niederreiter, Uniform Distribution of Sequences. $\endgroup$ – Gerry Myerson Jul 11 at 1:01
  • $\begingroup$ 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. $\endgroup$ – Vincent Granville Jul 11 at 2:05
  • 1
    $\begingroup$ Version 18 of this question. $\endgroup$ – Gerry Myerson Jul 14 at 2:59
  • $\begingroup$ @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? $\endgroup$ – Vincent Granville Jul 14 at 4:16
  • 1
    $\begingroup$ My suggestion is, get it right the first time. $\endgroup$ – Gerry Myerson Jul 14 at 5:48
4
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Looks like more conditions must be imposed on $S$ otherwise the result is not true in general. $\endgroup$ – Vincent Granville Jul 19 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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