Wikipedia:Reference desk/Archives/Mathematics/2011 April 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.

April 21

about isomorphism between chain groups

Suppose K and L are two triangulations of the same polyhedron. Are the chain groups Cp(K) and Cp(L)isomorphic ? Mathematics2011 (talk) 08:45, 21 April 2011 (UTC)

In general, No. It depends of your triangulation. For example, C₀(K,G) is the abelian group of formal sums of vertices in the triangulation of K with coefficients in G; with group operation being addition. So

$C_{0}(K,G)=\{\alpha _{1}v_{1}+\cdots +\alpha _{n}v_{m}:\alpha _{i}\in G\}\cong \bigoplus _{k=1}^{m}G\,.$

If K has more vertices than L then C₀(K,G) will have a different rank to C₀(L,G) and they won't be isomorphic. The important thing is that as you add more vertices you have to add more edges and faces. Then everything cancels when you take the quotients to get the homology groups. — Fly by Night (talk) 11:56, 21 April 2011 (UTC)

Technical point: This argument does not work if C₀(K,G) does not have a uniquely defined rank -- for example if G is the direct sum of an infinite number of Z's. Aenar (talk) 22:15, 25 April 2011 (UTC)

In some applications, triangulations are not permitted to add more vertices (for instance point set triangulation). In that case, the chain groups will be isomorphic. Sławomir Biały (talk) 12:49, 21 April 2011 (UTC)

The Hauptvermutung article might be of interest too. — Fly by Night (talk) 13:28, 21 April 2011 (UTC)

thank you very much — Preceding unsigned comment added by Mathematics2011 (talk • contribs) 04:08, 23 April 2011 (UTC)

Contour Integral

I am trying to evaluate

$\int _{0}^{\infty }\!{\frac {x^{1/2}\log {x}}{1+x^{2}}}\,dx\,$

via contour integration. The contour I have chosen is a keyhole contour, with the main contour being of radius R and the indented contour being of radius r, avoiding the origin and allowing me to use the principal branches of $z^{1/2}$ and $\log {z}$. Call the line segment just above the negative real axis AB and that just below the negative real axis DE. I believe that

$\int _{C_{R}}{\frac {z^{1/2}\log {z}}{1+z^{2}}}\,dz+\int _{AB}{\frac {x^{1/2}\log {x}}{1+x^{2}}}\,dx+\int _{C_{r}}{\frac {z^{1/2}\log {z}}{1+z^{2}}}\,dz+\int _{DE}{\frac {x^{1/2}\log {x}}{1+x^{2}}}\,dz=2i\pi [Res({\frac {z^{1/2}\log {z}}{1+z^{2}}}\ ,i)+Res({\frac {z^{1/2}\log {z}}{1+z^{2}}}\ ,-i)]$

First question: is this correct? Second question: if it is, does the right hand side simplify as follows?

$2i\pi [Res({\frac {z^{1/2}\log {z}}{1+z^{2}}}\ ,i)+Res({\frac {z^{1/2}\log {z}}{1+z^{2}}}\ ,-i)]=2i\pi [{\frac {i^{1/2}\log(i)}{2i}}+{\frac {(-i)^{1/2}\log(-i)}{2i}}]={\frac {{\pi }^{2}}{2}}$

Making the not completely reasonable assumption that the above is correct, my problem now is that I am unsure how to incorporate my choice of branches into the two integrals I have to perform. I know that both of the contour integrals disappear but am unsure how to express what happens to the other two. Thank you. meromorphic [talk to me] 15:27, 21 April 2011 (UTC)

Yes to the first question. You shoud then evaluate the residues by writing out the complex numbers such as z = i in polar form. Here you invoke the definition of log(z) and z^1/2. The choice of the branch cuts for these functions fixes how you choose theta when you write some arbitrary z as r exp(i theta). This in turns determines the value of log(z) and z^(1/2) unambiguously. Count Iblis (talk) 18:29, 21 April 2011 (UTC)

But, referring to the last step of the computation here, $i^{(1/2)}=(1+i)/{\sqrt {2}}$, so your final answer is missing a factor of $1/{\sqrt {2}}$. Sławomir Biały (talk) 00:31, 22 April 2011 (UTC)

Thank you both for your help. I managed to get the correct answer. Happy editing! meromorphic [talk to me] 13:57, 23 April 2011 (UTC)

On reflection, have I definitely done this correctly? Should I not have only the upper half of the contour I have given above combined with a line segment going along the positive x axis? meromorphic [talk to me] 09:54, 24 April 2011 (UTC)

You can do it both ways. You can indeed use a contour consisting of a half circle in the upper half plane. That's a bit easier because you then only have to evaluate one residue and you can take the branch cuts to be any arbitrary curves that move from the origin into the lower half plane (although, even if you have to use the contour you used, you can always split the contour into two or more parts, each using a different defintion of the logarithm with different branch cuts, such that the logarithms are analytic continuations of each other). Count Iblis (talk) 15:02, 24 April 2011 (UTC)

That's a relief! I was thinking to myself that surely having only half the contour seemed like the way to go. Cheers Count. meromorphic [talk to me] 19:49, 25 April 2011 (UTC)

Number of involutions in groups

Is the following statement true: If G a group, then |{g∈G|o(g)=2}|∉{2n|0<n∈ℕ}? --84.62.193.214 (talk) 16:18, 21 April 2011 (UTC)

A simpler way to phrase this is to ask whether the number of elements of order 2 must be odd. Michael Hardy (talk) 18:08, 21 April 2011 (UTC)

It's been a while since I've thought about anything like this, so tell me if I'm missing something. Elements of order more than 2 are not their own inverses, so we've got an even number of those:

${\begin{array}{rcl}a&\leftrightarrow &a^{-1}\\b&\leftrightarrow &b^{-1}\\c&\leftrightarrow &c^{-1}\\&\vdots \end{array}}$

Then we've got elements of order 2, and one element of order 1. So the number of elements of order 2 must be odd if the order of the group is even, and even if the order of the group is odd. Finally, we recall that groups of even order and groups of odd order both exist. Michael Hardy (talk) 19:02, 21 April 2011 (UTC)

This seems plausible, but I'm not sure it's water tight. I don't think you can pair off all of the elements like that. The a`s, b`s and c`s need to be connected somehow. If not, then the group would be build from the set

$\{e,a_{1},a_{1}^{-1},a_{2},a_{2}^{-1},\ldots ,a_{n},a_{n}^{-1},b_{1},b_{2},\ldots ,b_{k}\}\,,$

where the a_i are distinct elements with order greater than two and the b_j are distinct elements of order exactly two. If the a_i's are all independent then the group will have only subgroups of order three and two, namely

$\{e,a_{i},a_{i}^{-1}\}\ {\text{and}}\ \{e,b_{j}\}\,.$

That would mean, by Lagrange's theorem that the order of the group must be divisible by both 2 and 3. Say that a₁ had order six; consider

$a_{1}^{0}=e,\ a_{1}^{1}=a_{1}^{1},\ a_{1}^{2}=\,?,\ a_{1}^{3}=\,?,\ a_{1}^{4}=\,?,\ a_{1}^{5}=a_{1}^{-1}\,.$

Three of the a_i's and b_j's are going to be needed to fill the gaps. So there must be some group relations involved. If there are no group relations then we have a cyclic group, that must have a prime number of elements, and so have no elements of order two, except C₂. I'm not trying to make a statement or a proof here. I'm just explaining some problems I see. Hopefully Michael will be able to resolve any doubts. — Fly by Night (talk) 21:10, 21 April 2011 (UTC)

