Wikipedia:Reference desk/Archives/Mathematics/2007 July 9

From Wikipedia, the free encyclopedia

Mathematics desk
< July 8 << Jun | July | Aug >> July 10 >
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.


Contents

[edit] July 9

[edit] What's an angle theta?

I've stumbled upon the Math.atan2() function in javascript (description) from [1] in its orbit functions. It takes 2 values and returns the "angle theta" of the two. But I have no idea what a "angle theta" is or why is it useful. Can anyone explain it a bit more? Also, can anyone give me some pointers on making an object go a in circle? I want to use the r2 = x2 + y2 but I don't know how to manipulate it from then on. How do I change the x or y values so that it moves at roughly constant speed around a circle? --antilivedT | C | G 02:25, 9 July 2007 (UTC)

atan2 takes two parameters (x,y), and returns the angle between the x axis and the line from the origin to the point (x,y) of the xy plane. The angle is measured counterclockwise from the positive x axis, and takes values between -Pi and Pi. For example, atan2(7,7)=+Pi/4, atan2(-7,7)=+3Pi/4, and atan2(7,-7)=-Pi/4. To generate a uniform circular motion, use a uniformly increasing time parameter t and set x = x0 + r cos(w t) and y = y0 + r sin(w t) for some radius r, angular speed w, and center point (x0,y0). 169.230.94.28 02:37, 9 July 2007 (UTC)
"angle theta" means "angle whose name is θ", which is merely the conventional name for the angle in a polar coordinate system, just as x,y are the conventional names for Cartesian coordinates. What the guide says means: if you have the rectangular coordinates for a point then atan2(y,x) will give you one of its polar coordinates. —Tamfang 03:19, 9 July 2007 (UTC)
Ok thank you very much. --antilivedT | C | G 09:00, 9 July 2007 (UTC)

[edit] Four Color Theorem again

A previous article introduced me what is four color theorem. My quick reaction at that time has been formalized as a temporary report. It is not the policy of Wiki to discuss the subject matter HERE. However may I ask some simple questions: Am I allowed to say thanks HERE NOW? If NOT, are you going to delete this? If some readers, not me, break the rule, what are you going to do? Twma 02:27, 9 July 2007 (UTC)

