Please Note: There will be a pre-seminar 10:55-11:15 in Skiles 005.
TBA
Please Note: There will be a pre-seminar 10:55-11:25 in Skiles 005.
For the classical actions of the linear algebraic groups in characteristic zero (special linear, orthogonal, symplectic) we calculate the arithmetic rank of Hilbert's nullcone ideals via a general theorem on pure subrings. Then, in positive charactersitic, we discuss topological methods that lead to an inequality between arithmetic rank of the nullcone ideal and the dimension of the invariant ring, that can be used to replace the argument of the pure subring (which is false in positive characteristic). In the outline of his argument we spend most of the time over the complex numbers, for better comfort. This is a report on a paper with J Jeffries, V Pandey and A K Singh.
Please Note: There will be a pre-seminar 10:55-11:15 in Skiles 005.
At its core, numerical algebraic geometry is the business of solving zero-dimensional polynomial systems over the complex numbers. Thanks to incredibly fast state-of-the-art software implementations, the bottleneck in these algorithms has shifted from computation time to memory usage.
To address this, recent work has introduced iterator datatypes for solution sets. An iterator represents a list by storing a single element and providing a mechanism to obtain the next one, thereby reducing memory overhead.
In this talk, we present our design of 'homotopy iterators' and 'monodromy coordinates', two iterator datatypes based on the most widely used numerical methods for solving polynomial systems. We highlight the substantial benefits of this low-memory perspective through several iterator-friendly adaptations of existing algorithms, including parameter space searches, data compression, and certification.
This talk features joint work with subsets of Paul Breiding, Hannah Friedman, and David K. Johnson.
Please Note: There will be a pre-seminar 10:55-11:15 in Skiles 005.
Suppose $f$ is a univariate polynomial with integer coefficients of absolute value at most $H$, exactly $t$ monomial terms, and degree $d$. Suppose also that $p,q$ are integers of absolute value at most $H$. Then one can determine the sign of $f(p/q)$ in time $(d^3 \log H)^{2+\epsilon}$, by combining work of Liouville from about 170 years ago, work of Mahler from about 60 years ago, work of Neff, Reif, and Pan from about 30 years ago, and more recent refinements.
However, when $t$ is small, one can do much better: When $t=2$, one can determine the sign of $f(p/q)$ in time $\log^5(dH)$, via work of Baker from about 55 years ago. Koiran asked, around 2016, about the $t=3$ case, after proving new bounds on the minimal separation of complex roots of univariate trinomials.
We make progress on Koiran's question by giving a new, dramatically faster algorithm for solving univariate trinomials over the real numbers. The key innovation is a new family of non-hypergeometric series for the roots of $f$ when $f$ is close to having a degenerate root. This is joint work with Emma Boniface and Weixun Deng.
Convex relaxations are of central interest in optimization, and it is typically challenging to determine whether a given convex relaxation will be tight for a given problem. We introduce a topological framework for analyzing situations in which a constrained optimization problem over a nonconvex set (such as a manifold) has a tight convex relaxation. In particular, we give a criterion for the existence of such a tight convex relaxation in terms of the existence of a continuous function of Lagrange multipliers for the constrained problem maximizing the corresponding Lagrangian. We call such a function a Lagrangian dual section, in reference to the topological notion of a section of a bundle.
As a corollary of this result, we will give new criteria for the exactness of SDP relaxations for Stiefel manifold optimization and inverse eigenvalue problems in terms of linear subspaces of matrices satisfying spectral properties such as being nonsingular. We will also illustrate a homotopy continuation style algorithm with global optimality guarantees with applications to the unbalanced procrustes problem.
Please Note: There will be a pre-seminar 10:55-11:15 in Skiles 005.
Proving conjectures is an essential part of our job as mathematicians. Another essential part is to come up with plausible conjectures. In the talk, we focus on this part. We present a new twist to an old method from computer algebra for detecting recurrence equations of infinite sequences of which only the first few terms are known. By applying this new version systematically to all the entries of the Online Encyclopedia of Integer Sequences, we detected a number of potential recurrence equations that could not be found by the classical methods. Some of these have meanwhile been proven. This is joint work with Christoph Koutschan.
====(Below is the information on the pre-talk.)====
Titile: Lattice Reduction
Abstract: It is well known how to go from an exact number (e.g. 1/3) into an approximation (e.g. 0.333). But how can we get back? At first glance, this seems impossible, because some information got lost during the approximation. However, there are techniques for doing this and similar seemingly magic tricks. We will discuss some such tricks that rely on an algorithm for finding short vectors in integer lattices.
We study the problem of computing the convex hull of a set $S \subseteq \mathbb{R}^n$ defined by three quadratic inequalities. A simple way to generate inequalities valid on $S$ is to take nonnegative linear combinations, called aggregations, of the defining inequalities. We study the set defined by aggregations using topological duality results for quadratic inequalities. In the case of three quadratic inequalities, this relates aggregations to an algebraic curve. This viewpoint allows us to find new cases for which the convex hull of $S$ can be recovered by aggregations. Joint work with Greg Blekherman.
Please Note: There will be a pre-seminar 10:55-11:15 in Skiles 005.
MacPhersonians are a combinatorial analog of real Grassmannians defined by oriented matroids. A long standing conjecture says that each MacPhersonian is homotopy equivalent to the corresponding Grassmannian. Pseudolinear Grassmannians are spaces of topological representations of oriented matroids, and these are each homotopy equivalent to the corresponding Grassmannian in rank 3. I will present a good cover of the rank 3 pseudolinear Grassmannian with nerve complex isomorphic to the order complex of the corresponding MacPhersonian, confirming the conjecture in rank 3.
Please Note: There will be a pre-seminar 10:55-11:15 in Skiles 005.
This talk is about an application of combinatorial algebraic geometry to complex/arithmetic dynamics. The n-th Gleason polynomial G_n is a polynomial in one variable with Z-coefficients, whose roots correspond to degree-2 polynomials with an n-periodic ramification point. Per_n is an affine algebraic curve, defined over Q, parametrizing degree-2 rational maps with an n-periodic ramification point. Two long-standing open questions in complex dynamics are: (1) Is G_n is irreducible over Q? (2) Is Per_n connected? We show that if G_n is irreducible over Q, then Per_n is irreducible over C, and is therefore connected. In order to do this, we find a Q-rational smooth point on a projective completion of Per_n — this Q-rational smooth point represents a special degeneration of degree-2 self-maps.
