The p-adic Valuations of Sequences Counting Alternating Sign Matrices

Xinyu Sun and Victor H. Moll Department of Mathematics Tulane University New Orleans, LA 70118 USA

                  xsun1@math.tulane.edu
                   vhm@math.tulane.edu

Abstract The p-adic valuations of a sequence of integers counting alternating sign symmetric matrices are examined for p = 2 and 3. Symmetry properties of their graphs produce a new proof of the result that characterizes the indices that yield an odd number of matrices.

1 Introduction

The magnificent book Proofs and Confirmations by David Bressoud [3] tells the story of the Alternating Sign Matrix Conjecture (ASM) and its proof. This remarkable result involves the counting function

T (n) = ∏_{j=0}^{n−1} \frac{(3j + 1)!}{(n + j)!}.  (1.1)

The survey by Bressoud and Propp [4] describes the mathematics underlying this problem.

The fact that these numbers are integers is a direct consequence of their appearance as counting sequences. Mills, Robbins and Rumsey [11] conjectured that the number of n × n matrices whose entries are −1, 0, or 1, whose row and column sums are all 1, and such that in every row, and in every column the non-zero entries alternate in sign is given by T (n). The first proof of this ASM conjecture was provided by D. Zeilberger [12]. This proof had the added feature of being pre-refereed. Its 76 pages were subdivided by the author who provided a tree structure for the proof. An army of volunteers provided checks for each node in the tree. The request for checkers can be read in

          http://www.math.rutgers.edu/∼zeilberg/asm/CHECKING

The question of integrality of quotients of factorials, such as T (n), has been considered by D. Cartwright and J. Kupka [5].

Theorem 1.1. Assume that for every integer k ≥ 2 we have

∑_{i=1}^{m} ⌊\frac{a_{i}}{k} ⌋ ≤ ∑_{j=1}^{n} ⌊\frac{b_{j}}{k} ⌋ .  (1.2)

Then the ratio of ∏_{j=1}^{n} b_{j}! to ∏_{i=1}^{m} a_{j}! is an integer.

The authors [5] use this result to prove that T (n) is an integer.

Given an interesting sequence of integers, it is a natural question to explore the structure of their factorization into primes. This is measured by the p-adic valuation of the elements of the sequence.

Definition 1.2. Given a prime p and a positive integer x ≠ 0, write x = p^{m}y, with y not divisible by p. The exponent m is the p-adic valuation of x, denoted by m = ν_{p}(x). This definition is extended to x = a/b ∈ ℚ via ν_{p}(x) = ν_{p}(a) − ν_{p}(b). We leave the value ν_{p}(0) as undefined.

The p-adic valuations of many sequences have surprising properties. The reader will find in Amdeberhan, Manna, and Moll [1] an analysis of the 2-adic valuation of the sequence

A_{l,m} = \frac{l!m!}{2^{m−l}} ∑_{k=l}^{m} 2^{k}\binom{2m − 2k}{m − k}\binom{m + k}{m}\binom{k}{l}  (1.3)

for fixed l ∈ ℕ and m ≥ l. This example appeared in the evaluation of a definite integral and some of its properties are given by Manna and Moll [10]. The 2-adic properties of the Stirling numbers of the second kind are described by Amdeberhan, Manna, and Moll [2].

Figure 1: The 2-adic valuation of T (n)  Figure 2: The 3-adic valuation of T (n)

In this paper we provide a complete description of the p-adic valuation of the sequence T (n) in (1.1) for the primes p = 2 and 3. Figure 1 depicts the sequence ν_{2} ∘ T (n) for 1 ≤ n ≤ 10^{5} and Figure 2 gives ν_{3} ∘ T (n) for 1 ≤ n ≤ 3^{12} = 531441.

The case p ≥ 5 presents similar features and the techniques presented here could be used to describe the function ν_{p} ∘ T completely. This will be reported elsewhere.

As a corollary of the analysis presenetd here, we produce a new proof of a result of D. Frey and J. Sellers [6]: the number T (n) is odd if and only if n is a Jacobsthal number J_{m}. These numbers, defined by the recurrence J_{n} = J_{n−1} + 2J_{n−2} with initial conditions J_{0} = 1 and J_{1} = 1, are reviewed in Section 3.

The main result of this paper is:

Theorem 1.3. Let J_{n} the Jacobsthal number and define I_{n} := [J_{n}, J_{n+1}]. The function ν_{2} ∘ T restricted to I_{n} is determined by its restriction to I_{n−1} ∪ I_{n−2}.

The details are provided in the algorithm presented next.

Algorithm for the function ν_{2} ∘ T:

Step 1. Verify the special values ν_{2}(T (2^{n})) = J_{n−1} and ν_{2}(T (J_{n})) = 0. The midpoint of the interval I_{n} = [ J_{n}, J_{n+1} ] is 2^{n}. Step 2. Given N ∈ ℕ, compute the unique index n such that J_{n} ≤ N < J_{n+1}. Step 3. For 1 ≤ i ≤ J_{n−1},

ν_{2}(T (2^{n} + i)) = ν_{2}(T (2^{n} − i)).  (1.4)

Thus, if 2^{n} < N < J_{n+1}, replace N by N^{∗} := 2^{n+1} − N that satisfies J_{n} < N^{∗} < 2^{n} and ν_{2}(T (N)) = ν_{2}(T (N^{∗})). Therefore, the value of ν_{2} ∘ T on the interval [J_{n}, J_{n+1}] is determined by the values on its first half [J_{n}, 2^{n}]. Step 4. For 0 < i < 2J_{n−3},

ν_{2}(T (J_{n} + i)) = i + ν_{2}(T (J_{n−2} + i)).  (1.5)

This yields the value of ν_{2} ∘ T on the first part of the interval [ J_{n}, 2^{n}], namely [ J_{n}, J_{n} + 2J_{n−3} ], in terms of those from I_{n−2} = [ J_{n−2}, J_{n−1} ]. Step 5. For 0 ≤ i ≤ J_{n−2},

ν_{2}(T (2^{n} − J_{n−2} + i)) = ν_{2}(T (J_{n−1} + i)) + 2J_{n−3}.  (1.6)

This determines the values of ν_{2} ∘ T on the second part of the interval [ J_{n}, 2^{n}], namely [ J_{n} + 2J_{n−3}, 2^{n}], in terms of ν_{2} ∘ T restricted to the previous interval I_{n−1} = [ J_{n−1}, J_{n−2} ].

The proof of this result is given in Section 4.

Theorem 1.4. For n ∈ ℕ, let f_{n} be the restriction of ν_{2}∘T to the interval I_{n} scaled to the unit square [0, 1]×[0, 1]. Then f_{n} converges to the unique function f : [0, 1] → [0, 1] that satisfies

f(x) = \begin{cases}2x + \frac{1}{4}f(4x), & if 0 ≤ x < \frac{1}{4}; \\ \frac{1}{2} + \frac{1}{2}f(2x − \frac{1}{2}), & if \frac{1}{4} ≤ x ≤ \frac{3}{4}; \\ 2(1 − x) + \frac{1}{4}f(4x − 3), & if \frac{3}{4} < x ≤ 1. \end{cases}

