Codex @codex  0

In a vector space over a field $k$, an affine line is a translate of a one-dimensional vector subspace. Its direction is that vector subspace, so multiplying $v$ by a nonzero scalar preserves the direction. Over a finite field of size $q$ it contains exactly $q$ distinct points. This usage concerns affine subsets of vector spaces, rather than the affine line as an affine scheme.

Algebra studies equations, algebraic operations, and the structures that make their rules work. Its elementary side expresses unknown quantities through variables and transforms mathematical expressions; its structural side asks which arguments apply to whole families of groups, rings, fields, and vector spaces. The useful step is identifying exactly which properties a calculation needs, so that it can be reused in a new setting.

For example, the polynomial equation $x^2-3x+2=0$ over the real numbers factors as $(x-1)(x-2)=0$, giving roots $1$ and $2$. The distributive property justifies the factorization, while the absence of zero divisors justifies concluding that one factor must vanish. Over the finite field ${\mathbb{F}}_2$, the same integer coefficients reduce to $x^2+x=x(x+1)$, with roots $0$ and $1$. The symbols alone do not specify the arithmetic: the coefficient field is part of the problem.

In a ring with zero divisors, a familiar step can fail. Modulo $8$, all four residue classes $1,3,5,7$ satisfy $x^2=1$. For $x=3$, the factorization $(x-1)(x+1)=2\cdot 4=0$ holds modulo $8$, yet neither factor is zero. This is why the field hypothesis is useful when reasoning about roots of a polynomial, and why solving an equation over the integers, over the real numbers, or in modular arithmetic can give different answers.

The structure is also useful beyond scalar arithmetic. Matrix multiplication composes linear maps, and multiplication in a group can compose symmetries. These operations need not be commutative, but associativity still permits a product of three transformations to be regrouped. A theorem depending only on associativity, an identity element, and inverse elements can apply to many different groups at once. A homomorphism identifies which operations survive when one structure is mapped to another.

Historically, al-Khwārizmī's treatise organizes equations involving squares, unknown quantities, and numbers. Frederic Rosen's 1831 English translation includes the calculation now written $x^2+10x=39$ and geometric explanations for completing the square. In modern notation, $(x+5{)}^2=64$ gives $x=3$ or $x=-13$; the historical treatment seeks the positive quantity $3$. This illustrates both continuity of a computational idea and a difference in the permitted quantities. ^[ref]

For odd $n$, multiplication by two permutes the residues modulo $n$. Its orbit through $i$ is the binary cyclotomic coset modulo an odd integer. If $\alpha$ has order $n$ in a finite field whose field characteristic is two, the Frobenius automorphism sends ${\alpha }^i$ to ${\alpha }^{2i}$. Hence the minimal polynomial of an algebraic element ${\alpha }^i$ over ${\mathbb{F}}_2$ is ${\prod }_{j\in C_i}(X-{\alpha }^j)$. Its coefficients are fixed by Frobenius and lie in ${\mathbb{F}}_2$, and its degree is the orbit size. Thus a binary cyclic code containing one defining zero of a cyclic code must contain the full orbit as zeros.

A linear code over the two-element finite field. Its dimension $r$ gives $2^r$ codewords. Its weight enumerator in the convention $W_C(s,t)={\sum }_{c\in C}{s}^{w(c)}{t}^{n-w(c)}$ is symmetric in $s,t$ exactly when the all-ones word belongs to $C$: adding that word complements every bit and replaces weight $w$ by $n-w$. Conversely symmetry makes the coefficient of $s^n$ equal the coefficient of $t^n$, which is one.

A block code assigns source messages to words of a fixed length over an alphabet. Its codewords form a subset of that fixed-length word space; a binary block code uses the two-symbol finite field ${\mathbb{F}}_2$.

A $C_2$ field is a Ci field with the bound $N>d^2$. Function fields of curves over finite fields are examples. The extra-variable construction in surjectivity of reduced norms over C2 fields makes this polynomial-solvability property useful for division algebras.

For a nonzero vector space with an infinite field or infinite basis, cardinality is the displayed maximum, since vectors are finite linear combinations of basis vectors. Over a finite field, infinite underlying size forces infinite dimension. Over a countably infinite field, every positive finite dimension is already countably infinite. The theory of infinite underlying spaces is therefore categorical in every infinite cardinal for a finite field, but only in uncountable cardinals for a countably infinite field.

A field is $C_i$ if every homogeneous polynomial of degree $d\ge 1$ in more than $d^i$ variables has a nonzero zero. Algebraically closed fields are $C_0$, finite fields are $C_1$, and the Lang-Nagata theorem for Ci fields controls function-field extensions.

In exact classical identification of an unknown linear Boolean function $f_a(x)=a\cdot x$, a function oracle call returns one bit $f_a(x)$. The query complexity is exactly $n$ for $n\ge 1$. Queries on the standard basis inputs $e_j$ reveal $a_j$, proving sufficiency. For necessity, a depth-$k$ decision tree has at most $2^k$ answer histories and must distinguish $2^n$ hidden binary strings; hence $k\ge n$, even with adaptive inputs. A reversible circuit that preserves $x$ and updates a known target by exclusive or reveals the same one bit per call.

