AFTD Auto-Formalizing Theoretical Domains

cyclic_permutation_subtraction_set_ne_nil

theoremverified

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

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

    lines 5–8

    uses Finset.mem_insert, Finset.mem_singleton

      intro w hw
      simp only [cyclic_permutation_subtraction_set, Finset.mem_insert, Finset.mem_singleton] at hw
      intro h
      rcases hw with rfl | rfl
  2. 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.

    lines 9–15

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

    lines 16–22

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

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

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