The p-adic Valuation of the ASM Numbers

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

                  ebeyerst@tulane.edu
                    vhm@tulane.edu

Xinyu Sun Department of Mathematics Xavier University of Louisiana New Orleans, LA 70125 USA

                     xsun@xula.edu

Abstract

A classical formula of Legendre gives the p-adic valuation for factorials as a finite sum of values of the floor function. This expression can be used to produce a formula for the p-adic valuation of n as a finite sum of periodic functions. An analogous result is established for the p-adic valuation of the ASM numbers. This sequence counts the number of alternating sign matrices.

1 Introduction

Let n ∈ ℕ and p be a prime. The highest power of p that divides n, called the p-adic valuation of n, is denoted by ν_{p}(n). The elementary formula

ν_{p}(n!) = ∑_{j=1}^{∞} ⌊\frac{n}{p^{j}} ⌋  (1)

is a classical result which appears in most texts in number theory. Observe that, for each fixed value of n, there are only finitely many non-zero terms in (1). An alternative form was given by Legendre [3] in the form

ν_{p}(n!) = \frac{n − S_{p}(n)}{p − 1},  (2)

where S_{p}(n) denotes the sum of the digits of n in base p.

The formula (1) can be used to express the p-adic valuation of n as

ν_{p}(n) = ∑_{j=1}^{∞} (⌊\frac{n}{p^{j}} ⌋ − ⌊\frac{n − 1}{p^{j}}⌋) .  (3)

Each summand in (3) is a periodic function of period p^{j}.

The goal of this paper is to describe the p-adic valuations of a sequence that count a famous class of matrices. The special cases p = 2 and 3 have been described in [4]. This paper extends, to arbitrary primes p, the interesting patterns found in [4].

An alternating sign matrix is an array of 0, 1 and −1, such that the entries of each row and column add up to 1 and the non-zero entries of a given row/column alternate. After a fascinating sequence of events, D. Zeilberger [5] proved that the numbers of such matrices is given by

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

In particular, the numbers A_{n} are integers: not an obvious fact. They are called the ASM numbers and form sequence \underline{A005130} in Sloane’s Encylopedia.

The story behind this formula and its many combinatorial interpretations are given in D. Bressoud’s book [1].

The main result presented here is a formula for the p-adic valuation of A_{n} similar to (3).

Theorem 1. Let n ∈ ℕ and p ≥ 5 be a prime. Define

Per_{j,p}(n) = \begin{cases}0, & if 0 ≤ n ≤ ⌊\frac{p^{j}+1}{3}⌋; \\ n − ⌊\frac{p^{j}+1}{3}⌋ , & if ⌊\frac{p^{j}+1}{3}⌋ + 1 ≤ n ≤ \frac{p^{j}−1}{2}; \\ ⌊\frac{2p^{j}+1}{3}⌋ − n, & if \frac{p^{j}+1}{2} ≤ n ≤ ⌊\frac{2p^{j}+1}{3}⌋; \\ 0, & if ⌊\frac{2p^{j}+1}{3}⌋ + 1 ≤ n ≤ p^{j} − 1. \end{cases}  (5)

Then

ν_{p}(A_{n}) = ∑_{j=1}^{∞} Per_{j,p} (n mod p^{j}) .  (6)

Observations.

1) For a fixed prime p, define r = r(n, p) by the inequalities p^{r} ≤ n < p^{r+1}. Then n = ⌊log n/ log p⌋. The number n admits a representation n = up^{r} + v, with 1 ≤ u ≤ p − 1 and 0 ≤ v ≤ p^{r} − 1. The index u is given by u = ⌊n/p^{r}⌋.

2) The j-th term in the series (6) is a periodic function of period p^{j}.

3) For fixed n ∈ ℕ, the series (6) reduces to a finite sum. Indeed, with r as above,

⌊\frac{p^{r+2} + 1}{3}⌋ ≥ \frac{p^{r+2} + 1}{3} − 1 ≥ p^{r+1} > n  (7)

so the sum ends after j = r + 1.

4) The form of the series (6) was found empirically. It would be desirable to develop a method that gives a series of this type for a large class of sequences. The goal is to produce an expansion of the form

