% ----------------------------------------------------------------
% AMS-LaTeX Paper ************************************************
% **** -----------------------------------------------------------
\documentclass{amsart}
\usepackage{graphicx}
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
%\theoremstyle{definition}
%\newtheorem{defn}[thm]{Definition}
%\theoremstyle{remark}
%\newtheorem{rem}[thm]{Remark}
%\numberwithin{equation}{section}
% MATH -----------------------------------------------------------
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\Real}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\BX}{\mathbf{B}(X)}
\newcommand{\A}{\mathcal{A}}
% ----------------------------------------------------------------
\begin{document}

\title{Using the ``Freshman's Dream'' Identity to  Prove  Combinatorial Congruences }

\author{Moa Apagodu} 
\address{Department of Mathematics, Virginia Commonwealth University, Richmond, VA 23284, USA}

\begin{abstract} In a recent beautiful but technical article, William Y.C. Chen, Qing-Hu Hou, and Doron Zeilberger 
developed an algorithms for finding congruence, mod p, of 
sequences of indefinite sums of many combinatorial sequences, namely those (like the Catalan and Motzkin sequences)
that are expressible in terms of constant terms of powers of Laurent polynomials.
Here we extend it in two directions. 
The Laurent polynomials in question may be of several variables, 
and instead of single sums we have multiple sums. In fact we even combine these two generalizations.
\end{abstract}

\maketitle

%\vskip .2in

\noindent {\bf {Introduction}}
\vskip .2in
\noindent  In a recent elegant article, [2],  the following type of quantities were considered

$$
\left(\sum_{k=0}^{rp-1}a(k)\right)\,\,\text{mod}\,\,p \,\,,
$$

\noindent where $a(k)$ is a combinatorial sequence, expressible as the constant term of a power of a Laurent polynomial
of a {\bf singel} variable, $k$; $r$ is a positive integer; and $p$ is a {\it general} (symbolic) 
prime. 

Their method, while ingenious, is very elementary! All they need is 
the

\vskip .2in

{\bf The Freshman's Dream Identity}

$$
(a+b)^p \equiv_p a^p + b^p \quad,
$$
where $x \equiv_p y$ means $x \equiv y \text{mod}\,\,p$.

\vskip .2in

Recall that the easy proof follows from using the Binomial theorem, and noting that ${p \choose r}$ is divisible by $p$ except when
$r=0$ and $r=p$. This also leads, to one of the many proofs of the grandmother of all congruences, {\bf Fermat's Little Theorem},
$a^p  \equiv_p a$,  by  starting with  $0^p  \equiv_p 0$,  and applying induction to $(a+1)^p \equiv_p a^p + 1^p$.

The second ingredient in the ingenious method of [2] is even more elementary

\vskip .2in

{\bf Sum of a Geometric Series}:
$$
\sum_{i=0}^{n-1} z^i = \frac{1-z^n}{1-z} \quad ,
$$

The focus in the Chen-Hou-Zeilberger paper was both computer-algebra implementation, and proving a general theorem
about a wide class of sums, and it is rather technical, and hence its beauty  is lost to a wider audience.
The first purpose of the present article is to give a more leisurly introduction to their method, and
illustrate it with some illuminating examples. The main purpose, however, is to extend it
in {\bf two} directions. The summand $a(k)$, may be the constant term of a Laurent polynomial in {\bf several} variables,
and instead of a {\bf single} summation sign, we can have {\it multi-sums}. In fact we can combine these two

\vskip .2in

{\bf Notation}
\noindent The constant term of a Laurent polynomial $P(x_1,x_2,\ldots,x_n)$, alias
the coefficient of $x_1^0x_2^0..x_n^0$, is denoted by $CT[P(x_1,x_2,\ldots,x_n)]$ and the general coefficient of 
$x_1^{n_1}x_2^{n_2}..x_n^{n_k}$ in $P(x_1,x_2,\ldots,x_n)$ is denoted by 
$COEFF_{[x_1^{n_1}x_2^{n_2}..x_n^{n_ k}]}P(x_1,x_2,\ldots,x_n) $. For example, 
$$
\displaystyle{CT\left[ \frac{1}{xy}+3+5xy-x^3+6y^2\right]=3}\,\, \text{and} \,\, 
COEFF_{[xy]}\left[ \frac{1}{xy}+3+5xy+x^3+6y^2\right]=5.
$$

\noindent We use the symmetric representation of integers in $[-|m|/2, |m|/2]$ when reducing modulo integer $m$. For example,  6 mod $5=1$ and 4 mod $5 =-1$. 

\vskip .2in
\noindent {\bf Review of the Chen-Hou-Zeilberger Single Variable Case}\\

\noindent  In order to motivate our generalization, we will first review, in more detail then given in [2], some
of their elegant results.\\ 

\noindent {\bf Proposition 1}. For any prime $p$ and positive integer $r$, define

$\displaystyle{A(r;p):=\sum_{n=0}^{rp-1} { 2n \choose n}}$. Then,  $A(1;p) \,\text{mod}\, p \,=\left\{\begin{array}{l}
1 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-1 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$
\vskip .1in

\noindent  {\bf Proof}: Using the fact that $\displaystyle{{ 2n \choose n} = CT\left[ \frac{(1+x)^{2n}}{x^n} \right]}$ and $(a+b)^p\equiv_p a^p+b^p $, we have

\begin{eqnarray*}
\sum_{n=0}^{p-1} {2n \choose n} &=& \sum_{n=0}^{p-1} CT\left[ \left(\frac{(1+x)^{2n}}{x^n}\right)\right] \\
&=& \sum_{n=0}^{p-1} CT\left[ \left(2+x+\frac{1}{x}\right)^n\right] \\
&=& CT\left[ \frac{\left(2+x+\frac{1}{x}\right)^p-1}{2+x+\frac{1}{x}-1}\right] \\
&\equiv_p& CT \left[ \frac{2^p+x^{p}+\frac{1}{x^p}-1}{1+x+\frac{1}{x}}\right]\text{By Freshman's dream} \\
&\equiv_p& CT \left[ \frac{2+x^{p}+\frac{1}{x^p}-1}{1+x+\frac{1}{x}}\right]\text{By Fermat's little theorem} \\
&=& CT \left[ \frac{1+x^{p}+\frac{1}{x^p}}{1+x+\frac{1}{x}}\right] \\
&=& CT\left[ \frac{1+x^p+x^{2p}}{(1+x+x^2)x^{p-1}}\right] \\
&=& COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x+x^2}\right] \\
&=& COEFF_{[x^{p-1}]} \left[ \frac{1-x}{1-x^3}\right]\,. \\
&=& COEFF_{[x^{p}]} \sum_{i=0}^{\infty} x^{3i+1} \, - \, \sum_{i=0}^{\infty} x^{3i+2}  \,. \\
\end{eqnarray*}

\noindent The result follows from extracting the coefficient of $x^p$ from the two sums on the right side.\\

\noindent {\bf Corollary 1 (Corollary 2.3, [2])}:   $A(2;p)\,\text{mod}\, p \,=\left\{\begin{array}{l}
3 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-3 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$

\noindent {\bf Proof}: Proceeding as in Theorem 1 above,

\begin{eqnarray*}
\sum_{n=0}^{2p-1} {2n \choose n} &=& \sum_{n=0}^{2p-1} CT \left[ \left(\frac{(1+x)^{2n}}{x^n}\right)\right] \\
&=&CT \left[ \frac{\left(2+x+\frac{1}{x}\right)^{2p}-1}{2+x+\frac{1}{x}-1}\right] \\
&=&CT\left[ \frac{\left(6+4x+\frac{4}{x}+x^2+\frac{1}{x^2}\right)^{p}-1}{2+x+\frac{1}{x}-1}\right] \\
&\equiv_p&CT\left[ \frac{\left(6+4x^p+\frac{4}{x^p}+x^{2p}+\frac{1}{x^{2p}}\right)-1}{2+x+\frac{1}{x}-1}\right] \\
&\equiv_p& COEFF_{[x^{2p-1}]} \left[  \frac{1+4x^p}{1+x+x^2}\right] \\
&\equiv_p& COEFF_{[x^{2p-1}]} \left[ \frac{1}{1+x+x^2}\right]  +4 COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x+x^2}\right] \,\,.\\
\end{eqnarray*}

\noindent The result follows from Theorem 1 and the last congruence. 

\vskip .2in

\noindent
{\bf Corollary 2 (Catalan Numbers)}: Let $a(n)$ be the constant term of $\displaystyle{(1-x)\left(2+x+\frac{1}{x}\right)^n}$ and let
$$
A(r;p):=\sum_{n=0}^{rp-1}  a(n)\,\,.
$$
 \noindent 
Then,  $A(1;p)\,\text{mod}\, p \,=\left\{\begin{array}{l}
1 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-2 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.$\\

\noindent {\bf Proof}:  Continuing as above, 
\begin{eqnarray*}
\sum_{n=0}^{p-1} a(n) &=& \sum_{n=0}^{p-1} CT \left[(1-x)\left(2+x+\frac{1}{x}\right)^n\right] \\
&=& CT \left[ \frac{(1-x)\left(\left(2+x+\frac{1}{x}\right)^p-1\right)}{2+x+\frac{1}{x}-1}\right]\\
&\equiv_p& CT\left[ \frac{(1-x)\left(\left(2+x^p+\frac{1}{x^p}\right)-1\right)}{2+x+\frac{1}{x}-1}\right]\\
&\equiv_p& COEFF_{[x^{p-1}]} \left[  \frac{1-x}{1+x+x^2}\right] \\
&\equiv_p& COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x+x^2}\right]  -  COEFF_{[x^{p-2}]} \left[ \frac{1}{1+x+x^2}\right]\,. \\
\end{eqnarray*}

\noindent The result follows from Theorem 1 and the last congruence.

\vskip .2in


\noindent
{\bf Theorem 2 (Motzkin Numbers)}.  Let $a(n)$ be the constant term of $\displaystyle{(1-x^2)\left(1+x+\frac{1}{x}\right)^n}$, and define
$$A(r;p):=\sum_{n=0}^{rp-1}  a(n)\,\,. $$
 
\noindent 
Then,  $A(1;p)\,\text{mod}\, p \,=\left\{\begin{array}{l}
2 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  4\\
-2 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 3 \mod 4\,\,\,.\\
\end{array}\right.
$

\noindent
{\bf Proof}: 

\begin{eqnarray*}
\sum_{n=0}^{p-1} a(n) &=& \sum_{n=0}^{p-1} CT \left[(1-x^2)\left(1+x+\frac{1}{x}\right)^n\right] \\
&=& CT \left[ \frac{(1-x^2)\left(\left(1+x+\frac{1}{x}\right)^p-1\right)}{1+x+\frac{1}{x}-1}\right]\\
&\equiv_p& COEFF_{[x^{p-1}]} \left[  \frac{1-x^2}{1+x^2}\right] \\
&\equiv_p& COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x^2}\right]  -  COEFF_{[x^{p-3}]} \left[ \frac{1}{1+x^2}\right] \\
\end{eqnarray*}

\noindent The result follows from series expansion of $\displaystyle{\frac{1}{1+x^2}}$ and the last congruence.

\vskip .2in

\noindent
{\bf Corollary 3}:  Let $a(n)$ be the constant term of $\displaystyle{(1-x^2)\left(1+x+\frac{1}{x}\right)^n}$ and let

$$
A(r;p):=\sum_{n=0}^{rp-1}  a(n)\,. 
$$
 
\noindent 
Then,  $A(2;p)\,\text{mod}\, p \,=\left\{\begin{array}{l}
4 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  4\\
-4 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 3 \mod 4\,\,\,.\\
\end{array}\right.
$

\noindent {\bf Proof}: 

\begin{eqnarray*}
\sum_{n=0}^{2p-1} a(n) &=& \sum_{n=0}^{2p-1} CT \left[(1-x^2)\left(1+x+\frac{1}{x}\right)^n\right] \\
&=& CT\left[ \frac{(1-x^2)\left(\left(1+x+\frac{1}{x}\right)^{2p}-1\right)}{1+x+\frac{1}{x}-1}\right]\\
&=& CT \left[ \frac{(1-x^2)\left(\left(3+2x+x^2+\frac{2}{x}+\frac{1}{x^2}\right)^{p}-1\right)}{1+x+\frac{1}{x}-1}\right]\\
&=& CT\left[ \frac{(1-x^2)\left(\left(3+2x^p+x^{2p}+\frac{2}{x^p}+\frac{1}{x^{2p}}\right)-1\right)}{1+x+\frac{1}{x}-1}\right]\\
&\equiv_p& COEFF_{[x^{2p-1}]} \left[  \frac{(1-x^2)(1+2x^p)}{1+x^2}\right] \\
&\equiv_p& COEFF_{[x^{2p-1}]} \left[ \frac{1}{1+x^2}\right]  + 2COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x^2}\right] \\& -&COEFF_{[x^{2p-3}]} \left[ \frac{1}{1+x^2}\right] -2COEFF_{[x^{p-3}]} \left[ \frac{1}{1+x^2}\right]\,. \\
\end{eqnarray*}

