AFTD Auto-Formalizing Theoretical Domains

forest_carpool_maximum_fibonacci_tail

theoremverified

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

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.

  1. 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.

    lines 8–18

      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 _
    
  2. 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.

    lines 19–37

    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]
    
  3. 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.

    lines 38–55

    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)
    
  4. 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.

    lines 56–58

    theorem G_nil (n : ℕ) (cs : List Bool) (d : Fin n → ℤ) : G n [] cs d = d := by
      cases cs <;> rfl
    
  5. 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.

    lines 59–71

    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⟩
    
  6. 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.

    lines 72–93

    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
    
  7. 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.

    lines 94–99

    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)
    
  8. 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.

    lines 100–106

    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
    
  9. 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.

    lines 107–119

    uses gbit_neg, step_neg

    theorem 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]
    
  10. 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.

    lines 120–127

    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
    
  11. 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.

    lines 128–142

    /-- 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
    
  12. 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).

    lines 143–155

    uses card_comp_equiv'', splitEquiv

    theorem 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]
    
  13. 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.

    lines 156–167

    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⟩
    
  14. 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.

    lines 168–228

    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)
    
  15. 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.

    lines 229–244

    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)
  16. 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.

    lines 245–270

    uses foldl_max_le, take_zip_aux, foldl_aux, last_touch

      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]
  17. 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.

    lines 271–294

    uses prefix_bound, Finset.card_union_le

      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
  18. 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).

    lines 295–308

    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

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
See it in the graphDiscuss this resultChallenge it