Michael's argument is correct. We can certainly partition the group via the equivalence relation 'a is related to itself and its inverse' --- these sets will have size either 1 or 2, depending on the order of the elements in each set. We want to find the number of elements of order 2; taking twice the number of sets of size two we have away from the group order (i.e. removing the elements of order greater than 2) preserves the parity of the group order. We must then remove one more element, the identity, which will flip the parity of the group order, and give us the number of elements of order 2 as Michael described. Apologies for essentially repeating his argument... Icthyos (talk) 22:00, 21 April 2011 (UTC)

That's true, you just repeated his argument without addressing any of the possible problems. A group is not just a set. It has extra structure. The elements must interact in special ways, see List of finite simple groups. For example, what if, in Michael's notation, a³b² = c and ab = d? As I've said, if the partition works, without any group relations, then the only subgroups have order two and three, so the group order is divisible by two and three. For example, in a group of order 35 there must be some group relations between the the a_i's and b_j's. The group relations might cause problems. This kind of a question isn't always very easy. See Finch, C. E.; Foote, R. M.; Jones, L.; Spickler, D. (2002). "Finite Groups that have exactly n Elements of Order n". Mathematics Magazine. 75 (3). Mathematical Association of America: 215−219. — Fly by Night (talk) 22:30, 21 April 2011 (UTC)

Yes, there will certainly be relations in the group, but that doesn't affect the argument. Perhaps I'm not understanding your objection. We're just enumerating the (finite) group in its entirety, then subtracting off the 'inverse pairs' of elements whose orders are greater than 2. You seem to be taking the entire group as a generating set, then looking at all possible words on those generators. Yes, there will be lots of words representing the same group element, but that doesn't affect our ability to list the finite number of genuine group elements. Icthyos (talk) 22:49, 21 April 2011 (UTC)

Add to Michael's argument the observation that, if the order of the group is odd, then there cannot be any elements of order two and we've answered the original question in the affirmative (for finite groups). Sławomir Biały (talk) 23:09, 21 April 2011 (UTC)

There are no objections per se. Let's assume I'm an OP. I'm just mentioning some things that make me feel uneasy. As I said: Michael's argument is plausible; but I'm not sure it's water tight. No-one seems to be addressing the point that if we can pair off the elements, without relations, then the group order must be divisible by either two, or three, or both. If not, then there must be group relations, and why don't they effect the parity argument? Simply saying (to paraphrase) "because they don't" isn't very convincing. My point is that in these "pairings" we might get an odd number of elements because of some group relations. — Fly by Night (talk) 23:30, 21 April 2011 (UTC)

How about this: Suppose that we have a set and a given involution defined on it. Then each orbit of the involution must have either cardinality two or one. Hence, if the cardinality of the set is even, then the number of fixed points of the involution must also be even. If it's odd, then the number of fixed points is also odd. Let the set be G and the involution be $x\mapsto x^{-1}$. The set of fixed points consists of the identity and the order two elements of G. Hence the set of order two elements must be odd if G has even order. It must be even if G has odd order, but because the order of any element divides the order of G, there can be no element of order two in that case. Sławomir Biały (talk) 23:41, 21 April 2011 (UTC)

Fly By Night: your 'subgroups' of order three are only genuine subgroups if a_i has order at most 3, otherwise the set won't be closed under multiplication. Yes, we have to decide what a_i² is (and so on). Say it's equal to some group element, a_k. This will lie in the subgroup generated by a_i, and we have the relation a_i²a_k^-1 = 1, but we just look at our complete enumeration of the group elements, see that we've already taken a_k and its inverse into account, and continue the argument. Icthyos (talk) 08:35, 22 April 2011 (UTC)

I know! That was exactly my point. If the subgroups aren't all of order two and three then it might imply group relations. I've said that two or three time already. Anyway, the matter is now resolved. Thank you. — Fly by Night (talk) 15:59, 22 April 2011 (UTC)

Is the following statement true: If G a infinite group with finitely many elements of order 2, then the number of elements of order 2 in G is odd or zero? --84.62.193.214 (talk) 20:04, 21 April 2011 (UTC)

Is the following statement true: This is a homework problem? — Fly by Night (talk) 20:26, 21 April 2011 (UTC)

