Some notes on the pseudorandomness of Legendre symbol and Liouville function

2024/11/08 by Grünberger, Johannes, Winterhof, Arne
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2411.05471

Abstract

We improve bounds on the degree and sparsity of Boolean functions representing the Legendre symbol as well as on the Nth linear complexity of the Legendre sequence. We also prove similar results for both the Liouville function for integers and its analog for polynomials over \mathbbF₂, or more general for any (binary) arithmetic function which satisfies f(2n)=-f(n) for n=1,2,…

Related

• Improved lower bound on the family complexity of Legendre sequences
• Pseudorandom binary sequences: quality measures and number-theoretic constructions
• The Binary Linearization Complexity of Pseudo-Boolean Functions
• Families of sequences with good family complexity and cross-correlation measure
• Some interesting number theory problems