Module ait 

Algorithmic information theory — certified description-length objects

The provers already measure algorithmic information (hypercube::symmetry_entropy_bits = log₂|Aut(F)|; the clause-orbit quotient as “the computable shadow of Kolmogorov complexity”). This module promotes those measurements into certified objects: a description length that carries a re-checkable witness, so “this object compresses to N bytes” is something a checker confirms rather than trusts.

Kolmogorov complexity K(x) is uncomputable, so we work with the two honest sides of it:

• Upper bounds K̄(x) are computable — the shortest program in a fixed description language that reproduces x. DescriptionBound carries such a program together with the bytes that, when decoded, reproduce x (the witness). The description language is layered: Descriptor::IntSeq is the closed-form generator menu of [logicaffeine_base::describe] (affine / geometric / polynomial / periodic / sparse / …), a computable upper bound with a lossless decode witness.

Lower bounds (the incompressibility side) and the two-sided structural bound live alongside this, gated by a budget so we never claim a bound past what the prover can itself re-check (the operational Chaitin ceiling).

Structs

AffineReduction

The affine reduction of a Boolean function: f(x) = h(reduced) ⊕ ℓ(x), where ℓ is a linear form and h collapses onto the free coordinates. This peels the COMPLEMENT linear structures (D_a f = 1) that reduce_by_invariance cannot — a residue XOR a linear form is invisible to every other axis but folds here.

AffineSignature

The AGL(n,2)-invariant signature of a Boolean function: its Walsh amplitude distribution and the plateaued/bent classification that distribution induces.

AlgebraicAttack

The certified result of an algebraic-recurrence attack: a low-degree nonlinear feedback register that regenerates a byte string, recovered by [describe::detect_algebraic_recurrence]. This is the OPEN rung — where maximal order complexity can only measure a nonlinear register (its 2^order truth table), the algebraic attack recovers it as a sparse ANF and thereby compresses it, when the feedback has low degree. The anf is a re-checkable witness (replay it with the seed).

AlgebraicImmunityReport

The algebraic-immunity profile of a filter/combining function: the minimum degree of an annihilator (the algebraic attack’s leverage), the maximum possible ⌈n/2⌉, and whether it sits at that ceiling.

BooleanCensus

An exhaustive census of the whole Boolean-function space on n variables: which structural axis the deep finder wins on, for every one of the 2^{2ⁿ} functions.

Budget

The prover’s own description budget — the operational Chaitin ceiling. Kolmogorov complexity lower bounds are only certifiable up to what the prover can itself re-check; beyond a resource bound we decline rather than over-claim. Every lower-bound (incompressibility) path is gated by a Budget and returns a documented Refusal instead of a certificate when a bound is exceeded. (Upper bounds — DescriptionBound — are always safe to compute: you can only be pleasantly surprised by a shorter description.)

CombinerLeak

A certified combiner leak: one candidate LFSR that a keystream measurably correlates with, recovered by [describe::correlation_attack]. The attack.init_state is the re-checkable witness.

CompressibilityReport

A full compressibility report: the class, the degree (K̄/n), and the raw vs described sizes.

CoverageCensus

A coverage census over a corpus of sequences: how many the lens arsenal covers, how many fall in the uncovered residue, and which lens covered how many. This is the covering problem made countable.

DeepStructureReport

The winning axis and description size of the unified deep structure finder.

DescriptionBound

A computable upper bound K̄(x) on the Kolmogorov complexity of an object x, over the fixed description language, carrying a re-checkable decode witness.

InvarianceReduction

The genuine domain compression from the INVARIANCE subspace V₀(f) = {a : f(x⊕a) = f(x) ∀x}: an (n − dim V₀)-variable truth table carrying all the information, over the surviving free_positions. A rotated junta collapses here even though the coordinate junta lens saw every variable as relevant.

KolmogorovBound

