Session S01 - Computational Algebra and Applications of Algebra
Chair: Alicia Dickenstein (Universidad de Buenos Aires & CONICET, Argentina)
Collaborators: Carina Curto (PSU, USA) - Luis David Garcia-Puente (Sam Houston State University, USA)
Talks
July 28, 15:00 ~ 15:25
Waring decompositions of a general polynomial vector
Giorgio Ottaviani
Università di Firenze, Italy - ottavian@math.unifi.it
Weierstrass canonical form expresses a pair of general quadratical forms as a sum of powers of the same linear forms. It is one of the many displays of the well known Spectral Theorem. The uniqueness is remarkable because it does not hold for a single quadratical form, but it holds for four quadratical forms in three variables. These are called (symultaneous) Waring decompositions, and when uniqueness holds they are canonical. The term identifiable is equivalently used in the applied setting. A classical (sometimes forgotten) Theorem by Roberts gives a similar canonical form for a pair given by two forms of degrees 2 and 3 in three variables, this result has a natural Euclidean meaning. We have found another canonical form, likely the last one, for three forms of degrees 3, 3, 4 in three variables.
Joint work with Elena Angelini (Università di Siena, Italy), Francesco Galuppi (Università di Ferrara, Italy) and Massimiliano Mella (Università di Ferrara, Italy).
July 28, 15:30 ~ 15:55
Varieties of apolar subschemes of toric surfaces
Nelly Villamizar
RICAM- Austrian Academy of Sciences, Austria - nelly.villamizar@oeaw.ac.at
The variety of sums of powers associated to a homogeneous polynomial describes the additive decompositions of the polynomial into powers of linear forms. These polynomial decompositions appear in several areas such as representation theory, coding theory, signal processing, data analysis, and algebraic statistics.
One of the most useful tools to study varieties of sums of powers is apolarity. This notion is originally related to the action of differential operators on the polynomial ring. It can be generalized in terms of the Cox ring of a variety, and in this way varieties of sum of powers are a special case of varieties of apolar schemes. In this talk I will present this generalization and examples of such varieties in the case of toric surfaces, when the Cox ring is particularly well-behaved.
Joint work with Kristian Ranestad (University of Oslo, Norway) and Matteo Gallet (RICAM-Austrian Academy of Sciences).
July 28, 16:00 ~ 16:25
Resultants modulo p
Carlos D'Andrea
Universitat de Barcelona, Spain - cdandrea@ub.edu
Several problems in elimination theory involving arithmetic over the integers (like resultants, the Nullstellensatz, etc) have as an outcome an integer number which if it is not zero modulo a prime p, often imply that classical results over the complex number (dimension, number of zeroes, etc.) "descend" to the residual field. But what happens when p does divide this number? In this talk, we will show that in the case of multivariate resultants, if the input system has a finite number of zeroes modulo p, then p powered to this cardinality (counted with multiplicities) divides the resultant.
Joint work with Martin Sombra (ICREA & Universitat de Barcelona).
July 28, 16:30 ~ 16:55
Sums of squares and the geometry of syzygies
Mauricio Velasco
Universidad de la República (CURE) y Universidad de los Andes, Uruguay / Colombia - mvelasco@cmat.edu.uy
Let $X\subseteq \mathbb{P}^n$ be a reduced scheme over the reals defined by an ideal $I_X$. We show that the number of steps for which the minimal free resolution of $I_X$ is linear is a lower bound for the next-to-minimal rank of extreme rays of the cone dual to the sums of squares in $X$. As a consequence, we obtain:
(1) A complete classification of totally real reduced schemes for which nonnegative quadratic forms are sums of squares.
(2) New certificates of exactness for semidefinite relaxations of polynomial optimization problems on projective varieties.
Joint work with Greg Blekherman (Georgia Tech, USA) and Rainer Sinn (Georgia Tech, USA).
July 28, 17:30 ~ 17:55
Computing the Homology of Real Projective Sets
Teresa Krick
UBA & CONICET, Argentina - krick@dm.uba.ar
We describe and analyze a numerical algorithm for computing the homology of real projective varieties. Its cost depends on the condition of the input as well as on its size: it 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.
Joint work with Felipe Cucker (City University of Hong Kong, China) and Michael Shub (City University of New York, USA).
July 28, 18:00 ~ 18:25
Critical points via Monodromy and Numerical Algebraic Geometry
Abraham Martin del Campo
Conacyt - CIMAT, Mexico - abraham.mc@cimat.mx
In statistics and other applications, we usually have data collected from an experiment or an observation, and we expect this data to follow a model. Many of these models can be interpreted as solutions to a polynomial system, and a fundamental problem is to find the point in the model that best explains the data. In statistics, this is the point that maximizes the Likelihood function.
It is usually a challenge to find solutions to a polynomial equation that are meaningful to the original problem in applications. A common approach is to relax the original problem to allow complex solutions, as in this cases, many algebraic methods can be used.
In this talk, I will introduce an algorithm that uses tools from Numerical Algebraic Geometry to find the critical points of a distance function, and discuss other implications concerning its real solutions.
Joint work with Jose I. Rodriguez (University of Chicago, USA).
July 28, 18:30 ~ 18:55
Numerically computing Galois groups
Jose Rodriguez
University of Chicago, USA - joisro@uchicago.edu
The Galois/monodromy group of a family of equations (or of a geometric problem) is a subtle invariant that encodes the structure of the solutions. In this talk, we will use numerical algebraic geometry to compute Galois groups. Our algorithm computes a witness set for the critical points of our family of equations. With this witness set, we use homotopy continuation to construct a generating set for the Galois group. Examples from optimization will be stated (maximum likelihood estimation and formation shape control).
Joint work with Jonathan Hauenstein (University of Notre Dame) and Frank Sottile (Texas A&M).
July 28, 19:00 ~ 19:25
Computational algebra for the working mathematician
Christopher Hillar
University of California, San Francisco, USA - chillar@msri.org
We show how computational algebra can be a powerful tool for the working mathematical scientist through several short stories from theoretical neuroscience, tensor analysis, and algebraic statistics. We also speculate about the future of algebra on a computer.
July 29, 15:00 ~ 15:25
Dowker complex, convex codes, and detecting hidden matrix factorizations.
Vladimir Itskov
The Pennsylvania State University, US - vladimir.itskov@psu.edu
Detecting low-rank structure is often key for understanding data. This task, however, is particularly challenging in the presence of an unknown nonlinearity — i.e., where one must detect the existence of a factorization $C_{il}=f(\sum_{a=1}^d A_{ia}B_{al})$ with small d, where $f(x)$ is an unknown monotone nonlinearity.
$\, $ It turns out that homological features of the Dowker complex associated to the matrix $C$ can be used to detect such a factorization, but the reason is somewhat mysterious. To understand why this works, we consider the relationship between the Dowker complex of $C$ and a convex code associated to the factors A and B. A convex code is a subset of $2^{[n]}$ that arises from intersection patterns of convex sets in some Euclidean space - in this case, the codewords correspond to selected chambers of a hyperplane arrangement. I will give a short introduction to the connection between Dowker complexes, convex codes, and matrix factorizations, reviewing our recent results and some open problems.
Joint work with Chad Giusti (University of Pennsylvania).
July 29, 15:30 ~ 15:55
Toric ideals of neural codes
Nora Youngs
Harvey Mudd College, USA - nyoungs@hmc.edu
A neural code is a collection of codewords (binary vectors) of a given length $n$; it captures the co-firing patterns of a set of neurons. A neural code is convexly realizable if there exist $n$ convex sets in some $\mathbb{R}^d$ so that each codeword in the code corresponds to a unique intersection carved out by the convex sets. There are some methods to determine whether a neural code is convexly realizable; however, these methods generally do not describe how to draw a realization. In this work, we construct toric ideals from neural codes, and we show how these and the related neural ideals are helpful in applying the theory of piercings from the field of information visualization.
Joint work with Elizabeth Gross (San Jose State University) and Nida Obatake (San Jose State University).
July 29, 16:00 ~ 16:25
Algebraic signatures of convex and non-convex neural codes
Anne Shiu
Texas A&M University, USA - annejls@math.tamu.edu
Neural codes allow the brain to represent, process, and store information about the world. Combinatorial codes, comprised of binary patterns of neural activity, encode information via the collective behavior of populations of neurons. A code is called convex if its codewords correspond to regions defined by an arrangement of convex open sets in Euclidean space. Convex codes have been observed experimentally in many brain areas, including sensory cortices and the hippocampus, where neurons exhibit convex receptive fields. What makes a neural code convex? That is, how can we tell from the intrinsic structure of a code if there exists a corresponding arrangement of convex open sets? This talk describes how to use tools from combinatorics and commutative algebra to uncover a variety of signatures of convex and non-convex codes.
Joint work with Carina Curto (Pennsylvania State University), Elizabeth Gross (San Jose State University), Jack Jeffries (University of Michigan), Katherine Morrison (University of Northern Colorado), Mohamed Omar (Harvey Mudd College), Zvi Rosen (University of Pennsylvania) and Nora Youngs (Harvey Mudd College).
July 29, 16:30 ~ 16:55
The structure of MESSI biological systems
Mercedes Pérez Millán
Universidad de Buenos Aires, Argentina - mpmillan@dm.uba.ar
We introduce a general framework for biological systems that describe Modifications of type Enzyme-Substrate or Swap with Intermediates, which we call MESSI systems. Many post-translational modification networks are MESSI systems. For example: the motifs in Feliu and Wiuf (2012), sequential distributive and processive multisite phosphorylation networks, phosphorylation cascades, or the bacterial EnvZ/OmpR network. We prove that, under mass-action kinetics, MESSI systems are conservative. We simplify the study of steady states of these systems by explicit elimination of intermediate complexes and we define an important subclass of MESSI systems with toric steady states. We show, for MESSI systems with toric steady states, an algorithm that determines whether the system has the capacity for multistationarity, and when it does, it shows two positive steady states and reaction rate constants that witness multistationarity.
Joint work with Alicia Dickenstein (Universidad de Buenos Aires).
July 29, 17:30 ~ 17:55
On computational aspects of the generalized differential Lüroth's theorem
Gabriela Jeronimo
Universidad de Buenos Aires - CONICET, Argentina - jeronimo@dm.uba.ar
Let $\mathcal{F}$ be a differential field of characteristic $0$, $\mathbf{t} = t_1,\dots, t_m$ a set of differential indeterminates over $\mathcal{F}$, and $\mathcal{F}\langle \mathbf{t} \rangle$ the field of differential rational functions. The generalized differential Lüroth's theorem proposed by Kolchin states that, for every differential subfield $\mathcal{G}$ of $\mathcal{F}\langle \mathbf{t} \rangle$ such that the extension $\mathcal{G}/\mathcal{F}$ has differential transcendence degree $1$, there exists $v\in \mathcal{F}\langle \mathbf{t}\rangle$ with $\mathcal{G} = \mathcal{F} \langle v \rangle$. This result generalizes the differential Lüroth theorem proved by Ritt for $m=1$.
We will discuss effectivity issues of the generalized differential Lüroth theorem. If $\mathcal{G}$ is generated by a finite family of differential rational functions in $\mathcal{F}\langle \mathbf{t} \rangle$ of bounded orders and degrees, we will present upper bounds for the order and the degree of any Lüroth generator $v$ of $\mathcal{G}$ over $\mathcal{F}$. These are the first known bounds for arbitrary $m$ and, in the case $m=1$, they improve the previous degree bounds. In addition, we will show that a Lüroth generator can be computed by means of classical techniques from computer algebra applied to a polynomial ideal associated with the given generators. Finally, we will show how to determine whether a given differentially finitely generated subfield of $\mathcal{F}\langle \mathbf{t} \rangle$ has differential transcendence degree $1$ over $\mathcal{F}$.
Joint work with Lisi D'Alfonso (Universidad de Buenos Aires, Argentina) and Pablo Solernó (Universidad de Buenos Aires - CONICET, Argentina).
July 29, 18:00 ~ 18:25
Arithmetical structures of graphs.
Carlos E. Valencia Oleta
Mathematics department, Cinvestav-IPN, México - cvalencia@math.cinvestav.edu.mx
Given a graph $G=(V,E)$, its generalized Laplacian matrix is the square matrix given by \[ L(G,X_G)_{u,v}= \begin{cases} x_u&\text{if }u=v,\\ -m_{uv}&\text{if }u\neq v, \end{cases} \] where $X_G=\{x_u|u\in V(G)\}$ is the set of indeterminates indexed by the vertices of $G$ and $m_{uv}$ is the number of edges between $u$ and $v$. For any ${\bf d}\in \mathbb{N}^{V}$, let $L(G,{\bf d})$ be the integer matrix that result by making $x_u={\bf d}_u$ on $L(G,X_G)$. An arithmetical graph is a triplet $(G,{\bf d},{\bf r})$ given by a multidigraph $G$ and a pair of vectors $({\bf d},{\bf r})\in \mathbb{N}_+^V\times \mathbb{N}_+^V$ such that $\mathrm{gcd}({\bf r}_v\, | \,v\in V(G))=1$ and \[ L(G,{\bf d}){\bf r}^t={\bf 0}^t. \] Given an arithmetical graph $(G,{\bf d},{\bf r})$ we say that the pair $({\bf d},{\bf r})$ is an arithmetical structure of $G$. The concept of arithmetical graphs was introduced by Lorenzini as some intersection matrices that arise in the study of degenerating curves in algebraic geometry.
Under certain hypothesis, it can be prove that the number of arithmetical structures of $G$ is finite. In this way, let \[ \mathcal{A}(G)=\{({\bf d},{\bf r})\in\mathbb{N}_+^{V(G)}\times \mathbb{N}_+^{V(G)} \,| \,({\bf d},{\bf r})\textrm{ is an arithmetical structure of } G\}. \] In this talk we present a survey of the recent results obtained on arithmetical graphs. For instance we present how behaves $\mathcal{A}(G)$ under some operations of graphs like subdivision of edges, duplication of vertices, etc.
These results allows to compute $\mathcal{A}(G)$ for some families of graphs. For instance it can be prove that the number of arithmetical structures of a path $P_n$ with $n$ vertices is equal to the Catalan number $C_{n-1}$.
July 29, 18:30 ~ 18:55
Tropical Graph Curves
Manjunath Madhusudan
Queen Mary University of London, United Kingdom - m.manjunath@qmul.ac.uk
We study a tropical analogue of the notion of graph curves. Given a connected $3$-regular graph $G$, we define a notion of tropical graph curve associated to $G$ and show their existence when $G$ is a $3$-regular, three-connected planar graph. Furthermore, we realize these tropical graph curves as tropicalizations of graph curves. As an application, for smooth curves with a $3$-regular, three-connected planar graph as their Berkovich skeleton, we construct canonical embeddings whose tropicalization preserves the topology of a Berkovich skeleton.
Posters
Unimodular lattices via $\mathbb{Q}(\zeta_{2^rp}+\zeta_{2^rp}^{-1})$ for $p=3$ and $p=5$
Grasiele Jorge
Federal University of Sao Paulo, Brazil - grajorge@gmail.com
A lattice $\Lambda$ is a discrete additive subgroup of $\mathbb{R}^n$. Lattices have a range of applications in different areas, especially in information theory and more recently in cryptography. Special algebraic lattice constructions can be used to derive certain parameters which are usually difficult to calculate for general lattices such as diversity and minimum product distance, which are important parameters related to the signal transmission error probability over Rayleigh fading channels [3]. In this work we approach algebraic constructions of full diversity unimodular lattices via the twisted embedding, introduced in [1,2], applied to the ring of the integers of $\mathbb{Q}(\zeta_{2^rp}+\zeta_{2^rp}^{-1})$ for $p=3$ and $p=5$ and calculate their minimum product distances. The lattices obtained here are direct sums of rotated versions of the lattices $\mathbb{Z}^8$ and $E_8$.
References
[1] E. Bayer-Fluckiger, Lattices and number fields, Contemporary Mathematics, vol. 241, pp. 69-84, 1999.
[2] E. Bayer-Fluckiger, Ideal lattices, Proceedings of the conference Number theory and Diophantine Geometry, Zurich, 1999, Cambridge Univ. Press, pp. 168-184, 2002.
[3] E. Bayer-Fluckiger, F. Oggier, E. Viterbo, New Algebraic Constructions of Rotated $\mathbb{Z}^{n}$-Lattice Constellations for the Rayleigh Fading Channel, IEEE Transactions on Information Theory, vol. 50, no. 4, pp. 702-714, 2004.
Joint work with Agnaldo José Ferrari (Sao Paulo State University, Brazil).