# Dense path in square, constructed from grid

Working on this stack overflow question led me to ask another, related question (here) .

This first attempt was shown unsuccessful in the answer to it, so I try a rather different approach here. Let $D=\bigg\lbrace \frac{i}{2^j}\bigg | j \geq 1, 0 < i < 2^j \bigg\rbrace$ be the set of all dyadic numbers in $]0,1[$.

Let us say that a (finite or infinite) sequence $u=(u_n)$ of elements in $D^2$ is rectangular if all the vectors $\overrightarrow{u_{k}u_{k+1}}$ are horizontal or vertical.
When $u$ is finite of length $n$, we have a polygonal path $p_u: [0,1] \to ]0,1[^2$ such that $p_u$ induces a bijection between $[\frac{k-1}{n},\frac{k}{n}]$ and the segment $[u_ku_{k+1}]$, for each $k$. When $u$ is infinite, $u=(u_k)_{k \geq 1}$, we have an “infinite” polygonal path $p_u$ such that $p_u$ induces a bijection between $[k,k+1]$ and the segment $[u_ku_{k+1}]$, for each $k \geq 1$.

It is easily seen for any $\varepsilon >0$, any finite rectangular sequence $u$ such that $p_u$ is injective (let us call these good finite sequences for short) can be extended to form a larger good finite sequence that’s $\varepsilon$-dense (formally, this means that if $(u_1,u_2,u_3, \ldots ,u_p)$ is a good finite sequence, then there is a $q>p$ and values $u_{p+1},u_{p+2}, \ldots ,u_q$ in $D^2$ such that the sequence $(u_1,u_2,u_3, \ldots ,u_q)$ is again a good finite sequence, and for any $x\in [0,1]^2$ there is an index $i$ between $1$ and $q$ such that $||x-u_i|| \lt \varepsilon$ ). We deduce that there exist countably infinite, rectangular sequences $u$ that are dense in $[0,1]^2$ and such that $p_u$ is injective (let us call these good infinite sequences).

Let $(u_k)_{k\geq 1}$ be a good infinite sequence. Let $P$ be the path followed by the sequence, i.e. the union of all the segments $[u_ku_{k+1}]$ for $k\geq 1$. Is $Z=]0,1[^2 \setminus P$ path connected ? A related question : is it true that for any $z\in Z$, there is an open segment containing $z$ and contained in $Z$ ?

-
I don't really understand the part where you say that any finite rectangular sequence whose path is injective can be extended to form a larger sequence. What exactly do you mean by "extended"? Also, in the next sentence, what is the "associated polygonal path" for an infinite sequence? – Dan Shved Dec 4 '12 at 12:27
@DanShved : I edited the post, hope it is clearer now. – Ewan Delanoy Dec 4 '12 at 15:20

$Z$ may not be path-connected, and the number of its path-connected components may even be uncountable.

Instead of working with dyadics, I find it easier to use triadic numbers to work out an explicit example (and it makes no real difference : just use any order preserving bijection between the two to recover your original context) Let $T_n = \{(a/3^n, b/3^n), 0 < a,b < 3^n \}$.

First, pick $u_0, \ldots u_3$ in $T_1$ so that they make a U shape. Then, pick $u_4, \ldots u_{16}$ in $T_2$ by extending the line $u_2 u_3$ by $1/9$, then go back inside the U and "follow the walls" until you've passed on every point in $T_2$ and are back at a corner of $T_2$. Then pick $u_{17} \ldots u_{53}$ in $T_3$ using the same procedure, etc.

You will notice that there are big areas of the square where you are always moving along the same axis : the intersection of $P$ with those areas consist of a bunch of horizontal (or vertical) lines. Thus the path-connected components of $Z$ in those areas must also be made of horizontal (or vertical lines).

There is a half $H$ of the square where every path-connected component of $Z \cap H$ or $P \cap H$ have the same U shape. You can parametrize those components by a real number in $(0;1/2]$. As you look progressively into the other (more complicated) half of the square, what happens is that you're extending those components, twisting them, and connecting some of them. Those connections are of the form "if $x$ is in some interval $I_n$, connect component $x$ with component $r_n \pm x$" where $r_n$ is a rational (triadic) number and $I_n$ an interval with rational (halves of triadic numbers, I think) endpoints.

Then the path-connected components of $Z$, together with $P$, correspond to the quotient of $(0;1/2]$ modulo those connections. $P$ corresponds to the class of $1/3$ and has an endpoint ($u_0$). The path-connected component corresponding to the class of $1/2$ will have countably many endpoints and nodes. And all the other path-connected components will have no endpoint and no node (they can't form a loop since that would disconnect the square, so there is a continuous bijection from $\Bbb R$ into them). Since each equivalence class is countably infinite and $(0;1/2]$ is uncountable, the number of equivalence classes (and thus of path-connected components) has the same cardinality as $(0;1/2]$. Also, every one of them is dense in the square, and so choosing to remove any one of them instead of $P$ will give you the same partition of the square into path-connected subsets.

Assuming you start at $u_0 = (1/3,2/3)$ and go down to form the first U shape, we get $u_3 = (2/3,2/3), u_4 = (2/3,7/9), u_5 = (5/9,7/9), \ldots u_{16} = (8/9,8/9), u_{17} = (8/9,25/27), \ldots u_{53} = (26/27,26/27) \ldots$

Note $\overline{x}$ the component of the point $(x,1/2)$, looking at the bottom half of the square you have the equivalence $\overline{x} \sim_0 \overline{1-x}$. This makes an endpoint at $(1/2,1/2)$.

The other reflections take place on the upper half and they have pairwise disjoint support, so from almost any point at $(x,1/2)$ you can travel through the top half to get to a unique $(y,1/2)$ or travel through the bottom half to get to $(1-x,1/2)$.

Next you have $\overline x \sim_1 \overline{2/3 - x}$ for $x \in [1/6 ; 1/2]$, making the endpoint at $u_0$; and $\overline x \sim_2 \overline{11/9 - x}$ for $x \in [1/2 ; 13/18]$, making an endpoint at $(11/18,13/18)$ and a T node at $(1/2,5/6)$.

Since $11/18 \sim_0 7/18 \sim_1 5/18 \sim_0 13/18 \sim_2 1/2$, these are all on the same component (1/2's) (and this chain of equivalences describe an actual path from $(11/18,13/18)$ to the T node which is directly tied to the other endpoint $(1/2,1/2)$).

On the next step, you have $\overline x \sim_3 \overline{8/9 - x}$ for $x \in [1/18 ; 1/6] \cup [13/18 ; 5/6]$ and $\overline x \sim_4 \overline{47/27 - x}$ for $x \in [5/6 ; 49/54]$, making an endpoint at $x=47/54$ and a T node at $x=5/6$.

And so on : $\overline x \sim_{2n+1} \overline{1-3^{-n-1} - x}$ for $x \in [\frac 1 2 3^{-n-1} ; \frac 1 2 3^{-n}] \cup [1- \frac 5 2 3^{-n-1} ; 1- \frac 1 2 3^{-n}]$ and $\overline x \sim_{2n+2} \overline{2-7.3^{-n-2} - x}$ for $x \in [1- \frac 1 2 3^{-n}; 1- \frac 5 2 3^{-n-2}]$, making an endpoint at $x = 1- \frac 7 2 3^{-n-2}$ and a T node at $x = 1- \frac 1 2 3^{-n}$.

So hopefully, this will help to draw the picture.

I would like to say that $\overline{x} = \overline{y}$ if and only if $x-y$ or $x+y$ is a triadic number, but that would require more analysis on what those reflections do in terms of the base 3 expansion of $x$.

-
So my answer looks like a version of this answer : math.stackexchange.com/a/234999/17445 – mercio Dec 4 '12 at 16:41
That’s a good synthesis of a lot of things that would be awkward to write out formally. I certainly need to check and work out the details before accepting this as an answer. – Ewan Delanoy Dec 4 '12 at 20:33
Why does the equivalence class of $\frac{1}{2}$ have countably many endpoints and nodes ? All I see is that it has an endpoint at $(\frac{1}{2},\frac{4}{3})$, the middle of $[u_8u_9]$. – Ewan Delanoy Dec 5 '12 at 6:08