\noindent The result follows from Theorem 2 and the last congruence. 

\vskip .2in

\noindent From the above theorems and corollaries, it is easy to observe that partial sums with upper summation limit of the form  $rp-1$, for $r >1$, can always be expressed in terms of the sum with upper summation limit $p-1$. This observation leads us to the following simplification of Theorem 2.1 in [2]. 

\vskip .2in

\noindent 
{\bf Theorem 3 }. Let $P(x)$  be a Laurent polynomial in $x$ and let $p$ be a prime.  Let $R(x)$ be the denominator, after clearing, of the expression 
$$
\frac{P(x^p)-1}{P(x)-1}. 
$$

\noindent  Then, for any positive integer $r$ and Laurent polynomial $Q(x)$,

$$
\left( \sum_{n=0}^{rp-1} CT \left[P(x)^nQ(x)\right] \right) \text{mod} \,\, p\,\,,
$$

\noindent is congruent to a finite
linear combination of finite terms of coefficients of the rational function $\displaystyle{\frac{1}{R(x)}}$.

\vskip .2in

\noindent {\bf Multi-Sums and Multi-Variables}\\


\noindent 
{\bf Theorem 4}. Let $p$ be a prime number and let $r$ and $s$ be a positive integers.  Let 

$$
A(r,s;p) := \sum_{n=0}^{rp-1}\sum_{m=0}^{sp-1} { n+m \choose m}^2\,\,.
$$

