\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{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}{-.1in}
\setlength{\textheight}{8.4in}

\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}
\newtheorem{openproblem}[theorem]{Open Problem}

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

\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

\begin{center}
\vskip 1cm{\LARGE\bf 
An Integer Sequence Motivated by \\
\vskip .1in
Generalized Quadrangles 
}
\vskip 1cm
\large
Brian G.\ Kronenthal\\
Department of Mathematics\\
Kutztown University of Pennsylvania\\
15200 Kutztown Road\\
Kutztown, PA 19530-9335\\
USA \\
\href{mailto:kronenthal@kutztown.edu}{\tt kronenthal@kutztown.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
In this paper, we prove a closed form for a sequence motivated by the search for new generalized quadrangles of odd order.  We present two proofs: a direct proof to explain the closed form's derivation and a shorter inductive argument.  The sequence in question is derived from congruences that arise from applying the Hermite-Dickson criterion to a permutation polynomial that is related to the girth of monomial graphs.
\end{abstract}


\section{Introduction}

In this section, we first present some definitions and notation that we will need (Section \ref{Section:Defs}).  Then we provide some background and motivation for the results presented in this paper (Section \ref{Section:MGGQMotivation}).

\subsection{Fundamental definitions and notation}\label{Section:Defs}

We begin with some definitions.  A \textit{graph} $\mathcal{G}=(V,E)$ consists of a set $V$ of vertices and a set $E$ of edges.  The \textit{order} of a graph is the number of vertices it contains (namely $|V|$).  Edges are two-element subsets of $V$; if $\{u,v\}\in E$ for some $u,v\in V$, then $u$ and $v$ are said to be \textit{adjacent}.  The \textit{degree of a vertex $v$} is the number of vertices adjacent to $v$.  If every $v\in V$ has the same finite degree $t$, then $\mathcal{G}$ is called a \textit{$t$-regular graph}.  A \textit{$uv$-walk of length $k\geq1$} is a sequence $(u=v_0,e_1,v_1,e_2,v_2,\ldots,e_k,v_k=v)$ of alternating vertices and edges, where $e_i=\{v_{i-1},v_i\}$ for $i=1,\ldots,k$.  For every vertex $u$, we define $(u)$ to be a \textit{$uu$-walk of length 0}.  A graph $\mathcal{G}$ is \textit{connected} if for every pair of vertices $u$ and $v$, there exists a $uv$-walk in $\mathcal{G}$.  In a connected graph, the \textit{distance} from vertex $u$ to vertex $v$ is the length of a shortest $uv$-walk.  The \textit{diameter} of a connected graph $\mathcal{G}$ is the largest distance between any two of its vertices.  A \textit{$k$-cycle} $C_k$ is a $uv$-walk of length $k\geq3$ where $u=v$, but no other vertices repeat.  If $\mathcal{G}$ contains any cycles, the \textit{girth} of $\mathcal{G}$ is the length of a shortest cycle in $\mathcal{G}$.  A connected graph that does not contain any cycles is called a \textit{tree}.  A graph $\mathcal{G}$ is \textit{bipartite} if its vertex set may be partitioned into two sets, say $P$ and $L$, such that every edge $\{x,y\}$ has the property that $x\in P$ and $y\in L$ (or vice versa).  Two graphs $\mathcal{G}_1=(V_1,E_1)$ and $\mathcal{G}_2=(V_2,E_2)$ are \textit{isomorphic} if there exists a bijection $\varphi:V_1\to V_2$ such that $x,y\in V_1$ are adjacent if and only if $\varphi(x),\varphi(y)\in V_2$ are adjacent.  Other standard graph theory definitions may be found, for example, in Bollob\'{a}s \cite{Bollobas}.

Let $\mathbb{F}_q$ denote the finite field of order $q$.  A \textit{permutation polynomial of $\mathbb{F}_q$} is a polynomial $f\in\mathbb{F}_q[x]$ whose induced function on $\mathbb{F}_q$, defined by $a\mapsto f(a)$, is a bijection.  Let $f_2,f_3:\mathbb{F}_q^2\to\mathbb{F}_q$ be functions.  An \textit{algebraically defined graph $G_q(f_2,f_3)$ of dimension three} is a bipartite graph with partite sets $P=\mathbb{F}_q^3=L$, and $(x_1,x_2,x_3)\in P$ is adjacent to $[y_1,y_2,y_3]\in L$ if $x_i+y_i=f_i(x_1,y_1)$ for $i=2,3$.  If both $f_2$ and $f_3$ are monomials, we call $G_q(f_2,f_3)$ a \textit{monomial graph}.  



\subsection{Motivation}\label{Section:MGGQMotivation}

One reason for studying monomial graphs is the desire to construct new generalized quadrangles of odd prime power order.  While typically viewed as incidence geometries (see Payne and Thas \cite{Payne-Thas}, Van Maldeghem \cite{VanMaldeghem}, and Benson \cite{Benson} for additional information), we will view generalized quadrangles from the perspective of their point-line incidence graphs, also known as Levi graphs.  In other words, for the remainder of this paper, we will adopt a purely graph-theoretical viewpoint.  Hence, we define a finite \textit{generalized quadrangle of order $q$}, denoted $GQ(q)$, to be a bipartite $(q+1)$-regular graph of girth eight and diameter four.  No $GQ(q)$ of non-prime power order is currently known.   Many examples of nonisomorphic $GQ(q)$ are known when $q$ is a power of 2.  However, for a given odd prime power $q$, only one $GQ(q)$ is known (up to graph isomorphism).


The \textit{affine part} of a generalized quadrangle is the subgraph induced by all vertices at distance three from a fixed edge. In all known $GQ(q)$ for odd prime powers $q$, the affine part is simply an isomorphic copy of $G_q(xy,xy^2)$, which we denote by $\Gamma_3(q)$.

Now, a primary motivation for Dmytrenko, Lazebnik, and Williford \cite{Monomial} and Kronenthal \cite{MGGQ} was to construct a new $GQ(q)$ of odd prime power order as follows. First, construct a $q$-regular girth eight graph that is not isomorphic to $\Gamma_3(q)$, and has vertex partition $P\cup L$ such that $|P|=q^3=|L|$.  Next, ``attach'' a tree to it in such a way that the result is a new generalized quadrangle.  

To address the first step, we note that our goal is to find an algebraically defined graph with many of the same properties as $\Gamma_3(q)$, a monomial graph.  Therefore, it is logical to first search for a replacement among monomial graphs.   This strategy was investigated by Dmytrenko, Lazebnik and Williford \cite{Monomial}, who conjectured that a suitable monomial graph does not exist.
\begin{conjecture}{\rm\cite{Monomial}}\label{MonomConj4}
Let $q=p^e$ be an odd prime power.  Then every monomial graph over $\mathbb{F}_q$ of girth at least eight is isomorphic to $\Gamma_3(q)$.  
\end{conjecture}
This conjecture is of particular interest because it stands in stark contrast to the case when $q$ is a power of 2, where the described strategy of constructing nonisomorphic generalized quadrangles succeeds.  See Payne \cite{Payne}, Van Maldeghem \cite{VanMaldeghem}, and Cherowitzo \cite{Cherowitzo} for additional information.

Working towards a proof of Conjecture \ref{MonomConj4}, Dmytrenko, Lazebnik and Williford \cite{Monomial} proved the following result:
\begin{theorem}\label{MonomialThm1-2}
Let $q=p^e$ be an odd prime power.  Then every monomial graph of girth at least eight is isomorphic to the graph $G_q(xy,x^ky^{2k})$, where $k$ is not divisible by $p$.  If $q \geq 5$, the following statements also
hold:
\begin{enumerate}
 \item\label{Monom1.1} $1\leq k<\frac{q-1}{2}$, $\gcd(k,q-1)=1$, and $k\equiv1 \pmod{p-1}$.
 \item\label{Monom1.2} $((x+1)^{2k}-1)x^{q-1-k}-2x^{q-1}\in\mathbb{F}_q[x]$ is a permutation polynomial of $\mathbb{F}_q$.
\end{enumerate}
\end{theorem}
The permutation polynomial from part \ref{Monom1.2} of Theorem \ref{MonomialThm1-2} was then used in conjunction with the Hermite-Dickson criterion:
\begin{theorem}[Hermite-Dickson criterion] {\rm(See Hermite \cite{Hermite} and Dickson \cite{Dickson}; see also Lidl and Niederreiter \cite{FF}.)}
Let $\mathbb{F}_q$ be of characteristic $p$.  Then $f\in\mathbb{F}_q[x]$ is a permutation polynomial of $\mathbb{F}_q$ if and only if the following two conditions hold:
\begin{enumerate}
\item $f$ has exactly one root in $\mathbb{F}_q$; and 	
\item for each integer $t$ with $1\leq t\leq q-2$ and $p\nmid t$, the reduction of $f^t\pmod{x^q-x}$ has degree at most $q-2$.
\end{enumerate}
\end{theorem}
Indeed, let $e\geq1$ be an integer, $p$ an odd prime, and $q=p^e\geq5$.  Let $G$ be a monomial graph of girth at least eight.  Then by Theorem \ref{MonomialThm1-2}, $G$ is isomorphic to $G_q(xy,x^ky^{2k})$ and \[F=((x+1)^{2k}-1)x^{q-1-k}-2x^{q-1}\in\mathbb{F}_q[x]\] is a permutation polynomial of $\mathbb{F}_q$.  The Hermite-Dickson criterion implies that the coefficient of $x^{q-1}$ in $F^t \pmod{x^q-x}$ must be zero for all $1\leq t\leq q-2$.  This yields
\begin{equation}\label{GeneralCong}\sum_{j=0}^t(-2)^{j}{t\choose j}\sum_{h=0}^{\left\lfloor\frac{t-j}{2}\right\rfloor}(-1)^{h}{t-j\choose h}{2k(t-j-h)\choose k(t-j)}\equiv 0\pmod{p};\end{equation} 
for details of this derivation, see Kronenthal \cite{MGGQ}.

We now consider instances of (\ref{GeneralCong}) for some small values of $t$; the result is a sequence of congruences.  We use ($\kappa_{i}$) to denote the congruence resulting from the substitution $t=i$.  When $t=1$, (\ref{GeneralCong}) yields $-2+{2 k \choose k}\equiv 0\pmod{p}$, and so \begin{equation}{2 k\choose k}\equiv2\pmod{p}.\label{Cong1}\tag{$\kappa_1$}\end{equation}  When $t=2$, we have $2-4 {2 k \choose k}+{4 k\choose 2 k}\equiv 0\pmod{p}$; substituting (\ref{Cong1}) implies $2-4\cdot 2+{4 k\choose 2 k}\equiv 0\pmod{p}$, and therefore \begin{equation}{4 k\choose 2 k}\equiv6\pmod{p}.\label{Cong2}\tag{$\kappa_2$}\end{equation}  Continuing this process of evaluating (\ref{GeneralCong}) for subsequent values of $t$, and back-substituting previous congruences at each step, yields the following:
\begin{align*}
{6 k\choose 3 k} - 3 {4 k\choose 3 k}&\equiv8\pmod{p}\label{Cong3}\tag{$\kappa_3$}\\
{8 k\choose 4 k} - 4 {6 k\choose 4 k}&\equiv10\pmod{p}\label{Cong4}\tag{$\kappa_4$}\\
{10 k\choose 5 k} - 5 {8 k\choose 5 k} + 10 {6 k\choose 5 k}&\equiv32\pmod{p}\label{Cong5}\tag{$\kappa_5$}\\
{12 k\choose 6 k} - 6 {10 k\choose 6 k} + 15 {8 k\choose 6 k}&\equiv84\pmod{p}\label{Cong6}\tag{$\kappa_6$}\\
{14 k\choose 7 k} - 7 {12 k\choose 7 k} + 21 {10 k\choose 7 k} - 35 {8 k\choose 7 k}&\equiv 128\pmod{p}\label{Cong7}\tag{$\kappa_7$}\\
{16 k\choose 8 k} - 8 {14 k\choose 8 k} + 28 {12 k\choose 8 k}- 56 {10 k\choose 8 k}&\equiv186\pmod{p}\label{Cong8}\tag{$\kappa_8$}\\
&\;\;\vdots
\end{align*}
In general, we obtain that for every integer $t\geq1$,
\begin{equation}\label{Congt}\tag{$\kappa_{t}$}
\sum_{h=0}^{\floor{\frac{t-1}{2}}}(-1)^{h}{t\choose h}{2k(t-h)\choose kt}\equiv b_{t}\pmod{p},
\end{equation}
where the integer $b_{t}$ represents the terms in (\ref{GeneralCong}) not involving $k$ (after back-substituting (\ref{Cong1}), \ldots, ($\kappa_{t-1}$)).  The sequence $(b_t)_{t\geq1}$ appears in Sloane's Online Encyclopedia of Integer Sequences as sequence number \seqnum{A247984} \cite{Sloane}: 
\begin{quote}
2, 6, 8, 10, 32, 84, 128, 186, 512, 1276, 2048, 3172, 8192, 19816, 32768, 52666, 131072, 310764, 524288, 863820, 2097152, 4899736, 8388608, 14073060, 33554432, 77509464, 134217728, 228318856, 536870912, 1228859344, \ldots.
\end{quote}
The following theorem, our main result, states a closed form for $b_t$.

\begin{theorem}\label{BinomialCoefCongConstantTerm}
For all positive integers $t$, let $b_t$ be as defined in (\ref{Congt}).  Then   
\[b_t=\begin{cases}2^t,&\text{if $t$ is odd;}\\{\displaystyle2^t-(-1)^{t/2}{t\choose t/2},}&\text{if $t$ is even.}\end{cases}\]
\end{theorem}

Theorem \ref{BinomialCoefCongConstantTerm} first appeared as a comment, without proof, in Kronenthal \cite{MGGQ}.  The purpose of this paper is to prove Theorem \ref{BinomialCoefCongConstantTerm} in two ways.  In Section \ref{Section:DirectProof}, we prove the theorem directly (much like how we originally derived it).  In Section \ref{Section:InductiveProof}, we present a shorter inductive argument.

However, before ending this section, we note that after the change of variables $g=t-j$, (\ref{GeneralCong}) may be rewritten as 
\begin{equation}\label{GeneralCongVarChange}\sum_{g=0}^t(-2)^{t-g}{t\choose g}\sum_{h=0}^{\floor{g/2}}(-1)^{h}{g\choose h}{2k(g-h)\choose kg}\equiv 0\pmod{p}.\end{equation}
This will be used both in Section \ref{Section:DirectProof} and in Section \ref{Section:InductiveProof}.

\section{A direct proof}\label{Section:DirectProof}
In this section, we prove Theorem \ref{BinomialCoefCongConstantTerm} directly.  We begin with a number of preliminary results.

\begin{lemma}\label{ColSum} {\rm (Graham, Knuth, and Patashnik \cite[Equation 5.10]{Graham})} Let $n$ and $k$ be non-negative integers.  Then
\[\sum_{j=0}^n{j\choose k}={n+1\choose k+1}.\]
\end{lemma}

\begin{lemma}\label{FracBinomIdentity} {\rm (Graham, Knuth, and Patashnik \cite[Equation 5.5]{Graham})} Let $k\neq0$ be an integer.  Then
 \[{n\choose k}=\frac{n}{k}{n-1\choose k-1}.\]
\end{lemma}

\begin{lemma} \label{Gould1.47} {\rm (Gould \cite[Equation 1.47 with $x=1$]{Gould})}  For all $j\leq n$, 
\[\sum_{k=1}^n(-1)^k{n\choose k}\frac{k^j}{k+1}=(-1)^j\frac{1}{n+1}.\]
\end{lemma}

In the following, let $\mathbb{N}=\{1,2,3,\ldots\}$ denote the set of natural numbers. 

\begin{lemma}\label{InnerSumPIELemma} Let $j,n\in\mathbb{N}$.  Then
\[\mathop{\sum_{y_1+\cdots+y_j=n}}_{y_1,\ldots,y_j\in\mathbb{N}}{n\choose y_1,y_2,\ldots,y_{j-1},y_j}=\sum_{k=1}^j(-1)^{j-k}k^n{j\choose j-k}.\]
\end{lemma}

Lemma \ref{InnerSumPIELemma} follows directly from Kao and Zetterberg \cite[Theorem 2.2]{KaoZetterberg}.

\begin{lemma}\label{InnerSum}
Let $i,t\in\mathbb{N}$ such that $i<t$.  Then \[\sum_{j=1}^{t-i}\sum_{t>x_1>\cdots>x_j=i}(-1)^{j+1}{t\choose x_1}{x_1\choose x_2}\cdots{x_{j-1}\choose i}=(-1)^{t+i-1}{t\choose i},\] where $x_i\in\mathbb{N}$ for all $i=1,2,\ldots,j$.
\end{lemma}

\begin{proof} We have

${\displaystyle\sum_{j=1}^{t-i}\sum_{t>x_1>\cdots>x_j=i}(-1)^{j+1}{t\choose x_1}{x_1\choose x_2}\cdots{x_{j-1}\choose i}}$
\begin{align*}
&={t\choose i}\sum_{j=1}^{t-i}(-1)^{j+1}\sum_{t>x_1>\cdots>x_j=i}{t-i\choose t-x_1,x_1-x_2,\ldots,x_{j-2}-x_{j-1},x_{j-1}-i}\\
&={t\choose i}\sum_{j=1}^{t-i}(-1)^{j+1}\mathop{\sum_{y_1+\cdots+y_j=t-i}}_{y_1,\ldots,y_j\in\mathbb{N}}{t-i\choose y_1,y_2,\ldots,y_{j-1},y_j}\\
&={t\choose i}\sum_{j=1}^{t-i}(-1)^{j+1}\sum_{k=1}^j(-1)^{j-k}k^{t-i}{j\choose j-k}\quad\text{(by Lemma \ref{InnerSumPIELemma} with $n=t-i$)}\\
&={t\choose i} \sum_{k=1}^{t-i}(-1)^{k-1}k^{t-i}\sum_{j=0}^{t-i}{j\choose k}\\
&={t\choose i} \sum_{k=1}^{t-i}(-1)^{k-1}k^{t-i}{t-i+1\choose k+1}\quad\text{(by Lemma \ref{ColSum})}\\
&=-{t\choose i} (t-i+1)\sum_{k=1}^{t-i}(-1)^{k}{t-i\choose k}\frac{k^{t-i}}{1+k}\quad\text{(by Lemma \ref{FracBinomIdentity})}\\
&=-{t\choose i} (t-i+1)\left((-1)^{t-i}\frac{1}{t-i+1}\right)\quad\text{(by Lemma \ref{Gould1.47} with $n=t-i$ and $j=t-i$)}\\
&={t\choose i}(-1)^{t+i-1}.
\end{align*}
\end{proof}

\begin{lemma}\label{Graham5.24}{\rm (Graham, Knuth, and Patashnik \cite[Equation 5.24]{Graham})} Let $l\geq0$, $m$, and $n$ be integers.  Then
\[\sum_k{l\choose m+k}{s+k\choose n}(-1)^k=(-1)^{l+m}{s-m\choose n-l}.\]
\end{lemma}

 
We now use (\ref{GeneralCongVarChange}) and the above lemmas to prove Theorem \ref{BinomialCoefCongConstantTerm}.  Define \[C_t=\sum_{g=0}^{\left\lfloor t/2\right\rfloor}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g},\]
\[L_t=\sum_{h=0}^{\floor{\frac{t-1}{2}}}(-1)^{h}{t\choose h}{2k(t-h)\choose kt},\]
and \[a_{t,u}=(-2)^{t-u}{t\choose u}.\]  Note that on the left-hand side of (\ref{GeneralCongVarChange}), $C_t$ is the constant term (i.e., the term not involving $k$, which comes from the terms with $h=g/2$ followed by the change of variables $g\mapsto 2g$), $L_t$ consists of all non-constant terms containing binomial coefficients of the form ${x\choose kt}$ for some $x$ ($L_t$ is the left-hand side of ($\kappa_t$)), and $a_{t,u}$ is the coefficient of $L_u$ when it appears in the calculation of $(\kappa_t)$.  Then (\ref{GeneralCongVarChange}) is equivalent to
\[ C_{t}+\sum_{g=1}^{t-1} a_{t,g}L_g+\sum_{h=0}^{\floor{\frac{t-1}{2}}}(-1)^{h}{t\choose h}{2k(t-h)\choose kt}\equiv 0\pmod{p},\]
and therefore congruence $(\kappa_t)$ may be rewritten as
\[\sum_{h=0}^{\floor{\frac{t-1}{2}}}(-1)^{h}{t\choose h}{2k(t-h)\choose kt}\equiv -C_{t}-\sum_{g=1}^{t-1} a_{t,g} L_g\pmod{p}.\]
In other words,
\[L_t\equiv -C_{t}-\sum_{g=1}^{t-1} a_{t,g} L_g\pmod{p}.\]
Expanding and back-substituting for some small values of $t$, we have:

