Cyclic self-sumset recognition: a credited corollary of the integer hardness theorem
Read the paper (PDF) · Download PDF · Supporting ZIP · Zenodo record
Plain-English explanation · Read on this page · Collaboration
Abstract
We give a short explicit cyclic corollary of the integer hardness theorem of Abboud, Fischer, Safier, and Wallheimer. For unbounded positive input n, deciding whether a given B ⊆ ℤ/nℤ equals A + A for some subset A of the same group is NP-complete in each of two explicit representations: binary n with a binary residue list, and an n-bit characteristic vector. Sums include repeated summands. Hardness already holds for odd n and nonempty B containing zero with every canonical representative b satisfying 2b < n. The proof normalizes integer targets and forces a zero anchor in every cyclic root, after which no sum wraps. Dense hardness uses the source's polynomial numerical universe, separately from the sparse bit-length argument. This is credited exposition; no new hardness gadget, novelty, first-publication, or independent-discovery claim is made.
The idea in plain English
Given a set of residues, can it be exactly the set of all pairwise sums of a set in the same cyclic group? The answer is NP-complete to decide in both the sparse and dense input models. The note derives both from earlier integer sumset hardness.
The exact recognition problem
The input modulus n is a positive integer with no fixed upper bound. Given B ⊆ ℤ/nℤ, ask whether there is a subset A of that same group such that
B = A + A = {a + a′ : a, a′ ∈ A}.
Repeated summands are included. The decision problem is NP-complete under deterministic polynomial-time many-one reductions in each of these two explicit representations:
| Representation | Input |
|---|---|
| Sparse | Binary n and a sorted list of distinct binary canonical residues of B. |
| Dense | Binary n and exactly n indicator bits for B. |
Both problems remain NP-complete when n is odd, B is nonempty, 0 ∈ B, and every canonical residue b satisfies 2b < n. This is a worst-case result for exact decision.
The odd-order zero anchor
Normalize a nonempty integer target by subtracting its even minimum, obtaining 0 ∈ B ⊆ [0, M]. If its minimum is odd, it cannot be an integer self-sumset. Choose odd n > 2M.
If a cyclic root contains a and −a witnessing zero, its diagonal sums 2a and −2a lie in B. Their canonical representatives sum to less than n and to zero modulo n, so both vanish. Oddness then gives a = 0. Thus every cyclic root contains zero and lies in B; its integer pair sums cannot wrap around the modulus.
The conclusion is stronger than existence equivalence: the canonical representatives of every cyclic root are an integer root of B.
Why both input sizes are controlled
For sparse input, normalization and n = max(3, 2M + 1) require arithmetic polynomial in binary input length, even if M is numerically enormous.
Dense hardness uses the bounded integer construction of Abboud, Fischer, Safier and Wallheimer (AFWS) directly. For a 3-CNF formula with q = v + c ≥ 1, after relabeling its occurring variables, the operative construction has
S ⊆ [0, 257q4] ∩ ℤ,
n ≤ max(3, 258q4 + 1).
The dense vector therefore has polynomial length in the explicit formula size. This argument is separate from the sparse bit-length transfer; expanding an arbitrary sparse integer instance would not supply that bound.
NP membership is also explicit: for nonempty B = A + A, translation by one element of A injects A into B, so |A| ≤ |B|. A sparse root list is a polynomial-size witness, and all its pair sums can be checked. A dense root uses n witness bits.
Scope and limitations
The theorem concerns ordinary all-pair self-sums in the same cyclic group and exactly the two input representations stated above. It gives no classification for a prime-modulus-only restriction, distinct-summand sums, two unrelated summand sets, succinct or oracle inputs, randomized algorithms, approximation, average-case recognition or promised-root search.
AFWS’s separate theorem for the additive group of a higher-dimensional finite field is not used as a cyclic-group theorem. Empty targets, zero-span targets, parity branches and malformed inputs are handled explicitly in the note.
Background and prior work
All integer hardness gadgets and the bounded 3SAT construction used here are due to AFWS, Recognizing Sumsets is NP-Complete (SODA 2025). The operative proof edition is arXiv:2410.18661v2, Theorem 1.2 and the composition on pp.21–23 through Lemmas 5.3, 1.5 and 1.4. The support note reconstructs the relevant integer interfaces and handles presentation slips while retaining the displayed bound. The cited version is the version used for the proof comparison.
The AFWS integer-hardness input already gives an elementary cyclic consequence through an even-order lift: for an anchored target in [0, M] and even n > 2M, a cyclic root can be translated by an element annihilated by doubling so that it contains zero. Its canonical sums then do not wrap. The odd-order lemma above separately ensures that every original canonical root already has the anchor. Generic cyclic hardness is presented as an attributed consequence, with no new hardness-gadget or independent-discovery claim.
Campos’s Problem 15, attributed to Alon and Granville, asks the same-group recognition question without fixing a computational encoding. Earlier antecedents include Croot and Lev’s Problem 4.11, Dose’s even integer-translation lemma, and Antoniou and Tringali’s anchored no-wrap lifts. The note makes no historical-firstness or present-day-openness claim.
Status and AI use
Unrefereed preprint. AI tools assisted substantially in developing, writing and checking the work. Independent human review is welcome.
Read the paper
Open the published PDF · Download PDF · Original PDF on Zenodo
Supporting materials
Download pr1052_support_v1_0.zip · Original support archive on Zenodo
Collaborate on this result
I welcome researchers in additive combinatorics or computational complexity who would like to independently check the zero-anchor transfer, the sparse and dense size accounting, or the precise source interface for the bounded AFWS construction. Careful comparison with earlier cyclic formulations or substantive work on a revised exposition and journal submission would also be useful.
Authorship and responsibilities would be discussed in relation to substantive contributions. Contact Alec.
Cite this paper
Kriebel, Alec (2026). Cyclic self-sumset recognition: a credited corollary of the integer hardness theorem. Version 1.0. Zenodo. 10.5281/zenodo.23430681.
Licensing
The deposited work is available under Creative Commons Attribution 4.0.