Position sum, -generable sequences and the uniform pumping condition
DefinitionCopylessCRA_Supplement_UniformPumpingalgebraic-groupscost-register-automatap2o-gran-per-chapterp2o-plan-paperp2o-v1rational-seriesweighted-automata
For a bit word , the position sum is
Given a subsemiring , an -generable sequence is obtained from constants in , the sequence , exponentials , and geometric sums by finite pointwise sums and products. An exponential-polynomial representation has distinct nonzero bases and coefficient sums .
The uniform pumping condition at requires, for every context words and pumped word , that be -generable and have every in . The module also defines as the subsemiring generated by and .
Formalization Note Boolean values encode bits and , and word positions start at one.
Definition code
import Mathlib
import Definitions.Def_CopylessCRA_CCRA
namespace CopylessCRA
namespace Supplement
/-- The position-sum function of display (1): on `b_1 ... b_j`, return
`sum_{i=1}^j i b_i`. -/
def positionSumFrom : ℕ -> List Bool -> ℚ
| _, [] => 0
| i, b :: w => (if b then (i : ℚ) else 0) + positionSumFrom (i + 1) w
/-- The position sum starts its positions at one. -/
def positionSum (w : List Bool) : ℚ := positionSumFrom 1 w
/-- A word repeated `k` times by concatenation. -/
def repeatWord {alpha : Type*} (w : List alpha) : ℕ -> List alpha
| 0 => []
| k + 1 => w ++ repeatWord w k
/-- The subsemiring `ℤ[1/2]` used in Theorem B.3, generated as a subsemiring of `ℚ` by `-1` and
`1/2`. -/
def dyadicSemiring : Subsemiring ℚ :=
Subsemiring.closure ({(-1 : ℚ), (1 / 2 : ℚ)} : Set ℚ)
/-- An `R`-generable sequence: the least family containing constants from `R`, `n`, exponentials
`alpha^n`, and geometric sums, and closed under finite pointwise sums and products. -/
inductive IsGenerable (R : Subsemiring ℚ) : (ℕ -> ℚ) -> Prop
| const (c : ℚ) (hc : c ∈ R) : IsGenerable R (fun _ => c)
| nat : IsGenerable R (fun n => (n : ℚ))
| pow (alpha : ℚ) (ha : alpha ∈ R) : IsGenerable R (fun n => alpha ^ n)
| geom (alpha : ℚ) (ha : alpha ∈ R) (hne : alpha ≠ 1) :
IsGenerable R (fun n => ∑ i ∈ Finset.range n, alpha ^ i)
| add {s t : ℕ -> ℚ} : IsGenerable R s -> IsGenerable R t ->
IsGenerable R (fun n => s n + t n)
| mul {s t : ℕ -> ℚ} : IsGenerable R s -> IsGenerable R t ->
IsGenerable R (fun n => s n * t n)
/-- A finite exponential-polynomial representation
`s(n) = sum_lambda p_lambda(n) lambda^n` with distinct nonzero bases. -/
structure ExpPolyRepresentation (s : ℕ -> ℚ) where
bases : Finset ℚ
bases_nonzero : forall lambda, lambda ∈ bases -> lambda ≠ 0
coeff : ℚ -> Polynomial ℚ
represents : forall n, s n = ∑ lambda ∈ bases, Polynomial.eval (n : ℚ) (coeff lambda) * lambda ^ n
/-- The degree-`j` coefficient sum `S_j = sum_lambda a_{lambda,j}`. -/
def ExpPolyRepresentation.coefficientSum {s : ℕ -> ℚ} (E : ExpPolyRepresentation s)
(j : ℕ) : ℚ :=
∑ lambda ∈ E.bases, (E.coeff lambda).coeff j
/-- The full uniform pumping condition: one exponent `m >= 1`, independent of `u,w,v`, such that
the shifted pumping sequence is `R`-generable and admits an exponential-polynomial form whose
every coefficient sum belongs to `R`. -/
def UniformPumping {alpha : Type*} (R : Subsemiring ℚ) (m : ℕ)
(f : List alpha -> ℚ) : Prop :=
0 < m ∧ forall u w v : List alpha,
let s : ℕ -> ℚ := fun n => f (u ++ repeatWord w (m * (n + 1)) ++ v)
IsGenerable R s ∧ exists E : ExpPolyRepresentation s,
forall j, E.coefficientSum j ∈ R
end Supplement
end CopylessCRA
Source
Zeng–Cao–Dai–Wang–Ding, Copyless Cost Register Automata and Algebraic Groups, STOC 2027 submission (manuscript sha256 434d3094df2665371c402d5b5291b3c7f3a27a0d79384e4a8ec3ca3a46a92543), §B.1 and Theorem B.3, p.15 (PDF p.17); proof p.16 (PDF p.18)