New improved bound on Fourier analysis of Boolean functions
An $m^{2.943}$ Bohnenblust--Hille Bound on the Boolean Cube
Information Theory
Summary
This paper improves how well we can measure certain aspects of functions defined on Boolean cubes, which are mathematical objects used to model binary inputs. The authors provide a tighter upper limit on a key mathematical expression involving these functions' Fourier coefficients, reducing previous rough estimates drastically. This refined bound helps understand the complexity and behavior of these functions better. Their work focuses on carefully analyzing different layers of the function's structure to get more accurate results.
What this means in practice
- •For computer scientists: Better bounds on Fourier coefficients improve understanding of Boolean function complexity relevant for algorithms.
- •For quantum algorithm designers: Tighter Fourier bounds can inform the design and analysis of quantum queries involving Boolean functions.
A theory result. No direct application yet.
Authors
Joseph Slote, Chun-Kai Tseng, Alexander Volberg
Abstract
Let $q_m=2m/(m+1)$ and put \[ β_0=\frac{3}{2}+\frac{1}{\log 2}=2.9426950408\ldots, \] where $\log$ is the natural logarithm. We give a proof scheme showing that, for every $\varepsilon>0$, there is $C_\varepsilon<\infty$ such that every complex-valued function $f:\{-1,1\}^n\to\C$ of Fourier degree at most $m$ satisfies \[ \left(\sum_{A\subseteq[n]}\abs{\wh f(A)}^{q_m}\right)^{1/q_m} \le C_\varepsilon m^{β_0+\varepsilon}\norm{f}_\infty. \] The improvement over the $m^9$ estimate of the earlier draft has two ingredients. The first three Fourier levels are estimated at the scales $m$, $m^{3/2}$, and $m^{5/3}$. These losses are encoded in the weight $M^{μ_r/r}r^B\min\{r,L_M\}^8$, $L_M\asymp_B \log (M+1)$, with $μ_r=\lceil3r/2\rceil$ for $r\ge2$. A parity-compatible central window handles $r<L_M$, while a shrinking balanced window handles $r\ge L_M\asymp_B\log(M+1)$, no parity is used in this regime. The leading high-degree loss--gain factor is $\ee\,2^{-B}$; careful uniform bounds close the bootstrap for every $B>1/\log2$. The formula for $μ_r$ is explained below.