Determining the vector space for application of Cauchy Schwarz - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T12:40:28Z http://mathoverflow.net/feeds/question/56663 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56663/determining-the-vector-space-for-application-of-cauchy-schwarz Determining the vector space for application of Cauchy Schwarz Chris 2011-02-25T18:40:11Z 2011-02-25T20:24:12Z <p>In the paper "On the Erdős distinct distance problem in the plane" by Larry Guth and Nets Hawk Katz,</p> <p><a href="http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf" rel="nofollow">http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf</a></p> <p>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</p> <p>$|d(P)|\ge\frac{N^4}{|Q(P)|}$</p> <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.</p> http://mathoverflow.net/questions/56663/determining-the-vector-space-for-application-of-cauchy-schwarz/56665#56665 Answer by Seva for Determining the vector space for application of Cauchy Schwarz Seva 2011-02-25T18:58:12Z 2011-02-25T20:24:12Z <p>I belive, the following is meant. Let $x_1,...,x_N$ be your points. Write <code>$P-P:=\{x_i-x_j\colon i,j\in[N] \}$</code> 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</p> <p>$$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)}.$$</p> <hr> <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</p> <p>$$Q(P) = \sum_l (r(l))^2 \ge \frac1{d(P)}\Big(\sum_l r(l)\Big)^2 = \frac{N^4}{d(P)}.$$</p> http://mathoverflow.net/questions/56663/determining-the-vector-space-for-application-of-cauchy-schwarz/56666#56666 Answer by Gjergji Zaimi for Determining the vector space for application of Cauchy Schwarz Gjergji Zaimi 2011-02-25T18:59:10Z 2011-02-25T18:59:10Z <p>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$.</p>