\documentclass[12pt]{article}
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9 


%\input arstex.sty


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{amstext}
\usepackage{amssymb}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setlength{\textwidth}{6.5in}
%\setlength{\oddsidemargin}{.15in} 
%\setlength{\evensidemargin}{0in} 
%\setlength{\topmargin}{0in}
%\hsize 9in
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%\penalty 1000

%\newcounter{prcount}
%\setcounter{prcount}{0}

\parindent 10pt
%\def\indent{\parindent 20pt)
%\def\noindent{\parindent 0pt}


%\def\qued{\hfill \vrule height 8pt width6pt depth0pt}
\def\qued{\hfill $\Box$}
\def\forget#1 {}
\def\vag{\smallskip\hrule\smallskip}

\def\bull {{\item{$\bullet$}}}
\def\bull {}
\def\bullno #1 {{\item {#1}}}
\def\starr {}
\def\ra {\ $\Rightarrow$ \ }


\font\kisfont=cmr10 scaled 700


%\input refs


\def\GGranville{5}
\def\MMendelsohn{9}
\def\KW{7}
\def\HW{6}
\def\gl{4}
\def\l{8}
\def\GGessel{3}
\def\CComtet{2}
\def\RRiordan{11}
\def\TollisenLengyel{{13}}
\def\SSun{{12}}
\def\RRamus{{10}}
\def\CClark{{1}}

\def\egy{1}
\def\egypp{2}
\def\ketto{3}
\def\harom{5}
\def\negy{6}
\def\cor{4}
\def\het{7}
\def\nyolc{8}
\def\kilenc{9}

\def\dstar{dstar}
\def\dstarketto{{17}} %{dstar2}
\def\phatvany{{18}} %{phatvany}
\def\coarse{coarse}
\def\szamlaloe{{19}} %{szamlalo1}
\def\szamlalok{{20}} %{szamlalo2}
\def\rec{S-re becsles}
\def\AHSGR{A}
\def\A{B}
\def\perio{{10}}  %{periodic additivity}
\def\Gineq{{5}}  %{{G-ineq}}
\def\Sineq{{12}} %{{S-ineq}}
\def\kettompluszegy{{15}} %{{long-rec}}
\def\Ssharp{{13}} %{{S-Sharp}}
\def\sgen{{11}} %{{sgen}}


\def\binom{{1}}
\def\ASH{{2}}
\def\binomk{{3}}
\def\ae{{4}}
\def\Gp{{6}}
\def\kbhez{{7}}
\def\kbk{{8}}
\def\kbl{{9}}
\def\threestars{{14}}
\def\twostars{{16}} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document} 

\newcounter{ctr}
\setcounter{ctr}{1}

\begin{center}
{\bf ON THE ORDER OF LACUNARY SUMS OF BINOMIAL COEFFICIENTS}
\vskip 20pt
{\bf Tam\'as Lengyel\footnote{The author wishes to express his gratitude to 
the Computer and Automation Institute
 of the Hungarian Academy of Sciences for its hospitality during this work.}}\\
{\smallit Department of Mathematics, 
Occidental College, 1600 Campus Road, Los Angeles, USA}\\
{\tt lengyel@oxy.edu}
\end{center}

\vskip 30pt
\centerline{\smallit Received:  11/19/02, Accepted:  2/26/03, Published: 2/27/03 }
\vskip 30pt 

\centerline{\bf Abstract}


\noindent
In this paper we study the exact 
orders of lacunary sums of binomial coefficients.
It is remarkable that the periodic patterns evolving from powers of 2 differ markedly from those of other prime powers. For the latter ones the pattern is transparent and is determined
by the first term.
For the former ones  multisected generating functions are used to obtain 
the exact order or lower bounds on it.



\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF
 COMBINATORIAL NUMBER THEORY \smalltt 3 (2003), \#A03\hfill}

\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 30pt 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%\section{Introduction}
\section*{\normalsize 1. Introduction}
\label{}

We set the lacunary sum of binomial coefficients $$G_{n,l}(k)=\sum_{t=0}^ {\lfloor k/n\rfloor} {k\choose {l+nt}} \eqno(\binom)
$$ 
and the associated 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}}$$ \\
for any integer $n\ge 1$ and $l=0,1,\dots n-1.$ These multisected sums arise
 in combinatorics, applied probability, the analysis of algorithms, and number theoretical settings (e.g., in [\CClark], [\CComtet], [\gl], [\RRiordan], [\SSun]). 
Ramus [\RRamus] determined $G_{n,l}(k)$ as an $n$-term trigonometric sum in 1834.
Clearly, for $n=2$ we have $G_{2,0}(k)=G_{2,1}(k)=2^{k-1}, k\ge 1, $  
$g_{2,0}(x)={1-x\over {1-2x}},$ and $g_{2,1}(x)={x\over {1-2x}}.$
From now on we assume that $n>2$.


The analysis of $g_{n,l}(x)$  for a prime $n$
is similar to that of [\gl] in which alternating binomial coefficient sums are studied and sharp lower bounds are found on the orders.
In that analysis changing the value of $l$ requires only slight modifications (cf. Theorem~3 [\gl]). Our case is more complicated in this respect. Other closely related binomial coefficient sums are studied in [\l], and closed forms for $g_{n,l}(x)$ and its alternating version are derived by Howard and Witt [\HW]
for $n=3,4,5,8,$ and $10$.
The case $n=12$ appears in [\SSun] in the context of some congruences.

