Families that intersect in an arithmetic progression

Introduction

For $n \in\mathbb{N}$, write $[n] = \{1,\ldots,n\}$ and identify a subset of $[n]$ with its indicator vector in $\{0,1\}^n$. Let $\mu_n$ be the uniform probability measure on $2^{[n]}$.

Forbidden intersection problems are a classical topic in extremal combinatorics; the Erdős–Ko–Rado theorem [4] is a central example. In 1964, Katona [7], answering one of the questions from [4], proved a non-uniform analogue of the Erdős–Ko–Rado theorem for $k$-intersecting families.

Katona’s bound is attained by the ball $\mathcal{F}=\{F\subseteq[n]:|F|\ge s\}$ when $n+k=2s$, and by a similar family in the other case. Note that if $k$ is fixed and $\mathcal{F}_n$ is an extremal $k$-intersecting family, we have

In 1976, Simonovits and Sós suggested several structured variants of the intersection problem for non-uniform families, in which trivial families are expected to be extremal. One of these variants studies families intersecting in a $k$-term arithmetic progression. A $k$-term arithmetic progression, or $k$-AP, is a set $Q(a,d)=\{a,a+d,\ldots,a+(k-1)d\}$, where $a,d\in\mathbb{N}$, $d\ge1$, and $a+(k-1)d\le n$. Let $\mathcal{P}_k(n)$ be the collection of all such progressions. A family $\mathcal{F}\subseteq2^{[n]}$ is $k$-AP-intersecting if $F_1\cap F_2$ contains a member of $\mathcal{P}_k(n)$ for every $F_1,F_2\in\mathcal{F}$. Set

For fixed $k$, $m_{k,n}$ is nondecreasing in $n$: a family on $[n]$ extends to $[n+1]$ by allowing the new element freely. Since $m_{k,n}\le1$, the limit exists:

Simonovits and Sós conjectured that the largest 3-AP-intersecting family is trivial, that is, consists of all sets that contain a fixed 3-term arithmetic progression. Their conjecture was recorded by Chung, Graham, Frankl and Shearer [2 Conjecture 4].

A natural generalization of this conjecture is $m_k = 2^{-k}$ for all $k \ge3$. Until recently, only the trivial upper bound $m_k \le1/2$ was known. Gillott [5 Theorems 3.3 and 2.1] introduced an adaptive concentration inequality extending Talagrand’s work and obtained

He asked whether $m_k$ decays exponentially in $k$ [5 Question 4.1].

More recently, Keevash [8] proved that $m_3 \le\frac{1}{2} - c$ for an absolute constant $c > 0$.

In this paper, we show that the trivial construction for $k$-AP-intersecting families is optimal up to an absolute multiplicative constant. Actually, we prove a bound for cross $k$-AP-intersecting families. Families $\mathcal{A}, \mathcal{B} \subseteq2^{[n]}$ are cross $k$-AP-intersecting if $A \cap B$ contains a member of $\mathcal{P}_k(n)$ for every $A \in\mathcal{A}$ and $B \in\mathcal{B}$. Set

Our main result is the following theorem.

Since two copies of any $k$-AP-intersecting family $\mathcal{F}$ are cross $k$-AP-intersecting, we have $m_k \le\widetilde{m}_k^{1/2}$. Thus, together with the lower bound provided by a trivial $k$-AP-intersecting family, Theorem 1.3 gives

where the upper bound for $k = 3$ is immediate.

Another well-studied class of structured intersection patterns consists of the edge sets of graphs. Let $H$ be a graph with at least one edge. A family of graphs on the same vertex set is called $H$-intersecting if the common edges of any two members contain a copy of $H$. The most well-known case of the graph-intersection problem is the triangle-intersection problem that asks about the largest $K_3$-intersecting family. In 1986 Chung, Graham, Frankl and Shearer proved that every triangle-intersecting family has density at most $1/4$ using the entropy method [2]. Later Ellis, Filmus and Friedgut used Boolean analysis to prove that the trivial triangle-intersecting family is extremal [3]. A similar result is known for $K_4$-intersecting families [1]. For bipartite graphs $H$, until recently there was no non-trivial bound on $m_H = \sup\{\mu(\mathcal{F}) : \mathcal{F}\text{ is }H\text{-intersecting}\}$. Gillott proved that $m_{C_4} < 1/2$ using the same approach as in his bound on $m_4$ [5]. More recently, Han and Wang [6] proved that $m_{P_4} < 1/2$, where $P_4$ is a path with 4 vertices. Since $m_H = 1/2$ for every graph $H$ containing no $P_4$ or $K_3$, this characterizes the graphs with $m_H = 1/2$.

Let us comment on the proof of Theorem 1.3. After taking up-closures and replacing the second family by its family of complements, we obtain a decreasing family $\mathcal{C}$ such that $A \setminus C$ contains a $k$-AP for every $A \in\mathcal{A}$ and $C \in\mathcal{C}$. Now take a uniform random set $X$ and, conditionally on $X$, choose a random subset $Z=Z(X)\subseteq X$ and put

