AFTD Auto-Formalizing Theoretical Domains

wild_profile_conditioned_joint_count_transport

theoremverified

For a finite vertex type, finite block type, arbitrary block profile p, chosen block b and vertex subset S, and any finite set of color relations R_c,T_c simultaneously transported by a vertex permutation e, the number of permutations making every selected color have an empty nontrivial block cut and making block b equal S is unchanged after replacing the relations by T_c and S by its image under e. A simultaneous isomorphism is a hypothesis; no classification by cycle data is asserted.

Statement

theorem wild_profile_conditioned_joint_count_transport {V B C : Type*}
    [Fintype V] [Fintype B]
    (p : V → B) (b : B) (S : Finset V)
    (R T : C → V → V → Prop) (colors : Finset C)
    (e : Equiv.Perm V) (h : ∀ c ∈ colors, ∀ u v, T c (e u) (e v) ↔ R c u v) :
    wild_profile_conditioned_joint_bad_count p b S R colors =
      wild_profile_conditioned_joint_bad_count p b (S.image e) T colors
Source
IN-364 / OP-306, continuation of the finite weighted-partition route for https://arxiv.org/html/2610.22142v1, Sections3.3 and6. Standard permutation-orbit background: Matchings and Representation Theory (2018), Section4.10, https://dspacemainprd01.lib.uwaterloo.ca/server/api/core/bitstreams/9d33772f-c7dc-409f-a4ed-521da8d87890/content. The witness triple system is standard incidence data; these are route helpers or finite method diagnostics. No wild-number bound, new exact sharpness case, general sign theorem, or research advance is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 3

The proof, explained

