Quantitative bounds for regular $3$-wise intersecting families

Abstract

Frankston, Kahn and Narayanan proved that every regular increasing 3-wise intersecting family of subsets of $[n]$ has cardinality $o(2^{n})$ using Friedgut’s junta theorem. We give a short quantitative proof using elementary tools from the analysis of Boolean functions and entropy. More precisely, if $\mathcal{A}\subseteq\mathcal{P}_{n}$ is a nonempty 3-wise intersecting family that is both regular and increasing, then

$$\log\frac{2^{n}}{|\mathcal{A}|}\geq\frac{n}{2}\left(\frac{|\mathcal{A}|}{2^{n}-|\mathcal{A}|}\right)^{2},$$

and consequently $|\mathcal{A}|\leq 2^{n}\sqrt{\mathrm{W}(n)/n}$, where $\mathrm{W}$ is the principal Lambert function defined by $\mathrm{W}(x)e^{\mathrm{W}(x)}=x$ for $x\geq 0$. We also give a purely Fourier-analytic proof of the weaker estimate

$$|\mathcal{A}|\leq\frac{2^{n}}{1+n^{1/3}}.$$

1 Introduction

For a positive integer $n$, let $[n]=\{1,2,\ldots,n\}$ and let $\mathcal{P}_{n}$ denote the power-set of $[n]$. For an integer $r\geq 2$, a family $\mathcal{A}\subseteq\mathcal{P}_{n}$ is said to be $r$-wise intersecting if any $r$ of the sets in $\mathcal{A}$ have nonempty intersection. We say that $\mathcal{A}$ is increasing if it is closed under taking supersets, regular if every element of $[n]$ belongs to the same number of members of $\mathcal{A}$, and symmetric if its automorphism group is transitive on $[n]$.

The distinction between $2$-wise and $3$-wise intersection is already apparent in the symmetric setting. When $n$ is odd, the family $\{A\subseteq[n]:|A|>n/2\}$ is a symmetric intersecting family of size $2^{n-1}$, which is the largest possible size of an intersecting subfamily of $\mathcal{P}_{n}$. For $3$-wise intersection, however, Frankl [6] conjectured that every symmetric $3$-wise intersecting family has cardinality $o(2^{n})$. Cameron, Frankl and Kantor [2] had earlier obtained a substantially stronger estimate in the $4$-wise setting. Frankl’s conjecture was eventually proved by Ellis and Narayanan [5], who obtained the quantitative bound $|\mathcal{A}|\leq 2^{n}/n^{c}$ for some universal constant $c>0$ by combining the $p$-biased measure with the Friedgut–Kalai sharp-threshold theorem [8]. A construction of Riordan, recorded in [5], gives symmetric $3$-wise intersecting families satisfying

$$\log_{2}|\mathcal{A}|=n-2\sqrt{n}+o(\sqrt{n})$$

for infinitely many $n$, and therefore they conjectured that every symmetric 3-wise intersecting family $\mathcal{A}\subseteq\mathcal{P}_{n}$ satisfies

$$\log_{2}|\mathcal{A}|\leq n-cn^{\delta}$$

for some universal constants $c,\delta>0$ and one cannot take $\delta>1/2$ in such a result.

Symmetry is considerably stronger than regularity, and Frankl [6] gave a projective-geometric construction of regular $3$-wise intersecting families containing a positive proportion of all subsets of the ground set, so regularity alone cannot imply an $o(2^{n})$ bound. Frankston, Kahn and Narayanan [7] showed that every regular increasing $3$-wise intersecting family has cardinality $o(2^{n})$, using Friedgut’s junta theorem [9] to establish the required threshold behaviour. The quantitative estimate obtained by their argument is, however, very weak, and they raised the corresponding problem for regular increasing families. Analogous questions for vector-intersecting families were considered by Eberhard, Kahn, Narayanan and Spirkl [4], while the more recent theory of global functions has yielded effective quantitative bounds for intersecting families under weaker “smearedness” assumptions [10].

