Wikipedia:Reference desk/Archives/Mathematics/2010 January 21

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.

January 21

Riemannian geometry

How do you calculate a straight line in Riemannian geometry using a given coordinate system? For example, if I was using the surface of a sphere in spherical coordinates, what series of steps would I have to go through to find the equation of a great circle?

Will it tend to be feasible to solve symbolically, or would you have to do it numerically?

Alternately, what could I read to teach me to do that?

I know up to linear algebra and differential equations. — DanielLC 06:11, 21 January 2010 (UTC)

The closest analogue of a straight line on a curved manifold is a geodesic. If a string is made to stay on the surface then the geodesic is the one where you stretch the string. On a sphere like the world it is a great circle, planes fly along them. Dmcq (talk) 11:32, 21 January 2010 (UTC)

You need the geodesic curvature to be zero along the whole of the curve. Fly by Night (talk) 13:25, 21 January 2010 (UTC)

How do you find that using only the metric tensor? From what I managed to find, there isn't generally a closed-form solution. Is it simple to find a taylor series solution? — DanielLC 19:59, 22 January 2010 (UTC)

Even with simple figures you find integrals of square roots coming in, you might get a trig function but you're quite liable to get something much worse. what are you expecting really? Try expressing even the great circles of a sphere easily and that's as simple as they come. Dmcq (talk) 20:26, 22 January 2010 (UTC)

I'm just asking if you could find the taylor series. It seems like it would be simple enough. I doubt there's any difficulty in just finding the geodesic curvature. I can't imagine finding the change in geodesic curvature would be much harder. Keep doing that and you get the taylor series. I've only been able to find out how to get the geodesic curvature using an actual surface. — DanielLC 02:05, 23 January 2010 (UTC)

Taylor Series would not help very much. Taylor Series are local. You would need to prove that each and every term was zero. If you were to calculate the first 1,000 terms and found them all to be zero then that does not mean, for example, that the 2,001st term is zero. If you were able to prove that each and every term is zero then you would most probably be able to prove that the geodesic curvature is zero without resorting to Taylor Series at all. Fly by Night (talk) 19:44, 25 January 2010 (UTC)

Fractional chromatic number

What is the fractional chromatic number of the United States? --84.61.165.65 (talk) 17:21, 21 January 2010 (UTC)

Sounds like the Six degrees of separation, but it might also be generated by a new AI. It does help to just invest that extra minute or two making things clearer if you're going ask people to spend time on something. Dmcq (talk) 17:33, 21 January 2010 (UTC)

What is the chromatic number of the United States? --84.61.165.65 (talk) 17:42, 21 January 2010 (UTC)

The US isn't a graph. What do you mean? You mean the states as vertices with edges between those that border each other? Or the resident people as vertices with edges between those that know each other? Or what? --Tango (talk) 17:44, 21 January 2010 (UTC)

I mean the states as vertices with edges between those that border each other. --84.61.165.65 (talk) 17:58, 21 January 2010 (UTC)

Plus I guess he means Fractional coloring rather than the straight chromatic number but I've not come across fractional coloring before. Dmcq (talk) 18:02, 21 January 2010 (UTC)

Fractional chromatic number redirects to Fractional coloring, which does define the term. --Tango (talk) 18:09, 21 January 2010 (UTC)

4 is an upper bound on both numbers: File:Map of USA with state names.svg. That's hardly surprising, given that the graph is planar. — Emil J. 18:26, 21 January 2010 (UTC)

Why is the chromatic number of the United States not smaller than 4? --84.61.165.65 (talk) 18:43, 21 January 2010 (UTC)

West Virginia and the adjoining states are already not three-colourable. Algebraist 18:49, 21 January 2010 (UTC)

Well the fractional version is ≤7/2. I don't really want to try 3-fold coloring by hand though. :) Edit: Since the graph H with 1 point surrounded by 5 has χ_f(H) = 7/2, and the US map has H as a subgraph, the fractional chromatic number of the U.S. map is exactly 7/2. Rckrone (talk) 20:01, 21 January 2010 (UTC)

