# Iterated majority

## Definition

Let $n = 3^k$. The iterated majority function $f:\{-1,1\}^n \to \{-1,1\}$ is a recursively-defined variation on the majority function:

 $f(x) = \begin{cases} \textrm{maj}(x), & \textrm{if}~ n = 3 \\ \textrm{maj}(f(x^{(1)}),f(x^{(2)}),f(x^{(3)}) & \textrm{otherwise}, \end{cases}$

where $x^{(1)} = (x_1,x_2\ldots x_{n/3})$, $x^{(2)} = (x_{n/3+1},\ldots x_{2n/3})$ and $x^{(3)} = (x_{2n/3+1},\ldots x_{n})$.

• TODO