AFTD Auto-Formalizing Theoretical Domains

canonical_permutation_negative_dependency_card_bound

theoremverified

For canonical permutation events with disjoint domains and ranges from a fixed injective partial assignment, multiplying the avoiding permutations that extend it by the relevant falling factorial bounds them by all avoiding permutations.

Statement

theorem canonical_permutation_negative_dependency_card_bound
    {α I : Type*} [Fintype α] [DecidableEq α]
    (D : Finset α) (f : α → α) (hf : Set.InjOn f (↑D : Set α))
    (T : Finset I) (C : I → Finset α) (g : I → α → α)
    (hdom : ∀ i ∈ T, Disjoint D (C i))
    (hran : ∀ i ∈ T, Disjoint (D.image f) ((C i).image (g i))) :
    (Fintype.card α).descFactorial D.card *
      ((Finset.univ.filter (fun τ : Equiv.Perm α =>
        ∀ i ∈ T, ∃ v ∈ C i, τ v ≠ g i v)).filter
          (fun τ => ∀ a ∈ D, τ a = f a)).card ≤
      (Finset.univ.filter (fun τ : Equiv.Perm α =>
        ∀ i ∈ T, ∃ v ∈ C i, τ v ≠ g i v)).card
Source
Negative-dependency counting helper for OP-306; EJC 14 (2007) R63, DOI 10.37236/981, Theorem 1, specialized to the domain/range-overlap supergraph.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem is proved by invoking `permutation_partial_assignment_card_bound_of_switching`, which reduces the negative dependency bound to showing that the set of pattern-avoiding permutations is closed under transposition switching of the form τ ↦ (swap y (f a)) * τ. Assuming for contradiction that the switched permutation agrees with some pattern g i on C i, the disjointness of domains and ranges ensures that the witness v ∈ C i (where the original permutation differed from g i) is fixed by the transposition and satisfies g i v ≠ y. This forces the original permutation to agree with g i at v, yielding a contradiction.

  1. The bound reduces to verifying that the set of pattern-avoiding permutations is closed under transposition switching.

    By `permutation_partial_assignment_card_bound_of_switching`, multiplying the number of pattern-avoiding permutations that extend the injective partial assignment f on D by the falling factorial (|α|)_{|D|} is bounded by the total number of pattern-avoiding permutations, provided that for every a ∈ D, every avoiding permutation τ with τ a = f a, and every y ∈ α, the switched permutation (swap y (f a)) * τ is also pattern-avoiding.

    lines 13–14

    uses permutation_partial_assignment_card_bound_of_switching

      classical
      apply permutation_partial_assignment_card_bound_of_switching D f hf
  2. To show the switched permutation τ' = (swap y (f a)) * τ is avoiding, it suffices to find for each index i ∈ T an element v ∈ C i where τ' v ≠ g i v.

    Fix a ∈ D, an avoiding permutation τ with τ a = f a, and an element y ∈ α. To show that τ' belongs to the filtered finset of permutations avoiding all patterns, we introduce an arbitrary index i ∈ T and aim to show that τ' differs from g i on at least one element of C i.

    lines 15–18

    uses Finset.mem_filter.mpr, Finset.mem_univ

      intro a ha τ hτ hτa y
      apply Finset.mem_filter.mpr
      refine ⟨Finset.mem_univ _, ?_⟩
      intro i hi
  3. Assuming for contradiction that τ' agrees with g i everywhere on C i, the original avoiding permutation τ still provides a witness v ∈ C i where τ v ≠ g i v.

    Assume for contradiction that τ' u = g i u for all u ∈ C i. Because the original permutation τ is in the avoiding set, extracting the avoidance condition for index i provides a witness v ∈ C i such that τ v ≠ g i v.

    lines 19–21

    uses Finset.mem_filter.mp

      by_contra h
      push Not at h
      obtain ⟨v, hv, hτv⟩ := (Finset.mem_filter.mp hτ).2 i hi
  4. The witness v is distinct from a, and its assigned value g i v is distinct from f a.

    Because D and C i are disjoint (by `hdom`), the elements a ∈ D and v ∈ C i cannot be equal. Similarly, because the image sets f(D) and (g i)(C i) are disjoint (by `hran`), f a ∈ f(D) and g i v ∈ (g i)(C i) cannot be equal.

    lines 22–29

    uses Finset.disjoint_left.mp, Finset.mem_image.mpr

      have hva : v ≠ a := by
        intro heq
        exact Finset.disjoint_left.mp (hdom i hi) ha (heq ▸ hv)
      have hgfa : g i v ≠ f a := by
        intro heq
        exact Finset.disjoint_left.mp (hran i hi)
          (Finset.mem_image.mpr ⟨a, ha, rfl⟩)
          (Finset.mem_image.mpr ⟨v, hv, heq⟩)
  5. The assigned value g i v is distinct from y.

    First, τ' a = (swap y (f a)) (τ a) = (swap y (f a)) (f a) = y. If g i v = y, then the contradiction hypothesis gives τ' v = g i v = y = τ' a. Because τ' is an injective permutation, this would force v = a, contradicting v ≠ a.

    lines 30–35

    uses Equiv.Perm.mul_apply

      have hsva : (Equiv.swap y (f a) * τ) a = y := by
        simp [Equiv.Perm.mul_apply, hτa]
      have hgy : g i v ≠ y := by
        intro heq
        apply hva
        exact (Equiv.swap y (f a) * τ).injective ((h v hv).trans (heq.trans hsva.symm))
  6. Applying the transposition (swap y (f a)) to τ' v = g i v implies τ v = g i v, which contradicts τ v ≠ g i v.

    Applying the swap (swap y (f a)) to both sides of the assumption τ' v = g i v, the left-hand side simplifies to (swap y (f a)) ((swap y (f a)) (τ v)) = τ v because transpositions are involutions. The right-hand side simplifies to g i v because g i v is distinct from both swap points y and f a. This yields τ v = g i v, contradicting τ v ≠ g i v and completing the proof.

    lines 36–39

    uses congrArg, Equiv.Perm.mul_apply, Equiv.swap_apply_self, Equiv.swap_apply_of_ne_of_ne

      apply hτv
      have hh := congrArg (Equiv.swap y (f a)) (h v hv)
      simpa only [Equiv.Perm.mul_apply, Equiv.swap_apply_self,
        Equiv.swap_apply_of_ne_of_ne hgy hgfa] using hh
