AFTD Auto-Formalizing Theoretical Domains

not_prefix_reversal_sum_bound_necessary

theoremverifiedoriginal

The statement prefix_reversal_sum_bound_necessary is false: The statement claims that m + k ≥ n + 1 is a necessary condition for prefix reversals of lengths k, m, n to generate S_n. However, for (k, m, n) = (2, 3, 5), the prefix reversals of lengths 2, 3, 5 generate the entire symmetric group S_5 (order 120), yet m + k = 5 < 6 = n + 1. Further counterexamples include (k, m, n) = (2, 4, 7), (3, 4, 7), (2, 5, 7), (2, 7, 9), (4, 6, 11), (5, 6, 11), (4, 7, 11), (3, 8, 11), (2, 9, 11).

Statement

theorem not_prefix_reversal_sum_bound_necessary : ¬ (∀ (k m n : ℕ)
    (hk : 2 ≤ k) (hkm : k < m) (hmn : m < n)
    (hgen : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = ⊤), m + k ≥ n + 1)
Related work
refutes `prefix_reversal_sum_bound_necessary`
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • prefixReversalFor integers n and k, prefixReversal n k is the permutation in the symmetric group Equiv.Perm (Fin n) that reverses the first k elements…

The proof, explained

The theorem refutes the claim that m + k ≥ n + 1 is a necessary condition for prefix reversals of lengths k, m, n to generate S_n by producing the counterexample (k, m, n) = (2, 3, 5). It shows that the prefix reversals of lengths 2, 3, and 5 generate the entire symmetric group S_5 by explicitly expressing every adjacent transposition as a word in the three generators. Since S_5 is generated yet 3 + 2 = 5 < 6 = 5 + 1, the asserted necessity condition fails.

  1. Assume for contradiction that m + k ≥ n + 1 is a necessary condition for prefix reversals of lengths k, m, n to generate S_n.

    We introduce the assumed universal statement h, which asserts that whenever 2 ≤ k < m < n and the prefix reversals of lengths k, m, and n generate S_n, the sum inequality m + k ≥ n + 1 must hold.

    line 4

      intro h
  2. The prefix reversals of lengths 2, 3, and 5 belong to the subgroup they generate in S_5.

    To disprove the claim, we construct the counterexample (k, m, n) = (2, 3, 5). We begin proving that these three prefix reversals generate the entire symmetric group S_5 (goal `g5_eq_top`). As immediate premises, each of the three generating reversals belongs to their subgroup closure by `Subgroup.subset_closure`.

    lines 5–12

    uses Subgroup.subset_closure

      have g5_eq_top : Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} = (⊤ : Subgroup (Equiv.Perm (Fin 5))) := by
        open Equiv Perm in
        have ha : prefixReversal 5 2 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} :=
          Subgroup.subset_closure (by simp)
        have hb : prefixReversal 5 3 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} :=
          Subgroup.subset_closure (by simp)
        have hc : prefixReversal 5 5 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} :=
          Subgroup.subset_closure (by simp)
  3. All four adjacent transpositions (0 1), (1 2), (2 3), and (3 4) belong to the subgroup generated by the prefix reversals of lengths 2, 3, and 5.

    Each adjacent transposition is explicitly decomposed into products of the generators: (0 1) is the reversal of length 2; (1 2) is the conjugate (2)(3)(2); (2 3) is the conjugate (5)((2)(3)(2))(5); and (3 4) is (5)(2)(5). Each identity between permutations of 5 elements is verified by finite evaluation (`decide`), and subgroup closure under multiplication (`Subgroup.mul_mem`) establishes that each transposition belongs to the subgroup.

    lines 13–27

    uses Subgroup.mul_mem

        have ht0 : swap 0 1 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by
          have : prefixReversal 5 2 = swap 0 1 := by decide
          rwa [← this]
        have ht1 : swap 1 2 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by
          have : prefixReversal 5 2 * prefixReversal 5 3 * prefixReversal 5 2 = swap 1 2 := by decide
          rw [← this]
          exact Subgroup.mul_mem _ (Subgroup.mul_mem _ ha hb) ha
        have ht2 : swap 2 3 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by
          have : prefixReversal 5 5 * (prefixReversal 5 2 * prefixReversal 5 3 * prefixReversal 5 2) * prefixReversal 5 5 = swap 2 3 := by decide
          rw [← this]
          exact Subgroup.mul_mem _ (Subgroup.mul_mem _ hc (Subgroup.mul_mem _ (Subgroup.mul_mem _ ha hb) ha)) hc
        have ht3 : swap 3 4 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by
          have : prefixReversal 5 5 * prefixReversal 5 2 * prefixReversal 5 5 = swap 3 4 := by decide
          rw [← this]
          exact Subgroup.mul_mem _ (Subgroup.mul_mem _ hc ha) hc
  4. Every adjacent transposition (i i+1) for i < 4 belongs to the submonoid underlying the generated subgroup.

    Given an arbitrary adjacent transposition (i i+1) with i < 4, case analysis on i ∈ {0, 1, 2, 3} (`interval_cases`) matches each case with one of the four adjacent transpositions verified in the previous step.

    lines 28–36

        have hrange : Set.range (fun i : Fin 4 => swap i.castSucc i.succ) ⊆
            ((Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5}).toSubmonoid : Set (Perm (Fin 5))) := by
          intro x hx
          rcases hx with ⟨⟨i, hi⟩, rfl⟩
          interval_cases i
          · exact ht0
          · exact ht1
          · exact ht2
          · exact ht3
  5. The subgroup generated by prefix reversals of lengths 2, 3, and 5 is the full symmetric group S_5.

    Because adjacent transpositions generate the full symmetric group as a monoid (`mclosure_swap_castSucc_succ`), the fact that every adjacent transposition is contained in the underlying submonoid implies that the submonoid is top (`Submonoid.closure_le`, `eq_top_iff`). Passing between subgroup and submonoid membership (`Subgroup.mem_toSubmonoid`) and applying extensionality (`ext`) yields that the generated subgroup is all of S_5.

    lines 37–41

    uses eq_top_iff, mclosure_swap_castSucc_succ, Submonoid.closure_le, Subgroup.mem_toSubmonoid

        have htopM : (Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5}).toSubmonoid = ⊤ := by
          rw [eq_top_iff, ← mclosure_swap_castSucc_succ 4, Submonoid.closure_le]
          exact hrange
        ext x
        simp [← Subgroup.mem_toSubmonoid, htopM]
  6. Contradiction: the sum bound fails for (k, m, n) = (2, 3, 5).

    Instantiating the assumption h with k = 2, m = 3, and n = 5 alongside the fact that they generate S_5 produces the inequality 3 + 2 ≥ 5 + 1 (i.e. 5 ≥ 6). Linear integer arithmetic (`omega`) deduces False, completing the proof.

    lines 42–43

      have hfalse := h 2 3 5 (by omega) (by omega) (by omega) g5_eq_top
      omega
