# Almost orthogonal subsets of vector spaces over finite fields

Ali Mohammadi  A.M.: School of Mathematics, Institute for Research in
Fundamental Sciences (IPM), Tehran, Iran<EMAIL_ADDRESS>and  Giorgis
Petridis  G.P.: Department of Mathematics, University of Georgia, Athens, GA,
30602 USA<EMAIL_ADDRESS>
###### Abstract.

We prove various results on the size and structure of subsets of vector spaces
over finite fields which, in some sense, have too many mutually orthogonal
pairs of vectors. In particular, we obtain sharp finite field variants of a
theorem of Rosenfeld and an almost version of a theorem of Berlekamp.

##  1\. Introduction

###  1.1. Background

An _orthogonal set_ of vectors in ${\mathbb{R}}^{n}$, that is a set of non-
zero vectors with the property that every pair of distinct vectors is mutually
orthogonal, is linearly independent and therefore contains at most $n$
elements. Erdős asked the question of determining the maximum size of a set of
_almost orthogonal_ vectors: a set of non-zero vectors with the property that
among any three distinct vectors, at least two are mutually orthogonal [14].
The union of two disjoint orthogonal sets is an almost orthogonal set of size
$2n$. Rosenfeld, confirming a belief of Erdős, proved that $2n$ is the maximum
size of an almost orthogonal subset of ${\mathbb{R}}^{n}$ [16]. Deaett gave a
short and elegant proof of Rosenfeld’s theorem [6], which has similarities
with an argument of Pudlák [15]. Deaett also proved that for dimension 4 and
lower every almost orthogonal set of maximum size is the union of two
orthogonal sets; and provided examples in dimension 5 and higher of almost
orthogonal sets of maximum size that are not the union of two disjoint
orthogonal sets.

In ${\mathbb{C}}^{n}$, the existence of self-orthogonal vectors (like
$(1,i)\in{\mathbb{C}}^{2})$ changes the answer to both questions. Even in
dimension two, the span of $(1,i)$ is an uncountable set of orthogonal
vectors. Deaett proved, however, that in ${\mathbb{C}}^{n}$ equipped with the
Hermitian inner product, the maximum number of almost orthogonal vectors is
$2n$, generalising Rosenfeld’s theorem [6].

Both questions have also been investigated over finite fields. The size of the
largest orthogonal set in $({\mathbb{Z}}/(2{\mathbb{Z}}))^{n}$ was determined
by Berlekamp [5] and the size of the largest orthogonal set in
$({\mathbb{Z}}/(p{\mathbb{Z}}))^{n}$ for primes $p$ was determined by Zame
[23]. There are similarities in their methods. The question Berlekamp answered
is equivalent to solving another question of Erdős: determining the size of
the largest family of subsets of $\\{1,2,\dots,n\\}$ with the property that
every two distinct elements have even intersection. Erdős’ question was solved
independently by Graver [5, 8].

A key to Berlekamp’s and Zame’s arguments is the existence of self-orthogonal
vectors. Self-orthogonal vectors exist over any finite field when the
dimension is at least 3 or, in dimension 2, when the order of the field is 2
or is congruent to 1 modulo 4. There are further intricacies when working in
vector spaces over finite fields. For example, as is detailed in the next
subsection, in dimension 6, the dot product is equivalent to the symmetric
bilinear form $(\bm{x},\bm{y})\mapsto
x_{1}y_{1}-x_{2}y_{2}+x_{3}y_{3}-x_{4}y_{4}+x_{5}y_{5}-x_{6}y_{6}$ when the
order of the field is congruent to 1 modulo 4, and to the symmetric bilinear
form $(\bm{x},\bm{y})\mapsto
x_{1}y_{1}-x_{2}y_{2}+x_{3}y_{3}-x_{4}y_{4}+x_{5}y_{5}+x_{6}y_{6}$ when the
order of the field is congruent to 3 modulo 4. The difference points to the
fact that the largest orthogonal subspace has dimension that depends on the
order of the field [21]. In addition to this, expressing the dot product in
these equivalent ways has the advantage that it makes clear the existence of
self-orthogonal vectors.

There does not seem to be a significant difference between studying the dot
product and studying any symmetric non-degenerate bilinear form and this is
the approach taken in the literature recently. Ahmadi and Mohammadian [1],
using an argument similar to Berlekamp, determined the size of the largest
orthogonal set with respect to any non-degenerate symmetric bilinear form over
fields of odd order (see also [10, 21]). Ahmadi and Mohammadian also made
progress on the question of determining the size of the largest almost
orthogonal set with respect to any non-degenerate symmetric bilinear form.

The main purpose of this paper is to determine the size of the largest almost
orthogonal set with respect to any bilinear form in any vector space over any
sufficiently large finite field of odd order; and also in
$({\mathbb{Z}}/(2{\mathbb{Z}}))^{n}$ for sufficiently large $n$. It is worth
recording here that, unlike Rosenfeld’s and Deaett’s theorems, it is not
always the case that the size of the largest almost orthogonal set equals
twice the size of the largest orthogonal set. The
$({\mathbb{Z}}/(2{\mathbb{Z}}))^{n}$ question has a set system formulation
that can be thought of as an “almost” version of Berlekamp’s theorem:
determine the size of the largest family of subsets of $\\{1,2,\dots,n\\}$
with the property that among every three distinct elements, at least two have
even intersection. We show that the size of the largest family almost doubles.
We also investigate the finite field analogue of another question that Erdős
asked for Euclidean space: determine the maximum size of subsets of
${\mathbb{R}}^{n}$ with the property that among any $k$ of their elements, at
least two are mutually orthogonal [4, 7].

###  1.2. Notation and definitions

Throughout the paper, we use $m$ and $n$ to be positive integers, $p$ a prime
and $q=p^{m}$. We also use ${\mathbb{F}}_{q}$ to denote a finite field of
order $q$ and write ${\mathbb{F}}_{q}^{*}={\mathbb{F}}_{q}\setminus\\{0\\}$. A
bilinear form over ${\mathbb{F}}_{q}^{n}$ is a mapping
$\mathcal{B}:{\mathbb{F}}_{q}^{n}\times{\mathbb{F}}_{q}^{n}\rightarrow{\mathbb{F}}_{q}$,
which takes the form

${\mathcal{B}}(\bm{x},\bm{y})=\bm{x}^{T}A\bm{y},\ \text{for all
}\bm{x},\bm{y}\in{\mathbb{F}}_{q}^{n},$

for some $n\times n$ matrix $A$ over ${\mathbb{F}}_{q}$. We say
${\mathcal{B}}$ is symmetric if $A$ is a symmetric matrix and say
${\mathcal{B}}$ is degenerate if $\text{det}(A)=0$. We call two bilinear forms
equivalent if their corresponding matrices are equivalent ($A,B$ are
equivalent if $A=M^{T}BM$ for an invertible matrix $M$).

Fix a non-square element $\gamma\in{\mathbb{F}}_{q}$ and let
$k=\lfloor\frac{n}{2}\rfloor$. For any bilinear form $\mathcal{B}$ over
${\mathbb{F}}_{q}^{n}$, with associated matrix $A$, we define

$\varepsilon(\mathcal{B})=\begin{cases}0,&\mbox{if }\det(A)=0;\\\ 1,&\mbox{if
}k\ \text{is even and }\det(A)\ \text{is a non-zero square, or}\\\ &\mbox{if
}k\ \text{is odd and }-\det(A)\ \text{is a non-zero square};\\\
\gamma,&\mbox{if }k\ \text{is even and }\det(A)\ \text{is a non-square, or}\\\
&\mbox{if }k\ \text{is odd and }-\det(A)\ \text{is a non-square.}\end{cases}$

For odd $q$, by a result in [9, p. 79], which also appears as [1, Theorem 1],
any non-degenerate symmetric bilinear form, ${\mathcal{B}}$, over
${\mathbb{F}}_{q}^{n}$ is equivalent to the form

(1) $(\bm{x},\bm{y})\mapsto
x_{1}y_{1}-x_{2}y_{2}+\dots+x_{n-2}y_{n-2}-x_{n-1}y_{n-1}+\varepsilon({\mathcal{B}})x_{n}y_{n}$

for odd $n$ and is equivalent to the form

(2) $(\bm{x},\bm{y})\mapsto
x_{1}y_{1}-x_{2}y_{2}+\dots+x_{n-3}y_{n-3}-x_{n-2}y_{n-2}+x_{n-1}y_{n-1}-\varepsilon({\mathcal{B}})x_{n}y_{n}$

for even $n$, where $\bm{x}=(x_{1},\dots,x_{n})$ and
$\bm{y}=(y_{1},\dots,y_{n})$.

Given finite-dimensional vector spaces $V_{1}$ and $V_{2}$ over
${\mathbb{F}}_{q}$, with $n_{i}=\text{dim}(V_{i})$ for $i=1,2$, we define the
_direct sum_ $V_{1}\oplus V_{2}$ to be the vector space $V_{1}\times V_{2}$,
which may be identified by ${\mathbb{F}}_{q}^{n_{1}+n_{2}}$. Furthermore, if
$M_{1}$ and $M_{2}$ are matrices corresponding to bilinear forms over
${\mathbb{F}}_{q}^{n_{1}}$ and ${\mathbb{F}}_{q}^{n_{2}}$ respectively, we
define the matrix $M_{1}\oplus M_{2}$ by

$M_{1}\oplus M_{2}=\begin{pmatrix}M_{1}&0\\\ 0&M_{2}\end{pmatrix},$

which gives rise to a bilinear form over ${\mathbb{F}}_{q}^{n_{1}+n_{2}}.$

For $q=2$, one can infer from (5) in [12, p. 7] that every non-degenerate
symmetric bilinear form in odd dimension is equivalent to the dot product that
arises from the $n\times n$ identity matrix $I_{n}$. In even dimensions every
non-degenerate symmetric bilinear form is either equivalent to the dot product
or to the _hyperbolic form_ ${\mathcal{H}}$ that arises from the matrix
$H\oplus\dots\oplus H$, where

$H=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}.$

######  Definition 1.1.

We refer to two vectors
$\bm{v_{1}},\bm{v_{2}}\in{\mathbb{F}}_{q}^{n}\setminus\\{\bm{0}\\}$ as
mutually _orthogonal_ if $\mathcal{B}(\bm{v_{1}},\bm{v_{2}})=0$. If
$\bm{v}\in{\mathbb{F}}_{q}^{n}\setminus\\{\bm{0}\\}$, satisfies
$\mathcal{B}(\bm{v},\bm{v})=0$, we refer to it as _self-orthogonal_. We call a
subset $S\subset{\mathbb{F}}_{q}^{n}\setminus\\{\bm{0}\\}$ an _orthogonal set_
if every distinct pair of elements of $S$ are mutually orthogonal and we say
$S\subset{\mathbb{F}}_{q}^{n}\setminus\\{\bm{0}\\}$ is _$(k,l)$ -orthogonal_
if for any $k$ vectors in $S$ at least $l$ of them are pairwise mutually
orthogonal. Furthermore, we call a subspace $V\subset{\mathbb{F}}_{q}^{n}$ an
_orthogonal subspace_ if $V\setminus\\{\bm{0}\\}$ is an orthogonal set. We
denote by ${\mathcal{S}}_{k,l}={\mathcal{S}}_{k,l}(q,n,{\mathcal{B}})$ the
maximum size of any $(k,l)$-orthogonal subset of ${\mathbb{F}}_{q}^{n}$ with
respect to ${\mathcal{B}}$.

Given a set $X\subset{\mathbb{F}}_{q}^{n}$, we use $\langle X\rangle$ to
denote the subspace of ${\mathbb{F}}_{q}^{n}$ generated by $X$ and write
$\langle\bm{v}_{1},\cdots,\bm{v}_{k}\rangle$, instead of
$\langle\\{\bm{v}_{1},\cdots,\bm{v}_{k}\\}\rangle$. We also define the
_orthogonal complement_ of $X$ by
$X^{\perp}=\\{\bm{v}\in{\mathbb{F}}_{q}^{n}:{\mathcal{B}}(\bm{v},\bm{x})=0\
\text{for all }\bm{x}\in X\\}$, which constitutes a subspace of
${\mathbb{F}}_{q}^{n}$.

Finally, for sets $S,S_{1},\dots,S_{k}$, where $k\geq 2$, we write
$S=S_{1}\sqcup S_{2}\sqcup\cdots\sqcup S_{k}$ to mean firstly that
$S=S_{1}\cup S_{2}\cup\cdots\cup S_{k}$ and secondly that $S_{i}\cap
S_{j}=\emptyset$ for $1\leq i<j\leq k$.

###  1.3. Previous results for almost orthogonal sets

In [1, Examples 12–15], explicit examples of $(3,2)$-orthogonal sets are
provided for odd $q$, showing that

(3)
${\mathcal{S}}_{3,2}(q,n,{\mathcal{B}})\geq\begin{cases}2q^{\frac{n-1}{2}},&\mbox{if
}n\ \text{is odd and }\varepsilon({\mathcal{B}})=1;\\\
2q^{\frac{n-1}{2}}-q+1,&\mbox{if }n\ \text{is odd and
}\varepsilon({\mathcal{B}})=\gamma;\\\ 2q^{\frac{n}{2}}-q-1,&\mbox{if }n\
\text{is even and}\ \varepsilon(\mathcal{B})=1;\\\
2q^{\frac{n}{2}-1}+2,&\mbox{if }n\ \text{is even and}\
\varepsilon(\mathcal{B})=\gamma.\end{cases}$

The examples also work for $q=2$, showing that

(4)
${\mathcal{S}}_{3,2}(2,n,\cdot)\geq\begin{cases}2^{\frac{n+1}{2}},&\mbox{if
$n$ is odd};\\\ 2^{\frac{n}{2}+1}-3,&\mbox{if $n$ is even}.\end{cases}$

The authors further conjectured, in [1, Conjectures 11 and 16], that the
inequalities in (3) and (4) could be replaced by equalities and outlined a
proof, in [1, Theorem 17], that for all $n$ and either choices (1) and (2) of
bilinear forms, ${\mathcal{S}}_{3,2}\leq 3q^{\lfloor\frac{n}{2}\rfloor}$.

###  1.4. Improved lower bounds on $\mathcal{S}_{3,2}$

We proceed to present examples of $(3,2)$-orthogonal subsets of
${\mathbb{F}}_{q}^{n}$ for odd $q$ that have slightly more elements than the
examples given in (3). Theorem 2.1, which is stated in the next section, shows
that the examples described below are of maximum size. We denote by
$\\{\bm{e}_{1},\dots,\bm{e}_{n}\\}$ the standard basis of
${\mathbb{F}}_{q}^{n}$.

######  Example 1.2.

Let $q$ be odd and $n=2k+1\geq 3$ and ${\mathcal{B}}$ satisfy
$\varepsilon({\mathcal{B}})\in\\{1,\gamma\\}$. Consider the two mutually
disjoint orthogonal sets

$S_{1}=\big{(}\\{(x_{1},x_{1},\dots,x_{k},x_{k},0):x_{1},\dots,x_{k}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}\big{)}\sqcup\\{\bm{e}_{n-2}+\bm{e}_{n-1}+\bm{e}_{n}\\}$

and

$S_{2}=\big{(}\\{(x_{1},-x_{1},\dots,x_{k},-x_{k},0):x_{1},\dots,x_{k}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}\big{)}\sqcup\\{\bm{e}_{n-2}-\bm{e}_{n-1}-2\varepsilon({\mathcal{B}})^{-1}\bm{e}_{n}\\}.$

