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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

1 Answer

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

1. 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|}.$$
2. 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.$$
3. 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.

-

Thanks Kali, I think you are right.  then one can take large N to ensure the 3 by Large number law. I agree that one should work on a smaller set.  – rrrq Mar 17 2011 at 15:11
Hmm. I'm not really convinced by my own answer. I have to think about it some more. – Thomas Kalinowski Mar 17 2011 at 21:45
in fact one can do estimate directly to see the probability is positive – rrrq Mar 18 2011 at 1:39
one can do this as following Claim: suppose both $L_{1}$ and $L_{2}$ has $O(N^{2})$ lines, each line in $L_{1}$ intersects with at least almost $QN$ lines in $L_{2}$, now choosing line in $L_{2}$ independently with probability $\frac{1}{Q}$, the resulting subset of $L_{2}$ is denoted by $L_{3}$ then one has similar statement in 2: with probability bigger than 1/2  $L_{3}$ contains $\frac{O(N^{2})}{Q}$ lines for 3, the probability that a line in $L_{1}$ intersects more than $\frac{N}{2}$ lines in $L_{3}$ is bigger than $1-e^{-N/100}$    – rrrq Mar 18 2011 at 3:21
this can be done by using estimate in en.wikipedia.org/wiki/Binomial_distribution.  then the probability that every line in $L_{2}$ intersects with at least $\frac{N}{2}$ lines in $L_{3}$ is bigger than $(1-e^{-N/100})^{N^{2}}$, which goes to 1 when $N$ very large. – rrrq Mar 18 2011 at 3:25
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 57, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9595860838890076, "perplexity_flag": "head"}