Section~2
%\ref{padic}
 is devoted to the analysis of divisibility by $p$ of $G_{n,l}(k)$ for any prime $n=p$ and prime power $n=p^q, p>2$. 
We deal with the case in which $n$ is a power of two in Section~3.
%\ref{2adic}.
Some related conjectures are mentioned in Section~4.
%\ref{conjectures}.

\vskip 30pt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{\normalsize 2. The case of the gap size $n=p^q, p>2$}
\label{padic}

\def\n{{p}}
\def\rr #1{\rho_\n (#1) }\def\k{j}

In this section we prove that for a prime power $n=p^q$ with $p>2$,
$\rr {G_{n,l}(k)}$ is the same as the order of the first term, i.e.,  $\rr {{k\choose l}}$. 
Therefore, the $\bmod \ {p^q}$ periodicity of the binomial coefficients guarantees  either a periodic
 increment or periodicity of $\rr {G_{n,l}(c p+k)}$ in $c$ depending on whether $k<l$ or
not. We start with  the case of $q=1$.

%\medskip\medskip
%\proclaim 
\noindent {\bf Theorem~\egy.  }
For any odd prime  $\n$ 
and $0\le l\le p-1$, we have
$\rr {G_{\n,l}(k)}=
\rr {{k\choose l}}.$


\def\5{\n}


%
\noindent {\it Proof of Theorem~1. } 
The relevant coefficients of the denominator contributing to the recursion $(1-x)^\n-x^\n$ of $g_{\n,l}(x)$ are divisible by $\n$ except those of $x^0$ and $x^\n$. Also notice that $G_{\n,l}(k)=0$ for $k=0,1,\dots,l-1$,
and
$\rr {G_{\n,l} (k)}=0$ for $k=l,l+1,\dots,\n-1$. These facts imply the cases resulting in a $p$-adic order of 0 (cf. [\l] and [\MMendelsohn]).  
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
For $m\ge 1,  
1\le l\le \n-1,  
0\le i\le l-1,
1\le c\le \n-1,  
0\le t\le c \5^{m-1}-1$, we observe that
$\rr {{{c \5^m+i} \choose {l+\5t}}}= m$ by carry counting due to Kummer
(cf. [\KW]).  
%
We will rely on the fact that this
holds for every $t$ which enters the summation in (\binom).



\def\c{d}




\indent
Now we use a theorem which was independently derived by Anton, Stickelberger, and Hensel (see identity (2) in [\GGranville])  
to determine \ ${1\over \n^q} {N\choose M} \!\!\! \pmod \n$ \
with $\n^q$ being the exact power of $\n$ dividing ${N\choose M}$. 

\def\i{j} 


\noindent {\bf Theorem~\AHSGR. }
Let $N=(N_d,\dots, N_1,N_0)_{\n}=N_0+N_1 \n+\cdots+N_d \n^d$,
$M=M_0+M_1 \n+\cdots+M_d \n^d$ and $R=N-M=R_0+R_1 \n+\cdots+R_d \n^d$ with $0\le N_i, M_i, R_i \le \n-1$ for each $i$, be the base $\n$ representations of $N, M,$ and $R=N-M,$ respectively.
Then
%
$$(-1)^q  {1\over \n^q}{N \choose M}\equiv  
\bigg({N_0!\over {M_0!R_0!}}\bigg) 
\bigg({N_1!\over {M_1!R_1!}}\bigg) \cdots
\bigg({N_d!\over {M_d!R_d!}}\bigg)\bmod \n. \eqno(\ASH)$$
%
%
We apply this with $q=\rr {{{c \5^m+i} \choose {l+\5t}}}=m$ as noted above.
To expand the right side of (\binom) by (\ASH)
for the case of the form $k=c p^m+i$, 
we group the various value ranges for $t$ according to its $\n$-ary digits
$t=(t_{m-1}, \dots, t_0)_{\n}$. With  $t_{m-1}: 0\le t_{m-1} \le c-1, \ t_\i: 0\le t_\i \le \n-1, \i=0,1, \dots m-2$, we rewrite 
%
$$\sum_{{0\le t_{m-1} \le c-1} \atop {0\le t_\i \le \5-1, \i=0,1, \dots, m-2}}
\bigg(
{{c!} \over {t_{m-1}! (c-1-t_{m-1})!}}
\bigg) 
\Bigg(\prod_{0\le \i \le m-2}\bigg(
{{0!} \over {t_\i! (\n-1-t_\i)!}}
\bigg)\Bigg)
\bigg(
{{i!} \over {l! (\5+i-l)!}}
\bigg)\equiv$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$${{c! i!}\over {l! (\5+i-l)!}} \bigg(\sum_{{0\le t_{m-1} \le c-1}
}
{1 \over {t_{m-1}! (c-1-t_{m-1})!}}\bigg)
\times
$$
$$ 
\bigg(\sum_{0\le t_0  \le p-1}
{{1} \over {t_0! (\n-1-t_0)!}}
\bigg) \cdots
\bigg(\sum_{0\le t_{m-2}  \le p-1}
{{1} \over {t_{m-2}! (\n-1-t_{m-2})!}}
\bigg) 
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bmod \n. \eqno (\binomk)$$ 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Note that \ $T_\c=\sum_{i=0}^{\c-1} {1\over {i! (\c-1-i)!}}=
{1\over {(\c-1)!}} \sum_{i=0}^{\c-1} {{\c-1} \choose i}=
{{2^{\c-1}} \over {(\c-1)!}}\not\equiv 0 \!\!\pmod \n$, for $d\le p$. We use this with $\c=c$ and $\5$. (In the latter case we obtain $T_\n\equiv -1 \!\!\!\pmod n$ by Euler's and Wilson's Theorems.) This guarantees that the expression in (\binomk) is not a multiple of $\n$. 
%%%%%%%%%%%%%%%%%%
In fact, we get that 
$$G_{p,l}(cp^m+i)\equiv -c 2^{c-1}  i! a_{i,l}  p^q \ \bmod {p^{q+1}}$$ 
with $a_{i,l}\equiv\big(l! (p+i-l)!\big)^{p-2} \bmod p$ being the $\bmod \ p$ multiplicative inverse of $l! (p+i-l)!$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


