On the maximum size of ultrametric orthogonal sets over discrete valued fields

Abstract

Let ${\mathcal {K}}$ be a discrete valued field with finite residue field. In analogy with orthogonality in the Euclidean space ${\mathbb {R}}^n$, there is a well-studied notion of “ultrametric orthogonality” in ${\mathcal {K}}^n$. In this paper, motivated by a question of Erdős in the real case, given integers $k \ge \ell \ge 2$, we investigate the maximum size of a subset $S \subseteq {\mathcal {K}}^n {\setminus }\{\textbf{0}\}$ satisfying the following property: for any $E \subseteq S$ of size k, there exists $F \subseteq E$ of size $\ell$ such that any two distinct vectors in F are orthogonal. Other variants of this property are also studied.

1 Introduction

Let ${\mathbb {R}}^n$ ($n \ge 2$) be the Euclidean space equipped with the classical scalar product ${\textbf{u}}\cdot {\textbf{v}}=\sum _{i=1}^nu_iv_i$; the vectors ${\textbf{u}}$ and ${\textbf{v}}$ are orthogonal if ${\textbf{u}}\cdot {\textbf{v}}=0$. It is well-known that the maximum size of a set $S \subseteq {\mathbb {R}}^n {\setminus }\{\textbf{0}\}$, such that any two distinct vectors of S are orthogonal is n. More generally, Erdős asked the following question.

Question 1.1

(Erdős) Let $k \ge \ell \ge 2$. We let $\alpha _n^{(k,\ell )}$ be the maximum size of a subset $S \subseteq {\mathbb {R}}^n \setminus \{\textbf{0}\}$ satisfying the following property: for any $E \subseteq S$ of size k, there exists $F \subseteq E$ of size $\ell$ such that any two distinct vectors in F are orthogonal. What is $\alpha _n^{(k,\ell )}$?

This question has attracted a lot of attention in the past decades (see for example [4, 7, 8, 13]). Note that the observation at the beginning can be reformulated as $\alpha _n^{(2,2)}=n$. In [8], Füredi and Stanley proved that $\alpha _2^{(k,2)}=2k-2$. Furthermore, Rosenfeld showed [13] that $\alpha _n^{(3,2)}=2n$, a result which was reproved by Deaett [7].

Given a finite field ${\mathbb {F}}_q$ where q is an odd prime power, Ahmadi and Mohammadian [1] investigated the analogue of the problem of Erdős in ${\mathbb {F}}_q^n$ ($n \ge 2$), equipped with a symmetric non-degenerate bilinear form. In this setting, they computed $\alpha _n^{(2,2)}$. Moreover, they provided an upper bound on $\alpha _n^{(3,2)}$. In [12], Mohammadian and Petridis improved this upper bound.

A positive characteristic analogue of ${\mathbb {R}}$ that is well-studied in geometry of numbers is the field ${\mathbb {F}}_q((x^{-1}))$ of Laurent series in $x^{-1}$ over a finite field ${\mathbb {F}}_q$ (see [2, 3, 10, 11, 14]). However, orthogonality with respect to bilinear forms on ${\mathbb {F}}_q((x^{-1}))^n$ are different. In this work, we consider the “ultrametric orthogonality” (see Definition 1.4), which makes sense in any ultrametric discrete valued field. This is inspired by the following property: in ${\mathbb {R}}^n$ equipped with the ${\mathcal {L}}_2$-norm, ${\textbf{u}},{\textbf{v}}\in {\mathbb {R}}^n$ are orthogonal if and only if, for every $a,b\in {\mathbb {R}}$, we have $\Vert a{\textbf{u}}+b{\textbf{v}}\Vert ^2_2=\Vert a{\textbf{u}}\Vert ^2_2+\Vert b{\textbf{v}}\Vert ^2_2$.

Now let ${\mathcal {K}}$ be a discrete valued field with valuation $\nu :{\mathcal {K}} \rightarrow {\mathbb {Z}} \cup \{0\}$. The sets

$$\begin{aligned} & {\mathfrak {m}}=\{ \lambda \in {\mathcal {K}} \mid \nu (\lambda )>0\},\\ & {\mathcal {O}}=\{ \lambda \in {\mathcal {K}} \mid \nu (\lambda ) \ge 0\}, \end{aligned}$$

and

$$\begin{aligned} \kappa ={\mathcal {O}}/{\mathfrak {m}} \end{aligned}$$

denote, respectively, the maximal ideal, the valuation ring and the residue field of ${\mathcal {K}}$. In the following, we assume that $\kappa$ is finite; for that let us suppose $\kappa ={\mathbb {F}}_q$ where q is a prime power. Here are some examples of discrete valued fields.

Example 1.2

• Let ${\mathcal {K}}={\mathbb {F}}_q((x^{-1}))$ (q a prime power) be the field of Laurent series in $x^{-1}$ and let $\nu$ be the valuation defined by $\nu (\sum _{i}a_ix^{-i})=\min (i \mid a_i\ne 0)$. In this case, ${\mathcal {O}}={\mathbb {F}}_q[[x^{-1}]]$, ${\mathfrak {m}}=x^{-1} {\mathcal {O}}$ and $\kappa ={\mathbb {F}}_q$.

• Let ${\mathcal {K}}={\mathbb {Q}}_p$ (p a prime number) be the field of p-adic numbers and let $\nu$ be the p-adic valuation. In this case, ${\mathcal {O}}={\mathbb {Z}}_p$, ${\mathfrak {m}}=p {\mathbb {Z}}_p$ and $\kappa ={\mathbb {F}}_p$.

On ${\mathcal {K}}$, we consider the utrametric absolute value defined by:

$$\begin{aligned} \left| \lambda \right| =q^{-\nu (\lambda )},\,\,\text {for all}\,\,\lambda \in {\mathcal {K}}. \end{aligned}$$

This gives rise to the infinity norm on ${\mathcal {K}}^n$ ($n \ge 1$) given by:

$$\begin{aligned} \Vert \textbf{v}\Vert =\max _{i \in [n]}\vert v_i\vert ,\,\, \text {for all}\,\, \textbf{v}=(v_1,\dots ,v_n) \in {\mathcal {K}}^n. \end{aligned}$$

Recall:

Lemma 1.3

(Ultrametric Inequality)

• (1) For any $\alpha _1,\dots ,\alpha _{\ell }\in {\mathcal {K}}$, we have

  $$\begin{aligned} \vert \alpha _1+\dots +\alpha _{\ell }\vert \le \max _{i \in [\ell ]}\vert \alpha _i\vert , \end{aligned}$$

  (1.1)

  where $[\ell ]=\{1,\dots ,\ell \}$. Moreover, if there exists $i_0$ such that $\vert \alpha _{i}\vert < \vert \alpha _{i_0}\vert$ for all $i \ne i_0$, then the inequality in (1.1) is an equality.

• (2) For any ${\textbf{u}}_1,\dots ,{\textbf{u}}_{\ell }\in {\mathcal {K}}^n$, we have

  $$\begin{aligned} \Vert {\textbf{u}}_1+\dots +{\textbf{u}}_{\ell }\Vert \le \max _{i \in [\ell ]}\Vert {\textbf{u}}_i\Vert . \end{aligned}$$

  (1.2)

  Moreover, if there exists $i_0$ such that $\Vert \textbf{u}_{i}\Vert < \Vert \textbf{u}_{i_0} \Vert$ for all $i \ne i_0$, then the inequality in (1.2) is an equality.

In the sequel, for two vector spaces U and V, we denote $U\le V$, whenever U is a subspace of V. The “ultrametric orthogonality” we consider is the following (see [10] and [14]).

Definition 1.4

• The vectors ${\textbf{u}}_1,\dots ,{\textbf{u}}_\ell \in {\mathcal {K}}^n {\setminus } \{\textbf{0}\}$ are orthogonal if

  $$\begin{aligned} \Vert \lambda _\ell {\textbf{u}}_1+\dots + \lambda _\ell {\textbf{u}}_\ell \Vert =\max _{i \in [\ell ]}\Vert \lambda _i \textbf{u}_i \Vert , \end{aligned}$$

  for all $\lambda _1,\dots ,\lambda _\ell \in {\mathcal {K}}$. In other words, every linear combination of ${\textbf{u}}_1,\dots ,{\textbf{u}}_\ell$ satisfies the equality case of the ultrametric inequality.

• The subspaces $U,V \le {\mathcal {K}}^n$ are orthogonal if ${\textbf{u}}$ and ${\textbf{v}}$ are orthogonal, for all $\textbf{u}\in U$ and $\textbf{v}\in V$.

• The subspaces $U, V \subseteq {\mathcal {K}}^n$ are feebly orthogonal if:

  • either there exists $\textbf{u} \in U \setminus \{\textbf{0}\}$ such that ${\mathcal {K}}\cdot \textbf{u}$ and V are orthogonal;

  • or there exists $\textbf{v} \in V \setminus \{\textbf{0}\}$ such that ${\mathcal {K}}\cdot \textbf{v}$ and U are orthogonal.

Remark 1.5

We can view feeble orthogonality as a weaker variant of orthogonality, in which one of the subspaces contains a vector which is orthogonal to all of the vectors in the other subspace.

The unit sphere in ${\mathcal {K}}^n$ is defined by ${\mathbb {B}}_n=\{\textbf{v}\in {\mathcal {K}}^n \mid \Vert \textbf{v}\Vert =1\}$, and the Grassmannian $\textrm{Gr}_{s,n}({\mathcal {K}})$ ($1 \le s \le n$) denotes the set of all s-dimensional subspaces of ${\mathcal {K}}^n$.

Definition 1.6

• A subset $S\subseteq {\mathcal {K}}^n \setminus \{\textbf{0}\}$ is weakly orthogonal if any two distinct vectors in S are orthogonal.

• A subset $S=\{\textbf{u}_1,\dots ,\textbf{u}_\ell \}\subseteq {\mathcal {K}}^n {\setminus } \{\textbf{0}\}$ is orthogonal if the vectors $\textbf{u}_1,\dots ,\textbf{u}_\ell$ are orthogonal in the sense of Definition 1.4.

• Let $s \ge 1$. A family ${\mathcal {F}} \subseteq \textrm{Gr}_{s,n}({\mathcal {K}})$ is feebly orthogonal if any two distinct subspaces in ${\mathcal {F}}$ are feebly orthogonal.

We can generalize Definition 1.6.

Definition 1.7

Let $k \ge \ell \ge 2$.

• A subset $S \subseteq {\mathcal {K}}^n \setminus \{\textbf{0}\}$ is $(k,\ell )$-weakly orthogonal if any $E \subseteq S$ of size k contains a weakly orthogonal subset $F \subseteq E$ of size $\ell$. We denote by $\Delta _{n}^{(k,\ell )}$ the maximum size of a $(k,\ell )$-weakly orthogonal set in ${\mathcal {K}}^n \setminus \{\textbf{0}\}$, that is,

  $$\begin{aligned} \Delta _{n}^{(k,\ell )}&=\max \{\vert S\vert \mid S \subseteq {\mathcal {K}}^n\setminus \{\textbf{0}\} \,\,\text {is}\,\, (k,\ell )\text {-weakly orthogonal}\}\\&=\max \{\vert S\vert \mid S \subseteq {\mathbb {B}}_n \,\,\text {is}\,\, (k,\ell )\text {-weakly orthogonal}\}. \end{aligned}$$

• A family ${\mathcal {F}} \subseteq \textrm{Gr}_{s,n}({\mathcal {K}})$ ($1 \le s \le n$) is $(k,\ell )$-feebly orthogonal if any ${\mathcal {E}} \subseteq {\mathcal {F}}$ of size k contains a feebly orthogonal subset ${\mathcal {R}} \subseteq {\mathcal {E}}$ of size $\ell$. We let

  $$\begin{aligned} \Omega _{s,n}^{(k,\ell )}&=\max \{\vert {\mathcal {F}}\vert \mid {\mathcal {F}} \subseteq \textrm{Gr}_{s,n}({\mathcal {K}})\,\,\text {is}\,\, (k,\ell )\text {-feebly orthogonal}\}. \end{aligned}$$

Remark 1.8

Note that orthogonality is invariant under scalar multiplication. Hence, we restrict to vectors in ${\mathbb {B}}_n$ in Definition 1.7.

In analogy with Question 1.1, it is natural to ask the following.

Question 1.9

Let $s \ge 1$ and let $k \ge \ell \ge 2$. What are $\Delta _{n}^{(k,\ell )}$ and $\Omega _{s,n}^{(k,\ell )}$?

The two theorems below answer Question 1.9.

Theorem 1.10

(Weakly orthogonal sets) Let $k \ge \ell \ge 2$. Then

