Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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.

enter image description here

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

enter image description here

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.