Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
The Degree of Threshold mod 6 and Diophantine Equations

Abstract: We study the degree of polynomials weakly and strongly representing Threshold k (T_k)for general k over Z₆. This problem is motivated by the work of Barrington et al., who showed that over Z₆ the strong degree of the OR function (k=1) is n^1/2 . In this paper, we use the framework establised in [1] by the authors to show that proving bounds on the degree of Threshold functions is equivalent to counting the number of solutions to certain Diophantine equations. Using this equivalence we show nearly tight upper and lower bounds on the strong and weak degree over Z₆ of T_k for all k.

We show a lower bound of Ω (nk)^1/2 on the degree of symmetric polynomials strongly representing T_k, improving the previously best known lower bound of Ω (max(k, n^1/2)) (Tsai, [1]). We show and upper bound of O(nk)^{1/2 + ε} assuming the abc-conjecture. When k is a fixed constant, we show an unconditional bound of O(n)^{1/2 + ε}. The previous best known bounds were O(n)^1/2 for T₁ by Barrington et al. and o(n) for T_c where c is constant in [1]. These results can be generalized to Z_m for arbitrary m. We also show nearly tight lower and upper bounds on the weak degree.

We study the degree of polynomials probabalistically (weakly and strongly) representing threshold mod 6. We show that T_k is represented by polynomials of degree O (max(k, n^1/2)), beating the best deterministic lower bound of Ω (nk)^1/2  for most k.