A certified Kolmogorov upper bound on a Boolean function: the recursive structure decomposition and its total description size, with a re-checkable decode witness. This is a K̄ — an UPPER bound only. The kernel-certified Chaitin theorem in this module forbids certifying K(f) > c for any function past budget, so a bound that equals the raw 2ⁿ means “irreducible by this arsenal,” never “incompressible.”

LensCoverage

One lens’s verdict on a sequence: the number of bits it needs to DESCRIBE the sequence (usize::MAX if the lens finds no exploitable structure). Lower ⇒ the lens compresses it more.

LensReport

The result of running the whole lens portfolio against a bit sequence.

LinearDistinguisher

The linear-cryptanalytic profile of a Boolean combining/filter function, from its Walsh spectrum: the best linear approximation (the distinguisher), its nonlinearity, and its correlation-immunity order.

LinearRigidityCert

A re-checkable certificate that F’s parity structure admits no linear symmetry shortcut beyond its exposed kernel: the GF(2) coefficient system has rank rank, its solution space is exactly 2^solution_count_log2 (spanned by kernel_basis), and this is the complete linear structure.

LinearStructureCert

The par32-scale linear-structure certificate: the GF(2) rank and kernel dimension of F’s parity system, valid for any number of variables (beyond the u64 cap of LinearRigidityCert). It carries no explicit kernel basis — at this scale the witness is recomputation: re-extract the parity system, re-reduce it, and confirm the same rank and kernel dimension. This is the object par32’s “157-dim linearly-rigid kernel” measurement becomes.

LinearStructureReport

The linear space V(f) of a Boolean function: the directions along which the derivative is constant.

RecursiveReduction

The trace of recursively symmetry-breaking an object down to its incompressible core.

SampledCensus

A sampled census of the Boolean-function space on n variables, for n too large to enumerate.

SboxProfile

The cryptographic structural profile of an S-box.

SboxSpectra

The affine-invariant spectra of an S-box: the fingerprints for classification up to affine equivalence.

SeparableDecomposition

A direct-sum decomposition f = constant ⊕ ⊕ᵢ fᵢ(x_{Bᵢ}) over independent variable blocks.

StructuralBound

A certified statement that F is described by an orbit-representative set plus automorphism generators — with all three description lengths, the group-entropy, and a self-contained decode witness. StructuralBound::verify re-derives F, rep, and the generators from the three descriptors and confirms the generators are automorphisms and that expanding rep by the group they generate reproduces F exactly.

StructureCover

A cover of the cube by structural class: the ANF degree stratification of a Boolean function. Every function is a XOR of monomials ∏_{i∈S} xᵢ, and each monomial is a structural class — its degree |S| is the order of variable interaction it encodes. Peeling low-degree slices (constant, linear, quadratic, …) covers most of the 2ⁿ corners with a handful of terms; what remains is the residue: the high-degree core no lower-order slice explains. This is why the peel is more efficient than walking the cube corner by corner — each class-slice accounts for many corners at once, and you reason about the small residue directly instead of labeling all 2ⁿ of them.

StructureReport

The verdict of the hypercube structure finder: the tightest structural class, its description size in bits, and how that compares to the raw 2ⁿ-bit truth table.

VariableSymmetry

The variable-permutation symmetry of a Boolean function: a certified subgroup G ≤ Aut(f) and the input-orbit compression it induces.

Enums

CompressibilityClass

The compressibility class of an input, read off the winning description-menu generator.

CryptoStrength

The algorithmic-information verdict on key or ciphertext material (a byte string).

CubeStructure

The compressibility class of a Boolean function on the hypercube, tightest description first. Each variant carries a re-checkable witness (CubeStructure::reconstruct) except the residue.

Descriptor

The description language. Each variant is a program in a fixed language whose length is the description bound and whose execution (decode) reproduces the object.

LinearShortcut

The honest verdict on whether F admits a linear (GF(2)) symmetry shortcut — the certified, re-checkable “no shortcut of this class” answer the dispatcher and diagnostics can report instead of silently spinning a symmetry search. Class-relative (linear/parity), with the Chaitin ceiling as the documented frame: we certify the linear structure exactly, never claim an absolute bound.

Refusal