ν_{p}(a_{n}) = ∑_{j=1}^{∞} α_{j,n}ϕ_{j,p}(n)  (8)

where ϕ_{j,p} is a function of period p^{j}. A procedure to determine the coefficients α_{j,n} directly from the sequence {a_{n}} and the functions {ϕ_{j,p}} should be developed. Moreover, it is required that, for fixed n ∈ ℕ, the series (8) contains only finitely non-vanishing terms.

5) The authors of [2] present an analytic formula for ν_{p}(A_{n}) from which they obtain the asymptotic behavior of this function. A Fourier-series based approach is presented which reveals the dominant terms and also periodic fluctuations. A study of the expressions discussed in this paper and the results in [2] will be reported later.

The proof of the theorem is based on the observation that ν_{p}(A_{1}) = 0 and Per_{j,p}(1) = 0, showing that both sides of (6) agree at n = 1 coupled with recurrences satisfied by ν_{p}(A_{n}) and Per_{j,p}(n). These are given by

ν_{p}(A_{n}) − ν_{p}(A_{n−1}) = \frac{1}{p − 1} (S_{p}(2n − 2) + S_{p}(2n − 1) − S_{p}(3n − 2) − S_{p}(n − 1)) (9)

and

Per_{j,p}(n) − Per_{j,p}(n − 1) = \begin{cases}0, & if 0 ≤ n ≤ ⌊\frac{p^{j}+1}{3}⌋; \\ 1, & if ⌊\frac{p^{j}+1}{3}⌋ + 1 ≤ n ≤ \frac{p^{j}−1}{2}; \\ 0, & if n = \frac{p^{j}+1}{2}; \\ −1, & if \frac{p^{j}+3}{2} ≤ n ≤ ⌊\frac{2p^{j}+1}{3}⌋; \\ 0, & if ⌊\frac{2p^{j}+1}{3}⌋ + 1 ≤ n ≤ p^{j} − 1. \end{cases}  (10)

The proof shows that the right-hand side of (9) matches that of (10).

The study of the arithmetic aspects of the sequence A_{n} was initiated in [4], where the case of ν_{2}(A_{n}) was considered. It is shown that ν_{2}(A_{n}) vanishes precisely when n is a Jacobstahl number J_{m}. These numbers are defined by the recurrence J_{m} = J_{m−1} + 2J_{m−2} with initial conditions J_{0} = 1 and J_{1} = 1. The main result is the existence of a well-defined algorithm to produce the graph of ν_{2}(A_{n}) on the interval [J_{m}, J_{m+1}] from its value on the two previous intervals [J_{m−2}, J_{m−1}] ∪ [J_{m−1}, J_{m}]. In the situation considered here, the partial sums of the series (6) give approximations to ν_{p}(A_{n}).

Section 2 describes data that motivated the main theorem. Section 3 establishes the recurrence for the valuation of A_{n} and Section 4 the corresponding recurrence for the function Per_{j,p}. Section 5 presents the proof of the main result.

2 An experimental illustration of the main theorem

In this section the procedure employed to find the main result is described in the case of the valuation ν_{p}(A_{n}) for p = 5. The first 100 values of ν_{5}(A(n)) are given below (each row is of length 10)

0 0 0 0 0 0 0 0 1 2
3 4 4 3 2 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 3 4 4 3 2
1 0 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 18 20
22 24 24 22 20 18 16 15 14 13
12 11 10 9 8 7 6 5 4 3
2 1 0 1 2 3 4 4 3 2
1 0 0 0 0 0 0 0 0 0

Figure 1: The 5-adic valuation of A_{n}

The observation employed to find the main theorem is based on the string

0 0 0 0 0 0 0 0 1 2 3 4 4 3 2 1 0 0 0 0 0 0 0 0 0  (1)

and its central role in the function ν_{2}(n). An analytic expression for the string is given by

Per_{2,5}(n) := \begin{cases}0, & if 0 ≤ n ≤ 8; \\ n − 8, & if 9 ≤ n ≤ 12; \\ 17 − n, & if 13 ≤ n ≤ 16; \\ 0, & if 17 ≤ n ≤ 24; \end{cases}  (2)

and this is now extended to a periodic function of period 5^{2} by Per_{2,5}(n mod 5^{2}).

The function

