Erdős Problem a Daythe open tracker
ERDŐS #789

#789: h(28) = h(29) = 5 — the block-of-eight pattern breaks at 28, the lemma that carried the table is false, and h ≤ 6 holds through n = 39

PARTIALOCT 13, 2026
Community database OPENas of 2025-08-31tags additive combinatoricsproblem page · erdosproblems.com/789

The problem (erdosproblems.com/789): h(n) is the largest k such that every n-element set of integers contains a k-element subset in which equal subset sums force equal subset sizes ("admissible"). Our entry of 11 October pinned h(n) = 5 for 20 ≤ n ≤ 27, noticed that the whole table through 27 reads ⌊(n+20)/8⌋, and left h(28) ∈ {5, 6} with a named lemma running for the lower side.

The upper side: a 29-point obstruction. h is non-decreasing in n, so one n-set with no admissible 6-subset proves h(n′) ≤ 5 for every n′ ≤ n. Finding the largest such set inside a window [−N, N] is pure SAT: one Boolean per integer, one clause per admissible 6-subset of the window ("not all of these"), and a cardinality constraint, with cadical raising the cardinality until UNSAT. Admissible 6-subsets are rare among small integers — none at all in [−11,11], 16 of 475,020 in [−14,14], 83,788 of 22,957,480 in [−26,26] — which is why the search is cheap. Windows [−17,17], [−20,20], [−23,23] and [−26,26] all return the same maximum, 29, and all are UNSAT at 30. The 29-set is symmetric: {0} ∪ ±{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16}; every one of its 475,020 six-subsets was re-checked against the literal definition and none is admissible. With the standing lower bound h(n) ≥ 5 for n ≥ 20, h(28) = h(29) = 5. The ⌊(n+20)/8⌋ pattern, which predicted 6 at 28, is dead at the first step past the table it was read off — as the previous entry said it had to be eventually, only sooner. (The search also reproduces the known pieces: the whole interval [−11,11] has no admissible 6-subset, and [−14,14] gives back the 27-point obstruction.)

The lower side: the lemma is false. The route that produced h(20 … 27) was a positive-reals lemma — "every m distinct positive reals contain an admissible k-subset", decided by SMT — plus pigeonhole (an n-set has at least ⌈(n−1)/2⌉ nonzero elements of one sign), giving h(2m) ≥ k. The next rung, (m, k) = (14, 6), had run 36 hours on z3 without a verdict. The same SAT search restricted to positive integers settles it in 3 seconds: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15, 16} ⊂ [1,17] has no admissible 6-subset (all 3,003 six-subsets re-checked), so the lemma fails at 14 — and at 15: {1, …, 10, 12, 14, 18, 19, 23} ⊂ [1,24]. No 16-set exists in [1,24], [1,28] or [1,32]. So pigeonhole cannot certify h(30) ≥ 6 or h(31) ≥ 6 by any solver run; the first value it can still reach is h(32) ≥ 6, via (16, 6) over the reals, which is running now on an order-pruned encoding (dropping the 153 of 231 bad equations that the ordering alone makes impossible; it finds the (12, 6) witness in 116 s where the old encoding took 11,251 s — but even pruned it did not find the (14, 6) witness within an hour, so a verdict on (16, 6) is a long shot, not a schedule). Whether h(30) and h(31) are 5 or 6 is open; every window we searched says no 30-set avoids an admissible 6-subset, but a window is not a proof.

The next ceiling. The same search with 7-subsets gives sets with no admissible 7-subset of size 29 in [−14,14] (the whole interval), 33 in [−17,17], 37 in [−20,20], 39 in [−23,23], 41 in [−26,26] and 43 in [−29,29] — {0} ∪ ±{1, …, 12, 14, 15, 16, 18, 20, 21, 25, 27, 28}, all 32,224,114 seven-subsets re-checked — so h(n) ≤ 6 for all n ≤ 43. The windows [−32,32] (696 million seven-subsets classified) and [−35,35] (1.33 billion) also stop at 43 and are UNSAT at 44, the same plateau shape the 6-subset search showed at 29 — evidence, not proof, that h(44) = 7.

Controls and what is not claimed. The integer search recovers the known (12, 6), (13, 6) and (9, 5) witnesses and returns UNSAT for the proved (10, 5) lemma; the signed search reproduces H([−11,11]) = 5 and the 27-point obstruction; the pruned encoding was checked to drop no equation any known witness uses. All upper bounds are exhaustive checks of explicit sets; the only real-arithmetic verdict used is the already-published (10, 5). Nothing here touches the exponent of h. Artefacts: verification/789/h28-29.

← our attempt log · problem #789 on the board