Similar results are valid for primes p ≥ 3. Some details are given in Section 5. The generalization of T (n) defined by

T_{p}(n) := ∏_{j=0}^{n−1} \frac{(pj + 1)!}{(n + j)!}  (1.7)

is also considered. The numbers T_{p}(n) are integers and a recurrence for its p-adic valuation is presented. A combinatorial interpretation of them is left as an open question.

2 A recurrence

The integers T (n) defined in (1.1) grow rapidly and a direct calculation using (1.1) is impractical. The number of digits of T (10^{k}) is 12, 1136, 113622 and 11362189 for 1 ≤ k ≤ 4. Naturally, the prime factorization of T (n) can be computed in reasonable time since every prime p dividing T (n) satisfies p ≤ 3n − 2.

In this section we discuss a recurrence for the p-adic valuation of T (n), that permits its fast computation. Introduce the notation

f_{p}(j) := ν_{p}(j!).  (2.1)

Theorem 2.1. Let p be a prime. Then the p-adic valuation of T (n) satisfies

ν_{p}(T (n + 1)) = ν_{p}(T (n)) + f_{p}(3n + 1) + f_{p}(n) − f_{p}(2n) − f_{p}(2n + 1).  (2.2)

Proof. This follows directly by combining the initial value T (1) = 1 with the expression

ν_{p}(T (n)) = ∑_{j=0}^{n−1} f_{p}(3j + 1) − ∑_{j=0}^{n−1} f_{p}(n + j)  (2.3)

and the corresponding one for ν_{p}(T (n + 1)).

Legendre [9] established the formula

f_{p}(j) = ν_{p}(j!) = \frac{j − S_{p}(j)}{p − 1},  (2.4)

where S_{p}(j) denotes the sum of the base-p digits of j. The result of Theorem 2.1 is now expressed in terms of the function S_{p}.

Corollary 2.2. The p-adic valuation of T (n) is given by

ν_{p}(T (n)) = \frac{1}{p − 1} (∑_{j=0}^{n−1} S_{p}(n + j) − ∑_{j=0}^{n−1} S_{p}(3j + 1)) .  (2.5)

Summing the recurrence (2.2) and using T (1) = 1 we obtain an alternative expression for the p-adic valuation of T (n).

Proposition 2.3. The p-adic valuation of T (n) is given by

ν_{p}(T (n)) = \frac{1}{p − 1} ∑_{j=1}^{n−1} (S_{p}(2j) + S_{p}(2j + 1) − S_{p}(3j + 1) − S_{p}(j)) .  (2.6)

In particular, for p = 2 we have

ν_{2}(T (n)) = ∑_{j=0}^{n−1} (S_{2}(2j + 1) − S_{2}(3j + 1))  (2.7)

Corollary 2.4. For each n ∈ ℕ we have

∑_{j=1}^{n−1} S_{2}(2j + 1) ≥ ∑_{j=1}^{n−1} S_{2}(3j + 1).  (2.8)

Note. The formula (2.6) can be used to compute T (n) for large values of n. Recall that only primes p ≤ 3n − 2 appear in the factorization of T (n). For example, the number T (100) has 1136 digits and its prime factorization is given by

T (100) = 2^{23} · 3^{19} · 13^{13} · 17^{4} · 29^{3} · 41^{4} · 61^{2} · 67^{11} · 71^{5} · 73^{3} · 151 · 157^{5} · 163^{9} · 167^{11} × 173^{15} · 179^{19} · 181^{21} · 191^{27} · 193^{29} · 197^{31} · 199^{33} · 211^{30} · 223^{26} · 227^{24} · 229^{24} · 233^{22}

× 239^{20} · 241^{40} · 251^{16} · 257^{14} · 263^{12} · 269^{10} · 271^{10} · 277^{8} · 281^{6} · 283^{6} · 293^{2}.

3 The Jacobsthal numbers

The Jacobsthal sequence (A001045) is defined by the recurrence

J_{n} = J_{n−1} + 2J_{n−2}, with J_{0} = 1, J_{1} = 1.  (3.1)

The first few values are 1, 1, 3, 5, 11, 21, 43, 85. These numbers have many interpretations. Here is a small sample:

a) J_{n} is the numerator of the reduced fraction in the alternating sum

∑_{j=1}^{n+1} \frac{(−1)^{j+1}}{2^{j}} .

b) Number of permutations with no fixed points avoiding 231 and 132.

c) The number of odd coefficients in the expansion of (1 + x + x^{2})^{2^{n−1}−1}.

Many other examples can be found at

         http://www.research.att.com/∼njas/sequences/A001045

The discussion of the function ν_{2} ∘ T employs several elementary properties of the Jacobsthal number J_{n}, summarized here for the convenience of the reader. Lemma 3.1. For n ≥ 2, the Jacobsthal numbers J_{n} satisfy

a) J_{n} = J_{n−1} + 2J_{n−2} with J_{0} = 1 and J_{1} = 1. (This is the definition of J_{n}).

b) J_{n} = \frac{1}{3}(2^{n+1} + (−1)^{n}). Therefore J_{n} is the nearest integer to \frac{2^{n+1}}{3} .

c) 2^{n−1} + 1 ≤ J_{n} < 2^{n}.

d) J_{n} + J_{n−1} = 2^{n}.

e) J_{n} − J_{n−2} = 2^{n−1}.

4 The 2-adic valuation of T (n)

The goal of this section is to prove Theorem 1.3. The algorithm presented in Section 1 is justified. The analysis begins with an auxiliary lemma.

Lemma 4.1. Let n ∈ ℕ. Introduce the notation S_{n,j}^{+} := S_{2}(3 · 2^{n} + 3j − 2) and S_{n,j}^{−} := S_{2}(3 · 2^{n} − 3j + 1). Then

S_{n,j}^{+} = \begin{cases}S_{2}(3j − 2) + 2, & if 1 ≤ j ≤ J_{n−1}; \\ S_{2}(3j − 2), & if 1 + J_{n−1} ≤ j ≤ J_{n}; \\ S_{2}(3j − 2) + 1, & if 1 + J_{n} ≤ j ≤ 2^{n}; \end{cases}  (4.1)

and

S_{n,j}^{−} = \begin{cases}n + 1 − S_{2}(3j − 2), & if 1 ≤ j ≤ J_{n−1}; \\ n + 2 − S_{2}(3j − 2), & if 1 + J_{n−1} ≤ j ≤ J_{n}; \\ n + 1 − S_{2}(3j − 2), & if 1 + J_{n} ≤ j ≤ 2^{n}. \end{cases}  (4.2)

Proof. Let 3j − 2 = a_{0} + 2a_{1} + ⋯ + a_{r}2^{r} be the binary expansion of 3j − 2. The corresponding one for 3 · 2^{n−1} is simply 2^{n−1} + 2^{n}. For 3j − 2 < 2^{n−1} these two expansions have no terms in common, therefore S_{n,j}^{+} = S_{2}(3j − 2) + 2. On the other hand, if 2^{n−1} ≤ 3j − 2 < 2^{n} then the index in the binary expansion of 3j − 2 is r = n − 1 with a_{n−1} = 1. The expansion of 3j − 2 + 3 · 2^{n−1} is now

