2 Notation

We recall some basic notation which we will use throughout the paper.

Let $\mathrm {O}_d(\mathbb {F}_q)$ denote the group of orthogonal $d\times d$ matrices with entries in $\mathbb {F}_q$ .

Let $\mathbb {F}_q^*$ denote the set of nonzero elements in $\mathbb {F}_q$ , that is, $\mathbb {F}^*_q=\big \{a\in \mathbb {F}_q: a\neq 0 \big \}$ .

Let $(\mathbb {F}_q)^2$ denote the set of quadratic residues in $\mathbb {F}_q$ , that is, $(\mathbb {F}_q)^2=\big \{a^2: a\in \mathbb {F}_q \big \}$ .

Define the map $\lVert \cdot \rVert : \mathbb {F}_q^d \to \mathbb {F}_q$ by , where $\alpha = (\alpha _1, \ldots , \alpha _d) \in \mathbb {F}_q^d$ . This map is not a norm, as we do not impose a metric structure on $\mathbb {F}_q^d$ . However, it shares an important property with the Euclidean norm: it is invariant under orthogonal transformations.

If X is a finite set, let $|X|$ denote its cardinality.

3 First proof of Theorem 1.3

Let $k \in \mathbb {N}$ and $\varnothing \neq A \subset \{(i, j) : 1 \leq i < j \leq k + 1\}$ . For $r \in (\mathbb {F}_q)^2 \setminus \{0\}$ , $z \in \mathbb {F}_q^d$ and $\theta \in \mathrm {O}_d(\mathbb {F}_q)$ , define the counting function:

(3.1)

For $p \geq 1$ , we define the $L^p$ -norm of $\lambda _{r,\theta }(z)$ as follows:

From (3.1),

$$ \begin{align*} \lambda_{r,\theta}(z)^{k+1} = | \{(u_1, \dots, u_{k+1}, v_1, \dots, v_{k+1}) \in E^{2k+2} : u_i - \sqrt{r}\theta v_i = z, \ i \in [k+1] \} |. \end{align*} $$

Then, we obtain

$$ \begin{align*} & \lVert \lambda_{r,\theta}(z)\rVert_{k+1}^{k+1} =\sum_{\theta,z}\lvert\{(u_1,\dots,u_{k+1},v_1,\dots,v_{k+1})\in E^{2k+2}: u_i-\sqrt{r}\theta v_i=z,\ i\in [k+1]\}\rvert\\ & =\sum_{\theta}\lvert\big\{(u_1,\dots,u_{k+1},v_1,\dots,v_{k+1})\in E^{2k+2}: u_i-u_j=\sqrt{r}\theta (v_i-v_j),\ 1\leq i< j\leq k+1 \big\}\rvert. \end{align*} $$

Let us introduce the notation:

With this notation, one can express the $L^{k+1}$ -norm of the function $\lambda _{r,\theta }(z)$ in terms of $|\Lambda _{\theta }(r)|$ :

$$ \begin{align*} \lVert \lambda_{r,\theta}(z)\rVert_{k+1}^{k+1}=\sum_{\theta\in \mathrm{O}_d(\mathbb{F}_q)}|\Lambda_{\theta}(r)|. \end{align*} $$

Let us consider the auxiliary sets:

$$ \begin{align*} \mathcal{N}_{A,\theta}(r)& :=\bigg\{(u_1,\dots,u_{k+1},v_1,\dots,v_{k+1})\in E^{2k+2}: \begin{array}{l} u_i-u_{j}=\sqrt{r}\theta(v_i-v_j),\ (i,j)\in A,\\ v_i\neq v_j,\ 1\leq i< j\leq k+1\end{array}\!\!\bigg\}, \\ \mathcal{N}_{\theta}(r)& :=\bigg\{(u_1,\dots,u_{k+1},v_1,\dots,v_{k+1})\in E^{2k+2}: \begin{array}{l} u_i-u_{j}=\sqrt{r}\theta(v_i-v_j),\\ v_i\neq v_j,\ 1\leq i<j\leq k+1\end{array}\!\!\bigg\}. \end{align*} $$

