{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T07:25:53Z","timestamp":1778657153331,"version":"3.51.4"},"reference-count":26,"publisher":"American Mathematical Society (AMS)","issue":"223","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n This paper introduces new techniques for the efficient computation of Fourier transforms on symmetric groups and their homogeneous spaces. We replace the matrix multiplications in Clausen\u2019s algorithm with sums indexed by combinatorial objects that generalize Young tableaux, and write the result in a form similar to Horner\u2019s rule. The algorithm we obtain computes the Fourier transform of a function on\n \n \n \n \n S<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n S_n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in no more than\n \n \n \n \n \n 3<\/mml:mn>\n 4<\/mml:mn>\n <\/mml:mfrac>\n n<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n \n S<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n \n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n \\frac {3}{4} n(n-1) |S_n|<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n multiplications and the same number of additions. Analysis of our algorithm leads to several combinatorial problems that generalize path counting. We prove corresponding results for inverse transforms and transforms on homogeneous spaces.\n <\/p>","DOI":"10.1090\/s0025-5718-98-00964-8","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1121-1147","source":"Crossref","is-referenced-by-count":33,"title":["The efficient computation of Fourier transforms on the symmetric group"],"prefix":"10.1090","volume":"67","author":[{"given":"David","family":"Maslen","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"key":"1","series-title":"Leitf\\\"{a}den der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics]","isbn-type":"print","volume-title":"Verfahren der schnellen Fourier-Transformation","volume":"61","author":"Beth, Thomas","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/3519023636"},{"key":"2","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, M. Clausen, A. Shokrollahi, Algebraic Complexity Theory, Springer-Verlag, Berlin, 1996.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"3","isbn-type":"print","volume-title":"Fast Fourier transforms","author":"Clausen, Michael","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3411163615"},{"issue":"204","key":"4","doi-asserted-by":"publisher","first-page":"833","DOI":"10.2307\/2153256","article-title":"Fast Fourier transforms for symmetric groups: theory and implementation","volume":"61","author":"Clausen, Michael","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0304-3975(89)90021-2","article-title":"Fast generalized Fourier transforms","volume":"67","author":"Clausen, Michael","year":"1989","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"6","unstructured":"\\bysame, Beitr\u00e4ge zum Entwurf schneller Spektraltransformationen, Habilitationsschrift, Fakult\u00e4t f\u00fcr Informatik der Universit\u00e4t Karlsruhe (TH), 1988."},{"key":"7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.2307\/2003354","article-title":"An algorithm for the machine calculation of complex Fourier series","volume":"19","author":"Cooley, James W.","year":"1965","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"949","DOI":"10.1214\/aos\/1176347251","article-title":"A generalization of spectral analysis with application to ranked data","volume":"17","author":"Diaconis, Persi","year":"1989","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"key":"9","unstructured":"\\bysame, Group representations in probability and statistics, IMS, Hayward, CA, 1988."},{"issue":"2","key":"10","doi-asserted-by":"publisher","first-page":"297","DOI":"10.2307\/1990955","article-title":"Efficient computation of the Fourier transform on finite groups","volume":"3","author":"Diaconis, Persi","year":"1990","journal-title":"J. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/dimacs\/011\/06","article-title":"Efficient computation of isotypic projections for the symmetric group","author":"Diaconis, Persi","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0821865994"},{"key":"12","isbn-type":"print","volume-title":"Fast transforms","author":"Elliott, Douglas F.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/0122370805"},{"key":"13","doi-asserted-by":"publisher","first-page":"712","DOI":"10.2307\/1968951","article-title":"Rings with minimal condition for left ideals","volume":"40","author":"Hopkins, Charles","year":"1939","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"14","series-title":"Mathematical Sciences Research Institute Publications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9641-3","volume-title":"Coxeter graphs and towers of algebras","volume":"14","author":"Goodman, Frederick M.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0387969799"},{"key":"15","series-title":"Encyclopedia of Mathematics and its Applications","isbn-type":"print","volume-title":"The representation theory of the symmetric group","volume":"16","author":"James, Gordon","year":"1981","ISBN":"https:\/\/id.crossref.org\/isbn\/0201135159"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF01459500","article-title":"Fourier transforms with respect to monomial representations","volume":"297","author":"Linton, Stephen A.","year":"1993","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"17","series-title":"Oxford Mathematical Monographs","isbn-type":"print","volume-title":"Symmetric functions and Hall polynomials","author":"Macdonald, I. G.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0198535309"},{"key":"18","unstructured":"D. Maslen, Efficient computation of Fourier transforms on compact groups, J. Fourier Anal. Appl. (to appear)."},{"key":"19","doi-asserted-by":"crossref","unstructured":"D. Maslen and D. Rockmore Generalized FFTs - a survey of some recent results, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Groups and Computation, II, L. Finkelstein and W. Kantor (eds.), (1996), 183\u2013237.","DOI":"10.1090\/dimacs\/028\/13"},{"issue":"1","key":"20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1090\/S0894-0347-97-00219-1","article-title":"Separation of variables and the computation of Fourier transforms on finite groups. I","volume":"10","author":"Maslen, David K.","year":"1997","journal-title":"J. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"key":"21","unstructured":"\\bysame, Separation of variables and the efficient computation of Fourier transforms on finite groups, II, (preprint)."},{"key":"22","doi-asserted-by":"crossref","unstructured":"D. Rockmore, Applications of generalized FFTs, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Groups and Computation, II, L. Finkelstein and W. Kantor (eds.), (1996).","DOI":"10.1090\/dimacs\/028\/19"},{"key":"23","series-title":"Graduate Texts in Mathematics, Vol. 42","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9458-7","volume-title":"Linear representations of finite groups","author":"Serre, Jean-Pierre","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/0387901906"},{"issue":"4","key":"24","doi-asserted-by":"publisher","first-page":"919","DOI":"10.2307\/1990995","article-title":"Differential posets","volume":"1","author":"Stanley, Richard P.","year":"1988","journal-title":"J. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"key":"25","isbn-type":"print","first-page":"145","article-title":"Variations on differential posets","author":"Stanley, Richard P.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/038797170X"},{"key":"26","first-page":"3","article-title":"Locally semisimple algebras. Combinatorial theory and the \ud835\udc3e\u2080-functor","author":"Vershik, A. M.","year":"1985"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00964-8\/S0025-5718-98-00964-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00964-8\/S0025-5718-98-00964-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:48:17Z","timestamp":1776721697000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00964-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":26,"journal-issue":{"issue":"223","published-print":{"date-parts":[[1998,7]]}},"alternative-id":["S0025-5718-98-00964-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00964-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}