# Generalized Newman Phenomena and  Digit Conjectures on Primes

Authors: Vladimir Shevelev
Journal: International Journal of Mathematics and Mathematical Sciences
 (2008)

---

## Abstract

We prove that the ratio of the Newman sum over numbers
multiple of a fixed integer, which is not a multiple of 3, and the Newman
sum over numbers multiple of a fixed integer divisible by 3 is o(1)
when the upper limit of summing tends to infinity. We also discuss a
connection of our results with a digit conjecture on primes.


---

## Body

## 1. Introduction

Denote  forx,m∈ℕ, (1.1)Sm(x)=∑0≤n<x,n≡0(modm)(−1)s(n), where s(n) is the number of 1's in the binary expansion
of n.
Sum (1.1) is a Newman digit sum. From the fundamental paper of Gelfond [1], it follows
that (1.2)Sm(x)=O(xλ),λ=ln3ln4. The case m=3 was studied in detail in [2–4].So, from Coquet's theorem [3, 5] it follows
that (1.3)−13+23xλ≤S3(3x)≤13+553(365)λxλ with a microscopic improvement [4]: (1.4)23xλ≤S3(3x)≤553(365)λxλ,x≥2, and, moreover, (1.5)⌊2(x6)λ⌋≤S3(x)≤⌈553(x65)λ⌉.These estimates give the most exact modern limits of
the so-calledNewman phenomena.
Note that Drmota and Skałba [6], using a close function (Sm(m)(x)),
proved that if m is a multiple of 3, then for sufficiently
large x, (1.6)Sm(x)>0,x≥x0(m).In this paper, we study a general case form≥5 (in the cases of m=2 and m=4, we have |Sm(n)|≤1).To formulate our results, put form≥5,(1.7)λm=1+log2bm,(1.8)μm=22bm−1, where (1.9)bm2={sin(π3(1+3m))(3−sin(π3(1+3m))),ifm≡0(mod3),sin(π3(1−1m))(3−sin(π3(1−1m))),ifm≡1(mod3),sin(π3(1+1m))(3−sin(π3(1+1m))),ifm≡2(mod3). Directly, one can see that (1.10)32>bm≥{0.86184088⋯,if(m,3)=1,0.85559967⋯,if(m,3)=3, and thus, (1.11)λm<λ,2.73205080⋯<μm≤{2.76364572⋯,if(m,3)=1,2.81215109⋯,if(m,3)=3. Below, we prove the following results.Theorem 1.1.
If(m,3)=1,
then (1.12)|Sm(x)|≤1+μmxλm.Theorem 1.2 (Generalized Newman phenomena).
Ifm>3 is a multiple of 3, then (1.13)|Sm(x)−3mS3(x)|≤1+μmxλm.Using Theorem1.2 and (1.5), one can estimate x0(m) in (1.6). For example, one can prove that x0(21)<e909.


## 2. Explicit Formula forSm(N)

We have(2.1)Sm(N)=∑n=0,m|nN−1(−1)s(n)=1m∑t=0m−1∑n=0N−1(−1)s(n)e2πi(nt/m)=1m∑t=0m−1∑n=0N−1e2πi((t/m)n+(1/2)s(n)). Note that the interior sum has the
form (2.2)Fα(N)=∑n=0N−1e2πi(αn+(1/2)s(n)),0≤α<1.Lemma 2.1.
IfN=2ν0+2ν1+⋯+2νr,ν0>ν1>⋯>νr≥0,
then (2.3)Fα(N)=∑h=0re2πi(α∑j=0h−12νj+h/2)∏k=0νh−1(1+e2πi(α2k+1/2)), where as usual ∑j=0−1=0,∏k=0−1=1.Proof.
Letr=0,
then by (2.2), (2.4)Fα(N)=∑n=0N−1(−1)s(n)e2πiαn=1−∑j=0ν0−1e2πiα2j+∑0≤j1<j2≤ν0−1e2πiα(2j1+2j2)−⋯=∏k=0ν0−1(1−e2πiα2k), which  corresponds to (2.3) for r=0.
Assuming that (2.3) is valid for every N with s(N)=r+1,
let us consider N1=2νra+2νr+1 where a is odd, s(a)=r+1,
and νr+1<νr.
Let (2.5)N=2νra=2ν0+⋯+2νr;N1=2ν0+⋯+2νr+2νr+1. Notice that for n∈[0,2νr+1),
we have (2.6)s(N+n)=s(N)+s(n). Therefore, (2.7)Fα(N1)=Fα(N)+∑n=NN1−1e2πi(αn+(1/2)s(n))=Fα(N)+∑n=02νr+1−1e2πi(αn+αN+(1/2)(s(N)+s(n)))=Fα(N)+e2πi(αN+(1/2)s(N))∑n=02νr+1−1e2πi(αn+(1/2)s(n)). Thus, by (2.3) and (2.4), (2.8)Fα(N1)=∑h=0re2πi(α∑j=0h−12νj+h/2)∏k=0νh−1(1+e2πi(α2k+1/2)+e2πi(α∑j=0r2νj+(r+1)/2)∏k=0νr+1−1(1+e2πi(α2k+1/2))=∑h=0r+1e2πi(α∑j=0h−12νj+h/2)∏k−0νh−1(1+e2πi(α2k+1/2)).Formulas (2.1)–(2.3) give an explicit expression for Sm(N) as a linear combination of the products of the
form (2.9)∏k=0νh−1(1+e2πi(α2k+1/2)),α=tm,0≤t≤m−1.Remark 2.2.
On can
extract (2.3) from a very complicated general Gelfond formula [1], however, we prefer to give
an independent proof.


## 3. Proof of Theorem1.1

Note that in (2.3) (3.1)r≤ν0=⌊lnNln2⌋. By Lemma 2.1, we have (3.2)|Fα(N)|≤∑νh=ν0,ν1,…,νr|∏k=1νh(1+e2πi(α2k−1+1/2))|≤∑h=0ν0|∏k=1h(1+e2πi(α2k−1+1/2))|. Furthermore, (3.3)1+e2πi(2k−1α+1/2)=2sin(2k−1απ)(sin(2k−1απ)−icos(2k−1απ)) and, therefore, (3.4)|1+e2πi(2k−1α+1/2)|≤2|sin(2k−1απ)|. According to (3.2), let us estimate the
product (3.5)∏k=1h(2|sin(2k−1απ)|)=2h∏k=1h|sin(2k−1απ)|, where by (2.1), (3.6)α=tm,0≤t≤m−1. Repeating arguments of [1], put (3.7)|sin(2k−1απ)|=tk. Considering the function (3.8)ρ(x)=2x1−x2,0≤x≤1, we have (3.9)tk=2tk−11−tk−12=ρ(tk−1). Note that(3.10)ρ′(x)=2(1−x2−x21−x2)≤−1 for x0≤x≤1,
where (3.11)x0=32 is the only positive root of the equation ρ(x)=x.Show that either(3.12)tk≤sin(πm⌊m3⌋)=sin(πm⌈2m3⌉)=gm<32 or, simultaneously, tk>gm,
and (3.13)tktk+1≤max0≤l≤m−1(|sinlπm|(3−|sinlπm|))={(sin(πm⌊m3⌋))(3−sin(πm⌊m3⌋)),ifm≡1(mod3)(sin(πm⌈m3⌉))(3−sin(πm⌈m3⌉)),ifm≡2(mod3)=hm<34. Indeed, let for a fixed values of t∈[0,m−1] and k∈[1,n], (3.14)t2k−1≡l(modm),0≤l≤m−1. Then, (3.15)tk=|sinlπm|. Now, distinguish two cases: (1) tk≤3/2,(2)tk>3/2.In case (1),(3.16)tk=32⇆lπm=rπ3,(r,3)=1, and since 0≤l≤m−1,
then (3.17)m=3lr,r=1,2. Because of the condition (m,3)=1,
we have tk<3/2.Thus, in (3.15), (3.18)l∈[0,⌊m3⌋]∪[⌈2m3⌉,m], and (3.12) follows.In case (2), lettk>3/2=x0. For ε>0,
put (3.19)1+ε=tkx0=23|sin(π2k−1α)| such that (3.20)1−ε=2−23|sin(π2k−1α)|,(3.21)1−ε2=43|sin(π2k−1α)|(3−|sin(π2k−1α)|). By (3.9) and (3.19), we have (3.22)tk+1=ρ(tk)=ρ((1+ε)x0)=ρ(x0)+εx0ρ′(c), where c∈(x0,(1+ε)x0).Thus, according to (3.10) and taking into account that ρ(x0)=x0,
we find (3.23)tk+1≤x0(1+ε), while by (3.19) (3.24)tk=x0(1+ε). Now, in view of (3.21) and (3.11), (3.25)tktk+1≤|sinπ2k−1α|(3−|sin(π2k−1α)|), and according to (3.14), (3.15), we obtain that (3.26)tktk+1≤hm, where hm is defined by (3.13).Notice that from simple arguments and according to
(1.9), (3.27)gm≤hm=bm.Therefore,(3.28)∏k=1h|sin(π2k−1α)|≤(bm⌊h/2⌋)2≤bmh−1. Now, by (3.2)-(3.4), for α=t/m,t=0,1,…,m−1, we have (3.29)|Ft/m(N)|≤∑h=0ν0|∏k=1h(1+e2πi(α2k−1+1/2))|≤∑h=0ν02h∏k=1h|sin(2k−1απ)|≤1+2∑h=1ν0(2bm)h−1≤1+2(2bm)ν02bm−1.Note that, according to (1.7) and (3.1), (3.30)(2bm)ν0=2λmν0≤2λmlog2N=Nλm. Thus, by (1.8) (3.31)|Ft/m(N)|≤1+22bm−1Nλm=1+μmNλm.
Thus, the theorem follows from
(2.1).


## 4. Proof of Theorem1.2

Select in (2.1) the summands which correspond to t=0,m/3,2m/3.We have(4.1)mSm(N)=∑n=0N−1(eπis(n)+e2πi(n/3+(1/2)s(n))+e2πi(2n/3+(1/2)s(n)))+∑t=1,t≠m/3,2m/3m−1∑n=0N−1e2πi((t/m)n+(1/2)s(n)).Since the chosen summands do not depend onm and, for m=3,
the latter sum is empty, then we find (4.2)mSm(N)=3S3(N)+∑t=1,t≠m/3,2m/3m−1∑n=0N−1e2πi((t/m)n+(1/2)s(n)).Further, the last double sum is estimated by the same
way as in Section3 such that  (4.3)|Sm(N)−3mS3(N)|≤μmNλm.Remark 4.1.
Notice that from elementary arguments it follows that
ifm≥5 is a multiple of 3,
then (4.4)(sinπm⌊m−13⌋)(3−sinπm⌊m−13⌋)≤(sinπm⌈m+13⌉)(3−sinπm⌈m+13⌉). The latter expression is the
value of bm2 in this case (see (1.9)).Example 4.2.
Let us find somex0 such that S21(x)>0 for x≥x0.
Supposing thatx is multiple of 3 and using (1.4), we obtain that (4.5)S3(x)≥23λ+1/2xλ. Therefore, putting m=21 in Theorem 1.2, we have (4.6)S21(x)≥17S3(x)−μ21xλ21−1≥27⋅3λ+1/2xλ−μ21xλ21−1. Now, calculating λ and λm by (1.2) and (1.8), we find a required x0: (4.7)x0=(3.5⋅3λ+1/2μ21)1/(λ−λ21)=e908.379....Corollary 4.3.
Form which is not a multiple of 3, denote Um(x) the set of the positive integers not exceeding x which are multiples of m and not multiples of 3. Then, (4.8)∑n∈Um(x)(−1)s(n)=−1mS3(x)+O(xλm).In particular, for sufficiently largex,
we have (4.9)∑n∈Um(x)(−1)s(n)<0.Proof.
Since(4.10)|Um(x)|=Sm(x)−S3m(x), then the corollary immediately follows from Theorems
1.1, 1.2.


## 5. On Newman Sum over Primes

In [7], we put the following binary digit conjectures on
primes.Conjecture 5.1.
For alln∈ℕ,n≠5,6, (5.1)∑p≤n(−1)s(p)≤0, where the summing is over all primes not exceeding n.More precisely,  by the observations,∑p≤n(−1)s(p)<0 beginning with n=31. Moreover,
the following conjecture holds.Conjecture 5.2.
(5.2)limn→∞ln(−∑p≤n(−1)s(p))lnn=ln3ln4.A heuristic proof of Conjecture5.2 was given in
[8]. For a prime p,
denote Vp(x) the set of positive integers not exceeding x for which p is the least prime divisor. Show that the
correctness of Conjectures 5.1 (for n≥n0) follows from the following very plausible
statement, especially in view of the above estimates.Conjecture 5.3.
For
sufficiently largen,
we have (5.3)|∑5≤p≤n∑j∈Vp(n),j>p(−1)s(j)|<∑j∈V3(n)(−1)s(j)=S3(n)−S6(n).Indeed, in the “worst case” (really is not
satisfied), in which for alln≥p2(5.4)∑j∈Vp(n),j>p(−1)s(j)<0,p≥5, we have a decreasing but positive sequence of sums: (5.5)∑j∈V3(n),j>3(−1)s(j),∑j∈V3(n),j>3(−1)s(j)+∑j∈V5(n),j>5(−1)s(j),…,∑j∈V3(n),j>3(−1)s(j)+∑5≤p<n∑j∈Vp(n),j>p(−1)s(j)>0. Hence, the “balance condition” for odd
numbers [8] (5.6)|∑j≤n,jisodd(−1)s(j)|≤1 must be ensured permanently by the excess of the
odious primes. This explains Conjecture 5.1.It is very interesting that for some
primesp the inequality  (5.4), indeed, is satisfied for all n≥p2 . Such
primes we call “resonance primes." Our numerous observations show
that all resonance primes not exceeding 1000 are (5.7)11,19,41,67,107,173,179,181,307,313,421,431,433,587,601,631,641,647,727,787.In conclusion, note that forp≥3,
we have (5.8)limn→∞|Vp(n)|n=1p∏2≤q<p(1−1q) such that (5.9)limn→∞(∑p≥3|Vp(n)|n)=12. Thus, using Theorems 1.1, 1.2 in the form (5.10)Sm(n)={o(S3(n)),(m,3)=1,3mS3(n)(1+o(1)),3∣m, and inclusion-exclusion for p≥5,
we find (5.11)∑j∈Vp(n)(−1)σ(j)=−33p∏2≤q<p,q≠3(1−1q)S3(n)(1+o(1))=−32p∏2≤q<p(1−1q)S3(n)(1+o(1)).Now, in view of
(1.5), we obtain the following absolute result as an approximation of Conjectures
5.1, 5.2.Theorem 5.4.
For every prime numberp≥5 and sufficiently large n≥np,
we have (5.12)∑j∈Vp(n)(−1)s(j)<0 and, moreover, (5.13)limn→∞ln(−∑j∈Vp(n)(−1)s(j))lnn=ln3ln4.



---

*Source: 908045-2008-10-13.xml*