Union Closed Set Conjecture – Variational Estimate

entropyvariational-inequalities

Let $\varphi := \frac{\sqrt{5}-1}{2}$ be the golden ratio, and $H(x):=-x\log_2 x -(1-x) \log_2(1-x)$ be the binary entropy function for a Bernoulli random variable.

Show that for all $\delta > 0$, one can choose sufficiently small $\gamma > 0$, such that if $\mu$ is a probability measure on $[0, 1]$, with
\begin{align*}
\mathbb{E}_{p \sim \mu}(p) \geq \varphi – \gamma
\end{align*}

and
\begin{align*}
\mathbb{E}_{(p, q) \sim \mu \times \mu} H(pq) < \mathbb{E}_{p \sim \mu} H(p),
\end{align*}

then
\begin{align*}
\mu(p \leq \frac12) < \delta.
\end{align*}

This is true when $\gamma$ is allowed to be $0$: in that case, it has been shown that $\mu = \delta_\varphi$.

This comes up as a key estimate in Will Sawin's proposed proof that the lower bound of Frankl's union closed set conjecture can be pushed to $\frac{3 – \sqrt{5}}{2} + \delta$ for some small $\delta > 0$; see also Justin Gilmer's original breakthrough paper.

Update: I believe (could be wrong) following the linearization approach here, it suffices to show the result for $\mu$ of the form $u \delta_0 + v \delta_{1/2} + w \delta_y$, with $y > \varphi – \gamma$ and $u + v + w = 1$. However I cannot get any quantitative estimate on $\gamma$ for a given $\delta$.

Best Answer

Actually I don't see what your trouble is then. Switching to natural $\log$ (which is just scaling of $H$), you have the key inequality $$ \varphi H(x^2)\ge xH(x) $$ (ask Zachary Chase if you want to see a reasonably short and almost computation-free complex analysis proof of it) with equality only for $x=0,\varphi,1$.

