Related Links (Outside this Site)

---

(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...

---

(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:

A  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).

(*)   Both sides of the distributivity law are shown, so that this 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 the one-sided version listed here  without  assumming commutativity  (see elsewhere on this site for a proof).

The terms  commutative  and  distributive  (French masculine forms: 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 multiplication of octonions  does not  have this property...

---

(2006-03-18)   Wedderburn's 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.

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 contains the reciprocals of all its nonzero elements.  The same is true about the center  C  of  K  (which consists of those elements of  K  which commute with  every  element of  K).  Since  C  is clearly commutative, it's a  field  (of order q ).

K  and  C(x)  are vector spaces over  C, of respective dimensions  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:  If all the elements of   K  are of the form  x + ya,  with  x  and  y  in the center  C,  then all of them commute  (so, n = 1).

Let's apply the  conjugacy class formula  to the multiplicative group formed by the  qⁿ-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  (qⁿ-1) / (q^n(x)-1).   We may thus enumerate all the conjugacy classes of  noncentral  elements  (assuming that there are any)  by letting  n_i  be  n(x_i ) ¹ n   for a typical member  x_i  of the i^th such class:

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

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

There are several ways to do this.  Wedderburn used a special case (b=1, due to A.S. Bang in 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, Artin in 1955, etc.  This says that, when a and b are coprime,   aⁿ-bⁿ  has at least one primitive factor (i.e., a prime factor not dividing this expression for a lower positive value of  n) except with  2⁶-1⁶  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  (as stated in the above note)  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  qⁿ-1  but not  q^m-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.  

Proof of Wedderburn's theorem   |   Witt's Proof

---

(2006-03-26)   Finite Integral Domains
Every  finite  integral domain is a  field.

Proof :   (Ruling out as trivial a single-element ring.)

In this, we understand an  integral domain  to be a ring  (commutative or not)  where the product of two nonzero elements is never zero.  Commutativity will be implied by Wedderburn's theorem  if we just prove that every element is necessarily invertible in such a  finite  structure...

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

y¹ = y,     y² = yy,     y³ = yyy,     y⁴,     y⁵,     ...

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

"x,     ( x u - x ) yⁿ⁺¹   =   x y^n+k+1 - x yⁿ⁺¹   =   0

As there are no divisors of zero, 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 element  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  (the  pigeonhole principle )  which implies that 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 is sufficient to establish that  all  of them are invertible. 

It's remarkable that the mere absence of divisors of zero in a finite ring makes it necessarily commutative and isomorphic to a Galois field.

---

(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 = pⁿ  is denoted  GF(q)  or  F_q 

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) = F_q  is isomorphic to the  direct sum  C_pⁿ  of  n  cyclic groups of order  p  (the  n  components add independently modulo p).

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

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

If  n > 1,  the  Galois field   GF(q)  of order  q = pⁿ  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 an irreducible cubic polynomial of  GF(2) = ({0,1},+,´).  There are only two such polynomials:

x³ + x² + 1       and       x³ + x + 1

Either will do.  Let's use the latter.  A root of that polynomial verifies  x³ = 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.

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

x² + 1 ,     x² + x + 2 ,     x² + 2x + 2

However, the first of these is less convenient than the others, because it does  not  yield a  generator of the (cyclic) multiplicative group  (a  primitive  root).  Basing a construction of  GF(9)  on it makes the multiplication table messy to build... 

There's no shortcut to predict which irreducible polynomials of degree n over  GF(p)  yield primitive roots of  GF(pⁿ )  but most of them do...

Using the last of the above polynomials  (whose roots verify  x² = x+1)  we may proceed as with the above construction of  GF(8) :  Calling the new root "3",  we use  ternary  digit-wise addition to name other elements of  GF(9)  after integers:

Abstractly,  GF(q) = GF(pⁿ )  may also be defined as the set of solutions, of  x^q = 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₉  ).

x⁹ - 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 equal to  -1.  (When  q  is even, -1 = +1.)

The  automorphism group  of  GF(pⁿ )  is the  cyclic group of order n  generated by the (standard) Frobenius map.  Its other elements are also 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 ,   p² ,   p³   ...   p^n-1

Finite fields play an essential role in the classification of  finite simple groups.

---

+ 0  0   0

´ 0  0   0

(2006-04-05)   The Trivial Field   F₁ = 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).

A few authors observed that some concepts traditionally studied on their own can be viewed as the specialization to  q = 0  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 enligntening identifications may not always be obvious.  For example, the classical group  SL(n,F)  is argued to be the symmetric group  S_n  when  F = F₁

---

(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).

---

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

In the seventh chapter (Chapter 6) of his  1976  masterpiece  On Numbers and Games  (Academic Press, London, ISBN 0-12-186350-6)  John H. Conway 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 this latter name, the 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 describes 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 powers is their ordinary product.
• The  Nim-product  of two equal Fermat powers is their  sesquimultiple.

A  Fermat power  means 2 to the power of a 2-power  ( 2²ⁿ )  namely:
2, 4, 16, 256, 65536, 4294967296, 18446744073709551616, ... A001146
The sesquimultiples of those, as involved in the above, 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  (originally, he wrote "Fermat 2-power").  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 so-called "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 power  form a subfield).  Conway calls the whole field  On₂ .

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

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

Note that the Nim-product of a Fermat 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 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  5^m steps to Nim-multiply two  2^m-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'.

These 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  ax²  (compare this to the computation of a p-adic reciprocal).  Starting from 1, we obtain 1 again after a number of such 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, rim is 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-toot 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 ² )

