8
$\begingroup$

I am currently working on a computer formalization of the algebraic completeness of Conway's nimbers. However, I've found Conway's exposition to be a bit convoluted, and I'm having trouble filling in what I consider to be a gap in the proof.

The main result for the proof is Theorem 45 in On Numbers And Games (page 58). It states that if $\Delta \in \mathrm{ON}_2$ is a non-algebraically complete field (when considered as the set of the nimbers smaller than it), then it is the root of the lexicographically smallest polynomial

$$p = x^n + x^{n-1}\alpha_{n-1} + \cdots + \alpha_0$$

over $\Delta$ without a root in $\Delta$.

Conway first argues that for any lexicographically smaller polynomial (with the same degree) $q = x^n + x^{n-1}\beta_{n-1} + \cdots + \beta_0$, the value $(q + x^n)(\Delta)$ must be in the excludents of $\Delta^n$, while $(p + x^n)(\Delta)$ won't. That step seems fine to me.

Conway then argues that the values $\Delta^{n-1}\beta_{n-1} + \cdots + \beta_0$ evaluated with nimber addition and multiplication actually coincide with those evaluated with ordinal addition and multiplication. Thus, all ordinals with a base $\Delta$ expansion less than that represented by $p + x^n$ appear as excludents for $\Delta^n$ but $(p + x^n)(\Delta)$ doesn't, meaning $(p + x^n)(\Delta) = \Delta^n$ and thus $p(\Delta) = 0$.

But what justifies this correspondence between nimber operations and ordinal operations? It seems like the previous Theorem 44 attempts to do this, but that explicitly talks about $\Delta$ not forming a field, and even defines an auxiliary $\Gamma$ in terms of the smallest non-invertible nimber in $\Delta$. In any case, applying that theorem would require substituting $\Gamma = \Delta$, which is definitely incorrect, as it implies that evaluating polynomials over $\Delta$ as nimbers always corresponds to doing so as ordinals. This has the easy counterexample of $p = x^2$ and $\Delta = 2$.

Even more confusingly, the second edition of the book mentions that Theorem 44 is flawed, though the proof itself doesn't seem to acknowledge this.

What justifies this step in the argument? Is there any other published exposition of this proof that gives more detail?

$\endgroup$
0

1 Answer 1

6
$\begingroup$

[Converted from a comment into an answer, and expanded with a copy of the statement from Siegel's book.]

You may find clearer the proof given in Siegel, Combinatorial Game Theory (2013, AMS Graduate studies 146), chapter VIII, theorem 4.3 (generally speaking, I find Siegel's proofs easier to follow than Conway's). Specifically, the correspondence between nim and ordinal operations is justified in Siegel's lemma 4.4(c′): there does indeed appear to be a certain amount of inductive work that Conway omits.

For completeness of MathOverflow, here is the statement (slightly rephrased) of Siegel's lemma VIII.4.4(c′):

Let $\gamma$ be an ordinal. Suppose that $\mathcal{P}_\gamma := \{\alpha<\gamma\}$ is a field and that every polynomial of degree $\leq n$ has a nim-root in $\mathcal{P}_\gamma$. Then $$\bigoplus_{i=0}^n (\gamma^{\otimes i} \otimes \alpha_i) = \sum_{i=0}^n (\gamma^i \times \alpha_i)$$ for all $\alpha_0,\ldots,\alpha_n<\gamma$, where $\bigoplus,\otimes,(—)^{\otimes (—)}$ refer to the nim operations while $\sum,\times,(—)^{(—)}$ refer to the usual ordinal arithmetic operations [and the sum in the RHS is taken in decreasing order, i.e. $\gamma^n\times \alpha_n + \cdots + \gamma\times\alpha_1 + \alpha_0$].

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .