×

Pseudorandomness of large sets in finite fields. (English) Zbl 1466.11005

Schmidt, Kai-Uwe (ed.) et al., Combinatorics and finite fields. Difference sets, polynomials, pseudorandomness and applications. Selected papers based on the presentations at the workshop on pseudo-randomness and finite fields, Linz, Austria, October 15–18, 2018. Berlin: De Gruyter. Radon Ser. Comput. Appl. Math. 23, 199-210 (2019).
The celebrated Roth’s 3-term progression theorem provides an answer on the cardinality of subsets \(A\) of finite fields \(\mathbb{F}_p\) guarantying a nontrivial solution to equation \(a_1-a_2=a_2-a_3\) with all variables \(a_1,a_2,a_3\in A\) and not all equal. In the first part of the paper the author gives a short commented overview of results extending this result in direction of J. Bourgain et al. [Isr. J. Math. 221, No. 2, 853–867 (2017; Zbl 1420.11024)] and M. Rudnev [Combinatorica 38, No. 1, 219–254 (2018; Zbl 1413.51001)]. He proves – among others – a variant of Rudnev’s theorem on the number of ordered solution to the equation \((a_1-a_2)(a_3-a_4)=(a_5=a_6)(a_7-a_8)\) with \(a_i\in A\), \(i=1,\dots,8\), showing that the pseudorandom term dominates when \(|A|\geq p^{3/5}\). The paper contains examples showing that the proved bound are essentially sharp. He also explains some tools allowing one to make a further progress.
For the entire collection see [Zbl 1420.00048].

MSC:

11B30 Arithmetic combinatorics; higher degree uniformity
11T99 Finite fields and commutative rings (number-theoretic aspects)
05B99 Designs and configurations
51A45 Incidence structures embeddable into projective geometries
52C10 Erdős problems and related topics of discrete geometry
Full Text: DOI