Dimension-Free Bounds for the Union-Closed Sets Conjecture

Abstract

The union-closed sets conjecture states that, in any nonempty union-closed family $\mathcal{F}$ of subsets of a finite set, there exists an element contained in at least a proportion $1/2$ of the sets of $\mathcal{F}$. Using an information-theoretic method, Gilmer recently showed that there exists an element contained in at least a proportion $0.01$ of the sets of such $\mathcal{F}$. He conjectured that their technique can be pushed to the constant $\frac{3-\sqrt{5}}{2}$ which was subsequently confirmed by several researchers including Sawin. Furthermore, Sawin also showed that Gilmer’s technique can be improved to obtain a bound better than $\frac{3-\sqrt{5}}{2}$ but this new bound was not explicitly given by Sawin. This paper further improves Gilmer’s technique to derive new bounds in the optimization form for the union-closed sets conjecture. These bounds include Sawin’s improvement as a special case. By providing cardinality bounds on auxiliary random variables, we make Sawin’s improvement computable and then evaluate it numerically, which yields a bound approximately $0.38234$, slightly better than $\frac{3-\sqrt{5}}{2}\approx 0.38197$.

1. Introduction

This paper concerns the union-closed sets conjecture which is described in the information-theoretic language as follows. For that purpose, every set $B\subseteq \left[n\right]:=\{1,2,\dots ,n\}$ is uniquely described by an n-length sequence $x^n:=(x_1,x_2,\dots ,x_n)\in {\Omega }^n$ with $\Omega :=\{0,1\}$ such that $x_i=1$ if $i\in B$ and $x_i=0$ otherwise. So, a family $\mathcal{F}$ of subsets of $\left[n\right]$ uniquely corresponds to a subset $A\subseteq {\Omega }^n$. Denote the (element-wise) OR operation for two finite $\Omega$-valued sequences as $x^n\vee y^n:={(x_i\vee y_i)}_{i\in \left[n\right]}$ with $x^n,y^n\in {\Omega }^n$, where ∨ is the OR operation. The family $\mathcal{F}$ is closed under the union operation (i.e., $F\cup G\in \mathcal{F},\forall F,G\in \mathcal{F}$) if and only if the corresponding set $A\subseteq {\Omega }^n$ is closed under the OR operation (i.e., $x^n\vee y^n\in A,\forall x^n,y^n\in A$).

Let $A\subseteq {\Omega }^n$ be closed under the OR operation. Let $X^n:=(X_1,X_2,\dots ,X_n)$ be a random vector uniformly distributed on A and denote $P_{X^n}=\mathrm{Unif}\left(A\right)$ as its distribution (or probability mass function, PMF). We are interested in estimating

$$p_A:=\underset{i\in \left[n\right]}{max}{P}_{X_i}\left(1\right)$$

where $P_{X_i}$ is the distribution of $X_i$ and, hence, $P_{X_i}\left(1\right)$ is the proportion of the sets containing the element i among all sets in $\mathcal{F}$. Frankl made the following conjecture.

Conjecture 1 

(Frankl Union-Closed Sets Conjecture). $p_A\ge 1/2$ for any OR-closed set A.

This conjecture equivalently states that, for any union-closed family $\mathcal{F}$, there exists an element contained in at least a proportion $1/2$ of the sets of $\mathcal{F}$. Since the union-closed conjecture was posed by Peter Frankl in 1979, it has attracted a great deal of research interest; see, e.g., [1,2,3,4,5]. We refer readers to the survey paper [6] for more details. Gilmer [7] made a breakthrough recently, showing that this conjecture holds with constant $0.01$. His method used a clever idea from information theory in which two independent random vectors were constructed. It was conjectured by Gilmer that his method can improve the constant to $\frac{3-\sqrt{5}}{2}$, which is now confirmed by several groups of researchers [8,9,10,11]. This constant is shown to be the best for an approximate version of the union-closed sets problem [9]. Moreover, Sawin [8] further developed Gilmer’s idea by allowing the two random vectors to depend on each other. In fact, the same idea was previously used by the present author in several works [12,13,14]. By this technique, Sawin [8] showed that the constant can be improved to a value that is strictly larger than $\frac{3-\sqrt{5}}{2}$. However, without cardinality bounds on auxiliary random variables, Sawin’s constant is difficult to compute, hence the accurate value of this improved constant is not explicitly given in [8].

The present paper further develops Gilmer’s (or Sawin’s) technique to derive new constants (or bounds) in the optimization form for the union-closed sets conjecture. These bounds include Sawin’s improvement as a special case. By providing cardinality bounds on auxiliary random variables, we make Sawin’s improvement computable and then evaluate it numerically which yields a bound approximately $0.38234$, slightly better than $\frac{3-\sqrt{5}}{2}\approx 0.38197$.

2. Main Results

To state our result, we need to introduce some notations. Since we only consider distributions on finite alphabets, we do not distinguish between the terms “distributions” and “probability mass functions”. For a pair of distributions $(P_X,P_Y)$, a coupling of $(P_X,P_Y)$ is a joint distribution $P_{XY}$ whose marginals are, respectively, $P_X,P_Y$. For a distribution $P_X$ defined on a finite alphabet $\mathcal{X}$, a coupling $P_{X{X}^{\prime }}$ of $(P_X,P_X)$ is called symmetric if $P_{X{X}^{\prime }}(x,y)=P_{X{X}^{\prime }}(y,x)$ for all $x,y\in \mathcal{X}$. Denote ${\mathcal{C}}_{\mathrm{s}}\left(P_X\right)$ as the set of symmetric couplings of $(P_X,P_X)$. Denote ${\delta }_x$ as the Dirac measure with a single atom at x. That is, the PMF of this measure takes the value 1 at x and takes the value 0 at other points.

