# On $k$-simplexes in (2$k$ − 1)-dimensional vector spaces over finite fields

Le Anh Vinh

*Mathematics Department, Harvard University, Cambridge, MA 02138, US*

**Abstract.** We show that if the cardinality of a subset of the (2k − 1)-dimensional vector space over a finite field with q elements is ≫ q²k−1−1/2k, then it contains a positive proportional of all k-simplexes up to congruence.

**Résumé.** Nous montrons que si la cardinalité d'un sous-ensemble de l'espace vectoriel à (2k − 1) dimensions sur un corps fini à q éléments est ≫ q²k−1−1/2k, alors il contient une proportion non-nulle de tous les k-simplexes de congruence.

**Keywords:** distance problem, finite Euclidean graphs, finite non-Euclidean graphs, spectral graphs

## 1 Introduction

A classical result due to Furstenberg, Katznelson and Weiss (6) states that if $E \subset \mathbb{R}^2$ has positive upper Lebesgue density, then for any $\delta > 0$, the $\delta$-neighborhood of $E$ contains a congruent copy of a sufficiently large dilate of every three-point configuration. For higher dimensional simplexes, Bourgain (4) showed that if $E \subset \mathbb{R}^d$ has positive upper density, and $\Delta$ is a $k$-simplex with $k < d$, then $E$ contains a rotated and translated image of every large dilate of $\Delta$. The cases $k = d$ and $k = d+1$ still remain open. Magyar (10; 11) studied related problems in the integer lattice $\mathbb{Z}^d$. He showed (11) that if $d > 2k+4$, and $E \subset \mathbb{Z}^d$ has positive upper densitiy, then all large (depending on density of $E$) dilates of a $k$-simplex in $\mathbb{Z}^d$ can be embedded in $E$.

Hart and Iosevich (7) made the first investigation in an analog of this question in finite field geometries. They showed that if $E \subset \mathbb{F}_q^d$, $d \ge \binom{k+1}{2}$ of cardinality $|E| \ge C q^{\frac{kd}{k+1}} q^{\frac{k}{2}}$ for a sufficiently large constant $C > 0$, then $E$ contains an isometric copy of every $k$-simplex. Using graph theoretic method, the author (14) showed that the same result holds for $d \ge 2k$ and $|E| \gg q^{\frac{d-1}{2}+k}$ (cf. Theorem 1.4 in (14)).

Note that serious difficulties arise when the size of the simplex is sufficiently large with respect to the ambient dimension. Even in the case of triangles, the result in (14) is only non-trivial for $d \ge 4$. In (5), Covert, Hart, Iosevich, and Uriarte-Tuero addressed the case of triangles in two-dimensional vector spaces over finite fields. They showed that if $E$ has density $\ge \rho$, for some $\frac{C}{\sqrt{q}} \le \rho \le 1$ with a sufficiently large constant $C > 0$, then the set of triangles determined by $E$, up to congruence, has density $\ge c\rho$. In (15), the author studied the remaining case; triangles in three-dimensional vector spaces over finite fields. Using a combination of graph theory method and Fourier analysis, the author showed that if $E \subset \mathbb{F}_q^d$,
$d \ge 3$, such that $|E| \gg q^{\frac{d+2}{2}}$, then $E$ determines almost all triangles up to congruence. The arguments in (15), however, do not work for $k \ge 5$.

In this paper, we will study the case of $k$-simplexes in $(2k-1)$-dimensional vector spaces with $k \ge 3$. Given $E_1, \dots, E_k \subset \mathbb{F}_q^d$, where $\mathbb{F}_q$ is a finite field of $q$ elements, define

$$T_k(E_1, \dots, E_k) = \{(x_1, \dots, x_k) \in E_1 \times \dots \times E_k\} / \sim \qquad (1.1)$$

with the equivalence relation $\sim$ such that $(x_1, \dots, x_k) \sim (x'_1, \dots, x'_k)$ if there exist $\tau \in \mathbb{F}_q^d$ and $O \in SO_d(\mathbb{F}_q)$, the set of $d$-by-$d$ orthogonal matrices over $\mathbb{F}_q$ with determinant 1, such that

$$(x'_1, \dots, x'_k) = (O(x_1) + \tau, \dots, O(x_k) + \tau). \qquad (1.2)$$

The main result of this paper is the following.

**Theorem 1.1** Let $E \subset \mathbb{F}_q^{2k-1}$ with $k \ge 3$, and suppose that

