On finite pseudorandom sequences of \(k\) symbols.
type: Item
instance of: scholarly article
title: On finite pseudorandom sequences of \(k\) symbols.
zbMATH Open document ID: 1049.11090
DOI: 10.1016/S0019-3577(02)90008-X
author: Christian Mauduit
author: András Sárközy
published in: Indagationes Mathematicae. New Series
publication date: 2002-01-01T00:00:00Z
review text: 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\).
reviewed by: Gerhard Dorfer
Mathematics Subject Classification ID: 11K45
zbMATH DE Number: 1893632
zbMATH Keywords: pseudorandom sequences
zbMATH Keywords: well-distribution measure
zbMATH Keywords: correlation measure
MaRDI profile type: Publication
cites work: On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
cites work: On finite pseudorandom binary sequences. II: The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction
cites work: On finite pseudorandom binary sequences III: The Liouville function, I
cites work: On finite pseudorandom binary sequences IV: The Liouville function, II
cites work: On finite pseudorandom binary sequences. V: On \((n\alpha)\) and \((n^2\alpha)\) sequences
cites work: On finite pseudorandom binary sequences. VI: On \((n^k\alpha)\) sequences
cites work: Q3900124
cites work: Q5794285
description: scientific article; zbMATH DE number 1893632