Congruence Classes of 2-adic Valuations of Stirling Numbers of the Second Kind

Curtis Bennett and Edward Mosteig Department of Mathematics Loyola Marymount University Los Angeles, CA 90045 USA

                       cbennett@lmu.edu
                       emosteig@lmu.edu

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.

1 Introduction

The Stirling numbers of the second kind were originally defined to aid in the computation of the sum of the kth 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 ≥ 0 and k ≥ 1:

S(n + 1, k) = k · S(n, k) + S(n, k − 1)

with initial conditions

S(n, 0) = \begin{cases}1, & if n = 0 and k = 0; \\ 0, & if n ≥ 1 or n < k. \end{cases}

Much like the binomial coefficients, this recurrence leads to interesting divisibility properties. Indeed, if one codes the odd Stirling numbers with a black box and the even numbers

Figure 1: The parity of S(n, k).

with a white box, we obtain a Sierpinski-like triangle (see Figure 1). Here the top row corresponds to n = 0.

More recently, a deeper study of the behavior of the Stirling numbers with respect to primes has taken place. Kwong [6] shows that for any prime p and fixed k, the sequence {S(n, k)}_{n=1}^{∞} is periodic modulo p once n is sufficiently large. Lengyel [7] then formulates (and proves several special cases of) the conjecture that the 2-adic valuation of the Stirling number S(2^{n}, k) is one less than the number of occurrences of the digit 1 in the binary expansion of k. Later in 2005, De Wannemaker [3] proves this result in general.

Amdeberhan, Manna, and Moll [1] make a general study of the 2-adic valuation of the Stirling numbers S(n, k), noting that for fixed k, the sequence of 2-adic valuations of S(n, k) appears to satisfy interesting fractal-like properties. Their paper proves a special result for the case k ≤ 5, and then makes a general conjecture (which we call AMM) about the 2-adic valuations of these sequences in general. The proof provided by Amdeberhan, Manna, and Moll [1] of the case k = 5 appears complicated, and while one might see a way to generalize this proof for the case k = 6, it appears that larger values of k would not fall easily to similar arguments.

The goal of the present paper is to provide a general technique for proving the AMM conjecture (see Section 2 for details) for fixed k, and to provide a deterministic method for carrying out this technique. This method allows us to prove the AMM conjecture for all k ≤ 20 on our desktop computer. Further, we believe that optimizing our code would allow us to obtain results for larger values of k; however, there are significant limitations since the complexity of our algorithms is exponential. This method further allows us to expose some of the difficulties in the general case by contrasting the behaviors of sequences of the form {S(n, k)} for different values of k.

2 Background

Given k, n ∈ ℕ such that n ≥ k, the Stirling number of the second kind, S(n, k), can be defined combinatorially as the number of ways to partition a set of n elements into k nonempty subsets. Throughout this paper, we fix k and anaylze the behavior of S(n, k) for different values of n. To this end, we define the function St_{k} : {k, k + 1, k + 2, … } → ℕ by

St_{k}(n) := S(n, k).

A classical formula for Stirling numbers of the second kind [5] is given by

St_{k}(n) = \frac{1}{k!} ∑_{t=0}^{k−1} \binom{k}{t}(k − t)^{n}(−1)^{t},  (1)

which can be rewritten as

k!St_{k}(n) = (−1)^{k} ∑_{t=1}^{k}(−1)^{t}\binom{k}{t}t^{n}.  (2)

Our primary objective is to examine the powers of 2 that divide St_{k}(n) for a fixed value of k. With this in mind, we define the 2-adic valuation as the function ν_{2} : ℤ^{+} → ℕ given by

ν_{2}(z) = max{i ∈ ℕ : 2^{i} | z}.

In the future, we will compute 2-adic valuations of Stirling numbers indexed according to congruence classes modulo powers of 2.

For n, t ∈ ℕ, we define the congruence class

[n]_{t} = {j ∈ ℕ : j ≥ max{n, t} and j ≡ n (mod t)}.  (3)

For each class of the form [n]_{2^{m}}, we refer to m as the level of the class. Note that each class of level m can “almost” be written as a disjoint union of two classes of level m + 1:

[n]_{2^{m}} ∩ {j ∈ ℕ : j ≥ 2^{m+1}} = [n]_{2^{m+1}} ∪ [n + 2^{m}]_{2^{m+1}}.  (4)

We refer to [n]_{2^{m+1}} and [n + 2^{m}]_{2^{m+1}} as the children of [n]_{2^{m}}.

Throughout this paper, whenever f is a function and S is a subset of the domain of f, we adopt the notation

f(S) = {f(s) : s ∈ S},

and we say that f is constant on S if and only if f(S) a singleton.

Our paper focuses on the following conjecture, posed by Amdeberhan, Manna and Moll, which we refer to as the AMM conjecture [1].

Conjecture 1. For each k ∈ ℕ, there exist non-negative integers M_{k} and μ_{k} such that for any m ≥ M_{k}, the following two statements hold.

(a) There are μ_{k} classes of the form [n]_{2^{m}} on which ν_{2} ∘ St_{k} is non-constant.

(b) If ν_{2} ∘ St_{k} is non-constant on the class [n]_{2^{m}}, then ν_{2} ∘ St_{k} is non-constant on exactly one of the children of [n]_{2^{m}}.

Amdeberhan, Manna and Moll [1] demonstrate when k = 5 that at each level m ≥ 1, there are exactly two classes on which ν_{2} ∘ St_{5} is non-constant. In addition, the authors demonstrate that for each such class, ν_{2} ∘ St_{5} is non-constant on exactly one of the children.

The proof provided by Amdeberhan, Manna and Moll for the case k = 5 could be adapted for the case k = 6 with some additional effort. However, when k = 7, the situation is much more complex, and so a different approach is necessary. In this paper, we produce a general framework that can be used to verify the conjecture for many different values of k, which we have completed for all non-negative integers from k = 5 to k = 20. In Section 6, we use this framework to demonstrate different behaviors exhibited for different values of k.

In order to justify the conjecture, we first determine the classes on which ν_{2} ∘ St_{k} is constant for some initial values of m. To this end, we formulate the definition below.

Definition 2. For any positive integers k, m, we define N_{k,m} by

N_{k,m} = {n ∈ ℕ : k ≤ n < k + 2^{m} and ν_{2} ∘ St_{k} is non-constant on [n]_{2^{m}}}.  (5)

We can compute the number of non-constant classes for small, fixed values of k and m, as described in the table below.

