Mathematics desk
< October 30	<< Sep \| October \| Nov >>	November 1 >

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

October 31

Pumping Lemma

Hi, I've been trying to understand the pumping lemma to no avail. I understand that it has something to do with the pigeon hole principle and that the idea is to get a repeating string x(y^i)z. I just still don't understand how to pick the pumping string, or figure out the minimum pumping length, or how to solve a proof. The wikipedia page made some sense but it was confusing too :/ —Preceding unsigned comment added by Legolas52 (talk • contribs) 00:09, 31 October 2010 (UTC)[reply]

I'm guessing you mean the pumping lemma for regular languages. I'm not sure what you mean by "how to pick the pumping string". Finding a pumping length isn't hard, though. For a regular language, write out its finite state automaton. Count the number of states--that's a pumping length. I say "a" pumping length because any larger length than the number of states actually works as well, and it may well be the case that a smaller number could work. The point is, the number of states *does* work. The proof of the pumping lemma is actually pretty simple. For a regular language where you've found its finite state automaton and the number of states in that automaton , say p, try an input string of p+1 characters. As the automaton processes these characters, the current state jumps around. How many possible different states can be visited during processing? At most, each character can cause a jump to a new, unvisited state, giving p+1 states visited--but there are only p states in the automaton. So, not every jump can be to a new, unvisited state, forcing some state to have been visited twice. That double visit is the key--the first visit is just before the first character of the "y" string and the last visit is just after the last character of the "y" string has been processed. We could simply skip "y", or we could repeat "y" as many times as we feel like, which simply corresponds to going around in the loop "y" traverses.

How to "solve a proof" is a bit vague, but I think you mean to ask how one uses the pumping lemma to show that a given language is not regular. (The pumping lemma doesn't show a language is regular; it can only be used to prove that no finite state automaton can accept a particular language, for if one existed, the pumping lemma would apply.) These lecture notes are decent and provide a number of examples starting at "Applications". To choose a good counterexample string (which might have been what you meant by "pumping string") sometimes just takes insight into the problem, though other times the first string you would ever think of trying to pump is the right one. There's no real general method. I remember spending a few hours on one pumping lemma problem once and finally finding a complicated but correct counterexample. (The prof. hadn't intended the question to be so hard and replaced it after I had completed it. The replacement, as I recall, was almost trivial in that the first thing worked obviously.) 67.158.43.41 (talk) 11:10, 31 October 2010 (UTC)[reply]

Analytic injective functions on the extended complex plane

Hello RD. I am aware that any analytic injective function on the whole complex plane (i.e. entire, injective), must be of the form az+b, a!=0 - I just found a very nice proof using the Casorate-Weierstrass theorem, much more concise than my previous efforts. However, what happens in the case of the extended complex plane? I'd be astonished if the situation remained the same, only functions of the form az+b, but I can't think for the life of me how to investigate the thing.

Would it be easier to operate on the Riemann sphere, perhaps? I've just recently been introduced to the concept of a Riemann surface, atlases etc., so I'd probably be happy with any theory you would consider 'simpler' than that - thankyou for suggestions. Estrenostre (talk) 01:27, 31 October 2010 (UTC)[reply]

Actually, the situation is very similar. Suppose your injective function f maps the point at infinity to d. Consider g(z) = (dz + 1)/(z - d). g maps d to infinity and infinity to d, and it's not hard to check that g is its own inverse. So g(f(z)) is an analytic injective function that fixes its infinity. That means we can ignore infinity, and think of it as an analytic injective function on the complex plane, which you already know means g(f(z)) = az+b. So f(z) = g(g(f(z))) = g(az+b). Play around with this, and what you'll get are precisely the Mobius transformations.--203.97.79.114 (talk) 03:03, 31 October 2010 (UTC)[reply]

Thankyou, that's a great help! Estrenostre (talk) 12:01, 31 October 2010 (UTC)[reply]

Lie Groups and Infinitesimal Actions

I'm reading a paper about projective differential geometry. There is a smooth surface in the real projective space RP³, and the authors say that the group PGL(4,R) acts on RP³. That's what projective differential geometry looks at: differential invariants under the action on projective transformations. They claim that the Lie algebra $\scriptstyle {\mathfrak {sl}}(4,{\mathbf {R} })$ is the "infinitesimal version of the PGL(4,R)-action." Are they trying to say that the tangent space to PGL(4,R) at the identity is SL(4,R)? I always thought that the tangent space to SL(n,R) at the identity was the space of n-by-n matrices with zero trace. If the tangent space to SL(n,R) at the identity is different to SL(n,R) it means, in some sense, that SL(n,R) is not linear. So how can SL(4,R) be the tangent space to PGL(4,R) at the identity when SL(4,R) is not linear? — Fly by Night (talk) 18:05, 31 October 2010 (UTC)[reply]

Here's a link to the article in question. — Fly by Night (talk)

The question is confused because you use lower case sl for the Lie algebra in only one place, when you should use it in several. The point is that PGL and SL are infinitesimally the same, equivalently, (they're semisimple) they have the same global universal cover or the same quotient by their centers. Their lie algebras are the traceless 4x4s: sl is the subspace of gl with zero trace, pgl is the quotient of gl by the diagonal) John Z (talk) 00:06, 1 November 2010 (UTC)[reply]

That's why I'm making a post on the reference desk: I, myself, am confused by it all. The paper tells me that they're infinitesimally the same. I was hoping someone could explain why, and what it means. — Fly by Night (talk) 10:49, 1 November 2010 (UTC)[reply]

Starting with lie group morphisms SL->GL->PGL and taking the tangent space at the identity, the lie algebra, we get sl-->gl-->pgl, which is an isomorphism of lie algebras sl & pgl, so sl is the "infinitesimal version of PGL(4,R)" . SL being a tangent space of PGL doesn't make sense, capital SL is a lie group, not a vector space (with lie algebras structure) like sl.John Z (talk) 04:20, 2 November 2010 (UTC)[reply]

Incorrectly named theorems

It is often, rather cynically, remarked in mathematics that a theorem is named after the last person to discover it, hence denying its original discoverer of recognition, such as the Steinitz exchange lemma. This law is named after a person, who attributes it to someone else, but I cannot for the life of me remember who. Anyone know? Thanks. 128.232.247.49 (talk) 22:02, 31 October 2010 (UTC)[reply]

I've heard the name you're referring to but I can't come up with it at the moment. However the general principle that what counts is not the first person to discover it, but rather the last, is called the Columbus principle. I used to think it was an injustice but I don't anymore. If you discover something and then someone discovers it again later, it means you did not succeed in adding your knowledge to the general heritage of mankind, so why should you get credit for it? --Trovatore (talk) 22:26, 31 October 2010 (UTC)[reply]

Stigler's law of eponymy. Algebraist 22:32, 31 October 2010 (UTC)[reply]

Trovatore: Technological, political and religious factors can all influence the dissemination of knowledge. Controversial, hypothetical example: You were a political prisoner/prisoner of war and your work was never released until many years after the down fall of the regime that held you prisoner. By which time, another mathematician had used all of the freely available work to arrive at your conclusion. Albeit some years later. I would say that you deserve all the credit, and then some. — Fly by Night (talk) 22:38, 31 October 2010 (UTC)[reply]

Also,it may also happen that at the time of the first discovery people is simply not ready to it, and many years are needed in order that they get acquainted to it. For instance, think to Paolo Ruffini's work on the impossibility of solving the quintic by radicals ^[1]. In 1799 he proved the theorem up to a minor gap, that himself or somebody else could have fixed soon, had his book met the attention that deserved. But times were not ready for a such a revolutionary idea as proving the impossibility; 20-30 years later, this idea had slowly spread and become more natural, and Abel and Galois got more lucky (at least, on the publishing side). --pm a 00:30, 1 November 2010 (UTC)[reply]

Yes, sometimes the dog really does eat your homework. So what? You weren't the one who made the contribution to human knowledge. --Trovatore (talk) 01:00, 1 November 2010 (UTC)[reply]

:-) Who knows who are the ones? Often, it is really difficult to weigh the impact of a contribution, that can be quite delayed in time. But I get your point; science is not a solitary game, and a discovery really makes a contribution if it is followed. --pm a 09:25, 1 November 2010 (UTC)[reply]

Sorry to cut the tangential philosophizing short, but to answer the original question, the phenomenon is known as Stigler's law of eponymy, or sometimes Boyer's law. —Bkell (talk) 00:43, 1 November 2010 (UTC)[reply]

This thread exhibits why StatisticsMan's law of indenting is so important. I realize that Algebraist was replying to the OP so he indented the same as Trovatore, who had already replied. But, it just looks as if Algebraist's remark is part of the reply by Trovatore. I actually missed it (and noticed it when I had read through half of this topic) and it looks like Bkell did the same thing since he answered the question that had already been answered. I just put an extra line break in there and now it looks separate. That's my law of indenting. StatisticsMan (talk) 17:04, 1 November 2010 (UTC)[reply]

Oh, yeah, oops. Good catch. —Bkell (talk) 18:24, 1 November 2010 (UTC)[reply]

^ http://www-history.mcs.st-and.ac.uk/Biographies/Ruffini.html

[1] ttp://www-history.mcs.st-and.ac.uk/Biographies/Ruffini.html

[1]