Large convex sets in difference sets (Q6581862)

A set of real numbers \(A = \{ a_1 < \dots < a_n\}\) is called convex if for all \(i=2,\dots, n\) we have\N\[\Na_{i+1} - a_i > a_i - a_{i-1} \,.\N\]\NIn other words, any convex set is the image of a strictly convex function \(f\), applied to the first \(n\) positive integers. Convex sets were introduced by Erdős, and this natural object is related to many combinatorial questions, for example, to the sum-product phenomenon. It was usually believed that convex sets do not correlate with sets having some additive structure, for example, with sumsets, but Ruzsa and Zhelezov showed that there is a set \(A\), such that \(A+A\) contains a convex set of size \(\Omega(n^2)\). The paper under review develops the same line of research, and proves that there exists \(A \subseteq A-A\) containing a convex set of size \(\Omega(n^2)\). The authors also show that there always exists a subset \(M\), \(|M| \ge \sqrt{n}\) of \(A \times A\), such that \(\{ x-y ~:~ (x,y) \in M\}\) is a convex set. The latter result is sharp up to a multiplicative constant.