A380496 Lenstra excess of the n-th odd prime.

0, 0, 1, 1, 0, 0, 4, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 4, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0

Offset: 1

Author

Aaron N. Siegel, Jan 21 2025

Keywords

• nonn
• hard
• more

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

Examples

			For n <= 4 the corresponding ordinals alpha_p are:
  alpha_3 = 2,
  alpha_5 = 4,
  alpha_7 = w + 1,
  alpha_11 = w^w + 1.
		

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

• Combinatorial Game Suite
• neverendingbooks, On2, Extending Lenstra's List, January 27 2009.