AFTD Auto-Formalizing Theoretical Domains

derangements_no_two_cycles_quotient_ge_factorial

theoremverifiedformalization

For every natural number n ≥ 3, the quotient derangements_no_two_cycles_quotient n is at least (n - 3)!.

Statement

theorem derangements_no_two_cycles_quotient_ge_factorial (n : ℕ) (hn : 3 ≤ n) : (n - 3).factorial ≤ derangements_no_two_cycles_quotient n
Formalizes
scout/2610-40342-a-p-adic-valuation-calculus-for-permutations-with-restricte.md:1633
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • derangements_no_two_cycles_quotientFor a natural number n, derangements_no_two_cycles_quotient n is the quotient of the number of derangements of Fin n without 2-cycles…
  • derangements_no_two_cycles_countFor a natural number n, derangements_no_two_cycles_count n is the number of permutations of Fin n that have no cycles of length 1 and no…

Read back from the Lean

For every natural number $n$ such that $3 \le n$, $(n - 3)!$ is less than or equal to $\lfloor D_n / ((n - 1)(n - 2)) \rfloor$ (using natural number division), where $D_n$ is the number of permutations of $\{0, \dots, n-1\}$ that have no fixed points (1-cycles) and no 2-cycles.

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 lower-bounds the count of derangements without 2-cycles by the number of full n-cycles in the symmetric group on n elements. Every n-cycle acts transitively on all n elements, so its only cycle has length n; since n ≥ 3, this length is neither 1 nor 2, meaning every n-cycle has neither fixed points nor 2-cycles. There are (n - 1)! such n-cycles, which factors as (n - 1)(n - 2)(n - 3)!. Dividing this lower bound by the positive divisor (n - 1)(n - 2) gives the required lower bound (n - 3)! on the quotient.

  1. The number of permutations of Fin n consisting of a single n-cycle is (n - 1)!.

    Since n ≥ 3 ≥ 2, the number of permutations of Fin n with a single cycle of length n is given by (n - 1)! * (card(Fin n) choose n). Because card(Fin n) = n and (n choose n) = 1, this simplifies directly to (n - 1)!.

    lines 3–5

    uses le_trans, Equiv.Perm.card_of_cycleType_singleton, Fintype.card_fin, Nat.choose_self, mul_one

      have hn2 : 2 ≤ n := le_trans (by decide) hn
      have h_card := Equiv.Perm.card_of_cycleType_singleton (α := Fin n) (n := n) hn2 (by simp)
      simp only [Fintype.card_fin, Nat.choose_self, mul_one] at h_card
  2. Every n-cycle on Fin n is a derangement with no 2-cycles.

    Let σ be a permutation whose cycle type is the singleton {n}. Having a single cycle means σ is a cycle whose support has cardinality n, which equals the total number of elements in Fin n, so the support is the entire universe. Thus, every element x is moved by σ and belongs to the same cycle as any other element y. Therefore, the cycle of x consists of all n elements of Fin n. Since n ≥ 3, the cycle length n is neither 1 nor 2, which proves that σ has no fixed points and no 2-cycles.

    lines 6–32

    uses Finset.mem_filter, Finset.mem_univ, true_and, Equiv.Perm.card_cycleType_eq_one, Equiv.Perm.sum_cycleType, Finset.eq_univ_of_card, Fintype.card_fin, Equiv.Perm.mem_support, Finset.card_univ, Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff

      have h_sub : ({g : Equiv.Perm (Fin n) | g.cycleType = {n}} : Finset (Equiv.Perm (Fin n))) ⊆
          ({σ : Equiv.Perm (Fin n) | ∀ (x : Fin n),
            ({y : Fin n | σ.SameCycle x y} : Finset (Fin n)).card ∉ (({1, 2} : Finset ℕ) : Set ℕ)} : Finset (Equiv.Perm (Fin n))) := by
        intro σ hσ
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hσ ⊢
        have hcyc : σ.IsCycle := by
          rw [← Equiv.Perm.card_cycleType_eq_one, hσ]
          rfl
        have hsupp : σ.support.card = n := by
          rw [← Equiv.Perm.sum_cycleType, hσ]
          rfl
        have hsupp_univ : σ.support = Finset.univ := by
          apply Finset.eq_univ_of_card
          rw [hsupp, Fintype.card_fin]
        intro x
        have hx : x ∈ σ.support := by rw [hsupp_univ]; exact Finset.mem_univ x
        have h_same : ∀ y : Fin n, σ.SameCycle x y := by
          intro y
          have hy : y ∈ σ.support := by rw [hsupp_univ]; exact Finset.mem_univ y
          rw [Equiv.Perm.mem_support] at hx hy
          exact hcyc.sameCycle hx hy
        have h_filt : ({y : Fin n | σ.SameCycle x y} : Finset (Fin n)) = Finset.univ := by
          ext y
          simp [h_same y]
        rw [h_filt, Finset.card_univ, Fintype.card_fin]
        simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff]
        omega
  3. The number of derangements without 2-cycles on Fin n is at least (n - 1)!.

    Since the set of n-cycles is a subset of the permutations with no 1-cycles and no 2-cycles, its cardinality (n - 1)! is bounded above by the cardinality of the latter set, derangements_no_two_cycles_count n.

    lines 33–35

    uses Finset.card_le_card

      have h_le := Finset.card_le_card h_sub
      rw [h_card] at h_le
      change (n - 1).factorial ≤ derangements_no_two_cycles_count n at h_le
  4. The factorial identity (n - 1)! = (n - 1) * (n - 2) * (n - 3)! holds.

    Using 3 ≤ n, write n = 3 + k. Then (n - 1)! is (k + 2)!, which unfolds twice via (m + 1)! = (m + 1) * m! into (k + 2) * (k + 1) * k!. Expressing k back in terms of n gives (n - 1) * (n - 2) * (n - 3)!.

    lines 36–44

    uses Nat.exists_eq_add_of_le, Nat.factorial_succ

      have h_fact : (n - 1).factorial = (n - 1) * (n - 2) * (n - 3).factorial := by
        obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_le hn
        have h1 : 3 + k - 1 = k + 2 := by omega
        have h2 : 3 + k - 2 = k + 1 := by omega
        have h3 : 3 + k - 3 = k := by omega
        rw [h1, h2, h3]
        rw [Nat.factorial_succ (k + 1), Nat.factorial_succ k]
        ring
      rw [h_fact] at h_le
  5. The product (n - 1) * (n - 2) is strictly positive.

    Because n ≥ 3, both n - 1 and n - 2 are strictly positive, and therefore their product is strictly positive.

    lines 45–48

      have h_pos : 0 < (n - 1) * (n - 2) := by
        have : 0 < n - 1 := by omega
        have : 0 < n - 2 := by omega
        positivity
  6. (n - 3)! ≤ derangements_no_two_cycles_quotient n.

    By definition, the quotient is the integer division of derangements_no_two_cycles_count n by (n - 1) * (n - 2). Because this divisor is strictly positive, the inequality (n - 3)! ≤ count / ((n - 1) * (n - 2)) is equivalent to (n - 3)! * (n - 1) * (n - 2) ≤ count, which matches the established lower bound (n - 1) * (n - 2) * (n - 3)! ≤ count after commuting factors.

    lines 49–52

    uses Nat.le_div_iff_mul_le, mul_comm

      dsimp [derangements_no_two_cycles_quotient]
      rw [Nat.le_div_iff_mul_le h_pos]
      rw [mul_comm]
      exact h_le
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Equiv.Perm.card_of_cycleType_singleton
The number of permutations of a finite set α whose cycle type is a single cycle of length n is (n - 1)! * (|α| choose n).
Fintype.card_fin
The cardinality of Fin n = {0, ..., n - 1} is n.
Nat.choose_self
The binomial coefficient n choose n is equal to 1.
mul_one
Multiplying any element by 1 leaves it unchanged: a * 1 = a.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the filtering predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset univ.
true_and
The proposition True ∧ p is equivalent to p.
Equiv.Perm.card_cycleType_eq_one
A permutation is a single non-trivial cycle if and only if its cycle type multiset has cardinality 1.
Equiv.Perm.sum_cycleType
The sum of the lengths of the disjoint cycles in a permutation equals the cardinality of its support.
Finset.eq_univ_of_card
A subset of a finite type whose cardinality equals the cardinality of the type is the entire universe.
Equiv.Perm.mem_support
An element is in the support of a permutation if and only if it is not fixed by the permutation.
Finset.card_univ
The cardinality of the universal finset is the cardinality of the underlying finite type.
Finset.coe_insert
Coercing the insertion of an element into a finset to a set yields the set-theoretic insertion.
Finset.coe_singleton
Coercing a singleton finset to a set yields the singleton set.
Set.mem_insert_iff
An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff
An element belongs to the singleton set {b} if and only if it equals b.
Finset.card_le_card
If a finite set s is a subset of t, then |s| ≤ |t|.
Nat.exists_eq_add_of_le
If m ≤ n, then n = m + k for some natural number k.
Nat.factorial_succ
The factorial of n + 1 equals (n + 1) * n!.
Nat.le_div_iff_mul_le
For k > 0, x ≤ y / k in natural division if and only if x * k ≤ y.
mul_comm
Multiplication is commutative: a * b = b * a.

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

