Compositions and collisions at degree p^2
From MaRDI portal
Publication:2437328
Abstract: A univariate polynomial f over a field is decomposable if f = g o h = g(h) for nonlinear polynomials g and h. In order to count the decomposables, one wants to know, under a suitable normalization, the number of equal-degree collisions of the form f = g o h = g^* o h^* with (g, h) = (g^*, h^*) and deg g = deg g^*. Such collisions only occur in the wild case, where the field characteristic p divides deg f. Reasonable bounds on the number of decomposables over a finite field are known, but they are less sharp in the wild case, in particular for degree p^2. We provide a classification of all polynomials of degree p^2 with a collision. It yields the exact number of decomposable polynomials of degree p^2 over a finite field of characteristic p. We also present an efficient algorithm that determines whether a given polynomial of degree p^2 has a collision or not.
Recommendations
Cites work
- A Class of Exceptional Polynomials
- Algebraic Function Fields and Codes
- Composite Polynomials with Coefficients in an Arbitrary Field of Characteristic Zero
- Composition collisions and projective polynomials: statement of results
- Compositions and collisions at degree p^2
- Exceptional polynomials and the reducibility of substitution polynomials
- Functional decomposition of polynomials: the tame case
- Functional decomposition of polynomials: the wild case
- scientific article; zbMATH DE number 1703931 (Why is no real title available?)
- scientific article; zbMATH DE number 5831615 (Why is no real title available?)
- scientific article; zbMATH DE number 4202411 (Why is no real title available?)
- scientific article; zbMATH DE number 3918501 (Why is no real title available?)
- scientific article; zbMATH DE number 3765914 (Why is no real title available?)
- scientific article; zbMATH DE number 1222351 (Why is no real title available?)
- scientific article; zbMATH DE number 1273634 (Why is no real title available?)
- scientific article; zbMATH DE number 1313469 (Why is no real title available?)
- scientific article; zbMATH DE number 1467743 (Why is no real title available?)
- scientific article; zbMATH DE number 940594 (Why is no real title available?)
- scientific article; zbMATH DE number 3201718 (Why is no real title available?)
- Lower bounds for decomposable univariate wild polynomials
- Modern computer algebra
- On \(x^{q+1}+ax+b\)
- On decomposition of sub-linearised-polynomials
- On the invariance of chains of fields
- On the values of the divisor function
- Polynomial decomposition algorithms
- Polynomial decomposition algorithms
- Polynomial Substitutions
- Prime and composite polynomials
- Ritt's Second Theorem in arbitrary characteristic.
- Solvability by radicals is in polynomial time
- The Equation f(X) = f(Y) in Rational Functions X = X(t), Y = Y(t)
- The number of decomposable univariate polynomials
- The zeros of Dirichlet \(L\)-functions and the least prime in arithmetic progression
- Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
Cited in
(8)- Normal form for Ritt's second theorem
- Counting decomposable polynomials with integer coefficients
- Composition collisions and projective polynomials: statement of results
- Compositions and collisions at degree p^2
- Counting decomposable univariate polynomials
- Tame decompositions and collisions
- Tame decompositions and collisions
- Interpolation by decomposable univariate polynomials
This page was built for publication: Compositions and collisions at degree \(p^2\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437328)
