Fact 2.3 — Gaussian tail and Mills bounds
ProvedRecGaussColoring.Main.fact_2_3algorithmsgraph-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For a real threshold , the standard Gaussian upper tail satisfies both inequalities
These bounds control Gaussian thresholds and logarithmic cardinality estimates throughout the analysis.
Differences from the source: none.
Preamble
import Definitions.Def_RecGaussColoring_Main_Gaussian open scoped RealInnerProductSpace open Filter MeasureTheory ProbabilityTheory open scoped Topology noncomputable section
Formal statement
namespace RecGaussColoring.Main
/-- Fact 2.3, p. 7, both bounds with the printed constants. -/
theorem fact_2_3 (t : ℝ) (ht : 0 < t) :
t/(1+t^2) * (1/Real.sqrt (2*Real.pi)) * Real.exp (-t^2/2) ≤ PhiTail t ∧
PhiTail t ≤ Real.exp (-t^2/2) := by sorry
end RecGaussColoring.Main
Source
Ijay Narang, Yukai Tang, STOC 2027 submission #295 (October 2026), Fact 2.3, (2.2), p. 7. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/295.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.