\bigbreak

\begin{align*}
L_1&\equiv -C_1 \pmod{p}\\
 L_2&\equiv-a_{2,1}\cdot L_1-C_2\equiv a_{2,1}C_1-C_2\pmod{p}\\
L_3&\equiv-a_{3,2}\cdot L_2-a_{3,1}\cdot L_1-C_3\\
&\equiv-a_{3,2}(a_{2,1}C_1-C_2)+a_{3,1}C_1-C_3\\
&\equiv(a_{3,1}-a_{3,2}a_{2,1})C_1+a_{3,2}C_2-C_3\pmod{p}\\
L_4&\equiv-a_{4,3}\cdot L_3-a_{4,2}\cdot L_2-a_{4,1}\cdot L_1-C_4\\
&\equiv-a_{4,3}\bigl((a_{3,1}-a_{3,2}a_{2,1})C_1+a_{3,2}C_2-C_3\bigr)-a_{4,2}(a_{2,1}C_1-C_2)+a_{4,1}C_1-C_4\\
&\equiv(a_{4,1}-a_{4,3}a_{3,1}-a_{4,2}a_{2,1}+a_{4,3}a_{3,2}a_{2,1})C_1+(a_{4,2}-a_{4,3}a_{3,2})C_2+a_{4,3}C_3-C_4\pmod{p}
\end{align*}
In general, congruence $(\kappa_t)$ may be written as
\begin{equation}\label{Cong}
\begin{split}
L_t=\sum_{h=0}^{\floor{\frac{t-1}{2}}}(-1)^{h}{t\choose h}&{2k(t-h)\choose kt}\\
&\equiv -C_t+\sum_{i=1}^{t-1}C_i\sum_{j=1}^{t-i}\sum_{t>x_1>\cdots>x_j=i}(-1)^{j+1}a_{t,x_1}a_{x_1,x_2}\cdots a_{x_{j-1},i} \pmod{p}.
\end{split}
\end{equation}
We are now ready to prove our main result.

\begin{proof}[Proof of Theorem \ref{BinomialCoefCongConstantTerm}.]
From (\ref{Cong}), the right-hand side of congruence $(\kappa_t)$ is
\begin{align*}
b_t&=-C_t+\sum_{i=1}^tC_i\sum_{j=1}^{t-i}\sum_{t>x_1>\cdots>x_j=i}(-1)^{j+1}a_{t,x_1}a_{x_1,x_2}\cdots a_{x_{j-1},i}\\
&=-\sum_{g=0}^{\left\lfloor t/2\right\rfloor}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}+\sum_{i=1}^{t-1}\left(\sum_{g=0}^{\floor{i/2}}(-1)^{i-g}2^{i-2g}{i\choose 2g}{2g\choose g}\right)\\
&\quad\sum_{j=1}^{t-i}\sum_{t>x_1>\cdots>x_j=i}(-1)^{j+1}\left((-2)^{t-x_1}{t\choose x_1}\right)\left((-2)^{x_1-x_2}{x_1\choose x_2}\right)\cdots\left((-2)^{x_{j-1}-i}{x_{j-1}\choose i}\right) \\
&=-\sum_{g=0}^{\left\lfloor t/2\right\rfloor}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}\\
&\qquad+(-2)^t\sum_{i=1}^{t-1}\left(\sum_{j=1}^{t-i}\sum_{t>x_1>\cdots>x_j=i}(-1)^{j+1}{t\choose x_1}\cdots{x_{j-1}\choose i}\right)\sum_{g=0}^{\floor{i/2}}(-4)^{-g}{i\choose 2g}{2g\choose g}
\end{align*}
\begin{align*}
\vphantom{b_t}&=-\sum_{g=0}^{\left\lfloor t/2\right\rfloor}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}\\*
&\qquad+(-2)^t\sum_{i=1}^{t-1}\left({t\choose i}(-1)^{t+i-1}\right)\sum_{g=0}^{\floor{i/2}}(-4)^{-g}{i\choose 2g}{2g\choose g}\quad\text{(by Lemma \ref{InnerSum})}\\
&=(-2)^t\sum_{i=1}^t\left({t\choose i}(-1)^{t+i-1}\right)\sum_{g=0}^{\floor{i/2}}(-4)^{-g}{i\choose 2g}{2g\choose g}\\
&=(-1)^{t-1}(-2)^t\sum_{g=0}^{\floor{t/2}}(-4)^{-g}{2g\choose g}\sum_{i=1}^t(-1)^i{t\choose i}{i\choose 2g}\\
&=-2^t\left(\sum_{i=1}^t(-1)^i{t\choose i}+\sum_{g=1}^{\floor{t/2}}(-4)^{-g}{2g\choose g}\sum_{i=1}^t(-1)^i{t\choose i}{i\choose 2g}\right)\\
&=-2^t\left(-1+\sum_{g=1}^{\floor{t/2}}(-4)^{-g}{2g\choose g}\sum_{i=1}^t(-1)^i{t\choose i}{i\choose 2g}\right)\\
&=-2^t\left(-1+\sum_{g=1}^{\floor{t/2}}(-4)^{-g}{2g\choose g}(-1)^t{0\choose 2g-t}\right)\quad\text{(by Lemma \ref{Graham5.24})}\\
&=\begin{cases}2^t,&\text{if $t$ is odd;}\\ {\displaystyle -2^t\left(-1+(-4)^{-t/2}{t\choose t/2}(-1)^t\right)}, &\text{if $t$ is even;}\end{cases}\\
&=\begin{cases}2^t,&\text{if $t$ is odd;}\\{\displaystyle 2^t-(-1)^{t-t/2}2^t(2^2)^{-t/2}{t\choose t/2}},&\text{if $t$ is even;}\end{cases}\\
&=\begin{cases}2^t,&\text{if $t$ is odd;}\\{\displaystyle 2^t-(-1)^{t/2}{t\choose t/2}},&\text{if $t$ is even.}\end{cases}
\end{align*}
\end{proof}


