Reproduce “On the degree of polynomials computing square roots mod p” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Kiran Kedlaya, Swastik Kopparty
Steven B. Giddings, Kiran Kedlaya, and Swastik Kopparty establish the first nontrivial lower bound for the degree of polynomials computing square roots modulo prime $p$ when $p \equiv 1 \pmod 4$, showing it must be at least $(p-1)/3$. This work also introduces a robust version stable against errors and explores connections to Reed-Solomon list-recovery.
Key insights
- The problem of polynomial representation for square roots exhibits a fundamental distinction between $p \equiv 3 \pmod 4$ (where the degree is low) and $p \equiv 1 \pmod 4$ (where it requires a significantly higher degree).
- A general algebraic lemma states that the $t$-th power of a low-degree polynomial cannot have too many consecutive zero coefficients, providing a versatile tool for lower bounds.
- The problem serves as a challenging instance for Reed-Solomon list-recovery, contributing to understanding the limits of list-recoverability for specific parameter settings.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.