PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite Fields: Root Sets, Frobenius, and Algebraic Structure

Hongfeng Wu, Li Zhu

arXiv:2610.36727v1math.NTcs.ITmath.IT

TL;DR

The book asks how root sets that form fields and orbit lengths that determine irreducible-polynomial degrees share a common origin. It develops finite-field theory through Frobenius orbits, root sets, and linear actions, showing how these perspectives connect while preserving different information.

  • Problem

    The book asks how root sets that form fields and orbit lengths that determine irreducible-polynomial degrees share a common origin in finite-field theory.

    Source: Preface · p. 3

  • Method

    The book develops finite-field theory by treating relative Frobenius as an action on conjugate orbits and as a linear operator linked to normal bases and cyclic shifts.

    Source: Preface · p. 3

  • Results

    Frobenius conjugacy, group periods, and cyclic linear structure are presented as different descriptions of the same action, while orbit length alone does not determine the span dimension of conjugates.

    Source: Preface · p. 3

  • Takeaways & Limitations

    Bounds on the number of roots provide a common tool for proving multiplicative-group cyclicity, trace-map nonvanishing, and the existence of cyclic vectors.

    Source: Preface · p. 3

    Orbit length does not determine conjugate-span dimension, and distinct roots do not retain repeated-factor information.

    Source: Preface · pp. 3–4

Abstract

from arXiv · show

This monograph develops finite field theory through root sets, Frobenius orbits, trace duality, and cyclic modules, with applications to polynomial constructions and algebraic coding theory. Root-set descent and base extension are expressed through finite reduced algebras, while linearized polynomials connect normal bases, invariant subspaces, and linear recurrences. Coefficient pairings and derivative formulas recover information lost by trace pairings in quotient algebras with repeated factors. Cyclotomic cosets are studied through additive stabilizers, power substitution, and compatible factor lifting, including extensions to Galois rings. A central theme connects low-degree representations of subfields with conjugate root blocks, polynomial composition, and recovery from relative trace data. Return maps on root fibers determine factor degrees and organize constructions of irreducible polynomials, affine symmetries, and permutation polynomials. Applications include cyclic and constacyclic codes, BCH and Goppa distance bounds, rank-metric codes, trace codes, and Fourier support. Character orthogonality and Gauss and Jacobi sums yield counting formulas, a proof of the primitive normal basis theorem, and recurrences for extension-field character sums. Gaussian periods connect these methods with short linear relations in multiplicative subgroups. Proofs of Weil bounds for polynomial character sums combine auxiliary polynomials with generating polynomials and estimates for their reciprocal roots. The emphasis throughout is on explicit arguments connecting field structure, orbit structure, and linear dependence.

Edition and Contact Information

This section provides edition and contact information for the lecture notes, including their translation history, compilation date, and institutional affiliations.

Edition and Contact Information

Hongfeng Wu; Li Zhu

Reading Guide and Notation

This section guides readers through recurring structures—root sets, Frobenius orbits, trace duality, and cyclic modules—and maps chapter dependencies, while establishing notation and conventions for finite fields, operators, and polynomial statements.

Reading Guide

  • Read Chapters 1–4 before Chapters 6–9 alongside Chapter 5, tracing how root sets, fixed fields, trace duality, linearized polynomials, and cyclic modules interact.This path connects field structure, multiplicative periods, and Frobenius action; the guide also recommends Chapters 10–11 for factorization and irreducible-polynomial constructions, with Chapter 19.1–19.5 as a related reading.Source: Reading Guide and Notation · p. 9
  • The reading paths connect Chapter 18’s character and Fourier methods with Chapters 6–8, and connect primitive normal bases with Chapter 9’s cyclic modules and trace duality.For extension-field character-sum recurrences, the guide points back to Chapter 16’s recurrences and generating functions; Appendix C supplies the arithmetic completion for all parameters.Source: Reading Guide and Notation · p. 10
  • Chapter 5’s compatible lifting and Galois-ring methods connect local root-of-unity orbits to lifted factors, while Chapter 17 uses consecutive zeros for BCH bounds and trace coordinates for cyclic codes.Affine return on finite fibers determines factor degrees after lifting; support periods determine indecomposable coordinate blocks in cyclic codes.Source: Reading Guide and Notation · p. 13
  • The guide links the return-map lemma to root-set symmetry, recursive constructions, fiber permutations, and affine compression, and connects subfield representation degrees to root-block coefficients and relative-trace data.A short trace prefix recovers divisor-subfield degree profiles, and exact counts determine minimum generator-representation degrees.Source: Reading Guide and Notation · p. 14
  • Examples and exercises illustrate representation changes, recurrence recovery, trace degeneracy, and the separation of transient and periodic behavior in quotient algebras.The guide also notes a binary Goppa code of distance exactly nine from two subfield root sets in the field with 64 elements.Source: Reading Guide and Notation · pp. 14–15
  • The appendices collect algebraic preliminaries, algebraic-closure and automorphism material, the arithmetic verification of the primitive normal basis theorem, and exercise solutions.The book’s structural overview, notation index, and subject index help readers navigate its results and connections.Source: Reading Guide and Notation · p. 15

Notation

  • Write p for a prime, q = p^r, k = F_q ⊆ E = F_{q^n}, σ(x) = x^q, and φ(x) = x^p; [E : k] is the extension degree and Aut_k(E) fixes k pointwise.X usually denotes polynomials in field elements, while T denotes polynomials in operators.Source: Reading Guide and Notation · p. 15

Conventions

  • Field homomorphisms preserve identity, and finite fields of a given order are unique up to isomorphism; subfield operations and root-set comparisons use a specified common extension.Source: Reading Guide and Notation · p. 15
  • Statements allowing polynomial degrees below a positive integer include the zero polynomial.Source: Reading Guide and Notation · p. 15

Chapter 1 Existence of Finite Fields: Characteristic, Adjoining Roots,

The supplied contents entries span topics in Frobenius orbits, root descent, polynomial factorization, base extension, and trace duality.

Orbit structure and descent

Element representations and multiplicative orders

Roots of unity and base extension

Trace duality and factorization

  • The listed material includes trace and coefficient pairings, derivatives, dual bases, tower duality, discriminants, and Frobenius factorization methods.The contents also name Berlekamp and equal-degree factorization, normal elements, and computational costs.Source: Chapter 1 Existence of Finite Fields:… · pp. 19, 21

Chapter 11 Root Fibers, Return Periods, and Irreducible Constructions301

The contents map constructions across root fibers, stabilizers, subfield representations, and polynomial composition. Later entries include recursive lifting and permutation-polynomial topics.

Chapter 11 Root Fibers, Return Periods, and Irreducible Constructions301

  • Chapter 11 lists root-fiber return maps, binomial and quadratic constructions, additive trace conditions, and root-field spectra; Chapter 12 turns to stabilizers and Frobenius recovery of irreducible factors.Source: Chapter 11 Root Fibers, Return… · p. 21

Chapter 13

14.5 Recursive Quadratic Lifting: Self-Reciprocal Orbits

Chapter 15

  • The contents also list function algebras, low-degree polynomial representatives, permutation polynomials, value sets, power sums, and the AGW criterion.Source: §14.6 · p. 22

Chapter 16 Linear Recurrences and Recovery from Finite Observations501

Chapter 16 organizes linear recurrence relations around shift operators, quotient algebras, trace representations, periods, and recovery from finite observations.

16.1 The Shift Operator and Linear Recurrence Relations

16.6 Recovering Recurrences from Finite Observations: The Berlekamp–Massey Algorithm

16.2 A Quotient-Algebra Model of the Recurrence Space

16.3 Trace Representations and Conjugate Decomposition of Recurrences

16.4 Primitive Polynomials and Maximum-Length Sequences

16.5 Transients, Eventual Periods, and Rational Generating Functions

Chapter 19 Exact-Period Layers, Affine Compression, and Orbit Counts681

These passages characterize finite subfields through their distinct roots and Frobenius fixed points, relating their size to complete splitting and separability. They also describe finite splitting extensions obtained by adjoining roots.

1.1 Characteristic and the Prime Field

  • A finite field has prime characteristic p and order p^n, while a finite extension of a field of order q and degree n has order q^n.The degree is dimension over the specified base field, and the tower law multiplies extension degrees.Source: §1.1 · p. 27, §1.2 · p. 29

1.5 Adjoining Finitely Many Roots and Complete Splitting

  • Every nonconstant polynomial has a finite-degree splitting extension, and the construction also works for polynomials with repeated roots.Roots are adjoined successively using irreducible factors; when the base field is finite, the resulting splitting field is finite.Source: §1.5 · pp. 31–32

1.6 The Field Structure of Frobenius Fixed Points

  • For every prime p and positive integer n, the roots of X^(p^n) − X form a field with exactly p^n elements.The polynomial splits in a finite extension and has simple roots; closure of its root set under field operations makes that set a subfield.Source: §1.6 · p. 33
  • Given a field k of q elements, for every m ≥ 1 there is an extension E ⊇ k with |E| = q^m and [E : k] = m.Take the roots of X^(q^m) − X in a splitting extension; the closure argument gives a field containing k with the stated order and degree.Source: §1.6 · p. 33

1.7 The Root Polynomial of a Finite Subfield

  • A finite subfield S of order p^n has root polynomial X^(p^n) − X, so finite subfields of the same order in a common extension coincide.The monic polynomial with roots S divides X^(p^n) − X and has the same degree, identifying S with its complete root set.Source: §1.7 · p. 34
  • The distinct roots 0 and the three cube roots of unity form F4, whose monic root polynomial is X^4−X, but this simple-root polynomial does not encode the original multiplicities.In the example, zero has multiplicity one and each nonzero root has multiplicity two in the original polynomial.Source: §1.7 · pp. 34–35
  • The fixed points of an identity-preserving field homomorphism form a subfield; for φ^n in characteristic p, complete splitting and separability give exactly p^n fixed points.Finiteness of the field and surjectivity of the homomorphism are not needed for the subfield claim.Source: §1.7 · p. 35

Finite Fields

These parts develop finite-field structure and arithmetic through minimal polynomials, root matching, and quotient-ring constructions, including uniqueness of finite fields of a given order and cyclicity of their multiplicative groups. They also treat primitive elements, inverses, and isomorphisms between quotient-ring models, distinguishing generators of an extension from generators of its multiplicative group and emphasizing that coordinate conversions must respect defining polynomial relations.

2.1 Minimal Polynomials and Fields Generated by One Element

  • An algebraic element’s minimal polynomial is unique and irreducible, divides every polynomial that vanishes at it, and yields the basis 1, α, …, α^(d−1) for k(α).The degree d of the minimal polynomial is the extension degree.Source: §2.1 · p. 38

2.2 Extending a Base-Field Isomorphism After Adjoining a Root

  • A base-field isomorphism extends uniquely after adjoining a root, provided the image minimal polynomial has that root in the target extension.The resulting isomorphism restricts to the given base-field map and sends the adjoined element to the chosen root.Source: §2.2 · pp. 39–40

2.3 Matching Roots and Uniqueness of Splitting Fields

  • Matching roots extends base-field isomorphisms between splitting fields; consequently, fields of order p^n are isomorphic fixing their prime fields, and extensions of equal order over k are isomorphic fixing k.The finite fields of each prime-power order therefore have a unique isomorphism type, though individual isomorphisms need not be unique.Source: §2.3 · pp. 40–41

2.4 Combining Elements of Coprime Orders

  • In a finite abelian group, commuting elements of coprime orders have a product of order equal to their product, and some element has order equal to the group’s exponent.The exponent is the least common multiple of all element orders.Source: §2.4 · p. 42

2.5 The Root Bound and Multiplicative Cyclicity

  • Every finite subgroup of a field’s multiplicative group is cyclic: its elements are roots of X^M − 1, while the group contains an element of order M.For a field with Q elements, the multiplicative group has order Q − 1; the equation x^t = 1 has exactly gcd(t, Q − 1) solutions.Source: §2.5 · pp. 42–43

2.6 Successively Increasing the Multiplicative Order: Gauss’s Method

  • Gauss’s method constructs a primitive element by repeatedly increasing an element’s order, terminating because each increase is strict and the field is finite.The construction combines selected prime-power factors of two element orders to obtain a larger order; its computational complexity depends on finding orders and factoring integers.Source: §2.6 · pp. 43–44

2.7 Primitive Elements Make Finite Extensions Simple

  • A primitive element generates every finite extension over its base field, giving a monic irreducible polynomial of every positive degree and quotient-ring models for all extensions of that degree.For monic irreducible f of degree n over a field k of q elements, k[X]/(f) has q^n elements, and every such extension is isomorphic to that quotient over k.Source: §2.7 · pp. 44–45

Arithmetic

  • In k[X]/(f), each element has a unique polynomial representative of degree less than n, and arithmetic is performed using remainders modulo f.For nonzero representatives, the extended Euclidean algorithm supplies inverses because f is irreducible.Source: Arithmetic · pp. 45–46
  • The element α has order fifteen and is primitive; irreducibility alone ensures extension generation, while the theorem’s proof also yields primitive polynomials of every degree.Source: Arithmetic · p. 46
  • Direct multiplication verifies (1 + α2)(α3 + α + 1) = 1, agreeing with the Bézout calculation for the inverse.Source: Arithmetic · p. 46
  • Irreducible polynomials of the same degree give isomorphic quotient-field models, but conversion requires choosing a root, not simply identifying polynomial bases.Source: Arithmetic · p. 47
  • In F9, replacing α by β = 1 + α gives a model with a different minimal polynomial and an explicit field isomorphism with inverse coordinate map.Source: Arithmetic · p. 47

Frobenius: Subfields, Conjugates,

The section uses Frobenius fixed spaces and orbits to describe subfields, minimal polynomials, descent, and finite reduced-algebra structure, and relates periodic-point counts to irreducible-polynomial counts and Euler products. It also develops representations and order data for field elements and polynomials, including repeated roots, projective order, reciprocal irreducibles, and splitting fields of roots of unity.

3.1 The Order of Frobenius and the Extension Degree

  • The relative Frobenius on E/k has order m and fixed field k, and its powers generate Aut_k(E), a cyclic group of order m.The full automorphism group of a field with q^m elements has order rm.Source: §3.1 · p. 52, Theorem 3.3 · p. 52

Theorem 3.3

  • The relative Frobenius σ on E/k is an automorphism fixing k pointwise, and its fixed elements are exactly k.Its exact order is m.Source: §3.1 · p. 52

3.3 Subfields and Divisors of the Extension Degree

  • For every divisor d of m, E has a unique subfield with q^d elements, and E_d is contained in E_e exactly when d divides e.Every subfield containing k arises this way.Source: §3.3 · p. 53

3.4 Fixed Fields of Iterates, Intersections, and Composita

  • For d,e dividing m, E_d∩E_e=E_gcd(d,e) and their compositum is E_lcm(d,e); subfields correspond inclusion-reversingly to subgroups of the Frobenius group.More generally, Fix(σ^t)=E_gcd(m,t).Source: §3.4 · pp. 54–55

3.5 Orbits, Conjugates, and Minimal Polynomials

  • An element’s Frobenius period equals its degree over the base field, and its orbit consists of the distinct roots of its minimal polynomial.Thus extension degree, minimal-polynomial degree, and orbit length coincide.Source: §3.5 · pp. 55–56

3.6 Orbit Periods and Irreducible Factors of Power Polynomials

  • A monic irreducible polynomial of degree d divides X^(q^n)−X exactly when d divides n; this power polynomial contains each such irreducible factor once.Its factors are precisely the monic irreducibles whose degrees divide n.Source: §3.6 · p. 58

3.7 Descent of Root Sets and Decompositions of Function Algebras

  • For a monic separable polynomial, its coefficients lie in k exactly when Frobenius preserves its root set, and its irreducible factors correspond to Frobenius orbits.For repeated roots, descent requires preserving root multiplicities, and one orbit of distinct roots alone does not imply irreducibility.Source: §3.7 · pp. 59–60
  • For a stable root set, equivariant functions form a product of fields indexed by Frobenius orbits, and the fixed-subalgebra dimension counts irreducible factors.An orbit of length d contributes F_{q^d}; the fixed subalgebra is k^s for s orbits.Source: §3.7 · pp. 62–63

3.8 Finite Reduced Algebras and Abstract Frobenius Orbits

  • A finite-dimensional commutative reduced algebra over a finite field is a product of finite fields, equivalently one on which some Frobenius iterate fixes every element; its factor degrees are unique.The component degrees, including multiplicities, are determined up to reordering.Source: §3.8 · p. 64
  • For a reduced algebra, evaluation points correspond contravariantly to Frobenius orbits, with evaluation identifying the algebra with the equivariant functions on those points.The evaluation-point set has cardinality dim_k A, and algebra homomorphisms correspond to Frobenius-commuting maps in the reverse direction.Source: §3.8 · p. 66
  • Frobenius acts transitively on a reduced algebra’s evaluation points exactly when the algebra is a field; s orbits give fixed subalgebra k^s and exactly 2^s idempotents.Abstract orbit sets need not come from univariate polynomial quotients, and evaluation points alone cannot detect nilpotents.Source: §3.8 · pp. 68–70

3.9 Recovering Algebra Decompositions from Frobenius Fixed Spaces

  • The integer dimensions of Frobenius fixed spaces, through two Möbius inversions, uniquely determine all field components of a finite reduced algebra.The characteristic polynomial alone does not provide the relevant data.Source: §3.9 · pp. 70–71
  • Similar Frobenius operators characterize isomorphic finite-dimensional commutative reduced algebras, while fixed-space dimensions distinguish examples with identical characteristic polynomials.Reducedness is essential: Frobenius similarity does not recover the algebra structure when nilpotents are present.Source: §3.9 · pp. 72–73

3.10 Frobenius Descent of Multivariate Linear Factors

  • For a normalized multivariate linear factor, its coefficientwise Frobenius orbit product descends to the base field and is irreducible exactly when it is a scalar multiple of the polynomial.The orbit length is the least common multiple of the coefficient degrees, and the descended product has that total degree.Source: §3.10 · p. 74

3.11 Counting Irreducible Polynomials

  • Möbius inversion converts the divisor-sum identity for finite-field elements into a count of monic irreducible polynomials of each degree.The count groups elements by minimal polynomial; each irreducible polynomial of degree d contributes d distinct roots.Source: §3.11 · p. 75

Example 3.37

  • Over F2, there is exactly one monic irreducible quadratic and two monic irreducible cubics.The formula counts irreducibles of prescribed degree by dividing elements of exact period n into Frobenius orbits of size n.Source: Example 3.37 · p. 76

3.11.1 Möbius Inversion for Periodic-Point Counts

  • Möbius inversion recovers the number or aggregate value of objects of exact period n from cumulative data for periods dividing n.The relations hold for values in any additive abelian group and have a multiplicative analogue for multiplicative abelian groups.Source: §3.11.1 · p. 76

3.11.2 From Orbit Counts to Euler Products

  • The formal Euler product over monic irreducible polynomials connects unique factorization, polynomial-degree counts, and Frobenius fixed-point counts.An orbit of length d contributes d fixed points under the r-th iterate exactly when d divides r.Source: §3.11.2 · p. 77

Polynomial Orders

  • Multiplicative order records an element’s cyclic subgroup, while its Frobenius period records the field extension it generates.Quotient-ring coordinates and multiplication matrices make these invariants accessible to polynomial computations; repeated factors encode contributions from characteristic powers.Source: Polynomial Orders · p. 81

4.1 Coordinates for Computing with Field Elements

  • In a polynomial basis, field elements have unique coordinates and multiplication reduces polynomial products modulo the minimal polynomial; a primitive-element exponent representation makes multiplication, inversion, and powers arithmetic on exponents.Addition in exponent coordinates requires a Zech logarithm table or conversion to polynomial-basis coordinates.Source: §4.1 · pp. 81–82
  • Tower coordinates preserve the field and do not change minimal polynomials, conjugacy orbits, or element orders.Writing elements with bases for L/k and E/L gives unique coordinates for elements of E.Source: §4.1 · p. 82

4.2 The Regular Representation by Multiplication

  • Every n-dimensional matrix model of an extension E/k of degree n is obtained from its regular multiplication representation by one simultaneous change of basis.The representation preserves multiplication relations and the annihilating polynomials of multiplication matrices.Source: §4.2 · pp. 82–83

4.3 Multiplicative Order and Frobenius Period

  • For nonzero a of multiplicative order e, its Frobenius period and degree are ord_e(q), while its multiplication matrix has order e and Frobenius-conjugation period equal to its degree.For powers a^t, the degree is ord_{e/gcd(e,t)}(q); membership in F_{q^r} is equivalent to e/gcd(e,t) dividing q^r−1.Source: §4.3 · pp. 84–85

4.4 Polynomial Orders and the Contribution of Repeated Factors

  • If f has distinct irreducible factors with orders e_i and maximum multiplicity A, then ord(f)=e p^b, where e=lcm(e_i) and b is least with p^b≥A.The part coprime to the characteristic comes from distinct roots, while the p-power records multiplicities; for gcd(e,q)=1, there are ϕ(e)/ord_e(q) irreducibles of order e, each of degree ord_e(q).Source: §4.4 · pp. 86–87

function

  • The polynomial Euler totient counts unit classes in k[T]/(F); h gives a basis through its successive T-multiples exactly when gcd(h,F)=1, and ord(f)=q^d−1 characterizes primitive f.The basis criterion identifies the count used to reduce normal-element counting to counting units in a quotient ring.Source: §4.5 · p. 87, function · p. 88

4.6 Projective Orders Modulo Base-Field Scalars

  • Projective order is the order of the class of X modulo nonzero base-field scalars, and f is primitive exactly when this order is (q^d−1)/(q−1).This identifies powers of X that differ by a nonzero scalar in k.Source: §4.6 · pp. 88–89

4.6.1 Projective Order and Minimal Binomial Multiples

  • Root ratios and maximum root multiplicity determine the projective order and the least-degree binomial multiple divisible by f.The root-ratio orders combine by least common multiple, while the required p-power is the least p^b at least the maximum multiplicity.Source: §4.6.1 · pp. 89–90
  • For an irreducible polynomial whose root has order N, its projective order is N gcd(N,q−1).Minimal binomial multiples depend on root ratios and multiplicity, unlike expressions G(X^r), which require multiplicative symmetry of the whole root set; for example, f^3 with f=X^3+X+1 has minimal binomial multiple X^28+1.Source: §4.6.1 · p. 90

4.7 Reciprocal Polynomials and Inverse-Root Orbits

  • A monic irreducible polynomial is self-reciprocal only if it is X − 1, X + 1, or has degree 2s with each root satisfying α^(q^s+1) = 1; this condition is also sufficient.Self-reciprocity means inversion sends a root into its own Frobenius orbit.Source: §4.7 · p. 91
  • For roots of order e > 2, self-reciprocity is equivalent to −1 belonging to ⟨q⟩ modulo e, or equivalently d = ord_e(q) being even with q^(d/2) ≡ −1 (mod e).Reciprocity pairs the irreducibles that are not fixed; even degree alone does not imply self-reciprocity, as shown by the order-eight quadratic example over F3.Source: §4.7 · pp. 91–92

