קולוקוויום בביה"ס למדעי המחשב - Improved Lower Bounds for the Fourier Entropy/Influence Conjecture via Lexicographic Functions

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 〈2/3〉 of measure 2/3 to demonstrate that C >= 4+3 log_4 (3) > 6.377444. The second generalizes their construction to biased functions and obtains C > 6.413846 using, 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.