# Interpolation by decomposable univariate polynomials

Joachim von zur Gathen  B-IT
Universität Bonn
D - 53113 Bonn<EMAIL_ADDRESS>and  Guillermo Matera  Universidad
Nacional de General Sarmiento, Instituto del Desarrollo Humano, J.M. Gutiérrez
1150 (B1613GSX) Los Polvorines, Buenos Aires, Argentina
and National Council of Science and Technology (CONICET), Argentina
<EMAIL_ADDRESS>
###### Abstract.

The usual univariate interpolation problem of finding a monic polynomial $f$
of degree $n$ that interpolates $n$ given values is well understood. This
paper studies a variant where $f$ is required to be composite, say, a
composition of two polynomials of degrees $d$ and $e$, respectively, with
$de=n$, and therefore $d+e-1$ given values. Some special cases are easy to
solve, and for the general case, we construct a homotopy between it and a
special case. We compute a _geometric solution_ of the algebraic curve
presenting this homotopy, and this also provides an answer to the
interpolation task. The computing time is polynomial in the geometric data,
like the degree, of this curve. A consequence is that for almost all inputs, a
decomposable interpolation polynomial exists.

###### Key words and phrases:

Polynomial composition, interpolation, algorithms, symbolic computation,
complexity.

###### 1991 Mathematics Subject Classification:

Primary 12E05, Secondary 68W30, 14Q05, 14Q20

##  1\. Introduction

For two univariate polynomials $g,h\in{\mathbb{F}}[X]$ of degrees $d$, $e$,
respectively, over a field ${\mathbb{F}}$, their _composition_

(1.1) $f=g(h)=g\circ h\in{\mathbb{F}}[X]$

is a polynomial of degree $n=de$. If such $g$ and $h$ exist with degree at
least $2$, then $f$ is called _decomposable_ (or _composed, composite_ , a
_composition_). With a suitable normalization, explained in Section 3, we
denote as $C_{n,d}({\mathbb{F}})$ the set of decomposable polynomials $f$ as
above.

The standard univariate interpolation problem is well understood. It asks for
a monic interpolation polynomial $f$, given $\deg f$ many constraints on
values. When we require $f\in C_{n,d}({\mathbb{F}})$, then only the $d+e-1$
coefficients of $g$ and $h$ need to be determined. It is natural to impose the
same number of constraints. We write $\overline{{\mathbb{F}}\\!}{\,}$ for an
algebraic closure of ${\mathbb{F}}$ and consider the following interpolation
problem:

######  Problem 1.1.

Given integers $d,e\geq 2$,
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{d+e-1})\in{\mathbb{F}}^{d+e-1}$
with $\alpha_{i}\not=\alpha_{j}$ for $i\not=j$,
$\boldsymbol{\beta}=(\beta_{1},\ldots,\beta_{d+e-1})\in{\mathbb{F}}^{d+e-1}$,
and $n=de$, does there exist $f\in C_{n,d}(\overline{{\mathbb{F}}\\!}{\,})$
such that $f(\alpha_{i})=\beta_{i}$ for $1\leq i\leq d+e-1$ and $f=g\circ h$
with $\deg g=d$ as above?

Standard univariate interpolation at $n$ points $(\alpha_{i},\beta_{i})$ has a
solution if $\alpha_{i}\neq\alpha_{j}$ for $i\neq j$, that is, $\prod_{i\neq
j}(\alpha_{i}-\alpha_{j})$ is nonzero. But most polynomials are
indecomposable: the decomposable ones form a subvariety of small dimension
within the space of all polynomials (Fact 3.1). Thus interpolating at $n$
points and then decomposing will usually not furnish a solution. Our
parametrization provides a polynomial $R$ (Definition 3.9) such that
$R(\alpha)\neq 0$ guarantees a decomposable interpolant. Thus almost all such
problems have a solution and Problem 1.1 a positive answer.

This issue arises, for example, in the black-box model of representing
polynomials. If it is expensive to calculate any single value of the
polynomial—say by some experiment—then one may wish to minimize the number of
values sufficient to identify the polynomial. If, in addition, the polynomial
is a priori known to be decomposable, then our method provides the optimal
number of values required.

##  2\. Special cases of the interpolation problem

In this section, we show that Problem 1.1 has a positive answer for a generic
choice of $\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ and certain, rather
special, $\boldsymbol{\beta}\in{\mathbb{F}}^{d+e-1}$. These results hold over
an arbitrary field ${\mathbb{F}}$.

For any positive integer $\ell$ and vector
$\boldsymbol{x}=(x_{1},\ldots,x_{\ell})\in{\mathbb{F}}^{\ell}$, we write
$\\#\boldsymbol{x}$ for the number of different coordinates of
$\boldsymbol{x}$, so that $\\#\boldsymbol{x}=\\#\\{x_{1},\ldots,x_{\ell}\\}$.
Then $\boldsymbol{x}$ defines a set partition $\mathcal{P}_{\boldsymbol{x}}$
of $\\{1,\ldots,\ell\\}$ into $\\#\boldsymbol{x}$ blocks, where $i,j\leq\ell$
belong to the same block if and only if $x_{i}=x_{j}$. The Stirling number of
the second kind $S_{2}(\ell,m)$ is the number of set partitions of
$\\{1,\ldots,\ell\\}$ into exactly $m$ blocks ($m$-partitions). For a
polynomial $f\in{\mathbb{F}}[X]$, we write
$f(\boldsymbol{x})=(f(x_{1}),\ldots,f(x_{\ell}))\in{\mathbb{F}}^{\ell}$, so
that $\\#f(\boldsymbol{x})$ equals the number of different values that $f$
takes on $\\{x_{1},\ldots,x_{\ell}\\}$. For two set partitions ${\mathcal{P}}$
and ${\mathcal{Q}}$ we say that ${\mathcal{P}}$ is a _refinement_ of
${\mathcal{Q}}$ and write ${\mathcal{P}}\preccurlyeq{\mathcal{Q}}$, if each
block of ${\mathcal{P}}$ is contained in one block of ${\mathcal{Q}}$. If
$\mathcal{P}$ consists of $m$ blocks, we call it an $m$-refinement of
$\mathcal{Q}$. Then $m\geq\\#\mathcal{Q}$, and some $m$-refinement of
$\mathcal{Q}$ exists if and only if $\ell\geq m\geq\\#\mathcal{Q}$. This
induces a partial order on the set of partitions of $\\{1,\ldots,\ell\\}$. The
minimum of this lattice consists of $\ell$ singletons, and its maximum of a
single block. Let
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{d+e-1})\in{\mathbb{F}}^{d+e-1}$
and $(g,h)$ be a solution to Problem 1.1. Then

$h(\alpha_{i})=h(\alpha_{j})\Longrightarrow\beta_{i}=g\circ
h(\alpha_{i})=g\circ h(\alpha_{j})=\beta_{j}\text{ for }i,j\leq d+e-1.$

Thus
${\mathcal{P}}_{h(\boldsymbol{\alpha})}\preccurlyeq{\mathcal{P}}_{\boldsymbol{\beta}}$
and $\\#h(\boldsymbol{\alpha})\geq\\#\boldsymbol{\beta}$.

We use the polynomial $R^{(1)}$ defined in (2.5) below.

######  Lemma 2.1.

The polynomial $R^{(1)}\in{\mathbb{F}}[\boldsymbol{A}]$ is nonzero and has
degree less than $e^{2}\,S_{2}(d+e-1,d-1)$. For any
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{d+e-1})\in{\mathbb{F}}^{d+e-1}$
with $R^{(1)}(\boldsymbol{\alpha})\neq 0$ and any
$h=X^{e}+h_{e-1}X^{e-1}+\cdots+h_{1}X\in{\mathbb{F}}[X]$ we have
$\\#h(\boldsymbol{\alpha})\geq d$.

###### Proof.

Assume that $h=X^{e}+h_{e-1}X^{e-1}+\cdots+h_{1}X\in{\mathbb{F}}[X]$ satisfies
$m=\\#h(\boldsymbol{\alpha})<d$. We consider the $m$-partition
$\mathcal{P}=\\{P_{1},\ldots,P_{m}\\}={\mathcal{P}}_{h(\boldsymbol{\alpha})}$
of $\\{1,\ldots,d+e-1\\}$. Thus $i,j<d+e$ are in the same block of
$\mathcal{P}$ if and only if $h(\alpha_{i})=h(\alpha_{j})$. In order to
facilitate notation, we sort the integers in each
$P_{k}\subseteq\\{1,\ldots,d+e-1\\}$ in the natural order, let $i_{k}\in
P_{k}$ be the smallest element of $P_{k}$, and furthermore sort
$\\{1,\ldots,m\\}$ according to the $i_{k}$’s, so that
$i_{1}<i_{2}<\cdots<i_{m}$. Then we have

(2.1) $h(\alpha_{i_{k}})-h(\alpha_{j})=0\text{ for all }k\leq m\text{ and
}j\in P_{k}.$

We also set $P_{k}^{(1)}=P_{k}\setminus\\{i_{k}\\}$. In particular, if
$P_{k}=\\{i_{k}\\}$ is a singleton, then $P_{k}^{(1)}=\emptyset$. The various
instances of (2.1) provide

$\sum_{1\leq k\leq m}\\#P_{k}^{(1)}=\sum_{1\leq k\leq
m}(\\#P_{k}-1)=\sum_{1\leq k\leq m}\\#P_{k}-m=d+e-1-m\geq e$

linear equations on the coefficients of $h$.

We now pick $e$ of these equations. We might take any $e$ ones, but for a
unique choice, we take the “first” ones, as follows. We let $\ell\leq m$ be
the smallest index so that

$\sum_{1\leq k\leq\ell}\\#P_{k}^{(1)}\geq e,\quad
P_{\ell}^{(1)}\neq\emptyset,$

let $P_{\ell}^{(2)}\subseteq P_{\ell}^{(1)}$ consist of the first
$e-\sum_{1\leq k<\ell}\\#P_{k}^{(1)}$ elements of $P_{\ell}^{(1)}$, and
$E=\bigcup_{1\leq k<\ell}P_{k}^{(1)}\cup P_{\ell}^{(2)}$. Then
$P_{\ell}^{(2)}$ is nonempty and $\\#E=e$.

The equations (2.1) corresponding to $E$ are:

(2.2) $\left\\{\begin{array}[]{ll}h(\alpha_{i_{k}})-h(\alpha_{j})=0&\text{for
}1\leq k<\ell,\,j\in P_{k}^{(1)},\\\
h(\alpha_{i_{\ell}})-h(\alpha_{j})=0&\text{for }j\in
P_{\ell}^{(2)}.\end{array}\right.$

We denote by $j_{0}$ the largest value of $j\in P_{\ell}^{(2)}$. Then these
equations correspond to the following system of $e$ linear equations for the
coefficients of $h$:

(2.3)
$\left(\begin{array}[]{ccccccc}\alpha_{i_{1}}-\alpha_{j}&\cdots&\alpha_{i_{1}}^{e}-\alpha_{j}^{e}\\\
\vdots&&\vdots\\\
\alpha_{i_{\ell}}-\alpha_{j_{0}}&\cdots&\alpha_{i_{\ell}}^{e}-\alpha_{j_{0}}^{e}\\\
\end{array}\right)\left(\begin{array}[]{c}h_{1}\\\ \vdots\\\ h_{e-1}\\\ 1\\\
\end{array}\right)=\left(\begin{array}[]{c}0\\\ \vdots\\\ 0\\\
\end{array}\right),$

where the indices correspond to those of (2.2). In particular, $j$ has the
same value on each line of the matrix, but these values are different for
different lines.

If the coefficient matrix is nonsingular, then the system has no solution $h$,
and thus our assumption about $h$ is contradictory. We can reformulate this by
replacing each occurrence of an $\alpha_{i}$ in the matrix by an indeterminate
$A_{i}$ and letting

(2.4)
$R_{\mathcal{P}}=\text{det}\left(\begin{array}[]{ccccccc}A_{i_{1}}-A_{j}&\cdots&A_{i_{1}}^{e}-A_{j}^{e}\\\
\vdots&&\vdots\\\
A_{i_{\ell}}-A_{j_{0}}&\cdots&A_{i_{\ell}}^{e}-A_{j_{0}}^{e}\\\
\end{array}\right)\in{\mathbb{F}}[\boldsymbol{A}],$

where $\boldsymbol{A}=(A_{1},\ldots,A_{d+e-1})$. Then
$\\#h({\boldsymbol{\alpha}})\geq d$ if
$R_{\mathcal{P}}(\boldsymbol{\alpha})\neq 0$.

We claim that the matrix for $R_{\mathcal{P}}$ is nonsingular. For each of its
rows, there is a value $j$ so that $A_{j}$ occurs on that line and nowhere
else in the matrix, namely as $A_{j},\ldots,A_{j}^{e}$. In a Laplace expansion
of the determinant, the cofactor of $A_{j}^{e}$ is a matrix that also has this
property. There is no cancellation for $A_{j}^{e}$ and inductively, it follows
that $R_{\mathcal{P}}\neq 0$. Its total degree is $\sum_{1\leq i\leq
e}i=e(e+1)/2<e^{2}$.

The partition $\mathcal{P}$ that gives rise to $R_{\mathcal{P}}$ is an
$m$-partition of $\\{1,\ldots,d+e-1\\}$, for some $m<d$. We now describe a
$(d-1)$-partition ${\mathcal{Q}}$ of $\\{1,\ldots,d+e-1\\}$ with
$R_{\mathcal{P}}=R_{{\mathcal{Q}}}$. We let $E^{\prime}=\bigcup_{1\leq
k<\ell}P_{k}\cup\\{i_{\ell}\\}\cup P_{\ell}^{(2)}$. An index
$i\in\\{1,\ldots,d+e-1\\}$ occurs somewhere in the matrix for
$R_{\mathcal{P}}$ if and only if $i\in E^{\prime}$, and
$\\#E^{\prime}=e+\ell$. Thus there are $d+e-1-(e+\ell)=d-1-\ell$ such indices
that do not occur in the matrix. Now ${\mathcal{Q}}$ consists of the blocks
$P_{1},\ldots,P_{\ell-1}$ of ${\mathcal{P}}$, $\\{i_{\ell}\\}\cup
P_{\ell}^{(2)}$, and a singleton $\\{i\\}$ for all
$i\in\\{1,\ldots,d+e-1\\}\setminus E^{\prime}$. Thus ${\mathcal{Q}}$ has
$\ell+d-1-\ell=d-1$ blocks and is a $(d-1)$-partition of
$\\{1,\ldots,d+e-1\\}$. Furthermore, the indices in the added singletons occur
neither in the matrix for $R_{\mathcal{P}}$ nor in that for
$R_{{\mathcal{Q}}}$, so that $R_{\mathcal{P}}=R_{{\mathcal{Q}}}$.

We set

(2.5) $R^{(1)}=\prod_{\mathcal{Q}}R_{\mathcal{Q}},$

where the product runs over all $(d-1)$-partitions ${\mathcal{Q}}$ of
$\\{1,\ldots,d+e-1\\}$. Then the claim of the lemma follows. ∎

For $\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$, let

${\mathcal{C}}_{\boldsymbol{\alpha}}=\\{h=X^{e}+h_{e-1}X^{e-1}+\cdots+h_{1}X\in{\mathbb{F}}[X]\colon\,\\#(h(\boldsymbol{\alpha}))\leq
d\\}.$

We use the polynomial $R^{(2)}$ defined in (2.7) below.

######  Lemma 2.2.

The polynomial $R^{(2)}\in{\mathbb{F}}[\boldsymbol{A}]$ is nonzero and has
degree less than $e^{2}\,(S_{2}(d+e-1,d-1)+S_{2}(d+e-1,d))$. For any
$\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ with
$R^{(2)}(\boldsymbol{\alpha})\neq 0$, we have

$\\#{\mathcal{C}}_{\boldsymbol{\alpha}}=S_{2}(d+e-1,d),$

$\\#h(\boldsymbol{\alpha})=d$ for all
$h\in{\mathcal{C}}_{\boldsymbol{\alpha}}$, and $\alpha_{i}\neq\alpha_{j}$
whenever $1\leq i<j<d+e$.

###### Proof.

Let $\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ with
$R^{(1)}(\boldsymbol{\alpha})\neq 0$, and
$h=X^{e}+h_{e-1}X^{e-1}+\cdots+h_{1}X\in{\mathcal{C}}_{\boldsymbol{\alpha}}$.
Lemma 2.1 implies that $\\#h(\boldsymbol{\alpha})=d$.

We now follow the recipe for proving Lemma 2.1. Now
$\mathcal{P}=(P_{1},\ldots,P_{d})$ is a $d$-partition of
$\\{1,\ldots,d+e-1\\}$, and all instances of (2.1) yield only

$\sum_{1\leq k\leq d}\\#P_{k}^{(1)}=\sum_{1\leq k\leq
d}(\\#P_{k}-1)=\sum_{1\leq k\leq d}\\#P_{k}-d=d+e-1-d=e-1$

linear equations on the coefficients of $h$. Thus (2.3) would provide an
$(e-1)\times e$ system of linear equations. In order to obtain a square
coefficient matrix, we move the quantities corresponding to the last column to
the “constant” side and obtain:

(2.6)
$\left(\begin{array}[]{ccccccc}\alpha_{i_{1}}-\alpha_{j}&\cdots&\alpha_{i_{1}}^{e-1}-\alpha_{j}^{e-1}\\\
\vdots&&\vdots\\\
\alpha_{i_{d}}-\alpha_{j}&\cdots&\alpha_{i_{d}}^{e-1}-\alpha_{j}^{e-1}\\\
\end{array}\right)\left(\begin{array}[]{c}h_{1}\\\ \vdots\\\ h_{e-1}\\\
\end{array}\right)=\left(\begin{array}[]{c}\alpha_{j}^{e}-\alpha_{i_{1}}^{e}\\\
\vdots\\\ \alpha_{j}^{e}-\alpha_{i_{d}}^{e}\\\ \end{array}\right),$

where again the value of $j$ is constant along each row of the matrix, but
different for different rows.

We consider the matrix in ${\mathbb{F}}[\boldsymbol{A}]^{(e-1)\times(e-1)}$,
where each entry $\alpha_{i}$ in the coefficient matrix is replaced by the
indeterminate $A_{i}$ and let $S_{\mathcal{P}}\in{\mathbb{F}}[\boldsymbol{A}]$
be its determinant. By the same argument as for $R_{\mathcal{P}}$ in the
previous proof, also $S_{\mathcal{P}}$ is nonzero. Its degree is
$(e-1)e/2<e^{2}$. If $S_{\mathcal{P}}(\boldsymbol{\alpha})\neq 0$, then the
coefficients of $h$ are uniquely determined by (2.6).

An $h\in{\mathcal{C}}_{\boldsymbol{\alpha}}$ determines its partition
${\mathcal{P}}$ uniquely via (2.1). On the other hand, if
$S_{\mathcal{P}}(\boldsymbol{\alpha})\neq 0$, then (2.6) determines $h$
uniquely. Thus we have a bijection between
${\mathcal{C}}_{\boldsymbol{\alpha}}$ and the set of $d$-partitions of
$\\{1,\ldots,d+e-1\\}$, both finite of size $S_{2}(d+e-1,d)$.

Recalling $R^{(1)}$ from (2.5), we let

(2.7)
$R^{(2)}=R^{(1)}\cdot\prod_{\mathcal{P}}S_{\mathcal{P}}\in{\mathbb{F}}[\boldsymbol{A}],$

where the product runs over the set of $d$-partitions of
$\\{1,\ldots,d+e-1\\}$.

For the last claim, let $1\leq i<j<d+e$ and choose a $d$-partition
$\mathcal{P}$ of $\\{1,\ldots,d+e-1\\}$, one of whose blocks, say $P_{k}$, is
$\\{i,j\\}$. Since $e\geq 2$, there exists a $(d-1)$-partition on the other
$d+e-3\geq d-1$ elements. In the matrix of indeterminates defining
$S_{\mathcal{P}}$, $A_{i}-A_{j}$ divides all entries in the row corresponding
to $P_{k}$, and hence also $S_{\mathcal{P}}$ and $R^{(2)}$ are divisible by
this difference. Thus $\alpha_{i}\neq\alpha_{j}$ whenever
$R^{(2)}(\boldsymbol{\alpha})\neq 0$. The claims of the lemma follow. ∎

The Bell number $B_{n}$ counts the number of all set partitions of a set with
$n$ elements. The estimate in Berend & Tassa [3] yields

$\displaystyle S_{2}(d+e-1,d-1)+S_{2}(d+e-1,d)$ $\displaystyle<$
$\displaystyle B_{d+e-1}<\bigg{(}\frac{d+e-1}{\ln(d+e)}\bigg{)}^{d+e-1},$
(2.8) $\displaystyle\deg R^{(2)}$ $\displaystyle<$ $\displaystyle
e^{2}B_{d+e-1}\leq(d+e)^{d+e-1}.$

For certain $\boldsymbol{\beta}$ with sufficiently few distinct entries, we
can compute a composite interpolation polynomial $f=g\circ h$ with $\deg g=d$,
and the number of such polynomials.

######  Proposition 2.3.

Let $\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ satisfy
$R^{(2)}(\boldsymbol{\alpha})\neq 0$ and $\\#\boldsymbol{\beta}\leq d$. Then
we can compute a solution to Problem 1.1 for
$(\boldsymbol{\alpha},\boldsymbol{\beta})$. All solutions are defined over
${\mathbb{F}}$ and the number of solutions equals the number of
$d$-refinements of ${\mathcal{P}}_{\boldsymbol{\beta}}$.

###### Proof.

We let $\mathcal{P}$ be an arbitrary $d$-refinement of
$\mathcal{P}_{\boldsymbol{\beta}}$, that is,
$\mathcal{P}\preccurlyeq\mathcal{P}_{\bf\beta}$. Solving the nonsingular
system (2.6) of linear equations corresponding to $\mathcal{P}$ provides a
solution $(h_{1},\ldots,h_{e-1})$ with all $h_{i}\in{\mathbb{F}}$, and we set
$h=X^{e}+h_{e-1}X^{e-1}+\cdots+h_{1}X\in{\mathbb{F}}[X]$. Then
$\\#h(\boldsymbol{\alpha})=d$ and for $1\leq k\leq d$, we let $i_{k}\in
P_{k}\subset\\{1,\ldots,d+e-1\\}$ be a representative of the $k$th block
$P_{k}$ of $\mathcal{P}$. The condition that
$g(h(\alpha_{i_{k}}))=\beta_{i_{k}}$ for $k\leq d$ defines a unique monic
interpolation polynomial $g\in{\mathbb{F}}[X]$ of degree $d$, and $(g,h)$ is a
solution to Problem 1.1.

The proof of Lemma 2.2 notes a bijection between the set of $h$ and that of
the above partitions. This implies the claim on the number of solutions. ∎

######  Example 2.4.

For $d=e=2$, we consider the arbitrarily chosen $\boldsymbol{\alpha}=(5,6,7)$
and $\boldsymbol{\beta}=(3,3,3)$. Then
$\mathcal{P}_{\boldsymbol{\beta}}=\\{1,2,3\\}$ has the three 2-refinements
$\\{\\{1,2\\},\\{3\\}\\}$, $\\{\\{1,3\\},\\{2\\}\\}$, and
$\\{\\{2,3\\},\\{1\\}\\}$. We find the corresponding three components
$g=x^{2}+g_{1}x+g_{0}$ and $h=x^{2}+h_{1}x$ with $(g_{1},g_{0},h_{1})$ as

$(58,843,-11),(71,1263,-12),(82,1683,-13)$

and their compositions $f=g\circ h$ as

$\displaystyle
x^{4}-22x^{3}+179x^{2}-638x+843,x^{4}-24x^{3}+215x^{2}-852x+1263,$
$\displaystyle x^{4}-26x^{3}+251x^{2}-1066x+1683.$

This works over any field ${\mathbb{F}}$ with $\text{char}\ {\mathbb{F}}\neq
2$. ${\mathbb{F}}_{2}$ does not have enough elements for such an example, but
${\mathbb{F}}_{4}={\mathbb{F}}_{2}[y]/(y^{2}+y+1)$ does. For
$\boldsymbol{\alpha}=(0,1,y)$ and $\boldsymbol{\beta}=(y+1,y+1,y+1)$, we find
the following three coefficient vectors of components $(g,h)$:

$(1,y+1,1),(y+1,y+1,y),(y,y+1,y+1)$

For all three, the composition is $f=x^{4}+x+y+1$. This is a _composition
collision_ of a type which is classified in Blankertz et al. [5]. ∎

######  Corollary 2.5.

For an $\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ with $R^{(2)}\neq 0$, the
set of solutions $(g,h)$ to Problem 1.1 for
$(\boldsymbol{\alpha},\boldsymbol{0})$ is finite of cardinality
$S_{2}(d+e-1,d)$ and all solutions are defined over ${\mathbb{F}}$. For such a
solution, we have $\\#h(\boldsymbol{\alpha})=d$.

###### Proof.

${\mathcal{P}}_{\boldsymbol{0}}$ is the maximum partition in the lattice of
partitions, $\\#{\mathcal{P}}_{\boldsymbol{0}}=1$, and it has $S_{2}(d+e-1,d)$
many $d$-refinements. ∎

##  3\. The number of interpolants

We have shown with methods from linear algebra how to solve the interpolation
problem for special $\boldsymbol{\beta}$. The general case requires tools from
algebraic geometry. We use notions like varieties and morphism only over
algebraically closed fields, but they may be “defined over” some smaller field
${\mathbb{F}}$ with algebraic closure $\overline{{\mathbb{F}}\\!}{\,}$.
Standard notions and notations of algebraic geometry can be found in, e.g.,
Kunz [25] or Shafarevich [30].

We now set some notation for the decomposable polynomials as in (1.1). We may
assume all three polynomials to be monic (leading coefficient 1) and $h$
original (constant coefficient 0, so that the graph contains the origin). All
other compositions can be obtained from this special case by composing (on the
left and on the right) with linear polynomials (polynomials of degree 1); see,
e.g., von zur Gathen [13].

Thus we consider for a proper divisor $d$ of $n$ and $e=n/d$

$\displaystyle P_{n}({\mathbb{F}})=$
$\displaystyle\;\\{f\in{{\mathbb{F}}}[X]\colon\deg f=n,f\text{ monic}\\},$
$\displaystyle P_{e}^{*}({\mathbb{F}})=$ $\displaystyle\;\\{h\in
P_{e}({\mathbb{F}})\colon h\text{ original}\\},$ (3.1)
$\displaystyle\gamma_{n,d}\colon$ $\displaystyle P_{d}({\mathbb{F}})\times
P_{e}^{*}({\mathbb{F}})\rightarrow P_{n}({\mathbb{F}})\text{ with
}\gamma_{n,d}(g,h)=g\circ h,$ $\displaystyle C_{n,d}({\mathbb{F}})=$
$\displaystyle\;\\{f\in P_{n}({\mathbb{F}})\colon\exists\,g,h\in
P_{d}({\mathbb{F}})\times P_{e}^{*}({\mathbb{F}})\;\;f=g\circ h\\}$
$\displaystyle=$ $\displaystyle\;\text{im }\gamma_{n,d},$ $\displaystyle
C_{n}({\mathbb{F}})=$ $\displaystyle\bigcup_{{d\mid
n}\atop{d\not\in\\{1,n\\}}}C_{n,d}({\mathbb{F}}).$

We may endow $P_{n}({\mathbb{F}})$ with a structure of $n$-dimensional vector
space over ${\mathbb{F}}$, associating each
$f=X^{n}+f_{n-1}X^{e-1}+\cdots+f_{0}$ with the vector
$(f_{n-1},\ldots,f_{0})$, and $C_{n}({\mathbb{F}})$ is the algebraic variety
of decomposable polynomials. We drop the argument ${\mathbb{F}}$ when it is
clear from the context. When $n$ is prime, then $C_{n}({\mathbb{F}})$ is
empty, and in the following we always assume $n$ to be composite. We have the
following geometric description of $C_{n,d}$.

######  Fact 3.1 (von zur Gathen & Matera [15, Theorem 2.2]).

Let $d$ be a proper divisor of $n$ and ${\mathbb{F}}$ be an algebraically
closed field with $\text{char}({\mathbb{F}})$ not dividing $d$. Then
$C_{n,d}({\mathbb{F}})=~{}\mathrm{im}\ \gamma_{n,d}$ as in (3) is a closed
irreducible algebraic subvariety of $P_{n}({\mathbb{F}})$ of dimension $d+e-1$
and degree at most $d^{d+e-1}$.

In all of the following, we assume that $\text{char}({\mathbb{F}})$ does not
divide $d$. Our goal is to show that Problem 1.1 has an affirmative answer for
a suitably generic instance
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$,
namely there exists an interpolation polynomial in $C_{n,d}$. For this
purpose, we introduce the following incidence variety:

(3.2) $\Gamma_{n,d}=\\{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})\in
P_{d}(\overline{{\mathbb{F}}\\!}{\,})\times
P_{e}^{*}(\overline{{\mathbb{F}}\\!}{\,})\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\colon
g\circ h(\boldsymbol{\alpha})=\boldsymbol{\beta}\\}.$

