More Like this

1. 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
2. High-Performance Polynomial Root Finding for Graphics

   https://doi.org/10.1145/3543865  

   Yuksel, Cem (July 2022, Proceedings of the ACM on Computer Graphics and Interactive Techniques)

   We present a computationally-efficient and numerically-robust algorithm for finding real roots of polynomials. It begins with determining the intervals where the given polynomial is monotonic. Then, it performs a robust variant of Newton iterations to find the real root within each interval, providing fast and guaranteed convergence and satisfying the given error bound, as permitted by the numerical precision used. For cubic polynomials, the algorithm is more accurate and faster than both the analytical solution and directly applying Newton iterations. It trivially extends to polynomials with arbitrary degrees, but it is limited to finding the real roots only and has quadratic worst-case complexity in terms of the polynomial's degree. We show that our method outperforms alternative polynomial solutions we tested up to degree 20. We also present an example rendering application with a known efficient numerical solution and show that our method provides faster, more accurate, and more robust solutions by solving polynomials of degree 10. 

   more » « less
3. Misiurewicz polynomials and dynamical units, part II

   https://doi.org/10.1007/s40993-024-00539-0  

   Benedetto, Robert_L; Goksel, Vefa (June 2024, Research in Number Theory)

   Abstract Fix an integer$$d\ge 2$$ $d\ge 2$. The parameters$$c_0\in \overline{\mathbb {Q}}$$ $c_0\in \overline{Q}$for which the unicritical polynomial$$f_{d,c}(z)=z^d+c\in \mathbb {C}[z]$$ $f_{d,c}\left(z\right)=z^d+c\in C\left[z\right]$has finite postcritical orbit, also known asMisiurewiczparameters, play a significant role in complex dynamics. Recent work of Buff, Epstein, and Koch proved the first known cases of a long-standing dynamical conjecture of Milnor using their arithmetic properties, about which relatively little is otherwise known. Continuing our work from a companion paper, we address further arithmetic properties of Misiurewicz parameters, especially the nature of the algebraic integers obtained by evaluating the polynomial defining one such parameter at a different Misiurewicz parameter. In the most challenging such combinations, we describe a connection between such algebraic integers and the multipliers of associated periodic points. As part of our considerations, we also introduce a new class of polynomials we callp-special, which may be of independent number theoretic interest. 

   more » « less
4. Introducing isodynamic points for binary forms and their ratios

   https://doi.org/10.1007/s40627-022-00112-4  

   Hägg, Christian; Shapiro, Boris; Shapiro, Michael (January 2023, Complex Analysis and its Synergies)

   Abstract The isodynamic points of a plane triangle are known to be the only pair of its centers invariant under the action of the Möbius group$${\mathcal {M}}$$ $M$on the set of triangles, Kimberling (Encyclopedia of Triangle Centers,http://faculty.evansville.edu/ck6/encyclopedia). Generalizing this classical result, we introduce below theisodynamicmap associating to a univariate polynomial of degree$$d\ge 3$$ $d\ge 3$with at most double roots a polynomial of degree (at most)$$2d-4$$ $2d-4$such that this map commutes with the action of the Möbius group$${\mathcal {M}}$$ $M$on the zero loci of the initial polynomial and its image. The roots of the image polynomial will be called theisodynamic pointsof the preimage polynomial. Our construction naturally extends from univariate polynomials to binary forms and further to their ratios. 

   more » « less
5. Bivariate Dimension Polynomials of Non-Reflexive Prime Difference-Differential Ideals. The Case of One Translation

   Levin, A. (July 2018, Proceedings of the 43rd International Symposium on Symbolic and Algebraic Computation (ISSAC 2018))

   We use the method of characteristic sets with respect to two term orderings to prove the existence and obtain a method of computation of a bivariate dimension polynomial associated with a non-reflexive difference-differential ideal in the algebra of difference-differential polynomials with several basic derivations and one translation. As a consequence, we obtain a new proof and a method of computation of the dimension polynomial of a non-reflexive prime difference ideal in the algebra of difference polynomials over an ordinary difference field. We also discuss applications of our results to systems of algebraic difference-differential equations. 

   more » « less