Subgroup.subset_closure
Any subset of a group is contained in the subgroup generated by that subset.
Subgroup.mul_mem
If two elements belong to a subgroup, their product also belongs to the subgroup.
eq_top_iff
An element in a preordered type with a top element ⊤ equals ⊤ if and only if it is greater than or equal to ⊤.
mclosure_swap_castSucc_succ
The submonoid generated by all adjacent transpositions on n + 1 elements is the entire symmetric group.
Submonoid.closure_le
The submonoid generated by a set s is contained in a submonoid S if and only if s is a subset of S.
Subgroup.mem_toSubmonoid
An element belongs to a subgroup if and only if it belongs to its underlying submonoid.

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

theorem not_prefix_reversal_sum_bound_necessary : ¬ (∀ (k m n : ℕ)    (hk : 2 ≤ k) (hkm : k < m) (hmn : m < n)    (hgen : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = ⊤), m + k ≥ n + 1) := by  intro h  have g5_eq_top : Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} = (⊤ : Subgroup (Equiv.Perm (Fin 5))) := by    open Equiv Perm in    have ha : prefixReversal 5 2 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} :=      Subgroup.subset_closure (by simp)    have hb : prefixReversal 5 3 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} :=      Subgroup.subset_closure (by simp)    have hc : prefixReversal 5 5 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} :=      Subgroup.subset_closure (by simp)    have ht0 : swap 0 1 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by      have : prefixReversal 5 2 = swap 0 1 := by decide      rwa [← this]    have ht1 : swap 1 2 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by      have : prefixReversal 5 2 * prefixReversal 5 3 * prefixReversal 5 2 = swap 1 2 := by decide      rw [← this]      exact Subgroup.mul_mem _ (Subgroup.mul_mem _ ha hb) ha    have ht2 : swap 2 3 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by      have : prefixReversal 5 5 * (prefixReversal 5 2 * prefixReversal 5 3 * prefixReversal 5 2) * prefixReversal 5 5 = swap 2 3 := by decide      rw [← this]      exact Subgroup.mul_mem _ (Subgroup.mul_mem _ hc (Subgroup.mul_mem _ (Subgroup.mul_mem _ ha hb) ha)) hc    have ht3 : swap 3 4 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by      have : prefixReversal 5 5 * prefixReversal 5 2 * prefixReversal 5 5 = swap 3 4 := by decide      rw [← this]      exact Subgroup.mul_mem _ (Subgroup.mul_mem _ hc ha) hc    have hrange : Set.range (fun i : Fin 4 => swap i.castSucc i.succ) ⊆        ((Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5}).toSubmonoid : Set (Perm (Fin 5))) := by      intro x hx      rcases hx with ⟨⟨i, hi⟩, rfl⟩      interval_cases i      · exact ht0      · exact ht1      · exact ht2      · exact ht3    have htopM : (Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5}).toSubmonoid = ⊤ := by      rw [eq_top_iff, ← mclosure_swap_castSucc_succ 4, Submonoid.closure_le]      exact hrange    ext x    simp [← Subgroup.mem_toSubmonoid, htopM]  have hfalse := h 2 3 5 (by omega) (by omega) (by omega) g5_eq_top  omega
See it in the graphDiscuss this resultChallenge it