Fourier Entropy–Influence conjecture

A rule takes on/off switches and gives a yes-or-no answer. How much hidden structure can it have if changing one switch rarely changes that answer? For the two-switch AND rule, which says yes only when both are on, flipping one switch changes the answer exactly when the other is on. Under equally likely settings, that happens half the time for each switch. Adding those probabilities gives its total influence. A second description breaks the rule into patterns involving individual switches and combinations of switches. The conjecture asks whether influence always limits how widely that description is spread across patterns.[3] [4]

Changing one input of a Boolean rule may rarely change its output, even though combinations of inputs matter. Must this total flip sensitivity control the spread of the rule’s Fourier weights? Work under the uniform distribution on $\{-1,+1\}^n$, where $n$ counts input switches, with a sign-valued output. For the two-switch AND rule, encode yes as +1 and no as −1. Then $f(x_1,x_2)=(-1+x_1+x_2+x_1x_2)/2$. Its four coefficients have magnitude one half, so each squared weight is one quarter. Its Fourier entropy is two bits, while each switch has influence one half and total influence is one. These are illustrative values, not evidence for every function.

For a set $S$ of input positions, the parity pattern is $\chi_S(x)=\prod_{i\in S}x_i$, with the empty product equal to one. The coefficient $\widehat f(S)=\mathbb E[f(x)\chi_S(x)]$ measures agreement averaged over all settings. Because the output is always a sign, the weights $p_S=\widehat f(S)^2$ sum to one. Their entropy is $H(f)=\sum_S p_S\log_2(1/p_S)$, with a zero-weight contribution defined as zero. Total influence is the sum of individual flip probabilities; equivalently $I(f)=\sum_S |S|p_S$. The conjecture is $H(f)\le C I(f)$ for a universal constant, independent of the dimension and function.[3] [4]

The required spread measure is Fourier entropy, which uses squared pattern weights, not just a count of switches. The conjecture needs one fixed constant that works for every Boolean rule and every number of switches, with settings equally likely. Results for particular rule families or bounds with an extra term do not establish that guarantee.[3] [4]

Han’s revised bound retains a sum involving individual influences in addition to total influence. González, MacManus and Pereyra compare a rule with the two smaller rules obtained by fixing one input to −1 or +1. A suitable bound on the resulting entropy difference would let the conjecture follow by repeated splitting. Their June 2026 results verify needed conditions for particular classes, including specified separation and tribes classes, rather than for every Boolean rule. The sign-valued output and uniform input measure are part of the statement; arbitrary real outputs or another distribution would change the problem.[3] [4]

The flip test examines one switch at a time, but a rule can depend on combinations that this local view hides. A positive answer would connect stability under these small changes to a compact approximate description using a limited collection of important patterns. It would make local sensitivity informative about global structure.[3]

Entropy controls concentration of squared coefficient weight. If the conjectured inequality holds, then for a fixed tolerated fraction $0<\delta<1$, at most $2^{CI(f)/\delta}$ coefficients can carry all but $\delta$ of the weight. Truncating to them gives an approximation in average squared error under the uniform measure. This is concentration in patterns, which can involve several inputs, rather than a guarantee that only a few original switches matter or that learning is automatically easy. It would explain how local flip stability limits the complexity of a global approximate representation.[3]