# Complex Roots of Unity and Normal Numbers

Authors: Jean Marie De Koninck; Imre Kátai
Journal: Journal of Numbers
 (2014)

---

## Abstract

Given an arbitrary prime numberq, set ξ=e2πi/q. We use a clever selection of the values of ξα, α=1,2,…, in order to create normal numbers. We also use a famous result of André Weil concerning Dirichlet characters  to construct a family of normal numbers.


---

## Body

## 1. Introduction and Statement of the Results

Letλ(n) be the Liouville function (defined by λ(n)≔(-1)Ω(n), where Ω(n)≔∑pα∥n‍α). It is well known that the statement “∑n≤x‍λ(n)=o(x) as x→∞” is equivalent to the Prime Number Theorem. It is conjectured that if b1<b2<⋯<bk are arbitrary positive integers, then ∑n≤x‍λ(n)λ(n+b1)⋯λ(n+bk)=o(x) as x→∞. This conjecture seems presently out of reach since we cannot even prove that ∑n≤x‍λ(n)λ(n+1)=o(x) as x→∞.The Liouville function belongs to a particular class of multiplicative functions, namely, the classM* of completely multiplicative functions. Recently, Indlekofer et al. [1] considered a very special function f∈M* constructed in the following manner. Let ℘ stand for the set of all primes. For each q∈℘, let Cq={ξ∈C:ξq=1} be the group of complex roots of unity of order q. As p runs through the primes, let ξp be independent random variables distributed uniformly on Cq. Then, let f∈M* be defined on ℘ by f(p)=ξp, so that f(n) yields a random variable. In their 2011 paper, Indlekofer et al. proved that if (Ω,A,℘) stands for a probability space, where ξp (p∈℘) are the independent random variables, then, for almost all ω∈Ω, the sequence α=f(1)f(2)f(3)⋯ is a normal sequence over Cq (see Definition 1 below).Let us now consider a somewhat different setup. Letq≥2 be a fixed prime number and set Aq≔{0,1,…,q-1}. Given an integer t≥1, an expression of the form i1i2⋯it, where each ij∈Aq, is called aword of length t. We use the symbol Λ to denote theempty word. Then, Aqt will stand for the set of words of length t over Aq, while Aq* will stand for the set of all words over Aq regardless of their length, including the empty word Λ. Similarly, we define Cq* to be the set of words over Cq regardless of their length.Given a positive integern, we write its q-ary expansion as
(1)n=ε0(n)+ε1(n)q+⋯+εt(n)qt,
where εi(n)∈Aq for 0≤i≤t and εt(n)≠0. To this representation, we associate the word
(2)n¯=ε0(n)ε1(n)⋯εt(n)∈Aqt+1.Definition 1.
Given a sequence of integersa(1),a(2),a(3),…, one will say that the concatenation of their q-ary digit expansions a(1)¯a(2)¯a(3)¯⋯, denoted by Concat(a(n)¯:n∈N), is anormal sequence if the number 0.a(1)¯a(2)¯a(3)¯⋯ is a q-normal number.It can be proved using a theorem of Halász (see [2]) that if f∈M* is defined on the primes p by f(p)=ξa (a≠0), then ∑n≤x‍f(n)=o(x) as x→∞.Now, givenu0,u1,…,ul-1∈Aq, let Q(n)≔∏j=0l-1‍(n+j)uj. We believe that if max⁡j∈{0,1,…,l-1}uj>0, then
(3)∑n≤x‍f(Q(n))=o(x)asx⟶∞.
If this was true, it would follow that
(4)Concat(f(n):n∈N)is  a  normal  sequence  overCq.We cannot prove (3), but we can prove the following. Let q∈℘ and set ξ≔e2πi/q. Furthermore set xk=2k and yk=xk1/k for k=1,2,…. Then, consider the sequence of completely multiplicative functions fk, k=1,2,…, defined on the primes p by
(5)fk(p)={ξifk≤p≤yk,1ifp<korp>yk.
Then, set
(6)ηk≔fk(xk)fk(xk+1)fk(xk+2)⋯fk(xk+1-1)vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv(k∈N),θ≔Concat(ηk:k∈N).Theorem 2.
The sequenceθ is a normal sequence over Cq.We now use a famous result of André Weil to construct a large family of normal numbers.Letq be a fixed prime and set ξ≔e2πi/q and ξa≔e2πia/q=ξa. Recall that Cq stands for the group of complex roots of unity of order q; that is,
(7)Cq={ς∈C:ςq=1}={ξa:a=0,1,…,q-1}.Letp∈℘ be such that q∣p-1. Moreover, let χp be a Dirichlet character modulo p of order q, meaning that the smallest positive integer t for which χpt=χ0 is q. (Here χ0 stands for the principal character.)Letu0,u1,…,uk-1∈Aq. Consider the polynomial
(8)F(z)=Fu0,…,uk-1(z)=∏j=0k-1‍(z+j)uj
and assume that its degree is at least 1, that is, that there exists one j∈{0,…,k-1} for which uj≠0. Further set
(9)Su0,…,uk-1(χp)=∑n(mod⁡p)‍χp(Fu0,…,uk-1(n)).
According to a 1948 result of Weil [3],(10)|Su0,…,uk-1(χp)|≤(k-1)p.
For a proof, see Proposition 12.11 (page 331) in the book of Iwaniec and Kowalski [4].We can prove the following.Theorem 3.
Letp1<p2<⋯ be an infinite set of primes such that q∣pj-1 for all j∈N. For each j∈N, let χpj be a character modulo pj of order q. Further set
(11)Γp=χp(1)χp(2)⋯χp(p-1)(p=p1,p2,…),(12)η≔Γp1Γp2⋯.
Then η is a normal sequence over Cq.As an immediate consequence of this theorem, we have the following corollary.Corollary 4.
Letφ:Cq→Aq be defined by φ(ξa)=a. Extend the function φ to φ:Cq*→Aq* by φ(αβ)=φ(α)φ(β). Let
(13)φ(η)=φ(Γp1)φ(Γp2)⋯
and consider the q-ary expansion of the real number
(14)κ=0,φ(Γp1)φ(Γp2)⋯.
Then κ is a normal number in base q.Example 5.
Choosingq=3 and {p1,p2,p3,…}={7,13,19,…} as the set of primes pj≡1(mod⁡3), then, the number η defined by (12) is normal sequence over {0,e2πi/3,e4πi/3} while κ defined by (14) is a ternary normal number.


## 2. Proof of Theorem2

Letl be a fixed positive integer. Let a0,a1,…,al-1∈Aq. Recall the notation ξ=e2πi/q. Given a positive integer k, let x,y be such that xk≤x<x+y≤xk+1-l. We will now count the number M([x,x+y]∣(a0,…,al-1)) of those n∈[x,x+y] for which fk(n+j)=ξaj (j=0,…,l-1) holds.Consider the polynomial(15)Pd(x)=xq-1x-ξd=∏h=0h≠dq-1(x-ξh),
so that in particular
(16)(x-ξd)Pd(x)=xq-1.
Taking the derivatives on both sides of the above equation yields
(17)Pd(x)+(x-ξd)Pd′(x)=qxq-1.
Thus,
(18)Pd(fk(m))+(fk(m)-ξd)Pd′(fk(m))=qfk(m)¯,
where z¯ stands for the complex conjugate of z.We then have(19)Pd(fk(m))={qfk(m)¯iffk(m)=ξd,0iffk(m)≠ξd.Write the polynomialPd as Pd(m)=∑u=0q-1‍eu(d)mu, so that Pd(0)=ξ¯d; that is, e0(d)=ξ¯d. We then have
(20)Pa0(fk(n))⋯Pal-1(fk(n+l-1))=∏h=0l-1‍{∑uh=0q-1‍euh(ah)fkuh(n+h)}=∑u0,…,ul-1∈Aq‍A(u0,…,ul-1)fk(∏j=0l-1‍(n+j)uj),
where A(u0,…,ul-1)=eu0(a0)⋯eul-1(al-1), with A(0,…,0)=ξ¯a0+⋯+al-1.With integersx,y such that xk≤x<x+y≤xk+1-l, we now sum both sides of (20) for n=x,…,x+y, and we then obtain that
(21)ql∏j=0l-1‍ξ¯aj·M([x,x+y]∣(a0,…,al-1))=y∏j=0l-1‍ξ¯aj+∑u0,…,ul-1∈Aq(u0,…,ul-1)≠(0,…,0)A(u0,…,ul-1)×∑n=xx+y‍fk(∏j=0l-1‍(n+j)uj).Setting(22)Q(n)=∏j=0l-1‍(n+j)uj,
it remains to prove that
(23)lim⁡k→∞1xkmax⁡xk≤x<x+y≤xk+1-l⁡|∑n=xx+y‍fk(Q(n))|=0.To prove this, we proceed using standard techniques. Letρ(δ) stand for the number of solutions of the congruence Q(n)≡0(mod⁡δ), in which case we have ρ(pα)=ρ(p) for all primes p>k and integers α≥1. Now define the completely multiplicative function gk implicitly by the relation
(24)fk(m)=∑d∣m‍gk(d),
thus implying, in light of (5), that
(25)gk(p)=fk(p)-1={0ifp<korp>yk,ξ-1ifk≤p≤yk.
It follows that
(26)∑n∈[x,x+y]‍fk(Q(n))=∑n∈[x,x+y]‍∑δ∣Q(n)‍gk(δ)=∑δ‍gk(δ)∑n∈[x,x+y]Q(n)≡0(mod⁡δ)1=y∑δ‍gk(δ)ρ(δ)δ+o(1).Now, observe that sincegk(pα)=fk(pα)-fk(pα-1)=ξα-1(ξ-1), it follows that
(27)∑δ‍gk(δ)ρ(δ)δ=∏p‍(1+gk(p)ρ(p)p+gk(p2)ρ(p2)p2+⋯)=∏k≤p≤yk‍(1+ρ(p)(ξ-1)p(1+ξp+ξ2p2+⋯))=∏k≤p≤yk‍(1+ρ(p)(ξ-1)p·11-ξ/p)=∏k≤p≤yk‍(1+ρ(p)(ξ-1)p-ξ)=exp⁡{ρ(p)(ξ-1)∑k≤p≤yk‍1p+O(1)}.
But, since R(ξ-1)<0, we have
(28)exp⁡{ρ(p)(ξ-1)∑k≤p≤yk‍1p+O(1)}⟶0ask⟶∞.
Hence, combining (28) with (27) and (26), we obtain (23).We have thus established that(29)M([x,x+y]∣(a0,…,al-1))-yql=o(xk)(k⟶∞),
which completes the proof of Theorem 2.


## 3. Proof of Theorem3

As we will see, the proof of Theorem3 is essentially a consequence of Weil’s result (10).Letl be a fixed positive integer. Fix a prime p and let β=ξe0⋯ξel-1 be any word belonging to Cql. Consider the expression
(30)fβ(n)=∏j=0l-1‍∏ξ∈Cqξ≠ξej(χp(n+j)-ξ).
Observe that fβ(n)=0 if χ(n)⋯χ(n+l-1)∈Cql is different from β. But if χ(n)⋯χ(n+l-1)=β, then
(31)fβ(n)=∏j=0l-1‍∏ξ∈Cqξ≠ξej(ξej-ξ).
Since, for each j=0,…,l-1,
(32)ddx(xq-1)|x=ξej=qξejq-1=qξej¯,
it follows that
(33)fβ(n)=ql(ξe0⋯ξel-1¯),
where again z¯ stands for the complex conjugate of z. Hence, letting Mp(β) stand for the number of occurrences of β as a subword in the word Γp, we have
(34)ξe0⋯ξel-1¯qlMp(β)=∑n=1p-l‍fβ(n).
Now fβ(n) can be written as
(35)fβ(n)=∑(u0,…,ul-1)∈Aql‍A(u0,…,ul-1)χ(Fu0,…,ul-1(n)),
where
(36)Fu0,…,ul-1(n)=∏j=0l-1‍(n+j)uj,A(0,…,0)=ξe0¯⋯ξel-1¯.
Thus taking into account (8), the Weil inequality (10), and the above relations (34) and (35), we obtain that
(37)|ξe0⋯ξel-1¯(qlMp(β)-(p-l))|≤∑(u0,…,ul-1)∈Aql(u0,…,ul-1)≠(0,…,0)|A(u0,…,ul-1)|·|∑n=1p-l‍χ(Fu0,…,ul-1(n))|≤∑(u0,…,ul-1)∈Aql(u0,…,ul-1)≠(0,…,0)|A(u0,…,ul-1)|·((l-1)p+l)≤c1(l)p.
We have thus shown that
(38)|Mp(β)-p-lql|≤c(l)p,
thus completing the proof of Theorem 3.



---

*Source: 437814-2014-06-12.xml*