5.1 The Splitting Field of the Roots of Unity

  • For gcd(N, q) = 1, the splitting field of X^N − 1 over F_q is F_(q^s), where s = ord_N(q); in characteristic p, p-power factors give multiplicity p^a rather than additional distinct roots.The distinct roots remain μ_M, so characteristic p has no nontrivial p-th roots of unity.Source: §5.1 · pp. 95–96

Root-Set Definition

The section develops explicit descriptions of polynomial root sets and Frobenius orbits, using cyclotomic cosets, compatible factor lifting, trace and norm, and return maps to study factorization and solvability. It also treats trace and coefficient duality, quotient algebras, quadratic roots, and linearized polynomials through their root spaces and associated linear maps.

Root-Set Definition

  • Cyclotomic polynomials are defined by grouping roots of unity by order, and their identities uniquely determine them with integer coefficients.After reduction modulo p, when p does not divide N, ΦN has precisely the primitive N-th roots of unity as roots.Source: Root-Set Definition · p. 96

5.3 Cyclotomic Cosets and Exponent Orbits

  • Frobenius orbits of exponents modulo N determine irreducible factors of ΦN over Fq, with each q-cyclotomic coset giving a factor.For gcd(N,q)=1, each factor has degree ord_N(q), so ΦN is irreducible exactly when ord_N(q)=ϕ(N). For a multiplicative coset of a subgroup, the quotient orbit determines how its root polynomial changes under Frobenius and when its coefficients lie in the base field.Source: §5.3 · pp. 97–98

5.3.1 Coset Leaders and Order-Preserving Filtering

  • Order-preserving scaling maps q-cyclotomic cosets modulo n to corresponding cosets modulo N=cn, enabling leader filtering without changing orbit lengths.Retain leaders divisible by c, then divide by c to recover the leaders modulo n; the resulting root-set construction also gives BCH generator polynomials for consecutive roots.Source: §5.3.1 · pp. 99–101

5.4 Irreducibility of Cyclotomic Polynomials

  • ΦM is irreducible over Fq exactly when ordM(q)=ϕ(M), equivalently when q generates the unit group modulo M.The proposition limits this possibility to moduli whose unit groups are cyclic; for those moduli, q must still be checked as a generator.Source: §5.4 · p. 102

5.5 Base Extension and Orbit Step Size

  • Over Fqr, an irreducible degree-d polynomial splits into gcd(d,r) irreducible factors, each of degree d/gcd(d,r).It remains irreducible exactly when gcd(d,r)=1 and splits completely exactly when d divides r.Source: §5.5 · p. 104
  • Each factor after base extension is irreducible over, and has coefficients generating, the intersection of the enlarged base field and the original splitting field.Under the stated hypotheses, this coefficient field is Fqg = Fqd ∩ Fqr.Source: §5.5 · p. 105

5.6 Multiple Equal-Difference Structure of Cyclotomic Cosets and Binomial Descent

  • For roots of unity, extending the base field splits Frobenius orbits into suborbits, and complete equal-difference suborbits yield binomials with forced zero coefficients.The resulting lower-degree polynomials are suited to computation.Source: §5.6 · p. 106

5.6.1 Complete Equal-Difference Root Blocks and the Coarsest Partition

  • A root polynomial is a binomial exactly when its exponent set is a complete equal-difference block; consequently, a cyclotomic coset gives an irreducible binomial exactly when it is such a block.The block must be a complete additive coset, not merely a finite arithmetic-progression segment.Source: §5.6.1 · pp. 106–107
  • The additive stabilizer H+(C) defines the unique coarsest decomposition of a cyclotomic coset; admissible block sizes are precisely its positive divisors, with a unique decomposition for each size.For step m, all q^m-suborbits are complete equal-difference blocks exactly when ωC | m, where ωC = |C|/|H+(C)|.Source: §5.6.1 · pp. 107–108
  • For a multiplicative orbit C = uH, an additive subgroup I stabilizes C exactly when 1 + I ⊆ H, independently of the unit representative u.Thus the multiplier group directly identifies the orbit's multiple equal-difference structure.Source: §5.6.1 · p. 109

15. Then

  • For q = 2 modulo 15, the coset C1 has no complete equal-difference block larger than a singleton, so its only such decomposition is the singleton partition.Although {1, 2} is an arithmetic progression, it is not a complete equal-difference block modulo fifteen.Source: §15 · p. 110

5.6.2 An Explicit Formula for the Least Step and the Dyadic Exception

  • For C_i with d = N/gcd(N,i), the entire coset is a complete equal-difference block exactly when rad(d) | q − 1 and, if 8 | d, q ≡ 1 (mod 4); then its size is ord_d(q) = d/gcd(d,q − 1).The dyadic condition is the additional exception when 8 divides d.Source: §5.6.2 · p. 110
  • The least Frobenius step producing complete equal-difference suborbits is determined explicitly from ρ = ord_rad(d)(q), with an additional parity condition when 8 | d and q^ρ ≡ 3 (mod 4).The maximal block has common difference N/κC, and the coarsest decomposition has ωC blocks.Source: §5.6.2 · p. 112
  • If a coset is itself a complete equal-difference block, its leader satisfies λN(i) = [i]N/τ.Maximal-block calculations also show that parameters depend on N/gcd(N, i), not only on N.Source: §5.6.2 · p. 114
  • In the 324-element orbit example, maximal-block compression reduces the coset-leader search to two modular reductions.The passage states that τ and ωC are calculated from multiplicative orders and valuations.Source: §5.6.2 · p. 114

Composition, and Binomial Descent

  • For r | κC, the minimal polynomial of α^r has degree τ/r, and the associated irreducible binomials have root exponent sets equal to the blocks of size r.When r = κC, the power map reduces the orbit length from τ to ωC.Source: Composition, and Binomial Descent · pp. 115–116
  • MC(X) lies in k[X^r] exactly when r | κC; consequently, κC is the gcd of its nonzero exponents and [k(α^κC) : k] = ωC.The power map α → α^κC compresses each maximal complete equal-difference root block to one value.Source: Composition, and Binomial Descent · p. 116
  • Every irreducible factor of XN − 1 is binomial exactly when every q-cyclotomic coset is a complete equal-difference block, rad(N) | q − 1 with q ≡ 1 (mod 4) if 8 | N, or N | t(q − 1).Over Fq^m, all factors are binomials exactly when ωN | m.Source: Composition, and Binomial Descent · p. 118

5.6.4 Three-Sparse Factorizations and Images under Root Squaring

  • For odd q and n = p^a m with gcd(m, p) = 1, Xn − 1 is 3-sparse over k exactly when rad(m) | q^2 − 1.The passage also states that 3-sparsity depends on m, not on factor multiplicities.Source: §5.6.4 · p. 120
  • Over F3 and F9, the 3-sparse polynomials X^n−1 have lengths n=3^a2^b and n=3^a2^b5^c, respectively; squaring roots can destroy trinomial form.For example, X^13−1 is not 3-sparse over F3, although the root-squared image remains an irreducible cubic with four nonzero terms.Source: §5.6.4 · pp. 121–122

5.6.5 The Exceptional Family of Powers of Seven in Characteristic Two

  • In characteristic two, 3-sparsity is governed by prime-divisor and power-of-seven Frobenius-order conditions, with explicit classifications over F2 and F4.For n=2^λm with m odd, over F2 the criterion is m=3^u or 7^v; over F4 it is m=3^u5^v, 7^A, or 3·7^A. The exceptional conditions include rad(s0)|q−1, 3∤s0/gcd(s0,q−1), and ord_{7^a}(q)=3·7^{a−1}; the final order conditions are equivalent to A=1 or 7∤e.Source: §5.6.5 · pp. 122–123
  • In the powers-of-seven family, omitting the restriction 3∤s0/gcd(s0,q−1) can produce a four-term irreducible factor, and maximal Frobenius orbit length can fail after base extension.The characteristic-two sparse product identity holds over every such finite field, but when 7|e and a≥2, the trinomials split further and their irreducible factors may have more terms.Source: §5.6.5 · pp. 123–124

5.6.6 Cyclotomic Polynomials of Low Order and Coefficient Recurrences

  • Under rad(n)|q+1 and v2(n)≤v2(q+1), monomial lifting yields ϕ(m)/2 distinct irreducible factors of degree 2t.The coefficients are generated in the base field by c0=2, c1=c, and c_{j+1}=c·c_j−c_{j−1}; the lifting identity is Φ_n(X)=Φ_m(X^t).Source: §5.6.6 · p. 126
  • The trace parameter must certify exact root order, and the dyadic hypothesis is needed for lifted factors to remain irreducible.For an irreducible X²−cX+1, exact order m is characterized by c_m=2 and c_{m/ℓ}≠2 for every prime ℓ|m; without the dyadic condition, composed factors may split.Source: §5.6.6 · pp. 127–128

5.6.7 Unions of Orbits, Root Power Sums, and the Maximum Composition Exponent

  • The maximum monomial composition exponent of a root-set polynomial is its additive-stabilizer invariant, computable as the gcd of N and its nonzero root power-sum frequencies.Specifically, P_T∈k[X^r] exactly when r|κ_T, and κ_T=gcd(N,{j:s_j≠0}).Source: §5.6.7 · pp. 128–129
  • A union of cyclotomic cosets can have a larger additive stabilizer than its individual cosets, allowing translations to interchange roots from different factors.For q = 2 and N = 15, the union {0, 5, 10} has stabilizer of order three although each constituent coset has trivial stabilizer.Source: §5.6.7 · p. 130

5.7 Base Extension and Tensor Product Decompositions

  • For finite extensions of degrees a and b, their tensor product over the base field decomposes into gcd(a, b) field components, and its multiplication map is an isomorphism exactly when a and b are coprime.The multiplication map has domain dimension ab and target dimension ab/gcd(a, b).Source: §5.7 · p. 131

Direct Products, Tensor Products, and Changes of Orbit Step

  • Finite reduced k-algebras have Frobenius-equivariant evaluation-point descriptions for direct products and tensor products; extending the base to Fq^r changes relative Frobenius to τ^r.The tensor product remains reduced.Source: Direct Products, Tensor Products, and… · p. 132

5.8 Synchronization of Local Orbits and Explicit Factorization of Roots-of-Unity Polynomials

  • Local conjugate orbits combined by the Chinese remainder theorem may form multiple global orbits, distinguished by the relative phases of their components.The section gives nonredundant phase representatives for this local-to-global construction.Source: §5.8 · p. 134

5.8.1 Simultaneous Action and the Phase Quotient

  • For pairwise coprime moduli, simultaneous Frobenius action gives global orbits of length lcm(τ1, …, τs), indexed by the local phase quotient.The number of global orbits is the product of the local orbit lengths divided by their least common multiple.Source: §5.8.1 · p. 134

5.8.2 Local Representatives at Odd Prime Powers

  • For an odd prime power modulus ℓ^e, each valuation-y layer has orbits of length f_y, with nonredundant representatives obtained from unit-group cosets; zero is a separate orbit.The local calculation gives three nonzero orbits modulo 27, of lengths eighteen, six, and two.Source: §5.8.2 · pp. 136–137

5.8.3 From Local Representatives to Factors of Roots-of-Unity Polynomials

  • Local orbit data and phase representatives construct all Frobenius orbits modulo N, yielding roots-of-unity polynomial factors whose degrees are the least common multiples of local orbit lengths.Combining this enumeration with multiple equal-difference structure can compress root products and determine the least extension degree over which the factors are binomials.Source: §5.8.3 · pp. 137–138

5.8.4 Multiplier Orbits and Blocks of Factors

  • For indices of additive order d, an H-multiplier orbit has length |Hd|, and its root block contains |Hd|/ord_d(q) irreducible factors, each of degree ord_d(q).The block is irreducible exactly when Hd equals the subgroup generated by q modulo d.Source: §5.8.4 · p. 139

5.9 Cyclotomic Systems and Compatible Factor Lifting

  • Cyclotomic systems record compatibility of cyclotomic cosets across divisibility chains and correspond to compatible towers of irreducible factors; return permutations describe their lifting structure [73].The moduli are coprime to the characteristic.Source: §5.9 · p. 140

5.9.1 Reduction Maps and Compatible Systems

  • A compatible system is a sequence of orbits related by reduction, and the lifting tree can exhibit growth followed by splitting before lifts become unique [Theorem 5.66].For q = 3 in the dyadic example, orbit lengths are 1, 1, 2, 2, 4; from modulus eight onward, each lift is unique and doubles the length.Source: §5.9.1 · pp. 140–141

5.9.2 Affine Return on a Lifting Fiber

  • An affine return permutation on the lifting fiber indexes the lifted orbits, whose lengths equal the base orbit length times the return periods.For a prime lift, the return is the identity, a nonzero translation, or a map with one fixed point and nonzero cycles of order ord_ℓ(a).Source: §5.9.2 · pp. 142–143

5.9.3 Compatible Roots of Unity and Towers of Irreducible Factors

  • Compatible primitive roots make power substitution factor an irreducible polynomial into distinct irreducible factors, with degrees determined by return periods.Compatible factor sequences correspond uniquely to compatible orbit systems; lifting the modulus changes orbit branching, unlike base extension at a fixed modulus.Source: §5.9.3 · pp. 144–145

5.9.4 Admissible Digits and Compatible Representatives

  • Admissible digits give a unique parametrization of systems above an initial orbit and recursively produce compatible representatives, while local systems generally do not determine a total system.Independent coset-leader choices can break representative compatibility; combining local orbits globally also requires recording their relative phases.Source: §5.9.4 · pp. 146–147

5.9.5 Stable Growth of Local Systems

  • For a nonprincipal local system, deviation depth and local multiplicative orders determine orbit lengths and the stabilization index, from which every subsequent lift is unique.The theorem gives order-dependent cases, including separate formulas when ℓ = 2 and Q is congruent to 1 or 3 modulo 4.Source: §5.9.5 · pp. 147–148
  • For q = 3 and ℓ = 11, G(X^(11^t)) is irreducible of degree 5·11^t for every t ≥ 0.Here the stabilization threshold is modulus 121, despite the initial orbit length being 5.Source: §5.9.5 · p. 150
  • For primitive ℓ^a r-th roots, factors lift irreducibly with degree hℓ^(a−b), and their number is independent of a once a ≥ b.Only finitely many initial factorizations are needed for these primitive-root levels; arbitrary deviation depths need not share a common finite determining level.Source: §5.9.5 · pp. 149, 151, 152

5.9.6 Binomial Root Sets and Factorization with Multiplicities

  • For n coprime to the characteristic, Frobenius orbits on the exponent set of X^n−λ yield distinct monic irreducible factors whose degrees equal the orbit lengths.If n has a characteristic-power factor p^v, the distinct factors still have orbit-determined degrees and each occurs with multiplicity p^v.Source: §5.9.6 · p. 153

5.10.1 Quotient Ring Models and Coprime Hensel Lifting

  • In Galois rings, simple roots and pairwise coprime residue-field factors lift uniquely; the lifted factors remain pairwise comaximal.Roots of unity of order coprime to p retain their orbit structure, with factor coefficients uniquely determined by coprime Hensel lifting.Source: §5.10 · p. 154, §5.10.1 · pp. 155–156

5.10.2 Teichmüller Representatives and the Frobenius Automorphism

  • The Teichmüller representatives give unique digit expansions, and a unique ring automorphism lifts the p-th-power automorphism of the residue field.Reduction bijects the Teichmüller set with Fq, and its nonzero elements form a cyclic group isomorphic to Fq×.Source: §5.10.2 · p. 157
  • Relative Frobenius on an unramified Galois-ring extension has order d and fixed subring A, while the Galois-ring isomorphism type is independent of the defining polynomial.On Teichmüller elements, relative Frobenius acts by t ↦ t^q; in general it need not act as z ↦ z^q on the whole ring.Source: §5.10.2 · p. 158

5.10.3 Roots-of-Unity Orbits, Factor Lifting, and Quotient Ring Decompositions

  • For p ∤ n, q-cyclotomic orbits yield pairwise comaximal basic irreducible factors of X^n−1 with degree |C| and quotients isomorphic to GR(p^s, r|C|).Under base extension to GR(p^s, rt), a degree-d factor splits into gcd(d, t) basic irreducible factors of degree d/gcd(d, t).Source: §5.10.3 · pp. 159–160
  • An orbit factor is binomial exactly when its coset is a complete equal-difference block; at every precision, its nonzero exponents have greatest common divisor κ_C.In general, the factor also compresses through a basic irreducible polynomial of degree ω_C.Source: §5.10.3 · p. 160

5.10.4 Local Corrections Determined by the Derivative

  • When p ∤ n, a derivative-based local correction determines the unique monic factor lift of the same degree from a factor modulo p^j.The correction uses the remainder of X^n−1 modulo the lifted factor and the derivative-based quotient relation.Source: §5.10.4 · p. 161

5.10.5 Comaximal Blocks When the Residue Characteristic Divides the Exponent

  • When p divides n, canonical blocks are pairwise comaximal with local quotient rings and give a Chinese remainder decomposition, but generally cannot split further into comaximal factors.The identity B_C = F_C(X^pa) holds when r = 1; for s > 1, the power identity holds only after reduction modulo p.Source: §5.10.5 · p. 162
  • Exercises use cyclotomic orbits and return maps to analyze factorization, including twelve degree-twelve factors of Φ315 over F2 and thirty irreducible cubics of S91 over F9.Other exercises treat synchronized local orbits, valuation layers, binomial factors, and lifting roots-of-unity factors over residue rings.Source: §5.10.5 · pp. 166–168

Coordinates

  • Trace and norm arise from sums and products along conjugate orbits, and also represent traces and determinants of multiplication operators governing Frobenius difference equations.The trace splits equivariantly in a way that depends on the characteristic and extension degree.Source: Coordinates · p. 169

6.1 Orbit Sums and Orbit Products

  • Frobenius-invariant orbit sums and products give relative trace and norm; repeated conjugates remain in the formulas when the element lies in a proper subfield.For conjugate linear factors, the full orbit product evaluated at a base-field point is the norm of the corresponding linear expression, retaining all terms even if its value lies in a smaller subfield.Source: §6.1 · pp. 169–170

6.2 Surjectivity and Fiber Sizes

  • Trace and norm maps are surjective, with q^(n−1) elements in each trace fiber and (q^n−1)/(q−1) preimages of each nonzero norm value.Each nonempty norm fiber is a multiplicative coset of the norm kernel.Source: §6.2 · p. 171
  • When |k| > 2, a k-linear map preserving every norm is multiplication by a norm-one element followed by a k-automorphism.The result is identified as the finite-field case of Lenstra’s norm-form theorem [33, Theorem 4].Source: §6.2 · p. 171

6.3 Compatibility of Multiple Norms and Joint Fibers

  • Simultaneous nonzero norm prescriptions are solvable exactly when their values are compatible over pairwise subfield intersections; each compatible joint fiber is a multiplicative coset of the joint kernel.For q = 5 in the degree-six example, each compatible pair has exactly 21 common preimages.Source: §6.3 · pp. 172–173

6.4 Two Hilbert 90 Identities

  • The Frobenius difference equation x^q − x = a is solvable exactly when TrE/k(a) = 0, with q solutions; x^(q−1) = a for nonzero a is solvable exactly when NE/k(a) = 1, with q − 1 solutions.These are additive and multiplicative Hilbert 90: orbit differences and ratios reduce to a condition over the base field.Source: §6.4 · pp. 173–174
  • The map φθ bijects k ∪ {∞} with the norm-one group; in F9, its values at 0, 1, −1, and ∞ give μ4.Source: §6.4 · p. 174

6.5 Trace, Differences, and Equivariant Decomposition

  • When p ∤ n, trace splits E Frobenius-equivariantly as k ⊕ ker Tr, with D = σ − id invertible on ker Tr; when p | n, no such stable complement exists.In the latter case, k ⊆ ker Tr = im D and Tr² = 0.Source: §6.5 · p. 175

Prime Degree

  • For X^p − X − a over Fq, zero absolute trace gives complete splitting and nonzero trace gives irreducibility; every irreducible factor of X^n − λ has degree divisible by the stated norm-class order d.Source: Prime Degree · pp. 176–177

6.7 Explicit Solutions of Hilbert 90 Equations

  • Trace-zero a admits explicit solutions to x^q − x = a, norm-one a admits solutions to x^(q−1) = a, and quadratic solvability is characterized by the discriminant or additive Hilbert 90.The additive solution set is a coset −B + k; in characteristic two, a quadratic with B = 0 has a unique root, while the stated trace condition for B ≠ 0 yields two distinct roots.Source: §6.7 · pp. 177–179

6.8 Trace Fibers and Polynomial Factorization

  • Trace fibers factor X^q − X − b into X^r − X − β terms, irreducible of degree p when r = p and b ≠ 0; X^p − aX − b is irreducible exactly under the stated u-based trace condition.Source: §6.8 · pp. 179–180

6.9 Conjugate Coordinates, Tensor Product Decomposition, and Multiplication Operators

  • Conjugate coordinates make multiplication matrices simultaneously diagonalizable over E; their characteristic polynomials encode field trace and norm, while Frobenius has minimal polynomial T^n − 1.Frobenius is diagonalizable over a scalar field precisely when p ∤ n and all n-th roots of unity lie in that field.Source: §6.9 · pp. 180–182

6.10 Root Ratios and Coefficient Criteria for Primitive Quadratics

  • For irreducible quadratics, trace and norm encode the coefficients, while the conjugate-root ratio yields primitivity criteria, fixed-constant-term counts, and minimal binomial multiples.Source: §6.10 · p. 182

6.10.1 Root Ratios, Recurrence Remainders, and Projective Order

  • For an irreducible quadratic, the first positive zero of its Lucas recurrence is the projective order, determining its minimal binomial multiple and ordinary order.The zero index r divides q + 1, with minimal binomial multiple X^r − λ and ordinary order r ord(λ).Source: §6.10.1 · p. 183
  • The first zero recurrence coefficient determines projective order, while the preceding coefficient recovers the root-ratio parameter; maximal projective order q + 1 yields minimal binomial X^(q+1) − c.In that case the ordinary order is (q + 1) ord(c).Source: §6.10.1 · p. 184

6.10.2 Counting Primitive Quadratics with Fixed Norm

  • For even q, exactly ϕ(q + 1)/2 monic quadratics with fixed generator constant term c are primitive.Primitive elements of norm c occur in conjugate pairs, each pair defining one quadratic.Source: §6.10.2 · p. 184