In general, if $k\ge p, i\equiv k \!\!\! \pmod p,  0\le i\le l-1$,  and  $\rr {k-i} =m 
$  then the proof can be easily modified by using 
$T_d\not\equiv 0 \!\!\! \pmod p$ \ with $d 
\equiv {{k-i}\over p^m} \!\!\! \pmod p$ \ so that $0<d 
<p$, and with $d=p$, 
%%%%%%%%%%%%%%%%%%%
to yield $\rr {G_{p,l}(k)} = \rr {{k\choose l}}=m$. Note, however, that if $k-i>p^{m+1}$ then some terms ${k \choose {l+pt}}$ will be divisible by $p^{m+1}.$ 


The case of $k\ge p, i\equiv k \!\!\! \pmod p,  l\le i\le p-1$, is taken care of by the observation for cases resulting in a $p$-adic order of 0 made at
 the beginning of the proof. \qued

We can generalize Theorem~\egy\ for prime powers.
%\medskip



\noindent{\bf Theorem~\egypp. } 
For any prime power $n=\n^q, 0\le l\le n-1$, we have  
$\rr {G_{n,l}(k)}=\rr {{k\choose l}}
$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



The proof is similar to that of the Theorem~\egy\ and is based on the fact 
that the coefficients of $(1-x)^n-x^n$ are divisible by $\n$ except those of $x^0$ and $x^n$.  

\vskip 30pt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%\newpage
%\section{Gap size of $2^m$}
\section*{\normalsize 3. Gap size of $2^m$}
\label{2adic}


\def\r #1 {\rho_2\big(#1\big)}

This case is quite involved. In fact,
first we prove a theorem for alternating sums. 
Later we discuss the divisibility behavior for  the non-alternating 
sum $G_{2^m,0}(k) $ by applying multisection techniques to its generating function. Recall that we are interested only in cases with $m\ge 2$.%\\

We note that Gessel [\GGessel] studies generalized Dedekind sums, 
including $ \sum_{j=0}^{2^m-1} (1+\omega^j)^k$ with $\omega =$ $\cos{(2\pi/2^m)}+i\sin{(2\pi/2^m)}$ being a  primitive $2^m$th root of unity. Of course, the above sum is ${2^m} G_{2^m,0}(k)$  in disguise (cf. [\CComtet], [\RRamus], or [\RRiordan]) but the analysis in [\GGessel] does not seem to help in determining the 
%
$2$-adic order of $G_{2^m,0}(k).$
%
In [\TollisenLengyel] we proved 

\def\i{k}

\noindent {\bf Theorem~\A.}
For $\i\ge 2$, we have $$\r {G_{4,0}(\i)} =\cases {\lfloor {\i/2} \rfloor-1, &if $\i\equiv 0,1,3 \bmod 4$\cr \i-2, &if $\i\equiv 2 \bmod 4$\cr}\eqno(\ae)
$$
and $$\r {G_{4,l}(2\i+1)} =\i-1, l=0,1,2,3, \i\ge 1.
$$

%\medskip\medskip

We generalize this theorem. The main results of this section are
summarized in the following theorem.

%\medskip\medskip

\def\k{c}

\noindent {\bf Theorem~\ketto. } For $k,c\ge 1$, we have
$$\r {G_{2^m,0}(k)} \ge \lceil {k\over 2^{m-1}} \rceil -2, \eqno(\Gineq)
$$
$$\r {G_{2^m,0}((2c-1)2^{m-1})} =4c-4,\eqno(\Gp)$$
$$\r {G_{2^m,0}(c 2^{m})} =2c-1,\eqno(\kbhez)$$
and
$$\r {G_{2^m,2^{m-1}}(c 2^{m})} =2c-1.\eqno(\kbk)$$
%
For $l=0,1,\dots,2^m-1, \k\ge 2,$ we have 
$$\r {G_{2^m,l}(\k 2^{m-1}-1)} = \k-2.\eqno(\kbl)$$


\def\m{m}