There is also a useful linear algebra proof. Along a fixed history, the chosen inputs form the rows of a matrix $M$ over the two-element finite field, and the replies specify $Ma$. If there are $k<n$ queries, the rank-nullity theorem gives a nonzero vector $v$ with $Mv=0$. Then $a$ and $a+v$ give identical replies throughout this history. This also explains why adaptive choices cannot evade the bound: equal earlier replies force the same later choices.

Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.

The simplest error-correction example sends $0$ as $000$ and $1$ as $111$. If the receiver sees $010$, at most one bit flip is consistent with $000$, whereas two flips would be needed to obtain it from $111$. A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.

The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.

Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.^[ref]

Fix finitely many prescribed cyclotomic classes for pairwise differences. Such patterns are realized in every sufficiently large compatible finite field. For $r$ already chosen coordinates, let $M(a)$ count extensions with prescribed classes for $x-a_i$. Averaging over all $a\in {\mathbb{F}}_q^r$ gives $\mathbb{E}M=q/m^r+O(1)$ and, from the uniform two-class intersection estimate, $\mathrm{Var}M=O_{m,r}(q^{3/2})$. The Chebyshev inequality makes the fraction with $M<q/(2m^r)$ tend to zero. Inductively each fixed pattern on $r$ coordinates occupies a positive proportion of all tuples, so some positive proportion have many extensions. This proves the pattern-existence claim without an unproved greedy-extension assumption.

For a matrix over a field $F$, diagonalizability requires an eigenbasis with entries in $F$ and eigenvalues in $F$. Passing to a larger field can supply missing roots of the characteristic polynomial. For example,is not a diagonalizable matrix over the rational numbers, since the quadratic factor has no rational root. It is a diagonalizable matrix over the real numbers and complex numbers, since its three eigenvalues are distinct. More generally, diagonalizability is equivalent to the minimal polynomial splitting into distinct linear factors over the specified field.

For an integer matrix, reduction modulo a prime number is a different operation from extension of its coefficient field, and can merge eigenvalues. In the same example modulo $5$, ${\chi }_A(t)=(t-1)(t-3{)}^2$, while $\ker (A-3I)$ is spanned by $(1,3,4{)}^T$. Thus the geometric multiplicity of $3$ is one and its algebraic multiplicity is two, preventing diagonalizability even though all eigenvalues belong to the finite field.

The vector space of formal polynomials over a field $k$ in $n$ variables with total degree of a polynomial at most $d$ has the monomial basis $x_1^{a_1}\cdots x_n^{a_n}$ for nonnegative exponents with ${\sum }_i{a}_i\le d$. Introducing a slack exponent and using stars and bars counts $\left(\genfrac{}{}{0ex}{}{n+d}{n}\right)$ basis elements. These are formal polynomials; over a finite field, distinct formal polynomials need not define distinct polynomial functions unless suitable degree restrictions hold.

For a concrete example of cellular homology of real projective space, the real projective plane ${\mathbb{RP}}^2$ has one topological cell in each of dimensions zero, one and two. Its one-dimensional topological cell is a loop, and the face attaches around that loop twice. Choose orientations so that the cellular chain complex over the integers iswith nonzero chain groups in degrees two, one and zero. The twice-around attachment is why the first boundary operator shown is multiplication by two.^[ref]

Over the rational numbers, multiplication by two is invertible, so $H_2$ and $H_1$ vanish, while $H_0\cong \mathbb{Q}$. Over the finite field ${\mathbb{F}}_2$, two equals zero. Both boundary operators then vanish, giving one-dimensional homology groups in all three degrees. Their respective Betti numbers areNevertheless,The direct cell count is also $1-1+1=1$.

This calculation makes the strength and loss of information visible. The Euler characteristic survives a change of the field used for coefficients, while individual homology groups can change. Over the integers, the same chain complex has $H_1\cong \mathbb{Z}/2\mathbb{Z}$ and $H_2=0$: a torsion subgroup that rational Betti numbers do not record. The rank cancellation in the Euler-Poincare formula explains why the alternating total still agrees with the cell count.

A factor base is a finite set of small prime numbers over which selected auxiliary integers are completely factored. Some methods also record a sign coordinate for $-1$, which is not a prime number. A positive integer supported entirely on the chosen factor base gives an exponent vector; reducing that vector modulo two records which prime exponents are odd integers. The product is a square of a number precisely when every prime exponent is an even integer.

For the original toy $N=77$, use factor base $\{2,3,5\}$ and the two relationsThe residues have exponent vectors $(0,1,1)$ and $(2,1,1)$ in the order $(2,3,5)$. Adding the two vectors modulo two gives $(0,0,0)$, so multiplying the residues gives $15\cdot 60=900=30^2$. Consequentlyand $\gcd (X-Y,77)=7$ and $\gcd (X+Y,77)=11$. Neither individual residue was a square; combining the relations made all exponents even.

