A fast generalized DFT for finite groups of Lie type
Chloe Ching-Yun Hsu
Caltech

Chris Umans∗
Caltech

arXiv:1707.00349v2 [cs.DS] 23 Oct 2017

October 25, 2017

Abstract
We give an arithmetic algorithm using O(|G|ω/2+o(1) ) operations to compute the generalized
Discrete Fourier Transform (DFT) over group G for finite groups of Lie type, including the
linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups
of Lie type. Here ω is the exponent of matrix multiplication, so the exponent ω/2 is optimal if
ω = 2.
Previously, “exponent one” algorithms were known for supersolvable groups and the symmetric and alternating groups. No exponent one algorithms were known (even under the assumption ω = 2) for families of linear groups of fixed dimension, and indeed the previous
best-known algorithm for SL2 (Fq ) had exponent 4/3 despite being the focus of significant effort.
We unconditionally achieve exponent at
√ most 1.19 for this group, and exponent one if ω = 2.
We also show that ω = 2 implies a 2 exponent for general finite groups G, which beats the
longstanding previous best upper bound (assuming ω = 2) of 3/2.

∗

Supported by NSF grant CCF-1423544 and a Simons Foundation Investigator grant.

1

Introduction

Let G be a finite group and let Irr(G) denote a complete set of irreducible representations.
Given an element of the group algebra c ∈ C[G], a generalized DFT is a linear transform that
takes c to
X
M
ρ(g).
cg ·
g∈G

ρ∈Irr(G)

This is the fundamental linear operation that maps the standard basis for the group algebra C[G]
to the Fourier basis of irreducible representations of group G. It has applications in data analysis
[Roc97], as a component in other algorithms (including fast operations on polynomials and in
the Cohn-Umans matrix multiplication algorithms), and as the basis for quantum algorithms for
problems entailing a Hidden Subgroup Problem [MR97b]. As one varies the underlying group
G, the generalized DFT is a rich source of structured linear maps which one can hope to apply
in nearly-linear time via significant generalizations of the famous Cooley-Tukey FFT.
We typically speak of the complexity of computing this map in the (non-uniform) arithmetic
circuit model and do not concern ourselves with finding the irreps. The trivial algorithm thus
requires O(|G|2 ) operations. The best-known algorithm that works for general finite groups G
achieves O(|G|1.5 ) operations1 assuming the exponent of matrix multiplication is two (see Section
2). For solvable groups exponent 1.5 has been achieved by Beth [Bet84, CB93], unconditionally.
For a number of special cases, “exponent 1” algorithms are known: for abelian groups, the
symmetric and alternating groups [Cla89], and the so-called supersolvable groups [Bau91]. A
group that has resisted such exponent 1 algorithms despite a significant amount of work is
SL2 (Fq ), where the best known algorithm achieves O(|G|4/3 ) [LR92]. This group was described
as a “particularly interesting and thorny special case” by Maslen, Rockmore, and Wolff in
[MRW16a].
In this paper we obtain exponent one for SL2 (Fq ) under the assumption that ω = 2 (ω is the
exponent of matrix multiplication). Using the current best upper bound ω < 2.3729 [LG14], we
obtain exponent 1.19 for SL2 (Fq ) unconditionally, which improves the previous 4/3 exponent.
More generally, we achieve exponent ω/2 for essentially all linear groups via our methods, and
we work out the most common cases explicitly in this paper in Section 5.

The main idea. At its core, the seminal Beth-Clausen fast generalized DFT is a recursive
algorithm that computes a DFT with respect to G by computing several DFTs with respect
to H, a subgroup of G. Each of the [G : H] many H-DFTs is lifted to G and then summed
together. See Corollary 4. A bottleneck in this algorithm comes from the final summation step,
which in general costs [G : H]|G|. Since there are groups whose largest subgroup H has index
at least |G|1/2 , exponent 3/2 is the best possible within this approach. Improvements have
generally come from using specific knowledge of how the induced representations from H up to
G break up; this can sometimes be used to circumvent the bottleneck summation. In the case
of supersolvable groups and the symmetric and alternating groups, this has yielded exponent
one algorithms [Bau91, Cla89]. In the case of solvable groups, one can obtain exponent ω/2
[Bet84, CB93].
In this paper we devise a more general way to circumvent the bottleneck summation, which
depends on the structure of the group rather than knowledge of the representation theory. Our
new recursive step permits us to decompose G via two subgroups H and K, and recurse on H
and K. See Theorem 11. One side-effect is an alternative proof of the ω/2 exponent for solvable
groups that does not require knowledge of the representation theory of the group, in Section 4.
Our reduction bears some similarity to the double coset algorithm of [MR00]; a key difference
seems to be the use of fast matrix multiplication at an opportune time in the procedure.
1

Note that exercise 3.16 in [BCS97] claims that the exponent 1.5 can be reduced to ≈ 1.44 but this seems to be
an error, as discussed in Section 2.

1

Our results. We obtain new and sought-after results for linear groups that give an indication of the power of the new approach. We obtain, for the first time, fast DFT algorithms
using O(|G|ω/2+ǫ ) operations, for all ǫ > 0, for the general, orthogonal, and symplectic groups,
including their special and projective versions, and for all finite groups with a split (B, N )-pair,
which includes all simple finite groups of Lie type2 .
√
We also use our new method to show that ω = 2 implies a 2 exponent for general finite
groups G, which beats the longstanding previous best upper bound of 3/2 (assuming ω = 2).
To do this we prove a structural result about arbitrary finite groups (Theorem 23) that relies
on the Classification Theorem, which may be of independent interest.
For easy reference, the most important “bottom-line” results in this paper are (1) exponent
ω/2 generalized DFT algorithms for all general linear and special linear groups (Theorems 18 and
19, respectively), including the well-studied dimension two case, (2) exponent ω/2√generalized
DFT algorithms for all finite simple groups of Lie type (Theorem 17), and the new 2 exponent
upper bound for general groups, assuming ω = 2 (Theorem 24).

1.1

Past and related work

A good description of past work in this area can be found in Section 13.5 of [BCS97]. The first
algorithm generalizing beyond the abelian case is due to Beth in 1984 [Bet84]; this algorithm
is described in Section 2 in a form often credited jointly to Beth and Clausen. This algorithm
was the best known for the general case of an arbitrary finite group prior to this work. Two
other milestones are the O(|G| log |G|) algorithm for supersolvable groups due to Baum [Bau91],
and the O(|G| log3 |G|) algorithm for the symmetric group due to Clausen [Cla89]. The latter
algorithm was improved to O(|G| log 2 |G|) by Maslen [Mas98], and very recently to linear for
the special case of Sn−k -invariant functions on Sn with n > 2k [CH17]. Wreath products were
studied by Rockmore [Roc95] who obtained exponent one algorithms in certain cases.
In the 1990s, Maslen, Rockmore and coauthors, developed the so-called “separation of variables” approach, which relies on non-trivial decompositions along chains of subgroups via Bratteli
diagrams and (again) detailed knowledge of the representation theory of the underlying groups.
There is a rather large body of literature on this approach and it has been applied to a wide
variety of group algebras and more general algebraic objects. For a fuller description of this approach and the results obtained, the reader is referred to the surveys [MR97b, MR97a, Roc02],
and the most recent paper in this line of work [MRW16a].
For the present paper, the most important results for comparison are the previous best
known results for linear groups of various sorts. We gather them in Figure 1. Notice that for
each fixed dimension n, these all represent exponent α algorithms for α > 1. Our methods give
exponent ω/2 algorithms for all of these groups, which translates to (the optimal) exponent 1
if ω = 2. Using the current best upper bounds on ω our methods give concrete improvements
in small dimension, in all cases; we explicitly highlight only the case of SL2 (Fq ) in this paper.