Then, the set $S=S_{1}\sqcup S_{2}\sqcup\\{\bm{e}_{n}\\}$ is a
$(3,2)$-orthogonal set of size $2q^{k}+1=2q^{(n-1)/2}+1$.

######  Example 1.3.

Let $q$ be odd and $n=2k\geq 2$ and ${\mathcal{B}}$ satisfy
$\varepsilon({\mathcal{B}})=1$. Consider the two mutually disjoint orthogonal
sets

$S_{1}=\\{(x_{1},x_{1},\dots,x_{k},x_{k}):x_{1},\dots,x_{k}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}$

and

$S_{2}=\\{(x_{1},-x_{1},\dots,x_{k},-x_{k}):x_{1},\dots,x_{k}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}.$

Then, the set $S=S_{1}\sqcup S_{2}$ is a $(3,2)$-orthogonal set of size
$2q^{k}-2=2q^{n/2}-2$.

######  Example 1.4.

Let $q$ be congruent to 3 modulo 4 and $n=2k\geq 4$ and ${\mathcal{B}}$
satisfy $\varepsilon({\mathcal{B}})=-1$ ($-1$ is not a square). Consider the
three pairwise disjoint orthogonal sets

$\displaystyle S_{1}=\big{(}\\{($ $\displaystyle
x_{1},x_{1},\dots,x_{k-1},x_{k-1},0,0):x_{1},\dots,x_{k-1}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}\big{)}\sqcup\\{\bm{e}_{n-3}+\bm{e}_{n-2}+\bm{e}_{n-1}+\bm{e}_{n},$
$\displaystyle\bm{e}_{n-3}+\bm{e}_{n-2}+\bm{e}_{n-1}-\bm{e}_{n}\\}$

and

$\displaystyle S_{2}=\big{(}\\{($ $\displaystyle
x_{1},-x_{1},\dots,x_{k-1},-x_{k-1},0,0):x_{1},\dots,x_{k-1}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}\big{)}\sqcup\\{\bm{e}_{n-3}-\bm{e}_{n-2}-\bm{e}_{n-1}-\bm{e}_{n},$
$\displaystyle\bm{e}_{n-3}-\bm{e}_{n-2}-\bm{e}_{n-1}+\bm{e}_{n}\\},$

and

$S_{3}=\\{\bm{e}_{n-1}+\bm{e}_{n},\bm{e}_{n-1}-\bm{e}_{n}\\}.$

Then, the set $S=S_{1}\sqcup S_{2}\sqcup S_{3}$ is a $(3,2)$-orthogonal set of
size $2q^{k-1}+4=2q^{n/2-1}+4$. For $n=2$,
$\\{\bm{e}_{1},2\bm{e}_{1},\bm{e}_{2},2\bm{e}_{2}\\}$ is a $(3,2)$-orthogonal
set of size 4.

Next, we provide examples for $q=2$. Theorem 2.2 shows they are of maximum
size. The following example is obtained by adding a single element to the
example given by [1, Example 12].

######  Example 1.5.

Let $n=2k+1\geq 3$ and ${\mathcal{B}}$ denote the dot product in
${\mathbb{F}}_{2}^{n}$. Consider the disjoint orthogonal sets

$S_{1}=\big{(}\\{(0,x_{1},x_{1}\dots,x_{k},x_{k}):x_{1},\dots,x_{k}\in{\mathbb{F}}_{2}\\}\setminus\\{\bm{0}\\}\big{)}\sqcup\\{\bm{e}_{1}\\}$

and

$S_{2}=\big{(}\\{(x_{1},x_{1},\dots,x_{k},x_{k},0):x_{1},\dots,x_{k}\in{\mathbb{F}}_{2}\\}\setminus\\{\bm{0}\\}\big{)}\sqcup\\{\bm{e}_{n}\\}.$

Then, the set $S=S_{1}\sqcup
S_{2}\sqcup\\{\bm{e}_{1}+\bm{e}_{2}+\dots+\bm{e}_{n}\\}$ is a
$(3,2)$-orthogonal set of size $2^{k+1}+1=2^{(n+1)/2}+1$.

The example below is the same as [1, Example 14].

######  Example 1.6.

Let $n=2k\geq 2$ and ${\mathcal{B}}$ denote the dot product in
${\mathbb{F}}_{2}^{n}$. Consider the disjoint orthogonal sets

$S_{1}=\\{(x_{1},x_{1},\dots,x_{k},x_{k}):x_{1},\dots,x_{k}\in{\mathbb{F}}_{2}\\}\setminus\\{\bm{0}\\}$

and

$S_{2}=\\{(x_{k},x_{1},x_{1},\dots,x_{k-1},x_{k-1},x_{k}):x_{1},\dots,x_{k}\in{\mathbb{F}}_{2}\\}\setminus\\{\bm{0}\\}.$

Then, noting $(1,1,\dots,1,1)\in S_{1}\cap S_{2}$, it follows that the set
$S=S_{1}\cup S_{2}$ is a $(3,2)$-orthogonal set of size
$2^{k+1}-3=2^{n/2+1}-3$.

Our final example concerns the hyperbolic form.

######  Example 1.7.

Let $n=2k\geq 2$ and ${\mathcal{H}}$ denote the hyperbolic form in
${\mathbb{F}}_{2}^{n}$. Consider the disjoint orthogonal sets

$S_{1}=\langle\bm{e}_{1},\bm{e}_{3},\bm{e}_{5},\dots,\bm{e}_{2k-1}\rangle\setminus\\{\bm{0}\\}$

and

$S_{2}=\langle\bm{e}_{2},\bm{e}_{4},\bm{e}_{6},\dots,\bm{e}_{2k}\rangle\setminus\\{\bm{0}\\}.$

It follows that the set $S=S_{1}\cup S_{2}$ is a $(3,2)$-orthogonal set of
size $2^{k+1}-2=2^{n/2+1}-2$.

##  2\. Main results

Our first main result is an upper bound on the size of $(3,2)$-orthogonal sets
for odd $q$.

######  Theorem 2.1.

Let $n\geq 0$ be an integer and $q\geq 7$ be an odd prime power. If
$S\subset{\mathbb{F}}_{q}^{n}$ is $(3,2)$-orthogonal with respect to a non-
degenerate symmetric bilinear form ${\mathcal{B}}$, then

$|S|\leq\begin{cases}2q^{\frac{n-1}{2}}+1,&\mbox{if }n\ \text{is odd};\\\
2q^{\frac{n}{2}}-2,&\mbox{if }n\ \text{is even and}\
\varepsilon(\mathcal{B})=1;\\\ 2q^{\frac{n}{2}-1}+4,&\mbox{if }n\geq 4\
\text{is even and}\ \varepsilon(\mathcal{B})=\gamma;\\\ 4,&\mbox{if }n=2\
\text{ and}\ \varepsilon(\mathcal{B})=\gamma.\end{cases}$

Combined with Examples 1.2, 1.3, and 1.4, Theorem 2.1 establishes the value of
$\mathcal{S}_{3,2}$ for all $n$, sufficiently large $q$, and ${\mathcal{B}}$:

$\mathcal{S}_{3,2}(q,n,{\mathcal{B}})=\begin{cases}2q^{\frac{n-1}{2}}+1,&\mbox{if
}n\geq 3\ \text{is odd};\\\ 2q^{\frac{n}{2}}-2,&\mbox{if }n\geq 2\ \text{is
even and}\ \varepsilon(\mathcal{B})=1;\\\ 2q^{\frac{n}{2}-1}+4,&\mbox{if
}n\geq 4\ \text{is even and}\ \varepsilon(\mathcal{B})=\gamma;\\\ 4,&\mbox{if
}n=2\ \text{ and}\ \varepsilon(\mathcal{B})=\gamma.\end{cases}$

In contrast to the Euclidean space ${\mathbb{R}}^{n}$, $\mathcal{S}_{3,2}$ is
sometimes larger than twice the size of the largest orthogonal set
(specifically when $n\geq 3$ is odd or when $n\geq 4$ is even and
$\varepsilon({\mathcal{B}})=\gamma$). See [1] or Lemma 3.3 below for the size
of the largest orthogonal set for the various possibilities of $n$, $q$, and
${\mathcal{B}}$.

The proof of Theorem 2.1 relies on the framework developed by Ahmadi and
Mohammadian [1]. It also has similarities with the work of Berlekamp [5] and
the paper of Deaett [6]. In Section 5 we present a different argument for even
$n$ with $\varepsilon({\mathcal{B}})=1$ that is based on character sum
estimates. The proof in Section 5 works for all odd $q$.

We also answer the corresponding question for $q=2$.

######  Theorem 2.2.

Let $n$ be an integer. If $S\subset{\mathbb{F}}_{2}^{n}$ is a
$(3,2)$-orthogonal with respect to the dot product, then

$|S|\leq\begin{cases}2^{\frac{n+1}{2}}+1,\quad&\text{if}\quad n\geq 21\
\text{is odd};\\\ 2^{\frac{n}{2}+1}-3,\quad&\text{if}\quad n\geq 18\ \text{is
even}.\end{cases}$

For even $n\geq 2$ and $S\subset{\mathbb{F}}_{2}^{n}$ be $(3,2)$-orthogonal
with respect to the hyperbolic form ${\mathcal{H}}$,

$|S|\leq 2^{\frac{n}{2}+1}-2.$

Combined with Examples 1.5, 1.6, and 1.7, Theorem 2.2 establishes the value of
$\mathcal{S}_{3,2}$ for all sufficiently large $n$:

$\mathcal{S}_{3,2}(2,n,{\mathcal{B}})=\begin{cases}2^{\frac{n+1}{2}}+1,&\mbox{if
}n\geq 21\ \text{is odd and }{\mathcal{B}}=\cdot\,;\\\
2^{\frac{n}{2}+1}-3,&\mbox{if }n\geq 18\ \text{is even and}\
\mathcal{B}=\cdot\,;\\\ 2^{\frac{n}{2}+1}-2,&\mbox{if }n\geq 2\ \text{is even
and}\ \mathcal{B}={\mathcal{H}}.\end{cases}$

As highlighted in [1], the quantity $\mathcal{S}_{3,2}(2,n,\cdot)$ may be
interpreted as the size of a maximally large family $\mathcal{F}$ of non-empty
subsets of an $n$-element set such that among every three distinct elements of
$\mathcal{F}$, there is a pair of sets whose intersection is of even
cardinality. The values above confirm [1, Conjecture 16] of Ahmadi and
Mohammadian for sufficiently large, even $n$. Although, for odd $n$, we have
shown that the relevant value is larger by one than what was conjectured. The
sufficiently large $n$ assumption cannot be removed, see Remark 6.7.

We also prove an upper bound for $\mathcal{S}_{k,2}(q,n,{\mathcal{B}})$. This
is the finite field analogue of another question of Erdős [4, 7].

######  Theorem 2.3.

Let $q$ be an odd prime power and $k\geq 2$ be an integer. Suppose that
$S\subset{\mathbb{F}}_{q}^{n}\setminus\\{\bm{0}\\}$ is $(k,2)$-orthogonal with
respect to a non-degenerate symmetric bilinear form ${\mathcal{B}}$. Then

$|S|\leq\bigg{(}k-1+\frac{(k-1)^{2}}{q-k+1}\bigg{)}(q^{n/2}+1).$

Theorem 2.3 implies

$\mathcal{S}_{k,2}\leq(k-1+o_{q\to\infty}(1))q^{n/2},$

which is asymptotically sharp in some cases. For example for odd $q$, $k=n=4$
and $\varepsilon({\mathcal{B}})=1$ the union of the following three pairwise
disjoint orthogonal sets has size $3(q^{2}-1)$:

$S_{1}=\\{(x_{1},x_{1},x_{2},x_{2}):x_{1},x_{2}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}$

and

$S_{2}=\\{(x_{1},-x_{1},x_{2},-x_{2}):x_{1},x_{2}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}$

and

$S_{3}=\\{(x_{1},x_{2},x_{2},-x_{1}):x_{1},x_{2}\in{\mathbb{F}}_{q}\\}\setminus\\{\bm{0}\\}.$

###  2.1. Outline of the proofs of Theorems 2.1 and 2.2

The proofs of Theorems 2.1 and 2.2 are based on an inductive scheme developed
by Ahmadi and Mohammadian [1]. To outline the argument let us denote by
$d_{n}=d_{n}(q,{\mathcal{B}})$ the dimension of the largest orthogonal
subspace of ${\mathbb{F}}_{q}^{n}$ with respect to a non-degenerate symmetric
bilinear form ${\mathcal{B}}$. Both theorems take the form

(5) ${\mathcal{S}}_{3,2}(q,n,{\mathcal{B}})=2q^{d_{n}}+f(q,n,{\mathcal{B}}),$

where $f(q,n,{\mathcal{B}})\in\\{-3,-2,1,4\\}$. We show this by proving by
induction a weaker statement of the form
${\mathcal{S}}_{3,2}(q,n,{\mathcal{B}})\leq(2+o(1))q^{d_{n}}$. Note here that
the $o(1)$ term is for $q\to\infty$ for odd $q$ and $n\to\infty$ for $q=2$. A
technical difficulty in carrying out the induction is that one must ensure
that the restriction of ${\mathcal{B}}$ to the orthogonal complement
considered is non-degenerate.

The inductive argument that proves the weaker bound is based on the basic
observation that for every $\bm{v}\in S$, the set of elements in
$S\setminus\\{\bm{v}\\}$ not orthogonal to $\bm{v}$ constitute an orthogonal
set. The structure of orthogonal sets has been determined by Berlekamp, and
Ahmadi and Mohammadian [5, 1]. A key feature is that they contain few elements
not in a single orthogonal subspace. We make repeated use of this fact. The
second basic fact we use to our advantage for large odd $q$ is that a proper
subspace of a vector space is significantly smaller than the vector space.

Once the weak bound has been established, it is used to determine
$f(q,n,{\mathcal{B}})$. It is at this point that different arguments must be
used according to $(q,n,{\mathcal{B}})$. The key observation, implicit in the
literature, is that if an orthogonal set contains just a few elements that are
not self-orthogonal, then it is much smaller than $q^{d_{n}}$ (for large $q$).

For $q=2$, which is not large, slightly different arguments are utilised. The
basic fact that drives the proof is that, unlike for odd $q$, the set of
vectors not orthogonal to any $\bm{v}$ contains at most half of any orthogonal
subspace.

The proofs of Theorems 2.1 and 2.2 probably yield a characterisation of nearly
extremal sets: they are mostly contained in two disjoint orthogonal subspaces
of maximum dimension.

##  3\. Preparations

We begin with some basic facts about Ramsey numbers. Given positive integers
$s,t$ the _Ramsey number_ $R(s,t)$ is the least integer with the property that
every graph on $R(s,t)$ vertices either contains a $K_{s}$ or the complement
of the graph contains a $K_{t}$. We will use the following bounds:

(6) $R(3,3)=6,R(3,4)=9,R(s,t)\leq\binom{s+t-2}{s-1}.$

The connection between Ramsey numbers and almost orthogonal sets goes back to
at least the paper of Deaett [6]. A connection with other similar questions of
Erdős is detailed in [14]. We deduce the following elementary observation
concerning graphs.

######  Lemma 3.1.

A triangle-free graph with the property that its complement is also triangle-
free is either the 5-cycle or has at most 4 vertices.

###### Proof.

We denote by $H$ the graph. Its order is at most $R(3,3)-1=5$ (by (6)).

Suppose now that the order of $H$ is 5. Note that $H$ does not have a vertex
of degree at least 3. This is because if such a vertex existed, then either
two of its neighbours would be connected by an edge, giving rise to a
triangle; or none of its neighbours would be connected by an edge, giving a
triangle in the complement. Similarly, the complement has no edge of degree at
least 3. Therefore all vertices of the graph have degree 2. Finite graphs of
constant degree 2 contain a cycle. The graph $H$ has no 3-cycle. It does not
contain a 4-cycle (the fifth vertex would be isolated). Therefore it contains
a 5-cycle, which is the entire graph. ∎

