2nd Latin American School and Workshop on Polynomial Systems

Angra dos Reis, RJ, Brasil - Feb 28th to March 4th, 2005

Preliminary Program

Five Lectures

Bernd Sturmfels, Department of Mathematics, University of California at BerkeleyAlgebraic Geometry of Statistical Models

The five lectures offer an introduction to algebraic methods in statistics. Many statistical models for discrete data, in particular those used in machine learning and computational biology, can be regarded as algebraic varieties inside a high-dimensional probability simplex. While some of these models correspond to classical geometric objects (e.g. Segre varieties and their secant varieties), others pose new and unexpected challenges for algebraic geometers. Conversely, computational algebraic geometry has a lot to offer for statistical analysis since certain key problems, such as computing maximum likelihood estimates and checking identifiability, lead to systems of polynomial equations.

Bernd Sturmfels' five lectures will be based on his forthcoming book with Lior Pachter, titled "Algebraic Statistics for Computational Biology".

The lectures will correspond to sections in the book as follows:

Lecture 1: Statistical Models (Sections 1.1 and 1.2)

Lecture 2: Maximum Likelihood (Sections 3.3 and 1.3)

Lecture 3: Markov Models (Sections 1.4 and 1.5)

Lecture 4: Phylogenetics (Sections 2.4 and 3.5)

Lecture 5: Alignment and Inference (Sections 2.2 and 3.4)

A draft of the book is available electronically at http://math.berkeley.edu/~lpachter/ascb_book/. Course participants are strongly encouraged to take a look at the above sections before traveling to Angra dos Reis.

Tutorial Lectures

Alicia Dickenstein, Departamento de Matemática, FCEyN, Universidad de Buenos AiresToric Ideals and Applications
ABSTRACT: Toric ideals are those prime polynomial ideals generated by monomial differences, or equivalently, the defining ideals of toric varieties. We will survey basic features of these ideals and more generally of binomial ideals, as well as of the relationship between the geometry of toric varieties and the geometry of lattice polytopes.

If time permits, we will also outline very briefly some of the applications of toric ideals to enumeration of lattice points in polytopes, integer programming, hypergeometric differential equations, and toric models in statistics.

Gregorio Malajovich, Departamento de Matemática Aplicada, Universidade Federal do Rio de JaneiroMixed Volume and Sparse Homotopy
ABSTRACT: The number of solutions of a sparse system of polynomial equations can be bounded in terms of an invariant of the "support" of the equations, known as the mixed volume.

I intend to explain mixed volume from the elementary geometric viewpoint, and speak briefly about the algorithm of "polyhedral homotopy" suggested by Huber and Sturmfels.

If time allows, I will also speak on more elaborate interpretations of the mixed volume.

Ioannis Emiris, Department of Informatics & Telecommunications, National University of AthensSparse Elimination and Geometric Applications
ABSTRACT: This talk surveys the theory of sparse, or toric, elimination, including recent progress in this area, as well as certain open questions. We present algorithmic issues and methods, most notably mixed subdivisions and matrix formulae for the sparse, or toric, resultant. We finally discuss different applications, in particular examples from non-linear computational geometry, computer-aided geometric design and the kinematics of rigid mechanisms.
Jean-Pierre Dedieu, Département de Mathématique, Université Paul Sabatier, ToulouseNewton Iteration on Manifolds and Applications
ABSTRACT: The first part of this talk is a survey of recent results about Newton method on manifolds. In the second part, we consider problems posed on the manifold of mxn rank k matrices.
Laurent Buse, INRIA Sophia-AntipolisElimination Theory, Commutative Algebra and Applications
ABSTRACT: Classical multivariate resultants, mainly introduced by Macaulay, can be used to solve polynomial systems and have many applications in computer aided geometric design. As a main drawback, they require the system to be in a sufficiently generic position. In this talk, we will show how commutative algebra can help resultants when the system is not in such a generic position. In a first part we will focus on polynomial system solving and in a second part we will report on the "implicitization" problem consisting in computing an implicit equation of a rational curve or surface.

Invited Lectures

Aron Simis, Departamento de Matemática, Universidade Federal de PernambucoAlgebraic description and effective computation of certain structures in algebra
ABSTRACT: For some years we have looked into an algebraic transciption of geometric structures suited for effective computation in the usual computer systems.

