AFTD Auto-Formalizing Theoretical Domains

op_1106_forest_carpooling_random_greedy_double_exponential_tail

theoremverifiedoriginal

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.

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

    lines 14–15

    uses Real.log_pos

      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, ?_⟩
  2. 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.

    lines 16–17

      intro n edges hT hforest D hD
      dsimp only
  3. 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.

    line 18

    uses forest_carpool_maximum_fibonacci_tail

      have hm := forest_carpool_maximum_fibonacci_tail n edges hforest D hD
  4. The 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.

    line 19

    uses forest_carpool_envelope_exp

      have he := forest_carpool_envelope_exp D hD
  5. The 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.

    lines 20–24

    uses mul_le_mul_of_nonneg_left, le_trans

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

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