An Integer Sequence Motivated by Generalized Quadrangles

Brian G. Kronenthal Department of Mathematics Kutztown University of Pennsylvania 15200 Kutztown Road Kutztown, PA 19530-9335 USA

                    kronenthal@kutztown.edu

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.

1 Introduction

In this section, we first present some definitions and notation that we will need (Section 1.1). Then we provide some background and motivation for the results presented in this paper (Section 1.2).

1.1 Fundamental definitions and notation

We begin with some definitions. A graph G = (V, E) consists of a set V of vertices and a set E of edges. The order of a graph is the number of vertices it contains (namely |V |). Edges are two-element subsets of V; if {u, v} ∈ E for some u, v ∈ V, then u and v are said to be adjacent. The degree of a vertex v is the number of vertices adjacent to v. If every v ∈ V has the same finite degree t, then G is called a t-regular graph. A uv-walk of length k ≥ 1 is a sequence (u = v_{0}, e_{1}, v_{1}, e_{2}, v_{2}, …, e_{k}, v_{k} = v) of alternating vertices and edges, where e_{i} = {v_{i−1}, v_{i}} for i = 1, …, k. For every vertex u, we define (u) to be a uu-walk of length 0. A graph G is connected if for every pair of vertices u and v, there exists a uv-walk in G. In a connected graph, the distance from vertex u to vertex v is the length of a shortest uv-walk. The diameter of a connected graph G is the largest distance between any two of its vertices. A k-cycle C_{k} is a uv-walk of length k ≥ 3 where u = v, but no other vertices repeat. If G contains any cycles, the girth of G is the length of a shortest cycle in G. A connected graph that does not contain any cycles is called a tree. A graph G is 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 ∈ P and y ∈ L (or vice versa). Two graphs G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) are isomorphic if there exists a bijection φ : V_{1} → V_{2} such that x, y ∈ V_{1} are adjacent if and only if φ(x), φ(y) ∈ V_{2} are adjacent. Other standard graph theory definitions may be found, for example, in Bollobás [2].

Let 𝔽_{q} denote the finite field of order q. A permutation polynomial of 𝔽_{q} is a polynomial f ∈ 𝔽_{q}[x] whose induced function on 𝔽_{q}, defined by a ↦ f(a), is a bijection. Let f_{2}, f_{3} : 𝔽_{q}^{2} → 𝔽_{q} be functions. An algebraically defined graph G_{q}(f_{2}, f_{3}) of dimension three is a bipartite graph with partite sets P = 𝔽_{q}^{3} = L, and (x_{1}, x_{2}, x_{3}) ∈ P is adjacent to [y_{1}, y_{2}, y_{3}] ∈ 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 monomial graph.

1.2 Motivation

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 [13], Van Maldeghem [15], and Benson [1] 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 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 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 Γ_{3}(q).

Now, a primary motivation for Dmytrenko, Lazebnik, and Williford [5] and Kronenthal [10] 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 Γ_{3}(q), and has vertex partition P ∪ 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 Γ_{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 [5], who conjectured that a suitable monomial graph does not exist.

Conjecture 1. [5] Let q = p^{e} be an odd prime power. Then every monomial graph over 𝔽_{q} of girth at least eight is isomorphic to Γ_{3}(q).

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 [12], Van Maldeghem [15], and Cherowitzo [3] for additional information.

Working towards a proof of Conjecture 1, Dmytrenko, Lazebnik and Williford [5] proved the following result:

Theorem 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^{k}y^{2k}), where k is not divisible by p. If q ≥ 5, the following statements also hold:

1. 1 ≤ k < \frac{q−1}{2}, gcd(k, q − 1) = 1, and k ≡ 1 (mod p − 1).

2. ((x + 1)^{2k} − 1)x^{q−1−k} − 2x^{q−1} ∈ 𝔽_{q}[x] is a permutation polynomial of 𝔽_{q}.