\section{An inductive proof}\label{Section:InductiveProof}
In this section, we prove Theorem \ref{BinomialCoefCongConstantTerm} inductively.  
We begin by reorganizing the terms of (\ref{GeneralCongVarChange}).  The left-hand side of congruence (\ref{Congt}) will be those terms with $g=t$ and $h\neq g/2$, namely 
\[\sum_{h=0}^{\floor{\frac{t-1}{2}}}(-1)^{h}{t\choose h}{2k(t-h)\choose kt}.\]
We partition the remaining terms into two sums: 
\[\sum_{g=0}^t(-1)^{g/2}2^{t-g}{t\choose g}{g\choose g/2}=\sum_{g=0}^{\floor{t/2}}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}\]
contains all terms such that $h=g/2$, and 
\[\sum_{g=1}^{t-1}(-2)^{t-g}{t\choose g}\sum_{h=0}^{\floor{\frac{g-1}{2}}}(-1)^{h}{g\choose h}{2k(g-h)\choose kg}\]
contains all remaining terms (i.e., all terms such that $g\neq t$ and $h\neq g/2$).  Note that the inner sum is the left-hand side of congruence ($\kappa_g$).  Hence, we rewrite (\ref{GeneralCongVarChange}) as
\[\sum_{h=0}^{\floor{\frac{t-1}{2}}}(-1)^{h}{t\choose h}{2k(t-h)\choose kt}\equiv -\sum_{g=0}^{\floor{t/2}}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}-\sum_{g=1}^{t-1}(-2)^{t-g}{t\choose g}b_g \pmod{p},\] which proves   
\begin{equation}\label{bFormula}b_t=-\sum_{g=0}^{\floor{t/2}}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}-\sum_{g=1}^{t-1}(-2)^{t-g}{t\choose g}b_g.\end{equation}

