Inequalities among higher-order difference sets, or, remarks on a construction of Ruzsa

Noah Kravitz · 2026

Read Inequalities among higher-order difference sets, or, remarks on a construction of Ruzsa by Noah Kravitz (2026) 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-2606-27087.txt.

Introduction

Kravitz examines which comparisons between repeated sums and differences of an integer set must always hold. For a finite set of whole numbers, adding it to itself several times gives a sumset, and subtracting gives a difference set. Sizes of these grown sets sit at the heart of additive combinatorics, the study of addition patterns. In the 2026 classification, Kravitz extends a little-known construction of Ruzsa to settle the general higher-order question.

Four counts govern the comparison: sums and subtractions on each side of the claimed inequality. Kravitz characterises exactly which quadruples of counts make the inequality hold for every finite integer set. The answer compares only the smaller and larger count on each side. Both must not decrease from the left side to the right side. Sharp examples show why nothing weaker works, including cases where balanced huge difference sets lose to modest sumsets.

Catalog record

CREATORNoah Kravitz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27087

Browse the full library · About the Tower of Babel

Full text

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

Inequalities among higher-order difference sets, or, remarks on a construction of Ruzsa Noah Kravitz Abstract . Extending a little-known construction of Ruzsa, we characterize the quadruples ( s , t , u , v ) (s,t,u,v) of nonnegative integers such that the inequality | s ​ A − t ​ A | ≤ | u ​ A − v ​ A | |sA-tA|\leq|uA-vA| holds for all finite sets A ⊆ ℤ A\subseteq\mathbb{Z} . 1. Introduction 1.1. Higher-order difference sets For subsets A,B of an abelian group, define the sumset A+B:=\{a+b:a\in A,~b\in B\}. For a nonnegative integer r , we denote the r -fold iterated sumset of A by rA:=\underbrace{A+\cdots+A}_{r}=\{a_{1}+\cdots+a_{r}:a_{1},\ldots,a_{r}\in A\} (with the convention 0A:=\{0\} for A nonempty). Inequalities among cardinalities of iterated sumsets play a central role in additive combinatorics. One prominent example is the Plünnecke–Ruzsa inequality (see [ 13 ] ). At the same time, there is interest in constructing pathological examples to show that certain natural-looking sumset inequalities cannot hold in general. For instance, this perspective has motivated the now-abundant literature (see [ 7 ] and the references therein) around more-sums-than-differences (MSTD) sets, namely, finite sets A\subseteq\mathbb{Z} with |2A|>|A-A| . In this paper, we study the higher-order difference set inequality (1) |sA-tA|\leq|uA-vA|, where s,t,u,v are fixed nonnegative integers. One source of motivation is that ( 1 ) captures a vast generalization of the MSTD setup. It is clear that ( 1 ) always holds (in every imaginable setting) if s\leq u and t\leq v , or if s\leq v and t\leq u . Our first main result shows that this sufficient condition is in fact necessary, in the setting where A ranges over the finite subsets of the integers. Theorem 1.1 . Let s,t,u,v be nonnegative integers. Then the inequality |sA-tA|\leq|uA-vA| holds for all finite sets A\subseteq\mathbb{Z} if and only if \min(s,t)\leq\min(u,v) and \max(s,t)\leq\max(u,v) . The hard direction of the proof boils down to producing examples of finite sets A\subseteq\mathbb{Z} satisfying a priori surprising inequalities such as (2) |10A-10A|>|9A-100000A|\quad\text{and}\quad|100A|>|99A-99A|. The existence of such examples is striking because one generally expects iterated sumsets to grow with the number of summands. For comparison, the MSTD set problem concerns the relative sizes of 2A and A-A , which are both 2 -fold sumsets, whereas in each example in ( 2 ), the sumset on the left-hand side has much lower order than the sumset on the right-hand side. In the second example, the set 50A must be an MSTD set, in fact in a rather strong sense since 50A+50A=100A is not only larger than 50A-50A but also larger than 99A-99A=(50A-50A)+(49A-49A) . We remark that once the inequality ( 1 ) fails for some finite set A\subseteq\mathbb{Z} , it necessarily fails by a wide margin for other A ’s, since a single counterexample can be amplified as follows. Suppose that B\subseteq\mathbb{Z} satisfies |sB-tB|>|uB-vB| . Then set \alpha:=\log(|sB-tB|)/\log(|uB-vB|)>1 , and notice that the n -fold Cartesian product of B satisfies |sB^{n}-tB^{n}|=|sB-tB|^{n}=|uB-vB|^{\alpha n}=|uB^{n}-vB^{n}|^{\alpha}. Taking A:=B^{n} with n large (and applying a suitable Freiman homomorphism to transfer from \mathbb{Z}^{n} to \mathbb{Z} ), we see that ( 1 ) even fails polynomially with an exponent 1+\Omega_{s,t,u,v}(1) . This observation might make one wonder if ( 1 ) can fail only for “trivial reasons” due to numerical coincidences for small sets A . To the contrary, our proof of Theorem 1.1 will, without any amplification, naturally produce examples with |sA-tA|/|uA-vA| arbitrarily large. 1.2. Sums of dilates The arguments behind Theorem 1.1 naturally output a more general statement about inequalities among sums of dilates. For a nonzero integer \lambda , define the dilate \lambda\cdot A:=\{\lambda a:a\in A\} (not to be confused with the \lambda -fold sumset \lambda A ). A natural generalization of the problem resolved by Theorem 1.1 is determining the pairs of multisets of nonzero integers \{\lambda_{1},\ldots,\lambda_{\ell}\},\{\mu_{1},\ldots,\mu_{m}\} such that the inequality (3) |\lambda_{1}\cdot A+\cdots+\lambda_{\ell}\cdot A|\leq|\mu_{1}\cdot A+\cdots+\mu_{m}\cdot A| holds for all finite sets A\subseteq\mathbb{Z} . It is clear that ( 3 ) always holds if some scalar multiple of \{\mu_{1},\ldots,\mu_{m}\} contains \{\lambda_{1},\ldots,\lambda_{\ell}\} (as multisets). This is, however, not the most general way in which ( 3 ) can trivially hold: Say that \{\mu_{1},\ldots,\mu_{m}\} dominates \{\lambda_{1},\ldots,\lambda_{\ell}\} if there are a nonzero real number r and disjoint subsets S_{1},\ldots,S_{\ell}\subseteq[m] such that r\lambda_{j}=\sum_{h\in S_{j}}\mu_{h} for all j\in[\ell] . For example \{2,3,5\} dominates \{2,8\} (with r=1 ) and \{-1,-4\} (with r=-2 ). If \{\mu_{1},\ldots,\mu_{m}\} dominates \{\lambda_{1},\ldots,\lambda_{\ell}\} in this way, then \mu_{1}\cdot A+\cdots+\mu_{m}\cdot A contains a translate of \sum_{h\in S_{1}}(\mu_{h}\cdot A)+\cdots+\sum_{h\in S_{\ell}}(\mu_{h}\cdot A)\supseteq r\lambda_{1}\cdot A+\cdots+r\lambda_{\ell}\cdot A=r\cdot(\lambda_{1}\cdot A+\cdots+\lambda_{\ell}\cdot A), whence |\lambda_{1}\cdot A+\cdots+\lambda_{\ell}\cdot A|\leq|\mu_{1}\cdot A+\cdots+\mu_{m}\cdot A| . Our most general result says that this is the only way for ( 3 ) to hold. Theorem 1.2 . Let \lambda_{1},\ldots,\lambda_{\ell},\mu_{1},\ldots,\mu_{m} be nonzero integers. Then the inequality |\lambda_{1}\cdot A+\cdots+\lambda_{\ell}\cdot A|\leq|\mu_{1}\cdot A+\cdots+\mu_{m}\cdot A| holds for all finite sets A\subseteq\mathbb{Z} if and only if \{\mu_{1},\ldots,\mu_{m}\} dominates \{\lambda_{1},\ldots,\lambda_{\ell}\} . Theorem 1.1 corresponds to the special case of Theorem 1.2 where \lambda_{i},\mu_{i}\in\{-1,1\} for all i . 1.3. Relation to prior work The first hint of the possibility of achieving ( 2 ) came from an unpublished (and somewhat obscure) 2016 note of Ruzsa [ 15 ] in which he constructed sets with many more differences than multiple sums. More precisely, he showed that for every positive integer u , there is a finite set A\subseteq\mathbb{Z} with |A-A|>|uA|. This corresponds to the special case of Theorem 1.1 where s=t=1 and v=0 . Our proof of Theorem 1.1 is based on a careful analysis and generalization of Ruzsa’s quite creative construction. Our main contribution is recognizing the appropriate level of generality at which his approach works. Ruzsa says that he took inspiration from an older paper of Haight [ 3 ] . See [ 9 , 10 ] for other subsequent work based on Ruzsa’s construction. One other special case of Theorem 1.1 was previously known: The “homogeneous” instance s+t=u+v recovers a result of Iyer, Lazarev, Miller, and Zhang [ 6 ] on what they term ‘‘generalized MSTD sets’’. 1 1 1 See [ 7 ] for corrections of several mistakes in [ 6 ] . This work used fairly ad hoc methods which do not play a role in the present paper. We remark that the (s,t,u,v)=(2,0,1,1) instance of Theorem 1.1 provides a new source of MSTD sets. Our construction is more “robust” than many existing constructions in the literature, in the sense that it naturally provides amplification-free examples with 2A much larger than |A-A| . For other work on sums of dilates with a similar general flavor, see the references in [ 14 , 4 ] . 1.4. Open problems We round out this introduction with a few open problems. 1.4.1. Growth rates As we suggested above, the natural scaling for the problem of comparing |sA-tA| and |uA-vA| is captured by the quantity \alpha(s,t,u,v):=\lim_{n\to\infty}\sup_{|A|=n}\frac{\log|sA-tA|}{\log|uA-vA|}. The limit exists by Fekete’s Lemma (since sumset sizes are multiplicative with respect to the Cartesian product), and it trivially lies between 1 and s+t . In the 1970’s, Freiman and Pigaev [ 2 ] studied the values of the constants \alpha(2,0,1,1) and \alpha(1,1,2,0) , which pertain to the relative sizes of |2A| and |A-A| . See [ 16 , 5 ] for follow-up work. Here we raise the more general problem of computing or estimating

Read the complete text