×

A singular quartic curve over a finite field and the trisentis game. (English) Zbl 1218.05104

Summary: The Trisentis game consists of a rectangular array of lights each of which also functions as a toggle switch for its (up to eight) neighboring lights. The lights are OFF at the start, and the object is to turn them all ON. We give explicit formulas for the dimension of the kernel of the Laplacian associated to this game as well as some variants, in some cases, by counting rational points of the singular quartic curve \((x+x^{ - 1}+1)(y+y^{ - 1}+1)=1\) over finite fields. As a corollary, we have an affirmative answer to a question of Clausing whether the \(n\times n\) Trisentis game has a unique solution if \(n=2-4^{k}\) or \(n=2-4^{k} - 2\).

MSC:

05C57 Games on graphs (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
11G20 Curves over finite and local fields
14G15 Finite ground fields in algebraic geometry
31C20 Discrete potential theory
91A46 Combinatorial games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barua, Rana; Ramakrishnan, S., \(σ\)-game, \( \sigma^+\)-game and two-dimensional additive cellular automata, Theoret. Comput. Sci., 154, 2, 349-366 (1996) · Zbl 0872.68121
[2] Clausing, Achim, Das Trisentis-Spiel, Math. Semesterber., 48, 1, 49-66 (2001) · Zbl 0999.91013
[3] Goshima, Masato; Yamagishi, Masakazu, Two remarks on torus lights out puzzle, Adv. Appl. Discrete Math., 4, 2, 115-126 (2009) · Zbl 1177.05071
[4] Masato Goshima, Masakazu Yamagishi, On the dimension of the space of harmonic functions on a discrete torus, Experiment. Math. 19 (4) (2010), in press.; Masato Goshima, Masakazu Yamagishi, On the dimension of the space of harmonic functions on a discrete torus, Experiment. Math. 19 (4) (2010), in press. · Zbl 1292.11134
[5] Gravier, Sylvain; Mhalla, Mehdi; Tannier, Eric, On a modular domination game, Theoret. Comput. Sci., 306, 1-3, 291-303 (2003) · Zbl 1060.68076
[6] Hunziker, Markus; Machiavelo, António; Park, Jihun, Chebyshev polynomials over finite fields and reversibility of \(σ\)-automata on square grids, Theoret. Comput. Sci., 320, 2-3, 465-483 (2004) · Zbl 1068.68089
[7] Joyner, David, Adventures in Group Theory. Rubikʼs Cube, Merlinʼs Machine and Other Mathematical Toys (2002), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1117.00002
[8] Rivlin, Theodore J., Chebyshev Polynomials. From Approximation Theory to Algebra and Number Theory, Pure Appl. Math. (N. Y.) (1990), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York · Zbl 0734.41029
[9] Sarkar, Palash; Barua, Rana, Multidimensional \(σ\)-automata, \(π\)-polynomials and generalised \(S\)-matrices, Theoret. Comput. Sci., 197, 1-2, 111-138 (1998) · Zbl 0902.68125
[10] Sutner, Klaus, The \(σ\)-game and cellular automata, Amer. Math. Monthly, 97, 1, 24-34 (1990) · Zbl 0797.68122
[11] Sutner, Klaus, \(σ\)-automata and Chebyshev-polynomials, Theoret. Comput. Sci., 230, 1-2, 49-73 (2000) · Zbl 0947.68540
[12] Zaidenberg, Mikhail, Periodic binary harmonic functions on lattices, Adv. in Appl. Math., 40, 2, 225-265 (2008) · Zbl 1165.11019
[13] Zaidenberg, Mikhail, Convolution equations on lattices: periodic solutions with values in a prime characteristic field, (Geometry and Dynamics of Groups and Spaces. Geometry and Dynamics of Groups and Spaces, Progr. Math., vol. 265 (2008), Birkhäuser: Birkhäuser Basel), 721-742 · Zbl 1183.11076
[14] Zaidenberg, Mikhail, Periodic harmonic functions on lattices and points count in positive characteristic, Cent. Eur. J. Math., 7, 3, 365-381 (2009) · Zbl 1243.37013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.