Is Fourier analysis a special case of representation theory or an analogue? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T22:31:00Z http://mathoverflow.net/feeds/question/37021 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue Is Fourier analysis a special case of representation theory or an analogue? David Corwin 2010-08-29T03:47:43Z 2012-12-06T00:36:58Z <p>I'm asking this question because I've been told by some people that Fourier analysis is "just representation theory of $S^1$."</p> <p>I've been introduced to the idea that Fourier analysis is related to representation theory. Specifically, when considering the representations of a finite abelian group $A$, these representations are all $1$-dimensional, hence correspond to characters $A \to \mathbb{R}/\mathbb{Z} \cong S^1 \subseteq \mathbb{C}$. On the other side, finite Fourier analysis is, in a simplistic sense, the study of characters of finite abelian groups. Classical Fourier analysis is, then, the study of continuous characters of locally compact abelian groups like $\mathbb{R}$ (classical Fourier transform) or $S^1$ (Fourier series). However, in the case of Fourier analysis, we have something beyond characters/representations: We have the Fourier series / transform. In the finite case, this is a sum which looks like $\frac{1}{n} \sum_{0 \le r &lt; n} \omega^r \rho(r)$ for some character $\rho$, and in the infinite case, we have the standard Fourier series and integrals (or, more generally, the abstract Fourier transform). So it seems like there is something more you're studying in Fourier analysis, beyond the representation theory of abelian groups. To phrase this as a question (or two):</p> <p>(1) What is the general Fourier transform which applies to abelian and non-abelian groups?</p> <p>(2) What is the category of group representations we consider (and attempt to classify) in Fourier analysis? That is, it seems like Fourier analysis is more than just the special case of representation theory for abelian groups. It seems like Fourier analysis is trying to do more than classify the category of representations of a locally compact abelian group $G$ on vector spaces over some fixed field. Am I right? Or can everything we do in Fourier analysis (including the Fourier transform) be seen as one piece in the general goal of classifying representations?</p> <p>Let me illustrate this in another way. The basic result of Fourier series is that every function in $L^2(S^1)$ has a Fourier series, or in other words that $L^2$ decomposes as a (Hilbert space) direct sum of one dimensional subspaces corresponding to $e^{2 \pi i n x}$ for $n \in \mathbb{Z}$. If we encode this in a purely representation-theoretic fact, this says that $L^2(S^1)$ decomposes into a direct sum of the representations corresponding to the unitary characters of $S^1$ (which correspond to $\mathbb{Z}$). But this fact is not why Fourier analysis is interesting (at least in the sense of $L^2$-convergence; I'm not even worrying about pointwise convergence). Fourier analysis states furthermore an <em>explicit</em> formula for the function in $L^2$ giving this representation. Though I guess by knowing the character corresponding to the representation would tell you what the function is.</p> <p>So is Fourier analysis merely similar to representation theory, or is it none other than the abelian case of representation theory?</p> <p>(Aside: This leads into a more general question of mine about the use of representation theory as a generalization of modular forms. My question is the following: I understand that a classical Hecke eigenform (of some level $N$) can be viewed as an element of $L^2(GL_2(\mathbb{Q})\ GL_2(\mathbb{A}_{\mathbb{Q}})$ which corresponds to a subrepresentation. But what I don't get is why the representation tells you everything you would have wanted to know about the classical modular form. A representation is nothing more than a vector space with an action of a group! So how does this encode the information about the modular form?)</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/37031#37031 Answer by Yemon Choi for Is Fourier analysis a special case of representation theory or an analogue? Yemon Choi 2010-08-29T07:19:02Z 2010-08-30T00:02:55Z <p>Since David's asked or suggested that some remarks be written up as an answer, let me repeat what I said in the comments:</p> <ul> <li><p>in my opinion, the answer to the question in the title is "neither";</p></li> <li><p>my answer to Q1 would be "look up Fourier transform and noncommutative harmonic analysis" - if one is only interested in compact groups then there is a very satisfactory theory, outlined in Hewitt &amp; Ross volume 2 for example;</p></li> <li><p>and my answer to Q2 would be "not applicable - the question is founded on a debatable premise".</p></li> </ul> <p>Actually, in the middle of the salvo that he's labelled as "Question 2", David asks</p> <blockquote> <p>That is, it seems like Fourier analysis is more than just the special case of representation theory for abelian groups. It seems like Fourier analysis is trying to do more than classify the category of representations of a locally compact abelian group $G$ on vector spaces over some fixed field. Am I right?</p> </blockquote> <p>and in my inexpert opinion, the answer is "yes". Why would it be 'just' a subtopic of the enterprise of classifying representations?</p> <hr> <p><b>Update:</b> to elaborate on my objections to the original questions, while not taking anything away from the informative comments and answers that other people have given: <em>there is more to Fourier analysis than constructing a Fourier transform between certain topological vector spaces and getting a Plancherel formula</em>. Hence being able to construct a generalization or analogue of the Fourier transform for nonabelian locally compact groups is not the be all and end all of the topic, unless the topic is "constructing a nonabelian Fourier transform". Looking in the literature on harmonic analysis, even in the abelian case, ought to bear this out.</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/37071#37071 Answer by Theo Johnson-Freyd for Is Fourier analysis a special case of representation theory or an analogue? Theo Johnson-Freyd 2010-08-29T17:48:56Z 2010-08-30T03:08:03Z <p>This answer is essentially a comment, but slightly too long.</p> <p>As someone who is closer to representation theory than analysis, to me the word "Fourier analysis" means "Pontrjagin duality". You hint at this theorem in your question, but I will state (a version of) it for completeness:</p> <p><strong>Theorem:</strong> Let $G$ be a locally-compact topological abelian group. A <em>character</em> is a continuous homomorphism $G \to \mathbb S^1$ the circle. The set $G^\vee$ of characters is naturally an abelian group under $\otimes$, and has a canonical topological structure in which it is locally compact. The canonical pairing $G \times G^\vee \to \mathbb S^1$ induces a map $G \to (G^\vee)^\vee$, which is an isomorphism.</p> <p>A good reference is:</p> <ul> <li>André Joyal, Ross Street. An introduction to Tannaka duality and quantum groups. <em>Category Theory, Lecture Notes in Math</em>. 1991 vol. 1488 pp. 412–492.</li> </ul> <p>They describe the relationship between Pontrjagin duality and Fourier theory as a warm-up for various forms of Tannaka-Krein theory, which can be thought of as a "noncommutative" analogue of Pontrjagin duality.</p> <hr> <p>Incidentally, just as there are questions that Fourier analysts care about that aren't "just" representation theory of abelian groups, there are questions in the representation theory of abelian groups that aren't "just" Pontrjagin duality. For example, given a fixed vector space $V$, the collection of sets of $n$ commuting matrices $V \to V$ is naturally the same as the collection of representations of $\mathbb Z^n$ on $V$, i.e. $\operatorname{Hom}(\mathbb Z^n \to \operatorname{End}(V))$. Now, $\operatorname{GL}(V)$ acts on $\operatorname{End}(V)$ and hence on $\operatorname{Hom}(\mathbb Z^n \to \operatorname{End}(V))$ by conjugation. The corresponding moduli problem &mdash; find the moduli space of $n$ commuting matrices of fixed dimension &mdash; is hard, although I think it's solved.</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/37078#37078 Answer by Dick Palais for Is Fourier analysis a special case of representation theory or an analogue? Dick Palais 2010-08-29T19:43:25Z 2010-08-29T20:06:26Z <p>First, I think it is better to restrict the term "Fourier Analysis" to refer to the process of expanding functions on a locally compact ABELIAN group $G$ as a "sum'' of the characters of the group. (I'll come back to that in a moment.) The generalization, when the group $G$ is not assumed to be abelian, should probably be better referred to as Harmonic Analysis". Regarding the latter, if the group $G$ is compact, then the Peter-Weyl Theorem gives an elegant and simple generalization to the theory of Fourier Series on the circle group---it shows how to write any $L^2$ function on $G$ as an series of (orthogonal) matrix elements of irreducible unitary representations of $G$. When $G$ is neither abelian nor compact, the theory becomes MUCH more complicated and sophisticated. BTW, note that when $G$ is abelian, then as you pointed out, the irreducble unitary representaions of $G$ are one-dimensional, so there is no difference between a matrix element and a character in this case and we are generalizing Fourier series on the circle group.</p> <p>OK, lets now restrict to the Fourier" case, where $G$ is locally compact and abelian. Note that an irreducible unitary character of $G$ is now just a group homomorphism of $G$ into the circle group $S= S^1$ (considered as the complex numbers of modulus one under multiplication). Since $G$ is abelian, the set $\hat G = Hom(G,S)$ is an abelian group, the character (or Pontrjagin dual) group of $G$, under pointwise multiplication. It is easy to see that $\hat G$ is locally compact (in the compact open topology) What Fourier analysis becomes in this case is a method for expressing an arbitrary element of $L^2(G)$ as an integral of the form $f(g) \sim \int \hat f(\chi)\chi(g) d\chi$, where $\hat f$, the Fourier transform of $f$ is defined dually by $\hat f(\chi) = \int f(g) \chi(g) dg$ (and the Haar measures on $G$ and $\hat G$ are suitably normalized). Note that if we take for $G$ the real line $R$ then this reduces to the classical Fourier transform. It is easy to show that the integral defining the Fourier transform $\hat f(\chi)$ is convergent when $f$ is in $L^1 \cap L^2$ and that then $||\hat f||_2 = ||f||_2^2$, and since $L^1 \cap L^2$ is dense in $L^2$ it follows that the Fourier transform extends uniquely to a unitary map of $L^2(G)$ onto $L^2(\hat G)$.</p> <p>Now lets restrict further to the compact case, where characters, being continuous, are bounded and so integrable. As one can prove in a couple of lines (using the invariance of Haar measure), if $\chi$ is any character of $G$ then $\int \chi(g)\, dg = 0$ unless $\chi$ is the identity character in which case the integral is one (using normalized Haar measure on $G$). Since the complex conjugate of a character is its inverse in $\hat G$, it now follows trivially that the elements of $\hat G$ are orthonormal. In fact they form an orthonormal basis for $L^2(G)$, and the Fourier transform of the preceding paragraph becomes a formula for expanding any element of $L^2(G)$ as the sum of an infinite series in the characters of $G$, a direct generalization of the theory of Fourier series (the case when $G = S$).</p> <p>A good place to see all the details is Lynn Loomis' "Absract Harmonic Analysis". </p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/37098#37098 Answer by Kimball for Is Fourier analysis a special case of representation theory or an analogue? Kimball 2010-08-29T23:42:14Z 2010-08-29T23:42:14Z <p>As a complement to the other answers, the (Selberg or Arthur-Selberg) trace formula can be viewed as a generalization of Poisson summation. Harish-Chandra also generalized the Plancherel formula. Both of these can be carried out for connected reductive Lie groups and are important in representation theory. </p> <p>From this point of view, it is perhaps more evident what one should expect of a generalized Fourier transform, and its role is played by the Harish-Chandra/Selberg transform. For the simplest (but not really so simple) non-abelian case, see Iwaniec's "Spectral Theory of Automorphic Forms." </p> <p>As for what other groups one might be able to do this for, one can at least do the trace formula for finite groups (which can be viewed as a generalization of Frobenius reciprocity, cf. Arthur's "Trace formula and Hecke operators"---Arthur also has a Notices article which discusses the general Plancherel formula and Langlands' program), and perhaps it's not too hard to see what a generalization of the Fourier transform should be in nonabelian cases, but I'd need to think about it.</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/37189#37189 Answer by Emerton for Is Fourier analysis a special case of representation theory or an analogue? Emerton 2010-08-30T19:40:03Z 2010-08-31T14:28:48Z <p>I would like to elaborate slightly on my comment. First of all, Fourier analysis has a very broad meaning. Fourier introduced it as a means to study the heat equation, and it certainly remains a major tool in the study of PDE. I'm not sure that people who use it in this way think of it in a particularly representation-theoretic manner.</p> <p>Also, when one thinks of the Fourier transform as interchanging position space and frequency space, or (as in quantum mechanics) position space and momentum space, I don't think that a representation theoretic view-point necessarily need play much of a role.</p> <p>So, when one thinks about Fourier analysis from the point of view of group representation theory, this is just one part of Fourier analysis, perhaps the most foundational part, and it is probably most important when one wants to understand how to extend the basic statements regarding Fourier transforms or Fourier series from functions on $\mathbb R$ or $S^1$ to functions on other (locally compact, say) groups.</p> <p>As I noted in my comment, the basic question is: how to decompose the regular representation of $G$ on the Hilbert space $L^2(G)$. When $G$ is locally compact abelian, this has a very satisfactory answer in terms of the Pontrjagin dual group $\widehat{G}$, as described in Dick Palais's answer: one has a Fourier transform relating $L^2(G)$ and $L^2(\widehat{G})$. A useful point to note is that $G$ is discrete/compact if and only if $\widehat{G}$ is compact/discrete. So $L^2(G)$ is always described as the Hilbert space direct integral of the characters of $G$ (which are the points of $\widehat{G}$) with respect to the Haar measure on $\widehat{G}$, but when $G$ is compact, so that $\widehat{G}$ is discrete, this just becomes a Hilbert space direct sum, which is more straightforward (thus the series of Fourier series are easier than the integrals of Fourier transforms).</p> <p>I will now elide Dick Palais's distinction between the Fourier case and the more general context of harmonic analysis, and move on to the non-abelian case. As Dick Palais also notes, when $G$ is compact, the Peter--Weyl theorem nicely generalizes the theory of Fourier series; one again describes $L^2(G)$ as a Hilbert space direct sum, not of characters, but of finite dimensional representations, each appearing with multiplicity equal to its degree (i.e. its dimension). Note that the set over which one sums now is still discrete, but is not a group. And there is less homogeneity in the description: different irreducibles have different dimensions, and so contribute in different amounts (i.e. with different multiplicities) to the direct sum.</p> <p>When G is locally compact but neither compact nor abelian, the theory becomes more complex. One would like to describe $L^2(G)$ as a Hilbert space direct integral of matrix coefficients of irreducible unitary representations, and for this, one has to find the correct measure (the so-called Plancherel measure) on the set $\widehat{G}$ of irreducible unitary representations. Since $\widehat{G}$ is now just a set, a priori there is no natural measure to choose (unlike in the abelian case, when $\widehat{G}$ is a locally compact group, and so has its Haar measure), and in general, as far as I understand, one doesn't have such a direct integral decomposition of $L^2(G)$ in a reasonable sense.</p> <p>But in certain situations (when $G$ is of "Type I") there is such a decomposition, for a uniquely determined measure, so-called Plancherel measure, on $\widehat{G}$. But this measure is not explicitly given. Basic examples of Type I locally compact groups are semi-simple real Lie groups, and also semi-simple $p$-adic Lie groups.</p> <p>The major part of Harish-Chandra's work was devoted to explicitly describing the Plancherel measure for semi-simple real Lie groups. The most difficult part of the question is the existence of atoms (i.e. point masses) for the measure; these are irreducible unitary representations of $G$ that embed as subrepresentations of $L^2(G)$, and are known as "discrete series" representations. Harish-Chandra's description of the discrete series for all semi-simple real Lie groups is one of the major triumphs of 20th century representation theory (indeed, 20th century mathematics!).</p> <p>For $p$-adic groups, Harish-Chandra reduced the problem to the determination of the discrete series, but the question of explicitly describing the discrete series in that case remains open.</p> <p>One important thing that Harish-Chandra proved was that not all points of $\widehat{G}$ (when $G$ is a real or $p$-adic semisimple Lie group) are in the support of Plancherel measure; only those which satisfy the technical condition of being "tempered". (So this is another difference from the abelian case, where Haar measure is supported uniformly over all of $\widehat{G}$.) Thus in explicitly describing Plancherel measure, and hence giving an explicit form of Fourier analysis for any real semi-simple Lie group, he <em>didn't</em> have to classify all unitary representations of $G$.</p> <p>Indeed, the classification of all such reps. (i.e. the explicit description of $\widehat{G}$) remains an open problem for real semi-simple Lie groups (and even more so for $p$-adic semi-simple Lie groups, where even the discrete series are not yet classified).</p> <p>This should give you some sense of the relationship between Fourier analysis in its representation-theoretic interpretation (i.e. the explicit description of $L^2(G)$ in terms of irreducibles) and the general classification of irreducible unitary representations of $G$. They are related questions, but are certainly not the same, and one can fully understand one without understanding the other.</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/46041#46041 Answer by Marc Palm for Is Fourier analysis a special case of representation theory or an analogue? Marc Palm 2010-11-14T13:42:34Z 2010-11-14T14:55:23Z <p>Fourier Analysis on $\mathbb{R}$ has several similiar interpretations. The most important one is it realizes the Functional calculus for the rightregular representation.</p> <p>I can only be really sketchy here:</p> <p>We can see it as the realization of the functional calculus for the operator $D= - \mathrm{i} \frac{\partial}{\partial x}$. Observe that $\mathcal{F} D = M_x \mathcal{F}$. Here $M_x$ is multiplication by $x$, which is much easier to understand than taking derivative. That is the main reason, why the Fourier transform is so important in the theory of differential operators. A great generalization of this is the Gelfand transform, which identifies certain commutative Algebras with functions over topological spaces. In this theory, we identify the algebra $D$ given by normal closed operator with the continouos function on the spectrum of $D$.</p> <p>Analogues ideas in algebraic geometry have been introduced by Grothendieck, who associated to varieties over a commutative unital ring R also a spectrum. In the case of an algebraic group this spectrum can be seen as a certain the group ring.</p> <p>Since taking derivatives commutes with the right translations, which are exactly the right regular representation of $\mathbb{R}$. The Fourier analysis also realizes the functional calculus for this family of operators.</p> <p>The analysis of noncommutative groups is of course much more difficult since the right translation do not commute here, hence there is no functional calculus, since this is not available for non commutative algebras.</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/56600#56600 Answer by saghar for Is Fourier analysis a special case of representation theory or an analogue? saghar 2011-02-25T06:02:56Z 2011-02-25T06:02:56Z <p>If you want to know what is the dual of a nonabelian locally compact group, you have to study about locally compact quantum groups. Then you can see that even we can define the fourier transform here as well.</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/115355#115355 Answer by paul garrett for Is Fourier analysis a special case of representation theory or an analogue? paul garrett 2012-12-04T04:09:27Z 2012-12-04T04:09:27Z <p>In addition to the many other interesting and useful answers, and as evidence for the fruitfulness of the question (!), I do think there are a few other (maybe-interesting and maybe-useful) points to be made. </p> <p>First, to limit the scope, let's say we're talking about "Type I" groups, that is, groups which more-or-less have a reasonable/tractable representation theory, in the sense that "factor representations" are sums/integrals of irreducibles. This assumption deserves comment: as in one of the earlier good answers, there are many reasonable groups which do not fall into this class. (Dang...) The good news is that it is possible to understand this failing (e.g., see Alain Robert's wonderful LMS book), and that for many critical applications (in my own purview, to number-theoretic things) this is not an issue. Whew.</p> <p>It is likewise certainly true (as observed and documented in earlier answers) that the "full question" of determination of details about various Plancherel theorems (for reductive p-adic groups...) is still open... but, also, sufficiently-many examples are known that "we" feel some confidence in advancing in a certain way. It is important to note that many literal Plancherel formulas do not (as noted in other answers!) involve <em>all</em> (unitary) irreducibles, but only a nice (a.k.a. "tempered", in some contexts) subclass.</p> <p>A very educational case is the Gelfand-Naimark story from the late 1940's, addressing more-or-less reductive complex Lie groups, essentially proving that the decomposition of $L^2(G)$ needed only unitary principal series... [sic]</p> <p>At best, such an assertion is about $L^2$, not about pointwise convergence, etc. </p> <p>Harish-Chandra showed in the 1950s and '60s that things are (stunningly) more complicated for "real" Lie groups <em>not</em> obtained by the forgetful functor complex-to-real Lie group.</p> <p>Nevertheless, ... for applications to analytic number theory (!?), one would desire sharp estimates on convergence of spectral expansions of automorphic forms. Maass and Selberg initiated this study, but/and this line of thought has not-so-often interacted with the Schwartz-Grothendieck modern-analysis thinking... to all our loss.</p> <p>As David Farmer aptly quipped in Oklahoma at a lovely conference in Sept of this year, "convergence is tricky". </p> <p>... but/and in many interesting cases, the convergence of "an eigenfunction expansion" is exactly what a serious problem wants.</p> <p>(Some schools of thought study the individual "eigenfunctions", e.g., automorphic forms, ... but/and many applications require those pesky convergence considerations.)</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/115358#115358 Answer by Will Sawin for Is Fourier analysis a special case of representation theory or an analogue? Will Sawin 2012-12-04T05:28:35Z 2012-12-04T05:28:35Z <p>Here is a very quick, overly simplified answer:</p> <p>Fourier analysis = The representation theory of S^1 + Peter-Weyl for S^1.</p> <p>So it's not a special case of representation theory, but it is a special case of ( representation theory + Peter-Weyl ).</p> <p>The reason this is only a rough schematic is that there is Fourier analysis that isn't just about the $L^2$ spaces. But you can think of it as having an $L^2$, algebraic core, with all the other functions between Banach spaces with various properties "glued" to the core, meaning they determine each other.</p> http://mathoverflow.net/questions/37021/is-fourier-analysis-a-special-case-of-representation-theory-or-an-analogue/115564#115564 Answer by Steve Huntsman for Is Fourier analysis a special case of representation theory or an analogue? Steve Huntsman 2012-12-06T00:36:58Z 2012-12-06T00:36:58Z <p>I just saw this and figured a more elementary and explicit answer discussing Fourier transforms on finite groups couldn't hurt, especially since it's a chance to use some of my notes.</p> <p>First, some scene-setting: harmonic analysis on a finite abelian group $G$ turns out to be a direct generalization of the theory of Fourier series. A function $f$ is decomposed according to</p> <p>$\hat f(\chi) := \lvert G \rvert^{-1/2} \sum_g f(g) \chi(g);$</p> <p>$f(g) = \lvert G \rvert^{-1/2} \sum_\chi \hat f(\chi) \chi(g^{-1}).$</p> <p>Here $\chi$ denotes a character. The factors of $\lvert G \rvert^{-1/2}$ are chosen for the sake of unitarity; the more general case of locally compact abelian $G$ is broadly similar.</p> <p>Nonabelian groups do not have enough unitary characters to enable a decomposition of the form above. Let $\rho: G \rightarrow GL(V)$ be a representation with dimension $d_\rho \equiv \dim V$; the corresponding character is $\chi_\rho(g) = \mbox{Tr} \rho(g)$.</p> <p>Two key identities express the orthogonality and completeness of representations, i.e.</p> <p><code>$\frac{d_\rho}{\lvert G \rvert} \sum_g \rho_{jk}(g^{-1}) \rho'_{\ell m}(g) = \delta_{\rho \rho'} \delta_{jm} \delta_{k \ell}$</code>; </p> <p>$\sum_\rho \frac{d_\rho}{\lvert G \rvert} \mbox{Tr} \left [ \rho(g^{-1}) \rho(g') \right ] = \delta_{gg'},$</p> <p>respectively, where straightforward generalizations of the usual Kronecker delta are indicated, $\rho_{jk}(g)$ denotes the $jk$ matrix element of $\rho(g)$, and the sum in the equality on the right is over inequivalent irreps (taking $g' = g$ shows also that $\sum_\rho d_\rho^2 = \lvert G \rvert$, in turn demonstrating that the irreps are all finite-dimensional). </p> <p>With this in mind it should not come as a surprise that Fourier analysis on a finite group essentially amounts to the prescription </p> <p>$\hat f(\rho) := (d_\rho/\lvert G \rvert)^{1/2} \sum_g f(g) \rho(g);$</p> <p>$f(g) = \lvert G \rvert^{-1/2} \sum_{\rho } \mbox{Tr}\left[ \hat f(\rho) \rho(g^{-1}) \right] d_\rho^{1/2}.$</p> <p>By the orthogonality and completeness of characters, the number of inequivalent irreps equals the number of conjugacy classes for $G$ finite. In fact a complete set of inequivalent irreps over $\mathbb{C}$ can be constructed classically in $poly(\lvert G \rvert)$ time, which makes the construction of FFTs feasible in general.</p>