a_{0} + 2a_{1} + ⋯ + a_{n−2}2^{n−2} + 2^{n−1} + 2^{n−1} + 2^{n} = a_{0} + 2a_{1} + ⋯ + a_{n−2}2^{n−2} + 2^{n+1},

and this yields S_{n,j}^{+} = a_{0} + a_{1} + ⋯ + a_{n−2} + 1 = S_{2}(3j − 2). The remaining cases are treated in a similar form.

We now establish the 2-adic valuation at the center of the interval [J_{n−1}, J_{n}]. This establishes one of the special values in Step 1 of the algorithm. Theorem 4.2. Let n ∈ ℕ. Then

ν_{2} (T (2^{n})) = J_{n−1}.  (4.3)

Proof. We proceed by induction and split

ν_{2} (T (2^{n})) = ∑_{j=1}^{2^{n}−1} [S_{2}(2j + 1) − S_{2}(3j + 1)]  (4.4)

at j = 2^{n−1} − 1. The first part is identified as ν_{2} (T (2^{n−1})) to produce

ν_{2} (T (2^{n})) = ν_{2} (T (2^{n−1})) + ∑_{j=0}^{2^{n−1}−1} S_{2}(2j + 1 + 2^{n}) − ∑_{j=1}^{2^{n−1}} S_{2}(3j − 2 + 3 · 2^{n−1}).

From 2j + 1 ≤ 2^{n} − 1 < 2^{n} it follows S_{2}(2j + 1 + 2^{n}) = S_{2}(2j + 1) + 1. Assume first that n is even. Lemma 4.1 gives

∑_{j=1}^{2^{n−1}} S_{2}(3j − 2 + 3 · 2^{n−1}) = ∑_{j=1}^{(2^{n−1}+1)/3}[S_{2}(3j − 2) + 2]+

∑_{j=(2^{n−1}+1)/3}^{(2^{n}−1)/3} S_{2}(3j − 2) + ∑_{j=(2^{n}+2)/3}^{2^{n−1}}[S_{2}(3j − 2) + 1]

and using (2.7) yields

ν_{2}(T (2^{n})) = 2ν_{2}(T (2^{n−1})) − 1 = 2J_{n−2} − 1.  (4.5)

Elementary properties of Jacobsthal numbers give 2J_{n−2} − 1 = J_{n−1}, proving the result. The argument for n odd is similar.

The next theorem gives the second special value in Step 1. Theorem 4.3. Let n ∈ ℕ. Then ν_{2}(T (J_{n})) = 0. Proof. Proposition 2.3 gives

ν_{2} (T (J_{n})) = ∑_{j=1}^{J_{n}−1} [S_{2}(2j + 1) − S_{2}(3j + 1)] .  (4.6)

Split the sum at 2^{n−1} ≤ J_{n} − 1 to obtain

ν_{2} (T (J_{n})) = ∑_{j=1}^{2^{n−1}−1} [S_{2}(2j + 1) − S_{2}(3j + 1)]

+ ∑_{j=2^{n−1}}^{J_{n}−1} [S_{2}(2j + 1) − S_{2}(3j + 1)]

= ν_{2} (T (2^{n−1})) + ∑_{j=2^{n−1}}^{J_{n}−1} [S_{2}(2j + 1) − S_{2}(3j + 1)] .

Therefore

ν_{2} (T (J_{n})) = ν_{2}(T (2^{n−1})) + ∑_{j=0}^{J_{n}−1−2^{n−1}} [S_{2}(2j + 1 + 2^{n}) − S_{2}(3j + 1 + 3 · 2^{n−1})] .

The Jacobsthal numbers satisfy J_{n} − 1 − 2^{n−1} = J_{n−2} − 1, so that

ν_{2} (T (J_{n})) = ν_{2}(T (2^{n−1})) + ∑_{j=0}^{J_{n−2}−1} [S_{2}(2j + 1 + 2^{n}) − S_{2}(3j + 1 + 3 · 2^{n−1})] .

The relation

2j + 1 ≤ 2(J_{n−2} − 1) + 1 = 2J_{n−2} − 1 = J_{n} − J_{n−1} − 1 < 2^{n},

implies

S_{2}(2j + 1 + 2^{n}) = S_{2}(2j + 1) + 1.

Similarly 3j +1 ≤ 3J_{n−2} −2 < 3(2^{n−1} +(−1)^{n})−2 ≤ 2^{n−1} −1 and 3·2^{n−1} = 2^{n} +2^{n−1} give

S_{2}(3j + 1 + 3 · 2^{n−1}) = S_{2}(3j + 1) + 2,

for 0 ≤ j ≤ J_{n−2} − 1. Therefore

ν_{2} (T (J_{n})) = ν_{2} (T (2^{n−1})) + ∑_{j=0}^{J_{n−2}−1} [S_{2}(2j + 1) − S_{2}(3j + 1)] − J_{n−2}.

Theorem 4.2 shows that the first and third term on the line above cancel, leading to

ν_{2} (T (J_{n})) = ν_{2} (T (J_{n−2})) .

The result now follows by induction on n.

We continue with the analysis of the function ν_{2}∘T. The next Lemma corresponds to Step 3 in the outline that deals with ν_{2}(T (j)) for J_{n} ≤ j ≤ J_{n} + 2J_{n−3} = 2^{n} − J_{n−2}.

Lemma 4.4. For 0 < i ≤ 2J_{n−3} we have

ν_{2}(T (J_{n} + i)) = i + ν_{2}(T (J_{n−2} + i)).  (4.7)

Proof. Assume n is even. Then

ν_{2}(T (J_{n} + i)) = ∑_{j=1}^{J_{n}+i−1} [S_{2}(2j + 1) − S_{2}(3j + 1)]

= ∑_{j=1}^{J_{n}−1} [S_{2}(2j + 1) − S_{2}(3j + 1)] + ∑_{j=J_{n}}^{J_{n}+i−1} [S_{2}(2j + 1) − S_{2}(3j + 1)] .

The first sum is ν_{2}(T (J_{n})) = 0, according to Theorem 4.3. Lemma 3.1 now gives

ν_{2}(T (J_{n} + i)) = ∑_{j=J_{n}}^{J_{n}+i−1} [S_{2}(2j + 1) − S_{2}(3j + 1)]

= ∑_{j=J_{n}+1}^{J_{n}+i} [S_{2}(2j − 1) − S_{2}(3j − 2)]

= ∑_{j=J_{n}+1−2^{n−1}}^{J_{n}+i−2^{n−1}} [S_{2}(2^{n} + 2j − 1) − S_{2}(3 · 2^{n−1} + 3j − 2)]

= ∑_{j=J_{n−2}+1}^{J_{n−2}+i} [S_{2}(2^{n} + 2j − 1) − S_{2}(3 · 2^{n−1} + 3j − 2)] .

The index j satisfies

2j − 1 ≤ 2(J_{n−2} + i) − 1 < 2(J_{n−2} + 2J_{n−3}) = 2J_{n−1} < 2^{n},