The permutation polynomial from part 2 of Theorem 2 was then used in conjunction with the Hermite-Dickson criterion:

Theorem 3 (Hermite-Dickson criterion). (See Hermite [8] and Dickson [4]; see also Lidl and Niederreiter [11].) Let 𝔽_{q} be of characteristic p. Then f ∈ 𝔽_{q}[x] is a permutation polynomial of 𝔽_{q} if and only if the following two conditions hold:

1. f has exactly one root in 𝔽_{q}; and

2. for each integer t with 1 ≤ t ≤ q − 2 and p ∤ t, the reduction of f^{t} (mod x^{q} − x) has degree at most q − 2.

Indeed, let e ≥ 1 be an integer, p an odd prime, and q = p^{e} ≥ 5. Let G be a monomial graph of girth at least eight. Then by Theorem 2, G is isomorphic to G_{q}(xy, x^{k}y^{2k}) and

F = ((x + 1)^{2k} − 1)x^{q−1−k} − 2x^{q−1} ∈ 𝔽_{q}[x]

is a permutation polynomial of 𝔽_{q}. The Hermite-Dickson criterion implies that the coefficient of x^{q−1} in F^{t} (mod x^{q} − x) must be zero for all 1 ≤ t ≤ q − 2. This yields

∑_{j=0}^{t}(−2)^{j}\binom{t}{j} \begin{matrix}⌊ & \frac{t−j}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{t − j}{h}\binom{2k(t − j − h)}{k(t − j)} ≡ 0 (mod p);  (1)

for details of this derivation, see Kronenthal [10].

We now consider instances of (1) for some small values of t; the result is a sequence of congruences. We use (κ_{i}) to denote the congruence resulting from the substitution t = i. When t = 1, (1) yields −2 + \binom{2k}{k} ≡ 0 (mod p), and so

\binom{2k}{k} ≡ 2 (mod p).  (κ_{1})

When t = 2, we have 2−4\binom{2k}{k}+\binom{4k}{2k} ≡ 0 (mod p); substituting (κ_{1}) implies 2−4·2+\binom{4k}{2k} ≡ 0 (mod p), and therefore

\binom{4k}{2k} ≡ 6 (mod p).  (κ_{2})

Continuing this process of evaluating (1) for subsequent values of t, and back-substituting previous congruences at each step, yields the following:

\binom{6k}{3k} − 3\binom{4k}{3k} ≡ 8 (mod p)  (κ_{3})
\binom{8k}{4k} − 4\binom{6k}{4k} ≡ 10 (mod p)  (κ_{4})
\binom{10k}{5k} − 5\binom{8k}{5k} + 10\binom{6k}{5k} ≡ 32 (mod p)  (κ_{5})
\binom{12k}{6k} − 6\binom{10k}{6k} + 15\binom{8k}{6k} ≡ 84 (mod p)  (κ_{6})
\binom{14k}{7k} − 7\binom{12k}{7k} + 21\binom{10k}{7k} − 35\binom{8k}{7k} ≡ 128 (mod p)  (κ_{7})
\binom{16k}{8k} − 8\binom{14k}{8k} + 28\binom{12k}{8k} − 56\binom{10k}{8k} ≡ 186 (mod p)  (κ_{8})
⋮

In general, we obtain that for every integer t ≥ 1,

\begin{matrix}⌊ & \frac{t−1}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{t}{h}\binom{2k(t − h)}{kt} ≡ b_{t} (mod p),  (κ_{t})

where the integer b_{t} represents the terms in (1) not involving k (after back-substituting (κ_{1}), …, (κ_{t−1})). The sequence (b_{t})_{t≥1} appears in Sloane’s Online Encyclopedia of Integer Sequences as sequence number \underline{A247984} [14]:

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, ….

The following theorem, our main result, states a closed form for b_{t}.

Theorem 4. For all positive integers t, let b_{t} be as defined in (κ_{t}). Then

