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. 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
5. Bernstein-Sato theory for arbitrary ideals in positive characteristic

   https://doi.org/10.1090/tran/8271  

   Quinlan-Gallego, Eamon (March 2021, Transactions of the American Mathematical Society)

   Mustaţă defined Bernstein-Sato polynomials in prime characteristic for principal ideals and proved that the roots of these polynomials are related to the F F -jumping numbers of the ideal. This approach was later refined by Bitoun. Here we generalize these techniques to develop analogous notions for the case of arbitrary ideals and prove that these have similar connections to F F -jumping numbers. 

   more » « less