Is a dense subset of the plane always dense in some line segment?

Consider the following question:

Given a dense set in the plane, does there always exist a line segment in which this set is dense?

I have been puzzling over this for some time. Can someone help or give me some hints?

Solution 1:

I will interpret your question as asking whether for any set $S$ which is dense in the plane, there is a line segment $PQ$ such that the intersection of $S$ with the interval $PQ$ is dense in $PQ$.

The answer is no. There is in fact a set $S$ which is dense in the plane and contains no three collinear points. Thus for any line segment $PQ$, the intersection of $S$ with $PQ$ has at most two points. Very non-dense!

There is a very nice blog entry by Gowers that discusses this result, and provides a simple proof. One cannot expect to improve on Gowers.

Solution 2:

In the comments to André Nicolas' answer, Emilio asked if there was a way to carry out the Gowers construction without using the Axiom of Choice. I'll try to outline how to do that here:

First, let me summarize the construction by Gowers: to find a dense subset $A$ of $\mathbb R^2$ which contains no three collinear points, we can take an enumeration $(q_1, q_2, \dotsc)$ of $\mathbb Q^2$, let $D_n$ be a ball of radius $1/n$ around $q_n$ for all $n \in \mathbb N$, and for each $n \in \mathbb N$, choose $a_n \in D^*_n = D_n \setminus \bigcup_{1\le i < j < n} L_{ij}$, where $L_{ij}$ is the set of points collinear with $a_i$ and $a_j$, and let $A = \{a_1, a_2, \dotsc\}$. Since every $L_{ij}$ is a line and $D_n$ is a ball, it's easy to see that $D^*_n$ must be non-empty, so by AC we can choose a point $a_n$ from each of them. The challenge is to do this constructively, without using AC in any form.

Now, enumerating $\mathbb Q^2$ is not hard to do explicitly, just a bit tedious, and once we have the enumeration, we get the balls $D_n$ directly. (For example, since it doesn't really matter here if we double-count some points in $\mathbb Q^2$, we can define $f: \mathbb N \to \mathbb N^4$ as the inverse of the generalized Cantor pairing function $\pi^{(4)}$, $g: \mathbb N \to \mathbb Z$ as $g(n) = (-1)^n \lfloor \frac n2 \rfloor$, and let $q_n = (g(a_n)/b_n, g(c_n)/d_n)$ where $(a_n,b_n,c_n,d_n) = f(n)$. It's not hard to show that $n \mapsto q_n$ is a surjection from $\mathbb N$ to $\mathbb Q^2$.)

The tricky part is giving an explicit formula for $a_n$, given $D_n$ and $a_i$ for $1 \le i < n$. I'll follow Gowers' example by first choosing a line $L$ passing through $q_n$ which is not parallel to any $L_{ij}$ (for $1 \le i < j < n$), and then choosing $a_n \in D_n \cap L$ so that $a_n$ does not lie in the intersection of $L$ with any $L_{ij}$. For both of these steps, the following lemma turns out to be useful:

Lemma: Let $X = \{x_1, \dotsc, x_n\} \subset [a,b)$, $a > b$, $n \ge 1$, and let the points $x_1, \dotsc, x_n$ be distinct and sorted in ascending order, so that $x_i < x_j \iff 1 \le i < j \le n$. Define $x_{n+1} := b$. Then $x := \frac{x_1 + x_2}2 \in [a,b) \setminus X$. (If $n=0$, then $X$ is empty and e.g. $x := \frac{a+b}2 \in [a,b) \setminus X$.)

Now, we first need a line $L$ which is not parallel to any $L_{ij}$. Let $\alpha_{ij} \in [0, \pi)$ be the angle of the line $L_{ij}$ with respect to some arbitrary reference line (say, the $x$-axis). Using the lemma above, we can explicitly choose an angle $\alpha \in [0, \pi) \setminus \{\alpha_{ij}: 1 \le i < j <n\}$. Let $L$ be the unique line that passes through the point $q_n$ at the angle $\alpha$.

Now, let $d_{ij}$ be the distance from $q_n$ to the intersection of $L_{ij}$ and $L$, and let $X = \{d_{ij}: 1 \le i < j < n\} \cap [0,1/n)$. Using the above lemma again, we can select an $x \in [0, 1/n) \setminus X$. Let $a_n$ be one of the two points in $L$ at distance $x$ from $q_n$. (To choose from the two points, we can e.g. take the one with the lower $x$-coordinate, or with the lower $y$-coordinate if the $x$-coordinates are equal.)

(A minor detail I left out from the construction above is that we also need to ensure that all $a_n$ are distinct, since if $a_i = a_j$ for any $i < j$, then $L_{ij} = \mathbb R^2$ and we have no way to choose $a_{j+1}$. Luckily, it turns out that it's enough to make sure that $a_1 \ne a_2$, since thereafter the construction ensures that no subsequent points can coincide, as two coincident points would be collinear with any third point. Thus we can, for example, pick $a_1 = (0,0)$ and $a_2 = (0,1)$ and proceed with the construction described above from there on.)