\begin{matrix}k\m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 5 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 6 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 7 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 8 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 9 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 10 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 11 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 12 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 13 & 2 & 4 & 5 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 14 & 2 & 4 & 6 & 6 & 6 & 6 & 6 & 6 & 6 & 6 \end{matrix}

Table 1: The cardinality of N_{k,m}.

Note that for each fixed value of k, the sequence

#N_{k,1}, #N_{k,2}, #N_{k,3}, …

appears to stabilize. From empirical evidence, we conjecture that this, indeed, is the case; in addition, it appears that if we define

n_{k} = lim_{m→∞} #N_{k,m},

then n_{1}, n_{2}, n_{3}, … is a non-decreasing sequence. In future studies, we plan to investigate the validity of this conjecture as well as determine for each k, the smallest index i_{k} such that #N_{k,i} = #N_{k,i_{k}} for all i ≥ i_{k}.

Before revealing our results, we introduce some terminology and make a few additional definitions. Our arguments heavily rely on the result established by Kwong [6] that if k and m are positive integers such that k ≥ 5, then for sufficiently large n,

St_{k}(n) ≡ St_{k}(n + 2^{m}) (mod 2^{m−⌈log_{2}(k)⌉+2}).  (6)

Since the expression ⌈log_{2}(k)⌉−2 appears frequently enough throughout this paper, we make the following definition.

Definition 3. Given k ≥ 5, define

b_{k} = ⌈log_{2}(k)⌉ − 2.

Before proceeding, we must adopt some additional terminology.

Definition 4. Given a set S, if there exists a constant c such that all the elements of S are congruent to c modulo M, then we write S ≡ c (mod M), and we say that S is constant modulo M; otherwise, we say that S is not constant modulo M. Regardless of whether S is constant modulo M, if there exists s ∈ S such that s ≢ c (mod M), then we write S ≢ c (mod M).

We are now in a position to state our main result, which provides a step toward verifying the AMM conjecture for specific values of k. In addition, the theorem provide a way to determine μ_{k}, the number of classes at level k on which ν_{2} ∘ St_{k} is non-constant. It also provides an upper bound on M_{k}, the level at which the number of such classes stabilizes.

Theorem 5. Let k, M be non-negative integers such that k ≥ 5, M ≥ b_{k} and 2^{M} ≥ M −b_{k} + ν_{2}(k!). For each j ∈ N_{k,M}, let ℓ_{j} be a non-negative integer. Suppose further that for every integer n ≥ k such that n ≡ j (mod 2^{M}) for some j ∈ N_{k,M}, the following two conditions hold for all m ≥ M.

(i) St_{k}([n]_{2^{m}}) is not constant modulo 2^{m−b_{k}+ℓ_{j}+1}.

(ii) St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ_{j}}.

Then the AMM conjecture holds with μ_{k} = #N_{k,M} and M_{k} ≤ M.

If it were possible to determine when St_{k}([n]_{2^{m}}) is constant modulo powers of 2, then Theorem 5 would provide a concrete approach to proving the AMM conjecture. Fortunately, Proposition 13 provides conditions that are equivalent to the statement that St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ}. We will consider these conditions when replacing ℓ by the parameter ℓ_{j} (and ℓ_{j} + 1) found in Theorem 5. More specifically, through the use of an auxiliary function f_{k} defined in Lemma 12, we will see that these conditions can be reduced to a finite check using Proposition 13, thus making verification of the AMM conjecture possible. We implement the algorithms that perform these checks using Mathematica, and produce examples for different values of k in Section 6.

3 Preliminary results

To investigate the AMM conjecture and prove our main result, we first produce a few preliminary results concerning modular arithmetic, which we explore in this section. Since equation (2) will play a critical role in our analysis, we must first analyze the behavior of powers of the form t^{n} that appear in the summation. We begin by quoting the following result, which can be attributed to Gauss [4].

Lemma 6. For any integer m ≥ 1 and any odd positive integer t,

t^{2^{m}} ≡ 1 (mod 2^{m+2}).

Using this lemma as a basis, we demonstrate how to produce the binary representation of t^{2^{m}} modulo powers of 2.

Proposition 7. For any odd positive integer t and non-negative integer s, there exists a sequence c_{0}, …, c_{s}, where c_{i} ∈ {0, 1}, such that for m ≥ s + 1,

t^{2^{m}} ≡ 1 + ∑_{i=0}^{s} c_{i}2^{m+2+i} (mod 2^{m+s+3}).

The sequence c_{0}, …, c_{s} is comprised of the first s + 1 digits of the binary representation of the integer (t^{2^{s+1}} − 1)/2^{s+3}.

Before proceeding with the proof, we provide an example. Note that if s = 2 and t = 7, then the base 10 and base 2 representations of (t^{2^{s+1}} − 1)/2^{s+3} are given by

(7^{8} − 1)/32 = (180150)_{10} = (101011111110110110)_{2}.

Therefore, c_{0} = 0, c_{1} = 1, c_{2} = 2, …, and so for m ≥ 3,

7^{2^{m}} ≡ 1 + 2^{m+3} + 2^{m+4} (mod 2^{m+5}).

Repeated applications of this proposition will permit us to reduce some specific expressions modulo powers of 2, which we first encounter in Lemma 12.

Proof. We proceed by induction on m. We begin with the base case m = s + 1. By Lemma 6, t^{2^{s+1}} − 1 is divisible by 2^{s+3}. Define the integer a = (t^{2^{s+1}} − 1)/2^{s+3}, and write its binary representation as a = ∑_{i=0}^{∞} c_{i}2^{i}, where c_{i} = 0 for i ≫ 0. Then a ≡ ∑_{i=0}^{s} c_{i}2^{i} (mod 2^{s+1}), and so a · 2^{s+3} ≡ ∑_{i=0}^{s} c_{i}2^{s+3+i} (mod 2^{2s+4}). Since a = (t^{2^{s+1}} − 1)/2^{s+3}, it follows that t^{2^{s+1}} = 1 + a · 2^{s+3}, and so

t^{2^{s+1}} ≡ 1 + ∑_{i=0}^{s} c_{i}2^{s+3+i} (mod 2^{2s+4}).

For the inductive step, we assume

t^{2^{m}} ≡ 1 + ∑_{i=0}^{s} c_{i}2^{m+2+i} (mod 2^{m+s+3}),

in which case t^{2^{m}} = 1 + A + B · 2^{m+s+3}, where A = ∑_{i=0}^{s} c_{i}2^{m+2+i} and B is an integer. Since t^{2^{m+1}} = (t^{2^{m}})^{2}, we can write

