Iterated majority

Definition

Let [math]n = 3^k[/math]. The iterated majority function f:\{-1,1\}^n \to \{-1,1\}</math> is a recursively-defined variation on the majority function.

[math] f(x) = \begin{cases} maj(x), & if ~ n = 3 \\ maj(f(x^{(1)}),f(x^{(2)}),f(x^{(3)}) & otherwise, \end{cases}[/math]

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

Properties

• TODO