$$\begin{aligned} \left\lfloor \frac{k-1}{\ell -1}\right\rfloor \frac{q^n-1}{q-1}\le \Delta _{n}^{(k,\ell )}\le \left\lfloor \frac{k-1}{\ell -1}\cdot \frac{q^n-1}{q-1}\right\rfloor ; \end{aligned}$$

(1.3)

more precisely,

$$\begin{aligned} \Delta ^{(k,\ell )}_{n}=\max \left\{ \left. \sum _{i=1}^{\frac{q^n-1}{q-1}}t_i\,\, \right| \sum _{i \in I}t_i \le k-1,\,\,\text {for all}\,\, I \subseteq \left[ \frac{q^n-1}{q-1}\right] \,\, \text {of size}\,\, \ell -1\right\} . \end{aligned}$$

(1.4)

As a consequence, if $\ell -1$ divides $k-1$, then $\Delta _{n}^{(k,\ell )}=\frac{k-1}{\ell -1}\cdot \frac{q^n-1}{q-1}$. In particular,

$$\begin{aligned} \Delta _{n}^{(k,2)}=(k-1)\frac{q^n-1}{q-1}. \end{aligned}$$

Corollary 1.11

Let $\ell \ge 2$. When $k \rightarrow \infty$, we have $\Delta _n^{(k,\ell )}\sim \frac{1}{\ell -1}\frac{q^n-1}{q-1} \cdot k$.

Theorem 1.12

(Feebly orthogonal spaces) Let $s \ge 1$ and let $k \ge \ell \ge 2$. Then

$$\begin{aligned} \left\lfloor \frac{k-1}{\ell -1}\right\rfloor {n \brack s}_{q}\le \Omega _{s,n}^{(k,\ell )}\le \left\lfloor \frac{k-1}{\ell -1}\cdot {n \brack s}_{q}\right\rfloor , \end{aligned}$$

(1.5)

where ${n \brack s}_{q}=\frac{(q^{n-s+1}-1)\cdots (q^2-1)(q-1)}{(q^s-1)\cdots (q^2-1)(q-1)}$; more precisely,

$$\begin{aligned} \Omega ^{(k,\ell )}_{s,n}=\max \left\{ \left. \sum _{i=1}^{{n \brack s}_{q}}t_i\,\,\right| \sum _{i \in I}t_i \le k-1,\,\,\text {for all}\,\, I \subseteq \left[ {n \brack s}_{q}\right] \,\, \text {of size}\,\, \ell -1\right\} . \end{aligned}$$

(1.6)

As a consequence, if $\ell -1$ divides $k-1$, then $\Omega _{s,n}^{(k,\ell )}=\frac{k-1}{\ell -1}\cdot {n \brack s}_{q}$. In particular, $\Omega _{s,n}^{(k,2)}=(k-1){n \brack s}_{q}$.

Corollary 1.13

Let $s \ge 1$ and let $\ell \ge 2$. When $k \rightarrow \infty$, we have $\Omega _{s,n}^{(k,\ell )}\sim \frac{1}{\ell -1}{n \brack s}_q \cdot k$.

Motivated by Definition 1.7, we also consider:

Definition 1.14

Let $k \ge \ell \ge 2$. A subset $S\subseteq {\mathcal {K}}^n{\setminus } \{\textbf{0}\}$ is $(k,\ell )$-orthogonal if any $E\subseteq S$ of size k contains an orthogonal subset $F \subseteq E$ of size $\ell$. We let

$$\begin{aligned} \Theta _{n}^{(k,\ell )}&=\max \{\vert S\vert \mid S \subseteq {\mathcal {K}}^n \setminus \{\textbf{0}\}\,\,\text {is}\,\,(k,\ell )\text {-orthogonal}\}\\&=\max \{\vert S\vert \mid S \subseteq {\mathbb {B}}_n\,\,\text {is}\,\,(k,\ell )\text {-orthogonal}\}. \end{aligned}$$

Question 1.15

Let $k \ge \ell \ge 2$. What is $\Theta _{n}^{(k,\ell )}$?

In order to estimate $\Theta _{n}^{(k,\ell )}$, our approach leads to analyze “independent sets” in ${\mathbb {F}}_q^n$; see [5, 6, 9, 15, 16].

Definition 1.16

Let $1 \le \ell \le k \le q^n-1$ with $\ell \le n$. A subset $S\subseteq {\mathbb {F}}_q^n \setminus \{\textbf{0}\}$ is $(k,\ell )$-independent if every subset $X\subseteq S$ of size k contains a linearly independent subset of size $\ell$, that is $\textrm{dim}(\langle S \rangle ) \ge \ell$. We let

$$\begin{aligned} \textrm{Ind}_q(n,k,\ell )=\max \{\vert S\vert \mid S \subseteq {\mathbb {F}}_q^n\setminus \{\textbf{0}\}\,\,\text {is}\,\,(k,\ell )\text {-independent}\}. \end{aligned}$$

Towards Question 1.15, we obtain partial results:

Theorem 1.17

(Orthogonal sets) Let $k \ge \ell \ge 2$.

• (1)
  $$\begin{aligned} \Theta _{n}^{(k,\ell )} \le \Delta _{n}^{(k,\ell )} \le \left\lfloor \frac{k-1}{\ell -1}\cdot \frac{q^n-1}{q-1}\right\rfloor . \end{aligned}$$

• (2) ${\text {Ind}}_{q}(n,k,\ell )\le \Theta _{n}^{(k,\ell )}$, with equality when $k=\ell$. Moreover, if the equality holds, then $k\le q^{\ell -2}+1$. As a consequence $\textrm{Ind}_{q}(n,k,2)=(k-1)\frac{q^n-1}{q-1}$, for all $2\le k \le q$.

• (3) $\left\lfloor \frac{k-1}{\ell -1}\right\rfloor \Theta _{n}^{(\ell ,\ell )} \le \Theta _{n}^{(k,\ell )}\le (k-\ell +1){\text {Ind}}_{q}(n,k,\ell )$.

• (4)
  $$\begin{aligned} \frac{q^n-1}{q^{\ell -1}-1} \le \limsup _{k\rightarrow \infty }\frac{\Theta _{n}^{(k,\ell )}}{k} \le q^{n}-1. \end{aligned}$$

• (5) $\Theta _{n}^{(\ell ,\ell )}<\Delta _{n}^{(\ell ,\ell )}$.

An interesting question is whether a $(k,\ell )$-orthogonal set must be weakly orthogonal. This motivates the following definition.

Definition 1.18

Let $k \ge \ell \ge 2$. A weakly orthogonal set $S\subseteq {\mathcal {K}}^n{\setminus } \{\textbf{0}\}$ is $(k,\ell )$-strongly orthogonal if, for any set $E\subseteq S$ of size k, there exists an orthogonal set $F \subseteq E$ of size $\ell$. We let

$$\begin{aligned}\Gamma _{n}^{(k,\ell )}&=\max \{\vert S\vert \mid S \subseteq {\mathcal {K}}^n \setminus \{\textbf{0}\}\,\,\text {is}\,\,(k,\ell )\text {-strongly orthogonal}\}\\&=\max \{\vert S\vert \mid S \subseteq {\mathbb {B}}_n\,\,\text {is}\,\,(k,\ell )\text {-strongly orthogonal}\}. \end{aligned}$$

Question 1.19

Let $k \ge \ell \ge 2$. What is $\Gamma _{n}^{(k,\ell )}$?

To investigate $\Gamma _{n}^{(k,\ell )}$, we also need to study “independent sets” in ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)=({\mathbb {F}}_q^n{\setminus }\{\textbf{0}\})/{\mathbb {F}}_q^*$.

Definition 1.20

Let $1 \le \ell \le k \le \frac{q^n-1}{q-1}$ with $\ell \le n$. A subset $S\subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ is $(k,\ell )$-pro-independent if any subset $X\subseteq S$ of size k contains a linearly independent subset of size $\ell$, that is $\textrm{dim}(\langle S \rangle ) \ge \ell$. We let

$$\begin{aligned} \textrm{Ind}_q^{{\text {pro}}}(n,k,\ell )=\max \{\vert S\vert \mid S \subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)\,\,\text {is}\,\,(k,\ell )\text {-pro-independent}\}. \end{aligned}$$

Remark 1.21

When $q=2$, we have ${\mathbb {P}}^{n-1}({\mathbb {F}}_2)={\mathbb {F}}_2^n$, so ${\text {Ind}}_2^{{\text {pro}}}(n,k,\ell )={\text {Ind}}_2(n,k,\ell )$.

Concerning Question 1.19, we get:

Theorem 1.22

(Strongly orthogonal sets) Let $k \ge \ell \ge 2$. Then $\Gamma _{n}^{(k,\ell )}=\textrm{Ind}^{\textrm{pro}}_q(n,k,\ell )$.

Of independent interest, we also investigate some questions regarding independent sets in ${\mathbb {F}}_q^n$ and ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$:

Theorem 1.23

• (1) Independent sets in ${\mathbb {F}}_q^n$ . Let $2 \le \ell \le k \le q^n-1$ with $\ell \le n$. Then:

  • (a) ${\text {Ind}}_q(n,k,\ell )=q^{n}-1$ if and only if $k\ge q^{\ell -1}$. In other words, ${\mathbb {F}}_q^{n}{\setminus } \{\textbf{0}\}$ is $(k,\ell )$-independent if and only if $k\ge q^{\ell -1}$;

  • (b) the sequence $\{\textrm{Ind}_q(n,k,\ell )\}_{k=\ell }^{q^{\ell -1}}$ is strictly increasing in k;

  • (c)
    $$\begin{aligned} q^n-1=\textrm{Ind}_q(n,k,1) =\dots =\textrm{Ind}_q(n,k,\lfloor \log _q(k) \rfloor +1)> \dots > \textrm{Ind}_q(n,k,k)\ge n+1. \end{aligned}$$

• (2) Independent sets in ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ . Let $2 \le \ell \le k \le \frac{q^n-1}{q-1}$ with $\ell \le n$. Then:

  • (a) ${\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )=\frac{q^n-1}{q-1}$ if and only if $k\ge \frac{q^{\ell -1}-1}{q-1}$. In other words, ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ is $(k,\ell )$-pro-independent if and only if $k\ge \frac{q^{\ell -1}-1}{q-1}$;

  • (b) the sequence $\{{\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )\}_{k=\ell }^{\frac{q^{\ell -1}-1}{q-1}}$ is strictly increasing in k;

  • (c) moreover,

    $$\begin{aligned} & \frac{q^n-1}{q-1}=\textrm{Ind}^{{\text {pro}}}_q(n,k,1)= \dots =\textrm{Ind}^{\textrm{pro}}_{q}(n,k,\lfloor \log _q((q-1)k+1)\rfloor +1)> \dots > \\ & \quad \textrm{Ind}^{{\text {pro}}}_q(n,k,k)\ge n+1. \end{aligned}$$

• (3) Independent sets in ${\mathbb {F}}_q^n$ vs independent sets in ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ . Let $2 \le \ell \le k \le \frac{q^n-1}{q-1}$ with $\ell \le n$. Then:

  • (a) $\textrm{Ind}_q^{\textrm{pro}}(n,k,\ell ) \le \textrm{Ind}_q(n,k,\ell )$, with equality when $k=\ell$;

  • (b) $\left\lceil \llceil \frac{1}{q-1}{\text {Ind}}_q(n,k,\ell )\right\rceil \rrceil \le {\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )\le \left\lfloor \frac{1}{q-1}{\text {Ind}}_q(n,(q-1)k,\ell )\right\rfloor .$ Moreover, if $k\le \frac{q^{\ell -1}-1}{q-1}$, then $\textrm{Ind}_q(n,k,\ell )=(q-1)\textrm{Ind}^{\textrm{pro}}_q(n,k,\ell )$ if and only if $q=2$.

This paper is organized as follows. In Sect. 2, we investigate independent sets in ${\mathbb {F}}_q^n$ and ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$; in particular we prove Theorem 1.23. Section 3 is devoted to orthogonality in ${\mathcal {K}}^n$:

• Weakly orthogonal sets and feebly orthogonal spaces: Theorems 1.10 and 1.12 are proved in §3.1.

• Orthogonal sets: Theorem 1.17 is proved in §3.2.

• Strongly orthogonal sets: Theorem 1.22 is proved in §3.3.

2 Independent sets in ${\mathbb {F}}_q^n$ and ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$

In this section, we deal with independent sets in ${\mathbb {F}}_q^n$ and ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$. In particular, we prove Theorem 1.23. Let ${\mathbb {F}}_q$ be a finite field and let $n\ge 1$ be an integer.

Notations:

• For $m \ge 1$, we let $[m]=\{1,\dots ,m\}$.

• For $\textbf{v}=(v_1,\dots ,v_n) \in {\mathbb {F}}_q^n$, let $\textrm{supp}(\textbf{v})=\{i\in [n] \mid v_i \ne 0\}$.

