Overview

  • How are finite fields constructed?
  • How does Frobenius determine conjugates and subfields?
  • How does an irreducible polynomial factor over a larger finite field?
  • How do trace, norm, and root order determine polynomial coefficients and degrees?

Fields from irreducible polynomials

Let q=prq=p^r, where pp is prime. A finite field with qq elements is denoted by Fq\mathbb F_q. Its characteristic is pp; as a vector space over Fp\mathbb F_p, it has dimension rr.

If f∈Fq[x]f\in\mathbb F_q[x] is monic and irreducible of degree nn, then K=Fq[x]/(f)K=\mathbb F_q[x]/(f) is a field with qnq^n elements. Writing Ξ±=xβ€Šmodβ€Šf\alpha=x\bmod f, every element has a unique expression a0+a1Ξ±+β‹―+anβˆ’1Ξ±nβˆ’1a_0+a_1\alpha+\cdots+a_{n-1}\alpha^{n-1}. Addition is coefficientwise; multiplication is followed by reduction modulo ff.

Example

The polynomial x2+x+1x^2+x+1 has no root in F2\mathbb F_2. Thus F4=F2(Ξ±)\mathbb F_4=\mathbb F_2(\alpha), where Ξ±2=Ξ±+1\alpha^2=\alpha+1. Its elements are 0,1,Ξ±,Ξ±+10,1,\alpha,\alpha+1, and Ξ±3=1\alpha^3=1. The ring Z/4Z\mathbb Z/4\mathbb Z is different: it has characteristic four and is not a field.

References 1

Existence and uniqueness

In an algebraic closure of Fq\mathbb F_q, the roots of xqnβˆ’xx^{q^n}-x form a field. Indeed, the identity (a+b)qn=aqn+bqn(a+b)^{q^n}=a^{q^n}+b^{q^n} gives closure under addition, and multiplication and inversion preserve the equation. The derivative is βˆ’1-1, so there are exactly qnq^n distinct roots.

Every field with qnq^n elements is a splitting field of this polynomial over Fq\mathbb F_q. Uniqueness of splitting fields therefore gives uniqueness up to Fq\mathbb F_q-isomorphism. We may choose all these fields inside one algebraic closure.

References 1

Frobenius and conjugates

The map Οƒ(a)=aq\sigma(a)=a^q is an automorphism of Fqn\mathbb F_{q^n} fixing Fq\mathbb F_q. It has order nn: its nn-th power is the identity, while Οƒj=1\sigma^j=1 with 0<j<n0<j<n would give qnq^n roots of xqjβˆ’xx^{q^j}-x. Consequently Gal⁑(Fqn/Fq)=βŸ¨ΟƒβŸ©β‰…Cn.\operatorname{Gal}(\mathbb F_{q^n}/\mathbb F_q)=\langle\sigma\rangle\cong C_n.

If Ξ±\alpha has degree dd over Fq\mathbb F_q, its conjugates are Ξ±,Ξ±q,…,Ξ±qdβˆ’1\alpha,\alpha^q,\ldots,\alpha^{q^{d-1}}. They are distinct, and its minimal polynomial is their product mΞ±(x)=∏i=0dβˆ’1(xβˆ’Ξ±qi).m_\alpha(x)=\prod_{i=0}^{d-1}(x-\alpha^{q^i}). Frobenius permutes the roots, so the coefficients belong to its fixed field Fq\mathbb F_q.

References 1

Subfields

There is a subfield FqdβŠ†Fqn\mathbb F_{q^d}\subseteq\mathbb F_{q^n} exactly when d∣nd\mid n, and it is unique. It consists of the elements fixed by Οƒd\sigma^d. This is the Galois correspondence for the subgroups of a cyclic group.

Inside a fixed algebraic closure, Fqa∩Fqb=Fqgcd⁑(a,b),FqaFqb=Fqlcm⁑(a,b).\mathbb F_{q^a}\cap\mathbb F_{q^b}=\mathbb F_{q^{\gcd(a,b)}},\qquad \mathbb F_{q^a}\mathbb F_{q^b}=\mathbb F_{q^{\operatorname{lcm}(a,b)}}. In particular, an element of Fqn\mathbb F_{q^n} has degree nn if and only if it lies in none of the maximal proper subfields Fqn/β„“\mathbb F_{q^{n/\ell}}, where β„“\ell ranges over the prime divisors of nn.

References 1

Changing the field

Theorem

Let f∈Fq[x]f\in\mathbb F_q[x] be irreducible of degree nn. Over Fqm\mathbb F_{q^m}, it has exactly gcd⁑(n,m)\gcd(n,m) distinct irreducible factors, each of degree n/gcd⁑(n,m)n/\gcd(n,m).