The product $\mu_n(\mathcal{A})\mu_n(\mathcal{C})$ is bounded by

See Lemma 2.2 below. Bounding (1) is the core of the argument. We shall define $Z$ coordinate by coordinate, so that the first factor shall become the terminal value of a positive supermartingale starting at 1.

The choice of $Z$ involves a trade-off. Adding more coordinates to $Z$ increases $W(X)$ and hence lowers the term $\frac{\mu_n(\mathcal{C})}{W(X)}$, but it also makes a progression inside $Z$ more likely. We carefully choose $Z$, which allows us to reduce $k$-AP bounds to 4-AP bounds: we get a factor $1/4$ for each of the remaining $k-4$ terms.

To construct $Z$, we use a modification of an adaptive exposure procedure introduced by Gillott in the proof of [5 Theorem 1.1]. Conditional on $X$, the elements of $Z$ are chosen independently, but their inclusion probabilities are determined adaptively. We reveal the coordinates of $X$ one by one and choose $\mathbb{P}[i\in Z\mid X]$ as a function of $X_1,\ldots,X_i$. This probability depends on the relative increase in the conditional density of $\mathcal{C}$ produced by deleting coordinate $i$.

In § 2, we reduce the problem to bounding the right-hand side of (1). In § 3, we construct $Z$. In § 4, we analyze the supermartingale associated with this construction and derive the estimates used in the final step. In § 5, we complete the proof of Theorem 1.3. Finally, in § 6, we compare our proof with Gillott’s [5].

Reduction and the random-deletion inequality

We first convert cross-intersection into a one-sided difference condition. Let $\mathcal{A},\mathcal{B}\subseteq2^{[n]}$ be cross $k$-AP-intersecting. We may assume that $\mathcal{A}$ and $\mathcal{B}$ are up-sets, since up-closure preserves the property of being cross $k$-AP-intersecting. Set

Then $\mu_n(\mathcal{C})=\mu_n(\mathcal{B})$ and $\mathcal{C}$ is a down-set. For $C=[n]\setminus B$, we have $A\setminus C=A\cap B$, so $A\setminus C$ contains a $k$-AP for every $A\in\mathcal{A}$ and $C\in\mathcal{C}$. Thus Theorem 1.3 follows from the next statement.

The following inequality explains the rest of the construction. We will guarantee that $W(X)>0$ in the next section.

Proof. Since $Z \subseteq X$, we have $Z=X\setminus(X\setminus Z)$. Therefore, if $X\in\mathcal{A}$ and $X\setminus Z\in\mathcal{C}$, then $Z$ contains a $k$-AP by Theorem 2.1(ii). Fixing $X$ and taking conditional expectation over the auxiliary randomness therefore gives

Since $W(X)>0$, we may multiply by $\mu_n(\mathcal{C})/W(X)$ and get

Averaging over $X$ gives (2).

Adaptive construction of the deletion set

Fix $\mathcal{A},\mathcal{C}$ as in Theorem 2.1. If $\mu_n(\mathcal{C})=0$, the theorem is trivial, so assume $\mu_n(\mathcal{C})>0$. Let $X$ be uniform on $\{0,1\}^{n}$, and let

be the sigma-algebra generated by the first $i$ coordinates. We construct the deletion sets $Z^{(i)}$ and the associated conditional probabilities $W_i$ recursively, starting with

After step $n$, we set $Z:=Z^{(n)}$. Suppose that the first $i-1$ deletion rules have been defined and $W_{i-1}>0$. Compare the two conditional probabilities

Since $X_i$ is a fair bit independent of $\mathcal{F}_{i-1}$, we have

The earlier deletion rules do not depend on $X_i$, and $\mathcal{C}$ is a down-set, so

Define the relative gap

Then $r_i$ is $\mathcal{F}_{i-1}$-measurable and

The deletion rule is guided by how much deleting $i$ increases the conditional probability that the remaining set belongs to $C$. If $X_i=0$, we cannot add $i$ to $Z$, since $Z\subseteq X$. If $X_i=1$, keeping $i$ gives conditional probability $W_{i-1}^{(1)}=(1-r_i)W_{i-1}$, whereas deleting it gives $W_{i-1}^{(0)}=(1+r_i)W_{i-1}$, by (4). Thus $r_i$ measures the effect of deletion relative to $W_{i-1}$. This relative effect is what matters for the reciprocal conditional probability in (2). When $r_i$ is small, the two branches are close, while deletion still makes a $k$-AP in $Z$ more likely. We therefore let the deletion probability increase with $r_i$:

where

For brevity, we denote the probability of adding $\{i\}$ to $Z^{(i-1)}$ by $p_i$:

Let $W_i$ denote the conditional probability that $X\setminus Z^{(i)}$ belongs to $C$:

