<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{epsfig}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf The $p$-adic Valuation of the ASM Numbers}
\vskip 1cm
\large
Erin Beyerstedt and Victor H. Moll \\
Department of Mathematics\\
Tulane University \\
New Orleans, LA 70118 \\
USA \\
\href{mailto:ebeyerst@tulane.edu}{\tt ebeyerst@tulane.edu}\\
\href{mailto:vhm@tulane.edu}{\tt vhm@tulane.edu} \\
\ \\
Xinyu Sun\\
Department of Mathematics\\
Xavier University of Louisiana\\
New Orleans, LA 70125 \\
USA \\
\href{mailto:xsun@xula.edu}{\tt xsun@xula.edu} \\
\end{center}

\vskip .2 in


\begin{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.
\end{abstract}

\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\im}{\mbox{\upshape Im}}

\newcommand{\stirlings}[2]{\genfrac\{\}{0pt}{}{#1}{#2}}
\newcommand{\stirlingf}[2]{\genfrac[]{0pt}{}{#1}{#2}}

\section{Introduction} \label{sec-intro}
\setcounter{equation}{0}

Let $n \in \mathbb{N}$ and $p$ be a prime. The highest power of $p$ that 
divides $n$, called the {\em $p$-adic valuation of $n$}, is denoted by 
$\nu_{p}(n)$. The elementary formula
\begin{equation}
\nu_{p}(n!) = \sum_{j=1}^{\infty} 
\left\lfloor \frac{n}{p^{j}} \right\rfloor
\label{series-1}
\end{equation}
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 (\ref{series-1}). An 
alternative form was given by Legendre 
\cite{legendre1} in the form
\begin{equation}
\nu_{p}(n!) = \frac{n- S_{p}(n)}{p-1},
\label{leg-11}
\end{equation}
where $S_{p}(n)$ denotes the sum of the digits of $n$ in base $p$. 

The formula \eqref{series-1} can be used to express the $p$-adic valuation 
of $n$ as 
\begin{equation}
\nu_{p}(n) = \sum_{j=1}^{\infty} 
\left( \left\lfloor \frac{n}{p^{j}} \right\rfloor 
- \left\lfloor \frac{n-1}{p^{j}} \right\rfloor 
\right).
\label{series-2}
\end{equation}
Each summand in \eqref{series-2} is a periodic function of period $p^{j}$. 

\medskip

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 \cite{moll-sun1}. This paper 
extends, to arbitrary primes $p$, the interesting patterns found in 
\cite{moll-sun1}.

An {\em 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 \cite{zeilberger96} proved that the numbers of such matrices is 
given by 
\begin{equation}
A_{n} = \prod_{j=0}^{n-1} \frac{(3j+1)!}{(n+j)!}. 
\end{equation}
In particular, the numbers $A_{n}$ are integers: not an obvious fact.  They
are called the ASM numbers and form sequence \seqnum{A005130} in Sloane's
{\it Encylopedia}.

The story behind this formula and its many combinatorial interpretations 
are given in D. Bressoud's book \cite{bressoud1}.

The main result presented here is a formula for the $p$-adic valuation of 
$A_{n}$ similar to \eqref{series-2}.

\begin{theorem}
\label{thm-main}
Let $n \in \mathbb{N}$ and $p \geq 5$ be a prime. Define 
\begin{equation}
\text{Per}_{j,p}(n) = 
\begin{cases}
0,  &amp; \quad \text{ if }  \quad 0 \leq n \leq 
\left\lfloor \frac{p^{j}+1}{3} \right\rfloor;  \\
n - \left\lfloor \frac{p^{j}+1}{3} \right\rfloor,
 &amp; \quad \text{ if } \quad  
\left\lfloor \frac{p^{j}+1}{3} \right\rfloor  
+1 \leq n \leq \frac{p^{j}-1}{2}; \\
\left\lfloor \frac{2p^{j}+1}{3} \right\rfloor  - n,
 &amp; \quad \text{ if } \quad  
\frac{p^{j}+1}{2} \leq  n \leq 
\left\lfloor \frac{2p^{j}+1}{3} \right\rfloor;   \\
0, &amp; \quad \text{ if } \quad  
\left\lfloor \frac{2p^{j}+1}{3} \right\rfloor  +1 \leq n \leq p^{j}-1. 
\end{cases}
\end{equation}
Then 
\begin{equation}
\nu_{p}(A_{n}) = \sum_{j=1}^{\infty} \text{Per}_{j,p} 
\left(n \,\bmod p^{j} \right).
\label{series-0}
\end{equation}
\end{theorem}

\noindent {\bf Observations}. 

\medskip

\noindent 
1) For a fixed prime $p$, define $r = r(n,p)$ by the inequalities 
$p^{r} \leq n &lt; p^{r+1}$. Then $n = \left\lfloor \log n / \log p \right\rfloor$.
The number $n$ admits a representation $n = up^{r} + v$, with $1 \leq u 
\leq p-1$ and $0 \leq v \leq p^{r}-1$.  The index $u$ is given by 
$u = \left \lfloor n/p^{r} \right \rfloor$. 

\medskip

\noindent
2) The $j$-th term in the series \eqref{series-0} 
is a periodic function of period $p^{j}$. 

\medskip

\noindent
3) For fixed $n \in \mathbb{N}$, the series \eqref{series-0} reduces to a
finite sum. Indeed, with $r$ as above, 
\begin{equation}
\left\lfloor \frac{p^{r+2}+1}{3} \right \rfloor 
\geq \frac{p^{r+2}+1}{3}-1 \geq p^{r+1} &gt; n
\end{equation}
\noindent
so the sum ends after $j = r+1$. 

\medskip

\noindent
4) The form of the series \eqref{series-0} 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
\begin{equation}
\nu_{p}(a_{n}) = \sum_{j=1}^{\infty} \alpha_{j,n} \phi_{j,p}(n)
\label{series-des}
\end{equation}
\noindent 
where $\phi_{j,p}$ is a function of period $p^{j}$. A 
procedure to determine the coefficients $\alpha_{j,n}$ directly from the 
sequence $\{ a_{n} \}$ and the functions $\{ \phi_{j,p} \}$ should be 
developed. Moreover, it is required that, 
for fixed $n \in \mathbb{N}$, the series \eqref{series-des} contains 
only finitely non-vanishing terms.

\medskip

\noindent
5) The authors of \cite{heu-pro} present an analytic formula for 
$\nu_{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 \cite{heu-pro} will be reported
later. 

\bigskip

 The proof of the theorem is based on the observation that
$\nu_{p}(A_{1}) = 0$ and $\text{Per}_{j,p}(1) = 0$, showing that both 
sides of \eqref{series-0} agree at $n=1$ coupled with recurrences 
satisfied by $\nu_{p}(A_{n})$
and $\text{Per}_{j,p}(n)$. These are given by
\begin{equation}
\nu_{p}(A_{n}) - \nu_{p}(A_{n-1}) = 
\frac{1}{p-1} 
\left( S_{p}(2n-2) + S_{p}(2n-1) - S_{p}(3n-2) -S_{p}(n-1) \right)
\label{rec-A}
\end{equation}
\noindent
and 
\begin{equation}
\text{Per}_{j,p}(n) - 
\text{Per}_{j,p}(n-1) = 
\begin{cases}
0,  &amp; \quad \text{ if }  \quad 0 \leq n \leq 
\left\lfloor \frac{p^{j}+1}{3} \right\rfloor;  \\
1,  &amp; \quad \text{ if } \quad  
\left\lfloor \frac{p^{j}+1}{3} \right\rfloor  
+1 \leq n \leq \frac{p^{j}-1}{2};\\
0, &amp; \quad \text{ if } \quad  
n = \frac{p^{j}+1}{2};  \\
-1,  &amp; \quad \text{ if } \quad  
\frac{p^{j}+3}{2} \leq n \leq \left\lfloor \frac{2p^{j}+1}{3} \right\rfloor; \\
0, &amp; \quad \text{ if } \quad  
\left\lfloor \frac{2p^{j}+1}{3} \right\rfloor  
+1 \leq n \leq p^{j}-1. 
\end{cases}
\label{dif-P}
\end{equation}
\noindent
The proof shows that the right-hand side of \eqref{rec-A} matches that of 
\eqref{dif-P}.


The study of the arithmetic aspects of the sequence $A_{n}$ was initiated in 
\cite{moll-sun1}, where the case of $\nu_{2}(A_{n})$ was considered. It is
shown that $\nu_{2}(A_{n})$ vanishes precisely when $n$ is a 
{\em 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 $\nu_{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}] \cup [J_{m-1},J_{m}]$.  In the 
situation considered here, the 
partial sums of the series \eqref{series-0} give approximations to 
$\nu_{p}(A_{n})$.  

\medskip

Section \ref{sec-exper} describes data that motivated the main theorem.
Section \ref{sec-ex1} establishes the recurrence for the valuation of 
$A_{n}$ and Section \ref{sec-recP} the corresponding recurrence for the 
function $\text{Per}_{j,p}$. Section \ref{sec-main} presents the 
proof of the main result. 


\section{An experimental illustration of the main theorem} \label{sec-exper}
\setcounter{equation}{0}

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

\medskip

\begin{center}
$
\begin{matrix}
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 \\
3 &amp; 4 &amp; 4 &amp; 3 &amp; 2 &amp; 1 &amp; 
0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp;
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 4 &amp; 3 &amp; 2 \\
1 &amp;
0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 \\
9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 &amp; 14 &amp; 15 &amp; 16 &amp; 18 &amp; 20 \\
22 &amp; 24 &amp; 24 &amp; 
22 &amp; 20 &amp; 18 &amp; 
16 &amp; 15 &amp; 14 &amp; 13 \\
12 &amp; 11 &amp; 10 &amp; 9 &amp; 8 &amp;
7 &amp; 6 &amp; 5 &amp; 4 &amp; 3 \\
2 &amp; 1 &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 4 &amp; 3 &amp; 2 \\
1 &amp; 
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 
\end{matrix}
$
\end{center}


{{
\begin{figure}[ht]
\centering
\epsfig{file=prime5.eps,width=15em,angle=0}
\caption{The $5$-adic valuation of $A_{n}$}
\label{figure-3}
\end{figure}
}}

\medskip

The observation employed to find the main theorem is based on the string
\begin{equation}
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
\end{equation}
and its central role in the function $\nu_{2}(n)$.  An analytic expression for 
the string is given by 
\begin{equation}
\text{Per}_{2,5}(n) := \begin{cases} 
               0, &amp; \quad \text{ if } 0 \leq n \leq 8; \\
               n-8, &amp; \quad \text{ if } 9 \leq n \leq 12; \\
               17 - n, &amp;  \quad \text{ if } 13 \leq n \leq 16; \\
               0, &amp;  \quad \text{ if } 17 \leq n \leq 24;
              \end{cases}
\end{equation}
and this is now extended to a periodic function of period $5^{2}$ by
$\text{Per}_{2,5}( n \bmod 5^{2} )$.

The function
\begin{equation}
\nu_{5}(A_{n})  - \text{Per}_{2,5}( n \bmod 5^{2}) 
\end{equation}
has values given by

\medskip

\begin{center}
$
\begin{matrix}
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 \\
9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 &amp; 14 &amp; 15 &amp; 16 &amp; 17 &amp; 18 \\
19 &amp; 20 &amp; 20 &amp; 19 &amp; 18 &amp; 17 &amp; 16 &amp; 15 &amp; 14 &amp; 13 \\
12 &amp; 11 &amp; 10 &amp; 9 &amp; 8 &amp; 7 &amp; 6 &amp; 5 &amp; 4 &amp; 3 \\
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 
\end{matrix}
$
\end{center}


\medskip

This data suggests the function

\begin{equation}
\text{Per}_{3,5}(n) := \begin{cases} 
               0, &amp; \quad \text{ if } 0 \leq n \leq 42;\\
               n-42, &amp; \quad \text{ if } 43 \leq n \leq 62;\\
               83 - n, &amp;  \quad \text{ if } 63 \leq n \leq 82;\\
               0, &amp;  \quad \text{ if } 83 \leq n \leq 124;
              \end{cases}
\end{equation}
and extend $\text{Per}_{3,5}$ to a periodic function of period $5^{3}$. 
This empirical procedure leads to the functions $\text{Per}_{j,p}(n)$ defined 
Theorem~\ref{thm-main}.

\section{An analytic formula } \label{sec-ex1}
\setcounter{equation}{0}

For a prime $p$, introduce the notation
\begin{equation}
f_{p}(j) := \nu_{p}(j!).
\end{equation}

\begin{lemma}
\label{thm-recurr1}
Let $p$ be a prime. Then the $p$-adic valuation of $A_{n}$ satisfies 
\begin{equation}
\nu_{p}(A_{n}) = \nu_{p}(A_{n-1}) + f_{p}(3n-2) + f_{p}(n-1) -f_{p}(2n-2) 
-f_{p}(2n-1).
\label{rec-1}
\end{equation}
\end{lemma}
\begin{proof}
This follows directly by combining the initial value $A_{1}=1$ with the 
expression 
\begin{equation}
\nu_{p}(A_{n}) = \sum_{j=0}^{n-1} f_{p}(3j+1) - \sum_{j=0}^{n-1} f_{p}(n+j)
\end{equation}
and the corresponding one for $\nu_{p}(A_{n-1})$.
\end{proof}

Legendre's formula (\ref{leg-11}) gives the result of 
Theorem~\ref{thm-recurr1} in terms of the function $S_{p}$.

\begin{corollary}
\label{p-val}
The $p$-adic valuation of $A_{n}$ is given by 
\begin{equation}
\nu_{p}(A_{n}) = \frac{1}{p-1} \left( \sum_{j=0}^{n-1} S_{p}(n+j) - 
\sum_{j=0}^{n-1} S_{p}(3j+1) \right). 
\end{equation}
\end{corollary}


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

\begin{proposition}
\label{prop-valuetn}
The $p$-adic valuation of $A_{n}$ is given by 
\begin{equation}
\nu_{p}(A_{n}) = \frac{1}{p-1} \sum_{j=1}^{n-1} 
\left( S_{p}(2j) + S_{p}(2j+1) - S_{p}(3j+1) - S_{p}(j) \right). 
\label{valp-form1}
\end{equation}
\end{proposition}

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

\begin{theorem}
\label{rec-A1}
The $p$-adic valuation of $A_{n}$ satisfies 
\begin{equation}
\nu_{p}(A_{n}) - \nu_{p}(A_{n-1})   = 
\frac{1}{p-1} 
\left( S_{p}(2n-2) + S_{p}(2n-1) - S_{p}(3n-2) -S_{p}(n-1) \right).
\nonumber
\end{equation}
\end{theorem}


\section{The recurrence for $\text{Per}_{j,p}(n)$} 
\label{sec-recP}
\setcounter{equation}{0}

The explicit formulas for $\text{Per}_{j,p}(n)$ can be used to give a
proof of \eqref{dif-P}. The only cases that require special 
attention are when $n$ and $n-1$ are on different intervals of the definition.
For instance, if
$ n =  \left\lfloor \frac{p^{j}+1}{3} \right\rfloor  + 1$, then 
$\text{Per}_{j,p}(n) = n - 
\left\lfloor \frac{p^{j}+1}{3} \right\rfloor  = 1$  and 
$\text{Per}_{j,p}(n-1) = 0$. The verification of all the cases is elementary. 

\section{The proof of the main theorem} \label{sec-main}
\setcounter{equation}{0}

Introduce the notation 
\begin{equation}
L_{1}(n,p) = S_{p}(2n-2) + S_{p}(2n-1) - S_{p}(3n-2) - S_{p}(n-1),
\end{equation}
with the convention that $S_{p}(x) = 0$ if $x&lt;0$ and 
\begin{equation}
L_{2}(n,p) = 
\sum_{j=1}^{\infty} g_{j}(n,p)
\label{series-p}
\end{equation}
where 
\begin{equation}
g_{j}(n,p) = 
\begin{cases}
0,  &amp; \quad \text{ if }  \quad 0 \leq n \bmod p^{j} \leq 
\left\lfloor \frac{p^{j}+1}{3} \right\rfloor;  \\
p-1, &amp; \quad \text{ if } \quad  
\left\lfloor \frac{p^{j}+1}{3} \right\rfloor  
+1 \leq n \bmod p^{j} \leq \frac{p^{j}-1}{2}; \\
0, &amp; \quad \text{ if } \quad  
n \bmod p^{j} = \frac{p^{j}+1}{2};  \\
-(p-1)  &amp; \quad \text{ if } \quad  
\frac{p^{j}+3}{2} \leq n \bmod p^{j} \leq \left\lfloor \frac{2p^{j}+1}{3} \right\rfloor; \\
0, &amp; \quad \text{ if } \quad  
\left\lfloor \frac{2p^{j}+1}{3} \right\rfloor  
+1 \leq n \bmod p^{j} \leq p^{j}-1. 
\end{cases}
\label{f-def}
\end{equation}
The statement of the main theorem is the identity
\begin{equation}
L_{1}(n,p) = L_{2}(n,p) \text{   for  } n \in \mathbb{N}.
\label{iden1}
\end{equation}

\medskip

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 \leq u \leq p-1$ and 
$0 \leq v \leq p^{r}-1$. The base case shows that $L_{1}(n,p) = L_{2}(n,p)$
for $1 \leq n \leq 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 {\em 
same } function $E$ in both cases. This completes the proof. 

\medskip


Observe that, for fixed $n \in \mathbb{N}$, the series in \eqref{series-p} is 
actually a finite sum. Terms with index $j \geq 2 + \left\lfloor{\log n/\log p }
\right \rfloor$ vanish. Thus, if $p^{r} \leq n &lt; p^{r+1}$, 
\begin{equation}
L_{2}(n,p) = \sum_{j=1}^{r+1} g_{j}(n,p).
\end{equation}

\medskip

The proof of \eqref{iden1} is by induction on the number of digits of $n$ in 
base $p$. The basic  case is considered first:  it deals with 
$n \in \mathbb{N}$ that
have a single digit; that is, $1 \leq n \leq p-1$.

\medskip

\noindent
$\bullet$ {\bf Base case}. Assume that $1 \leq n \leq p-1$. 

\medskip

The bound $p \geq 5$ implies that for $j \geq 2$ 
\begin{equation}
1 \leq n \leq p-1 &lt; \frac{p^{2}-2}{3} \leq 
\left \lfloor \frac{p^{j}+1}{3} \right \rfloor. 
\end{equation}
It follows that the sum 
in \eqref{series-p} contains a single term. It is required to show that
\begin{equation}
L_{1}(n,p) = 
\begin{cases}
0,  &amp; \quad \text{ if }  \quad 0 \leq n  \leq 
\left\lfloor \frac{p+1}{3} \right\rfloor;  \\
p-1,  &amp; \quad \text{ if } \quad  
\left\lfloor \frac{p+1}{3} \right\rfloor  
+1 \leq n \leq \frac{p-1}{2}; \\
0, &amp; \quad \text{ if } \quad  
n  = \frac{p+1}{2};  \\
1-p,  &amp; \quad \text{ if } \quad  
\frac{p+3}{2} \leq n \leq \left\lfloor \frac{2p+1}{3} \right\rfloor; \\
0, &amp; \quad \text{ if } \quad  
\left\lfloor \frac{2p+1}{3} \right\rfloor  
+1 \leq n \leq p-1. 
\end{cases}
\label{series-p1}
\end{equation}

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

\medskip

\noindent
{\bf Case 1.1}. Observe that  $3n-2 &lt; p$ is equivalent to 
$n \leq \left\lfloor \frac{p+1}{3} 
\right \rfloor$. Under this condition the terms $2n-2, \, 2n-1, \, 3n-2$ and 
$n-1$ have a single digit in base $p$. Therefore 
\begin{equation}
L_{1}(n,p)  = 
(2n-2) + (2n-1) - (3n-2) - (n-1) = 0.
\end{equation}

\medskip

\noindent
{\bf Case 1.2}. Assume $\left \lfloor \frac{p+1}{3} \right \rfloor 
&lt;  n \leq \frac{p-1}{2}.$ Then 
$2n-2 &lt; 2n-1 \leq p-2$ and $p \leq 3n-2 &lt; 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 \cdot 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 \eqref{series-p1} follows from these values. 

\medskip

\noindent
{\bf Case 1.3}. If $n = \frac{p+1}{2}$, then the terms 
involved in \eqref{series-p1} are 
\begin{equation}
S_{p}(2n-2) = p-1, \, S_{p}(2n-1) = 1, \, 
S_{p}(3n-2) = 1 + (3n-2-p) \text{ and } S_{p}(n-1) = n-1.
\nonumber
\end{equation}
The identity \eqref{series-p1} follows from these values. 

\medskip

The remaining cases can be obtained by similar arguments.
The proof of \eqref{series-p1} is now complete establishing the base case
of the main theorem. 

\medskip

\noindent
$\bullet$ {\bf Inductive step}. For fixed $n \in \mathbb{N}$, recall that 
$r \in \mathbb{N}$ is defined by the inequalities
$p^{r} \leq n &lt; p^{r+1}$; that is, 
\begin{equation}
r = \left \lfloor \frac{\log n}{\log p} \right \rfloor.
\end{equation}
\noindent
Write $n = up^{r} + v$, with $1 \leq u &lt; p$ and $0 \leq v \leq 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)$. 

