A certificate state for every coprime prime factorization
ProvedCouret.Certificate.factorization_T_certificatecouret-programmecouret-unification-20261108
Write , with residue map taking to , respectively. Let be a word of natural primes with product and . There is a state index whose decoded total is the code of and whose decoded support is exactly the residues of divisors with . Its tabulated output equals both its presence count and its mask output. For every pair of symbols ,
where means that some strict divisor of has the residue represented by symbol . This connects arithmetic factorizations to the explicit finite-state table.
Preamble
import Definitions.Def_Couret_CertificateProofs_3244eb90a0e1 import Std import Theorems.Thm_Couret_Certificate_StepValid_sound import Theorems.Thm_Couret_Certificate_initial_encoding import Theorems.Thm_Couret_Certificate_observation_checked import Theorems.Thm_Couret_Certificate_pairPresent_semantics import Theorems.Thm_Couret_Certificate_symbol_code import Theorems.Thm_Couret_Certificate_transitions_checked import Theorems.Thm_Couret_decode_encode30 import Theorems.Thm_Couret_mod30_run_for_factorization import Theorems.Thm_Couret_mul30_residue import Theorems.Thm_Couret_residue30_injective import Definitions.Def_Couret_CertificateData_653c7a96c17c /-! Universal consequences of the finite certificate checks. -/ set_option maxRecDepth 16384 set_option maxHeartbeats 8000000 namespace Couret namespace Certificate
Formal statement
theorem factorization_T_certificate (w : Word Nat) (hp : w.primeFactors)
(n : Nat) (hn : total natProduct w = n) (hc : Nat.gcd n 30 = 1) (h1 : 1 < n) :
∃ i : StateId,
decoded i = State.active (encode30 n) (strictDivisorResidue n) ∧
tableOutput i = presenceCount (entry i) ∧
tableOutput i = outputMask (entry i) ∧
∀ a b : Symbol, pairPresent (entry i) a b = true ↔ arithmeticPair n a b := by sorry
end Certificate
end Couret
Source
Alexandre Couret, Certified minimal memory for a divisor-residue presence observable modulo 30, https://zenodo.org/records/23989640; archive Couret_BC_MOD30_Companion_20261105.zip, SHA-256 9bb2678164c63a9e47c192093f5ce9deb1b7b74a1f1c8fecc77f305a408266a2; file source/S4/CertificateProofs.lean, lines 188–205; source file SHA-256 34105504de63d99f05e7d3427ba82853380bac1d8c053b618776cd7d98da83b2; theorem Couret.Certificate.factorization_T_certificate