= Solution
Let
$$
c=\frac{3-\sqrt5}{2}=1-\frac1\varphi,
$$
where $\varphi$ is the <golden ratio>. If the <union-closed family> consists of one nonempty set, any element of that set has frequency one, so assume its cardinality exceeds one. Choose independent uniform members $A,B$ and let $X,Y\in\{0,1\}^n$ be their <characteristic vectors of sets>. Then $H(X)=H(Y)=\log|\mathcal A|>0$.
Suppose for a contradiction that every element has frequency $p_i<c$. Put $q_i=1-p_i>1/\varphi$, and let $Z=X\mathbin{\mathrm{OR}}Y$, the <characteristic vector of a set> of $A\cup B$. The <chain rule for information entropy> and <conditioning reduces entropy> give
$$
H(Z)=\sum_iH(Z_i\mid Z_{<i})
\geq\sum_iH(Z_i\mid X_{<i},Y_{<i}),
$$
because $Z_{<i}$ is a <function> of $(X_{<i},Y_{<i})$.
Fix the two prefixes and set
$$
x=\mathbb P(X_i=0\mid X_{<i}),
\qquad
y=\mathbb P(Y_i=0\mid Y_{<i}).
$$
The two conditioned bits are <independent random variables>, and $Z_i=0$ exactly when both are zero. The supplied <binary entropy product inequality> therefore gives
$$
H(Z_i\mid X_{<i},Y_{<i})
=h_2(xy)
\geq\frac\varphi2\bigl(xh_2(y)+yh_2(x)\bigr).
$$
Averaging over the independent prefixes yields
$$
\begin{aligned}
H(Z_i\mid X_{<i},Y_{<i})
&\geq\frac\varphi2\bigl(q_iH(Y_i\mid Y_{<i})+q_iH(X_i\mid X_{<i})\bigr)\\
&>\frac12\bigl(H(Y_i\mid Y_{<i})+H(X_i\mid X_{<i})\bigr)
\end{aligned}
$$
whenever either conditional entropy is positive. Summing and using $H(X)>0$ gives $H(Z)>H(X)$.
But <set union> keeps $A\cup B$ inside the <union-closed family>, so $Z$ is supported on $\mathcal A$. The <maximum entropy distribution on a finite set> gives $H(Z)\leq\log|\mathcal A|=H(X)$, a contradiction. Some element must therefore occur in at least $c|\mathcal A|$ members, proving the <entropy bound for a union-closed family>.
Solved by gpt-5.6-sol high.
Back to article page
