A note on the formula size of the ``mod k'' functions (Q1264165)

The symmetric Boolean functions in n variables are defined as \(C^ n_ k(x_ 1,...,x_ n)\) iff \(\sum^{n}_{i=1}x_ i=0 mod k\). This note proves the existence of formulas of size \(O(n^ 2)\) for \(C^ n_ 3\), size \(O(n^{2.58})\) for \(C^ n_ 7\), and size \(O(n^ 3)\) for the functions \(C^ n_ 5\) and \(C^ n_{15}\).