Proof of Lemma 4.3 — the weighted geometric mean bound
ProvedHypercliqueFalse.weighted_geometric_meanalgebraic-algorithmsfine-grained-complexityhypercliquep2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be reals and . Then
(The first inequality bounds the minimum by the weighted geometric mean with weights , , .)
In the proof of Lemma 4.3 this turns the running time of the fastest of three algorithms into with .
Differences from the source:
- generalization: a, b, c positive integers (matrix dimensions), 0 < ϵ_{h−1} ≤ ϵ₂ → real a, b, c ≥ 1 and 0 < ε ≤ 2; reason: the chain holds there (the weights are nonnegative for ε ≤ 4, the last step needs ε ≤ 2 and c ≥ 1); specializes to the paper's values
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace HypercliqueFalse
/-- **The weighted-geometric-mean bound of the base case.** Fischer, *The Hyperclique Hypothesis is False*, arXiv:2611.03880 (held version, sha256 6bd5cf5d…7730), proof of
Lemma 4.3, p.12: "Bounding the minimum by a weighted geometric mean with weights 1−ϵ_{h−1}/4,
ϵ_{h−1}/8, and ϵ_{h−1}/8, we obtain min{abc^{1−ϵ_{h−1}}, a^{1−ϵ_{h−1}}bc², ab^{1−ϵ_{h−1}}c²} ≤
(ab)^{1−ϵ²_{h−1}/8} c^{1−3ϵ_{h−1}/4+ϵ²_{h−1}/4} ≤ (abc)^{1−ϵ²_{h−1}/8}".
Both inequalities of the chain, for real `a, b, c ≥ 1` and `0 < ε ≤ 2`. -/
theorem weighted_geometric_mean (a b c ε : ℝ) (ha : 1 ≤ a) (hb : 1 ≤ b) (hc : 1 ≤ c)
(hε : 0 < ε) (hε2 : ε ≤ 2) :
min (min (a * b * c ^ (1 - ε)) (a ^ (1 - ε) * b * c ^ 2)) (a * b ^ (1 - ε) * c ^ 2) ≤
(a * b) ^ (1 - ε ^ 2 / 8) * c ^ (1 - 3 * ε / 4 + ε ^ 2 / 4) ∧
(a * b) ^ (1 - ε ^ 2 / 8) * c ^ (1 - 3 * ε / 4 + ε ^ 2 / 4) ≤
(a * b * c) ^ (1 - ε ^ 2 / 8) := by sorry
end HypercliqueFalse
Source
Fischer, The Hyperclique Hypothesis is False, arXiv:2611.03880 (held version, sha256 6bd5cf5d…7730), proof of Lemma 4.3, p.12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.