Tame Decompositions and Collisions

arXiv:1402.5945v1 [math.AC] 24 Feb 2014

Konstantin Ziegler
B-IT, Universität Bonn
D-53113 Bonn, Germany
zieglerk@bit.uni-bonn.de
http://cosec.bit.uni-bonn.de/
April 10, 2018
Abstract
A univariate polynomial f over a field is decomposable if f =
g ◦ 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.

1

Introduction

The composition of two univariate polynomials g, h ∈ F [x] over a field F
is denoted as f = g ◦ h = g(h), and then (g, h) is a decomposition of f ,
and f is decomposable if g and h have degree at least 2. In the 1920s, Ritt,
1

Fatou, and Julia studied structural properties of these decompositions over
C, using analytic methods. Particularly important are two theorems by Ritt
on the uniqueness, in a suitable sense, of decompositions, the first one for
(many) indecomposable components and the second one for two components,
as above. Engstrom (1941) and Levi (1942) proved them over arbitrary fields
of characteristic zero using algebraic methods.
The theory was extended to arbitrary characteristic by Fried & MacRae
(1969), Dorey & Whaples (1974), Schinzel (1982, 2000), Zannier (1993), and
others. Its use in a cryptographic context was suggested by Cade (1985).
In computer algebra, the decomposition method of Barton & Zippel (1985)
requires exponential time. A fundamental dichotomy is between the tame
case, where the characteristic p does not divide deg g, and the wild case,
where p divides deg g, see von zur Gathen (1990a,b). A breakthrough result
of Kozen & Landau (1989) was their polynomial-time algorithm to compute
tame decompositions; see also von zur Gathen, Kozen & Landau (1987);
Kozen, Landau & Zippel (1996); Gutierrez & Sevilla (2006), and the survey
articles of von zur Gathen (2002) and Gutierrez & Kozen (2003) with further
references.
Schur’s conjecture, as proven by Turnwald (1995), offers a natural connection between indecomposable polynomials with degree coprime to p and
certain absolutely irreducible bivariate polynomials. On a different, but related topic, Avanzi & Zannier (2003) study ambiguities in the decomposition
of rational functions over C.
It is intuitively clear that the univariate decomposable polynomials form
only a small minority among all univariate polynomials over a field. A
set of distinct decompositions of f is called a collision. The number of
decomposable polynomials of degree n is thus the number of all pairs (g, h)
with deg g · deg h = n reduced by the ambiguities introduced by collisions.
An important tool for estimating the number of collisions is Ritt’s Second
Theorem. Ritt worked with F = C and used analytic methods. Subsequently,
his approach was replaced by algebraic methods and Ritt’s Second Theorem
was also shown to hold in positive characteristic p. The original versions of
this required p > deg(g ◦ h). Zannier (1993) reduced this to the milder and
more natural requirement g 0 6= 0 for all g in the collision. His proof works
over an algebraic closed field, and Schinzel’s (2000) monograph adapts it to
finite fields.
The task of counting compositions over a finite field of characteristic p
was first considered in Giesbrecht (1988). Von zur Gathen (2014a) presents
general approximations to the number of decomposable polynomials. These
come with satisfactory (rapidly decreasing) relative error bounds except when
p divides n = deg f exactly twice. Blankertz, von zur Gathen & Ziegler (2013)
2

determine exactly the number of decomposable polynomials in one of these
difficult cases, namely when n = p2 .
Zannier (2008) studies a different but related question, namely compositions f = g ◦ h in C[x] with a sparse polynomial f , having t terms. The
degree is not bounded. He gives bounds, depending only on t, on the degree
of g and the number of terms in h. Furthermore, he gives a parametrization
of all such f , g, h in terms of varieties (for the coefficients) and lattices (for
the exponents). Bodin, Dèbes & Najib (2009) also deal with counting.
Zieve & Müller (2008) derive an efficient method for describing all complete
decompositions of a polynomial, where all components are indecomposable.
This turns Ritt’s First Theorem into an applicable form and Medvedev &
Scanlon (2014) combine this approach with results from model theory to
describe the subvarieties of the k-dimensional affine space that are preserved
by a coordinatewise polynomial map. Both works lead to slightly different
canonical forms for the complete decomposition of a given polynomial. Zieve
& Müller (2008) employ Ritt moves, where adjacent indecomposable g, h in a
complete decomposition are replaced by g ∗ , h∗ with the same composition,
but deg g = deg h∗ 6= deg h = deg g ∗ . Such collisions are the theme of Ritt’s
Second Theorem and von zur Gathen (2014b) presents a normal form with
an exact description of the (non)uniqueness of the parameters.
Our work combines the “normalizations” of Ritt’s theorems by Zieve &
Müller (2008) and von zur Gathen (2014b) to classify collisions of two or
more decompositions, not necessarily complete and of arbitrary length. We
make the following contributions.
• We obtain a normal form for collisions described by a set of degree
sequences for (possibly incomplete) decompositions. (Theorem 3.14 and
Theorem 3.15)
• The (non)uniqueness of the parameters leads to an exact formula for the
number of such collisions over a finite field with characteristic coprime
their degree. (Theorem 4.1)
• We conclude with an efficient algorithm for the number of decomposable
polynomials at degree n over a finite field of characteristic coprime n.
(Algorithm 4.2)
The latter extends the explicit formulae of von zur Gathen (2014a) for n a
semiprime or the cube of a prime.
We proceed in three steps. In Section 2, we introduce notation and
establish basic relations. In Section 3, we introduce the relation graph of a set
of collisions which captures the necessary order and possible Ritt moves for
3

any in decomposition. This leads to a complete classification of collisions by
Theorem 3.14 and Theorem 3.15. We conclude with the corresponding formula
for the number of such collisions over a finite field and the corresponding
procedure in Section 4.

2

Notation and Preliminaries

A nonzero polynomial f ∈ F [x] over a field F of characteristic p ≥ 0 is monic
if its leading coefficient lc(f ) equals 1. We call f original if its graph contains
the origin, that is, f (0) = 0. For g, h ∈ F [x],
f = g ◦ h = g(h) ∈ F [x]

(2.1)

is their composition. If deg g, deg h ≥ 2, then (g, h) is a decomposition of f .
A polynomial f ∈ F [x] is decomposable if there exist such g and h, otherwise
f is indecomposable. A decomposition (2.1) is tame if p - deg g, and f is tame
if p - deg f .
Multiplication by a unit or addition of a constant does not change decomposability, since
f = g ◦ h ⇐⇒ af + b = (ag + b) ◦ h
for all f , g, h as above and a, b ∈ F with a 6= 0. In other words, the set of
decomposable polynomials is invariant under this action of F × × F on F [x].
Furthermore, any decomposition (g, h) can be normalized by this action, by
taking a = lc(h)−1 ∈ F × , b = −a · h(0) ∈ F , g ∗ = g((x − b)a−1 ) ∈ F [x], and
h∗ = ah + b. Then g ◦ h = g ∗ ◦ h∗ and g ∗ and h∗ are monic original.
It is therefore sufficent to consider compositions f = g ◦ h where all three
polynomials are monic original. For n ≥ 1 and any positive divisor d of n, we
write
Pn (F ) = {f ∈ F [x] : f is monic original of degree n},
Dn (F ) = {f ∈ Pn : f is decomposable},
Dn,d (F ) = {f ∈ Pn : f = g ◦ h for some (g, h) ∈ Pd × Pn/d }.
We sometimes leave out F from the notation when it is clear from the context
and have over a finite field Fq with q elements,
#Pn = q n−1 .

(2.1a)

It is well known that in a tame decomposition, g and h are uniquely determined
and we have over Fq
#Dn,d = q n+n/d−2
(2.2)
4

if n is coprime to p.
The set Dn of all decomposable polynomials in Pn satisfies
Dn =

