Möbius-Walsh correlation bounds and an estimate of Mauduit and Rivat

Abstract

We establish small correlation bounds for the Möbius function and the Walsh system, answering affirmatively a question posed by G. Kalai [Ka] . The argument is based on generalizing the approach of Mauduit and Rivat [M-R] in order to treat Walsh functions of "large weight", while the "small weight" case follows from recent work due to B. Green [Gr] . The conclusion is an estimate uniform over the full Walsh system. A similar result also holds for the Liouville function.

Full text

Translate

Turn on search term navigation

MBIUS-WALSH CORRELATION BOUNDS AND AN ESTIMATE OF MAUDUIT AND RIVAT

J. BOURGAIN

Abstract. We establish small correlation bounds for the Mbius function and the Walsh system, answering afrmatively a question posed by G. Kalai [Ka]. The argument is based on generalizing the approach of Mauduit and Rivat [M-R] in order to treat Walsh functions of large weight, while the small weight case follows from recent work due to B. Green [Gr]. The conclusion is an estimate uniform over the full Walsh system. A similar result also holds for the Liouville function.

0 Introduction

Fix a large integer and restrict the Mbius function to the interval [1, 2]

Z = . Identifying with the Boolean cube {0, 1} by binary expan

sion x =

0 j< xj 2j, the Walsh system

wA; A {0, . . . , 1} is dened by

w = 1 and

(0.1) wA(x) =

The Walsh functions on form an orthonormal basis (the character group of (Z/2Z)); and, given a function f on , we write

(0.2) f =

A{0,...,1} f(A)wA,

where f(A) = 2

n f (n)wA(n) are the Fourier-Walsh coefcients of f . Understanding the size and distribution of those coefcients is well known to be important to various issues, in particular, in complexity theory and computer science. Roughly speaking, a Fourier-Walsh (F-W for short) spectrum which is spread out indicates a high level of complexity for the function f . We do not elaborate

This research was partially supported by NSF grants DMS-0808042 and DMS-0835373.

147

jA(1 2xj ) = exp

jAxj

JOURNAL DANALYSE MATHMATIQUE, Vol. 119 (2013) DOI 10.1007/s11854-013-0005-2

148 J. BOURGAIN

on this theory here and refer the reader to the extensive literature on the subject; see also the preprint of B. Green [Gr], which motivated this Note.

Returning to the Mbius function and the so-called Mbius randomness law, it therefore seems reasonable to expect that | will have a F-W spectrum that

is not localized. More precisely, we establish the following uniform bound on its F-W coefcients, answering afrmatively a question posed by G. Kalai.

Theorem 1. For large enough,

(0.3) max

A{0,...,1}

n<2 (n)wA(n)

< 21/10.

(A similar estimate is also valid for the Liouville function.)

The proof of (0.3) involves different arguments, depending on the size |A|.

Roughly speaking, one distinguishes between the case |A| = o() and |A| [greaterorsimilar] .

In the rst case, B. Green already obtained an estimate of the type (0.3); see [Gr]. Part of the technique used in [Gr] is borrowed from Harman and Katais work [H-K] on prescribing binary digits of the primes. Let us point out that in this range, the problem of estimating the correlation of with a Walsh function is reduced to estimates on the usual Fourier spectrum of (by an expansion of wA in

the trigonometric system). The latter is then achieved either by means of Dirichlet L-function theory (when the argument is close to a rational a/q with sufciently small denominator q) or by Vinogradovs estimate when q is large.

At the other end of the spectrum, when A = {0, . . . , }, Mauduit and Rivat

proved that

(0.4)

n<2 (n)

wA(n)

< 2(1)

for some > 0. Here (n) stands for the von Mangoldt function [M-R]. Their motivation was the solution to a problem of Gelfond on the uniform distribution of the sum of the binary digits of the primes. Of course, their argument gives a similar bound for the Mbius function as well. Thus,

(0.5)

n<2 (n)

< 2(1).

A remarkable feature of the [M-R] method is that the usual type-I, type-II sum approach in the study of sums

n<X (n) f (n) or n<X (n) f (n) is applied directly to f = w{1,...,} without an initial conversion to additive characters (as done

in [H-K] and [Gr]). The main idea in what follows is to generalize the Mauduit-Rivat argument in order to treat all Walsh functions wA provided A is not too small (the latter case being captured by [Gr]).

w{0,...,1}(n)

MBIUS-WALSH CORRELATION BOUNDS 149

