forest_carpool_final_one_sided_fibonacci_tail
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
- forest_carpool_maximum_fibonacci_tailFor a forest arrival sequence, the probability that any vertex at any prefix has absolute discrepancy at least D is at most four times the…
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.
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.
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
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`.
uses
card_comp_equiv',Fintype.card_congrobtain ⟨⟨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 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.
uses
Finset.card_product,Finset.card_univ,Fintype.card_bool,Fintype.card_prod,mul_div_mul_rightobtain ⟨⟨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)]
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.
uses
Finset.card_nbij',card_comp_equiv',Nat.eq_of_mul_eq_mul_rightobtain ⟨⟨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
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.
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)
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`.
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
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]`.
uses
List.ext_getElem,List.getElem_ofFn,List.getElem_appendapply 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
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.
uses
ForestCarpoolLocal.final_eq,ofFn_coinEquiv,G_appendobtain ⟨r, c⟩ := p rw [ForestCarpoolLocal.final_eq, ForestCarpoolLocal.final_eq, ofFn_coinEquiv, G_append n e c es _ _ (by simp)]
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`.
uses
if_negsimp only [carpool_step, ForestCarpoolLocal.gbit, forest_greedy_signed_step, if_neg huv] cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)
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`.
uses
if_negsimp only [carpool_step, ForestCarpoolLocal.gbit, forest_greedy_signed_step, if_neg huv.symm] cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)
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`.
simp [carpool_step, hu, hv]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`.
uses
List.mem_append_left,List.map_append,List.sublist_append_left,SimpleGraph.fromEdgeSet_adjobtain ⟨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⟩
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.
uses
enveloped_diag,forest_carpool_component_coin_locality,if_pos,if_negclassical 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
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$.
uses
List.reverseRecOn,ForestCarpoolLocal.final_eq,Finset.card_empty,Nat.cast_zero,zero_divintro 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
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`.
uses
forest_init,forest_carpool_append_edge_disconnected,final_append,step_at_u,env_pair,forest_greedy_envelope_preserved_by_independent_mergerw [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
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.
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 _ keyThe 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`.
uses
ForestCarpoolTail.env_all,Fintype.card_fun,Fintype.card_bool,Fintype.card_finhave := (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`.
- The file proves several auxiliary lemmas establishing that discrepancy laws are invariant under coin space equivalences and component decoupling before proving by reverse induction that discrepancy laws on forests are enveloped.
- Unresolved check: no step explains line(s) 153, 259 -- every tactic of the proof has to belong to some step
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 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