b_{t} = \begin{cases}2^{t}, & if t is odd; \\ 2^{t} − (−1)^{t/2}\binom{t}{t/2}, & if t is even. \end{cases}

Theorem 4 first appeared as a comment, without proof, in Kronenthal [10]. The purpose of this paper is to prove Theorem 4 in two ways. In Section 2, we prove the theorem directly (much like how we originally derived it). In Section 3, we present a shorter inductive argument.

However, before ending this section, we note that after the change of variables g = t − j,

(1) may be rewritten as

∑_{g=0}^{t}(−2)^{t−g}\binom{t}{g} ∑_{h=0}^{⌊g/2⌋}(−1)^{h}\binom{g}{h}\binom{2k(g − h)}{kg} ≡ 0 (mod p).  (2)

This will be used both in Section 2 and in Section 3.

2 A direct proof

In this section, we prove Theorem 4 directly. We begin with a number of preliminary results.

Lemma 5. (Graham, Knuth, and Patashnik [7, Equation 5.10]) Let n and k be non-negative integers. Then

∑_{j=0}^{n} \binom{j}{k} = \binom{n + 1}{k + 1}.

Lemma 6. (Graham, Knuth, and Patashnik [7, Equation 5.5]) Let k ≠ 0 be an integer. Then

\binom{n}{k} = \frac{n}{k}\binom{n − 1}{k − 1}.

Lemma 7. (Gould [6, Equation 1.47 with x = 1]) For all j ≤ n,

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}\frac{k^{j}}{k + 1} = (−1)^{j} \frac{1}{n + 1}.

In the following, let ℕ = {1, 2, 3, …} denote the set of natural numbers.

Lemma 8. Let j, n ∈ ℕ. Then

∑_{y_{1}+···+y_{j}=n} ; y_{1},...,y_{j}∈ℕ \binom{n}{y_{1}, y_{2}, …, y_{j−1}, y_{j}} = ∑_{k=1}^{j}(−1)^{j−k}k^{n}\binom{j}{j − k}.

Lemma 8 follows directly from Kao and Zetterberg [9, Theorem 2.2]. Lemma 9. Let i, t ∈ ℕ such that i < t. Then

∑_{j=1}^{t−i} ∑_{t>x_{1}>···>x_{j}=i}(−1)^{j+1}\binom{t}{x_{1}}\binom{x_{1}}{x_{2}} ⋯ \binom{x_{j−1}}{i} = (−1)^{t+i−1}\binom{t}{i},

where x_{i} ∈ ℕ for all i = 1, 2, …, j. Proof. We have

∑_{j=1}^{t−i} ∑_{t>x_{1}>···>x_{j}=i}(−1)^{j+1}\binom{t}{x_{1}}\binom{x_{1}}{x_{2}} ⋯ \binom{x_{j−1}}{i}

= \binom{t}{i} ∑_{j=1}^{t−i}(−1)^{j+1} ∑_{t>x_{1}>···>x_{j}=i} \binom{t − i}{t − x_{1}, x_{1} − x_{2}, …, x_{j−2} − x_{j−1}, x_{j−1} − i}

= \binom{t}{i} ∑_{j=1}^{t−i}(−1)^{j+1} ∑_{y_{1}+···+y_{j}=t−i} ; y_{1},...,y_{j}∈ℕ \binom{t − i}{y_{1}, y_{2}, …, y_{j−1}, y_{j}}

= \binom{t}{i} ∑_{j=1}^{t−i}(−1)^{j+1} ∑_{k=1}^{j}(−1)^{j−k}k^{t−i}\binom{j}{j − k} (by Lemma 8 with n = t − i)

= \binom{t}{i} ∑_{k=1}^{t−i}(−1)^{k−1}k^{t−i} ∑_{j=0}^{t−i} \binom{j}{k}

