Workshop A2 - Computational Algebraic Geometry

Organizers: Marta Casanellas (Universitat Politècnica de Catalunya, Spain) - Agnes Szanto (North Carolina State University, USA) - Thorsten Theobald (Universität Frankfurt, Germany)

View workshop abstracts PDF



July 10, 14:30 ~ 15:20

Symmetric sums of squares over $k$-subset Hypercubes

Rekha Thomas

University of Washington, USA   -

Polynomial optimization over hypercubes has important applications in combinatorial optimization. We develop a symmetry-reduction method that finds sums of squares certificates for non-negative symmetric polynomials over k-subset hypercubes that improves on a technique due to Gatermann and Parrilo. For every symmetric polynomial that has a sos expression of a fixed degree, our method finds a succinct sos expression whose size depends only on the degree and not on the number of variables. Our results relate naturally to Razborov's flag algebra calculus for solving problems in extremal combinatorics. This leads to new results involving flags and their power in finding sos certificates in a finite setting, an angle that had not been explored before.

Joint work with Annie Raymond (University of Washington, USA), James Saunderson (Monash University, Australia) and Mohit Singh (Georgia Institute of Technology, USA).

View abstract PDF

July 10, 15:30 ~ 15:55

Subresultants in multiple roots

Teresa Krick

Universidad de Buenos Aires & CONICET, Argentina   -

I will introduce Sylvester sums for univariate polynomials with simple roots and their classical connection with polynomial subresultants (that can be viewed as a generalization of the Poisson formula for resultants), and then speak about the search of analogous expressions in the case of polynomials with multiple roots, with motivations and examples.

Joint work with Alin Bostan (INRIA Saclay Ile de France, France), Carlos D'Andrea (Universitat de Barcelona, España), Agnes Szanto (North Carolina State University, USA) and Marcelo Valdettaro (Universidad de Buenos Aires, Argentina).

View abstract PDF

July 10, 16:00 ~ 16:25

Quadratic Persistence and Pythagoras Number of Varieties

Greg Blekherman

GeorgiaTech, USA   -

Let $X \subset \mathbf{P}^n$ be a variety. Quadratic persistence of $X$ is the smallest integer $k$ such that the ideal of projection away from $k$ generic points of $X$ contains no quadrics. I will motivate this definition and explain how quadratic persistence captures some geometric properties of a variety. Finally I will explain how quadratic persistence can be used to provide lower bounds for length of sums of squares decompositions.

Joint work with Rainer Sinn (Georgia Tech), Greg Smith (Queens University) and Mauricio Velasco (Universidad de los Andes).

View abstract PDF

July 10, 17:00 ~ 17:25

Algebraic Geometry of Gaussian Graphical Models

Seth Sullivant

North Carolina State University, USA   -

Gaussian graphical models are statistical models widely used for modeling complex interactions between collections of linearly related random variables. A graph is used to encode recursive linear relationships with correlated error terms. These models a subalgebraic subsets of the cone of positive definite matrices, that generalize familiar objects in combinatorial algebraic geometry like toric varieties and determinantal varieties. I will explain how the study of the equations of these models is related to matrix Schubert varieties.

Joint work with Alex Fink (Queen Mary University -- London) and Jenna Rajchgot (University of Saskatchewan).

View abstract PDF

July 10, 17:30 ~ 17:55

Universal Groebner bases and Cartwright-Sturmfels ideals

Elisa Gorla

University of Neuchatel, Switzerland   -

I will introduce a family of multigraded ideals named after Cartwright and Sturmfels, and defined in terms of properties of the multigraded generic initial ideals. By definition, a multigraded ideal I is Cartwright-Sturmfels if it has a radical multigraded generic initial ideal. Our main technical result asserts that the family of Cartwright-Sturmfels ideals is closed under several natural operations, including multigraded linear sections and multigraded eliminations. Connection to universal Groebner bases for different families of ideals will be discussed.

Joint work with Aldo Conca (University of Genoa, Italy) and Emanuela De Negri (University of Genoa, Italy).

View abstract PDF

