A CONGRUENTIAL IDENTITY AND THE 2-ADIC ORDER OF LACUNARY SUMS OF BINOMIAL COEFFICIENTS

Gregory Tollisen

Department of Mathematics, Occidental College, 1600 Campus Road, Los Angeles, USA

                            tollisen@oxy.edu

Tamás Lengyel

Department of Mathematics, Occidental College, 1600 Campus Road, Los Angeles, USA

                            lengyel@oxy.edu

Received: 7/7/03, Revised: 3/26/04, Accepted: 4/1/04, Published: 4/2/04

Abstract

In this paper we obtain a universal lower bound on the 2-adic order of lacunary sums of binomial coefficients. By means of necessary and sufficient conditions, we determine the set of values for which the bound is achieved and show the periodicity of the set. We prove a congruential identity for the corresponding generating function. Our approach gives an alternative and transparent proof for some results derived recently by the second author and extends them. We also propose a conjecture that implies a recursion for calculating the 2-adic order of the lacunary sums for almost all values. A congruence in the style of Lucas is proved for the lacunary sums considered.

1. Introduction

We define the lacunary binomial sum

G_{n,l}(k) = ∑_{t=0}^{⌊k/n⌋} \binom{k}{l + nt},  (1)

with l : 0 ≤ l ≤ n − 1, and consider the situation where n = p^{m}, p prime, m ≥ 1. Lacunary sums arise naturally in combinatorial contexts and have been studied in the past ([1], [2], [4], [5], [6], [8], [9], [10], and [11]). The p-adic order of G_{p^{m},l}(k) was explored in [6]. For p > 2, the exact p-adic order of G_{p^{m},l}(k) was obtained using a theorem of Stickelberger [4]. The 2-adic order of G_{2^{m},l}(k) was found on select regular sequences of values for k involving multiples of 2^{m−1} through use of the vertical generating function

g_{n,l}(x) = ∑_{k=0}^{∞} G_{n,l}(k)x^{k} = \frac{x^{l}(1 − x)^{n−l−1}}{(1 − x)^{n} − x^{n}}

(n ≥ 1 and l = 0, 1, …, n − 1) in combination with multisection techniques to prove (among other results) that

ρ_{2} (G_{2^{m},l}(k)) ≥ ⌊\frac{k}{2^{m−1}} ⌋ − 1  (2)

for l = 0. Equality holds in (2) if k = c2^{m} with l = 0 or 2^{m−1}, or if k = c2^{m} + l, c2^{m−1} − 1 with l = 0, 1, …, 2^{m}−1. That equality is not always attained is verified by the result (also proved in [6]) that ρ_{2} (G_{2^{m},0}(k)) = 2 (⌊\frac{k}{2^{m−1}} ⌋ − 1) when k = (2c − 1)2^{m−1}. In this paper, we prove that (2) is true for all k and l (cf. remarks in Section 3), and we characterize the necessary and sufficient conditions for equality (cf. corollary in Section 4).

Our primary focus is (1 + x)^{k} mod (x^{2^{m}} − 1) since the horizontal generating function ∑_{l=0}^{2^{m}−1} G_{2^{m},l}(k)x^{l} is obtained when (1 + x)^{k} is reduced mod (x^{2^{m}} − 1) according to the congruence

∑_{l=0}^{2^{m}−1} G_{2^{m},l}(k)x^{l} ≡ (1 + x)^{k} mod (x^{2^{m}} − 1).

Our main result is the theorem to be found in Section 3, wherein we identify the common power of 2 in the coefficients of (1 + x)^{k} mod (x^{2^{m}} − 1) for each value of k. After dividing out by the common power, we further reduce mod 2, to obtain a congruential factorization of the quotient into simple canonical factors based on the digits of the binary expansion of k. Our proof is by induction on m, and ultimately relies on repeated substitution of x^{2} for x in congruences of the form p(x) ≡ q(x) mod (x^{2^{m−1}} − 1) to yield p(x^{2}) ≡ q(x^{2}) mod (x^{2^{m}} − 1) for polynomials p(x) and q(x).

