#A10 INTEGERS 12 (2012) ON THE NUMBER OF CARRIES OCCURRING IN AN ADDITION MOD 2

ON THE NUMBER OF CARRIES OCCURRING IN AN ADDITION MOD 2^K −1

Jean-Pierre Flori

T´el´ecom ParisTech, CNRS LTCI, Paris, France flori@enst.fr

Hugues Randriam

T´el´ecom ParisTech, CNRS LTCI, Paris, France randriam@enst.fr

Received: 5/16/11, Revised: 9/24/11, Accepted: 1/1/12, Published: 1/13/12

Abstract

In this paper we study the number of carries occurring while performing an addition modulo 2^k−1. For a fixed modular integert, it is natural to expect the number of carries occurring when adding a random modular integer a to be roughly the Hamming weight oft. Here we are interested in the number of modular integers in Z/(2^k−1)Z producing strictly more than this number of carries when added to a fixed modular integert∈Z/(2^k−1)Z. In particular it is conjectured that less than half of them do so. An equivalent conjecture was proposed by Tu and Deng in a different context.

Although quite innocent, this conjecture has resisted different attempts of proof and only a few cases have been proved so far. The most manageable cases involve modular integerst whose bits equal to 0are sparse. In this paper we continue to investigate the properties ofP_t,k, the fraction of modular integersato enumerate, for t in this class of integers. Doing so we prove thatP_t,k has a polynomial expression and describe a closed form for this expression. This is of particular interest for computing the function giving P_t,k and studying it analytically. Finally, we bring to light additional properties ofP_t,k in an asymptotic setting and give closed-form expressions for its asymptotic values.

1. Introduction

For a fixed modular integer t ∈ Z/(2^k−1)Z, it is natural to expect the number of carries occurring when adding a random modular integer a ∈ Z/(2^k−1)Z to be roughly the Hamming weight of t. Following this idea, it is of interest to study the distribution of the number of carries around this value. Quite unexpectedly the following conjecture, indicating a kind of regularity, seems to be verified.

Conjecture 1. LetSt,k denote the following set:

S_t,k=!

a∈Z/(2^k−1)Z|r(a, t)> w(t)"

, andP_t,k thefractionof modular integers inS_t,k:

Pt,k =|St,k|/2^k. Then

P_t,k≤ 1 2.

(We are fully aware that there are only 2^k−1 elements inZ/(2^k−1)Z, but we will often use the abuse of terminology we made above and speak offraction,probability orproportionforP_t,k.) An equivalent conjecture was originally proposed by Tu and Deng [8] in a different context. For the connection between the conjecture of Tu and Deng and the one given here, we refer the reader to [4]. Tu and Deng verified computationally the validity of their assumption fork≤29.

Up to now, different attempts [4, 5, 3, 2] were conducted and lead to partial proof of the conjecture in very specific cases. A list of the different cases proven to be true can be found in [5, Section 5]. Unfortunately a direct proof or a simple recursive one seems hard to find [5, Section 4]. What however came out of these works is that supposing thatt has a high Hamming weight [3, 2] or more generally that its0bits are sparse [4, 5], greatly simplifies the study ofP_t,k. This condition casts a more algebraic and probabilistic structure upon it.

In this paper we restrict ourselves to this class of numbers. We do not prove any further cases of the conjecture, but extend the study ofPt,k as a function oftfor this class of numbers. It is organized as follows. In the first section we recall definitions and results found in [4]. In the second section we explore the algebraic nature of Pt,k, deduce a closed-form expression for it as well as additional properties that this expression verifies. This is of particular interest for computing the function giving P_t,k and studying it analytically. In the third section we analyze the probabilistic nature ofP_t,k, find useful closed-form expressions for the asymptotic value of P_t,k and give relations verified by different limits.

1.1. Notations

Unless stated otherwise, we use the following notations:

• k∈Nis the number of bits we are currently working on.

• t∈Z/(2^k−1)Zis a fixed modular integer.

Moreover we will assume that t $= 0. The case t = 0 is trivial and can be found in [4, Proposition 2.1].

The Hamming (or binary) weight of a natural or modular integer is defined as follows.

Definition 2. (Hamming Weight)