July 10, 18:00 ~ 18:25

The Chow form of a reciprocal linear space

Cynthia Vinzant

North Carolina State University, USA   -

A reciprocal linear space is the image of a linear space under coordinate-wise inversion. This nice algebraic variety appears in many contexts and its structure is governed by the combinatorics of the underlying hyperplane arrangement. A reciprocal linear space is also an example of a hyperbolic variety, meaning that there is a family of linear spaces all of whose intersections with it are real. This special real structure is witnessed by a determinantal representation of its Chow form in the Grassmannian. In this talk, I will introduce reciprocal linear spaces and discuss the relation of their algebraic properties to their combinatorial and real structure.

Joint work with Mario Kummer (Max Planck Institute, Leipzig, Germany).

View abstract PDF

July 10, 18:30 ~ 18:55

Symmetrizing the matrix multiplication tensor

Jonathan Hauenstein

University of Notre Dame, USA   -

Determining the exponent of matrix multiplication is a central question in algebraic complexity theory. We propose a novel approach to bounding this exponent via the rank of cubic polynomials that are closely related to matrix multiplication. This allows us to exploit the vast literature of the algebraic geometry of cubic hypersurfaces and perform many numerical computations to study the exponent of matrix multiplication.

Joint work with Luca Chiantini (Universita di Siena, Italy), Christian Ikenmeyer (Max Planck Institute for Informatics, Germany), Giorgio Ottaviani (Universita di Firenze, Italy) and J.M. Landsberg (Texas A&M University, USA).

View abstract PDF

July 11, 14:30 ~ 14:55 - Room B5

Factorization of sparse bivariate polynomials

Martín Sombra

ICREA & Universitat de Barcelona, Spain   -

It is expected that, for a given sparse univariate polynomial over the rationals, its non-cyclotomic irreducible factors are also sparse. This is a vague principle that takes a more precise form in an old (and still open) conjecture of Schinzel, on the irreducible factors in families of polynomials with fixed coefficients and varying monomials.

In this talk, I will present a theorem giving an analogue of Schinzel conjecture for polynomials over a function field. This result gives a description of the irreducible factors in families of bivariate polynomials over a field of characteristic zero.

Its proof is based on a toric version of Bertini's theorem.

Joint work with Francesco Amoroso (Université de Caen, France).

View abstract PDF

July 11, 15:00 ~ 15:25 - Room B5

Local equations for equivariant evolutionary models

Jesús Fernández-Sánchez

Universitat Politècnica de Catalunya, Spain   -

Phylogenetic varieties related to equivariant substitution models have been studied largely in the last years. One of the main objectives has been finding a set of generators of the ideal of these varieties, but this has not yet been achieved in some cases (for example, for the general Markov model this involves the open "salmon conjecture") and it is not clear how to use all generators in practice. However, for phylogenetic reconstruction purposes, the elements of the ideal that could be useful only need to describe the variety around certain points of no evolution. With this idea in mind, we produce a collection of explicit equations that describe the variety on a neighborhood of these points. Namely, for any tree on any number of leaves (and any degrees at the interior nodes) and for any equivariant model on any set of states , we compute the codimension of the corresponding phylogenetic variety. We prove that this variety is smooth at general points of no evolution, and provide an algorithm to produce a complete intersection that describes the variety around these points.

Joint work with Marta Casanellas (Universitat Politècnica de Catalunya) and Mateusz Michalek (Polish Academy of Sciences).

View abstract PDF

July 11, 15:30 ~ 15:55 - Room B5

Arithmetically-Free Resolutions of Toric Vector Bundles

Gregory G. Smith

Queen's University, Canada   -

To each torus-equivariant vector bundle over a smooth complete toric variety, we associated a representable matroid (essentially a finite collection of vectors). In this talk, we will describe how the combinatorics of this matroid encodes a resolution of the toric vector bundles by a complex whose terms are direct sums of toric line bundles. We will also outline some applications to the equations and syzygies of smooth projective toric varieties.

View abstract PDF

July 11, 16:00 ~ 16:25 - Room B5

Bounds on the degree of the central curve of semidefinite programming