We proceed with results concerning orthogonal sets. The most important is a
structural characterisation of orthogonal sets which we take from [1, Lemma 3]
– see also [5] for $q=2$.

######  Lemma 3.2.

Let $\mathcal{B}$ denote a non-degenerate, symmetric bilinear form over
${\mathbb{F}}_{q}^{n}$, where $q$ is a prime power and $n\geq 2$. Suppose that
$S\subset{\mathbb{F}}_{q}^{n}$ is an orthogonal set. Then, there exists an
orthogonal subspace
$V\subset\\{\bm{x}\in{\mathbb{F}}_{q}^{n}:\mathcal{B}(\bm{x},\bm{x})=0\\}$ and
a set $T=\\{\bm{x}\in S:\mathcal{B}(\bm{x},\bm{x})\not=0\\}$, such that
$S\subset V\sqcup T$ and $2\dim(V)+|T|\leq n.$

Next, we recall [1, Theorem 4], which relying mainly on Lemma 3.2, obtains the
following sharp bound on orthogonal sets. We note that in [1]
$\mathcal{S}_{2,2}(q,n,{\mathcal{B}})$ is denoted by $\mathcal{S}_{0}(q,n)$.

######  Lemma 3.3.

For $n\geq 2$ and a prime power $q\geq 3$, let $\mathcal{B}$ denote a non-
degenerate symmetric bilinear form over ${\mathbb{F}}_{q}^{n}$. Then

${\mathcal{S}}_{2,2}(q,n,{\mathcal{B}})=\begin{cases}q^{\frac{n-1}{2}},&\mbox{if
}n\ \text{is odd};\\\ q^{\frac{n}{2}}-1,&\mbox{if }n\ \text{is even and}\
\varepsilon(\mathcal{B})=1;\\\ q^{\frac{n}{2}-1}+1,&\mbox{if }n\ \text{is even
and}\ \varepsilon(\mathcal{B})=\gamma.\end{cases}$

An analogue of Lemma 3.3, for $q=2$, was earlier proved by Berlekamp [5]. Also
see [8].

######  Lemma 3.4.

${\mathcal{S}}_{2,2}(2,n,\cdot)=\begin{cases}n,&\mbox{if }n\leq 5;\\\
1+2^{\frac{n-1}{2}},&\mbox{if }n\ \text{is odd and}\ n\geq 7;\\\
2^{\frac{n}{2}},&\mbox{if }n\ \text{is even and}\ n\geq 6.\end{cases}$

The following corollary is central to our considerations.

######  Lemma 3.5.

For $n\geq 2$ and a prime power $q$, let $S\subset{\mathbb{F}}_{q}^{n}$ be a
$(3,2)$-orthogonal set with respect to a non-degenerate symmetric bilinear
form ${\mathcal{B}}$ over ${\mathbb{F}}_{q}^{n}$. For $\bm{s}\in S$, define

(7) $S_{\bm{s}}=\\{\bm{x}\in S\setminus\\{\bm{s}\\}:\
\mathcal{B}(\bm{x},\bm{s})\not=0\\}.$

If $|S_{\bm{s}}|\geq 2$, then $S_{\bm{s}}$ is an orthogonal set. In
particular, we may write for all $\bm{s}\in S$

$S_{\bm{s}}=R_{\bm{s}}\sqcup T_{\bm{s}},$

where $T_{\bm{s}}=\\{\bm{x}\in S_{\bm{s}}:\mathcal{B}(\bm{x},\bm{x})\not=0\\}$
and $\langle R_{\bm{s}}\rangle=V_{\bm{s}}$, an orthogonal subspace of
${\mathbb{F}}_{q}^{n}$ that contains only self-orthogonal vectors.

###### Proof.

Given two distinct vectors $\bm{x_{1}},\bm{x_{2}}\in S_{\bm{s}}$, by the
$(3,2)$-orthogonality of $S$, two of $\\{\bm{x_{1}},\bm{x_{2}},\bm{s}\\}$ must
be mutually orthogonal. Thus, given the definition of $S_{\bm{s}}$, we must
have $\mathcal{B}(\bm{x_{1}},\bm{x_{2}})=0$. The rest follows from Lemma 3.2
or is immediate when $|S_{\bm{s}}|\leq 1$. ∎

We also collect some basic facts about orthogonal subspaces as follows.

######  Lemma 3.6.

Let $V\subset{\mathbb{F}}_{q}^{n}$ denote an orthogonal subspace with at least
three elements.

  1. (i)

Every vector in $V$ is self-orthogonal.

  2. (ii)

Suppose that $V$ is of maximum dimension and $V=\langle R\rangle$ for some
$R\subset{\mathbb{F}}_{q}^{n}$. If $\bm{z}\notin V$ is a self-orthogonal
vector, then $\bm{z}$ is not orthogonal to $R$.

###### Proof.

For the first statement, let $\bm{x}$ be any element of $V$ and $\bm{y}$ some
other element of $V$. It follows that $\bm{x}+\bm{y}\in
V\setminus\\{\bm{x}\\}$ and so

$0={\mathcal{B}}(\bm{x},\bm{x}+\bm{y})={\mathcal{B}}(\bm{x},\bm{x})+{\mathcal{B}}(\bm{x},\bm{y})={\mathcal{B}}(\bm{x},\bm{x}).$

For the second statement, we have ${\mathcal{B}}(\bm{z},\bm{z})=0$. Suppose
for a contradiction that $\bm{z}\perp R$. Then $\bm{z}\perp V$. Note that by
the first part, for all $\lambda,\mu\in{\mathbb{F}}_{q}$ and $\bm{x},\bm{y}\in
V$ we have

${\mathcal{B}}(\lambda\bm{z}+\bm{x},\mu\bm{z}+\bm{y})=\lambda\mu{\mathcal{B}}(\bm{z},\bm{z})+\lambda{\mathcal{B}}(\bm{z},\bm{y})+\mu{\mathcal{B}}(\bm{z},\bm{x})+{\mathcal{B}}(\bm{x},\bm{y})=0.$

Hence $\langle\\{\bm{z}\\}\cup R\rangle$ is an orthogonal subspace that
strictly contains $V$, a contradiction. ∎

The next result forms the basis of the induction argument in the proof of
Theorem 2.1. The key is to show that if we restrict ${\mathcal{B}}$ to a
certain type of orthogonal complement, then it remains non-degenerate; and
that, under a further condition, the equivalence class of ${\mathcal{B}}$ is
conserved.

######  Lemma 3.7.

Let $n\geq 2$, $\mathcal{B}$ be a non-degenerate symmetric bilinear form over
${\mathbb{F}}_{q}^{n}$, and $\\{\bm{v},\bm{w}\\}\subset{\mathbb{F}}_{q}^{n}$
be linearly independent.

  1. (i)

If

${\mathcal{B}}(\bm{v},\bm{w})^{2}\neq{\mathcal{B}}(\bm{v},\bm{v}){\mathcal{B}}(\bm{w},\bm{w}),$

then the restriction
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$}$
of $\mathcal{B}$ to the orthogonal complement of $\\{\bm{v},\bm{w}\\}$, is a
non-degenerate symmetric bilinear form.

  2. (ii)

If $q$ is odd, $\bm{v}$ and $\bm{w}$ are not mutually orthogonal, and $\bm{w}$
is self-orthogonal (that is ${\mathcal{B}}(\bm{v},\bm{w})\neq 0$ and
${\mathcal{B}}(\bm{w},\bm{w})=0$), then
$\varepsilon(\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$})=\varepsilon(\mathcal{B})$.

  3. (iii)

If $q=2$, $n$ is even, $\bm{v}$ and $\bm{w}$ are not mutually orthogonal, and
both $\bm{v},\bm{w}$ are self-orthogonal (that is
${\mathcal{B}}(\bm{v},\bm{w})\neq 0$ and
${\mathcal{B}}(\bm{v},\bm{v})={\mathcal{B}}(\bm{w},\bm{w})=0$), then
${\mathcal{B}}$ is equivalent to ${\mathcal{H}}$ if and only if
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$}$
is equivalent to ${\mathcal{H}}$.

###### Proof.

Throughout the proof we write

$a={\mathcal{B}}(\bm{v},\bm{v}),b={\mathcal{B}}(\bm{v},\bm{w}),c={\mathcal{B}}(\bm{w},\bm{w}).$

For (i), we first show
$\langle\bm{v},\bm{w}\rangle\cap\\{\bm{v},\bm{w}\\}^{\perp}=\\{\bm{0}\\}$ and
therefore that
${\mathbb{F}}_{q}^{n}=\langle\bm{v},\bm{w}\rangle\oplus\\{\bm{v},\bm{w}\\}^{\perp}$.
Suppose $\lambda\bm{v}+\mu\bm{w}\in\\{\bm{v},\bm{w}\\}^{\perp}$. Applying
${\mathcal{B}}(\bm{v},-)$ and then ${\mathcal{B}}(\bm{w},-)$ to both sides
gives the linear system

$\left\\{\begin{matrix}\lambda a+\mu b=0\\\ \lambda b+\mu
c=0\end{matrix}\right..$

It follows that $\lambda=\mu=0$ because $ac\neq b^{2}$.

We write $M_{1}$ for the matrix of
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\langle\bm{v},\bm{w}\rangle$}$
with respect to the basis $\\{\bm{v},\bm{w}\\}$, $M_{2}$ for the matrix of
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$}$
with respect to any basis, and $M$ for the matrix of $\mathcal{B}$ with
respect to the union of these two bases, then

$M=\begin{pmatrix}M_{1}&0\\\ 0&M_{2}\end{pmatrix}.$

It follows immediately that if $\mathcal{B}$ is non-degenerate, then so is
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$}$.

For (ii), we have $b\neq 0$ and $c=0$. We show

$M_{1}=\begin{pmatrix}a&b\\\ b&0\end{pmatrix}\sim\begin{pmatrix}1&0\\\
0&-1\end{pmatrix},$

which proves
$\varepsilon(\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$})=\varepsilon(\mathcal{B})$.

Let $\alpha,\beta,\gamma$ be solutions to $\alpha^{2}-\gamma^{2}=a$ and
$\beta(\alpha-\gamma)=b$. Such $\alpha,\gamma$ exist because every element of
${\mathbb{F}}_{q}$ is the difference of two squares. The characteristic is not
2, so we can always take $\alpha\neq\gamma$ (even when $a=0$). Then there
exists a suitable $\beta$. Now a simple calculation confirms

$\begin{pmatrix}\alpha&\beta\\\
\gamma&\beta\end{pmatrix}^{T}\begin{pmatrix}1&0\\\
0&-1\end{pmatrix}\begin{pmatrix}\alpha&\beta\\\
\gamma&\beta\end{pmatrix}=\begin{pmatrix}\alpha^{2}-\gamma^{2}&\beta(\alpha-\gamma)\\\
\beta(\alpha-\gamma)&0\end{pmatrix}=\begin{pmatrix}a&b\\\ b&0\end{pmatrix};$

and $\det\begin{pmatrix}\alpha&\beta\\\
\gamma&\beta\end{pmatrix}=\beta(\alpha-\gamma)=b\neq 0$.

For (iii), we have $b=1$ and $a=c=0$. Therefore $M_{1}=H$. So ${\mathcal{B}}$
is equivalent to ${\mathcal{H}}$ if and only if
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$}$
is equivalent to ${\mathcal{H}}$. ∎

######  Remark 3.8.

The condition in part (i) of Lemma 3.7 is necessary. Take, for example, $n=4$
and ${\mathcal{B}}$ the bilinear form given by the diagonal matrix with
diagonal entries $(1,-1,1,-1)$. ${\mathcal{B}}$ is the dot product when $q=2$.
Take $\bm{v}=(1,0,0,0)$ and $\bm{w}=(1,1,1,0)$. These are two linearly
independent vectors with the numbers $a,b,c$ defined in the proof of the lemma
all equal to 1. Hence $ac=b^{2}$. It is not true that
$\langle\bm{v},\bm{w}\rangle$ trivially intersects
$\\{\bm{v},\bm{w}\\}^{\perp}$ because the span of $\bm{w}-\bm{v}=(0,1,1,0)$
lies in both subspaces. Furthermore, ${\mathcal{B}}$ restricted to
$\\{\bm{v},\bm{w}\\}^{\perp}$ is degenerate because $\bm{w}-\bm{v}$ is
orthogonal to both $\bm{w}-\bm{v}$ and $(0,0,0,1)$, which span
$\\{\bm{v},\bm{w}\\}^{\perp}$.

The next step is to bound the number of vectors in any $(3,2)$-orthogonal
subset in ${\mathbb{F}}_{q}^{n}$ that are not self-orthogonal. It may be true
that, analogously to the results of Rosenfeld and Deaett [16, 6], there are at
most $2n$ such vectors. We prove a weaker result that suffices for our
purposes. As part of the proof, we require a straightforward adaptation of [6,
Proposition 4.4], which we state. The proof is nearly identical to that in
[6].

######  Lemma 3.9.

Let $n\geq 1$ be a positive integer, $F$ be a field, and $S\subset F^{n}$ be a
$(3,2)$-orthogonal set with respect to a symmetric bilinear form. If $B\subset
S$ is an orthogonal basis for $F^{n}$, then $S\setminus B$ is an orthogonal
set.

We state and prove another result that is implicit in [6, Section 4]. It is
convenient to phrase many of the subsequent arguments in terms of the simple
graph $G$ with vertex set $S$ and edges given by pairs of elements of $S$ that
are not mutually orthogonal ($\bm{xy}$ is an edge precisely when
${\mathcal{B}}(\bm{x},\bm{y})\neq 0$).

######  Lemma 3.10.

Let $n\geq 1$ be a positive integer, $F$ a field, and $D\subset F^{n}$ be a
$(3,2)$-orthogonal set with respect to a symmetric bilinear form. If $D$
consists entirely of vectors that are not self-orthogonal, then

$|D|\leq\max\\{2n,R(3,n)-1\\}\overset{\eqref{eqn:Ramsey}}{=}\begin{cases}2n,&\mbox{if
}0\leq n\leq 4;\\\ \tfrac{n(n+1)}{2}-1,&\mbox{if }n\geq 5.\end{cases}$

###### Proof.

We use the graph $G$ described just above the statement of the lemma. The
claim is true for $n=0$. For $n\geq 1$ we observe that an independent set of
vertices is an orthogonal set in $F^{n}$ and so is linearly independent (we
need here that all vectors in $D$ are not self-orthogonal). If $G$ has an
independent set $B$ of size $n$, then that set is linearly independent and
therefore is a basis for $F^{n}$. By Lemma 3.9 we get that $D\setminus B$ is
orthogonal and hence contains at most $n$ elements. Hence $|D|=|B|+|D\setminus
B|\leq 2n$. If $G$, which is triangle-free, has no independent set of size
$n$, then $|D|<R(3,n)$, by the definition of $R(3,n)$. ∎

Note that by work of Ajtai, Komlós and Szemerédi, and of Kim [2, 11]

$R(3,n)=(1+o_{n\to\infty}(1))\frac{n^{2}}{\log n},$

with stronger explicit upper bounds in [17]. This means that $|D|=o(n^{2})$.

We also extract this consequence of Lemma 3.2 and Lemma 3.9 from the proof of
[1, Theorem 17].

######  Lemma 3.11.