\vskip .2in
\noindent 
Then,  $A(1,1;p) \,\text{mod}\,p\,=\left\{\begin{array}{l}
0 ,\,\,\, \,\,\,\, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,0 \mod 3\\
1 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-1 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$

\vskip .2in
\noindent 
Furthermore,  $\displaystyle{A(2,2;p) \equiv_p COEFF_{[x^{2p-1}y^{2p-1}]} \frac{1+4x^p+4y^p+16x^py^p}{(1+x+xy)(1+y+xy)}}$.\\

\vskip .2in
\noindent 
{\bf{Proof}}: Let  $\displaystyle{P(x,y)=\left(1+y\right)\left(1+\frac{1}{x}\right)}$ and $\displaystyle{ Q(x,y) = \left(1+x\right)\left(1+\frac{1}{y}\right)}$. First observe that 
$$
 { n+m \choose m}^2 =  { n+m \choose m} { n+m \choose n}=CT\left( P(x,y)^n Q(x,y)^m\right)\,\,.
$$

\noindent
Then,

\begin{eqnarray*}
 \sum_{m=0}^{p-1}\sum_{n=0}^{p-1}  { m+n \choose m}^2  &=& \sum_{m=0}^{p-1}\sum_{n=0}^{p-1}  CT\left[ P(x,y) ^nQ(x,y)^m\right]\\
&=&\sum_{m=0}^{p-1} CT\left[\frac{P(x,y)^{p}-1)Q(x,y)^m}{P(x,y)-1}\right] \\
&=&CT\left[\left(\frac{P(x,y)^{p}-1}{P(x,y)-1}\right ) \left(\frac{Q(x,y)^{p}-1}{Q(x,y)-1}\right)\right]
\end{eqnarray*}

