AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it