La influencia $\operatorname{Inf}_i(f)$ cuenta cuántos de los pares de valores de entrada que difieren sólo en el $i$ -ésima coordenada tienen diferentes valores de función:
$$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]=2^{-n}\sum_x[f(x)\neq f(\hat x_i)]=2^{1-n}\sum_{\{ x,\hat x_i\}}[f(x)\neq f(\hat x_i)]\;,$$
donde el paréntesis es el Soporte Iverson y la última suma es sobre todos los pares desordenados $\{ x,\hat x_i\}$ que sólo se diferencian en el $i$ -coordenadas. Sumando esto sobre $i$ cuenta el número $\sigma(f)$ de pares de valores de entrada que difieren sólo en una coordenada y tienen diferentes valores de función (llamemos a tal par un "par de influencia"):
$$\sum_{i=1}^n\operatorname{Inf}_i(f)=2^{1-n}\sum_{i=1}^n\sum_{\{ x,\hat x_i\}}[f(x)\neq f(\hat x_i)]=2^{1-n}\sum_{\{ x,y\}}[f(x)\neq f(y)]=2^{1-n}\sigma(f)\;,$$
donde la última suma es sobre todos los pares desordenados $\{ x,y\}$ de los vecinos más cercanos, es decir, valores de entrada que sólo difieren en una coordenada.
Intuitivamente hablando, esta función está en un mínimo si el $-1$ s y $1$ (de los que tiene que haber el mismo número debido a la restricción de equilibrio) están agrupados y la interfaz entre ellos es lo más pequeña posible. Este es el caso si el $1$ s están todos en un hiperplano ortogonal a uno de los ejes, es decir, si $f$ es una función dictatorial. Podemos demostrarlo generalizando la afirmación y demostrándola por inducción:
Si el valor de la función de $f$ que ocurre con menos frecuencia ocurre $k$ veces, entonces $\sigma(f)\ge k$ . Además, $\sigma(f)=k$ si y sólo si $k=0$ o $f$ es una función dictatorial.
La afirmación es válida para $n=1$ : En este caso, tenemos $\sigma(f)=0$ para $k=0$ y $\sigma(f)=1$ para $k=1$ y en este último caso $f$ es una función dictatorial.
Supongamos ahora que la afirmación es válida para $n-1$ y considerar los dos hiperplanos con $x_n=\pm1$ . El $k$ los valores de la función se distribuyen de alguna manera en estos hiperplanos, con $k^-$ valores en $x_n=-1$ y $k^+$ valores en $x_n=+1$ y $k^-+k^+=k$ . Supongamos sin pérdida de generalidad que $k^+\ge k^-$ .
Sumemos los pares de influencia. Hay al menos $k^+-k^-$ tales pares de puntos que sólo difieren en el $i$ -coordenadas. Por la hipótesis de inducción, hay al menos $k^-$ pares de influencia en el hiperplano $x_n=-1$ ya que cualquier valor de la función es minoritario para $f$ también es minoritario en ese hiperplano.
El hiperplano $x_n=+1$ es sólo un poco más complicado de tratar. Si el mismo valor de la función es minoritario en ese hiperplano, entonces hay al menos $k^+$ pares de influencia en ese hiperplano por la hipótesis de inducción, y así al menos $k^-$ . Si el otro valor de la función es minoritario en ese plano, entonces hay al menos $2^{n-1}-k^+$ pares de influencia, y como $k^++k^-=k\le2^{n-1}$ Esto es también al menos $k^-$ pares de influencia. Así, cada hiperplano contribuye al menos con otro $k^-$ pares de influencia, por lo que la suma es al menos $k^+-k^-+2k^-=k^++k^-=k$ .
Para que el límite se alcance, debe lograrse en ambos hiperplanos individualmente. Si ambos hiperplanos tienen un solo valor de la función, entonces $f$ en su conjunto también tiene un solo valor de función ( $k=0$ ) o es una función dictatorial. Si uno de los hiperplanos tiene un solo valor de la función y $f$ es una función dictatorial en el otro hiperplano, el límite no se alcanza. Si $f$ es una función de dictadura en ambos hiperplanos, entonces el límite sólo se alcanza si las dictaduras están "alineadas", para no producir ningún par de influencia extra entre ellas, y en este caso $f$ también es una función dictatorial. En resumen, el límite se alcanza si y sólo si $k=0$ o $f$ es una función dictatorial. Esto completa la inducción.
La condición de equilibrio implica $k=2^{n-1}$ y la condición de influencia implica $\sigma(f)=2^{n-1}$ . Por la afirmación que se acaba de demostrar, esto implica que $f$ es una función dictatorial.