We have the following result.

######  Lemma 3.2.

$\Gamma_{n,d}$ is defined over ${\mathbb{F}}$, irreducible of dimension
$2(d+e-1)$ and degree at most $n^{d+e-1}$.

###### Proof.

Let $\boldsymbol{A}=(A_{1},\ldots,A_{d+e-1})$,
$\boldsymbol{B}=(B_{1},\ldots,B_{d+e-1})$,
$\boldsymbol{G}=(G_{d-1},\ldots,G_{0})$ and
$\boldsymbol{H}=(H_{e-1},\ldots,H_{1})$ be vectors of indeterminates over
$\overline{{\mathbb{F}}\\!}{\,}$. We denote by $\boldsymbol{A}$ and
$\boldsymbol{B}$ the coordinates of
$\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$,
and by $\boldsymbol{G}$ and $\boldsymbol{H}$ the coordinates of
$P_{d}(\overline{{\mathbb{F}}\\!}{\,})\times
P_{e}^{*}(\overline{{\mathbb{F}}\\!}{\,})$. Let
$G,H\in{\mathbb{F}}[\boldsymbol{G},\boldsymbol{H},X]$ be the polynomials

$G=X^{d}+G_{d-1}X^{d-1}+\cdots+G_{0},\quad
H=X^{e}+H_{e-1}X^{e-1}+\cdots+H_{1}X,$

and consider the ${\mathbb{F}}$-algebra morphism

$\Phi\colon{\mathbb{F}}[\boldsymbol{A},\boldsymbol{B},\boldsymbol{G},\boldsymbol{H}]\to{\mathbb{F}}[\boldsymbol{A},\boldsymbol{G},\boldsymbol{H}]$

defined by $\Phi(B_{i})=(G\circ H)(A_{i})$ for $1\leq i\leq d+e-1$. It is
clear that $\Phi$ is surjective, and its kernel is

$\displaystyle\mathrm{ker}\,\Phi$ $\displaystyle=\langle B_{1}-(G\circ
H)(A_{1}),\ldots,B_{d+e-1}-(G\circ
H)(A_{d+e-1})\rangle=\mathcal{I}(\Gamma_{n,d}),$

where
$\mathcal{I}(\Gamma_{n,d})\subset{\mathbb{F}}[\boldsymbol{A},\boldsymbol{B},\boldsymbol{G},\boldsymbol{H}]$
denotes the ideal of polynomials vanishing on $\Gamma_{n,d}$. It follows that

$\overline{\Phi}:{\mathbb{F}}[\boldsymbol{A},\boldsymbol{B},\boldsymbol{G},\boldsymbol{H}]/\mathcal{I}(\Gamma_{n,d})\to{\mathbb{F}}[\boldsymbol{A},\boldsymbol{G},\boldsymbol{H}]$

is an isomorphism. Since
${\mathbb{F}}[\boldsymbol{A},\boldsymbol{G},\boldsymbol{H}]$ is a domain,
$\Gamma_{n,d}$ is irreducible, and its dimension agrees with the Krull
dimension of ${\mathbb{F}}[\boldsymbol{A},\boldsymbol{G},\boldsymbol{H}]$,
namely $2(d+e-1)$.

Since $\Gamma_{n,d}$ is defined by $d+e-1$ equations of degree at most $n=de$,
the Bézout inequality (see, e.g., Heintz [18] or Fulton [11]) implies the
claimed upper bound on its degree. ∎

We have a natural projection

(3.3)
$\pi\colon\Gamma_{n,d}\to\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}.$

In these terms, Problem 1.1 can be rephrased as follows:

######  Problem 3.3.

Given
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{d+e-1})\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
with $\alpha_{i}\not=\alpha_{j}$ for $i\not=j$, and
$\boldsymbol{\beta}=(\beta_{1},\ldots,\beta_{d+e-1})\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$,
is the fiber $\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})$ nonempty?

Our next result shows that Problem 3.3 has a positive answer for most
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$.

######  Corollary 3.4.

The projection mapping
$\pi\colon\Gamma_{n,d}\to\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
is dominant. In particular, if $R^{(2)}(\boldsymbol{\alpha})\neq 0$, then the
fiber $\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})$ is of dimension zero.

###### Proof.

Lemma 3.2 shows that $\Gamma_{n,d}$ is irreducible of dimension $2(d+e-1)$.
Consider $\pi\colon\Gamma_{n,d}\to\overline{\pi(\Gamma_{n,d})}$ and observe
that both $\Gamma_{n,d}$ and $\overline{\pi(\Gamma_{n,d})}$ are irreducible
varieties, where $\overline{\pi(\Gamma_{n,d})}$ is the Zariski closure of
$\pi(\Gamma_{n,d})$ in
$\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$.
For an $\boldsymbol{\alpha}\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$ with
$R^{(2)}(\boldsymbol{\alpha})\neq 0$, the fiber
$\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{0})$ has dimension zero by Corollary
2.5. Therefore, the theorem on the dimension of fibers (see, e.g., [30, §6.3,
Theorem 7]) shows that

$2(d+e-1)-\dim\overline{\pi(\Gamma_{n,d})}=\dim\Gamma_{n,d}-\dim\overline{\pi(\Gamma_{n,d})}\leq
0.$

It follows that $2(d+e-1)\leq\dim\overline{\pi(\Gamma_{n,d})}$, that is,
$\overline{\pi(\Gamma_{n,d})}=\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$.
This proves the first assertion. Finally, taking into account that
$\Gamma_{n,d}$ and
$\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
are both irreducible varieties of dimension $2(d+e-1)$, the second assertion
is a standard consequence of the theorem on the dimension of fibers. ∎

We may paraphrase the statement of Corollary 3.4 in terms of the interpolation
problem in the following way: for any
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ with
$R^{(2)}(\boldsymbol{\alpha})\neq 0$, there is a finite positive number of
solutions $f=g\circ h\in C_{n,d}$ to the interpolation problem defined by
$(\boldsymbol{\alpha},\boldsymbol{\beta})$. Now we discuss the possible number
of interpolants.

Since the projection

$\pi\colon\Gamma_{n,d}\to\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$

is a dominant mapping defined over ${\mathbb{F}}$, it induces a finite field
extension
${\mathbb{F}}(\boldsymbol{A},\boldsymbol{B})\hookrightarrow{\mathbb{F}}(\Gamma_{n,d})$
between the fields of rational functions on
$\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
and on $\Gamma_{n,d}$ defined over ${\mathbb{F}}$. The degree of this field
extension is the degree of the morphism $\pi$ and is denoted by $\deg\pi$.

Assume that the field extension
${\mathbb{F}}(\boldsymbol{A},\boldsymbol{B})\hookrightarrow{\mathbb{F}}(\Gamma_{n,d})$
is separable (in Proposition 3.7 below we prove this assertion). By, e.g.,
[18, Proposition 1],
$\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})\leq\deg\pi$ for any
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
with a finite fiber, with equality in a Zariski open subset of
$\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$.
In particular, from Corollary 2.5 we deduce that

$\deg\pi\geq S_{2}({d+e-1,d}).$

We also have an easy upper bound.

######  Lemma 3.5.

We have $\deg\pi\leq\deg C_{n,d}\leq d^{d+e-1}$.

###### Proof.

Let
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
with $\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$. Then
$\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})$ is isomorphic to the zero-
dimensional variety

$\\{f\in C_{n,d}\colon f(\alpha_{i})=\beta_{i}\ \text{ for }1\leq i\leq
d+e-1\\},$

which is the intersection of $C_{n,d}$ with an affine linear subspace of
$\overline{{\mathbb{F}}\\!}{\,}^{n}$. The Bézout inequality (see, e.g., [18]
or [11]) implies the first inequality, and the second one follows from Theorem
3.1. ∎

Corollary 2.5 and Lemma 3.5 imply that

(3.4) $S_{2}({d+e-1,d})\leq\deg\pi\leq d^{d+e-1}.$

To compare both sides of the inequality, we recall that $d!\,S_{2}(d+e-1,d)$
is the number of surjective functions from $\\{1,\ldots,d+e-1\\}$ to
$\\{1,\ldots,d\\}$ (see, e.g., Mezö [26, page 17]), while $d^{d+e-1}$ is the
total number of functions from $\\{1,\ldots,d+e-1\\}$ to $\\{1,\ldots,d\\}$.

Next we want to show that
$\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$ for most inputs.
For this purpose, we have to understand the ramification locus of the
projection
$\pi\colon\Gamma_{n,d}\to\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
and the separability of the corresponding field extension. For
$(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})\in\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})$,
$\pi$ is unramified at $(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})$ if the
differential mapping
$d_{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}\pi\colon
T_{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}\Gamma_{n,d}\to
T_{(\boldsymbol{\alpha},\boldsymbol{\beta})}(\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1})$
is injective.

Since the polynomials $Q_{i}=(G\circ H)(A_{i})-B_{i}$ with $1\leq i\leq d+e-1$
defining the incidence variety $\Gamma_{n,d}$ generate a radical ideal, it
follows that the tangent space
$T_{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}$ of any
$(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})\in\Gamma_{n,d}$ is the kernel of
the Jacobian matrix
$(\partial\boldsymbol{Q}/(\partial(\boldsymbol{G},\boldsymbol{H},\boldsymbol{A},\boldsymbol{B}))(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})$
of $\boldsymbol{Q}=(Q_{1},\ldots,Q_{d+e-1})$ with respect to
$\boldsymbol{G},\boldsymbol{H},\boldsymbol{A},\boldsymbol{B}$ at
$(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})$. Since $\pi$ is the linear
mapping defined by the projection to
$\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$,
it is unramified at $(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})$ if and only
if the Jacobian matrix
$((\partial\boldsymbol{Q})/(\partial(\boldsymbol{G},\boldsymbol{H}))(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})$
is of full rank.