= \binom{t}{i} ∑_{k=1}^{t−i}(−1)^{k−1}k^{t−i}\binom{t − i + 1}{k + 1} (by Lemma 5)

= −\binom{t}{i}(t − i + 1) ∑_{k=1}^{t−i}(−1)^{k}\binom{t − i}{k}\frac{k^{t−i}}{1 + k} (by Lemma 6)

= −\binom{t}{i}(t − i + 1) ((−1)^{t−i} \frac{1}{t − i + 1}) (by Lemma 7 with n = t − i and j = t − i)

= \binom{t}{i}(−1)^{t+i−1}.

Lemma 10. (Graham, Knuth, and Patashnik [7, Equation 5.24]) Let l ≥ 0, m, and n be integers. Then

∑_{k} \binom{l}{m + k}\binom{s + k}{n}(−1)^{k} = (−1)^{l+m}\binom{s − m}{n − l}.

We now use (2) and the above lemmas to prove Theorem 4. Define

C_{t} = ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g},

L_{t} = \begin{matrix}⌊ & \frac{t−1}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{t}{h}\binom{2k(t − h)}{kt},

and

a_{t,u} = (−2)^{t−u}\binom{t}{u}.

Note that on the left-hand side of (2), 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 ↦ 2g), L_{t} consists of all non-constant terms containing binomial coefficients of the form \binom{x}{kt} for some x (L_{t} is the left-hand side of (κ_{t})), and a_{t,u} is the coefficient of L_{u} when it appears in the calculation of (κ_{t}). Then (2) is equivalent to

C_{t} + ∑_{g=1}^{t−1} a_{t,g}L_{g} + \begin{matrix}⌊ & \frac{t−1}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{t}{h}\binom{2k(t − h)}{kt} ≡ 0 (mod p),

and therefore congruence (κ_{t}) may be rewritten as

\begin{matrix}⌊ & \frac{t−1}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{t}{h}\binom{2k(t − h)}{kt} ≡ −C_{t} − ∑_{g=1}^{t−1} a_{t,g}L_{g} (mod p).

In other words,

L_{t} ≡ −C_{t} − ∑_{g=1}^{t−1} a_{t,g}L_{g} (mod p).

Expanding and back-substituting for some small values of t, we have:

L_{1} ≡ −C_{1} (mod p)
L_{2} ≡ −a_{2,1} · L_{1} − C_{2} ≡ a_{2,1}C_{1} − C_{2} (mod p)
L_{3} ≡ −a_{3,2} · L_{2} − a_{3,1} · L_{1} − C_{3}

≡ −a_{3,2}(a_{2,1}C_{1} − C_{2}) + a_{3,1}C_{1} − C_{3}

≡ (a_{3,1} − a_{3,2}a_{2,1})C_{1} + a_{3,2}C_{2} − C_{3} (mod p)

L_{4} ≡ −a_{4,3} · L_{3} − a_{4,2} · L_{2} − a_{4,1} · L_{1} − C_{4}

≡ −a_{4,3}((a_{3,1} − a_{3,2}a_{2,1})C_{1} + a_{3,2}C_{2} − C_{3}) − a_{4,2}(a_{2,1}C_{1} − C_{2}) + a_{4,1}C_{1} − C_{4} ≡ (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} (mod p)

In general, congruence (κ_{t}) may be written as

\begin{matrix}L_{t} = \begin{matrix}⌊ & \frac{t−1}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{t}{h} & \binom{2k(t − h)}{kt} \\ ≡ −C_{t} + ∑_{i=1}^{t−1} C_{i} ∑_{j=1}^{t−i} ∑_{t>x_{1}>···>x_{j}=i}(−1)^{j+1}a_{t,x_{1}}a_{x_{1},x_{2}} ⋯ a_{x_{j−1},i} (mod p). \end{matrix} ; (3)

We are now ready to prove our main result.

Proof of Theorem 4. From (3), the right-hand side of congruence (κ_{t}) is

