home | index | units | counting | geometry | algebra | trigonometry | calculus | functions
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics
+  0  1  2  3 
 0  0123
 1  1032
 2 2301
 3 3210
´  0  1  2  3 
 0  0000
 1  0123
 2 0231
 3 0312

Final Answers
© 2000-2023   Gérard P. Michon, Ph.D.

Fields

In France, about 1830, a new star of unimaginable brightness
appeared in the heavens of pure mathematics:   Evariste Galois
.
Felix Klein  (1849-1925)
 Michon
 

On this site, see also:

 Evariste Galois 
 (1811-1832)
I need all my courage to die at 20.
Evariste Galois  (1811-1832

Related Links (Outside this Site)

Wikipedia:   Field (mathematics)
The Evariste Galois Archives
 
border
border

Fields  (and Skew Fields)


(2006-03-16)   A Vocabulary Issue
Is a "field" a type of  skew field  like "tea" is a type of  leaf tea ?

At the very least, the analogy  (attributed to bourbakist  Roger Godement)  is amusing.  It deserves much better consideration than what it received when somebody  (Robinh)  kindly posted it within the Wikipedia article defining a  division ring,  only to see the remark hastily dismissed as "patent nonsense".

Well, no matter how you slice it, a qualifier which  widens  the scope of whatever it qualifies results in a confusing expression, unless it's recognized as an idiom...  Scientific locutions which go against common usage aren't helpful and a concerned scientist like Godement  (who isn't a native speaker of English)  has every right to be disturbed when the  lingua franca  of Science  is butchered this way.

A number of noted authors have used  (albeit fleetingly)  the term  skew field  as synonymous with the inclusive concept of  division ring  (commutative or not).

We argue that the term  skew field  should only designate a  noncommutative  division ring  (the only popular example consists of Hamilton's  quaternions).  To many of us, a  division ring  is  either  a  field  or a  skew field.  However, because this is not universally accepted, it's best to use the locution  "skew field"  only in special contexts where noncommutativity is otherwise clearly stated...


 Niels Abel 
 (1802-1829) (2006-03-16)   Fields
Commutative rings in which all nonzero elements are invertible.

Although it's just based on the ancient rules of ordinary arithmetic, the  field  concept emerged as such only when the Norwegian  Niels Henrik Abel (1802-1829) and the Frenchman  Evariste Galois (1811-1832) where led to consider  finite fields  in their independent investigations concerning the impossibility of solving "by radicals" a general polynomial of degree greater than 4.  This had been  the  central problem of Algebra ever since Renaissance Italian algebraists gave solutions  by radicals  for equations of the third and fourth degree.

The groundwork for the successful investigations of Abel and Galois was laid by the forefathers of group theory, starting with the first paper ever published by Alexandre-Theophile Vandermonde (1735-1796) :  Mémoire sur la résolution des équations (1770).  This introduced the clever idea of investigating functions which are invariant under the permutations of a polynomial's roots, which Joseph-Louis Lagrange (1736-1813) would soon build on.  Paolo Ruffini (1765-1822) proposed an incomplete proof of what's now called the "Abel-Ruffini theorem".

Fields  became a primary focus of investigation in their own right with the joint work of Leopold Kronecker (1823-1891) and Richard Dedekind (1831-1916).  Ernst Steinitz  (1871-1928)  published an axiomatic definition of fields in 1910:

field  is a  commutative ring  in which every element but "zero"  (the neutral element for addition)  has a multiplicative inverse  (a reciprocal).  This means that the properties listed below hold for "addition" and "multiplication", which are otherwise only assumed to be  well defined  internal operations  (this is to say that a sum or a product of two elements of the field is also an element of the field).

The Field Axioms   (multiplicative commutativity isn't required in a  division ring)
"x "y "z AdditionMultiplication
Associativity x + (y + z)  =  (x + y) + z x (y z)  =  (x y) z
Commutativity x + y  =  y + x x y  =  y x
Neutral Elements x + 0  =  x x 1  =  x
Invertibility " x,  $(-x),   x + (-x)  =  0 " x¹0, $ x-1,   x x-1  =  1
Distributivity x (y + z)   =   x y  +  x z     and(*)     (x + y) z   =   x z  +  y z

(*)   Both sides of the distributivity law are shown, so that the table remains correct for a  division ring  with just the deletion of the (highlighted) entry concerning multiplicative commutativity.  Two-sided versions of the other multiplicative properties can be derived from their one-sided counterparts  without  assumming commutativity  (see elsewhere on this site for a proof).

The terms  commutative  and  distributive  (French:  commutatif & distributif)  were both introduced in a memoir of Joseph Servois (1768-1847) published in the  Annales de Gergonne  (5:4, October 1, 1814).

Associativity  was so named by  W.R. Hamilton  in 1843, shortly after he realized that the multiplication of octonions  does not  have this property...

Commutativity of Addition :

In 1905, Leonard Dickson (1874-1954) pointed out that commutativity of addition need not be postulated if the commutativity of multiplication is  (which isn't always so, especially in texts of French origin).  This is an easy theorem which can be proved by expanding the equal quantities  (1+x)(1+y)  and  (1+y)(1+x)  using the  other  field axioms,  including  xy = yx.

Addition must be commutative even if multiplication isn't :

Actually, in a  unital  ring, distributivity by itself implies that any associative addition is commutative, even when multiplication is not.  Proof:

x + y   =   (-x+x) + x + y + (y+(-y))   =   -x + (1+1) x + (1+1) y + (-y)
=   -x + (1+1) (x+y) + (-y)   =   -x + (x+y) + (x+y) + + (-y)
=   -x + x + y + x + y + (-y)   =   (-x + x) + y + x + (y + (-y))   =   y + x  QED

At the heart of that proof are the two possible expansions of  (1+1) (x+y)  using distributivity on either side  (as both are explicitely allowed by the ring axioms  which are included in the above  field axioms).

"Definition of a group and a field by independent postulates"  Leonard Eugene Dickson (1874-1954).
Transactions of the American Mathematical Society, 6:198-204, 1905.
 
How distributivity makes addition commutative (0:57)  by  Michael Penn  (2023-04-11).


(2006-02-06)   Quotient Field   (or  Field of Fractions )
Smallest field containing a given ring  A  (without zero-divisors).

In a ring,  a  zero-divisor  x  is a nonzero element whose product with some nonzero element  y  is zero.  In a subring of a field,  that never happens because any nonzero  y  has an inverse in the field.  So,  if  xy = 0  ,  then:

x   =   x ( y y-1 )   =   ( x y ) y-1   =   0 y-1   =   0

However,  if a ring  A  has no zero-divisors,  then we may always find a field  K  with a subring isomorphic to  A.  The smallest such field is called the  quotient field  of  A  and it can be constructed as follows:

We define an  equivalence relation within the  Cartesian product  A x A*  (i.e,  all ordered pairs of elements from  A  where the second one is nonzero)  by stating that  (a,b)  and  (c,d)  are equivalent  when:

a d   =   b c

The equivalence-class of  (a,b)  is then called the  quotient  of a  and  b.  (When all is said and done we'll denote it  a/b.)

All such quotients form the ring's  quotient field  K  (also called  field of fractions)  on which addition and multiplication are induced by the following operations between pairs,  which can be shown to respect the above equivalence relation  (i.e., the class of the result depends only on the classes of the operands):

(a,b) + (c,d)   =   (ad+bc,bd)
(a,b) (c,d)   =   (ac,bd)

The first key observation is that the resulting pairs are indeed also in  A x A*  (the second element of either result is never zero because there are no zero-divisors in  A).

Next we can show that any element  x  of  A  is uniquely associated with the class consisting of all pairs  (bx,b)  where  b  is a nonzero element of  A.  Indeed,  all such pairs are  equivalent  and the class associated with  x  can't be associated with another element  y  of  A  (HINT:  otherwise  x-y  would be a divisor of zero).  It's also easy to verify that this one-to-one mapping is an  homomorphism  (i.e., it respects both operations).  So,  we may as well identify an element of  A  with its associated class and consider that  A  is just a  subring  of  K  (just like we routinely consider that integers are part of the rational numbers).

Likewise,  (b,b)  is the neutral element for multiplication,  which we may call  1  (whether or such a neutral element was already present in  A).

The  tedious  verification of all field properties is just routine.

Some common examples of quotient fields :
Ring  AQuotient Field  K
Integers   Z Rationals   Q
p-adic Integers   Zp p-adic Numbers   Qp
(Formal) Polynomials  (Formal) Rational Functions  
  (Formal) Power Series  (Formal) Laurent Series

Here  (and elsewhere)  the qualifier  formal  denotes the algebraic definition of an object independently of whatever applications it may have.  For example,  a formal polynomial is nonzero whenever some of its coefficients are nonzero,  although its value may be zero everywhere in a finite field.  Likewise, formal power series are well-defined irrespective of convergence.

Field of fractions


(2006-03-26)   Every  Finite  Integral Ring is a Division Ring
In the  next section,  we'll show that it's actually a  (commutative)  field.

We call  integral ring  (anneau intègre  in French)  a ring  (commutative or not)  where the product of two nonzero elements is never zero.  Below is a proof that every nonzero element in a  finite  integral ring is invertible:

First, we establish the existence of a  neutral element  1  (unity)  for multiplication:  Consider the successive powers of a  nonzero  element  y :

y1 = y,     y2 = yy,     y3 = yyy,     y4,     y5,     ...

As there are only finitely many possible values,  those can't be all distinct...  Say the  n+k+1st  is equal to the  n+1st   (for some k>0).  Let's put   u = yk

"x,     ( x u - x ) yn+1   =   x yn+k+1 - x yn+1   =   0

As there are no zero-divisor, the bracket must vanish, so  x u = x.  Likewise, u x = x.  Thus,  u  is neutral for multiplication;  the ring is  unital  ( 1 = u ).

Now, for any nonzero  a,  the map which sends  x  to  a x  is  injective:  If two distinct elements  x  and  y  had the same image, the product  a (x-y)  would vanish without any factor vanishing, which is ruled out here.

Any injection of a  finite  set into itself is surjective  (by the  pigeonhole principle ).  So,  there's an element  a'  whose image is 1  (unity)  this element is thus the right-inverse of  a.  The existence of a right-inverse for  every  nonzero element suffices to show that  all  of them are invertible. QED

Corollary : Every nonzero element of a  subring  S  of a finite division ring has its inverse in  S.

Indeed,  we only have to remark that such an  S  is a finite integral ring.


(2006-03-18)   Wedderburn's Little Theorem  (1905)
Multiplication in a finite division ring is necessarily commutative.

In other words, every  finite  division ring is a  field.

In English at least, "fields" are now officially required to be commutative, but there's no law against  memorizing  this surprising result the French way:

Every finite "field" is commutative.
Tout corps fini est commutatif.

In French, a "corps" is a division ring  (it may or may not be commutative).  When applicable, the French call "corps commutatif" what's just dubbed a "field" in English.  Some French authors write in English as if the English word was defined the French way  (Cédric Milliet is one of them).

The theorem was first published in 1905 by the Scottish mathematician  Joseph Wedderburn (1882-1948).  After seeing a proof of the theorem by L.E. Dickson (1874-1954), Wedderburn gave two other proofs in the same year...  However, Karen H. Parshall points out  (in her 1983 study of the issue)  that Wedderburn's first "proof" had a gap which went unnoticed at the time.  Although Dickson did acknowledge Wedderburn's priority, he should have been given credit for the first valid proof of what's now universally known as  Wedderburn's theorem.

"In pursuit of the finite division algebra theorem and beyond:  Joseph H.M. Wedderburn, Leonard E. Dickson, and Oswald Veblen"   by Karen Hunger Parshall.   Archives of International History of Science  33:111, 274-299 (1983).

Proof :   Let  K  be a  finite  division ring.

Let  C(x)  be the centralizer  (or commutant)  in  K  of a nonzero element  x  [ this consists of all the elements  y  of  K, including 0, for which   x y = y x ].  It's easy to establish that  C(x)  is a  subring  of  K, which means that it contains the reciprocals of all its nonzero elements.  So is the center  C  of  K  (which consists of those elements of  K  which commute with  every  element of  K).  Since  C  is commutative, it's a  field  (of order q ).

K  and  C(x)  are vector spaces over  C, whose respective dimensions are  n  and  n(x).  K  can also be viewed as a  module  over  C(x).    n(x)  divides  n.

Notice that  n  cannot  be equal to 2:  Otherwise, all the elements of   K  would be of the form  x + ya,  with  x  and  y  in the center  C,  which would make all of them commute  (thus implying that  n  is  1,  not 2).

Let's apply the  conjugacy class formula  to the multiplicative group formed by the  qn-1  nonzero elements of  K,  whose center  (C-{0})  is of order  q-1.  The order of the  conjugacy class  of  x  is the index of  C(x)-{0}  in the whole multiplicative group, namely  (qn-1) / (qn(x)-1).   We may enumerate all the conjugacy classes of  noncentral  elements  (assuming that there are any)  by letting  ni  be  n(x¹ n   for some member  xi  of the ith such class:

qn-1   =   q-1  +  
 
å
i
    qn  - 1
Vinculum
qni - 1

To establish that multiplication is commutative  (K = C)  we must prove that this relation implies that  n = 1  (i.e.,  the  S  on the right  must  be empty).

There are several ways to do so.  Wedderburn used the special case b=1  (A.S. Bang, 1886)  of Zsigmondy's Theorem (1892)  itself often credited to Birkhoff and Vandiver (1904) and rediscovered by many authors:  Carmichael in 1913, Kanold in 1950, Emil Artin in 1955, etc.  It says that, if a and b are coprime, then   an-bn  has a primitive factor (i.e., a prime factor not dividing that expression for a lower positive value of  n) except with  26-16  or for n=2 when a+b is a power of 2. 
 
In 1931, Ernest Witt proposed instead a celebrated self-contained argument based on the cyclotomic polynomials in the complex plane.  Several authors have modified Witt's proof to shun complex numbers.

Let's first show that the special cases of  Zsigmondy's theorem,  stated above,  don't apply:  We've already observed that  n  cannot be equal to 2.  It's not possible either to have  q = 2  and  n = 6,  because the sum  S  would then be equal to  62  while consisting of multiples of  3  (i.e.,  9, 21 or 63).

Therefore,  Zsigmondy's theorem  tells us that there's a prime  p  which divides  qn-1  but not  qm-1  for any positive value of  m  less than  n  (if there are any).  Since such a  p  necessarily divides  q-1  because it divides all other terms in the above equation, we must conclude that  n = 1.   QED

Proof of Wedderburn's theorem   |   Witt's Proof


(2015-12-24)   Artin-Zorn Theorem   (1930)
A finite alternative algebra without zero-divisors is necessarily a field.

This is a generalization of Wedderburn's theorem (1905) which states that a field is neccessarily obtained even whith a multiplication which need not be postulated to be  associativealternativity  is strong enough...

This theorem first appeared in the doctoral dissertation  (1930)  of  Max Zorn  (1906-1993)  on  alternative algebras.  Zorn himself credits the above theorem to his doctoral advisor,  Emil Artin (1898-1962).


(2006-03-18)   Galois Fields  (Finite Fields)
The order of a finite field is necessarily a power of a prime number.

Evariste Galois (1811-1832) established the existence of a field of order  q  (a finite field with  q  elements)  whenever  q  is a power of a prime number.

In 1893, E.H. Moore (1862-1932) proved that  all  finite fields are necessarily such  Galois Fields.  All finite fields of the same order are  isomorphic !

The essentially unique finite field of order  q = pn  is denoted  GF(q)  or  Fq 

The prime number  p  is the  characteristic  of  GF(q).  Any sum of  p  identical terms vanishes in  GF(q).

The  additive  group of  GF(q) = Fq  is isomorphic to the  direct sum  Cpn  of  n  cyclic groups of order  p  (the  n  components add independently modulo p).

Multiplicatively,  the  q-1  nonzero elements of  Fq  form a cyclic group.

In particular, if  q  is prime  (q = p)  then  Fq  is simply isomorphic to the field of integers  modulo  p.  In other words,   GF(p)  =  ( Z/pZ/pZ/pZ, + , ´ )

If  n > 1,  the  Galois field   GF(q)  of order  q = pn  may be constructed explicitely from the  prime field  GF(p),  by adding formally to it a  root  of any polynomial of degree  n  which happens to be irreducible in  GF(p).

For example, a construction of  GF(8)  is based on either one of the two irreducible cubic polynomial of  GF(2) = ({0,1},+,´)   namely:

x3 + x2 + 1       and       x3 + x + 1

Let's use the  latter.  A root of that polynomial verifies  x3 = x+1  (an element is its own opposite in a field of "characteristic 2" like this one).  We may call such a root  "2"  and call its square  "4",  so the rules of bitwise addition can be used to  name  the other elements of  GF(8)  after ordinary integers.

x0 = x7    x1         x2    x3 x4x5 x6
1x x2 x + 1   x2 + x  x2 + x + 1x2 + 1
1243675
 
Galois Addition over  F8
+ 01234567
0 0123 4567
1 1032 5476
2 23 01 6745
3 32 10 7654
4 45670123
5 54761032
6 67452301
7 76543210
Galois Multiplication over  F8
  01234567
0 000 00000
1 012 34567
2 0246 3175
3 0365 7412
4 0437 6251
5 0514 2736
6 0671 5324
7 0752 1643
L2 013 2645
 

When the order  (q-1)  of the multiplicative group of  GF(q)  isn't prime, there's a complication, best illustrated with the construction of  GF(9) :  Three of the  9  monic  quadratic polynomials over  GF(3)  are irreducible:

x2 + 1 ,     x2 + x + 2 ,     x2 + 2x + 2

However, a root  g  of the first polynomial only generates a cycle of order 4  (namely, g, -1, -g, 1).  What we need is a  primitive  element of order 8 which would generate the entire multiplicative group of  GF(9).  A root of either of the last two polynomials has this property.  (Such polynomials are thus called  primitive  polynomials.)

We have no shortcut to predict which irreducible polynomials of degree n over  GF(p)  yield primitive roots of  GF(p)  but many do.

Using the last of the above polynomials  (whose roots verify  x2 = x+1)  we may simply proceed as we did for  GF(8) :  We just call the new root "3",  and use  ternary  digit-wise addition to name other elements after integers:

x0 = x8    x1         x2    x3 x4x5 x6x7
1x  x + 1 2x + 1     2        2x     2x + 2 x + 2 
13472685
 
Galois Addition over  F9
+ 01234 5678
0 012 345678
1 120 453786
2 201 534867
3 345 678012
4 453 786120
5 534 867201
6 678 012345
7 786 120453
8 867 201534
Galois Multiplication over  F9
  01234 5678
0 000 000000
1 012 345678
2 021 687354
3 0364 71825
4 0487 23561
5 0571 38246
6 0638 52417
7 0752 64183
8 0845 16732
log3 0412 7536
 

Abstractly,  GF(q) = GF(pn )  may also be defined as the set of solutions, of  xq = x  in the algebraic closure of the  prime field  GF(p).  For example, the following identity holds in  F[x]  (the ring of the polynomials over  F ).

x9 - x   =   x (x-1) (x-2) (x-3) (x-4) (x-5) (x-6) (x-7) (x-8)

Therefore, all symmetric functions of the nonzero elements of  GF(q)  vanish, except their  product,  which is  -1.  (When  q  is even, -1 = +1.)

The  automorphism group  of  GF(pn )  is the  cyclic group of order n  generated by the  (standard)  Frobenius map.  Its other elements are also loosely called  Frobenius maps.  Each of these sends  x  to the Galois k-th power of  x  for some  k  which is a power of  p.  (There's only one such automorphism when  n = 1.)

k   =   1 ,   p ,   p2 ,   p3   ...   pn-1

Finite fields are essential in the classification of  finite simple groups.

Galois Fields on the HP Prime Calculator


(2015-12-22)   Fq[x] :   The Polynomials in a Galois Field.
Irreducible and primitive polynomials of a Galois field

The  ring  of the  polynomial functions  over the field  Z/pZ  whose degrees are less than  n  form a vector space  of  dimension  n  isomorphic to  the Galois field  Fq  of  (prime)  characteristic  p  and order  q = pn.

The  multiplicative group  formed by the nonzero elements of  GF(q)  is a cyclic group of order  q-1.  As such, it can be generated by a single element  and by any power of  g  whose exponent is relatively prime to  q-1.  Such generating elements are called  primitive.  There are  f(q-1)  primitive  elements in GF(q)  (where  f  is Euler's totient function).

The number of primitive polynomials of degree d in GF(q) is equal to:

f (qd-1) / d

d 123456789 OEIS
F2 112266181648 A011260
F3 124822481563201008 A027385
F4 2412321202881512409615552 A027695
F5 24204828072055801497699360 A027741
F7 283616011206048378561920001376352 A027743
F8 61814443254002332825401685944012607488 A027744
F9 41696640528027648340704196608015676416 A027745

 Come back later, we're
 still working on this one...

Introduction to finite fields   |   MathWorld :   Primitive polynomials
Wikipedia :   Primitive element in a Galois field   |   Primitive polynomial


(2022-05-08)   Fundamental Theorem of Galois Theory
The structure of a field is the structure of its symmetries.

 Come back later, we're
 still working on this one...

The Fundamental Theorem of Galois Theory (25:09)  by    (Aleph 0, 2021-11-25).
 
The Insolvability of the Quintic (10:18)  by    (Aleph 0, 2021-02-20).


+ 0
 0  0 
 
´ 0
 0  0 
(2006-04-05)   The Trivial Field   F1 = GF(1)
The field with only  one  element:   0 = 1.

The zeroth power of any prime is 1.  Arguably, the simplest Galois field is thus of order 1.  Its single element is neutral for  both  addition and multiplication  (1 = 0)  which  cannot  happen in a nontrivial field  (with 2 elements or more).  Some textbooks rule out fields with only one element.

A few authors observed that some concepts traditionally studied on their own can be viewed as the specialization to  q = 1  of structures normally defined over a  nontrivial finite field  of order  q > 1.  On this subject, Christophe Soulé (2003) quotes Jacques Tits  (1957), A. Smirnov  (1992)  and  Y. Manin  (1995).

Such enlightening specializations aren't obvious.  For example, the classical group  SL(n,F)  is identified with the symmetric group  Sn  when  F = F1

Incidentally,  if we didn't count the trivial field as a legitimate ring,  then the function  r  which counts  the number of finite rings of given order  would no longer be a  multiplicative function.  That would be silly.    Wink

Faire des mathématiques,  c'est 
donner le même nom à des choses différentes
.
Henri Poincaré  (1854-1912)

Les variétés sur le corps à un élément  (2003, 2018) by  Christophe Soulé
 
https://en.wikipedia.org/wiki/Field_with_one_element
 
https://en.wikipedia.org/wiki/Field_with_one_element


(2006-03-25)   Splitting Field of a Polynomial  P Î F[x]
The smallest subfield or extension of F where P factors completely.

An  extension  of a field  F  is a field  K  of which  F  is a subfield.  There's no  proper  subfield of the splitting field of P where P can be completely factored  (into polynomials of degree 1).


(2017-12-06)   Perfect Fields
Characteristic is either  0  or  p,  if every element has a p-th root.

A perfect field is either a field of characteristic 0  (like the rationals)  or a field of characteristic  p  where all elements are  p-th  powers.  (This includes all finite fields and all algebraically-closed fields.)

If the ground field is perfect,  Galois theory  is simpler, because every finite extension of the field is  separable  (that's called  Galois' hypothesis).

Some equivalent characterizations of what makes a field  K  perfect :

Perfect field

 Pierre Alphonse Laurent
(2017-08-01)   The Field of Laurent Series
The Laurent series over  any  given field of coefficients.

A formal  Laurent series  (irrespective of its convergence)  is uniquely formed by a formal power series  f  and a polynomial  P:

f(x)   +   P(1/x) / x.

The  field of Laurent series  is to the  ring of formal power series  what the  field of p-adic numbers  is to the  ring of p-adic integers.  In either case,  allowing finitely many negative powers makes every element invertible and turns a ring into a field.

Example  |  Formal Laurent series  |  Pierre Laurent (1813-1854; X1830)
 
The field of Laurent series over finite fields  (Mathematics Stack Exchange,  2011-05-14).


(2006-03-17)   The Algebraically Complete Nim-Field:  Conway's  On2
A multiplication compatible with  bitwise  addition of integers.   (1975)

In the seventh chapter (Chapter 6) of his  1976  masterpiece  On Numbers and Games  (Academic Press, London, ISBN 0-12-186350-6)  John Horton Conway (1937-2020)  shows in what sense  bitwise  addition is the simplest "addition" we can endow the natural integers with.  This operation can be described as binary addition  without carry.  It's also known as  Nim-sum,  or bitwise  "exclusive or".  Under the latter name, this operation is widely available at the fundamental level of the  assembly languages  of modern binary computers  (abbreviated "xor" or "eor").

  • The  Nim-sum  of distinct powers of  2  is their ordinary sum.
  • The  Nim-sum  of two equal integers is 0.

Conway then introduces the "simplest" multiplication compatible with this addition.  This multiplication can be effectively computed for integers using field properties and two additional statements which parallel those given above for Nim-addition.

  • The  Nim-product  of distinct Fermat 2-powers is their ordinary product.
  • The  Nim-product  of two equal Fermat 2-powers is their  sesquimultiple.

Fermat 2-power  is 2 raised to the power of a 2-power  ( 22)  namely:
2, 4, 16, 256, 65536, 4294967296, 18446744073709551616, ... A001146
The aforementioned sesquimultiples of those are half as much again:
3, 6, 24, 384, 98304, 6442450944, 27670116110564327424, ...

Conway coined these learned terms to shun ordinary arithmetic when describing Nim operations.
 
Pierre de Fermat (1601-1665) once conjectured that a prime number always came after 2 raised to a 2-power.  The conjecture is false; there are probably no such prime numbers beyond the five known to Fermat:  3, 5, 17, 257 and 65537.  In 1796, teenager Carl Friedrich Gauss showed that a regular n-gon is constructible just when  n  is a 2-power multiplied by a square-free product of those "Fermat primes".

Those two operations give natural integers the structure of a field of characteristic 2, which can be generalized to the entire  class  of ordinal numbers  (the numbers below a  Fermat 2-power  form a subfield).  Conway calls the whole field  On (pronounced "onto").

On is meant to stand for "Ordinal numbers with characteristic 2".

We may call  nimbers  the elements of  On especially the finite ones...

Nim-multiplication table   ( F2 ,  F4  and  F16  are subfields of  On)
  01234567 89101112131415
  0     0    0     0    0     0    0     0    0     0    0     0    0     0    0     0    0  
1 0123 4567 89101112131415
2 02 31 810119 121415134675
3 03 12 12151314 4756811910
4 04812621410 11153713951
5 05101527813 36912141114
6 06111314853 71121091524
7 07914101334 15861521211
8 08124113715 13519614102
9 0914715618 512112103413
10 01015539126 11114428137
11 011136712101 9241514538
12 0124813195 610214117153
13 01361194152 14385710112
14 01479511212 10413315186
15 015510114411 2137831269
 

Note that the Nim-product of a Fermat 2-power and  any  lesser number is the same as their ordinary product  (HINT:  The lesser number is a sum of 2-powers, each of which is a product of Fermat 2-powers).  Thus, using the fact that the Nim-square of 16 is 16+8, Nim-products of factors up to 255 can be "put together" after 5 look-ups of the above table and three 4-bit Nim-additions.  Example:

100.200 = (6.16 + 4)(12.16 + 8)
        = (6.12)(16+8) + (6.8 + 4.12) 16 + 4.8   [4 look-ups]
        = 9 (16+8) + (7+13) 16 + 11
        = (9+7+13) 16 + 9.8 + 11                 [1 look-up ]
        = (9+7+13) 16 + (5+11)                   [3 Nim-sums] 
        = 3.16 + 14 = 62

It takes little more than  5m steps to Nim-multiply two  2m-bit integers from scratch using the recursive procedure suggested by the above example.  Asymptotically, this means that the Nim-product of two  n-bit  integers can be computed in time  O(n k )  where  k = lg(5) < 2.322.

Denoting  a'  an arbitrary ordinal smaller than  a, Conway gives two remarkable one-line definitions of the Nim-operations  which are very similar to his other one-liners in the realm of surreal numbers  (the "-" sign is used here as a synonym of the "+" sign for aesthetic reasons, in part to reinforce that similarity).

  • a + b   is the least ordinal distinct from all numbers   a' + b  and  a + b'.
  • a b   is the least ordinal distinct from all numbers   a' b + a b' - a' b'.

Note that, in an additive groupa + b   cannot be equal to either  a' + b  or  a + b'  unless  a' = a  or  b' = b.  Therefore, the above definition is the "simplest" possible definition of addition in some sense.

Likewise, in a field,  a b   can't be equal to   a' b + a b' - a' b'.  Otherwise,   (a-a') (b-b')  would be a zero product of nonzero factors.

These "genetic" definitions are also valid for infinite ordinals  (they're equivalent to the above practical rules for  finite  integers)  and do make  On  a field.

1/a  is recursively defined as the least nonzero ordinal distinct from all numbers

(1/a' ) [ 1 + (a'-a)(1/a)' ]

The Nim-reciprocals of nonzero ordinals are  1, 3, 2, 15, 12, 9, 11, 10, 6, 8, 7, 5, 14, 13, 4, 170, 160, 109, 107, 131, 139, 116, 115, 228, 234, 92...  A051917.  One way to compute the reciprocal of a finite ordinal  a  is by iterating the function which sends  x  to  ax2  (compare this to the computation of a p-adic reciprocal).  Starting from 1, we obtain 1 again after a number of iterations equal to the bit-length of  a, rounded up to a 2-power.  The last step reveals the reciprocal of  a.

In a field of characterisic  2,  like this one,  the  square  function is a field homomorphism  (the square of a sum is the sum of the squares)  which is injective  (HINT:  If x and y have equal squares, then x+y vanishes).  Therefore, it's a bijection within any finite additive subgroup  (which is a fancy way to say that a  nimber  and its Nim-square have the same  bit length).  This shows that Nim-squaring is a field  automorphism  among finite  nimbers  (in fact, it's an automorphism of the  whole  field On.)

Conversely, any nimber  x  has a unique square-root  rim (x)  and the  rim  function is an  automorphism  as well  (the square-root of a sum is the sum of the square roots).  For finite nimbers,  the rim  function can be defined  recursively :

rim (0) = 0         rim (x) = x + rim ( x + x 2 )

That's effectively a recursive definition, because  x + x 2  has  fewer  bits than  x.   (A160679)

n 012 345 678 91011 121314 151617 181920
rim(n) 013 276 4514 151312 9810 113031 292825

An homomorphism  f  from the multiplicative subgroup of  finite ordinals  onto the unit circle of the complex plane  (a representation of U(1),  the  phase group  of physicists)  can be defined by any sequence of integers  (u)  satisfying the following conditions.  (Using Conway's own convention, we put "ordinary" arithmetic between square brackets, wherever needed.)

u <  [ 22n ]           f (un )  =  exp [ 2pi / (22n-1) ]           un+1[ 22n+ 1 ]  =  un

Because  x <  [ 22n ]  just when  x [ 22n- 1 ] = 1,  the above inequality is true for  n  if  it's true for  n+1  (HINT:  Raise both sides of the last equality to a power).  As there's clearly a  finite  satisfactory sequence of any length, there must be an  infinite  one  (among finitely many possibilities for the n-th term, at least one must belong to a satisfactory sequence whose length exceeds any given bound).
Actually, for  any  satisfactory  un  there are  22n  satisfactory values of   un+1


With the surreal transfinite ordinals it contains,  On2  is  algebraically complete.  Here's just one of many mind-boggling results about the least infinite ordinal  w :

w3 = 2

On Numbers and Games (1975)  J.H. Conway   (1976, Academic Press, London, ISBN 0-12-186350-6)
On the Algebraic Closure of Two   by  Hendrik W. Lenstra, Jr.   (Leiden University, 1977).
Nim Multiplication   by  Hendrik W. Lenstra, Jr.   (IHES, Bures-sur-Yvette, February 1978).
On2Transfinite Number Hacking   &   Conway's Nim-Arithmetics   by  Lieven Le Bruyn   (January 2009).
Conway's Nimbers   by  Alasdair McAndrew   (2010-10-09).
Conway's Nim Field   by  Peter Cameron   (2011-10-29).
Video :   Lexicographic codes of minimal distance 3 are vectors over nimbers  by  J.H. Conway  (2014).


 Gerard Michon (2013-07-22)   One step beyond  Conway's  On2 :
The  On3  field   (Michon, 2013)

Think how far the reasonable person would go, and then go a step further. John H. Conway  (introduction to the  Atlas of Finite Groups, 1985) 

On2  was the name given by Conway to the "curious field" discussed in the previous article, with infinitely many nested finite subfields  (Galois fields)  of characteristic 2.  Here, we introduce a counterpart of  characteristic 3.  (Other prime characteristics are discussed in the next section.)

Preliminaries :

Consider the Cayley-Dickson construct presented elsewhere on this site, in the special case of algebras over the field of real numbers.

So to speak, that construct yields the  square  of an algebra by doubling its number of dimensions  (e.g., complex numbers are obtained from real numbers, quaternions from complex numbers, and so forth).

The original algebra must be endowed  a priori  with a  conjugation  unary operator, traditionally denoted by a postfixed star  (the conjugate of x is x*)  having the following axiomatic properties:

  • Conjugation is an additive isomorphism:   (x+y)*   =   x* + y*
  • It's an involution  (i.e., a bijection equal to its inverse):  (x*)*  =  x
  • It endows multiplication with Hermitian symmetry:  (x y)*   =   y* x*

Because a  finite  division algebra is commutative, it's a field and conjugation is a field automorphism.  Any such automorphisms must be Froebenius maps, which is to sau that there is an integer k such that:

" x ,     x*   =   xpk

The last two axioms imply that   1*   =   1   because:

1   =   (1*)*   =   (1 1*)*   =   1** 1*  =   1 1*   =   1*

The squared algebra consists of ordered pairs of elements from the original algebra, endowed with addition and multiplication defined as follows:

( a , b )  +  ( c , d )       =     ( a + c  ,  b + d )
( a , b )   ( c , d )   = ( a c  -  d b*  ,  a*d  +  c b )

From the fact that   1* = 1   it follows that  (1,0)  is neutral for multiplication.  By equating  (x,0)  with  x,  the original algebra is considered to be included in its Cayley-Dicskon square.  Another key remark is that:

( a , b ) ( a* , -b )   =   ( a a* + b b* , 0 )

Now, by definition, a  division algebra  is an algebra where every nonzero element has a multiplicative inverse.  (If such an algebra is associative and commutative it's a field.  If it's only associative, it's a skew-field.)  Our last relation shows that the square of a division algebra is a division algebra  provided  the following  postulate  holds:

Postulate :   The quantity  a a* + b b*  is nonzero, unless  a = b = 0

Over the field of real numbers, the Cayley-Dickson construction can be applied iteratively by defining conjugation over the squared algebra in terms of conjugation over the original algebra:

( a , b )*   =   ( a* , -b )   [for real algebras only]

It's then easy to show, by induction, that the quantity  x x*  is always a positive real number.  The above postulate follows from the fact that a sum of nonnegative reals can only vanish if they're all zero.

With other fields  (in particular, finite fields)  the same postulate could possibly be derived from other  ad hoc  properties, like:

$ u ,     u + u   ¹   0 ,     " x ,     x x*   =   u

Clearly, this implies that  u = 1  (HINT:  consider  x = u)  and that the field is of characteristic 3  (i.e.,  1+1+1=0)  because:

u   =   (u+u) (u*+u*)   =   u u* + u u* + u u* + u u*   =   u + u + u + u

The above holds for the field  F3  = (Z/3Z,+,.)  with trivial conjugation:

0* = 0 ,     1* = 1 ,     2* = 2 ,     1 . 1*   =   2 . 2*   =   1   =   u

Now, for any division algebras over that field  (starting with the field itself)  we may define conjugation via:

" x ¹ 0 ,     x*   =   - x-1

For successive algebra obtained from the Cayley-Dickson construct, the same definition can be given a recursive expression, if needed:

( a , b )*   =   ( -a* , b )   [for characteristic-3 fields only]

All such successive Cayley-Dickson algebras are thus division algebras.  By induction, they can all be proved to be  fields.  (HINT:  The Cayley-Dickson square of a commutative algebra is associative, an associative algebra is a ring and a finite division ring is commutative.)

Therefore, the  Cayley-Dickson construction  (with the above conjugation adapted to characteristic 3)  defines a nested sequence of finite fields whose orders form a sequence where every term is followed by its square:

3,  9,  81,  6561,  43046721,  1853020188851841,  ... 32n ... (A011764)

The sum or product of finite ordinals is well-defined by working things out in any field from that sequence large enough to contain all operands.

The ternary field structure so given to nonnegative integers mirrors Conway's binary structure, although he went much further with inductive definitions encompassing surreal ordinals  to form the great  algebraically complete  field described in his exciting masterpiece  "On Numbers and Games"  (1976).
 
The above preliminaries provide theoretical specifications for the "ternary" operations, which are described below in practical terms.

Ternary Addition
+ 01234 5678
0 012 345678
1 120 453786
2 201 534867
3 345 678012
4 453 786120
5 534 867201
6 678 012345
7 786 120453
8 867 201534
          Ternary Multiplication
x*  01234 5678
00 000 000000
11 012 345678
22 021 687354
63 036258147
74 048561723
85 057813462
36 063174285
47 075426831
58 084732516
 

Ternary Addition :

Ternary  addition is of  "characteristic 3".  This means:   "x,  x+x+x = 0

We understand the  ternary sum  of two integers as the integer whose n-th ternary digit is the sum of the two n-th ternary digits of the operands modulo 3.  You may call that  ternary addition  "without carry" if you must.

Ternary addition  must naturally always be understood "without carry", as addition performed  with  carry is the same operation on integers regardless of the numeration radix used  (just call that "ordinary addition").  Likewise,  binary addition  can only be interpreted as the operation we've called "Nim-addition" above and elsewhere.

Ternary  addition (without carry) pertains to a version of Moore's Nim where a player may take from  one or two  heaps at each turn.

H.W. Lenstra (1978, Exercise 15)  attributes to Simon Norton a definition of ternary addition  à la Conway  (where  a' denotes any ordinal below a) :

The ternary sum  a + b  is  defined  as the least ordinal not expressible as:

  • a' + b   or
  • a + b'   or
  • a' + b'   with   a' + b  =  a + b'

This recursive definition need not be limited to finite ordinals.

Ternary Multiplication :

Let's use the theoretical definitions to work out practical rules, similar to those devised by Conway in the binary case.  In what follows, we use Conway's convention of putting ordinary arithmetic between square brackets  [ ].

  • 2.2 = 1   and   "x, 0.x = 0,  1.x = x.
  • If  x < [32n]  then   x [32n ]  =  [x 32n
  • The  ternary square  of   [ 32n ]   is   [ 2n ]

 Come back later, we're
 still working on this one...

Simon P. Norton (1952-)   |   Simon Norton   by Frances Hubbard  (2011-09-10).


(2006-03-22 & 2013-07-24)   Beyond  On2  and  On3...
Defining  Onp  as a  field  of  prime  characteristic p.

The approach we used in the previous section, based on the Cayley-Dickson construct, will not work for characteristic 5  because  1 1* is 1  and 2 2*  is  4.  This makes  1 1* + 2 2*  vanish modulo 5.

Likewise, it won't work for any other prime characteristic  p  congruent to 1 modulo 4, because the equation  n2+1 =  has a solution modulo p.  For such a solution,  1 1* + n n*  vanishes modulo p.

Ternary Multiplication  (a second look)

Let's take  ternary addition  (without carry)  for granted.  Considering only finite integers for now, we want to define a compatible commutative multiplication which does not break the rules of arithmetic in a ring.

This goal can be achieved with the following practical rules, similar to those devised by Conway in the binary case.  In what follows, we use Conway's convention of putting ordinary arithmetic between square brackets  [ ].

  • 2.2 = 1   and   "x, 0.x = 0,  1.x = x.
  • If  x < [32n]  then   x [32n ]  =  [x 32n
  • The  ternary square  of   un = [32n ]   is   un+ vn   where   vn< un.
A slight generalization would be to let the square of  un  be  wnun+vn  where both sequences v and w are dominated by u.

Any sequence  v  stricly dominated by  u  would do  if  all we wanted was a  unital ring,  but only special ones will yield a  field...

vn  can't be zero, or else  un (un-1)  would be a zero product of two nonzero factors, which is ruled out in a field.  Here are 4 satisfactory initial terms:

v0 = [ 1/3 u0 ]     v1 = [ 2/3 u1 ]     v2 = [ 2/3 u2 ]     v3 = [ 1/3 u3 ]

The first relation means   32 = 4   and corresponds to a  subfield  already presented explicitely above as a  particular  representation of  GF(9).  The next relations yield subfields of orders  81, 6561 and 43046721.

With  v4 = 10000000   we obtain a subfield of order  1853020188851841  whose nonzero elements are all powers of 43046731  (not 43046721).

The multiplicative group of a finite field being cyclic, a finite ring is a field if and only if there's a  primitive  element in it  (for example, the nonzero elements of the aforementioned field of order 43046721 are the  distinct  powers of 6561).
An element  x  is of order  k = [32n-1]  if and only if:

  • xk = 1
  • For any prime divisor  p  of  k,   x[k/p] ¹ 1.

(When this holds for some element  x  of a monoid of order  k,  then this monoid is a  cyclic group  consisting of the k distinct powers of  x.)  Joseph-Louis Lagrange 
 1736-1813

Conversely, if  xk ¹ 1  for some nonzero  x,  then the ring can't possibly be a field  (by Lagrange's theorem, the order of an element would divide the order of the group, so the  k  nonzero elements can't form a group).

Using fast exponentiation, a guess-based search for a primitive root may thus result in an efficient proof that the ring is a field  or that it's not  (albeit much less efficiently in the latter case, so the repeated lack of a firm conclusion is a strong indication that the ring is  not  a field).  There are  f(k)  "lucky guesses"  for  x  which will prove that a subfield of order  k  is just that  (where  f  is Euler's totient function).  This is always a substantial percentage of random guesses.

In the case where we're actually faced with a field, the above proof has a good chance to work with a random  x  (we just need a factorization of  k  into primes, which can be a significant problem for very large values of k).  If the above proof fails with a specific x, then all we know is that  x  is not a primitive root...  However, repeated failures within a field are highly unlikely because there are so many primitive roots in it.  Such repeated failures thus indicate that we're not dealing with a field...

All the prime factors of   [ 32n-1 ]   appear below, at row  n  or less :
 n  Prime Factorization  of   32n-1+ 1   ( if  n > 0 )
0 2
1 2 . 2
2 2 . 5
3 2 . 41
4 2 . 17 . 193
5 2 . 21523361
6 2 . 926510094425921
7 2 . 1716841910146256242328924544641
8 2 . 257 . 275201 . 138424618868737 . 3913786281514524929 . 153849834853910661121
9 2 . 12289 . 8972801 . 891206124520373602817 . 707275264749309881405141965802671548079179711820351316861777644606207216944972589404100097
10 2 . 59393 . 448524289 . 847036417 ... (466-digit  composite  factor)

 Come back later, we're
 still working on this one...

A Recursive Definition of p-ary Addition without Carry (1999)   by  François Laubie.
ON Onp   by  Dr. Joseph M. DiMuro   (2011-08-08).


Judea Pearl (2013-09-25)   Summary of  Galois Theory
How  Galois  proved that  quintic  equations can't be solved by radicals.

 Come back later, we're
 still working on this one...

border
border
visits since March 19, 2006
 (c) Copyright 2000-2023, Gerard P. Michon, Ph.D.