• For a ∈ N, w(a) is the weight of a, i.e., the number of 1’s in its binary expansion.

• For a ∈ Z/(2^k −1)Z, w(a) is the weight of its unique representative in

!0, . . . ,2^k−2".

The number of carries is then defined as follows.

Definition 3. Fora∈Z/(2^k−1)Z,a$= 0, we set r(a, t) =w(a) +w(t)−w(a+t),

i.e.,r(a, t) is the number of carries occurring while performing the addition ofaand t. By convention we set

r(0, t) =k, i.e., 0 behaves like the binary string1...1# $% &

k

. We also remark thatr(−t, t) =k.

The setS_t,k is described as

S_t,k={a|r(a, t)> w(t)}.

We recall thattcan be multiplied by any power of 2 (which corresponds to rotating its binary expansion) without affecting the value ofP_t,k [4, Proposition 2.2].

1.2. A Block Splitting Pattern

To compute P_t,k, a fruitful idea is to split t in several blocks and perform the computation in each block as independently as possible. Here we recall the splitting pattern defined in [4].

We split t($= 0) (once correctly rotated, i.e., we multiply it by a correct power of 2 so that its binary expansion on k bits begins with a1 and ends with a0) in blocks of the form [1^∗0^∗] (i.e., as many 1’s as possible followed by as many0’s as possible) and write it down as follows.

Definition 4. We let t=

α1 ' 1---1

β1 ' 0---0

# $% &

t1

...

αi ' 1---1

βi ' 0---0

# $% &

ti

...

αd ' 1---1

βd ' 0---0

# $% &

td

