
























Every Boolean function can be uniquely represented as a multilinear polynomial. The entropy and the total influence are two ways to measure the concentration of its Fourier coefficients, namely the monomial coefficients in this representation: the entropy roughly measures their spread, while the total influence measures their average level. The Fourier Entropy/Influence conjecture of Friedgut and Kalai from 1996 states that the entropy to influence ratio is bounded by a universal constant $C$. Using lexicographic Boolean functions, we present three explicit asymptotic constructions that improve upon the previously best known lower bound $C>6.278944$ by O'Donnell and Tan, obtained via recursive composition. The first uses their construction with the lexicographic function $\ell\left\langle 2/3\right\rangle $ of measure $2/3$ to demonstrate that $C\ge4+3\log_{4}3>6.377444$. The second generalizes their construction to biased functions and obtains $C>6.413846$ using $\ell\left\langle Φ\right\rangle $, where $Φ$ is the inverse golden ratio. The third, independent, construction gives $C>6.454784$, even for monotone functions. Beyond modest improvements to the value of $C$, our constructions shed some new light on the properties sought in potential counterexamples to the conjecture. Additionally, we prove a Lipschitz-type condition on the total influence and spectral entropy, which may be of independent interest.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。