MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
Wait, my pardon, how are we adding the $s_i$'s? – Chris Feb 25 '11 at 20:50
$|S_i|=s_i$, since we have $P^2=\cup S_i$ you get $\sum s_i=N^2$. – Gjergji Zaimi Feb 25 '11 at 22:19
Awesome. Crystal clear now. Thanks :) – 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)}. $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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