Let $S\subset{\mathbb{F}}_{q}^{n}$ be a $(3,2)$-orthogonal set with respect to
a non-degenerate symmetric bilinear form ${\mathcal{B}}$. If every pair of
linearly independent vectors in $S$ is mutually orthogonal (that is
${\mathcal{B}}(\bm{x},\bm{y})=0$ for every linearly independent
$\\{\bm{v},\bm{w}\\}\subset S$), then
$|S|\leq{\mathcal{S}}_{2,2}(q,n,{\mathcal{B}})+n$.

As the final result of this section, we recall [1, Theorem 17], which is a
quantitatively weaker version of Theorem 2.1. We will use this result in
Section 5 and so provide a proof which follows the same scheme as that
introduced in [1], while paying special attention to certain intricacies
involved in carrying out the induction. In particular, the proof relies on
Lemma 3.7 to sidestep a potential issue that appears to have been overlooked
in the original proof of [1, Theorem 17]. It also serves as a prelude to the
proof of Theorem 2.1.

We employ for the first of many times a decomposition of a $(3,2)$-orthogonal
set $S$ that appears in [1], and so we describe it in detail. Given two
distinct elements $\bm{x},\bm{y}\in S$, every element of
$S\setminus\\{\bm{x},\bm{y}\\}$ is either not orthogonal to $\bm{x}$, or not
orthogonal to $\bm{y}$, or orthogonal to both $\bm{x}$ and $\bm{y}$. Using the
notation of Lemma 3.5 we decompose $S$ as follows

(8) $S=S_{\bm{x}}\cup S_{\bm{y}}\cup S_{\bm{x}\bm{y}}\cup\\{\bm{x},\bm{y}\\},$

where $S_{\bm{x}}$ and $S_{\bm{y}}$ are defined in (7) and
$S_{\bm{x}\bm{y}}=S\cap\\{\bm{x},\bm{y}\\}^{\perp}$. Note that
$\\{\bm{x},\bm{y}\\}$ can be left out if ${\mathcal{B}}(\bm{x},\bm{y})\neq 0$
because $\bm{x}\in S_{\bm{y}}$ and vice versa. When bounding
$|S_{\bm{x}\bm{y}}|$ by induction it is essential that
${\mathcal{B}}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{x},\bm{y}\\}^{\perp}$}$
is non-degenerate.

######  Proposition 3.12.

Let $q$ be odd and let ${\mathcal{B}}$ be a non-degenerate symmetric bilinear
form over ${\mathbb{F}}_{q}^{n}$. If
$S\subset{\mathbb{F}}_{q}^{n}\setminus\\{\bm{0}\\}$ is $(3,2)$-orthogonal,
then

$|S|\leq 3q^{\lfloor\frac{n}{2}\rfloor}.$

###### Proof.

We proceed by induction on $n$. Note that the result is true for
$n\in\\{0,1\\}$ because $|S|\leq 2$ and assume it is also true for all
dimensions strictly less than $n$.

If every linearly independent pair of vectors in $S$ is mutually orthogonal,
by Lemma 3.11 and Lemma 3.3, we have

$|S|\leq{\mathcal{S}}_{2,2}(q,n,{\mathcal{B}})+n\leq
2q^{\lfloor\frac{n}{2}\rfloor}.$

Hence suppose there exists a linearly independent pair
$\\{\bm{x},\bm{y}\\}\subset S$, with ${\mathcal{B}}(\bm{x},\bm{y})\not=0$. If
at least one of these vectors is self-orthogonal, by Lemma 3.7 (i),
${\mathcal{B}}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{x},\bm{y}\\}^{\perp}$}$
is non-degenerate. Recalling the decomposition (8) and noting that $\bm{x}\in
S_{\bm{y}}$ and $\bm{y}\in S_{\bm{x}}$, we have

$|S|\leq|S_{\bm{x}}|+|S_{\bm{y}}|+|S_{\bm{xy}}|.$

Since $\bm{x}$ and $\bm{y}$ are linearly independent,
$\\{\bm{x},\bm{y}\\}^{\perp}$ constitutes a subspace of ${\mathbb{F}}_{q}^{n}$
of dimension $n-2$. Then, using that
$S_{\bm{xy}}\subset\\{\bm{x},\bm{y}\\}^{\perp}$, for $n\in\\{2,3\\}$ we have
$|S_{\bm{xy}}|\leq q^{n-2}\leq q$ and for $n\geq 4$ we have $|S_{\bm{xy}}|\leq
3q^{\lfloor\frac{n}{2}\rfloor-1}$ by the induction hypothesis. Furthermore, by
Lemma 3.3 and Lemma 3.5, we have $|S_{\bm{x}}|,|S_{\bm{y}}|\leq
q^{\lfloor\frac{n}{2}\rfloor}$. Adding this all up, we obtain the required
result in this case.

Next, suppose that neither $\bm{x}$ nor $\bm{y}$ is self-orthogonal and note
that in this case, we may no longer assume
${\mathcal{B}}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{x},\bm{y}\\}^{\perp}$}$
is non-degenerate (see Remark 3.8). If every pair of elements of $S_{\bm{xy}}$
is mutually orthogonal, by Lemma 3.3, we have $|S_{\bm{xy}}|\leq
q^{\lfloor\frac{n}{2}\rfloor}$ and the required result follows. Hence suppose
there exist $\bm{v},\bm{w}\in S_{\bm{xy}}$, with
${\mathcal{B}}(\bm{v},\bm{w})\not=0$. Again, if at least one of
$\\{\bm{v},\bm{w}\\}$ is self-orthogonal, we may repeat the arguments of the
first case to obtain the required result. Thus assume otherwise. Consider the
decomposition

(9) $S=S_{\bm{x}}\cup S_{\bm{v}}\cup S_{\bm{xv}}\cup\\{\bm{x},\bm{v}\\}.$

By Lemma 3.7 (i),
${\mathcal{B}}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{x},\bm{v}\\}^{\perp}$}$
is non-degenerate. Employing the notation of Lemma 3.5, note that $\bm{y}\in
T_{\bm{x}}$ and $\bm{w}\in T_{\bm{v}}$. Suppose there exists $\bm{z}\in
R_{\bm{v}}$, with ${\mathcal{B}}(\bm{y},\bm{z})\not=0$. Then by Lemma 3.7 (i),
${\mathcal{B}}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{y},\bm{z}\\}^{\perp}$}$
is non-degenerate and we may repeat the arguments of the first case, with
$\bm{z}$ in place of $\bm{x}$, to obtain the required result. Otherwise, if
$\bm{y}$ is orthogonal to $R_{\bm{v}}$, it follows that
$R_{\bm{v}}\sqcup\\{\bm{y},\bm{w}\\}$ is an orthogonal set, which by Lemma
3.2, implies that $\dim(V_{\bm{v}})\leq\lfloor n/2\rfloor-1$. By a similar
argument, we may assume $R_{\bm{x}}\sqcup\\{\bm{y},\bm{w}\\}$ is an orthogonal
set and that $\dim(V_{\bm{x}})\leq\lfloor n/2\rfloor-1$. Furthermore note that
$\bm{w}\in S_{\bm{xy}}$ and so $\bm{w}\not\in S_{\bm{x}}$ and similarly
$\bm{y}\not\in S_{\bm{v}}$.

For $n\in\\{2,3\\}$, by Lemma 3.2 and the above observations, we have
$|S_{\bm{x}}\cup S_{\bm{v}}|\leq 2n-2$ and $|S_{\bm{xv}}|\leq q$. Thus going
back to (9), we get $|S|\leq 2n+q\leq 3q$ as required. For $n\geq 4$, we may
again use Lemma 3.2 to see $|S_{\bm{x}}\cup S_{\bm{v}}|\leq 2(q^{\lfloor
n/2\rfloor-1}+3)-2$. Then

$\displaystyle|S|$ $\displaystyle\leq(2q^{\lfloor
n/2\rfloor-1}+4)+3q^{\lfloor\frac{n}{2}\rfloor-1}+2$
$\displaystyle=5q^{\lfloor n/2\rfloor-1}+6$ $\displaystyle\leq 3q^{\lfloor
n/2\rfloor},$

for all $n\geq 4$ and $q\geq 3$. ∎

##  4\. Proof of Theorem 2.1

We set

$d_{n}=\begin{cases}\frac{n-1}{2},&\mbox{if }n\geq 3\ \text{is odd};\\\
\frac{n}{2},&\mbox{if }n\geq 2\ \text{is even and}\
\varepsilon(\mathcal{B})=1;\\\ \frac{n}{2}-1,&\mbox{if }n\geq 2\ \text{is even
and}\ \varepsilon(\mathcal{B})=\gamma.\end{cases}$

It was proved in [21] that $d_{n}$ is the dimension of the largest orthogonal
subspace of ${\mathbb{F}}_{q}^{n}$ (also follows from Lemma 3.2). Note that
$d_{n-2}=d_{n}-1$.

We proceed by induction on $n$. For $n=0$ and $n=1$ the size of the largest
$(3,2)$-orthogonal set is at most 2, and the theorem follows.

We will show that either $|S|\leq q^{d_{n}}+O(q^{d_{n}-1})$ or that $S$
possesses certain properties that make proving the theorem a matter of case
analysis. For sufficiently large $q$ the former upper bound is smaller than
the one in the theorem.

We phrase the argument in terms of the graph $G$ with vertex set $S$ and two
vectors adjacent precisely when they are not mutually orthogonal. The two
properties of $G$ we use is that it is triangle free (follows from $S$ being
$(3,2)$-orthogonal) and the largest independent set in $G$ having size at most
$\mathcal{S}_{2,2}(q,n,{\mathcal{B}})$ (because an independent set is an
orthogonal subset of ${\mathbb{F}}_{q}^{n}$). We will also use the fact that
every orthogonal set in ${\mathbb{F}}_{q}^{n}$ has size at most
$\mathcal{S}_{2,2}(q,n,{\mathcal{B}})$, a quantity that is determined in Lemma
3.3.

By Lemma 3.11 we may assume from now on the existence of linearly independent
$\\{\bm{v},\bm{w}\\}\subset S$ with $\bm{vw}$ an edge (that is
${\mathcal{B}}(\bm{v},\bm{w})\neq 0$). This is because $n\leq q^{d_{n}}-2$ for
all $n\geq 2$ when $q\geq 5$. We decompose $S$ in the neighbourhood
$S_{\bm{v}}$ of $\bm{v}$, the neighbourhood $S_{\bm{w}}$ of $\bm{w}$, and the
set of vertices $S_{\bm{v}\bm{w}}$ that are not adjacent to either $\bm{v}$ or
$\bm{w}$:

$S=S_{\bm{v}}\cup S_{\bm{w}}\cup S_{\bm{vw}},$

where $S_{\bm{vw}}\subset\\{\bm{v},\bm{w}\\}^{\perp}$. We follow the set up of
Lemma 3.5 and decompose $S_{\bm{v}}=R_{\bm{v}}\sqcup T_{\bm{v}}$ with
$R_{\bm{v}}$ spanning the orthogonal vector space $V_{\bm{v}}$.

When $n=2$ we get that $S_{\bm{vw}}$ is a subset of a zero dimensional vector
space that does not include $\bm{0}$ and so is empty. Since both $S_{\bm{v}}$
and $S_{\bm{w}}$ are orthogonal sets, we get $|S|\leq
2\mathcal{S}_{2,2}(q,2,{\mathcal{B}})$. This proves the theorem for $n=2$.

For $n\geq 3$ we have to be more careful when dealing with $S_{\bm{vw}}$. We
need the following to be able to apply the second part of Lemma 3.7.

######  Lemma 4.1.

For $n\geq 3$, let $S\subset{\mathbb{F}}_{q}^{n}$ be a $(3,2)$-orthogonal set
with respect to a non-degenerate symmetric bilinear form ${\mathcal{B}}$. If
every pair of linearly independent self-orthogonal vectors in $S$ is
orthogonal to one another (that is ${\mathcal{B}}(\bm{x},\bm{y})=0$ for all
linearly independent self-orthogonal $\bm{x},\bm{y}\in S$), then

$|S|\leq\begin{cases}{\mathcal{S}}_{2,2}(q,n,{\mathcal{B}})+2n,&\mbox{if
}0\leq n\leq 4;\\\
{\mathcal{S}}_{2,2}(q,n,{\mathcal{B}})+\tfrac{n(n+1)}{2}-1,&\mbox{if }n\geq
5.\end{cases}$

###### Proof.

Let $D$ be the set of vectors in $S$, which are not self-orthogonal:

$D=\\{\bm{x}\in S:{\mathcal{B}}(\bm{x},\bm{x})\neq 0\\}.$

By the hypothesis on $S$ we have that $S\setminus D$ is an orthogonal set.
Hence $|S\setminus D|\leq{\mathcal{S}}_{2,2}(q,n,{\mathcal{B}})$. The claim
follows by bounding $|D|$ via Lemma 3.10. ∎

The upper bound on $|S|$ in Lemma 4.1 is smaller than the bound in Theorem 2.1
for $n\geq 3$ when $q\geq 5$. From now on we assume the existence of linearly
independent vectors $\\{\bm{v},\bm{w}\\}$ that are self-orthogonal but are not
mutually orthogonal:

${\mathcal{B}}(\bm{v},\bm{v})={\mathcal{B}}(\bm{w},\bm{w})=0\text{, but
}{\mathcal{B}}(\bm{v},\bm{w})\neq 0.$

Recalling the definition of $f=f(q,n,{\mathcal{B}})$ inferred from Theorem 2.1
and (5), we get from Lemma 3.7 (ii)

(10) $|S_{\bm{vw}}|\leq 2q^{d_{n-2}}+f=2q^{d_{n}-1}+f.$

Therefore $|S_{\bm{vw}}|$ is much smaller than the bound on $|S|$ we are
trying to prove. What drives the proof is that if either $V_{\bm{v}}$ or
$V_{\bm{w}}$ is not of maximum dimension, then we are done. To see why,
suppose $V_{\bm{v}}$ is not of maximum dimension. Then using Lemma 3.2, Lemma
3.3, Lemma 3.5 and (10) we get

$\displaystyle|S|$ $\displaystyle\leq|S_{\bm{v}}|+|S_{\bm{w}}|+|S_{\bm{vw}}|$
$\displaystyle\leq(q^{d_{n}-1}+3)+(q^{d_{n}}+1)+(2q^{d_{n}-1}+f)$
$\displaystyle=q^{d_{n}}+3q^{d_{n}-1}+4+f.$

Since for $q\geq 7$ we have $3q^{d_{n}-1}+4\leq q^{d_{n}}$, we assume from now
on $\dim(V_{\bm{v}})=\dim(V_{\bm{w}})=d_{n}$.

One more property we need is that $\bm{v}\in V_{\bm{w}}$ and $\bm{w}\in
V_{\bm{v}}$. To confirm, say the latter, note that there is no edge from
$\bm{w}$ to $R_{\bm{v}}$ (because the graph is triangle-free). Therefore
$\bm{w}\perp\langle R_{\bm{v}}\rangle=V_{\bm{v}}$. By Lemma 3.6 (ii), and
using the fact that $\bm{w}$ is self-orthogonal, we get $\bm{w}\in
V_{\bm{v}}$.

We summarise all this in a proposition.

######  Proposition 4.2.

Let $q\geq 7$ be an odd prime power, $n\geq 3$ and
$S\subset{\mathbb{F}}_{q}^{n}$ be a $(3,2)$-orthogonal set with respect to a
non-degenerate symmetric bilinear form. Then $|S|$ satisfies the upper bound
of Theorem 2.1 unless there exist linearly independent self-orthogonal vectors
$\bm{v}$ and $\bm{w}$ with $\dim(V_{\bm{v}})=\dim(V_{\bm{w}})=d_{n}$; and
$\bm{v}\in V_{\bm{w}}$ and $\bm{w}\in V_{\bm{v}}$. In this case
$S_{\bm{vw}}=S\cap\\{\bm{v},\bm{w}\\}^{\perp}$ satisfies $|S_{\bm{vw}}|\leq
2q^{d_{n}-1}+f(q,n,{\mathcal{B}})$, with $f(q,n,{\mathcal{B}})$ inferred from
Theorem 2.1 and (5).

The final preparatory result is that for the remaining $S$ described in
Proposition 4.2, $R_{\bm{z}}$ is considerably smaller than $q^{d_{n}}$ for all
$\bm{z}\in S_{\bm{vw}}$. The proof is typical of forthcoming considerations.
The key observation is that if a subspace of a vector space does not contain a
single element of the vector space, then it is considerably smaller.

######  Lemma 4.3.

Let $q$ be an odd prime power and let $S\subset{\mathbb{F}}_{q}^{n}$ be
$(3,2)$-orthogonal with respect to a non-degenerate symmetric bilinear form
${\mathcal{B}}$. Suppose $\\{\bm{v},\bm{w}\\}\subset S$ is a linearly
independent subset that consists of two self-orthogonal vectors that are not
mutually orthogonal (that is
${\mathcal{B}}(\bm{v},\bm{v})={\mathcal{B}}(\bm{w},\bm{w})=0$, but
${\mathcal{B}}(\bm{v},\bm{w})\neq 0$). If $\bm{z}\in
S_{\bm{vw}}=S\cap\\{\bm{v},\bm{w}\\}^{\perp}$, then

$|R_{\bm{z}}|\leq 3q^{d_{n}-1}-3.$

###### Proof.

We have

$S\subset(V_{\bm{v}}\setminus\\{\bm{0}\\})\cup
T_{\bm{v}}\cup(V_{\bm{w}}\setminus\\{\bm{0}\\})\cup T_{\bm{w}}\cup
S_{\bm{vw}}.$

By Lemma 3.5 we know that $R_{\bm{z}}$ contains only self-orthogonal vectors
and so is disjoint from $T_{\bm{v}}\cup T_{\bm{w}}$. Hence

$|R_{\bm{z}}|\leq(|V_{\bm{v}}\cap V_{\bm{z}}|-1)+(|V_{\bm{w}}\cap
V_{\bm{z}}|-1)+|R_{\bm{z}}\cap S_{\bm{vw}}|.$

$V_{\bm{v}}\neq V_{\bm{z}}$ because $\bm{w}\in V_{\bm{v}}\setminus
V_{\bm{z}}$. Hence $V_{\bm{v}}\cap V_{\bm{z}}$ is a proper subspace of
$V_{\bm{v}}$ and is therefore not of maximum dimension. This means
$|V_{\bm{z}}\cap V_{\bm{v}}|\leq q^{d_{n}-1}$. Similarly $|V_{\bm{z}}\cap
V_{\bm{w}}|\leq q^{d_{n}-1}$. Moreover, note that $R_{\bm{z}}\cap S_{\bm{vw}}$
is an orthogonal subset of $\\{\bm{v},\bm{w}\\}^{\perp}$, on which non-
degeneracy and type of ${\mathcal{B}}$ is preserved by Lemma 3.7 (ii). Thus by
Lemma 3.2, we have $|R_{\bm{z}}\cap S_{\bm{vw}}|\leq q^{d_{n}-1}-1$. Putting
everything together gives the desired bound. ∎

We begin the final stage of the proof of the theorem. We assume we are in the
remaining case detailed in Proposition 4.2. Let

$S_{\bm{vw}}^{*}=S_{\bm{vw}}\setminus(V_{\bm{v}}\cup V_{\bm{w}}).$

We distinguish between two different cases.

Case 1: An edge exists between $R_{\bm{v}}\cup R_{\bm{w}}$ and
$S_{\bm{vw}}^{*}$.

Suppose $\bm{uz}$ is an edge with $\bm{z}\in S_{\bm{vw}}$ and, say, $\bm{u}\in
R_{\bm{v}}$. Our first claim is that $\\{\bm{u},\bm{z}\\}$ is linearly
independent. Indeed if $\bm{z}=\lambda\bm{u}$, then we would have
${\mathcal{B}}(\bm{z},\bm{u})=\lambda B(\bm{u},\bm{u})=0$, which contradicts
$\bm{uz}$ being an edge. Furthermore, $\bm{u}$ is self-orthogonal and so by
Lemma 3.7 (ii) we get that
${\mathcal{B}}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{u},\bm{z}\\}^{\perp}$}$
is non-degenerate and $\varepsilon({\mathcal{B}})$ is preserved.

We have

$|S|\leq|S_{\bm{u}}|+|R_{\bm{z}}|+|T_{\bm{z}}|+|S_{\bm{uz}}|.$

We have the following bounds: by Lemma 3.3 and Lemma 3.5 $|S_{\bm{u}}|\leq
q^{d_{n}}+1$; by Lemma 3.2 and Lemma 4.3 (and its proof),
$|R_{\bm{z}}|+|T_{\bm{z}}|\leq 3q^{d_{n}-1}+1$; and by induction, just like in
(10), $|S_{\bm{uz}}|\leq 2q^{d_{n}-1}+f$. In total

$|S|\leq q^{d_{n}}+5q^{d_{n}-1}+2+f.$

We are done because for $q\geq 7$ and $n\geq 3$, $5q^{d_{n}-1}+2\leq
q^{d_{n}}$.

Case 2: No edge exists between $R_{\bm{v}}\cup R_{\bm{w}}$ and
$S_{\bm{vw}}^{*}$.

There is no edge from $S_{\bm{vw}}^{*}$ to $R_{\bm{v}}$ and therefore
$S_{\bm{vw}}^{*}$ is orthogonal to $R_{\bm{v}}$. It follows that $S_{vw}^{*}$
is orthogonal to $V_{\bm{v}}=\langle R_{\bm{v}}\rangle$. Similarly,
$S_{vw}^{*}$ is orthogonal to $V_{\bm{w}}$. All vectors in $T_{\bm{v}}\cup
T_{\bm{w}}\cup S_{\bm{vw}}$ are not self-orthogonal by Lemma 3.6 (ii) and
$\dim(V_{\bm{v}})$ being maximum. We use the decomposition

(11)
$S\subset(V_{\bm{v}}\setminus\\{\bm{0}\\})\cup(V_{\bm{w}}\setminus\\{\bm{0}\\})\cup(T_{\bm{v}}\cup
T_{\bm{w}}\cup S_{\bm{vw}}).$

We consider the three different possibilities separately.

Even $n\geq 4$ and $\varepsilon({\mathcal{B}})=1$. Our aim is to show that
$T_{\bm{v}}=T_{\bm{w}}=S_{\bm{vw}}^{*}=\emptyset$. Then by (11)

$|S|\leq(|V_{\bm{v}}|-1)+(|V_{\bm{w}}|-1)\leq 2(q^{d_{n}}-1)=2q^{n/2}-2.$

We may assume $T_{\bm{v}}=T_{\bm{w}}=\emptyset$ else, by Lemma 3.2,
$V_{\bm{v}}$ or $V_{\bm{w}}$ are not of maximum dimension, which is not
allowed by Proposition 4.2. To show that $S_{\bm{vw}}^{*}=\emptyset$, suppose
for a contradiction that $\bm{z}\in S_{\bm{vw}}^{*}$, then
$V_{\bm{v}}\cup\\{\bm{z}\\}$ would be an orthogonal set, forcing, via Lemma
3.2, $V_{\bm{v}}$ not to have maximum dimension.

Odd $n\geq 3$. We want to show
$|T_{\bm{v}}|+|T_{\bm{w}}|+|S_{\bm{vw}}^{*}|\leq 3$. Then by (11)

$|S|\leq(|V_{\bm{v}}|-1)+(|V_{\bm{w}}|-1)+3\leq 2q^{d_{n}}+1=2q^{(n-1)/2}+1.$

For any distinct $\bm{x},\bm{y}\in S_{\bm{vw}}^{*}$, $\bm{xy}$ is an edge.
This is because if $\bm{xy}$ were not an edge, then
$V_{\bm{v}}\cup\\{\bm{x},\bm{y}\\}$ would be an orthogonal set of size
$|V_{\bm{v}}|+2$, which, by Lemma 3.2, would force $V_{\bm{v}}$ not to have
maximum dimension. Therefore the induced subgraph on $S_{\bm{vw}}^{*}$ is
complete and triangle-free. Hence $S_{\bm{vw}}^{*}$ must have at most two
vertices. Moreover, by Lemma 3.2, $|T_{\bm{v}}|,|T_{\bm{w}}|\leq 1$ (else the
subspaces do not have maximum dimension). We are done unless
$|S_{\bm{vw}}^{*}|=|T_{\bm{v}}\cup T_{\bm{w}}|=2$. Suppose
$S_{\bm{vw}}^{*}=\\{\bm{x},\bm{y}\\}$ with $\bm{xy}$ an edge, and
$T_{\bm{v}}=\\{\bm{u}\\}$. The graph is triangle-free and so one of $\bm{ux}$,
$\bm{uy}$ is not an edge. Suppose that $\bm{ux}$ is not an edge. Then
$V_{\bm{v}}\cup\\{\bm{u},\bm{x}\\}$ is an orthogonal set, forcing $V_{\bm{v}}$
not to be of maximal dimension.

Even $n\geq 4$ and $\varepsilon({\mathcal{B}})=\gamma$. We want to show
$|T_{\bm{v}}|+|T_{\bm{w}}|+|S_{\bm{vw}}^{*}|\leq 6$. Then by (11)

$|S|\leq(|V_{\bm{v}}|-1)+(|V_{\bm{w}}|-1)+6\leq 2q^{d_{n}}+4=2q^{n/2-1}+4.$

In fact, by Lemma 3.2 and Proposition 4.2, $|T_{\bm{w}}|\leq 2$ and we must
show $|T_{\bm{v}}|+|S_{\bm{vw}}^{*}|\leq 4$.

Note that every vertex in $T_{\bm{v}}\cup S_{\bm{vw}}^{*}$ is orthogonal to
$R_{\bm{v}}$ and therefore is orthogonal to $V_{\bm{v}}$. Similarly,
$S_{\bm{vw}}^{*}$ is orthogonal to $\langle V_{\bm{v}}\cup
V_{\bm{w}}\rangle=V_{\bm{v}}+V_{\bm{w}}$. Now consider the graph $H$ induced
on $T_{\bm{v}}\cup S_{\bm{vw}}^{*}$. This is a triangle-free graph. Moreover,
it has no independent set of size 3 because otherwise we could join this set
to $V_{\bm{v}}$ and obtain an orthogonal set of size $|V_{\bm{v}}|+3$, which
would force $V_{\bm{v}}$ not to have maximum dimension. By Lemma 3.1 we get
$|T_{\bm{v}}\cup S_{\bm{vw}}^{*}|\leq 5$ with equality only when $H$ is a
5-cycle. Our final task is to rule out this possibility. Suppose for a
contradiction that $H$ is a 5-cycle.

We set $T_{\bm{v}}=\\{\bm{u}_{1},\bm{u}_{2}\\}$ and
$S_{\bm{vw}}^{*}=\\{\bm{z}_{1},\bm{z}_{2},\bm{z}_{3}\\}$.
$\bm{u}_{1}\bm{u}_{2}$ is not an edge (because both $\bm{u}_{1},\bm{u}_{2}$
are incident to $\bm{v}$) and so $H$ can be taken to be the 5-cycle
$\bm{z}_{1}\bm{u}_{1}\bm{z}_{2}\bm{u}_{2}\bm{z}_{3}$. The complement of $H$ is
the 5-cycle $\bm{z}_{1}\bm{z}_{2}\bm{z}_{3}\bm{u}_{1}\bm{u}_{2}$. In the
complement of $H$ vertex adjacency is equivalent to orthogonality, and so
$\\{\bm{z}_{1},\bm{z}_{2}\\}\subset(V_{\bm{v}}+V_{\bm{w}})^{\perp}$ is an
orthogonal (and hence linearly independent) set in the orthogonal complement
of $V_{\bm{v}}+V_{\bm{w}}$.

We make a small digression to investigate the dimension of
$V_{\bm{v}}+V_{\bm{w}}$. We may assume $V_{\bm{v}}\cap
V_{\bm{w}}=\\{\bm{0}\\}$. This is because if the intersection is non-trivial,
then

$|S|\leq|(V_{\bm{v}}\cup
V_{\bm{w}})\setminus\\{\bm{0}\\}|+|T_{\bm{v}}|+|T_{\bm{w}}|+|S_{\bm{vw}}^{*}|\leq(2q^{d_{n}}-q)+7\leq
2q^{d_{n}}+4,$

and we are done. We may therefore assume that
$\dim(V_{\bm{v}}+V_{\bm{w}})=2d_{n}=n-2$ and hence

${\mathbb{F}}_{q}^{n}=(V_{\bm{v}}+V_{\bm{w}})\oplus\langle\bm{z}_{1}\rangle\oplus\langle\bm{z}_{2}\rangle.$

To complete the argument we exploit the orthogonality relations encoded in the
complement of $H$ and show that $\bm{z_{3}}=\bm{0}$, the contradiction we are
after. To start note that $\bm{z}_{3}\in\langle\bm{z}_{1},\bm{z}_{2}\rangle$.
As $\bm{z}_{3}$ is orthogonal to $\bm{z}_{2}$, we get
$\bm{z}_{3}=\lambda\bm{z}_{1}$. We are left to show $\lambda=0$.

We next show $\bm{u}_{1},\bm{u}_{2}\in
V_{\bm{v}}\oplus\langle\bm{z}_{1},\bm{z}_{2}\rangle$. Let’s start with, say,
the decomposition

$\bm{u}_{1}=\alpha\bm{z}_{1}+\beta\bm{z}_{2}+\bm{x}_{\bm{v}}+\bm{x}_{\bm{w}},$

for $\alpha,\beta\in{\mathbb{F}}_{q}$, $\bm{x}_{\bm{v}}\in V_{\bm{v}}$, and
$\bm{x}_{\bm{w}}\in V_{\bm{w}}$. Suppose for a contradiction that
$\bm{x}_{\bm{w}}\neq\bm{0}$. By Lemma 3.6 (ii) and the maximality of
$\dim(V_{\bm{v}})$ we get that the self-orthogonal vector $\bm{x}_{\bm{w}}$ is
not orthogonal to $V_{\bm{v}}$. Therefore there exists $\bm{y}\in
V_{\bm{v}}\setminus\\{\bm{0}\\}$ such that
${\mathcal{B}}(\bm{x}_{\bm{w}},\bm{y})\neq 0$. But then

${\mathcal{B}}(\bm{u}_{1},\bm{y})={\mathcal{B}}(\bm{x}_{\bm{w}},\bm{y})\neq
0,$

a contradiction to $\bm{u}_{1}$ being orthogonal to the whole of $V_{\bm{v}}$.
We therefore have

$\bm{u}_{1}=\alpha\bm{z}_{1}+\beta\bm{z}_{2}+\bm{x}_{\bm{v}}\text{ and
}\bm{u}_{2}=\alpha^{\prime}\bm{z}_{1}+\beta^{\prime}\bm{z}_{2}+\bm{x}_{\bm{v}}^{\prime}.$

Now, $\bm{u}_{2}$ is orthogonal to $\bm{z_{1}}$ and so
$0=\alpha^{\prime}{\mathcal{B}}(\bm{z}_{1},\bm{z}_{1})$, which gives
$\alpha^{\prime}=0$. Moreover $\bm{u}_{2}\notin V_{\bm{v}}$, which gives
$\beta^{\prime}\neq 0$. Next, $\bm{u}_{2}$ is orthogonal to $\bm{u}_{1}$ and
so $0=\beta\beta^{\prime}{\mathcal{B}}(\bm{z}_{2},\bm{z}_{2})$. Hence
$\beta=0$ and, similarly to above,
$\bm{u}_{1}=\alpha\bm{z}_{1}+\bm{x}_{\bm{v}}$ for
$\alpha\in{\mathbb{F}}_{q}^{*}$. Finally, $\bm{u}_{1}$ is orthogonal to
$\bm{z}_{3}=\lambda\bm{z}_{1}$. Hence
$0=\lambda\alpha{\mathcal{B}}(\bm{z}_{1},\bm{z}_{1})$, which implies the
desired $\lambda=0$.

The graph $H$ is therefore not a 5-cycle and consequently $|T_{\bm{v}}\cup
S_{\bm{vw}}^{*}|\leq 4$. The proof of the theorem is concluded.

##  5\. Character sum proof of Theorem 2.1 for even $n$,
$\varepsilon({\mathcal{B}})=1$ and all odd $q$

First, we recall some basic facts from the theory of character sums, which we
use to give an alternative proof of Theorem 2.1 for even $n$ and
$\varepsilon({\mathcal{B}})=1$ that holds for all odd $q$. See, for example,
[13, Chapter 5] for more details.

######  Lemma 5.1.

Let $H$ be a subgroup of a finite abelian group $G$ and $\chi$ a character of
$G$, then

$\sum_{g\in H}\chi(g)=\begin{cases}|H|\quad&\text{if}\quad\chi\ \text{is
trivial on}\ H,\\\ 0\quad&\text{otherwise}.\end{cases}$

Let $e_{p}(x)=\exp(2\pi ix/p)$, $\mathrm{Tr}(x)=x+x^{p}+\dots+x^{p^{m-1}}$
(recalling $q=p^{m}$) and $\psi(x)=e_{p}(\mathrm{Tr}(x))$. Then the functions
$\\{\psi(\lambda x):\lambda\in{\mathbb{F}}_{q}\\}$ determine all of the
characters of ${\mathbb{F}}_{q}$.

######  Lemma 5.2.

Let $\mathcal{B}$ denote a non-degenerate, symmetric bilinear form over
${\mathbb{F}}_{q}^{n}$, where $q$ is odd and $n\geq 2$. Let $V$ denote a
subspace of ${\mathbb{F}}_{q}^{n}$. Suppose that $\bm{s}\not\in V^{\perp}$.
Then $\psi(\mathcal{B}(\bm{s},-))$ is a nontrivial character of $V$.

The next result is a slight extension of Vinogradov’s bound on bilinear
character sums, which appears, for example, in [22, p. 92]. Also see [18,
Lemma 5] for the special case, where ${\mathcal{B}}$ is the dot product.

######  Lemma 5.3.

Given $X,Y\subset{\mathbb{F}}_{q}^{n}$, we have

$\bigg{|}\sum_{\bm{x}\in X}\sum_{\bm{y}\in
Y}\psi\Big{(}\mathcal{B}(\bm{x},\bm{y})\Big{)}\bigg{|}\leq\sqrt{|X||Y|q^{n}}.$

###### Proof.

We apply the triangle inequality and then the Cauchy-Schwarz inequality to get

$\displaystyle\bigg{|}\sum_{\bm{x}\in X}\sum_{\bm{y}\in
Y}\psi\Big{(}\mathcal{B}(\bm{x},\bm{y})\Big{)}\bigg{|}^{2}$
$\displaystyle\leq|X|\sum_{\bm{x}\in X}\bigg{|}\sum_{\bm{y}\in
Y}\psi\Big{(}\mathcal{B}(\bm{x},\bm{y})\Big{)}\bigg{|}^{2}$
$\displaystyle\leq|X|\sum_{\bm{x}\in{\mathbb{F}}_{q}^{n}}\bigg{|}\sum_{\bm{y}\in
Y}\psi\Big{(}\mathcal{B}(\bm{x},\bm{y})\Big{)}\bigg{|}^{2}$
$\displaystyle=|X|\sum_{\bm{x}\in{\mathbb{F}}_{q}^{n}}\sum_{\bm{y},\bm{z}\in
Y}\psi\Big{(}\mathcal{B}(\bm{x},\bm{y}-\bm{z})\Big{)}$
$\displaystyle=|X|\sum_{\bm{y},\bm{z}\in
Y}\sum_{\bm{x}\in{\mathbb{F}}_{q}^{n}}\psi\Big{(}\mathcal{B}(\bm{x},\bm{y}-\bm{z})\Big{)}$
$\displaystyle=|X||Y|q^{n}.$

To obtain the last equality, we used the fact that the inner sum in the
penultimate line equals $q^{n}$ if $\bm{y}=\bm{z}$ and zero otherwise. This,
in turn, follows from the observation that
${{\mathbb{F}}_{q}^{n}}^{\perp}=\\{\bm{0}\\}$, combined with Lemmas 5.1 and
5.2. ∎

###### Proof of Theorem 2.1 for even $n$ and $\varepsilon({\mathcal{B}})=1$.

Firstly, replace $S$ by $S\sqcup\\{\bm{0}\\}$. This makes calculations easier.
We will take away $\bm{0}$ at the end of the proof. For $\bm{s}\in S$, write
$S^{{}^{\prime}}_{\bm{s}}=\\{\bm{x}\in S:\mathcal{B}(\bm{x},\bm{s})\not=0\\}$.
Also write $D=\\{\bm{x}\in S:\mathcal{B}(\bm{x},\bm{x})\not=0$}. Recalling
(7), note that

$\sum_{\bm{s}\in S}|S^{{}^{\prime}}_{\bm{s}}|=\sum_{\bm{s}\in
S}|S_{\bm{s}}|+|D|.$

Now

(12) $\displaystyle|S|^{2}-\sum_{\bm{s}\in S}|S_{\bm{s}}|-|D|$
$\displaystyle=|S|^{2}-\sum_{\bm{s}\in S}|S^{{}^{\prime}}_{\bm{s}}|$
$\displaystyle=\bigg{|}\sum_{\bm{s}_{1}\in S}\sum_{\bm{s}_{2}\in S\setminus
S^{{}^{\prime}}_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}.$

Here, we used just that for $\bm{s}_{1}\in S$ and $\bm{s}_{2}\in S\setminus
S^{{}^{\prime}}_{\bm{s}_{1}}$, we have
$\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))=1$. By the triangle inequality, we
also have

$\displaystyle\bigg{|}\sum_{\bm{s}_{1}\in S}\sum_{\bm{s}_{2}\in S\setminus
S^{{}^{\prime}}_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}$
$\displaystyle\leq\bigg{|}\sum_{\bm{s}_{1}\in S}\sum_{\bm{s}_{2}\in
S}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}+\bigg{|}\sum_{\bm{s}_{1}\in
S}\sum_{\bm{s}_{2}\in
S^{{}^{\prime}}_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}$
$\displaystyle\leq\bigg{|}\sum_{\bm{s}_{1}\in S}\sum_{\bm{s}_{2}\in
S}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}+\bigg{|}\sum_{\bm{s}_{1}\in
S}\sum_{\bm{s}_{2}\in
S_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}+|D|.$

Next, let $W=\\{\bm{x}\in S:|S_{\bm{x}}|\geq 2\\}$. Then, using Lemmas 3.2 and
3.5, we have

(13) $\displaystyle\bigg{|}\sum_{\bm{s}_{1}\in W}\sum_{\bm{s}_{2}\in
S_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}$
$\displaystyle\leq\bigg{|}\sum_{\bm{s}_{1}\in
W}\sum_{\bm{s}_{2}\in(V_{\bm{s}_{1}}\sqcup
T_{\bm{s}_{1}})}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}$
$\displaystyle+\bigg{|}\sum_{\bm{s}_{1}\in
W}\sum_{\bm{s}_{2}\in(V_{\bm{s}_{1}}\sqcup T_{\bm{s}_{1}})\setminus
S_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}.$

To bound the first sum, on the RHS of (13), we first apply the triangle
inequality to obtain

$\displaystyle\bigg{|}\sum_{\bm{s}_{1}\in
W}\sum_{\bm{s}_{2}\in(V_{\bm{s}_{1}}\sqcup
T_{\bm{s}_{1}})}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}$
$\displaystyle\leq\bigg{|}\sum_{\bm{s}_{1}\in W}\sum_{\bm{s}_{2}\in
V_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}+\bigg{|}\sum_{\bm{s}_{1}\in
W}\sum_{\bm{s}_{2}\in
T_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}.$

Note that for $\bm{s}\in W$, it follows from the definition of $V_{\bm{s}}$
(see Lemma 3.5) that $\bm{s}\not\in V_{\bm{s}}^{\perp}$. Thus, by Lemma 5.2,
$\psi(\mathcal{B}(\bm{s},-))$ constitutes a character of
${\mathbb{F}}_{q}^{n}$ which is nontrivial on the subspace $V_{\bm{s}}$.
Consequently, by Lemma 5.1, we have

$\sum_{\bm{x}\in
V_{\bm{s}}}\psi(\mathcal{B}(\bm{s},\bm{x}))=0\quad\implies\quad\sum_{\bm{s}_{1}\in
W}\sum_{\bm{s}_{2}\in
V_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))=0.$

Then, based on this observation and applications of the triangle inequality,
we obtain

$\displaystyle\bigg{|}\sum_{\bm{s}_{1}\in
W}\sum_{\bm{s}_{2}\in(V_{\bm{s}_{1}}\sqcup
T_{\bm{s}_{1}})}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}$
$\displaystyle\leq\bigg{|}\sum_{\bm{s}_{1}\in W}\sum_{\bm{s}_{2}\in
T_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}$
$\displaystyle\leq\sum_{\bm{s}_{1}\in W}\bigg{|}\sum_{\bm{s}_{2}\in
T_{\bm{s}_{1}}}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}$
$\displaystyle\leq\sum_{\bm{s}\in W}|T_{\bm{s}}|.$

The second sum, on the RHS of (13), is bounded trivially by

$\sum_{\bm{s}\in W}|V_{\bm{s}}|+|T_{\bm{s}}|-|S_{\bm{s}}|.$

Going back to (12), we have

$\displaystyle|S|^{2}\leq 2|D|+\bigg{|}\sum_{\bm{s}_{1}\in
S}\sum_{\bm{s}_{2}\in
S}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}+\sum_{\bm{s}\in
W}|V_{\bm{s}}|+2|T_{\bm{s}}|+\sum_{\bm{s}\in S\setminus{W}}2|S_{\bm{s}}|.$

By Lemma 5.3, we know

$\bigg{|}\sum_{\bm{s}_{1}\in S}\sum_{\bm{s}_{2}\in
S}\psi(\mathcal{B}(\bm{s}_{1},\bm{s}_{2}))\bigg{|}\leq|S|q^{n/2}.$

For $\bm{s}\in W$, write $k_{\bm{s}}=\dim(V_{\bm{s}})$. Then by Lemma 3.2, we
know $|V_{\bm{s}}|+2|T_{\bm{s}}|\leq q^{k_{\bm{s}}}+2n-4k_{\bm{s}}\leq
q^{n/2}.$ Furthermore, for $\bm{s}\in S\setminus{W}$, we have
$2|S_{\bm{s}}|\leq q^{n/2}$. So adding it all up,

$|S|^{2}\leq 2|S|q^{n/2}+2|D|.$

At this stage we go back to the original $S$ that does not include $\bm{0}$.
The above becomes

(14) $|S|\leq 2q^{n/2}+\Big{\lfloor}\frac{2|D|}{|S|}\Big{\rfloor}-1.$

Note that from (14), one can only deduce the bound $|S|\leq 2q^{n/2}+1$.
However, we proceed to sharpen this bound through an analysis of the set $D$.
Some aspects of the remaining arguments can certainly be simplified if we are
not aiming to prove the theorem for all $q$. To deal with some small
technicalities that follow, we require the bound

(15) $|S|\leq 2(q-1),$

for $n=2$, all odd $q$ and either scenarios
$\varepsilon({\mathcal{B}})\in\\{1,\gamma\\}$. This bound has already been
established as the base case of the induction in the proof of Theorem 2.1111In
the proof of Theorem 2.1, when applying Lemma 3.11, to avoid a lengthy multi-
case analysis, it is assumed that $q>3$. However one may easily confirm that,
for our purposes here, the argument remains valid when $q=3$.. In particular,
henceforth assume $n\geq 4$.

First we establish

(16) $|S|\leq 2q^{n/2}-1,$

which follows from (14) if $2|D|<|S|$. So suppose otherwise. Using the bound
on $|D|$ provided by Lemma 3.10, we get $|S|\leq 16$ for $n=4$ and $|S|\leq
n(n+1)-2$ with both being better than (16) for all $q\geq 3$ and $n\geq 4$.

It remains to show (16) may be lowered by one. To this end, we consider a few
cases showing that the assumption $|S|=2q^{n/2}-1$ leads to contradictions on
either the size or the parity of $|S|.$ In particular, the following
observations will be useful.

######  Claim 5.4.

Let $S\subset{\mathbb{F}}_{q}^{n}$ denote a maximal $(3,2)$-orthogonal set.
Then $|S\setminus D|\equiv 0\pmod{q-1}$.

###### Proof.

Each $\bm{v}\in S\setminus D$ is self-orthogonal and so $S$ must contain the
entire punctured line
$l_{\bm{v}}=\\{\lambda\bm{v}:\lambda\in{\mathbb{F}}_{q}^{*}\\}$, otherwise
maximality of $S$ is violated. The result follows noting that $l_{\bm{v}}\cap
l_{\bm{w}}$ is empty if $\bm{w}\not\in l_{\bm{v}}$ and of size $q-1$
otherwise. ∎

######  Claim 5.5.

At least one of the following statements holds.

  1. (i)

$|S|\leq 2q^{n/2}-2$,

  2. (ii)

$|D|=2$,

  3. (iii)

$|T_{\bm{v}}|\leq 1$ for each $\bm{v}\in S$, where $T_{\bm{v}}=D\cap
S_{\bm{v}}$.

###### Proof.

We suppose that neither (ii) nor (iii) is true and prove (i). Thus, assume
there exist $\bm{v}\in S$, distinct elements $\bm{w}_{1},\bm{w}_{2}\in
D\setminus\\{\bm{v}\\}$, with ${\mathcal{B}}(\bm{v},\bm{w}_{1})$ and
${\mathcal{B}}(\bm{v},\bm{w}_{2})$ both non-zero, and potentially a fourth
element $\bm{w}_{3}\in D$, which need not be distinct from the previous ones.
We consider two main cases as to whether $\bm{v}$ is self-orthogonal or not.

First, assume ${\mathcal{B}}(\bm{v},\bm{v})\not=0$, which in particular
implies $\bm{v}\in T_{\bm{w}_{1}}\cap T_{\bm{w}_{2}}$. By the
$(3,2)$-orthogonality of $S$, we have ${\mathcal{B}}(\bm{w}_{1},\bm{w}_{2})=0$
and so firstly $\\{\bm{w}_{1},\bm{w}_{2}\\}$ is linearly independent and
secondly by Lemma 3.7 (i),
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{w}_{1},\bm{w}_{2}\\}^{\perp}$}$
is non-degenerate. Write

$S=S_{\bm{w}_{1}}\cup S_{\bm{w}_{2}}\cup
S_{\bm{w}_{1}\bm{w}_{2}}\cup\\{\bm{w}_{1},\bm{w}_{2}\\}.$

