There's a famous old problem in additive number theory which asks whether, for any $\epsilon > 0$, if $B$ is a 2basis 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)$ ?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
