A Few Remarks About the Hilbert Scheme of Smooth Projective Curves

We discuss two conjectures by Francesco Severi and Joe Harris about the irreducibility and the dimension of the Hilbert scheme parameterizing smooth projective curves of given degree and genus.     

Complexity of Sparse Polynomial Solving: Homotopy on Toric Varieties and the Condition Metric

Foundations of Computational Mathematics - This paper investigates the cost of solving systems of sparse polynomial equations by homotopy continuation. First, a space of systems of n-variate...     

Counting Complexity Classes for Numeric Computations. III: Complex Projective Sets

In [8] counting complexity classes #P_R and #P_C in the Blum-Shub-Smale (BSS) setting of computations over the real and complex numbers, respectively, were introduced. One of the main results of [8] is that the problem to compute the Euler characteristic of a semialgebraic set is complete in the class FP_R^#PR. In this paper, we prove that the corresponding result is true over C, namely that the computation of the Euler characteristic of an affine or projective complex variety is complete in the class FP_C^#PC. We also obtain a corresponding completeness result for the Turing model.     

The Hilbert Series of the Clique Complex

For a graph G, we show a theorem that establishes a correspondence between the fine Hilbert series of the Stanley-Reisner ring of the clique complex for the complementary graph of G and the fine subgraph polynomial of G. We obtain from this theorem some corollaries regarding the independent set complex and the matching complex.     

Computing the Homology of Real Projective Sets

We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of real projective varieties. Here numerical means that the algorithm is numerically stable (in a sense to be made precise). Its cost depends on the condition of the input as well as on its size and is singly exponential in the number of variables (the dimension of the ambient space) and polynomial in the condition and the degrees of the defining polynomials. In addition, we show that outside of an exceptional set of measure exponentially small in the size of the data, the algorithm takes exponential time.     

Polynomial interpolation of operators in Hilbert spaces

An operator polynomial is constructed as the limit of a smoothing polynomial as λ → ∞. Using its interpolation properties, necessary and sufficient conditions for the existence of a solution of the polynomial interpolation problem are found. The set of all interpolating polynomials in a Hilbert space is described. Bibliography:4 titles. Translated fromObchyslyuval’na ta Prykladna Matematyka, No. 77, 1993, pp. 44–54.     

The Computational Complexity of the Resultant Method for Solving Polynomial Equations

Under an assumption of distribution on zeros of the polynomials, we have given the estimate of computational cost for the resultant method. The result in that, in probability $1-\mu$, the computational cost of the resultant method for finding $ε$-approximations of all zeros is at most $$cd^2(log d+log\frac{1}{\mu}+loglog\frac{1}ε)$$, where the cost is measured by the number of f-evaluations. The estimate of cost can be decreased to $c(d^2logd+d^2log\frac{1}{\mu}+dloglog\frac{1}ε)$ by combining resultant method with parallel quasi-Newton method.     

Hilbert Polynomial of a Certain Ladder-Determinantal Ideal

A ladder-shaped array is a subset of a rectangular array which looks like a Ferrers diagram corresponding to a partition of a positive integer. The ideals generated by the p-by-p minors of a ladder-type array of indeterminates in the corresponding polynomial ring have been shown to be hilbertian (i.e., their Hilbert functions coincide with Hilbert polynomials for all nonnegative integers) by Abhyankar and Kulkarni [3, p 53–76]. We exhibit here an explicit expression for the Hilbert polynomial of the ideal generated by the two-by-two minors of a ladder-type array of indeterminates in the corresponding polynomial ring. Counting the number of paths in the corresponding rectangular array having a fixed number of turning points above the path corresponding to the ladder is an essential ingredient of the combinatorial construction of the Hilbert polynomial. This gives a constructive proof of the hilbertianness of the ideal generated by the two-by-two minors of a ladder-type array of indeterminates.     

On the Complexity Exponent of Polynomial System Solving

Foundations of Computational Mathematics - We present a probabilistic Las Vegas algorithm for solving sufficiently generic square polynomial systems over finite fields. We achieve a nearly...     

The Stirling Polynomial of a Simplicial Complex

We introduce a new encoding of the face numbers of a simplicial complex, its Stirling polynomial, that has a simple expression obtained by multiplying each face number with an appropriate generalized binomial coefficient. We prove that the face numbers of the barycentric subdivision of the free join of two CW-complexes may be found by multiplying the Stirling polynomials of the barycentric subdivisions of the original complexes. We show that the Stirling polynomial of the order complex of any simplicial poset and of certain graded planar posets has non-negative coefficients. By calculating the Stirling polynomial of the order complex of the r-cubical lattice of rank n + 1 in two ways, we provide a combinatorial proof for the following identity of Bernoulli polynomials:

The Varieties of Tangent Lines to Hypersurfaces in Projective Spaces

For a hypersurface in a projective space, we consider the set of pairs of a point and a line in the projective space such that the line intersects the hypersurface at the point with a fixed multiplicity. We prove that this set of pairs forms a smooth variety for a general hypersurface.     

On the Projective Normality of Smooth Surfaces of Degree Nine

The projective normality of smooth, linearly normal surfaces of degree 9 in ^N is studied. All nonprojectively normal surfaces which are not scrolls over a curve are classified. Results on the projective normality of surface scrolls are also given.     

Computing the arithmetic genus of Hilbert modular fourfolds

The Hilbert modular fourfold determined by the totally real quartic number field is a desingularization of a natural compactification of the quotient space , where PSL acts on by fractional linear transformations via the four embeddings of into . The arithmetic genus, equal to one plus the dimension of the space of Hilbert modular cusp forms of weight , is a birational invariant useful in the classification of these varieties. In this work, we describe an algorithm allowing for the automated computation of the arithmetic genus and give sample results.

     

On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e., estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that: (1) perform at least one operation on each matrix entry; and (2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors. September 10, 1999. Final version received: August 23, 2000.