To prove Theorem 1.3, we need to show that $\lvert \mathcal {S}_A\rvert>0$ , where

It is easy to verify that $\mathcal {N}_{A,\theta }(r)\subset \mathcal {S}_A$ for each $\theta \in \mathrm {O}_d(\mathbb {F}_q)$ and hence

(3.2) $$ \begin{align} \lvert \mathcal{S}_A\rvert\geq \frac{1}{\lvert \mathrm{O}_d(\mathbb{F}_q)\rvert}\sum_{\theta\in \mathrm{O}_d(\mathbb{F}_q)}|\mathcal{N}_{A,\theta}(r)|. \end{align} $$

Since $\mathcal {N}_{\theta }(r)\subset \mathcal {N}_{A,\theta }(r)$ for each $\theta \in \mathrm {O}_d(\mathbb {F}_q)$ , (3.2) yields

(3.3) $$ \begin{align} \lvert \mathcal{S}_A\rvert\geq \frac{1}{\lvert \mathrm{O}_d(\mathbb{F}_q)\rvert}\sum_{\theta\in \mathrm{O}_d(\mathbb{F}_q)}|\mathcal{N}_{\theta}(r)|. \end{align} $$

For each pair $(\alpha ,\beta )$ such that $1\leq \alpha <\beta \leq k+1$ , we define

$$ \begin{align*} A_{\alpha,\beta}:=\bigg\{(u_1,\dots,u_{k+1},v_1,\dots,v_{k+1})\in E^{2k+2}: \begin{array}{l} u_i-u_{j}=\sqrt{r}\theta(v_i-v_j),\\ 1\leq i<j\leq k+1,\ v_{\alpha}=v_{\beta}\end{array}\!\!\bigg\}. \end{align*} $$

From the set equality

$$ \begin{align*} \Lambda_{\theta}(r)\setminus \bigcup_{1\leq \alpha<\beta\leq k+1}A_{\alpha,\beta}=\mathcal{N}_{\theta}(r), \end{align*} $$

we obtain

(3.4) $$ \begin{align} |\mathcal{N}_{\theta}(r)|\geq |\Lambda_{\theta}(r)|-\sum \limits_{1\leq \alpha<\beta\leq k+1}|A_{\alpha,\beta}|. \end{align} $$

One can verify that, for $(\alpha ,\beta )$ with $1\leq \alpha <\beta \leq k+1$ ,

(3.5) $$ \begin{align} |A_{\alpha,\beta}|=\sum \limits_{z\in \mathbb{F}_q^d}\lambda_{r,\theta}(z)^k. \end{align} $$

Substituting (3.5) into (3.4}, we obtain

(3.6) $$ \begin{align} |\mathcal{N}_{\theta}(r)|\geq |\Lambda_{\theta}(r)|-\binom{k+1}{2}\sum \limits_{z\in \mathbb{F}_q^d}\lambda_{r,\theta}(z)^k. \end{align} $$

Summing (3.6) over all $\theta \in \mathrm {O}_d(\mathbb {F}_q)$ yields

(3.7) $$ \begin{align} \sum \limits_{\theta}|\mathcal{N}_{\theta}(r)|\geq \sum \limits_{\theta}|\Lambda_{\theta}(r)|-\binom{k+1}{2}\sum \limits_{\theta,z}\lambda_{r,\theta}(z)^k. \end{align} $$

Combining (3.7) and (3.3),

(3.8) $$ \begin{align} |\mathcal{S}_A|\geq \frac{1}{|\mathrm{O}_d(\mathbb{F}_q)|}\bigg(\lVert{\lambda_{r,\theta}(z)\rVert}_{k+1}^{k+1}-\binom{k+1}{2}\lVert{\lambda_{r,\theta}(z)\rVert}_{k}^{k}\bigg). \end{align} $$

