Guy vs. Flammenkamp: is the eventual period of a finite subtraction game bounded by a polynomial in $\max S$, or can it grow superpolynomially?
Statement
For a finite subtraction set $S=\{s_1<s_2<\dots<s_n\}\subset\mathbb{Z}_{>0}$, the impartial subtraction game (a move removes some $s_i$ beans from the heap; normal play, last mover wins) has an eventually periodic nim-sequence $(\mathcal{G}(m))_{m\ge0}$. Two conjectures about how its eventual period grows with $\max S=s_n$ are in direct conflict. GUY: the period is bounded above by a polynomial in $s_n$ of degree at most $\binom{n}{2}$. FLAMMENKAMP: there exists a family of finite subtraction games whose eventual period grows exponentially in $s_n$. Decide the conflict -- in particular, does there exist a single plain (unseeded) finite subtraction set whose eventual nim-value period is superpolynomial in $\max S$?
Acceptance. FULLY RESOLVES (disproves Guy): a single explicit finite subtraction set $S\subset\mathbb{Z}_{>0}$ (plain, no terminal seed) together with a machine-verified eventual nim-value period exceeding every polynomial of degree $\binom{|S|}{2}$ in $\max S$ -- the certificate being the computed nim-sequence plus a verification that the claimed period holds past the recurrence horizon (finite and re-runnable). FULLY RESOLVES (toward Guy): a proof of Guy's degree-$\binom{n}{2}$ polynomial period bound for a fixed small cardinality $|S|=3$ or $|S|=4$. ADVANCES: a rigorous superpolynomial period lower bound for an unseeded parametrized family (e.g. proving the Althoefer-Bueltermann 5-move family has superpolynomial period), or a proof of the polynomial bound under a structural restriction (e.g. max-symmetric sets). Experimental period observations without a verified finite period certificate do NOT qualify.
Background
Both conjectures are recorded in Problem A1 (old number 1) of R. J. Nowakowski, 'Unsolved problems in combinatorial games' (Games of No Chance 5, MSRI Publ. 70, 2017, p. 127): 'Guy conjectures that they are bounded by polynomials of degree at most (n choose 2) in s_n.' The opposing Flammenkamp conjecture -- a sequence of finite-ruleset subtraction games with exponential eventual period in $\max S$, from his 1997 Bielefeld thesis -- is stated as Conjecture 1 in the 2025 survey by U. Larsson and I. Saha, 'A brief conversation about subtraction games' (Games of No Chance 6, MSRI Publ. 71, 2025 = arXiv:2405.20054), which reports it OPEN: experiments on 'max-symmetric' size-5 sets show period $\sim 2^{0.3\,\max S}$ for $61\le\max S\le117$, but no proof either way. It remains open as of March 2026: Larsson-Manabe, 'Additive Subtraction Games' (arXiv:2603.10414), footnote 1, treats Flammenkamp's exponential-period conjecture as an unresolved conjecture. CRUCIAL scoping (do not mistake for a resolution): S. Miklos and I. Z. Post, 'Superpolynomial period lengths...' (arXiv:2312.02426 = Int. J. Game Theory 53(4):1275-1313, 2024), prove superpolynomial period ONLY for a 'terminal-seed' GENERALIZATION and only for OUTCOMES (not nim-values): they exhibit size-3 sets $\{n,4n-1,4n^2\}$ equipped with a chosen P/N terminal seed; a seed cannot change the period for $|A|\le2$ but can for $|A|\ge3$. That is not a plain finite subtraction game, so it does NOT decide Guy vs Flammenkamp. No plain (unseeded) finite subtraction game with superpolynomial period has ever been exhibited; Althoefer-Bueltermann only conjecture superpolynomiality of the 5-move family $\{a,8a,30a+1,37a+1,38a+1\}$. Proven scaffolding: Golomb's $2^{\max S}$ trivial bound; Flammenkamp's improved $2\varphi^{\max S}$ bound (for sets with $s_i+s_j\le\max S$) and his theorem that max-symmetric sets are purely periodic. Vetted open as of 2026-07-06; genuinely contested (~35 years).
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.