Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T00:14:56Z http://mathoverflow.net/feeds/question/58718 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58718/degree-reduction-argument-in-guth-katzsproof-of-erdos-distinct-distance-problem Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane rrrq 2011-03-17T03:20:21Z 2011-03-17T12:21:08Z <p>In the middle of page 9 of <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 said " Now we select a random subset....choosing lines independently with probability $\frac{Q}{100}$. With positive probability....</p> <p>I can not see why there is positive probability...</p> <p>Could any one explain a bit about what is going on there? I feel they are applying large number law, but I can not see it clearly, for example what is the probability measure space, what is the random variables, how the law is used?..</p> http://mathoverflow.net/questions/58718/degree-reduction-argument-in-guth-katzsproof-of-erdos-distinct-distance-problem/58742#58742 Answer by Thomas Kalinowski for Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane Thomas Kalinowski 2011-03-17T12:21:08Z 2011-03-17T12:21:08Z <p>Not a complete answer but a quick explanation of how I read page 9 in that paper.</p> <ol> <li>The underlying probabilistic model is that for every line $l\in\mathfrak L'$ you throw a coin that shows head with probability $100/Q$ and tail with probability $(Q-100)/Q$, and then $\mathfrak L''$ is the set of all lines whose coin showed head. In other words, you choose a random subset $\mathfrak L''$ of $\mathfrak L'$ and the probability for choosing a particular set $\mathfrak L_0\subseteq \mathfrak L'$ equals $$\mathbf{P}[\mathfrak L''=\mathfrak L_0]=\left(\frac{100}{Q}\right)^{|\mathfrak L_0|}\left(1-\frac{100}{Q}\right)^{|\mathfrak L'\setminus\mathfrak L_0|}.$$</li> <li>By linearity of expectation the expected cardinality of $\mathfrak L''$ is $\mathbf{E}(|\mathfrak L''|)=\frac{100\alpha N^2}{Q}$, and this implies $$\mathbf{P}\left[|\mathfrak L''|\leqslant\frac{200\alpha N^2}{Q}\right]\geqslant\frac12.$$</li> <li>We are done when we can show that the probability of the event "Every line in $\mathfrak L'$ intersects $N/20$ lines in $\mathfrak L''$" has probability at least $1/2+\varepsilon$ for some positive $\varepsilon$, since then the event "$|\mathfrak L''|\leqslant\frac{200\alpha N^2}{Q}$ and every line in $\mathfrak L'$ intersects $N/20$ lines in $\mathfrak L''$" has probability at least $\varepsilon$. </li> </ol> <p>As I understand it, the intuition is that a typical line in $\mathfrak L'$ intersects a quadratic number of lines in $\mathfrak L'$ so it is highly unlikely that less than $N/20$ of these are chosen for $\mathfrak L''$. </p> <p>At the moment I don't see how to make that rigorous. I haven't read the rest of the paper, yet, but my impression is that it might be convenient (or even necessary) to replace $\mathfrak L'$ by something slightly smaller, throwing away some rubbish: </p> <ul> <li>I don't see why $\mathfrak L'$, as it is defined, cannot contain a few exceptional lines that have almost all their intersections with lines outside $\mathfrak L'$, so they intersect less than $N/20$ lines in $\mathfrak L'$. If this is the case, these lines have no chance to intersect $N/20$ lines in $\mathfrak L''$. </li> <li>It looks easier to show that with high probability almost every line in $\mathfrak L'$ intersects $\mathfrak L''$ at least $N/20$ times (instead of "every line in $\mathfrak L'$" ). Maybe it is sufficient to replace $\mathfrak L'$ by this big subset. </li> </ul> <p>Let's hope for a better answer by someone who understands what's going on. </p>