b_{t} = −C_{t} + ∑_{i=1}^{t} C_{i} ∑_{j=1}^{t−i} ∑_{t>x_{1}>···>x_{j}=i}(−1)^{j+1}a_{t,x_{1}}a_{x_{1},x_{2}} ⋯ a_{x_{j−1},i}

= − ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g} + ∑_{i=1}^{t−1} (∑_{g=0}^{⌊i/2⌋}(−1)^{i−g}2^{i−2g}\binom{i}{2g}\binom{2g}{g})

∑_{j=1}^{t−i} ∑_{t>x_{1}>···>x_{j}=i}(−1)^{j+1} ((−2)^{t−x_{1}} \binom{t}{x_{1}}) ((−2)^{x_{1}−x_{2}} \binom{x_{1}}{x_{2}}) ⋯ ((−2)^{x_{j−1}−i}\binom{x_{j−1}}{i})

= − ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g}

+ (−2)^{t} ∑_{i=1}^{t−1} (∑_{j=1}^{t−i} ∑_{t>x_{1}>···>x_{j}=i}(−1)^{j+1}\binom{t}{x_{1}} ⋯ \binom{x_{j−1}}{i}) ∑_{g=0}^{⌊i/2⌋}(−4)^{−g}\binom{i}{2g}\binom{2g}{g}

= − ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g}

+ (−2)^{t} ∑_{i=1}^{t−1} (\binom{t}{i}(−1)^{t+i−1}) ∑_{g=0}^{⌊i/2⌋}(−4)^{−g}\binom{i}{2g}\binom{2g}{g} (by Lemma 9)

= (−2)^{t} ∑_{i=1}^{t} (\binom{t}{i}(−1)^{t+i−1}) ∑_{g=0}^{⌊i/2⌋}(−4)^{−g}\binom{i}{2g}\binom{2g}{g}

= (−1)^{t−1}(−2)^{t} ∑_{g=0}^{⌊t/2⌋}(−4)^{−g}\binom{2g}{g} ∑_{i=1}^{t}(−1)^{i}\binom{t}{i}\binom{i}{2g}

= −2^{t} (∑_{i=1}^{t}(−1)^{i}\binom{t}{i} + ∑_{g=1}^{⌊t/2⌋}(−4)^{−g}\binom{2g}{g} ∑_{i=1}^{t}(−1)^{i}\binom{t}{i}\binom{i}{2g})

= −2^{t} (−1 + ∑_{g=1}^{⌊t/2⌋}(−4)^{−g}\binom{2g}{g} ∑_{i=1}^{t}(−1)^{i}\binom{t}{i}\binom{i}{2g})

= −2^{t} (−1 + ∑_{g=1}^{⌊t/2⌋}(−4)^{−g}\binom{2g}{g}(−1)^{t}\binom{0}{2g − t}) (by Lemma 10)

= \begin{cases}2^{t}, & if t is odd; \\ −2^{t} (−1 + (−4)^{−t/2}\binom{t}{t/2}(−1)^{t}), & if t is even; \end{cases}

= \begin{cases}2^{t}, & if t is odd; \\ 2^{t} − (−1)^{t−t/2}2^{t}(2^{2})^{−t/2}\binom{t}{t/2}, & if t is even; \end{cases}

= \begin{cases}2^{t}, & if t is odd; \\ 2^{t} − (−1)^{t/2}\binom{t}{t/2}, & if t is even. \end{cases}

9

3 An inductive proof

In this section, we prove Theorem 4 inductively. We begin by reorganizing the terms of (2). The left-hand side of congruence (κ_{t}) will be those terms with g = t and h ≠ g/2, namely

\begin{matrix}⌊ & \frac{t−1}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{t}{h}\binom{2k(t − h)}{kt}.

We partition the remaining terms into two sums:

∑_{g=0}^{t}(−1)^{g/2}2^{t−g}\binom{t}{g}\binom{g}{g/2} = ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g}

