A Certified n=18 Lower Bound for the Fourier Entropy-Influence Constant from AI Autoresearch

Numaro AI Autoresearch

Plain language

What this result means

The Fourier Entropy-Influence conjecture asks whether the Fourier spectrum of every Boolean function has entropy controlled by its sensitivity to input changes. No finite universal upper bound is known. An explicit function with a larger certified ratio therefore forces any valid universal constant upward. Here the improvement comes from a structural correction to the previous record, not from changing the influence or relaxing monotonicity.

The live Optimization Problems repository record is the merged MI2026b n=17 construction at 6.514326913930565372. The new n=18 certificate reaches 6.521845710923046575 and has not yet been submitted for maintainer review.
The total influence remains exactly 261/128. The gain comes from increasing spectral entropy after splitting one four-cell auxiliary host into two uniform two-cell hosts.
The truth table is exactly balanced and exhaustive monotonicity checking finds zero violations across all 2,359,296 coordinate edges.
The included standalone checker and a separately written NumPy Walsh-Hadamard verifier both reproduce the strict beat from the published certificate.

The mathematical object

How one finite Boolean function forces a universal constant upward

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a Boolean function onn input bits. Write $[n]=\{1,\ldots,n\}$ for the input indices and let $S\subseteq[n]$ select a subset of them. Every such function has a Fourier expansion in parity characters:

\begin{aligned} f(x)&=\sum_{S\subseteq[n]}\widehat f(S)\,\chi_S(x),\\ \chi_S(x)&=\prod_{i\in S}x_i. \end{aligned}

Here $x=(x_1,\ldots,x_n)$ is an input, $\chi_S$ multiplies the coordinates indexed by $S$ , and $\widehat f(S)$ is the corresponding Fourier coefficient. Parseval's identity makes the squared coefficients $p_S$ a probability distribution over subsets.

01Measure how widely the Fourier mass is spread

\begin{aligned} p_S&=\widehat f(S)^2,\qquad \sum_{S\subseteq[n]}p_S=1,\\ H(f)&=\sum_{S\subseteq[n]}p_S\log_2\!\frac{1}{p_S},\\ I(f)&=\sum_{S\subseteq[n]}|S|\,p_S. \end{aligned}

02Ask for one constant that works for every Boolean function

C_{71}=\inf\!\left\{C>0:\ H(f)\le C\,I(f)\ \text{for every Boolean }f\right\}

The spectral entropy $H(f)$ is measured in bits. Total influence $I(f)$ is the average Fourier level, equivalently the sum of the probabilities that each input coordinate changes the output. The FEI conjecture says $C_{71}$ is finite; that is still open. A larger explicit ratio does not prove the conjecture, but it raises the minimum value any valid universal constant must have.

\widehat g(\varnothing)=0,\ H(g)>0 \quad\Longrightarrow\quad C_{71}\ge \frac{H(g)}{I(g)-1}

A seed $g$ is balanced when it outputs each sign equally often, so $\widehat g(\varnothing)=\mathbb E[g]=0$ . The new seed $g_{18}$ is also monotone under the standard coordinatewise Boolean order. The O'Donnell-Tan amplification rule turns that one finite truth table into a lower bound for the universal constant, including the restriction to monotone functions.

\begin{aligned} I(g_{18})&=\frac{261}{128},\\ \frac{H(g_{18})}{I(g_{18})-1} &>6.521845710923046575,\\ 6.521845710923046575 &>6.514326913930565372. \end{aligned}

The first inequality is the certified interval lower endpoint. The second compares it with the previous record's certified upper endpoint, so the strict beat does not depend on rounded display digits.

L_n:=\frac{H(g_n)}{I(g_n)-1}, \qquad L_{18}-L_{17}=\frac{1}{133}

262,144truth-table entries reconstructed from the artifact

2,770nonzero Fourier coefficients after the exact transform

261/128total influence, verified as an exact rational number

Visual notes

How to read the result

Historical chart of lower bounds for the Fourier Entropy-Influence constant with a magnified comparison of the previous 6.5143269 record and Numaro's 6.5218457 certificate. — **The lower-bound frontier**The full history gives scale; the magnified panel shows the final step from the merged n=17 record to the n=18 certificate. Both seeds have the same exact influence.

Schematic comparing an overloaded four-cell auxiliary variable in the n=17 construction with nine uniform two-cell auxiliary variables at n=18. — **Hosting dilution**In the n=17 seed, x10 handled four majority-boundary cells while seven auxiliaries handled two each. Moving two cells to the new x18 makes all nine hosts uniform.

Result table

A certified n=18 monotone construction raises the live lower bound by exactly 1/133.

Cell	Baseline	Numaro	Delta	Note
FEI lower bound	6.514326913930565372	6.521845710923046575	+1/133	strictly clears the previous certified upper endpoint
Seed dimension	n=17	n=18	+1 variable	262,144-entry truth table
Total influence	261/128	261/128	unchanged	exact rational identity
Nonzero Fourier coefficients	2,578	2,770	+192	recomputed from the truth table
Logic monotonicity	verified	verified	0 violations	all 2,359,296 coordinate edges checked

Method

How it was found

The construction keeps the previous record's perturbed majority-of-nine core and fixes an asymmetry in its auxiliary layer. At n=17, x10 acts on four core-boundary cells while each of the other seven auxiliaries acts on two. Adding x18 and moving two of x10's cells onto it produces nine two-cell hosts. The moved Fourier weight is split more evenly, increasing entropy while leaving total influence unchanged.

Reproduced the merged MI2026b n=17 seed and its 261/128 exact influence.
Separated the nine-variable majority core from the auxiliary-variable hosting map.
Added x18 and rehosted two of x10's four boundary cells, producing a uniform two-cells-per-auxiliary layer.
Scanned 16,838 single swap-freeze, relocate, and rehost moves; none improved the n=18 seed within that move class.

Verification

How it was checked

The published artifact encodes the full truth table as a hex bitmask and binds it to SHA-256 f8a7bb2c...7839. The self-contained checker and an independently written NumPy verifier rebuild all 262,144 values, compute the integer Walsh-Hadamard spectrum, assert Parseval and exact balance, derive I=261/128 as a Fraction, enclose spectral entropy with interval arithmetic, exhaustively check monotonicity, and compare the new lower endpoint against the previous record's certified upper endpoint. Both included checkers pass in local reruns.

Scope

What is not being claimed

This is a certified candidate lower-bound update, not yet an accepted repository record. It does not prove the FEI conjecture, provide a finite upper bound, or establish that the n=18 seed is globally optimal. The 16,838-move scan certifies only local optimality within the stated construction moves; richer cores and multi-variable tail functions remain open.

References

Baseline sources

Citation

How to cite

Numaro AI Autoresearch. "A Certified n=18 Lower Bound for the Fourier Entropy-Influence Constant from AI Autoresearch." Numaro Research Report NUMARO-2026-016, 2026.

@techreport{numaro2026FourierEntropyInfluence,
  title = {A Certified n=18 Lower Bound for the Fourier Entropy-Influence Constant from AI Autoresearch},
  author = {Numaro AI Autoresearch},
  institution = {Numaro},
  number = {NUMARO-2026-016},
  year = {2026},
  url = {https://numaro.tech/research/fourier-entropy-influence-2026/}
}