Optimal three-element postage-stamp bases with a negative element

Compare the largest covered interval of a three-element integer h-basis using exactly h summands when a negative element is required versus unrestricted bases. The stated pattern is a strictly smaller maximum for odd h or h=4, and equality for other even h.

Why it matters and what counts as progress

Why it matters: It asks whether negative denominations help or hinder interval coverage across this infinite family of small additive bases.

What counts as progress: Prove the optimal covered intervals for three-element h-bases in each parity case, with exactly h summands and the negative-element restriction retained.

How the problem developed

1937 · Problem formulation [1]
Hans Rohrbach Formalized the postage-stamp problem of maximizing the consecutive range representable with a bounded number of stamps.
1955 · Exact result [2]
Alfred Stöhr Determined the optimal three-denomination nonnegative h-basis range, n_h(2)=⌊(h²+6h+1)/4⌋.
14 Oct 2026 · Comparison result [3]
Wouter van Doorn, Pietro Monticone and Melvyn B. Nathanson; Aristotle For three-element h-bases containing a negative integer, proved the attainable range is smaller for odd h or h=4, and equal for even h≠4. The paper reports autonomous Lean discovery and verification.

AI contribution

Positivity and negativity for h-bases for n

Wouter van Doorn, Pietro Monticone, Melvyn B. Nathanson

The original comparisons for three-element integer h-bases with exactly h summands: requiring a negative element gives a strictly smaller maximal covered interval for odd h or h=4, and the same maximum for even h other than 4. These are Aristotle’s original proofs, not Nathanson’s replacement arguments.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationReported

Human understandingFull