Towards Randomized Testing of \(q\)-Monomials in Multivariate Polynomials

Abstract

Given any fixed integer \(q\ge 2\), a \(q\)-monomial is of the format \(\displaystyle x^{s_1}_{i_1}x^{s_2}_{i_2}...x_{i_t}^{s_t}\) such that \(1\le s_j \le q-1\), \(1\le j \le t\). \(q\)-monomials are natural generalizations of multilinear monomials. Recent research on testing multilinear monomials and \(q\)-monomails for prime \(q\) in multivariate polynomials relies on the property that \(Z_q\) is a field when \(q\ge 2 \) is prime. When \(q>2\) is not prime, it remains open whether the problem of testing \(q\)-monomials can be solved in some compatible complexity. In this paper, we present a randomized \(O^*(7.15^k)\) algorithm for testing \(q\)-monomials of degree \(k\) that are found in a multivariate polynomial that is represented by a tree-like circuit with a polynomial size, thus giving a positive, affirming answer to the above question. Our algorithm works regardless of the primality of \(q\) and improves upon the time complexity of the previously known algorithm for testing \(q\)-monomials for prime \(q>7\).