Wikipedia:Reference desk/Archives/Mathematics/2010 May 4

Mathematics desk
< May 3	<< Apr | May | Jun >>	May 5 >

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.

May 4

Completing rows/columns in a character table

I'm currently trying to complete the character tables of A₆ and S₆. The 7x7 A₆ table is complete except for one ('non-trivial') column, which is entirely blank, except for the top entry, corresponding to the trivial character. My plan of attack would be to use the orthogonality relations to generate six equations, in the six unknown entries of the final column (taking the product of this column with each other column, which must be zero), then solving this system. Is there some simpler trick I'm missing? The problem I'm attempting is from an exam, so I'm assuming there's some time-saving method I'm not seeing.

Similarly, for the 11x11 S₆ table: it is complete except for two rows. I've managed to fill in the first entry of each, corresponding to the trivial conjugacy class, but my plan of attack would be the same: to generate ten equations in the ten unknowns. Again, I'm hoping for some alternative method! Thanks, Icthyos (talk) 12:29, 4 May 2010 (UTC)

Symmetric group characters are easy because they can all be derived from characters induced from the trivial characters on subgroups. In fact you only have to look at the subgroups S₆, S₅×S₁, S₄×S₂, S₄×S₁×S₁, ... . Once you have S₆ you should be able to get nearly all of the A₆ characters by restriction since A₆ has such a low index.

Btw, the character table for S₆ is interesting because it has an unexpected symmetry. This corresponds to the outer automorphism that's unique to S₆ (among symmetric groups).--RDBury (talk) 14:15, 4 May 2010 (UTC)

Ah, thanks a lot. That cuts down the work. For general groups though, if the situation is as I described, is setting up the system of equations and solving them the only sure fire way of completing it? Icthyos (talk) 14:46, 4 May 2010 (UTC)

First, I'm by no means a group theorist so take what I say with a grain of NaCl. In my experience the symmetric groups and related groups are somewhat exceptional because you can get all the representations by inducing trivial representations of subgroups. With other groups it gets trickier because the orthogonality relations only get you so far. There is a theorem (we probably have an article on it but I don't remember the name off hand) that states that any representation is a linear combination of characters induced from cyclic subgroups. As a practical matter though, finding which linear combinations of these characters give you the irreducible characters can be tricky. So I guess my answer to your question for general groups is probably yes, but I never got far enough in group theory to know what they are.--RDBury (talk) 18:14, 4 May 2010 (UTC)

PS. For a real test, try finding character tables for some of the small linear groups, such as psl(2,11). It's order is 660, not that much bigger than the order of A6, but the level of difficulty is much higher.--RDBury (talk) 18:20, 4 May 2010 (UTC)

Brauer's theorem on induced characters is probably the article you want.

You may find James and Liebeck's textbook helpful. S6 is worked out in some detail on pages 201–205 using only the earlier tools: linear characters, tensor products of characters, the permutation character, and orthogonality. In particular, it avoids the exceptionally effective technique of inducing from Young subgroups and using Gram-Schmidt to pull out the irreducibles. A6 is left as an exercise, but a large portion of a chapter is devoted to making this exercise easy: pages 216–220 cover restriction to a normal subgroup of index 2, a very, very important technique. Page 220–222 cover using the table of S5 to get the table of A5. To get the table of A6 is exercise 2. You use (20.13).(1) to see that the restrictions of the characters of S6 of degree 1,5,10,9,5 (and their signed friends) reduce to irreducible characters of A6 of degree 1,5,10,9,5 (only one copy each). The only character left is the one of S6 of degree 16, which you know must restrict to the sum of two Galois conjugate characters of A6 of degree 8. Writing out the character table of A6, I thus need 5 variables to denote the missing values, and each value follows easily from column orthogonality and the definition of the character value (sums of n'th roots of unity, where n is the order of the element). The character values of S6 give me the trace of the numbers, and column orthogonality gives me their (complex) norm. JackSchmidt (talk) 21:30, 4 May 2010 (UTC)

Retrieving the Metric from Christoffel Symbols

Lets say we know the Christoffel Symbols of a geometry in some coordinate system. How does one obtain the metric in terms of its Christoffel Symbols? Thanks.The Successor of Physics 14:09, 4 May 2010 (UTC)

An easy way could be to try to find the Lagrangian that will yield the equations for the geodesic. Count Iblis (talk) 14:43, 4 May 2010 (UTC)

I don't really get what you mean. May you please clarify?The Successor of Physics 15:17, 4 May 2010 (UTC)

The equations for a geodesic are given by