Elias Tsigaridas

INRIA Paris, France   -

We present bounds on the algebraic degree of the central curve of semidefinite programming (SDP). We derive the bounds based on the degree of polynomial systems that exploit the primal and dual formulation of SDP.

Joint work with Jean-Charles FAUGERE (INRIA, LIP6/UMPC) and Mohab SAFEY EL DIN (LIP6/UPMC, INRIA).

View abstract PDF

July 11, 17:00 ~ 17:25 - Room B5

Automated Reasoning Tools in GeoGebra

Tomas Recio

Universidad de Cantabria, Spain   -

GeoGebra (see Hohenwarter, 2002)   is a dynamic geometry software with tenths of millions users worldwide. Despite its original merely graphical flavor, successful attempts were performed during the last years towards combining standard dynamic geometry approaches with automated reasoning methods using computer algebra tools.  Since Automated Theorem Proving (ATP) in geometry has reached a rather mature stage, an Austro-Spanish group (see Botana & al., 2015) started in 2010 a project of incorporating and testing a number of different automated geometry provers in GeoGebra. This collaboration was built upon previous approaches and achievements of a large community of researches, involving different techniques from algebraic geometry and computer algebra. Moreover, various symbolic computation, open source, packages have been involved, most importantly the Singular (Decker & al., 2012) and the Giac (Parisse, 2013) computer algebra systems. See Kovács, 2015a and Kovács, 2015b for a more detailed overview. As a result of this collaboration, we have been able to recently announce the implementation (Abanades et. al. 2016) of three automated reasoning tools (ART) in GeoGebra, all of them working in the desktop, web, tablet or smartphone versions of GeoGebra: the automated derivation of (numerical) properties in a given construction, by means of the Relation Tool; the verification of the symbolic truth of these properties, by means of the Prove and ProveDetails tools;  and the discovery of missing hypotheses for a conjectural statement to hold true, through the LocusEquation tool. The Relation Tool, in its original form, allows selecting two geometrical objects in a construction, and then to check for typical relations among them, including perpendicularity, parallelism, equality or incidence. Finally, it shows a message box with the obtained information (yes/no the relation holds). GeoGebra version 5 now displays an extra button in the message box with the caption “More...” which results in some symbolic computations when pressed. That is, by pressing the “More...” button, GeoGebra's Automatic Theorem Proving subsystem starts and selects (by some heuristics) an appropriate prover method to decide if the numerically obtained property is indeed absolutely true in general. The current version of GeoGebra is capable of choosing a) the Gröbner basis method, b) Wu's characteristic method, c) the area method, or d) sufficient number of exact checks, deterministic method (see Kovacs et. al. 2012, Weitzhofer, 2013), as the underlying ATP technique addressed by the Prove command. See Kovacs 2015b for more details on this portfolio prover. Moreover, if the conjectured relation does not (mathematically speaking) hold, the first two methods can determine some geometrical extra-conditions, which need to hold true in order to make the given statement generally correct, either using the ProveDetails tool (in the generally true case) or the LocusEquation tool (in the generally false case). In the talk I will outline, through examples, some features of the ART in GeoGebra, providing some details on the underlying algebraic methods and reporting on our current work-in-progress concerning this topic.

Acknowledgement: Partially supported by the Spanish Ministerio de Economía y Competitividad and by the European Regional Development Fund (ERDF), under the Project MTM2014-54141-P.

