seeded_subtraction_seq_eventually_periodic
For every integer $a \ge 1$ and every binary initial seed of length $2a + 1$, the generated subtraction sequence is eventually periodic.
Statement
theorem seeded_subtraction_seq_eventually_periodic (a : ℕ) (ha : 1 ≤ a)
(seed : Fin (2 * a + 1) → Bool) :
∃ p : ℕ, is_eventual_period (seeded_subtraction_seq a seed) p- Formalizes
- knowledgebase, OP-1251
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- seeded_subtraction_seqThe binary sequence defined recursively from a seed of length $2a + 1$, where the first $2a + 1$ values are given by the seed, and each…
- is_eventual_periodA positive integer $p$ is an eventual period of a sequence $w : \mathbb{N} \to \text{Bool}$ if there exists $N \in \mathbb{N}$ such that…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
For every natural number $a$ such that $1 \le a$, and for every initial sequence $\text{seed} : \text{Fin}(2a + 1) \to \text{Bool}$, there exists a natural number $p$ such that $p$ is an eventual period of the sequence $\text{seeded\_subtraction\_seq}(a, \text{seed})$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by viewing the subtraction sequence through a sliding window of length 2a + 1, which serves as a finite state space of size 2^(2a+1). Because each term of the sequence is determined by the values at delays a, 2a, and 2a + 1, the next window is a deterministic transition of the current window. By the Pigeonhole Principle, iterates of this transition function on the finite state space must eventually repeat a state, yielding a strictly positive period p. Evaluating the first coordinate of the periodic sequence of windows proves that the subtraction sequence itself is eventually periodic.
Definition of the transition operator on state blocks of length 2a + 1.
A state block is a function from {0, ..., 2a} to Bool. The step operator shifts entries left by mapping index i to i + 1 whenever i + 1 < 2a + 1, and for the boundary index 2a, computes the next value using the game rule as ¬b(a + 1) ∨ ¬b(1) ∨ ¬b(0). The arithmetic tactic omega confirms that a + 1, 1, and 0 are all strictly less than 2a + 1 when a ≥ 1.
private def seeded_subtraction_seq_eventually_periodic_step (a : ℕ) (ha : 1 ≤ a) : (Fin (2 * a + 1) → Bool) → (Fin (2 * a + 1) → Bool) := fun b i => if h : (i : ℕ) + 1 < 2 * a + 1 then b ⟨(i : ℕ) + 1, h⟩ else !b ⟨a + 1, by omega⟩ || !b ⟨1, by omega⟩ || !b ⟨0, by omega⟩
Definition of the state block sequence and recurrence for n ≥ 2a + 1.
The state block at index n is defined as the slice B_n(i) = s(n + i) for i ∈ {0, ..., 2a}. For n ≥ 2a + 1 and a ≠ 0, the lemma seeded_subtraction_seq_eventually_periodic_rec confirms that s(n) = ¬s(n - a) ∨ ¬s(n - 2a) ∨ ¬s(n - (2a + 1)) by unfolding seeded_subtraction_seq.eq_def and dismissing the initial branch conditions with dif_neg.
uses
seeded_subtraction_seq.eq_def,dif_negprivate def seeded_subtraction_seq_eventually_periodic_block (a : ℕ) (seed : Fin (2 * a + 1) → Bool) (n : ℕ) : Fin (2 * a + 1) → Bool := fun i => seeded_subtraction_seq a seed (n + i.val) private lemma seeded_subtraction_seq_eventually_periodic_rec (a : ℕ) (seed : Fin (2 * a + 1) → Bool) (ha : a ≠ 0) (n : ℕ) (hn : 2 * a + 1 ≤ n) : seeded_subtraction_seq a seed n = (!seeded_subtraction_seq a seed (n - a) || !seeded_subtraction_seq a seed (n - 2 * a) || !seeded_subtraction_seq a seed (n - (2 * a + 1))) := by rw [seeded_subtraction_seq.eq_def] dsimp only rw [dif_neg (by omega : ¬ n < 2 * a + 1), dif_neg ha]
For indices below 2a + 1, the sequence matches the initial seed.
Unfolding the definition using seeded_subtraction_seq.eq_def and taking the true branch of the condition i < 2a + 1 via dif_pos shows that s(i) = seed(i).
uses
seeded_subtraction_seq.eq_def,dif_posprivate lemma seeded_subtraction_seq_eventually_periodic_initial (a : ℕ) (seed : Fin (2 * a + 1) → Bool) (i : Fin (2 * a + 1)) : seeded_subtraction_seq a seed i.val = seed i := by rw [seeded_subtraction_seq.eq_def] simp only [show i.val < 2 * a + 1 from i.isLt, dif_pos]
The block at index 0 equals the initial seed.
By function extensionality on index i, the definition of the block gives s(0 + i), which simplifies to s(i) by Nat.zero_add and equals seed(i) by seeded_subtraction_seq_eventually_periodic_initial.
uses
seeded_subtraction_seq_eventually_periodic_block,Nat.zero_add,seeded_subtraction_seq_eventually_periodic_initialprivate lemma seeded_subtraction_seq_eventually_periodic_block_zero (a : ℕ) (seed : Fin (2 * a + 1) → Bool) : seeded_subtraction_seq_eventually_periodic_block a seed 0 = seed := by funext i simp only [seeded_subtraction_seq_eventually_periodic_block, Nat.zero_add] exact seeded_subtraction_seq_eventually_periodic_initial a seed i
The block at index n + 1 equals the step operator applied to the block at index n.
By function extensionality, we evaluate both sides at index i and case split on whether i + 1 < 2a + 1. In the positive case, the block value s(n + 1 + i) = s(n + (i + 1)) matches the shifted value of B_n via dif_pos. In the negative case, i must be 2a, so s(n + 1 + 2a) = s(n + (2a + 1)) expands via the recurrence seeded_subtraction_seq_eventually_periodic_rec into ¬s(n + a + 1) ∨ ¬s(n + 1) ∨ ¬s(n), which matches the step operator's boundary computation via dif_neg.
uses
seeded_subtraction_seq_eventually_periodic_step,seeded_subtraction_seq_eventually_periodic_block,dif_pos,dif_neg,seeded_subtraction_seq_eventually_periodic_recprivate lemma seeded_subtraction_seq_eventually_periodic_block_succ (a : ℕ) (ha : 1 ≤ a) (seed : Fin (2 * a + 1) → Bool) (n : ℕ) : seeded_subtraction_seq_eventually_periodic_block a seed (n + 1) = seeded_subtraction_seq_eventually_periodic_step a ha (seeded_subtraction_seq_eventually_periodic_block a seed n) := by funext i simp only [seeded_subtraction_seq_eventually_periodic_step, seeded_subtraction_seq_eventually_periodic_block] by_cases h : (i : ℕ) + 1 < 2 * a + 1 · rw [dif_pos h] rw [show n + 1 + (i : ℕ) = n + ((i : ℕ) + 1) from by omega] · rw [dif_neg h] have hi : (i : ℕ) = 2 * a := by have := i.isLt; omega rw [hi] rw [show n + 1 + 2 * a = n + (2 * a + 1) from by omega] rw [seeded_subtraction_seq_eventually_periodic_rec a seed (by omega) (n + (2 * a + 1)) (by omega)] rw [show n + (2 * a + 1) - a = n + (a + 1) from by omega, show n + (2 * a + 1) - 2 * a = n + 1 from by omega, show n + (2 * a + 1) - (2 * a + 1) = n + 0 from by omega]
The block at index n is the n-th iterate of the step operator applied to the seed.
By induction on n: the base case n = 0 reduces to the identity by Function.iterate_zero and id_eq, matching B_0 = seed from seeded_subtraction_seq_eventually_periodic_block_zero. The inductive step rewrites B_(n+1) to step(B_n) via seeded_subtraction_seq_eventually_periodic_block_succ, applies the inductive hypothesis, and rewrites with Function.iterate_succ_apply'.
uses
Function.iterate_zero,id_eq,seeded_subtraction_seq_eventually_periodic_block_zero,seeded_subtraction_seq_eventually_periodic_block_succ,Function.iterate_succ_apply'private lemma seeded_subtraction_seq_eventually_periodic_block_iterate (a : ℕ) (ha : 1 ≤ a) (seed : Fin (2 * a + 1) → Bool) (n : ℕ) : seeded_subtraction_seq_eventually_periodic_block a seed n = (seeded_subtraction_seq_eventually_periodic_step a ha)^[n] seed := by induction n with | zero => rw [Function.iterate_zero, id_eq] exact seeded_subtraction_seq_eventually_periodic_block_zero a seed | succ n ih => rw [seeded_subtraction_seq_eventually_periodic_block_succ a ha seed n, ih, Function.iterate_succ_apply']
Any map on a finite set has two iterates that collide, producing a positive period.
For any map f on a finite type of size N = |α|, consider the N + 1 iterates f^[k](x) for k ∈ {0, ..., N}. By the Pigeonhole Principle (Fintype.exists_ne_map_eq_of_card_lt), two distinct indices x_0 ≠ y_0 produce the same iterate. Ordering them with lt_or_gt_of_ne gives i < j with f^[i](x) = f^[j](x), providing a strictly positive candidate period p = j - i > 0.
uses
Fintype.card,Fintype.exists_ne_map_eq_of_card_lt,lt_or_gt_of_neprivate lemma seeded_subtraction_seq_eventually_periodic_finite_orbit {α : Type*} [Fintype α] (f : α → α) (x : α) : ∃ p N : ℕ, 0 < p ∧ ∀ n ≥ N, f^[n + p] x = f^[n] x := by classical let N := Fintype.card α let g : Fin (N + 1) → α := fun k => f^[k.val] x have hcard : Fintype.card α < Fintype.card (Fin (N + 1)) := by simp [N] obtain ⟨x0, y0, hne, heq⟩ := Fintype.exists_ne_map_eq_of_card_lt g hcard obtain ⟨i, j, hij, hper⟩ : ∃ i j : ℕ, i < j ∧ f^[i] x = f^[j] x := by rcases lt_or_gt_of_ne hne with hlt | hgt · exact ⟨x0.val, y0.val, hlt, heq⟩ · exact ⟨y0.val, x0.val, hgt, heq.symm⟩ refine ⟨j - i, i, by omega, ?_⟩
The collision propagates to all subsequent steps: f^[n + p](x) = f^[n](x) for all n ≥ i.
Induction on k shows that f^[i + k](x) = f^[i + k + (j - i)](x) for all k ≥ 0: the base case k = 0 is the collision f^[i](x) = f^[j](x), and the inductive step applies f to both sides using Function.iterate_succ_apply'. For any n ≥ i, writing n = i + (n - i) and evaluating the claim at k = n - i proves the periodicity.
uses
Function.iterate_succ_apply'have hij' : i + (j - i) = j := by omega have hclaim : ∀ k : ℕ, f^[i + k] x = f^[i + k + (j - i)] x := by intro k induction k with | zero => simpa [hij'] using hper | succ k ih => have h1 : i + (k + 1) = i + k + 1 := by omega have h2 : i + k + 1 + (j - i) = i + k + (j - i) + 1 := by omega rw [h1, h2, Function.iterate_succ_apply', Function.iterate_succ_apply', ih] intro n hn have hn' : n = i + (n - i) := by omega rw [hn'] exact (hclaim (n - i)).symm
The block sequence has an eventual period p > 0 starting at some threshold N.
Since the state space Fin (2 * a + 1) → Bool is finite, applying seeded_subtraction_seq_eventually_periodic_finite_orbit to the step operator and the initial seed provides a period p > 0 and a threshold N such that step^[n + p](seed) = step^[n](seed) for all n ≥ N.
uses
seeded_subtraction_seq_eventually_periodic_finite_orbit,seeded_subtraction_seq_eventually_periodic_step/-- Every seed generates an eventually periodic binary sequence in the {a, 2a, 2a+1} subtraction game. -/ theorem seeded_subtraction_seq_eventually_periodic (a : ℕ) (ha : 1 ≤ a) (seed : Fin (2 * a + 1) → Bool) : ∃ p : ℕ, is_eventual_period (seeded_subtraction_seq a seed) p := by obtain ⟨p, N, hp, hN⟩ := seeded_subtraction_seq_eventually_periodic_finite_orbit (seeded_subtraction_seq_eventually_periodic_step a ha) seed refine ⟨p, hp, N, ?_⟩ intro n hn
The subtraction sequence s(n) is eventually periodic with period p.
Evaluating the state blocks at the initial index z = 0 yields s(n + p) = B_(n+p)(0) and s(n) = B_n(0) by definition of the block. By seeded_subtraction_seq_eventually_periodic_block_iterate, these blocks equal the iterates step^[n + p](seed) and step^[n](seed), which are equal for all n ≥ N. Therefore s(n + p) = s(n) for all n ≥ N.
uses
seeded_subtraction_seq_eventually_periodic_block_iterate,seeded_subtraction_seq_eventually_periodic_blocklet z : Fin (2 * a + 1) := ⟨0, by omega⟩ have key : (seeded_subtraction_seq_eventually_periodic_step a ha)^[n + p] seed = (seeded_subtraction_seq_eventually_periodic_step a ha)^[n] seed := hN n hn have hb : seeded_subtraction_seq_eventually_periodic_block a seed n = (seeded_subtraction_seq_eventually_periodic_step a ha)^[n] seed := seeded_subtraction_seq_eventually_periodic_block_iterate a ha seed n have hbp : seeded_subtraction_seq_eventually_periodic_block a seed (n + p) = (seeded_subtraction_seq_eventually_periodic_step a ha)^[n + p] seed := seeded_subtraction_seq_eventually_periodic_block_iterate a ha seed (n + p) calc seeded_subtraction_seq a seed (n + p) = (seeded_subtraction_seq_eventually_periodic_block a seed (n + p)) z := by simp [seeded_subtraction_seq_eventually_periodic_block, z] _ = ((seeded_subtraction_seq_eventually_periodic_step a ha)^[n + p] seed) z := by rw [hbp] _ = ((seeded_subtraction_seq_eventually_periodic_step a ha)^[n] seed) z := by rw [key] _ = (seeded_subtraction_seq_eventually_periodic_block a seed n) z := by rw [hb] _ = seeded_subtraction_seq a seed n := by simp [seeded_subtraction_seq_eventually_periodic_block, z]
seeded_subtraction_seq.eq_def- Unfolds the recursive definition of the subtraction sequence: returns the seed value if the index is less than 2a + 1, and otherwise evaluates the disjunction of the negations of the sequence values at offsets a, 2a, and 2a + 1.
dif_neg- A dependent if-then-else expression evaluates to its else branch when the condition is false.
dif_pos- A dependent if-then-else expression evaluates to its then branch when the condition is true.
seeded_subtraction_seq_eventually_periodic_block- Packages 2a + 1 consecutive terms of the subtraction sequence starting at index n into a state vector.
Nat.zero_add- For any natural number n, 0 + n = n.
seeded_subtraction_seq_eventually_periodic_initial- For any index i < 2a + 1, the subtraction sequence evaluated at index i equals the initial seed at i.
seeded_subtraction_seq_eventually_periodic_step- The transition operator that updates a state block of length 2a + 1 by shifting entries left and computing the new rightmost entry via the subtraction game rule.
seeded_subtraction_seq_eventually_periodic_rec- For n ≥ 2a + 1 and a ≠ 0, the sequence value s(n) is the disjunction of the negations of s(n - a), s(n - 2a), and s(n - (2a + 1)).
Function.iterate_zero- The 0-th iterate of any function is the identity function.
id_eq- The identity function satisfies id(x) = x.
seeded_subtraction_seq_eventually_periodic_block_zero- The state block at index 0 is equal to the initial seed.
seeded_subtraction_seq_eventually_periodic_block_succ- The state block at index n + 1 equals the step transition function applied to the state block at index n.
Function.iterate_succ_apply'- The (n + 1)-st iterate of a function satisfies f^[n + 1](x) = f(f^[n](x)).
Fintype.card- The cardinality of a finite type as a natural number.
Fintype.exists_ne_map_eq_of_card_lt- The Pigeonhole Principle: any map from a finite set to a strictly smaller finite set maps two distinct elements to the same value.
lt_or_gt_of_ne- If two elements of a linearly ordered set are unequal, then one is strictly less than the other.
seeded_subtraction_seq_eventually_periodic_finite_orbit- Any map on a finite set has an eventually periodic orbit starting from any point.
seeded_subtraction_seq_eventually_periodic_block_iterate- The state block at index n equals the n-th iterate of the step function applied to the seed.
- The $(2a + 1)$-term sliding window of the subtraction sequence is formalized as a function from the finite index type Fin (2 * a + 1) to Bool, with linear arithmetic (omega) verifying that all lookback indices remain within bounds.
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.
private def seeded_subtraction_seq_eventually_periodic_step (a : ℕ) (ha : 1 ≤ a) : (Fin (2 * a + 1) → Bool) → (Fin (2 * a + 1) → Bool) := fun b i => if h : (i : ℕ) + 1 < 2 * a + 1 then b ⟨(i : ℕ) + 1, h⟩ else !b ⟨a + 1, by omega⟩ || !b ⟨1, by omega⟩ || !b ⟨0, by omega⟩private def seeded_subtraction_seq_eventually_periodic_block (a : ℕ) (seed : Fin (2 * a + 1) → Bool) (n : ℕ) : Fin (2 * a + 1) → Bool := fun i => seeded_subtraction_seq a seed (n + i.val)private lemma seeded_subtraction_seq_eventually_periodic_rec (a : ℕ) (seed : Fin (2 * a + 1) → Bool) (ha : a ≠ 0) (n : ℕ) (hn : 2 * a + 1 ≤ n) : seeded_subtraction_seq a seed n = (!seeded_subtraction_seq a seed (n - a) || !seeded_subtraction_seq a seed (n - 2 * a) || !seeded_subtraction_seq a seed (n - (2 * a + 1))) := by rw [seeded_subtraction_seq.eq_def] dsimp only rw [dif_neg (by omega : ¬ n < 2 * a + 1), dif_neg ha]private lemma seeded_subtraction_seq_eventually_periodic_initial (a : ℕ) (seed : Fin (2 * a + 1) → Bool) (i : Fin (2 * a + 1)) : seeded_subtraction_seq a seed i.val = seed i := by rw [seeded_subtraction_seq.eq_def] simp only [show i.val < 2 * a + 1 from i.isLt, dif_pos]private lemma seeded_subtraction_seq_eventually_periodic_block_zero (a : ℕ) (seed : Fin (2 * a + 1) → Bool) : seeded_subtraction_seq_eventually_periodic_block a seed 0 = seed := by funext i simp only [seeded_subtraction_seq_eventually_periodic_block, Nat.zero_add] exact seeded_subtraction_seq_eventually_periodic_initial a seed iprivate lemma seeded_subtraction_seq_eventually_periodic_block_succ (a : ℕ) (ha : 1 ≤ a) (seed : Fin (2 * a + 1) → Bool) (n : ℕ) : seeded_subtraction_seq_eventually_periodic_block a seed (n + 1) = seeded_subtraction_seq_eventually_periodic_step a ha (seeded_subtraction_seq_eventually_periodic_block a seed n) := by funext i simp only [seeded_subtraction_seq_eventually_periodic_step, seeded_subtraction_seq_eventually_periodic_block] by_cases h : (i : ℕ) + 1 < 2 * a + 1 · rw [dif_pos h] rw [show n + 1 + (i : ℕ) = n + ((i : ℕ) + 1) from by omega] · rw [dif_neg h] have hi : (i : ℕ) = 2 * a := by have := i.isLt; omega rw [hi] rw [show n + 1 + 2 * a = n + (2 * a + 1) from by omega] rw [seeded_subtraction_seq_eventually_periodic_rec a seed (by omega) (n + (2 * a + 1)) (by omega)] rw [show n + (2 * a + 1) - a = n + (a + 1) from by omega, show n + (2 * a + 1) - 2 * a = n + 1 from by omega, show n + (2 * a + 1) - (2 * a + 1) = n + 0 from by omega]private lemma seeded_subtraction_seq_eventually_periodic_block_iterate (a : ℕ) (ha : 1 ≤ a) (seed : Fin (2 * a + 1) → Bool) (n : ℕ) : seeded_subtraction_seq_eventually_periodic_block a seed n = (seeded_subtraction_seq_eventually_periodic_step a ha)^[n] seed := by induction n with | zero => rw [Function.iterate_zero, id_eq] exact seeded_subtraction_seq_eventually_periodic_block_zero a seed | succ n ih => rw [seeded_subtraction_seq_eventually_periodic_block_succ a ha seed n, ih, Function.iterate_succ_apply']private lemma seeded_subtraction_seq_eventually_periodic_finite_orbit {α : Type*} [Fintype α] (f : α → α) (x : α) : ∃ p N : ℕ, 0 < p ∧ ∀ n ≥ N, f^[n + p] x = f^[n] x := by classical let N := Fintype.card α let g : Fin (N + 1) → α := fun k => f^[k.val] x have hcard : Fintype.card α < Fintype.card (Fin (N + 1)) := by simp [N] obtain ⟨x0, y0, hne, heq⟩ := Fintype.exists_ne_map_eq_of_card_lt g hcard obtain ⟨i, j, hij, hper⟩ : ∃ i j : ℕ, i < j ∧ f^[i] x = f^[j] x := by rcases lt_or_gt_of_ne hne with hlt | hgt · exact ⟨x0.val, y0.val, hlt, heq⟩ · exact ⟨y0.val, x0.val, hgt, heq.symm⟩ refine ⟨j - i, i, by omega, ?_⟩ have hij' : i + (j - i) = j := by omega have hclaim : ∀ k : ℕ, f^[i + k] x = f^[i + k + (j - i)] x := by intro k induction k with | zero => simpa [hij'] using hper | succ k ih => have h1 : i + (k + 1) = i + k + 1 := by omega have h2 : i + k + 1 + (j - i) = i + k + (j - i) + 1 := by omega rw [h1, h2, Function.iterate_succ_apply', Function.iterate_succ_apply', ih] intro n hn have hn' : n = i + (n - i) := by omega rw [hn'] exact (hclaim (n - i)).symm/-- Every seed generates an eventually periodic binary sequence in the {a, 2a, 2a+1} subtraction game. -/theorem seeded_subtraction_seq_eventually_periodic (a : ℕ) (ha : 1 ≤ a) (seed : Fin (2 * a + 1) → Bool) : ∃ p : ℕ, is_eventual_period (seeded_subtraction_seq a seed) p := by obtain ⟨p, N, hp, hN⟩ := seeded_subtraction_seq_eventually_periodic_finite_orbit (seeded_subtraction_seq_eventually_periodic_step a ha) seed refine ⟨p, hp, N, ?_⟩ intro n hn let z : Fin (2 * a + 1) := ⟨0, by omega⟩ have key : (seeded_subtraction_seq_eventually_periodic_step a ha)^[n + p] seed = (seeded_subtraction_seq_eventually_periodic_step a ha)^[n] seed := hN n hn have hb : seeded_subtraction_seq_eventually_periodic_block a seed n = (seeded_subtraction_seq_eventually_periodic_step a ha)^[n] seed := seeded_subtraction_seq_eventually_periodic_block_iterate a ha seed n have hbp : seeded_subtraction_seq_eventually_periodic_block a seed (n + p) = (seeded_subtraction_seq_eventually_periodic_step a ha)^[n + p] seed := seeded_subtraction_seq_eventually_periodic_block_iterate a ha seed (n + p) calc seeded_subtraction_seq a seed (n + p) = (seeded_subtraction_seq_eventually_periodic_block a seed (n + p)) z := by simp [seeded_subtraction_seq_eventually_periodic_block, z] _ = ((seeded_subtraction_seq_eventually_periodic_step a ha)^[n + p] seed) z := by rw [hbp] _ = ((seeded_subtraction_seq_eventually_periodic_step a ha)^[n] seed) z := by rw [key] _ = (seeded_subtraction_seq_eventually_periodic_block a seed n) z := by rw [hb] _ = seeded_subtraction_seq a seed n := by simp [seeded_subtraction_seq_eventually_periodic_block, z]