Note that the lower bound for the size of $\mathcal {S}_A$ is independent of A. This is a key aspect of the result being proven.

Now, we will demonstrate that if $\lvert E\rvert \geq C_k q^{d/2}$ , then $\lvert \mathcal {S}_{A}\rvert> 0$ . By applying Hölder’s inequality, we can establish a lower bound for the $L^{k+1}$ -norm of $\lambda _{r,\theta }(z)$ , namely

(3.9) $$ \begin{align} \sum_{\theta,z}\lambda_{r,\theta}(z)^{k+1}\geq \lvert \mathrm{O}_d(\mathbb{F}_q)\rvert\cdot \frac{|E|^{2k+2}}{q^{dk}}. \end{align} $$

The second term in (3.8) can be divided into two separate sums, where the terms are categorised as either ‘small’ or ‘large’. More precisely,

(3.10) $$ \begin{align} \lVert{\lambda_{r,\theta}(z)\rVert}_{k}^{k}=\sum_{\theta,z}\lambda_{r,\theta}(z)^k =\sum_{\lambda\geq c}\lambda_{r,\theta}(z)^k+\sum_{\lambda<c}\lambda_{r,\theta}(z)^k, \end{align} $$

where the parameter $c\in \mathbb {R}_{\geq 0}$ will be chosen later. Combining (3.10) with (3.8), we obtain the lower bound:

(3.11) $$ \begin{align} \lvert\mathcal{S}_A\rvert\geq \frac{1}{\lvert \mathrm{O}_d(\mathbb{F}_q)\rvert} \big(\mathcal{S}_1+\mathcal{S}_2\big), \end{align} $$

where

$$ \begin{align*} \mathcal{S}_1=\frac{1}{2}\lVert \lambda_{r,\theta}(z)\rVert_{k+1}^{k+1}-\binom{k+1}{2}\sum_{\lambda\geq c}\lambda_{r,\theta}(z)^k, \end{align*} $$

$$ \begin{align*} \mathcal{S}_2=\frac{1}{2}\lVert \lambda_{r,\theta}(z)\rVert_{k+1}^{k+1}-\binom{k+1}{2}\sum_{\lambda< c}\lambda_{r,\theta}(z)^k. \end{align*} $$

By using the definition of the $L^{k+1}$ -norm of $\lambda _{r,\theta }(z)$ , we can establish the following lower bound for $\mathcal {S}_1$ :

$$ \begin{align*} \mathcal{S}_1\geq \frac{1}{2}\bigg(\sum_{\lambda\geq c}\lambda_{r,\theta}(z)^{k+1}-k(k+1)\sum_{\lambda\geq c}\lambda_{r,\theta}(z)^{k}\bigg) =\frac{1}{2}\bigg(\sum_{\lambda \geq c} \lambda_{r,\theta}(z)^k(\lambda_{r,\theta}(z)-k(k+1))\bigg). \end{align*} $$

Choosing $c = k(k+1)$ shows that $\mathcal {S}_1 \geq 0$ .

Next, we estimate $\mathcal {S}_2$ : for the first term, we use (3.9), and for the second term, we provide a straightforward estimate. Thus,

(3.12) $$ \begin{align} \mathcal{S}_2&\geq \frac{|E|^{2k+2}}{2q^{dk}}\cdot \lvert \mathrm{O}_d(\mathbb{F}_q)\rvert-\binom{k+1}{2}\sum_{\lambda<c}\lambda_{r,\theta}(z)^k \nonumber\\& \geq \frac{|E|^{2k+2}}{2q^{dk}}\cdot \lvert \mathrm{O}_d(\mathbb{F}_q)\rvert - c^k\binom{k+1}{2}\sum_{\theta, z} 1 \nonumber\\& \geq \lvert \mathrm{O}_d(\mathbb{F}_q)\rvert \bigg(\frac{|E|^{2k+2}}{2q^{dk}}-\frac{(k^2+k)^{k+1}q^d}{2}\bigg). \end{align} $$