ν_{5}(A_{n}) − Per_{2,5}(n mod 5^{2})  (3)

has values given by

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 17 18
19 20 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3
2 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

This data suggests the function

Per_{3,5}(n) := \begin{cases}0, & if 0 ≤ n ≤ 42; \\ n − 42, & if 43 ≤ n ≤ 62; \\ 83 − n, & if 63 ≤ n ≤ 82; \\ 0, & if 83 ≤ n ≤ 124; \end{cases}  (4)

and extend Per_{3,5} to a periodic function of period 5^{3}. This empirical procedure leads to the functions Per_{j,p}(n) defined Theorem 1.

3 An analytic formula

For a prime p, introduce the notation

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

Lemma 2. Let p be a prime. Then the p-adic valuation of A_{n} satisfies

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

Proof. This follows directly by combining the initial value A_{1} = 1 with the expression

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

and the corresponding one for ν_{p}(A_{n−1}).

Legendre’s formula (2) gives the result of Theorem 2 in terms of the function S_{p}.

Corollary 3. The p-adic valuation of A_{n} is given by

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

Summing the recurrence (2) and using A_{1} = 1 we obtain an alternative expression for the p-adic valuation of A_{n}.

Proposition 4. The p-adic valuation of A_{n} is given by

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

This gives a recurrence for the p-adic valuation of A_{n}.

Theorem 5. The p-adic valuation of A_{n} satisfies

ν_{p}(A_{n}) − ν_{p}(A_{n−1}) = \frac{1}{p − 1} (S_{p}(2n − 2) + S_{p}(2n − 1) − S_{p}(3n − 2) − S_{p}(n − 1)) .

4 The recurrence for Per_{j,p}(n)

The explicit formulas for Per_{j,p}(n) can be used to give a proof of (10). The only cases that require special attention are when n and n − 1 are on different intervals of the definition. For instance, if n = ⌊\frac{p^{j}+1}{3}⌋ + 1, then Per_{j,p}(n) = n − ⌊\frac{p^{j}+1}{3}⌋ = 1 and Per_{j,p}(n − 1) = 0. The verification of all the cases is elementary.

5 The proof of the main theorem

Introduce the notation

L_{1}(n, p) = S_{p}(2n − 2) + S_{p}(2n − 1) − S_{p}(3n − 2) − S_{p}(n − 1),  (1)

with the convention that S_{p}(x) = 0 if x < 0 and

L_{2}(n, p) = ∑_{j=1}^{∞} g_{j}(n, p)  (2)

where

g_{j}(n, p) = \begin{cases}0, & if 0 ≤ n mod p^{j} ≤ ⌊\frac{p^{j}+1}{3}⌋; \\ p − 1, & if ⌊\frac{p^{j}+1}{3}⌋ + 1 ≤ n mod p^{j} ≤ \frac{p^{j}−1}{2}; \\ 0, & if n mod p^{j} = \frac{p^{j}+1}{2}; \\ −(p − 1) & if \frac{p^{j}+3}{2} ≤ n mod p^{j} ≤ ⌊\frac{2p^{j}+1}{3}⌋; \\ 0, & if ⌊\frac{2p^{j}+1}{3}⌋ + 1 ≤ n mod p^{j} ≤ p^{j} − 1. \end{cases}  (3)

The statement of the main theorem is the identity

L_{1}(n, p) = L_{2}(n, p) for n ∈ ℕ.  (4)

The proof is achieved by induction on the number of digits in the expansion of n in base p. Write n = up^{r} + v, with 1 ≤ u ≤ p − 1 and 0 ≤ v ≤ p^{r} − 1. The base case shows that L_{1}(n, p) = L_{2}(n, p) for 1 ≤ n ≤ p − 1 and the inductive step is based on the identities L_{1}(n, p) = L_{1}(v, p) + E(n, p) and L_{2}(n, p) = L_{2}(n, p) + E(n, p), with the same function E in both cases. This completes the proof.

Observe that, for fixed n ∈ ℕ, the series in (2) is actually a finite sum. Terms with index j ≥ 2 + ⌊log n/ log p⌋ vanish. Thus, if p^{r} ≤ n < p^{r+1},

