×

Polynomial configurations in subsets of random and pseudo-random sets. (English) Zbl 1401.11014

Summary: We prove transference results for sparse random and pseudo-random subsets of \(\mathbb{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\geq 2\) any subset of the first \(N\) integers of density at least \(C(\log N)^{- \frac{1}{4} \log \log \log \log N}\) contains a configuration of the form \(\{x, x + d^k \}\) for some integer \(d > 0\). Let \([\mathbb{Z}_N]_p\) denote the random set obtained by choosing each element from \(\mathbb{Z}_N\) with probability \(p\) independently. Our first result shows that for \(p > N^{- 1 / k + o(1)}\) asymptotically almost surely any subset \(A \subset [\mathbb{Z}_N]_p\) (\(N\) prime) of density \(| A | / p N \geq(\log N)^{- \frac{1}{5} \log \log \log \log N}\) contains the polynomial configuration \(\{x, x + d^k \}\), \(0 < d \leq N^{1 / k}\). This improves on a result of Nguyen in the setting of \(\mathbb{Z}_N\).
Moreover, let \(k\geq 2\) be an integer and let \(\gamma > \beta > 0\) be real numbers satisfying \[ \gamma +(\gamma - \beta) /(2^{k + 1} - 3) > 1. \] Let \(\Gamma \subseteq \mathbb{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 \subseteq \Gamma\) with positive relative density contains the polynomial configuration \(\{x, x + d^k \}\), \(0 < d \leq 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\).

MSC:

11B05 Density, gaps, topology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balog, A.; Pelikán, J.; Pintz, J.; Szemerédi, E., Difference sets without \(κ\) th powers, Acta Math. Hungar., 65, 2, 165-187 (1994) · Zbl 0816.11014
[2] Bourgain, J., On triples in arithmetic progression, Geom. Funct. Anal., 9, 5, 968-984 (1999) · Zbl 0959.11004
[4] Conlon, David; Fox, Jacob; Zhao, Yufei, Extremal results in sparse pseudorandom graphs, Adv. Math., 256, 256, 206-290 (2014) · Zbl 1285.05096
[5] Furstenberg, Harry, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Anal. Math., 31, 204-256 (1977) · Zbl 0347.28016
[6] Gauy, M.; Hàn, H.; Oliveira, I., Erdős-Ko-Rado for random hypergraphs: asymptotics and stability, Combin. Probab. Comput. (2016), in press · Zbl 1371.05267
[8] Green, Ben, On arithmetic structures in dense sets of integers, Duke Math. J., 114, 2, 215-238 (2002) · Zbl 1020.11010
[9] Green, Ben, Roth’s theorem in the primes, Ann. of Math. (2), 161, 3, 1609-1636 (2005) · Zbl 1160.11307
[10] Hamel, M.; Lyall, N.; Rice, A., Improved bounds on Sarkozy’s theorem for quadratic polynomials, Int. Math. Res. Not., 8, 1761-1782 (2013) · Zbl 1337.11006
[11] Hardy, G. H.; Littlewood, J. E., A new solution of Waring’s problem, Q. J. Math., 48, 272-293 (1919) · JFM 47.0114.01
[12] Balogh, József; Morris, Robert; Wojciech, Samotij, Independent sets in hypergraphs, J. Amer. Math. Soc., 2015, 669-709 (2015) · Zbl 1310.05154
[13] Kohayakawa, Yoshiharu; Rödl, Vojtěch; Schacht, Mathias; Skokan, Jozef, On the triangle removal lemma for subgraphs of sparse pseudorandom graphs, (An Irregular Mind. An Irregular Mind, Bolyai Soc. Math. Stud., vol. 21 (2010), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 359-404 · Zbl 1213.05238
[14] Łaba, I.; Hamel, M., Arithmetic structures in random sets, Integers, 8, 21 (2008) · Zbl 1195.11037
[15] Mockenhaupt, Gerd; Tao, Terence, Restriction and Kakeya phenomena for finite fields, Duke Math. J., 121, 1, 35-74 (2004) · Zbl 1072.42007
[16] Nathanson, Melvyn B., Additive number theory, (The Classical Bases. The Classical Bases, Graduate Texts in Mathematics, vol. 164 (1996), Springer-Verlag: Springer-Verlag New York) · Zbl 0859.11002
[17] Nguyen, H. H., On two-point configurations in random set, Integers, 9, 41-45 (2009) · Zbl 1207.11021
[18] Pintz, János; Steiger, W. L.; Szemerédi, Endre, On sets of natural numbers whose difference set contains no squares, J. Lond. Math. Soc. (2), 37, 2, 219-231 (1988) · Zbl 0651.10031
[19] Ruzsa, I. Z., Difference sets without squares, Period. Math. Hungar., 15, 3, 205-209 (1984) · Zbl 0552.10035
[20] Sárkőzy, A., On difference sets of sequences of integers. I, Acta Math. Acad. Sci. Hung., 31, 1-2, 125-149 (1978) · Zbl 0387.10033
[21] Saxton, David; Thomason, Andrew, Hypergraphs containers, Invent. Math., 201, 3, 925-992 (2015) · Zbl 1320.05085
[23] Tao, T.; Vu, V. H., Additive Combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105 (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1179.11002
[24] Tao, Terence; Ziegler, Tamar, The primes contain arbitrarily long polynomial progressions, Acta Math., 201, 2, 213-305 (2008) · Zbl 1230.11018
[25] Tomas, Peter A., A restriction theorem for the Fourier transform, Bull. Amer. Math. Soc., 81, 477-478 (1975) · Zbl 0298.42011
[26] Varnavides, P., On certain sets of positive density, J. Lond. Math. Soc., 34, 358-360 (1959) · Zbl 0088.25702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.