OFFSET
1,7
COMMENTS
In Combinatorial Game Theory, the nim product of two ordinals is defined by:
a*b = the least ordinal not equal to any a*b' + a'*b + a'*b' with a' < a, b' < b.
Here + is nim addition (binary xor). With this definition, the ordinals form a Field ON_2 of characteristic 2.
Conway showed that under nim addition and nim multiplication, the ordinals below w^w^w form an algebraic and algebraically closed subfield of ON_2, i.e., they form the algebraic closure of {0,1}. (Here w = omega = the least infinite ordinal.) Conway moreover gave a description of the arithmetic of ordinals below w^w^w. This arithmetic depends on calculating a particular ordinal alpha_p for each odd prime p: specifically, if p is the (n+1)-st odd prime, then alpha_p is defined to be the p-th nim-power of w^w^n. It is always the case that alpha_p < w^w^n.
Lenstra later showed that for each such p, there is a particular ordinal kappa_{f(p)} (following Lenstra's notation) such that alpha_p = kappa_{f(p)} + m_p for some integer m_p >= 0. This integer m_p is the Lenstra excess of p. It is usually 0 or 1, with the only other observed values for p <= 281 being m_19 = m_163 = 4.
Lenstra gave an algorithm for calculating m_p, but the values are in general quite hard to compute. The calculation depends on carrying out operations in the finite subfield F_p of ON_2 generated by w^w^n. The size of F_p is always 2^(e_p) for some integer e_p (the Lenstra exponent of p). The running time of Lenstra's algorithm is on the order of O(e_p^3), and the values of e_p, while erratic, tend to grow exponentially in p. For p <= 281 the largest exponent is e_263 = 102180; whereas for p = 283 (the least prime for which m_p is unknown as of January 2025), we have e_283 = 237820.
The latest version of CGSuite implements the arithmetic of w^w^w and includes Scala code for calculating the values of m_p and alpha_p.
a(1)-a(3): John H. Conway
a(4)-a(13): Hendrik W. Lenstra
a(14)-a(18): Lieven Le Bruyn
a(19)-a(59): Aaron N. Siegel
From Django Peeters, Oct 24 2025: (Start)
The only other observed values of m_p, besides 0 or 1, are m_19 = m_163 = m_1459 = 4.
For p <= 709 the largest exponent is e_659 = 4994220; whereas for p = 719 (the least prime for which m_p is unknown as of October 2025), we have e_719 = 1258230380.
a(60)-a(126): Django Peeters (a(68), a(71), a(75), a(90), a(91), a(101), a(106), a(116) and a(119) in a joint effort with Tristan Figueroa-Reid). (End)
REFERENCES
John H. Conway, On Numbers and Games, second edition. A K Peters, Ltd. / CRC Press, Natick, MA, 2001.
Hendrik W. Lenstra, On the algebraic closure of two, Proc. Kon. Ned. Akad. Wet. Series A 80 (1977), 389-396
Aaron N. Siegel, Combinatorial Game Theory. Number 146 in Graduate Studies in Mathematics. American Mathematical Society, 2013.
LINKS
Django Peeters, Table of n, a(n) for n = 1..126
neverendingbooks, On2, Extending Lenstra's List, January 27 2009.
Django Peeters, C++ port of Lenstra excess calculator from CGSuite
Django Peeters, Table of n, a(n) for n = 1..1417 (with question marks at the unknown entries)
Aaron N. Siegel, Combinatorial Game Suite
EXAMPLE
For n <= 4 the corresponding ordinals alpha_p are:
alpha_3 = 2,
alpha_5 = 4,
alpha_7 = w + 1,
alpha_11 = w^w + 1.
CROSSREFS
KEYWORD
nonn,hard
AUTHOR
Aaron N. Siegel, Jan 21 2025
EXTENSIONS
a(60) onward from Django Peeters, Oct 23 2025
STATUS
approved