An inverse and a stability result for Ruzsa’s inequality on triple sumsets

Swaroop Hegde · 2025

Read An inverse and a stability result for Ruzsa’s inequality on triple sumsets by Swaroop Hegde (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-2510-20073.txt.

Introduction

Swaroop Hegde proves an inverse and stability result for Ruzsa inequality on triple sumsets in additive combinatorics. The inequality bounds the size of a triple sumset by a power of the size of the double sumset for any finite set in a commutative group. Ruzsa own examples show the bound is nearly sharp, which raises the question of what near-extremal sets look like.

Hegde shows that if a set comes close to the bound, within a factor set by a parameter, then it must resemble the sets in Ruzsa construction. New families of examples suggest that description is likely best possible in qualitative terms. The method extends to higher sumsets, with an almost exact stability version included.

Catalog record

CREATORSwaroop Hegde
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20073

Browse the full library · About the Tower of Babel

Full text

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

An inverse and a stability result for Ruzsa’s inequality on triple sumsets Swaroop Hegde Abstract . Ruzsa’s inequality states that | A + A + A | ≤ | A + A | 3 / 2 |A+A+A|\leq|A+A|^{3/2} for any finite set A A in a commutative group. Ruzsa has constructed examples showing that this inequality is sharp asymptotically, up to a constant factor. We prove an inverse result which says that if | A + A + A | ≥ 1 M ​ | A + A | 3 / 2 |A+A+A|\geq\frac{1}{M}|A+A|^{3/2} for some parameter M , M, then the set A A resembles the sets in Ruzsa’s construction. We then construct more families of examples which suggest that our inverse result is likely best possible qualitatively. The method extends to give an inverse result for a higher sumset analogue of Ruzsa’s inequality, namely | ( h + 1 ) ​ A | ≤ | h ​ A | h + 1 h |(h+1)A|\leq|hA|^{\frac{h+1}{h}} for any h ≥ 2 . h\geq 2. We also provide a “99%-stability” version of Ruzsa’s inequality, which describes near optimal structures when M M is very close to 1 . 1. † † Department of Mathematics, University of Georgia, Athens, Georgia 30602, United States. Email: [email protected] . This material is based upon work supported by the National Science Foundation under Grant No. 2054214. 1. Introduction If A is a subset of a commutative group then its sumset is defined as follows: A+A=\{a+b:a,b\in A\}. If A is finite and non-empty, then size of A+A can be trivially bounded by (1) |A|\leq|A+A|\leq\binom{|A|+1}{2}. The lower bound in Equation ( 1 ) is attained when for instance A is a coset of a subgroup and the upper bound is attained when all the sums of A are distinct, such as in a geometric progression inside \mathbb{Z} or when A is the set of generators of a free group. The quantity K=\frac{|A+A|}{|A|} called the doubling ratio is generally used to measure how big |A+A| is compared to |A|. The general philosopy in additive combinatorics is that when the doubling ratio is small, then the set A has high additive structure and resembles a coset of a subgroup. This is, for example, the essence of Freiman’s theorem [ 8 ] and there have been recent breakthroughs in the quantitative aspects of this theorem [ 9 ] . Such results which give information about the additve structure of a set just by knowing something about the size of its sumset fall under the bigger umbrella of inverse theorems in combinatorics. Classical questions in additive combinatorics also concern cardinality estimates of iterated sumsets of a set A given the size of |A+A|. (The iterated sumset hA for h\geq 2 consists of all the h -fold sums of A .) For instance, Plünnecke’s inequality [ 20 , 21 ] , a standard tool in additive combinatorics, says that if |A+A|=K|A| then for h\geq 3 (2) |hA|\leq K^{h}|A|. So if K is not large, then the sizes of iterated sumsets do not change by very much, like in cosets. Note however, that if K\geq|A|^{1-\frac{1}{h}} then Plünnecke’s inequality is worse than the trivial bound |hA|\leq|A|^{h} . Ruzsa investigated this and first proved a bound in the case h=3 which complements Plünnecke’s inequality when K is large (see Theorem 1.9.1 of [ 22 ] ), namely (3) |A+A+A|\leq|A+A|^{3/2}=K^{3/2}|A|^{3/2}. We will be refering to Equation ( 3 ) as Ruzsa’s inequality in this paper. Plünnecke’s inequality gives the better estimate when K\leq|A|^{1/3} and Ruzsa’s inequality is better when |A|^{1/3}\leq K\leq|A|. Ruzsa’s inequality is asymptotically sharp up to a constant factor as is shown by the following example. Example 1.1 (Additively dissociated sets) . Let us call a subset A of a commutative group h -dissociated for some integer h\geq 2 if all the h -fold sums of A are distinct. (Note that if a set is h -dissociated, then it is also (h-1) -dissociated.) For example, A\subset\mathbb{Z} given by the geometric progression A=\{1,3,3^{2},\ldots,3^{n-1}\} is 3 -dissociated. We have |A|=n with |A+A|=\binom{n+1}{2}\qquad\text{and}\qquad|A+A+A|=\binom{n+2}{3}. Thus we have |A+A+A|=\Omega(|A+A|^{3/2}) and A serves as an asymptotically sharp example for Ruzsa’s inequality. However, in this case the doubling ratio is K=\frac{|A+A|}{|A|}=\frac{|A|+1}{2}, which is the largest possible, whereas Ruzsa’s inequality is better than Plünnecke’s inequality for a wider range, namely |A|^{1/3}\leq K\leq|A|. Ruzsa has constructed the following family of examples (Theorem 1.9.5 of [ 22 ] ) showing that Ruzsa’s inequality is sharp asymptotically, upto a constant factor, for any possible doubling in the range |A|^{1/3}\leq K\leq|A|. Example 1.2 (Ruzsa’s construction) . Let m\geq 1 be an integer and K\in\mathbb{R} be such that m\leq K\leq m^{3}. We construct A\subset\mathbb{Z}^{3} as the union of two sets A=X\cup Y, where X=\{(x,y,z)\in\mathbb{Z}^{3}\ |\ 0\leq x,y,z<m\}\ \text{and} Y=\{(x,0,0),(0,x,0),(0,0,x)\in\mathbb{Z}^{3}\ |\ 0\leq x<\sqrt{Km^{3}}\}. Visually, A consists of a cube in \mathbb{Z}^{3} cornered at the origin with sides of length m, together with three splines, each of length \sqrt{Km^{3}}, attached to it along the coordinate axes. x y z A x y z \sqrt{Km^{3}} Y m X Then it can be checked that |A|=\Theta(m^{3}) , |A+A|=\Theta(K|A|) and |A+A+A|=\Theta(K^{3/2}|A|^{3/2}). (We omit the details here but similar calculations can be found in Examples 5.2 , 5.1 and 6.1 .) The main result of this paper is an inverse result showing that if |A+A+A|\geq\frac{1}{M}K^{3/2}|A|^{3/2}, for some parameter M, then A is similar to the sets in Ruzsa’s construction. More specifically, we show the existence of a subset Y\subset A of size |Y|=\Theta_{M}(\sqrt{K|A|}) such that |Y+Y+Y|=\Theta_{M}(|Y|^{3}) (with the dependence on M being polynomial in M ), which is analogous to the splines in Ruzsa’s construction. Theorem 1.3 (Inverse result) . Let A be a finite non-empty subset of a commutative group with |A+A|\leq K|A|. Suppose |A+A+A|\geq\frac{1}{M}K^{3/2}|A|^{3/2}, where 1\leq M\leq\frac{1}{2}\sqrt{\frac{|A|}{K}}. Then there exists Y\subset A such that (1) \displaystyle\frac{\sqrt{K|A|}}{(2M)^{1/3}}\leq|Y|<2M{\sqrt{K|A|}} and (2) \displaystyle|Y+Y+Y|\geq\frac{|Y|^{3}}{(2M)^{4}}. Furthermore, in Examples 5.2 and 5.1 of this paper we modify Ruzsa’s construction to obtain more extremal examples to show that one could not hope to say much structurally about the set A\setminus Y which is analogous to the cube in Example 1.2 . The key feature that these examples have in common is “having splines”, making our inverse result qualitatively best possible. The conclusions of Theorem 1.3 are nontrivial even when M is |A|^{\varepsilon} for a small \varepsilon>0. In Section 2 , we will survey various approaches that have appeared in the literature to prove Ruzsa’s inequality and provide new perspectives. In Theorem 2.3 , we will state Ruzsa’s inequality in a slightly sharper form (with respect to the multiplicative constant), while characterizing the extremal cases exactly to be 3 -dissociated sets described in Example 1.1 . This is a known result by the work of Eliahou and Mazumdar [ 5 ] , but we provide a new and short proof here. Using these ideas we obtain a stability version of Ruzsa’s inequality. Theorem 1.4 (Stability for Theorem 2.3 ) . Let \delta<1/1152 and A be a large enough 1 1 1 This will be made clear later in the proof in Section 3 . subset of a commutative group. Suppose |A+A|=\binom{x+1}{2} for some real number x\geq 1. If |A+A+A|\geq(1-\delta)\binom{x+2}{3}, then there exists a subset Y\subset A with \displaystyle(1-6\delta^{1/2})x<|Y|<(1+9\delta^{1/2})(x+1) such that |Y+Y+Y|\geq(1-50\delta^{1/2})\binom{|Y|+2}{3}. The above

Read the complete text