1
$\begingroup$

Assume that $A$ and $B$ are subsets of $\mathbb N$, with counting functions verifying $A(x)\gg x^\alpha$ and $B(x)\gg x^\beta$, with $\alpha+\beta<1$. Let $C=A+B$ and $C(x)$ its counting function. For some particular choices of $A$ and $B$ we don't have necessarily $C(x)\gg x^{\alpha+\beta}$.

For exemple, if $A$ is the set of all possible sums of distinct powers of $3$ and $B$ is the set of all possible sums of distinct powers of $9$, one has $A(x)\gg x^{\log2/\log3}=x^{0.630\dots}$ and $B(x)\gg x^{\log2/\log9}=x^{0.315\dots}$. On the other hand, the counting fonction $C(x)$ of the set $C=A+B$ doesn't verifies $C(x)\gg x^{\alpha+\beta}$. Indeed $C(x)\ll x^{\frac12\log 6/\log3}=x^{0.815\dots} $.

My question : It is true that for almost all choices of $A$ and $B$ (in other word if $A$ and $B$ are random subsets) one should expect that $C(x)\gg x^{\alpha+\beta}$ ?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ How do you choose a random subset, with respect to which measure? For example, if we take $n$ with independent probabilities $n^{\alpha - 1}$ and $n^{\beta-1}$, respectively, then I think you can prove that the probability that $n\in C$ is proportional to $n^{\alpha + \beta-1}$, although I'm not sure if you can push it to the asymptotic number of elements in $C$. $\endgroup$
    – Aleksei Kulikov
    Commented Oct 20 at 5:23
  • $\begingroup$ Presumably the necessary ideas can be found in the works of Erdös, Freiman, Rusza,... on sumsets. Small sumsets imply a sort of linear structure. Typical results i found deal with $A+A$, not general $A+B$. A quick search does not yield results where the size, under the uniform probability on $[0,1]$ or $[0,1]^2$, of sets of $A$ or pairs $(A,B)$ seen as sets of (pairs of) reals, with some properties, is studied. I expect that your bound holds for a set of pairs at least of positive measure. One could also look at how sums of Sidon sets behave. $\endgroup$
    – plm
    Commented Oct 20 at 7:03

0

Reset to default

You must log in to answer this question.