This expectation averages over the auxiliary choices of $Z$ and the unexposed coordinates $X_{i+1},\ldots,X_n$. The next lemma verifies $W_i>0$, completing the inductive step.

Proof. If $X_i=0$, coordinate $i$ is absent and cannot be deleted. Thus, by (3),

If $X_i=1$, we have

Substituting (5) gives $D(r)=(1+r)^2/(1+3r)$. Since $W_0=\mu_n(C)>0$ and both factors in (6) are positive on $[0,1]$, positivity follows by induction.

To analyze the recursion, we introduce the $\mathcal{F}_i$-measurable inverse weight

In particular, as $W_0=\mu_n(\mathcal{C})$ and $W_n=\mathbb{E}\left(I(X\setminus Z\in\mathcal{C})\mid X\right)=W(X)$, it satisfies

and (6) is equivalent to

In the next section, we show that $(L_i)_{i=0}^n$ is a supermartingale and establish the one-step estimates needed for the proof.

The inverse weight supermartingale

Recall that our goal is to prove

We now establish the estimates on $(L_i)$ needed for this bound. The choice $p(r)=2r/(1+3r)$ is used through three elementary identities.

Proof. All identities follow by direct substitution. For (9), the inequality $r/(1+r)^2\le1/4$ is equivalent to $(1-r)^2\ge0$.

Proof. Conditionally on $\mathcal{F}_{i-1}$, the bit $X_i$ is fair and $r_i$ is fixed. Hence (8) gives

This proves (11) and the supermartingale property.

Since $p_i=0$ on $\{X_i=0\}$ and $p_i=p(r_i)$ on $\{X_i=1\}$,

by (9). Similarly, by (10),

and (13) follows from (11).

Summing the quadratic estimate gives the following bound, used for the weighted 4-AP sum.

Proof. Taking conditional expectations in (13) given $\mathcal{F}_t$ and summing gives

Positivity of $L_n$ gives the second inequality. Taking $t=0$ and using $L_0=1$ proves (14).

:::

Completion of the proof

By Lemma 3.1 and the definition of $W(X)$, $W_n=W(X)>0$; by (7), $L_n=\mu_n(C)/W(X)$. Lemma 2.2 therefore gives

Since probabilities $p_i$ are fixed given $X$, for $S\subseteq[n]$, we define

where $P_{\varnothing}=1$. Note that $P_S$ is $\mathcal{F}_{\max S}$-measurable when $S\ne\varnothing$. Then, by the union bound,

We bound the last sum by the following claim.

As any progression of length $k\geq4$ is uniquely determined by its first four terms, the claim together with (16) implies

The last sum is bounded by the following lemma.

Proof. Write $R=\{a_1<a_2<a_3<a_4\}$. We have

For the first term, $p_{a_1}^2p_{a_2}^2$ is $\mathcal{F}_{a_2}$-measurable, so the supermartingale property gives

Hence

The last inequality uses the elementary fact that a 4-AP is uniquely determined by its first two terms and also by its last two terms; thus any ordered pair $i<j$ occurs at most once in each of the two sums.

Now apply Corollary 4.3 twice. Since $p_i^2$ is $\mathcal{F}_i$-measurable,

where the last inequality is (14). This proves (20).

Now, we are ready to complete the proofs of Theorems 2.1 and 1.3.

Proof of Theorem 2.1 and Theorem 1.3. Combining (15), (16), (19), and (20), we have

Comparison with Gillott's proof

Our approach builds on Gillott's framework [5]. We highlight the differences that give exponential decay with the correct base in place of the polynomial bound.

First, our deletion probabilities depend on the relative increase in the conditional density of $C$, whereas Gillott uses the absolute increase. This modification already suffices for an exponential bound.

Second, in order to bound

Gillott estimates the surviving density and the probability that $Z$ contains a $k$-AP separately. He shows that the latter probability is small for independent sampling with a sufficiently small $\ell_2$-norm of the probability vector [5 Theorem 2.1], and that for most $X$ one can choose such a deletion set with $W_n(X)$ close to $\mu_n(C)$ from below [5 Theorem 1.1]. We instead estimate the weighted probability $L_n(X)\mathbb{E}(\mathbb{I}(Z\text{ contains a }k\text{-AP})\mid X)$ directly, using (12) and (13) to retain the dependence between $L_i$ and $p_i$.

We also remark that the pairing argument in Lemma 5.1 can be viewed as an elementary discrete Brascamp–Lieb-type inequality.

Declaration of generative AI use

We first asked ChatGPT 5.6 to improve the $k$-AP result of [5]. It initially obtained the exponential bound $m_k \le\exp(-\Omega(k))$. After further discussion, during which we provided additional ideas, ChatGPT improved this bound to $m_k \le2^{-k+o(k)}$. Subsequent conversations led to the stronger estimate $\widetilde{m}_k \le O(4^{-k})$. ChatGPT generated the initial draft of the manuscript. The authors verified the arguments, revised and edited the manuscript, and take full responsibility for the final content.