Compression and complexity for sumset sizes in additive number theory

Melvyn B. Nathanson

arxiv: 2505.20998 · v2 · submitted 2025-05-27 · 🧮 math.NT · math.CO

Compression and complexity for sumset sizes in additive number theory

Melvyn B. Nathanson This is my paper

Pith reviewed 2026-05-19 13:30 UTC · model grok-4.3

classification 🧮 math.NT math.CO

keywords sumsetsadditive number theorysumset cardinalitycompression algorithmdiameterh-fold sumslattice points

0 comments

The pith

For h-fold sumsets with large diameter, there is a compression algorithm to construct sets with the same sumset size but small diameter.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the sets of all possible sizes of h-fold sumsets of k-element sets in the integers and in integer lattices. It investigates the geometric and computational complexity of these collections of sizes. Central to the work is a compression algorithm that, for any set with a large-diameter h-fold sumset, produces a new set with the same sumset cardinality but much smaller diameter. A sympathetic reader would care because this implies that the possible sizes of sumsets can be understood by examining only sets confined to small intervals or boxes, greatly simplifying the analysis.

Core claim

For sumsets hA with large diameter, there is a compression algorithm to construct sets A' with |hA'| = |hA| and small diameter.

What carries the argument

The compression algorithm for reducing the diameter of a set while preserving the size of its h-fold sumset.

If this is right

The possible sizes R_Z(h,k) can be studied using only small-diameter sets.
Geometric complexity is reduced since all large sumset sizes arise from compressed sets.
Computational enumeration of sumset sizes becomes feasible by bounding the diameter.
The same holds in higher dimensions for Z^n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This compression might enable complete lists of possible sumset sizes for fixed small h and k.
It could connect to algorithms for computing minimal sumset sizes or inverse problems in additive combinatorics.
Testing on explicit examples like arithmetic progressions would verify the diameter reduction in practice.

Load-bearing premise

The assumption that such a compression procedure exists and works for arbitrary finite sets A in Z or Z^n with large-diameter hA, without restrictions on A, h or k.

What would settle it

Discovering a finite set A of integers such that hA has large diameter yet no set with the same |hA| has small diameter would disprove the claim.

read the original abstract

