VibeMathedMath problems solved with AI
Sign in

Zak's modified integer round-down conjecture for the skiving stock problem

In the one-dimensional skiving stock problem (bin covering), items of given sizes are grouped into as many disjoint groups as possible, each group reaching a threshold LL; items may be left unused. The pattern linear programming relaxation gives an upper bound LPSSPLP_{\mathrm{SSP}} on the optimum OPTSSPOPT_{\mathrm{SSP}}. The integer round-down property OPTSSP=⌊LPSSP⌋OPT_{\mathrm{SSP}}=\lfloor LP_{\mathrm{SSP}}\rfloor fails, but the largest known gap LPSSP−OPTSSPLP_{\mathrm{SSP}}-OPT_{\mathrm{SSP}} was about 1.181.18. The modified integer round-down property (MIRDP) conjectures that every instance satisfies LPSSP−OPTSSP<2LP_{\mathrm{SSP}}-OPT_{\mathrm{SSP}}<2. Is that true?

Result
Disproved(see note)
Status
Candidate (review pending)
AI contribution
AI co-developed
Method
—
Field
Skiving stock and bin covering; pattern LP integrality gap
Posed by
E. J. Zak (2003), as cited by the manuscript; stated as an open conjecture by Martinovic and Scheithauer (Discrete Optimization 2016; Pesquisa Operacional 2019)
Year posed
2003
Years open
23y
Solved
2026-10-07
Model
Anthropic Fable 5.1 and OpenAI GPT-5.6 Sol Pro
Vendor
Anthropic / OpenAI
Collaborators
Eric Winnington
Verification
Unreviewed
Publication
Announced
Significance
14 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1: for every integer c≥0c\ge0 there is a rational instance with 5B5B items, sizes in (53/270,11/54)(53/270,11/54) for threshold 11, LPSSP=LPSSP,prop=BLP_{\mathrm{SSP}}=LP_{\mathrm{SSP,prop}}=B and OPTSSP≤B−c−1OPT_{\mathrm{SSP}}\le B-c-1; c=1c=1 refutes MIRDP with no rounding ambiguity. Theorem 2 and Corollary 3: fixed additive approximation is NP-hard. The result is conditional on OpenAI's bin-packing theorem (itself a Candidate here). Not shown: any growth rate of the gap in terms of instance size.

What the AI did

The manuscript's abstract and the repository README say the proof was generated by a combination of Anthropic Fable 5.1 and OpenAI GPT-5.6 Sol Pro; its closing note says ChatGPT assisted with drafting, literature organization and analysis of the proofs. The idea is a transfer: complement OpenAI's bin-packing instances (24 September 2026, which disprove the round-up analogue) by bi=2−aib_i=2-a_i with threshold 99. On 5B5B items with sizes above 1/61/6, feasible five-item packing and covering sets coincide, LP saturation carries the LP value BB across, and a covering deficit dd converts to a packing excess of at most ⌈3d/2⌉\lceil 3d/2\rceil. Result: for every c≥0c\ge0 an instance with LPSSP=BLP_{\mathrm{SSP}}=B and OPTSSP≤B−c−1OPT_{\mathrm{SSP}}\le B-c-1, also for the proper relaxation, and NP-hardness of every fixed additive approximation.

Verification

No independent mathematician has checked this yet. Checked here on 7 October 2026: the manuscript's TeX source was read in full. The transfer itself (Proposition 9, Theorems 6 and 7, Corollary 11 and the proof of Theorem 1) was checked by hand and is elementary: four items below 7/307/30 always pack and six complemented items always cover, so a covering deficit dd gives a packing excess at most ⌈3d/2⌉\lceil 3d/2\rceil; even without the 7/307/30 bound, singletons give 24d24d, so the conclusion follows from the exported Lean statement of OpenAI's theorem alone. A brute-force computation written here on 60 random 10-item instances (sizes near 1/51/5, matching deficiency 00 to 22) confirmed the exact formulas OPTBP−B=⌈h/4⌉OPT_{\mathrm{BP}}-B=\lceil h/4\rceil and B−OPTSSP=⌈h/6⌉B-OPT_{\mathrm{SSP}}=\lceil h/6\rceil in every case. The result depends on OpenAI's unbounded configuration-gap theorem, which is Lean-checked but not independently verified; the transfer is not formalised and nothing was rebuilt here.

Sources

Submitted by LucidStoat857 on

Changelog2 changes

Discussion