Pure Mathematics for Theoretical Computer Science

We study the reversibility of one-dimensional linear cellular automata (CA) with periodic boundary conditions over a finite field Fq, identifying the global transition map with multiplication by a rule polynomial f (x) in the cyclic group algebra Rn = Fq[x]/(xn−1). We prove that reversibility is exactly equivalent to f (x) being a unit of Rn, and, when gcd(n,q) = 1, we use the classical correspondence between irreducible factors of xn−1 and q-cyclotomic cosets modulo n to derive a closed-form count of the reversible rules of a given neighborhood size: |R×n | = Πi(qdi −1), where the di are the sizes of the q-cyclotomic cosets modulo n. We then resolve the complementary case gcd(n,q)>1: writing n = pam with p = char(Fq) and gcd(m, p) = 1, we show xn−1 = (xm−1)pa , determine the local structure of each factor ring Fq[x]/(g(x)pa) for g irreducible, and obtain the fully general count |R×n| = Πi qdi(pa−1)(qdi −1), valid for every n and every finite field Fq. We give an explicit closed form for the case where m is prime and q is a primitive root modulo m, a density lower bound, an explicit description of the group of reversible rules under composition together with a formula for the exact dynamical period of any reversible rule via its coordinates under the Chinese Remainder Theorem, and a remark on explicit inverse-rule construction. All results are stated and proved in full; numerical instances used to validate the formulas were checked by direct and brute-force computation and are reported without tabulation.

A proof-only calculus is developed for exact set abstraction and backward safety certification of monotone neural operators. A Galois insertion between concrete sets and interval boxes yields the best correct interval transformer. For every coordinatewise monotone map F, this transformer maps [ℓ,u] exactly to [F(ℓ),F(u)]; hence layerwise interval propagation is hull-exact for networks with nonnegative weights and isotone activations. The analysis is sharpened for max–plus layers T(x) =W ⊗x⊕b. Their upper safety preimages are either empty or principal ideals generated by the residualW\y, where (W\y)i = inf j:Wji>−∞(yj−Wji). Reverse residual propagation through a depth-L network computes the greatest input vector satisfying a prescribed upper output bound. Consequently, the largest weighted ℓ∞ radius around a nominal input is obtained in closed form, without optimization, branching, sampling, or relaxation. Soundness, maximality, compositionality, exactness, homogeneous collapse, and target-bound stability are proved. Four open problems concern signed architectures, two-sided class margins, residuated transformer attention, and completeness beyond boxes.

Implicit hypergraph models represent higher-order propagation by an equilibrium equation, but standard wellposedness arguments typically force a contraction and therefore exclude noncontractive yet order-preserving dynamics. This paper introduces an interval-lattice semantics for implicit hypergraph neural operators. On the box lattice L = {X ∈ Rn×d : ℓ ≤ Xi j ≤ u}, a normalized hypergraph propagation PH ≥ 0, an entrywise nonnegative channel map A ≥ 0, and an isotone activation generate an order-preserving operator T : L →L. The Knaster– Tarski theorem then yields a nonempty complete lattice of equilibria without requiring ∥A∥ < 1. Coupled iterations from the bottom and top elements produce certified lower and upper enclosures for every equilibrium. Under the optional metric condition q = Lσ ∥PH ∥2 ∥A∥2 < 1, the extremal equilibria coincide; geometric convergence, a residual-to-solution certificate, and a structural perturbation bound follow. Permutation equivariance and monotone dependence on input features are also proved. Two small arithmetic tables illustrate certificate scaling rather than empirical performance. The paper concludes with seven open problems on noncontractive uniqueness, signed hypergraphs, finite certificate complexity, topology-aware perturbation metrics, expressivity, differentiable extremal selection, and asynchronous lattice iteration.

We study spectral moment invariants Σp(G) = (trAG, . . . , trApG), built from the adjacency spectrum of a graph G, as graph isomorphism invariants positioned relative to the Weisfeiler–Leman (WL) hierarchy used to characterize graph neural network (GNN) expressivity. We give three fully verified case studies. First, C6 vs. 2K3: a 1- WL-indistinguishable pair separated by Σ3 but not Σ2 or Σ4. Second, K3,3 vs. the triangular prism: a second 1-WL-indistinguishable, cubic pair, also separated at order 3, but where the fourth moment separates as well, showing separating power is graph-family dependent even at fixed order. Both examples are grounded in a general fourth-moment identity (Proposition 2.8) and a homomorphism-counting identity (Proposition 2.5) that we prove from first principles. Third, and in the opposite direction, we prove that spectral moment invariants of every finite order fail on the classical cospectral, non-isomorphic strongly regular pair srg(16,6,2,2) (the Shrikhande graph and the 4×4 rook’s graph), verified numerically to fourth order by two independent methods. We situate both directions within published enumeration data and the Godsil–McKay switching construction, compare the computational complexity of spectral-moment, WL, and general isomorphism testing, connect the limitation to Laplacian eigenvector positional encodings in Graph Transformers, and pose three precise open problems.

A Functorial Structure is defined as a covariant functor F : C → Set, assigning sets to objects and functions to morphisms, ensuring functoriality. In this paper, we introduce and formally define two new concepts: the HybridFunctorial Structure and the MultiFunctorial Structure. A HybridFunctorial Structure combines two functors on the same category, linked by a natural transformation, ensuring consistent pushforward compatibility. A MultiFunctorial Structure involves multiple functors indexed by a preorder, coherently related via natural transformations, forming compatible families with functorial consistency.

Standard probability theory assigns each event a single real value in [0, 1], satisfying non-negativity, normalization, and countable additivity. Hyper-Probability extends this notion by assigning to each event a set of probability values in [0, 1], thereby capturing multiple independent assessments from diverse sources. Super-HyperProbability further generalizes the framework by mapping events to iterated power sets of [0, 1], modeling hierarchical uncertainty across multiple aggregation levels. In this paper, we formally define the Hyper-Probability Measure and Hyper-Probability Distribution, examine their fundamental properties, and demonstrate how these constructs unify and extend classical probability within the Hyper- and Super-HyperProbability paradigms.