Needless to say, the 21/10-saving in (0.3) can surely be improved (this is an issue concerning the treatment of low-weight Walsh functions), and no effort has been made in this respect. We also observe that, assuming GRH, (0.3) may be improved to

Theorem 2. Under GRH, assuming large, we have

(0.6) max

A{0,...,1}

n<2 (n)wA(n)

< 2

1c/(log )2

We assume the reader is familiar with the basic technique, going back to Vinogradov, of type-I and type-II sums, to which sums

n<X (n) f (n) may be reduced; see [I-K, Ch. 13] or [M-R]. In fact, we rely here on the same version as used in [M-R]; see [M-R, Lemma 1]. Otherwise, besides referring to the work of B. Green for |A| small, our presentation is basically self-contained. In particular, all the re

quired lemmas pertaining to bounds on Fourier coefcients of Walsh functions are proven (they include estimates similar to those needed in [M-R] and also some additional ones) and are presented in Section 1 of the paper.

1 Estimates on Fourier coefcients of Walsh functions

For A {0, . . . , 1} and x = j xj 2j [1, 2]

(1.0) wA(x) =

jA(1 2xj ) = exp(i jAxj ) = jAh

x 2j+1

where h : R {1, 1} is the 1-periodic function

h =

1 if 0 x < 12

1 if 12 x < 1

For x

x 2j+1

|r|<2j+1ar,j e

rx 2j+1

with

|ar| [lessorsimilar] j.

Here, e(t) = e2it. It follows that

Lemma 1. wA(x) =

k<2

wA(k)e

kx 2

with

wA(k)| < (C)|A|.

From the second equality in (1.0), also

(1.1)

wA(k) = 2

{xj }ei[summationtext] jA xj e2ik2 [summationtext] xj 2j =

j A

1 + e(k2j)2

1 e(k2j)2

150 J. BOURGAIN

and

(1.2) |

wA(k)| =

j A |cos k2j|

jA |sin k2j|.

Lemma 2.

(1.3)

wA [lessorsimilar] 2c|A| for some constant c > 0.

Proof. Use (1.2).

Taking some i0 A and assuming

sin k

0 1, and hence

k 2i

it follows that either

k 2i

1 4

0 or

k 2i

In either case,

cos k

sin k

1 2.

The conclusion follows from (1.2).

In addition to (1.1), we have the bound

Lemma 3.

(1.4)

k<2|

wA(k)| [lessorsimilar] 2((1/2)c) for some constant c > 0.

Proof. We have to estimate

(1.5)

k Z/2Z

cos

ui2 +k 2i

where ui = 1 if i A and ui = 0 if i A.

Perform a shift k k + c22 + d21 with c, d = 0, 1.

This gives

k Z/22Z

cos

ui2 +k 2i

()

MBIUS-WALSH CORRELATION BOUNDS 151

with

() =

1 4

cos

u12 +k21 +c2

cos

u02 +k2 +c4 +d2

c,d =0,1

= 14

c=0,1

cos

u02 +k2 +c4 +

sin

u02 +k2 +c4

cos

u12 +k21 +c2

= 14

(1.6)

where = (u0/2 + k/2). Clearly,

(1.6)

1 4

(| cos | + | sin |)

cos

u12 + 2

+ 1