6.10.3 Symmetric Cyclotomic Polynomials and Lucas Atoms

  • Every symmetric polynomial in two variables has a unique expression in their sum and product; the resulting Lucas atom encodes inverse pairs of primitive roots of unity.For c ≠ 0, its roots detect root ratios; the specialization is square-free in odd characteristic and every root has multiplicity two in characteristic two.Source: §6.10.3 · p. 185

6.10.4 Optimal Coefficient Determining Polynomials

  • The optimal coefficient polynomial P_q,c is monic, square-free, has roots in k, and vanishes exactly at coefficients b for which X^2 + bX + c is primitive.In even characteristic it is obtained as the unique square root of Λ_(q+1)(B,c).Source: §6.10.4 · p. 187
  • A recurrence-only test characterizes primitivity by U_N(b,c) = 0 and U_(N/ℓ)(b,c) ≠ 0 for every prime ℓ dividing N = q + 1.These conditions ensure the root ratio has order exactly N.Source: §6.10.4 · p. 188

6.11 Quadratic Root Sets in Additive Cosets and Frobenius Eigenspaces

  • The normalized roots of the quadratic family correspond to solutions in E = F_(q^4) split between V+ = K and V−, the two-dimensional relative-Frobenius eigenspaces.The V+ solutions correspond to reducible members and the V− solutions to irreducible members.Source: §6.11 · p. 189
  • The split and anisotropic quadratic forms yield q − 1 and q + 1 solutions, respectively, so the family has (q − 1)/2 reducible and (q + 1)/2 irreducible members.Irreducible members correspond to nonsquare norm parameters z in K satisfying z − z^q = Δ, via a = μ²(z − 1/4).Source: §6.11 · pp. 190–191

7.1 Nondegeneracy of the Trace Pairing

  • Every k-linear functional on E has a unique representation x ↦ TrE/k(ax), and every ordered k-basis has a unique trace-dual basis.The trace pairing is nondegenerate, so dual bases recover coordinates through trace evaluations.Source: §7.1 · pp. 197–198

7.2 Interpolation and the Dual of a Power Basis

  • Interpolation constructs the trace-dual basis of a power basis and identifies the top-coefficient functional with a trace weighted by 1/f′(α).The derivative normalization also lets conjugate evaluations be summed into a base-field coefficient, connecting low-degree subfield intersections with relative-trace orthogonality and recurrence sequences.Source: §7.2 · pp. 198–200
  • For coprime squarefree polynomials of equal degree, interpolation transfers evaluations between their root sets, and every nonempty square minor of the transfer matrix is nonzero.The resulting matrices give coordinate systems for low-degree polynomials, not automatically a ring isomorphism between the quotient algebras.Source: §7.2 · pp. 200–201

7.3 Coefficient Pairings, Derivatives, and Algebra Trace

  • In k[T]/(f), the pairing formed from the coefficient of T^(d−1) in the standard remainder is nondegenerate, while its relation to algebra trace includes a derivative factor that may fail to be invertible for repeated factors.This preserves the coefficient functional in quotient algebras where the trace alone does not capture it.Source: §7.3.1 · p. 201, §7.3 · p. 201

7.3.1 The Derivative Formula and Nondegeneracy

  • The coefficient pairing is nondegenerate for every monic nonconstant polynomial, while the algebra trace pairing is nondegenerate exactly when the polynomial is separable (equivalently, its quotient is reduced over Fq).The derivative formula for the trace remains valid with repeated factors, but multiplication by the derivative can then erase directions.Source: §7.3.1 · pp. 202–203

7.3.2 Local Multiplicities and the Rank of the Trace Pairing

  • For f=∏Pi^ei over Fq, the trace on component i is weighted by ei, and its pairing contributes rank deg Pi when p∤ei and zero when p|ei.When p∤ei, the component radical is (Pi); when p|ei, the entire component lies in the radical.Source: §7.3.2 · pp. 205–206

7.3.3 The Periodic Part of Frobenius and the Reduced Quotient

  • The periodic Frobenius subalgebra Aper is a reduced complement to the nilradical n, maps isomorphically onto A/n, and is the image of a sufficiently high Frobenius iterate.It is the unique subalgebra mapped isomorphically onto the reduced quotient.Source: §7.3.3 · p. 207
  • In an eight-dimensional example, the trace pairing has rank two and a six-dimensional radical, exceeding the five-dimensional nilradical, while the coefficient pairing has rank eight.A coordinate idempotent lies in the trace radical but is not nilpotent.Source: §7.3.3 · p. 209

7.3.4 Quadratic Quotient Algebras and Product Coordinates of Root Sets

  • For quadratic quotient algebras, the projective unit group is a norm-one group, k×, or (k,+) for irreducible, split, or repeated-root moduli, respectively; induced q-Frobenius acts by inversion, identity, or zero.Source: §7.3.4 · p. 210
  • For fixed quadratic quotient, root-set coordinates depend on the chosen ordered roots, but the projective residue class is unchanged; disjoint unions multiply in the first two coordinate groups and add in the third.Source: §7.3.4 · p. 211
  • With a nondegenerate multiplication pairing, a linear vanishing condition on a root-set polynomial is equivalent to its projective class being a prescribed unit class; repeated roots require coefficient pairings beyond trace alone.In dual numbers, the algebra trace does not detect the nilpotent coefficient, while the coefficient functional gives a nondegenerate pairing.Source: §7.3.4 · p. 211

7.3.5 Weighted trace forms and symmetric multiplication matrices

  • Weighted trace forms make every multiplication operator self-adjoint, and some choice of weight and basis makes all multiplication matrices symmetric simultaneously.Source: §7.3.5 · p. 212

7.4 Tower Bases and Transitivity of Duality

  • Tower bases preserve duality under composition, while relative trace is adjoint to subfield inclusion; the trace pairing on all of E remains nondegenerate even when its restriction to L is identically zero.The restriction can vanish when the characteristic divides [E:L].Source: §7.4 · p. 213

7.5 Discriminants and Matrices of Conjugates

  • The trace discriminant is nonzero exactly when the elements form a basis, and its square class is basis-independent; the discriminant, derivative factor, and distinct conjugate roots reflect the same conjugate matrix.Source: §7.5 · p. 214

7.6 Existence of Self-Dual Bases

  • A self-dual basis of F_qn/F_q exists exactly when q is even or both q and n are odd.For a nondegenerate symmetric form, an identity-Gram-matrix basis exists when the Gram determinant is a square in characteristic other than two, or when the form is nonalternating in characteristic two.Source: §7.6 · pp. 215–216

8.1 Polynomial Representations of Linear Maps

  • Every k-linear map on E has a linearized-polynomial representation; its root space has dimension at most its q-degree, and Moore determinants test k-linear independence.A Moore determinant is nonzero exactly when its entries are linearly independent over k.Source: §8.1 · pp. 219–220

8.2 Subspace Polynomials

  • A k-subspace has a monic linearized root polynomial with nonzero linear coefficient; its coefficients lie in k exactly when the subspace is Frobenius-stable.For nested subspaces U ⊆ V, LV = LLU(V) ◦ LU.Source: §8.2 · p. 221
  • The maximal field over which a nonzero subspace W is a vector space is determined by the support of its root polynomial, and its degree divides dimk W.This characterization does not require Frobenius stability of W or coefficients in k.Source: §8.2 · p. 222

8.3 Composition and Operator Polynomials

  • For a ∈ k[T], the kernel dimension of a(σ) is governed by gcd(a, T^n − 1), and a(σ) is invertible exactly when that gcd is 1.Source: §8.3 · p. 223

8.4 The Operator Algebra Generated by Multiplication and Frobenius

  • Every k-linear operator has a unique multiplication–Frobenius expansion, yet an invertible Frobenius-commuting map fixing 1 need not preserve multiplication.The example in F16 establishes that such a map need not be a field isomorphism.Source: §8.4 · pp. 224–225

8.5 Root Multiplicities and Composition Division

  • A split polynomial whose distinct roots form an Fq-subspace is linearized precisely under the stated equal-multiplicity condition; right composition division has a unique quotient and lower-q-degree remainder.The roots must all have the same multiplicity, a power of q; ordinary divisibility by M is equivalent to L = Q ◦ M.Source: §8.5 · p. 225
  • The minimal linearized polynomial of β has as its roots the Fq-span of its K-conjugates, while Frobenius-invariant subspaces of Lh’s root space correspond to monic divisors of h.Source: §8.5 · pp. 226–227
  • The Moore determinant also admits a root-product formula for arbitrary x1, . . . , xs.Source: §8.5 · p. 227
  • A basis determines its monic linearized root polynomial via the Moore determinant, and ordinary polynomial gcds follow the Euclidean algorithm under linearization.The root-product formula identifies the polynomial with the product over the subspace; the Moore criterion ensures the determinant denominator is nonzero.Source: §8.5 · pp. 227–228

8.6 Adjoints and Solvability of Linear Equations

  • The equation L(x) = b is solvable exactly when Tr(bz) = 0 for every z in ker L*, and its solutions form a coset of ker L.In particular, x^q − cx permutes E exactly when N_E/k(c) ≠ 1; when the norm is 1, solvability is equivalent to Tr_E/k(b/u^q) = 0 for c = u^(q−1).Source: §8.6 · p. 229

The Trace Pairing Identifies the Dual Map with the Adjoint

8.6.1 Quotient Multiplication and Trace Duality

  • For quotient multiplication, ker Φ_W = H(W) and rank T_a,W = r − I_W(a); trace duality also gives H(W) = H(W^⊥) and matching complementary rank formulas.If dim_k U + dim_k V > n, then UV = E.Source: §8.6.1 · pp. 232–233

8.6.2 Counting Scalar Intersections

  • If H(W) = F_(q^d), then N_r = q^d − 1, while N_j = 0 when d does not divide j; relative-trace hyperplanes have only two nonzero intersection counts.For W = ker Tr_E/H, those counts are N_(n−d) = q^d − 1 and N_(n−2d) = q^n − q^d; intersection dimensions are invariant under a ↦ a^(−1), and under Frobenius when σ(W) = W.Source: §8.6.2 · pp. 233–234

gate Coordinates

  • The Dickson matrix encodes an operator’s root space: dim_k ker L = n − rank_E D_L, and L is invertible exactly when det D_L ≠ 0.In conjugate coordinates, composition becomes matrix multiplication and the trace adjoint becomes transposition.Source: gate Coordinates · pp. 235–237
  • Exercise 8.1 gives the one-dimensional root-polynomial formula X^q − u^(q−1)X and asks readers to derive the two-dimensional case by recurrence.The formula is for the k-subspace ku, with u ∈ E×.Source: gate Coordinates · p. 238
  • Exercise 8.3 asks readers to prove trace self-adjointness and recover (ker Tr)⊥ = k using im L = (ker L*)⊥.Source: gate Coordinates · p. 238
  • Exercise 8.4 asks readers to prove that LU | LV as ordinary polynomials exactly when U ⊆ V, while the ordinary least common multiple generally differs from LU+V.It also requests a two-dimensional example.Source: gate Coordinates · p. 238
  • Exercises 8.8–8.9 concern the Ore correspondence and permutation tests, including the need to distinguish base-field coefficients from coefficients in E.The tasks invoke a gcd criterion and Bézout construction for base-field coefficients, and compare gcd, determinant, and kernel tests when that condition is omitted.Source: gate Coordinates · p. 238
  • Exercise 8.9 states two possible multiplicative-intersection distributions for a two-dimensional space, distinguishing scalar multiples of Fq² from other spaces.For W = bFq² it gives N2 = q² − 1, N1 = 0, N0 = q^n − q²; otherwise it gives H(W) = k and N2 = q − 1, N1 = q(q² − 1), N0 = q^n − q³.Source: gate Coordinates · p. 239

Invariant Subspaces

This section develops Frobenius-based methods for describing invariant subspaces and normality, and for relating trace data, polynomial modules, and root-orbit structure. It applies these methods to polynomial factorization and composition, affine symmetries, and subfield representations.

Invariant Subspaces

  • A normal basis makes Frobenius a cyclic shift, and the cyclic-module model classifies invariant subspaces and describes which primary components translations can repair.Reciprocation and the trace pairing also describe duality in this framework.Source: Invariant Subspaces · p. 241

9.1 Orbit Length and the Dimension of Its Span

  • The degree of an element’s Frobenius annihilator equals the dimension of its conjugate span, so orbit length alone does not establish normality.A normal element has linearly independent conjugates, whereas an element may have full field degree without being normal.Source: §9.1 · pp. 241–242

9.2 The Normal Basis Theorem

  • Every finite-field extension has a normal basis: the cyclic vector lemma turns Frobenius’s minimal polynomial T^n −1 into a basis of iterates, even when it has repeated factors.In F4/F2, Frobenius is not diagonalizable, yet a cyclic basis still exists.Source: §9.2 · p. 245

9.2.1 The Root Bound and Linear Nondegeneracy

  • A nonzero linearized polynomial of q-degree s cannot annihilate a k-subspace of dimension greater than s, a root-bound argument reused for cyclicity, trace nondegeneracy, the Moore criterion, and normal bases.For normal bases, the bound rules out operator relations of degree below n; the cyclic vector lemma then yields a basis.Source: §9.2.1 · p. 246

9.3 Testing and Counting Normal Elements

  • An element is normal exactly when its Frobenius annihilator is T^n −1, and normal elements correspond to units modulo T^n −1.For n a power of the characteristic, normality is equivalent to nonzero trace; the number of normal elements is ϕq(T^n −1), and the number of bases up to cyclic shift is this quantity divided by n.Source: §9.3 · pp. 247–248
  • Prescribing a divisor D of T^n −1 constructs an element whose conjugates span dimension deg D, while its field degree is the least r with D dividing T^r −1.This construction retains repeated factors and separates conjugate-span dimension from field degree.Source: §9.3 · p. 247

9.3.1 The Effect of Translation on Normality

  • For base-field translates, if p does not divide n, normality depends on the trace condition TrE/k(θ)+nt ≠ 0 after other primary components pass; if p divides n, translation preserves normality.Thus the translate contains either q−1 or zero normal elements when p does not divide n, and either q or zero when p divides n.Source: §9.3.1 · p. 249

9.4 Linearized Root Spaces with Base-Field Coefficients

  • The root space of Lh is a cyclic k[T]-module with T acting as Frobenius: each monic d | h is the annihilator of exactly ϕq(d) elements, and nonzero roots have degree ord(µx).For monic h with h(0) ≠ 0, the splitting field of Lh is Fq^N, where N = ord(h); deg(h) determines root-space dimension while ord(h) determines the extension degree.Source: §9.4 · p. 250
  • For h = cT^a h0, Lh permutes every finite extension when h0 = 1; otherwise, its kernels across extensions are governed by root-space intersections and factor multiplicities.If h0 = ∏ Pi^ei and m has p-adic valuation v_p(m), the multiplicity contribution of Pi in the gcd formula is min{ei, p^v_p(m)} when its order divides m, and zero otherwise.Source: §9.4 · p. 251
  • The r-fold iterate of Lf has a root space of dimension r deg(f) and splitting field Fq^(N p^br), where br = ⌈logp(er)⌉.Here N = ord(f), and er is the largest multiplicity among irreducible factors of f^r; the root-space dimension grows linearly while the splitting-field degree changes only at characteristic-power thresholds.Source: §9.4 · p. 252
  • A Frobenius-stable subspace can realize an invertible operator exactly when the operator is cyclic; its image may be the full root space of the operator’s minimal polynomial.For monic irreducible h, every irreducible factor of Lh(X)/X has degree ord(h), and Lh(X)/X is irreducible exactly when h is primitive.Source: §9.4 · pp. 253–254

9.5 Norms and Cyclic Decomposition of Weighted Frobenius

  • For weighted Frobenius Sa, its cyclic decomposition over k is determined by the relative norm c: the minimal and characteristic polynomials are formed from Pc(T^m).Over the fixed field K, Sa has minimal and characteristic polynomial T^m − c; the k-module decomposition applies even when p | m.Source: §9.5 · pp. 255–256
  • Sa is cyclic over k exactly when its relative norm generates K over k, and two such operators are similar exactly when their norms are conjugate over k.The norm need not generate K×; the relevant condition is generation of the field as measured by degree.Source: §9.5 · pp. 256–257

9.6 The Lattice of Invariant Subspaces and Trace Duality

  • Monic divisors h of T^n − 1 correspond bijectively to Frobenius-invariant subspaces Uh = ker h(σ), with dimension deg(h), intersection indexed by gcd, and sum indexed by lcm.Source: §9.6 · p. 258
  • Frobenius is diagonalizable over a splitting field exactly when p ∤ n, and a Frobenius-invariant self-dual subspace exists exactly when q and n are both even.When both are even, F_{q^{n/2}} is such a subspace.Source: §9.6 · p. 259
  • When p ∤ n, products of invariant subspaces are governed by root-set products: in F_2^7, each of two three-dimensional spaces squares to the six-dimensional trace kernel, while their mixed product is the whole field.For repeated roots, eigenvalues alone do not determine invariant-subspace dimensions or products: in F_16, the trace kernel W satisfies W^2 = E.Source: §9.6 · pp. 260–261

9.7 Cyclic Correlation Polynomials and Normality

  • The cyclic correlation polynomial g_α tests normality by gcd(g_α, T^n−1) = 1; when α is normal, its modular inverse constructs a dual normal basis.The same trace-correlation coefficients form the Gram matrix of Frobenius conjugates and recover the inverse operator for dual coordinates.Source: §9.7 · pp. 262–263
  • The correlation coefficients also define a linearized operator C_α, which is invertible exactly when α is normal.This connects the trace Gram matrix of the conjugates to an invertibility test for a linearized operator.Source: §9.7 · pp. 262–263

9.8 When Nonzero Trace Implies Normality

  • Every degree-n element with nonzero trace is normal exactly when n is a power of p, or n is a prime ℓ ≠ p with ord_ℓ(q) = ℓ−1.Nonzero trace detects the multiplicity of T−1 in the Frobenius annihilator; the classification identifies when that condition and full degree force the annihilator to be T^n−1.Source: §9.8 · pp. 264–265
  • Nonzero trace forces normality for all elements of F_{q^n} exactly when n is a power of p; otherwise an element can have full Frobenius period and nonzero trace without being normal.In F_64/F_2, such an element has Frobenius orbit length 6 but its conjugates span dimension 4, showing that orbit length and linear independence are distinct.Source: §9.8 · pp. 265–266
  • The six elements satisfying α^8 + α = 1 are exactly the roots of X^6 + X^5 + X^3 + X^2 + 1.The equation follows from μ_α = (T + 1)(T^3 + 1); α^8 + α cannot be zero because that would force its orbit length to divide three.Source: §9.8 · p. 266

9.9 Normal Coordinates, Duality, and Multiplication

  • In normal coordinates, q-Frobenius acts by cyclic shift, the dual basis is normal, and absolute Frobenius acts semilinearly as v ↦ Cv^[p], with the identities valid even when p divides n.For the dual basis with first element θ, Tr(η)Tr(θ) = 1.Source: §9.9 · pp. 266–267

9.10 Descent to Subfields and Composition in Coprime Degrees

  • Relative trace sends a normal element to a normal element in a subfield, while products of normal elements in coprime-degree subfields are normal in the compositum; self-duality is preserved in both constructions.The trace construction also preserves a self-dual normal basis.Source: §9.10 · p. 269
  • For an extension of characteristic-power degree, α is normal if and only if it is completely normal, if and only if Tr_E/k(α) ≠ 0.The criterion applies over every intermediate field because trace transitivity gives nonzero relative traces.Source: §9.10 · p. 270

9.11 Normal Elements with Prescribed Intermediate Traces

  • Prescribed intermediate traces admit a common preimage exactly when they satisfy trace compatibility; the fiber has q^(n−deg G) elements and contains normal lifts exactly when every target is normal, with ϕ_q(F)/ϕ_q(G) such lifts, even if p divides n.There are no normal elements of trace zero; for each c ∈ k×, Corollary 9.43 gives the exact number of normal elements of trace c.Source: §9.11 · pp. 271–272
  • In a Frobenius-invariant affine subspace, normality is counted componentwise: a freely varying local component contributes proportion 1 − q^(−d_i) of units, while a fixed component contributes all or none.The count requires every fixed residue class to be nonzero and does not require p ∤ n.Source: §9.11 · p. 274

9.12 Relative Trace Reduction and Affine Spaces of Normal Elements

  • For E = F_(q^n), writing n = p^a m with p ∤ m, u(σ)η is normal exactly when u is nonzero modulo every distinct irreducible factor P_i of T^m − 1.Equivalently, u(σ)η is a unit in k[T]/(T^n − 1).Source: §9.12 · p. 275

9.12.1 What Ordinary Intermediate Traces Detect

  • Normality in E/k is equivalent to normality of the trace τ(x) in K/k, and each normal b ∈ K has q^(n−m) preimages under τ, all normal in E/k.Here K corresponds to the prime-to-characteristic degree m; the criterion recovers the identity trace when p ∤ n and the nonzero-trace criterion when n is a power of p.Source: §9.12.1 · pp. 275–276
  • Every element in a joint intermediate-trace fiber is normal exactly when m divides at least one r_j; otherwise the fiber contains both normal and nonnormal elements.A k-linear map whose fibers determine normality must have rank at least m, and the map τ attains this bound.Source: §9.12.1 · pp. 276–277

9.12.2 Weighted Traces and Affine Spaces of Normal Elements

  • s weighted-trace conditions, one nonzero weight from each local component, define affine spaces of normal elements of optimal dimension n − s.Every affine space of normal elements lies in such a fiber; its dimension is at most n − s, with equality precisely for these fibers.Source: §9.12.2 · p. 278

9.12.3 Imposing Primitivity as Well

  • Weighted trace fibers overlap, but every normal element occurs in the same number of them, yielding an exact counting formula for primitive normal elements.The section expresses the joint count using primitive-element counts in ordinary and weighted trace fibers.Source: §9.12.3 · p. 279

9.13 The Complete Criterion for Self-Dual Normal Bases

  • A self-dual normal basis exists exactly when n is odd, or q is even and n ≡ 2 (mod 4).For odd n, self-duality reduces to solving a unit norm equation under the involution u ↦ u∗; the section also describes admissible trace autocorrelations for normal elements.Source: §9.13 · pp. 280, 282

Properties

  • Every finite-field extension has a primitive normal element, and every primitive element of a quadratic extension is normal.The section also gives primitive normality in specified degree families, including completely normal elements when n is a power of the characteristic.Source: Properties · p. 284

9.14.1 Two Unit Coordinate Systems and a Joint Criterion

  • Primitive and normal elements satisfy a joint criterion using units in two coordinate systems: multiplicative exponent coordinates and Frobenius cyclic-module coordinates.The models preserve different operations, so coprimality in one coordinate system cannot be substituted for coprimality in the other.Source: §9.14.1 · p. 285
  • An element is primitive and normal exactly when a^(N/ℓ) ≠ 1 for every prime ℓ|N and (F/P)(σ)(a) ≠ 0 for every monic irreducible P|F.The first tests exclude elements in multiplicative subgroups; the second exclude kernels of Frobenius operators, including repeated-factor structure. Taking P = T − 1 gives the nonzero-trace condition, which is only one normality test in general.Source: §9.14.1 · p. 285