Our approach is similar to some others used in analyzing congruential and divisibility properties, and p-adic orders of binomial coefficients [4]. In particular, a result by Lucas [7] states that

\binom{k}{l} ≡ \binom{ε_{0}}{γ_{0}}\binom{ε_{1}}{γ_{1}} ⋯ \binom{ε_{d}}{γ_{d}} mod p,

where k = ε_{0} + ε_{1}p + … + ε_{d}p^{d} and l = γ_{0} + γ_{1}p + … + γ_{d}p^{d} in prime base p. To set a context for our result, in Section 2 we prove congruence (3) for G_{p^{m},l}(k), p ≥ 2, à la Lucas [7], and explain why the congruence trivializes in the case of G_{2^{m},l}(k), thus leaving a gap that the corollary, in some sense, fills.

2. A congruence for G_{p^{m},l}(k), p > 2

Because we will be reducing polynomials mod p and mod (x^{p^{m}} − 1), both for p = 2 and p > 2, followed by a further reduction mod (p, x^{p^{m}} − 1), we begin by briefly explaining what we mean in each case. A polynomial s(x) ∈ Z[x] is reduced to r_{1}(x) mod p if s(x) = pq_{1}(x) + r_{1}(x) where q_{1}(x), r_{1}(x) ∈ Z[x] and the coefficients of r_{1}(x) are restricted to the values 0, 1, …, p − 1. The polynomial s(x) is reduced to pq_{2}(x) + r_{2}(x) mod (x^{p^{m}}−1) and to r_{2}(x) mod (p, x^{p^{m}}−1) if s(x) = (x^{p^{m}} − 1) q_{3}(x)+pq_{2}(x)+r_{2}(x) where q_{2}(x), q_{3}(x), r_{2}(x) ∈ Z[x], deg(q_{2}(x)), deg(r_{2}(x)) < p^{m}, and the coefficients of r_{2}(x) are restricted to the values 0, 1, …, p − 1. Two polynomials are in the same congruence class if they reduce under the congruence modulus to the same polynomial. These define ring homomorphisms between Z[x] → Z_{p}[x] → Z_{p}[x]/⟨x^{p^{m}} − 1⟩ and between Z[x] → Z[x]/⟨x^{p^{m}} − 1⟩ → Z_{p}[x]/⟨x^{p^{m}} − 1⟩ allowing us in each case to safely sequentially reduce.

We proceed by obtaining a Lucas-type result by a “Fine-styled” [3] argument. Let k = ε_{0} + ε_{1}p + … + ε_{d}p^{d} in base p. Kummer’s carry counting shows that p|\binom{p}{l} if and only if l ≠ 0, p, which immediately implies (1 + x)^{p} ≡ 1 + x^{p} mod p, and after inducting on m, that (1 + x)^{p^{m}} ≡ 1 + x^{p^{m}} mod p. Thus,

(1 + x)^{k} ≡ (1 + x)^{ε_{0}}(1 + x^{p})^{ε_{1}}(1 + x^{p^{2}})^{ε_{2}} … (1 + x^{p^{d}})^{ε_{d}} ≡ ∏_{j=0}^{d}(1 + x^{p^{j}})^{ε_{j}} mod p.

Now, by further reducing mod (p, x^{p^{m}} −1), we use the fact that 1+x^{p^{j}} ≡ 2 mod (p, x^{p^{m}} − 1) for j ≥ m to conclude that

(1 + x)^{k} ≡ ( ∏_{j=m}^{d}(1 + x^{p^{j}})^{ε_{j}}) ( ∏_{j=0}^{m−1}(1 + x^{p^{j}})^{ε_{j}}) mod p
≡ 2^{ε_{m}+ε_{m+1}+...+ε_{d}} ∏_{j=0}^{m−1} ( ∑_{γ_{j}=0}^{ε_{j}} \binom{ε_{j}}{γ_{j}}x^{γ_{j}p^{j}}) mod(p, x^{p^{m}} − 1)
≡ 2^{ε_{m}+ε_{m+1}+...+ε_{d}} ∑_{l=0}^{p^{m}−1} ( ∏_{j=0}^{d} \binom{ε_{j}}{γ_{j}}) x^{l}  mod(p, x^{p^{m}} − 1)

