Polynomial configurations in subsets of random and pseudo-random sets

Author(s)

Aigner-Horev, Elad ^[1] ; Han, Hiep ^[2]

Affiliation

^[1] Ariel Univ, Dept Math & Comp Sci, Ariel - Israel

^[2] Pontificia Univ Catolica Valparaiso, Inst Matemat, Valparaiso - Chile

• Document type: Journal article
• Source: JOURNAL OF NUMBER THEORY; v. 165, p. 363-381, AUG 2016.
• Web of Science Citations: 0

Abstract

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-Sarkozy theorem due to Balog, Pintz, Steiger and Szemeredi. 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+0(1) asymptotically almost surely any subset A subset of {[}Z(N)](p) (N prime) of density vertical bar A vertical bar/p(N) >= (log N)(- /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 gamma > beta > 0 be real numbers satisfying gamma + (gamma - beta)/(2(k+1) -3) > 1. Let Gamma subset of Z(N) (N prime) be a set of size at least N-gamma and linear bias at most N-beta. Then our second result implies that every A subset of Gamma with positive relative density contains the polynomial configuration [x, x dk], 0 < d <= N-1/k, For instance, for squares, i.e., k = 2, and assuming the best possible pseudo-randomness beta = gamma/2 our result applies as soon as gamma > 10/11. (C) 2016 Published by Elsevier Inc. (AU)

• FAPESP's process: 13/11353-1 - Degenerate extremal problems for random discrete structures
• Grantee: Hiep Han
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• FAPESP's process: 10/16526-3 - Quasi-random hypergraphs and spanning subhypergraph containment
• Grantee: Hiep Han
• Support Opportunities: Scholarships in Brazil - Post-Doctoral