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

Vocabulary: We consider
skew fields to be noncommutative. Some don't.

Fields are commutative rings where
every nonzero element has a reciprocal.

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

The Field Axioms
(multiplicative commutativity isn't required in a division ring)

"x
"y
"z

Addition

Multiplication

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) = 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
octonionsdoes not
have this property...

Commutativity of Addition :

In 1905, Leonard Dickson
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.

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

(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 may specify "corps commutatif" which is
what we simply call a "field" in English.

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 Science33:111, 274-299 (1983).

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 centerC
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 centerC,
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 q^{n}-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^{n}-1) / (q^{n(x)}-1). _{ }
We may enumerate all the conjugacy classes of
noncentral
elements (assuming that there are any) by letting
n_{i} be
n(x_{i }) ¹ n
for some member x_{i} of the i^{th} such class:

q^{n}-1 = q-1 +

å

i

q^{n}_{ } - 1

q^{ni} - 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
a^{n}-b^{n} has a
primitive factor
(i.e., a prime factor not dividing that expression for a lower positive
value of n)
except with 2^{6}-1^{6} 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
q^{n}-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.

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

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^{n+1}
= x y^{n+k+1}
- x y^{n+1} = 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.

(2015-12-24) Artin-Zorn Theorem (1930)
A finite alternative algebra
without divisors of zero 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 associative,
alternativity 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 = p^{n} 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 sumC_{p}^{n}
of n cyclic groups
of order p
(the n components add independentlymodulo 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^{n} 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:

x^{3} + x^{2} + 1
and
x^{3} + x + 1

Let's use the latter.
A root of that polynomial verifies x^{3} = 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.

x^{0} = x^{7}

x^{1}

x^{2}

x^{3}

x^{4}

x^{5}

x^{6}

1

x

x^{2}

x + 1

x^{2} + x

x^{2} + x + 1

x^{2} + 1

1

2

4

3

6

7

5

Galois Addition overF_{8}

+

0

1

2

3

4

5

6

7

0

0

1

2

3

4

5

6

7

1

1

0

3

2

5

4

7

6

2

2

3

0

1

6

7

4

5

3

3

2

1

0

7

6

5

4

4

4

5

6

7

0

1

2

3

5

5

4

7

6

1

0

3

2

6

6

7

4

5

2

3

0

1

7

7

6

5

4

3

2

1

0

Galois Multiplication overF_{8}

0

1

2

3

4

5

6

7

0

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

7

2

0

2

4

6

3

1

7

5

3

0

3

6

5

7

4

1

2

4

0

4

3

7

6

2

5

1

5

0

5

1

4

2

7

3

6

6

0

6

7

1

5

3

2

4

7

0

7

5

2

1

6

4

3

L_{2}

0

1

3

2

6

4

5

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:

x^{2} + 1 ,
x^{2} + x + 2 ,
x^{2} + 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^{n }) but many do.

Using the last of the above polynomials
(whose roots verify x^{2} = 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:

x^{0} = x^{8}

x^{1}

x^{2}

x^{3}

x^{4}

x^{5}

x^{6}

x^{7}

1

x

x + 1

2x + 1

2

2x

2x + 2

x + 2

1

3

4

7

2

6

8

5

Galois Addition overF_{9}

+

0

1

2

3

4

5

6

7

8

0

0

1

2

3

4

5

6

7

8

1

1

2

0

4

5

3

7

8

6

2

2

0

1

5

3

4

8

6

7

3

3

4

5

6

7

8

0

1

2

4

4

5

3

7

8

6

1

2

0

5

5

3

4

8

6

7

2

0

1

6

6

7

8

0

1

2

3

4

5

7

7

8

6

1

2

0

4

5

3

8

8

6

7

2

0

1

5

3

4

Galois Multiplication overF_{9}

0

1

2

3

4

5

6

7

8

0

0

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

7

8

2

0

2

1

6

8

7

3

5

4

3

0

3

6

4

7

1

8

2

5

4

0

4

8

7

2

3

5

6

1

5

0

5

7

1

3

8

2

4

6

6

0

6

3

8

5

2

4

1

7

7

0

7

5

2

6

4

1

8

3

8

0

8

4

5

1

6

7

3

2

log_{3}

0

4

1

2

7

5

3

6

Abstractly, GF(q) = GF(p^{n })
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_{9 }[x]
(the ring
of the polynomials over F_{9 } ).

x^{9} - 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(p^{n })
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^{2} , p^{3}
... p^{n-1}

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

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

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

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:

(2006-04-05) The Trivial Field
F_{1} = 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).
Many 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 enligntening specializations aren't obvious.
For example, the classical groupSL(n,F)
is identified with the symmetric groupS_{n} when F = F_{1}

(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_{2} 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 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 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^{2n }) 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 (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 "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_{2 } (pronounced "onto").

On_{2 }
is meant to stand for "Ordinal numbers with characteristic 2".

We may call nimbers the elements of
On_{2 } especially the finite ones...

Nim-multiplication table
( F_{2} , F_{4} and
F_{16} are subfields of On_{2 })

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

2

0

2

3

1

8

10

11

9

12

14

15

13

4

6

7

5

3

0

3

1

2

12

15

13

14

4

7

5

6

8

11

9

10

4

0

4

8

12

6

2

14

10

11

15

3

7

13

9

5

1

5

0

5

10

15

2

7

8

13

3

6

9

12

1

4

11

14

6

0

6

11

13

14

8

5

3

7

1

12

10

9

15

2

4

7

0

7

9

14

10

13

3

4

15

8

6

1

5

2

12

11

8

0

8

12

4

11

3

7

15

13

5

1

9

6

14

10

2

9

0

9

14

7

15

6

1

8

5

12

11

2

10

3

4

13

10

0

10

15

5

3

9

12

6

1

11

14

4

2

8

13

7

11

0

11

13

6

7

12

10

1

9

2

4

15

14

5

3

8

12

0

12

4

8

13

1

9

5

6

10

2

14

11

7

15

3

13

0

13

6

11

9

4

15

2

14

3

8

5

7

10

1

12

14

0

14

7

9

5

11

2

12

10

4

13

3

15

1

8

6

15

0

15

5

10

1

14

4

11

2

13

7

8

3

12

6

9

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:

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

Note that, in an additive group,
a + 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_{2 } 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^{2}
(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_{2 }.)

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

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

rim(n)

0

1

3

2

7

6

4

5

14

15

13

12

9

8

10

11

30

31

29

28

25

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

Because
x < [ 2^{2n} ] 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^{2n} satisfactory values of
u_{n+1}

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

(2013-07-22) One step beyond Conway's On_{2} :
The On_{3}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)

On_{2} 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* = x^{pk}

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 )

=

( ac - db* ,
a*d + cb )

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 F_{3}
= (/3,+,.)
with trivial conjugation:

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:

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

+

0

1

2

3

4

5

6

7

8

0

0

1

2

3

4

5

6

7

8

1

1

2

0

4

5

3

7

8

6

2

2

0

1

5

3

4

8

6

7

3

3

4

5

6

7

8

0

1

2

4

4

5

3

7

8

6

1

2

0

5

5

3

4

8

6

7

2

0

1

6

6

7

8

0

1

2

3

4

5

7

7

8

6

1

2

0

4

5

3

8

8

6

7

2

0

1

5

3

4

Ternary Multiplication

x*

0

1

2

3

4

5

6

7

8

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

2

3

4

5

6

7

8

2

2

0

2

1

6

8

7

3

5

4

6

3

0

3

6

2

5

8

1

4

7

7

4

0

4

8

5

6

1

7

2

3

8

5

0

5

7

8

1

3

4

6

2

3

6

0

6

3

1

7

4

2

8

5

4

7

0

7

5

4

2

6

8

3

1

5

8

0

8

4

7

3

2

5

1

6

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 [ ].

(2006-03-22 & 2013-07-24) Beyond On_{2} and On_{3}...
Defining On_{p} 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 n^{2}+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 < [3^{2n}] then
x [3^{2n }] = [x 3^{2n }]

The ternary square
of u_{n} = [3^{2n }] is
u_{n}+ v_{n} where
v_{n}< u_{n}.

A slight generalization would be to let the square of
u_{n} be w_{n}u_{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:

The first relation means 3^{2} = 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_{4} = 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^{2n}-1]
if and only if:

(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
x^{k} ¹ 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 [ 3^{2n}-1 ]
appear below, at row n or less :