Single-letterization, computability, and reach of the entropy-coupling bound for the union-closed sets conjecture

The union-closed sets conjecture of Frankl (1979) asks whether every finite union-closed family of sets contains an element belonging to at least half of its members. Gilmer's 2022 information-theoretic method — comparing the entropy of a random set with that of the union of two coupled random sets — first certified a constant frequency bound, soon improved to $(3-\sqrt{5})/2\approx 0.38197$; Lei Yu's dimension-free formulation constrains the coupling by maximal correlation, yielding a single-letter functional $\Gamma(t)$ whose exceedance of $1$ certifies frequency at least $t$, with a computable specialization giving about $0.38234$. Yu explicitly left open: (i) whether the multi-letter quantity $\Gamma_n(t)$, whose limit exists by a super-block argument, admits a single-letter characterization, and whether $\Gamma(t)$ is tight; (ii) a provable support bound on the optimizing distribution that would make $\Gamma(t)$ itself numerically computable; and (iii) how far coupling/entropy methods can be pushed toward the conjectured $1/2$ threshold. In the subsequent literature, the mixture-based subclass was proven by Cambie to be exactly capped at about $0.3823455$, Liu's conditionally i.i.d. couplings improve this to about $0.382709$ only under numerically verified hypotheses, and no single-letterization, computability, or ceiling result for the general framework is known; Frankl's conjecture itself remains open as of mid-2026. The problem — determine the exact dimension-free constant that the entropy-coupling method certifies, and whether the method can reach $1/2$ — is open.

Background

A family $\mathcal{F}$ of subsets of a finite set is union-closed if $A\cup B\in\mathcal{F}$ whenever $A,B\in\mathcal{F}$. Frankl's union-closed sets conjecture (1979) asserts that every finite union-closed family $\mathcal{F}\neq\{\emptyset\}$ contains an element belonging to at least half of the sets of $\mathcal{F}$; it remains one of the most notorious open problems in extremal set theory. Identifying sets with binary strings, a union-closed family corresponds to a set $A\subseteq\Omega^n$, $\Omega=\{0,1\}$, closed under the element-wise OR operation $x^n\vee y^n$. For $X^n$ uniformly distributed on an OR-closed set $A$, write $p_A:=\max_{i\in[n]}P(X_i=1)$ for the largest frequency of an element; the conjecture reads $p_A\ge 1/2$.

In November 2022 Gilmer introduced an information-theoretic attack: take two random members of the family and compare the Shannon entropy $H(X^n\vee Y^n)$ of their union with $H(X^n)$ (the Shannon entropy $H(\cdot)=-\sum_x P(x)\log P(x)$ measures the uncertainty of a random variable). Since $X^n\vee Y^n$ again lies in a union-closed family, $H(X^n\vee Y^n)\le\log|A|=H(X^n)$ must hold for the uniform distribution, so any construction forcing $H(X^n\vee Y^n)>H(X^n)$ under the frequency constraint $P(X_i=1)\le t$ for all $i$ yields $p_A>t$. Gilmer's independent-sample argument gave the first constant bound $p_A\ge 0.01$. Four groups (Sawin; Chase–Lovett; Alweiss–Huang–Sellke; Pebody) pushed the constant to $\frac{3-\sqrt{5}}{2}\approx 0.38197$, the threshold at which the binary entropy function $h(p)=-p\log p-(1-p)\log(1-p)$ satisfies $h(2p-p^2)=h(p)$; Chase–Lovett also proved this constant optimal for an approximate version of the problem in which the family is only required to be nearly union-closed. Sawin then observed that the two samples need not be independent: one may use a coupling, a joint distribution of $(X^n,Y^n)$ whose two marginals are both $P_{X^n}$, and even a symmetric one (invariant under swapping the two coordinates).

Lei Yu's dimension-free formulation governs this coupling through maximal correlation: for a pair of random variables, $\rho_m(X;Y):=\sup\mathrm{Corr}(f(X),g(Y))$ over real functions $f,g$ with nonzero variances. Its decisive property is tensorization: the maximal correlation of a pair of independent products equals that of a single pair, which allows bounds on per-coordinate dependence to persist across the block length. Yu defines a single-letter (dimension-independent) functional — an optimization over distributions on one coordinate —

