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. Modules over orders, conjugacy classes of integral matrices, and abelian varieties over finite fields

   https://doi.org/10.1007/s40993-024-00584-9  

   Marseglia, Stefano (March 2025, Research in Number Theory)

   Abstract We give an algorithm to compute representatives of the conjugacy classes of semisimple square integral matrices with given minimal and characteristic polynomials. We also give an algorithm to compute the $$\mathbb {F}_q$$ $F_q$-isomorphism classes of abelian varieties over a finite field $$\mathbb {F}_q$$ $F_q$which belong to an isogeny class determined by a characteristic polynomial hof Frobenius when his ordinary, or qis prime and hhas no real roots. 

   more » « less