<p>I used field extensions (and Tarksi's transfer principle) to prove <a href="http://cjtcs.cs.uchicago.edu/articles/1999/8/contents.html" rel="nofollow">lower bounds for linear degeneracy problems</a>.  Using a field extension of the reals with formal infinitesimals simplified the construction of adversarial inputs.  (But see also <a href="http://portal.acm.org/citation.cfm?id=1059513.1059515" rel="nofollow">Ailon and Chazelle's followup paper</a>, which generalized my result without using field extensions.)</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Real_closed_field" rel="nofollow">real closed field</a> that contains the reals.</p>

CC BY-SA 2.5
2010-11-27T20:54:55.477Z
2010-11-27T20:54:55.477Z
Jeffε
<p>In a paper with Ran Raz on <em>randomness-efficient low degree testing</em> we used sub-fields/field extensions.</p>

<p>The problem (which I once described on this website) is to find a <em>small</em> 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.</p>

<p>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$.</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-11-27T21:41:21.153Z
2010-11-27T21:41:21.153Z
Dana Moshkovitz
<p>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 <em>zero polynomial</em> 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}$.</p>

CC BY-SA 2.5
2010-11-28T04:05:54.557Z
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.
Ross Snider
CC BY-SA 2.5
2010-11-28T05:21:19.607Z
@Ross: The polynomial can be re-interpreted as defined over the larger field.
arnab
CC BY-SA 2.5
2010-11-28T02:24:01.923Z
2010-11-28T05:22:14.207Z
2010-11-28T05:22:14.207Z
arnab
<p>A <b>field</b> is a set with two binary operations called addition and multiplication satisfying various axioms. Wikipedia article: <a href="http://en.wikipedia.org/wiki/Field_%28mathematics%29">Field_(mathematics)</a></p>

<p>A field extension is when you add a new element and then have to add all <a href="http://en.wikipedia.org/wiki/Arithmetic_combinatorics">arithmetic combinations</a> of that new element with the existing elements, e.g. adding <b>i</b> 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.</p>

<p>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.</p>

<p>Wikipedia: <a href="http://en.wikipedia.org/wiki/Field_extension">Field_extension</a></p>

<p>Finite field extensions are useful in the construction of BCH codes which are codes over the finite fields of order q=p<sup>n</sup> 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).</p>

<p>Wikipedia: <a href="http://en.wikipedia.org/wiki/BCH_code">BCH_code</a></p>

<p>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.</p>

CC BY-SA 2.5
2010-11-27T17:42:33.813Z
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.
Hsien-Chih Chang 張顯之
<big-list><algebra>
Field extensions in CS
Mouswi
# Field extensions in CS

(Asked by: username_0 on 2010-11-27)

A **field** is a set with two binary operations called addition and multiplication satisfying various axioms. Wikipedia article: [Field\_(mathematics)](http://en.wikipedia.org/wiki/Field_%28mathematics%29)

A field extension is when you add a new element and then have to add all [arithmetic combinations](http://en.wikipedia.org/wiki/Arithmetic_combinatorics) 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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.

**Tags:** big-list, algebra

> **Comments:**
> **username_1**: 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.  

---

## 3 answers

### Answer by username_2 on 2010-11-27. Score: 9

I used field extensions (and Tarksi's transfer principle) to prove [lower bounds for linear degeneracy problems](http://cjtcs.cs.uchicago.edu/articles/1999/8/contents.html). 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](http://portal.acm.org/citation.cfm?id=1059513.1059515), 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](http://en.wikipedia.org/wiki/Real_closed_field) that contains the reals.


---

### Answer by username_3 on 2010-11-27. Score: 5

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.


---

### Answer by username_4 on 2010-11-28. Score: 2

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}$.

> **Comments:**
> **username_5**: 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.  
> **username_4**: @Ross: The polynomial can be re-interpreted as defined over the larger field.  

---

