Traveling across a square

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
timonan
Posts: 84
Joined: Fri Mar 28, 2008 5:46 pm UTC

Traveling across a square

Postby timonan » Sun Feb 22, 2009 6:20 pm UTC

This might be an easy question for all of you, but I can't figure out what I'm missing.

Picture a square with side length one. For our purposes, let's call a side length one mile because someone will be walking across it. Now, if a person walks the perimeter from one corner to the opposite corner, they've traveled 2 miles. If they walk across the diagonal, they've walked the square root of 2 miles. Simple enough.

Now, let's say the inside of the square is marked out like a chessboard. If a person walks from one corner to the other, but instead of going straight across the diagonal, they trace around the squares that the diagonal runs through (either all black squares or all white squares). So they keep turning at right angles as they work their way across the square, being very close to the diagonal, but never actually walking on it. Now, I know that as long as they turn at right angles, they never cut out any distance, and the distance traveled will still be two miles. (That seems to be a common fallacy, that cutting across a shape making right-angle turns somehow saves distance.)

Where I get stuck is by imagining more turns being made at smaller intervals. Say the square had 256 squares instead of 64 and the individual again walks around the squares cutting through the diagonal. The line is still a bit jagged, but is approximating the diagonal a bit more. Divide the square up into a million squares and now the path traced across the square (though all right angle turns) looks almost exactly like the diagonal.

My question is: If you divide the square up into smaller and smaller squares (approaching an infinite number of squares), it seems like the path traveled will begin to map onto the diagonal and make the distance traveled root 2 miles. But if all the turns made are right angles, no matter how many are made( even infinite?), then the distance traveled will always be 2 miles. These two ways of looking at it don't reconcile, so I'm obviously missing something. What is it?

By the way, I'm leaving on a trip for a few days, so I may not be able to respond for a little while. I hope my description makes sense.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Traveling across a square

Postby Buttons » Sun Feb 22, 2009 6:34 pm UTC

This is covered pretty well here.

ThomasS
Posts: 585
Joined: Wed Dec 12, 2007 7:46 pm UTC

Re: Traveling across a square

Postby ThomasS » Sun Feb 22, 2009 6:51 pm UTC

Being a short distance from the diagonal is a different condition than approximating its length. In fact, to be assured that you approximate the length of a curve the normal vectors of your line segments must approach the normal vectors of the curve. There is a standard limit/geometry problem which demonstrates that the same thing happens to 2-d surfaces in 3-d. It also demonstrates a problem with taking a limit of two variables.

Take a right circular cylinder. You can tessellate the curved portion with [imath]n[/imath] rows of [imath]m[/imath] triangles. However you take both [imath]n[/imath] and [imath]m[/imath] to infinity, the tessellation gets closer to the surface in terms of distance. However, depending on how you take [imath]m[/imath] and [imath]n[/imath] to infinity, the limit of the area can be anything between the actual area of the curved portion and [imath]+\infty[/imath] (inclusive).

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Traveling across a square

Postby t0rajir0u » Mon Feb 23, 2009 12:59 am UTC

The issue depends on how you define the "limit" of a sequence of curves as opposed to a sequence of numbers. In an appropriate sense, the limit is a fractal, and then the reason its length doesn't behave the way you would expect it to is that it is not, in a precise sense, either 1-dimensional or 2-dimensional.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Traveling across a square

Postby skeptical scientist » Mon Feb 23, 2009 1:28 am UTC

Torajirou, how are you defining limit for the curve to converge to something other than the diagonal of the square?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: Traveling across a square

Postby keeperofdakeys » Mon Feb 23, 2009 1:39 am UTC

let's think in algebra
if there are n amount of squares then the side of the squares is [imath]1 / \sqrt{n}[/imath]
then thanks to pythagoras we know that the diagonal of the squares is [imath]\sqrt{(1 / \sqrt{n})^2+(1 / \sqrt{n})^2}[/imath], or [imath]\sqrt{2/n}[/imath]