This short note aims to give a direct quantitative proof of the theorem of Frankston, Kahn and Narayanan [7]. Throughout the paper, $\log$ denotes the natural logarithm. Our main result is the following.

Theorem 1.1.

If $\mathcal{A}\subseteq\mathcal{P}_{n}$ is a nonempty 3-wise intersecting family that is both regular and increasing, then

$$\log\frac{2^{n}}{|\mathcal{A}|}\geq\frac{n}{2}\left(\frac{|\mathcal{A}|}{2^{n}-|\mathcal{A}|}\right)^{2}.$$

In particular,

$$|\mathcal{A}|\leq 2^{n}\sqrt{\frac{\mathrm{W}(n)}{n}},$$

where $\mathrm{W}$ is the principal branch of the Lambert $W$-function defined by $\mathrm{W}(x)e^{\mathrm{W}(x)}=x$ for $x\geq 0$.

Since $\mathrm{W}(n)\leq\log n$ for $n\geq 3$, Theorem 1.1 gives

$$\log_{2}|\mathcal{A}|\leq n-\frac{1}{2}\log_{2}n+\frac{1}{2}\log_{2}\log n.$$

Using only basic tools from the analysis of Boolean functions, we can prove the following weaker estimate.

Theorem 1.2.

If $\mathcal{A}\subseteq\mathcal{P}_{n}$ is a 3-wise intersecting family that is both regular and increasing, then

$$|\mathcal{A}|\leq\frac{2^{n}}{1+n^{1/3}}.$$

Both theorems also hold for symmetric $3$-wise intersecting families. Indeed, the upward closure of such a family is $3$-wise intersecting, regular and increasing.

Let us briefly describe the proofs. We identify $\mathcal{P}_{n}$ with $\{0,1\}^{n}$ and write $f=\mathbbm{1}_{\mathcal{A}}$ and $\alpha=\mathbb{E}[f]$. The combinatorial hypothesis is converted into spectral information in two steps: 3-wise intersection implies that $\mathcal{A}$ is sum-free in $\mathbb{F}_{2}^{n}$, and sum-freeness gives the cubic identity

$$\sum_{S\subseteq[n]}\hat{f}(S)^{3}=0.$$

On the other hand, regularity and monotonicity imply that all coordinate influences are equal, while every nonconstant Fourier coefficient is bounded by half of the relevant influence. Combining these facts with Parseval’s identity gives

$${\rm I}[f]\geq\frac{2n\alpha^{2}}{1-\alpha}\geq 2n\alpha^{2}.$$

A second use of Parseval gives ${\rm I}[f]\leq 2\sqrt{n\alpha(1-\alpha)}$, and Theorem 1.2 follows. For Theorem 1.1, the same lower bound on ${\rm I}[f]$ forces a bias in every coordinate of a uniformly random member of $\mathcal{A}$; subadditivity of entropy then turns this common bias into the stated estimate.

Organization. Section 2 collects the elementary facts from the analysis of Boolean functions and entropy. Theorem 1.2 is proved in Section 3, and Therorem 1.1 in Section 4. We conclude in Section 5 with a brief discussion of the limitation of the method.

2 Preliminaries

In this section, we briefly describe the notions and tools we shall require for our arguments. We identify $\mathcal{P}_{n}$ with the discrete cube $\{0,1\}^{n}$, and, when convenient, with the group $\mathbb{F}_{2}^{n}$ under coordinatewise addition modulo $2$.

