Wikipedia:Reference desk/Archives/Mathematics/2008 March 5

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 5

log^* n ?

The paper cited above uses the notation $log^{*}n$. I can't see where the author introduces it: it's used on the first page of the paper without any definition, so it must presumably be a well-known notation in the field of computational complexity. I've never seen it used before. Does anyone know what it means? -- The Anome (talk) 12:18, 5 March 2008 (UTC)

See iterated logarithm. -- Meni Rosenfeld (talk) 12:24, 5 March 2008 (UTC)

Thanks! -- The Anome (talk) 12:31, 5 March 2008 (UTC)

Trigonometry simplification

Our math teacher gave us this to express "as a single trig function without a denominator." Reviewing it in class, he got no answer, and some of us students got conflicting ones. Here is what he gave us (I don't know LaTex, so please excuse the ugliness: (1+cot²A)/(sin²A-1). I personally got csc^4vA. Any ideas? Abeg92contribs 15:10, 5 March 2008 (UTC)

(1+cot²A)/(sin²A-1)

but (sin²A-1)=-cos²A

a. So (1+cot²A)/-cos²A

but cotA = cosA/sinA

b. So (1+(cosA/sinA)²)/-cos²A

c. (1+(cos²A/sin²A))/-cos²A

d. ((sin²A+cos²A)/sin²A) /-cos²A

but sin²A+cos²A=1

e. (1/sin²A) /-cos²A

f. -1/sin²A cos²A

g. But 2sinAcosA=sin(2A)

ie sinAcosA=0.5sin(2A)

Therefor I get -4/sin²(2A) how does that sound?? (h) that's -4cosec²(2A)87.102.85.28 (talk) 15:26, 5 March 2008 (UTC)

I put letters in so if you didn't understand a step you can ask easily.87.102.85.28 (talk) 15:29, 5 March 2008 (UTC)

You can simplify that quite a lot by using cot²+1=cosec². --Tango (talk) 16:00, 5 March 2008 (UTC)

Just apply the following identities right at the beginning: cotan²A+1=cosec²A=1/sin²A, and sin²A+cos²A=1. Tesseran (talk) 00:31, 7 March 2008 (UTC)

Equilateral right triangle / shortest distance between points

I had this idea today when taking a shortcut through some side hallways in a big building.

Take a look at this image:
http://img181.imageshack.us/img181/6789/57031082cn1.png

To get from point A to B, you can take either the red path or the green path- the length of your walk is the same either way. But say there's a side hallway in the red path that lets you take a more "direct" diagonal path between A and B.
http://img137.imageshack.us/img137/1849/60259883cq5.png

But notice that your walk is still the same length. You just flipped that rectangle over. How about more side hallways?
http://img181.imageshack.us/img181/2305/69875898sd4.png
http://img187.imageshack.us/img187/2191/88665540yo1.png

No matter how many iterations you go through the red and green paths will always be of equal length. Even if you're going straight from A to B!!

Is this a known paradox? Am I totally off? :D\=< (talk) 16:28, 5 March 2008 (UTC)

It's not a (proper) paradox (what is?) You're measuring in 'L1' space see Taxicab geometry (Could this article have a better name, PLEASE?87.102.85.28 (talk) 16:55, 5 March 2008 (UTC)

Ah, that explained it perfectly- it's an entirely different space! Makes sense :D\=< (talk) 17:08, 5 March 2008 (UTC)

The wobbly line you are making could be described as a fractal (especially if you always go half way each iteration) - hence its greater length than the L2 diagonal. compare with the koch snowflake curve..87.102.85.28 (talk) 17:36, 5 March 2008 (UTC)

By the way why is user 'froth' now called 'd#;>>' - have you been robotised?87.102.85.28 (talk) 17:37, 5 March 2008 (UTC)

It's epic fail guy.. :D\=< (talk) 18:07, 5 March 2008 (UTC)

This is a simple demonstration that the arc length and (let's say parametric) limit operators on curves (and lengths) do not commute. --Tardis (talk) 17:57, 5 March 2008 (UTC)

The paradox, is that's what it is, is that the length of the limit is not equal to the limit of the lengths. I first came across this many years ago in "Riddles in Mathematics" by Eugene P. Northrop, where he incorrectly states that the length of the limiting line is the taxicab distance. AndrewWTaylor (talk) 18:04, 5 March 2008 (UTC)

It's not a fractal. The steps to produce it, being finite unions of line segments, aren't fractal, and the limit curve is a straight line. Also, taxicab geometry is an excellent name for the article. Black Carrot (talk) 19:59, 5 March 2008 (UTC)

That was no, no, and then no then I see, next time you answer it then.87.102.85.28 (talk) 20:13, 5 March 2008 (UTC)

So lets get this straight - if I replace the right angle (below left) with two right angles - and interate that - there's no fractal self similarity??????????87.102.85.28 (talk) 20:29, 5 March 2008 (UTC)

x           x           x
x           x           x
x           x           xxx 
x           x             x
x           xxxxx         xxx
x               x           x   
x               x           xxx
x               x             x
xxxxxxxx        xxxxx         xxx

Let's get one thing straight though - while I'm here: If your reasoning is wrong and you get the wrong answer this is not a paradox, nor is it counter-intuitive - what it is in fact is stupid.

So the remarkable (sarcasm) discovery that a L1 measure of length between A and B differs from any other L(n) (n is not 1) measure of length between A and B is not paradoxical. And never will be.87.102.85.28 (talk) 20:21, 5 March 2008 (UTC)

Are you saying a paradox means your reasoning is right and you get the wrong answer? Can you give an example of something then that is a paradox?  --Lambiam 23:37, 5 March 2008 (UTC)

That would be one example yes, and no I can't give an example - not a mathematical one. Or something that does not follow/is not explained by a priori knowledge -eg people popping into existence out of no where - those people could be described as paradoxes.87.102.74.217 (talk) 10:07, 6 March 2008 (UTC)

Well, it is a real relief that you can't give a mathematical example, because if reasoning that is correct could lead to a wrong answer, that would mean mathematics is inconsistent. If mathematics is consistent, then with your notion of paradox no mathematical paradoxes exist, period. So instead of saying "this is not a paradox", you could have said: "sorry, paradoxes don't exist".  --Lambiam 18:40, 6 March 2008 (UTC)

What you get after a finite number of iterations is not a fractal, a fractal would require you to do an infinite number of iterations, after which you would just have a straight line. I guess you could say a straight line is a fractal - it looks like a straight line at all scales - but it's a rather trivial one. --Tango (talk) 21:12, 5 March 2008 (UTC)

Well sorr-y if I'm not well-educated in theoretical math. Surely you can understand my confusion.. as you iterate more and more, it looks more like a line, and you could theoretically do it to infinity, and you'd be left with a hypotenuse of a right equilateral triangle. But it's only a "straight line" in taxicab-space, not in euclidian space. This seems like a legitimate question, why are you biting me for it? And when I said "paradox" I was thinking of Zeno's paradoxes, which I find very similar to this problem. And Tango how is this not a fractal? It looks like the construction of the koch snowflake, though yeah you just end up with a line in the end. A taxicab-space line.. at an infintesimal level it'd still be jaggy. :D\=< (talk) 22:33, 5 March 2008 (UTC)

Sorry if it seemed like I bit. see http://mathworld.wolfram.com/DiagonalParadox.html - of course what I was trying to say was that it's not a paradox, but a fallacy if you think the two measurements are unreconcilable. In that sense it's not a paradox - provided you can spot any errors of reasoning. There are no real paradoxes in maths - just errors of reasoning.87.102.74.217 (talk) ie it seems paradoxical --- but isn't.13:36, 6 March 2008 (UTC)

It doesn't matter how you construct it, a straight line is a straight line, and it wouldn't usually be considered a fractal (although, as I say, I guess the definition does kind of fit in a trivial way). I'm not really sure what it means to say it's jagged at an infinitesimal level... a straight line is differentiable, which by definition means it's straight at an infinitesimal level (that's a little tautologous, but oh well...). The curve after a finite number of iterations is only piecewise differentiable, but in the limit, it's smooth. --Tango (talk) 23:08, 5 March 2008 (UTC)

If you never make the leap from L1 to L2 then it remains jagged at infinitely small distances, hence the difference in length. (obviously it looks straight to you - but that's not the same as a straight diagonal) - if you don't explicity state you've changed the measurement metric you'll never get the euclidean length.87.102.74.217 (talk) 10:16, 6 March 2008 (UTC)

Could you give a rigorous definition of "jagged"? I'm not sure I'm understanding you. A straight line is a straight line, regardless of the metric you use to measure it's length. I interpret "jagged" as meaning having sharp points, in which case a straight line is certainly not jagged. It seems you are using the word to mean something different, since your definition seems to depend on the metric, which mine doesn't. --Tango (talk) 10:43, 6 March 2008 (UTC)

For a line in L1 space moving +x,+y the line can only be straight if either x or y = 0, there are no diagonals in L1, jagged here means contains a L (right angle shape) - I left a note right at the bottom explaining why (hopefully) the two lines (infinitely small 'L's and diagonal) are not/never the same. The usually method such as used when approximating a circle with many diagonals does not work here, even in the infinite limit because an L remains an L no matter how small - see below.87.102.74.217 (talk) 11:21, 6 March 2008 (UTC) Whereas in the case of a circle the chord becomes an increasingly better approximation to the arc (percentage error in lengths decreases) note that the error in L/diagonal line lengths remains constant independant of size..87.102.74.217 (talk) 11:23, 6 March 2008 (UTC)

It's length isn't relevant. A curve is a set of points. The set of points that make up a straight line and the set of points that make up a series of infinitely small L's are equal, therefore the curves are equal. --Tango (talk) 11:29, 6 March 2008 (UTC)

Consider the slopes - the diagonal has constant slope, the L curve has oscillating slope - taking a limit shouldn't change that unless you explicitly state you've changed.87.102.74.217 (talk) 12:30, 6 March 2008 (UTC)

Well, taking a limit *does* change that, whether you think it should or not. Consider the diagonal of the unit square ([0,1]x[0,1]) and the limit of your iteration for a line joining (0,0) and (1,1). Name a point that is on one line but not on the other. If such a point doesn't exist, the lines are, by definition, the same. --Tango (talk) 13:16, 6 March 2008 (UTC)

But their lengths are different according to the type of measure87.102.74.217 (talk) 13:29, 6 March 2008 (UTC)

Of course they are, but they're the same line. What does jaggedness have to do with the metric? A line is either jagged or it's not, it doesn't matter what metric you use. --Tango (talk) 16:51, 6 March 2008 (UTC)

But if I construct a line out of 'L's from (0,0) to (x,x) the length of that line is 2x, whether or not I have 1,10 or many 'L's - and so the limiting length is 2x (measured both in L1 and euclidean space), even though the limiting line is pointwise equivalent with the diagonal, but the L line is not differentiable in the same way the line x=y is.77.86.98.70 (talk) 19:14, 6 March 2008 (UTC)

Measured in Euclidean space, the limiting length is ${\sqrt {2}}$. Yes, it's weird, but that's the way it is. You can't have the same line having 2 different lengths under the same metric, that's nonsense. It doesn't matter where the line comes from, it's the same line. In Euclidean space, the line x=y is smooth, regardless of construction. As for the plane under L1 - is it even a differentiable manifold? I haven't studied differential geometry, so I'm not sure where to start working out what a "differentiable curve" is in L1 - can anyone help there? --Tango (talk) 19:36, 6 March 2008 (UTC)

Ok, I've done some research, and it looks like it should be the same differential structure as the Euclidean plane since the two metrics define the same topology and differential structures are unique for 2-manifolds. If I'm interpreting that correctly, the line x=y is smooth under L1 in exactly the same way as it is under L2, so the limiting curve is not "jagged" by any reasonable definition I can see. --Tango (talk) 19:52, 6 March 2008 (UTC)

You should read the linked archived discusssion below (and here http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Archives/Mathematics/2008_February_3#Distance) the diagonal line and limiting 'L' line have pointwise convergence as you point out, but do not share Uniform convergence.

I read your researched point above.. ((aside - It's worth noting that the shortest line from (0,0) to (a,b) (a<>0,b<>0) is in fact an infinite set of lines)), unlike in euclidean space where there is only one shortest line - the diagonal. I agree that a line in L1 can be smooth, but an alternative line (contructed of infinitesimal 'L's ) can also be constructed - which is pointwise but not uniformly equivalent to the smooth line..

The links always explain better than I do.77.86.98.70 (talk) 20:02, 6 March 2008 (UTC)

What you say is true, but I'm unsure of your point. The differentiability of a line depends only on the points that make up that line, not on how the line was constructed, so the convergence isn't relevant. However, the fact that it's not uniform is, I believe, the reason why a sequence of non-differentiable curves can tend to a differentiable one (that may be possible under uniform convergence, I haven't thought it through, but I would guess it isn't). My point is, the straight line (which is not a unique geodesic in L1, you're right, but that's not significant to this discussion) is not "jagged", regardless of the metric you consider it under. --Tango (talk) 20:57, 6 March 2008 (UTC)

My point is that the line produce from the limit of the 'stepped line' is in fact a series of mathematical singularities - did you understand what I was saying about pointwise equivalence not being all there is to it?87.102.83.54 (talk) 12:53, 7 March 2008 (UTC)

(deindent)What is singular about them? A point on a curve is singular if there isn't a well defined tangent there, but the tangent to a straight line is just itself (since, as I worked out above, the differential structure under L1 is the same as under L2, so the tangents are the same). A line is just a set of points, there is nothing more to it. --Tango (talk) 13:41, 7 March 2008 (UTC)

RE 87.102.85.28 - I learnt this as the Manhattan Metric, which seems a much nicer name IMO. -mattbuck (Talk) 23:45, 5 March 2008 (UTC)

That's the name I know it by too. I think it's a more descriptive name. --Tango (talk) 10:43, 6 March 2008 (UTC)

Nobody's bitten you for anything. Except 87.102, who seems a little sensitive about something. And the construction is extremely similar to that of a fractal like the Koch curve. However, you can construct an awful lot of ordinary Euclidean objects that way. For instance, you can turn the algorithm for a Sierpinski triangle into one for a regular triangle by pasting a fourth copy (upside down) into the center at every step. You've asked two different questions, though. One was what the limit curve would be - it's a straight line, regardless of the metric. The other was how long it would be - that depends on your system of measurement. With the Euclidean metric, it's the square root of the sum of the squares of the length and width of the box. With the Manhattan metric, it's the sum of the length and the width of the box. There are many other metrics you could use, but in each case the limit curve should be the same, since the underlying space is the same. Black Carrot (talk) 00:23, 6 March 2008 (UTC)

When considering the limit curve - you need to consider what it looks like under magnification (in this case infinite magnification) - if you iterate steps (manhattan) - you haven't used any diagonals - they curve is composed off lengths that are orthogonal to each other - no matter how small you go the lengths never become diagonal UNLESS you explicity state that you are making that change. As I mentioned above to another - the limit curve may be indistinguishable to a human observer - but is not mathematically the same as the diagonal.

<please> SO PLEASE DON'T TELL PEOPLE THEY ARE THE SAME </please>87.102.74.217 (talk) 10:21, 6 March 2008 (UTC)

This has already been discussed here before under uniform convergence. Basically, if you take a right triangle with two legs being length a and b, then to get from one side of the hypotenuse to another, traveling along the legs, would be a+b (taking only one turn). If you take two or three or four turns, the distance still traveled will be a+b. But if you take the limit as n goes to infinity, you are converging to the hypotenuse which has length sqrt(a^2+b^2). In other words, you have {a+b,a+b,a+b,a+b,...}->sqrt{a^2+b^2). Why and when is there this break as we go to infinity? The answer is because we do not have uniform convergence of this sequence. See if you (or anybody else here who is more familiar with wikipedia than I am) can find that old post and put a link here.130.166.165.124 (talk) 00:49, 6 March 2008 (UTC)

I remember that discussion. This is a link to the archived thread. Pallida  Mors 01:15, 6 March 2008 (UTC)

I remember it too. It still seems weird to me (I should study more analysis...), but I can accept a counterexample when I see one. --Tango (talk) 10:43, 6 March 2008 (UTC)

NOTE for an iterated line to become equivalent to a curve the successively smaller iterations must tend to the same length as the subdivision lengths tend to zero eg this works in the case of n chords approximating a circle since 2rsin(pi/n) can be approximated by 2rpi/n (sin a = a as a becomes 0), whereas x+y does not become a better approximation for sqrt(xx+yy) as x,y tend to zero (in fact in this case the error remains the same)87.102.74.217 (talk) 10:36, 6 March 2008 (UTC)

Those of you who think the L1 lenght should become the L2 length when the step length tends to zero might enjoy [[1]] ((and perhaps even Sorites paradox just for fun)). Also don't forget Suppressed correlative - tis a form of fallacy..87.102.74.217 (talk) 12:42, 6 March 2008 (UTC)

Aha, that wolfram link confirms it: the length of the stepped line remains equal to half the perimeter, no matter how many steps you take, including infinity. :D\=< (talk) 19:15, 6 March 2008 (UTC)

You were right all along - well done! (now go back to the computer desk) bye... (waves hand)77.86.98.70 (talk) 20:46, 6 March 2008 (UTC)

Was that really called for? And no, that's still not right. The wolfram link confirms no such thing. It says that the length is 2 for every step except the infinite one, which it agrees is sqrt(2). Black Carrot (talk) 00:21, 7 March 2008 (UTC)

I was being light hearted. The limit of the stepwise (right angled line) is point wise equivalent to the diagonal - but is not uniformly equivalent (note it has infinite discontinuities) - hence the difference.87.102.83.54talk) 11:32, 7 March 2008 (UTC)

it doesn't say that the length of the iterated line becomes root 2. You've misread that. I've explained to you that pointwise equivalence is not the only kind of equivalence possible - the two types of line are different lengths in euclidean space.87.102.83.54 (talk) 11:57, 7 March 2008 (UTC)

Also note that the limit of the 'stepped line' can be considered to be a series of mathmatical singularities, the true diagonal cannot. Another difference between the two lines.87.102.83.54 (talk) 12:06, 7 March 2008 (UTC)

The length of the straight line *in L2* is sqrt(2), the length in L1 is 2. I think that's what's being claimed. --Tango (talk) 11:25, 7 March 2008 (UTC)