• Let $s \in [n]$. The Grassmannian $\textrm{Gr}_{s,n}({\mathbb {F}}_q)$ denotes the space of all s-dimensional subspaces of ${\mathbb {F}}_q^n$; the size of $\textrm{Gr}_{s,n}({\mathbb {F}}_q)$ is given by the q-binomial ${n \brack s}_q=\frac{(q^{n-s+1}-1)\dots (q^2-1)(q-1)}{(q^s-1)\dots (q^2-1)(q-1)}$.

• Let $\rho _n:{\mathbb {F}}_q^n{\setminus } \{\textbf{0}\}\rightarrow {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ be the natural projection.

2.1 Independent sets in ${\mathbb {F}}_q^n$

In this part, we establish some properties of $\textrm{Ind}_q(n,k,\ell )$. In [5] and [6], Damelin, Michalski, Müllen and Stone investigated $\textrm{Ind}_q(n,k,\ell )$ when $k=\ell$. Independently, Tassa and Villar [16] also studied $\textrm{Ind}_q(n,k,\ell )$. In finite geometry, similar concepts closely related to the $(k,\ell )$-(pro-)independence have been also investigated earlier (see the survey [9] of Hirschfeld); for example, given $1 \le k \le n$, Tallini [15] studied the maximum size of $S \subset {\mathbb {F}}_q^n$ such that any $X \subset S$ of size k is ${\mathbb {F}}_q$-linearly independent, but not all $X' \subset S$ of size $k+1$ is ${\mathbb {F}}_q$-linearly independent.

Theorem 2.1

(Theorem 2 in [5])

• (1) For every $n\ge 3$, we have $\textrm{Ind}_2(n,3,3)=2^{n-1}$.

• (2) For every $m\ge 0$ and $n\ge 3\,m+2$, we have $\textrm{Ind}_2(n,n-m,n-m)=n+1$.

• (3) For every $m\ge 2$, $i\in \{0,1\}$ and $n=3\,m+i$, we have $\textrm{Ind}_2(n,n-m,n-m)=n+2$.

Theorem 2.2

(Theorem 2 in [6]) Let $2 \le \ell \le n$. Then ${\text {Ind}}_q(n,\ell ,\ell )=n+1$ if and only if $\frac{q}{q+1}(n+1)\le \ell$.

Proposition 2.3

(Theorem 1.23 (1a)) Let $2 \le \ell \le k \le q^n-1$ with $\ell \le n$. Then ${\text {Ind}}_q(n,k,\ell )=q^{n}-1$ if and only if $k\ge q^{\ell -1}$. In other words, ${\mathbb {F}}_q^{n}{\setminus } \{\textbf{0}\}$ is $(k,\ell )$-independent if and only if $k\ge q^{\ell -1}$.

Proof

First assume that $k< q^{\ell -1}$. Let us consider an $\ell -1$-dimensional subspace $V \le {\mathbb {F}}_q^n$. Since $\vert V {\setminus } \{\textbf{0}\}\vert = q^{\ell -1}-1\ge k$ and $\textrm{dim}(\langle V{\setminus } \{\textbf{0}\} \rangle ) < \ell$, the set ${\mathbb {F}}_q^n{\setminus }\{{\varvec{0}}\}$ is not $(k,\ell )$-independent.

Now assume that $k \ge q^{\ell -1}$. Let $S\subseteq {\mathbb {F}}_q^n{\setminus }\{\textbf{0}\}$ be a subset of size k. Since $\vert S\cup \{\textbf{0}\}\vert =k+1> q^{\ell -1}$, we have $\textrm{dim}(\langle S\rangle ) \ge \ell$. Hence ${\mathbb {F}}_q^n\setminus \{\textbf{0}\}$ is $(k,\ell )$-independent.

This completes the proof. $\square$

Corollary 2.4

For $k \ge 3$,

$$\begin{aligned} \textrm{Ind}_2(n,k,3)= {\left\{ \begin{array}{ll} 2^{n-1} & \text {if}\,\, k=3,\\ 2^n-1 & \text {if}\,\, k \ge 4. \end{array}\right. } \end{aligned}$$

Proof

This follows from Theorem 2.1 (1) and Proposition 2.3. $\square$

Proposition 2.5

(Theorem 1.23 (1b) and (1c))

• (1) Let $2 \le \ell \le n$. Then the sequence $\{\textrm{Ind}_q(n,k,\ell )\}_{k=\ell }^{q^{\ell -1}}$ is strictly increasing in k.

• (2) Let $2 \le k \le q^n-1$. Then

  $$\begin{aligned} q^n-1=\textrm{Ind}_q(n,k,1) =\dots =\textrm{Ind}_q(n,k,\lfloor \log _q(k) \rfloor +1)> \dots > \textrm{Ind}_q(n,k,k)\ge n+1. \end{aligned}$$

Proof

• (1) First, note that by Proposition 2.3, $\textrm{Ind}_q(n,k,q^{\ell -1}-1)< \textrm{Ind}_q(n,k,q^{\ell -1})=q^n-1$. Also, $\{\textrm{Ind}_q(n,k,\ell )\}_{k=\ell }^{q^{\ell -1}}$ is weakly increasing. Assume on the contrary that it is not strictly increasing, that is, ${\text {Ind}}_q(n,k,\ell )={\text {Ind}}_q(n,k+1,\ell )$ for some $\ell \le k \le q^{\ell -1}-2$. Let us consider a $(k,\ell )$-independent set $S \subseteq {\mathbb {F}}_q^n{\setminus }\{\textbf{0}\}$ of maximum size, and let ${\textbf{v}}\in {\mathbb {F}}_q^n\setminus (S\cup \{\textbf{0}\})$.

Claim

The set $S\cup \{{\textbf{v}}\}$ is $(k+1,\ell )$-independent.

Proof of the claim

Let $X\subseteq S\cup \{{\textbf{v}}\}$ be of size $k+1$. Since $\vert S \cap X\vert \ge k$, by the $(k,\ell )$-independence of S, the set $S \cap X$ contains an independent set of size $\ell$. Hence $S\cup \{{\textbf{v}}\}$ is $(k+1,\ell )$-independent, which completes the proof of the claim. $\square$

Therefore ${\text {Ind}}_q(n,k+1,\ell )\ge \vert S\vert +1>{\text {Ind}}_q(n,k,\ell )$, a contradiction. Consequently $\{\textrm{Ind}_q(n,k,\ell )\}_{k=\ell }^{q^{\ell -1}}$ is strictly increasing.

• (2) Clearly $\{\textrm{Ind}_q(n,k,\ell )\}_{\ell =1}^k$ is weakly decreasing in $\ell$. By Proposition 2.3, we have

  $$\begin{aligned} q^n-1=\textrm{Ind}_q(n,k,1) =\dots =\textrm{Ind}_q(n,k,\lfloor \log _q(k)\rfloor +1) \end{aligned}$$

  and

  $$\begin{aligned} \textrm{Ind}_q(n,k,\lfloor \log _q(k)\rfloor +1)> \textrm{Ind}_q(n,k,\lfloor \log _q(k)\rfloor +2). \end{aligned}$$

  Assume on the contrary that $\textrm{Ind}_q(n,k,\ell )=\textrm{Ind}_q(n,k,\ell +1)$ for some $\lfloor \log _q(k)\rfloor +2 \le \ell \le k-1$. Note that $\textrm{Ind}_q(n,k,\ell )<q^n-1$. Now let us consider a $(k,\ell +1)$-independent set S of maximum size, and let ${\textbf{v}}\in {\mathbb {F}}_q^n\setminus (S\cup \{\textbf{0}\})$.

Claim

The set $S\cup \{{\textbf{v}}\}$ is $(k,\ell )$-independent.

Proof of the claim

Let $X\subseteq S\cup \{{\textbf{v}}\}$ be of size k. If $X \subseteq S$, then, by the $(k,\ell +1)$-independence of S, the set X contains an independent set of size $\ell$. We may then assume that $X \not \subset S$. Let us choose $\textbf{u} \in S \setminus X$, which exists because $\vert S\vert \ge k$. Since $\vert (X\cap S) \cup \{\textbf{u}\}\vert \ge k$, by the $(k,\ell +1)$-independence of S, the set $(X\cap S)\cup \{\textbf{u}\}$ contains an independent set of size $\ell +1$. Hence X contains an independent set of size $\ell$. This implies that $S\cup \{{\textbf{v}}\}$ is $(k,\ell )$-independent. $\square$

Therefore $\textrm{Ind}_q(n,k,\ell )\ge \vert S\vert +1 > \textrm{Ind}_q(n,k,\ell +1)$, a contradiction. Consequently

$$\begin{aligned} q^n-1=\textrm{Ind}_q(n,k,1) =\dots =\textrm{Ind}_q(n,k,\lfloor \log _q(k) \rfloor +1)> \dots > \textrm{Ind}_q(n,k,k)\ge n+1. \end{aligned}$$

$\square$

The following generalizes slightly Theorem 2.2.

Corollary 2.6

Let $2 \le \ell \le k \le q^{n}-1$. Then ${\text {Ind}}_q(n,k,\ell )=n+1$ if and only if $k=\ell$ and $\frac{q}{q+1}(n+1) \le \ell$.

Proof

This is a consequence of Theorem 2.2 and Proposition 2.5 (1). $\square$

2.2 Independent sets in ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$

In this part, we investigate some properties of ${\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )$.

Proposition 2.7

(Theorem 1.23 (2a)) Let $2 \le \ell \le k \le \frac{q^n-1}{q-1}$ with $\ell \le n$. Then ${\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )=\frac{q^n-1}{q-1}$ if and only if $k> \frac{q^{\ell -1}-1}{q-1}$. In other words, ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ is $(k,\ell )$-pro-independent if and only if $k> \frac{q^{\ell -1}-1}{q-1}$.

Proof

First assume that $k\le \frac{q^{\ell -1}-1}{q-1}$. Let us consider an $\ell -1$-dimensional subspace $V \le {\mathbb {F}}_q^{n}$. Since $\vert \rho _n(V {\setminus } \{\textbf{0}\})\vert =\frac{q^{\ell -1}-1}{q-1}\ge k$ and $\textrm{dim}(\langle X \rangle )< \ell$, the set ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ is not $(k,\ell )$-pro-independent.

Now assume that $k> \frac{q^{\ell -1}-1}{q-1}$. Let $S\subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ be of size k. Since $\vert S\vert =k > \frac{q^{\ell -1}-1}{q-1}$, we have $\textrm{dim}(\langle S \rangle ) \ge \ell$. Hence ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ is $(k,\ell )$-pro-independent. $\square$

Proposition 2.8

(Theorem 1.23 (2b) and (2c))

• (1) Let $2 \le \ell \le n$. Then the sequence $\{{\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )\}_{k=\ell }^{\frac{q^{\ell -1}-1}{q-1}}$ is strictly increasing in k.

• (2) Let $2 \le k \le \frac{q^n-1}{q-1}$. Then

  $$\begin{aligned} & \frac{q^n-1}{q-1}=\textrm{Ind}^{{\text {pro}}}_q(n,k,1)= \dots =\textrm{Ind}^{\textrm{pro}}_{q}(n,k,\lfloor \log _q((q-1)k+1)\rfloor +1)> \dots >\\ & \quad \textrm{Ind}^{{\text {pro}}}_q(n,k,k)\ge n+1. \end{aligned}$$

Proof

• (1) The proof is analogous to the one of Proposition 2.5 (1).

• (2) The proof is analogous to the one of Proposition 2.5 (2).

$\square$

2.3 ${\mathbb {F}}_q^n$ versus ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$

In this part, we discuss some relations between $\textrm{Ind}_q(n,k,\ell )$ and $\textrm{Ind}^{\textrm{pro}}_q(n,k,\ell )$. The following is straightforward.

Lemma 2.9

(Properties of $\rho _n$)

• (1) The map $\rho _n$ is a $(q-1)$-to-1. As a consequence, for every $S\subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$, we have that $\vert \rho _n^{-1}(S)\vert =(q-1)\vert S\vert$.

• (2) For any $T\subseteq {\mathbb {F}}_q^n {\setminus } \{\textbf{0}\}$, we have $\frac{\vert T\vert }{q-1}\le \vert \rho _n (T)\vert \le \vert T\vert$.

• (3) If $T\subseteq {\mathbb {F}}_q^n{\setminus }\{\textbf{0}\}$ is linearly independent, then $\vert \rho _n(T)\vert =\vert T\vert$.

• (4) Let $\textbf{v}_1,\dots ,\textbf{v}_r \in {\mathbb {F}}_q^n {\setminus }\{\textbf{0}\}$. If $\rho _n(\textbf{v}_1),\dots ,\rho _n(\textbf{v}_r)$ are linearly independent, then so are $\textbf{v}_1,\dots ,\textbf{v}_r$.

Lemma 2.10

Let $2 \le \ell \le n$. Suppose that $S\subseteq {\mathbb {F}}_q^n{\setminus } \{\textbf{0}\}$ is an $(\ell ,\ell )$-independent set. Then S is (2, 2)-independent.

Proof

Let $\textbf{u},\textbf{v} \in S$ be distinct vectors. Since $\vert S\vert \ge \ell$, there exists a subset $X \subseteq S$ of size $\ell$ containing both $\textbf{u}$ and $\textbf{v}$. Noticing that X is an independent set, $\textbf{u}$ and $\textbf{v}$ are also independent. Therefore S is (2, 2)-independent. $\square$

Lemma 2.11

Let $2 \le \ell \le k \le q^n-1$ with $\ell \le n$. Suppose that $S\subseteq {\mathbb {F}}_q^n{\setminus } \{\textbf{0}\}$ is $(k,\ell )$-independent. Then $\rho _n(S) \subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ is $(k,\ell )$-pro-independent. Moreover, if $k=\ell$, then $\vert \rho _n(S)\vert =\vert S\vert$.

Proof

For the first statement, let $X\subseteq \rho _n(S)$ be of size k. Since $\rho _n^{-1}(X) \cap S \subseteq S$ has size at least k, it contains an independent subset Y of size $\ell$. By Lemma 2.9 (2.9) and (2.9), $\rho _n(Y) \subseteq X$ is also independent of size $\ell$. Consequently $\rho _n(S)$ is $(k,\ell )$-pro-independent.

For the second statement, by Lemma 2.10, S is (2, 2)-independent. Hence, by Lemma 2.9 (2.9), $\rho _n\vert _S$ is injective; so $\vert \rho _n(S)\vert =\vert S\vert$ $\square$

Proposition 2.12

(Theorem 1.23 (3a)) Let $2 \le \ell \le k \le \frac{q^n-1}{q-1}$ with $\ell \le n$. Then $\textrm{Ind}_q^{\textrm{pro}}(n,k,\ell ) \le \textrm{Ind}_q(n,k,\ell )$. Moreover ${\text {Ind}}_q^{{\text {pro}}}(n,\ell ,\ell )={\text {Ind}}_q(n,\ell ,\ell )$.

Proof

For the first statement, let $S \subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ be $(k,\ell )$-pro-independent of maximum size. Let us choose a lift $S' \subseteq {\mathbb {F}}_q^n {\setminus } \{\textbf{0}\}$ of S under $\rho _n$. Since $\rho _n\vert _{S'}$ is injective, it is clear that $S'$ is $(k,\ell )$-independent. Hence $\textrm{Ind}_q^{\textrm{pro}}(n,k,\ell )=\vert S\vert =\vert S'\vert \le \textrm{Ind}_q(n,k,\ell )$.

For the second statement, let $S\subseteq {\mathbb {F}}_q^n{\setminus } \{\textbf{0}\}$ be $(\ell ,\ell )$-independent of maximum size. By Lemma 2.11, $\rho _n(S)$ is $(\ell ,\ell )$-pro-independent and $\vert \rho _n(S)\vert =\vert S\vert$. Hence $\textrm{Ind}_q(n,\ell ,\ell )=\vert S\vert =\vert \rho _n(S)\vert \le \textrm{Ind}_q^{\textrm{pro}}(n,\ell ,\ell )$. Consequently, from the first statement, we obtain ${\text {Ind}}_q^{{\text {pro}}}(n,\ell ,\ell )={\text {Ind}}_q(n,\ell ,\ell )$. $\square$

Question 2.13

When is ${\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )={\text {Ind}}_q(n,k,\ell )$?

Corollary 2.14

Let $2 \le \ell \le n$. Then ${\text {Ind}}_q^{{\text {pro}}}(n,\ell ,\ell )=n+1$ if and only if $\frac{q}{q+1}(n+1)\le \ell$.

Proof

This is a direct consequence of Theorem 2.2 and Proposition 2.12. $\square$

Proposition 2.15

(Theorem 1.23 (3b)) Let $2 \le \ell \le k \le \frac{q^n-1}{q-1}$ with $\ell \le n$. Then

$$\begin{aligned} \left\lceil \llceil \frac{1}{q-1}{\text {Ind}}_q(n,k,\ell )\right\rceil \rrceil \le {\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )\le \left\lfloor \frac{1}{q-1}{\text {Ind}}_q(n,(q-1)k,\ell )\right\rfloor . \end{aligned}$$

(2.1)

Proof

-Upper bound: Let $S\subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ be a $(k,\ell )$-pro-independent set of maximum size. Let $X\subseteq \rho _n^{-1}(S)$ be of size $(q-1)k$. Since $\vert \rho _n(X)\vert \ge k$ there exists an independent subset $Y \subseteq \rho _n(X)$ of size $\ell$. Let us consider a lift $T \subseteq X$ of Y under $\rho _n$. By Lemma 2.9 (2.9), T is also linearly independent. Hence $\rho _n^{-1}(S)$ is $((q-1)k,\ell )$-independent, so

$$\begin{aligned} {\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )=\vert S\vert =\frac{\vert \rho _n^{-1}(S)\vert }{q-1}\le \frac{{\text {Ind}}_q(n,(q-1)k,\ell )}{q-1}. \end{aligned}$$

Therefore ${\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )\le \left\lfloor \frac{{\text {Ind}}_q(n,k(q-1),\ell )}{q-1}\right\rfloor$.

-Lower bound: Let $S\subseteq {\mathbb {F}}_q^n{\setminus } \{\textbf{0}\}$ be a $(k,\ell )$-independent set of maximum size. By Lemma 2.11, $\rho _n(S)$ is $(k,\ell )$-pro-independent. Since $\vert \rho _n(S)\vert \ge \frac{\vert S\vert }{q-1}$, we have ${\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )\ge \vert \rho _n(S)\vert \ge \frac{{\text {Ind}}_q(n,k,\ell )}{q-1}$. Therefore ${\text {Ind}}_q^{{\text {pro}}}(n,k,\ell )\ge \left\lceil \llceil \frac{{\text {Ind}}_q(n,k,\ell )}{q-1}\right\rceil \rrceil$. $\square$

Proposition 2.16

(Theorem 1.23 (3b)) Let $2 \le \ell \le k \le \frac{q^n-1}{q-1}$ with $\ell \le n$. Assume that $k\le \frac{q^{\ell -1}-1}{q-1}$. Then $\textrm{Ind}_q(n,k,\ell )=(q-1)\textrm{Ind}^{\textrm{pro}}_q(n,k,\ell )$ if and only if $q=2$.

Proof

Assume that $q=2$. Then, by Remark 1.21, we have $\textrm{Ind}_q(n,k,\ell )=(q-1)\textrm{Ind}^{\textrm{pro}}_q(n,k,\ell )$.

Conversely assume that $\textrm{Ind}_q(n,k,\ell )=(q-1)\textrm{Ind}^{\textrm{pro}}_q(n,k,\ell )$. Let us consider a $(k,\ell )$-independent set $S\subseteq {\mathbb {F}}_q^n\setminus \{\textbf{0}\}$ of maximum size.

Claim

The set $\rho _n(S)$ is $(k,\ell )$-pro-independent of maximum size.

Proof of the claim

By Lemma 2.11, $\rho _n(S)$ is $(k,\ell )$-pro-independent. Since $\textrm{Ind}^{\textrm{pro}}(n,k,\ell ) \ge \vert \rho _n(S)\vert \ge \frac{\vert S\vert }{q-1}=\frac{\textrm{Ind}_q(n,k,\ell )}{q-1}$, we get $\vert \rho _n(S)\vert =\textrm{Ind}_q^{\textrm{pro}}(n,k,\ell )$. Hence $\rho _n(S)$ is $(k,\ell )$-pro-independent of maximum size. $\square$

Set $r= \left\lceil \llceil \frac{k}{q-1} \right\rceil \rrceil \ge 1$.

Claim

The set $\rho _n(S)$ is $(r,\ell )$-pro-independent.

Proof of the claim

First, note that $(q-1)\vert \rho _n(S)\vert =\vert S\vert$. Hence $\rho _n\vert _S: S \rightarrow \rho _n(S)$ is $(q-1)$ to 1. Now let $V \subseteq \rho _n(S)$ be of size r. As $X=\rho _n^{-1}(V)\cap S$ has size at least k, by the $(k,\ell )$-independence of S, we have $\textrm{dim}(\langle X \rangle ) \ge \ell$. Therefore $\textrm{dim}(\langle V \rangle ) \ge \ell$. This implies that $\rho _n(S)$ is $(r,\ell )$-pro-independent. $\square$

Consequently, $\textrm{Ind}_q^{\textrm{pro}}(n,k,\ell )=|\rho _n(S)|\le \textrm{Ind}^{\textrm{pro}}_q(n,r,\ell )$. By Proposition 2.8 (1), we deduce that $r=k$, so $q=2$. $\square$

Question 2.17

When are the inequalities in Proposition 2.15 tight?

3 Orthogonality in ${\mathcal {K}}^n$

In this section we prove Theorems 1.10, 1.12, 1.17 and 1.22. For that, let ${\mathcal {K}}$ be a discrete valued field with valuation $\nu$, maximal ideal ${\mathfrak {m}}$, valuation ring ${\mathcal {O}}$ and finite residue field $\kappa ={\mathbb {F}}_q$. Let us fix a uniformizer $\pi$ (that is $\nu (\pi )=1$) of ${\mathcal {K}}$ and an integer $n \ge 1$.

Notations:

• Denote by $\{\textbf{e}_1,\dots ,\textbf{e}_n\}$ the standard basis for ${\mathcal {K}}^n$.

• The Grassmannians $\textrm{Gr}_{s,n}({\mathcal {K}})$ and $\textrm{Gr}_{n,s}({\mathbb {F}}_q)$ ($1 \le s \le n$) denote the set of all s-dimensional subspaces of ${\mathcal {K}}^n$ and ${\mathbb {F}}_q^n$, respectively. In particular, $\textrm{Gr}_{1,n}({\mathbb {F}}_q)={\mathbb {P}}^{n-1}({\mathbb {F}}_q)$.

• For ${\textbf{v}}\in {\mathcal {K}}^n \setminus \{\textbf{0}\}$, let $\nu (\textbf{v})=\min _{1 \le i \le n} (\nu (v_i))$.

• Denote by ${\mathbb {B}}_n$ the unit sphere in ${\mathcal {K}}^{n}$, that is, ${\mathbb {B}}_n=\{\textbf{v} \in {\mathcal {K}}^n \mid \Vert \textbf{v}\Vert =1\}$.

• For $m \in {\mathbb {Z}}$ and $\lambda \in \pi ^m{\mathcal {O}}$, write $\lambda =O(\pi ^m)$ and denote by $\textrm{res}_m(\lambda )$ the residue of $\lambda$ in $\pi ^m{\mathcal {O}}/\pi ^{m+1}{\mathcal {O}} \simeq {\mathbb {F}}_q$. Let $\gamma =\textrm{res}_0: {\mathcal {O}} \rightarrow {\mathbb {F}}_q$ (the reduction modulo ${\mathfrak {m}}$) and let us fix a section $\delta :{\mathbb {F}}_q \rightarrow {\mathcal {O}}$ of $\gamma$.

• For $\textbf{v}=(v_1,\dots ,v_n) \in {\mathcal {O}}^n$, let $\gamma _n(\textbf{v})=(\gamma (v_1),\dots ,\gamma (v_n)) \in {\mathbb {F}}_q^n$. Denote by $\delta _n:{\mathbb {F}}_q^n \rightarrow {\mathcal {O}}^n$ the section of $\gamma _n$ induced by $\delta$.

• For $\textbf{0} \ne V \subseteq {\mathcal {K}}^n$, let $\mu _n(V)=\gamma _n(V \cap {\mathbb {B}}_n)\cup \{\textbf{0}\}$.

• Denote by $\rho _n$ the natural projection ${\mathbb {F}}_q^n\setminus \{\textbf{0}\} \rightarrow {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$.

• For $\ell \ge 1$, we denote by $\textrm{Sym}(\ell )$ the symmetric group on $\{1,\dots ,\ell \}$.

Example 3.1

Let ${\mathcal {K}}={\mathbb {F}}_q((x^{-1}))$ be as in Example 1.2. Take $\pi =x^{-1}$. Recall that ${\mathcal {O}}={\mathbb {F}}_q[[x^{-1}]]$ and note that ${\mathbb {B}}_n={\mathcal {O}}^n$. We have $\textrm{res}_m\left( \sum _{j=m}^{\infty }a_jx^{-j}\right) =a_m$ and

$$\begin{aligned} \gamma _n\left( \sum _{j=0}^{\infty }a_{1j}x^{-j},\dots ,\sum _{j=0}^{\infty }a_{nj}x^{-j}\right) =\left( a_{10},\dots ,a_{n0}\right) . \end{aligned}$$

A section of $\gamma$ is given by the inclusion $\delta : a \in {\mathbb {F}}_q \mapsto a \in {\mathcal {O}}$.

3.1 Weak and feeble orthogonality

In this part, we provide proofs of Theorem 1.10 (see §3.1.1) and Theorem 1.12 (see §3.1.2). We begin with some preliminary results.

Lemma 3.2

Let $\textbf{u}, \textbf{v} \in {\mathbb {B}}_n$. Then ${\textbf{u}}$ and ${\textbf{v}}$ are orthogonal if and only if $\rho _n(\gamma _n({\textbf{u}})) \ne \rho _n(\gamma _n({\textbf{v}}))$.

Proof

Assume that $\rho _n(\gamma _n({\textbf{u}}))=\rho _n(\gamma _n({\textbf{v}}))$. Then there exists $(a,b)\in {\mathbb {F}}_q^2 \setminus \{\textbf{0}\}$ such that $a \gamma _n(\textbf{u})+b \gamma _n(\textbf{v})=0$. Hence, for every $i\in [n]$, we have

$$\begin{aligned} \vert \delta (a)u_i+\delta (b)v_i\vert =\vert O(\pi )\vert <\max \{\Vert \delta (a){\textbf{u}}\Vert ,\Vert \delta (b){\textbf{v}}\Vert \}. \end{aligned}$$

This implies that $\Vert \delta (a)\textbf{u}+ \delta (b) \textbf{v}\Vert < \max \{\Vert \delta (a){\textbf{u}}\Vert ,\Vert \delta (b){\textbf{v}}\Vert \}$. Therefore, ${\textbf{u}}$ and ${\textbf{v}}$ are not orthogonal.

Conversely assume that $\rho _n(\gamma _n({\textbf{u}}))\ne \rho _n(\gamma _n({\textbf{v}}))$. Let $(\lambda ,\beta )\in {\mathcal {K}}^2 \setminus \{\textbf{0}\}$.

• Case 1: $\vert \lambda \vert <\vert \beta \vert$ or $\vert \beta \vert <\vert \lambda \vert$ . By the ultrametric inequality,

  $$\begin{aligned} \Vert \lambda {\textbf{u}}+\beta {\textbf{v}}\Vert =\max \{\Vert \lambda {\textbf{u}}\Vert ,\Vert \beta {\textbf{v}}\Vert \}. \end{aligned}$$

• Case 2: $\vert \lambda \vert =\vert \beta \vert$ . Since $\rho _n(\gamma _n(\textbf{u})) \ne \rho _n(\gamma _n(\textbf{v}))$, we have $\textrm{res}_{\nu (\lambda )}(\lambda )\gamma _n(\textbf{v})+\textrm{res}_{\nu (\beta )}(\beta )\gamma _n({\textbf{u}})\ne \textbf{0}$. Fix $i_0\in \textrm{supp}(\gamma _n(\textbf{u}))\cup \textrm{supp}(\gamma _n(\textbf{v}))$ such that

  $$\begin{aligned} \textrm{res}_{\nu (\lambda )}(\lambda )\gamma (v_{i_0})+\textrm{res}_{\nu (\beta )}(\beta )\gamma (u_{i_0}) \ne 0. \end{aligned}$$

  Since

  $$\begin{aligned} \textrm{res}_{\nu (\lambda )}\left( \lambda v_{i_0}+\beta u_{i_0}\right) =\textrm{res}_{\nu (\lambda )}(\lambda )\gamma (v_{i_0})+\textrm{res}_{\nu (\beta )}(\beta )\gamma (u_{i_0}) \ne 0, \end{aligned}$$

  we have

  $$\begin{aligned} \vert \lambda v_{i_0}+\beta u_{i_0}\vert =q^{\nu (\lambda )}=\max \{\Vert \lambda {\textbf{u}}\Vert ,\Vert \beta {\textbf{v}}\Vert \}, \end{aligned}$$

  and so

  $$\begin{aligned} \Vert \lambda {\textbf{u}}+\beta {\textbf{v}}\Vert =\vert \lambda u_{i_0}+\beta v_{i_0}\vert =\max \{\Vert \lambda {\textbf{u}}\Vert ,\Vert \beta {\textbf{v}}\Vert \}. \end{aligned}$$

Therefore $\Vert \lambda {\textbf{u}}+\beta {\textbf{v}}\Vert =\max \{\Vert \lambda {\textbf{u}}\Vert ,\Vert \beta {\textbf{v}}\Vert \}$. Consequently ${\textbf{u}}$ and ${\textbf{v}}$ are orthogonal. $\square$

Lemma 3.3

Suppose that $W={\mathbb {F}}_q \cdot \textbf{w}_1 \oplus \dots \oplus {\mathbb {F}}_q \cdot \textbf{w}_s \le {\mathbb {F}}_q^n$ ($s \ge 1$). Let

$$\begin{aligned} V={\mathcal {K}}\cdot \delta _n(\textbf{w}_1)+\dots +{\mathcal {K}} \cdot \delta _n(\textbf{w}_s). \end{aligned}$$

Then $\textrm{dim}(V)=s$ and $\mu _n(V)=W$.

Proof

Assume on the contrary that $\delta _n(\textbf{w}_1),\dots ,\delta _n(\textbf{w}_s)$ are linearly dependent over ${\mathcal {K}}$. Then $\lambda _1 \delta _n(\textbf{w}_1)+\dots +\lambda _s \delta _n(\textbf{w}_s)=0$ for some $(\lambda _1,\dots ,\lambda _s)\in {\mathcal {K}}^s \setminus \{\textbf{0}\}$. Fix $1 \le i_0 \le s$ such that $\vert \lambda _{i_0}\vert =\max _{1 \le i \le s}\vert \lambda _i\vert$. Hence $\sum _{i \ne i_0}\gamma (\lambda _i \lambda _{i_0}^{-1})\textbf{w}_{i}+\textbf{w}_{i_0}=0$, a contradiction. Therefore $\delta _n(\textbf{w}_1),\dots ,\delta _n(\textbf{w}_s)$ are linearly independent over ${\mathcal {K}}$. Consequently $\textrm{dim}(V)=s$.

Now we are going to prove that $\mu _n(V)=W$.

• The inclusion $W \subseteq \mu _n(V)$ . Let $\textbf{w} \in W$. Write $\textbf{w}=\lambda _1 \textbf{w}_1+\dots +\lambda _s\textbf{w}_s$ where $\lambda _1,\dots ,\lambda _s \in {\mathbb {F}}_q$. Then $\textbf{w}=\gamma _n\left( \delta (\lambda _1)\delta _n(\textbf{w}_1)+\dots +\delta (\lambda _s)\delta _n(\textbf{w}_s)\right) \in \mu _n(V)$. Hence $W \subseteq \mu _n(V)$.

• The inclusion $\mu _n(V) \subseteq W$ . Let $\textbf{a} \in \mu _n(V) {\setminus } \{\textbf{0}\}$. Write $\textbf{a}=\gamma _n(\textbf{v})$ where $\textbf{v} \in V \cap {\mathbb {B}}_n$. Moreover write $\textbf{v}=\lambda _{1}\delta _n(\textbf{w}_1)+\dots +\lambda _{s}\delta _n(\textbf{w}_s)$ where $\lambda _1,\dots ,\lambda _s \in {\mathcal {K}}$. Fix $1 \le i_0 \le s$ such that $\vert \lambda _{i_0}\vert =\max _{1\le i \le s}\vert \lambda _i\vert$. Since $\gamma _n(\lambda _{i_0}^{-1} \textbf{v})=\textbf{w}_{i_0}+\sum _{i \ne i_0}\gamma (\lambda _{i_0}^{-1}\lambda _i)\textbf{w}_i \ne \textbf{0}$, we get $\Vert \lambda _{i_0}^{-1} \textbf{v}\Vert =1$ and so $\vert \lambda _{i_0}\vert =1$. Hence $\lambda _{1},\dots ,\lambda _s \in {\mathcal {O}}$ and $\textbf{a}=\gamma _n(\textbf{v})=\sum _{i=1}^s \gamma (\lambda _i)\textbf{w}_i \in W$. Therefore $\mu _n(V) \subseteq W$.

Consequently $\mu _n(V)=W$. $\square$

Example 3.4

With the same notation as in Example 3.1, if $\textbf{w}_1,\dots ,\textbf{w}_s \in {\mathbb {F}}_q^n$ are ${\mathbb {F}}_q$-linearly independent, then

$$\begin{aligned} \mu _n({\mathcal {K}} \textbf{w}_1+\dots +{\mathcal {K}} \textbf{w}_s)={\mathbb {F}}_q\textbf{w}_1+\dots +{\mathbb {F}}_q\textbf{w}_s. \end{aligned}$$

Lemma 3.5

Let $V \le {\mathcal {K}}^n$ be a subspace of dimension $s \ge 1$. Then $\mu _n(V)$ is a subspace of ${\mathbb {F}}_q^n$ of dimension s.

Proof

Claim

The set $\mu _n(V)$ is a subspace of ${\mathbb {F}}_q^n$

Proof of the claim

Let $\lambda \in {\mathbb {F}}_q^*$ and let $\textbf{a}, \textbf{b} \in \mu _n(V){\setminus }\{\textbf{0}\}$. Write $\textbf{a}=\gamma _n(\textbf{u})$ and $\textbf{b}=\gamma _n(\textbf{v})$ where $\textbf{u},\textbf{v} \in V \cap {\mathbb {B}}_n$. First, noting that $\delta (\lambda )\textbf{u} \in V \cap {\mathbb {B}}_n$, we have $\lambda \textbf{a}=\gamma _n(\delta (\lambda ) \textbf{u}) \in \mu _n(V)$. Now we are going to prove that $\lambda \textbf{a}+\textbf{b} \in \mu _n(V)$. Without loss of generality, we may assume $\lambda \textbf{a}+\textbf{b} \ne \textbf{0}$. Since $\gamma _n(\delta (\lambda )\textbf{u}+\textbf{v})=\lambda \textbf{a}+\textbf{b} \ne \textbf{0}$, we have $\delta (\lambda )\textbf{u}+\textbf{v} \in V \cap {\mathbb {B}}_n$, and so $\lambda \textbf{a}+\textbf{b} \in \mu _n(V)$. Consequently, $\mu _n(V)$ is a subspace of ${\mathbb {F}}_q^n$. $\square$

Claim

The dimension of $\mu _n(V)$ is s.

Proof of the claim

By [10, Lemma 3.3], V admits an orthogonal basis $\{\textbf{v}_1,\dots ,\textbf{v}_s\}$, which we may assume to be in ${\mathbb {B}}_n$. By Proposition 3.14, $\gamma _n(\textbf{v}_1),\dots ,\gamma _n(\textbf{v}_s)$ are linearly independent. Then by Lemma 3.3, $\mu _n(V)={\mathbb {F}}_q \cdot \gamma _n(\textbf{v}_1)\oplus \dots \oplus {\mathbb {F}}_q \cdot \gamma _n(\textbf{v}_s)$. Hence $\textrm{dim}(\mu _n(V))=s$. $\square$

$\square$

Lemma 3.6

Let $s \ge 1$. Two subspaces $U,V \in \textrm{Gr}_{s,n}({\mathcal {K}})$ are feebly orthogonal if and only if $\mu _n(U) \ne \mu _n(V)$.

Proof

This follows from Lemmas 3.2, 3.3 and 3.5. $\square$

Lemma 3.7

Let $s\ge 1$ and let $k \ge \ell \ge 2$.

• (1) Let $S\subseteq {\mathbb {B}}_n$. Then S is $(k,\ell )$-weakly orthogonal, if and only if, for any $S'\subseteq S$ of size k, we have $\vert (\rho _n \circ \gamma _n)(S')\vert \ge \ell$.

• (2) Let ${\mathcal {F}}\subseteq \textrm{Gr}_{s,n}({\mathcal {K}})$. Then ${\mathcal {F}}$ is $(k,\ell )$-feebly orthogonal, if and only if, for any ${\mathcal {E}}\subseteq {\mathcal {F}}$ of size k, we have $\vert \mu _n({\mathcal {E}})\vert \ge \ell$.

Proof

• (1) This follows from the definition of $(k,\ell )$-weak orthogonality and Lemma 3.2.

• (2) This follows from the definition of $(k,\ell )$-feeble orthogonality and Lemma 3.6.

$\square$

Lemma 3.8

Let $s \ge 1$ and let $k \ge \ell \ge 2$.

• (1) Let $S \subseteq {\mathbb {B}}_n$. For $\textbf{w} \in {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$, let

  $$\begin{aligned} t_{\textbf{w},S}=\vert \{\textbf{v} \in S \mid \rho _n(\gamma _n(\textbf{v}))=\textbf{w}\}\vert . \end{aligned}$$

  Then the following are equivalent:

  • (a) S is $(k,\ell )$-weakly orthogonal;

  • (b) For any ${\mathcal {I}} \subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ with $\vert {\mathcal {I}}\vert \le \ell -1$, we have $\sum _{\textbf{w} \in {\mathcal {I}}}t_{\textbf{w},S} \le k-1$.

• (2) Let ${\mathcal {F}} \subseteq \textrm{Gr}_{n,s}({\mathcal {K}})$. For $W \in \textrm{Gr}_{n,s}({\mathbb {F}}_q)$, let

  $$\begin{aligned} t_{W,{\mathcal {F}}}=\vert \{V \in {\mathcal {F}} \mid \mu _n(V)=W\}\vert . \end{aligned}$$

  Then the following are equivalent:

  • (a) ${\mathcal {F}}$ is $(k,\ell )$-feebly orthogonal;

  • (b) For any ${\mathcal {R}} \subseteq \textrm{Gr}_{s,n}({\mathbb {F}}_q)$ with $\vert {\mathcal {R}}\vert \le \ell -1$, we have $\sum _{W \in {\mathcal {R}}} t_{W,S} \le k-1$.

Proof

• (1) By Lemma 3.7, S is $(k,\ell )$-weakly orthogonal, if and only if, $\vert \rho _n(\gamma _n(S'))\vert \ge \ell$, for all $S'\subseteq S$ of size k. This is equivalent to the following: for any ${\mathcal {I}} \subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ with $\vert {\mathcal {I}}\vert \le \ell -1$, we have $\vert (\rho _n \circ \gamma _n)^{-1}({\mathcal {I}}) \cap S\vert \le k-1$. In other words, for any ${\mathcal {I}} \subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ with $\vert {\mathcal {I}}\vert \le \ell -1$, we have $\sum _{\textbf{w} \in {\mathcal {I}}}t_{\textbf{w},S} \le k-1$.

• (2) By Lemma 3.7, ${\mathcal {F}}$ is $(k,\ell )$-feebly orthogonal, if and only if, $\vert \mu _n({\mathcal {E}})\vert \ge \ell$, for all ${\mathcal {E}}\subseteq {\mathcal {F}}$ of size k. This is equivalent to the following: for all ${\mathcal {R}} \subseteq \textrm{Gr}_{s,n}({\mathbb {F}}_q)$ with $\vert {\mathcal {R}}\vert \le \ell -1$, we have $\vert \mu _n^{-1}({\mathcal {R}}) \cap {\mathcal {F}}\vert \le k-1$. In other words, for any ${\mathcal {R}} \subseteq \textrm{Gr}_{s,n}({\mathbb {F}}_q)$ with $\vert {\mathcal {R}}\vert \le \ell -1$, we have $\sum _{W \in {\mathcal {R}}}t_{W,S} \le k-1$.

$\square$

3.1.1 Proof of Theorem 1.10

Lower bound of (1.3). Take $S_0 \subseteq {\mathbb {B}}_n$ satisfying $\vert (\rho _n \circ \gamma _n)^{-1}(\textbf{z})\cap S_0\vert = \left\lfloor \frac{k-1}{\ell -1}\right\rfloor$ for all $\textbf{z} \in {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$. Note that, for any $S' \subseteq S_0$ of size k, we have $(\rho _n \circ \gamma _n)(S') \ge \ell$. Thus, by Lemma 3.7, $S_0$ is $(k,\ell )$-weakly orthogonal. Therefore

$$\begin{aligned} \Delta _{n}^{(k,\ell )} \ge \vert S_0\vert = \left\lfloor \frac{k-1}{\ell -1}\right\rfloor \frac{q^n-1}{q-1}. \end{aligned}$$

-Upper bound of (1.3). Let $S \subseteq {\mathbb {B}}_n$ be a $(k,\ell )$-weakly orthogonal set of maximum size. By Lemma 3.8 (3.8), we have

$$\begin{aligned} \vert S\vert = \sum _{\textbf{w}\in {\mathbb {P}}^{n-1}({\mathbb {F}}_q)}t_{\textbf{w},S}=\frac{\sum _{{\mathcal {I}} \subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q),\vert {\mathcal {I}}\vert =\ell -1}\sum _{\textbf{w} \in {\mathcal {I}}}t_{\textbf{w},S}}{\left( {\begin{array}{c}\frac{q^n-1}{q-1}-1\\ \ell -2\end{array}}\right) }\le \frac{\left( {\begin{array}{c}\frac{q^n-1}{q-1}\\ \ell -1\end{array}}\right) (k-1)}{\left( {\begin{array}{c}\frac{q^n-1}{q-1}-1\\ \ell -2\end{array}}\right) }= \frac{k-1}{\ell -1} \cdot \frac{q^n-1}{q-1}, \end{aligned}$$

and so

$$\begin{aligned} \Delta _{n}^{(k,\ell )}=\vert S\vert \le \left\lfloor \frac{k-1}{\ell -1} \cdot \frac{q^n-1}{q-1}\right\rfloor . \end{aligned}$$

-Equation (1.4). From the discussion above, it is easy to see that

$$\begin{aligned} \Delta ^{(k,\ell )}_{n}=\max \left\{ \left. \sum _{i=1}^{\frac{q^n-1}{q-1}}t_i\,\,\right| \sum _{i \in I}t_i \le k-1,\,\,\text {for all}\,\, I \subseteq \left[ \frac{q^n-1}{q-1}\right] \,\, \text {of size}\,\, \ell -1\right\} . \end{aligned}$$

3.1.2 Proof of Theorem 1.12

The approach is quite similar to the proof of Theorem 1.10 in §3.1.1.

-Lower bound of (1.5). Take ${\mathcal {F}}_0 \subseteq \textrm{Gr}_{s,n}({\mathcal {K}})$ satisfying $\vert \mu _n^{-1}(W)\cap {\mathcal {F}}_0\vert = \left\lfloor \frac{k-1}{\ell -1}\right\rfloor$ for all $W \in \textrm{Gr}_{s,n}({\mathbb {F}}_q)$. Note that, for any ${\mathcal {E}} \subseteq {\mathcal {F}}_0$ of size k, we have $\vert \mu _n({\mathcal {E}})\vert \ge \ell$. By Lemma 3.7, ${\mathcal {F}}_0$ is $(k,\ell )$-feebly orthogonal. Therefore

$$\begin{aligned} \Delta _{n,s}^{(k,\ell )} \ge \vert {\mathcal {F}}_0\vert \ge \left\lfloor \frac{k-1}{\ell -1}\right\rfloor {n \brack s}_{q}. \end{aligned}$$

-Upper bound of (1.5). Let ${\mathcal {F}} \subseteq \textrm{Gr}_{s,n}({\mathcal {K}})$ be a $(k,\ell )$-feebly orthogonal set of maximum size. By Lemma 3.8 (3.8), we have

$$\begin{aligned} & \vert {\mathcal {F}}\vert = \sum _{W \in \textrm{Gr}_{s,n}({\mathbb {F}}_q)} t_{W,{\mathcal {F}}}=\frac{\sum _{{\mathcal {R}} \subseteq \textrm{Gr}_{s,n}({\mathbb {F}}_q),\vert {\mathcal {R}}\vert =\ell -1}\sum _{W \in {\mathcal {R}}}t_{W,{\mathcal {F}}}}{\left( {\begin{array}{c}\vert \textrm{Gr}_{s,n}({\mathbb {F}}_q)\vert -1\\ \ell -2\end{array}}\right) } \\ & \quad \le \frac{\left( {\begin{array}{c}\vert \textrm{Gr}_{s,n}({\mathbb {F}}_q)\vert \\ \ell -1\end{array}}\right) (k-1)}{\left( {\begin{array}{c}\vert \textrm{Gr}_{s,n}({\mathbb {F}}_q)\vert -1\\ \ell -2\end{array}}\right) }=\frac{k-1}{\ell -1} \cdot \vert \textrm{Gr}_{s,n}({\mathbb {F}}_q)\vert , \end{aligned}$$

and so

$$\begin{aligned} \Delta _{n,s}^{(k,\ell )}=\vert {\mathcal {F}}\vert \le \left\lfloor \frac{k-1}{\ell -1} \cdot {n \brack s}_{q}\right\rfloor . \end{aligned}$$

-Equation (1.6). From the discussion above, it is easy to see that

$$\begin{aligned} \Delta ^{(k,\ell )}_{n,s}=\max \left\{ \left. \sum _{i=1}^{{n \brack s }_{q}}t_i\,\,\right| \sum _{i \in I}t_i \le k-1,\,\,\text {for all}\,\, I \subseteq \left[ {n \brack s }_{q}\right] \,\, \text {of size}\,\, \ell -1\right\} . \end{aligned}$$

3.2 Orthogonal sets

In this section, we give a proof of Theorem 1.17 and establish another results. Our approach is based on the notion of wedge product, and we refer the reader to [14] for more details.

Lemma 3.9

(Wedge product norm) Let $\textbf{v}_1,\dots , \textbf{v}_\ell \in {\mathcal {K}}^n {\setminus } \{\textbf{0}\}$. Then

$$\begin{aligned} \Vert \textbf{v}_1 \wedge \dots \wedge \textbf{v}_\ell \Vert =\max _{1\le j_1<\dots<j_{\ell }\le n}\left| \det ((v_{i,j_k})_{1\le i,k \le \ell }) \right| =\max _{1\le j_1<\dots <j_{\ell }\le n}\left| \sum _{\sigma \in \textrm{Sym}(\ell )}{\text {sgn}}(\sigma )\prod _{i=1}^{\ell } v_{i,j_{\sigma (i)}}\right| .\nonumber \\ \end{aligned}$$

(3.1)

In particular, if $\ell =n$, then

$$\begin{aligned} \Vert \textbf{v}_1 \wedge \dots \wedge \textbf{v}_n\Vert =\left| \det ({\textbf{v}}_1,\dots ,{\textbf{v}}_n)\right| =\left| \sum _{\sigma \in \textrm{Sym}(n)} \textrm{sgn}(\sigma ) \prod _{i=1}^n v_{i,\sigma (i)} \right| . \end{aligned}$$

Lemma 3.10

(Hadamard’s inequality) Let $\textbf{v}_1,\dots , \textbf{v}_\ell \in {\mathcal {K}}^n {\setminus } \{\textbf{0}\}$. Then

$$\begin{aligned} \Vert \textbf{v}_1 \wedge \dots \wedge \textbf{v}_\ell \Vert \le \Vert \textbf{v}_1\Vert \dots \Vert \textbf{v}_\ell \Vert , \end{aligned}$$

with equality if and only if $\{\textbf{v}_1,\dots , \textbf{v}_\ell \}$ is orthogonal; in this case $\textbf{v}_1,\dots , \textbf{v}_\ell$ are linearly independent over ${\mathcal {K}}$.

Proof

See [14, Lemma 2.4]. $\square$

Lemma 3.11

A set $\{{\textbf{v}}_1,\dots , {\textbf{v}}_{\ell }\} \subseteq {\mathbb {B}}_n$ is orthogonal if and only if

$$\begin{aligned} \max _{1\le j_1<\dots <j_{\ell }\le n}\left| \sum _{\sigma \in \textrm{Sym}(\ell )}{\text {sgn}}(\sigma )\prod _{i=1}^{\ell } v_{i,j_{\sigma (i)}}\right| =1. \end{aligned}$$

(3.2)

Proof

This follows from Hadamard’s inequality and (3.1). $\square$

Lemma 3.11 motivates the following.

Definition 3.12

Let ${\textbf{v}}_1,\dots , {\textbf{v}}_{\ell } \in {\mathbb {B}}_n$. For any $1\le j_1<\dots <j_{\ell }\le n$, we define the matrix $C({\textbf{v}}_1,\dots ,{\textbf{v}}_{\ell };j_1,\dots ,j_{\ell })\in M_{\ell }({\mathbb {F}}_q)$ whose the (i, k)-th coordinate is $\gamma (v_{i,j_k})$, that is

$$\begin{aligned} C({\textbf{v}}_1,\dots ,{\textbf{v}}_{\ell };j_1,\dots ,j_{\ell })=\begin{pmatrix} \gamma (v_{1,j_1})& \gamma (v_{1,j_2})& \dots & \gamma (v_{1,j_\ell })\\ \gamma (v_{2,j_1})& \gamma (v_{2,j_2})& \dots & \gamma (v_{2,j_\ell })\\ \vdots & \dots & \ddots & \vdots \\ \gamma (v_{\ell ,j_{1}})& \gamma (v_{\ell ,j_{2}})& \dots & \gamma (v_{\ell ,j_{\ell }}) \end{pmatrix}. \end{aligned}$$

Lemma 3.13

Let ${\textbf{v}}_1,\dots , {\textbf{v}}_{\ell } \in {\mathbb {B}}_n$. Then $\{{\textbf{v}}_1,\dots ,{\textbf{v}}_{\ell }\}$ is orthogonal if and only if there exist $1 \le j_1<\dots <j_{\ell } \le n$ such that $C({\textbf{v}}_1,\dots ,{\textbf{v}}_{\ell };j_1,\dots ,j_{\ell })\in {\text {GL}}_\ell ({\mathbb {F}}_q)$.

Proof

By (3.2), $\{{\textbf{v}}_1,\dots ,{\textbf{v}}_{\ell }\}$ is orthogonal if and only if

$$\begin{aligned} \max _{1 \le j_1<\dots <j_{\ell }\le n}\left| \sum _{\sigma \in \textrm{Sym}(\ell )}{\text {sgn}}(\sigma )\prod _{i=1}^{\ell }v_{i,j_{\sigma (i)}}\right| =1, \end{aligned}$$

if and only if there exist $1 \le j_1<\dots <j_{\ell }\le n$ such that

$$\begin{aligned} \sum _{\sigma \in \textrm{Sym}(\ell )}{\text {sgn}}(\sigma )\prod _{i=1}^{\ell } v_{i,j_{\sigma (i)}} \in {\mathcal {O}}^*. \end{aligned}$$

This happens if and only if there exist $1 \le j_1<\dots <j_{\ell }\le n$ such that

$$\begin{aligned} \sum _{\sigma \in \textrm{Sym}(\ell )}{\text {sgn}}(\sigma )\prod _{i=1}^{\ell } \gamma (v_{i,j_{\sigma (i)}}) \ne 0, \end{aligned}$$

if and only if there exist $1 \le j_1<\dots <j_{\ell }\le n$ such that $\det \left( C({\textbf{v}}_1,\dots ,{\textbf{v}}_{\ell };j_1,\dots ,j_{\ell })\right) \ne 0$. $\square$

Proposition 3.14

A set $S=\{\textbf{v}_1,\dots ,\textbf{v}_\ell \} \subseteq {\mathbb {B}}_n$ with $\ell \le n$ is orthogonal if and only if the vectors $\gamma _n(\mathbf{v_1}),\dots ,\gamma _n(\mathbf{v_\ell }) \in {\mathbb {F}}_q^n$ are linearly independent. Moreover S is $(k,\ell )$-orthogonal if and only if for every $X\subseteq S$ of size k, we have $\textrm{dim}(\langle \gamma _n(X)\rangle ) \ge \ell$.

Proof

This follows easily from the definition of $(k,\ell )$-orthogonality and Lemma 3.13. $\square$

Proposition 3.15

(Theorem 1.17 (1)) Let $k \ge \ell \ge 2$. Then

$$\begin{aligned} \Theta _{n}^{(k,\ell )} \le \Delta _{n}^{(k,\ell )} \le \left\lfloor \frac{k-1}{\ell -1}\cdot \frac{q^n-1}{q-1}\right\rfloor . \end{aligned}$$

Proof

The first inequality is straightforward. The second inequality comes from Theorem 1.10. $\square$

Remark 3.16

Note that:

• $\Delta _{n}^{(k,2)}=\Theta _{n}^{(k,2)}$;

• and that $\Theta _{n}^{(n,n)}\ge n+1$, since $S=\{{\textbf{e}}_1,\dots , {\textbf{e}}_n,\sum _{i=1}^n \textbf{e}_i\}\subseteq {\mathcal {K}}^n{\setminus }\{\textbf{0}\}$ is (n, n)-orthogonal.

Question 3.17

When is $\Theta _{n}^{(k,\ell )} = \Delta _{n}^{(k,\ell )}$?

Lemma 3.18

Let $2 \le \ell \le n$ and let $S' \subset {\mathbb {B}}_n$ be an $(\ell ,\ell )$-orthogonal set.

• (1) $(\rho _n \circ \gamma _n)\vert _{S'}$ is injective. In particular, $\gamma _n\vert _{S'}$ is injective;

• (2) $S'$ is (m, m)-orthogonal, for all $2 \le m \le \ell$.

Proof

• (1) Let $\textbf{u}, \textbf{v} \in S'$ be distinct. Since $\vert S'\vert \ge \ell$, there exists $X \subset S'$ of size $\ell$ such that $\textbf{u},\textbf{v} \in X$. Since X is orthogonal, by Proposition 3.14, $(\rho _n \circ \gamma _n)(\textbf{u}) \ne (\rho _n \circ \gamma _n)(\textbf{v})$. Hence $(\rho _n \circ \gamma _n)\vert _{S'}$ is injective.

• (2) Let $2 \le m \le \ell$. Consider a subset $X \subset S'$ of size m. Since $\vert S'\vert \ge \ell$, there exists $Y \subset S'$ of size $\ell$ containing X. By the $(\ell ,\ell )$-orthogonality of $S'$, the set Y is orthogonal, so is X. Consequently $S'$ is (m, m)-orthogonal.

$\square$

Proposition 3.19

(Theorem 1.17 (2)) Let $2 \le \ell \le k$. Then ${\text {Ind}}_{q}(n,k,\ell )\le \Theta _{n}^{(k,\ell )}$. Moreover $\textrm{Ind}_q(n,\ell ,\ell )=\Theta _n^{(\ell ,\ell )}$.

Proof

For the first statement, let $S \subset {\mathbb {F}}_q^n {\setminus } \{ \textbf{0}\}$ be a $(k,\ell )$-independent set of maximum size. Then, by Proposition 3.14, the lift $\delta _n(S) \subset {\mathbb {B}}_n$ of S is $(k,\ell )$-orthogonal. Hence $\textrm{Ind}(n,k,\ell )=\vert S\vert =\vert \delta _n(S)\vert \le \Theta _n^{(k,\ell )}$.

For the second statement, let $S' \subseteq {\mathbb {B}}_n$ be an $(\ell ,\ell )$-orthogonal set of maximum size. On the one hand, by Lemma 3.18, we have $\vert \gamma _n(S')\vert =\vert S'\vert$. On the other hand, by Proposition 3.14, $\gamma _n(S')$ is $(\ell ,\ell )$-independent. Hence