No. Look at the free product $Z_{2}*Z_{2}$. This has exactly two elements of order two. Sławomir Biały (talk) 23:15, 21 April 2011 (UTC)

(Presumably you meant free product?) Icthyos (talk) 23:16, 21 April 2011 (UTC)

Oops. It's not even true what I said. But one should be able to produce a counterexample somehow. Sławomir Biały (talk) 23:19, 21 April 2011 (UTC)

"Fly by Night", I do think you're missing something. Whatever it is you mean by "independent", I don't think I was suggesting that the elements involved should be "independent". I was just saying that some elements---those of order 1 or 2---are their own inverses, and all others have an inverse other than themselves. Of those that are not inverse to themselves, there must be an even number. Michael Hardy (talk) 23:47, 21 April 2011 (UTC)

By independent, I mean not related by group relations. And yes: I am obviously missing something; that's why I've been asking questions! — Fly by Night (talk) 23:51, 21 April 2011 (UTC)

OK, look at a concrete example: the symmetric group on three elements. The group has six elements:

(), (ab), (ac), (bc), (abc), (acb).

Pair them:

() <----> ()

(ab) <---> (ab)

(ac) <---> (ac)

(bc) <---> (bc)

(abc) <---> (acb)

Michael Hardy (talk) 04:59, 22 April 2011 (UTC)

Thanks for the explanation. I've done some research and your method appears on a few homework problems solution sheets; so it must be right. I hope you can see my apprehension. My worry was that you might pick up the same element twice in the pairing because of some group relation. I also hope I made it clear that I wasn't saying you were wrong. I just had doubts, that's all. — Fly by Night (talk) 14:47, 22 April 2011 (UTC)

See my argument above. It was supposed to settle your apprehension, but seems to have been ignored instead. Sławomir Biały (talk) 15:07, 22 April 2011 (UTC)

I no longer have an apprehension. Michael explained it to me, and I did some Googling. The problem is already resolved. I only made that last post to make sure Michael knew I wasn't saying he was wrong. I didn't realise that I had to comment on every post. Sorry. — Fly by Night (talk) 15:55, 22 April 2011 (UTC)

Well, no. But it's a little hard to understand all of the continued hand-wringing after a rigorous proof has already been given. Sławomir Biały (talk) 16:05, 22 April 2011 (UTC)

What "continued hand-wringing"? You made that post at 1:41, and I only made three posts after that. One to explain to Michael what I meant by "independent", a second to correct the first, and a third to admit that I was missing something. These were all secondary interactions that has little to do with the proof. I don't see anything wrong with that. I don't understand the prolongation of this thread. Michael has explain, I have done some Googling, and the matter is resolved. Are you upset that I didn't praise your proof? If so, then I'm sorry. It was a lovely proof. I'm sorry that I missed its beauty. — Fly by Night (talk) 16:56, 22 April 2011 (UTC)

No, I'm not upset about anything. But I did rather mean to call attention to the fact that this was proven without relying on the feature of Michael's proof that you objected to. It seemed odd to me that the thread proceeded as though my post had never been made, a post that was intended to put an end to this pointless discussion. I just assumed you hadn't seen it. Sławomir Biały (talk) 21:58, 22 April 2011 (UTC)

I'm pleased you're not upset. I did not object to anything; I simply had some questions. In fact, I explicitly stated above: "There are no objections per se." Michael has made his point, my Googling has supported it. The matter is now, as far as I am concerned, closed. Maybe we should address the OP now… Thanks again Sławomir. — Fly by Night (talk) 01:42, 23 April 2011 (UTC)

Integrals and limits

Can anyone point me towards a proof (preferably online, but in a book if needs be!) that if $f_{1},\,f_{2},\ldots$ measurable functions: $\Omega \to \mathbb {R}$, where $\mu (\Omega )<\infty$ and $f_{n}(x)\to 0\,\forall \,x\,\in \,\Omega$, then

