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.
We analyze the behavior of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field F_q of q elements when the highest-degree polynomial g is fixed. Considering all the elements f of fixed degree, we es
tablish asymptotically optimal bounds in terms of q for the number of elements f which are relatively prime with g and for the average degree of gcd(g,f). The accuracy of our estimates is confirmed by practical experiments. We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.
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 obtain estimates on the number $|mathcal{A}_{boldsymbol{lambda}}|$ of elements on a linear family $mathcal{A}$ of monic polynomials of $mathbb{F}_q[T]$ of degree $n$ having factorization pattern $boldsymbol{lambda}:=1^{lambda_1}2^{lambda_2}cdots n
^{lambda_n}$. We show that $|mathcal{A}_{boldsymbol{lambda}}|= mathcal{T}(boldsymbol{lambda}),q^{n-m}+mathcal{O}(q^{n-m-{1}/{2}})$, where $mathcal{T}(boldsymbol{lambda})$ is the proportion of elements of the symmetric group of $n$ elements with cycle pattern $boldsymbol{lambda}$ and $m$ is the codimension of $mathcal{A}$. Furthermore, if the family $mathcal{A}$ under consideration is sparse, then $|mathcal{A}_{boldsymbol{lambda}}|= mathcal{T}(boldsymbol{lambda}),q^{n-m}+mathcal{O}(q^{n-m-{1}})$. Our estimates hold for fields $mathbb{F}_q$ of characteristic greater than 2. We provide explicit upper bounds for the constants underlying the $mathcal{O}$--notation in terms of $boldsymbol{lambda}$ and $mathcal{A}$ with good behavior. Our approach reduces the question to estimate the number of $mathbb{F}_q$--rational points of certain families of complete intersections defined over $mathbb{F}_q$. Such complete intersections are defined by polynomials which are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning their singular locus, from which precise estimates on their number of $mathbb{F}_q$--rational points are established.
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.
We obtain an estimate on the average cardinality of the value set of any family of monic polynomials of Fq[T] of degree d for which s consecutive coefficients a_{d-1},..., a_{d-s} are fixed. Our estimate holds without restrictions on the characterist
ic of Fq and asserts that V(d,s,bfs{a})=mu_d.q+mathcal{O}(1), where V(d,s,bfs{a}) is such an average cardinality, mu_d:=sum_{r=1}^d{(-1)^{r-1}}/{r!} and bfs{a}:=(a_{d-1},.., d_{d-s}). We provide an explicit upper bound for the constant underlying the mathcal{O}--notation in terms of d and s with good behavior. Our approach reduces the question to estimate the number of Fq--rational points with pairwise--distinct coordinates of a certain family of complete intersections defined over Fq. We show that the polynomials defining such complete intersections are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning the singular locus of the varieties under consideration, from which a suitable estimate on the number of Fq--rational points is established.
We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time--space complexity is roughly quadratic in the logarithm of the cardinality o
f the field and a geometric invariant of the input system (called its degree), which is always bounded by the Bezout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.
