On finite pseudorandom binary sequences III: The Liouville function, I

DOI10.4064/AA-87-4-367-390MaRDI QIDQ4238756zbMATH OpenOpenAlexFDO

Authors Julien Cassaigne, Sébastien Ferenczi, Joël Rivat, András Sárközy, Christian Mauduit

Publication date 18 May 1999

Published in Acta Arithmetica (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/207226, http://matwbn.icm.edu.pl/ksiazki/aa/aa87/aa8744.pdf

zbMATH Keywords

complexity of sequencecorrelation measurefinite pseudorandom binary sequencesLiouville functionpseudorandom properties of arithmetic sequenceswell-distribution measure

Mathematics Subject Classification ID

Pseudo-random numbers; Monte Carlo methods (11K45) Random number generation in numerical analysis (65C10)

Review text

This is the third part of an extensive investigation on pseudorandom properties of arithmetic sequences initiated by \textit{C. Mauduit} and \textit{A. Sarközy}, see [Acta Arith. 82, 365--377 (1997; Zbl 0886.11048) and J. Number Theory 73, 256--276 (1998; Zbl 0916.11047)]. The authors mainly consider the ``correlation measure of order \(k\) of binary sequences over \(\{-1,+1\}\). In part I of their work they were concerned with the sequence \(e_n=({n\over p})\), \(n=1,\dots,N\) of Legendre symbols, \(p\) a prime number. In the present paper the authors investigate the sequence \(\lambda(n)=(-1)^{\Omega (n)}\) and \(\gamma(n)=(-1)^{(\omega(n)}\), where \(\omega(n)\) denotes the number of distinct prime factors of \(n\) and \(\Omega(n)\) the number of prime factors of \(n\) counted with multiplicity. The authors obtain estimates for a ``well-distribution measure and for the ``correlation measure of order \(k\). Moreover, they study the complexity of the sequences and a connection between correlation and complexity.

Recommendations

• A note on the pseudorandomness of the Liouville function
• On finite pseudorandom binary sequences IV: The Liouville function, II
• On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol

Cited in

(23)

• On the measures of pseudorandomness of binary sequences.
• Finite and infinite pseudorandom binary words
• Congruence properties of multiplicative functions on sumsets and monochromatic solutions of linear equations
• On finite pseudorandom sequences of k symbols.
• On finite pseudorandom sequences of \(k\) symbols
• Pseudorandom sequences derived from automatic sequences
• On the correlation measures of subsets
• The structure of logarithmically averaged correlations of multiplicative functions, with applications to the Chowla and Elliott conjectures
• More constructions of pseudorandom sequences of \(k\) symbols
• On pseudorandomness in families of sequences derived from the Legendre symbol
• On the pseudorandomness of the Liouville function of polynomials over a finite field
• Multiplicative functions in short intervals
• On the correlation of families of pseudorandom sequences of \(k\) symbols
• New pseudorandom sequences constructed by quadratic residues and Lehmer numbers
• A large family of pseudorandom binary lattices
• Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin–Shapiro sequences
• Equivalence of the Logarithmically Averaged Chowla and Sarnak Conjectures
• A note on certain modular constructions of pseudorandom binary sequences with composite moduli
• On the bivariate Erdős-Kac theorem and correlations of the Möbius function
• A note on the pseudorandomness of the Liouville function
• Pseudorandom properties of prime factors
• -generalized prime factors counting functions
• On a problem of D.H. Lehmer and pseudorandom binary sequences

This page was built for publication: On finite pseudorandom binary sequences III: The Liouville function, I

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