${\frac {d^{2}x^{\mu }}{du^{2}}}+\Gamma _{\rho \sigma }^{\mu }{\frac {dx^{\rho }}{du}}{\frac {dx^{\sigma }}{du}}=0$

But these are also generated by the Lagrangian:

$L={\frac {1}{2}}g_{\mu \nu }{\frac {dx^{\mu }}{du}}{\frac {dx^{\nu }}{du}}$ Count Iblis (talk) 15:52, 4 May 2010 (UTC)

Thanks!The Successor of Physics 13:07, 5 May 2010 (UTC)

Number of conjugacy classes

Suppose G is a non-abelian group of order pq, where p and q are primes such that p divides q - 1. I know that the size of the conjugacy classes of G have to divide pq, and since the group is non-abelian, there are none of size pq. How would I go about finding the number of distinct conjugacy classes of each size? I know from the class equation we must have pq = a + bp + cq = a + bp + c(kp + 1), where a, b and c are the number of classes of each type and k is some integer, but I'm not sure how to go much further. Thanks, Icthyos (talk) 14:58, 4 May 2010 (UTC)

If S is a Sylow q-subgroup of G, then it is necessarily normal (this follows from certain fundamental results in Sylow theory). Furthermore, the size of the conjugacy class of any non-identity element s of S must be p (since the center of G is necessarily trivial, the centralizer of any such s is S). However, any element of G conjugate to s must have order q (since s has order q), and any such element must therefore be in S since S is the (unique) Sylow q-subgroup of G. Consequently, there are precisely ${\frac {q-1}{p}}$ conjugacy classes of size p in G.

Since the center of G is trivial (since I have already used this fact, I shall quickly note that it is equivalent to the statement that the quotient G/Z(G) can never be a non-trivial cyclic group for any finite group G), the class equation yields that there are precisely ${\frac {pq-q}{q}}$ or $(p-1)$ conjugacy classes of size q. (Of course, there is precisely one conjugacy class of size 1, since G is centerless.) Hope this helps (and I hope I have not made any mistakes; I am a bit tired). PST 15:52, 4 May 2010 (UTC)

2x(edit conflict) Not sure how much this will help to compute the conjugacy classes, but note that your assumptions determine the group uniquely up to isomorphism, as follows. Let P and Q be a Sylow p-subgroup and q-subgroup of G, respectively. Since the number m of Sylow q-subgroups divides p < q and is congruent to 1 mod q, the only possibility is m = 1, which means that Q is a normal subgroup of G. (Incidentally, a symmetric argument shows that the assumption that p divides q − 1 can be weakened to just p < q.) Moreover, P and Q are cyclic groups of orders p and q, respectively, and it is easy to see from $Q\trianglelefteq G$ that G is their semidirect product $Q\rtimes _{\varphi }P$. Such a semidirect product is determined by the action $\varphi$ of P on Q (i.e., a homomorphism $\varphi \colon P\to \operatorname {Aut} (Q)$), which has to be nontrivial as G is nonabelian. Since Aut(Q) is a cyclic group of order q − 1, and P is cyclic of order p, there is (up to an automorphism of P) only one nontrivial homomorphism of P to Aut(Q), namely one which sends the generator of P to an element of Aut(Q) of order (q − 1)/p. To sum it up, G is isomorphic to the group consisting of elements (a,b) where $a\in \mathbb {Z} _{q}$, $b\in \mathbb {Z} _{p}$, with multiplication defined by

$(a,b)(c,d)=(a+\xi ^{b}c,b+d),$

where $\xi$ is a fixed primitive pth root of unity in $\mathbb {Z} _{q}$.—Emil J. 15:55, 4 May 2010 (UTC)

It may be worthwhile to supplement a reading of EmilJ's argument with an attempt at the problem of determining the isomorphism classes of groups of order 6 (this corresponds to p=2 and q=3), and in particular, an attempt to determine the non-abelian groups of order 6. PST 16:15, 4 May 2010 (UTC)

Icthyos, you said, "since the group is non-abelian, there are none [conjugacy classes] of size pq". While it is indeed true that there are no conjugacy classes of size pq in G, this follows more directly (and accurately) from the fact that the identity element constitutes a single conjugacy class (that is, the identity element is not conjugate to any non-identity element in G). (With virtually no extra effort, you can establish that no finite group with more than two elements has precisely two conjugacy classes; it is interesting to note that that this is not the case for infinite groups (that is, there do exist infinite groups in which any two non-identity elements are conjugate!).) PST 16:06, 4 May 2010 (UTC)

