# 2nd Latin American School and Workshop on Polynomial Systems

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

# Five Lectures

 Bernd Sturmfels, Department of Mathematics, University of California at Berkeley Algebraic Geometry of Statistical Models ABSTRACT: 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 Aires Toric 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 Janeiro Mixed 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 Athens Sparse 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, Toulouse Newton 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-Antipolis Elimination 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 Pernambuco Algebraic 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 Toronto Complex, 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 Michigan rational 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, Toulouse Computation 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 References 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 (download) Mario Wschebor, Centro de Matemática, Facultad de Ciencias, Universidad de la República Random 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 University Polynomial amoebas and tropical geometry Rimvydas Krasauskas, Department of Mathematics and Informatics, Vilnius University Applications 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 University Recent 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 Sul A 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.