9.14.2 Changing Generators and Intersecting the Two Conditions

  • Power maps coprime to N preserve primitivity, while invertible u(σ) preserve normality; neither property is generally preserved by the other change, though Frobenius preserves both.In F16, inversion takes a primitive nonnormal element to a primitive normal one, while an invertible Frobenius polynomial maps a normal element of order 15 to one of order five.Source: §9.14.2 · p. 286
  • In F16, eight elements are primitive and eight are normal, but only four are both, rather than the 64/15 expected under independence.Separate counts do not determine the intersection; the primitive normal basis theorem guarantees that the two conditions can be satisfied simultaneously.Source: §9.14.2 · pp. 286–287
  • For a translate θ + k, test first whether any element is normal; only then count candidates satisfying primitivity, and the procedure gives no estimate for that count.If the translate has no normal element, it has no primitive normal element; the multiplicative test does not remove the need to check the normality obstruction.Source: §9.14.2 · p. 287

Changes of Representation

  • Root-set descent reduces to linear-algebra and polynomial operations: irreducibility tests orbit lengths, fixed subalgebras separate orbits, and minimal polynomials determine splitting values.Value fibers of fixed elements also yield idempotent projections; constructing normal elements compares translation and reciprocation effects on conjugate relations.Source: Changes of Representation · p. 293

10.1 Frobenius Criteria for Irreducibility

  • In the irreducibility proof, f | X^(q^n) − X makes f square-free with factor degrees dividing n; the degree tests force every factor to have degree n.Since deg f = n, this leaves only one irreducible factor.Source: §10.1 · p. 293
  • Frobenius-power gcd tests characterize irreducibility, while order tests in the quotient characterize primitivity; without prior irreducibility, the congruence X^N ≡ 1 (mod f) is essential.For a reducible polynomial, a factor of degree at most half the degree divides the corresponding X^(q^i) − X; the primitivity test requires the order of X to be exactly N.Source: §10.1 · pp. 294–295

10.2 Square-Free and Distinct-Degree Factorization

  • Square-free factorization reduces general polynomial factorization to square-free inputs, which can be factored directly or split after grouping irreducible factors by degree.Berlekamp’s method is one direct option; randomized methods can split equal-degree groups.Source: §10.2 · p. 295

10.2.1 Separating Multiplicities

  • The square-free factorization algorithm extracts factors according to multiplicity using gcds with the derivative, then recursively handles any remaining pth power.Each recursive call lowers the degree, ensuring termination.Source: §10.2.1 · pp. 295–296

10.2.2 Grouping by Orbit Length

  • Distinct-degree factorization uses gcds with X^(q^i) − X to collect irreducible factors of degree i, leaving at most one irreducible factor when the process ends.At step i, remaining factors have degree at least i, and common factors have degree dividing i, so collected factors have degree exactly i.Source: §10.2.2 · p. 296

the Fixed Subalgebra

  • Berlekamp’s fixed subalgebra has dimension s and is isomorphic to k^s for a square-free polynomial with s irreducible factors, providing elements that separate its Frobenius orbits.Computing the fixed space and taking gcds with h − c yields factor groups; its dimension also counts the root orbits.Source: the Fixed Subalgebra · pp. 296–297

Field

  • For a fixed element h, its minimal polynomial records the distinct base-field values on irreducible components, while its multiplication operator’s characteristic polynomial also records each value fiber’s total degree.A value can merge several root orbits, so further splitting may be needed.Source: Field · pp. 298, 301
  • Randomized root finding splits a completely split square-free polynomial with success probability at least 1/2 per attempt and expected at most 2(t − 1) attempts to find all roots.It uses polynomial operations and modular exponentiation without enumerating the q base-field elements.Source: Field · p. 300
  • For a square-free polynomial of degree n whose roots span an affine space of dimension v, an affine q-polynomial multiple has degree q^v, with v ≤ n − 1.The multiple is A_f(X) = L_V(X) − L_V(β), and it lies in k[X] and is divisible by f.Source: Field · p. 301
  • The affine space β + V, where V is spanned by root differences, is the smallest affine k-subspace containing S, and its polynomial Af is independent of the choice of β.The root set of Af is β + V, and its degree is |V| = q^v.Source: Field · p. 302

nents

  • The Frobenius-fixed subalgebra Bf has dimension equal to the number of distinct irreducible factors of f; dimension one implies irreducibility only when f is square-free.The fixed algebra is isomorphic to a product of one copy of k for each distinct irreducible factor.Source: nents · p. 303

A Berlekamp Basis on Roots of Unity

  • For f = X^N − 1 with p ∤ N, a basis of Bf is given by sums of monomials over q-cyclotomic cosets modulo N.For N = 7 and q = 2, the basis is 1, X + X^2 + X^4, and X^3 + X^5 + X^6; exponent-orbit and conjugate-root-orbit counts coincide.Source: A Berlekamp Basis on Roots of Unity · p. 303

10.4 Equal-Degree Factorization and Random Splitting

  • Equal-degree factorization samples uniformly from the quotient algebra and uses componentwise exponent or trace values followed by gcds to separate factors; one attempt succeeds with probability at least 1/2.The separating elements lie in the Berlekamp subalgebra; odd-characteristic sign splitting is conditional on h being a unit.Source: §10.4 · p. 304, Splitting Steps and Success… · p. 305

Recursive Factorization and Correctness of the Output

  • Recursive equal-degree splitting is a Las Vegas algorithm: its output is always correct, independent retries terminate with probability one, and a full factorization needs at most 2(s−1) trials in expectation.Each successful split lowers subproblem degrees, and the final factors have degree exactly d.Source: Recursive Factorization and… · p. 306

10.5 From Quotient-Ring Representations to Explicit Isomorphisms

  • For monic irreducibles f and g of degree n, mapping a root α of f to any root b in k[Y]/(g) gives a k-isomorphism, and all n isomorphisms send α to b^q^i.The possible images are the Frobenius conjugates b, b^q, …, b^q^(n−1).Source: §10.5 · pp. 307–308

Defining Equations and Changes of Generator

  • Changing generators optimizes defining equations, while a rational image R(α) generates the extension exactly when R is injective on α’s Frobenius orbit.For degree d = [k(R(α)):k], each image value occurs n/d times; over F2, X^3 + X + 1 and X^3 + X^2 + 1 both attain minimum support 3, but only the first attains θ2(3) = 1.Source: Defining Equations and Changes of… · p. 309

10.5.1 Sparse Relations for a Fixed Defining Polynomial

  • For fixed monic f with f(0) ≠ 0, Ls(f) is the minimum degree of a nonzero multiple P of f having at most s terms; the degree is that of P, not P/f.This formulation separates sparse multiples of a fixed polynomial from changing the generator to obtain a simpler defining equation.Source: §10.5.1 · pp. 310–311
  • A repeated adjacent coefficient ratio characterizes when a degree-d multiple of f can have d+1 terms; equal multiplicative periods need not give the same sparse relations.When all coefficients are nonzero, Ld(f) = d + 1 exactly when the adjacent ratios repeat, and coefficients in FQ with d ≥ Q guarantee Ld(f) ≤ d + 1.Source: §10.5.1 · pp. 311–312

10.5.2 Gauss periods, roots of unity, and optimal normal bases

  • Normal-basis multiplication complexity is at least 2n − 1, and under r = n + 1 prime and ordr(q) = n, a Gauss-period basis attains this bound.The construction uses a primitive rth root of unity and yields a normal basis of Fqn/Fq with complexity 2n − 1.Source: §10.5.2 · p. 313

10.6 Finding Normal Elements, Dual Bases, and Computational Costs

  • Among reciprocals of translates of an irreducible generator, at most n(n − 1) parameters yield nonnormal elements, so q > n(n − 1) guarantees a normal element.This bound does not require the characteristic to avoid dividing n; for a normal basis, Frobenius iteration obtains the remaining dual vectors from one dual vector.Source: §10.6 · pp. 315–316

Measuring Arithmetic Costs

  • With naive multiplication and reduction, M(n) = O(n^2), and binary exponentiation computes a qth power in O(M(n) log q) base-field operations.The stated linear-algebra costs exclude root finding, factoring F, and constructing the Gram matrix; bit-operation estimates must also account for base-field representation and operation costs.Source: Measuring Arithmetic Costs · p. 317

10.7 Random Computation and Canonical Output

  • Successive fixed choices among square roots produce a quadratic irreducible polynomial depending only on p after exactly s − 1 root extractions when p − 1 = 2^s m.The construction has expected bit complexity polynomial in log p; a 3T(p)-step timeout returns the fixed valid output with probability at least 2/3 when T(p) bounds expected work.Source: §10.7 · p. 318

Sparse Representations and Complexity

  • Sparse input length can be far smaller than polynomial degree, so a complexity bound polynomial in degree need not be polynomial in sparse input length.For example, X^(2^u) − 1 has two terms and an exponent encoded using u + 1 bits, while dense storage requires 2^u + 1 coefficient positions.Source: Sparse Representations and Complexity · p. 319
  • If general sparse greatest common divisors were computable in randomized polynomial bit time in sparse input and output lengths, then NP⊆BPP when finite-field size is part of the input.The conditional obstruction uses binary-encoded exponents and does not establish the same result over every fixed finite field.Source: Sparse Representations and Complexity · p. 319

10.8 A Running Example: Representations and Orbits in the Field of Order 64

  • Since 63 = 32 · 7, the primitivity criterion shows that α has multiplicative order 63; however, TrE/F2(α) = 0, so α is not normal.Source: §10.8 · p. 320

Subfields and Factors After Enlarging the Base Field

  • The elements u=α21 and v=α9 generate F4 and F8, whose intersection is F2 and compositum is E; over F4, f factors into two conjugate irreducible cubics.Squaring coefficients interchanges the two cubic factors.Source: Subfields and Factors After Enlarging… · p. 320

Power Bases, Normal Bases, and Dual Coordinates

  • The highest-degree power-basis coordinate equals trace, and γ’s six conjugates form a normal basis whose dual normal element follows from a self-inverse cyclic correlation polynomial.The correlation polynomial is 1+T+T2+T4+T5, whose square is 1 modulo T6−1.Source: Power Bases, Normal Bases, and Dual… · p. 321

Isomorphisms Between Two Quotient-Ring Models

  • Translation of the variable gives an isomorphic quotient-ring model, with inverse sending β to α+1 and the other five isomorphisms sending α to (β+1)2j for 1≤j<6.The translated polynomial remains irreducible because the variable translation is invertible.Source: Isomorphisms Between Two Quotient-Ring… · p. 322

Irreducible Constructions

  • Frobenius return periods multiply the base-orbit length to give source-orbit lengths, and together with fiber multiplicities characterize composite-polynomial factor degrees and multiplicities.Return-period divisibility also compares root fields, while affine-fiber periods in linearized compositions control the least root field.Source: Irreducible Constructions · p. 327

11.1 Root Fibers and Equivariant Return Maps

  • For h0(X)=X2, the return map fixes each fiber point and X4+1 splits into two irreducible quadratics; for h1(X)=X2+1, it swaps points and X4+2X2+2 is irreducible.In the h1 case all four roots form one Frobenius orbit.Source: §11.1 · p. 328
  • A return cycle of length d over a base orbit of length n yields a full root orbit of length nd; factor multiplicities still depend on fiber-root multiplicities.The Frobenius orbits in the full set correspond bijectively to return-map orbits in one fiber.Source: §11.1 · p. 329
  • Q is irreducible over k exactly when A(X) − αB(X) is irreducible over k(α); for n > 1, deg Q = n max(deg A, deg B).Factoring one fiber also recovers the composite polynomial’s factor degrees and multiplicities; Capelli’s criterion is the single-orbit case.Source: §11.1 · pp. 329, 331
  • An invertible fractional-linear transformation over k sends an irreducible polynomial of degree n ≥ 2 to another irreducible polynomial of degree n.Its root transformation commutes with Frobenius and maps the original root orbit bijectively onto the new one.Source: §11.1 · p. 332

Eliminating the Trace while Preserving Generation

  • If p ∤ n, α − T/n is a trace-zero generator; if p | n, a fractional-linear trace-zero generator exists exactly when T = 0 or f′(t) = 0 for some t ∈ k.Here T = TrE/k(α) and f is the minimal polynomial of α.Source: Eliminating the Trace while Preserving… · p. 333
  • For n ≥ 3, a trace-zero generator is obtainable from a rational function whose reduced numerator and denominator have degrees at most two.In characteristic two, a quadratic extension has no trace-zero generator; when the fractional-linear criterion fails, the quadratic construction has the least possible rational degree.Source: Eliminating the Trace while Preserving… · pp. 334–335

11.2 Binomials and Lifting Multiplicative Periods

  • X^t − a is irreducible exactly when every prime ℓ | t divides e but not (q − 1)/e, and 4 | t implies q ≡ 1 (mod 4).For X^t + a, the criterion applies to −a; when it holds, the root has Frobenius period t.Source: §11.2 · pp. 335–336
  • P(X^t) is irreducible exactly when the binomial criterion holds over Fq^n with e and t unchanged; its degree and root order are nt and et.For fixed admissible n, e, and t, this construction bijects irreducible polynomials of order e and degree n with those of order et and degree nt.Source: §11.2 · p. 337

11.3 Quadratic Fibers and Self-Reciprocal Constructions

  • The Q-transform is self-reciprocal of degree 2n and is irreducible exactly when Tr(c1/c0)=1 in characteristic two or P(2)P(−2) is a nonsquare in odd characteristic; in the latter case, R(P) is irreducible exactly when P(1)P(−1) is a nonsquare.Here c1 is the coefficient specified in the theorem; the R-transform criterion is stated for odd characteristic.Source: §11.3 · pp. 338–339

11.4 Additive Fibers and Trace Conditions

  • P(X^p−X−b) is irreducible exactly when Tr_k/Fp(nb−c_{n−1}) is nonzero.The fiber criterion reduces irreducibility to the Artin–Schreier trace test.Source: §11.4 · p. 339
  • A solvable power equation alone does not ensure irreducibility of an additive composition: the fiber’s nonzero trace condition is also necessary.For P=X^3+X+1 and a=1, P(X^2+X) factors as (X^3+X+1)(X^3+X^2+1).Source: §11.4 · p. 340

11.5 Restrictions on Irreducibility of Affine Root Spaces

  • If L is p-linearized of degree p^v and L(X)−b is irreducible, then v=1 or p=v=2.Irreducibility requires one Frobenius orbit on the affine root space; the affine-orbit restriction rules out the other cases.Source: §11.5 · p. 343
  • In characteristic two, a monic 2-linearized quartic L has L+b irreducible exactly when L=(X^2+uX)^2+v(X^2+uX) and both stated quadratic factors are irreducible.The required quadratics are X^2+uX+v and X^2+vX+b.Source: §11.5 · p. 343
  • For monic irreducible P of degree n and monic p-linearized L of degree p^v with v≥2, P(L) is irreducible only when p=v=2, n is odd, and both specified quadratics are irreducible.The quadratics are X^2+uX+v0 and X^2+v0X+c_{n−1}.Source: §11.5 · p. 344

11.6 Root-Field Spectra and Least Root Fields

  • A least root field exists exactly when some degree in the root-field spectrum divides all the others; when it exists, it is F_{q^{d*}}, where d* is their gcd.The intersection of all root fields is F_{q^{d*}} even when that intersection is not generated by a root of f.Source: §11.6 · p. 346
  • For irreducible P and a root α, P(G) has a least root field over k exactly when G−α has a least root field over k(α).Source: §11.6 · p. 346
  • For a linearized composition, the least root field is F_(q^(n p^e)) for some e ≤ ⌈log_p(r + 1)⌉, and polynomial gcd computations can determine e.The computation tests whether gcds involving X^(q^(n p^j)) and L − α are nonconstant; the minimum such j is e.Source: §11.6 · p. 347
  • For inseparable nonconstant p-linearized polynomials, the distinct roots still form a Frobenius-stable affine space, so a least root field exists and common multiplicity changes only factor multiplicities.The argument reduces to a p-linearized polynomial over the perfect finite field.Source: §11.6 · p. 348
  • The example X^8 + X + 1 over F2 factors into degrees 2 and 6, so its least root field is F4 although its splitting field is F64.The third Frobenius iterate acts on the root fiber by a nonidentity translation, and the two factor degrees show that the least root field does not determine the full degree spectrum.Source: §11.6 · p. 348

Affine Symmetries of Root Sets

  • Frobenius orbits determine irreducible factors, while translation and affine orbits organize root-set decompositions; affine symmetries lift only when their slopes preserve the translation subspace.Polynomial differences and coefficient comparison can recover these symmetries without first finding individual roots.Source: Affine Symmetries of Root Sets · pp. 353–354

12.1 Root Multiplicities and Three Stabilizers

  • The additive and affine stabilizers preserve the full root-multiplicity function, while the base-field affine stabilizer further restricts transformation coefficients to the base field.These transformations may permute distinct roots; the base-field affine stabilizer is distinct from the stabilizer of a specified point.Source: §12.1 · p. 354
  • Affine root-multiplicity stabilizers satisfy f(aX + b) = a^n f(X); when f has at least two distinct roots, their parameters are finite and lie in its splitting field.The stabilizer identities are ordinary polynomial identities.Source: §12.1 · p. 355
  • Frobenius preserves root multiplicities and the translation stabilizer, while additive periods of root-of-unity indices represent the multiplicative stabilizer.Frobenius maps the affine stabilizer to itself; it commutes with transformations whose parameters are fixed by Frobenius.Source: §12.1 · p. 356

12.2.1 The Common p-Power and Hasse Derivatives

  • Extracting the largest common p-power e gives νf = eνh, and f and h have the same three stabilizer groups.The reduced polynomial h need not be square-free.Source: §12.2.1 · p. 357
  • Hasse derivatives recover multiplicity through νf(α) ≥ m iff ∂[j]f(α) = 0 for 0 ≤ j < m, and their root-evaluation coordinates preserve divisibility relations and rank.They require no division by j!, so the criterion works for arbitrary multiplicities, unlike ordinary root evaluation alone.Source: §12.2.1 · p. 358

12.2.2 The Translation Stabilizer Polynomial

  • The translation stabilizer polynomial has distinct roots exactly Vf, each with multiplicity e, so its coefficients recover the translation subspace and common p-power.Even when Vf = {0}, the polynomial still recovers e.Source: §12.2.2 · pp. 359–360

12.2.3 Coefficient Equations for Scalings and the Full Affine Stabilizer

  • For nonmonomial f, coefficient-support exponent differences determine Mf = µs*; every factor of X^n − λ has support period one, so a support-primitive factor forces splitting over Fq^m.When zero is a root, the support exponent gcd need not equal e|Mf|.Source: §12.2.3 · pp. 360–361
  • Coefficient comparison characterizes full affine stabilizers, while first-order affine symmetries form a k-linear space of dimension max{0, 2 − r}, where r is the trace-pairing rank.The first-order condition is (uX + v)f′(X) = nu f(X).Source: §12.2.3 · pp. 362–363
  • Unequal root multiplicities force every multiplicity-preserving affine transformation to be the identity; in the example, the trace pairing has rank one, and first-order data cannot distinguish common p-powers p and p^2.For monic nonconstant g with g′ ≠ 0, both g^p and g^(p^2) have zero derivative and the same stated invariant I = k^2 despite different common p-powers.Source: §12.2.3 · p. 364

12.3 Translation Orbits and Additive Decompositions

  • A polynomial is invariant under translations by a finite space W exactly when it is uniquely F(LW(X)); for monic nonconstant polynomials, deg f = |W| deg F.The outer polynomial F is also monic when f is monic.Source: §12.3 · p. 364
  • For V = Vf, every translation-invariant f has a unique decomposition through LV with an outer polynomial having no nonzero translation symmetry, and f ∈ k[LW] exactly when W ⊆ Vf.Thus LV has maximal degree among the additive inner components described in the passage.Source: §12.3 · p. 365

12.4 The Full Affine Stabilizer, Center Coset, and Normal Form

  • The affine stabilizer is the translation group V when t = 1; otherwise it consists of centered scalings by µt followed by translations in V, has size |V|t, and t divides |V| − 1 when |V| > 1.In the latter case the center c need not lie in the base field.Source: §12.4 · pp. 366, 368
  • When t > 1, the center coset is the unique special orbit of size |V| and consists exactly of points with nontrivial stabilizers; every other orbit is free and has size |V|t.The center coset descends to LV(X) = δ with δ ∈ k, and it contains a base-field point exactly when δ ∈ LV(V ∩ k).Source: §12.4 · pp. 367–368
  • For t > 1, the affine normal form records multiplicities on the special orbit and nonzero fibers; it is square-free exactly when e = 1, w ∈ {0, 1}, and H is square-free.The converse construction preserves root multiplicities under the specified affine group, which may be only a subgroup of the full stabilizer.Source: §12.4 · pp. 369–370
  • A polynomial invariant under the full affine group is a polynomial in π exactly when t divides w.The orbit map π identifies points precisely when they lie in the same affine orbit; the normal-form multiplicity factor gives the condition t | w.Source: §12.4 · pp. 370–371

12.4.1 Polynomial Spaces with a Fixed Scalar Multiplier

  • For a fixed scalar multiplier, semi-invariants form U^r k[U^t]; their powers have exponents congruent to r modulo t, yielding a basis after imposing the degree bound.The symmetry condition follows by expressing translation invariants as R(U) and requiring R(aY) = a^rR(Y) for each a ∈ µt.Source: §12.4.1 · p. 371
  • The support of f lies among multiples of s = em between 0 and deg f, within a set bounded by the affine symmetry data.This common-support bound applies to monic f with f(0) ≠ 0 and at least two roots.Source: §12.4.1 · p. 372

12.5 Recovering the Normal-Form Data: Three Examples

  • A finite coefficient procedure recovers the full affine normal form by finding the common p-power, translation space, affine group, center data, and outer polynomial.Its first two steps operate over the base field without factoring f or enumerating the translation space; the affine-group search may require a splitting extension.Source: §12.5 · pp. 373–374
  • Outer centers and support recover the full affine group: at most one base-field center yields a nontrivial slope group, and each slope has exactly |V| lifts.A center can be chosen in the base field precisely when δ ∈ LV(k).Source: §12.5 · pp. 375, 377

12.6 Frobenius Return and Recovery of Irreducible Factors

  • Symmetry orbits determine quotient polynomials and normal forms, whereas Frobenius orbits determine irreducible factors; their relationship is measured by return periods in fibers.The fiber return period multiplied by the base-orbit length gives the degree of the original root.Source: §12.6 · p. 379

