Lemma A.2 — for ,
ProvedSubexpPermanent.Main.lemma_A_2p2o-gran-per-chapterp2o-plan-paperp2o-v1permanentreal-inequalities
For real numbers and ,
This inequality shows that the dependence of the optimization accuracy on adds at most a polynomial factor in to the running time of Theorem 1.2 (with , ).
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace SubexpPermanent.Main
/-- Lemma A.2, p. 38, eq. (36). -/
theorem lemma_A_2 (t b z : ℝ) (ht : 1 ≤ t) (hb : 0 ≤ b) (hz : 0 ≤ z) :
t * (b + Real.log (z + Real.exp 1)) ^ 2 ≤ 2 * t * (b + Real.log t + 1) ^ 2 + 2 * z := by sorry
end SubexpPermanent.Main
Source
Kudria, Luo, Majid, Subexponential Approximation of the Permanent in Deterministic Polynomial Time, arXiv:2609.10516 (held PDF, sha256 e752b6f0…), p. 38, Lemma A.2, eq. (36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.