where l = γ_{0} + γ_{1}p + … + γ_{d}p^{d} ≤ p^{m} − 1. After noting that ∑_{l=0}^{p^{m}−1} G_{p^{m},l}(k)x^{l} ≡ (1 +

x)^{k} mod (x^{p^{m}} − 1) and using Fermat’s little theorem, we immediately arrive at the

Lemma (à la Lucas). For p > 2 and prime, and for k = ε_{0} + ε_{1}p + … + ε_{d}p^{d} and l = γ_{0} + γ_{1}p + … + γ_{m−1}p^{m−1} in base p,

G_{p^{m},l}(k) ≡ 2^{ε_{m}+ε_{m+1}+...+ε_{d}} \binom{ε_{0}}{γ_{0}}\binom{ε_{1}}{γ_{1}} ⋯ \binom{ε_{m−1}}{γ_{m−1}} ≡ 2^{⌊k/p^{m}⌋}\binom{k′}{l} mod p  (3)

where k′ is the least nonnegative remainder of k when divided by p^{m}.

The lemma also can be proved by reducing all of the terms of (1) by applying Lucas’ theorem and after factoring out \binom{k′}{l}, summing the quotients to get the other factor in (3). This idea was extended in the proof of Theorem 1 in [6].

We exclude p = 2, not because the lemma fails in this case, but because the power of 2 trivializes the identity to G_{2^{m},l}(k) ≡ 0 mod 2 as soon as k ≥ 2^{m}.

Note that [6, page 3] provides an alternative congruence mod p^{m+1} for G_{p,l}(cp^{m} + i), 0 ≤ i < l ≤ p − 1, m ≥ 1.

3. A congruential identity for (1 + x)^{k}, p = 2

Were we to devise a nontrivial result along the lines of Lucas for the case 2^{m} following an argument in the style of Fine, for each k we would first need to factor out the common power of 2 in (1 + x)^{k} mod (x^{2^{m}} − 1), and then consider the remaining factor mod(2, x^{2^{m}} − 1) as we do in the following

Theorem. For m ≥ 1 and k ≥ 2^{m−1}, 2^{⌊k/2^{m−1}⌋−1}|(1+x)^{k} mod (x^{2^{m}} −1). Furthermore, for m = 1 and k ≥ 1: (1 + x)^{k} ≡ 2^{k−1}(1 + x) mod (x^{2} − 1). For m ≥ 2 and k ≥ 1, if k = ε_{0} + 2ε_{1} + 4ε_{2} + … + 2^{m−1}ε_{m−1} + 2^{m}q with 0 ≤ ε_{0}, ε_{1}, …, ε_{m−1} ≤ 1 then:

1. when q = 0 (i.e., 1 ≤ k < 2^{m}):

(1 + x)^{k} ≡ (1 + ε_{0}x)(1 + ε_{1}x^{2})(1 + ε_{2}x^{4}) … (1 + ε_{m−2}x^{2^{m−2}})(1 + ε_{m−1}x^{2^{m−1}}) mod 2,

2. when q > 0 (i.e., k ≥ 2^{m}):

\begin{matrix}(1 + x)^{k} ≡ \\ ≡ 2^{⌊k/2^{m−1}⌋−1}(1 + ε_{0}x)(1 + ε_{1}x^{2})(1 + ε_{2}x^{4}) … \\ … (1 + ε_{m−2}x^{2^{m−2}})x^{2^{m−2}ε_{m−1}}(1 + x^{2^{m−1}}) & mod(2^{⌊k/2^{m−1}⌋}, x^{2^{m}} − 1). \end{matrix} (4)

