We prove that if a subset of a d-dimensional vector space over a finite field with q elements has more than qd?1 elements, then it determines all the possible directions. We obtain a complete characterization if the size of the set is ≥ qd?1. If a set has more than qk elements, it determines a k-dimensional set of directions. We prove stronger results for sets that are sufficiently random. This result is best possible as the example of a k-dimensional hyperplane shows. We can view this question as an Erd?os type problem where a sufficiently large subset of a vector space determines a large number of configurations of a given type. For discrete subsets of Rd, this question has been previously studied by Pach, Pinchasi and Sharir.
展开▼
