Non-degenerate Hilbert cubes in random sets. (English) Zbl 1126.11014

Sándor, Csaba

J. Théor. Nombres Bordx. 19, No. 1, 249-261 (2007).

A \(k\)-cube \(H\subseteq\{1,\ldots,n\}\) has the form \(\{a_0+\sum_{i\in I}a_i: I\subseteq\{1,\dots,k\}\}\) with \(a_0,a_1,\ldots,a_k\in\{1,\dots,n\}\). It is called non-degenerate if \(| H| =2^k\). By D. S. Gunderson and V. Rödl’s refinement [Comb. Probab. Comput. 7, 65–79 (1998; Zbl 0892.05050)] of Szemerédi’s cube lemma, each set \(S\subseteq\{1,\ldots,n\}\) with \(| S| \geq n/2\) contains a \(\lfloor\log_2\log_2n-3\rfloor\)-cube.
In the paper under review, the author shows that in a random set \(S\) with Pr\((s\in S)=1/2\) for all \(s=1,\dots,n\), \(\max\{k:S\) contains a non-degenerate \(k\)-cube} is almost everywhere nearly \(\log_2\log_2n+\log_2\log_2\log_2n\).

Reviewer: Sun Zhi-Wei (Nanjing)

MSC:

11B75	Other combinatorial number theory
05D40	Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
11P99	Additive number theory; partitions

Keywords:

Hilbert cube; subset sum; random set

Citations:

Zbl 0892.05050

References:

[1]	N. Alon, J. Spencer, The Probabilistic Method. Wiley-Interscience, Series in Discrete Math. and Optimization, 1992. · Zbl 0767.05001
[2]	A. Godbole, S. Janson, N. Locantore, R. Rapoport, Random Sidon Seqence. J. Number Theory 75 (1999), no. 1, 7-22. · Zbl 0924.11006
[3]	D. S. Gunderson, V. Rödl, Extremal problems for Affine Cubes of Integers. Combin. Probab. Comput 7 (1998), no. 1, 65-79. · Zbl 0892.05050
[4]	R. L. Graham, B. L. Rothchild, J. Spencer, Ramsey Theory. Wiley-Interscience, Series in Discrete Math. and Optimization, 1990. · Zbl 0705.05061
[5]	N. Hegyvári, On the dimension of the Hilbert cubes. J. Number Theory 77 (1999), no. 2, 326-330. · Zbl 0989.11012