\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, & \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, & \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, & \quad \text{ if } \quad \frac{p^{j}+1}{2} \leq n \leq \left\lfloor \frac{2p^{j}+1}{3} \right\rfloor; \\ 0, & \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 < 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} > 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, & \quad \text{ if } \quad 0 \leq n \leq \left\lfloor \frac{p^{j}+1}{3} \right\rfloor; \\ 1, & \quad \text{ if } \quad \left\lfloor \frac{p^{j}+1}{3} \right\rfloor +1 \leq n \leq \frac{p^{j}-1}{2};\\ 0, & \quad \text{ if } \quad n = \frac{p^{j}+1}{2}; \\ -1, & \quad \text{ if } \quad \frac{p^{j}+3}{2} \leq n \leq \left\lfloor \frac{2p^{j}+1}{3} \right\rfloor; \\ 0, & \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 & 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 \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, & \quad \text{ if } 0 \leq n \leq 8; \\ n-8, & \quad \text{ if } 9 \leq n \leq 12; \\ 17 - n, & \quad \text{ if } 13 \leq n \leq 16; \\ 0, & \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 & 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 \end{matrix} $ \end{center} \medskip This data suggests the function \begin{equation} \text{Per}_{3,5}(n) := \begin{cases} 0, & \quad \text{ if } 0 \leq n \leq 42;\\ n-42, & \quad \text{ if } 43 \leq n \leq 62;\\ 83 - n, & \quad \text{ if } 63 \leq n \leq 82;\\ 0, & \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<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, & \quad \text{ if } \quad 0 \leq n \bmod p^{j} \leq \left\lfloor \frac{p^{j}+1}{3} \right\rfloor; \\ p-1, & \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, & \quad \text{ if } \quad n \bmod p^{j} = \frac{p^{j}+1}{2}; \\ -(p-1) & \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, & \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 < 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 < \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, & \quad \text{ if } \quad 0 \leq n \leq \left\lfloor \frac{p+1}{3} \right\rfloor; \\ p-1, & \quad \text{ if } \quad \left\lfloor \frac{p+1}{3} \right\rfloor +1 \leq n \leq \frac{p-1}{2}; \\ 0, & \quad \text{ if } \quad n = \frac{p+1}{2}; \\ 1-p, & \quad \text{ if } \quad \frac{p+3}{2} \leq n \leq \left\lfloor \frac{2p+1}{3} \right\rfloor; \\ 0, & \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 < 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 < n \leq \frac{p-1}{2}.$ Then $2n-2 < 2n-1 \leq p-2$ and $p \leq 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 \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 < 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 < 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 < p^{r+1}$. By convention, $S_{p}(n) = 0 $ if $n < 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$ &$ u$ & $ T_{1}(n,p)$ \\ \hline & & \\ $v = 0$ & $1 \leq u \leq \tfrac{p-1}{2}$ & $2u -2 + r(p-1)$ \\ & & \\ $v = 0$ & $\tfrac{p+1}{2} \leq u \leq p-1$ & $2u -p -1 + r(p-1)$ \\ & & \\ $1 \leq v \leq \tfrac{p^{r}+1}{2}$ & $1 \leq u \leq \tfrac{p-1}{2}$ & $ 2u $\\ & & \\ $1 \leq v \leq \tfrac{p^{r}+1}{2}$ &$ \tfrac{p+1}{2} \leq u \leq p-1$ & $2u - p + 1$ \\ & & \\ $ \tfrac{p^{r}+3}{2} \leq v \leq p^{r} -1 $ &$ 1 \leq u \leq \tfrac{p-3}{2}$ & $ 2u $\\ & & \\ $\tfrac{p^{r}+3}{2} \leq v \leq p^{r}-1$ & $\tfrac{p-1}{2} \leq u \leq p-1$ & $2u - p + 1$ \\ & & \\ \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 & = & (2u-1)p^{r} + (p^{r}-2) \nonumber \\ & = & p^{r+1} + (2u-1-p)p^{r} + (p^{r}-2) \nonumber \end{eqnarray} \noindent gives \begin{eqnarray} S_{p}(2n-2) & = & 1 + (2u-1-p) + S_{p}(p^{r}-2) \nonumber \\ & = & (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< 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 \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 < 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 < 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$ &$ u$ & $ T_{2}(n,p)$ \\ \hline & & \\ $v = 0$ & $1 \leq u \leq \tfrac{p-1}{2}$ & $2u -1 + r(p-1)$ \\ & & \\ $v = 0$ & $\tfrac{p+1}{2} \leq u \leq p-1$ & $2u -p + r(p-1)$ \\ & & \\ $1 \leq v \leq \tfrac{p^{r}-1}{2}$ & $1 \leq u \leq \tfrac{p-1}{2}$ & $ 2u $\\ & & \\ $1 \leq v \leq \tfrac{p^{r}-1}{2}$ &$ \tfrac{p+1}{2} \leq u \leq p-1$ & $2u - p + 1$ \\ & & \\ $ \tfrac{p^{r}+1}{2} \leq v \leq p^{r} -1 $ &$ 1 \leq u \leq \tfrac{p-3}{2}$ & $ 2u $\\ & & \\ $\tfrac{p^{r}+1}{2} \leq v \leq p^{r}-1$ & $\tfrac{p-1}{2} \leq u \leq p-1$ & $2u - p + 1$ \\ & & \\ \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$ & $ T_{3}(n,p)$ \\ \hline & \\ $v = 0$ & $u-1 + r(p-1)$ \\ & \\ $1 \leq v \leq p^{r}-1$ & $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$ &$ u$ & $ T_{4}(n,p)$ \\ \hline & & \\ $v = 0$ & $2 \leq 3u-1 \leq p-1$ & $3u -2 + r(p-1)$ \\ & & \\ $v = 0$ & $p \leq 3u-1 \leq 2p-1$ & $3u -p -1 + r(p-1)$ \\ & & \\ $v = 0$ & $2p \leq 3u-1 \leq 3p-4 $ & $3u -2p + r(p-1)$ \\ & & \\ $1 \leq 3v-2 \leq p^{r}-1$ & $1 \leq 3u \leq p-1 $ & $3u $ \\ & & \\ $1 \leq 3v-2 \leq p^{r}-1$ & $p \leq 3u \leq 2p-1 $ & $3u-p + 1 $ \\ & & \\ $1 \leq 3v-2 \leq p^{r}-1$ & $2p \leq 3u \leq 3p-3 $ & $3u-2p + 2 $ \\ & & \\ $p^{r} \leq 3v-2 \leq 2p^{r}-1$ & $1 \leq 3u + 1 \leq p-1 $ & $3u $ \\ & & \\ $p^{r} \leq 3v-2 \leq 2p^{r}-1$ & $p \leq 3u + 1 \leq 2p-1 $ & $3u-p + 1$ \\ & & \\ $p^{r} \leq 3v-2 \leq 2p^{r}-1$ & $2p \leq 3u + 1 \leq 3p-2 $ & $3u-2p + 2$ \\ & & \\ $2p^{r} \leq 3v-2 \leq 3p^{r}-1$ & $1 \leq 3u + 2 \leq p-1 $ & $3u $ \\ & & \\ $2p^{r} \leq 3v-2 \leq 3p^{r}-1$ & $p \leq 3u + 2 \leq 2p-1 $ & $3u-p + 1$ \\ & & \\ $2p^{r} \leq 3v-2 \leq 3p^{r}-1$ & $2p \leq 3u + 2 \leq 3p-1 $ & $3u-2p + 1$ \\ & & \\ \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 < p^{r+1}$. It follows that the inequality $\begin{displaystyle} p^{r+1} < \left\lfloor (p^j+1)/3 \right\rfloor \end{displaystyle}$ holds for $j \geq r+2$, yielding \begin{equation} n \bmod p^{j} = n < p^{r+1} < \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 < 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 < 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, & \quad \text{ if } \quad 0 \leq n \leq \left\lfloor \frac{p^{r+1}+1}{3} \right\rfloor; \\ p-1, & \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, & \quad \text{ if } \quad n = \frac{p^{r+1}+1}{2}; \\ -(p-1) & \quad \text{ if } \quad \frac{p^{r+1}+3}{2} \leq n \leq \left\lfloor \frac{2p^{r+1}+1}{3} \right\rfloor;\\ 0, & \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 > 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 < 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}