If you mean "May I acknowledge Wikipedians' help in my report?" I think the answer is clearly yes (it's your report). If you mean "May I insert a thank-you into the reference desk for the help I received?" I'm not sure (but I doubt anyone would mind). Personally, having read through that discussion, I'd like to thank Lambiam on behalf of the Ref Desk and as a mathematician, along with everyone else who helped keep things on a even keel. (The usual cast: Ksmrq, Gandalf, Meni, Maelin, David, and Black Carrot.) Tesseran 04:11, 9 July 2007 (UTC)
I love the thought of an academic paper citing fellow scholars named Ksmrq and Black Carrot. —Tamfang 23:18, 9 July 2007 (UTC)
The Reference Desk talk page, or the pages of individual helpful posters would be more appropriate, and would last longer. --TotoBaggins 13:46, 9 July 2007 (UTC)

I am very happy to acknowledge the help of Ksmrq and Black Carrot as indicated by Tamfang BUT they may not be their true names. I did acknowledge Wiki as [5] in my references. I could not find the procedure to set up a talk page based on the information from http://en.wikipedia.org/wiki/Talk_page. I also did a search on **wiki, poster**. I got too much to be useful. So I do not understand the suggestion of TotoBaggins above. After I type in four ~ as my signiture, I do not get superscript-Talk. I must miss something as a result of my own ignorance. Twma 00:26, 10 July 2007 (UTC)

Every user automatically has a talk page; yours is User talk:Twma. Some have created custom signatures that include links to their talk pages, but for those (like you and me) who haven't, you can go to their user pages and click "discussion" at the top. —Tamfang 03:28, 10 July 2007 (UTC)

So the question becomes: How to create my custom signature that includes a link to my talk page? I looked through http://en.wikipedia.org/wiki/Help:Contents but did not know what to do. Thank you in advance. Twma 04:36, 10 July 2007 (UTC)

Answered on your talk page. --CiaPan 05:45, 10 July 2007 (UTC)

Thank you. Will follow up later. 130.95.16.119 01:07, 13 July 2007 (UTC)

[edit] Hilbert curve

I have a project in mind that involves mapping a 2d Hilbert curve (on (2^12)^2 points) to a 3d Hilbert curve (on (2^8)^3 points); more precisely, getting the coordinates of the kth point on the latter and assigning them to an array-cell corresponding to the coordinates of the kth point on the former. Is there an efficient way to say where is the kth point of a Hilbert curve of given degree, and/or conversely where in the sequence a given point (identified by coordinates) occurs? Unfortunately I haven't enough memory to do it the naive way, i.e. generate the curves recursively and then examine them. —Tamfang 02:49, 9 July 2007 (UTC)

You can find an arbitrary point on such a curve in log(k) steps. Each iteration of the 2D curve has 4 times as many points as the one before it, which means that if you take the modulo 4 of k, that will tell you where it is on the highest curve level; next subtract that from k and divide by 4 (if you're rounding down you don't need to bother subtracting first), repeat this process to find out where the curve is on the next level; after you've accounted for every level you will hit zero.
p^{}_n = {k_n}\mod{4}
k^{}_{n-1} = ( k_n - p_n ) / 4
So, you can use these relative positions (from 0 to 4) to find that point iteratively. I don't know offhand how the 3D hilbert curve works (is it 8 per level instead of 4?) but you should be able to apply the same idea to it. - Rainwarrior 03:52, 9 July 2007 (UTC)
Perhaps I'm dim but I don't see how converting to base 4 suffices. I need to know in what order the four sub-points wrap around the parent point (there appear to be eight possibilities). Or to put it less politely: Did you notice where I mentioned coordinates? —Tamfang 06:01, 9 July 2007 (UTC)
Sorry, I wasn't sure how far I should take the explanation. Starting at the lowest level, let's say we start with four points that are distance 2b apart (excepting the diagonals). Now, the curve at this level would pass through the four points, let's put them at: (-b,-b), (-b,b), (b,b), (b,-b) in that order, so, the numbers 0,1,2,3 map to these coordinates directly.
Now, if it turns out that was just the first of two levels instead, this his has given us a starting point which our second-level coordinate is going to be near to. Let's say our level 1 point had the value "3", so we are starting from (b,-b). At level two there is a smaller copy of that first level curve, rotated 90 degrees clockwise and then flipped vertically, placed around that point. So at this point, we do what we did for the first level, except smaller, so make the new points 2c apart, where c = b/2; and say our value for level 2 is "2", we should take (c,c), but now remember that we are rotated 90 degrees clockwise, so rotate that point 90 degrees clockwise to become (-c,c) and flip it vertically to become (-c,-c). Now that you've resolved its local position, and oriented it properly, you can translate it to the position found in level 1: (-c,-c) + (b,-b) = (-c+b, -c-b), or if b=2 and c=1: (1, -3)
So in this example we were mapping k=14 to the coordinate (1,-3) on a hilbert curve that ranges from -3 to 3 with points on coordinates with odd integers. 14 = (3*4) + 2. The process in general, beginning with the position on the largest curve is:
1. Find position on the curve by looking it up from the table (and scale by desired size): (-1,-1),(-1,1),(1,1),(1,-1)
2. Find the orientation of the next subcurve by looking it up from the table: (90 degrees counter-clockwise then flipped vertically, no rotation or flip, no rotation or flip, 90 degrees clockwise then flipped vertically)
3. If not on the smallest curve, recursively begin again at step 1 with half the size using the next coordinate.
4. With the position found in step 3 (or 0,0 if already at the smallest), rotate then flip it as specified and then add it to the coordinate found in step 1.
5. If at the largest curve, stop. Otherwise the value calculated in step 4 will be passed down to step 3 of the previous level.
Is this clearer? The way this works is that the curve is composed of smaller copies of itself that have been scaled, rotated, and/or flipped. If you understand the relationship between the first and second level you can apply that same relationship again and again until you reach the desired level. - Rainwarrior 07:26, 9 July 2007 (UTC)

Maybe this diagram will help. I've arranged values of k for a 2-level hilbert curve; I hope it makes the recursive relationship clear:

k
0 1 14 15
3 2 13 12
4 7 8 11
5 6 9 10
(k-(k mod 4))/4
0 0 3 3
0 0 3 3
1 1 2 2
1 1 2 2
k mod 4
0 1 2 3
3 2 1 0
0 3 0 3
1 2 1 2
coordinates
(-3,-3) (-1,-3) (+1,-3) (+3,-3)
(-3,-1) (-1,-1) (+1,-1) (+3,-1)
(-3,+1) (-1,+1) (+1,+1) (+3,+1)
(-3,+3) (-1,+3) (+1,+3) (+3,+3)

-Rainwarrior 07:33, 9 July 2007 (UTC)

In the general multidimensional case, given a hypercube and the start and finish vertices (which must be connected by an edge), there are several different Hilbert curves from start to finish. This is so because there are (except for the 1D and 2D cases) non-trivial automorphisms of the hypercube that leave a given edge fixed. For the 3D case there is one such automorphism, but because of the recursion you also have two choices for each of the 23 subcubes, giving altogether 16 "regular" curves (and continuously many if the choices on recursion are not required to be made uniformly in any way). Assuming you have picked one of these 16 ways and stick to it, you'll find that recursively the number of orientations in which the sub...subcubes are traversed is finite – I conjecture it is equal to 12, the number of edges of a cube, but in any case it is a relatively small number. Let's assume our coordinates are in the unit interval [0, 1) – just divide yours by 28. Then you can express (x, y, z) in the form ((a+x')/2, (b+y')/2, (c+z')/2), in which each of a, b and c is either 0 or 1, and (x',y',z') is again a point in the unit cube. The triple (a,b,c) identifies which of the 8 subcubes we're in, and (x',y',z') is the position of (x,y,z) in that subcube, after scaling it up to unit size. Repeating this gives the joint binary expansions of the coordinates. Although the Hilbert curve (mapping) is not injective, it actually is injective (and therefore bijective) if we only consider the binary sequences and do not identify 0.111... with 1.000... . In particular, it is bijective in the discrete case. If Hinvs(x,y,z) is the value in [0,1) assigned to (x,y,z) by the correspondence for orientation s, then Hinvs(x,y,z) = (d+Hinvs'(x',y',z'))/8, where d = ts(a,b,c) is a number in the range 0 through 7 corresponding to which subcube, in the traversal order, we're hitting, and s' = S(s; a,b,c) is the orientation in which that subcube is traversed. This now implies that the mapping in one direction can be produced by a finite state automaton, having one state for each of th 12(?) orientations, taking a triple of bits as input for each transition and producing an octal digit and a new state. The inverse mapping should also be a FSA, now taking an octal digit and producing a triple of bits. In the discrete case, you can actually also work in the other direction (from least significant to most significant digits), as long as the number of steps is fixed and sufficient for the largest possible case. I've sketched this for the 3D case, but the same idea applies in general.  --LambiamTalk 09:59, 9 July 2007 (UTC)