t^{2^{m+1}} = (1 + A + B · 2^{m+s+3})^{2}
= 1 + 2A + A^{2} + 2(1 + A) · B · 2^{m+s+3} + (B · 2^{m+s+3})^{2}
= 1 + 2A + A^{2} + (1 + A) · B · 2^{m+s+4} + (B · 2^{m+s+3})^{2} .

It follows immediately that t^{2^{m+1}} ≡ 1 + 2A + A^{2} (mod 2^{m+s+4}), and so working modulo 2^{m+s+4}, we have

t^{2^{m+1}} ≡ 1 + 2 · ∑_{i=0}^{s} c_{i}2^{m+2+i} + (∑_{i=0}^{s} c_{i}2^{m+2+i})^{2}

≡ 1 + ∑_{i=0}^{s} c_{i}2^{m+3+i} + 2^{2(m+2)} (∑_{i=0}^{s} c_{i}2^{i})^{2} .

Since m ≥ s + 1, it follows that 2^{2(m+2)} ≡ 0 (mod 2^{m+s+4}), and so

t^{2^{m+1}} ≡ 1 + ∑_{i=0}^{s} c_{i}2^{m+3+i} (mod 2^{m+s+4}),

as desired.

Next, we reformulate and reprove (6) while adding specificity to the requirement that n be sufficiently large.

Proposition 8. For non-negative integers k, m, n such that n ≥ k ≥ 5, m ≥ b_{k} and 2^{m} ≥ m − b_{k} + ν_{2}(k!),

St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}}.

Again, before proceeding with the proof, we provide an example. If k = 5, then b_{k} = 1. The conditions m ≥ b_{k} and 2^{m} ≥ m − b_{k} + ν_{2}(k!) hold precisely when m ≥ 3. Reducing multiple expressions of the form St_{k}(n + j · 2^{m}) modulo 2^{m−b_{k}} where j is a positive integer provides evidence of the following modular equivalences, all of which can be justified by the proposition:

St_{k}([1]_{2^{3}}) ≡ 3;
St_{k}([2]_{2^{3}}) ≡ 1;
St_{k}([3]_{2^{3}}) ≡ 2;
St_{k}([4]_{2^{3}}) ≡ 0;
St_{k}([5]_{2^{3}}) ≡ 1;
St_{k}([6]_{2^{3}}) ≡ 3;
St_{k}([7]_{2^{3}}) ≡ 0;
St_{k}([8]_{2^{3}}) ≡ 2.

Proof. First, we note that since each term of [n]_{2^{m}} is at least 2^{m}, we may assume without loss of generality that n ≥ 2^{m}. Since 2^{m} ≥ m − b_{k} + ν_{2}(k!), it follows that

n ≥ m − b_{k} + ν_{2}(k!).

Now, for any given value of n,

St_{k}(n + 2^{m}) ≡ St_{k}(n) (mod 2^{m−b_{k}})

if and only if

k!St_{k}(n + 2^{m}) − k!St_{k}(n) ≡ 0 (mod 2^{m−b_{k}+ν_{2}(k!)}).

Using (2), we can write k!St_{k}(n + 2^{m}) − k!St_{k}(n) as

(−1)^{k} ∑_{t=1}^{k}(−1)^{t}\binom{k}{t}t^{n} (t^{2^{m}} − 1) .

For n ≥ m − b_{k} + ν_{2}(k!), we have that t^{n} ≡ 0 (mod 2^{m−b_{k}+ν_{2}(k!)}) whenever t is even, in which case

h(n) ≡ k!St_{k}(n + 2^{m}) − k!St_{k}(n) (mod 2^{m−b_{k}+ν_{2}(k!)})  (7)

where

h(n) = (−1)^{k} ∑_{s=1}^{⌈k/2⌉}(−1)^{2s−1}\binom{k}{2s − 1}(2s − 1)^{n} ((2s − 1)^{2^{m}} − 1)

= (−1)^{k−1} ∑_{s=1}^{⌈k/2⌉} \binom{k}{2s − 1}(2s − 1)^{n} ((2s − 1)^{2^{m}} − 1)

For any positive integer s, the sequence {(2s−1)^{n}}_{n=1}^{∞} is periodic modulo 2^{m−b_{k}+ν_{2}(k!)}. (More specifically, by Lemma 6, the the period of this sequence reduced modulo 2^{m−b_{k}+ν_{2}(k!)} divides 2^{m−b_{k}+ν_{2}(k!)−2}.) Consequently, {h(n)}_{n=1}^{∞} must be periodic modulo 2^{m−b_{k}+ν_{2}(k!)}. By (7), it follows that the sequence

{k!St_{k}(n + 2^{m}) − k!St_{k}(n)}_{n=m−b_{k}+ν_{2}(k!)}^{∞}

is periodic modulo 2^{m−b_{k}+ν_{2}(k!)}, and so

{St_{k}(n + 2^{m}) − St_{k}(n)}_{n=m−b_{k}+ν_{2}(k!)}^{∞}  (8)

is periodic modulo 2^{m−b_{k}}. However, by (6), for n sufficiently large (n ≫ 0),

St_{k}(n + 2^{m}) − St_{k}(n) ≡ 0 (mod 2^{m−b_{k}}).  (9)

Combining this with (8), we see that (9) holds whenever n ≥ m−b_{k}+ν_{2}(k!), and so St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}}.

Using Proposition 8, we demonstrate that our search for classes [n]_{2^{m}} on which ν_{2} ∘ St_{k} is non-constant can be restricted to those such that St_{k}(n) ≡ 0 (mod 2^{m−b_{k}}).

Proposition 9. Let k, m, n be non-negative integers such that n ≥ k ≥ 5, m ≥ b_{k} and 2^{m} ≥ m − b_{k} + ν_{2}(k!). If ν_{2} ∘ St_{k} is non-constant on [n]_{2^{m}}, then

St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{m−b_{k}}).

Proof. We demonstrate the contrapositive. By Proposition 8, St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}}, and so there exists s ∈ ℕ with s < 2^{m−b_{k}} such that

St_{k}([n]_{2^{m}}) ≡ s (mod 2^{m−b_{k}}).  (10)

Since we are assuming that St_{k}([n]_{2^{m}}) ≢ 0 (mod 2^{m−b_{k}}), it follows that s ≠ 0. Consequently, the 2-adic valuation of every element of S([n]_{2^{m+b_{k}}} , k) is ν_{2}(s).

The next two sections examine when the converse of Proposition 9 holds.

4 General framework

