\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Congruence Classes of $2$-adic Valuations of \\
\vskip .1in
Stirling Numbers of the Second Kind
}
\vskip 1cm
\large
Curtis Bennett and Edward Mosteig\\
Department of Mathematics\\
Loyola Marymount University\\
Los Angeles, CA 90045\\
USA\\
\href{mailto:cbennett@lmu.edu}{\tt cbennett@lmu.edu}\\
\href{mailto:emosteig@lmu.edu}{\tt emosteig@lmu.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
We analyze congruence classes of $S(n,k)$, the Stirling numbers of the second kind, modulo powers of 2.
This analysis provides insight into a conjecture posed by Amdeberhan, Manna and Moll, which those authors established for $k$ at most 5.
We provide a framework that can be used to justify the conjecture by computational means, which we then complete for values of $k$ between 5 and 20.
\end{abstract}
\section{Introduction}
The Stirling numbers of the second kind were originally defined to aid in the computation of the sum of the $k$th powers of the first $n$ positive integers. They gained importance in mathematics as they arose in myriad contexts ranging from elementary combinatorics to topology.
For computational purposes, the Stirling numbers of the second kind can be described by the
following recurrence relation where $n \ge 0$ and $k\ge 1$:
$$
S(n+1,k) = k\cdot S(n,k) + S(n,k-1)
$$
with initial conditions
\begin{displaymath}
S(n,0) =
\begin{cases}
1, & \text{if } n=0 \text{ and } k=0; \\
0, & \text{if } n \ge 1 \text{ or } n c + {{b}}_k$, then $\nu_2 \circ {\rm St}_k$ is constant on $[n]_{2^m}$.
\item[(b)] If $m \le c + {{b}}_k$, then $\nu_2 \circ {\rm St}_k$ is constant on $[n]_{2^m}$ if and only if for all $j\in {\mathbb{N}}$ such that $1 \le j \le 2^{c+ {{b}}_k - m}$,
$$ {\rm St}_k(n+ j \cdot 2^m) \equiv 0 \pmod{2^c}$$
and $$ {\rm St}_k(n+ j \cdot 2^m) \not\equiv 0 \pmod{2^{c+1}}.$$
\end{enumerate}
\end{proposition}
\begin{proof}
For part (a), we have $m > c+ {{b}}_k$. Since $(\nu_2\circ {\rm St}_k)(r) = c$, it follows that
${\rm St}_k(r) \equiv 0 \pmod{2^c}$ but
${\rm St}_k(r) \not\equiv 0 \pmod{2^{c+1}}$.
By Proposition \ref{kwongext},
we have ${\rm St}_k([n]_{2^{c+{{b}}_k}})$ is constant modulo $2^c$.
Since $m > c+{{b}}_k$, it follows that ${\rm St}_k([n]_{2^m})$ is constant modulo $2^c$.
Since $r \in [n]_{2^m}$ and ${\rm St}_k(r) \equiv 0 \pmod{2^c}$, we have that ${\rm St}_k([n]_{2^m}) \equiv 0 \pmod{2^c}$. Thus, $\nu_2({\rm St}_k(i)) \ge c$ for all $i \in [n]_{2^m}$, and we have only left to demonstrate that $\nu_2({\rm St}_k(i)) < c+1$ for all $i \in [n]_{2^m}$.
By Proposition \ref{kwongext}, we have that ${\rm St}_k([n]_{2^{c+1 + {{b}}_k}})$ is constant modulo $2^{c+1}$. Since $m > c + {{b}}_k$, we know $m \ge c+1+{{b}}_k$, and so ${\rm St}_k([n]_{2^m})$ is constant modulo $2^{c+1}$.
Since $j \in [n]_{2^m}$ and ${\rm St}_k(j) \not\equiv 0 \pmod{2^{c+1}}$, it follows that for all $i \in[n]_{2^m}$ we have that ${\rm St}_k(i) \not\equiv 0 \pmod{2^{c+1}}$, in which case
$\nu_2({\rm St}_k(i)) < c+1$ , as desired.
For part (b), we consider the case $m \le c + {{b}}_k$. If $\nu_2 \circ {\rm St}_k$ is constant on $[n]_{2^m}$, then $\nu_2 \circ {\rm St}_k ([n]_{2^m}) = c$.
In this case, ${\rm St}_k([n]_{2^m}) \equiv 0 \pmod{2^c}$ but
${\rm St}_k(i) \not\equiv 0 \pmod{2^{c+1}}$ for all $i \in [n]_{2^m}$.
For each $j \in {\mathbb{N}}$ such that $1 \le j < 2^{c-{{b}}_k-m}$, we have $n + j \cdot 2^m \in [n]_{2^m}$, and so the conclusion follows.
Conversely, we assume that for all $j \in {\mathbb{N}}$ such that $1 \le j \le 2^{c-{{b}}_k -m}$,
\begin{equation}\label{cong0}
{\rm St}_k(n+j \cdot 2^m) \equiv 0 \pmod{2^c}
\end{equation}
and
\begin{equation}\label{notcong0}
{\rm St}_k(n+j \cdot 2^m) \not\equiv 0 \pmod{2^{c+1}}.
\end{equation}
We will show that for any $b\in[n]_{2^m}$, we have $\nu_2({\rm St}_k(b))=c$, thus demonstrating
that $\nu_2 \circ {\rm St}_k$ is constant on $[n]_{2^m}$. Since $b \in [n]_{2^m}$, we have that $b= n + i \cdot 2^m$
for some $i\in {\mathbb{N}}$. Select $j\in {\mathbb{N}}$ such that $1 \le j \le 2^{c-{{b}}_k-m}$ and $i \equiv j \pmod{2^{c-{{b}}_k -m}}$, in which case
$$b = n + i \cdot 2^m \equiv n+ j \cdot 2^m \pmod{2^{c-{{b}}_k}}.$$
Thus, by Proposition \ref{kwongext}, it follows that
$${\rm St}_k(b) \equiv {\rm St}_k(n+ j \cdot 2^m) \pmod{2^c},$$
and so by (\ref{cong0}), we have that ${\rm St}_k(b) \equiv 0 \pmod{2^c}$. Similarly, by using Proposition \ref{kwongext} in conjunction with (\ref{notcong0}), we have that ${\rm St}_k(b) \not\equiv 0 \pmod{2^{c+1}}.$ Therefore, $\nu_2({\rm St}_k(b)) = c$.
\end{proof}
Using the results from this section in conjunction with Theorem \ref{maintheorem}, we have a method of verifying the AMM conjecture for different values of $k$. In the next section, we put this method into practice.
\section{Examples}\label{examples}
In this section, we begin with $k=5$ in order to demonstrate how to reproduce the result of Amdeberhan, Manna, and Moll \cite{Am} by using the techniques developed in this paper. Next, we consider $k=6, 7, 13$ and $15$ in order to compare the behavior of $\nu_2 \circ {\rm St}_k$ for values of $k$ other than $5$. The case $k=6$ is very similar to that of $k=5$, but the scenario is more complex when $k=7$, as the behavior depends on the parity of $n$. We then close with the case $k=13$, which exhibits even more complex behaviors.
Before going into specific examples, we describe the general approach. The goal is to apply Theorem \ref{maintheorem} for a given choice of $k$, which requires establishing conditions (i) and (ii) of that theorem. That is, we need to investigate whether ${ St}_k([n]_{2^m})$ is constant modulo $2^{m-b_k+\ell_j}$ but not constant modulo $2^{m-b_k+\ell_j+1}$. Proposition \ref{kwongext} and Proposition \ref{finitecheckconstant} give us methods for checking these congruences. Unfortunately, however, each of these require certain minimal values of $m$. The significant bound is
$$
m \ge s+1=\nu_2(k!)+\ell-{{b}}_k-3,
$$
where $\ell$ must be determined to ensure that $f_k(n)\equiv 0\pmod{2^{2s+4}}$. (For small values of $m$, we will also need to check that $2^m-m\ge s+3$.) Once $\ell$ is determined, we can prove Theorem \ref{maintheorem} for all but a small number of values of $m$ using {\sl Mathematica} to perform the necessary calculations. The cases for small $m$ can then be handled by the use of Proposition \ref{algconstclass}. At this point, we have then verified Conecture \ref{mollconjecture} for the given value of $k$.
The above is essentially how our computer proof works, except that in a few cases we need a little additional information (as will be discussed in the example of $k=13$, the only value for $k \le 20$ that requires this information). It appears that the approach we use may require more computation than absolutely necessary, which we shall discuss further when we look at the case of $k=13$.
\subsection{$k=5$ and $k=6$}\label{k5}
We begin by considering the case $k=5$. We note that ${{b}}_5 = \lceil \log_2(5) \rceil -2 =1$ and $\nu_2(5!) = 3$, and so $s=3+\ell-1-3=\ell-1$. Thus $m\ge \ell$. However, if $\ell=1$ or $2$, the condition that $2^m - m \ge s+3$ is violated for small values of $m$, and so we know that we must use Proposition \ref{algconstclass} to check whether both $m=1$ and $m=2$ satisfy the conjecture. Using the proposition, we can computationally determine whether $\nu_2 \circ {\rm St}_{5}$ is constant on $[n]_{2^m}$ for a given choice of $n$ and $m$. Using the notation from Defintion \ref{Nkm}, with the aid of {\sl Mathematica}, we determine the following: ${\mathcal N}_{5,1} = \{5,6\}$, ${\mathcal N}_{5,2} = \{7,8\}$ and ${\mathcal N}_{5,3} = \{7,12\}$. For $m\ge 3$, we turn to our general argument.
By Proposition \ref{kwongext}, for $m \ge 3$,
\begin{equation}
{\rm St}_{5}([n]_{2^m}) \mbox{ is constant modulo } 2^{m-1}.
\end{equation}
If $\ell =1$, then $s= \nu_2(5!) + \ell - {{b}}_5 - 3 = 0$ and so by
Proposition \ref{finitecheckconstant}, ${\rm St}_{5}([n]_{2^m})$ is constant modulo $2^m$ whenever $m \ge 3$ if and only
$f_5(n) \not\equiv 0 \pmod{2^4}$. We will check the case $n=7$ here.
\begin{eqnarray*}
f_5(7) & = & {5\choose 1}1^7(1^{2^1}-1) + {5\choose 3}3^7(3^{2^1}-1) + {5\choose 5}5^7(5^{2^1}-1) \pmod{2^4} \\
& = & 0 + 10\cdot11\cdot 8 + 1\cdot13\cdot8 \pmod{2^4} \\
& = & 8 \pmod{2^4} \\
& \not\equiv & 0 \pmod{2^4}.
\end{eqnarray*}
{\sl Mathematica} needs only a finite check (since we are working modulo $2^4$) to show the non-congruence for all $n$. Thus, we conclude that for all $m \ge 3$,
\begin{equation}
{\rm St}_{5}([n]_{2^m}) \mbox{ is not constant modulo } 2^{m}.
\end{equation}
Now, if we select $M=3$, we see that ${\mathcal N}_{5,3} = \{7,12\}$, and if we define $\ell_7 = \ell_{12} = 3$, then parts (i) and (ii) of Theorem \ref{maintheorem} hold for all non-negative integers. (In fact, in order to apply Theorem \ref{maintheorem}, we only need these two parts to hold when $n$ is congruent to either $7$ or $12$ modulo $8$.)
Thus, we have that the AMM conjecture holds with $\mu_5 = \#{\mathcal N}_{5,3} = 2$ and $M_5 \le 3$. In fact, since we have verified the conjecture for levels $m=1$ and $m=2$, it follows that $M_5=1$.
When $k=6$, the result follows very similarly. Using Proposition \ref{algconstclass} and {\sl Mathematica}, we find that
${\mathcal N}_{6,1} = \{6,7 \}$, ${\mathcal N}_{6,2} = \{ 8,9 \}$ and ${\mathcal N}_{6,3} = \{ 12, 13 \}$.
When $k=6$, we note that ${{b}}_6 = \lceil \log_2(6) \rceil -2 =1$ and
$\nu_2(6!) = 4$. By Proposition \ref{kwongext}, for $m \ge 3$,
\begin{equation}
{\rm St}_6([n]_{2^m}) \mbox{ is constant modulo } 2^{m-1}.
\end{equation}
Using Proposition \ref{finitecheckconstant} in a manner similar to that for $k=5$, we we conclude that for all $m \ge 3$,
\begin{equation}
{\rm St}_6([n]_{2^m}) \mbox{ is not constant modulo } 2^{m}.
\end{equation}
Again, as in the case when $k=5$, an application of Theorem \ref{maintheorem} justifies that the AMM conjecture holds for $k=6$
with $\mu_6=2$ and $M_6\le 3$, and since we already determined that the conjecture holds for levels $m=1$ and $m=2$, it follows that $M_6=1$.
The calculations for $k=6$ are of roughly the same magnitude as those for $k=5$, and in both cases, they are not dissimilar from the proof for $k=5$ given by Amdeberhan, Manna, and Moll. One aspect in both of these cases is that $n\in {\mathcal N}_{k,m}$ if and only if ${\rm St}_k[k]([n]_{2^{m+{{b}}{k}}})\equiv 0 \pmod{2^m}$. That is, the converse of Proposition \ref{translateSnu} holds.
\subsection{$k=7$}\label{k7}
Although the behavior exhibited by $\nu_2 \circ {\rm St}_k$ is similar for the cases $k=5$ and $k=6$, the landscape changes when $k=7$. By Proposition \ref{kwongext}, for $m \ge 3$,
\begin{equation}\label{k=7,m-1}
{\rm St}_7([n]_{2^m}) \mbox{ is constant modulo } 2^{m-1}.
\end{equation}
Using Proposition \ref{finitecheckconstant} with $\ell = 1$ in conjunction with {\sl Mathematica}, we find that for $m \ge 3$
\begin{equation}\label{k=7,m}
{\rm St}_7([n]_{2^m}) \mbox{ is not constant modulo $2^{m}$ if and only if $n$ is odd}.
\end{equation}
In fact, since (\ref{k=7,m-1}) follows directly from (\ref{k=7,m}), we did not actually need to apply Proposition \ref{kwongext} for the case $k=7$.
Using Proposition \ref{finitecheckconstant} with $\ell = 2$, we find that for $m \ge 3$, \begin{equation}\label{k=7,m+1}
{\rm St}_7([n]_{2^m}) \mbox{ is not constant modulo } 2^{m+1} \mbox{ if and only if $n$ is odd}.
\end{equation}
Applying Proposition \ref{finitecheckconstant} with $\ell = 3$ yields the following for all non-negative integers when $m \ge 4$:
\begin{equation}\label{k=7,m+2}
{\rm St}_7([n]_{2^m}) \mbox{ is not constant modulo } 2^{m+2}.
\end{equation}
As with the cases $k=5$ and $k=6$, it is possible to determine ${\mathcal N}_{7,4}$ explicitly. However, we demonstrate that this is not necessary when justifying that the AMM conjecture holds. Fix $M=4$, and consider $j \in {\mathcal N}_{7,4}$. Whenever $j$ is odd, define $\ell_j = 1$, and whenever $j$ is even, define $\ell_j = 2$. Thus, whenever $n$ is odd, we see that (\ref{k=7,m+1}) and (\ref{k=7,m}), constitute parts (i) and (ii) of Theorem \ref{maintheorem}, respectively. In addition, whenever $n$ is even,
(\ref{k=7,m+2}) and (\ref{k=7,m+1}) constitute parts (i) and (ii) of Theorem \ref{maintheorem}, respectively.
Putting this together, we see that the AMM conjecture holds for $k=7$ with $M_7 \le 4$.
At this point, it makes sense to say a few words about the role that $\ell$ plays as well as the link between ${\rm St}_k([n]_{2^{m+{{b}}_k}})\equiv 0 \pmod{2^{m}}$ and $n\in {\mathcal N}_{k,m}$. When $\ell=1$, we have for exactly one child (say $x$) of $[n]_{2^{m+{{b}}_k}}$ that ${\rm St}_k([x]_{2^{m+{{b}}_k+1}})\equiv 0 \pmod{2^{m+1}}$ and $x\in {\mathcal N}_{k,m+1}$. However, when $\ell>1$, both children have the property of ${\rm St}_k([x]_{2^{m+{{b}}_k+1}})\equiv 0 \pmod{2^{m+1}}$, but we know that only one lies in $ {\mathcal N}_{k,m}$. The value of $\ell$ essentially tells you how many generations of children of $n$ have the property of being congruent to $0$ for the appropriate power of $2$. More precisely, when we calculate the sets ${\mathcal N}_{7,1}$, ${\mathcal N}_{7,2}$, ${\mathcal N}_{7,3}$, and ${\mathcal N}_{7,4}$, we have the following:
\begin{eqnarray*}
{\mathcal N}_{7,1} & = & \{7, 8\} \\
{\mathcal N}_{7,2} & = & \{9, 10\} \\
{\mathcal N}_{7,3} & = & \{13, 14\} \\
{\mathcal N}_{7,4} & = & \{13,14\}.
\end{eqnarray*}
While this looks similar to the cases $k=5$ and $k=6$, there is a difference in the behavior of the children regarding congruences to $0$ modulo $2^{m}$. While ${\rm St}_7(7)\equiv {\rm St}_7(8)\equiv 0 \pmod{2^0}$, we see that $7$ and $9$ behave differently from $8$ and $10$. In particular, ${\rm St}_7(8)\equiv {\rm St}_7(10)\equiv 0 \pmod{2^1}$, but ${\rm St}_7(7)=1\not\equiv 0 \pmod{2^1}$. In fact, it is more complicated when you look at $10$. In this case, both the children and the grandchildren are congruent to $0$ modulo the appropriate power of $2$. Moreover, this pattern continues, which is why we had to choose different values of $\ell$ in the cases that $n$ was even and odd. This more complex behavior is what appears to limit the proof method used by Amdeberhan, Manna, and Moll. Moreover, the case $k=7$ is only the tip of the iceberg. When $k=15$, each value of $\ell$ from $1$ to $4$ gives new congruence classes for $n$ with $f_{15}(n)\not\equiv 0 \pmod{2^{2s+4}}$. On the bright side, however, similar to the case $k=7$ where $f_3(n)\not\equiv 0 \pmod{2^{2s+4}}$ for all $n$ whenever $\ell=3$, for $k=15$ we have a similar result for $\ell=4$.
\subsection{$k=13$}
The case $k=13$ is unique in that it is not sufficient to use Proposition \ref{kwongext} in conjunction with performing calculations according to Proposition \ref{finitecheckconstant}.
According to Proposition \ref{kwongext}, for $m \gg0$, we have
\begin{equation}\label{k=13,m-2}
{\rm St}_{13}([n]_{2^m}) \mbox{ is constant modulo } 2^{m-2}.
\end{equation}
For $m \gg 0$, we can use Proposition \ref{finitecheckconstant} to determine that the following holds if and only if $n \equiv 1, 2 \pmod{4}$:
\begin{equation}\label{k=13,m-1}
{\rm St}_{13}([n]_{2^m}) \mbox{ is not constant modulo } 2^{m-1}.
\end{equation}
In addition, for $m \gg 0$, the following holds if and only if $n \equiv 0, 1, 2 \pmod{4}$:
\begin{equation}\label{k=13,m}
{\rm St}_{13}([n]_{2^m}) \mbox{ is not constant modulo } 2^{m}.
\end{equation}
However, within our ability to calculate with {\sl Mathematica} there is no non-negative integer $\ell$ such that for sufficiently large $m$ such that for all $n\ge m$, $f_{13}(n)\not\equiv 0 \pmod{2^{s+4}}$. In other words, there is no non-negative integer $L$ such that the following holds for all non-negative integers $n$:
\begin{equation}\label{k=13,m+L}
{\rm St}_{13}([n]_{2^m}) \mbox{ is not constant modulo } 2^{m+L}.
\end{equation}
This peculiarity distinguishes the case $k=13$ from all other cases when $k\le 20$. Fortunately, a finite check (using Proposition \ref{translateSnu}) verifies that
$\nu_2 \circ { St}_{13}$ is constant on the class $[n]_{2^m}$ whenever $n \equiv 3 \pmod{4}$, and so when employing Theorem \ref{maintheorem}, we only need to consider values of $n$ where $n \equiv 0,1,2 \pmod{4}$. Consequently, statements (\ref{k=13,m-2}), (\ref{k=13,m-1}) and (\ref{k=13,m}) are sufficient for the purposes of validating the AMM conjecture.
This brings up a method to increase computational efficiency, but at some cost in terms of ease of programming. Our algorithm looks for a sufficient value of $\ell$ to guarantee that $f_k(n)\not\equiv 0\pmod{2^{2s+4}}$ for all $n$, but in cases like $k=13$, where finding such an $\ell$ is beyond our computing power, the program then performs a check to see whether the values of $n$ that we cannot guarantee the non-equivalence are constant. However, we could use Proposition \ref{translateSnu} to check which $n$ we need to check for each $\ell$. While this would lead to some improvement in the number of values of $k$ that we could check, the work in calculating $f_k(n) \pmod{2^{2s+4}}$ is a limiting factor since the magnitude of $s$ is largely dictated by $\nu_2(k!)$.
The case of $k=13$ also shows another complication in that $9\in {\mathcal N}_{13,3}$, but $[9]_{2^m}$ has no non-constant children. Indeed, the number of congruence classes modulo $2^{m+{{b}}_k}$ for which Proposition \ref{translateSnu} does not rule out a non-constant class is $6$ for $m=1$, $8$ for $m=2$, $10$ for $m=3$ and $m=4$, $14$ for $m=5$, and then a constant $6$ for $m\ge 6$. The case $k=13$ is the first such case where the congruence classes with this property are not (weakly) monotone with respect to $m$, and is the only case for $k<21$.
\subsection{General $k$}
The {\sl Mathematica} code that performs the calculations yielding the proof of the conjecture for $k\le 20$ is available at {\tt http://myweb.lmu.edu/emosteig}. For these values of $k$, the largest choice of $\ell$ necessary is $4$ (in the case $k=15$). In principle this code will work for any value of $k$ for which the conjecture holds true, and while we anticipate that we could further optimize the program to produce results for larger values of $k$, it also seems with the current ideas that the best we could hope for using these algorithms would be $k\le 100$ (and in fact, $k=89$ appears to be require a very large value of $\ell$ based on the data we currently have).
\section{Further questions}
As we approached this problem, we collected a lot of data concerning which values of $n,m$ and $k$ the statement ${\rm St}_k([n]_{2^{m+{{b}}_k}}) \equiv 0 \pmod{2^m}$ holds true. As might be expected by the requirement that $f_k(n)\not\equiv 0 \pmod{2^{2s+4}}$ together with $m\ge s+1$ in the computer-generated (as well as the hand-generated) proof, we often had more data than was fully needed for the proofs. In addition, when $k$ is large, although our automated proof process is computationally infeasible due to the magnitude of $s$, we have a great deal of data that suggests many conjectures. We close by describing what appear to be the most tractable problems at this time.
The case where $k=2^t+1$ for some positive integer is extremely intriguing. The data suggests several results, which we are currently working on with a student. In particular,
we have the following conjecture.
\begin{conjecture} \label{dinnerconjecture}
The AMM conjecture holds for $k=2^t+1$ for all integers $t\ge 2$. Moreover, the following hold.
\begin{enumerate}
\item The parameter $\ell$ can be chosen equal to $1$. That is, if $s=\nu_2(k!)+1-{{b}}_k-3= \nu_2(k!)+t-3$, $m\ge s+1$, and $2^m-m\ge s+3$, then $f_k(n)\not\equiv 0\pmod{2^{2s+4}}$ for all $n$.
\item $M_k=1$.
\item $\mu_k=\#{\mathcal N}_{k,m}=2^{t-1}$ for all $m$.
\end{enumerate}
\end{conjecture}
A natural question arises about whether this work might apply to the work of Berrizbeitia {\em et. al.}
\cite{BeMe}, where the authors look at the $p$-adic valuation of $S(n,k)$ where $p$ is an odd prime. For small odd primes, similar arguments to the one in this paper should apply, given that the right analogue of Proposition~\ref{binrep} can be found. While this seems relatively easy to do in the case of $p=3$, where there will need to be two possible starting states ($t \equiv \pm1 \mod 3$), stating a similar result in a usable way for odd primes greater than $3$ might be quite difficult as there will necessarily be $p-1$ starting states to use. For example, looking at the case of $2^{5^n}$ modulo $5^{n+1}$ yields the result for $n<11$ that
$$
2^{5^n} \equiv \sum_{t=0}^n a_t 5^t \pmod {5^{n+1}},
$$
where
$$
a_0=2, a_1=1, a_2=2, a_3=1, a_4=3, a_5=4, a_6=2, a_7=3, a_8=0, a_9=3, a_{10}=2.
$$
Our choice of working modulo $5^{n+1}$ was purely arbitrary here. In the $p=2$ case, we needed $2^{n+3}$, and if we must move to a higher power of $5$ in the modulus in the proofs, this would add even more complexity, as $2^{5^n}\equiv 7^{5^n} \pmod{5^{n+1}}$, but not modulo $5^{n+2}$.
Another potential challenge in the odd prime case is that instead of looking at the difference ${\rm St}_k(n+2^m)-{\rm St}_k(n)$, we will need to show that each element of $\{{\rm St}_k(n+ a\cdot p^m)\mid a\in\{0,1,\dots, p-1\}\}$ lies in its own equivalence class modulo the appropriate power of $p$. Thus instead of looking at terms of the form $t^n(t^{2^m}-1)$, we will be looking at terms of the form $t^n(t^{p^m}-a)$, where $a=1, 2,\dots,p-1$, and we will need to show they are all non-zero. While both of these hurdles seem possible to overcome, both may require modifying our techniques significantly.
Generalizing these results to other sequences modulo $2$ may prove more tractable. The difficulty here seems to be identifying interesting such sequences. For example, the sequences $b\cdot a^n+1$ for appropriate choices of integers $a$ and $b$ seem to have similar properties to the $S(n,k)$, but for many choices of $a$ and $b$ the result appears to be uninteresting as the $2$-adic valuation is bounded. A few examples suggest that choosing $a$ and $b$ so that $b\cdot a^n+1$ is congruent to $0$ modulo $8$ may generally lead to interesting examples, but even here, we do not seem to get the full range of behaviors that make the Stirling numbers interesting.
Other interesting problems arise from the terms of $\ell$, $M_k$ and $\mu_k$. In particular, from our early data, it appears that $\mu_k$ is a non-decreasing sequence. Is this true in general? A more ambitious problem appears to be determining the behavior of $M_k$. Regarding $\ell$, we notice that the largest choices of $\ell$ needed for Lemma \ref{S2nu} occurs when $k=2^t-1$. Is there a reason for this? Is this true in general? More precisely, determining bounds for $\ell$ depending on $k$ would be extremely interesting.
\begin{thebibliography}{9}
\bibitem{Am} T. Amdeberhan, D. Manna, and V. Moll,
The 2-adic valuation of Stirling numbers,
{\em Exp. Math.} {\bf 17} (2008), 69--82.
\bibitem{BeMe} A. Berrizbeitia, L. A. Medina, A. C. Moll, V. Moll, and L. Noble, The $p$-adic valuation of Stirling numbers,
{\em Journal for Algebra and Number Theory Academia} {\bf 1} (2010), 1--30.
\bibitem{Wa}
S. De Wannemacker, On 2-adic orders of Stirling numbers of the second
kind, {\em Integers} {\bf 5} (2005).
\bibitem{Du}
D. Dummit and R. Foote, {\em Abstract Algebra}, Prentice-Hall, 1991.
\bibitem{Gr} R. Graham, D. Knuth, and O. Patashnik, {\em Concrete Mathematics,}
Addison-Wesley, 1989.
\bibitem{Kw}Y. H. H. Kwong, Minimum periods of $S(n,k)$ modulo $M$, {\em Fibonacci Quart.} {\bf 27} (1989), 217--221.
\bibitem{Le1.5} T. Lengyel, On the divisibility by 2 of the Stirling numbers of the second kind, {\em Fibonacci Quart.}, {\bf 32} (1994) 194--201.
\bibitem{Le2} T. Lengyel, On the 2-adic order of Stirling numbers of the second kind and their differences, in {\em
21st International Conference on Formal Power Series and Algebraic
Combinatorics --- FPSAC 2009},
Discrete Math. Theor. Comput. Sci. Proc., 2009, pp.\ 561--572.
\bibitem{Wo} Wolfram Research, Inc., {\sl Mathematica\/}, Version
8.0, Champaign, IL, 2010.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B73; Secondary 05A15.
\noindent \emph{Keywords: }
Stirling number, valuation, combinatorial enumeration problem.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 27 2012;
revised version received February 17 2013.
Published in {\it Journal of Integer Sequences}, March 2 2013.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}