Lafferty, John D.; Rockmore, Daniel Fast Fourier analysis for \(SL_ 2\) over a finite field and related numerical experiments. (English) Zbl 0773.65091 Exp. Math. 1, No. 2, 115-139 (1992). Let \(G:=SL_ 2(F_ q)\). The authors prove that the minimal number of arithmetic operations to compute a Fourier transform of \(f\in L^ 2(G)\) and to recover \(f\) via Fourier inversion is \(O(q^ 2\log q)\), respectively. The result is based on the fact that \(G\) contains the metabelian subgroup of upper triangular matrices and on symmetry adapted fast Fourier transforms.The paper builds up on M. Clausen [SIAM J. Comput. 18, No. 3, 584- 593 (1989; Zbl 0677.68028)] and previous results of the second author [Adv. Appl. Math. 11, No. 2, 164-204 (1990; Zbl 0709.65126)]. The computation of the relevant Fourier transform permits extensive numerical investigations of the spectra of families of Cayley graphs on \(G\). Reviewer: G.Steidl (Rostock) Cited in 3 ReviewsCited in 9 Documents MSC: 65T40 Numerical methods for trigonometric approximation and interpolation 65Y20 Complexity and performance of numerical algorithms 65J10 Numerical solutions to equations with linear operators 43A25 Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 20C15 Ordinary representations and characters Keywords:finite field; Fourier analysis on finite groups; representation theory; spectrum of Cayley graphs; Fourier transform; Fourier inversion; fast Fourier transforms Citations:Zbl 0677.68028; Zbl 0709.65126 PDFBibTeX XMLCite \textit{J. D. Lafferty} and \textit{D. Rockmore}, Exp. Math. 1, No. 2, 115--139 (1992; Zbl 0773.65091) Full Text: DOI EuDML EMIS References: [1] Alon N., Combinatorica 6 pp 83– (1983) · Zbl 0661.05053 [2] Alon N., J. Combin. Theory 38 pp 73– (1985) · Zbl 0549.05051 [3] Baum U., Doctoral dissertation, in: ”Existence and efficient construction of fast Fourier transforms on supersolvable groups” (1991) [4] Baum U., SIAM J. Comput. 20 pp 451– (1991) · Zbl 0729.65115 [5] Baum U., Applicable Algebra in Engineering, Communication and Computing 2 pp 35– (1991) · Zbl 0734.65103 [6] Bien F., Notices of the AMS 36 (1) pp 5– (1989) [7] Biggs N., Algebraic Graph Theory (1974) · Zbl 0797.05032 [8] Brooks R., ”Some relations between spectral geometry and number theory” (1991) [9] Bshouty N., J. of Algorithms 9 pp 354– (1988) · Zbl 0653.65032 [10] Buck M. W., SIAM J. Algebraic and Discrete Methods 7 pp 282– (1986) · Zbl 0612.68061 [11] Chung F., J. Amer. Math. Soc. 2 pp 187– (1989) [12] Clausen M., J. Theor. Comp. Sci. 67 pp 55– (1989) · Zbl 0677.65143 [13] Clausen M., SIAM J. Comput. 18 pp 584– (1989) · Zbl 0677.68028 [14] Diaconis P., Group Representations in Probability and Statistics (1988) · Zbl 0695.60012 [15] Diaconis P., J. Amer. Math. Soc. 3 pp 297– (1990) [16] Dickson L., Linear Groups with an Exposition of the Galois Field Theory (1958) · Zbl 0082.24901 [17] Jordan H., Amer. J. Math. 29 pp 387– (1907) · JFM 38.0175.01 [18] Kesten H., Trans. Amer. Math. Soc. 92 pp 336– (1959) [19] Kantor W., Georn. Ded. 36 pp 67– (1990) [20] Kloosterman H. D., Ann. of Math. 47 pp 317– (1946) · Zbl 0063.03262 [21] Lenstra A. K., Handbook of Theoretical Computer ScienceA: Algorithms and Complexity pp 673– (1990) [22] Lubotzky A., ”Discrete groups, expanding graphs, and invariant measures” · Zbl 1183.22001 [23] Naimark M. A., Theory of Group Representations (1980) [24] Piatetski-Shapiro I., Complex Representations of GL[2, K] for Finite Fields K (1983) · Zbl 0513.20026 [25] Rockmore D., Adv. in Appl. Math. 11 pp 164– (1990) · Zbl 0709.65126 [26] Rockmore D., ”Efficient computation of Fourier inversion for finite groups” (1990) · Zbl 0709.65125 [27] Sarnak P., Some Applications of Modular Forms (1990) · Zbl 0721.11015 [28] Schur I., J. Reine Angew. Math. 132 pp 85– (1907) [29] Serre J. P., Linear Representations of Finite Groups (1977) · Zbl 0355.20006 [30] Silberger A., Osaka J. Math. 6 pp 329– (1969) [31] Suzuki M., Group Theory, volume I (1982) [32] Tanaka S., Osaka J. Math. 4 pp 65– (1967) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.