# Parity

## Definition

TODO: extend the page to include parity of some specific $k$ bits out of the entire $n$.

The $n$-variable parity function is the Boolean function $f:\{-1,1\}^n\to\{-1,1\}$ defined by $f(x)=x_1 \cdot x_2 \cdot \ldots \cdot x_n$. In other words, $f(x)=1$ if and only if the number of ones in the vector $x\in\{-1,1\}^n$ is odd.

## Properties

• Parity only depends on the number of ones and is therefore a symmetric Boolean function.
• Over $\{-1,1\}$, the representation of the parity function is exactly the monomial $x_1 x_2 \ldots x_n$. Thus all of its Fourier mass rests on the highest level.
• The n-variable parity function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2 n − 1 monomials of length n and all conjunctive normal forms have the maximal number of 2 n − 1 clauses of length n. 
• Parity is not in AC0: A constant-depth Boolean circuit must have super-polynomial size in order to represent the parity function.  In fact, a circuit of depth $d$ must have size $\exp n^{\Theta (\frac{1}{d-1})}$ in order to exactly compute parity. This is tight: there exists a circuit of this size which computes parity.  
• Parity cannot even be approximated in AC0: A circuit of depth $d$ and size $S$ can only have a correlation of $2^{-c_d n / (\log S)^{d-1} }$ with parity. 
• Parity over $n$ bits is odd when $n$ is odd, and even when $n$ is even.