# Longest 'increasing' path inside a square

Say you have a function $$f: [0,1] \to [0,1]$$ such that:

1. $$f(0)=0$$
2. $$f(1)=1$$
3. Let's just say that $$f$$ is everywhere differentiable (not really necessary)
4. $$f$$ is increasing i.e order preserving

Now what I'm trying to show is that the 'length' of such a function (i.e of it's graph) is always longer than $$\sqrt{2}$$ and always shorter than $$2$$. The lower bound is pretty straightforward (shortest path is the diagonal of the unit square). Now I'm struggling with the upper bound. I'm convinced it should be trivial, but cannot for the life of me find a proof.

Would greatly appreciate any help on the matter. Cheers!

• Doesn't it have to smoothly approximate $f(x) = 0\ {\rm for}\ (0 \leq x < 1 - \epsilon), 1\ {\rm for}\ (1-\epsilon < x \leq 1)$? Use the Pythagorean Theorem or triangle inequality on portions of candidate solutions, perhaps. Jul 17, 2023 at 17:08
• @DavidG.Stork A sequence $f_n$ smoothly approximating your function would indeed satisfy $L(f_n)\to 2$. That is how I would show that 2 is the lowest upper bound. However, I fail to show that there are no functions of 'length' bigger than 2.
– M. L
Jul 17, 2023 at 17:13
• "longer than $\sqrt2$" is wrong, isn't it? These things matter! Jul 17, 2023 at 18:09
• You missed the point: its length can be exactly $\sqrt 2$, which is not "longer than $\sqrt 2$". Jul 17, 2023 at 18:55
• @DavidG.Stork The problem is symmetric with respect to exchanging x and y. It can got across and then up, or up and then across. Jul 20, 2023 at 3:38

Partition $$[0,1]$$ as $$0 = x_0 < x_1 < \cdots < x_n = 1$$. Then, by the triangle inequality: \begin{align} \sum_{k = 0}^{n-1} & \sqrt{(x_{k + 1} - x_k)^2 + (f(x_{k + 1}) - f(x_k))^2} \\&\leq \sum_{k = 0}^{n -1} (x_{k + 1} - x_k) + (f(x_{k + 1}) - f(x_k)) \\&= (x_n - x_0) + (f(x_n) - f(x_0)) \\&= (1- 0) + (1 - 0) \\&= 2 \end{align} The length of a graph is defined to be the $$\sup$$ over all sums like the first line above. We have shown that all such sums are less than or equal to $$2$$, so the $$\sup$$ must be less than or equal to $$2$$. That is, the length of the graph of $$f$$ must be less than or equal to $$2$$.

• I'll note that this doesn't prove strict inequality. I really have no idea how one would go about proving that, but it feels like it should be possible if we assume $f$ is differentiable. Jul 17, 2023 at 17:43
• Thanks! I was going back to the definition of length using the derivative of the curve and was struggling to majorize that ($L(f)=\int_0^1 \sqrt{1+|f'(x)|^2}dx)$.
– M. L
Jul 17, 2023 at 17:46
• Is my proof clear? I found it a bit hard to write up because there are so many different notations used around this topic, and I didn't want to have to introduce my own before answering the question. Jul 17, 2023 at 17:49
• Yes, it's great thank you.
– M. L
Jul 17, 2023 at 17:51
• Yes although it is perhaps worth noting that I only needed monotonicity of $f$. I didn't need differentiability or even continuity. I don't know how much you can weaken the assumptions to still get the $\sqrt{2}$ lower bound though. Jul 17, 2023 at 18:05

If we assume $$f$$ continuously differentiable, using $$\sqrt{1+\lvert f'(x)\rvert^2} \le 1+\lvert f'(x) \rvert = 1 + f'(x)\label{first}\tag1$$ we get $$L(f) = \int_0^1 \sqrt{1+\lvert f'(x)\rvert^2} \,dx \le \int_0^1 \bigl(1+f'(x)\bigr) \,dx = 2 \text.\label{second}\tag2$$ Furthermore, since on some open interval $$f'(x) > 0$$ and then $$\eqref{first}$$ is strict, $$\eqref{second}$$ is strict.

• Thanks ! I was missing the strict condition.
– M. L
Jul 17, 2023 at 18:37
• Just commenting to say that it turns out one really does need at least differentiability for the strict inequality. The Cantor function has all of the properties in the OP except differentiability (and indeed is differentiable everywhere except a set of measure $0$) and its graph has length $2$. See: en.wikipedia.org/wiki/Cantor_function Jul 18, 2023 at 3:35
• I asked another question here which confirmed that $f$ being merely differentiable is enough to ensure strict inequality. We do not need to assume that $f'$ is continuous. Jul 19, 2023 at 15:36
• @CharlesHudgins Very nice! Another related question is then: if $\gamma$ is everywhere differentiable and $\gamma' \in L^1$ is $L(\gamma) = \int_0^1 \lvert d\gamma \rvert = \int_0^1 \lvert\gamma'\rvert \,dt$? If not (and in any case probably) you should add this as an edit to your own answer! Jul 19, 2023 at 15:47

Consider any monotonic candidate function $$f(x)$$ (even one that might, in principle, have a total path length $$>2$$), and two arbitrary distinct points along it (red).

We can always find another point (green) beneath $$f(x)$$ and replace the path between the red dots with a longer path (dashed) that respects the conditions of the problem. By the triangle inequality, this new path is longer than the previous one. (Of course, the $$y$$ coordinate of the green point must be non-negative, so as to conform to the conditions of the problem.)

We can perform this path-lengthening step infinitely many times and become arbitrarily close to the path length of $$2$$.

• Thank you for your answer! I like that approach, however I think it would require proving that this construction — when iterated — actually converges towards something of pathlength 2. And I think that is non-trivial (indeed the process is extremely local and pretty hard to formalize).
– M. L
Jul 17, 2023 at 17:35
• What is meant by "the green point must be non-negatoive"? Jul 17, 2023 at 17:51
• "the green point must be non-negative" means that its $y$ coordinate value cannot be less than zero (to conform to the conditions of the problem). Jul 17, 2023 at 18:41
• +1 The answers seems to explain the intuition. Jul 18, 2023 at 3:29
• How do you know that the dashed path is longer than the curve between the red points? This is just equivalent to the original problem (which is the special case where the red points are at (0,0) and (1,1). Jul 19, 2023 at 8:53

For every available direction $$(dx,dy)$$,

$$dx \ge 0, dy \ge 0 \implies \frac{dx+dy}{\sqrt{2}} \le \sqrt{dx^2 + dy^2} \le dx+dy$$

and the integral of $$dx+dy$$ over the whole path is $$2$$.