We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington, Beigel and Rudich. We use the framework established by the authors relating representations by symmetric polynomials to simultaneous protocols. We show that proving bounds on the degree of Threshold functions is equivalent to counting the number of solutions to certain Diophantine equations. This allows us to use tools from number theory to study such polynomial representations.

When $k$ is a fixed constant, we show that the degree of the Threshold-$k$ function (T_k) mod 6 is bounded by $O(n^{0.5 + \epsilon})$ for any $\epsilon > 0$ using a result of Filaseta on factors of numbers of the form $N(N + d)$. We show an upper bound of $O(n^{1/t + \epsilon})$ when $m$ has $t$ distinct prime factors using a theorem due to Granville, which generalizes Filaseta's result but which assumes the abc conjecture. We show that for $t=2$, the abc conjecture implies that the degree of $T_k$ is $O(nk)^{0.5 + \epsilon}$.

We show a lower bound of $\Omega(n^{1/t}k^{1 -1/t})$ for strong representations of $T_k$ mod $m$. When $t =2$, it nearly matches the upper bound of $O(nk)^{0.5 + \epsilon}$. Further, when $t=2$, we also show a similar weak lower bound. These lower bounds are proved by constructing solutions to the equations in question using a pigeonhole argument.

The $O(\sqrt n)$ upper bound for the OR function can be interpreted as follows: For suitably chosen parameters $k_2, k_3$ if $0 \leq w \leq n$ and $w mod 2^{k_2}$ and $w mod 3^{k_3}$ are both zero, then in fact $w=0$. Our bounds for $T_k$ give a similar result about the size of $w$: For $n$ sufficiently large and suitably chosen parameters $k_2, k_3$, if the residues $w mod 2^{k_2}$ and $w mod 3^{k_3}$ are both less than $k$, then in fact they are both equal to $w$ itself and $w < k$. Conversely, if $w \geq k$, then one of the residues must be large.