The emphasys is on structures of tangential nature, such as the variety of secant lines and higher secant spaces, tangential varieties, higher Gauss images of a projective variety and the associated defining incidence varieties in biprojective space. This talk will explain the contents of such a transcription and survey some examples to clarify the whole intent.

Grigory Mikhalkin, Mathematics, University of TorontoComplex, real and tropical curves
ABSTRACT: Tropical varieties are algebraic varieties over the so-called tropical semifields (terminology is taken from Computer Science). From a geometric point of view they are limit objects of the so-called amoebas of complex algebraic varieties under a certain deformation of the ambient complex structure. This talk will focus on tropical curves and their applications for a range of classical problems in complex and real algebraic geometry.
Harm Derksen, Mathematics, University of Michiganrational invariant theory
ABSTRACT: I will discuss theoretical and computational aspects of function fields. I will present a uniform approach to a wide range of problems, such as:

* finding the intersection of two function fields

* finding rational invariants (integrating factors) for discrete and continuous dynamical systems, and for algebraic group actions

* intersecting an ideal in K[x_1,...,x_n] with the subring k[x_1,...,x_n] where k is a subfield of K.

Jean-Claude Yakoubsohn, Département de Mathématiques, Université Paul Sabatier, ToulouseComputation of singularities of analytic functions
ABSTRACT: This work is joint with Marc Giusti, Grégoire Lecerf, and Bruno Salvy

1- In the one variable case we will give precise complexity estimates to locate all the roots in a square and we discuss how to prove numerically the existence of clusters of roots.

2- For multivariate systems, we will give the state of art for the embedding dimension one case.

In the both cases, we will propose a numerical certificated algorithm to approximate a cluster of roots

1- M. Giusti, G. Lecerf, B. Salvy, and J.-C. Yakoubsohn. On location and approximation of clusters of zeroes of analytic functions.
2-M. Giusti, G. Lecerf, B. Salvy, and J.-C. Yakoubsohn. On location and approximation of clusters of zeroes : case of embedding one

Mario Wschebor, Centro de Matemática, Facultad de Ciencias, Universidad de la RepúblicaRandom systems of equations
ABSTRACT: Our initial goal is to give a simple proof of the Shub-Smale theorem on the expectation of the number of roots of a particular random polynomial system of equations, using the so-called Rice formula coming from the theory of random fields.

As by products of the method one can extend the Shub-Smale formula to quite general situations.

We will also mention some recent results on higher moments of the number of roots, wich help to understand the quality of the approximations.

Mikael Passare, Department of Mathematics, Stockholm UniversityPolynomial amoebas and tropical geometry
Rimvydas Krasauskas, Department of Mathematics and Informatics, Vilnius UniversityApplications of toric varieties to rational surface modeling
ABSTRACT: Rational surfaces are widely used in Geometric Modeling in the form of rational Bezier quadrangular or triangular patches, which have most intuitive shape control. We will survey several applications of toric varieties to rational surface modeling: toric Bezier patches as generalized Bezier surfaces; complex toric surfaces with non-canonical real structures; universal rational parametrizations of almost toric varieties; relations between certain toric threefolds and rational surfaces with rational offsets; blending of natural quadrics using rational canal surfaces.
Shuhong Gao, Department of Mathematical Sciences, Clemson UniversityRecent progress on factoring polynomials
ABSTRACT: The past few years have witnessed dramatic progress on polynomial factoring. Several new algorithms have been proposed using ideas from different areas, e.g. differential equations, polytopes, trace combination, or logarithmic derivative. The differential equation method yields an efficient algorithm for rational and absolute factorizaion, as well as for approximate factoring. Logarithmic derivative method combined with differential equations can be used to dramatically speed up the classical Hensel lifting method for rational factorization. In this talk, I shall give a survey on these developments. My main focus will be on multivariate polynomials. Both exact and approximate factoring will be discussed.
Vilmar Trevisan, Mathematics, UFRGS - Federal do Rio Grande do SulA generalization of Gao's algorithm for polynomial factorization
ABSTRACT: In 2003 Shuhong Gao presented an algorithm for bivariate polynomial factorization based on a differential equation. His crucial result is that the dimension of the polynomial solution space associated with the differential equation equals the number r of absolutely irreducible factors of the polynomial f, as long as the characteristic of the field is zero or is greater than a certain bound. In our contribution, we eliminate the restriction on the chacteristic of the field by determining a subspace of Gao's original solution space, whose dimension is r.

