Sawin's coupling question for the entropy approach to Frankl's union-closed sets conjecture

Frankl's union-closed sets conjecture (1979) predicts that every nonempty family of sets closed under pairwise unions contains an element belonging to at least half of its members; it remains open. Gilmer's 2022 entropy method, which compares the Shannon entropy of a random set $A$ from the family with that of the union $A\cup B$ of two samples, was sharpened independently by Sawin and three other simultaneous groups to a frequency bound of $\frac{3-\sqrt{5}}{2}\approx 0.38197$, and Sawin posed a coupling question (Question 9 of the cited paper): does every probability measure $\mu$ on subsets of $[n]$ with nonzero entropy and all coordinate marginals below $\tfrac{1}{2}$ admit identically distributed random sets $A,B\sim\mu$, not necessarily independent, with $H(A\cup B)>H(A)$? A positive answer would imply the full Frankl conjecture. The same paper's sketched task of extracting an explicit constant $\delta>0$ beyond $\frac{3-\sqrt{5}}{2}$ has since been resolved (Yu and Cambie obtained $\approx 0.38234$; Liu improved it further via conditionally-IID couplings), while the coupling question itself — the precise surviving open core of the entropy approach — remains open, with no proof and no counterexample in the literature through 2026.

Background

A family $\mathcal{F}$ of sets is called 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 nonempty union-closed family, other than the family consisting of the empty set alone, contains some element of its underlying set that belongs to at least half of the members of $\mathcal{F}$. The conjecture is one of the most notorious open problems in extremal set theory; before 2022 the best known results (Knill 1994; Wójcik 1999) only guaranteed an element in a proportion that decays like $1/\log|\mathcal{F}|$.

Gilmer's breakthrough introduced an information-theoretic method. Let $H(A)$ denote the Shannon entropy of a random variable $A$ taking values in subsets of $[n]$, that is, the entropy $-\sum_S \Pr[A=S]\log\Pr[A=S]$ of its distribution, and let $A,B$ be two independent random sets with a common distribution. The argument studies the entropy of the union: if $A$ is uniform on a union-closed family $\mathcal{F}$ then $H(A)=\log|\mathcal{F}|$, while $A\cup B\in\mathcal{F}$ almost surely forces $H(A\cup B)\le\log|\mathcal{F}|$; so any lower bound of the form $H(A\cup B)>H(A)$ under the assumption that every element $i$ has marginal probability $\Pr[i\in A]<u$ produces an element of frequency at least $u$. Gilmer proved such an inequality for independent samples with $u=0.01$; within days four independent groups (Sawin; Alweiss–Huang–Sellke; Chase–Lovett; Pebody) sharpened the key estimate to yield $u=\frac{3-\sqrt{5}}{2}\approx 0.38197$, and Sawin showed this constant is sharp for the independent-sample method. A coupling of two random sets $A,B$ is the joint distribution of the pair, constrained so that each has the prescribed law $\mu$ (the marginals); independence is one coupling among many, and the marginal $\Pr[i\in A]$ is the probability that $i$ belongs to the random set.

Sawin then sketched that using a specially correlated coupling — a convex combination of the independent coupling and a coordinate-wise max-entropy coupling (the coupling that greedily maximizes the conditional entropy of the union at each coordinate) — yields a bound strictly above $\frac{3-\sqrt{5}}{2}$, while leaving the extraction of an explicit constant as an open task. This task was subsequently completed: Yu and Cambie independently made the sketch rigorous and computable, obtaining $\approx 0.38234$, with Cambie proving that this value is the exact limit of Sawin's convex-combination approach; Liu later improved the constant strictly further using conditionally IID couplings (pairs that are independent conditioned on an auxiliary random variable), reaching $\approx 0.38271$ under numerically verified hypotheses. All of these remain far below the conjectured $\tfrac{1}{2}$.

Two neighboring proposals of Gilmer were refuted early on: Sawin's Proposition 6 (with an independent note by Ellis) shows that controlling the Kullback–Leibler divergence $D(A\cup B\,\|\,A)$ — an information-theoretic measure of how distinguishable the distributions of $A\cup B$ and $A$ are — by itself does not improve the entropy estimate. In contrast, the question that survives untouched is the most flexible version of the coupling idea, posed as Question 9 in the source paper: it allows the solver to choose the coupling of $A$ and $B$ freely, depending on the measure $\mu$. It is known that no fixed restricted coupling class known so far (independent, max-entropy, mixtures, maximal-correlation, conditionally IID) achieves the goal in general, and that standard tensorization tools fail here because the constraint that both marginals equal $\mu$ is essential; the general coupling-existence question is open.

Problem Statement

Sawin's Question 9 (arXiv:2211.11504), posed as the central open question of the entropy approach to Frankl's union-closed sets conjecture: For every $n\ge 1$ and every probability measure $\mu$ on the power set $2^{[n]}$ such that $H(\mu)>0$ (the measure is not a point mass) and every coordinate marginal satisfies $\mu(\{A\subseteq[n]: i\in A\})<\tfrac{1}{2}$ for all $i\in[n]$, do there exist random subsets $A,B$ of $[n]$, each distributed according to $\mu$ (an arbitrary coupling, not necessarily independent), such that

$H(A\cup B)\;>\;H(A)?$