$\lim _{c\to \infty }\sup _{n\in \mathbb {N} }\int _{|f_{n}|>c}|f_{n}|d\mu =0\Rightarrow \int _{\Omega }|f_{n}|d\mu \to 0$

please? Staytime101 (talk) 16:58, 21 April 2011 (UTC)

Am I just being obtuse, or is $f_{n}\equiv 1$ a counterexample? Sławomir Biały (talk) 18:28, 21 April 2011 (UTC)

$f_{n}(x)\to 0\,\forall \,x\,\in \,\Omega$ doesn't hold in that case :) Staytime101 (talk) 00:01, 22 April 2011 (UTC)

Ahha! I missed that. Sławomir Biały (talk) 00:08, 22 April 2011 (UTC)

Choose a cutoff value of c so that

$\sup _{n\in \mathbb {N} }\int _{|f_{n}|>c}|f_{n}|d\mu <\epsilon .$

Then apply dominated convergence to conclude that $\int _{\Omega }|f_{n}|\chi _{\{|f_{n}|\leq c\}}d\mu \to 0$. Hence,

$\limsup _{n\to \infty }\int _{\Omega }|f_{n}|d\mu =\limsup _{n\to \infty }\int _{\Omega }(|f_{n}|\chi _{\{|f_{n}|\leq c\}}+|f_{n}|\chi _{\{|f_{n}|>c\}})d\mu <\epsilon .$

Since $\epsilon$ was arbitrary, you have the result. Sławomir Biały (talk) 00:12, 22 April 2011 (UTC)

Ah, very smart, that was simpler than expected. Thank you!! Staytime101 (talk) 02:45, 22 April 2011 (UTC)

Derivatives

Hello all. If I have a pair of functions x(t) and y(t) that parameterize a curve C, I know that the derivative ${\frac {dy}{dx}}$ can be given by ${\frac {dy}{dx}}={\frac {\frac {dy}{dt}}{\frac {dx}{dt}}}$. However both ${\frac {dy}{dt}}$ and ${\frac {dx}{dt}}$ will be in terms of t, but ${\frac {dy}{dx}}$ should be in terms of x. How do I get rid of the t in ${\frac {dy}{dx}}$? Thanks. 72.128.95.0 (talk) 18:19, 21 April 2011 (UTC)

Normally, given the level of question this is, by using the x in terms of t relation you had before you differentiated it to give ${\frac {dx}{dt}}$. Grandiose (me, talk, contribs) 18:21, 21 April 2011 (UTC)

x = 1/2 implies y = ±√3/2

It depends on the curve in question. There's no real reason to get rid of the x. Consider the circle parametrised by x(t) = cos(t) and y(t) = sin(t). What's dy/dx when t = 0, i.e. at the point (x,y) = (1,0)? It's not well defined. You can only make sense of dy/dx when dx/dt is non-zero. Even when dx/dt is non-zero you may still have problems. It becomes art at this point. You need to be able to write dy/dx in terms of x(t) and y(t). In the case of the circle, even away from the point (1,0) and (−1,0), you have problems because you can't write y as a function of x. For each value of x, where −1 < x < 1, there are two values of y (see image); one on the upper semi-circle and one on the lower semi-circle. There are two parametrisations:

$y(x)=\pm {\sqrt {1-x^{2}}}\,.$

Where the choice of ± depends on the choice of semi-circle. The expressions for y(x) are valid for −1 ≤ x ≤ 1, but the resulting expressions for dy/dx are only valid for −1 < x < 1. This is hinting at what I told you in a previous post: you can't always globally parametrise manifolds. The two expressions for y(x) above parametrise pieces of the circle, also know as charts. (In this case the circle does have a global parametrisation; just not in terms of y as a function of x, or even x as a function of y.) — Fly by Night (talk) 18:55, 21 April 2011 (UTC)

