Identity testing for radical expressions

We study the Radical Identity Testing problem (RIT): Given an algebraic circuit over integers representing a multivariate polynomial (1, . . . , ) and nonnegative integers 1, . . . , and 1, . . . , , written in binary, test whether the polynomial vanishes at the real radicals √1 1, . . . , √ , i.e., test whether ( √1 1, . . . , √ ) = 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 [16] 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