AFTD Auto-Formalizing Theoretical Domains

prefix_reversal_necessary_conditions_not_sufficient

theoremverifiedformalization

It is not the case that for all natural numbers 2 ≤ k < m < n satisfying 2 * m > n, at least one of k, m, n even, at least one of k, m, n congruent to 2 or 3 mod 4, gcd(gcd(k, m), n) = 1, m + k ≥ n + 1, and gcd(n - m, n - k) = 1, the three prefix reversals of lengths k, m, n generate the full symmetric group Equiv.Perm (Fin n).

Statement

theorem prefix_reversal_necessary_conditions_not_sufficient :
    ¬ (∀ (k m n : ℕ),
        2 ≤ k → k < m → m < n →
        2 * m > n →
        (Even k ∨ Even m ∨ Even n) →
        (k % 4 = 2 ∨ k % 4 = 3 ∨ m % 4 = 2 ∨ m % 4 = 3 ∨ n % 4 = 2 ∨ n % 4 = 3) →
        Nat.gcd (Nat.gcd k m) n = 1 →
        m + k ≥ n + 1 →
        Nat.gcd (n - m) (n - k) = 1 →
        Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = (⊤ : Subgroup (Equiv.Perm (Fin n))))
Formalizes
arXiv:2610.30892 after Lemma 3.2
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • prefix_reversal_six_five_three_not_topIn the symmetric group Equiv.Perm (Fin 6), the subgroup generated by the three prefix reversals of lengths 3, 5, and 6 does not equal the…

Read back from the Lean

It is not the case that for all natural numbers $k, m, n$, the following implication holds: If 1. $2 \le k$, 2. $k < m$, 3. $m < n$, 4. $2 \cdot m > n$, 5. at least one of $k, m, n$ is even, 6. at least one of $k, m, n$ is congruent to $2$ or $3$ modulo $4$, 7. $\gcd(\gcd(k, m), n) = 1$, 8. $m + k \ge n + 1$, and 9. $\gcd(n - m, n - k) = 1$, then the subgroup of $\operatorname{Equiv.Perm}(\operatorname{Fin} n)$ generated by the three permutations $\{\operatorname{prefixReversal}(n, k), \operatorname{prefixReversal}(n, m), \operatorname{prefixReversal}(n, n)\}$ is the entire symmetric group $\top$.

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 exhibiting a concrete counterexample. Assuming for contradiction that the given conditions are sufficient to generate the full symmetric group, the claim is instantiated at $(k, m, n) = (3, 5, 6)$. All ordering constraints and arithmetic conditions hold by simple computation, but the generated subgroup is already known not to be the full symmetric group by `prefix_reversal_six_five_three_not_top`, yielding a contradiction.

  1. Assume for contradiction that the six necessary conditions are collectively sufficient to guarantee generation of the full symmetric group.

    We introduce the universal hypothesis $h$, which asserts that any triple of natural numbers $(k, m, n)$ satisfying the ordering bounds and the six specified necessary conditions generates the entire permutation group $\operatorname{Equiv.Perm}(\operatorname{Fin} n)$.

    line 12

      intro h
  2. Contradiction: the triple $(k, m, n) = (3, 5, 6)$ satisfies all conditions, yet its prefix reversals do not generate the full symmetric group.

    We instantiate the universal hypothesis $h$ with $k = 3$, $m = 5$, and $n = 6$. All nine antecedent conditions are checked by direct numerical computation: $2 \le 3$, $3 < 5$, $5 < 6$, $2 \cdot 5 > 6$, $6$ is even, $3 \equiv 3 \pmod 4$, $\gcd(\gcd(3, 5), 6) = 1$, $5 + 3 \ge 6 + 1$, and $\gcd(6 - 5, 6 - 3) = \gcd(1, 3) = 1$. The hypothesis therefore asserts that these three prefix reversals generate the top subgroup $\top$ of $\operatorname{Equiv.Perm}(\operatorname{Fin} 6)$, which contradicts `prefix_reversal_six_five_three_not_top`.

    lines 13–15

    uses prefix_reversal_six_five_three_not_top

      exact prefix_reversal_six_five_three_not_top
        (h 3 5 6 (by norm_num) (by norm_num) (by norm_num) (by norm_num)
          (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num))
prefix_reversal_six_five_three_not_top
The subgroup generated by the prefix reversals of lengths 3, 5, and 6 on 6 elements is not the full symmetric group on Fin 6.

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

/-- The six necessary conditions for generation by three prefix reversals are not collectively sufficient. -/theorem prefix_reversal_necessary_conditions_not_sufficient :    ¬ (∀ (k m n : ℕ),        2 ≤ k → k < m → m < n →        2 * m > n →        (Even k ∨ Even m ∨ Even n) →        (k % 4 = 2 ∨ k % 4 = 3 ∨ m % 4 = 2 ∨ m % 4 = 3 ∨ n % 4 = 2 ∨ n % 4 = 3) →        Nat.gcd (Nat.gcd k m) n = 1 →        m + k ≥ n + 1 →        Nat.gcd (n - m) (n - k) = 1 →        Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = (⊤ : Subgroup (Equiv.Perm (Fin n)))) := by  intro h  exact prefix_reversal_six_five_three_not_top    (h 3 5 6 (by norm_num) (by norm_num) (by norm_num) (by norm_num)      (by norm_num) (by norm_num) (by norm_num) (by norm_num) (by norm_num))
See it in the graphDiscuss this resultChallenge it