withdthe number of blocks,α_i andβ_i the numbers of 1’s and0’s of thei-th block t_i. We defineB =(d

i=1β_i=k−w(t).

We define corresponding values fora(a number to be added tot) as follows.

Definition 5. We let t=

α1 ' 1---1

β1 ' 0---0...

αi ' 1---1

βi ' 0---0...

αd ' 1---1

βd ' 0---0, a=?10-0

!_γ1 ?01-1

!_δ1 ...?10-0

!_γ

i

?01-1

!_δ

i

...?10-0

!_γ

d

?01-1

!_δ

d

,

i.e.,γ_iis the number of 0’s in front of the end of the1’s subblock oft_i andδ_i is the number of 1’s in front of the end of the 0’s subblock of t_i. One should be aware thatγi’s andδi’s depend onaand are considered as variables.

Thenαi−γi is the number of carries occurring in thei-th block, but only if no carry comes out of the previous block.

If a carry comes out of the previous block, the situation is more complicated because we must take into account the fact that it will propagate in the0subblock and could even propagate into the1subblock ifδ_i =β_i. Therefore we defineγ^"_i as follows.

• ifδ_i$=β_i, we define γ_i^"=γ_i as before,

• ifδi =βi, we defineγ_i^" = 0 (i.e., the carry coming from the previous block goes through the0’s subblock so the1’s subblock always producesα_i carries).

We defineδ_i^"=δifor notation consistency. Thenαi−γ^"_i+δ^"_iis the number of carries occurring if a carry comes out of the previous block.

Unfortunately theγ_i^"’s andδ_i^"’s are no longer pairwise independent. Indeed within the same block,γ_i^" andδ^"_i are correlated. However each block remains independent of the other ones. The distributions ofγ_i^" andδ^"_i are given in Table 1.

c_i= 0 1 . . . c_i . . . α_i−1 α_i α_i+ 1 . . .

P(γ_i^"=c_i) ^1+1/2₂ ^{βi 1−1/2}₄ ^βi . . . ^1−1/2_2ci+1^βi . . . ^1−1/2₂αi^βi

1−1/2^βi

2^αi 0 . . .

di= 0 1 . . . di . . . βi−1 βi βi+ 1 . . .

P(δ^"_i=di) 1/2 1/4 . . . 1/2^di+1 . . . 1/2^βi 1/2^βi 0 . . . Table 1: Distributions ofγ_i^" andδ^"_i

Finally, for computational reasons, it will sometimes be easier to count the num- ber of carries not occurring within a block. Hence we define %_i = γ_i +δ_i and

%^"_i =γ_i^"+βi−δ_i^". It is the number of carries lost in the i-th block depending on whether a carry comes out of the previous block or not.

1.3. The Constrained Case

It is now time to define what we understand by sparse 0bits. Informally we want each of the blocks defined in the previous subsection to have a large number of 1’s and only a few 0’s. Mathematically we impose that t verifies the following constraint:

mini (α_i)≥ )d i=1

β_i−1 =B−1 =k−w(t)−1.

Under that hypothesis, ifais inS_t,k, then a carry has to go through each subblock of 1’s. Therefore each block is independent of the other ones. Moreover it can be shown that we get an equivalence betweenr(a, t)> w(t) and(d

i=1γ_i^"<(d i=1δ_i^". Proposition 6. [4, Proposition 3.8]

P_t,k =P

*)

d

γ^"<)

d

δ^"

+ .

Formulated in a different way, it also means that for such t ∈ Z/(2^k −1)Z, a∈St,kis equivalent to(

d%^"_i< B=k−w(t) and we get the following proposition.

Proposition 7. [4, Proposition 3.9]

P_t,k =^B−1)

E=0

)

!

dei=E 0≤ei

,

d

P(e_i)

whereP(e_i)is defined by

P(e_i) =P(%^"_i=e_i) =







2^−βi if e_i= 0,

2^−βi

3 (2^ei−2^−ei) if 0< e_i<β_i,

2^βi−2^−βi

3 2^−ei if β_i≤e_i.

As soon as a given set ofβi’s andαi’s verifies the constraint min_iαi≥B−1, the above expression shows that the value of Pt,k for the corresponding t and k only depends on the value of theβ_i’s. Furthermore it does not depend on the ordering of theβ_i’s and so is a symmetric function of them, whence the following definition.

Definition 8. We denote by fd(β₁, . . . ,βd) the value of Pt,k for any t made of d blocks, with that set of βi’s and any set of of αi’s such that min_iαi ≥ B−1.

Obviouslyf_d is a symmetric function of theβ_i’s.

This function will be our main object of interest in this paper.

2. A Closed-Form Expression forPt,k

The main goal of this section is to describe a closed-form expression of fd and its properties.

After giving some experimental results in Subsection 2.1, we will prove that fd

has the following “polynomial” expression.

Proposition 9. For anyd≥1,f_d can be written in the following form:

fd(β₁, . . . ,βd) = )

I⊂{1,...,d}

4^−!i∈IβiP_d^|I|({βi}_i∈I),

whereP_dⁿ is a symmetric multivariate polynomial innvariables of total degreed−1 and of degree d−1 in each variable if n >0. If n= 0, then P_d⁰= ¹₂(1−Pd), the value computed in 44.

The proof of this result covers three subsections:

1. in Subsection 2.2, we split the expression givingfdas a sum into smaller pieces and establish a recursion relation ind;

2. in Subsection 2.3, we study the expression of the residual term appearing in this relation;

3. in Subsection 2.4, we put the pieces back together to conclude.

Once this proposition is shown, we will be allowed to denote by a^d,n_(i1,...,i

n) the coefficient ofP_dⁿ(x₁, . . . , x_n) of multi-degree (i₁, . . . , i_n) normalized by 3^d. In Sub- section 2.5 we give simple expressions for some specific values of a^d,n_(i1,...,i

n) as well as the following general expression.

Proposition 10. Suppose thati1 > . . . > im$= 0> im+1= 0> . . . > in = 0 and m >0. Let us denote byl the suml=i1+. . .+in >0(i.e., the total degree of the monomial). Then

a^d,n_(i1,...,i

n)= (−1)ⁿ⁺¹1 l i₁, . . . , i_n

2 b^d,n_l,m, with

b^d,n_l,m= ^n−m)

i=0

1n−m i

2d−n)

j=0

1d−n j

2 )

kj≥0,j∈I∪J,1≤j≤m

(l+S−m)!

l!



)

k≥1

2^k (h−k)!

5 h−k l+S−m

6

,

j∈J

Akj

k_j! ,

j∈I

Akj−3_kj=0 k_j!

,m j=1

Ckj−1

|k_j−1|!. Within b^d,n_l,m, the following notations are used:

• I={m+ 1, . . . , m+i};

• J={n+ 1, . . . , n+j};

