On (Not) Computing the Möbius Function Using Bounded Depth Circuits

DOI10.1017/S0963548312000284zbMath1279.11095arXiv1103.4991OpenAlexW2115726687MaRDI QIDQ3168449

Ben Green

Publication date: 31 October 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1103.4991

Mathematics Subject Classification ID

Analytic circuit theory (94C05) Multiplicative number theory (11N99)

Related Items (24)

Möbius disjointness for models of an ergodic system and beyond ⋮ 0-1 sequences of the Thue-Morse type and Sarnak’s conjecture ⋮ Odometers and Toeplitz systems revisited in the context of Sarnak's conjecture ⋮ Möbius orthogonality of sequences with maximal entropy ⋮ Möbius disjointness for analytic skew products ⋮ 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 ⋮ Prime numbers along Rudin-Shapiro sequences ⋮ The Möbius function and continuous extensions of rotations ⋮ Substitutions and Möbius disjointness ⋮ Möbius disjointness for topological models of ergodic measure-preserving systems with quasi-discrete spectrum ⋮ Blocs de chiffres de taille croissante dans les nombre premiers ⋮ Measure complexity and Möbius disjointness ⋮ The logarithmic Sarnak conjecture for ergodic weights ⋮ Disjointness of Moebius from Horocycle Flows ⋮ Monotone Boolean functions capture their primes ⋮ On Sarnak's conjecture and Veech's question for interval exchanges ⋮ Algebraic trace functions over the primes ⋮ Sums with the Möbius function twisted by characters with powerful moduli ⋮ Bounds on short character sums and \(L\)-functions with characters to a powerful modulus ⋮ Möbius orthogonality for \(q\)-semimultiplicative sequences ⋮ Prime number theorem for regular Toeplitz subshifts ⋮ The Möbius function and statistical mechanics

Cites Work

• Unnamed Item
• On a problem of Gelfond: the sum of digits of prime numbers
• Distribution of digits of primes in \(q\)-ary canonical form
• Constant depth circuits, Fourier transform, and learnability
• Primes with preassigned digits II
• Exponential Sums Formed with the Möbius Function
• Primes in arithmetic progressions
• ON SOME INFINITE SERIES INVOLVING ARITHMETICAL FUNCTIONS (II)

This page was built for publication: On (Not) Computing the Möbius Function Using Bounded Depth Circuits