19 hours ago
- The recognition of algebraic matroids is undecidable, as proven by Boege and Yashfe, combining matroid theory, algebraic geometry, model theory, and undecidability.
- In characteristic zero, every algebraic matroid is linear over an appropriate extension field (Ingleton, 1971), making recognition decidable, but in positive characteristic, algebraic matroids are not necessarily linear.
- No algorithm exists to decide if a finite matroid is algebraic in any given positive characteristic, nor to decide if it is algebraic over some field without characteristic restrictions.
- The proof uses classical von Staudt constructions, the Hrushovski-Zilber group configuration theorem, and identifies the Frobenius map via matroid information, ultimately translating equations over rational function fields into matroid realizability.
- Undecidability of equations over such fields is established using results by Pheidas (odd characteristics) and Videla (characteristic 2).
- The Vámos matroid serves as a non-algebraic example: rank 4 on 8 elements, with five dependent four-element sets (circuit-hyperplanes) but one conspicuous independent four-element set, violating algebraic matroid properties.