$\Gamma(t):=\sup_{P_\rho}\ \inf_{P_p:\ \mathbb{E}h(p)>0,\ \mathbb{E}p\le t}\ \frac{\mathbb{E}_\rho\Big[\inf_{P_{pq}\in C_s(P_p):\ \rho_m(p;q)\le\rho}\ \mathbb{E}_{p,q}\,h(\varphi(\rho,p,q))\Big]}{\mathbb{E}h(p)},$

where $P_\rho$ and $P_p$ range over finitely supported distributions on $[0,1]$, $C_s(P_p)$ is the set of symmetric couplings of $P_p$ with itself, and $\varphi(\rho,p,q)=\mathrm{median}\{\max\{p,q,p+q-z_2\},\,1/2,\,\min\{p+q,p+q-z_1\}\}$ with $z_{1,2}=pq\mp\rho\sqrt{p(1-p)q(1-q)}$ is the entropy-maximizing feasible value of the probability that the OR of two $\{0,1\}$-valued variables with means $p,q$ equals $1$, over all couplings whose correlation is at most $\rho$. The companion multi-letter quantity, whose value may depend on the dimension $n$, is

$\Gamma_n(t):=\inf_{P_{X^n}:\ P_{X_i}(1)\le t\ \forall i}\ \sup_{P_{X^nY^n}\in C_s(P_{X^n})}\ \frac{H(X^n\vee Y^n)}{H(X^n)}.$

Yu proves $\Gamma_n(t)\ge\Gamma(t)$, that $\lim_{n\to\infty}\Gamma_n(t)$ exists via a super-block coding argument (a standard blocking device establishing convergence of the dimension-dependent sequence), and the implication $\Gamma(t)>1\Rightarrow p_A\ge t$. Restricting $P_\rho$ to a two-point mixture $(1-\alpha)\delta_0+\alpha\delta_1$ recovers Sawin's suggestion; for that restriction Yu derives a cardinality bound of $4$ on the support of an optimizing coupling $P_{pq}$ (via the Krein–Milman theorem, which states that a compact convex set is the closed convex hull of its extreme points), making the restricted functional computable, and its numerical evaluation certifies $p_A\ge 0.38234$ approximately — slightly above $(3-\sqrt{5})/2$. The general functional $\Gamma(t)$, however, is not yet computable, and the relation between $\Gamma(t)$ and $\lim_{n\to\infty}\Gamma_n(t)$ is unknown.

Problem Statement

With $\Gamma(t)$ and $\Gamma_n(t)$ defined in the Background above (Yu, Entropy 25(5):767, 2023; eqs. (2) and (8)), determine the exact power of the entropy-coupling method for the union-closed sets conjecture. Concretely:

1. (Single-letterization and tightness.) Prove, or disprove, that the limit $\lim_{n\to\infty}\Gamma_n(t)$ — which exists by the super-block coding argument — admits a single-letter (dimension-independent) characterization; in particular, determine whether the single-letter functional $\Gamma(t)$ equals this limit, i.e., whether $\Gamma(t)$ is tight as a lower bound for the multi-letter quantity, or whether there is a strict gap that only higher-dimensional couplings can exploit.

2. (Computability of $\Gamma$.) Prove an upper bound on the cardinality of the support of the optimizing distribution $P_p$ in the outer infimum defining $\Gamma(t)$ — a finite-parametric reduction analogous to the cardinality bound of $4$ on the optimizing coupling $P_{pq}$ known for the two-point-mixture restriction — so that $\Gamma(t)$, and hence $t_{\max}=\sup\{t\in(0,1/2):\Gamma(t)>1\}$, becomes numerically computable; determine $t_{\max}$ exactly or by certified bounds.