The study of sums of finite sets of integers has mostly concentrated on sets with small sumsets (Freiman's theorem and related work) and on sets with large sumsets (Sidon sets and $B_h$-sets). This paper considers the sets ${\mathcal R}_{\mathbf Z}(h,k)$ and ${\mathcal R}_{{\mathbf Z}^n}(h,k)$ of \emph{all} sizes of $h$-fold sums of sets of $k$ integers or of $k$ lattice points, and the geometric and computational complexity of the sets ${\mathcal R}_{\mathbf Z}(h,k)$ and ${\mathcal R}_{{\mathbf Z}^n}(h,k)$. For sumsets $hA$ with large diameter, there is a compression algorithm to construct sets $A'$ with $|hA'| = |hA|$ and small diameter.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Nathanson defines new families R_Z(h,k) and R_{Z^n}(h,k) to collect attainable sizes of h-fold sumsets and claims a diameter-compression algorithm that keeps |hA| fixed while shrinking the diameter.

read the letter

The core contribution is the explicit introduction of the sets R_Z(h,k) and R_{Z^n}(h,k), which gather every possible cardinality that an h-fold sumset can take when the underlying set has exactly k elements in Z or in Z^n. This gives a single object that organizes questions about both small and large sumsets instead of treating them as separate regimes. The paper also asserts that any finite A whose hA has large diameter can be replaced by an A' with the same |hA'| but small diameter via a compression procedure. If that procedure is constructive and terminates, it supplies a reduction that could turn diameter-dependent problems into bounded-diameter ones for computational or theoretical work. That is the concrete algorithmic angle the abstract highlights. The organizing device itself is new in the literature the paper cites; it is not just another Freiman-type theorem or Sidon-set construction. The compression claim, if it holds without hidden restrictions on A or on h and k, would be a useful tool for anyone who needs to enumerate or bound sumset sizes in practice. The main soft spot is that the abstract gives no proof sketch, no explicit construction of the algorithm, and no verification that the output A' always satisfies |hA'| = |hA| for arbitrary input. Without those details it is impossible to check termination, correctness on edge cases, or whether the method applies uniformly in Z^n for n greater than 1. The full manuscript presumably contains the missing steps, but on the supplied evidence the central existence statement remains unverified. This paper is aimed at researchers already working inside additive combinatorics who want a new bookkeeping tool or a reduction for computational experiments. A reader who cares about the complexity of sumset-size problems or who needs to reduce unbounded-diameter cases will find something usable here. It is coherent enough on its own terms to merit a serious referee rather than a desk rejection; the ideas are specific and checkable once the algorithm is written out.

Referee Report

2 major / 1 minor

Summary. The paper defines the sets R_Z(h,k) and R_{Z^n}(h,k) as the collections of all possible cardinalities of h-fold sumsets hA for finite sets A of size k in Z or Z^n. It examines the geometric and computational complexity of these R sets. The central claim is that whenever hA has large diameter, there exists a compression algorithm producing A' with |hA'| = |hA| but with small diameter.

Significance. If rigorously established, the compression result would reduce the study of possible sumset sizes to the bounded-diameter case, potentially simplifying both the characterization of R_Z(h,k) and R_{Z^n}(h,k) and the associated computational problems. The emphasis on complexity aspects could also connect additive combinatorics with algorithmic questions.

major comments (2)

[Abstract] Abstract (final paragraph): the existence of a compression algorithm that preserves |hA| while reducing diameter is asserted for arbitrary finite A subset Z or Z^n and without restrictions on h or k, but no explicit construction, termination argument, or proof that cardinality is preserved is supplied. This existence statement is load-bearing for the paper's main contribution.
[Main results section (assumed near the statement of the compression claim)] The manuscript does not indicate how the algorithm interacts with the definition of the sets R_Z(h,k) and R_{Z^n}(h,k); if the compression is used to compute or enumerate elements of R, a formal reduction showing that every possible size is realized by some small-diameter representative must be stated and verified.

minor comments (1)

[Abstract] The notation R_Z(h,k) and R_{Z^n}(h,k) is introduced without an immediate small example (e.g., for h=2, k=3) that would illustrate which integers appear in the set.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for highlighting the need for greater clarity on the compression algorithm and its relation to the sets R. We address the major comments point by point below and will revise the manuscript to strengthen these aspects.

read point-by-point responses

Referee: [Abstract] Abstract (final paragraph): the existence of a compression algorithm that preserves |hA| while reducing diameter is asserted for arbitrary finite A subset Z or Z^n and without restrictions on h or k, but no explicit construction, termination argument, or proof that cardinality is preserved is supplied. This existence statement is load-bearing for the paper's main contribution.

Authors: We acknowledge that the abstract states the existence of the compression algorithm without including an explicit construction, termination argument, or full proof of cardinality preservation in the visible text. The manuscript body sketches the algorithm, but we agree these details are insufficiently developed. In the revision we will supply an explicit description of the compression procedure, prove that it terminates, and verify that |hA'| equals |hA| for the output set A'. revision: yes
Referee: [Main results section (assumed near the statement of the compression claim)] The manuscript does not indicate how the algorithm interacts with the definition of the sets R_Z(h,k) and R_{Z^n}(h,k); if the compression is used to compute or enumerate elements of R, a formal reduction showing that every possible size is realized by some small-diameter representative must be stated and verified.

Authors: The compression result is intended to imply that the possible values in R_Z(h,k) and R_{Z^n}(h,k) can be realized by sets of bounded diameter. We will add an explicit proposition in the main results section stating that for every finite A there exists A' with diameter bounded by a function of h and k such that |hA'| = |hA|, thereby establishing the formal reduction. This will be accompanied by a short verification that the image of the compression map covers all attainable cardinalities. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper asserts the existence of a compression algorithm that produces A' with |hA'| = |hA| and small diameter whenever hA has large diameter. This is an existence claim about an algorithmic construction for arbitrary finite sets A in Z or Z^n. No equations, fitted parameters, self-citations, or derivation steps are visible that reduce the central claim to its own inputs by construction. The statement supplies no technical detail that collapses into a renaming, fit, or self-referential definition. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard axioms of the integers and lattice points together with the usual definition of sumsets; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)

standard math The integers Z and the lattice Z^n are equipped with the standard addition operation and the usual notion of diameter (max minus min).
Invoked implicitly when the abstract speaks of 'large diameter' and 'small diameter'.

pith-pipeline@v0.9.0 · 5669 in / 1334 out tokens · 31437 ms · 2026-05-19T13:30:53.726208+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

For sumsets hA with large diameter, there is a compression algorithm to construct sets A' with |hA'| = |hA| and small diameter.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · 1 internal anchor

[1]

