Question

In the paper "On the Erdős distinct distance problem in the plane" by Larry Guth and Nets Hawk Katz,

http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf

they define the functions $d(P)$, (distinct distances between $N$ points), and $Q(P)$, (quadruples on $N$ points where the distances between the first two points of the quadruple are equal to the second two points). They then apply Cauchy Schwarz to obtain

$|d(P)|\ge\frac{N^4}{|Q(P)|}$

However, I don't see how we can consider the functions $d$ and $Q$ to be functions in the same Vector Space, since one yields a set of distances, where the other yields a set of quadruples. If I can't interpret them as elements of a Vector Space, I don't see how Cauchy Schwarz can be applied.

Answer 1

Let $d(P)=\{d_1,\dots,d_r\}$ and write $P^2=\cup_{i=1}^r S_i$, where $(p_1,p_2)\in S_i$ if $|p_1,p_2|=d_i$. Now you can see that $Q(P)=\cup (S_i\times S_i)$ and so the inequality is only saying $$r(s_1^2+\cdots+s_r^2)\geq (s_1+\cdots+s_r)^2$$ because $s_1+\cdots+s_r=N^2$.

Answer 2

I belive, the following is meant. Let $x_1,...,x_N$ be your points. Write $P-P:=\{x_i-x_j\colon i,j\in[N] \}$ and for $x\in P-P$, denote by $r(x)$ the number of representations of $x$ in the form $x_i-x_j$ with $i,j\in[N]$. Since $Q(P)$ is the number of solutions of $x_i-x_j=x_k-x_l$, using Cauchy-Schwarz you get

$$ Q(P) = \sum_{x\in P-P} (r(x))^2 \ge \frac1{|P-P|}\Big(\sum_{x\in P-P} r(x)\Big)^2 = \frac{N^4}{d(P)}. $$

---

I've just realized that if distances are counted as numbers (instead of vectors), then the argument is to be suitably adjusted. Namely, for every possible distance $l$ let $r(l)$ denote the number of pairs of points from your set which are at distance $l$. Then $Q(P)$ is the number of quadruples $(x_i,x_j,x_k,x_s)$ with $|x_i-x_j|=|x_k-x_s|$, whence

$$ Q(P) = \sum_l (r(l))^2 \ge \frac1{d(P)}\Big(\sum_l r(l)\Big)^2 = \frac{N^4}{d(P)}. $$