Recognition of algebraic matroids is undecidable

Abstract

We prove that the recognition problem for algebraic matroids is undecidable. Explicitly, this means that there is no algorithm that takes as input a finite set $S$ and a function $r:\mathcal{P}(S)\to {\mathbb{Z}}_{\ge 0}$ (where $\mathcal{P}(S)$ is the power set) and decides whether there exists a pair of fields $F\subset K$, and a function $f:S\to K$, such that for all $A\subseteq S$: ${\mathrm{trdeg}}_{F}f(A)=r(A)$. This problem is known to be decidable if the characteristic of the fields involved is constrained to be zero. We prove that it is undecidable if the characteristic is either left unspecified (in which case a realization over any characteristic is accepted) or fixed to be a prime $p$. The proof relies on Hrushovski--Zilber's Group Configuration Theorem and on the work of Evans and Hrushovski on "Projective Planes in Algebraically Closed Fields". We relate two different such projective planes, and eventually construct a reduction from the solvability of Diophantine equations over ${\mathbb{F}}_p(x)$ ($p$ prime) to algebraicity of matroids. Solvability of Diophantine equations over ${\mathbb{F}}_p(x)$ was proved to be undecidable by Pheidas for all $p>2$, and later by Videla for $p=2$. A central part of our proof is a variant of the so-called Field Configuration Theorem.

29 pages, 7 figures. Comments are welcome! This version corrects the arxiv abstract and some latex issues, as well as a few typos

Topics & keywords