L_{2}(n, p) = ∑_{j=1}^{r+1} g_{j}(n, p).  (5)

The proof of (4) is by induction on the number of digits of n in base p. The basic case is considered first: it deals with n ∈ ℕ that have a single digit; that is, 1 ≤ n ≤ p − 1.

• Base case. Assume that 1 ≤ n ≤ p − 1.

The bound p ≥ 5 implies that for j ≥ 2

1 ≤ n ≤ p − 1 < \frac{p^{2} − 2}{3} ≤ ⌊\frac{p^{j} + 1}{3}⌋ .  (6)

It follows that the sum in (2) contains a single term. It is required to show that

L_{1}(n, p) = \begin{cases}0, & if 0 ≤ n ≤ ⌊\frac{p+1}{3}⌋; \\ p − 1, & if ⌊\frac{p+1}{3}⌋ + 1 ≤ n ≤ \frac{p−1}{2}; \\ 0, & if n = \frac{p+1}{2}; \\ 1 − p, & if \frac{p+3}{2} ≤ n ≤ ⌊\frac{2p+1}{3}⌋; \\ 0, & if ⌊\frac{2p+1}{3}⌋ + 1 ≤ n ≤ p − 1. \end{cases}  (7)

This identity is verified by considering the position of n in [0, p − 1].

Case 1.1. Observe that 3n − 2 < p is equivalent to n ≤ ⌊\frac{p+1}{3}⌋. Under this condition the terms 2n − 2, 2n − 1, 3n − 2 and n − 1 have a single digit in base p. Therefore

L_{1}(n, p) = (2n − 2) + (2n − 1) − (3n − 2) − (n − 1) = 0.  (8)

Case 1.2. Assume ⌊\frac{p+1}{3}⌋ < n ≤ \frac{p−1}{2}. Then 2n − 2 < 2n − 1 ≤ p − 2 and p ≤ 3n − 2 < 2p. Therefore the numbers 2n−2, 2n−1 and n−1 have a single digit in base p. The representation of 3n − 2 is 3n − 2 = 1 · p + (3n − 2 − p). It follows that S_{p}(2n − 2) = 2n − 2, S_{p}(2n − 1) = 2n − 1, S_{p}(n − 1) = n − 1, and S_{p}(3n − 2) = 3n − p − 1. The identity (7) follows from these values.

Case 1.3. If n = \frac{p+1}{2}, then the terms involved in (7) are

S_{p}(2n − 2) = p − 1, S_{p}(2n − 1) = 1, S_{p}(3n − 2) = 1 + (3n − 2 − p) and S_{p}(n − 1) = n − 1.

The identity (7) follows from these values.

The remaining cases can be obtained by similar arguments. The proof of (7) is now complete establishing the base case of the main theorem.

• Inductive step. For fixed n ∈ ℕ, recall that r ∈ ℕ is defined by the inequalities p^{r} ≤ n < p^{r+1}; that is,

r = ⌊\frac{log n}{log p}⌋ .  (9)

Write n = up^{r} + v, with 1 ≤ u < p and 0 ≤ v ≤ p^{r} − 1. The main step of the proof is to produce a reduction formula that relates L_{1}(n, p) to L_{1}(v, p).

The next lemma illustrates one case in complete detail. The common assumption is that n ∈ ℕ satisfies p^{r} ≤ n < p^{r+1}. By convention, S_{p}(n) = 0 if n < 0.

Lemma 6. For n ∈ ℕ,

S_{p}(2n − 2) = S_{p}(2v − 2) + T_{1}(n, p)  (10)

where T_{1}(n, p) is given in the table below.

\begin{matrix}v & u & T_{1}(n, p) \\ v = 0 & 1 ≤ u ≤ \frac{p−1}{2} & 2u − 2 + r(p − 1) \\ v = 0 & \frac{p+1}{2} ≤ u ≤ p − 1 & 2u − p − 1 + r(p − 1) \\ 1 ≤ v ≤ \frac{p^{r}+1}{2} & 1 ≤ u ≤ \frac{p−1}{2} & 2u \\ 1 ≤ v ≤ \frac{p^{r}+1}{2} & \frac{p+1}{2} ≤ u ≤ p − 1 & 2u − p + 1 \\ \frac{p^{r}+3}{2} ≤ v ≤ p^{r} − 1 & 1 ≤ u ≤ \frac{p−3}{2} & 2u \\ \frac{p^{r}+3}{2} ≤ v ≤ p^{r} − 1 & \frac{p−1}{2} ≤ u ≤ p − 1 & 2u − p + 1 \end{matrix}

