1 Introduction
A t-\((v,k,\lambda )\) combinatorial design (or just combinatorial t-design) is a collection Y of k-subsets of a v-set V such that each t-subset of V lies in exactly \(\lambda \) members of Y. Teirlinck [16] obtained the celebrated result that nontrivial combinatorial t-designs exist for all t. It is well known that combinatorics of sets can be regarded as the limiting case \(q\rightarrow 1\) of combinatorics of vector spaces over a finite field \(\mathbb {F}_q\) with q elements. Following Delsarte [6] and Cameron [4], a t-\((v,k,\lambda )\) design over \(\mathbb {F}_q\) is a collection Y of k-dimensional subspaces (or k-spaces for short) of \(\mathbb {F}_q^v\) such that each t-dimensional subspace of \(\mathbb {F}_q^v\) lies in exactly \(\lambda \) members of Y. It was shown in [7] that nontrivial t-\((v,k,\lambda )\) designs over \(\mathbb {F}_q\) exist for all t and q if \(k>12(t+1)\) and v is sufficiently large enough. These designs can be seen as q-analogs of combinatorial designs of type \(A_{v-1}\) since \(\mathbb {F}_q^v\) together with the action of the general linear group \({{\,\textrm{GL}\,}}(v,q)\) is of this type.
We look at q-analogs of combinatorial designs in finite vector spaces of type \(^{2}{}{A}_{{2n-1}}\), \(^{2}{}{A}_{{2n}}\), \(B_n\), \(C_n\), \(D_n\), and \(^{2}{}{D}_{{n+1}}\) (using the notation of [5]). In all these cases, the space V is equipped with a nondegenerate form and the relevant groups are U(2n, q), \(U(2n+1,q)\), \(O(2n+1,q)\), Sp(2n, q), \(O^+(2n,q)\), and \(O^-(2n+2,q)\), respectively, where q is a square number in the case of \(^{2}{}{A}_{{2n-1}}\) and \(^{2}{}{A}_{{2n}}\). The chosen notation means that the maximal totally isotropic subspaces of V have dimension n (see Table 1). A finite classical polar space (or just polar space) of rank n is the collection of all totally isotropic subspaces with respect to a given form. We denote the polar spaces by the same symbol as the type of the underlying vector space. A t-\((n,k,\lambda )\) design in a polar space \(\mathcal {P}\) of rank n is a collection Y of k-dimensional totally isotropic subspaces of \(\mathcal {P}\) such that each t-dimensional totally isotropic subspace of \(\mathcal {P}\) lies in exactly \(\lambda \) members of Y.
Advertisement
A 1-(n, n, 1) design in a polar space is also known as a spread, whose existence question has been studied for decades, but is still not fully resolved (see [8, § 7.4] for the current status). In [14] (see also [17, § 3–4]), it was shown that nontrivial t-(n, n, 1) designs in polar spaces, also known as t-Steiner systems, do not exist except in some corner cases. According to [13, § 5.3], De Bruyn and Vanhove firstly announced the existence of a 2-\((3,3,\lambda )\) design with \(\lambda >1\) in the parabolic polar space \(B_3\) for \(q=3\) in conference presentations. Moreover, 2-\((3,3,\lambda )\) designs with \(\lambda >1\) in \(B_3\) for \(q=3,5,7,11\) were found in [13, § 5.3] (see also [2]). In [10], Kiermaier, Schmidt, and Wassermann found 2-\((n,k,\lambda )\) designs in various polar spaces of small rank n with \(2<k\le n\), \(\lambda >1\), and \(q=2,3\). No nontrivial t-\((n,k,\lambda )\) designs in polar spaces are presently known for \(k<n\) and \(t\ge 3\).
We prove the following existence result.
Theorem 1
Let \(\mathcal {P}\) be a polar space of rank n and let t and k be positive integers satisfying \(k>\frac{21}{2}t\) and \(n\ge ck^2\) for a large enough constant \(c>0\) independent of all other parameters. Then there exists a t-\((n,k,\lambda )\) design in \(\mathcal {P}\) of size at most \(q^{21nt}\).
We remark that the proof is nonconstructive and based on a probabilistic method developed by Kuperberg et al. [12]. This method cannot explicitly determine the smallest value of n that guarantees existence. We also note that this method is quite different to the probabilistic approach taken by Keevash et al. [9] to show the existence of designs over \(\mathbb {F}_q\). Namely, whereas their technique includes the case \(\lambda =1\), the KLP method requires \(\lambda \ge q^{Cnt}\) with \(C>0\) and thus excludes small values for \(\lambda \). So far, it is unknown whether [9] can also be applied to designs in polar spaces.
Advertisement
2 Polar spaces
In this section, we will shortly give some basic facts about polar spaces.
Let V be a vector space over a finite field with q elements equipped with a nondegenerate form f. A subspace U of V is called totally isotropic if \(f(u,w)=0\) for all \(u,w\in U\), or in the case of a quadratic form, if \(f(u)=0\) for all \(u\in U\). A finite classical polar space (or just polar space) with respect to a form f consists of all totally isotropic subspaces of V. It is well known that all maximal (with respect to the dimension) totally isotropic spaces in a polar space have the same dimension, which is called the rank of the polar space. A finite classical polar space \(\mathcal {P}\) of rank n has the parameter e if every \((n-1)\)-space in \(\mathcal {P}\) lies in exactly \((q^{e+1}+1)\) n-spaces of \(\mathcal {P}\). Up to isomorphism, there are exactly six finite classical polar spaces of rank n, which are listed together with their parameter e in Table 1. We note that q has to be a square number for the Hermitian polar spaces. For further background on polar spaces, we refer to [15, 3, § 9.4], and [1, § 4.2]. (We emphasize that in this paper, the term dimension is used in the usual sense as vector space dimension, not as projective dimension sometimes used by geometers.)
Table 1
List of all six finite classical polar spaces
Name | Form | Type | Group | \(\dim (V)\) | e |
|---|---|---|---|---|---|
Hermitian | Hermitian | \(^{2}{}{A}_{{2n-1}}\) | U(2n, q) | 2n | \(-1/2\) |
Hermitian | Hermitian | \(^{2}{}{A}_{2n}\) | \(U(2n+1,q)\) | \(2n+1\) | 1/2 |
Symplectic | Alternating | \(C_n\) | Sp(2n, q) | 2n | 0 |
Hyperbolic | Quadratic | \(D_n\) | \(O^+(2n,q)\) | 2n | \(-1\) |
Parabolic | Quadratic | \(B_n\) | \(O(2n+1,q)\) | \(2n+1\) | 0 |
Elliptic | Quadratic | \(^{2}{}{D}_{n+1}\) | \(O^-(2n+2,q)\) | \(2n+2\) | 1 |
We close this section by stating some well-known counting results that we later need, but first we define the q-binomial coefficient \(\genfrac[]{0.0pt}{}{{n}}{{k}}_q\) byfor nonnegative integers n, k.
$$\begin{aligned} \genfrac[]{0.0pt}{}{{n}}{{k}}_q=\prod _{j=1}^k \frac{q^{n-j+1}-1}{q^j-1} \end{aligned}$$
Lemma 2
([3, Lemmas 9.3.2, 9.4.1, 9.4.2])
(a)
The number of k-dimensional subspaces of an m-dimensional vector space over \(\mathbb {F}_q\) is given by \(\genfrac[]{0.0pt}{}{{m}}{{k}}_q\).
(b)
Let W be an m-dimensional vector space over \(\mathbb {F}_q\) and let V be a t-dimensional subspace of W. Then the number of k-dimensional subspaces U of W with \(V\subseteq U\subseteq W\) is given by \(\genfrac[]{0.0pt}{}{{m-t}}{{k-t}}_q\).
(c)
Let \(\mathcal {P}\) be a polar space of rank n. Then the number of k-spaces in \(\mathcal {P}\) is given by
$$\begin{aligned} \genfrac[]{0.0pt}{}{{n}}{{k}}_q \prod _{i=0}^{k-1} (q^{n-i+e}+1). \end{aligned}$$
(1)
(d)
Let \(\mathcal {P}\) be a polar space of rank n and let V be a t-space in \(\mathcal {P}\). Then the number of k-spaces U in \(\mathcal {P}\) with \(V\subseteq U\) is given by
$$\begin{aligned} \genfrac[]{0.0pt}{}{{n-t}}{{k-t}}_q\prod _{i=0}^{k-t-1} (q^{n-t-i+e}+1). \end{aligned}$$
(2)
3 The KLP theorem
In this section, we describe the main theorem of [12]. Let X be a finite set and let L be a \(\mathbb {Q}\)-linear subspace of functions \(f:X\rightarrow \mathbb {Q}\). We are interested in subsets Y of X satisfyingAn integer basis of L is a basis of L in which all elements are integer-valued functions. Let \(\{\phi _a\mid a\in A\}\) be an integer basis of L, where A is an index set. Then a subset Y of X satisfies (3) if and only ifThe KLP theorem guarantees the existence of small subsets Y of X with the property (4), once the vector space L satisfies the following five conditions (C1)–(C5). We can now state the KLP theorem.
$$\begin{aligned} \frac{1}{|Y|}\sum _{x\in Y} f(x)=\frac{1}{|X|}\sum _{x\in X} f(x)\quad \text {for all }f\in L. \end{aligned}$$
(3)
$$\begin{aligned} \frac{1}{|Y|}\sum _{x\in Y} \phi _a(x)=\frac{1}{|X|}\sum _{x\in X} \phi _a(x)\quad \text {for all }a\in A. \end{aligned}$$
(4)
(C1)
Constant Function. All constant functions belong to L, which means that every such function can be written as a rational linear combination of the basis functions \(\phi _a\) with \(a\in A\).
(C2)
Symmetry. A permutation \(\pi :X\rightarrow X\) is called a symmetry of L if \(\phi _a\circ \pi \) lies in L for all \(a\in A\). The set of symmetries of L forms a group called the symmetry group of L. The symmetry condition requires that the symmetry group of L acts transitively on X, which means that for all \(x_1,x_2\in X\), there exists a symmetry \(\pi \) such that \(x_1=\pi (x_2)\).
(C3)
Divisibility. There exists a positive integer \(c_1\) such that, for all \(a\in A\), there exists \(\alpha \in \mathbb {Z}^X\) (with \(\alpha =(\alpha _x)_{x\in X}\)) satisfying The smallest positive integer \(c_1\) for which this identity holds is called the divisibility constant of L.
$$\begin{aligned} \frac{c_1}{|X|}\sum _{x\in X} \phi _a(x)=\sum _{x\in X} \alpha _x \phi _a(x)\quad \hbox { for all}\ a\in A. \end{aligned}$$
(C4)
Boundedness of L. The \(\ell _\infty \)-norm of a function \(g:X\rightarrow \mathbb {Q}\) is given by The vector space L has to be bounded in the sense that there exists a positive integer \(c_2\) such that L has a \(c_2\)-bounded integer basis in \(\ell _\infty \).
$$\begin{aligned} \left\Vert g\right\Vert _\infty =\max _{x\in X} |g(x)|. \end{aligned}$$
(C5)
Boundedness of \(L^\perp \). The \(\ell _1\)-norm of a function \(g:X\rightarrow \mathbb {Q}\) is given by The orthogonal complement of L has to be bounded in the sense that \(L^\perp \) has a \(c_3\)-bounded integer basis in \(\ell _1\).
$$\begin{aligned} \left\Vert g\right\Vert _1=\sum _{x\in X} |g(x)|. \end{aligned}$$
$$\begin{aligned} L^\perp =\left\{ g:X\rightarrow \mathbb {Q}\;\Bigg \vert \;\sum _{x\in X} f(x)g(x)=0\;\text {for all }f\in L\right\} \end{aligned}$$
KLP theorem
([12, Theorem 2.4]) Let X be a finite set and let L be a \(\mathbb {Q}\)-linear subspace of functions \(f:X\rightarrow \mathbb {Q}\) satisfying the conditions (C1)–(C5) with the corresponding constants \(c_1,c_2,c_3\). Let N be an integral multiple of \(c_1\) withwhere \(C>0\) is a constant. Then there exists a subset Y of X of size \(|Y|=N\) such that
$$\begin{aligned} \min (N, |X|-N)\ge C\,c_2c_3^2 (\dim L)^6 \log (2c_3\dim L)^6, \end{aligned}$$
$$\begin{aligned} \frac{1}{|Y|}\sum _{x\in Y} f(x)=\frac{1}{|X|}\sum _{x\in X} f(x)\quad \text {for all }f\in L. \end{aligned}$$
We close this section with a useful criterion for the verification of (C5) from [12]. An integer basis \(\{\phi _a\mid a\in A\}\) of L is locally decodable with bound \(c_4\) if there exist functions \(\gamma _a:X\rightarrow \mathbb {Z}\) with \(\left\Vert \gamma _a\right\Vert _1\le c_4\) for all \(a\in A\) such thatfor some integer \(m\ge 1\) with \(|m|\le c_4\), where \(\delta _{a,a'}\) denotes the Kronecker \(\delta \)-function.
$$\begin{aligned} \sum _{x\in X}\gamma _a(x)\phi _{a'}(x)=m\delta _{a,a'}\quad \text {for all}\, a,a'\in A \end{aligned}$$
(5)
Lemma 3
([12, Claim 3.2]) Suppose that \(\{\phi _a\mid a\in A\}\) is a \(c_2\)-bounded integer basis in \(\ell _\infty \) of L that is locally decodable with bound \(c_4\). Then \(L^\perp \) has a \(c_3\)-bounded integer basis in \(\ell _1\) with \(c_3\le 2c_2c_4|A|\).
4 Proof of Theorem 1
In this section, we prove Theorem 1 using the KLP theorem. Not surprisingly, our proof proceeds along similar lines as the proof given in [7] for designs over finite fields. First, we put the definition of a design in a polar space in the framework of the KLP theorem by specifying the underlying vector space L. Then we show that L satisfies the required conditions (C1)–(C5) of the KLP theorem with suitable constants. This will establish the existence of nontrivial designs in polar spaces.
Let \(\mathcal {P}\) be a polar space of rank n and let t, k be positive integers with \(t\le k\le n\). In the following, we assume that \(t+k\le n\). Let X be the set of k-spaces in \(\mathcal {P}\) and let A be the set of t-spaces in \(\mathcal {P}\). For \(V\in A\), define \(\phi _V:X\rightarrow \mathbb {Q}\) byLet L be the \(\mathbb {Q}\)-span of \(\{\phi _V\mid V\in A\}\). Now, a subset Y of X satisfies (4) if and only iffor all \(V\in A\). Hence, (4) holds if and only if Y is a t-\((n,k,\lambda )\) design in \(\mathcal {P}\), wherefor all \(V\in A\).
$$\begin{aligned} \phi _V(U)={\left\{ \begin{array}{ll} 1&{}\text {if}\, V\subseteq U,\\ 0&{}\text {otherwise}. \end{array}\right. } \end{aligned}$$
$$\begin{aligned} \frac{1}{|Y|}\;|\{U\in Y\mid V\subseteq U\}|=\frac{1}{|X|}\;|\{U\in X\mid V\subseteq U\}| \end{aligned}$$
$$\begin{aligned} \lambda =\frac{|Y|}{|X|}\;|\{U\in X\mid V\subseteq U\}| \end{aligned}$$
4.1 Conditions (C1)–(C5)
In what follows, we will show that L satisfies the conditions (C1)–(C5) and establish the corresponding constants. Afterwards, we will deduce Theorem 1 from the KLP theorem.
4.1.1 (C1) Constant vector
For all \(U\in X\), we havesince every subspace of a totally isotropic space is again totally isotropic. This givesfor all \(U\in X\), and the space L thus contains the constant function.
$$\begin{aligned} \sum _{V\in A} \phi _V(U)=|\{V\in A\mid V\subseteq U\}|=\genfrac[]{0.0pt}{}{{k}}{{t}}_q \end{aligned}$$
$$\begin{aligned} \frac{1}{\genfrac[]{0.0pt}{}{{k}}{{t}}_q}\sum _{V\in A} \phi _V(U)=1 \end{aligned}$$
4.1.2 (C2) Symmetry
Let G be the group associated to \(\mathcal {P}\) as given in Table 1. The group G acts on X by mapping a k-space \(U=\langle u_1,\dots ,u_k\rangle \) via \(g\in G\) to \(g(U)=\langle g(u_1),\dots ,g(u_k)\rangle \). Similarly, G acts on A. We show that G is a subgroup of the symmetry group of L. For a given \(g\in G\), consider the permutation \(\sigma \) of A and the permutation \(\pi \) of X, both induced by g. Then, for all \(V\in A\) and all \(U\in X\), we haveHence, we obtain \((\phi _{\sigma (V)}\circ \pi ) (U)=\phi _{V}(U)\) for all \(U\in X\) giving \(\phi _{\sigma (V)}\circ \pi \in L\). Since \(\sigma \) is a permutation of A, we have \(\phi _V\circ \pi \in L\) for all \(V\in A\). Thus, the group G is a subgroup of the symmetry group of L. It is well known that G acts transitively on X, which establishes the symmetry condition.
$$\begin{aligned} (\phi _{\sigma (V)}\circ \pi ) (U) =\phi _{\sigma (V)} (\pi (U)) ={\left\{ \begin{array}{ll} 1&{}\text {if}\, \sigma (V)\subseteq \pi (U)\\ 0&{}\text {otherwise} \end{array}\right. } ={\left\{ \begin{array}{ll} 1&{}\text {if}\, V\subseteq U,\\ 0&{}\text {otherwise}. \end{array}\right. } \end{aligned}$$
4.1.3 (C4) Boundedness of L
The space L is spanned by the set \(\{\phi _V\mid V\in A\}\) consisting of integer-valued functions, which are 1-bounded in \(\ell _\infty \). Therefore, there exists a \(c_2\)-bounded integer basis of L with \(c_2=1\).
4.1.4 (C5) Boundedness of \(L^\perp \)
We will show that L has a locally decodable spanning set with bound \(c_4\). This is achieved by considering (5) as a linear system of equations with the unknowns \(\gamma _V(U)\) and showing that the system has a suitable integer solution. Together with Lemma 3, the local decodability then implies the required boundedness of \(L^\perp \).
Fix a t-space V in A and a \((k+t)\)-space W in \(\mathcal {P}\) with \(V\subset W\). Let \(\gamma _V:X\rightarrow \mathbb {Z}\) with \(\gamma _V(U)=0\) for all \(U\not \subset W\) andwhere m is a positive integer. We will see that \(\gamma _V(U)\) depends only on the dimension of \(U\cap V\). Therefore, we write \(f_{k,t}(\dim (U\cap V))=\gamma _V(U)\). Hence, (6) becomesFirst, for \(V'=V\), we obtainand thusSince every subspace of W is totally isotropic, the wanted number of k-spaces U is given by \(\genfrac[]{0.0pt}{}{{k+t-t}}{{k-t}}_q=\genfrac[]{0.0pt}{}{{k}}{{t}}_q\) due to Lemma 2 (b). Hence, we requireSecond, for every \(V'\in A\) with \(V'\ne V\), we wantwhich becomeswhere the sum is over all allowed U. Therefore, we only need to consider those \(V'\) that are contained in W.
$$\begin{aligned} \sum _{U\in X} \gamma _V(U)\phi _{V'}(U)=m\delta _{V,V'}\quad \text {for all}\, V'\in A, \end{aligned}$$
(6)
$$\begin{aligned} \sum _{\begin{array}{c} U\subset W\\ \dim (U)=k \end{array}} f_{k,t}(\dim (U\cap V)) \phi _{V'}(U)=m\delta _{V,V'}\quad \hbox { for all}\ V'\in A. \end{aligned}$$
$$\begin{aligned} \sum _{\begin{array}{c} U\subset W\\ \dim (U)=k \end{array}} f_{k,t}(\dim (U\cap V)) \phi _{V}(U)=m, \end{aligned}$$
$$\begin{aligned} f_{k,t}(t)\cdot |\{U\in \mathcal {P}\mid \dim (U)=k, V\subseteq U\subset W\}|=m. \end{aligned}$$
$$\begin{aligned} f_{k,t}(t)\genfrac[]{0.0pt}{}{{k}}{{t}}_q=m. \end{aligned}$$
(7)
$$\begin{aligned} \sum _{\begin{array}{c} U\subset W\\ \dim (U)=k \end{array}} f_{k,t}(\dim (U\cap V)) \phi _{V'}(U)=0, \end{aligned}$$
$$\begin{aligned} \sum _{\begin{array}{c} V'\subseteq U\subset W\\ \dim (U)=k \end{array}} f_{k,t}(\dim (U\cap V))=0, \end{aligned}$$
(8)
To further evaluate the sum (8), we apply the following lemma, which was proven for subspaces in a general vector space over a finite field in [7]. However the lemma also holds for subspaces in a polar space since W is totally isotropic and so are all its subspaces.
Lemma 4
([7, Lemma 5]) Let W be a \((k+t)\)-space in a polar space \(\mathcal {P}\) of rank n. Let V and \(V'\) be two distinct t-subspaces of W such that \(\dim (V\cap V')=\ell \) for some \(\ell \in \{0,1,\dots ,t-1\}\). Then the number of k-subspaces U of W such that \(V'\subseteq U\) and \(\dim (U\cap V)=j\) for some \(j\in \{\ell , \ell +1, \dots , t\}\) is given by
$$\begin{aligned} q^{(t-j)(k-t-j+\ell )}\genfrac[]{0.0pt}{}{{t-\ell }}{{j-\ell }}_q\genfrac[]{0.0pt}{}{{k+\ell -t}}{{j}}_q. \end{aligned}$$
By applying Lemma 4, we obtain from (8) thatwhere \(\ell =\dim (V\cap V')\). Combining (7) and (9) gives us a system of \(t+1\) linear equations. We represent this system as a matrix product of the formwhere \(f=(f_{k,t}(0),f_{k,t}(1),\dots ,f_{k,t}(t))^T\) and D is a \((t+1)\times (t+1)\) matrix with the entriesfor all \(\ell =0,1,\dots ,t\) and \(j=0,1,\dots ,t\). Since \(\genfrac[]{0.0pt}{}{{t-\ell }}{{j-\ell }}_q=0\) if \(\ell >j\), the matrix D is upper-triangular. Due to \(t\le k\), the main diagonal entries of D are all nonzero. Therefore, the determinant of D is nonzero and the system of linear equations is thus solvable. Applying Cramer’s rule giveswhere \(D_j\) is obtained from D by replacing the j-th column of D by \((0,\dots ,0,1)^T\). We can set \(m=\det (D)\) since the determinant of D is an integer. This gives \(f_{k,t}(j)=\det (D_j)\) and ensures that the coefficients \(f_{k,t}(0),f_{k,t}(1), \dots , f_{k,t}(t)\) are all integers, as required.
$$\begin{aligned} \sum _{j=\ell }^t f_{k,t}(j)\,q^{(t-j)(k-t-j+\ell )}\genfrac[]{0.0pt}{}{{t-\ell }}{{j-\ell }}_q\genfrac[]{0.0pt}{}{{k+\ell -t}}{{j}}_q=0\quad \text {for all}\, \ell =0,1,\dots ,t-1, \end{aligned}$$
(9)
$$\begin{aligned} Df=(0,\dots ,0,m)^T, \end{aligned}$$
$$\begin{aligned} d_{\ell ,j}=q^{(t-j)(k-t-j+\ell )}\genfrac[]{0.0pt}{}{{t-\ell }}{{j-\ell }}_q\genfrac[]{0.0pt}{}{{k+\ell -t}}{{j}}_q \end{aligned}$$
$$\begin{aligned} f_{k,t}(j)=\frac{\det (D_j)}{\det (D)} m, \end{aligned}$$
To derive a bound on the constant \(c_4\), we use \(c_4=\max \{m,\left\Vert \gamma _V\right\Vert _1\}\) and thus need to bound the determinants of D and \(D_j\). This was already done in [7].
Lemma 5
([7, Lemma 6]) Let D and \(D_j\) be defined as above for \(j=0,1,\dots ,t\). Then we have
$$\begin{aligned} |\det (D)|&\le q^{k(t+1)^2}, \end{aligned}$$
(10)
$$\begin{aligned} |\det (D_j)|&\le q^{k(t+1)^2}\quad \text {for all}\, j=0,1,\dots ,t. \end{aligned}$$
(11)
Since \(\gamma _V(U)=0\) if \(U\not \subset W\), we haveBy using \(|f_{k,t}(j)|=|\det (D_j)|\le q^{k(t+1)^2}\) due to (11) and the well-known bound(see [11, Lemma 4]), we obtainUsing \(m=\det (D)\) and (10), we deduceIn conclusion, we established the local decodability of the spanning set \(\{\phi _V\mid V\in A\}\) with bound \(c_4\). Moreover, by (1), we haveApplying (12) givesSince it holds that(see, e.g., [14, Lemma 3.6]), we obtainLemma 3 then implies the boundedness of \(L^\perp \) with
$$\begin{aligned} \left\Vert \gamma _V\right\Vert _1 = \sum _{U\in X} |\gamma _V(U)|\le |\{U\in X\mid U\subset W\}|\; \max _{U\in X} |\gamma _V(U)|=\genfrac[]{0.0pt}{}{{k+t}}{{k}}_q\max _j |f_{k,t}(j)|. \end{aligned}$$
$$\begin{aligned} \genfrac[]{0.0pt}{}{{n}}{{k}}_q\le 4 q^{k(n-k)} \end{aligned}$$
(12)
$$\begin{aligned} \left\Vert \gamma _V\right\Vert _1 \le \genfrac[]{0.0pt}{}{{k+t}}{{k}}_q q^{k(t+1)^2} \le 4 q^{kt+k(t+1)^2}. \end{aligned}$$
$$\begin{aligned} c_4=\max \{m,\left\Vert \gamma _V\right\Vert _1\}\le 4q^{kt+k(t+1)^2}. \end{aligned}$$
$$\begin{aligned} |A|=\genfrac[]{0.0pt}{}{{n}}{{t}}_q\prod _{i=0}^{t-1} (q^{n-i+e}+1). \end{aligned}$$
$$\begin{aligned} |A| \le 4 q^{(n+e)t-\left( {\begin{array}{c}t\\ 2\end{array}}\right) +t(n-t)}\prod _{i=0}^{t-1} \left( 1+\frac{1}{q^{n-i+e}}\right) . \end{aligned}$$
$$\begin{aligned} \prod _{i=0}^{t-1}\left( 1+\frac{1}{q^{n-i+e}}\right) <\frac{5}{2} \end{aligned}$$
$$\begin{aligned} |A|\le 10 q^{(n+e)t-\left( {\begin{array}{c}t\\ 2\end{array}}\right) +t(n-t)} \le 10 q^{2nt}. \end{aligned}$$
(13)
$$\begin{aligned} c_3\le 2c_2c_4|A|\le 80q^{2nt+kt+k(t+1)^2}. \end{aligned}$$
4.1.5 (C3) Divisibility
By using the local decodabilitywe can establish the divisibility condition in the following way. Since \(\mathbb {Z}^A\) is equipped with the standard basis \(\{e^V\mid V\in A\}\), where \(e_{V'}^V=\delta _{V,V'}\) for all \(V,V'\in A\), we obtainwith \(\phi (U)=(\phi _V(U))_{V\in A}\). This impliesMoreover by combining (1) and (2), we obtainHence, we haveTherefore, it holdsThus, there exists a positive integer \(c_1\) withsuch thatThe divisibility condition is therefore satisfied. Observe that \(c_1\le |\det (D)|\,|A|\). Hence, from Lemma 5 and (13), we find that
$$\begin{aligned} \sum _{U\in X} \gamma _V(U) \phi _{V'}(U)=m\delta _{V,V'}\quad \text {for all}\, V,V'\in A, \end{aligned}$$
$$\begin{aligned} \sum _{U\in X} \gamma _V(U) \phi (U)=me^V \end{aligned}$$
$$\begin{aligned} m\mathbb {Z}^A=\left\{ \sum _{U\in X} \alpha _U\, \phi (U) \;\Bigg \vert \; \alpha _U\in \mathbb {Z}\right\} . \end{aligned}$$
$$\begin{aligned} \frac{1}{|X|}\sum _{U\in X} \phi _V(U)=\frac{1}{|X|}\;|\{U\in X\mid V\subseteq U\}|=\frac{\genfrac[]{0.0pt}{}{{n-t}}{{k-t}}_q\prod \limits _{i=0}^{k-t-1} (q^{n-t-i+e}+1)}{\genfrac[]{0.0pt}{}{{n}}{{k}}_q\prod \nolimits _{i=0}^{k-1} (q^{n-i+e}+1)}. \end{aligned}$$
(14)
$$\begin{aligned} \frac{1}{|X|}\sum _{U\in X} \phi _V(U) =\frac{\genfrac[]{0.0pt}{}{{k}}{{t}}_q}{\genfrac[]{0.0pt}{}{{n}}{{t}}_q\prod \limits _{i=0}^{t-1}(q^{n-i+e}+1)}. \end{aligned}$$
$$\begin{aligned} \genfrac[]{0.0pt}{}{{n}}{{t}}_q\left( \prod \limits _{i=0}^{t-1}(q^{n-i+e}+1)\right) \frac{1}{|X|}\sum _{U\in X} \phi (U)=\genfrac[]{0.0pt}{}{{k}}{{t}}_q (1,\dots ,1). \end{aligned}$$
$$\begin{aligned} c_1\le m\genfrac[]{0.0pt}{}{{n}}{{t}}_q\prod \limits _{i=0}^{t-1}(q^{n-i+e}+1) \end{aligned}$$
$$\begin{aligned} \frac{c_1}{|X|}\sum _{U\in X} \phi (U)\in m\mathbb {Z}^A. \end{aligned}$$
$$\begin{aligned} c_1\le |\det (D)|\,|A|\le 10q^{2nt+k(t+1)^2}. \end{aligned}$$
4.2 Applying the KLP theorem
In the previous section, we have verified that the space L satisfies all conditions of the KLP theorem and obtained the following bounds on the constants:By (13), we also haveMoreover, due to standard lower bound \(\genfrac[]{0.0pt}{}{{n}}{{k}}_q\ge q^{k(n-k)}\) (see, e.g., [11, Lemma 4]), we obtainUsing (15) and (16), the lower bound on N in the KLP theorem is thus at mostfor some constants \(c,c'>0\). For fixed k and t, the right-hand side of (18) is bounded by \(cq^{21nt}\) if n is large enough, namely, if \(n\ge {\tilde{c}} k^2\) for a large enough constant \({\tilde{c}}>0\). Due to (17), the term \(cq^{21nt}\) is strictly less than |X| whenever \(k>\frac{21}{2}t\).
$$\begin{aligned} c_1\le 10 q^{2nt+k(t+1)^2},\quad c_2=1,\quad c_3\le 80q^{2nt+kt+k(t+1)^2}. \end{aligned}$$
(15)
$$\begin{aligned} \dim L\le |A|&\le 10 q^{2nt}. \end{aligned}$$
(16)
$$\begin{aligned} |X| =\genfrac[]{0.0pt}{}{{n}}{{k}}_q\prod _{i=0}^{k-1} (q^{n-i+e}+1) \ge q^{k(n-k)+k(n+e)-\left( {\begin{array}{c}k\\ 2\end{array}}\right) } \ge q^{2nk-\frac{3}{2} k^2}. \end{aligned}$$
(17)
$$\begin{aligned} c'c_2c_3^3 (\dim L)^7\le c q^{20nt+3kt+3k(t+1)^2} \end{aligned}$$
(18)
The KLP theorem now implies that for \(k>\frac{21}{2}t\) and \(n\ge {\tilde{c}} k^2\) with a large enough constant \({\tilde{c}}>0\), a t-\((n,k,\lambda )\) design in \(\mathcal {P}\) of size \(N\le q^{21nt}\) exists, which proves Theorem 1.
Declaration
Competing interests
The authors declare no competing interests.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
