Fourier Entropy-Influence Conjecture

Fourier Entropy-Influence Conjecture

Definitions and mathematical statement

For $f:\{-1,1\}^n\to\{-1,1\}$, write its uniform Fourier expansion as $f(x)=\sum_{S\subseteq[n]}\widehat f(S)\chi_S(x)$, where $\chi_S(x)=\prod_{i\in S}x_i$ and $\widehat f(S)={\mathbb{E}}[f\chi_S]$. Parseval gives $\sum_S\widehat f(S)^2=1$. Define spectral entropy and total influence by \[ \operatorname{Ent}(f)=\sum_S\widehat f(S)^2 \log_2\frac1{\widehat f(S)^2},\qquad I(f)=\sum_i{\mathbb{P}}[f(x)\ne f(x^{\oplus i})] =\sum_S|S|\widehat f(S)^2, \] with zero terms contributing zero. The conjecture seeks a universal $C$ such that $\operatorname{Ent}(f)\le C I(f)$ for every $n,f$. The probability measure is uniform and $x^{\oplus i}$ flips one coordinate. The constant cannot depend on dimension or on the Boolean function.

Formulation and concept references: [S1].

Short English statement

Is the entropy of every Boolean function's squared Fourier coefficients controlled by a universal constant times its total influence?

Research attempt

Scope and process.

This attempt by GPT-6 Astra Ultra, dated 27 September 2026, views squared Fourier coefficients as a probability distribution on subsets. It derives a general entropy bound, computes a family approaching a nonzero entropy/influence ratio, and checks the effect of independent products. The work consists of standard Fourier and entropy calculations, not a new general inequality.

The source [S1] studies further evidence for the conjecture, rather than announcing its resolution for all Boolean functions. We keep its uniform-cube and base-two entropy convention. The first remaining gap is to use the Boolean identity $f^2=1$ to remove the dimension-dependent logarithm in the general estimate below. An inequality for arbitrary probability distributions on subsets would be false.

A random spectral set and a general bound.

Let $\mathcal S$ be a random subset of $[n]$ with $\mathbb P(\mathcal S=S)=\widehat f(S)^2$. Parseval makes this a probability law. Write \[ p_i=\mathbb P(i\in\mathcal S) =\sum_{S\ni i}\widehat f(S)^2,\qquad I=\sum_i p_i. \] Then spectral entropy is exactly the Shannon entropy of the indicator vector of $\mathcal S$. By the chain rule and the fact that conditioning cannot increase entropy, \[ \operatorname{Ent}(f)\le\sum_{i=1}^n h_2(p_i) \le n\,h_2(I/n), \tag{412.1} \] where $h_2(u)=-u\log_2u-(1-u)\log_2(1-u)$ and the second step is concavity.

For $0<u\le1$, the inequality $-(1-u)\ln(1-u)\le u$ gives $h_2(u)\le u\log_2(e/u)$. Therefore, if $I>0$, \[ \operatorname{Ent}(f)\le I\log_2(en/I). \tag{412.2} \] If $I=0$, all Fourier mass is at the empty set, so the Boolean function is constant and the entropy is zero. Thus this exceptional case is settled without division by zero.

The estimate becomes dimension-free when $I$ is a fixed positive fraction of $n$. It is inadequate in the low-influence regime, where the conjecture has its content. Concavity alone cannot remove this loss.

A countertest without the Boolean constraint.

Consider the real-valued function \[ g_n(x)=\frac1{\sqrt n}\sum_{i=1}^n x_i. \] It has $L^2$ norm one, and its squared Fourier distribution is uniform on the $n$ singleton subsets. That distribution has entropy $\log_2 n$ and expected cardinality one. Hence no universal inequality bounding entropy by a constant times expected set size holds for arbitrary normalized Fourier spectra.

For $n>1$ this function is not $\{-1,1\}$-valued. In particular it reaches $\sqrt n$ at the all-positive input. Rescaling it into $[-1,1]$ changes the normalization of the squared coefficients and does not turn it into a Boolean function. The example isolates the necessity of Boolean structure; it is not a counterexample to the stated conjecture.

One exact algebraic restriction from Booleanity is \[ \sum_S\widehat f(S)\widehat f(S\triangle T) =\begin{cases}1,&T=\varnothing,\\0,&T\ne\varnothing.\end{cases} \tag{412.3} \] This follows by taking the Fourier coefficients of $f^2=1$. Equation $412.1$ ignores these signed convolution identities completely. The missing structural work is to make them impose the required entropy bound.

