AFTD Auto-Formalizing Theoretical Domains

forest_carpool_disjoint_components_independent

theoremverified

If appending the edge u-v to the given prefix yields a forest, then under uniformly random prefix coins the two endpoint final discrepancies are independent, expressed as exact joint and marginal counts.

Statement

theorem forest_carpool_disjoint_components_independent (n : ℕ)
    (edges : List (Fin n × Fin n)) (u v : Fin n)
    (hf : CarpoolForestEdgeSequence n (edges ++ [(u, v)])) (a b : ℤ) :
  (Finset.univ.filter (fun r : Fin edges.length → Bool =>
    forest_carpool_final_discrepancy n edges r u = a ∧
    forest_carpool_final_discrepancy n edges r v = b)).card * 2 ^ edges.length =
  (Finset.univ.filter (fun r : Fin edges.length → Bool =>
    forest_carpool_final_discrepancy n edges r u = a)).card *
  (Finset.univ.filter (fun r : Fin edges.length → Bool =>
    forest_carpool_final_discrepancy n edges r v = b)).card
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

The proof, explained

The independence of the final discrepancies at u and v is proven via a bijective counting argument on pairs of coin sequences. Because appending the edge (u, v) preserves the acyclicity of the prefix, u and v lie in disconnected components of the prefix graph. Using the component locality of the carpool discrepancy process, swapping the coin flips on u's connected component between two independent coin sequences preserves the discrepancy at u while adopting the discrepancy at v from the second sequence. This mixing operation forms an involution on pairs of coin sequences that maps the product of the marginal events to the joint event paired with the universal set, equating the product of the marginal counts to the joint count scaled by 2^(edges.length).

  1. Vertices u and v belong to different connected components of the prefix graph Γ, and we define an operation that mixes two coin sequences based on reachability from u.

    Because appending (u, v) to the edge sequence still forms a forest, u and v cannot already be connected in the prefix graph Γ (forest_carpool_append_edge_disconnected). We define predicates P(r) and Q(r) stating that the final discrepancies at u and v equal a and b, respectively. The function mix(r, s) blends two coin sequences r and s by taking the coin from r on edges whose initial vertex is reachable from u, and from s otherwise.

    lines 11–17

    uses forest_carpool_append_edge_disconnected

      classical
      have huv := forest_carpool_append_edge_disconnected n edges u v hf
      set Γ := SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}
      set P : (Fin edges.length → Bool) → Prop := fun r => forest_carpool_final_discrepancy n edges r u = a
      set Q : (Fin edges.length → Bool) → Prop := fun r => forest_carpool_final_discrepancy n edges r v = b
      let mix : (Fin edges.length → Bool) → (Fin edges.length → Bool) → (Fin edges.length → Bool) :=
        fun r s i => if Γ.Reachable u (edges.get i).1 then r i else s i
  2. The event P(mix(r, s)) depends only on r, that is, P(mix(r, s)) ↔ P(r).

    By discrepancy locality (forest_carpool_component_coin_locality), the discrepancy at u depends only on coins for edges reachable from u in Γ. Since mix(r, s) agrees with r on all edges whose initial vertex is reachable from u (by if_pos), the discrepancy at u under mix(r, s) equals that under r.

    lines 18–24

    uses forest_carpool_component_coin_locality, if_pos

      have hP : ∀ r s, P (mix r s) ↔ P r := by
        intro r s
        simp only [P]
        rw [forest_carpool_component_coin_locality n edges u (mix r s) r]
        intro i hi
        have hi' : Γ.Reachable u (edges.get i).1 := hi
        simp only [mix, if_pos hi']
  3. The event Q(mix(r, s)) depends only on s, that is, Q(mix(r, s)) ↔ Q(s).

    Similarly, the discrepancy at v depends only on edges reachable from v (forest_carpool_component_coin_locality). If any edge reachable from v were also reachable from u, then u and v would be connected, contradicting that u and v are disconnected in Γ. Thus, no edge reachable from v is reachable from u, so mix(r, s) agrees with s on all edges reachable from v (by if_neg), ensuring the discrepancy at v under mix(r, s) equals that under s.

    lines 25–31

    uses forest_carpool_component_coin_locality, if_neg

      have hQ : ∀ r s, Q (mix r s) ↔ Q s := by
        intro r s
        simp only [Q]
        rw [forest_carpool_component_coin_locality n edges v (mix r s) s]
        intro i hi
        have : ¬ Γ.Reachable u (edges.get i).1 := fun h => huv (h.trans hi.symm)
        simp only [mix, if_neg this]
  4. The mapping φ(r, s) = (mix(r, s), mix(s, r)) is an involution on pairs of coin sequences.

    Pointwise at each edge index, mix(mix(r, s), mix(s, r)) evaluates to r regardless of whether the edge is reachable from u or not (via split_ifs). Applying this coordinate-wise identity shows φ(φ(p)) = p for all pairs p.

    lines 32–37

      have hmix : ∀ r s, mix (mix r s) (mix s r) = r := by
        intro r s; funext i; simp only [mix]; split_ifs <;> rfl
      let φ : (Fin edges.length → Bool) × (Fin edges.length → Bool) →
          (Fin edges.length → Bool) × (Fin edges.length → Bool) := fun p => (mix p.1 p.2, mix p.2 p.1)
      have hφ : ∀ p, φ (φ p) = p := by
        rintro ⟨r, s⟩; simp only [φ, hmix]
  5. The number of pairs (r, s) satisfying P(r) ∧ Q(s) equals the number of pairs satisfying P(r) ∧ Q(r).

    We establish a bijection between the two sets using φ and Finset.card_nbij'. Because φ is an involution, it is its own inverse. When P(r) ∧ Q(s) holds, both P and Q hold on mix(r, s) because P(mix(r, s)) ↔ P(r) and Q(mix(r, s)) ↔ Q(s). Conversely, when P(r) ∧ Q(r) holds, the first component mix(r, s) satisfies P and the second component mix(s, r) satisfies Q. Membership conditions are simplified using basic finset and set properties (Finset.coe_filter, Finset.mem_product, Finset.mem_univ, true_and, Set.mem_ofPred_eq).

    lines 38–50

    uses Finset.card_nbij', Finset.coe_filter, Finset.mem_product, Finset.mem_univ, true_and, Set.mem_ofPred_eq

      have h1 : ((Finset.univ ×ˢ Finset.univ).filter
          (fun p : (Fin edges.length → Bool) × (Fin edges.length → Bool) => P p.1 ∧ Q p.2)).card =
          ((Finset.univ ×ˢ Finset.univ).filter
          (fun p : (Fin edges.length → Bool) × (Fin edges.length → Bool) => P p.1 ∧ Q p.1)).card := by
        refine Finset.card_nbij' φ φ ?_ ?_ (fun p _ => hφ p) (fun p _ => hφ p)
        · rintro ⟨r, s⟩ hp
          simp only [Finset.coe_filter, Finset.mem_product, Finset.mem_univ, true_and,
            Set.mem_ofPred_eq] at hp ⊢
          exact ⟨(hP r s).mpr hp.1, (hQ r s).mpr hp.2⟩
        · rintro ⟨r, s⟩ hp
          simp only [Finset.coe_filter, Finset.mem_product, Finset.mem_univ, true_and,
            Set.mem_ofPred_eq] at hp ⊢
          exact ⟨(hP r s).mpr hp.1, (hQ s r).mpr hp.2⟩
  6. The product sets decompose into Cartesian products of marginal fibers: {(r, s) | P(r) ∧ Q(s)} = {r | P(r)} ×ˢ {s | Q(s)} and {(r, s) | P(r) ∧ Q(r)} = {r | P(r) ∧ Q(r)} ×ˢ univ.

    By extensionality and simplifying membership in Cartesian products, the condition P(r) ∧ Q(s) factors into separate constraints on r and s, producing the Cartesian product of the fibers of P and Q. The condition P(r) ∧ Q(r) constrains only r and leaves s unrestricted, producing the Cartesian product of the joint fiber with the entire universe of coin sequences.

    lines 51–58

      have h2 : ((Finset.univ ×ˢ Finset.univ).filter
          (fun p : (Fin edges.length → Bool) × (Fin edges.length → Bool) => P p.1 ∧ Q p.2)) =
          (Finset.univ.filter P) ×ˢ (Finset.univ.filter Q) := by
        ext ⟨r, s⟩; simp
      have h3 : ((Finset.univ ×ˢ Finset.univ).filter
          (fun p : (Fin edges.length → Bool) × (Fin edges.length → Bool) => P p.1 ∧ Q p.1)) =
          (Finset.univ.filter (fun r => P r ∧ Q r)) ×ˢ Finset.univ := by
        ext ⟨r, s⟩; simp
  7. The joint count multiplied by 2^(edges.length) equals the product of the marginal counts.

    Taking cardinalities in the equicardinality of step 5 using the product decompositions of step 6 (Finset.card_product, Finset.card_univ), the left side is |{r | P(r)}| · |{s | Q(s)}| and the right side is |{r | P(r) ∧ Q(r)}| · |univ|. The size of the universe of coin sequences (Fin edges.length → Bool) is 2^(edges.length) by Fintype.card_fun, Fintype.card_bool, and Fintype.card_fin. Symmetrizing the resulting equality yields the theorem.

    lines 59–62

    uses Finset.card_product, Finset.card_univ, Fintype.card_fun, Fintype.card_bool, Fintype.card_fin

      have h4 := h1
      rw [h2, h3, Finset.card_product, Finset.card_product, Finset.card_univ] at h4
      simp only [Fintype.card_fun, Fintype.card_bool, Fintype.card_fin] at h4
      exact h4.symm
forest_carpool_append_edge_disconnected
If appending edge (u, v) to an edge sequence preserves the forest property, then u and v are not reachable from each other in the graph formed by the prefix edges.
forest_carpool_component_coin_locality
The final discrepancy at a vertex v depends only on the coin choices on edges reachable from v.
if_pos
A conditional expression if c then t else e evaluates to t when the condition c holds.
if_neg
A conditional expression if c then t else e evaluates to e when the condition c does not hold.
Finset.card_nbij'
Two finsets have the same cardinality if there exists a map between them with an explicit two-sided inverse on their elements.
Finset.coe_filter
The set coercion of a filtered finset consists of all elements in the finset satisfying the predicate.
Finset.mem_product
A pair belongs to the Cartesian product s ×ˢ t of two finsets if and only if its first component is in s and its second is in t.
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.
true_and
For any proposition p, the conjunction True ∧ p is equivalent to p.
Set.mem_ofPred_eq
Membership of an element x in a set comprehension {y | p y} is equivalent to p x.
Finset.card_product
The cardinality of the Cartesian product of two finsets is the product of their individual cardinalities.
Finset.card_univ
The cardinality of Finset.univ for a finite type is the cardinality of the type itself.
Fintype.card_fun
The cardinality of the function type α → β is |β|^|α|.
Fintype.card_bool
The type Bool of booleans has exactly 2 elements.
Fintype.card_fin
The type Fin n has exactly n elements.

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 forest_carpool_disjoint_components_independent (n : ℕ)    (edges : List (Fin n × Fin n)) (u v : Fin n)    (hf : CarpoolForestEdgeSequence n (edges ++ [(u, v)])) (a b : ℤ) :  (Finset.univ.filter (fun r : Fin edges.length → Bool =>    forest_carpool_final_discrepancy n edges r u = a ∧    forest_carpool_final_discrepancy n edges r v = b)).card * 2 ^ edges.length =  (Finset.univ.filter (fun r : Fin edges.length → Bool =>    forest_carpool_final_discrepancy n edges r u = a)).card *  (Finset.univ.filter (fun r : Fin edges.length → Bool =>    forest_carpool_final_discrepancy n edges r v = b)).card := by  classical  have huv := forest_carpool_append_edge_disconnected n edges u v hf  set Γ := SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}  set P : (Fin edges.length → Bool) → Prop := fun r => forest_carpool_final_discrepancy n edges r u = a  set Q : (Fin edges.length → Bool) → Prop := fun r => forest_carpool_final_discrepancy n edges r v = b  let mix : (Fin edges.length → Bool) → (Fin edges.length → Bool) → (Fin edges.length → Bool) :=    fun r s i => if Γ.Reachable u (edges.get i).1 then r i else s i  have hP : ∀ r s, P (mix r s) ↔ P r := by    intro r s    simp only [P]    rw [forest_carpool_component_coin_locality n edges u (mix r s) r]    intro i hi    have hi' : Γ.Reachable u (edges.get i).1 := hi    simp only [mix, if_pos hi']  have hQ : ∀ r s, Q (mix r s) ↔ Q s := by    intro r s    simp only [Q]    rw [forest_carpool_component_coin_locality n edges v (mix r s) s]    intro i hi    have : ¬ Γ.Reachable u (edges.get i).1 := fun h => huv (h.trans hi.symm)    simp only [mix, if_neg this]  have hmix : ∀ r s, mix (mix r s) (mix s r) = r := by    intro r s; funext i; simp only [mix]; split_ifs <;> rfl  let φ : (Fin edges.length → Bool) × (Fin edges.length → Bool) →      (Fin edges.length → Bool) × (Fin edges.length → Bool) := fun p => (mix p.1 p.2, mix p.2 p.1)  have hφ : ∀ p, φ (φ p) = p := by    rintro ⟨r, s⟩; simp only [φ, hmix]  have h1 : ((Finset.univ ×ˢ Finset.univ).filter      (fun p : (Fin edges.length → Bool) × (Fin edges.length → Bool) => P p.1 ∧ Q p.2)).card =      ((Finset.univ ×ˢ Finset.univ).filter      (fun p : (Fin edges.length → Bool) × (Fin edges.length → Bool) => P p.1 ∧ Q p.1)).card := by    refine Finset.card_nbij' φ φ ?_ ?_ (fun p _ => hφ p) (fun p _ => hφ p)    · rintro ⟨r, s⟩ hp      simp only [Finset.coe_filter, Finset.mem_product, Finset.mem_univ, true_and,        Set.mem_ofPred_eq] at hp ⊢      exact ⟨(hP r s).mpr hp.1, (hQ r s).mpr hp.2⟩    · rintro ⟨r, s⟩ hp      simp only [Finset.coe_filter, Finset.mem_product, Finset.mem_univ, true_and,        Set.mem_ofPred_eq] at hp ⊢      exact ⟨(hP r s).mpr hp.1, (hQ s r).mpr hp.2⟩  have h2 : ((Finset.univ ×ˢ Finset.univ).filter      (fun p : (Fin edges.length → Bool) × (Fin edges.length → Bool) => P p.1 ∧ Q p.2)) =      (Finset.univ.filter P) ×ˢ (Finset.univ.filter Q) := by    ext ⟨r, s⟩; simp  have h3 : ((Finset.univ ×ˢ Finset.univ).filter      (fun p : (Fin edges.length → Bool) × (Fin edges.length → Bool) => P p.1 ∧ Q p.1)) =      (Finset.univ.filter (fun r => P r ∧ Q r)) ×ˢ Finset.univ := by    ext ⟨r, s⟩; simp  have h4 := h1  rw [h2, h3, Finset.card_product, Finset.card_product, Finset.card_univ] at h4  simp only [Fintype.card_fun, Fintype.card_bool, Fintype.card_fin] at h4  exact h4.symm
See it in the graphDiscuss this resultChallenge it