\medskip

The next lemma illustrates one case in complete detail. The common assumption 
is that 
$n \in \mathbb{N}$ satisfies $p^{r} \leq n &lt; p^{r+1}$. By
convention, $S_{p}(n) = 0 $ if $n &lt; 0$. 

\begin{lemma}
For $n \in \mathbb{N}$, 
\begin{equation}
S_{p}(2n-2) = S_{p}(2v-2) + T_{1}(n,p)
\end{equation}
where $T_{1}(n,p)$ is given in the table below. 

\begin{center}
\begin{tabular}{||c|c|c||}
\hline 
 $v$ &amp;$ u$ &amp; $ T_{1}(n,p)$ \\
\hline  
 &amp; &amp;  \\
$v = 0$ &amp;  $1 \leq u \leq \tfrac{p-1}{2}$ &amp; $2u -2 + r(p-1)$ \\
&amp; &amp; \\
$v = 0$ &amp;  $\tfrac{p+1}{2} \leq u \leq p-1$ &amp; $2u -p -1  + r(p-1)$  \\
&amp; &amp; \\
  $1 \leq v \leq \tfrac{p^{r}+1}{2}$ &amp; $1 \leq u \leq \tfrac{p-1}{2}$ &amp;
$  2u $\\
&amp; &amp; \\
  $1 \leq v \leq \tfrac{p^{r}+1}{2}$ &amp;$ \tfrac{p+1}{2} \leq u \leq p-1$ &amp;  