2(| cos sin

sin + cos

sin

u12 + 2

(1 + | sin 2|)1/2 cossin (2) + (1 + | cos 2|)1/2 sin cos(2)

2 + 2.

Iterating, we obtain the bound

2 + 2

1 4

/2and hence (1.4).

Lemma 4. Let r < , a = 0, 1, . . . , 2r 1. Then

(1.7)

wA(k)| [lessorsimilar] 2(1

2 c)(r).

a(mod 2r )

Proof. Writing k = a + 2rk1 with k1 < 2r, we have

wA(k)| =

i <r

cos

ui2 +a2i +k1 2ir

ui2 +a 2i

cos

(1.8)

For xed k1, denote

B(k1) =

i < r; cos

cos

i<r

ui2 +k1 2ri

+ 2+i+r

ui2 +k1 2ri

1 2 ri

Hence, if i Bk1,

cos

ui2 +k1 2ri

1 2 ri

cos

+ 2+r+i <

1 +

ui2 +k1 2ri

;

152 J. BOURGAIN

and if i Bk1,

cos

ui2 +k1 2ri

+ 2+r+i

1 2 ri

1 + 2

1 2 ri

sin

ui2 +k1 2ri

Thus certainly

(1.9) |

wA(k)| [lessorsimilar]

B {0,1,...,r1}

1 2 [summationtext]iB(ri)

i B

i<r

cos

ui2 +k1 2ri

sin

ui2 +k1 2ri

Given B [0, r 1[, dene B1 [0, r 1[ asB1 = (B [ui = 0]) (Bc [ui = 1]).

Then

(1.10) (1.9) =

1 2 [summationtext]iB(ri) |

wB1(k1)|.

Summing (1.10) over k1 < 2r and using the bound (1.4) with replaced by r

clearly gives (1.7).

We also need the following approximation property for shifts.

Lemma 5. Let A [ , ]

Z. Then

(1.11)

k<2|

wA(k)| < C(log)2(2)1

Moreover, there is a bounded function WA on [0, ]

Z satisfying |

WA| |

wA| and

(1.12)

x<2

|WA(x) wA(x)|2 1/2< 2ct

WA(k) = 0 if |k| > 2+t.

(1.13)

Here t

Z is a parameter satisfying C(log )2 < t < 12( ).

Proof. Writing k = k0 + 2k1 with k0 < 2, |k1| < 21 and setting again

ui = 1 if i A, ui = 0 if i A, we obtain

wA(k)| =

i <

cos

k0 + 2k1 2i

cos

ui2 +k0 2i

= (1.14)|

wA+(k0)|,

MBIUS-WALSH CORRELATION BOUNDS 153

where (1.14) refers to the rst factor and

A + [0, ]

We treat (1.14) as in the proof of Lemma 4, obtaining a bound

(1.15) |(1.14)| <

B {0,1,...,1}

1 2 [summationtext]iB(i) |

wB(k1)|.

From (1.1), certainly

k 1<2 |

(1.16)

wB(k1)| < (C)|B|;

and substitution of (1.16) in (1.15) implies that

wA 1

wA+ 1

1 2 [summationtext]iB(i)

(C)|B|

Lemma 3

< (2)(1/2)cC(log)2,

which is (1.11).Next, let C(log )2 < < 12( ) and estimate

(1.17)

1 2 [summationtext]iB(i) |

wB(k1)| [lessorsimilar] 2/4.

min B

(1.18) B [ , ],

we establish a bound on

wB(k1). Write

wB(k1)

cos k1

cos

i <

vi2 +k1 2i

with vi = 0, 1 if i B, i B, respectively. Hence, for 4 < k1 < 21,

(1.19) |

wB(k1)|

< j

cos k1

< kc1

for some c < 0, as we verify by dyadic expansion of k1.

154 J. BOURGAIN

It follows that for 4 K1 < 2,

1 2 [summationtext]iB(i) |

wB(k1)|

K1<|k1|<2

B(1.18)

< C

B(1.18)

1 2 [summationtext]iB(i) |

(1.20)

Dene WA as the Fourier restriction of wA. More specically, let

(1.21) WA(x) =

(k)

wB(k1)|2

K1<|k1|<2

1 2 [summationtext]iB(i)

(1.19)

< K c1

wB 1

(1.16)

< K c1C(log)2.

wA(k)e

kx 2

where : R [0, 1] is trapezoidal with (z) = 1 for |z| < K12, (z) = 0 for |z| 2K12. Then WA 3 and

A(k) =A(k) for |k| K12,

A(k) = 0 for

|k| 2K12.From the preceding,

wA 22

k0<2|

wA+(k0)|2

K1|k1|<2(1.15)2

(1.22)

(1.17), (1.20)

< 2/2 + K c1C(log)2.

Taking K1 = 2t1, = (t 1)/2, Lemma 5 follows.

The role of WA is to provide a substitute for wA with localized Fourier transform.

Lemma 6. If J [1, 2[ is an interval, there is a bound(1.23)

kJ |

wA(k)| [lessorsimilar] |J|(1/2)c.

Proof. Write

wA(k)| =

cos

ui2 +k 2i

with ui = 0 (ui = 1) if i A (i A).

Assume 2m |J| < 2m. Obviously,

wA(k)|

mi<

cos

ui2 +k 2i

cos

ui1+m2 +k 2mi 1

0i1<m

= |

wA1(k)|,

MBIUS-WALSH CORRELATION BOUNDS 155

where A1 = {0 i1 < m; i1 A + m }. Hence, sinceA1 is 2m-periodic,

kJ |

wA(k)|

kJ |

wA1(k)|

k<2m|

wA1(k)| A1 1 < 2m(1

2 c),

by Lemma 3.

2 Type-II sums

Let X = 2, S {0, . . . , 1}, wS(x) =!iS (1 2xi) with x =

xi2i.

Specify ranges M 2, N 2 such that M N and MN X.

Our goal is to bound bilinear sums of the form

mMnNmnwS(mn), where

|m|, |n| 1 are arbitrary coefcients.

We x a relatively small dyadic integer L = 2 (to be specied). We assume < /100, noting that otherwise our nal estimate (2.29) is trivial.

Following [M-R], we proceed with the initial reduction of the problem, crucial to our analysis.

Estimate

(2.1)

mMnN mnwS(mn)

nN nw(mn)

Fix K such that L2K < N and write, using Cauchys inequality,

nN nw(m.n)

1 L

m(n + 2K )

=1n+ 2K w

nN nw(mn)

[lessorsimilar]

nN | |<L

nn+ 2K w(m.n) w

m(n + 2K )

Hence, by another application of Cauchys inequality, we obtain

(2.2) (2.1)2 [lessorsimilar]

MN L

nN | |<L

mM wS(mn)wS

m(n + 2K)

Comparing the binary expansions of mn and mn + m2K , the K rst digits remain and we can assume that also digits j > K + + + are unchanged, provided in(2.2) we introduce an additional error term of the order 2M2N 2 (cf. Lemma 5 in [M-R]). Here > 0 remains to be specied, and we assume

Z+.

156 J. BOURGAIN

Therefore we may write, up to above error,

wS(mn)wS

m(n + 2K ) = wS (mn)wS

m(n + 2K)

with S = S [K, K + + ] and = (1 + ) and in (2.2) we may replace w = wS

by wS .

We choose either K = 0 or K < . Hence, by varying K , the

intervals [K, K + + ] will cover [0, [.For K = 0, we approximate wS

by WS given by Lemma 5, applied with replaced by K + + and by + .

Take t = , where is assumed to satisfy /100 > (log )2. Then

from (1.12),

x<X |wS (x) WS (x)|2 < 2ctX. From the preceding (since WS is

bounded),

(2.2) [lessorsimilar]

nN | |<L

mMWS (mn)WS

m(n + 2K)

(2.3)

(2.4)

+ X

mM nN

|wS (mn) WS (mn)|

+ X2L,

where

(2.4) < X

x<X

|wS (x) WS (x)|2 1/2 xX d(x)2

1/2

< LcX2(log X)C < LcX2.

For K = 0,

(2.5) wS (x) =

k<2+

wS (k)e

kx 2+

where, from Lemma 2 and Lemma 3 applied with replaced by + ,

(2.6)

wS < 2c|S |

and

(2.7)

wS 1 < 2((1/2)c)(+ ) < 2(1/2)c)(+)

for small enough.

MBIUS-WALSH CORRELATION BOUNDS 157

For K = 0,

(2.8) WS (x) =

kx 2+ +K

|k|<2

+ +t

WS (k)e

where

(2.9)

wS < 2c|S |

and by (1.11) and our choice of ,

(2.10)

WS 1 < 2((1/2)c)(+).

Denoting by w either wS when K = 0 or WS for + K < ,

substituting (2.5) and (2.8), and applying a smoothened m-summation give for(2.3) with M1 = M11,

(2.11) M2N L

| |[lessorsimilar]L

k,k |

w(k)||

w(k )|1

( kn2+ +K k (n+ 2K )2+ +K < 1M1)

up to a negligible error term.The condition

(2.12)

(k k )n

2+ +K

< 1

has to be analyzed.

For k = k , the contribution is

(2.13) M2N 2 L

| |[lessorsimilar]L

|k|<2+ +t |

w(k)|21

( k 2+ < 1M1

The = 0 contribution in (2.2) is at most M 2N 2/L.

For = 0, we get a bound(2.14) M2+1N 22 +t

w 2 < M2N 2L2|

w 2 < X2L22c|S |

from (2.6), (2.9) and choosing 1 > 0 small enough to ensure 1 < .

In the sequel, we assume k = k , = 0.

Also, if in (2.11) for given k, k , there are at most O(1) values of n satisfying(2.12), the resulting contribution is at most

(2.15) M2N

w 21 <

(2.7)(2.10)

M2N (ML)12c < X2LN c,

158 J. BOURGAIN

since M N .

Returning to (2.11), consider rst the case K = 0.

We estimate the contribution for (k k , 2+ ) = 2r. Thus k k = k12r,

(k1, 2) = 1, and (2.12) becomes

(2.16)

k1n

2+ r

< 1

implying also

(2.17)

< L1+2

2r .

It follows from (2.17) that there are at most L1+2 possibilities for k (mod 2r) and hence for (k, k ) (mod 2r).

For xed k, k , , (2.16) determines n (mod 2+ r) up to 1 + L1+22r possibilities and hence n up to N2rML (1 + L1+22r) possibilities.

Thus the corresponding contribution to (2.11) is at most

(2.18) M2N L

| |[lessorsimilar]LL1+2 N 2rML (1 + L1+22r) max a

w(k)||

w(k )|

a(mod 2r ) k a(mod 2r)

[lessorsimilar] MN 2(L + 2r)L2 max

w(k)|+2

k<2+ ka(mod 2r)

From Lemma 4 applied with replaced by + ,

(2.18) [lessorsimilar] MN 2(L + 2r)(2+ r)1cL2= M2N 2(L22r + L)(ML2r)cL3.

(2.19)

Hence, assuming

(2.20) ML2r > LC,

we obtain the bound X2/L. Next, assume

(2.21) ML2r < LC.

From the preceding, there are at most L1+4(ML2r)2 < LC possibilities for (k, k ).

This gives the contribution M2N 2LC

w 2 < LCX22c|S | and, in conclusion,

(K = 0) the bound

(2.22) X2(L1 + LC2c|S |).

MBIUS-WALSH CORRELATION BOUNDS 159

Next, assume

(2.23) K .

Return to (2.11). Fix , k, k with |k k | k < ML2. Letting n range over an

interval of size ML2K / k, the number of possibilities for n in that interval is at most 1 + L1+22K / k. Assume N [greaterorsimilar] ML2K / k.

The number of ns satisfying (2.12) is at most (since L2K M > K/L2 by

(2.23))

N k ML2K

1 + L1+22K k < NM L2.

This gives the contribution in (2.11)

(2.24) L2MN 2

w 21 <

(2.10) L2MN 2(ML2)1c < X2L3Mc.

Next, assume N ML2K / k. From (2.12), for , k, k given, there are at most

1 + 2K L3/ k 2K L3/ k values of n.

Also

kN M2 2K .

Since |k | < 2+L2, there is some integer 1, | 1| < L2 such that

< 1

M1 +

2+ 1

< 1

M1 +

kN M2 2K ;

hence

k 1

< L1+2 + kN

2K .

This restricts k to at most L2 intervals of size L1+2 + kN/2K.

Using Lemma 6, we obtain the following bound for the contribution to (2.11):

M2N.L2

L1+2 + kN 2K

1c 2K L3 k

(2.25)

[lessorsimilar]

M2NL72K

k + M2N 2L5

kN 2K

c < M2N 2L7 2K N k

If we assume N k/2K > LC, (2.25) gives the bound

(2.26) X2

L .

Assume next N k/2K < LC. From the preceding, k is restricted to LC values and the corresponding contribution to (2.11) is bounded by

(2.27) M2N 2LC

w 2 < X2LC2c|S |.

160 J. BOURGAIN

Collecting previous bounds gives

(2.28) (2.11) < X 2

1L + L3Mc + LC2c|S |

and recalling (2.3), (2.4) yields

(2.29) (2.1) < X

Lc + L2Mc + LC2c|S | .

In the estimate (2.29), S depends on the choice of K .Recall that either K = 0 or K < and hence, varying K , the

intervals [K, K + + ] cover [0, 1]. Thus we may choose K as to ensure that(2.30) |S | max |S J| [greaterorsimilar]

|S|

with max taken over intervals J [0, 1] of size . In particular, (2.29) implies(2.31) (2.1) < X

Lc + L2Mc + LC2c|S|/

where L is a parameter.

For |S| 1/2/H with H 1 a parameter, we apply B. Greens estimate (see

[Gr])

(2.32)

x<2 wS(x)(x)

< ecH.

Thus we assume |S| > 1/2/H. Taking L = 2H, it follows from (2.29), (2.31)

that

(2.33) (2.1) [lessorsimilar] X2cH,

assuming either that

(2.34) M > 2CH21/2

(2.35) M > CH and |S | > CH (S satisfying (2.30)).

3 Type-I sums and conclusion

We use Lemma 1 from [M-R] but also treat some of the type-I sums as type-II sums. Indeed, according to (2.33), (2.34), only the range M < C H21/2 remains to be treated.

MBIUS-WALSH CORRELATION BOUNDS 161

Thus we need to bound

(3.1)

nN wS(mn)

where MN X = 2, M < CH21/2. We assume |S| > 1/2/H.

Expanding in Fourier and using a suitable mollier in the n-summation, we obtain

(3.1)

k<X|

wS(k)|

nNe

kmn2

(3.2)

< N

mM k<X|

wS(k)|1

( km2 < 2N)+ o(1)

(3.2 )

< NM22

(3.3)

< XM2c1/2H12.

Taking H < 1/10, (3.3) is certainly conclusive if M < CH . Hence, recalling(2.35), we can assume that

(3.4) > H and max |S J| < CH

for any interval J {0, . . . , 1} of size , where M 2.Assumption (3.4) provides further information onS useful in exploiting (3.2). Write S = S1 S2 where S1 = S [0, 2] and S2 = S [ 2, ]. Then

by (3.4), |S2| < CH. Thus

(3.5) wS2(x) (1.0)=

jS2h

x 2j+1

k 2

wS2(k2)e

k2x2 + OL1 (2H),

where the set A2 may be taken of size

(3.6) |A2| < 2H|S2| < CH2

(obtained by truncation of the Fourier expansion of h).

On the other hand, wS1(x) =

k1<22

wS1(k1)e(k1x/22), and hence

(3.7) wS(x) =

k 1<22

k2A2

wS1(k1)

wS2(k2)e

22k1 + k22 x + OL1 (2H).

162 J. BOURGAIN

The bound (3.2) becomes now

(3.8) N

k1<22 k2A2

wS1(k1)||

wS2(k2)|1

(

< 2N

)

22k1+k2

2 m

22k1 + k2

< N |A2|

wS1 . max

2 m

< 2

k1 < 22;

Clearly,

k1m

< 22

k1 < 22; k1m 0(mod 22)

[lessorsimilar] M;

and therefore, since |S1| [greaterorsimilar] 1/2/H and (3.6)

(3.9) (3.8) < CH22c1/2H1NM < 2c1/2H1X.

From (2.33) and (3.9), we can claim a uniform bound

(3.10)

x<X (x)wS(x)

k1 < 22;

[lessorsimilar] X2c1/10,

hence obtaining Theorem 1.

Under GRH, (3.10) can be improved of course.

First, from a result due to Baker and Harman [B-H], there is a uniform bound

(3.11)

nX (n)e(n)

X(3/4)+ .

Hence

(3.12)

n<X (n)wS(n)

< S 1X(3/4)+ < (log X)|S|X(3/4)+ ,

and we may assume

(3.13) |S| > c

log X log log X .

If (3.13), apply the type-I-II analysis above.

From (2.31), assuming

(3.14) M 2 > Xc1/loglogX

MBIUS-WALSH CORRELATION BOUNDS 163

and choosing L appropriately, we obtain

(3.15) (2.1) < X.2clogX/(loglogX)2.

If M fails (3.14), the type-I bound (3.2 ) gives

(3.1) < X.M S

(1.3)

< XXc1/loglogX2c logX/loglogX

< X1c2/loglogX

(3.16)

for an appropriate choice of c1 in (3.14).In either case,

(3.17)

n<X (n)wS(n)

< X1c/(loglogX)2,

which is Theorem 2.

REFERENCES

[B-H] R. Baker and G. Harman, Exponential sums formed with the Mbius function, J. London Math.

Soc. (2) 43 (1991), 193198.

[Gr] B. Green, On (not) computing the Mbius function using bounded depth circuits, Combin.

Probab. Comput. 21 (2012), 442451.

[H-K] G. Harman and I. Katai, Primes with preassigned digits II, Acta Arith. 133 (2008), 171184.

[I-K] H. Iwaniec and E. Kowalski, Analytic Number Theory, American Mathematical Society, Providence, RI, 2004.

[Ka] G. Kalai, Private communication.

[M-R] C. Mauduit and J. Rivat, Sur un problme de Gelfond: la somme des chiffres des nombres premiers, Ann. of Math (2) 171 (2010), 15911646.

J. BourgainSCHOOL OF MATHEMATICS

INSTITUTE FOR ADVANCED STUDY

1 EINSTEIN DRIVE

PRINCETON, NJ 08540 USA email: [email protected]

(Received September 14, 2011 and in revised form January 16, 2012)

Word count: 3912

Show less

Hebrew University Magnes Press 2013

Möbius-Walsh correlation bounds and an estimate of Mauduit and Rivat

Content area

Abstract

Full text