therefore S_{2}(2^{n} + 2j − 1) = 1 + S_{2}(2j − 1). The lower limit in the last sum is J_{n−2} + 1 = \frac{1}{3}(2^{n−1} + 1) + 1, and the upper bound is

J_{n−2} + i ≤ J_{n−2} + 2J_{n−3} = J_{n−1} = \frac{1}{3}(2^{n} − 1).  (4.8)

For these values of j, Lemma 4.1 gives S_{2}(3 · 2^{n−1} + 3j − 2) = S_{2}(3j − 2). Therefore

ν_{2}(T (J_{n} + i)) = ∑_{j=J_{n−2}+1}^{J_{n−2}+i} [S_{2}(2j − 1) + 1 − S_{2}(3j − 2)]

= i + ∑_{j=J_{n−2}+1}^{J_{n−2}+i} [S_{2}(2j − 1) − S_{2}(3j − 2)]
= i + ν_{2}(T (J_{n−2} + i)).

The result has been established for n even. The proof for n odd is similar.

Corollary 4.5. The 2-adic valuation of T (n) satisfies ν_{2}(T (j)) > 0 for J_{n} < j < 2^{n} − J_{n−2}.

The next result shows the graph of ν_{2} ∘ T on the interval [2^{n} − J_{n−2}, 2^{n} + J_{n−2}] is a vertical shift of the graph on [J_{n−1}, J_{n}]. This corresponds to Step 4 in the outline.

Proposition 4.6. For 0 ≤ i ≤ 2J_{n−2},

ν_{2}(T (2^{n} − J_{n−2} + i)) = ν_{2}(T (J_{n−1} + i)) + 2J_{n−3}.  (4.9)

Proof. The functions ν_{2}(T (J_{n−1} + i)) and ν_{2}(T (2^{n} − J_{n−2} + i)) have the same discrete derivative. This amounts to

ν_{2}(T (J_{n−1} + i)) − ν_{2}(T (J_{n−1} + i − 1)) = ν_{2}(T (2^{n} − J_{n−2} + i)) − ν_{2}(T (2^{n} − J_{n−2} + i − 1)) (4.10)

for 1 ≤ i ≤ 2J_{n−2}. Observe that

ν_{2}(T (k)) − ν_{2}(T (k − 1)) = S_{2}(2k − 1) − S_{2}(3k − 2),  (4.11)

and using 2^{n} − J_{n−2} = 2^{n−1} + J_{n−1}, conclude that the result is equivalent to the identity

S_{2}(2^{n} + 2(J_{n−1} + i) − 1) − S_{2}(2(J_{n−1} + i) − 1) = S_{2}(3 · 2^{n−1} + 3(J_{n−1} + i) − 2) − S_{2}(3(J_{n−1} + i) − 2), (4.12) for 1 ≤ i ≤ 2J_{n−2}. Define

h_{n}(i) = \begin{cases}1, & if 1 ≤ i ≤ J_{n−2}; \\ 0, & if J_{n−2} + 1 ≤ i ≤ 2J_{n−2}. \end{cases}  (4.13)

The assertion is that both sides in (4.12) agree with h_{n}(i). The analysis of the left hand side is easy: the condition 1 ≤ i ≤ J_{n−2} implies 2(J_{n−1} + i) − 1 ≤ 2^{n} − 1. Thus, the term 2^{n} does not interact with the binary expansion 2(J_{n−1} + i) − 1 and produces the extra 1. On the other hand, if J_{n−2} + 1 ≤ i ≤ 2J_{n−2}, then

2^{n} + 1 = 2(J_{n−1} + J_{n−2} + 1) − 1 ≤ 2(J_{n−1} + i) − 1 ≤ 2(J_{n−1} + 2J_{n−2}) − 1 = 2J_{n} − 1 < 2^{n+1} − 1. (4.14)

Therefore the binary expansion of x := 2(J_{n−1} + i) − 1 is of the form a_{0} + a_{1} · 2 + ⋯ + a_{n−1} · 2^{n−1} + 1 · 2^{n}. It follows that 2^{n} + x and x have the same number of 1’s in their binary expansion. Thus S_{2}(x) = S_{2}(x + 2^{n}) as claimed.

The analysis of the right hand side of (4.12) is slightly more difficult. Let x := 3(J_{n−1} + i) − 2 and it is required to compare S_{2}(x) and S_{2}(3 · 2^{n−1} + x). Observe that

x ≤ 3(J_{n−1} + 2J_{n−2}) − 2 = 3J_{n} − 2 = 2^{n+1} + (−1)^{n} − 2 < 2^{n+1}  (4.15)

and

x ≥ 3(J_{n−1} + 1) − 2 = 2^{n} + (−1)^{n−1} + 1 ≥ 2^{n}.  (4.16)

This shows that the binary expansion of x is of the form

x = a_{0} + a_{1} · 2 + · + a_{n−1} · 2^{n−1} + 1 · 2^{n},  (4.17)

and the corresponding one for 3 · 2^{n−1} is 2^{n} + 2^{n−1}. An elementary calculation shows that S_{2}(x + 3 · 2^{n−1}) − S_{2}(x) is 1 if a_{n−1} = 0 and 0 if a_{n−1} = 1. In order to transform this inequality to a restriction on the index i, observe that a_{n−1} = 1 is equivalent to x − 2^{n} ≥ 2^{n−1}. Using the value of x this becomes 3(J_{n−1} + i) − 2) ≥ 3 · 2^{n−1}, that is directly transformed to i ≥ J_{n−2} + 1. This shows that the right hand side of (4.12) also agrees with h_{n} and (4.12) has been established.

The final step in the proof of Theorem 1.3 deals with the symmetry of the graph of ν_{2}(T (j)) on I_{n} about the point j = 2^{n}. The range covered in the next proposition is 2^{n} − J_{n−1} ≤ j ≤ 2^{n} + J_{n−1}.

Proposition 4.7. For 1 ≤ i ≤ J_{n−1},

ν_{2}(T (2^{n} − i)) = ν_{2}(T (2^{n} + i)).  (4.18)

Proof. Start with

ν_{2}(T (2^{n})) − ν_{2}(T (2^{n} − i)) = ∑_{j=2^{n}−i+1}^{2^{n}} [S_{2}(2j − 1) − S_{2}(3j − 2)]

= ∑_{k=1}^{i} [S_{2}(2^{n+1} − (2k − 1)) − S_{2}(3 · 2^{n} − (3k − 1))] .

The first term in the sum satisfies

S_{2}(2^{n+1} − (2k − 1)) = n + 2 − S_{2}(2k − 1).  (4.19)

To check this, write 2k − 1 = a_{0} + a_{1} · 2 + ⋯ + a_{r} · 2^{r} with a_{0} = 1 because 2k − 1 is odd. Now, 2^{n+1} = (1 + 2 + 2^{2} + ⋯ + 2^{n}) + 1 implies that

2^{n+1} − (2k − 1) = (2^{n} + 2^{n−1} + ⋯ + 2^{r+1})
+(1 − a_{r}) · 2^{r} + (1 − a_{r+1}) · 2^{r−1} + ⋯ + (1 − a_{1}) · 2 + 1

