Lights Out Puzzle in p p Colors: Evolution of Quiet Patterns

Wisdom Boinde, Igor Minevich, and Dipesh Poudel · 2025

Read Lights Out Puzzle in p p Colors: Evolution of Quiet Patterns by Wisdom Boinde, Igor Minevich, and Dipesh Poudel (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-2510-23677.txt.

Introduction

Wisdom Boinde and two co-authors study quiet patterns in the Lights Out puzzle, now in many colors. The classic puzzle is a grid where pressing a square flips its light and its neighbors' lights. A quiet pattern is a set of presses that changes nothing in the end, a kind of self-canceling combination. Here each square can sit in one of p states, where p is prime.

The authors show how to grow quiet patterns from small grids into grids p times larger, an evolution step across scales. Using elliptic curves, they prove a reverse step, de-evolution, also exists for most primes. They further describe every way to press a grid so that only five squares — the fewest possible — end in a nonzero state. The work links a recreational puzzle to deep tools from number theory.

Catalog record

CREATORWisdom Boinde, Igor Minevich, and Dipesh Poudel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-23677

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lights Out Puzzle in p p Colors: Evolution of Quiet Patterns Wisdom Boinde, Igor Minevich, and Dipesh Poudel Abstract The Lights Out Puzzle represents a cellular automaton based on a grid of squares where clicking a square changes its state and the states of surrounding squares. A “quiet pattern” is a way to click such that in the end, no change is effected. We introduce a way to “evolve” quiet patterns in smaller grids into ones in p p times larger grids when the number of possible states of a square is a prime p p . Using elliptic curves, we also find that an inverse “de-evolution” exists for most p p . We also describe the only ways to click a grid of squares such that only 5 (the minimum) number of squares have a nonzero state. 1 Introduction The Lights Out Puzzle began as an electronic game made in 1995 by Tiger Electronics, where a more-or-less random stored pattern of lights in a 5\times 5 grid would be turned on. Pressing any button would switch the state of the light on that button (between on and off), but also the lights horizontally and vertically adjacent to it, and the player needed to turn all the lights off. Since then, several variants of the puzzle have been explored, not only to sizes M\times N ( Scherphuis 2022 ) but to various graphs and numbers of colors (rather than just on and off) ( Edwards et al. 2010 ; Kreh 2017 ) , where the rules dictate that each vertex has a “state” (i.e. color) in \mathbb{Z}/k\mathbb{Z} , where k is the number of colors, and when a vertex is clicked, its own state and the state of the adjacent vertices are changed by +1\pmod{k} . The reader can try out the puzzle and many such variants online at https://tiny.one/lights , https://www.jaapsch.net/puzzles/lights.htm#java , and many other places. Recently, we have also started exploring the generalization where the state of a vertex is represented by an element of a group G , and clicking a vertex with a specified element g\in G multiplies the states of it and adjacent vertices by g on the right ( Cunningham and Minevich 2025a ; Cunningham and Minevich 2025b ) . In these papers, we have shown many graphs, including grid graphs, cylinders, and tori, as well as any possible higher-dimensional generalization of these except for odd-dimensional cubes essentially reduce to working with an abelian group G , which, if finitely generated, can itself be broken down into studying the puzzle over \mathbb{Z} and \mathbb{Z}/k\mathbb{Z} for prime-power k . In essence, in all these settings, a “click” is a linear operation that adds 1’s to the states of certain vertices. More precisely, we can collect the states of all the squares of the puzzle (or all the vertices if we want to be most general) in a state vector . Then a “click” is simply a linear operation that adds a vector of 1’s and 0’s to that state vector. If we put the vectors of 1’s and 0’s that represents clicking the j -th vertex in the j -th column of a matrix A , then the effect of a click vector \vec{v} (representing the vertices we want to click and how many times we want to click them) is simply to add A\vec{v} to the current state vector. The reader will note that this matrix A=A_{M,N} , which we call the activation matrix for the M\times N puzzle, is just the adjacency matrix of the graph plus the identity matrix (since vertices affect themselves). In particular, the Lights Out question asks if we can find a vector \vec{v} such that A\vec{v} such that \vec{1}+A\vec{v}=\vec{0} (where \vec{1} and \vec{0} are the vectors of all 1’s and all 0’s, respectively). This is obviously equivalent to solving the matrix equation A\vec{v}=\vec{1} , which always has a solution when there are 2 colors ( Sutner 1989 ) , but not always when there are more colors, e.g. there is no solution with k=3 to the 2\times 2 puzzle. The number of solutions is the same as the number of vectors in the null space of A , i.e. the number of vectors \vec{v} for which A\vec{v}=\vec{0} . We call the latter vectors quiet patterns , as Jaap did in ( Scherphuis 2022 ) , because adding the clicks in a quiet pattern to any preset clicks does not change the resulting states of the board; we can always quietly sneak these in. Example 1.1 . The matrix A below is the activation matrix A_{2,3} for the 2\times 3 grid, if we order the grid by going through the first row (left to right) and then the second row. A=\begin{pmatrix}1&1&0&1&0&0\\ 1&1&1&0&1&0\\ 0&1&1&0&0&1\\ 1&0&0&1&1&0\\ 0&1&0&1&1&1\\ 0&0&1&0&1&1\\ \end{pmatrix},\qquad\vec{q}=\begin{pmatrix}1\\ 1\\ 1\\ 0\\ 1\\ 0\end{pmatrix},\qquad\vec{r}=\begin{pmatrix}1\\ 1\\ 0\\ 1\\ 1\\ 0\end{pmatrix},\qquad\vec{s}=\begin{pmatrix}1\\ 0\\ 0\\ 0\\ 0\\ 1\end{pmatrix} Now the vector \vec{q} above forms a quiet pattern (the leftmost in Figure 1 ) since A\vec{q}=\vec{0} ; \vec{s} forms a solution vector for the 2-color puzzle since A\vec{s}=\vec{1}\pmod{2} ; and \vec{r} gives a solution vector to A\vec{v}=\vec{1} for any k -color puzzle. In Figure 1 , we have displayed the nontrivial quiet patterns for the 2-color 2\times 3 Lights Out Puzzle, not as 6\times 1 vectors but as 2\times 3 grids where the numbers denote how many times each square is clicked. 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 1 Figure 1: The nontrivial quiet patterns for the 2-color 2\times 3 puzzle. The 2-color quiet patterns are also called parity patterns by Knuth (see ( Knuth et al. 2008 ) for two interesting related problems and solutions) because for any square in the grid, the sum of the number in it and the numbers in the squares horizontally or vertically adjacent is even. A parity pattern is called perfect if there is no zero row or column in it, so in Figure 1 , the left and middle ones are perfect and the right one is not. Using the idea of the mikado diamond introduced in ( Eriksson et al. 2001 ) , Knuth showed ( Knuth 2011 ) that a quiet pattern for an M\times N 2-color puzzle can be “evolved” into a (2M+1)\times(2N+1) quiet pattern. The construction essentially replaces each square in the former pattern by a 3\times 3 square, whose centers are now exactly 1 space apart. A former 0 is replaced by an all-zero 3\times 3 square, and a former 1 is replaced by a ‘+’ pattern of 1’s, and then any overlapping ‘+’ patterns are superimposed and the numbers in them added where they intersect – see Section 2 for more details. The quiet patterns from Figure 1 evolve to the ones in Figure 2 , and here we see just one demonstration of a general fact that perfect parity patterns evolve into perfect ones; imperfect ones certainly evolve into imperfect ones. 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1

Read the complete text