# Basis for the Algebraic numbers over the rationals

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

-
I would bet against it. I once asked T. Y. Lam about preferred forms for compass and straightedge "constructible numbers," those being the smallest field extension of the rationals closed under square roots of positive elements. He was quite firm that there is no canonical form for these numbers.  Meanwhile, you are asking for far more intricate fields. Perhaps it depends on the word "explicit." –  Will Jagy Nov 30 '10 at 16:49
Sure! Just enumerate the rationals using the usual "spiral" argument, enumerate the polynomials with rational coefficients using lexicographic ordering, enumerate the complex roots of each of them using some suitable partial ordering on the complexes (e.g. $z_1<z_2$ iff $z_1$ has a smaller argument than $z_2$, or they have the same argument but $|z_1|<|z_2|$) and now you've enumerated the algebraic numbers and you can just now construct a basis by going through each one adding it in if it's not a linear combination of anything we've seen before. Completely explicit! ;-) –  Kevin Buzzard Nov 30 '10 at 18:05
Mathahada, I appreciate that you accepted my answer, but it would seem more appropriate for you to accept Russell Miller's answer, because he gave the solution to the version of your question that I proposed. (And also Jared Weinstein suggested a similar solution in comments.) –  Joel David Hamkins Dec 2 '10 at 12:58

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.

-
Hello, Russell, welcome to MO, and thanks for this explanation! –  Joel David Hamkins Dec 2 '10 at 4:13

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

-
"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." Joel, can you comment on why this is so? Let's suppose that after every iteration of Kevin's construction, you throw in enough new elements so that what you have is the basis for a field, call it K. Then you look up the next polynomial on your list; you have to decide whether each of its roots belong to K or not. But this can be accomplished using the LLL algorithm. –  Jared Weinstein Dec 1 '10 at 3:43
Jared, if I understand you, what you are talking about why $\mathbb{A}$ has a computable presentation, and that part is fine; it does have a computable presentation, in part for the reasons you mention. But next, having the computable presentation of $\mathbb{A}$, you want to build the basis, and here you include a new element in the basis exactly when it is not in the span of what came earlier. This seems to be a $\Pi^0_1$ question (a $\forall$ question in arithmetic), since you are considering all rational linear combinations of the earlier numbers on the list. –  Joel David Hamkins Dec 1 '10 at 3:54
No no, I really meant the basis part of the question! Given a finite set B of algebraic numbers (described, let's say, using their minimal polynomials, together with sufficiently many decimal digits), and another algebraic number x, I thought it could be decided in finite time whether x belongs to the span of B. Certainly it can be decided whether x belongs to the field generated by B (by factoring the minpoly of x over that field), and the rest is linear algebra. What am I missing? –  Jared Weinstein Dec 1 '10 at 4:41
I understand your proposal better now. What concerned me is that there are computable vector spaces that have no computable basis, and in such a space, the dependency problem is undecidable---one cannot in general computably determine if one vector is in the span of a finite list of other vectors, even when the ambient space is computably presented. You propose to get around that....(continued) –  Joel David Hamkins Dec 1 '10 at 14:56
I think you propose that if we have a finite linearly independent set $B_0$ of algebraic numbers and $\mathbb{Q}(B_0)=\text{Span}(B_0)$, then we consider the next algebraic number $x$. Using the LLL algorithm, we determine if $x$ is in $\mathbb{Q}(B_0)$; if it is, then discard; if not, then add $x$ to the basis by expanding $B_0$ to a linearly independent set $B_1$ with $x\in B_1$ such that $\mathbb{Q}(B_1)=\text{Span}(B_1)$. That sounds very promising, but I don't quite see all the details for the final step of constructing $B_1$. May I kindly ask that you explain it more fully in an answer? –  Joel David Hamkins Dec 1 '10 at 14:57