\noindent Using $(a+b)^p \equiv (a^p+b^p)\,\text{mod}\,p$, we can pass to mod $p$ as above

\begin{eqnarray*}
\sum_{m=0}^{p-1}\sum_{n=0}^{p-1}  { m+n \choose m}^2  &\equiv_p&CT\left[\left(\frac{P(x^p,y^p)-1}{P(x,y)-1}\right ) \left(\frac{Q(x^p,y^p)-1}{Q(x,y)-1}\right)\right]\\
&\equiv_p&CT\left[\frac{(1+y^p+x^py^p)(1+x^p+x^py^p)}{(1+y+xy)(1+x+xy)x^{p-1}y^{p-1}}\right]\\
&\equiv_p&COEFF_{[x^{p-1}y^{p-1}]}\left[\frac{(1+y^p+x^py^p)(1+x^p+x^py^p)}{(1+y+xy)(1+x+xy)}\right]\\
&\equiv_p&COEFF_{[x^{p-1}y^{p-1}]}\left[\frac{1}{(1+y+xy)(1+x+xy)}\right]\\
\end{eqnarray*}


\noindent
Using the Apagodu-Zeilberger algorithm ([1]), the diagonal coefficients satisfy the recurrence equation $N^2+N+1=0$  with initial conditions $a(0)=1,a(1)=1, a(2)=0$. The result now follows from the fact that this recurrence is equivalent to $N^3-1=0$ and the solution to this recurrence is given by: \\