Proposition 9 gives us a sufficient condition for ν_{2} ∘ St_{k} to be constant on a congruence class. In the cases that k ∈ {5, 6}, as we shall see, it turns out that this condition is also necessary. Numerically, we suspect that there are infinitely many values of k for which the congruence condition is necessary; however, for k chosen at random, the probability appears to be small. Our goal in this section is to focus on the relationship between congruence classes and their children regarding whether or not ν_{2} ∘ St_{k} is constant.

We begin by stating the following simple lemma without proof.

Lemma 10. Let k, m, n be non-negative integers such that n ≥ k. If ν_{2} ∘ St_{k} is constant on [n]_{2^{m}}, then it is constant on both of its children.

If ν_{2} ∘ St_{k} is not constant on a given congruence class, then describing the behavior of ν_{2} ∘ St_{k} on the children of the congruence class is more subtle. Below we produce a sufficient result for ν_{2} ∘ St_{k} to be non-constant on the children of a given congruence class.

Lemma 11. Let k, ℓ, M, n be non-negative integers such that n ≥ k ≥ 5, M ≥ b_{k} and 2^{M} ≥ M − b_{k} + ν_{2}(k!). Suppose the following four conditions hold for all m ≥ M.

(i) St_{k}([n]_{2^{m}}) is not constant modulo 2^{m−b_{k}+ℓ+1}.

(ii) St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ}.

(iii) St_{k}([n]_{2^{m+1}}) is constant modulo 2^{m−b_{k}+ℓ+1}.

(iv) St_{k}([n + 2^{m}]_{2^{m+1}}) is constant modulo 2^{m−b_{k}+ℓ+1}.

Then for all m ≥ M, if ν_{2} ∘ St_{k} is non-constant on [n]_{2^{m}}, then it is non-constant on exactly one of its children.

Before proceeding with the proof, we provide an example. For k = 6, we have b_{k} = 5, and we will see in Section 6.1 that for m ≥ 3 and any non-negative integer n,

St_{5}([n]_{2^{m}}) is constant modulo 2^{m−1}

and

St_{5}([n]_{2^{m}}) is not constant modulo 2^{m}.

By selecting ℓ = 0, conditions (i) through (iv) all immediately follow. Consequently, the AMM conjecture immediately follows from the lemma. For k = 7, the scenario is much more complex. In fact, the conditions above do not hold for all values of n. Fortunately, however, these conditions do appear to hold at least for the values of n when ν_{2} ∘ St_{k} is non-constant on [n]_{2^{m}}. Details are provided in Section 6.2.

Proof. Let m ≥ M. First, we note that since each term of [n]_{2^{m}} is at least 2^{m}, we may assume without loss of generality that n ≥ 2^{m}, and since ν_{2}(k!) ≥ b_{k} for all k,

n ≥ 2^{m−M} · 2^{M} ≥ 2^{m−M}(M − b_{k} + ν_{2}(k!)) ≥ 2^{m−M} · M − b_{k} + ν_{2}(k!).

A simple exercise reveals that 2^{m−M} · M ≥ m, which yields the inequality

n ≥ m − b_{k} + ν_{2}(k!).

Note that by condition (ii) St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ}; it then necessarily follows that

St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+j}  (11)

for all 0 ≤ j ≤ ℓ. Using this, we will inductively demonstrate that

St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{m−b_{k}+j})  (12)

for 0 ≤ j ≤ ℓ.

Assuming ν_{2} ∘St_{k} is non-constant on [n]_{2^{m}}, we know by Proposition 9 that St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{m−b_{k}}), thus justifying (12) when j = 0. We proceed by induction, demonstrating that if (12) holds for a particular value of j such that 0 ≤ j ≤ ℓ − 1, then it must also hold for j + 1.

Since 1 ≤ j + 1 ≤ ℓ, it follows from (11) that St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+j+1}. Since we are assuming St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{m−b_{k}+j}), it follows that every element of St_{k}([n]_{2^{m}}) is congruent to either 0 or 2^{m−b_{k}+j} modulo 2^{m−b_{k}+j+1}. Since St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+j+1}, it follows that either St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{m−b_{k}+j+1}) or St_{k}([n]_{2^{m}}) ≡ 2^{m−b_{k}+j} (mod 2^{m−b_{k}+j+1}). If the latter holds, then ν_{2}(St_{k}([n]_{2^{m}})) = {m − b_{k} + j}, contradicting the assumption that ν_{2} is non-constant on St_{k}([n]_{2^{m}}). Consequently, St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{m−b_{k}+j+1}), and so (12) holds for j + 1, as desired.

We have just demonstrated that (12) holds for 0 ≤ j ≤ ℓ, and so, in particular,

St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{m−b_{k}+ℓ}).

Therefore, each element of St_{k}([n]_{2^{m}}) is congruent to either 0 or 2^{m−b_{k}+ℓ} modulo 2^{m−b_{k}+ℓ+1}. Moreover, by conditions (iii) and (iv), we know that St_{k}([n]_{2^{m+1}}) and St_{k}([n + 2^{m}]_{2^{m+1}}) are both constant modulo 2^{m−b_{k}+ℓ+1}. Since by condition (i), St_{k}([n]_{2^{m}}) is not constant modulo 2^{m−b_{k}+ℓ+1}, it follows that either

St_{k}([n]_{2^{m+1}}) ≡ 0 (mod 2^{m−b_{k}+ℓ+1})  (13)

and

St_{k}([n + 2^{m}]_{2^{m+1}}) ≡ 2^{m−b_{k}+ℓ} (mod 2^{m−b_{k}+ℓ+1})  (14)

both hold, or

St_{k}([n]_{2^{m+1}}) ≡ 2^{m−b_{k}+ℓ} (mod 2^{m−b_{k}+ℓ+1})  (15)

and

St_{k}([n + 2^{m}]_{2^{m+1}}) ≡ 0 (mod 2^{m−b_{k}+ℓ+1})  (16)

both hold. Suppose conditions (13) and (14) hold. By (14), we see that ν_{2} is constant on St_{k}([n+2^{m}]_{2^{m+1}}). Since ν_{2} is not constant on St_{k}([n]_{2^{m}}), it follows that ν_{2} cannot be constant on both St_{k}([n]_{2^{m+1}}) and St_{k}([n + 2^{m}]_{2^{m+1}}). Therefore, ν_{2} is not constant on St_{k}([n]_{2^{m+1}}).

Similarly, if conditions (15) and (16) hold, then it can be shown that ν_{2} is constant on St_{k}([n]_{2^{m+1}}) but is not constant on St_{k}([n + 2^{m}]_{2^{m+1}}).