12.6.1 Affine Return on Additive Fibers

  • For irreducible P of degree d, cycles of the affine return permutation on V give the factors of P(L): each cycle of length ℓ yields a distinct factor of degree dℓ.The factors occur with multiplicity one, and choosing another α in the same fiber leaves the cycle type unchanged.Source: §12.6.1 · p. 379
  • Factoring each Pi(L) recovers multiplicities in f: every factor arising from Pi(L) has multiplicity e_hi, and factors from distinct Pi are distinct.Source: §12.6.1 · p. 380
  • Factor counts can be obtained from linear equations for fixed points of iterates of the return map and Möbius inversion; base-field translations yield only two possible factorization types.Source: §12.6.1 · pp. 380–381
  • When V ⊆ F_qd and dim(V) = s ≥ 2, P(LV) is reducible.The passage states the reducibility conclusion for s ≥ 2 and gives V ⊆ F_qd as the more general condition.Source: §12.6.1 · p. 381

12.6.2 Return on Full Affine Fibers

  • On a full affine fiber, the return permutation's cycle lengths determine factor degrees, and factors have multiplicity e hP; if G is defined over F_qd, their number is |G|/ord(g0) and each degree is d ord(g0).For the special orbit, cycle lengths also give the degrees of the irreducible factors of U, each with multiplicity ew.Source: §12.6.2 · pp. 382–383

12.7.1 Restrictions on the Base-Field Group and Translation Group

  • For an irreducible polynomial of degree n ≥ 2, its base-field affine stabilizer is cyclic of order dividing n, and its full translation group has size 1 or p for odd p, and 1, 2, or 4 for p = 2.A four-element translation block occurs under the stated irreducibility conditions on X² + uX + v and X² + vX + c_(m−1); conversely, with monic irreducible F and odd m, those conditions yield an irreducible F(LV) with exactly four translations.Source: §12.7.1 · pp. 384–385

12.7.2 Frobenius Differences and Recovery of the Translation Stabilizer

  • Frobenius differences recover the translation stabilizer: in odd characteristic a qualifying nonzero translation space is Fp bp, while in characteristic two a four-element space requires n = 4r with r odd and b^q = b, u^q = u + b.When the binary criterion holds, Vf = {0, b, u, b+u}; otherwise the cited passage states the remaining even-degree case has Vf = {0, b²}.Source: §12.7.2 · pp. 386–387

12.7.3 The Translation Quotient and Lifting Compatible Slopes

  • The map from affine stabilizers of f to quotient transformations of G is surjective, with kernel exactly the translations from V, so each quotient transformation has |V| lifts.The quotient transformations use slopes a in the scalar stabilizer of V and preserve the roots and multiplicities of G.Source: §12.7.3 · p. 389
  • Quotient affine symmetries need not lift: over F2, the example’s quotient has three stabilizing scalings, but the original polynomial’s full affine stabilizer consists only of two translations.The two nonidentity quotient scalings do not preserve Vf and therefore cannot lift.Source: §12.7.3 · p. 390

12.7.4 Centered Multiplicative Orders and Recovery of the Full Stabilizer

  • A root of multiplicative order N has exactly sq(N) multiplicative stabilizers of its minimal polynomial over k.The count is also κC for its cyclotomic coset, computable by the square-free-kernel and 2-adic exception formulas.Source: §12.7.4 · p. 391
  • For irreducible f, the full affine stabilizer is determined by the translation space and, when a unique quotient center δ exists, has order Qt with t | D.When D = 1, its elements are X ↦ aX + (1 − a)α + v for a ∈ NE(V), v ∈ V; otherwise each slope has Q translation parameters, and at most one base-field center yields t > 1.Source: §12.7.4 · pp. 391–392

12.7.5 Possible Group Types and Classification in Prime Degree

  • The possible group types include cyclic groups for Q = 1, Cp ⋊ Ct for Q = p, and C2 × C2 or A4 when p = 2 and Q = 4.In the Q = 4 case, A4 occurs only when D = 1, so n = 4.Source: §12.7.5 · p. 394
  • When the degree equals p, a nontrivial full affine stabilizer has Vf = bFp and is isomorphic to AGL1(Fp), of order p(p − 1).Its base-field subgroup consists exactly of the p translations from bFp.Source: §12.7.5 · p. 395
  • For prime degree ℓ ≠ p, a nontrivial affine stabilizer occurs exactly for f(X) = (X − c)^ℓ − a0 with ℓ | q − 1 and a0 a non-ℓth-power.Then Vf = {0}, and the full group is the order-ℓ scaling group centered at c; together with the characteristic-degree case, these results classify prime-degree irreducibles with nontrivial full affine stabilizer.Source: §12.7.5 · pp. 395–396
  • For irreducible quartics in characteristic two, a3 = 0 exactly when the roots form a coset of a four-element translation space, giving |Vf| = 4.In that case a1a0 ≠ 0; the final group-type case requires [k : F2] to be odd.Source: §12.7.5 · p. 396

12.7.6 Four Frobenius Orbits of Roots of Order 13

  • Four irreducible degree-three polynomials with root order 13 have trivial multiplicative stabilizers but different full affine groups, reflecting differences in additive relations among root values.The first and third are reciprocal yet have different group types, so inversion need not preserve affine stability.Source: §12.7.6 · p. 398

Polynomial Decomposition

  • In F16, the same subfield K=F4 has a generator representative of minimum degree 2 in the α-basis but degree 3 in the γ-basis.The example identifies the two quotient fields with the same F16 and compares representatives of the same subfield element.Source: Polynomial Decomposition · pp. 401–402
  • Degree profiles and defects organize the chapter’s tools for degree-bound equality and Hankel recovery of root-block equations from finite relative-trace prefixes.The chapter presents these as tools connecting subfield representations with polynomial decomposition.Source: Polynomial Decomposition · p. 402

13.1 Low-Degree Representations of Subfields and Polynomial Decomposition

  • Low-degree intersections of a subfield with power-basis spaces record its coordinate distribution and connect representation degrees to irreducible-root partitions and polynomial decomposition.Here complexity means the degree of a polynomial representative, not the number of operations or bit operations needed to compute it.Source: §13.1 · pp. 402–403

13.1.1 Power-Basis Degrees and the Degree Profile of a Subfield

  • The degree profile ρ records intersection-space dimensions, whereas κ_f(d) is the least representative degree generating K_d; for composite d, a non-base element need not generate K_d.The passage distinguishes the profile of the whole intersection space from the minimum degree needed to represent a generator.Source: §13.1.1 · p. 404
  • The degree profile and minimum generator-representation degree are invariant under conjugate-root choice and affine changes α′=aα+b, but generally depend on the generator rather than the abstract field.The affine change preserves the degree filtration, while a general change of generator can alter these data.Source: §13.1.1 · p. 404

Blocks, and Decomposition

This section develops explicit criteria connecting subfield representations, degree profiles, relative-trace data, and root-block or root-fiber structure to polynomial decomposition and irreducible-polynomial constructions. It also treats polynomial iterates and compositions, finite-field permutation criteria, and rigidity conditions derived from difference constraints.

Blocks, and Decomposition

  • The minimum representation degree is m exactly when f = P ◦ h with deg P = d and deg h = m; P is irreducible and h(α) generates Kd/k, without requiring p ∤ n or p ∤ m.A generator representation of larger degree guarantees only divisibility f | Pβ(h); equal degrees force the compositional identity.Source: Blocks, and Decomposition · pp. 405–406
  • A composition exists exactly when the root-block polynomials share their nonconstant part, equivalently when B0’s nonconstant coefficients lie in k; this condition is distinct from the existence of the subfield.Under the coefficient condition, the block polynomials yield h ∈ k[X] with h(α) generating Kd/k.Source: Blocks, and Decomposition · pp. 407, 409

13.1.3 Dimension Bounds, Degree Jumps, and Representation Defect

  • The degree-jump set lists exactly the possible representation degrees of nonzero elements of Kd, while the representation defect sums the displacement of the full jump sequence from its lower bounds.It measures subfield directions absent from low-degree spaces, not only the first occurrence of a generator.Source: §13.1.3 · pp. 409–411
  • Zero defect is equivalent to the decomposition criterion of Theorem 13.4 and gives a unique normalized inner component h of degree m with h(0) = 0, as well as a unique monic outer polynomial P.For each fixed inner degree, a fixed monic irreducible polynomial has at most one such normalized inner component.Source: §13.1.3 · pp. 410–411

13.1.4 Recovering Profiles from Coefficients and Counting Exact Degrees

  • A linear map h ↦ h^qd − h modulo f recovers degree profiles, jump sequences, and representation defects from f’s coefficients; Möbius inversion counts generators of an exact subfield.A profile dimension greater than one need not mean a generator exists, except when d is prime.Source: §13.1.4 · p. 412

13.1.5 Multiplicative Constraints and the Least Positive Defect

  • The degree set has truncated additive closure: if a, b ∈ Λf,d and a + b < n, then a + b is also a jump; defect one restricts the parameters to d = 2 or (n, d) = (6, 3).The truncation is essential because reaching n requires reduction modulo f.Source: §13.1.5 · p. 413
  • The least-positive-defect condition is necessary but not sufficient from parameters alone; the stated constraints leave (n, d) = (6, 3) as an exception.For the degree-six example f = X6 + X + 1 over F2, the profile is Λf,3 = {0, 3, 4} and ∆f(3) = 1.Source: §13.1.5 · p. 413, §13.1.6 · p. 414

13.1.6 Different Representation Degrees in the Same Finite Field

  • In the degree-six example, 1, u, and v form a basis of F8 with distinct representative degrees, realizing the exceptional defect-one case.The profile is Λf,3 = {0, 3, 4}, with ρf,3 = (1, 1, 1, 2, 3, 3) and ∆f(3) = 1; u generates K3, so κf(3) = 3 > 6/3.Source: §13.1.6 · p. 414

13.1.7 Optimal Inner Components and Degree Transfer in Subfield Towers

  • If f = P(h) with deg P = d and deg h = m, then h(α) generates Kd and the degree jumps and defect transfer by λf,c,i = mλP,c,i and ∆f(c) = m∆P(c).Thus ∆f(c) = 0 exactly when ∆P(c) = 0, allowing optimal inner components to compose successively; root blocks give candidate partitions, while representation degree determines when they are complete polynomial fibers.Source: §13.1.7 · pp. 415–416

13.2 Duality Between Subfield Degree Profiles and Relative Traces

  • Weighted trace orthogonality turns low-degree power-space intersections into a duality: relative-trace ranks recover the entire subfield degree profile.The pairing weighted by 1/f′(α) makes the orthogonal complement of a low-degree space another low-degree space; the first n trace values span K, while the first n − 1 span its trace kernel.Source: §13.2 · p. 416, §13.2.1 · p. 417, §13.2.2 · pp. 417–418

13.2.3 Two Kinds of Jumps and a Trace-Rank Criterion for Decomposition

  • Degree jumps correspond to reversed trace-rank jumps, and polynomial composition is equivalent to the stated trace-rank criteria.The quartic examples distinguish composition on the trace side: the first polynomial has a quadratic inner component, whereas the second does not.Source: §13.2.3 · pp. 418–419

13.3 Root-Block Coefficient Rank and Rational Representations of Subfields

  • Root-block coefficient rank characterizes when polynomial and rational representations achieve the subfield degree lower bound.For a degree-bound polynomial representation, conjugate root blocks differ only in their constant terms; rank two corresponds to a numerator and denominator, and the denominator can be constant exactly when the coordinate-polynomial space contains 1.Source: §13.3 · pp. 419–420, §13.3.1 · pp. 420–421

13.3.1 Two Coefficient Spaces of a Relative Root Block

  • The root-block coefficient rank and coordinate-polynomial space are basis-independent and unchanged by replacing the root with a conjugate.The space collects base-field polynomials extracted from one relative root block, and its dimension is the least number of independent such polynomials needed to reconstruct that block.Source: §13.3.1 · pp. 420–421

13.3.2 Rational Representations Attaining the Degree Lower Bound

  • When a + b ≥ n − 1, every element of E has a rational representation with numerator degree at most a and denominator degree at most b; at equality, evaluation is bijective.The root-block coefficient rank determines when a rational generator representation attains the degree lower bound.Source: §13.3.2 · pp. 422–423
  • A rational generator representation attains degree m exactly when ηf(d) = 2, and can be written A(α)/C(α) with A monic, deg A = m, deg C < m, and A,C coprime.Each fiber on the original root set is exactly one σd-root block.Source: §13.3.2 · pp. 423–424

13.3.3 Removal of the Denominator

  • Degree-bound attainment has three cases: polynomial and rational representations when ηf(d) = 2 and 1 ∈ Wf,d, rational only when 1 ∉ Wf,d, and neither when ηf(d) > 2.When ηf(d) = 2, all attaining rational functions arise by invertible fractional linear changes of A/C; the two-dimensional space Wf,d is uniquely determined.Source: §13.3.3 · pp. 424–425

13.3.4 Obstructions That Denominators Can and Cannot Remove

  • The quartic example has a two-dimensional coefficient space without 1, so its root block is a quadratic rational fiber but not a quadratic polynomial fiber; a three-dimensional sextic space blocks quadratic rational representations.In the sextic case ηf(3) = 3, so the existing cubic polynomial representation gives the degree upper bound while no quadratic rational representation exists.Source: §13.3.4 · p. 426

13.4.1 The Shortest Recurrence from a Relative Root Block

  • Over K, the relative trace sequence has minimal polynomial Bf,d, which gives its recurrence and divides every recurrence polynomial; over k, the same trace values record the subfield degree profile.These are distinct linear structures: recurrence coefficients lie in K, whereas the degree profile concerns linear independence over k.Source: §13.4 · p. 427, §13.4.1 · p. 427

13.4.2 Hankel Matrices and Recovery from a Finite Prefix

  • The first 2m relative trace values uniquely recover Bf,d and the multiplication operator without factoring f over K, with Hankel invertibility valid even when p divides m or c0 = 0.The finite prefix also recovers the degree profile and can expose an obstruction to attaining the rational representation bound.Source: §13.4.2 · pp. 428, 431
  • For a q-cyclotomic coset of size d, the first 2d period sums determine its irreducible factor through an invertible Hankel system, even when p divides d.Unlike successive Newton-identity recovery, this linear method has no restriction requiring p not to divide the coefficient index.Source: §13.4.2 · p. 431
  • A zero first trace value and failure of division in a Newton identity do not prevent recovery: the Hankel matrix remains invertible and the full power-sum data determine the polynomial.Source: §13.4.2 · p. 432

13.4.3 Two Linear Interpretations of the Same Data

  • The first 2m relative-trace terms determine Bf,d, ηf(d), Wf,d, the degree profile and defect, and whether a degree-m polynomial or rational generator representation exists, recovering it when possible.Source: §13.4.3 · p. 432
  • The trace data recover every divisor subfield’s degree profiles and counts of representatives generating it, yielding minimum generator-representation degrees κf(c) for 1 < c | d.Source: §13.4.3 · pp. 433–434
  • A minimum representative degree of n/d is equivalent to polynomial composition of the corresponding degrees.Source: §13.4.3 · p. 434
  • Base-field prefix ranks recover subfield degree profiles, while shortest recurrences over the subfield recover root-block polynomials and coefficient spaces, testing low-degree representations and functional decompositions.Source: §13.4.3 · p. 435

Lifting, and Trace Descent

  • Direct products and tensor products of root orbits, return maps, and trace descent construct irreducible polynomials; resultants express products of conjugate values as norms and yield reciprocity laws.Source: Lifting, and Trace Descent · p. 439
  • In recursive lifting, degree growth multiplies the internal return periods at successive levels, and inductive trace, function-value, and derivative conditions ensure each next return map traverses its entire fiber.Source: Lifting, and Trace Descent · p. 441

14.1 Composed Sums and Products of Roots

  • For a Frobenius-stable group with Frobenius-preserved operation, the composed sum or product is irreducible exactly when both input polynomials are irreducible and their degrees are coprime.Source: §14.1 · p. 442
  • Composed sums and products can be expressed through companion-matrix operations, while for coprime cyclotomic orders Φs ⊙ Φt = Φst.In the stated example, the degree-two and degree-three inputs are irreducible, but only the second is primitive because their root orders are 21 and 63, respectively.Source: §14.1 · p. 443, §14.2 · p. 445

14.1.1 Synchronized Phases and Factorization of Composed Products

  • When root orders are coprime, composed-product factors are distinct irreducibles of degree lcm(d, e), and their number is gcd(d, e).Coprime degrees instead ensure the product of root sets is a single Frobenius orbit; the two coprimality conditions answer different questions.Source: §14.1.1 · pp. 443–444
  • For coprime root orders, composed products can have distinct roots even when input degrees are not coprime, as Φ3 ⊙ Φ5 factors into two irreducible quartics over F2.The eight products split into two Frobenius orbits of size four, giving Φ15 = (X4 + X + 1)(X4 + X3 + 1).Source: §14.1.1 · p. 444

14.2 Matrix Representations of Composed Constructions

  • Kronecker sums and products represent composed sums and products as characteristic polynomials of multiplication operators, with multiplicities retained even for repeated roots.For irreducible inputs, the operators act by α⊗1 + 1⊗β and α⊗β in the tensor-product quotient; when degrees are not coprime, components and possible collisions require retaining multiplicity information.Source: §14.2 · pp. 445–446

14.3 Power-Residue Symbols, Norms, and Polynomial Reciprocity

  • The power-residue symbol tests whether a residue-field element is a d-th power using a value in the base field’s d-th roots of unity, and norm/resultant interchange yields polynomial reciprocity [1, Chapter 9].The symbol is independent of the chosen root and multiplicative in its argument; its norm expression connects it to the resultant.Source: §14.3 · pp. 446–447
  • For quotient algebras with repeated factors, determinants of multiplication operators retain local norm contributions with each irreducible factor’s multiplicity, even when the element is not invertible.If an irreducible factor divides the input polynomial, both sides of the stated relation are zero.Source: §14.3 · pp. 447–448

14.4 Recursive Additive Lifting Preserving Trace Conditions

  • Trace conditions make repeated reciprocal-and-substitution lifts irreducible, yielding degrees np^(j+1), including degrees p^(j+1) from P = X and a = −1.The recursion preserves coefficient and nonzero-trace conditions needed at each stage, rather than requiring only irreducibility of the first lift.Source: §14.4 · pp. 450–451

Orbits

  • The Q-transform in characteristic two and R-transform in odd characteristic recursively produce irreducible self-reciprocal polynomials of degrees 2^j n, under their stated trace and coefficient conditions.For the Q-transform, self-reciprocity holds from j ≥ 1; for the R-transform, the initial polynomial must satisfy P(1)P(−1) nonsquare, with n even additionally required when q ≡ 3 (mod 4).Source: Orbits · pp. 451–452
  • Preserved nonsquare values make each quadratic fiber return nontrivially, yielding irreducible self-reciprocal iterates; an odd initial degree can instead make the second iterate split.The recursive example maintains Pj(1) = 1 and Pj(−1) = 2, while starting from X over F3 gives R(X) = X2 + 1 but R(X2 + 1) = X4 + 1, which splits.Source: Orbits · pp. 453–454

ducibility

  • Earlier recursive constructions preserve a trace, square class, or multiplicative order so each new root fiber has a single return orbit; fixed-polynomial substitution towers require conditions that persist at every level.Repeated substitution provides another class of irreducible polynomial towers.Source: ducibility · p. 454

14.6.1 Prescribed Targets and Successive Root Fibers

  • The next iterate h◦(n+1) − τ is irreducible exactly when h(X) − βn is irreducible over k(βn), where βn roots h◦n − τ.Ordinary stability is the target-0 case; pointed affine conjugacy simultaneously changes the polynomial and target while preserving dynamic irreducibility.Source: §14.6.1 · p. 455
  • An irreducible level of degree dn splits over Fq^r into gcd(dn, r) factors of degree dn/gcd(dn, r), so the tower remains dynamically irreducible exactly when gcd(d, r) = 1.The iteration level changes the polynomial over k, whereas base extension changes the Frobenius iterate for a fixed polynomial.Source: §14.6.1 · p. 455

14.6.2 Iteration of Power Maps and the Binomial Criterion

  • For f(X) = (X + ζ)^d − ζ, stability is equivalent to each prime ℓ dividing d dividing ord(ζ) but not (q − 1)/ord(ζ), and to q ≡ 1 (mod 4) when d is even.When d is odd, testing the first level suffices; when d is even, the first two levels must be tested.Source: §14.6.2 · p. 456

14.6.3 Quadratic Iteration and Finite Critical Orbits

  • For odd q, (X2 + c, τ) is dynamically irreducible exactly when τ − c and every h◦j(0) − τ for j ≥ 2 are nonsquares in k.The criterion tests values along the critical orbit rather than expanding the iterates.Source: §14.6.3 · p. 457
  • For quadratics, checking the critical orbit until a point repeats gives a finite stability test; for general aX2 + bX + c, the conditions are that Δ and af◦j(γ) are nonsquares.It suffices to test h◦n − τ through n = (q + 3)/2; the general quadratic criterion uses γ = −b/(2a), its critical point.Source: §14.6.3 · pp. 457–458

14.6.4 Cubic Iteration in Characteristic Two and Reciprocal Coordinates

  • In characteristic two, h = X3 + X is dynamically irreducible for target τ exactly when h(X) − τ is irreducible over Fq.The proof uses reciprocal coordinates and norms to preserve noncubicity through successive root fibers.Source: §14.6.4 · pp. 459–460
  • In characteristic two, f(X)=b^2(X+a)^3+X is stable whenever it is irreducible.For a=b=1, every positive iterate of X^3+X^2+1 is irreducible of degree 3^n. Reciprocal parameters yield roots of degrees 3 and 9 at the first two levels; the parameter fields are quadratic over the corresponding root fields.Source: §14.6.4 · pp. 461–462

14.6.5 Mixed Compositions and Forward-Invariant Sets in the Base Field

  • For odd d whose prime divisors divide q−1, the family is dynamically irreducible exactly when its smallest forward-invariant set S contains only nonzero elements that are not ℓ-th powers for any prime ℓ|d.Starting with the constant terms and repeatedly applying the polynomials constructs S in at most q distinct elements, giving a finite test for irreducibility of all mixed compositions.Source: §14.6.5 · pp. 462–463

14.6.6 Denominators of Rational Iterates and Inverse Stability

  • For q=p^e, ψ=X^p−X+s is inversely stable over Fq exactly when p∤e, and then its nth denominator has degree p^n.The denominators are irreducible and pairwise distinct at every level in this case. The text also notes that ordinary polynomial iterates of ψ fail to be irreducible at specified early levels, while a cubic discriminant’s square class gives only partial factorization information.Source: §14.6.6 · pp. 464–465

