Pith. sign in

REVIEW 4 major objections 5 minor 18 references

On the recognition problem for limits of entropy functions

T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that no algorithm can decide whether a given integer vector is a pointwise limit of joint entropy functions: membership in the closure of the entropic cone is undecidable.

desk verdict Yashfe closes the last open case in entropy-cone undecidability with a sound-looking Desargues-type theorem, but the proof leans on two external results a referee must verify. read the letter →

arxiv 2509.06302 v1 pith:AW7CDFQV submitted 2025-09-08 math.CO cs.ITmath.IT

Geva Yashfe This is my paper · ORCID
classification math.COcs.ITmath.IT MSC 05B3503D3594A17
keywords undecidabilityentropicconeentropyfunctionsalmostpolymatroidsmatroidrecognitionDesarguestheorempartialDowlinggeometrieswordproblem
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

The paper proves that the recognition problem for the closed entropic cone is undecidable: there is no algorithm that, given a number n and an integer table of proposed entropies, decides whether that table is a pointwise limit of the joint entropy functions of n random variables on a finite probability space. In other words, no computer can certify that a proposed vector can be approximated arbitrarily well by genuine entropy vectors. The proof establishes the same undecidability for the more restricted question of whether a finite matroid is almost entropic, i.e. is itself a limit of entropy functions. The mechanism is group-theoretic: certain matroids built from a group presentation encode the presentation's relations in their rank function, and the paper shows that an encoded generator is nontrivial in the group exactly when one of the constructed matroids is almost entropic. Since deciding nontriviality of a generator is undecidable, so is the matroid question, which closes the last open case in a sequence of undecidability results for entropy-like cones and, via a known reduction, makes approximate conditional independence implication undecidable as well.

What carries the argument

Partial Dowling geometries (PDGs): matroids built from a group presentation whose rank function records the relations — a generator triple is a relator exactly when its three points lie on a rank-2 line. The load-bearing mechanism is a Desargues'-type theorem for almost entropic polymatroids (Theorem 18): it guarantees that the intersection points demanded by a projective configuration exist in some almost entropic extension. The theorem rests on two imported tools: the three-line intersection theorem (Theorem 15) and the copy lemma (Lemma 16). From these configurations a geometric product of generators is defined, unique up to parallelism and associative (Theorems 32, 36), recovering a grou

What would settle it

The most direct check is on Theorem 15: take the six-point rank-4 configuration (three pairs of points, each pair spanning a 'line', with the three lines pairwise coplanar), realize it by actual random variables on a finite probability space, and verify that a seventh point lying on all three lines can always be adjoined in an almost entropic extension. A single almost entropic embedding of the six-point matroid with no such extension would refute the base theorem and collapse the argument. On the group side, the equivalent test: for a presentation in which a generator x is explicitly trivial,

Watch

Extended reading notes

Core claim

Membership in the closed entropic cone is undecidable: no procedure decides whether an integer vector is a limit of entropy functions; equivalently, whether a finite matroid is almost entropic. The proof reduces the group word problem to matroids: Dowling-type geometries built from a presentation yield a computable family F of rank-3 matroids in which x is nontrivial iff some member is almost entropic. One direction was known for almost multilinear matroids; the converse uses a Desargues'-type theorem for almost entropic polymatroids to define a geometric product on generators, prove it associative, and recover a quotient of the presented group from a rank-4 geometry.

Load-bearing premise

Everything rests on the three-line intersection theorem for almost entropic polymatroids (Theorem 15, Section 3), which the paper states without a full proof and attributes to earlier work: if that theorem does not actually hold for every polymatroid that is a limit of entropy functions, the new Desargues theorem, the group recovery, and the undecidability result all collapse; the copy lemma (Lemma 16, Section 3.1) is a second unproved input.

Editorial extensions

If this is right

  • No algorithm decides membership in the closed entropic cone: given n and an integer vector in Z^{2^n}, the question 'is this vector a limit of joint entropy functions?' is undecidable (Theorem 1).
  • No algorithm decides whether a finite matroid is almost entropic; this is the statement the proof actually establishes, and it is equivalent to Theorem 1.
  • It is undecidable whether a given integer-valued set function h on P({1,...,n}) is epsilon-approximable by joint entropies of n random variables for every epsilon > 0 — that is, whether h is a pointwise limit of entropy functions.
  • Approximate conditional independence implication is undecidable: via a reduction the paper cites from earlier work, Theorem 1 makes the approximate version of the conditional-independence implication problem unsolvable.
  • Any class of representations that admits both a copy lemma and a three-line intersection theorem inherits the undecidability, since these are the only properties of the almost entropic setting the proof uses.

