Explicit automorphisms of the field of algebraic numbers

The field $\overline {\bf {Q}} $ of algebraic numbers admits many automorphisms other than conjugation. This follows from Galois theory: the field $\overline {\bf {Q}}$ can be realized as the union of a chain $ {\bf{Q}} \subseteq F_1 \subseteq F_2 \subseteq ... $ where each $F_{n+1}$ is a finite Galois extension of $\bf{Q}$. If $\phi_n$ is a nontrivial automorphism of $F_n$ such that $\phi_{n+1}$ extends $\phi_n$, then the union $\phi = \bigcup \phi_n$ is the desired mapping.

Similarly, it is possible to construct a maximal ideal $I$ in the ring $\overline {\bf {Z}}$ of algebraic integers. Enumerate the algebraic integers as $a_1, a_2, ...$ and in stange $n$, put $a_n$ into the ideal constructed so far, unless this turns it into an ideal which is not proper. This is adressed in this answer:

Prime ideals in the ring of algebraic integers

This, of course, is not new. In abstract algebra we write "let $\mathfrak {m}$ be a maximal ideal..." with no second thoughts. Indeed, there is no hope for an explicit description of a nontrivial automorphism of $\bf {C}$ or a basis for $\bf{R}$ as a vector space over the rationals. However, in this case we are dealing with rather concrete objects. Both the algebraic numbers and the rational numbers can be computably enumerated in such a way that a maximal ideal, or a nontrivial automorphism other than conjugation, can be defined by a first order formula in the language of arithmetic. They do not require choice, but in some sense remain elusive.

My questions are:

1. Under a suitable recursive enumeration of the algebraic numbers, can there be a nontrivial automorphism other than conjugation which is recursively enumerable or even computable (in the sense that its graph has these properties?)

2. Is there any reason why such an automorphism cannot have an "explicit" description - whatever that is supposed to mean? This could possibly be related to the fact that the construction of the algebraic closure is not canonical.

Solution 1:

The answer to these questions is yes, in a rather strong sense. There do exist recursive enumerations of the algebraic numbers and algebraic integers, they are unique up to a recursive isomorphism (so, the answer to the questions asked here do not depend on the presentation chosen). Then, the maximal ideal described in the question is recursive, and similarly one can construct recursive automorphisms extending any homormorphism of a finite algebraic extension of $\mathbb{Q}$ into its algebraic closure. E.g., the isomorphism of $\mathbb{Q}(\sqrt2)$ taking $\sqrt2$ to $-\sqrt2$ extends to a recursive isomorphism of the algebraic closure of $\mathbb{Q}$ which is necessarily neither the identity nor complex conjugation.

First, a bit of notation (which I have just learned myself). A recursively presentated field is a recursive set together field operations $+$, $\cdot$ which are defined by recursive functions. Clearly $\mathbb{Q}$ is recursively presentable. Rabin¹ showed in 1960 that every recursively presented field has a recursively presented algebraic closure. Metakides & Nerode² showed that uniqueness of the algebraic closure (up to recursive isomorphisms) is equivalent to the existence of a splitting algorithm (i.e., to decide if a polynomial is reducible or not) over the original field.

The following statements hold, and answer the questions asked here.

• The field of algebraic numbers has a recursive presentation, which is unique up to recursive isomorphisms. So, in the remaining statements, we can just use $\mathbb{A}$ to represent the field of algebraic numbers assuming any recursive presentation.
• Given any finite extension $\mathbb{Q}\subseteq F\subset\mathbb{A}$ of the rationals and field homomorphism $f\colon F\to\mathbb{A}$, there exists a recursive isomorphism $g\colon\mathbb{A}\to\mathbb{A}$ with $g\vert_F=f$. This can be constructed as follows; choosing a recursive enumeration $a_1,a_2,\ldots$ of $\mathbb{A}$, inductively define $g(a_i)$ to be $a_j$ for the minimal $j$ for which there is a homomorphism $F(a_1,\cdots,a_i)\to\mathbb{A}$ taking $a_i$ to $a_j$ and agreeing with the previously chosen values of $g$ on $F(a_1,\ldots,a_{i-1})$.
• The ring of algebraic integers is a recursive subset of $\mathbb{A}$.
• Every finitely generated ideal of the algebraic integers is recursive.
• Every finitely generated proper ideal $I$ of the algebraic integers is contained in a recursive maximal ideal $\mathfrak{m}$. This can be constructed as described in the question. Let $a_1,a_2,\ldots$ be a recursive enumeration of the algebraic integers. Set $I_0=I$ and, for each $n\ge1$, set $I_n=I_{n-1}+(a_n)$ if this is proper, otherwise $I_n=I_{n-1}$. Then, $\mathfrak{m}=\bigcup_n I_n$ is a recursive maximal ideal containing $I$.

