LONG PATHS IN THE DISTANCE GRAPH OVER LARGE SUBSETS OF VECTOR SPACES OVER FINITE FIELDS

Abstract

Let <TEX>$E{\subset}{\mathbb{F}}^d_q$</TEX>, the d-dimensional vector space over the finite field with q elements. Construct a graph, called the distance graph of E, by letting the vertices be the elements of E and connect a pair of vertices corresponding to vectors x, y 2 E by an edge if <TEX>${\parallel}x-y{\parallel}:=(x_1-y_1)^2+{\cdots}+(x_d-y_d)^2=1$</TEX>. We shall prove that the non-overlapping chains of length k, with k in an appropriate range, are uniformly distributed in the sense that the number of these chains equals the statistically correct number, <TEX>$1{\cdot}{\mid}E{\mid}^{k+1}q^{-k}$</TEX> plus a much smaller remainder.