This question stems from the paper "Computably categorical fields via Fermat's Last Theorem," by Russell Miller and Hans Schoutens (available online at <http://qcpages.qc.cuny.edu/~rmiller/Fermat.pdf>). In this paper, they construct a field $F$ by starting with the field $\mathbb{Q}(x\_0, x\_1, x\_2, . . .)$ of infinite transcendence degree over $\mathbb{Q}$, and then adjoining elements $y\_i$ such that $(x\_i, y\_i)$ is a solution to the polynomial $X\_i^{p\_i}+Y\_i^{p\_i}=1$ for some odd prime $p\_i$ (see paragraph 2, page 3); they then show that the resulting field has interesting computability-theoretic properties. In particular, they show that this field is computably categorical (i.e., any two computable presentations are computably isomorphic). I have only started reading this paper, but I have two questions, a simple one and a probably not-so-simple one:


Question 1: It is unclear to me exactly how much of Fermat's Last Theorem (FLT) is required for this paper, but certainly we need at least the existence of infinitely many primes $p$ such that $X^p+Y^p=1$ has no nontrivial rational solutions. How difficult is this fact to prove? (And, historically, when was it first known?)


Question 2: How much of FLT is actually required for the paper? I would be very interested if full FLT was required; although, as the authors point out, there has been at least one previous attempt made to prove the same result that apparently did not rely on FLT.


Thank you very much in advance,


Noah S



Fermat's Last Theorem and Computability Theory
Actually, I am harder-pressed to say anything the supposedly simpler question. For Question 1, I would just add that we need the existence of an infinite *computably enumerable* set of primes satisfying FLT, and that this ought to suffice. (Since the set P of primes NOT satisfying FLT is obviously $\exists$-definable and hence c.e., another way to say this is that we need to show that P is not a simple set.) I would not have guessed that any odd prime was known to satisfy FLT, up until Wiles's proof, but I'm ready to be corrected on that.


For Question 2, I do think that one could come up with a proof avoiding FLT entirely. I can't do so myself; I'm in computability, and when I was thinking about computable categoricity for fields of infinite transcendence, I realized that we needed multivariable polynomials with known finite numbers of rational solutions, and I thought of the Fermat polynomials because I didn't know any other candidates. (Of course, this condition was not all that was needed, but clearly it's necessary.) I'm still a computability theorist, and I still don't know any other candidates, but field theorists have told me that they could come up with other such polynomials fairly readily. Whether those would satisfy the more difficult requirements (basically Theorem 3.1 in the paper) is not so clear, but I suspect that it can be done with other polynomials. Bjorn Poonen suggested at one point that the Fermat polynomials were actually a bad choice, because their symmetry creates an extra solution whenever one adds a single transcendental solution to the field.


As a related question: is there a computably stable field of infinite transcendence degree? A computable structure $\mathcal{A}$ is *computably stable* if, for every computable structure $\mathcal{B}$, every isomorphism from $\mathcal{A}$ onto $\mathcal{B}$ is computable. (Example: $\mathbb{Z}$ under the successor function.) A common way to build computably stable structures is to make them computably categorical and rigid, i.e. with no nontrivial automorphisms, so that the isomorphism from $\mathcal{A}$ onto any computable copy must be unique (by rigidity), hence computable (by categoricity). I would conjecture that it is possible to mimic the construction in the Fermat paper, with different polynomials, and to get a computably stable field of infinite transcendence degree, but I certainly don't know offhand what polynomials one might use.


