AFTD Auto-Formalizing Theoretical Domains

forest_carpool_final_one_sided_fibonacci_tail

theoremverified

For any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded by the stated Fibonacci envelope.

Statement

theorem forest_carpool_final_one_sided_fibonacci_tail (n : ℕ)
    (edges : List (Fin n × Fin n)) (hf : CarpoolForestEdgeSequence n edges)
    (v : Fin n) (D : ℕ) (hD : 1 ≤ D) :
  (((Finset.univ.filter (fun r : Fin edges.length → Bool =>
    (D : ℤ) ≤ forest_carpool_final_discrepancy n edges r v)).card : ℝ) /
    (2 ^ 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 12
  • forest_carpool_final_discrepancyThe final discrepancy of a vertex after greedy orientation of the given edges with the given indexed tie-breaking coins.
  • 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.
  • 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_disjoint_components_independentIf appending the edge u-v to the given prefix yields a forest, then under uniformly random prefix coins the two endpoint final…
  • forest_greedy_envelope_preserved_by_independent_mergeIndependent symmetric finite uniform discrepancy laws of fixed parity that satisfy the envelope still satisfy it after one greedy step…
  • carpool_stepIn online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d…
  • 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…
  • forest_greedy_law_envelopedA finite uniform integer law has one fixed parity, is symmetric, and its positive tail at each positive integer is bounded by the forest…
  • ValidCarpoolEdgeSequenceA list of edges on n vertices is valid for online carpooling if every arriving edge connects two distinct vertices.
  • 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_greedy_signed_stepThe new discrepancy of the first endpoint of a greedy edge is x+1 when x<y, x-1 when x>y, and uses the fair coin to choose between these…
  • Arena.Reachable.transReachability is transitive.
Used by 1

The proof, explained

The theorem establishes that for any forest arrival sequence and any vertex, the probability that the final greedy discrepancy is at least D is bounded by the Fibonacci envelope. The proof proceeds by reverse induction on the edge list, showing that the discrepancy distribution is always enveloped (parity invariant, symmetric, and tail-bounded). In the inductive step, acyclicity guarantees that the endpoints of a newly appended edge belong to disconnected components; because discrepancy depends only on component coins, the two endpoints behave independently, and their greedy merger preserves the enveloped law.

  1. Precomposing a decidable predicate with an equivalence between finite types preserves the size of the satisfying subset. automation

    A bijection between `{p | f (Φ p)}` and `{q | f q}` is constructed using `Finset.card_nbij'` with `Φ` and `Φ.symm`, where automation verifies membership preservation.

    lines 6–9

    uses Finset.card_nbij'

      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
  2. Enveloped laws are invariant under a change of coin space by an equivalence.

    Parity invariance is immediate under reindexing. Fiber cardinalities for symmetry and level set cardinalities for the tail bound are preserved by `card_comp_equiv'`, and the denominator cardinality is preserved by `Fintype.card_congr`.

    lines 15–20

    uses card_comp_equiv', Fintype.card_congr

      obtain ⟨⟨p, hp⟩, hs, ht⟩ := h
      refine ⟨⟨p, fun a => hp _⟩, fun z => ?_, fun k hk => ?_⟩
      · rw [card_comp_equiv' Φ (fun q => X q = z), card_comp_equiv' Φ (fun q => X q = -z)]
        exact hs z
      · rw [card_comp_equiv' Φ (fun q => (k : ℤ) ≤ X q), Fintype.card_congr Φ]
        exact ht k hk
  3. An extra unused fair coin does not change an enveloped law.

    Each fiber on the product space `α × Bool` has size twice that on `α`. This factor of 2 cancels out in the tail bound ratio via `mul_div_mul_right`, while parity and symmetry are unaffected.

    lines 26–40

    uses Finset.card_product, Finset.card_univ, Fintype.card_bool, Fintype.card_prod, mul_div_mul_right

      obtain ⟨⟨p, hp⟩, hs, ht⟩ := h
      have hc : ∀ (f : ℤ → Prop) [DecidablePred f],
          (Finset.univ.filter (fun q : α × Bool => f (X q.1))).card =
            (Finset.univ.filter (fun a => f (X a))).card * 2 := by
        intro f _
        have : (Finset.univ.filter (fun q : α × Bool => f (X q.1))) =
            (Finset.univ.filter (fun a => f (X a))) ×ˢ (Finset.univ : Finset Bool) := by
          ext q; simp
        rw [this, Finset.card_product, Finset.card_univ, Fintype.card_bool]
      refine ⟨⟨p, fun a => hp _⟩, fun z => ?_, fun k hk => ?_⟩
      · rw [hc (fun x => x = z), hc (fun x => x = -z), hs z]
      · rw [hc (fun x => (k : ℤ) ≤ x), Fintype.card_prod, Fintype.card_bool]
        have := ht k hk
        push_cast
        rwa [mul_div_mul_right _ _ (by norm_num : (2 : ℝ) ≠ 0)]
  4. An enveloped law on an independent product of components transfers to the joint law on the coupled coin space.

    An involution swapping coin vectors outside a component establishes a bijection between the joint fiber and the independent product fiber times `2^L`. Dividing out `2^L` using `Nat.eq_of_mul_eq_mul_right` preserves symmetry and the tail bound.

    lines 51–99

    uses Finset.card_nbij', card_comp_equiv', Nat.eq_of_mul_eq_mul_right

      obtain ⟨⟨p, hp⟩, hs, ht⟩ := h
      have hc : ∀ (f : ℤ → Prop) [DecidablePred f],
          (Finset.univ.filter (fun q : (Fin L → Bool) × (Fin L → Bool) × Bool =>
            f (F (A q.1) (B q.2.1) q.2.2))).card =
          (Finset.univ.filter (fun q : (Fin L → Bool) × Bool => f (F (A q.1) (B q.1) q.2))).card *
            2 ^ L := by
        intro f _
        let φ : (Fin L → Bool) × (Fin L → Bool) × Bool → (Fin L → Bool) × (Fin L → Bool) × Bool :=
          fun q => (mix q.1 q.2.1, mix q.2.1 q.1, q.2.2)
        have hφ : ∀ q, φ (φ q) = q := by
          rintro ⟨r, s, c⟩; simp only [φ, hmix]
        have h1 : (Finset.univ.filter (fun q : (Fin L → Bool) × (Fin L → Bool) × Bool =>
            f (F (A q.1) (B q.2.1) q.2.2))).card =
            (Finset.univ.filter (fun q : (Fin L → Bool) × (Fin L → Bool) × Bool =>
            f (F (A q.1) (B q.1) q.2.2))).card := by
          refine Finset.card_nbij' φ φ ?_ ?_ (fun q _ => hφ q) (fun q _ => hφ q)
          · rintro ⟨r, s, c⟩ hq
            simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hq ⊢
            simp only [φ, hA, hB]; exact hq
          · rintro ⟨r, s, c⟩ hq
            simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hq ⊢
            simp only [φ, hA, hB]; exact hq
        rw [h1]
        let ψ : (Fin L → Bool) × (Fin L → Bool) × Bool ≃ ((Fin L → Bool) × Bool) × (Fin L → Bool) :=
          { toFun := fun q => ((q.1, q.2.2), q.2.1)
            invFun := fun q => (q.1.1, q.2, q.1.2)
            left_inv := fun q => rfl
            right_inv := fun q => rfl }
        rw [← card_comp_equiv' ψ.symm (fun q => f (F (A q.1) (B q.1) q.2.2))]
        have : (Finset.univ.filter (fun q : ((Fin L → Bool) × Bool) × (Fin L → Bool) =>
            f (F (A (ψ.symm q).1) (B (ψ.symm q).1) (ψ.symm q).2.2))) =
            (Finset.univ.filter (fun q : (Fin L → Bool) × Bool => f (F (A q.1) (B q.1) q.2))) ×ˢ
              (Finset.univ : Finset (Fin L → Bool)) := by
          ext q; simp [ψ]
        rw [this, Finset.card_product, Finset.card_univ, Fintype.card_fun, Fintype.card_bool,
          Fintype.card_fin]
      have hpos : 0 < 2 ^ L := by positivity
      refine ⟨⟨p, fun q => hp (q.1, q.1, q.2)⟩, fun z => ?_, fun k hk => ?_⟩
      · have e1 := hc (fun x => x = z)
        have e2 := hc (fun x => x = -z)
        have := hs z
        rw [e1, e2] at this
        exact Nat.eq_of_mul_eq_mul_right hpos this
      · have := ht k hk
        rw [hc (fun x => (k : ℤ) ≤ x)] at this
        simp only [Fintype.card_prod, Fintype.card_fun, Fintype.card_bool, Fintype.card_fin] at this ⊢
        push_cast at this ⊢
        convert this using 1
        field_simp
  5. Appending an edge and coin to the arrival sequence applies one additional carpool step to the intermediate discrepancy state. automation

    Induction on the edge list `es` shows that the dynamic `G` on an appended list computes one step of `carpool_step` applied to the previous state.

    lines 106–119

      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)
  6. The coin space `(Fin L → Bool) × Bool` is equivalent to `Fin (L + 1) → Bool`. automation

    The map sends indices below `L` to the first component and index `L` to the extra boolean, with inverse given by restriction and evaluation at `L`.

    lines 124–135

      invFun f := (fun j => f ⟨j.val, by omega⟩, f ⟨L, by omega⟩)
      left_inv p := by
        obtain ⟨r, c⟩ := p
        ext j
        · simp
        · simp
      right_inv f := by
        funext i
        by_cases h : i.val < L
        · simp [h]
        · simp only [h, dite_false]
          congr 1; ext; simp; omega
  7. Converting the reindexed coin tuple to a list yields the original coin list appended with the extra coin.

    Extensionality for lists (`List.ext_getElem`) confirms that index by index, `List.ofFn` of the equivalence matches the concatenation of `List.ofFn r` and `[c]`.

    lines 139–148

    uses List.ext_getElem, List.getElem_ofFn, List.getElem_append

      apply List.ext_getElem
      · simp [hm]
      · intro i h1 h2
        simp only [List.getElem_ofFn, coinEquiv, Equiv.coe_fn_mk]
        rw [List.getElem_append]
        split_ifs with h3 h4 h4
        · simp
        · simp at h4; omega
        · simp at h4; omega
        · simp
  8. The final discrepancy after appending an edge is one carpool step from the previous final discrepancy. automation

    Rewriting with `ForestCarpoolLocal.final_eq`, `ofFn_coinEquiv`, and `G_append` expresses the final discrepancy as a single carpool step.

    lines 156–158

    uses ForestCarpoolLocal.final_eq, ofFn_coinEquiv, G_append

      obtain ⟨r, c⟩ := p
      rw [ForestCarpoolLocal.final_eq, ForestCarpoolLocal.final_eq, ofFn_coinEquiv,
        G_append n e c es _ _ (by simp)]
  9. At the first endpoint `u` of edge `(u, v)`, the carpool step is the 1D greedy signed step with coin `c`. automation

    Unfolding definitions and performing case analysis shows that when `u ≠ v`, the discrepancy update at `u` matches `forest_greedy_signed_step`.

    lines 163–164

    uses if_neg

      simp only [carpool_step, ForestCarpoolLocal.gbit, forest_greedy_signed_step, if_neg huv]
      cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)
  10. At the second endpoint `v` of edge `(u, v)`, the carpool step is the 1D greedy signed step with inverted coin `!c`. automation

    By symmetry, the discrepancy update at `v` matches `forest_greedy_signed_step` with the inverted coin `!c`.

    lines 169–170

    uses if_neg

      simp only [carpool_step, ForestCarpoolLocal.gbit, forest_greedy_signed_step, if_neg huv.symm]
      cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)
  11. The discrepancy at any vertex other than `u` and `v` is unchanged by an arrival on `(u, v)`. automation

    Both indicator terms in `carpool_step` vanish when the vertex is neither `u` nor `v`.

    line 174

      simp [carpool_step, hu, hv]
  12. Any prefix of a valid acyclic carpool forest edge sequence is also a valid forest edge sequence.

    Distinct endpoints, absence of duplicates, and acyclicity are inherited by sublists and subgraphs using `List.mem_append_left`, `List.map_append`, `List.sublist_append_left`, and `SimpleGraph.fromEdgeSet_adj`.

    lines 178–185

    uses List.mem_append_left, List.map_append, List.sublist_append_left, SimpleGraph.fromEdgeSet_adj

      obtain ⟨hv, hnd, hac⟩ := hf
      refine ⟨fun x hx => hv x (List.mem_append_left _ hx), ?_, ?_⟩
      · rw [List.map_append] at hnd; exact hnd.sublist (List.sublist_append_left _ _)
      · refine hac.anti ?_
        intro x y hxy
        rw [SimpleGraph.fromEdgeSet_adj] at hxy ⊢
        obtain ⟨⟨e', he', hex⟩, hne⟩ := hxy
        exact ⟨⟨e', List.mem_append_left _ he', hex⟩, hne⟩
  13. For vertices in disconnected components, any merge operation preserving the envelope on independent components also preserves it on the joint space.

    By coin locality (`forest_carpool_component_coin_locality`), discrepancies at `x` and `y` depend only on coins in their respective components. Since they are disconnected, a mixing function decouples them, allowing `enveloped_diag` to transfer the enveloped law.

    lines 196–212

    uses enveloped_diag, forest_carpool_component_coin_locality, if_pos, if_neg

      classical
      set Γ := SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ es}
      let mix : (Fin es.length → Bool) → (Fin es.length → Bool) → (Fin es.length → Bool) :=
        fun r s i => if Γ.Reachable x (es.get i).1 then r i else s i
      refine enveloped_diag (fun r => forest_carpool_final_discrepancy n es r x)
        (fun r => forest_carpool_final_discrepancy n es r y) mix ?_ ?_ ?_ F h
      · intro r s
        apply forest_carpool_component_coin_locality
        intro i hi
        have hi' : Γ.Reachable x (es.get i).1 := hi
        simp only [mix, if_pos hi']
      · intro r s
        apply forest_carpool_component_coin_locality
        intro i hi
        have : ¬ Γ.Reachable x (es.get i).1 := fun h => hxy (h.trans hi.symm)
        simp only [mix, if_neg this]
      · intro r s; funext i; simp only [mix]; split_ifs <;> rfl
  14. The base case of an empty edge list has identically 0 discrepancy, which is enveloped.

    Reverse induction on the edge list begins with `es = []`. The final discrepancy is constantly 0, which has parity 0, is trivially symmetric, and has empty level sets for $k \ge 1$.

    lines 217–229

    uses List.reverseRecOn, ForestCarpoolLocal.final_eq, Finset.card_empty, Nat.cast_zero, zero_div

      intro es
      induction es using List.reverseRecOn with
      | nil =>
        intro _ w
        have h0 : ∀ r : Fin ([] : List (Fin n × Fin n)).length → Bool,
            forest_carpool_final_discrepancy n [] r w = 0 := by
          intro r; rw [ForestCarpoolLocal.final_eq]; simp [ForestCarpoolLocal.G]
        refine ⟨⟨0, fun r => by show forest_carpool_final_discrepancy n [] r w % 2 = 0; rw [h0]; rfl⟩, fun z => ?_, fun k hk => ?_⟩
        · simp only [h0]; congr 1; ext r; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega
        · have : (Finset.univ.filter (fun r : Fin ([] : List (Fin n × Fin n)).length → Bool =>
              (k : ℤ) ≤ forest_carpool_final_discrepancy n [] r w)) = ∅ := by
            ext r; simp only [h0, Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty,
              iff_false]; omega
  15. When appending an edge `(u, v)`, the discrepancy at `u` follows an enveloped law.

    By acyclicity, `u` and `v` are disconnected in the preceding graph (`forest_carpool_append_edge_disconnected`). By induction, their discrepancies are enveloped. Their independent merge is enveloped by `forest_greedy_envelope_preserved_by_independent_merge`, transferring to the joint space via `env_pair` and `step_at_u`.

    lines 230–246

    uses forest_init, forest_carpool_append_edge_disconnected, final_append, step_at_u, env_pair, forest_greedy_envelope_preserved_by_independent_merge

          rw [this, Finset.card_empty, Nat.cast_zero, zero_div]
          unfold forest_carpool_tail_envelope; split_ifs <;> positivity
      | append_singleton es e ih =>
        intro hf w
        obtain ⟨u, v⟩ := e
        have hf0 := forest_init n es (u, v) hf
        have ih' := ih hf0
        have huv : u ≠ v := hf.1 (u, v) (by simp)
        have hdis := forest_carpool_append_edge_disconnected n es u v hf
        have key : forest_greedy_law_enveloped ((Fin es.length → Bool) × Bool)
            (fun p => forest_carpool_final_discrepancy n (es ++ [(u, v)])
              (coinEquiv es.length (es ++ [(u, v)]).length (by simp) p) w) := by
          simp only [final_append]
          by_cases hwu : w = u
          · subst hwu
            simp only [step_at_u n _ _ _ huv]
            exact env_pair n es w v hdis forest_greedy_signed_step
  16. When appending an edge `(u, v)`, discrepancies at `v` and at other vertices also follow enveloped laws.

    For `w = v`, the update is symmetric using an inverted coin by `step_at_v` and `enveloped_equiv`. For `w ∉ {u, v}`, the discrepancy is unchanged by `step_at_other` and an extra unused coin preserves the envelope via `enveloped_extra`. Reindexing with `coinEquiv` completes the induction.

    lines 247–258

    uses step_at_v, forest_greedy_envelope_preserved_by_independent_merge, enveloped_equiv, Equiv.refl, Equiv.prodCongr, Equiv.boolNot, env_pair, step_at_other, enveloped_extra, coinEquiv

              (forest_greedy_envelope_preserved_by_independent_merge _ _ _ _ (ih' w) (ih' v))
          · by_cases hwv : w = v
            · subst hwv
              simp only [step_at_v n _ _ _ huv]
              have hm := forest_greedy_envelope_preserved_by_independent_merge _ _ _ _ (ih' w) (ih' u)
              have hm' := enveloped_equiv
                ((Equiv.refl _).prodCongr ((Equiv.refl _).prodCongr Equiv.boolNot)) _ hm
              exact env_pair n es w u (fun h => hdis h.symm)
                (fun a b c => forest_greedy_signed_step a b (!c)) hm'
            · simp only [step_at_other n _ _ _ _ hwu hwv]
              exact enveloped_extra _ (ih' w)
        have := enveloped_equiv (coinEquiv es.length (es ++ [(u, v)]).length (by simp)).symm _ key
  17. The tail probability that discrepancy at vertex `v` is at least `D` is bounded by the Fibonacci envelope. automation

    Specializing `ForestCarpoolTail.env_all` to $D \ge 1$ gives the envelope tail bound with denominator $|Fin\ edges.length \to Bool|$, which simplifies to $2^{edges.length}$ using `Fintype.card_fun`, `Fintype.card_bool`, and `Fintype.card_fin`.

    lines 269–270

    uses ForestCarpoolTail.env_all, Fintype.card_fun, Fintype.card_bool, Fintype.card_fin

      have := (ForestCarpoolTail.env_all n edges hf v).2.2 D hD
      simpa [Fintype.card_fun, Fintype.card_bool, Fintype.card_fin] using this
Finset.card_nbij'
Two finite sets have equal cardinality if there is a bijection between them with explicit inverses on the sets.
card_comp_equiv'
Precomposing a predicate with an equivalence between finite types preserves the cardinality of the satisfying subset.
Fintype.card_congr
Equivalent finite types have the same cardinality.
Finset.card_product
The cardinality of a Cartesian product of finite sets is the product of their cardinalities.
Finset.card_univ
The cardinality of the universal finset `Finset.univ` is the cardinality of the underlying finite type.
Fintype.card_bool
The cardinality of the boolean type `Bool` is 2.
Fintype.card_prod
The cardinality of a product type `α × β` is `|α| * |β|`.
mul_div_mul_right
For non-zero `c`, `(a * c) / (b * c) = a / b`.
Nat.eq_of_mul_eq_mul_right
If `0 < m` and `n * m = k * m`, then `n = k`.
List.ext_getElem
Two lists of equal length that agree at every index are equal.
List.getElem_ofFn
Indexing into `List.ofFn f` at `i` gives `f i`.
List.getElem_append
Indexing into an appended list `l₁ ++ l₂` yields `l₁[i]` when `i < l₁.length` and `l₂[i - l₁.length]` otherwise.
ForestCarpoolLocal.final_eq
The final discrepancy of an edge sequence equals the discrepancy computed by running the local simulation dynamic `G` initialized at 0.
ofFn_coinEquiv
Converting the coin equivalence on `(Fin L → Bool) × Bool` to a list produces the original list of coins appended with the extra coin.
G_append
Running the carpool simulation dynamic `G` on an appended edge corresponds to taking one greedy step from the intermediate discrepancy state.
if_neg
If the condition of an `if-then-else` expression is false, the expression simplifies to the `else` branch.
List.mem_append_left
An element of `as` is also an element of `as ++ bs`.
List.map_append
Mapping a function over an appended list produces the concatenation of the mapped lists.
List.sublist_append_left
A list `l₁` is a sublist of `l₁ ++ l₂`.
SimpleGraph.fromEdgeSet_adj
In a graph defined by an edge set, two distinct vertices are adjacent if and only if their undirected edge is in the set.
enveloped_diag
If a bivariate function on independent component coin spaces has an enveloped law, coupling the components diagonally via an involution swap preserves the enveloped law.
forest_carpool_component_coin_locality
The final discrepancy at a vertex depends only on the coin flips of edges in its connected component.
if_pos
If the condition of an `if-then-else` expression is true, the expression simplifies to the `then` branch.
List.reverseRecOn
Principle of reverse induction on lists: to prove a statement for all lists, prove it for `[]` and for `l ++ [a]` given the statement for `l`.
Finset.card_empty
The empty finset has cardinality 0.
Nat.cast_zero
The natural number 0 casts to 0 in any ring.
zero_div
Zero divided by any element in a division structure with zero is zero.
forest_init
Any prefix of a valid acyclic carpool forest edge sequence is itself a valid forest edge sequence.
forest_carpool_append_edge_disconnected
In an acyclic forest arrival sequence, the endpoints of an appended edge are disconnected in the existing edge graph.
final_append
Appending an edge updates the final discrepancy by one greedy step with the extra coin.
step_at_u
At the first endpoint `u` of an edge `(u, v)`, a carpool step reduces to the 1D greedy signed step with coin `c`.
env_pair
Discrepancies at vertices in disconnected components can be coupled to independent components, so any merge function preserving the envelope applies.
forest_greedy_envelope_preserved_by_independent_merge
The independent merge of two enveloped discrepancy laws under a greedy signed step produces an enveloped law.
step_at_v
At the second endpoint `v` of an edge `(u, v)`, a carpool step reduces to the 1D greedy signed step with inverted coin `!c`.
enveloped_equiv
Precomposing a random variable with an equivalence between finite types preserves its enveloped law.
Equiv.refl
The identity equivalence on any type.
Equiv.prodCongr
The Cartesian product of two equivalences is an equivalence between the product types.
Equiv.boolNot
Boolean negation is an equivalence (permutation) of `Bool`.
step_at_other
A carpool step along edge `(u, v)` does not change the discrepancy at any vertex other than `u` and `v`.
enveloped_extra
Adding an independent unused fair coin to the coin space preserves the enveloped law.
coinEquiv
An equivalence between `(Fin L → Bool) × Bool` and `Fin (L + 1) → Bool`.
ForestCarpoolTail.env_all
For any forest arrival sequence and vertex, the distribution of final greedy discrepancy is enveloped.
Fintype.card_fun
The cardinality of the function space `α → β` is `|β| ^ |α|`.
Fintype.card_fin
The cardinality of `Fin n` is `n`.

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 ForestCarpoolTailtheorem 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/-- enveloped laws are invariant under a change of coin space by an equivalence -/theorem enveloped_equiv {γ δ : Type} [Fintype γ] [Fintype δ] (Φ : γ ≃ δ) (X : δ → ℤ)    (h : forest_greedy_law_enveloped δ X) :    forest_greedy_law_enveloped γ (fun p => X (Φ p)) := by  obtain ⟨⟨p, hp⟩, hs, ht⟩ := h  refine ⟨⟨p, fun a => hp _⟩, fun z => ?_, fun k hk => ?_⟩  · rw [card_comp_equiv' Φ (fun q => X q = z), card_comp_equiv' Φ (fun q => X q = -z)]    exact hs z  · rw [card_comp_equiv' Φ (fun q => (k : ℤ) ≤ X q), Fintype.card_congr Φ]    exact ht k hk/-- an extra unused fair coin does not change the law -/theorem enveloped_extra {α : Type} [Fintype α] (X : α → ℤ)    (h : forest_greedy_law_enveloped α X) :    forest_greedy_law_enveloped (α × Bool) (fun p => X p.1) := by  obtain ⟨⟨p, hp⟩, hs, ht⟩ := h  have hc : ∀ (f : ℤ → Prop) [DecidablePred f],      (Finset.univ.filter (fun q : α × Bool => f (X q.1))).card =        (Finset.univ.filter (fun a => f (X a))).card * 2 := by    intro f _    have : (Finset.univ.filter (fun q : α × Bool => f (X q.1))) =        (Finset.univ.filter (fun a => f (X a))) ×ˢ (Finset.univ : Finset Bool) := by      ext q; simp    rw [this, Finset.card_product, Finset.card_univ, Fintype.card_bool]  refine ⟨⟨p, fun a => hp _⟩, fun z => ?_, fun k hk => ?_⟩  · rw [hc (fun x => x = z), hc (fun x => x = -z), hs z]  · rw [hc (fun x => (k : ℤ) ≤ x), Fintype.card_prod, Fintype.card_bool]    have := ht k hk    push_cast    rwa [mul_div_mul_right _ _ (by norm_num : (2 : ℝ) ≠ 0)]/-- the transfer from the independent product law to the joint law on disjoint components -/theorem enveloped_diag {L : ℕ} (A B : (Fin L → Bool) → ℤ)    (mix : (Fin L → Bool) → (Fin L → Bool) → (Fin L → Bool))    (hA : ∀ r s, A (mix r s) = A r) (hB : ∀ r s, B (mix r s) = B s)    (hmix : ∀ r s, mix (mix r s) (mix s r) = r)    (F : ℤ → ℤ → Bool → ℤ)    (h : forest_greedy_law_enveloped ((Fin L → Bool) × (Fin L → Bool) × Bool)      (fun p => F (A p.1) (B p.2.1) p.2.2)) :    forest_greedy_law_enveloped ((Fin L → Bool) × Bool) (fun p => F (A p.1) (B p.1) p.2) := by  obtain ⟨⟨p, hp⟩, hs, ht⟩ := h  have hc : ∀ (f : ℤ → Prop) [DecidablePred f],      (Finset.univ.filter (fun q : (Fin L → Bool) × (Fin L → Bool) × Bool =>        f (F (A q.1) (B q.2.1) q.2.2))).card =      (Finset.univ.filter (fun q : (Fin L → Bool) × Bool => f (F (A q.1) (B q.1) q.2))).card *        2 ^ L := by    intro f _    let φ : (Fin L → Bool) × (Fin L → Bool) × Bool → (Fin L → Bool) × (Fin L → Bool) × Bool :=      fun q => (mix q.1 q.2.1, mix q.2.1 q.1, q.2.2)    have hφ : ∀ q, φ (φ q) = q := by      rintro ⟨r, s, c⟩; simp only [φ, hmix]    have h1 : (Finset.univ.filter (fun q : (Fin L → Bool) × (Fin L → Bool) × Bool =>        f (F (A q.1) (B q.2.1) q.2.2))).card =        (Finset.univ.filter (fun q : (Fin L → Bool) × (Fin L → Bool) × Bool =>        f (F (A q.1) (B q.1) q.2.2))).card := by      refine Finset.card_nbij' φ φ ?_ ?_ (fun q _ => hφ q) (fun q _ => hφ q)      · rintro ⟨r, s, c⟩ hq        simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hq ⊢        simp only [φ, hA, hB]; exact hq      · rintro ⟨r, s, c⟩ hq        simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hq ⊢        simp only [φ, hA, hB]; exact hq    rw [h1]    let ψ : (Fin L → Bool) × (Fin L → Bool) × Bool ≃ ((Fin L → Bool) × Bool) × (Fin L → Bool) :=      { toFun := fun q => ((q.1, q.2.2), q.2.1)        invFun := fun q => (q.1.1, q.2, q.1.2)        left_inv := fun q => rfl        right_inv := fun q => rfl }    rw [← card_comp_equiv' ψ.symm (fun q => f (F (A q.1) (B q.1) q.2.2))]    have : (Finset.univ.filter (fun q : ((Fin L → Bool) × Bool) × (Fin L → Bool) =>        f (F (A (ψ.symm q).1) (B (ψ.symm q).1) (ψ.symm q).2.2))) =        (Finset.univ.filter (fun q : (Fin L → Bool) × Bool => f (F (A q.1) (B q.1) q.2))) ×ˢ          (Finset.univ : Finset (Fin L → Bool)) := by      ext q; simp [ψ]    rw [this, Finset.card_product, Finset.card_univ, Fintype.card_fun, Fintype.card_bool,      Fintype.card_fin]  have hpos : 0 < 2 ^ L := by positivity  refine ⟨⟨p, fun q => hp (q.1, q.1, q.2)⟩, fun z => ?_, fun k hk => ?_⟩  · have e1 := hc (fun x => x = z)    have e2 := hc (fun x => x = -z)    have := hs z    rw [e1, e2] at this    exact Nat.eq_of_mul_eq_mul_right hpos this  · have := ht k hk    rw [hc (fun x => (k : ℤ) ≤ x)] at this    simp only [Fintype.card_prod, Fintype.card_fun, Fintype.card_bool, Fintype.card_fin] at this ⊢    push_cast at this ⊢    convert this using 1    field_simpopen ForestCarpoolLocal intheorem 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)/-- coin space of an appended edge -/def coinEquiv (L m : ℕ) (hm : m = L + 1) : (Fin L → Bool) × Bool ≃ (Fin m → Bool) where  toFun p := fun i => if h : i.val < L then p.1 ⟨i.val, h⟩ else p.2  invFun f := (fun j => f ⟨j.val, by omega⟩, f ⟨L, by omega⟩)  left_inv p := by    obtain ⟨r, c⟩ := p    ext j    · simp    · simp  right_inv f := by    funext i    by_cases h : i.val < L    · simp [h]    · simp only [h, dite_false]      congr 1; ext; simp; omegatheorem ofFn_coinEquiv (L m : ℕ) (hm : m = L + 1) (r : Fin L → Bool) (c : Bool) :    List.ofFn (coinEquiv L m hm (r, c)) = List.ofFn r ++ [c] := by  apply List.ext_getElem  · simp [hm]  · intro i h1 h2    simp only [List.getElem_ofFn, coinEquiv, Equiv.coe_fn_mk]    rw [List.getElem_append]    split_ifs with h3 h4 h4    · simp    · simp at h4; omega    · simp at h4; omega    · simptheorem final_append (n : ℕ) (es : List (Fin n × Fin n)) (e : Fin n × Fin n)    (p : (Fin es.length → Bool) × Bool) :    forest_carpool_final_discrepancy n (es ++ [e])        (coinEquiv es.length (es ++ [e]).length (by simp) p) =      carpool_step n (forest_carpool_final_discrepancy n es p.1) e        (ForestCarpoolLocal.gbit (forest_carpool_final_discrepancy n es p.1) e p.2) := by  obtain ⟨r, c⟩ := p  rw [ForestCarpoolLocal.final_eq, ForestCarpoolLocal.final_eq, ofFn_coinEquiv,    G_append n e c es _ _ (by simp)]theorem step_at_u (n : ℕ) (d : Fin n → ℤ) (u v : Fin n) (huv : u ≠ v) (c : Bool) :    carpool_step n d (u, v) (ForestCarpoolLocal.gbit d (u, v) c) u =      forest_greedy_signed_step (d u) (d v) c := by  simp only [carpool_step, ForestCarpoolLocal.gbit, forest_greedy_signed_step, if_neg huv]  cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)theorem step_at_v (n : ℕ) (d : Fin n → ℤ) (u v : Fin n) (huv : u ≠ v) (c : Bool) :    carpool_step n d (u, v) (ForestCarpoolLocal.gbit d (u, v) c) v =      forest_greedy_signed_step (d v) (d u) (!c) := by  simp only [carpool_step, ForestCarpoolLocal.gbit, forest_greedy_signed_step, if_neg huv.symm]  cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)theorem step_at_other (n : ℕ) (d : Fin n → ℤ) (u v w : Fin n) (hu : w ≠ u) (hv : w ≠ v)    (b : Bool) : carpool_step n d (u, v) b w = d w := by  simp [carpool_step, hu, hv]theorem forest_init (n : ℕ) (es : List (Fin n × Fin n)) (e : Fin n × Fin n)    (hf : CarpoolForestEdgeSequence n (es ++ [e])) : CarpoolForestEdgeSequence n es := by  obtain ⟨hv, hnd, hac⟩ := hf  refine ⟨fun x hx => hv x (List.mem_append_left _ hx), ?_, ?_⟩  · rw [List.map_append] at hnd; exact hnd.sublist (List.sublist_append_left _ _)  · refine hac.anti ?_    intro x y hxy    rw [SimpleGraph.fromEdgeSet_adj] at hxy ⊢    obtain ⟨⟨e', he', hex⟩, hne⟩ := hxy    exact ⟨⟨e', List.mem_append_left _ he', hex⟩, hne⟩theorem env_pair (n : ℕ) (es : List (Fin n × Fin n)) (x y : Fin n)    (hxy : ¬ (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ es}).Reachable x y)    (F : ℤ → ℤ → Bool → ℤ)    (h : forest_greedy_law_enveloped ((Fin es.length → Bool) × (Fin es.length → Bool) × Bool)      (fun p => F (forest_carpool_final_discrepancy n es p.1 x)        (forest_carpool_final_discrepancy n es p.2.1 y) p.2.2)) :    forest_greedy_law_enveloped ((Fin es.length → Bool) × Bool)      (fun p => F (forest_carpool_final_discrepancy n es p.1 x)        (forest_carpool_final_discrepancy n es p.1 y) p.2) := by  classical  set Γ := SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ es}  let mix : (Fin es.length → Bool) → (Fin es.length → Bool) → (Fin es.length → Bool) :=    fun r s i => if Γ.Reachable x (es.get i).1 then r i else s i  refine enveloped_diag (fun r => forest_carpool_final_discrepancy n es r x)    (fun r => forest_carpool_final_discrepancy n es r y) mix ?_ ?_ ?_ F h  · intro r s    apply forest_carpool_component_coin_locality    intro i hi    have hi' : Γ.Reachable x (es.get i).1 := hi    simp only [mix, if_pos hi']  · intro r s    apply forest_carpool_component_coin_locality    intro i hi    have : ¬ Γ.Reachable x (es.get i).1 := fun h => hxy (h.trans hi.symm)    simp only [mix, if_neg this]  · intro r s; funext i; simp only [mix]; split_ifs <;> rfltheorem env_all (n : ℕ) : ∀ es : List (Fin n × Fin n), CarpoolForestEdgeSequence n es →    ∀ w, forest_greedy_law_enveloped (Fin es.length → Bool)      (fun r => forest_carpool_final_discrepancy n es r w) := by  intro es  induction es using List.reverseRecOn with  | nil =>    intro _ w    have h0 : ∀ r : Fin ([] : List (Fin n × Fin n)).length → Bool,        forest_carpool_final_discrepancy n [] r w = 0 := by      intro r; rw [ForestCarpoolLocal.final_eq]; simp [ForestCarpoolLocal.G]    refine ⟨⟨0, fun r => by show forest_carpool_final_discrepancy n [] r w % 2 = 0; rw [h0]; rfl⟩, fun z => ?_, fun k hk => ?_⟩    · simp only [h0]; congr 1; ext r; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega    · have : (Finset.univ.filter (fun r : Fin ([] : List (Fin n × Fin n)).length → Bool =>          (k : ℤ) ≤ forest_carpool_final_discrepancy n [] r w)) = ∅ := by        ext r; simp only [h0, Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty,          iff_false]; omega      rw [this, Finset.card_empty, Nat.cast_zero, zero_div]      unfold forest_carpool_tail_envelope; split_ifs <;> positivity  | append_singleton es e ih =>    intro hf w    obtain ⟨u, v⟩ := e    have hf0 := forest_init n es (u, v) hf    have ih' := ih hf0    have huv : u ≠ v := hf.1 (u, v) (by simp)    have hdis := forest_carpool_append_edge_disconnected n es u v hf    have key : forest_greedy_law_enveloped ((Fin es.length → Bool) × Bool)        (fun p => forest_carpool_final_discrepancy n (es ++ [(u, v)])          (coinEquiv es.length (es ++ [(u, v)]).length (by simp) p) w) := by      simp only [final_append]      by_cases hwu : w = u      · subst hwu        simp only [step_at_u n _ _ _ huv]        exact env_pair n es w v hdis forest_greedy_signed_step          (forest_greedy_envelope_preserved_by_independent_merge _ _ _ _ (ih' w) (ih' v))      · by_cases hwv : w = v        · subst hwv          simp only [step_at_v n _ _ _ huv]          have hm := forest_greedy_envelope_preserved_by_independent_merge _ _ _ _ (ih' w) (ih' u)          have hm' := enveloped_equiv            ((Equiv.refl _).prodCongr ((Equiv.refl _).prodCongr Equiv.boolNot)) _ hm          exact env_pair n es w u (fun h => hdis h.symm)            (fun a b c => forest_greedy_signed_step a b (!c)) hm'        · simp only [step_at_other n _ _ _ _ hwu hwv]          exact enveloped_extra _ (ih' w)    have := enveloped_equiv (coinEquiv es.length (es ++ [(u, v)]).length (by simp)).symm _ key    simpa using thisend ForestCarpoolTailtheorem forest_carpool_final_one_sided_fibonacci_tail (n : ℕ)    (edges : List (Fin n × Fin n)) (hf : CarpoolForestEdgeSequence n edges)    (v : Fin n) (D : ℕ) (hD : 1 ≤ D) :  (((Finset.univ.filter (fun r : Fin edges.length → Bool =>    (D : ℤ) ≤ forest_carpool_final_discrepancy n edges r v)).card : ℝ) /    (2 ^ edges.length : ℝ)) ≤ forest_carpool_tail_envelope D := by  have := (ForestCarpoolTail.env_all n edges hf v).2.2 D hD  simpa [Fintype.card_fun, Fintype.card_bool, Fintype.card_fin] using this
See it in the graphDiscuss this resultChallenge it