Cycles of arbitrary length in distance graphs on ${\mathbb{F}}_q^d$

Abstract

For $E\subset {\mathbb{F}}_q^d$, $d\ge 2$, where ${\mathbb{F}}_q$ is the finite field with $q$ elements, we consider the distance graph ${\mathcal{G}}_t^{dist}(E)$, $t\ne 0$, where the vertices are the elements of $E$, and two vertices $x$, $y$ are connected by an edge if $||x-y||\equiv {(x_1-y_1)}^2+\cdots +{(x_d-y_d)}^2=t$. We prove that if $|E|\ge C_k{q}^{\frac{d+2}{2}}$, then ${\mathcal{G}}_t^{dist}(E)$ contains a statistically correct number of cycles of length $k$. We are also going to consider the dot-product graph ${\mathcal{G}}_t^{prod}(E)$, $t\ne 0$, where the vertices are the elements of $E$, and two vertices $x$, $y$ are connected by an edge if $x\cdot y\equiv x_1{y}_1+\cdots +x_d{y}_d=t$. We obtain similar results in this case using more sophisticated methods necessitated by the fact that the function $x\cdot y$ is not translation invariant. The exponent $\frac{d+2}{2}$ is improved for sufficiently long cycles.