For a joint distribution $P_{XY}$, the (Pearson) correlation coefficient between $(X,Y)\sim P_{XY}$ is defined by

$${\rho }_{\mathrm{p}}(X;Y):=\left\{\begin{array}{cc}\frac{\mathrm{Cov}(X,Y)}{\sqrt{\mathrm{Var}\left(X\right)\mathrm{Var}\left(Y\right)}},\hfill & \mathrm{Var}\left(X\right)\mathrm{Var}\left(Y\right)>0\hfill \\ 0,\hfill & \mathrm{Var}\left(X\right)\mathrm{Var}\left(Y\right)=0\hfill \end{array}\right..$$

The maximal correlation between $(X,Y)\sim P_{XY}$ is defined by

$$\begin{array}{cc}\hfill {\rho }_{\mathrm{m}}(X;Y)& :=\underset{f,g}{sup}{\rho }_{\mathrm{p}}(f\left(X\right);g\left(Y\right))\hfill \\ \hfill & =\underset{f,g}{sup}\left\{\begin{array}{cc}\frac{\mathrm{Cov}\left(f\right(X),g(Y\left)\right)}{\sqrt{\mathrm{Var}\left(f\right(X\left)\right)\mathrm{Var}\left(g\right(Y\left)\right)}},\hfill & \mathrm{Var}\left(f\right(X\left)\right)\mathrm{Var}\left(g\right(Y\left)\right)>0\hfill \\ 0,\hfill & \mathrm{Var}\left(f\right(X\left)\right)\mathrm{Var}\left(g\right(Y\left)\right)=0\hfill \end{array}\right.,\hfill \end{array}$$

where the supremum is taken over all pairs of real-valued functions $\left(f,g\right)$ such that $\mathrm{Var}\left(f\right(X\left)\right),\mathrm{Var}\left(g\right(Y\left)\right)<\infty$. Note that ${\rho }_{\mathrm{m}}(X;Y)\in [0,1]$ and, moreover, ${\rho }_{\mathrm{m}}(X;Y)=0$ if and only if $X,Y$ are independent. Moreover, ${\rho }_{\mathrm{m}}(X;Y)$ is equal to the second largest singular value of the matrix ${\left[\frac{P_{XY}(x,y)}{\sqrt{P_X\left(x\right)P_Y\left(y\right)}}\right]}_{(x,y)}$; see, e.g., [15]. Clearly, the largest singular value of the matrix ${\left[\frac{P_{XY}(x,y)}{\sqrt{P_X\left(x\right)P_Y\left(y\right)}}\right]}_{(x,y)}$ is equal to 1 with corresponding eigenvectors ${\left(\sqrt{P_X\left(x\right)}\right)}_x$ and ${\left(\sqrt{P_Y\left(y\right)}\right)}_y$.

Denote for $p,q,\rho \in [0,1]$,

$$\begin{array}{cc}\hfill z_1& :=pq-\rho \sqrt{p(1-p)q(1-q)}\hfill \\ \hfill z_2& :=pq+\rho \sqrt{p(1-p)q(1-q)}\hfill \end{array}$$

and

$$\phi (\rho ,p,q):=\mathrm{median}\left\{max\{p,q,p+q-z_2\},1/2,min\{p+q,p+q-z_1\}\right\},$$

(1)

where $\mathrm{median}\left(A\right)$ denotes the median value of elements in a multiset A. We regard the set in (1) as a multiset which means $\mathrm{median}\{a,a,b\}=a$. Denote $h\left(a\right)=-a{log}_{2}a-(1-a){log}_2(1-a)$ for $a\in [0,1]$ as the binary entropy function. Define for $t>0$,

$$\Gamma \left(t\right):=\underset{P_{\rho }}{sup}\underset{P_p:\mathbb{E}h\left(p\right)>0,\mathbb{E}p\le t}{inf}{\mathbb{E}}_{\rho }\left[\underset{P_{pq}\in {\mathcal{C}}_{\mathrm{s}}\left(P_p\right):{\rho }_{\mathrm{m}}(p;q)\le \rho }{inf}\frac{{\mathbb{E}}_{p,q}h\left(\phi (\rho ,p,q)\right)}{\mathbb{E}h\left(p\right)}\right],$$

(2)

where the supremum over $P_{\rho }$ and the infimum over $P_p$ are both taken over all finitely supported probability distributions on $[0,1]$.

Our main results are as follows.

Theorem 1. 

If $\Gamma \left(t\right)>1$ for some $t\in (0,1/2)$, then $p_A\ge t$ for any OR-closed $A\subseteq {\Omega }^n$ (i.e., for any union-closed family $\mathcal{F}$, there exists an element contained in at least a proportion t of the sets of $\mathcal{F}$).

The proof of Theorem 1 is given in Section 2 by using a technique based on coupling and entropy. It is essentially the same as the technique used by Sawin [8]. Prior to Sawin’s work, such a technique was used by the present author in several works; see [12,13,14].

Equivalently, Theorem 1 states that $p_A\ge t_{sup}$ for any OR-closed $A\subseteq {\Omega }^n$, where $t_{sup}:=sup\{t\in (0,1/2):\Gamma \left(t\right)>1\}.$ To compute $\Gamma \left(t\right)$ numerically, it is required to upper bound the cardinality of the support of $P_p$ in the outer infimum in (2) since, otherwise, infinitely many parameters are needed to optimize. This is left to be done in a future work. We next provides a computable bound, which is a lower bound of $\Gamma \left(t\right)$, instead $\Gamma \left(t\right)$ itself.

If we choose $P_{\rho }={\delta }_0$, then Theorem 1 implies Gilmer’s bound in [7] since, for this case, the couplings constructed in the proof of Theorem 1 (given in the next section) turn out to be independent, coinciding with Gilmer’s construction. On the other hand, if we choose $P_{\rho }={\delta }_1$, then the couplings constructed in our proof are arbitrary. In fact, we can make a choice of $P_{\rho }$ better than these two special cases. As suggested by Sawin [8], we can choose $P_{\rho }=(1-\alpha ){\delta }_0+\alpha {\delta }_1$ which in fact leads to an optimization over mixtures of independent couplings and arbitrary couplings. This final choice yields the following bound.

Substituting $\rho =0$ and 1, respectively, into $\phi (\rho ,p,q)$ yields

$$\begin{array}{cc}\phi (0,p,q)\hfill & =p+q-pq,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hfill \end{array}$$

(3)

$$\begin{array}{cc}\hfill \phi (1,p,q)& =\mathrm{median}\left\{max\{p,q\},1/2,p+q\right\},\hfill \end{array}$$

(4)

where, in the evaluation of $\phi (1,p,q),$ the following facts were used: (1)

$$p+q-pq-\sqrt{p(1-p)q(1-q)}\le max\{p,q\}$$

for all $p,q\in [0,1]$; (2) if $p+q\le 1$, then

$$p+q-pq+\sqrt{p(1-p)q(1-q)}\ge p+q,$$

and otherwise,

$$1/2<max\{p,q\}\le p+q-pq+\sqrt{p(1-p)q(1-q)}.$$

By defining

$$\begin{array}{cc}\hfill g(P_{pq},\alpha )& :=(1-\alpha ){\mathbb{E}}_{(p,q)\sim P_p^{\otimes 2}}\left[h(p+q-pq)\right]+\alpha {\mathbb{E}}_{(p,q)\sim P_{pq}}\left[h\left(\phi (1,p,q)\right)\right]\hfill \end{array}$$

and substituting $P_{\rho }=(1-\alpha ){\delta }_0+\alpha {\delta }_1$ into Theorem 1, one obtains the following simpler bound.

Proposition 1. 

For $t\in (0,1/2)$,

$$\Gamma \left(t\right)\ge \widehat{\Gamma }\left(t\right):=\underset{\alpha \in [0,1]}{sup}\underset{\mathrm{symmetric}{P}_{pq}:\mathbb{E}h\left(p\right)>0}{inf}\frac{g(P_{pq},\alpha )}{\mathbb{E}h\left(p\right)},$$

(5)

where the infimum is taken over all distributions $P_{pq}$ of the form $(1-\beta )Q_{a_1,a_2}+\beta Q_{b_1,b_2}$ with

$$0\le a:=\frac{a_1+a_2}{2}\le t<b:=\frac{b_1+b_2}{2}\le 1$$

(6)

and $\beta =0$ or $\beta =\frac{t-a}{b-a}>0$ such that $\mathbb{E}h\left(p\right)>0$. (Note that $\mathbb{E}h\left(p\right)=0$ if and only if $P_{pq}$ is a convex combination of ${\delta }_{(0,0)}$, ${\delta }_{(0,1)}$, ${\delta }_{(1,0)}$, and ${\delta }_{(1,1)}$.) Here,

$$Q_{x,y}:=\frac{1}{2}{\delta }_{(x,y)}+\frac{1}{2}{\delta }_{(y,x)}$$

(7)

with ${\delta }_{(x,y)}$ denoting the Dirac measure at $(x,y)$ (whose PMF takes the value 1 at $(x,y)$ and takes the value 0 at other points).

As a consequence of the two results above, we have the following corollary.

Corollary 1. 

If $\widehat{\Gamma }\left(t\right)>1$ for some $t\in (0,1/2)$, then $p_A\ge t$ for any OR-closed $A\subseteq {\Omega }^n$.

The proof of Corollary 1 is given in Section 3.

The lower bound in (5) without the cardinality bound on the support of $P_{pq}$ was given by Sawin [8], which was used to show $p_A>\frac{3-\sqrt{5}}{2}.$ However, thanks to the cardinality bound, we can numerically compute the best bound on $p_A$ that can be derived using $\widehat{\Gamma }\left(t\right)$. That is, $p_A\ge {\widehat{t}}_{sup}$ for any OR-closed $A\subseteq {\Omega }^n$, where ${\widehat{t}}_{sup}:=sup\{t\in (0,1/2):\widehat{\Gamma }\left(t\right)>1\}.$ Numerical results show that if we set $\alpha =0.035,t=0.38234$, then the optimal $P_{pq}=(1-\beta )Q_{a,a}+\beta Q_{a,1}$ with $a\approx 0.3300622$ and $\beta \approx 0.1560676$ which leads to the lower bound $\widehat{\Gamma }\left(t\right)\ge 1.00000889$. Hence, $p_A\ge 0.38234$ for any OR-closed $A\subseteq {\Omega }^n$. This is slightly better than the previous bound $\frac{3-\sqrt{5}}{2}\approx 0.38197$. The choice of $(\alpha ,t)$ in our evaluation is nearly optimal. Our code can be found on the author’s homepage https://leiyudotscholar.wordpress.com/ (accessed on 1 May 2023.) More decimal places of Sawin’s bound (or equivalently, ${\widehat{t}}_{sup}$) were computed by Cambie in a concurrent work [16], i.e., $0.382345533366702\le {\widehat{t}}_{sup}\le 0.382345533366703$ which is attained by the choice $\alpha \approx 0.03560698136437784$. This more precise evaluation can be also verified using our code above.

3. Proof of Theorem 1

Denote $H\left(X\right)=-{\sum }_x{P}_X\left(x\right)log{P}_X\left(x\right)$ as the Shannon entropy of a random variable $X\sim P_X$. Let $A\subseteq {\Omega }^n$ be closed under the OR operation. We assume $\left|A\right|\ge 2$. This is because Theorem 1 holds obviously for singletons A, since for this case, $p_A=1$. Let $P_{X^n}=\mathrm{Unif}\left(A\right)$. So, $H\left(X^n\right)>0$ and, by the chain rule, $H\left(X^n\right)={\sum }_{i=1}^{n}H\left(X_i\right|X^{i-1})$.

If $P_{X^n{Y}^n}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^n}\right)$, then $Z^n:=X^n\vee Y^n\in A$ a.s. where $(X^n,Y^n)\sim P_{X^n{Y}^n}$. So, we have