• S=(

j∈I∪J,1≤j≤mk_j;

• h=d−m−j−i;

and

C_j =





A_j+^B_j+1^j+1 ifj >0,

−¹³₆ ifj = 0,

1 ifj =−1.

Here Ai is a sum of Eulerian numbers and Bi a Bernoulli number which are described in Subsection 2.3.

Finally, we prove in Subsection 2.6 an additional property predicted experimen- tally.

Proposition 11. For0< j≤i,

a^d,n_(i,j,...)=i+ 1

j a^d,n(i+1,j−1,...); i.e., the value of b^d,n_l,m does not depend onm.

2.1. Experimental Results

Ford= 1, by [4, Theorem 3.6], we have f1(β₁) = 2

34^−β1+1 3.

The case d = 2 has been treated in [4, Proposition 3.12] and leads to a similar expression:

f2(β₁,β2) =11

27 + 4^−β112 9β1− 2

27 2

+ 4^−β212 9β2− 2

27 2

+ 4^−β1−β2120 27−2

9(β₁+β2)2 .

In both cases,f_d has the correct form and has been shown to verify Conjecture 1.

The tables in Appendix 4 give the coefficients of the multivariate polynomials P_dⁿ for the first few d’s. Graphs of some functions derived from fd are given in Figures 2.1 and 2.1. All of this data was computed using Sage [7], Pynac [10] and Maxima [9].

Moreover looking at the tables in Appendix 4, some additional properties seem to be verified. Here are some examples. The value ofa^d,d(1,...,1,0)is easy to predict:

a^d,d(1,...,1,0)= (−1)^d+12;

Figure 1: f_d(β_i) forβ_i= 1,i$= 1.

Figure 2: fd(β_i) forβi= 10,i$= 1.

we prove this in Proposition 28. There is a recursion relation between coefficients with differentd’s:

a^d,n+1_(i1,...,i

n,0)+a^d,n_(i1,...,i

n)= 3a^d−1,n_(i1,...,i

n);

this is Corollary 27. There is a relation between coefficients with a givend:

a^d,n_(i,j,...)=i+ 1

j a^d,n(i+1,j−1,...);

this is Proposition 11. All of these results will be proved in the next subsections.

It should also be noted that we already know the value offd(1, . . . ,1).

Theorem 12. [4, Theorem 4.14]Ford≥1, f_d(1, . . . ,1) = 1

2. 2.2. Splitting the Sum into Atomic Parts We consider a generald≥1. From Proposition 7:

f_d(β₁, . . . ,β_d) =

B−1)

E=0

)

!

dei=E 0≤ei

,

d

P(e_i),

whereP(e_i) has three different expressions according to the value ofei:

P(e_i) =







2^−βi ife_i= 0,

2^−βi

3 (2^ei−2^−ei) if 0< e_i<β_i,

2^βi−2^−βi

3 2^−ei ifβ_i≤e_i. Let us denote for a vectorX ∈{0,1,2}^d:

• thei-th coordinate by Xi with 1≤i≤d;

• jk=wk(X) =|{i|Xi =k}|for 0≤k≤2;

• B_0,1=(

{i|Xi)=2}β_i;