Reading between the lines

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

  • A consequence the paper leaves implicit: the undecidable instances are matroids of bounded rank (3 and 4) on growing ground sets, so the hardness is carried by the incidence structure rather than by high rank; restricting attention to small-rank entropy regions would not bypass the problem.
  • Connection to a neighbouring problem: the paper notes that algebraic matroids form a proper subclass of almost entropic ones in which even the simpler two-line intersection theorem fails; whether the three-line/Desargues incidence still holds inside algebraic matroids is a natural open probe, and if it does, algebraic-matroid recognition would inherit undecidability.
  • The construction never bounds the size of the almost entropic extension that manufactures each geometric product, and the recovered group is typically infinite; read quantitatively, the minimal size of an approximating entropic structure would give each group presentation a concrete hardness measure — a direction the paper leaves untouched.
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

4 major / 5 minor

Summary. The paper proves that the membership problem for the closure of the entropic cone is undecidable: there is no algorithm that, given n and an integer vector v in Z^{2^n}, decides whether v lies in \overline{\Gamma_n^*}. The strategy is to show that no algorithm can decide whether a finite matroid is almost entropic. The new technical engine is a Desargues-type theorem for almost entropic polymatroids (Theorem 18), built on a three-line intersection theorem (Theorem 15) and the copy lemma (Lemma 16). These tools are used to recover the underlying group from an almost entropic rank-4 partial Dowling geometry (Theorems 34 and 36) and to lift almost entropic rank-3 PDGs to rank 4 (Theorem 37). Combining these with the almost multilinear undecidability results of Kühne and Yashfe [KY22b] yields the main theorem.

Significance. The main result is significant: it settles the last open recognition problem for entropic limit cones and strengthens the undecidability program initiated in [KY22b]. The paper gives a genuinely new synthetic-geometric tool, a Desargues theorem valid in the almost entropic setting, and the reduction from group triviality to almost entropic representability is coherent. The author is explicit that the missing step in [KY22b] was precisely the almost entropic case (Remark 41), and the new Desargues machinery is a credible replacement for the approximate-linear-representation arguments used there. The paper does not provide machine-checked proofs or reproducible code; its strengths are conceptual and structural.

major comments (4)
  1. [§3, Theorem 15] Theorem 15 is the foundation of the new Desargues theorem (Theorem 18) and hence of the group-recovery and lifting arguments. It is stated without proof and attributed to [MMRV02, Lemma 5] and [BFP23, Prop. 3.16]. Since the paper uses the result for arbitrary almost entropic polymatroids, not only for positive multiples of entropic ones, the cited sources must be shown to cover exactly this statement. Please include a full proof, or a precise statement of the cited proposition together with a verification that it implies Theorem 15 as formulated here. This is load-bearing: if the cited proposition does not apply, the undecidability proof collapses.
  2. [§3.1, Lemma 16] The copy lemma for almost entropic polymatroids is stated but not proved. The references [DFZ06, Mat07a, DFZ11] are for the classical copy lemma, but the present lemma is used for almost entropic finite-type polymatroids, including an independence-over-base condition (property (3)) that is essential in the lifting theorem (Theorem 37). Please provide a proof or a precise citation to a result that establishes this exact almost entropic form. As with Theorem 15, this is a load-bearing point.
  3. [§7, proof of Theorem 1] The sentence 'Now by theorem 36 we have an extension...' is incorrect as written: Theorem 36 assumes a PDG that is already closed under geometric products and does not construct an extension. The extension is presumably supplied by Theorem 34. This is likely a typo, but since the main proof depends on passing from a finite rank-4 PDG to a product-closed extension, the reference should be corrected and the use of Theorem 34 made explicit.
  4. [§3.2, proof of Theorem 18] The proof says 'Since the entire polymatroid has rank 4, this determines it completely...' The ground set E in Theorem 18 is not assumed to have rank 4; only the configuration C has rank 4. The intended meaning is that the six-element subconfiguration {a1,a2,b1,b2,x1,x2} has rank 4, as follows from earlier displayed equalities (e.g. f(a1,a2,b1,x1)=4). Please rephrase to avoid ambiguity, because the argument for identifying the rank function of the six-point matroid depends on this point.
