Tag - Additive number theory

Jimmy He: Random walks on finite fields with deterministic jumps

1st March, 2021

Recently, Chatterjee and Diaconis showed that most bijections, if applied between steps of a Markov chain, cause the resulting chain to mix much faster. However, explicit examples of this speedup phenomenon are rare. I will discuss recent work studyingsuch walks on finite fields where the bijection is algebraically defined. This work gives a large collection of examples where this speedup phenomenon occurs. These walks can be seen as a non-linear analogue of the Chung-Diaconis-Graham process, where the bijectionis multiplication by a non-zero element of the finite field. This work is partially joint with Huy Pham and Max Xu.

Swastik Kopparty: Geometric rank of tensors and the subrank of matrix multiplication

22nd February, 2021

I will talk about a new notion of rank for tensors called geometric rank, and discuss some of its basic properties, as well as its relationship with other well-studied notions of rank like subrank, slice rank and analytic rank. As an application, we will see a proof of tightness of an old bound of Strassen on the subrank of the matrix multiplication tensor.

Shukun Wu: On the largest sum-free subsets of integers

15th February, 2021

An old conjecture in additive combinatorics asks: what is the largest sum-free subset of any set of N positive integers? Here the word "largest" should be understood in terms of cardinality. In this talk, I will discuss some recent progress on this conjecture, and the analogous conjecture on (k,l)-sum-free sets. The main method we used is Fourier analysis.

George Shakan: Effective Khovanskii Theorems

8th February, 2021

Let A be a subset of the d dimensional integer lattice and NA be the N-fold sumset. In 1992, Khovanskii proved that |NA| can be written as a polynomial in |A| of degree at most d, provided N is sufficiently large. We provide an effective bound for "sufficiently large", and discuss some related results.

Rachel Greenfeld: Translational tilings: structure and decidability

25th January, 2021

Let F be a finite subset of ℤd. We say that F is a translational tile of ℤd if it is possible to cover ℤd by translates of F with no overlaps. Given a finite subset F of ℤd, could we determine whether F is a translational tile in finite time? Suppose that F does tile, does it admit a periodic tiling? A well known argument of Wang shows that these two questions are closely related. In the talk, we will discuss this relation and present some new results, joint with Terence Tao, on the rigidity of tiling structures in ℤ2, and their applications to decidability.

Boris Bukh: Almost nets and convex holes

18th January, 2021

A net is a subset of [0,1]d containing the expected number of points in every large dyadic subcube. Nets are one of the central objects in discrepancy theory, with numerous applications in numerical algorithms. In this talk, I will discuss a construction of sets that instead contain approximately correct number of points in every large dyadic subcube, and how these can be used to construct sets in ℝd without large convex holes.

Cosmin Pohoata: New lower bounds for the Erdős box problem

14th December, 2020

We discuss some new lower bounds for the Erdős box problem, the problem of estimating the extremal number of the complete d-partite d-uniform hypergraph with two vertices in each part, thereby improving on work of Gunderson, Rödl and Sidorenko.

Brandon Hanson: Higher convexity and iterated sumsets

30th November, 2020

Erdős and Szemerédi made the (still open) conjecture that for a finite set of natural numbers, A, either the sumset A+A, or else the productset AA, must be nearly as large as possible. A slightly different interpretation is that either A+A is large or log(A)+log(A) is large, where log(A) is the image of A under the (convex) logarithm function. This phenomenon is in fact more general, and extends to arbitrary convex functions f: if f has non-vanishing second derivative, then either A+A or else f(A)+f(A) is large. In recent work with Roche-Newton and Rudnev, we show that this growth persists when f has further non-vanishing derivatives.