prefix_reversal_necessary_conditions_not_sufficient
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.
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)$.
intro hContradiction: 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`.
uses
prefix_reversal_six_five_three_not_topexact 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
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.
/-- 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))