We consider real-valued functions $f:\{0,1\}^{n}\to\mathbb{R}$, equipped with the inner product $\left\langle f,g\right\rangle=\mathbb{E}_{x}[f(x)g(x)]$. For $S\subseteq[n]$, define the Fourier–Walsh character $\chi_{S}(x):=(-1)^{\sum_{i\in S}x_{i}}$. The family $\{\chi_{S}\}_{S\subseteq[n]}$ is an orthonormal basis of $L^{2}(\{0,1\}^{n})$. The Fourier–Walsh expansion of $f$ is given by $f(x)=\sum_{S\subseteq[n]}\hat{f}(S)\chi_{S}(x)$, where $\hat{f}(S)=\left\langle f,\chi_{S}\right\rangle$. We shall use Parseval’s identity $\sum_{S\subseteq[n]}\hat{f}(S)^{2}=\mathbb{E}[f^{2}]$. We refer the reader to [11] for the standard background on Boolean Fourier analysis.

For $i\in[n]$, let $e_{i}$ denote the $i$th standard basis vector. If $f:\{0,1\}^{n}\to\{0,1\}$, define the $i$th influence and the total influence by

$${\rm Inf}_{i}[f]=\Pr_{x}\bigl(f(x)\neq f(x\oplus e_{i})\bigr),\qquad{\rm I}[f]=\sum_{i=1}^{n}{\rm Inf}_{i}[f].$$

For $x\in\{0,1\}^{[n]\setminus\{i\}}$ and $a\in\{0,1\}$, we write $x^{i=a}$ for the point obtained by setting the $i$th coordinate equal to $a$. Then

$${\rm Inf}_{i}[f]=\mathbb{E}_{x\in\{0,1\}^{[n]\setminus\{i\}}}\left[\left|f(x^{i=1})-f(x^{i=0})\right|\right].$$

We call $f$ increasing or regular when its support has the corresponding property as a family of subsets of $[n]$.

A set $\mathcal{A}\subseteq\mathbb{F}_{2}^{n}$ is sum-free if $x,y\in\mathcal{A}$ implies $x+y\notin\mathcal{A}$.

Lemma 2.1.

If $\mathcal{A}\subseteq\mathbb{F}_{2}^{n}$ is sum-free and $f=\mathbbm{1}_{\mathcal{A}}$, then

$$\sum_{S\subseteq[n]}\hat{f}(S)^{3}=0.$$

Proof.

Sum-freeness gives $f(x)f(y)f(x+y)=0$ for all $x,y\in\mathbb{F}_{2}^{n}$. Hence

$$0=\mathbb{E}_{x,y}[f(x)f(y)f(x+y)].$$

Expanding each $f$ in Fourier expansions and using $\chi_{S}(x+y)=\chi_{S}(x)\chi_{S}(y)$, we obtain

$$0=\sum_{R,S,T\subseteq[n]}\hat{f}(R)\hat{f}(S)\hat{f}(T)\mathbb{E}_{x}[\chi_{R}(x)\chi_{T}(x)]\mathbb{E}_{y}[\chi_{S}(y)\chi_{T}(y)]=\sum_{S\subseteq[n]}\hat{f}(S)^{3},$$

by orthogonality. ∎

Lemma 2.2.

If $f:\{0,1\}^{n}\to\{0,1\}$ is regular and increasing, then ${\rm Inf}_{i}[f]=\frac{{\rm I}[f]}{n}$ for every $i\in[n]$.

Proof.

Let $\mathcal{A}$ be the support of $f$, and for each $i\in[n]$ define

$$\mathcal{A}_{i}^{0}=\{x\subseteq[n]\setminus\{i\}:x\in\mathcal{A}\},\qquad\mathcal{A}_{i}^{1}=\{x\subseteq[n]\setminus\{i\}:x\cup\{i\}\in\mathcal{A}\}.$$

Since $\mathcal{A}$ is increasing, $\mathcal{A}_{i}^{0}\subseteq\mathcal{A}_{i}^{1}$, and therefore

$${\rm Inf}_{i}[f]=\frac{|\mathcal{A}_{i}^{1}\setminus\mathcal{A}_{i}^{0}|}{2^{n-1}}=\frac{2|\mathcal{A}_{i}^{1}|-|\mathcal{A}|}{2^{n-1}}.$$

Regularity says that $|\mathcal{A}_{i}^{1}|$ is independent of $i$. Thus all the influences are equal, and summing them gives the claim. ∎