minor comments (5)
  1. [§5.1, Theorem 34] The statement of Theorem 34 contains the sentence 'The details are routine but slightly longer, and the claim is not used in this paper, so it is omitted.' This is confusing because the proof given already constructs a countable extension by a union of a chain. If the countable case is not needed, the sentence should be removed or reformulated; if it is needed, the proof should be indicated.
  2. [§3, opening] The phrase 'Desargues’-type theorem' in the abstract and introduction mixes apostrophe styles; use a consistent possessive form, e.g. 'Desargues-type' or 'Desargues’s-type'.
  3. [§2.1, Remark 5] The informal remark 'I was unable to find the finite type hypothesis here elsewhere in the literature' is not appropriate in a formal paper unless the author has made a genuine literature search; consider moving this to a footnote and citing the closest standard notion (finitary matroids of finite rank).
  4. [§6, Theorem 37] The verification of condition (6) for the four remaining index triples is summarized by the four diagrams and a short paragraph. The diagrams are helpful, but the dependencies for the assumption checks are delicate; adding a table listing, for each of the four triples, the previously established relator used would make the proof easier to verify.
  5. [§5.2, Theorem 36] The proof of associativity chooses an element p with [p^{-1}]=[s]·[z]; this is justified by closure under geometric products, but the notation [s]·[z] is defined only after Theorem 32. The order of the argument is clear, but a one-sentence reminder of the two-step definition of the product on parallelism classes would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new Desargues-type argument proves the previously missing direction, and the cited lemmas are external or parameter-free previous results, not re-statements of the target.

full rationale

The paper's central reduction (Theorem 1) splits into two directions. The direction 'nontrivial group element ⇒ some constructed PDG is almost entropic' is imported from the authors' earlier [KY22b, Thm. 9.16]; this is a self-citation, but it is parameter-free, concerns almost multilinear matroids, and does not assume the target theorem. The converse direction, the one that was missing for almost entropic matroids, is proved in this paper by Theorems 36 and 37 via the new Desargues theorem (Theorem 18). Remark 41 explicitly acknowledges that earlier work lacked the machinery for this direction, so the new argument is not a disguised re-importation of the self-cited result. The principal unproved inputs, the three-line intersection theorem (Theorem 15) and the copy lemma (Lemma 16), are cited to external sources ([MMRV02], [BFP23], [DFZ06], [Mat07a], [DFZ11]) and are finite extension/representation lemmas; they are not equivalent to, nor defined in terms of, membership in Γ*_n. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors to force a choice, and no known empirical pattern is merely renamed. Consequently the derivation chain is self-contained in the sense relevant to circularity, even though it depends on unproved external lemmas whose correctness is a separate risk.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

Pure mathematics, so no fitted free parameters. The load-bearing inputs are unproved-within-the-paper incidence facts (three-line intersection, copy lemma), the inherited reduction machinery of the self-cited unpublished [KY22b], and the classical word-problem undecidability. No new entities (particles, forces, dimensions) are postulated.

assumptions (5)
  • domain assumption Three-line intersection theorem for almost entropic polymatroids (Theorem 15)
    Foundation of the new Desargues theorem (Thm 18); stated without proof in this paper and cited to [MMRV02, Lemma 5] and [BFP23, Prop. 3.16].
  • domain assumption Copy lemma for almost entropic polymatroids (Lemma 16)
    Stated without proof; the cited works [DFZ06, Mat07a, DFZ11] treat the entropic case, and the passage to almost entropic limits is not shown. Used to lift rank-3 configurations into rank 4 in Theorem 37.
  • domain assumption Reduction framework of [KY22b]: computable family F of PDGs from group presentations, and direction (a) that s nontrivial implies some member of F is almost multilinear ([KY22b, Thm 9.16])
    The undecidability reduction in Theorem 1 is inherited from the unpublished, self-cited preprint [KY22b] by the author and L. Kühne; the present paper only replaces direction (b) with an almost entropic version.
  • standard math Undecidability of the word problem for the class of finitely presented groups used in the reduction
    Classical (Boone, Novikov); the reduction needs a finitely presented (torsion-free, sofic) group with undecidable word problem, whose existence is standard.
  • standard math Linear polymatroids are almost entropic ([DFZ09])
    Used in Lemma 40 to conclude every almost multilinear matroid is almost entropic, providing direction (a) of the reduction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the recognition problem for limits of entropy functions." pith.science (2026). https://pith.science/paper/AW7CDFQV

@misc{pith2026250906302,
  author       = {Pith},
  title        = {Pith review of: On the recognition problem for limits of entropy functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AW7CDFQV}},
  note         = {Machine review of arXiv:2509.06302}
}
abstract