/-- Factorial lower bound on the quotient: Q_n ≥ (n - 3)! for n ≥ 3. -/theorem derangements_no_two_cycles_quotient_ge_factorial (n : ℕ) (hn : 3 ≤ n) : (n - 3).factorial ≤ derangements_no_two_cycles_quotient n := by  have hn2 : 2 ≤ n := le_trans (by decide) hn  have h_card := Equiv.Perm.card_of_cycleType_singleton (α := Fin n) (n := n) hn2 (by simp)  simp only [Fintype.card_fin, Nat.choose_self, mul_one] at h_card  have h_sub : ({g : Equiv.Perm (Fin n) | g.cycleType = {n}} : Finset (Equiv.Perm (Fin n))) ⊆      ({σ : Equiv.Perm (Fin n) | ∀ (x : Fin n),        ({y : Fin n | σ.SameCycle x y} : Finset (Fin n)).card ∉ (({1, 2} : Finset ℕ) : Set ℕ)} : Finset (Equiv.Perm (Fin n))) := by    intro σ hσ    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hσ ⊢    have hcyc : σ.IsCycle := by      rw [← Equiv.Perm.card_cycleType_eq_one, hσ]      rfl    have hsupp : σ.support.card = n := by      rw [← Equiv.Perm.sum_cycleType, hσ]      rfl    have hsupp_univ : σ.support = Finset.univ := by      apply Finset.eq_univ_of_card      rw [hsupp, Fintype.card_fin]    intro x    have hx : x ∈ σ.support := by rw [hsupp_univ]; exact Finset.mem_univ x    have h_same : ∀ y : Fin n, σ.SameCycle x y := by      intro y      have hy : y ∈ σ.support := by rw [hsupp_univ]; exact Finset.mem_univ y      rw [Equiv.Perm.mem_support] at hx hy      exact hcyc.sameCycle hx hy    have h_filt : ({y : Fin n | σ.SameCycle x y} : Finset (Fin n)) = Finset.univ := by      ext y      simp [h_same y]    rw [h_filt, Finset.card_univ, Fintype.card_fin]    simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff]    omega  have h_le := Finset.card_le_card h_sub  rw [h_card] at h_le  change (n - 1).factorial ≤ derangements_no_two_cycles_count n at h_le  have h_fact : (n - 1).factorial = (n - 1) * (n - 2) * (n - 3).factorial := by    obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_le hn    have h1 : 3 + k - 1 = k + 2 := by omega    have h2 : 3 + k - 2 = k + 1 := by omega    have h3 : 3 + k - 3 = k := by omega    rw [h1, h2, h3]    rw [Nat.factorial_succ (k + 1), Nat.factorial_succ k]    ring  rw [h_fact] at h_le  have h_pos : 0 < (n - 1) * (n - 2) := by    have : 0 < n - 1 := by omega    have : 0 < n - 2 := by omega    positivity  dsimp [derangements_no_two_cycles_quotient]  rw [Nat.le_div_iff_mul_le h_pos]  rw [mul_comm]  exact h_le
See it in the graphDiscuss this resultChallenge it