resulting in

S_{2}(2^{n+1} − (2k − 1)) = n + 1 − (a_{r} + a_{r−1} + ⋯ + a_{1})
= n + 2 − S_{2}(2k − 1).

Therefore

ν_{2}(T (2^{n})) − ν_{2}(T (2^{n} − i)) = (n + 2)i − ∑_{k=1}^{i} S_{2}(2k − 1)−

∑_{k=1}^{i} S_{2}(3 · 2^{n} − (3k − 1)). (4.20)

Similarly

ν_{2}(T (2^{n} + i)) − ν_{2}(T (2^{n})) = ∑_{j=2^{n}+1}^{2^{n}+i} (S_{2}(2j − 1) − S_{2}(3j − 2))

= ∑_{k=1}^{i} (S_{2}(2^{n+1} + 2k − 1) − S_{2}(3 · 2^{n} + 3k − 2)) .

The inequality

2k − 1 ≤ 2i − 1 ≤ 2J_{n−1} − 1 ≤ 2 · 2^{n−1} − 1 ≤ 2^{n} − 1 < 2^{n+1}  (4.21)

shows that S_{2}(2^{n+1} + 2k − 1) = 1 + S_{2}(2k − 1). Also, Lemma 4.1 yields the identity

S_{2}(3 · 2^{n} + 3k − 2) + S_{2}(3 · 2^{n} − 3k + 1) = n + 3.  (4.22)

Therefore

ν_{2}(T (2^{n} + i)) − ν_{2}(T (2^{n})) = ∑_{k=1}^{i} (S_{2}(2^{n+1} + 2k − 1) − S_{2}(3 · 2^{n} + 3k − 2)) + i

+ ∑_{k=1}^{i} S_{2}(2k − 1) − (n + 3 − S_{2}(3 · 2^{n} − 3k + 1)) .

Thus

ν_{2}(T (2^{n})) − ν_{2}(T (2^{n} − i)) = − [ν_{2}(T (2^{n} − i)) − ν_{2}(T (2^{n}))] ,

and symmetry has been established. Note. The identity (4.22) can be given a direct proof by induction on k. It is required to check that the left hand side is independent of k. This follows from the identity

S_{2}(m + 3) − S_{2}(m) = \begin{cases}2 − ω_{2} (\frac{m}{2}) , if m ≡ 0 mod 2; \\ −ω_{2} (⌊\frac{m}{4}⌋) , if m ≡ 1 mod 2; \end{cases}  (4.23)

where ω_{2}(m) is the number of trailing 1’s in the binary expansion of m. For m = 829, S_{3}(829) = 7 and S_{3}(832) = 3. The binary expansion of m = 207 = ⌊829/4⌋ is 11001111 and the number of trailing 1’s is 4. This observation is due to A. Straub. Note. The proof of Theorem 1.3 is now complete. Example. The use of the algorithm is illustrated with the computation of ν_{2}(T (5192)). The number T (5192) has 3, 062, 890 digits and it is never computed.

1. Start with J_{12} = 2731 < 5192 < J_{13} = 5461. The midpoint of [2731, 5461] is 4096.

2. Apply Step 3, to obtain ν_{2}(T (5192)) = ν_{2}(T (3000)).

3. The number 3000 ∈ [J_{12}, J_{12} + 2J_{9}]. Step 4 gives ν_{2}(T (3000)) = 269 + ν_{2}(T (952)).

4. The number 952 ∈ [J_{10} + 2J_{7}, 2^{10}]. Step 5 gives ν_{2}(T (952)) = 170 + ν_{2}(T (440)).

5. The number 440 ∈ [J_{9} + 2J_{6}, 2^{9}]. Step 5 gives ν_{2}(T (440)) = 86 + ν_{2}(T (184)).

6. The number 184 ∈ [J_{8}, J_{8} + 2J_{5}]. Step 4 gives ν_{2}(T (184)) = 13 + ν_{2}(T (56)).

7. The number 56 ∈ [J_{6} + 2J_{3}, 2^{6}]. Step 5 gives ν_{2}(T (56)) = 10 + ν_{2}(T (24)).

8. The number 24 ∈ [J_{5}, J_{5} + 2J_{2}]. Step 4 gives ν_{2}(T (24)) = 3 + ν_{2}(T (8)).

9. The number 8 is a power of 2, so ν_{2}(T (8)) = J_{2} = 3.

Backwards substitution gives ν_{2}(T (5192)) = 554. This can be verified using 2.7.

The construction of ν_{2} ∘ T given in the algorithm following Theorem 1.3 gives the result of Frey and Sellers [6].

Corollary 4.8. The number T (n) is odd if and only if n is a Jacobstahl number.

The next statement deals with the range of ν ∘ T.

Theorem 4.9. The range of ν_{2} ∘ T is ℕ. Furthermore, for each m ∈ ℕ, the equation ν_{2}(T (n)) = m has finitely many solutions, the largest being n = J_{2m+1} − 1.

Proof. The inequality

ν_{2}(T (J_{n} + i)) > ν_{2}(T (J_{n} + 1)) = ν_{2}(T (J_{n+1} − 1)),

for 1 < i < J_{n+1} − J_{n} − 2 and ν_{2}(T (J_{n+2} − 1)) = ν_{2}(T (J_{n} − 1)) + 1, comes from the previous discussion. Therefore the minimum value of ν_{2}(T (n)) around 2^{n} is attained exactly at J_{n} +1 and J_{n+1} −1. These values are also strictly increasing along the even and odd indices. Thus, m < ν_{2}(T (i)) for any given m, provided i is large enough.

To determine the last appearance of m, it is only required to determine the last occurance of n such that ν_{2}(T (J_{n} −1)) = m. Since ν_{2}(T (J_{2} −1)) = ν_{2}(T (J_{3} −1)) = 1, it follows that ν_{2}(T (J_{2n} − 1)) = ν_{2}(T (J_{2n+1} − 1)) = n.

Note. Define λ(m) to be the number of solutions of ν_{2}(T (n)) = m. The values for 1 ≤ m ≤ 8 are shown below.

\begin{matrix}m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ λ(m) & 2 & 8 & 5 & 12 & 5 & 14 & 8 & 14 \end{matrix}

Table 1: The first 8 values in the range of ν_{2} ∘ T

For example, the five solutions to ν(T (n)) = 5 are 16, 342, 682, 684 and J_{11}−1 = 1364 and the eight solutions to ν(T (n)) = 7 are 26, 38, 46, 82, 5462, 10922, 10924 and J_{15} − 1 = 21844.

Note. In sharp contrast to the 2-adic valuation, D. Frey and J. Sellers [7, 8] show that if p ≥ 3 is a prime, the equation ν_{p}(T (n))) = m has infinitely many solutions, for each m ∈ ℕ.

Scaling. The graph of ν_{2}∘T on the interval I_{n} := [ J_{n}, J_{n+1} ] vanishes at the endpoints and it is symmetric about the midpoint 2^{n} where the maximum value J_{n−1} occurs. Figure 3 shows ν_{2}(T (n)) on the interval I_{10} = [341, 683] and Figure 4 depicts the first 15 such graphs, scaled to the unit square.

