\documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{amsfonts} \usepackage{amstext} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \tolerance 10000 %\def\qued{\hfill \vrule height 8pt width6pt depth0pt} \def\qued{\hfill $\Box$} \def\vag{\smallskip\hrule\smallskip} \def\forget#1{} \def\gdefi{1} \def\nulla{2} \def\main{4} \def\rec{5} \def\Lucas{3} \def\CClark{{1}} \def\CComtet{2} \def\FFine{3} \def\GGranville{4} \def\HW{5} \def\IntLengyel{{6}} \def\LLucas{7} \def\RRiordan{8} \def\ZHWSun{9} \def\SSun{{10}} \def\TollisenLengyel{{11}} \begin{document} \begin{center} {\bf {\uppercase {A congruential identity and the $2$-adic order of lacunary sums of binomial coefficients}}} \vskip 20pt {\bf Gregory Tollisen} \\ {{\smallit Department of Mathematics, Occidental College, 1600 Campus Road, Los Angeles, USA}\\ {\tt tollisen@oxy.edu}} \vskip 10pt {\bf Tam\'as Lengyel} \\ {{\smallit Department of Mathematics, Occidental College, 1600 Campus Road, Los Angeles, USA}\\ {\tt lengyel@oxy.edu}}\\ \end{center} \vskip 30pt \centerline{ {\smallit Received: 7/7/03, Revised: 3/26/04, Accepted: 4/1/04, Published: 4/2/04}} \vskip 30pt \centerline{\bf Abstract} \noindent %\begin{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 %horizontal 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. } %\end{abstract} \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY (2004), \#A04\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 1. Introduction} \label{} % We define the lacunary binomial sum $$G_{n, l}(k)= \sum_{t=0}^{ \lfloor k / n \rfloor } { k \choose {l+nt}}, \eqno(\gdefi)$$ with $l: 0\le l\le n-1$, and consider the situation where $n=p^m, \;p$ prime, $m\ge 1$. Lacunary sums arise naturally in combinatorial contexts and have been studied in the past ([\CClark], [\CComtet], [\GGranville], [\HW], [\IntLengyel], [\RRiordan], [\ZHWSun], [\SSun], and [\TollisenLengyel]). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The $p$-adic order of $G_{p^m, l}(k)$ was explored in [\IntLengyel]. For $p>2$, the exact $p$-adic order of $G_{p^m, l}(k)$ was obtained using a theorem of Stickelberger [\GGranville]. 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)=\sum_{k=0}^\infty G_{n, l}(k) x^k ={{x^l(1-x)^{n-l-1}}\over {(1-x)^n-x^n}}$$ \\ ($n\ge 1$ and $l=0,1,\dots, n-1$) in combination with multisection techniques to prove (among other results) that $$\rho_{2} \left(G_{2^{m}, l} (k)\right) \geq \left\lfloor \frac{k}{2^{m-1} } \right\rfloor -1\eqno(\nulla)$$ for $l=0$. Equality holds in (\nulla) if $k=c2^{m} $ with $l=0$ or $2^{m-1}$, or if $k=c2^{m} +l$, $%k= c2^{m-1} -1$ with $l=0,1,\ldots,2^{m}-1$. That equality is not always attained is verified by the result (also proved in [\IntLengyel]) that $\rho_{2}\left(G_{2^{m}, 0}(k)\right) =2\left( \left\lfloor \frac{k}{2^{m-1} } \right\rfloor -1\right) $ when $k=(2c-1)2^{m-1}$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % In this paper, we prove that (\nulla) 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). %%%%%%%%%%%%%%%%%%%%%%%%%\medskip Our primary focus is $(1+x)^{k} \bmod{ (x^{2^{m}}-1)}$ since the horizontal generating function $\sum_{l=0}^{2^{m} -1} G_{2^{m}, l}(k) x^{l}$ is obtained when $(1+x)^k$ is reduced $\bmod{\;(x^{2^m}-1)}$ according to the congruence $$\sum\limits_{l=0}^{2^{m} -1} G_{2^{m}, l}(k) x^{l} \equiv (1+x)^{k} \bmod(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} \bmod(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)\equiv q(x) \bmod(x^{2^{m-1}}-1)$ to yield $p(x^2)\equiv q(x^2) \bmod(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 [\GGranville]. In particular, a result by Lucas [\LLucas] states that % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% $$ {k \choose l}\equiv {\varepsilon_0\choose\gamma_0} {\varepsilon_1\choose\gamma_1} \cdots {\varepsilon_d\choose\gamma_d} \bmod p, $$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% where $k=\varepsilon _{0} +\varepsilon _{1} p+\dots +\varepsilon _{d} p^{d} $ and $l=\gamma _{0} +\gamma _{1} p+\dots +\gamma _{d} p^{d} $ in prime base $p$. To set a context for our result, in Section~2 we prove congruence (\Lucas) for $G_{p^{m} ,l} (k)$, $p\geq 2$, \`a la Lucas [\LLucas], 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 2. A congruence for $G_{p^{m} ,l} (k)$, $p>2$} \label{} 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)\in Z\lbrack x]$ is reduced to $r_{1}(x)$ mod $p$ if $s(x)=p q_{1}(x)+r_{1}(x)$ where $q_{1}(x),\;r_{1} (x)\in Z\lbrack x]$ and the coefficients of $r_{1}(x)$ are restricted to the values $0, 1, \ldots, p-1$. The polynomial $s(x)$ is reduced to $p q_{2}(x)+r_{2}(x)$ mod $(x^{p^{m}}-1)$ and to $r_{2} (x)$ mod $(p,\;x^{p^{m} } -1)$ if $s(x)=\left(x^{p^{m}}-1\right) q_{3} (x)+p q_{2}(x)+r_{2} (x)$ where \hbox{$q_{2}(x),\;q_{3}(x),\;r_{2}(x)\in Z\lbrack x]$}, \hbox{$\deg (q_{2} (x)),\;\deg (r_{2} (x))2$ and prime, and for $k=\varepsilon_{0} +\varepsilon_{1} p+\dots +\varepsilon_{d} p^{d} $ and $l=\gamma_{0} +\gamma_{1} p+\dots +\gamma_{m-1} p^{m-1}$ in base $p$, $$G_{p^{m} ,l} (k)\equiv 2^{\varepsilon_{m} +\varepsilon_{m+1} +\dots+\varepsilon_{d}} {\varepsilon_0\choose \gamma_0} {\varepsilon_1\choose \gamma_1} \cdots {\varepsilon_{m-1}\choose \gamma_{m-1}} \equiv 2^{\left\lfloor k/p^{m} \right\rfloor} %{\varepsilon_0\choose \gamma_0} {\varepsilon_1\choose \gamma_1} \cdots %{\varepsilon_{m-1}\choose \gamma_{m-1}} {k' \choose l} \bmod p\eqno(\Lucas)$$ 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 (\gdefi) by applying Lucas' theorem and after factoring out ${k' \choose l}$, summing the quotients to get the other factor in (\Lucas). This idea was extended in the proof of Theorem~1 in [\IntLengyel]. 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)\equiv 0 \bmod 2$ as soon as $k\geq 2^{m}$. Note that [\IntLengyel, page 3] provides an alternative congruence $\bmod \;p^{m+1}$ for $G_{p,l}(cp^m+i), 0\le i0 $ (i.e., $k\ge 2^m$): $$\begin{array}{llll} \hspace*{-20pt}(1+x)^{k} \equiv \\ \equiv 2^{\left\lfloor k/2^{m-1} \right\rfloor -1}(1+\varepsilon_{0} x) (1+\varepsilon_{1} x^{2}) (1+\varepsilon_{2} x^{4}) \ldots \\ \phantom{\equiv\, }\ldots (1+\varepsilon_{m-2} x^{2^{m-2}}) x^{2^{m-2} \varepsilon_{m-1}} (1+x^{2^{m-1}}) & %\hspace*{-200pt} \bmod (2^{\left\lfloor k/2^{m-1} \right\rfloor },x^{2^{m}} -1). %& %\hspace{100pt} %(\main) \end{array}\eqno(\main)$$ \end{enumerate} \noindent{\bf Remarks. } Before presenting the proof, we first note that the theorem instantly implies that $\rho _{2} \left(G_{2^{m} ,l} (k)\right) \geq \left\lfloor \frac{k}{2^{m-1} } \right\rfloor -1$. Second, we wish to draw the reader's attention to the last three factors in congruence (\main) 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent {\it Proof. } We cover the case $m=1$ with the preliminary \noindent{\bf Claim 0. } % $(1+x)^{k} \equiv 2^{k-1} (1+x) \bmod ( x^{2} -1)$, for % $k\geq 1$. \noindent{\it Proof. } Note that % $(1+x)^{2} \equiv 2(1+x) \bmod ( x^{2} -1)$ and induct. \qued %\medskip \noindent The case when $q=0$ easily follows because in this case, if $k \ge 2^{m-1}$ then $2^{\left\lfloor k/2^{m-1} \right\rfloor -1} =1$, and for $p\geq 0$, $(1+x)^{2^{p} } \equiv 1+x^{2^{p} } \bmod 2$. For the case when $q>0$, we proceed by induction on $m$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf BASE STEP: } We begin by establishing the result for $m=2$ (i.e., $\bmod (x^{4} -1)$). \noindent{\bf Claim 1. } $2^{\left\lfloor k/2\right\rfloor -1} \big|(1+x)^{k} \bmod (x^{4}-1)$, for $k\geq 4$. \noindent{\it Proof. } Let $k=\varepsilon _{0} +2\varepsilon _{1} +4q$ and let $r=\left\lfloor \frac{k}{2} \right\rfloor =\varepsilon_{1} +2q$. Then % $$\begin{array}{lll} (1+x)^{2r} &=\left[ (1+x^{2} )+2x\right] ^{\;r} =(2x)^{r} +\sum\limits_{t=1}^{r} {r\choose t} (1+x^{2} )^{t} (2x)^{r-t} \\ &\equiv 2^{r} x^{r} +\sum\limits_{t=1}^{r}{r\choose t} 2^{t-1} (1+x^{2} )2^{r-t} x^{r-t} &\bmod(x^{4}-1) \\ &\equiv 2^{r} x^{r} +2^{r-1} (1+x^{2} )\left[ \sum\limits_{t=0}^{r}{r\choose t} x^{r-t} -x^{r} \right] &\bmod(x^{4}-1) \\ &\equiv 2^{r-1} \left[ x^{r} (1-x^{2} )+(1+x^{2} )(1+x)^{r} \right] &\bmod( x^{4}-1)\\ \end{array} $$ % 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 $\bmod (x^{4}-1)$. \qued From now on, for notational convenience only, we move the power of 2 to the left. \noindent{\bf Claim 2. } % $2^{-\left\lfloor k/2\right\rfloor +1} (1+x)^{k} \equiv (1+\varepsilon _{0} x)x^{\varepsilon _{1} } (1+x^{2} ) \bmod (2 ,x^{4}-1)$ for $k\geq 4$ (i.e., $q\ge 1)$. \noindent{\it Proof. } Continuing with the previous congruence, % $$ \begin{array}{lll} 2^{-r+1} (1+x)^{2r} \!\!\!\!&\equiv x^{r} (1-x^{2} )+(1+x^{2} )(1+x)^{r} &\!\!\bmod (x^{4}-1)\\ &\equiv x^{\varepsilon _{1} +2q} (1-x^{2})+(1+x^{2} )(1+x)^{\varepsilon _{1} +2q} &\!\!\bmod (x^{4}-1) \\ &\equiv x^{\varepsilon _{1} } \left[ x^{2q} (1-x^{2} )\right] +(1+x)^{\varepsilon _{1} } \left[ (1+x^{2} )\left( (1+x)^{2} \right)^{q} \right] &\!\!\bmod (x^{4}-1) \\ &\equiv x^{\varepsilon _{1} } (x^{2q} +x^{2q+2})\!+\!(1+x)^{\varepsilon_1}\!\! \left[(1+x^2)^2\left((1+x)^2\right)^{q-1}\right] &\!\!\bmod (2, x^{4}-1) \\ &&\!\!\hbox{(recall that $q\ge 1$)}\\ &\equiv x^{\varepsilon _{1} } (1+x^{2}) &\!\!\bmod (2,x^{4}-1) \end{array} $$ % % Finish by multiplying both sides by $(1+x)^{\varepsilon _{0} } =1+\varepsilon _{0} x$. \qued\\ \noindent \medskip \noindent{\bf INDUCTION STEP: } We assume the theorem true for $m-1$ (i.e., $\bmod (x^{2^{m-1}}-1)$) and prove it true for $m$ (i.e., $\bmod (x^{2^{m} } -1)$), $m\geq 3$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf Claim 3. } % Under the induction hypothesis, $2^{\left\lfloor k/2^{m-1} \right\rfloor -1} \big|(1+x)^{k} \bmod (x^{2^{m}}-1)$, for % $k\geq 2^{m}$ (i.e., $q\ge 1)$. \noindent{\it Proof. } Let % $k=\varepsilon _{0} +2\varepsilon _{1} +4\varepsilon _{2} +\dots +2^{m-1} \varepsilon _{m-1} +2^{m} q$ and % $r=\left\lfloor \frac{k}{2^{m-1} } \right\rfloor =\varepsilon _{m-1} +2q$. Then, % $$(1+x)^{2^{m-1} r} =\left[ (1+x^{2} )+2x\right] ^{2^{m-2} r} =\sum\limits_{t=0}^{2^{m-2} r} { 2^{m-2}r \choose t} (1+x^{2} )^{t} (2x)^{2^{m-2} r-t}. $$ % Now, from the induction hypothesis, % $2^{\left\lfloor t/2^{m-2} \right\rfloor -1} \big|(1+x^{2} )^{t} \bmod (x^{2^{m}}-1)$, by replacing $x$ with $x^{2}$, so $2^{2^{m-2} r-t+\left\lfloor t/2^{m-2} \right\rfloor -1} $ is a factor of the $t$th 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} \big|(1+x)^{2^{m-1} r} \bmod (x^{2^{m}}-1)$ and the claim follows. \qued %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf Claim 4. } Under the induction hypothesis, $2^{-\left\lfloor k/2^{m-1} \right\rfloor +1} (1+x)^{k} \equiv (1+\varepsilon_{0} x) (1+\varepsilon_{1} x^{2}) (1+\varepsilon_{2} x^{4}) \cdots (1+\varepsilon_{m-2} x^{2^{m-2}}) x^{2^{m-2} \varepsilon_{m-1} } (1+x^{2^{m-1}}) \bmod (2,x^{2^{m}}-1)$, for $k\geq 2^{m}$ (i.e., $q\ge 1)$. \noindent{\it Proof. } Multiply both sides of the equation in Claim 3 by $2^{-r+1} =2^{-\varepsilon_{m-1} -2q+1} $ and reduce $\bmod (x^{2^{m}}-1)$ to get % $$\begin{array}{lll} 2^{-r+1}(1+x)^{2^{m-1} r} \equiv \sum\limits_{t=0}^{2^{m-2} r-2} { 2^{m-2}r \choose t} % \left[ 2^{-r+1} (1+x^{2} )^{t} \right] (2x)^{2^{m-2} r-t} + \\ \hspace*{15pt}+ { 2^{m-2}r \choose {2^{m-2}r -1}} % \left[ 2^{-r+1} (1+x^{2} )^{2^{m-2} r-1} (2x)\right] + {2^{m-2}r \choose {2^{m-2}r}} % \left[ 2^{-r+1} (1+x^{2} )^{2^{m-2} r} \right] \bmod( x^{2^{m}} -1) \end{array} $$ $$ \begin{array}{lll} \equiv 2^{-r+1} (1+x^{2} )^{2^{m-2} r} &\bmod (2, x^{2^{m}}-1) \\ &(\hbox{all terms but the last are even)} \\ \equiv 2^{-\varepsilon _{m-1} -2q+1} (1+x^{2} )^{2^{m-2} \varepsilon _{m-1} +2^{m-1} q} &\bmod (2,(x^{2})^{2^{m-1}}-1) \\ \equiv (x^{2})^{2^{m-3} \varepsilon_{m-1}} (1+(x^{2})^{2^{m-2}} )&\bmod (2,(x^{2})^{2^{m-1}}-1) \\ &\hbox{(applying induction hyp. with $x^{2}$ replacing $x$)} \\ \equiv x^{2^{m-2} \varepsilon_{m-1} } (1+x^{2^{m-1}}) &\bmod (2,x^{2^{m}}-1) \end{array} $$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Finish by multiplying both sides by % $(1+x)^{\varepsilon _{0} +2\varepsilon _{1} +4\varepsilon_{2} +\dots +2^{m-2} \varepsilon _{m-2} } \equiv (1+\varepsilon_{0} x)(1+\varepsilon _{1} x^{2} )(1+\varepsilon_{2} x^{4} )\ldots (1+\varepsilon_{m-2} x^{2^{m-2}}) \bmod 2$. \qued This truly concludes our proof of the theorem. \qued %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize 4. A note, a corollary, and a conjecture} \label{} % We conclude the paper with some comments, our primary application with consequences, and a conjecture. \noindent{\bf Note. } By replacing each instance of $x$ with the $2^{m} \times 2^{m}$ forward shift permutation matrix $$E=circ\lbrack 0,1,0,\dots,0]=\left( \begin{array}{cccccc} 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 0 \\ \cdot & \cdot & \cdot & \cdots & \cdot & \cdot \\ % 0 & 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & 0 & \cdots & 0 & 0 \end{array} \right) $$ and observing that $E^{t} \neq 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 [\TollisenLengyel]. %%%%%%%%%%% (In fact, if $C$ is the ring of $2^{m} \times 2^{m} $ circulant matrices with integer coefficients, then $C\cong {Z\lbrack x]}/{\left\langle x^{2^{m} } -1\right\rangle}$, the isomorphism being $A\longmapsto p_{A} (x)$, where $p_{A} (x)$ is the auxiliary polynomial associated with the circulant matrix $A$.) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf Corollary. } For $m\geq 1,\;0\leq l<2^{m}, k\geq 2^{m-1}$, we have $\rho_{2}(G_{2^{m}, \;l}(k)) \geq \left\lfloor \frac{k}{2^{m-1} } \right\rfloor -1$, where $G_{n,l}(k)$ is as in (\gdefi). %$G_{n, l}(k)=\sum\limits_{t=0}^{\left\lfloor k/n\right\rfloor}{k \choose l+nt}$. Furthermore, if $$k=\varepsilon_{0}+2\varepsilon_{1} +4\varepsilon_{2} +\dots +2^{m-1} \varepsilon_{m-1}+2^{m}q$$ and $$l=\gamma_{0} +2\gamma_{1} +4\gamma_{2} +\dots +2^{m-1} \gamma_{m-1}$$ with $0\leq \varepsilon_{i}, \gamma_{i} \leq 1$, then %%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \begin{enumerate} \item when $q=0$, equality holds if and only if $\varepsilon_{i} \geq \gamma_{i}$, $i=0, 1, \dots, m-1$, i.e., if and only if $l,\;k-l\geq 0$ have no carries when added. \item when $q>0$, equality holds if and only if $\varepsilon_{i} \geq \gamma_{i}$, $i=0,1,\ldots,m-3,$ and $\gamma_{m-2} +\gamma_{m-1} \geq \varepsilon_{m-1} $ if $\varepsilon_{m-2} =1$ or $\gamma_{m-2} =\varepsilon_{m-1} $ if $\varepsilon_{m-2} =0$. (In fact, these two alternatives can be collapsed to $-\varepsilon_{m-2}\le \varepsilon_{m-1}-\gamma_{m-2}\le \varepsilon_{m-2}\gamma_{m-1}.$) \end{enumerate} \medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Case~1 can be written as % $$G_{2^{m} ,l} (k)\equiv {\varepsilon_0\choose \gamma_0} {\varepsilon_1\choose \gamma_1} \cdots {\varepsilon_{m-1}\choose \gamma_{m-1}}\bmod 2,$$ while Case~2 can be partially represented by a similar form in line with congruence (\main). The proof of the corollary depends on using the theorem from Section~3 to determine the powers of $2^{-\left\lfloor k/2^{m-1} \right\rfloor +1} (1+x)^{k} \bmod (2,\;x^{2^{m}}-1)$ with nonzero coefficients. This is easily done, except perhaps when taking into account the last three factors in congruence (\main). To handle these factors, one can simply but painstakingly check for all possible assignments of 0 and 1 to $\varepsilon_{m-2}, \varepsilon_{m-1}, \gamma_{m-2}$, and $\gamma_{m-1}$. %%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf Note. } The second case in the corollary with $l=0, k\ge 2^m$, gives an instant proof of Conjecture~1 in [\IntLengyel]: the lower bound is achieved in (\nulla) for 75\% of the $k$ values. Similarly, Conjectures~2 and 3 hold for the very same values. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{\bf 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} =\left[ 2x+(1+x^{2} )\right] ^{q} =\sum\limits_{t=0}^{q}{q\choose t} (2x)^{t} (1+x^{2})^{q-t}$$ Thus, %%%%%%%%%%% $$ \begin{array}{lll} \sum\limits_{l=0}^{2^{m} -1}G_{2^{m}, l} (2q)x^{l} &\equiv \sum\limits_{t=0}^{q}{q \choose t} 2^{t} x^{t} \left[ \sum\limits_{u=0}^{2^{m-1}-1}G_{2^{m-1}, u} (q-t)(x^{2} )^{u} \right] &\bmod((x^{2} )^{2^{m-1} } -1)\\ &\equiv \sum\limits_{t=0}^{q}\sum\limits_{u=0}^{2^{m-1} -1}{q\choose t} 2^{t} G_{2^{m-1}, u} (q-t)x^{t+2u} &\bmod(x^{2^{m}}-1) \end{array} $$ % One then matches the powers of $x$. The result differs slightly depending on the parity of $l$. So, let $l=2j+\varepsilon $ where $\varepsilon $ is $0$ or $1$. Then, $G_{2^{m}, l}(2q)={q \choose \varepsilon} 2^{\varepsilon } G_{2^{m-1}, \;j}(q-\varepsilon )+{q\choose \varepsilon+2} 2^{\varepsilon +2} G_{2^{m-1}, \;j-1} (q-\varepsilon-2)+{q\choose \varepsilon+4} 2^{\varepsilon +4} G_{2^{m-1}, \;j-2} (q-\varepsilon -4)+\dots $ where the second subscript of $G$ is taken $\bmod \, 2^{m-1}$. We conjecture, supported by numerical evidence, that for each $m$, $\rho_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$, % $$ \rho_{2}(G_{2^{m}, 2j+\varepsilon}(2q)) = \left\{ \begin{array}{ll} \rho_{2}(G_{2^{m-1}, \;j}(q)), &$if $ \varepsilon =0, \\ \rho_2(q)+1+\rho_{2}(G_{2^{m-1}, \;j}(q-1)), &$if $ \varepsilon =1, \end{array} \right.\eqno(\rec) $$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% $$ \rho_{2}(G_{2^{m}, l} (2q+1)) \left\{ \begin{array}{ll} =\min \left\{ \rho_{2} (G_{2^{m}, \;l-1} (2q)), \rho_{2} (G_{2^{m}, \;l}(2q)) \right\}, &$if the orders differ$,\\ \geq \rho_{2} (G_{2^{m}, \;l}(2q)) +1, &$otherwise$. \end{array} \right. $$ %%%%%%%%%%%%%%%%%%%% The base of the recursion is the following % $$\rho_{2} (G_{4, l}(k)) = \left\{ \begin{array}{ll} 2\left(\left\lfloor \frac{k}{2} \right\rfloor -1\right), &$if $ k-2l\equiv 2 \bmod 4,\\ \left\lfloor \frac{k}{2} \right\rfloor -1, &$otherwise$, \end{array} \right. $$ %%% valid for $k\geq \max \left\{2,l\right\}$, as can easily be proved. Again, numerical evidence suggests that for each $n=2^{m} \geq 4$, the recursion (\rec) 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{\normalsize References} \begin{itemize} \footnotesize \item[{[\CClark]}] {{D.~S.~Clark}, {\rm On some abstract properties of binomial coefficients}, {\it Amer. Math. Monthly}\, {\bf 89}(1982), 433--443.} \item[{[\CComtet]}] {L.~Comtet}, {\it Advanced Combinatorics}, {\rm \ D.~Reidel, Dordrecht, 1974.} \item[{[\FFine]}] {{N.~J.~Fine}, {\rm Binomial coefficients modulo a prime}, {\it Amer. Math. Monthly}\, {\bf 54}(1947), 589--592.} \item[{[\GGranville]}] { {A.~Granville}, {Binomial coefficients modulo prime powers}, {in preparation at %{\tt http://www.math.uga.edu:80}/\~{\tt {andrew }}} {\tt http://www.dms.umontreal.ca/}\~{\tt {andrew }}} in {\tt Binomial/index.html} or {\tt Postscript/binomial.ps}, and {\tt http://www.cecm.sfu.ca/organics/} {\tt papers/granville/paper/binomial/html/binomial.html}} %http://www.dms.umontreal.ca/~andrew/Binomial/index.html \item[{[\HW]}] {F.~T.~Howard and R.~Witt}, {\rm Lacunary sums of binomial coefficients.} {\it Applications of Fibonacci Numbers}, Vol 7: 185--195. {\rm \ Kluwer Academic Publishers, 1998.} \item[{[\IntLengyel]}] {T.~Lengyel, {\rm On the orders of lacunary binomial coefficient sums}, {\it INTEGERS, Electronic Journal of Combinatorial Number Theory}\, {\bf A3:3}(2003), 1--10.} \item[{[\LLucas]}] {%M.~ \'E.~Lucas, {\rm Sur les congruences des nombres Euleriennes et des coefficients diff\'erentiels des functions trigonom\'etrique, suivant un module premier}, {\it Bull. Soc. Math. France}\, {\bf 6}(1878), 49--54.} \item[{[\RRiordan]}] {J.~Riordan}, {\it An Introduction to Combinatorial Analysis}, {\rm Wiley, New York, 1958.} \item[{[\ZHWSun]}] {{Z.-H.}~Sun and {Z.-W.}~Sun, {Fibonacci numbers and Fermat's last theorem}, {\it Acta Arith.} {\bf 60}(1992), 371--388. } \item[{[\SSun]}] {{Z.-W.}~Sun, {On the sum $\sum_{k\equiv r \!\!\pmod m} {n \choose k}$ and related congruences}, {\it Israel J. Math.} {\bf 128}(2002), 135--156. } \item[{[\TollisenLengyel]}] {{G.~Tollisen and T.~Lengyel}, {Averaging around the circle, manuscript, 2003.}} \end{itemize} \end{document}