TY - JOUR

T1 - Automata and finite order elements in the Nottingham group

AU - Byszewski, Jakub

AU - Cornelissen, Gunther

AU - Tijsma, Djurre

N1 - Funding Information:
JB was supported by National Science Center, Poland under grant no. 2016/23/D/ST1/01124. DT was supported in part by the research training group GRK 2240: Algebro-geometric Methods in Algebra, Arithmetic and Topology, funded by the DFG. We thank Jeroen Sijsling for advice on various computations, Jonathan Lubin for sharing his unpublished work on conjugacy classes in the Nottingham group, Andrew Bridy and Eric Rowland for many interesting discussions about implementations, and Jason Bell for some insightful discussions. We also thank Ragnar Groot Koerkamp for setting up a computer search for small automata. We also thank the reviewer for some pertinent suggestions that are reflected in Subsection 8.3 and Remark 12.2.3.
Funding Information:
JB was supported by National Science Center, Poland under grant no. 2016/23/D/ST1/01124 . DT was supported in part by the research training group GRK 2240 : Algebro-geometric Methods in Algebra, Arithmetic and Topology, funded by the DFG .
Publisher Copyright:
© 2022 The Author(s)

PY - 2022/7/15

Y1 - 2022/7/15

N2 - The Nottingham group at 2 is the group of (formal) power series t+a2t2+a3t3+⋯ in the variable t with coefficients ai from the field with two elements, where the group operation is given by composition of power series. The depth of such a series is the largest d⩾1 for which a2=…=ad=0. Only a handful of power series of finite order (forcedly a power of 2) are explicitly known through a formula for their coefficients. We argue in this paper that it is advantageous to describe such series in closed computational form through automata, based on effective versions of proofs of Christol's theorem identifying algebraic and automatic series. Up to conjugation, there are only finitely many series σ of order 2n with fixed break sequence (i.e. the sequence of depths of σ∘2i). Starting from Witt vector or Carlitz module constructions, we give an explicit automaton-theoretic description of: (a) representatives up to conjugation for all series of order 4 with break sequence (1,m) for m<10; (b) representatives up to conjugation for all series of order 8 with minimal break sequence (1,3,11); and (c) an embedding of the Klein four-group into the Nottingham group at 2. We study the complexity of the new examples from the algebro-geometric properties of the equations they satisfy. For this, we generalise the theory of sparseness of power series to a four-step hierarchy of complexity, for which we give both Galois-theoretic and combinatorial descriptions. We identify where our different series fit into this hierarchy. We construct sparse representatives for the conjugacy class of elements of order two and depth 2μ±1 (μ⩾1). Series with small state complexity can end up high in the hierarchy. This is true, for example, for a new automaton we found, representing a series of order 4 with 5 states (the minimal possible number for such a series).

AB - The Nottingham group at 2 is the group of (formal) power series t+a2t2+a3t3+⋯ in the variable t with coefficients ai from the field with two elements, where the group operation is given by composition of power series. The depth of such a series is the largest d⩾1 for which a2=…=ad=0. Only a handful of power series of finite order (forcedly a power of 2) are explicitly known through a formula for their coefficients. We argue in this paper that it is advantageous to describe such series in closed computational form through automata, based on effective versions of proofs of Christol's theorem identifying algebraic and automatic series. Up to conjugation, there are only finitely many series σ of order 2n with fixed break sequence (i.e. the sequence of depths of σ∘2i). Starting from Witt vector or Carlitz module constructions, we give an explicit automaton-theoretic description of: (a) representatives up to conjugation for all series of order 4 with break sequence (1,m) for m<10; (b) representatives up to conjugation for all series of order 8 with minimal break sequence (1,3,11); and (c) an embedding of the Klein four-group into the Nottingham group at 2. We study the complexity of the new examples from the algebro-geometric properties of the equations they satisfy. For this, we generalise the theory of sparseness of power series to a four-step hierarchy of complexity, for which we give both Galois-theoretic and combinatorial descriptions. We identify where our different series fit into this hierarchy. We construct sparse representatives for the conjugacy class of elements of order two and depth 2μ±1 (μ⩾1). Series with small state complexity can end up high in the hierarchy. This is true, for example, for a new automaton we found, representing a series of order 4 with 5 states (the minimal possible number for such a series).

KW - Automata theory

KW - Nottingham group

KW - Power series over finite fields

UR - http://www.scopus.com/inward/record.url?scp=85127490821&partnerID=8YFLogxK

U2 - 10.1016/j.jalgebra.2022.03.019

DO - 10.1016/j.jalgebra.2022.03.019

M3 - Article

AN - SCOPUS:85127490821

SN - 0021-8693

VL - 602

SP - 484

EP - 554

JO - Journal of Algebra

JF - Journal of Algebra

ER -