Identity Testing for Radical Expressions

We study the Radical Identity Testing problem (RIT): Given an algebraic circuit representing a multivariate polynomial $f(x_1, \dots, x_k)$ and nonnegative integers $a_1, \dots, a_k$ and $d_1, \dots, $ $d_k$, written in binary, test whether the polynomial vanishes at the \emph{real radicals} $\sqrt[d_1]{a_1}, \dots, \sqrt[d_k]{a_k}$, i. e. , test whether $f(\sqrt[d_1]{a_1}, \dots, \sqrt[d_k]{a_k}) = 0$. We place the problem in {\coNP} assuming the Generalised Riemann Hypothesis (GRH), improving on the straightforward {\PSPACE} upper bound obtained by reduction to the existential theory of reals. Next we consider a restricted version, called $2$-RIT, where the radicals are square roots of prime numbers, written in binary. It was known since the work of Chen and Kao~\cite{chen-kao} that $2$-RIT is at least as hard as the polynomial identity testing problem, however no better upper bound than {\PSPACE} was known prior to our work. We show that $2$-RIT is in {\coRP} assuming GRH and in {\coNP} unconditionally. Our proof relies on theorems from algebraic and analytic number theory, such as the Chebotarev density theorem and quadratic reciprocity. This is a joint work with Klara Nosan, Mahsa Shirmohammadi and James Worrell and is currently under submission. A full version can be found here - https: //arxiv. org/abs/2202. 07961

Authors

• Nikhil Balaji

Keywords

No keywords are indexed for this paper.