Title: Additive Sink Subtraction
Speaker: Urban Larsson, IEOR, IIT Bombay; co-authors A. Bhagat, H. Manabe, T. Yamashita
Keywords: Additive Game; Nimber; Periodicity; Sink Convention; Subtraction Game.
Abstract
Subtraction games belong to the folklore of Combinatorial Game Theory (CGT). In particular, a classical result of Golomb (1966) shows that every subtraction game with a finite move set has an eventually periodic nimber sequence. From this perspective, subtraction games are often regarded as “solved”. However, this result provides only an exponential upper bound on the period length, while most studied rulesets have polynomial (small degree) period lengths. Very few general results are known concerning explicit formulas for given ruleset families. Through extensive computational experiments, remarkably, Flammenkamp (PhD thesis, 1996) identifies subtraction sets S with as few as five moves whose outcome-period lengths appear to grow as large as ∼2^{0.3 max S}. He also formulates a conjecture for three-move subtraction games, for which a striking experimental classification emerges: non-additive sets exhibit linear period lengths of the form “the sum of two moves”, although the choice of which two moves displays fractal-like behavior, whereas additive sets S = {a, b, a + b} have purely periodic outcomes with conjectured linear or quadratic period lengths. Additive subtraction games receive special attention already in Winning Ways (1982), where a specific family with linear period lengths is solved. However, contrary to a statement in Flammenkamp’s thesis, to the best of our knowledge the general additive case in the standard setting remains open (see also Ward’s more recent arXiv post).
In this talk, we introduce and analyze a dual setting, which we call sink subtraction. In contrast to the standard “wall” convention, where moves to negative positions are forbidden, the sink convention declares a player the winner as soon as they move to any non-positive position (normal play). This winning convention has not yet received much attention, except for a related generalization appearing in Miklós et al. (2024), where three-move games under specific terminal “seeds” are shown to attain super-polynomial, though still sub-exponential, period lengths. A fundamental structural difference is that the wall convention enforces finite play, whereas the sink convention allows circular play for finite sinks; see Bhagat’s talk at this conference. In celebration of this added generality, we demonstrate that additive sink subtraction, with an infinite sink, admits a complete solution: the nimber sequence is purely periodic with an explicit (linear or) quadratic period formula. Strikingly, this formula exhibits “dual” properties to the conjectured period formula for additive wall subtraction; see Manabe’s talk at this conference.