$$H\left(Z^n\right)\le log\left|A\right|=H\left(X^n\right).$$

We hence have

$$\underset{P_{X^n{Y}^n}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^n}\right)}{sup}\frac{H\left(Z^n\right)}{H\left(X^n\right)}\le 1.$$

If $p_A\le t$, then $P_{X_i}\left(1\right)\le t,\forall i\in \left[n\right]$. Relaxing $P_{X^n}=\mathrm{Unif}\left(A\right)$ to arbitrary distributions such that $P_{X_i}\left(1\right)\le t$, we obtain ${\Gamma }_n\left(t\right)\le 1$ where

$${\Gamma }_n\left(t\right):=\underset{P_{X^n}:P_{X_i}\left(1\right)\le t,\forall i}{inf}\underset{P_{X^n{Y}^n}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^n}\right)}{sup}\frac{H\left(Z^n\right)}{H\left(X^n\right)}.$$

(8)

In other words, if given t, ${\Gamma }_n\left(t\right)>1$, then, by contradiction, $p_A>t$.

We next show that ${\Gamma }_n\left(t\right)\ge \Gamma \left(t\right)$ which implies Theorem 1. To this end, we need the following lemmas.

For two conditional distributions $P_{X|U},P_{Y|V}$, denote $\mathcal{C}(P_{X|U},P_{Y|V})$ as the set of conditional distributions $Q_{XY|UV}$ such that their marginals satisfy $Q_{X|UV}=P_{X|U},Q_{Y|UV}=P_{Y|V}$. The conditional (Pearson) correlation coefficient of X and Y given U is defined by

