26

Could someone provide a reference or a sketch of a proof that no differentiable space-filling curve exists? Or piecewise differentiable? Must every continuous space-filling curve be nowhere differentiable?

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 10
    The answer to your last question must be no, since we could trivially extend a space filling curve by defining it on an extra segment, on which it was very nice, or by inserting a nice smooth function on a segment in the middle, before picking up the space-filling behavior again right at the place we left off. – Joel David Hamkins Mar 29 '15 at 21:57
  • 10
    http://en.wikipedia.org/wiki/Sard%27s_theorem – Qiaochu Yuan Mar 29 '15 at 22:02
  • @QiaochuYuan: Thanks. I see that your answer to an MSE question here expands upon your citation of Sard's theorem as the underlying reason. – Joseph O'Rourke Mar 29 '15 at 22:40
  • 7
    @QiaochuYuan isn't Sard's theorem about $C^k$ maps? And the question asks for differentiable, not $C^1$... – Yemon Choi Mar 29 '15 at 22:54
  • @Yemon: oog, yeah, I guess, but in that case I've got nothing intelligent to say. – Qiaochu Yuan Mar 29 '15 at 22:59
  • Such spaces (curves) are a countable union of subspaces homeomorphic to a closed interval. Thus these spaces must be 1-dimensional (or, to use a different argument, they are small in the sense of Baire categories). – Włodzimierz Holsztyński Mar 30 '15 at 07:23
  • 1
    How research question was it? :-) – Włodzimierz Holsztyński Mar 30 '15 at 07:24
  • @YemonChoi For a map $\mathbb{R}^n\to \mathbb{R}^m$ the minimal $k$ for which Sard's theorem works is the maximum of $n-m+1$ and $1$. If $m\geq n$ (as in this case), Sard's theorem works for $C^1$-maps. – Lennart Meier Mar 30 '15 at 13:39
  • 2
    @LennartMeier Yes, I know that Sard would apply in this case for $C^1$. My point (although perhaps not one that the OP had in mind) is that $C^1$ is strictly stronger than being everywhere differentiable, and for these kinds of functions I have no good intuition whether that makes a difference to the original question – Yemon Choi Mar 30 '15 at 14:06
  • To Joseph O'Rourke: could you please clarify whether you had $C^1$ in mind during your question? – Yemon Choi Mar 30 '15 at 14:07
  • @YemonChoi: I apologize for the vagueness of my question. I was not thinking of $C^1$, No, but now I have learned quite a bit more about the intricacies of this question, and how its answer depends on precise conditions. – Joseph O'Rourke Mar 30 '15 at 17:03

5 Answers5

33

There is a theorem by Michal Morayne saying that there is a space filling function $$f:\mathbb R\to\mathbb R^2;x\mapsto(f_1(x),f_2(x))$$ such that for all $x$ at least one of $f_1'(x)$ and $f_2'(x)$ exists if and only if the continuum hypothesis holds. This is proved here: https://www.infona.pl/resource/bwmeta1.element.desklight-90a9a45c-fcc9-4b83-8ebf-cbd61a258fd9/content/partContents/8f463644-c16a-36c1-b87f-0d42dcd1b3c7 Note that the surjection $f:\mathbb R\to\mathbb R^2$ constructed by Morayne assuming CH is not continuous, though.

However, Morayne's proof also shows that no space filling curve can be differentiable in both components in every point.

Stefan Geschke
  • 16,346
  • 2
  • 53
  • 80
  • A great theorem! But only a "Peano type function", not really a curve, since neither $f_1$ nor $f_2$ is continuous. – Goldstern Mar 30 '15 at 09:57
  • 1
    The cited paper: Michal Morayne, "On differentiability of Peano type functions," Colloquium Mathematicum, Volume LIII, 1987. – Joseph O'Rourke Mar 30 '15 at 10:09
  • @Goldstern: Thank you for the comment. I edited my answer accordingly. Of course, that doesn't affect the argument that there is no differentiable surjection from $\mathbb R$ to $\mathbb R^2$. – Stefan Geschke Mar 30 '15 at 13:14
  • Apologies for asking this, but could you point out where in Morayne's arguments one can see that no space filling curve can be differentiable in both components in every point? Thanks. – Joseph O'Rourke Mar 30 '15 at 23:58
  • 2
    @Joseph O'Rourke: Unfortunately I am unable to access Morayne's article right now. But in the proof of CH from the existence of a Peano type function that is differentiable in at least one component at every point, he constructs sets $S_0$ and $S_1$ (might be called differently) and argues that these two sets satisfy Sierpinski's condition. I.e., $S_0\cup S_1=M_0\times M_1$ where the $M_i$ are of size $2^{\aleph_0}$ and the sections of $S_i$ in the direction of the $M_i$-axis are countable. If the function were differentiable, these sections would have to be uncountable. – Stefan Geschke Mar 31 '15 at 04:18
  • I managed to read the article again. The sets in question are called $S_1$, $S_2$, $M_1$, and $M_2$. – Stefan Geschke Mar 31 '15 at 04:20
24

The image of an interval under a Lipschitz map has finite $1$-dimensional Hausdorff measure.

EDIT: Here's a corrected version of Pablo Shmerkin's construction. Suppose $f: \mathbb R \to \mathbb R^d$ is differentiable.

For positive integers $m,n$ let $A_{m,n} = \{x: |y -x| \le 1/n \implies \|f(y) - f(x)\| \le m |y - x|\}$. For $k \in \mathbb Z$ let $A_{m,n,k} = A_{m,n} \cap [(k-1)/n, k/n]$. Then $\bigcup_{m,n,k} A_{m,n,k} = \mathbb R$, and $f$ is Lipschitz on $A_{m,n,k}$ with Lipschitz constant $m$.

We conclude that $f(\mathbb R)$ has $\sigma$-finite $1$-dimensional Hausdorff measure, which in particular implies that it has $2$-dimensional Lebesgue measure $0$.

Robert Israel
  • 53,594
  • 3
    However, a differentiable map (even on a compact interval) is not necessarily Lipschitz. $\hspace{1.27 in}$ –  Mar 30 '15 at 08:08
  • 1
    @Ricky - a differentiable map $f$ from $\mathbb{R}$ is not necessarily Lipschitz, but one can partition $\mathbb{R}$ into countably many sets $A_i$ such that the restriction of $f$ to $A_i$ is Lipschitz. – Pablo Shmerkin Mar 30 '15 at 20:08
  • @PabloShmerkin : $:$ How can one show that? $;;;;$ –  Mar 31 '15 at 02:17
  • @Ricky - First partition $\mathbb{R}$ into the sets on which the differential has norm $\le M$ (these are Borel sets). Let $A=A(M)$ be one of these sets. For $x\in A$, there is $\delta(x)>0$ (a Borel function) such that $|f(x)-f(y)|<2M$ when $|y-x|<\delta$. Cover $A$ by $A_n={ x\in A: \delta(x)<1/n}$. Then $f$ is (locally) Lipschitz on $A_n$. – Pablo Shmerkin Mar 31 '15 at 12:45
  • That's not quite right, but it can be fixed. I'll edit my answer. – Robert Israel Mar 31 '15 at 15:51
  • @MarkMcClure The original statement, about a Lipschitz function, is still true. A differentiable function is not necessarily Lipschitz. – Robert Israel Apr 01 '15 at 15:28
19

Robert mentions the crucial issue that a Lipschitz map cannot increase Hausdorff dimension.

In the other direction we might ask, how well behaved can a space-filling curve be? Lebesgue's space filling-curve is smooth on the compliment of Cantor's middle third set. Thus, a space-filling curve can be differentiable almost everywhere. The idea is simple. If $x$ in the Cantor set has base three expansion $$0.(2d_1)(2d_2)(2d_3)\cdots,$$ where each digit $d_i$ is zero or one, then define $f$ in terms of its binary expansion by $$f(x) = (0.d_1d_3d_5\ldots,0.d_2d_4d_6\ldots).$$ Then, $f$ maps the Cantor set onto the unit square continuously and easily extends to the interval by connecting the dots.

Hans Sagan's Space-filling curves is, perhaps, the definitive reference on the topic and Lebesgue's curve is covered in chapter 5 of that text.

Mark McClure
  • 1,898
  • "a space-filling curve can be differentiable almost everywhere": Interesting! – Joseph O'Rourke Mar 30 '15 at 11:30
  • 4
    Alternatively, if $f : [0,1] \to [0,1]^2$ is a space-filling curve and $\phi : [0,1] \to [0,1]$ is the Cantor staircase function, then $f \circ \phi$ is a space-filling curve whose derivative exists and vanishes almost everywhere. But this raises an interesting question: is there an easy way to show that a space-filling curve cannot be absolutely continuous? – Nate Eldredge Mar 30 '15 at 15:21
  • 3
    Oh, yes there is: an absolutely continuous curve is rectifiable (its length is given by $\int_0^1 |f'(t)|,dt$). – Nate Eldredge Mar 30 '15 at 21:59
  • Of course a Cantor set can be continuously mapped on any cube of any finite or countable dimension. Then you can extend such a map to a continuous map about any way you want it. There is really nothing interesting at all that the extended part can be differantiable. – Włodzimierz Holsztyński Apr 02 '15 at 06:23
  • Must a space-filling curve be non-differentiable uncountably often? – Toby Bartels Jan 25 '19 at 21:23
5

This is answered for $C^1$ curves here, and then the $C^1$ condition is weakened here.

Community
  • 1
Igor Rivin
  • 95,560
2

Using the Sard's theorem.

Assume that your curves exists. Then Each point in the domain is a critical point and so each point in the image is a critical value.

But this is a contradiction with the sard's theorem since the set of critical values has measure zero.

Cepu
  • 1,424