On discrete exponentiation

David Pierce

2006.02.17

Some of these remarks might be incorporated into my notes for Math 111, or an article on induction.

An inductive structure is one in which proof by induction is possible: so it is a structure that has a distinguished element and a singulary operation, but has no proper substructures. Usually the distinguished element is 0, and the operation is x ↦ x + 1. On such a structure, the operations of addition and multiplication can be defined.

Let 𝔄 be an inductive structure. Then there is a homomorphism h from (ω,′, 0) into 𝔄. If A is infinite, then h is an isomorphism. If A is finite, then 𝔄 has two (finite) cardinal invariants, which determine its isomorphism class:

(1) min{x ∈ ω : ∃y h(x + y + 1) = h(x)};

(2) min{y ∈ ω : ∃x h(x + y + 1) = h(x)}.

Indeed, call these numbers k and n; then A has k + n + 1 elements, say

0, 1, …, k, k + 1, …, k + n;

and s^{𝔄}(x) = x + 1, if x ≠ k + n, but s^{𝔄}(k + n) = k. If k = 0, then the structure is isomorphic to ℤ/(n + 1).

Exponentiation on inductive structures is an operation

(x, y) ⟼ x^{y}

such that

x^{0} = 1;
x^{y+1} = x^{y} · x.

The value of 0^{y} is unimportant and can be left undefined.

Naïvely, but wrongly, one might argue that expontiation exists by induction: For, x^{0} is defined, and if x^{y} is defined, then x^{y+1} is defined.

A correct way to proceed would be to define a family of functions f_{x}, where x ≠ 0, such that

f_{x}(0) = 1;
f_{x}(y + 1) = f_{x}(y) · x.

One may define f_{1} as y ↦ 1; then one attempts to define f_{x+1} in terms of f_{x}. But the attempt must fail, since if the structure is ℤ/(3), then 2^{0} = 1, 2^{1} = 2, 2^{2} = 4 = 1, so 2^{3} = 2; but also 2^{3} = 2^{0} = 1, so 2 = 1, which is absurd.

However, exponentiation is well-defined as a function from

𝔽_{p}^{×} × ℤ/(p − 1)

into

𝔽_{p}.

This is by the Fermat theorem

x^{p−1} ≡ 1 (mod p).

Also, 𝔽_{p}^{×} has a generator, α. Then we have the inductive structure

(𝔽_{p}^{×}, s, 1).

where s is x ↦ x · α. We also have an isomorphism f_{α} from ℤ/(p − 1) into this structure, namely

y ⟼ α^{y}.

Let f_{1} be y ↦ 1 as before, and given f_{x} as desired, define

f_{s(x)}(y) = f_{x}(y) · f_{α}(y).

Then f_{s(x)}(0) = 1, and

f_{s(x)}(y + 1) = f_{x}(y + 1) · f_{α}(y + 1)
= f_{x}(y) · x · f_{α}(y) · α
= f_{x}(y) · f_{α}(y) · x · α
= f_{s(x)}(y) · s(x).