$$\begin{aligned} \Theta _n^{(\ell ,\ell )} \ge \vert \gamma _n(S')\vert = \vert S'\vert =\textrm{Ind}_q(n,\ell ,\ell ). \end{aligned}$$

Therefore $\textrm{Ind}_q(n,\ell ,\ell )=\Theta _n^{(\ell ,\ell )}$ $\square$

Question 3.20

When is ${\text {Ind}}_{q}(n,k,\ell )=\Theta _{n}^{(k,\ell )}$?

Proposition 3.21

(Theorem 1.17 (2)) For every $2\le k \le q$, we have $\textrm{Ind}_{q}(n,k,2)=(k-1)\frac{q^n-1}{q-1}$.

Proof

Let $2 \le k \le q$. By Proposition 3.15 and Proposition 3.19, we have $\textrm{Ind}_{q}(n,k,2)\le (k-1)\frac{q^n-1}{q-1}$. Let us consider a lift $W \subseteq {\mathbb {F}}_q^n \setminus \{\textbf{0}\}$ of ${\mathbb {P}}^{n-1}({\mathbb {F}}_q)$, and let $\lambda _1,\dots ,\lambda _{k-1} \in {\mathbb {F}}_q^*$ be distinct elements. It is easy to see that $S=\cup _{i=1}^{k-1}\lambda _{i}W \subset {\mathbb {F}}_q^n {\setminus } \{\textbf{0}\}$ is (k, 2)-independent of size $(k-1)\frac{q^n-1}{q-1}$. Consequently, $\textrm{Ind}_{q}(n,k,2)=(k-1)\frac{q^n-1}{q-1}$. $\square$

The next result follows from Theorem 2.1 and Proposition 3.19.

Lemma 3.22

Assume $q=2$.

• (1) For every $n\ge 3$, we have $\Theta _{n}^{(3,3)}=2^{n-1}$.

• (2) For every $m\ge 0$ and $n\ge 3\,m+2$, we have $\Theta _{n}^{(n-m,n-m)}=n+1.$

• (3) For every $m\ge 2$, $i=0,1$, and $n=3m+i$, we have $\Theta _{n}^{(n-m,n-m)}=n+2$.

The next result follows from Theorem 2.2 and Proposition 3.19.

Lemma 3.23

Let $\ell \ge 2$. Then $\Theta _{n}^{(\ell ,\ell )}=n+1$ if and only if $\frac{q}{q+1}(n+1)\le \ell$.

Proposition 3.24

(Theorem 1.17 (2)) Let $k \ge \ell \ge 2$. Assume that $\Theta _{n}^{(k,\ell )}={\text {Ind}}_{q}(n,k,\ell )$. Then $k\le q^{\ell -2}+1$.

Proof

Let $T\subseteq {\mathbb {F}}_q^n\setminus \{\textbf{0}\}$ be a $(k,\ell )$-independent set of maximum size. By Proposition 3.14, since $\Theta _{n}^{(k,\ell )}={\text {Ind}}_q(n,k,\ell )$, the lift $\delta _n(T) \subseteq {\mathbb {B}}_n$ of T is $(k,\ell )$-orthogonal of maximum size.

Fix ${\textbf{v}}\in \delta _n(T)$ and $\textbf{u}\in {\mathcal {K}}^n$ with $0<\Vert {\textbf{u}}\Vert <1$. Then ${\textbf{v}}+{\textbf{u}}\notin \delta _n(T)$, and so $\delta _n(T)\cup \{{\textbf{v}}+{\textbf{u}}\}$ is not $(k,\ell )$-orthogonal. Hence, there exists $X\subseteq \delta _n(T)$ of size $k-1$, such that $X\cup \{{\textbf{v}}+{\textbf{u}}\}$ does not contain an orthogonal set of size $\ell$.

Now assume on the contrary that ${\textbf{v}}$ is orthogonal to some orthogonal subset $Y=\{{\textbf{w}}_1,\dots ,{\textbf{w}}_{\ell -1}\}\subseteq X$ of size $\ell -1$. On the one hand, by Lemma 3.10, since Y and $\textbf{v}+\textbf{u}$ are not orthogonal, we have

$$\begin{aligned} \Vert ({\textbf{v}}+{\textbf{u}})\wedge {\textbf{w}}_1\wedge \dots \wedge {\textbf{w}}_{\ell -1}\Vert <\Vert {\textbf{v}}+ {\textbf{u}}\Vert \cdot \Vert {\textbf{w}}_1\Vert \cdots \Vert {\textbf{w}}_{\ell -1}\Vert . \end{aligned}$$

(3.3)

On the other hand, again by Lemma 3.10,

$$\begin{aligned} \Vert {\textbf{v}}\wedge {\textbf{w}}_1\wedge \dots \wedge {\textbf{w}}_{\ell -1}\Vert =\Vert {\textbf{v}}\Vert \Vert {\textbf{w}}_1\Vert \cdots \Vert {\textbf{w}}_{\ell -1}\Vert , \end{aligned}$$

and

$$\begin{aligned} \Vert {\textbf{u}}\wedge {\textbf{w}}_1\wedge \dots \wedge {\textbf{w}}_{\ell -1}\Vert \le \Vert \textbf{u} \Vert \Vert \textbf{w}_1 \Vert \dots \Vert \textbf{w}_{\ell -1} \Vert <\Vert {\textbf{v}}\Vert \prod _{i=1}^{\ell -1}\Vert {\textbf{w}}_1\Vert ; \end{aligned}$$

so

$$\begin{aligned} \Vert ({\textbf{v}}+{\textbf{u}})\wedge {\textbf{w}}_1\wedge \cdots \wedge {\textbf{w}}_{\ell -1}\Vert =\Vert {\textbf{v}}\Vert \prod _{i=1}^{\ell -1}\Vert {\textbf{w}}_i\Vert =\Vert {\textbf{v}}+{\textbf{u}}\Vert \prod _{i=1}^{\ell -1}\Vert {\textbf{w}}_i\Vert . \end{aligned}$$

(3.4)

Equations (3.3) and (3.4) lead to a contradiction. Hence, ${\textbf{v}}$ is not orthogonal to any orthogonal set $Y\subseteq X$ of size $\ell -1$.

Therefore, by Proposition 3.14, $\gamma _n({\textbf{v}})$ belongs to every $\ell -1$-dimensional subset of $\gamma _n(X)$. Consequently we have $\textrm{dim}\langle \gamma _n(X){\setminus } \{\gamma _n({\textbf{v}})\} \rangle \le \ell -2$ so that

$$\begin{aligned} k-2\le \vert \gamma _n(X)\setminus \{\gamma _n({\textbf{v}})\}\vert \le q^{\ell -2}-1, \end{aligned}$$

and so $k\le q^{\ell -2}+1$. $\square$

Corollary 3.25

Let $k \ge \ell \ge 2$. Then $\textrm{Ind}(n,k,\ell ) < \Theta ^{(k,\ell )}_{n}$, for all $q^{\ell -2}+2\le k \le q^n-1$.

Proposition 3.26

(Theorem 1.17 (3)) Let $2 \le \ell \le k$. Then $\Theta _{n}^{(k,\ell )}\ge \left\lfloor \frac{k-1}{\ell -1}\right\rfloor \Theta _{n}^{(\ell ,\ell )}$.

Proof

Let $S=\{{\textbf{v}}_1,\dots ,{\textbf{v}}_{m}\}\subseteq {\mathbb {B}}_n$ be an $(\ell ,\ell )$-orthogonal set of maximum size. Let us choose $\omega _1,\dots , \omega _{\Big \lfloor \frac{k-1}{\ell -1}\Big \rfloor }\in \gamma ^{-1}(1)$ such that the $\omega _i \textbf{v}_j$’s are pairwise distinct. Consider the set

$$\begin{aligned} Y=\left\{ \omega _i{\textbf{v}}_j \Bigm \vert 1 \le i \le \left\lfloor \frac{k-1}{\ell -1}\right\rfloor ,1 \le j \le \vert S\vert \right\} \subseteq {\mathbb {B}}_n, \end{aligned}$$

of size $\left\lfloor \frac{k-1}{\ell -1}\right\rfloor \Theta _{n}^{(\ell ,\ell )}$. Note that, by Lemma 3.18, the $\gamma _n(\textbf{v}_j)$’s are pairwise distinct. Then $\gamma _n:Y\rightarrow \gamma _n(Y)$ is a $\Big \lfloor \frac{k-1}{\ell -1}\Big \rfloor$-1 function. Moreover, by Proposition 3.14, $\gamma _n(Y)=\gamma _n(S)$ is $(\ell ,\ell )$-independent.

Claim

The set Y is $(k,\ell )$-orthogonal.

Proof of the claim

Let $X\subseteq Y$ be a subset of size $\vert X\vert =k$. Since $\vert X\vert = k > (\ell -1)\Big \lfloor \frac{k-1}{\ell -1}\Big \rfloor$, we have $\vert \gamma _n(X)\vert \ge \ell$. Let us consider a subset $W\subseteq \gamma _n(X)$ of size $\ell$. Since $\gamma _n(Y)$ is $(\ell ,\ell )$-independent, $W\subseteq \gamma _n(S)$ is linearly independent. Letting $X'$ be a lift of W in X, again by Proposition 3.14, $X'\subseteq X$ is orthogonal of size $\ell$. Therefore Y is $(k,\ell )$-orthogonal. $\square$

Consequently

$$\begin{aligned} \Theta _{n}^{(k,\ell )}\ge \vert Y\vert =\left\lfloor \frac{k-1}{\ell -1}\right\rfloor \Theta _{n}^{(\ell ,\ell )}. \end{aligned}$$

$\square$

Proposition 3.27

(Theorem 1.17 (3)) Let $2 \le \ell \le k$. Then $\Theta _{n}^{(k,\ell )}\le (k-\ell +1){\text {Ind}}_{q}(n,k,\ell )$.

Proof

Let $S\subseteq {\mathbb {B}}_n$ be a $(k,\ell )$-orthogonal set of maximum size.

Claim

For every $\textbf{z} \in {\mathbb {F}}_q^n\setminus \{\textbf{0}\}$, we have $\vert \gamma _n^{-1}(\textbf{z}) \cap S\vert \le k-\ell +1$.

Proof of the claim

Assume on the contrary that $\vert \gamma _n^{-1}({\textbf{u}}) \cap S\vert \ge k-\ell +2$, for some ${\textbf{u}}\in {\mathbb {F}}_q^n{\setminus } \{\textbf{0}\}$. First note that $\vert S\vert \ge k$. Let us consider $X\subseteq S{\setminus } \gamma _n^{-1}({\textbf{u}})$ of size at most $\ell -2$ such that $Y=X\cup (\gamma _n^{-1}({\textbf{u}}) \cap S)$ has size at least k. Now take $Z \subseteq Y$ of size $\ell$. Since $\vert Z \cap \gamma _n^{-1}({\textbf{u}})\vert \ge 2$, the set Z is not orthogonal. Then Y does not contain an orthogonal set of size $\ell$. This contradicts the $(k,\ell )$-orthogonality of S. This completes the proof of the claim. $\square$

Therefore we have

$$\begin{aligned} \vert S\vert \le (k-\ell +1)\vert \gamma _n(S)\vert . \end{aligned}$$

By Proposition 3.14, $\gamma _n(S) \subseteq {\mathbb {F}}_q^n {\setminus } \{\textbf{0}\}$ is $(k,\ell )$-independent, so $\Theta _{n}^{(k,\ell )}=\vert S\vert \le (k-\ell +1)\vert \gamma _n(S)\vert \le (k-\ell +1){\text {Ind}}_q(n,k,\ell )$. Consequently $\Theta _{n}^{(k,\ell )}\le (k-\ell +1){\text {Ind}}_{q}(n,k,\ell )$. $\square$

Question 3.28

Let $\ell \ge 2$. Does the limit $\lim _{k \rightarrow \infty }\frac{\Theta ^{(k,\ell )}_{n}}{k}$ exist? Is $\left( \frac{\Theta ^{k,\ell }_{n}}{k}\right) _{k \ge \ell }$ increasing in k?

Proposition 3.29

(Theorem 1.17 (4)) Let $\ell \ge 2$. Then

$$\begin{aligned} \frac{q^n-1}{q^{\ell -1}-1} \le \limsup _{k\rightarrow \infty }\frac{\Theta _{n}^{(k,\ell )}}{k} \le q^{n}-1. \end{aligned}$$

Proof

-Upper bound. By Propositions 3.27 and 2.3,

$$\begin{aligned} \limsup _{k\rightarrow \infty }\frac{\Theta _{n}^{(k,\ell )}}{k}\le \limsup _{k\rightarrow \infty }\frac{k-\ell +1}{k}{\text {Ind}}_q(n,k,\ell )= \limsup _{k\rightarrow \infty }\frac{k-\ell +1}{k}(q^n-1)=q^n-1. \end{aligned}$$

-Lower bound. Let us consider a $(q^{\ell -1},\ell )$-independent subset $S \subseteq {\mathbb {F}}_q^n{\setminus }\{\textbf{0}\}$ of maximum size. Fix $r \ge 1$ and let $k_r=r(q^{\ell -1}-1)+1$. For each $\textbf{z} \in S$, choose $\Omega _{\textbf{z}} \subseteq \gamma _n^{-1}(\textbf{z})$ of size r. Note that $\Omega =\cup _{\textbf{z} \in S}\Omega _{\textbf{z}}$ has size $r\vert S\vert$.

Claim

The set $\Omega$ is $(k_r,\ell )$-orthogonal.

Proof of the claim

Let $Y \subseteq \Omega$ be of size $k_r$. By the pigeonhole principle, $\vert \gamma _n(Y)\vert \ge q^{\ell -1}$. Combining the fact that S is $(q^{\ell -1},\ell )$-independent with Proposition 3.14, we deduce that Y contains an orthogonal subset of size $\ell$. Hence $\Omega$ is $(k_r,\ell )$-orthogonal. $\square$

Therefore, by Proposition 2.3, $\Theta _{n}^{(k_r,\ell )}\ge \vert \Omega \vert =r\vert S\vert =r {\text {Ind}}_q(n,q^{\ell -1},\ell )=r(q^n-1)$, so

$$\begin{aligned} \Theta _{n}^{(k_r,\ell )}\ge \frac{k_r-1}{q^{\ell -1}-1}(q^n-1), \end{aligned}$$

which implies

$$\begin{aligned} \frac{\Theta _{n}^{(k_r,\ell )}}{k_r}\ge \frac{k_r-1}{k_r(q^{\ell -1}-1)}(q^n-1). \end{aligned}$$

Consequently we obtain

$$\begin{aligned} \limsup _{k\rightarrow \infty }\frac{\Theta _{n}^{(k,\ell )}}{k}\ge \limsup _{r\rightarrow \infty }\frac{\Theta _n^{(k_r,\ell )}}{k_r}\ge \frac{q^n-1}{q^{\ell -1}-1}. \end{aligned}$$

$\square$

Proposition 3.30

(Theorem 1.17 (5)) Let $\ell \ge 3$. Then $\Theta _{n}^{(\ell ,\ell )}<\Delta _{n}^{(\ell ,\ell )}$.

Proof

Let $S\subseteq {\mathbb {B}}_n$ be an $(\ell ,\ell )$-orthogonal set of maximum size. First note that, by Lemma 3.18, S is (3, 3)-orthogonal. Take distinct $\textbf{u}, \textbf{v} \in S$. By Lemma 3.18, since $(\rho _n \circ \gamma _n)(\textbf{u}) \ne (\rho _n \circ \gamma _n)(\textbf{v})$, we have $\gamma _n(\textbf{u}+\textbf{v}) \ne 0$, so $\textbf{u}+\textbf{v}\in {\mathbb {B}}_n$. As $\gamma _n(\textbf{u})$, $\gamma _n(\textbf{v})$ and $\gamma _n(\textbf{u}+\textbf{v})$ are linearly dependent, by Proposition 3.14, $\textbf{u}$, $\textbf{v}$ and $\textbf{u}+\textbf{v}$ are not orthogonal. Hence $\textbf{u}+\textbf{v} \notin S$.

Claim

The set $S \cup \{\textbf{u}+\textbf{v}\}$ is $(\ell ,\ell )$-weakly orthogonal.

Proof of the claim

Let $X\subseteq S \cup \{\textbf{u}+\textbf{v}\}$ be of size $\ell$. If $X\subseteq S$, then it is weakly orthogonal, by the $(\ell ,\ell )$-othogonality of S. Now assume that $X=X'\cup \{{\textbf{u}}+{\textbf{v}}\}$, for some $X'\subseteq S$ of size $\ell -1$. Clearly $X'$ is weakly orthogonal. Assume on the contrary that X is not weakly orthogonal, that is, there is ${\textbf{w}}\in X'$ such that ${\textbf{u}}+{\textbf{v}}$ and ${\textbf{w}}$ are not orthogonal. Then, by Proposition 3.14, $\gamma _n({\textbf{u}}+{\textbf{v}})$ and $\gamma _n({\textbf{w}})$ are linearly dependent, so are $\gamma _n({\textbf{u}}),\gamma _n({\textbf{v}}), \gamma _n({\textbf{w}})$. Again by Proposition 3.14, $\{{\textbf{u}},{\textbf{v}},{\textbf{w}}\}\subseteq S$ is not orthogonal, a contradiction. Hence, X is weakly orthogonal. Therefore $S\cup \{\textbf{u}+\textbf{v}\}$ is $(\ell ,\ell )$-weakly orthogonal. $\square$

Consequently, we have $\Theta _{n}^{(\ell ,\ell )}<\vert S \cup \{\textbf{u},\textbf{v}\}\vert \le \Delta _{n}^{(\ell ,\ell )}$. $\square$

3.3 Strongly orthogonal sets

In this part, we prove Theorem 1.22.

Proposition 3.31

(Theorem 1.22) Let $k \ge \ell \ge 2$. Then $\Gamma _{n,q}^{(k,\ell )}=\textrm{Ind}^{\textrm{pro}}_q(n,k,\ell )$.

Proof

By Lemma 3.2, $X \subseteq {\mathbb {B}}_n$ is weakly orthogonal if and only if $\vert (\rho _n \circ \gamma _n)(S)\vert =\vert S\vert$. Then a subset $S \subseteq {\mathbb {B}}_n$ is $(k,\ell )$-strongly orthogonal, if and only if, $\vert (\rho _n \circ \gamma _n)(S)\vert =\vert S\vert$, and by Proposition 3.14, for every $X\subseteq S$ of size k, we have $\textrm{dim}(\langle \gamma _n(X) \rangle ) \ge \ell$, if and only if $(\rho _n \circ \gamma _n)(S) \subseteq {\mathbb {P}}^{n-1}({\mathbb {F}}_q)$ is $(k,\ell )$-pro-independent of size $\vert S\vert$. This completes the proof. $\square$