Why a lower-bound certificate was not issued — the documented refusal that makes the Chaitin ceiling operational. A refusal is never a claim that no bound exists; it is an honest “this is beyond what I can re-check within budget.”

RsaAuditVerdict

The verdict of throwing the ENTIRE arsenal at an RSA public key.

RsaStrength

The structural-security verdict on an RSA modulus.

SboxVerdict

The structural-security verdict on an S-box — the vectorial analogue of rsa_full_audit. It flags only PROVABLE weaknesses (an exact linear relation, a deterministic difference, a quadratic system); a clean profile is the honest ceiling, “no structural weakness of these classes,” never a proof of security (the Chaitin frame in the symmetric world).

StructureTree

A recursive structural decomposition of a Boolean function: the fixed point of the deep finder.

Constants

GROUP_DECODER_OVERHEAD

The fixed byte cost of the group-expansion decoder (“take rep, apply the group generated by gens, output the union”). A documented constant so the inequality K̄(F) ≤ K̄(rep) + K̄(gens) + O(1) is concrete.

Functions

affine_reduce

Peel a linear form off a Boolean function so its complement linear structures become invariances, then reduce. Catches f = h ⊕ ℓ where ℓ is linear and h collapses — the residue-plus-a-linear-form class every other axis misses. Fail-closed: returns Some only if the reconstruction re-checks exactly. None when there are no complement structures (pure invariance is reduce_by_invariance’s job).

affine_signature

Compute the affine-equivalence signature of a Boolean function from its Walsh spectrum. None if truth.len() is not a power of two.

algebraic_attack_on_bytes

Run the algebraic attack on data (its LSB-first bit expansion) at maximal ANF degree max_degree, searching register orders 1..=max_order: return the shortest low-degree nonlinear feedback that regenerates the whole bit stream, with its sparse ANF. None when no degree-≤max_degree register up to max_order fits — the genuine high-degree / incompressible residue (a real cipher’s keystream, the Chaitin ceiling). max_order bounds the cost: the solve is O(rows · M²/64) with M = O(Lᵈ).

algebraic_filter_attack

Recover the initial state of a filter generator (a length-L LFSR with feedback taps filtered by filter_truth) via the algebraic attack — the certified break of a target the correlation and Walsh rungs only glimpse statistically. See [describe::algebraic_filter_attack]. Returns the secret initial state (verified by regeneration) or None.

algebraic_immunity_of

The algebraic-immunity profile of a Boolean function given as its 2ⁿ truth table. Low immunity is a certified structural weakness: a degree-AI annihilator turns each keystream bit of a filter generator using C into a degree-AI equation in the secret state (algebraic_filter_attack). Maximal immunity (AI = ⌈n/2⌉) is the ceiling — no low-degree relation to exploit. None for a malformed table.

assess_key_material

Assess key/ciphertext bytes: Weak (with a re-checkable compression witness — the concrete attack) when the engine describes the data in fewer bytes than storing it raw, else IncompressibleInClass.

attack_shrinking_generator

Break a shrinking (clock-controlled) generator: recover both register states from the output alone by guessing the clock register and linear-solving the data register. Reaches a generator whose output is a data-dependent decimation — not a fixed function of any register’s own past — that no feedback, correlation, algebraic, or linear rung can touch. See [describe::attack_shrinking_generator].

boolean_function_census

Exhaustively classify every Boolean function on n variables by the deep finder’s winning axis. None for n = 0 or n > 4 (beyond 2^{2⁴} = 65536 functions the space is astronomically large). The residue count is the concrete, countable face of the Chaitin ceiling: it is a growing fraction of the space as n rises — structured functions are 2^{poly}, the space is 2^{2ⁿ}.

boomerang_uniformity

The boomerang uniformity of an S-box permutation — the third cryptanalytic pillar after differential and linear. BCT[a][b] = #{x : S⁻¹(S(x)⊕b) ⊕ S⁻¹(S(x⊕a)⊕b) = a}; the uniformity is the maximum over a≠0, b≠0 and measures resistance to the boomerang attack (lower is stronger; 2 is optimal, attained exactly by APN permutations). None if sbox is not a permutation.