Before differentiating, try to convert them into a single equation (see: Parametric equation#Conversion from two parametric equations to a single equation). Based on the question, you might try to solve for t (or any other expression involving t you obtain that is relevant, squaring both parametric equations is quite popular but there is not a single method to do this) in the first parametric equation and substitute in the second one. After you convert them into a single equation, ${\frac {dy}{dx}}$ is straightforward. Nimuaq (talk) 19:06, 21 April 2011 (UTC)

But that still doesn't work. Following the link you gave and working out the example, you see that dy/dx = −x/y. For a start, this expression returns values for points (x,y) that aren't even on the curve. You need to solve for y as a function of x and then substitute into the derivative. Secondly, what is the value of dy/dx when y = 0? It's not well defined. The fact is that dy/dx only makes sense over a curve with non-vertical tangent lines. — Fly by Night (talk) 19:18, 21 April 2011 (UTC)

I didn't give any example but if you refer to the example of converting the system to a single equation on the link, dy/dx = −x/y comes from implicit differentiation that comes handy when the equation can not be solved for y in terms of x. It sure is valid only for y ≠ 0 and the downside is it can only be used when the corresponding y value to a certain x is known (the exact pair, since there might be two y values for a certain x value). I think that is what you mean by this expression returns values for points (x,y) that aren't even on the curve, since the pairs should always satisfy the curve equation. It is much more easier to use ${\frac {dy}{dx}}=\pm {\frac {x}{\sqrt {a^{2}-x^{2}}}}$ Nimuaq (talk) 10:38, 22 April 2011 (UTC)

The link you gave links directly to an example in an article. I had already mentioned that one "need[s] to solve for y as a function of x and then substitute into the derivative." The point still remains that the expression for dy/dx is not well defined when x = ±a. There's no point looking for dy/dx because you lose information. That's a point that I hopefully articulated above. In fact working with equations causes more problems that parametrisations. Take for example x² − y² = 0. This has no vertical tangents, but you still have problems with dy/dx; (dy/dx = ±1). What is better is to consider the homogeneous coordinates (dx/dt : dy/dt); see Real projective line. Obviously, if the parametrised curve has no vertical tangent lines then dy/dx is fine to use. — Fly by Night (talk) 13:15, 22 April 2011 (UTC)

King's tour

The number of distinct king's tours on an nXn chessboard for n=1, 2, 3, ... is 1, 24, 784, ... (OEIS sequence A158651). It would help me in another application if I could generate all 784 in the 3X3 case - does anyone know of a non-recursive algorithm to do this?Semiable (talk) 19:53, 21 April 2011 (UTC)

I don't think it would be all that difficult to do by brute force: pick a starting point, pick a second point from the neighboring points not yet chosen, and so on, until you either finish or run out of options. Looie496 (talk) 20:03, 21 April 2011 (UTC)

You can make such an algorithm from depth-first search: when you reach the dead end, go back and check other possible ways. Or you can generate all possible permutations of nine elements (squares) and check each one if it describes a king's tour. --Martynas Patasius (talk) 21:24, 21 April 2011 (UTC)

four(tildes) —Preceding unsigned comment added by 99.38.0.95 (talk) 21:51, 21 April 2011 (UTC)

99, to sign a post, you want to write ~~~~ (that is, you want to press the tilde key four times), not literally write the words "four tildes". 69.111.194.167 (talk) 19:50, 22 April 2011 (UTC)

I tried Looie's way and the program gave all 784 as fast as it could print them. I suspect that generating all 362880 permutations, then rejecting about 99.8% of them by checking that consecutive listed squares are indeed connected, would take rather longer. No matter - I'm not after every way, just one which works in a reasonable time. Thanks.Semiable (talk) 22:08, 22 April 2011 (UTC)

I did some benchmarking on both approaches. The "brute force" method took 0.07 secs, while the "elegant" approach took 0.0002 seconds. So, on my computer, the elegant approach is some 350 times quicker, but both are practically instantaneous. Of course, for boards larger than 3×3, the brute force approach would soon become annoyingly (and then unusably) slow. StuRat (talk) 00:01, 23 April 2011 (UTC)