Pith. sign in

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 →

arxiv 2607.14907 v2 pith:CBMSV6SI submitted 2026-07-16 math.CO math.LO

classification math.COmath.LO MSC 05B3503B2512L0512L12
keywords algebraicmatroidundecidabilitygroupconfigurationtheoremtranscendencedegreequasi-automorphismaffineDiophantineequationsoverfunctionfieldsvonStaudtconstruction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Combinatorial objects called matroids abstract the notion of independence; a matroid is algebraic when it records the transcendence-degree ranks of a set of field elements over a base field. This paper proves that the recognition problem for algebraic matroids is undecidable: no algorithm can take a matroid and decide whether it is algebraic, whether the characteristic of the field is fixed at any prime p or left completely unspecified. In characteristic zero the problem was already known to be decidable, so the undecidability is a purely positive-characteristic phenomenon. The proof works by reducing Diophantine equations over the rational function field F_p(x) — a problem known to be undecidable — to questions about whether certain finite matroids are algebraic, using the group configuration theorem and a new way of transferring a distinguished field element from the multiplicative to the additive group through the affine group.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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)
  1. [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.
  2. [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.
  3. [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)
  1. [Proposition 2.16] The displayed formula 't1p' appears to be a typesetting error for t1^p. Please correct.
  2. [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.
  3. [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.
  4. [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

0 steps flagged · score 2.0 of 10

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 0 free parameters · 5 assumptions · 0 invented entities

The proof relies on heavy external model theory (group configuration theorem, Evans–Hrushovski planes) and on the pheidas–Videla undecidability theorem. It introduces no fitted parameters. The new mathematical objects (quasi-automorphisms, affine group configuration) are defined and proven within the paper. No physical or ad hoc entities are postulated.

assumptions (5)
  • domain assumption Group Configuration Theorem (Theorems 2.3 and 2.6)
    Used throughout to extract a definable algebraic group from rank-theoretic configurations; a standard result in stable model theory, cited to [Bay18].
  • domain assumption Pheidas–Videla theorem: the existential theory of F_q(t) is undecidable for each prime power q
    External undecidability result used as the target of the reduction; cited as [Phe91, Vid94] and stated as Theorem 5.1.
  • domain assumption Evans–Hrushovski projective plane coordinatization theorem (Theorem 2.14)
    Basis for encoding von Staudt constructions in algebraic matroids; cited to [EH91].
  • domain assumption Existence of algebraic matroids realizable only in characteristic p (Lindström)
    Used in Corollary 5.5 to reduce unrestricted characteristic to fixed characteristic p; cited to [Lin85].
  • standard math ACF_p is stable, eliminates imaginaries, and Morley rank coincides with Krull dimension for definable sets
    Background used throughout the model-theoretic arguments, e.g., in Lemma 2.5 and the group configuration theorem.

how reviews work

0 comments
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 reproduced from arXiv: 2607.14907 by the authors.

Figure 1
Figure 1. A picture of the group configuration M(K4), realized in a projective plane over a skew field. Any algebraic realization of this matroid yields a one￾dimensional algebraic group G with an associated skew field LF (G). This skew field coordinatizes a projective plane in which the six points lie as pictured. We need a variant of this construction that works in higher dimensional groups which are not necessarily commuta… view at source ↗
Figure 2
Figure 2. A group configuration. Definition 2.2. A group configuration in K over F is a tuple (a, b, c, x, y, z) of tuples in K such that: (1) Any non-collinear triple in [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Start with a projective basis O, P, X∞, Y∞ inside a projective plane. The intersection of the lines Y∞ ∨ P and O ∨ X∞ defines a point X1 which determines a scale on the X-axis; the point Y1 is constructed similarly. Finally, Q is the intersection of X1 ∨ Y1 and the line at infinity X∞ ∨ Y∞. Forgetting the point P yields a group configuration. 2.4. Evans–Hrushovski planes. To an extension K/F of algebraically closed … view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Two superimposed group configurations (X, Y , Q, O, X∞, Y∞) and (X1, Y1, Q, O, X∞, Y∞). We review the groups that can appear and their endomorphism rings, following [EH91, Section 3] and its references. A one-dimensional connected algebraic group definable over an alge…
Figure 5
Figure 5. Figure 5: Three superimposed group configurations. The dashed lines indicate interalgebraicities. All three configurations share (up to interalgebraicity) the ver￾tices of the triangle. In addition any two configurations share another point which establishes a quasi-isomorphism …
Figure 6
Figure 6. Figure 6: The same configuration as in [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]
Figure 7
Figure 7. Figure 7: The configuration featuring in the theorems of Section 4.2 and in Theorem 5.4. The points in red are part of a Ga plane; the points in blue are part of an H-plane, for H an algebraic group which is not of exponent p (hence not Ga). The gray circle containing x ′ is a r…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 1 linked inside Pith

  1. [1]

    and Hrushovski, Ehud , title =

    Evans, David M. and Hrushovski, Ehud , title =. Proc. Lond. Math. Soc. (3) , issn =. 1991 , doi =

  2. [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 =

  3. [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 =

  4. [4]

    Cartwright, Dustin and Varghese, Dony , title =. Eur. J. Comb. , issn =. 2024 , doi =

  5. [5]

    1996 , publisher =

    Pillay, Anand , title =. 1996 , publisher =

  6. [6]

    Odoni, Robert W. K. , title =. Proc. Edinb. Math. Soc., II. Ser. , issn =. 1999 , doi =

  7. [7]

    Bayo, Nadir , title =

  8. [8]

    Matroids, algebraic and non-algebraic , year =

    Lindstr. Matroids, algebraic and non-algebraic , year =

Show all 40 references
  1. [9]

    Poonen, Bjorn , title =. J. Am. Math. Soc. , issn =. 2003 , doi =

  2. [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 =

  3. [11]

    Pheidas, Thanases , title =. Invent. Math. , volume =. 1991 , doi =

  4. [12]

    , title =

    Videla, Carlos R. , title =. Proc. Am. Math. Soc. , volume =. 1994 , doi =

  5. [13]

    , title =

    Cohn, Paul M. , title =. 2006 , publisher =

  6. [14]

    Wang, Paul , title =. J. Symb. Log. , issn =. 2025 , doi =

  7. [15]

    2002 , publisher =

    David. 2002 , publisher =

  8. [16]

    Lectures in model theory , editor =

    Bays, Martin , title =. Lectures in model theory , editor =. 2018 , publisher =

  9. [17]

    An introduction to stability theory , booktitle =

    Palac. An introduction to stability theory , booktitle =. 2018 , publisher =

  10. [18]

    2018 , publisher =

    Lectures in model theory , editor =. 2018 , publisher =

  11. [19]

    Contributions to stable model theory

    Hrushovski, Ehud. Contributions to stable model theory. 1986

  12. [20]

    The model theory of groups , fseries =

    Bouscaren, Elisabeth , title =. The model theory of groups , fseries =. 1989 , publisher =

  13. [21]

    , title =

    Humphreys, James E. , title =. 1975 , publisher =

  14. [22]

    , title =

    Milne, James S. , title =. 2017 , publisher =

  15. [23]

    2001 , publisher =

    Poizat, Bruno , title =. 2001 , publisher =

  16. [24]

    2009 , isbn =

    Nathan Jacobson , title =. 2009 , isbn =

  17. [25]

    Herstein , title =

    Israel N. Herstein , title =

  18. [26]

    1988 , volume=

    Algebraic groups and class fields , author=. 1988 , volume=

  19. [27]

    2021 , publisher =

    Voight, John , title =. 2021 , publisher =

  20. [28]

    K. von. Comb. Theory , issn =. 2023 , doi =

  21. [29]

    , title =

    Wagner, Frank O. , title =. J. Symb. Log. , issn =. 1993 , doi =

  22. [30]

    2002 , publisher =

    Lang, Serge , title =. 2002 , publisher =

  23. [31]

    , title =

    Oxley, James G. , title =. 2011 , publisher =

  24. [32]

    Rosen, Zvi and Sidman, Jessica and Theran, Louis , title =. Am. Math. Mon. , issn =. 2020 , doi =

  25. [33]

    2010 , publisher =

    Combinatorial geometries , edition =. 2010 , publisher =

  26. [34]

    Computational synthetic geometry , fseries =

    Bokowski, J. Computational synthetic geometry , fseries =. 1989 , publisher =

  27. [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 =

  28. [36]

    1857 , publisher =

    von Staudt, Karl Georg Christian , title =. 1857 , publisher =

  29. [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=

  30. [38]

    arXiv preprint arXiv:2506.22415 , year=

    Linear operators preserving volume polynomials , author=. arXiv preprint arXiv:2506.22415 , year=

  31. [39]

    Current developments in mathematics , volume=

    Tropical geometry of matroids , author=. Current developments in mathematics , volume=

  32. [40]

    Advances in Mathematics , volume=

    When are multidegrees positive? , author=. Advances in Mathematics , volume=. 2020 , publisher=

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.