wild_profile_conditioned_joint_count_transport
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
- wild_normalized_array_whole_bad_first_momentFor a symmetric idempotent row-injective array on Fin n and any finite block profile, the sum over all vertex permutations of the number…
- wild_involution_pattern_conditioned_bad_count_invariantFor finite matching patterns with the same internal partner equalities, the permutation counts of a whole-bad matching and any prescribed…
- wild_normalized_array_single_bad_count_invariantFor any finite block profile p and two symmetric idempotent row-injective arrays on Fin n, the number of vertex permutations for which a…
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.
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).
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
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).
· 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 huvPermuting 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`).
rflThe 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.
uses
mem_filter,mem_univ,true_and,mem_imageclassical 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
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 ∘ σ⁻¹.
uses
Finset.card_bij,mem_filter,mem_univ,true_and,wild_profile_permute_trans,wild_profile_bad_relabelclassical 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)
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 σ = τ.
uses
congrArg· intro σ _ τ _ he ext v exact e.injective (congrArg (fun f : Equiv.Perm V => f v) he)
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 τ.
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
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.
uses
Finset.card_bijclassical unfold wild_profile_conditioned_joint_bad_count apply Finset.card_bij (fun σ _ => σ.trans e)
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`.
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]
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.
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)
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.
uses
congrArg· intro σ _ τ _ he ext v exact e.injective (congrArg (fun f : Equiv.Perm V => f v) he)
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.
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
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.
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
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 τ.
· 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.
- The action of a permutation σ on a profile p is defined formally as p ∘ σ⁻¹. Under this convention, composing on the right by e (σ ↦ σ ∘ e) pushes forward the fiber of block b covariantly to e(S).
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.
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