$$|E| \gg q^{2k-1-\frac{1}{2k}}.$$

There exists $c > 0$ such that

$$|T_{k+1}(E)| \ge c q^{\binom{k+1}{2}}.$$

In other words, we always get a positive proportion of all $k$-simplexes if $E \gg q^{k-1-\frac{1}{2k}}$ and $k \ge 3$. The rest of this short paper is organized as follows. In Section 2, we establish some results about the occurrences of colored subgraphs in a pseudo-random coloring of a graph. In Section 3, we construct our main tools to study simplexes in vector spaces over finite fields, the finite Euclidean and non-Euclidean graphs. We then prove our main result, Theorem 1.1 in Section 4.

# 2 Subgraphs in expanders

We call a graph $G = (V, E)$ $(n, d, \lambda)$-graph if $G$ is a $d$-regular graph on $n$ vertices with the absolute values of each of its eigenvalues but the largest one are at most $\lambda$. Suppose that a graph $G$ of order $n$ is colored by $t$ colors. Let $G_i$ be the induced subgraph of $G$ on the $i^{th}$ color. We call a $t$-colored graph $G$ $(n, d, \lambda)$-r.c. (regularly colored) graph if $G_i$ is an $(n, d, \lambda)$-regular graph for each color $i \in \{1, \dots, t\}$. In this section, we will study the occurrences of colored subgraphs in an $(n, d, \lambda)$-r.c. graph.

## 2.1 Colored subgraphs

It is well-known that if $\lambda \ll d$ then an $(n, d, \lambda)$-graph behaves similarly as a random graph $G_{n,d/n}$. Precisely, we have the following result.

**Theorem 2.1** ((1, Theorem 9.2.4)) Let $G$ be an $(n, d, \lambda)$-graph. For a vertex $v \in V$ and a subset $B$ of $V$, denote by $N(v)$ the set of all neighbors of $v$ in $G$, and let $N_B(v) = N(v) \cap B$ denote the set of all neighbors of $v$ in $B$. For every subset $B$ of $V$, we have

$$\sum_{v \in V} \left( |N_B(v)| - \frac{d}{n} |B| \right)^2 \le \frac{\lambda^2}{n} |B|(n - |B|). \qquad (2.1)$$

The following result is an easy corollary of Theorem 2.1.
**Theorem 2.2** ((1, Corollary 9.2.5)) Let $G$ be an $(n, d, \lambda)$-graph. For every set of vertices $B$ and $C$ of $G$, we have

$$|e(B, C) - \frac{d}{n} |B||C|| \leq \lambda \sqrt{|B||C|}, \qquad (2.2)$$

where $e(B, C)$ is the number of edges in the induced bipartite subgraph of $G$ on $(B, C)$ (i.e. the number of ordered pair $(u, v)$ where $u \in B, v \in C$ and $uv$ is an edge of $G$).

Let $H$ be a fixed graph of order $s$ with $r$ edges. Let Aut($H$) be an automorphism group of $H$. It is well-known that for every constant $p \in (0, 1)$, the random graph $G(n, p)$ contains

$$(1 + o(1))p^r(1 - p)^{\binom{s}{2} - r} \frac{n^s}{|\mathrm{Aut}(H)|} \qquad (2.3)$$

induced copies of $H$. Alon extended this result to $(n, d, \lambda)$-graph. He proved that every large subset of the set of vertices of a $(n, d, \lambda)$-graph contains the “correct” number of copies of any fixed small subgraph.

**Theorem 2.3** ((9, Theorem 4.10)) Let $H$ be a fixed graph with $r$ edges, $s$ vertices and maximum degree $\Delta$, and let $G = (V, E)$ be an $(n, d, \lambda)$-graph, where, say, $d \leq 0.9n$. Let $m < n$ satisfies $m \gg \lambda (\frac{n}{d})^{\Delta}$. Then, for every subset $U \subset V$ of cardinality $m$, the number of (not necessarily induced) copies of $H$ in $U$ is

$$(1 + o(1)) \frac{m^s}{|\mathrm{Aut}(H)|} \left(\frac{d}{n}\right)^r. \qquad (2.4)$$

In (14), we observed that Theorem 2.3 can be extended to $(n, d, \lambda)$-r.c. graph. Precisely, we showed that every large subset of the set of vertices of an $(n, d, \lambda)$-r.c. graph contains the “correct” number of copies of any fixed small colored graph. We present here a multiset version of this statement.

**Theorem 2.4** Let $H$ be a fixed $t$-colored graph with $r$ edges, $s$ vertices, maximum degree $\Delta$ (with the vertex set is ordered), and let $G$ be a $t$-colored graph of order $n$. Suppose that $G$ is an $(n, d, \lambda)$-r.c graph, where, say, $d \ll n$. Let $E_1, \dots, E_s \subset V$ satisfy $|E_i| \gg \lambda (\frac{n}{d})^{\Delta}$. Then the number of (not necessarily induced) copies of $H$ in $E_1 \times \dots \times E_s$ (one vertex in each set) is

$$(1 + o(1)) \prod_{i=1}^{s} |E_i| \left(\frac{d}{n}\right)^r. \qquad (2.5)$$

The proof of this theorem is similar to the proofs of (9, Theorem 4.10) and (14, Theorem 2.3). Note that going from one color formulation ((9, Theorem 4.10)) and one set formulation ((14, Theorem 2.3)) to a multicolor-multiset formulation (Theorem 2.4) is just a matter of inserting different letters in a couple of places.

## 2.2 Colored stars

Given any $k$ colors $r_1, \dots, r_k$, a $k$-star of type $(r_1, \dots, r_k)$ has $k + 1$ vertices, one center vertex $x_0$ and $k$ leaves $x_1, \dots, x_k$, with the edge $(x_0, x_i)$ is colored by the color $r_i$. The following result gives us an estimate for the number of colored $k$-stars in an $(n, d, \lambda)$-r.c. graph $G$ (see (15) for an earlier version).
**Theorem 2.5** Let G be an $(n, d, \lambda)$-r.c. graph. Given any k colors $r_1, \dots, r_k$ in the color set. Suppose that $E_0, E_1, \dots, E_k \subset V(G)$ with

$$|E_0|^2 \prod_{i \in I} |E_i| \gg \left(\frac{n}{d}\lambda\right)^{2|I|} \qquad (2.6)$$

for all $I \subset \{1, \dots, k\}, |I| \ge 2$, and

$$|E_0||E_i| \gg \left(\frac{n}{d}\lambda\right)^2 \qquad (2.7)$$

for all $i \in \{1, \dots, k\}$. Let $e_{\{r_1, \dots, r_k\}}(E_0; \{E_1, \dots, E_k\})$ denote the number of k-stars of type $(r_1, \dots, r_k)$ in $E_0 \times E_1 \times \dots \times E_k$ (with the center in $E_0$). We have

$$e_{\{r_1, \dots, r_k\}}(E_0; \{E_1, \dots, E_k\}) = (1 + o(1)) \left(\frac{d}{n}\right)^k \prod_{i=0}^{k} |E_i|, \qquad (2.8)$$

where k is fixed and n, d, λ ≫ 1.

**Proof:** The proof proceeds by induction. We first consider the best case, $k=1$. Since $|E| \gg \frac{n}{d}\lambda$ and the number of 1-stars of type a in $E_0 \times E_1$ is just the number of a-colored edges in $E_0 \times E_1$, the statement follows immediately from Theorem 2.2 and (2.7).

Suppose that the statement holds for all colored l-stars with $l < k$. For a vertex $v \in V$ and a color r, let $N_E^r(v)$ denote the set of all r-colored neighbors of v in E. From Theorem 2.1, we have

$$\sum_{v \in E_0} (|N_{E_i}^{r_i}(v)| - \frac{d}{n}|E_i|)^2 \le \sum_{v \in V} (|N_{E_i}^{r_i}(v)| - \frac{d}{n}|E_i|)^2 \le \frac{\lambda^2}{n}|E_i|(n - |E_i|) \le \lambda^2|E_i|. \qquad (2.9)$$

For $k \ge 2$, by the Cauchy-Schwartz inequality, we have

$$\prod_{i=1}^{k} \left( \sum_{j=1}^{n} a_{i,j}^2 \right) \ge \left( \sum_{j=1}^{n} \prod_{i=1}^{k-1} a_{i,j}^2 \right) \left( \sum_{j=1}^{n} a_{k,j}^2 \right) \ge \left( \sum_{j=1}^{n} \prod_{i=1}^{k} a_{i,j} \right)^2. \qquad (2.10)$$

It follows from (2.9) and (2.10) that

$$\left( \sum_{v \in E_0} \prod_{i=1}^{k} (N_{E_i}^{r_i}(v) - \frac{d}{n} |E_i|) \right)^2 \le \prod_{i=1}^{k} \sum_{v \in E_0} (|N_{E_i}^{r_i}(v)| - \frac{d}{n} |E_i|)^2 \le \lambda^{2k} \prod_{i=1}^{k} |E_i|.$$

It can be written as

$$\left| \sum_{I \subset \{1, \dots, k\}} (-1)^{k-|I|} \left(\frac{d}{n}\right)^{k-|I|} \prod_{j \notin I} |E_j| \sum_{v \in E_0} \prod_{i \in I} N_{E_i}^{r_i}(v) \right| \le \lambda^k \sqrt{\prod_{i=1}^{k} |E_i|}. \qquad (2.11)$$

For any $I \subset \{1, \dots, k\}$ with $0 < |I| < k$, by the induction hypothesis, we have

$$\sum_{v \in E_0} \prod_{i \in I} N_{E_i}^{r_i}(v) = e_I(E_0; \{E_i\}_{i \in I}) = (1 + o(1)) \left(\frac{d}{n}\right)^{|I|} |E_0| \prod_{i \in I} |E_i|. \qquad (2.12)$$
Putting (2.11) and (2.12) together, we have

$$
\left| \sum_{v \in E_0} \prod_{i=1}^{k} N_{E_i}^{r_i}(v) - (1 + o(1)) \left(\frac{d}{n}\right)^k \prod_{i=0}^{k} |E_i| \right| \le \lambda^k \sqrt{\prod_{i=1}^{k} |E_i|}.
$$

Since $|E_0|^2 \prod_{i=1}^k |E_i| \gg (\frac{n}{d}\lambda)^{2k}$, the left hand side is dominated by $(1+o(1)) (\frac{d}{n})^k \prod_{i=0}^k |E_i|$. This
implies that

$$
e_{\{r_1, \dots, r_k\}}(E_0; \{E1, \dots, E_k\}) = \sum_{v \in E_0} \prod_{i=1}^{k} N_{E_i}^{r_i}(v) = (1+o(1)) \left(\frac{d}{n}\right)^k \prod_{i=0}^{k} |E_i|,
$$

completing the proof of the theorem.

□

3 Finite Euclidean and non-Euclidean graphs

In this section, we construct our main tools to study simplexes in vector spaces over finite fields, the
graphs associated to finite Euclidean and non-Euclidean spaces. The construction of finite Euclidean
graphs follows one of Medrano et al. in (12) and the construction of finite non-Euclidean graphs follows
one of Bannai, Shimabukuro, and Tanaka in (3).

3.1 Finite Euclidean graphs

Let $\mathbb{F}_q$ be a finite field with $q$ elements where $q \gg 1$ is an odd prime power. For any $x = (x_1, \dots, x_d) \in \mathbb{F}_q^d$, let

$$
\|x\| = x_1^2 + \dots + x_d^2.
$$

For a fixed $a \in \mathbb{F}_q$, the finite Euclidean graph $G_q(a)$ in $\mathbb{F}_q^d$ is defined as the graph with the vertex set $\mathbb{F}_q^d$,
and the edge set

$$
\{(x, y) \in \mathbb{F}_q^d \times \mathbb{F}_q^d \mid x \neq y, \|x - y\| = a\}.
$$

Medrano et al. (12) studied the spectrum of these graphs and showed that these graphs are asymptotically
Ramanujan graphs. Precisely, they proved the following result.

**Theorem 3.1** ((12)) *The finite Euclidean graph* $G_q(a)$ *is a regular graph with n(q, a) = q<sup>d</sup> vertices of valency*

$$
k(q, a) = \begin{cases}
q^{d-1} + \chi((-1)^{(d-1)/2}a)q^{(d-1)/2} & a \neq 0, \ d \text{ odd,} \\
q^{d-1} - \chi((-1)^{d/2}))q^{(d-2)/2} & a \neq 0, \ d \text{ even,} \\
q^{d-1} & a = 0, \ d \text{ odd,} \\
q^{d-1} - \chi((-1)^{d/2}))(q-1)q^{(d-2)/2} & a = 0, \ d \text{ even.}
\end{cases}
$$

where $\chi$ is the quadratic character

$$
\chi(a) = \begin{cases} 1 & a \neq 0, \text{ a is square in } \mathbb{F}_q, \\ -1 & a \neq 0, \text{ a is nonsquare in } \mathbb{F}_q, \\ 0 & a = 0. \end{cases}
$$
Let $\lambda$ be any eigenvalues of the graph $G_q(a)$ with $\lambda \neq$ valency of the graph then

$$|\lambda| \le 2q^{\frac{d-1}{2}}. \qquad (3.1)$$

## 3.2 Finite non-Euclidean graphs

Let $V = \mathbb{F}_q^{2k-1}$ be the $(2k-1)$-dimensional vector space over the finite field $\mathbb{F}_q$ ($q$ is an odd prime power). For each element $x$ of $V$, we denote the 1-dimensional subspace containing $x$ by $[x]$. Let $\Omega$ be the set of all square type non-isotropic 1-dimensional subspaces of $V$ with respect to the quadratic form $Q(x) = x_1^2 + \dots + x_{2k-1}^2$. The simple orthogonal group $O_{2k-1}(\mathbb{F}_q)$ acts transitively on $\Omega$, and yields a symmetric association scheme $\Psi(O_{2k-1}(\mathbb{F}_q), \Omega)$ of class $(q+1)/2$. The relations of $\Psi(O_{2k-1}(\mathbb{F}_q), \Omega)$ are given by

$$R_1 = \{([U], [V]) \in \Omega \times \Omega \mid (U+V) \cdot (U+V) = 0\},$$

$$R_i = \{([U], [V]) \in \Omega \times \Omega \mid (U+V) \cdot (U+V) = 2 + 2\nu^{-(i-1)}\} \quad (2 \le i \le (q-1)/2)$$

$$R_{(q+1)/2} = \{([U], [V]) \in \Omega \times \Omega \mid (U+V) \cdot (U+V) = 2\},$$

where $\nu$ is a generator of the field $\mathbb{F}_q$ and we assume $U \cdot U = 1$ for all $[U] \in \Omega$ (see (2) for more details).

The graphs $(\Omega, R_i)$ are asymptotic Ramanujan for large $q$. The following theorem summarizes the results from Section 2 in (3) in a rough form.

**Theorem 3.2 (3)** The graphs $(\Omega, R_i)$ $(1 \le i \le (q+1)/2)$ are regular of order $q^{2k-2}(1 + o_q(1))/2$ and valency $Kq^{2k-3}$. Let $\lambda$ be any eigenvalue of the graph $(\Omega, R_i)$ with $\lambda \neq$ valency of the graph then

$$|\lambda| \le kq^{(2k-3)/2},$$

for some $k, K > 0$ (In fact, we can show that $k = 2 + o_q(1)$ and $K = 1 + o_q(1)$ or $1/2 + o_q(1)$).

# 4 Proof of Theorem 1.1

We now give a proof of Theorem 1.1. For any $\{a_{ij}\}_{1 \le i < j \le k+1} \in \mathbb{F}_q^{(k+1)/2}$, define

$$T_{\{a_{ij}\}_{1 \le i < j \le k+1}}(E) = \{(x_i)_{i=1}^{k+1} \in E^{k+1} : \|x_i - x_j\| = a_{ij}\}.$$

Hart and Iosevich (7) observed that in vector spaces over finite fields, a (non-degenerate) simplex is defined uniquely (up to translation and rotation) by the norms of its edges.

**Lemma 4.1 ((7))** Let $P$ be a (non-degenerate) simplex with vertices $V_0, V_1, \dots, V_k$ where $V_j \in \mathbb{F}_q^d$. Let $P'$ be another (non-degenerate) simplex with vertices $V'_0, \dots, V'_k$. Suppose that

$$\|V_i - V_j\| = \|V'_i - V'_j\| \qquad (4.1)$$

for all $i, j$. There exists $\tau \in \mathbb{F}_q^d$ and $O \in SO_d(\mathbb{F}_q)$ such that $\tau + O(P) = P'$.

Therefore, it suffices to show that if $E \subset \mathbb{F}_q^{2k-1}$ ($k \ge 3$) of cardinality $|E| \gg q^{2k-1-1/2k}$, then

$$\left| \left\{ a_{ij} \mid 1 \le i < j \le k+1 \in \mathbb{F}_q^{(k+1)/2} : |T_{\{a_{ij}\}_{1 \le i < j \le k+1}}(E)| > 0 \right\} \right| \ge c q^{(k+1)/2}. \qquad (4.2)$$
Consider the set of colors $L = \{c_0, \dots, c_{q-1}\}$ corresponding to elements of $\mathbb{F}_q$. We color the complete graph $G_q$ with the vertex set $\mathbb{F}_q^{2k-1}$, by $q$ colors such that $(x, y) \in \mathbb{F}_q^{2k-1} \times \mathbb{F}_q^{2k-1}$ is colored by $c_i$ whenever $\|x - y\| = i$.

Suppose that $|E| \gg q^{2k-1-\frac{1}{2k}}$, we have

$$|E| \gg \left( \frac{q^{2k-1} \cdot 2q^{k-1}}{q^{2k-2}(1+o(1))} \right)^{\frac{2i}{i+2}},$$

for all $2 \le i \le k$. From Theorem 3.1, $G_q$ is a $(q^{2k-1}, q^{2k-2}(1+o(1)), 2q^{k-1})$-r.c. graph when $k \ge 3$. Therefore, applying Theorem 2.5 for the number of k-stars of type $(a_{12}, \dots, a_{1(k+1)})$ in $E^{k+1}$, we have

$$e_{a_{12}, \dots, a_{1(k+1)}}(E; \{E, \dots, E\}) = \left( \frac{q^{2k-2}(1+o(1))}{q^{2k-1}} \right)^k |E|^{k+1}(1+o(1)) = \frac{|E|^{k+1}(1+o(1))}{q^k},$$

for any $a_{12}, \dots, a_{1(k+1)} \in \mathbb{F}_q$.

Let $\mathbb{F}_q^*$ denote the set of non-zero squares in $\mathbb{F}_q$. For any $a_{12}, \dots, a_{1(k+1)} \in \mathbb{F}_q^*$, then

$$ \begin{aligned} |\{(x_1, \dots, x_{k+1}) \in E^{k+1} : \|x_1 - x_i\| = a_{1i}\}| &= e_{a_{12}, \dots, a_{1(k+1)}}(E; \{E, \dots, E\}) \\ &= \frac{|E|^{k+1}(1+o(1))}{q^k}. \end{aligned} $$

By the pigeon-hole principle, there exists $x_1 \in E$ such that

$$\{(x_2, \dots, x_{k+1}) \in E^k : \|x_1 - x_i\| = a_{1i}\} = \frac{|E|^k(1+o(1))}{q^k}.$$

Let $S_t = \{v \in \mathbb{F}_q^{2k-1} : \|v\| = t\}$ denote the sphere of radius $t$ in $\mathbb{F}_q^{2k-1}$, then

$$|S_t| = q^{2k-2}(1+o(1))$$

for any $t \in \mathbb{F}_q$. Let

$$E_i = \{v \in E : \|x_1 - v\| = a_{1i}\} \subset S_{a_i}, \quad 2 \le i \le k+1,$$

then

$$|E_2| \dots |E_{k+1}| = \frac{|E|^k(1+o(1))}{q^k},$$

and

$$|E_2|, \dots, |E_{k+1}| \le O(q^{2k-2}).$$

This implies that

$$|E_i| \ge \Omega \left( \frac{|E|^k (1+o(1))}{q^{k+(2k-2)(k-1)}} \right) \gg q^{2k-\frac{5}{2}}.$$

There are $(q-1)^k/2^k$ possibilities of $a_{12}, \dots, a_{1(k+1)} \in \mathbb{F}_q^*$. From Lemma 4.1, it suffices to show that $T_k(E_2, \dots, E_{k+1}) \ge c q^{(\frac{k}{2})}$ for some $c > 0$. Let

$$E'_i = \{[x] : x \in E_i\} \subset \Omega$$
where $\Omega$ is the set of all square type non-isotropic 1-dimensional subspaces of $\mathbb{F}_q^{2k-1}$ with respect to the quadratic form $Q(x) = x_1^2 + \dots + x_{2k-1}^2$. Since each line through origin in $\mathbb{F}_q^{2k-1}$ intersects the unit sphere $S_1$ at two points, $|E'_i| \ge |E_i|/2 \gg q^{2k-\frac{5}{2}}$. Suppose that $([U], [V]) \in E'_i \times E'_j$ is an edge of $(\Omega, R_l)$, $2 \le l \le (q-1)/2$. Then

$$ (U+V) \cdot (U+V) = 2 + \alpha_l, $$