Now I want to upgrade it to $$ 2\varphi H(xy)\ge xH(y)+yH(x)\,. $$ Then, taking the expectations, we will get what we want if we take into account that $xy$ is far away from $\varphi^2$ with probability $\delta^2$ (I'm not shooting for the best dependence at this point).

To get this extended version, fix $xy$. Then the RHS is $$ xy\log\frac 1y+yx\log\frac 1x+x(1-y)\log\frac 1{1-y}+y(1-x)\log\frac 1{1-x} $$ The sum of the first two terms is $xy\log \frac 1{xy}$, so it is completely determined by the product $xy$.

Now, expand $$ y(1-x)\log \frac 1{1-x}=y(1-x)\left(x+\tfrac 12 x^2+\tfrac 13 x^3+\tfrac 14 x^4+\dots\right) \\ =yx\left(1-\frac 1{1\cdot 2}x-\frac 1{2\cdot 3}x^2-\dots\right) $$ and similarly for the other term.

Then the sum of the two troublesome terms is $$ xy\left(1-\sum_{k=1}^\infty \frac 1{k(k+1)}(x^k+y^k)\right) $$ but, for fixed product $xy$, the sum $x^k+y^k$ is minimized with $x=y$, so the two-variable inequality immediately follows from the one-variable one.

Edit: the full endgame

The main idea in analyzing the stability in the inequalities is the following. Suppose we have some continuous function $F(x)$ on a compact set (of any nature) that is non-negative and vanishes only at finitely many points $x_1,\dots,x_n$. If we invent any continuous function $G(x)$ ("gain") that also vanishes at these points and such that $G(x)/F(x)$ stays bounded in a small neighborhood of each of the points, then $G/F$ is bounded on the entire compact, i.e., there exists $c>0$ with $F\ge cG$ everywhere.

Now I want to write the chain of inequalities $$ 2\varphi H(XY)\ge 2\sqrt{XY}H(\sqrt{XY})\ge XH(Y)+YH(X)\,. $$
Denoting $Z=\sqrt{XY}$, we can easily analyze $F(Z)=\varphi H(Z^2)-ZH(Z)$ at its only zeroes $0,\varphi,1$. We have $$ F(Z)=(2\varphi-1)Z^2\log\frac 1Z+O(Z^2), \quad Z\to 0; \\ F(Z)=(2\varphi-1)(1-Z)\log\frac 1{1-Z}+O(1-Z), \quad Z\to 1; \\ F(Z)=C(Z-\varphi^2)^2+O(|Z-\varphi|^3), \quad Z\to\varphi $$ (I'm too lazy to compute $C>0$ explicitly, but it is not required: the proof of the key inequality you can obtain from Zachary (or, possibly, even from me if I still have it in the mess on my desk) shows that $\varphi$ is a regular zero of the second order and the function is globally non-negative, so $C>0$ is automatic). Thus, if I invent absolutely anything that is bounded and matches these asymptotic behaviors up to a constant factor, I will have it as a lower bound with some coefficient. So, I just write $$ G(Z)=Z^2(1-Z)(Z-\varphi^2)[\log\tfrac 1Z+\log\tfrac 1{1-Z}] $$ and have $$ 2\varphi H(XY)\ge 2\sqrt{XY}H(\sqrt{XY})+aG(\sqrt{XY}) $$ with some numeric constant $a>0$.

Now passing from one variable to two is even simpler. Note that when we discussed why the diagonal was the worst possible case, we said that $x^k+y^k$ is minimized for fixed $xy$ for $x=y$, i.e., for $k=1$ used the inequality $x+y\ge 2\sqrt{xy}$. Using (for $k=1$ only) the identity $x+y=2\sqrt{xy}+(\sqrt x-\sqrt y)^2$, we arrive at $$ 2\sqrt{XY} H(\sqrt{XY})\ge XH(X)+YH(Y)+\frac 12XY(\sqrt X-\sqrt Y)^2\. $$ Thus, in the whole chain, we can claim the gain $$ \widetilde G(X,Y)=XY(1-\sqrt{XY})(\sqrt{XY}-\varphi)^2[\log \tfrac 1{\sqrt{XY}}+\log \tfrac 1{1-\sqrt{XY}}]+XY(\sqrt X-\sqrt Y)^2. $$

Now fix $\delta>0$ and let $\gamma$ be very small. Then we can write $$ 2\varphi H(XY)\ge XH(Y)+YH(X)+2a\widetilde G(X,Y) $$ with a numeric $a>0$. Taking the expectations, we obtain $$ 2\varphi EH(XY)\ge 2\varphi EH(X)-2\gamma EH(X)+a E\widetilde G(X,Y)\,. $$ Thus, it suffices to show that under your assumptions, $$ E\widetilde G(X,Y)\ge a(\delta)E H(X) $$ with $a(\delta)$ depending on $\delta$, but not on $\gamma$ for $\gamma<\gamma(\delta)$.

Now, your assumptions imply that $P(Y>\varphi+b\delta)>b\delta$ for some explicit numeric $b>0$. Indeed, otherwise we would have $$ EY\le \frac 12\delta+\varphi(1-\delta)+2 b\delta $$ so if $3b<\varphi-\tfrac 12$, we'll have a $b\delta$ drop from $\varphi$ for which $\gamma$ would not be able to compensate.

We have for $Y>\varphi+b\delta$ $$ \widetilde G(X,Y)\ge \begin{cases} {\rm const} X\log\frac 1X, & X<\frac 14 \\ {\rm const}\delta^2, & \frac 14\le X\le \varphi+\frac b2\delta\\ {\rm const}\delta^2 (1-X)\log\frac 1{1-X}, & \varphi+\frac b2\delta\le X\le 1 \end{cases} $$ (in the middle case the first term in $\widetilde G$ is useless and the whole estimate comes from the second term; otherwise the second term is ignored).

So, we have at least ${\rm const} \delta^2 H(X)$ in all cases and $$ E\widetilde G(X,Y)\ge {\rm const} \delta^2 EH(X)P(Y>\varphi+b\delta)\ge {\rm const} \delta^3 EH(X) $$ and we are done.

Some estimates here can be improved, but you requested just a qualitative result, so I didn't bother to chase the best constants and powers: you and Will will easily figure that stuff now once you know that the desired result is possible.

Related Question