A note on the unit distance problem for planar configurations with Q-independent direction set

Abstract

Let T(n) denote the maximum number of unit distances that a set of n points in the Euclidean plane R 2 can determine with the additional condition that the distinct unit length directions determined by the configuration must be Q-independent. This is related to the Erd¨os unit distance problem but with a simplifying additional assumption on the direction set that holds generically . We show that T(n + 1) − T(n) is the Hamming weight of n, i.e. the number of nonzero binary coefficients in the binary expansion of n, and find a formula for T(n) explicitly. In particular, T(n) is Θ(nlog(n)). Furthermore, we describe a process to construct a set of n points in the plane with Q-independent unit length direction set that achieves exactly T(n) unit distances. In the process of doing this, we show T(n) is also the same as the maximum number of edges a subset of vertices of size n determines in either the countably infinite lattice Z ∞ or the infinite hypercube graph {0, 1} ∞ . The problem of determining T(n) can be viewed as either a type of packing or isoperimetric problem.