is_two_regular
def
An integer sequence $f : \mathbb{N} \to \mathbb{Z}$ is 2-regular if the $\mathbb{Z}$-submodule of $\mathbb{Z}^\mathbb{N}$ spanned by its 2-kernel $\{n \mapsto f(2^e n + r) : e \ge 0, 0 \le r < 2^e\}$ is finitely generated.
Statement
def is_two_regular (f : ℕ → ℤ) : Prop
- Defined in
- arXiv:2611.01243 Sec. 6; Allouche and Shallit, TCS 1992
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 1
- is_two_regular_of_submodule_stableA sequence f : ℕ → ℤ is 2-regular if there exists a finitely generated ℤ-submodule N of ℤ^ℕ containing f that is closed under both…
Read back from the Lean
For a function f : ℕ → ℤ, is_two_regular f asserts that the ℤ-submodule of ℕ → ℤ spanned by the set of all functions g : ℕ → ℤ for which there exist e, r : ℕ such that r < 2 ^ e and g = fun n => f (2 ^ e * n + r) is finitely generated (Submodule.FG). (This is the standard definition of a 2-regular sequence in the sense of Allouche and Shallit.)
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A sequence f : ℕ → ℤ is 2-regular if the ℤ-submodule spanned by its 2-kernel is finitely generated. -/ def is_two_regular (f : ℕ → ℤ) : Prop := (Submodule.span ℤ { g : ℕ → ℤ | ∃ (e r : ℕ), r < 2 ^ e ∧ g = fun n => f (2 ^ e * n + r) }).FG