References: 1) Abánades, M.A., Botana, F., Kovács, Z., Recio, T., & Sólyom-Gecse, C. (2016). Development of automatic reasoning tools in GeoGebra. In: ACM Communications in Computer Algebra 50(3):85-88, November 2016.  2) Botana, F., Hohenwarter, M., Janicic, P., Kovács Z., Petrovic, I., Recio, T., Weitzhofer, S. (2015). Automated theorem proving in GeoGebra: current achievements. Journal of Automated Reasoning (Vol. 5, Number 1, pp. 39-59). 3) Decker, W., Greuel, G.M., Pfister, G. & Schönemann, H. (2012). Singular 3-1-6 –A computer algebra system for polynomial computations. 4) Hohenwarter, M. (2002). Ein Softwaresystem für dynamische Geometrie und Algebra der Ebene. Master’s thesis. Salzburg: Paris Lodron University. 5) Kovács, S., Recio, T., Weitzhofer, S. (2012): Implementing theorem proving in GeoGebra by exact check of a statement in a bounded number of test cases. In: Proceedings EACA 2012, Libro de Resúmenes del XIII Encuentro de Álgebra Computacional y Aplicaciones. Universidad de Alcalá, pp. 123–126. 6) Kovács, Z. (2015a). Computer based conjectures and proofs. Dissertation. Linz: Johannes Kepler University. 7) Kovács, Z. (2015b). The Relation Tool in GeoGebra 5. In Botana, F., Quaresma, P. (Eds.), Post-conference Proceedings of the 10th International Workshop on Automated Deduction in Geometry (ADG 2014), 9-11 July 2014, Lecture Notes in Artificial Intelligence 9201 (pp. 53-71). Springer. 8) Parisse, B. (2013). Giac/Xcas, a free computer algebra system. Available at 9)Weitzhofer, S. (2013): Mechanic proving of theorems in plane geometry. Master’s thesis, Johannes Kepler University, Linz, Austria.

View abstract PDF

July 11, 17:30 ~ 17:55 - Room B5

Degree-Optimal Moving Frames for Rational Curves

Irina Kogan

North Carolina State University, USA   -

We present an algorithm that, for a given vector $\mathbf a$ of $n$ relatively prime polynomials in one variable over an arbitrary field, outputs an $n\times n$ invertible matrix $P$ with polynomial entries, such that it forms a degree-optimal moving frame for the rational curve defined by $\mathbf a$. The first column of the matrix $P$ consists of a minimal-degree Bézout vector (a minimal-degree solution to the univariate effective Nullstellensatz problem) of $\mathbf a$, and the last $n-1$ columns comprise an optimal-degree basis, called a $\mu$-basis, of the syzygy module of $\mathbf a$. To develop the algorithm, we prove several new theoretical results on the relationship between optimal moving frames, minimal-degree Bézout vectors, and $\mu$-bases. In particular, we show how the degree bounds of these objects are related. Comparison with other algorithms for computing moving frames and Bézout vectors will be given, however, we are currently not aware of another algorithm that produces an optimal degree moving frame or a Bézout vector of minimal degree.

Joint work with Hoon Hong (North Carolina State University, USA), Zachary Hough (North Carolina State University, USA) and Zijia Li (Joanneum Research, Austria).

View abstract PDF

July 11, 18:00 ~ 18:25 - Room B5

A Positivstellensatz for Sums of Nonnegative Circuit Polynomials

Timo de Wolff

TU Berlin, Germany   -

In 2014, Iliman and I introduced an entirely new nonnegativity certificate based on sums of nonnegative circuit polynomials (SONC), which are independent of sums of squares. We successfully applied SONCs to global nonnegativity problems.

In 2016, Dressler, Iliman, and I proved a Positivstellensatz for SONCs, which provides a converging hierarchy of lower bounds for constrained polynomial optimization problems. These bounds can be computed efficiently via relative entropy programming.

In this talk, I will give an overview about sums of nonnegative circuit polynomials, introduce our Positivstellensatz, and if time permits, briefly explain the connection to relative entropy programming.

Joint work with Mareike Dressler (Goethe University Frankfurt), Sadik Iliman.

View abstract PDF

July 12, 14:30 ~ 14:55 - Room B5

Computational geometry of real plane curves

Daniel Plaumann

University of Dortmund, Germany   -

Deriving the geometric and topological properties of a curve in the real projective plane from its defining equation leads to many interesting and challenging computational problems in real algebraic geometry. Such problems concern the configuration of the ovals, singularities, the flex and bitangent lines, as well as various representation theorems. In this talk, we will focus on the case of quartics and sextics and highlight some recent experimental results.