Remarks. Before presenting the proof, we first note that the theorem instantly implies that ρ_{2} (G_{2^{m},l}(k)) ≥ ⌊\frac{k}{2^{m−1}} ⌋−1. Second, we wish to draw the reader’s attention to the last three factors in congruence (4) that, when combined, break the regular pattern followed by the preceding factors of lower degree, and thus, play a significant role in determining the conditions under which equality is reached, as will be explored in the corollary in the next section.

Proof. We cover the case m = 1 with the preliminary

Claim 0. (1 + x)^{k} ≡ 2^{k−1}(1 + x) mod (x^{2} − 1), for k ≥ 1.

Proof. Note that (1 + x)^{2} ≡ 2(1 + x) mod (x^{2} − 1) and induct. □

The case when q = 0 easily follows because in this case, if k ≥ 2^{m−1} then 2^{⌊k/2^{m−1}⌋−1} = 1, and for p ≥ 0, (1+x)^{2^{p}} ≡ 1+x^{2^{p}} mod 2. For the case when q > 0, we proceed by induction on m.

BASE STEP: We begin by establishing the result for m = 2 (i.e., mod(x^{4} − 1)).

Claim 1. 2^{⌊k/2⌋−1}|(1 + x)^{k} mod (x^{4} − 1), for k ≥ 4.

Proof. Let k = ε_{0} + 2ε_{1} + 4q and let r = ⌊\frac{k}{2}⌋ = ε_{1} + 2q. Then

(1 + x)^{2r} = [(1 + x^{2}) + 2x]^{r} = (2x)^{r} + ∑_{t=1}^{r} \binom{r}{t}(1 + x^{2})^{t}(2x)^{r−t}
≡ 2^{r}x^{r} + ∑_{t=1}^{r} \binom{r}{t}2^{t−1}(1 + x^{2})2^{r−t}x^{r−t}  mod(x^{4} − 1)
≡ 2^{r}x^{r} + 2^{r−1}(1 + x^{2}) [∑_{t=0}^{r} \binom{r}{t}x^{r−t} − x^{r}]  mod(x^{4} − 1)
≡ 2^{r−1} [x^{r}(1 − x^{2}) + (1 + x^{2})(1 + x)^{r}]  mod(x^{4} − 1)

where, in the first congruence of the sequence, Claim 0 was used with x^{2} replacing x. Thus 2^{r−1} divides (1 + x)^{k} when reduced mod(x^{4} − 1). □

From now on, for notational convenience only, we move the power of 2 to the left.

Claim 2. 2^{−⌊k/2⌋+1}(1 + x)^{k} ≡ (1 + ε_{0}x)x^{ε_{1}}(1 + x^{2}) mod (2, x^{4} − 1) for k ≥ 4 (i.e., q ≥ 1).

Proof. Continuing with the previous congruence,

2^{−r+1}(1 + x)^{2r} ≡ x^{r}(1 − x^{2}) + (1 + x^{2})(1 + x)^{r}  mod(x^{4} − 1)
≡ x^{ε_{1}+2q}(1 − x^{2}) + (1 + x^{2})(1 + x)^{ε_{1}+2q}  mod(x^{4} − 1)
≡ x^{ε_{1}} [x^{2q}(1 − x^{2})] + (1 + x)^{ε_{1}} [(1 + x^{2}) ((1 + x)^{2})^{q}] mod(x^{4} − 1)
≡ x^{ε_{1}}(x^{2q} + x^{2q+2})+(1 + x)^{ε_{1}}[(1 + x^{2})^{2} ((1 + x)^{2})^{q−1}] mod(2, x^{4} − 1)

(recall that q ≥ 1)

≡ x^{ε_{1}}(1 + x^{2})  mod(2, x^{4} − 1)

Finish by multiplying both sides by (1 + x)^{ε_{0}} = 1 + ε_{0}x. □

INDUCTION STEP: We assume the theorem true for m − 1 (i.e., mod(x^{2^{m−1}} − 1)) and prove it true for m (i.e., mod(x^{2^{m}} − 1)), m ≥ 3.