Our first result considers the special case
$(\boldsymbol{\alpha},\boldsymbol{0})$.

######  Lemma 3.6.

For an $\boldsymbol{\alpha}$ with $R^{(2)}(\boldsymbol{\alpha})\neq 0$, $\pi$
is unramified at any point
$(g,h,\boldsymbol{\alpha},\boldsymbol{0})\in\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{0})$.

###### Proof.

We let $q=d+e-1$ and consider the $q\times q$ Jacobian matrix
$J=(\partial\boldsymbol{Q}/(\partial(\boldsymbol{G},\boldsymbol{H}))(g,h,\boldsymbol{\alpha},\boldsymbol{0})$:

(3.5)
$J=\left(\begin{array}[]{ccccccc}h(\alpha_{1})^{d-1}&\cdots&h(\alpha_{1})&\\!\\!1\\!\\!&g^{\prime}(h(\alpha_{1}))\,\alpha_{1}^{e-1}&\cdots&g^{\prime}(h(\alpha_{1}))\,\alpha_{1}\\\
\vdots&&\vdots&\\!\\!\vdots\\!\\!&\vdots&&\vdots\\\
h(\alpha_{d})^{d-1}&\cdots&h(\alpha_{d})&\\!\\!1\\!\\!&g^{\prime}(h(\alpha_{d}))\,\alpha_{d}^{e-1}&\cdots&g^{\prime}(h(\alpha_{d}))\,\alpha_{d}\\\\[4.30554pt]
h(\alpha_{d+1})^{d-1}&\cdots&h(\alpha_{d+1})&\\!\\!1\\!\\!&g^{\prime}(h(\alpha_{d+1}))\,\alpha_{d+1}^{e-1}\\!\\!&\cdots&\\!\\!g^{\prime}(h(\alpha_{d+1}))\,\alpha_{d+1}\\\
\vdots&&\vdots&\\!\\!\vdots\\!\\!&\vdots&&\vdots\\\
h(\alpha_{q})^{d-1}&\cdots&h(\alpha_{q})&\\!\\!1\\!\\!&g^{\prime}(h(\alpha_{q}))\,\alpha_{q}^{e-1}&\cdots&g^{\prime}(h(\alpha_{q}))\,\alpha_{q}\end{array}\right).$

From Corollary 2.5 we have $\\#h(\boldsymbol{\alpha})=d$ and by Lemma 2.2 that
$h(\alpha_{i})\not=h(\alpha_{j})$ for $1\leq i<j\leq d$, while each of the
remaining values $h(\alpha_{d+j})$ agrees with an $h(\alpha_{i_{j}})$ with
$1\leq i_{j}\leq d$ for $1\leq j\leq e-1$. As a consequence, the upper-left
$d\times d$ submatrix $J_{1}$ of $J$ is invertible. Further, by subtracting
the $i_{j}$th row from the $(d+j)$th row of $J$ for $1\leq j\leq e-1$, we
obtain a $q\times q$ matrix with the same rank as $J$ and of the following
shape:

$\left(\begin{array}[]{c|c}J_{1}&*\\\
\hline\cr\boldsymbol{0}&\begin{array}[]{ccc}g^{\prime}(h(\alpha_{d+1}))\,(\alpha_{d+1}^{e-1}-\alpha_{i_{1}}^{e-1})&\cdots&g^{\prime}(h(\alpha_{d+1}))\,(\alpha_{d+1}-\alpha_{i_{1}})\\\\[4.30554pt]
\vdots&&\vdots\\\
g^{\prime}(h(\alpha_{q}))(\alpha_{q}^{e-1}-\alpha_{i_{e-1}}^{e-1})&\cdots&g^{\prime}(h(\alpha_{q}))(\alpha_{q}-\alpha_{i_{e-1}})\end{array}\end{array}\right).$

It follows that $J$ is invertible if and only if this $(e-1)\times(e-1)$
lower-right submatrix $J_{2}$ is invertible.

Since $g$ is monic polynomial of degree $d$ vanishing on
$h(\boldsymbol{\alpha})$ and $\\#h(\boldsymbol{\alpha})=d$, any
$h(\alpha_{i})$ is a simple root of $g$. This implies that
$g^{\prime}(h(\alpha_{d+i}))\not=0$ for $1\leq i\leq e-1$. We conclude that
$J_{2}$ is invertible if and only if the matrix

$J_{3}=\left(\begin{array}[]{ccc}\alpha_{d+1}^{e-1}-\alpha_{i_{1}}^{e-1}&\cdots&\alpha_{d+1}-\alpha_{i_{1}}\\\\[4.30554pt]
\vdots&&\vdots\\\
\alpha_{q}^{e-1}-\alpha_{i_{e-1}}^{e-1}&\cdots&\alpha_{q}-\alpha_{i_{e-1}}\end{array}\right)$

is nonsingular. Up to row and column permutations and signs, $J_{3}$ is the
matrix in (2.6). (In the numbering of (2.6), $d+j$ is in the same block of the
partition as $i_{j}$.) Since $R^{(2)}(\boldsymbol{\alpha})\neq 0$, it follows
that $J_{3}$ is nonsingular. ∎

In fact, the lemma’s statement and proof are valid for any
$\boldsymbol{\beta}$ with $\\#\boldsymbol{\beta}\leq d$, not just
$\boldsymbol{\beta}=\boldsymbol{0}$, using Proposition 2.3 instead of
Corollary 2.5.

Next we show that the field extension
${\mathbb{F}}(\boldsymbol{A},\boldsymbol{B})\hookrightarrow{\mathbb{F}}(\Gamma_{n,d})$
is separable. This will show that
$\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$ for any suitably
generic $(\boldsymbol{\alpha},\boldsymbol{\beta})$.

######  Proposition 3.7.

The field extension
${\mathbb{F}}(\boldsymbol{A},\boldsymbol{B})\hookrightarrow{\mathbb{F}}(\Gamma_{n,d})$
is separable.

###### Proof.

The Jacobian
$\boldsymbol{J}=\partial\boldsymbol{Q}/\partial(\boldsymbol{G},\boldsymbol{H})\in{\mathbb{F}}[\boldsymbol{G},\boldsymbol{H},\boldsymbol{A}]^{q\times
q}$ is the matrix in (3.5) with $g,h,\alpha$ replaced by vectors of
indeterminates $\boldsymbol{G},\boldsymbol{H},\boldsymbol{A}$. Lemma 3.6 shows
that $\det\boldsymbol{J}$ does not vanish at certain points, so in particular
$\det\boldsymbol{J}\neq 0$ as a polynomial.

In the proof of Lemma 3.2 it is shown that the ${\mathbb{F}}$-algebra morphism
$\overline{\Phi}\colon{\mathbb{F}}[\Gamma_{n,d}]\to{\mathbb{F}}[\boldsymbol{A},\boldsymbol{G},\boldsymbol{H}]$,
defined by $\overline{\Phi}(\overline{B}_{j})=(G\circ H)(A_{j})$ for $1\leq
j\leq d+e-1$, where
$\overline{B}_{j}\in{\mathbb{F}}[\Gamma_{n,d}]={\mathbb{F}}[\boldsymbol{A},\boldsymbol{B},\boldsymbol{G},\boldsymbol{H}]/\mathcal{I}(\Gamma_{n,d})$
is the coordinate function of $\Gamma_{n,d}$ defined by $B_{j}$, is an
isomorphism. As $\det\boldsymbol{J}$ is a nonzero element of
${\mathbb{F}}[\boldsymbol{A},\boldsymbol{G},\boldsymbol{H}]$, we have
$\overline{\Phi}^{-1}(\det{\boldsymbol{J}})\not=0$, and the fact that
${\mathbb{F}}[\Gamma_{n,d}]$ is a domain implies that
$\overline{\Phi}^{-1}(\det{\boldsymbol{J}})$ is not a zero divisor of
${\mathbb{F}}[\Gamma_{n,d}]$. As a consequence,
$\Gamma_{n,d}\cap\\{\det{\boldsymbol{J}}\not=0\\}$ is a nonempty Zariski open
subset of $\Gamma_{n,d}$. In particular, the projection
$\pi:\Gamma_{n,d}\to\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
is unramified at any
$(\boldsymbol{g},\boldsymbol{h},\boldsymbol{\alpha},\boldsymbol{\beta})$ in
this set.

According to Iversen [21, Proposition T.8], the extension
${\mathbb{F}}(\boldsymbol{A},\boldsymbol{B})\hookrightarrow{\mathbb{F}}(\Gamma_{n,d})$
is separable if and only if
$\pi\colon\Gamma_{n,d}\to\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
is unramified in a nonempty Zariski open subset of $\Gamma_{n,d}$, which
proves the proposition. ∎

Now [18, Proposition 1] shows that
$\deg\pi=\max\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})$, where the
maximum is taken among all fibers with finite cardinality, and there exists a
nonempty Zariski open subset of
$\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
such that $\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$ for
all its elements. Schost [29, Proposition 3] and its proof allow to describe
more precisely an open subset for the condition that
$\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$.

######  Fact 3.8.

There exists a nonzero polynomial
$R^{(3)}\in{\mathbb{F}}[\boldsymbol{A},\boldsymbol{B}]$ of total degree at
most $2\deg\pi\deg\Gamma_{n,d}$ with the following property: for any
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
with $R^{(3)}(\boldsymbol{\alpha},\boldsymbol{\beta})\not=0$, we have
$\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$.

We have introduced two polynomial conditions on $\boldsymbol{\alpha}$:
$R^{(2)}$ in (2.7) and $R^{(3)}$ in the previous fact. We now combine them
into a single polynomial:

(3.6) $R=R^{(2)}R^{(3)}.$

Then $R\in{\mathbb{F}}[\boldsymbol{A}]$ is nonzero and from (2), (3.4), and
Lemma 3.2, we have

(3.7) $\deg R<(d+e)^{d+e-1}+2(d^{2}e)^{d+e-1}\leq 3(d^{2}e)^{d+e-1}.$

######  Definition 3.9.

For $d,e\geq 2$ and a field ${\mathbb{F}}$, we call
$\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ _generic_ if
$R(\boldsymbol{\alpha})\neq 0$, and the nonempty Zariski-open set
$\mathcal{U}=\\{R\neq 0\\}\subset{\mathbb{F}}^{d+e-1}$ consists of these
generic $\boldsymbol{\alpha}$. For any
$\boldsymbol{\beta}\in{\mathbb{F}}^{d+e-1}$, we also call
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ _generic_.

We can now give a criterion under which $\pi$ is unramified.

######  Lemma 3.10.

Let
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$
be generic. Then $\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$
and $\pi$ is unramified at all
$(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})\in\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})$.

###### Proof.

From Fact 3.8, we know that
$\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$. Thus the
restriction
$\pi|_{\pi^{-1}(\mathcal{U})}\colon\pi^{-1}(\mathcal{U})\to\mathcal{U}$ is a
finite morphism. Then for any
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in\mathcal{U}$, the Principle of
conservation of number (see, e.g., Danilov [9, §5.7]) asserts that

$\deg\pi=\sum_{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})\in\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})}\deg_{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}\pi,$

where

$\deg_{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}\pi=\dim_{\mathbb{F}}(\mathcal{O}_{\Gamma_{n,d},(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}/\pi^{*}(\mathfrak{m}_{(\boldsymbol{\alpha},\boldsymbol{\beta})})\mathcal{O}_{\Gamma_{n,d},(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}),$

$\mathcal{O}_{\Gamma_{n,d},(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}$ is
the local ring of rational functions on $\Gamma_{n,d}$ defined over
${\mathbb{F}}$ which are well-defined at
$(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})$ and
$\mathfrak{m}_{(\boldsymbol{\alpha},\boldsymbol{\beta})}$ is the maximal ideal
of rational functions on
$\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}\times\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$,
defined over ${\mathbb{F}}$ and vanishing at
$(\boldsymbol{\alpha},\boldsymbol{\beta})$.

Now the fact that
$\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$ implies that
$\deg_{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}\pi=1$ for any
$(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})\in\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})$.
This means that
$\mathcal{O}_{\Gamma_{n,d},(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}/\pi^{*}(\mathfrak{m}_{(\boldsymbol{\alpha},\boldsymbol{\beta})})\mathcal{O}_{\Gamma_{n,d},(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}$
is isomorphic to ${\mathbb{F}}$. It follows that

$\pi^{*}(\mathfrak{m}_{(\boldsymbol{\alpha},\boldsymbol{\beta})})=\mathfrak{m}_{(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})}$

for all the points
$(g,h,\boldsymbol{\alpha},\boldsymbol{\beta})\in\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})$,
which by, e.g., [9, §5.2], implies that $\pi$ is unramified at all such
points. ∎

##  4\. Homotopy for interpolation

Our general task is to find composite interpolating polynomials for given
generic
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in{\mathbb{F}}^{d+e-1}\times{\mathbb{F}}^{d+e-1}$,
where $\text{char}({\mathbb{F}})$ does not divide $d$. Corollary 2.5 provides
a solution for the special value $\boldsymbol{\beta}=\boldsymbol{0}$. Our main
tool is a homotopy connecting these two instances.

Recall that the interpolants for
$(\boldsymbol{\alpha},\boldsymbol{\beta})=(\alpha_{1},\ldots,\alpha_{d+e-1},\beta_{1},\ldots,\beta_{d+e-1})$
are the common zeros $(g,h)$ of the polynomial system

(4.1) $(G\circ H)(\alpha_{i})-\beta_{i}=0\quad\text{ for }1\leq i\leq d+e-1,$

where $G=X^{d}+G_{d-1}X^{d-1}+\cdots+G_{0}$ and
$H=X^{e}+H_{e-1}X^{e-1}+\cdots+H_{1}X$ are univariate polynomials in $X$ with
$d+e-1$ indeterminate coefficients $G_{d-1},\ldots,G_{0}$ and
$H_{e-1},\ldots,H_{1}$. The deformation describing the homotopy is the variety
$V^{*}\subset\overline{{\mathbb{F}}\\!}{\,}^{d+e}$, defined over
${\mathbb{F}}$ and determined by the equations

(4.2) $(G\circ H)(\alpha_{i})-\beta_{i}S=0\quad\text{ for }1\leq i\leq d+e-1.$

Here, $S$ is a parameter whose values range over
$\overline{{\mathbb{F}}\\!}{\,}$. For $S=0$, we have the special problem
already solved, and $S=1$ is our general task. More precisely, we shall be
interested in a curve $V\subset V^{*}$ which consists of certain irreducible
components over ${\mathbb{F}}$ of the variety $V^{*}$. Since each equation in
(4.2) has degree at most $d$, the Bézout inequality then implies that

(4.3) $\delta=\deg V\leq\deg V^{*}\leq d^{d+e-1}.$

The algorithm solving system (4.1) may be divided into three main parts.
First, we compute a bivariate polynomial $m_{i}(S,T)$ defining an irreducible
plane curve birationally equivalent to an irreducible component of $V$. Then
we extend the computation of the polynomial $m_{i}(S,T)$ to the computation of
the birational inverse itself. Finally, we substitute 1 for $S$ in the
birational inverse computed in the previous step and recover at least one
solution to system (4.1). We use a representation of varieties called a
geometric solution or a rational univariate representation which is well
suited for algorithmic purposes (see, e.g., Rouillier [28], Giusti et al.
[17]).

###  4.1. Geometric solutions

Let $X_{1},\ldots,X_{n}$ be indeterminates over ${\mathbb{F}}$ and denote
$\boldsymbol{X}=(X_{1},\ldots,X_{n})$. We start with the definition of a
geometric solution of a zero-dimensional variety defined over ${\mathbb{F}}$.
Let
$V=\\{\boldsymbol{P}_{1},\ldots,\boldsymbol{P}_{D}\\}\subset\overline{{\mathbb{F}}\\!}{\,}^{n}$
be a zero-dimensional reduced variety defined over ${\mathbb{F}}$, and
$\mathcal{L}\in{\mathbb{F}}[\boldsymbol{X}]$ a linear form which separates the
points of $V$, that is,
$\mathcal{L}(\boldsymbol{P}_{i})\neq\mathcal{L}(\boldsymbol{P}_{j})$ for
$i\neq j$. A _geometric solution_ of $V$ consists of

  * •

$\boldsymbol{\lambda}\in{\mathbb{F}}^{n}$ so that the linear form
$\mathcal{L}=\boldsymbol{\lambda}\cdot\boldsymbol{X}=\lambda_{1}X_{1}+\cdots+\lambda_{n}X_{n}\in{\mathbb{F}}[\boldsymbol{X}]$
separates the points of $V$,

  * •

the minimal polynomial $m_{\boldsymbol{\lambda}}=\prod_{1\leq i\leq
D}(T-\mathcal{L}(\boldsymbol{P}_{i}))\in{\mathbb{F}}[T]$ of $\mathcal{L}$ in
$V$, where $T$ is a new variable,

  * •

polynomials $w_{1},\dots,w_{n}\in{\mathbb{F}}[T]$ with $\deg w_{j}<D$ for
$1\leq j\leq n$ such that

$V=\\{(w_{1}(\eta),\dots,w_{n}(\eta))\in\overline{{\mathbb{F}}\\!}{\,}^{n}\colon\,\eta\in\overline{{\mathbb{F}}\\!}{\,},\,m_{\boldsymbol{\lambda}}(\eta)=0\\}.$