The values of T_{1}(n, p).

Proof. Start with 2n − 2 = 2up^{r} + 2v − 2. The discussion of S_{p}(2n − 2) is divided into cases according to 2v − 2.

Case 1: v = 0. Then 2n − 2 = 2up^{r} − 2 = (2u − 1)p^{r} + (p^{r} − 2). The term p^{r} − 2 does not contribute to the power p^{r} and the bounds 1 ≤ 2u − 1 ≤ 2p − 3 yield two separate cases:

SubCase 1.1: 1 ≤ 2u − 1 ≤ p − 1. In this case S_{p}(2u − 1) = 2u − 1 and it follows that

S_{p}(2n − 2) = 2u − 1 + S_{p}(p^{r} − 2).  (11)

The identity

p^{r} − 2 = (p − 2) + (p − 1)p + (p − 1)p^{2} + ⋯ (p − 1)p^{r−1}  (12)

produces S_{p}(p^{r} − 2) = r(p − 1) − 1. Therefore

S_{p}(2n − 2) = 2u − 2 + r(p − 1).  (13)

SubCase 1.2: p ≤ 2u − 1 ≤ 2p − 3. The expression

2n − 2 = (2u − 1)p^{r} + (p^{r} − 2)
= p^{r+1} + (2u − 1 − p)p^{r} + (p^{r} − 2)

gives

S_{p}(2n − 2) = 1 + (2u − 1 − p) + S_{p}(p^{r} − 2)
= (2u − p − 1) + r(p − 1).

This completes the case v = 0. Case 2. This considers the situation where 0 < 2v − 2 < p^{r}. Then the representation of 2v − 2 in base p does not produce carries to the position of p^{r}. The discussion of

2n − 2 = 2up^{r} + 2v − 2  (14)

is divided, as before, into two subcases according to the value of 2u. SubCase 2.1.: 1 ≤ 2u ≤ p − 1. Then (14) gives

S_{p}(2n − 2) = 2u + S_{p}(2v − 2).  (15)

SubCase 2.2: p ≤ 2u ≤ 2p − 1. Equation (14) is now written as

2n − 2 = p^{r+1} + (2u − p)p^{r} + (2v − 2).  (16)

It follows from here that S_{p}(2n − 2) = 1 + (2u − p) + S_{p}(2v − 2). Case 3. The last possibility is p^{r} ≤ 2v − 2 < 2p^{r}. The expression

2n − 2 = (2u + 1)p^{r} + (2v − 2 − p^{r})  (17)

leads to two subcases: SubCase 3.1: 2u + 1 ≤ p − 1. Then 2u + 1 < p and S_{p}(2n − 2) = 2u + 1 + S_{p}(2v − 2 − p^{r}). Now, from 2v − 2 = p^{r} + (2v − 2 − p^{r}), it follows that S_{p}(2v − 2 − p^{r}) = S_{p}(2v − 2) − 1. Therefore S_{p}(2n − 2) = 2u + S_{p}(2v − 2). SubCase 3.2: p ≤ 2u + 1 ≤ 2p − 1. Proceeding as before gives S_{p}(2n − 2) = 2u − p + 1 + S_{p}(2v − 2). All the cases have now been considered and the proof is complete.

The other terms appearing in the expression for L_{1} have similar reductions. These are stated next. The proofs are ommitted since they are similar to the one presented above.

Lemma 7. Let n ∈ ℕ. Then S_{p}(2n − 1) = S_{p}(2v − 1) + T_{2}(n, p) where T_{2}(n, p) is given in the table below.