Lemma 2.3.

Let $f:\{0,1\}^{n}\to\{0,1\}$ be increasing. If $i\in S$, then

$$|\hat{f}(S)|\leq\frac{1}{2}{\rm Inf}_{i}[f].$$

In particular, $\hat{f}(\{i\})=-\frac{1}{2}{\rm Inf}_{i}[f]$.

Proof.

Write $x=(x_{i},z)\in\{0,1\}^{n}$ with $z\in\{0,1\}^{[n]\setminus\{i\}}$. Note that

$$\begin{split}|\hat{f}(S)|&=\left|\mathbb{E}_{x\in\{0,1\}^{n}}[f(x)\chi_{S\setminus\{i\}}(z)(-1)^{x_{i}}]\right|\\ &=\frac{1}{2}\left|\mathbb{E}_{z\in\{0,1\}^{[n]\setminus\{i\}}}\left[\chi_{S\setminus\{i\}}(z)\bigl(f(z^{i=1})-f(z^{i=0})\bigr)\right]\right|\\ &\leq\frac{1}{2}\mathbb{E}_{z\in\{0,1\}^{[n]\setminus\{i\}}}\left[\left|f(z^{i=1})-f(z^{i=0})\right|\right]=\frac{1}{2}{\rm Inf}_{i}[f]\end{split}$$ (2.1)

When $S=\{i\}$, monotonicity gives $f(z^{i=1})-f(z^{i=0})\geq 0$, and therefore $\hat{f}(\{i\})=-\frac{1}{2}{\rm Inf}_{i}[f]$. ∎

We briefly recall the elementary facts about entropy that will be used below; see, for example, [1, Section 14.6]. Let $X$ be a discrete random variable with finite support $\Omega$, and write $p_{X}(x)=\Pr(X=x)$. The Shannon entropy of $X$ is defined by

$$H(X)=-\sum_{x\in\Omega}p_{X}(x)\log p_{X}(x).$$

For random variables $X_{1},\ldots,X_{n}$, we write $H(X_{1},\ldots,X_{n})$ for the entropy of the joint random variable $(X_{1},\ldots,X_{n})$. In particular, if $X$ is uniformly distributed on a finite set $\Omega$, then $H(X)=\log|\Omega|$.

A Bernoulli random variable with parameter $t$ has entropy $h(t)=-t\log t-(1-t)\log(1-t)$ for $0\leq t\leq 1$, where, as usual, $0\log 0=0$. We shall use the standard subadditivity inequality

$$H(X_{1},\ldots,X_{n})\leq\sum_{i=1}^{n}H(X_{i}).$$

The following immediate consequence will be used in the proof of Theorem 1.1.

Lemma 2.4.

Let $Z$ be uniformly distributed on a regular family $\mathcal{A}\subseteq\mathcal{P}_{n}$. Then there exists $\theta\in[0,1]$ such that $\Pr(i\in Z)=\theta$ for every $i\in[n]$, and

$$\log|\mathcal{A}|\leq nh(\theta).$$

Proof.

Identify $Z=(Z_{1},\ldots,Z_{n})$ with $Z_{i}=\mathbbm{1}_{\{i\in Z\}}$. Since $\mathcal{A}$ is regular, each $Z_{i}$ is a Bernoulli random variable with the same parameter $\theta=\Pr(i\in Z)$. Then subadditivity gives

$$\log|\mathcal{A}|=H(Z_{1},\ldots,Z_{n})\leq\sum_{i=1}^{n}H(Z_{i})=nh(\theta),$$

as required. ∎

Lemma 2.5.

For every $0\leq t\leq 1$,

$$\log 2-h(t)\geq 2\left(t-\frac{1}{2}\right)^{2}.$$

Proof.

Set $g(t)=\log 2-h(t)-2(t-\frac{1}{2})^{2}$. We have $g(\frac{1}{2})=g^{\prime}(\frac{1}{2})=0$, while