This leads to a reduction of the problem to Gao's and to an extension of his algorithm to finite fields of any given characteristic. Additionally, we identify a second vector subspace whose dimension agrees with the number of rational irreducible factors of f, leading to a bivariate factorization algorithm over finite fields recovering these factors.

25 Minutes Lectures

Alvaro Rittatore, Centro de Matemática, Facultad de Ciencias, Universidad de la Republica, UruguayCombinatorial aspects of the theory of reductive monoids.
ABSTRACT: We will present a (short) survey of the combinatorial classification of reductive monoids, as well as how to relate it with the representation theory of the monoids.
Anton Leykin, Mathematics, Statistics and Computer Science, University of Illinois at ChicagoDeflation of Polynomial Systems at Isolated Singularities
ABSTRACT: We have developed a modification of Newton's method that guarantees quadratic convergence in the neighborhood of an isolated singular solution of a polynomial system. Our method is symbolic-numeric: in a numerically stable way, we produce a sequence of deflations ending in a new polynomial system which has the original multiple solution as a regular root. Using standard bases for local orderings, a symbolic tool for analysis of local polynomial rings, we show that the number of deflation stages is bounded by the multiplicity of the isolated root. Our implementation of the algorithm performs well on a large class of examples. (joint work with Jan Verschelde and Ailing Zhao)
Dan Avritzer, Departamento de matemática, Universidade Federal de Minas Gerais Desargues Configurations and the associated binary sextic
ABSTRACT: A Desargues configuration is the configuration of 10 points and 10 lines of the classical Desargues Theorem in the complex projective plane. In the paper 'Curves of genus 2 and Desargues Configurations' (Advances in Geometry 2(2002),259-280), joint with Herbert Lange, we considered a classical XIX century construction of Stephanos, where he started from a Desargues configuration and constructed a binary sextic from it using about 100 pages of classical geometric invariant theory.We were able to get a slightly more precise result and simplify considerably the proof using contemporary machinery. More precisely we showed that there is a birational morphism from the moduli sapce of Desargues configurations to the moduli space of binary sextics. Recently it came to our attention another such map in a paper by Marr of 1926 using different methods. In this talk I would like to explain the contents of the first paper and describe some more recent results where we compare both maps and give more precise results about the relation between the two moduli spaces.
Fernando Cukierman, Department of Mathematics, University of Buenos Aires (FCEN)On the geometry of the moduli space of foliations in projective space
ABSTRACT: Let F(r, d) denote the scheme parametrizing codimension one integrable foliations of degree d on the complex projective space of dimension r. We plan to describe some problems and results about the irreducible components of F(r, d) related to their enumeration, incidence relations and singularities. This is joint work with Jorge Vitorio Pereira (IMPA)
Gabriela Jeronimo, Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos AiresDifferential polynomial equation systems
ABSTRACT: We consider a class of ordinary first order multivariate polynomial differential systems related to the observability problem from control theory and investigate the application of algebraic and geometric tools to their resolution.

Given a polynomial differential system, we focus on the computation of the differential Hilbert function of the prime differential ideal associated with the system and of a transcendence basis of the induced differential field extension, a starting point towards the computation of a resolvent representation of the ideal. First, we establish theoretical formulae for the differential Hilbert function and we design a probabilistic algorithm for its computation. Then, we show an algebraic criterion for deciding differential transcendence which is the basis for the algorithm solving the second task.

