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 \((E,r)\) abstracts algebraic independence in a field extension \(F\subseteq K\). If the elements of \(E\) are represented by elements of \(K\), the rank \(r(A)\) of a subset \(A\subseteq E\) is the transcendence degree over \(F\) 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 \(V_8\), 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 minors.

Boege and Yashfe prove that:

  1. There is no algorithm that takes as input a finite matroid and decides whether it is algebraic in any given positive characteristic \(p\).
  2. There is no algorithm that decides whether a finite matroid is algebraic over some field, with no restriction on the characteristic.

The contrast with characteristic zero is striking: recognizing algebraic matroids in characteristic zero is decidable, because there algebraic and linear matroids coincide.

Recognizing whether a matroid has a particular sort of realization is a central question in matroid theory. One precursor is Mnëv’s universality theorem: realization spaces of oriented matroids can model arbitrary primary semialgebraic sets, and the associated realizability problem is complete for the existential theory of the reals. Another is work of Lukas Kühne and Geva Yashfe showing that multilinear representability is undecidable: there is no algorithm to determine whether a matroid can be represented by a \(c\)-arrangement of vector subspaces for some positive integer \(c\).

Here is a very rough glimpse of the new proof. Classical von Staudt constructions turn incidences of points and lines in a projective plane into equations for their coordinates. The group configuration theorem of Hrushovski and Zilber, together with work of Evans and Hrushovski, allows Boege and Yashfe to recover suitable projective planes from patterns of algebraic dependence. A central difficulty is to identify the Frobenius map \(a\mapsto a^p\) using only information recorded by a matroid. They do this by connecting the additive and multiplicative algebraic groups through the affine group. In the resulting structure, the operations commuting with Frobenius give a copy of the rational function field \(\mathbb F_p(t)\), with \(t\) distinguished. The authors then translate solvability of equations over this field into algebraic realizability of finite matroids. The necessary undecidability theorem for equations over \(\mathbb F_p(t)\) is due to Pheidas for odd \(p\) and Videla for \(p=2\).

What is the Vámos matroid?

The Vámos matroid \(V_8\) has rank four on eight elements. Here is a concrete description. Divide its elements into four pairs \(A,B,C,D\). Every set of at most three elements is independent. Among the 70 four-element sets, exactly five are dependent:

\(A\cup B,\quad A\cup C,\quad A\cup D,\quad B\cup C,\quad B\cup D.\)

The conspicuous exception is \(C\cup D\), which is independent. Every other four-element set is independent as well, and therefore a basis. The five dependent four-element sets are called circuit-hyperplanes.

Why does this example matter here? Ingleton and Main showed that this pattern cannot arise from algebraic dependence among elements of a field extension: under the stated rank conditions, dependence of the five listed unions would force \(C\cup D\) to be dependent too. Thus \(V_8\) is not algebraic over any field.

What does the word conspicuous mean?

Conspicuous means easy to notice or standing out clearly. So “a conspicuous exception” is an exception that draws attention.

Here are some beautiful figures from the paper.