Timeline for Is the Hilbert space-filling curve bijective over computable numbers?
Current License: CC BY-SA 4.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 26, 2019 at 17:39 | vote | accept | Mehmet Ozan Kabak | ||
| Dec 26, 2019 at 17:39 | comment | added | Mehmet Ozan Kabak | @Arno: OK, I think I understand the root issue now. There is no way to "fix" forward and reverse maps simultaneously while preserving the space-filling property, regardless whether we operate in $I$ or $\mathbb{CN}$. | |
| Dec 26, 2019 at 16:29 | comment | added | Arno | @MehmetOzanKabak We would end up with a bijection between the computable points, but the map is no longer computable, and it is no longer a space-filling curve. | |
| Dec 26, 2019 at 16:22 | comment | added | Mehmet Ozan Kabak | @Arno: I don't mean to be stubborn. I'm trying to understand the root issue as best as I can, but I fail. If we slightly modify the definition of the space-filling function to use finite binary expansions for dyadic rational values, why wouldn't we end up with a one-to-one map? | |
| Dec 26, 2019 at 16:09 | comment | added | Arno | Related: mathoverflow.net/q/303278/15002 | |
| Dec 26, 2019 at 16:07 | comment | added | Arno | @MehmetOzanKabak Yes, the issue "just" comes from dyadic rationals. No, we can't resolve this by any kind of agreement - because we cannot compute any specific binary expansion (or Gray code) from a real number. (Technically we even ought to be using signed digit expansions rather than binary...) | |
| Dec 26, 2019 at 15:06 | comment | added | Mehmet Ozan Kabak | @GeraldEdgar: OK, the inverse image of $(1/2, 1/2)$ indeed converges to $1/6$ if we use the infinite expansion $0.01111\cdots$. But isn't this a special issue that only manifests for dyadic rationals? If we agree to use finite expansions for dyadic rationals (which is a subset of computable numbers), don't we end up with a one-to-one map? | |
| Dec 26, 2019 at 14:41 | comment | added | Gerald Edgar | Where am I going wrong? The number $1/2$ has more than one binary expansion. Not only $0.10000\cdots$ but also $0.01111\cdots$. | |
| Dec 26, 2019 at 14:31 | comment | added | Pietro Majer | Note that if we agree to represent a point of $I^3$ (or in general $I^n$) with a unique expansion, i.e. just merging the digits of the three coordinates: $x_1,y_1,z_1,x_2,y_2,z_2,x_3,\dots$ , then the Peano curve $I\to I^3$ comes from an extremely simple involutory bijection on the ternary strings $\{0,1,2\}^\mathbb{N} \to \{0,1,2\}^\mathbb{N}$; thus at least on the representing digits your conjecture it is true. Of course, passing to the quotient, one gets a non-injective curve $I\to I^3$. Points with multiple fiber are easily characterized. | |
| Dec 26, 2019 at 14:19 | comment | added | Mehmet Ozan Kabak | @GeraldEdgar: If we list finite binary approximations of $(1/2, 1/2)$ as a sequence of tuples, we get: $((0.1, 0.1), (0.10, 0.10), (0.100, 0.100), ...)$. Feeding this to the reverse algorithm, we generate the binary digits $(0.1, 0.10, 0.100, ...)$. It is actually easy to see that all further zeroes in the input sequence result in zeroes in the output sequence. Therefore, I deduce that $(1/2, 1/2)$ maps (uniquely) to $1/2$. Where am I going wrong? | |
| Dec 26, 2019 at 14:13 | comment | added | Mehmet Ozan Kabak | @PietroMajer: I mean the n-dimensional generalization that uses Gray codes. I added this to the question body. | |
| Dec 26, 2019 at 14:11 | history | edited | Mehmet Ozan Kabak | CC BY-SA 4.0 |
Incorporate Pietro Majer's comments to clarify the question
|
| Dec 26, 2019 at 12:50 | comment | added | Pietro Majer | The Hilbert curve is the very specific square filling curve $I\mapsto I^2$ defined via a dyadic subdivision, but what should be the definition of a "Hilbert curve" in $I^n$ , i.e a filling cube curve in dimension $n\ge3$? Hilbert does not make any mention to such a generalization, btw. There are of course many constructions of $n$-cube filling curves (already described in the Peano's paper) but it is not clear if you refer to a precise natural generalization of Hilbert construction. | |
| Dec 26, 2019 at 12:31 | comment | added | Gerald Edgar | For example, in this Hilbert curve: en.wikipedia.org/wiki/Hilbert_curve the midpoint $(1/2,1/2)$is the image of three different points, all computable. | |
| Dec 26, 2019 at 11:51 | history | edited | Mehmet Ozan Kabak | CC BY-SA 4.0 |
Further clarifications and references
|
| Dec 26, 2019 at 11:21 | history | edited | Mehmet Ozan Kabak | CC BY-SA 4.0 |
Mentioned both the forward and the reverse algorithms
|
| Dec 26, 2019 at 7:36 | history | edited | Mehmet Ozan Kabak | CC BY-SA 4.0 |
Fixed a typo that mixed domain/range of the Hilbert curve, restricted domain/range to unit interval
|
| Dec 25, 2019 at 22:54 | answer | added | Arno | timeline score: 6 | |
| Dec 25, 2019 at 21:09 | comment | added | Mehmet Ozan Kabak | How can we construct a non-injective example? It seems to me that the standard algorithm based on Gray codes produces unique output bits for each input bit sequence. What am I missing? | |
| Dec 25, 2019 at 20:56 | comment | added | Noah Schweber | I believe the standard curve is not injective on computable points - intuitively, we can find many non-injectivities pretty easily, and this suggests that those non-injectivities are computable. | |
| Dec 25, 2019 at 20:55 | history | edited | Mehmet Ozan Kabak | CC BY-SA 4.0 |
Added reference to the specific curve/construction algorithm I have in mind.
|
| Dec 25, 2019 at 20:52 | comment | added | Mehmet Ozan Kabak | @NoahSchweber; You are right, being specific matters here. Even though I was talking about the specific curve whose construction was as given in the Wikipedia link, this was not clear. I will add a reference to a specific construction to clarify the question. | |
| Dec 25, 2019 at 20:40 | comment | added | Noah Schweber | Injectivity depends on the curve of course - maybe the original curve maps two computable points to the same element. I think the "right" question here is whether some Hilbert curve which is computable is injective on the computable points. | |
| Dec 25, 2019 at 20:28 | history | edited | Mehmet Ozan Kabak |
Added the computability-theory tag
|
|
| Dec 25, 2019 at 19:57 | history | asked | Mehmet Ozan Kabak | CC BY-SA 4.0 |