3. (Reach toward $1/2$.) Determine how far the coupling/entropy framework can be pushed toward the conjectured threshold $p_A\ge 1/2$: what is the supremum of the values of $t$ that this method can rigorously certify, and can that supremum reach $1/2$? Yu sketches variants of his Theorem 1 in which the maximal-correlation constraint is replaced by any other tensorizing measure of dependence (hypercontractivity constants, i.e., noise-amplification parameters for functions of product measures; strong data-processing-inequality constants; or $\Phi$-ribbons, i.e., common generalizations of such tensorizing quantities) or Shannon entropy by Rényi entropies (the one-parameter family $H_\alpha$ of entropy functionals whose limit at $\alpha\to 1$ is Shannon entropy); whether any such variant extends the reach of the framework is part of the question. For context, the best rigorously certified constant to date is $\approx 0.3823455$, Cambie's exact cap of the two-point-mixture subclass, while Liu's improvement to $\approx 0.382709$ via conditionally i.i.d. couplings remains conditional on numerically verified hypotheses and is not a proof.

These three questions jointly serve one objective: characterizing the exact dimension-free constant that the coupling/entropy method certifies for union-closed families, and deciding whether that constant can be $1/2$ (which would resolve Frankl's conjecture by these techniques).

Each sub-question is a self-contained question that can be attacked independently of the other two. The two requests overlap in one component: the supremum of the values of $t$ that the base maximal-correlation framework can rigorously certify (sub-question 3) is the same quantity as $t_{\max}=\sup\{t\in(0,1/2):\Gamma(t)>1\}$ (sub-question 2), so determining the base-framework $t_{\max}$ discharges that shared component of both; beyond it, sub-question 2 additionally asks for the support bound on the optimizing $P_p$, while sub-question 3 additionally asks whether the tensorizing-measure or Rényi-entropy variants certify a strictly larger supremum.

References

1. Lei Yu, "Dimension-Free Bounds for the Union-Closed Sets Conjecture", Entropy 25(5):767, 2023. DOI: 10.3390/e25050767; arXiv:2212.00658, https://arxiv.org/abs/2212.00658
2. Justin Gilmer, "A constant lower bound for the union-closed sets conjecture", arXiv:2211.09055, 2022, https://arxiv.org/abs/2211.09055
3. Will Sawin, "An improved lower bound for the union-closed set conjecture", arXiv:2211.11504, 2022, https://arxiv.org/abs/2211.11504
4. Zachary Chase, Shachar Lovett, "Approximate union closed conjecture", arXiv:2211.11689, 2022, https://arxiv.org/abs/2211.11689
5. Ryan Alweiss, Brice Huang, Mark Sellke, "Improved Lower Bound for Frankl's Union-Closed Sets Conjecture", arXiv:2211.11731, 2022, https://arxiv.org/abs/2211.11731
6. Luke Pebody, "Extension of a Method of Gilmer", arXiv:2211.13139, 2022, https://arxiv.org/abs/2211.13139
7. Stijn Cambie, "Better bounds for the union-closed sets conjecture using the entropy approach", arXiv:2212.12500, 2022 (v2 2025), https://arxiv.org/abs/2212.12500
8. Jingbo Liu, "Improving the Lower Bound for the Union-closed Sets Conjecture via Conditionally IID Coupling", arXiv:2306.08824, 2023, https://arxiv.org/abs/2306.08824
9. Stijn Cambie, "Progress on the union-closed conjecture and offsprings in winter 2022-2023", arXiv:2306.12351, 2023, https://arxiv.org/abs/2306.12351
10. Wojciech Samotij, "Entropy methods in combinatorics", arXiv:2607.24414, 2026, https://arxiv.org/abs/2607.24414
11. Raffaele Scandone, "A proof of the union-closed sets conjecture", arXiv:2302.03484, 2023 (withdrawn), https://arxiv.org/abs/2302.03484
12. Ravi B. Boppana, "A Useful Inequality for the Binary Entropy Function", arXiv:2301.09664, 2023, https://arxiv.org/abs/2301.09664
13. Tanay Wakhare, "Iterated Entropy Derivatives and Binary Entropy Inequalities", arXiv:2312.14743, 2023, https://arxiv.org/abs/2312.14743
14. Boon Suan Ho, "A generalization of Boppana's entropy inequality", arXiv:2601.19327, 2026, https://arxiv.org/abs/2601.19327