Jackson's inequality on the hypercube

Abstract

We investigate the best constant $J(n,d)$ such that Jackson's inequality \[ \inf_{\mathrm{deg}(g) \leq d} \|f - g\|_{\infty} \leq 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)\le 1$. As a first application we show that reverse Bernstein inequality fails in the tail space $L_{\ge 0.499n}^1$ improving over previously known counterexamples in $L_{\ge C\log \log (n)}^1$. As a second application, we show that there exists a function $f:\{0,1{\}}^n\to [-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)\ge \hat{I}\text{c◯}(\mathrm{deg}(f{)}^C)$ fails in the strongest sense for bounded real-valued functions even when $\mathrm{deg}(f)$ is relaxed to the approximate degree. We also show that in the regime $d=(1-\hat{I}´)n$, the bound \[ J(n,d) \leq C \min\{δ, \max\{δ^2, n^{-2/3}\}\} \] holds. Moreover, when restricted to symmetric real-valued functions, we obtain $J_{\mathrm{symmetric}}(n,d)\le 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 $2^{n-1}$ such that ${\inf }_{g\in E}\Vert f-g{\Vert }_{\infty }\le s(f)/n$ holds for all $f$.