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$:
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.
Final notes:
$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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP