We extend the Shannon-blind contextual information residue separation theorem fromcycle graphs to arbitrary finite graph families and introduce a partition-function formalismfor predicting error-regime boundaries. Our contributions are threefold. (1) We generalize theČech cohomological obstruction to parameterized n-cycles (proved for all n ≥ 3), completegraphs (K4 , with dim H 1 = 3), and trees (negative control: dim H 1 = 0, separation collapses).The polynomial degree barrier persists across all tested cycle lengths n ∈ {3, 4, 5, 7, 10, 15, 20}.P(2) We define a finite Čech Hamiltonian and partition function Z(β) = ω exp(−β · H(ω))on the measurement-cover graph, whose heat-capacity peak identifies a critical inversetemperature β ∗ predicting the error regime. (3) We present a falsifiability surface: the regimeclassifier (exact-decoder-required vs. surrogate-sufficient) is correct for all 8 tested graphfamilies, while the quantitative threshold predictions are falsified for 5 of 8 families undertolerance 0.03. All proofs are verified in Lean 4 with zero sorry declarations; all experimentsare exhaustive finite-graph enumerations reproducible from a single command. The separationis binary: any non-trivial cycle topology (H 1 ≥ 1) activates the full polynomial barrier,making exact symbolic computation the only reliable decoder for topologically structuredworkloads.
We extend the Shannon-blind contextual information residue separation theorem fromcycle graphs to arbitrary finite graph families and introduce a partition-function formalismfor predicting error-regime boundaries. Our contributions are threefold. (1) We generalize theČech cohomological obstruction to parameterized n-cycles (proved for all n ≥ 3), completegraphs (K4 , with dim H 1 = 3), and trees (negative control: dim H 1 = 0, separation collapses).The polynomial degree barrier persists across all tested cycle lengths n ∈ {3, 4, 5, 7, 10, 15, 20}.P(2) We define a finite Čech Hamiltonian and partition function Z(β) = ω exp(−β · H(ω))on the measurement-cover graph, whose heat-capacity peak identifies a critical inversetemperature β ∗ predicting the error regime. (3) We present a falsifiability surface: the regimeclassifier (exact-decoder-required vs. surrogate-sufficient) is correct for all 8 tested graphfamilies, while the quantitative threshold predictions are falsified for 5 of 8 families undertolerance 0.03. All proofs are verified in Lean 4 with zero sorry declarations; all experimentsare exhaustive finite-graph enumerations reproducible from a single command. The separationis binary: any non-trivial cycle topology (H 1 ≥ 1) activates the full polynomial barrier,making exact symbolic computation the only reliable decoder for topologically structuredworkloads.
We establish a formally verified three-layer separation theorem demonstrating that contextual information residue—the non-trivial Čech cohomology class of a Boolean 1cochain on a finite Z/2 cycle graph—is structurally invisible to both Shannon mutual information and bounded-degree polynomial computation. Specifically: (1) Shannon mutual information of a binary symmetric channel achieves AUC = 0.500 for contextual/noncontextual classification, exhibiting perfect orthogonality; (2) multilinear polynomials of degree d < n on n-bit cochains produce FN = 4088/4092 on the exhaustive corpus, a consequence of the Minsky–Papert degree barrier; and (3) exact rational symbolic evaluation Q via the parity formula parity(b) = (1 − i (1 − 2bi ))/2 ∈ Q achieves perfect classification with zero error. The algebraic core—including H 1 (Cn ; Z/2) ∼ = Z/2 and the non-coboundary witness for the triangle and square parity cochains—is verified in Lean 4 with Mathlib. The corpus comprises all 2n Boolean 1-cochains on cycles Cn for n ∈ {3, . . . , 12}, totaling 8,184 cochains exhaustively enumerated. All proofs, experiments, and data are publicly available. Published by The Institute for Applied Ontological Mathematics.
Whether a quantum proof outperforms a classical one — both checked by the same efficient quantum verifier — is a question answered, so far, only relative to oracles. Beneath that answer is a structure with no quantum content at all: the difference between a resource one can copy and one one cannot. We show that this difference is cohomological. A witness that carries a copy map collapses every verifier to a memoryless sampler, so its distinguishing power is a functional of k-wise marginals alone; the obstruction to copying is a Čech class on a cover of a state by its measurement bases, and the Forrelation function of Aaronson and Ambainis is exactly the transition cocycle of that cover. The separation holds precisely when the class is nonzero: invisible from inside any single copyable chart, where it is a coboundary, and visible to the linear witness that reads the whole cover at once. Four familiar facts turn out to be four faces of the same class. Its non-vanishing is the no-cloning theorem; the dimension of its kernel is the Landauer erasure cost of the witness register; its representative on the standard/Hadamard cover is Forrelation; and the collapse of the copyable verifier onto one chart is why a classical witness, for these problems, cannot win. We make each face a finite, exactly computed certificate: on a corpus of distinguishing tasks built from Heisenberg–Weyl orbits, every depth-two adaptive sampler has advantage exactly zero — a total quantification over the strategy space, not a sampled estimate — while the linear witness reads a squared-Forrelation gap the kernel computes from truth tables through the Hadamard transform. Two independent exact computations agree on every verdict, and the engine that results either returns a gap two exact paths both certify, or refuses — and a refusal carries its own evidence, a certificate of exactly the obstruction that stopped it. The asymptotic separation of the underlying family is not ours; we cite it. What is ours is the identification — that a separation of complexity classes is, at bottom, a hole. All results below are machine-checked in Lean 4; the formal record and its axiom footprint are described in Section 8. The paper is legible in mathematics alone. Published by The Institute for Applied Ontological Mathematics.
Topological quantum memories need decoders that are both reliable and scalable, but these goals compete: globally informed decoders are accurate near threshold yet expensive, while strictly local rules are fast but can miss long-range structure. Motivated by recent recoverability and mixed-state viewpoints, we make this tradeoff operational for the dephased toric code through a decoder-level local recoverability diagnostic. We compare global MWPM corrections to quasi-local corrections inside a target region and define a matching ratio Rmatch, with mismatch εmatch=1−Rmatch. Across geometry families, εmatch shows strong buffer-controlled suppression and is well organized by a two-geometry scaling form. For scaled families, especially a=b=d/8, Rmatch exhibits a clear crossing and finite-size collapse near p∼0.09, consistent with a growing recoverability scale near the decoding transition. We use this scaling to formulate an adaptive buffer-selection rule and to identify a distance-scaled initialization for a composite quasi-local RG decoder on the full torus. In the tuned family a0=b0=d/8, the resulting logical-failure curves show an apparent finite-size crossing at p≃0.09--0.10, below the conventional MWPM threshold scale. We focus on dephasing noise with perfect syndrome measurements to cleanly isolate the underlying behavior.
We are undergoing a revolution in data. The ever-growing amount of information in our world has created an unprecedented demand for ultra-reliable, affordable, and resource-efficient data storage systems. Error-correcting codes, as a critical component of any memory device, will play a crucial role in the future of data storage.One particular class of error-correcting codes, known as graph-based codes, has drawn significant attention in both academia and in industry. Graph-based codes offer superior performance compared to traditional algebraic codes. Recently, it has been shown that non-binary graph-based codes, which operate over finite fields rather than binary alphabets, outperform their binary counterparts and exhibit outstanding overall performance. For this reason, these codes are particularly suitable for emerging data storage systems.In this dissertation, we present a comprehensive combinatorial analysis of non-binary graph-based codes. We perform both finite-length and asymptotic analyses for these codes, providing a systematic framework to evaluate and optimize various families of non-binary graph-based codes.In the finite-length case, we provide a mathematical characterization of the error floor problem, including a general definition of absorbing sets over non-binary alphabets. We consider several structured low-density parity-check (LDPC) codes, including quasi-cyclic and spatially-coupled codes, as well as unstructured LDPC codes. We offer design guidelines for non-binary LDPC codes with outstanding performance in extremely low error-rate regimes; making them excellent candidates for data storage applications.In the asymptotic case, we provide a novel toolbox for the evaluation of families of non-binary graph-based codes. By utilizing insights from graph theory and combinatorics, we establish enumerators for a general family of graph-based codes which are constructed based on protographs. We provide asymptotic distributions of codewords and trapping sets for the family of protograph-based codes. Furthermore, we present an asymptotic enumeration of binary and non-binary elementary absorbing sets for regular code ensembles.The contributions of this dissertation can potentially impact a broad range of data storage and communication technologies that require excellent performance in high-reliability regimes.
A CSS quantum error-correcting code is, on the nose, a length-three chain complex over F2 : the commutation law HZ H⊤ X = 0 that makes the code valid is exactly the condition ∂ 2 = 0 that makes a chain complex. We take this identification literally and show that the entire working theory of a quantum code is one homological object the same engine computes, at scale, and certifies. The number of logical qubits is the first Betti number, k = dim H1 = n − rank HX − rank HZ = b1 ; the code distance is the systole, the shortest non-contractible cycle. We reproduce the published parameters of state-of-the-art codes exactly—the toric and hypergraph-product families and the IBM bivariate-bicycle codes [[72, 12, 6]], [[144, 12, 12]], [[90, 8, 10]]—cross-validated four independent ways and kernelcertified for the small cases in Cubical Agda, on CPU and GPU. The two scale certificates—the Betti count b1 and the rank-derived logical count k—are themselves kernel-proved to be a single first-homology certificate (a DescentCertificate both readings factor through), closed terminally through a fixed-point engine. We then run the code, not just measure it. (i) The Union-Find decoder is the engine's connected-components reduction, and "a logical error occurred" is the engine's coboundary decision (the residual cycle has nonzero winding); decoding the toric code at growing distance recovers the accuracy threshold near 9.5%, and the optimal (maximum-likelihood) threshold near 11% is the engine's two homology sectors competing as the domain-wall free energy of a random-bond Ising model on the Nishimori line. (ii) A code's distance scaling is its Tanner-graph spectral expansion: the second eigenvalue λ2 versus the Ramanujan bound is a computable certificate (Sipser–Spielman), exact on the topological tier where the spectral gap obeys γ d2 → 4π 2 . (iii) The full chain complex carries metachecks—redundancies among the parity checks—and we compute them: the bivariate-bicycle codes have six, the engines of single-shot error correction; the 4-dimensional toric code's homology (1, 4, 6, 4, 1), with k = b2 = 6, is the tensor of four circle complexes. (iv) The logical error-rate prefactor is the multiplicity of the systole, A = 2L for the toric code, which we compute exactly. (v) Finally the engine measures a topological phase transition: as random noise thickens, torus-wrapping "giant" cycles appear in a sharp homological-percolation transition at pc ≈ 0.5 that sharpens with system size—the same homology machinery now detecting when noise spontaneously writes a logical operator. (vi) The engine runs over any coefficients: qudit (Fp ) codes are chain complexes over Fp , and the integral homology, computed by the Smith normal form, exposes torsion—so a code's logical-qudit count can depend on the qudit dimension, an extra logical appearing exactly when p divides a torsion coefficient (reproducing the known homology of the torus, the Moore spaces, the Klein bottle, and RP2 ). We are careful to fence what is not claimed: minimum distance is NP-hard in general and we compute it only on the systolic tier; the giant-cycle transition is the random-cluster one, distinct from the maximum-likelihood decoding threshold of the random-bond Ising model. The thesis is singular and operational: a quantum code's parameters, its decoder, its quality, its higher-dimensional structure, its performance prefactor, and its phase transition are not six theories but one—homology you can run. Published by The Institute for Applied Ontological Mathematics.
Preprint of the article "A fixed-level certification dichotomy for an infinite family of frustration-free spin chains" (22 pages, no figures). To every finite loopless directed graph T the paper attaches a rational, range-three, frustration-free spin-chain interaction: arcs of T carry hopping bands for domain walls, missing arcs act as hard local penalties. The main theorem is the exact three-term equivalence: T is acyclic <=> liminf_m gap_m(T) > 0 <=> delta_LTI(5) > 0, where gap_m is the spectral gap of the periodic chain on m sites and delta_LTI(5) is the value of the local translation-invariant (LTI) semidefinite certification hierarchy at level 5, its first sound level. The certification level is fixed while the size of the graph and the local Hilbert-space dimension are unbounded across the family. To the author's knowledge, this is the first fixed-level completeness result for a spectral-gap certification hierarchy over an infinite family of frustration-free chains: a single finite combinatorial invariant, acyclicity, decides both the thermodynamic spectral gap and the success of the certificate at one universal level. The acyclic direction is proved by an explicit rational certificate, a superpotential built from a topological height and three local corrections, giving delta_LTI(5) >= min{1/48, 1/sqrt(12H)} for a DAG of height H. The cyclic direction is made quantitative by a free-fermion analysis of the invariant winding sectors: directed cycles carry a diffusive lowest mode of energy of order 1/m^2, and the finite-volume gaps of the directed 2- and 3-cycles are computed exactly, 2(1-cos(pi/m)) and 2(1-cos(2pi/m)). The relationship with the PVBS chains of Bachmann and Nachtergaele and with earlier gapped-gapless classifications is discussed explicitly. All computer-assisted statements use exact symbolic arithmetic. The complete reproducibility package (symbolic pipeline, generated blocks with exact characteristic polynomials, Sturm data, LDL^T certificates, SHA-256 digests) is archived separately at https://doi.org/10.5281/zenodo.21790411. The manuscript has been submitted to Reports on Mathematical Physics.