census

Census a corpus of bit sequences through the lens_report portfolio: tally what each lens covers and what lands in the uncovered residue.

certified_incompressible_function_exists

A kernel-re-checkable counting certificate that an incompressible Boolean function on n variables MUST exist. A function is its 2ⁿ-bit truth table, and there are only 2^{2ⁿ} − 1 programs shorter than 2ⁿ bits — too few to name all 2^{2ⁿ} functions — so at least one has no shorter description. This is the certified REASON the census residue is nonempty: boolean_function_census measures it, counting guarantees it. Any such function necessarily sits in the residue (no arsenal compresses the truly incompressible). None for n = 0 or n > 6 (a 2⁷-bit truth table overflows the exact-u128 counting range). Re-check with crate::pigeonhole::check_counting_cert.

certify_linear_rigidity

Certify the linear (GF(2)) rigidity of F under the standard budget — None on any refusal (no parity structure, or over budget). See certify_linear_rigidity_within for the documented refusal.

certify_linear_rigidity_within

Certify the linear (GF(2)) rigidity of F, failing closed to budget: a system that exceeds the budget’s Gaussian cap returns Refusal::OverBudgetGaussian — the operational Chaitin ceiling — rather than a certificate we could not re-check.

certify_linear_structure

Certify the GF(2) linear structure of F at any scale via the incremental engine, or None if there is no parity structure to characterize.

check_linear_rigidity

Re-check a LinearRigidityCert against F, trusting nothing the producer computed: re-extract the parity system, independently recompute its kernel, and confirm the certificate’s basis is a genuine, independent, complete null-space of the recovered rows.

check_linear_structure

Re-check a LinearStructureCert by re-extracting F’s parity system, re-reducing it, and confirming the certificate’s rank, kernel dimension, and equation count are exactly reproduced.

classify_bytes

Classify a byte string by its compressibility class and degree.

classify_int_seq

Classify an integer sequence (numeric data, not bytes) by its compressibility class, measured against the plain varint encoding — so a linear recurrence (Fibonacci-class) is recognized as a closed-form Generated program even though it grows past byte range.

classify_text

Classify a text string by the compressibility class of its UTF-8 bytes.

exhaustive_coverage

Exhaustively census EVERY length-len bit sequence (2^len of them): what fraction of the WHOLE space does the lens arsenal cover? The answer is a small sliver — most sequences are incompressible, the residue — which is the concrete, countable face of the Chaitin ceiling. The structured families our lenses catch are real and important, but they are a vanishing fraction of the space; you cannot arrange lenses to cover it all (counting forbids it), and you cannot even certify which points are uncovered (Chaitin forbids that). len ≤ ~18 to stay tractable.

fast_correlation_attack

Fast correlation attack (Meier–Staffelbach): recover a leaking LFSR’s initial state from a noisy keystream by DECODING the register-as-linear-code, in time polynomial in L — where the exhaustive correlation attack (scan_for_combiner_leaks, Rung E) needs O(2^L). This is what scales the correlation break to the register lengths real ciphers use. See [describe::fast_correlation_attack].

find_structure

Walk the hypercube of a Boolean function (its 2ⁿ truth table) and return the tightest structural class that describes it, with the achieved description size and a re-checkable witness. Every lens is a traversal of the cube along one axis of structure (coordinate edges, Walsh butterfly, weight shells, Möbius butterfly); the finder reports whichever yields the shortest description, or the residue (CubeStructure::ResistedArsenal) when none beats storing the table raw. None if truth.len() is not a power of two.

find_structure_deep

Run every structural axis and return the globally tightest description of a Boolean function. None if truth.len() is not a power of two.

gf256_word_complexity

The GF(2⁸) word linear complexity of a byte string — the length of the shortest byte-oriented (GF(256)) LFSR that generates it, via Berlekamp–Massey over the AES field. The word analogue of the bit linear complexity: low relative to n/2 ⇒ a word-LFSR keystream, a certified weakness. (Runs in O(n²) byte-ops — 64× fewer than the bit-level BM on the same data.)

