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

  • On sets of points in general position that lie on a cubic curve in the plane and determine lines that can be pierced by few points. / Makhul, M; Pinchasi, R.
    in: Studia Scientiarum Mathematicarum Hungarica, Jahrgang 59, Nr. 3-4, 14.12.2022, S. 196--208.
    DOIRISENWBIB
  • On the index of the Diffie-Hellman mapping. / Isik, L; Winterhof, A.
    in: Applicable Algebra in Engineering, Communications and Computing, Jahrgang 33, Nr. 5, 14.10.2022, S. 587--595.
    DOIRISENWBIB
  • Arcs in Fq2. / Roche-Newton, Oliver; Warren, Audie.
    in: European Journal of Combinatorics, Jahrgang 103, 15.06.2022, S. ARTN 103512.
    DOIRISENWBIB
  • Normality of the Thue-Morse function for finite fields along polynomial values. / Makhul, M; Winterhof, A.
    in: Research in Number Theory, Jahrgang 8, Nr. 38, 13.06.2022, S. 17.
    DOIRISENWBIB
  • Pseudorandom sequences derived from automatic sequences. / Merai, L; Winterhof, A.
    in: Cryptography and Communications, Jahrgang 14, Nr. 4, 19.04.2022, S. 783--815.
    DOIRISENWBIB
  • The Elekes-Szabo problem and the uniformity conjecture. / Makhul, M; Roche-Newton, O; Stevens, S et al.
    in: Israel Journal of Mathematics, Jahrgang 248, 39–66 (2022), 06.03.2022, S. 39--66.
    DOIRISENWBIB
  • Sequences of the parities of differences of consecutive quadratic residues. / Winterhof, A; Xiao, Z.
    in: Advances in Mathematics of Communications, Jahrgang 16, Nr. 1, 10.01.2022, S. 83--93.
    DOIRISENWBIB
  • On the Pinned Distances Problem in Positive Characteristic. / Murphy, Brendan; Petridis, Giorgis; Pham, Thang et al.
    in: Journal of the London Mathematical Society, Jahrgang 105:469–499, 01.01.2022, S. 469--499.
    DOIRISENWBIB
  • An energy bound in the affine group. / Petridis, G; Roche-Newton, O; Rudnev, M et al.
    in: International Mathematics Research Notices, Jahrgang 2022, Nr. 2, 01.01.2022, S. 1154--1172.
    DOIRISENWBIB
  • An update on the sum-product problem. / Rudnev, M; Stevens, S.
    in: Mathematical Proceedings of the Cambridge Philosophical Society, Jahrgang 173, 01.01.2022, S. 411-430.
    DOIRISENWBIB
  • Attaining the exponent 5/4 for the sum-product problem in finite fields. / Mohammadi, A; Stevens, S.
    in: International Mathematics Research Notices, Jahrgang rnab338, 15.12.2021, S. 1--11.
    DOIRISENWBIB
  • Balance and pattern distribution of sequences derived from pseudorandom subsets of Z_q. / Liu, H; Winterhof, A.
    in: Uniform Distribution Theory, Jahrgang 16, Nr. 2, 10.11.2021, S. 89--108.
    DOIRISENWBIB
  • Sums, products and dilates on sparse graphs. / Roche-Newton, O.
    in: SIAM Journal on Discrete Mathematics, Jahrgang 1, 07.10.2021, S. 194-204.
    RISENWBIB
  • Higher convexity and iterated sum sets. / Hanson, B; Roche-Newton, O; Rudnev, M.
    in: Combinatorica, Jahrgang to appear, 07.10.2021, S. 15pp.
    DOIRISENWBIB
  • Additive double character sums over some structured sets and applications. / Swaenepoel, C; Winterhof, A.
    in: Acta Arithmetica, Jahrgang 199, Nr. 2, 14.09.2021, S. 135--143.
    DOIRISENWBIB
  • New expander bounds from affine group energy. / Roche-Newton, O; Warren, A.
    in: Discrete and Computational Geometry, Jahrgang 66, Nr. 2, 14.09.2021, S. 552-574.
    DOIRISENWBIB
  • On the number of perfect triangles with a fixed angle. / Makhul, M.
    in: Discrete and Computational Geometry, Jahrgang 66, Nr. 3, 14.09.2021, S. 1143--1149.
    DOIRISENWBIB
  • Binary Sequences Derived From Differences of Consecutive Primitive Roots. / Winterhof, A; Xiao, Z.
    in: IEEE Transactions on Information Theory, Jahrgang 67, Nr. 8, 15.08.2021, S. 5334--5338.
    DOIRISENWBIB
  • Additive and multiplicative Sidon sets. / Roche-Newton, O; Warren, A.
    in: Acta Mathematica Hungarica, Jahrgang 165, Nr. 2, 22.06.2021, S. 326--336.
    DOIRISENWBIB
  • On the distribution of the Rudin-Shapiro function for finite fields. / Dartyge, C; Merai, L; Winterhof, A.
    in: Proceedings of the American Mathematical Society, Jahrgang 149, Nr. 12, 12.05.2021, S. 5013--5023.
    DOIRISENWBIB
  • Improved bounds for pencils of lines. / Roche-Newton, O; Warren, A.
    in: Proceedings of the American Mathematical Society, Jahrgang 149, Nr. 2, 05.03.2021, S. 805–815.
    DOIRISENWBIB
  • The spherical Kakeya problem in finite fields. / Makhul, M; Warren, A; Winterhof, A.
    in: SIAM Journal on Discrete Mathematics, Jahrgang 34, Nr. 4, 10.12.2020, S. 2502--2509.
    DOIRISENWBIB
  • A note on the cross-correlation of Costas permutations. / Gomez, D; Winterhof, A.
    in: IEEE Transactions on Information Theory, Jahrgang 66, Nr. 12, 25.11.2020, S. 7724--7727.
    DOIRISENWBIB
  • On iterated product sets with shifts II. / Hanson, B; Roche-Newton, O; Zhelezov, D.
    in: Algebra and Number Theory, Jahrgang 14, Nr. 8, 04.10.2020, S. 2239--2260.
    RISENWBIB
  • A note on Hall's sextic residue sequence: correlation measure of order k and related measures of pseudorandomness. / Aly, H; Winterhof, A.
    in: IEEE Transactions on Information Theory, Jahrgang 66, Nr. 3, 21.02.2020, S. 1944--1947.
    DOIRISENWBIB
  • Constructions for the Elekes-Szabó and Elekes-Rónyai problems. / Makhul, M; Roche-Newton, O; Warren, A et al.
    in: Electronic Journal of Combinatorics, Jahrgang 27, Nr. 1, 19.02.2020, S. Paper No. 1.57, 8 pp.
    RISENWBIB
  • Probabilities of incidence between lines and a plane curve over finite fields. / Makhul, Mehdi; Schicho, Josef; Gallet, Matteo.
    in: Finite Fields and their Applications, Jahrgang 61, Nr. 101582, 17.09.2019, S. 22pp.
    WebsiteRISENWBIB
  • On products of shifts in arbitrary fields. / Warren, A.
    in: Moscow Journal of Combinatorics and Number Theory, Jahrgang 8, Nr. 3, 09.09.2019, S. 247--261.
    RISENWBIB
  • r-th order nonlinearity, correlation measure and least significant bit of the discrete logarithm. / Hofer, R; Winterhof, A.
    in: Cryptography and Communications, Jahrgang 11, Nr. 5, 09.09.2019, S. 993--997.
    RISENWBIB
  • If A+A is small then AAA is superquadratic. / O, Roche-Newton and Ilya D.
    in: Journal of Number Theory, Jahrgang 201, 01.08.2019, S. 124-134.
    DOIRISENWBIB
  • A family of four-variable expanders with quadratic growth. / Makhul, M.
    in: Moscow Journal of Combinatorics and Number Theory, Jahrgang 8, Nr. 2, 28.06.2019, S. 143--149.
    RISENWBIB
  • Conical Kakeya and Nikodym sets in finite fields. / Warren, A; Winterhof, A.
    in: Finite Fields and their Applications, Jahrgang 59, 04.06.2019, S. 185--198.
    RISENWBIB
  • On iterated product sets with shifts. / Hanson, B; O, Roche-Newton and D.
    in: Mathematika, Jahrgang 65, Nr. 4, 21.05.2019, S. 831-850.
    RISENWBIB
  • On the size of the set AA+A. / Roche-Newton, Oliver; Imre, Z; Ruzsa, Chun-Yen Shen et al.
    in: Journal of the London Mathematical Society, Jahrgang 99, Nr. 2, 21.05.2019, S. 477-494.
    RISENWBIB
  • On the maximum order complexity of subsequences of the Thue-Morse sequence and Rudin-Shapiro sequence along squares. / Sun, Z; Winterhof, A.
    in: International Journal of Computer Mathematics: Computer Systems Theory, Jahrgang 4, Nr. 1, 02.04.2019, S. 30-36.
    DOIRISENWBIB
  • Codes correcting restricted errors. / Shparlinski, I; Winterhof, A.
    in: Designs, Codes, and Cryptography, Jahrgang 87, Nr. 4, 02.04.2019, S. 855-863.
    RISENWBIB
  • New results on sum-product type growth over fields. / Murphy, Brendan; Petridis, Giorgis; Roche-Newton, Oliver et al.
    in: Mathematika, Jahrgang 65, Nr. 3, 02.04.2019, S. 588-642.
    RISENWBIB
  • Analogues of the Balog--Wooley decomposition for subsets of finite fields and character sums with convolutions. / Roche-Newton, O; Shparlinski, I.E; Winterhof, A.
    in: Annals of Combinatorics, Jahrgang 23, Nr. 1, 02.04.2019, S. 183-205.
    RISENWBIB
  • On discrete values of bilinear forms. / Iosevich, A; Roche-Newton, O; Rudnev, M.
    in: Sbornik Mathematics, Jahrgang 209, Nr. 10, 18.12.2018, S. 71--88.
    RISENWBIB
  • Packing sets over finite abelian groups. / Roche-Newton, O; Shkredov, I; Winterhof, A.
    in: Integers, Jahrgang 18, Nr. Paper No. A38, 15.06.2018, S. 9 pp.
    RISENWBIB
  • On the difference between permutation polynomials over finite fields. / Anbar, N; Oduzak, A; Patel, V et al.
    in: Finite Fields and their Applications, Jahrgang 49, 01.01.2018, S. 132-142.
    RISENWBIB

Book/Monograph

Contribution in Collection

  • On the Carlitz rank of permutation polynomials: Recent developments. / Anbar, N; Ozdak, A; Patel, V et al.
    Proceedings of Women in Numbers Europe 2. Springer, 2019. S. 39--55.
    RISENWBIB

Dissertation

  • The Sum-Product Phenomenon and Discrete Geometry. / Warren, Audie.
    Linz: JKU Linz, 2020.
    RISENWBIB

Workingpaper

  • Convexity, Superquadratic Growth, and Dot Products. / Hanson, B; Roche-Newton, O; Senger, S.
    2021.
    RISENWBIB
  • Low-energy decomposition results over finite fields. / Mohammadi, A; Stevens, S.
    2021.
    RISENWBIB
  • On sum sets of convex functions. / Stevens, S; Warren, A.
    2021.
    RISENWBIB
  • No perfect triangle is isosceles. / Makhul, M.
    2020.
    RISENWBIB
  • Arcs in F_q^2. / Roche-Newton, O; Warren, A.
    2020.
    RISENWBIB