Basis for the Algebraic numbers over the rationals

Question

Is there an explicit basis for the algebraic numbers as a vector space over the rationals?

Answer 1

Every computable field which is an algebraic extension of the rationals $\mathbb{Q}$ has a computable basis (as a vector space over $\mathbb{Q}$). The idea is to build up this basis by recursion: let $F_0 = \mathbb{Q}$, with basis $B_0=$ {$1$}, and, given a basis for $F_s$ over $\mathbb{Q}$, find the least element $x$ of $F$ whose minimal polynomial over $F_s$ has degree $d > 1$. This can be done because $F_s$ has a splitting algorithm, enabling one to recognize irreducible polynomials in $F_s[X]$, uniformly in $s$. Then $C_s=${$ 1, x, x^2, x^3,...x^{d-1}$} is a basis for $F_{s+1}=F_s[x]$ over $F_s$, and a basis $B_{s+1}$ for $F_{s+1}$ over $\mathbb{Q}$ is given by all products of one element of $C_s$ with one element of the basis $B_s$ for $F_s$ over $\mathbb{Q}$. Since $1$ lies in $C_s$, we have $B_s \subset B_{s+1}$, and the union (over $s$) of all these $B_s$ will be a basis $B$ for $F$ over $\mathbb{Q}$. The same construction would work with any finite field in place of $\mathbb{Q}$, and indeed over every c.e. ground field which has a splitting algorithm.

However, when $F$ is transcendental over $\mathbb{Q}$ (especially when it has infinite transcendence degree), this can no longer be done. In this case a computable vector-space basis follows if there exists a computable transcendence basis for $F$ over $\mathbb{Q}$, but not all computable field extensions of $\mathbb{Q}$ have computable transcendence bases. Metakides and Nerode produced a computable field of infinite transcendence degree over $\mathbb{Q}$ which has no computable vector-space basis over $\mathbb{Q}$. One could probably also build a computable field $\mathbb{Q}$ with computable vector-space basis over $\mathbb{Q}$, but with no computable transcendence basis over $\mathbb{Q}$.

A discussion of splitting algorithms, over $\mathbb{Q}$ and over finitely generated extensions, appears in Harold Edwards' book Galois Theory. Fried & Jarden is another good source.

Answer 2

Let me offer a formulation of your question, using ideas of computable model theory, which make it both interesting and nontrivial. Given that there is a computable presentation of the field $\mathbb{A}$ of algebraic numbers, meaning the algebraic closure of $\mathbb{Q}$, the natural questions would seem to be:

• Is there a computable presentation of $\mathbb{A}$ in which there is a computable subset forming a basis for it as a vector space over $\mathbb{Q}$?

• Does every computable presentation of $\mathbb{A}$ admit such a computable basis?

So my proposal is to interpret "explicit" as computable, inside a computable presentation of the algebraic numbers.

Note that Kevin's comment, which is closely related to Cantor's argument that the collection of algebraic numbers is countable, doesn't provide a computable basis. At each stage of his construction, he is asking a negated existential question "is this number not in the span of the earlier numbers?", which we cannot expect to answer computably in finite time. Thus, the basis that he provides has on its face complexity $\Pi^0_1$, or co-c.e., and may not be computable. This is the same complexity as the complement of the halting problem, and is less explicit than one might hope to achieve.

I don't know if there is a computable basis or not, but I suspect there isn't. In this case, perhaps Kevin's sort of solution is the most explicit possible, and it may even be true that every basis is complete for $\Pi^0_1$, and therefore Turing equivalent to the halting problem. But I offer two observations.

First, the answer cannot depend on the presentation of the field. That is, the answers to the two questions above must be the same. The reason (as Russell Miller just reminded me) is that the algebraic closure of $\mathbb{Q}$ is computably categorical, meaning that all computable presentations of it are isomorphic by a computable isomorphism. Such an isomorphism would preserve the Turing degree of any subset. So there would be a computable basis for one if and only if there is a computable basis in the other.

Second, if there is a c.e. basis, then it must be computable. The reason is that if we can enumerate the elements of a basis $B$, then we can also enumerate the complement of $B$, since a number $u$ is in the complement of $B$ if it is expressible as a rational linear combination of objects in $B$ other than $u$, and this we can find by searching if it is true.

It doesn't seem to change the problem much to consider the real algebraic numbers. Here, one has computable categoricity as an ordered real-closed field.

Meanwhile, we wait for the computable model theorists to show up with the answer...