On finite pseudorandom sequences of \(k\) symbols. (Q1866459)

In a series of papers [Zbl 0886.11048; Zbl 0916.11047; Zbl 0920.11053; Zbl 0961.11026; Zbl 0973.11076; Zbl 1011.11054; Zbl 1126.11330] \textit{C. Mauduit} and \textit{A. Sárközy}, with some co-authors, studied binary pseudorandom sequences. In [Acta Arith. 82, 365--377 (1997; Zbl 0886.11048)] they introduced a well-distribution measure and a correlation measure and considered a binary sequence \(E_N=(e_1,\ldots,e_N)\) as a `good' pseudorandom sequence if both these measures are \(o(N)\) as \(N \to \infty\). A lot of important binary sequences were tested with respect to these measures in their series of papers (loc. cit.). In the paper under review two possible generalizations of these measures for pseudorandomness to sequences \(E_N\) over a \(k\)-element alphabet, \(k \geq 3\), are introduced: One approach measures the frequency of elements and \(l\)-tuples of the alphabet in the sequence leading to the so-called \(f\)-well-distribution measure \(\delta(E_N)\) and the \(f\)-correlation measure \(\gamma_l(E_N)\), respectively. The other pair of measures, the \(\mathcal{E}\)-well-distribution measure \(\Delta(E_N)\) and the \(\mathcal{E}\)-correlation measure \(\Gamma_l(E_N)\), involves all bijections of the alphabet to the \(k\)th roots of unity and then utilizes the same formulas as for \(k=2\). In the following it is proved that these measures are `nearly equivalent' in the following sense: \[ \begin{aligned} &k/(k-1)\delta(E_N)\leq \Delta(E_N)\leq k \delta(E_N), \tag{a}\\ &1/k^l \Gamma_l(E_N)\leq \gamma_l(E_N)\leq \sum_{t=1}^l {l \choose t} (k-1)^t \Gamma_t(E_N).\tag{b} \end{aligned} \] Finally the `Legendre symbol construction' studied in [Parts 1,2; cf. Zbl 0886.11048; Zbl 0916.11047] is generalized to a \(k\)-element alphabet, and it is shown that the arising sequence is a `good' pseudorandom sequence in terms of \(\delta\) and \(\gamma_l\).