# Masanori Koyama

Harvey Mudd College Mathematics 2007

Thesis Proposal: | Discrete Fourier Transform for Finite Groups |
---|---|

Thesis Report: | mkoyama-2007-thesis.pdf |

Thesis Poster: | mkoyama-2007-poster.pdf |

15 minutes Presentation: | 15min_presentation.pdf |

30 minutes Presentation: | mkoyama-2007-presentation |

Thesis Advisor: | Prof. Michael Orrison |

Second Reader: | Prof. Nathan Ryan |

## A Discrete Fourier Transform for Symmetric Group

A Discrete Fourier Transform (DFT) changes the basis in the Group Algebra from the standard basis to a Fourier basis, and efficient application of a DFT is called an Fast Fourier Transform (FFT). This research pertains to a particular algorithm of FFT called Decimation in Frequency (DIF). An efficient DIF has been established for commutative Algebra; however successful similar analogue for the non-commutative algebra has not been derived. In particular, sophisticated structure of the permutation bimodule has been deterring the computation of the runtime of a potentially fast DIF algorithm called Orrison-DIF. I will resolve this obstacle and compute

the general runtime of the algorithm for Symmetric group.