Joint work with Nidhi Kaihnsa (MPI Leipzig), Mario Kummer (MPI Leipzig), Mahsa Sayyary Namin (MPI Leipzig) and Bernd Sturmfels (UC Berkeley / MPI Leipzig).

View abstract PDF

July 12, 15:00 ~ 15:25 - Room B5

On the solutions to polynomials systems arising from chemical reaction networks

Elisenda Feliu

University of Copenhagen, Denmark   -

Under the law of mass-action, the dynamics of the concentration of biochemical species over time is modelled using polynomial dynamical systems, which often have parameterised coefficients. The steady states, or equilibrium points, of the system are the solutions to a parameterised family of systems of polynomial equations. Because only nonnegative concentrations are meaningful in applications, one aims at finding the nonnegative solutions to these systems. In the talk I will present a result on finding parameter regions for which the steady state equations admit multiple solutions, and discuss the existence of positive parameterisations of the set of steady states.

Joint work with Carsten Conradi (HTW Berlin), Maya Mincheva (Northern Illinois University), Meritxell Sáez (University of Copenhagen), Carsten Wiuf (University of Copenhagen).

View abstract PDF

July 12, 15:30 ~ 15:55 - Room B5

Computing Simple Multiple Zeros of Polynomial Systems

Lihong Zhi

Chinese Academy of Sciences, China   -

Given a polynomial system $f$ associated with a simple multiple zero $x$ of multiplicity $\mu$, we give a computable lower bound on the minimal distance between the simple multiple zero $x$ and other zeros of $f$. If $x$ is only given with limited accuracy, we propose a numerical criterion that $f$ is certified to have $\mu$ zeros (counting multiplicities) in a small ball around $x$. Furthermore, for simple double zeros and simple triple zeros whose Jacobian is of normalized form, we define modified Newton iterations and prove the quantified quadratic convergence when the starting point is close to the exact simple multiple zero. For simple multiple zeros of arbitrary multiplicity whose Jacobian matrix may not have a normalized form, we perform unitary transformations and modified Newton iterations, and prove its non-quantified quadratic convergence and its quantified convergence for simple triple zeros.

Joint work with Zhiwei Hao, Wenrong Jiang (Chinese Academy of Sciences) and Nan Li (Tianjin University, China).

View abstract PDF

July 12, 16:00 ~ 16:25 - Room B5

Distinguishing phylogenetic networks

Elizabeth Gross

San Jose State University, USA   -

Phylogenetic networks are increasingly becoming popular in phylogenetics since they have the ability to describe a wider range of evolutionary events than their tree counterparts. In this talk, we discuss Markov models on phylogenetic networks, i.e. directed acyclic graphs, and their associated algebra and geometry. In particular, assuming the Jukes-Cantor model of evolution and restricting to one reticulation vertex, using tools from computational algebraic geometry we show that the semi-directed network topology of $k$-cycle networks with $k \geq 4$ is generically identifiable.

Joint work with Colby Long (Mathematical Biosciences Institute).

View abstract PDF

July 12, 17:00 ~ 17:50 - Room B5

The Euclidean distance degree of orthogonally invariant matrix varieties.

Giorgio Ottaviani

Università di Firenze, Italy   -

The closest orthogonal matrix to a real matrix A can be computed by the Singular Value Decomposition of A. Moreover, all the critical points for the Euclidean distance function from A to the variety of orthogonal matrices can be found in a similar way, by restriction to the diagonal case. The number of these critical points is the Euclidean distance degree. We generalize this result to any orthogonally invariant matrix variety. This gives a new perspective on classical results like the Eckart-Young Theorem and also some new results, e.g. on the essential variety in computer vision. At the end of the talk we will touch the case of tensors.

Joint work with Dmitriy Drusvyatskiy (University of Washington, Seattle, USA), Hon-Leung Lee (University of Washington, Seattle, USA) and Rekha R. Thomas (University of Washington, Seattle, USA).

View abstract PDF

July 12, 18:00 ~ 18:25 - Room B5

Solving the Rational Hermite Interpolation Problem

Carlos D'Andrea

Universitat de Barcelona, Spain   -