$2u - p + 1$  \\
&amp; &amp; \\
 $ \tfrac{p^{r}+3}{2}  \leq v \leq p^{r} -1 $ &amp;$ 1 \leq u \leq \tfrac{p-3}{2}$ 
&amp; $ 2u $\\
&amp; &amp; \\
  $\tfrac{p^{r}+3}{2}  \leq v \leq p^{r}-1$ &amp; $\tfrac{p-1}{2} \leq u \leq p-1$ &amp;  
$2u - p + 1$ 
\\
&amp; &amp; \\
\hline
\end{tabular}
\end{center}
\begin{center}
\rm{The values of $T_{1}(n,p)$}.
\end{center}

\medskip

\end{lemma}
\begin{proof}
Start with $2n-2 = 2up^{r} + 2v-2$. The discussion of
$S_{p}(2n-2)$ is divided into cases according to $2v-2$. 

\medskip

\noindent
{\bf 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 \leq 2u-1 \leq 2p-3$ yield two separate cases:

\medskip

\noindent
{\bf SubCase 1.1}: $1 \leq 2u-1 \leq p-1$. In this case 
$S_{p}(2u-1) = 2u-1$ and it follows that
\begin{equation}
S_{p}(2n-2) = 2u-1 + S_{p}(p^{r}-2).
\end{equation}
\noindent
The identity 
\begin{equation}
p^r-2 = (p-2) + (p-1)p + (p-1)p^{2} + \cdots (p-1)p^{r-1}
\end{equation}
\noindent
produces $S_{p}(p^{r}-2) = r(p-1)-1$. Therefore
\begin{equation}
S_{p}(2n-2) = 2u-2 + r(p-1).
\end{equation}

\medskip

\noindent
{\bf SubCase 1.2}: $p \leq 2u-1 \leq 2p-3$. The expression
\begin{eqnarray}
2n-2  &amp; = &amp; (2u-1)p^{r} + (p^{r}-2) \nonumber \\
      &amp; = &amp; p^{r+1} + (2u-1-p)p^{r} + (p^{r}-2)  \nonumber 
\end{eqnarray}
\noindent
gives
\begin{eqnarray}
S_{p}(2n-2) &amp; = &amp; 1 + (2u-1-p) + S_{p}(p^{r}-2) \nonumber \\
 &amp; = &amp; (2u-p-1) + r(p-1). \nonumber
\end{eqnarray}

\medskip

\noindent 
This completes the case $v=0$. 

\medskip

\noindent
{\bf Case 2}. This considers the situation where $0&lt; 2v-2 &lt; p^{r}$. Then
the representation of $2v-2$ in base $p$ does not produce carries to the 
position of $p^{r}$. The discussion of 
\begin{equation}
2n-2 = 2u p^{r} + 2v-2 
\label{form-1}
\end{equation}
is divided, as before,  into two subcases according to the value of $2u$.

\medskip

\noindent
{\bf SubCase 2.1.}: $1 \leq 2u \leq p-1$. Then \eqref{form-1} gives
\begin{equation}
S_{p}(2n-2) = 2u + S_{p}(2v-2).
\end{equation}

\medskip

\noindent
{\bf SubCase 2.2}: $p \leq 2u \leq 2p-1$. Equation \eqref{form-1}
is now written as
\begin{equation}
2n-2   =  p^{r+1} + (2u-p)p^{r} + (2v-2).
\end{equation}
It follows from here that
$S_{p}(2n-2) =  1 + (2u-p) + S_{p}(2v-2)$.

\medskip

\noindent
{\bf Case 3}. The last possibility is $p^{r} \leq 2v-2 &lt; 2p^{r}$.  The 
expression 
\begin{equation}
2n-2 = (2u+1)p^{r} + (2v-2-p^{r})
\end{equation}
\noindent
leads to two subcases:

\medskip

\noindent
{\bf SubCase 3.1}: $2u+1 \leq p-1$. Then $2u+1 &lt; 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)$.

