REVIEW 3 major objections 4 minor 40 references
Recognition of algebraic matroids is undecidable
T0 review · 3 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash
Pith's one-line read This paper proves that recognizing algebraic matroids is undecidable in every positive characteristic, reducing the problem to Diophantine equations over F_p(x).
desk verdict Real new undecidability result for algebraic matroid recognition; the core quasi-automorphism and field-configuration machinery is sound, but the final reduction in Theorem 5.4 is sketched rather than fully proven. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the group configuration theorem together with a new affine-group configuration. A group configuration is a six-tuple of points in a field extension satisfying rank and algebraic-closure axioms; the theorem extracts from any algebraic realization a definable algebraic group. The paper develops quasi-automorphisms—subgroups of G × G projecting onto each factor with finite kernel, i.e., isogenies up to finite indeterminacy—as the higher-dimensional replacement for the endomorphism skew field, and shows that a pointed configuration can be labeled by a quasi-automorphism. A rank-only configuration (Figure 7) then forces the group to be G_m ⋉ G_a, and a variant of the fi
What would settle it
Run the construction on an explicit Diophantine system over F_p(x) with no solution; any algebraic realization of the resulting matroid in characteristic p whose recovered group is not quasi-isomorphic to G_m ⋉ G_a, or whose special point is not conjugate to x in F(x;Frob), would refute the theorem.
Extended reading notes
Core claim
The paper's central claim, Theorem 1.1, is that no algorithm can decide whether a finite matroid is algebraic, even when the characteristic is fixed to any prime p, or when it is left unspecified. Since the same problem is decidable in characteristic zero, this is a positive-characteristic phenomenon. The proof reduces Diophantine solvability over the function field F_p(x) to algebraicity of finite matroids. The reduction forces algebraic realizations of a configuration to be, up to isogeny, the affine group G_m ⋉ G_a, and transfers the Frobenius element p from the multiplicative group to an additive-group endomorphism conjugate to the generator x of F(x;Frob), whose centralizer is F_p(x). U
Load-bearing premise
The reduction requires that the rank conditions in the main figure force every algebraic realization to have the intended affine-group structure and a distinguished point conjugate to x; that forcing step is not fully proven here and is delegated to earlier work and to omitted figure lines.
Editorial extensions
If this is right
- For every prime p, there is no algorithm that decides whether a finite matroid is algebraic over a field of characteristic p, so the decidability of characteristic zero is sharply contrasted.
- With the characteristic left free, the recognition problem is also undecidable, since a matroid that is algebraic only in a prescribed characteristic can be attached to any input.
- Realizability problems in algebraic geometry that reduce to algebraic matroids, such as certain tropical realization questions, inherit undecidability in positive characteristic.
- The construction gives an explicit finite translation from Diophantine systems over F_p(x) into matroid rank axioms, drawing a clear boundary between decidable and undecidable matroid realization notions.
Reading between the lines
- The matroid construction depends on the prime p and on the specific Diophantine sentence, so the undecidability is non-uniform; it does not yield a single matroid family that defeats all algorithms uniformly across characteristics.
- The same transfer mechanism through the affine group may apply to other algebraic-group configurations, suggesting that recognizing algebraic matroids over restricted base fields, or over skew-field coordinatization problems, is also undecidable.
- The new rank-only variant of the field configuration theorem, which avoids canonical-base conditions, could be reused in other problems where group configurations arise but where such conditions are unavailable.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that the recognition problem for algebraic matroids is undecidable: given a finite ground set and a rank function, there is no algorithm that decides whether the matroid is realizable as the transcendence-degree matroid of a field extension F⊂K, either when the characteristic is fixed to p>0 (Theorem 1.1(1)) or left unrestricted (Theorem 1.1(2)). The proof strategy is to reduce the existential theory of F_p(t) to algebraicity of matroids. Starting from an algebraic realization of a suitable matroid gadget, the authors use the Hrushovski–Zilber group configuration theorem to extract an algebraic group; they develop a quasi-isomorphism/quasi-epimorphism calculus (§3) that recovers a skew-field coordinatization in rank 1; in §4 they prove a new field-configuration-type theorem showing that a rank-2 configuration forces the group G_m ⋉ G_a; and in Theorem 5.4 they transfer the Frobenius element p ∈ Q = L_F(G_m) to the element x in L_F(G_a), whose centralizer is F_p(x). Pheidas–Videla undecidability for F_p(t) then gives the result. Corollary 5.5 derives the unrestricted-characteristic case by a direct-sum construction with Lindström's matroid.
Significance. If the proof can be completed, this is a major result: it separates the recognition problem for algebraic matroids in positive and unrestricted characteristic from the decidable characteristic-zero case, and it demonstrates a new interaction between algebraic matroids, group configurations, and Diophantine undecidability. The paper contains substantial original machinery: the quasi-automorphism/quasi-epimorphism calculus of §3, the affine group recovery in Theorems 4.5 and 4.15, and the transfer of the Frobenius element through quasi-automorphisms in §5. These parts are technically nontrivial and appear sound. The reliance on the external Pheidas–Videla theorem and on [EH91] for von Staudt constructions is appropriate. However, the final reduction is not yet a complete proof: Theorem 5.4 is a sketch in which the matroid construction and the encoding of equations are asserted rather than demonstrated, and this is the exact point on which the undecidability claim rests.
major comments (3)
- [Theorem 5.4 / Figure 7] The proof of Theorem 5.4 does not define the finite matroid that is supposed to encode a Diophantine system. Figure 7 is an incidence skeleton; the proof states that 'some lines are omitted' and that stubs indicate the missing lines needed for group configurations and for Theorem 3.17. A matroid cannot be specified by such stubs: one needs an explicit ground set and rank function, or at least a complete point-line incidence list, together with a proof that the rank axioms hold and that every algebraic realization satisfies the acl/circuit hypotheses of Theorems 4.5 and 4.15. This is not a presentation detail: those theorems are stated for tuples satisfying algebraic-dependence conditions, not for arbitrary rank conditions of a matroid. The missing translation is exactly the reduction.
- [Proof of Theorem 5.4] The forcing assertions are delegated rather than proved. The sentence 'We may force the red group to be Ga by requiring p=0 inside its quasi-automorphism skew field' and the analogous non-Ga forcing for the blue group are not supported by an explicit construction. The cited [EH91, KPY23] give von Staudt constructions for one-dimensional commutative group configurations; the present paper's contribution is precisely to extend the framework to quasi-automorphisms of possibly non-abelian groups (§§3–4). It must be shown that the rank conditions of the gadget, including the omitted lines, implement these equations in every realization, and that the forced labels are compatible with the quasi-automorphism labels from Theorem 3.17. Without this, the reduction to Diophantine solvability over F_p(φ) does not go through.
- [Theorem 5.4, final encoding step] The step from the element φ ∈ L_F(G_a) to an encoding of arbitrary existential sentences about F_p(φ) is asserted in one sentence. The paper does not explain how a given Diophantine equation over F_p(φ) is converted into finitely many rank conditions on the matroid, nor how the centralizer computation of Lemma 5.3 is made uniform and effective in the matroid data. Since the undecidability conclusion relies on this encoding, a complete proof must include the construction and verify that algebraicity of the resulting matroid is equivalent to solvability. The current text leaves this as a reference to [EH91, KPY23].
minor comments (4)
- [Proposition 2.16] The displayed formula 't1p' appears to be a typesetting error for t1^p. Please correct.
- [Figure 7] The element d is mentioned in Theorem 4.15 and in the proof of Theorem 5.4 but is not clearly labeled in the figure. Please mark it, and also mark the red/blue/gray points consistently with the text.
- [Lemma 5.3 / Theorem 5.4] The notation F_p(φ) is used for the centralizer of φ, but the ambient ring is not repeated at each use. Clarify that C(φ) is taken inside L_F(G_a) and that the identification with F_p(φ) is an isomorphism of fields.
- [Corollary 5.5] The direct sum M ⊕ N_p is used without stating the standard fact that direct sums of algebraic matroids are algebraic and that the Lindström matroids N_p have a uniform description. This is routine but should be stated explicitly, since it carries the unrestricted-characteristic conclusion.
Circularity Check
No circular reduction; the undecidability argument is anchored to Pheidas/Videla and EH91, with only a minor supporting self-citation.
full rationale
The central derivation is not circular. The conclusion (undecidability of algebraic matroid recognition) is reduced to the external undecidability theorem of Pheidas/Videla (Theorem 5.1) and to the external Hrushovski–Zilber/EH91 group-configuration and projective-plane machinery; it does not presuppose the target theorem. Sections 3 and 4 build the quasi-automorphism and affine-group configuration internally, and Theorem 5.4 only applies these results, transferring the Frobenius endomorphism p from Gm to Ga via Proposition 5.2 and isolating Fp(phi) via Lemma 5.3. The only self-citation is [KPY23] (co-authored by Yashfe), used for von Staudt construction details and cited together with the independent [EH91]; it is published supporting technology, not an unverified premise on which the main claim uniquely rests. The proof does leave real gaps: in the proof of Theorem 5.4, the paragraph beginning 'Some lines are omitted from this figure for clarity' and the assertions 'We may force the red group to be Ga by requiring p=0...' delegate the existence of the omitted lines and the forcing constructions to [EH91]/[KPY23] without displaying the matroid. These are omissions/incompleteness (a correctness risk), not circularity: no equation is defined in terms of the target result, no parameter is fitted and then renamed a prediction, and the self-citation does not carry the undecidability step by itself.
Assumptions & free parameters
assumptions (5)
- domain assumption Group Configuration Theorem (Theorems 2.3 and 2.6)
- domain assumption Pheidas–Videla theorem: the existential theory of F_q(t) is undecidable for each prime power q
- domain assumption Evans–Hrushovski projective plane coordinatization theorem (Theorem 2.14)
- domain assumption Existence of algebraic matroids realizable only in characteristic p (Lindström)
- standard math ACF_p is stable, eliminates imaginaries, and Morley rank coincides with Krull dimension for definable sets
Cite this review
Pith. "Pith review of Recognition of algebraic matroids is undecidable." pith.science (2026). https://pith.science/paper/CBMSV6SI
@misc{pith2026260714907,
author = {Pith},
title = {Pith review of: Recognition of algebraic matroids is undecidable},
year = {2026},
howpublished = {\url{https://pith.science/paper/CBMSV6SI}},
note = {Machine review of arXiv:2607.14907}
}
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\colon\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\colon 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.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
and Hrushovski, Ehud , title =
Evans, David M. and Hrushovski, Ehud , title =. Proc. Lond. Math. Soc. (3) , issn =. 1991 , doi =
1991
-
[2]
On the algebraic characteristic set for a class of matroids , fjournal =
Lindstr. On the algebraic characteristic set for a class of matroids , fjournal =. Proc. Am. Math. Soc. , issn =. 1985 , doi =
1985
-
[3]
A survey of local-global methods for
Anscombe, Sylvy and Karemaker, Valentijn and Kisak. A survey of local-global methods for. Women in numbers Europe IV. Research directions in number theory. Selected papers based on the presentations at the 4th workshop, WINE 4, Utrecht, the Netherlands, August 29 -- September 2, 2022 , isbn =. 2024 , publisher =
2022
-
[4]
Cartwright, Dustin and Varghese, Dony , title =. Eur. J. Comb. , issn =. 2024 , doi =
2024
-
[5]
1996 , publisher =
Pillay, Anand , title =. 1996 , publisher =
1996
-
[6]
Odoni, Robert W. K. , title =. Proc. Edinb. Math. Soc., II. Ser. , issn =. 1999 , doi =
1999
-
[7]
Bayo, Nadir , title =
-
[8]
Matroids, algebraic and non-algebraic , year =
Lindstr. Matroids, algebraic and non-algebraic , year =
Show all 40 references
-
[9]
Poonen, Bjorn , title =. J. Am. Math. Soc. , issn =. 2003 , doi =
2003
-
[10]
Kim, K. H. and Roush, F. W. , title =. Proceedings of the Asian mathematical conference 1990, Hong Kong, August 14--18, 1990 , isbn =. 1992 , publisher =
1990
-
[11]
Pheidas, Thanases , title =. Invent. Math. , volume =. 1991 , doi =
1991
-
[12]
, title =
Videla, Carlos R. , title =. Proc. Am. Math. Soc. , volume =. 1994 , doi =
1994
-
[13]
, title =
Cohn, Paul M. , title =. 2006 , publisher =
2006
-
[14]
Wang, Paul , title =. J. Symb. Log. , issn =. 2025 , doi =
2025
-
[15]
2002 , publisher =
David. 2002 , publisher =
2002
-
[16]
Lectures in model theory , editor =
Bays, Martin , title =. Lectures in model theory , editor =. 2018 , publisher =
2018
-
[17]
An introduction to stability theory , booktitle =
Palac. An introduction to stability theory , booktitle =. 2018 , publisher =
2018
-
[18]
2018 , publisher =
Lectures in model theory , editor =. 2018 , publisher =
2018
-
[19]
Contributions to stable model theory
Hrushovski, Ehud. Contributions to stable model theory. 1986
1986
-
[20]
The model theory of groups , fseries =
Bouscaren, Elisabeth , title =. The model theory of groups , fseries =. 1989 , publisher =
1989
-
[21]
, title =
Humphreys, James E. , title =. 1975 , publisher =
1975
-
[22]
, title =
Milne, James S. , title =. 2017 , publisher =
2017
-
[23]
2001 , publisher =
Poizat, Bruno , title =. 2001 , publisher =
2001
-
[24]
2009 , isbn =
Nathan Jacobson , title =. 2009 , isbn =
2009
-
[25]
Herstein , title =
Israel N. Herstein , title =
-
[26]
1988 , volume=
Algebraic groups and class fields , author=. 1988 , volume=
1988
-
[27]
2021 , publisher =
Voight, John , title =. 2021 , publisher =
2021
-
[28]
K. von. Comb. Theory , issn =. 2023 , doi =
2023
-
[29]
, title =
Wagner, Frank O. , title =. J. Symb. Log. , issn =. 1993 , doi =
1993
-
[30]
2002 , publisher =
Lang, Serge , title =. 2002 , publisher =
2002
-
[31]
, title =
Oxley, James G. , title =. 2011 , publisher =
2011
-
[32]
Rosen, Zvi and Sidman, Jessica and Theran, Louis , title =. Am. Math. Mon. , issn =. 2020 , doi =
2020
-
[33]
2010 , publisher =
Combinatorial geometries , edition =. 2010 , publisher =
2010
-
[34]
Computational synthetic geometry , fseries =
Bokowski, J. Computational synthetic geometry , fseries =. 1989 , publisher =
1989
-
[35]
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties , year =
Mn. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties , year =
-
[36]
1857 , publisher =
von Staudt, Karl Georg Christian , title =. 1857 , publisher =
-
[37]
Journal of Combinatorial Theory, Series A , volume=
Algebraic matroids and set-theoretic realizability of tropical varieties , author=. Journal of Combinatorial Theory, Series A , volume=. 2017 , publisher=
2017
-
[38]
arXiv preprint arXiv:2506.22415 , year=
Linear operators preserving volume polynomials , author=. arXiv preprint arXiv:2506.22415 , year=
-
[39]
Current developments in mathematics , volume=
Tropical geometry of matroids , author=. Current developments in mathematics , volume=
-
[40]
Advances in Mathematics , volume=
When are multidegrees positive? , author=. Advances in Mathematics , volume=. 2020 , publisher=
2020
Reviewed August 2, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.