is_two_regular_of_submodule_stable
A sequence f : ℕ → ℤ is 2-regular if there exists a finitely generated ℤ-submodule N of ℤ^ℕ containing f that is closed under both decimation operations g ↦ (n ↦ g(2n)) and g ↦ (n ↦ g(2n+1)).
Statement
theorem is_two_regular_of_submodule_stable (f : ℕ → ℤ) (N : Submodule ℤ (ℕ → ℤ)) (hN : N.FG) (hf : f ∈ N) (h0 : ∀ g ∈ N, (fun n => g (2 * n)) ∈ N) (h1 : ∀ g ∈ N, (fun n => g (2 * n + 1)) ∈ N) : is_two_regular f
- Source
- step towards halving_partition_sequence_two_regular
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_two_regularAn integer sequence $f : \mathbb{N} \to \mathbb{Z}$ is 2-regular if the $\mathbb{Z}$-submodule of $\mathbb{Z}^\mathbb{N}$ spanned by its…
The proof, explained
To show that f is 2-regular, it suffices to prove that every 2-decimation sequence n ↦ f(2^e * n + r) (with r < 2^e) is contained in the finitely generated submodule N, since submodules of finitely generated modules over the Noetherian ring ℤ are finitely generated. This decimation containment is proved by induction on the power e, with the base case e = 0 holding because f ∈ N. In the induction step from e to e + 1, the remainder r < 2^(e+1) is split into two cases: if r < 2^e, the decimation is obtained from the induction hypothesis for remainder r via the stability hypothesis h0 (closure under n ↦ 2n); if r ≥ 2^e, it is obtained from the induction hypothesis for remainder r - 2^e via the stability hypothesis h1 (closure under n ↦ 2n + 1).
Unfold the definition of 2-regularity and set up an induction on the exponent e to show that every 2-decimation of f belongs to N.
A sequence f is 2-regular if the submodule spanned by all its 2-decimations n ↦ f(2^e * n + r) (for e, r ∈ ℕ with r < 2^e) is finitely generated. We formulate the auxiliary assertion h_dec that every such decimation sequence lies in N, and begin proving it by induction on e.
dsimp [is_two_regular] have h_dec : ∀ (e : ℕ) (r : ℕ), r < 2 ^ e → (fun n => f (2 ^ e * n + r)) ∈ N := by intro e induction' e with e ih
For the base case e = 0, the only decimation is f itself, which belongs to N.
When e = 0, the condition r < 2^0 = 1 forces r = 0. The sequence n ↦ f(2^0 * n + 0) is identically f, which belongs to N by the hypothesis hf.
· intro r hr have : r = 0 := by omega subst this have : (fun n => f (2 ^ 0 * n + 0)) = f := by funext n; simp rw [this] exact hf
In the induction step from e to e + 1, if r < 2^e, the decimation n ↦ f(2^(e+1) * n + r) belongs to N.
Assuming the induction hypothesis for e, if r < 2^e, the sequence g = (m ↦ f(2^e * m + r)) is in N. Applying hypothesis h0 (closure under decimation by 2n) shows that n ↦ g(2n) = f(2^e * (2n) + r) belongs to N. Rewriting 2^e * 2 = 2^(e+1) via `pow_succ` identifies this with n ↦ f(2^(e+1) * n + r).
uses
pow_succ· intro r hr by_cases hr_lt : r < 2 ^ e · have h_step := h0 (fun n => f (2 ^ e * n + r)) (ih r hr_lt) have heq : (fun n => (fun m => f (2 ^ e * m + r)) (2 * n)) = (fun n => f (2 ^ (e + 1) * n + r)) := by funext n dsimp congr 1 rw [pow_succ] ring rwa [heq] at h_step
In the induction step from e to e + 1, if 2^e ≤ r < 2^(e+1), the decimation n ↦ f(2^(e+1) * n + r) belongs to N.
When r ≥ 2^e, the shifted remainder r' = r - 2^e satisfies r' < 2^e because r < 2^(e+1) = 2 * 2^e. By the induction hypothesis, g = (m ↦ f(2^e * m + r')) is in N. Applying hypothesis h1 (closure under decimation by 2n + 1) shows that n ↦ g(2n + 1) = f(2^e * (2n + 1) + (r - 2^e)) belongs to N. Expanding 2^e * (2n + 1) + (r - 2^e) = 2^(e+1) * n + r using `pow_succ`, `Nat.add_assoc`, and `Nat.add_sub_cancel'` shows this is n ↦ f(2^(e+1) * n + r).
uses
pow_succ,Nat.add_assoc,Nat.add_sub_cancel'· have hr_le : 2 ^ e ≤ r := by omega have hr' : r - 2 ^ e < 2 ^ e := by rw [pow_succ] at hr omega have h_step := h1 (fun n => f (2 ^ e * n + (r - 2 ^ e))) (ih (r - 2 ^ e) hr') have heq : (fun n => (fun m => f (2 ^ e * m + (r - 2 ^ e))) (2 * n + 1)) = (fun n => f (2 ^ (e + 1) * n + r)) := by funext n dsimp congr 1 rw [pow_succ] have h1 : 2 ^ e * (2 * n + 1) = 2 ^ e * 2 * n + 2 ^ e := by ring rw [h1, Nat.add_assoc, Nat.add_sub_cancel' hr_le] rwa [heq] at h_step
The submodule spanned by all 2-decimations of f is contained in N and therefore finitely generated, proving f is 2-regular.
Since ℤ is a Noetherian ring, any submodule of the finitely generated submodule N is itself finitely generated (`hN.of_le`). By `Submodule.span_le`, it suffices to verify that each generating sequence n ↦ f(2^e * n + r) belongs to N, which is precisely the statement established by `h_dec`.
uses
Submodule.span_leapply hN.of_le rw [Submodule.span_le] rintro g ⟨e, r, hr, rfl⟩ exact h_dec e r hr
pow_succ- In any monoid (including (ℕ, *)), a ^ (n + 1) = a ^ n * a.
Nat.add_assoc- Addition of natural numbers is associative: (n + m) + k = n + (m + k).
Nat.add_sub_cancel'- Subtracting and adding back a smaller or equal natural number cancels: if m ≤ n, then m + (n - m) = n.
Submodule.span_le- The submodule spanned by a set s is contained in a submodule p if and only if s is a subset of p.
- The deduction that a submodule of a finitely generated ℤ-module is finitely generated (`hN.of_le`) relies implicitly on the ring ℤ being Noetherian, which Mathlib supplies via typeclass resolution.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- An integer sequence f is 2-regular if there exists a finitely generated ℤ-submodule containing f that is closed under both decimation operations g ↦ (n ↦ g(2n)) and g ↦ (n ↦ g(2n+1)). -/theorem is_two_regular_of_submodule_stable (f : ℕ → ℤ) (N : Submodule ℤ (ℕ → ℤ)) (hN : N.FG) (hf : f ∈ N) (h0 : ∀ g ∈ N, (fun n => g (2 * n)) ∈ N) (h1 : ∀ g ∈ N, (fun n => g (2 * n + 1)) ∈ N) : is_two_regular f := by dsimp [is_two_regular] have h_dec : ∀ (e : ℕ) (r : ℕ), r < 2 ^ e → (fun n => f (2 ^ e * n + r)) ∈ N := by intro e induction' e with e ih · intro r hr have : r = 0 := by omega subst this have : (fun n => f (2 ^ 0 * n + 0)) = f := by funext n; simp rw [this] exact hf · intro r hr by_cases hr_lt : r < 2 ^ e · have h_step := h0 (fun n => f (2 ^ e * n + r)) (ih r hr_lt) have heq : (fun n => (fun m => f (2 ^ e * m + r)) (2 * n)) = (fun n => f (2 ^ (e + 1) * n + r)) := by funext n dsimp congr 1 rw [pow_succ] ring rwa [heq] at h_step · have hr_le : 2 ^ e ≤ r := by omega have hr' : r - 2 ^ e < 2 ^ e := by rw [pow_succ] at hr omega have h_step := h1 (fun n => f (2 ^ e * n + (r - 2 ^ e))) (ih (r - 2 ^ e) hr') have heq : (fun n => (fun m => f (2 ^ e * m + (r - 2 ^ e))) (2 * n + 1)) = (fun n => f (2 ^ (e + 1) * n + r)) := by funext n dsimp congr 1 rw [pow_succ] have h1 : 2 ^ e * (2 * n + 1) = 2 ^ e * 2 * n + 2 ^ e := by ring rw [h1, Nat.add_assoc, Nat.add_sub_cancel' hr_le] rwa [heq] at h_step apply hN.of_le rw [Submodule.span_le] rintro g ⟨e, r, hr, rfl⟩ exact h_dec e r hr