For $(q,n)=(3,4)$, by (15), we have

$|S|\leq 2(q^{n/2-1}+1)-1+2(q-1)+2=13<16=2q^{n/2}-2.$

For other admissible choices of $(q,n)$, by Proposition 3.12, we have

$|S|\leq 2(q^{n/2-1}+1)-1+3q^{n/2-1}+2=5q^{n/2-1}+3<2q^{n/2}-2.$

Next, assume ${\mathcal{B}}(\bm{v},\bm{v})=0$. In this case
$\bm{w}_{3}\not\in\\{\bm{v},\bm{w}_{1},\bm{w}_{2}\\}.$ We split this case
further by first assuming that $\bm{w}_{3}$ is orthogonal to $R_{\bm{v}}$
(using the notation of Lemma 3.5). This implies
$R_{\bm{v}}\sqcup\\{\bm{w}_{1},\bm{w}_{2},\bm{w}_{3}\\}$ is an orthogonal set.
Further note that $\\{\bm{w}_{1},\bm{v}\\}$ is linearly independent and that
by parts (i) and (ii) of Lemma 3.7,
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{w}_{1},\bm{v}\\}^{\perp}$}$
is non-degenerate and its equivalence class is preserved. Write

$S=S_{\bm{w}_{1}}\cup S_{\bm{v}}\cup S_{\bm{w}_{1}\bm{v}}.$

For $(q,n)=(3,4)$, by Lemma 3.2 and (15), we have

$|S|\leq(q^{n/2}-1)+(q^{n/2-2}+3)+2q^{n/2-1}-2=16=2q^{n/2}-2.$

For the remaining combinations of $(q,n)$, we use the bound (16) to get

$|S|\leq(q^{n/2}-1)+(q^{n/2-2}+3)+2q^{n/2-1}-1\leq 2q^{n/2}-2.$

Finally, suppose there exists some $\bm{u}\in R_{\bm{v}}$, such that
${\mathcal{B}}(\bm{w}_{3},\bm{u})\not=0$. By definition
${\mathcal{B}}(\bm{u},\bm{u})=0$ and ${\mathcal{B}}(\bm{u},\bm{v})\not=0$,
from which we may deduce $\\{\bm{u},\bm{v}\\}$ is linearly independent and
that by parts (i) and (ii) of Lemma 3.7,
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{u},\bm{v}\\}^{\perp}$}$
is non-degenerate and its equivalence class is preserved. Write

$S=S_{\bm{u}}\cup S_{\bm{v}}\cup S_{\bm{u}\bm{v}}$

and note that $\bm{w}_{1},\bm{w}_{2}\in T_{\bm{v}}$ and $\bm{w}_{3}\in
T_{\bm{u}}$.

We use the bound (16) to get

$|S|\leq 2(q^{n/2-1}+1)+2q^{n/2-1}-1=4q^{n/2-1}+1\leq 2q^{n/2}-2$

for all odd $q$ and $n\geq 4$. ∎

######  Claim 5.6.

Suppose that $S\subset\\{\bm{z}\\}^{\perp}$, where
$\bm{z}\in{\mathbb{F}}_{q}^{n}$ is not self-orthogonal. Then

$|S|\leq 3q^{n/2-1}\leq 2q^{n/2}-2,$

for all $n\geq 4$ and odd $q$.

###### Proof.

Since $\bm{z}$ is not self-orthogonal, the restriction of ${\mathcal{B}}$ on
$\\{\bm{z}\\}^{\perp}$ remains non-degenerate. Now, using that
$S=S\cap\\{\bm{z}\\}^{\perp}$, we may use Proposition 3.12, to obtain the
required result. ∎

Writing $Q=\\{\bm{v}\in S:\bm{v}\in(S\setminus\\{\bm{v}\\})^{\perp}\\}$, note
that

$S=\bigcup_{\bm{v}\in S}S_{\bm{v}}\cup Q.$

Now if $\bm{z}\in D\cap Q$, then
$S\setminus\\{\bm{z}\\}\subset\\{\bm{z}\\}^{\perp}$. Thus, by Claim 5.6, we
have

$|S|\leq 1+3q^{n/2-1}\leq 2q^{n/2}-2,$

for all $n\geq 4$ and odd $q$. In particular, we may assume

(17) $D=\bigcup_{\bm{v}\in S}T_{\bm{v}}.$

Suppose $|S|=2q^{n/2}-1$. Note that, if $|D|$ is even, by Claim 5.4 we must
have that $|S|$ is even leading to a contradiction. Recalling Claim 5.5, if
statement (ii) holds, we are done and so assume statement (iii) is true. Let
$\bm{w}\in D$ and so, by (17), we have $T_{\bm{v}}=\\{\bm{w}\\}$ for some
$\bm{v}\in S$. If $\bm{v}$ is self-orthogonal, then firstly
$\\{\bm{v},\bm{w}\\}$ is linearly independent and secondly by parts (i) and
(ii) of Lemma 3.7,
$\mathcal{B}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$}$
is non-degenerate and its equivalence class is unchanged. We write

$S=S_{\bm{v}}\cup S_{\bm{w}}\cup S_{\bm{v}\bm{w}}$

and use Lemma 3.2 as before, being mindful of the crucial fact that
$S_{\bm{v}}$ contains exactly one non-self-orthogonal element. For
$(q,n)=(3,4)$, we have, by (15)

$|S|\leq
q^{n/2-1}+(q^{n/2}-1)+2q^{n/2-1}-2=3q^{n/2-1}+q^{n/2}-3=15<16=2q^{n/2}-2.$

For other combinations of $(q,n)$, by (16), we have

$|S|\leq q^{n/2-1}+(q^{n/2}-1)+2q^{n/2-1}-1=3q^{n/2-1}+q^{n/2}-2\leq
2q^{n/2}-2.$

Both bounds above contradict the presumed size of $S$. Then, we must have that
$\bm{v}$ is not self-orthogonal. It follows that $T_{\bm{w}}=\\{\bm{v}\\}$,
which in turn implies that elements of $D$ occur in pairs. As explained above,
this contradicts the presumed parity of $|S|$, concluding the proof.

∎

##  6\. Proof of Theorem 2.2

The proof of Theorem 2.2 is similar to the proof of Theorem 2.1. The
differences arise from having characteristic 2 (the theory of bilinear forms
is different) and not being able to assume that $q$ is large enough. We are
however free to assume that $n$ is large enough. A fact special to
${\mathbb{F}}_{2}^{n}$ that we use is that every two distinct non-zero vectors
are linearly independent. In particular the requirement for
$\\{\bm{v},\bm{w}\\}$ to be linearly independent in Lemma 3.7 becomes
redundant.

From now on we use the notation in Lemma 3.2 and Lemma 3.5. The following
simple inequality will be useful. It is specific to ${\mathbb{F}}_{2}^{n}$, is
true for all $n$, and is sharp.

######  Lemma 6.1.

For $n\geq 2$, let $S\subset{\mathbb{F}}_{2}^{n}$ be a $(3,2)$-orthogonal set
with respect to a non-degenerate symmetric bilinear form ${\mathcal{B}}$. If
$\bm{v}\in S$, then in the notation of Lemma 3.5,
$|R_{\bm{v}}|\leq|V_{\bm{v}}|/2$.

###### Proof.

Note that $R_{\bm{v}}$ is disjoint from $R_{\bm{v}}+R_{\bm{v}}$. Indeed, if
$\bm{x},\bm{y}\in R_{\bm{v}}$, then
${\mathcal{B}}(\bm{v},\bm{x})={\mathcal{B}}(\bm{v},\bm{y})=1$. Therefore
${\mathcal{B}}(\bm{v},\bm{x}+\bm{y})=1+1=0$. This means that
$\bm{x}+\bm{y}\notin R_{\bm{v}}$.

Now, $V_{\bm{v}}$ is a vector space containing $R_{\bm{v}}$. Therefore
$R_{\bm{v}}$ and $R_{\bm{v}}+R_{\bm{v}}$ are two disjoint sets contained in
$V_{\bm{v}}$. Hence

$2|R_{\bm{v}}|\leq|R_{\bm{v}}|+|R_{\bm{v}}+R_{\bm{v}}|\leq|V_{\bm{v}}|.\qed$

We derive a bound on $|S_{\bm{v}}|$.

######  Lemma 6.2.

For $n\geq 2$, let $S\subset{\mathbb{F}}_{2}^{n}$ be a $(3,2)$-orthogonal set
with respect to a non-degenerate symmetric bilinear form ${\mathcal{B}}$. If
$\bm{v}\in S$, then in the notation of Lemma 3.5:

  * •

If ${\mathcal{B}}=\cdot$, then

$|S_{\bm{v}}|\leq\begin{cases}n,&\mbox{if }n\leq 7;\\\
1+2^{\frac{n-1}{2}-1},&\mbox{if }n\ \text{is odd and}\ n\geq 9;\\\
2^{\frac{n}{2}-1},&\mbox{if }n\ \text{is even and}\ n\geq 8.\end{cases}$

  * •

If ${\mathcal{B}}={\mathcal{H}}$ and $n$ is even, then $|S_{\bm{v}}|\leq
2^{\frac{n}{2}-1}$.

###### Proof.

We begin with ${\mathcal{B}}=\cdot$. By Lemma 3.5 and Lemma 6.1, we have

$|S_{\bm{v}}|\leq|R_{\bm{v}}|+|T_{\bm{v}}|\leq\frac{|V_{\bm{v}}|}{2}+|T_{\bm{v}}|.$

By Lemma 3.2 we have $\dim(V_{\bm{v}})\leq\lfloor(n-|T_{\bm{v}}|)/2\rfloor$.
Setting $t=|T_{\bm{v}}|$ we get

$|S_{\bm{v}}|\leq 2^{\lfloor\frac{n-t}{2}\rfloor-1}+t.$

A routine calculation confirms that, for $n\leq 7$, the right side is maximum
when $t=n$. Otherwise, the maximum is achieved when $t=1$ for odd $n$ and when
$t=0$ for even $n$.

If ${\mathcal{B}}={\mathcal{H}}$, there are no non-self-orthogonal vectors and
so, similarly to above, $|S_{\bm{v}}|\leq|V_{\bm{v}}|/2\leq
2^{\frac{n}{2}-1}$. ∎

We first prove the theorem for the hyperbolic form ${\mathcal{H}}$.

######  Proposition 6.3.

Let $n\geq 2$ be even and $S\subset{\mathbb{F}}_{2}^{n}$ be a
$(3,2)$-orthogonal set with respect to the hyperbolic form ${\mathcal{H}}$.
Then

$|S|\leq 2^{\frac{n}{2}+1}-2.$

###### Proof.

We prove the claim by induction. For $n=2$,
${\mathbb{F}}_{2}^{2}\setminus\\{\bm{0}\\}$ is not $(3,2)$-orthogonal. So the
claim is true for $n=2$.

For the inductive step, we may assume there exist linearly independent
$\bm{v},\bm{w}$ such that $\bm{v}\cdot\bm{w}=1$. If not, then $S$ is an
orthogonal set and by Lemma 3.2, we have the better bound $|S|\leq
2^{\frac{n}{2}}-1$. By Lemma 3.7 (iii),
${\mathcal{H}}{\mathbin{\upharpoonright}}\raise-2.15277pt\hbox{$\\{\bm{v},\bm{w}\\}^{\perp}$}$
is non-degenerate and is equivalent to ${\mathcal{H}}$ (in this lower
dimensional vector space). By the induction hypothesis we have

$|S_{\bm{vw}}|\leq 2^{\frac{n}{2}}-2.$

Hence by Lemma 6.2,

$|S|\leq|S_{\bm{v}}|+|S_{\bm{w}}|+|S_{\bm{vw}}|\leq
2^{\frac{n}{2}-1}+2^{\frac{n}{2}-1}+(2^{\frac{n}{2}}-2)=2^{\frac{n}{2}+1}-2.\qed$

From now on we mainly restrict our attention to the dot product, though we
will use Proposition 6.3 for even $n$ because we sometimes use Lemma 3.7 (i)
and the restriction of the dot product may be equivalent to ${\mathcal{H}}$.
To prove the theorem we consider two cases separately depending on whether $S$
contains a vector that is not self-orthogonal or not. We first prove the
theorem when all vectors in $S$ are self-orthogonal. The proof is similar to
that of Proposition 6.3.

######  Proposition 6.4.

For $n\geq 1$, let $S\subset{\mathbb{F}}_{2}^{n}$ be a $(3,2)$-orthogonal set
with respect to the dot product. If $S$ consists entirely of self-orthogonal
vectors, then

$|S|\leq\begin{cases}2^{\frac{n+1}{2}}-2,&\mbox{if }n\ \text{is odd};\\\
2^{\frac{n}{2}+1}-3,&\text{if }n\ \text{is even}.\end{cases}$

###### Proof.

We prove the claim by induction. For $n=1$, $|S|=0$. For $n=2$, we have
$S\subset\\{(1,1)\\}$ and the claim follows.

For the inductive step, we may assume there exist linearly independent
$\bm{v},\bm{w}$ such that $\bm{v}\cdot\bm{w}=1$. If not, then $S$ is an
orthogonal set and by Lemma 3.4, we have a better bound on $|S|$ than
required. Furthermore, by Lemma 3.7 (iii), the dot product restricted to
$\\{\bm{v},\bm{w}\\}^{\perp}$ is equivalent to the (lower dimensional) dot
product and $S_{\bm{vw}}$ contains only self-orthogonal vectors. For even $n$,
by the induction hypothesis we have

$|S_{\bm{vw}}|\leq 2^{\frac{n}{2}}-3.$

All vectors in $S$ are self-orthogonal and so
$T_{\bm{v}}=T_{\bm{w}}=\emptyset$. Therefore $S_{\bm{v}}=R_{\bm{v}}$. Lemma
6.1 gives

$|R_{\bm{v}}|\leq 2^{\frac{n}{2}-1}.$

The same holds for $\bm{w}$. Putting everything together gives

$|S|\leq
2^{\frac{n}{2}-1}+2^{\frac{n}{2}-1}+(2^{\frac{n}{2}}-3)=2^{\frac{n}{2}+1}-3.$

For odd $n$, the induction hypothesis gives

$|S_{\bm{vw}}|\leq 2^{\frac{n-1}{2}}-2.$

Again $T_{\bm{v}}=T_{\bm{w}}=\emptyset$ and so by Lemma 6.2, we have

$|S_{\bm{v}}|,|S_{\bm{w}}|\leq 2^{\frac{n-1}{2}-1}.$

This gives

$|S|\leq
2^{\frac{n-1}{2}-1}+2^{\frac{n-1}{2}-1}+(2^{\frac{n-1}{2}}-2)=2^{\frac{n+1}{2}}-2,$

as required. ∎

The next step is to prove a bound for all $S$ that is weaker than that in
Theorem 2.2. It will be used to prove the theorem when $S$ contains a vector
that is not self-orthogonal.

######  Lemma 6.5.

For $n\geq 1$, let $S\subset{\mathbb{F}}_{2}^{n}$ be a $(3,2)$-orthogonal set
with respect to a non-degenerate symmetric bilinear form. Then

$|S|\leq\begin{cases}2^{\frac{n+1}{2}}+2n-2,&\mbox{if }n=1,3;\\\
2^{\frac{n+1}{2}}+\tfrac{n(n+1)}{2}-3,&\mbox{if }n\geq 5\ \text{is odd};\\\
2^{\frac{n}{2}+1}+2n-3,&\mbox{if }n=2,4;\\\
2^{\frac{n}{2}+1}+\tfrac{n(n+1)}{2}-4,&\mbox{if }n\geq 6\ \text{is
even}.\end{cases}$