Claim 3. Under the induction hypothesis, 2^{⌊k/2^{m−1}⌋−1}|(1 + x)^{k} mod (x^{2^{m}} − 1), for k ≥ 2^{m} (i.e., q ≥ 1).

Proof. Let k = ε_{0} + 2ε_{1} + 4ε_{2} + … + 2^{m−1}ε_{m−1} + 2^{m}q and r = ⌊\frac{k}{2^{m−1}} ⌋ = ε_{m−1} + 2q. Then,

(1 + x)^{2^{m−1}r} = [(1 + x^{2}) + 2x]^{2^{m−2}r} = ∑_{t=0}^{2^{m−2}r} \binom{2^{m−2}r}{t}(1 + x^{2})^{t}(2x)^{2^{m−2}r−t}.

Now, from the induction hypothesis, 2^{⌊t/2^{m−2}⌋−1}|(1 + x^{2})^{t} mod (x^{2^{m}} − 1), by replacing x with x^{2}, so 2^{2^{m−2}r−t+⌊t/2^{m−2}⌋−1} is a factor of the tth term of the sum, which takes on the minimum value of 2^{r−1} at t = 2^{m−2}r and t = 2^{m−2}r − 1. Thus, 2^{r−1}|(1 + x)^{2^{m−1}r} mod (x^{2^{m}} − 1) and the claim follows. □

Claim 4. Under the induction hypothesis, 2^{−⌊k/2^{m−1}⌋+1}(1+x)^{k} ≡ (1+ε_{0}x)(1+ε_{1}x^{2})(1+ ε_{2}x^{4}) ⋯ (1 + ε_{m−2}x^{2^{m−2}})x^{2^{m−2}ε_{m−1}}(1 + x^{2^{m−1}}) mod (2, x^{2^{m}} − 1), for k ≥ 2^{m} (i.e., q ≥ 1).

Proof. Multiply both sides of the equation in Claim 3 by 2^{−r+1} = 2^{−ε_{m−1}−2q+1} and reduce mod(x^{2^{m}} − 1) to get

\begin{matrix}2^{−r+1}(1 + x)^{2^{m−1}r} ≡ ∑_{t=0}^{2^{m−2}r−2} \binom{2^{m−2}r}{t} [2^{−r+1}(1 + x^{2})^{t}] (2x)^{2^{m−2}r−t}+ \\ +\binom{2^{m−2}r}{2^{m−2}r−1} [2^{−r+1}(1 + x^{2})^{2^{m−2}r−1}(2x)] + \binom{2^{m−2}r}{2^{m−2}r} [2^{−r+1}(1 + x^{2})^{2^{m−2}r}] mod (x^{2^{m}} − 1) \end{matrix}

≡ 2^{−r+1}(1 + x^{2})^{2^{m−2}r}  mod(2, x^{2^{m}} − 1)

(all terms but the last are even)

≡ 2^{−ε_{m−1}−2q+1}(1 + x^{2})^{2^{m−2}ε_{m−1}+2^{m−1}q} mod(2, (x^{2})^{2^{m−1}} − 1)
≡ (x^{2})^{2^{m−3}ε_{m−1}}(1 + (x^{2})^{2^{m−2}})  mod(2, (x^{2})^{2^{m−1}} − 1)

(applying induction hyp. with x^{2} replacing x)

≡ x^{2^{m−2}ε_{m−1}}(1 + x^{2^{m−1}})  mod(2, x^{2^{m}} − 1)

Finish by multiplying both sides by (1+x)^{ε_{0}+2ε_{1}+4ε_{2}+...+2^{m−2}ε_{m−2}} ≡ (1+ε_{0}x)(1+ε_{1}x^{2})(1+ ε_{2}x^{4}) … (1 + ε_{m−2}x^{2^{m−2}}) mod 2. □

This truly concludes our proof of the theorem. □

4. A note, a corollary, and a conjecture

We conclude the paper with some comments, our primary application with consequences, and a conjecture.

Note. By replacing each instance of x with the 2^{m} × 2^{m} forward shift permutation matrix