$${\rho }_{\mathrm{p}}(X;Y|U)=\left\{\begin{array}{cc}\frac{\mathbb{E}\left[\mathrm{cov}\right(X,Y\left|U\right)]}{\sqrt{\mathbb{E}\left[\mathrm{var}\right(X\left|U\right)]}\sqrt{\mathbb{E}\left[\mathrm{var}\right(Y\left|U\right)]}},\hfill & \mathbb{E}\left[\mathrm{var}\right(X\left|U\right)\left]\mathbb{E}\right[\mathrm{var}\left(Y\right|U\left)\right]>0,\hfill \\ 0,\hfill & \mathbb{E}\left[\mathrm{var}\right(X\left|U\right)\left]\mathbb{E}\right[\mathrm{var}\left(Y\right|U\left)\right]=0.\hfill \end{array}\right.$$

The conditional maximal correlation coefficient of X and Y given U is defined by

$${\rho }_{\mathrm{m}}(X;Y|U)=\underset{f,g}{sup}{\rho }_{\mathrm{p}}(f(X,U);g(Y,U)|U),$$

where the supremum is taken over all real-valued functions $f(x,u),g(y,u)$ such that $\mathbb{E}\left[\mathrm{var}\right(f(X,U)\left|U\right)]$, $\mathbb{E}\left[\mathrm{var}\right(g(Y,U)\left|U\right)]<\infty$. It has been shown in [17] that

$${\rho }_{\mathrm{m}}(X;Y|U)=\underset{u:P_U\left(u\right)>0}{sup}{\rho }_{\mathrm{m}}(X;Y|U=u),$$

where ${\rho }_{\mathrm{m}}(X;Y|U=u)={\rho }_{\mathrm{m}}(X^{\prime };Y^{\prime })$ with $(X^{\prime },Y^{\prime })\sim P_{XY|U=u}$.

Lemma 1 

(Product Construction of Couplings). Lemma 9 in [12], Corollary 3 in [17], and Lemma 6 in [18] For any conditional distributions $P_{X_i|X^{i-1}},P_{Y_i|Y^{i-1}},i\in \left[n\right]$ and any

$$Q_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}\in \mathcal{C}(P_{X_i|X^{i-1}},P_{Y_i|Y^{i-1}}),\forall i\in \left[n\right],$$

