Additive structure in convex sets

Thomas F. Bloom, Jakob Führer, Oliver Roche-Newton · 2025

Read Additive structure in convex sets by Thomas F. Bloom, Jakob Führer, Oliver Roche-Newton (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01568.txt.

Introduction

Thomas F. Bloom, Jakob Fuhrer, and Oliver Roche-Newton measure how much additive structure a convex set can hold. Convex sets curve outward with no dents, which might seem to limit patterns such as arithmetic progressions inside them. Their main result builds a convex set packed with three-term arithmetic progressions, at a count growing as the set size to the power three halves.

Catalog record

CREATORThomas F. Bloom, Jakob Führer, Oliver Roche-Newton
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-01568

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Additive structure in convex sets Thomas F. Bloom, Jakob Führer, Oliver Roche-Newton Abstract . This paper considers some different measures for how additively structured a convex set can be. The main result gives a construction of a convex set A A containing Ω ⁡ ( | A | 3 / 2 ) \Omega(|A|^{3/2}) three-term arithmetic progressions. 1. Introduction A convex set is a finite set A\subset\mathbb{R} such that, if the elements are ordered A=\{a_{1}<\cdots<a_{n}\} , the consecutive differences d_{i}=a_{i+1}-a_{i}\quad\textrm{ for }\quad 1\leq i\leq n-1 form a strictly increasing sequence. This is equivalent to the statement that A=\{f(x):1\leq x\leq n\} for a strictly convex and increasing function f:\mathbb{R}\to\mathbb{R} . In a similar spirit to the sum-product problem, one expects that a strictly convex function disturbs (or even destroys) the additive structure of a set or, to put this another way, that a convex set cannot be additively structured. This vague principle can be quantified in various ways. It was conjectured by Erdős that the bound 1 1 1 Here and throughout this paper, the notation X\gg Y , Y\ll X, X=\Omega(Y) , and Y=O(X) are all equivalent and mean that X\geq cY for some absolute constant c>0 . The notation X\asymp Y (or equivalently X=\Theta(Y) ) indicates that both X\ll Y and X\gg Y hold. |A+A|\gg|A|^{2-o(1)} holds for any convex set A , with a similar conjecture for the difference set A-A . This problem remains open, with the current best-known bounds |A+A|\gg|A|^{30/19-o(1)},\,\,\,\,\,|A-A|\gg|A|^{6681/4175-o(1)} due to Rudnev and Stevens [ 11 ] and Bloom [ 2 ] respectively. Note that the latter bound gives a small improvement on the previous record with exponent 8/5-o(1) , due to Schoen and Shkredov [ 14 ] . Another useful way to measure of the additive structure of a set is the additive energy, defined by E(A):=|\{(a,b,c,d)\in A^{4}:a+b=c+d\}|. Since a convex set should be additively unstructured, one expects E(A) to be small for any convex A . The trivial solutions a+b=a+b already give E(A)\geq|A|^{2} , and the example of the first n squares shows that the energy can be slightly larger than quadratic by a logarithmic factor. The best-known bound (1) E(A)\ll|A|^{\frac{123}{50}+o(1)} is due to Bloom [ 2 ] , slightly improving an earlier bound of Shkredov [ 15 ] . There are no known constructions of large convex sets A such that E(A)\geq|A|^{2+c} for a strictly positive c . With this in mind, the following rather strong conjecture is not entirely implausible, although we do approach it with some suspicion. Conjecture 1 . If A\subset\mathbb{R} is convex then E(A)\leq\left\lvert A\right\rvert^{2+o(1)}. One can also consider solutions to other additive equations, and a close relative of the energy E(A) is the quantity T_{3}(A) , which counts the number of three-term arithmetic progressions inside A . That is, define T_{3}(A):=|\{(a,b,c)\in A^{3}:2a=b+c\}|. Trivially we have \left\lvert A\right\rvert\leq T_{3}(A)\leq\left\lvert A\right\rvert^{2}. The lower bound comes from considering the trivial arithmetic progressions whereby a=b=c , while the upper bound follows from the observation that fixing a and b determines c . Since very structured sets (for example, arithmetic progressions) have T_{3}(A)\gg\left\lvert A\right\rvert^{2} , the count T_{3}(A) can be viewed as an alternative measure of additive structure. To this end, it is natural to ask how it behaves for convex sets. Of course, one can take convex sets which do not contain any non-trivial three-term arithmetic progressions (for example, A=\{1,2,4,\ldots,2^{n}\} ), and hence T_{3}(A)=\left\lvert A\right\rvert is certainly possible. The interesting question is how large T_{3}(A) can possibly be. In this paper, perhaps surprisingly considering the above heuristic that convex sets lack additive structure, we construct a convex set containing many 3 -term arithmetic progressions. Theorem 2 . There are arbitrarily large convex sets A\subset\mathbb{R} which contain \gg\left\lvert A\right\rvert^{3/2} many non-trivial 3 -term arithmetic progressions. Moreover, our construction generalises to give convex sets which have relatively many copies of various additive configurations, including longer progressions. See Theorem 6 for a more general form of the statement. The construction appeals to an idea from a paper of Ruzsa and Zhelezov [ 12 ] in which they proved the existence of a set A with the property that A+A contains a large convex set (see also Bhowmick, Lund, and Roche-Newton [ 1 ] ). For upper bounds, we observe that Conjecture 1 would imply a nearly matching upper bound T_{3}(A)\ll|A|^{3/2+o(1)} . Indeed, since E(A)=\sum_{x}r_{A+A}(x)^{2} , the Cauchy-Schwarz inequality yields T_{3}(A)=\sum_{a\in A}r_{A+A}(2a)\leq\left\lvert A\right\rvert^{1/2}E(A)^{1/2}\leq\left\lvert A\right\rvert^{3/2+o(1)}. To put this observation in its contrapositive form, any construction with T_{3}(A)\geq|A|^{3/2} would also give a construction refuting Conjecture 1 . As an unconditional upper bound, we have the following result. Theorem 3 . If A\subset\mathbb{R} is convex then T_{3}(A)\ll|A|^{5/3}. Theorem 3 is an immediate corollary of an upper bound for the number of representations of an element of A+A . Let r_{A+A}(x) denote the number of such representations, that is, r_{A+A}(x)=|\{(a,b)\in A\times A:a+b=x\}|. Schoen [ 13 ] proved that the bound r_{A+A}(x)\ll|A|^{2/3} holds for any convex set A and any x\in\mathbb{R} . Theorem 3 follows since T_{3}(A)=\sum_{a\in A}r_{A+A}(2a). In this paper we give an alternative proof of Schoen’s upper bound, and also give a construction of a convex set such that r_{A+A}(x)\gg|A|^{2/3}, thus showing that Schoen’s upper bound for additive representations is optimal. We also consider the problem of finding a large Sidon set in a convex set. A set is Sidon if the only solutions to the energy equation a+b=c+d are the trivial ones with \{a,b\}=\{c,d\} . Another way to measure the additive structure of the set is to determine the size of the largest Sidon set contained within it. Given an arbitrary finite set A\subset\mathbb{R} , let S(A) denote this quantity, that is, S(A)=\max\{|B|:B\text{ is Sidon and }B\subset A\}. It follows from a more general result of Komlós, Sulyok, and Szemerédi [ 7 ] that S(A)\gg|A|^{1/2} for any finite A\subset\mathbb{R} , and one can see that this is optimal by considering the very additively structured set A=\{1,\dots,n\} . (There are several ways to construct Sidon sets of size \gg n^{1/2} in \{1,\ldots,n\} . The first such construction is due to Singer [ 17 ] .) Intuitively, we expect that less additively structured sets should always contain larger Sidon sets. With this in mind, we consider the following problem; given a convex set A\subset\mathbb{R} , how small can S(A) be? The next two statements give some partial answers to this question. Theorem 4 . If A\subset\mathbb{R} is convex then S(A)\gg|A|^{\frac{1}{2}+\frac{1}{75}-o(1)}. From the other side, we obtain the following result. Theorem 5 . There exist arbitrarily large convex sets A\subset\mathbb{R} such that S(A)\ll|A|^{3/4}. This question has a similar flavour to a Sidon set analogue of the sum-product problem posed by Klurman and Pohoata [ 8 ] . They conjectured that any set A\subset\mathbb{R} must contain either a large additive Sidon set or a large multiplicative Sidon set (i.e. a large set containing only trivial solutions to the equation ab=cd ). The proof of Theorem 5 is a fairly straightforward consequence of the result of Ruzsa and Zhelezov [ 12 ] , and uses similar ideas Roche-Newton and Warren [ 9 ] used to refute a strong form of the Klurman-Pohoata Conjecture. We refer to Shkredov [ 16 ] for more details on this Sidon sum-product problem. We conclude the introduction by summarising

Read the complete text