Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

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|improve this answer
    
Wait, my pardon, how are we adding the $s_i$'s? –  Chris Feb 25 '11 at 20:50
1  
$|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.