Efficient Recognition of Cyclic Sumsets

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

The cyclic group $\mathbb Z/n\mathbb Z$ uses addition modulo $n$. For a subset $A$, its sumset is $A+A=\{a+a':a,a'\in A\}$; summands need not be distinct. The decision input consists of $n$ and an encoding of $B\subseteq\mathbb Z/n\mathbb Z$. A positive instance has a subset $A$ whose sumset equals $B$ exactly, rather than merely containing it.

Statement recorded in the supplied source.

Given $B\subseteq\mathbb Z/n\mathbb Z$, is there an efficient algorithm that decides whether some $A\subseteq\mathbb Z/n\mathbb Z$ satisfies $B=A+A$? [S2]

Scope qualification.

The complexity depends on the source encoding of $B$ and $n$; explicit membership arrays and sparse binary-encoded lists have different input lengths. No encoding-independent polynomial-time claim is inserted.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Can one efficiently recognize which subsets of a finite cyclic group are sums of a subset with itself?

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30005118 (OWR-10252930-031). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorics, Probability and Computing $2023$, Oberwolfach Reports, DOI 10.4171/owr/2022/22, pp. 1165--1237 https://doi.org/10.4171/owr/2022/22.
• S3 official OWR report https://publications.mfo.de/bitstream/handle/mfo/3964/OWR_2022_22.pdf?isAllowed=y&sequence=4. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30005118 and source code OWR-10252930-031 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

I read Problem 15, attributed to Alon and Granville and presented by Marcelo Campos, on printed page 1228 of the primary report. It asks exactly the cyclic recognition question preserved above. The sumset-counting talk on pages 1174--1175 is a different passage and is not the location of this problem. I also consulted the introduction, Theorem 1.2 and the accompanying reduction-size paragraph of Abboud, Fischer, Safier and Wallheimer, Recognizing Sumsets is NP-Complete, arXiv:2410.18661v2. Their theorem states NP-completeness over the integers; the accompanying paragraph gives a reduction from 3-SAT with $N$ variables and clauses to a set contained in an interval of size $O(N^4)$. That integer hardness theorem is an explicitly external dependency: its positioning and masking gadgets are not re-proved or independently verified here. The elementary reduction below was suggested by the root Codex GPT-6 agent and then independently inspected, written out and adversarially checked by this OpenAI gpt-6-astra agent. No novelty claim is made.

Research attempt: Integer-to-cyclic recognition reduction with encoding control

Decision problems and encodings.

Let $q\geq1$ be an integer and let $B\subseteq\mathbb Z/q\mathbb Z$. The question is whether $B=A+A$ for some subset $A$, with addition modulo $q$. Consider either (i) $q$ in binary and the distinct canonical residues of $B$ in a binary list, or (ii) a membership array of length $q$. We prove NP-completeness under either encoding, using the stated external integer theorem. Thus a polynomial-time decision algorithm exists if and only if $\mathrm P=\mathrm{NP}$. This conclusion does not assert an unconditional separation of those classes.

Membership in NP.

The empty input set has the empty root. For a nonempty root choose $a_0\in A$. The injection $a\mapsto a+a_0$ maps $A$ into $B$, so $|A|\leq |B|$. A witness list therefore uses $O(|B|\log(q+1))$ bits. Computing all at most $|B|^2$ pair sums, reducing modulo $q$, removing repetitions and comparing with $B$ verifies the witness in polynomial time in either specified input length. This also covers $q=1$; there is no hidden demand for a witness of size $q$ under sparse encoding.

Normalization of integer instances.

Given a finite nonempty set $S\subseteq\mathbb Z$, put $s_0=\min S$. If $S=C+C$, then $s_0=2\min C$. Thus odd $s_0$ implies a NO instance. For even $s_0$ define $B=S-s_0$ and $M=\max B$. Then \[ S=C+C\quad\Longleftrightarrow\quad B=(C-s_0/2)+(C-s_0/2). \] Conversely any integer root $D$ of $B$ yields the root $D+s_0/2$ of $S$. Here $0\in B\subseteq[0,M]\cap\mathbb Z$ and $M\geq0$. An empty $S$ is mapped to a fixed YES instance, for example $(q,B)=(3,\varnothing)$. An odd minimum is mapped to the fixed NO instance $(3,\{0,1\})$. To verify the latter, a root has at most two elements by the injection just proved. A singleton has a singleton sumset. For two distinct residues $a,b$ modulo $3$, the three sums $2a,a+b,2b$ are distinct: equality of either adjacent pair implies $a=b$, and $2a=2b$ does also because $2$ is invertible modulo $3$. Hence its sumset has three elements.

The no-wrap lemma.

