For an odd prime p, we say that a polynomial f(X) in F_p[X] computes square roots mod p if for all non-zero perfect squares a, f(a)^2 = a (mod p).
Problem: Construct a low degree polynomial f(X) that compute square roots mod p.
It can be easily shown that f(X) has degree between p/4 and p/2. When p = 3 mod 4, it is well-known that f(X)=X^{(p+1)/4} computes square roots, and the degree is as low as possible.
When p = 1 mod 4, previously no non-trivial lower bound for degree of f(X) were known. In the paper, the authors show that f(X) has degree at least (p-1)/3. The main ingredient in the proof is the following general lemma: powers of low degree polynomial cannot have too many consecutive zero coefficients.
In the other direction, the authors show that for infinitely many p = 1 mod 4, the degree of the polynomial computing square roots can be (1/2-Ω(1))p.
Paper link: https://eccc.weizmann.ac.il/report/2023/177/download
Authors: Kiran Kedlaya, Swastik Kopparty
