Source-sensitive and sourcewise numerical budgets
DefinitionDistancePreserver934_Exact_Supplement_Budgetsadditive-spannersdistance-preserversgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a nonnegative vertex count , source count , demand count , and integer level , define the numerical expressions
These are real powers, with cast to a real number before division. They describe cost scales without asserting existence of any graph. The linear term is kept separately in the theorem statements.
Definition code
import Mathlib
set_option autoImplicit false
namespace DistancePreserver934.Exact.Supplement
open Classical
/-- The nonlinear source-sensitive term of Theorem 37, defined also at level zero. -/
noncomputable def F (k : ℕ) (n σ p : ℝ) : ℝ :=
n ^ ((8 + 8 * (k : ℝ)) / (9 + 8 * (k : ℝ))) *
(p * σ ^ k) ^ ((4 : ℝ) / (9 + 8 * (k : ℝ)))
/-- The nonlinear complete-sourcewise term of Theorem 40. -/
noncomputable def W (k : ℕ) (n σ : ℝ) : ℝ :=
n ^ ((8 + 8 * (k : ℝ)) / (5 + 8 * (k : ℝ))) *
σ ^ ((4 * (k : ℝ)) / (5 + 8 * (k : ℝ)))
end DistancePreserver934.Exact.Supplement
Source
Yanyu Chen, Yu Chen, Zihan Tan, Mingyang Yang, Improved Bounds on Distance Preservers, STOC 2027 submission #934 (October 2026); canonical source.pdf SHA-256 79b3d23a6e7b7fc6148c7a627181474a0129fb2f4c1d04ccd94c1da7987ed76b; Theorem 37, printed pp. 32–33 (PDF pp. 33–34); Theorem 40, printed p. 34 (PDF p. 35)