Figure 3: The 2-adic valuation of T (n) between minima Figure 4: The scaled version of the 2-adic valuation of T (n)

The interval [J_{n}, 2^{n}] ⊂ I_{n} is divided into [J_{n}, J_{n} + 2J_{n−3}] and [J_{n} + 2J_{n−3}, 2^{n}]. Scaling I_{n} to [0, 1] the shifted endpoints of these subintervals are

\{0, \frac{2J_{n−3}}{J_{n+1} − J_{n}} , \frac{2^{n} − J_{n}}{J_{n+1} − J_{n}} \} → \{0, \frac{1}{4}, \frac{1}{2}\} ,  (4.24)

as n → ∞.

The linear interpolation of the function ν_{2} ∘ T on the interval I_{n} = [J_{n}, J_{n+1}] is now scaled to the unit square by

f_{n}(x) = \frac{1}{J_{n−1}} (ν_{2} ∘ T) (J_{n} + (J_{n+1} − J_{n})x) .  (4.25)

The algorithm in Section 1 is now translated into a relation for the functions f_{n}.

Proposition 4.10. The function f_{n} satisfies

f_{n}(x) = \frac{J_{n+1} − J_{n}}{J_{n−1}} x + \frac{J_{n−3}}{J_{n−1}} f_{n−2} (\frac{J_{n+1} − J_{n}}{J_{n−1} − J_{n−2}} x) ,

for 0 ≤ x ≤ \frac{2J_{n−3}}{J_{n+1}−J_{n}} and

f_{n}(x) = \frac{J_{n−2}}{J_{n−1}} f_{n−1} (\frac{J_{n+1} − J_{n}}{J_{n} − J_{n−1}} x − \frac{2J_{n−3}}{J_{n} − J_{n−1}} ) + \frac{2J_{n−3}}{J_{n−1}} ,

for \frac{2J_{n−3}}{J_{n+1}−J_{n}} ≤ x ≤ \frac{J_{n−1}}{J_{n+1}−J_{n}}.

A contraction mapping argument shows that f_{n} converges to the unique function f : [0, 1] → [0, 1] that satisfies

f(x) = \begin{cases}2x + \frac{1}{4}f(4x), & if 0 ≤ x < \frac{1}{4}; \\ \frac{1}{2} + \frac{1}{2}f(2x − \frac{1}{2}), & if \frac{1}{4} ≤ x ≤ \frac{3}{4}; \\ 2(1 − x) + \frac{1}{4}f(4x − 3), & if \frac{3}{4} < x ≤ 1. \end{cases}

This is the function obtained from Figure 1 as the number of points becomes infinite. The details are ommited.

5 The 3-adic valuation of T (n)

The analysis of the 2-adic valuation of T (n) presented in Section 4 is now extended to the prime p = 3. A complete analytic description of Figure 2 is possible. Only the results are given since the arguments are similar to those for p = 2.

The 3-adic expansion of n ∈ ℕ is

n = a_{j} · 3^{j} + a_{j−1} · 3^{j−1} + ⋯ + a_{1} · 3 + a_{0}  (5.1)

is used to define

S_{3}(n) := a_{0} + a_{1} + ⋯ + a_{k}.  (5.2)

The analog of Theorem 1.3 is stated first.

Theorem 5.1. The function ν_{3} ∘ T restricted to the interval K_{n} := [3^{n}, 3^{n+1}] is determined by its restriction to K_{n−1}.

A characterization of the values n for which ν_{3}(T (n)) = 0 is given next.

Theorem 5.2. Let n ∈ ℕ with (5.1) as its expansion in base 3. Then ν_{3}(T (n)) = 0 if and only if there is an index 0 ≤ i ≤ k such that a_{0} = a_{1} = ⋯ = a_{i−1} = 0 and a_{i+1} = a_{i+2} = ⋯ = a_{k} = 0 or 2, with a_{i} arbitrary.

Proposition 2.3 is now written as

ν_{3}(T (n)) = \frac{1}{2} ∑_{j=1}^{n−1} μ_{3}(j),  (5.3)

using the function

μ_{3}(j) := S_{3}(2j) + S_{3}(2j + 1) − S_{3}(3j + 1) − S_{3}(j).  (5.4)

Theorem 5.3. The 3-adic valuation of T (n) satisfies

a) ν_{3}(T (3n)) = 3ν_{3}(T (n)).

b) ν_{3}(T (a)) = ν_{3}(T (2 · 3^{n} + a)) for 0 ≤ a ≤ 3^{n} and

μ_{3}(3^{n} + i) = \{ \begin{matrix}μ_{3}(i) + 2 & if 1 ≤ i < \frac{1}{2}3^{n}, \\ μ_{3}(i) & if i = \frac{1}{2}(3^{n} + 1), \\ μ_{3}(i) − 2 & if \frac{1}{2}3^{n} + 1 < i ≤ 3^{n}, \end{matrix}

for 1 ≤ i < 3^{n}.

c) μ_{3}(3^{n} + i) = −μ_{3}(2 · 3^{n} − i + 1) for 1 ≤ i < \frac{3^{n}}{2} .

The rest of this section contains a procedure to compute ν_{3}(T (n)). Consider the ternary expansion (5.1) and define a sequence of integers {x_{j}, x_{j−1}, ⋯, x_{1}, x_{0}} according to the following rules:

a) the initial term is x_{j} = n.

b) for 1 ≤ i ≤ j, write x_{i} in base 3 with i + 1 digits (a certain number of zeros might have to be placed at the beginning) and let d_{i} be the first digit in this expansion;

c) let t_{i} be the integer obtained by dropping the first digit of the expansion of x_{i} in part b). Then, for 1 ≤ i ≤ j,

x_{i−1} = \begin{cases}t_{i}, & if d_{i} = 0 or 2; \\ Min (t_{i}, 3^{i} − t_{i}) , & if d_{i} = 1. \end{cases}  (5.5)

Theorem 5.4. The sequence defined above satisfies

ν_{3} (T (x_{i})) = \begin{cases}ν_{3} (T (x_{i+1})) , & if d_{i} = 0 or 2; \\ ν_{3} (T (x_{i+1})) − x_{i}, & if d_{i} = 1. \end{cases}

Moreover

ν_{3} (T (n)) = ∑_{d_{i+1}=1} x_{i}.  (5.6)

Observe that the number of 3-adic digits is decreased by 1 in the passage from x_{i} to x_{i−1}. Therefore 0 ≤ x_{1} ≤ 2 and the procedure terminates in a finite number of steps.

Example A symbolic computation shows that ν_{3}(T (1280)) = 180. This is now confirmed using Theorem 5.4. The 3-adic expansion of n = 1280 is [1 2, 0, 2, 1, 0, 2]_{3}. Therefore j = 6 and x_{6} = 1280. The first digit is d_{6} = 1. Dropping it yields t_{6} = [2, 0, 2, 1, 0, 2]_{3} = 551 and x_{5} = Min(551, 3^{6} − 551) = 178. The 3-adic expansion of x_{5} is written as x_{5} = [0 2, 0, 1, 2, 1]_{3}. The extra zero in front is added to have 6 digits in this expansion. This is the first step of the algorithm. The complete

