AFTD Auto-Formalizing Theoretical Domains

canonical_permutation_avoidance_of_local_lemma

theoremverifiedformalization

For finitely many injective partial assignments on n points, if weights in [0,1) satisfy the asymmetric local-lemma inequalities for the graph connecting assignments with overlapping domains or ranges, some permutation avoids every assignment.

Statement

theorem canonical_permutation_avoidance_of_local_lemma
    {I : Type*} [Fintype I] [DecidableEq I] (n : ℕ) (hn : 0 < n)
    (D : I → Finset (Fin n)) (f : I → Fin n → Fin n)
    (hD : ∀ i, (D i).Nonempty)
    (hf : ∀ i, Set.InjOn (f i) (↑(D i) : Set (Fin n)))
    (x : I → ℝ) (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i < 1)
    (hprob : ∀ i, (1 : ℝ) / (n.descFactorial (D i).card : ℝ) ≤
      x i * ∏ j ∈ Finset.univ.filter (fun j => j ≠ i ∧
        (¬ Disjoint (D i) (D j) ∨
          ¬ Disjoint ((D i).image (f i)) ((D j).image (f j)))), (1 - x j)) :
    ∃ σ : Equiv.Perm (Fin n), ∀ i, ∃ v ∈ D i, σ v ≠ f i v
Formalizes
Using Lovász Local Lemma in the Space of Random Injections, Electronic Journal of Combinatorics 14 (2007), R63, DOI 10.37236/981, Theorem 1 and Lemma 3. Specialization to permutations of Fin n and the domain/range-intersection supergraph of the canonical conflict graph; this is a statement only, not an imported proof.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 3

The proof, explained