The theorem proves that simultaneously transporting a family of relations R_c to T_c by a vertex permutation e preserves the number of permutations σ that place block b on S and induce empty nontrivial cuts in all selected colors. The proof establishes preliminary lemmas showing that permutation action commutes with composition, fibers transform covariantly under relabeling, and empty cuts transfer across isomorphic relations. To equate the counts, `Finset.card_bij` constructs a bijection between the sets of valid permutations by right-composition with e (σ ↦ σ ∘ e). This map pushes the fiber of b forward to e(S) and preserves the cut conditions for each color, with the inverse mapping τ ↦ τ ∘ e⁻¹ providing the two-sided inverse.

  1. If the permuted profile p ∘ e⁻¹ has an empty nontrivial block cut in T, then p has one in R.

    Suppose S ⊆ B witnesses an empty nontrivial cut for p ∘ e⁻¹ in T. For any u, v ∈ V with p(u) ∈ S and p(v) ∉ S, the points e(u) and e(v) satisfy (p ∘ e⁻¹)(e(u)) = p(u) ∈ S and (p ∘ e⁻¹)(e(v)) = p(v) ∉ S, so ¬T(e(u), e(v)). Since e is an isomorphism between R and T via hypothesis h, T(e(u), e(v)) ↔ R(u, v), which yields ¬R(u, v).

    lines 20–28

      classical
      constructor
      · rintro ⟨S,hS,hS',hcut⟩
        refine ⟨S,hS,hS',?_⟩
        intro u v hu hv huv
        apply hcut (e u) (e v)
        · simpa [wild_profile_permute] using hu
        · simpa [wild_profile_permute] using hv
        · exact (h u v).mpr huv
  2. If p has an empty nontrivial block cut in R, then p ∘ e⁻¹ has one in T.

    Conversely, suppose S ⊆ B witnesses an empty nontrivial cut for p in R. For any u, v ∈ V with (p ∘ e⁻¹)(u) ∈ S and (p ∘ e⁻¹)(v) ∉ S, evaluating at e⁻¹(u) and e⁻¹(v) gives p(e⁻¹(u)) ∈ S and p(e⁻¹(v)) ∉ S, so ¬R(e⁻¹(u), e⁻¹(v)). By hypothesis h applied to e⁻¹(u) and e⁻¹(v), T(u, v) ↔ R(e⁻¹(u), e⁻¹(v)), proving ¬T(u, v).

    lines 29–34

      · rintro ⟨S,hS,hS',hcut⟩
        refine ⟨S,hS,hS',?_⟩
        intro u v hu hv huv
        apply hcut (e.symm u) (e.symm v) hu hv
        apply (h (e.symm u) (e.symm v)).mp
        simpa using huv
  3. Permuting a profile by σ ∘ e is definitionally equal to permuting first by σ and then by e.

    By definition, (p ∘ (σ ∘ e)⁻¹)(v) = p(e⁻¹(σ⁻¹(v))) = ((p ∘ σ⁻¹) ∘ e⁻¹)(v), so the identity holds by reflexivity (`rfl`).

    line 40

      rfl
  4. The fiber of block b under p ∘ e⁻¹ is the image under e of its fiber under p.

    Unfolding the fiber definition and applying set extensionality via `mem_filter`, `mem_univ`, `true_and`, and `mem_image`, a vertex v has (p ∘ e⁻¹)(v) = b if and only if there exists u such that p(u) = b and e(u) = v. In the forward direction, taking u = e⁻¹(v) works since e(e⁻¹(v)) = v; in the reverse direction, if v = e(u) with p(u) = b, then (p ∘ e⁻¹)(e(u)) = p(u) = b.

    lines 45–53

    uses mem_filter, mem_univ, true_and, mem_image

      classical
      unfold wild_profile_fiber wild_profile_permute
      ext v
      simp only [mem_filter,mem_univ,true_and,mem_image]
      constructor
      · intro h
        exact ⟨e.symm v,h,e.apply_symm_apply v⟩
      · rintro ⟨u,hu,rfl⟩
        simpa using hu
  5. The equality of unconditioned joint bad counts reduces via `Finset.card_bij` to right-composition by e, which preserves the cut conditions.

    By `Finset.card_bij`, we construct a bijection between the sets of permutations by sending σ to σ ∘ e. For any valid permutation σ and any color c ∈ colors, `wild_profile_permute_trans` writes the permuted profile as (p ∘ σ⁻¹) ∘ e⁻¹. Since e is an isomorphism between R(c) and T(c), `wild_profile_bad_relabel` ensures that the empty nontrivial cut condition in T(c) holds if and only if it holds for R(c) under p ∘ σ⁻¹.

    lines 66–74

    uses Finset.card_bij, mem_filter, mem_univ, true_and, wild_profile_permute_trans, wild_profile_bad_relabel

      classical
      unfold wild_profile_joint_bad_count
      apply Finset.card_bij (fun σ _ => σ.trans e)
      · intro σ hσ
        simp only [mem_filter,mem_univ,true_and] at hσ ⊢
        intro c hc
        rw [wild_profile_permute_trans]
        exact (wild_profile_bad_relabel (wild_profile_permute p σ) (R c) (T c) e (h c hc)).mpr
          (hσ c hc)
  6. The mapping σ ↦ σ ∘ e is injective in the unconditioned case.

    If σ ∘ e = τ ∘ e, evaluating at any vertex v yields e(σ(v)) = e(τ(v)) by `congrArg`. Since e is an equivalence and therefore injective, σ(v) = τ(v) for all v, so σ = τ.

    lines 75–77

    uses congrArg

      · intro σ _ τ _ he
        ext v
        exact e.injective (congrArg (fun f : Equiv.Perm V => f v) he)
  7. The mapping σ ↦ σ ∘ e is surjective in the unconditioned case.

    Given τ valid for T, we propose τ ∘ e⁻¹ as its preimage. By `wild_profile_permute_trans` and `wild_profile_bad_relabel` applied with e⁻¹, the empty cut condition transfers from T(c) to R(c). Pointwise evaluation simplifies ((τ ∘ e⁻¹) ∘ e)(v) = τ(v), showing that right-composition with e recovers τ.

    lines 78–88

    uses mem_filter, mem_univ, true_and, wild_profile_permute_trans, wild_profile_bad_relabel

      · intro τ hτ
        refine ⟨τ.trans e.symm,?_,?_⟩
        · simp only [mem_filter,mem_univ,true_and] at hτ ⊢
          intro c hc
          rw [wild_profile_permute_trans]
          apply (wild_profile_bad_relabel (wild_profile_permute p τ) (T c) (R c) e.symm ?_).mpr
            (hτ c hc)
          intro u v
          simpa using (h c hc (e.symm u) (e.symm v)).symm
        · ext v
          simp
  8. The equality of conditioned joint bad counts reduces to establishing a bijection via the map σ ↦ σ ∘ e.

    Unfolding `wild_profile_conditioned_joint_bad_count`, each count is the size of the set of permutations σ where the fiber of block b is fixed (to S for R, and to e(S) for T) and every selected color has an empty nontrivial cut. By `Finset.card_bij`, equality of cardinalities follows if right-composition by e defines a bijection between these sets.

    lines 105–107

    uses Finset.card_bij

      classical
      unfold wild_profile_conditioned_joint_bad_count
      apply Finset.card_bij (fun σ _ => σ.trans e)
  9. If σ has fiber S at block b, then σ ∘ e has fiber e(S) at block b.

    Given σ whose fiber at b is S, the permuted profile p ∘ (σ ∘ e)⁻¹ factors as (p ∘ σ⁻¹) ∘ e⁻¹ by `wild_profile_permute_trans`. By `wild_profile_fiber_relabel`, the fiber of b under this profile is the image under e of the fiber under p ∘ σ⁻¹, which equals e(S). Set membership is simplified with `mem_filter`, `mem_univ`, and `true_and`.

    lines 108–111

    uses mem_filter, mem_univ, true_and, wild_profile_permute_trans, wild_profile_fiber_relabel

      · intro σ hσ
        simp only [mem_filter,mem_univ,true_and] at hσ ⊢
        constructor
        · rw [wild_profile_permute_trans,wild_profile_fiber_relabel,hσ.1]
  10. If σ has empty nontrivial cuts for each R(c), then σ ∘ e has empty nontrivial cuts for each T(c).

    For each color c ∈ colors, factoring the profile via `wild_profile_permute_trans` allows the application of `wild_profile_bad_relabel`. Because e is an isomorphism between R(c) and T(c) by hypothesis h, the permuted profile has an empty nontrivial cut in T(c) if and only if p ∘ σ⁻¹ has one in R(c), which holds by assumption.

    lines 112–115

    uses wild_profile_permute_trans, wild_profile_bad_relabel

        · intro c hc
          rw [wild_profile_permute_trans]
          exact (wild_profile_bad_relabel (wild_profile_permute p σ) (R c) (T c) e (h c hc)).mpr
            (hσ.2 c hc)
  11. The mapping σ ↦ σ ∘ e is injective in the conditioned case.

    If σ ∘ e = τ ∘ e, evaluating at any vertex v gives e(σ(v)) = e(τ(v)) by `congrArg`. Because e is injective, σ(v) = τ(v) for all v, so σ = τ by function extensionality.

    lines 116–118

    uses congrArg

      · intro σ _ τ _ he
        ext v
        exact e.injective (congrArg (fun f : Equiv.Perm V => f v) he)
  12. For any valid τ in the target set, the preimage candidate τ ∘ e⁻¹ satisfies the fiber condition for S.

    Given τ satisfying the conditions for e(S) and T, we propose τ ∘ e⁻¹. Permuting p by τ ∘ e⁻¹ decomposes by `wild_profile_permute_trans` into permuting by τ and then by e⁻¹. By `wild_profile_fiber_relabel`, its fiber at b is e⁻¹(e(S)). Using `Finset.image_image`, this simplifies to (e⁻¹ ∘ e)(S) = S.

    lines 119–125

    uses mem_filter, mem_univ, true_and, wild_profile_permute_trans, wild_profile_fiber_relabel, Finset.image_image

      · intro τ hτ
        refine ⟨τ.trans e.symm,?_,?_⟩
        · simp only [mem_filter,mem_univ,true_and] at hτ ⊢
          constructor
          · rw [wild_profile_permute_trans,wild_profile_fiber_relabel,hτ.1]
            simp only [Finset.image_image]
            simp
  13. The candidate preimage τ ∘ e⁻¹ satisfies the empty cut condition for each R(c).

    For each color c ∈ colors, rewriting with `wild_profile_permute_trans` and applying `wild_profile_bad_relabel` with e⁻¹ shows that an empty nontrivial cut in R(c) pulls back from T(c). The isomorphism hypothesis for e⁻¹, R(c)(e⁻¹(u), e⁻¹(v)) ↔ T(c)(u, v), follows by symmetry from hypothesis h.

    lines 126–131

    uses wild_profile_permute_trans, wild_profile_bad_relabel

          · intro c hc
            rw [wild_profile_permute_trans]
            apply (wild_profile_bad_relabel (wild_profile_permute p τ) (T c) (R c) e.symm ?_).mpr
              (hτ.2 c hc)
            intro u v
            simpa using (h c hc (e.symm u) (e.symm v)).symm
  14. The map σ ↦ σ ∘ e is surjective in the conditioned case, since (τ ∘ e⁻¹) ∘ e = τ.

    Applying (τ ∘ e⁻¹) ∘ e to an arbitrary vertex v yields e(e⁻¹(τ(v))) = τ(v). This pointwise identity verifies that right-composing the candidate preimage with e returns τ.

    lines 132–133

        · ext v
          simp
