Paperlane

no. 15 · Monday 16 November 2026

Positive Dual Certificates for Real Separated Subset Sums: Chamber Optimality of the Conway-Guy and Bohman Sets, and Exact Values up to Eight

Esther Notik

math.CO · 14 pp

Abstract

Let $f_R(n)$ be the least possible largest element of a set of $n$ positive reals whose $2^n$ subset sums are pairwise at least 1 apart, and let $f_Z(n) \ge f_R(n)$ be the corresponding integer quantity of the Erdős distinct subset sums problem. Fixing the signs of all signed relations $\varepsilon\cdot x$, $\varepsilon \in \{-1,0,1\}^n$, decomposes the real problem into polyhedral chambers, on each of which it is a linear program. We prove that for every $n$ the Conway-Guy set is the unique optimum of its chamber. The proof is an explicit positive dual certificate consisting of $n$ signed relations that are tight at the Conway-Guy set and unit lower triangular in gap coordinates; the relations are described by blocks of consecutive coordinates together with the positions $n - k(k+1)/2$, and tightness reduces to an identity of the Conway-Guy sequence proved by induction. We then show, by a branch-and-bound over chambers in which every leaf carries an exact rational certificate, that $f_R(n) = f_Z(n)$ for all $n \le 8$; in particular $f_R(7) = 44$ and $f_R(8) = 84$. We then prove the same for both of Bohman's families, which first improve on Conway-Guy at $n = 12$ ($1159 < 1164$): every Bohman set is the unique optimum of its chamber, with a block-triangular certificate given by explicit formulas. Finally we exhibit chambers whose optimal vertex is not an integer point.

comments
14 pages. Certificate data and checking programs: https://doi.org/10.5281/zenodo.23315221
fields
Combinatorics
pdf ↗ page arXiv:2611.17360 ↗