14.7 Roots of Unity and Sparse Trinomial Families

  • When q≡3 (mod 4), the construction from an element ζ of order 2^(r+1) yields an irreducible trinomial over Fq for every j≥1.Over F2, another stated trinomial family is irreducible by the order equality ord_(3^(j+1))(2)=2·3^j.Source: §14.7 · p. 465

14.7.1 Counting Sparse Families and Conjugate Roots

  • For fixed n with p∤n(n−1), the square-root estimate implies irreducible trinomials X^n+X+b exist over sufficiently large finite fields, but not necessarily every small field.For distinct roots, irreducibility is equivalent to Frobenius acting as an n-cycle; the estimate’s main-term factor 1/n matches the proportion of n-cycles.Source: §14.7.1 · p. 466

14.8 Combined Constructions for Arbitrary Degrees

  • For an odd prime ℓ≠p, an auxiliary extension K=F_(q^s), s=ord_ℓ(q), and relative trace produce an element generating F_(q^(ℓe)) from an ℓ^e-th root of a non-ℓ-th-power in K.Distinct powers in the trace sum rule out membership in a proper subfield. The construction combines with prime-power constructions to produce irreducible polynomials of arbitrary degree.Source: §14.8 · pp. 467–468
  • Prime-power degrees are constructed using successive Artin–Schreier equations for characteristic powers and the stated binomial or trinomial families for other prime powers; composed sums or products then give arbitrary degrees.For characteristic powers, each Artin–Schreier step has degree p, and the final root generates the full extension.Source: §14.8 · p. 468
  • The construction yields the degree-six irreducible polynomial X^6 + X^5 + X^3 + X^2 + 1 by combining components and checking the root’s degree.The auxiliary cubic g(Y) = Y^3 + Y + 1 is irreducible over F2; the resulting root lies in neither F8 nor F4, so its degree is six.Source: §14.8 · p. 469

15.1 Function Algebras and Low-Degree Polynomial Representatives

  • Every function on Fq has a unique polynomial representative of degree less than q, and permutation tests include power-map and Frobenius-operator criteria.For linearized polynomials with arbitrary coefficients over Fqn, the Dickson matrix determines fiber sizes and gives the permutation criterion det DL ≠ 0.Source: §15.1 · pp. 473–474, §15.2 · pp. 474–475

15.2.1 Redei root polynomials, secant directions, and a lacunarity obstruction

  • For a prime p, complete splitting of X^p + g(X), with deg g = d < p, imposes p ≤ 2d − 1, apart from the constant and g = −X cases.The Redei root polynomial encodes secant directions through root multiplicities, translating a direction-set question into constraints on polynomial coefficients.Source: §15.2.1 · pp. 475–476

15.2.2 Difference fibers of Gold power maps

  • For f(X) = X^(2^k+1) on F2^n, every nonempty difference fiber has exactly 2^gcd(k,n) solutions, hence at most two when gcd(k,n) = 1.Source: §15.2.2 · p. 476

15.3 Difference Preservation and Algebraic Rigidity

  • Difference constraints can force global algebraic form, but over integer residue rings certain additive blocks also admit non-affine permutations.Source: §15.3 · pp. 476–477

15.3.1 Parallel Difference Quotients and Linearized Maps

  • A function on Fq has difference quotients independent of the base point exactly when it is Fp-affine, with a unique linearized-polynomial representation.Bijectivity and nonvanishing of the quotient are not required; the example on F9 shows such a function need not be a permutation.Source: §15.3.1 · pp. 477–478

15.3.2 Multiplicative Coset Preservation and Rigidity

  • Preserving multiplicative cosets of nonzero differences forces f(x) = ax^(p^j) + b, with a ∈ H and d | p^j − 1.Here H is a proper subgroup of Fq× and d = (q − 1)/|H|; the cited Carlitz–McConnel theorem gives the rigidity conclusion.Source: §15.3.2 · p. 478
  • Difference-quotient-preserving permutations are exactly f(x)=ax^p^j+b, with a∈H, d|(p^j−1), and unique parameters.Every such function is a permutation of Fq.Source: §15.3.2 · pp. 478, 480
  • q|H|n/r maps satisfy the condition, where r=ord_d(p); those fixing 0 and 1 are exactly x↦x^{p^{rt}} for 0≤t<n/r.For F9, the square-class-preserving maps are ax+b or ax^3+b, giving 72 functions.Source: §15.3.2 · pp. 480–481
  • Allowing one global permutation of multiplicative cosets yields maps f(x)=β(x)+b, with β semilinear over the subfield K=Fp(D) [33].For a proper K, β acts on a higher-dimensional K-space, so it need not be a single Frobenius monomial.Source: §15.3.2 · p. 481

15.3.3 Three-Point Difference Determinants and Second-Order Rigidity

  • The three-point divided difference is the X² coefficient of the interpolating polynomial, is symmetric in the nodes, and is unchanged by adding an affine function.It equals a for aX²+bX+c and x+y+z for X³.Source: difference determinant · p. 482

difference determinant

  • If every three-point divided difference lies in H, the functions are exactly f(X)=aX²+bX+c with a∈H; there are q²|H| such functions, not necessarily permutations.The proof uses one-point-deleted difference quotients and compatibility across base points to exclude nontrivial Frobenius exponents.Source: difference determinant · pp. 482–483
  • For one fixed shape λ, constant divided differences yield f(X)=aX²+L(X)+b, where L is K-linear for K=Fp[λ], not necessarily invertible.When K=Fq, the solutions reduce to aX²+b1X+b0.Source: difference determinant · p. 484
  • In F16, f(X)=X⁸ has fixed-shape divided differences t⁶∈H that vary over H, showing subgroup membership need not imply a constant value or a quadratic function.This example distinguishes recovery from constant divided differences from the weaker subgroup-value condition.Source: difference determinant · p. 485

shape-specific four-term relation count

This section develops explicit finite-field methods for analyzing polynomial maps through value, fiber, and collision counts, permutation criteria, cycle structures, and root-set decompositions. It also connects Frobenius orbits and quotient-algebra pairings to recurrence periods, minimal-polynomial recovery, and finite-prefix algorithms.

shape-specific four-term relation count

  • When Kλ,f(x,t) ∈ H everywhere and Nλ(H) = 0, the four values at x, x+t, x+λt, and x+(1+λ)t sum to zero, but this identity alone gives no global additivity.A single shape can have zero relation count without H being Sidon; the text gives H = F8× and λ outside F8 as an example.Source: shape-specific four-term relation count · pp. 485–486

15.3.4 Difference Orbits and Local Rigidity at Prime Powers

  • Under the hypotheses of Lemmas 15.17 and 15.18, preserving cyclotomic difference orbits modulo odd prime powers and powers of two forces every map to be affine.For K = F× modulo a prime p, every permutation preserves the condition, and nonaffine examples exist when p ≥ 5.Source: §15.3.4 · pp. 486–487

15.3.5 Chinese Remainder Decomposition and Global Rigidity

  • For cyclic K modulo n, Theorem 15.19 classifies when the orbit-preserving group strictly exceeds AffK(n); otherwise its maps are exactly x ↦ ux + b with u ∈ K.The listed enlargement cases include a prime p ≥ 5 with p ∥ n and Δn(n/p) ⊆ K, or an odd prime p with p² | n and Δn(n/p) ⊆ K; the proof also treats a 2-primary exception. The Chinese remainder theorem reduces rigidity to local components.Source: §15.3.5 · pp. 489–490
  • For odd prime powers, multiple equal-difference decompositions with blocks larger than one are equivalent to the existence of a non-affine orbit-preserving permutation.This equivalence is restricted to the stated odd prime-power case: modulo 8, K = ⟨5⟩ has a nontrivial additive stabilizer, yet all preserving maps are affine.Source: §15.3.5 · pp. 491–492

15.4 Value Sets, Fibers, and Minimal Value Set Polynomials

  • The section introduces value sets and fiber sizes for polynomial maps, noting that the root bound restricts their sizes and subspace polynomials attain it.For each b, Nb(F) counts the inputs mapping to b; the sum of the fiber sizes is stated to equal Q.Source: §15.4 · pp. 492–493
  • For a degree-d polynomial on F_Q, |V_F| ≥ ceil(Q/d); attaining the bound defines a minimal value set polynomial, and reduction modulo X^Q−X can change whether it attains the bound.The polynomial X and X^Q induce the same function on F_Q, but only X is minimal by this definition.Source: §15.4 · p. 493

15.4.1 From Additive Cosets to Power Images of Subspaces

  • Subspace polynomials composed with power maps yield minimal value set polynomials whose distinguished fiber has q^s elements and whose other nonempty fibers have vq^s elements.Borges and Reis classify realizable value sets of size greater than two in F_(p^N) as aW^v+b, with W a subspace containing 1 over an intermediate field and v dividing its multiplicative order [7, Theorem 2.2].Source: §15.4.1 · pp. 493, 495

15.4.2 Pairs with the Same Image and Collision Counts

  • Collision-count equality holds exactly when all nonempty fibers have equal size, and the collision count is Q exactly when F is a permutation.Collision counts also equal mean squared absolute values of additive character sums, connecting value-set counting with Fourier duality.Source: §15.4.2 · pp. 495–496

15.4.3 Exact Value Counts from an Affine Linearized Equation

  • For P_N(X)=X(X−1)^(N−1) on F_Q, the intersection F_N∩F_Q=F_s controls nonzero fiber sizes, which can only be 0, 1, or s; exactly Q/s target values are omitted.The formula requires no containment between F_N and F_Q.Source: §15.4.3 · pp. 496–497

15.4.4 Two-Point Coefficient Fibers and Fractional-Linear Involutions

  • Two-point coefficient counts satisfy N_H(A,B,C)=|H∩J(H)| minus the diagonal fixed-point count; ordinarily J is a projective involution with at most two fixed points, while the stated characteristic-two exception gives N_H=0.In the exception, characteristic two and A=C=0; then J is the identity and B is nonzero.Source: §15.4.4 · p. 498

15.5 Power Sums and Hermite’s Criterion

  • Hermite’s criterion says F is a permutation polynomial exactly when it has one zero and the canonical remainders of F^t lack an X^(q−1) term for 1≤t≤q−2.Power sums and the Vandermonde matrix imply every fiber size is congruent to 1 modulo p; since the sizes sum to q, each is one.Source: §15.5 · pp. 500–501

15.6.1 A Fiber Criterion for Finite Sets

  • A map on a finite set is a permutation exactly when its induced base map is bijective and it is injective on every fiber.The criterion applies to both additive trace fibers and multiplicative power-map fibers.Source: §15.6.1 · p. 501, §15.6 · p. 501

15.6.2 Constructing Permutations Along Trace Fibers

  • For F(x) = ax + g(Tr(x)), permutation of E is equivalent to permutation of the induced map on k; if g is k-valued and p divides n, every such g works.The trace condition on g is what determines the induced map on the base field.Source: §15.6.2 · p. 502

15.6.3 Multiplicative Fibers and Explicit Return Maps

  • For F(x) = x^r g(x^s), permutation requires gcd(r, s) = 1 and a permutation induced on μ_d; return maps then determine cycle lengths above base cycles.Over a base cycle of length ℓ, each return-map cycle of length t gives an F-cycle of length ℓt.Source: §15.6.3 · pp. 503–504
  • A trace-zero involution on F8 lifts through a multiplicative quotient to a nonlinear involution on F64 with a sparse inverse.Its canonical representative has nonzero terms of degrees 37 and 46 and is not F2-linear.Source: §15.6.3 · pp. 506–507

15.7.1 Norms and Changes of Origin

  • For affine Frobenius maps, norm and trace criteria permit changes of origin: c ≠ 1 gives a unique fixed point, while c = 1 reduces to τ(y) + β.When the trace obstruction θ vanishes, the normalized map is conjugate to τ; when θ ≠ 0, it has no fixed point and order pm.Source: §15.7.1 · p. 508

15.7.2 Fixed Points of Iterates and All Cycles

  • Fixed-point counts for iterates of affine Frobenius maps determine all cycle lengths and their multiplicities.The counts distinguish the cases classified by c and θ.Source: §15.7.2 · pp. 509–510
  • When c = 1 and θ ≠ 0, the shortest-cycle length and count are specified by m; otherwise the shortest cycle has length one.In the nonzero-trace case, any cycle length ℓ satisfies vp(ℓ) > vp(m).Source: §15.7.2 · p. 510
  • When the trace obstruction is nonzero in the F16 example, the affine map has two cycles of length eight, covering all 16 elements.The norm determines the weighted linear part’s fixed-point condition, while the trace determines whether a translation can be removed when the norm is one.Source: §15.7.2 · p. 511

15.7.3 Cycle Data for General Linear Permutations

  • Elementary-divisor multiplicities determine fixed-point and cycle counts, while identical characteristic polynomials can correspond to different cycle structures.The fixed-point count uses the factors’ degrees, multiplicities, and orders; the example contrasts maps with the same characteristic polynomial and order but different fixed spaces.Source: §15.7.3 · pp. 513–514

15.7.4 The Sign and Determinant of a Linear Permutation

  • In odd characteristic, the sign of a linear permutation is determined by the quadratic character of its determinant; in even q, all are even except for specified maps in (q, n) = (2, 2).For (q, n) = (2, 2), the odd maps are exactly the nonidentity maps of order two.Source: §15.7.4 · pp. 515–516

15.8 Dickson Polynomials: Power Maps Descending Along Conjugate Fibers

  • For a ≥ 1 satisfying ma ≡ 1 (mod q² − 1), D_a represents the inverse function of D_m; the cited passages also identify π(u)=π(v) exactly when v=u or v=u⁻¹.Source: §15.8 · pp. 518–519

15.8.1 Reciprocal-Orbit Root Polynomials and a Frobenius Equation

  • For odd m with p ∤ m, P_m has distinct roots given by z + z^-1 for reciprocal pairs of nonidentity mth roots of unity, each pair counted once.These parameter values form the reciprocal-orbit root polynomial used to compare Frobenius equations from roots of unity of different orders.Source: §15.8.1 · p. 520
  • For every odd prime power q, Theorem 15.58 gives a root-set decomposition of the equation y^q = D2(y).Its nonconstant factors are squarefree and pairwise coprime, but need not be irreducible.Source: §15.8.1 · p. 520
  • At each root t of H = Pq+2, H′(t) = −2t(t − 2)J(t) ≠ 0, giving the normalization weight 1/H′(t) for Lagrange interpolation.The root-set decomposition therefore supplies weights for recovering the highest coefficient from root evaluations.Source: §15.8.1 · p. 521
  • For q = 5, Y^5 − Y^2 + 2 factors as (Y − 2)(Y + 1)(Y^3 + Y^2 − 2Y − 1), whose cubic roots lie in F125, not F25.The reciprocal orbits of seventh roots have Frobenius period three, matching the cubic factor.Source: §15.8.1 · p. 521

16.1 The Shift Operator and Linear Recurrence Relations

  • If f(S)s = 0 and f(0) ≠ 0, the sequence’s minimal polynomial divides f; when f is irreducible, every nonzero solution has minimal polynomial f and least period ord(f).The theorem identifies least period with the polynomial order of the minimal polynomial.Source: §16.1 · p. 528
  • Repeated irreducible-factor multiplicities affect sequence periods through an additional power of p.Source: §16.1 · p. 528

16.2.1 The Coefficient Pairing and the Recurrence-Space Isomorphism

  • The coefficient pairing identifies the recurrence solution space with k[T]/(f), makes the shift multiplication by T, and gives exactly φ_q(h) sequences with minimal polynomial h for each monic h|f.When f(0) ≠ 0, those sequences have least period ord(h).Source: §16.2.1 · pp. 529–530

16.2.2 Linearized Root Spaces and Compatible Quotient Maps

  • For f(0) ≠ 0, recurrence states correspond to linearized roots with matching minimal annihilators and periods, and L_f splits over F_q^ord(f).The correspondence is an isomorphism of operator modules, not generally a multiplication-preserving map; repeated factors record the operator’s nonsemisimple part.Source: §16.2.2 · pp. 530–531
  • The quotient map, multiplication by v(S) on recurrence spaces, and L_v on root spaces represent the same map; the recurrence compatibility also holds with transient phases.The root-space quotient description assumes f(0) ≠ 0, while the recurrence-space identity does not.Source: §16.2.2 · pp. 531–532
  • If the quotient state has Frobenius period t and zero’s affine return period in its fiber is e, the original root and recurrence state have period te.The fiber is a translate of W_v, and the affine return map determines the internal period e.Source: §16.2.2 · pp. 532–533
  • For f=(T+1)^2 over F_2, the coefficient model produces a period-two sequence, while algebra trace and reduction modulo the nilpotent direction lose it.More generally, coefficient pairing retains recurrence states that trace pairing can erase along repeated-factor nilpotent directions.Source: §16.2.2 · pp. 534, 536

16.3 Trace Representations and Conjugate Decomposition of Recurrences

  • For irreducible f, every recurrence solution has a unique trace representation over E=F_q^d, obtained by rescaling its quotient parameter by f′(α).The rescaling is bijective because f′(α) ≠ 0.Source: §16.3 · p. 536
  • For squarefree f, each recurrence sequence decomposes uniquely into trace components, and its minimal polynomial is the product of factors whose component is nonzero.Source: §16.3 · p. 537

16.4 Primitive Polynomials and Maximum-Length Sequences

  • A degree-d polynomial is primitive exactly when its nonzero solution sequences have period q^d−1, with d-term states running through all nonzero vectors once per period.In one period, zero occurs q^d−1−1 times and each nonzero symbol occurs q^d−1 times.Source: §16.4 · p. 538

16.5.1 The Exact Decomposition into Transient and Periodic Parts

  • A recurrence with minimal polynomial T^a g has a unique decomposition into a finitely supported part and a purely periodic part, with least transient length a and eventual period ord(g).Only the zero-root factor causes a transient; repeated factors at nonzero roots may enlarge the period, and the invertible component admits a Frobenius model.Source: §16.5.1 · pp. 539–541

16.5.2 Rational Generating Functions and Minimal Polynomials

  • For reduced G_s(Z)=A/B with B(0)=1, the minimal polynomial is T^a g, where g=T^bB(T^-1) and a=max(0, deg A-b+1); the least transient and eventual period are a and ord(g).The polynomial part records the transient, while the reduced denominator records the minimal polynomial of the invertible component.Source: §16.5.2 · pp. 542–543

16.6 Recovering Recurrences from Finite Observations: The Berlekamp–Massey Algorithm

  • Berlekamp–Massey returns a finite prefix’s minimum linear complexity and a corresponding connection relation in O(N(L_N + 1)) arithmetic operations.Apart from storing the input, its stored polynomials contain O(L_N + 1) coefficients.Source: §16.6 · p. 545
  • If an infinite sequence’s minimal-polynomial degree is at most D, Berlekamp–Massey on its first 2D terms returns the minimal polynomial of the entire sequence.The degree bound is required: a finite prefix can have continuations with different minimal polynomials.Source: §16.6 · pp. 546–547
  • For the trace representation of the multiplicative orbit, H(T) = T^6 + T + 1; s is a nonzero solution of an irreducible recurrence, with minimal polynomial equal to that of α and period 63.The connection polynomial is 1 + Z^6 at positions 5–9 and 1 + Z^5 + Z^6 at positions 10–11.Source: §16.6 · p. 547

Root Sets and Coding

This section uses finite-field root sets, Frobenius structure, and linear algebra to describe code spaces and translate distance and divisibility conditions into vanishing, independence, and quotient-algebra criteria. It develops bounds and constructions for cyclic, constacyclic, Goppa, rank-metric, and evaluation codes, together with structural descriptions of decompositions, symmetries, and subcodes.

17.1.1 Hamming Distance, Duality, and the Column Criterion

  • A linear code has distance N − max{|I| : rank G_I < K} ≤ N − K + 1; equality holds exactly when every K columns are independent.Scalar extension preserves dimension and distance; the dual of an MDS code is MDS, and shortening s coordinates gives parameters [N − s, K − s, N − K + 1].Source: §17.1.1 · p. 552

17.1.2 Rank Weight and the Rank-Metric Singleton Bound

  • For rank-metric codes with length n ≤ m, the rank-metric Singleton bound limits minimum rank distance, and codes attaining the bound are maximum rank distance.Rank weight measures the dimension over Fq of the span of a word's coordinates.Source: §17.1.2 · p. 553

17.2 Linearized Evaluation and Rank-Metric Codes

  • Linearized-polynomial evaluations at Fq-linearly independent points give dimension-K E-linear codes meeting the rank-metric Singleton bound.These Gabidulin codes illustrate how Moore independence and the linearized root-space bound yield a construction without developing rank-metric decoding.Source: §17.2 · pp. 553–554

17.3 Root Orbits, Cyclic Codes, and Fourier Coordinates

  • Cyclic codes are ideals generated by monic divisors of X^N − 1, and their defining root sets are precisely q-stable exponent sets.For a root η, trace coordinates produce a cyclic code whose check polynomial is its minimal polynomial; its nonzero codewords have least shift period ord(η).Source: §17.3 · pp. 555–557
  • For a single root orbit, the trace model maps a d-dimensional field extension isomorphically to a cyclic code, with check polynomial equal to the root's minimal polynomial.The orbit length gives the code dimension, while the root's multiplicative order determines the least period of each nonzero codeword.Source: §17.3 · pp. 556–557
  • Fourier data descend to k exactly when they are Frobenius-equivariant: each cyclotomic orbit of length d contributes a d-dimensional k-space, and allowed frequencies form unions of orbits.The root-set and spectral descriptions are two forms of the same evaluation isomorphism; cyclic right shift acts in these coordinates by multiplication by ζ^i.Source: §17.3 · pp. 557–558

17.4 Constacyclic Codes, Duality, and Sparse Multiples

  • A λ-constacyclic code is an ideal generated by a monic divisor of X^N − λ, with dimension N − deg f; for MDS codes, the generator and check polynomials have full support.The reciprocal check polynomial generates the dual constacyclic code, and its divisibility condition describes all column relations of the original generator matrix.Source: §17.4 · pp. 559–560
  • The constacyclic dual is generated by h∨, not generally h; an example gives a [3, 2, 2] MDS code with h∨ ≠ h.For power-vector eigenvalues the root parameter is θ = α^-1 when α^N = λ; the reciprocal-root Frobenius orbit lengths are unchanged.Source: §17.4 · p. 561

17.5 Consecutive Root Constraints and the BCH Bound

  • For a cyclic code with δ consecutive defining zeros, the BCH bound gives minimum distance at least δ; the binary example has parameters [7, 4, 3].Frobenius closure makes root constraints descend to the base field, and consecutive exponents yield an invertible Vandermonde system.Source: §17.5 · pp. 561–563
  • A square-free λ-constacyclic code with δ−1 consecutive roots ωζ^b+r has minimum distance at least δ, without requiring an Nth root of λ in k.The bound follows from evaluating a putative low-weight codeword at the listed roots and applying an invertible Vandermonde matrix.Source: §17.5 · p. 563

