Technical Spine

Compositional Incoherence is a Parity

Local Audit Carries Zero Signal; Recovering Conventions from Observation is SQ- and LPN-Hard

DemonstratedExplicit-constant SQ lower-bound crux machine-checked in Lean 4 (LocalCertificationSQ, Aristotle stamp b4f87803, standard axioms): Bessel/Markov counting, the pigeonhole, and the assembled bound q ≥ (2^k-1)τ² chained for a concrete query. Orthonormality/Parseval and the SQ-model facts (union bound, identification) enter as cited hypotheses; Theorems 1 and 3 are paper-level. Finite arithmetic demonstration — measured, with a negative control; interpretability-probe LLM scaling deferred. Draft, June 2026.
Key result

Recovering the compositional obstruction from r-local observation is SQ-hard (q ≥ (2^k-1)τ²) and LPN/LWE-hard under noise — local interpretability sees zero cyclic signal by a complexity barrier, not a tooling gap

Falsification

A radius-r statistical query correlated with the obstruction (refutes Thm 1); a poly(k)-query constant-tolerance learner recovering the obstruction (refutes Thm 2); a PPT recoverer from noisy local views (refutes Thm 3 or breaks LPN/LWE)

Abstract

Semantic coherence of a composition is agreement of the conventions its components attach to shared quantities around every cycle; a companion impossibility result shows no bounded-radius local audit can certify it. This paper recasts certification as learning, from one observation: the holonomy of a composition around a cycle is a parity of edge signs, so recovering its coherence structure is learning a parity. Three results follow. On a graph of girth > 2r the radius-r local views are identical across all obstructions, so local interpretability obtains zero signal at any sample size. Detection is trivial but recovery is statistical-query-hard: any correlational-SQ learner needs q ≥ (2^k-1)τ² queries, exponential in the cycle-count. Under noisy observation, recovery is LPN/LWE-hard in the abelian regime. The barrier is complexity-theoretic, not a tooling limitation.

Resources