More Like this

1. 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
2. A STABILITY VERSION OF THE GAUSS–LUCAS THEOREM AND APPLICATIONS

   https://doi.org/10.1017/S1446788719000284  

   STEINERBERGER, STEFAN (September 2019, Journal of the Australian Mathematical Society)

   Let $$p:\mathbb{C}\rightarrow \mathbb{C}$$ be a polynomial. The Gauss–Lucas theorem states that its critical points, $$p^{\prime }(z)=0$$ , are contained in the convex hull of its roots. We prove a stability version whose simplest form is as follows: suppose that $$p$$ has $n+m$ roots, where $$n$$ are inside the unit disk, $$\begin{eqnarray}\max _{1\leq i\leq n}|a_{i}|\leq 1~\text{and}~m~\text{are outside}~\min _{n+1\leq i\leq n+m}|a_{i}|\geq d>1+\frac{2m}{n};\end{eqnarray}$$ then $$p^{\prime }$$ has $n-1$ roots inside the unit disk and $$m$$ roots at distance at least $(dn-m)/(n+m)>1$ from the origin and the involved constants are sharp. We also discuss a pairing result: in the setting above, for $$n$$ sufficiently large, each of the $$m$$ roots has a critical point at distance $${\sim}n^{-1}$$ . 

   more » « less
3. Computing Higher Polynomial Discriminants

   https://doi.org/10.1145/3452143.3465543  

   Kaltofen, Erich L. (July 2021, ISSAC '21: Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation)

   null (Ed.)

   In https://arxiv.org/abs/1609.00840, D. Wang and J. Yang in 2016 have posed the problem how to compute the ``third'' discriminant of a polynomial f(X) = (X-A_1) ... (X-A_n), delta_3(f) = product_{1 <= i < j < k < l <= n} ( (A_i + A_j - A_k - A_l) (A_i - A_j + A_k - A_l) (A_i - A_j - A_k + A_l) ), from the coefficients of f; note that delta_3 is a symmetric polynomial in the A_i. For complex roots, delta_3(f) = 0 if the mid-point (average) of 2 roots is equal the mid-point of another 2 roots. Iterated resultant computations yield the square of the third discriminant. We apply a symbolic homotopy by Kaltofen and Trager [JSC, vol. 9, nr. 3, pp. 301--320 (1990)] to compute its squareroot. Our algorithm use polynomially many coefficient field operations. 

   more » « less
4. Computing Euler factors of genus 2 curves at odd primes of almost good reduction

   https://doi.org/10.1007/s40993-024-00605-7  

   Maistret, Céline; Sutherland, Andrew V (March 2025, Research in Number Theory)

   Abstract We present an efficient algorithm to compute the Euler factor of a genus 2 curve$$C/\mathbb {Q}$$ $C/Q$ at an odd primepthat is of bad reduction forCbut of good reduction for the Jacobian ofC(a prime of “almost good” reduction). Our approach is based on the theory of cluster pictures introduced by Dokchitser, Dokchitser, Maistret, and Morgan, which allows us to reduce the problem to a short, explicit computation over$$\mathbb {Z}$$ $Z$ and$$\mathbb {F}_p$$ $F_p$ , followed by a point-counting computation on two elliptic curves over$$\mathbb {F}_p$$ $F_p$ , or a single elliptic curve over$$\mathbb {F}_{p^2}$$ $F_{p^2}$ . A key feature of our approach is that we avoid the need to compute a regular model forC. This allows us to efficiently compute many examples that are infeasible to handle using the algorithms currently available in computer algebra systems such as Magma and Pari/GP. 

   more » « less
5. 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