Erd˝ os and E

P. Erd˝ os and E. Szemer´ edi, On sums and products of integers, in: Studies in Pure Mathe- matics, Birkh¨ auser, Basel-Boston, 1983, pp. 213–218

work page 1983
[2]

J. Fox, N. Kravitz, and S. Zhang, Finer control on relative sizes of iterated susmets, preprint, 2025

work page 2025
[3]

G. A. Freiman,Foundations of a Structural Theory of Set Addition, American Mathematical Society, Providence, R.I., 1973

work page 1973
[4]

G. A. Freiman, What is the structure ofKifK+Kis small?, in:Number Theory, New York 1984–85, Springer-Verlag, New York, 1987, pages 109–134

work page 1984
[5]

Hegyv´ ari, On representation problems in the additive number theory, Acta Math

N. Hegyv´ ari, On representation problems in the additive number theory, Acta Math. Hungar. 72 (1996), 35–44

work page 1996
[6]

Kravitz, Relative sizes of iterated sumsets, J

N. Kravitz, Relative sizes of iterated sumsets, J. Number Theory 272 (2025), 113–128,

work page 2025
[7]

M. B. Nathanson,Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer, New York, 1996

work page 1996
[9]

M. B. Nathanson, Problems in additive number theory, VI: Sizes of sumsets of finite sets, Acta Math. Hungarica, to appear; arXiv:2411.02365

work page arXiv
[10]

M. B. Nathanson, Explicit sumset sizes in additive number theory, arXiv: 2505.05329, 2025

work page internal anchor Pith review Pith/arXiv arXiv 2025
[11]

O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron

K. O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin. DS11 (2004), 39 pages

work page 2004
[12]

P´ eringuey and A

P. P´ eringuey and A. de Roton, A note on iterated sumsets races, preprint, 2025

work page 2025
[13]

Schinina, On the sums of sets of sizek, preprint, 2025

V. Schinina, On the sums of sets of sizek, preprint, 2025. COMPRESSION AND COMPLEXITY FOR SUMSET SIZES 17 Department of Mathematics, Lehman College (CUNY), Bronx, NY 10468 Email address:melvyn.nathanson@lehman.cuny.edu

work page 2025

[1] [1]

Erd˝ os and E

P. Erd˝ os and E. Szemer´ edi, On sums and products of integers, in: Studies in Pure Mathe- matics, Birkh¨ auser, Basel-Boston, 1983, pp. 213–218

work page 1983

[2] [2]

J. Fox, N. Kravitz, and S. Zhang, Finer control on relative sizes of iterated susmets, preprint, 2025

work page 2025

[3] [3]

G. A. Freiman,Foundations of a Structural Theory of Set Addition, American Mathematical Society, Providence, R.I., 1973

work page 1973

[4] [4]

G. A. Freiman, What is the structure ofKifK+Kis small?, in:Number Theory, New York 1984–85, Springer-Verlag, New York, 1987, pages 109–134

work page 1984

[5] [5]

Hegyv´ ari, On representation problems in the additive number theory, Acta Math

N. Hegyv´ ari, On representation problems in the additive number theory, Acta Math. Hungar. 72 (1996), 35–44

work page 1996

[6] [6]

Kravitz, Relative sizes of iterated sumsets, J

N. Kravitz, Relative sizes of iterated sumsets, J. Number Theory 272 (2025), 113–128,

work page 2025

[7] [7]

M. B. Nathanson,Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer, New York, 1996

work page 1996

[8] [9]

M. B. Nathanson, Problems in additive number theory, VI: Sizes of sumsets of finite sets, Acta Math. Hungarica, to appear; arXiv:2411.02365

work page arXiv

[9] [10]

M. B. Nathanson, Explicit sumset sizes in additive number theory, arXiv: 2505.05329, 2025

work page internal anchor Pith review Pith/arXiv arXiv 2025

[10] [11]

O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron

K. O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin. DS11 (2004), 39 pages

work page 2004

[11] [12]

P´ eringuey and A

P. P´ eringuey and A. de Roton, A note on iterated sumsets races, preprint, 2025

work page 2025

[12] [13]

Schinina, On the sums of sets of sizek, preprint, 2025

V. Schinina, On the sums of sets of sizek, preprint, 2025. COMPRESSION AND COMPLEXITY FOR SUMSET SIZES 17 Department of Mathematics, Lehman College (CUNY), Bronx, NY 10468 Email address:melvyn.nathanson@lehman.cuny.edu

work page 2025