17.6 Support Root Polynomials and the Distance of Binary Goppa Codes

  • For a binary Goppa code defined by square-free G of degree r, every nonzero codeword has weight at least 2r + 1.The support root polynomial and its derivative translate the support condition into divisibility; square-freeness of G yields the bound.Source: polynomial · p. 564, §17.6 · p. 564

polynomial

  • Over F64, Γ(E, G) has length 64, dimension at least 40, and minimum distance exactly nine, attained by a split root set and its derivative.Here deg G = 4, so the general bound is also nine; the result is obtained without enumerating codewords.Source: polynomial · p. 565
  • For distinct a, b in (E×)^d, the two-coset construction produces a root set of size 2d + 1 and a Goppa code with minimum distance 2d + 1.Its auxiliary polynomial has derivative X^(2d) + ab, the square of the Goppa polynomial.Source: polynomial · p. 566
  • The fixed-derivative family uniquely parametrizes F = XP(X^d) by V; complete splitting over K holds exactly when PV has distinct roots in H = (K×)^d.The family also counts square-free choices of V through the polynomial Euler function.Source: polynomial · p. 567
  • For K = F64 and d = 3, exactly 10 of 63 square-free candidates split completely, yielding ten distinct weight-seven words and minimum distance seven.These counts refer to distinct locator root sets, not different Goppa codes.Source: polynomial · p. 568
  • At least Q/2 − 2r parameters produce square-free constructions, which preserve relative Frobenius symmetry but need not form unions of full absolute Frobenius orbits.Different parameter values yield different polynomials; the construction also turns the binary Goppa distance criterion into a way to construct root sets from admissible orbits.Source: polynomial · p. 569

17.7.1 Support Periods and Interleaved Direct Sums

  • If f(X) = fsp(X^s) has support period s, then s divides N and the code interleaves s copies of its support-primitive core, preserving minimum distance and multiplying dimension by s.The interleaved components have disjoint coordinate positions, so their weights add.Source: §17.7.1 · p. 570

17.7.2 Affine Symmetries and Code Subspaces

  • An affine substitution preserves the polynomial code space exactly when it preserves the generator’s root multiplicities, while its substitution action generally does not preserve Hamming weight.For a nonzero translation, X maps to aX + b and its Hamming weight changes from one to two.Source: §17.7.2 · p. 572
  • The indecomposable coordinate blocks are the residue classes modulo the support period, and every coordinate direct-sum decomposition groups these blocks.The compressed code has the same minimum distance as the original code; the stated Singleton-bound application uses its shorter length and dimension.Source: §17.7.2 · pp. 572–573
  • For a subspace D = C ∩ W, its dimension is l − ρ and its effective support consists exactly of coordinates whose coefficient rows are outside the remainder matrix’s row space.Source: §17.7.2 · p. 574

17.7.3 Reducing Divisibility by the Affine Normal Form

  • Outer divisibility tests retain the special root orbit through the factor Y^ur: for finite J, dim(C ∩ Wr,J) = |J| − ρr,J, with a simplified dimension for consecutive exponents.For J = {0, …, L}, the dimension is max{0, L + 1 − deg Br}; the special factor cannot be omitted when w > r.Source: §17.7.3 · pp. 575–576
  • A recurrence matrix has the same kernel and rank as the outer remainder test, and the method requires neither consecutive exponents nor a separable quotient polynomial.The recurrence-matrix and root-value Hasse tests encode the same quotient-algebra constraint while retaining root multiplicities.Source: §17.7.3 · pp. 576–577
  • The affine-normal-form construction yields a code with parameters [12], whose weight-three codeword comes from the centered power basis and outer relation.Its effective support is {0, 1, 5}; the weight bound and exclusion of weights one and two establish the minimum distance.Source: §17.7.3 · p. 578

17.8.1 Projective Root Forms and Evaluation Spaces

  • Homogenizing a root polynomial adds the point at infinity, yielding a binary form that records projective roots and links coordinate changes, Frobenius descent, and evaluation spaces.The image of a polynomial vector space under pointwise evaluation on fixed points is an evaluation space, or an evaluation code when viewed as a linear code.Source: §17.8.1 · pp. 578–579

form

  • The projective root form Bq vanishes exactly on P1(k), has each linear factor once, and transforms under a change of coordinates by the determinant.A nonzero binary homogeneous form of degree d has at most d distinct projective zeros; vanishing on all of P1(k) implies divisibility by Bq.Source: form · p. 579
  • A projective root form descends to k exactly when its root set is Frobenius-stable; projective Frobenius orbits correspond to homogenized minimal polynomials, with gcds and quotients encoding field-period layers.For r | s, Bq^r divides Bq^s, and the quotient is square-free with roots P1(Fq^s) \ P1(Fq^r).Source: form · p. 580
  • Homogeneous evaluation in degree d has kernel BqR_{d−q−1} and image dimension min{d + 1, q + 1}; it is injective for d ≤ q and an isomorphism for d = q.Nonzero homogeneous vanishing relations first occur in degree q + 1.Source: form · p. 581
  • Nontrivial [N, K] MDS codes satisfy N ≤ q + K − 1, K ≤ q − 1, and N ≤ 2q − 2; Reed–Solomon codes have parameters [n, K, n − K + 1].The Reed–Solomon result applies for 1 ≤ K ≤ n and a set S ⊆ k of size n ≥ 1.Source: form · pp. 581–582

code

This section develops structural and Fourier methods for MDS, cyclic, and trace codes, connecting polynomial evaluation and duality with fields of definition, coordinate symmetries, and Frobenius-orbit structure. It also uses character orthogonality and Gaussian periods to relate polynomial-fiber counts, equation counts, and short relations in finite fields.

code

  • In characteristic two, the displayed columns generate an [q + 2, 3, q] MDS code with dual [q + 2, q − 1, 4], defining a hyperoval.The construction verifies independence directly; for q = 2, both codes are trivial boundary cases.Source: code · pp. 582–583

17.8.2 Interpolation Weights, Duality, and Squaring in Characteristic Two

  • Lagrange interpolation’s highest-coefficient weights yield orthogonality relations for low-degree evaluation spaces and their extended-evaluation counterparts.The proof uses the coefficient identity and injective parameter maps to establish equality of the orthogonal spaces.Source: §17.8.2 · pp. 583–584
  • For q = 2^e and 1 ≤ h ≤ q/2 − 1, differential interpolation becomes extended evaluation at squares, giving an [q − h + 1, q/2 + 1, q/2 − h + 1] MDS code.For q = 8 and H = {0, 1}, the construction gives an [7] MDS code with an [7] [6] MDS dual.Source: §17.8.2 · pp. 584, 586

17.8.3 Low-Degree and Critical-Degree Rigidity of the Frobenius Derivation

  • For total degree at most q, the Frobenius derivation satisfies DqP = 0 exactly when P is a pth power.The derivation preserves each ideal generated by a k-linear form and has the same expression after any k-linear coordinate change.Source: §17.8.3 · p. 587
  • At degree q + 1, the kernel first contains non-pth-power relations for r ≥ 2, spanned by pairwise projective forms; for r = 1 the critical kernel is zero.These critical-degree relations occur in arbitrary characteristic, unlike the lower-degree kernel elements, which come from characteristic powers.Source: §17.8.3 · pp. 587, 589

17.8.4 Compatible Restrictions and Recovery of Homogeneous Polynomials

  • For pairwise nonproportional linear forms in three variables, compatible degree-d restrictions on their planes determine a unique homogeneous form when d < N.The result holds over any field; at d = N, adding a scalar multiple of the product of the defining linear forms preserves every restriction.Source: §17.8.4 · p. 590
  • Compatible restrictions on three coordinate lines make the first six coordinates an information set for C2 = [7, 6, 2], while the cubic evaluation kernel is spanned by three Frobenius-difference forms and gives [7].The quadratic code is obtained by gluing local forms; the cubic kernel counts redundant representations.Source: §17.8.4 · p. 591

17.9 Trace Codes, Sparse Multiples, and Multiplicative Subgroup Rigidity

  • The MDS criterion is equivalent to every set of at most K distinct elements of H being k-linearly independent; in that case, all K + 1 coefficients of mα are nonzero.The condition also excludes low-weight multiples of mα of degree less than the code length.Source: §17.9 · pp. 593–594
  • For a nontrivial MDS trace code, N is odd, gcd(N, q −1) = gcd(N, K) = 1, N ≡1 (mod K), and N ≥2K +1; every nonidentity subgroup element is normal with a full-support minimal polynomial.These conclusions use the subgroup restrictions and the MDS independence condition.Source: §17.9 · pp. 595–596

17.10 Residue Layers and Balance of Fourier Supports

  • A cyclic MDS code’s Fourier support must be as evenly distributed as possible in every residue class modulo each divisor of N, a necessary but not sufficient test.The condition concerns the exponent set and can be checked before constructing a generator matrix.Source: §17.10 · pp. 598–599
  • For a nontrivial [N, K] cyclic MDS code, zero-class compression by h | N yields a cyclic code of length N/h and dimension floor(K/h) or ceil(K/h), which is MDS when nonzero.The compressed code is over the base field.Source: §17.10 · p. 599

17.11 The Smallest Field of Definition of a Cyclic Code

  • Root-set descent can determine whether a cyclic code is definable over a smaller alphabet; the comparison fixes coordinates and allows no scalings or permutations.Source: §17.11 · p. 600
  • A cyclic code’s smallest field of definition is F_{p^s}, where s is its root-set return period and divides both f and ord_N(p); for an irreducible check polynomial with root order N, s = gcd(ord_N(p), f).Descent to F_{p^s} preserves irreducibility and dimension K in that irreducible case.Source: §17.11 · p. 600
  • For a nontrivial MDS cyclic code, s < f implies N ≤ 2√q − 2, while N > q + 1 forces s = f and ord_N(p) = f ord_N(q).In the irreducible case, the dimension restriction follows from fK = ord_N(p) ≤ N − 1 ≤ q + K − 2.Source: §17.11 · pp. 601–602

17.12 Common Permutation Symmetries of Cyclic Codes

  • For gcd(n, q) = 1, common symmetries of cyclic codes are derived using finite-field Fourier spectral projections and difference-orbit rigidity, without developing cyclotomic association schemes.The result concerns permutations preserving every cyclic code individually, not permutations that merely rearrange the family.Source: §17.12 · p. 602, §17.12.1 · p. 603

17.12.1 Recovering Difference Orbits from Spectral Projections

  • A coordinate permutation preserves every length-n cyclic code if and only if it preserves each difference orbit, as detected by the Fourier spectral projections.The projections express the code components in coefficient coordinates; their matrix entries separate the difference orbits.Source: §17.12.1 · pp. 603–604

17.12.2 An Arithmetic Criterion for the Common Affine Group

  • The common permutation group is tested by multiplicative-order index conditions, including E1 and E2; when no exceptional condition holds, it is exactly the affine group generated by shift and the q-multiplier.E1 requires a prime p ≥ 5 with p ∥ n and ι_q(n/p) = ι_q(n); E2 requires an odd prime p with p² | n and the same index equality.Source: §17.12.2 · pp. 604–605

17.12.3 Multiplier Preservation and Fixed-Point Rigidity for One Code

  • A nonidentity multiplier preserving a cyclic MDS code has at most two fixed points; the restriction comes from preserving a linear space with strong column independence.For general cyclic codes, the multiplier-order synchronization applies to divisors d ≥ 3, and the code dimension K need not equal the common coset size m.Source: §17.12.3 · pp. 607–608
  • The code dimensions satisfy K ≡ N−K ≡ 1 (mod 2m) and min{K,N−K} ≥ 2m+1.The same conclusion applies to the dual code's dimension.Source: §17.12.3 · pp. 608–609

and Character Sums

  • Character orthogonality supports root-count congruences, quadratic-form value distributions, primitive-element counts, and recurrences for extension-field character sums.The chapter also uses trace fibers for point counts on a family of characteristic-two curves, and connects power-sum solution counts and orbit-sequence correlations to character sums.Source: and Character Sums · p. 615

18.1 Additive and Multiplicative Characters

  • Additive characters are parametrized by Tr_K/Fp(ax), multiplicative characters by their values on a generator, and nontrivial character sums vanish by orthogonality.Source: §18.1 · pp. 616–617
  • For trace evaluation Tj, the image has dimension dj over Fp, and choosing u with relative trace 1 gives each image function a unique expression Tj(ub).Here dj is the p-Frobenius orbit length of gj; using the subfield Kj removes coefficient redundancy.Source: §18.1 · pp. 617–618
  • Over F16, x^5 takes values in F4 and yields only four distinct trace functions, each represented by four coefficients, with kernel F4.For a = 1, the trace of x^5 is identically zero although X^5 is a nonzero polynomial function.Source: §18.1 · p. 618

18.2 Fourier Transforms and Root-Count Formulas

  • The Fourier-transform subsection begins by defining an additive Fourier transform for functions F: K → C.Source: §18.2 · p. 618
  • Character orthogonality expresses the number of solutions to P(x) = b as an exact count, while trace-fiber translation preserves Fourier support and changes the sign at frequency one.Unlike point indicators valued in characteristic p, complex character orthogonality retains integer solution counts.Source: §18.2 · pp. 619–620

18.2.1 The Fourier support uncertainty principle

  • For nonzero f on a finite abelian group G, the Fourier support sizes satisfy |supp f| |supp bf| ≥ |G|.For finite-field additive groups, the trace pairing parametrizes the characters.Source: §18.2.1 · p. 620

18.3 Moments of Character Sums and Power-Sum Equations

  • Character-sum moments reduce to power-sum equation fiber counts, and when p > d, matching first d power sums determine the same root multiset with multiplicities.For F = (X^3 − X)^2, the collision count is 153 and the unnormalized sum of squares is 4131; the characteristic condition matters, as F3 gives a counterexample when d = 3.Source: §18.3 · pp. 621–622

18.4 Fourier Transforms and Adjoints of Linear Operators

  • For a linear map A, the Fourier transform of its fiber-sum function is obtained by composing the transform with the adjoint A*, and im A = (ker A*)⊥.Thus the kernel of a linearized polynomial, a trace-orthogonal complement, and Fourier support describe the same linear equation.Source: §18.4 · p. 624

18.5 Gauss and Jacobi Sums

  • Gauss sums scale under nonzero frequency changes by χ(a)^−1, and Jacobi sums have explicit evaluations for inverse and trivial characters.For χ ≠ ε, J(χ, χ^−1) = −χ(−1); J(ε, χ) = J(χ, ε) = −1 and J(ε, ε) = Q − 2.Source: §18.5 · p. 625

18.6 Short Linear Relations in Multiplicative Subgroups and Gaussian Periods

  • Multiplicative orders and Frobenius orbits alone do not determine joint linear dependence in a subgroup; the section studies shortest relations, trace hyperplanes, and Gaussian-period moments.The focus is on linear relations among subgroup elements rather than only on individual orbit structure.Source: §18.6 · p. 627

18.6.1 Linear relation length and multiplicative orders

  • If λq(H) ≥ s + 1, then ordd(q) ≥ s for every divisor d > 1 of n, and every prime divisor ℓ of n satisfies ℓ ≥ s + 1.Source: §18.6.1 · p. 628

18.6.2 When every Frobenius orbit is a normal basis

  • When λq(H) = k + 1, all nonzero q-cyclotomic cosets modulo n have length k, H \ {1} partitions into normal-basis Frobenius orbits, and each minimal polynomial has nonzero coefficients.The same condition implies ordd(q) = k for every d | n, d > 1, n | Φk(q), and n ≡ 1 (mod k).Source: §18.6.2 · p. 628
  • All eighteen elements satisfy the stated order, orbitwise normality, and full-support conditions, yet 3β + 5β² + β⁵ = 0 shows that distinct Frobenius orbits can fail joint independence.The exponents 1, 2, and 5 lie in three distinct nonzero Frobenius orbits.Source: §18.6.2 · p. 629
  • If λq(H) ≥ 2r+1, weighted sums supported on at most r elements are distinct; in particular, λq(H) ≥ 4 excludes weighted three-term relations.The passage also states that λq(H) ≥ 5 gives uniqueness of weighted two-term sums.Source: §18.6.2 · p. 630

18.6.3 Trace hyperplanes and Singer difference sets

  • The hyperplane criterion connects subgroup general position with trace codes and projective arcs, and the trace code Cβ is MDS under the stated equivalence.For k = 3, the example distinguishes noncollinear triangles within individual Frobenius orbits from a dependent triple drawn across different triangles.Source: §18.6.3 · p. 631
  • Trace-zero projective points form a Singer difference set, and subgroup general position becomes an intersection constraint with its translates.The passage also cites cyclic arcs of Singer type in the projective plane [44].Source: §18.6.3 · pp. 631–632

18.6.4 Three-term relations from one cyclotomic intersection number

  • When g = 1, the theorem exactly enumerates dependent three-element subsets using a scalar-saturated cyclotomic intersection number.The q − 2 term counts unavoidable scalar solutions; for q = 2 the criterion reduces to (1 + H) ∩ H = ∅, whereas for q > 2 ordinary sum-freeness does not exclude all weighted relations.Source: §18.6.4 · pp. 632–633

18.6.5 Gaussian periods and their first three moments

  • The Gaussian-period setup fixes Q = q^k, e = (Q − 1)/M, an additive character of Fq, and representatives for L×/U.It defines Ψ as the composition of ψ with the trace from L to Fq.Source: §18.6.5 · p. 633

periods

The section develops character-sum methods for counting primitive and primitive normal elements, analyzing quadratic forms and trace fibers, and deriving extension-field sums and bounds. It also studies exact-period root layers and their affine compression, using orbit and return-map structure to describe factorization, with supporting field and polynomial tools.

periods

  • The third Gaussian-period moment counts three-term subgroup relations, and the periods are additive Cayley-graph eigenvalues without requiring strong regularity.Individual period values give trace-code weights, whereas moments of intersection numbers detect short subgroup relations and the dual code's minimum distance.Source: periods · pp. 633–634

18.6.6 Higher factorial moments and recovery of relation length

  • Factorial hyperplane moments count subsets by rank, and successively testing R_s identifies the shortest relation length; the first k period moments determine λ_q(H).The exact recovery principle does not guarantee that high moments are easy to evaluate, since they encode substantial additive information.Source: §18.6.6 · p. 635

18.6.7 Base-field descent, a seven-element example, and Fourier minors

  • Scalar extension preserves subgroup dependence, while Fourier-minor nonvanishing yields λ_q(H) = k + 1 when n = ℓ is prime and p > (k!)^(ℓ−1).The Fourier-minor deduction relies on the classical prime-order theorem; at composite n, minors may vanish in characteristic zero.Source: §18.6.7 · pp. 636–638

18.7.1 Exact Counts for Two-Variable Equations

  • Character orthogonality gives exact solution counts for a x^u + b y^v = c using multiplicative characters whose orders divide gcd(u, q − 1) and gcd(v, q − 1).The common characters in the count are precisely those whose orders divide the gcd of those two gcd values.Source: §18.7.1 · pp. 638–639

18.7.2 Multiple Jacobi Sums and the Product Character

  • For multiple Jacobi sums with nontrivial characters, Gauss-sum expressions and square-root bounds depend on whether their product character is trivial.The product character determines which of the two cases in the proposition applies.Source: §18.7.2 · p. 639

18.7.3 Exact Counts and Weil-Type Bounds for Diagonal Equations

  • Character expansion gives exact counts and Weil-type square-root bounds for diagonal equations, with the error-term scale determined by whether the product character is trivial.The bounds follow from the square-root magnitude of Gauss sums; when some d_i = 1, the solution count is q^(n−1).Source: §18.7.3 · pp. 641–642

18.8.1 The Primitivity Indicator

  • The primitive-element indicator is expanded in multiplicative characters, with the character sum distinguishing primitive from nonprimitive elements.The expansion is defined to vanish at zero and also covers the case where the multiplicative group has order one.Source: §18.8.1 · p. 643

18.8.2 Character Sums over Trace Fibers

  • Gauss-sum expressions for trace-fiber character sums yield different error scales according to whether the character is trivial on the base-field multiplicative group.Characters with trivial restriction contribute only to the zero-trace fiber, which must be counted separately from nonzero-trace fibers.Source: §18.8.2 · p. 644

18.8.3 Counting Formulas and Existence Conditions

  • The section gives an exact formula for primitive elements of each prescribed trace and derives sufficient conditions for nonzero prescribed traces and for trace zero.These conditions are sufficient, not necessary; when they fail, the exact formula or other methods may still be needed.Source: §18.8.3 · pp. 645–646
  • For every prime power q and n ≥ 1, a primitive element of Fq^n exists with nonzero trace to Fq.The argument sums over all nonzero-trace fibers, and primitive elements of prescribed trace also count primitive polynomials with the corresponding next-to-leading coefficient, with count Na/n.Source: §18.8.3 · pp. 647–648

18.9.1 A scaling group that preserves normality

  • A normality-preserving scaling subgroup reduces the primitivity test: a coset contains a primitive element exactly when it generates the quotient group.Scaling within that coset preserves normality, while the Frobenius module structure continues to detect it.Source: §18.9.1 · pp. 649–650

18.9.2 Local trace indicators and the joint estimate

  • Local Frobenius-component indicators and multiplicative-character expansions give a joint estimate for elements satisfying primitivity and the local normality conditions.Taking the full conditions yields existence of a primitive normal element when the estimate's sufficient inequality holds; a separate criterion estimates primitive elements in a fixed weighted-trace fiber.Source: §18.9.2 · pp. 651–652

18.9.3 Sieving only the remaining local conditions

  • When the basic sufficient condition fails, a local density sieve retains the density of conditions already met and excludes each remaining obstruction in turn.The resulting criterion q^n/2 > C(e, g) suffices for existence of a primitive normal element.Source: §18.9.3 · pp. 652–653

18.9.4 Two generation conditions among elements of full degree

  • For n ≥ 3, the section introduces a comparison of two types of generators among elements of full extension degree, noting that quotient generation forces full degree.Source: §18.9.4 · pp. 653–654
  • A generator of E×/C has degree n over k, and inclusion–exclusion gives a sufficient counting criterion for a primitive normal element.The criterion counts elements satisfying both generation conditions within the full-degree elements.Source: §18.9.4 · p. 654

18.9.5 Multiplicative obstructions automatically excluded by normality

  • Normality automatically excludes certain multiplicative subgroup obstructions, so prime factors already excluded need not enter the multiplicative sieve.For example, the text handles (3, 4) and (5, 8) this way.Source: §18.9.5 · pp. 655–656

