Isodiametric inequality for vector spaces

Jiaqi Liao State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China & School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China. Emails: 9[email protected], [email protected]. Supported by National Key RD Program of China No. 2023YFA100960 Hong Liu Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic Science (IBS), Daejeon, South Korea. Emails: h[email protected]. Supported by Institute for Basic Science IBS-R029-C4. Guiying Yan¹¹footnotemark: 1

Abstract

A theorem of Kleitman states that a collection of binary vectors with diameter $d$ has cardinality at most that of a Hamming ball of radius $d/2$ . In this paper, we give a $q$ -analog of it.

1 Introduction

The classical isodiametric inequality in euclidean space states that the volume of a set with given diameter is maximized by euclidean balls. Analogues of isodiametric inequalities have been established in various settings. In the discrete setting, resolving a conjecture of Erdős, Kleitman [14] in 1966 famously proved an isodiametric inequality for Hamming space, the space of binary vectors equipped with Hamming distance. We shall state his result via graphs. Given a graph $G=(V,E)$ , let $\delta_{G}(\cdot,\cdot):V^{2}\rightarrow\mathbb{N}$ be the graph distance, i.e. the length of the shortest path between two vertices. For a subset $\mathcal{F}\subseteq V$ , its diameter is $\mathrm{diam}(\mathcal{F}):=\max_{a,b\in\mathcal{F}}\delta_{G}(a,b)$ . Note that $(V,\delta_{G})$ is a metric space. The Hamming graph on $[n]$ has vertex set $2^{[n]}$ and two vertices $A,B\in 2^{[n]}$ are adjacent if $A\subseteq B$ and $\left|B\right|-\left|A\right|=1$ . Kleitman’s theorem is an isodiametric inequality on Hamming graphs, which reads as follows.

Theorem 1.1 (Kleitman, [14]).

Let $n>d$ and $G$ be the Hamming graph on $[n]$ . Given $\mathcal{F}\subseteq V(G)$ , if $\mathrm{diam}(\mathcal{F})\leqslant d$ , then