[

Dn,d .

(2.3)

d|n
1<d<n

In particular, Dn = ∅ if n is prime. Our collisions turn up in the resulting
inclusion-exclusion formula for #Dn if n is composite.
Let N = {1 < d < n : d | n} be the set of nontrivial divisors of n and
D ⊆ N a nonempty subset of size k. This defines a set
Dn,D =

\

Dn,d

d∈D

of k-collisions. We obtain from (2.3) the inclusion-exclusion formula
#Dn =

X

(−1)k+1

X

#Dn,D .

(2.4)

D⊆N
#D=k

k≥1

For #D = 1, the size of Dn,D is given in (2.2). For #D = 2, the central
tool for understanding is Ritt’s Second Theorem as presented in the next
subsection.
For f ∈ Pn (F ) and a ∈ F , the original shift of f by a is
f [a] = (x − f (a)) ◦ f ◦ (x + a) ∈ Pn (F ).

(2.5)

Original shifting defines a group action of the additive group of F on Pn (F ).
Shifting respects decompositions in the sense that for each decomposition
(g, h) of f we have a decomposition (g [h(a)] , h[a] ) of f [a] , and vice versa. We
denote (g [h(a)] , h[a] ) as (g, h)[a] . The stabilizer of a monic original polynomial
f under original shifting is F if f is linear and {0} otherwise.

2.1

Normal Form for Ritt’s Second Theorem

In the 1920s, Ritt, Fatou, and Julia investigated the composition f = g ◦ h =
g(h) of univariate polynomials over a field F for F = C. It emerged as an
important question to determine the collisions (or nonuniqueness) of such
decompositions, that is, different components (g, h) 6= (g ∗ , h∗ ) with equal
composition g ◦ h = g ∗ ◦ h∗ and equal sets of degrees: deg g = deg h∗ 6=
deg h = deg g ∗ .
Ritt (1922) presented two types of essential collisions:
xe ◦ xk w(xe ) = xke we (xe ) = xk we ◦ xe ,
5

(2.6)

∗
Td∗ (x, z e ) ◦ Te∗ (x, z) = Ted
(x, z) = Te∗ (x, z d ) ◦ Td∗ (x, z),

(2.7)

where w ∈ F [x], z ∈ F × = F \ {0}, and Td∗ is the dth Dickson polynomial
of the first kind. And then he proved that these are all possibilities up to
composition with linear polynomials. This involved four unspecified linear
functions, and it is not clear whether there is a relation between the first and
the second type of example. Without loss of generality, we use the originalized
dth Dickson polynomial Td (x, z) = Td∗ (x, z) − Td∗ (0, z) which also satisfy (2.7).
Von zur Gathen (2014b) presents a normal form for the decompositions
6 0 and the standard
in Ritt’s Theorem under Zannier’s assumption g 0 (g ∗ )0 =
assumption gcd(e, d) = 1, where d = k + e deg w in (2.6). This normal form
is unique unless p | m.
Theorem 2.8. (Ritt’s Second Theorem, Normal Form, tame case) Let d >
e ≥ 2 be coprime integers, and n = de coprime to the characteristic of F .
Furthermore, let f = g ◦ h = g ∗ ◦ h∗ be monic original polynomials with
deg g = deg h∗ = d, deg h = deg g ∗ = e.
Then either (i) or (ii) holds, and (iii) is also valid.
(i) (Exponential Case) There exists a monic polynomial w ∈ F [x] of degree
s and a ∈ F so that
f = (xke we (xe ))[a]
where d = se+k is the division with remainder of d by e, with 1 ≤ k < e.
Furthermore
(g ∗ , h∗ ) = (xe , xk w(xe ))[a] ,

(g, h) = (xk we , xe )[a] ,

and (w, a) is uniquely determined by f and d. Conversely, any (w, a)
as above yields a 2-collision via the above formulas.
(ii) (Trigonometric Case) There exist z, a ∈ F with z 6= 0 so that
f = Tn (x, z)[a] .
Furthermore we have
(g, h) = (Td (x, z e ), Te (x, z))[a] ,

(g ∗ , h∗ ) = (Te (x, z d ), Td (x, z))[a] ,

and (z, a) is uniquely determined by f . Conversely, any (z, a) as above
yields a 2-collision via the above formulas.
(iii) For e = 2, the Trigonometric Case is included in the Exponential Case.
For e ≥ 3, the Exponential and Trigonometric Cases are mutually
exclusive.
6

If p - n, then the case where gcd(d, e) 6= 1 is reduced to the previous one
by the following result about the left and right greatest common divisors
of decompositions. It was shown over algebraically closed fields by Tortrat
(1988, Proposition 1); a more concise proof using Galois theory is due to Zieve
& Müller (2008, Lemma 2.8). We use the version of von zur Gathen (2014b,
Fact 6.1(i)), adapted to monic original polynomials.
Proposition 2.9. Let d, e, d∗ , e∗ ≥ 2 be integers and de = d∗ e∗ coprime to p.
Furthermore, let g ◦ h = g ∗ ◦ h∗ be monic original polynomials with deg g = d,
deg h = e, deg g ∗ = d∗ , deg h∗ = e∗ , and ` = gcd(d, d∗ ), r = gcd(e, e∗ ).
Then there are unique monic original polynomials a and b of degree ` and r,
respectively, such that
g = a ◦ u,
g ∗ = a ◦ u∗ ,

h = v ◦ b,
h∗ = v ∗ ◦ b,

for unique monic original polynomials u, u∗ , v, v ∗ of degree d/`, d∗ /`, e/r,
and e∗ /r, respectively.
This determines Dn,{d,e} exactly if p - n = de.
For coprime integers d ≥ 2 and e ≥ 1, we define the sets

Ed,e =



P

 d

k





for e = 1,
e

{x w ∈ Pd : d = s · e + k with 1 ≤ k < e
(2.10)
and w ∈ Fq [x] monic of degree s},
otherwise,

Td,e = {Td (x, z e ) ∈ Pd : z ∈ F×
q }
of exponential and trigonometric components, respectively. For d < e, we
have s = 0, k = d in (2.10), and therefore
Ed,e = {xd }.

(2.10a)

This allows the following reformulation of Theorem 2.8.
Corollary 2.11. Let f ∈ Dn,{d,e} . Then either (i) or (ii) holds and (iii) is
also valid.
(i) There is a unique monic original g ∈ Ed,e and a unique a ∈ F such that
f = (g ◦ xe )[a] .

7

(ii) There is a unique monic original g ∈ Tde,1 and a unique a ∈ F such
that
f = g [a] .
(iii) If e = 2, then case (ii) is included in case (i). If e ≥ 3, they are
mutually exclusive.
Conversely, we have
[F ]

Dn,{d,e} = (Ed,e ◦ Ee,d )[F ] ∪ Tde,1 ,
where the union is disjoint if and only if e ≥ 3, and
#Dn,{d,e} = q · (q bd/ec + (1 − δe,2 )(q − 1)).
With respect to the size under original shifting, we have the following
consequences.
Proposition 2.14. For F = Fq , coprime d ≥ 2 and e ≥ 1, both coprime to
p, we have
[F ]
#Td,eq

[F ]
#Ed,eq

(

=

=

q
q(q − 1)/ gcd(q − 1, e)

 d−1

q


for d = 2,
otherwise,
for e = 1,

bd/2c+1

− q(q − 1)/2 for e = 2,



 bd/ec+1
q

otherwise.

q

Proof. (i) For d = 2, we have T2,e = {x2 } independent from e. Since
p 6= 2, the original shifts (x2 )[a] = x2 + 2ax range over all monic original
[F ]
polynomials of degree 2 as a runs over all field elements. Thus T2,e = P2
and the size follows from (2.1a).
For d > 2, the coefficient of xd−2 in Td (x, z e ) ∈ Td,e is −dz e . Since there
are exactly (q − 1)/ gcd(q − 1, e) distinct eth powers z e for nonzero
elements z ∈ Fq , this shows
#Td,e = (q − 1)/ gcd(q − 1, e).
For the claimed formula it is sufficient to show that for T ∈ Td,e and
a ∈ F , we have
T [a] ∈ Td,e if and only if a = 0.

8

For d odd, we also have T an odd polynomial. Hence the coefficient of
xd−1 in T is 0 and the coefficient of xd−1 in T [a] is ad. This proves the
claim. For d even, the same argument applies with “odd” replaced by
“even”.
For a nonzero polynomial f ∈ F [x] and b in some algebraic closure K of F ,
let multb (f ) denote the root multiplicity of b in f , so that f = (x − b)multb (f ) u
with u ∈ K[x] and u(b) 6= 0.
[F ]

(ii) For e = 1, we have Ed,e = Pd = Pd

of size q d−1 by (2.1a).

For e > 1, we have #Ed,e = q bd/ec . It is sufficient to show that for
f ∈ Ed,e and a ∈ F , we have
f [a] ∈ Ed,e if and only if a = 0.
We have directly f [0] = f ∈ Ed,e . Conversely, let f [a] = f¯ = xk w̄e ∈ Ed,e ,
and compare the derivatives
0

f [a] = (x + a)k−1 w(x + a)e−1 (kw(x + a) + e(x + a)w0 (x + a)),
f¯0 = xk−1 w̄e−1 (k w̄ + exw̄0 ),
respectively. These are nonzero, since p - d = deg(f¯) = deg(f [a] ), and
we compute the root multiplicity of 0 as
mult0 (f

[a] 0

(

) = [a = 0] · (k − 1) + multa (w) · (e − 1) +

multa (w)
if p | multa (w),
multa (w) − [a 6= 0] otherwise.

= e multa (w) + [a = 0](k − 1) − [p - multa (w) and a 6= 0],
mult0 (f¯0 ) = k − 1 + (e − 1) · mult0 (w̄) + mult0 (w̄)
= e mult0 (w̄) + k − 1.
If f [a] = f¯, we find modulo e
k − 1 = [a = 0] · (k − 1) − [p - multa (w) and a 6= 0].
This holds if
• a = 0 or
• p | multa (w) and k = 1.

9

It remains to show that the latter case is included in the former. In other
words, that p | multa (w) and k = 1 imply a = 0. Let ∆ = w(x + a) − w̄
of degree less than s, since both are monic. Then
0
0 = f [a] − f¯0 = w(x + a)e − w̄e + e((x + a)w0 (x + a) − xw̄0 )

!

e 2 e−2
= e∆w̄
+
∆ w̄
+ ...
2
+ (e − 1)xw̄0 + ex∆0 + eaw̄0 + ea∆0
e−1

If ∆ = 0, we are done. Otherwise, deg ∆ ≥ 0 and the coefficient of
xdeg ∆+s(e−1) is
e lc(∆) + s(e − 1)[e = 2 and deg ∆ = 0].
If e > 2, this is nonzero, a contradiction.
We have w(x + a) = w̄. Feeding this and k = 1 back into the definition
of f [a] and f¯, we obtain for their difference
f [a] − f¯ = (x + a)w̄e − f (a) − xw̄e = aw̄e − f (a).
With deg(w) = s > 0 this implies a = 0.

3

Normal Form for Collisions

The results of the previous section suffice to describe 2-collisions of decompositions g ◦ h = g ∗ ◦ h∗ with length 2 each. This section describes the
structure of “many”-collisions of decompositions with arbitrary, possibly pairwise distinct, lengths. Let d = (d1 , d2 , . . . , d` ) be an ordered factorization of
n = d1 · d2 · . . . · d` with ` nontrivial divisors di ∈ N , 1 ≤ i ≤ `, and define
the set
Dn,d = {f ∈ Pn : f = g1 ◦ · · · ◦ g` with deg gi = di for all 1 ≤ i ≤ `}
of decomposable polynomials with decompositions of length ` and degree
sequence d. For a set D = {d(1) , d(2) , . . . , d(c) } of c ordered factorizations of n,
we define
Dn,D =

\

Dn,d

d∈D

10

(k)

(k)

(k)

= {f ∈ Pn : f = g1 ◦ · · · ◦ g`k with deg gi

(k)

= di

for all 1 ≤ k ≤ c and 1 ≤ i ≤ `k }.
For #D = 1, we have
Dn,D = Dn,d = Pd1 ◦ Pd2 ◦ · · · ◦ Pd` ,
#Dn,D = #Dn,d = q

P
1≤i≤`

di −`

,

where D = {d} and d = (d1 , d2 , . . . , d` ). The rest of this section deals with
#D > 1.
We determine the structure of Dn,D . First, we replace D by a refinement D∗ ,
where all elements are suitable permutations of the same ordered factorization
of n. Second, we define the relation graph of D∗ that captures the degree
sequences for polynomials in Dn,D . Finally, we classify the elements of Dn,D
as a composition of unique trigonometric or unique exponential components
as defined in (2.10).

3.1

A refinement of D

Let d = (d1 , d2 ) and e = (e1 , e2 ) be distinct ordered factorizations of n.
Let ` = gcd(d1 , e1 ), d∗1 = d1 /`, e∗1 = e1 /`, r = gcd(d2 , e2 ), d∗2 = d2 /r, and
e∗2 = e2 /r. Then Proposition 2.9 shows
Dn,{d,e} = Dn,{d∗ ,e∗ }
for d∗ = (`, d∗1 , d∗2 , r) and e∗ = (`, e∗1 , e∗2 , r) with gcd(d∗1 , e∗1 ) = 1 = gcd(d∗2 , e∗2 )
and therefore d∗1 = e∗2 and d∗2 = e∗1 . We generalize this procedure to two
ordered factorizations of arbitrary length. For squarefree n this is similar to
the computation of a coprime (also: gcd-free) basis for {d1 , d2 , e1 , e2 }, if we
keep duplicates and the order of factors; see Bach & Shallit (1997, Section 4.8).
For squareful n, the factors with gcd > 1 require additional attention.
Let d = (d1 , d2 , . . . , d` ) be an ordered factorization of n and call the underlying unordered multiset d = {d1 , d2 , . . . , d` } of divisors its basis. A refinement of
d is an ordered factorization d∗ = (d∗11 , . . . , d∗1m1 , d∗21 , . . . , d∗2m2 , . . . , d∗`1 , . . . , d∗`m` ),
Q
where di = 1≤k≤mi d∗ik for all 1 ≤ i ≤ `. We write d∗ | d and have directly
Dn,d∗ ⊆ Dn,d .

(3.1)

Every ordered factorization is a refinement of (n). A complete refinement
of d = (di )1≤i≤` is obtained by replacing every di by one of its ordered
factorization into primes.
11

Two ordered factorizations d = (d1 , . . . , d` ) and e = (e1 , . . . , e` ) of n with
the same basis, define a permutation σ = σ(d, e) on the indices 1, 2, . . . , `
through
di = eσ(i)
(3.2)
for 1 ≤ i ≤ `. We require
σ(i) < σ(j) for all i < j with di = dj

(3.3)

to make σ unique. In other words, σ has to preserve the order of repeated
divisors. If even stronger,
σ(i) < σ(j) for all i < j with gcd(di , dj ) > 1,

(3.4)

then we call d and e associated. Any two complete refinements d∗ of d and e∗
of e, respectively, are associated and we have from (3.1)
Dn,{d∗ ,e∗ } ⊆ Dn,{d,e} .

(3.5)

We ask for associated refinements d∗ and e∗ , respectively, that describe the
same set of collisions as d and e. Algorithm 3.6 solves this task and returns
“coarsest” associated refinements d∗ and e∗ that yield equality in (3.5). We
call the output d∗ of Algorithm 3.6 the refinement of d by e and denote it
by d∗ = d // e. Similarly, e∗ = e // d is the refinement of e by d and this is
well-defined, since interchanging the order of the input merely interchanges
the order of the output.
Lemma 3.7. For two ordered factorizations d and e of n, the following are
equivalent.
(i) len(d // e) = len(d) and len(e // d) = len(e).
(ii) d // e = d and e // d = e.
(iii) d and e are associated.
Proof. Let d = (d1 , . . . , d` ) and e = (e1 , . . . , e` ) be associated and σ = σ(d, e)
the unique permutation satisfying (3.2) and (3.4). Then we have in step 5 of
Algorithm 3.6
(

gcd(d∗i,m+1 , e∗j,`+1 )

=

di = ej
1

if j = σ(i),
otherwise,

for all 1 ≤ i ≤ ` and 1 ≤ j ≤ m. Thus Algorithm 3.6 returns d, e on input
d, e and (ii) and (i) follow.
12

Algorithm 3.6: Refine d and e
Input: two ordered factorizations d = (d1 , . . . , d` ) and e = (e1 , . . . , em )
of n
Output:
refinements d∗ | d and e∗ | e

 two associated
1 . . . 1 d1


1 . . . 1 d2 


∗
 = (d∗i,j ) 1≤i≤`
1 d ← 
..


1≤j≤m+1
.




1 . . . 1 d` 
1 . . . 1 e1


1 . . . 1 e2 


∗
e ←
 = (e∗j,i ) 1≤j≤m
..


1≤m≤`+1
.


2



3
4
5
6
7
8
9
10
11



1 . . . 1 em
for i = 1, . . . , ` do
for j = 1, . . . , m do
c ← gcd(d∗i,m+1 , e∗j,`+1 )
d∗i,j ← c and e∗j,i ← c
d∗i,m+1 ← d∗i,m+1 /c and e∗j,`+1 ← e∗j,`+1 /c
end
end
remove last column (of all 1’s) from d∗ and e∗
d∗ ← (d∗i,j ) 1≤k≤`m /* rewrite row-by-row as a sequence

*/

e∗ ← (e∗j,i )

*/

k=(i−1)m+j
1≤i≤`,1≤j≤m

12

13
14

1≤k≤m`
k=(j−1)`+i
1≤j≤m,1≤i≤`

/* rewrite row-by-row as a sequence

remove all 1’s from d∗ and e∗
return d∗ , e∗

13

Conversely, let d = (d1 , . . . , d` ), e = (e1 , . . . , em ), and ` = len(d) ≥
len(e) = m. We assume that d and e are not associated and define i∗ as the
minimal index 1 ≤ i∗ ≤ ` such that there is no injective map τ : {1, . . . , i∗ } →
{1, . . . , m} with
di = eτ (i) for all 1 ≤ i ≤ i∗ ,
τ (i) < τ (j) for all 1 ≤ i < j ≤ i∗ with gcd(di , dj ) > 1
in analogy to (3.2) and (3.4), respectively.
We have two possible cases for the execution of the inner loop, steps 4-8,
for i = i∗ .
• If c = d∗i∗ ,m+1 in step 5 for some j, then e∗j,`+1 6= d∗i∗ ,m+1 (otherwise, we
could extend some injective τ for i∗ − 1 by i∗ 7→ j) and e∗j,`+1 splits into
at least two nontrivial factors in steps 6 and 7, thus len(e//d) ≥ len(e)+1
and e // d 6= e.
• Otherwise c 6= d∗i∗ ,m+1 in step 5 for all j, and d∗i∗ ,m+1 splits into at least
two nontrivial factors in steps 6 and 7, thus len(d // e) ≥ len(d) + 1 and
d // e 6= d.

Proposition 3.8. Let n be a positive integer and d, e two ordered factorizations of n with length ` and m, respectively. Then the following holds.
(i) Algorithm 3.6 works as specified and requires O(`m) gcd-computations
and O(`m) additional integer divisions.
(ii) We have Dn,{d,e} = Dn,{d//e,e} = Dn,{d//e,e//d} .
Proof. If we ignore the last column of d∗ and e∗ , respectively, we obtain
matrices that are each other’s transpose before and after every execution of
the inner loop in Algorithm 3.6. We use this property to define a sequence
of integer matrices M(k) ∈ Z(`+1)×(m+1) for 0 ≤ k ≤ `m to simultaneously
capture d∗ and e∗ after the inner loop has bee executed k times.
For k = 0, let


1

1


M(0) = 




1

e1

1
1

...
...
..
.

1
1

1 ... 1
e2 . . . em
14



d1

d2 




d` 


1

(0)

= (mi,j ) 1≤i≤`+1

1≤j≤m+1

and for k = (i − 1)m + j > 0, 1 ≤ i ≤ `, 1 ≤ j ≤ m, we define M(k) as M(k−1)
(k−1)
(k−1)
(k−1)
(k−1)
with mi,j replaced by c, mi,m+1 replaced by mi,m+1 /c, and m`+1,j replaced
(k−1)
by m`+1,j /c, respectively. Thus, we have the following invariants. For every
0 ≤ k ≤ `m and every 1 ≤ i ≤ `, the ith row of M(k) is a factorization of di .
Analogously, for every 1 ≤ j ≤ m, the jth column of M(k) is a factorization
of ej .
We have d∗ as M(k) with the last row removed, and e∗ as M(k) with the
last column removed and then transposed. In particular, the output d // e is
the first ` rows of M`m read as a sequence with 1’s ignored. Analogously,
the output e // d is the first m columns of M`m read as a sequence with 1’s
ignored.
(i) By the invariants of M(k) mentioned above, the output d // e is a
refinement of the input d. Analogously, the output e // d is a refinement of the
input e. The outputs also have the same basis, namely the entries of M(`m)
different from 1.
A bijection σ on {1, . . . , `m} is given by k = (i − 1)m + j 7→ (j − 1)` + i
with 1 ≤ i ≤ `, 1 ≤ j ≤ m. And this satisfies (3.2) since dk = ci,j = eσ(k)
for all such i, j. We also show (3.3) for σ. Let 1 ≤ k < k 0 ≤ `m with
k = (i − 1)m + j and k 0 = (i0 − 1)m + j 0 . We have to prove, that if
σ(k) > σ(k 0 ), then gcd(dk , dk0 ) = 1. The condition is equivalent to i < i0 and
j > j 0.
Lemma 3.8a. Let 1 ≤ i ≤ m, 1 ≤ j ≤ `, (i − 1)m + j ≤ k ≤ `m and
Q
(k)
c(k) the state of Algorithm 3.6 after k executions. Let Ri,j = j<j 0 ≤`+1 ci,j 0
Q
(k)
and Bi,j = i<i0 ≤m+1 ci0 ,j . Then gcd(Ri,j , Bi,j ) = 1. In particular, after the
algorithm has terminated, we have gcd(ci,j 0 , ci0 ,j ) = 1 for all i0 > i, j 0 > j.
Proof of Lemma 3.8a. Concentrate on the element ci,j 0 . By construction
Q
Q
k>j 0 ci,k and
k>i ck,j 0 are coprime. In particular, their factors ci,j and
ci0 ,j 0 .
This shows that d∗ and e∗ are associated if we restrict σ to indices k with
dk > 1.
Finally, the only arithmetic costs are the gcd-computations in step 5 and
the integer divisions in step 7.
(ii) We begin with the first equality. The matrix d∗ corresponds to
an ordered factorization, when read row-by-row and 1’s ignored. Let d(k)
correspond to the state of the matrix d∗ after the inner loop has been executed
exactly k times for 0 ≤ k ≤ `m. Thus d(0) = d, d(`m) = d // e, and we show
inductively
Dn,{d(k) ,e} = Dn,{d(k+1) ,e}
(3.8b)

15

for all 0 ≤ k < `m.
Let k + 1 = (i − 1)m + j with 1 ≤ i ≤ `, 1 ≤ j ≤ m. If c = 1 in step 5,
then d(k+1) = d(k) and (3.8b) holds trivially. Otherwise c > 1, and d(k+1) is
the proper refinement of d(k) , where the entry d∗i,m+1 in d(k) is replaced by the
pair (c, d∗i,m+1 /c).
We have to show that if a polynomial has decomposition degree sequences
d(k−1) and e, then it also has decomposition degree sequence d(k) . This follows
from the following generalization of Proposition 2.9.
Lemma 3.8c. Let g1 ◦ g2 ◦ · · · ◦ g` = h1 ◦ h2 ◦ · · · ◦ hm be two decompositions
with degree sequence d and e, respectively. Let 1 ≤ i ≤ `, 1 ≤ j ≤ m,
c = gcd(di , ej ), and
gcd(d1 · . . . · di−1 · di , e1 · . . . · ej−1 ) = gcd(d1 · . . . · di−1 , e1 · . . . · ej−1 · ej ).
(3.8d)
Then there are unique monic original polynomials u and v of degree c and
di /c, respectively, such that
gi = u ◦ v.
(3.8e)
Therefore, if a monic original polynomial f has decomposition degree sequences
d and e, then it also has decomposition degree sequence d∗ = (d1 , . . . , di−1 , c, di /c, di+1 , . . . , d` ).
Proof of Lemma 3.8c. Let A = g1 ◦ · · · ◦ gi−1 , B = h1 ◦ · · · ◦ hj−1 , and
b = gcd(deg(A), deg(B)). Then (3.8d) reads gcd(deg(A ◦ gi ), deg(B)) =
gcd(deg(A), deg(B◦hj )). This implies gcd(deg(B)/ gcd(deg(A), deg(B)), deg(gi )) =
gcd(deg(A)/ gcd(deg(A), deg(B)), deg(hj )) and since the first arguments of
both outer gcd’s are coprime, this quantity is 1. This proves
gcd(deg(A ◦ gi ), deg(B ◦ hj )) = gcd(deg(A), deg(B)) · gcd(deg(g), deg(h))
deg(A)
deg(hj )
· gcd(
,
)
gcd(deg(A), deg(B)) gcd(deg(gi , hj ))
· gcd(

deg(B)
deg(gi )
,
)
gcd(deg(A), deg(B)) gcd(deg(gi , hj ))

= gcd(deg(A), deg(B)) · gcd(deg(gi ), deg(hj ))
= bc.

(3.8f)

Then Proposition 2.9 applied to left components of the bi-decompositions
A ◦ (gi ◦ · · · ◦ g` ) = B ◦ (hj ◦ · · · ◦ hm )
16

(3.8g)

guarantees the existence of unique, monic original C, A0 , B 0 with deg(C) = b
and gcd(deg(A0 ), deg(B 0 )) = 1, such that
A = C ◦ A0 and B = C ◦ B 0 .

(3.8h)

We substitute (3.8h) back into (3.8g), ignore the common left component C
due to the absence of equal-degree collisions, and write with the associativity
of composition
(A0 ◦ gi ) ◦ (gi+1 ◦ · · · ◦ g` ) = (B 0 ◦ hj ) ◦ (hj+1 ◦ · · · ◦ hm ).
From (3.8f), we have gcd(deg(A0 ◦ gi ), deg(B 0 ◦ hj )) = gcd(di , ej ) = c. With
Proposition 2.9, we obtain some monic original w and A00 of degree c and
deg(A0 ◦ gi )/c = deg(A0 ) · di /c, respectively, such that
A0 ◦ gi = w ◦ A00 .

(3.8i)

We have gcd(deg(gi ), deg(A00 )) = di /c and a final application of Proposition 2.9
to the right components of (3.8i) provides the decomposition for g, claimed
in (3.8e).
To apply this result with d = d(k) and e, we have to provide (3.8d). For
(k + 1) = (i − 1)m + j, we split D = d1 · . . . · di−1 and E = e1 · . . . · ej−1 into
their common (left upper subset) C and the remainders R and B, respectively.
By Lemma 3.8a, we have gcd(R, B) = 1 and therefore gcd(D, E) = C. The
same lemma shows gcd(di , B) = 1 = gcd(R, ej ) and we have
gcd(Ddi , E) = C gcd(di , B) = C gcd(R, ej ) = gcd(D, Eej ),
as required for (3.8b).
Finally, interchanging the rôles of d and e yields
Dn,{d,e} = Dn,{d//e,e} = Dn,{d,e//d} = Dn,{d//e,e//d,d,e} = Dn,{d//e,e//d} ,
since composition degree sequence d // e implies d and similarly e // d implies
e.
Example 3.9. Let n = 7! = 5040, d = (12, 420), and e = (14, 360). We have
as refinements
d // e = (2, 6, 7, 60) ,
e // d = (2, 7, 6, 60) ,

(3.10)

and any f ∈ Dn,{d,e} has a unique decomposition f = a ◦ g ◦ b with a ∈ P2 ,
g ∈ D42,{(6,7),(7,6)} , and b ∈ P60 by Proposition 2.9.
17

Given a set D with more than two ordered factorizations, we repeatedly
replace pairs d, e ∈ D by d//e and e//d, respectively, until we reach a refinement
D∗ invariant under this operation. This process terminates by Lemma 3.7.
The result depends on the order of the applied refinements, but any order
ensures the desired properties described by the following proposition.
Proposition 3.11. Let n be a positive integer and D a set of c ordered
factorizations of n. There is a set D∗ of at most c ordered factorizations of n
with the following properties.
(i) All ordered factorizations of D∗ are pairwise associated.
(ii) Dn,D∗ = Dn,D .
(iii) D∗ can be computed from D with at most O(c2 ) calls to Algorithm 3.6.
Proof. For c = 1, we have D = {d} and D∗ = {d} satisfies all claims.
For c = 2, we have D = {d, e} for ordered factorizations d 6= e, and
D∗ = {d // e, e // d} satisfies all claims by Proposition 3.8.
Let c > 2 and D = {d(1) , . . . , dc }. By induction assumption, we can
assume all d(i) for 1 ≤ i < c − 1 be pairwise associated. Let d(c) = f and
D∗ = {d(1) // f, d(2) // f, . . . , d(c−1) // f, f // d(1) }. Clearly Dn,D = Pn,D∗ and it
remains to show that all elements of D∗ are pairwise associated.
By construction, we have d(1) // f associated with f // d(1) and by transitivity
of associatedness the following lemma suffices.
Lemma 3.11a. If d∗ and e∗ are associated, then so are d∗ // f and e∗ // f for
any factorization f.
Proof. Let σ = σ(d∗ , e∗ ) and compare the matrices
M = M(d∗ , f) and N = M(e∗ , f).
The claimed bijection between the indices of M and N is given by mapping
row i to row σ(i) (followed by identity on the columns).
Assume for contradiction that i is the minimal row index such that
Mi,∗ 6= Nσ(i),∗ and j is the minimal column index such that Mi,j 6= Nσ(i),j .
Let Nσ(i),j = aMi,j with a > 1. Then there is a column j 0 > j, such that
a | Mi,j 0 , since the rows Mi,∗ and Nσ(i),∗ are both factorizations of di = eσ(i) .
Also there is a row i0 > i, such that a | Mi0 ,j , since the earlier occurrences of
a in that column are pairwise matched.
By Lemma 3.8a, this is a contradiction. And analogously, if Mi,j = aNσ(i),j
with a > 1.

18

Any D∗ satisfying Proposition 3.11(i)-(ii) is called a normalization of D.
For a normalized D = {d(k) : 1 ≤ k ≤ c, we have the same basis d(k) for all
1 ≤ k ≤ c and call this multiset the basis of D, denoted by D.
Example 3.12. We add the ordered factorization f = (20, 252) to D = {d, e}
of Example 3.9 and obtain from (3.10) through refinement with f
d∗ = (d // e) // f = (2, 2, 3, 7, 5, 12) ,
e∗ = (e // d) // f = (2, 7, 2, 3, 5, 12) ,
f ∗ = (f // d) // e = (2, 2, 5, 3, 7, 12) .

(3.12b)

Any f ∈ Pn,{d,e,f} = Pn,{d∗ ,e∗ ,f ∗ } has a unique decomposition f = a ◦ g ◦ b
with a ∈ P2 , g ∈ D210,{(2,3,7,5),(7,2,3,5),(2,5,3,7)} , and b ∈ P12 . The normalized set
{d∗ , e∗ , f ∗ } has basis {2, 2, 3, 5, 7, 12}.

3.2

The relation graph of D

An ordered factorization d = (d1 , d2 , . . . , d` ) defines a relation ≺d on its basis
d = {d1 , d2 , . . . , d` } by
di ≺d dj for 1 ≤ i < j ≤ `.
In other words, di ≺d dj if di appears before dj in the ordered factorization d,
where we distinguish between repeated factors in the multiset d. We define
the relation graph Gd as directed graph with
• vertices d = {d1 , d2 , . . . , d` } and
• directed edges (dj , di ) = di ← dj for di ≺d dj .
This graph is a transitive tournament, that is a complete graph with directed
edges, where a path d ← e ← f implies an edge d ← f for any vertices
d, e, f ∈ d.
Now, let D = {d(1) , d(2) , . . . , d(c) } be a normalized set of c ordered factorizations with common basis D = {d1 , d2 , . . . , d` }. The relation ≺D is the union
of the relations ≺d(k) for 1 ≤ k ≤ c and the relation graph GD is the union
of the relation graphs Gd(k) for 1 ≤ k ≤ c. The undirected graph underlying
GD is still complete, but may be intransitive. See Figure 1 for the relation
graphs of Example 3.9 and Example 3.12.
We can express the relation ≺D with the permutations (3.2). Let σk =
σ(d(1) , d(k) ) for 1 ≤ k ≤ c. Then σ1 is the identity on 1, 2, . . . , ` and we have
di ≺d(k) dj

19

2

6

2'
2

12

3

7

60

5

7

Figure 1: Relation graphs of (3.10) and (3.12b); in the latter, 20 denotes the
first 2 in each ordered factorization.
if and only if σk (i) < σk (j).
A Hamiltonian path e = e1 ← · · · ← e` in a graph G visits each vertex
exactly once. We call e transitive, if its transitive closure is a subgraph of G.
In other words, e is transitive if ei ← ej is an edge in G for all 1 ≤ i < j ≤ `.
Q
For a relation graph G with vertices d1 , d2 , . . . , d` and n = 1≤i≤` di , we define
DG = {f ∈ Pn : for every transitive Hamiltonian path e1 ← · · · ← e`
in G, there is a decomposition f = g1 ◦ g2 ◦ · · · ◦ g`
with deg gi = ei for 1 ≤ i ≤ `}.
If G = {d} is a singleton, we have DG = Pd .
Proposition 3.13. Let n be a positive integer, D a normalized set of ordered
factorizations of n, and G the relation graph of D. We have
Dn,D = DG .
Proof. Every transitive tournament Gd for d ∈ D, has d as its unique transitive
Hamiltonian path. Since G is the union of all such Gd , we have “⊇”.
For “⊆”, we have to show that every polynomial with decomposition
degree sequences D also has decomposition degree sequence d∗ for every
transitive Hamiltonian path d∗ in G. We proceed on two levels. First, we
derive all transitive Hamiltonian paths in G from “twisting” the paths given
by D. Second, we show that the corresponding “twisted” decomposition
degree sequences follow from the given ones.
20

di

di
di +2

di−1

di +2

di−1

di +1

di +1

Figure 2: A “swap” between two transitive Hamiltonian paths di−1 ← di ←
di+1 ← di+2 and di−1 ← di ← di+1 ← di+2 along the bidirectional edge
between di and di+1 .
Let d∗ be a transitive Hamiltonian path in G and d ∈ D arbitrary. We
use Bubble-Sort to transform d into d∗ and call the intermediate states
after k passes d(k) , 0 ≤ k ≤ c, such that d(0) = d and d(c) = d∗ .
Algorithm 3.14: Bubble-Sort d according to d∗
1 ` ← len(d)
(0)
2 k ← 0, d
←d
(k)
3 while d
6= d∗ do
4
k ← k + 1, d(k) ← d(k−1) /* copy previous state
*/
5
for i = 1, . . . , ` − 1 do
6
σ = σ(d(k) , d∗ )
7
if σ(i) > σ(i + 1) then
(k) (k)
(k)
(k)
8
(di , di+1 ) ← (di+1 , di ) /* swap
*/
9
end
10
end
11 end
12 c ← k
In other words, d(k) is obtained from d(k−1) by at most ` − 1 “swaps” of
(k)
(k)
adjacent vertices. Figure 2 visualizes a swap of di and di+1 as in step 8.
The fundamental properties of Bubble-Sort guarantee correctness and
c ≤ `(` − 1)/2, see Cormen, Leiserson, Rivest & Stein (2009, Problem 2.2).
Furthermore, the following holds.
(k)

(k)

(i) Every pair (di , di+1 ) of swapped vertices in step 8 is connected by a
bidirectional edge in G.
(ii) Every d(k) , 0 ≤ k ≤ c, is a transitive Hamiltonian path in G.

21

(k)

For (i), we have the edge di
(k)

(k)

← di+1 from d(k−1) and the edge d∗σ(i+1) =

(k)

di+1 ← di = d∗σ(i) from d∗ with σ as in step 6.
For k = 0, (ii) holds by definition. For k > 0 it follows inductively from
k − 1, since a swap merely replaces the 4-subpath di−1 ← di ← di+1 ← di+2
by di−1 ← di+1 ← di ← di+2 , where the outer edges are guaranteed in G by
transitivity of d(k−1) and the inner edge by (i). Thus, the swapped path is
also a transitive Hamiltonian path in G.
Now, we mirror the “swaps” of vertices by “Ritt moves” of components as
introduced by Zieve & Müller (2008).
Claim 3.13a (Ritt moves). Let g1 ◦· · ·◦g` = h1 ◦· · ·◦h` be decompositions with
degree sequence d and e, respectively. Let d and e be associated, σ = σ(d, e),
and 1 ≤ i < ` with σ(i) > σ(i + 1). Then
∗
gi ◦ gi+1 = gi∗ ◦ gi+1
∗
with deg(gi ) = deg(gi+1
) and deg(gi+1 ) = deg(gi∗ ). Therefore, if some monic
original polynomial f has decomposition degree sequences d and e, it also has
the decomposition degree sequence d∗ = (d1 , . . . , di−1 , di+1 , di , di+2 , . . . , d` ).
The claim is based on the following lemma.
Lemma 3.13b. Let d and e be associated ordered factorizations, σ = σ(d, e),
1 ≤ i ≤ len(d), and j = σ(i). Then

gcd(d1 · . . . · di−1 , e1 · . . . · ej−1 ) = gcd(d1 · . . . · di−1 · di , e1 · . . . · ej−1 )
= gcd(d1 · . . . · di−1 , e1 · . . . · ej−1 · ej ).
In particular, (3.8d) holds.
Proof of Lemma 3.13b. For any 1 ≤ k < j, with gcd(ek , ej ) = gcd(ek , di ) > 1,
we have σ −1 (k) < i due to (3.4). In other words, σ −1 maps all indices
1 ≤ k < j, where gcd(ek , di ) > 1, into the set {1, . . . , i − 1}. Therefore
e1 · . . . · ej−1
gcd(
, di ) = 1,
gcd(d1 · . . . · di−1 , e1 · . . . · ej−1 )
gcd(d1 · . . . · di−1 · di , e1 · . . . · ej−1 ) = gcd(gcd(d1 · . . . · di−1 , e1 · . . . · ej−1 )di , e1 · . . . · ej−1 )
= gcd(d1 · . . . · di−1 , e1 · . . . · ej−1 ).

Let j 0 = σ(i + 1) < σ(i) = j, A = g1 ◦ · · · ◦ gi−1 , C = gi+2 ◦ · · · ◦ g` ,
A = h1 ◦ · · · ◦ hj 0 −1 , B 0 = hj 0 +1 ◦ · · · ◦ hj−1 , and C 0 = hj+1 ◦ · · · ◦ h` , such that
0

A ◦ gi ◦ gi+1 ◦ C = A0 ◦ hj 0 ◦ B 0 ◦ hj ◦ C 0 .

22

Lemma 3.13b for i and i + 1 yields
gcd(deg(A ◦ gi ), deg(A0 ◦ hj 0 ◦ B 0 )) = gcd(deg(A), deg(A0 ◦ hj 0 ◦ B 0 )),
gcd(deg(A ◦ gi ◦ gi+1 ), deg(A0 )) = gcd(deg(A ◦ gi ), deg(A0 ◦ hj 0 )),
respectively. From the former, we derive
deg(A0 ◦ hj 0 ◦ B 0 )
)
gcd(deg(A), deg(A0 ◦ hj 0 ◦ B 0 ))
deg(A0 ◦ hj )
= gcd(gi ,
).
gcd(deg(A), deg(A0 ◦ hj 0 ))

1 = gcd(gi ,

And then continue the latter as
gcd(deg(A ◦ gi ◦ gi+1 ), deg(A0 ))
= gcd(deg(A ◦ gi ), deg(A0 ◦ hj 0 ))
= gcd(deg(A), deg(A0 ◦ hj 0 )) · gcd(gi ,
= gcd(deg(A), deg(A0 ◦ hj 0 )).

deg(A0 ◦ hj 0 )
)
gcd(deg(A), deg(A0 ◦ hj 0 ))
(3.13c)

Let G = gi ◦ gi+1 and H = hj . We have gcd(di , di+1 ) = 1 due the “twisting
condition” σ(i + 1) < σ(i) and therefore gcd(deg(G), deg(H)) = di+1 . We
apply Lemma 3.8c with gi = G, hj = H, and c = di+1 in the notation of that
claim, and find, since (3.13c) provides condition (3.8d),
∗
G = gi∗ ◦ gi+1
∗
with deg(gi∗ ) = di+1 and deg(gi+1
) = di as required.
Repeated application of Claim 3.13a shows that for every f ∈ Dn,D ,
d ∈ D, and every transitive Hamiltonian path d∗ in G, we have d(k) as in
Algorithm 3.14 as decomposition degree sequence. In particular, d(c) = d∗ .

3.3

The Decomposition of Dn,D

Every directed graph admits a decomposition into strictly connected components, where any two distinct vertices are connected by paths in either
direction. Since a relation graph G is the union of directed complete graphs,
its strictly connected components Gi , 1 ≤ i ≤ `, are again relation graphs
and form a chain G1 ← G2 ← · · · ← G` . Figure 3 shows the connected
components of the relation graphs Figure 1

23

6
60

2
7
3
2'

7

2

12

5
Figure 3: The three strongly connected components of each relation graph in
Figure 1, respectively.

24

Theorem 3.14. Let G be a relation graph with strongly connected components
G1 ← G2 ← · · · ← G` . We have
DG = DG1 ◦ DG2 ◦ · · · ◦ DG`
and for any f ∈ DG , we have uniquely determined gi ∈ DGi such that
f = g1 ◦ g2 ◦ · · · ◦ g` . Furthermore, over a finite field F = Fq with q elements,
we have
Y
#DG =
#DGi .
1≤i≤`

Proof. For f ∈ Pn , where n =
equivalent.

Q

v∈G

v, we show that the following are

(i) The polynomial f has decomposition degree sequence d for every transitive Hamiltonian path d in G.
(ii) The polynomial f has decomposition degree sequence d = d1 ← d2 ←
· · · ← d` for every concatenation of transitive Hamiltonian paths di in
Gi for 1 ≤ i ≤ `.
Assume (i) and let d = d1 ← d2 ← · · · ← d` be the concatenation of
transitive Hamiltonian paths di in Gi for 1 ≤ i ≤ ` as in (ii). Then di is
a Hamiltonian path in G. Since the underlying undirected graph of G is
complete, we have di ← dj in G for any vertices di ∈ Gi and dj ∈ Gj in
distinct strictly connected components with i < j. Thus d is also transitive
and f has decomposition degree sequence d by (i).
Conversely, assume (ii) and observe that the decomposition of G into
strictly connected components induces a decomposition of every transitive
Hamiltonian path d in G into Hamiltonian paths di in Gi . These are transitive,
since transitivity is a local condition and f has decomposition degree sequence
d by (ii).
Uniqueness and thus the counting formula follow from the absence of
equal-degree collisions in the tame case.
We split the edge set E of a strictly connected relation graph G with
→
−
vertices V into its uni-directional edges E = {(u, v) ∈ E : (v, u) ∈
/ E} and its
→
−
bi-directional edges (2-loops) E = {{u, v} ⊆ V : {(u, v), (v, u)} ∈ E} = E \ E .
We call the corresponding graphs on V the directed and the undirected
subgraph of G, respectively. The directed subgraph of G is a directed acyclic
graph since G is the union of transitive tournaments. The undirected subgraph
of G is connected. It is also the union of the permutation graphs of σk ,
1 ≤ k ≤ c.
25

3

7

2

5

Figure 4: The strongly connected component on 4 vertices of Figure 3
decomposed into its undirected subgraph (red) and its directed subgraph
(blue) with Max-Sink-sorting 7 ≺ 2 ≺ 5 ≺ 3.

26

→
−
The directed subgraph G captures the requirements on the position
of the degrees in a decomposition sequence. The undirected subgraph G
captures the admissible Ritt moves d’après Zieve & Müller (2008) and thus
the requirements on the shape of the components.
Every directed acyclic graph admits a topological sorting v1 , v2 , . . . , v` of
→
−
its vertices, where a directed edge vi ← vj in G implies i < j, see Cormen
et al. (2009, Section 22.4). A directed acyclic graph may have several distinct
topological sortings. Tarjan (1976) suggested to use Depth-First-Search
→
−
on G . The time step, when Depth-First-Search visits a vertex for the
last time, is called the finish time of the vertex and listing the vertices with
increasing finish time yields a topological sorting. The result is unique, if the
tie-break rule for expanding in Depth-First-Search is deterministic. We
use the following terminology.
Let U (v) denote the open G-neighborhood of a vertex v. It is always
nonempty. We call a vertex v locally maximal, if its value is greater or equal
than the value of every vertex in U (v). Since vertices with equal values are
never connected by an edge in G, a locally maximal v is always strictly greater
than all vertices in U (v). Furthermore, there is at least one locally maximal
vertex, namely a “globally” maximal one. There is a unique enumeration of
the locally maximal vertices d1 , d2 , . . . , dm such that
d1 ← d2 ← · · · ← dm
is a directed path in G. Furthermore, we define for 1 ≤ i ≤ m,
Vi = U (di ) \ U (di+1 ) and Wi = Vi ∪ {di },
V0 = W0 = {v ∈ G : no edge di ← v in G for any 1 ≤ i ≤ m},
Vm+1 = Wm+1 = {v ∈ G : no edge v ← di in G for any 1 ≤ i ≤ m}.
→
−
The Wi , 0 ≤ i ≤ m + 1, form a partition of all vertices of G and we formulate
the tie-break rule for Depth-First-Search as follows. Given vertices
u ∈ Wi and v ∈ Wj with i < j, the vertex u is preferred. Given vertices
u, v ∈ Wi , the vertex with the larger value is preferred. Since vertices with
→
−
equal value are always connected by a unidirectional edge in G due to (3.4),
the search has never to choose between to vertices with the same value and
Depth-First-Search with this tie-break rule yields a unique topological
→
−
sorting. We call it the Max-Sink topological sorting of G . Figure 4 shows
the largest strongly connected component of Figure 3 and its Max-Sink
topological sorting.

27

Theorem 3.15. Let G be a strongly connected relation graph with at least two
→
−
vertices, directed subgraph G , and undirected subgraph G. Let d1 , d2 , . . . , d`
→
−
be the Max-Sink topological sorting of G and let ei be the product of all
vertices in the open G-neighborhood of di . For every f ∈ DG either (i) or (ii)
holds, and (iii) is also valid.
(i) (Exponential Case) There are unique gi ∈ Edi ,ei for 1 ≤ i ≤ ` and a ∈ F
such that
f = (g1 ◦ g2 ◦ · · · ◦ g` )[a] .
(ii) (Trigonometric Case) There are unique z, a ∈ F with z 6= 0 such that
f = Td1 d2 ···d` (x, z)[a] .
(iii) If G contains no edge that connects two vertices both larger than 2, then
the Trigonometric Case is included in the Exponential Case. Otherwise,
they are mutually exclusive.
Conversely,
[F ]

Dn,G = Td1 d2 ···dm ,1 ∪ (Ed1 ,e1 ◦ Ed2 ,e2 ◦ · · · ◦ Edm ,em )[F ] .

(3.15a)

The ei are well-defined, since there are no empty neighborhoods in the
connected graph G with at least two vertices.
Proof. We begin with the proof of existence, then show uniqueness and
conclude with the “converse” (3.15a).
→
−
The Max-Sink topological sorting d1 , d2 , . . . , d` of G yields a transitive
Hamiltonian path
d = d1 ≺ d2 ≺ · · · ≺ d`
in G. For the rest of the proof, we identify the max-sink topological sorting
with the corresponding transitive Hamiltonian path.
We (re)label the locally maximally vertices d1 , d2 , . . . , dm and the elements
(1) (2)
(` )
of Vi as di , di , . . . , di i for 0 ≤ i ≤ m + 1 and `i = #Vi such that
(1)

(` )