Thus
$\boldsymbol{P}_{i}=\big{(}w_{1}(\mathcal{L}(\boldsymbol{P}_{i})),\ldots,w_{n}(\mathcal{L}(\boldsymbol{P}_{i})\big{)}$
for $1\leq i\leq D$, and each $w_{j}$ interpolates on $D$ pairwise distinct
points
$\mathcal{L}(\boldsymbol{P}_{1}),\ldots,\mathcal{L}(\boldsymbol{P}_{D})$.

Next, we consider this notion for equidimensional varieties of dimension one,
that is, for curves, defined over ${\mathbb{F}}$. Let $n\geq 2$,
$V\subset\overline{{\mathbb{F}}\\!}{\,}^{n}$ be a reduced variety defined over
${\mathbb{F}}$ of pure dimension $1$ and degree $\delta$, and let
$V=V_{1}\cup\cdots\cup V_{t}$ be the decomposition over ${\mathbb{F}}$ of $V$
into irreducible components. Suppose that the indeterminate $X_{1}$ forms a
separable transcendence basis of all field extensions
${\mathbb{F}}\hookrightarrow{\mathbb{F}}(V_{i})$ for $1\leq i\leq t$, that is,
each ${\mathbb{F}}(X_{1})\hookrightarrow{\mathbb{F}}(V_{i})$ is a finite
separable field extension. Denote by $D_{i}$ its degree and let $D=\sum_{1\leq
i\leq t}D_{i}$. In particular, the linear projection
$\pi:V_{i}\to\overline{{\mathbb{F}}\\!}{\,}^{1}$ defined by
$\pi(\boldsymbol{x})=x_{1}$ is a dominant morphism of degree $D_{i}$ for
$1\leq i\leq t$. The behavior of the degree of a variety under linear maps
(see, e.g., [18, Lemma 2]) implies that

(4.4) $D=\sum_{1\leq i\leq t}D_{i}\leq\sum_{1\leq i\leq t}\deg V_{i}=\delta.$

Let $\boldsymbol{\Lambda}=(\Lambda_{2},\ldots,\Lambda_{n})$ be a vector of new
indeterminates. The extension $V_{{\mathbb{F}}(\boldsymbol{\Lambda})}$ of $V$
to $\overline{{\mathbb{F}}(\boldsymbol{\Lambda})}{}^{n}$ is a variety of pure
dimension $1$ and its coordinate ring is isomorphic to
${\mathbb{F}}(\boldsymbol{\Lambda})\otimes_{{\mathbb{F}}}{\mathbb{F}}[V]$.
Consider the generic linear form

(4.5)
$\mathcal{L}_{\boldsymbol{\Lambda}}=\boldsymbol{\Lambda}\cdot\boldsymbol{X}^{*}=\Lambda_{2}X_{2}+\cdots+\Lambda_{n}X_{n}.$

As the mapping
${\mathbb{F}}[V]\to{\mathbb{F}}[V_{1}]\times\cdots\times{\mathbb{F}}[V_{t}]$
defined by $\xi\mapsto(\xi|_{V_{1}},\ldots,\xi|_{V_{t}})$ is an isomorphism of
${\mathbb{F}}$-algebras, we identify ${\mathbb{F}}[V]$ with
${\mathbb{F}}[V_{1}]\times\cdots\times{\mathbb{F}}[V_{t}]$. For
$\xi\in{\mathbb{F}}[V]$, we denote its restriction to $V_{i}$ by $\xi^{(i)}$
for $1\leq i\leq t$. Let $\xi_{1},\ldots,\xi_{n}\in{\mathbb{F}}[V]$ be the
coordinate functions of $V$ induced by $X_{1},\ldots,X_{n}$, and set
$\widehat{\mathcal{L}}=\mathcal{L}_{\boldsymbol{\Lambda}}(\xi_{2},\ldots,\xi_{n})\in{\mathbb{F}}(\boldsymbol{\Lambda})\otimes_{{\mathbb{F}}}{\mathbb{F}}[V]$.
Since $\xi_{1}^{(i)}$ and $\widehat{\mathcal{L}}^{(i)}$ are algebraically
dependent over ${\mathbb{F}}(\boldsymbol{\Lambda})$, there exists an
irreducible polynomial
$m_{\boldsymbol{\Lambda}}^{(i)}\in{\mathbb{F}}[\boldsymbol{\Lambda},X_{1},T]$,
separable with respect to $T$, such that
$m_{\boldsymbol{\Lambda}}^{(i)}(\boldsymbol{\Lambda},\xi_{1}^{(i)},\widehat{\mathcal{L}}^{(i)})=0$
holds in
${\mathbb{F}}(\boldsymbol{\Lambda})\otimes_{{\mathbb{F}}}{\mathbb{F}}[V_{i}]$
for $1\leq i\leq t$. These polynomials are pairwise relatively prime, and
defining

$m_{\boldsymbol{\Lambda}}=\prod_{1\leq i\leq
t}m_{\boldsymbol{\Lambda}}^{(i)},$

we find the following identity in
${\mathbb{F}}(\boldsymbol{\Lambda})\otimes_{{\mathbb{F}}}{\mathbb{F}}[V]$:

(4.6)
$m_{\boldsymbol{\Lambda}}(\boldsymbol{\Lambda},\xi_{1},\widehat{\mathcal{L}})=0.$

From, e.g., [29, Proposition 1], we deduce the following bounds:

  * •

$\deg_{T}m_{\boldsymbol{\Lambda}}=D$,

  * •

$\deg_{X_{1}}m_{\boldsymbol{\Lambda}}\leq\delta$,

  * •

$\deg_{\boldsymbol{\Lambda}}m_{\boldsymbol{\Lambda}}\leq\delta$.

Taking partial derivatives with respect to $\Lambda_{j}$ in (4.6), we deduce
the identity

(4.7) $\displaystyle\frac{\partial
m_{\boldsymbol{\Lambda}}}{\partial\Lambda_{j}}(\boldsymbol{\Lambda},\xi_{1},\widehat{\mathcal{L}})+\xi_{j}\displaystyle\frac{\partial
m_{\boldsymbol{\Lambda}}}{\partial
T}(\boldsymbol{\Lambda},\xi_{1},\widehat{\mathcal{L}})=0$

in ${\mathbb{F}}(\boldsymbol{\Lambda})\otimes_{{\mathbb{F}}}{\mathbb{F}}[V]$
for $2\leq j\leq n$. The polynomial $\partial
m_{\boldsymbol{\Lambda}}/\partial T$ is nonzero, and the resultant
$\mathrm{Res}_{T}(m_{\boldsymbol{\Lambda}},\partial
m_{\boldsymbol{\Lambda}}/\partial T)$ is also nonzero (see, e.g., Gímenez &
Matera [16, Lemma 3.2]).

We take some $\boldsymbol{\lambda}\in{\mathbb{F}}^{n-1}$ such that
$\deg_{T}m_{\boldsymbol{\Lambda}}(\boldsymbol{\lambda},X_{1},T)=D$ and
$\mathrm{Res}_{T}(m_{\boldsymbol{\Lambda}},\partial
m_{\boldsymbol{\Lambda}}/\partial T)(\boldsymbol{\lambda},X_{1})\not=0$. Then
the linear form $\mathcal{L}=\boldsymbol{\lambda}\cdot\boldsymbol{X}^{*}$ with
$\boldsymbol{X}^{*}=(X_{2},\ldots,X_{n})$ induces a primitive element of the
separable field extension
${\mathbb{F}}(X_{1})\hookrightarrow{\mathbb{F}}(V_{i})$ for $1\leq i\leq t$,
and the minimal polynomials of $\mathcal{L}$ in the field extensions
${\mathbb{F}}(X_{1})\hookrightarrow{\mathbb{F}}(V_{i})$ are pairwise
relatively prime (see, e.g., [16, Proposition 3.4]). If $\ell$ is the
coordinate function of ${\mathbb{F}}[V]$ defined by $\mathcal{L}$, we then say
that $\ell$ is a primitive element of the extension
${\mathbb{F}}(X_{1})\hookrightarrow{\mathbb{F}}(V)$, where ${\mathbb{F}}(V)$
is total ring of fractions of ${\mathbb{F}}[V]$. Since
$\deg_{T}m_{\boldsymbol{\Lambda}}=D$, it follows that
$m_{\boldsymbol{\Lambda}}(\boldsymbol{\lambda},X_{1},T)$ is the minimal
polynomial of $\ell$ in the extension
${\mathbb{F}}(X_{1})\hookrightarrow{\mathbb{F}}(V)$. Setting

(4.8)
$m_{\boldsymbol{\lambda}}(X_{1},T)=m_{\boldsymbol{\Lambda}}(\boldsymbol{\lambda},X_{1},T),\quad
v_{j}(X_{1},T)=-\frac{\partial
m_{\boldsymbol{\Lambda}}}{\partial\Lambda_{j}}(\boldsymbol{\lambda},X_{1},T)\text{
in }{\mathbb{F}}[X_{1},T]$

and substituting $\boldsymbol{\lambda}$ for $\boldsymbol{\Lambda}$ in
(4.6)–(4.7), we obtain the following identities of ${\mathbb{F}}[V]$:

(4.9) $m_{\boldsymbol{\lambda}}(\xi_{1},\ell)=0,\quad\frac{\partial
m_{\boldsymbol{\lambda}}}{\partial
T}(\xi_{1},\ell)\xi_{j}-v_{j}(\xi_{1},\ell)=0\ \ (2\leq j\leq n).$

Thus the polynomials

$m_{\boldsymbol{\lambda}}(X_{1},\mathcal{L})\text{ and }\frac{\partial
m_{\boldsymbol{\lambda}}}{\partial
T}(X_{1},\mathcal{L})X_{j}-v_{j}(X_{1},\mathcal{L})\ \ (2\leq j\leq n)$

belong to $\mathcal{I}(V)\subset{\mathbb{F}}[X_{1},\ldots,X_{n}]$. They
satisfy the bounds $\deg_{X_{1}}v_{j}\leq\delta$ and $\deg_{T}v_{j}\leq D$ for
$2\leq j\leq n$. Finally, the equations

$m_{\boldsymbol{\lambda}}(X_{1},\mathcal{L})=0,\quad\frac{\partial
m_{\boldsymbol{\lambda}}}{\partial
T}(X_{1},\mathcal{L})X_{j}-v_{j}(X_{1},\mathcal{L})=0\quad(2\leq j\leq n),$

constitute a system of equations for the variety $V$ in the Zariski dense open
subset $V\cap\\{(\partial m_{\boldsymbol{\lambda}}/\partial
T)(X_{1},\mathcal{L})\not=0\\}$ of $V$. This motivates the following
definition.

######  Definition 4.1.

With assumptions as above, a _geometric solution_ of $V$ consists of the
following items:

  * •

a linear form
$\mathcal{L}=\boldsymbol{\lambda}\cdot\boldsymbol{X}^{*}\in{\mathbb{F}}[\boldsymbol{X}^{*}]$
which induces a primitive element $\ell$ of the extension
${\mathbb{F}}(X_{1})\hookrightarrow{\mathbb{F}}(V)$,

  * •

the minimal polynomial $m_{\boldsymbol{\lambda}}\in{\mathbb{F}}[X_{1}][T]$ of
$\ell$,

  * •

a generic _parametrization_ $v_{2},\ldots,v_{n}$ of $V$ by the zeros of
$m_{\boldsymbol{\lambda}}$, of the form

$\frac{\partial m_{\boldsymbol{\lambda}}}{\partial
T}(X_{1},T)\,X_{j}-v_{j}(X_{1},T)\quad(2\leq j\leq n),$

with $v_{j}\in{\mathbb{F}}[X_{1}][T]$, $\deg_{T}v_{j}<D$,
$\deg_{X_{1}}v_{j}\leq\delta$ and $(\partial m_{\boldsymbol{\lambda}}/\partial
T)(X_{1},\mathcal{L})\,X_{j}-v_{j}(X_{1},\mathcal{L})\in\mathcal{I}(V)$ for
$j\leq n$.

We observe that the polynomial
$m_{\boldsymbol{\lambda}}\in{\mathbb{F}}[X_{1},T]$ can be also defined as
follows: consider the linear map

$\pi_{\boldsymbol{\lambda}}\colon
V\to\overline{{\mathbb{F}}\\!}{\,}^{2},\quad\pi_{\boldsymbol{\lambda}}(\boldsymbol{x})=(x_{1},\boldsymbol{\lambda}\cdot\boldsymbol{x}^{*}).$

The Zariski closure of $\pi_{\boldsymbol{\lambda}}(V)$ is a plane curve of
degree at most $\delta$, which is indeed defined by
$m_{\boldsymbol{\lambda}}(X_{1},T)=0$. Further, the projection
$\pi_{\boldsymbol{\lambda}}$ constitutes a birational equivalence between $V$
and the plane curve $\mathcal{C}=\\{m_{\boldsymbol{\lambda}}(X_{1},T)=0\\}$,
namely there is a rational inverse of $\pi_{\lambda}$. More precisely, let

$\displaystyle V_{\mathrm{deg}}$
$\displaystyle=\\{\boldsymbol{x}\in\overline{{\mathbb{F}}\\!}{\,}^{n}:(\partial
m_{\boldsymbol{\lambda}}/\partial T)(x_{1},\mathcal{L}(\boldsymbol{x}))=0\\},$
$\displaystyle\mathcal{C}_{\mathrm{deg}}$
$\displaystyle=\\{\boldsymbol{(}x_{1},t)\in\overline{{\mathbb{F}}\\!}{\,}^{2}:(\partial
m_{\boldsymbol{\lambda}}/\partial T)(x_{1},t)=0\\}.$

The fact that $\mathrm{Res}_{T}(m_{\boldsymbol{\lambda}},\partial
m_{\boldsymbol{\lambda}}/\partial T)\not=0$ implies that $V\setminus
V_{\mathrm{deg}}$ and $\mathcal{C}\setminus\mathcal{C}_{\mathrm{deg}}$ are
Zariski dense open subsets of $V$ and $\mathcal{C}$ respectively. We have the
following result.

######  Fact 4.2 (Cafure & Matera [7, Proposition 6.3]).

$\pi_{\boldsymbol{\lambda}}|_{V\setminus V_{\mathrm{deg}}}:V\setminus
V_{\mathrm{deg}}\to\mathcal{C}\setminus\mathcal{C}_{\mathrm{deg}}$ is an
isomorphism of open sets defined over ${\mathbb{F}}$.

We remark that the inverse of $\pi_{\boldsymbol{\lambda}}|_{V\setminus
V_{\mathrm{deg}}}$ is defined in the following way:

$\displaystyle\mathcal{C}\setminus\mathcal{C}_{\mathrm{deg}}$
$\displaystyle\to V\setminus V_{\mathrm{deg}},$
$\displaystyle(\boldsymbol{x},t)$
$\displaystyle\mapsto\left(x_{1},\frac{v_{2}(x_{1},t)}{(\partial
m_{\boldsymbol{\lambda}}/\partial
T)(x_{1},t)},\ldots,\frac{v_{n}(x_{1},t)}{(\partial
m_{\boldsymbol{\lambda}}/\partial T)(x_{1},t)}\right).$

###  4.2. Power series expansions

Let $n\geq 2$, $V\subset\overline{{\mathbb{F}}\\!}{\,}^{n}$ be a reduced
variety defined over ${\mathbb{F}}$ of pure dimension $1$ and degree $\delta$,
and let $V=V_{1}\cup\cdots\cup V_{t}$ be the decomposition over ${\mathbb{F}}$
of $V$ into irreducible components. Let
$\mathcal{L}=\boldsymbol{\lambda}\cdot\boldsymbol{X}^{*}\in{\mathbb{F}}[\boldsymbol{X}^{*}]$
be a linear form and
$m_{\boldsymbol{\lambda}},v_{2},\ldots,v_{n}\in{\mathbb{F}}[X_{1}][T]$ which
form a geometric solution of $V$ as in the previous subsection.

$V$ is birationally equivalent to the plane curve
$\mathcal{C}\subset\overline{{\mathbb{F}}\\!}{\,}^{2}$ defined by
$m_{\boldsymbol{\lambda}}$. The fact that $V=V_{1}\cup\cdots\cup V_{t}$, where
each $V_{i}$ is irreducible of dimension 1, implies $\mathcal{C}$ has a
decomposition $\mathcal{C}=\mathcal{C}_{1}\cup\cdots\cup\mathcal{C}_{t}$,
where each $\mathcal{C}_{i}$ is defined by an irreducible factor $m_{i}$ of
$m_{\boldsymbol{\lambda}}$, so that the irreducible factorization of
$m_{\boldsymbol{\lambda}}$ in ${\mathbb{F}}[X_{1},T]$ is of the form

$m_{\boldsymbol{\lambda}}(X_{1},T)=\prod_{i=1}^{t}m_{i}(X_{1},T).$

As the linear form $\mathcal{L}$ is a primitive element of the extension
${\mathbb{F}}(X_{1})\hookrightarrow{\mathbb{F}}(V)$, the factors $m_{i}$ are
pairwise coprime with $\sum_{i=1}^{t}\deg_{T}m_{i}=\sum_{i=1}^{t}D_{i}=D$.

Consider a single factor, say $m_{1}$, of $m_{\boldsymbol{\lambda}}$. A
representation of the zeros of $m_{1}$ is provided by the well-known Hensel
lemma (see, e.g., Abhyankar [1, Lecture 12]). More precisely, assume that

(4.10) $\mathrm{Res}_{T}\left(m_{1}(0,T),\frac{\partial m_{1}}{\partial
T}(0,T)\right)\not=0.$

Then there is a factorization $m_{1}=\prod_{i=1}^{D_{1}}(T-\sigma_{i})$ in
$\overline{{\mathbb{F}}\\!}{\,}[\\![X_{1}]\\!][T],$ where
$\overline{{\mathbb{F}}\\!}{\,}[\\![X_{1}]\\!]$ denotes the ring of formal
power series in $X_{1}$ with coefficients in $\overline{{\mathbb{F}}\\!}{\,}$,
and $\sigma_{i}\not=\sigma_{j}$ for $i\not=j$. We shall see that an
approximation of order $2D\delta$ of a single power series, say
$\sigma=\sigma_{1}$, suffices to compute $m_{1}$.

For this purpose, we observe that $m_{1}\in{\mathbb{F}}[X_{1},T]$ can also be
characterized as the primitive polynomial $p\in{\mathbb{F}}[X_{1}][T]$ of
minimal degree (up to nonzero multiples in ${\mathbb{F}}$) for which
$p(X_{1},\sigma)=0$ holds. Let $N=2D\delta$ and let
$\sigma_{N}\in{\mathbb{F}}[X_{1}]$ be the power series $\sigma$ truncated up
to order $N+1$, that is, $\sigma_{N}$ is the polynomial of degree at most $N$
congruent to $\sigma$ modulo $X_{1}^{N+1}$. Our next result shows that $m_{1}$
can be obtained as the solution of a suitable congruence equation involving
$\sigma_{N}$.

######  Lemma 4.3.

Let $p\in{\mathbb{F}}[X_{1},T]$ be a polynomial with $\deg_{X_{1}}p\leq\delta$
and $\deg_{T}p\leq D$ satisfying the condition

(4.11) $p(X_{1},\sigma_{N})\equiv 0\mod X_{1}^{N+1}.$

Then $m_{1}$ divides $p$ in ${\mathbb{F}}[X_{1},T]$.

###### Proof.

Let $p\in{\mathbb{F}}[X_{1},T]$ be a solution of (4.11) satisfying the
conditions of the lemma. The resultant $q\in{\mathbb{F}}[X_{1}]$ of $p$ and
$m_{1}$ with respect to $T$ has degree at most $N$ and belongs to the ideal
generated by $m_{1}$ and $p$. Since $m_{1}(X_{1},\sigma_{N})\equiv 0\mod
X_{1}^{N+1}$ and $p(X_{1},\sigma_{N})\equiv 0\mod X_{1}^{N+1}$ by hypothesis,
we deduce that $q(X_{1})\equiv 0\mod X_{1}^{N+1}$. Therefore, the facts that
$\deg q\leq N$ and $q(X_{1})\equiv 0\mod X_{1}^{N+1}$ imply $q=0$. In
particular, $m_{1}$ and $q$ have a nonconstant common factor in
${\mathbb{F}}(X_{1})[T]$. Taking into account the irreducibility of $m_{1}$ in
${\mathbb{F}}(X_{1})[T]$ and the Gauss lemma, we easily deduce the statement
of the lemma. ∎

Lemma 4.3 characterizes $m_{1}$ as the nonzero solution of (4.11) of minimal
degree in $T$, up to nonzero multiples in ${\mathbb{F}}$. We remark that the
argument of Lemma 4.3 holds mutatis mutandis with any
$M=2D^{\prime}\delta^{\prime}$ instead of $N$, where $D^{\prime}$ and
$\delta^{\prime}$ are upper bounds of $D$ and $\delta$ respectively.

##  5\. The homotopy curve

This section studies the set
$V^{*}\subset\overline{{\mathbb{F}}\\!}{\,}^{d+e}$ of common solutions of the
equations (4.2) and provides a homotopy between the solutions for
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ and for
$(\boldsymbol{\alpha},\boldsymbol{0})$. We use throughout the notation given
there and assume that $\boldsymbol{\alpha}$ is generic.

We consider the projection $\pi_{S}\colon
V^{*}\to\overline{{\mathbb{F}}\\!}{\,}^{1}$ with
$\pi_{S}(\boldsymbol{g},\boldsymbol{h},s)=s$.

######  Lemma 5.1.

$\pi_{S}$ is dominant.

###### Proof.

For $s\in\overline{{\mathbb{F}}\\!}{\,}$, we write
$\pi_{S}^{-1}(s)=W_{s}\times\\{s\\}$, where
$W_{s}\subset\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$ is the set of solutions
$(g,h)$ of the system $(G\circ H)(\alpha_{i})-s\beta_{i}=0$ $\text{ for }1\leq
i\leq d+e-1$, namely the set of interpolants for the interpolation problem
determined by $(\boldsymbol{\alpha},s\boldsymbol{\beta})$. By Corollary 3.4,
any $(\boldsymbol{\gamma},\boldsymbol{\delta})\in\mathcal{U}$ admits a
nonempty finite set of interpolants. As
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ belongs to this dense Zariski open
subset $\mathcal{U}\subset\overline{{\mathbb{F}}\\!}{\,}^{2(d+e-1)}$, it
follows that the affine line
$L_{(\boldsymbol{\alpha},\boldsymbol{\beta})}=\\{(\boldsymbol{\alpha},s\boldsymbol{\beta})\colon
s\in\overline{{\mathbb{F}}\\!}{\,}^{1}\\}$ has a nonempty intersection with
$\mathcal{U}$. In particular,
$L_{(\boldsymbol{\alpha},\boldsymbol{\beta})}\cap\mathcal{U}\\}$ is a nonempty
Zariski open subset of $L_{(\boldsymbol{\alpha},\boldsymbol{\beta})}$, which
proves that there is a nonempty Zariski open subset
$U_{S}=\\{s\colon(\boldsymbol{\alpha},\boldsymbol{\beta}s)\in
L(\boldsymbol{\alpha},\boldsymbol{\beta})\cap\mathcal{U}\\}$ of
$\overline{{\mathbb{F}}\\!}{\,}^{1}$, so that the interpolation problem
determined by $(\boldsymbol{\alpha},s\boldsymbol{\beta})$ for $s\in U_{S}$
admits a finite positive number of interpolants. In particular,
$\pi_{S}^{-1}(s)$ is nonempty for any $s\in U_{S}$, which proves that
$\pi_{S}$ is dominant. ∎