A positive answer (a proof that such a coupling always exists) would imply Frankl's union-closed sets conjecture in full: applied to the uniform measure on a union-closed family in which every element appears in strictly less than half the sets, it would give $H(A\cup B)>H(A)=\log|\mathcal{F}|$, contradicting $A\cup B\in\mathcal{F}$. A negative answer consists of an explicit measure $\mu$, with nonzero entropy and all coordinate marginals strictly below $\tfrac{1}{2}$, such that $H(A\cup B)\le H(A)$ for every coupling of $\mu$ with itself; such a witness would show that the entropy/coupling route cannot prove the full Frankl conjecture. The problem is answered completely by either a rigorous existence proof for all $n$ and $\mu$, or a single verified counterexample measure.

References

1. Will Sawin, "An improved lower bound for the union-closed set conjecture", arXiv:2211.11504 (2022), DOI 10.48550/arXiv.2211.11504, https://arxiv.org/abs/2211.11504
2. Justin Gilmer, "A constant lower bound for the union-closed sets conjecture", arXiv:2211.09055 (2022), DOI 10.48550/arXiv.2211.09055, https://arxiv.org/abs/2211.09055
3. Ryan Alweiss, Brice Huang, Mark Sellke, "Improved Lower Bound for Frankl's Union-Closed Sets Conjecture", Electronic Journal of Combinatorics 31(3), Paper No. 3.35 (2024), DOI 10.37236/12232, https://doi.org/10.37236/12232 (preprint arXiv:2211.11731)
4. Zachary Chase, Shachar Lovett, "Approximate union closed conjecture", arXiv:2211.11689 (2022), DOI 10.48550/arXiv.2211.11689, https://arxiv.org/abs/2211.11689
5. Luke Pebody, "Extension of a Method of Gilmer", arXiv:2211.13139 (2022), DOI 10.48550/arXiv.2211.13139, https://arxiv.org/abs/2211.13139
6. David Ellis, "Note: a counterexample to a conjecture of Gilmer which would imply the union-closed conjecture", arXiv:2211.12401 (2022), DOI 10.48550/arXiv.2211.12401, https://arxiv.org/abs/2211.12401
7. Lei Yu, "Dimension-Free Bounds for the Union-Closed Sets Conjecture", Entropy 25(5), Paper No. 767 (2023), DOI 10.3390/e25050767, https://doi.org/10.3390/e25050767 (preprint arXiv:2212.00658)
8. Stijn Cambie, "Better bounds for the union-closed sets conjecture using the entropy approach", arXiv:2212.12500 (2022), DOI 10.48550/arXiv.2212.12500, https://arxiv.org/abs/2212.12500
9. Stijn Cambie, "Progress on the union-closed conjecture and offsprings in winter 2022-2023", arXiv:2306.12351 (2023), DOI 10.48550/arXiv.2306.12351, https://arxiv.org/abs/2306.12351
10. Jingbo Liu, "Improving the Lower Bound for the Union-closed Sets Conjecture via Conditionally IID Coupling", 2024 58th Annual Conference on Information Sciences and Systems (CISS), pp. 1-6, DOI 10.1109/CISS59072.2024.10480167, https://doi.org/10.1109/CISS59072.2024.10480167 (preprint arXiv:2306.08824)
11. Wojciech Samotij, "Entropy Methods in Combinatorics", Proceedings of the International Congress of Mathematicians 2026, Volume 6, pp. 253-273, DOI 10.1137/25m180874x, https://doi.org/10.1137/25m180874x (preprint arXiv:2607.24414)
12. Raffaele Scandone, "A proof of the union-closed sets conjecture", arXiv:2302.03484 (2023, withdrawn by the author on 2023-02-08), DOI 10.48550/arXiv.2302.03484, https://arxiv.org/abs/2302.03484
13. Ravi B. Boppana, "A Useful Inequality for the Binary Entropy Function", arXiv:2301.09664 (2023), DOI 10.48550/arXiv.2301.09664, https://arxiv.org/abs/2301.09664
14. Tanay Wakhare, "Iterated Entropy Derivatives and Binary Entropy Inequalities", arXiv:2312.14743 (2023), DOI 10.48550/arXiv.2312.14743, https://arxiv.org/abs/2312.14743
15. Boon Suan Ho, "A generalization of Boppana's entropy inequality", arXiv:2601.19327 (2026), DOI 10.48550/arXiv.2601.19327, https://arxiv.org/abs/2601.19327
16. Shagnik Das, Saintan Wu, "Frequent elements in union-closed set families", arXiv:2412.03862 (2024), DOI 10.48550/arXiv.2412.03862, https://arxiv.org/abs/2412.03862
17. Veronica Phan, "Entropy approach for a generalization of Frankl's conjecture", arXiv:2412.18622 (2024), DOI 10.48550/arXiv.2412.18622, https://arxiv.org/abs/2412.18622
18. Masoud Zargar, "The union-closed sets conjecture for non-uniform distributions", arXiv:2305.19338 (2023), DOI 10.48550/arXiv.2305.19338, https://arxiv.org/abs/2305.19338
19. Emanuel Knill, "Graph generated union-closed families of sets", arXiv:math/9409215 (1994), DOI 10.48550/arXiv.math/9409215, https://arxiv.org/abs/math/9409215
20. Piotr Wójcik, "Union-closed families of sets", Discrete Mathematics 199(1-3):173-182 (1999), DOI 10.1016/S0012-365X(98)00208-8, https://doi.org/10.1016/S0012-365X(98)00208-8