2
$\begingroup$

Conway constructed a field of characteristic 2 whose elements are the finite Nim values, indexed by the natural numbers. What is known about nontrivial automorphisms of this field? Do any of them correspond to arithmetically tractable bijections from the set of natural numbers to itself?

$\endgroup$
1
  • 1
    $\begingroup$ If multiplication is tractable then squaring is, and so every power of it is. $\endgroup$
    – Will Sawin
    Nov 18, 2021 at 3:49

1 Answer 1

4
$\begingroup$

The field of natural numbers under nim operations is precisely the quadratic closure $\mathbb{F}_{2^{2^\infty}}$ of $\mathbb{F}_2$, viꝫ. the inductive limit (“union”) of the subfields $\mathbb{F}_{2^{2^d}}$ given by the nim multiplication on the integers $0,\ldots,2^{2^d}-1$.

The Galois group $\operatorname{Gal}(\mathbb{F}_{2^{2^\infty}}/\mathbb{F}_2)$ of automorphisms of $\mathbb{F}_{2^{2^\infty}}$ is the projective limit of the Galois groups $\operatorname{Gal}(\mathbb{F}_{2^{2^d}}/\mathbb{F}_2)$ which are none other than the cyclic groups $\mathbb{Z}/2^d\mathbb{Z}$ generated by the Frobenius or “squaring” map $\sigma\colon x \mapsto x^2$ (which is of order precisely $d$ on $\mathbb{F}_{2^{2^d}}$); the map $\mathbb{Z}/2^d\mathbb{Z} \to \mathbb{Z}/2^{d'}\mathbb{Z}$ for $d'\leq d$ is, as one might expect, reduction mod $2^{d'}$. So this projective limit is $\mathbb{Z}_2$ (the $2$-adic integers), i.e., we have $\operatorname{Gal}(\mathbb{F}_{2^{2^\infty}}/\mathbb{F}_2) = \mathbb{Z}_2$, progenerated by $\sigma$, meaning that every automorphism of $\mathbb{F}_{2^{2^\infty}}$ can be described as $\sigma^z$ for some uniquely defined $2$-adic integer $z$ (we might write this as raising to the power $2^z$ but it's an abuse of notation).

Certainly the $\sigma^k$ for $k\in\mathbb{Z}$ are tractable, since they are just $x \mapsto x^{2^k}$. More generally, if $z$ is tractable as a $2$-adic integer, meaning we have some way to compute its residue $\bar z$ in $\mathbb{Z}/2^d\mathbb{Z}$, then we can compute $\sigma^z$, by applying $\sigma^{\bar z}$ whenever the given $x$ is in $\mathbb{F}_{2^{2^d}}$ (concretely on the nimbers: is $<2^{2^d}$ as a natural number).

As a very concrete example, $z = 1/3$ is certainly a tractable $2$-adic integer, so this gives an automorphism $\sigma^{1/3}$ which, when applied three times, is the squaring automorphism $\sigma$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.