{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T20:33:17Z","timestamp":1773261197251,"version":"3.50.1"},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2012,8,24]],"date-time":"2012-08-24T00:00:00Z","timestamp":1345766400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2012,11]]},"abstract":"<jats:p>Any function <jats:italic>F<\/jats:italic>: {0,.\u00a0.\u00a0., <jats:italic>N<\/jats:italic> \u2212 1} \u2192 {\u22121,1} such that <jats:italic>F<\/jats:italic>(<jats:italic>x<\/jats:italic>) can be computed from the binary digits of <jats:italic>x<\/jats:italic> using a bounded depth circuit is orthogonal to the M\u00f6bius function \u03bc in the sense that\n<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548312000284_eqnU1\"\/><jats:tex-math>\n\\[\n\\frac{1}{N} \\sum_{0 \\leq x \\leq N-1} \\mu(x)F(x) &amp;#x2192; 0 \\quad\\text{as}~~ N &amp;#x2192; \\infty.\n\\]\n<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>\nThe proof combines a result of Linial, Mansour and Nisan with techniques of K\u00e1tai and Harman, used in their work on finding primes with specified digits.<\/jats:p>","DOI":"10.1017\/s0963548312000284","type":"journal-article","created":{"date-parts":[[2012,8,24]],"date-time":"2012-08-24T04:59:39Z","timestamp":1345784379000},"page":"942-951","source":"Crossref","is-referenced-by-count":28,"title":["On (Not) Computing the M\u00f6bius Function Using Bounded Depth Circuits"],"prefix":"10.1017","volume":"21","author":[{"given":"BEN","family":"GREEN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,8,24]]},"reference":[{"key":"S0963548312000284_ref11","unstructured":"Lipton R. J. (2011) The depth of the M\u00f6bius function. Blog post, available at: http:\/\/rjlipton.wordpress.com\/2011\/02\/23\/the-depth-of-the-mobius-function\/"},{"key":"S0963548312000284_ref14","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-96-00669-2"},{"key":"S0963548312000284_ref8","unstructured":"Kalai G. (2011) Walsh Fourier transform of the M\u00f6bius function. Math Overflow question, available at: http:\/\/mathoverflow.net\/questions\/57543\/walsh-fourier-transform-of-mobius-functions"},{"key":"S0963548312000284_ref4","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/os-8.1.313"},{"key":"S0963548312000284_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48686-0_29"},{"key":"S0963548312000284_ref2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-43.2.193"},{"key":"S0963548312000284_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"S0963548312000284_ref15","unstructured":"Sarnak P. (2010) M\u00f6bius Randomness and Dynamics. Lecture notes, available at: http:\/\/www.math.princeton.edu\/sarnak\/MobiuslecturesSummer2010.pdf"},{"key":"S0963548312000284_ref7","unstructured":"Kalai G. (2011) The AC0 prime number conjecture. Blog post, available at: http:\/\/gilkalai.wordpress.com\/2011\/02\/21\/the-ac0-prime-number-conjecture\/"},{"key":"S0963548312000284_ref13","volume-title":"Multiplicative Number Theory I: Classical Theory","author":"Montgomery","year":"2007"},{"key":"S0963548312000284_ref1","first-page":"356","article-title":"A lower bound for primality","volume":"62","author":"Allender","year":"2001","journal-title":"J. Comput. System Sci. (Special Issue on the Fourteenth Annual IEEE Conference on Computational Complexity"},{"key":"S0963548312000284_ref12","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.1591"},{"key":"S0963548312000284_ref5","doi-asserted-by":"publisher","DOI":"10.4064\/aa133-2-5"},{"key":"S0963548312000284_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01953972"},{"key":"S0963548312000284_ref6","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/053"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T17:59:53Z","timestamp":1556128793000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000284\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,24]]},"references-count":15,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["S0963548312000284"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000284","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,24]]}}}