That's effectively a recursive definition, because  x + x ²  has  fewer  bits than  x. 

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_n  <  [ 2²ⁿ ]           f (u_n )  =  exp [ 2pi / (2²ⁿ-1) ]           u_n+1^{[ 22n+ 1 ]}  =  u_n

Because  x <  [ 2²ⁿ ]  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  u_n  there are  2²ⁿ  satisfactory values of   u_n+1

---

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

w³ = 2

---

(2006-03-22)   On₃ and beyond...
On_p  is a  field  for any  prime  p.

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) 

The symbol introduced by Conway for the "curious field" discussed in the previous article and the connection of that field to the Galois fields of characteristic 2 suggest an easy generalization to any other prime characteristic  (3, 5, 7, etc.)  at least for finite integers...  We may even attempt to mimic Conway's inductive definitions to encompass all  surreal ordinals  in the hope of getting  algebraically complete  fields.  Let's start with  On₃    [limited to finite ordinals, for now].

Ternary Addition :

Ternary  addition is of  "characteristic 3".  This means that:   "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.

We're resisting the temptation to coin a new name for  ternary  operations, since the term should be otherwise unused and thus unambiguous:  Ternary addition  must 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").  Similarily,  binary addition  should only be interpreted as the operation we've called "Nim-addition" above and elsewhere.

Ternary  addition "without carry" is related to the version of Moore's Nim where a player is allowed to take from  one or two  heaps at each turn.

Ternary Multiplication  (a first attempt)

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 < [3²ⁿ]  then   x [3²ⁿ ]  =  [x 3²ⁿ ] 
• The  ternary square  of   u_n = [3²ⁿ ]   is   u_n+ v_n   where   v_n< u_n.

A slight generalization would be to let the square of  u_n  be  w_nu_n+v_n  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...

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

v₀ = [ ¹/₃ u₀ ]     v₁ = [ ²/₃ u₁ ]     v₂ = [ ²/₃ u₂ ]     v₃ = [ ¹/₃ u₃ ]

The first relation means   3² = 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  v₄ = 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 = [3²ⁿ-1]  if and only if:

• x^k = 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.)

Conversely, if there's a nonzero  x  for which  x^k ¹ 1  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...

Ternary Multiplication on  On₃

3³ⁿ