Using this lemma, we are now in a position to prove Theorem 5.

Proof. First, we note by Definition 2, there are #N_{k,m} congruence classes at level m on which ν_{2} ∘ St_{k} is non-constant. Therefore, ν_{2} ∘ St_{k} is constant on the remaining congruence classes at level m. By Lemma 10, ν_{2} ∘ St_{k} is constant on each of the children of those classes.

Therefore, if we can demonstrate that for each congruence class at level m ≥ M on which ν_{2} ∘ St_{k} is non-constant, the function ν_{2} ∘ St_{k} is non-constant on exactly one of its children, then we will have demonstrated both parts (a) and (b) of the AMM conjecture with μ_{k} = #N_{k,m} and M_{k} ≤ M.

Suppose m, n are integers such that m ≥ M and n ≥ k where ν_{2} ∘ St_{k} is non-constant on [n]_{2^{m}}. Since ν_{2} ∘ St_{k} is non-constant on [n]_{2^{m}}, it follows that ν_{2} ∘ St_{k} is non-constant on [n]_{2^{M}}, and so there exists an integer j ∈ N_{k,M} such that n ≡ j (mod 2^{M}). By assumption, we have conditions (i) and (ii) above:

St_{k}([n]_{2^{m}}) is not constant modulo 2^{m−b_{k}+ℓ_{j}+1}  (17)

and

St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ_{j}}.  (18)

Moreover, since (18) actually holds for any value of m ≥ M, replacing m by m + 1 reveals that

St_{k}([n]_{2^{m+1}}) is constant modulo 2^{m−b_{k}+ℓ_{j}+1}.  (19)

Since m ≥ M, we have that n + 2^{m} ≡ j (mod 2^{M}), and so we can replace n by n + 2^{m} to obtain

St_{k}([n + 2^{m}]_{2^{m+1}}) is constant modulo 2^{m−b_{k}+ℓ_{j}+1}.  (20)

Since (17), (18), (19), and (20) represent conditions (i), (ii), (iii), and (iv), respectively, of Lemma 11, it follows that ν_{2} ∘ St_{k} is non-constant on exactly one of [n]_{2^{m+1}} and [n + 2^{m}]_{2^{m+1}}.

5 Computational framework

In this section, we provide a method for determining when sets of the form St_{k}([n]_{2^{m}}) are constant modulo specific powers of 2. We then use this method in Section 6 to perform finite checks that verify the AMM conjecture via Theorem 5. We begin with the following lemma, which translates the condition that St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ} into a statement about an auxiliary function f_{k}(n).

Lemma 12. Let k, ℓ, n be positive integers such that k ≥ 5, and define s = ν_{2}(k!)+ℓ−b_{k} −3. Define f_{k} : ℕ → ℕ by

f_{k}(n) = ∑_{i=1}^{⌈k/2⌉} \binom{k}{t_{i}}t_{i}^{n}(t_{i}^{2^{s+1}} − 1)  (21)

where t_{i} = 2i − 1. Suppose m is an integer such that m ≥ s + 1 and 2^{m} − m ≥ s + 3. If n ≥ 2^{m}, then

St_{k}(n + 2^{m}) ≡ St_{k}(n) (mod 2^{m−b_{k}+ℓ})

if and only if

f_{k}(n) ≡ 0 (mod 2^{2s+4}).

Proof. By (2), we can rewrite the condition

St_{k}(n + 2^{m}) ≡ St_{k}(n) (mod 2^{m−b_{k}+ℓ})

as

∑_{t=1}^{k}(−1)^{t}\binom{k}{t}t^{n+2^{m}} ≡ ∑_{t=1}^{k}(−1)^{t}\binom{k}{t}t^{n} (mod 2^{m+s+3}),

which, in turn, can be rewritten as

∑_{t=1}^{k}(−1)^{t}\binom{k}{t}t^{n}(t^{2^{m}} − 1) ≡ 0 (mod 2^{m+s+3}).  (22)

Since we are assuming that n ≥ 2^{m} and 2^{m} − m ≥ s + 3, it follows that n ≥ m + s + 3. Thus, t^{n} ≡ 0 (mod 2^{m+s+3}) whenever t is even, and so (22) can be expressed as

∑_{i=1}^{⌈k/2⌉} \binom{k}{t_{i}}t_{i}^{n}(t_{i}^{2^{m}} − 1) ≡ 0 (mod 2^{m+s+3}),  (23)

where t_{i} = 2i − 1. Since s = ν_{2}(k!) + ℓ − b_{k} − 3, we know by Proposition 7 that for all m ≥ s + 1,

t_{i}^{2^{m}} − 1 ≡ ∑_{j=0}^{s} c_{i,j}2^{m+2+j} (mod 2^{m+s+3}),  (24)

where c_{i,0}, c_{i,1} …, c_{i,s} is comprised of the first s + 1 digits of the binary representation of the integer (t_{i}^{2^{s+1}} − 1)/2^{s+3}. Substituting this into (23), we obtain the following equivalent statement:

∑_{i=1}^{⌈k/2⌉} \binom{k}{t_{i}}t_{i}^{n} (∑_{j=0}^{s} c_{i,j}2^{m+2+j}) ≡ 0 (mod 2^{m+s+3}).

Multiplying both sides by 2^{s−m+1}, we obtain

∑_{i=1}^{⌈k/2⌉} \binom{k}{t_{i}}t_{i}^{n} (∑_{j=0}^{s} c_{i,j}2^{s+3+j}) ≡ 0 (mod 2^{2s+4}).  (25)

Since (24) holds whenever m ≥ s + 1, we can replace m by s + 1 to obtain

t_{i}^{2^{s+1}} − 1 ≡ ∑_{j=0}^{s} c_{i,j}2^{s+3+j} (mod 2^{2s+4}),

and so by substituting this expression into (25) produces

∑_{i=1}^{⌈k/2⌉} \binom{k}{t_{i}}t_{i}^{n} (t_{i}^{2^{s+1}} − 1) ≡ 0 (mod 2^{2s+4}),  (26)

which is simply the statement that f_{k}(n) ≡ 0 (mod 2^{2s+4}).

We are now in a position to determine when St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ} given appropriate choices of n, m, and ℓ. Using Lemma 12, we reduce this problem to a finite check.

Proposition 13. Let k, ℓ be positive integers such that k ≥ 5, and define s = ν_{2}(k!)+ℓ−b_{k}−3. Let f_{k} : ℕ → ℕ be the function described in (21) where t_{i} = 2i − 1. Then for all n ≥ k, the following three statements are equivalent.