E = circ[0, 1, 0, …, 0] = ( \begin{matrix}0 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & 1 & ⋯ & 0 & 0 \\ 0 & 0 & 0 & ⋯ & 0 & 0 \\ · & · & · & ⋯ & · & · \\ 0 & 0 & 0 & ⋯ & 0 & 1 \\ 1 & 0 & 0 & ⋯ & 0 & 0 \end{matrix} )

and observing that E^{t} ≠ I for t < 2^{m} while E^{2^{m}} = I, the theorem translates to modulo 2 congruential matrix identities for (I + E)^{k} after removing the elementwise common power of 2 [11]. (In fact, if C is the ring of 2^{m} × 2^{m} circulant matrices with integer coefficients, then C ≅ Z[x]/⟨x^{2^{m}} − 1⟩, the isomorphism being A ⟼ p_{A}(x), where p_{A}(x) is the auxiliary polynomial associated with the circulant matrix A.)

Corollary. For m ≥ 1, 0 ≤ l < 2^{m}, k ≥ 2^{m−1}, we have ρ_{2}(G_{2^{m}, l}(k)) ≥ ⌊\frac{k}{2^{m−1}} ⌋ − 1, where G_{n,l}(k) is as in (1). Furthermore, if

k = ε_{0} + 2ε_{1} + 4ε_{2} + … + 2^{m−1}ε_{m−1} + 2^{m}q

and

l = γ_{0} + 2γ_{1} + 4γ_{2} + … + 2^{m−1}γ_{m−1}

with 0 ≤ ε_{i}, γ_{i} ≤ 1, then

1. when q = 0, equality holds if and only if ε_{i} ≥ γ_{i}, i = 0, 1, …, m − 1, i.e., if and only if l, k − l ≥ 0 have no carries when added.

2. when q > 0, equality holds if and only if ε_{i} ≥ γ_{i}, i = 0, 1, …, m − 3, and γ_{m−2} + γ_{m−1} ≥ ε_{m−1} if ε_{m−2} = 1 or γ_{m−2} = ε_{m−1} if ε_{m−2} = 0. (In fact, these two alternatives can be collapsed to −ε_{m−2} ≤ ε_{m−1} − γ_{m−2} ≤ ε_{m−2}γ_{m−1}.)

Case 1 can be written as

G_{2^{m},l}(k) ≡ \binom{ε_{0}}{γ_{0}}\binom{ε_{1}}{γ_{1}} ⋯ \binom{ε_{m−1}}{γ_{m−1}} mod 2,

while Case 2 can be partially represented by a similar form in line with congruence (4).

The proof of the corollary depends on using the theorem from Section 3 to determine the powers of 2^{−⌊k/2^{m−1}⌋+1}(1 + x)^{k} mod (2, x^{2^{m}} − 1) with nonzero coefficients. This is easily done, except perhaps when taking into account the last three factors in congruence (4). To handle these factors, one can simply but painstakingly check for all possible assignments of 0 and 1 to ε_{m−2}, ε_{m−1}, γ_{m−2}, and γ_{m−1}.

Note. The second case in the corollary with l = 0, k ≥ 2^{m}, gives an instant proof of Conjecture 1 in [6]: the lower bound is achieved in (2) for 75% of the k values. Similarly, Conjectures 2 and 3 hold for the very same values.

Conjecture. The same process as above can be used to get a recursion for the lacunary binomial sums G_{2^{m},l}(k) themselves. We argue as follows:

(1 + x)^{2q} = [2x + (1 + x^{2})]^{q} = ∑_{t=0}^{q} \binom{q}{t}(2x)^{t}(1 + x^{2})^{q−t}

Thus,

