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


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


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.


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$.

  • $\begingroup$ Wait, my pardon, how are we adding the $s_i$'s? $\endgroup$ – Chris Feb 25 '11 at 20:50
  • 1
    $\begingroup$ $|S_i|=s_i$, since we have $P^2=\cup S_i$ you get $\sum s_i=N^2$. $\endgroup$ – Gjergji Zaimi Feb 25 '11 at 22:19
  • $\begingroup$ Awesome. Crystal clear now. Thanks :) $\endgroup$ – Chris Feb 26 '11 at 18:26

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)}. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.