Formula Complexity of a Linear Function in a $k$-ary Basis

A way of extending the Khrapchenko method of finding a lower bound for the complexity of binary formulas to formulas in $k$-ary bases is proposed. The resulting extension makes it possible to evaluate the complexity of a linear Boolean function and a majority function of $n$ variables when realized by formulas in the basis of all $k$-ary monotone functions and negation as $\Omega(n^{g(k)})$, where $g (k)=1+\Theta(1/\ln k)$. For a linear function, the complexity bound in this form is unimprovable. For $k=3$, the sharper lower bound $\Omega(n^{1.53})$ is proved.