Polynomial configurations in subsets of random and pseudo-random sets.

We prove transference results for sparse random and pseudo-random subsets of Z N , which are analogous to the quantitative version of the well-known Furstenberg–Sárközy theorem due to Balog, Pintz, Steiger and Szemerédi. In the dense case, Balog et al. showed that there is a constant C > 0 such that for all integer k ≥ 2 any subset of the first N integers of density at least C ( log ⁡ N ) − 1 4 log ⁡ log ⁡ log ⁡ log ⁡ N contains a configuration of the form { x , x + d k } for some integer d > 0 . Let [ Z N ] p denote the random set obtained by choosing each element from Z N with probability p independently. Our first result shows that for p > N − 1 / k + o ( 1 ) asymptotically almost surely any subset A ⊂ [ Z N ] p ( N prime) of density | A | / p N ≥ ( log ⁡ N ) − 1 5 log ⁡ log ⁡ log ⁡ log ⁡ N contains the polynomial configuration { x , x + d k } , 0 < d ≤ N 1 / k . This improves on a result of Nguyen in the setting of Z N . Moreover, let k ≥ 2 be an integer and let γ > β > 0 be real numbers satisfying γ + ( γ − β ) / ( 2 k + 1 − 3 ) > 1 . Let Γ ⊆ Z N ( N prime) be a set of size at least N γ and linear bias at most N β . Then our second result implies that every A ⊆ Γ with positive relative density contains the polynomial configuration { x , x + d k } , 0 < d ≤ N 1 / k . For instance, for squares, i.e., k = 2 , and assuming the best possible pseudo-randomness β = γ / 2 our result applies as soon as γ > 10 / 11 . [ABSTRACT FROM AUTHOR]