$$g^{\prime\prime}(t)=\frac{1}{t(1-t)}-4\geq 0.$$

Thus $g$ is convex and has its minimum at $\frac{1}{2}$. ∎

3 Proof of Theorem 1.2

We first give the simple combinatorial observation that allows us to use Lemma 2.1.

Lemma 3.1.

If $\mathcal{A}\subseteq\mathcal{P}_{n}$ is 3-wise intersecting, then $\mathcal{A}$ is sum-free in $\mathbb{F}_{2}^{n}$.

Proof.

For any $x,y\in\mathbb{F}_{2}^{n}$, the three sets corresponding to $x$, $y$ and $x+y$ have empty common intersection. Indeed, if $x_{i}=y_{i}=1$, then $(x+y)_{i}=0$, while otherwise at least one of $x_{i},y_{i}$ is zero. Thus $x,y,x+y$ cannot all belong to a 3-wise intersecting family. ∎

Proof of Theorem 1.2.

Let $f=\mathbbm{1}_{\mathcal{A}}$ and set $\alpha=\mathbb{E}[f]=\frac{|\mathcal{A}|}{2^{n}}$. Since $\mathcal{A}$ is intersecting, $0<\alpha\leq 1/2$.

By Lemmas 3.1 and 2.1,

$$\alpha^{3}=-\sum_{S\neq\varnothing}\hat{f}(S)^{3}.$$

Also, Lemmas 2.2 and 2.3 give

$$|\hat{f}(S)|\leq\frac{{\rm I}[f]}{2n}$$

for every nonempty $S\subseteq[n]$. It follows from Parseval’s identity that

$$\alpha^{3}\leq\sum_{S\neq\varnothing}|\hat{f}(S)|^{3}\leq\frac{{\rm I}[f]}{2n}\sum_{S\neq\varnothing}\hat{f}(S)^{2}=\frac{{\rm I}[f]}{2n}\alpha(1-\alpha).$$

Thus

$${\rm I}[f]\geq\frac{2n\alpha^{2}}{1-\alpha}\geq 2n\alpha^{2}.$$ (3.1)

On the other hand, Lemmas 2.2 and 2.3, followed by Parseval, give

$$\frac{{\rm I}[f]^{2}}{4n}=\sum_{i=1}^{n}\hat{f}(\{i\})^{2}\leq\sum_{S\neq\varnothing}\hat{f}(S)^{2}=\alpha(1-\alpha).$$

Thus

$${\rm I}[f]\leq 2\sqrt{n\alpha(1-\alpha)}.$$ (3.2)

Combining (3.1) and (3.2), we obtain $\alpha\leq\frac{1}{1+n^{1/3}}$. ∎

4 The entropy refinement

Proof of Theorem 1.1.

Let $f=\mathbbm{1}_{\mathcal{A}}$ and set $\alpha=\mathbb{E}[f]=\frac{|\mathcal{A}|}{2^{n}}$. Let $X$ be uniformly distributed on $\{0,1\}^{n}$. Since $\mathcal{A}$ is regular, there is a number $\theta\in[0,1]$ such that, for every $i\in[n]$,

$$\theta=\Pr(X_{i}=1\mid X\in\mathcal{A}).$$

Equivalently, if $Z$ is chosen uniformly from $\mathcal{A}$, then $\Pr(i\in Z)=\theta$ for every $i\in[n]$. Note that

$$\begin{split}\hat{f}(\{i\})&=E\left[f(X)\chi_{\{i\}}(X)\right]=\mathbb{E}[f(X)(1-2X_{i})]=\mathbb{E}[f(X)]-2\mathbb{E}[f(X)X_{i}]\\ &=\alpha-2\Pr(X\in\mathcal{A},\ X_{i}=1)=\alpha-2\Pr(X\in\mathcal{A})\Pr(X_{i}=1\mid X\in\mathcal{A})=\alpha(1-2\theta).\end{split}$$ (4.1)

By Lemmas 2.2 and 2.3,