Proof. Frobenius acts on the roots of ff as an nn-cycle. Over Fqm\mathbb F_{q^m}, the relevant Frobenius is Οƒm\sigma^m. Its orbits have length n/gcd⁑(n,m)n/\gcd(n,m), and each orbit is the root set of one irreducible factor.

Example

An irreducible polynomial of degree six over F2\mathbb F_2 remains irreducible over F32\mathbb F_{32}, splits into two cubics over F4\mathbb F_4, and into three quadratics over F8\mathbb F_8. It splits completely over F64\mathbb F_{64}.

References 1

Trace and norm

For α∈Fqn\alpha\in\mathbb F_{q^n}, Tr⁑qn/q(Ξ±)=βˆ‘i=0nβˆ’1Ξ±qi,N⁑qn/q(Ξ±)=∏i=0nβˆ’1Ξ±qi=Ξ±(qnβˆ’1)/(qβˆ’1).\operatorname{Tr}_{q^n/q}(\alpha)=\sum_{i=0}^{n-1}\alpha^{q^i},\qquad \operatorname{N}_{q^n/q}(\alpha)=\prod_{i=0}^{n-1}\alpha^{q^i}=\alpha^{(q^n-1)/(q-1)}. If Ξ±\alpha has degree nn and minimal polynomial xn+anβˆ’1xnβˆ’1+β‹―+a0x^n+a_{n-1}x^{n-1}+\cdots+a_0, then anβˆ’1=βˆ’Tr⁑(Ξ±)a_{n-1}=-\operatorname{Tr}(\alpha) and a0=(βˆ’1)nN⁑(Ξ±)a_0=(-1)^n\operatorname{N}(\alpha).

Thus prescribed trace and norm are prescribed coefficients. The other coefficients are elementary symmetric functions of the conjugates. Newton's identities relate these to the traces of powers, but division by an index divisible by the characteristic is unavailable. This is one reason that prescribed-coefficient arguments require care in small characteristic.

References 2

Roots of unity

Suppose m>1m>1 and gcd⁑(m,q)=1\gcd(m,q)=1, and let Ξ±\alpha have multiplicative order mm. Its degree over Fq\mathbb F_q is the least dβ‰₯1d\ge1 with qd≑1(modm)q^d\equiv1\pmod m, denoted by ord⁑m(q)\operatorname{ord}_m(q). Hence the reduction of Ξ¦m(x)\Phi_m(x) is a product of Ο†(m)/ord⁑m(q)\varphi(m)/\operatorname{ord}_m(q) distinct irreducibles of that degree.

Example

Since ord⁑7(2)=3\operatorname{ord}_7(2)=3, the seventh cyclotomic polynomial has two irreducible cubic factors over F2\mathbb F_2: Φ7(x)=(x3+x+1)(x3+x2+1).\Phi_7(x)=(x^3+x+1)(x^3+x^2+1). Both cubics have roots of multiplicative order seven.

If m=paum=p^a u with p∀up\nmid u, then xmβˆ’1=(xuβˆ’1)pax^m-1=(x^u-1)^{p^a} in characteristic pp. Its distinct irreducible factors are therefore those of xuβˆ’1x^u-1.

References 1

From structure to construction

The structural theory reduces finite-field irreducibility to Frobenius computations. Berlekamp's factorization algorithm and Rabin's irreducibility test made this viewpoint algorithmic. Later construction problems ask for more: few nonzero terms, prescribed coefficients, or roots that also generate a normal basis. These conditions lead to character sums, sieves, and questions about the distribution of irreducible polynomials.

References 3

Related topics

References

  1. Finite Fields

    Conrad, Keith. Author-hosted expository notes.

    Read the source
  2. Finite Fields

    Lidl, Rudolf and Niederreiter, Harald. Edition 2. Cambridge University Press, Encyclopedia of Mathematics and its Applications, vol. 20, 1997.

    Read the source
  3. Handbook of Finite Fields

    Mullen, Gary L. and Panario, Daniel (editors). CRC Press, 2013.

    Read the source
  4. A new proof of the Hansen–Mullen irreducibility conjecture

    Tuxanidy, Aleksandr and Wang, Qiang. Canadian Journal of Mathematics, 70(6), 1373–1389, 2018.

    Read the source
  5. Factoring polynomials over finite fields

    Berlekamp, Elwyn R. Bell System Technical Journal, 46(8), 1853–1859, 1967.

    Read the source
  6. Probabilistic algorithms in finite fields

    Rabin, Michael O. SIAM Journal on Computing, 9(2), 273–280, 1980.

    Read the source
  7. Primitive polynomials over finite fields

    Hansen, Tom and Mullen, Gary L. Mathematics of Computation, 59(200), 639–643, 1992.

    Read the source