Periodic binary harmonic functions on lattices

A function on a (generally infinite) graph Γ with values in a field K of characteristic 2 will be called harmonic if its value at every vertex of Γ is the sum of its values over all adjacent vertices. We consider binary pluri-periodic harmonic functions on integer lattices, and address the problem of describing the set of possible multi-periods of such functions. This problem arises in the theory of cellular automata [O. Martin, A.M. Odlyzko, S. Wolfram, Algebraic properties of cellular automata, Comm. Math. Phys. 93 (1984) 219–258; K. Sutner, On σ-automata, Complex Systems 2 (1988) 1–28; K. Sutner, The σ-game and cellular automata, Amer. Math. Monthly 97 (1990) 24–34; J. Goldwasser, W. Klostermeyer, H. Ware, Fibonacci polynomials and parity domination in grid graphs, Graphs Combin. 18 (2002) 271–283]. It happens to be equivalent to determining, for a certain affine algebraic hypersurface Vs in , the torsion multi-orders of the points on Vs in the multiplicative group . In particular V2 is an elliptic cubic curve. In this special case we provide a more thorough treatment. A major part of the paper is devoted to a survey of the subject.