incompressibility_gate

The SAT-dispatcher gate: Some(cert) iff F’s parity structure is fully exposed AND F is provably rigid (|Aut| = 1), so the symmetry arsenal is provably useless and the solver may go straight to CDCL with an honest “no shortcut of this class” verdict. The exact rigidity check (symmetry_entropy_bits == 0) is size-gated — past [GATE_SYMMETRY_MAX_VARS] the gate declines rather than run the superpolynomial automorphism search (there is no cheap sound global-asymmetry test; it is graph-isomorphism-hard). Fail-closed throughout: any doubt returns None and the arsenal runs as usual.

incompressibility_ratio

The incompressibility ratio K̄(x)/n for an n-byte string — the shortest menu description measured against storing the bytes raw (the incompressible size for byte material). ≈ 1.0 ⇒ incompressible (no exploitable structure of this class); well below 1.0 ⇒ compressible (a short, predictable description exists).

incompressible_string_exists

The incompressibility lemma for length n, as a re-checkable counting certificate: 2ⁿ strings (pigeons) against 2ⁿ − 1 shorter programs (holes) ⇒ an incompressible string exists. None only when n is out of the exact-u128 range (1 ≤ n ≤ 127). Re-check with crate::pigeonhole::check_counting_cert.

kolmogorov_bound

Compute a certified Kolmogorov upper bound for a Boolean function via its recursive structure decomposition. None if truth.len() is not a power of two.

lens_report

The auto-lens-finder: run every sequence lens in the arsenal against bits and report which one compresses it (covers it) and by how much — or that none do, placing it in the incompressible residue. This makes the covering explicit: each structured family is caught by its own lens, and a cryptographically-random sequence falls through all of them (the ceiling). Lenses are ordered cheapest-first so a covered sequence is recognized quickly.

linear_cryptanalysis

The linear-cryptanalysis profile of a combining/filter function given as its 2ⁿ truth table: the whole Walsh spectrum distilled into the best linear approximation, its nonlinearity, and its correlation-immunity order. Where scan_for_combiner_leaks (Rung E) reads only weight-1 masks, this reads them ALL — surfacing the multi-register approximation (mask_weight ≥ 2) that E is blind to, even on a first-order correlation-immune function. None for a malformed table.

linear_shortcut_verdict

Decide the linear-shortcut verdict for F (fail-closed via certify_linear_structure).

linear_structures

Detect the linear space V(f) of a Boolean function from its autocorrelation. None if truth.len() is not a power of two.

maximal_order_complexity_of_bytes

The maximal order complexity of a byte string (its LSB-first bit expansion) — the length of the shortest feedback register, LINEAR OR NONLINEAR, generating it. The TOP of the FSR hierarchy: it catches nonlinear generators (NFSRs, algebraic combiners) that fool every linear-complexity measure. Low relative to the bit count ⇒ a short-register generator. This is the last cheap rung — a general nonlinear feedback function is a full truth table (as large as the data), so a low MOC is a certified STRUCTURAL weakness (a short register exists) even though recovering its sparse form is the (hard) algebraic attack. For a real cipher MOC ≈ n/2: the incompressible residue, the Chaitin ceiling.

recursive_reduce

Recursively symmetry-break an object until nothing reduces it further. Each level applies the compression lens (the MDL description menu) and recurses on the DESCRIPTION — each compression is a symmetry break, and its output becomes the next object. The recursion terminates at the FIXED POINT: the point where no lens shrinks it, the incompressible core.

reduce_by_invariance

Peel the invariance subspace off a Boolean function: quotient out every direction a with f(x⊕a) = f(x) and return the smaller function on the surviving coordinates, together with the invariance basis that certifies it. None when the invariance subspace is trivial (nothing to reduce).

rsa_full_audit

