TransWikia.com

If an infinite set $S$ of positive integers is equidistributed, is $S+S$ also equidistributed?

Mathematics Asked by Vincent Granville on November 2, 2021

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,yin S$ then $x+ynotin 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 } zrightarrowinfty$$

where $a,b,c$ are non-negative real numbers with $bleq 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 $bleq 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) = {xin 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 $0leq q,q'<n$ we have

$$frac{N_{T(n,q)}(z)} {N_{T(n,q’)}(z)}rightarrow 1 mbox{ as } zrightarrow 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 $0leq 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/(2sqrt{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.

One Answer

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

Answered by mathworker21 on November 2, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP