2024/10/25 by Paata Ivanisvili, Ivanisvili, Paata, Roman Vershynin +3
Mathematics · #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2410.19949
We investigate the best constant J(n,d) such that Jackson's inequality infdeg(g) ≤ d ‖f - g‖∞ ≤ J(n,d) s(f), holds for all functions f on the hypercube \0,1\n, where s(f) denotes the sensitivity of f. We show that the quantity J(n, 0.499n) is bounded below by an absolute positive constant, independent of n. This complements Wagner's theorem, which establishes that J(n,d)≤ 1 . As a first application we show that reverse Bernstein inequality fails in the tail space L1≥ 0.499n improving over previously known counterexamples in L1≥ C log log (n). As a second application, we show that there exists a function f : \0,1\n → [-1,1] whose sensitivity s(f) remains constant, independent of n, while the approximate degree grows linearly with n. This result implies that the sensitivity theorem s(f) ≥ Ω(deg(f)C) fails in the strongest sense for bounded real-valued functions even when deg(f) is relaxed to the approximate degree. We also show that in the regime d = (1 - δ)n, the bound J(n,d) ≤ C min\δ, max\δ2, n-2/3\\ holds. Moreover, when restricted to symmetric real-valued functions, we obtain Jsymmetric(n,d) ≤ C/d and the decay 1/d is sharp. Finally, we present results for a subspace approximation problem: we show that there exists a subspace E of dimension 2n-1 such that infg ∈ E ‖f - g‖∞ ≤ s(f)/n holds for all f.