• E₁=(

{i|Xi=1}e_i.

We can now define subsetsS_X^d of the sum in Proposition 7 where eachP(e_i) has a

specific behavior given by the value of thei-th coordinate of such a vectorX:

S^dX=

B!−1 E=0

!

! de_i=E e_i=0 ifX_i=0 0<e_i<β_iifX_i=1

β_i≤eiifX_i=2

"n i=1

P(ei)

=

B!−1 E=0

!

! de_i=E e_i=0 ifX_i=0 0<e_i<β_iifX_i=1

β_i≤e_iifX_i=2



 "

{i|X_i=0}

2^−βi "

{i|X_i=1}

2^−βi

3 (2^ei−2^−ei) "

{i|X_i=2}

2^βi−2^−βi 3 2^−ei



,

so that

fd(β1, . . . ,βd) = !

X∈{0,1,2}^d

SX^d.

Here we drop the dependency in theβ_i’s for conciseness. The sumS_X^d already has some properties off_d.

Lemma 13. S_X^d is symmetric for each set {i|X_i=k} where k ∈ {0,1,2}. To compute S_Y^d where Y is any permutation of X, one has just to permute the βi’s accordingly inS_X^d.

The previous lemma shows that it is enough to study theX’s such that

X= (

j0

% &# $ 0, . . . ,0,

j1

% &# $ 1, . . . ,1,

j2

% &# $ 2, . . . ,2).

The following lemma is obvious.

Lemma 14. S_(0,...,0)^d = 2^−!di=1βi andS_(2,...,2)^d = 0.

And whenj₂= 0,S_X^d has a simple expression.

Proposition 15. Ifj₂= 0 andX = (

j0

% &# $ 0, . . . ,0,

j1

% &# $ 1, . . . ,1), then S^d_X= 2^{−!ji=10 βi}

3^j1

,d i=j0+1

(1 + 2·4^−βi−3·2^−βi).

Proof. This is a simple consequence of the fact that we can sum up in each ei

independently:

S_X^d = 2^−B 3^j1

)

0<ei<βi

j0+1≤i≤d

,d i=j0+1

(2^ei−2^−ei) =2^−B 3^|j1|

,d i=j0+1

)

0<ei<βi

(2^ei−2^−ei)

= 2^−B 3^j1

,d i=j0+1

(2^βi+ 2·2^−βi−3)

= 2^−!j0i=1βi ,d i=j0+1

1 + 2·4^−βi−3·2^−βi

3 .

The next proposition is the key to our proof. It exhibits a recursion relation betweenS^d_X for different values of dand will reduce the proof of Proposition 9 to the case j₂= 0 and the study of a residual term denoted byT_X^d.

Proposition 16. Forj₂≥1andX = (

j0

% &# $ 0, . . . ,0,

j1

% &# $ 1, . . . ,1,

j2

% &# $

2, . . . ,2), we have S_X^d = 21−4^−βd

3 S_X^d−1−2T_X^d, where

T_X^d = 4^−B0,1 3^j1+j2

,d i=j0+j1+1

(1−4^−βi) )

0<ei<βi

j0+1≤i≤j0+j1

j0,+j1

i=j0+1

(4^ei−1) )

0≤ei,!

ei<B0,1−E1

j0+j1+1≤i≤d−1

1.

Proof. ReplacingP(e_i) by its expression, we get S_X^d =

j0

,

i=1

2^−βi )

0<ei<βi

j0+1≤i≤j0+j1

j0,+j1

i=j0+1

2^−βi

3 (2^ei−2^−ei) )

βi≤ei

!ei<B−E1

j0+j1+1≤i≤d

,d i=j0+j1+1

2^βi−2^−βi 3 2^−ei

=2^−B0,1 3^j1+j2

,d i=j0+j1+1

(1−4^−βi) )

0<ei<βi

j0+1≤i≤j0+j1

j0,+j1

i=j0+1

(2^ei−2^−ei) )

0≤ei

!ei<B0,1−E1

j0+j1+1≤i≤d

,d i=j0+j1+1

2^−ei,

lettingei =ei−βi forj0+j1+ 1≤i≤d. We now explicitly compute the sum on

ed:

S_X^d = 2^−B0,1 3^j1+j2

,d i=j0+j1+1

(1−4^−βi) )

0<ei<βi

j0+1≤i≤j0+j1

j0,+j1

i=j0+1

(2^ei−2^−ei)

)

0≤ei

!ei<B0,1−E1

j0+j1+1≤i≤d−1 d−1,

i=j0+j1+1

2^−ei9 29

1−2^{−B0,1+E1+!d−1i=j0+j1+1ei}::

= 21−4^−βd

3 S^d−1_X −24^−B0,1 3^j1+j2

,d i=j0+j1+1

(1−4^−βi) )

0≤ei

!ei<B0,1−E1

j0+j1+1≤i≤d−1

1

= 21−4^−βd

3 S^d−1_X −2T_X^d.

2.3. The Residual TermT_X^d

We now study the termT_X^d forj₂≥1 andX = (

j0

% &# $ 0, . . . ,0,

j1

% &# $ 1, . . . ,1,

j2

% &# $

2, . . . ,2) and show thatfd has the following expression.

