Character sums and generating sets (Q2829801)

To find generating sets of small order for given groups is a problem of interest in computational algebra. For the multiplicative group of the finite field \(\mathbb F_{p^d}\), \textit{F. R. K. Chung} showed in [J. Am. Math. Soc. 2, No. 2, 187--195 (1989; Zbl 0678.05037)]] that the set \(x+\mathbb F_p=\{x+t:t\in \mathbb F_p\}\) forms a generating set. The finite field \(\mathbb F_{p^d}\cong \mathbb F_p[x]/f\) for an irreducible polynomial \(f(x)\in \mathbb F_p[x]\) of degree \(d\geq 2\).NEWLINENEWLINEThe main purpose of the present paper is to find generating sets of small order for the multiplicative group of the algebra \(A=\mathbb F_p[x]/f^e\) with \(f(x)\in \mathbb F_p[x]\) being an irreducible polynomial of degree \(d\geq 2\) and \(p\geq e>1\). This multiplicative group is no longer a cyclic group but it is finite abelian.NEWLINENEWLINENEWLINEFor a finite abelian group \(G\) and a subset \(S\subset G\), the set of eigenvalues of the adjacency matrix of the corresponding Cayley graph can be given as the set of character sum values \(\chi(S)\) where \(\chi\) is a character of \(G\). Using this result and a result from Chung [loc. cit.], the authors prove that for a subset \(S\) to be a generating set for a finite abelian group \(G\), the absolute value of the character sum \(\chi(S)\) must be less than \(| S|\) for any nontrivial character \(\chi\) of \(G\).NEWLINENEWLINENEWLINEFirst of all they present a lemma showing that the multiplicative group of \(A\) is isomorphic to the direct product of a cyclic group of order \(p^d-1\) and an elementary abelian group of order \(p^{d(e-1)}\).NEWLINENEWLINEThen by considering \(A\) as an \(\mathbb F_p\) and \(\mathbb F_q\) algebra where \(q=p^d\), respectively, the authors give two different generating sets for \(A^\ast\). The required conditions for the second construction given in Theorem 5 is more relaxed but then the size of the generating set becomes larger compared to the one given in Theorem 4. In Theorem 6 a generating set of smaller size is given considering \(A\) as an algebra over a subfield \(K\) of \(\mathbb F_q\).NEWLINENEWLINENEWLINEIn Section 4 of the paper the authors analyze whether the required conditions for the generating sets are too restrictive. In the last section they provide a construction of a regular directed expander graph which is actually the Cayley graph corresponding to \(A^\ast\) and the generating set \(S\) given in Theorem 6.NEWLINENEWLINEFor the entire collection see [Zbl 1345.11003].