Tobias Boege and Geva Yashfe: Recognizing Algebraic Matroids Is Undecidable

Algebraic Matroids are Undecidable Tobias Boege and Geva Yashfe have posted a remarkable paper, Recognition of algebraic matroids is undecidable. It brings together matroid theory, algebraic geometry, model theory, and undecidability. An algebraic matroid abstracts algebraic independence in a field extension . If the elements of are represented by elements of , the rank of a subset is the transcendence degree over of the field generated by its representatives. In characteristic zero, Ingleton proved in 1971 that every algebraic matroid is linear over an appropriate extension field. In positive characteristic, however, algebraic matroids include examples that are not linear over any field. In 1975, Ingleton and Main showed that non-algebraic matroids exist: their example was the Vámos matroid , which violates an extension property of algebraic matroids. The class of algebraic matroids is closed under matroid union and truncation; Lindström later constructed infinitely many excluded…