%\medskip
\noindent {\bf Corollary~\cor. }
If inequality (\Gineq) holds with equality for some value $k$ then 
$$\r {G_{2^m,0}(k+2^{2(m-1)})} =\r {G_{2^m,0}(k)} +2^{m-1}. \eqno(\perio)$$ 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Note that (\Gineq) is sharpened by (\kbhez), and (\perio) also holds for even multiples of $2^{m-1}$ while (\Gp) shows that for odd multiples the growth rate is doubled. 
The corollary and identity (\Gp) reveal the differences in the periodic nature of $\r {G_{2^m,0}(k)}$ .  We note that $\r {G_{2^m,0}(k)} \ge \lfloor {k/{2^{m-1}}} \rfloor -1$ also holds true in agreement with (\ae) but we prefer to use (\Gineq).


 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In order to prove Theorem~\ketto,  we set $$S_{2^m}(k)=\sum_{t} {k\choose {2^mt}}(-1)^t,
$$
for the lacunary alternating binomial coefficient sum with generating function
$$\sum_{k=0}^\infty S_{2^\m}(k) x^k={{(1-x)^{2^\m-1}}\over {(1-x)^{2^\m}+x^{2^\m}}},
\eqno(\sgen)$$
 and prove 

%\medskip
%%%%%%%%%%%%%%%%%%%%
%\medskip
\noindent{\bf Theorem~\harom. } For $k, c\ge 1,$ we have
$$\r {S_{2^m}(k)} \ge {{k}\over {2^m}}-1,\eqno(\Sineq)$$
$$\r {S_{2^m}(k)} = {{k}\over {2^m}} \hbox { if } 2^{m+1}|k, \quad \hbox{ i.e., } \quad
 \r {S_{2^m}(c 2^{m+1})} = {2c},\eqno (\Ssharp)$$
and $$\r {S_{2^m}((2c-1)2^m)} = \infty.$$




%\medskip
\noindent {\it Proof of Theorem~\harom. } 
%\medskip
We note that  
%
$$S_{2^m}((2c-1)2^m)=0,\eqno(\threestars)$$ 
%
for ${{(2c-1)2^m} \choose {2^mt}}(-1)^t+{{(2c-1)2^m} \choose {(2c-1)2^m-2^mt}}(-1)^{(2c-1)-t}=0, \ 0\le t \le c-1,$
%
which yields the last part of the theorem.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent We prove the other statements by induction on $k$. 
We will need the first $2^{m+1}$ values of $S_{2^m}(l)$ as starting values for the order $2^{m+1}$ linear recurrence (\kettompluszegy) below.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
The values are obvious for $k: 1\le k\le 2^m.$ 
For $0<i<2^m$, $S_{2^m}(2^{m+1}-i)={{2^{m+1}-i}\choose 0}-{{2^{m+1}-i}\choose {2^m}}$ is even confirming $\r {S_{2^m}(2^{m+1}-i)} \ge 1-{i\over {2^m}}={{2^{m+1}-i}\over {2^m}}-1.$ 
By Theorem~1 in [\GGranville], which is an extension of identity (\ASH), we have that for $m\ge 1: $
$\r {S_{2^m}(2^{m+1})} = 2$. In fact,  
$${1\over 2} {2^{m+1}\choose {2^m}}
\equiv 3  \bmod {2^3}$$
which yields $S_{2^m}(2^{m+1})
\equiv 1-6+1 \!\!\!\pmod 8.$\footnote{Note that  in general, for every $N\ge 1$ there exists an $m_0=m_0(N)$ so that for all $m\ge m_0: $ ${1\over 2} {2^{m+1}\choose 2^m} \pmod {2^N}$ is the same.} 

%\medskip
Now we prove the inductive statements.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
Identity (\sgen) suggests a recurrence of order $2^m$. For $k>2^m$,
%
%
$$S_{2^m}(k+2^m)=\bigg(\sum_{i=1}^{2^m-1} (-1)^{i+1} {{2^m}\choose i} S_{2^m}(k+2^m-i)\bigg)-2S_{2^m}(k).$$
%
%
This implies (\Sineq). In fact, for $1\le i\le 2^m-1$ we have
$\rho_2 \big({{2^m}\choose i} S_{2^m} (k+2^m-i)\big)\ge m-\r {i} +{{k+2^m-i}\over {2^m}}-1\ge {k\over 2^m}+{1\over 2},$ with the unique minimum taken at $i=2^{m-1}$, and $\r {2S_{2^m}(k)} \ge 1+ {k\over 2^m}-1={k\over 2^m}.$

