Probabilistic absolute irreducibility test for polynomials

The absolute irreducibility of a polynomial with rational coefficients can usually be proved by detecting rational conditions on one of its reductions modulo some prime numbers. We show that the probability for these conditions to be realized is very high. The resulting fast algorithm is thus a good preliminary step for absolute factorization procedures of computer algebra systems.     

Continuity properties for flat families of polynomials (I) Continuous parametrizations

Inspired by classical results in algebraic geometry, we study the continuity with respect to the coefficients, of the zero set of a system of complex homogeneous polynomials with a given pattern and when the Hilbert polynomial of the generated ideal is fixed. In this work we prove topological properties of some classifying spaces, e.g. the space of systems with given pattern, fixed Hilbert polynomial is locally compact, and we establish continuous parametrizations of Nullstellensatz formulae. In the general case we get local rational results but in the complex case we get global results using rational polynomials in the real and imaginary parts of the coefficients. In a second companion paper, we shall treat the continuity of zero sets for the Hausdorff distance, i.e., from a metric point of view.     

Degree formulae for offset curves

In this paper, we present three different formulae for computing the degree of the offset of a real irreducible affine plane curve C given implicitly, and we see how these formulae particularize to the case of rational curves. The first formula is based on an auxiliary curve, called S, that is defined depending on a non-empty Zariski open subset of R². The second formula is based on the resultant of the defining polynomial of C, and the polynomial defining generically S. The third formula expresses the offset degree by means of the degree of C and the multiplicity of intersection of C and the hodograph H to C, at their intersection points.     

Impossibility of extending Pólya’s theorem to “forms” with arbitrary real exponents

Pólya proved that if a form (homogeneous polynomial) with real coefficients is positive on the nonnegative orthant (except at the origin), then it is the quotient of two real forms with no negative coefficients. While Pólya’s theorem extends, easily, from ordinary real forms to “generalized” real forms with arbitrary rational exponents, we show that it does not extend to generalized real forms with arbitrary real (possibly irrational) exponents.     

Quadratic Newton Iteration for Systems with Multiplicity

Newton's iterator is one of the most popular components of polynomial equation system solvers, either from the numeric or symbolic point of view. This iterator usually handles smooth situations only (when the Jacobian matrix associated to the system is invertible). This is often a restrictive factor. Generalizing Newton's iterator is still an open problem: How to design an efficient iterator with a quadratic convergence even in degenerate cases? We propose an answer for an m -adic topology when the ideal m can be chosen generic enough: compared to a smooth case we prove quadratic convergence with a small overhead that grows with the square of the multiplicity of the root.     

Effective Nullstellensatz for arbitrary ideals

Let f _i be polynomials in n variables without a common zero. Hilbert’s Nullstellensatz says that there are polynomials g _i such that ∑g _i f _i =1. The effective versions of this result bound the degrees of the g _i in terms of the degrees of the f _j . The aim of this paper is to generalize this to the case when the f _i are replaced by arbitrary ideals. Applications to the Bézout theorem, to Łojasiewicz–type inequalities and to deformation theory are also discussed. Received August 24, 1998 / final version received June 21, 1999     

Fast conversion algorithms for orthogonal polynomials

We discuss efficient conversion algorithms for orthogonal polynomials. We describe a known conversion algorithm from an arbitrary orthogonal basis to the monomial basis, and deduce a new algorithm of the same complexity for the converse operation.     

On zero-divisors of near-rings of polynomials

In this paper, we are interested to study zero-divisor properties of a 0-symmetric nearring of polynomials R₀[x], when R is a commutative ring. We show that for a reduced ring R, the set of all zero-divisors of R₀[x], namely Z(R₀[x]), is an ideal of R₀[x] if and only if Z(R) is an ideal of R and R has Property (A). For a non-reduced ring R, it is shown that Z(R₀[x]) is an ideal of Z(R₀[x]) if and only if ann_R({a, b}) ∩ N i?(R) ≠ 0, for each a, b ∈ Z(R). We also investigate the interplay between the algebraic properties of a 0-symmetric nearring of polynomials R₀[x] and the graph-theoretic properties of its zero-divisor graph. The undirected zero-divisor graph of R₀[x] is the graph Γ(R₀[x]) such that the vertices of Γ(R₀[x]) are all the non-zero zero-divisors of R₀[x] and two distinct vertices f and g are connected by an edge if and only if f ? g = 0 or g ? f = 0. Among other results, we give a complete characterization of the possible diameters of Γ(R₀[x]) in terms of the ideals of R. These results are somewhat surprising since, in contrast to the polynomial ring case, the near-ring of polynomials has substitution for its “multiplication” operation.     

On an isoperimetric inequality for capacity conjectured by Pólya and Szegö