permutation_partial_assignment_card_bound_of_switching
If an injective partial assignment f on D and a set of permutations A satisfy the switching property that (swap y (f a)) * τ ∈ A whenever τ ∈ A has τ a = f a, then (|α|)_{|D|} * |{τ ∈ A | τ|_D = f}| ≤ |A|.
Finset.mem_filter.mpr
An element x belongs to {y ∈ s | p y} if x ∈ s and p x holds.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_filter.mp
If x belongs to {y ∈ s | p y}, then x ∈ s and p x holds.
Finset.disjoint_left.mp
If two finsets are disjoint, then any element belonging to the first does not belong to the second.
Finset.mem_image.mpr
An element y belongs to the image f(s) if there exists x ∈ s such that f x = y.
Equiv.Perm.mul_apply
Multiplication of permutations acts by function composition: (f * g) x = f (g x).
congrArg
Applying a function to equal arguments yields equal values: if a₁ = a₂, then f a₁ = f a₂.
Equiv.swap_apply_self
Applying the transposition (swap i j) twice to any element returns that element: (swap i j) ((swap i j) a) = a.
Equiv.swap_apply_of_ne_of_ne
The transposition (swap a b) fixes any element x distinct from both a and b: if x ≠ a and x ≠ b, then (swap a b) x = x.

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_negative_dependency_card_bound    {α I : Type*} [Fintype α] [DecidableEq α]    (D : Finset α) (f : α → α) (hf : Set.InjOn f (↑D : Set α))    (T : Finset I) (C : I → Finset α) (g : I → α → α)    (hdom : ∀ i ∈ T, Disjoint D (C i))    (hran : ∀ i ∈ T, Disjoint (D.image f) ((C i).image (g i))) :    (Fintype.card α).descFactorial D.card *      ((Finset.univ.filter (fun τ : Equiv.Perm α =>        ∀ i ∈ T, ∃ v ∈ C i, τ v ≠ g i v)).filter          (fun τ => ∀ a ∈ D, τ a = f a)).card ≤      (Finset.univ.filter (fun τ : Equiv.Perm α =>        ∀ i ∈ T, ∃ v ∈ C i, τ v ≠ g i v)).card := by  classical  apply permutation_partial_assignment_card_bound_of_switching D f hf  intro a ha τ hτ hτa y  apply Finset.mem_filter.mpr  refine ⟨Finset.mem_univ _, ?_⟩  intro i hi  by_contra h  push Not at h  obtain ⟨v, hv, hτv⟩ := (Finset.mem_filter.mp hτ).2 i hi  have hva : v ≠ a := by    intro heq    exact Finset.disjoint_left.mp (hdom i hi) ha (heq ▸ hv)  have hgfa : g i v ≠ f a := by    intro heq    exact Finset.disjoint_left.mp (hran i hi)      (Finset.mem_image.mpr ⟨a, ha, rfl⟩)      (Finset.mem_image.mpr ⟨v, hv, heq⟩)  have hsva : (Equiv.swap y (f a) * τ) a = y := by    simp [Equiv.Perm.mul_apply, hτa]  have hgy : g i v ≠ y := by    intro heq    apply hva    exact (Equiv.swap y (f a) * τ).injective ((h v hv).trans (heq.trans hsva.symm))  apply hτv  have hh := congrArg (Equiv.swap y (f a)) (h v hv)  simpa only [Equiv.Perm.mul_apply, Equiv.swap_apply_self,    Equiv.swap_apply_of_ne_of_ne hgy hgfa] using hh
See it in the graphDiscuss this resultChallenge it