Following on, in a sense, from the previous post: soon I shall be rid of this turbulent priest, erm, I mean, teaching calculus to 1st year North American students.
(This post brought to you from the Department of Procrastination.)
The post title is from W. H. Auden’s Leap Before You Look — full text at this page.
Years ago it was pointed out to me that the rhyme scheme is
abab bbaa baab abba aabb baba
illustrating rather neatly that “4 choose 2 equals 6”. Note also that the last word of each stanza alternates between “leap” and “disappear”, and that there is a kind of “reflectional symmetry” in the order of the stanzas. Specifically, the transposition of a and b has the effect of reversing the order of the 6 4-tuples.
Hmm, maybe I should try this as an example if I get to teach a course introducing people to finite groups…
Well, that break was longer than intended…
In the last post, we claimed that for every finite, non-abelian group G. It turns out that the easiest way to prove this goes via a certain minorant for which we will work with in some subsequent posts. In this post, we’ll introduce this minorant, give an explicit lower bound, and then briefly indicate how it allows us to show the stronger result that
We can rewrite this in a cosmetic but suggestive way. Observe that the inversion map on G, which sends each element to its inverse, maps conjugacy classes to conjugacy classes. It follows that for each D in Conj(G), the set
also belongs to Conj(G). Moreover, the map is an involution, in particular is bijective. Therefore, since for every character , we obtain
We already saw this idea, in a special case, when we looked at for abelian groups. There, the point of this small change was that it made the expression look more like an inner product, so that one could apply Schur orthogonality relations; a similar idea was applied in a recent paper of Alaghmandan, Samei and myself (arXiv 1302.1929) to handle certain groups which are close to the abelian case in some sense.
2. A remark on normalized versus unnormalized counting measure
First, I need to clear up an issue of normalization conventions, which I omitted to deal with before. In our series of posts, we have always been working on the complex group algebra equipped with the -norm. That is, we are looking at where denotes counting measure on the finite set G.
On the other hand, the paper of Azimifard–Samei–Spronk (henceforth referred to as [ASS09]), where the amenability constant of the centre of the group algebra was first studied, considers where G is a compact group and denotes uniform probability measure on G.
However, there is no serious conflict. For if G is a finite group, let A denote equipped with counting measure and equipped with convolution using , and let B denote equipped with uniform probability measure and equipped with convolution using . Then a direct calculation shows that the obvious isometric rescaling map from A to B is in fact an isomorphism of Banach algebras. In particular, A and B have the same amenability constant. Thus, our formula from coincides with the formula in [ASS09] for the amenability constant of .
3. A minorant for
At a naive level (but not a completely facile one) we might say that the difficulty in getting non-trivial lower bounds on is due to the fact that one takes the modulus of a sum of different terms, inside which there might be significant cancellation. Indeed, this is exactly what happens in the case of an abelian group: see the previous post for details.
One situation where we can avoid cancellation is where the terms in the sum are all non-negative, so that the modulus is just the sum itself. Looking at the revised formula for , we see that this happens whenever C=D (it may also happen for some other choices of C and D, but let us ignore that for now). Moreover, if we only want a lower bound on and not its precise value, we are free to discard terms indexed by particular C and D. Thus, as observed in [ASS09], is bounded below by the following quantity
(The paper [ASS09] does not give this quantity a specific symbol, but in subsequent posts it will appear frequently enough that some extra notation seems warranted.)
In the previous post, we claimed that if G is a non-abelian finite group then we have > 1. We can now give a sharper statement. (The calculation in [ASS09] does not give the explicit bound that we do, but it is implicit in their work.)
Proof: Compare the formula (1) which defines with
Rearranging the sum and using the Schur row and column orthogonality relations, we see that (2) is equal to
Now all of the terms on the right hand side are non-negative. Some of them may be zero (for instance, whenever C consists of just a single point, or whenver ) but we can identify at least one strictly positive term. Namely, let be a conjugacy class of size s, and consider the trivial character which takes the value 1 everywhere. Then
which gives us the lower bound that was claimed.
Note that our lower bound “gets worse” as G gets bigger. Indeed, I believe the following question is still open.
Question. Is the infimum of over all finite non-abelian groups G strictly greater than 1?
Nevertheless, as mentioned in the first post of this series, we can do better when it comes to , which is the original quantity of interest. This was done in [ASS09] by appealing to a hard result of D. A. Rider, which tells us that the norms of central idempotents have “a gap at 1”.
Theorem 2 (Rider, 1973) Let K be a compact group, let E be a finite subset of Irr(K), and let . (The orthogonality relations for irreducible characters imply that is a central idempotent in , and all central idempotents in arise this way.) If , then .
Now let G be a finite, non-abelian group. Since , Proposition~1 immediately implies that . Now , where is a central idempotent in . Applying Rider’s theorem to we deduce, as in [ASS09], that .
Rider’s proof is rather long and technical and we will not present the details here. The constant 301/300 is somewhat arbitrary, resulting from choices made in chains of estimates, and can be improved slightly by repeating Rider’s arguments with more nit-picking. However, it seems that a significant improvement in the constant would require new ideas.
the next a future post, we will see that with a more careful use of the Schur orthogonality relations, one can improve the lower bound in Proposition~1 to a constant that does not depend on |G|, provided that G has trivial centre. To do this we will need a new ingredient, not available in [ASS09], which ensures that a group which has an irreducible character of “surprisingly large” degree cannot have any small conjugacy classes except for elements of the centre.
Edited 2013-06-17: corrected some typos/omissions.
Edited 2014-12-30: revised rash promise.
OK, back to the story of the central amenability constant. I’ll take the opportunity to re-tread some of the ground from the first post.
Given a finite group G, denotes the usual complex group algebra: we think of it as the vector space equipped with a suitable multiplication. This has a canonical basis as a vector space, indexed by group elements: we denote the basis vector corresponding to an element x of G by . Thus for any function , we have .
(Aside: this is not really the correct “natural” way to think of the group algebra if one generalizes from finite groups to infinite groups; one has to be more careful about whether one is thinking “covariantly or contravariantly”. is naturally a contravariant object as G varies, but the group algebra should be covariant as G varies. However, our approach allows us to view characters on G as elements of the group algebra, which is a very convenient elision.)
The centre of , henceforth denoted by , is commutative and spanned by its minimal idempotents, which are all of the form
for some irreducible character . Moreover, is a bijection between the set of irreducible characters and the set of minimal idempotents in .
and, equipping with the natural -norm, defined by
we define to be . Explicitly, if we use the convention that the value of a class function on any element of a conjugacy class C is denoted by , we have
the formula stated in the first post of this series.
2. Moving onwards
As I am writing these things up, it occurs to me that “philosophically speaking”, perhaps one should regard as an element of the group algebra , where Gop denotes the group whose underlying set is that of G but equipped with the reverse multiplication. It is easily checked that a function on is central as an element of if and only if it is central as an element of the algebra , so we can get away with the definition chosen here. Nevertheless, I have a suspicion that the picture is somehow the “right” one to adopt, if one wants to put the study of into a wider algebraic context.
is a non-zero idempotent in a Banach algebra, so it follows from submultiplicativity of the norm that . When do we have equality?
Theorem 2 (Azimifard–Samei–Spronk) if and only if G is abelian.
The proof of necessity (that is, the “only if” direction) will go in the next post. In the remainder of this post, I will give two proofs of sufficiency (that is, the “if” direction).
In the paper of Azimifard–Samei–Spronk (MR 2490229; see also arXiv 0805.3685) where I first learned of , this direction is glossed over quickly, since it follows from more general facts in the theory of amenable Banach algebras. I will return later, in Section 2.2, to an exposition of how this works for the case in hand. First, let us see how we can approach the problem more directly.
2.1. Proof of sufficiency: direct version
Suppose G is abelian, and let . Then G has exactly n irreducible characters, all of which are linear (i.e. one-dimensional representations, a.k.a. multiplicative functionals). Denoting these characters by , we have
This sum can be evaluated explicitly using some Fourier analysis — or, in the present context, the Schur column orthogonality relations. To make this a bit more transparent, recall that for all characters and all y in G. Hence by a change of variables in the previous equation, we get
For a fixed element x in G, the n-tuple is a column in the character table of G. We know by general character theory for finite groups that distinct columns of the character table, viewed as column vectors with complex entries, are orthogonal with respect to the standard inner product. Hence most terms in the expression above vanish, and we are left with
which equals , since each takes values in . This completes the proof.
The following argument is an expanded version of the one that is outlined, or alluded to, in the paper of Azimifard–Samei–Spronk. It is part of the folklore in Banach algebras — for given values of “folk” — but really the argument goes back to the study of “separable algebras” in the sense of ring theory.
Lemma 3 Let A be an associative, commutative algebra, with identity element 1A. Let be the linear map defined by . Then there is at most one element m in that simultaneously satisfies =1A and for all a in A.
Proof: Let us first omit the assumption that A is commutative, and work merely with an associative algebra that has an identity.
Define the following multiplication on :
Then is an associative algebra — the so-called enveloping algebra of A. If m satisfies the conditions mentioned in the lemma, then
and so, by taking linear combinations, for every w in . If n is another element of satisfying the conditions of the lemma, we therefore have nm=m, and by symmetry, mn=n.
Now we use the assumption that A is commutative. From this assumption, we see that is also commutative. Therefore
Now let G be a finite group and let A= . Because A is spanned by its minimal idempotents , and because minimal idempotents in a commutative algebra are mutually orthogonal, satisfies the two conditions mentioned in Lemma 3. On the other hand, if G is abelian, consider
Clearly =1A, and a direct calculation shows that for all g in G, so by linearity also satisfies both conditions mentioned in Lemma 3. Applying the lemma tells us that , and in particular
I am a bit suprised and disappointed to see that the online maths communities I lurk around seem largely oblivious to this recent preprint 1306.3969. Here is the abstract: the added emphasis is mine.
We use the method of interlacing families of polynomials to prove Weaver’s conjecture KS2, which is known to imply a positive solution to the Kadison-Singer problem via Anderson’s Paving Conjecture. Our proof goes through an analysis of the largest roots of a family of polynomials that we call the “mixed characteristic polynomials” of a collection of matrices.
(A few years ago, the 2nd and 3rd authors of that preprint recently made a dramatic improvement in our understanding of a theorem of Bourgain and Tzafriri, see arXiv 0911.1114. So this paper is certainly worth taking seriously at the very least.)
Over on G+, Willie Wong quite sensibly asked for some brief explanation of what the problem said, and why people care(d). I must confess that the full background to the Kadison-Singer conjecture/problem is well outside my area of technical expertise, possibly outside my area of competence. Nevertheless, I can at least link to this article by Casazza and Tremain, which mentions some other conjectures in functional analysis that are known to be equivalent to the Paving Conjecture, and hence (by work of Anderson) to the Kadison-Singer conjecture.
P. G. Casazza, J. C. Tremain. The Kadison–Singer Problem in mathematics and engineering. PNAS vol. 103 (2006) no. 7, 2032–2039
Here is a link to some web material for an AIM workshop on the Kadison-Singer problem, which may give the general audience some idea of work in recent years.
The paper of Weaver which the preprint refers to is:
The MathReview of Weaver’s paper, by P. J. Stacey, is short enough that it can be reproduced here:
In [Amer. J. Math. 81 (1959), 383–400; MR0123922 (23 #A1243)], R. V. Kadison and I. M. Singer asked if every pure state on an atomic maximal abelian subalgebra of B(H), the algebra of bounded operators on a separable Hilbert space H, extends uniquely to a pure state on B(H). Developing the approach in [C. A. Akemann and J. Anderson, Mem. Amer. Math. Soc. 94 (1991), no. 458, iv+88 pp.; MR1086563 (92e:46113)], the author formulates a combinatorial version of the Kadison-Singer problem, in terms of unit vectors in Ck. Some positive partial results are then obtained using discrepancy theory.
Perhaps I will keep this blog post updated with some more links, if anyone has suggestions. Though really it should be left to the operator theorists, operator algebraists, and combinatorists to write some expositions in the weeks to come.
I see there is some attention now that Terence Tao has mentioned this on G+ and thence on the Selected Papers Network. (I admit that when I mentioned the paper on G+, I didn’t tag it with #spnetwork, mainly because I didn’t feel I had anything intelligent to say at the time; and if this #spnetwork is to become useful to the community of research mathematicians, it needs less noise from spectators, and more commentary from people who understand some ideas in the papers under discussion!)
Gil Kalai has a blogpost which says a little more about how the paper of Marcus, Spielman and Srivastava relates to the previous results of Bourgain and Tzafriri, and mentions that Spielman and Srivastava had previously given a new proof – an improved proof? – of Bourgain-Tzafriri’s restricted invertibility theorem.
Orr Shallit has also picked up on this, and offers some thoughts from the perspective of an operator algebraist/operator theorist.
As promised in the previous blogpost, here is some finite group theory. (Those of you familiar with the British TV show “Faking It” will appreciate that you don’t have to fool all of the people all of the time, just some of the people at the right moments.)
Some preliminary terminology is useful, since we will need it in later posts. We say that H is (isomorphic to) a proper quotient of a group G if there is a homomorphism from G onto H which has non-trivial kernel. A group G is said to be just non-abelian (or JNA or short) if it is non-abelian, yet every proper quotient is abelian. A little thought shows that this is equivalent to the condition that the derived subgroup [G,G] is contained in each non-trivial normal subgroup of G.
(I don’t remember explicitly hearing about JNA groups in past courses or talks, but about seven years ago in Newcastle I heard a visiting speaker talk about families of groups that were “just-” for some property .)
Doing some digging in the literature: in the case where the group G is JNA and [G,G] is abelian, there is a classification or structure theorem available, through work of M. F. Newman in two papers that appear in the Proceedings of the London Mathematical Society (both in volume 10, 1960). Later on, when we resume the story of the central amenability constant, JNA groups will turn up very naturally. However, none of that is needed to follow the proof of the following result:
Theorem 1. Let G be a finite JNA group which has trivial centre and which has a conjugacy class of size 2. Then G contains an involution and an element of odd prime order p, such that G has order 2p and .
Up to isomorphism, the only group satisfying the conclusions of the theorem is the dihedral group of order 2p. (Checking that this group actually is JNA is not too difficult, but I won’t go into the details here.)
Remark. In any finite group with a conjugacy class of size 2, both elements in the conjugacy class have the same centralizer — this point will be reiterated below in a little more detail — and this centralizer has index 2 in the parent group, hence is normal. This is encouraging in our setting, since the JNA condition now gives us extra information.
A leisurely proof
The purpose of this post is to provide a proof of Theorem 1 that uses only basic facts of finite group theory, such as may be found in a first course that covers notions such as conjugacy classes and normal subgroups.
We recall that the derived subgroup of G, sometimes called the commutator subgroup of G, is the subgroup of G generated by all elements of the form as vary over G. (For those who prefer to think categorically, [G,G] is uniquely determined by the property that it is contained in the kernel of every homomorphism from G to any abelian group, i.e. it is the kernel of the abelianization homomorphism.)
Now in Theorem 1, the hypotheses on G are as follows:
- there exists G with exactly one other conjugate,
- If N is a non-trivial normal subgroup of G, then every commutator belongs to N.
It is immediate from Condition 2 that any given G either centralizes both and , or else swaps them (this is true for any group action on any 2-point set, of course). More formally:
Lemma 2. Let G. Either and , or and .
In particular, this lemma implies that , i.e. and commute. Applying the lemma to shows that for all in G, and so by Condition 1 we must have
Let N be the order of : this is an integer . If N were even, say N=2m, then , and applying Lemma 2 we would find that Z(G), which contradicts Condition 1. Therefore N is odd.
Because has odd order, this implies that , and so [G,G] contains the subgroup of G generated by , which we denote by . On the other hand, observe that since , Lemma 2 implies that is a normal subgroup of G. Therefore, by Condition 3,
Let H be the centralizer in G of the element (and hence, as remarked above, of the element ). We know that H has index 2 in G (by applying the orbit-stabilizer theorem to the conjugation action of G on ). At this point we could now invoke the general fact that index 2 subgroups of any group are necessarily normal subgroups. To keep things self-contained, we instead use some ad hoc arguments (although this admittedly leaves out the bigger picture which motivates our calculations).
Lemma 3. Let G. Then either or belongs to H.
Proof: If belongs to G but not H, then does not lie in H, and so by Lemma 2. So and rearranging shows that centralizes .
Moreover, by definition H contains . Hence it contains [G,G], by Equation (2). The next step in our argument is to show that in fact H=[G,G].
Digression. At this point, if we just wanted to proceed as quickly as possible, we could appeal to Theorem 3.4 of
M. F. Newman, On a class of metabelian groups. Proc. London Math. Soc. (3) 10 1960 354–364. MR0117293 (22 #8074)
Indeed, this point is where I’d originally got stuck on my first attempt to prove the theorem, and I has to resort to Newman’s paper to check that what I was hoping to prove was actually true. Nevertheless, it seems worth giving an ad hoc argument using only “bare-hands techniques”, since we are in a much more specialized setting than that covered by Newman’s theorem. What follows is my own argument, found by some trial and error after I had used Newman’s paper to check I was on the right lines.
Proof that H=[G,G]
Consider the function θ : H [G,G] defined by . Since [G,G]= is contained in Z(H), for all H we have
in other words, θ is a homomorphism. Our goal is to show θ is a bijection, which will force H and [G,G] to have the same cardinality. Since we already know that [G,G] is contained in H, we can conclude that [G,G]=H as required.
First, we show θ is surjective. Note that , so if we let m=(N+1)/2 and k be any integer, induction (or the fact θ is a homomorphism) implies that . Since [G,G]=, this shows θ(H)=[G,G].
Secondly, we show θ is injective. Let K=, which is a normal subgroup of H (being the kernel of a homomorphism). Note that K=. It now follows from Lemma 3 that K is normal as a subgroup of G. Suppose K is not the trivial subgroup; then by Condition 3, K contains [G,G], and in particular belongs to K. But since (Equation (1)) we have
(since ) and we get a contradiction. Therefore K is the trivial subgroup, and θ:H[G,G] is indeed injective.
Continuing the proof of Theorem 1
Let us take stock. We have shown that there exist elements G such that:
- (this follows from Equation (1) and the choice of );
- has odd order, say N (this follows from the remarks after Equation (1));
- is an index 2 subgroup in G (this follows from Equation (2) and the result just proved).
This is close to what is needed: it only remains to show that and that N is prime.
We will show that belongs to the centre of G, which combined with Condition 1 forces . To do this, first observe that by Lemma 2, centralizes , and hence centralizes . But since is an index 2 subgroup of G and , every element of G belongs to either or , from which it follows that centralizes everything in G, as required.
Remark. The argument just given seems the quickest way to do things, given what we have already shown to date. However, it relies on knowing that has index 2 in G. It may be of some interest to note that one can show centralizes G more directly, using only Equations (1) and (2). Thus, let G}. By Equation (2), there exists some integer k such that
Since , it follows that
and so . Rearranging gives
so that . Since is arbitrary in G, belongs to the centre of G.
Finally, to finish things off, it suffices to show that N is prime. Let p be a prime factor of N. Then is a proper subgroup of , and it is normal in G by Equation (1), since . Condition 3 therefore forces , and so N=p. This completes the proof of Theorem 1.
Well, having already been drenched on the way into work today, I am now stuck in my office as I wait for a lull in the rainstorm. So I guess I should put the time to use, and a blog post is as good as any right now.
This continues from the previous post. I’ll also continue the experiment of writing things up in an anecdotal style, rather than in the mode of a presentation or paper — the aim is not to present the outcome as quickly or cleanly as possible, but to give an account of its evolution. Apologies if it proves tedious, irksome, or outright Pooterish.
This is also my first attempt at using the LaTeX-to-Wordpress script written by Luca Trevisan, which has saved me a certain amount of teeth-grinding when fighting WP’s limited LaTeX support.
A few weeks after writing the previous post, I was at a rather enjoyable conference in Granada where I spent some time, on and off during lulls in the conference schedule, reconstructing the proof of the lower bound 4/3, from memory while away from my books. Annoyingly, the 4/3 comes as the limiting value of a weak lower bound, in one branch of a case-by-case analysis, but in a branch where known results suggest the true value of the amenability constant should be at least 2. (In the other branch of the analysis, one is led to 7/4 and knows that this is sharp.)
Without going into details about how the case-by-case analysis works, let’s just say that for all finite groups G in a certain class , the method in question yields a lower bound
However, for various speculative reasons (well, guesswork) it seemed likely that for all
In fact, the existing method already implied that whenever and all non-central conjugacy classes have size at least 3. This got me thinking about what one could say about those which had a conjugacy class of size 2 in the group, since — as part of the small amount of finite group theory that I remembered from my undergraduate days — this ensures G has a normal subgroup of index 2, from which one might try to play games with induction or restriction of characters.
Fast-forward to June. About a week ago, shortly after getting back to Saskatoon, some idle tweaking done while waiting for food showed that the method used to get the 4/3 bound could be modestly improved by a slightly more careful use of various inequalities. The improved method still only gave
but it did now show that whenever and all its non-central conjugacy classes have size at least 3.
The upshot? To prove that for all , one now only needed to do it for those which had a conjugacy class of size 2. Moreover, the calculations I’d been doing in Granada hinted strongly that any such group would be forced to be something like a dihedral group of order 2 mod 4, and in my earlier paper with Alaghmandan and Samei, we had already calculated the exact values of for dihedral groups, showing that in the 2 mod 4 case this constant is at least 7/3.
So, at this point, you naturally go and ask a group theorist. On the other hand, since none were at hand, and since the question seemed a little basic to throw on MathOverflow without having a more serious go on one’s own…
… and it works. To be precise for a moment, here is what I was able to show last week.
Theorem 1 Let G be a finite group which has trivial centre, and where every proper quotient is abelian. If G has a conjugacy class of size 2, then it is isomorphic to the dihedral group of order 2p for some odd prime p.
Well, assuming there isn’t a mistake, for many of you this is probably like watching a young child come up to you proudly to show you their latest kindergarten handiwork. I have a strong suspicion that this result is already known, perhaps implicitly, or as one of those folklore exercises that is set in Proper Courses for Proper Students. Certainly, in the argument I have right now, one shows en route that G is solvable, whereupon one can invoke a classification of “just non-abelian, metabelian groups” due to M. F. Newman.
On the other hand, since it turns out that one can prove the theorem using only what one learns in a first course on finite group theory, my plan is to write up the proof in the next blog post in this series.
(The rain has stopped.)