Programme of the DIAMANT symposium
Hotel Het Witte Huis, Soest
24 and 25 November 2016
Thursday  
11:0011:25  arrival and coffee 
11:2511:30  welcome 
Reem Yassawi (Trent U, Canada)  Linear cellular automata and pautomatic sequences 
11:3012:25 
Let p be a prime number. A pautomatic sequence is one that is generated by a deterministic finite state machine which is fed basep expansions of natural numbers. Cobham's theorem characterizes these sequences as the letter to letter projections of fixed points of length p substitutions: these are generated by a morphism on some finite alphabet A, which replaces letters with words. These sequences generate a rich source of combinatorial and symbolic dynamical systems, whose dynamical, spectral and measurable properties have been studied extensively. If one further assumes that A has a field structure, then the beautiful theorems of Christol and Furstenberg give other characterizations of pautomatic sequences. We describe these characterizations, and using them, we show that a sequence over a finite field F of characteristic p is pautomatic if and only if it occurs as a column of the spacetime diagram (with eventually periodic initial conditions), of a linear cellular automaton with 'memory' over F. We compare this phenomenon to the one of spacetime diagrams whose initial condition is mrandom for some measures m. Our proofs are constructive. As a corollary, we show that the dynamical system generated by a length psubstitution can be realized as a topological factor of a linear cellular automaton. This is joint work with Eric Rowland (Hofstra University).

12:3014:00  lunch 
Bart de Keijzer (CWI)  The groundsetcost budgeted maximum coverage problem 
14:0014:25  The weighted budgeted maxcoverage problem is a wellknown optimization problem where we are given a budget and collection of subsets over a finite ground set (the elements of which we refer to as the vertices), each subset has a certain cost, and each vertex has a certain profit. The goal is to select a subcollection of the subsets such that the total cost does not exceed the budget, and the total profit of the covered elements is maximized. We study a natural and strictly harder variant of this problem where the costs are on the vertices instead of on the subsets, so that each vertex has both a profit and a cost. We show that this problem is APXhard, and prove that for the following special cases of the problem, there exist constant factor approximation algorithms that run in polynomial time: (1) when the size of the sets is bounded by a constant, there exists a (1−1/sqrt(e))/2approximation algorithm. (2) when there is a bound d on the degree of each vertex (when viewed as a hypergraph), there exists an O(d^2)approximation algorithm. (3) when the incidence graph of the set system is a forest, the problem can be solved to optimality in polynomial time. Besides that this problem is a natural generalization of the wellstudied maxcoverage problem, we additionally illustrate how this problem arises naturally in the context of bid optimization in sponsored search auctions, such as in Google’s AdWords system. 
Guus Bollen (TUe)  Algebraic representability of matroids 
14:3014:55  Ingleton has shown that over fields of characteristic 0, a matroid is algebraically representable if and only if it is linearly representable. Over fields of positive characteristic, this equivalence does not hold. We look at flockrepresentable matroids, as a class that contains the algebraically representable matroids. Each flock of a matroid M gives rise to a valuation on the set of bases of M. If M has a very limited range of valuations, then this limits the flockrepresentations, and in turn the algebraic representations of M. We use this approach to redo some classical results, and more. 
15:0015:30  tea 
Peter Koymans (UL)  An application of Vinogradov's method to class groups 
15:3015:55  We show that the density of prime numbers p for which the class group of the imaginary quadratic field Q(sqrt{p}) has an element of order 16 is 1/16, as predicted by the CohenLenstra heuristics. Our proof relies on a method due to Vinogradov, which we will explain during the talk. Joint work with Djordjo Milovic. 
Jörg Jahnel (Siegen)  Moduli spaces and the inverse Galois problem for cubic surfaces 
16:0016:55  I will report on our project, joint with A.S. Elsenhans, to construct cubic surfaces over Q with prescribed Galois operation on the 27 lines. This involves the application of classical algebrogeometric constructions such as J.J. Sylvester's pentahedral form for a cubic surface, A. Clebsch's 5 fundamental invariants of a cubic surface, and A. Coble's 40 irrational invariants for a marked cubic surface. 
17:0018.30  drinks 
18:30  dinner 
Friday  
Oleg Pikhurko (U Warwick)  Measurable equidecomposition via augmenting paths 
10:0010:55  Two subsets A, B of R^n are called equidecomposable if one can partition A into finitely many parts and move them using isometries to form a partition of B. One example is the famous BanachTarski Paradox that a unit ball can be doubled if the dimension n is at least 3. We present sufficient criteria for the existence of equidecompositions with Lebesgue measurable parts, by running an analytic version of the augmenting path algorithm. This in particular gives measurable versions of Tarski's circle squaring and Hilbert's 3d problem. Joint work with András Máthé and Łukasz Grabowski. 
11:0011:30  coffee 
Richard Griffon (UL)  An analogue of the BrauerSiegel theorem for Fermat surfaces over finite fields 
11:3011:55  The classical BrauerSiegel theorem gives upper and lower bounds on the product of the classnumber times the regulator of units of a number field, in terms of its discriminant. These bounds can be seen as a measure of the "arithmetic complexity" of number fields. In this talk, I'd like to report on a work in progress in a more geometric setting. Consider a projective smooth surface S defined over a finite field k. Assuming that its Brauer group is finite, one can form the product of the order of this group by the determinant of a basis of the NéronSeveri group of S over k with respect to the intersection form. We are interested in bounding this quantity in terms of the geometric genus of S, in the case when S is a Fermat surface. When the genus grows to infinity, the bounds we prove provide a complete analogue of the BrauerSiegel theorem for the Fermat surfaces. The proof is mostly "analytical" in that it boils down to estimates about the zeta functions of these surfaces. 
12:0013:00  lunch 
Dion Gijswijt (TU Delft)  A solution of the cap set problem 
13:0013:55  A subset of GF(3)^n, the ndimensional vector space over the field of 3 elements, is called a cap set if it does not contain an affine line. In dimension 4, this relates to the famous card game SET. There, a cap set corresponds to a collection of cards without a SET. The cap set problem is concerned with upper bounds on the size of cap sets. A question raised by Frankl, Graham and Rödl is: do cap sets have exponentially small density? A positive answer implies the ErdösSzemerédi sunflower conjecture. On the other hand, several approaches for fast matrix multiplication rely on a negative answer. In this talk we give a positive answer by showing that the maximum size of a cap set is O(c^n), where c=2.756. The proof is surprisingly simple and uses the polynomial method, building upon work of Croot, Lev and Pach. This is joint work with Jordan Ellenberg. 
14:0014:30  tea 
Quentin Louveaux (Université de Liège)  The kFrobenius number: bounds and algorithms 
14:3015:25  The Frobenius number is a wellknown problem in number theory and integer optimization. Given a set of integer numbers, the problem is to find the largest integer b that cannot be represented as a nonnegative integral combination of the given integers. The kFrobenius number is a generalization in which we ask for the largest integer b that cannot be represented by at least k different nonnegative integral combinations of the given integers. In this talk we make a survey on different algorithms to find these numbers. We also discuss its known properties and in particular the lower and upper bounds that are known about it. 
15:30  end of the symposium 