Make $ 1000 from simple combinatorics

This is problem 5.5.2 of “the generic chaining” book. You have to have a look at the book to get the connection between this problem and stochastic processes, but the problem can be understood without knowing anything about this book.

Consider a number δ ≤ 1/2, an integer N and the product measure P on {0, 1}^{N}, when on each factor one gives mass δ to 1 and 1 − δ to 0. Given an integer q and a set D ⊂ {0, 1}^{N} we define

D^{(q)} = {(x_{1}, ⋯, x_{N}) ∈ {0, 1}^{N}; ∀(x_{1}^{1}, ⋯, x_{N}^{1}), ⋯, (x_{1}^{q}, ⋯, x_{N}^{q}) ∈ D,
∃i ≤ N, x_{i} = 1, x_{i}^{1}, ⋯, x_{i}^{q} = 0}.

If one identifies points in {0, 1}^{N} with subsets of {1, ⋯, N}, then D^{(q)} is simply the collection of subsets of {1, ⋯, N} that cannot be covered by q elements of D. Also, P is the law of a random set J obtained as follows: for each i ∈ {1, ⋯, N} the probability that i ∈ J is δ, and these probabilities are independent over i.

Given a subset I of {0, 1}^{N}, we denote

B(I) = {(x_{1}, ⋯, x_{N}) ∈ {0, 1}^{N}; ∀i ∈ I, x_{i} = 1}.

This is simply the collection of subsets of {1, ⋯, N} that contain I.

Problem. Can one find a number q, independent of N and δ, such that for each set D with P (D) ≥ 1 − 1/q we can find a family G of subsets of {1, ⋯, N} such that

D^{(q)} ⊂ ⋃_{I∈G} B(I)

and

∑_{I∈G} δ^{cardI} ≤ 1/2?

If, rather that the above condition you obtain the weaker condition that

∑_{I∈G} δ^{′cardI} ≤ 1/2,

where δ′ depends on δ only, you get the money. (The case δ = 1/2 won’t get you anything, q = 2 works.)

This problem is discussed in great detail in my paper “Are many small sets explicitly small?”, which is available in the section “Preprints” of this site. Problems related to this one (but in some sense less basic) are explained in my paper “Are all sets of positive measure essentially convex?” Operator theory: Advances and applications. Vol. 77, Birkhäuser, 1995, p. 295-310. The new book “Upper and Lower bounds...” is also relevant.