Верхние оценки сложности формул для симметрических булевых функций

Показано, что сложность реализации оператора подсчета числа единиц в булевом наборе длины $n$ формулами над базисом $B_2$ двуместных булевых функций не превосходит $n^{3.03}$, а над стандартным базисом $B_0$ – $n^{4.47}$. Как следствие, такие же оценки справедливы для сложности любой пороговой симметрической функции $n$ переменных, в частности, для функции голосования. Для сложности произвольной симметрической функции $n$ переменных получены оценки $n^{3.04}$ и $n^{4.48}$ над базисами $B_2$ и $B_0$ соответственно. Доказательство основано на применении модулярной арифметики.