We note that $\lvert \mathrm {O}_d(\mathbb {F}_q) \rvert> 0$ . By combining this observation with the inequalities $\mathcal {S}_1 \geq 0$ as well as (3.12) and (3.11), we obtain

$$ \begin{align*} \lvert \mathcal{S}_A \rvert \geq \frac{|E|^{2k+2}}{2q^{dk}} - \frac{(k^2+k)^{k+1}q^d}{2}. \end{align*} $$

It is not difficult to verify that if $\lvert E \rvert \geq 2k q^{d/2}$ , then $\lvert \mathcal {S}_A \rvert> 0$ , which completes the proof of Theorem 1.3.

4 Second proof of Theorem 1.3

In this section, we will prove Theorem 1.3 using elementary combinatorial arguments.

Suppose $E\subset \mathbb {F}_q^d$ and $r\in (\mathbb {F}_q)^2\setminus \{0\}$ , so $r=t^2$ where $t\neq 0$ . For such t, define $tE$ as $tE = \{tv : v\in E\}$ .

Now, consider the set:

$$ \begin{align*} H = \{(x,a) : x\in tE\cap (E+a),\ a\in \mathbb{F}_q^d\}. \end{align*} $$

We will use double counting to determine the cardinality of H. First,

(4.1) $$ \begin{align} \lvert H\rvert =\sum_{x\in tE}\sum_{\substack{a\in \mathbb{F}_q^d \\ x\in E+a}}1=\sum_{x\in tE}\sum_{\substack{a\in \mathbb{F}_q^d \\ a\in x-E}}1 =\sum_{x\in tE}\lvert x-E \rvert=\sum_{x\in tE}\lvert E\rvert =\lvert tE\rvert \lvert E\rvert=\lvert E\rvert^2. \end{align} $$

However, by changing the order of variables,

(4.2) $$ \begin{align} \lvert H\rvert =\sum_{a\in \mathbb{F}_q^d}\sum_{\substack{x\in tE \\ x\in E+a}}1 =\sum_{a\in \mathbb{F}_q^d}\lvert tE\cap (E+a)\rvert. \end{align} $$

Comparing (4.1) with (4.2) yields

$$ \begin{align*} \sum_{a\in \mathbb{F}_q^d}\lvert tE\cap (E+a)\rvert=\lvert E\rvert^2. \end{align*} $$

Therefore,

$$ \begin{align*} \max_{a\in \mathbb{F}_q^d}\lvert tE\cap (E+a)\rvert\geq \frac{\lvert E\rvert^2}{q^d}. \end{align*} $$

We observe that if $\lvert E \rvert \geq \sqrt {k+1}q^{d/2}$ , then $\max_{a\in \mathbb{F}_q^d} \lvert tE \cap (E + a) \rvert \geq k + 1$ . Thus, there exists an element $a \in \mathbb {F}_q^d$ such that $\lvert tE \cap (E + a) \rvert \geq k+1$ . Consequently, we can establish the existence of a sequence $\{z_1,\dots ,z_{k+1}\}$ such that $\{z_1,\dots ,z_{k+1}\}\subset tE \cap (E + a)$ . This implies the existence of sequences $\{x_1,\dots ,x_{k+1}\} \subset E$ and $\{y_1,\dots ,y_{k+1}\} \subset E$ , such that $z_i = tx_i$ and $z_i = y_i + a$ for $1\leq i\leq k+1$ .

In summary, we have demonstrated the existence of $(k+1)$ -tuples $(x_1, \ldots , x_{k+1}) \in E^{k+1}$ and $(y_1, \ldots , y_{k+1}) \in E^{k+1}$ satisfying the conditions:

