forest_carpool_maximum_fibonacci_tail
For a forest arrival sequence, the probability that any vertex at any prefix has absolute discrepancy at least D is at most four times the number of edges times the Fibonacci tail envelope.
Statement
theorem forest_carpool_maximum_fibonacci_tail (n : ℕ) (edges : List (Fin n × Fin n)) (hf : CarpoolForestEdgeSequence n edges) (D : ℕ) (hD : 1 ≤ D) : (((Finset.univ.filter (fun r : Fin edges.length → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r)))).card : ℝ) / (2 ^ edges.length : ℝ)) ≤ 4 * edges.length * forest_carpool_tail_envelope D
- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- carpool_max_discrepancyThe maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.
- carpool_greedy_orientationsGiven a list of edges and a list of tie-breaking coins, randomized greedy carpooling orients each edge toward the endpoint with smaller…
- 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_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…
- max_vertex_discrepancyThe maximum absolute discrepancy among all vertices for an integer discrepancy vector d on n vertices.
- forest_carpool_tail_envelopeThe proposed one-sided discrepancy tail envelope is 3/8 at level 2 and otherwise two to the negative Fibonacci number of the level.
- 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…
- ValidCarpoolEdgeSequenceA list of edges on n vertices is valid for online carpooling if every arriving edge connects two distinct vertices.
- forest_carpool_final_discrepancyThe final discrepancy of a vertex after greedy orientation of the given edges with the given indexed tie-breaking coins.
- carpool_stepIn online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d…
- Used by 1
- op_1106_forest_carpooling_random_greedy_double_exponential_tailThere exist absolute positive real constants c, C, and a such that for every natural number n, every forest edge sequence of length T ≥ 2…
The proof, explained
To bound the maximum discrepancy over all vertices and all prefixes of a forest arrival sequence, we first show that if discrepancy reaches D at any time, it must reach D immediately following the arrival of an edge incident to that vertex. This reduces the event to the union over all T edges of 4 single-vertex signed prefix events (two endpoints, positive or negative discrepancy). Each such event depends only on coins up to that edge arrival and is bounded by the one-sided Fibonacci tail envelope by symmetry and acyclicity of prefixes, so a union bound over all 4T events gives at most 4 * T times the envelope.
Folding carpool steps over edges and their greedy orientations computes the discrepancy function G.
By induction on the edge list es and case analysis on the coin list cs, the step-by-step foldl matches the recursive definition of the discrepancy function G.
intro es induction es with | nil => intro cs d; simp [carpool_greedy_orientations.aux, G] | cons e es ih => intro cs d cases cs with | nil => simp [carpool_greedy_orientations.aux, G] | cons c cs => simp only [carpool_greedy_orientations.aux, List.zip_cons_cons, List.foldl_cons, G] exact ih cs _
Taking a prefix of length t of the zipped edge-orientation list commutes with the greedy orientation process.
By induction on the edge list es and cases on cs and t, the first t greedy orientations depend only on the first t edges and coins.
theorem take_zip_aux (n : ℕ) : ∀ (es : List (Fin n × Fin n)) (cs : List Bool) (d : Fin n → ℤ) (t : ℕ), (es.zip (carpool_greedy_orientations.aux n es cs d)).take t = (es.take t).zip (carpool_greedy_orientations.aux n (es.take t) (cs.take t) d) := by intro es induction es with | nil => intro cs d t; simp [carpool_greedy_orientations.aux] | cons e es ih => intro cs d t cases cs with | nil => cases t <;> simp [carpool_greedy_orientations.aux] | cons c cs => cases t with | zero => simp [carpool_greedy_orientations.aux] | succ t => simp only [carpool_greedy_orientations.aux, List.zip_cons_cons, List.take_succ_cons] rw [ih]
Appending an edge and coin updates the discrepancy G by a single carpool step.
By induction on es, appending an edge e and coin c to equal-length lists computes G on the initial part and applies one carpool step with the greedy bit.
theorem G_append' (n : ℕ) (e : Fin n × Fin n) (c : Bool) : ∀ (es : List (Fin n × Fin n)) (cs : List Bool) (d : Fin n → ℤ), cs.length = es.length → G n (es ++ [e]) (cs ++ [c]) d = carpool_step n (G n es cs d) e (gbit (G n es cs d) e c) := by intro es induction es with | nil => intro cs d h cases cs with | nil => simp [G] | cons _ _ => simp at h | cons e' es ih => intro cs d h cases cs with | nil => simp at h | cons c' cs => simp only [List.cons_append, G] exact ih cs _ (by simpa using h)
With no edges, the discrepancy function G is the identity.
Case analysis on the coin list cs shows that G with an empty edge list returns the initial discrepancy d unchanged.
theorem G_nil (n : ℕ) (cs : List Bool) (d : Fin n → ℤ) : G n [] cs d = d := by cases cs <;> rfl
If the maximum of a list folded with an accumulator is at least D, then D is bounded by the accumulator or some list element.
By induction on the list l, each step takes max acc x; if D ≤ max acc x, then D ≤ acc or D ≤ x by le_max_iff.
theorem foldl_max_le (D : ℕ) : ∀ (l : List ℕ) (acc : ℕ), D ≤ l.foldl max acc → D ≤ acc ∨ ∃ x ∈ l, D ≤ x := by intro l induction l with | nil => intro acc h; exact Or.inl h | cons x l ih => intro acc h rcases ih _ h with h1 | ⟨y, hy, h2⟩ · rcases le_max_iff.mp h1 with h3 | h3 · exact Or.inl h3 · exact Or.inr ⟨x, by simp, h3⟩ · exact Or.inr ⟨y, by simp [hy], h2⟩
A high discrepancy at vertex w must already occur immediately after some edge arrival incident to w.
By induction on prefix length t: for t = 0 the discrepancy is 0 < D. At step t + 1, if edge es[t] touches w, this step witnesses the claim. Otherwise, es[t] does not touch w, so the discrepancy at w is unchanged from step t, and the induction hypothesis applies.
uses
G_nil,G_append'/-- if some prefix discrepancy is large, it is large right after an edge at that vertex -/ theorem last_touch (n : ℕ) (es : List (Fin n × Fin n)) (cs : List Bool) (hcs : cs.length = es.length) (D : ℕ) (hD : 1 ≤ D) : ∀ t, t ≤ es.length → ∀ w, D ≤ (G n (es.take t) (cs.take t) (fun _ => 0) w).natAbs → ∃ j, ∃ hj : j < es.length, (w = (es[j]).1 ∨ w = (es[j]).2) ∧ D ≤ (G n (es.take (j + 1)) (cs.take (j + 1)) (fun _ => 0) w).natAbs := by intro t induction t with | zero => intro _ w h; simp [G_nil] at h; omega | succ t ih => intro ht w h by_cases hw : w = (es[t]'(by omega)).1 ∨ w = (es[t]'(by omega)).2 · exact ⟨t, by omega, hw, h⟩ · apply ih (by omega) w have hes : es.take (t + 1) = es.take t ++ [es[t]'(by omega)] := by rw [List.take_add_one, List.getElem?_eq_getElem (by omega)]; rfl have hcs' : cs.take (t + 1) = cs.take t ++ [cs[t]'(by omega)] := by rw [List.take_add_one, List.getElem?_eq_getElem (by omega)]; rfl rw [hes, hcs', G_append' n _ _ _ _ _ (by simp [hcs])] at h push Not at hw simpa [carpool_step, hw.1, hw.2] using h
Negating the discrepancy state and flipping the coin inverts the greedy orientation bit.
Unfolding gbit and case splitting on the coin and the ordering of endpoint discrepancies confirms that the greedy choice is inverted.
theorem gbit_neg {n : ℕ} (d : Fin n → ℤ) (e : Fin n × Fin n) (c : Bool) : gbit (fun x => -d x) e (!c) = !(gbit d e c) := by unfold gbit dsimp only cases c <;> split_ifs <;> first | rfl | (exfalso; omega)
A carpool step with negated discrepancy and inverted bit yields the negated new discrepancy.
By function extensionality, updating a negated discrepancy with inverted orientation bit negates the delta on both endpoints.
theorem step_neg {n : ℕ} (d : Fin n → ℤ) (e : Fin n × Fin n) (b : Bool) : carpool_step n (fun x => -d x) e (!b) = fun x => -(carpool_step n d e b x) := by funext x unfold carpool_step cases b <;> simp only [Bool.not_true, Bool.not_false, Bool.false_eq_true, if_true, if_false] <;> split_ifs <;> ring
Inverting all coins and negating the initial discrepancy negates the final discrepancy.
By induction on the edge sequence, using gbit_neg and step_neg at each step to propagate the negation.
uses
gbit_neg,step_negtheorem G_neg (n : ℕ) : ∀ (es : List (Fin n × Fin n)) (cs : List Bool) (d : Fin n → ℤ), G n es (cs.map (!·)) (fun x => -d x) = fun x => -(G n es cs d x) := by intro es induction es with | nil => intro cs d; simp [G_nil] | cons e es ih => intro cs d cases cs with | nil => rfl | cons c cs => simp only [List.map_cons, G] rw [gbit_neg, step_neg, ih]
Cardinality of a filtered finite set is invariant under a bijection of the domain.
We apply Finset.card_nbij' using the bijection Φ and its inverse.
theorem card_comp_equiv'' {γ δ : Type} [Fintype γ] [Fintype δ] (Φ : γ ≃ δ) (f : δ → Prop) [DecidablePred f] : (Finset.univ.filter (fun p => f (Φ p))).card = (Finset.univ.filter f).card := by refine Finset.card_nbij' Φ Φ.symm ?_ ?_ (fun p _ => Φ.symm_apply_apply p) (fun p _ => Φ.apply_symm_apply p) · intro p hp; simpa using hp · intro p hp; simpa using hp
A coin sequence of length T is equivalent to a prefix of length t paired with a suffix of length T - t.
We define splitEquiv by mapping each index i < t to the prefix and each index t + j to the suffix, and verify left and right inverses.
/-- split the coins into a prefix and a suffix -/ def splitEquiv (t T : ℕ) (h : t ≤ T) : (Fin T → Bool) ≃ (Fin t → Bool) × (Fin (T - t) → Bool) where toFun r := (fun i => r ⟨i, by omega⟩, fun j => r ⟨t + j, by omega⟩) invFun p := fun i => if hi : i.val < t then p.1 ⟨i, hi⟩ else p.2 ⟨i - t, by omega⟩ left_inv r := by funext i by_cases hi : i.val < t · simp [hi] · simp only [hi, dite_false]; congr 1; ext; simp; omega right_inv p := by obtain ⟨p1, p2⟩ := p ext j · simp · simp
An event depending only on the first t coins has cardinality scaled by 2^(T - t) in the full space.
Applying splitEquiv, the fiber over each satisfying prefix of length t is the full space of suffixes of length T - t, which has cardinality 2^(T - t).
uses
card_comp_equiv'',splitEquivtheorem marginal (t T : ℕ) (h : t ≤ T) (P : (Fin t → Bool) → Prop) [DecidablePred P] : (Finset.univ.filter (fun r : Fin T → Bool => P (fun i => r ⟨i, by omega⟩))).card = (Finset.univ.filter P).card * 2 ^ (T - t) := by rw [← card_comp_equiv'' (splitEquiv t T h).symm (fun r : Fin T → Bool => P (fun i => r ⟨i, by omega⟩))] have : (Finset.univ.filter (fun p : (Fin t → Bool) × (Fin (T - t) → Bool) => P (fun i => (splitEquiv t T h).symm p ⟨i, by omega⟩))) = (Finset.univ.filter P) ×ˢ Finset.univ := by ext ⟨p1, p2⟩ simp [splitEquiv] rw [this, Finset.card_product, Finset.card_univ, Fintype.card_fun, Fintype.card_bool, Fintype.card_fin]
Any prefix of a forest edge sequence remains a forest edge sequence.
A prefix has a subset of edges, so it preserves distinct non-loop edges, nodup, and acyclicity of the underlying graph.
theorem forest_take (n : ℕ) (es : List (Fin n × Fin n)) (t : ℕ) (hf : CarpoolForestEdgeSequence n es) : CarpoolForestEdgeSequence n (es.take t) := by obtain ⟨hv, hnd, hac⟩ := hf have hsub : ∀ x ∈ es.take t, x ∈ es := fun x hx => List.mem_of_mem_take hx refine ⟨fun x hx => hv x (hsub x hx), ?_, ?_⟩ · rw [List.map_take]; exact hnd.sublist (List.take_sublist _ _) · refine hac.anti ?_ intro x y hxy rw [SimpleGraph.fromEdgeSet_adj] at hxy ⊢ obtain ⟨⟨e', he', hex⟩, hne⟩ := hxy exact ⟨⟨e', hsub e' he', hex⟩, hne⟩
The number of coin sequences where prefix t has signed discrepancy at vertex w at least D is bounded by the envelope times 2^T.
By marginal, the count on T coins is 2^(T - t) times the count on t coins. For positive sign, the one-sided Fibonacci tail bound applies to the prefix forest. For negative sign, flipping all coins inverts the discrepancy by G_neg, reducing to the positive case. Combining with 2^(T - t) * 2^t = 2^T yields the bound.
uses
marginal,forest_carpool_final_one_sided_fibonacci_tail,forest_take,G_neg,card_comp_equiv''/-- the one-sided bound for a prefix, with unused suffix coins, in counting form -/ theorem prefix_bound (n : ℕ) (es : List (Fin n × Fin n)) (hf : CarpoolForestEdgeSequence n es) (t : ℕ) (ht : t ≤ es.length) (w : Fin n) (D : ℕ) (hD : 1 ≤ D) (sgn : Bool) : ((Finset.univ.filter (fun r : Fin es.length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * G n (es.take t) ((List.ofFn r).take t) (fun _ => 0) w)).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ es.length := by have hlen : (es.take t).length = t := by simp; omega -- restrict coins have hres : ∀ r : Fin es.length → Bool, (List.ofFn r).take t = List.ofFn (fun i : Fin (es.take t).length => r ⟨i, by omega⟩) := by intro r apply List.ext_getElem · simp · intro i h1 h2; simp have hcount := marginal (es.take t).length es.length (by omega) (fun r' => (D : ℤ) ≤ (if sgn then 1 else -1) * forest_carpool_final_discrepancy n (es.take t) r' w) have heq : (Finset.univ.filter (fun r : Fin es.length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * G n (es.take t) ((List.ofFn r).take t) (fun _ => 0) w)) = Finset.univ.filter (fun r : Fin es.length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * forest_carpool_final_discrepancy n (es.take t) (fun i => r ⟨i, by omega⟩) w) := by ext r; simp only [Finset.mem_filter, Finset.mem_univ, true_and] rw [final_eq, hres] rw [heq, hcount] -- the prefix bound have hpre : ((Finset.univ.filter (fun r' : Fin (es.take t).length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * forest_carpool_final_discrepancy n (es.take t) r' w)).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ (es.take t).length := by have hb := forest_carpool_final_one_sided_fibonacci_tail n (es.take t) (forest_take n es t hf) w D hD rw [div_le_iff₀ (by positivity)] at hb cases sgn · -- negative side: flip all coins let flip : (Fin (es.take t).length → Bool) ≃ (Fin (es.take t).length → Bool) := { toFun := fun r i => !r i, invFun := fun r i => !r i, left_inv := fun r => by funext i; simp, right_inv := fun r => by funext i; simp } have hneg : ∀ r', forest_carpool_final_discrepancy n (es.take t) (flip r') w = - forest_carpool_final_discrepancy n (es.take t) r' w := by intro r' rw [final_eq, final_eq] have : List.ofFn (flip r') = (List.ofFn r').map (!·) := by rw [List.map_ofFn]; rfl rw [this] have := congrFun (G_neg n (es.take t) (List.ofFn r') (fun _ => 0)) w simpa using this rw [← card_comp_equiv'' flip] at hb simp only [hneg] at hb simp only [Bool.false_eq_true, if_false, neg_one_mul] exact hb · simp only [if_true, one_mul] exact hb rw [Nat.cast_mul, Nat.cast_pow, Nat.cast_two] have hsplit : (2 : ℝ) ^ es.length = 2 ^ (es.take t).length * 2 ^ (es.length - (es.take t).length) := by rw [← pow_add]; congr 1; omega rw [hsplit, ← mul_assoc] exact mul_le_mul_of_nonneg_right hpre (by positivity)
Define T and the event that vertex w has signed discrepancy at least D after edge arrival j + 1.
We set T = edges.length and define ev(j, w, sgn) as the set of coin sequences where the signed discrepancy of vertex w after the prefix of length j + 1 is at least D.
end ForestCarpoolMax theorem forest_carpool_maximum_fibonacci_tail (n : ℕ) (edges : List (Fin n × Fin n)) (hf : CarpoolForestEdgeSequence n edges) (D : ℕ) (hD : 1 ≤ D) : (((Finset.univ.filter (fun r : Fin edges.length → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r)))).card : ℝ) / (2 ^ edges.length : ℝ)) ≤ 4 * edges.length * forest_carpool_tail_envelope D := by classical open ForestCarpoolLocal ForestCarpoolMax in set T := edges.length with hT let ev : Fin T → Fin n → Bool → Finset (Fin T → Bool) := fun j w sgn => Finset.univ.filter (fun r : Fin edges.length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * G n (edges.take (j + 1)) ((List.ofFn r).take (j + 1)) (fun _ => 0) w)
If the maximum discrepancy reaches D, then for some edge j and one of its endpoints, the discrepancy after step j + 1 is at least D in absolute value.
If the maximum over all prefixes is at least D, foldl_max_le shows some prefix i has discrepancy at least D at some vertex w. By last_touch, this already occurred at some step j < T where edge j touches w, so the discrepancy after step j + 1 is at least D in absolute value, placing the outcome in the union of the 4 endpoint events for edge j.
uses
foldl_max_le,take_zip_aux,foldl_aux,last_touchhave hsub : Finset.univ.filter (fun r : Fin edges.length → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r))) ⊆ Finset.univ.biUnion (fun j : Fin T => ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false) := by intro r hr simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hr unfold carpool_max_discrepancy carpool_discrepancies carpool_greedy_orientations at hr rcases foldl_max_le D _ 0 hr with h0 | ⟨x, hx, hDx⟩ · omega obtain ⟨dv, hdv, rfl⟩ := List.mem_map.mp hx obtain ⟨i, hi, rfl⟩ := List.getElem_of_mem hdv rw [List.getElem_scanl, take_zip_aux, foldl_aux] at hDx unfold max_vertex_discrepancy at hDx obtain ⟨w, _, hw⟩ := (Finset.le_sup_iff (lt_of_lt_of_le (by decide : (⊥ : ℕ) < 1) hD)).mp hDx have hilen : i ≤ edges.length := by simp [List.length_scanl] at hi; omega obtain ⟨j, hj, hjw, hjD⟩ := last_touch n edges (List.ofFn r) (by simp) D hD i hilen w hw simp only [Finset.mem_biUnion, Finset.mem_univ, true_and, Finset.mem_union] refine ⟨⟨j, hj⟩, ?_⟩ simp only [ev, Finset.mem_filter, Finset.mem_univ, true_and, if_true, if_false, Bool.false_eq_true, one_mul, neg_one_mul] have habs : (D : ℤ) ≤ G n (edges.take (j + 1)) ((List.ofFn r).take (j + 1)) (fun _ => 0) w ∨ (D : ℤ) ≤ -G n (edges.take (j + 1)) ((List.ofFn r).take (j + 1)) (fun _ => 0) w := by omega rcases hjw with rfl | rfl <;> rcases habs with h | h <;> simp [h]
For each edge j, the union of its 4 endpoint events has cardinality at most 4 * envelope(D) * 2^T.
The union of the 4 events (two endpoints, positive and negative sign) is bounded by the sum of their cardinalities by Finset.card_union_le. Each of the 4 events has cardinality at most envelope(D) * 2^T by prefix_bound.
uses
prefix_bound,Finset.card_union_lehave hcard := (Finset.card_le_card hsub).trans (Finset.card_biUnion_le) have hbound : ∀ j : Fin T, ((ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false).card : ℝ) ≤ 4 * (forest_carpool_tail_envelope D * 2 ^ edges.length) := by intro j have h1 : ((ev j (edges[j]).1 true).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ edges.length := prefix_bound n edges hf (j + 1) j.2 (edges[j]).1 D hD true have h2 : ((ev j (edges[j]).1 false).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ edges.length := prefix_bound n edges hf (j + 1) j.2 (edges[j]).1 D hD false have h3 : ((ev j (edges[j]).2 true).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ edges.length := prefix_bound n edges hf (j + 1) j.2 (edges[j]).2 D hD true have h4 : ((ev j (edges[j]).2 false).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ edges.length := prefix_bound n edges hf (j + 1) j.2 (edges[j]).2 D hD false have hu := Finset.card_union_le (ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true) (ev j (edges[j]).2 false) have hu2 := Finset.card_union_le (ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false) (ev j (edges[j]).2 true) have hu3 := Finset.card_union_le (ev j (edges[j]).1 true) (ev j (edges[j]).1 false) have : ((ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false).card : ℝ) ≤ (ev j (edges[j]).1 true).card + (ev j (edges[j]).1 false).card + (ev j (edges[j]).2 true).card + (ev j (edges[j]).2 false).card := by exact_mod_cast (by omega) linarith
The probability that the maximum discrepancy reaches D is at most 4 * edges.length * envelope(D).
Summing the bound over all T = edges.length edges gives at most T * 4 * envelope(D) * 2^T by Finset.sum_le_sum. Dividing both sides by 2^T via div_le_iff₀ yields the final probability bound 4 * T * envelope(D).
uses
Finset.sum_le_sum,div_le_iff₀have hsum : ((Finset.univ.filter (fun r : Fin edges.length → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r)))).card : ℝ) ≤ T * (4 * (forest_carpool_tail_envelope D * 2 ^ edges.length)) := by calc _ ≤ ((∑ j : Fin T, (ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false).card : ℕ) : ℝ) := by exact_mod_cast hcard _ = ∑ j : Fin T, ((ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false).card : ℝ) := by push_cast; rfl _ ≤ ∑ _j : Fin T, 4 * (forest_carpool_tail_envelope D * 2 ^ edges.length) := Finset.sum_le_sum (fun j _ => hbound j) _ = _ := by simp rw [div_le_iff₀ (by positivity)] linarith
G_nil- Running the carpool process on an empty list of edges leaves the initial discrepancy unchanged.
G_append'- Appending an edge and a coin to equal-length histories updates the cumulative discrepancy by a single carpool step using the greedy bit for that edge.
gbit_neg- Negating the discrepancy state and inverting the coin flips the greedy orientation bit.
step_neg- A carpool step with negated discrepancy and an inverted orientation bit negates the updated discrepancy.
card_comp_equiv''- Precomposing a predicate on a finite set with a bijection preserves the cardinality of the filtered subset.
splitEquiv- A sequence of T boolean choices is in canonical bijection with the product of its prefix of length t and suffix of length T - t.
marginal- The number of length-T boolean sequences satisfying a condition that depends only on the first t bits equals the number of length-t sequences satisfying it times 2^(T - t).
forest_carpool_final_one_sided_fibonacci_tail- For a forest edge sequence, the probability that the final discrepancy at a given vertex is at least D is at most the Fibonacci tail envelope.
forest_take- Any prefix of an acyclic edge sequence with distinct edges is also an acyclic edge sequence with distinct edges.
G_neg- Inverting all coins and negating the initial discrepancy negates the resulting discrepancy at every vertex.
foldl_max_le- If the fold of max over a list is at least D, then either the initial accumulator or some element in the list is at least D.
take_zip_aux- The prefix of length t of the zipped edge and greedy orientation sequence equals the zip of the prefix of edges and the greedy orientations computed from the prefixes.
foldl_aux- Folding the carpool step over edges and greedy orientations matches the discrepancy accumulated by G.
last_touch- If a vertex has absolute discrepancy at least D ≥ 1 at time t, it already had absolute discrepancy at least D immediately after some edge arrival incident to that vertex.
prefix_bound- For any prefix length t, vertex w, and sign, the number of coin sequences where the signed discrepancy of w at prefix t is at least D is bounded by the Fibonacci tail envelope times 2^T.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.sum_le_sum- A sum of termwise smaller or equal real quantities is at most the sum of the larger quantities.
div_le_iff₀- For positive c, b / c ≤ a is equivalent to b ≤ a * c.
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.
namespace ForestCarpoolMaxopen ForestCarpoolLocaltheorem foldl_aux (n : ℕ) : ∀ (es : List (Fin n × Fin n)) (cs : List Bool) (d : Fin n → ℤ), (es.zip (carpool_greedy_orientations.aux n es cs d)).foldl (fun d (e, b) => carpool_step n d e b) d = G n es cs d := by intro es induction es with | nil => intro cs d; simp [carpool_greedy_orientations.aux, G] | cons e es ih => intro cs d cases cs with | nil => simp [carpool_greedy_orientations.aux, G] | cons c cs => simp only [carpool_greedy_orientations.aux, List.zip_cons_cons, List.foldl_cons, G] exact ih cs _theorem take_zip_aux (n : ℕ) : ∀ (es : List (Fin n × Fin n)) (cs : List Bool) (d : Fin n → ℤ) (t : ℕ), (es.zip (carpool_greedy_orientations.aux n es cs d)).take t = (es.take t).zip (carpool_greedy_orientations.aux n (es.take t) (cs.take t) d) := by intro es induction es with | nil => intro cs d t; simp [carpool_greedy_orientations.aux] | cons e es ih => intro cs d t cases cs with | nil => cases t <;> simp [carpool_greedy_orientations.aux] | cons c cs => cases t with | zero => simp [carpool_greedy_orientations.aux] | succ t => simp only [carpool_greedy_orientations.aux, List.zip_cons_cons, List.take_succ_cons] rw [ih]theorem G_append' (n : ℕ) (e : Fin n × Fin n) (c : Bool) : ∀ (es : List (Fin n × Fin n)) (cs : List Bool) (d : Fin n → ℤ), cs.length = es.length → G n (es ++ [e]) (cs ++ [c]) d = carpool_step n (G n es cs d) e (gbit (G n es cs d) e c) := by intro es induction es with | nil => intro cs d h cases cs with | nil => simp [G] | cons _ _ => simp at h | cons e' es ih => intro cs d h cases cs with | nil => simp at h | cons c' cs => simp only [List.cons_append, G] exact ih cs _ (by simpa using h)theorem G_nil (n : ℕ) (cs : List Bool) (d : Fin n → ℤ) : G n [] cs d = d := by cases cs <;> rfltheorem foldl_max_le (D : ℕ) : ∀ (l : List ℕ) (acc : ℕ), D ≤ l.foldl max acc → D ≤ acc ∨ ∃ x ∈ l, D ≤ x := by intro l induction l with | nil => intro acc h; exact Or.inl h | cons x l ih => intro acc h rcases ih _ h with h1 | ⟨y, hy, h2⟩ · rcases le_max_iff.mp h1 with h3 | h3 · exact Or.inl h3 · exact Or.inr ⟨x, by simp, h3⟩ · exact Or.inr ⟨y, by simp [hy], h2⟩/-- if some prefix discrepancy is large, it is large right after an edge at that vertex -/theorem last_touch (n : ℕ) (es : List (Fin n × Fin n)) (cs : List Bool) (hcs : cs.length = es.length) (D : ℕ) (hD : 1 ≤ D) : ∀ t, t ≤ es.length → ∀ w, D ≤ (G n (es.take t) (cs.take t) (fun _ => 0) w).natAbs → ∃ j, ∃ hj : j < es.length, (w = (es[j]).1 ∨ w = (es[j]).2) ∧ D ≤ (G n (es.take (j + 1)) (cs.take (j + 1)) (fun _ => 0) w).natAbs := by intro t induction t with | zero => intro _ w h; simp [G_nil] at h; omega | succ t ih => intro ht w h by_cases hw : w = (es[t]'(by omega)).1 ∨ w = (es[t]'(by omega)).2 · exact ⟨t, by omega, hw, h⟩ · apply ih (by omega) w have hes : es.take (t + 1) = es.take t ++ [es[t]'(by omega)] := by rw [List.take_add_one, List.getElem?_eq_getElem (by omega)]; rfl have hcs' : cs.take (t + 1) = cs.take t ++ [cs[t]'(by omega)] := by rw [List.take_add_one, List.getElem?_eq_getElem (by omega)]; rfl rw [hes, hcs', G_append' n _ _ _ _ _ (by simp [hcs])] at h push Not at hw simpa [carpool_step, hw.1, hw.2] using htheorem gbit_neg {n : ℕ} (d : Fin n → ℤ) (e : Fin n × Fin n) (c : Bool) : gbit (fun x => -d x) e (!c) = !(gbit d e c) := by unfold gbit dsimp only cases c <;> split_ifs <;> first | rfl | (exfalso; omega)theorem step_neg {n : ℕ} (d : Fin n → ℤ) (e : Fin n × Fin n) (b : Bool) : carpool_step n (fun x => -d x) e (!b) = fun x => -(carpool_step n d e b x) := by funext x unfold carpool_step cases b <;> simp only [Bool.not_true, Bool.not_false, Bool.false_eq_true, if_true, if_false] <;> split_ifs <;> ringtheorem G_neg (n : ℕ) : ∀ (es : List (Fin n × Fin n)) (cs : List Bool) (d : Fin n → ℤ), G n es (cs.map (!·)) (fun x => -d x) = fun x => -(G n es cs d x) := by intro es induction es with | nil => intro cs d; simp [G_nil] | cons e es ih => intro cs d cases cs with | nil => rfl | cons c cs => simp only [List.map_cons, G] rw [gbit_neg, step_neg, ih]theorem card_comp_equiv'' {γ δ : Type} [Fintype γ] [Fintype δ] (Φ : γ ≃ δ) (f : δ → Prop) [DecidablePred f] : (Finset.univ.filter (fun p => f (Φ p))).card = (Finset.univ.filter f).card := by refine Finset.card_nbij' Φ Φ.symm ?_ ?_ (fun p _ => Φ.symm_apply_apply p) (fun p _ => Φ.apply_symm_apply p) · intro p hp; simpa using hp · intro p hp; simpa using hp/-- split the coins into a prefix and a suffix -/def splitEquiv (t T : ℕ) (h : t ≤ T) : (Fin T → Bool) ≃ (Fin t → Bool) × (Fin (T - t) → Bool) where toFun r := (fun i => r ⟨i, by omega⟩, fun j => r ⟨t + j, by omega⟩) invFun p := fun i => if hi : i.val < t then p.1 ⟨i, hi⟩ else p.2 ⟨i - t, by omega⟩ left_inv r := by funext i by_cases hi : i.val < t · simp [hi] · simp only [hi, dite_false]; congr 1; ext; simp; omega right_inv p := by obtain ⟨p1, p2⟩ := p ext j · simp · simptheorem marginal (t T : ℕ) (h : t ≤ T) (P : (Fin t → Bool) → Prop) [DecidablePred P] : (Finset.univ.filter (fun r : Fin T → Bool => P (fun i => r ⟨i, by omega⟩))).card = (Finset.univ.filter P).card * 2 ^ (T - t) := by rw [← card_comp_equiv'' (splitEquiv t T h).symm (fun r : Fin T → Bool => P (fun i => r ⟨i, by omega⟩))] have : (Finset.univ.filter (fun p : (Fin t → Bool) × (Fin (T - t) → Bool) => P (fun i => (splitEquiv t T h).symm p ⟨i, by omega⟩))) = (Finset.univ.filter P) ×ˢ Finset.univ := by ext ⟨p1, p2⟩ simp [splitEquiv] rw [this, Finset.card_product, Finset.card_univ, Fintype.card_fun, Fintype.card_bool, Fintype.card_fin]theorem forest_take (n : ℕ) (es : List (Fin n × Fin n)) (t : ℕ) (hf : CarpoolForestEdgeSequence n es) : CarpoolForestEdgeSequence n (es.take t) := by obtain ⟨hv, hnd, hac⟩ := hf have hsub : ∀ x ∈ es.take t, x ∈ es := fun x hx => List.mem_of_mem_take hx refine ⟨fun x hx => hv x (hsub x hx), ?_, ?_⟩ · rw [List.map_take]; exact hnd.sublist (List.take_sublist _ _) · refine hac.anti ?_ intro x y hxy rw [SimpleGraph.fromEdgeSet_adj] at hxy ⊢ obtain ⟨⟨e', he', hex⟩, hne⟩ := hxy exact ⟨⟨e', hsub e' he', hex⟩, hne⟩/-- the one-sided bound for a prefix, with unused suffix coins, in counting form -/theorem prefix_bound (n : ℕ) (es : List (Fin n × Fin n)) (hf : CarpoolForestEdgeSequence n es) (t : ℕ) (ht : t ≤ es.length) (w : Fin n) (D : ℕ) (hD : 1 ≤ D) (sgn : Bool) : ((Finset.univ.filter (fun r : Fin es.length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * G n (es.take t) ((List.ofFn r).take t) (fun _ => 0) w)).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ es.length := by have hlen : (es.take t).length = t := by simp; omega -- restrict coins have hres : ∀ r : Fin es.length → Bool, (List.ofFn r).take t = List.ofFn (fun i : Fin (es.take t).length => r ⟨i, by omega⟩) := by intro r apply List.ext_getElem · simp · intro i h1 h2; simp have hcount := marginal (es.take t).length es.length (by omega) (fun r' => (D : ℤ) ≤ (if sgn then 1 else -1) * forest_carpool_final_discrepancy n (es.take t) r' w) have heq : (Finset.univ.filter (fun r : Fin es.length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * G n (es.take t) ((List.ofFn r).take t) (fun _ => 0) w)) = Finset.univ.filter (fun r : Fin es.length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * forest_carpool_final_discrepancy n (es.take t) (fun i => r ⟨i, by omega⟩) w) := by ext r; simp only [Finset.mem_filter, Finset.mem_univ, true_and] rw [final_eq, hres] rw [heq, hcount] -- the prefix bound have hpre : ((Finset.univ.filter (fun r' : Fin (es.take t).length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * forest_carpool_final_discrepancy n (es.take t) r' w)).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ (es.take t).length := by have hb := forest_carpool_final_one_sided_fibonacci_tail n (es.take t) (forest_take n es t hf) w D hD rw [div_le_iff₀ (by positivity)] at hb cases sgn · -- negative side: flip all coins let flip : (Fin (es.take t).length → Bool) ≃ (Fin (es.take t).length → Bool) := { toFun := fun r i => !r i, invFun := fun r i => !r i, left_inv := fun r => by funext i; simp, right_inv := fun r => by funext i; simp } have hneg : ∀ r', forest_carpool_final_discrepancy n (es.take t) (flip r') w = - forest_carpool_final_discrepancy n (es.take t) r' w := by intro r' rw [final_eq, final_eq] have : List.ofFn (flip r') = (List.ofFn r').map (!·) := by rw [List.map_ofFn]; rfl rw [this] have := congrFun (G_neg n (es.take t) (List.ofFn r') (fun _ => 0)) w simpa using this rw [← card_comp_equiv'' flip] at hb simp only [hneg] at hb simp only [Bool.false_eq_true, if_false, neg_one_mul] exact hb · simp only [if_true, one_mul] exact hb rw [Nat.cast_mul, Nat.cast_pow, Nat.cast_two] have hsplit : (2 : ℝ) ^ es.length = 2 ^ (es.take t).length * 2 ^ (es.length - (es.take t).length) := by rw [← pow_add]; congr 1; omega rw [hsplit, ← mul_assoc] exact mul_le_mul_of_nonneg_right hpre (by positivity)end ForestCarpoolMaxtheorem forest_carpool_maximum_fibonacci_tail (n : ℕ) (edges : List (Fin n × Fin n)) (hf : CarpoolForestEdgeSequence n edges) (D : ℕ) (hD : 1 ≤ D) : (((Finset.univ.filter (fun r : Fin edges.length → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r)))).card : ℝ) / (2 ^ edges.length : ℝ)) ≤ 4 * edges.length * forest_carpool_tail_envelope D := by classical open ForestCarpoolLocal ForestCarpoolMax in set T := edges.length with hT let ev : Fin T → Fin n → Bool → Finset (Fin T → Bool) := fun j w sgn => Finset.univ.filter (fun r : Fin edges.length → Bool => (D : ℤ) ≤ (if sgn then 1 else -1) * G n (edges.take (j + 1)) ((List.ofFn r).take (j + 1)) (fun _ => 0) w) have hsub : Finset.univ.filter (fun r : Fin edges.length → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r))) ⊆ Finset.univ.biUnion (fun j : Fin T => ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false) := by intro r hr simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hr unfold carpool_max_discrepancy carpool_discrepancies carpool_greedy_orientations at hr rcases foldl_max_le D _ 0 hr with h0 | ⟨x, hx, hDx⟩ · omega obtain ⟨dv, hdv, rfl⟩ := List.mem_map.mp hx obtain ⟨i, hi, rfl⟩ := List.getElem_of_mem hdv rw [List.getElem_scanl, take_zip_aux, foldl_aux] at hDx unfold max_vertex_discrepancy at hDx obtain ⟨w, _, hw⟩ := (Finset.le_sup_iff (lt_of_lt_of_le (by decide : (⊥ : ℕ) < 1) hD)).mp hDx have hilen : i ≤ edges.length := by simp [List.length_scanl] at hi; omega obtain ⟨j, hj, hjw, hjD⟩ := last_touch n edges (List.ofFn r) (by simp) D hD i hilen w hw simp only [Finset.mem_biUnion, Finset.mem_univ, true_and, Finset.mem_union] refine ⟨⟨j, hj⟩, ?_⟩ simp only [ev, Finset.mem_filter, Finset.mem_univ, true_and, if_true, if_false, Bool.false_eq_true, one_mul, neg_one_mul] have habs : (D : ℤ) ≤ G n (edges.take (j + 1)) ((List.ofFn r).take (j + 1)) (fun _ => 0) w ∨ (D : ℤ) ≤ -G n (edges.take (j + 1)) ((List.ofFn r).take (j + 1)) (fun _ => 0) w := by omega rcases hjw with rfl | rfl <;> rcases habs with h | h <;> simp [h] have hcard := (Finset.card_le_card hsub).trans (Finset.card_biUnion_le) have hbound : ∀ j : Fin T, ((ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false).card : ℝ) ≤ 4 * (forest_carpool_tail_envelope D * 2 ^ edges.length) := by intro j have h1 : ((ev j (edges[j]).1 true).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ edges.length := prefix_bound n edges hf (j + 1) j.2 (edges[j]).1 D hD true have h2 : ((ev j (edges[j]).1 false).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ edges.length := prefix_bound n edges hf (j + 1) j.2 (edges[j]).1 D hD false have h3 : ((ev j (edges[j]).2 true).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ edges.length := prefix_bound n edges hf (j + 1) j.2 (edges[j]).2 D hD true have h4 : ((ev j (edges[j]).2 false).card : ℝ) ≤ forest_carpool_tail_envelope D * 2 ^ edges.length := prefix_bound n edges hf (j + 1) j.2 (edges[j]).2 D hD false have hu := Finset.card_union_le (ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true) (ev j (edges[j]).2 false) have hu2 := Finset.card_union_le (ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false) (ev j (edges[j]).2 true) have hu3 := Finset.card_union_le (ev j (edges[j]).1 true) (ev j (edges[j]).1 false) have : ((ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false).card : ℝ) ≤ (ev j (edges[j]).1 true).card + (ev j (edges[j]).1 false).card + (ev j (edges[j]).2 true).card + (ev j (edges[j]).2 false).card := by exact_mod_cast (by omega) linarith have hsum : ((Finset.univ.filter (fun r : Fin edges.length → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r)))).card : ℝ) ≤ T * (4 * (forest_carpool_tail_envelope D * 2 ^ edges.length)) := by calc _ ≤ ((∑ j : Fin T, (ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false).card : ℕ) : ℝ) := by exact_mod_cast hcard _ = ∑ j : Fin T, ((ev j (edges[j]).1 true ∪ ev j (edges[j]).1 false ∪ ev j (edges[j]).2 true ∪ ev j (edges[j]).2 false).card : ℝ) := by push_cast; rfl _ ≤ ∑ _j : Fin T, 4 * (forest_carpool_tail_envelope D * 2 ^ edges.length) := Finset.sum_le_sum (fun j _ => hbound j) _ = _ := by simp rw [div_le_iff₀ (by positivity)] linarith