###### Proof.

If the bilinear form is equivalent to ${\mathcal{H}}$, the result follows from
Proposition 6.3.

If the bilinear form is equivalent to the dot product, we let $D\subset S$ be
the collection of vectors in $S$ that are not self-orthogonal. The claim
follows by applying Proposition 6.4 to $S\setminus D$ and Lemma 3.10 to $D$. ∎

We continue with the case when there is a vector that is non-self-orthogonal.
The proof is longer because we cannot initiate the induction (for example,
Remark 6.7 on p. 6.7 shows ${\mathcal{S}}_{3,2}(2,4,\cdot)\geq 7>2^{3}-3$) and
because we can no longer assume, say, $T_{\bm{v}}=\emptyset$.

######  Proposition 6.6.

Let $n$ be an integer and $S\subset{\mathbb{F}}_{2}^{n}$ be a
$(3,2)$-orthogonal with respect to the dot product. If $S$ contains a vector
that is not self-orthogonal, then

$|S|\leq\begin{cases}2^{\frac{n+1}{2}}+1,&\mbox{if }n\geq 21\ \text{is
odd};\\\ 2^{\frac{n}{2}+1}-3,&\mbox{if }n\geq 18\ \text{is even}.\end{cases}$

###### Proof.

We begin with familiar notation. We let $G$ be the simple graph with vertex
set $S$ and edges given by not mutually orthogonal pairs of vertices, and

$D=\\{\bm{v}\in S:\bm{v}\cdot\bm{v}=1\\}.$

Even $n$. Let $\bm{z}\in D$. We consider two separate cases according to
whether there exists an edge between $\bm{z}$ and $S\setminus D$ or not.

Suppose first that there is no edge between $\bm{z}$ and $S\setminus D$. Then
$S\setminus D\subset\\{\bm{z}\\}^{\perp}$. The dot product restricted to
$\\{\bm{z}\\}^{\perp}$ is non-degenerate (because $\bm{z}$ is not self-
orthogonal). The dimension of $\\{\bm{z}\\}^{\perp}$ is odd and so the
restriction is equivalent to the (lower dimensional) dot product. Moreover,
all elements of $S\setminus D$ are self-orthogonal. Therefore by Proposition
6.4 we get $|S\setminus D|\leq 2^{\frac{n}{2}}-2$. By Lemma 3.10 we have
$|D|\leq\tfrac{n(n+1)}{2}-1$. Hence (because $n\geq 14)$

$|S|\leq(2^{\frac{n}{2}}-2)+(\tfrac{n(n+1)}{2}-1)\leq 2^{\frac{n+1}{2}}-3.$

Next we suppose that there exists and edge $\bm{vz}$ with $\bm{v}\in
S\setminus D$. We have

$|S|\leq|S_{\bm{v}}|+|S_{\bm{z}}|+|S_{\bm{vz}}|.$

By Lemma 3.7 (i), the dot product restricted to $\\{\bm{v},\bm{z}\\}^{\perp}$
is non-degenerate. Lemma 6.5 gives

$|S_{\bm{vz}}|\leq 2^{\frac{n}{2}}+\tfrac{(n-2)(n-1)}{2}-4.$

To bound $|S_{\bm{v}}|$ note $\bm{z}\in T_{\bm{v}}$. Writing $t=|T_{\bm{v}}|$,
and applying Lemma 3.5 and Lemma 6.1 we get (using $n\geq 12$)

$|S_{\bm{v}}|\leq 2^{\lfloor\frac{n-1-t}{2}\rfloor-1}+t\leq
2^{\frac{n}{2}-2}+1.$

By Lemma 6.2 we get $|S_{\bm{z}}|\leq 2^{\frac{n}{2}-1}$.

Putting everything together gives (using $n\geq 18$)

$|S|\leq 2^{\frac{n}{2}+1}-3-(2^{\frac{n}{2}-2}-\tfrac{(n-2)(n-1)}{2})\leq
2^{\frac{n}{2}+1}-3.$

Odd $n$. If $D$ contains up to three elements, the required result follows
from Proposition 6.4. Let $\bm{x},\bm{y},\bm{z}\in D$ denote three distinct
elements and let $H$ be the graph induced on $\\{\bm{x},\bm{y},\bm{z}\\}$. The
graph $H$ is not a triangle because $D$ is a subset of a $(3,2)$-orthogonal
set. We consider three cases based on the number of edges in $H$.

Suppose $H$ is the empty graph. First, assume a pair of the sets
$R_{\bm{x}},R_{\bm{y}},R_{\bm{z}}$ has non-empty intersection. Namely, say
$\bm{v}\in R_{\bm{x}}\cap R_{\bm{y}}$. Consider the decomposition

(18) $S=S_{\bm{x}}\cup S_{\bm{v}}\cup S_{\bm{xv}}.$

Note that $\bm{x},\bm{y}\in T_{\bm{v}}$ and that by Lemma 3.7 (i), we may
apply Lemma 6.5 to obtain

(19)
$|S|\leq(2^{\frac{n-1}{2}-2}+3)+(2^{\frac{n-1}{2}-1}+1)+(2^{\frac{n-1}{2}}+\tfrac{(n-2)(n-1)}{2}-3)\leq
2^{\frac{n+1}{2}}+1,$

for $n\geq 21$. Thus suppose $R_{\bm{x}},R_{\bm{y}},R_{\bm{z}}$ are pairwise
disjoint. This means that $R_{\bm{z}}\cup\\{\bm{x},\bm{y}\\}$ is orthogonal.
Since $\bm{z}\in S_{\bm{xy}}$ and the dot product restricted to
$\\{\bm{x},\bm{y}\\}^{\perp}$ is non-degenerate (by Lemma 3.7 (i)), Lemma 6.2
gives

$|S_{\bm{z}}|=|S_{\bm{z}}\cap S_{\bm{xy}}|\leq 1+2^{\frac{n-1}{2}-2}.$

Considering the decomposition

(20) $S=S_{\bm{x}}\cup S_{\bm{z}}\cup S_{\bm{xz}}\cup\\{\bm{x},\bm{z}\\},$

and using Lemma 3.7 (i), Lemma 6.2 (as well as its proof), and Lemma 6.5, we
have

(21)
$|S|\leq(2^{\frac{n-1}{2}-1}+1)+(2^{\frac{n-1}{2}-2}+3)+(2^{\frac{n-1}{2}}+\tfrac{(n-2)(n-1)}{2}-3)+2\leq
2^{\frac{n+1}{2}}+1$

for $n\geq 21$. (We can do better but will refer later to (21)).

Next, suppose $H$ has exactly one edge. Without loss of generality take
$\bm{yx}$ to be the edge. We split this case further. First suppose there
exists an edge between $\bm{z}$ and $R_{\bm{x}}\cup R_{\bm{y}}$. Say, an edge
between $\bm{z}$ and $\bm{v}\in R_{\bm{x}}$. We consider the decomposition
(18) Then noting that $\bm{x},\bm{z}\in T_{\bm{v}}$ and that Lemma 3.7 (i)
allows one to apply Lemma 6.5, one recovers the same bound on $|S|$ as (19).
Next, suppose there is no edge between $\bm{z}$ and $R_{\bm{x}}\cup
R_{\bm{y}}$. In particular, $R_{\bm{x}}\cup\\{\bm{y},\bm{z}\\}$ is an
orthogonal set. It follows that $V_{\bm{x}}$ does not have the maximum
dimension that is possible for orthogonal subspaces. Thus, using the
decomposition (20) and using Lemma 3.7 (i), Lemma 3.2, Lemma 6.1 and Lemma
6.5, we may obtain the same bound on $|S|$ as (21).

Finally, suppose $H$ has two edges. Without loss of generality let $\bm{yxz}$
be the path of length 2. Here, we proceed to show that we may assume $|D|=3$,
which, as pointed out earlier, gives the required result.

Suppose there exists a fourth vector $\bm{w}\in D$. If $\bm{w}$ forms an edge
with $\bm{x}$, then there is no edge between any two of
$\\{\bm{y},\bm{z},\bm{w}\\}$ and we are done by the arguments of the first
case. If, on the other hand, $\bm{w}$ does not form an edge with $\bm{x}$, by
Lemma 3.7 (i), dot product is non-degenerate on $\\{\bm{x},\bm{w}\\}^{\perp}$,
so we use

$S=S_{\bm{x}}\cup S_{\bm{w}}\cup S_{\bm{xw}}\cup\\{\bm{x},\bm{w}\\}.$

Then, noting $|T_{\bm{x}}|\geq 2$ and arguing as before, we obtain

$|S|\leq(2^{\frac{n-1}{2}-2}+3)+(2^{\frac{n-1}{2}-1}+1)+(2^{\frac{n-1}{2}}+\tfrac{(n-2)(n-1)}{2}-3)+2\leq
2^{\frac{n+1}{2}}+1,$

which is the same as (21). ∎

The proof of Theorem 2.2 is completed by combining Propositions 6.3, 6.4 and
6.6.

######  Remark 6.7.

Theorem 2.2 is false for small $n$. For $n=2$,
${\mathcal{S}}_{3,2}(2,2,\cdot)=3$ as we see by taking
$S={\mathbb{F}}_{2}^{2}\setminus\\{\bm{0}\\}$. For $n=4$ the example below
shows ${\mathcal{S}}_{3,2}(2,4,\cdot)\geq 7$:

$S=\\{(1,1,1,0),(1,0,0,0),(1,0,1,1),(0,0,0,1),(0,1,1,1),(0,1,1,0),(1,1,0,1)\\}.$

The graph of $S$ is indeed triangle-free: using the implicit order on the
vertices, it is the union of the 6-cycle $234567$ with the edges $12$ and
$47$.

##  7\. Proof of Theorem 2.3

The following is essentially the same as [10, Equation 2.4] and [18, Lemma 5].
Also see [3] or apply the point-hyperplane incidence bound in [20].

######  Lemma 7.1.

For $X,Y\subset{\mathbb{F}}_{q}^{n}$, define

$O(X,Y)=|\\{(\bm{x},\bm{y})\in X\times Y:\mathcal{B}(\bm{x},\bm{y})=0\\}|.$

Then

$\bigg{|}O(X,Y)-\frac{|X||Y|}{q}\bigg{|}\leq\sqrt{|X||Y|q^{n}}.$

The following result is due to Turán [19].

######  Lemma 7.2.

Any graph of $n$ vertices, which is $K_{r+1}$-free contains at most
$(1-1/r)(n^{2}/2)$ edges.

###### Proof of Theorem 2.3.

Let $G=G(S,E_{1})$ be the simple graph, where $(\bm{s_{1}},\bm{s_{2}})\in
S^{2}$ forms an edge in $E_{1}$ if $\bm{s_{1}}\neq\bm{s_{2}}$ and
$\mathcal{B}(\bm{s_{1}},\bm{s_{2}})\not=\bm{0}$. Then using the fact that $S$
is $(k,2)$-orthogonal, we know that $G$ is $K_{k}$-free and thus by Lemma 7.2,

$|E_{1}|\leq\frac{k-2}{k-1}\frac{|S|^{2}}{2}.$

Denoting $G^{{}^{\prime}}=G(S,E_{2})$ as the complement of $G$, we deduce that

$|E_{2}|\geq\frac{|S|(|S|-1)}{2}-|E_{1}|\geq\frac{|S|^{2}}{2(k-1)}-\frac{|S|}{2}.$

Now, clearly $O(S,S)\geq 2|E_{2}|$. Hence, applying Lemma 7.1, we have

$\frac{|S|^{2}}{k-1}-\frac{|S|^{2}}{q}-|S|\leq|S|q^{n/2},$

which gives

$|S|\leq\bigg{(}\frac{q(k-1)}{q-k+1}\bigg{)}(q^{n/2}+1).\qed$

## Acknowledgement

The authors are grateful to anonymous referees for their suggestions, which
helped improve the presentation of the paper.

## References

  * [1] O. Ahmadi and A. Mohammadian, ‘Sets with many pairs of orthogonal vectors over finite fields’, Finite Fields Appl., 37 (2016), 179–192.
  * [2] M. Ajtai, J. Komlós, and E. Szemerédi, ‘A note on Ramsey numbers’, J. Combin. Theory Ser. A, 29 (1980), 354–360.
  * [3] N. Alon and M. Krivelevich, ‘Constructive bounds for a Ramsey-type problem’, Graphs Combin., 13 (1997), 217–225.
  * [4] N. Alon and M. Szegedy, ‘Large sets of nearly orthogonal vectors’, Graphs Combin., 15 (1999), 1–4.
  * [5] E. R. Berlekamp, ‘On subsets with intersections of even cardinality’, Can. Math. Bull., 23 (1969), 471–474.
  * [6] L. Deaett, ‘The minimum semidefinite rank of a triangle-free graph’, Linear Algebra Appl., 434 (2011), 1945–1955.
  * [7] Z. Füredi and R. P. Stanley, ‘Sets of vectors with many orthogonal pairs’, Graphs Combin., 8 (1992), 391–394.
  * [8] J. E. Graver, ‘Boolean designs and self-dual matroids’, Linear Algebra Appl., 10 (1975), 111–128.
  * [9] L. C. Grove, ‘Classical Groups and Geometric Algebra’, Grad. Stud. Math., Vol. 90, American Mathematical Society, Providence, RI, 2008.
  * [10] D. Hart, A. Iosevich, D. Koh, and M. Rudnev, ‘Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős-Falconer distance conjecture’, Trans. Amer. Math. Soc., 363 (2011), 3255–3275.
  * [11] J. H. Kim, ‘The Ramsey number $R(3,t)$ has order of magnitude $t^{2}/\log t$’, Random Structures Algorithms, 7 (1995), 173–207.
  * [12] M. Knebusch, ‘Specialization of quadratic and symmetric bilinear forms’, Translated from the German by Thomas Unger Algebra and Applications, 11. Springer-Verlag London 2010.
  * [13] R. Lidl and H. Niederreiter, Finite Fields, Cambridge Univ. Press, Cambridge, 1997.
  * [14] J. Nešetřil and M. Rosenfeld, ‘Embedding graphs in Euclidean spaces, an exploration guided by Paul Erdős’, Geombinatorics, 6 (1997), 143–155.
  * [15] P. Pudlák, ‘Cycles of nonzero elements in low rank matrices’, Combinatorica, 22 (2002), 321–334.
  * [16] M. Rosenfeld, ‘Almost orthogonal lines in $E^{d}$’, in Applied Geometry and Discrete Mathematics, in DIMACS Ser. Discret. Math. Theor. Comput. Sci. Vol. 4, (1991), 489–492.
  * [17] J. B. Shearer, ‘A note on the independence number of triangle-free graphs. II’, J. Combin. Theory Ser. B, 53 (1991), 300–307.
  * [18] I. E. Shparlinski, ‘On the additive energy of the distance set in finite fields’, Finite Fields Appl., 42 (2016), 187–199.
  * [19] P. Turán, ‘Eine Extremalaufgabe aus der Graphentheorie’, Mat. Fiz. Lapok, 48 (1941), 436–452.
  * [20] L. A. Vinh, ‘The Szemerédi–Trotter type theorem and the sum-product estimate in finite fields’, European J. Combin., 32 (2011), 1177–1181.
  * [21] L. A. Vinh, ‘Maximal sets of pairwise orthogonal vectors in finite fields’, Canad. Math. Bull., 55 (2012), 418–423.
  * [22] I. M. Vinogradov, An Introduction to the Theory of Numbers, Pergamon Press, London and New York, 1955.
  * [23] A. Zame, ‘Orthogonal sets of vectors over $Z_{m}$’, J. Combinatorial Theory, 9 (1970), 136–143.