Now, before proving our main result, we state a well-known lemma.
\begin{lemma}\label{BCSums} Let $t$ be a positive integer.  Then
${\displaystyle\sum_{g=0}^{\floor{t/2}}{t\choose 2g}=2^{t-1}}$ and
\[\sum_{g=1}^{\floor{t/2}}{t\choose 2g-1}=
\begin{cases}
2^{t-1},& \text{if $t$ is even;}\\
2^{t-1}-1,& \text{if $t$ is odd.}
\end{cases}
\]
\end{lemma}

\begin{proof}[Proof of Theorem \ref{BinomialCoefCongConstantTerm}.]  
We proceed by induction.  When $t=1$, (\ref{bFormula}) implies that \[b_1=-(-1)(2){1\choose 0}{0\choose 0}=2.\]  Now, suppose the result holds for all positive integers less than $t$.  Then from (\ref{bFormula}),
\begin{align*}
b_t&=-\sum_{g=0}^{\floor{t/2}}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}-\sum_{g=1}^{t-1}(-2)^{t-g}{t\choose g}b_g\\
&=-\sum_{g=0}^{\floor{t/2}}(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}-\sum_{g=0}^{\floor{\frac{t-1}{2}}}(-2)^{t-2g}{t\choose 2g}\left(2^{2g}-(-1)^g{2g\choose g}\right)\\
&\qquad-\sum_{g=1}^{\floor{t/2}}(-1)^{t+1}2^t{t\choose 2g-1}\\
&=-\sum_{g=0}^{\floor{t/2}}\left[(-1)^{t-g}2^{t-2g}{t\choose 2g}{2g\choose g}+(-2)^{t-2g}{t\choose 2g}\left(2^{2g}-(-1)^g{2g\choose g}\right)\right]\\
&\qquad+\left(\frac{1+(-1)^t}{2}\right)\left(2^t-(-1)^{t/2}{t\choose t/2}\right)-\sum_{g=1}^{\floor{t/2}}(-1)^{t+1}2^t{t\choose 2g-1}\\
&=-\sum_{g=0}^{\floor{t/2}}(-2)^t{t\choose 2g}+\left(\frac{1+(-1)^t}{2}\right)\left(2^t-(-1)^{t/2}{t\choose t/2}\right)-\sum_{g=1}^{\floor{t/2}}(-1)^{t+1}2^t{t\choose 2g-1}\\
&=(-1)^{t+1}2^t\sum_{g=0}^{\floor{t/2}}{t\choose 2g}+\left(\frac{1+(-1)^t}{2}\right)\left(2^t-(-1)^{t/2}{t\choose t/2}\right)
+(-2)^t\sum_{g=1}^{\floor{t/2}}{t\choose 2g-1}\\
&=(-1)^{t+1}2^{2t-1}+\left(\frac{1+(-1)^t}{2}\right)\left(2^t-(-1)^{t/2}{t\choose t/2}\right)+(-2)^t\left(2^{t-1}-\frac{1-(-1)^t}{2}\right) \\*
&\qquad\qquad\text{(by Lemma \ref{BCSums})}\\
&=\begin{cases}
        2^t,&\text{if $t$ is odd;}\\
	{\displaystyle 2^t-(-1)^{t/2}{t\choose t/2}},&\text{if $t$ is even.}
       \end{cases}
