Field extensions in CS

A field is a set with two binary operations called addition and multiplication satisfying various axioms. Wikipedia article: Field_(mathematics)

A field extension is when you add a new element and then have to add all arithmetic combinations of that new element with the existing elements, e.g. adding i to the real numbers to get the complex numbers. If F is a subfield of K then K is called an extension field of F.

Technically you aren't adding new elements, but defining a new field which has a subset isomorphic to the orginal field, e.g. the complex numbers x+0i are identified with the real numbers x.

Wikipedia: Field_extension

Finite field extensions are useful in the construction of BCH codes which are codes over the finite fields of order q=pn which are extensions of the fields of order p where p is prime. These finite fields known as Galois fields GF(p) are extended to GF(q) by adding roots of polynomials that are irreducible (non-factorable) over GF(p).

Wikipedia: BCH_code

Where else in CS does the concept of extension fields arise ? A fundamental appearance in some subject would be more interesting than an occurence in some proof, but if it is used frequently in a common proof stategy then such a proof strategy would also be an interesting answer here.

• While the question is clear to the one familiar with algebra, maybe add some definitions will help. And, the question is a little broad; what kind of results count as "using the concept of field extensions"? In proofs? Please provide additional backgrounds so the one who is familiar with this topic can give you the answers in an useful way. Nov 27 '10 at 17:42

I used field extensions (and Tarksi's transfer principle) to prove lower bounds for linear degeneracy problems. Using a field extension of the reals with formal infinitesimals simplified the construction of adversarial inputs. (But see also Ailon and Chazelle's followup paper, which generalized my result without using field extensions.)

More generally, in the algebraic decision tree model (with real coefficients), the complexity of any problem with real inputs is identical to the complexity of the same problem where the inputs are drawn from any real closed field that contains the reals.

In a paper with Ran Raz on randomness-efficient low degree testing we used sub-fields/field extensions.

The problem (which I once described on this website) is to find a small collection of constant-dimensional affine subspaces of a space $F^m$ (F is a finite field, m is a natural number) such that the proximity (in Hamming distance) of any function $f:F^m\rightarrow F$ to low degree polynomial is approximately the same as the average proximity over the subspaces.

Our collection of subspaces was planes that are spanned by directions over a sub-field H of F. That is, subspaces of the form $\{x+ty+sz | t,s\in F\}$, where $x \in F^m$, $y,z\in H^m$.

For a small sub-field $|H|=|F|^{o(1)}$, this is a very small collection, its size is $|F^m|^{1+o(1)}$.

Yet, this collection has the following property we needed: Inside each subspace that is spanned by vectors over a sub-field, there are many smaller dimensional subspaces that are spanned by vectors over the sub-field. This is because of the sub-field property: the linear combinations over the sub-field of the spanning directions are over the sub-field. Note that small random collections of directions don't have this property: two vectors in the collection span a vector in the collection with very small probability.

Here's a simple example of a situation where we need the notion of a field extension. Consider the problem of polynomial identity testing in the blackbox setting. That is, given a blackbox which evaluates a polynomial $p$ over a field $\mathbb{F}$, we want to know whether $p$ is the zero polynomial or not. But note that if the degree of $p$ is not less than the characteristic of the field $\mathbb{F}$, it could be that $p$ evaluates to $0$ over the entire field without actually being the zero polynomial. For instance, $p(x) = x^2 + x$ over $\mathbb{F}_2$ is not the zero polynomial, yet $p(0) = p(1) = 0$. Thus, if we feed in elements of $\mathbb{F}$ to the blackbox, we'd never be able to distinguish $p$ from the zero polynomial. The way to get around this problem is to feed into the blackbox elements from a large enough field extension of $\mathbb{F}$.

• If we are given a blackbox that evaluates a polynomial $p$ over a field $\mathbb{F}$, how do field extensions help us? Isn't it an error to feed a blackbox elements that aren't in the field it evaluates over? Wouldn't we need a different blackbox than the one we are given, namely one that evaluated $p$ over a large enough field extension? I must have missed something crucial. Nov 28 '10 at 4:05
• @Ross: The polynomial can be re-interpreted as defined over the larger field. Nov 28 '10 at 5:21