Simplified Reed-Muller expressions for residue threshold functions (Q1882415)

A residue threshold function \(R(n,T| m)\) is a symmetric Boolean function of \(n\) variables \(x_i\) which is equal to 1 if and only if \(\sum_{i=1}^n x_i\), taken modulo \(m\), is greater than \(T-1\), where \(T\) and \(m\) are integers. In the paper the complexity of Reed-Muller expansions (also known as ring-sum expansions or algebraic normal forms) for these functions are studied.