Convexity and sumsets (Q1581869): Difference between revisions

Let \(A\) be an \(n\) element subset of real numbers, and let \(f\) be a strictly convex or concave function defined on an interval containing \(A\). Let \(S=\{(a,f(a)): a\in A\}\subseteq \mathbb R^2\). The authors prove that for every finite set \(T\) \[ |S+T|\geq c \min\{n|T|, n^{3/2}|T|^{1/2}\}, \] where \(c\) is an absolute constant, \(0<c<1\). A generalization is also proved for a repeated addition of \(k\) identical sets \(S*k:=S+S+\dots +S\) (\(k\) times). They prove: for every \(k\geq 1\) \[ |S*k+T|\geq c'n^{3(1-2^{-k}})|T|^{2^{-k}} \quad\text{if }|T|\geq n, \] and \[ |S*k+T|\geq c'n^{3-2^{-(k-2)}}|T|^{2^{-k-1}}\quad\text{if }|T|<n, \] where \(c'\) is an absolute constant \(0<c'<1\). As a corollary they improve an earlier result of \textit{P. Erdős} and \textit{E. Szemerédi} [Studies in pure mathematics, Mem. of P. Turan, 213--218 (1983; Zbl 0526.10011)] and a result of the reviewer.