drf_geometric_mean_bound
For any natural number D, non-negative real opt, real values A, B, and Z1 with 0 ≤ A, A ≤ 2 * D * opt, B ≤ 8 * opt, and Z1^2 ≤ A * B, it holds that Z1 ≤ 4 * Real.sqrt D * opt.
Statement
theorem drf_geometric_mean_bound (D : ℕ) (opt A B Z1 : ℝ) (hopt : 0 ≤ opt) (hA : A ≤ 2 * (D : ℝ) * opt) (hB : B ≤ 8 * opt) (hA_nonneg : 0 ≤ A) (hCS : Z1 ^ 2 ≤ A * B) : Z1 ≤ 4 * Real.sqrt (D : ℝ) * opt- Source
- arXiv:2611.07905 Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness, Section 3.1.5
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any natural number $D$ and real numbers $opt$, $A$, $B$, and $Z_1$, if $0 \le opt$, $A \le 2 D \cdot opt$, $B \le 8 \cdot opt$, $0 \le A$, and $Z_1^2 \le A \cdot B$, then $Z_1 \le 4 \sqrt{D} \cdot opt$.
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
To bound Z1, we chain the upper bounds on A and B to bound the product A * B by (2 * D * opt) * (8 * opt) = 16 * D * opt^2. Algebraic expansion shows that (4 * Real.sqrt D * opt)^2 equals 16 * D * opt^2, so the hypothesis Z1^2 ≤ A * B implies Z1^2 ≤ (4 * Real.sqrt D * opt)^2. Because 4 * Real.sqrt D * opt is non-negative, taking square roots gives |Z1| ≤ 4 * Real.sqrt D * opt, which immediately implies Z1 ≤ 4 * Real.sqrt D * opt.
A * B ≤ (2 * D * opt) * (8 * opt)
Multiplying B ≤ 8 * opt on the left by A ≥ 0 yields A * B ≤ A * (8 * opt) using mul_le_mul_of_nonneg_left. Since opt ≥ 0, the term 8 * opt is non-negative (checked by positivity), so multiplying A ≤ 2 * D * opt on the right by 8 * opt yields A * (8 * opt) ≤ (2 * D * opt) * (8 * opt) using mul_le_mul_of_nonneg_right.
uses
mul_le_mul_of_nonneg_left,mul_le_mul_of_nonneg_righthave hAB1 : A * B ≤ A * (8 * opt) := mul_le_mul_of_nonneg_left hB hA_nonneg have hAB2 : A * (8 * opt) ≤ (2 * (D : ℝ) * opt) * (8 * opt) := mul_le_mul_of_nonneg_right hA (by positivity)
Z1^2 ≤ (4 * Real.sqrt D * opt)^2
We first compute (4 * Real.sqrt D * opt)^2 = 16 * D * opt^2. By distributing the exponent over multiplication (mul_pow) and simplifying (Real.sqrt D)^2 = D since natural numbers are non-negative (Real.sq_sqrt and Nat.cast_nonneg), ring arithmetic simplifies 4^2 * D * opt^2 to 16 * D * opt^2. Substituting this identity into the goal, non-linear arithmetic (nlinarith) combines Z1^2 ≤ A * B with the bounds on A * B to deduce Z1^2 ≤ 16 * D * opt^2 = (4 * Real.sqrt D * opt)^2.
uses
mul_pow,Real.sq_sqrt,Nat.cast_nonneghave hAB : Z1 ^ 2 ≤ (4 * Real.sqrt (D : ℝ) * opt) ^ 2 := by have hsq : (4 * Real.sqrt (D : ℝ) * opt) ^ 2 = 16 * (D : ℝ) * opt ^ 2 := by rw [mul_pow, mul_pow, Real.sq_sqrt (Nat.cast_nonneg D)] ring rw [hsq] nlinarith
Z1 ≤ 4 * Real.sqrt D * opt
Since D and opt are non-negative, 4 * Real.sqrt D * opt is non-negative (via positivity). Together with Z1^2 ≤ (4 * Real.sqrt D * opt)^2, this implies |Z1| ≤ 4 * Real.sqrt D * opt by abs_le_of_sq_le_sq. Finally, because Z1 ≤ |Z1| by le_abs_self, linear arithmetic (linarith) concludes that Z1 ≤ 4 * Real.sqrt D * opt.
uses
abs_le_of_sq_le_sq,le_abs_selfhave hnonneg : 0 ≤ 4 * Real.sqrt (D : ℝ) * opt := by positivity have habs : |Z1| ≤ 4 * Real.sqrt (D : ℝ) * opt := abs_le_of_sq_le_sq hAB hnonneg linarith [le_abs_self Z1]
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality by a non-negative value on the left preserves the inequality.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality by a non-negative value on the right preserves the inequality.
mul_pow- The power of a product is the product of the powers: (a * b)^n = a^n * b^n.
Real.sq_sqrt- The square of the square root of a non-negative real number x equals x.
Nat.cast_nonneg- The cast of any natural number into an ordered semiring (such as the real numbers) is non-negative.
abs_le_of_sq_le_sq- If a^2 ≤ b^2 and b is non-negative, then |a| ≤ b.
le_abs_self- Every real number is bounded above by its absolute value: a ≤ |a|.
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.
/-- Geometric mean bound on congestion delay combining capacity and bottleneck bounds. -/theorem drf_geometric_mean_bound (D : ℕ) (opt A B Z1 : ℝ) (hopt : 0 ≤ opt) (hA : A ≤ 2 * (D : ℝ) * opt) (hB : B ≤ 8 * opt) (hA_nonneg : 0 ≤ A) (hCS : Z1 ^ 2 ≤ A * B) : Z1 ≤ 4 * Real.sqrt (D : ℝ) * opt := by have hAB1 : A * B ≤ A * (8 * opt) := mul_le_mul_of_nonneg_left hB hA_nonneg have hAB2 : A * (8 * opt) ≤ (2 * (D : ℝ) * opt) * (8 * opt) := mul_le_mul_of_nonneg_right hA (by positivity) have hAB : Z1 ^ 2 ≤ (4 * Real.sqrt (D : ℝ) * opt) ^ 2 := by have hsq : (4 * Real.sqrt (D : ℝ) * opt) ^ 2 = 16 * (D : ℝ) * opt ^ 2 := by rw [mul_pow, mul_pow, Real.sq_sqrt (Nat.cast_nonneg D)] ring rw [hsq] nlinarith have hnonneg : 0 ≤ 4 * Real.sqrt (D : ℝ) * opt := by positivity have habs : |Z1| ≤ 4 * Real.sqrt (D : ℝ) * opt := abs_le_of_sq_le_sq hAB hnonneg linarith [le_abs_self Z1]