# Boolean circuit size bounds on the majority function

I am a bit lost in the literature. Is it known whether there is a $$o(n \log n)$$ size boolean circuit family for the majority function?

A binary full adder takes as input three bits $$x,y,z$$, and outputs two bits $$a,b$$ such that $$x+y+z = 2a+b$$.

Now suppose we are given $$2^n$$ bits $$x_1,\ldots,x_{2^n}$$. We compute as follows:

• $$x_1 + x_2 = 2a_1 + b_1$$.
• $$b_1 + x_3 + x_4 = 2a_2 + b_2$$. Thus $$x_1 + x_2 + x_3 + x_4 = 2(a_1 + a_2) + b_2$$.
• $$b_2 + x_5 + x_6 = 2a_3 + b_3$$. Thus $$x_1 + \cdots + x_6 = 2(a_1 + a_2 + a_3) + b_3$$.
• ...
• $$b_{2^{n-1}-1} + x_{2^n-1} + x_{2^n} = 2a_{2^{n-1}} + b_{2^{n-1}}$$. Thus $$x_1 + \cdots + x_{2^n} = 2(a_1 + \cdots + a_{2^{n-1}}) + b_{2^{n-1}}$$.

Using $$O(2^n)$$ gates, we computed $$2^{n-1}$$ bits $$a_1,\ldots,a_{2^{n-1}}$$ and a bit $$b_{2^{n-1}}$$ bits such that $$x_1 + \cdots + x_{2^n} = 2(a_1 + \cdots + a_{2^{n-1}}) + b_{2^{n-1}}.$$ Thus $$b^{2^{n-1}}$$ is the LSB of the sum $$x_1 + \cdots + x_{2^n}$$, and the higher-order bits of the sum are just the sum $$a_1 + \cdots + a_{2^{n-1}}$$. In particular, the majority of $$x_1,\ldots,x_{2^n}$$ is the same as the majority of $$a_1,\ldots,a_{2^{n-1}}$$. This gives a recursive circuit for majority whose size satisfies the recurrence $$S(N) = S(N/2) + O(N),$$ whose solution is $$S(N) = O(N)$$.

If implemented carefully, the circuit size is roughly $$5n$$. Demenkov, Kojevnikov, Kulikov, and Yaroslavstev improved this to roughly $$4.5n$$ in their paper New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions.