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

Mathematics desk
< January 4 << Dec | January | Feb >> January 6 >
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 5

edit

Convergence

edit

I am working through a proof and I am at a part that might be pretty simple but I am a bit confused. It's probably stuff I understood well a few months ago and haven't worked on since and now I feel silly. Here is the expression I am working with, and what the proof says right after it:

 

Both sums on the right converge absolutely and locally uniformly for   (the second one because the expression in square brackets is   by the mean-value theorem, which tells us that   for any differentiable function   is bounded in   by  ), so the limit of the expression on the right as   exists and can be obtained simply by putting   in each term.

So, I get the first sum, that's easy. The second one confuses me. I think I understand partially. I believe I understand the mean value theorem part as we would have a   such that   and  . So, for that  , we have  . Then, the derivative of the integral is 0 and so the derivative of the thing in square brackets is just the derivative of the other term. I guess I definitely don't understand why showing the limit exists tells us we can just plug in  . I also don't understand if the double sum screws things up. Thanks. StatisticsMan (talk) 03:00, 5 January 2010 (UTC)[reply]

Maybe a simpler way to say it is  
The fact that there's a double sum does come into play, but you can show that   converges for s > 2, so you're still fine there with s = 3 + 2ε.
For arguing that thing is continuous in ε near zero, I'm pretty sure there must be some sort of theorem about the continuity of a series of continuous functions that are bounded by an absolutely convergent series or something like that. I'm not really sure exactly what it is, but it shouldn't be too hard to show if you don't have anything like that. The sum of all but finitely many terms is small and a finite sum of continuous functions is continuous. Probably someone will come along with a better informed answer to that. Rckrone (talk) 06:10, 5 January 2010 (UTC)[reply]
Yes, you are talking of the so called Weierstrass M-test. --pma (talk) 13:48, 5 January 2010 (UTC)[reply]
Does the fact that our function is complex-valued and not real-valued affect the mean value theorem? StatisticsMan (talk) 14:58, 6 January 2010 (UTC)[reply]
No, because the mean value theorem in the form of the inequality   holds true for any normed space valued function f continuous on the interval [a,b] and differentiable on (a,b) (BTW even continuous and differentiable up to a countable set is OK, and even absolutely continuous and differentiable a.e. is OK). What is no longer true for vector valued functions, even for E = R2, is that there is a a<t<b such that f(b)-f(a)=(b-a)f'(t). --pma 00:18, 7 January 2010 (UTC)[reply]

Alright, I have been able to show, correctly I believe, that  . Thus, for each interval [n, n+1], using the bound given above by Rckrone, we have a constant bound on   for each n. Rckrone above said   converges for s > 2. Is this supposed to say   (adding in the z)??? That is what we have in this situation at least and I'm pretty sure it is true. I know the Weierstrass M test for a single sum and it seems pretty clear that we can extend it to 2 sums using the 1 sum version because we can just take the inside sum of constants as a new constant. So, we can use that here. But, I guess I don't understand how that helps. This gives us uniform convergence of continuous functions (in t), so that what it converges to is continuous (in t). How does that help us plug in a certain value of  ? StatisticsMan (talk) 15:47, 18 January 2010 (UTC)[reply]



Let's define, for   and for  

 

For any   we have, by the mean value theorem (see Rckrone bound)

 

We wish to show that the family   is locally normally summable in the uniform norm, that is, for any   there exists a neighborhood   of  ) such that

 

This implies that the double sum

 

converges uniformly to a continuous function on  

Consider an open covering of   by open sets of the form

 

for real numbers   and   Let   be one of these.


It is convenient to bipartite the set of indices into the subsets:

 

 

Therefore, for any   there are at most   values of   such that   and in any case   are among them. Since for   and   we have   we can bound the sum on   as follows:

 


On the other hand, for all   either   or   In both cases, for any   and  

 

Note that for any   one has   so   and the last inequality holds.

Thus

  --pma 03:16, 20 January 2010 (UTC) PS: I re-edited in my talk page a more corrected version (here there are minor defects and tyops) --pma 14:39, 20 January 2010 (UTC)[reply]

Question on combinations

edit

I suspect there's an easy formula for figuring this out, but I can't figure out what it is:

Given n teams in a league (assume n is even), how many possible opening day match-ups are there? The order of each match-up determines which is the home team, so Team-A vs. Team-B is different from Team-B vs. Team-A. However, it doesn't matter in which order the matches are listed: A v B and C v D is the same as C v D and A v B.

It's not a simple combination, nor a permutation that I can figure. Any ideas? –RHolton17:40, 5 January 2010 (UTC)[reply]

The first team has n-1 choices for who to play and then 2 choices for who is the home team. Once that's decided, the next team on the list that isn't already scheduled for a game has n-3 choices for who to play and 2 choices for who is the home team. The next has n-5 choices, etc. So there are   possibilities assuming everyone plays. Rckrone (talk) 17:57, 5 January 2010 (UTC)[reply]

First find the number of (unordered) partitions of a set of size n into sets of size 2. Then you can multiply that by 2n/2 (2 choices for each of n/2 pairs) to get the number you're looking for. To be continued..... Michael Hardy (talk) 19:23, 5 January 2010 (UTC)[reply]

...and here is something possibly somewhat relevant.
But I think Rckone's answer may be enough for your purpose. Michael Hardy (talk) 19:26, 5 January 2010 (UTC)[reply]
Also, if N is such a number, N(n/2)!=n! (permuting the n/2 pairs in each of the N sets of pairs you get every permutation of the n teams, each once).--pma (talk) 19:54, 5 January 2010 (UTC)[reply]
Also you may first choose the subset of n/2 home teams, and then select a bijection with its complement (there are of course as many such bijections as there are (n/2)-permutations); and of course the result is again Rckrone's formula.--pma (talk) 20:03, 5 January 2010 (UTC)[reply]

I like Maple's answer for Rckrone's formula. Since n is even, let's assume that n = 2m where m is a positive integer. Then Maple gives

 

where Γ is Euler's Gamma function. More beautiful, but far less applicable. ~~ Dr Dec (Talk) ~~ 20:15, 5 January 2010 (UTC)[reply]

Möbius Maps

edit

Hi. I am trying to find the group G of Möbius transformations that map the set {0,1, } onto itself. Now, I have looked through my notes (this is a course on group theory incidentally) and have found the general function to be  , where you choose your   accordingly. Problems obviously arise though when you pick one z to be  ; indeed, what meaning does  ? So, to solve this problem my lecturer told us that, in the case   for example, rewrite your function as  , which obviously takes   to 0 and   to 1. What I don't understand is how this is, in general, supposed to take   to  . How does this work when   and  ? By my logic, for this case  , most definitely not a result I want. Can anyone help me out here? Thanks 92.0.129.48 (talk) 20:17, 5 January 2010 (UTC)[reply]

Check this. Does it give you a clue? Also note that   here is the point that compactifies the complex plane to get the Riemann sphere. There's no   (or if you like, it coincides with   and is one of the two fixed points of the involution  ).--pma (talk) 20:38, 5 January 2010 (UTC)[reply]


If   then you are restricting yourself to the sub-set of Möbius maps that fix   - these are the affine maps  . To map   to 0 and   to 1 then   and  , so you have  , as you said. In particular, if   and   then  . Geometrically, in the complex plane, this is a rotation through 180 degrees about the point  . Gandalf61 (talk) 08:27, 6 January 2010 (UTC)[reply]
A maybe-obvious-but-maybe-worth-to-recall remark. Since a Moebius map is fixed by the image of three points, it should be clear that the subgroup G is isomorphic to the symmetric group S3. It is generated e.g. by the maps 1-z and 1/z, the map 1-z corresponding to a transposition (0,1)(∞), and 1/z corresponding to (0,∞)(1). You may enjoy finding the other 4 maps by means of compositions of these, together with the associated permutations of {0,1,∞}. --pma 10:28, 6 January 2010 (UTC)[reply]
Thank you both for your help. On a related note though, what exactly is the order of a Möbius map f(z)? Is it just how many times must you apply f to reach the identity? Thanks 92.0.129.48 (talk) 19:45, 6 January 2010 (UTC)[reply]
Yepp. Note that order has a lot of meanings in maths; but here the group theoretic one (that is the one you mention) is I think the only reasonable one. --pma 22:34, 6 January 2010 (UTC)[reply]

NP and NPC

edit

Just wondering, because it is not specifically stated in the NP and NP-complete articles... Does a solution to an NP problem imply that all NPC is solvable? If it is proven that there is no solution to an NP problem, does it imply that there is absolutely no solution to all NPC problems? -- kainaw 21:50, 5 January 2010 (UTC)[reply]

I think you have the wrong idea about what NP means. All P problems are automatically NP. Problems that are not NP are harder than NP problems, not easier. --Trovatore (talk) 21:59, 5 January 2010 (UTC)[reply]
I wasn't wondering about NP and P. I was wondering if the following statement is reversible... Solving (in polynomial time) a single NP-complete problem proves that there is a polynomial-time solution to all NP problems. By "reversible", I mean is the following true: Proving that there is no polynomial time solution to an NP problem proves that there is no polynomial-time solution to any NP-complete problem. -- kainaw 22:09, 5 January 2010 (UTC)[reply]
Sure. That's just the contrapositive of the original statement. You don't need to know anything about P and NP for that. --Trovatore (talk) 22:13, 5 January 2010 (UTC)[reply]
That is what I thought, but I wasn't certain that there wasn't some rarely mentioned snag in the whole thing that made the contrapositive incorrect. -- kainaw 22:23, 5 January 2010 (UTC)[reply]
For what it's worth, your statement is a more precise fit for "NP-hard" than for "NP-complete"; NP-complete is just the intersection of NP-hard and NP. (In case it's confusing not to state it explicitly, NP-hard is not a subset of NP.) --Tardis (talk) 22:30, 5 January 2010 (UTC)[reply]