# A result of van der Waerden says Galois theory “needs” incomputable sets - what does this mean, exactly?

I happened across the recent arXiv paper Transfinite Recursion In Higher Reverse Mathematics, and the introduction begins:

The question "What role do incomputable sets play in mathematics?" has been a central theme in modern logic for almost as long as modern logic has existed. Six years before Alan Turing formalized the notion of computability, van der Waerden [vdW30] showed that the splitting set of a field is not uniformly computable from the field; put another way, van der Waerden demonstrated the necessity of certain incomputable sets for Galois theory.

The article referred to is

[vdW30] Bartel L. van der Waerden. Eine Bemerkung über die Unzerlegbarkeit von Polynomen. Math. Ann., 102(1):738–739, 1930

I'm afraid I don't know any German, nor am I familiar with even the basics of complexity theory. But I was surprised and interested by this connection to Galois theory, which is something much closer to mathematical home for me.

I would greatly appreciate an overview / explanation of van der Waerden's result - what does it mean to say that Galois theory needs "certain incomputable sets", and how is this result proven?

-

The gist of the matter is that testing if a polynomial is squarefree can be undecidable in positive characteristic, see below. This has no impact in practice because the bizarre (though computable) fields that are constructed for such counterexamples (e.g. below) do not arise naturally in algebra.

Above is excerpted from C. F. Miller, Computable Algebra.

Above is excerpted from von zur Gathen, Hensel and Newton Methods in Valuation Rings, Math. Comp., 1984

Below are the original papers.

M.O. Rabin, Computable Algebra, General Theory, and Theory of Computable Fields, Trans. A.M.S. 95 (1960), 341-360.

A. Frohlich & J.C. Shepherdson. Effective procedures in field theory, Phil. Trans. Royal Soc. London, Series A 248 (1956) 950, 407-432.

-