(i) f_{k}(n) ≡ 0 (mod 2^{2s+4}).

(ii) St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ} for all integers m ≥ s+1 such that 2^{m}−m ≥ s+3.

(iii) St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ} for some integer m ≥ s + 1 such that 2^{m} − m ≥ s + 3.

Proof. We will prove (i) ⇒ (ii) ⇒ (iii) ⇒ (i). Before proceeding, we argue that we can assume without loss of generality that n ≥ 2^{m}. Indeed, if m is an integer such that m ≥ s+1 and 2^{m} − m ≥ s + 3, we have that 2^{m} ≥ 2s + 4. Consequently, by using Lemma 6, it can be shown that f_{k}(n) ≡ f_{k}(n + 2^{m}) (mod 2^{2s+4}), and so when considering part (i), it is sufficient to consider the case that n ≥ 2^{m}. Moreover, for parts (ii) and (iii), the congruence class [n]_{2^{m}} solely consists of integers greater than 2^{m}, in which case it is also sufficient to consider the case where n ≥ 2^{m}.

Now, suppose (i) holds for a fixed integer n ≥ k, and let m be an integer such that m ≥ s + 1 and 2^{m} − m ≥ s + 3, in which case 2^{m} ≥ 2s + 4. Consequently, by Lemma 6, we have t_{i}^{2^{m}} ≡ 1 (mod 2^{2s+4}), and so f_{k}(n) ≡ f_{k}(n + 2^{m}) (mod 2^{2s+4}). In fact, multiple applications of Lemma 6 reveal that f_{k}(n) ≡ f_{k}(n + j · 2^{m}) (mod 2^{2s+4}) for all j ∈ ℕ, and so f_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{2s+4}). Therefore, by Lemma 12, St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ}, and so (ii) holds.

The fact that (ii) ⇒ (iii) follows trivially. Now, assuming (iii), we have that St_{k}([n]_{2^{m}}) is constant modulo 2^{m−b_{k}+ℓ} for some integer m ≥ s + 1 such that 2^{m} − m ≥ s + 3. Therefore, by Lemma 12, f_{k}(n) ≡ 0 (mod 2^{2s+4}), which is precisely statement (i).

We also need a method for determining when ν_{2}∘St_{k} is constant on individual congruence classes of the form [n]_{2^{m}}, which is easily described in the following proposition.

Proposition 14. Let k and m be non-negative integers such that n ≥ k ≥ 5, m ≥ b_{k} and 2^{m} ≥ m − b_{k} + ν_{2}(k!). Let r ∈ [n]_{2^{m}}, and define c = (ν_{2} ∘ St_{k})(r).

(a) If m > c + b_{k}, then ν_{2} ∘ St_{k} is constant on [n]_{2^{m}}.

(b) If m ≤ c + b_{k}, then ν_{2} ∘ St_{k} is constant on [n]_{2^{m}} if and only if for all j ∈ ℕ such that

1 ≤ j ≤ 2^{c+b_{k}−m},

St_{k}(n + j · 2^{m}) ≡ 0 (mod 2^{c})

and

St_{k}(n + j · 2^{m}) ≢ 0 (mod 2^{c+1}).

Proof. For part (a), we have m > c + b_{k}. Since (ν_{2} ∘ St_{k})(r) = c, it follows that St_{k}(r) ≡ 0 (mod 2^{c}) but St_{k}(r) ≢ 0 (mod 2^{c+1}). By Proposition 8, we have St_{k}([n]_{2^{c+b_{k}}}) is constant modulo 2^{c}. Since m > c+b_{k}, it follows that St_{k}([n]_{2^{m}}) is constant modulo 2^{c}. Since r ∈ [n]_{2^{m}} and St_{k}(r) ≡ 0 (mod 2^{c}), we have that St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{c}). Thus, ν_{2}(St_{k}(i)) ≥ c for all i ∈ [n]_{2^{m}}, and we have only left to demonstrate that ν_{2}(St_{k}(i)) < c + 1 for all i ∈ [n]_{2^{m}}.

By Proposition 8, we have that St_{k}([n]_{2^{c+1+b_{k}}}) is constant modulo 2^{c+1}. Since m > c + b_{k}, we know m ≥ c + 1 + b_{k}, and so St_{k}([n]_{2^{m}}) is constant modulo 2^{c+1}. Since j ∈ [n]_{2^{m}} and St_{k}(j) ≢ 0 (mod 2^{c+1}), it follows that for all i ∈ [n]_{2^{m}} we have that St_{k}(i) ≢ 0 (mod 2^{c+1}), in which case ν_{2}(St_{k}(i)) < c + 1 , as desired.

For part (b), we consider the case m ≤ c + b_{k}. If ν_{2} ∘ St_{k} is constant on [n]_{2^{m}}, then ν_{2} ∘ St_{k}([n]_{2^{m}}) = c. In this case, St_{k}([n]_{2^{m}}) ≡ 0 (mod 2^{c}) but St_{k}(i) ≢ 0 (mod 2^{c+1}) for all i ∈ [n]_{2^{m}}. For each j ∈ ℕ such that 1 ≤ j < 2^{c−b_{k}−m}, we have n + j · 2^{m} ∈ [n]_{2^{m}}, and so the conclusion follows.

Conversely, we assume that for all j ∈ ℕ such that 1 ≤ j ≤ 2^{c−b_{k}−m},

St_{k}(n + j · 2^{m}) ≡ 0 (mod 2^{c})  (27)

and

St_{k}(n + j · 2^{m}) ≢ 0 (mod 2^{c+1}).  (28)

We will show that for any b ∈ [n]_{2^{m}}, we have ν_{2}(St_{k}(b)) = c, thus demonstrating that ν_{2} ∘St_{k} is constant on [n]_{2^{m}}. Since b ∈ [n]_{2^{m}}, we have that b = n + i · 2^{m} for some i ∈ ℕ. Select j ∈ ℕ such that 1 ≤ j ≤ 2^{c−b_{k}−m} and i ≡ j (mod 2^{c−b_{k}−m}), in which case

b = n + i · 2^{m} ≡ n + j · 2^{m} (mod 2^{c−b_{k}}).

Thus, by Proposition 8, it follows that

St_{k}(b) ≡ St_{k}(n + j · 2^{m}) (mod 2^{c}),

and so by (27), we have that St_{k}(b) ≡ 0 (mod 2^{c}). Similarly, by using Proposition 8 in conjunction with (28), we have that St_{k}(b) ≢ 0 (mod 2^{c+1}). Therefore, ν_{2}(St_{k}(b)) = c.

