Theorem B.3 — position sum satisfies uniform pumping but is not CCRA-computable
OpenCopylessCRA.Supplement.theorem_B_3algebraic-groupscost-register-automatap2o-gran-per-chapterp2o-plan-paperp2o-v1rational-seriesweighted-automata
On a bit word , let
This position-sum function satisfies the complete uniform pumping condition over the finitely generated subsemiring with the uniform exponent : for every words , the sequence
is -generable and every degree coefficient sum of its exponential-polynomial representation belongs to . Nevertheless, no CCRA over computes .
This separates the necessary uniform pumping condition from CCRA recognizability.
Differences from the source:
- encoding: bits, , generable sequences and exponential-polynomial coefficient sums are given operational Lean definitions →
Boolencodes , the subsemiring is generated by and , and finite sums/products and distinct nonzero bases are explicit; reason: these choices implement exactly the definitions restated on pp.15–16 without changing an instance
Preamble
import Mathlib import Definitions.Def_CopylessCRA_Supplement_UniformPumping
Formal statement
namespace CopylessCRA namespace Supplement /-- Zeng--Cao--Dai--Wang--Ding, *Copyless Cost Register Automata and Algebraic Groups*, STOC 2027 submission (manuscript sha256 434d3094...), Theorem B.3, p.15 (PDF p.17), proof p.16 (PDF p.18). The position sum satisfies the complete uniform pumping condition over the finitely generated subsemiring `ℤ[1/2]` with the one exponent `m = 1`, independent of all context words, but no CCRA over `ℚ` computes it. **Formalization Note** Boolean `false/true` encode the bits `0/1`, positions start at one, and `UniformPumping` includes both `R`-generability and every exponential-polynomial coefficient-sum condition. -/ theorem theorem_B_3 : UniformPumping dyadicSemiring 1 positionSum ∧ ¬ C1 positionSum := by sorry end Supplement end CopylessCRA
Source
Zeng–Cao–Dai–Wang–Ding, Copyless Cost Register Automata and Algebraic Groups, STOC 2027 submission (manuscript sha256 434d3094df2665371c402d5b5291b3c7f3a27a0d79384e4a8ec3ca3a46a92543), Theorem B.3, p.15 (PDF p.17); proof p.16 (PDF p.18)