11
$\begingroup$

By $S+S$, I mean $\{x+y,$ with $x,y \in S\}$. By equidistributed, I mean equidistributed in residue classes, as defined here (the definition is very intuitive, and examples of such equidistributed sets are provided on that page).

My goal here is to prove that if $S$ is equidistributed and contains enough elements (see here), then $S+S$ covers all the positive integers except a finite number of them. The first step, I think, would be to prove that $S+S$ is equidistributed. I d guess the proof is not difficult and this fact has probably been established, but I could not find a reference.

The result seems obvious if you consider "equidistribution modulo 1" instead, so I suppose it can also be derived (probably in a similar way) for "equidistribution in residue classes", as the two concepts are closely related and based on a similar Weyl criterion (a continuous version for modulo 1, a discrete version for residue classes.)

Special case

If the infinite set $S$ of positive integers is such that if $x,y\in S$ then $x+y\notin S$, it is easy to prove that $S$ equidistributed implies $S+S$ is also equidistributed. Note that $S$ is called a Sidon set or sum-free set. Let $N_S(z)$ be the number of elements of $S$ less or equal to $z$, and let's assume that

$$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 $b\leq 1$. The sets that I am interested in all have $b>\frac{1}{2}$, for instance, pseudo-primes ($a=b=c=1$) or pseudo-superprimes ($a=b=1, c=2$). Such sets satisfy this conjecture A (see here) : all but a finite number of positive integers can be written as $z=x+y$ with $x, y \in S$. That conjecture would imply that $S+S$ is de facto equidistributed, since essentially, in this case $S+S$ it is the set of all positive integers minus a finite number of them. However, that conjecture A is precisely what I would want to prove, so I can not use it as a justification to establish the much weaker result that $S+S$ is supposedly equidistributed if $b>\frac{1}{2}$ and $S$ is equidistributed. If $b\leq \frac{1}{2}$, conjecture A is not true.

Hints to prove the result and win the bounty

In case it is not true, a counter-example will do. Assuming it is correct, a sketch of a proof for a simple case is enough. Here is how it could start.

Let $T = S+S$ and

$$S(n,q) = \{x\in S, x=q \bmod{n}\}.$$

We have

$$T(n,q) = \bigcup_{p=0}^{n-1}\Big[S(n,p) + S(n,(q-p) \bmod{n} )\Big]$$ $$T=\bigcup_{q=0}^{n-1}T(n,q)$$

$T(n,q)$ is the subset of elements of $T$ that are equal to $q$ modulo $n$. The subsets $T(n,q)$ for any given $n>1$ form a partition of $T$. However the first union for $T(n,q)$ consists of potentially overlapping sets, making the problem non-trivial. Proving the result consists in proving that for any integer $n>1$ and $0\leq q,q'<n$ we have

$$\frac{N_{T(n,q)}(z)} {N_{T(n,q')}(z)}\rightarrow 1 \mbox{ as } z\rightarrow \infty.$$

Again $N_T(z)$ counts the number of elements of $T$ less than or equal to $z$. We can focus on sets $S$ such that

$$N_S(z) \sim \frac{a z^b}{(\log z)^c} $$

with $0\leq b \leq \frac{1}{2}$. I will offer the bounty even if the proof is only for the special case $b=\frac{1}{2}, c=0$ and $n=2$. For computer experiments (generating such a set $S$ that is supposed to be equidistributed), proceed as follows: the positive integer $k$ belongs to $S$ if and only if $U_k < a/(2\sqrt{z})$ where the $U_k$'s are independent uniform deviates on $[0, 1]$.

I did some experiments and here are the results, using $n=12, b=\frac{1}{2}$ and looking at all elements of $S$ and $T=S+S$ up to $10^6$:

enter image description here

Equidistribution in $S$ (modulo $n=12$ in this case) means that the "Ratio_1" tend to be identical and equal to $\frac{1}{n}$as you look at more and more elements of $S$, while equidistribution in $T$ means that the "Ratio_2" tend to be identical also converging to $\frac{1}{n}$.

I also did the same test on the set $S$ of perfect squares, which is notoriously not equidistributed. The results are below.

enter image description here

Final notes:

  • For perfect squares, $a=1, b=\frac{1}{2}, c=0$. Even though $T$, the set of sums of two perfect squares is not equidistributed, the set $T+T$ is the set of all non-negative integers, and is thus equidistributed (that set of course has $a=0, b=1, c=0$).
  • The last table suggests that the equations $x^2 + y^2 = 12z+ 3$, $x^2 + y^2 = 12z+ 7$, $x^2 + y^2 = 12z+ 11$ do not have integer solutions, while $x^2 + y^2 = 12z$, $x^2 + y^2 = 12z+6$ and $x^2 + y^2 = 12z+9$ might have only finitely many solutions.
$\endgroup$
1
  • $\begingroup$ This can give the false impression that we are making little progress towards proving Goldbach and other similar conjectures. I believe this is not the case, because the set $S$ of primes is also notoriously non-equidistributed. $\endgroup$ – Vincent Granville Jul 19 '20 at 17:06
7
+200
$\begingroup$

$S+S$ need not be equidistributed.

Let $(a_n)_n$ be a sequence of even positive integers such that $$a_{n+1} > 3+a_n+a_{n-1}+\dots+a_2+a_1$$ for each $n \ge 1$ and such that $\{\frac{a_n}{2} : n \ge 1\}$ is equidistributed. It should be clear that such a sequence exists; let me know if you want details. Let $$S = \cup_{n=1}^\infty \{a_n,a_n+1\}.$$ Then $S$ is equidistributed: it is clearly equidistributed mod $2$, and that $\{\frac{a_n}{2} : n \ge 1\}$ is equidistributed implies $S$ is equidistributed mod $n$, for any $n \ge 3$.

Now, $S+S = \cup_{1 \le n \le m < \infty} \{a_n+a_m,a_n+a_m+1,a_n+a_m+2\}$. Note the union is a disjoint one, since $a_{n+1} > 3+a_n+\dots+a_1$ for each $n \ge 1$. Therefore, $S+S$ is not equidistributed mod $2$, since $2$ out of $3$ of $a_n+a_m, a_n+a_m+1,a_n+a_m+2$ (namely, the first and the third) are even.

$\endgroup$
6
  • $\begingroup$ Thank you. I haven't yet looked in detail at your counter-example. Wondering what extra conditions on $S$ might be needed to warrant that $S+S$ is equidistributed. Also wondering if your set $S$ satisfies the same asymptotic class of distributions as discussed in my question. I will look into this. $\endgroup$ – Vincent Granville Jul 19 '20 at 18:21
  • 1
    $\begingroup$ @VincentGranville I'm not sure what extra conditions would help. My example stems from the fact (and basically is just the fact) that $\{1,2\}+\{1,2\} = \{2,3,4\}$ is not even equidistributed mod $2$. $\endgroup$ – mathworker21 Jul 19 '20 at 18:27
  • $\begingroup$ @ mathworker21: yes, I am aware that this does not work at all with finite sets. Sets need to be infinite, and your counter-example is. $\endgroup$ – Vincent Granville Jul 19 '20 at 19:35
  • $\begingroup$ @VincentGranville what?? the whole point of my answer was showing that this finite example transfers to an infinite example. $\endgroup$ – mathworker21 Jul 19 '20 at 19:51
  • $\begingroup$ @ mathworker21: yes, and I totally agree with you. What I meant is "your example is infinite and thus qualifies". Not sure why you understood it differently. $\endgroup$ – Vincent Granville Jul 19 '20 at 19:55

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.