Talagrand’s discrete-convexity conjecture

Proof. If E_2(\mathcal D)=\varnothing, the empty cover suffices. Otherwise it is a nonempty proper increasing family: \mathcal D\ne\varnothing, so \varnothing\notin E_2(\mathcal D), and the defining obstruction is preserved by taking supersets. By Li’s result [6, Corollary 3.1] in Park’s fractional-cover formulation [9, Theorem 3.4], this family has a fractional cover of cost at most 1/2 at r=p/2. Capping each coefficient at one preserves coverage and does not increase cost. The companion expectation-threshold theorem [8, Theorem 1.1] then gives an integral cover of cost at most 1/2 at r/(25\cdot512^4). Thus C=50\cdot512^4 suffices.□

Proof. Put

For I\subseteq X with |I|\le r, define its weighted degree by

Large weighted degrees. Begin with the generators

Counting the subsets of each edge gives

Consequently,

Call an edge regular if it contains no member of \mathcal C_0, and let \mathcal H' be the family of regular edges. In particular,

We will use this regularity in the following form. Given B\subseteq X, group the edges e\in\mathcal H' according to I=e\cap B. Each nonempty group contributes

It follows that

Sampled pairs. Independently for each ordered pair (e,e')\in(\mathcal H')^2, including the diagonal pairs, sample that pair with probability \pi. Let \mathcal C_1 consist of the unions of the sampled pairs. Applying (2.2) with B=e, so that |B|=r, yields

Thus

The first inequality counts unions with multiplicity. Distinct ordered pairs remain independent sampling indices even when their unions coincide.

Residual generators. For every ordered tuple (e_1,\ldots,e_m) of distinct regular edges, add e_1\cup\cdots\cup e_m to \mathcal C_2 if none of the pairs (e_i,e_j), 1\le i,j\le m, was sampled. Then

covers the target family for every sampling outcome. Indeed, a target set S containing no generator from \mathcal C_0 contains at least m distinct regular edges. Choose m of them. If a pair among these edges was sampled, its union is a member of \mathcal C_1 contained in S; otherwise their full union belongs to \mathcal C_2.

It remains to bound the expected cost of \mathcal C_2. For 0\le t\le m, let

For a prefix of length t<m, its union B has size at most rt\le rm. The elementary inequality

can be seen by ordering B, listing the members of each subset of size at most r, and padding the list to length r with a new symbol. Since \rho^{|B\cup e|}=\rho^{|B|}\rho^{|e\setminus B|}, (2.2) bounds the total weight of extensions of this prefix by

Allowing all regular edges as possible extensions only increases this bound. Summing over prefixes and iterating gives

The m^2 ordered pair indices associated with a tuple of distinct edges are all distinct. Hence the probability that this tuple contributes a residual generator is exactly

Linearity of expectation, again counting generators with multiplicity, therefore gives

To make this at most 2^{-m}, it is enough that

The choice of m makes \pi m=2^{4h}, while the left side is bounded by a quadratic function of h. Indeed,

Here we used r\le h, h+1\le2^h, and h\ge64. It follows that

Combining (2.1), (2.3), and (2.4), we obtain

All families and sampling indices are finite, so some outcome has cost at most its expectation. Since every outcome supplies a cover, this proves the lemma.□

Proof. Identify subsets of [N] with their indicator vectors and write f=\mathbf 1_{\mathcal F}. For U\subseteq[N], define

where Y has independent Bernoulli-q coordinates on [N]\setminus U. In particular, b(\varnothing)=\mu_q(\mathcal F).

We will compare a global bound on the weights with a lower bound on their sixteenth powers over subsets of each exceptional set. In a bin where w(U)\le2^{-h}, fewer than 2^{12h} terms contribute at most 2^{-4h} to the sum of sixteenth powers. This is the gap exploited by Lemma 2.1.

The global weight bound. We use the standard biased Fourier basis [7, Section 8.4], with its normalization made explicit here. Under the product law \mu_q, the functions

are orthonormal: each standardized coordinate has mean zero and variance one, and the coordinates are independent. Since 0<q<1, the measure has full support; these 2^N orthonormal functions form a basis of the 2^N-dimensional space of real functions on the cube. Set \widehat f(U)=\mathbb E[f(X)\chi_U(X)] for X\sim\mu_q. For a Bernoulli-q bit X_i and z_i\in\{0,1\},

Summing over the coordinates in U therefore gives

Consequently, Parseval’s identity yields

This calculation holds for all q\in(0,1).

A bound on every exceptional set. Fix S\in E_{32}(\mathcal F). We claim that

Consider an array of bits with 32 rows and N columns. For a column y\in\{0,1\}^{32}, let

