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

-

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.

-
The blog post is philosophically helpful as well. – Dylan Moreland Feb 2 '12 at 15:52
Clearly the Axiom of (countable) Choice has been used to define the set in question. I wonder if a constructive approach might be possible here; maybe by defining the sequence of balls $D_n$ explicitely, and the points recursively with some formula which guarantees that no point will lie on a straight line defined by any two preceding ones. – Emilio Ferrucci Feb 2 '12 at 16:44
@Emilio: The sequence of balls is easy to construct explicitly; the part that seems tricky without AC is choosing a point in $D_n \setminus \bigcup_{i<j<n}L_{ij}$ for every $n$. I think I know a way to do that without AC too, but it's a bit too long for a comment... – Ilmari Karonen Feb 2 '12 at 22:26
@IlmariKaronen Yes, I think I have a way too: to define $x_n$ you first choose an angle, the choice of which is based on the $L_{ij}s, \ i, j < n$, then a point on the straight line though the center of $D_n$ forming such angle with the $x$ axis, based on preceding points. A general formula for the coordinates of $x_n$ would be extremely complicated, but a recursive algorithm is strong enough to prove that $AC$ is not necessary here. – Emilio Ferrucci Feb 3 '12 at 0:08

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

-
Yes, this works nicely, great answer! – Emilio Ferrucci Feb 3 '12 at 0:18
@Ilmari Karonen: Very nice constructivization of the Gowers solution! – André Nicolas Feb 3 '12 at 0:20
While I did not yet read the post in great details and attention, I should remark that the axiom of choice can sneak up without noticing (e.g. Henri Lebesgue and Emile Borel and their constant use of Dependent Choice). The fact that you define something by induction and that you can assure the induction step can be carried does not guarantee that you can find an infinite "path" of steps. That been said, I have to go now but when I return I will sit through this carefully and comment again. – Asaf Karagila Feb 4 '12 at 12:00
@Asaf: I know this is a very old post, but since you said you'd get back to it... Anyway, I went over it again, and I'm fairly sure there's no DC (or even ACω) used here: all the choices that need to be made are from sets of the form $[a, b) \setminus \{x_1, x_2, \dotsc, x_n\}$, and the lemma above singles out a specific element $x = (x_1 + x_2)/2$ for each such set. – Ilmari Karonen Aug 29 '14 at 0:38
Err... Yeah, I I had to fold a lot of laundry! And cook dinner, make that dinners. ;-) Yeah that seems about right, what you wrote in your comment. – Asaf Karagila Aug 29 '14 at 0:45