A family with ratio tending to four.

Let $f_n$ equal $-1$ only at the all-positive input and $1$ elsewhere. Put $p=2^{-n}$. Since the indicator of that input is $2^{-n}\prod_i(1+x_i)$, its Fourier coefficients are \[ \widehat f_n(\varnothing)=1-2p,\qquad \widehat f_n(S)=-2p\quad(S\ne\varnothing). \] Set $a=(1-2p)^2$ and $q=1-a=4p(1-p)$. Direct substitution gives \[ \operatorname{Ent}(f_n) =-a\log_2a+q(2n-2),\qquad I(f_n)=2np. \tag{412.4} \] The influence identity can also be checked directly: flipping coordinate $i$ changes the answer exactly when all other coordinates are positive, which has probability $2^{-(n-1)}=2p$.

The elementary inequality $-a\log_2a\le(1-a)\log_2e$ yields \[ \operatorname{Ent}(f_n) \le q(2n-2+\log_2e) \le 4p(2n)=4I(f_n). \] The conventions at $a=0$ handle $n=1$. As $n\to\infty$, the first term of the entropy is $O(p)$, while $q/p\to4$. Consequently \[ \frac{\operatorname{Ent}(f_n)}{I(f_n)}\longrightarrow4. \] Thus any universal constant in the conjecture must be at least four. This is a lower bound on a possible constant, not a claim that four works for all Boolean functions. The family also shows why tiny influence does not force tiny entropy relative to influence.

Independent products preserve the ratio scale.

Let $g$ and $h$ be Boolean functions on disjoint variable sets and put $f(x,y)=g(x)h(y)$. Their Fourier coefficients satisfy \[ \widehat f(S\sqcup T)=\widehat g(S)\widehat h(T). \] Therefore the spectral distribution of $f$ is a product distribution, and \[ \operatorname{Ent}(f)=\operatorname{Ent}(g)+\operatorname{Ent}(h), \qquad I(f)=I(g)+I(h). \tag{412.5} \] The second identity follows either from the expected cardinalities of the two independent spectral sets or directly from flipping a coordinate in one factor.

If both influences are positive, the ratio for $f$ is a weighted average of the two ratios. Zero-influence factors are constants and contribute zero entropy. Hence taking disjoint products of one example cannot amplify its ratio beyond the largest ratio already present. A proposed counterexample construction based only on repeating independent blocks fails for this exact reason. Conversely an established bound with one constant is closed under such products.

The linear Boolean subcase.

Suppose a Boolean function has degree at most one: $f=a_0+\sum_i a_i x_i$. Comparing the coefficients of $x_ix_j$ in $f^2=1$ gives $a_ia_j=0$ for distinct $i,j$. Thus at most one nonconstant coefficient is nonzero. If it is $a_i$, the coefficient of $x_i$ also gives $a_0a_i=0$, so $a_0=0$ and the constant coefficient forces $a_i=\pm1$.

The only possibilities are constants and signed coordinate functions. Their spectra have a single atom, so spectral entropy is zero. This is a complete degree-one subcase. It contrasts with the normalized non-Boolean sum $g_n$, whose spread-out singleton spectrum is forbidden precisely by $412.3$.

Verification and the remaining obstruction.

The local script computes Fourier transforms of every Boolean function on up to four variables using integer Walsh sums. It verifies Parseval, both influence formulas, the entropy upper bound, and the special-family formulas. Floating-point logarithms are used only to report entropy values; the coefficient and influence identities are exact. Independent-product examples check the additivity identities separately.

Finite enumeration cannot bound the ratio for all dimensions. Nor does the AND-type calculation exclude more complicated interacting spectra. The first missing theorem is a consequence of $412.3$ and Booleanity strong enough to replace the logarithm in $412.2$ by an absolute constant, especially when $I/n$ is very small.

Outcome.

UNRESOLVED. We obtain the general dimension-dependent entropy bound, exact degree-one and independent-product behavior, and a family proving that any universal constant must be at least four. No dimension-free upper bound or Boolean counterexample is established.

Sources

• S1 Maria Jose Gonzalez, Paul MacManus, Maria Cristina Pereyra, "Further evidence towards the Fourier Entropy-Influence conjecture," arXiv:2606.00246 (June 2026). https://arxiv.org/abs/2606.00246. Formulation source.