Proposition 17. Forj₂≥1andX = (

j0

% &# $ 0, . . . ,0,

j1

% &# $ 1, . . . ,1,

j2

% &# $ 2, . . . ,2), T_X^d = 1

3^j2 ,d i=j0+j1+1

(1−4^−βi)Σ^d_X where

Σ^d_X= 4^−!j0i=1βi 3^j1(j2−1)!

j)2−1 l=0

5j₂−1 l

6 )

k+k_j0+1+...+k_j0+j1=l

1 l

k, kj0+1, . . . , kj0+j1

2 ;)j0

i=1

βi

<^k Π^d_X

and

Π^dX= "

{^{j0≤j≤j0+j1|kj=0}}

1−4^−βj−3βj4^−βj 3

"

{^{j0≤j≤j0+j1|kj$=0}} '

Ak_j(1−4^−βj)− ( 1

kj+ 1β_j^kj+1+5 6β_j^kj

+

k!_j−1 i=1

'kj

i ) (

Ai+Bi+1

i+ 1

* β^kj−i

* 4^−βj

) .

Also,Σ^d_Xis a sum forI⊂{j0+ 1, . . . , j0+j1}of terms of the form4^{−!ji=10 βi−!i∈Iβi} multiplied by a multivariate polynomial of degree inβ_i exactlyj₂ if i∈I, j₂−1if 1≤i≤j₀,0otherwise, and of total degree j₂+|I|−1.

The end of this subsection is devoted to the proof of this proposition. This is a quite technical part, but it is also of great interest to prove Proposition 10.

We denote byR^d_X the sum at the end ofT_X^d:

R^d_X= )

0≤ei,!

ei<B0,1−E1

j0+j1+1≤i≤d−1

1,

which is simply the number ofj₂−1-tuples of natural integers such that their sum is strictly less thanB0,1−E1; and byΣ^d_X the sum on theei’s forj0+1≤i≤j0+j₁:

Σ^d_X =4^−B0,1 3^j1

)

0<ei<βi

j0+1≤i≤j0+j1

j0,+j1

i=j0+1

(4^ei−1)R^d_X,

so T_X^d is given by

T_X^d = 1 3^j2

,d i=j0+j1+1

(1−4^−βi)Σ^d_X.

We first check the proposition for j2 = 1. Then R^d_X = 1 and the sum Σ^d_X to compute is

Σ^d_X =4^−B0,1 3^j1

)

0<ei<βi

j0+1≤i≤j0+j1

j0,+j1

i=j0+1

(4^ei−1) = 4^−B0,1 3^j1

j0,+j1

i=j0+1

4^βi−1−3βi

3

=4^{−!ji=00 βi} 3^j1

j0,+j1

i=j0+1

1−4^−βi−3β_i4^−βi

3 ,

so T_X^d becomes T_X^d = 1

3(1−4^−βd)4^{−!ji=00 βi} 3^j1

j0,+j1

i=j0+1

1−4^−βi−3β_i4^−βi 3

which is what the proposition states.

Let us now proceed to a general j2 ≥ 1. In what follows Bi is a Bernoulli number [6, Formula 6.78] (hereB1= 1/2) and5

i j 6

is an unsigned Stirling number

of the first kind [6, Section 6.1]. We recall that the sum of the first n k-th powers is given as a polynomial innby

)n i=0

i^k = 1 k+ 1

)k i=0

1k+ 1 i

2

B_in^k+1−i. Here is a classical combinatorial lemma.

Lemma 18. Forn≥1andm >0, the number ofn-tuples of natural integers such that their sum is strictly less than mis given by

)

0≤i!_nj,1≤j≤n

j=1ij<m

1 =1

n+m−1 n

2

= 1 n!

)n l=1

5n l

6 m^l.

Proof. This is indeed the same thing as the number of (n+ 1)-tuples of natural integers such that their sum is exactlym−1.

Then the sumR^d_X inT_X^d forj₂≥1, which counts the number ofj₂−1-tuples of natural integers such that their sum is strictly less thanB_0,1−E₁, is given by the following expression:

R_X^d = 1 (j₂−1)!

j)2−1 l=0

5j₂−1 l

6

(B_0,1−E₁)^l

= 1

(j₂−1)!

j)2−1 l=0

5j₂−1 l

6

× )

k+kj0+1+···+kj0+j1=l