contains all terms such that h = g/2, and

∑_{g=1}^{t−1}(−2)^{t−g}\binom{t}{g} \begin{matrix}⌊ & \frac{g−1}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{g}{h}\binom{2k(g − h)}{kg}

contains all remaining terms (i.e., all terms such that g ≠ t and h ≠ g/2). Note that the inner sum is the left-hand side of congruence (κ_{g}). Hence, we rewrite (2) as

\begin{matrix}⌊ & \frac{t−1}{2} & ⌋ \\ ∑ \\ h=0 \end{matrix}(−1)^{h}\binom{t}{h}\binom{2k(t − h)}{kt} ≡ − ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g}−∑_{g=1}^{t−1}(−2)^{t−g}\binom{t}{g}b_{g} (mod p),

which proves

b_{t} = − ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g} − ∑_{g=1}^{t−1}(−2)^{t−g}\binom{t}{g}b_{g}.  (4)

Now, before proving our main result, we state a well-known lemma.

Lemma 11. Let t be a positive integer. Then ∑_{g=0}^{⌊t/2⌋} \binom{t}{2g} = 2^{t−1} and

∑_{g=1}^{⌊t/2⌋} \binom{t}{2g − 1} = \begin{cases}2^{t−1}, & if t is even; \\ 2^{t−1} − 1, & if t is odd. \end{cases}

Proof of Theorem 4. We proceed by induction. When t = 1, (4) implies that

b_{1} = −(−1)(2)\binom{1}{0}\binom{0}{0} = 2.

Now, suppose the result holds for all positive integers less than t. Then from (4),

b_{t} = − ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g} − ∑_{g=1}^{t−1}(−2)^{t−g}\binom{t}{g}b_{g}

= − ∑_{g=0}^{⌊t/2⌋}(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g} − \begin{matrix}⌊ & \frac{t−1}{2} & ⌋ \\ ∑ \\ g=0 \end{matrix}(−2)^{t−2g}\binom{t}{2g} (2^{2g} − (−1)^{g}\binom{2g}{g})

− ∑_{g=1}^{⌊t/2⌋}(−1)^{t+1}2^{t}\binom{t}{2g − 1}

= − ∑_{g=0}^{⌊t/2⌋} [(−1)^{t−g}2^{t−2g}\binom{t}{2g}\binom{2g}{g} + (−2)^{t−2g}\binom{t}{2g} (2^{2g} − (−1)^{g}\binom{2g}{g})]

+ (\frac{1 + (−1)^{t}}{2} ) (2^{t} − (−1)^{t/2}\binom{t}{t/2}) − ∑_{g=1}^{⌊t/2⌋}(−1)^{t+1}2^{t}\binom{t}{2g − 1}

= − ∑_{g=0}^{⌊t/2⌋}(−2)^{t}\binom{t}{2g} + (\frac{1 + (−1)^{t}}{2} ) (2^{t} − (−1)^{t/2}\binom{t}{t/2}) − ∑_{g=1}^{⌊t/2⌋}(−1)^{t+1}2^{t}\binom{t}{2g − 1}

= (−1)^{t+1}2^{t} ∑_{g=0}^{⌊t/2⌋} \binom{t}{2g} + (\frac{1 + (−1)^{t}}{2} ) (2^{t} − (−1)^{t/2}\binom{t}{t/2}) + (−2)^{t} ∑_{g=1}^{⌊t/2⌋} \binom{t}{2g − 1}

= (−1)^{t+1}2^{2t−1} + (\frac{1 + (−1)^{t}}{2} ) (2^{t} − (−1)^{t/2}\binom{t}{t/2}) + (−2)^{t} (2^{t−1} − \frac{1 − (−1)^{t}}{2} )

(by Lemma 11)

= \begin{cases}2^{t}, & if t is odd; \\ 2^{t} − (−1)^{t/2}\binom{t}{t/2}, & if t is even. \end{cases}