$${\rm I}[f]=-2n\hat{f}(\{i\})=2n\alpha(2\theta-1).$$

Combining this with (3.1), we obtain

$$2\theta-1\geq\frac{\alpha}{1-\alpha}.$$ (4.2)

By Lemma 2.4,

$$n\log 2+\log\alpha=\log|\mathcal{A}|\leq nh(\theta).$$

Applying Lemma 2.5 and then (4.2), we find that

$$\log\frac{1}{\alpha}\geq 2n\left(\theta-\frac{1}{2}\right)^{2}\geq\frac{n}{2}\left(\frac{\alpha}{1-\alpha}\right)^{2}.$$

This is exactly

$$\log\frac{2^{n}}{|\mathcal{A}|}\geq\frac{n}{2}\left(\frac{|\mathcal{A}|}{2^{n}-|\mathcal{A}|}\right)^{2}.$$

For the explicit bound, we weaken the preceding estimate to $\log(\frac{1}{\alpha})\geq\frac{n\alpha^{2}}{2}$ and set $y=n\alpha^{2}$. Since $\log(\frac{1}{\alpha})=\frac{1}{2}\log\frac{n}{y}$, we have $\log\frac{n}{y}\geq y$, or equivalently $ye^{y}\leq n$. The principal Lambert function is defined by $\mathrm{W}(x)e^{\mathrm{W}(x)}=x$ for $x\geq 0$. For the Lambert function and its basic properties, see [3]. Its monotonicity therefore gives $y\leq\mathrm{W}(n)$, and hence

$$|\mathcal{A}|=2^{n}\alpha\leq 2^{n}\sqrt{\frac{\mathrm{W}(n)}{n}}.$$

∎

5 Concluding remarks

The estimates above are likely to be far from best possible. Ellis and Narayanan [5] conjectured that every symmetric 3-wise intersecting family $\mathcal{A}\subseteq\mathcal{P}_{n}$ satisfies

$$\log_{2}|\mathcal{A}|\leq n-cn^{\delta}$$

for some universal constants $c,\delta>0$, and Frankston, Kahn and Narayanan [7] asked for the same conclusion for regular increasing families.

Let us indicate where the present argument loses information. With the notation used in the proofs, its two key conclusions are

$${\rm I}[f]\geq\frac{2n\alpha^{2}}{1-\alpha}\qquad\text{and}\qquad 2\theta-1\geq\frac{\alpha}{1-\alpha}.$$

Subadditivity of entropy then gives

$$\log\frac{1}{\alpha}\geq n\bigl(\log 2-h(\theta)\bigr).$$

Even if one keeps the exact entropy function, these inequalities yield only

$$\log\frac{1}{\alpha}\geq n\left(\log 2-h\left(\frac{1}{2(1-\alpha)}\right)\right)=\frac{n\alpha^{2}}{2}+O(n\alpha^{3})$$

as $\alpha\to 0$. Thus the method naturally stops at the scale $\alpha\asymp\sqrt{\frac{\log n}{n}}$.

The main loss occurs when the cubic identity is estimated by

$$\alpha^{3}\leq\left(\max_{S\neq\varnothing}|\hat{f}(S)|\right)\sum_{S\neq\varnothing}\hat{f}(S)^{2}\leq\frac{{\rm I}[f]}{2n}\alpha(1-\alpha).$$

This step discards the signs of the Fourier coefficients and the way in which the Fourier mass is distributed across the different levels. Regularity and monotonicity make the coordinate influences equal, but it gives no higher-level information in the form used here. The entropy argument then sees only the common one-coordinate marginal and charges its deviation from $1/2$ quadratically.

Acknowledgments. After the main mathematical results of this note had been obtained, ChatGPT 5.6 pointed out that the principal branch of the Lambert $W$-function could be used to express the bound in Theorem 1.1 in a more explicit and comparable form. We also used ChatGPT 5.6 to assist with polishing the exposition. All other mathematical content in this paper is due to the authors.