\begin{matrix}v & u & T_{2}(n, p) \\ v = 0 & 1 ≤ u ≤ \frac{p−1}{2} & 2u − 1 + r(p − 1) \\ v = 0 & \frac{p+1}{2} ≤ u ≤ p − 1 & 2u − p + r(p − 1) \\ 1 ≤ v ≤ \frac{p^{r}−1}{2} & 1 ≤ u ≤ \frac{p−1}{2} & 2u \\ 1 ≤ v ≤ \frac{p^{r}−1}{2} & \frac{p+1}{2} ≤ u ≤ p − 1 & 2u − p + 1 \\ \frac{p^{r}+1}{2} ≤ v ≤ p^{r} − 1 & 1 ≤ u ≤ \frac{p−3}{2} & 2u \\ \frac{p^{r}+1}{2} ≤ v ≤ p^{r} − 1 & \frac{p−1}{2} ≤ u ≤ p − 1 & 2u − p + 1 \end{matrix}

The values of T_{2}(n, p).

Lemma 8. Let n ∈ ℕ. Then S_{p}(n − 1) = S_{p}(v − 1) + T_{3}(n, p) where T_{3}(n, p) is given below.

\begin{matrix}v & T_{3}(n, p) \\ v = 0 & u − 1 + r(p − 1) \\ 1 ≤ v ≤ p^{r} − 1 & u \end{matrix}

The values of T_{3}(n, p).

Lemma 9. Let n ∈ ℕ. Then S_{p}(3n − 2) = S_{p}(3v − 2) + T_{4}(n, p) where T_{4}(n, p) is given in the table below.

\begin{matrix}v & u & T_{4}(n, p) \\ v = 0 & 2 ≤ 3u − 1 ≤ p − 1 & 3u − 2 + r(p − 1) \\ v = 0 & p ≤ 3u − 1 ≤ 2p − 1 & 3u − p − 1 + r(p − 1) \\ v = 0 & 2p ≤ 3u − 1 ≤ 3p − 4 & 3u − 2p + r(p − 1) \\ 1 ≤ 3v − 2 ≤ p^{r} − 1 & 1 ≤ 3u ≤ p − 1 & 3u \\ 1 ≤ 3v − 2 ≤ p^{r} − 1 & p ≤ 3u ≤ 2p − 1 & 3u − p + 1 \\ 1 ≤ 3v − 2 ≤ p^{r} − 1 & 2p ≤ 3u ≤ 3p − 3 & 3u − 2p + 2 \\ p^{r} ≤ 3v − 2 ≤ 2p^{r} − 1 & 1 ≤ 3u + 1 ≤ p − 1 & 3u \\ p^{r} ≤ 3v − 2 ≤ 2p^{r} − 1 & p ≤ 3u + 1 ≤ 2p − 1 & 3u − p + 1 \\ p^{r} ≤ 3v − 2 ≤ 2p^{r} − 1 & 2p ≤ 3u + 1 ≤ 3p − 2 & 3u − 2p + 2 \\ 2p^{r} ≤ 3v − 2 ≤ 3p^{r} − 1 & 1 ≤ 3u + 2 ≤ p − 1 & 3u \\ 2p^{r} ≤ 3v − 2 ≤ 3p^{r} − 1 & p ≤ 3u + 2 ≤ 2p − 1 & 3u − p + 1 \\ 2p^{r} ≤ 3v − 2 ≤ 3p^{r} − 1 & 2p ≤ 3u + 2 ≤ 3p − 1 & 3u − 2p + 1 \end{matrix}

The values of T_{4}(n, p).

Corollary 10. The information given above, shows that

L_{1}(n, p) = L_{1}(v, p) + [T_{1}(n, p) + T_{2}(n, p) − T_{3}(n, p) − T_{4}(n, p)] .  (18)

The next step is to obtain a relation between L_{2}(n, p) and L_{2}(v, p).

Recall that r is defined by p^{r} ≤ n < p^{r+1}. It follows that the inequality p^{r+1} < ⌊(p^{j} + 1)/3⌋ holds for j ≥ r + 2, yielding

n mod p^{j} = n < p^{r+1} < ⌊(p^{j} + 1)/3⌋ .  (19)

Thus the corresponding term in (2) vanishes. For indices 1 ≤ j ≤ r, the relation n = up^{r} +v, gives n mod p^{j} = v mod p^{j}. Therefore L_{2}(n, p) and L_{2}(v, p) differ only in the last term. Morever, the bound n < p^{r+1} implies that n mod p^{r+1} is simply n. These observations are recorded in the next proposition.

