论文标题
激进表达的身份测试
Identity Testing for Radical Expressions
论文作者
论文摘要
我们研究了激进的身份测试问题（RIT）：给定代数代表多项式$ f \ in \ mathbb {z} [x_1，\ ldots，x_k] $和非阴性整数$ a_1，\ ldots，\ ldots，a_k $ and $ d_1，$ ddots，$ ddots，$ ddots，$ ldots，$ ldots，$ ldots，$ ldots，$ ldots，$ ldots，在真实的激进分子$ \ sqrt [d_1] {a_1}，\ ldots，\ sqrt [d_k] {a_k} $，即测试$ f（\ sqrt [d_1] {a_1}假设普遍的Riemann假设（GRH），我们将问题置于综合中，从而改善了通过还原为真实的存在理论获得的直接Pspace上限。接下来，我们考虑一个限制版本，称为$ 2 $ rit，其中激进的是用二进制编写的质数的正方形。自Chen和Kao的工作以来，人们已经知道$ 2 $ rit至少与多项式身份测试问题一样困难，但是在我们工作之前已经知道了比PSPACE更好的上限。我们表明，假设GRH并无条件地统一，$ 2 $ rit在Corp中。我们的证明依赖于代数和分析数理论的定理，例如Chebotarev密度定理和二次互惠。
We study the Radical Identity Testing problem (RIT): Given an algebraic circuit representing a polynomial $f\in \mathbb{Z}[x_1, \ldots, x_k]$ and nonnegative integers $a_1, \ldots, a_k$ and $d_1, \ldots,$ $d_k$, written in binary, test whether the polynomial vanishes at the real radicals $\sqrt[d_1]{a_1}, \ldots,\sqrt[d_k]{a_k}$, i.e., test whether $f(\sqrt[d_1]{a_1}, \ldots,\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 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.
