AFTD Auto-Formalizing Theoretical Domains

wild_joint_conditioned_bad_probability_transport

theoremverified

For arbitrary relations R,U and a vertex permutation e carrying S to T and preserving the relations, the conditional whole-bad probabilities given first block S or T agree. Both probabilities are explicit finite-cardinality ratios.

Statement

theorem wild_joint_conditioned_bad_probability_transport
    (q : ℕ) (R U : Fin (3*q) → Fin (3*q) → Prop)
    (S T : Finset (Fin (3*q))) (e : Equiv.Perm (Fin (3*q)))
    (heT : S.image e = T)
    (heR : ∀ x y, U (e x) (e y) ↔ R x y) :
    (((univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>
      wild_joint_first_block q σ = S ∧ wild_joint_bad_relation q (wild_joint_block q σ) R).card : ℝ) /
      (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = S).card) =
    (((univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>
      wild_joint_first_block q σ = T ∧ wild_joint_bad_relation q (wild_joint_block q σ) U).card : ℝ) /
      (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = T).card)
Source
IN-382 / OP-306 campaign9, 2026-10-30. Standard finite matching symmetry and exact permutation conditioning supporting wild_joint_expected_ID_eq_alpha_sum. This uses the corrected odd-q orbit theorem; it does not establish the main weighted sign or a new wild-number bound.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • wild_joint_alphaalpha(T): the conditional probability, under the uniform distribution on all vertex permutations σ, that the fixed canonical matching is…
  • wild_joint_first_blockThe first block: the set of vertices placed in positions 0,1,2 by σ (= {σ 0, σ 1, σ 2}).
  • wild_joint_blockBlock (index of the consecutive triple) containing vertex v under the permutation σ, where σ p is the vertex at position p; blocks are…
  • wild_joint_bad_relationA symmetric relation R is whole-bad for the block map p if some nonempty proper union of blocks (a nonempty proper set of block indices B,…
Used by 1

The proof, explained

The proof establishes that post-composition by the vertex permutation $e$, mapping $\sigma \mapsto \sigma \circ e$, provides a cardinality-preserving bijection between permutations associated with $(S, R)$ and those associated with $(T, U)$. First, block assignments and first blocks are shown to transform equivariantly under $e$, which makes the condition of having first block $S$ equivalent to having first block $T$, and preserves badness between relations $R$ and $U$. A single bijective equicardinality lemma parameterised by a boolean flag then simultaneously equates the numerators (with the badness condition) and denominators (conditioning only on the first block), completing the equality of conditional probabilities.

  1. Block assignment is equivariant under composition with $e$: the block of $e(x)$ under $\sigma \circ e$ equals the block of $x$ under $\sigma$.

    Enabling classical logic, we consider the block assignment `wild_joint_block`, which assigns element $v$ to block $\lfloor \sigma^{-1}(v) / 3 \rfloor$. For the composed permutation $\sigma \circ e$ evaluated at $e(x)$, the inverse permutation gives $(\sigma \circ e)^{-1}(e(x)) = \sigma^{-1}(e^{-1}(e(x))) = \sigma^{-1}(x)$. Dividing by 3 gives identical quotient values, which `Fin.ext` and `simp` verify by definition.

    lines 18–23

    uses Fin.ext

      classical
      have hblock : ∀ (σ : Equiv.Perm (Fin (3*q))) x,
          wild_joint_block q (σ.trans e) (e x) = wild_joint_block q σ x := by
        intro σ x
        apply Fin.ext
        simp [wild_joint_block]
  2. The first block of $\sigma \circ e$ is the image under $e$ of the first block of $\sigma$.

    By definition, an element $x$ belongs to `wild_joint_first_block q (σ.trans e)` if and only if $((\sigma \circ e)^{-1}(x)) < 3$, which is equivalent to $\sigma^{-1}(e^{-1}(x)) < 3$. This means $e^{-1}(x)$ belongs to the first block of $\sigma$, or equivalently, $x$ lies in the image under $e$ of the first block of $\sigma$. The equivalence is established by exhibiting $e^{-1}(x)$ in the forward direction and simplifying in the reverse direction.

    lines 24–34

    uses true_and

      have hfirst : ∀ σ : Equiv.Perm (Fin (3*q)),
          wild_joint_first_block q (σ.trans e) = (wild_joint_first_block q σ).image e := by
        intro σ
        ext x
        simp only [wild_joint_first_block,mem_filter,mem_univ,true_and,mem_image]
        constructor
        · intro hx
          refine ⟨e.symm x,?_,e.apply_symm_apply x⟩
          exact hx
        · rintro ⟨y,hy,rfl⟩
          simpa using hy
  3. The first block of $\sigma \circ e$ equals $T$ if and only if the first block of $\sigma$ equals $S$.

    From the previous step, the first block of $\sigma \circ e$ is $e(\text{first\_block}(\sigma))$. Since $T = e(S)$ by hypothesis `heT`, this equality is $e(\text{first\_block}(\sigma)) = e(S)$. Because $e$ is an equivalence and therefore injective, the finset image operation is injective (`Finset.image_injective`), so the image sets are equal if and only if the original sets are equal.

    lines 35–39

    uses Finset.image_injective

      have hfirstiff : ∀ σ : Equiv.Perm (Fin (3*q)),
          wild_joint_first_block q (σ.trans e) = T ↔ wild_joint_first_block q σ = S := by
        intro σ
        rw [hfirst,← heT]
        exact Finset.image_injective e.injective |>.eq_iff
  4. The relation $U$ is bad under $\sigma \circ e$ if and only if $R$ is bad under $\sigma$.

    A relation is bad if there is a non-trivial block subset $B$ such that related pairs belong to $B$ either both or neither. By `hblock`, the block of $e(x)$ under $\sigma \circ e$ is the block of $x$ under $\sigma$. Because $U(e(x), e(y)) \leftrightarrow R(x, y)$ by hypothesis `heR` and $e$ is surjective, pairs related by $R$ correspond bijectively to pairs related by $U$. Thus, a subset of blocks $B$ witnesses badness for $U$ under $\sigma \circ e$ if and only if it witnesses badness for $R$ under $\sigma$.

    lines 40–55

      have hbad : ∀ σ : Equiv.Perm (Fin (3*q)),
          wild_joint_bad_relation q (wild_joint_block q (σ.trans e)) U ↔
          wild_joint_bad_relation q (wild_joint_block q σ) R := by
        intro σ
        constructor
        · rintro ⟨B,hB,hBU,hBR⟩
          refine ⟨B,hB,hBU,?_⟩
          intro x y hxy
          have hh := hBR (e x) (e y) ((heR x y).mpr hxy)
          simpa only [hblock] using hh
        · rintro ⟨B,hB,hBU,hBR⟩
          refine ⟨B,hB,hBU,?_⟩
          intro x y hxy
          obtain ⟨x,rfl⟩ := e.surjective x
          obtain ⟨y,rfl⟩ := e.surjective y
          simpa only [hblock] using hBR x y ((heR x y).mp hxy)
  5. For any boolean flag `extra`, the set of permutations with first block $S$ (and bad for $R$ if `extra = true`) has the same cardinality as the corresponding set for $T$ and $U$.

    We apply `card_bij` with the map $\sigma \mapsto \sigma \circ e$. This map preserves the membership conditions by `hfirstiff` and `hbad`. It is injective because $\sigma \circ e = \tau \circ e$ implies $\sigma(x) = \tau(x)$ for all $x$ via $e$'s injectivity, yielding $\sigma = \tau$ by `Equiv.ext`. It is surjective because any target permutation $\tau$ is the image of $\tau \circ e^{-1}$, which satisfies the required conditions since $(\tau \circ e^{-1}) \circ e = \tau$.

    lines 56–85

    uses card_bij, Equiv.ext, congrArg

      have hcount (extra : Bool) :
          (univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>
            wild_joint_first_block q σ = S ∧
              (extra = true → wild_joint_bad_relation q (wild_joint_block q σ)
                R)).card =
          (univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>
            wild_joint_first_block q σ = T ∧
              (extra = true → wild_joint_bad_relation q (wild_joint_block q σ)
                U)).card := by
        apply card_bij (fun σ _ => σ.trans e)
        · intro σ hσ
          simp only [mem_filter,mem_univ,true_and] at hσ ⊢
          exact ⟨(hfirstiff σ).mpr hσ.1,fun h => (hbad σ).mpr (hσ.2 h)⟩
        · intro σ _ τ _ h
          apply Equiv.ext
          intro x
          have hh := congrArg (fun a : Equiv.Perm (Fin (3*q)) => a x) h
          exact e.injective hh
        · intro τ hτ
          have hc : (τ.trans e.symm).trans e = τ := by ext x; simp
          refine ⟨τ.trans e.symm,?_,hc⟩
          simp only [mem_filter,mem_univ,true_and] at hτ ⊢
          constructor
          · apply (hfirstiff _).mp
            rw [hc]
            exact hτ.1
          · intro h
            apply (hbad _).mp
            rw [hc]
            exact hτ.2 h
  6. The conditional whole-bad probabilities given first block $S$ under $R$ and given first block $T$ under $U$ are equal.

    Setting `extra = true` in `hcount` equates the numerators of the two conditional probability ratios (permutations whose first block matches and for which the relation is bad). Setting `extra = false` makes the badness implication vacuously true (`false_implies`), which equates the denominators (all permutations with the given first block). Rewriting both the numerator and denominator counts by these equalities finishes the proof.

    lines 86–89

    uses Bool.false_eq_true, false_implies, and_true, forall_const

      have hnum := hcount true
      have hden := hcount false
      simp only [Bool.false_eq_true, false_implies, and_true, forall_const] at hnum hden
      rw [hnum,hden]
Fin.ext
Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
true_and
The conjunction `True ∧ p` simplifies to `p`.
Finset.image_injective
If `f` is an injective function, then the finset image operation `Finset.image f` is also injective.
card_bij
Two finite sets have equal cardinality if there exists a bijection (an injective and surjective map) between them.
Equiv.ext
Two equivalences (or permutations) are equal if they agree pointwise on all inputs.
congrArg
Applying a function to equal arguments produces equal results: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
Bool.false_eq_true
The equality `false = true` in `Bool` evaluates to `False`.
false_implies
An implication with a false antecedent, `False → p`, is logically equivalent to `True`.
and_true
The conjunction `p ∧ True` simplifies to `p`.
forall_const
A universal quantification over a nonempty domain of a constant proposition is equivalent to the proposition itself.

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 6000000set_option maxRecDepth 20000set_option synthInstance.maxSize 10000theorem wild_joint_conditioned_bad_probability_transport    (q : ℕ) (R U : Fin (3*q) → Fin (3*q) → Prop)    (S T : Finset (Fin (3*q))) (e : Equiv.Perm (Fin (3*q)))    (heT : S.image e = T)    (heR : ∀ x y, U (e x) (e y) ↔ R x y) :    (((univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>      wild_joint_first_block q σ = S ∧ wild_joint_bad_relation q (wild_joint_block q σ) R).card : ℝ) /      (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = S).card) =    (((univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>      wild_joint_first_block q σ = T ∧ wild_joint_bad_relation q (wild_joint_block q σ) U).card : ℝ) /      (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = T).card) := by  classical  have hblock : ∀ (σ : Equiv.Perm (Fin (3*q))) x,      wild_joint_block q (σ.trans e) (e x) = wild_joint_block q σ x := by    intro σ x    apply Fin.ext    simp [wild_joint_block]  have hfirst : ∀ σ : Equiv.Perm (Fin (3*q)),      wild_joint_first_block q (σ.trans e) = (wild_joint_first_block q σ).image e := by    intro σ    ext x    simp only [wild_joint_first_block,mem_filter,mem_univ,true_and,mem_image]    constructor    · intro hx      refine ⟨e.symm x,?_,e.apply_symm_apply x⟩      exact hx    · rintro ⟨y,hy,rfl⟩      simpa using hy  have hfirstiff : ∀ σ : Equiv.Perm (Fin (3*q)),      wild_joint_first_block q (σ.trans e) = T ↔ wild_joint_first_block q σ = S := by    intro σ    rw [hfirst,← heT]    exact Finset.image_injective e.injective |>.eq_iff  have hbad : ∀ σ : Equiv.Perm (Fin (3*q)),      wild_joint_bad_relation q (wild_joint_block q (σ.trans e)) U ↔      wild_joint_bad_relation q (wild_joint_block q σ) R := by    intro σ    constructor    · rintro ⟨B,hB,hBU,hBR⟩      refine ⟨B,hB,hBU,?_⟩      intro x y hxy      have hh := hBR (e x) (e y) ((heR x y).mpr hxy)      simpa only [hblock] using hh    · rintro ⟨B,hB,hBU,hBR⟩      refine ⟨B,hB,hBU,?_⟩      intro x y hxy      obtain ⟨x,rfl⟩ := e.surjective x      obtain ⟨y,rfl⟩ := e.surjective y      simpa only [hblock] using hBR x y ((heR x y).mp hxy)  have hcount (extra : Bool) :      (univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>        wild_joint_first_block q σ = S ∧          (extra = true → wild_joint_bad_relation q (wild_joint_block q σ)            R)).card =      (univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>        wild_joint_first_block q σ = T ∧          (extra = true → wild_joint_bad_relation q (wild_joint_block q σ)            U)).card := by    apply card_bij (fun σ _ => σ.trans e)    · intro σ hσ      simp only [mem_filter,mem_univ,true_and] at hσ ⊢      exact ⟨(hfirstiff σ).mpr hσ.1,fun h => (hbad σ).mpr (hσ.2 h)⟩    · intro σ _ τ _ h      apply Equiv.ext      intro x      have hh := congrArg (fun a : Equiv.Perm (Fin (3*q)) => a x) h      exact e.injective hh    · intro τ hτ      have hc : (τ.trans e.symm).trans e = τ := by ext x; simp      refine ⟨τ.trans e.symm,?_,hc⟩      simp only [mem_filter,mem_univ,true_and] at hτ ⊢      constructor      · apply (hfirstiff _).mp        rw [hc]        exact hτ.1      · intro h        apply (hbad _).mp        rw [hc]        exact hτ.2 h  have hnum := hcount true  have hden := hcount false  simp only [Bool.false_eq_true, false_implies, and_true, forall_const] at hnum hden  rw [hnum,hden]
See it in the graphDiscuss this resultChallenge it