Convex subsets of sumsets - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:02:19Z http://mathoverflow.net/feeds/question/106817 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106817/convex-subsets-of-sumsets Convex subsets of sumsets Peter Hegarty 2012-09-10T14:21:10Z 2012-09-10T14:21:10Z <p>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 &lt; a_2 &lt; \cdots &lt; 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)$ ? </p>