I'll explain how these can be shown to hold.

1) The field of algebraic numbers has a recursive presentation.

This is not difficult, and there are various ways in which $\mathbb{A}$ can be recursively presented. I'll refer to Rabin¹ which shows the more general (and more interesting) result that every recursively presented field $K$ has a recursively presented algebraic closure. The idea is to represent the algebraic closure as $R/\mathfrak{m}$ where $R=K[x_1,x_2,\ldots]$ is a polynomial ring in infinitely many indeterminates and $\mathfrak{m}$ is a recursive maximal ideal of $R$.

2) $\mathbb{Q}$ has a splitting algorithm.

That is, there is a computable procedure to tell whether a polynomial $f\in\mathbb{Q}[X]$ is reducible or not. This is described on the wikipedia page on polynomial factorization. Multiplying $f$ by an integer if necessary, we can suppose that it has integer coefficients. Then, if it factors as $f=gh$, Gauss's lemma tells us that we can take $g,h$ to have integer coefficients. Calculating $f$ at $n={\rm deg}f$ integer values $\{a_i\}$ then, if $f(a_i)=0$ we have a factor $X-a_i$, otherwise $f(a_i)$ only has finitely many factors. This gives only finitely many choices for $g(a_i),h(a_i)$ each of which can be interpolated in a unique way by polynomials of degree $\le n$. Each of these can be checked (Lagrange interpolation) to give an exhaustive search of all possible factors of $f$ in $\mathbb{Q}[X]$.

3) If $K$ is a recursively presented field of characteristic $0$ with a splitting algorithm, and $K\hookrightarrow L=K(a_1,\ldots,a_n)$ is a finite (algebraic) field extension, then we can obtain a splitting algorithm for $L$.

I'll just reference Trager's method, as described on the Wikipedia page on polynomial factorization. It relies on the extension being separable, so that the primitive element theorem can be applied (and is guaranteed for characteristic $0$ fields).

4) Let $\mathbb{Q}\hookrightarrow L$ and $\mathbb{Q}\hookrightarrow M$ be recursively presented algebraic closures. If $\mathbb{Q}\subseteq F\subset L$ is a finitely generated subextension, and $f\colon F\to M$ is a field homomorphism, then there exists a recursive isomorphism $g\colon L\to M$ with $g\vert_F=f$.

As $M$ is recursively presented it, in particular, has an effective ordering (although not compatible with the field structure).

Let $F=\mathbb{Q}(c_1,\ldots,c_n)$ and $\{a_1,a_2,\ldots\}$ be a recursive enumeration of $L$. Define $f(a_i)$ by induction on $i$ as follows. Find a polynomial in $\mathbb{Q}[X]$ satisfied by $a_i$ (just recurse through and test each element in $\mathbb{Q}[X]$ until one is found, if necessary). By the splitting algorithm given by (3) above applied to $F_i\equiv\mathbb{Q}(c_1,\ldots,c_n,a_0,\ldots,a_{i-1})$, we can factor to obtain the minimal polynomial of $a_i$ in $F_i[X]$. Applying $f\vert_{F_i}$ to the coefficients of this polynomial gives an element of $M[X]$, and we can let $f(a_i)$ be one of its roots (say, the minimal root in $M$ under the given order). This can be found by recursing through $M$ in order and testing each element in turn until a root is found. The resulting $f$ can be seen to be effective, is an isomorphism, and $f\vert_F=g$.

Note, (4) shows that the algebraic numbers are unique up to effective isomorphisms and also generates many effective isomorphisms of $\mathbb{A}$. That's enough to fully answer the question in the title, although the answers in the body of the question are a bit different. They are still yes, using similar ideas. I can come back and add this, but that's enough for now...

¹Computable algebra, general theory and theory of computable fields, Michael O. Rabin, Trans. Amer. Math. Soc. 95 (1960), 341-360. (link)

²Effective content of field theory, G. Metakides & A. Nerode, Ann. Math. Logic, 17 (1979) 289-320. (link)