Let $V^{*}=V_{1}\cup\cdots\cup V_{u}$ be the decomposition of $V^{*}$ into
irreducible components defined over ${\mathbb{F}}$. Since $\pi_{S}$ is
dominant, we may assume that the restriction $\pi_{S}|_{V_{i}}\colon
V_{i}\to\overline{{\mathbb{F}}\\!}{\,}^{1}$ of $\pi_{S}$ to $V_{i}$ is
dominant for $1\leq i\leq t$ and not dominant for $t+1\leq i\leq u$, with some
$t\in\\{1,\ldots,u\\}$. We now define the curve which describes our
deformation:

(5.1) $V=V_{1}\cup\cdots\cup
V_{t}\subset\overline{{\mathbb{F}}\\!}{\,}^{d+e}.$

######  Lemma 5.2.

For $1\leq i\leq t$, $\dim V_{i}=1$.

###### Proof.

Fix $i$ with $1\leq i\leq t$. The Theorem on the dimension of fibers (see,
e.g., [30, §6.3, Theorem 7]) shows that

$\dim V_{i}-1=\dim(\pi_{S}|_{V_{i}})^{-1}(s)$

for $s\in{\mathcal{U}}_{S}$. The proof of Lemma 5.1 shows that
$\pi_{S}^{-1}(s)$ has dimension 0 for generic
$s\in\overline{{\mathbb{F}}\\!}{\,}^{1}$, which implies that

$\dim V_{i}-1=\dim(\pi_{S}|_{V_{i}})^{-1}(s)\leq 0.$

Taking into account that $V\subset\overline{{\mathbb{F}}\\!}{\,}^{d+e}$ is
defined by the $d+e-1$ equations (4.2), it follows that $\dim V_{i}\geq 1$ for
$1\leq i\leq u$. We conclude that $\dim V_{i}=1$. ∎

Next we give a more intrinsic definition of the curve $V$. Let $Q_{i}=(G\circ
H)(\alpha_{i})-\beta_{i}S$ $\text{ for }1\leq i\leq d+e-1$, denote
$\boldsymbol{Q}=(Q_{1},\ldots,Q_{d+e-1})$ and let $J$ be the Jacobian
determinant of $\boldsymbol{Q}$ with respect to $\boldsymbol{G}$ and
$\boldsymbol{H}$, that is,

$J=\det(\partial\boldsymbol{Q}/\partial(\boldsymbol{G},\boldsymbol{H})).$

Let $\mathcal{I}\subset{\mathbb{F}}[\boldsymbol{G},\boldsymbol{H},S]$ be the
ideal generated by $Q_{1},\ldots,Q_{d+e-1}$ and let

$\mathcal{I}:J^{\infty}=\\{Q\in{\mathbb{F}}[\boldsymbol{G},\boldsymbol{H},S]\colon\exists\,m\geq
0\textrm{ with }J^{m}Q\in\mathcal{I}\\}$

be the saturation of $\mathcal{I}$ with respect to $J$. Its variety
$\mathcal{Z}(\mathcal{I}:J^{\infty})\subset{\mathbb{F}}^{d+e}$ is the Zariski
closure of the locally closed set
$\mathcal{Z}(\mathcal{I})\setminus\mathcal{Z}(J)$.

######  Lemma 5.3.

$V=\mathcal{Z}(\mathcal{I}:J^{\infty})$.

###### Proof.

For a component $V_{i}$ with $i>t$ we have $\dim\pi_{S}(V_{i})=0$. Further, as
$V_{i}$ is irreducible, also $\pi_{S}(V_{i})$ is irreducible, so that
$\pi_{S}(V_{i})=\\{s_{i}\\}$ for a specific
$s_{i}\in\overline{{\mathbb{F}}\\!}{\,}^{1}$. The fiber $\pi_{S}^{-1}(s_{i})$
is the set of common zeros in $\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$ of the
polynomials $Q_{j}(\boldsymbol{G},\boldsymbol{H},s_{i})$ $(1\leq j\leq
d+e-1)$. For a given point
$(\boldsymbol{g},\boldsymbol{h},s_{i})\in\pi_{S}^{-1}(s_{i})\cap V_{i}$, if
$J(\boldsymbol{g},\boldsymbol{h},s_{i})$ was nonzero, then
$(\boldsymbol{g},\boldsymbol{h},s_{i})$ would be an isolated point of $V_{i}$,
contradicting the fact that $\dim V_{i}\geq 1$. It follows that
$J(\boldsymbol{g},\boldsymbol{h},s_{i})=0$ for any
$(\boldsymbol{g},\boldsymbol{h},s_{i})\in V_{i}$ and
$\mathcal{Z}(\mathcal{I}:J^{\infty})\subseteq V$.

On the other hand, let $1\leq i\leq t$. By Lemma 5.2, $V_{i}$ has dimension 1
and $\pi_{S}|_{V_{i}}\colon V_{i}\to\overline{{\mathbb{F}}\\!}{\,}^{1}$ is
dominant. Since $V_{t+1}\cup\cdots\cup V_{u}$ projects onto the finite set
$\\{s_{t+1},\ldots,s_{u}\\}$, for
$s\in\overline{{\mathbb{F}}\\!}{\,}^{1}\setminus\\{s_{t+1},\ldots,s_{u}\\}$
the fiber $\pi_{S}^{-1}(s)$ does not intersect $V_{t+1}\cup\cdots\cup V_{u}$.
Further, since
$\pi_{S}^{-1}(1)=\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})\times\\{1\\}$
and $\\#\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})=\deg\pi$ by Fact 3.8
and the genericity of $\boldsymbol{\alpha}\in\mathcal{U}$, we conclude that
$\\#\pi_{S}^{-1}(s)=\deg\pi$ for generic
$s\in\overline{{\mathbb{F}}\\!}{\,}^{1}$. In particular, by Lemma 3.10 we have
that $\pi$ is unramified at any
$(\boldsymbol{g},\boldsymbol{h},\boldsymbol{\gamma},\boldsymbol{\delta})\in\pi^{-1}(\boldsymbol{\gamma},\boldsymbol{\delta})$
with $(\boldsymbol{\gamma},\boldsymbol{\delta})\in\mathcal{U}$, which implies
that $\pi_{S}$ is unramified at any
$(\boldsymbol{g},\boldsymbol{h},s)\in\pi_{S}^{-1}(s)$ with $s$ in the nonempty
Zariski open subset $U_{S}$ of $\overline{{\mathbb{F}}\\!}{\,}^{1}$.

We pick some $s\in\pi_{S}(V_{i})\cap U_{S}$ and
$(\boldsymbol{g},\boldsymbol{h},s)\in\pi_{S}^{-1}(s)$. Then
$J(\boldsymbol{g},\boldsymbol{h},s)\not=0$, so that $V_{i}$ is not contained
in $\\{J=0\\}$. It follows that the Zariski closure $V_{i}$ of
$V_{i}\setminus\\{J=0\\}$ is contained in the zero set
$\mathcal{Z}(\mathcal{I}:J^{\infty})$, which completes the proof of the lemma.
∎

With a slight abuse of notation, we also denote the restriction of $\pi_{S}$
to $V$ as $\pi_{S}$, that is, we consider the projection

$\pi_{S}\colon V\to\overline{{\mathbb{F}}\\!}{\,}^{1}\text{ with
}\pi_{S}(\boldsymbol{g},\boldsymbol{h},s)=s.$

As $V=V_{1}\cup\cdots\cup V_{t}$ is the irreducible decomposition of $V$ over
${\mathbb{F}}$ and $\pi_{S}|_{V_{i}}\colon
V_{i}\to\overline{{\mathbb{F}}\\!}{\,}^{1}$ is dominant for $1\leq i\leq t$,
we define

$\deg\pi_{S}=\sum_{1\leq i\leq t}\deg\pi_{S}|_{V_{i}}.$

In the next corollary we collect several consequences of Lemma 5.3.

######  Corollary 5.4.

The following assertions hold:

  1. (1)

the extension ${\mathbb{F}}(S)\hookrightarrow{\mathbb{F}}(V_{i})$ is separable
for $1\leq i\leq t$;

  2. (2)

$\deg\pi_{S}=\deg\pi$;

  3. (3)

$\mathcal{I}:J^{\infty}$ is a radical ideal.

###### Proof.

Fix $i$ with $1\leq i\leq t$. Since $V_{i}$ is not contained in $\\{J=0\\}$,
$V_{i}\cap\\{J=0\\}$ has dimension zero, and thus $V_{i}\setminus\\{J=0\\}$ is
a nonempty Zariski open subset of $V_{i}$. Furthermore, $\pi_{S}|_{V_{i}}$ is
unramified precisely at all points of this open subset. According to [21,
Proposition T.8], the finite field extension
${\mathbb{F}}(S)\hookrightarrow{\mathbb{F}}(V_{i})$ is separable, which proves
(1).

As a consequence, for $1\leq i\leq t$ there exists a nonempty Zariski open
subset $U_{i}$ of $\overline{{\mathbb{F}}\\!}{\,}^{1}$ such that
$\\#(\pi_{S}|_{V_{i}})^{-1}(s)=\deg(\pi_{S}|_{V_{i}})$ for any $s\in U_{i}$.
On the other hand, $\\#\pi^{-1}(s)=\deg\pi$ for any $s$ in a nonempty Zariski
open subset $U_{S}\subset\overline{{\mathbb{F}}\\!}{\,}^{1}$. Let $s^{*}\in
U_{1}\cap\cdots\cap U_{t}\cap U_{S}\setminus\\{s_{t+1},\ldots,s_{u}\\}$ be
such that
$\pi_{S}|_{V_{i}}^{-1}(s^{*})\cap\pi_{S}|_{V_{j}}^{-1}(s^{*})=\emptyset$ for
$i\not=j$. We have

$\deg\pi_{S}=\sum_{i=1}^{t}\deg\pi_{S}|_{V_{i}}=\sum_{i=1}^{t}\\#(\pi_{S}|_{V_{i}})^{-1}(s^{*})=\\#\pi_{S}^{-1}(s^{*})=\\#\pi^{-1}(s)=\deg\pi.$

Finally, since $\\{J=0\\}$ intersects properly each irreducible component
$V_{i}$ with $1\leq i\leq t$, by [16, Lemma 2.1] we conclude that
$\mathcal{I}:J^{\infty}$ is a radical ideal. ∎

Corollary 5.4 and Lemma 3.5 imply the bounds

(5.2) $D=\deg\pi_{S}=\deg\pi\leq\delta=\deg V\leq d^{d+e-1}.$

Now assume that $\boldsymbol{\lambda}\in{\mathbb{F}}^{d+e-1}$ is such that the
linear form
$\mathcal{L}=\boldsymbol{\lambda}\cdot(\boldsymbol{G},\boldsymbol{H})\in{\mathbb{F}}[\boldsymbol{G},\boldsymbol{H}]$
induces a coordinate function $\ell$ of ${\mathbb{F}}[V]$ which is a primitive
element of the extension ${\mathbb{F}}(S)\hookrightarrow{\mathbb{F}}(V_{i})$
for $1\leq i\leq t$. In particular, the minimal polynomial
$m_{\boldsymbol{\lambda}}\in{\mathbb{F}}[S,T]$ of $\ell$ satisfies
$\deg_{T}m_{\boldsymbol{\lambda}}=D$.

For any $s\in\overline{{\mathbb{F}}\\!}{\,}^{1}$, we identify each point in
the fiber $\pi_{S}^{-1}(s)$ with the vector of its
$(\boldsymbol{g},\boldsymbol{h})$-coordinates and denote by
$W_{s}\subset\overline{{\mathbb{F}}\\!}{\,}^{d+e-1}$ the set of such points,
so that $\pi_{S}^{-1}(s)=W_{s}\times\\{s\\}$. In particular,

$\pi_{S}^{-1}(0)=W_{0}\times\\{0\\}=\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{0})\times\\{0\\},\quad\pi_{S}^{-1}(1)=W_{1}\times\\{1\\}=\pi^{-1}(\boldsymbol{\alpha},\boldsymbol{\beta})\times\\{1\\}.$

Let $\boldsymbol{\Lambda}=(\Lambda_{1},\ldots,\Lambda_{d+e-1})$ be a vector of
new indeterminates over ${\mathbb{F}}$.

######  Lemma 5.5.

There exists a nonzero polynomial
$R^{(4)}\in{\mathbb{F}}[\boldsymbol{\Lambda}]$ of degree at most $4D^{2}$ such
that for any $\boldsymbol{\lambda}\in{\mathbb{F}}^{d+e-1}$ with
$R^{(4)}(\boldsymbol{\lambda})\neq 0$, the linear form
$\mathcal{L}=\boldsymbol{\lambda}\cdot(\boldsymbol{G},\boldsymbol{H})$
separates the points of $W_{0}\cup W_{1}$.

###### Proof.

We consider the generic linear form
$\mathcal{L}_{\boldsymbol{\Lambda}}=\boldsymbol{\Lambda}\cdot(\boldsymbol{G},\boldsymbol{H})$
and define

$R^{(4)}=\displaystyle\prod_{p\neq q\in W_{0}\cup
W_{1}}(\mathcal{L}_{\boldsymbol{\Lambda}}(p)-\mathcal{L}_{\boldsymbol{\Lambda}}(q))\in{\mathbb{F}}[\Lambda].$

For $p\neq q$, we have
$\mathcal{L}_{\boldsymbol{\Lambda}}(p)\neq\mathcal{L}_{\boldsymbol{\Lambda}}(q)$.
Since $\\#W_{0}\cup W_{1}\leq 2D$ by Lemma 3.10, it follows that the nonzero
polynomial $R^{(4)}\in{\mathbb{F}}[\boldsymbol{\Lambda}]$ has degree at most
$4D^{2}$. Any $\boldsymbol{\lambda}\in{\mathbb{F}}^{d+e-1}$ not annihilating
$R^{(4)}$ defines a linear form $\mathcal{L}_{\boldsymbol{\lambda}}$ that
separates the points of $W_{0}\cup W_{1}$. ∎

##  6\. An algorithm for decomposable interpolation

The algorithm for computing an interpolant $(g,h)$ for the input
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ with a generic
$\boldsymbol{\alpha}$ proceeds as follows. Computing in
${\mathbb{F}}[\boldsymbol{G},\boldsymbol{H},S]$ is straightforward, and we can
also take its elements modulo the ideal ${\mathcal{I}}(V)$ of the homotopy
curve $V$ to
${\mathbb{F}}[V]={\mathbb{F}}[\boldsymbol{G},\boldsymbol{H},S]/{\mathcal{I}}(V)$.
But testing whether an element of
${\mathbb{F}}[\boldsymbol{G},\boldsymbol{H},S]$ is zero in ${\mathbb{F}}[V]$
amounts to an ideal membership test, which is a nontrivial task. In order to
circumvent this, we work with power series expansions. Recall the general
assumption that $\text{char}({\mathbb{F}})$ does not divide $d$.

From Section 2, we find an interpolating polynomial $(g_{0},h_{0})\in W_{0}$
for $(\boldsymbol{\alpha},\boldsymbol{0})$, so that
$\boldsymbol{v}=(g_{0},h_{0},0)\in V$. Now $\boldsymbol{v}$ actually lies on a
single irreducible component of $V$, say $\boldsymbol{v}\in V_{1}$.
Furthermore, $S\in{\mathbb{F}}[\boldsymbol{G},\boldsymbol{H},S]$ is a local
parameter on $V_{1}$ at $\boldsymbol{v}$, so that there is an injective
morphism of ${\mathbb{F}}$-algebras
$\tau\colon{\mathcal{O}}_{\boldsymbol{v}}\to{\mathbb{F}}[\\![Y]\\!]$ from the
local ring ${\mathcal{O}}_{\boldsymbol{v}}$ of $V_{1}$ at $\boldsymbol{v}$ to
the ring of power series in a new variable $Y$. Since $\tau(S)=Y$ generates
this ring, $\tau$ is actually an isomorphism.

To simplify notation, we abbreviate
$\boldsymbol{G}|\boldsymbol{H}=(G_{d-1},\ldots,G_{0},H_{e-1},\ldots,H_{1})$, a
vector of $d+e-1$ indeterminates. For each $i<d$,
$\gamma_{i}=\tau(G_{i})\in{\mathbb{F}}[\\![Y]\\!]$ is a power series, and
similarly $\eta_{i}=\tau(H_{i})\in{\mathbb{F}}[\\![Y]\\!]$ for $i<e$. We
abbreviate again
$\boldsymbol{\gamma}|\boldsymbol{\eta}=(\gamma_{d-1},\ldots,\gamma_{0},\eta_{e-1},\ldots,\eta_{1})$.