it holds that

$$\begin{array}{cc}\hfill \prod _{i=1}^n{Q}_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}& \in \mathcal{C}\left(\prod _{i=1}^n{P}_{X_i|X^{i-1}},\prod _{i=1}^n{P}_{Y_i|Y^{i-1}}\right).\hfill \end{array}$$

(9)

Moreover, for $(X^n,Y^n)\sim {\prod }_{i=1}^n{Q}_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}$, it holds that

$${\rho }_{\mathrm{m}}(X^n;Y^n)=\underset{i\in \left[n\right]}{max}{\rho }_{\mathrm{m}}(X_i;Y_i|X^{i-1},Y^{i-1}).$$

(10)

For a conditional distribution $P_{X|U}$ defined on finite alphabets, a conditional coupling $P_{X{X}^{\prime }|U{U}^{\prime }}$ of $(P_{X|U},P_{X|U})$ is called symmetric if $P_{X{X}^{\prime }|U{U}^{\prime }}(x,y|u,v)=P_{X{X}^{\prime }|U{U}^{\prime }}(y,x|v,u)$ for all $x,y\in \mathcal{X},u,v\in \mathcal{U}$. Denote ${\mathcal{C}}_{\mathrm{s}}\left(P_{X|U}\right)$ as the set of symmetric conditional couplings of $(P_{X|U},P_{X|U})$. Applying the lemma above to symmetric couplings, we have that if couplings $Q_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X_i|X^{i-1}}\right)$ satisfy ${\rho }_{\mathrm{m}}(X_i;Y_i|X^{i-1},Y^{i-1})\le \rho$ for some $\rho >0$, then

$$\begin{array}{cc}\hfill \prod _{i=1}^n{Q}_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}& \in {\mathcal{C}}_{\mathrm{s}}\left(\prod _{i=1}^n{P}_{X_i|X^{i-1}}\right),\hfill \\ \hfill {\rho }_{\mathrm{m}}(X^n;Y^n)& \le \rho ,\hfill \end{array}$$

with $(X^n,Y^n)\sim {\prod }_{i=1}^n{Q}_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}$. We hence have that, for any $\rho \in [0,1]$,

$$\begin{array}{cc}\hfill & \underset{\begin{array}{c}{P}_{X^n{Y}^n}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^n}\right):\\ {\rho }_{\mathrm{m}}(X^n;Y^n)\le \rho \end{array}}{sup}H\left(Z^n\right)\hfill \\ \hfill & \ge \underset{\begin{array}{c}{P}_{X^{n-1}{Y}^{n-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^{n-1}}\right):\\ {\rho }_{\mathrm{m}}(X^{n-1};Y^{n-1})\le \rho \end{array}}{sup}\left(H\left(Z^{n-1}\right)+\underset{\begin{array}{c}{P}_{X_n{Y}_n|X^{n-1}{Y}^{n-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X_n|X^{n-1}}\right):\\ {\rho }_{\mathrm{m}}(X_n;Y_n|X^{n-1},Y^{n-1})\le \rho \end{array}}{sup}H\left(Z_n\right|Z^{n-1})\right)\hfill \\ \hfill & \ge \underset{\begin{array}{c}{P}_{X^{n-1}{Y}^{n-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^{n-1}}\right):\\ {\rho }_{\mathrm{m}}(X^{n-1};Y^{n-1})\le \rho \end{array}}{sup}H\left(Z^{n-1}\right)\hfill \\ \hfill & +\underset{\begin{array}{c}{P}_{X^{n-1}{Y}^{n-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^{n-1}}\right):\\ {\rho }_{\mathrm{m}}(X^{n-1};Y^{n-1})\le \rho \end{array}}{inf}\underset{\begin{array}{c}{P}_{X_n{Y}_n|X^{n-1}{Y}^{n-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X_n|X^{n-1}}\right):\\ {\rho }_{\mathrm{m}}(X_n;Y_n|X^{n-1},Y^{n-1})\le \rho \end{array}}{sup}H\left(Z_n\right|Z^{n-1})\hfill \\ \hfill & \ge \dots \dots \hfill \\ \hfill & \ge \sum _{i=1}^n\underset{\begin{array}{c}{P}_{X^{i-1}{Y}^{i-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^{i-1}}\right):\\ {\rho }_{\mathrm{m}}(X^{i-1};Y^{i-1})\le \rho \end{array}}{inf}\underset{\begin{array}{c}{P}_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X_i|X^{i-1}}\right):\\ {\rho }_{\mathrm{m}}(X_i;Y_i|X^{i-1},Y^{i-1})\le \rho \end{array}}{sup}H\left(Z_i\right|Z^{i-1}),\hfill \end{array}$$

(11)

where the first inequality above follows by Lemma 1 and the chain rule for entropies. In fact, in the derivation above, the i-th distribution $P_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}$ is chosen as a greedy coupling in the sense that it only maximizes the i-th objective function $H\left(Z_i\right|Z^{i-1})$, regardless of other $H\left(Z_j\right|Z^{j-1})$ with $j>i$ (although it indeed affects their values).

