1. Introduction
The study of set families with restricted intersections is fundamental in extremal set theory. A cornerstone result in this area is the Erdős–Ko–Rado theorem [Reference Erdős, Ko and Rado21], which states that for any pair of positive integers n and k with
$n \ge 2k$
, if
$\mathcal{F} \subseteq \binom{[n]}{k}$
is a k-uniform intersecting family—meaning
$A \cap B \ne \varnothing \, (\forall A, B \in \mathcal{F})$
—then
$|\mathcal{F}| \le \binom{n-1}{k-1}$
. This result can be generalised to t-intersecting families, where
$|A \cap B| \ge t \, (\forall A, B \in \mathcal{F})$
. In this case, it holds that
$|\mathcal{F}| \le \binom{n-t}{k-t}$
for sufficiently large n, and the Ahlswede–Khachatrian theorem [Reference Ahlswede and Khachatrian1] provides a complete characterisation of the maximum size of a t-intersecting family
$\mathcal{F}$
for every n, k and t.
Denote by
$A \bigtriangleup B$
the symmetric difference between A and B, i.e.
$(A \setminus B) \cup (B \setminus A)$
, and refer to
$|A \bigtriangleup B|$
as the distance between them. By replacing the intersection restriction “
$|A \cap B| \ge t$
” with the distance restriction “
$|A \bigtriangleup B| \ge t$
”, we naturally arrive at a problem which is central to coding theory. Intensive research efforts have been dedicated to bounding the size of set families under various distance constraints, including Singleton bound [Reference Singleton48], Plotkin bound [Reference Plotkin45], Hamming bound, Elias–Bassalygo bound [Reference Bassalygo9] and Gilbert–Varshamov bound [Reference Gilbert26, Reference Jiang and Vardy30, Reference Varshamov50]. A comprehensive overview of these developments and their significance is available in the standard reference [Reference van Lint49].
A closely related problem, originally proposed by Erdős [Reference Erdős20], considers families
$\mathcal{F} \subseteq 2^{[n]}$
with a forbidden intersection size
$|A \cap B| \ne \ell \, (\forall A, B \in \mathcal{F})$
. Erdős conjectured that, with an offer of $250 for a solution, if the ratio
${\ell}/{n}$
lies between
$\bigl( \varepsilon, {1}/{2} - \varepsilon \bigr)$
, then the family size
$|\mathcal{F}|$
is exponentially smaller than
$2^n$
. This conjecture was first solved by Frankl and Rödl [Reference Frankl and Rödl23]. Keevash and Long [Reference Keevash and Long34] later provided an alternative proof and gave a restricted distance result: if
${d}/{n} \in (\varepsilon, 1-\varepsilon)$
and
$\mathcal{F} \subseteq 2^{[n]}$
is a family with
$|A \bigtriangleup B| \ne d \, (\forall A, B \in \mathcal{F})$
, then
$|\mathcal{F}| \le 2^{(1-\delta)n}$
. We also direct readers to [Reference Kupavskii, Sagdeev and Zakharov37].
While research on restricted intersections has found substantial applications in areas such as Ramsey theory and discrete geometry (see, e.g., [Reference Frankl and Tokushige24, chapter 22]), comparatively little attention has been devoted to the restricted-distance families. Motivated by this gap, in this paper we study set families with restricted distances. For any distance set D, our objective is to investigate
$f_D(n)$
, the largest possible size of a D-distance family on [n].
1·1. Generalising Kleitman’s isodiametric inequality
Among all smooth convex bodies of fixed diameter in
$\mathbb{R}^n$
, the classical Euclidean isodiametric inequality (see [Reference Evans and Gariepy22]) asserts that the ball attains the maximum volume. In the discrete setting, solving a conjecture of Erdős, Kleitman [Reference Kleitman35] established an isodiametric result which states that
\begin{align*}f_D(n) = \begin{cases} \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{t} \qquad &\text{if $D = [2t]$}, \\ 2\Bigl( \binom{n-1}{0} + \binom{n-1}{1} + \cdots + \binom{n-1}{t} \Bigr) \qquad &\text{if $D = [2t+1]$}.\end{cases}\end{align*}
The bounds above are optimal, as witnessed by Hamming balls of appropriate radius.
Kleitman’s original proof relies on sophisticated set operations. Recently, Huang, Klurman and Pohoata [Reference Huang, Klurman and Pohoata29] discovered a smart linear algebraic proof of Kleitman’s result. They also applied their technique to general intervals as distance sets and established that
\begin{align*}\bigl( 1 + o(1) \bigr) \cdot \frac{1}{\tbinom{t}{s}} \cdot \binom{n}{t-s} \le f_{\{2s+1, 2s+2, \dots, 2t\}}(n) \le \bigl( 1 + o(1) \bigr) \cdot \binom{n}{t-s};\end{align*}
They conjectured that the lower bound gives the correct asymptotics.
We study the same problem for even more general distance sets that are arithmetic progressions. An integer arithmetic progression is homogeneous if its common difference divides its first term, and non-homogeneous otherwise. Denote by
$D_{\operatorname{even}} {\stackrel{\text{def}}{\,=\,}} \{d \in D \colon \textit{d}\ \text{is even}\}$
the set of all even integers in D.
Theorem 1·1. Let d, s, t be positive integers with
$1 \le s \le t$
and
$D = \bigl\{ sd, (s+1)d, \dots, td \bigr\}$
be a homogeneous arithmetic progression. As
$n \to \infty$
, the following hold:
-
(i) if d is even, then
\begin{align*} f_D(n) = \bigl(1 + o(1)\bigr) \cdot \frac{1}{\binom{t}{|D_{\operatorname{even}}|}} \cdot \binom{2n/d}{|D_{\operatorname{even}}|} = \bigl(1 + o(1)\bigr) \cdot \frac{1}{\binom{t}{t-s+1}} \cdot \binom{2n/d}{t-s+1}; \end{align*}
-
(ii) if d is odd, then
where
\begin{align*} f_D(n) &= \bigl(1 + o(1)\bigr) \cdot \frac{c}{\binom{\lfloor t/2 \rfloor}{|D_{\operatorname{even}}|}} \cdot \binom{n/d}{|D_{\operatorname{even}}|} \\ &= \bigl(1 + o(1)\bigr) \cdot \frac{c}{\binom{\lfloor t/2 \rfloor}{\lfloor t/2 \rfloor - \lceil s/2 \rceil + 1}} \cdot \binom{n/d}{\lfloor t/2 \rfloor - \lceil s/2 \rceil + 1}, \end{align*}
$c = 1$
if st is even and
$c = 2$
if st is odd.
Theorem 1·1 provides asymptotically sharp bounds on
$f_D(n)$
for every homogeneous arithmetic progression distance set D with arbitrary common differences, which greatly generalises previous results on interval distance sets. In particular, by setting
$d_{1.1} {\stackrel{\text{def}}{\,=\,}} 1, \, s_{1.1} {\stackrel{\text{def}}{\,=\,}} 2s + 1$
, and
$t_{1.1} {\stackrel{\text{def}}{\,=\,}} 2t$
, we confirm the above Huang–Klurman–Pohoata conjecture that
$f_{\{2s+1, \dots, 2t\}}(n)=\bigl( 1 + o(1) \bigr) \cdot {1}/{\tbinom{t}{s}} \cdot \tbinom{n}{t-s}$
.
Somewhat surprisingly, the non-homogeneous arithmetic progressions exhibit a completely different behaviour. In fact, we prove that
$f_D(n)$
grows only linearly in this case.
Theorem 1·2. Given
$n, d, s, t, a \in \mathbb{N}_+$
with
$1 \le s \le t$
and
$1 \le a \lt d$
. For any non-homogeneous arithmetic progression
$D = \bigl\{ sd+a, (s+1)d+a, \dots, td+a \bigr\}$
, the following hold:
-
(i) if
$D_{\operatorname{even}} = \varnothing$
, then
$f_D(n) = 2$
when
$n \ge \min(D)$
, and
$f_D(n) = 1$
otherwise; -
(ii) if
$D_{\operatorname{even}} \ne \varnothing$
, then
$\bigl\lfloor {2n}/{\min(D_{\operatorname{even}})} \bigr\rfloor \le f_D(n) \le n + 2$
.
Our approach differs from both the classical combinatorial shifting in [Reference Kleitman35] and the linear algebraic method in [Reference Huang, Klurman and Pohoata29]. For upper bounds, the main idea is to convert the restricted distance problems to restricted intersection problems. In Theorem 1·1, given a family
$\mathcal{F}$
with prescribed distances, the key is to identify within
$\mathcal{F}$
a subfamily
$\mathcal{F}'$
which constitutes the majority of our family
$\mathcal{F}$
(Claim 3·6)and is located on at most two slices of the hypercube (Claim 3·7).The difficult case is when the distance set
$D = \bigl\{ sd, (s+1)d, \dots, td \bigr\}$
is an arithmetic progression with odd dt and even s. To obtain the correct asymptotics for this case, we have to show that the two slices of
$\mathcal{F}'$
cannot be both large at the same time. To this end, we show that between the two slices of
$\mathcal{F}'$
, there is a restricted (cross) intersection pattern and we need to analyse the structure of the common intersection of each slice. In Theorem 1·2, we apply a modular restricted intersection result. It is worth noting that the lower bound constructions towards Theorem 1·1 involve additional difficulty. Inspired by [Reference Huang, Klurman and Pohoata29], we employ the classical Rödl nibble method. When d, s, t are all odd, we have to build up a “double almost design” to achieve an additional factor 2.
1·2. Bounding the size of binary t-codes
Our method is versatile, and it applies to the study of binary t-codes as well. We begin with some terminologies. Let
$\mathcal{M}$
be a metric space endowed with distance function
$\textrm{dist}_{\mathcal{M}}$
. For finite
$X \subseteq \mathcal{M}$
, denote by
$D(X) {\stackrel{\text{def}}{\,=\,}} \bigl\{\textrm{dist}_\mathcal{M}(x, y) \colon x, y \in X, \, x \ne y\bigr\}$
the distance set of X. For fixed D, we define
\begin{align*}A(\mathcal{M}, D)\ {\stackrel{{def}}{=}} \max \bigl\{ |X| \,:\, X \subseteq \mathcal{M}\, \text{such that} \quad D(X) = D \bigr\}.\end{align*}
Following the terminology of coding theory, we call X a t-code if
$|D(X)| = t$
. Denote the maximum cardinality of a t-code as
$A(\mathcal{M}, t)\ {\stackrel{\text{def}}{\,=\,}} \max \bigl\{ A(\mathcal{M}, D) \,:\, |D| = t \bigr\}$
.
It is a fundamental challenge to establish good upper bounds on
$A(\mathcal{M}, t)$
. Historically, Einhorn and Schoenberg [Reference Einhorn and Schoenberg18, Reference Einhorn and Schoenberg19] initiated the study of t-codes in Euclidean space
$\mathcal{M} = \mathbb{R}^n$
. As a classical application of the polynomial method, Larman, Rogers, and Seidel [Reference Larman, Rogers and Seidel38] (later slightly improved by Blokhuis [Reference Blokhuis11]) deduced that
${n(n+1)}/{2} \le A(\mathbb{R}^n, 2) \le {(n+1)(n+2)}/{2}$
. The same problem for Euclidean sphere
$\mathcal{M} = \mathbb{S}^{n-1} \subseteq \mathbb{R}^n$
has also been intensively studied. Delsarte, Goethals, and Seidel [Reference Delsarte, Goethals and Seidel16] established
${n(n+1)}/{2} \le A(\mathbb{S}^{n-1}, 2) \le {n(n+3)}/{2}$
. Related results and improvements can be found in a large series of papers [Reference Barg and Musin7, Reference Barg and Yu8, Reference Glazyrin and Yu27, Reference Jiang, Tidor, Yao, Zhang and Zhao31, Reference Liu and Yu39–Reference Nozaki43, Reference Yu52].
We focus on such a problem concerning Hamming cubes. Let
$\mathcal{H}_n$
be the set of binary strings
$\mathbb{F}_2^n$
endowed with the Hamming distance. (For any
$\boldsymbol{x}, \boldsymbol{y} \in \mathbb{F}_2^n$
, their Hamming distance
$\textrm{dist}_{\mathcal{H}_n}(\boldsymbol{x}, \boldsymbol{y})$
is the number of bits at which
$\boldsymbol{x}$
differs from
$\mathbf{y}$
.) The study of binary codes has long been central to coding theory. Two-distance sets in
$\mathcal{H}_n$
, binary 2-codes, have received considerable attention as they connect to finite geometry. See [Reference Calderbank and Kantor12] for an early survey and [Reference Shi, Honold, Solé, Qiu, Wu and Sepasdar47] for recent work. Due to the extensive interest on t-codes in
$\mathbb{R}^n$
and
$\mathbb{S}^{n-1}$
, it is natural to bound
$A(\mathcal{H}_n, t)$
. Earliest such results date back to the influential work of Delsarte [Reference Delsarte15] in 1973, where he established
$A(\mathcal{H}_n, t) \le \sum_{i = 0}^{t} \binom{n}{i}$
. Most such results are obtained by either the polynomial method [Reference Bannai, Bannai and Stanton5, Reference Blokhuis10] or the linear programming method [Reference Delsarte15, Reference Delsarte, Goethals and Seidel16], which reduce the problem to the study of spherical t-codes in
$\mathbb{R}^n$
. A folklore conjecture, communicated to us by Yu [Reference Yu51], predicts that the maximum value is achieved by the t-set
$\{2,4,\ldots, 2t\}$
.
Conjecture 1·3 (Folklore). For every sufficiently large n (with respect to t), we have
\begin{align*} A(\mathcal{H}_n, t) = A \bigl( \mathcal{H}_n, \{2, 4, \dots, 2t\} \bigr) = \begin{cases} \binom{n}{0} + \binom{n}{2} + \dots + \binom{n}{t-2} + \binom{n}{t} \qquad & \text{if}\, \textit{t}\ \text{is even}, \\ \binom{n}{1} + \binom{n}{3} + \dots + \binom{n}{t-2} + \binom{n}{t} \qquad &\text{if}\, \textit{t}\ \text{is odd}. \end{cases} \end{align*}
Towards this folklore conjecture, Nozaki and Shinohara [Reference Nozaki and Shinohara44] refined the result of Delsarte [Reference Delsarte15] to
$A(\mathcal{H}_n, t) \le \sum_{i:c_i \gt 0} \binom{n}{i}$
, where
$c_i$
are the coefficients defined by a polynomial related to D in terms of the Krawtchouk polynomial basis. Barg and Musin [Reference Barg and Musin7] further established an explicit formula
$A(\mathcal{H}_n, t) \le \binom{n}{t} + \sum_{i = 0}^{t-2} \binom{n}{i}$
under the condition
$\sum_{d\in D}d \le {tn}/{2}$
. For small values of t, partial results were proved in [Reference Barg and Musin7] for
$t = 2, 3, 4$
. Later, the
$t = 2$
case was resolved by Barg et al. [Reference Barg, Glazyrin, Kao, Lai, Tseng and Yu6].
Our next result establishes
$A(\mathcal{H}_n, D) \le A \bigl( \mathcal{H}_n, \{2, 4, \dots, 2t\} \bigr)$
for any fixed D and every sufficiently large n, which makes significant progress towards the first equality in Conjecture 1·3. We shall also prove that the second equality holds in Conjecture 1·3.
Theorem 1·4. Let
$D \subseteq \mathbb{N}_+$
be a t-set. If
$D \ne \{2, 4, \dots, 2t\}$
, then as
$n \to \infty$
we have
\begin{align*} A(\mathcal{H}_n, D) \le \Bigl(\frac{t}{t+1}+o(1)\Bigr) \cdot \binom{n}{t}. \end{align*}
When
$n \ge 2t + 2$
, we have
\begin{align*} A \bigl( \mathcal{H}_n, \{2, 4, \dots, 2t\} \bigr) = \begin{cases} \binom{n}{0} + \binom{n}{2} + \dots + \binom{n}{t-2} + \binom{n}{t} \qquad &\text{if}\ \textit{t}\ \text{is even}, \\ \binom{n}{1} + \binom{n}{3} + \dots + \binom{n}{t-2} + \binom{n}{t} \qquad &\text{if}\ \textit{t}\ \text{is odd}. \end{cases} \end{align*}
We remark that the bound
$n \ge 2t + 2$
above is optimal. Indeed, when
$n \le 2t + 1$
, the behaviour changes into
$A \bigl( \mathcal{H}_n, \{2, 4, \dots, 2t\} \bigr) = 2^{n-1}$
. Here the lower bound is witnessed by the collection of all binary strings with odd (or even) numbers of 1-s, and the upper bound follows from the observation that
$\textrm{dist}_{\mathcal{H}_n}(\boldsymbol{x}, \boldsymbol{y})$
is odd when the number of 1-s in
$\boldsymbol{x}$
and
$\mathbf{y}$
are of opposite parities.
Theorem 1·4 can be viewed as a stability result, for it infers that the distance set
$\{2, 4, \dots, 2t\}$
is the unique maximiser, showing that
$A(\mathcal{H}_n, D)$
is substantially smaller than
$A \bigl( \mathcal{H}_n, \{2, 4, \dots, 2t\} \bigr)$
for any other fixed t-set D. In contrast, due to the leading term
$\binom{n}{t}$
, the previous bounds could not perform well when D differs from
$\{2, 4, \dots, 2t\}$
.
Paper organisation. We first prove Theorem 1·1. The lower bounds are given in Section 2 and the upper bounds are deduced in Section 3. We then prove Theorem 1·2 in Section 4. In Section 4, we prove Theorem 1·4. Finally, we include some further discussions and open problems in Section 6.
2. Proof of the lower bounds in Theorem 1·1
In this section, we prove the lower bounds in Theorem 1·1. Depending on the parity of dst, we divide the constructions for the lower bounds into two cases.
Theorem 2·1. Suppose d, s, t are positive integers with
$1 \le s \le t$
. Let
$D = \bigl\{ sd, (s+1)$
$d, \dots, td \bigr\}$
be a homogeneous arithmetic progression. The following hold for sufficiently large n.
-
(i) if dst is even, then there exists a D-distance set family
$\mathcal{F} \subseteq 2^{[n]}$
of size
\begin{align*} |\mathcal{F}| = \begin{cases} \bigl(1 - o(1)\bigr) \cdot \dfrac{\binom{2n/d}{t-s+1}}{\binom{t}{t-s+1}} \qquad &\text{when}\ \textit{d}\ \text{is even}, \\[10pt] \bigl(1 - o(1)\bigr) \cdot \dfrac{\binom{n/d}{\lfloor t/2 \rfloor - \lceil s/2 \rceil + 1}}{\binom{\lfloor t/2 \rfloor}{\lfloor t/2 \rfloor - \lceil s/2 \rceil + 1}} \qquad &\text{when}\ \textit{d}\ \text{ is odd}. \end{cases} \end{align*}
-
(ii) if dst is odd, then there exists a D-distance set family
$\mathcal{F} \subseteq 2^{[n]}$
of size
\begin{align*} |\mathcal{F}| = \bigl(2 - o(1)\bigr) \cdot \frac{\binom{n/d}{\lfloor t/2 \rfloor - \lceil s/2 \rceil + 1}}{\binom{\lfloor t/2 \rfloor}{\lfloor t/2 \rfloor - \lceil s/2 \rceil + 1}}. \end{align*}
Inspired by [Reference Huang, Klurman and Pohoata29, theorem 3·2], we are going to apply the following lemma in our constructions to establish Theorem 2·1(i)· This lemma is known as “the Rödl nibble” [Reference Rödl46]. (See also [Reference Alon and Spencer3, section 4·7].)
Lemma 2·2. Let
$s, t \in \mathbb{N}$
with
$1 \le s \le t$
. As
$m \to \infty$
, there exists a t-uniform set family
$\mathcal{F} \subseteq 2^{[m]}$
of size
$|\mathcal{F}| = \bigl( 1 - o(1) \bigr) \cdot \big({\binom{m}{t-s+1}}/{\binom{t}{t-s+1}}\big)$
such that
$|A \cap B| \le t - s$
holds for any pair of distinct
$A, B \in \mathcal{F}$
.
Proof of Theorem 2·1(i). We first look at the case when d is even. Write
$m {\stackrel{\text{def}}{\,=\,}} \lfloor 2n/d \rfloor$
. Thanks to Lemma 2·2, we are able to find a t-uniform family
$\mathcal{F}' \subseteq 2^{[m]}$
of size
$|\mathcal{F}'| = (1-o(1)) \cdot \big({\binom{m}{t-s+1}}/{\binom{t}{t-s+1}}\big)$
such that
$|A' \cap B'| \le t - s$
holds for any pair of distinct
$A', B' \in \mathcal{F}'$
. This implies that
\begin{align*} |A' \bigtriangleup B'| \in \bigl\{ 2t, 2t-2, \dots, 2t-2(t-s) \bigr\} = \bigl\{ 2s, 2s+2, \dots, 2t \bigr\}. \end{align*}
Since d is even, we can replace each element in [m] by a unique group of
$d/2$
distinct elements in [n]. This replacement then turns
$\mathcal{F}'$
into a D-distance family
$\mathcal{F} \subset 2^{[n]}$
of desired size.
If d is odd, we replace D by
$D_{\operatorname{even}}$
and the same construction as above gives us a
$D_{\operatorname{even}}$
-distance (hence D-distance) family
$\mathcal{F} \subset 2^{[n]}$
of desired size. That is, we begin with a
$\lfloor t/2\rfloor$
-uniform family of size
$(1-o(1)) \cdot \big({\binom{m}{\lfloor t/2\rfloor-\lceil s/2\rceil+1}}/{\binom{\lfloor t/2\rfloor}{\lfloor t/2\rfloor-\lceil s/2\rceil+1}}\big)$
and pairwise intersection size at most
$\lfloor t/2\rfloor - \lceil s/2\rceil$
, and then blowup each element in [m] to a unique group of size d. (We have
$\lfloor t/2\rfloor \ge \lceil s/2\rceil$
since st is even.)
To prove Theorem 2·1(ii), we need the following extension of Lemma 2·2.
Lemma 2·3. Let
$s', t' \in \mathbb{N}_+$
with
$1 \le s' \le t' + 1$
. As
$m \to \infty$
, there exist two t′-uniform families
$\mathcal{F}_1, \mathcal{F}_2 \subseteq 2^{[m]}$
, each of size
$(1-o(1)) \cdot \big({\binom{m}{t'-s'+1}}/{\binom{t'}{t'-s'+1}}\big)$
such that:
-
(i)
$|A \cap B| \le t' - s'$
holds for any pair of distinct
$A, B \in \mathcal{F}_1$
or
$A, B \in \mathcal{F}_2$
, and -
(ii)
$|A \cap B| \le t' - s' + 1$
holds for any pair of
$A \in \mathcal{F}_1, \, B \in \mathcal{F}_2$
.
We remark that one can force
$\mathcal{F}_1$
and
$\mathcal{F}_2$
to be disjoint in Lemma 2·3. In fact, the second condition directly shows the disjointness, provided that
$s' \gt 1$
. However, this is unnecessary for our application.
Proof of Theorem 2·1(ii) assuming Lemma 2·3. Let
$s'\, {\stackrel{\text{def}}{\,=\,}} \lceil s/2 \rceil, \, t'\, {\stackrel{\text{def}}{\,=\,}} \lfloor t/2 \rfloor$
. Conversely, this implies that
$s = 2s' - 1, \, t = 2t' + 1$
. Define the parameter
$m {\stackrel{\text{def}}{\,=\,}} \lfloor n/d \rfloor - 1$
.
Let
$\mathcal{F}_1, \mathcal{F}_2 \subseteq 2^{[m]}$
be two t
′-uniform families obtained from Lemma 2·3. Append a new element
$m + 1$
to each set in
$\mathcal{F}_2$
. Then replace each element in
$[m+1]$
by a unique group of d distinct elements in [n]. Let the resulting families be
$\mathcal{F}_1', \mathcal{F}_2'$
. For any distinct
$A, B \in \mathcal{F}_1'$
or
$A, B \in \mathcal{F}_2'$
, we have
\begin{align*} |A \bigtriangleup B| \in d \cdot \bigl\{ 2t', 2t'-2, \dots, 2t'-2(t'-s') \bigr\} = \bigl\{ (s+1)d, (s+2)d, \dots, (t-1)d \bigr\} \subseteq D. \end{align*}
Moreover, for any
$A \in \mathcal{F}_1', \, B \in \mathcal{F}_2'$
, we have
\begin{align*} |A \bigtriangleup B| \in d \cdot \bigl\{ 2t'+1, 2t'-1, \dots, 2t'+1-2(t'-s'+1) \bigr\} = \bigl\{ sd, (s+1)d, \dots, td \bigr\} = D. \end{align*}
Since
$\mathcal{F}_1'$
and
$\mathcal{F}_2'$
are disjoint (due to element
$m + 1$
), we see that
$\mathcal{F}_1' \cup \mathcal{F}_2'$
is a D-distance family with
\begin{align*} |\mathcal{F}_1' \cup \mathcal{F}_2'| = |\mathcal{F}_1'| + |\mathcal{F}_2'| = |\mathcal{F}_1| + |\mathcal{F}_2| = \bigl(2 - o(1)\bigr) \cdot \frac{\binom{n/d}{\lfloor t/2 \rfloor - \lceil s/2 \rceil + 1}}{\binom{\lfloor t/2 \rfloor}{\lfloor t/2 \rfloor - \lceil s/2 \rceil + 1}}. \end{align*}
We are left to establish Lemma 2·3. The Rödl nibble (Lemma 2·2) already implies the existence of
$\mathcal{F}_1$
and
$\mathcal{F}_2$
separately. However, it is difficult to control the intersections between sets in
$\mathcal{F}_1, \mathcal{F}_2$
. To achieve this, we need tools from combinatorial design theory.
An (N, q, r)-design is a family
$\mathcal{S}$
of q-subsets of [N] in which every r-subset of [N] appears as a subset of exactly one set in
$\mathcal{S}$
. By considering the codegree of an i-subset for
$i = 0, 1, \dots, r - 1$
, an obvious necessary condition for the existence of an (N, q, r)-design is the divisibility condition:
\begin{align*}\binom{q-i}{r-i} \text{divides} \binom{N-i}{r-i}\,\,\, \text{for}\, i = 0, 1, \dots, r-1.\end{align*}
A profound result due to Keevash [Reference Keevash32] states that this divisibility condition is sufficient for large N.
Theorem 2·4. Let q, r be positive integers with
$q \ge r$
. For every sufficiently large positive integer N satisfying the divisibility condition, an (N, q, r)-design exists.
We remark that alternative and simpler proofs of Theorem 2·4 can be found in [Reference Delcourt and Postle14, Reference Glock, Kühn, Lo and Osthus28, Reference Keevash33].
To prove Lemma 2·3, the idea is to begin with an
$(N, t', t'-s'+2)$
-design, and then extract
$\mathcal{F}_1, \mathcal{F}_2$
successively from it. Recall that a hypergraph is linear if any pair of its edges intersects in at most one vertex, and a matching in a hypergraph is a set of vertex-disjoint hyperedges.
Informally, the following technical result from [Reference Alon, Kim and Spencer2, Reference Kostochka and Rödl36] says that an almost perfect matching always exists in a uniform almost regular linear hypergraph.
Theorem 2·5. For any positive integers
$\ell \ge 3$
and K, there exists some
$D_0 = D_0(\ell, K)$
such that the following property holds: Suppose
$D \ge D_0$
and let
$\mathcal{H} = (V, \mathcal{E})$
be an
$\ell$
-uniform linear hypergraph with
$D - K\sqrt{D \log D} \le \deg_{\mathcal{H}}(v) \le D$
for all vertices
$v \in V$
. Then as
$|V| \to \infty$
, there exists a matching covering all but at most
$O\bigl(|V|D^{-1/(\ell-1)}\log^{3/2}D\bigr)$
vertices.
Due to the almost regularity restriction
$D - K\sqrt{D \log D} \le \deg_{\mathcal{H}}(x) \le D$
in Theorem 2·5, we have to find a design (using the deep result Theorem 2·4) instead of an almost design (via Lemma 2·2).
Proof of Lemma 2·3. When
$s' = 1$
, upon setting
$\mathcal{F}_1 = \mathcal{F}_2 {\stackrel{\text{def}}{\,=\,}} \binom{[m]}{t'}$
we are done. If
$s' = t' + 1$
, then we can choose two single-set families supported on distinct elements
$\mathcal{F}_1 = [t'],$
$\mathcal{F}_2 = \{t'+1,\ldots,2t'\}$
.
Assume
$t'\ge s' \ge 2$
then. Pick the largest integer
$N \le m$
satisfying
$N \equiv q \pmod Q$
, where
\begin{align*} Q {\stackrel{\text{def}}{\,=\,}} r! \cdot \prod\limits_{i=0}^{r-1} \dbinom{q-i}{r-i}, \quad q {\stackrel{\text{def}}{\,=\,}} t', \quad r {\stackrel{\text{def}}{\,=\,}} t' - s' + 2. \end{align*}
Since s
′, t
′ (hence q, r) are fixed, we have
$m - N = O(1)$
. For
$i = 0, 1, \dots, r - 1$
, we compute
\begin{align*} (r-i)! \cdot \binom{N-i}{r-i} = (N-i) \cdots (N-r+1) &\equiv (q-i) \cdots (q-r+1) \\&= (r-i)! \cdot \binom{q-i}{r-i} \pmod{Q}. \end{align*}
Since
$(r-i)! \cdot \binom{q-i}{r-i}$
divides Q, we have
$\binom{q-i}{r-i}$
divides
$\binom{N-i}{r-i}$
. So, N satisfies the divisibility condition. Due to Theorem 2·4, we can find an
$(N, t', t'-s'+2)$
-design
$\mathcal{S}$
on [N] when m is sufficiently large.
Construct an
$\ell$
-uniform linear hypergraph
$\mathcal{H} = (V, \mathcal{E})$
of uniformity
$\ell = \binom{t'}{t'-s'+1}$
as follows. Let V be the set of
$(t'-s'+1)$
-subsets of [N]. For each
$A \in \mathcal{S}$
, include a hyperedge
$\{B \in V \colon B \subseteq A\}$
into
$\mathcal{E}$
. Since each
$(t'-s'+2)$
-subset of [N] is contained in exactly one t’-subset in
$\mathcal{S}$
, the hypergraph
$\mathcal{H}$
is linear and D-regular, where
$D = {(N-(t'-s'+1))}/{(t'-(t'-s'+1))}$
. By Theorem 2·5, since
$D = \Omega(N)$
and
$D_0 = O(1)$
, there exists a matching
$\mathcal{M}$
in the hypergraph
$\mathcal{H}$
covering
$\bigl(1 - o(1)\bigr)$
-proportion of its vertices. Phrasing differently, this matching
$\mathcal{M}$
misses
$o \big( \binom{N}{t'-s'+1} \big)$
vertices. Take
$\mathcal{F}_1$
to be the set of t’-sets in
$\mathcal{S}$
which corresponds to the hyperedges in
$\mathcal{M}$
.
Consider the
$\ell$
-uniform linear hypergraph
$\mathcal{H}' = (V, \mathcal{E}')$
for
$\mathcal{E}' {\stackrel{\text{def}}{\,=\,}} \mathcal{E} \setminus \mathcal{M}$
. This is the hypergraph obtained by stripping a matching from the D-regular hypergraph
$\mathcal{H}$
. It follows that the degree of each vertex in
$\mathcal{H}'$
is either
$D-1$
or D. From Theorem 2·5 we deduce that
$\mathcal{H}'$
also admits an almost perfect matching. Take
$\mathcal{F}_2$
to be the set of t’-sets in
$\mathcal{S}$
corresponding to this matching.
For any pair of distinct sets
$A, B \in \mathcal{F}_1$
or
$A, B \in \mathcal{F}_2$
, since their corresponding hyperedges in
$\mathcal{H}$
are vertex-disjoint, we have
$|A \cap B| \le t' - s'$
. Also, for any pair of
$A \in \mathcal{F}_1$
and
$B \in \mathcal{F}_2$
, we have
$|A \cap B| \le t'-s'+1$
as
$\mathcal{H}$
is linear. Since
$m - N = O(1)$
, the families
$\mathcal{F}_1, \mathcal{F}_2$
meet all requirements in lem:rodlvariant, and hence the proof is complete.
3. Proof of the upper bounds in Theorem 1·1
In this section, we prove the following result which implies the upper bounds in Theorem 1·1.
Theorem 3·1. Suppose d, s, t are positive integers with
$1 \le s \le t$
. Let
$D = \{ sd, (s+1)d, \dots, td \}$
be a homogeneous arithmetic progression, and
$\mathcal{F} \subseteq 2^{[n]}$
be a D-distance family. As
$n \to \infty$
, we have
\begin{align*} |\mathcal{F}| \le \begin{cases} \bigl(1 + o(1)\bigr) \cdot \prod\limits_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell} \qquad &\text{if }\textit{dst}\text{ is even}, \\ \bigl(2 + o(1)\bigr) \cdot \prod\limits_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell} \qquad &\text{if }\textit{dst}\text{ is odd}. \end{cases} \end{align*}
We remark that if
$D_{\operatorname{even}} = \varnothing$
(dst is odd and
$s = t$
), conventionally the empty product is 1.
Indeed, when dst is odd,
$\lfloor t/2 \rfloor = {(t-1)}/{2}, \, \lceil s/2 \rceil = {(s+1)}/{2}, \, |D_{\operatorname{even}}| = \lfloor t/2 \rfloor - \lceil s/2 \rceil + 1 = {(t-s)}/{2}$
, and so
\begin{align*}\bigl(2 + o(1)\bigr) \cdot \prod_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell} = \bigl(2 + o(1)\bigr) \cdot \frac{(\frac{n}{d})^{\frac{t-s}{2}}}{\frac{s+1}{2} \cdot \frac{s+3}{2} \cdot \cdots \cdot \frac{t-1}{2}} = \bigl(2 + o(1)\bigr) \cdot \frac{\binom{n/d}{(t-s)/2}}{\binom{(t-1)/2}{(t-s)/2}},\end{align*}
implying the upper bound in Theorem 1·1. Other cases are similar.
3·1. Distance families versus intersecting families
A set family
$\mathcal{F}$
is k-uniform if
$|A| = k \, (\forall A \in \mathcal{F})$
. For a set of non-negative integers L, we say that
$\mathcal{F}$
is an L-intersecting family if
$|A \cap B| \in L$
holds for each pair of distinct
$A, B \in \mathcal{F}$
. A classical result concerning intersecting families is the Frankl–Wilson theorem below.
Theorem 3·2
[Reference Frankl and Wilson25]. Suppose
$0 \le \ell_1 \lt \dots \lt \ell_r \lt k$
are integers and write
$L {\stackrel{\text{def}}{\,=\,}} \{\ell_1, \dots, \ell_r\}$
. If
$\mathcal{F} \subseteq 2^{[n]}$
is a k-uniform L-intersecting family, then
$|\mathcal{F}| \le \binom{n}{r}$
.
Let
$\mathcal{F}$
be a D-distance family. By flipping the belonging relation of a single number in [n] to each set from
$\mathcal{F}$
simultaneously, we may assume without loss of generality that
$\varnothing \in \mathcal{F}$
. It follows that
$|A| = |A \bigtriangleup \varnothing| \in D$
holds for all
$A \in \mathcal{F} \setminus \{\varnothing\}$
. Partition
$\mathcal{F} \setminus \varnothing$
into a disjoint union of
$\mathcal{F}_d$
for
$d \in D$
. From the fact
$2|A \cap B| = |A| + |B| - |A \bigtriangleup B|$
we deduce that
$\mathcal{F}_d$
is an
$L_d$
-intersecting family, where the set of intersection sizes is
$L_d {\stackrel{\text{def}}{\,=\,}} d - {D_{\operatorname{even}}}/{2} = \bigl\{d - {k}/{2} \colon k \in D_{\operatorname{even}}\bigr\}$
. After dropping negative integers in
$L_d$
, the Frankl–Wilson theorem (Theorem 3·2) directly shows the following crude upper bound.
Corollary 3·3. If
$\mathcal{F} \subseteq 2^{[n]}$
is a D-distance family, then
$|\mathcal{F}| \le |D| \cdot n^{|D_{\operatorname{even}}|}$
.
One can see that the order of magnitude in Corollary 3·3 already matches that from the upper bounds in Theorem 1·1, and the most interesting part in our main result is to find the sharp leading coefficient. The following result proved by Deza, Erdős and Frankl [Reference Deza, Erdős and Frankl17] can be viewed as a refinement of the Frankl–Wilson theorem. This is crucial for us to establish the upper bounds in Theorem 1·1. Instead of the original statement, here we state a slightly weaker version.
Theorem 3·4.
[Reference Frankl and Tokushige24
, theorem 18·1]. Let
$0 \le \ell_1 \lt \dots \lt \ell_r \lt k$
and
$n \ge 2^k k^3$
be integers and write
$L {\stackrel{\text{def}}{\,=\,}} \{\ell_1, \dots, \ell_r\}$
. If
$\mathcal{F} \subseteq 2^{[n]}$
is a k-uniform L-intersecting family, then
$|\mathcal{F}| \le \prod_{i=1}^r {(n-\ell_i)}/{(k-\ell_i)}$
. Moreover, if
$|\mathcal{F}| \ge 2^k k^2 n^{r-1}$
, then there exists
$C \subseteq [n]$
with
$|C| = \ell_1$
such that C is contained in every set in
$\mathcal{F}$
.
We also need the following corollary of Theorem 3·4.
Lemma 3·5. If
$\mathcal{G} \subseteq 2^{[n]}$
is a k-uniform D-distance set family with
$n \ge 2^k k^3$
, then
$|\mathcal{G}| \le \prod\limits_{\ell \in D_{\operatorname{even}}} {2n}/{\ell}$
.
Proof. For distinct
$A, B \in \mathcal{G}$
, since
$|A \bigtriangleup B| = |A| + |B| - 2|A \cap B|$
, we see that
$\mathcal{G}$
is an L-intersecting family, where
$L {\stackrel{\text{def}}{\,=\,}} \bigl( k - {D_{\operatorname{even}}}/{2} \bigr) \cap \mathbb{Z}_{\ge 0}$
. It then follows from Theorem 3·4 that
\begin{align*} |\mathcal{G}| \le \prod_{\ell \in L} \frac{n-\ell}{k-\ell} \le \prod_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell}. \end{align*}
3.2. Proof of Theorem 3·1
The
$D_{\operatorname{even}} = \varnothing$
case is easy. We shall discuss it separately at the beginning of Section 4.
Here and after we assume that
$D_{\operatorname{even}} \ne \varnothing$
. By passing to a subprogression of D if necessary, we may assume that there is a pair of sets
$\mathcal{F}$
realising the maximum distance td in D. By flipping the belonging relation of a single element in [n] to each set from
$\mathcal{F}$
simultaneously and then relabeling, we may further assume that
$\varnothing \in \mathcal{F}$
and
$[td] \in \mathcal{F}$
. Introduce the auxiliary subfamily
\begin{align*}\mathcal{F}' {\stackrel{\text{def}}{\,=\,}} \bigl\{ A \in \mathcal{F} \colon \bigl| A \setminus [td] \bigr| \ge d^*/2 \bigr\}, \text{where $d^*\, {\stackrel{\text{def}}{\,=\,}} \max(D_{\operatorname{even}})$}.\end{align*}
To upper bound
$|\mathcal{F}|$
, we are to show that
$|\mathcal{F} \setminus \mathcal{F}'|$
is small; and to upper bound
$|\mathcal{F}'|$
by analyzing its intersection pattern and applying the Frankl–Wilson and the Deza–Erdős–Frankl theorems.
Claim 3.6. As
$n \to \infty$
, we have
$|\mathcal{F} \setminus \mathcal{F}'| = O \bigl( n^{|D_{\operatorname{even}}|-1} \bigr)$
.
Proof. For each
$S \subseteq [td]$
, define
$\mathcal{F}_S {\stackrel{\text{def}}{\,=\,}} \bigl\{ A \in \mathcal{F} \setminus \mathcal{F}' \colon A \cap [td] = S \bigr\}$
. It suffices to show that
$|\mathcal{F}_S| = O\bigl(n^{|D_{\operatorname{even}}|-1}\bigr)$
. For distinct
$A, B \in \mathcal{F}_S$
, note that
$|A \bigtriangleup B| \le \bigl|A \setminus [td]\bigr| + \bigl|B \setminus [td]\bigr| \lt d^*$
. Thus,
$\mathcal{F}_S$
is a
$D \setminus \{d^*\}$
-distance family. The desired bound on
$|\mathcal{F}_S|$
then follows from Corollary 3·3.
It remains to upper bound the size of
$\mathcal{F}'$
.
Claim 3.7. For any
$A\in \mathcal{F}'$
, we have
\begin{align*}|A| = \begin{cases} td \qquad &\text{if }\textit{td}\text{ is even}, \\ \text{}\textit{td}\text{ or $(t-1)d$} \qquad &\text{if }\textit{td}\text{ is odd}.\end{cases}\end{align*}
Proof. Write
$x {\stackrel{\text{def}}{\,=\,}} \bigl| A \cap [td] \bigr|$
and
$y {\stackrel{\text{def}}{\,=\,}} \bigl| A \setminus [td] \bigr| \ge d^*/2$
. Since
$\mathcal{F}'$
is a D-distance family,
\begin{align*} y + (td-x) = \bigl| A \setminus [td] \bigr| + \bigl| [td] \setminus A \bigr| = \bigl| A \bigtriangleup [td] \bigr| \le td \implies y \le x. \end{align*}
It follows that
$|A| = x + y \ge 2y \ge d^*$
, and so
$|A| \ge td$
if td is even while
$|A| \ge (t-1)d$
if td is odd. On the other hand,
$|A| \le td$
as
$\varnothing \in \mathcal{F}$
, concluding the claim.
If td is even, then
$d^* = td$
, and Claim 3.7 says that
$\mathcal{F}'$
is a td-uniform D-distance set family. So, from Lemma 3·5 and Claim 3·6 we deduce that
\begin{equation} |\mathcal{F}| = |\mathcal{F}'| + |\mathcal{F} \setminus \mathcal{F}'| \le \prod_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell} + O\bigl(n^{|D_{\operatorname{even}}|-1}\bigr) = \bigl(1+o(1)\bigr) \cdot \prod_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell}.\end{equation}
If td is odd, then
$d^* = (t-1)d$
. Due to Claim 3·7, we are able to partition
$\mathcal{F}'$
into a td-uniform family
$\mathcal{F}'_1{\stackrel{\text{def}}{\,=\,}} \{ A \in \mathcal{F}' \,:\, |A| = td \}$
and a
$(t-1)d$
-uniform family
$\mathcal{F}'_2{\stackrel{\text{def}}{\,=\,}} \{ A \in \mathcal{F}' \colon |A| = (t-1)d \}$
. It then follows from Lemma 3·5 and Claim 3·6 that
\begin{equation} |\mathcal{F}| = |\mathcal{F}'_1| + |\mathcal{F}'_2| + |\mathcal{F} \setminus \mathcal{F}'| \le \bigl(2+o(1)\bigr) \cdot \prod_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell}.\end{equation}
By combining (3·1) and (3·2), Theorem 3·1 is proved in all but one case. We are left with improving the upper bound on
$|\mathcal{F}|$
by a factor of 2 when d, t are odd and s is even. In this case,
\begin{align*}D_{\operatorname{even}} = \bigl\{ sd, (s+2)d, \dots, (t-1)d \bigr\}.\end{align*}
To achieve this, we need to analyse
$\mathcal{F}'_1, \mathcal{F}'_2$
carefully and utilise the structural part of Theorem 3·4.
For distinct
$A, B\in \mathcal{F}'$
, we compute the possible sizes of their intersection as follows:
\begin{align*}|A \cap B| = \frac{|A|+|B|-|A \bigtriangleup B|}{2} \in \begin{cases} td - \frac{D_{\operatorname{even}}}{2} \qquad &\text{if $A, B \in \mathcal{F}'_1$}; \\ (t-1)d - \frac{D_{\operatorname{even}}}{2} \qquad &\text{if $A, B \in \mathcal{F}'_2$};\\ (t-1)d - \frac{D_{\operatorname{even}}}{2} \qquad &\text{if $A \in \mathcal{F}'_1$ and $B \in \mathcal{F}'_2$}.\end{cases}\end{align*}
Denote
\begin{align*} L_1 &{\stackrel{\text{def}}{\,=\,}} td - \tfrac{D_{\operatorname{even}}}{2} = \Bigl\{ \tfrac{(t+1)d}{2}, \tfrac{(t+3)d}{2}, \dots, \tfrac{(2t-s)d}{2} \Bigr\}, \\ L_2 &{\stackrel{\text{def}}{\,=\,}} (t-1)d - \tfrac{D_{\operatorname{even}}}{2} = \Bigl\{ \tfrac{(t-1)d}{2}, \tfrac{(t+1)d}{2}, \dots, \tfrac{(2t-s-2)d}{2} \Bigr\}.\end{align*}
It follows that
$\mathcal{F}'_1$
is an
$L_1$
-intersecting family and
$\mathcal{F}'_2$
is an
$L_2$
-intersecting family.
For any set family
$\mathcal{G}$
, we denote its center as
$\bigcap \mathcal{G} {\stackrel{\text{def}}{\,=\,}} \bigcap_{A \in \mathcal{G}} A$
. If the center of
$\mathcal{F}'_1$
is of size smaller than
$\min \bigl( td - {D_{\operatorname{even}}}/{2} \bigr) = {(t+1)d}/{2}$
, then Theorem 3·4 implies that
$|\mathcal{F}'_1| = O\bigl( n^{|D_{\operatorname{even}}|-1} \bigr)$
, and hence
\begin{align*}|\mathcal{F}| = |\mathcal{F}'_1| + |\mathcal{F}'_2| + |\mathcal{F} \setminus \mathcal{F}'| \le \bigl(1+o(1)\bigr) \cdot \prod_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell}.\end{align*}
We may then assume
$\bigl| \bigcap \mathcal{F}'_1 \bigr| \ge {(t+1)d}/{2}$
and similarly
$\bigl| \bigcap \mathcal{F}'_2 \bigr| \ge \min \bigl( (t-1)d - {D_{\operatorname{even}}}/{2} \bigr) = {(t-1)d}/{2}$
.
Arbitrarily fix a
${(t+1)d}/{2}$
-element subset
$X_1 \subseteq \bigcap \mathcal{F}'_1$
and a
${(t-1)d}/{2}$
-element subset
$X_2 \subseteq \bigcap \mathcal{F}'_2$
.
Case 1.
$X_2 \subseteq X_1$
.
Denote
$Y {\stackrel{\text{def}}{\,=\,}} X_1 \setminus X_2$
and observe that
$|Y| = {(t+1)d}/{2} - {(t-1)d}/{2} = d$
. For each
$S \subseteq Y$
, we write
\begin{align*}\mathcal{F}_{2, S} {\stackrel{\text{def}}{\,=\,}} \{A \in \mathcal{F}'_2 \colon A \cap Y = S\}\end{align*}
and thus partition
$\mathcal{F}'_2 = \bigcup_{S \subseteq Y} \mathcal{F}_{2, S}$
into
$2^{|Y|} = 2^d$
subfamilies. For each non-empty
$S \subseteq Y$
and any distinct
$A, B \in \mathcal{F}_{2, S}$
, we have
$|A \cap B| \ge |X_2| + |S| \gt {(t-1)d}/{2}$
. Then
$\mathcal{F}_{2, S}$
is a
$(t-1)d$
-uniform and
$L_2 \setminus \bigl\{ {(t-1)d}/{2} \bigr\}$
-intersecting family, and so from Theorem 3·2 we deduce that
$|\mathcal{F}_{2, S}| = O\bigl( n^{|D_{\operatorname{even}}|-1} \bigr)$
.
Define
$\mathcal{F}_{2, \varnothing}^+ {\stackrel{\text{def}}{\,=\,}} \{A \cup Y \colon A \in \mathcal{F}_{2, \varnothing}\}$
. Then, crucially, we observe that the union
$\mathcal{F}'_1 \cup \mathcal{F}_{2, \varnothing}^+$
forms a td-uniform
$L_1$
-intersecting family, since sets between
$\mathcal{F}'_1, \mathcal{F}'_2$
are
$L_2$
-intersecting and
$L_1 = L_2 + |Y|$
. This implies
$|\mathcal{F}'_1 \cup \mathcal{F}_{2, \varnothing}^+| \le\prod\limits_{\ell \in D_{\operatorname{even}}} {2n}/{\ell}$
by Theorem 3·4.
We claim that
$\mathcal{F}'_1$
and
$\mathcal{F}_{2, \varnothing}^+$
are disjoint. Suppose there is some
$A \cup Y \in \mathcal{F}'_1 \cap \mathcal{F}_{2, \varnothing}^+$
. Again, sets between
$\mathcal{F}'_1$
and
$\mathcal{F}'_2$
have intersection size at most
$\max(L_2) = {(2t-s-2)d}/{2} \le (t-2)d$
as
$s\ge 2$
is even. However,
$A \cup Y \in \mathcal{F}'_1$
and
$A \in \mathcal{F}_{2, \varnothing} \subseteq \mathcal{F}_2'$
have intersection size
$|A| = (t-1)d$
, a contradiction. So,
\begin{align*}|\mathcal{F}| &= |\mathcal{F}'_1| + |\mathcal{F}'_2| + |\mathcal{F} \setminus \mathcal{F}'| \\&\quad= |\mathcal{F}'_1 \cup \mathcal{F}_{2, \varnothing}^+| + \sum_{\varnothing \ne S \subseteq Y} |\mathcal{F}_{2, S}| + |\mathcal{F} \setminus \mathcal{F}'| \le \bigl(1+o(1)\bigr) \cdot \prod\limits_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell}.\end{align*}
Case 2.
$X_2 \nsubseteq X_1$
.
Pick some element
$x \in X_2$
and set
$Z \in \mathcal{F}'_1$
such that
$x \notin Z$
. For each
$T \subseteq Z$
, we write
\begin{align*}\mathcal{F}_{2, T} {\stackrel{\text{def}}{\,=\,}} \{A \in \mathcal{F}'_2 \colon A \cap Z = T\}\end{align*}
and partition
$\mathcal{F}'_2$
into
$2^{|Z|} = 2^{td}$
subfamilies. Recall that for any
$A \in \mathcal{F}'_2$
, we have
$|A \cap Z| \in L_2$
, and so
$\mathcal{F}_{2, T} = \varnothing$
whenever
$|T| \lt \min(L_2) = {(t-1)d}/{2}$
. Fix an arbitrary
$T \subseteq Z$
with
$|T| \ge {(t-1)d}/{2}$
. For every distinct
$A, B \in \mathcal{F}_{2, T}$
, observe that
$T \cup \{x\} \subseteq A \cap B$
, hence
$|A \cap B| \ge {(t+1)d}/{2}$
. It follows that
$\mathcal{F}_{2, T}$
is
$(t-1)d$
-uniform and
$L_2 \setminus \{ {(t-1)d}/{2} \}$
-intersecting, and so
$|\mathcal{F}_{2, T}| = O( n^{|D_{\operatorname{even}}|-1} )$
by Theorem 3·2. So,
\begin{align*}|\mathcal{F}| = |\mathcal{F}'_1| + |\mathcal{F}'_2| + |\mathcal{F} \setminus \mathcal{F}'| = |\mathcal{F}'_1| + \sum_{T \subseteq Z} |\mathcal{F}_{2, T}| + |\mathcal{F} \setminus \mathcal{F}'| \le \bigl(1+o(1)\bigr) \cdot \prod\limits_{\ell \in D_{\operatorname{even}}} \frac{2n}{\ell}.\end{align*}
We thus conclude the case when s is even and d, t are odd. The proof of Theorem 3·1 is complete·
4. Proof of Theorem 1·2
The
$D_{\operatorname{even}} = \varnothing$
case is easy, and is already included in the previous work due to Huang, Klurman and Pohoata [Reference Huang, Klurman and Pohoata29, section 3]. In fact, the D-distance family
$\bigl\{ \varnothing, [sd+a] \bigr\}$
shows
$f_D(n) \ge 2$
, and from
\begin{align*}|A \bigtriangleup B| + |B \bigtriangleup C| + |C \bigtriangleup A| = 2 \bigl( |A \cup B \cup C| - |A \cap B \cap C| \bigr)\end{align*}
we deduce that
$f_D(n) \le 2$
. It follows that
$f_D(n) = 2$
whenever
$D_{\operatorname{even}} = \varnothing$
and
$n \ge \min (D)$
.
Hereafter we focus on the
$D_{\operatorname{even}} \ne \varnothing$
case. Set
$u {\stackrel{\text{def}}{\,=\,}} {\min(D_{\operatorname{even}})}/{2}$
. Then any collection of
$\bigl\lfloor {n}/{u} \bigr\rfloor$
disjoint u-subsets of [n] is a D-distance family, and so
$f_D(n) \ge \bigl\lfloor {n}/{u} \bigr\rfloor = \bigl\lfloor {2n}/{\min(D_{\operatorname{even}})} \bigr\rfloor$
. The lower bound follows.
To deduce the upper bound, we need the following result concerning modular intersecting families due to Babai, Frankl, Kutin and Štefankovicč.
Theorem 4·1.
[Reference Babai, Frankl and Kutin4
, theorem 1.1]. Suppose p is a prime,
$q {\stackrel{\text{def}}{\,=\,}} p^k \, (k \in \mathbb{N}_+)$
, and
$L \subseteq \{0, 1, \dots, q-1\}$
. Assume X is an n-element ground set and
$A_1, \dots, A_m$
are subsets of X with the following property:
-
(1) for any
$i, j \in [m]$
, the modular cardinality
$|A_i \cap A_j| \pmod q \in L$
if and only if
$i \ne j$
.
Set
$D {\stackrel{\text{def}}{\,=\,}} 2^{|L|-1}$
. Then
$m \le \binom{n}{D} + \binom{n}{D-1} + \dots + \binom{n}{0}$
.
Let
$\mathcal{F}$
be a D-difference family and assume without loss of generality that
$\varnothing \in \mathcal{F}$
. Consider the family
$\mathcal{F}' {\stackrel{\text{def}}{\,=\,}} \mathcal{F} \setminus \{\varnothing\}$
. Then
$|A| = |A \bigtriangleup \varnothing| \in D$
holds for any
$A \in \mathcal{F}'$
. For any sets A, B, note that
\begin{equation} 2|A \cap B| = |A| + |B| - |A \bigtriangleup B|.\end{equation}
Since
$a \lt d$
, we can find a prime power
$q = p^k$
that divides d but not a. Here p is a prime.
-
(1) If
$p = 2$
, then the fact
$D_{\operatorname{even}} \ne \varnothing$
implies that a is even and
$k \ge 2$
. For each
$A \in \mathcal{F}'$
, we have
$|A| \equiv a \pmod {2^{k-1}}$
. For distinct
$A, B \in \mathcal{F}'$
, from (4·1) we deduce that
$|A \cap B| \equiv ({a}/{2}) \pmod {2^{k-1}}$
. Notice that
$a\not\equiv ({a}/{2}) \pmod {2^{k-1}}$
as q does not divide a. Thus, Theorem 4·1 applied to
$2^{k-1}$
and
$L = \bigl\{ {a}/{2} \bigr\}$
implies that
$|\mathcal{F}'| \le n + 1$
, and so
$|\mathcal{F}| \le n + 2$
. -
(2) If
$p \ge 3$
, then q is odd. For every
$A \in \mathcal{F}'$
, we have
$|A| \equiv a \pmod q$
. For distinct
$A, B \in \mathcal{F}'$
, from (4·1) we deduce that
$2|A \cap B| \equiv a \pmod q$
hence
$|A \cap B| \equiv {a(q+1)}/{2} \pmod q$
. Again, notice that
$a \not\equiv {a(q+1)}/{2} \pmod q$
since q does not divide a. Therefore, Theorem 4·1 applied to q and
$L = \bigl\{ {a(q+1)}/{2} \bigr\}$
implies that
$|\mathcal{F}'| \le n + 1$
, and so
$|\mathcal{F}| \le n + 2$
.
By combining the cases above, the proof of Theorem 1·2 is complete.
5. Proof of Theorem 1·4
Fix a t-set
$D \subseteq \mathbb{N}_+$
with
$D \ne \{2, 4, \dots, 2t\}$
and take n be sufficiently large in terms of t. Thanks to Corollary 3·3, it suffices to prove the special case that D consists of even numbers. Let
$\mathcal{F}$
be a D-distance family. Write
$d {\stackrel{\text{def}}{\,=\,}} \max(D)$
and assume without loss of generality that
$\varnothing \in \mathcal{F}, \, [d] \in \mathcal{F}$
. Then for any set
$A\in \mathcal{F}\setminus\{\varnothing\}$
, we have
$|A|\in D$
.
5·1. Bounding
$A(\mathcal{H}_n, D)$
away from
$A \bigl( \mathcal{H}_n, \{2, 4, \dots, 2t\} \bigr)$
If
$d \ge 4t^2$
, then we write
$\mathcal{F}(z) {\stackrel{\text{def}}{\,=\,}} \{A \in \mathcal{F} \colon |A| = z\}$
for each
$z \in D$
. Due to Lemma 3·5,
\begin{align*}|\mathcal{F}| = |\{\varnothing\}| + \sum_{z \in D} |\mathcal{F}(z)| \le 1 + \sum_{z \in D} \biggl( \prod_{\ell \in D} \frac{2n}{\ell} \biggr) \le 1 + t \cdot \frac{n^{t-1}}{(t-1)!} \cdot \frac{n}{2t^2} \le \Bigl( \frac{1}{2} + o(1) \Bigr) \cdot \binom{n}{t}.\end{align*}
We may then assume
$d \lt 4t^2$
. Similar to the proof of Theorem 3·1, we denote
\begin{align*}\mathcal{F}' {\stackrel{\text{def}}{\,=\,}} \bigl\{ A \in \mathcal{F} \colon \bigl| A \setminus [d] \bigr| \ge d/2 \bigr\}\end{align*}
and bound from above the sizes of
$\mathcal{F}'$
and
$\mathcal{F} \setminus \mathcal{F}'$
separately.
-
(1) For any
$A \in \mathcal{F}'$
, write
$x {\stackrel{\text{def}}{\,=\,}} \bigl| A \cap [d] \bigr|$
and
$y {\stackrel{\text{def}}{\,=\,}} \bigl| A \setminus [d] \bigr| \ge d/2$
. Then
$\bigl|A \bigtriangleup [d]\bigr| = d - x + y \le d$
, and so
$x \ge y \ge d/2$
, which implies that
$|A| = x + y \ge d$
. Combining this with
$|A| = |A \bigtriangleup \varnothing| \le d$
, we see that
$|A| = d$
. So,
$\mathcal{F}'$
is d-uniform. Thus, Lemma 3·5, along with the facts that D is a t-set consisting of even numbers and
$D \ne \{2, 4, \dots, 2t\}$
, implies
$|\mathcal{F}'| \le \prod\nolimits_{\ell \in D} {2n}/{\ell} \le {n^t}/{(t-1)!(t+1)}$
. -
(2) For any
$S \subseteq [d]$
, denote
$\mathcal{F}_S {\stackrel{\text{def}}{\,=\,}} \bigl\{ A \in \mathcal{F} \setminus \mathcal{F}' \colon A \cap [d] = S \bigr\}$
. For any pair of distinct
$A, B \in \mathcal{F}_S$
, from
$|A \bigtriangleup B| \le \bigl|A \setminus [d]\bigr| + \bigl|B \setminus [d]\bigr| \lt d$
we deduce that
$\mathcal{F}_S$
is a
$D \setminus \{d\}$
-distance family. Then Corollary 3·3 implies
$|\mathcal{F}_S| \le (t-1) \cdot n^{t-1}$
. It follows that
$|\mathcal{F} \setminus \mathcal{F}'| \lt 2^{4t^2}(t-1) \cdot n^{t-1}$
.
Combining the estimates above, we conclude the first part of Theorem 1·4 by estimating
\begin{align*}|\mathcal{F}| = |\mathcal{F}'| + |\mathcal{F} \setminus \mathcal{F}'| \le \frac{n^t}{(t-1)!(t+1)} + 2^{4t^2} (t-1) \cdot n^{t-1} \le \Bigl( \frac{t}{t+1} + o(1) \Bigr) \cdot \binom{n}{t}.\end{align*}
5·2. The unique maximiser
$D_0 = \{2, 4, \dots, 2t\}$
Let
$n \ge 2t + 2$
and
$D_0 = \{2, 4, \dots, 2t\}$
. Then
$A \bigl( \mathcal{H}_n, \{2, 4, \dots, 2t\} \bigr) = f_{D_0}(n)$
. We need to prove that
\begin{align*}f_{D_0}(n) = \begin{cases} \binom{n}{0} + \binom{n}{2} + \dots + \binom{n}{t-2} + \binom{n}{t} \qquad &\text{if }\,\textit{t}\, \text{is even}, \\ \binom{n}{1} + \binom{n}{3} + \dots + \binom{n}{t-2} + \binom{n}{t} \qquad &\text{if }\,\textit{t}\, \text{is odd}.\end{cases}\end{align*}
When t is even (resp. odd), the bound is achieved by subsets of [n] of even (resp. odd) size up to t.
Let
$\mathcal{F} \subset 2^{[n]}$
be a
$D_0$
-distance set family. We are going to construct an auxiliary graph in which we may view
$\mathcal{F}$
as an independent set. The following corollary of Cauchy’s Interlacing Theorem was discovered earlier by Cvetković. This provides a useful technique to upper bound the independence number
$\alpha(G)$
of a graph G. (A proof can be found after [Reference Huang, Klurman and Pohoata29, corollary 2·5].)
Proposition 5·1
([Reference Cvetković13]). Let
$G = ( [m], E )$
be an m-vertex graph and M be a pseudo-adjacency matrix of G, i.e., a symmetric
$m \times m$
matrix with
$M_{ij} = 0$
whenever
$ij \not\in E$
. Let
$n_{\le 0}(M), \, n_{\ge 0}(M)$
be the number of non-positive, non-negative eigenvalues of M. Then
$\alpha(G) \le \min \bigl\{ n_{\le 0}(M), n_{\ge 0}(M) \bigr\}$
.
If the distance
$|X \bigtriangleup Y|$
is even, then we observe that
$|X|$
and
$|Y|$
are of the same parity. So,
$\mathcal{F}$
consists solely of even-sized subsets or odd-sized subsets. By taking the symmetric difference with
$\{1\}$
altogether, we may assume without loss of generality that
$\mathcal{F} \subseteq \mathcal{X} {\stackrel{\text{def}}{\,=\,}} \bigl\{ X \subseteq 2^{[n]} \colon |X|\text{ is even} \bigr\}$
.
For each integer
$k \ge 0$
, construct an
$|\mathcal{X}| \times |\mathcal{X}|$
matrix
$M_k$
whose entries are either 0 or 1 with
\begin{align*}\text{$(M_k)_{X, Y} = 1$ if and only if $X, Y \in \mathcal{X}$ and $|X \bigtriangleup Y| = 2k$}.\end{align*}
Let
$V {\stackrel{\text{def}}{\,=\,}} \mathbb{R}^{\mathcal{X}}$
be the vector space indexed by
$\mathcal{X}$
. For any
$S \subseteq [n]$
, set
$\boldsymbol{\nu}_S \in V$
with
$(\boldsymbol{\nu}_S)_X {\stackrel{\text{def}}{\,=\,}} (\!-1)^{|X \cap S|}$
.
Proposition 5·2. We have
$\boldsymbol{\nu}_S = \mathbf{v}_{[n] \setminus S} \, (\forall S \subseteq [n])$
and the vectors
$\bigl\{ \boldsymbol{\nu}_S \colon S \subseteq [n] \bigr\}$
form an orthogonal basis of V. Moreover, the matrix
$M_k$
has an eigenvector
$\boldsymbol{\nu}_S$
of eigenvalue
$\sum_{i=0}^{|S|}(\!-1)^{i}\binom{|S|}{i}\binom{n-|S|}{2k-i}$
.
Proof. From
$X \in \mathcal{X}$
we deduce that
\begin{align*} |X \cap S| \equiv |X| - |X \cap S| = \bigl| X \cap \bigl([n] \setminus S\bigr) \bigr| \pmod 2, \end{align*}
and so
$\boldsymbol{\nu}_S = \mathbf{v}_{[n] \setminus S}$
. For any pair of
$S, S' \subseteq [n]$
with
$S' \ne S$
and
$S' \ne [n] \setminus S$
, we have
\begin{align*} \langle \boldsymbol{\nu}_S, \mathbf{v}_{S'} \rangle &= \sum_{X \in \mathcal{X}} (\!-1)^{|X \cap S|} \cdot (\!-1)^{|X \cap S'|} = \sum_{X \in \mathcal{X}} (\!-1)^{|X \cap \left( S \bigtriangleup S' \right)|} \\ &= \sum_{k=0}^{\infty} \biggl( \sum_{X \subseteq [n] \colon |X| = 2k} (\!-1)^{|X \cap (S \bigtriangleup S')|} \biggr) \\ &= \sum_{k=0}^{\infty} \Biggl( \sum_{i=0}^{2k} (\!-1)^i \binom{|S \bigtriangleup S'|}{i} \binom{n - |S \bigtriangleup S'|}{2k-i} \Biggr) \\ &= \sum_{i=0}^{\infty} \Biggl( (\!-1)^i \binom{|S \bigtriangleup S'|}{i} \cdot \sum_{k = \lceil i/2 \rceil}^{\infty} \binom{n-|S \bigtriangleup S'|}{2k-i} \Biggr) \\ &\overset{(\text{a})}{=} \sum_{i=0}^{\infty} \Biggl( (\!-1)^i \binom{|S \bigtriangleup S'|}{i} \cdot \frac{2^{n - |S \bigtriangleup S'|}}{2} \Biggr) \overset{(\text{b})}{=} 0, \end{align*}
where (a) follows from
$S' \ne [n] \setminus S$
together with
$\sum_{i=0}^{\infty} (\!-1)^i \binom{m}{i} = 0$
, and (b) follows from
$S \ne S'$
. Since
$\bigl| \bigl\{ \boldsymbol{\nu}_S \colon S \subseteq [n] \bigr\} \bigr| = 2^{n-1} = |\mathcal{X}|$
, the set
$\bigl\{ \boldsymbol{\nu}_S \colon S \subseteq [n] \bigr\}$
forms an orthogonal basis of V.
Abbreviate
$[n] \setminus Z$
as
$Z^c$
for any
$Z \subseteq [n]$
. For
$X, Y \subseteq [n]$
, observe that
\begin{align*} |Y \cap S| = |X \cap S| + |X^{c} \cap Y \cap S| - |X \cap Y^{c} \cap S|. \end{align*}
Think about
$\boldsymbol{\nu}_S$
as a column vector. It then follows that
\begin{align*} (M_k \cdot \boldsymbol{\nu}_S)_{X} &= \sum_{Y \in \mathcal{X}} (M_k)_{X, Y} \cdot (\boldsymbol{\nu}_S)_Y = \sum_{Y \subseteq [n] \colon |X \bigtriangleup Y| = 2k} (\!-1)^{|Y \cap S|} \\ &= (\!-1)^{|X \cap S|} \sum_{Y \subseteq [n] \colon |X \bigtriangleup Y| = 2k} (\!-1)^{|X^{c} \cap Y \cap S| + |X \cap Y^{c} \cap S|} \\ &\overset{(\text{c})}{=} (\!-1)^{|X \cap S|} \sum_{Y \subseteq [n] \colon |Y| = 2k} (\!-1)^{|Y \cap S| + |\varnothing|} \\ &= (\boldsymbol{\nu}_S)_X \cdot \sum_{i=0}^{|S|} (\!-1)^i \binom{|S|}{i}\binom{n-|S|}{2k-i}, \end{align*}
where at (c) we flip for every element of X the belonging between it and X, Y altogether, hence we assume
$X = \varnothing$
in the summation. This is valid because such a flipping does not affect the summand
$(\!-1)^{|X^{c} \cap Y \cap S| + |X \cap Y^{c} \cap S|}$
. So,
$\boldsymbol{\nu}_S$
is an eigenvector of
$M_k$
whose eigenvalue is exactly
\begin{align*} \sum_{i=0}^{|S|}(\!-1)^{i}\binom{|S|}{i}\binom{n-|S|}{2k-i}. \end{align*}
Construct a graph G on vertex set
$\mathcal{X}$
, where we put an edge between distinct
$S, T \in \mathcal{X}$
if and only if
$|S \bigtriangleup T| \ge 2t+2$
. The
$D_0$
-distance family
$\mathcal{F}$
corresponds to an independent set in G. Define a matrix
$M {\stackrel{\text{def}}{\,=\,}} \sum_{k \ge t+1} \binom{k-1}{t} M_k$
. (The infinite range of k is unproblematic because
$M_k = 0$
whenever
$k \gt n/2$
.) Then M is a pseudo-adjacency matrix of G if we identify
$\mathcal{X}$
and
$\bigl[ |\mathcal{X}| \bigr]$
.
For every integer k, denote by
$\bigl[x^k\bigr] f(x)$
the coefficient of the
$x^k$
term in the Laurent expansion of a meromorphic function f(x) in the
$|x| \gt 1$
region on the complex plane. For instance, we have the identity
$\binom{k-1}{t} = (\!-1)^{t+1} \bigl[x^{-2k}\bigr] \Bigl({1}/{(1-x^2)^{t+1}}\Bigr)$
because of
$\binom{-(t+1)}{k} = (\!-1)^k \binom{k+t}{t}$
and the expansion
\begin{align*}\frac{1}{(1-x^2)^{t+1}} = (\!-1)^{t+1} x^{-2(t+1)} (1 - x^{-2})^{-(t+1)} = (\!-1)^{t+1}x^{-2(t+1)} \sum_{k = 0}^\infty \binom{k+t}{t} x^{-2k}.\end{align*}
By Proposition 5·2,
$\boldsymbol{\nu}_S$
is an eigenvector of each
$M_k$
, so the eigenvalue of M with respect to it is
\begin{align*} \lambda_S &= \sum_{k \ge t+1} \Biggl( \binom{k-1}{t} \sum_{i=0}^{|S|}(\!-1)^{i}\binom{|S|}{i}\binom{n-|S|}{2k-i} \Biggr) \\ &= (\!-1)^{t+1} \sum_{k \ge t+1} \bigl[x^{-2k}\bigr] \biggl(\frac{1}{(1-x^2)^{t+1}}\biggr) \cdot \bigl[x^{2k}\bigr] \bigl( (1-x)^{|S|} (1+x)^{n-|S|} \bigr) \\ &= (\!-1)^{t+1} \bigl[x^0\bigr] \biggl( \frac{(1-x)^{|S|} (1+x)^{n-|S|}}{(1-x^2)^{t+1}} \biggr).\end{align*}
-
(1) If
$|S| \in \{t+1, \dots, n-t-1\}$
, then the denominator of
${(1-x)^{|S|} (1+x)^{n-|S|}} /{(1-x^2)^{t+1}}$
gets cancelled out and hence the quotient is a polynomial in x. So, the constant term is exactly the evaluation of the function at
$x = 0$
, which is 1. It follows that
$\lambda_S=(\!-1)^{t+1}$
. -
(2) If
$|S| \in \{1, \dots, t\}$
, then we compute
\begin{align*} \bigl[x^0\bigr] \frac{(1-x)^{|S|} (1+x)^{n-|S|}}{(1-x^2)^{t+1}} &= \bigl[x^0\bigr] \frac{(1+x)^{n-|S|-t-1}}{(1-x)^{t+1-|S|}} \\ &= \bigl[x^0\bigr] \biggl( (\!-1)^{t+1-|S|} \cdot \frac{1}{x^{t+1-|S|}} \cdot \frac{(1+x)^{n-|S|-t-1}}{(1-\frac{1}{x})^{t+1-|S|}} \biggr) \\ &= (\!-1)^{t+1-|S|} \bigl[x^{t+1-|S|}\bigr]\\ &\quad\times \biggl( (1+x)^{n-|S|-t-1} \Bigl(1+\frac{1}{x}+\cdots\Bigr)^{t+1-|S|} \biggr). \\[-60pt] \nonumber \end{align*}
It follows from
$n \ge 2t + 2$
that
$n - |S| - t - 1 \ge t + 1 - |S|$
. So, every coefficient is non-zero, and hence the sign of
$\lambda_S$
is
$(\!-1)^{t+1} \cdot (\!-1)^{t+1-|S|} = (\!-1)^{|S|}$
. -
(3) If
$|S| \in \{n-t, \dots, n\}$
, then
$\boldsymbol{\nu}_S = \mathbf{v}_{[n] \setminus S}$
(part of Proposition 5·2) implies that
$\lambda_S = \lambda_{[n] \setminus S}$
. It follows from the previous case that the sign of
$\lambda_S$
is
$(\!-1)^{n-|S|}$
.
According to Proposition 5·1,
-
(1) if t is even, then
$\alpha(G) \le n_{\ge 0}(M) = \binom{n}{0} + \binom{n}{2} + \cdots + \binom{n}{t}$
; -
(2) if t is odd, then
$\alpha(G) \le n_{\le 0}(M) = \binom{n}{1} + \binom{n}{3} + \cdots + \binom{n}{t}$
.
We thus conclude the proof of Theorem 1·4 by noticing that
$|\mathcal{F}| \le \alpha(G)$
.
6. Concluding remarks
In this paper, we determine
$f_D(n)$
asymptotically for all homogeneous arithmetic progress D. When D is non-homogeneous, Theorem 1·2 shows that
$f_D(n)$
grows linearly in n. We are unable to derive an asymptotically tight bound on
$f_D(n)$
. It remains an interesting problem to determine the leading coefficient here. We propose the following easier problem.
Question 6·1. Suppose D is a non-homogeneous arithmetic progression with
$\min(D) \ge 3$
. Is it true that for every sufficiently large n, we have
$f_D(n) \le (1-\varepsilon)n$
for some
$\varepsilon \gt 0$
?
One natural relaxation of the above question is to impose additional uniformity constraints on the family
$\mathcal{F}$
and make it an L-intersecting family for some L, where many well-developed methods and theories can be applied. A prototypical example of such a relaxed question is the following.
Question 6·2. Let
$p \ge 3$
be a prime with
$p \nmid r$
. Suppose
$\mathcal{F} \subseteq 2^{[n]}$
is a set family satisfying:
-
(i)
$|A| \equiv r \not\equiv 0 \pmod p$
holds for any
$A \in \mathcal{F}$
, and -
(ii)
$|A \cap B| \equiv 0 \pmod p$
holds for any pair of distinct
$A, B \in \mathcal{F}$
.
Is it true that there exists some
$\varepsilon \gt 0$
such that
$|\mathcal{F}| \le (1-\varepsilon)n$
all sufficiently large n?
In Question 6·2, the family
$\mathcal{F}$
is an
$\{2r, 2r+p, 2r+2p, \dots\}$
-distance family. When
$r = 1$
, this is evidently false as witnessed by all singletons in [n]. For a general r, Shengtong Zhang provided the following counterexample: let
$q \equiv r \pmod{p}$
be a sufficiently large prime (power) and consider the finite projective plane
$\operatorname{PG}(2, \mathbb{F}_q)$
. It contains
$q^2+q+1$
points,
$q^2+q+1$
lines (each of size
$q+1$
), where any two lines intersect in exactly one point. By adding
$p-1$
dummy points simultaneously into each line, one obtains an
$\{r \mod p\}$
-intersecting family of size
$q^2+q+1$
on
$[q^2+q+p]$
.
Nevertheless, this example does not refute Question 6·1, for the distance set
$D = \{2q\}$
therein grows with n. One may further hope that, if D is a fixed non-homogeneous arithmetic progression with
$\min D \ge 3$
, then
$f_D(n) \le {n}/{2}$
. However, the following shows that this is false when
$p = 3$
.
Example. There exists a 5-uniform
$\{0, 3\}$
-intersecting family on [n] of size
$5 \lfloor {n}/{9} \rfloor$
.
Proof. For
$i = 1, 2, \dots, \bigl\lfloor {n}/{9} \bigr\rfloor$
, write
$\widetilde{i} \stackrel{\text{def}}{\,=\,} 9(i-1)$
and consider
\begin{align*} \widetilde{i} + \{1,2,3,4,5\}, \, \widetilde{i} + \{1,2,3,6,7\}, \,\, \widetilde{i} + \{1,2,3,8,9\}, \,\, \widetilde{i} + \{1,2,4,6,8\}, \,\, \widetilde{i} + \{1,3,4,6,9\}. \end{align*}
Then the
$5 \bigl\lfloor {n}/{9} \bigr\rfloor$
many 5-element subsets from above form a
$\{0, 3\}$
-intersection family.
This construction shows that the lower bounds in Theorem 1·2 are not asymptotically correct for some specific D, notably
$D = \{4, 10\}$
. To be specific, it implies that
$f_{\{4, 10\}}(n) \ge 5 \bigl\lfloor {n}/{9} \bigr\rfloor$
.
Regarding Conjecture 1·3, our approach fails to deduce the first equality for all D. This is because in one of our tools, the Deza–Erdős–Frankl theorem (Theorem 3·4), one needs n to be at least exponential in the uniformity k. sec:exact in fact establishes a slightly stronger result than Theorem 1·4 exact that
$A(\mathcal{H}_n, D) \le A \bigl( \mathcal{H}_n, \{2, 4, \dots, 2t\} \bigr)$
holds for all D and large n with
$|D| = t$
and
$\max D \le {\log n}/{2}$
. Towards a complete resolution of Conjecture 1·3, we suspect that essential new ideas are required. In particular, when
$t = 1$
, the existence of an n-by-n Hadamard matrix implies that
$A \bigl( \mathcal{H}_n, \{2\} \bigr) = A \bigl( \mathcal{H}_n, \{{n}/{2}\} \bigr) = n$
. This shows that, in constrast to the case when n is sufficiently large compared to D, the set
$D_0 = \{2, 4, \dots, 2t\}$
is not necessarily a unique maximiser of
$A(\mathcal{H}_n, D)$
in general, and hence our proof cannot be easily adapted to resolve the conjecture.
Acknowledgments
We are grateful to Boris Bukh for bringing the Deza–Erdős–Frankl theorem to our attention. We also benefited from discussions with Andrey Kupavskii, Cosmin Pohoata, Wei-Hsuan Yu, and Shengtong Zhang. This work was initiated at the
$2{\text{nd}}$
ECOPRO Student Research Program in the summer of 2024. MO would like to thank ECOPRO for hosting. Part of this work was done during a visit of ZD and MO to Shandong University. They are thankful to Guanghui Wang for his support.