now the amount of squares on the diagonal will be equal to [imath]\sqrt{n}[/imath]
then times it by the diagonal length of the squares [imath]\sqrt{2/n} * \sqrt{n} = \sqrt{2n} / \sqrt{n}[/imath], or [imath]\sqrt{2}[/imath]

anyway if you go using right angles then you would be going [imath]\sqrt{n} * 1 / \sqrt{n} = 1[/imath] in both x and y directions
Last edited by keeperofdakeys on Mon Feb 23, 2009 6:02 am UTC, edited 1 time in total.

User avatar
J Spade
Luppoewagan
Posts: 523
Joined: Wed Apr 18, 2007 7:56 pm UTC
Location: Up a creek without a paddle
Contact:

Re: Traveling across a square

Postby J Spade » Mon Feb 23, 2009 2:14 am UTC

I look at the problem this way:

If you are never technically moving in a strictly diagonal direction, then your x distance is still in intervals of dx and the y distance in intervals of dy. The sum of all the dx intervals is still 1 mile, and the same for the dy intervals.

It's kind of like a fractal then?

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Traveling across a square

Postby antonfire » Mon Feb 23, 2009 2:19 am UTC

It's simple. "Length" is not a continuous function on curves. You might as well be surprised that the floor of 1-e is 0 for small e>0, but the floor of 1 is 1.

Not all useful functions are continuous. This is especially true when you start taking limits of "big" things like curves.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

Yesila
Posts: 221
Joined: Sun Dec 16, 2007 11:38 am UTC

Re: Traveling across a square

Postby Yesila » Mon Feb 23, 2009 2:49 am UTC

antonfire wrote:It's simple. "Length" is not a continuous function on curves. You might as well be surprised that the floor of 1-e is 0 for small e>0, but the floor of 1 is 1.

Not all useful functions are continuous. This is especially true when you start taking limits of "big" things like curves.



Unl[imath]\varepsilon[/imath]ss you'r[imath]\varepsilon[/imath] using a non-standard d[imath]\varepsilon[/imath]finition of 1, e, "-', or floor, [imath]\lfloor 1-e \rfloor = -2 \neq 0[/imath]....

***edited all things that should be 'e' into [imath]\varepsilon[/imath], and left all things that should be [imath]\varepsilon[/imath] as 'e', just because I can.
Last edited by Yesila on Mon Feb 23, 2009 3:58 pm UTC, edited 1 time in total.

User avatar
Mathmagic
It's not as cool as that Criss Angel stuff.
Posts: 2926
Joined: Thu Nov 30, 2006 12:48 am UTC
Location: In ur fora posting in teh threads

Re: Traveling across a square

Postby Mathmagic » Mon Feb 23, 2009 2:50 am UTC

I think by 'e', he means [imath]\epsilon[/imath].
Axman: That, and have you played DX 10 games? It's like having your corneas swabbed with clits made out of morphine.
Pathway: cocks cocks cocks

User avatar
Cycle
Posts: 146
Joined: Mon Feb 25, 2008 1:55 am UTC

Re: Traveling across a square

Postby Cycle » Mon Feb 23, 2009 2:53 am UTC

More important is to actually consider the topology of the space of paths. It seems obvious that lim (sawtooth curves) = diagonal, but what do you actually mean by limit? Most people intuitively use the C0 topology (that is, with the sup norm). But length isn't even defined on C0, as many curves have infinite length. Furthermore, even where it is defined, length is not continuous.

But you're using the wrong topology. If you use the C1 topology, you get all the right answers. Of course, since length is usually defined to be [imath]\int_a^b |f'(x)| dx[/imath], it's natural to consider length as a function on C1 (or piecewise C1), and also to use the C1 topology. Here, length is a continuous function.

However, lim (finer sawtooth functions) doesn't exist here. You might think it's limit is the diagonal, but since the derivative of the diagonal is constantly in the diagonal direction, and the derivative of the sawtooth is constantly either vertical or horizontal, the diagonal is not the C1 limit.

The whole question, "What is the right topology to put on my infinite dimensional space of functions?" is functional analysis. Limits of functions have non-trivial technicalities, depending on what structure you're trying to preserve.

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Traveling across a square

Postby phlip » Mon Feb 23, 2009 3:31 am UTC

I must admit ignorance when it comes to topology... so Cycle's post went a fair bit over my head. When I think of the limit of the staircases, I think:

Let [imath]f_n : [0,1] \to [0,1]^2[/imath] (for natural n > 0) be the staircase path from (0,0) to (1,1) with n "steps". For example:[math]f_1(x) = \begin{cases} (0,2x) & x < 0.5 \\ (2x - 1,1) & x \ge 0.5 \end{cases}[/math][math]f_2(x) = \begin{cases} (0,2x) & x < 0.25 \\ (2x - 0.5,0.5) & 0.25 \le x < 0.5 \\ (0.5,2x - 0.5) & 0.5 \le x < 0.75 \\ (2x - 1,1) & x \ge 0.75 \end{cases}[/math]And so on.

Then we can call the "limit" of these curves [imath]f_\infty(x) = \lim_{n \to \infty} f_n(x)[/imath]... for instance, [imath]f_\infty(1/3)[/imath] would be the limit of f1(1/3), f2(1/3), etc, etc... Now, with some pokery, I'm pretty sure it'd be possible to prove that [imath]f_\infty(x) = (x,x)[/imath]... (possible proof outline: I think that each coordinate of fn(x) will be within 1/n of x... since it'll be in the step of the staircase that steps over (x,x), and the size of that step is 1/n... I could make this more rigorous if I wasn't lazy, but it's kinda a side point).

So by this, [imath]f_\infty(x)[/imath] is the basic diagonal... just what intuition asks for.

Then we have:[math]arclen(\lim_{n \to \infty} f_n(x)) = arclen(f_\infty(x)) = \sqrt 2 \text{ (since it's a simple diagonal)}[/math][math]\lim_{n \to \infty} arclen(f_n(x)) = 2 \text{ (since it's 2 for any finite n)}[/math]So arclen simply isn't continuous.

Cycle: is this definition of the limit of a sequence of functions equivalent to one of the definitions you mention? Or is it something completely different and wrong?
Last edited by phlip on Mon Feb 23, 2009 9:07 pm UTC, edited 1 time in total.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Lothar
Posts: 63
Joined: Sat Dec 23, 2006 11:37 am UTC
Location: Berlin, Germany
Contact:

Re: Traveling across a square

Postby Lothar » Mon Feb 23, 2009 4:15 am UTC

phlip wrote:is this definition of the limit of a sequence of functions equivalent to one of the definitions you mention? Or is it something completely different and wrong?


It's different, but not necessarily "wrong." There are many ways of defining the limit of a sequence of functions. Your definition is known as pointwise convergence: [imath]f_n \to f[/imath] pointwise if and only if [imath]f_n(x) \to f(x)[/imath] for all [imath]x[/imath].

But pointwise convergence is not always good enough. For example, the pointwise limit of continuous functions may not be continuous. A stronger notion of the limit for functions is uniform convergence: [imath]f_n \to f[/imath] uniformly if and only if [imath]\sup_x|f_n(x) - f(x)| \to 0[/imath] which means that the functions must eventually be close to the limit function everywhere in the domain (at the same time). Uniform convergence preserves continuity.

But it does not preserve arc length, as we've seen. For this, we'll need an even stronger notion of limit, so we'll restrict ourselves to differentiable curves (or piecewise differentiable curves) and require that not only the functions converge uniformly, but that their derivatives do as well. This is C1 convergence.
Always program as if the person who will be maintaining your program is a violent psychopath that knows where you live.

If you're not part of the solution, you're part of the precipitate.

1+1=3 for large values of 1.

ThomasS
Posts: 585
Joined: Wed Dec 12, 2007 7:46 pm UTC

Re: Traveling across a square

Postby ThomasS » Mon Feb 23, 2009 4:30 am UTC

t0rajir0u wrote:The issue depends on how you define the "limit" of a sequence of curves as opposed to a sequence of numbers. In an appropriate sense, the limit is a fractal, and then the reason its length doesn't behave the way you would expect it to is that it is not, in a precise sense, either 1-dimensional or 2-dimensional.


It isn't really fractal because there isn't really self similarity under expansion, it is more that, simply put, lines that wiggle are longer than lines which are straight, and smaller tighter faster wiggles can expand the length by just as much as a slow wiggles. Also note that the Hausdorff dimension of everything in sight here is 1. Er, well, everything in my cylinder example has a dimension of 2.

In order to discuss the limit of a sequence of sets it is easiest to have some sort of distance measurement in mind. (There are other ways to define limits, but...) The Hausdorff distance is perhaps the most obvious. In [imath]\mathbb{R}^2[/imath] area is continuous with respect to this distance. In [imath]\mathbb{R}^3[/imath] volume is. Therefore things like the disk and washer pictures in Calc II are in some sense justified. Also the boxes in the Riemann integral. However, area is not a continuous function of the Hausdorff distance in [imath]\mathbb{R}^3[/imath], nor is length in [imath]\mathbb{R}^2[/imath], and therefore you have to be more careful when measuring these lower dimensional structures.

Edited to add:
Bah, now I think that my statement that area is continuous under the Hausdorff distance needs some qualification. Consider say the distance between a space filling curve in the unit square and the unit square. I think it just need to be restricted to closed sets, but it is late and perhaps I need to reread some geometric measure theory tommarrow.

Yesila
Posts: 221
Joined: Sun Dec 16, 2007 11:38 am UTC

Re: Traveling across a square

Postby Yesila » Mon Feb 23, 2009 3:54 pm UTC

Mathmagic wrote:I think by 'e', he means [imath]\epsilon[/imath].


I know, but I like to point out other peoples "errors" by being a jerk. Maybe it would have been more appropriate to indicate that there is a way to typeset the [imath]\varepsilon[/imath], but wheres the fun in that?

**edit; I found the fun in that... well I found fun in doing it that way AND the way I did before. Previous post edited to reflect said fun.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Traveling across a square

Postby antonfire » Mon Feb 23, 2009 4:11 pm UTC

Well, if the meanings of symbols are context-independent, the permittivity of what material are you talking about, Yesila?

TeX takes longer to type and makes the page slow to load (and jerky while it's loading), so I try to avoid it when it's not necessary. The use of epsilon in that context is conventional, but using another variable doesn't change the meaning, as I hope everyone reading this thread is aware.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

vatar
Posts: 118
Joined: Wed Dec 31, 2008 4:58 pm UTC

Re: Traveling across a square

Postby vatar » Mon Feb 23, 2009 6:44 pm UTC

I remember seeing this problem somewhere as a teenager. Possibly in Asimov on Numbers?

kandalf
Posts: 41
Joined: Tue Jun 03, 2008 1:16 am UTC

Re: Traveling across a square

Postby kandalf » Mon Feb 23, 2009 10:02 pm UTC

This is pretty funny because I came up with this walking home from school one day and I've been puzzled about it ever since! On the other hand, I don't get much of the math in this thread :p

ST47
Posts: 125
Joined: Tue Oct 16, 2007 6:42 pm UTC

Re: Traveling across a square

Postby ST47 » Tue Feb 24, 2009 2:10 am UTC

You mathematicians always overthink everything. If you're walking strictly horizontally part of the time, and strictly vertically part of the time, sum all the displacement vectors with the same direction, and you get dx=1 and dy=1. 1+1=2.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Traveling across a square

Postby t0rajir0u » Tue Feb 24, 2009 2:29 am UTC

"We mathematicians" also think about convergence properly. You're assuming that total displacement is continuous, and there've been a lot of very intelligent comments in this thread about what kind of lengths are and aren't continuous in various topologies we could place on the space of paths.

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Traveling across a square

Postby z4lis » Tue Feb 24, 2009 3:21 am UTC

But it does not preserve arc length, as we've seen. For this, we'll need an even stronger notion of limit, so we'll restrict ourselves to differentiable curves (or piecewise differentiable curves) and require that not only the functions converge uniformly, but that their derivatives do as well. This is C1 convergence.


So if C-1 functions fn converge uniformly to f, then the arclength of f is the limit of the arclengths of fn? If so, are those the strictest conditions?

EDIT: Completely misunderstood the above quote when I read it initially. -_-
Last edited by z4lis on Tue Feb 24, 2009 5:55 am UTC, edited 1 time in total.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

ThomasS
Posts: 585
Joined: Wed Dec 12, 2007 7:46 pm UTC

Re: Traveling across a square

Postby ThomasS » Tue Feb 24, 2009 4:06 am UTC

z4lis wrote:
But it does not preserve arc length, as we've seen. For this, we'll need an even stronger notion of limit, so we'll restrict ourselves to differentiable curves (or piecewise differentiable curves) and require that not only the functions converge uniformly, but that their derivatives do as well. This is C1 convergence.


So if C-1 functions fn converge uniformly to f, then the arclength of f is the limit of the arclengths of fn? If so, are those the strictest conditions?


What do you mean by strictest? When [imath]f[/imath] is differentiable, we can find arclength with the integral [imath]\int \sqrt{1+f'(x)} dx[/imath]. Now, [imath]C^1[/imath] convergence ensures convergence of this functional, almost by definition. So the condition is sufficient. I do not believe that it is necessary. Both in the sense that one could also have some sequence which just happen to be convergent, and in the sense that there are various non-trivial relaxations of this condition studied in geometric measure theory: fractional powered derivatives and such.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Traveling across a square

Postby skeptical scientist » Tue Feb 24, 2009 6:55 am UTC

z4lis wrote:So if C-1 functions fn converge uniformly to f, then the arclength of f is the limit of the arclengths of fn? If so, are those the strictest conditions?

EDIT: Completely misunderstood the above quote when I read it initially. -_-

No. It's not enough for C1 functions to converge uniformly to f, they must converge in the C1 metric d(f,g)=max(sup(|f-g|),sup(|f'-g'|)). Those surely aren't the most general conditions under which the statement is true, however, since you can produce examples where fn -> f pointwise, and the lengths converge as well, without fn -> f in the C1 metric.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Gumbitha
Posts: 10
Joined: Tue Feb 24, 2009 6:49 am UTC

Re: Traveling across a square

Postby Gumbitha » Tue Feb 24, 2009 6:57 am UTC

Wow, I think about this one all the time. xkcd related places are really creepy deja vu for me.

Basically, I think of it in terms of a velocity.

For my example, 1m by 1m square, you move at 1m/s

If you use "taxicab" movement, it takes you 2 seconds to do, correct?

Even if you keep making the movements smaller, it still takes you 2 seconds to do, because you keep crossing the diagonal, back and forth, smaller and smaller, until it seems you are going completely diagonal.

However, if you go diagonally, it takes rt(2) seconds to travel, right?

This makes much more sense in my head, I'm sorry. x_x

User avatar
Cycle
Posts: 146
Joined: Mon Feb 25, 2008 1:55 am UTC

Re: Traveling across a square

Postby Cycle » Thu Feb 26, 2009 8:45 am UTC

A much better generality I think is something like Lipschitz functions, or absolutely continuous functions. Probably with a metric like [math]\sup_{x \in [0,1]} |f(x)-g(x)| + \limsup_{\epsilon \to 0} \sup_{|x-y|< \epsilon} \frac{|f(x) - g(x)|}{|x-y|}.[/math] I say something like that metric, because I'm not sure that's natural, or even well defined. You can fix it, the standard ways to make a norm bounded. Then you can define length as [math]L(f) = \sup_{0=x_0<x_1<...<x_n=1}\sum_{i=1}^n |f(x_i)-f(x_{i-1})|.[/math] (Or you can take the easy way out and just take 1 dimensional Hausdorff measure.) It's a much larger class of curves, with a normed linear space topology, so that length is continuous function to R. I don't know if that's the best you can get though.

Hausdorff measure, in any dimension, is not continuous on the Hausdorff (unfortunate naming scheme here) topology on the set of compact sets. (Did you read Edgar too?) Consider, for example, the sequence An = {q \in [0,1] ; q is rational and the denominator of q is less than n} converges to the set [0,1].


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests