\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 $ix_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: \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}\\ &=-\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}