Bohnenblust–Hille constant on the Boolean cube
Description of constant
Degreer at most $d$ functions $f:\lbrace \pm 1\rbrace^n\to\mathbb{R}$ have Fourier–Walsh expansion
\[f(x)=\sum_{S\subseteq [n], |S|\leq d} \widehat f(S) \ x^S, \qquad x^S:=\prod_{i\in S}x_i, \qquad [n]:=\lbrace 1,\dots,n\rbrace.\]For $d\in\mathbb{N}$ set $p_d:=\frac{2d}{d+1}$. The (degree $\le d$) Bohnenblust–Hille inequality asks for the smallest constant $C$ such that for every $n$ and every function $f:\lbrace \pm 1\rbrace^n\to\mathbb{R}$ of degree at most $d$ ($d\leq n$),
\[\left(\sum_{\substack{S\subseteq[n]\\ |S|\le d}} |\widehat f(S)|^{p_d}\right)^{1/p_d} \le C \|f\|_\infty, \qquad \|f\|_{\infty}:=\max_{x\in \lbrace \pm 1\rbrace^n}|f(x)|.\]Let $\mathrm{BH}^{\le d}_{\lbrace\pm1\rbrace}$ denote this best constant $C$ (which depends on $d$). We define
\[C_{26a}:=\sup_{d\ge 1}\mathrm{BH}^{\le d}_{\lbrace\pm1\rbrace}.\]Equivalently, $C_{26a}$ is the smallest constant for which the above inequality holds simultaneously for all degrees $d$ (with the exponent $p_d=\frac{2d}{d+1}$ depending on $d$ as above).
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $\infty$ | Trivial | the best general estimate currently available is subexponential growth: $\mathrm{BH}^{\le d}_{\lbrace\pm1\rbrace}\le C^{\sqrt{d \ \log \, d}}$ for an absolute constant $C>1$ [DMP2019]. |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $2$ | [ADGP2025] | Degree $d$ address function achieves the bound $2^{\frac{d-1}{d}}$. At present, chasing incremental improvements of lower bounds seems less compelling than establishing any finite uniform upper bound. That said, exhibiting a construction that forces the constant to exceed $100$ would already be a genuinely interesting result. |
Additional comments and links
- The exponent $p_d=\frac{2d}{d+1}$ is best possible (cannot be increased), even if the constant is allowed to depend on $d$. [Bl2001]
- The paper [DMP2019] proves the subexponential upper bound $\mathrm{BH}^{\le d}_{\lbrace\pm1\rbrace}\le C^{\sqrt{d\log d}}$ arXiv:1706.03670
- One application is to computational learning theory: quantitative bounds on the Bohnenblust–Hille constants for functions on $(\pm 1)^n$ yield improved upper bounds on the randomized query complexity for learning bounded degree-$d$ functions from random queries; see [EI2022].
References
- [ADGP2025] Arunachalam, S.; Dutt, A.; Escudero Gutiérrez, F.; Palazuelos, C. A cb-Bohnenblust–Hille inequality with constant one and its applications in learning theory. Math. Ann. 392 (2025), 3367–3396. doi:10.1007/s00208-025-03142-5.
- [BH1931] Bohnenblust, H. F.; Hille, E. On the absolute convergence of Dirichlet series. Ann. of Math. 32 (1931), no. 3, 600–622.
- [Bl2001] Blei, R. Analysis in Integer and Fractional Dimensions. Cambridge Univ. Press, 2001.
- [DMP2019] Defant, Andreas; Mastyło, Mieczysław; Pérez, Antonio. On the Fourier spectrum of functions on Boolean cubes. Math. Ann. 374 (2019), no. 1–2, 653–680. arXiv:1706.03670
- [EI2022] Eskenazis, Alexandros; Ivanisvili, Paata. Learning Low-Degree Functions from a Logarithmic Number of Random Queries. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC ‘22), 2022. arXiv:2109.10162. doi:10.1145/3519935.3519981.
Contribution notes
Prepared with assistance from ChatGPT 5.2 Pro.