Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane

2011-03-17T03:20:21Z

In the middle of page 9 of http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf.

They said " Now we select a random subset....choosing lines independently with probability $\frac{Q}{100}$. With positive probability....

I can not see why there is positive probability...

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

Answer by Thomas Kalinowski for Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane

2011-03-17T12:21:08Z

Not a complete answer but a quick explanation of how I read page 9 in that paper.

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

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

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:

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

Let's hope for a better answer by someone who understands what's going on.

Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane - MathOverflow

Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane

Answer by Thomas Kalinowski for Degree reduction argument in Guth-Katz'sproof of Erdos distinct distance problem in the plane