Thanks PST, that's exactly what I needed. I'd gone down the route of Sylow subgroups (and had in fact shown that your S was normal), but thought I was just stumbling in the dark. Huzzah! Thanks to you too, Emil J - I've seen that sort of thing before, but I'd never have spotted it for this question. Icthyos (talk) 16:33, 4 May 2010 (UTC)

Actually, I have another question: how do we know that there isn't some conjugacy class of size p entirely disjoint from S? You showed that a general element g being conjugate to s shows that g is in S, but how do we know that there isn't a conjugacy class of size p containing no elements of S? I've shown that g being in a conjugacy class of size p implies that the centraliser of g is S...but does that force g to be in S? Icthyos (talk) 19:35, 4 May 2010 (UTC)

Oops, got it - if gs = sg because the centraliser of g is S, then g is also in the centraliser of s, which we have already shown is S! Icthyos (talk) 20:31, 4 May 2010 (UTC)

I thought I might mention the following neat (and basic) result, since it is somewhat relevant to your question (and might interest you if you have not heard of it already). If G is a finite group, the probability that two elements of G chosen at random (with replacement) commute is given by ${\frac {k(G)}{|G|}}$ where k(G) is the number of conjugacy classes in G. Since we have computed k(G) in terms of p and q for non-abelian groups of order pq (where p divides q−1), this formula yields:

$P({\mbox{Two elements chosen at random from G (with replacement) commute}})={\frac {{\frac {q-1}{p}}+p-1+1}{pq}}={\frac {p^{2}+q-1}{p^{2}q}}$

Note that for the fundamental case corresponding to G being the permutation group on three letters, this formula yields the correct value of ${\frac {1}{2}}$. Further information (if you are curious) may be found at this source.PST 04:29, 5 May 2010 (UTC)

Thanks for that; I consider myself a group theorist (in training, admittedly...), so it's quite fun to collect new and interesting facts like that. Icthyos (talk) 10:23, 5 May 2010 (UTC)

Constructible Universe

From the article Constructible Universe:

"An alternate definition, due to Gödel, characterizes each L_(α+1) as the intersection of the powerset of L_α with the closure of L_α under a collection of nine explicit functions."

Does anyone here know what these functions are? JumpDiscont (talk) 17:42, 4 May 2010 (UTC)

Various choices work, for example

${\begin{aligned}F_{1}(u)&=\operatorname {dom} (u)=\{x:\exists y\,\langle x,y\rangle \in u\},\\F_{2}(u)&=\{\langle x,y\rangle \in u:x\in y\},\\F_{3}(u)&=u^{-1}=\{\langle x,y\rangle :\langle y,x\rangle \in u\},\\F_{4}(u)&=\{\langle \langle y,z\rangle ,x\rangle :\langle \langle x,y\rangle ,z\rangle \in u\},\\F_{5}(u,v)&=\{u,v\},\\F_{6}(u,v)&=u-v,\\F_{7}(u,v)&=u\times v.\end{aligned}}$