Finset.card_bij
Two finite sets have the same cardinality if there exists a well-defined map between them that is injective and surjective.
mem_filter
An element x belongs to the filtered sub-finset {a ∈ s | p a} if and only if x ∈ s and p x holds.
mem_univ
Every element of a finite type belongs to the universal finset `univ`.
true_and
The conjunction True ∧ p is logically equivalent to p.
mem_image
An element y belongs to the image of a finset s under f if and only if there is an element x ∈ s with f(x) = y.
wild_profile_permute_trans
Permuting a block profile by the composite permutation σ.trans e equals permuting first by σ and then by e.
wild_profile_fiber_relabel
The fiber of a block b under a profile permuted by e is the image under e of its fiber under the unpermuted profile.
wild_profile_bad_relabel
If a permutation e is an isomorphism between relations R and T, then a permuted profile has an empty nontrivial cut in T if and only if the original profile has one in R.
congrArg
Applying a function to equal arguments produces equal results.
Finset.image_image
The image of a finset under f followed by g is equal to its image under the composite function g ∘ f.

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

open Finsetopen scoped BigOperators Classicalset_option maxHeartbeats 3000000noncomputable def wild_profile_bad {V B : Type*} [Fintype B]    (p : V → B) (R : V → V → Prop) : Prop :=  ∃ S : Finset B, S.Nonempty ∧ S ≠ univ ∧    ∀ u v, p u ∈ S → p v ∉ S → ¬ R u vdef wild_profile_permute {V B : Type*} (p : V → B) (σ : Equiv.Perm V) : V → B :=  fun v => p (σ.symm v)noncomputable def wild_profile_fiber {V B : Type*} [Fintype V]    (p : V → B) (b : B) : Finset V := univ.filter fun v => p v = btheorem wild_profile_bad_relabel {V B : Type*} [Fintype B]    (p : V → B) (R T : V → V → Prop) (e : Equiv.Perm V)    (h : ∀ u v, T (e u) (e v) ↔ R u v) :    wild_profile_bad (wild_profile_permute p e) T ↔ wild_profile_bad p R := by  classical  constructor  · rintro ⟨S,hS,hS',hcut⟩    refine ⟨S,hS,hS',?_⟩    intro u v hu hv huv    apply hcut (e u) (e v)    · simpa [wild_profile_permute] using hu    · simpa [wild_profile_permute] using hv    · exact (h u v).mpr huv  · rintro ⟨S,hS,hS',hcut⟩    refine ⟨S,hS,hS',?_⟩    intro u v hu hv huv    apply hcut (e.symm u) (e.symm v) hu hv    apply (h (e.symm u) (e.symm v)).mp    simpa using huvtheorem wild_profile_permute_trans {V B : Type*}    (p : V → B) (σ e : Equiv.Perm V) :    wild_profile_permute p (σ.trans e) =      wild_profile_permute (wild_profile_permute p σ) e := by  rfltheorem wild_profile_fiber_relabel {V B : Type*} [Fintype V]    (p : V → B) (b : B) (e : Equiv.Perm V) :    wild_profile_fiber (wild_profile_permute p e) b = (wild_profile_fiber p b).image e := by  classical  unfold wild_profile_fiber wild_profile_permute  ext v  simp only [mem_filter,mem_univ,true_and,mem_image]  constructor  · intro h    exact ⟨e.symm v,h,e.apply_symm_apply v⟩  · rintro ⟨u,hu,rfl⟩    simpa using hunoncomputable def wild_profile_joint_bad_count {V B C : Type*}    [Fintype V] [Fintype B]    (p : V → B) (R : C → V → V → Prop) (colors : Finset C) : ℕ :=  (univ.filter fun σ : Equiv.Perm V =>    ∀ c ∈ colors, wild_profile_bad (wild_profile_permute p σ) (R c)).cardtheorem wild_profile_joint_bad_count_transport {V B C : Type*}    [Fintype V] [Fintype B]    (p : V → B) (R T : C → V → V → Prop) (colors : Finset C)    (e : Equiv.Perm V) (h : ∀ c ∈ colors, ∀ u v, T c (e u) (e v) ↔ R c u v) :    wild_profile_joint_bad_count p R colors = wild_profile_joint_bad_count p T colors := by  classical  unfold wild_profile_joint_bad_count  apply Finset.card_bij (fun σ _ => σ.trans e)  · intro σ hσ    simp only [mem_filter,mem_univ,true_and] at hσ ⊢    intro c hc    rw [wild_profile_permute_trans]    exact (wild_profile_bad_relabel (wild_profile_permute p σ) (R c) (T c) e (h c hc)).mpr      (hσ c hc)  · intro σ _ τ _ he    ext v    exact e.injective (congrArg (fun f : Equiv.Perm V => f v) he)  · intro τ hτ    refine ⟨τ.trans e.symm,?_,?_⟩    · simp only [mem_filter,mem_univ,true_and] at hτ ⊢      intro c hc      rw [wild_profile_permute_trans]      apply (wild_profile_bad_relabel (wild_profile_permute p τ) (T c) (R c) e.symm ?_).mpr        (hτ c hc)      intro u v      simpa using (h c hc (e.symm u) (e.symm v)).symm    · ext v      simpnoncomputable def wild_profile_conditioned_joint_bad_count {V B C : Type*}    [Fintype V] [Fintype B]    (p : V → B) (b : B) (S : Finset V)    (R : C → V → V → Prop) (colors : Finset C) : ℕ :=  (univ.filter fun σ : Equiv.Perm V =>    wild_profile_fiber (wild_profile_permute p σ) b = S ∧    ∀ c ∈ colors, wild_profile_bad (wild_profile_permute p σ) (R c)).cardtheorem wild_profile_conditioned_joint_count_transport {V B C : Type*}    [Fintype V] [Fintype B]    (p : V → B) (b : B) (S : Finset V)    (R T : C → V → V → Prop) (colors : Finset C)    (e : Equiv.Perm V) (h : ∀ c ∈ colors, ∀ u v, T c (e u) (e v) ↔ R c u v) :    wild_profile_conditioned_joint_bad_count p b S R colors =      wild_profile_conditioned_joint_bad_count p b (S.image e) T colors := by  classical  unfold wild_profile_conditioned_joint_bad_count  apply Finset.card_bij (fun σ _ => σ.trans e)  · intro σ hσ    simp only [mem_filter,mem_univ,true_and] at hσ ⊢    constructor    · rw [wild_profile_permute_trans,wild_profile_fiber_relabel,hσ.1]    · intro c hc      rw [wild_profile_permute_trans]      exact (wild_profile_bad_relabel (wild_profile_permute p σ) (R c) (T c) e (h c hc)).mpr        (hσ.2 c hc)  · intro σ _ τ _ he    ext v    exact e.injective (congrArg (fun f : Equiv.Perm V => f v) he)  · intro τ hτ    refine ⟨τ.trans e.symm,?_,?_⟩    · simp only [mem_filter,mem_univ,true_and] at hτ ⊢      constructor      · rw [wild_profile_permute_trans,wild_profile_fiber_relabel,hτ.1]        simp only [Finset.image_image]        simp      · intro c hc        rw [wild_profile_permute_trans]        apply (wild_profile_bad_relabel (wild_profile_permute p τ) (T c) (R c) e.symm ?_).mpr          (hτ.2 c hc)        intro u v        simpa using (h c hc (e.symm u) (e.symm v)).symm    · ext v      simp
See it in the graphDiscuss this resultChallenge it