Tame decompositions and collisions

DOI10.1145/2608628.2608653MaRDI QIDQ5899518zbMATH OpenOpenAlexFDO

Authors Konstantin Ziegler

Publication date 11 November 2015

Published in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.5945

zbMATH Keywords

combinatorics on polynomials over finite fieldsRitt's second theoremunivariate polynomial decomposition

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Polynomials in general fields (irreducibility, etc.) (12E05)

Abstract: A univariate polynomial f over a field is decomposable if f = g o h = g(h) for nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials over a finite field. The tame case, where the characteristic p of Fq does not divide n = deg f, is fairly well-understood, and we have reasonable bounds on the number of decomposables of degree n. Nevertheless, no exact formula is known if $n$ has more than two prime factors. In order to count the decomposables, one wants to know, under a suitable normalization, the number of collisions, where essentially different (g, h) yield the same f. In the tame case, Ritt's Second Theorem classifies all 2-collisions. We introduce a normal form for multi-collisions of decompositions of arbitrary length with exact description of the (non)uniqueness of the parameters. We obtain an efficiently computable formula for the exact number of such collisions at degree n over a finite field of characteristic coprime to p. This leads to an algorithm for the exact number of decomposable polynomials at degree n over a finite field Fq in the tame case.

Recommendations

• Tame decompositions and collisions
• Compositions and collisions at degree p^2
• Compositions and collisions at degree \(p^2\)
• Survey on counting special types of polynomials
• Counting decomposable univariate polynomials

Cites work

• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• Definability and decision problems in arithmetic
• scientific article; zbMATH DE number 1952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• The Jordan Curve Theorem, Formally and Informally

Cited in

(10)

• Counting invariant subspaces and decompositions of additive polynomials
• Normal form for Ritt's second theorem
• Compositions and collisions at degree \(p^2\)
• Survey on counting special types of polynomials
• The number of decomposable univariate polynomials
• Composition collisions and projective polynomials: statement of results
• On decomposition of sub-linearised-polynomials
• Compositions and collisions at degree p^2
• Counting decomposable univariate polynomials
• Tame decompositions and collisions

Describes a project that uses

Uses Software

• Jordan

This page was built for publication: Tame decompositions and collisions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899518)