Combinatorial incidence geometry is the study of the possible combinatorial configurations between geometric objects such as lines and circles. One of the basic open problems in the subject has been the Erd?s distance problem, posed in 1946:
Problem 1 (Erd?s distance problem) Let be a large natural number. What is the least number of distances that are determined by points in the plane?
Erd?s called this least number . For instance, one can check that and , although the precise computation of rapidly becomes more difficult after this. By considing points in arithmetic progression, we see that . By considering the slightly more sophisticated example of a lattice grid (assuming that is a square number for simplicity), and using some analytic number theory, one can obtain the slightly better asymptotic bound .