4 Concluding remarks

In this paper, we have provided direct and inductive proofs of Theorem 4. One interesting future direction is as follows:

Open Problem 12. Prove Theorem 4 using a combinatorial argument.

We conclude by stating two results that were proven using Theorem 4. Theorem 13 used b_{1} and b_{2}, while Theorem 14 relied on Theorem 4 in its entirety.

Theorem 13. (Dmytrenko, Lazebnik, and Williford [5]) Let q = p^{e} be an odd prime power, with p ≥ 5 and e = 2^{a}3^{b} for integers a, b ≥ 0. Then every monomial graph over 𝔽_{q} of girth at least eight is isomorphic to Γ_{3}(q) and has girth eight. Furthermore, for 3 ≤ q ≤ 10^{10}, every monomial graph over 𝔽_{q} nonisomorphic to Γ_{3}(q) has girth at most six.

Theorem 14. (Kronenthal [10]) Let q = p^{e} be an odd prime power and e ≥ 2. Then there exists p_{0} such that for all p ≥ p_{0}, every monomial graph over 𝔽_{q} of girth at least eight is isomorphic to Γ_{3}(q), and hence has girth exactly eight. Furthermore, p_{0} depends only on the largest prime divisor of e. In particular:

1. if e = 2^{a}3^{b}5^{c} with a, b, c ≥ 0, then p_{0} = 7.

2. if e = 2^{a}3^{b}5^{c}7^{d} with a, b, c, d ≥ 0, then p_{0} = 11.

3. if e = 2^{a}3^{b}5^{c}7^{d}11^{y} with integers a, b, c, d, y ≥ 0, then p_{0} = 13.

5 Acknowledgments

The author is grateful to Felix Lazebnik for his support while conducting this research, as well as for suggesting Open Problem 12.

References

[1] C. T. Benson, On the structure of generalized quadrangles, J. Algebra 15 (1970) 443– 454.

[2] B. Bollobás, Modern Graph Theory, Springer, 1998.

[3] W. E. Cherowitzo, Hyperovals in Desarguesian planes: an electronic update, informal notes, available at

    http://math.ucdenver.edu/~wcherowi/research/hyperoval/hypero.html.

[4] L. E. Dickson, The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group, Ann. of Math. 11 (1896–1897) 161–183.

[5] V. Dmytrenko, F. Lazebnik, and J. Williford, On monomial graphs of girth eight, Finite Fields Appl. 13 (2007) 828–842.

[6] H. W. Gould, Combinatorial Identities, Morgantown, WV, 1972.

[7] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley Publishing Company, 1994.

[8] C. Hermite, Sur les fonctions de sept lettres, C. R. Math. Acad. Sci. Paris 57 (1863) 750–757.

[9] R. C. Kao and L. H. Zetterberg, An identity for the sum of multinomial coefficients, Amer. Math. Monthly 64 (1957) 96–100.

[10] B. G. Kronenthal, Monomial graphs and generalized guadrangles, Finite Fields Appl. 18 (2012) 674–684.

[11] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, 2008.

[12] S. E. Payne, A census of finite generalized quadrangles, in Finite Geometries, Buildings, and Related Topics, Oxford Univ. Press, 1990, pp. 29–36.

[13] S. E. Payne and J. A. Thas, Finite Generalized Quadrangles, Research Notes in Mathematics, Vol. 110, Pitman, 1984.

[14] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically

    at http://oeis.org.

[15] H. Van Maldeghem, Generalized Polygons, Birkhäuser, 1998.

2010 Mathematics Subject Classification: Primary 12E99; Secondary 51E12. Keywords: permutation polynomial, monomial graph, generalized quadrangle, girth, cycle.

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

Received February 10 2015; revised versions received July 10 2015. Published in Journal of Integer Sequences, July 16 2015.

Return to Journal of Integer Sequences home page.