forest_carpool_disjoint_components_independent
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
- forest_carpool_final_discrepancyThe final discrepancy of a vertex after greedy orientation of the given edges with the given indexed tie-breaking coins.
- CarpoolForestEdgeSequenceA list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected…
- forest_carpool_append_edge_disconnectedWhen a new edge appended to an edge sequence still forms a forest with no duplicate undirected edges, its endpoints lie in distinct…
- forest_carpool_component_coin_localityTwo coin assignments that agree on every edge in the final connected component of a fixed vertex give the same final greedy discrepancy at…
- Arena.Reachable.transReachability is transitive.
- Used by 1
- forest_carpool_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…
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).
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.
uses
forest_carpool_append_edge_disconnectedclassical 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
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.
uses
forest_carpool_component_coin_locality,if_poshave 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']
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.
uses
forest_carpool_component_coin_locality,if_neghave 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]
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.
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]
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).
uses
Finset.card_nbij',Finset.coe_filter,Finset.mem_product,Finset.mem_univ,true_and,Set.mem_ofPred_eqhave 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⟩
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.
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
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.
uses
Finset.card_product,Finset.card_univ,Fintype.card_fun,Fintype.card_bool,Fintype.card_finhave 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
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.
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