#156: Round 5 — exact maximal-Sidon values through 136

The target (erdosproblems.com/156, [ESS94]). A Sidon set has no repeated pairwise sums. A greedy Sidon set in {1,...,N}, extended until nothing more can be added, is automatically maximal and has size ≫N^(1/3) — cheap. The question asks whether a maximal Sidon set can be built as small as O(N^(1/3)). Ruzsa (1998) got O((N log N)^(1/3)) — one log factor above the target, unimproved in the literature since. HONEST DECLINE, but a genuinely useful one: literature search confirmed the record hasn't moved, and reconstructing Ruzsa's method (it isn't freely available in full) from first principles and its known descendants pins down exactly why the log is there.

Round 5 (11 August): thirty-four more exact values. Let a(n) be the minimum size of a maximal Sidon subset of {1,...,n}. A new complete computation proves

a(n)=8 for every 102≤n≤136.

For the lower bound, translate a candidate so its first mark is zero. Any candidate in this range then has diameter at most 135, and maximality requires its blocked component to have length at least n. Two complete seven-mark engines, one using unordered pair sums and one using three words of positive differences, independently enumerate all 8,515 search tasks. They agree on 4,664,137,760 endpoint attempts, 3,188,523,904 Sidon rulers, 455,390 rulers whose blocked component contains their hull, and a longest blocked run of only 101. Complete searches through six marks give a still smaller maximum of 67. Thus no set of at most seven marks is maximal on an interval of any claimed length.

The upper certificate is one ruler: {0,39,47,51,52,61,67,101}. Its 36 unordered pair sums are distinct and its blocked component is [−16,119], containing 136 consecutive integers. Translations of this ruler give maximal eight-element Sidon sets for every n from 102 through 136; the public checker tests every outside insertion in all 35 domains.

Hostile audit. A third implementation uses mutable byte arrays, a different three-mark task decomposition, and reflection symmetry. It recovers every seven-mark counter exactly and explicitly finds zero hull-covering rulers of diameter 102 through 135. A separate one-tree search reproduces every row through six marks, while a literal checker rejects all 3,885 outside insertions in the upper certificates. The full author and audit bundles, hashes, sources, and frozen outputs are public. This advances only the exact finite sequence; the asymptotic Problem 156 remains open.

Round 4 (11 August): the exact sequence reaches its next jump. A complete extension of the finite computation now proves

a(n)=7 for every 68≤n≤101,   and   a(102)=8.

The lower bound at 102 is the load-bearing new piece. Three exact engines enumerate every normalized set of at most six marks and diameter at most 101; their size-six totals agree at 79,208,745 raw sets, 46,198,688 Sidon sets, and longest blocked run 67. A fourth OpenMP engine exhausts every seven-mark Sidon ruler of diameter at most 101: 386,623,922 Sidon rulers survive the difference test, 455,390 cover their own hull, and the longest blocked run is exactly 101. No seven-mark set can therefore be maximal on {1,...,102}.

The matching upper certificates are short. The normalized ruler {0,24,27,35,39,41,75} blocks the full interval [−17,83], so its translations give seven-mark maximal sets for every new n from 96 through 101. At 102 the eight-mark set {10,33,38,42,59,69,71,89} is Sidon and rejects every one of the 94 outside points.

Independent audit. A separate unpruned program visited all C(101,6)=1,267,339,920 normalized seven-mark candidates, rebuilt every difference set at the leaf, and tested insertions directly. It recovered the same 386,623,922 Sidon rulers and the same reported optimum, while full ASan/UBSan runs passed for the production enumerators. The public extension bundle freezes the proof reduction, four enumerators, direct witness replay, logs, hashes, and hostile audit. This is still a finite computational result; the asymptotic Problem 156 remains open.

Round 3 (11 August): the exact finite frontier moves by thirty places. Let a(n) be the minimum size of a maximal Sidon subset of {1,...,n}, with unordered sums including the diagonal sums 2a. The current OEIS A382397 table stops at n=65. We now have the exact continuation

a(66)=a(67)=6,   and   a(n)=7 for every 68≤n≤95.

This is an exact finite result, not a solution of the asymptotic Erdős problem. Its useful reduction is a blocking lemma. If S(A) is the old pair-sum set of a Sidon set A, define

B(A) = A
  union {s-a:
         s in S(A), a in A}
  union {s/2:
         s in S(A), s even}.

For x outside A, the set A∪{x} fails to be Sidon exactly when x∈B(A): the only new sums are x+a and 2x, and failure means one of them equals an old sum. Thus A is maximal on an interval exactly when every unused point of that interval is blocked.

Why the finite search is complete. Translate a candidate so its least mark is 0, writing R={0}∪T and L=max R. Translation preserves both the Sidon property and blocking. If the maximal consecutive run in B(R) containing the hull [0,L] has length h, then R has a maximal translate in an n-point interval exactly when h≥n and L≤n−1. For every n≤95 it therefore suffices to enumerate every normalized ruler with diameter at most 94.

Two exact C++ engines did that for every size at most six. One stores positive differences in a 128-bit mask and constructs the difference form of B(R); the other stores unordered sums in a bitset and constructs the displayed sum form. Their central representations differ, although they deliberately share the normalization, traversal shape, and reporting scaffolding. They agree on every row:

k=1: 1 raw, 1 Sidon, 1 hull-covered; best run 1.
k=2: 94 raw, 94 Sidon, 2 hull-covered; best run 4.
k=3: 4,371 raw, 4,324 Sidon, 8 hull-covered; best run 10.
k=4: 134,044 raw, 125,504 Sidon, 76 hull-covered; best run 22.
k=5: 3,049,501 raw, 2,434,706 Sidon, 1,102 hull-covered; best run 42.
k=6: 54,891,018 raw, 30,594,300 Sidon, 20,166 hull-covered; best run 67.

The first six-mark ruler attaining 67 is R={0,7,19,22,28,39}, whose blocked run is [−15,51]. Hence no set of at most six marks can be maximal on any interval of length 68 through 95. The rows of sizes at most five similarly rule out five marks at lengths 66 and 67.

The matching upper certificates are explicit. Translating that extremal ruler gives the six-mark witness {16,23,35,38,44,55} for n=67; {21,25,31,40,43,60} works for n=66. Thirty directly checked witnesses cover every n from 66 through 95, ending with {30,31,33,48,55,59,93} at n=95. The public bundle contains both enumerators, all witnesses, frozen logs, the proof of the reduction, and direct sum-by-sum and difference-by-difference checkers.

Audit and scope. Three hostile audits rebuilt the programs, reproduced all 54,891,018 size-six candidates under sanitizers, checked the blocking equivalence separately, and verified every outside insertion for all 30 witnesses. One audit added a third, unpruned enumerator which visits all 58,079,029 normalized sets of sizes one through six and tests insertion directly from positive differences; it matched every row. No discrepancy was found. That Round 3 computation stopped at n=95; Round 4 above supplies the complete extension through 102. The parent question still asks for O(N^(1/3)); the exact sequence moved, but Ruzsa's O((N log N)^(1/3)) asymptotic record did not.

Where the log actually comes from. Ruzsa's construction: embed a dense Singer-difference-set Sidon set into a small ambient group of size M, then randomly lift it into {1,...,N}. Average-degree counting alone only needs M≫N^(2/3) — that would give the target O(N^(1/3)). But guaranteeing every one of the ~N points gets covered (not just almost all of them) needs a union bound over N events, and that union bound is exactly what forces M up by a factor of log N — coupon-collector, not Sidon combinatorics. Ruzsa's (N log N)^(1/3) falls out of balancing √M + N/M with that M. Nobody has shown the log is necessary — only that this specific covering method needs it.

The real find: a verified sibling result the tracker doesn't mention. Redman, Rose, and Walker (arXiv:2109.00292, SIAM J. Discrete Math. 2022) prove the exact group-theoretic analogue in Z₂ⁿ: a maximal Sidon set of size O((n·2ⁿ)^(1/3)) — same "log-like" factor (n = log|G|), same construction template, explicitly adapted from Ruzsa's method. We verified the citation directly: real paper, real authors, matches the claimed bound exactly. They also note that Bennett–Bohman random-greedy analysis of the analogous covering process predicts this factor is tight in the group setting — suggestive, not a proof, but it's the first piece of evidence either direction on whether Ruzsa's log is real or just an artifact of one particular argument.

Round 2: the log is provably structural for random lifts — not a sloppy union bound. Round 1 left a precise question open: is the log necessary, or just an artifact of Ruzsa's union bound? For his actual independent random-lift model, it's necessary. The upper half is Ruzsa's: each non-Singer target survives with probability at most e^(−c·p/M). The new half is a matching LOWER bound — the Lovász local lemma, applied to the O(p) collision events for a fixed target, whose dependency graph has bounded degree (exactly because the Singer set is Sidon modulo q): the survival probability is at least e^(−C·p/M). So Ruzsa's exponential estimate is the right ORDER; there is no hidden extra saving waiting in the dependence. We verified the load-bearing pieces directly — the saturation counting that sets the N^(1/3) floor, Singer (q,p+1,1) difference sets for p=2,3,5 (every nonzero residue a unique difference, Sidon modulo q), the local-lemma condition, and the threshold algebra.

The threshold is sharp, and below it the failure is total. Let U be the number of targets a random lift leaves unblocked. McDiarmid's bounded-differences inequality (changing one height moves U by O(p²)) gives Pr(U=0) ≤ e^(−Ω(p)) right at the log-free scale p≈M≈N^(1/3), where the expected number of uncovered targets is E U = Θ(N) — not a sparse cleanup set, a positive-density SEA of them. A small Monte Carlo makes it visible even at p=5: the unblocked-target fraction falls monotonically 0.71 → 0.00 as λ=p/M crosses log N. The iid covering threshold is λ = Θ(log N). Random heights cannot remove the log.

A real reduction — and why it still isn't enough randomly. Ruzsa demands every non-Singer residue class be fully covered; that's stronger than needed. An alteration lemma (verified counting) shows that if the initially addable points outside the Singer classes land in only L residue classes modulo q, the lift extends to a maximal Sidon set of size at most (p+1) + L + 2⌊(N−1)/q⌋ — the added points anchor by class, and their within-class offsets are forced to be distinct nonzero multiples of q or they'd create a pair-sum collision. At the critical scale p≈M≈N^(1/3) the target drops to achieving L=O(p): holes confined to O(p) of the q≈p² columns, not zero holes. Materially weaker — but a random critical lift still misses it by an order of magnitude (it would need U=O(p²) where E U=Θ(p³), the same e^(−Ω(p)) wall).

The door that's still open: deterministic heights. The probability bound e^(−Ω(p)) is enormously larger than the probability M^(−(p+1)) of any one specific height assignment, so an exponentially rare, algebraically structured labeling could still cover everything; the concentration estimate is nowhere near strong enough to rule it out. The log-free problem inside Ruzsa's architecture is now precise: choose p+1 labels d_u ∈ [0,M−1] with p/M=Θ(1) so that, for all but O(p) of the q≈p² residues ρ, the set of blocked fiber-heights H_ρ(d) — each a Θ(p)-element set of sums d_u + d_v − d_w over Singer certificates — covers all Θ(M)=Θ(p) relevant heights. That is an almost-perfect simultaneous covering problem, closer to an orthogonal array or an algebraic covering code than to ordinary probabilistic selection. Parameter tuning and stronger tail inequalities are provably dead ends; this labeling is the right next object. (Equally open: a completely different Sidon set whose A+A−A nearly tiles [N], or a finite-group perfect-saturation object embedded into the integers carry-aware.)

What's still open — sharper now. The bound itself has not moved: still no O(N^(1/3)) maximal Sidon set, and still no lower bound past the trivial Ω(N^(1/3)) — the universal counting obstruction remains N^(1/3), with no evidence for a universal (log N)^(1/3) floor. But the question is no longer "is the log real or an artifact?" For random lifts it is provably real and structural. The live question is whether a deterministic, algebraic lift can do what random ones provably cannot — and Round 2 turns that into a concrete design problem rather than a vague hope. Ruled out: optimizing Ruzsa's constants or prime, routine dependency estimates, iid heights at p=O(N^(1/3)), sparse random cleanup, and swapping Singer for any other dense quotient (same k³/N intensity). 28 years, one log factor — still standing, now with a named attack vector.