Additive combinatorics over finite fields and applications

Externally Funded Project

FWF Project P 30405-N32
Runtime: 01.09.2017-31.08.2021

Project Team

  • Arne Winterhof (project leader)
  • Oliver Roche-Newton (co-leader)
  • Nurdagül Anbar (01.09.2017-31.01.2018)
  • Audie Warren (01.01.2018-28.02.2021)
  • Laszlo Merai (01.08.2018-31.12.2018)
  • Mehdi Makhul (01.01.2019-31.12.2019, 01.10.2020-30.09.2021)
  • Sophie Stevens (01.04.2020-31.03.2021)

Project Abstract

Loosely speaking, additive combinatorics is the study of arithmetic structures within finite sets. It is an indication of the high level of activity in this research area that it has become the primary research interest for three Fields medalists (Terence Tao, Timothy Gowers, and Jean Bourgain), along with several more of the world's most respected and decorated mathematicians (such as Ben Green, Nets Katz and Endre Szemeredi).

Additive combinatorics over finite fields is particularly interesting because of its applications to computer science, cryptography, and coding theory. It is a very old area with celebrated results such as the Cauchy-Davenport theorem:
Let  $A,B$ subsets of a finite field of prime order $p$.  Then we have $|A+B|≥min{|A|+|B|−1,p}$.

Recent years have seen a flurry of activity in this area. One influential development was the work of Bourgain, Katz and Tao that shows that for a subset A of a finite field (which is not too large) either the product set $A⋅A={ab:a,b∈A}$ or the sum set $A+A={a+b:a,b∈A}$ is essentially larger than $A$. Since then this area has gained increasing interest.

Among others we will study the following topics which are problems either coming directly from additive combinatorics or dealing with applications where methods from additive combinatorics are very promising:

  • sum-product and related problems
  • character sums with convolutions and Balog-Wooley decomposition
  • covering sets and packing sets, rewriting schemes and error-correction
  • Waring's problem in finite fields and covering codes
  • sums of Lehmer numbers.

We will use a collection of different methods and their combinations including

  • theorems from incidence geometry
  • character sum techniques
  • polynomial method
  • probabilistic method
  • linear programming
  • methods from algebraic geometry

We expect that the results and newly developed methods of this project will provide substantial contributions to both theory and applications.

Publications and Preprints

Peer Reviewed Journal Publication

Oops, an error occurred! Code: 2021092201291689bb6e36

Book/Monograph

Oops, an error occurred! Code: 20210922012916ee1b4394

Contribution in Collection

Oops, an error occurred! Code: 20210922012916584f24a6

Dissertation

Oops, an error occurred! Code: 2021092201291676e56ca9

Workingpaper

Oops, an error occurred! Code: 20210922012916bc316f64