Invited speakers:

David Conlon (Oxford) - A relative Szemerédi theorem

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. In this talk, we will discuss a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Our strengthened version can be applied to give the first relative Szemerédi theorem for k-term arithmetic progressions in pseudorandom subsets of Z_N of density N^{-c_k}. The key component in our proof is an extension of the regularity method to sparse pseudorandom hypergraphs, which we believe to be interesting in its own right. From this we derive a relative extension of the hypergraph removal lemma. This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem. This is joint work with Jacob Fox and Yufei Zhao.

Cristian Dobre (Aachen) -  Exploiting symmetry in copositive programs via semidefinite hierarchies

In this talk we show how one can exploit the symmetry in a hierarchy of improving semidefinite programming (SDP) relaxations of NP-hard combinatorial optimization problems. Each level of the hierarchy consists of a semidefinite part and a system of linear equations coming from coefficient identification in equalities between polynomials. Both parts need nontrivial preprocessing in order to reduce the dimension of the problem, and we show how the symmetry in the data of the problem can be used to achieve the reduction. Numerically we exemplify the advantages of this approach by providing new upper bounds on crossing number instances, one of the most well known NP-hard combinatorial optimization problem which involves symmetric data.

Barbara Terhal (Aachen) -  Quantum Complexity Theory

We will discuss the model of quantum computation and the important differences between quantum and classical computation. We then review a quantum version of the classical Cook-Levin theorem due to Kitaev which proves that determining the lowest eigenvalue of physical Hamiltonians is quantum NP or QMA-complete. We discuss the mathematical problems that we have encountered in some of our recent work in quantum complexity theory related to bounding the mixing times of classical Markov chains.

Thorsten Theobald (Frankfurt) - Polytopes, spectrahedra, and the question of containment

Polyhedra (or in the bounded cases polytopes) are the feasible regions of linear programs. Generalizing this notion, spectrahedra are defined as the feasible regions of the semidefinite programs. In this talk, we first provide some general insights into the world of spectrahedra. Then we study the computational question whether a given polytope or spectrahedron S_A (as given by the positive semidefiniteness region of a linear matrix pencil A(x)) is contained in another one S_B. Our results both concern the computational complexity (extending results on the polytope/polytope-case by Gritzmann and Klee), sufficient conditions to certify containment (whose study was initiated by Ben-Tal, Nemirovski and Helton, Klep, McCullough), as well as a hierarchy of semidefinite conditions to certify the containment of a spectrahedron in another one. (Joint work with Kai Kellner and Christian Trabandt.)

Contributed speakers:

Ane Anema (RUG) - Elliptic curves and the Hesse pencil

Given an elliptic curve E defined over a perfect field k of characteristic different from two and three, we describe a family of elliptic curves with the property that the Galois representations on the 3-torsion subgroup of E and of an elliptic curve in this family are identical. Moreover, if E' is another elliptic curve defined over k such that the Galois representations on the 3-torsion subgroup of E and E' are equivalent via a Weil-pairing preserving isomorphism, then E' is isomorphic over k to a member of this family. We will present a simple proof of this statement. This family is related to earlier results by K. Rubin, A. Silverberg, T.A. Fisher and M. Kuwata.

Evan Decorte (TU Delft) - Low-dimensional spherical sets avoiding orthogonal pairs of points.

Let M_n be the maximum surface measure of a subset of the n-dimensional unit sphere not containing a pair of orthogonal vectors. A 1974 conjecture of H.S. Witsenhausen states that the extremal configuration is given by two diametrically opposite spherical caps of equal size. In the same article, Witsenhausen proves M_n <= 1/n. A result of A.M. Raigoroskii from 1999 gives exponentially decreasing upper bounds for M_n via a Frank-Wilson type approach. However for n=3, the original 1/3 bound of Witsenhausen is the best known. In this talk we outline a proof that M_3 is strictly less than 1/3. This is joint work with Oleg Pikhurko.

Rob Eggermont (TU/e) - Alternating tensors of bounded rank are defined in bounded degree

Exterior products of a vector space V help to describe volumes, determinants, and subspaces of V. An element of the p-th exterior product of V (called an alternating tensor from here on) is called pure if it is the wedge product of p elements of V. The rank of an alternating tensor w is the minimal r such that there is an r-tuple of pure alternating tensors that sums up to w. The set of pure alternating tensors can be described by homogeneous equations of degree two, the Plücker relations. In fact, up to automorphisms of V, we only need a single equation to cut out the set of pure alternating tensors. Moreover, this equation does not change in an essential way if we change V or p. We generalize these statements to the (closure of) the set of alternating tensors of rank at most r in the p-th exterior product of V. More specifically, we show that this variety can be described by finitely many types of equations, regardless of V or p.