\medskip

\noindent
{\bf SubCase 3.2}: $p \leq 2u+1 \leq 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.
\end{proof}

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. 


\begin{lemma}
Let $n \in \mathbb{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. 
\end{lemma}

\medskip

\begin{center}
\begin{tabular}{||c|c|c||}
\hline 
 $v$ &amp;$ u$ &amp; $ T_{2}(n,p)$ \\
\hline  
 &amp; &amp;  \\
$v = 0$ &amp;  $1 \leq u \leq \tfrac{p-1}{2}$ &amp; $2u -1 + r(p-1)$ \\
&amp; &amp; \\
$v = 0$ &amp;  $\tfrac{p+1}{2} \leq u \leq p-1$ &amp; $2u -p  + r(p-1)$  \\
&amp; &amp; \\
  $1 \leq v \leq \tfrac{p^{r}-1}{2}$ &amp; $1 \leq u \leq \tfrac{p-1}{2}$ &amp;
$  2u $\\
&amp; &amp; \\
  $1 \leq v \leq \tfrac{p^{r}-1}{2}$ &amp;$ \tfrac{p+1}{2} \leq u \leq p-1$ &amp;  
$2u - p + 1$  \\
&amp; &amp; \\
 $ \tfrac{p^{r}+1}{2}  \leq v \leq p^{r} -1 $ &amp;$ 1 \leq u \leq \tfrac{p-3}{2}$ 
&amp; $ 2u $\\
&amp; &amp; \\
  $\tfrac{p^{r}+1}{2}  \leq v \leq p^{r}-1$ &amp; $\tfrac{p-1}{2} \leq u \leq p-1$ &amp;  
$2u - p + 1$ 
\\
&amp; &amp; \\
\hline
\end{tabular}
\end{center}
\begin{center}
The values of $T_{2}(n,p)$.
\end{center}

\medskip


\begin{lemma}
Let $n \in \mathbb{N}$. Then
$S_{p}(n-1) = S_{p}(v-1) + T_{3}(n,p)$
where $T_{3}(n,p)$ is given below. 
\end{lemma}


\begin{center}
\begin{tabular}{||c|c||}
\hline 
 $v$  &amp; $ T_{3}(n,p)$ \\
\hline  
 &amp;   \\
$v = 0$ &amp;    $u-1 + r(p-1)$ \\
&amp;  \\
  $1 \leq v \leq p^{r}-1$ &amp; $u$  \\
\hline
\end{tabular}
\end{center}
\begin{center}
The values of $T_{3}(n,p)$.
\end{center}

\begin{lemma}
Let $n \in \mathbb{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.
\end{lemma}

\medskip

\begin{center}
\begin{tabular}{||c|c|c||}
\hline 
 $v$ &amp;$ u$ &amp; $ T_{4}(n,p)$ \\
\hline  
 &amp; &amp;  \\
$v = 0$ &amp;  $2 \leq 3u-1 \leq p-1$ &amp; $3u -2 + r(p-1)$ \\
&amp; &amp; \\
$v = 0$ &amp;  $p \leq 3u-1  \leq 2p-1$ &amp; $3u -p -1  + r(p-1)$  \\
&amp; &amp; \\
$v = 0$ &amp;  $2p \leq 3u-1 \leq 3p-4 $ &amp; $3u -2p  + r(p-1)$  \\
&amp; &amp; \\
$1 \leq 3v-2 \leq p^{r}-1$ &amp;  $1 \leq 3u \leq p-1 $ &amp; $3u $  \\
&amp; &amp; \\
$1 \leq 3v-2 \leq p^{r}-1$ &amp;  $p \leq 3u \leq 2p-1 $ &amp; $3u-p + 1 $  \\
&amp; &amp; \\
$1 \leq 3v-2 \leq p^{r}-1$ &amp;  $2p \leq 3u \leq 3p-3 $ &amp; $3u-2p + 2 $  \\
&amp; &amp; \\
$p^{r}  \leq 3v-2 \leq 2p^{r}-1$ &amp;  $1 \leq 3u + 1 \leq p-1 $ &amp; $3u $  \\
&amp; &amp; \\
$p^{r}  \leq 3v-2 \leq 2p^{r}-1$ &amp;  $p \leq 3u + 1 \leq 2p-1 $ 
&amp; $3u-p + 1$  \\
&amp; &amp; \\
$p^{r}  \leq 3v-2 \leq 2p^{r}-1$ &amp;  $2p \leq 3u + 1 \leq 3p-2 $ 
&amp; $3u-2p + 2$  \\
&amp; &amp; \\
$2p^{r}  \leq 3v-2 \leq 3p^{r}-1$ &amp;  $1 \leq 3u + 2 \leq p-1 $ &amp; $3u $  \\
&amp; &amp; \\
$2p^{r}  \leq 3v-2 \leq 3p^{r}-1$ &amp;  $p \leq 3u + 2 \leq 2p-1 $ 
&amp; $3u-p + 1$  \\
&amp; &amp; \\
$2p^{r}  \leq 3v-2 \leq 3p^{r}-1$ &amp;  $2p \leq 3u + 2 \leq 3p-1 $ 
&amp; $3u-2p + 1$  \\
&amp; &amp; \\
\hline
\end{tabular}
\end{center}
\begin{center}
The values of $T_{4}(n,p)$.
\end{center}
\medskip

\begin{corollary}
The information given above, shows that
\begin{equation}
L_{1}(n,p) = L_{1}(v,p) + \left[ T_{1}(n,p) + T_{2}(n,p) - T_{3}(n,p) -
T_{4}(n,p) \right].
\end{equation}
\end{corollary}

\medskip

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

\medskip

Recall that $r$ is defined
by  $p^{r} \leq n &lt; p^{r+1}$. It follows that the inequality
$\begin{displaystyle} p^{r+1} &lt; \left\lfloor (p^j+1)/3 \right\rfloor
\end{displaystyle}$ holds for $j \geq r+2$, yielding
\begin{equation}
n \bmod p^{j} = n &lt; p^{r+1} &lt; \left\lfloor (p^{j}+1)/3 \right\rfloor.
\end{equation}
Thus the corresponding term in \eqref{series-p} vanishes. For
indices $1 \leq j \leq r$, the relation $n = up^{r}+v$, gives 
$n \bmod p^{j} = v \bmod p^{j}$. Therefore $L_{2}(n,p) $ and $L_{2}(v,p)$ 
differ only in the last term. Morever, the bound $n &lt; p^{r+1}$ implies that 
$n \bmod p^{r+1}$ is simply $n$. These observations are recorded in the next 
proposition.  

\begin{proposition}
Let $n \in \mathbb{N}$. Recall the definition
$r = r(n,p) :=  \left\lfloor \log n/\log p \right\rfloor$, so that 
$p^{r} \leq n &lt; p^{r+1}$. Then, the identity 
\begin{equation}
L_{2}(n,p) = L_{2}(v,p) + g_{r+1}(n,p)
\end{equation}
holds, with
\begin{equation}
g_{r+1}(n,p) = 
\begin{cases}
0,  &amp; \quad \text{ if }  \quad 0 \leq n  \leq 
\left\lfloor \frac{p^{r+1}+1}{3} \right\rfloor; \\
p-1,  &amp; \quad \text{ if } \quad  
\left\lfloor \frac{p^{r+1}+1}{3} \right\rfloor  
+1 \leq n  \leq \frac{p^{r+1}-1}{2};\\
0, &amp; \quad \text{ if } \quad  
n  = \frac{p^{r+1}+1}{2}; \\
-(p-1)  &amp; \quad \text{ if } \quad  
\frac{p^{r+1}+3}{2} \leq n 
\leq \left\lfloor \frac{2p^{r+1}+1}{3} \right\rfloor;\\
0, &amp; \quad \text{ if } \quad  
\left\lfloor \frac{2p^{r+1}+1}{3} \right\rfloor  
+1 \leq n  \leq p^{r+1}-1. 
\end{cases}
\end{equation}
\end{proposition}

\noindent
The next result completes the proof of the main theorem.

\begin{theorem}
With the notations established above
\begin{equation}
T_{1}(n,p) + T_{2}(n,p) - T_{3}(n,p) - T_{4}(n,p) = g_{r+1}(n,p).
\label{eqn-final}
\end{equation}
\end{theorem}
\begin{proof}
The proof is presented in detail for the case  $\left\lfloor 
(p^{r+1}+1)/3 \right \rfloor +1 \leq n \leq (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
\begin{equation}
0 \leq v \leq p^{r} -1 \text{ and }
p \leq 3 u + \text{Spill}(3v-2) \leq \tfrac{3}{2}(p-1).
\end{equation}
Assume that $v &gt; 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 \leq 3v-2 &lt; 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 \leq 3v-2 \leq p^{r}-1$ and $p \leq 3u \leq 2p-1$.
The table of values for $T_{4}$ gives $T_{4}(n,p) = 3u-p+1$. The bound 
$n \leq \tfrac{1}{2}(p^{r+1}-1) = \tfrac{p-1}{2}p^{r} + \tfrac{1}{2}(p^{r}-1)$
imply that $u \leq \tfrac{p-1}{2}$. Since the spill of  $3v-2$ is $0$ 
it follows that $3v \leq p^{r}+1$. Now, $p \geq 5$, therefore
$v \leq \tfrac{1}{3}(p^{r}+1) \leq \tfrac{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
\begin{equation}
T_{1}(n,p) + T_{2}(n,p) - T_{3}(n,p) - T_{4}(n,p) = 
2u + 2u - \left[ u + 3u-p+1 \right] = p-1.
\nonumber
\end{equation}
This is the value of $g_{r+1}(n,p)$. The remaining cases follow the same 
pattern. 
\end{proof}

\medskip

The main theorem has now been established. 

\medskip

\section{Acknowledgements} \label{sec-ack}
\setcounter{equation}{0}

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.



\begin{thebibliography}{1}

\bibitem{bressoud1}
D.~Bressoud.
\newblock \textit{Proofs and {C}onfirmations: the {S}tory of the {A}lternating
  {S}ign {M}atrix {C}onjecture}.
\newblock Cambridge University Press, 1999.


\bibitem{heu-pro}
C.~Heuberger and H.~Prodinger.
\newblock A precise description of the $p$-adic valuation of the 
number of alternating sign matrices.
\newblock \textit{Int. {J}. {N}umber {T}heory}, \textbf{7} (2011), 
57--69.

\bibitem{legendre1}
A.~M. Legendre.
\newblock \textit{Th\'eorie des {N}ombres}.
\newblock Firmin {D}idot {F}r\`eres, {P}aris, 1830.

\bibitem{moll-sun1}
X.~Sun and V.~Moll.
\newblock The $p$-adic valuation of sequences counting alternating sign
  matrices.
\newblock \textit{J. {I}nteger {S}eq.}, \textbf{12} (2009), {A}rticle 09.3.8.

\bibitem{zeilberger96}
D.~Zeilberger.
\newblock Proof of the alternating sign matrix conjecture.
\newblock \textit{Electron. {J}. {C}ombin.}, \textbf{3} (1996), 1--78.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A10; Secondary 11B75, 11Y55

\noindent \emph{Keywords: } Alternating sign matrices, valuations, recurrences, digit count. 

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A005130}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 3 2011;
revised version received July 18 2011; September 8 2011.
Published in {\it Journal of Integer Sequences}, October 16 2011.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


</pre></body></html>