A Newton-Hensel iteration computes an approximation of
$\boldsymbol{\gamma}|\boldsymbol{\eta}$ to a sufficiently large precision $N$,
that is, $\boldsymbol{\psi}\in({\mathbb{F}}[Y]/(Y^{N}))^{d+e-1}$ with
$\boldsymbol{\psi}\equiv\boldsymbol{\gamma}|\boldsymbol{\eta}\bmod Y^{N}$. For
a randomly chosen $\boldsymbol{\lambda}\in{\mathbb{F}}^{d+e-1}$, we take the
linear combination
$\boldsymbol{\lambda}\cdot(\boldsymbol{\gamma}|\boldsymbol{\eta})=\sum_{1\leq
i\leq d}\lambda_{i}\gamma_{d-i}+\sum_{d<i<d+e}\lambda_{i}\eta_{d+e-i}$, its
truncation $L=\sum_{1\leq i<d+e}\lambda_{i}\psi_{i}\in{\mathbb{F}}[Y]/(Y^{N})$
and find the minimal polynomial $m\in{\mathbb{F}}[Y,T]$ of
$\boldsymbol{\lambda}\cdot\boldsymbol{\gamma}|\boldsymbol{\eta}$, which equals
the polynomial of minimal degree in $T$ with $\deg m\leq d^{d+e-1}$ such that
$m(Y,L)\equiv 0\bmod Y^{N}$. Furthermore, we calculate
$m^{\prime}((\boldsymbol{G}|\boldsymbol{H})_{i})$ for each $i<e+d$, where
$m^{\prime}=\partial m/\partial T$ is the derivative of $m$. These data
provide a geometric solution of $V_{1}$, and it then remains to substitute
$S=1$ in them to find the desired interpolation polynomial $(g,h)$ for
$(\boldsymbol{\alpha},\boldsymbol{\beta})$.

We sketch the whole algorithm as follows.

######  Algorithm 6.1.

Input: Generic
$(\boldsymbol{\alpha},\boldsymbol{\beta})\in{\mathbb{F}}^{d+e-1}\times{\mathbb{F}}^{d+e-1}$,
real $\epsilon$ with $0<\epsilon<1$, access to a finite set
${\mathcal{S}}\subseteq{\mathbb{F}}$ with at least
$32\epsilon^{-1}(d^{2}+de)^{2}d^{5(d+e-1)}$ elements.

Output: A composite interpolating polynomial $f$ for
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ as in Problem 1.1, or “fail”.

  1. (1)

Compute a point $(\boldsymbol{g}_{0},\boldsymbol{h}_{0})\in W_{0}$.

  2. (2)

Set $M=d^{d+e-1}+1$ and $N=2d^{2(d+e-1)}+1$. Compute truncated power series
approximations
$\boldsymbol{\gamma}|\boldsymbol{\eta}\in({\mathbb{F}}[Y]/(Y^{N}))^{d+e-1}$
for $\boldsymbol{G}|\boldsymbol{H}$, with $\lceil\log_{2}N\rceil$ steps of the
following quadratic Newton-Hensel iteration for solving the equations
$\boldsymbol{P}=(P_{1},\ldots,P_{d+e-1})=0$, where
$P_{j}(\boldsymbol{G},\boldsymbol{H})=(G\circ
H)(\alpha_{j})-\beta_{j}\,S\in{\mathbb{F}}[G,H,S]$ for $1\leq j\leq d+e-1$.
The initial value is $(\boldsymbol{g}_{0},\boldsymbol{h}_{0})$. One iteration
step is given by the Newton-Hensel operator

$N_{\boldsymbol{P}}(\boldsymbol{\gamma},\boldsymbol{\eta})=(\boldsymbol{\gamma},\boldsymbol{\eta})-(J_{\boldsymbol{P}}^{-1}(\boldsymbol{\gamma},\boldsymbol{\eta},Y))\bigg{(}\boldsymbol{P}(\boldsymbol{\gamma},\boldsymbol{\eta},Y)^{\sf
T}\bigg{)}\in{\mathbb{F}}[\\![Y]\\!]^{d+e-1},$

where
$J_{\boldsymbol{P}}=\partial\boldsymbol{P}/{\partial(G|H)}\in{\mathbb{F}}[G,H,S]^{(d+e-1)\times(d+e-1)}$
is the Jacobian matrix of the system and $\sf T$ denotes transposition. Let
$\psi\in({\mathbb{F}}[Y]/(Y^{N}))^{d+e-1}$ be the resulting vector of power
series truncated up to order $N$.

  3. (3)

Choose $\boldsymbol{\lambda}\in\mathcal{S}^{d+e-1}$ uniformly at random. For
$1\leq j<d+e$, let

$\boldsymbol{Z}^{(j)}=(\lambda_{1},\ldots,\lambda_{j-1},\lambda_{j}+\Lambda_{j},\lambda_{j+1},\ldots,\lambda_{d+e-1}),$

where $\Lambda_{1},\ldots,\Lambda_{d+e-1}$ are new indeterminates. Compute

$\displaystyle L^{(j)}$ $\displaystyle=$
$\displaystyle\boldsymbol{Z}^{(j)}\cdot\boldsymbol{\psi}=\sum_{1\leq
i<d+e}\boldsymbol{Z}^{(j)}_{i}\psi_{i}\in{\mathbb{F}}[\Lambda_{j}][Y]/(Y^{N}),$
$\displaystyle(L^{(j)})^{2},\ldots,(L^{(j)})^{2M}\in{\mathbb{F}}[\Lambda_{j}][Y]/(Y^{N},\Lambda_{j}^{2}).$

  4. (4)

For each $j\in\\{1,\ldots,d+e-1\\}$, find by binary search the smallest value
$k_{j}$ of $\ell$ for which

(6.1) $\sum_{0\leq i\leq\ell}a_{i}^{(j)}(L^{(j)})^{i}\equiv
0\bmod(Y^{N},\Lambda_{j}^{2})$

has a solution
$a_{0}^{(j)},\ldots,a_{\ell}^{(j)}\in{\mathbb{F}}[\Lambda_{j}][Y]$ with
$\deg_{Y}a_{i}^{(j)}<M$ for $i\leq\ell$ and $a_{\ell}^{(j)}$ monic. This
corresponds to a system of linear equations for the coefficients in
${\mathbb{F}}[\Lambda_{j}]/(\Lambda_{j}^{2})$ of the $a_{i}^{(j)}$’s. Compute
such a solution $a^{(j)}_{0},\ldots,a^{(j)}_{k_{j}}$ with $a^{(j)}_{k_{j}}$
monic of minimal degree $M_{j}$. [Then $\ell\leq 2M$ and $M_{j}\leq 2M$ for
all $\ell$ and $M_{j}$ considered.]

  5. (5)

For each $j\in\\{1,\ldots,d+e-1\\}$, let

$\displaystyle m^{(j)}$ $\displaystyle=\sum_{0\leq i\leq
k_{j}}a^{(j)}_{i}T^{i}\in{\mathbb{F}}[\Lambda_{j}][Y,T],\quad
w^{(j)}=-\partial
m^{(j)}/\partial\Lambda_{j}\in{\mathbb{F}}[\Lambda_{j}][Y,T].$

Set

$\displaystyle m$ $\displaystyle=m^{(1)}|_{\Lambda_{1}\leftarrow
0}\in{\mathbb{F}}[Y,T],\quad v_{j}=w^{(j)}|_{\Lambda_{j}\leftarrow
0}+Y\cdot(\partial m/\partial T)\in{\mathbb{F}}[Y,T].$

[Then $\boldsymbol{\lambda},m,v_{1},\ldots,v_{d+e-1}$ form a geometric
solution of $V_{1}$.]

  6. (6)

Substitute 1 for $Y$ in the polynomials $m,v_{1},\ldots,v_{d+e-1}$. Let
$m_{1}=m(1,T)$. Compute polynomials
$u,w_{1},\ldots,w_{d+e-1}\in{\mathbb{F}}[T]$ of degrees less than $\deg m_{1}$
that satisfy

$u\equiv(m_{1}^{\prime})^{-1}\bmod m_{1},\quad
w_{j}\equiv(m_{1}^{\prime})^{-1}\cdot v_{j}(1,T)\bmod m_{1}\ (1\leq j<d+e).$

[Then $\boldsymbol{\lambda},m_{1},w_{1},\ldots,w_{d+e-1}\in{\mathbb{F}}[T]$
form a geometric solution of the zero-dimensional variety
$(W_{1}\times\\{1\\})\cap V_{1}$.]

  7. (7)

Find a root $\eta$ of $m_{1}$ in some extension field ${\mathbb{K}}$ of
${\mathbb{F}}$ and compute

$g|h=(w_{1}(\eta),\ldots,w_{d+e-1}(\eta))\in{\mathbb{K}}^{d+e-1}.$

If $(g\circ h)(\boldsymbol{\alpha}_{j})=\boldsymbol{\beta}_{j}$ for $1\leq
j<d+e$, then return $(g,h)$ else return “fail”.

Details on performing some of the steps are given below. We start with an
illustration of the first steps of the algorithm.

######  Example 6.2.

Continuing Example 2.4, we have $d=e=2$, $\boldsymbol{\alpha}=(5,6,7)$ and
$\boldsymbol{\beta}=(3,3,3)$. Now we need this for
$\boldsymbol{\beta}=(0,0,0)$ and so have to subtract $3$ from $g_{0}$. Then
the very first solution yields $(g_{0},h_{0})=(58,840,-11).$ Then for
$\boldsymbol{\beta}=(1,2,3)$, we have

$\displaystyle J_{\boldsymbol{P}}(\boldsymbol{g}_{0},\boldsymbol{h}_{0})$
$\displaystyle=\left(\begin{array}[]{cccc}h_{0}(\alpha_{1})&1&g_{0}^{\prime}(h_{0}(\alpha_{1}))\,\alpha_{1}\\\
h_{0}(\alpha_{2})&1&g_{0}^{\prime}(h_{0}(\alpha_{2}))\,\alpha_{2}\\\
h_{0}(\alpha_{3})&1&g_{0}^{\prime}(h_{0}(\alpha_{3}))\,\alpha_{3}\end{array}\right)=\left(\begin{array}[]{cccc}-30&1&-10\\\
-30&1&-12\\\ -28&1&\ 14\end{array}\right),$ $\displaystyle
J_{\boldsymbol{P}}^{-1}(\boldsymbol{g}_{0},\boldsymbol{h}_{0})$
$\displaystyle=\left(\begin{array}[]{cccc}-\frac{13}{2}&6&\frac{1}{2}\\\\[2.15277pt]
-189&175&15\\\\[2.15277pt] \frac{1}{2}&-\frac{1}{2}&0\end{array}\right),$
$\displaystyle\boldsymbol{P}(\boldsymbol{g}_{0},\boldsymbol{h}_{0})$
$\displaystyle=\left(\begin{array}[]{cccc}g_{0}\circ
h_{0}(\alpha_{1})-\beta_{1}Y\\\ g_{0}\circ h_{0}(\alpha_{2})-\beta_{2}Y\\\
g_{0}\circ
h_{0}(\alpha_{3})-\beta_{3}Y\end{array}\right)=\left(\begin{array}[]{cccc}-\beta_{1}Y\\\
-\beta_{2}Y\\\
-\beta_{3}Y\end{array}\right)=\left(\begin{array}[]{cccc}-1\,Y\\\ -2\,Y\\\
-3\,Y\end{array}\right),$ $\displaystyle
N_{\boldsymbol{P}}(\boldsymbol{g}_{0},\boldsymbol{h}_{0})$
$\displaystyle=\left(\begin{array}[]{cccc}58\\\ 840\\\
-11\end{array}\right)-\left(\begin{array}[]{cccc}-\frac{13}{2}&6&\frac{1}{2}\\\\[2.15277pt]
-189&175&15\\\
\frac{1}{2}&-\frac{1}{2}&0\end{array}\right)\left(\begin{array}[]{cccc}-1\,Y\\\
-2\,Y\\\ -3\,Y\end{array}\right)$
$\displaystyle=\left(\begin{array}[]{cccc}58+7\,Y\\\ 840+206\,Y\\\
-11-\frac{1}{2}\,Y\end{array}\right)\equiv\left(\begin{array}[]{cccc}\gamma_{1}\\\
\gamma_{0}\\\ \eta_{1}\end{array}\right)\bmod Y^{2}.$

Now suppose that the iteration stops here and in the algorithm, we choose
$\boldsymbol{\lambda}=(-1,1,2)$. Then we have

(6.2)
$L=-1\cdot(58+7\,Y)+1\cdot(840+206\,Y)+2\cdot(-11-\frac{1}{2}Y)=760+198\,Y\in{\mathbb{F}}[Y].$

∎

We next provide some subroutines used in Algorithm 6.1 and estimate error
probabilities and cost. For the latter, we only count arithmetic operations in
${\mathbb{F}}$ and ignore the (small) cost of Boolean operations and finding
random elements. Furthermore, we use the dense representation of
(multivariate) polynomials and mainly standard procedures for simplicity,
except that we denote by ${\sf M}(n)$ the cost of multiplying two univariate
polynomials of degree at most $n$, and by $\omega$ a feasible exponent for
matrix multiplication, so that two $n\times n$ matrices can be multiplied with
$n^{\omega}$ operations. Thus we may use $\omega=2.3728639$ (Le Gall [12]),
and with the notation $O\,\,{\widetilde{}}\,(f)=\\{g\colon g\in f(\log
f)^{O(1)}\\}$ for real functions $f$ and $g$, we have ${\sf M}\in
O\,\,{\widetilde{}}\,(n)$. Possible algorithmic improvements are discussed in
Section 7.

For the analysis of the algorithm, we assume throughout that
$\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ is generic, as required.

######  Lemma 6.3.

Steps (1) and (2) can be performed with $O\,\,{\widetilde{}}\,(d^{2(d+e-1)})$
operations in ${\mathbb{F}}$.

###### Proof.

In step (1) we use Proposition 2.3 to compute a solution
$(\boldsymbol{g}_{0},\boldsymbol{h}_{0})$ for the interpolation problem given
by $(\boldsymbol{\alpha},\boldsymbol{\beta}\cdot
0)=(\boldsymbol{\alpha},\boldsymbol{0})$. This requires a $d$-refinement of
${\mathcal{P}}_{\boldsymbol{0}}$, say
${\mathcal{P}}=\\{\\{1\\},\ldots,\\{d-1\\},\\{d,\ldots,d+e-1\\}\\}$. The
system (2.6) of linear equations can be solved for $\boldsymbol{h}_{0}$ with
$(e-1)^{\omega}$ operations, and the interpolation for $\boldsymbol{g}_{0}$
with $O({\sf M}(d)\log d)$ operations.

One step of the Newton-Hensel iteration in step (2) at most doubles the degree
of the $d+e-1$ power series in $Y$. In the first step, given in Example 6.2,
this degree is at most $1$, and thus in the $k$th step at most $2^{k}$.
Writing $q=d+e-1$ for simplicity, the rows of the $q\times q$ Jacobian matrix
$J_{\boldsymbol{P}}$ are like the top rows in (3.5). At the start of the $k$th
step, each coefficient $(\boldsymbol{g}|\boldsymbol{h})_{i}$ is replaced by a
polynomial in $Y$ of degree at most $2^{k-1}$, say by
$(\boldsymbol{\gamma}^{(k-1)}|\boldsymbol{\eta}^{(k-1)})_{i}$. The linear
combination of the $\eta_{i}^{(k-1)}$ corresponding to $h(\alpha_{j})$ with
coefficients $\alpha_{j}^{i}$ can be computed with $O(e2^{k})$ operations, and
then the powers $h(\alpha_{j})^{2},\ldots,h(\alpha_{j})^{d-1}$ with $O(de{\sf
M}(2^{k}))$ further steps. All this needs to be done for the $q$ values of
$j$, at a cost of $O(deq{\sf M}(2^{k}))$ operations. Similarly, a single
$g^{\prime}(h(\alpha_{j}))$, given the powers of $h(\alpha_{j})$, corresponds
to at most $d$ multiplications of polynomials modulo $Y^{2^{k}}$ at a cost of
$O(d{\sf M}(2^{k}))$ operations. The multiplications by powers of $\alpha_{j}$
are even cheaper. This leads to $O(dq{\sf M}(2^{k}))$ operations.

Thus the matrix
$J_{\boldsymbol{P}}(\boldsymbol{\gamma}^{(k-1)},\boldsymbol{\eta}^{(k-1)},Y)\in{\mathbb{F}}[Y]^{q\times
q}$ can be calculated with $O(de{\sf M}(2^{k}))$ operations. It is invertible
modulo $Y$, hence also modulo $Y^{2^{k}}$. Its inverse in
${\mathbb{F}}[Y]^{q\times q}$ can be found with $O(q^{\omega}{\sf M}(2^{k}))$
operations in ${\mathbb{F}}$ and the product by
$\boldsymbol{P}(\boldsymbol{\gamma}^{(k-1)},\boldsymbol{\eta}^{(k-1)},S)^{\sf
T}$ with $q^{2}{\sf M}(2^{k})$ operations.

In total, the $k$th step of the iteration takes $q^{\omega}{\sf M}(2^{k})$
operations. Since ${\sf M}(n)$ is essentially linear, $\sum_{1\leq
k\leq\kappa}{\sf M}(2^{k})\in O({\sf M}(N))$ and the total cost for step (2)
is $O(q^{\omega}{\sf M}(N))$. ∎

Now $\pi_{S}$ is unramified at $(\boldsymbol{g}_{0},\boldsymbol{h}_{0},0)\in
V=V_{1}\cup\cdots\cup V_{t}$ if and only if $\pi$ is unramified at
$(\boldsymbol{g}_{0},\boldsymbol{h}_{0},\boldsymbol{\alpha},0\cdot\boldsymbol{\beta})=(\boldsymbol{g}_{0},\boldsymbol{h}_{0},\boldsymbol{\alpha},\boldsymbol{0})$,
and the latter holds by Lemma 3.6. Hence
$(\boldsymbol{g}_{0},\boldsymbol{h}_{0},0)$ is contained in exactly one of the
components. Their numbering is arbitrary and we may assume that
$(\boldsymbol{g}_{0},\boldsymbol{h}_{0},0)\in V_{1}$.

In order to provide some details for step (4), we first describe an algorithm
that works for indeterminates $\boldsymbol{\Lambda}$ instead of values
$\boldsymbol{\lambda}\in{\mathbb{F}}^{d+e-1}$. Its intermediate results may
become too large and it is not suited for implementation, but specializations
of it are. So we consider a polynomial ring
$R={\mathbb{F}}[\boldsymbol{\Lambda}]$ in variables
$\boldsymbol{\Lambda}=(\Lambda_{1},\ldots,\Lambda_{d+e-1})$,
$\boldsymbol{\psi}\in({\mathbb{F}}[Y]/(Y^{N}))^{d+e-1}$, and
$\boldsymbol{\Lambda}\cdot\boldsymbol{\psi}=\sum_{1\leq
i<d+e}\Lambda_{i}\psi_{i}\in{\mathbb{F}}[\boldsymbol{\Lambda}][Y]/(Y^{N})$.

######  Subroutine 6.4.

Input: $\boldsymbol{\psi}\in({\mathbb{F}}[Y]/(Y^{N}))^{d+e-1}$.

Output: Integer $k$ and a polynomial
$\mu\in{\mathbb{F}}(\boldsymbol{\Lambda})[Y,T]$ with $\deg_{T}\mu=k$.

  1. (S1)

Find the smallest value $k$ of $\ell$ for which

(6.3) $\sum_{0\leq
i\leq\ell}A_{i}(\boldsymbol{\Lambda}\cdot\boldsymbol{\psi})^{i}\equiv 0\bmod
Y^{N}$

has a solution $A_{0},\ldots,A_{\ell}\in{\mathbb{F}}(\boldsymbol{\Lambda})[Y]$
with $\deg_{Y}A_{i}<M$ for all $i\leq\ell$ and $A_{\ell}$ monic, and compute
such a solution $A_{0},\ldots,A_{k}$ with $A_{k}$ monic of minimal degree
$M^{\prime}$. Starting with $\ell=1,2,4,\ldots$, this binary search keeps on
doubling the values of $\ell$ while calls to the subroutine (S2) return
“fail”. Then it backtracks and homes in on the smallest values $k$ and
similarly finds the smallest $M^{\prime}$ for which (S2) returns an output.

  2. (S2)

