More Like this

1. On the Degree of Polynomials Computing Square Roots Mod p

   https://doi.org/10.4230/LIPIcs.CCC.2024.25  

   Kedlaya, Kiran S; Kopparty, Swastik (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   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. 

   more » « less
2. Counting Real Roots in Polynomial-Time via Diophantine Approximation

   https://doi.org/10.1007/s10208-022-09599-z  

   Rojas, J. Maurice (November 2022, Foundations of Computational Mathematics)

   Peter Burgisser (Ed.)

   Suppose A = {a 1 , . . . , a n+2 } ⊂ Z n has cardinality n + 2, with all the coordinates of the a j having absolute value at most d, and the a j do not all lie in the same affine hyperplane. Suppose F = ( f 1 , . . . , f n ) is an n × n polynomial system with generic integer coefficients at most H in absolute value, and A the union of the sets of exponent vectors of the f i . We give the first algorithm that, for any fixed n, counts exactly the number of real roots of F in time polynomial in log(dH ). We also discuss a number- theoretic hypothesis that would imply a further speed-up to time polynomial in n as well. 

   more » « less
3. A Faster Solution to Smale's 17th Problem I: Real Binomial Systems

   https://doi.org/10.1145/3326229.3326267  

   Paouris, Grigoris; Phillipson, Kaitlyn; Rojas, J. Maurice (July 2019, ISSAC (International Symposium on Symbolic and Algebraic Computation) 2019)

   Suppose $$F:=(f_1,\ldots,f_n)$$ is a system of random $$n$$-variate polynomials with $$f_i$$ having degree $$\leq\!d_i$$ and the coefficient of $$x^{a_1}_1\cdots x^{a_n}_n$$ in $$f_i$$ being an independent complex Gaussian of mean $$0$$ and variance $$\frac{d_i!}{a_1!\cdots a_n!\left(d_i-\sum^n_{j=1}a_j \right)!}$$. Recent progress on Smale's 17$$\thth$$ Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, B\"{u}rgisser, and Cucker --- has resulted in a deterministic algorithm that finds a single (complex) approximate root of $$F$$ using just $$N^{O(1)}$$ arithmetic operations on average, where $$N\!:=\!\sum^n_{i=1}\frac{(n+d_i)!}{n!d_i!}$$ ($$=n(n+\max_i d_i)^{O(\min\{n,\max_i d_i)\}}$$) is the maximum possible total number of monomial terms for such an $$F$$. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when $$F$$ is instead a binomial system --- a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just $$O(n^3\log^2(n\max_i d_i))$$ arithmetic operations on average. Furthermore, our approach allows Gaussians with arbitrary variance. We also discuss briefly the obstructions to maintaining average-case time polynomial in $$n\log \max_i d_i$$ when $$F$$ has more terms. 

   more » « less
4. Counting Roots of Polynomials over Z/p2Z

   Hammonds, Trajan; Johnson, Jeremy; Patini, Angela; Walker, Robert M. (January 2018, Houston journal of mathematics)

   Until recently, the only known method of finding the roots of polynomials over prime power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm, obstructing the use of greatest common divisors. Fix a prime integer p and f in (Z/pnZ)[x] any nonzero polynomial of degree d whose coefficients are not all divisible by p. For the case n=2, we prove a new efficient algorithm to count the roots of f in Z/p2Z within time (d+size(f)+log p),2+o(1), based on a formula conjectured by Cheng, Gao, Rojas, and Wan. 

   more » « less
5. Reduction of dynatomic curves

   https://doi.org/10.1017/etds.2017.140  

   DOYLE, JOHN R.; KRIEGER, HOLLY; OBUS, ANDREW; PRIES, RACHEL; RUBINSTEIN-SALZEDO, SIMON; WEST, LLOYD (October 2019, Ergodic Theory and Dynamical Systems)

   null (Ed.)

   In this paper, we make partial progress on a function field version of the dynamical uniform boundedness conjecture for certain one-dimensional families $${\mathcal{F}}$$ of polynomial maps, such as the family $$f_{c}(x)=x^{m}+c$$ , where $$m\geq 2$$ . We do this by making use of the dynatomic modular curves $$Y_{1}(n)$$ (respectively $$Y_{0}(n)$$ ) which parametrize maps $$f$$ in $${\mathcal{F}}$$ together with a point (respectively orbit) of period $$n$$ for $$f$$ . The key point in our strategy is to study the set of primes $$p$$ for which the reduction of $$Y_{1}(n)$$ modulo $$p$$ fails to be smooth or irreducible. Morton gave an algorithm to construct, for each $$n$$ , a discriminant $$D_{n}$$ whose list of prime factors contains all the primes of bad reduction for $$Y_{1}(n)$$ . In this paper, we refine and strengthen Morton’s results. Specifically, we exhibit two criteria on a prime $$p$$ dividing $$D_{n}$$ : one guarantees that $$p$$ is in fact a prime of bad reduction for $$Y_{1}(n)$$ , yet this same criterion implies that $$Y_{0}(n)$$ is geometrically irreducible. The other guarantees that the reduction of $$Y_{1}(n)$$ modulo $$p$$ is actually smooth. As an application of the second criterion, we extend results of Morton, Flynn, Poonen, Schaefer, and Stoll by giving new examples of good reduction of $$Y_{1}(n)$$ for several primes dividing $$D_{n}$$ when $n=7,8,11$ , and $$f_{c}(x)=x^{2}+c$$ . The proofs involve a blend of arithmetic and complex dynamics, reduction theory for curves, ramification theory, and the combinatorics of the Mandelbrot set. 

   more » « less