Conjetura sobre la influencia de la entropía

En matemáticas, la conjetura de la influencia de la entropía es una afirmación sobre funciones booleanas originalmente conjeturada por Ehud Friedgut y Gil Kalai en 1996. ^{[ 1 ]}

Para una función${\displaystyle f:\{-1,1\}^{n}\to \{-1,1\},}$Nótese su expansión de Fourier.

${\displaystyle f(x)=\sum _{S\subset [n]}{\widehat {f}}(S)x_{S},{\text{ donde }}x_{S}=\prod _{i\in S}x_{i}.}$

La conjetura de entropía-influencia afirma que existe una constante absoluta C tal que${\displaystyle H(f)\leq CI(f),}$donde la influencia total${\displaystyle I}$se define por

${\displaystyle I(f)=\sum _{S}|S|{\widehat {f}}(S)^{2},}$

y la entropía${\displaystyle H}$(del espectro) se define por

${\displaystyle H(f)=-\sum _{S}{\widehat {f}}(S)^{2}\log {\widehat {f}}(S)^{2},}$

(donde x  log x se considera igual a 0 cuando x = 0).    

• Análisis de funciones booleanas

• Problemas sin resolver en teoría de números, lógica y criptografía.
• El Proyecto de Problemas Abiertos , problemas de geometría discreta y computacional.