FWF Project P 30405-N32
Runtime: 01.09.2017-31.08.2021
Project Team
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|\ge \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 \cdot A=\{ab : a,b \in A\}$ or the sum set $A+A=\{a+b : a,b \in 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
- Makhul, M.; Winterhof, A. (2022) Normality of the Thue-Morse function for finite fields along polynomial values. Research in Number Theory, Bd. to appear, S. 19.
- Merai, L.; Winterhof, A. (2022) Pseudorandom sequences derived from automatic sequences. Cryptography and Communications, Bd. to appear, S. 33.
- Winterhof, A.; Xiao, Z. (2022, online: 2020) Sequences of the parities of differences of consecutive quadratic residues. Advances in Mathematics of Communications, Bd. 16 (1), S. 83--93.
- Mohammadi, A.; Stevens, S. (2021) Attaining the exponent 5/4 for the sum-product problem in finite fields. International Mathematical Research Notices, Bd. n/a, S. n/a.
- Liu, H.; Winterhof, A. (2021) Balance and pattern distribution of sequences derived from pseudorandom subsets of Z_q. Unif. Distrib. Theory, Bd. 16 (2), S. 89--108.
- Rudnev, M.; Stevens, S. (2021) An update on the sum-product problem. Mathematical Proceedings of the Cambridge Philosophical Society, Bd. n/a, S. 1-20.
- Hanson, B.; Roche-Newton, O.; Rudnev, M. (2021) Higher convexity and iterated sum sets. Combinatorica, Bd. to appear, S. 15pp.
- Roche-Newton, O. (2021) Sums, products and dilates on sparse graphs. SIAM Journal on Discrete Mathematics 35, Bd. 1, S. 194-204.
- Roche-Newton, O.; Warren, A. (2021) New expander bounds from affine group energy. Discrete & Computational Geometry, Bd. 66 (2), S. 552-574.
- Swaenepoel, C.; Winterhof, A. (2021) Additive double character sums over some structured sets and applications. Acta Arithmetica, Bd. 199 (2), S. 135--143.
- Makhul, M. (2021) On the number of perfect triangles with a fixed angle. Discrete Comput. Geom., Bd. 66 (3), S. 1143--1149.
- Winterhof, A.; Xiao, Z. (2021) Binary Sequences Derived From Differences of Consecutive Primitive Roots. IEEE Trans. Inf. Theory, Bd. 67 (8), S. 5334--5338.
- Roche-Newton, O.; Warren, A. (2021) Additive and multiplicative Sidon sets. Acta Mathematica Hungarica, Bd. 165 (2), S. 10.
- Makhul, M.; Roche-Newton, O.; Stevens, S.; Warren, A. (2021) The Elekes-Szabo problem and the uniformity conjecture. Israel Journal of Mathematics, Bd. to appear, S. 23.
- Dartyge, C.; Merai, L.; Winterhof, A. (2021) On the distribution of the Rudin-Shapiro function for finite fields. Proceedings of the American Mathematical Society, Bd. 149 (12), S. 5013--5023.
- Roche-Newton, O.; Warren, A. (2021) Improved bounds for pencils of lines. Proceedings of the American Mathematical Society, Bd. 149 (2), S. 805–815.
- Makhul, M.; Warren, A.; Winterhof, A. (2020) The spherical Kakeya problem in finite fields. SIAM J. Discrete Math., Bd. 34 (4), S. 2502--2509.
- Gomez, D.; Winterhof, A. (2020) A note on the cross-correlation of Costas permutations. IEEE Transactions on Information Theory, Bd. 66 (12), S. 7724--7727.
- Isik, L.; Winterhof, A. (2020) On the index of the Diffie-Hellman mapping. Applicable Algebra in Engineering, Communication and Computing, Bd. to appear, S. 10.
- B. Hanson, O. Roche-Newton, D. Zhelezov (2020, online: 2021) On iterated product sets with shifts II. Algebra and Number Theory, Bd. 14 (8), S. 2239--2260.
- Petridis, G.; Roche-Newton, O.; Rudnev, M.; Warren, A. (2020) An energy bound in the affine group. International Mathematics Research Notices, Bd. to appear, S. 10.
- Aly, H.; Winterhof, A. (2020) A note on Hall's sextic residue sequence: correlation measure of order k and related measures of pseudorandomness. IEEE Trans. Inf. Th., Bd. 66 (3), S. 1944--1947.
- Makhul, M.; Roche-Newton, O.; Warren, A.; de Zeeuw, F. (2020) Constructions for the Elekes-Szabó and Elekes-Rónyai problems. Electronic Journal of Combinatorics, Bd. 27 (1), S. Paper No. 1.57, 8 pp.
- Mehdi Makhul, Josef Schicho, Matteo Gallet (2019) Probabilities of incidence between lines and a plane curve over finite fields. Finite Fields and Their Applications, Bd. 61 (101582), S. 22pp.
- Warren, A. (2019) On products of shifts in arbitrary fields. Moscow Journal of Combinatorics and Number Theory, Bd. 8 (3), S. 247--261.
- R. Hofer, A. Winterhof (2019) r-th order nonlinearity, correlation measure and least significant bit of the discrete logarithm. Cryptography and Communications, Bd. 11 (5), S. 993--997.
- Shkredov, O. Roche-Newton and Ilya D. (2019) If A+A is small then AAA is superquadratic. Journal of Number Theory, Bd. 201, S. 124-134.
- Makhul, M. (2019) A family of four-variable expanders with quadratic growth. Mosc. J. Comb. Number Theory, Bd. 8 (2), S. 143--149.
- Warren, A.; Winterhof, A. (2019) Conical Kakeya and Nikodym sets in finite fields. Finite Fields and Their Applications, Bd. 59, S. 185--198.
- Oliver Roche-Newton, Imre Z. Ruzsa, Chun-Yen Shen, Ilya D. Shkredov (2019) On the size of the set AA+A. Journal of the London Mathematical Society, Bd. 99 (2), S. 477-494.
- Brendan Murphy, Giorgis Petridis, Oliver Roche-Newton, Misha Rudnev, Ilya D. Shkredov (2019) New results on sum-product type growth over fields. Mathematika, Bd. 65 (3), S. 588-642.
- O. Roche-Newton, I.E. Shparlinski, A. Winterhof (2019) Analogues of the Balog--Wooley decomposition for subsets of finite fields and character sums with convolutions. Annals of Combinatorics, Bd. 23 (1), S. 183-205.
- I. Shparlinski, A. Winterhof (2019) Codes correcting restricted errors. Designs, Codes and Cryptography, Bd. 87 (4), S. 855-863.
- Sun, Z.; Winterhof, A. (2019) On the maximum order complexity of subsequences of the Thue-Morse sequence and Rudin-Shapiro sequence along squares. International Journal of Computer Mathematics: Computer Systems Theory, Bd. 4 (1), S. 30-36.
- Iosevich, A.; Roche-Newton, O.; Rudnev, M. (2018) On discrete values of bilinear forms. Mat. Sb, Bd. 209 (10), S. 71--88.
- O. Roche-Newton, I. Shkredov, A. Winterhof (2018) Packing sets over finite abelian groups. Integers, Bd. 18 (Paper No. A38), S. 9 pp.
- N. Anbar, A. Oduzak, V. Patel, L. Quoos, A. Somoza, A. Topuzoglu (2018, online: 2017) On the difference between permutation polynomials over finite fields. Finite Fields and Their Applications, Bd. 49, S. 132-142.
- B. Hanson, O. Roche-Newton and D. Zhelezov (online: 2019) On iterated product sets with shifts. Mathematika, Bd. 65 (4), S. 831-850.
- Brendan Murphy, Giorgis Petridis, Thang Pham, Misha Rudnev, Sophie Stevens On the Pinned Distances Problem in Positive Characteristic. Journal of the London Mathematical Society, Bd. To appear, S. n/a.
Book/Monograph
- K.-U. Schmidt, A. Winterhof (eds.) (2019) Combinatorics and finite fields: Difference sets, polynomials, pseudorandomness and applications. In Reihe: Radon Series on Computational and Applied Mathematics, 23; Berlin: de Gruyter.
Contribution in Collection
- N. Anbar, A. Ozdak, V. Patel, L. Quoos, A. Somoza, A. Topuzoğlu (2019) On the Carlitz rank of permutation polynomials: Recent developments. In: Bouw, I., Özman, E., Johnson-Leung, J., Newton, R. (Hrsg.), Proceedings of Women in Numbers Europe 2: Springer, S. 39--55.
Dissertation
- Warren, A. (2020) The Sum-Product Phenomenon and Discrete Geometry. Doktorarbeit, Institute for Financial Mathematics and Applied Number Theory, JKU Linz, Linz.
Workingpaper
- Stevens, S.; Warren, A. (2021) On sum sets of convex functions.
- Mohammadi, A.; Stevens, S. (2021) Low-energy decomposition results over finite fields.
- Makhul, M.; Pinchasi, R. (2021) 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. (2020) No perfect triangle is isosceles.
- Roche-Newton, O.; Warren, A. (2020) Arcs in $F_{q^2}$.