\end{align*}
\end{proof}


\section{Concluding remarks}

In this paper, we have provided direct and inductive proofs of Theorem \ref{BinomialCoefCongConstantTerm}.  One interesting future direction is as follows:

\begin{openproblem}\label{OpenProblem}
Prove Theorem \ref{BinomialCoefCongConstantTerm} using a combinatorial argument.
\end{openproblem}

We conclude by stating two results that were proven using Theorem \ref{BinomialCoefCongConstantTerm}.  Theorem \ref{DLWThm3} used $b_1$ and $b_2$, while Theorem \ref{KThm4} relied on Theorem \ref{BinomialCoefCongConstantTerm} in its entirety. 

\begin{theorem}\label{DLWThm3}{\rm(Dmytrenko, Lazebnik, and Williford \cite{Monomial})}
Let $q=p^e$ be an odd prime power, with $p\geq5$ and $e=2^a3^b$ for integers $a,b\geq0$.  Then every monomial graph over $\mathbb{F}_q$ of girth at least eight is isomorphic to $\Gamma_3(q)$ and has girth eight.  Furthermore, for $3\leq q\leq 10^{10}$, every monomial graph over $\mathbb{F}_q$ nonisomorphic to $\Gamma_3(q)$ has girth at most six.
\end{theorem}