18.9.6 Eight boundary cases and general existence

  • For every prime power q and positive integer n, F_qn/F_q has a primitive normal element; the proof covers eight boundary cases using counting, automatic exclusion, and local sieves.The eight exceptional pairs are (2, 3), (2, 6), (2, 15), (3, 4), (3, 8), (5, 4), (5, 8), and (7, 6).Source: §18.9.6 · pp. 656–657

18.10 The Quadratic Character and a Complete Counting Example

  • Quadratic-character counting gives solution counts for quadratic equations over odd finite fields, including a separate assertion for the nonzero-parameter case.The character is 1 on nonzero squares, −1 on nonsquares, and 0 at zero; y² = b has 1 + χ(b) solutions.Source: §18.10 · p. 658

18.11 The Chevalley–Warning Congruence for Root Counts

  • If the sum of the polynomial degrees is less than the number of variables, the common-zero count over F_q is divisible by its characteristic p.For homogeneous positive-degree polynomials under the same degree condition, there is a nonzero common zero; in particular, quadratic forms in at least three variables have a nontrivial zero.Source: §18.11 · pp. 658–659

18.12 Polarization, Radicals, and Classification of Quadratic Forms

  • Quadratic forms have canonical forms determined differently in odd and even characteristic; in odd characteristic, the isometry type is fixed by dimension, polar rank, and discriminant square class.In even characteristic the polar rank is 2s, and the canonical forms distinguish whether the quadratic form vanishes on the radical; polar rank alone need not determine solution counts.Source: §18.12 · pp. 661–662
  • Quadratic forms split into canonical types: in characteristic two, hyperbolic blocks split off until the remainder is zero-dimensional or anisotropic of dimension two.A two-dimensional block ax2+xy+by2 with a nonzero is anisotropic exactly when Trk/F2(ab)=1.Source: §18.12 · p. 662

18.13 Value Distributions of Quadratic Forms: Odd Characteristic

  • Quadratic-form value counts are determined by rank and discriminant square class in odd characteristic; over F3, x2 + y2 + z2 has counts 9, 6, and 12 for values 0, 1, and 2.Forms of the same rank can have different distributions when their discriminant square classes differ.Source: §18.13 · pp. 663–664

18.14 Value Distributions of Quadratic Forms: Characteristic Two

  • In characteristic two, the value distribution depends on the polar rank, the quadratic form on its radical, and a sign distinguishing hyperbolic from anisotropic types.When Q|R is nonzero, every value has q^(m−1) preimages; when Q|R=0, the sign distinguishes H^s from H^(s−1) ⊥ Nδ.Source: §18.14 · pp. 664–665

18.15 Trace Quadratic Forms and Adjoints of Linearized Operators

  • For Q(x)=Tr(xL(x)), every quadratic form on E has such a representation, and the polar radical is ker(L+L*).The polar rank can be computed from the reduced linearized representation; in characteristic two, the values of Q on the radical must also be retained.Source: §18.15 · p. 666

18.15.1 Fourier Support of Quadratic Phases

  • For a quadratic phase over F2, Fourier support is an affine coset of the polar radical’s orthogonal complement, with its direction and coefficient magnitudes determined by the radical.For Q=QL, the support is a coset of im(L+L*), and when Q vanishes on the radical it is im(L+L*) itself.Source: §18.15.1 · pp. 667–668

18.15.2 Differential Kernels and Trace Components of a Field-Valued Quadratic Map

  • Each nonempty solution set of F(x+a)+F(x)=c is a coset of ker La; for F(x)=x3, trace-component radicals vary with the extension degree.For odd n, each nonzero trace parameter has a one-dimensional radical; for even n, (2^n−1)/3 parameters have two-dimensional radicals and the rest have zero radicals.Source: §18.15.2 · pp. 669–670

18.16 Character Lifts to Extensions and Weighted Orbit Products

  • The Davenport–Hasse multiplication formula relates Gauss sums for η of order m | q−1 and remains valid when χ^m is trivial or m=1.Its proof compares weighted orbit products and isolates the degree-m coefficient using Newton’s identities.Source: §18.16 · pp. 672–674
  • When χ, λ, and χλ are nontrivial, the Jacobi sum lifts through extensions by substituting the Gauss-sum lifting formula into the Gauss-sum ratio identity.Norm and trace surjectivity preserve the nontriviality of the lifted characters and additive character.Source: §18.16 · p. 675
  • The Hasse–Davenport lifting formula expresses extension-field Gauss sums for lifted characters as signed powers of a single base-field Gauss sum.Multiplicative characters lift by norm and additive characters by trace; orbit repetitions control both lifts.Source: §18.16 · p. 671, §18.17 · p. 676

18.17.1 Polynomial Phases and Degree Cancellation

  • Phase reduction must include the character parameter: it replaces af by a unique reduced polynomial R while preserving the trace phase over every extension.The reduction removes positive exponents divisible by p; the resulting polynomial decomposition is unique, though evaluation on one fixed field may introduce further degeneracy.Source: §18.17.1 · pp. 677–678
  • The reduced-phase classification separates constant, linear, and degree-at-least-two cases; linear phases have zero sums and L_f(u)=1, while degree-d phases have L_f degree at most d−1.For degree d≥2, p does not divide d.Source: §18.17.1 · p. 679

18.17.2 Characteristic Roots and Recurrences

  • When L_f(u) is a polynomial of degree m, the extension-field sums satisfy an initial relation for 1≤r≤m and a homogeneous order-m recurrence for r>m.The recurrence coefficients are the coefficients ℓ_i of the generating polynomial.Source: §18.17 · p. 676, §18.17.2 · p. 680
  • For general character sums, polynomiality yields a constant-coefficient recurrence, but does not by itself bound the absolute values of its characteristic roots.The recurrence coefficients lie in C, and the complex-valued sequence does not inherit finite-state eventual periodicity.Source: §18.17.2 · pp. 680–681

18.17.3 A Second-Order Recurrence for Kloosterman Sums

  • A second-order recurrence with K0 = −2 and K1 determines the extension-field Kloosterman sums, which also admit a Dickson-polynomial representation in K1 and q.The recurrence follows from the two characteristic roots of 1 + K1u + qu2; q is an integer in C in the polynomial representation.Source: §18.17.3 · pp. 681–682

18.18.1 The Curve Model and Trace Fibers

  • For b ≠ 0 in characteristic two, the nonsingular cubic Eb converts extension-field point counts into one-variable Kloosterman sums through the Artin–Schreier trace criterion.The curve has a unique point at infinity; b = 0 would make (0, 0) singular.Source: §18.18 · p. 683, §18.18.1 · p. 684

18.18.2 Recovering All Extension-Field Point Counts from One Count

  • The quantities An = qn + 1 − Nn satisfy a second-order recurrence, so N1 and q determine all extension-field point counts.The recurrence uses the initial-value convention A0 = 2.Source: §18.18.2 · p. 685

18.18.3 The Point-Count Generating Function and Frobenius Fixed Points

  • The curve zeta function is rational, its point-count differences are power sums of two roots, and its coefficients record successive Frobenius fixed-point counts.The recurrence and rational generating function alone do not prove |α| = |β| = √q; that bound requires the Hasse theorem.Source: §18.18.3 · pp. 686–687

18.19 Weil bounds for polynomial character sums

  • The Weil-bound argument combines an auxiliary polynomial controlling trace and power-value fibers with extension-uniform estimates to bound characteristic roots.The auxiliary construction uses Stepanov’s method to impose high-multiplicity zeros; the generating-polynomial degree supplies the precise final constant.Source: §18.19 · pp. 687–688

18.19.1 Bounding characteristic roots by extension-field power sums

  • A uniform bound on sufficiently large extension-field power sums bounds every characteristic root’s modulus, and estimates over even extension degrees suffice.Source: §18.19.1 · pp. 688–689

18.19.2 An auxiliary polynomial for trace fibers

  • Under the stated degree and size conditions, the trace-fiber construction gives an auxiliary polynomial H with H(x) = Bb(x) on the specified fiber and all its exponents divisible by A.Its coefficient polynomials eij have degree below S, with q(K + 1)S undetermined coefficients.Source: §18.19.2 · pp. 689–690
  • A uniform estimate is established for trace fibers over sufficiently large extensions of even degree.The proof combines fiber counts with additive-character orthogonality.Source: §18.19.2 · p. 691

18.19.3 The Weil bound for additive character sums

  • For a nonconstant reduced additive phase of degree d prime to p, the character sum has square-root cancellation; constant phases are handled by an exact formula.Phase reduction identifies the effective degree and nondegeneracy condition.Source: §18.19.3 · p. 692

18.19.4 Multiplicative character sums: finite recurrences from residue-class algebras

  • A generating polynomial of degree at most r −1 expresses extension-field multiplicative sums as power sums of at most r −1 complex numbers.The resulting recurrence, together with bounds on its characteristic roots, yields the precise factor r −1 in the final estimate.Source: §18.19.4 · pp. 693–694

18.19.5 An auxiliary polynomial for multiplicative fibers

  • The multiplicative auxiliary-polynomial method proves a coarse square-root bound with a constant depending only on character order and polynomial degree, not field size.Linear conditions produce a nonzero polynomial whose zeros have high multiplicity across a chosen fiber; the root-degree comparison bounds the fiber size.Source: §18.19.5 · pp. 696–697
  • The multiplicative sum satisfies |S1| ≤ (r −1)√q, where r is the number of distinct roots of f; the estimate excludes f = ah^n.The constant r −1 comes from the generating-polynomial degree, while the auxiliary-polynomial argument supplies square-root scale.Source: §18.19.5 · pp. 698–699

Exercises

  • The exercises ask readers to verify primitive elements of nonzero trace, prove a sixth-moment identity for cubic-phase sums, and recover Fourier orthogonality.They also include a finite-field solvability problem for a binary quadratic equation and comparison with Chevalley–Warning.Source: Exercises · p. 699

Compression, and Orbit Counts

  • Affine invariants compress affine orbits in an exact-period layer into new root coordinates, whose factorization is recovered by return maps.The introductory overview also connects exact-period layers to polynomial divisibility, coefficient gaps, and Euler products for global point counts.Source: Compression, and Orbit Counts · p. 707

19.1 Fixed-Point Sets and Exact-Period Layers

  • Exact-period polynomials are monic and have no repeated roots, and polynomials with distinct indices are pairwise coprime.The corresponding exact-period layer consists of roots of monic irreducible polynomials of that degree.Source: §19.1 · p. 708

19.2 First Occurrence and Parity Cancellation

  • Each irreducible f ≠ X first divides Cq,m at m = deg f, and the parity-cancellation quotient has each degree-n irreducible factor exactly once.The polynomials Cq,m have no repeated roots, and gcd(Cq,a, Cq,b) differs from Cq,gcd(a,b) only by a nonzero constant.Source: §19.2 · pp. 709–710

19.3 The First Nonconstant Term and Existence of Irreducible Polynomials

  • The first nonconstant term makes Eq,n nonconstant; together with parity cancellation, this proves that an irreducible polynomial of every positive degree n exists over Fq.The construction removes factors of shorter periods, while the coefficient argument ensures the remaining polynomial is nonconstant.Source: §19.3 · p. 711

19.4 The Square-Free Kernel and Base-Field Lifting

  • Under q-to-q^s Frobenius, an element with q-period d has q^s-period d/gcd(d,s); for q=2 and n=12, E2,12 = E4,6 ≡ 1 + X^3 (mod X^15), with degrees 4 through 14 vanishing.Self-reciprocity gives the corresponding coefficient gap at the high-degree end.Source: §19.4 · p. 713

19.5 Connection with Cyclotomic Polynomials

  • Exact-period layers split into cyclotomic root sets by multiplicative order; E2,4 = Φ5 Φ15, whose quartic factors have roots of orders five and 15.The cyclotomic polynomials are reduced in the field’s characteristic.Source: §19.5 · p. 714

19.5.1 Decomposition by Multiplicative Order and Counting

  • For each e dividing q^n − 1 with ord_e(q) = n, the layer contains ϕ(e) elements of order e in ϕ(e)/n Frobenius orbits; primitive-root irreducibles number ϕ(q^n − 1)/n.The order classes partition the exact-period layer, and each orbit has n elements.Source: §19.5.1 · pp. 714–715

19.5.2 Base-Field Extension and Reciprocal Pairing

  • Extending the base field to F_{q^r} splits each original order-e orbit into g = gcd(n,r) orbits of length n/g, while exact-period polynomials need not coincide.Reciprocal pairing occurs within each multiplicative-order class; in an odd-degree exact-period layer, irreducible factors occur in pairs.Source: §19.5.2 · pp. 715–716

19.6.1 The Ring of Affine Invariants

  • Every affine invariant in one variable has a unique expression as a polynomial in Θq.Translation invariance first gives polynomials in X^q − X; dilation invariance restricts the powers to multiples of q − 1.Source: §19.6.1 · p. 717

19.6.2 Compressed Root Sets and Orbit Quotients

  • For α, β outside k, Θq(α) = Θq(β) exactly when β = aα + b for a ∈ k× and b ∈ k; each nonempty such fiber is one orbit of size q(q − 1).Thus the compression coordinate separates affine-group orbits outside the base field.Source: §19.6.2 · p. 717
  • Gq,n is monic and squarefree, with irreducible factors corresponding to Frobenius orbits on affine-orbit classes; compression can lower root periods.For n = 2, all compression values equal −1.Source: §19.6.2 · p. 719

19.7 Compressed Periods, Return Orders, and Factor Lifting

  • The compressed period t gives the fiber’s first return time, while its return permutation determines original root degrees and the degrees and number of lifted factors.Source: §19.7 · p. 720

19.7.1 Compressed Periods and Orders of Affine Returns

  • The unique affine return g satisfies e = ord(g) = n/t; its order is 1, p, or a divisor of q −1, and every permitted nontrivial reduction factor occurs.Source: §19.7.1 · pp. 720–722

19.7.2 Computing the Affine Return Order from the Compression Value

  • The return order can be computed from the compression value using its norm and, when the norm is one, an orbit-sum trace test; for q = 2, e is 1 or 2 according to absolute trace.Source: §19.7.2 · pp. 722–724

19.7.3 Lifting Irreducible Factors

  • If H is a degree-t compressed factor and e = n/t, then H(Θq(X)) has q(q −1)/e distinct irreducible factors, each of degree n.Over k(c), the fiber polynomial Θq(X) − c has q(q −1)/e factors, each of degree e; the lifted factor count and degrees can be computed from H’s constant term and a remainder of Rq,t. For q > 2 the composition is reducible; for q = 2 it is irreducible exactly when ht−1 = 1.Source: §19.7.3 · pp. 724–725
  • When n is odd, only degree-n factors H are possible.Source: §19.7.3 · p. 727
  • Two six-root fibers yield three irreducible quadratic factors and two irreducible cubic factors, as return orders two and three determine orbit counts and factor degrees.The example gives Θ3(X) −2 as a product of three irreducible quadratics and reports two irreducible cubic factors for Θ3(X) −1.Source: §19.7.3 · p. 728

19.7.4 Return Mechanisms for Power and Affine Compression

  • For power compression, the period-reduction factor equals the full root-block size, whereas affine compression uses the chosen root’s return period, which can be smaller than its fiber.The relative degree is the return period within the fiber; power compression uses κC and affine compression uses ord(g).Source: §19.7.4 · p. 729

19.8 Sparse Recurrences and Base-Field Lifting

  • In F2, roots in the same compressed fiber can have the same field degree but different multiplicative orders, while the compression value’s degree is determined by the return period.For the two quartic factors, translation interchanges the original period-four orbits in one case; the roots have multiplicative orders 15 and five, respectively.Source: §19.8 · pp. 731–732

19.9 Binary Moore Forms and Homogeneous Period Layers

  • Exact-period layers are stable under fractional linear transformations, and binary Dickson invariants and a Frobenius recurrence express their compatibility with linear-group actions.The invariants have degrees q^2−1 and q^2−q; setting Y = 1 recovers the corresponding univariate period-layer and affine-compression formulas.Source: §19.9 · pp. 733, 735

19.10 Period Counts and Euler Products

  • Weighting Frobenius orbits yields a product encoding their counts; setting all weights to one recovers ordinary point counts, while character weights give a weighted product.The same regrouping principle applies to infinitely many orbits when only finitely many have any given length.Source: §19.10 · p. 736

Exercises

  • The exercise hint shows how to realize every nontrivial period-reduction factor permitted by Proposition 19.19 using an affine relation with prescribed coefficient c.For c ∈ k×, choose Θq(α) = c and show the unique relation α^q = aα + b has a = c.Source: Exercises · p. 737

Tools

  • The appendix’s field-extension and polynomial tools apply over arbitrary fields and do not rely on finite-field existence or structure theorems..Source: Tools · p. 739

A.1 Field Embeddings and a Specified Base Field

  • A specified embedding identifies the base field with a subfield, and homomorphisms preserving it are k-linear; bijective ones are k-isomorphisms.The k-automorphisms of an extension form Aut_k(E).Source: §A.1 · p. 739

A.2 Bases, Extension Degrees, and Restriction of Scalars

  • Restriction of scalars gives dim_k V = [L : k] dim_L V, yielding the tower formula and divisibility of intermediate-field degrees.The appendix presents these as basis-expansion arguments independent of finite-field subfield classification.Source: §A.2 · pp. 740–741

A.3 Generated Subfields and Algebraic Extensions

  • Generated subfields consist of fractions of polynomial values, and finite extensions are precisely finitely generated algebraic extensions.Finite generation alone does not imply finite dimension; for example, k(t)/k is generated by t but has infinite degree.Source: §A.3 · pp. 741–742

A.4 Simple Extensions, Splitting Fields, and Separability

  • Splitting fields are finite extensions, while finite-field Frobenius orbits show that irreducible polynomials are separable and their root degrees equal their least Frobenius periods.The appendix also notes that finite extensions over general fields can be inseparable.Source: §A.4 · pp. 743–744

A.5 Divisibility, Bézout’s Identity, and Unique Factorization

  • Polynomial division yields the root criterion X − a | A exactly when A(a) = 0, while Bézout’s identity supports irreducible-factor primality and unique factorization.Every nonconstant polynomial has a monic irreducible factor and factors into monic irreducibles up to a constant.Source: §A.5 · pp. 744–746

A.6 The Chinese Remainder Theorem and Interpolation

The Chinese remainder theorem and interpolation assemble local polynomial data, while Frobenius periods organize finite subfields and automorphisms. The section also characterizes algebraic extensions by pointwise periods and finite fields by a common period.

A.6 The Chinese Remainder Theorem and Interpolation

  • For pairwise coprime polynomial moduli, the Chinese remainder theorem identifies classes modulo their product with tuples of local remainder classes, with a unique representative of degree less than the product’s degree.Separating idempotents provide the local components; the theorem motivates decomposing polynomial problems into local ones.Source: §A.6 · pp. 746–747
  • A polynomial of degree less than s uniquely interpolates any prescribed values at s distinct elements, and repeated roots are detected by gcd(P, P′) ≠ 1.The interpolation polynomials are the Lagrange basis polynomials; the repeated-root criterion holds in a splitting extension.Source: §A.6 · pp. 747–748

Finite Periods

  • Every finite field has an algebraic closure constructed as an increasing union of finite extension fields.At each stage, a finite extension is chosen to split the relevant finite collection of polynomials; every element of the union is algebraic over the base field.Source: Finite Periods · pp. 749–750

Common Notation in an Algebraic Closure

  • Inside a fixed algebraic closure, F_p^a is contained in F_p^b exactly when a divides b; its absolute automorphisms correspond to compatible families of Frobenius exponents.The automorphism group is procyclic, with integer powers of Frobenius dense, but it is not cyclic as an abstract group.Source: Common Notation in an Algebraic Closure · p. 750, §B.1 · pp. 751–752

B.2 Pointwise Periods and a Common Period

  • An extension of F_q is algebraic exactly when every element has a finite Frobenius period, and it is finite exactly when one common exponent makes Frobenius the identity.A common period bounds the field by the root bound for X^(q^N) − X.Source: §B.2 · p. 752

B.3 Intermediate Fields Determined by Allowed Periods

Intermediate fields in a fixed algebraic closure are classified by their allowed Frobenius periods. The section then distinguishes field isomorphism types from chosen identifications and completes sufficient bounds for the primitive normal basis theorem, leaving eight stated exceptions.

B.3 Intermediate Fields Determined by Allowed Periods

  • Intermediate fields correspond bijectively to nonempty sets of positive integers closed under divisors and least common multiples, and those integers are exactly the occurring Frobenius periods.An infinite intermediate field can have only power-of-two periods and still fail to contain a root of any irreducible cubic over the base field.Source: §B.3 · pp. 753–754

B.4 Uniqueness of the Isomorphism Type and Choice of an Isomorphism

  • Finite extensions of the same degree have the same isomorphism type, but a particular isomorphism depends on the chosen image of a generator.For the two displayed quadratic models over F_2, the generator may map to either β or β² = β + 1.Source: §B.4 · pp. 754–755

Appendix C

  • The appendix reduces the primitive normal basis bound to estimates combining Frobenius orbit lengths and multiplicative orders, with finite tables checking boundary cases.Its stated purpose is to determine when the basic bound holds; eight pairs not covered by it are handled in the main text.Source: Primitive Normal Basis Theorem · p. 757, §C.1.2 · p. 760

C.1.1 Irreducible Factor Counts: Low-Degree Roots and the Remaining Degree

  • Low-degree roots of T^m − 1 yield bounds on its irreducible-factor count, while retaining allowed small prime factors gives W(R) < 3R^(1/4) when R is odd.The factor-count bounds remain valid when the characteristic divides n after its characteristic-power part is removed.Source: §C.1.1 · p. 758, §C.1.2 · p. 759

C.2.1 Degrees That Are Powers of the Characteristic

  • Every characteristic-power degree satisfies the basic bound, and the degree-three and degree-five analysis leaves only (2, 3) among its stated cases.The text explicitly says all characteristic-power degrees are covered; it identifies (2, 3) as the remaining case in the degree-three analysis.Source: §C.2.1 · p. 760, §C.2.2 · p. 761

C.2.3 Larger Base Fields: q ≥16

  • For q ≥ 16, the basic bound holds for every n ≥ 3.The proof separates cases according to whether n divides q − 1 and uses monotone comparisons for the remaining parameters.Source: §C.2.3 · pp. 761–762

C.3 33 Monotone Families over Small Base Fields

  • The small-base-field analysis organizes 33 monotone families and checks the remaining explicit boundary pairs to complete the exception accounting.For the listed boundary set, degrees three, five, and characteristic powers are removed before identifying the stated exceptions.Source: §C.3 · pp. 762, 764
  • The explicit boundary analysis identifies exactly eight exceptions to the basic bound, including (2, 3), after removing degree three, degree five, and characteristic-power cases.The listed boundary set contains 42 pairs; the text states these, together with (2, 3), give precisely the eight exceptions.Source: §C.2.2 · p. 761, §C.3 · p. 764
Loading 2610.36727v1…