3

2

There's a famous old problem in additive number theory which asks whether, for any $\epsilon > 0$, if $B$ is a 2-basis for the set $A =$ {$1^2,2^2,...,n^2$}, i.e.: a set for which $B+B \supseteq A$, then $|B| = \Omega(n^{1-\epsilon})$ ? Erdos and Newman showed many years ago that the answer is yes if $\epsilon > 1/3$, but not much beyond that is known, I think. So what is it about the set of squares that makes them hard to "cover by sums" ? When thinking about this, I wondered if convexity might be an important property. A finite set $A =$ {$a_1 < a_2 < \cdots < a_n$} is said to be (strictly) convex if the consecutive differences $a_{i+1}-a_i$ are (strictly) increasing. My question, in its simplest form, is as follows: Let $B$ be a set of $n$ integers and let $A$ be a strictly convex subset of $B+B$. Must $|A| = o(n^2)$ ?

flag
I would suspect some variant of the arguments of Elekes, Nathanson, and Ruzsa ams.org/mathscinet-getitem?mr=1772612 would answer your question affirmatively (although the results in that paper do not quite directly apply to your setting). – Terry Tao Sep 11 at 5:06
@Terry: Thanks for the link. Actually we (grad student + me) were already aware of that paper, and several like it which have appeared since. We had a look again and while there are certainly indications that the methods there are relevant to my formulation (for example, Lemma 2.1 in arxiv.org/pdf/1108.4382v1.pdf), it's still not clear to us how to deduce an answer. So I was just wondering if you had something very specific in mind with your comment, or if it was just a general suggestion ? – Peter Hegarty Sep 27 at 15:18
As I said, the results do not directly apply - they assume convexity on the summand sets, rather than the sumsets - but the proof techniques may possibly be adapted to your setting. (One could of course move B on to the other side, and use the fact that if $A \subset B+B$, then $A-B$ has high overlap with $B$ counting multiplicity, though probably the existing results in the literature won't be able to say something nontrivial about this situation.) One might also contact some of the authors of these recent papers to see if they have any suggestions. – Terry Tao Oct 2 at 16:50

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.