The Rational Hermite Interpolation Problem is an extension of the classical Polynomial Interpolation one, and there are several approaches to it: Euclidean algorithm, Linear Algebra with structured matrices, barycentric coordinates, orthogonal polynomials, computation of syzygies,.... We will review some of these methods along with the study of their complexity.

Joint work with Teresa Cortadellas (Universitat de Barcelona) and Eul\`alia Montoro (Universitat de Barcelona).

View abstract PDF



Angles and dimension: Estimating local dimensions from a dataset

Mateo Diaz

Cornell University, USA   -

Given a subvariety $\mathcal{Z}$ of $\mathbb{R}^n$, we want to determine its dimension from an independent sample of points $\mathbf{p}_1, \mathbf{p}_2, \dots, \mathbf{p}_n$ according to some probability distribution supported on $\mathcal{Z}$. Recall that there are many varieties which are connected but not equidimensional (think for instance of the union of a plane and a line which intersects the plane transversely). When considering these examples it is natural to think of dimension as a local concept. In this work, we address the following problem: How to estimate the dimension $d$ of a variety at a given point $\mathbf{p}$ from the sample? Assuming that $\mathbf{p}$ is not a singularity point of $\mathcal{Z}$, we define a statistic based on pairwise angles between data points, that only depends on $d$. Due to its simple description we are able to compute its mean and variance, in closed-form, for a specific dimension. Which allows us to develop a test to estimate the dimension, we prove that under mild assumptions our estimate is correct with high probability if the sample size is at least a constant multiple of the dimension at $\mathbf{p}$. We also provide experimental results that support our claims.

Joint work with Adolfo Quiroz (Universidad de los Andes, Colombia) and Mauricio Velasco (Universidad de los Andes, Colombia).

View abstract PDF

Gr\"obner bases of neural ideals

Rebecca E. Garcia

Sam Houston State University, USA   -

A major area in neuroscience is the study of how the brain processes spatial information. Neurons in the brain represent external stimuli via neural codes. These codes often arise from regions of space called receptive fields: each neuron fires at a high rate precisely when the animal is in the corresponding receptive field. Much research in this area has focused on understanding what features of receptive fields can be extracted directly from a neural code. In particular, Curto, Itskov, Veliz-Cuba, and Youngs recently introduced the concept of neural ideal, which is an algebraic object that encodes the full combinatorial data of a neural code. Every neural ideal has a particular generating set, called the canonical form, that directly encodes a minimal description of the receptive field structure intrinsic to the neural code. On the other hand, for a given monomial order, any polynomial ideal is also generated by its unique (reduced) Gr\"obner basis with respect to that monomial order. How are these two types of generating sets, canonical forms and Gr\"obner bases, related? Our main result states that if the canonical form of a neural ideal is a Gr\"obner basis, then it is the universal Gr\"obner basis (that is, the union of all reduced Gr\"obner bases). Furthermore, we prove that this situation --- when the canonical form is a Gr\"obner basis --- occurs precisely when the universal Gr\"obner basis contains only pseudo-monomials (certain generalizations of monomials). Our results motivate two questions: (1) When is the canonical form a Gr\"obner basis? (2) When the universal Gr\"obner basis of a neural ideal is not a canonical form, what can the non-pseudo-monomial elements in the basis tell us about the receptive fields of the code? We give partial answers to both questions. Along the way, we develop a representation of pseudo-monomials as hypercubes in a Boolean lattice.

Joint work with Luis David Garcia Puente (Sam Houston State University, USA), Ryan Kruse (Central College, USA), Jessica Liu (Bard College, USA), Dane Miyata (Willamette University, USA), Ethan Petersen (Rose-Hulman Institute of Technology, USA), Kaitlyn Phillipson (St. Edward’s University, USA) and Anne Shiu (Texas A\&M University, USA).

View abstract PDF

Multilinear Algebra for Phylogenetic Reconstruction

Marina Garrote-López

Universitat politècnica de Catalunya, Spain   -

The objective of phylogenetic reconstruction is recovering the ancestral relationships among a group of current species. In order to reconstruct phylogenetic trees it is necessary to model evolution adopting a parametric statistic model which allows us to define a joint distribution at the leaves of the trees. Using theses models one is able to deduce polynomial relationships between the parameters, known as phylogenetic invariants. One can study these polynomials and the geometry of the algebraic varieties that arise from them and use it to reconstruct phylogenetic trees. The framework of our research is to study and analyse some transformations of these joint distributions, the characterizations of stochasticity of the parameters for the general Markov model and understand the relationship between phylogenetics and algebraic techniques to recover phylogenetic trees from real data. Our main goal is to use phylogenetic invariants over the joint distribution transformations to give new information to phylogenetic reconstruction methods and to infer new methods for phylogenetic inference.

View abstract PDF

Imaginary Projections of (Homogeneous) Polynomials

Thorsten Jörgens

Goethe University Frankfurt, Germany   -

We introduce the imaginary projection of a general multivariate polynomial $f\in\mathbb{C}[\mathbf{z}]$ as the projection of the variety of $f$ onto its imaginary part, $\mathcal{I}(f) \ = \ \{\text{Im}(\mathbf{z}) \, : \, \mathbf{z} \in \mathcal{V}(f) \}$. Since a polynomial $f$ is stable if and only if $\mathcal{I}(f) \cap \mathbb{R}_{>0}^n \, = \, \emptyset$, the notion offers a novel geometric view underlying stability questions of polynomials. As a first fundamental geometric property we show that the connected components of the complement of the imaginary projections are convex.

For homogeneous (and hyperbolic) polynomials, we study the relation between imaginary projections and hyperbolicity cones. Hyperbolic polynomials became of interest in hyperbolic programming, where the set of feasible solutions is a hyperbolicity cone of a hyperbolic polynomial. It is a natural generalization of semidefinite programming.

Building upon this, for the homogeneous case we characterize the boundary of imaginary projections and we discuss a connection between hyperbolicity cones and certain components in the complement of the imaginary projection of inhomogeneous polynomials.

Joint work with Thorsten Theobald (Goethe University Frankfurt, Germany) and Timo de Wolff (Texas A&M University, USA).

View abstract PDF

The lexicographic degree of the first two-bridge knots

Pierre-Vincent Koseleff

UPMC - Sorbonne Universités (Paris 6), France   -

We study the degree of polynomial representations of knots. We give here the lexicographic degree of all two-bridge knots with 11 or fewer crossings. The proof uses the braid theoretical method developed by Orevkov to study real plane curves [BKP2], isotopies on trigonal space curves and explicit parametrizations obtained by perturbing a triple point.

The lexicographic degree of a knot $K$ is the minimal multidegree, for the lexicographic order, of a polynomial knot whose closure in $S_3$ is isotopic to $K$.

We show that this degree is not necessarily obtained for curves that have the minimal number of real crossings. For example the knot $8_6$ has minimal degree $(3,10,14)$ that corresponds to a diagram with 9 crossings while the alternating diagram with 8 crossings has degree at least $(3, 11, 13)$.

Here we study two-bridge knots, namely those that admit a trigonal parametrization, that is to say a polynomial parametrization in degree $(3,b,c)$. We show the sharp lower bound $c \geq 3N - b$, where $N$ is the crossing number of $K$.

Lower bounds for $b$ are obtained by considering first Bézout-like conditions on the real crossings of the plane projection.

We also use the associated 3-strings braid associated to any trigonal algebraic plane curve that must be quasi-positive [Or2].

Upper bounds are given by previous constructions on Chebyshev diagrams [KP3] and slide isotopies on knot diagrams : isotopies for which the number of crossings never increases [BKP1].

In addition, we introduce a new reduction $R$ on trigonal plane curves. In many cases, the use of this reduction allows to subtract three to the number of crossings of the diagram and to the degree $b$, thanks to a result on real pseudoholomorphic curves deduced from [Or2]. On the other hand we show that we can explicitly give a polynomial curve of degree $(3, d+3)$ from a polynomial curve of degree $(3, d)$ by adding a triple point and perturbing the singularity.

We obtain the lexicographic degree for some infinite familes of two-bridge knots (the torus knots and generalized twist-knots) and for all two-bridge knots with 11 or fewer crossings. For every considered knot, we compute first an upper bound $b_C$ for $b$, using Chebyshev diagrams. We compute all diagrams with $b_C -1$ or fewer crossings that cannot be reduced by slide isotopies. Most of these diagrams may be reduced using $R$-reductions. For those that cannot be reduced, we consider all possible schemes corresponding to admissible rational algebraic curve of degree $(3,b)<(3,b_C)$ and compute their associated braids, that must be quasi-positive.


[BKP1] E. Brugallé, P. -V. Koseleff, D. Pecker. Untangling trigonal diagrams, Journal Of Knot Theory And Its Ramificationsc (JKTR), 25(7) (2016), 10p.

[BKP2] E. Brugallé, P. -V. Koseleff, D. Pecker, On the lexicographic degree of two-bridge knots, Journal Of Knot Theory And Its Ramifications (JKTR), 25(7) (2016), 17p.

[KP3] P. -V. Koseleff, D. Pecker, Chebyshev diagrams for two-bridge knots, Geom. Dedicata 150 (2010), 405–425

[Or2] S. Yu. Orevkov. Classification of flexible $M$-curves of degree 8 up to isotopy, Geom. Funct. Anal., 12(4), 723–755, 2002.

Joint work with Erwan Brugallé (Centre de Mathématiques Laurent Schwartz, CMLA, École Polytechnique, France) and Daniel Pecker (UPMC - Sorbonne Universités, Paris 6, France).

View abstract PDF

The embedding problem for Kimura nucleotide substitution models

Jordi Roca-Lacostena

Universitat Politècnica de Catalunya, Spain   -

In this poster we present the embedding problem for nucleotide substitution models from a biological and algebraic point of view. More precisely, we focus on the family of Kimura 3-parameters model and sub-models and we give a complete characterization of embeddable matrices for biological meaningful matrices.

Joint work with Jesús Fernández-Sánchez (Universitat Politècnica de Catalunya, Spain) and Marta Casanellas (Universitat Politècnica de Catalunya, Spain).

View abstract PDF

Multiprojective witness sets and a trace test

Jose Rodriguez

University of Chicago, USA   -

In the field of numerical algebraic geometry, positive-dimensional solution sets of systems of polynomial equations are described by witness sets. We define multiprojective witness sets which will encode the multidegree information of an irreducible multiprojective variety. Our main results generalize the regeneration solving procedure, a trace test, and numerical irreducible decomposition to the multiprojective case. Examples in tensor decomposition and kinematics are used to illustrate the approach.

Joint work with Jonathan Hauenstein (University of Notre Dame).

View abstract PDF

Elimination in steady state equations of chemical reaction networks

Meritxell Sáez Cornellana

University of Copenhagen, Denmark   -

The steady states of a chemical reaction network with mass-action kinetics are solutions to a system of polynomial equations. Even for small systems, finding the steady states of the system is a very demanding task and therefore methods that reduce the number of variables are desirable. In [FW] the authors give one such method, in which so-called non-interacting species are eliminated from the system of steady state equations.

We extend this method for the elimination of what we call reactant non-interacting species and give some conditions that ensure the positivity of the elimination obtained, that is, for positive values of the reaction rate constants and the non-eliminated species, we ensure that the eliminated species are positive as well. In particular, if enough species can be eliminated, then this method provides a parametrisation of the positive part of the steady state variety. Such a parametrisation can be used, for instance, to study the number of steady states in each linear invariant subspace defined by the conservation laws [CFMW].

[FW] Feliu, Wiuf: Variable elimination in chemical reaction networks with mass-action kinetics. SIAM J. APPL. MATH.

[CFMW] Conradi, Feliu, Mincheva, Wiuf. Identifying parameter regions for multistationarity. (2016) arXiv:1608.03993.

Joint work with Elisenda Feliu (University of Copenhagen, Denmark) and Carsten Wiuf (University of Copenhagen, Denmark).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.