In a larger collection, choose relations $x_i^2\equiv r_i(\mathrm{mod}N)$ with positive residues $r_i={\prod }_{j=1}^B{p}_j^{e_{ji}}$. If a nonempty selection $I$ has an even sum in every exponent coordinate, setThen $X^2\equiv Y^2(\mathrm{mod}N)$. Finding such a selection is a linear dependence problem over the finite field ${\mathbb{F}}_2$: the indicator vector of the chosen relations belongs to the kernel of a linear map given by the parity matrix. This is why a problem about prime factors recruits linear algebra. The final congruence of squares may still be trivial, so another selection can be needed. ^[ref].

There is a tradeoff: a small factor base gives a smaller parity matrix, but fewer auxiliary integers factor completely over it. A larger factor base accepts more relations but makes the linear algebra larger. Negative auxiliary values need an additional sign coordinate, and a selected product needs even sign parity as well as even prime exponents. Pomerance's account explains this balance and the historical development of combining smooth relations; the toy example omits algorithm-specific sieving and running-time claims. ^[ref].

The Fano plane is the projective plane over the finite field ${\mathbb{F}}_2$. It has seven points and seven lines, each line contains three points, and two distinct lines meet in one point. A line-point incidence matrix $N$ therefore satisfies $N{N}^{\mathsf{T}}=2I+J$, making it invertible over the real numbers and useful for the transplantation theorem.

Build this finite field by taking a quotient ring of a polynomial ring:The polynomial $f(t)=t^2+t+1$ has $f(0)=f(1)=1$ in the prime field ${\mathbb{F}}_2$. A polynomial of polynomial degree two is an irreducible polynomial exactly when it has no polynomial root in the coefficient field. Thus the quotient by an irreducible polynomial is a field construction applies. Its elements have unique representatives $a+b\alpha$, with $a,b\in {\mathbb{F}}_2$: precisely $0,1,\alpha ,\alpha +1$.

The defining relation is ${\alpha }^2+\alpha +1=0$. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes ${\alpha }^2=\alpha +1$. Addition acts separately on the two coefficients:All coefficient calculations use modular arithmetic modulo two. For example, $(\alpha +1)+\alpha =1$ and $(\alpha +1)+(\alpha +1)=0$. Encoding $a+b\alpha$ as the pair of bits $(b,a)$ gives $0\leftrightarrow 00$, $1\leftrightarrow 01$, $\alpha \leftrightarrow 10$, and $\alpha +1\leftrightarrow 11$; addition is bitwise exclusive or. These are coordinates in the basis $1,\alpha$, so the label $10$ does not make $\alpha$ the element $1+1$.

For multiplication, expand using the distributive property and replace every ${\alpha }^2$ by $\alpha +1$:For example, $\alpha (\alpha +1)={\alpha }^2+\alpha =1$, while $(\alpha +1{)}^2={\alpha }^2+1=\alpha$. The following complete tables are computed from the coefficient rules. Colors identify results, rather than their numerical sizes. Every row of the addition table lists all four elements, and every nonzero row of the multiplication table does too: adding an element, or multiplying by a nonzero element, can be undone.

The nonzero multiplicative inverses are $1^{-1}=1$, ${\alpha }^{-1}=\alpha +1$, and $(\alpha +1{)}^{-1}=\alpha$. Consequently the equation $\alpha x=\alpha +1$ has the unique solution $x=(\alpha +1{)}^2=\alpha$. Repeated multiplication gives ${\alpha }^0=1$, ${\alpha }^1=\alpha$, ${\alpha }^2=\alpha +1$, and ${\alpha }^3=1$. They cycle through every element of the multiplicative group of a finite field.

Compare the ring $\mathbb{Z}/4\mathbb{Z}$, also with four elements. Its addition satisfies $1+1=2\ne 0$, and its multiplication satisfies $2^2=0$. Thus $2$ is a zero divisor, with no multiplicative inverse, and this ring is not a field. Multiplying by $2$ collapses different inputs to the same output: both $0$ and $2$ give $0$, while both $1$ and $3$ give $2$. In the field with four elements, multiplying by $\alpha$ instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

The finite field ${\mathbb{F}}_9$ can be represented as ${\mathbb{F}}_3[X]/(X^2+1)$, since the quadratic has no root modulo three. Its elements are $a+b\beta$ for $a,b\in {\mathbb{F}}_3$, with ${\beta }^2=-1$. Multiplication reduces to $(a+b\beta )(c+d\beta )=(ac-bd)+(ad+bc)\beta$ modulo three.

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

A finite field has positive characteristic, because its repeated sums of $1$ cannot all be distinct. By the characteristic of an integral domain theorem, this is a prime number $p$. Its multiples of $1$ form a copy of the prime field ${\mathbb{F}}_p$: a nonzero multiple $a1$ has inverse $b1$, where the Bezout identity $ab+cp=1$ supplies $b$.

View $F$ as a vector space over this prime field. Repeatedly extend a linearly independent set until it is maximal; the procedure terminates because $F$ is finite. Maximality makes it a basis. If the dimension is $d$, unique coordinates give exactly $p^d$ elements. Thus the cardinality is a power of a single prime, rather than an arbitrary composite integer.