\begin{matrix}i & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ d_{i} & 1 & 0 & 2 & 0 & 1 & 0 & 0 \\ x_{i} & 1280 & 178 & 178 & 16 & 16 & 2 & 2 \end{matrix}

Table 2: The algorithm for ν_{3} ∘ T for n = 1280

sequence is gioven in table 2.

The terms contributing to ν_{3}(T (n)) are those with d_{i+1} = 1, namely i = 5 and i = 1. This gives x_{5} + x_{1} = 178 + 2 = 180.

Example. The value ν_{3}(T (1000)) is computed from the table below. It yields ν_{3}(T (1000)) = x_{5} + x_{4} + x_{2} = 271 + 28 + 1 = 300.

\begin{matrix}i & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ d_{i} & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ x_{i} & 1000 & 271 & 28 & 28 & 1 & 1 & 1 \end{matrix}

Table 3: The algorithm for ν_{3} ∘ T for n = 1000

Theorem 5.4 yields a scaling procedure similar to the one given for p = 2 in Section 4. The resulting limiting function satisfies

f(x) = \begin{cases}\frac{1}{3}f(3x), & if 0 ≤ x ≤ \frac{1}{3}; \\ 4(x − \frac{1}{3}) + \frac{1}{3}f(3x − 1), & if \frac{1}{3} ≤ x ≤ \frac{1}{2}; \\ −4(x − \frac{2}{3}) + \frac{1}{3}f(3x − 1), & if \frac{1}{2} ≤ x ≤ \frac{2}{3}; \\ \frac{1}{3}f(3x − 2), & if \frac{2}{3} ≤ x ≤ 1. \end{cases}

The graph of f corresponds to the limiting behavior of Figure 2.

Note. A similar phenomena is observed for larger primes. The figures show the valuations of T (n) for p = 5 and p = 7 in the range 1 ≤ n ≤ 2000.

6 A generalization

The sequence

T_{p}(n) := ∏_{j=0}^{n−1} \frac{(pj + 1)!}{(n + j)!},  (6.1)

Figure 5: The 5-adic valuation of T (n)  Figure 6: The 7-adic valuation of T (n)

contains T (n) of (1.1) as the special case for p = 3. In this section we present some elementary properties of this generalization.

Theorem 6.1. For a fixed prime p ≥ 3, the numbers T_{p}(n) are integers.

Proof. Start with

T_{p}(n + 1) = T_{p}(n) × y_{p}(n),  (6.2)

where

y_{p}(n) = \frac{(pn + 1)! n!}{(2n + 1)! (2n)!}.  (6.3)

Define

x_{p}(n) := \frac{(pn + 1)!}{((p − 1)n + 1)! n!} = \binom{pn + 1}{n},  (6.4)

and observe that

y_{p}(n) = x_{p}(n) × y_{p−1}(n)n!.  (6.5)

Iterating this argument yields

y_{p}(n) = ∏_{r=0}^{k−1} x_{p−r}(n)y_{p−k}(n).  (6.6)

The choice k = p − 4 yields

y_{p}(n) = \binom{4n + 1}{2n} n!^{p−3} ∏_{r=0}^{p−5} \binom{(p − r)n + 1}{n}.

The upshot is that y_{p}(n) is an integer. The recurrence (6.2) and the initial condition T_{p}(1) = 1 now show that T_{p}(n) is also an integer. The explicit formula

T_{p}(n) = ∏_{j=1}^{n−1} \binom{4j + 1}{2j}j!^{p−3} ∏_{r=0}^{p−5} \binom{(p − r)j + 1}{j}  (6.7)

follows from the recurrence.

Proof. An alternative proof of the fact that y_{p}(n) is an integer was shown to us by Valerio de Angelis. Observe that, for p ≥ 4, we have (pn + 1)! = N × (4n + 1)! for the integer N = (4n + 2)_{(p−4)n}. Therefore

y_{p})(n) = (4n + 2)_{(p−4)n} × \binom{4n + 2}{2n}n!,  (6.8)

shows that y_{p}(n) ∈ ℕ and yields the explicit formula

T_{p}(n) = ∏_{j=1}^{n−1}(4j + 2)_{(p−4)n}\binom{4j + 1}{2j}j!.  (6.9)

Proof. A third proof using Theorem 1.1 was shown to us by T. Amdeberhan. The required inequality states: if n, k, p ∈ ℕ and p ≥ 3, then

ψ_{k}(n; p) := ∑_{j=0}^{n−1} ⌊\frac{pj + 1}{k}⌋ − ∑_{j=0}^{n−1} ⌊\frac{n + j}{k} ⌋ ≥ 0.

It suffices to prove the special case p = 3, i.e. ψ_{k}(n; 3) ≥ 0 which we denote by ψ_{k}(n) for k ≥ 3, n ≥ 1. Write n = ck + r where 0 ≤ r ≤ k − 1. We approach a reduction process by breaking down the respective sums as follows.

∑_{j=0}^{n−1} ⌊\frac{3j + 1}{k}⌋ = ∑_{j=0}^{ck−1} ⌊\frac{3j + 1}{k}⌋ + ∑_{j=0}^{r−1} ⌊\frac{3(ck + j) + 1}{k}⌋

= ∑_{j=0}^{ck−1} ⌊\frac{3j + 1}{k}⌋ + 3cr + ∑_{j=0}^{r−1} ⌊\frac{3j + 1}{k}⌋ ,

and

∑_{j=0}^{n−1} ⌊\frac{n + j}{k} ⌋ = ∑_{j=0}^{ck−1} ⌊\frac{ck + r + j}{k} ⌋ + 2cr + ∑_{j=0}^{r−1} ⌊\frac{r + j}{k} ⌋

= ∑_{j=0}^{ck−1} ⌊\frac{ck + j}{k} ⌋ − ∑_{j=0}^{r−1} ⌊\frac{ck + j}{k} ⌋ + ∑_{j=0}^{r−1} ⌊\frac{2ck + j}{k} ⌋ + 2cr + ∑_{j=0}^{r−1} ⌊\frac{r + j}{k} ⌋

= ∑_{j=0}^{ck−1} ⌊\frac{ck + j}{k} ⌋ + ∑_{j=0}^{r−1} ⌊\frac{ck + j}{k} ⌋ + 2cr + ∑_{j=0}^{r−1} ⌊\frac{r + j}{k} ⌋

= ∑_{j=0}^{ck−1} ⌊\frac{ck + j}{k} ⌋ + cr + ∑_{j=0}^{r−1} ⌊\frac{j}{k} ⌋ + 2cr + ∑_{j=0}^{r−1} ⌊\frac{r + j}{k} ⌋

= ∑_{j=0}^{ck−1} ⌊\frac{ck + j}{k} ⌋ + 3cr + ∑_{j=0}^{r−1} ⌊\frac{r + j}{k} ⌋ .

