Symmetric Boolean function

The weight of the function can be calculated from its value vector:

$${\displaystyle |f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{k}}$$

The algebraic normal form either contains all monomials of certain order ${\displaystyle m}$, or none of them; i.e. the Möbius transform ${\displaystyle {\hat {f}}}$ of the function is also a symmetric function. It can thus also be described by a simple (n+1) bit vector, the ANF vector ${\displaystyle {\hat {f}}_{m}}$. The ANF and value vectors are related by a Möbius relation:

$${\displaystyle {\hat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}}$$

where ${\displaystyle k_{2}\subseteq m_{2}}$ denotes all the weights k whose base-2 representation is covered by the base-2 representation of m (a consequence of Lucas’ theorem).[3] Effectively, an n-variable symmetric Boolean function corresponds to a log(n)-variable ordinary Boolean function acting on the base-2 representation of the input weight.

For example, for three-variable functions:

$${\displaystyle {\begin{array}{lcl}{\hat {f}}_{0}&=&f_{0}\\{\hat {f}}_{1}&=&f_{0}\oplus f_{1}\\{\hat {f}}_{2}&=&f_{0}\oplus f_{2}\\{\hat {f}}_{3}&=&f_{0}\oplus f_{1}\oplus f_{2}\oplus f_{3}\end{array}}}$$

So the three variable majority function with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:

$${\displaystyle {\text{Maj}}(x,y,z)=xy\oplus xz\oplus yz}$$

The coefficients of the real polynomial agreeing with the function on ${\displaystyle \{0,1\}^{n}}$ are given by:

$${\displaystyle f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k}}f_{k}}$$

For example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):

$${\displaystyle {\text{Maj}}(x,y,z)=(xy+xz+yz)-2(xyz)}$$