The equation (6.3) corresponds to a system of $N$ linear equations for the
$\ell M+M^{\prime}$ coefficients of all
$A_{i}\in{\mathbb{F}}(\boldsymbol{\Lambda})[Y]$ with $\deg_{Y}A_{i}<M$ for
$i<\ell$ and $\deg_{Y}A_{\ell}<M^{\prime}$. With a suitable matrix
$B\in{\mathbb{F}}(\boldsymbol{\Lambda})^{N\times(\ell M^{\prime}+M)}$, the
vector $A\in{\mathbb{F}}(\boldsymbol{\Lambda})^{\ell M^{\prime}+M}$, and a
suitable constant vector $C\in{\mathbb{F}}(\boldsymbol{\Lambda})^{N}$, this
corresponds to the system $BA=C$. Compute with a version of Gaussian
elimination matrices $D\in{\mathbb{F}}(\boldsymbol{\Lambda})^{N\times(\ell
M+M^{\prime})}$, $P\in{\mathbb{F}}^{(\ell M+M^{\prime})\times(\ell
M+M^{\prime})}$ and a vector $E\in{\mathbb{F}}(\boldsymbol{\Lambda})^{N}$ so
that $BX=C$ is equivalent to $DPX=E$ for all $X\in{\mathbb{F}}^{\ell
M+M^{\prime}}$, $P$ is a permutation matrix, and $D$ and $E$ have the form:

$\begin{array}[]{|cccc|c|c|c|}\cline{1-5}\cr\cline{7-7}\cr\star&*&*&*&*&&*\\\
&\ddots&\vdots&\vdots&*&&*\\\ &{0}&\ddots&\vdots&*&&*\\\ &&&\star&*&&*\\\
\cline{1-5}\cr\cline{7-7}\cr&0&&&0&&*\\\
\cline{1-5}\cr\cline{7-7}\cr\end{array}\,,$

where $*$ stands for an arbitrary value and $\star$ for a nonzero value in
${\mathbb{F}}(\boldsymbol{\Lambda})$. If the bottom entries of $E$ (designated
by a single $*$) are all zero, then compute by back-substitution a solution
$Y\in{\mathbb{F}}(\boldsymbol{\Lambda})^{\ell M+M^{\prime}}$ of $DY=E$ with
the value $0$ for those entries of $Y$ that correspond to the lower block of
the matrix, $A=P^{-1}Y\in{\mathbb{F}}(\boldsymbol{\Lambda})^{\ell
M+M^{\prime}}$ and return $A$, else return “fail”.

  3. (S3)

Return $k$ and $\mu=\sum_{0\leq i\leq
k}A_{i}T^{i}\in{\mathbb{F}}(\boldsymbol{\Lambda})[Y,T]$.

The Gaussian elimination works row by row, choosing a suitable nonzero pivot
element $p\in{\mathbb{F}}(\Lambda)$, multiplying one row by the pivot and then
adding it to another row. This creates entries with value $0$ in the matrix.

Now step (4) of Algorithm 6.1 is implemented by running Subroutine 6.4 on the
special inputs $\boldsymbol{Z}^{(j)}$. Gauss elimination performs two types of
computations: calculations in the ground field, here
${\mathbb{F}}(\boldsymbol{\Lambda})$, and tests for zero. Such algorithms are
sometimes called _arithmetic-Boolean circuits_. If $\boldsymbol{\Lambda}$ is
substituted by some special value, say $\boldsymbol{\lambda}$ or
$\boldsymbol{Z}^{(j)}$, then some of the tests that originally return “$\neq
0$” might return “$=0$”. In (6.4) below we define a polynomial
$R^{(5)}\in{\mathbb{F}}[\boldsymbol{\Lambda}]$ such that
$R^{(5)}(\boldsymbol{\lambda})\neq 0$ guarantees that this does not happen. We
call some $\boldsymbol{\lambda}\in{\mathbb{F}}^{d+e-1}$ _lucky_ if
$R^{(5)}(\boldsymbol{\lambda})\neq 0$, and show that the latter occurs with
high probability.

In other words, the condition $R^{(5)}(\boldsymbol{\lambda})\neq 0$ fixes the
Boolean sequence of test outcomes and turns the arithmetic-Boolean circuit
into an arithmetic circuit (or straight-line program).

######  Lemma 6.5.

For the output of Subroutine 6.4, we have $k\leq d^{d+e-1}$.
$R^{(5)}\in{\mathbb{F}}[\boldsymbol{\Lambda}]$ is a nonzero polynomial of
degree at most $32(d^{2}+de)^{2}d^{5(d+e-1)}$. A $\boldsymbol{\lambda}$ as
chosen in step (3) of Algorithm 6.1 is lucky with probability at least
$1-\epsilon$. For any lucky $\boldsymbol{\lambda}$, the following statements
hold:

  1. (1)

The linear form
$\mathcal{L}=\boldsymbol{\lambda}\cdot(\boldsymbol{G},\boldsymbol{H})\in{\mathbb{F}}[\boldsymbol{G},\boldsymbol{H}]$
separates the points of $W_{0}\cup W_{1}$.

  2. (2)

For $1\leq j<d+e$, we have $k_{j}=k$,
$m^{(j)}=\mu|_{\boldsymbol{\Lambda}\leftarrow\boldsymbol{Z}^{(j)}}$ and
$m=\mu|_{\boldsymbol{\Lambda}\leftarrow\boldsymbol{\lambda}}$

###### Proof.

From [29, Proposition 1] we know that there exists a solution to (6.1) with
$k\leq D\leq d^{d+e-1}$ and $M^{\prime}\leq\delta\leq d^{d+e-1}$. Therefore
$\max\\{k,M^{\prime}\\}\leq d^{d+e-1}<M$ in (6.3), so that
$\max\\{\ell,M^{\prime}\\}$ never exceeds $2M$.

For the probabilistic analysis in (1), Lemma 5.5 provides a nonzero polynomial
$R^{(4)}\in{\mathbb{F}}[\boldsymbol{\Lambda}]$ of total degree at most
$4D^{2}\leq 4d^{2(d+e-1)}$ so that $R^{(4)}(\boldsymbol{\lambda})\neq 0$ is
sufficient for the linear form
$\mathcal{L}=\boldsymbol{\lambda}\cdot(\boldsymbol{G},\boldsymbol{H})$ to
separate the points of $W_{0}\cup W_{1}$.

We now present a similar polynomial
$R^{(5)}\in{\mathbb{F}}[\boldsymbol{\Lambda}]$ for the claim in (2), namely,
such that for any $\boldsymbol{\lambda}\in{\mathbb{F}}^{d+e-1}$ with
$R^{(5)}(\boldsymbol{\lambda})\neq 0$, all pivots and denominators in the
subroutine with $\boldsymbol{\lambda}$ substituted for $\boldsymbol{\Lambda}$
are nonzero. A fortiori, this holds for substitution by any
$\boldsymbol{Z}^{(j)}$.

We represent each intermediate result in ${\mathbb{F}}(\boldsymbol{\Lambda})$
as the quotient of two coprime polynomials in
${\mathbb{F}}[\boldsymbol{\Lambda}]$. The _degree_ of the rational function is
the maximum of the two polynomial degrees. Each calculation step yields first
a quotient of two arbitrary polynomials which we then simplify by dividing out
their $\gcd$. All pivots and divisors in the Gaussian elimination of step (S2)
for some value of $\ell$ are quotients of determinants of two square
submatrices of the original coefficient matrix $B$; see Edmonds [10] and
Bareiss [2]. In (6.3), the (total) degree in $\boldsymbol{\Lambda}$ is at most
$\ell$, so this also holds for all entries in $B$. The size of square
submatrices is at most $N\times N$, and their determinants have degree at most
$\ell N$ in $\boldsymbol{\Lambda}$. We denote by
$R^{(5)}_{\ell,M^{\prime}}\in{\mathbb{F}}[\boldsymbol{\Lambda}]$ the product
of all pivots examined and found to be nonzero in the course of the
subroutine. Since there are at most $N$ such pivots, we have $\deg
R^{(5)}_{\ell,M^{\prime}}\leq\ell N^{2}\leq 2d^{d+e-1}N^{2}$. At most
$2\log_{2}2d^{d+e-1}\leq 2(d+e)\log_{2}d$ values of $\ell$ and $M^{\prime}$
are used. We let

(6.4) $R^{(5)}=R^{(4)}\cdot\prod_{\ell,M^{\prime}}R^{(5)}_{\ell,M^{\prime}},$

where the product runs over all such $\ell$. $R^{(5)}$ is a nonzero polynomial
of degree at most

$\displaystyle 4d^{2(d+e-1)}+$ $\displaystyle 4(\log_{2}d)^{2}(d+e)^{2}\cdot
2d^{d+e-1}N^{2}$ $\displaystyle\leq 32(d^{2}+de)^{2}\cdot d^{5(d+e-1)}.$

It is well known (see for example von zur Gathen & Gerhard [14, Lemma 6.44])
that for a nonzero polynomial $p\in{\mathbb{F}}[Y_{1},\ldots,Y_{n}]$ and a
uniformly random choice of
$y=(y_{1},\ldots,y_{n})\in{\mathcal{S}}^{n}\subseteq{\mathbb{F}}^{n}$,

${\text{prob}}\\{p(y)=0\\}\leq\deg p/\\#{\mathcal{S}},$

where $\deg$ denotes the total degree. This implies the second claim. ∎

In particular, in step (5) of Algorithm 6.1, we have
$m=m^{(j)}|_{\Lambda_{j}\leftarrow 0}$ for any $j<d+e$.

######  Lemma 6.6.

Step (3) can be performed with $O\,\,{\widetilde{}}\,(d^{3(d+e-1)})$
operations in ${\mathbb{F}}$ for $1\leq j<d+e$.

###### Proof.

We perform $(d+e)M$ multiplications of univariate polynomials in
${\mathbb{F}}[\Lambda_{j}][Y]$, each with degree at most $1$ in $\Lambda_{j}$
and at most $N$ in $Y$. A single such multiplication can be done with
$O\,\,{\widetilde{}}\,(N)$ operations, for a total cost of
$O\,\,{\widetilde{}}\,(d^{3(d+e-1)})$ operations in ${\mathbb{F}}$. ∎

######  Lemma 6.7.

For a lucky choice of $\boldsymbol{\lambda}$, step (4) can be performed with
$O\,\,{\widetilde{}}\,(d^{6(d+e-1)})$ operations in ${\mathbb{F}}$, for $1\leq
j<d+e$.

###### Proof.

If (6.1) has a solution for some values $\ell$ and $M^{\prime}$, then it also
has one for $\ell+1$ and $M^{\prime}+1$ and all larger values of $\ell$ and
$M^{\prime}$. Therefore, by Lemma 6.5, in the binary search in step (4) all
values $\ell$ and $M^{\prime}$ are at most $2d^{d+e-1}$.

We first consider (6.1) for an arbitrary value of $\ell$ and $M^{\prime}$ and
write each unknown $a^{(j)}_{i}\in{\mathbb{F}}[\Lambda_{j}][Y]$ as
$a^{(j)}_{i}=\sum_{0\leq m<M}a^{(j)}_{im}Y^{m}$ for $i<\ell$ and
$a^{(j)}_{\ell}=\sum_{0\leq m<M^{\prime}}a^{(j)}_{im}Y^{m}$, and
$(L^{(j)})^{i}=\sum_{0\leq
h<N}\ell^{(j)}_{ih}Y^{h}\bmod(Y^{N},\Lambda_{j}^{2})$, with all
$\ell^{(j)}_{ih}\in{\mathbb{F}}[\Lambda_{j}]$ polynomials of degree at most 1
and unknowns $a^{(j)}_{im}$ taking values in
${\mathbb{F}}[\Lambda_{j}]/(\Lambda_{j}^{2})$. Thus (6.1) corresponds to a
system of $N$ linear equations in $\ell M+M^{\prime}$ unknowns over
${\mathbb{F}}[\Lambda_{j}]/(\Lambda_{j}^{2})$.

We use the calculation of Subroutine 6.4 with input $\boldsymbol{Z}^{(j)}$
instead of $\boldsymbol{\Lambda}$. By the assumption that the choice of
$\boldsymbol{\lambda}$ is lucky, all rational functions of
${\mathbb{F}}(\Lambda_{j})$ arising during the execution of Subroutine 6.4 on
input $\boldsymbol{Z}^{(j)}$ are well-defined modulo $\Lambda_{j}$, which
implies that they are well-defined modulo $\Lambda_{j}^{2}$. We conclude that
the output of step (4) is of the form

(6.5) $m^{(j)}|_{\Lambda_{j}\leftarrow 0}+(\partial
m^{(j)}/\partial\Lambda_{j})|_{\Lambda_{j}\leftarrow 0}\cdot\Lambda_{j}.$

The system of linear equations is of size $(\ell M+M^{\prime})\times N$ and
$\ell M+M^{\prime},N\leq 3d^{2(d+e-1)}$. Solving it can be done with
$27d^{6(d+e-1)}$ calculations on matrix entries, which are elements of the
quotient ring ${\mathbb{F}}[\Lambda_{j}]/(\Lambda_{j}^{2})$. More precisely,
each operation involves the images modulo $\Lambda_{j}^{2}$ of two rational
functions of ${\mathbb{F}}(\Lambda_{j})$ (which are well-defined modulo
$\Lambda_{j}^{2}$), and is performed modulo $\Lambda_{j}^{2}$. Since each
operation in ${\mathbb{F}}(\Lambda_{j})$ is replaced by $O(1)$ operations in
${\mathbb{F}}$, we conclude that the whole procedure requires
$O(d^{6(d+e-1)})$ operations in ${\mathbb{F}}$. At most
$2\log_{2}(2d^{d+e-1})$ values of $\ell$ and $M^{\prime}$ occur and the
claimed bound on the running time follows. ∎

######  Lemma 6.8.

For a lucky choice of $\boldsymbol{\lambda}$, the values computed in step (5)
constitute a geometric solution of $V_{1}$. The computation can be performed
with $O\,\,{\widetilde{}}\,(d^{2(d+e-1)})$ operations in ${\mathbb{F}}$.

###### Proof.

For $1\leq j<d+e$, the polynomial $m^{(j)}$ has $\ell M+M^{\prime}\leq
3d^{2(d+e-1)}$ coefficients in ${\mathbb{F}}[\Lambda_{j}]/(\Lambda_{j}^{2})$.
By the expression (6.5) of $m^{(j)}$ the claim on the number of operations in
${\mathbb{F}}$ follows. The fact that the output of step (5) is a geometric
solution of $V_{1}$ is due to (4.8) and (4.9). ∎

######  Lemma 6.9.

For a lucky choice of $\boldsymbol{\lambda}$, the output of step (6) is a
geometric solution of the zero-dimensional variety $(W_{1}\times\\{1\\})\cap
V_{1}$. It can be performed with $O\,\,{\widetilde{}}\,(d^{3(d+e-1)})$
operations in ${\mathbb{F}}$.

###### Proof.

Recall that $(\pi_{S}|_{V_{1}})^{-1}(1)=(W_{1}\times\\{1\\})\cap V_{1}$.
Observe that $\\#((W_{1}\times\\{1\\})\cap
V_{1})=\deg\pi_{S}|_{V_{1}}=D_{1}>0$ and all the elements of
$\pi_{S}((W_{1}\times\\{1\\})\cap V_{1})$ are interpolants for the
interpolation problem defined by $(\boldsymbol{\alpha},\boldsymbol{\beta})$.
Since $\boldsymbol{\lambda},m,v_{1},\ldots,v_{d+e-1}$ form a geometric
solution of $V_{1}$, for $m_{1}=m(1,T)$ we have

$\displaystyle(W_{1}\times\\{1\\})\cap V_{1}=\\{$
$\displaystyle(1,\boldsymbol{g},\boldsymbol{h})\in{\mathbb{F}}^{d+e-1}\colon\
m_{1}(\mathcal{L}(\boldsymbol{g},\boldsymbol{h}))=0,$ $\displaystyle\
m_{1}^{\prime}(\mathcal{L}(\boldsymbol{g},\boldsymbol{h}))(g|h)_{j}=v_{j}(1,\mathcal{L}(\boldsymbol{g},\boldsymbol{h}))\
(1\leq j<d+e)\\}.$

Observe that $\deg m_{1}\leq D_{1}$, $m_{1}\not=0$ and $m_{1}$ vanishes on the
set
$\\{\mathcal{L}(\boldsymbol{g},\boldsymbol{h})\colon(\boldsymbol{g},\boldsymbol{h})\in
W_{1}\\}$, of cardinality $D_{1}$. It follows that $\deg m_{1}=D_{1}$, $m_{1}$
and $m_{1}^{\prime}$ are coprime, and thus the inverse $(m_{1}^{\prime})^{-1}$
modulo $m_{1}$ is well-defined. In particular, defining
$w_{j}=(m_{1}^{\prime})^{-1}\cdot v_{j}$ modulo $m_{1}$ for $1\leq j<d+e$, we
obtain

$(W_{1}\times\\{1\\})\cap
V_{1}=\\{(1,w_{1}(\eta),\ldots,w_{d+e-1}(\eta))\in{\mathbb{F}}^{d+e}\colon\
\eta\in\overline{{\mathbb{F}}\\!}{\,},\ m_{1}(\eta)=0\\}.$

This shows that $\boldsymbol{\lambda},m_{1},w_{1},\ldots,w_{d+e-1}$ form a
geometric solution of $W_{1}$.

The dense representation of $m(1,T),v_{1}(1,T),\ldots,v_{d+e-1}(1,T)$ can be
obtained from that of $m(Y,T),v_{1}(Y,T),\ldots,v_{d+e-1}(Y,T)$ with
$O((d+e)MN)\subseteq O\,\,{\widetilde{}}\,(d^{3(d+e-1)})$ operations in
${\mathbb{F}}$. The remaining computations consist of a modular inversion and
$d+e-1$ modular multiplications of univariate polynomials of degree at most
$M$, which contribute with $O\,\,{\widetilde{}}\,(d^{d+e-1})$ additional
operations. ∎

Step (7) of Algorithm 6.1 has to find a root of $m_{1}\in{\mathbb{F}}[T]$,
with $u=\deg m_{1}\leq d^{d+e-1}$. A natural implementation is to find an
irreducible factor $m_{2}$ of $m_{1}$ and use the root $T\bmod
m_{2}\in{\mathbb{K}}={\mathbb{F}}[T]/(m_{2})$. While the cost of all other
steps can be analyzed for general ${\mathbb{F}}$, this is not clear here. Over
a finite field ${\mathbb{F}}_{q}$, the factorization can be done
probabilistically with $O\,\,{\widetilde{}}\,(u^{1.5}\log q+u\log^{2}q)$ steps
(Kedlaya & Umans [24]). For ${\mathbb{F}}={\mathbb{Q}}$, efficient
factorization algorithms are known, but their cost estimates require a bound
on the size of the coefficients of $m_{1}$. Such a bound can be derived along
the computations of Algorithm 6.1, but we have not done so. Thus in the
following we use some “cost of root finding at degree $u$” for which we have
no good estimate in general.

######  Lemma 6.10.

