Identity testing for radical expressions

Conference item

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.

Authors: Balaji, N; Nosan, K; Shirmohammadi, M; Worrell, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Host title: Proceedings of the 37th Annual Symposium on Logic in Computer Science (LICS 2022)
• Journal: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
• Article number: 8
• Publication date: 2022-08-04
• Acceptance date: 2022-05-31
• Event title: 37th Annual Symposium on Logic in Computer Science (LICS 2022)
• Event location: Haifa, Israel
• Event website: https://lics.siglog.org/lics22/
• Event start date: 2022-08-02
• Event end date: 2022-08-05
• DOI: 10.1145/3531130.3533331
• ISBN: 978-1-4503-9351-5
• Language: English
• Keywords: FFR