For columns in S, we want a correction that cancels the all-zero column and factors across rows. A suitably scaled parity term has both properties. Give each column outside S the mass function P, and give each column in S the signed mass function

With two rows, this is precisely Li’s signed kernel after multiplying by the Bernoulli masses [6, Section 2]. Park also notes the extension of Li’s argument to an even number of unions [9, Corollary 3.5, footnote 3]. Here the higher powers obtained from 32 rows are combined with Lemma 2.1 to obtain a fixed density loss. The signed-operator approach to forbidden configurations and its biased Fourier basis have earlier forms in [4, Section 2.2] and [2, Section 4.1]. Let \nu_S be the product of these column masses. Since R(0,\ldots,0)=0, every array with nonzero \nu_S-weight has a 1 in each column of S. The sets represented by its rows therefore have union containing S. By the definition of E_{32}(\mathcal F), these rows cannot all lie in \mathcal F. Writing x_j for row j, we obtain

This uses pointwise vanishing of the product on the support of \nu_S; nonnegativity of the signed masses is unnecessary.

Expand the column products, and let U\subseteq S be the columns in which the subtracted term is chosen. After taking out (-1)^{|U|}, the correction contributes

All coordinates outside U retain their Bernoulli product masses. Thus the sum factors over rows. In each row the factor is precisely b(U) from (3.1), because the power (1-q)^{32|U|} distributes as (1-q)^{|U|} to each row. It follows that

All products and sums here are finite. Isolating the empty term and using the triangle inequality gives

which proves (3.3).

Constructing the cover. Set \rho=q/L. First include all sets in

as generators. For U\in\mathcal G_0 with r=|U|\ge1,

Hence (3.2) gives

Partition the remaining nonempty sets of positive weight into families

where r\ge1 and h is an integer. Every such set belongs to exactly one bin, and every occupied bin has h\ge64r. Indeed, its weights are strictly below 2^{-64r}; a weight equal to that threshold was included in \mathcal G_0. By (3.2),

for each occupied bin. In particular,

Since h\ge64r\ge64, all the hypotheses of Lemma 2.1 hold. Choose a cover \mathcal G_{r,h} of the sets containing at least 2^{12h} members of \mathcal H_{r,h}, with

There are only finitely many occupied bins, because the ground set is finite. We may therefore choose these covers simultaneously and form

Removing any repeated generators can only decrease its cost. The geometric sum

and (3.5) imply

It remains to show that \mathcal G covers E_{32}(\mathcal F). Suppose that S\subseteq[N] contains no member of \mathcal G. It contains no member of \mathcal G_0 and fewer than 2^{12h} members of each bin \mathcal H_{r,h}. Zero weights contribute nothing, so

By (3.3), such an S cannot belong to E_{32}(\mathcal F). Thus \mathcal G is the required cover.□

Proof of Theorem 1.1. Set L=2^{70} and k=32L=2^{75}, and suppose that \mu_p(\mathcal D)\ge1-1/k. In particular, \mathcal D is nonempty. We construct L random sets R_1,\ldots,R_L, each with law \mu_p. For any such construction the union bound gives

Independence between rows is not required.

Case 1: Lp<1. For each coordinate i, independently across coordinates, choose a label J_i\in\{0,1,\ldots,L\} with

Put R_j=\{i:J_i=j\}. For a fixed row j, its membership indicators are independent Bernoulli variables of parameter p, so R_j has law \mu_p. The union R=R_1\cup\cdots\cup R_L has law \mu_q, where q=Lp\in(0,1): a coordinate belongs to R precisely when its label is nonzero. Figure 1 illustrates the construction with three rows.

Define

On the event in (4.1), the union R belongs to \mathcal F. Hence

Grouping a tuple of 32L members of \mathcal D into 32 groups of size L, or conversely expanding 32 members of \mathcal F, shows that the possible unions agree exactly. Thus

Proposition 3.1 makes this family (q/L)-small. Since q/L=p, this is the required conclusion.

Case 2: Lp\ge1. Set

At each coordinate i, choose a mandatory row uniformly among the L rows. Include i in that row, and, conditional on this choice, include it independently in each other row with probability t. Make these choices independently across coordinates. For each fixed row j,

and the coordinates of R_j are independent. Thus each R_j again has law \mu_p, while the union of all rows is [N] in every outcome.

By (4.1), some outcome has all L rows in \mathcal D. These rows cover [N]. Repeating the resulting tuple 32 times gives exactly k members of \mathcal D with full union. Consequently E_k(\mathcal D)=\varnothing, which is covered at cost zero by the empty family. This construction also covers the boundary Lp=1, when t=0.□