To prove (\Ssharp) we multiply both the numerator and denominator in (\sgen) by $(1-x)^{2^m}+x^{2^m}$. This results in the order $2^{m+1}$ recurrence
$$S_{2^m}(k+2^{m+1})=\bigg(\sum_{i=1}^{2^{m+1}-1} c_i  S_{2^m}(k+2^{m+1}-i)\bigg)-4S_{2^m}(k),\eqno(\kettompluszegy)$$
%
%
for $k>2^{m+1}$. It is fairly easy to see that 
$\r {c_i} \ge 3$ except for $\r {c_{2^{m-2}}} =2$. Provided that $2^{m+1}|k$, we get
%
that
%
$\rho_2 \big(c_i S_{2^m} (k+2^{m+1}-i)\big)\ge 3 +{{k+2^{m+1}-i}\over {2^m}}-1 > 2+{k\over  2^m}$ 
except for $i=2^{m-2}$ when the lower bound still exceeds $2+{k\over 2^m}$
%
and for the last term whose contribution is only $\r {4S_{2^{m}}(k)} =2+ {k\over 2^m}.$
\qued

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\p{{2^m}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%
\def\m{q}
%

Now we turn back to the original problem
and first prove
%\\
%\medskip


\noindent{\bf Lemma~\negy. }
%
$$G_{2^m,0}(k)={{2^k}\over {2^m}}+{1\over {2^m}} \sum_{q=1}^{m-1} 2^q S_{2^q}(k).\eqno(\twostars)$$
%\\
%
%\medskip

\noindent {\it Proof of Lemma~\negy.} 
We use  the corresponding generating functions of $G_{2^m}(k)$ and $S_{2^q}(k), 0<q\le m.$
Note that $S_{2^m}(0)=1.$ For $m\ge 1$, we set $A_{m}(x)= {1\over 2^{m-1}} {{1-x}\over {1-2x}}+ \sum_{q=1}^{m-1} {{(1-x)^{2^q-1}}\over {(1-x)^{2^q}+x^{2^q}}} {{2^q}\over {2^m}},$
and observe that $A_{m+1}(x)={1\over 2} A_{m}(x)+{1\over 2} {{(1-x)^{2^m-1}}\over {(1-x)^{2^m}+x^{2^m}}}. $ Now identity (\twostars) follows by a simple inductive proof that
$A_m(x)=g_{2^m,0}(x)$ for $m\ge 1$. \qued

We are ready to proceed with the

\noindent {\it Proof of Theorem~\ketto. }
If $k< 2^m$ then $G_{2^m,0}(k)=1$ holds in accordance with the assertions.
Otherwise, we can rely on the summation in (\twostars) to estimate or determine $\r {G_{2^m,0}(k)}$ .

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

First we prove (\Gineq)
without the ``ceiling" function, i.e., in the form $\r {G_{2^m,0}(k)} \ge {k\over 2^{m-1}}-2$.
%%%%%%%%%%%%%%%%%%%%%%%%%
For $k\ge 2^m$, we observe that the terms of (\twostars) are divisible by various powers of 2. The exponent of the term with index $q$ is at least $q-m+{k\over {2^q}}-1 $ whose unique minimum is ${k\over 2^{m-1}}-2$ taken at $q=m-1$, proving (\Gineq).

For the proof of (\Gp) 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
with  $k=(2c-1)2^{m-1}$, 
we need only consider the term with index $q=m-2 $ \
in (\twostars). 
%%%%%%%%%%%%%
 (In fact the last term, with index $q=m-1$, is 0 by (\threestars).)
To see this we observe that for $k>2^{m+1}$  and $q\le m-1$:
$1<{k\over 2^{m+1}}<{k\over 2^m}\le {k\over 2^{q+1}}. $
This means that if $2^{m-1}|k$ then for the 2-adic order of the terms with indices $q$ and $q+1$ we have $q-m+{k\over 2^q}>q+1-m+{k\over 2^{q+1}} $ by (\Ssharp). 
%%%%%%%%%%
In other words, the terms on the right side of identity (\twostars) contribute smaller and smaller exponents of 2 as $q$ increases. 
%%%%%%%%%%
(For example, to get $\r {G_{16}(24)} =4$ we need only $\r {{2^{m-2}\over 2^m} S_{2^{m-2} }(24) } =2-4+{24\over 4}=4$ since $m=4$ and $8|24.$) 
%%%%%%%%%%%%%%%%%%%
We immediately obtain $\r {G_{2^m,0}((2c-1) 2^{m-1})} =m-2-m+\r{S_{2^{m-2}}((2c-1) 2^{m-1})} =4c-4.$
%
A similar analysis yields (\kbhez), for   only the last term matters in (\twostars) 
if $k=c 2^m$. This leads to the $2$-adic order  $(m-1)-m+k/2^{m-1}=2c-1$ by identity (\Ssharp). 


Now we turn to (\kbl). {}
Since by binomial identities $G_{2^m,0}(c 2^{m}-1)=G_{2^m,2^m-1}(c 2^{m}-1), $
and their sum is $G_{2^m,0}(c 2^{m})$, it follows from identity (\kbhez) that $\r {G_{2^m,l}(c 2^{m}-1)} = 2c-2,$ if  $ l=0$ or $ 2^m-1.$ This works for all cases if $m=2$ (see [\TollisenLengyel]) but does not seem to work for other values of $l$ if $m>2$ so we opt for a different approach below.
%
On the other hand, identity (\kbk) can be derived from (\kbl) since $G_{2^m,2^{m-1}-1}(c2^m-1)=G_{2^m,2^{m-1}}(c2^m-1)$, and their sum is $G_{2^m,2^{m-1}}(c2^m).$


It turns out that (\kbl) requires $2^{m-1}$-section of $g_{2^m,l}(x).$ 
It can be derived by multiplying (cf. [\gl], [\l]) both the numerator and denominator of 
$g_{2^m,l}(x)$ by $\prod_{j=1}^{2^{m-1}-1} D(\omega^j x)$ with $D(x)=(1-x)^{2^m}-x^{2^m}=
\sum_{j=0}^{\p-1} {\p\choose j} (-1)^j x^j$ with $\omega$ being a $2^{m-1}$th primitive root of unity. We expand the new denominator $D^{*}(x)$ symbolically:

\def\c{C}


$$D^{*}(x)=\prod_{j=0}^{2^{m-1}-1} D(\omega^jx) 
=1-c_{2^{m-1}} x^{2^{m-1}}-\cdots-c_{{(2^m-1)2^{m-1}}} x^{({2^m-1}) 2^{m-1}}\eqno(\dstarketto)$$ 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
which is a polynomial in $x^{2^{m-1}}$ since $D^{*}(\omega^j x)=D^{*}(x), 0\le j< 2^{m-1}$.
%
%
%\\ \medskip
%
%
%
Any combination of $2^{m-1}$ factors contributing $x^{k{2^{m-1}}}$ to the expansion can be characterized by the number, $i_j$, of polynomial factors in which the term with $x^{j}$ is selected. By binomial expansion and ignoring the factors of $\omega$, the contribution of any term with the characterization $(i_0, i_1, \dots, i_{\p-1})$ is a multiple of
$$
{\p\choose 0}^{i_0} {\p\choose 1}^{i_1} \cdots {\p\choose \p-1}^{i_{\p-1}}. \eqno(\phatvany)
$$
%
We determine the exponent in the power of $2$ which divides this quantity in
terms of $(i_0, i_1, \dots, i_{\p-1})$.
%%%%%%%%%%
Here we need a finer analysis than that of Lemmas~1 and 2 of [\l]  which is accomplished by
the following two lemmas.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\noindent{\bf Lemma~\het. } We have $\r {c_{k 2^{m-1}}} \ge k$, for  $k: 
1\le k \le 2^m-1$. Equality holds if and only if $k=2^{m-1}.$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\j {{c}}




\noindent{\bf Lemma~\nyolc. } With $y_c=G_{2^m,l}(c 2^{m-1}-1)$ 
we have $\r {y_\j} =\j-2$, for $\j=2, \dots, 2^m.$ 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We get the recurrence 
$y_{\j+1}=\sum_{k=1}^{2^{m}-1} c_{k 2^{m-1}} y_{\j+1-k}$ by (\dstarketto).
It follows that 
$$\r {c_{k 2^{m-1}} y_{\j+1-k
}} \ge k+(\j+1-k-2)=\j-1$$
by Lemmas~\het\ and \nyolc, 
%%%%%%%%%%%%%%%%%%%%%%
 with equality holding for the index $k=2^{m-1}$ only. This guarantees the statement of
identity (\kbl), 
$\r {y_{\j+1}} =\j-1$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Hence, the proof of Theorem~\ketto\ is now complete.
\qued


\noindent {\it Proof of Lemma~\het. } Indeed, in (\phatvany) for the terms contributing to $x^{k 2^{m-1}}$ 
we get that 
$i_0+i_{1}+\cdots+i_{2^m-1}=2^{m-1}$ and
$0 i_0+1 i_{1}+\cdots+(2^m-1)  
i_{2^m-1}=k 2^{m-1}$
since each of the $2^{m-1}$
factors has exactly one contributing
term.
%%%%%%%%%%%%%%
With $\c=i_{2^{m-1}}$,
we have that $k 2^{m-1}$ is $\c 2^{m-1}$ plus the other at most
$2^{m-1}-\c$ terms  $ji_j, j\not=2^{m-1}.$
%
% 
Thus, $(k-\c)2^{m-1}
\le (2^{m-1}-\c) (2^m-1)$. This yields that
$k\le {{2^{m-1}-\c}\over 2^{m-1}}(2^m-1)+\c\le 2^m-1-\c + {\c\over 2^{m-1}}$ leading to 
$k\le 2^m-\c$ since $\c\le 2^{m-1}$
and equality holding if and only if $\c=k=2^{m-1}.$ In order to determine 
$\r {c_{k 2^{m-1}}}$  
%
we count the contribution of the corresponding factors in (\phatvany) to the exponent of 2
%%%%%%%%%%%
and get that $\r {c_{k 2^{m-1}}} \ge 1\cdot 
\c
+2\cdot (2^{m-1}-
\c
)=2^m-
\c \ge 
k$. Equality holds in
$\r {c_{k2^{m-1}}} =k$ if and only if $k=\c=2^{m-1}.$
{For example, for  $m=3$, we get $\r {c_{4k}} \ge k$ and equality holds if and only if  $k=0$ or $k=\c=4$; in fact, we have that the exponents are $0,3,3,6,4,7,8,12$, in the order
of $k=0,1,2,3,4,5,6,7$.
}
\qued

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\it Proof of Lemma~\nyolc. } 
We apply  an argument similar to that used for proving Lemma~2 of [\l].  
%
Recall that by the $2^{m-1}$-section used in (\dstarketto), $g_{2^m,l}(x)$
can be written with numerator
$x^l (1-x)^{2^m-l-1} {{D^{*}(x)}\over {D(x)}}
$ and denominator $D^{*}(x)$.
(In the above proof we have just discussed the divisibility properties of the coefficients of the latter.) Let us focus now on the numerator. To get the coefficient of $x^{c 2^{m-1}-1},$ i.e., $y_c, c\ge 2,$ we take $$[x^u] x^l (1-x)^{2^{m}-l-1}=\cases{
{{2^m-l-1}\choose {u-l}}(-1)^{u-l}, &if $u: l\le u<2^m$,\cr 0, &if $u: 0\le u<l$,\cr}\eqno(\szamlaloe)$$ 
and 
$$[x^{c2^{m-1}
-1-u}] D^{*}(x)/D(x)\eqno(\szamlalok)$$ with $0\le u < 2^m$ and the usual notation.
%%%%%%%%
We will see shortly that the only interesting cases are $u=i 2^{m-1}-1, i=1,2$.
Note that the right hand side of (\szamlaloe) 
is $\pm1$ 
if $i=2$.%\\

