cyclic_permutation_subtraction_set_ne_nil
For natural numbers d, s, a, b with 1 ≤ d, 1 ≤ a, and 1 ≤ b, every word w in the finite set cyclic_permutation_subtraction_set d s a b is nonempty (w ≠ []).
Statement
theorem cyclic_permutation_subtraction_set_ne_nil (d s a b : ℕ)
(hd : 1 ≤ d) (ha : 1 ≤ a) (hb : 1 ≤ b) :
∀ w ∈ cyclic_permutation_subtraction_set d s a b, w ≠ []- Source
- arXiv:2611.09157
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cyclic_permutation_subtraction_setFor natural numbers d, s, a, b, cyclic_permutation_subtraction_set d s a b is the finite set in Finset (List (Fin d)) consisting of the…
Read back from the Lean
For all natural numbers $d$, $s$, $a$, and $b$, assuming $1 \le d$, $1 \le a$, and $1 \le b$, every list $w$ in the finite set cyclic_permutation_subtraction_set d s a b is non-empty ($w \ne []$).
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 proof proceeds by contradiction. By definition, any word in the cyclic permutation subtraction set is obtained by concatenating either a copies of the range ⟨0, …, d - 1⟩, or b copies of that range cyclically rotated by s. In either case, the length of the word is the product of the number of copies (a or b) and the block length d. Because d ≥ 1 and a, b ≥ 1, this product is at least 1, which contradicts the assumption that the word is the empty list (having length 0).
Assuming for contradiction that some element w of the subtraction set is empty, it suffices to derive a contradiction for each of the two words defining the set.
We introduce an arbitrary word w in the cyclic permutation subtraction set and assume for contradiction that w = []. By unfolding the definition of the subtraction set and finite set membership, w must be either the concatenation of a copies of the standard range ⟨0, …, d - 1⟩, or the concatenation of b copies of that range rotated by s. We then perform a case split on these two possibilities.
uses
Finset.mem_insert,Finset.mem_singletonintro w hw simp only [cyclic_permutation_subtraction_set, Finset.mem_insert, Finset.mem_singleton] at hw intro h rcases hw with rfl | rfl
The first candidate word cannot be empty, ruling out the first case.
In the first case, w is the flattened list of a copies of the range of length d. Simplifying with List.length_flatten shows that its length is a * d. However, since w = [], List.length_nil implies its length is 0, so 0 = a * d. Since 1 ≤ a and 1 ≤ d, Nat.mul_le_mul yields 1 ≤ a * d. Linear arithmetic (omega) derives a contradiction from 0 = a * d and 1 ≤ a * d.
uses
List.length_flatten,List.length_nil,Nat.mul_le_mul· have hlen : ((List.replicate a (List.finRange d)).flatten).length = a * d := by simp [List.length_flatten] have hz : ((List.replicate a (List.finRange d)).flatten).length = 0 := by rw [h, List.length_nil] rw [hz] at hlen have : 1 ≤ a * d := Nat.mul_le_mul ha hd omega
The second candidate word cannot be empty, ruling out the second case and completing the proof.
In the second case, w is the flattened list of b copies of the range of length d rotated by s. Because rotation preserves length, simplifying with List.length_flatten gives that its length is b * d. Since w = [], its length must also be 0, so 0 = b * d. Applying Nat.mul_le_mul to 1 ≤ b and 1 ≤ d yields 1 ≤ b * d. Linear arithmetic (omega) derives a contradiction from 0 = b * d and 1 ≤ b * d, concluding the proof.
uses
List.length_flatten,List.length_nil,Nat.mul_le_mul· have hlen : ((List.replicate b ((List.finRange d).rotate s)).flatten).length = b * d := by simp [List.length_flatten] have hz : ((List.replicate b ((List.finRange d).rotate s)).flatten).length = 0 := by rw [h, List.length_nil] rw [hz] at hlen have : 1 ≤ b * d := Nat.mul_le_mul hb hd omega
Finset.mem_insert- An element belongs to the insertion of an element into a finite set if and only if it equals the inserted element or belongs to the set.
Finset.mem_singleton- An element belongs to a singleton set if and only if it equals the unique element of that set.
List.length_flatten- The length of the concatenation (flattening) of a list of lists is the sum of the lengths of the inner lists.
List.length_nil- The empty list has length 0.
Nat.mul_le_mul- Multiplication on natural numbers preserves weak inequalities: if n₁ ≤ n₂ and m₁ ≤ m₂, then n₁ * m₁ ≤ n₂ * m₂.
- In lines 10 and 17, `simp [List.length_flatten]` simplifies the length of the flattened replicated lists directly to `a * d` (and `b * d`) by automatically using auxiliary facts that `List.finRange d` has length `d` and that rotating a list preserves its length.
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.
/-- Words in the cyclic permutation subtraction set are nonempty when d >= 1 and a, b >= 1. -/theorem cyclic_permutation_subtraction_set_ne_nil (d s a b : ℕ) (hd : 1 ≤ d) (ha : 1 ≤ a) (hb : 1 ≤ b) : ∀ w ∈ cyclic_permutation_subtraction_set d s a b, w ≠ [] := by intro w hw simp only [cyclic_permutation_subtraction_set, Finset.mem_insert, Finset.mem_singleton] at hw intro h rcases hw with rfl | rfl · have hlen : ((List.replicate a (List.finRange d)).flatten).length = a * d := by simp [List.length_flatten] have hz : ((List.replicate a (List.finRange d)).flatten).length = 0 := by rw [h, List.length_nil] rw [hz] at hlen have : 1 ≤ a * d := Nat.mul_le_mul ha hd omega · have hlen : ((List.replicate b ((List.finRange d).rotate s)).flatten).length = b * d := by simp [List.length_flatten] have hz : ((List.replicate b ((List.finRange d).rotate s)).flatten).length = 0 := by rw [h, List.length_nil] rw [hz] at hlen have : 1 ≤ b * d := Nat.mul_le_mul hb hd omega