\begin{aligned}∑_{l=0}^{2^{m}−1} G_{2^{m},l}(2q)x^{l} & ≡ ∑_{t=0}^{q} \binom{q}{t}2^{t}x^{t} [ ∑_{u=0}^{2^{m−1}−1} G_{2^{m−1},u}(q − t)(x^{2})^{u}] & mod((x^{2})^{2^{m−1}} − 1) \\ & ≡ ∑_{t=0}^{q} ∑_{u=0}^{2^{m−1}−1} \binom{q}{t}2^{t}G_{2^{m−1},u}(q − t)x^{t+2u} & mod(x^{2^{m}} − 1) \end{aligned}

One then matches the powers of x. The result differs slightly depending on the parity of l. So, let l = 2j + ε where ε is 0 or 1. Then, G_{2^{m},l}(2q) = \binom{q}{ε}2^{ε}G_{2^{m−1}, j}(q − ε) + \binom{q}{ε+2}2^{ε+2}G_{2^{m−1}, j−1}(q − ε − 2) + \binom{q}{ε+4}2^{ε+4}G_{2^{m−1}, j−2}(q − ε − 4) + … where the second subscript of G is taken mod2^{m−1}. We conjecture, supported by numerical evidence, that for each m, ρ_{2}(G_{2^{m},l}(k)) is equal to the diadic order of the leading term of the sum with a finite number of exceptions. Assuming the conjecture, we can find a simple recursion for the diadic order of the lacunary binomial sums. For m > 2,

ρ_{2}(G_{2^{m},2j+ε}(2q)) = \{ \begin{matrix}ρ_{2}(G_{2^{m−1}, j}(q)), & if ε = 0, \\ ρ_{2}(q) + 1 + ρ_{2}(G_{2^{m−1}, j}(q − 1)), & if ε = 1, \end{matrix}  (5)

ρ_{2}(G_{2^{m},l}(2q + 1)) \{ \begin{matrix}= min \{ρ_{2}(G_{2^{m}, l−1}(2q)), ρ_{2}(G_{2^{m}, l}(2q))\} , & if the orders differ, \\ ≥ ρ_{2}(G_{2^{m}, l}(2q)) + 1, & otherwise. \end{matrix}

The base of the recursion is the following

ρ_{2}(G_{4,l}(k)) = \{ \begin{matrix}2 (⌊\frac{k}{2}⌋ − 1) , & if k − 2l ≡ 2 mod 4, \\ ⌊\frac{k}{2}⌋ − 1, & otherwise, \end{matrix}

valid for k ≥ max {2, l}, as can easily be proved. Again, numerical evidence suggests that for each n = 2^{m} ≥ 4, the recursion (5) gives the exact diadic order of G_{2^{m},l}(k) except possibly for a finite number of small values for k where the recursion only gives a lower bound.

References

[1] D. S. Clark, On some abstract properties of binomial coefficients, Amer. Math. Monthly 89(1982), 433–443.

[2] L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, 1974.

[3] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54(1947), 589–592.

[4] A. Granville, Binomial coefficients modulo prime powers, in preparation at http://www.dms.umontreal.ca/˜ andrew in

   Binomial/index.html or Postscript/binomial.ps, and http://www.cecm.sfu.ca/organics/
   papers/granville/paper/binomial/html/binomial.html

[5] F. T. Howard and R. Witt, Lacunary sums of binomial coefficients. Applications of Fibonacci Numbers, Vol 7: 185–195. Kluwer Academic Publishers, 1998.

[6] T. Lengyel, On the orders of lacunary binomial coefficient sums, INTEGERS, Electronic Journal of Combinatorial Number Theory A3:3(2003), 1–10.

[7] É. Lucas, Sur les congruences des nombres Euleriennes et des coefficients différentiels des functions trigonométrique, suivant un module premier, Bull. Soc. Math. France 6(1878), 49–54.

[8] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, New York, 1958.

[9] Z.-H. Sun and Z.-W. Sun, Fibonacci numbers and Fermat’s last theorem, Acta Arith. 60(1992), 371–388.

[10] Z.-W. Sun, On the sum ∑_{k≡r (mod m)} \binom{n}{k} and related congruences, Israel J. Math. 128(2002), 135–156.

[11] G. Tollisen and T. Lengyel, Averaging around the circle, manuscript, 2003.