Search for: All records

Abstract We describe an algorithm for computing, for all primes$$p \le X$$ $p\le X$, the trace of Frobenius atpof a hypergeometric motive over$$\mathbb {Q}$$ $Q$in time quasilinear inX. This involves computing the trace modulo$$p^e$$ $p^e$for suitablee; as in our previous work treating the case$$e=1$$ $e=1$, we combine the Beukers–Cohen–Mellit trace formula with average polynomial time techniques of Harvey and Harvey–Sutherland. The key new ingredient for$$e>1$$ $e>1$is an expanded version of Harvey’s “generic prime” construction, making it possible to incorporate certainp-adic transcendental functions into the computation; one of these is thep-adic Gamma function, whose average polynomial time computation is an intermediate step which may be of independent interest. We also provide an implementation in Sage and discuss the remaining computational issues around tabulating hypergeometricL-series. 

For an odd prime p, we say f(X) ∈ F_p[X] computes square roots in F_p if, for all nonzero perfect squares a ∈ F_p, we have f(a)² = a. When p ≡ 3 mod 4, it is well known that f(X) = X^{(p+1)/4} computes square roots. This degree is surprisingly low (and in fact lowest possible), since we have specified (p-1)/2 evaluations (up to sign) of the polynomial f(X). On the other hand, for p ≡ 1 mod 4 there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in F_p. We show that for all p ≡ 1 mod 4, the degree of a polynomial computing square roots has degree at least p/3. Our main new ingredient is a general lemma which may be of independent interest: powers of a low degree polynomial cannot have too many consecutive zero coefficients. The proof method also yields a robust version: any polynomial that computes square roots for 99% of the squares also has degree almost p/3. In the other direction, Agou, Deliglése, and Nicolas [Agou et al., 2003] showed that for infinitely many p ≡ 1 mod 4, the degree of a polynomial computing square roots can be as small as 3p/8.