Proposition 11. Let n ∈ ℕ. Recall the definition r = r(n, p) := ⌊log n/ log p⌋, so that p^{r} ≤ n < p^{r+1}. Then, the identity

L_{2}(n, p) = L_{2}(v, p) + g_{r+1}(n, p)  (20)

holds, with

g_{r+1}(n, p) = \begin{cases}0, & if 0 ≤ n ≤ ⌊\frac{p^{r+1}+1}{3}⌋; \\ p − 1, & if ⌊\frac{p^{r+1}+1}{3}⌋ + 1 ≤ n ≤ \frac{p^{r+1}−1}{2}; \\ 0, & if n = \frac{p^{r+1}+1}{2}; \\ −(p − 1) & if \frac{p^{r+1}+3}{2} ≤ n ≤ ⌊\frac{2p^{r+1}+1}{3}⌋; \\ 0, & if ⌊\frac{2p^{r+1}+1}{3}⌋ + 1 ≤ n ≤ p^{r+1} − 1. \end{cases}  (21)

The next result completes the proof of the main theorem.

Theorem 12. With the notations established above

T_{1}(n, p) + T_{2}(n, p) − T_{3}(n, p) − T_{4}(n, p) = g_{r+1}(n, p).  (22)

Proof. The proof is presented in detail for the case ⌊(p^{r+1} + 1)/3⌋ + 1 ≤ n ≤ (p^{r+1} − 1)/2. The other cases are similar.

From the representation n = up^{r} + v and the bounds considered above, it follows that

0 ≤ v ≤ p^{r} − 1 and p ≤ 3u + Spill(3v − 2) ≤ \frac{3}{2}(p − 1).  (23)

Assume that v > 0. The case v = 0 can be treated by similar methods. The spill of 3v − 2 is defined as the contribution of 3v − 2 to the power p^{r} in its expansion on base p. The bounds −2 ≤ 3v − 2 < 3p^{r} shows that the spill is between 0 and 2. The details are given for the case where the spill is 0. The analysis for the case of spill 1 and 2 is analogous.

If the spill is 0, then 0 ≤ 3v − 2 ≤ p^{r} − 1 and p ≤ 3u ≤ 2p − 1. The table of values for T_{4} gives T_{4}(n, p) = 3u − p + 1. The bound n ≤ \frac{1}{2}(p^{r+1} − 1) = \frac{p−1}{2}p^{r} + \frac{1}{2}(p^{r} − 1) imply that u ≤ \frac{p−1}{2}. Since the spill of 3v − 2 is 0 it follows that 3v ≤ p^{r} + 1. Now, p ≥ 5, therefore v ≤ \frac{1}{3}(p^{r} + 1) ≤ \frac{1}{2}(p^{r} − 1). This gives T_{1}(n, p) = 2u, T_{2}(n, p) = 2u and T_{3}(n, p) = u. The result is

T_{1}(n, p) + T_{2}(n, p) − T_{3}(n, p) − T_{4}(n, p) = 2u + 2u − [u + 3u − p + 1] = p − 1.

This is the value of g_{r+1}(n, p). The remaining cases follow the same pattern.

The main theorem has now been established.

6 Acknowledgements

The second author wishes to thank the partial support of NSF-DMS 0713836. The work of the first author was also funded, as a graduate student, by the same grant.

References

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

[2] C. Heuberger and H. Prodinger. A precise description of the p-adic valuation of the number of alternating sign matrices. Int. J. Number Theory, 7 (2011), 57–69.

[3] A. M. Legendre. Théorie des Nombres. Firmin Didot Frères, Paris, 1830.

[4] X. Sun and V. Moll. The p-adic valuation of sequences counting alternating sign matrices. J. Integer Seq., 12 (2009), Article 09.3.8.

[5] D. Zeilberger. Proof of the alternating sign matrix conjecture. Electron. J. Combin., 3 (1996), 1–78.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 11B75, 11Y55 Keywords: Alternating sign matrices, valuations, recurrences, digit count.

(Concerned with sequence \underline{A005130}.)

Received February 3 2011; revised version received July 18 2011; September 8 2011. Published in Journal of Integer Sequences, October 16 2011.

Return to Journal of Integer Sequences home page.