(Joint work with Lisi D'Alfonso and Pablo Solernó.)

Juan Sabia, Departamento de Matemática - Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires - CONICETEliminating polynomials easy to evaluate
ABSTRACT: One of the parameters that can be taken into account when dealing with polynomial coding is whether they are easy to evaluate or not, that is to say, if they do or do not take too many steps to be evaluated at a particular point. In general, a polynomial in n variables of degree d will take d^{O(n)} steps to be evaluated. In this talk we show that the multihomogeneous resultant is easy to evaluate (i.e. it can be evaluated in much less steps than expected).

(Joint work with Gabriela Jeronimo)

Leandro Cagliero, FaMAF , Univ. Nac. CordobaA closed formula for weight multiplicities of representations of Sp(2,C).
ABSTRACT: Complex finite dimensional irreducible representations of complex simple Lie algebras decompose, under the action of a Cartan subalgebra, as the sum of their weight spaces. The dimension of a given weight space is called its multiplicity. Although there are several formulas to compute these multiplicities, from the classical formulas of Freudenthal and Kostant to more recent ones as those of Lusztig, Littelmann, Sahi among others, this is still a computationally hard problem. Some of the formulas are of a recursive nature, some involve partition functions or counting paths or infinite sums.

Here we present a closed formula for weight multiplicities of irreducible representations of Sp(2,C). More precisely, we explicitely give the degree 2 quasipolynomials and the chamber decomposition arising from the vector partition function nature of the weight functions.

Paulo Tirao, CIEM - FaMAF, Universidad Nacional de CordobaBounds for the homology of nilpotent Lie algebras
ABSTRACT: An important problem in the the theory of Lie algebras is to understand their homology. Very little is known about how to compute it and precise computations exist only in a few particular cases. The class of nilpotent Lie algebras deserves special attention. A major topic in this area has been for a long time the construction of lower bounds for their homology. General results are lacking and a number of conjectures are open.

In this talk we will discuss the Toral Rank Conjecture and related problems. We exhibit combinatorial bounds for the class of graded Lie algebras and we show that they are ``accurate'' for 2-step algebras. We will also consider briefly the case of the adjoint homology of 2-step algebras and finally we report on recent progress for the non-graded case.

Rodrigo Iglesias, Departamento de Matematica, Universidad Nacional del SurEquations defining simple groups and quantum groups
ABSTRACT: Let G be a simply connected complex semisimple group and V a finite dimensional representation of G. The image of G inside GL(V) is known to be defined by quadratic equations in many special cases (for example V. Popov proved recently that this happens when V is the sum of the fundamental representations). Here we show that for an arbitrary V this immersion is essentially determined by quadratic polynomials. We also discuss the quantum analogue of this problem.
Sfer, Ana María, Matemática, Nacional de TucumánA proposal of a model based definition for the causal effect in nonlinear models
ABSTRACT: The randomization produces comparables or balanced groups when there are a large number of experimental units. (Fisher (1996), Kempthorne (1977), Lehman (1975)). In normal linear models, with additive effect, the randomization produces unbiased estimator for the causal effect even when there are omitted covariates or unobserved variables. This result is not clear from the literature for no linear models. We studied new tools for Causal Inference as Graphical Models and Rubin Causal Model. We write the maximum likelihood equations and we propose a new definition of the causal effect based in the model. In particular, building on the work of Rubin (1978) and Spirtes et al. (2001). In this way, when there is randomization, it is easy to remove the effect of the covariate on the causal effect in no linear models as in the linear models. We show as our propose function by simulations for Logistic Model.
Victor Hugo Jorge Pérez, Departamento de Matemática -ICMC , Universidade de São PauloConstant Lê numbers implies constant multiplicity for nondegenerate singularit
ABSTRACT: We investigate the constancy of the Lê numbers of one parameter deformations of holomorphic germs of functions f:C^{n+1},0) to (C,0) with non isolated singularity, in terms of some Newton polyhedra associate to such germs.

When the Jacobian ideals J(f_t) of a deformation f_t(z) = f(z)+sum_{s=1}^{ell}delta_s(t)g_s(z)$ are non-degenerate on some fixed Newton polyhedron Gamma_+, we show that this family has constant Lê numbers for small values of t, if and only if all germs g_s have non-decreasing Gamma ordering with respect to f. As a consequence of these results, we give a positive answer for the Zariski question: "Wheter for a hypersurface singularity the multiplicity is an invariant of the topological type" for Lê constant families satisfying a non-degeneracy condition on the Jacobian ideal.

Virgínia Maria Rodrigues, Departamento de Matemática, Pontifícia Universidade Católica do Rio Grande do SulGroebner Basis Structure of Finite Sets of Points
ABSTRACT: We study the structure of Groebner bases for zero- dimensional radical ideals. These ideals correspond to vanishing ideals of finite sets of points in an affine n-dimensional space. We are interested in monomial orders that 'eliminate' one variable, say z, which correponds to the projection map of points in the n-space to (n-1)-space where the z- coordinate is projected out. We show that any minimal Groebner basis of an ideal under an elimination order will exhibit the geometric structure of the variety defined by the ideal. Particularly, the degrees in z of the polynomials in the Groebner basis match the fibre sizes of the projection map, and the leading coefficients of z with given degrees give Groebner bases for the projected points with corresponding fibre sizes.

Joint work with Shuhong Gao and Jeff Stroomer.

Walter Ferrer, Mathematics, Universidad de la RepublicaTBA