Combining these expressions, we find that ψ_{k}(ck + r) = ψ_{k}(ck) + ψ_{k}(r). A similar argument with r replaced by k produces ψ_{k}(ck + k) = ψ_{k}(ck) + ψ_{k}(k). We conclude ψ_{k} is k-Euclidean, i.e.

ψ_{k}(ck + r) = cψ_{k}(k) + ψ_{k}(r).

Therefore, we just need to verify the assertion ψ_{k}(r) ≥ 0. In fact, we will strengthen it by giving an explicit formula in vectorial form

[ψ_{k}(0), …, ψ_{k}(k − 1)] = [0, 0^{k′}, 1, 2, …, ⌊k′′/2⌋, ⌈k′′/2⌉, …, 2, 1, 0^{k′}];

where k′ = ⌊\frac{k+1}{3}⌋, k′′ = k − 1 − 2k′ and 0^{k′} means k′ consecutive zeros. This admits an elementary proof. Note that ψ_{k}(ck) = 0, hence ψ_{k} is k-periodic and it satisfies ψ_{k}(ck + r) = ψ_{k}(r).

We now present a recurrence for the p-adic valuation of the sequence T_{p}(n). The special role of the prime p = 3 becomes apparent.

Theorem 6.2. Let p be prime. Then the sequence T_{p}(n) satisfies

ν_{p}(T_{p}(pn)) = pν_{p}(T_{p}(n)) + \frac{1}{2}p(p − 3)n^{2}.  (6.10)

Proof. Start with

T_{p}(pn) = ∏_{j=0}^{pn−1}(pj + 1)!/ ∏_{j=pn}^{2pn−1} j!  (6.11)

and using Legendre’s formula to obtain

(p − 1)ν_{p}(T_{p}(pn)) = ∑_{j=0}^{pn−1} pj + 1 − S_{p}(pj + 1) − ∑_{j=pn}^{2pn−1} j − S_{p}(j).  (6.12)

The terms independent of the function S_{p} add up to n^{2}p(p − 3)/2 so that

ν_{p}(T_{p}(pn)) − pν_{p}(T_{p}(n)) = \frac{1}{2}n^{2}p(p − 3) + \frac{1}{p − 1}W_{p,n},  (6.13)

where

W_{p,n} = − ∑_{j=0}^{pn−1} S_{p}(pj + 1) + ∑_{j=pn}^{2pn−1} S_{p}(j) + p ∑_{j=0}^{n−1} S_{p}(pj + 1) − p ∑_{j=0}^{n−1} S_{p}(n + j). (6.14)

Theresult follows from W_{p,n} = 0. To establish this use S_{p}(pj + 1) = 1 + S_{p}(j) to write

W_{p,n} = − ∑_{j=0}^{pn−1} S_{p}(j) + ∑_{j=pn}^{2pn−1} S_{p}(j) + p ∑_{j=0}^{n−1} S_{p}(j) − p ∑_{j=n}^{2n−1} S_{p}(j).  (6.15)

In the second sum, write j = pr + k with 0 ≤ k ≤ p − 1 and n ≤ r ≤ 2n − 1, to obtain

∑_{j=pn}^{2pn−1} S_{p}(j) = ∑_{k=0}^{p−1} ∑_{r=n}^{2n−1} S_{p}(pr + k)

= ∑_{r=n}^{2n−1} ∑_{k=0}^{p−1} (k + S_{p}(r))

= \frac{n}{2}p(p − 1) + p ∑_{r=n}^{2n−1} S_{p}(r).

This form of the second term is now combined with the fourth one in (6.15). A similar calculation on the first term gives the result. Indeed,

∑_{j=0}^{pn−1} S_{p}(j) = ∑_{k=0}^{p−1} ∑_{r=0}^{n−1} S_{p}(pr + k)

= ∑_{k=0}^{p−1} ∑_{r=0}^{n−1} (k + S_{p}(r))

= \frac{n}{2}p(p − 1) + p ∑_{r=0}^{n−1} S_{p}(r).

Corollary 6.3. For p a prime, we have

ν_{p}(T_{p}(p^{n})) = \frac{p^{n}(p − 3)(p^{n} − 1)}{2(p − 1)}.  (6.16)

Proof. Replace n by p^{n} in the Theorem to obtain

ν_{p}(T_{p}(p^{n+1})) = pν_{p}(T_{p}(p^{n})) + \frac{1}{2}(p − 3)p^{2n+1}.  (6.17)

Iterating this identity yields the result.

Problem. The sequence T_{p}(n) comes as a formal generalization of the original sequence T_{3}(n) that appeared in counting alternating symmetric matrices. This raises the question: what does T_{p}(n) count?

7 Acknowledgments

The authors wish to thank Tewodros Amdeberhan, Valerio de Angelis and A. Straub for many conversations about this paper. Marc Chamberland helped in the experimental discovery of the generalization presented in Section 6. The authors also wish to thank a referee for a very complete and illuminating report on a preliminary version of the paper. This included the ideas behind Theorem 1.4. The work of the second author was partially funded by NSF-DMS 0713836.

References

[1] T. Amdeberhan, D. Manna, and V. Moll. The 2-adic valuation of a sequence arising from a rational integral. J. Combin. Theory Ser. A, 115 (2008), 1474– 1486.

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

[3] D. Bressoud. Proofs and Confirmations: the story of the Alternating Sign Matrix Conjecture. Cambridge University Press, 1999.

[4] D. Bressoud and J. Propp. How the alternating sign matrix conjecture was solved. Notices Amer. Math. Soc., 46 (1999), 637–646.

[5] D. Cartwright and J. Kupka. When factorial quotients are integers. Austral. Math. Soc. Gaz., 29 (2002), 19–26.

[6] D. Frey and J. Sellers. Jacobsthal numbers and alternating sign matrices. J. Integer Sequences, 3 (2000), Article 00.2.3.

[7] D. Frey and J. Sellers. On powers of 2 dividing the values of certain plane partitions. J. Integer Sequences, 4 (2001), Article 01.1.8.

[8] D. Frey and J. Sellers. Prime power divisors of the number of n × n Alternating Sign Matrices. Ars Combin., 71 (2004), 139–147.

[9] A. M. Legendre. Theorie des Nombres. Firmin Didot Freres, Paris, 1830.

[10] D. Manna and V. Moll. A remarkable sequence of integers. To appear, Expo. Math., 2009.

[11] W. H. Mills, D. P. Robbins, and H. Rumsey. Proof of the MacDonald conjecture. Inv. Math., 66 (1982), 73–87.

[12] D. Zeilberger. Proof of the Alternating Sign Matrix conjecture. Electronic J. Combin., 3 (2) (1996), Paper #R13. Electronic version at

    http://www.combinatorics.org/Volume 3/Abstracts/v3i2r13.html.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 11B75, 11Y55. Keywords: Alternating sign matrices, Jacobsthal numbers, valuations.

(Concerned with sequences \underline{A005130} and \underline{A001045}.)

Received January 28 2009; revised version received April 27 2009. Published in Journal of Integer Sequences, April 30 2009.

Return to Journal of Integer Sequences home page.