Random Finite Sum Sets and Product Sets in Subsets of the Natural Numbers
DOI:
https://doi.org/10.64229/gppmde45Keywords:
Binomial model, Finite sumsets, Finite product sets, Random subsets, Probabilistic combinatorics, Central limit theoremAbstract
We investigate the occurrence of additive and multiplicative structures in random subsets of the natural numbers. Specifically, for a Bernoulli random subset of N where each integer is included independently with probability p ∈ (0, 1), we prove that almost surely such a set contains finite sumsets (FS-sets) and finite product sets (FP-sets) of every finite length. Then we prove any Bernoulli random subset of N contains a pattern of the form {x, y, x + y, xy}, giving a random solution of the Hindman conjecture.
References
[1]Nathanson MB. Additive number theory. New York: Springer; 1996. DOI: 10.1017/9781108775267.013
[2]Tao T, Vu VH. Additive combinatorics. Cambridge University Press; 2006. DOI: 10.1017/CBO9780511755149
[3]Alon N, Spencer JH. The probabilistic method. John Wiley & Sons; 2016. Available at: http://lib.ysu.am/disciplines_bk/39cbf4832349c9024453be49f58db93e.pdf (accessed on 20 May 2025).
[4]Bollobás B. Random graphs. In Modern graph theory 2011 May 28 (pp. 215-252). New York, NY: Springer New York. DOI: 10.1007/978-1-4612-0619-4_7
[5]Gowers WT. A new proof of Szemerédi's theorem. Geometric & Functional Analysis GAFA, 200, 11(3), 465-588. DOI:10.1007/s00039-001-0332-9
[6]Komlós J, Simonovits M. Szemeredi's Regularity Lemma and its applications in graph theory. Center for Discrete Mathematics & Theoretical Computer Science, 1995. Available at: https://dl.acm.org/doi/abs/10.5555/868009 (accessed on 20 May 2025).
[7]Hindman N. Finite sums from sequences within cells of a partition of N. Journal of Combinatorial Theory, Series A. 1974, 17(1), 1-1. DOI: 10.1016/0097-3165(74)90023-5
[8]Hindman N. Partitions and sums and products of integers. Transactions of the American Mathematical Society. 1979, 247, 227-245. DOI: 10.1090/S0002-9947-1979-0517693-4
[9]Baumgartner JE. A short proof of Hindman's theorem. Journal of Combinatorial Theory, Series A. 1974, 17(3), 384-386. DOI: 10.1016/0097-3165(74)90103-4
[10]Bergelson V, Hindman N. Partition regular structures contained in large sets are abundant. Journal of Combinatorial Theory, Series A. 2001, 93(1), 18-36. DOI: 10.1006/jcta.2000.3061
[11]Bergelson V, Leibman A. Sets of large values of correlation functions for polynomial cubic configurations. Ergodic Theory and Dynamical Systems. 2018, 38(2), 499-522. DOI: 10.1017/etds.2016.49
[12]Erdős P, Rényi A. On the strength of connectedness of a random graph. Acta Mathematica Hungarica. 1961, 12(1-2), 261-267. DOI: 10.1007/bf02066689
[13]Conlon D, Gowers WT. Combinatorial theorems in sparse random sets. Annals of Mathematics. 2016, 184, 367-454. DOI: 10.4007/annals.2016.184.2.2
[14]Rödl V, Ruciński A. Threshold functions for Ramsey properties. Journal of the American Mathematical Society. 1995, 8(4), 917-942. DOI: 10.1090/S0894-0347-1995-1276825-6
[15]Sisto A. Exponential triples. The Electronic Journal of Combinatorics, 2011, 18(1). DOI: 10.37236/634
[16]Sahasrabudhe J. Exponential patterns in arithmetic Ramsey theory. Acta Arithmetica, 2018, 182(1), 13-42. DOI:10.4064/aa8603-9-2017
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Sukrit Chakraborty, Sourav Kanti Patra (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
