Recogntion of Algebraic Matroids is Undecidable

Tobias Boege and Geva Yashfe prove that no algorithm can decide whether a given finite matroid is algebraic in any fixed positive characteristic p, and no algorithm can decide algebraicity over some field without restricting characteristic. An algebraic matroid encodes transcendence-degree relations among field elements; in characteristic zero algebraic matroids coincide with linear matroids (Ingleton), making recognition decidable, but positive characteristic admits genuinely non-linear algebraic behavior and known non-algebraic examples (notably the Vámos matroid) and infinitely many excluded minors. This result sits alongside previous undecidability and universality phenomena in realizability problems for matroids and related combinatorial geometries.

The proof builds a bridge from combinatorial dependence patterns to arithmetic undecidability. Classical von Staudt incidence constructions and the Hrushovski-Zilber group-configuration machinery (with Evans-Hrushovski input) recover projective-plane-like structures from matroidal dependence. The key technical achievement is detecting the Frobenius map a ↦ a^p using only matroid data by linking additive and multiplicative algebraic groups through the affine group; endomorphisms commuting with Frobenius yield a copy of the rational function field F_p(t) with a distinguished t. Solvability of equations over F_p(t) is encoded as algebraic realizability of finite matroids, and known undecidability for equations over F_p(t) (Pheidas for odd p, Videla for p=2) transfers to the matroid-recognition problem.