Size-4 Counterexamples to the Sidon-Extension Conjecture

Tong Niu

arxiv: 2604.25214 · v3 · submitted 2026-04-28 · 🧮 math.CO · cs.DM

Size-4 Counterexamples to the Sidon-Extension Conjecture

Tong Niu This is my paper

Pith reviewed 2026-05-15 07:38 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords Sidon setsperfect difference setsErdős conjecturecounterexamplesnon-extending setssize-4 Sidon setsSinger affine orbitsbrute-force search

0 comments

The pith

There exist Sidon sets of size 4 that cannot be extended to perfect difference sets.

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

Erdős conjectured every finite Sidon set extends to a finite perfect difference set, but size-5 counterexamples were found recently. This paper supplies evidence that the failure already occurs at size 4 by giving two explicit Sidon sets in the integers. These sets and all their dilations and reflections fail to extend in every modulus up to 133 by exhaustive search and in every prime-power order up to 317 by an affine-orbit test. The count of such non-extending sets up to N matches exactly the pattern generated by these two families for N at most 50. A proof that they never extend for any modulus is left open.

Core claim

We exhibit two integer Sidon sets A = {0, 1, 3, 11} and B = {0, 1, 4, 11} together with the apparent infinite family of their dilations kA, kB and reflections, all of which fail to extend for every prime power q ≤ 317 via the Singer affine-orbit check and unconditionally for every modulus v ≤ 133 via brute-force depth-first search. This indicates that the smallest size of a non-extending Sidon set is 4.

What carries the argument

The two base Sidon sets A = {0, 1, 3, 11} and B = {0, 1, 4, 11} together with their dilations and reflections, verified as non-extendable by the Singer affine-orbit check and brute-force depth-first search.

Load-bearing premise

That failure to extend for all prime powers up to 317 and all moduli up to 133 is enough to conclude these sets never extend for any modulus.

What would settle it

An explicit perfect difference set of size 4 in some modulus v greater than 133 or prime power q greater than 317 that contains a dilation or reflection of A or B would show that at least one of these sets does extend.

read the original abstract