Using the results from this section in conjunction with Theorem 5, we have a method of verifying the AMM conjecture for different values of k. In the next section, we put this method into practice.

6 Examples

In this section, we begin with k = 5 in order to demonstrate how to reproduce the result of Amdeberhan, Manna, and Moll [1] by using the techniques developed in this paper. Next, we consider k = 6, 7, 13 and 15 in order to compare the behavior of ν_{2} ∘ 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 5 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}+ℓ_{j}} but not constant modulo 2^{m−b_{k}+ℓ_{j}+1}. Proposition 8 and Proposition 13 give us methods for checking these congruences. Unfortunately, however, each of these require certain minimal values of m. The significant bound is

m ≥ s + 1 = ν_{2}(k!) + ℓ − b_{k} − 3,

where ℓ must be determined to ensure that f_{k}(n) ≡ 0 (mod 2^{2s+4}). (For small values of m, we will also need to check that 2^{m} −m ≥ s+3.) Once ℓ is determined, we can prove Theorem 5 for all but a small number of values of m using Mathematica to perform the necessary calculations. The cases for small m can then be handled by the use of Proposition 14. At this point, we have then verified Conecture 1 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 ≤ 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.

6.1 k = 5 and k = 6

We begin by considering the case k = 5. We note that b_{5} = ⌈log_{2}(5)⌉ − 2 = 1 and ν_{2}(5!) = 3, and so s = 3 + ℓ − 1 − 3 = ℓ − 1. Thus m ≥ ℓ. However, if ℓ = 1 or 2, the condition that 2^{m} − m ≥ s + 3 is violated for small values of m, and so we know that we must use Proposition 14 to check whether both m = 1 and m = 2 satisfy the conjecture. Using the proposition, we can computationally determine whether ν_{2} ∘ St_{5} is constant on [n]_{2^{m}} for a given choice of n and m. Using the notation from Defintion 2, with the aid of Mathematica, we determine the following: N_{5,1} = {5, 6}, N_{5,2} = {7, 8} and N_{5,3} = {7, 12}. For m ≥ 3, we turn to our general argument.

By Proposition 8, for m ≥ 3,

St_{5}([n]_{2^{m}}) is constant modulo 2^{m−1}.  (29)

If ℓ = 1, then s = ν_{2}(5!) + ℓ − b_{5} − 3 = 0 and so by Proposition 13, St_{5}([n]_{2^{m}}) is constant modulo 2^{m} whenever m ≥ 3 if and only f_{5}(n) ≢ 0 (mod 2^{4}). We will check the case n = 7 here.

f_{5}(7) = \binom{5}{1}1^{7}(1^{2^{1}} − 1) + \binom{5}{3}3^{7}(3^{2^{1}} − 1) + \binom{5}{5}5^{7}(5^{2^{1}} − 1) (mod 2^{4})
= 0 + 10 · 11 · 8 + 1 · 13 · 8 (mod 2^{4})
= 8 (mod 2^{4})
≢ 0 (mod 2^{4}).

Mathematica needs only a finite check (since we are working modulo 2^{4}) to show the noncongruence for all n. Thus, we conclude that for all m ≥ 3,

St_{5}([n]_{2^{m}}) is not constant modulo 2^{m}.  (30)