1. (1) $x_i \neq x_j, y_i\neq y_j$ for $1 \leq i < j \leq k+1$ ;

2. (2) $y_i + a = tx_i$ for $i \in \{1, \ldots , k+1\}$ .

Therefore, for $1\leq i<j\leq k+1$ ,

$$ \begin{align*} \lVert y_i-y_j\rVert=\lVert (tx_i-a)-(tx_j-a)\rVert=\lVert tx_i-tx_j\rVert=t^2 \lVert x_i-x_j\rVert=r\lVert x_i-x_j\rVert. \end{align*} $$

Since A is a nonempty subset of $\{(i, j) : 1 \leq i < j \leq k+1\}$ , we have demonstrated the existence of two $(k+1)$ -point configurations: $(x_1, \ldots , x_{k+1}) \in E^{k+1}$ and $(y_1, \ldots , y_{k+1}) \in E^{k+1}$ satisfying:

1. (1) $x_i \neq x_j$ and $y_i \neq y_j$ for $1 \leq i < j \leq k+1$ ;

2. (2) $\lVert y_i - y_j \rVert = r \lVert x_i - x_j \rVert $ for $(i, j) \in A$ .

This completes the proof of Theorem 1.3.

5 Corollaries

In this section, we will explore some interesting corollaries that follow from Theorem 1.3. For simplicity, we assume a two-dimensional scenario, that is, $d = 2$ .

5.2 Cycles of length k

Assuming that $k\geq 3$ , for k-cycles, one needs to take $A=\{(1,2),\dots ,(k-1,k), (k,1)\}$ . Then, we can see that for $E\subset \mathbb {F}_q^2$ with $\lvert E\rvert \geq 2kq$ , there exist k-cycles in E. That is, there exist $(x_1,\dots ,x_k)\in E^k$ and $(y_1,\dots ,y_k)\in E^k$ such that $x_i\neq x_j$ and $y_i\neq y_j$ for $1\leq i<j\leq k$ , and $\lVert y_i-y_{i+1}\rVert =r\lVert x_i-x_{i+1}\rVert $ for $i\in \{1,\dots , k-1\}$ , and $\lVert y_k-y_{1}\rVert =r\lVert x_k-x_{1}\rVert $ (see Figure 3).

Figure 2 6-paths with a dilation ratio of $r\in (\mathbb {F}_q)^2\setminus \{0\}$ .

Figure 3 6-cycles with a dilation ratio of $r\in (\mathbb {F}_q)^2\setminus \{0\}$ .

5.3 Stars with k edges

Assuming that $k\geq 1$ , for k-stars, one needs to take $A=\{(1,2),\dots , (1,k+1)\}$ . Then, for $E\subset \mathbb {F}_q^2$ with $|E|\geq 2k q$ , there exist k-stars in E. That is, there exist $(x_1,\dots ,x_{k+1})\in E^{k+1}$ and $(y_1,\dots ,y_{k+1})\in E^{k+1}$ such that $x_i\neq x_j$ and $y_i\neq y_j$ for $1\leq i<j\leq k+1$ , and $\lVert y_1-y_i\rVert =r\lVert x_1-x_i\rVert $ for $i\in \{2,\dots ,k+1\}$ (see Figure 4).

Figure 4 5-stars with a dilation ratio of $r\in (\mathbb {F}_q)^2\setminus \{0\}$ .

6 Sharp examples

In this section, we will demonstrate that in dimension 2, the exponent $d/2$ in Theorem 1.3 is optimal under certain mild conditions.

6.1 The case when $\lvert A\rvert \geq 1$

In this setting, we will demonstrate that if $q=p^{2\ell }$ with $p\equiv 3 \pmod 4$ and $\ell \equiv 1 \pmod 2$ , the exponent $d/2$ in Theorem 1.3 is optimal.