A finite set $S \subset \mathbb{Z}$ is a Sidon set if its pairwise differences are distinct. Recall that a perfect difference set (PDS) of order $n$ is a set $B \subset \mathbb{Z}_v$ ($v = n^2 - n + 1$) of size $n$ such that every nonzero residue arises exactly once as a difference of two elements of $B$. Erd\H{o}s's \$1000 conjecture -- that every finite Sidon set extends to a finite PDS -- was disproved by Alexeev and Mixon (arXiv:2510.19804, October 2025), via the size-5 counterexamples $\{1,2,4,8,13\}$ and Hall's earlier $\{1,3,9,10,13\}$; they then asked: what is the smallest size $s$ of a non-extending Sidon set? The trivial bounds give $3 \le s \le 5$. Our evidence points to $s = 4$. We exhibit two integer Sidon sets, \[ A = \{0, 1, 3, 11\}, \qquad B = \{0, 1, 4, 11\}, \] together with the apparent infinite family of dilations $kA$, $kB$ and their reflections, all of which fail to extend for every prime power $q \le 317$ via the Singer affine-orbit check (rigorous under Hall's 1947 uniqueness for Desarguesian cyclic planes through $q \le 40$ and under the prime-power conjecture beyond that), and unconditionally for every modulus $v \le 133$ via brute-force depth-first search. We also report the exact density $N_{\text{ne}}(N) = 4 \lfloor N / 11 \rfloor$ of non-extending size-4 Sidon sets in $[0, N]$ for $N \le 50$ -- the match is exact, which suggests the $kA, kB$ family is complete in this range. A complete proof, perhaps in the spirit of Alexeev--Mixon's polarity argument or via a multiplier descent, remains open.

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

This paper gives the first explicit size-4 Sidon sets that fail to extend, with solid checks up to moderate bounds but a conditional gap for larger prime powers.

read the letter

The main takeaway is that Niu has produced concrete size-4 examples—A = {0,1,3,11} and B = {0,1,4,11}—along with their dilations that do not extend to perfect difference sets. This narrows the open question on the smallest non-extendable Sidon set from the previous 3-to-5 range down to exactly 4, at least in the verified cases. The work improves on Alexeev-Mixon by moving from size 5 to size 4 and by giving an explicit infinite-looking family plus a density count that matches exactly up to N=50. The computational side is handled cleanly: brute-force depth-first search covers all v ≤ 133 unconditionally, and the Singer affine-orbit method plus Hall's uniqueness theorem handles prime-power orders q ≤ 40 rigorously. That part is reproducible and useful. The soft spot is the extension to q ≤ 317, which leans on the unproven prime-power conjecture for cyclic planes beyond q=40. The paper states this limitation plainly and leaves a full unconditional proof open, so the claim is scoped correctly rather than overstated. No circularity or hidden parameters appear. This is for specialists in combinatorial number theory who care about Sidon sets, difference sets, and the Erdős conjecture. A reader already following the Alexeev-Mixon work will get immediate value from the new examples and the density observation. It deserves a serious referee because the concrete sets and the bounded verification are new and checkable; the conditional part is clearly flagged. I would send it to peer review with the expectation that the authors tighten the statement around the conjecture or add more unconditional data if possible.

Referee Report

1 major / 3 minor

Summary. The manuscript presents two explicit size-4 Sidon sets A = {0,1,3,11} and B = {0,1,4,11} together with their dilations kA, kB and reflections; it reports that these fail to extend to a perfect difference set in Z_v for every v ≤ 133 (via unconditional brute-force depth-first search) and for every prime-power order q ≤ 317 (via the Singer affine-orbit check, rigorous for q ≤ 40 by Hall's uniqueness theorem and conditional on the prime-power conjecture for larger q). The paper also records the exact count N_ne(N) = 4⌊N/11⌋ of non-extending size-4 Sidon sets in [0,N] for N ≤ 50 and states that a complete proof of non-extendability for all moduli remains open. This supplies concrete evidence that the smallest size of a non-extending Sidon set is 4.

Significance. If the reported verifications hold, the work supplies the first size-4 counterexamples to Erdős's Sidon-extension conjecture, tightening the trivial bounds 3 ≤ s ≤ 5 after the size-5 examples of Alexeev-Mixon. The unconditional exhaustive search up to v = 133, the exact density match through N = 50, and the machine-checkable nature of the Singer-orbit test for small q constitute reproducible computational support that is valuable in this area and may guide subsequent theoretical arguments such as polarity or multiplier descent.

major comments (1)

[Singer affine-orbit check] Singer affine-orbit check (q > 40): the claim that the sets fail to extend for every prime power q ≤ 317 is conditional on the unproven prime-power conjecture for cyclic planes beyond q = 40; while the manuscript notes the dependence, this conditional status directly limits the strength of the evidence for the infinite family and should be stated explicitly in the abstract and conclusion.

minor comments (3)

[Definition of the families] The precise construction of the reflections of kA and kB is not spelled out; adding a short sentence or equation defining the reflected sets would remove ambiguity.
[Computational verification] The description of the depth-first search for v ≤ 133 should include at least one sentence on the pruning or ordering strategy employed, to facilitate independent verification.
[Rigorous range q ≤ 40] Hall's 1947 uniqueness theorem for Desarguesian planes is invoked for q ≤ 40; the precise reference (including page or theorem number) should be supplied in the relevant paragraph.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the constructive suggestion regarding the presentation of the conditional results. We agree that the dependence on the prime-power conjecture for q > 40 merits more explicit emphasis in the abstract and conclusion to accurately reflect the strength of the evidence.

read point-by-point responses

Referee: [Singer affine-orbit check] Singer affine-orbit check (q > 40): the claim that the sets fail to extend for every prime power q ≤ 317 is conditional on the unproven prime-power conjecture for cyclic planes beyond q = 40; while the manuscript notes the dependence, this conditional status directly limits the strength of the evidence for the infinite family and should be stated explicitly in the abstract and conclusion.

Authors: We agree that the conditional status for q > 40 should be stated more prominently. In the revised version we will add a sentence to the abstract and a corresponding paragraph in the conclusion explicitly noting that the non-extendability claims for prime powers q > 40 rely on the prime-power conjecture (while remaining unconditional for q ≤ 40 via Hall’s uniqueness theorem and for all v ≤ 133 via exhaustive search). This change will be made without altering any computational claims or the overall conclusions. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper exhibits explicit Sidon sets A and B and verifies non-extendability via direct brute-force DFS for v ≤ 133 and Singer affine-orbit checks for prime powers q ≤ 317 (rigorous for q ≤ 40 via Hall's uniqueness theorem). The density formula N_ne(N) = 4⌊N/11⌋ is presented purely as an observational match for N ≤ 50 and is not used to derive or force any non-extension claim. No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citation chains appear; all central claims rest on independent computation and external theorems within the stated verified range.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definitions of Sidon sets and perfect difference sets from the literature, plus the known uniqueness theorem of Hall (1947) for small Desarguesian planes; no free parameters or new entities are introduced.

axioms (1)

standard math Hall's 1947 uniqueness theorem for Desarguesian cyclic planes of order q ≤ 40
Invoked to make the Singer check rigorous for small q.

pith-pipeline@v0.9.0 · 5717 in / 1336 out tokens · 31918 ms · 2026-05-15T07:38:30.361398+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[1]

Alexeev and D

B. Alexeev and D. G. Mixon,Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof,arXiv:2510.19804, October 2025; v2 January 2026

work page arXiv 2025
[2]

L. D. Baumert and D. M. Gordon,On the existence of cyclic difference sets with small parameters,Fields Inst. Commun.41(2004), 61–68

work page 2004
[3]

Hall,Cyclic projective planes,Duke Math

M. Hall,Cyclic projective planes,Duke Math. J.14(1947), 1079–1090

work page 1947
[4]

Independent brute-force verification of 4 candidate non-extending size-4 Sidon sets:\n

J. Singer,A theorem in finite projective geometry and some applications to number theory,Trans. Amer. Math. Soc.43(1938), 377–385. Acknowledgements The author thanks Boris Alexeev and Dustin G. Mixon. Their October 2025 paper resolved Erdős’s 1000 conjecture, and the question ofsposed explicitly in their Section 8 is what motivated this note. AppendixA.Ve...

work page 1938

[1] [1]

Alexeev and D

B. Alexeev and D. G. Mixon,Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof,arXiv:2510.19804, October 2025; v2 January 2026

work page arXiv 2025

[2] [2]

L. D. Baumert and D. M. Gordon,On the existence of cyclic difference sets with small parameters,Fields Inst. Commun.41(2004), 61–68

work page 2004

[3] [3]

Hall,Cyclic projective planes,Duke Math

M. Hall,Cyclic projective planes,Duke Math. J.14(1947), 1079–1090

work page 1947

[4] [4]

Independent brute-force verification of 4 candidate non-extending size-4 Sidon sets:\n

J. Singer,A theorem in finite projective geometry and some applications to number theory,Trans. Amer. Math. Soc.43(1938), 377–385. Acknowledgements The author thanks Boris Alexeev and Dustin G. Mixon. Their October 2025 paper resolved Erdős’s 1000 conjecture, and the question ofsposed explicitly in their Section 8 is what motivated this note. AppendixA.Ve...

work page 1938