Step (7) of Algorithm 6.1 can be performed with
$O\,\,{\widetilde{}}\,(d^{2(d+e-1)})$ operations in ${\mathbb{F}}$ plus the
cost of root finding at degree not more than $d^{d+e-1}$.

###### Proof.

For any root $\eta$ of $m_{1}\in{\mathbb{F}}[T]$,
${\mathbb{K}}={\mathbb{F}}[\eta]$ has degree at most $d^{d+e-1}$ over
${\mathbb{F}}$. For any $j<d-e$, the same bound holds for the degree of
$w_{j}\in{\mathbb{F}}[T]$, so that all $w_{j}(\eta)\in{\mathbb{K}}$ can be
computed with $O\,\,{\widetilde{}}\,(d^{d+e-1})$ operations in ${\mathbb{F}}$.
Then $O\,\,{\widetilde{}}\,(d^{2(d+e-1)})$ operations in ${\mathbb{F}}$ are
sufficient to test whether $(g\circ
h)(\boldsymbol{\alpha}_{j})=\boldsymbol{\beta}_{j}$ for $1\leq j<d+e$. ∎

######  Theorem 6.11.

Let $d,e\geq 2$, $0<\epsilon<1$, ${\mathbb{F}}$ be a field of characteristic
not dividing $d$ and with at least
$32\epsilon^{-1}(d^{2}+de)^{2}{d^{5(d+e-1)}}$ elements,
$\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ generic, and
$\boldsymbol{\beta}\in{\mathbb{F}}^{d+e-1}$. Then Algorithm 6.1 returns a
solution $(g,h)$ to Problem 1.1, so that $(g\circ
h)(\boldsymbol{\alpha}_{j})=\boldsymbol{\beta}_{j}$ for $1\leq j<d+e$, with
probability at least $1-\epsilon$. It uses
$O\,\,{\widetilde{}}\,(d^{6(d+e-1)})$ operations in ${\mathbb{F}}$ plus root
finding for degree at most $d^{d+e-1}$.

###### Proof.

The various estimates in Lemmas 6.3 through 6.10 imply a cost of
$O\,\,{\widetilde{}}\,(d^{6(d+e-1)})$ operations in ${\mathbb{F}}$ plus root
finding. For a lucky choice of $\boldsymbol{\lambda}$, the output is indeed a
solution to Problem 1.1, and the probability for this to happen is at least
$1-\epsilon$ by Lemma 6.5. ∎

##  7\. Cost of the algorithm

We have not tried to optimize the cost of our method. The input to Problem 1.1
consists of $2(d+e-1)$ elements of ${\mathbb{F}}$. We do not expect that
runtime polynomial in this input size is feasible, since the coefficients of a
solution $(g,h)$ lie in a field of potentially exponential degree.

The more appropriate view seems to consider the geometric variant of Problem
1.1 as stated in Problem 3.3. This involves the incidence variety
$\Gamma_{n,d}$ and its projection $\pi$ to
$\overline{{\mathbb{F}}\\!}{\,}^{2(d+e-1)}$. According to (5.2), their
geometric degrees are bounded as $D=\deg\pi\leq\delta=\deg\Gamma_{n,d}\leq
d^{d+e-1}$. In step (2) of Algorithm 6.1, the quantities $M$ and $N$ are
defined so that $M>\delta\geq D$ and $N>2\delta D$. These inequalities are all
that is being used about $M$ and $N$ in the lemmas above, and the algorithm
would also work with $D+1$ and $2\delta D+1$ in their place.

Within the algorithm, we avoid using the values of $\delta$ and $D$ because we
do not know them. But we could start the algorithm with some small guess at
those values and then keep on doubling until we actually find a solution
$(g,h)$. The running time then is polynomial in $\delta$.

More precisely, the runtime of this variant of our algorithm is
$O\,\,{\widetilde{}}\,{((d+e)^{\omega}D\delta}+(D\delta)^{\omega}+(d+e)D^{2}\delta)$
plus root finding for degree at most $D$. In particular, Lemma 6.7 can be
modified so that for a lucky choice of $\boldsymbol{\lambda}$, step (4) can be
performed with $O\,\,{\widetilde{}}\,((d+e)D^{\omega}\delta)\subset
O\,\,{\widetilde{}}\,(d^{4(d+e-1)})$ operations in ${\mathbb{F}}$. We briefly
discuss below this modification.

The important papers of Lecerf [20] and van der Hoeven & Lecerf [19] present
algorithms for solving systems of polynomial equations, with running times
$O\,\,{\widetilde{}}\,{(B^{3})}$ and $O\,\,{\widetilde{}}\,{(B^{2})}$,
respectively, where $B$ is the system’s Bézout number. The values $D$ and
$\delta$ considered above satisfy $D\leq\delta\leq B$. Our approach can
approximate $D$ and $\delta$ by binary search, as described. In cases where
they are considerably smaller than $B$, the running time presented here may be
smaller than that of the cited works.

The paper of [19] assumes that their elimination encounters only radical
ideals and that the polynomial system forms a regular sequence. In our case,
the latter requires a saturation with respect to the Jacobian. This has degree
up to roughly $n^{d+e}$; see Figure 3.5. If this is added to the equations of
Problem 3.3 via the Rabinovich trick, then it will increase the Bézout number
by the stated factor. Our approach circumvents this problem by using a
starting value for the Newton iteration where the Jacobian does not vanish.

For the characteristic $p$, we only demand that it does not divide the degree
$n$ of the target polynomial. [20] is stated only for characteristic zero.

We discuss here [20] and [19], because they yield important progress in
general. But it does not seem that they are applicable to our problem.

###  7.1. Hermite–Padé approximations to perform step (4) of Algorithm 6.1

In this section we briefly discuss a variant to perform step (4) of Algorithm
6.1. Recall that, in such a step, for each $j\in\\{1,\ldots,d+e-1\\}$ we find
by binary search the smallest values $k_{j}$ of $\ell$ and, given $k_{j}$, of
$M_{j}$ for $M^{\prime}$ for which

(7.1) $\sum_{0\leq i\leq\ell}a_{i}^{(j)}(L^{(j)})^{i}\equiv
0\bmod(Y^{N},\Lambda_{j}^{2})$

has a solution
$a_{0}^{(j)},\ldots,a_{\ell}^{(j)}\in{\mathbb{F}}[\Lambda_{j}][Y]$ with
$\deg_{Y}a_{i}^{(j)}\leq\delta$ for $i<\ell$,
$\deg_{Y}a_{\ell}^{(j)}<M^{\prime}$ and $a_{\ell}^{(j)}$ monic. For this
purpose, we consider (7.1) as a system of linear equations for the
coefficients in ${\mathbb{F}}[\Lambda_{j}]/(\Lambda_{j}^{2})$ of the
$a_{i}^{(j)}$’s, and compute such a solution
$a^{(j)}_{0},\ldots,a^{(j)}_{k_{j}}$ with $a^{(j)}_{k_{j}}=1$ monic of degree
$M_{j}^{\prime}$.

To find such a solution of (7.1), we interpret it as a problem of Hermite-Padé
approximation, which can be solved applying an algorithm of Bostan et al. [6],
based on fast linear-algebra algorithms for matrices of fixed displacement
rank (cf. Bini & Pan [4], Pan [27]). More precisely, for a suitable ordering
of the unknowns, the matrix $B_{j}$ of system (7.1) is a block-Toeplitz matrix
with $\ell$ blocks (see Cafure et al. [8, Lemma 4.3]; see also [6, Lemma 17]).

From [6, Corollary 1] it follows that, if there exist a nonzero solution of
(7.1), then one such solution can be computed with
$O\,\,{\widetilde{}}\,\big{(}\ell^{\omega-1}{\sf M}(\ell M^{\prime})\big{)}$
arithmetic operations in ${\mathbb{F}}$ and error probability at most
$1/(2\epsilon)$ for any fixed $\epsilon>0$. The algorithms of [6] work over a
field. We apply their results to computations over
${\mathbb{F}}(\\!(\Lambda_{j})\\!)$, but perform calculations in
${\mathbb{F}}[\\![\Lambda_{j}]\\!]/(\Lambda_{j}^{2})$, which is all that we
need. This works because our conditions guarantee that all divisions are by
series which are invertible in
${\mathbb{F}}[\\![\Lambda_{j}]\\!]/(\Lambda_{j}^{2})$. Thus computing in
${\mathbb{F}}[\Lambda_{j}]/(\Lambda_{j}^{2})$ is sufficient. Taking into
account that at most $2\log_{2}(2D)$ values of $\ell$ and $2\log_{2}(2\delta)$
values of $M^{\prime}$ occur for $1\leq j\leq d+e-1$, we have the following
result.

######  Lemma 7.1.

For a lucky choice of $\boldsymbol{\lambda}$, step (4) of Algorithm 6.1 can be
computed with $O\,\,{\widetilde{}}\,\big{(}(d+e)D^{\omega}\delta\big{)}$
operations in ${\mathbb{F}}$ and error probability at most $1/(2\epsilon)$ for
any fixed $\epsilon>0$.

Next we analyze the probability of failure of the choice of the vector
$\boldsymbol{\lambda}$.

######  Proposition 7.2.

Let $\mathcal{S}\subset{\mathbb{F}}$ be a finite set with at least
$64\epsilon^{-1}(d+e)D^{2}(\delta+2)^{\log\delta+3}$ elements. A
$\boldsymbol{\lambda}$ chosen uniformly at random in $\mathcal{S}^{d+e-1}$ is
lucky with probability at least $1-2\epsilon$.

###### Proof.

Arguing as in Lemma 6.5, we analyze the denominators in
${\mathbb{F}}[\Lambda_{j}]$ which occur when using the algorithm of [6] to
solve the Hermite-Padé approximation problem (7.1) for $1\leq j\leq d+e-1$.
This algorithm is an adaptation of Kaltofen’s _Leading Principal Inverse_
algorithm (Kaltofen [22], [23]). The algorithm performs a recursive reduction
of the computation of the inverse of a “generic-rank-profile” square input
matrix

$A=\left(\begin{array}[]{cc}A_{1,1}&A_{1,2}\\\ A_{2,1}&A_{2,2}\\\
\end{array}\right)$

to that of the leading principal submatrix $A_{1,1}$ and its Schur complement
$\Delta=A_{2,2}-A_{2,1}A_{1,1}^{-1}A_{1,2}$. The divisions which arise during
the execution of this recursive step are related to the computation of
$A_{1,1}^{-1}$ and $\Delta^{-1}$ and a routine of “compression” (cf. [4,
Problem 2.2.11.c]) of the generators of matrices which are obtained as certain
products involving $A_{1,1}^{-1}$, $\Delta^{-1}$, $A_{1,2}$ and $A_{2,1}$. The
latter in turn requires the computation of the inverses of certain submatrices
of the products under consideration.

Each entry of the matrix $B_{j}$ of the linear system (7.1) is a coefficient
of a power $(L^{(j)})^{i}$, which is therefore a polynomial in $\Lambda_{j}$
of degree at most $i\leq\ell$. Since the generic-rank-profile matrix $A$ is
obtained by multiplying the matrix $B_{j}$ with suitable matrices with entries
in ${\mathbb{F}}$, we conclude that the entries of $A_{1,1}$ are polynomials
of ${\mathbb{F}}[\Lambda_{j}]$ of degree at most $\ell\leq D$, while the
numerators and denominators of the entries of $\Delta^{-1}$ are polynomials of
${\mathbb{F}}[\Lambda_{j}]$ of degree at most $D(\delta+2)$. Therefore, by a
simple recursive argument it can be seen that the numerators and denominators
of all leading principal submatrices and Schur complements which are inverted
during the algorithm have degrees bounded by
$\mathcal{D}=D(\delta+2)^{\log\delta}$. This in turn implies that the
denominators arising during the compression routine have degrees bounded by
$3\mathcal{D}\delta$.

Taking into account that the algorithm of [6] for each value of $\ell$ and
$M^{\prime}$ consists of at most $\log_{2}\delta$ recursive steps, and that
each recursive step requires the inversion of at most 4 matrices, we conclude
that the product of all the denominators arising during the algorithm has
degree bounded by $8\mathcal{D}\delta\log_{2}\delta$. Since at most
$2\log_{2}(2D)$ values of $\ell$ and $2\log_{2}(2\delta)$ values of
$M^{\prime}$ occur for $1\leq j\leq d+e-1$, we conclude that the degree of all
denominators is bounded from above by
$32(d+e)\mathcal{D}\delta\log_{2}^{3}(2\delta)$.

Finally, according to Lemma 5.5, $\boldsymbol{\lambda}$ must not annihilate a
polynomial $R^{(4)}$ of degree $2D^{2}$. The statement of the proposition
readily follows. ∎

We recall from (4.3) and (4.4) that $D\leq\delta\leq d^{d+e-1}$. Then from the
above estimate, Lemma 7.1 and the error probability $1/(2\mu)$ of the
algorithm underlying Lemma 7.1, we deduce the following result.

######  Theorem 7.3.

Let $d,e\geq 2$, $0<\epsilon<1$, ${\mathbb{F}}$ be a field of characteristic
not dividing $d$ and with at least
$64\epsilon^{-1}(d+e)D^{2}(\delta+2)^{\log\delta+3}$ elements,
$\boldsymbol{\alpha}\in{\mathbb{F}}^{d+e-1}$ generic, and
$\boldsymbol{\beta}\in{\mathbb{F}}^{d+e-1}$. Then a solution $(g,h)$ to
Problem 1.1 can be computed with probability at least $1-\epsilon$. It uses
$O\,\,{\widetilde{}}\,{((d+e)^{\omega}D^{\omega}\delta)}$ operations in
${\mathbb{F}}$ plus root finding for degree at most $D$.

## Open question

Our algorithm uses time polynomial in the _geometric input size_ , namely the
degree of the variety $\Gamma_{n,d}$ in (3.2) that encodes our problem. The
entries of an output $(g,h)$ lie in an extension field whose degree is bounded
by $D\leq d^{d+e-1}$ and our runtime estimate is polynomial in this bound. It
remains open how close this bound is to the actual minimal extension degree
required; some experiments might shed light on this, but we have not done
this.

One may wonder whether time polynomial in the actual output size of an
instance is possible, or whether some particularly succinct representation of
the output allows a faster solution. The special cases treated in Section 2
even allow a solution in time polynomial in the size of the input, consisting
just of the $d+e-1$ field elements that form $\alpha$ and $\beta$. This cannot
be expected in general.

Another approach would be to use a numerical instead of our algebraic
homotopy. We have not investigated this.

## Acknowledgements

We thank Adrien Touboul for pointing out to us the question addressed in this
paper, and Joris van der Hoeven and Grégoire Lecerf for useful comments.

## References

  * [1] S. Abhyankar, _Algebraic geometry for scientists and engineers_ , Math. Surv. Monogr., vol. 35, American Mathematical Society, Providence, RI, 1990.
  * [2] E. Bareiss. _Sylvester’s Identity and Multistep Integer-Preserving Gaussian Elimination_ , Math. Comp. 22 (1968), 565–578.
  * [3] D. Berend and T. Tassa, _Improved bounds on Bell numbers and on moments of sums of random variables_ , Probability and Mathematical Statistics, 30 (2010), 185–205.
  * [4] D. Bini and V. Pan, _Polynomial and matrix computations_ , Progress in Theoretical Computer Science, Birkhäuser, Boston, 1994.
  * [5] R. Blankertz, J. von zur Gathen, and K. Ziegler, _Compositions and collisions at degree $p^{2}$_, J. Symbolic Computation 59 (2013), 113-145.
  * [6] A. Bostan, C.-P. Jeannerod, and E. Schost, _Solving structured linear systems with large displacement rank_. Theoret. Comput. Sci. 407 (2008), 155–181.
  * [7] A. Cafure and G. Matera, _Improved explicit estimates on the number of solutions of equations over a finite field_ , Finite Fields Appl. 12 (2006), 155–185.
  * [8] A. Cafure, G. Matera, and A. Waissbein, _Inverting bijective polynomial maps over finite fields_ , in Proceedings of the 2006 Information Theory Workshop, ITW2006, G. Seroussi and A. Viola, eds., IEEE Information Theory Society, 2006, pp. 27–31.
  * [9] V. Danilov, _Algebraic varieties and schemes_ , in I. Shafarevich (Ed.), Algebraic Geometry I, vol. 23 of Encyclopaedia of Mathematical Sciences, Springer, Berlin Heidelberg New York, 1994, 167–307.
  * [10] J. Edmonds, _Systems of distinct representatives and linear algebra_ , J. Res. Nat. Bureau Standards 71B (1967), 241–245.
  * [11] W. Fulton, _Intersection theory_ , Springer, Berlin Heidelberg New York, 1984\.
  * [12] F. Le Gall, _Powers of tensors and fast matrix multiplication_ , in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), 2014, pages 296-303. Also arXiv:1401.7714.
  * [13] J. von zur Gathen, _Normal form for Ritt’s Second Theorem_ , Finite Fields Appl. 27 (2014), 41–71.
  * [14] J. von zur Gathen and J. Gerhard, _Modern computer algebra_ , Cambridge Univ. Press, Cambridge, 2013.
  * [15] J. von zur Gathen and G. Matera, _Density of real and complex decomposable univariate polynomials_ , Q. J. Math. 68 (2017), no. 4, 1227–1246.
  * [16] N. Giménez and G. Matera, _On the bit complexity of polynomial system solving_ , J. Complexity 51 (2017), 20–67.
  * [17] M. Giusti, G. Lecerf, and B. Salvy, _A Gröbner free alternative for polynomial system solving_ , J. Complexity 17 (2001), 154–211.
  * [18] J. Heintz, _Definability and fast quantifier elimination in algebraically closed fields_ , Theoret. Comput. Sci. 24 (1983), 239–277.
  * [19] J. van der Hoeven and G. Lecerf, _On the complexity exponent of polynomial system solving_ , Found. Comput. Math. 21 (2021), no. 1, 1–57.
  * [20] G. Lecerf, _Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers_ , J. Complexity, 19(4), 2003, 564–596.
  * [21] B. Iversen, _Generic local structure of the morphisms in commutative algebra_ , Springer Lect. Notes in Math. 13, Springer, New York, 1973.
  * [22] E. Kaltofen, _Asymptotically fast solution of Toeplitz–like singular linear systems_ , in Proceedings ISSAC’94, J. von zur Gathen and M. Giesbrecht, eds., New York, 1994, ACM Press, pp. 297–304.
  * [23] , E. Kaltofen, _Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems_ , Math. Comp. 64 (1995), 777–806.
  * [24] K. Kedlaya and C. Umans, _Fast polynomial factorization and modular composition_ , SIAM J. Computing 40 (6) (2011), 1767-1802.
  * [25] E. Kunz, _Introduction to commutative algebra and algebraic geometry_ , Birkhäuser, Boston, 1985.
  * [26] I. Mezö, _Combinatorics and number theory of counting sequences_ , Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2020.
  * [27] V. Pan, _Structured matrices and polynomials. Unified superfast algorithms_ , Birkhäuser, Boston, 2001.
  * [28] F. Rouillier, _Solving zero–dimensional systems through rational univariate representation_ , Appl. Algebra Engrg. Comm. Comput. 9 (1997), 433–461.
  * [29] E. Schost, _Computing parametric geometric resolutions_ , Appl. Algebra Engrg. Comm. Comput. 13 (2003), 349–393.
  * [30] I. Shafarevich, _Basic algebraic geometry: Varieties in projective space_ , Springer, Berlin Heidelberg New York, 1994.