We observe that $\r {{{2^m}\choose j}} , 1\le j\le 2^m-1, $ is smallest for $j=2^{m-1}.$
So to keep the 2-adic order small in (\phatvany) we try to maximize $i_0$ and then $\c=i_{2^{m-1}}$. We now prove that $\c$ is either $c-1$ or $c-2$. In fact, as we dropped $D(x)$ from (\dstarketto), $\sum_{j=0}^{2^m-1} i_j=2^{m-1}-1$ and  $\sum_{j=0}^{2^m-1}j i_j=c 2^{m-1}-1-u \ge \c 2^{m-1}$ yield $(c-\c) 2^{m-1}\ge u+1$.
To avoid adding extra factors of 2 in (\phatvany), we take $i_0=2^{m-1}-1-\c$ 
implying $u=(c-\c)2^{m-1}-1.$
%
Note that $1\le 1+u\le 2^m;$ therefore, 
$\c+1 \le c\le \c+2$.

If $\c=c-1$ then the contribution is $2^{c-1}$ from (\szamlalok),
while if $\c=c-2$ then the contribution is $2^{c-2}$ since in this case $u=2^m-1$
and there is no contribution from (\szamlaloe). 
This gives 
$\r {y_c} =c-2$ for $c\ge 2.$ \qued




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\noindent {\bf Remark. } We note that identity (\twostars) can be generalized. Let $q'$ be the smallest integer $q$ so that $2^q>l$. 
We set $S_{2^m,l}(k)=
\sum_{t} {k\choose {l+2^mt}}(-1)^t, 0\le l<2^m,$ and prove that
$$G_{2^m,l}(k)={1\over 2^{m-q'}} G_{2^{q'},l}(k) +{1\over 2^m}\sum_{q=q'}^{m-1}
2^q S_{2^q,l}(k).
$$
In fact, for $m\ge q'$ we set $A_{m,l}(x)={1\over {2^{m-q'}}}{x^l(1-x)^{2^{q'}-l-1} \over 
{(1-x)^{2^{q'}}-x^{2^{q'}}}}+\sum_{q=q'}^{m-1}
{x^l (1-x)^{2^q-l-1} \over {(1-x)^{2^q}+x^{2^q}}} {2^q\over 2^m}
$ 
and observe that $A_{m+1,l}(x)={1\over 2} A_{m,l}(x)+{1\over 2} {x^l(1-x)^{2^m-l-1} \over {(1-x)^{2^m}+x^{2^m}}} $  and $A_{m,l}(x)=g_{2^m,l}(x)$ by induction on $m$.
%
The previous proof  with $l=0$ suggests that it might be possible to utilize the above identity and information 
on $\r {S_{2^m,l}(k)} $ to obtain lower bounds on $\r {G_{2^m,l}(k)}  $ or even its value. 
Numerical evidence, however, suggests that 
this job might be more complicated.
%%%%%%%% 

Identity (\kbhez) is generalized by

\noindent
{\bf Theorem~\kilenc. } {For $c\ge 1$ and $0\le l\le 2^{m-1}-1$, we have $\r {G_{2^m,l}(c2^m+l)} = \r {G_{2^m,0}(c2^m)} =2c-1.$}

The proof parallels that of identity (\kbl) and is based on the $2^m$-section of $g_{2^m,l}(x)$ and lemmas similar to Lemmas~\het\ and \nyolc. The details are left to the reader. If 
$l\equiv 2^{m-1} \!\!\!\pmod {2^m}$ then numerical evidence suggests that the pattern apparently changes to $\r {G_{2^m,2^{m-1}}((2c-1)2^{m-1})} =4c-4.$
Similarly,   
$\r {G_{2^m,0}(k)} = \r {G_{2^m,2^{m-1}} (k)} $ seems to be true, in agreement with (\kbhez) and (\kbk), if $k$ is sufficiently large.

Finally we present the

\noindent {\it Proof of Corollary~\cor. } The  proof is based on 
the combination of (\Gineq)
and Lemma~\het. 
We have $G_{2^m,0}(k+2^{2(m-1)})=c_{2^{m-1}} G_{2^m,0}(k+2^{2(m-1)}-2^{m-1})+
c_{2^{m}} G_{2^m,0}(k+2^{2(m-1)}-2^m)+\dots+
c_{2^{2(m-1)}} G_{2^m,0}(k
)+\dots+
c_{(2^m-1)2^{m-1}} G_{2^m,0}(k+2^{2(m-1)}-(2^m-1)2^{m-1})$
by (\dstarketto).
Taking the 2-adic orders we get that
$\r {G_{2^m,0}(k+2^{2(m-1)})} $ is at least as large as $j+1+\lceil {{k+2^{2(m-1)}-j 2^{m-1}}\over {2^{m-1}}}\rceil -2$, $1\le j\le 2^m-1$, except for $j=2^{m-1}$ where the unique minimum 
is taken
by Lemma~\het, (\Gineq) and the assumption on $k$. 
In fact,  the minimum is $2^{m-1}+\r {G_{2^m,0}(k)} = 2^{m-1}+\lceil {k\over 2^{m-1}}\rceil -2$ guaranteeing that equality in (\Gineq) will also hold for $k+2^{2(m-1)}$. 
%%%%%%%%%%%%%%%
\qued 

\vskip 30pt

%\section{%Conclusions and 
%Related questions}
\section*{\normalsize 4. Related questions}
\label{conjectures}

We propose three conjectures. Numerical evidence suggests 

\noindent {\bf Conjecture~1. }
Assertion (\Gineq) holds with equality with $2^{m-2}$ exceptions at and immediately following odd multiples of $2^{m-1}$. (Even multiples of $2^{m-1}$ are taken care of by (\kbhez).)

This means that (\Gineq) gives the exact order
in about 75\% of the cases.
%
%
It seems interesting to investigate the periodic increment of $\r {G_{2^m,0}(k)} $ 
similar to (\perio) but for all $k\not\equiv 2^{m-1} \!\!\! \pmod {2^m}$. 
%
We believe that this ``limited scope"
period is $2^m$ rather than
$2^{2(m-1)}$. 

\def\ggg (#1){\r {G_{2^m,0}(#1)} }

\noindent {\bf Conjecture~2. } $\ggg (k+c 2^m) = \ggg (k) +2c$, for all sufficiently large $k$  with $k\not\equiv 2^{m-1} \!\!\! \pmod {2^m}.$ %\\

For example, if $m=2$ then $\r {G_{4,0}(k+4c)} = \r {G_{4,0}(k)} +2c$, for $ k\ge 3
$ and  $k\not\equiv 2 \pmod 4.$ 
%
%
%
{For $l>0$, $\r {G_{2^m,l}(k)} $ 
seems to have a larger set of positions excluded from the period. Typically, $k\equiv 0,1,
\dots, l-1 \!\! \pmod {2^m}$ are all excluded.} We also propose 

\noindent {\bf Conjecture~3. } $\r {G_{2^{m+s},0}(2^sk)} =\r {G_{2^m,0} (k)} $
for $s\ge 1$.

This evidently holds if $2^{m-1}|k$ by (\Gp) and (\kbhez), or if 
$k\le 2^m.$ This latter observation proves that Conjecture~3 follows from Conjecture~2 by induction on $k$.
In fact,  repeated use of Conjecture~2 implies that if
$\r {G_{2^{m+1},0}(2k)} =\ggg (k)$ then
$$\ggg (k+c2^{m})=\ggg (k) + 2c= \r {G_{2^{m+1},0} (2k)} +2c =
\r {G_{2^{m+1},0} (2k+c 2^{m+1})} .$$

%\medskip\medskip\medskip\medskip

\section*{\normalsize Acknowledgments}
I wish to thank Greg Tollisen for making many helpful suggestions and comments that improved the presentation of this paper.


%\noindent
%{\bf References}
\section*{\normalsize References}

\begin{itemize}

\item[{[\CClark]}] {{D.~S.~Clark}, 
{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[{[\GGessel]}] {I.~M.~Gessel, Generating functions and generalized Dedekind Sums, {
The Wilf Festschrift}, {\it Electronic Journal of Combinatorics} {\bf 4}(1997), \#R11}

\item[{[\gl]}] {I.~M.~Gessel and T.~Lengyel, {On the order of Stirling numbers and alternating binomial coefficient
sums}, {\it The Fibonacci Quarterly}\,  {\bf 39}(2001),  444--454.}

\item[{[\GGranville]}] {{A.}~{Granville},
{Binomial coefficients modulo prime powers}, {in preparation at  http:
\\ //www.math.uga.edu:80}/$\sim$ {{andrew }
 in Binomial/index.html or\\ Postscript/binomial.ps}}

\item[{[\HW]}] {{F.~T.~Howard} and R.~Witt},  {%\it 
Lacunary sums of binomial coefficients.} 
{\it Applications of Fibonacci Numbers}, Vol 7: 185--195. {\rm \ Kluwer Academic Publishers,
1998.} 

\item[{[\KW]}] {{D.~E.~Knuth and H.~S.~Wilf},  {%\it 
The power of a prime that divides a
generalized binomial coefficient.} {\it J. Reine Angew. Math.}\, {\bf 396}(1989),
212--219.}

\item[{[\l]}] {T.~Lengyel, {%\it 
Difference equations and divisibility properties of 
sequences}, {\it Journal of Difference Equations and Applications}\,
 {\bf 8}(2002), 741--753.}

\item[{[\MMendelsohn]}] {{N.~S.}~Mendelsohn, {Congruence
relationships for integral recurrences}, 
{\it Can. Math. Bull.}\, {\bf 5}(1962),
281--284.}

\item[{[\RRamus]}] {{Chr.~Ramus}, 
{Solution g\'{e}n\'{e}rale d'un probl\`{e}me d'analyse combinatoire}, {\it J. Reine Angew.
Math.}\, {\bf 11}(1834), 353-355.}

\item[{[\RRiordan]}] {J.~Riordan}, 
{\it An Introduction to Combinatorial Analysis},
{\rm Wiley, New York, 1958}

\item[{[\SSun]}] {{Z.-W.}~Sun, 
{On the sum $\sum_{k\equiv r \bmod m} {n \choose k}$ and related congruences}, {\it Israel
J. Math.} {\bf 128}(2002), 135--156. }

\item[{[\TollisenLengyel]}] {{G.~P.}~Tollisen and T.~Lengyel, 
{Averaging around the circle, manuscript, 2002.}}

\end{itemize}



\end{document}