\begin{theorem} \label{KThm4}{\rm(Kronenthal \cite{MGGQ})}
Let $q=p^e$ be an odd prime power and $e\geq2$.  Then there exists $p_0$ such that for all $p\geq p_0$, every monomial graph over $\mathbb{F}_q$ of girth at least eight is isomorphic to $\Gamma_3(q)$, and hence has girth exactly eight.  Furthermore, $p_0$ depends only on the largest prime divisor of $e$.  In particular:
\begin{enumerate}
 \item\label{Goal5} if $e=2^a3^b5^c$ with $a,b,c\geq0$, then $p_0=7$.
 \item\label{Goal7} if $e=2^a3^b5^c7^d$ with $a,b,c,d\geq0$, then $p_0=11$.
\item\label{Goal11} if $e=2^a3^b5^c7^d11^y$ with integers $a,b,c,d,y\geq0$, then $p_0=13$.
\end{enumerate}
\end{theorem}


\section{Acknowledgments}
The author is grateful to Felix Lazebnik for his support while conducting this research, as well as for suggesting Open Problem \ref{OpenProblem}.


\begin{thebibliography}{99}
\bibitem{Benson} C. T. Benson, On the structure of generalized quadrangles,  \textit{J. Algebra} \textbf{15} (1970) 443--454.