Now, if we select M = 3, we see that N_{5,3} = {7, 12}, and if we define ℓ_{7} = ℓ_{12} = 3, then parts (i) and (ii) of Theorem 5 hold for all non-negative integers. (In fact, in order to apply Theorem 5, 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 μ_{5} = #N_{5,3} = 2 and M_{5} ≤ 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 14 and Mathematica, we find that N_{6,1} = {6, 7}, N_{6,2} = {8, 9} and N_{6,3} = {12, 13}. When k = 6, we note that b_{6} = ⌈log_{2}(6)⌉ − 2 = 1 and ν_{2}(6!) = 4. By Proposition 8, for m ≥ 3,

St_{6}([n]_{2^{m}}) is constant modulo 2^{m−1}.  (31)

Using Proposition 13 in a manner similar to that for k = 5, we we conclude that for all m ≥ 3,

St_{6}([n]_{2^{m}}) is not constant modulo 2^{m}.  (32)

Again, as in the case when k = 5, an application of Theorem 5 justifies that the AMM conjecture holds for k = 6 with μ_{6} = 2 and M_{6} ≤ 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 ∈ N_{k,m} if and only if St_{k}[k]([n]_{2^{m+bk}}) ≡ 0 (mod 2^{m}). That is, the converse of Proposition 9 holds.

6.2 k = 7

Although the behavior exhibited by ν_{2} ∘ St_{k} is similar for the cases k = 5 and k = 6, the landscape changes when k = 7. By Proposition 8, for m ≥ 3,

St_{7}([n]_{2^{m}}) is constant modulo 2^{m−1}.  (33)

Using Proposition 13 with ℓ = 1 in conjunction with Mathematica, we find that for m ≥ 3

St_{7}([n]_{2^{m}}) is not constant modulo 2^{m} if and only if n is odd.  (34)

In fact, since (33) follows directly from (34), we did not actually need to apply Proposition 8 for the case k = 7. Using Proposition 13 with ℓ = 2, we find that for m ≥ 3,

St_{7}([n]_{2^{m}}) is not constant modulo 2^{m+1} if and only if n is odd.  (35)

Applying Proposition 13 with ℓ = 3 yields the following for all non-negative integers when m ≥ 4:

St_{7}([n]_{2^{m}}) is not constant modulo 2^{m+2}.  (36)

As with the cases k = 5 and k = 6, it is possible to determine 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 ∈ N_{7,4}. Whenever j is odd, define ℓ_{j} = 1, and whenever j is even, define ℓ_{j} = 2. Thus, whenever n is odd, we see that (35) and (34), constitute parts (i) and (ii) of Theorem 5, respectively. In addition, whenever n is even, (36) and (35) constitute parts (i) and (ii) of Theorem 5, respectively. Putting this together, we see that the AMM conjecture holds for k = 7 with M_{7} ≤ 4.

At this point, it makes sense to say a few words about the role that ℓ plays as well as the link between St_{k}([n]_{2^{m+b_{k}}}) ≡ 0 (mod 2^{m}) and n ∈ N_{k,m}. When ℓ = 1, we have for exactly one child (say x) of [n]_{2^{m+b_{k}}} that St_{k}([x]_{2^{m+b_{k}+1}}) ≡ 0 (mod 2^{m+1}) and x ∈ N_{k,m+1}. However, when ℓ > 1, both children have the property of St_{k}([x]_{2^{m+b_{k}+1}}) ≡ 0 (mod 2^{m+1}), but we know that only one lies in N_{k,m}. The value of ℓ 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 N_{7,1}, N_{7,2}, N_{7,3}, and N_{7,4}, we have the following:

N_{7,1} = {7, 8}
N_{7,2} = {9, 10}
N_{7,3} = {13, 14}
N_{7,4} = {13, 14}.

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 St_{7}(7) ≡ St_{7}(8) ≡ 0 (mod 2^{0}), we see that 7 and 9 behave differently from 8 and 10. In particular, St_{7}(8) ≡ St_{7}(10) ≡ 0 (mod 2^{1}), but St_{7}(7) = 1 ≢ 0 (mod 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 ℓ 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 ℓ from 1 to 4 gives new congruence classes for n with f_{15}(n) ≢ 0 (mod 2^{2s+4}). On the bright side, however, similar to the case k = 7 where f_{3}(n) ≢ 0 (mod 2^{2s+4}) for all n whenever ℓ = 3, for k = 15 we have a similar result for ℓ = 4.

6.3 k = 13

The case k = 13 is unique in that it is not sufficient to use Proposition 8 in conjunction with performing calculations according to Proposition 13. According to Proposition 8, for m ≫ 0, we have

St_{13}([n]_{2^{m}}) is constant modulo 2^{m−2}.  (37)

For m ≫ 0, we can use Proposition 13 to determine that the following holds if and only if n ≡ 1, 2 (mod 4):

St_{13}([n]_{2^{m}}) is not constant modulo 2^{m−1}.  (38)

In addition, for m ≫ 0, the following holds if and only if n ≡ 0, 1, 2 (mod 4):

St_{13}([n]_{2^{m}}) is not constant modulo 2^{m}.  (39)

However, within our ability to calculate with Mathematica there is no non-negative integer ℓ such that for sufficiently large m such that for all n ≥ m, f_{13}(n) ≢ 0 (mod 2^{s+4}). In other words, there is no non-negative integer L such that the following holds for all non-negative integers n:

St_{13}([n]_{2^{m}}) is not constant modulo 2^{m+L}.  (40)

This peculiarity distinguishes the case k = 13 from all other cases when k ≤ 20. Fortunately, a finite check (using Proposition 9) verifies that ν_{2} ∘ St_{13} is constant on the class [n]_{2^{m}} whenever n ≡ 3 (mod 4), and so when employing Theorem 5, we only need to consider values of n where n ≡ 0, 1, 2 (mod 4). Consequently, statements (37), (38) and (39) 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 ℓ to guarantee that f_{k}(n) ≢ 0 (mod 2^{2s+4}) for all n, but in cases like k = 13, where finding such an ℓ 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 9 to check which n we need to check for each ℓ. 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) (mod 2^{2s+4}) is a limiting factor since the magnitude of s is largely dictated by ν_{2}(k!).

The case of k = 13 also shows another complication in that 9 ∈ 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 9 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 ≥ 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.

6.4 General k

The Mathematica code that performs the calculations yielding the proof of the conjecture for k ≤ 20 is available at http://myweb.lmu.edu/emosteig. For these values of k, the largest choice of ℓ 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 ≤ 100 (and in fact, k = 89 appears to be require a very large value of ℓ based on the data we currently have).

7 Further questions

As we approached this problem, we collected a lot of data concerning which values of n, m and k the statement St_{k}([n]_{2^{m+b_{k}}}) ≡ 0 (mod 2^{m}) holds true. As might be expected by the requirement that f_{k}(n) ≢ 0 (mod 2^{2s+4}) together with m ≥ s + 1 in the computergenerated (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.

Conjecture 15. The AMM conjecture holds for k = 2^{t} + 1 for all integers t ≥ 2. Moreover, the following hold.

1. The parameter ℓ can be chosen equal to 1. That is, if s = ν_{2}(k!) + 1 − b_{k} − 3 = ν_{2}(k!) + t − 3, m ≥ s + 1, and 2^{m} − m ≥ s + 3, then f_{k}(n) ≢ 0 (mod 2^{2s+4}) for all n.

2. M_{k} = 1.

3. μ_{k} = #N_{k,m} = 2^{t−1} for all m.

A natural question arises about whether this work might apply to the work of Berrizbeitia et. al. [2], 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 7 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 ≡ ±1 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}} ≡ ∑_{t=0}^{n} a_{t}5^{t} (mod 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}} ≡ 7^{5^{n}} (mod 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 St_{k}(n + 2^{m}) − St_{k}(n), we will need to show that each element of {St_{k}(n + a · p^{m}) | a ∈ {0, 1, …, 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, …, 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 · 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 · 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 ℓ, M_{k} and μ_{k}. In particular, from our early data, it appears that μ_{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 ℓ, we notice that the largest choices of ℓ needed for Lemma 11 occurs when k = 2^{t} − 1. Is there a reason for this? Is this true in general? More precisely, determining bounds for ℓ depending on k would be extremely interesting.

References

[1] T. Amdeberhan, D. Manna, and V. Moll, The 2-adic valuation of Stirling numbers, Exp. Math. 17 (2008), 69–82.

[2] A. Berrizbeitia, L. A. Medina, A. C. Moll, V. Moll, and L. Noble, The p-adic valuation of Stirling numbers, Journal for Algebra and Number Theory Academia 1 (2010), 1–30.

[3] S. De Wannemacker, On 2-adic orders of Stirling numbers of the second kind, Integers 5 (2005).

[4] D. Dummit and R. Foote, Abstract Algebra, Prentice-Hall, 1991.

[5] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

[6] Y. H. H. Kwong, Minimum periods of S(n, k) modulo M, Fibonacci Quart. 27 (1989), 217–221.

[7] T. Lengyel, On the divisibility by 2 of the Stirling numbers of the second kind, Fibonacci Quart., 32 (1994) 194–201.

[8] T. Lengyel, On the 2-adic order of Stirling numbers of the second kind and their differences, in 21st International Conference on Formal Power Series and Algebraic Combinatorics — FPSAC 2009, Discrete Math. Theor. Comput. Sci. Proc., 2009, pp. 561–572.

[9] Wolfram Research, Inc., Mathematica, Version 8.0, Champaign, IL, 2010.

2010 Mathematics Subject Classification: Primary 11B73; Secondary 05A15.

Keywords: Stirling number, valuation, combinatorial enumeration problem. Received April 27 2012; revised version received February 17 2013. Published in Journal of Integer Sequences, March 2 2013. Return to Journal of Integer Sequences home page.