The proof applies the counting version of the asymmetric lopsided Lovász Local Lemma (`finite_lopsided_avoidance_of_card_bound`) to the uniform measure on permutations of n points. For each partial assignment, the bad event A_i consists of permutations that agree with the assignment on its entire domain. The key move is using negative dependency (`canonical_permutation_negative_dependency_card_bound`) to show that conditioning on avoiding non-interfering assignments leaves the conditional probability of A_i bounded by 1 / n^{\underline{|D_i|}}. The asymmetric local lemma conditions then guarantee the existence of a permutation avoiding all bad events simultaneously.

  1. Define the bad sets of permutations A_i and the dependency neighborhoods N_i.

    For each index i, let A_i be the set of permutations σ of Fin n that agree with f_i on all points of D_i. Define N(i) to be the set of indices j ≠ i whose domain or range intersects that of i, that is, D_i ∩ D_j ≠ ∅ or f_i(D_i) ∩ f_j(D_j) ≠ ∅.

    lines 12–17

      classical
      let A : I → Finset (Equiv.Perm (Fin n)) := fun i =>
        Finset.univ.filter (fun σ => ∀ v ∈ D i, σ v = f i v)
      let N : I → Finset I := fun i => Finset.univ.filter (fun j => j ≠ i ∧
        (¬ Disjoint (D i) (D j) ∨
          ¬ Disjoint ((D i).image (f i)) ((D j).image (f j))))
  2. A permutation avoids the i-th partial assignment if and only if it does not belong to A_i.

    A permutation σ belongs to A_i if and only if σ v = f_i v for all v ∈ D_i. Negating this universal quantification using `not_forall` shows that σ ∉ A_i is equivalent to the existence of some v ∈ D_i such that σ v ≠ f_i v.

    lines 18–20

    uses not_forall

      have hmem : ∀ σ i, σ ∉ A i ↔ ∃ v ∈ D i, σ v ≠ f i v := by
        intro σ i
        simp [A, not_forall]
  3. For any index i and any subset S disjoint from N(i) with i ∉ S, every j ∈ S has domain and range disjoint from those of i.

    Assume i ∉ S and S is disjoint from N(i). For any j ∈ S, j cannot belong to N(i). Because j ≠ i, the condition defining N(i) implies that neither the domains nor the ranges of i and j can overlap, so D_i is disjoint from D_j and f_i(D_i) is disjoint from f_j(D_j).

    lines 21–35

    uses Finset.disjoint_left.mp, Finset.mem_filter.mpr, Finset.mem_univ

      have hdep : ∀ i (S : Finset I), i ∉ S → Disjoint S (N i) →
          ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤
            (1 : ℝ) / (n.descFactorial (D i).card : ℝ) *
              ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) := by
        intro i S hi hd
        have hnon : ∀ j ∈ S, Disjoint (D i) (D j) ∧
            Disjoint ((D i).image (f i)) ((D j).image (f j)) := by
          intro j hj
          have hjN : j ∉ N i := fun h => Finset.disjoint_left.mp hd hj h
          have hji : j ≠ i := fun h => hi (h ▸ hj)
          have hh : ¬ (¬ Disjoint (D i) (D j) ∨
              ¬ Disjoint ((D i).image (f i)) ((D j).image (f j))) := by
            intro h
            exact hjN (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hji, h⟩)
          tauto
  4. The number of permutations extending f_i while avoiding all assignments in S, scaled by the falling factorial n^{\underline{|D_i|}}, is bounded by the total number of permutations avoiding S.

    Because assignment i has domain and range disjoint from every assignment in S, the negative dependency lemma `canonical_permutation_negative_dependency_card_bound` applies. Rewriting and simplifying the set membership conditions shows that the intersection A_i ∩ {σ | ∀ j ∈ S, σ ∉ A_j} corresponds precisely to permutations avoiding S that agree with f_i on D_i, establishing n^{\underline{|D_i|}} * |A_i ∩ ⋂_{j ∈ S} A_jᶜ| ≤ |⋂_{j ∈ S} A_jᶜ|.

    lines 36–51

    uses canonical_permutation_negative_dependency_card_bound, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_inter, not_forall, _root_.not_imp, exists_prop

        have hc := canonical_permutation_negative_dependency_card_bound
          (D i) (f i) (hf i) S D f (fun j hj => (hnon j hj).1) (fun j hj => (hnon j hj).2)
        have hc0 : n.descFactorial (D i).card *
            (A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card ≤
              (Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card := by
          convert hc using 1
          · congr 1
            · simp
            · congr 1
              ext σ
              simp only [A, Finset.mem_filter, Finset.mem_univ, true_and,
                Finset.mem_inter, not_forall, _root_.not_imp, exists_prop]
              tauto
          · congr 1
            ext σ
            simp only [Finset.mem_filter, Finset.mem_univ, true_and, hmem]
  5. The conditional avoidance bound required by the lopsided local lemma holds: |A_i ∩ ⋂_{j ∈ S} A_jᶜ| ≤ (1 / n^{\underline{|D_i|}}) * |⋂_{j ∈ S} A_jᶜ|.

    Since D_i is a subset of Fin n, its cardinality is at most n, which implies by `Nat.descFactorial_pos.mpr` that the falling factorial n^{\underline{|D_i|}} is strictly positive. Casting the cardinality inequality to the reals and dividing by n^{\underline{|D_i|}} gives the required conditional bound for the lopsided local lemma.

    lines 52–63

    uses Nat.descFactorial_pos.mpr, Finset.card_le_univ, le_div_iff₀, mul_comm, div_eq_mul_inv, one_mul, mul_one

        have hdpos : 0 < (n.descFactorial (D i).card : ℝ) := by
          exact_mod_cast Nat.descFactorial_pos.mpr
            (show (D i).card ≤ n by simpa using Finset.card_le_univ (D i))
        have hc' : (n.descFactorial (D i).card : ℝ) *
            ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤
              ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) := by
          exact_mod_cast hc0
        have hdiv : ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤
            ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) /
              (n.descFactorial (D i).card : ℝ) :=
          (le_div_iff₀ hdpos).mpr (by simpa [mul_comm] using hc')
        simpa only [div_eq_mul_inv, one_mul, mul_one, mul_comm] using hdiv
  6. There exists a permutation σ avoiding all bad sets A_i.

    We invoke `finite_lopsided_avoidance_of_card_bound` on the sample space of permutations of Fin n, the bad events A_i, and the dependency graph N_i, using upper bounds p_i = 1 / n^{\underline{|D_i|}}. The conditional upper bound `hdep` and the hypothesis `hprob` satisfy the asymmetric local-lemma inequalities, yielding a permutation σ with σ ∉ A_i for all i.

    lines 64–65

    uses finite_lopsided_avoidance_of_card_bound

      obtain ⟨σ, hσ⟩ := finite_lopsided_avoidance_of_card_bound A N
        (fun i => (1 : ℝ) / (n.descFactorial (D i).card : ℝ)) x hx0 hx1 hdep hprob
  7. The permutation σ avoids every partial assignment f_i on D_i.

    Using the equivalence proved earlier (σ ∉ A_i ↔ ∃ v ∈ D_i, σ v ≠ f_i v), the fact that σ avoids every A_i means that for every i, there is some v ∈ D_i such that σ v ≠ f_i v.

    line 66

      exact ⟨σ, fun i => (hmem σ i).mp (hσ i)⟩
finite_lopsided_avoidance_of_card_bound
The finite lopsided Lovász Local Lemma: given bad subsets A_i of a finite set Ω with conditional upper bounds p_i outside their neighborhood graphs N(i) and weights x_i in [0, 1) satisfying p_i ≤ x_i ∏_{j ∈ N(i)} (1 - x_j), there exists an outcome in Ω avoiding all A_i.
canonical_permutation_negative_dependency_card_bound
If a partial injection on a finite set has domain and range disjoint from a family of partial injections, the number of permutations extending it while avoiding the family, times the falling factorial of the domain size, is at most the total number of permutations avoiding the family.
not_forall
Negating a universal statement is equivalent to an existential statement of the negation: (¬∀ x, P x) ↔ ∃ x, ¬P x.
_root_.not_imp
The negation of an implication ¬(a → b) is equivalent to a ∧ ¬b.
exists_prop
An existential quantifier over a proposition (∃ (_ : a), b) is equivalent to the conjunction a ∧ b.
Finset.disjoint_left.mp
If two sets are disjoint, any element of the first set is not in the second set.
Finset.mem_filter.mpr
An element belongs to a filtered finset if it belongs to the base set and satisfies the filtering predicate.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.
Finset.mem_inter
An element belongs to the intersection of two finsets if and only if it belongs to both.
true_and
The conjunction True ∧ p simplifies to p.
Nat.descFactorial_pos.mpr
The falling factorial n^{\underline{k}} is strictly positive whenever k ≤ n.
Finset.card_le_univ
The cardinality of any finset of a finite type is at most the total cardinality of the type.
le_div_iff₀
For positive c in a division structure, a ≤ b / c is equivalent to a * c ≤ b.
mul_comm
Multiplication is commutative: a * b = b * a.
div_eq_mul_inv
Division is multiplication by the reciprocal: a / b = a * b⁻¹.
one_mul
Multiplication by 1 on the left is the identity: 1 * a = a.
mul_one
Multiplication by 1 on the right is the identity: a * 1 = 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

theorem canonical_permutation_avoidance_of_local_lemma    {I : Type*} [Fintype I] [DecidableEq I] (n : ℕ) (hn : 0 < n)    (D : I → Finset (Fin n)) (f : I → Fin n → Fin n)    (hD : ∀ i, (D i).Nonempty)    (hf : ∀ i, Set.InjOn (f i) (↑(D i) : Set (Fin n)))    (x : I → ℝ) (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i < 1)    (hprob : ∀ i, (1 : ℝ) / (n.descFactorial (D i).card : ℝ) ≤      x i * ∏ j ∈ Finset.univ.filter (fun j => j ≠ i ∧        (¬ Disjoint (D i) (D j) ∨          ¬ Disjoint ((D i).image (f i)) ((D j).image (f j)))), (1 - x j)) :    ∃ σ : Equiv.Perm (Fin n), ∀ i, ∃ v ∈ D i, σ v ≠ f i v := by  classical  let A : I → Finset (Equiv.Perm (Fin n)) := fun i =>    Finset.univ.filter (fun σ => ∀ v ∈ D i, σ v = f i v)  let N : I → Finset I := fun i => Finset.univ.filter (fun j => j ≠ i ∧    (¬ Disjoint (D i) (D j) ∨      ¬ Disjoint ((D i).image (f i)) ((D j).image (f j))))  have hmem : ∀ σ i, σ ∉ A i ↔ ∃ v ∈ D i, σ v ≠ f i v := by    intro σ i    simp [A, not_forall]  have hdep : ∀ i (S : Finset I), i ∉ S → Disjoint S (N i) →      ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤        (1 : ℝ) / (n.descFactorial (D i).card : ℝ) *          ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) := by    intro i S hi hd    have hnon : ∀ j ∈ S, Disjoint (D i) (D j) ∧        Disjoint ((D i).image (f i)) ((D j).image (f j)) := by      intro j hj      have hjN : j ∉ N i := fun h => Finset.disjoint_left.mp hd hj h      have hji : j ≠ i := fun h => hi (h ▸ hj)      have hh : ¬ (¬ Disjoint (D i) (D j) ∨          ¬ Disjoint ((D i).image (f i)) ((D j).image (f j))) := by        intro h        exact hjN (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hji, h⟩)      tauto    have hc := canonical_permutation_negative_dependency_card_bound      (D i) (f i) (hf i) S D f (fun j hj => (hnon j hj).1) (fun j hj => (hnon j hj).2)    have hc0 : n.descFactorial (D i).card *        (A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card ≤          (Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card := by      convert hc using 1      · congr 1        · simp        · congr 1          ext σ          simp only [A, Finset.mem_filter, Finset.mem_univ, true_and,            Finset.mem_inter, not_forall, _root_.not_imp, exists_prop]          tauto      · congr 1        ext σ        simp only [Finset.mem_filter, Finset.mem_univ, true_and, hmem]    have hdpos : 0 < (n.descFactorial (D i).card : ℝ) := by      exact_mod_cast Nat.descFactorial_pos.mpr        (show (D i).card ≤ n by simpa using Finset.card_le_univ (D i))    have hc' : (n.descFactorial (D i).card : ℝ) *        ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤          ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) := by      exact_mod_cast hc0    have hdiv : ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤        ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) /          (n.descFactorial (D i).card : ℝ) :=      (le_div_iff₀ hdpos).mpr (by simpa [mul_comm] using hc')    simpa only [div_eq_mul_inv, one_mul, mul_one, mul_comm] using hdiv  obtain ⟨σ, hσ⟩ := finite_lopsided_avoidance_of_card_bound A N    (fun i => (1 : ℝ) / (n.descFactorial (D i).card : ℝ)) x hx0 hx1 hdep hprob  exact ⟨σ, fun i => (hmem σ i).mp (hσ i)⟩
See it in the graphDiscuss this resultChallenge it