op_1106_forest_carpooling_random_greedy_double_exponential_tail
There exist absolute positive real constants c, C, and a such that for every natural number n, every forest edge sequence of length T ≥ 2 on Fin n, and every integer D ≥ 1, the uniform probability over all 2^T fair coin assignments that randomized greedy carpooling achieves maximum prefix discrepancy at least D is at most C * T * exp(-c * 2^(a * D)).
Statement
theorem op_1106_forest_carpooling_random_greedy_double_exponential_tail : ∃ (c C a : ℝ), 0 < c ∧ 0 < C ∧ 0 < a ∧ ∀ (n : ℕ) (edges : List (Fin n × Fin n)) (hT : 2 ≤ edges.length) (hforest : CarpoolForestEdgeSequence n edges) (D : ℕ) (hD : 1 ≤ D), let T := edges.length let high_discrepancy := Finset.univ.filter (fun r : Fin T → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r))) ((high_discrepancy.card : ℝ) / (2 ^ T : ℝ)) ≤ C * (T : ℝ) * Real.exp (-c * (2 : ℝ) ^ (a * (D : ℝ)))
- Related work
- OP-1106, proposed in this research system; related work arXiv:2611.00388 studies a different algorithm on general fixed sequences and does not pose this forest question.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- CarpoolForestEdgeSequenceA list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected…
- 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…
- carpool_max_discrepancyThe maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.
- 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…
- forest_carpool_envelope_expAt every positive integer level, the Fibonacci tail envelope is at most exp(-(log 2 / 4) times 2 to the power of half the level).
- 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.
Read back from the Lean
There exist positive real constants $c, C, a > 0$ such that for every natural number $n$, every list $\mathrm{edges}$ of pairs in $\mathrm{Fin}\ n \times \mathrm{Fin}\ n$ of length $T \ge 2$ satisfying $\mathrm{CarpoolForestEdgeSequence}(n, \mathrm{edges})$ (meaning: no edge is a self-loop, the list of undirected edges contains no duplicates, and the undirected graph formed by the edges is acyclic), and every positive integer $D \ge 1$: Let $T = \mathrm{edges.length}$. If fair random coins $r \in \mathrm{Fin}\ T \to \mathrm{Bool}$ are drawn uniformly at random to break ties in the online greedy carpooling algorithm on $\mathrm{edges}$, the probability that the maximum discrepancy across all vertices and all prefix steps is at least $D$ is bounded by: \[ \frac{|\{ r : \mathrm{Fin}\ T \to \mathrm{Bool} \mid \mathrm{carpool\_max\_discrepancy}(n, \mathrm{edges}, \mathrm{carpool\_greedy\_orientations}(n, \mathrm{edges}, \mathrm{List.ofFn}\ r)) \ge D \}|}{2^T} \le C \cdot T \cdot \exp\left(-c \cdot 2^{a D}\right). \]
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem shows that randomized greedy carpooling on any forest edge sequence achieves a doubly exponential tail bound on maximum discrepancy. The proof provides explicit constants c = ln 2 / 4, C = 4, and a = 1/2. It then combines two existing results: a bound on the maximum discrepancy probability in terms of a Fibonacci tail envelope (forest_carpool_maximum_fibonacci_tail), and a doubly exponential upper bound on that envelope (forest_carpool_envelope_exp), chaining them together by scaling and inequality transitivity.
It suffices to prove the doubly exponential tail bound for the explicit positive constants c = ln 2 / 4, C = 4, and a = 1/2.
We provide the explicit witnesses c = ln 2 / 4, C = 4, and a = 1 / 2. Because 1 < 2, ln 2 is strictly positive by Real.log_pos; positivity and numeric evaluation confirm that c, C, and a are all strictly positive.
uses
Real.log_poshave hlog : 0 < Real.log 2 := Real.log_pos (by norm_num) refine ⟨Real.log 2 / 4, 4, 1 / 2, by positivity, by norm_num, by norm_num, ?_⟩
It suffices to establish the probability bound for an arbitrary forest edge sequence and threshold D ≥ 1.
We introduce the graph size n, the edge list edges, the length bound hT (2 ≤ edges.length), the forest hypothesis hforest, and the discrepancy target D ≥ 1, and simplify the local definitions of the sequence length T and the set of high-discrepancy coin assignments.
intro n edges hT hforest D hD dsimp only
The probability of discrepancy at least D is bounded by 4 * T * forest_carpool_tail_envelope D.
We invoke forest_carpool_maximum_fibonacci_tail, an established result bounding the probability of high discrepancy under randomized greedy carpooling on a forest in terms of a Fibonacci-derived tail envelope.
uses
forest_carpool_maximum_fibonacci_tailhave hm := forest_carpool_maximum_fibonacci_tail n edges hforest D hDThe tail envelope is bounded by exp(-(ln 2 / 4) * 2^(D / 2)).
We invoke forest_carpool_envelope_exp, which provides the doubly exponential upper bound on the tail envelope function for any integer D ≥ 1.
uses
forest_carpool_envelope_exphave he := forest_carpool_envelope_exp D hDThe probability of discrepancy at least D is at most 4 * T * exp(-(ln 2 / 4) * 2^((1 / 2) * D)).
Since edges.length ≥ 0, the factor 4 * edges.length is non-negative, so multiplying the envelope bound by 4 * edges.length preserves the inequality via mul_le_mul_of_nonneg_left. Recognizing that (1 / 2) * D = D / 2 by ring arithmetic, transitivity of ≤ (le_trans) between the Fibonacci tail bound and this scaled envelope bound completes the proof.
uses
mul_le_mul_of_nonneg_left,le_transhave hfactor : 0 ≤ 4 * (edges.length : ℝ) := by positivity have hb := mul_le_mul_of_nonneg_left he hfactor have hExp : (1 / 2 : ℝ) * (D : ℝ) = (D : ℝ) / 2 := by ring rw [hExp] exact le_trans hm hb
Real.log_pos- For any real number x > 1, its natural logarithm ln x is strictly positive.
forest_carpool_maximum_fibonacci_tail- For any forest edge sequence of length T and discrepancy bound D ≥ 1, the probability under fair coin tosses that randomized greedy carpooling reaches maximum prefix discrepancy at least D is at most 4 * T * forest_carpool_tail_envelope D.
forest_carpool_envelope_exp- For any integer D ≥ 1, the carpooling tail envelope is bounded above by exp(-(ln 2 / 4) * 2^(D / 2)).
mul_le_mul_of_nonneg_left- If b ≤ c and 0 ≤ a, then a * b ≤ a * c.
le_trans- If a ≤ b and b ≤ c, then a ≤ c (transitivity of ≤).
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.
/-- Conjecture OP-1106: Randomized greedy carpooling achieves a doubly exponential tail bound on every oblivious forest edge arrival sequence. -/theorem op_1106_forest_carpooling_random_greedy_double_exponential_tail : ∃ (c C a : ℝ), 0 < c ∧ 0 < C ∧ 0 < a ∧ ∀ (n : ℕ) (edges : List (Fin n × Fin n)) (hT : 2 ≤ edges.length) (hforest : CarpoolForestEdgeSequence n edges) (D : ℕ) (hD : 1 ≤ D), let T := edges.length let high_discrepancy := Finset.univ.filter (fun r : Fin T → Bool => D ≤ carpool_max_discrepancy n edges (carpool_greedy_orientations n edges (List.ofFn r))) ((high_discrepancy.card : ℝ) / (2 ^ T : ℝ)) ≤ C * (T : ℝ) * Real.exp (-c * (2 : ℝ) ^ (a * (D : ℝ))) := by have hlog : 0 < Real.log 2 := Real.log_pos (by norm_num) refine ⟨Real.log 2 / 4, 4, 1 / 2, by positivity, by norm_num, by norm_num, ?_⟩ intro n edges hT hforest D hD dsimp only have hm := forest_carpool_maximum_fibonacci_tail n edges hforest D hD have he := forest_carpool_envelope_exp D hD have hfactor : 0 ≤ 4 * (edges.length : ℝ) := by positivity have hb := mul_le_mul_of_nonneg_left he hfactor have hExp : (1 / 2 : ℝ) * (D : ℝ) = (D : ℝ) / 2 := by ring rw [hExp] exact le_trans hm hb