# A variational estimate related to the union closed set conjecture

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$$.

• "with μ(p)≥φ−γ " I guess a couple of symbols escaped from the LHS. What were they? Commented Dec 6, 2022 at 0:17
• @fedja By $\mu(p)$ I actually meant $\mathbb{E}_{p \sim \mu} p$. I will update it make it clear. Commented Dec 6, 2022 at 2:25
• Something else is formally wrong: I can always take $\delta=1000$ as written and end up with the empty set, whose elements satisfy whatever I wish and a few more properties. Are you sure all inequalities are in the right direction? Commented Dec 6, 2022 at 2:45
• Or, perhaps, the quantifiers and their order are screwed up. It may be "For every $\delta>0$, there exist $\gamma,\varepsilon>0$ such that..." I like inequalities and will certainly try this one once you make the statement formally correct. Commented Dec 6, 2022 at 2:58
• @fedja Thank you for offering to help for the nth time! I corrected and simplified the conjectured claim. Commented Dec 6, 2022 at 4:24

## 1 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.

• P.S. The actual epsilonics in the end is a bit subtler than I wrote, but still not too difficult. If you have trouble with it, let me know and I'll be happy to spell it out, but in the morning. :-) Commented Dec 6, 2022 at 5:59
• Thanks! I didn't expect the clean formula in Chase and Lovett can yield quantitative improvement. Will try it out based on your outline. Commented Dec 6, 2022 at 6:10
• @JohnJiang To reduce your efforts and make the analysis explicit, let's notice (by looking at the orders of tangencies, etc.) that the gain in the two-variable inequality is at least (as well as at most) a constant multiple of $xy(1-\sqrt{xy})(\sqrt{xy}-\varphi)^2[\log\frac 1{\sqrt{xy}}+\log\frac 1{1-\sqrt{xy}}]+xy(\sqrt x-\sqrt y)^2$. All you need to show is that the expectation of this dominates $EH(X)$ with some positive coefficient $c(\delta)$ independent of $\gamma$ as $\gamma\to 0$. The key is that your conditions imply that $P(Y>\varphi+s)>s$ for some $s=s(\delta)$ for small $\gamma$. Commented Dec 6, 2022 at 6:32
• @JohnJiang OK, I'll add the full endgame to my post :-) Commented Dec 6, 2022 at 12:12
• @JohnJiang Usually it goes like that: you figure out with numeric search what is the best you are going to shoot for (checking that all your other argument parts are tight because there is no point in shooting for the best dependence in the inequality improvement if the rest is done sloppily, so you may want to revise the statement as well before doing anything else). Then, if the answer is nice, you try to match it with some simple argument, which you ultimately present to the public. So, the answer is "maybe" Commented Dec 12, 2022 at 14:38