On (not) computing the Möbius function using bounded depth circuits
From MaRDI portal
Abstract: Any function F : {0,...,N-1} -> {-1,1} such that F(x) can be computed from the binary digits of x using a bounded depth circuit is orthogonal to the Mobius function mu in the sense that E_{0 <= x <= N-1} mu(x)F(x) = o(1). The proof combines a result of Linial, Mansour and Nisan with techniques of Katai and Harman-Katai, used in their work on finding primes with specified digits.
Recommendations
- On the Fourier-Walsh spectrum of the Moebius function
- scientific article; zbMATH DE number 4103067
- Fonction sommatoire de la fonction de Möbius 1. Majorations expérimentales
- Number-theoretic functions which are equivalent to number of divisors
- The Möbius function is strongly orthogonal to nilsequences
Cites work
- Constant depth circuits, Fourier transform, and learnability
- Distribution of digits of primes in q-ary canonical form
- Exponential Sums Formed with the Möbius Function
- Multiplicative number theory. I. Classical theory
- On a problem of Gelfond: the sum of digits of prime numbers
- ON SOME INFINITE SERIES INVOLVING ARITHMETICAL FUNCTIONS (II)
- Primes in arithmetic progressions
- Primes with preassigned digits II
Cited in
(30)- Number-theoretic functions which are equivalent to number of divisors
- Möbius disjointness for models of an ergodic system and beyond
- Möbius disjointness for topological models of ergodic measure-preserving systems with quasi-discrete spectrum
- Measure complexity and Möbius disjointness
- The logarithmic Sarnak conjecture for ergodic weights
- On Sarnak's conjecture and Veech's question for interval exchanges
- Möbius orthogonality of sequences with maximal entropy
- Monotone Boolean functions capture their primes
- Bounds on short character sums and \(L\)-functions with characters to a powerful modulus
- Möbius disjointness for analytic skew products
- Algebraic trace functions over the primes
- On the Fourier-Walsh spectrum of the Moebius function. II
- Substitutions and Möbius disjointness
- The Möbius function and statistical mechanics
- Blocks of digits of increasing size in primes
- 0-1 sequences of the Thue-Morse type and Sarnak's conjecture
- Odometers and Toeplitz systems revisited in the context of Sarnak's conjecture
- On the Fourier-Walsh spectrum of the Moebius function
- Möbius orthogonality for the Zeckendorf sum-of-digits function
- Equivalence of the Logarithmically Averaged Chowla and Sarnak Conjectures
- Disjointness of Moebius from horocycle flows
- Sums with the Möbius function twisted by characters with powerful moduli
- Prime number theorem for regular Toeplitz subshifts
- Bracket words along Hardy field sequences
- Synchronizing automatic sequences along Piatetski-Shapiro sequences
- Primes as sums of Fibonacci numbers
- Correlations of the Möbius and Liouville functions with their partial sums
- Möbius orthogonality for q-semimultiplicative sequences
- Prime numbers along Rudin-Shapiro sequences
- The Möbius function and continuous extensions of rotations
This page was built for publication: On (not) computing the Möbius function using bounded depth circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168449)