1.2

Notation and preliminaries

Throughout this paper we will use the phrase
“G has a generalized DFT using O(|G|α+ǫ ) operations, for all ǫ > 0”
where G is a finite group and α ≥ 1 is a real number. We mean by this that there are universal
constants cǫ independent of the group G under consideration so that for each ǫ > 0, the operation
count is at most cǫ |G|α+ǫ . Such an algorithm will be referred to as an “exponent α” algorithm.
This comports with the precise definition of the exponent of matrix multiplication, ω: that there
2

See Figure 2 for families of groups that include all simple finite groups of Lie type. Other families of groups such
as GLn (Fq ) are not simple, but are still described as “groups of Lie type.” These families of groups are amenable to
our approach, on a case-by-case basis, and we work out the general, orthogonal, and symplectic cases in this paper.

2

Group G
SL2 (Fq )
GLn (Fq )
PSp2n (Fq )
O2n+1 (Fq )
+
O2n
(Fq ), n ≥ 4

Upper bound
e
O(q|G|)
e n |G|)
O(q
e 5n−3 |G|)
O(q
e 5n−3 |G|)
O(q
e 5n−6 |G|)
O(q

Reference
Theorem 1.1 in [LR92]
Theorem 4.3 in [MRW16b]
Theorem 5.14 in [MR97a]
Theorem 5.14 in [MR97a]
Theorem 5.14 in [MR97a]

Figure 1: Previously best known running times for the generalized DFT over various families of
e notation hides lower order terms and the dependence on n.
linear groups. In this table, the O(·)
are universal constants bǫ for which n × n matrix multiplication can be performed using at most
bǫ nω+ǫ operations, for each ǫ > 0.
All logarithms are base 2. We use Irr(G) to denote the complete set of irreducible representations of G being used for the DFT at hand. In the presentation to follow, we assume the
underlying field is C; however our algorithms work over any field Fpk whose characteristic p
does not divide the order of the group, and for which k is sufficiently large for Fpk to represent
a complete set of irreducibles.
P
A basic fact is that ρ∈Irr(G) dim(ρ)2 = |G|, which implies that for all ρ ∈ Irr(G), we have
dim(ρ) ≤ |G|1/2 . An inequality that we use repeatedly is this one:
Proposition 1. For any real number α > 2, we have
X
O(dim(ρ)α ) ≤ O(|G|α/2 ).
ρ∈Irr(G)

Proof. Set ρmax to be an irrep of largest dimension. We have
X
X
dim(ρ)2 = O(dim(ρmax )α−2 |G|) ≤ O(|G|α/2 ),
O(dim(ρ)α ) ≤ O(dim(ρmax )α−2 )
ρ∈Irr(G)

ρ∈Irr(G)

where the last inequality used the fact that dim(ρmax ) ≤ |G|1/2 .
We also need Lev’s Theorem:
Theorem 2 ([Lev92]). Every finite group G has a proper subgroup H of order at least |G|1/2 ,
unless G is cyclic of prime order.
This is easily seen to be tight by considering the cyclic group of order p2 , for p prime.
In a few key places, we utilize the Kronecker product (or tensor product) of two matrices A
and B, and there our convention is to name the indices of A ⊗ B so that
(A ⊗ B)[(i, i′ ), (j, j ′ )] = A[i, j]B[i′ , j ′ ].

2

The single subgroup reduction

In this section we describe the recursive generalized DFT attributed to Beth and Clausen (see
[BCS97]). Given a subgroup H of a finite group G, this reduction computes a DFT with respect
to G via DFTs with respect to H. Our presentation makes use of fast matrix multiplication
where possible and so the running time will be expressed in terms of ω. A key definition is that of
an H-adapted basis for the irreps of G. This is a basis in which the restriction of each irrep of G
to H respects the direct sum decomposition into irreps of H. In concrete terms, this means that

3

for each irrep ρ ∈ Irr(G), while for general g ∈ G, ρ(g) is a dim(ρ) × dim(ρ) matrix, for g ∈ H,
ρ(g) is a block-diagonal matrix with block sizes coming from the set {dim(σ) : σ ∈ Irr(H)}.
Theorem 3. Let G be a finite group and let H be a subgroup. Then we can compute a DFT
with respect to G and an H-adapted basis, at a cost of [G : H] many H-DFTs plus
X
O(dim(σ)ω+ǫ )
[G : H]|G| + [G : H]2
σ∈Irr(H)

operations, for all ǫ > 0.
Proof. Let g1 , g2 , . . . , gt be a system of distinct right coset representatives of H in G, so t = [G :
H]. Let c be an element of C[G]. We can write
!
t
X (i)
X
X
ch h g i
c=
cg g =
i=1

g∈G

for some elements c(i) =

P

(i)
h∈H ch h



si =

h∈H

∈ C[H]. By computing an H-DFT for each i, we obtain
X

M

(i)

ch

h∈H

σ(h).

σ∈Irr(H)

Let si be the lift of si in which we repeat each σ ∈ Irr(h) as many times as it occurs in the
irreps of G. We notice that


t
X
X
M
M
ρ(g) =
ρ(gi ) .
cg
si · 
g∈G

ρ∈Irr(G)

i=1

ρ∈Irr(G)

Moreover, since we are using an H-adapted basis, each of the t matrix multiplications is the
product of a block-diagonal matrix having blocks whose dimensions are those of the irreps of
H, with a block diagonal matrix having blocks whose dimensions are those of the irreps of G. If
nσ,ρ denotes the number of occurences of σ ∈ Irr(H) in ρ ∈ Irr(G), the cost of performing this
structured matrix multiplication is at most
X

X

σ∈Irr(H) ρ∈Irr(G)

nσ,ρ O(dim(σ)ω+ǫ )

dim(ρ)
dim(σ)

=

X

σ∈Irr(H)

=

X

O(dim(σ)ω−1+ǫ )

X

nσ,ρ dim(ρ)

ρ∈Irr(G)

O(dim(σ)ω−1+ǫ ) dim(σ)[G : H]

σ∈Irr(H)

=

X

O(dim(σ)ω+ǫ )[G : H]

σ∈Irr(H)

where the second-to-last equality used Frobenius reciprocity: nσ,ρ
P also equals the number of
times ρ occurs in the induction of σ from H up to G, and then ρ nσ,ρ dim(ρ) is easily seen
to be the dimension of the induced representation, which is dim(σ)[G : H]. We have to do
[G : H] many of these structured multiplications, and then sum them up. The summing costs
[G : H]|G| many operations, since the block-diagonal matrices we are summing have, in general,
|G| nonzeros.
We note that this final sum, which costs |G|[G : H] operations, cannot be accelerated by fast
matrix multiplication, and this appears to have been overlooked in the claim in [BCS97] that
by using fast matrix multiplication together with Theorem 2 one can achieve an upper bound

4

of |G|1.44 for all finite groups G. Indeed when |H| = |G|1/2 , the |G|[G : H] term by itself is
at least |G|3/2 . Our “double subgroup reduction” can be seen as a means to avoid having to
directly compute this bottleneck sum.
If we have a chain of subgroups {1} = H0 ⊆ H1 ⊆ · · · ⊆ Hk = G, and setting ti = [Hi : Hi−1 ],
we can apply the Theorem 3 repeatedly to obtain an upper bound on the operation count of


2−ω/2
2−ω/2
2−ω/2
2−ω/2
|G|(tk + tk−1 + . . . + t1 ) + O(|G|ω/2+ǫ ) tk
+ tk−1 + tk−2 · · · t1

P
where we used σ∈Irr(H) O(dim(σ)ω+ǫ ) ≤ O(|H|ω/2+ǫ ) which is obtained via Proposition 1 with
√
α = ω + ǫ. If t is the maximum of the ti , then using only that ω ≤ 3, we recover the O( t|G|3/2 )
running time of the presentation in [BCS97]. If we assume ω = 2, then we get a running time
of O(t|G|1+ǫ ). Lev’s theorem is tight, so as a general bound for finite groups G, this O(t|G|1+ǫ )
running time is never smaller than |G|3/2 .
Finally, we note that at the expense of a slightly coarser upper bound we can remove the
requirement of an H-adapted basis, which will simplify our use of Theorem 3 in more complicated
recursive algorithms later.
Corollary 4. Let G be a finite group and let H be a subgroup. Then we can compute a DFT
with respect to G at a cost of [G : H] many H-DFTs plus [G : H] · O(|G|ω/2+ǫ ) operations, for
all ǫ > 0.
Proof. At a cost of

X

O(dim(ρ)ω+ǫ )

(1)

ρ∈Irr(G)

operations, we can change an arbitrary basis to an H-adapted basis, to which we apply Theorem
3, and then change back to the original basis. Both expression (1) and the expression
X
O(dim(σ)ω+ǫ )
[G : H]2
σ∈Irr(H)

from the statement of Theorem 3 are upper bounded by [G : H] · O(|G|ω/2+ǫ ), via Proposition
1 with α = ω + ǫ.

3

The double subgroup reduction

This section contains our main algorithmic result. Given two subgroups H, K of a finite group
G, we show how to compute a DFT with respect to G, via DFTs with respect to H and K.
We first show how to obtain an intermediate representation in terms of tensor products of the
irreps of H and the irreps of K:
Lemma 5. Let H and K be subgroups of G and let c be an element of C[G] supported on HK.
Fix a way of writing g = hk for each g ∈ HK (this is unique iff H ∩ K = {1}). We can compute
X
M
σ(h) ⊗ τ (k),
cg
g=hk∈HK

σ∈Irr(H),τ ∈Irr(K)

by performing |H| many K-DFTs and |K| many H-DFTs.
Proof. We can write
c=

X

g∈G

cg g =

X

h∈H

5

h·

X

k∈K

(h)
ck k

!

for some elements c(h) =
for each h ∈ H:

P

k∈K


(h)
ck k ∈ C[K]. We perform |H| many K-DFTs to compute
sh =

X

(h)

ck

k∈K

M

τ (k).

τ ∈Irr(K)

We use the notation sh [τ, u, v] to refer to entry (u, v) of component τ in the direct sum. Then
we perform |K| many H-DFTs to compute for each τ ∈ Irr(K) and u, v ∈ [dim(τ )],
X
M
σ(h).
tτ,u,v =
sh [τ, u, v]
h∈H

σ∈Irr(H)

Note that tτ,u,v [σ, x, y] is the ((x, u), (y, v)) entry of
so we have computed:
X
M
chk
h,k

P

(h)
h,k ck σ(h)⊗τ (k)

σ∈Irr(H),τ ∈Irr(K)

(h)

and note that ck = chk ,

σ(h) ⊗ τ (k)

as promised.
The following is an important (and known) general observation (see, e.g., Lemma 4.3.1 in
[HJ91]):
Lemma 6. If A is an n1 × n2 matrix, B is an n2 × n3 matrix, and C is an n3 × n4 matrix, then
the product ABC can be computed by multiplying A ⊗ C T (which is an n1 n4 × n2 n3 matrix) by
B viewed as an n2 n3 -vector.
Proof. Observe that
(ABC)[i1 , i4 ] =

X

A[i1 , i2 ]B[i2 , i3 ]C[i3 , i4 ]

i2 ,i3

and
((A ⊗ C T ) · B)[(i1 , i4 )] =

X

i2 ,i3

(A ⊗ C T )[(i1 , i4 ), (i2 , i3 )]B[(i2 , i3 )] =

X

A[i1 , i2 ]C[i3 , i4 ]B[i2 , i3 ].

i2 ,i3

This n1 n4 × n2 n3 -matrix-vector multiplication costs O(n1 n4 n2 n3 ) operations. More importantly, we have:
Corollary 7. If A and C are as above, and square (so n1 = n2 and n3 = n4 ), and we have
several n2 × n3 matrices, B1 , B2 , . . . , Bℓ , then we can compute ABi C for all i from A ⊗ C T , at
a cost of
O((n2 n3 )ω−1+ǫ · max{n2 n3 , ℓ}).
operations, for all ǫ > 0.
Proof. Set N = n1 n4 = n2 n3 . If ℓ ≤ N , then this can be accomplished with a single N × N
matrix multiplication, at a cost of O(N ω+ǫ ) operations, by the definition of ω. If ℓ > N ,
then this can be accomplished with ⌈ℓ/N ⌉ many N × N matrix multiplications, at a cost of
O(ℓ · N ω−1+ǫ ) operations.
Now we show how to lift from the intermediate representation to the space of irreducibles of
G. We need some notation. For σ ∈ Irr(H), τ ∈ Irr(K), ρ ∈ Irr(G), let nσ,ρ be the number of
occurences of σ in the restriction of ρ to H, and let mτ,ρ be the number of occurences of τ in
the restriction of ρ to K.

6

Lemma 8. There is a linear map
Y
φG,H,K :

σ∈Irr(H),τ ∈Irr(K)

L

2

C(dim(σ) dim(τ )) →
L

Y

Cdim(ρ)

2

ρ∈Irr(G)

that maps σ∈Irr(H),τ ∈Irr(K) σ(h) ⊗ τ (k) to ρ∈Irr(G) ρ(hk) for all h ∈ H, k ∈ K. Map φG,H,K
can be computed using





X
X
O (dim(σ) dim(τ ))ω−1+ǫ · max dim(σ) dim(τ ),
nσ,ρ mτ,ρ 


ρ∈IrrG
σ∈Irr(H),τ ∈Irr(K)
X
O(dim(ρ)ω+ǫ )
+
ρ∈Irr(G)

operations, for all ǫ > 0.
Proof. Let Irr∗ (H) be the multiset of irreducibles of H in the multiplicities that they occur
in the restrictions to H of Irr(G), and let Irr∗ (K) be the multiset of irreducibles of K in
the multiplicities that they occur in the restrictions to K of Irr(G). Let S be the change of
basis matrix taking ⊕σ∈Irr∗ (H) σ to ⊕ρ∈Irr(G) ρ and let T be the change of basis matrix taking
⊕τ ∈Irr∗ (K) τ to ⊕ρ∈Irr(G) ρ. Then for each h ∈ H, k ∈ K, we have




M
M
M
ρ(hk).
τ (k) T −1 =
σ(h) S −1 T 
S
ρ∈Irr(G)

τ ∈Irr∗ (K)

σ∈Irr∗ (H)

Set M = S −1 T , and consider the expression
 

M

σ(h) M 
σ∈Irr∗ (H)

M

τ ∈Irr∗ (K)



τ (k) .

(2)

Note that both M and the above product are block-diagonal matrices with blocks of dimension
dim(ρ) as ρ runs through Irr(G). Now, for each ρ ∈ Irr(G), a given σ ∈ Irr(H) occurs nσ,ρ
times and a given τ ∈ Irr(K) occurs mτ,ρ P
times; therefore we are computing σ(h)Bi τ (k) for p
distinct sub-matrices Bi of M , where p = ρ∈Irr(G) nσ,ρ mτ,ρ . By Corollary 7, each such batch
can be computed by taking a product of σ(h) ⊗ τ (k)T with a matrix whose columns are the Bi
sub-matrices, viewed as vectors. This is linear in the entries of σ(h) ⊗ τ (k), and costs





X
nσ,ρ mτ,ρ 
O (dim(σ) dim(τ ))ω−1+ǫ · max dim(σ) dim(τ ),


ρ∈Irr(G)

operations. Finally, we need to L
multiply (2) by S on the left and T −1 on the right; both
maps are linear in the entries of
σ∈Irr(H),τ ∈Irr(K) σ(h) ⊗ τ (k), and as block-diagonal matrix
P
multiplications, both cost ρ∈Irr(G) O(dim(ρ)ω+ǫ ) operations.

Now we use elementary facts from representation theory to bound the complexity estimate
in Lemma 8 in terms of |H|, |K|, |G|.
Lemma 9. For all finite groups G and subgroups H, K, the expression





X
X
O (dim(σ) dim(τ ))ω−1+ǫ · max dim(σ) dim(τ ),
nσ,ρ mτ,ρ 


ρ∈IrrG
σ∈Irr(H),τ ∈Irr(K)
X
O(dim(ρ)ω+ǫ )
+
ρ∈Irr(G)

7

is upper bounded by O((|H||K|)ω/2+ǫ/2 + |G|ω/2+ǫ/2 ).
Proof. We use only the fact that for each ρ ∈ Irr(G),
X
dim(σ)nσ,ρ = dim(ρ),

(3)

σ∈Irr(H)

and similarly

X

dim(τ )mτ,ρ = dim(ρ),

(4)

τ ∈Irr(K)

together with the fact that the sum of the squares of the dimensions of the irreps of a group is
the order of that group (which implies that the maximum dimension is at most the square root
of the order of the group).
We observe that by replacing the “max” with addition,





X
X
O (dim(σ) dim(τ ))ω−1+ǫ · max dim(σ) dim(τ ),
nσ,ρ mτ,ρ 


ρ∈IrrG
σ∈Irr(H),τ ∈Irr(K)



X
X
O (dim(σ) dim(τ ))ω−1+ǫ · dim(σ) dim(τ ) +
≤
nσ,ρ mτ,ρ 
ρ∈IrrG

σ∈Irr(H),τ ∈Irr(K)

We know that
X

σ∈Irr(H),τ ∈Irr(K)

(dim(σ) dim(τ ))ω−1+ǫ · dim(σ) dim(τ )


=

X

σ∈Irr(H)

 

dim(σ)ω+ǫ  · 

X

τ ∈Irr(K)



dim(τ )ω+ǫ  ≤ (|H||K|)ω/2+ǫ/2 .

where the last inequality applied Proposition 1 twice, with α = ω + ǫ. Also, we know that


X
X
(dim(σ) dim(τ ))ω−1+ǫ · 
nσ,ρ mτ,ρ 

σ∈Irr(H),τ ∈Irr(K)

=

X

ρ∈Irr(G)

≤
=

X

ρ∈Irr(G)

X

ρ∈Irr(G)






ρ∈IrrG

X

σ∈Irr(H)

dim(σ)ω−1+ǫ nσ,ρ  · 

|H|(ω−2+ǫ)/2 ·

|H|

 

(ω−2+ǫ)/2

|K|

X

σ∈Irr(H)

X

τ ∈Irr(K)



dim(τ )ω−1+ǫ mτ,ρ 

 

dim(σ)nσ,ρ  · |K|(ω−2+ǫ)/2 ·

(ω−2+ǫ)/2

2

(ω−2+ǫ)/2

dim(ρ) = (|H||K|)

X

τ ∈Irr(K)

|G|

dim(τ )mτ,ρ 

where the second-to-last equality used (3) and (4). If |H||K| ≤ |G| then this expression is at most
ω/2+ǫ/2
|G|ω/2+ǫ/2 ; if |H||K| > |G| then this expression
. Finally, we have
P is at most (|H||K|)
ω+ǫ
that the final term in the main expression, ρ∈Irr(G) O(dim(ρ)
), is at most O(|G|ω/2+ǫ/2 ),
by Proposition 1 with α = ω + ǫ, and the lemma follows.
Our main theorems put everything together:

8



Theorem 10. Let G be a finite group and let H, K be subgroups and let x ∈ G be any element.
Fix a way of writing g = hk for each g ∈ HK (this is unique iff H ∩ K = {1}). Let c ∈ C[G]
be supported on HKx. Then we can compute
X
M
ρ(g)
cg ·
g=hkx∈HKx

ρ∈Irr(G)

at the cost of |H| many K-DFTS, |K| many H-DFTs, plus O(|G|ω/2+ǫ + (|H||K|)ω/2+ǫ ) operations, for all ǫ > 0.
Proof. Set c′g = cgx and notice that c′ is supported on HK. Apply Lemma 5 on c′ to compute
X

g=hk∈HK

c′g

M

σ∈Irr(H),τ ∈Irr(K)

σ(h) ⊗ τ (k).

L
P
Next, apply the linear map φG,H,K to obtain (by linearity) g=hk∈HK c′g ρ∈Irr(G) ρ(hk), and
P
finally, multiply by ⊕ρ∈Irr(G) ρ(x) on the right, at a cost of ρ∈Irr(G) dim(ρ)2 ≤ O(|G|ω/2+ǫ )
operations (by Proposition 1 with α = ω + ǫ). The result is
X
M
X
M
ρ(g ′ ),
ρ(gx) =
cg ′
c′g
g=hk∈HK

g′ ∈HKx

ρ∈Irr(G)

ρ∈Irr(G)

as promised.
By translating HK around, we cover all of G, leading to our main theorem:
Theorem 11 (main). Let G be a finite group and let H, K be subgroups. Then we can compute the DFT with respect to G at the cost of |H| many K-DFTS, |K| many H-DFTs, plus
ln(|G|)
O(|G|ω/2+ǫ + (|H||K|)ω/2+ǫ ) operations, all repeated r = O( |G||HK|
) many times, for all ǫ > 0.
If G = HK, then we may take r = 1.
Proof. We argue that there exist x1 , x2 , . . . , xr ∈ G so that ∪i HKxi = G. Then a G-DFT can
be computed by applying Theorem 10 r times with these translations. The existence of the xi
is a standard application of the probablistic method: for randomly chosen xi , the probability
∪i HKxi fails to contain a given g ∈ G is (1 − |HK|/|G|)r , and the r specified in the theorem
statement makes this quantity strictly less than 1/|G|, so a union bound finishes the argument.

4

Exponent ω/2 for finite solvable groups

We show how to derive algorithms for all solvable groups via our reduction, matching the
exponent ω/2 algorithm of [Bet84, CB93]. An advantage of our approach is that we don’t need
to rely on knowledge of the representation theory of G.
We begin with a key definition:
Definition 12. A finite group G is supersolvable if there is a sequence of subgroups
{1} = G0 ⊳ G1 ⊳ G2 ⊳ · · · ⊳ Gk = G
such that each Gi is normal in G, and for all i, Gi /Gi−1 is cyclic of prime order.
A solvable finite group G is one in which the requirement that each Gi is normal in G (rather
than just Gi+1 ) is removed. An early result in the area of fast generalized DFTs was Baum’s
algorithm which gives a fast DFT for all supersolvable groups.

9

Theorem 13 (Baum). There is an algorithm that uses O(|G| log |G|) operations to compute the
generalized DFT over G, if G is supersolvable.
An important class of supersolvable groups are p-groups. Together with this fact, the result
of the previous section makes it quite easy to obtain an algorithm for all solvable groups. We
need the following classical result of Hall:
Theorem 14 (Hall). Let G be a finite solvable group of order ab, with (a, b) = 1. Then there
exists a subgroup H ⊆ G of order a.
From this we obtain:
Theorem 15. Let G be a finite solvable group. Then a G-DFT can be computed in O(|G|ω/2+ǫ )
operations, for all ǫ > 0.
Proof. Take δ = ǫ/2. Let Aδ ≥ 1 be the constant hidden in the O(|G|ω/2+δ + (|H||K|)ω/2+δ )
notation in Theorem 11. Let B be the constant in the big-oh expression in the statement of
Theorem 13. It suffices to prove that for any finite group G with |G| having k distinct prime
factors, a G-DFT can be computed in
(4Aδ )log k |G|ω/2+δ B log |G|
operations, because for sufficiently large G, we have
(4Aδ )log k B log |G| ≤ (4Aδ )log log |G| B log |G| ≤ |G|δ .
The proof is by induction on the number of distinct prime factors in the order of G. For the
base case of k = 1, G is a p-group, hence supersolvable, and we apply Theorem 13.
Now, suppose |G| = pa1 1 . . . pakk , where p1 , . . . , pk are distinct primes, then |G| = ab, where a
and b each has no more than k/2 distinct prime factors and (a, b) = 1. Applying Hall’s theorem
(twice) there are subgroups H, K of order a and b respectively. Since (a, b) = 1, we must have
H ∩ K = {1}, and then G = HK because |G| = ab.
We can then apply Theorem 11, to reduce to the case of computing |H| many K-DFTs and
K many H-DFTs, at a cost of 2Aδ |G|ω/2+δ operations. But H and K are both solvable, and
hence by the induction hypothesis, these two sets of DFTs cost at most
|H| · (4Aδ )log(k/2) |K|ω/2+δ B log |K| + |K| · (4Aδ )log(k/2) |H|ω/2+δ B log |H|
2
(4Aδ )log k |G|ω/2+δ B log |G|
≤
4Aδ
operations. Together with the 2Aδ |G|ω/2+δ overhead, this is no more than
(4Aδ )log k |G|ω/2+δ B log |G|
operations, as required.

5

Exponent ω/2 for finite groups of Lie type

One of the main payoffs of Theorem 11 is exponent ω/2 algorithms for finite groups of Lie type.
This is because groups of Lie type have an “LDU -type” decomposition which is well-suited
to Theorem 11. We describe these decompositions and the resulting DFT algorithms in this
section. All of our “LDU -type” decompositions of groups of Lie type into three subgroups give
rise to the following DFT algorithm:

10

Theorem 16. Let H1 , H2 , H3 be subgroups of group G, and suppose all three are either p-groups
or abelian. Moreover, suppose H1 H2 is a subgroup and H1 ∩ H2 = {1} and H1 H2 ∩ H3 = {1}.
Then there is a generalized DFT for G that uses at most


|G| log |G|
O |G|ω/2+ǫ
|H1 ||H2 ||H3 |
operations, for all ǫ > 0.
Proof. We apply Theorem 11 to the pair H1 H2 and H3 at a cost of O(|G|ω/2+ǫ ) plus |H1 H2 |
many H3 -DFTs and |H3 | many H1 H2 -DFTs. This is all repeated


|G| log |G|
r=O
|H1 ||H2 ||H3 |
many times. The H3 -DFTs cost O(|H3 | log |H3 |) because H3 is abelian or a p-group (via Theorem 13). We apply Theorem 11 once more to H1 , H2 , at a cost of O(|H1 H2 |ω/2+ǫ ) plus |H1 |
many H2 -DFTs and |H2 | many H1 -DFTs. Each H1 -DFT costs O(|H1 | log |H1 |) because H1 is
abelian or a p-group, and the same is true for each H2 -DFT. Altogether, the cost is
h
r · O(|G|ω/2+ǫ ) + |H1 H2 | · O(|H3 | log |H3 |)

i
+ |H3 | · O(|H1 H2 |ω/2+ǫ ) + |H1 | · O(|H2 | log |H2 |) + H2 · O(|H1 log H1 |)
which is as claimed.

From Carter [Car89], we have that all finite simple groups of Lie type (except the Tits group)
have a split (B, N )-pair, which implies the following structure:
G = ⊔w∈W BwUw
B and N are subgroups, W is the Weyl group (i.e. W = B/(B ∩ N )), and B = U T with T
a maximal torus (hence abelian) and U, T are complements in B. The Uw are subgroups of U ,
and U is a p-group. This decomposition is “with uniqueness of expression” which implies that
|BwUw | = |B||Uw | for each w.
From this description we easily have the very general result:
Theorem 17. Let G be a finite group with a split (B, N )-pair, with associated Weyl group W .
Then there is a fast DFT over G that uses O(|G|ω/2+ǫ |W |) operations, for all ǫ > 0.
Proof. Fix the w maximizing the size of the double coset BwUw , and note that |BUww | =
|BwUw | ≥ |G|/|W |. As noted this size is |B||Uw |, and hence B ∩ Uww = {1}. Also from the
description above, B = U T with U ∩ T = {1}; T is abelian and U, Uww are p-groups. We are
then in the position to apply Theorem 16, which yields the claimed operation count.
As one can see from Figure 2, for families of finite simple groups of Lie type, the Weyl group
always has order that is |G|o(1) , so this algorithm has exponent ω/2, which is best-possible if
ω = 2. Next, we explicitly work out the more common cases of the general linear, orthogonal, and
symplectic families, and their variants. The overhead coming from the parameter r in Theorem
11 in each case is somewhat smaller than the worst-case bound of O(|W | log |G|) coming from
(the very general) Theorem 17; instead it approaches O(log |G|) as the underlying field size q
approaches infinity.

11

5.1

The groups GLn (Fq ) and SLn (Fq )

The easiest example for applying Theorem 16 is the general linear group.
Theorem 18. For each n and prime power q, there is a generalized DFT for the group G =
GLn (Fq ) that uses O(|G|ω/2+ǫ ) operations, for all ǫ > 0.
Proof. The three subgroups H1 , H2 , H3 are the set of lower-triangular matrices with ones on
the diagonal, the set of diagonal matrices, and the set of upper-triangular matrices with ones on
2
2
the diagonal, which have sizes q (n −n)/2 , (q − 1)n , and q (n −n)/2 , respectively. In the notation
of Theorem 16, we have



n
|G| log |G|
q
r=O
≤O
(n2 log q)
|H1 ||H2 ||H3 |
q−1
which can be absorbed into the |G|ǫ term.
For SLn (Fq ) the only difference is that the diagonal matrices must have determinant one, so
the size of that subgroup is (q − 1)n−1 instead of (q − 1)n ; the group itself is also smaller by a
factor of q − 1. We obtain in exactly the same way as for Theorem 18:
Theorem 19. For each n and prime power q, there is a generalized DFT for G = SLn (Fq ) that
uses O(|G|ω/2+ǫ ) operations, for all ǫ > 0.
Since the two dimensional case has attracted a lot of attention, we record that result separately, for concreteness:
Theorem 20. For each prime power q, there is a generalized DFT for G = SL2 (Fq ) that uses
O(|G|ω/2+ǫ ) operations, for all ǫ > 0.
Proof. Let H1 be the set of lower triangular matrices with ones on the diagonal, H2 be the set
of diagonal matrices with determinant 1, and H3 be the set of upper triangular matrices with
ones on the diagonal. These are all subgroups, each pairwise intersection is {1}, and we have
H1 H2 is a subgroup. All three subgroups are abelian, with orders q, q − 1, and q, respectively.
Since |G| = q 3 − q we have in this case that |H1 H2 ||H3 | = |G| and hence H1 H2 H3 = G. We
can perform the DFT by applying Theorem 11 to H1 H2 and H3 , and then to H1 and H2 . The
overall cost is
O(|G|ω/2+ǫ )

+ |H1 H2 | · O(|H3 | log |H3 |)


+ |H3 | · O(|H1 H2 |ω/2+ǫ ) + |H1 | · O(|H2 | log |H2 |) + H2 · O(|H1 log H1 |)

which simplifies to the claimed operation count.

5.2

The symplectic groups Sp2n (Fq )

A symplectic group of dimension 2n over Fq is the subgroup of invertible matrices that preserve
a symplectic form; all symplectic forms are equivalent under a change of basis, so concretely we
may take Sp2n (Fq ) to be the set of all matrices A ∈ GL2n (Fq ) such that


0 J
AT QA = Q, where Q =
−J 0
and J is the matrix with ones on the antidiagonal.
Theorem 21. For each n and prime power q, there is a generalized DFT for G = Sp2n (Fq )
that uses O(|G|ω/2+ǫ ) operations, for all ǫ > 0.

12

Proof. Let L, U, D be the lower-triangular (with ones on the diagonal), upper-triangular (with
ones on the diagonal), and diagonal subgroups of GL2n (Fq ), respectively. We view our group G
as a subgroup of GL2n (Fq ) as well. It is well known that the order of G is
2

qn

n
Y

2

(q 2i − 1) ≤ q 2n

+n

.

i=1

Now apply Theorem 16 with H1 = L ∩G, H2 = D ∩G and H3 = U ∩G. We note that H1 and
H3 are p-groups and H2 is abelian (as before). Also, H1 H2 is a subgroup, and H1 ∩ H2 = {1}
and H1 H2 ∩ H3 = {1}.
It remains to bound the sizes of H1 , H2 , H3 . In order to lower bound the size of H3 , consider
the following subgroups of GL2n (Fq ),



In M
n×n
: M ∈ Fq
H =
0 In



A 0
K =
: A, B upper triangular with ones on the diagonal .
0 B
One can verify that H ∩ G is the subgroup in which M is a persymmetric matrix (symmetric
about the anti-diagonal), and thus this subgroup has order q n(n+1)/2 . Similarly, one can verify
that K ∩ G is the subgroup in which A is an arbitrary upper-triangular matrix with ones on the
diagonal and B = J(AT )−1 J. Thus this subgroup has order q n(n−1)/2 . We have
(H ∩ G)(K ∩ G) ⊆ H3
2

and so |H3 | ≥ q n(n+1)/2+n(n−1)/2 = q n . A symmetric argument shows that |H1 | has the same
order. It is also easy to verify that |H2 | = (q − 1)n . In the notation of Theorem 16, we have


n

q
|G| log |G|
≤O
((n2 + n) log q)
r=O
|H1 ||H2 ||H3 |
q−1
which can be absorbed into the |G|ǫ term.

5.3

The orthogonal groups On (Fq )

An orthogonal group of dimension n over Fq is a subgroup of invertible matrices that preserve
a nondegenerate symmetric quadratic form. There are several inequivalent quadratic forms and
thus several non-isomorphic orthogonal groups. For simplicity, we work out only one case (the
“plus type” orthogonal group of even dimension, in odd characteristic). A similar analysis can
be easily carried out for the other non-isomorphic orthogonal groups. In our case, concretely,
we may take On (Fq ) to be the set of all matrices A ∈ GLn (Fq ) such that


0 J
T
A QA = Q, where Q =
J 0
and J is the matrix with ones on the antidiagonal.
Theorem 22. For each even n and odd prime power q, there is a generalized DFT for G =
On (Fq ) specified via the above quadratic form, that uses O(|G|ω/2+ǫ ) operations, for all ǫ > 0.
Proof. Let L, U, D be the lower-triangular (with ones on the diagonal), upper-triangular (with
ones on the diagonal), and diagonal subgroups of GLn (Fq ), respectively. We view our group G
2
as a subgroup of GLn (Fq ) as well. It is well known that the order of G is at most 2q (n −n)/2 .

13

Now apply Theorem 16 with H1 = L ∩G, H2 = D ∩G and H3 = U ∩G. We note that H1 and
H3 are p-groups and H2 is abelian (as before). Also, H1 H2 is a subgroup, and H1 ∩ H2 = {1}
and H1 H2 ∩ H3 = {1}.
It remains to bound the sizes of H1 , H2 , H3 . In order to lower bound the size of H3 , first
consider the following subgroups of GLn (Fq ),



In/2 M
: M ∈ Fn/2×n/2
H =
q
0
In/2



A 0
K =
: A, B upper tri. with ones on the diagonal .
0 B
One can verify that H ∩ G is the subgroup in which M is a “ skew-persymmetric” matrix (skew2
symmetric about the anti-diagonal), and thus this subgroup has order q ((n/2) −(n/2))/2 . Similarly, one can verify that K∩G is the subgroup in which A is an arbitrary upper-triangular matrix
2 2
with ones on the diagonal and B = J(AT )−1 J. Thus this subgroup has order q ((n ) −(n/2))/2 .
We have
(H ∩ G)(K ∩ G) ⊆ H3
2

and so |H3 | ≥ q (n/2) −(n/2) . A symmetric argument shows that |H1 | has the same order. It is
also easy to verify that |H2 | = (q − 1)n/2 . In the notation of Theorem 16, we have
r=O



|G| log |G|
|H1 ||H2 ||H3 |



≤O



q
q−1

n/2

((n2 − n) log q/2)

which can be absorbed into the |G|ǫ term.
We note that in all of the cases just considered in Sections 5.1, 5.2, 5.3, one obtains the
same results for the special or projective (or both) variants, by following essentially the same
argument. To obtain results for the projective cases, we observe that quotient-ing all of the
groups in our decomposition by the center can only change the operation count by a factor of
some constant multiple of the size of the center, which in these cases is itself a constant.

6

A new exponent upper bound for all finite groups

In this section we prove a structural result for all finite groups that allows us to make use of the
reduction in Theorem 11. Just as Lev’s theorem regarding a large single subgroup allows one to
use the single subgroup reduction of Section 2 to obtain a non-trival upper bound for all finite
groups, the following theorem
√ gives a pair of subgroups for use in the reduction of Theorem
11.
We
use
this
to
obtain
a
2 exponent algorithm (under the assumption ω = 2). Note that
√
2 < 3/2, which is the best previous exponent achieved for arbitrary finite groups, under the
assumption ω = 2.
√

Theorem 23. There exists a monotone increasing function f (x) ≤ 2c log x log log x for a universal constant c ≥ 1, for which the following holds: every finite group G that is not a p-group has
proper subgroups H, K satisfying |HK| ≥ |G|/f (|G|).
Proof. If G is simple then by the Classification Theorem, we have several cases:
• G is cyclic of prime order. This case cannot arise since G is not a p-group.

• G is the alternating group An . Then we choose H = An−1 and K = {1} and we have
|HK| ≥ |G|/n, so as long as f (x) > log x, the theorem holds.

14

Name
Chevalley

Exceptional
Chevalley

Steinberg

Suzuki
Ree

Family
Aℓ (q)
Bℓ (q)
Cℓ (q)
Dℓ (q)
E6 (q)
E7 (q)
E8 (q)
F4 (q)
G2 (q)
2 A (q 2 )
ℓ
2 D (q 2 )
ℓ
2 E (q 2 )
6
3 D (q 3 )
4
2 B (q), q = 22n+1
2
2 F (q), q = 32n+1
4
2 G (q), q = 32n+1
2

|W |
(ℓ + 1)!
2ℓ ℓ!
2ℓ ℓ!
2ℓ−1 ℓ!
O(1)
O(1)
O(1)
O(1)
O(1)
2⌈ℓ/2⌉ ⌈ℓ/2⌉!
2ℓ−1 (ℓ − 1)!
O(1)
O(1)
O(1)
O(1)
O(1)

|G|
2
q Θ(ℓ )
2
q Θ(ℓ )
2
q Θ(ℓ )
2
q Θ(ℓ )
q Θ(1)
q Θ(1)
q Θ(1)
q Θ(1)
q Θ(1)
2
q Θ(ℓ )
2
q Θ(ℓ )
q Θ(1)
q Θ(1)
q Θ(1)
q Θ(1)
q Θ(1)

Figure 2: Families of finite groups G of Lie type, together with the size of their associated Weyl
group W . These include all simple finite groups other than cyclic groups, the alternating groups,
the 26 sporadic groups, and the Tits group. See [Lev92, Wik17] for sources.
• G is a finite group of Lie Type. Then G has a (B, N ) pair (the Tits Group is an exception;
it does not have a (B, N ) pair, but it is a single finite group so it can be treated along
with the sporadic groups in the next case). Let W = N/(B ∩ N ) be the Weyl group, and
from the axioms of a (B, N ) pair, we have that the double cosets BwB with w ∈ W cover
G (the w denotes a lift to N ⊆ G). Thus there is some double coset BwB of size at least
|G|/|W |. Taking H = B w and K = B, we see that |HK| = |BwB| ≥ |G|/|W |. Now we
verify that we can choose f so that for each of the families in Figure 2, f (|G|) > |W |.
• G is one of the sporadic groups. Let C be the largest order of a sporadic group. Then by
choosing f (x) > C, the theorem holds for H = K = {1} in this case.

If G is not simple, then let N be a maximal normal subgroup of G, so that G/N is simple. We
have two cases:

• G/N is a p-group. Since G is not a p-group, we have that |G| = mpk for m > 1 and
′
(m, p) = 1. Let P be a p-Sylow subgroup of G. Then |P | = pk , and |N | = mpk for some
′
k < k. Then N P = G and both N and P are proper subgroups.
• G/N is a simple group that is not a p-group. Then apply the previous case analysis for
simple groups to obtain H/N, K/N , proper subgroups of G/N for which |(H/N )(K/N )| ≥
|G/N |/f (|G/N |). But then H, K are proper subgroups of G and
|HK| = |(H/N )(K/N )||N | ≥ |G/N ||N |/f (|G/N |) = |G|/f (|G/N |) ≥ |G|/f (|G|),
where the last inequality used the monotonicity of f .

Now we can apply the Theorem to achieve an exponent
ω = 2:

15

√
2 algorithm for all G, assuming

Theorem 24. If ω = 2, then for every finite group G, there is an exponent
computing the DFT with respect to G.

√
2 algorithm

Proof. Fix G. We describe a recursive algorithm. If G is a p-group, then we apply Theorem 13.
If |G| is the trivial group, then the DFT is trivial as well. Otherwise
let H, K be the subgroups
√
2− 2
, then we apply Theorem 11.
guaranteed by Theorem 23. If |H|, |K| are both
at most |G|
√
Otherwise one of H, K has size at least |G|2− 2 (WLOG say it is H) and we apply Corollary 4.
Let us now analyze the operation count. For this purpose, set δ = min{ǫ, 0.1}, and give
names to some constants:
• Let Aδ be the constant hidden in the O(|G|ω/2+δ + (|H||K|)ω/2+δ ) notation of Theorem
11.
• Let Bδ be the constant hidden in the [G : H] · O(|G|ω/2+δ ) notation of Corollary 4.

• Let B be the constant hidden in the O(|G| log |G|) notation of Theorem 13.

Let T (n) denote an upper bound on the running time of this recursive algorithm for any group
G of order n. For each fixed ǫ > 0, we will prove by induction on n that, for a universal constant
Cǫ ,
√
T (n) ≤ Cǫ n 2+ǫ log2 n.
This clearly holds for the base case of a p-group or the trivial group, provided Cǫ > B.
By choosing Cǫ sufficiently large,
√ we may assume that |G| is at least some fixed constant size,

and hence we may assume that 2c log |G| log log |G| · O(log |G|) term in the notation of Theorem
11 is bounded above by |G|ǫ/10 .
In the case that we apply Theorem 11, the cost is at most

|H| · T (|K|) + |K| · T (|H|) + Aδ (|H||K|)1+δ · |G|ǫ/10 ,
where |H|, |K| ≤ |G|2−

√

2

. Applying the induction hypothesis, we obtain:



T (n) ≤

2Cǫ n2−

≤

(2Cǫ (2 −
√

√ √
√
2 (2− 2)( 2+ǫ)

n

log2 (n2−

√

2

) + Aδ n2(2−

√
√
√ 2
2) + Aδ ) · n 2+(2− 2)ǫ+ǫ/10 log2 n


√
2)(1+δ)

· |G|ǫ/10

which is at most Cǫ n 2+ǫ log2 n as required, provided Cǫ > 10Aδ .
In the case that we apply Corollary 4, the cost is at most
[G : H] · T (|H|) + [G : H] · Bδ |G|1+δ ,
√

√

2− 2
and hence [G : H] ≤ |G| 2−1 . If we set α such that |H| = |G|α , and thus
where
√ |H| ≥ |G|
2 − 2 ≤ α ≤ 1, and apply the induction hypothesis, we obtain,

T (n) ≤
<
which is at most Cǫ n

7

√

2+ǫ

Cǫ n1−α nα(
Cǫ n

√
2+ǫ

√
2+ǫ)

log2 (n/2) + Bδ n1−α n1+δ

(log n)(log n − 1) + Bδ n

√
2+δ

log2 n as required, provided Cǫ ≥ Bδ .

Conclusions

There are two significant open problems that naturally follow from the results in this paper.
First, can one obtain exponent ω/2 algorithms for all finite groups? This might be possible
by proving a more sophisticated version of Theorem 23, which, for example, manages to upper

16

bound |H ∩ K|. Also of interest would be a proof of Theorem 23 that does not need the
Classification Theorem.
A second question is whether the dependence on ω can be removed. Alternatively, can one
show that a running time that depends on ω is necessary by showing that an exponent one DFT
for a certain family of groups would imply ω = 2?

Acknowledgements. We thank the SODA 2018 referees for their careful reading of this
paper and many useful comments.

References
[Bau91]

Ulrich Baum. Existence and efficient construction of fast Fourier transforms on
supersolvable groups. computational complexity, 1(3):235–256, Sep 1991.

[BCS97]

P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory,
volume 315 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag,
1997.

[Bet84]

Thomas Beth. Verfahren der schnellen Fourier-Transformation. Teubner, 1984.

[Car89]

Roger W Carter. Simple groups of Lie type, volume 22. John Wiley & Sons, 1989.

[CB93]

Michael Clausen and Ulrich Baum. Fast Fourier transforms. Wissenschaftsverlag,
1993.

[CH17]

Michael Clausen and Paul Hühne. Linear time fourier transforms of sn-k-invariant
functions on the symmetric group sn. In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’17, pages
101–108, New York, NY, USA, 2017. ACM.

[Cla89]

Michael Clausen. Fast generalized Fourier transforms. Theoretical Computer Science, 67(1):55–63, 1989.

[HJ91]

Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge
University Press, 1991.

[Lev92]

Arieh Lev. On large subgroups of finite groups. Journal of Algebra, 152(2):434–438,
1992.

[LG14]

François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings
of the 39th international symposium on symbolic and algebraic computation, pages
296–303. ACM, 2014.

[LR92]

John D. Lafferty and Daniel Rockmore. Fast fourier analysis for SL2 over a finite
field and related numerical experiments. Experiment. Math., 1(2):115–139, 1992.

[Mas98]

David Keith Maslen. The efficient computation of fourier transforms on the symmetric group. Math. Comput., 67(223):1121–1147, 1998.

[MR97a]

David Maslen and Daniel Rockmore. Separation of variables and the computation
of Fourier transforms on finite groups, I. Journal of the American Mathematical
Society, 10(1):169–214, 1997.

[MR97b]

David K Maslen and Daniel N Rockmore. Generalized FFTs – a survey of some
recent results. In Groups and Computation II, volume 28, pages 183–287. American
Mathematical Soc., 1997.

[MR00]

David K Maslen and Daniel N Rockmore. Double coset decompositions and computational harmonic analysis on groups. Journal of Fourier Analysis and Applications,
6(4):349–388, 2000.

17

[MRW16a] David Maslen, Daniel N Rockmore, and Sarah Wolff. The efficient computation of
Fourier transforms on semisimple algebras. arXiv preprint arXiv:1609.02634, 2016.
To appear in Journal of Fourier Analysis and Applications.
[MRW16b] David Maslen, Daniel N Rockmore, and Sarah Wolff. Separation of variables and the
computation of Fourier transforms on finite groups, II. Journal of Fourier Analysis
and Applications, pages 1–59, 2016.
[Roc95]

Daniel N. Rockmore. Fast Fourier transforms for wreath products. Applied and
Computational Harmonic Analysis, 2(3):279 – 292, 1995.

[Roc97]

Daniel Rockmore. Some applications of generalized FFTs. In Proceedings of the
1995 DIMACS Workshop on Groups and Computation, pages 329–369. June, 1997.

[Roc02]

Daniel N Rockmore. Recent progress and applications in group FFTs. In Signals,
Systems and Computers, 2002. Conference Record of the Thirty-Sixth Asilomar Conference on, volume 1, pages 773–777. IEEE, 2002.

[Wik17]

Wikipedia. List of finite simple groups — wikipedia, the free encyclopedia, 2017.
[Online; accessed 30-June-2017].

18