1 l

k, kj0+1, . . . , kj0+j1

2 ;)^j0

i=1

β_i

<_{k j0+j1} ,

i=j0+1

(β_i−e_i)^ki.

AndΣ^d_X becomes Σ^d_X =4^−B0,1

3^j1

)

0<ei<βi

j0+1≤i≤j0+j1

j0,+j1

i=j0+1

(4^ej−1)R^d_X

= 4^{−!ji=10 βi} 3^j1(j₂−1)!

j)2−1 l=0

5j₂−1 l

6

× )

k+kj0+1+...+kj0+j1=l

1 l

k, k_j0+1, . . . , k_j0+j1 2 ;)^j0

i=1

β_i

<^k Π^d_X,

whereΠ^d_X is defined as

Π^d_X = 4^{−!ji=j0+0+1j1 βi}

j0,+j1

i=j0+1 β)i−1 ei=1

(β_i−ei)^ki(4^ei−1).

We now study the different sums one_iaccording to the value ofk_i. We drop the subscripts for clarity.

Ifk= 0, then the sum is simply

β−1)

e=1

(4^e−1) =

β−1)

e=0

(4^e−1) = 4^β−1−3β

3 .

Whenk≥1, we do the change of summation variablee=β−e, so that the sum becomes

β−1)

e=1

(β−e)^k(4^e−1) = 4^β

β−1)

e=1

(β−e)^k(1/4)^β−e−

β−1)

e=1

(β−e)^k

= 4^β

β−1)

e=1

e^k4^−e−

β−1)

e=1

e^k.

The second part of this difference is related to the sum of the firstn k-th powers.

Here we sum up toβ−1 so the formula is slightly different:

β−1)

e=0

e^k = 1 k+ 1

)k i=0

(−1)¹ⁱ⁼¹1 k+ 1

i 2

Biβ^k+1−i. For the first part, the sum(n

i=1i^kzⁱis a multivariate polynomial inn,zandzⁿ of degree exactlyk innand 1 inzⁿ. More precisely the series(∞

i=0i^kzⁱ is related to the Eulerian numbers =

k i

>

[6, Section 6.2] defined by

=0 i

>

= 1i=0,

=k i

>

= (i+ 1)= k−1

i

>

+ (k−i)= k−1

i−1

>

fork >0, and expressed in closed form as [6, Formula 6.38]

=k i

>

= )i j=0

(−1)^j 1k+ 1

j 2

(i+ 1−j)^k.

The series is then given by the following classical formula fork≥1 and|z|<1:

)∞ i=1

i^kzⁱ= (k

j=0

=k j

>

z^j+1 (1−z)^k+1 .

The formula for the truncated sum is slightly more involved as stated in the next lemma.

Lemma 19. Fork≥1and|z|$= 1, )n

i=1

i^kzⁱ= (k

j=0A0(k, j)z^j+1 (1−z)^k+1 −

9(k i=0

?_k

i

@ 9(_k

j=0Ai(k, j)z^j+1: nⁱ:

zⁿ

(1−z)^k+1 ,

where A_i(k, j) is defined by the same recursion relation as = k j

>

and the initial conditions:

Ai(i, j) =Ai(i+ 1, j) = (−1)^j1 i j

2 . In particular, A₀(k, j) ==

k j

>

and we have the simple recursion formula fori≥1:

Ai(k, j) =A_i−1(k−1, j)−A_i−1(k−1, j−1).

We are interested in the case wherez= 1/4,n=β−1 and 1≤k≤j2−1, which is written as

β−1)

e=1

e^k4^−e= (k

j=0A₀(k, j)4^−j−1 (3/4)^k+1

− 9(_k−1

i=0

?_k

i

@ 9(k

j=0A_i(k, j)4^−j−1: βⁱ:

4^−β (3/4)^k+1

− 9(k

j=0A_k(k, j)4^−j: β^k4^−β

(3/4)^k+1 .

Beware that we are summing up toβ−1 and notβ, so the expression is slightly different from the one above.

Moreover we have the identity given in the following lemma.

Lemma 20. For0≤i≤k, 3

)k j=0

A_i(k, j)4^−j = 4

k+1)

j=0

A_i+1(k+ 1, j)4^−j.