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)\leq 1 $. As a first application we show that reverse Bernstein inequality fails in the tail space $L^{1}_{\geq 0.499n}$ improving over previously known counterexamples in $L^{1}_{\geq C \log \log (n)}$. 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) \geq \Omega(\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 - \delta)n$, the bound \[ J(n,d) \leq C \min\{\delta, \max\{\delta^2, n^{-2/3}\}\} \] holds. Moreover, when restricted to symmetric real-valued functions, we obtain $J_{\mathrm{symmetric}}(n,d) \leq 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} \|f - g\|_{\infty} \leq s(f)/n$ holds for all $f$.

Locations

• arXiv (Cornell University) - View - PDF