where $\alpha_l = 2\nu^{-(l-1)}$. Since $U \cdot U = V \cdot V = 1$, we have $(U-V) \cdot (U-V) = 2 - \alpha_l$. The distance between $U$ and $V$ (in $E'_i \times E'_j$) is either $(U+V) \cdot (U+V)$ or $(U-V) \cdot (U-V)$. Hence,

$$ \|U - V\| \in \{2 + \alpha_l, 2 - \alpha_l\}. \qquad (4.3) $$

Consider the set of colors $L = \{r_1, \dots, r_{(q+1)/2}\}$ corresponding to classes of the association scheme $\Psi(O_{2k-1}(\mathbb{F}_q), \Omega)$. We color the complete graph $P_q$ with the vertex set $\Omega$, by $(q+1)/2$ colors such that $([U], [V]) \in \Omega \times \Omega$ is colored by $r_i$ whenever $([U], [V]) \in R_i$.

From Theorem 3.2, $P_q$ is a $((1+o(1))q^{2k-2}/2, Kq^{2k-3}, kq^{(2k-3)/2})$-r.c. graph when $k \ge 3$. Since $|E'_i| \gg q^{2k-\frac{5}{2}}$, we have

$$ |E'_i| \gg kq^{(2k-3)/2} \left( \frac{(1+o(1))q^{2k-2}/2}{Kq^{2k-3}} \right)^{k-1}. $$

Therefore, applying Theorem 2.4 for colored $k$-complete subgraphs of $P_q$ then $P_q$ contains all possible colored $k$-complete subgraphs. From (4.3), $([U], [V])$ is colored by $r_l$ ($2 \le l \le (q-1)/2$) then $\|U-V\| \in \{2 + \alpha_l, 2 - \alpha_l\}$. Hence, $T_k(E_2, \dots, E_{k+1}) \ge c q^{(\frac{k}{2})}$ for some $c > 0$. The theorem follows.

## Acknowledgements

A part of this research is performed during the author's visit at the Erwin Schrödinger International Institute for Mathematical Physics. The author would like to thank the ESI for hospitality and financial support during his visit.

## References

[1] N. Alon and J. H. Spencer, *The probabilistic method*, 2nd ed., Willey-Interscience, 2000.

[2] E. Bannai, S. Hao and S.-Y. Song, Character tables of the association schemes of finite orthogonal groups acting on the nonisotropic points, *Journal of Combinatorial Theory, Series A* **54** (1990), 164-170.

[3] E. Bannai, O. Shimabukuro and H. Tanaka, Finite analogues of non-Euclidean spaces and Ramanujan graphs, *European Journal of Combinatorics* **25** (2004), 243-259.

[4] J. Bourgain, A Szemerédi type theorem for sets of positive density, *Israel J. Math.* **54** (1986), no. 3, 307-331.

[5] D. Covert, D. Hart, A. Iosevich and I. Uriarte-Tuero, An analog of the Furstenberg-Katznelson-Weiss theorem on triangles in sets of positive density in finite field geometries, preprint (2008).
[6] H. Furstenberg, Y. Katznelson and B. Weiss, Ergodic theory and configurations in sets of positive density, Mathematics of Ramsey Theory, 184-198, *Algorithms Combi.*, **5**, Springer, Berlin (1990).

[7] D. Hart and A. Iosevich, Ubiquity of simplices in subsets of vector spaces over finite fields, *Analysis Mathematika*, **34** (2007).

[8] 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, preprint (2007).

[9] M. Krivelevich and B. Sudakov, Pseudo-random graphs, *Conference on Finite and Infinite Sets Burdpest*, Bolyai Society Mathematical Studies X, pp. 1–64.

[10] A. Magyar, On distance sets of large sets of integer points, Israel Math J. (to appear), (2006).

[11] A. Magyar, *k*-points configurations in sets of positive density of $\mathbb{Z}^d$, Duke Math J. (to appear), (2007).

[12] A. Medrano, P. Myers, H. M. Stark and A. Terras, Finite analogues of Euclidean space, *Journal of Computational and Applied Mathematics*, **68** (1996), 221–238.

[13] L. A. Vinh, On a Furstenberg-Katznelson-Weiss type theorem over finite fields, *Annals of Combinatorics*, to appear.

[14] L. A. Vinh, On kaleidoscopic pseudo-randomness of finite Euclidean graphs, submitted.

[15] L. A. Vinh, Triangles in vector spaces over finite fields, *Online Journal of Analytic Combinatorics*, to appear.