The ambient space is $\mathbb {F}_{p^{2\ell }}^{2}$ , a $2$ -dimensional vector space over the finite field $\mathbb {F}_{p^{2\ell }}$ with $p^{2\ell }$ elements. The field $\mathbb {F}_{p^{2\ell }}$ contains the subfield $\mathbb {F}_{p^{\ell }}$ with $p^{\ell }$ elements. Consider the subset of $\mathbb {F}_{p^{2\ell }}^{2}$ and observe that $\lvert E\rvert =q$ .

We know that $\lvert (\mathbb {F}_{p^{2\ell }})^2\setminus \{0\}\rvert =\tfrac 12(p^{2\ell }-1)>p^{\ell }=\lvert \mathbb {F}_{p^{\ell }}\rvert $ , and one can always choose $r\in (\mathbb {F}_{p^{2\ell }})^2$ such that $r\notin \mathbb {F}_{p^{\ell }}$ . Then, for any $x_i,x_j,y_i,y_j\in E$ such that $x_i\neq x_j$ and $y_i\neq y_j$ , we have

$$ \begin{align*} \frac{\lVert y_i-y_j \rVert}{\lVert x_i-x_j\rVert} \in \mathbb{F}_{p^{\ell}}. \end{align*} $$

Here, we have used the fact that $\lVert x\rVert =0$ if and only if $x=(0,0)$ , which is true since $p\equiv 3 \pmod 4$ and $\ell \equiv 1 \pmod 2$ . However, r was chosen such that $r\notin \mathbb {F}_{p^{\ell }}$ . This observation demonstrates that the exponent $d/2$ is optimal in this setting.

6.2 The case when A contains $(a,b),(a,c),(b,c)$

In this scenario, we will establish that if $q\equiv 3 \pmod {4}$ , then the exponent $d/2$ is the optimal exponent in Theorem 1.3.

Without loss of generality, assume that $(1,2),(1,3),(2,3)\in A$ , and let $r\in (\mathbb {F}_q)^2$ be such that $r\neq 1$ . Define E as the set:

which represents a sphere of radius $1$ in $\mathbb {F}_q^2$ . It can be shown that $\lvert E\rvert =q+1$ . Now, suppose there exist two sets of points $(x_1,\dots ,x_{k+1})\in E^{k+1}$ and $(y_1,\dots ,y_{k+1})\in E^{k+1}$ such that $x_i\neq x_j$ and $y_i\neq y_j$ for $1\leq i<j\leq k+1$ , and $\lVert y_i-y_j\rVert =r\lVert x_i-x_j\rVert $ for $(i,j)\in A$ . In particular, this implies that $\lVert y_i-y_j\rVert =r\lVert x_i-x_j\rVert $ for $(i,j)\in \{(1,2),(1,3),(2,3)\}$ .

For each $i\in \{1,2,3\}$ , define , which implies $z_i-z_j=\sqrt {r}(x_i-x_j)$ . Therefore, $\lVert y_i-y_j\rVert =\lVert z_i-z_j\rVert $ for $1\leq i<j\leq 3$ . This implies the existence of a transformation $T\in \text {ISO}(2)$ such that $T(y_i)=z_i$ for $i\in \{1,2,3\}$ , where $\text {ISO}(2)$ is the group of rigid motions.

Since $z_i=\sqrt {r}x_i$ , it follows that $\lVert z_i \rVert =r\lVert x_i\rVert =r$ . Also, we observe that $\lVert z_i-T(0)\rVert =\lVert y_i\rVert =1$ . Therefore, we have demonstrated that $\{z_1,z_2,z_3\}\subset S(T(0);1)\cap S(0;r)$ , where $S(a;R)$ denotes the sphere of radius R centred at a. However, the spheres $S(T(0);1)$ and $S(0;r)$ are distinct since $r\neq 1$ . This assumption leads to a contradiction since two distinct spheres in $\mathbb {F}_q^2$ have at most two points in their intersection. Thus, we have established that the exponent $d/2$ is indeed sharp in this setting.