We prove that there is no algorithm to decide whether a given integer vector is in the closure of the entropic cone $\overline{\Gamma_{n}^{*}}$. Equivalently, there is no decision procedure to determine whether a given integer-valued function $h:\mathcal{P}(\{1,\ldots,n\})\rightarrow\mathbb{Z}_{\ge 0}$ is a pointwise limit of joint entropy functions. In other words, given such an $h$, it is undecidable whether for all $\varepsilon > 0$ there exists a finite probability space $(\Omega,P)$ with random variables $X_{1},\ldots,X_{n}$ such that their joint entropy $H$ satisfies $\max_{I\subseteq\{1,\ldots,n\}}\left|H\left(X_{I}\right)-h\left(I\right)\right|<\varepsilon$. This settles the last open case in a sequence of related undecidability results proved by L. K\"{u}hne and the author, with applications in algorithmic information theory. The main new tool is a Desargues'-type theorem for almost entropic polymatroids.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 16 canonical work pages

  1. [1]

    Michael Bamiloshin, Oriol Farr \`a s, and Carles Padr \'o , A note on extension properties and representations of matroids, arXiv preprint arXiv:2306.15085 (2023)

    work page Pith review arXiv 2023

  2. [2]

    233--236

    Randall Dougherty, Christopher Freiling, and Kenneth Zeger, Six new non-shannon information inequalities, 2006 IEEE International Symposium on Information Theory, IEEE, 2006, pp. 233--236

    work page 2006

  3. [3]

    Randall Dougherty, Chris Freiling, and Kenneth Zeger, Linear rank inequalities on five or more variables, arXiv preprint arXiv:0910.0284 (2009)

    arXiv 2009

  4. [4]

    , Non-shannon information inequalities in four random variables, arXiv preprint arXiv:1104.3602 (2011)

    arXiv 2011

  5. [5]

    1, 61--86

    Thomas A Dowling, A class of geometric lattices based on finite groups, Journal of Combinatorial Theory, Series B 14 (1973), no. 1, 61--86

    work page 1973

  6. [6]

    Batya Kenig and Dan Suciu, Integrity constraints revisited: From exact to approximate implication, Logical Methods in Computer Science 18 (2022)

    work page 2022

  7. [7]

    1, 95--147

    Lukas K \"u hne and Geva Yashfe, Representability of matroids by c-arrangements is undecidable, Israel Journal of Mathematics 252 (2022), no. 1, 95--147

    work page 2022

  8. [8]

    , On entropic and almost multilinear representability of matroids, arXiv preprint arXiv:2206.03465 ( 3 2022)

    work page Pith review arXiv 2022

Show all 18 references
  1. [9]

    6, 3493--3510

    Cheuk Ting Li, Undecidability of network coding, conditional information inequalities, and conditional independence implication, IEEE Transactions on Information Theory 69 (2023), no. 6, 3493--3510

    2023

  2. [10]

    1-3, 169--194

    Franti s ek Mat \'u s , Matroid representations by partitions, Discrete Mathematics 203 (1999), no. 1-3, 169--194

    1999

  3. [11]

    21, 2464--2477

    , Adhesivity of polymatroids, Discrete Mathematics 307 (2007), no. 21, 2464--2477

    2007

  4. [12]

    Frantisek Matus, Infinitely many information inequalities, 2007 IEEE International Symposium on Information Theory, IEEE, 2007, pp. 41--44

    2007

  5. [13]

    01, 1--6

    Franti s ek Mat \'u s , Algebraic matroids are almost entropic, Proceedings of the American Mathematical Society 152 (2024), no. 01, 1--6

    2024

  6. [14]

    2, 147--166

    Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, and Nikolai Vereshchagin, A new class of non-shannon-type inequalities for entropies, Communications in Information and Systems 2 (2002), no. 2, 147--166

    2002

  7. [15]

    3, Oxford University Press, USA, 2006

    James G Oxley, Matroid theory, vol. 3, Oxford University Press, USA, 2006

    2006

  8. [16]

    3, 379--423

    Claude E Shannon, A mathematical theory of communication, The Bell system technical journal 27 (1948), no. 3, 379--423

    1948

  9. [17]

    Raymond W Yeung, Information theory and network coding, Springer Science & Business Media, 2008

    2008

  10. [18]

    4, 1440--1452

    Zhen Zhang and Raymond W Yeung, On characterization of entropy function via information inequalities, IEEE transactions on information theory 44 (1998), no. 4, 1440--1452

    1998

Pith tools

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