A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
Talagrand’s discrete-convexity conjecture
expertly designed by an internal OpenAI model · released 2026-09-23
· original PDF
IntroductionLet \([N]=\{1,\ldots,N\}\), and let \(\mu_p\) be the probability measure on \(2^{[N]}\) under which each coordinate is present independently with probability \(p\in(0,1)\). For a family \(\mathcal D\subseteq2^{[N]}\) and an integer \(k\ge1\), define \[ E_k(\mathcal D) =\bigl\{S\subseteq[N]: S\nsubseteq D_1\cup\cdots\cup D_k \text{ for all }D_1,\ldots,D_k\in\mathcal D\bigr\}. \tag{1}\] The members in a tuple may repeat and need not be disjoint. A family \(\mathcal G\subseteq2^{[N]}\) covers a family \(\mathcal A\) if every \(S\in\mathcal A\) contains some \(I\in\mathcal G\). For \(\rho\in(0,1)\), write \[c_\rho(\mathcal G)=\sum_{I\in\mathcal G}\rho^{|I|}.\] We say that \(\mathcal A\) is \(p\)-small if it has a cover \(\mathcal G\) with \(c_p(\mathcal G)\le1/2\). Since \(\mu_p\{S:I\subseteq S\}=p^{|I|}\), such a cover witnesses \(\mu_p(\mathcal A)\le1/2\) by a union bound. The name reflects the analogy with Talagrand’s Gaussian convexity question [11]: can a bounded number of sums of a compact balanced set of sufficiently large Gaussian measure contain a convex set of Gaussian measure at least \(1/2\), uniformly in the dimension? Here balanced means closed under multiplication by scalars of absolute value at most one. In the discrete problem, unions replace sums, and containment covers describe the exceptional sets. Talagrand formulated the discrete-convexity conjecture in [11]: a fixed number of members of a sufficiently likely family should cover every set outside a \(p\)-small exceptional family. The same original-density formulation appears as Research Problem 13.3.2 in [12], whose Proposition 13.3.3 explains its connection to positive selector processes. We prove this conjecture. Theorem 1. Set \(k=2^{75}\). For every integer \(N\ge1\), every \(p\in(0,1)\), and every family \(\mathcal D\subseteq2^{[N]}\), \[\mu_p(\mathcal D)\ge1-\frac1k \quad\Longrightarrow\quad E_k(\mathcal D)\text{ is }p\text{-small}.\] The constant is independent of \(N\), \(p\), and \(\mathcal D\). The family \(\mathcal D\) is arbitrary; no monotonicity is assumed. Positive selectors.The connection to positive selector processes [11] gives a concrete consequence of the theorem, recovering the positive-selector conclusion proved by Park and Pham [10]. For a nonempty family \(T\subseteq[0,\infty)^N\), define \[\phi(S)=\sup_{t\in T}\sum_{i\in S}t_i, \qquad M=\mathbb E_{\mu_p}\phi,\] and suppose \(0<M<\infty\). Then \(\{S:\phi(S)\ge k^2M\}\) is \(p\)-small for \(k=2^{75}\). Indeed, Markov’s inequality gives \(\mu_p\{D:\phi(D)<kM\}\ge1-1/k\). Nonnegativity of the coordinates makes \(\phi\) monotone and subadditive under unions, so a set with \(\phi(S)\ge k^2M\) cannot be contained in the union of \(k\) such \(D\)’s. Theorem 1 supplies its cover. Thus the large-value event has explicit containment witnesses, beyond the small probability already supplied by Markov’s inequality. Proof strategy and method.The main task is to turn the obstruction to covering a set by unions into an inexpensive family of integral generators. We first work at a fixed fraction of the density. An orthogonal expansion gives nonnegative weights on subsets with a global bound on their weighted sum. A signed product on an array of 32 rows turns the failure of a union cover into a lower bound on the sixteenth powers of those same weights. Its column factor vanishes when all rows miss that coordinate, so the identity follows from pointwise vanishing. The two-row version is Li’s signed kernel after multiplication by the Bernoulli masses [6]. This method has antecedents in the signed product operators and biased Fourier analysis of Friedgut [4] and Ellis, Filmus, and Friedgut [2]. Large individual weights give cheap generators directly. If a set contains none of these generators, the higher-power bound forces it to contain many subsets of one size and comparable weight. An elementary covering lemma handles each such class: it selects subsets of large weighted degree, independently samples unions of pairs of the remaining edges, and adds the residual configurations. Weighted-degree control bounds the cost of extending a tuple, while a long tuple must avoid quadratically many independent pair choices to survive. Random unions also enter the covering constructions of Fischer and Person [3]; the lemma here is proved in full. Section 2 establishes this covering lemma, and Section 3 uses it with the signed identity to cover \(E_{32}(\mathcal F)\) at density \(q/2^{70}\) whenever \(\mu_q(\mathcal F)\ge1/2\). The final step, in Section 4, recovers the original density. We couple dependent rows so that each entire row has the original Bernoulli product law and their union has an exactly prescribed larger density. The probability that all rows belong to the starting family is controlled by a union bound. This exact coupling is what permits arbitrary families and returns the covering cost to \(p\). An elementary covering lemmaWe seek an inexpensive cover of all sets containing many edges of a uniform family with bounded total cost. The construction first selects subsets lying in many edges. The remaining edges then have controlled extension cost, while pair sampling makes long tuples unlikely to survive uncovered: they must avoid quadratically many independent choices. Unions of sampled edges also appear in the covering constructions of Fischer and Person [3]; the argument below is self-contained. Lemma 3. Let \(X\) be a finite set, let \(0<\rho<1\), and let \(r,h\) be integers with \(1\le r\le h\) and \(h\ge64\). Suppose that \(\mathcal H\subseteq\binom{X}{r}\) satisfies \[|\mathcal H|\rho^r\le2^{h+1}.\] Then the family \[\left\{S\subseteq X: |\{e\in\mathcal H:e\subseteq S\}|\ge2^{12h}\right\}\] has a cover \(\mathcal G\subseteq2^X\) with \[c_\rho(\mathcal G)\le3\cdot2^{-h}.\] Proof. Put \[m=2^{12h},\qquad T=2^{4h},\qquad \pi=2^{-8h}.\] For \(I\subseteq X\) with \(|I|\le r\), define its weighted degree by \[d(I)=|\{e\in\mathcal H:I\subseteq e\}|\rho^{r-|I|}.\] Large weighted degrees. Begin with the generators \[\mathcal C_0=\{I\subseteq X:|I|\le r,\ d(I)>T\}.\] Counting the subsets of each edge gives \[\sum_{\substack{I\subseteq X\\|I|\le r}}d(I)\rho^{|I|} =2^r|\mathcal H|\rho^r.\] Consequently, \[ c_\rho(\mathcal C_0) \le T^{-1}2^r|\mathcal H|\rho^r \le2^{r+1-3h}\le2^{1-2h}. \tag{2}\] 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, \[I\subseteq e\in\mathcal H' \quad\Longrightarrow\quad d(I)\le T.\] 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 \[\sum_{\substack{e\in\mathcal H'\\e\cap B=I}} \rho^{|e\setminus B|} =|\{e\in\mathcal H':e\cap B=I\}|\rho^{r-|I|} \le d(I)\le T.\] It follows that \[ \sum_{e\in\mathcal H'}\rho^{|e\setminus B|} \le T\sum_{i=0}^r\binom{|B|}{i}. \tag{3}\] 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 (3) with \(B=e\), so that \(|B|=r\), yields \[\sum_{e'\in\mathcal H'}\rho^{|e'\setminus e|}\le2^rT.\] Thus \[\begin{align*} \mathbb E[c_\rho(\mathcal C_1)] &\le\pi\sum_{e,e'\in\mathcal H'}\rho^{|e\cup e'|} \\ &\le\pi|\mathcal H'|\rho^r2^rT \le2^{r+1-3h}\le2^{1-2h}. \tag{4}\end{align*}\] 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 \[\mathcal G=\mathcal C_0\cup\mathcal C_1\cup\mathcal C_2\] 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 \[W_t= \sum_{\substack{(e_1,\ldots,e_t)\in(\mathcal H')^t\\ e_1,\ldots,e_t\ \text{distinct}}} \rho^{|e_1\cup\cdots\cup e_t|}, \qquad W_0=1.\] For a prefix of length \(t<m\), its union \(B\) has size at most \(rt\le rm\). The elementary inequality \[\sum_{i=0}^r\binom{|B|}{i}\le(1+|B|)^r\le(1+rm)^r\] 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|}\), (3) bounds the total weight of extensions of this prefix by \[\rho^{|B|}\,T(1+rm)^r.\] Allowing all regular edges as possible extensions only increases this bound. Summing over prefixes and iterating gives \[W_{t+1}\le T(1+rm)^rW_t, \qquad W_m\le[T(1+rm)^r]^m.\] 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 \[(1-\pi)^{m^2}\le e^{-\pi m^2}\le2^{-\pi m^2}.\] Linearity of expectation, again counting generators with multiplicity, therefore gives \[\mathbb E[c_\rho(\mathcal C_2)] \le[T(1+rm)^r]^m\,2^{-\pi m^2}.\] To make this at most \(2^{-m}\), it is enough that \[\log_2 T+r\log_2(1+rm)+1\le\pi m.\] The choice of \(m\) makes \(\pi m=2^{4h}\), while the left side is bounded by a quadratic function of \(h\). Indeed, \[1+rm\le(h+1)2^{12h}\le2^{13h}, \qquad 4h+13rh+1\le18h^2 \le18\cdot2^{2h}\le2^{4h}=\pi m.\] Here we used \(r\le h\), \(h+1\le2^h\), and \(h\ge64\). It follows that \[ \mathbb E[c_\rho(\mathcal C_2)] \le2^{(4h+13rh)m-\pi m^2}\le2^{-m}. \tag{5}\] Combining (2), (4), and (5), we obtain \[\mathbb E[c_\rho(\mathcal G)] \le2^{2-2h}+2^{-m}\le3\cdot2^{-h}.\] 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. ◻ Weights for exceptional setsThe next proposition supplies a cover at a fixed fraction of the original density. Its proof combines an orthogonal expansion with a signed measure on arrays of sets. The expansion bounds the total weight, while the signed measure forces a large sum of high powers on every exceptional set. Lemma 3 then converts these two bounds into a cover. Proposition 4. Let \(L=2^{70}\). For every integer \(N\ge1\), every \(q\in(0,1)\), and every \(\mathcal F\subseteq 2^{[N]}\) satisfying \(\mu_q(\mathcal F)\ge1/2\), the family \(E_{32}(\mathcal F)\) is \((q/L)\)-small. Proof. Identify subsets of \([N]\) with their indicator vectors and write \(f=\mathbf 1_{\mathcal F}\). For \(U\subseteq[N]\), define \[ b(U)=(1-q)^{|U|} \sum_{z\in\{0,1\}^{U}}(-1)^{\sum_{i\in U}z_i} \mathbb E[f(z,Y)], \qquad w(U)=b(U)^2, \tag{6}\] 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 3. The global weight bound.We use the standard biased Fourier basis [7], with its normalization made explicit here. Under the product law \(\mu_q\), the functions \[\chi_U(x)=\frac{\prod_{i\in U}(q-x_i)}{[q(1-q)]^{|U|/2}}, \qquad U\subseteq[N],\] 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\}\), \[\mathbb P(X_i=z_i)(q-z_i)=q(1-q)(-1)^{z_i}.\] Summing over the coordinates in \(U\) therefore gives \[\widehat f(U) =[q(1-q)]^{|U|/2} \sum_{z\in\{0,1\}^{U}}(-1)^{\sum_{i\in U}z_i} \mathbb E[f(z,Y)] =\left(\frac{q}{1-q}\right)^{|U|/2}b(U).\] Consequently, Parseval’s identity yields \[ \begin{aligned} \sum_{U\subseteq[N]}q^{|U|}w(U) &=\sum_{U\subseteq[N]}(1-q)^{|U|}\widehat f(U)^2\\ &\le\sum_{U\subseteq[N]}\widehat f(U)^2 =\mathbb E[f(X)^2] =\mu_q(\mathcal F)\le1. \end{aligned} \tag{7}\] 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 \[ \sum_{\varnothing\ne U\subseteq S}w(U)^{16}\ge2^{-32}. \tag{8}\] Consider an array of bits with \(32\) rows and \(N\) columns. For a column \(y\in\{0,1\}^{32}\), let \[P(y)=\prod_{j=1}^{32}q^{y_j}(1-q)^{1-y_j}.\] 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 \[R(y)=P(y)-(1-q)^{32}(-1)^{\sum_{j=1}^{32}y_j}.\] With two rows, this is precisely Li’s signed kernel after multiplying by the Bernoulli masses [6]. Park also notes the extension of Li’s argument to an even number of unions [9]. Here the higher powers obtained from 32 rows are combined with Lemma 3 to obtain a fixed density loss. The signed-operator approach to forbidden configurations and its biased Fourier basis have earlier forms in [4] and [2]. 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 \[\sum_{x\in\{0,1\}^{32\times N}}\nu_S(x) \prod_{j=1}^{32}f(x_j)=0.\] 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 \[(1-q)^{32|U|}\prod_{j=1}^{32} (-1)^{\sum_{i\in U}x_{ji}}.\] 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 (6), because the power \((1-q)^{32|U|}\) distributes as \((1-q)^{|U|}\) to each row. It follows that \[ 0=\sum_{U\subseteq S}(-1)^{|U|}b(U)^{32}. \tag{9}\] All products and sums here are finite. Isolating the empty term and using the triangle inequality gives \[2^{-32}\le b(\varnothing)^{32} \le\sum_{\varnothing\ne U\subseteq S}|b(U)|^{32} =\sum_{\varnothing\ne U\subseteq S}w(U)^{16},\] which proves (8). Constructing the cover.Set \(\rho=q/L\). First include all sets in \[\mathcal G_0= \{U\subseteq[N]:U\ne\varnothing,\ w(U)\ge2^{-64|U|}\}\] as generators. For \(U\in\mathcal G_0\) with \(r=|U|\ge1\), \[\rho^r=q^r2^{-70r} \le2^{-6r}q^r w(U) \le2^{-6}q^r w(U).\] Hence (7) gives \[ c_\rho(\mathcal G_0)\le2^{-6}. \tag{10}\] Partition the remaining nonempty sets of positive weight into families \[\mathcal H_{r,h}= \bigl\{U\subseteq[N]:|U|=r,\ U\notin\mathcal G_0, \quad 2^{-(h+1)}<w(U)\le2^{-h}\bigr\},\] 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 (7), \[|\mathcal H_{r,h}|q^r2^{-(h+1)} <\sum_{U\in\mathcal H_{r,h}}q^r w(U)\le1\] for each occupied bin. In particular, \[|\mathcal H_{r,h}|\rho^r\le2^{h+1}.\] Since \(h\ge64r\ge64\), all the hypotheses of Lemma 3 hold. Choose a cover \(\mathcal G_{r,h}\) of the sets containing at least \(2^{12h}\) members of \(\mathcal H_{r,h}\), with \[c_\rho(\mathcal G_{r,h})\le3\cdot2^{-h}.\] There are only finitely many occupied bins, because the ground set is finite. We may therefore choose these covers simultaneously and form \[\mathcal G=\mathcal G_0\cup\bigcup_{\mathcal H_{r,h}\ne\varnothing} \mathcal G_{r,h}.\] Removing any repeated generators can only decrease its cost. The geometric sum \[ 3\sum_{r\ge1}\sum_{h\ge64r}2^{-h} =\frac{6}{2^{64}-1}<\frac14 \tag{11}\] and (10) imply \[c_\rho(\mathcal G) \le\frac1{64}+\frac{6}{2^{64}-1}<\frac12.\] 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 \[ \begin{aligned} \sum_{\varnothing\ne U\subseteq S}w(U)^{16} &\le\sum_{r\ge1}\sum_{h\ge64r}2^{12h}2^{-16h}\\ &=\frac{16}{15(2^{256}-1)}<2^{-32}. \end{aligned} \tag{12}\] By (8), such an \(S\) cannot belong to \(E_{32}(\mathcal F)\). Thus \(\mathcal G\) is the required cover. ◻ Returning to the original densityWe now remove the factor \(L\) in Proposition 4. The useful coupling makes each row a product sample, while arranging its dependence with the other rows so that their union has a larger prescribed density. Proof of Theorem 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 \[ \mathbb P(R_j\in\mathcal D\text{ for all }1\le j\le L) \ge1-\sum_{j=1}^L\mathbb P(R_j\notin\mathcal D) \ge1-\frac Lk=\frac{31}{32}. \tag{13}\] 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 \[\mathbb P(J_i=0)=1-Lp, \qquad \mathbb P(J_i=j)=p\quad(1\le j\le L).\] 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 \[\mathcal F =\{D_1\cup\cdots\cup D_L:D_1,\ldots,D_L\in\mathcal D\}.\] On the event in (13), the union \(R\) belongs to \(\mathcal F\). Hence \[\mu_q(\mathcal F)=\mathbb P(R\in\mathcal F) \ge\frac{31}{32}\ge\frac12.\] 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 \[E_{32}(\mathcal F)=E_{32L}(\mathcal D)=E_k(\mathcal D).\] Proposition 4 makes this family \((q/L)\)-small. Since \(q/L=p\), this is the required conclusion. Case 2: \(Lp\ge1\). Set \[t=\frac{p-1/L}{1-1/L}\in[0,1).\] 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\), \[\mathbb P(i\in R_j) =\frac1L+\left(1-\frac1L\right)t=p,\] 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 (13), 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\). ◻
|
| ||||||||
|