Recognition: 1 theorem link
· Lean TheoremZero-Error Recovery under Deterministic Partial Views: Matroid Bounds and Verifiable Realizability
Pith reviewed 2026-05-15 18:32 UTC · model grok-4.3
The pith
For affine realized state families, restricted coordinate ranks form a representable matroid that certifies polynomial-time upper bounds on zero-error confusability and asymptotic capacity.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For affine realized state families with explicit linear presentations, restricted coordinate ranks form a representable matroid certificate giving polynomial-time upper bounds on one-shot confusability and asymptotic capacity, with rank additivity matching direct-sum block composition. In the full tuple-space coordinate model, the realizable confusability relations are exactly the upward-closed coordinate-agreement families. Transitive confusability is equivalent to intersection closure of the generated agreement family, yielding a cluster graph whose capacity is determined by connected components. Verifiable rate-1 realizability for structural facts holds if and only if the host provides零-零
What carries the argument
The representable matroid formed by restricted coordinate ranks in an affine realized state family, which supplies the certificate for polynomial-time bounds on the induced confusability graph.
If this is right
- Polynomial-time upper bounds on one-shot confusability and asymptotic capacity become available for any qualifying affine state family.
- Rank additivity guarantees that the bounds compose correctly under direct-sum block constructions.
- Every realizable confusability relation in the full coordinate model is an upward-closed coordinate-agreement family.
- Transitive confusability reduces to a cluster graph whose capacity is completely determined by its connected components.
- Rate-1 verifiable realizability of structural facts requires the host to supply zero-delay synchronization together with structural side-information.
Where Pith is reading between the lines
- The matroid certificate could be used to select which coordinates to observe in order to tighten recovery bounds in structured sensing systems.
- The exact characterization of realizable relations as upward-closed agreement families may simplify capacity calculations for other partial-observation models that share the same coordinate structure.
- The uniform clique-size bit-budget bound across inter-fact and intra-fact layers suggests that resource allocation for recovery can be made independent of the fact layer.
Load-bearing premise
The latent state family must be affine realized with explicit linear presentations for the matroid certificate and the rank-additivity property to hold.
What would settle it
An explicit small-dimensional affine state family with a linear presentation in which the matroid-derived upper bound on the chromatic number of the confusability graph is strictly larger than the true chromatic number.
Figures
read the original abstract
Zero-error recovery under deterministic partial views is graph recovery for the induced confusability relation. A finite family of coordinate-subset observations determines a graph on latent states; $T$-ary exact recovery is graph $T$-colorability, block composition is strong powering, and asymptotic recoverability is Shannon capacity. Coordinate structure gives tractable certificates inside the graph semantics. For affine realized state families with explicit linear presentations, restricted coordinate ranks form a representable matroid certificate giving polynomial-time upper bounds on one-shot confusability and asymptotic capacity, with rank additivity matching direct-sum block composition. In the full tuple-space coordinate model, the realizable confusability relations are exactly the upward-closed coordinate-agreement families. Transitive confusability is equivalent to intersection closure of the generated agreement family, yielding a cluster graph whose capacity is determined by connected components. Host-level realizability fixes when the latent state family is canonical. Verifiable rate-$1$ realizability for structural facts holds if and only if the host provides zero-delay synchronization and structural side-information; eleven representative host architectures instantiate the criterion. The inter-fact and intra-fact layers share the same clique-size bit-budget bound. All cited results are mechanized in Lean 4 against a shared formalization library.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript models zero-error recovery under deterministic partial views as graph recovery for confusability relations induced by coordinate-subset observations. For affine realized state families with explicit linear presentations, restricted coordinate ranks form a representable matroid certificate that yields polynomial-time upper bounds on one-shot confusability and asymptotic capacity, with rank additivity matching direct-sum block composition. It further characterizes realizable confusability relations as upward-closed coordinate-agreement families, equates transitive confusability to intersection closure, and provides verifiable rate-1 realizability criteria for eleven host architectures, with all results mechanized in Lean 4.
Significance. If substantiated, the work would advance zero-error information theory by supplying matroid-based, computationally tractable certificates for capacity bounds in structured partial-observation settings, extending beyond purely graph-theoretic methods. The explicit Lean 4 mechanization against a shared library constitutes a notable strength, offering external verification of the matroid realizability and rank-additivity claims. The scoping to affine realized families with linear presentations is clearly delimited, though the breadth of this class relative to general state families would determine broader applicability.
major comments (1)
- Abstract: the central claim that restricted coordinate ranks induce a representable matroid providing polynomial-time upper bounds cannot be verified without the full manuscript, explicit definitions of the restriction and linear presentations, and the Lean code; this prevents assessment of whether the bounds are load-bearing or contain gaps in the derivation of rank additivity.
minor comments (2)
- Abstract: the term 'affine realized state families' is introduced without a brief definition or reference, which may reduce accessibility for readers outside the immediate subfield.
- Abstract: the statement that 'all cited results are mechanized in Lean 4' would be strengthened by indicating the scope (e.g., whether every theorem or only key lemmas are covered).
Simulated Author's Rebuttal
We thank the referee for their careful reading and for noting the need for greater self-containment in the abstract. The full manuscript supplies the requested definitions, proofs of rank additivity, and Lean 4 mechanization; we have revised the abstract to include the core definitions while preserving its brevity. We address the single major comment below.
read point-by-point responses
-
Referee: Abstract: the central claim that restricted coordinate ranks induce a representable matroid providing polynomial-time upper bounds cannot be verified without the full manuscript, explicit definitions of the restriction and linear presentations, and the Lean code; this prevents assessment of whether the bounds are load-bearing or contain gaps in the derivation of rank additivity.
Authors: We agree that the original abstract was too terse. An affine state family with explicit linear presentation is a set of vectors in F_q^n generated by a matrix A whose columns are the states; a coordinate subset S induces the restricted rank r(S) = rank(A_S), where A_S is the submatrix of rows in S. The representable matroid is the column matroid of A, and the confusability graph's independence number is bounded above by the matroid rank function, which is computable in polynomial time by Gaussian elimination. Rank additivity under block composition follows because the linear presentation is compatible with the direct-sum matroid structure (Theorem 4.3). The Lean 4 formalization (files Matroid.lean and Capacity.lean) verifies both the rank-oracle bounds and the additivity identity. We have inserted a one-sentence definition of linear presentation and restricted rank into the revised abstract and added a pointer to the supplementary Lean code. revision: yes
Circularity Check
No significant circularity; claims externally grounded by Lean mechanization
full rationale
The abstract states that all cited results are mechanized in Lean 4 against a shared formalization library. This supplies independent, machine-checked verification rather than reducing any load-bearing claim to a self-definition, fitted parameter renamed as prediction, or self-citation chain. The matroid certificate and rank-additivity statements are scoped to affine realized families with explicit linear presentations; no equation or step in the provided text equates a derived quantity to its own input by construction. The restriction to this class is explicitly declared, and the Lean grounding satisfies the criterion for non-circular external support.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Standard definitions and properties of graphs, matroids, colorability, and Shannon capacity hold.
- domain assumption The latent states admit an affine realization with explicit linear presentations when the matroid bounds are claimed.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
For affine realized state families with explicit linear presentations, restricted coordinate ranks form a representable matroid certificate giving polynomial-time upper bounds on one-shot confusability and asymptotic capacity, with rank additivity matching direct-sum block composition.
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
C. E. Shannon, Zero-Error capacity of a noisy channel, IRE Transactions on Information Theory 2 (3) (1956) 8–19.doi:10.1109/TIT.1956. 1056798
-
[2]
L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25 (1) (1979) 1–7.doi:10.1109/TIT.1979. 1055985
-
[3]
N. Alon, E. Lubetzky, The Shannon capacity of a graph and the in- dependence numbers of its powers, IEEE Transactions on Information Theory 52 (5) (2006) 2172–2176.doi:10.1109/TIT.2006.872856
-
[4]
D. de Boer, P. Buys, J. Zuiddam, The asymptotic spectrum distance, graph limits, and the Shannon capacity (2024).arXiv:2404.16763, doi:10.48550/arXiv.2404.16763
-
[5]
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (2) (1981) 169–197.doi:10.1007/BF02579276
-
[6]
S. Gilbert, N. Lynch, Brewer’s conjecture and the feasibility of con- sistent, available, partition-tolerant web services, ACM SIGACT News 33 (2) (2002) 51–59, formal proof of CAP theorem.doi:10.1145/ 564585.564601
-
[7]
M. Herlihy, J. M. Wing, Linearizability: A correctness condition for concurrent objects, in: Proceedings of the 11th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 1990, pp. 139–150. doi:10.1145/214548.214562
-
[8]
K. V. Rashmi, N. B. Shah, K. Ramchandran, D. Gu, Multi-version coding: An information-theoretic perspective of consistent distributed storage, IEEE Transactions on Information Theory 63 (6) (2017) 4111– 4128.doi:10.1109/TIT.2017.2695219
-
[9]
L. de Moura, S. Ullrich, The Lean 4 theorem prover and programming language, in: Automated Deduction – CADE 28, Springer, 2021, pp. 625–635.doi:10.1007/978-3-030-79876-5_37. 33
-
[10]
The mathlib Community, The Lean mathematical library, in: Proceed- ings of the 9th ACM SIGPLAN International Conference on Certi- fied Programs and Proofs, 2020, pp. 367–381.doi:10.1145/3372885. 3373824
-
[11]
R. M. Fano, Transmission of Information: A Statistical Theory of Com- munications, MIT Press, Cambridge, MA, 1961
work page 1961
-
[12]
H. S. Witsenhausen, A. D. Wyner, A conditional entropy bound for a pair of discrete random variables, IEEE Transactions on Information Theory 21 (5) (1975) 493–501
work page 1975
-
[13]
T. M. Cover, J. A. Thomas, Elements of Information Theory, 2nd Edi- tion, Wiley-Interscience, 2006.doi:10.1002/047174882X
-
[14]
B. G. Kelly, A. B. Wagner, Improved source coding exponents via Witsenhausen’s rate, IEEE Transactions on Information Theory 57 (9) (2011) 5615–5633.doi:10.1109/TIT.2011.2162178
-
[15]
D. B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, 2001
work page 2001
-
[16]
Diestel, Graph Theory, 5th Edition, Springer, 2017.doi:10.1007/ 978-3-662-53622-3
R. Diestel, Graph Theory, 5th Edition, Springer, 2017.doi:10.1007/ 978-3-662-53622-3
work page 2017
-
[17]
Oxley, Matroid Theory, 2nd Edition, Oxford University Press, 2011
J. Oxley, Matroid Theory, 2nd Edition, Oxford University Press, 2011
work page 2011
-
[18]
D. J. A. Welsh, Matroid Theory, Academic Press, 1976
work page 1976
-
[19]
A. Recski, Matroid Theory and Its Applications in Electric Network Theory and in Statics, Springer, 1989
work page 1989
-
[20]
M. Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten, Mathematische Zeitschrift 17 (1) (1923) 228–249.doi:10.1007/BF01204614
-
[21]
Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Vol
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Vol. A, Springer, 2003.doi:10.1007/978-3-642-27448-2
-
[22]
W.H.Haemers, AnupperboundfortheShannoncapacityofagraph, in: Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis János Bolyai, Vol. 25, 1978, pp. 267–272. 34
work page 1978
-
[23]
J. Zuiddam, The asymptotic spectrum of graphs and the Shannon ca- pacity, Combinatorica 39 (5) (2019) 1173–1184.doi:10.1007/s00493- 019-3992-5
-
[24]
J. Körner, Coding of an information source having ambiguous alphabet and the entropy of graphs, Transactions of the 6th Prague Conference on Information Theory (1973) 411–425
work page 1973
- [25]
-
[26]
H. S. Witsenhausen, The Zero-Error side information problem and chro- matic numbers, IEEE Transactions on Information Theory 22 (5) (1976) 592–593
work page 1976
-
[27]
D. Slepian, J. K. Wolf, Noiseless coding of correlated information sources, IEEE Transactions on Information Theory 19 (4) (1973) 471– 480.doi:10.1109/TIT.1973.1055037
-
[28]
A. Orlitsky, J. R. Roche, Coding for computing, IEEE Transactions on Information Theory 47 (3) (2001) 903–917.doi:10.1109/18.915643
-
[29]
N. Alon, A. Orlitsky, Source coding and graph entropies, IEEE Trans- actions on Information Theory 42 (5) (1996) 1329–1339.doi:10.1109/ 18.532875
work page 1996
-
[30]
V. Doshi, D. Shah, M. Médard, M. Effros, Functional compression through graph coloring, IEEE Transactions on Information Theory 56 (8) (2010) 3901–3917.doi:10.1109/TIT.2010.2050835
-
[31]
Simonyi, Graph entropy: A survey, in: Combinatorial Optimization, Vol
G. Simonyi, Graph entropy: A survey, in: Combinatorial Optimization, Vol. 20 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, Rhode Island, 1995, pp. 399–441.doi:10.1090/dimacs/020/08
-
[32]
X. Guang, R.Zhang, Zero-Errordistributed compression ofbinary arith- metic sum, IEEE Transactions on Information Theory 70 (5) (2024) 3100–3117.doi:10.1109/TIT.2023.3319976. 35
-
[33]
Y. Liu, L. Ong, S. Johnson, J. Kliewer, P. Sadeghi, P. L. Yeoh, Informa- tion leakage in Zero-Error source coding: A Graph-Theoretic perspec- tive, in: 2021 IEEE International Symposium on Information Theory (ISIT), 2021, pp. 2590–2595.doi:10.1109/ISIT45174.2021.9517778
-
[34]
G. Kiczales, J. des Rivières, D. G. Bobrow, The Art of the Metaobject Protocol, MIT Press, 1991
work page 1991
-
[35]
B. C. Smith, Reflection and semantics in Lisp, in: Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of program- ming languages, 1984, pp. 23–35.doi:10.1145/800017.800513
-
[36]
X. Leroy, Formal verification of a realistic compiler, Communications of the ACM 52 (7) (2009) 107–115.doi:10.1145/1538788.1538814
-
[37]
T. Simas, Exact recovery under deterministic partial views: Confus- ability graphs, strong powers, and capacity, Zenodo, supplementary Lean 4 formalization, manuscript PDF, and source bundle. (2026). doi:10.5281/zenodo.19354075. URLhttps://doi.org/10.5281/zenodo.19354075
- [38]
-
[39]
Available: docs.python.org/3/reference/datamodel.html (2025)
PythonSoftwareFoundation, Pythondatamodel, Python3Documenta- tion, [Online]. Available: docs.python.org/3/reference/datamodel.html (2025)
work page 2025
-
[40]
Available: www.postgresql.org/docs/current/rules-materializedviews.html (2025)
The PostgreSQL Global Development Group, Material- ized views, PostgreSQL documentation, [Online]. Available: www.postgresql.org/docs/current/rules-materializedviews.html (2025)
work page 2025
-
[41]
Available: www.postgresql.org/docs/current/view-pg-matviews.html (2025)
The PostgreSQL Global Development Group, pg_matviews, PostgreSQL system catalog documentation, [Online]. Available: www.postgresql.org/docs/current/view-pg-matviews.html (2025)
work page 2025
-
[42]
The Rust Team, The Rust reference, Language reference, online: doc.rust-lang.org/reference/ (2024). 36
work page 2024
-
[43]
Available: www.typescriptlang.org/docs/handbook/decorators.html (2025)
Microsoft, Decorators, TypeScript Handbook, [Online]. Available: www.typescriptlang.org/docs/handbook/decorators.html (2025)
work page 2025
-
[44]
Available: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes (2025)
MDN Web Docs, Classes, JavaScript reference, [Online]. Available: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes (2025)
work page 2025
-
[45]
J. Gosling, B. Joy, G. Steele, G. Bracha, A. Buckley, D. Smith, G. Bier- man, The Java Language Specification, Java SE 17 Edition, Oracle America, Inc., 2021, online: docs.oracle.com/javase/specs/
work page 2021
-
[46]
TheGoAuthors, TheGoprogramminglanguagespecification, Language specification, online: go.dev/ref/spec (2024)
work page 2024
-
[47]
Available: docs.npmjs.com/cli/v8/configuring-npm/package-lock-json/ (2026)
npm, Inc., package-lock.json, npm CLI documentation, [Online]. Available: docs.npmjs.com/cli/v8/configuring-npm/package-lock-json/ (2026)
work page 2026
-
[48]
Available: docs.npmjs.com/cli/v7/commands/npm-explain/ (2026)
npm, Inc., npm explain, npm CLI documentation, [Online]. Available: docs.npmjs.com/cli/v7/commands/npm-explain/ (2026)
work page 2026
-
[49]
Available: docs.npmjs.com/cli/v7/commands/npm-ls/ (2026)
npm, Inc., npm ls, npm CLI documentation, [Online]. Available: docs.npmjs.com/cli/v7/commands/npm-ls/ (2026)
work page 2026
-
[50]
The Rust Project Developers, Cargo.toml vs cargo.lock, The Cargo Book, [Online].Available: doc.rust-lang.org/cargo/guide/cargo-toml-vs- cargo-lock.html (2026)
work page 2026
-
[51]
Available: doc.rust-lang.org/cargo/commands/cargo-tree.html (2026)
The Rust Project Developers, cargo-tree, The Cargo Book, [Online]. Available: doc.rust-lang.org/cargo/commands/cargo-tree.html (2026)
work page 2026
-
[52]
Available: doc.rust-lang.org/cargo/commands/cargo- metadata.html (2026)
The Rust Project Developers, cargo-metadata, The Cargo Book, [Online]. Available: doc.rust-lang.org/cargo/commands/cargo- metadata.html (2026)
work page 2026
-
[53]
Available: python-poetry.org/docs/cli/ (2026)
Poetry Contributors, CLI, Poetry documentation, [Online]. Available: python-poetry.org/docs/cli/ (2026)
work page 2026
-
[54]
Avail- able: pnpm.io/cli/install (2026)
pnpm Contributors, pnpm install, pnpm documentation, [Online]. Avail- able: pnpm.io/cli/install (2026). 37
work page 2026
-
[55]
Avail- able: pnpm.io/cli/why (2026)
pnpm Contributors, pnpm why, pnpm documentation, [Online]. Avail- able: pnpm.io/cli/why (2026)
work page 2026
-
[56]
Avail- able: pnpm.io/cli/list (2026)
pnpm Contributors, pnpm list, pnpm documentation, [Online]. Avail- able: pnpm.io/cli/list (2026). A. Boundary and Realizability Proofs A.1. Derived Views and the Unit-Rate Boundary An encoding system hasunit independent ratewhen DOF(C, F) = 1. By Corollary 2.7, this is exactly the regime in which every reachable state remains coherent, and any rate above1...
work page 2026
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.