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 deg
rees 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.
This paper deals with properties of the algebraic variety defined as the set of zeros of a typical sequence of polynomials. We consider various types of nice varieties: set-theoretic and ideal-theoretic complete intersections, absolutely irreducible
ones, and nonsingular ones. For these types, we present a nonzero obstruction polynomial of explicitly bounded degree in the coefficients of the sequence that vanishes if its variety is not of the type. Over finite fields, this yields bounds on the number of such sequences. We also show that most sequences (of at least two polynomials) define a degenerate variety, namely an absolutely irreducible nonsingular hypersurface in some linear projective subspace.
We estimate the density of tubes around the algebraic variety of decomposable univariate polynomials over the real and the complex numbers.
Most hypersurfaces in projective space are irreducible, and rather precise estimates are known for the probability that a random hypersurface over a finite field is reducible. This paper considers the parametrization of space curves by the appropriat
e Chow variety, and provides bounds on the probability that a random curve over a finite field is reducible.
