AFTD Auto-Formalizing Theoretical Domains

is_two_regular_of_submodule_stable

theoremverified

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).

  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.

    lines 7–10

      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
  2. 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.

    lines 11–17

        · 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
  3. 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).

    lines 18–27

    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
  4. 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).

    lines 28–40

    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
  5. 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`.

    lines 41–44

    uses Submodule.span_le

      apply 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.

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

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