By the fact that conditioning reduces entropy, it holds that

$$H\left(Z_i\right|Z^{i-1})\ge H\left(Z_i\right|X^{i-1},Y^{i-1}).$$

Denote

$$\begin{array}{cc}\hfill g_i(P_{X^{i-1}},\rho ):=& \underset{\begin{array}{c}{P}_{X^{i-1}{Y}^{i-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X^{i-1}}\right):\\ {\rho }_{\mathrm{m}}(X^{i-1};Y^{i-1})\le \rho \end{array}}{inf}\underset{\begin{array}{c}{P}_{X_i{Y}_i|X^{i-1}{Y}^{i-1}}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X_i|X^{i-1}}\right):\\ {\rho }_{\mathrm{m}}(X_i;Y_i|X^{i-1},Y^{i-1})\le \rho \end{array}}{sup}H\left(Z_i\right|X^{i-1},Y^{i-1}).\hfill \end{array}$$

(12)

Then, the expression at the right-hand side of (11) is further lower bounded by ${\sum }_{i=1}^n{g}_i(P_{X^{i-1}},\rho )$. Combing this with (8) and (11), and by noting that $\rho \in [0,1]$ is arbitrary, we obtain that

$$\begin{array}{cc}\hfill {\Gamma }_n\left(t\right)& \ge \underset{P_{X^n}:P_{X_i}\left(1\right)\le t,\forall i}{inf}\frac{{sup}_{\rho \in [0,1]}{\sum }_{i=1}^n{g}_i(P_{X^{i-1}},\rho )}{{\sum }_{i=1}^{n}H\left(X_i\right|X^{i-1})}\hfill \\ \hfill & =\underset{P_{X^n}:P_{X_i}\left(1\right)\le t,\forall i}{inf}\frac{{sup}_{P_{\rho }}{\mathbb{E}}_{P_{\rho }}{\sum }_{i=1}^n{g}_i(P_{X^{i-1}},\rho )}{{\sum }_{i=1}^{n}H\left(X_i\right|X^{i-1})}\hfill \\ \hfill & \ge \underset{P_{\rho }}{sup}\underset{P_{X^n}:P_{X_i}\left(1\right)\le t,\forall i}{inf}\frac{{\sum }_{i=1}^n{\mathbb{E}}_{P_{\rho }}{g}_i(P_{X^{i-1}},\rho )}{{\sum }_{i=1}^{n}H\left(X_i\right|X^{i-1})}\hfill \\ \hfill & \ge \underset{P_{\rho }}{sup}\underset{P_{X^n}:P_{X_i}\left(1\right)\le t,\forall i}{inf}\underset{i\in \left[n\right]:H\left(X_i\right|X^{i-1})>0}{min}\frac{{\mathbb{E}}_{P_{\rho }}{g}_i(P_{X^{i-1}},\rho )}{H\left(X_i\right|X^{i-1})}\hfill \\ \hfill & \ge \underset{P_{\rho }}{sup}\underset{P_{X^j}:H\left(X_j\right|X^{j-1})>0,P_{X_j}\left(1\right)\le t}{inf}\frac{{\mathbb{E}}_{P_{\rho }}{g}_j(P_{X^{j-1}},\rho )}{H\left(X_j\right|X^{j-1})},\hfill \end{array}$$

(13)

where

• (13) follows since $\frac{a+b}{c+d}\ge min\{\frac{a}{c},\frac{b}{d}\}$ for $a,b\ge 0,c,d>0$, and $H\left(X_i\right|X^{i-1})=0$ implies $X_i$ is a deterministic function of $X^{i-1}$ and, hence, $g_i(P_{X^{i-1}},\rho )=0$;
• The index j in the last line is the optimal i attaining the minimum in (13).

Denote $X=X_j,Y=Y_j,U=X^{j-1},V=Y^{j-1}$, and $Z=X\vee Y$. Then,

$$\begin{array}{cc}\hfill {\Gamma }_n\left(t\right)& \ge \underset{P_{\rho }}{sup}\underset{P_{UX}:H\left(X\right|U)>0,P_X\left(1\right)\le t}{inf}{\mathbb{E}}_{P_{\rho }}\left[\underset{\begin{array}{c}{P}_{UV}\in {\mathcal{C}}_{\mathrm{s}}\left(P_U\right):\\ {\rho }_{\mathrm{m}}(U;V)\le \rho \end{array}}{inf}\underset{\begin{array}{c}{P}_{XY|UV}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X|U}\right):\\ {\rho }_{\mathrm{m}}(X;Y|U,V)\le \rho \end{array}}{sup}\frac{H\left(Z\right|U,V)}{H\left(X\right|U)}\right].\hfill \end{array}$$

(14)

We next further simplify the lower bound in (14). Denote

$$p=P_{X|U}\left(1\right|U),q=P_{Y|V}\left(1\right|V),r=P_{XY|UV}(1,1|U,V).$$

(15)

So,

$$P_{XY|UV}(·|U,V)=\left[\begin{array}{cc}1+r-p-q& q-r\\ p-r& r\end{array}\right]$$

with

$$max\{0,p+q-1\}\le r\le min\{p,q\}.$$