Throw the entire arsenal at an RSA public key (N, e): the structural factoring suite (small factor / close primes / smooth p−1 / Pollard rho), Wiener’s small-exponent attack, and the compressibility classifier on the modulus bytes. This is the pre-release safety gate — if any of our own mathematics broke RSA, this is where it would surface. ResistsFullArsenal is the honest ceiling, not a security proof: we certify weakness whenever structure exists and can never certify its absence.

rsa_structural_audit

Audit an RSA modulus with the full structural factoring arsenal (see crate::factor): return a certified factorization if any structural weakness exists, else the soundness verdict — the number-theoretic incompressible residue. Uses the default triage budget.

sampled_boolean_census

Estimate the coverage map at n variables (where 2^{2ⁿ} is unenumerable) from a uniform random sample of samples functions, classified by the deep finder’s winning axis. None for n = 0 or n > 12. The residue fraction climbs toward 1 as n grows — the asymptotic form of the exhaustive census, and the whole thesis: structured functions vanish and almost every function is incompressible.

sbox_full_audit

Audit an S-box with the full structural arsenal — differential, linear, algebraic, and boomerang — and return the first provable weakness, else the honest ceiling with the measured profile. None if the table length is not a power of two. Threshold-free: it never fabricates a “weak” verdict from an arbitrary cutoff, only from a structure that is exact.

sbox_profile

Profile an S-box S : {0,1}ⁿ → {0,1}ᵐ given as its output table (sbox[x] = S(x), out_bits = m): differential uniformity, linearity, minimum component degree, and the affine/bijective/APN flags. None if the table length is not a power of two.

sbox_spectra

The affine-equivalence fingerprint of an S-box: its differential and linear spectra. Two S-boxes that are affine-equivalent (S′(x) = B·S(A·x⊕a)⊕c for invertible A,B) share both spectra, so a difference in either certifies inequivalence — the necessary test at the heart of S-box classification. None if the table length is not a power of two.

scan_for_combiner_leaks

Scan a byte keystream against a menu of candidate LFSR feedback tap-sets: return every register the keystream correlates with beyond significance × the spurious floor. Each hit is a certified break of a nonlinear combiner generator — a HIDDEN constituent register recovered independently (Siegenthaler divide-and-conquer), collapsing a 2^(Σ Lⱼ) search to Σ 2^Lⱼ. This reaches the combiners the algebraic-recurrence rung structurally cannot (their output is a function of the hidden register outputs, not of the keystream’s own past). Empty ⇒ no first-order correlation with any candidate: correlation-immune, or not this combiner — the ceiling, where higher-order and fast-correlation attacks take over.

separable_decomposition

Decompose a Boolean function into its independent direct-sum blocks (the connected components of its ANF interaction graph). None if truth.len() is not a power of two.

structural_bound

Build the structural bound for F under a set of candidate generators. Returns None if any generator is not an automorphism, or if rep + generators does not reconstruct F (so we never issue a certificate we could not re-check).

structure_cover

Peel the cube apart by structural class and examine the residue: return the ANF degree stratification of a Boolean function (its 2ⁿ truth table). Each degree is a slice of structure; the top nonempty degree is the residue — the interaction order that survives every lower-order peel, and the honest answer to what remains and why. None if truth.len() is not a power of two.

structure_tree

Recursively decompose a Boolean function to the fixed point of the deep finder: peel the tightest axis, then re-run on the smaller function(s) it exposes, until a coordinate leaf or the residue. None if truth.len() is not a power of two.

two_adic_complexity_of_bytes

The 2-adic complexity of a byte string (its LSB-first bit expansion) — the size of the shortest FCSR (feedback-with-carry / add-with-carry) generating it. Low relative to the bit count ⇒ a carry-based keystream that fools every linear-complexity test (Berlekamp–Massey over any field sees high complexity; the carry is nonlinear over GF(2)). The certified weakness the linear tools miss.

variable_symmetry

Find the variable-permutation symmetry group of a Boolean function: test every transposition and the cyclic shift, certify the subgroup they generate with Schreier–Sims, and compress by input-orbits. None if truth.len() is not a power of two.