[edit] Erdős Magic

Does anyone know of any examples of graphs with large girth and large chromatic number? I understand why they're incredibly difficult to produce, but I'm having trouble finding any examples at all. J Elliot 08:06, 9 July 2007 (UTC)

All I've seen is triangle-free graphs of high chromatic number (see [2], question 5), which presumably isn't what you're after. Algebraist 11:54, 9 July 2007 (UTC)
Nope, but that's one of my favorite constructions :-) J Elliot 17:10, 9 July 2007 (UTC)

[edit] The rational numbers are weird...right?

Hey everyone, I'm back with another old qualifying exam question. This one has totally gotten under my skin. I'll present it as best I can. It's a two parter. The first part is:

Is there an ordering r_1, r_2,\ldots of the rational numbers between 0 and 1 such that \lim_{k \to \infty} r_k exists?

This is pretty much spectacularly false. Suppose you did have a convergent sequence. Since [0,1] is closed and rk is a sequence in [0,1], it converges to some point L in [0,1]. However, this means that in every ε neighborhood of L, all but finitely many rational numbers live inside this neighborhood. Simply choose ε so that (L - \epsilon, L+\epsilon)\cap[0,1] \neq [0,1] and you've got your contradiction.

This isn't the thing under my skin. It's the second part.

Is there an ordering r_1, r_2,\ldots of the rational numbers between 0 and 1 such that \sum_{k=1}^\infty r_k^k < \infty?

At first, it seemed to me like it ought to be false, since there are arbitrarily many rationals close to 1, and hence this infinite sum ought not converge. I thought about using the root test to show divergence, but it is inconclusive in this case (\limsup \sqrt[k]{r_k^k}=1). Now, I'm starting to think it's true. If one well orders the rationals (which is possible, I guess), pretty much every term in this series is basically zero, so I feel like the sum ought to converge if my rk ordering is this well ordering that we know exists.

What's the punchline here? I'm kind of lost. Any help would be appreciated! –King Bee (τ • γ) 14:24, 9 July 2007 (UTC)

Not really an analysis guy, but (a) are you sure that "rational numbers between 0 and 1" translates to [0,1] and not (0,1)? (2) Does that change your answer to part one? (As I think about it, probably no, but I'm concernd about your use of [0,1] being closed.) As for well-ordering, you could always order the numbers using Cantor's diagonal method for proving the countability of the rationals. Then p1 / q1 < p2 / q2 if p1 + q1 < p2 + q2 or p1 + q1 = p2 + q2 and p1 < p2. Donald Hosek 14:31, 9 July 2007 (UTC)
No, it doesn't change the answer. If the sequence converges to 1 or to 0, then you just have a half open interval (0, ε) or (1-ε, 1); you still get the same contradiction as before. Just pick ε to be less than 1 in this case.
Cantor's argument might be the place to be. I'll see if it can help. –King Bee (τ • γ) 14:42, 9 July 2007 (UTC)
  • Sweet, I got it! My office mate has aided me in my quest. The answer is yes. Here's how it's done:

Let \{q_1,q_2,\ldots\} be any ordering of the rationals in [0,1]. Notice that \forall q \in \mathbb{Q}\cap[0,1), \exists K such that \forall k \geq K, q^k \leq 1/k^2 (this is because for fixed q, \dfrac{q^k}{k^2} \rightarrow 0 as k \to \infty. Hence, set r1 = 1, and

r_k = \min_{i \in \mathbb{N}} \left(\{q_i^k < 1/k^2\}\setminus\{r_1,r_2,\ldots,r_{k-1}\}\right).

Then we have that r_k^k \leq 1/k^2 for all k; hence

\sum r_k^k \leq \sum 1/k^2 < \infty,

and our prescribed ordering works.

Thanks for the help though, sometimes just posting a message on the refdesk can make me figure out a problem! –King Bee (τ • γ) 15:03, 9 July 2007 (UTC)

(after ec) Bah! I was about to send this exact solution! As a result, I am reduced to expounding the moral: Sometimes, if you are asked to find a mathematical object with certain properties, the best way to do it is simply to jump in and start building, and carry on until something forces you to stop. (stolen from [3]) Here, as often happens, nothing stops you, and you have the object. If you fail, work out why and use that to prove impossibility. Algebraist 15:09, 9 July 2007 (UTC)
Responding to the title of the question: There is an open set which contains all rational numbers in the interval [0, 1] but does not contain the entire interval. So something has to be weird. -- Meni Rosenfeld (talk) 15:32, 9 July 2007 (UTC)
All right, I'll bite. How can I interpret your comment to make it true? Tesseran 16:51, 9 July 2007 (UTC)
Never mind, I've constructed sets like this myself. Whoops. Tesseran 17:00, 9 July 2007 (UTC)
Before adding this, I was thinking, "Now what was that counterintuitive example with rational numbers that shocked me when I first encountered it? An open set which contains all rationals but not the entire interval? No, that can't be right..." :) -- Meni Rosenfeld (talk) 17:08, 9 July 2007 (UTC)
Actually, maybe it was something else after all. I was thinking about \bigcup_{n=1}^{\infty}(r_n-2^{-n-1},r_n+2^{-n-1}), but there's no need for something this complicated - (-1,2) \backslash \left\{\frac{\sqrt{2}}{2}\right\} would suffice. I'll need to check in my books if there was anything more interesting. -- Meni Rosenfeld (talk) 17:16, 9 July 2007 (UTC)
Maybe it was "... With Lebesgue measure less than 1, and in fact, arbitrarily small.". This implies that it does not contain the interval, but is less trivial. -- Meni Rosenfeld (talk) 17:21, 9 July 2007 (UTC)
That's definitely what you were thinking. The ol' "surround the nth rational number with an interval of length ε/2n" psychotic thing we've had to wrestle with before. –King Bee (τ • γ) 17:36, 9 July 2007 (UTC)
Responding to the formulation of the question: Where you say "ordering", I think "enumeration" is a more appropriate term; in this case you want an injective (and therefore bijective) enumeration.  --LambiamTalk 15:35, 9 July 2007 (UTC)
Agreed, "enumeration" is a far better term for this kind of thing than "ordering". However, the analysis quals at this particular university tend to be rife with errata, this being the least egregious of them all. =) –King Bee (τ • γ) 17:36, 9 July 2007 (UTC)

[edit] Multiplication tricks

Do you know where I can find a list of tricks to perform multiplication faster? 67.182.185.143 21:20, 9 July 2007 (UTC)

There's a book called Miracle Math which talks about some of this. The most useful and easiest one to use is to use polynomial techniques to get an answer. Say you want to multiply 98 and 104. You can take advantage of the fact that 98=100-2 and 104=100+4 and multiply those two expressions giving: (100-2)(100+4)=1002+(4-2)100-2x4=10,192. Donald Hosek 22:16, 9 July 2007 (UTC)
I'm not sure if this is what you are looking for, but there are videos out there, which demonstrates some techniques. —Bromskloss 08:29, 10 July 2007 (UTC)
See our article on mental calculation. Gandalf61 11:07, 10 July 2007 (UTC)