Note that

$$\begin{array}{cc}\hfill {\rho }_{\mathrm{m}}(X;Y|U,V)& =\underset{u,v:P_{UV}(u,v)>0}{sup}{\rho }_{\mathrm{m}}(X_u;Y_v)\hfill \\ \hfill & =\underset{u,v:P_{UV}(u,v)>0}{sup}\left|{\rho }_{\mathrm{p}}(X_u;Y_v)\right|\hfill \\ \hfill & =\underset{u,v:P_{UV}(u,v)>0}{sup}\frac{\left|r-pq\right|}{\sqrt{p(1-p)q(1-q)}},\hfill \end{array}$$

(16)

where $\left(X_u,Y_v\right)\sim P_{XY|U=u,V=v}$, ${\rho }_{\mathrm{p}}$ denotes the Pearson correlation coefficient and (16) follows since the maximal correlation coefficient between two binary random variables is equal to the absolute value of the Pearson correlation coefficient between them; see, e.g., [19]. So, ${\rho }_{\mathrm{m}}(X;Y|U,V)\le \rho$ is equivalent to $\frac{\left|r-pq\right|}{\sqrt{p(1-p)q(1-q)}}\le \rho$ a.s. and also equivalent to $z_1\le r\le z_2$ a.s.

The inner supremum in (14) can be rewritten as

$$\begin{array}{cc}\hfill & \underset{P_{XY|UV}\in {\mathcal{C}}_{\mathrm{s}}\left(P_{X|U}\right):{\rho }_{\mathrm{m}}(X;Y|U,V)\le \rho }{sup}H\left(Z\right|U,V)\hfill \\ \hfill & ={\mathbb{E}}_{p,q}\underset{max\{0,p+q-1,z_1\}\le r\le min\{p,q,z_2\}}{sup}h(p+q-r).\hfill \end{array}$$

By the fact that h is increasing on $[0,1/2]$ and decreasing on $[1/2,1]$, it holds that the optimal r attaining the supremum in the last line above, denoted by $r^{*}$, is the median of $max\{0,p+q-1,z_1\}$, $p+q-1/2$, and $min\{p,q,z_2\}$, which implies

$$p+q-r^{*}=\phi (\rho ,p,q).$$

Recall the definition of $\phi$ in (1). So, the inner supremum in (14) is equal to $\frac{{\mathbb{E}}_{p,q}h\left(\phi (\rho ,p,q)\right)}{\mathbb{E}h\left(p\right)}$.

We make the following observations. Firstly,

$$\begin{array}{cc}\hfill H\left(X\right|U)& =\mathbb{E}h\left(p\right),\hfill \\ \hfill P_X\left(1\right)& =\mathbb{E}p.\hfill \end{array}$$

Secondly, by the definition of maximal correlation, ${\rho }_{\mathrm{m}}(p;q)\le {\rho }_{\mathrm{m}}(U;V)$ holds (which is known as the data processing inequality) since $p,q$ are, respectively, functions of $U,V$; see (15). Lastly, observe that $P_{UV}$ is symmetric and $p,q$ are obtained from $U,V$ via the same function $P_{X|U}\left(1\right|·)$ (since $P_{X|U}=P_{Y|V}$ holds by the symmetry of $P_{XY|UV}$). Hence, $P_{pq}$ is symmetric as well. Substituting all of these into (14) yields ${\Gamma }_n\left(t\right)\ge \Gamma \left(t\right)$. □

4. Proof of Proposition 1

By choosing $P_{\rho }=(1-\alpha ){\delta }_0+\alpha {\delta }_1$ in (2), we obtain

$$\Gamma \left(t\right)\ge \underset{\alpha \in [0,1]}{sup}\underset{\mathrm{symmetric}{P}_{pq}:\mathbb{E}h\left(p\right)>0,\mathbb{E}p\le t}{inf}\frac{g(P_{pq},\alpha )}{\mathbb{E}h\left(p\right)}.$$

Note that $P_{pq}\mapsto g(P_{pq},\alpha )$ is concave, since, by Lemma 5 in [10]$P_p\mapsto {\mathbb{E}}_{(p,q)\sim P_p^{\otimes 2}}h(p+q-pq)$ is concave, and $P_{pq}\mapsto P_p$ is linear.

Let B be a finite subset of $[0,1]$. Let ${\mathcal{P}}_B$ be the set of symmetric distributions $P_{pq}$ concentrated on $B^2$ such that $\mathbb{E}p\le t$. By the Krein–Milman theorem, ${\mathcal{P}}_B$ is equal to the closed convex hull of its extreme points. These extreme points are of the form $(1-\beta )Q_{a_1,a_2}+\beta Q_{b_1,b_2}$ with $0\le a\le t<b\le 1$ and $\beta =0$ or $\frac{t-a}{b-a}$; recall the definitions $a:=\frac{a_1+a_2}{2},b:=\frac{b_1+b_2}{2}$, and $Q_{x,y}:=\frac{1}{2}{\delta }_{(x,y)}+\frac{1}{2}{\delta }_{(y,x)}$ in (6) and (7). By Carathéodory’s theorem, it is easy to see that the convex hull of these extreme points is closed (in the weak topology or, equivalently, in the relative topology on the probability simplex). So, every $P_{pq}$ supported on a finite set $B^2\subseteq {[0,1]}^2$ such that $\mathbb{E}p\le t$ is a convex combination of the extreme points above, i.e., $P_{pq}={\sum }_{i=1}^k{\gamma }_i{Q}_i$ where $Q_i,i\in \left[k\right]$ are extreme points, and ${\gamma }_i>0$ and ${\sum }_{i=1}^k{\gamma }_i=1$. For this distribution,

$$\begin{array}{cc}\hfill \frac{g(P_{pq},\alpha )}{\mathbb{E}h\left(p\right)}& =\frac{g({\sum }_{i=1}^k{\gamma }_i{Q}_i,\alpha )}{{\sum }_{i=1}^k{\gamma }_i{\mathbb{E}}_{Q_i}h\left(p\right)}\hfill \\ \hfill & \ge \frac{{\sum }_{i=1}^k{\gamma }_{i}g(Q_i,\alpha )}{{\sum }_{i=1}^k{\gamma }_i{\mathbb{E}}_{Q_i}h\left(p\right)}\hfill \\ \hfill & \ge \underset{i:{\mathbb{E}}_{Q_i}h\left(p\right)>0}{min}\frac{g(Q_i,\alpha )}{{\mathbb{E}}_{Q_i}h\left(p\right)}\hfill \end{array}$$

where, in the last line, the constraint ${\mathbb{E}}_{Q_i}h\left(p\right)>0$ is posed since ${\mathbb{E}}_{Q_i}h\left(p\right)=0$ implies $Q_i={\delta }_{(0,0)}$ (note that $t<1/2$) and, hence, $g(Q_i,\alpha )=0$.

Therefore,

$$\Gamma \left(t\right)\ge \underset{\alpha \in [0,1]}{sup}\underset{P_{pq}:\mathbb{E}h\left(p\right)>0}{inf}\frac{g(P_{pq},\alpha )}{\mathbb{E}h\left(p\right)},$$

(17)

where the infimum is taken over distributions $P_{pq}$ of the form $(1-\beta )Q_{a_1,a_2}+\beta Q_{b_1,b_2}$ with $0\le a\le t<b\le 1$ and $\beta =0$ or $\beta =\frac{t-a}{b-a}>0$ such that $\mathbb{E}h\left(p\right)>0$. (Recall the definition of $a,b$ in (6)). □

5. Discussion

The breakthrough made by Gilmer [7] shows the power of information-theoretic techniques in tackling problems in related fields. In fact, the union-closed sets conjecture has a natural interpretation in the information-theoretic (or coding-theoretic) sense. Consider the memoryless OR multi-access channel $(x^n,y^n)\in {\Omega }^{2n}\mapsto x^n\vee y^n\in {\Omega }^n$. We would like to find a nonempty code $A\subseteq {\Omega }^n$ to generate two independent inputs $X^n,Y^n$ with each following $\mathrm{Unif}\left(A\right)$ such that the input constraint $\mathbb{E}\left[X_i\right]\le t,\forall i\in \left[n\right]$ is satisfied and the output $X^n\vee Y^n$ is still in A a.s. The union-closed sets conjecture states that such a code exists if and only if $t\ge 1/2$. Based on this information-theoretic interpretation, it is reasonable to see that the information-theoretic techniques work for this conjecture. It is well-known that information-theoretic techniques usually work very well for problems with “approximate” constraints, e.g., the channel coding problem with the asymptotically vanishing error probability constraint (or the approximate version of the union-closed sets problem introduced in [9]). It is still unclear whether information-theoretic techniques are sufficient to prove sharp bounds for problems with “exact” constraints, e.g., the zero-error coding problem (or the original version of the union-closed sets conjecture).

Furthermore, as an intermediate result, it has been shown that ${\Gamma }_n\left(t\right)>1$ implies $p_A>t$ for any OR-closed $A\subseteq {\Omega }^n$. Here ${\Gamma }_n\left(t\right)$ is given in (8), expressed in the multi-letter form (i.e., the dimension-dependent form). By the super-block coding argument, it is verified that, given $t>0$, ${lim}_{n\to \infty }{\Gamma }_n\left(t\right)$ exists. It is interesting to investigate this limit and prove a single-letter (dimension-independent) expression for it.

For simplicity, in this paper, we only consider the maximal correlation coefficient as the constraint function. In fact, the maximal correlation coefficient used here can be replaced by other functionals. The key property of the maximal correlation coefficient we used in this paper is the “tensorization” property, i.e., (10) (in fact, only “≤” part of (10) was used in our proof). In the literature, there is a class of measures of correlation satisfying this property, e.g., the hypercontractivity constant, strong data processing inequality constant, or, more generally, $\Phi$-ribbons, see [20,21,22]. (Although the tensorization property in the literature is only defined and proven for independent random variables, this property can be extended to the coupling constructed in (9)). Following the same proof steps given in this paper, one can obtain various variants of Theorem 1 with the maximal correlation coefficient replaced by other quantities, as long as these quantities satisfy the tensorization property. Another potential direction is to replace the Shannon entropy with a class of more general quantities, Rényi entropies. However, unfortunately Rényi entropies do not satisfy the chain rule (unlike the Shannon entropy), which leads to a serious difficulty in single-letterizing the corresponding multi-letter bound such as ${\Gamma }_n\left(t\right)$ in (8) (i.e., in making the multi-letter bound dimension-independent).