Bohnenblust–Hille constant on the Boolean cube

Description of constant

Degree at most $d$ functions $f:\{\pm 1{\}}^n\to \mathbb{R}$ have Fourier--Walsh expansion

$$f(x)=\sum _{S\subseteq [n],|S|\le d}\hat{f}(S)x^S,x^S:=\prod _{i\in S}{x}_i,[n]:=\{1,\dots ,n\}.$$

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:\{\pm 1{\}}^n\to \mathbb{R}$ of degree at most $d$ ($d\le n$),

$${\left(\sum _{\begin{array}{c}S\subseteq [n]\\ |S|\le d\end{array}}|\hat{f}(S){|}^{p_d}\right)}^{1/p_d}\le C\Vert f{\Vert }_{\infty },\Vert f{\Vert }_{\infty }:=\underset{x\in \{\pm 1{\}}^n}{\max }|f(x)|.$$

Let ${\mathrm{BH}}_{\{\pm 1\}}^{\le d}$ denote this best constant $C$ (which depends on $d$). We define

$$C_{26a}:=\underset{d\ge 1}{\sup }{\mathrm{BH}}_{\{\pm 1\}}^{\le d}.$$

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

Known lower bounds

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}}_{\{\pm 1\}}^{\le d}\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.

-

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.