Multiplicative Modular Nim (MuM)
Satyam Tyagi · 2025
Read Multiplicative Modular Nim (MuM) by Satyam Tyagi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08830.txt.
Introduction
Satyam Tyagi builds a new form of the game Nim in a 2025 paper. In Nim, players take objects from heaps, and classic play rests on a sum rule. In this version, heap sizes are multiplied and then reduced by a set number, which changes how positions are judged.
Tyagi defines a game value for each position and proves it matches the heap product. When games are joined, values multiply rather than add as in the classic game. For joined numbers, a known math rule splits play into parts. He then extends the game to a field used in code work, with a fixed heap model to keep the rules sound.
Catalog record
| CREATOR | Satyam Tyagi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08830
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multiplicative Modular Nim (MuM) Satyam Tyagi Abstract We introduce Multiplicative Modular Nim (MuM), a variant of Nim in which the traditional nim-sum is replaced by heap-size multiplication modulo m m . We establish a complete theory for this game, beginning with a direct, Bouton-style analysis for prime moduli. Our central result is an analogue of the Sprague-Grundy theorem, where we define a game-theoretic value, the mumber , for each position via a multiplicative mex recursion. We prove that these mumbers are equivalent to the heap-product modulo m m , and show that for disjunctive sums of games, they combine via modular multiplication in contrast to the XOR-sum of classical nimbers. For composite moduli, we show that MuM decomposes via the Chinese Remainder Theorem into independent subgames corresponding to its prime-power factors. We extend the game to finite fields 𝔽 ( p n ) \mathbb{F}(p^{n}) , motivated by the pedagogical need to make the algebra of the AES S-box more accessible. We demonstrate that a sound game in this domain requires a Canonical Heap Model to resolve the many-to-one mapping from integer heaps to field elements. To our knowledge, this is the first systematic analysis of a multiplicative modular variant of Nim and its extension into a complete, non-additive combinatorial game algebra. Keywords: Combinatorial Game Theory, Impartial Games, Nim, Modular Arithmetic, Finite Fields MSC Classification: 91A46, 11A07 ACM Classification: G.2.1 Combinatorics 1 Introduction Classical Nim is a cornerstone of combinatorial game theory, with a simple structure and a deep strategy grounded in the binary XOR operation [ 2 ] . In this work, we explore a multiplicative analogue of Nim where the game state evolves through modular multiplication rather than the usual nim-sum. This seemingly simple change leads to a rich new game, Multiplicative Modular Nim (MuM), that introduces players to field-like behavior in a playful setting. Our analysis proceeds in stages of increasing generality. We begin with a direct, Bouton-style analysis to establish the winning strategy for prime moduli. We then build a more general, Sprague-Grundy-style theory that holds for any modulus m . We define a mumber for each position using a multiplicative mex recursion and prove constructively that this value is equivalent to the product of heaps modulo m . This demonstrates that the modular-product rule is not merely an imposed condition, but an emergent property of the game’s underlying combinatorial structure. We then apply this general theory to analyze the structure of games with composite moduli, showing how the Chinese Remainder Theorem allows for their decomposition into independent subgames corresponding to their prime-power factors. This framework naturally leads to our original motivation: creating a pedagogical bridge to the algebra of finite fields, particularly the field \mathbb{F}(2^{8}) used in the AES S-box. We define a final extension, Polynomial MuM , and show that a sound game in this domain requires a Canonical Heap Model to resolve the complex mapping between integer heaps and field elements. The resulting game provides a playable model whose optimal strategy requires precisely the field-multiplication and inversion operations that underpin modern cryptography. 2 Literature Review 2.1 ”Mod-m” Addition Variants Work on Nim-like games with modular invariants has a rich history, yet it has focused exclusively on additive structures. • [ 8 ] explored games where heap sizes are reduced modulo m by subtraction. This was extended by Fraenkel, Jaffray, Kotzig & Sabidussi, who coined the term ”Modular Nim” and proved the existence of periodic Sprague-Grundy patterns [ 6 ] . • More recent work by [ 10 ] and [ 7 ] has established further properties of these additive modular games, such as periodicity theorems and explicit computation of nim-values for various move-sets. All of these foundational papers explore invariants based on modular addition or subtraction; none use a product-based invariant. 2.2 Multiplicative Structures in Impartial Games Multiplication has appeared in combinatorial game theory, but typically as a secondary structure built upon the primary additive (nim-sum) framework. • Lenstra, in foundational work, defined nim-multiplication , proving that the set of nimbers forms a field under nim-sum and this new product [ 9 ] . This established a precedent for embedding field structures into game analysis. • Conway’s analysis of ”Turning Corners” uses the nim-product of coordinates to determine the nim-value of a position, but the winning strategy still relies on computing the nim-sum of these products [ 5 ] . • Other games feature multiplication in their move sets, such as replacing a number with one of its proper factors [ 3 ] , but not as the core invariant determining the game’s outcome. To our knowledge, no prior work uses modular multiplication as the primary winning invariant, nor does it develop a corresponding non-additive game algebra. MuM fills this previously unstudied niche at the intersection of modular arithmetic and impartial game theory. 3 Multiplicative Modular Nim (MuM) 3.1 Game Definition for Prime Moduli We first define the game for a prime modulus p , where the algebraic structure is a field. Definition 3.1 (MuM for Prime Moduli) . • Game Play: The game is played with n heaps, each containing a positive integer value. A fixed prime number p is chosen at the start. • Heap Constraint: No heap is allowed to hold a value divisible by p (i.e., for any heap h_{i} , h_{i}\not\equiv 0\pmod{p} ). • Legal Move: A player chooses any heap h_{i}>1 and replaces it with h_{i}^{\prime}=h_{i}-r , where the integer r satisfies: 1. 1\leq r<p (the amount subtracted is less than the modulus); 2. r<h_{i} (the heap strictly decreases); 3. The new heap h_{i}^{\prime} is not divisible by p . 3.2 A Bouton-Style Analysis for Prime Moduli The win/loss condition is determined by the product of the heaps modulo p . A position H with product P=\prod h_{i} is a losing position if P\equiv 1\pmod{p} and a winning position if P\not\equiv 1\pmod{p} . The following propositions establish a complete winning strategy. Proposition 3.2 (Winning to Losing) . If a position has product P\not\equiv 1\pmod{p} and at least one heap satisfies h_{j}>p , then there exists a legal move to a losing position. Proof. Let P=h_{j}\cdot m where m=\prod_{i\neq j}h_{i} . Because all heaps are coprime to p , so is m . Thus, its inverse m^{-1}\pmod{p} exists. The player chooses r\equiv h_{j}-m^{-1}\pmod{p} . Since h_{j}>p>m^{-1} , the move h_{j}\to h_{j}-r is a legal reduction. The new product is P^{\prime}=(h_{j}-r)m\equiv m^{-1}m\equiv 1\pmod{p} . ∎ Proposition 3.3 (Losing to Winning) . If a position has product P\equiv 1\pmod{p} and is non-terminal, every legal move leads to a winning position. Proof. Let m=\prod_{i\neq j}h_{i} . The initial state has h_{j}m\equiv 1\pmod{p} . A move h_{j}\to h_{j}-r results in a new product P^{\prime}=(h_{j}-r)m . If P^{\prime}\equiv 1\pmod{p} , then by subtracting the congruences, we get -rm\equiv 0\pmod{p} . Since m is invertible, this implies r\equiv 0\pmod{p} , which contradicts the move rule 1\leq r<p . ∎ 3.3 Stranded Positions and Consolidation When all heaps are smaller than p , a winning position may be stranded , meaning no legal move can reach a losing state. For example, with p=5 , the position [2,2,2] has product P\equiv 3\pmod{5} (winning), but every move results in a product of 4\pmod{5} . To ensure termination,