Inequalities for finite group permutation modules

General theory for finite permutation groups (20B05) Group rings of finite groups and their modules (group-theoretic aspects) (20C05) Ordinary representations and characters (20C15) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Fourier and Fourier-Stieltjes transforms on nonabelian groups and on semigroups, etc. (43A30) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: If f is a nonzero complex-valued function defined on a finite abelian group A and hat f is its Fourier transform, then |Supp (f)||Supp {hat f)| ge |A|, where Supp (f) and Supp (hat f) are the supports of f and hat f. In this paper we generalize this known result in several directions. In particular, we prove an analogous inequality where the abelian group A is replaced by a transitive right G-set, where G is an arbitrary finite group. We obtain stronger inequalities when the G-set is primitive and we determine the primitive groups for which equality holds. We also explore connections between inequalities of this type and a result of Chebotar"ev on complex roots of unity, and we thereby obtain a new proof of Chebotar"ev's theorem.

Review text

In a paper from 1989, Donoho and Stark proved what must be the simplest formulation of the uncertainty principle. The reviewer stated it in her book [Fourier analysis on finite groups and applications, Cambridge University Press (1999; Zbl 0928.43001)] as the following theorem. The notation is that if \(A\) is a finite Abelian group and \(f\colon A\to\mathbb{C}\), then \(\widehat f\) is the Fourier transform and \(\text{supp}(f)\) is the set of elements of \(A\) on which \(f\) is non-0. Theorem A. If \(A\) is a finite Abelian group, \(|\text{supp}(f)||\text{supp}(\widehat f)|\geq|A|\). In the present extremely interesting paper, the authors use the modern algebraic formulation of Fourier analysis to vastly generalize, simplify and blow life into the subject. Their Theorem B generalizes Theorem A in 3 ways. The group \(G\) need not be Abelian. The field \(F\) need not be the complex numbers. The function \(f\) need not be defined on the group \(G\) itself; it can be defined instead on an arbitrary transitive right \(G\)-set \(S\). In this language, the function \(f\) becomes a vector \(v\) in the right \(G\)-module \(F[S]\) of \(F\)-linear combinations of elements of \(S\). Then \(|\text{supp}(\widehat f)|\) becomes known as \(\dim_F\langle v\rangle\), where \(\langle v\rangle\) is the \(G\)-submodule of \(F[S]\) generated by \(v\). Theorem B. Let \(S\) be a finite transitive right \(G\)-set and \(0\neq v\in F[S]\), where \(F\) is an arbitrary field. Then \[ |\text{supp}(v)|\dim\langle v\rangle\geq|S|, \] where \(\langle v\rangle\) is the \(G\)-submodule of \(F[S]\) generated by \(v\). In fact, the proof of this result is even shorter than the proof we gave of Theorem A. When the transitive \(G\)-set \(S\) is primitive, one can say more. This is Theorem C. Theorem C. If \(S\) is a finite primitive right \(G\)-set, \(v\in F[S]\), and \(1\leq|\text{supp}(v)|<|S|\), then \[ (|\text{supp}(v)|+1)\dim_F\langle v\rangle\geq 2|S|. \] If \(|S|\) is prime then the \(G\)-set \(S\) is primitive. Then, assuming that the field \(F\) has characteristic 0, the authors prove an even better inequality. Theorem E. Under the same hypotheses as Theorem C, with \(S\) a transitive right \(G\)-set of prime order and \(F\) of characteristic 0, one has the inequality \[ |\text{supp}(v)|+\dim_F\langle v\rangle>|S|. \] Thus this theorem contains the main result of \textit{T. Tao} [Math. Res. Lett. 12, No. 1, 121-127 (2005; Zbl 1080.42002)] as a very special case, since Theorem E does not even assume the group \(G\) is Abelian. Theorem E is shown to be essentially equivalent to a result of Chebotarev saying that in the Vandermonde matrix \(V\) with \(ij\) entry \(\zeta^{ij}\), where \(\zeta\) is a primitive \(p\)-th root of 1, with \(p\) prime, all square submatrices are non-singular. Also the authors show that Theorem B implies a result of Diaconis and Shahshahani generalizing Theorem A to non-Abelian groups.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Inequalities for finite group permutation modules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5461373)