OpenFrontiers
Join
← Back to the index
OP-12034OpenAnalysis

Bohnenblust--Hille constant on the Boolean cube (C26aC_{26a})

Bohnenblust--Hille constant on the Boolean cube: determine C26aC_{26a} or improve its bounds; the repository records 22 (lower) and ∞\infty (upper).

MSC 06E30 · Boolean functionsMSC 46G25 · (Spaces of) multilinear mappings, polynomials

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Degree at most dd functions f:{±1}n→Rf:\lbrace \pm 1\rbrace^n\to\mathbb{R} have Fourier--Walsh expansion

f(x)=∑S⊆[n],∣S∣≤df^(S) xS,xS:=∏i∈Sxi,[n]:={1,…,n}.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∈Nd\in\mathbb{N} set pd:=2dd+1p_d:=\frac{2d}{d+1}. The (degree ≤d\le d) Bohnenblust--Hille inequality asks for the smallest constant CC such that for every nn and every function f:{±1}n→Rf:\lbrace \pm 1\rbrace^n\to\mathbb{R} of degree at most dd (d≤nd\leq n),

(∑S⊆[n]∣S∣≤d∣f^(S)∣pd)1/pd≤C∥f∥∞,∥f∥∞:=max⁡x∈{±1}n∣f(x)∣.\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 BH{±1}≤d\mathrm{BH}^{\le d}_{\lbrace\pm1\rbrace} denote this best constant CC (which depends on dd). We define

C26a:=sup⁡d≥1BH{±1}≤d.C_{26a}:=\sup_{d\ge 1}\mathrm{BH}^{\le d}_{\lbrace\pm1\rbrace}.

Equivalently, C26aC_{26a} is the smallest constant for which the above inequality holds simultaneously for all degrees dd (with the exponent pd=2dd+1p_d=\frac{2d}{d+1} depending on dd as above).

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • The exponent pd=2dd+1p_d=\frac{2d}{d+1} is best possible (cannot be increased), even if the constant is allowed to depend on dd. [Bl2001]
  • The paper [DMP2019] proves the subexponential upper bound BH{±1}≤d≤Cdlog⁡d\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 (±1)n(\pm 1)^n yield improved upper bounds on the randomized query complexity for learning bounded degree-dd functions from random queries; see [EI2022].

References (from the repository page)

  • [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.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 22; best known upper bound ∞\infty. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
∞\infty Trivial the best general estimate currently available is subexponential growth: BH{±1}≤d≤Cd log⁡ d\mathrm{BH}^{\le d}_{\lbrace\pm1\rbrace}\le C^{\sqrt{d \ \log \, d}} for an absolute constant C>1C>1 [DMP2019].

Known lower bounds

Bound Reference Comments
22 [ADGP2025] Degree dd address function achieves the bound 2d−1d2^{\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 100100 would already be a genuinely interesting result.
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Bohnenblust--Hille constant on the Boolean cube ($C_{26a}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.