# Publicaciones del CMAT

Publicaciones de los docentes del Centro de Matemática

Armentano, D, Beltrán, C, Burgisser, P, Cucker, F, and Shub, M (2016).

## Condition length and complexity for the solution of polynomial systems

Foundation of Computational Mathematics.

Smale’s 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale in Mathematical problems for the next century, American Mathematical Society, Providence, 2000). The main progress on Smale’s problem is Beltrán and Pardo (Found Comput Math 11(1):95–129, 2011) and Bürgisser and Cucker (Ann Math 174(3):1785–1836, 2011). In this paper, we will improve on both approaches and prove an interesting intermediate result on the average value of the condition number. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán and Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser and Cucker (2011), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last theorem is similar to the main result of Bürgisser and Cucker (2011) but relies only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser and Cucker (2011). We build on methods developed in Armentano et al. (2014).

Hammerlindl, A and Potrie, R (2015).

## Classification of partially hyperbolic diffeomorphisms in 3-manifolds with solvable fundamental group

Journal of Topology:1-36.

Iturriaga, R and Maderna, E (2015).

## Generic uniqueness of the minimal Moulton central configuration

Celest. Mech. Dyn. Astron., 123(3):351-361.

We prove that, for generic (open and dense) values of the masses, the Newtonian potential function of the collinear N-body problem has N!/2 critical values when restricted to a fixed inertia level. In particular, we provee that for generic masses, there is only one minimal Moulton configuration. We give a very short proof of an improved version of classical Moulton's theorem using the Gershgorin circle theorem and a normalization of central configurations introduced by Yoccoz in 1986. Then the proof of the main theorem follows by reduction to the case of three bodies, in which we apply a theorem by Euler of 1765.

Potrie, R (2014).

## Wild Milnor attractors accumulated by lower dimensional dynamics

Ergodic Theory and Dynamical Systems, 34(1):236–262.

Bonatti, C, Crovisier, S, Gourmelon, N, and Potrie, R (2014).

## Tame dynamics and robust transitivity

Transactions of the American Mathematical Society, 366(9):4849–4871.

Hammerlindl, A and Potrie, R (2014).

## Pointwise partial hyperbolicity in 3-dimensional nilmanifolds

Journal of London Math. Society, 89(3):853-875.

Potrie, R (2014).

## A few remarks on partially hyperbolic diffeomorphisms of T^3 isotopic to Anosov

Journal of Dynamics and Differential Equations:1-12.

Da Luz, A and Maderna, E (2014).

## On the free time minimizers of the Newtonian N-body problem

Math. Proc. Cambridge Philos. Soc., 156(2):209-227.

The Hamiltonian formulation of the Newtonian N-body problem assures that motions are characterized by the local minimization property of the Lagrangian action. In this paper we study the dynamics of a very special class of motions, which satisfy a strong global minimization property. More precisely, we call a free time minimizer a curve which satisfies the least action principle between any pair of its points without the constraint of time for the variations. A simple example of a free time minimizer defined on an unbounded interval is a parabolic homothetic motion by a minimal central configuration. The existence of a large amount of free time minimizers can be deduced from the weak KAM theorem. In particular, for any choice of y in E^N , there should be at least one free time minimizer x on [0,+∞) which satisfies x(0)=y. We prove that such motions are completely parabolic meaning that the velocity of each body goes to zero as t goes to +∞. More precisely, we show that the energy of that motions is zero, that the moment of inertia grows like t^{4/3}, and that the potential energy decay is like t^{-2/3}. Using Marchal's theorem, which states that minimizers avoid collisions we can deduce as a corollary that there are no complete free time minimizers, i.e. defined on (-∞,+∞).

Bambrila-Paz, L and Rittatore, A (2014).

## The Endomorphisms Monoid of a Homogenous Vector Bundle

Fields Institute of Communications, 71.

In this paper we give some properties of the algebraic and geometric structure of the endomorphisms monoid of a homogeneous vector bundle.

Abadie, F, Dokuhcaev, M, Exel, R, and Simón, JJ (2014).

## Morita equivalence of partial group actions and globalization

Transactions of the American Mathematical Society.

Treibich, A (2014).

## Hyperelliptic d-osculating covers and rational surfaces

Bulletin de la Société Mathématique de France.

Treibich, A (2014).

## Systems of polynomial equations defining hyperelliptic d-osculating covers

Functional Analisys and Applications.

Pan, I and Rittatore, A (2014).

## Some remarks about the Zariski Topology of the Cremona group

Preprint.

Armentano, D and Shub, M (2013).

## Smale's Fundamental Theorem of Algebra Reconsidered

Foundation of Computational Mathematics, DOI10.1007/s10208-013-9155-y:33.

In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton’s method. In this paper we reconsider his algorithm in the light of work done in the intervening years. Smale’s upper bound esti- mate was infinite average cost. Our’s is polynomial in the Bezout number and the dimension of the input. Hence polynomial for any range of dimensions where the Bezout number is polynomial in the input size. In particular not just for the case that Smale considered but for a range of dimensions as considered by Burgisser–Cucker where the max of the degrees is greater than or equal to n^{1+\epsilon} for some fixed . It is possible that Smale’s algorithm is polynomial cost in all dimensions and our main theorem raises some problems that might lead to a proof of such a theorem.

Armentano, D (2013).

## Complexity of Path-Following Methods for the Eigenvalue Problem

Foundation of Computational Mathematics, (submitted).

A unitarily invariant projective framework is introduced to analyze the complexity of path–following methods for the eigenvalue problem. A condition number, and its relation to the distance to ill–posedness, is given. A Newton map appropriate for this context is defined, and a version of Smale’s γ-Theorem is proven. The main result of this paper bounds the complexity of path–following methods in terms of the length of the path in the condition metric.

Armentano, D and Cucker, F (2013).

## A Randomized Homotopy for the Hermitian Eigenpair Problem

Foundation of Computational Mathematics, (submitted).

We describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. Given an n × n Hermitian matrix A the algorithm returns, almost surely, a pair (λ, v) which approximates, in a very strong sense, an eigenpair of A. We prove that the expected cost of this algorithm, where the expectation is both over the random choices of the algorithm and a probability distribution on the input matrix A, is O(n^4 ), that is, quadratic on the input size. Our result relies on a cost assumption for some pseudo-random number generators whose rationale is argued by us.