\left|\mathcal{F}\right|\leqslant\left\{\begin{aligned} &\sum_{i=0}^{t}\binom{n}{i}&\qquad&\text{if }d=2t;\\ &\sum_{i=0}^{t}\binom{n}{i}+\binom{n-1}{t}&\qquad&\text{if }d=2t+1.\end{aligned}\right.

The bounds above are optimal. When $d=2t$ , consider the Hamming ball of radius $t$ , i.e. $\mathcal{F}=\sum_{i=0}^{t}\binom{[n]}{i}$ . When $d=2t+1$ , consider $\mathcal{F}=\sum_{i=0}^{t}\binom{[n]}{i}\cup\{A\in\binom{[n]}{t+1}:1\in A\}$ . The original proof of Kleitman is combinatorial (see also [2] or [8]). Recently, Huang, Klurman and Pohoata [12] gave a nice linear algebraic proof. Extensions of this theorem have been explored for the $n$ -dimensional grid $[m]^{n}$ using Hamming distance [3, 7], as well as for $[m]^{n}$ and the $n$ -dimensional torus $\mathbb{Z}_{m}^{n}$ with Manhattan distance [1, 4, 6]. We refer the readers to [5] more references and recent developments on Kleitman’s theorem.

In this paper, we give a $q$ -analog of Theorem 1.1. To state it, we need to generalize the Hamming graphs. Fix a prime power $q$ and let $V:=\mathbb{F}_{q}^{n}$ be the $n$ -dimensional vector space over $\mathbb{F}_{q}$ . Denote by $\mathcal{V}:=\left\{\text{subspaces of }\mathbb{F}_{q}^{n}\right\}$ and $\mathcal{V}(k):=\left\{A\in\mathcal{V}:\dim A=k\right\}$ . The gaussian binomial coefficients record the cardinality of $\mathcal{V}(k)$ : $\left|\mathcal{V}(k)\right|=\binom{n}{k}_{q}:=\frac{(q^{n}-1)\cdots(q^{n-k+1}-1)}{(q^{k}-1)\cdots(q-1)}.$ The $n$ -dimensional $q$ -Hamming graph has vertex set $\mathcal{V}$ , in which two subspaces $A$ and $B$ are joined by an edge if and only if $A\subseteq B$ and $\dim B-\dim A=1$ .

Our main result is an isodiametric inequality on $q$ -Hamming graphs for large $n$ .

Theorem 1.2.

Fix a prime power $q$ . Let $n=d+1$ or $n>2d$ and let $G$ be the $n$ -dimensional $q$ -Hamming graph. Given $\mathcal{F}\subseteq\mathcal{V}$ , if $\mathrm{diam}(\mathcal{F})\leqslant d$ , then

\left|\mathcal{F}\right|\leqslant\left\{\begin{aligned} &\sum_{i=0}^{t}\binom{n}{i}_{q}&\qquad&\text{if }d=2t;\\ &\sum_{i=0}^{t}\binom{n}{i}_{q}+\binom{n-1}{t}_{q}&\qquad&\text{if }d=2t+1.\end{aligned}\right.

The bounds on the size of $\mathcal{F}$ above are optimal. Indeed, set $\mathcal{F}_{1}=\bigcup_{k=0}^{t}\mathcal{V}(k)$ and $\mathcal{F}_{2}=\mathcal{F}_{1}\cup\left\{A\in\mathcal{V}(t+1):x\in A\right\}$ for some fixed $x\in V-\left\{0\right\}$ . Then $\mathcal{F}_{1}$ attains the maximum bound if $d=2t$ and $\mathcal{F}_{2}$ attains the maximum bound if $d=2t+1$ .

An equivalent formulation of Theorem 1.2 is an isodiametric inequality on a metric space $(\mathcal{V},\Delta)$ , see (2.1) and Lemma 2.4. We believe that the isodiametric inequality holds for all $n>d$ . It would be interesting to bridge the gap in Theorem 1.2 when $d+2\leq n\leq 2d$ .

2 Preliminaries

We need the following result on subspaces counting.

Lemma 2.1 ([11]).

Fix $A\in\mathcal{V}(k)$ . Then $\left|\left\{B\in\mathcal{V}(\ell):\dim(A\cap B)=j\right\}\right|=q^{(k-j)(\ell-j)}\binom{n-k}{\ell-j}_{q}\binom{k}{j}_{q}.$

Let $G$ be a finite bipartite graph with partite sets $X$ and $Y$ where $\left|X\right|=\left|Y\right|$ . A perfect matching is a set of disjoint edges which covers every vertex. For a subset $W\subseteq X$ (resp. $W\subseteq Y$ ), let $\Gamma(W)$ denote the set of all vertices in $Y$ (resp. $X$ ) that are adjacent to at least one vertex of $W$ . Hall’s theorem states that if for every subset $W\subseteq X$ , $\left|W\right|\leqslant\left|\Gamma(W)\right|$ , then $G$ has a perfect matching. We shall use the following folklore corollary. A regular graph is a graph where each vertex has the same number of neighbors.

Proposition 2.2.

Every finite regular bipartite graph has a perfect matching.

2.1 A metric space $(\mathcal{V},\Delta)$

For $A,B\in\mathcal{V}$ , define $\Delta:\mathcal{V}\times\mathcal{V}\rightarrow\mathbb{N}$ as

\Delta(A,B):=\dim(A+B)-\dim(A\cap B)=\dim A+\dim B-2\dim(A\cap B).

(2.1)

The symmetric positive-definite function $\Delta$ is a metric on $\mathcal{V}$ .

Lemma 2.3.

The function $\Delta$ satisfies the triangle inequality.

Proof.

Recall the dimension formula from linear algebra, we have

	$\displaystyle\Delta(A,C)$	$\displaystyle\leqslant\dim A+\dim C-2\dim(A\cap B\cap B\cap C)$
		$\displaystyle=\dim A+\dim C-2\dim(A\cap B)-2\dim(B\cap C)+2\dim((A\cap B)+(B\cap C))$
		$\displaystyle\leqslant\dim A+\dim C-2\dim(A\cap B)-2\dim(B\cap C)+2\dim B$
		$\displaystyle=\Delta(A,B)+\Delta(B,C).\qed$

The following lemma shows that Theorem 1.2 is equivalent to an isodiametric inequality on the metric space $(\mathcal{V},\Delta)$ .

Lemma 2.4.

Let $G$ be the $q$ -Hamming graph. Then $\delta_{G}=\Delta$ .

Proof.

Note that the union of an $A$ - $(A\cap B)$ path and and $(A\cap B)$ - $B$ path contains a path from $A$ to $B$ . Thus, $\delta_{G}(A,B)\leqslant\delta_{G}(A,A\cap B)+\delta_{G}(A\cap B,B)=\Delta(A,B)$ .

We shall prove the converse $\Delta(A,B)\leq\delta_{G}(A,B)$ by induction on $k=\delta_{G}(A,B)$ . The cases $k\in\left\{0,1\right\}$ are trivial. Suppose now that $\delta_{G}(A,B)=k\geq 2$ . Then there exists a vertex $C$ on the shortest path from $A$ to $B$ , such that $\delta_{G}(A,C)=1$ and $\delta_{G}(B,C)=k-1$ . By Lemma 2.3 and by the induction hypothesis, we have $\Delta(A,B)\leqslant\Delta(A,C)+\Delta(B,C)=\delta_{G}(A,C)+\delta_{G}(B,C)=k.$ ∎

For $\mathcal{F},\mathcal{G}\subseteq\mathcal{V}$ , we say $(\mathcal{F},\mathcal{G})$ is cross- $s$ -intersecting in $V$ if $\dim(A\cap B)\geqslant s$ for any $A\in\mathcal{F}$ and any $B\in\mathcal{G}$ . In particular, if $\mathcal{F}=\mathcal{G}$ , then $\mathcal{F}$ is $s$ -intersecting in $V$ .

The following lemma follows immediately from (2.1).

Lemma 2.5.

Let $\mathcal{F}\subseteq\mathcal{V}$ with $\mathrm{diam}(\mathcal{F})=d$ . Then $(\mathcal{F}(i),\mathcal{F}(j))$ is cross- $\lceil\left(i+j-d\right)/2\rceil$ -intersecting in $V$ for any $i,j\in\mathrm{supp}(\mathcal{F})$ . In particular, $\mathcal{F}(k)$ is $(k-\lfloor d/2\rfloor)$ -intersecting in $V$ for any $k\in\mathrm{supp}(\mathcal{F})$ .

Theorem 2.6 ([9]).

Let $n\geqslant 2k-s$ and $\mathcal{F}\subseteq\mathcal{V}(k)$ . If $\mathcal{F}$ is $s$ -intersecting in $V$ , then

\left|\mathcal{F}\right|\leqslant\max\left\{\binom{n-s}{k-s}_{q},\binom{2k-s}{k-s}_{q}\right\}.

2.2 An isometry

Recall that, given two metric spaces $(X_{1},d_{1})$ and $(X_{2},d_{2})$ , a bijection $f:X_{1}\rightarrow X_{2}$ is said to be an isometry if $d_{2}(f(x),f(y))=d_{1}(x,y)$ for any $x,y\in X_{1}$ . Next we show that taking orthogonal complement is an isometry on $(\mathcal{V},\Delta)$ . If $W$ is a subspace of $V$ , then its orthogonal complement $W^{\perp}$ is the subspace of $V$ consisting of all elements $v\in V$ such that $\langle v,w\rangle=0$ for all $w\in W$ , where $\langle v,w\rangle:=\sum\limits_{i=1}^{n}v_{i}\cdot w_{i}$ .

Lemma 2.7.

The bijection $f(U):=U^{\perp}$ is an isometry on $(\mathcal{V},\Delta)$ .

Proof.

Take arbitrary $U_{1},U_{2}\in\mathcal{V}$ . Note that

	$\displaystyle\Delta(U_{1}^{\perp},U_{2}^{\perp})$	$\displaystyle=\dim(U_{1}^{\perp}+U_{2}^{\perp})-\dim(U_{1}^{\perp}\cap U_{2}^{\perp})=\dim((U_{1}\cap U_{2})^{\perp})-\dim((U_{1}+U_{2})^{\perp})$
		$\displaystyle=n-\dim(U_{1}\cap U_{2})-n+\dim(U_{1}+U_{2})=\Delta(U_{1},U_{2}).\qed$

Given $\mathcal{F}\subseteq\mathcal{V}$ , denote by $\mathrm{diam}(\mathcal{F}):=\max_{A,B\in\mathcal{F}}\Delta(A,B)$ its diameter and

D(\mathcal{F}):=\max\limits_{A,B\in\mathcal{F}}\left|\dim A-\dim B\right|.

It follows from definition that $\left|\dim A-\dim B\right|\leqslant\Delta(A,B)$ , and so $D(\mathcal{F})\leqslant\mathrm{diam}(\mathcal{F})$ . We write $\mathcal{F}(i)\subseteq\mathcal{F}$ for the set of subspaces of dimension $i$ in $\mathcal{F}$ . Let $\mathrm{supp}(\mathcal{F}):=\left\{i\in\mathbb{N}:\mathcal{F}(i)\neq\varnothing\right\}$ and $\mathcal{F}^{\perp}:=\left\{W^{\perp}:W\in\mathcal{F}\right\}$ . If $\mathrm{diam}(\mathcal{F})=d$ , define

m_{\mathcal{F}}:=\min\left\{x\in\mathbb{N}:\mathrm{supp}(\mathcal{F})\subseteq[x,x+d]\quad\text{ or }\quad\mathrm{supp}(\mathcal{F}^{\perp})\subseteq[x,x+d]\right\}.

Lemma 2.8.

If $\mathrm{diam}(\mathcal{F})=d$ , then $m_{\mathcal{F}}\leqslant\left(n-d\right)/2$ .

Proof.

It suffices to show that, if $y:=\min\left\{x\in\mathbb{N}:\mathrm{supp}(\mathcal{F})\subseteq[x,x+d]\right\}>\left(n-d\right)/2,$ then we must have $\min\left\{x\in\mathbb{N}:\mathrm{supp}\left(\mathcal{F}^{\perp}\right)\subseteq[x,x+d]\right\}\leqslant(n-d)/2$ . But this follows from

\mathrm{supp}(\mathcal{F})\subseteq[y,y+d]\quad\Rightarrow\quad\mathrm{supp}(\mathcal{F}^{\perp})\subseteq[n-d-y,n-y],

where $n-d-y<n-d-(n-d)/2=\left(n-d\right)/2$ .∎

By Lemmas 2.7 and 2.8, we may assume that

m_{\mathcal{F}}=\min\left\{x\in\mathbb{N}:\mathrm{supp}(\mathcal{F})\subseteq[x,x+d]\right\}\leqslant\left(n-d\right)/2.

(2.2)

3 Proof of Theorem 1.2

Let us first consider the case $n=d+1$ . For each $k\leqslant n/2$ , define a bipartite graph $G_{k}:=\left(\mathcal{V}(k)\uplus\mathcal{V}(n-k),\mathcal{E}_{k}\right)$ , where

\mathcal{E}_{k}=\left\{\left\{A,B\right\}:A\in\mathcal{V}(k),B\in\mathcal{V}(n-k)\text{ and }\dim(A\cap B)=0\right\}.

By Lemma 2.1, we know that $G_{k}$ is ${q^{k(n-k)}}$ -regular. By Proposition 2.2, there is a perfect matching in $G_{k}$ . Note that if $\left\{A,B\right\}$ is an edge in $G_{k}$ , then $\Delta(A,B)>d$ . Thus for any $k\leqslant n/2$ , we have

\left|\mathcal{F}(k)\right|+\left|\mathcal{F}(n-k)\right|\leqslant\binom{n}{k}_{q}.

Hence, if $d=2t$ , we have

\left|\mathcal{F}\right|=\sum_{i=0}^{t}\left(\left|\mathcal{F}(i)\right|+\left|\mathcal{F}(n-i)\right|\right)\leqslant\sum_{i=0}^{t}\binom{n}{i}_{q}.

If $d=2t+1$ , then $\mathcal{F}(t+1)$ must be $1$ -intersecting in $V$ . By Theorem 2.6, we have $\left|\mathcal{F}(t+1)\right|\leqslant\binom{n-1}{t}_{q}$ . So

\left|\mathcal{F}\right|=\sum_{i=0}^{t}\left(\left|\mathcal{F}(i)\right|+\left|\mathcal{F}(n-i)\right|\right)+\left|\mathcal{F}(t+1)\right|\leqslant\sum_{i=0}^{t}\binom{n}{i}_{q}+\binom{n-1}{t}_{q}.

We may now assume $n>2d$ . The cases $d\in\left\{0,1\right\}$ are trivial; assume then $d\geq 2$ . Set $t:=\lfloor d/2\rfloor\geqslant 1$ . We shall bound the size of each layer of $\mathcal{F}$ . By Lemma 2.5, for any $k\in\mathrm{supp}(\mathcal{F})$ , $\mathcal{F}(k)$ is a $(k-t)$ -intersecting family. Hence by Theorem 2.6, we have

\left|\mathcal{F}(k)\right|\leqslant\max\left\{\binom{n-k+t}{t}_{q},\binom{k+t}{t}_{q}\right\}.

(3.1)

Let $m=m_{\mathcal{F}}$ . Then by (2.2), $m\leq\frac{n-d}{2}$ . Our strategy is to bound each of the slices $\mathcal{F}(k)$ . The cases when $d$ and $q$ are small require separate treatments.

3.1 The case $d=2$

In this case, we have $t:=\lfloor d/2\rfloor=1$ and $D(\mathcal{F})\leq d=2$ .

Suppose $D(\mathcal{F})=0$ , i.e., $\mathrm{supp}(\mathcal{F})=\left\{m\right\}$ . As $m\leq\frac{n-d}{2}$ , by (3.1) we have

\left|\mathcal{F}\right|=\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{n-m+1}{1}_{q},\binom{m+1}{1}_{q}\right\}=\binom{n-m+1}{1}_{q}\leqslant 1+\binom{n}{1}_{q},

(3.2)

as desired.

Suppose then $D(\mathcal{F})=1$ , i.e., $\mathrm{supp}(\mathcal{F})=\left\{m,m+1\right\}$ . By Lemma 2.5, we have $(\mathcal{F}(m),\mathcal{F}(m+1))$ is cross- $m$ -intersecting in $V$ . In other words, we have $X\subseteq Y$ for any $X\in\mathcal{F}(m)$ and any $Y\in\mathcal{F}(m+1)$ . By Lemma 2.5 again, we have $\mathcal{F}(m)$ is $(m-1)$ -intersecting in $Y$ for any $Y\in\mathcal{F}(m+1)$ .

Now, if $\left|\mathcal{F}(m+1)\right|=1$ , i.e., $\mathcal{F}(m+1)=\left\{Y\right\}$ for some $Y\in\mathcal{V}(m+1)$ , then by Theorem 2.6 with $V=Y$ , we have

\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{2}{1}_{q},\binom{m+1}{1}_{q}\right\}=\binom{m+1}{1}_{q}.

Thus, $\left|\mathcal{F}\right|\leqslant 1+\binom{m+1}{1}_{q}\leqslant 1+\binom{n}{1}_{q}$ .

If instead $\left|\mathcal{F}(m+1)\right|\geqslant 2$ , i.e., $\mathcal{F}(m+1)=\left\{Y_{1},Y_{2},\ldots\right\}$ . Set $Z:=Y_{1}\cap Y_{2}$ and thus $\dim Z\leqslant m$ . Hence $\left|\mathcal{F}(m)\right|\leqslant 1$ . On the other hand, by (3.1), we have

\left|\mathcal{F}(m+1)\right|\leqslant\max\left\{\binom{n-m}{1}_{q},\binom{m+2}{1}_{q}\right\}=\binom{n-m}{1}_{q}.

Thus, $\left|\mathcal{F}\right|\leqslant 1+\binom{n-m}{1}_{q}\leqslant 1+\binom{n}{1}_{q}$ .

Suppose $D(\mathcal{F})=2$ , i.e., $\mathrm{supp}(\mathcal{F})=\left\{m,m+1,m+2\right\}$ . By Lemma 2.5, we have $(\mathcal{F}(m),\mathcal{F}(m+2))$ is cross- $m$ -intersecting in $V$ and $(\mathcal{F}(m+1),\mathcal{F}(m+2))$ is cross- $(m+1)$ -intersecting in $V$ respectively. In other words, we have $X\subseteq Y$ for any $X\in\mathcal{F}(m)\cup\mathcal{F}(m+1)$ and any $Y\in\mathcal{F}(m+2)$ . By Lemma 2.5 again, we have $\mathcal{F}(m)$ is $(m-1)$ -intersecting in $Y$ for any $Y\in\mathcal{F}(m+2)$ and $\mathcal{F}(m+1)$ is $m$ -intersecting in $Y$ for any $Y\in\mathcal{F}(m+2)$ respectively.

If $\left|\mathcal{F}(m+2)\right|=1$ , say $\mathcal{F}(m+2)=\left\{Y\right\}$ , then By Theorem 2.6, we have

\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{3}{1}_{q},\binom{m+1}{1}_{q}\right\},

and

\left|\mathcal{F}(m+1)\right|\leqslant\max\left\{\binom{2}{1}_{q},\binom{m+2}{1}_{q}\right\}=\binom{m+2}{1}_{q}.

If instead $\left|\mathcal{F}(m+2)\right|\geqslant 2$ , i.e., $\mathcal{F}(m+2)=\left\{Y_{1},Y_{2},\ldots\right\}$ . Set $Z:=Y_{1}\cap Y_{2}$ and thus $\dim Z\leqslant m+1$ . Then $\left|\mathcal{F}(m+1)\right|\leqslant 1$ and by Theorem 2.6, we have

\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{2}{1}_{q},\binom{m+1}{1}_{q}\right\}=\binom{m+1}{1}_{q}.

By (3.1), we have

\left|\mathcal{F}(m+2)\right|\leqslant\max\left\{\binom{n-m-1}{1}_{q},\binom{m+3}{1}_{q}\right\}.

In each case, thanks to $\binom{n}{1}_{q}>\sum\limits_{i=1}^{n-1}\binom{i}{1}_{q}$ , we have

\left|\mathcal{F}\right|=\sum_{k\in\mathrm{supp}(\mathcal{F})}\left|\mathcal{F}(k)\right|\leqslant 1+\binom{n}{1}_{q}.

3.2 The case $d=3$

In this case, we have $t:=\lfloor d/2\rfloor=1$ and $D(\mathcal{F})\leq d=3$ .

If $D(\mathcal{F})=0$ , as in (3.2), we have

\left|\mathcal{F}\right|\leqslant\max\left\{\binom{n-m+1}{1}_{q},\binom{m+1}{1}_{q}\right\}=\binom{n-m+1}{1}_{q}\leqslant 1+\binom{n}{1}_{q}+\binom{n-1}{1}_{q}.

If $D(\mathcal{F})=1$ , i.e. $\mathrm{supp}(\mathcal{F})=\left\{m,m+1\right\}$ . By (3.1), we have

\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{n-m+1}{1}_{q},\binom{m+1}{1}_{q}\right\}=\binom{n-m+1}{1}_{q},

and

\left|\mathcal{F}(m+1)\right|\leqslant\max\left\{\binom{n-m}{1}_{q},\binom{m+2}{1}_{q}\right\}=\binom{n-m}{1}_{q}.

Thus, $\left|\mathcal{F}\right|\leqslant\binom{n-m+1}{1}_{q}+\binom{n-m}{1}_{q}\leqslant 1+\binom{n}{1}_{q}+\binom{n-1}{1}_{q}$ .

Suppose $D(\mathcal{F})=2$ , i.e., $\mathrm{supp}(\mathcal{F})=\left\{m,m+1,m+2\right\}$ . Then by Lemma 2.5, we have $(\mathcal{F}(m),\mathcal{F}(m+2))$ is cross- $m$ -intersecting in $V$ and $\mathcal{F}(m+1)$ is $m$ -intersecting in $V$ respectively. In other words, we have $X\subseteq Y$ for any $X\in\mathcal{F}(m)$ and any $Y\in\mathcal{F}(m+2)$ . By Lemma 2.5 again, we have $\mathcal{F}(m)$ is $(m-1)$ -intersecting in $Y$ for any $Y\in\mathcal{F}(m+2)$ . By (3.1),

\left|\mathcal{F}(m+1)\right|\leqslant\max\left\{\binom{n-m}{1}_{q},\binom{m+2}{1}_{q}\right\}=\binom{n-m}{1}_{q}.

If $\left|\mathcal{F}(m+2)\right|=1$ , say $\mathcal{F}(m+2)=\left\{Y\right\}$ , then by Theorem 2.6, we have

\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{3}{1}_{q},\binom{m+1}{1}_{q}\right\}.

If $\left|\mathcal{F}(m+2)\right|\geqslant 2$ , i.e., $\mathcal{F}(m+2)=\left\{Y_{1},Y_{2},\ldots\right\}$ . Set $Z:=Y_{1}\cap Y_{2}$ and thus $\dim Z\leqslant m+1$ . By Theorem 2.6 with $V_{\ref{EKRVEC}}=Z$ , we have

\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{2}{1}_{q},\binom{m+1}{1}_{q}\right\}=\binom{m+1}{1}_{q},

and by (3.1),

\left|\mathcal{F}(m+2)\right|\leqslant\max\left\{\binom{n-m-1}{1}_{q},\binom{m+3}{1}_{q}\right\}.

In each case, thanks to $\binom{n}{1}_{q}>\sum\limits_{i=1}^{n-1}\binom{i}{1}_{q}$ , we have

\left|\mathcal{F}\right|=\sum_{k\in\mathrm{supp}(\mathcal{F})}\left|\mathcal{F}(k)\right|\leqslant 1+\binom{n}{1}_{q}+\binom{n-1}{1}_{q}.

Suppose $D(\mathcal{F})=3$ , i.e., $\mathrm{supp}(\mathcal{F})=\left\{m,m+1,m+2,m+3\right\}$ . By Lemma 2.5, we have $(\mathcal{F}(m),\mathcal{F}(m+3))$ is cross- $m$ -intersecting in $V$ and $(\mathcal{F}(m+1),\mathcal{F}(m+3))$ is cross- $(m+1)$ -intersecting in $V$ respectively. In other words, we have $X\subseteq Y$ for any $X\in\mathcal{F}(m)\cup\mathcal{F}(m+1)$ and any $Y\in\mathcal{F}(m+3)$ . By Lemma 2.5 again, we have $\mathcal{F}(m)$ is $(m-1)$ -intersecting in $Y$ for any $Y\in\mathcal{F}(m+3)$ and $\mathcal{F}(m+1)$ is $m$ -intersecting in $Y$ for any $Y\in\mathcal{F}(m+3)$ respectively. By (3.1),

\left|\mathcal{F}(m+2)\right|\leqslant\max\left\{\binom{n-m-1}{1}_{q},\binom{m+3}{1}_{q}\right\}.

If $\left|\mathcal{F}(m+3)\right|=1$ , say $\mathcal{F}(m+3)=\left\{Y\right\}$ , then by Theorem 2.6 with $V_{\ref{EKRVEC}}=Y$ , we have

\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{4}{1}_{q},\binom{m+1}{1}_{q}\right\},

and

\left|\mathcal{F}(m+1)\right|\leqslant\max\left\{\binom{3}{1}_{q},\binom{m+2}{1}_{q}\right\}.

If $\left|\mathcal{F}(m+3)\right|\geqslant 2$ , i.e., $\mathcal{F}(m+3)=\left\{Y_{1},Y_{2},\ldots\right\}$ . Set $Z:=Y_{1}\cap Y_{2}$ , thus $\dim Z\leqslant m+2$ . By Theorem 2.6 with $V_{\ref{EKRVEC}}=Z$ , we have

\left|\mathcal{F}(m)\right|\leqslant\max\left\{\binom{3}{1}_{q},\binom{m+1}{1}_{q}\right\},

and

\left|\mathcal{F}(m+1)\right|\leqslant\max\left\{\binom{2}{1}_{q},\binom{m+2}{1}_{q}\right\}=\binom{m+2}{1}_{q},

and by (3.1),

\left|\mathcal{F}(m+3)\right|\leqslant\max\left\{\binom{n-m-2}{1}_{q},\binom{m+4}{1}_{q}\right\}.

In each case, thanks to $\binom{n}{1}_{q}>\sum\limits_{i=1}^{n-1}\binom{i}{1}_{q}$ , we have

\left|\mathcal{F}\right|=\sum_{k\in\mathrm{supp}(\mathcal{F})}\left|\mathcal{F}(k)\right|\leqslant 1+\binom{n}{1}_{q}+\binom{n-1}{1}_{q}.

3.3 The cases $d\geqslant 4$

In these cases, we have $t:=\lfloor d/2\rfloor\geqslant 2$ . Let us first assume that $m=m_{\mathcal{F}}\geqslant t+1$ . Note that $\left|\mathcal{F}\right|=\sum_{k=m}^{\lfloor n/2\rfloor}\left|\mathcal{F}(k)\right|+\sum_{k=\lfloor n/2\rfloor+1}^{m+d}\left|\mathcal{F}(k)\right|$ . For the first sum, by (3.1) and $m\geq t+1$ we have

$\displaystyle\binom{n}{t}_{q}^{-1}\cdot\sum_{k=m}^{\lfloor n/2\rfloor}\left\|\mathcal{F}(k)\right\|$	$\displaystyle\leqslant\sum_{k=m}^{\lfloor n/2\rfloor}\binom{n}{t}_{q}^{-1}\cdot\binom{n-k+t}{t}_{q}\leqslant\sum_{k=t+1}^{\infty}\binom{n}{t}_{q}^{-1}\cdot\binom{n-k+t}{t}_{q}$
	$\displaystyle=\sum_{k=t+1}^{\infty}\frac{(q^{n-k+t}-1)\cdots(q^{n-k+1}-1)}{(q^{n}-1)\cdots(q^{n-t+1}-1)}$
	$\displaystyle<\sum_{k=t+1}^{\infty}\frac{q^{n-k+t}\cdots q^{n-k+1}}{q^{n}\cdots q^{n-t+1}}<\sum_{r=1}^{\infty}q^{-tr}=\frac{1}{q^{t}-1}.$	(3.3)

For the second sum, recall that $m\leq\frac{n-d}{2}$ and so

	$\displaystyle\binom{n}{t}_{q}^{-1}\cdot\sum_{k=\lfloor n/2\rfloor+1}^{m+d}\left\|\mathcal{F}(k)\right\|$	$\displaystyle\leqslant\sum_{k=\lfloor n/2\rfloor+1}^{\lfloor(n-d)/2\rfloor+d}\binom{n}{t}_{q}^{-1}\cdot\binom{k+t}{t}_{q}=\sum_{k=\lfloor n/2\rfloor+1}^{\lfloor(n+d)/2\rfloor}\frac{(q^{k+t}-1)\cdots(q^{k+1}-1)}{(q^{n}-1)\cdots(q^{n-t+1}-1)}$
		$\displaystyle\leqslant\sum_{k=\lfloor n/2\rfloor+1}^{\lfloor(n+d)/2\rfloor}\frac{q^{k+t}\cdots q^{k+1}}{q^{n}\cdots q^{n-t+1}}<\sum_{r=1}^{\infty}q^{-tr}=\frac{1}{q^{t}-1},$		(3.4)

where the penultimate inequality follows from $\lfloor(n+d)/2\rfloor+t<n$ . Thus, $\left|\mathcal{F}\right|<\frac{2}{q^{t}-1}\cdot\binom{n}{t}_{q}$ .

We may then assume that $m=m_{\mathcal{F}}\leqslant t$ . Let $M=\max\mathrm{supp}(\mathcal{F})$ and further assume that

M\geqslant\left\{\begin{aligned} &t+1,&\qquad&\text{if }d=2t;\\ &t+2,&\qquad&\text{if }d=2t+1.\end{aligned}\right.

Then, we have

\left|\mathcal{F}\right|\leqslant\sum_{i=0}^{t-1}\binom{n}{i}_{q}+\left|\mathcal{F}(t)\right|+\sum_{k=t+1}^{M}\left|\mathcal{F}(k)\right|.

Let us first bound the size of $\mathcal{F}(t)$ . To this end, fix $Y\in\mathcal{F}(M)$ and note that for any $X\in\mathcal{F}(t)$ ,

\dim(X\cap Y)=\lceil\left(\dim X+\dim Y-\Delta(X,Y)\right)/2\rceil\geqslant\lceil\left(t+M-d\right)/2\rceil\geqslant 1.

Thus by Lemma 2.1, we have

\left|\mathcal{F}(t)\right|\leqslant\left|\{X\in\mathcal{V}(t):\dim(X\cap Y)\neq 0\}\right|=\binom{n}{t}_{q}-q^{Mt}\binom{n-M}{t}_{q}.

Note that

	$\displaystyle\frac{q^{Mt}\binom{n-M}{t}_{q}}{\binom{n}{t}_{q}}$	$\displaystyle=\frac{(q^{n}-q^{M})\cdots(q^{n-t+1}-q^{M})}{(q^{n}-1)\cdots(q^{n-t+1}-1)}\geqslant\frac{(q^{n}-q^{M})\cdots(q^{n-t+1}-q^{M})}{q^{n}\cdots q^{n-t+1}}$
		$\displaystyle=\prod_{i=1}^{t}\left(1-\left(q^{-1}\right)^{n-M-t+i}\right)\geqslant\prod_{i=1}^{t}\left(1-\left(q^{-1}\right)^{1+i}\right)\geqslant\prod_{i=1}^{t}\left(1-\left(2^{-1}\right)^{1+i}\right)$
		$\displaystyle\geqslant\left\{\begin{aligned} &\left(1-4^{-1}\right)\left(1-8^{-1}\right)=\frac{21}{32},&\qquad&\text{if }t=2;\\ &2\prod_{i=1}^{\infty}\left(1-\left(2^{-1}\right)^{i}\right)\geqslant\frac{1}{2},&\qquad&\text{if }t\geqslant 3.\end{aligned}\right.$

To see the last inequality $y:=\prod\limits_{i=1}^{\infty}\left(1-2^{-i}\right)\geqslant\frac{1}{4}$ , set $f(x)=\prod\limits_{i=1}^{\infty}\left(1-x^{i}\right)^{-1}$ where $x<2/3$ , it is the generating function of the partition function $p(k)$ , which is the number of distinct ways of representing $k$ as a sum of positive integers. Note that $p(k)\leqslant e^{\pi\sqrt{2k/3}}$ (see[15]) and $e^{\pi\sqrt{2k/3}}\leqslant(3/2)^{k}$ for $k\geqslant 41$ ; it can be verified (OEIS: A000041) that $p(k)\leqslant(3/2)^{k}$ for $1\leqslant k\leqslant 40$ . Thus, $f(x)=\sum\limits_{k=0}^{\infty}p(k)x^{k}\leqslant\sum\limits_{k=0}^{\infty}(3x/2)^{k}={2}/\left(2-3x\right)$ , and $y=1/f(\frac{1}{2})\geqslant 1/(\frac{2}{2-3/2})=1/4$ . Therefore, $\left|\mathcal{F}(t)\right|\leqslant c_{1}\binom{n}{t}_{q}$ , where $c_{1}=11/32$ if $t=2$ and $c_{1}=1/2$ if $t\geq 3$ .

To bound $\sum\limits_{k=t+1}^{M}\left|\mathcal{F}(k)\right|$ , if $\max\left\{q,t\right\}>2$ , then by (3.3) and (3.3) we have $\sum\limits_{k=t+1}^{M}\left|\mathcal{F}(k)\right|\leqslant\frac{2}{q^{t}-1}\binom{n}{t}_{q}\leqslant\frac{2}{7}\binom{n}{t}_{q}$ . If $q=t=2$ , then note that there are at most $5$ summands if $t=2$ since $M\leqslant t+d$ . In this case, based on the calculation in (3.3) and (3.3), $\binom{n}{t}_{q}^{-1}\cdot\sum\limits_{k=t+1}^{M}\left|\mathcal{F}(k)\right|\leqslant\sum\limits_{a\in A}a$ , where $A$ is a $5$ -term-subset of the multiset $\left\{1/4,1/4,1/16,1/16,1/64,1/64,1/256,1/256,\ldots\right\}$ , then $\sum\limits_{k=t+1}^{M}\left|\mathcal{F}(k)\right|\leqslant\frac{41}{64}\binom{n}{t}_{q}$ .

Put the upper bounds together, we have

	$\displaystyle\left\|\mathcal{F}\right\|$	$\displaystyle\leqslant\sum_{i=0}^{t-1}\binom{n}{i}_{q}+\left\|\mathcal{F}(t)\right\|+\sum_{k=t+1}^{M}\left\|\mathcal{F}(k)\right\|$
		$\displaystyle\leqslant\sum_{i=0}^{t-1}\binom{n}{i}_{q}+c_{1}\binom{n}{t}_{q}+c_{2}\binom{n}{t}_{q}$
		$\displaystyle<\sum_{i=0}^{t}\binom{n}{i}_{q}.$

where $(c_{1},c_{2})=\left(11/32,41/64\right)$ if $q=t=2$ , and $\left(1/2,2/7\right)$ if $\max\left\{q,t\right\}>2$ .

We are left with the case when

M\leqslant\left\{\begin{aligned} &t,&\qquad&\text{if }d=2t;\\ &t+1,&\qquad&\text{if }d=2t+1.\end{aligned}\right.

When $d=2t$ , $\left|\mathcal{F}\right|=\sum_{i\leqslant M}\left|\mathcal{F}(i)\right|\leq\sum_{i=0}^{t}\binom{n}{i}_{q}$ . When $d=2t+1$ , note that $\mathcal{F}(t+1)$ is $1$ -intersecting in $V$ if $d=2t+1$ , so $\left|\mathcal{F}(t+1)\right|\leqslant\binom{n-1}{t}_{q}$ by (3.1). Therefore $\left|\mathcal{F}\right|=\sum_{i\leqslant M}\left|\mathcal{F}(i)\right|\leq\sum_{i=0}^{t}\binom{n}{i}_{q}+\binom{n-1}{t}_{q}$ .

This completes the proof.

References

[1] R. Ahlswede, N. Cai, and Z. Zhang. Diametric theorems in sequence spaces. Combinatorica, 12(1):1–17, 1992.
[2] R. Ahlswede and G. O. H. Katona. Contributions to the geometry of Hamming spaces. Discrete Math., 17(1):1–22, 1977.
[3] R. Ahlswede and L. H. Khachatrian. The diametric theorem in Hamming spaces—optimal anticodes. Adv. in Appl. Math., 20(4):429–449, 1998.
[4] B. Bollobás and I. Leader. Maximal sets of given diameter in the grid and the torus. Discrete Math., 122(1-3):15–35, 1993.
[5] Z. Dong, J. Gao, H. Liu, M. Ouyang, and Q. Zhou. Optimal bounds for binary $t$ -codes and sets with restricted distances. Preprint.
[6] D. Z. Du and D. J. Kleitman. Diameter and radius in the Manhattan metric. Discrete Comput. Geom., 5(4):351–356, 1990.
[7] P. Frankl and Z. Füredi. The Erdős-Ko-Rado theorem for integer sequences. SIAM J. Algebraic Discrete Methods, 1(4):376–381, 1980.
[8] P. Frankl and N. Tokushige. Extremal problems for finite sets, volume 86 of Student Mathematical Library. American Mathematical Society, Providence, RI, 2018.
[9] P. Frankl and R. M. Wilson. The Erdős-Ko-Rado theorem for vector spaces. J. Combin. Theory Ser. A, 43(2):228–236, 1986.
[10] J. Gao, H. Liu, and Z. Xu. Stability through non-shadows. Combinatorica, 43(6):1125–1137, 2023.
[11] C. Godsil and K. Meagher. Erdős-Ko-Rado theorems: algebraic approaches, volume 149 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2016.
[12] H. Huang, O. Klurman, and C. Pohoata. On subsets of the hypercube with prescribed Hamming distances. J. Combin. Theory Ser. A, 171:105156, 21, 2020.
[13] G. Katona. Intersection theorems for systems of finite sets. Acta Math. Acad. Sci. Hungar., 15:329–337, 1964.
[14] D. J. Kleitman. On a combinatorial conjecture of Erdős. J. Combinatorial Theory, 1:209–214, 1966.
[15] W. d. A. Pribitkin. Simple upper bounds for partition functions. Ramanujan J., 18(1):113–119, 2009.

Isodiametric inequality for vector spaces

Abstract

1 Introduction

Theorem 1.1 (Kleitman, [14]).

Theorem 1.2.

2 Preliminaries

Lemma 2.1 ([11]).

Proposition 2.2.

2.1 A metric space (𝒱,Δ)(\mathcal{V},\Delta)

Lemma 2.3.

Proof.

Lemma 2.4.

Proof.

Lemma 2.5.

Theorem 2.6 ([9]).

2.2 An isometry

Lemma 2.7.

Proof.

Lemma 2.8.

Proof.

3 Proof of Theorem 1.2

3.1 The case d=2d=2

3.2 The case d=3d=3

3.3 The cases d⩾4d\geqslant 4

References

2.1 A metric space $(\mathcal{V},\Delta)$

3.1 The case $d=2$

3.2 The case $d=3$

3.3 The cases $d\geqslant 4$