|
Inverse Moment Problems: the Crossroads of Analysis, Algebra, Discrete Geometry and Combinatorics
(18 Nov 2013 - 25 Jan 2014)
~ Abstracts ~
Separation of singularites of holomorhic functions
Lev Aizenberg, Bar-Ilan University, Israel
A statement is proved on the separation of singularities of holomorphic functions from $H^p$, $p\geq 2$, spaces of strictly pseudoconvex domains.
« Back... Ehrhart polynome: how to compute the highest degree coefficients and the knapsack problem
Velleda Baldoni, University di Roma Tor Vergata, Italy
For a given sequence $\bf{\alpha}=[\alpha_1,\alpha_2,\ldots, \alpha_{N+1}]$ of positive integers we consider the combinatorial function $E(\bf{\alpha},t)$ that counts the number of nonnegative solutions $x_i$ of the equation $\sum_i\alpha_ix_i=t$ where the $t$ is a nonnegative integer. It is well known that $E(\bf{\alpha},t)$ is quasi polynomial function in the variable $t$ of degree $N.$ Our main result is a new algorithm that, for every fixed number $k$, computes in polynomial time the highest $k + 1$ coefficients of the quasi-polynomial $E(\bf{\alpha}, t)$) as step polynomials of $t$ (a simpler and more explicit representation).
« Back... Inverse trigonometric moment problem for piecewise-smooth functions
Dmitry Batenkov, Weizmann Institute of Science, Israel
If a function $f$ is $C^{d}$ and periodic, then the Fourier series of order $N$ approximates $f$ with error at most $O\left(N^{-d-1}\right)$. If, however, $f$ is not smooth even at a single point, the rate of accuracy drops to only $O\left(N^{-1}\right)$. This accuracy problem, also known as the Gibbs phenomenon, is very important in applications, such as spectral methods in PDEs. The following natural question arises: is there a non-linear summation method which restores the asymptotically best possible accuracy $O\left(N^{-d-1}\right)$, by using the a-priori information that $f$ is discontinuous? A certain "algebraic" approach to this problem has been proposed by K.Eckhoff in the 1990s. This approach required a robust solution of a particular system of algebraic equations -- the "Eckhoff system" -- which is a special case of the so-called systems of Prony type, appearing in several other problems of Signal Reconstruction.
In this talk I will present a modified Eckhoff's method which achieves the best possible asymptotic accuracy for the piecewise-smooth inverse trigonometric moment problem. Essentially, this modification boils down to considering the Eckhoff system at an arithmetic progression. Such "arithmetic progression sampling", or "decimation", turns out to be applicable also for the general Prony-type systems, providing a significant improvement in accuracy of reconstruction.
« Back... Growth series of cyclotomic and root lattices
Matthias Beck, San Francisco State University, USA
The coordination sequence of a lattice L encodes the word-length function with respect to a fixed set of monoid generators of L. We investigate the coordination sequences of cyclotomic lattices Z[zeta_m], where zeta_m is a primitive m'th root of unity, and root lattices of type A, C, and D.
Our methods are based on unimodular triangulations of the contact polytope of the lattice, the convex hull of the monoid generators, and combine results from commutative algebra, number theory, and discrete geometry.
This is joint work with Federico Ardila (SF State), Serkan Hosten (SF State), Julian Pfeifle (Barcelona), and Kim Seashore (Berkeley).
« Back... Degree bounds in Hilbert's 17th problem
Greg Blekherman, Georgia Institute of Technology, USA
From Artin's solution of Hilbert's 17th problem it is known that every globally nonnegative polynomial can be written as a sum of squares of rational functions. Equivalently for every nonnegative polynomial f there exists a sum of squares g such that f*g is a sum of squares. However, it is not at all well understood how to bound the degree of the multiplier g. I will describe a simple dimension counting method to find degree bounds for polynomials nonnegative on a zero-dimensional set X and how these bounds have implications for the globally nonnegative case.
« Back... Homogeneous truncated moment problem and positive rank
Greg Blekherman, Georgia Institute of Technology, USA
Let L be a linear functional on the vector space of homogeneous polynomials of degree 2d in n variables. The functional L comes from integration with respect to a measure if and only if L can be written as a positive linear combination of point evaluations. I will call the minimal number of point evaluations needed to express L the positive rank of L. I will discuss finding bounds on the positive rank in terms of the number of variables n and degree 2d and why these bounds are of interest.
« Back... Minimum norm points on polytope boundaries
David Bremner, University of New Brunswick, Canada
Given two sets of vectors in $P, Q \subset \mathbb{R}^d$ the \emph{maximum margin hyperplane} is defined by the solution to the following
\begin{equation*}
\operatorname{margin}(P,Q) = \sup_{w \in \operatorname{bd} \mathbb{B}^*} \inf_{p \in P, q \in Q} \langle\,w,p-q\,\rangle
\end{equation*} where $\mathbb{B}$ is the relevant unit ball.
When $\mathbf{0} \in \operatorname{interior} (P\ominus Q$), margin is dual to finding the smallest translation that makes the two sets separable. It turns out this is defined by the minimum norm point on the boundary of $P \ominus Q$. In this case the feasible region is only piecewise convex, and the problem is NP-hard.
In this talk I will discuss experimental results from some cutting-plane approaches to finding the minimum point on the boundary of a polytope given by its vertices.
Joint work with David Bremner, Yan Cui, Zhan Gao.
« Back... Bounding the convergence of the sum-of-square hierarchy by quantum information techniques
Hsin-wen Chang, Institute of Statistical Science, Taiwan
In this talk I'll show that ideas from quantum information theory, and the study of quantum entanglement, are useful to bound the convergence of the sum-of-square (SOS) hierarchy (aka Lasserre/ Parrilo hierarchy). In particular using a connection between the SOS hierarchy and the idea of k-extendable quantum states [1, 2], together with tools to analyse correlations in quantum states, I'll show how one can obtain quasipolynomial-time algorithms for bilinear optimization problems by bounding the convergence of the SOS hierarchy. I'll also discuss consequences to computing hypercontractive norms and estimating the expansion of small sets in graphs (a problem tightly related to the unique games conjecture). The talk is based on [3, 4, 5].
[1] A. Doherty, P. Parrilo, F. Spedalieri. A complete family of separability criteria. Phys. Rev. A 69, 022308 (2004); arXiv:0308032
[2] A. Doherty, S. Wehner. Convergence of SDP hierarchies for polynomial optimization on the hypersphere. arXiv:1210.5048
[3] B. Barak, F. Brandao, A. Harrow, J. Kelner, D. Steurer, Y. Zhou. Hypercontractivity, Sum-of-Squares Proofs, and their Applications. STOC '12; arXiv:1205.4484
[4] F. Brandao, A. Harrow. Quantum de Finetti Theorems under Local Measurements with Applications. STOC '13; arXiv:1210.6367
[5] F. Brandao, M. Christandl, J. Yard. A quasipolynomial-time algorithm for the quantum separability problem. STOC '11; arXiv:1011.2751
« Back... Numerical reconstruction of convex polytopes from directional moments
Mathieu Collowald, INRIA Sophia Antipolis, France
We reconstruct an n-dimensional convex polytope from the knowledge of its directional moments up to a certain order. The directional moments are related to the projection of the polytope's vertices on the particular direction. To extract the vertex coordinates from the moment information we combine established numerical algorithms such as generalized eigenvalue computation and linear interval interpolation. Numerical illustrations are given for the reconstruction of 2-d and 3-d objects.
« Back... Affine semigroups and polyhedra with prescribed number of lattice points
Jesus De Loera, University of California at Davis, USA
Given a matrix $A \in {\mathbb Z}^{d\times n}$ and a vector $b \in {\mathbb Z}^d$, the classical integer feasibility problem asks whether the system $IP_A(=,b)$
\begin{equation}\label{feas1}
A x = b, \quad x \geq 0, \quad x \in {\mathbb Z}^n\,,
\end{equation}
has a solution or not. There is of course a slightly more general form $IP_A(\leq, b)$ of the problem above
\begin{equation}\label{feas2}
A x \leq b, \quad x \in {\mathbb Z}^n\,.
\end{equation}
The geometric problem is to decide whether a polyhedron contains a lattice point or not. In this talk we think about a generalization that asks when a polytope has at least, at most or exactly $k$-lattice points.
My talk will have four parts:
0) The answer to such questions finds applications in Number theory, Combinatorics, Representation theory, Optimization, & Statistics. I will outline why people should care about this.
1) I present a structure theory that characterizes precisely the set ${\rm Sg}_{\geq k}(A)$ of all vectors $b$ such that the problem $Ax=b, x\geq 0, x\in {\mathbb Z}^n,$ has \emph{at least} $k$-solutions. This set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computation. Similar results can be derived for those right-hand-side vectors that have \emph{exactly} $k$ solutions or \emph{fewer than} $k$ solutions. An important role is played by those $b$ for which $Ax=b$ has no solution, these are the gaps or holes of the semigroup.
2) We explain that, when $n$, $k$ are fixed natural numbers, one can compute in polynomial time an
encoding of ${\rm Sg}_{\geq k}(A)$ as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have exactly $k$ solutions (similarly for at least $k$ or less than $k$ solutions). As an application we prove that the $k$-Frobenius number can be computed in polynomial time in fixed dimension.
3) A key ingredient in all these is our generalization of the very famous Doignon-Bell-Scarf theorem: Given an integer $k$, we prove that there exists a constant $c(k,n)$, depending only on the dimension $n$ and $k$, such that if a polyhedron $\{x : Ax \leq b\}$ contains exactly $k$ integer solutions, then there exists a subset of the rows of cardinality no more than $c(k,n)$, defining a polyhedron that contains exactly the same $k$ integer solutions.
This work is joint work with Iskander Aliev (Cardiff, UK) and Quentin Louveaux (Liege, Belgium)
« Back... Convergence of SDP hierarchies for polynomial optimization on the hypersphere
Andrew Doherty, University of Sydney, Australia
We show how to bound the accuracy of a family of semi-definite programming relaxations for the problem of polynomial optimization on the hypersphere. Our method is inspired by a set of results from quantum information known as quantum de Finetti theorems. In particular, we prove a de Finetti theorem for a special class of real symmetric matrices to establish the existence of approximate representing measures for moment matrix relaxations. (This work is in collaboration with Stephanie Wehner.)
« Back... Space fullerenes a computer search
Mathieu Dutour, Institut Rudjer Boskovic, Croatia
A space fullerene is a periodic tiling of Euclidean space by combinatorial fullerenes. Here we report on the enumeration procedure for the Frank Kasper case. The exposition is useful for other enumeration of Face-to-face periodic tilings in Euclidean 3-sapce
« Back... Covering and Delaunay polytopes in lattices
Mathieu Dutour, Institut Rudjer Boskovic, Croatia
A family of balls in Euclidean space is called a covering if every point belong to at least one ball. We focus here on coverings for which the calls are of the form $x+B(0, R)$ with $x$ belonging to a lattice $L$. The covering radius $r(L)$ is the minimum $R$ such that the balls $x + B(0,R)$ cover the space; it is equal to the maximum radius of the Delaunay polytopes of $L$. We denote by $cov(L)$ the covering density of $L$ and study its geometry, maxima and minima.
The parameter space of Delaunay tesselations are named $L$-types and form a tesselations of the space of positive definite matrices. Over a given $L$-type the minimization problem is a semidefinite problem. This allows us to find new record lattices coverings in dimensions 9 to 15.
The covering function $cov$ has local covering maxima for $n\geq 6$. Those covering maxima are characterized by the notion of perfect and eutactic Delaunay polytopes. By generalizing the root lattices $E_6$ and $E_7$ we find an infinite series of perfect Delaunay polytopes which are covering maxima for $n\geq 6$ and conjecture that they are the ones with highest lattice covering density. This conjecture implies Minkowski conjecture. Also the covering function is a topological Morse function only if $n\leq 3$.
Finally, we give an algorithm for enumerating perfect Delaunay polytopes that uses the Erdahl cone. That is we express the problem as a dual description problem over a non-polyhedral cone. This allows us to find all perfect Delaunay polytopes in dimension $n\leq 7$.
« Back... Irreducibility of some spectral determinants
Andrei Gabrielov, Purdue University, USA
Eigenfunctions of the even quartic oscillator, i.e., Schrodinger operator with an even polynomial potential of degree four, are associated with certain properly embedded infinite planar trees. The braid group action on the trees helps us to understand the dependence of the eigenfunctions and the corresponding eigenvalues on the coefficients of the potential. In particular, we give a rigorous proof of the fact, discovered by Bender and Wu 40 years ago, that the spectral determinant of the even quartic oscillator has exactly two irreducible components. Similar results are obtained for several other one-parametric families of eigenvalue problems. This is joint work with A. Eremenko.
« Back... Lipschitz contact equivalence of functions in two variables
Andrei Gabrielov, Purdue University, USA
We consider germs at the origin in R^2 of continuous functions definable in a polynomially bounded o-minimal structure (e.g., semialgebraic or subanalytic). We construct a complete invariant of an equivalence class of such functions with respect to Lipschitz contact equivalence. This is joint work with L. Birbrair, A. Fernandes, V. Grandjean.
« Back... Classification of spherical quadrilaterals
Andrei Gabrielov, Purdue University, USA
A spherical quadrilateral (membrane) is a bordered surface homeomorphic to a closed disc, with four distinguished boundary points called corners, equipped with a Riemannian metric of constant curvature $1$, except at the corners, and such that the boundary arcs between the corners are geodesic. We discuss the problem of classification of these quadrilaterals and perform the classification up to isometry in the case that at most two angles at the corners are not multiples of $\pi$.
This is a very old problem, related to the properties of solutions of the Heun equation. The corresponding problem for the spherical triangles, related to the properties of solutions of the hypergeometric equation, has been solved by Klein, with some gaps in Klein's classification filled in by Eremenko in 2004. The quadrilateral case for small corners was treated in the Thesis of Smirnov (1918), but for arbitrary corners remains open.
This is joint work with A. Eremenko (Purdue) and V. Tarasov (IUPUI).
« Back... Application of Jacobi's representation theorem to LMC algebras
Mehdi Ghasemi, Nanyang Technological University
Let $A$ be a commutative unital algebra over real numbers and let $\tau$ be a locally multiplicatively convex topology on $A$. We apply T. Jacobi's representation theorem to determine the closure of a $\sum A^{2d}$-module $S$ of $A$ in the $\tau$-topology, for any integer $d \geq 1$. We show that this closure is exactly the set of all elements $a \in A$ such that $\alpha(a) \geq 0$ for every $\tau$-continuous real algebra homomorphism $\alpha$ on $A$ with $\alpha(S) \subseteq [0,\infty)$. We obtain a representation of any real valued linear functional on $A$ which is continuous with respect to any such $\tau$ and nonnegative on $S$ as integration with respect to a unique Radon measure on the space of all real valued $\mathbb{R}$-algebra homomorphisms on $A$.
« Back... Exponential transforms, resultants and moments
Björn Gustavsson, KTH Royal Institute of Technology, Sweden
The Taylor expansion at infinity of the Cauchy transform of a domain in the complex plane has the harmonic moments as coefficients. Similarly, there is a double Cauchy transform (in two complex variables) having the complete two index set of complex moments as coefficients. Assuming these moments are known, but the domain itself is unknown, one can in principle obtain a good defining function for the boundary by taking the exponential of this double Cauchy transform. The resulting function is called the exponential transform, and it has many remarkable properties. In particular, the above procedure for determining the unknown boundary turns out to be effective in many cases.
The best cases have some algebraic flavor, and then the exponential transform also become an algebraic object (actually a rational function), closely related to a certain meromorphic resultant. I plan to review some of these matters, but I hope also to come up with some new results. The talk is based on joint work with Mihai Putinar, Vladimir Tkachev and others.
« Back... Computation of (moment) invariants
Evelyne Hubert, INRIA Sophia Antipolis, France
Moments of an image are used in computer vision as a mean of pattern recognition. The patterns need to be recognize to be the same under some geometrical transformation like scaling, translation, rotation or even projective transform. Engineers have thus introduced the notion of moment invariants. They correspond to the classical notion of invariants for linear action of an algebraic group.
We shall use this motivation to present recent results for the computation of rational invariants. In the case of scalings or linear action of abelian groups we showed how to obtain a minimal set of generating rational invariants with linear algebra over the integers. A remarkable fact is that we can compute simultaneously an explicit substitution to rewrite any invariant in terms of these generators. We can apply these results to factor out a symmetry in polynomial system and to reduce the number of parameters in dynamical models.
This is joint work with George Labahn, University of Waterloo.
« Back... A symbolic approach to polynomial optimization over basic closed semialgebraic sets
Gabriela Jeronimo, Universidad de Buenos Aires, Argentina
We will discuss the problem of computing the minimum of a polynomial function g on a basic closed semialgebraic subset S of R^n, provided that g attains a minimum value over S. Assuming that the function and the constraints are given by polynomials with integer coefficients, we will present bounds for the algebraic degree and the absolute value of the minimum of g on S under certain compactness assumptions on the subset where the minimum is attained. In addition, we will describe a probabilistic symbolic algorithm that computes a finite set of sample points of the compact connected components of the set of minimizers of g over S.
« Back... From the fundamental theorem of algebra to astrophysics: a "harmonious" path
Dmitry Khavinson, University of South Florida, USA
The Fundamental Theorem of Algebra first rigorously proved by Gauss states that each complex polynomial of degree $n$ has precisely $n$ complex roots. In recent years various extensions of this celebrated result have been considered. We shall discuss the extension of the FTA to harmonic polynomials of degree $n$. In particular, the 2003 theorem of D. Khavinson and G. Swiatek that shows that the harmonic polynomial $\bar{z}-p(z), deg \, p=n>1$ has at most $3n-2$ zeros as was conjectured in the early 90\'s by T. Sheil-Small and A. Wilmshurst. More recently L. Geyer was able to show that the result is sharp for all $n$.\\ In 2006 G. Neumann and D. Khavinson showed that the maximal number of zeros of rational harmonic functions $ \bar{z}-r(z), deg \,r =n>1$ is $5n-5$. It turned out that this result confirmed several consecutive conjectures made by astrophysicists S. Mao, A. Petters, H. Witt and, in its final form, the conjecture of S. H. Rhie that were dealing with the estimate of the maximal number of images of a star if the light from it is deflected by $n$ co-planar masses. The first non-trivial case of one mass was already investigated by A. Einstein around 1912. \\ We shall also discuss the problem of gravitational lensing of a point source of light, e.g., a star, by an elliptic galaxy, more precisely the problem of the maximal number of images that one can observe. Under some more or less "natural'' assumptions on the mass distribution within the galaxy one can prove (A.Eremenko and W. Bergweiler - 2010, also, DK - E. Lundberg - 2010) that the number of visible images can never be more than four in some cases and six in the other. Interestingly, the former situation can actually occur and has been observed by astronomers. Still there are much more open questions than there are answers.
« Back... Algebraic and convex geometries
Askold Khovanskii, University of Toronto, Canada
Traditionally, the connection between convex geometry and algebraic geometry has been restricted to the framework of toric varieties and Newton polyhedra. The theory of Newton-Okounkov bodies, developed in recent joint work with Kiumars Kaveh, transcends these limitations. Generalizing the notion of a Newton polyhedron, we define Newton-Okounkov bodies for semigroups of integral points, graded algebras and linear series on varieties. We show that for a large class of graded algebras, the Hilbert functions have polynomial growth, and their growth coefficients satisfy a Brunn-Minkowski type inequality. If time permitted we will also discuss a new version of the intersection theory. Newton-Okounkov bodies together with this intersection theory allow to prove an algebraic analogues of Alexandrov-Fenchel inequality and to give elementary proof of the classical Alexandrov-Fenchel inequality. These results provide an interplay between algebraic and convex geometries, and suggest a new geometric Alexandrov-Fenchel type inequality for mixed covolumes of convex bodies inscribed in a given convex cone.
« Back... Discrete convolution operators, the Fourier transformation, and its tropical counterpart: the Fenchel transformation
Christer Kiselman, Uppsala University, Sweden
We study solvability of convolution equations for functions with discrete support in $\mathbf{R}^n$, a special case being functions with support in the integer points. The more general case is of interest for several grids in Euclidean space, like the body-centered and face-centered tesselations of three-space. The theorem of existence of fundamental solutions by Boor, H\"ollig \& Riemenschneider is generalized to general finite supports and also some more general discrete supports using only elementary methods. We also study the asymptotic growth of sequences and arrays using the Fourier and Fenchel transformations.
« Back... A discretization-free FPTAS for polynomial optimization over the mixed-integer points in a class of polytopes of varying dimension
Matthias Koeppe, University of California, Davis, USA
We present a new fully polynomial-time approximation scheme for the problem of optimizing non-convex polynomial functions over the mixed-integer points of a polytope of fixed dimension. This improves upon earlier work that was based on discretization [De Loera, Hemmecke, Köppe, Weismantel, FPTAS for optimizing polynomials..., Math. Prog. Ser. A 118 (2008), 273--290]. The algorithm also extends to a class of problems in varying dimension.
The algorithm is based on the study of intermediate sums, interpolating between integrals and discrete sums, initiated by A. Barvinok [2006] and continued by Baldoni, Berline, De Loera, Köppe, Vergne [Computation of the highest coefficients..., Found. Comput. Math. 2012] and Baldoni, Berline, Köppe, Vergne [Intermediate sums on polyhedra..., Mathematika 2012].
For a given polytope P with facets parallel to rational hyperplanes and a rational subspace L, we integrate a given polynomial function h over all lattice slices of the polytope P parallel to the subspace L and sum up the integrals.
This is the culmination of a long-term effort to extend the efficient theory of discrete generating functions to the mixed-integer case in a practical way, without using discretization, and to bring it to use in optimization.
« Back... Checkerboard discrepancies
Mihalis Kolountzakis, University of Crete, Greece
Consider the plane as a checkerboard, with each unit square colored black or white in an arbitrary manner. Suppose now that we place a piece of a curve C on that plane and that we measure the difference of the white and black length induced on the curve $C$ by the coloring of the plane. Call this the discrepancy of $C$. The main theme of this talk is that, no matter what the coloring, one can "place" the curve $C$ in such a manner that its discrepancy is "large". For instance, if $C$ is a straight line segment which is free to move then we can always find a placement where the discrepancy is at least $\sqrt{L}$, where $L$ is the length of the segment. The problem may be stated for several families of curves with various degrees of freedom. For instance one might consider circles or circular arcs which are free to dilate and translate or free to translate only, and in many of these cases we have results that are similar to the segment case, although there are several cases where the answer really ought to be known yet our approach leaves it out. For instance, what is the discrepancy of an L-shaped union of line segments that is free to translate, dilate and rotate? It ought to be the square root of the length but we cannot prove it. Our methods use Fourier Analysis. This is joint work with Alex Iosevich and Ioannis Parissis.
« Back... On splines and counting lattice points in polytopes
Matthias Lenz, University of Oxford, UK
Let $X$ be a $(d\times N)$-matrix. We consider the variable polytope $\Pi_X(u) = \{ w \ge 0 : X w = u \}$. It is known that the function $T_X$ that assigns to a parameter $u \in \mathbb{R}^N$ the volume of the polytope $\Pi_X(u)$ is piecewise polynomial. Formulas of Khovanskii-Pukhlikov and Brion-Vergne imply that the number of lattice points in $\Pi_X(u)$ can be obtained by applying a certain differential operator to the function $T_X$.
In this talk I will discuss the facts mentioned above and connections with objects from approximation theory such as box splines. I will characterise the space of differential operators that leave $T_X$ continuous and sketch a proof of a slightly generalised version of the Khovanskii-Pukhlikov formula.
The talk will be based on arXiv:1211.1187 and arXiv:1305.2784.
« Back... Determinantal representations of hyperbolic curves via numerical homotopy continuation
Anton Leykin, Georgia Institute of Technology, USA
A smooth curve in the real projective plane is hyperbolic if its ovals are maximally nested. By the Helton-Vinnikov Theorem, any such curve admits a definite symmetric determinantal representation. We use polynomial homotopy continuation to compute such representations numerically. One notable feature of our approach is that it avoids complex solving: the continuation paths that we track are real yet regular.
« Back... New trends in Hausdorff operators
Elijah Liflyand, Bar-Ilan University, Israel
Hausdorff operators (Hausdorff summability methods) appeared long ago aiming to solve certain classical problems in analysis, first of all the so called little moment problem. Modern theory of Hausdorff operators started with the work of A. Siskakis in complex analysis setting and with the work of F. M\'oricz and the author in the Fourier transform setting. I shall concentrate on recent results and certain open problems. It will be a joint talk with Lev Aizenberg.
« Back... Higher integrality conditions and volumes of slices
Fu Liu, University of California, Davis, USA
A polytope is integral if all of its vertices are lattice points. The costant term of the Ehrhart polynomial of an integral polytope is known to be 1. I generalize this result by introducing the definition of k-integral polytopes, where 0-integral is equivalent to integral. I will show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees of less than or equal to k are determined by a projection of P, and the coefficients in higher degrees are determined by slices of P. A key step of the proof is that under certain generality conditions, the volume of a polytope is equal to the sum of volumes of slices of the polytope.
« Back... Pseudo H-type Lie algebras and existence of an integer structure
Irina Markina, University of Bergen, Norway
Pseudo H-type Lie algebras, which are special type of 2 step nilpotent Lie algebras, are generalisations of the Heisenberg algebra, by making use of non degenerate scalar products. Their construction is related to the existence of representations of Clifford algebras and the composition of quadratic forms. We give all necessary definitions and will discuss the existence of bases of pseudo H-type Lie algebras in which the structural constants are integers. This integer structure on the Lie algebra leads to the existence of a lattice on the corresponding pseudo H-type Lie group according to the Mal'tcev result.
« Back... Translational tilings: recent results and open questions
Máté Matolcsi, Renyi Institute, Hungary
In this talk i will survey some of the recent progress in the field of translational tilings: questions, proofs, algorithms and counterexamples alike. In particular, i will recall the Fourier analytic conditions for tiling, introduce the concept of spectral sets, and sketch the solution of Fuglede's conjecture. The conjecture is disproved in dimension 3 and higher, but still open in dimension 1 and 2. The existing counterexamples always rely on the existence of certain complex Hadamard matrices. I will also sketch an algorithm to find non-periodic tilings in cyclic groups. Such tilings are sometimes called Vuza-canons and are actually used in music compositions. These non-periodic tilings will lead us to a discussion of the Coven-Meyerowitz conjecture for tiling the integers, and the Hajos quasi-periodicity conjecture for cyclic groups. These conjectures are still wide open.
« Back... Combinatorics of circle bundles
Nikolai Mnev, Steklov Institute of Mathematics at St.Petersburg, Russia
Any circle bundle (U(1) principal fibre bundle) can be triangulated, if the base can be triangulated. Combinatorics of a triangulation has full knowledge about the isomorphism class of the bundle. So we can try to calculate the characteristic classes of the bundle, which are the first Chern class and its powers, by the means of combinatorics of a triangulation. It appears, that there are simple local formulas for such a classes with interesting arithmetics. They look like mathematical expectation of parity of the necklace associated to elementary combinatorial bundle over simplex. This leads to combinatorial and arithmetical form of Gauss-Bonnet-Chern theorem. The theorem allows us for example to describe completely the minimal triangulations of circle bundles with fixed Chern number over closed oriented surface with fixed genus. This problem obtains simple answer but the proof looks unaccessible without presented theory. Even triangulations of the circle bundle associated to tangent bundle of 2-sphere previously were unknown.
« Back... Integer points in polytopes, toric arrangements, and matroids over a ring
Luca Moci, Université de Paris 7, France
Several objects can be associated to a list of vectors with integer coordinates: among others, a family of tori called toric arrangement, a convex polytope called zonotope, a function called vector partition function. These objects and their relations have been described in a recent book by De Concini and Procesi. The linear algebra of the list of vectors is retained by the combinatorial notion of a matroid; but several properties of the objects above depend also on the arithmetics of the list. This can be encoded by the notion of a "matroid over Z". Similarly, applications to tropical geometry suggest the introduction of matroids over a discrete valuation ring. Motivated by the examples above, we introduce the more general notion of a "matroid over a commutative ring R". Such a matroid arises for example from a list of elements in a R-module. When R is a Dedekind domain, we can extend the usual properties and operations holding for matroids (e.g., duality). We can also compute the Tutte-Grothendieck ring of matroids over R; the class of a matroid in such a ring specializes to several invariants, such as the Tutte polynomial and the Tutte quasipolynomial. We will also outline other possible applications and open problems. (Based on joint works with M. D'Adderio, P. Branden, and A. Fink).
« Back... Sparse reconstruction from moments
Bernard Mourrain, INRIA Sophia Antipolis, France
Many problems of reconstruction of structured models from measurements can by reformulated in terms of reconstruction of sparse exponential polynomials, which naturally lead to truncated moment problems. Gaspard-Clair-François-Marie Riche de Prony proposed in 1795 a method to reconstruct the decomposition of functions in one variable, which reduces to the solution of a univariate polynomial. We describe a generalization of this approach to several variables, which involves algebraic ingredients such as duality, border basis and eigenvector solving. We illustrate the method in some applications to signal recovering, sparse interpolation, tensor decomposition and polynomial optimization. Numerical issues are discussed including Newton-type improvement of exponential polynomial representations.
« Back... Multiplicity operators and effective bounds on multiplicities of intersection of Noetherian functions
Dmitry Novikov, Weizmann Institute of Science, Israel
A subring $K\subset {\mathcal{O}}(U)$ of of a ring of the ring of functions holomorphic in $U\subset{\mathbb{C}}^n$ is called a ring of Noetherian functions if it is closed under differentiation, contains the ${\mathbb{C}}[x_1,...,x_n]$ and is Noetherian. The Noetherian functions have natural complexity parameters (degrees of polynomials used in the definition of $K$), and a natural conjecture is that one can bound from above the local complexity of objects defined by them. In order to do this, one should know how to estimate from above the multiplicities of common zeros of Noetherian functions. This was done by Gabrielov and Khovanskii in 1998 for isolated common zeros. I'll discuss the recent progress for non-isolated case.
The main tool will be the theory of multiplicity operators: this is a partial differential operators giving quantitative control over distances between isolated zeros of holomorphic mappings $F:({\mathbb{C}}^n,0)\to({\mathbb{C}}^n,0)$, generalizing the properties of usual derivative in univariate case.
Joint work with Gal Binyamini.
« Back... Effective bounds on multiplicities of intersection of Noetherian functions
Dmitry Novikov, Weizmann Institute of Science, Israel
A subring $K\subset {\mathcal{O}}(U)$ of of a ring of the ring of functions holomorphic in $U\subset{\mathbb{C}}^n$ is called a ring of Noetherian functions if it is closed under differentiation, contains the ${\mathbb{C}}[x_1,...,x_n]$ and is Noetherian. The Noetherian functions have natural complexity parameters (degrees of polynomials used in the definition of $K$), and a natural conjecture is that one can bound from above the local complexity of objects defined by them. In order to do this, one should know how to estimate from above the multiplicities of common zeros of Noetherian functions. This was done by Gabrielov and Khovanskii in 1998 for isolated common zeros. I'll discuss the recent progress for non-isolated case.
Joint work with Gal Binyamini.
« Back... Distances between points on algebraic curves
János Pach, École Polytechnique Fédérale de Lausanne, Switzerland
Let P be a set of n points in the plane, contained in an algebraic curve C of degree d. We prove that the number of distinct distances determined by P is at least c_d n^{4/3}, unless C contains a line or a circle. We also prove the lower bound c'_d min{ m^{2/3}n^{2/3}; m^2; n^2 } for the number of distinct distances between m points on one irreducible plane algebraic curve and n points on another, unless the two curves are parallel lines, orthogonal lines, or concentric circles. (Here c_d and c'_d are suitable positive constants.) This generalizes a result on distances between lines of Sharir, Sheff er, and Solymosi. Joint work with Frank de Zeeuw.
« Back... Positive polynomials and moment problems on curve configurations
Daniel Plaumann, Universität Konstanz, Germany
We discuss positivity of polynomials and solvability of the moment problem for semialgebraic subsets of curves with several irreducible components. As an interesting special case, we consider embedded graphs as well as generalisations to simplicial complexes of higher dimension. This combines classical and modern results on the one-dimensional moment problem with arguments of a combinatorial flavour.
« Back... From Banach spaces to moments to positive polynomials
Bruce Reznick, University of Illinois at Urbana-Champaign, USA
The speaker will describe how his PhD thesis in Banach Spaces led him naturally to study the classical moment problem and then to the representation of psd polynomials as a sum of squares. He will try very, very hard not to think about how long ago these events occurred.
« Back... Ternary forms with lots of zeros
Bruce Reznick, University of Illinois at Urbana-Champaign, USA
We are concerned with real psd ternary forms $p(x,y,z)$ of degree $2d$, especially for $d = 3,4$. The Robinson form is a ternary sextic with exactly 10 zeros. Choi, Lam and Reznick proved in 1980 that a psd ternary sextic with more than 10 zeros has infinitely many zeros and is sos and used the Robinson form to construct psd ternary forms of degree $6k$ with exactly $10k^2$ zeros. We will give a psd-not-sos ternary octic with exactly 17 zeros. This is joint work with Greg Blekherman.
« Back... A Fourier-approach to the Brion identities
Sinai Robins, Nanyang Technological University
The Brion identities form a backbone for many modern approaches to moments of polytopes, integer point enumeration in polytopes, and volume computations. We give a new proof of the Brion identities in the discrete geometry of polytopes by using Gaussians and Fourier techniques. In this way, the localization problems that usually arise in the non-convergent rational function approach are alleviated, and a more global analysis ensues. The same techniques allow for a transition (with proof) to non-convex polytopes. We first show how to prove the continuous Brion identity, and then how to use it to prove the discrete Brion identity, using Poisson summation.
« Back... Moments of a polytope
Michael Shapiro, Michigan State University, USA
We show that a multivariate generating function of appropriately normalized moments of any compact polytope in $R^d$ with respect to any homogeneous polynomial weight function is a rational function. Its denominator is the product of linear forms dual to the vertices of P raised to the power equal to the degree of the weight function. I will discuss also the inverse moment problem for the set of polytopes having a given set of vertices.
(joint with N.Gravin, D. Pasechnik, and B. Shapiro)
« Back... Analyzing quantum coin-flipping protocols using optimization techniques
Jamie Sikora, Université Paris Diderot - Paris 7, France
We examine a cryptographic primitive known as (quantum) coin-flipping where two parties generate a random bit over a (quantum) communication channel. We use optimization techniques to investigate the security of a family of coin-flipping protocols based on bit-commitment. Using semidefinite programming, we formulate optimal cheating strategies and use duality theory to construct their "point games". Using linear programming, we formulate optimal cheating strategies for the classical protocol counterpart. We also investigate their point games, discuss how they are connected to the quantum point games, and show that they are useful in the security analysis. I will also briefly discuss a search algorithm used to search for secure protocols within this family.
This is joint work with Ashwin Nayak and Levent Tunçel.
« Back... Extreme rays of moment cones for ternary forms
Rainer Sinn, Universität Konstanz, Germany
The moment cones for ternary forms have extreme rays coming from point evaluations (or point measures) and, beginning in degree 6, they must have more. We review bounds on the ranks of extremal moment matrices due to Blekherman and present a constructive approach related to classical algebraic geometry of plane curves revolving around the Cayley-Bacharach Theorem. This is joint work in progress with Blekherman.
« Back... Moments in probability and statistics
Jordan Stoyanov, Newcastle University, UK
The goal is to describe probability/statistical distiributions and their properties expressed in terms of the moments. Any distribution with all moments finite is either unique (M-determinate) or non-unique (M-indeterminate). Along with classical criteria (Cramer, Carleman, Hausdorff, Krein, ...) some very recent results will be discussed. Ideas, techniques and results in this area are of general mathematical interest. However, they are not less important in applied areas, stochastic modelling, statistical inference and optimization. The specific choice of what to cover in more details will depend on the interests of the attendees. It time permits some open questions will be outlined.
« Back... Free nilpotent and H-type groups: combinatorial and orthogonal designs
Alexander Vasiliev, University of Bergen, Norway
Our primary aim is to prove that pseudo H-type groups admit lattices, or equivalently, the corresponding pseudo H-type algebras admit a basis with rational structural constants. We also show the interplay of these results and combinatorial and orthogonal designs.
Joint work with Kenro Furutani (Tokyo) and Irina Markina (Bergen)
« Back... Parallel repetition via a relaxation
Thomas Vidick, Massachusetts Institute of Technology, USA
Two-player one round games are a basic construction in computer science, where they are tightly connected to the study of local constraint satisfaction problems. The study of the quantum value, the maximum success probability of players allowed to share entanglement, of such games provides a computational perspective on the non-local correlations of entanglement.
We introduce a new relaxation for the quantum value of two-player one-round games. The relaxation is tighter than the classic semidefinite relaxations considered by Pironio et al. and Doherty et al.; in fact it is not (known to be) efficiently computable. However, the relaxation shares many desirable properties of semidefinite relaxations, and in particular it has a nice multiplicativity property. I will introduce this relaxation and show that its value remains close to the quantum value. Multiplicativity of the relaxation will let us derive a new parallel repetition theorem for the category of projection games.
Based on joint work with Irit Dinur and David Steurer, arXiv:1310.4113
« Back... Determinantal representations of stable polynomials
Victor Vinnikov, Ben Gurion University of the Negev, Israel
Determinantal representations of singular hypersurfaces in P^n
Dmitry Kerner, Victor Vinnikov,
arXiv:0906.3012
LMI Representations of Convex Semialgebraic Sets and Determinantal Representations of Algebraic Hypersurfaces: Past, Present, and Future
Victor Vinnikov
arXiv:1205.2286
Stable and real-zero polynomials in two variables
Anatolii Grinshpan, Dmitry S. Kaliuzhnyi-Verbovetskyi, Victor Vinnikov, Hugo J. Woerdeman
arXiv:1306.6655
« Back... Quartic spectrahedra
Cynthia Vinzant, University of Michigan, USA
Intersecting the convex cone of positive semidefinite 4 by 4 matrices with a three-dimensional affine space yields a quartic spectrahedron. It is bounded by a complex quartic hypersurface called a symmetroid. Recently, Degtyarev and Itenberg used the global Torelli Theorem for real K3 surfaces to describe the position of nodes (that is, rank-two matrices) on the real surface and spectrahedron. I'll discuss this result in the context of concrete algebraic geometry. In particular we'll see the special structure of these surfaces and spectrahedra by looking at their projection from a node, as done classically by Cayley.
« Back... An algebraic approach to phase retrieval
Cynthia Vinzant, University of Michigan, USA
The problem of phase retrieval is to reconstruct a signal from certain magnitude measurements. This problem is closely related to low-rank matrix completion and has many imaging-related applications: microscopy, optics, and diffraction imaging, among others. In purely mathematical terms, phase retrieval means recovering a complex vector from the modulus of its inner product with certain measurement vectors. One can ask how many measurements are necessary for this recovery to be possible. I'll discuss recent progress made on this problem by translating it into algebraic language and talk about my recent adventures as an algebraist in frame theory.
« Back... Quantum marginals and classical moments
Michael Walter, ETH Zürich, Switzerland
We will describe two problems related to the quantum marginal problem, (1) the problem of computing eigenvalue distributions of reduced density matrices for random pure states and (2) the problem of computing multiplicities of irreducible representations of Lie groups, discuss their relation and explain how they can be solved by studying generalized moments. This talk is based on arXiv:1204.0741 and arXiv:1204.4379
« Back... Algorithmic conversion of polynomial optimization problems of noncommuting variables to semidefinite programming relaxations: sparsity and scalability
Peter Wittek, University of Boras, Sweden
A hierarchy of semidefinite programming (SDP) relaxations approximates the global optimum of polynomial optimization problems of noncommuting variables. Typical applications include determining genuine multipartite entanglement, finding mutually unbiased bases, and solving ground-state energy problems. Generating the relaxations, however, is a computationally demanding task, and only problems of commuting variables have efficient generators. A closer look at the applications reveals sparse structures: either the monomial base can be reduced or the moment matrix has an inherent structure. Exploiting sparsity leads to scalable generation of relaxations, and the resulting SDP problem is also easier to solve. The current algorithm is able to generate relaxations of optimization problems of a hundred noncommuting variables and a quadratic number of constraints.
« Back... Vanishing of polynomial moments
Yosef Yomdin, Weizmann Institute of Science, Israel
We consider moments of the form $m_k = \int_a^b P^k(x)q(x)dx$, where $P(x)$ and $q(x)$ are two polynomials. The problem is to give conditions vor the identical vanishing of $m_k$ for each k, i.e. for the orthogonality of q to all the powers of P on [a,b]. The origin of this problem is in Qualitative theory of ODE's. One sufficent condition is given by the following "Composition Condition", which is important also in the original problems in ODE's: there is a polynomial W with W(a)=W(b), and polynomials R, S, such that $P(x)=R(W(x))$ and $Q(x)=\int q(x)=S(W(x))$. However, this condition is not necessary. Recently, F. Pakovich (after a long development) has finally solved the problem, providing necessary and sufficient condition for moments vanishing. I plan to discuss Pakovish's solution, some its consequences for ODE's, and some other problems of moments vanishing, in particular, those in the work of W. Zhao, related to the Jacobian Conjecture.
« Back... Introduction to tropical geometry
Josephine Yu, Georgia Institute of Technology, USA
Tropical geometry is the geometry over the max-plus semiring. It can be viewed as a polyhedral shadow of algebraic geometry. I will introduce tropical varieties from the point of view of Groebner theory and will discuss important examples including linear spaces, Grassmannians, discriminants, and resultants. Applications include new tools for computational problems such as implicitization and elimination. I will also introduce tropical convexity and tropical linear spaces as related to matroid theory.
« Back...
|
|