\noindent 
$$
a(n)=\left\{\begin{array}{l}
1 ,\,\,\, \,\,\,\, \,\text{if} \,\,\,n\,\,\,\,\equiv \,\,0 \mod 3\\
1 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,n\,\,\,\,\equiv \,\,1 \mod  3\\
0 ,\,\,\, \,\,\, \, \,  \text{if} \,\,\,n\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$$

\noindent  Note that our partial sum is congruent to $a(p-1)$, not $a(p)$.

\vskip .2in

\noindent 
For the $A(2,2;p)$, we have  

\begin{eqnarray*}
\sum_{m=0}^{2p-1}\sum_{n=0}^{2p-1}  { m+n \choose m}^2  &\equiv_p&CT\left[\left(\frac{P(x^p,y^p)^2-1}{P(x,y)-1}\right ) \left(\frac{Q(x^p,y^p)^2-1}{Q(x,y)-1}\right)\right]\\
&\equiv_p&CT\left[\frac{(1+y^p+x^py^p)^2(1+x^p+x^py^p)^2}{(1+y+xy)(1+x+xy)x^{p-1}y^{p-1}}\right]\\
&\equiv_p&COEFF_{[x^{2p-1}y^{2p-1}]}\left[\frac{(1+y^p+x^py^p)^2(1+x^p+x^py^p)^2}{(1+y+xy)(1+x+xy)}\right]\\
&\equiv_p&COEFF_{[x^{2p-1}y^{2p-1}]}\left[\frac{1+4x^p+4y^p+16x^py^p}{(1+x+xy)(1+y+xy)}\right]\\
\end{eqnarray*}

\noindent It follows that, 

$$\displaystyle{A(2,2;p) \equiv_p   COEFF_{[x^{2p-1}y^{2p-1}]} \frac{1+4x^p+4y^p+16x^py^p}{(1+x+xy)(1+y+xy)}}\,\,.$$

\noindent By symmetry, it simplifies to  

$$
A(2,2;p) \equiv_p COEFF_{[x^{2p-1}y^{2p-1}]} \frac{1}{(1+x+xy)(1+y+xy)} +
$$ 
$$
8COEFF_{[x^{p-1}y^{2p-1}]} \frac{1}{(1+x+xy)(1+y+xy)}+ 16COEFF_{[x^{p-1}y^{p-1}]} \frac{1}{(1+x+xy)(1+y+xy)}
$$

\vskip .2in


\noindent Based on computer calculations, we conjecture other values of $r$ and $s$ that admits a nice form.  These congruence are also true mod $p^2$. The congruences with higher power of $p$ are called supercongruence and the present method can't handle them.
\vskip .2in

\begin{enumerate}

\item
For $p\geq 17$, $A(2,2;p)\,\text{mod}\,p\,=\left\{\begin{array}{l}
7 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-7 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$

\item

For $p\geq 37$, $A(2,3;p)\,\text{mod}\,p\,=\left\{\begin{array}{l}
17 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-17 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$

\item

For $p\geq 127$,  $A(3,3;p)\,\text{mod}\,p\,=\left\{\begin{array}{l}
63 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-63 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$

\item
 $\displaystyle{A(1,1;p) \equiv 1 \,\,(\text{mod} \, p^2)}$ .\\

\item

For $p\geq 5$, $A(2,2;p)\,\text{mod}\,p^2\,=\left\{\begin{array}{l}
7 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-7 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$


\item

For $p\geq 7$, $A(2,3;p)\,\text{mod}\,p^2\,=\left\{\begin{array}{l}
17 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-17 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$


\item
For $p\geq 17$,  $A(3,3;p) \,\text{mod}\,p^2\,=\left\{\begin{array}{l}
63 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-63 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$

\end{enumerate}

\vskip .2in

\noindent {\bf Remark}: If we take the third power of the summand in Theorem 4 and define 

$$
C(r,s;p):=\sum_{n=0}^{rp-1}\sum_{m=0}^{sp-1} { n+m \choose m}^3\,\,,
$$

\noindent  then, 

$$
 { n+m \choose m}^3 =  CT \left[ \frac{(1+x)^{m+n}}{x^m}\frac{ (1+y)^{m+n}}{y^m}\frac{ (1+z)^{m+n}}{z^n}\right]\,\,.
$$

\noindent with $\displaystyle{P(x,y,z)=\left(1+\frac{1}{x}\right)\left(1+\frac{1}{y}\right)\left(1+z\right)}$ and $\displaystyle{ Q(x,y,z) = \left(1+x\right)\left(1+y\right)\left(1+\frac{1}{z}\right)}$, we have

$$
 { n+m \choose m}^3 =  CT\left(( P(x,y)^m Q(x,y)^n\right)\,\,.
$$

\noindent and proceeding as above, we get

$$
C(1,1;p) \equiv COEFF_{[x^{p-1}y^{p-1}z^{p-1}]}\left[\frac{1}{p(x,y,z)q(x,y,z)}\right] \,\text{mod}\,p\,,
$$

\vskip .2in
\noindent where $p(x,y,z)=1+x+y+xy+xz+yz+xyz$ and $q(x,y,z)=1+y+z+xy+xz+yz+xyz$.  

\vskip .2in
\noindent {\bf Theorem 5}.  Let $p>2 $ be prime, and $r, s$ and $t$ be positive integers. Define
$$
A(r,s,t;p):=\sum_{m_1=0}^{rp-1}\sum_{m_2=0}^{sp-1} \sum_{m_3=0}^{tp-1} { m_1+m_2+m_3 \choose m_1,m_2,m_3}   \,\,.
$$

\noindent  Then,   $\displaystyle{A(1,1,1;p) \equiv 1 \,\text{mod}\,p\,}$.    \\


\noindent  {\bf Proof}: First observe that $\displaystyle{ { m_1+m_2+m_3 \choose m_1,m_2,m_3}= CT \left[\frac{(x+y+z)^{m_1+m_2+m_3}}{x^{m_1}y^{m_2}z^{m_3}}\right]}$.

\noindent Hence

\begin{eqnarray*}
\sum_{0 \leq m_1, m_2, m_3 \leq p-1}{ m_1+m_2+m_3 \choose m_1,m_2,m_3}  &=& \sum_{0 \leq m_1, m_2, m_3 \leq p-1} CT [(x+y+z)^(m_1+m_2+m_3)/(x^{m_1}y^{m_2}z^{m_3})]\\
&=&CT\left[\sum_{0 \leq m_1, m_2, m_3 \leq p-1}\frac{ (x+y+z)^(m_1+m_2+m_3)}{x^{m_1}y^{m_2}z^{m_3}}\right]\\
&=&CT[\sum_{0 \leq m_1, m_2, m_3 \leq p-1} \frac{(x+y+z)^{m_1}}{x^{m_1}}\frac{ (x+y+z)^{m_2}}{y^{m_2}} \frac{(x+y+z)^{m_3}}{y^{m_3}}\\
&=&CT[\left ( \sum_{0 \leq m_1 \leq p-1} \left(\frac{x+y+z}{x}\right)^{m_1}  \right )\left ( \sum_{0 \leq m_2 \leq p-1 } \left (\frac{x+y+z}{y}\right)^{m_2}   \right )\\
& &\left ( \sum_{0 \leq m_3 \leq p-1}   \left (\frac{x+y+z}{z}\right)^{m_3} \right )\\
&=&CT\left[  \frac{(\frac{x+y+z}{x})^p -1}{\frac{x+y+z}{x}-1}\times \frac{(\frac{x+y+z}{y})^p -1}{\frac{x+y+z}{y}-1} \times\frac{(\frac{x+y+z}{z})^p -1}{\frac{x+y+z}{z}-1}\right]\\
&=&COEFF_{[x^{p-1}y^{p-1}z^{p-1}]} [ \frac{(x+y+z)^p -x^p}{y+z}\times\frac{(x+y+z)^p -y^p}{x+z} \times\\
&  & \frac{(x+y+z)^p -z^p}{x+y}]\,.
\end{eqnarray*}

\noindent So far this is true for all $p$, not only $p$ prime. Now take it mod $p$ and get, since 
$ (x+y+z)^p \equiv_p (x^p+y^p+z^p)$,


\begin{eqnarray*}
A(1,1,1;p)&=&COEFF_{[x^{p-1}y^{p-1}z^{p-1}]} \left(\frac{y^p+z^p}{y+z} \times \frac{x^p+z^p}{x+z}\times\frac{y^p+z^p}{y+z}\right)\\
&=& COEFF_{[x^{p-1}y^{p-1}z^{p-1}]} \left(y^{p-1}z^0-  y^{p-2}z+   y^{p-3}z^2+  ... +y^{0}z^{p-1}\right) \times\\
& &\left(x^{p-1}z^0-  x^{p-2}z+   x^{p-3}z^2+  ... +x^{0}z^{p-1}\right)\times \left(x^{p-1}y^0-  x^{p-2}y+   x^{p-3}y^2+  ... +x^{0}y^{p-1}\right)\\
&=&COEFF_{[x^{p-1}y^{p-1}z^{p-1}]}[\left(\sum_{j=0}^{p-1}(-1)^jx^{p-1-j}y^j\right)\left(\sum_{k=0}^{p-1}(-1)^{k+1}z^{p-1-k}x^k\right)\left(\sum_{l=0}^{p-1}(-1)^ly^{p-1-l}z^l\right)]\,.
\end{eqnarray*}


\vskip .2in

\noindent It is easy to see that to extract the
$x^{p-1}y^{p-1}z^{p-1}$ term in the above triple sum, we need $j=k=l=(p-1)/2$, and hence get $(-1)^{3*(p-1)/2}$
expansion by multiplying $(x^{p-1-j}y^j) (z^{p-1-k}x^k) (y^{p-1-l}z^l)$ exactly when 
$j=k=l=(p-1)/2$. Hence the 
coefficient of $x^{p-1}y^{p-1}z^{p-1}$
 is 

$\displaystyle{\sum_{j=0}^{p-1}(-1)^{3j}=\sum_{j=0}^{p-1}(-1)^{j}}$. It follows that the coefficient is 1 for $p>2$ and 0 for $p=2$. This completes the proof.


\vskip .2in

\noindent  We make the following conjectures based on computer calculations.
\begin{enumerate}
\item $\displaystyle{A(1,1,2;p) \equiv\, 2 \, \,(\text{mod}\, p)}$,  for $p\geq 5$.
\item $\displaystyle{A(1,2,2;p) \equiv \,5 \, \,(\text{mod}\, p)}$ , for $p\geq 11$.
\item $\displaystyle{A(2,2,2;p) \equiv\, 16\, \,(\text{mod}\, p)}$. for $p\geq 37$.
\end{enumerate}

\noindent The following supercongruences are also true.  
\begin{enumerate}
\item $\displaystyle{A(1,1,1;p) \equiv \, 1 \, \,(\text{mod}\,p^2)}$,  for $p\geq 2$.
\item $\displaystyle{A(1,1,1;p) \equiv \, 1 \, \,(\text{mod}\,p^3)}$,  for $p\geq 2$.
\item $\displaystyle{A(1,1,2;p) \equiv\, 2 \, \,(\text{mod}\, p^2)}$,  for $p\geq 3$. 
\item $\displaystyle{A(1,1,2;p) \equiv\, 2 \, \,(\text{mod}\, p^3)}$,  for $p\geq 3$. 
\item $\displaystyle{A(1,2,2;p) \equiv \,5 \, \,(\text{mod}\, p^2)}$,  for $p\geq 5$ .
\item $\displaystyle{A(1,2,2;p) \equiv \,5 \, \,(\text{mod}\, p^3)}$,  for $p\geq 3$ .
\item $\displaystyle{A(2,2,2;p) \equiv\, 16\, \,(\text{mod}\, p^2)}$,  for $p\geq 7$. 
\item $\displaystyle{A(2,2,2;p) \equiv\, 16\, \,(\text{mod}\, p^3)}$,  for $p\geq 5$. \\
\end{enumerate}

\noindent Similarly, if we define  

$$
A(r,s,t,u;p):=\sum_{m_1=0}^{rp-1}\sum_{m_2=0}^{sp-1} \sum_{m_3=0}^{tp-1}\sum_{m_4=0}^{up-1} { m_1+m_2+m_3 +m_4 \choose m_1,m_2,m_3,m_4}   \,\,,
$$


\noindent for prime $p$ and positive integers $r,s,t$ and $u$,  then we get the following conjectures.

\begin{enumerate}
\item $\displaystyle{A(1,1,1,1;p) \equiv\, 1 \,\, (\text{mod}\, p)}$, for $p \geq 3$ .
\item $\displaystyle{A(1,1,1,2;p) \equiv\, 2\,\,(\text{mod}\, p)}$,  for $p\geq 5$. 
\item $\displaystyle{A(1,1,2,2;p) \equiv \, 5\,\,( \text{mod}\, p)}$,  for $p\geq 11$ .
\item $\displaystyle{A(1,2,2,2;p) \equiv  16 \, \,(\text{mod}\, p)}$,  for $p\geq 37 $ . 
\end{enumerate}

\vskip .2in

\noindent Our last observation is the general multinomial case.  For prime $p>2 $ and positive integers $r_i, i=1,2,3,\ldots,k$,  if we define

$$
A(r_1,r_2,\ldots ,r_k;p):=\sum_{m_1=0}^{r_1p-1}\sum_{m_2=0}^{r_2p-1}\ldots  \sum_{m_a=0}^{r_kp-1} { m_1+m_2\ldots+m_a \choose m_1,m_2,\ldots,m_k}   \,\,.
$$


\noindent Then, computer outputs support the following conjectures


\begin{enumerate}
 \item $\displaystyle{A(1,1,\ldots,1;p)=1\,\,(\text{mod}\,\,p)}$, for $p\geq 2$.
\item $\displaystyle{A(1,1,\ldots,1;p)=1\,\,(\text{mod}\,\,p^{2})}$, for $p\geq 2$.
\item $\displaystyle{A(1,1,\ldots,1;p)=1\,\,(\text{mod}\,\,p^{3})}$, for $p\geq 2$.
\end{enumerate}

\vskip .2in

\noindent {\bf Acknowledgment} The author would like to thank Doron Zeilberger without whose insightful comments and discussions this project would not have come to fruition. 

\begin{thebibliography}{1}

\bibitem{AZ}
M. ~Apagodu and D. ~Zeilberger, Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory, Adv. Appl. Math. 37(2006).

\bibitem{CHZ} 
 William Y.C. Chen, Qing-Hu Hou, and D. ~Zeilberger, Automated Discovery and Proof of Congruence Theorems for Partial Sums of Combinatorial Sequences, J. of Difference Equations and Applications (on-line), 
DOI:10.1080/10236198.2016.1142541.

\end{thebibliography}

\end{document} 