\bibitem{Bollobas} B. Bollob\'{a}s, \textit{Modern Graph Theory},
Springer, 1998.

\bibitem{Cherowitzo} W. E. Cherowitzo, \textit{Hyperovals in
Desarguesian planes: an electronic update},  informal notes, available at \\
\url{http://math.ucdenver.edu/~wcherowi/research/hyperoval/hypero.html}.

\bibitem{Dickson} L. E. Dickson, The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group, \textit{Ann. of Math.} \textbf{11} (1896--1897) 161--183.

\bibitem{Monomial} V. Dmytrenko, F. Lazebnik, and J. Williford, On
monomial graphs of girth eight, \textit{Finite Fields Appl.}
\textbf{13} (2007) 828--842.

\bibitem{Gould} H. W. Gould, \textit{Combinatorial Identities},
Morgantown, WV, 1972.

\bibitem{Graham} R. L. Graham, D. E. Knuth, and O. Patashnik,
\textit{Concrete Mathematics}, 2nd edition,
Addison-Wesley Publishing Company, 1994.

\bibitem{Hermite} C. Hermite, Sur les fonctions de sept lettres,
\textit{C. R. Math. Acad. Sci. Paris} \textbf{57} (1863) 750--757.

\bibitem{KaoZetterberg} R. C. Kao and L. H. Zetterberg, An identity for
the sum of multinomial coefficients,  \textit{Amer. Math. Monthly}
\textbf{64} (1957) 96--100.

\bibitem{MGGQ} B. G. Kronenthal, Monomial graphs and generalized
guadrangles, \textit{Finite Fields Appl.} \textbf{18} (2012) 674--684.

\bibitem{FF} R. Lidl and H. Niederreiter, \textit{Finite Fields},
Cambridge University Press, 2008.

\bibitem{Payne} S. E. Payne, A census of finite generalized
quadrangles, in \textit{Finite Geometries, Buildings, and Related Topics},
Oxford Univ. Press, 1990, pp.\ 29--36.

\bibitem{Payne-Thas} S. E. Payne and J. A. Thas, \textit{Finite
Generalized Quadrangles}, Research Notes in Mathematics, Vol.~110,
Pitman, 1984.

\bibitem{Sloane}N. J. A. Sloane, \textit{The On-Line Encyclopedia of
Integer Sequences}, published electronically at \url{http://oeis.org}.

\bibitem{VanMaldeghem} H. Van Maldeghem, \textit{Generalized
Polygons},  Birkh\"{a}user, 1998.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 12E99; Secondary 51E12.



\noindent \emph{Keywords: } permutation polynomial, monomial graph, generalized quadrangle, girth, cycle.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A246800} and
\seqnum{A247984}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 10 2015;
revised versions received  July 10 2015.
Published in {\it Journal of Integer Sequences}, July 16 2015.

\bigskip
\hrule
\bigskip

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


\end{document}