Dino Festi (UL) - The Cayley-Oguiso free automorphism of positive entropy on a K3 surface 

Ziyang Gao (UL) - Ax-Lindemann: a statement of functional algebraic independence and bi-algebraicity

The Ax-Lindemann(-Weierstrass) theorem is a functional algebraic independence statement for the uniformizing map of an arithmetic variety. For algebraic torus over C this is the analogue of the classical Lindemann-Weierstrass theorem about transcendental numbers to the functional case. This theorem is a key step to prove the André-Oort/Manin-Mumford conjecture by the method of Pila-Zannier. In this talk I will briefly introduce the history of the theorem, explain how to view it as a bi-algebraicity statement and (if time permits) discuss its relationship with the André-Oort/Manin-Mumford conjecture.

Emil Horobet (TU/e) - The average number of critical rank-one approximations to a tensor

In this talk we present a study of the expected number of real critical points of the Euclidean distance function, on an algebraic variety X. After a general introduction to the topic, we concentrate on the variety of rank-one tensors. The expected number of real critical points is expressed in terms of the average absolute value of the determinant on a Gaussian-type matrix ensemble.

Pinar Kilicer (UL) - The class number one problem for genus-2 curves

The Gauss class number one problem for imaginary quadratic fields is equivalent to finding all elliptic curves over the rationals with non-trivial endomorphism ring. I will explain the relation between the class number one problem and the elliptic curves over the rationals. Then I will give the analogue of the class number one problem for genus-2 curves and sketch its solution.

Michiel Kosters (UL) - Images of polynomial maps on a field

Let k be a field and let f in k[x] be a non-constant polynomial. Suppose that k\f(k) is not empty. Our goal is to find a lower bound for |k\f(k)|. In this talk we will discuss the following two statements: (i) k is finite with |k|=q => |k\f(k)| >= (q-1)/deg(f); (ii) k is an infinite algebraic extension of a finite field => k\f(k) is not finite.

Djordjo Milovic (UL) - The infinitude of $\mathbb{Q}(\sqrt{-p})$ with a specified $16$-rank.

The density of primes $p$ such that the $2^k$-rank of the class group $\mathcal{C}(-p)$ of $\mathbb{Q}(\sqrt{-p})$ is $1$ is $2^{-k}$ for $1\leq k \leq 3$. For primes $p$ of the form $p = a^2 + b^4$ with $b$ even, we find the 8-Hilbert class field of $\mathbb{Q}(\sqrt{-p})$ in terms of $a$ and $b$. We then use a theorem of Iwaniec and Friedlander to show that there are infinitely many primes $p$ with the $16$-rank of $\mathcal{C}(-p)$ equal to $1$ and also infinitely many primes $p$ with the $8$-rank of $\mathcal{C}(-p)$ equal to $1$ and the $16$-rank equal to $0$.


Mathematics cluster DIAMANT

Upcoming events

Diamant symposium
28-11-2019 - 29-11-2019

News - more news

Full professor position in Discrete Mathematics in Delft

Delft Institute of Applied mathematics, Delft University of Technology, seeks a full Professor in the field of Discrete Mathematics. A description of the position can be found here. The deadline for applications is January 15, 2019.

ERC Starting grant for Daniel Dadush

Daniel Dadush (CWI) has been awarded an ERC Starting Grant of 1.5 ME for his proposal ‘Towards a Quantitative Theory of Integer Programming’. With this grant, Dadush aims to revolutionize the understanding of integer programming (IP), the most popular method used today for finding optimal solutions to real-world optimization problems.

Read more.

VICI grant for Nikhil Bansal

Nikhil Bansal has been awarded a Vici grant of 1.5 ME. He is one of the 35 academics to receive this grant from NWO in 2018. Bansal aims to use his grant to develop new algorithmic methods to make discrete decisions in a continuous way. He expects this to lead to applications in the fields of logistics, bio-informatics, chip design and machine learning.

Read more.

3 DIAMANT PhD positions awarded

NWO, following a shortlist provided by the DIAMANT board, has decided to award 3 PhD positions to young DIAMANT members: Dion Gijswijt (TU Delft), Jan Steffen Müller (RUG) and Arno Kret (UvA).
Read more.