For a normalized input set use the odd modulus \[ q=2M+3. \] We claim that $B$ has an integer sumset root if and only if it has a root modulo $q$. The forward implication follows just by reducing an integer equality modulo $q$; distinct elements of $B\subseteq[0,M]$ remain distinct. For the reverse implication suppose $B=A+A$ modulo $q$. Because $0\in B$, choose $a,b\in A$ with $a+b=0$ modulo $q$. Let $r,s\in[0,q-1]$ be the canonical residues of $2a,2b$. Both belong to $B$, so $0\leq r,s\leq M$. Moreover $r+s=0$ modulo $q$ and $0\leq r+s\leq2M<q$. Therefore $r=s=0$. Since $q$ is odd, multiplication by $2$ is injective, and $a=b=0$ modulo $q$. We have proved $0\in A$. It follows that every canonical representative of $A$ is in $B$, using $a=0+a\in A+A$. All representatives of $A$ thus lie in $[0,M]$. Their ordinary pair sums lie in $[0,2M]\subset[0,q-1]$, so none wraps modulo $q$. The modular equality is consequently the ordinary integer equality $A+A=B$. This proves both directions.

Polynomial encoding bounds.

Subtracting $s_0$ and forming $q=2M+3$ increases the binary length of each integer by at most an additive constant relative to the largest input magnitude. The number of elements of $B$ is $|S|$ and the exceptional instances have constant size. The map is thus a polynomial-time many-one reduction for sparse binary lists. For membership arrays, arbitrary huge binary integer inputs would not give a polynomial-size output array. Instead compose directly with the external 3-SAT reduction whose integer interval has size $O(N^4)$. After normalization $M=O(N^4)$ and hence $q=O(N^4)$, so the whole membership array can be produced in polynomial time. The same theorem consequently proves NP-hardness for both encodings. Together with membership in NP this establishes the claimed classification, even with hardness restricted to odd $q$.

An exact algorithm and the failed shortcut.

For completeness there is an elementary exponential search with candidate set \[ H=\{a\in\mathbb Z/q\mathbb Z:2a\in B\}. \] Every root lies in $H$, since every self-sum must belong to $B$. For each $b\in B$, the congruence $2a=b\pmod q$ has at most two solutions, computable by the Euclidean algorithm (one for odd $q$). Thus $|H|\leq2|B|$. Enumerating subsets of $H$ and checking pair sums is a finite exact algorithm. The necessary condition $A\subseteq H$ does not itself identify the root, and checking $H+H=B$ is not a correct recognition algorithm: for $q=7$ and $B=\{0,1,2\}$ the root $A=\{0,1\}$ works, but $H=\{0,1,4\}$ contains $4$ and $H+H$ contains $4\notin B$. The hardness classification concerns arbitrary inputs, not the termination of this exponential algorithm or the possibility of useful special-case algorithms.

Verification and adversarial audit

The reverse implication was checked at its two essential points: $0\in B$ alone does not imply $0\in A$ in a general cyclic group, and an arbitrarily large modulus alone does not prevent a modular root from having large representatives. The doubled-residue argument proves both claims using oddness and $2M<q$. For example the use of oddness cannot simply be erased: modulo $2$, the set $A=\{1\}$ has $A+A=\{0\}$ without containing $0$. The cases $S=\varnothing$, $M=0$, odd negative minima, $q=1$ in the verification problem, singleton roots and sparse witness size were separated explicitly. The dense encoding proof uses the external polynomial-interval theorem, not an unjustified expansion of arbitrary binary integers into an array.

Audit corrections.

The source location was corrected from the separate Campos counting talk to Problem 15 on page 1228. Oddness, empty inputs, negative-minimum normalization, and polynomial array size were added explicitly. The false maximal-candidate-set recognition shortcut was falsified by the displayed modulo-$7$ example.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The argument supplies the usual complexity-theoretic classification of the entire cyclic recognition question for both explicit encodings identified in the preserved scope note. It depends on the cited integer NP-completeness theorem and on the standard definitions of polynomial-time reduction and NP-completeness. It neither proves $\mathrm P\ne\mathrm{NP}$ nor settles fine-grained, average-case, or special input-family questions that the original statement did not ask.

Full original-target declaration.

The entire original decision question is classified for both stated encodings, without restricting the input sets, weakening the requested decision, or replacing cyclic groups by a different family. The elementary reduction and both encoding arguments are fully proved here. The integer hardness theorem is a cited external dependency. The parent Codex GPT-6 agent has reviewed the complete written reduction and approved this full scope. No claim of an unconditional $\mathrm P\ne\mathrm{NP}$ theorem or new mathematical priority is made.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 100% The proof gives the complete NP-completeness classification for both specified encodings of the original recognition problem. Completion measures original-target coverage, not novelty or independent verification.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46961 (consulted 2026-10-11).
• https://arxiv.org/html/2410.18661v2 (consulted 2026-10-11).

Model and contributor disclosure

Codex GPT-6 completed written mathematical review of the full reduction and scope; this is model-assisted review, not independent human proof checking. OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review and suggested the material integer-to-cyclic reduction; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Solved as a complete complexity classification, conditional on the explicitly cited known integer NP-completeness theorem. A polynomial algorithm exists exactly if $\mathrm P=\mathrm{NP}$. No unconditional separation, novelty, or independently verified proof of the external integer gadgets is asserted. The historical catalogue source status remains unchanged.