Jackson's inequality on the hypercube
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910670558068736 |
|---|---|
| author | Ivanisvili, Paata Vershynin, Roman Xie, Xinyuan |
| author_facet | Ivanisvili, Paata Vershynin, Roman Xie, Xinyuan |
| contents | 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 Ω(\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 - δ)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) \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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19949 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Jackson's inequality on the hypercube Ivanisvili, Paata Vershynin, Roman Xie, Xinyuan Functional Analysis Combinatorics Probability 41A10, 41A17, 68R05, 94C10, 42C10, 60C05 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 Ω(\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 - δ)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) \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$. |
| title | Jackson's inequality on the hypercube |
| topic | Functional Analysis Combinatorics Probability 41A10, 41A17, 68R05, 94C10, 42C10, 60C05 |
| url | https://arxiv.org/abs/2410.19949 |