I want a proof of the fact that the fractional chromatic number of the U.S. map is not greater than 7/2. --84.61.165.65 (talk) 20:27, 21 January 2010 (UTC)

Try 2-fold coloring it. Rckrone (talk) 20:37, 21 January 2010 (UTC)

Expected value problem

I've been looking at some self-generated 2-dimensional probability problems, and have got stuck. I'm considering a kind of random walk, specifically the case of a particle initially being at a particular distance $d$ (≥1) from the origin, then moving by unit distance in a uniformly-distributed direction. If it is then distance $r$ from the origin, what is E[$r$]? For $d=1$ the answer comes fairly readily to be 4/π via the pdf of $r$, but for general $d$ I got totally lost, and for the particular case of $d=2$ the integration was beyond me. Numerical simulation showed that E[$r$] always exceeds $d$, with the ratio decreasing towards 1 as $d$ increases, but didn't help in getting a general result - is there one?→86.155.184.123 (talk) 19:11, 21 January 2010 (UTC)

According to Wolfram Alpha, the answer is $2{\frac {d+1}{\pi }}E\left({\frac {4d}{(d+1)^{2}}}\right)$, where E is the complete elliptic integral of the second kind, whatever that may be. Algebraist 19:33, 21 January 2010 (UTC)

Wolfram uses a different notation from our article; the result is $2{\frac {d+1}{\pi }}E\left({\frac {2{\sqrt {d}}}{d+1}}\right)$ in our notation.

It may also be interesting to know that the answer is $d+{\frac {1}{4d}}+{\frac {1}{64d^{3}}}+O\left({\frac {1}{d^{5}}}\right)$ for large d and $1+{\frac {d^{2}}{4}}+{\frac {d^{4}}{64}}+O(d^{6})$ for small d. -- Meni Rosenfeld (talk) 19:54, 21 January 2010 (UTC)

can you explain turbo codes OR LDPC?

I don't really care which one, which proves that this isn't homework (and it's not) but could someone explain EITHER turbo codes or LDPC in a way I can actually understand? I'm having so much trouble following either articles... thanks! 84.153.235.239 (talk) 19:31, 21 January 2010 (UTC)

p.s. I don't mean the effect, the net outcome, but the math: how it's actually done. Thanks again.

Error detection and correction is a huge subject and it's hard to know where you want to start. If you haven't heard of Shannon's theorem then I'd suggest getting a book on the subject.--RDBury (talk) 00:12, 22 January 2010 (UTC)

Try this: you've got a set of M possible messages to be encoded into an n-dimensional codeword space. If you map each message to a single codepoint in n-dimensional codeword space, and transmit that message into your channel, you can perform error detection by finding the nearest message codepoint to the received codeword point. If the encoded message points are far enough from one another, you can decode to the correct original message even if the received codeword is quite far away from the transmitted codeword.

The problem then becomes a very simple one: how do you pack M points into n-dimensional space while maximizing the distances between those points, yet still retaining a simple, fast algorithm for finding the nearest codepoint given a codeword? All the different error-correcting codes are ways of addressing this single problem for a variety of different constraints, and metrics for what is considered to be "near".

Shannon's noisy-channel coding theorem establishes a best-case bound on what is possible, by considering a very general scenario; LDPC and Turbo codes are ingenious attempts at solving the problem above that can get very close to the Shannon limit, providing n is sufficiently large for any given M.

Understanding Shannon's coding theorem is the key to understanding. There is a really good treatment of the underlying reasoning here, which is not unduly mathematical, and, if I recall correctly, rather similar to the treatment used in Shannon's original paper. -- The Anome (talk) 08:24, 22 January 2010 (UTC)

Sorry, the above is ALMOST easy enough for me to understand, but you could you simplify exactly what "n-dimensional" codespace is? How am I supposed to visualize that? Thanks!! 82.113.121.203 (talk) 03:23, 23 January 2010 (UTC)

n-dimensional codespace is the set of n-tuples. For n=1, 2, or 3 it is visualized as line, plane or space. For n>3 it is not actually visualized, but the concepts of point and distance are used. Bo Jacoby (talk) 08:15, 23 January 2010 (UTC).