## A general lower bound for formula size of symmetric boolean functions

Recall that a boolean function $f:\{0,1\}^n\to\{0,1\}$ is *symmetric*
if the value $f(x)$ only depends on the number $|x|$ of ones in $x$.
Every such function corresponds to the function $f':\{0,1,\ldots,n\}\to\{0,1\}$
given by $f'(a)=1$ iff $f(x)=1$ for all $x$ of weight $|x|=a$.
Let $I_{n,d}$ denote the interval $\{\tfrac{n}{2}-d,\ldots,\tfrac{n}{2}+d\}$.
Say that a symmetric boolean function $f(x)$ is $d$-*trivial* if either
$f'$ is constant in the interval $I_{n,d}$, or $f'(a+1)\neq f'(a)$ for all
$a \in I_{n,d}\setminus\{\tfrac{n}{2}+d\}$. Note that for every $d$, at most
$4\cdot 2^{n+1-2d}$ of all $2^{n+1}$ symmetric functions can be $d$-trivial.
Define
\[
d(f)=\min\{d\colon \mbox{$f$ is not $d$-trivial}\}.
\]
For example, if $f$ is the majority function, then $d(f)=1$.
But if $f$ is the parity function,
then $d(f)$ is maximal, is about $n/2$.

Let $k\geq 2$ be an arbitrary (but fixed) integer, and let $L(f)$ denote the smallest
leaf-size of a formula computing $f$, with all boolean functions of $k$
variables allowed as gates.

**Theorem (Cherukhin 2000):**
For every symmetric boolean function $f$ of $n$ variables,
\[
L(f)=\Omega\Big(n\cdot \ln\frac{n}{d(f)} \Big).
\]

This extends Theorem 6.21 in the book to formulas using arbitrary boolean functions of larger
number $k$ of variables (larger than $k=2$). Cherukhin's proof is also entirely different.
For example, if $f$ is the majority function, then $d(f)=1$, and we obtain
$L(f)=\Omega(n\log n)$. But if $f$ is the parity function,
then $d(f)$ is maximal, is about $n/2$, and we only obtain $L(f)=\Omega(n)$.
This is not strange: formulas are allowed tu use *arbitrary* boolean functions of a constant
number of variables, including $x\oplus y$, as gates.

**Reference:**:

- D. Yu. Cherukhin (2000): Lower bounds for the formula complexity of symmetric Boolean functions,
Diskretn. Anal. Issled. Oper., Ser. 1, 7:3 (2000), 86-98.
Paper (in Russian)

S. Jukna, April 2013