Fast Fourier Analysis for SL₂ over a Finite Field and Related Numerical Experiments

REFERENCES

• Alon , N. 1983 . “Eigenvalues and expanders” . Combinatorica , 6 : 83 – 96 . [Alon 1983]
   Google Scholar
• Alon , N. and Milman , V. D. 1985 . “λ1, isoperimetric inequalities for graphs and superconcentrators” . J. Combin. Theory , B38 : 73 – 88 . [Alon and Milman 1985]
   Google Scholar
• Baum , U. 1991 . “Existence and efficient construction of fast Fourier transforms on supersolvable groups” , Doctoral dissertation Institut für Informatik, Universität Bonn. . [Baum 1991]
   Google Scholar
• Baum , U. and Clausen , M. 1991 . “Some lower and upper complexity bounds for generalized Fourier transforms and their inverses” . SIAM J. Comput. , 20 : 451 – 459 . [Baum and Clausen 1991]
   Web of Science ®Google Scholar
• Baum , U. , Clausen , M. and Tietz , B. 1991 . “Improved upper complexity bounds for the discrete Fourier transform” . Applicable Algebra in Engineering, Communication and Computing , 2 : 35 – 43 . [Baum et al. 1991]
   Google Scholar
• Bien , F. 1989 . “Constructions of telephone networks by group representations” . Notices of the AMS , 36 ( 1 ) : 5 – 22 . [Bien 1989]
   Google Scholar
• Biggs , N. 1974 . Algebraic Graph Theory Cambridge , , UK : Cambridge University Press. . [Biggs 1974]
   Google Scholar
• Brooks , R. 1991 . “Some relations between spectral geometry and number theory” Department of Mathematics, UCL. . [Brooks 1991], technical report
   Google Scholar
• Bshouty , N. , Kaminski , M. and Kirkpatrick , D. 1988 . “Addition requirements for matrix and transposed matrix products” . J. of Algorithms , 9 : 354 – 364 . [Bshouty et al. 1988]
   Google Scholar
• Buck , M. W. 1986 . “Expanders and diffusers” . SIAM J. Algebraic and Discrete Methods , 7 : 282 – 304 . [Buck 1986]
   Google Scholar
• Chung , F. 1989 . “Diameters and eigenvalues” . J. Amer. Math. Soc. , 2 : 187 – 200 . [Chung 1989]
   Google Scholar
• Clausen , M. 1989 . “Fast generalized Fourier transforms” . J. Theor. Comp. Sci. , 67 : 55 – 63 . [Clausen 1989a]
   Web of Science ®Google Scholar
• Clausen , M. 1989 . “Fast Fourier transforms for metabelian groups” . SIAM J. Comput. , 18 : 584 – 593 . [Clausen 1989b]
   Web of Science ®Google Scholar
• Diaconis , P. 1988 . Group Representations in Probability and Statistics Hayward , CA : Institute of Mathematical Statistics. . [Diaconis 1988]
   Google Scholar
• Diaconis , P. and Rockmore , D. 1990 . “Efficient computation of the Fourier transform on finite groups” . J. Amer. Math. Soc. , 3 : 297 – 332 . [Diaconis and Rockmore 1990]
   Google Scholar
• Dickson , L. 1958 . Linear Groups with an Exposition of the Galois Field Theory New York : Dover. . [Dickson 1958]
   Google Scholar
• Jordan , H. 1907 . “Group characters of various types of linear groups” . Amer. J. Math. , 29 : 387 – 405 . [Jordan 1907]
   Google Scholar
• Kesten , H. 1959 . “Symmetric random walks on groups” . Trans. Amer. Math. Soc. , 92 : 336 – 354 . [Kesten 1959]
   Google Scholar
• Kantor , W. and Lubotzky , A. 1990 . “The probability of generating a finite classical group” . Georn. Ded. , 36 : 67 – 87 . [Kantor and Lubotzky 1990]
   Web of Science ®Google Scholar
• Kloosterman , H. D. 1946 . “The behavior of general theta functions under the modular group and the characters of binary modular congruence groups” . Ann. of Math. , 47 : 317 – 375 . 376 – 447 . [Kloosterman 1946]
   Web of Science ®Google Scholar
• Lenstra , A. K. and Lenstra , H. 1990 . “Algorithms in number theory”. ” . In Handbook of Theoretical Computer ScienceA: Algorithms and Complexity Edited by: Van Leeuwen , J. 673 – 717 . Cambridge , MA : MIT Press. . [Lenstra and Lenstra 1990]
   Google Scholar
• Lubotzky , A. “Discrete groups, expanding graphs, and invariant measures” [Lubotzky], (to appear)
   Google Scholar
• Naimark , M. A. and Stern , A. I. 1980 . Theory of Group Representations New York : Springer-Verlag. . [Naimark and Stern 1990]
   Google Scholar
• Piatetski-Shapiro , I. 1983 . Complex Representations of GL[2, K] for Finite Fields K Providence , RI : American Mathematical Society. . [Piatetski-Shapiro 1983], Cont. Math. 16
   Google Scholar
• Rockmore , D. 1990 . “Fast Fourier analysis for abelian group extensions” . Adv. in Appl. Math. , 11 : 164 – 204 . [Rockmore 1990a]
   Web of Science ®Google Scholar
• Rockmore , D. 1990 . “Efficient computation of Fourier inversion for finite groups” Harvard : Department of Mathematics. . [Rockmore 1990b], technical report
   Google Scholar
• Sarnak , P. 1990 . Some Applications of Modular Forms Cambridge , , UK : Cambridge Univ. Press. . [Sarnak 1990]
   Google Scholar
• Schur , I. 1907 . “Untersuchungen über die Darstellungen der endlichen Gruppen durch gebrochene lineare Substitutionen” . J. Reine Angew. Math. , 132 : 85 – 117 . [Schur 1907]
   Google Scholar
• Serre , J. P. 1977 . Linear Representations of Finite Groups New York : Springer-Verlag. . [Serre 1977]
   Google Scholar
• Silberger , A. 1969 . “An elementary construction of the representations of SL(2, GF(q))” . Osaka J. Math. , 6 : 329 – 338 . [Silberger 1969]
   Google Scholar
• Suzuki , M. 1982 . Group Theory, volume I New York : Springer-Verlag. . [Suzuki 1982]
   Google Scholar
• Tanaka , S. 1967 . “Construction and classification of irreducible representations of the special linear group of the second order over a finite field” . Osaka J. Math. , 4 : 65 – 84 . [Tanaka 1967]
   Google Scholar