We study a conjecture by Pólya and Szegö on the approximation of the electrostatic capacity of convex bodies in terms of their surface measure. We prove that a “local version” of this conjecture holds true and we give some results which bring further evidence to its global validity.     

Lifting and recombination techniques for absolute factorization

In the vein of recent algorithmic advances in polynomial factorization based on lifting and recombination techniques, we present new faster algorithms for computing the absolute factorization of a bivariate polynomial. The running time of our probabilistic algorithm is less than quadratic in the dense size of the polynomial to be factored.     

Hurwitz spaces and liftings to the Valentiner group

We study the components of the Hurwitz scheme of ramified coverings of ${\mathbb{P}}^1$ with monodromy given by the alternating group $A_6$ and elements in the conjugacy class of product of two disjoint cycles. In order to detect the connected components of the Hurwitz scheme, inspired by the case of the spin structures studied by Fried for the 3-cycles, we use as invariant the lifting to the Valentiner group, a triple covering of $A_6$. We prove that the Hurwitz scheme has two irreducible components when the genus of the covering is greater than zero, in accordance with the asymptotic solution found by Bogomolov and Kulikov.     

Set-theoretic defining equations of the tangential variety of the Segre variety

We prove a set-theoretic version of the Landsberg-Weyman Conjecture on the defining equations of the tangential variety of a Segre product of projective spaces. We introduce and study the concept of exclusive rank. For the proof of this conjecture, we use a connection to the author’s previous work and re-express the tangential variety as the variety of principal minors of symmetric matrices that have exclusive rank no more than 1. We discuss applications to semiseparable matrices, tensor rank versus border rank, context-specific independence models and factor analysis models.     

A structured rank-revealing method for Sylvester matrix

We propose a fast algorithm for computing the numeric ranks of Sylvester matrices. Let S denote the Sylvester matrix and H   denote the Hankel-like-Sylvester matrix. The algorithm is based on a fast Cholesky factorization of S^TS$S^{\mathrm{T}}S$ or H^TH$H^{\mathrm{T}}H$ and relies on a stabilized version of the generalized Schur algorithm for matrices with displacement structure. All computations can be done in O(r(n+m))$\mathrm{O}(r(n+m))$, where n+m$n+m$ and r denote the size and the numerical rank of the Sylvester matrix, respectively.     

Lamé operators with finite monodromy—a combinatorial approach

We are describing Lamé differential operators with a full set of algebraic solutions. For each finite group G, we are describing the possible values of the degree parameter n such that the Lamé operator L_n has the projective monodromy group G. The main technical tool is the combinatorics associated to Belyi functions, ideas that we already used in (Rend. Sem. Mat. Univ. Padova 107 (2002) 191-208) for describing the case n=1. We also supply proofs to some finiteness properties conjectured by Baldassarri and by Dwork, and we work out an explicit formula for the number of essentially different Lamé equations when n=2. This approach can be generalized for arbitrary degree n (see (Counting Integral Lamé Equations by Means of Dessins d'Enfants, arXiv:math.CA/0311510) for n integer).     

Characteristic functional equations of polynomials and the morera-carleman theorem

Several characteristic functional equations satisfied by classes of polynomials of bounded degree are examined in connection with certain generalizations of the Morera-Carleman Theorem. Certain functional equations which have nonanalytic polynomial solutions are also considered.     

The Brauer-Manin obstruction for sections of the fundamental group

We introduce the notion of a Brauer-Manin obstruction for sections of the fundamental group extension and establish Grothendieck’s section conjecture for an open subset of the Reichardt-Lind curve.     

Curves having one place at infinity and linear systems on rational surfaces

Denoting by L_d(m₀,m₁,…,m_r) the linear system of plane curves of degree d passing through r+1 generic points p₀,p₁,…,p_r of the projective plane with multiplicity m_i (or larger) at each p_i, we prove the Harbourne-Hirschowitz Conjecture for linear systems L_d(m₀,m₁,…,m_r) determined by a wide family of systems of multiplicities and arbitrary degree d. Moreover, we provide an algorithm for computing a bound for the regularity of an arbitrary system , and we give its exact value when is in the above family. To do that, we prove an H¹-vanishing theorem for line bundles on surfaces associated with some pencils “at infinity”.     

Towards the multiplicative behavior of the K-theoretical McKay correspondence

When the quotient of a symplectic vector space by the action of a finite subgroup of symplectic automorphisms admits as a crepant projective resolution of singularities the Hilbert scheme of regular orbits of Nakamura, then there is a natural isomorphism between the Grothendieck group of this resolution and the representation ring of the group, given by the Bridgeland-King-Reid map. However, this isomorphism is not compatible with the ring structures. For the Hilbert scheme of points on the affine plane, we study the multiplicative behavior of this map.