(This is obviously not the original Gödel's list, as there are only seven of them.)—Emil J. 18:19, 4 May 2010 (UTC)

Also, I'm afraid the article is in error: for some technical reason which I forget, one has to take the intersection of ${\mathcal {P}}(L_{\alpha })$ with the closure of $L_{\alpha }\cup \{L_{\alpha }\}$, rather than just $L_{\alpha }$, under the operations.—Emil J. 18:26, 4 May 2010 (UTC)

Aha, one reason is that the operations take finite sets to finite sets, which means that under the wrong definition we would end up with $L=L_{\omega }=V_{\omega }$. (Putting preventively ω in L₀ wouldn't help, we would get stuck at ω₁ for the same reason again: in general the operations take sets of cardinality <κ to sets of cardinality <κ, for any infinite κ.)—Emil J. 18:30, 4 May 2010 (UTC)

It seems like F_5 takes subsets of L_α to not-necessarily-subsets of L_α.

Do you just restrict F_5 to when u and v are both elements of L_α?

JumpDiscont (talk) 19:42, 4 May 2010 (UTC)

On the other hand, I now realize you said "the intersection of ${\mathcal {P}}(L_{\alpha })$ with the closure", so it wouldn't have to be a subset of L_α.

However, would replacing F_5 with F_8(u) := {u} work?

JumpDiscont (talk) 21:09, 4 May 2010 (UTC)

I doubt it. How would you ever construct {u,v} using singletons and the other operations, if u ≠ v?—Emil J. 12:43, 5 May 2010 (UTC)

Oh, if $u,v\in L_{\alpha }$, then $\{u,v\}=L_{\alpha }-((L_{\alpha }-\{u\})-\{v\})$. Now, this does not quite apply when u,v are only in the closure of $L_{\alpha }\cup \{L_{\alpha }\}$ instead of in $L_{\alpha }$, though at the very least this means the two definitions of $L_{\alpha }$ would catch up for limit α. However, I have gone through the proof and it appears that even with F₅ replaced by {u} it is possible to show that the closure contains Def(L_α), hence it should actually give the correct L_α for all α. (This also prompted me to change the definition of F₄ above, as I don't know how to make the proof work with the original one; the book I copied it from gave the list without a proof, so it may have been a typo.) So, yes, replacing F₅ with {u} works.—Emil J. 15:11, 5 May 2010 (UTC)

request algorithm for vertex-weighted bipartite graph problem

Let D be a (finite) digraph whose underlying graph is bipartite and connected. Assume that the vertices of D are the union of P and N where the only directed edges in D go from vertices in P to those in N. Assume that the vertices V(D) (not edges!) in D have nonzero integral weights and vertices in P have positive weights and those in N have negative weights. Assume also

• (a) the sum of weights over all v in V(D) is zero
• (b) for all p in P, the sum of weights of adjacent vertices to p plus the weight of p is nonnegative
• (c) for all n in N, the sum of weights of incident vertices to n plus the weight of n is nonnegative

Is there an algorithm (other than brute force) to decide if we can redistribute vertex weights by sharing (positive integrally) weights of vertices in P amongst adjacent (negative) weight vertices such that all vertices in D now have zero weight? If so, what is its complexity?

This isn't a homework question! I know of a domain which gives rise to such graphs and the need for the decision algorithm. The domain also gives rise to other graphs where the needed algorithm is for a maximal cardinality matching, with the Hopcroft–Karp algorithm solving the problem, for example, but this seems to be computationally expensive, and worst case all the time, whereas I've reason to believe the requested algorithm would be more efficient, especially as most of the time we do essentially no work as D has only two vertices, so (a) provides a trivial solution. —Preceding unsigned comment added by Puzl bustr (talk • contribs) 19:40, 4 May 2010 (UTC)

Answered my own question: replace vertex of weight W, say, by abs(W) new vertices of weight sign(W) with new edges inherited in the obvious way. This reduces to bipartite matching. Puzl bustr (talk) 12:18, 5 May 2010 (UTC)

Modular forms/eta function

I am currently reading the proof of Proposition 20 on P130 of the "Introduction to Elliptic Curves and Modular Forms" by Koblitz. He defines $g(z)=(\eta (z)\eta (2z))^{8}$ (the $\eta$ function is famous so I imagine if you don't know what it is you can't help maybe, and thus I won't define it) and I understand that its q-expansion about infinity is $q\prod (1-q^{n})^{8}(1-q^{2n})^{8}$ so that g vanishes at infinity. Now, the sentence I do not get, which may be very easy:

"Using the relation $\eta (-1/z)={\sqrt {z/i}}\eta (z)$, we easily see that g(z) vanishes at the cusp 0 as well."

Just to be sure, I understand the relation is just the functional equation for the eta function and I have already gone through the proof of that. I am just not understanding how to use this relation to show that g vanishes at 0 as well. These q-series do not make a lot of sense to me at times. Thanks. StatisticsMan (talk) 20:01, 4 May 2010 (UTC)

Perhaps someone else can add to this if it needs clarification or more rigor. I believe you are supposed to use that relation to get $g(-1/z)=(\eta (-1/z)\eta (-2/z))^{8}=({\sqrt {z/i}}\eta (z){\sqrt {z/2i}}\eta (z/2))^{8}=z^{8}/16(\eta (z)\eta (z/2))^{8}$. The q-expansion of $\eta$ tells us that $\eta$ has a zero of order 1 at infinity (and g has a zero of order 16 at infinity). If you think about plugging in "the point at infinity" for z in the equation above and compare orders of zero, you see that g has a zero of order 8 at z=0.146.186.131.95 (talk) 13:32, 6 May 2010 (UTC)

Actually, this is good. I just wasn't thinking about it this way. I was thinking of taking $\eta (z)$ and transforming it to ${\frac {\eta (-1/z)}{\sqrt {z/i}}}$ and then g has $\eta (-1/z)\eta (-1/2z)$ and I didn't see how to get a q-series out of that. But, what you say is exactly what I needed. Thanks. StatisticsMan (talk) 14:20, 6 May 2010 (UTC)