(1)

(` )

(1)

d = (d0 , . . . , d0 0 , d1 , d1 , . . . , d1 1 , d2 , d2 , . . . ,
(`

)

(1)

(`

)

m−1
m+1
(`m )
dm−1
, dm , d(1)
m , . . . , dm , dm+1 , . . . , dm+1 )
= (V0 , d1 , V1 , d2 , . . . , dm , Vm , Vm+1 ),

28

(1)

(2)

(` )

where the Vi are read as tuple (di , di , . . . , di i ). Then f has a decomposition
(1)

(` )

(1)

(` )

(1)

f = G0 ◦ · · · ◦ G0 0 ◦ G1 ◦ G1 ◦ · · · ◦ G1 1 ◦ G2 ◦ G2 ◦ . . .
◦

(`m−1 )
Gm−1

(`m )
◦ Gm ◦ G(1)
◦
m ◦ · · · ◦ Gm

(1)
Gm+1

◦ ··· ◦

(3.15b)

(`m+1 )
Gm+1

(j)

with Gi ∈ Pd(j) for 0 ≤ i ≤ m + 1, 1 ≤ j ≤ `i , and Gi ∈ Pdi for 1 ≤ i ≤ m.
i

We assume for the moment that all edges in G contain a 2. Then Theorem 2.8 reduces to the exponential case, and we proceed as follows. First, we
(j)
[a ]
show that every Gi for 1 ≤ i ≤ m, 1 ≤ j ≤ `i , is of the form gi i for unique
gi ∈ Ed(j) ,e(j) and unique ai ∈ F . Then, we extend this to i = 0 and i = m + 1.
i
i
Finally, we show that the shifting parameters ai are “compatible” such that a
single shifting parameter a suffices.
For every 1 ≤ i ≤ m, we use Bubble-Sort Algorithm 3.14 with
Lemma 3.16 to obtain the decomposition degree sequence
(`i+1 )

(V0 , d1 , V1 , . . . , di , Vi , di
(`

(mi )

, . . . di

)

, di+1 , V̂i+1 , . . . , dm , V̂m , Vm+1 ),

(m )

where U (di ) = Vi ∪ {di i+1 , . . . di i } and the latter elements have been
Q
(j)
omitted from Vi+1 , . . . , Vm . We have ei = 1≤j≤mi di and this implies the
two decomposition degree sequences

(V0 , d1 , V1 , . . . , di , ei , di+1 , V̂i+1 , . . . , dm , V̂m , Vm+1 ), (V0 , d1 , V1 , . . . , ei , di , di+1 , V̂i+1 , . . . , dm , V̂m , Vm+1
Thus, there are unique gi ∈ Edi ,ei and ai ∈ F such that in (3.15b), we have
(1)

(`i )

Gi ◦ Gi ◦ · · · ◦ Gi

(1)

(`i )

= (gi ◦ xdi ◦ · · · ◦ x(di

) [ai ]

)

(j)

.

The same form applies to i = 0, since there is at least one di with 1 ≤ i ≤ m,
1 ≤ j ≤ `i that is in the G-neighborhood of some element of V0 due to the
strong connectedness of G. And since there is no locally maximal element
(j)
in V0 all components are of the form xd0 with possible some shift applied.
Every connection in G relates the corresponding shifting parameters and since
G has a Hamiltonian path, they are all determined by a single choice.
Now, for the general case, where some collisions may be trigonometric,
but not exponential. For any two locally maximal vertices di and dj there is
some vertex d ∈ U (di ) ∩ U (dj ). This shows, that either all blocks fall into the
exponential case or all blocks fall into the trigonometric case. The two cases
are disjoint if and only if there is some edge in G that connects two vertices
both with value greater than 2.
29

The stabilizer of original shifting is {0} for nonlinear monic original
polynomials and there are no equal-degree collisions. Hence the representation
is unique.
The converse (3.15a) is a direct computation.
Lemma 3.16. Let i < j and dj in the open G-neighborhood of di . Then for
every i < k < j, we have dk in the open G-neighborhood of di or dj or both.
Proof. The tournaments underlying G are acyclic. Therefore, if di ≺ dk ≺ dj
and dj ≺ dk , then at least one other edge is bidirectional, too.

4

Exact Counting of Decomposable Polynomials

The classification of Theorem 3.15 yields the exact number of decomposable
polynomials at degree n over a finite field Fq .
Theorem 4.1. Let G be a strongly connected relation graph with undirected
subgraph G. Let d1 , d2 , . . . , d` be the vertices of G and ei be the product of all
vertices in the (open) G-neighborhood of di . Let δG,2 be 1 if there is no edge
in G between two vertices both larger than 2 and let δG,2 be 0 otherwise. Then
#DG =


q d−1
Q
q · (

if G = {d},
di ∈G

q bdi /ei c + (1 − δG,2 ) · (q − 1)) otherwise.

Proof. For G = {d}, this follows from (2.1a). Otherwise from the (non)uniqueness
of the parameters in Theorem 3.15.
We are finally ready to employ the inclusion-exclusion formula (2.4) from
the beginning. For a nonempty set D of nontrivial divisors of n, it requires
#Dn,D = #Dn,D for D = {(d, n/d) : d ∈ D}. We compute the normalization
D∗ by repeated application of Algorithm 3.6 and derive the relation graph
of D∗ . Then #Dn,D = #PG and the latter follows from Theorem 3.14 and
Theorem 4.1.
This is easy to implement, see Algorithm 4.2, and yields the exact expressions for #Dn (Fq ) at lightning speed, see Table 1. Where no exact expression
was previously known, we compare this to the upper and lower bounds of
von zur Gathen (2014a).

30

Algorithm 4.2: Count Decomposables
Input: positive integer n
Output: #Dn (Fq ) as a polynomial in q for n coprime to q
1 if n = 1 or n is prime then
2
return 0
3 end
4 total ← 0
5 N ← {1 < d < n : d | n}
6 for ∅ =
6 D ⊆ N do
7
D ← {(d, n/d) : d ∈ D}
8
D∗ ← normalization of D
∗
9
G ← relation graph of D
10
collisions ← 1
11
for strongly connected components Gj of G do
12
Gj ← undirected subgraph of Gj
13
if Gj = {d} then
14
connected ← q d
15
else
16
{d1 , d2 , . . . , d` } ← Gj
17
for i = 1, . . . , ` do
18
U ← open neighborhood of di in Gj
Q
19
ei ← v∈U
20
end
Q
21
connected ← di ∈Gj q bdi /ei c
22
if some edge in Gj connects two vertices both larger than 2
then
23
connected ← connected + q − 1
24
end
25
connected ← connected · q
26
end
27
collisions ← collisions · connected
28
end
29
k ← #D
30
total ← total + (−1)k collisions
31 end
32 return total

31

Table 1: Exact values of #Dn (Fq ) in the tame case for composite n ≤ 50,
consistent with the upper and lower bounds (in the last column) or exact
values (no entry in the last column) of von zur Gathen (2014a, Theorem 5.2).

5

Conclusion

We presented a normal form for multi-collisions of decompositions of arbitrary
length with exact description of the (non)uniqueness of the parameters. This
lead to an efficiently computable formula for the exact number of such collisions
at degree n over a finite field of characteristic coprime to p. We concluded
with an algorithm to compute the exact number of decomposable polynomials
at degree n over a finite field Fq in the tame case.
We introduced the relation graph of a set of collisions which may be of
independent interest due to its connection to permutation graphs. It would
be interesting to characterize sets D of ordered factorizations that lead to
identical contributions #Dn,D and to quickly derive #Dn,D∪{e} form #Dn,D
or conversely. Finally, this work deals with polynomials only and the study
of rational functions with the same methods remains open.

6

Acknowledgements

Many thanks go to Joachim von zur Gathen for useful discussions and pointers
to the literature. This work was funded by the B-IT Foundation and the
Land Nordrhein- Westfalen.

References
Roberto M. Avanzi & Umberto M. Zannier (2003). The equation
f (X) = f (Y ) in rational functions X = X(t), Y = Y (t). Compositio Math.
139(3), 263–295. doi:10.1023/B:COMP.0000018136.23898.65.
Eric Bach & Jeffrey Shallit (1997). Algorithmic Number Theory, Vol.1:
Efficient Algorithms. MIT Press, Cambridge MA, second printing edition.
ISBN 0-262-02405-5.
David R. Barton & Richard Zippel (1985). Polynomial Decomposition
Algorithms. Journal of Symbolic Computation 1, 159–168.
Raoul Blankertz, Joachim von zur Gathen & Konstantin Ziegler
(2013). Compositions and collisions at degree p2 . Journal of Symbolic
32

Computation 59, 113–145. ISSN 0747-7171. URL http://dx.doi.org/
10.1016/j.jsc.2013.06.001. Also available at http://arxiv.org/abs/
1202.5810. Extended abstract in Proceedings of the 2012 International
Symposium on Symbolic and Algebraic Computation ISSAC ’12, Grenoble,
France (2012), 91–98.
Arnaud Bodin, Pierre Dèbes & Salah Najib (2009). Indecomposable
polynomials and their spectrum. Acta Arithmetica 139(1), 79–100.
John J. Cade (1985). A New Public-key Cipher Which Allows Signatures.
In Proceedings of the 2nd SIAM Conference on Applied Linear Algebra.
SIAM, Raleigh NC.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest &
Clifford Stein (2009). Introduction to Algorithms. MIT Press, Cambridge MA, London UK, 3rd edition. ISBN 978-0-262-03384-8 (hardcover),
978-0-262-53305-8 (paperback), 1312 pages .
F. Dorey & G. Whaples (1974). Prime and Composite Polynomials. Journal of Algebra 28, 88–101. URL http://dx.doi.org/10.1016/
0021-8693(74)90023-4.
H. T. Engstrom (1941). Polynomial Substitutions. American Journal of Mathematics 63, 249–255. URL http://www.jstor.org/stable/
pdfplus/2371520.pdf.
Michael D. Fried & R. E. MacRae (1969). On the invariance of chains
of Fields. Illinois Journal of Mathematics 13, 165–171.
Joachim von zur Gathen (1990a). Functional Decomposition of Polynomials: the Tame Case. Journal of Symbolic Computation 9, 281–299. URL
http://dx.doi.org/10.1016/S0747-7171(08)80014-4.
Joachim von zur Gathen (1990b). Functional Decomposition of Polynomials: the Wild Case. Journal of Symbolic Computation 10, 437–452. URL
http://dx.doi.org/10.1016/S0747-7171(08)80054-5.
Joachim von zur Gathen (2002). Factorization and Decomposition of Polynomials. In The Concise Handbook of Algebra, edited by Alexander V.
Mikhalev & Günter F. Pilz, 159–161. Kluwer Academic Publishers.
ISBN 0-7923-7072-4.
Joachim von zur Gathen (2014a). Counting decomposable univariate
polynomials. To appear in Combinatorics, Probability and Computing,
33

Special Issue. Extended abstract in Proceedings of the 2009 International
Symposium on Symbolic and Algebraic Computation ISSAC ’09, Seoul,
Korea (2009). Preprint (2008) available at http://arxiv.org/abs/0901.
0054.
Joachim von zur Gathen (2014b). Normal form for Ritt’s Second Theorem.
Finite Fields and Their Applications 27, 41–71. ISSN 1071-5797. URL http:
//dx.doi.org/10.1016/j.ffa.2013.12.004. Also available at http://
arxiv.org/abs/1308.1135.
Joachim von zur Gathen, Dexter Kozen & Susan Landau (1987).
Functional Decomposition of Polynomials. In Proceedings of the 28th Annual
IEEE Symposium on Foundations of Computer Science, Los Angeles CA,
127–131. IEEE Computer Society Press, Washington DC. URL http:
//dx.doi.org/10.1109/SFCS.1987.29.
Mark William Giesbrecht (1988). Some Results on the Functional
Decomposition of Polynomials. Master’s thesis, Department of Computer
Science, University of Toronto. Technical Report 209/88. Available as
http://arxiv.org/abs/1004.5433.
Johannes Grabmeier, Erich Kaltofen & Volker Weispfenning
(editors) (2003). Computer Algebra Handbook – Foundations, Applications,
Systems. Springer-Verlag, Berlin, Heidelberg, New York. ISBN 3-540-654666. URL http://www.springer.com/978-3-540-65466-7.
Jaime Gutierrez & Dexter Kozen (2003). Polynomial Decomposition.
In Grabmeier, Kaltofen & Weispfenning (2003), section 2.2.4 (pages 26–28).
URL http://www.springer.com/978-3-540-65466-7.
Jaime Gutierrez & David Sevilla (2006). On Ritt’s decomposition
theorem in the case of finite fields. Finite Fields and Their Applications
12(3), 403–412. URL http://dx.doi.org/10.1016/j.ffa.2005.08.004.
Dexter Kozen & Susan Landau (1989). Polynomial Decomposition
Algorithms. Journal of Symbolic Computation 7, 445–456. URL http:
//dx.doi.org/10.1016/S0747-7171(89)80027-6. An earlier version was
published as Technical Report 86-773, Cornell University, Department of
Computer Science, Ithaca, New York, 1986.
Dexter Kozen, Susan Landau & Richard Zippel (1996). Decomposition
of Algebraic Functions. Journal of Symbolic Computation 22, 235–246.

34

H. Levi (1942). Composite Polynomials with coefficients in an arbitrary
Field of characteristic zero. American Journal of Mathematics 64, 389–400.
Alice Medvedev & Thomas Scanlon (2014). Invariant varieties for polynomial dynamical systems. Annals of Mathematics 179(1), 81–177. URL
http://dx.doi.org/10.4007/annals.2014.179.1.2. Also available at
http://arxiv.org/abs/0901.2352v3.
J. F. Ritt (1922). Prime and Composite Polynomials. Transactions of the
American Mathematical Society 23, 51–66. URL http://www.jstor.org/
stable/1988911.
Andrzej Schinzel (1982). Selected Topics on Polynomials. Ann Arbor;
The University of Michigan Press. ISBN 0-472-08026-1.
Andrzej Schinzel (2000). Polynomials with special regard to reducibility.
Cambridge University Press, Cambridge, UK. ISBN 0521662257.
Robert Endre Tarjan (1976). Edge-Disjoint Spanning Trees and DepthFirst Search. Acta Informatica 6, 171–185. URL http://dx.doi.org/10.
1007/BF00268499.
Pierre Tortrat (1988). Sur la composition des polynômes. Colloquium
Mathematicum 55(2), 329–353.
Gerhard Turnwald (1995). On Schur’s Conjecture. Journal of the
Australian Mathematical Society, Series A 58, 312–357. URL http://
anziamj.austms.org.au/JAMSA/V58/Part3/Turnwald.html.
U. Zannier (1993). Ritt’s Second Theorem in arbitrary characteristic.
Journal für die reine und angewandte Mathematik 445, 175–203.
Umberto Zannier (2008). On composite lacunary polynomials and the
proof of a conjecture of Schinzel. Inventiones mathematicae 174, 127–138.
ISSN 0020-9910 (Print) 1432-1297 (Online). URL http://dx.doi.org/10.
1007/s00222-008-0136-8.
Michael E. Zieve & Peter Müller (2008). On Ritt’s Polynomial
Decomposition Theorems. Submitted, URL http://arxiv.org/abs/0807.
3578.

35

