GAUSS SUMS, JACOBI SUMS, AND p-RANKS OF CYCLIC DIFFERENCE SETS

RONALD EVANS, HENK HOLLMANN, CHRISTIAN KRATTENTHALER, QING XIANG

Abstract. We study quadratic residue difference sets, GMW difference sets, and difference sets arising from monomial hyperovals, all of which are (2^{d} −1, 2^{d−1} −1, 2^{d−2} −1) cyclic difference sets in the multiplicative group of the finite field 𝔽_{2^{d}} of 2^{d} elements, with d ≥ 2. We show that, except for a few cases with small d, these difference sets are all pairwise inequivalent. This is accomplished in part by examining their 2-ranks. The 2-ranks of all of these difference sets were previously known, except for those connected with the Segre and Glynn hyperovals. We determine the 2-ranks of the difference sets arising from the Segre and Glynn hyperovals, in the following way. Stickelberger’s theorem for Gauss sums is used to reduce the computation of these 2-ranks to a problem of counting certain cyclic binary strings of length d. This counting problem is then solved combinatorially, with the aid of the transfer matrix method. We give further applications of the 2-rank formulas, including the determination of the nonzeros of certain binary cyclic codes, and a criterion in terms of the trace function to decide for which β in 𝔽_{2^{d}}^{∗} the polynomial x^{6} + x + β has a zero in 𝔽_{2^{d}}, when d is odd.

1. Introduction

Let G be a finite (multiplicative) group of order v. A K-element subset D of G is called a (v, K, λ) difference set in G if the list of “differences” d_{1}d_{2}^{−1}, d_{1}, d_{2} ∈ D, d_{1} ≠ d_{2}, represents each nonidentity element in G exactly λ times. Thus, D is a (v, K, λ) difference set in G if and only if it satisfies the following equation in ℤ[G]:

( ∑_{d∈D} d)( ∑_{d∈D} d^{−1}) = (K − λ)1_{G} + λ ∑_{g∈G} g,  (1.1)

where 1_{G} is the identity element of G. If the group G is cyclic, then D is called a cyclic difference set.

We say that the (v, K, λ) difference sets D_{1} and D_{2} in an Abelian group G are equivalent if there exists an automorphism α of G and an element a ∈ G such that α(D_{1}) = D_{2}a. In particular, if G is cyclic, then D_{1} and D_{2} are equivalent if there exists an integer t, (t, v) = 1, such that D_{1} = D_{2}^{(t)}a for some a ∈ G, where D_{2}^{(t)} = {d^{t} | d ∈ D_{2}}.

2000 Mathematics Subject Classification. Primary 05B10; Secondary 05A15 05C38 05C90 11L05 11T24 11T71 94B15.

Key words and phrases. Cyclic difference set, monomial hyperoval, Segre hyperoval, Glynn hyperoval, Singer difference set, GMW difference set, quadratic residue difference set, binary cyclic code, finite fields, Teichmüller character, Gauss sum, Jacobi sum, enumeration of cyclic binary strings, transfer matrix method.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1999 by Academic Press.

In the case G is Abelian, using the Fourier inversion formula, we obtain the following standard result in the theory of difference sets [28, p. 323].

Lemma 1.1. Let G be an Abelian group of order v. A K-subset D is a (v, K, λ) difference set in G if and only if

χ(D)\overline{χ(D)} = K − λ  (1.2)

for every nontrivial complex multiplicative character χ of G. Here, χ(D) stands for ∑_{d∈D} χ(d).

Difference sets are the same objects as symmetric designs with a regular automorphism group (see [15, p. 243]). Therefore they play an important role in the theory of combinatorial designs. The study of difference sets is also closely related to coding theory, finite geometry, and communication signal designs. We refer the reader to the book of Lander [16] and the paper of Jungnickel [15] for a survey of this subject.

Let 𝔽_{q} be the finite field with q elements, q being a power of the prime p. Let ξ_{p} be a fixed complex primitive pth root of unity and let Tr_{q/p} be the trace from 𝔽_{q} to ℤ/pℤ. Define

ψ: 𝔽_{q} → ℂ^{∗}, ψ(x) = ξ_{p}^{Tr_{q/p}(x)},

which is easily seen to be a nontrivial character of the additive group of 𝔽_{q}. Let

χ: 𝔽_{q}^{∗} → ℂ^{∗}

be a multiplicative character of 𝔽_{q}^{∗}. We extend χ to all of 𝔽_{q} by setting χ(0) = 0. Note that χ^{q−1} = 1 (the trivial character), so the order of χ is prime to p.

Define the Gauss sum by

g(χ) = ∑_{a∈𝔽_{q}} χ(a)ψ(a).

One of the elementary properties of Gauss sums is [4, Theorem 1.1.4]

g(χ)\overline{g(χ)} = q, if χ ≠ 1.  (1.3)

If χ_{1}, χ_{2} are two multiplicative characters, we define the Jacobi sum by

J(χ_{1}, χ_{2}) = ∑_{a∈𝔽_{q}} χ_{1}(a)χ_{2}(1 − a).

Jacobi sums are closely related to Gauss sums. In fact if χ_{1} ≠ 1, χ_{2} ≠ 1, and χ_{1}χ_{2} ≠ 1, then [4, Theorem 2.1.3]

J(χ_{1}, χ_{2}) = g(χ_{1})g(χ_{2})/g(χ_{1}χ_{2}),  (1.4)

and

J(χ_{1}, χ_{2})\overline{J(χ_{1}, χ_{2})} = q.  (1.5)

The apparent analogy between (1.2) and {(1.3), (1.5)} suggests that there may be a connection between difference sets and Gauss and Jacobi sums. This is indeed the case. In fact, several authors have investigated difference sets by using Gauss sums and Jacobi sums; for example, see [3], [4, Chapter 5], [32]. However, such investigations deal mostly with power residue difference sets. In Section 2 of this paper, we use Jacobi sums to give a simple new proof that certain sets which Maschietti [21] constructed from hyperovals are cyclic (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1) difference sets; see Theorem 2.5. Then in Section 3, we use Stickelberger’s theorem on the prime ideal decomposition of Gauss sums to give a new proof of the p-rank formula for Singer difference sets (which include the difference sets arising from regular and translation hyperovals); see Theorem 3.5. The main result of Section 3 is Theorem 3.6, where, again using Stickelberger’s theorem, we reduce the problem of computing the 2-ranks of the difference sets arising from Segre and Glynn hyperovals to a problem of counting certain cyclic binary sequences. In Section 4, we solve the counting problem completely, with the aid of the transfer matrix method; see Theorem 4.3. In the case of the Segre hyperovals, this yields an explicit formula for their 2-ranks in terms of Fibonacci numbers; see Corollary 4.4. This explicit formula had been conjectured by Xiang [31]. In the case of the Glynn hyperovals we obtain 5term recurrence relations for the 2-ranks of the corresponding cyclic difference sets; see Theorems 4.6 and 4.8.

As applications, in Section 5, we determine the nonzeros of the binary cyclic codes which result from the Segre hyperovals, and we give a criterion to decide when the equation x^{6} + x + β = 0, β ∈ 𝔽_{2^{d}}^{∗}, has two distinct solutions in 𝔽_{2^{d}}, d odd.

The main applications of our results are contained in Section 6. There we show that, except for a few small values of d, the Singer difference sets and the difference sets which arise from the Segre and the Glynn hyperovals are all inequivalent; see Theorem 6.2. This answers a question raised by Maschietti [21]. We also show that difference sets arising from hyperovals are inequivalent to quadratic residue difference sets [15, p. 244] (see Theorem 6.3) and to GMW difference sets [11] (see Theorem 6.8).

Finally, in Section 7, we use the machinery developed in this paper to compute the 2-ranks of certain circulant matrices. These matrices are closely related to incidence matrices corresponding to difference sets arising from hyperovals.

2. Gauss Sums, Jacobi Sums and Cyclic Difference Sets

Singer (1938) (cf. [15, p. 244]) discovered a large class of difference sets which are related to finite projective geometry and to (generalized) Reed-Muller codes (cf. [2, p. 180]). These difference sets L_{0}, whose construction we give below, have parameters

v = \frac{q^{d} − 1}{q − 1},  K = \frac{q^{d−1} − 1}{q − 1},  λ = \frac{q^{d−2} − 1}{q − 1}

for d ≥ 2 and they exist whenever q is a prime power.

The construction is as follows. Let 𝔽_{q^{d}} be the finite field of q^{d} elements, d ≥ 2, and let Tr be the trace from 𝔽_{q^{d}} to 𝔽_{q}. We may take a system L of coset representatives of 𝔽_{q}^{∗} in 𝔽_{q^{d}}^{∗} such that Tr maps L into {0, 1}. Write L = L_{0} ∪ L_{1}, where

L_{0} = {x ∈ L | Tr(x) = 0}, L_{1} = {x ∈ L | Tr(x) = 1}.

The following proof that L_{0} is a difference set is due to Yamamoto [33]. We present it here since it is less well-known than the standard one using a Singer cycle, and since we will use it to give a new proof of the p-rank formula for the Singer difference sets (see Theorem 3.5). This proof of Theorem 2.1 is essentially an evaluation of the Eisenstein sum χ(L_{0}); see [4, pp. 389, 400].

Theorem 2.1. With the above notation, L_{0} is a (\frac{q^{d}−1}{q−1}, \frac{q^{d−1}−1}{q−1}, \frac{q^{d−2}−1}{q−1}) difference set in the quotient group 𝔽_{q^{d}}^{∗}/𝔽_{q}^{∗}.

Proof: Let χ be a nontrivial multiplicative character of 𝔽_{q^{d}} whose restriction to 𝔽_{q}^{∗} is trivial, so that we may view χ as a character of the quotient group 𝔽_{q^{d}}^{∗}/𝔽_{q}^{∗}. It is easy to see that every nontrivial character of 𝔽_{q^{d}}^{∗}/𝔽_{q}^{∗} can be obtained in this manner. We have

g(χ) = ∑_{y∈𝔽_{q^{d}}^{∗}} χ(y)ξ_{p}^{Tr_{q^{d}/p}(y)} = ∑_{a∈𝔽_{q}^{∗}} ∑_{x∈L} χ(xa)ξ_{p}^{Tr_{q^{d}/p}(xa)}

= ∑_{x∈L} χ(x) ∑_{a∈𝔽_{q}^{∗}} χ(a)ξ_{p}^{Tr_{q/p}(a Tr(x))}

= (q − 1) ∑_{x∈L_{0}} χ(x) − ∑_{x∈L_{1}} χ(x) = q ∑_{x∈L_{0}} χ(x) = qχ(L_{0}).

By (1.3), we have χ(L_{0})\overline{χ(L_{0})} = q^{d−2}. The theorem now follows from Lemma 1.1.

Remark: When q = 2, Singer difference sets have parameters (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1), which are a special case of the Hadamard parameters (4n − 1, 2n − 1, n − 1) (see [15, p. 244]).

Cyclic (2^{d} −1, 2^{d−1} −1, 2^{d−2} −1) difference sets have been extensively studied because of their important applications in communication signal designs (see [10]). Known examples of these difference sets include Singer difference sets, GMW difference sets (see [11]), quadratic residue difference sets [15, p. 244] and the cyclic (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1) difference sets constructed recently by Maschietti [21] by using monomial hyperovals.

We proceed to discuss Maschietti’s difference sets. An m-arc in the projective plane P G(2, q), with q a prime power, is a set of m points, no three of which are collinear. The maximum value of m is q+1 or q+2, according as q is odd or even. If q is odd, (q+1)-arcs are called ovals. A celebrated theorem of Segre [25] (see also [14, p. 168]) states that all such ovals are given algebraically by irreducible conics. If q is even, (q + 2)-arcs are called hyperovals. The classic example of a hyperoval is the union of an irreducible conic and its nucleus (see [14, p. 164]).

Two hyperovals are said to be projectively equivalent if one hyperoval can be transformed into the other by a projective linear transformation, i.e., by an element from P GL(3, q). By the Fundamental Theorem of Projective Geometry, the group P GL(3, q) of projective linear transformations of P G(2, q) is transitive on quadrangles. Thus every hyperoval can be mapped by an element of P GL(3, q) to a hyperoval containing the fundamental quadrangle (1, 0, 0), (0, 1, 0), (0, 0, 1), and (1, 1, 1). From now on, we will restrict our attention to those hyperovals in P G(2, q) with q > 2 which contain the fundamental quadrangle. The following result of Segre (see [14, Theorem 8.4.2]) shows that any such hyperoval can be expressed in terms of a permutation polynomial over 𝔽_{q}, i.e., a polynomial which, when interpreted as a function, permutes 𝔽_{q}.

Theorem 2.2. (Segre). Let q > 2 be a power of 2. Then any hyperoval in P G(2, q) containing the fundamental quadrangle is equal to a (q + 2)-arc

D(f) = {(1, t, f(t)) | t ∈ 𝔽_{q}} ∪ {(0, 1, 0), (0, 0, 1)},

where f is a permutation polynomial over 𝔽_{q} of degree at most q − 2, satisfying f(0) = 0, f(1) = 1, and such that for each s ∈ 𝔽_{q},

f_{s}(x) = \begin{cases}\frac{f(x + s) + f(s)}{x}, & if x ≠ 0, \\ 0, & if x = 0, \end{cases}

is a permutation polynomial.

Conversely, every such set D(f) is a hyperoval.

These polynomials f(x) are also called o-polynomials.

A subclass of hyperovals is the set of monomial hyperovals. These are hyperovals in P G(2, 2^{d}) projectively equivalent to

D(x^{k}) = {(1, t, t^{k}) | t ∈ 𝔽_{2^{d}}} ∪ {(0, 1, 0), (0, 0, 1)}.

Known examples of monomial hyperovals in P G(2, 2^{d}) include

(2.1) the regular hyperoval D(x^{2}),

(2.2) the translation hyperovals D(x^{2^{i}}), where (d, i) = 1, 1 < i < d/2,

(2.3) the Segre hyperoval D(x^{6}), where d ≥ 5 is odd,

(2.4) the Glynn type (I) hyperovals D(x^{σ+γ}), where d ≥ 7 is odd, σ = 2^{(d+1)/2}, and

γ = 2^{(3d+1)/4} if d ≡ 1 mod 4, whereas γ = 2^{(d+1)/4} if d ≡ 3 mod 4, (2.5) the Glynn type (II) hyperovals D(x^{3σ+4}), where d ≥ 11 is odd, and σ = 2^{(d+1)/2}.

Remark: We have not listed the translation hyperovals for i = 1 nor the Segre and Glynn hyperovals for d = 3, as these are all projectively equivalent to the regular hyperovals. The translation hyperoval for a given i > d/2 is equivalent to the one where i is replaced by d − i. The Glynn hyperovals for d = 5 are equivalent to translation hyperovals, while the Glynn type (II) hyperovals for d = 7 and d = 9 are respectively equivalent to the Segre hyperoval D(x^{6}) and the Glynn type (I) hyperoval D(x^{160}). These equivalences all follow from Lemma 2.3 below. It can be shown using Lemma 2.3 that the hyperovals listed in (2.1)–(2.5) are all mutually projectively inequivalent. For example, to show that the Segre hyperovals are inequivalent to the translation hyperovals, one shows that none of 6, 1/6, −5, −1/5, 6/5, or 5/6 (mod q − 1) can equal a power of 2 (mod q − 1), where q = 2^{d} for odd d ≥ 5. The computations involved are tedious but straightforward.

Glynn [8] conjectured that the hyperovals listed in (2.1)–(2.5) (together with the equivalent hyperovals given by Lemma 2.3 below) comprise all monomial hyperovals. This conjecture still remains open. Some progress was made in a recent paper by Cherowitzo and Storme [7].

Lemma 2.3. ([8], [22]) Let q > 2 be a power of 2. Two monomial hyperovals D(x^{j}) and D(x^{k}) in P G(2, q) are projectively equivalent if and only if j ≡ k, 1/k, 1 − k, 1/(1 − k), k/(k − 1), or (k − 1)/k (mod q − 1).

Proof: First, if D(x^{k}) is a monomial hyperoval in P G(2, q), then it is well known that for any j congruent to k, 1/k, 1−k, 1/(1−k), k/(k−1), or (k−1)/k modulo q−1, D(x^{j}) is projectively equivalent to D(x^{k}) (see [8]). Conversely, it follows from [22, Theorem 12.5.3] that if D(x^{j}) is projectively equivalent to D(x^{k}), then j is congruent to one of k, 1/k, 1 − k, 1/(1 − k), k/(k − 1), (k − 1)/k modulo q − 1. This completes the proof.

Let τ: 𝔽_{2^{d}} → 𝔽_{2^{d}} be defined by

τ(x) = x + x^{k},

and let Im τ be the image of the map τ. We need the following lemma from Maschietti [21]. For the convenience of the reader, we include a proof. In the statement of the lemma, and its proof, we use the convention that points in P G(2, q) are labelled as (z, x, y).

Lemma 2.4. Let q = 2^{d}. The (q +2)-set D(x^{k}) = {(1, t, t^{k}) | t ∈ 𝔽_{q}}∪{(0, 1, 0), (0, 0, 1)} in P G(2, q) is a hyperoval if and only if (k, q − 1) = 1 and τ is a two-to-one map from 𝔽_{q} into itself.

Proof: If D(x^{k}) is a hyperoval, then x^{k} is a permutation polynomial on 𝔽_{q}, so (k, q − 1) = 1. Furthermore, any affine line y = x + a (a ∈ 𝔽_{q}) meets D(x^{k}) at either 0 or 2 distinct points, which implies that x^{k} + x + a = 0 has either 0 or 2 distinct solutions in 𝔽_{q}, that is, the map τ is two-to-one.

Conversely, if τ is two-to-one, then the equation x^{k} + x = 0 has exactly two solutions, namely 0 and 1. Hence, there is no (k − 1)th root of 1 distinct from 1 in 𝔽_{q}, so that (k − 1, q − 1) = 1.

It is straightforward to show that a line of P G(2, q) with homogeneous equation cy = ax + bz, with abc = 0, intersects D(x^{k}) at either 0 or 2 points. It remains to show that the line y = ax + bz, with ab ≠ 0, intersects D(x^{k}) at either 0 or 2 points.

It is clear that there are no intersection points (0, x, y) of the line with D(x^{k}). Thus set z = 1 and consider the affine equation x^{k} = ax + b. We must show that this equation has 0 or 2 solutions. This follows from the hypothesis that τ is two-to-one, as can be seen after making the change of variable x = a^{\frac{1}{k−1}} x′. This completes the proof.

Remark: From Lemma 2.4 and its proof, it follows that when D(x^{k}) is a hyperoval in P G(2, q), with q = 2^{d}, then k and k − 1 are both relatively prime to q − 1.

Using the geometry of hyperovals, Maschietti [21] proved that if D(x^{k}) is a hyperoval in P G(2, 2^{d}), then

D_{k,d} = Im τ \ {0}

is a (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1) difference set in 𝔽_{2^{d}}^{∗}. In the following theorem, we give a simpler proof using Jacobi sums.

Theorem 2.5. Let q = 2^{d}. If D(x^{k}) = {(1, t, t^{k}) | t ∈ 𝔽_{q}} ∪ {(0, 1, 0), (0, 0, 1)} is a hyperoval in P G(2, q), then D_{k,d} = Im τ \ {0} is a (q − 1, q/2 − 1, q/4 − 1) difference set in 𝔽_{q}^{∗}.

Proof: Let χ be a nontrivial multiplicative character of 𝔽_{q}. Since D(x^{k}) is a hyperoval, τ is two-to-one by Lemma 2.4, and we have

χ(D_{k,d}) = \frac{1}{2} ∑_{x∈𝔽_{q}} χ(x + x^{k}) = \frac{1}{2} ∑_{x∈𝔽_{q}} χ(x)χ(1 + x^{k−1}).

By the previous remark, (k − 1, q − 1) = 1, so there exists a multiplicative character ϕ of 𝔽_{q} such that χ = ϕ^{k−1}. Hence

χ(D_{k,d}) = \frac{1}{2} ∑_{x∈𝔽_{q}} ϕ(x^{k−1})χ(1 + x^{k−1}) = \frac{1}{2}J(ϕ, χ).  (2.6)

Noting that ϕχ = ϕ^{k} is nontrivial, we have, by (1.5), χ(D_{k,d})\overline{χ(D_{k,d})} = 2^{d−2}. Now the theorem follows from Lemma 1.1.

The following proposition shows that two projectively equivalent monomial hyperovals give rise to two equivalent cyclic difference sets under the construction of Theorem 2.5.

Proposition 2.6. Let q = 2^{d}, q > 2. If D(x^{k}) and D(x^{j}) are two projectively equivalent monomial hyperovals in P G(2, q), then the corresponding difference sets D_{k,d} and D_{j,d} constructed in Theorem 2.5 are equivalent.

Proof: By Lemma 2.4, we know that j is congruent to one of k, 1/k, 1 − k, 1/(1 − k), k/(k − 1), (k − 1)/k modulo q − 1. Now direct calculation shows that

D_{\frac{k}{k−1} ,d} = D_{\frac{k−1}{k} ,d} = D_{k,d}^{(k−1)},  (2.7)
D_{1−k,d} = D_{\frac{1}{1−k} ,d} = D_{k,d}^{( \frac{1−k}{k})},  (2.8)
D_{\frac{1}{k} ,d} = D_{k,d},  (2.9)

where D^{(t)} = {d^{t} | d ∈ D}. For example, to prove (2.7), write c = x + x^{k}, make the variable change x = c/y, then multiply both sides by y^{k}. This completes the proof of the proposition.

The difference sets arising from the regular and translation hyperovals D(x^{2^{i}}) are the Singer difference sets {y ∈ 𝔽_{2^{d}}^{∗} | Tr(y) = 0}. This follows from Lemma 2.4 and Hilbert’s Theorem 90 [17, p. 56]. It is an interesting problem to determine whether the cyclic difference sets arising from the Segre and Glynn hyperovals are inequivalent to each other and to the previously known ones (such as Singer difference sets, quadratic residue difference sets, GMW difference sets). We approach these problems by studying the 2-ranks (as defined in Section 3) of these cyclic difference sets. Our conclusions are presented in Theorems 6.2, 6.3, and 6.8.

3. Stickelberger’s Theorem and the p-ranks of Cyclic Difference Sets

We start this section by reviewing a few standard notions from design theory. We refer the reader to [15, p. 243] for details and more information.

Let G be a (multiplicative) Abelian group of order v, and let D be a (v, K, λ) difference set in G. Then D = (P, B) is a (v, K, λ) symmetric design with a regular automorphism group G, where the set P of points of D is G, and where the set B of blocks of D is {gD | g ∈ G}. (As it turns out, the blocks are all distinct.) This design is usually called the development of D. The incidence matrix of D is the matrix A whose rows are indexed by the blocks B of D and whose columns are indexed by the points g of D, where the entry A_{B,g} in row B and column g is 1 if g ∈ B, and 0 otherwise.

The p-ary code of D, denoted C_{p}(D), is defined to be the row space of A over 𝔽_{p}, the field of p elements. This code is also the p-ary code of D, denoted by C_{p}(D). The 𝔽_{p}-dimension of C_{p}(D) is usually called the p-rank of the difference set D. We shall also denote it by rank_{p}D. It is well-known that C_{p}(D) is of interest only if p | (K − λ); see [5] or [15, p. 297]. So from now on, we always assume that p | (K − λ).

The p-ranks of difference sets have been studied extensively for several reasons. First, if D_{1} and D_{2} are two equivalent (v, K, λ) difference sets in an Abelian group G, then the p-ranks of D_{1} and D_{2} are the same. Therefore, the p-ranks can help us to distinguish two inequivalent difference sets.

Secondly, let D be a cyclic (v, K, λ) difference set in ℤ/vℤ with 2|(K −λ). Corresponding to D is the characteristic sequence {a_{i}}_{0≤i≤v−1} given by a_{i} = 1 if i ∈ D, and a_{i} = 0 otherwise. This sequence has a two-level autocorrelation function (see [10, p. 62]). The linear complexity (or linear span) of {a_{i}} is the smallest degree of a linear shift register over 𝔽_{2} which is capable of generating {a_{i}}. It turns out that the linear complexity of {a_{i}} is the same as the 2-rank of D. Therefore, the study of 2-ranks of cyclic difference sets is important for communications and cryptographic applications; see [10].

A third reason is provided by Theorem 3.2 below. MacWilliams and Mann [19], Goethals and Delsarte [9], and Smith [26] proved that the p-rank of the ((q^{d} − 1)/(q − 1), (q^{d−1} − 1)/(q − 1), (q^{d−2} − 1)/(q − 1)) Singer difference set is \binom{p+d−2}{d−1}^{s} + 1, where q = p^{s} for prime p. Subsequently, Hamada [12] made the following conjecture.

Conjecture 3.1. Let D be a symmetric design with Singer parameters ((q^{d} − 1)/(q − 1), (q^{d−1} − 1)/(q − 1), (q^{d−2} − 1)/(q − 1)), where q = p^{s}. Then one has

rank_{p}D ≥ \binom{p + d − 2}{d − 1}^{s} + 1,

with equality if and only if D is the development of a classical Singer difference set.

This conjecture still remains open. But Hamada and Ohmori [13] proved the following interesting result in this direction.

Theorem 3.2. Let D be a symmetric design with parameters (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1). Then D is the development of the cyclic Singer difference set with these parameters if and only if rank_{2}D = d + 1.

In Theorem 3.5, we will give a simple new proof of the p-rank formula for the classical Singer difference sets. Our approach is different from previous ones in that it uses Gauss and Jacobi sums, and Stickelberger’s theorem on the prime ideal factorization of Gauss sums.

We first quote a result (Theorem 3.3) of MacWilliams and Mann [19]. For the convenience of the reader, we include a proof here.

Let B = ∑_{g∈G} b_{g}g be an element of the group algebra F [G], where G is an Abelian group and F is a field. We associate with B the matrix (b_{g(g′)^{−1}}), whose rows and columns are labeled by the group elements g and g′. The rank of (b_{g(g′)^{−1}}) is called the rank of B. We remark that in particular, if B = ∑_{g∈D} g, where D is a (v, K, λ) difference set in G, then the p-rank of D, i.e., the 𝔽_{p}-dimension of the code C_{p}(D), is the same as the rank of B over 𝔽_{p}. The reason is that the rows and columns of the incidence matrix of the development of D can be arranged so that the incidence matrix is the transpose (b_{g(g′)^{−1}})^{T} of the matrix (b_{g(g′)^{−1}}).

Theorem 3.3. Let G be an Abelian group of order v and exponent v^{∗}, let F be a field of characteristic p not dividing v which contains the v^{∗}th roots of unity, and let B = ∑_{g∈G} b_{g}g be an element of the group algebra F [G]. Then the rank of B over F is equal to the number of characters χ : G → F^{∗} satisfying χ(B) ≠ 0, where χ(B) = ∑_{g∈G} b_{g}χ(g).

Proof: Let (χ(g)) be a matrix whose rows are labeled by the v characters χ and whose columns are labeled by the v group elements g, so that the entry in row χ and column g is χ(g). This matrix is nonsingular since \frac{1}{v}(χ(g))(χ(g^{−1}))^{T} is the identity matrix. The result now follows from the identity

(χ(g))(b_{g(g′)^{−1}})(χ(g^{−1}))^{T} = v · diag(χ(B)).

We will also need Stickelberger’s result (Theorem 3.4) on the prime ideal decomposition of Gauss sums. We first introduce some notation.

Let p be a prime, q = p^{s}, and let ξ_{q−1} be a (complex) primitive (q − 1)th root of unity. Fix any prime ideal 𝔭 in ℤ[ξ_{q−1}] lying over p. Then ℤ[ξ_{q−1}]/𝔭 is a finite field of order q, which we identify with 𝔽_{q}. Let ω_{𝔭} be the Teichmüller character on 𝔽_{q}, i.e., an isomorphism

ω_{𝔭} : 𝔽_{q}^{∗} → {1, ξ_{q−1}, ξ_{q−1}^{2}, …, ξ_{q−1}^{q−2}}

satisfying

ω_{𝔭}(α) (mod 𝔭) = α,  (3.1)

for all α in 𝔽_{q}^{∗}. The Teichmüller character ω_{𝔭} has order q − 1; hence it generates all multiplicative characters of 𝔽_{q}.

Let 𝔓 be the prime ideal of ℤ[ξ_{q−1}, ξ_{p}] lying above 𝔭. For an integer a, let s(a) = v_{𝔓}(g(ω_{𝔭}^{−a})), where v_{𝔓} is the 𝔓-adic valuation. Thus 𝔓^{s(a)} || g(ω_{𝔭}^{−a}). The following evaluation of s(a) is due to Stickelberger (see [4, p. 344], [29, p. 96]).

Theorem 3.4. Let p be a prime, and q = p^{s}. For an integer a not divisible by q − 1, let a_{0} + a_{1}p + a_{2}p^{2} + ⋯ + a_{s−1}p^{s−1}, 0 ≤ a_{i} ≤ p − 1, be the p-adic expansion of the reduction of a modulo q − 1. Then

s(a) = a_{0} + a_{1} + ⋯ + a_{s−1},

that is, s(a) is the sum of the p-adic digits of the reduction of a modulo q − 1.

An easily proved consequence of Theorem 3.4 is the formula [4, p. 347], [29, p. 98]

s(a) = \frac{p − 1}{q − 1} ∑_{i=0}^{s−1} L(ap^{i}),  (3.2)

where L(x) is the reduction of x modulo q − 1.

We are now ready to give a new proof of the p-rank formula for Singer difference sets.

Theorem 3.5. For q = p^{s}, let L_{0} be the (\frac{q^{d}−1}{q−1}, \frac{q^{d−1}−1}{q−1}, \frac{q^{d−2}−1}{q−1}) difference set in the quotient group 𝔽_{q^{d}}^{∗}/𝔽_{q}^{∗}, as in Theorem 2.1. Then the p-rank of L_{0} is

\binom{p + d − 2}{d − 1}^{s} + 1.

Proof: For 𝔭 a prime ideal in ℤ[ξ_{q^{d}−1}] lying over p, let ω_{𝔭} be the Teichmüller character on 𝔽_{q^{d}} and let χ = ω_{𝔭}^{−(q−1)}. Then χ is a generator of the character group of 𝔽_{q^{d}}^{∗}/𝔽_{q}^{∗}. From

the proof of Theorem 2.1, we know that for each a, 0 < a < \frac{q^{d}−1}{q−1},

q · χ^{a}(L_{0}) = g(χ^{a}).  (3.3)

Note that if χ_{0} is the trivial character, then χ_{0}(L_{0}) = |L_{0}| ≢ 0 (mod p). Thus by the definition (3.1) of the Teichmüller character and Theorem 3.3, the p-rank of L_{0} is 1 + A(q, d), where A(q, d) is the number of χ^{a}, 0 < a < (q^{d} − 1)/(q − 1), such that χ^{a}(L_{0})(mod 𝔭) ≠ 0.

Let 𝔓 be the prime of ℤ[ξ_{q^{d}−1}, ξ_{p}] lying above 𝔭. Since 𝔓 | χ^{a}(L_{0}) if and only if 𝔭 | χ^{a}(L_{0}), A(q, d) is equal to the number of χ^{a}, 0 < a < (q^{d} − 1)/(q − 1), such that 𝔓 |̸ χ^{a}(L_{0}).

By the definition of s(a) (with q^{d} in place of q), 𝔓^{s((q−1)a)} || g(χ^{a}). Since 𝔓^{(p−1)s} || q, we see from (3.3) that A(q, d) is equal to the number of a, 0 < a < (q^{d} − 1)/(q − 1), such that s((q − 1)a) = (p − 1)s, which, in turn, is equal to the number of x, 0 < x < q^{d} − 1, (q − 1) | x, such that s(x) = (p − 1)s.

For x with 0 < x < q^{d} − 1, write x = ∑_{j=0}^{d−1} ∑_{i=0}^{s−1} x_{i,j}p^{i}q^{j}, 0 ≤ x_{i,j} < p. By (3.2) (with q^{d} in place of q),

s(x) = \frac{p − 1}{q^{d} − 1} ∑_{j=0}^{d−1} ∑_{i=0}^{s−1} L(xp^{i}q^{j}),  (3.4)

where L(y) denotes the reduction of y modulo q^{d} − 1. Suppose that (q − 1) | x and s(x) = (p − 1)s. Then, by (3.4),

(q^{d} − 1)s = ∑_{j=0}^{d−1} ∑_{i=0}^{s−1} L(xp^{i}q^{j}).  (3.5)

Since

0 < ∑_{j=0}^{d−1} L(xp^{i}q^{j}) ≡ ∑_{j=0}^{d−1} xp^{i}q^{j} ≡ 0 (mod q^{d} − 1),

it follows that ∑_{j=0}^{d−1} L(xp^{i}q^{j}) ≥ q^{d} − 1 for each i. Thus, by (3.5),

∑_{j=0}^{d−1} L(xp^{i}q^{j}) = q^{d} − 1  (3.6)

for each i. Write x = a_{0} + a_{1}q + ⋯ + a_{d−1}q^{d−1}, where a_{j} = ∑_{i=0}^{s−1} x_{i,j}p^{i}, 0 ≤ j ≤ d − 1. Then by (3.6) with i = 0, we have a_{0} + a_{1} + ⋯ + a_{d−1} = q − 1. Thus ∑_{j=0}^{d−1} x_{0,j} ≥ p − 1. Similarly, by (3.6) for general i, we obtain

∑_{j=0}^{d−1} x_{i,j} ≥ p − 1  (3.7)

for all i. As

(p − 1)s ≤ ∑_{i=0}^{s−1} ∑_{j=0}^{d−1} x_{i,j} = s(x) = (p − 1)s,

it follows that equality holds in (3.7) for each i. The equation ∑_{j=0}^{d−1} x_{i,j} = p − 1, 0 ≤ x_{i,j} < p, has \binom{p+d−2}{d−1} solutions for each i, 0 ≤ i < s. Therefore A(q, d) = \binom{p+d−2}{d−1}^{s}. This completes the proof.

Next we show how to compute the 2-ranks of those cyclic difference sets D_{k,d} arising from monomial hyperovals in Section 2. For succinctness, we will actually state the theorem in terms of the 2-rank of the complement \overline{D_{k,d}}. (It follows easily from (1.1) that if D is a (v, K, λ) difference set in G then the complement \overline{D} of D in G is a (v, v − K, λ − 2K + v) difference set in G.) This is just a matter of convenience, as the 2-rank of the difference set D_{k,d} is exactly 1 more than the 2-rank of the complement \overline{D_{k,d}} (see the proof of Theorem 3.6).

Theorem 3.6. Let D_{k,d} be the (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1) cyclic difference set in 𝔽_{2^{d}}^{∗} constructed from the hyperoval D(x^{k}) as in Theorem 2.5, and let \overline{D_{k,d}} be the complement of D_{k,d} in 𝔽_{2^{d}}^{∗}. Then the 2-rank of \overline{D_{k,d}} is equal to the number of a’s, 0 < a < 2^{d} − 1, such that

s(a) + s((k − 1)a) = s(ka) + 1,  (3.8)

where s(a) is as defined above Theorem 3.4 with q = 2^{d}.

Proof: For 𝔭 a prime ideal in ℤ[ξ_{2^{d}−1}] lying over 2, let ω = ω_{𝔭} be the Teichmüller character on 𝔽_{2^{d}}. By (2.6), we see that for each a, 0 < a < 2^{d} − 1,

−2 · ω^{−(k−1)a} (\overline{D_{k,d}}) = J(ω^{−a}, ω^{−(k−1)a}).  (3.9)

By the definition of s(a) (with q = 2^{d}) and (1.4),

𝔭^{s(a)+s((k−1)a)−s(ka)} || J(ω^{−a}, ω^{−(k−1)a}).  (3.10)

Since 𝔭 || 2, we see from (3.9) that the number of a’s, 0 < a < 2^{d} − 1, such that ω^{−(k−1)a} (\overline{D_{k,d}}) (mod 𝔭) ≠ 0, is equal to the number of a’s, 0 < a < 2^{d} − 1, such that s(a) + s((k − 1)a) = s(ka) + 1. Since the cardinality of \overline{D_{k,d}} is 2^{d−1} ≡ 0 (mod 2), χ_{0}(\overline{D_{k,d}}) (mod 𝔭) equals 0 for the trivial character χ_{0}. (In contrast, χ_{0}(D_{k,d}) (mod 𝔭) equals 1, which is why we prefer to state the theorem in terms of \overline{D_{k,d}}.) Thus, by Theorem 3.3, we see that the 2-rank of \overline{D_{k,d}} is equal to the number of a’s, 0 < a < 2^{d} − 1, for which s(a) + s((k − 1)a) = s(ka) + 1. This completes the proof.

Let B_{k}(d) be the number of a’s, 0 < a < 2^{d} −1, for which s(a)+s((k −1)a) = s(ka)+1. By the above theorem, in order to compute the 2-rank of D_{k,d}, we need to compute B_{k}(d). We will discuss the determination of B_{k}(d) in the next section. But first of all, we observe that B_{k}(d) is always a multiple of d. We state this as a lemma.

Lemma 3.7. Let B_{k}(d) be the number of a’s, 0 < a < 2^{d}−1, for which s(a)+s((k−1)a) = s(ka) + 1. Then d | B_{k}(d).

Proof: For any a, 0 < a < 2^{d} − 1, it follows easily from (3.2) that

s(a) + s((k − 1)a) − s(ka) = ∑_{i=0}^{d−1} (⌊\frac{2^{i}ka}{2^{d} − 1}⌋ − ⌊\frac{2^{i}a}{2^{d} − 1}⌋ − ⌊\frac{2^{i}(k − 1)a}{2^{d} − 1}⌋) , (3.11)

where ⌊x⌋ denotes the greatest integer ≤ x (see [4, p. 349], [29, p. 98]).

Clearly, if a is a solution to s(a) + s((k − 1)a) = s(ka) + 1, then a · 2^{j} is also a solution, for all j, 0 ≤ j ≤ d − 1. We contend that a · 2^{j}, j = 0, 1, …, d − 1, are necessarily distinct modulo 2^{d} − 1. If they were not distinct, then the sum on i in (3.11) would have more than one term equal to 1, contradicting the fact that s(a) + s((k − 1)a) − s(ka) = 1. This completes the proof.

4. Enumeration of Cyclic Binary Strings and Computation of 2-ranks

Let d be an integer ≥ 2. In this section, we are concerned with determining explicitly the 2-ranks of the difference sets \overline{D_{k,d}} corresponding to the hyperovals D(x^{k}) (which, by the remark preceding Theorem 3.6, is equivalent to determining the 2-ranks of the difference sets D_{k,d} themselves). By Theorem 3.6, the 2-rank of \overline{D_{k,d}} equals the number B_{k}(d) of solutions a, 0 < a < 2^{d} − 1, to equation (3.8). The case of the difference sets arising from the translation and the regular hyperovals is already covered by Theorem 3.5, as these difference sets are instances of Singer difference sets (see the last paragraph of Section 2). Hence, we concentrate on the difference sets arising from the Segre and the Glynn hyperovals. Most of the time we will not actually deal with the number B_{k}(d) of solutions itself, but with the quantity A_{k}(d) = B_{k}(d)/d. For the convenience of the reader we have listed the first few values for A_{6}(d) (the Segre case, see (2.3)), for A_{σ+γ}(d) (the Glynn type (I) case, see (2.4)), and for A_{3σ+4}(d) (the Glynn type (II) case, see (2.5)). These values were originally found by the computer algebra package MAGMA [6].

\begin{matrix}d & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 & 25 \\ A_{6}(d) & 1 & 3 & 5 & 9 & 15 & 25 & 41 & 67 & 109 & 177 & 287 & 465 \\ A_{σ+γ}(d) & 1 & 1 & 3 & 7 & 13 & 23 & 45 & 87 & 167 & 321 & 619 & 1193 \\ A_{3σ+4}(d) & 1 & 1 & 5 & 7 & 21 & 37 & 89 & 173 & 383 & 777 & 1665 & 3441 \end{matrix} Table 1

When we entered the values from the table into the Maple package gfun [23], we were able to guess a linear recurrence for the numbers A_{k}(d) in each of the three cases. These recurrences are established by rather elaborate combinatorial arguments in Theorems 4.3, 4.6 and 4.8. Consequently, we obtain explicit formulas for the 2-ranks of the difference sets D_{k,d} corresponding to the Segre and Glynn hyperovals D(x^{k}); see Corollaries 4.4, 4.7 and 4.9.

Table 1 suggests that for d ≥ 15 the 2-ranks A_{6}(d) for the Segre case are the smallest, while the 2-ranks A_{3σ+4}(d) for the Glynn type (II) case are the largest. This observation is established in Lemma 6.1.

Our first goal is to determine B_{6}(d) explicitly in terms of Fibonacci numbers. The result, Theorem 4.3, was conjectured by Xiang [31].

Given any integer x not divisible by 2^{d} − 1, recall that by Theorem 3.4 with q = 2^{d}, s(x) equals the number of 1’s in the binary representation of x reduced modulo 2^{d} − 1. Now, the binary representation of 2x mod 2^{d} − 1 is simply the rotation of the binary representation of x mod 2^{d} − 1 by “one step”, i.e., all the digits are moved one step to the left, with a 1 that would be moved beyond the leftmost place moved (“rotated”) to the rightmost place. This implies that s(x) = s(2x). Therefore, given any solution to (3.8), multiples of the solution by powers of 2 will also give solutions to (3.8).

Proposition 4.1. Let d be an integer ≥ 2. The binary representations of all the solutions a mod 2^{d} − 1 to the equation

s(a) + s(5a) = s(6a) + 1  (4.1)

can be constructed by the following procedure:

Step 1. Form all the possible binary strings of length ≤ d by concatenating blocks of the form 01, 0011, 00111, subject to the following restrictions: (A) In a string of length < d, the rightmost block must be 01, and the block 00111 must

not occur. (B) In a string of length d, the block 00111 occurs exactly once, namely, as the rightmost

block. (In particular, strings of length d can only occur for odd d.) Step 2. Given a string of length k obtained through Step 1, append (d − k) 0’s on the

left to form a string of length d.

Step 3. All the solutions a mod 2^{d} − 1 to (4.1), or rather their binary representations, are obtained by forming all possible rotations of the strings that were constructed in Step 2.

Before we move on to a proof of the proposition, we illustrate this construction by an example.

Example 4.2. Let d = 9. Then all possible strings formed in Step 1 are (the bars indicate separation of blocks)

01, 01|01, 01|01|01, 01|01|01|01, 0011|01,
0011|01|01, 01|0011|01, 01|01|00111, 0011|00111.  (4.2)

Hence, according to Steps 2 and 3, the solutions a mod 2^{d} − 1 to (4.1), in binary notation, are all the possible rotations of

000000001, 000000101, 000010101, 001010101, 000001101,
000110101, 001001101, 010100111, 001100111.  (4.3)

Therefore, the solutions are

1, 5, 21, 85, 13, 53, 77, 167, 103,

and their multiples by powers of 2, for a total of 9 · 9 = 81 solutions.

Proof of Proposition 4.1. It is straightforward to check that the numbers obtained by the proposed construction are indeed solutions to (4.1). We leave this to the reader.

It remains to be shown that there cannot be other solutions to (4.1). We do this by performing a case-by-case analysis which rules out all other possibilities.

From now on, when we talk about some number x mod 2^{d} − 1, we always assume that x is reduced mod 2^{d} − 1 to a number between 0 and 2^{d} − 2. When we refer to a, 5a, and 6a, these numbers are to be viewed mod 2^{d} − 1.

Before we start our case-by-case analysis, it is helpful to recall what we would like to achieve. We want to find each number a such that the number of 1’s in the binary representation of 6a is exactly one less than the number of 1’s in the binary representation of a plus the number of 1’s in the binary representation of 5a.

On the other hand, by carrying out the addition a + 5a = 6a (mod 2^{d} − 1), we see that the number of 1’s in the binary representation of 6a can be at most the total of the number of 1’s in the binary representations of a and 5a minus the number of instances of a 1 occurring at the same place in a and 5a. To give an example, if d = 5, and if a = 11010, so 5a = 00110, then the number of 1’s in 6a can be at most 3 + 2 − 1 = 4. (The number of 1’s in the binary representation of a is 3, the number of 1’s in the binary representation of 5a is 2, and there is a 1 in both a and 5a in the second position from the right.) In fact, 6a = 00001, so the number of 1’s in 6a is even less.

Thus we can limit our search to a’s for which there is exactly one such instance of a 1 in the same position in a and 5a. In particular, if we detect two such instances in a and 5a, then a cannot be a solution to (4.1). To guarantee that the number of 1’s in the binary representation of 6a is exactly one less (as opposed to two or more less), we must have a 0 in both a and 5a in the position which is immediately to the left of the position where 1 occurs in both a and 5a.

In the analysis that follows, it does not matter whether we consider a or 2^{m}a, for a positive integer m. In terms of binary representations this means that it does not matter whether we consider the binary representation of a or any cyclic permutation of it.

Now we turn to our case-by-case analysis. Since Proposition 4.1 is easily checked for the cases d = 2, 3, 4, 5, we may assume in the following that d ≥ 6.

Case 1. The block 11111 occurs in the binary representation of a. Suppose that 11111 occurs in the binary representation of a. Then, since 5a = a + 4a, we have

\begin{matrix}a = & ….11111. . \\ 4a = & . .11111…. \\ 5a = & ….11. . . . . \end{matrix}

So, there are two instances of 1’s in the same position in a and 5a. Hence, a cannot be a solution to (4.1).

Case 2. The block 1111 occurs in the binary representation of a. Since we already ruled out that 11111 occurs, we may assume that there is a 0 before, and a 0 after 1111. We have

\begin{matrix}a = & ….011110. . \\ 4a = & . .011110…. \\ 5a = & . . . . . . . \underline{.} …. \end{matrix}

Now, if in the underlined position there is no 1 carrying over from the right, then the addition would give

\begin{matrix}a = & ….011110. . \\ 4a = & . .011110…. \\ 5a = & . . . . .101…. \end{matrix}

Again we are encountering two positions with 1’s in both a and 5a, and thus a cannot be a solution to (4.1).

On the other hand, if a 1 does carry over, then we have

\begin{matrix}a = & ….011110. . \\ 4a = & . .011110…. \\ 5a = & . . . . .110…. \end{matrix}

So again, a cannot be a solution to (4.1).

Case 3. The block 111 occurs in the binary representation of a. Since we already ruled out that 1111 occurs, we may assume that there is a 0 before, and a 0 after 111. We have

\begin{matrix}a = & ….01110. . \\ 4a = & . .01110…. \\ 5a = & . . . . . . . . . . . \end{matrix}

If to the left of the block 01110 we would have a 1,

\begin{matrix}a = & ….101110. . \\ 4a = & . .101110…. \\ 5a = & . . . . . . . \underline{.} …. \end{matrix}

then, regardless of whether a 1 carries over to the underlined position or not (see Case 2 for an analogous consideration), we would obtain two positions with 1’s in both a and 5a, and so a cannot be a solution to (4.1).

Therefore, the only way to have the block 111 is in the form … 001110 . . ..

Case 4. The block 0110 occurs in the binary representation of a. Let us first assume that we have a 1 on the left of this block, so that we encounter

\begin{matrix}a = & ….10110. . \\ 4a = & . .10110…. \\ 5a = & . . . . . . \underline{.} …. \end{matrix}

Now, if no 1 carries over to the underlined position, then we have

\begin{matrix}a = & ….10110. . \\ 4a = & . .10110…. \\ 5a = & . . . . .1\underline{1}…. \end{matrix}

So, there is a 1 in that position in both a and 5a, and there is a 1 just left of that position in 5a. By what we observed earlier, such a number a cannot be a solution to (4.1). If 1 does carry over to the underlined position, then we have

\begin{matrix}a = & …x10110. . \\ 4a = & . .10110…. \\ 5a = & …y10\underline{0}…. \end{matrix}

where either x or y equals 1. Again, a cannot be a solution to (4.1).

Therefore, the only way to have a block 0110 is in the form … 00110 . . ..

At this point, let us summarize our observations. The conclusions from the considerations in Cases 1–4 are that the (cyclic) binary strings of length d for a that we are looking for must be built out of the blocks 00111, 0011, and 01, with possibly filling 0’s placed in between.

It is not difficult to see that it is only possible to insert filling 0’s in one place in a (cyclic) binary string. For, otherwise we would have at least two instances of a 1 in the same place in a and 5a. For the same reason, if a block 00111 occurs, then it can appear only once, and no filling 0’s are allowed. Finally, it is easy to see that an all 0 string, or a string built out of blocks of the form 0011 plus filling 0’s, or a string where filling 0’s are adjacent to two consecutive 1’s, does not give a solution to (4.1). All the remaining possibilities are indeed covered by the construction in the statement of Proposition 4.1. This concludes the proof of the proposition.

Proposition 4.1 yields the following formula for the number B_{6}(d) of solutions to (4.1).

Theorem 4.3. Write A_{6}(d) = B_{6}(d)/d, where B_{6}(d) is the number of solutions mod 2^{d} − 1 to equation (4.1). Then for d ≥ 6, A_{6}(d) satisfies the recurrence

A_{6}(d) = A_{6}(d − 2) + A_{6}(d − 4) + 1,  (4.4)

with initial conditions A_{6}(2) = 0, A_{6}(3) = 1, A_{6}(4) = 1, A_{6}(5) = 3. Equivalently, for any positive integer m we have B_{6}(2m) = 2m(F_{m} − 1) and B_{6}(2m + 1) = (2m + 1)(2F_{m} − 1), where F_{n} is the n-th Fibonacci number (F_{0} = F_{1} = 1).

Proof: Clearly, the recurrence (4.4) can be viewed as a recurrence for the number B_{6}(d)/d of strings that are constructed in Step 1 of Proposition 4.1, i.e., before appending 0’s and rotating the obtained strings of length d. (There are B_{6}(d)/d such strings, since due to the particular form of the strings, all the d rotations in Step 3 are indeed different from each other.)

On the basis of this observation, it is easy to demonstrate the recurrence (4.4). For, given d, the strings that are constructed in Step 1 can be separated into three sets: first, there is the string 01 of length 2, then there is the set of strings of length greater than 2 with leftmost block 01, and finally there is the set of strings with leftmost block 0011. The former set of strings can be obtained by performing Step 1 with d replaced by d − 2 and then appending 01 to the left of each of the obtained strings. The latter set of strings can be obtained by performing Step 1 with d replaced by d − 4 and then appending 0011 to the left of each of the obtained strings. Summing, we obtain the recurrence (4.4) for B_{6}(d)/d.

From the recurrence, the explicit formulas for B_{6}(d) in terms of Fibonacci numbers follow immediately.

As a corollary, we have the following result on the 2-ranks of those cyclic difference sets constructed from the Segre hyperovals.

Corollary 4.4. Let d be an odd integer, d ≥ 5, and let D_{6,d} be the (2^{d}−1, 2^{d−1}−1, 2^{d−2}−1) cyclic difference set in 𝔽_{2^{d}}^{∗} corresponding to the Segre hyperoval D(x^{6}), as in Theorem 2.5 with k = 6. Let \overline{D_{6,d}} be the complement of D_{6,d} in 𝔽_{2^{d}}^{∗}. Then the 2-rank B_{6}(d) of \overline{D_{6,d}} is equal to d(2F_{(d−1)/2} − 1), where F_{n} is the nth Fibonacci number (F_{0} = F_{1} = 1).

Proof: This is immediate from Theorem 3.6 and Theorem 4.3.

Next we turn to the computation of the 2-ranks of the cyclic difference set arising from the two types of Glynn hyperovals. According to Theorem 3.6, (2.4) and (2.5), we need to compute the number B_{k}(d) of solutions a mod 2^{d} − 1 to

s(a) + s((k − 1)a) = s(ka) + 1,  (4.5)

where d is odd, d ≥ 7, and k = σ + γ or k = 3σ + 4, with σ = 2^{(d+1)/2}, and γ = 2^{(3d+1)/4} if d ≡ 1 mod 4, whereas γ = 2^{(d+1)/4} if d ≡ 3 mod 4. These are much more difficult problems than the counting problem in the case k = 6. We resolve them in Theorems 4.6 and 4.8 by making appeal to the so-called “transfer matrix method” (see [27, Sec. 4.7]). (We could have proved Theorem 4.3 by means of the transfer matrix method as well. We preferred to take the more direct approach via Proposition 4.1.)

In the proofs of Theorems 4.6 and 4.8, we will make use of the result (in the folklore) that when it is known (by some abstract means) that a sequence satisfies some linear recurrence, and when a bound for the order of the recurrence is also known, then one needs only to check a certain number of special instances of a specific recurrence to prove that the sequence satisfies this recurrence “always”. We give the precise statement in the lemma below. For the sake of completeness, we also supply a proof.

Lemma 4.5. Let (f_{n})_{n≥0} be a sequence of complex numbers. Suppose that we know that the generating function ∑_{n≥0} f_{n}z^{n} for the sequence is rational, i.e., that it equals p(z)/q(z), where p(z) and q(z) are polynomials in z, and that the degree of the numerator, p(z), is at most P, and the degree of the denominator, q(z), is at most Q. If the sequence (f_{n}) satisfies the recurrence

∑_{i=0}^{k} a_{i}f_{n−i} = c  (4.6)

for n = n_{0}, …, N, where n_{0} ≥ k, N = max{P +k+1, Q+n_{0}}, and where a_{0}, a_{1} …, a_{k} and c are some given complex numbers, then the recurrence (4.6) is satisfied for all n ≥ n_{0}.

Proof: Since (4.6) is satisfied for n = n_{0}, …, N, we have

a(z) ∑_{n≥0} f_{n}z^{n} = r(z) + c/(1 − z) + z^{N+1}S(z),  (4.7)

where a(z) = ∑_{i=0}^{k} a_{i}z^{i}, r(z) is a polynomial of degree less than n_{0}, and S(z) is some formal power series, the coefficients of which “measure” how (4.6) fails for n > N. In particular, S(z) vanishes if and only if (4.6) holds for all n ≥ n_{0}. Now we multiply both sides of (4.7) by (1 − z)q(z). This gives

(1 − z)a(z)p(z) = (1 − z)q(z)r(z) + cq(z) + z^{N+1}(1 − z)q(z)S(z).

In this equation, the term on the left-hand side and the first two terms on the right-hand side all have degree less than N + 1. It follows that z^{N+1}(1 − z)q(z)S(z) = 0, whence S(z) = 0. This completes the proof.

Now we are ready to determine the number of solutions to (4.5) for the Glynn cases. We start with the Glynn type (II) case because it is easier to handle.

Theorem 4.6. Let d be an odd integer, d ≥ 3. Let B_{3σ+4}(d) be defined as in the first paragraph of this section, and let A_{3σ+4}(d) = B_{3σ+4}(d)/d. Then

A_{3σ+4}(d) = A_{3σ+4}(d − 2) + 3A_{3σ+4}(d − 4) − A_{3σ+4}(d − 6) − A_{3σ+4}(d − 8) + 1, (4.8)

for all odd d, d ≥ 11, with initial values as given in Table 1.

Proof: First of all, from the proof of Proposition 4.1, we see that the solutions a, 0 < a < 2^{d}−1, to equation (4.5) are characterized by the following property (the pertinent considerations in the proof of Proposition 4.1 are valid for generic k, i.e., they do not restrict to the case k = 6):

(4.9) There is exactly one instance of a 1 occurring at the same place in a and (k − 1)a, and immediately to the left of those 1’s there is a 0 in both a and (k − 1)a,

where we view a and (k − 1)a (mod 2^{d} − 1) as binary strings of length d.

We are actually concerned not with the number B_{k}(d) of all solutions to (4.5), but rather with A_{k}(d) = B_{k}(d)/d. Since any solution a immediately gives rise to d solutions by forming all possible rotations of a, we may, without loss of generality, restrict our attention to those solutions a where the instance of a 1 imposed by (4.9) occurs exactly in the middle of the string. The number A_{k}(d) then is the number of these special solutions.

Now, for a proof of the theorem, we define a bijection between these special solutions to (4.5) (with k = 3σ + 4, where σ = 2^{(d+1)/2}) and a set of closed walks in a certain directed graph D. As we demonstrate at the end, it then follows from first principles that the generating function for the number of these closed walks, and hence for the number of solutions to (4.5), is rational (see also [27, Sec. 4.7]). Finally, we check (4.8) for enough (odd) values of d so that Lemma 4.5 will imply that (4.8) has to hold for all odd d ≥ 11.

In order to motivate the construction of the aforementioned directed graph D, we analyse, for a given special solution a to (4.5), the computation of (k − 1)a and ka mod 2^{d} − 1. Let d = 2r − 1, with r ≥ 2, and let the binary representation of a be a_{2r−2} … a_{1}a_{0}. Since k − 1 = 3σ + 3 = 3 · 2^{(d+1)/2} + 3 = 2^{r+1} + 2^{r} + 2 + 1, we may compute (k − 1)a and ka = (k − 1)a + a mod 2^{d} − 1 as follows:

\begin{matrix}a = & a_{2r−2} & … & a_{r} & a_{r−1} & a_{r−2} & … & a_{0} \\ 2a = & a_{2r−3} & … & a_{r−1} & a_{r−2} & a_{r−3} & … & a_{2r−2} \\ 2^{r+1}a = & a_{r−3} & … & a_{2r−2} & a_{2r−3} & a_{2r−4} & … & a_{r−2} \\ 2^{r}a = & a_{r−2} & … & a_{0} & a_{2r−2} & a_{2r−3} & … & a_{r−1} \\ (k − 1)a = & y_{2r−2} & … & y_{r} & y_{r−1} & y_{r−2} & … & y_{0} \\ a = & a_{2r−2} & … & a_{r} & a_{r−1} & a_{r−2} & … & a_{0} \\ ka = & z_{2r−2} & … & z_{r} & z_{r−1} & z_{r−2} & … & z_{0} \end{matrix} \begin{matrix}\} & + \\ \} & + \end{matrix}  (4.10)

where

a_{i} + a_{i−1} + a_{r+i−2} + a_{r+i−1} + b_{i−1} = y_{i} + 2b_{i}, for i = 0, 1, …, 2r − 2,  (4.11)
y_{i} + a_{i} + c_{i−1} = z_{i} + 2c_{i}, for i = 0, 1, …, 2r − 2,  (4.12)

for some integers b_{i}, c_{i} with 0 ≤ b_{i} ≤ 3, i = 0, 1, …, 2r − 2, c_{r−1} = 1, and c_{i} = 0 for i = 0, 1, …, r − 2, r, …, 2r − 2, with the convention that indices are read modulo 2r − 1 throughout. The integer b_{i} is the carry-over from the ith place to the (i + 1)th during the addition that gives (k − 1)a in (4.10), while c_{i} is the carry-over from the ith place to the (i + 1)th during the addition of (k − 1)a and a in (4.10) that gives ka. Here, places are counted from the right starting with 0; for example, in the top row of (4.10), the digit a_{0} is in the 0th place and the digit a_{1} is in the 1th place. (Indeed, as is not difficult to see, there is a unique such choice of b_{i}’s and c_{i}’s which satisfy (4.11) and (4.12) such that the y_{i}’s and z_{i}’s are the digits in the additions given by (4.10).) Equation (4.12), together with the above assignments for the c_{i}’s, reflects the conditions imposed by (4.9) with the 1’s in the middle place.

The subsequent considerations become more transparent, if in (4.11) and (4.12) we perform a relabelling. Given a sequence (x_{i})_{i=0,...,2r−2}, where (x_{i}) can be any of (a_{i}), (b_{i}), (c_{i}), (y_{i}), or (z_{i}), define the new sequence (x̃_{j})_{j=0,...,2r−2} by x̃_{j} := x_{(r−1)j}. Note that since (r−1, d) = (r−1, 2r−1) = 1, the sequence (x̃_{j})_{j=0,...,2r−2} is a permutation of (x_{i})_{i=0,...,2r−2} (recall that indices are read modulo 2r − 1). Now, by putting i = (r − 1)j, equations (4.11) and (4.12) read, in terms of the transformed sequences,

ã_{j} + ã_{j+2} + ã_{j+3} + ã_{j+1} + b̃_{j+2} = ỹ_{j} + 2b̃_{j}, for j = 0, 1, …, 2r − 2,  (4.13)
ỹ_{j} + ã_{j} + c̃_{j+2} = z̃_{j} + 2c̃_{j}, for j = 0, 1, …, 2r − 2,  (4.14)

where b̃_{j}, c̃_{j} are integers with 0 ≤ b̃_{j} ≤ 3, j = 0, 1, …, 2r − 2, c̃_{1} = 1, and c̃_{j} = 0 for j = 0, 2, 3, …, 2r − 2, where again all indices are viewed modulo 2r − 1.

Construct a directed graph D as follows. The set of vertices of D is the set of all vectors (a′, a′′, a′′′, b′, b′′, c′, c′′) with 0 ≤ a′, a′′, a′′′ ≤ 1, 0 ≤ b′, b′′ ≤ 3, and 0 ≤ c′, c′′ ≤ 1.

Corresponding to any special solution a, 0 < a < 2^{d} − 1, to equation (4.5) with k = 3σ + 4, define (in the notation of (4.13)–(4.14)) the 2r − 1 vertices

v_{j} = (ã_{j}, ã_{j+1}, ã_{j+2}, b̃_{j}, b̃_{j+1}, c̃_{j}, c̃_{j+1}),  (4.15)

0 ≤ j ≤ 2r − 2. Our construction of the directed edges will be motivated by the desire to obtain, via equations (4.13) and (4.14), a bijection between the special solutions a and certain closed walks in D of length d = 2r − 1. A solution a will correspond to the walk

v_{0} → v_{1} → v_{2} → ⋯ → v_{2r−2} → v_{0},  (4.16)

and vice versa.

We connect a vertex (a′, a′′, a′′′, b′, b′′, c′, c′′) to a vertex (A′, A′′, A′′′, B′, B′′, C′, C′′) by a directed edge if and only if

a′′ = A′,  (4.17)
a′′′ = A′′,  (4.18)
b′′ = B′,  (4.19)
c′′ = C′,  (4.20)
Y := (a′ + a′′′ + A′′′ + a′′ + B′′ − 2b′) ∈ {0, 1},  (4.21)
(Y + a′ + C′′ − 2c′) ∈ {0, 1}.  (4.22)

To motivate the construction of such directed edges, the reader should think of (a′, a′′, a′′′, b′, b′′, c′, c′′) and (A′, A′′, A′′′, B′, B′′, C′, C′′) as v_{j} = (ã_{j}, ã_{j+1}, ã_{j+2}, b̃_{j}, b̃_{j+1}, c̃_{j}, c̃_{j+1}) and v_{j+1} = (ã_{j+1}, ã_{j+2}, ã_{j+3}, b̃_{j+1}, b̃_{j+2}, c̃_{j+1}, c̃_{j+2}), respectively, j = 0, 1, …, 2r − 2, and should observe that (4.21) reflects (4.13), and that (4.22) reflects (4.14).

Define the sets V_{0}, V_{1}, V_{2} as the sets of vertices (a′, a′′, a′′′, b′, b′′, c′, c′′) for which (c′, c′′) equals (0, 0), (0, 1), (1, 0), respectively. With these definitions, we claim that for odd d ≥ 3 the special solutions a, 0 < a < 2^{d} − 1, to equation (4.5) with k = 3σ + 4 are in bijection with the special closed walks of length d which start in V_{1}, in the first step move to V_{2}, and from there on visit only vertices from V_{0}, until they return to the starting vertex from V_{1}. We leave it to the reader to check the claim in detail, as this is a straightforward task (cf. (4.16) and (4.15)).

Finally, let A_{ij} be the adjacency matrix of D restricted to the information about edges from V_{i} to V_{j}, i, j ∈ {0, 1, 2}, that is, A_{ij} is the matrix with rows labelled by the vertices from V_{i} and columns labelled by the vertices from V_{j}, with an entry 1 in some row and column whenever that particular vertex of V_{i} is connected to that particular vertex of V_{j}, all other entries being 0. Then, by basic principles (which are easily verified from scratch), the number of the above defined special closed walks of length d is equal to the trace of A_{12}A_{20}A_{00}^{d−3}A_{01}. Hence, by means of our bijection between special solutions to (4.5) and special closed walks in D, we have

∑_{r≥2} A_{3·2^{r}+4}(2r − 1)z^{r−2} = tr ( ∑_{j=0}^{∞} A_{12}A_{20}A_{00}^{2j}A_{01}z^{j})

= tr (A_{12}A_{20}(I − A_{00}^{2}z)^{−1}A_{01}).  (4.23)

We would be done if we could compute the expression on the right-hand side of (4.23). However, the matrix A_{00} is a 128 × 128 matrix, and with today’s technology it is still not easy to compute the inverse of a 128 × 128 matrix, such as (I − A_{00}^{2}z), which has the indeterminate z sitting inside. We circumvent this difficulty by appealing to Lemma 4.5.

On the right-hand side of (4.23) we have the trace of a matrix, all the entries of which are rational in z. Hence, the right-hand side, and so also the left-hand side, is rational in z. Taking into account that the matrix A_{00} is a 128 × 128 matrix, we see that we may write the left-hand side as p(z)/q(z) where the degree of p(z) is at most 127 and the degree of q(z) is at most 128. Now we are in the position to invoke Lemma 4.5, with n_{0} = k = 4, P = 127, Q = 128, once we are able to verify the recurrence (4.8) for d = 11, 13, …, 267. In view of our characterization of A_{3σ+4}(d) = A_{3·2^{r}+4}(2r − 1) as the trace of A_{12}A_{20}A_{00}^{d−3}A_{01}, this is routinely performed on a computer^{1}.

Thus, the proof of the theorem is complete.

By combining Theorems 4.6 and 3.6, we are now able to precisely determine the 2-ranks of the difference sets corresponding to the Glynn type (II) hyperovals.

Corollary 4.7. Let d be an odd integer, d ≥ 3, and set σ = 2^{(d+1)/2}. Let D_{3σ+4,d} be the (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1) cyclic difference set in 𝔽_{2^{d}}^{∗} corresponding to the Glynn type (II) hyperoval D(x^{3σ+4}), as in Theorem 2.5. Let \overline{D_{3σ+4,d}} be the complement of D_{3σ+4,d} in 𝔽_{2^{d}}^{∗}. Then the 2-rank B_{3σ+4}(d) of \overline{D_{3σ+4,d}} equals dA_{3σ+4}(d), where A_{3σ+4}(3) = 1, A_{3σ+4}(5) = 1, A_{3σ+4}(7) = 5, A_{3σ+4}(9) = 7, and for d ≥ 11, A_{3σ+4}(d) satisfies the recurrence (4.8).

Next we turn to the Glynn type (I) case.

Theorem 4.8. Let d be an odd integer, d ≥ 3. Let B_{σ+γ}(d) be defined as in the first paragraph of this section, and let A_{σ+γ}(d) = B_{σ+γ}(d)/d. Then

A_{σ+γ}(d) = A_{σ+γ}(d − 2) + A_{σ+γ}(d − 4) + A_{σ+γ}(d − 6) + A_{σ+γ}(d − 8) − 1,  (4.24)

for all odd d, d ≥ 13, with initial values as given in Table 1.

Proof: We proceed in the spirit of the proof of Theorem 4.6. Here we regard A_{σ+γ}(d) as the number of special solutions a, 0 < a < 2^{d} − 1, to (4.5) (where k = σ + γ) with the instance of a 1 imposed by (4.9) occurring exactly at the mth place if d = 4m − 1, and exactly at the (3m + 1)th place if d = 4m + 1 (where, again, we count places from the right starting with 0). We will define a bijection between these special solutions and certain closed walks in a directed graph D.

We distinguish between the cases d = 4m − 1 and d = 4m + 1, noting that γ is defined differently in these two cases (see (2.4)).

First let d = 4m − 1, m ≥ 2. In this case we have σ = 2^{2m} and γ = 2^{m}, by (2.4).

We analyse, for a given special solution a to (4.5), the computation of (k − 1)a and ka mod 2^{d} − 1 = 2^{4m−1} − 1. Let the binary representation of a be a_{4m−2} … a_{1}a_{0}. Since k = σ + γ = 2^{2m} + 2^{m}, we may compute ka in the following two ways:

\begin{matrix}2^{2m}a = & a_{2m−2} & … & a_{m} & a_{m−1} & … & a_{0} & a_{4m−2} & … & a_{3m−1} & a_{3m−2} & … & a_{2m−1} \\ 2^{m}a = & a_{3m−2} & … & a_{2m} & a_{2m−1} & … & a_{m} & a_{m−1} & … & a_{0} & a_{4m−2} & … & a_{3m−1} \\ ka = & z_{4m−2} & … & z_{3m} & z_{3m−1} & … & z_{2m} & z_{2m−1} & … & z_{m} & z_{m−1} & … & z_{0} \end{matrix} \} + (4.25)

1Maple and Mathematica codes for generating the matrices A_{00}, A_{01}, A_{12}, A_{20} can be obtained on request from the authors, or by WWW at http://radon.mat.univie.ac.at/People/kratt/artikel/glynn.html. The verification of (4.8)

for d = 11, 13, …, 267 took 8 minutes on a Pentium with 133 MHz.

and

\begin{matrix}(k − 1)a = & y_{4m−2} & … & y_{3m} & y_{3m−1} & … & y_{2m} & y_{2m−1} & … & y_{m} & y_{m−1} & … & y_{0} \\ a = & a_{4m−2} & … & a_{3m} & a_{3m−1} & … & a_{2m} & a_{2m−1} & … & a_{m} & a_{m−1} & … & a_{0} \\ ka = & z_{4m−2} & … & z_{3m} & z_{3m−1} & … & z_{2m} & z_{2m−1} & … & z_{m} & z_{m−1} & … & z_{0} \end{matrix} \} + (4.26)

where

a_{i} + a_{m+i} + b_{2m+i−1} = z_{2m+i} + 2b_{2m+i}, for i = 0, 1, …, 4m − 2,  (4.27)
y_{2m+i} + a_{2m+i} + c_{2m+i−1} = z_{2m+i} + 2c_{2m+i}, for i = 0, 1, …, 4m − 2,  (4.28)

for some integers b_{i}, c_{i} with 0 ≤ b_{i} ≤ 1, i = 0, 1, …, 4m − 2, c_{m} = 1, and c_{i} = 0 for i = 0, 1, …, m − 1, m + 1, …, 4m − 2, with the convention that indices are read modulo 4m − 1 throughout. The integer b_{i} is the carry-over from the ith place to the (i + 1)th during the addition displayed in (4.25) that gives ka, while c_{i} is the carry-over from the ith place to the (i + 1)th during the addition displayed in (4.26) that gives ka. (Again, it is not difficult to see that there is a unique such choice of b_{i}’s and c_{i}’s which satisfy (4.27) and (4.28) such that the y_{i}’s and z_{i}’s are the digits in the additions given by (4.25) and (4.26).) Equation (4.28), together with the above assignments for the c_{i}’s, reflects the conditions imposed by (4.9) with the 1’s in the mth place.

Next, as in the proof of Theorem 4.6, we perform an appropriate relabelling of indices. Given a sequence (x_{i})_{i=0,...,4m−2}, where (x_{i}) can be any of (a_{i}), (b_{i}), (c_{i}), (y_{i}), or (z_{i}), define the new sequence (x̃_{j})_{j=0,...,4m−2} by x̃_{j} := x_{mj}. Note that since (m, d) = (m, 4m − 1) = 1, the sequence (x̃_{j})_{j=0,...,4m−2} is a permutation of (x_{i})_{i=0,...,4m−2} (recall that indices are read modulo 4m − 1). Now, by putting i = mj, equations (4.27) and (4.28) read, in terms of the transformed sequences,

ã_{j} + ã_{j+1} + b̃_{j−2} = z̃_{j+2} + 2b̃_{j+2}, for j = 0, 1, …, 4m − 2,  (4.29)
ỹ_{j+2} + ã_{j+2} + c̃_{j−2} = z̃_{j+2} + 2c̃_{j+2}, for j = 0, 1, …, 4m − 2,  (4.30)

where 0 ≤ b̃_{j} ≤ 1, j = 0, 1, …, 4m − 2, c̃_{1} = 1, and c̃_{j} = 0 for j = 0, 2, 3, …, 4m − 2, where again all indices are viewed modulo 4m − 1.

We now interrupt the proof for the case d = 4m − 1 and turn for a moment to the case d = 4m + 1, m ≥ 1. Then we have σ = 2^{2m+1} and γ = 2^{3m+1}, by (2.4).

Again, we analyse, for a given special solution a to (4.5), the computation of (k − 1)a and ka mod 2^{d} − 1 = 2^{4m+1} − 1. Let the binary representation of a be a_{4m} … a_{1}a_{0}. Since k = σ + γ = 2^{2m+1} + 2^{3m+1}, we may compute ka in the following two ways:

\begin{matrix}2^{3m+1}a = & a_{m−1} & … & a_{0} & a_{4m} & … & a_{3m+1} & a_{3m} & … & a_{2m+1} & a_{2m} & … & a_{m} \\ 2^{2m+1}a = & a_{2m−1} & … & a_{m} & a_{m−1} & … & a_{0} & a_{4m} & … & a_{3m+1} & a_{3m} & … & a_{2m} \\ ka = & z_{4m} & … & z_{3m+1} & z_{3m} & … & z_{2m+1} & z_{2m} & … & z_{m+1} & z_{m} & … & z_{0} \end{matrix} \} + (4.31)

and

\begin{matrix}(k − 1)a = & y_{4m} & … & y_{3m+1} & y_{3m} & … & y_{2m+1} & y_{2m} & … & y_{m+1} & y_{m} & … & y_{0} \\ a = & a_{4m} & … & a_{3m+1} & a_{3m} & … & a_{2m+1} & a_{2m} & … & a_{m+1} & a_{m} & … & a_{0} \\ ka = & z_{4m} & … & z_{3m+1} & z_{3m} & … & z_{2m+1} & z_{2m} & … & z_{m+1} & z_{m} & … & z_{0} \end{matrix} \} + (4.32)

where

a_{i} + a_{i−m} + b_{2m+i} = z_{2m+i+1} + 2b_{2m+i+1}, for i = 0, 1, …, 4m,  (4.33)
y_{2m+i+1} + a_{2m+i+1} + c_{2m+i} = z_{2m+i+1} + 2c_{2m+i+1}, for i = 0, 1, …, 4m,  (4.34)

for some integers b_{i}, c_{i} with 0 ≤ b_{i} ≤ 1, i = 0, 1, …, 4m, c_{3m+1} = 1, and c_{i} = 0 for i = 0, 1, …, 3m, 3m+2, …, 4m, with the convention that indices are read modulo 4m+1 throughout. The integer b_{i} is the carry-over from the ith place to the (i + 1)th during the addition displayed in (4.31) that gives ka, while c_{i} is the carry-over from the ith place to the (i + 1)th during the addition displayed in (4.32) that gives ka. (As in the similar places before, there is a unique such choice of b_{i}’s and c_{i}’s which satisfy (4.33) and (4.34) such that the y_{i}’s and z_{i}’s are the digits in the additions given by (4.31) and (4.32).) Equation (4.34), together with the above assignments for the c_{i}’s, reflects the conditions imposed by (4.9) with the 1’s in the (3m + 1)th place.

Next, we perform an appropriate relabelling of indices. Here, given a sequence (x_{i})_{i=0,...,4m}, where (x_{i}) can be any of (a_{i}), (b_{i}), (c_{i}), (y_{i}), or (z_{i}), define the new sequence (x̃_{j})_{j=0,...,4m} by x̃_{j} := x_{−mj}. (Note the difference from the previous relabelling.) Note that since (−m, d) = (m, 4m + 1) = 1, the sequence (x̃_{j})_{j=0,...,4m} is a permutation of (x_{i})_{i=0,...,4m}. Now, by putting i = −mj, equations (4.33) and (4.34) read, in terms of the transformed sequences,

ã_{j} + ã_{j+1} + b̃_{j−2} = z̃_{j+2} + 2b̃_{j+2}, for j = 0, 1, …, 4m,  (4.35)
ỹ_{j+2} + ã_{j+2} + c̃_{j−2} = z̃_{j+2} + 2c̃_{j+2}, for j = 0, 1, …, 4m,  (4.36)

where 0 ≤ b̃_{j} ≤ 1, j = 0, 1, …, 4m, c̃_{1} = 1, and c̃_{j} = 0 for j = 0, 2, 3, …, 4m, where again all indices are viewed modulo 4m + 1.

Very conveniently, equations (4.35)-(4.36) are identical with equations (4.29)-(4.30), so that from now on we can treat the cases d = 4m − 1 and d = 4m + 1 simultaneously.

Construct a directed graph D as follows. The set of vertices of D is the set of all vectors (a′, a′′, b′, b′′, b′′′, b′′′′, c′, c′′, c′′′, c′′′′) with 0 ≤ a′, a′′, b′, b′′, b′′′, b′′′′, c′, c′′, c′′′, c′′′′ ≤ 1.

Corresponding to a special solution a, 0 < a < 2^{d} − 1, to (4.5) with k = σ + γ, define (in the notation of (4.29)–(4.30)/(4.35)–(4.36)) the d vertices

v_{j} = (ã_{j}, ã_{j+1}, b̃_{j−2}, b̃_{j−1}, b̃_{j}, b̃_{j+1}, c̃_{j−2}, c̃_{j−1}, c̃_{j}, c̃_{j+1}),  (4.37)

0 ≤ j ≤ d − 1. Our construction of the directed edges will be motivated by the desire to obtain, via equations (4.29) and (4.30), a bijection between the special solutions a and certain closed walks in D of length d. A solution a will correspond to the walk

v_{0} → v_{1} → ⋯ → v_{d−1} → v_{0},  (4.38)

and vice versa.

We connect a vertex (a′, a′′, b′, b′′, b′′′, b′′′′, c′, c′′, c′′′, c′′′′) to a vertex (A′, A′′, B′, B′′, B′′′, B′′′′, C′, C′′, C′′′, C′′′′) by a directed edge if and only if

a′′ = A′,  (4.39)
b′′ = B′,  (4.40)
b′′′ = B′′,  (4.41)
b′′′′ = B′′′,  (4.42)
c′′ = C′,  (4.43)
c′′′ = C′′,  (4.44)
c′′′′ = C′′′,  (4.45)
Z := (a′ + a′′ + b′ − 2B′′′′) ∈ {0, 1},  (4.46)
(Z + 2C′′′′ − A′′ − c′) ∈ {0, 1}.  (4.47)

The reader should think of (a′, a′′, b′, b′′, b′′′, b′′′′, c′, c′′, c′′′, c′′′′) and (A′, A′′, B′, B′′, B′′′, B′′′′, C′, C′′, C′′′, C′′′′) as v_{j} = (ã_{j}, ã_{j+1}, b̃_{j−2}, b̃_{j−1}, b̃_{j}, b̃_{j+1}, c̃_{j−2}, c̃_{j−1}, c̃_{j}, c̃_{j+1}) and v_{j+1} = (ã_{j+1}, ã_{j+2}, b̃_{j−1}, b̃_{j}, b̃_{j+1}, b̃_{j+2}, c̃_{j−1}, c̃_{j}, c̃_{j+1}, c̃_{j+2}), respectively, j = 0, 1, …, d−1. Equation (4.46) reflects (4.29)/(4.35), and equation (4.47) reflects (4.30)/(4.36).

The remainder of the proof proceeds just like the proof of Theorem 4.6. We define sets V_{0}, V_{1}, V_{2}, V_{3}, V_{4} as the sets of vertices (a′, a′′, b′, b′′, b′′′, b′′′′, c′, c′′, c′′′, c′′′′) for which (c′, c′′, c′′′, c′′′′) equals (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 0), respectively. As is easy to see, for odd d ≥ 3 the special solutions a, 0 < a < 2^{d} − 1, to equation (4.5) with k = σ + γ are in bijection with the closed walks of length d which start in V_{1}, in the first step move to V_{2}, in the next step move to V_{3}, then move to V_{4}, and from there on visit only vertices from V_{0}, until they return to the starting vertex from V_{1}. In an analogous manner we define matrices A_{12}, A_{23}, A_{34}, A_{40}, A_{00} and A_{01}, and obtain a rational expression for the generating function for the sequence (A_{σ+γ}(2r + 1))_{r≥2} in the form

∑_{r≥2} A_{σ+γ}(2r + 1)z^{r−2} = tr ( ∑_{j=0}^{∞} A_{12}A_{23}A_{34}A_{40}A_{00}^{2j}A_{01}z^{j})

= tr (A_{12}A_{23}A_{34}A_{40}(I − A_{00}^{2}z)^{−1}A_{01}).

This time the matrix A_{00}, the adjacency matrix of D restricted to V_{0}, is a 64 × 64 matrix. Therefore, in order to invoke Lemma 4.5, it suffices to verify the recurrence (4.24) for d = 13, 15, …, 141. This is again routinely performed on a computer^{2}. This establishes (4.24) for all odd d, d ≥ 13.

Now the proof of the theorem is complete.

2Maple and Mathematica codes for generating the matrices A_{00}, A_{01}, A_{12}, A_{23}, A_{34}, A_{40} can be obtained on request from the authors, or by WWW at http://radon.mat.univie.ac.at/People/kratt/artikel/glynn.html. The verification of (4.24) for d = 13, 15, …, 141 took 15 seconds on a Pentium with 133 MHz.

By combining Theorems 4.8 and 3.6, we are now able to precisely determine the 2-ranks of the difference sets corresponding to the Glynn type (I) hyperovals.

Corollary 4.9. Let d be an odd integer, d ≥ 3, and set σ = 2^{(d+1)/2}, γ = 2^{(3d+1)/4} if d ≡ 1 mod 4, and γ = 2^{(d+1)/4} if d ≡ 3 mod 4. Let D_{σ+γ,d} be the (2^{d} −1, 2^{d−1} −1, 2^{d−2} −1) cyclic difference set in 𝔽_{2^{d}}^{∗} corresponding to the Glynn type (I) hyperoval D(x^{σ+γ}), as in Theorem 2.5. Let \overline{D_{σ+γ,d}} be the complement of D_{σ+γ,d} in 𝔽_{2^{d}}^{∗}. Then the 2-rank B_{σ+γ}(d) of \overline{D_{σ+γ,d}} equals dA_{σ+γ}(d), where A_{σ+γ}(3) = 1, A_{σ+γ}(5) = 1, A_{σ+γ}(7) = 3, A_{σ+γ}(9) = 7, A_{σ+γ}(11) = 13, and for d ≥ 13, A_{σ+γ}(d) satisfies the recurrence (4.24).

5. Binary cyclic codes of difference sets arising from Segre hyperovals

The next two propositions give some further applications of Proposition 4.1. Let C_{2}(D_{6,d}) be the binary cyclic code of D_{6,d}, as defined near the beginning of Section 3. Define θ(x) (viewed as a polynomial over 𝔽_{2}) by

θ(x) = ∑_{j=0}^{2^{d}−2} b_{j}x^{j},

where b_{0}, b_{1}, …, b_{2^{d}−2} denotes the characteristic sequence of D_{6,d}. By suitably ordering the elements of D_{6,d}, we may choose a (fixed) generator α of 𝔽_{2^{d}}^{∗} such that b_{j} = 1 if and only if α^{j} ∈ D_{6,d}. The significance of θ(x) is that its greatest common divisor with x^{2^{d}−1} − 1 is the generator polynomial of the binary cyclic code C_{2}(D_{6,d}). The zeros of θ(x) in 𝔽_{2^{d}}^{∗} (i.e., the zeros of the generator polynomial) are called the zeros of C_{2}(D_{6,d}). The remaining elements of 𝔽_{2^{d}}^{∗} are called the nonzeros of C_{2}(D_{6,d}). Observe that for such a nonzero u, we have θ(u) = 1, since D_{6,d} is invariant under the d automorphisms of 𝔽_{2^{d}}.

Proposition 5.1. Let d be an odd integer, d ≥ 3, and let D_{6,d} be the (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1) cyclic difference set in 𝔽_{2^{d}}^{∗} corresponding to the Segre hyperoval D(x^{6}), as in Theorem 2.5 with k = 6. Let C_{2}(D_{6,d}) be the binary cyclic code of D_{6,d}. Then the nonzeros of C_{2}(D_{6,d}) are 1, α^{−5a}, where α is the primitive element of 𝔽_{2^{d}}^{∗} defined above, and a runs through all the solutions of (4.1) given explicitly in Proposition 4.1.

Proof: Clearly 1 is a nonzero of C_{2}(D_{6,d}) because the cardinality of D_{6,d} is odd. For 𝔭 a prime ideal in ℤ[ξ_{2^{d}−1}] lying over 2, let ω = ω_{𝔭} be the Teichmüller character on 𝔽_{2^{d}}. By definition of θ(x) and α, we see that α^{i}, 0 < i ≤ 2^{d} − 2 is a nonzero of C_{2}(D_{6,d}) if and only if ω^{i} (D_{6,d}) (mod 𝔭) ≠ 0. From the proof of Theorem 3.6, we see that for 0 < a ≤ 2^{d} − 2, ω^{−5a} (D_{6,d}) (mod 𝔭) ≠ 0 if and only if s(a) + s(5a) = s(6a) + 1. Therefore the nonzeros of C_{2}(D_{6,d}) are 1, α^{−5a}, where a runs through the solutions of (4.1). This completes the proof.

Example 5.2. Let D_{6,9} be the (2^{9} − 1, 2^{8} − 1, 2^{7} − 1) cyclic difference set in 𝔽_{2^{9}}^{∗} corresponding to the Segre hyperoval D(x^{6}), as in Theorem 2.5 with k = 6. Let C_{2}(D_{6,9}) be the binary cyclic code of D_{6,9}. By Proposition 5.1 and Example 4.2, we know that the nonzeros of C_{2}(D_{6,9}) are 1, α^{−5·2^{i}}, α^{−25·2^{i}}, α^{−77·2^{i}}, α^{−117·2^{i}}, α^{−9·2^{i}}, α^{−19·2^{i}}, α^{−7·2^{i}}, α^{−37·2^{i}}, and α^{−2^{i}}, where i = 0, 1, 2, …, 8. A simple computation shows that α^{501j}, j = 341, 342, 343, …, 408, are zeros of C_{2}(D_{6,9}). By the BCH-bound [20, p. 201], the code C_{2}(D_{6,9}) is a 34-error correcting code of length 511 and dimension 82 over 𝔽_{2}, (with minimum distance at least 69).

Let d be an odd integer, d ≥ 3. Let a be an integer with 1 ≤ a ≤ 2^{d} − 2, and let r be the smallest positive integer such that 2^{r+1}a ≡ a (mod 2^{d} − 1). The cyclotomic coset containing a consists of {a, 2a, 2^{2}a, …, 2^{r}a}. The solutions of (4.1) can be partitioned into A_{6}(d) disjoint cyclotomic cosets, each of cardinality d. Let J be a complete set of cyclotomic coset representatives of the solutions of (4.1). We can give a criterion involving trace to decide when the equation x^{6} + x + β = 0, β ∈ 𝔽_{2^{d}}^{∗}, has two distinct solutions (as opposed to no solutions) in 𝔽_{2^{d}}.

Proposition 5.3. Let d be an odd integer, d ≥ 3. Then x^{6} + x + β = 0, β ∈ 𝔽_{2^{d}}^{∗}, has two distinct solutions in 𝔽_{2^{d}} if and only if Tr(∑_{a∈J} β^{5a}) = 0, where Tr is the trace from 𝔽_{2^{d}} to 𝔽_{2}, and J is defined above.

Proof: By Fourier inversion and the definition of θ(x),

(2^{d} − 1)b_{j} = ∑_{i=0}^{2^{d}−2} θ(α^{−i})α^{ij},

for each j with 0 ≤ j ≤ 2^{d} − 2. By Proposition 5.1, θ(α^{−i}) equals 1 if i = 0 or i = 5a, and otherwise θ(α^{−i}) equals 0, where a runs through the solutions of (4.1). The result now follows with β = α^{j}.

Example 5.4. Let d = 9. By Example 4.2, J = {1, 5, 21, 85, 13, 53, 77, 167, 103} is a complete set of cyclotomic coset representatives of the solutions of (4.1). Therefore x^{6} + x + β = 0, β ∈ 𝔽_{2^{9}}^{∗}, has two distinct solutions in 𝔽_{2^{9}} if and only if Tr(β + β^{5} + β^{7} + β^{9} + β^{19} + β^{25} + β^{37} + β^{77} + β^{117}) = 0.

It is interesting to compare Proposition 5.3 with the result (following from Hilbert’s Theorem 90) that x^{2} +x+β = 0, β ∈ 𝔽_{2^{d}}^{∗} has two solutions in 𝔽_{2^{d}} if and only if Tr(β) = 0.

6. Inequivalence of difference sets arising from hyperovals, quadratic residue difference sets, and GMW difference sets

In the next theorem, we answer a question raised by Maschietti [21] by showing that the difference sets D_{k,d} arising from the hyperovals in (2.1), (2.3), (2.4), (2.5) are all inequivalent to each other. The difference sets arising from the hyperovals in (2.1)–(2.2) are of course equivalent for the same d, since as we showed at the end of Section 2, they are all Singer difference sets.

We precede the statement of the theorem by the following auxiliary result which is of independent interest. It relates the magnitudes of the 2-ranks of the difference sets arising from Segre and Glynn hyperovals.

Lemma 6.1. With A_{k}(d) as defined at the beginning of Section 4, we have for each odd d ≥ 15 that

A_{3σ+4}(d) > A_{σ+γ}(d) > A_{6}(d),  (6.1)

i.e., the 2-ranks of the difference sets that arise from Glynn type (II) hyperovals dominate the 2-ranks of the difference sets that arise from Glynn type (I) hyperovals, which in turn dominate the 2-ranks of the difference sets arising from Segre hyperovals.

Proof: Since A_{6}(d) = 2F_{(d−1)/2} − 1 by Theorem 4.3, it follows that

A_{6}(d) = \frac{2}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{(d+1)/2} − \frac{2}{\sqrt{5}} (\frac{1−\sqrt{5}}{2})^{(d+1)/2} − 1.

Note that (1 + \sqrt{5})/2 = 1.6181 … Solving the recurrence (4.24), we obtain

A_{σ+γ}(d) = a_{1}ω_{1}^{(d+1)/2} + a_{2}ω_{2}^{(d+1)/2} + a_{3}ω_{3}^{(d+1)/2} + a_{4}ω_{4}^{(d+1)/2} + a_{5},

where ω_{1}, ω_{2}, ω_{3}, ω_{4} are four distinct complex zeros of the polynomial z^{4} − z^{3} − z^{2} − z − 1, and where a_{1}, a_{2}, a_{3}, a_{4}, a_{5} are explicitly known complex numbers. The zero with greatest absolute value is ω_{1}, say, where |ω_{1}| = 1.927561975 …

Solving the recurrence (4.8), we obtain

A_{3σ+4}(d) = b_{1}ρ_{1}^{(d+1)/2} + b_{2}ρ_{2}^{(d+1)/2} + b_{3}ρ_{3}^{(d+1)/2} + b_{4}ρ_{4}^{(d+1)/2} + b_{5},

where ρ_{1}, ρ_{2}, ρ_{3}, ρ_{4} are four distinct complex zeros of the polynomial z^{4} − z^{3} − 3z^{2} + z + 1, and where b_{1}, b_{2}, b_{3}, b_{4}, b_{5} are explicitly known complex numbers. The zero with greatest absolute value is ρ_{1}, say, where |ρ_{1}| = 2.095293985 …

From these formulas, we see that for odd d > 25,

A_{3σ+4}(d) > \frac{1}{3}2^{(d+1)/2} > A_{σ+γ}(d) > (1.6181)^{(d+1)/2} > A_{6}(d).

Appealing to Table 1, we see that (6.1) holds for odd d ≥ 15.

This completes the proof.

Theorem 6.2. The difference sets D_{k,d} arising from the hyperovals in (2.1), (2.3), (2.4), (2.5) are all inequivalent.

Proof: It suffices to show that the 2-ranks of the complements \overline{D_{k,d}} in question are distinct. Since the difference set D_{k,d} arising from a regular hyperoval is a Singer difference set, the 2-rank of its complement equals d, by Theorem 3.5 and the remarks following Theorem 3.5. By Corollary 4.4, the 2-rank of \overline{D_{6,d}} is dA_{6}(d) = d(2F_{(d−1)/2} − 1), which exceeds d for d ≥ 5. This show the inequivalence for the cases (2.1) and (2.3). By Table 1 and Lemma 6.1, the 2-ranks in all the cases must be distinct.

This completes the proof.

Let Q_{d} denote the quadratic residue cyclic (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1) difference set in 𝔽_{2^{d}}^{∗} [15, p. 244]. Thus, 2^{d} − 1 must be a prime, and Q_{d} = {α^{r} : r is a square mod 2^{d} − 1, 0 < r < 2^{d} − 1}, where α generates the group 𝔽_{2^{d}}^{∗}. It is easily checked that Q_{2} and Q_{3} are equivalent to difference sets arising from the regular hyperoval, while Q_{5} is equivalent to the difference set arising from the Segre hyperoval. We now show that for (odd) d ≥ 7, the sets Q_{d} are inequivalent to difference sets arising from hyperovals.

Theorem 6.3. Let d ≥ 7 be odd. Then the quadratic residue difference sets Q_{d} are inequivalent to the difference sets D_{k,d} arising from the hyperovals in (2.1)–(2.5).

Proof: As χ runs through the (multiplicative) nontrivial characters on 𝔽_{2^{d}}^{∗}, χ(Q_{d}) = ∑_{β∈Q_{d}} χ(β) assumes exactly two distinct values z and \overline{z}, where z is a complex number and \overline{z} is its complex conjugate. If D is any difference set in 𝔽_{2^{d}}^{∗} equivalent to Q_{d}, then as χ runs through the nontrivial characters on 𝔽_{2^{d}}^{∗}, χ(D) assumes only the values z and \overline{z} up to a factor of a (2^{d} − 1)-th root of unity. Now assume for the purpose of contradiction that the aforementioned D is one of the difference sets D_{k,d} in (2.1)–(2.5). In view of (2.6), it suffices to show that as χ runs through the nontrivial characters on 𝔽_{2^{d}}^{∗}, the principal ideals in ℤ[ξ_{2^{d}−1}] generated by the Jacobi sums J(χ, χ^{k−1}) assume more than two distinct values. Thus, by (3.10), it suffices to show that as a runs through the values 1, 2, …, 2^{d} − 2, the expression c(a) := s(a) + s(a(k − 1)) − s(ak) assumes at least three distinct values. One checks this as follows.

For k as in (2.5), c(1), c(−1), and c(7) are distinct. For k as in (2.4), c(1), c(−1), and c(σ + 1) are distinct. For k as in (2.3), c(1), c(−1), and c(3) are distinct. Finally, for k as in (2.1) or (2.2), c(1), c(−1), and c(k + 1) are distinct. This completes the proof.

Next we consider GMW difference sets [11]. Suppose that d has the factorization d = uv for integers u, v > 1, and write q = 2^{u} (so that 2^{d} = q^{v}). Let r be an integer strictly between 1 and q − 1 which is relatively prime to q − 1 and which is not equal to a power of 2. Define the GMW set

G_{d,v,r} = {y ∈ 𝔽_{2^{d}}^{∗} | Tr_{q/2}((Tr_{q^{v}/q}(y))^{r}) = 0},

where Tr_{q^{v}/q} denotes the trace map from 𝔽_{q^{v}} to 𝔽_{q}. (We did not allow r to be a power of 2, for otherwise G_{d,v,r} would of course be equivalent to a Singer difference set.) Let w denote the number of 1’s in the binary expansion of r (so that 1 < w < u). It is known [24] that G_{d,v,r} is a (2^{d} − 1, 2^{d−1} − 1, 2^{d−2} − 1) difference set whose complement has 2-rank uv^{w}. (For related work over finite fields of characteristic p, see [1].) Theorem 6.8 below shows that the GMW sets G_{d,v,r} are inequivalent to the difference sets D_{k,d} in (2.1)–(2.5). We will first need four lemmas.

Lemma 6.4. Write d = uv and q = 2^{u} as above. For each nontrivial multiplicative character χ on 𝔽_{2^{d}}^{∗} we have

χ(G_{d,v,r}) = ∑_{y∈G_{d,v,r}} χ(y) = \frac{1}{2}g(χ)g_{1}(χ_{1}^{1/r})/g_{1}(χ_{1}),

where 1/r denotes the inverse of r modulo q − 1, χ_{1} denotes the restriction of χ to 𝔽_{q}^{∗}, and where g and g_{1} denote the Gauss sums over 𝔽_{2^{d}}^{∗} and 𝔽_{q}^{∗}, respectively.

Proof: We have

2χ(G_{d,v,r}) = ∑_{y∈𝔽_{2^{d}}^{∗}} χ(y)(−1)^{Tr_{q/2}((Tr_{q^{v}/q}(y))^{r})}.

Write

T = (q^{v} − 1)/(q − 1),

and let α be a fixed generator of 𝔽_{2^{d}}^{∗}, so that every y ∈ 𝔽_{2^{d}}^{∗} has the form y = α^{iT +j}, with 0 ≤ i < q − 1 , 0 ≤ j < T. Therefore, since α^{T} ∈ 𝔽_{q}^{∗},

2χ(G_{d,v,r}) = ∑_{j=0}^{T −1} χ(α^{j}) ∑_{i=0}^{q−2} χ^{1/r}(α^{irT})(−1)^{Tr_{q/2}(α^{irT} (Tr_{q^{v}/q}(α^{j}))^{r})}.

Thus

2χ(G_{d,v,r}) = A + B,

where

A = ∑_{j=0}^{T −1} χ(α^{j})\overline{χ}(Tr_{q^{v}/q}(α^{j}))g_{1}(χ_{1}^{1/r})

and

B = ∑_{Tr_{q^{v}/q}(α^{j})=0^{j=0}}^{T −1} ∑_{i=0}^{q−2} χ(α^{iT +j}) = ∑_{Tr_{q^{v}/q}(y)=0^{y∈𝔽{∗ \atop 2^{d}}}} χ(y).

To evaluate A, observe that

A = g_{1}(χ_{1}^{1/r}) ∑_{Tr_{q^{v}/q}(y)=1^{y∈𝔽{∗ \atop 2^{d}}}} χ(y).

This sum on y is an Eisenstein sum, which is known [4, pp. 391, 400] to equal g(χ)/g_{1}(χ_{1}) or −g(χ)/q, according as χ_{1} is nontrivial or trivial. Thus

A = \begin{cases}g_{1}(χ_{1}^{1/r})g(χ)/g_{1}(χ_{1}), & if χ_{1} is nontrivial, \\ g(χ)/q, & if χ_{1} is trivial. \end{cases}

To evaluate B, observe that B is an Eisenstein sum which is known [4, pp. 389, 391, 400] to equal

B = \begin{cases}0, & if χ_{1} is nontrivial, \\ g(χ)(q − 1)/q, & if χ_{1} is trivial. \end{cases}

Adding our evaluations of A and B, we obtain the desired result.

Lemma 6.5. Let v = 3, u ≥ 7 with u odd, q = 2^{u}, and d = uv. For an integer a not divisible by q^{v} − 1, let s(a) denote the number of 1’s in the binary expansion of the reduction of a modulo q^{v} − 1. As in (2.4), define σ = 2^{(d+1)/2} and γ = 2^{(3d+1)/4} if d ≡ 1 mod 4, whereas γ = 2^{(d+1)/4} if d ≡ 3 mod 4. Then for a = (q − 1)(γ + (−1)^{(d−1)/2}),

s(a) + s(a(σ + γ − 1)) − s(a(σ + γ)) < u.

Proof: First suppose that d ≡ 3 mod 4. Then it may be checked directly that s(a) = u, s(a(σ + γ − 1)) = (d − 1)/2, and s(a(σ + γ)) = (d + 1)/2. The result thus follows in the case d ≡ 3 mod 4. Next suppose that d ≡ 1 mod 4. Then it may be checked directly that s(a) = u, s(a(σ + γ − 1)) = u, and s(a(σ + γ)) = 5(d + 3)/12, and the result again follows.

Lemma 6.6. Let d = uv with v = 3 and odd u ≥ 3. Then every GMW difference set G_{d,3,r} is inequivalent to the difference set D_{σ+γ,d} corresponding to the Glynn type (I) hyperoval.

Proof: The result is easily checked for u = 3 and u = 5, because then the 2-ranks of the two kinds of difference sets differ (see Table 1). So let u ≥ 7. Write q = 2^{u} = 2^{d/3}. Let χ be any nontrivial multiplicative character on 𝔽_{2^{d}}^{∗} whose restriction χ_{1} to 𝔽_{q}^{∗} is trivial. Thus, if ω is a Teichmüller character (of order 2^{d} −1) on 𝔽_{2^{d}}^{∗} , then χ = ω^{−a} for an integer a divisible by q − 1.

Suppose that G_{d,3,r} were equivalent to D_{σ+γ,d}. Then it would follow from Lemma 6.4 and (2.6) that

J(χ, χ^{σ+γ−1}) = μg(χ^{t})

for some complex root of unity μ and some integer t relatively prime to 2^{d} − 1. Setting p = 2 and d = 3 in the proof of Theorem 2.1, we see from that proof that g(χ^{t}) is divisible by q in the ring of algebraic integers. Thus J(χ, χ^{σ+γ−1}) is divisible by q, so that every prime ideal occurring in the factorization of J(χ, χ^{σ+γ−1}) over ℤ[ξ_{2^{d}−1}] has an exponent ≥ u. Thus by (3.10),

s(a) + s(a(σ + γ − 1)) − s(a(σ + γ)) ≥ u

for every integer a divisible by q − 1. This contradicts Lemma 6.5, and so the proof is complete.

Lemma 6.7. Let u ≥ 5 be odd. Then A_{6}(3u) is never a power of 3 and A_{6}(5u) is never a power of 5.

Proof: By Theorem 4.3, for odd d > 1,

A_{6}(d) = 2F_{(d−1)/2} − 1.  (6.2)

First suppose that A_{6}(d) is a power of 3 for d = 3u. Then, since A_{6}(d) is different from 3, 9, 27 (see Table 1), A_{6}(d) must be divisible by 81. So by (6.2), d = 57 + 432x for some nonnegative integer x. Since F_{n} (mod 109) has period 108, it follows that A_{6}(d) (mod 109) has period 216, and hence A_{6}(57 + 432x) is congruent to 42 modulo 109 for all nonnegative integers x. This is a contradiction, since 42 is not a power of 3 modulo 109.

Next suppose that A_{6}(d) is a power of 5 for d = 5u. Then since A_{6}(d) is different from 5 and 25 (see Table 1), we have 125 | A_{6}(d). So by (6.2), we have d = 585 + 1000y for some nonnegative integer y. Since F_{n} (mod 251) has period 250, it follows that A_{6}(d) (mod 251) has period 500, and so A_{6}(585 + 1000y) is congruent to 235 modulo 251 for all nonnegative y. This is a contradiction, since 235 is not a power of 5 modulo 251.

Theorem 6.8. The GMW difference set G_{d,v,r} is inequivalent to each of the difference sets D_{k,d} arising from the hyperovals in (2.1)–(2.5).

Proof: As was mentioned following the definition of G_{d,v,r}, the complement \overline{G_{d,v,r}} has 2-rank uv^{w}, where d = uv and 1 < w < u < d. For k as in (2.1) or (2.2), the difference set \overline{D_{k,d}} has 2-rank d (cf. the proof of Theorem 6.2). Since u(d/u)^{w} > d, it follows that G_{d,v,r} is inequivalent to D_{k,d}.

Now let d be an odd composite integer > 5. It is easily checked by extending Table 1 that none of A_{6}(d), A_{σ+γ}(d), or A_{3σ+4}(d) can equal (d/u)^{w−1} for any d < 500. Hence assume d > 500. From the proof of Lemma 6.1,

A_{3σ+4}(d) > \frac{1}{4}(2.09)^{(d+1)/2} > 3^{d/3} > (d/u)^{u−2} ≥ (d/u)^{w−1}.

This completes the proof for k as in (2.5).

Next, let k be as in (2.4). By Lemma 6.6, G_{d,3,r} cannot be equivalent to D_{σ+γ,d}. Hence, assume that u ≤ d/5. From the proof of Lemma 6.1,

A_{σ+γ}(d) > \frac{1}{4}(1.92)^{(d+1)/2} > 5^{d/5} > (d/u)^{u−2} ≥ (d/u)^{w−1}.

This completes the proof for k as in (2.4).

Finally, let k be as in (2.3), i.e., k = 6. By Lemma 6.7, we cannot have A_{6}(d) equal to (d/u)^{w−1} with u = d/3 or d/5 or d/9. Moreover, A_{6}(d) cannot equal (d/u)^{w−1} for u = d/7, because it follows from Table 1 and the recurrence (4.4) that A_{6}(d) never equals 7 and is never divisible by 49 for any odd d. Thus assume that u ≤ d/11. From the proof of Lemma 6.1,

A_{6}(d) > (1.6)^{(d+1)/2} > 11^{d/11} > (d/u)^{u−2} ≥ (d/u)^{w−1}.

This completes the proof for k as in (2.3), and hence completes the proof of the theorem.

Remark: In the preceding proof, in order to show the inequivalence of GMW sets G_{d,3,r} and the difference sets D_{σ+γ,d} arising from the Glynn type (I) hyperovals, we used Lemma 6.6 instead of a 2-rank argument. We do in fact also have a proof^{3}, which is similar in spirit to the proof of Lemma 6.7, that for odd u ≥ 3 the number A_{σ+γ}(3u) is never a power of 3, whence also the 2-ranks of G_{d,3,r} and D_{σ+γ,d} are distinct. However, we prefer the approach via Lemma 6.6, because the aforementioned proof requires extensive computer calculations, and because Lemma 6.4 is of independent interest.

7. 2-ranks of circulant matrices

For integers k ≥ 3 and d ≥ 2, let

f(x) = x^{k} + x^{k−1}, x ∈ 𝔽_{2^{d}}^{∗}.

In Theorem 7.5, we will determine the ranks over 𝔽_{2} of certain circulant matrices M_{k}, defined as follows. Let α denote a generator of the cyclic group 𝔽_{2^{d}}^{∗} and define the circulant matrix

M_{k} = (m_{i,j})_{1≤i,j≤2^{d}−1} ,

where m_{i,j} denotes the number of x ∈ 𝔽_{2^{d}}^{∗} for which α^{j−i} = f(x). Note that for each k such that D(x^{k}) is a hyperoval in P G(2, 2^{d}), we have M_{k} = 2A_{k}, where A_{k} is the incidence matrix (defined at the beginning of Section 3) corresponding to the difference set D_{k,d} (defined in Theorem 2.5), the 2-ranks of which we studied in Section 4. This is because the incidence matrix A_{k} is not affected by changing τ(x) (as defined before Lemma 2.4) from x + x^{k} to x^{k−1} + x^{k}, since the difference sets D_{k,d} and D_{k/(k−1),d} are equivalent by Lemma 2.3.

3It can be obtained on request from the authors, or by WWW at http://radon.mat.univie.ac.at/People/kratt/artikel/glynn.html.

Let rank_{2}(M_{k}) denote the rank of M_{k} over 𝔽_{2}. In Section 4 we were concerned with the computation of the 2-ranks of incidence matrices A_{k}. Such a matrix A_{k} can be viewed as an adjacency matrix of the directed graph where for two vertices u, v in 𝔽_{2^{d}}^{∗}, a directed edge connects u to v if and only if v/u is in the difference set D_{k,d}, i.e., if and only if v/u is in the image of τ. The following two theorems exhibit values of k for which the computation of the 2-rank of M_{k} is also a 2-rank computation for an adjacency matrix N_{k} of a directed graph, where this time u is connected to v if and only if v/u is in the image of f.

Theorem 7.1. Let d > 1 be odd. Let N_{5} be the matrix obtained from M_{5} by replacing every nonzero entry with 1. Then rank_{2}(N_{5}) = rank_{2}(M_{5}).

Proof: It suffices to show that every nonzero entry of M_{5} is odd. We will prove the stronger result that for each c ∈ 𝔽_{2^{d}}^{∗}, the polynomial g(x) = x^{5} + x^{4} + c has either no zeros, one zero, or three zeros in 𝔽_{2^{d}}^{∗}. First, if g(x) had exactly two zeros in 𝔽_{2^{d}}^{∗}, then g(x) would have an irreducible cubic factor (normal over 𝔽_{2^{d}}), so that g(x) would have five zeros in 𝔽_{2^{3d}} . Similarly, if g(x) had four zeros in 𝔽_{2^{d}}^{∗}, then g(x) would have five zeros in 𝔽_{2^{d}}^{∗}. Thus, since 3d is odd, it remains to show that g(x) cannot have fives zeros in 𝔽_{2^{d}} for any odd d. Assume for the purpose of contradiction that g(x) has fives zeros in 𝔽_{2^{d}}. Let z denote one of these zeros. Since c is nonzero, z is not 0 or 1. Over 𝔽_{2^{d}}, we have the factorization g(x) = (x + z)h(x), where

h(x) = x^{4} + (z + 1)x^{3} + (z^{2} + z)x^{2} + (z^{3} + z^{2})x + (z^{4} + z^{3}).

Note that h(0) is nonzero since g(0) is nonzero. We have

q(x) = (z^{4} + z^{3})^{−1}x^{4}h(z/x) = x^{4} + x^{3} + x^{2} + x + w,

where w = z/(z + 1). Since h(x) has four zeros in 𝔽_{2^{d}}, so does q(x). Write q(x) = (x^{2} + rx + s)(x^{2} + ux + v) over 𝔽_{2^{d}}. Since both of these quadratic factors are reducible over 𝔽_{2^{d}}, we have Tr(s/r^{2}) = Tr(v/u^{2}) = 0. Note that r and u are nonzero, since q(x) cannot have multiple zeros over 𝔽_{2^{d}}. We will obtain a contradiction by showing that Tr(s/r^{2})+Tr(v/u^{2}) = 1. Now, r +u = 1, ru+s+v = 1, and su+vr = 1. Thus r = 1+u, u^{2} + u + v + 1 = s, and u^{3} + u^{2} + uv + u + (v + uv) = 1. Hence v = 1 + u + u^{2} + u^{3} and s = u^{3}. Therefore

s/r^{2} = u^{3}/(1 + u^{2}) = u + 1/(1 + u) + 1/(1 + u)^{2},

so that Tr(s/r^{2}) = Tr(u). On the other hand, v/u^{2} = (1/u) + (1/u)^{2} + 1 + u, so that Tr(v/u^{2}) = 1 + Tr(u). Thus Tr(v/u^{2}) + Tr(s/r^{2}) = 1, which yields the desired contradiction. This completes the proof.

The next theorem shows that the conclusion of Theorem 7.1 is valid for all d > 1 when the subscript 5 is replaced by any k of the form 2^{m} − 1 with m > 1.

Theorem 7.2. Let d > 1. Set k = 2^{m} − 1 for an integer m > 1, and let N_{k} be the matrix obtained from M_{k} by replacing every nonzero entry with 1. Then rank_{2}(N_{k}) = rank_{2}(M_{k}).

Proof: It suffices to show that for each c ∈ 𝔽_{2^{d}}^{∗}, the polynomial g(x) = x^{k} + x^{k−1} + c has either no zeros or an odd number of zeros in 𝔽_{2^{d}}^{∗}. Assume that z is a zero of g(x) in 𝔽_{2^{d}}^{∗}, and note that z is not 0 or 1. We will show that g(x) has an odd number of zeros in 𝔽_{2^{d}}^{∗}. We have the factorization g(x) = (x + z)h(x), where

h(x) = x^{k−1} + (z + 1)x^{k−2} + (z^{2} + z)x^{k−3} + … + (z^{k−2} + z^{k−3})x + (z^{k−1} + z^{k−2}).

It remains to show that h(x) has an even number of zeros. We have

q(x) = (z^{k−1} + z^{k−2})^{−1}x^{k−1}h(z/x) = x^{k−1} + x^{k−2} + … + x + z/(z + 1).

Since k = 2^{m} − 1, it follows that whenever x is a zero of q(x), so is x + 1. Thus q(x) and hence h(x) has an even number of zeros. This completes the proof.

We next give a formula for rank_{2}(M_{k}) in terms of s(x), where s(x) is defined above Theorem 3.4, with q = 2^{d}. Define

s^{∗}(x) = \begin{cases}s(x), & if (2^{d} − 1) |̸ x, \\ d, & if (2^{d} − 1) | x. \end{cases}

Theorem 7.3. For integers k ≥ 3 and d ≥ 2, rank_{2}(M_{k}) equals the number of a, 0 < a < 2^{d} − 1, for which

s(a) + s((k − 1)a) = s^{∗}(ka).  (7.1)

Proof: The 2^{d} − 1 complex eigenvalues of M_{k} are

∑_{x∈𝔽_{2^{d}}^{∗}} χ(f(x)),

where χ ranges over the 2^{d} − 1 multiplicative characters on 𝔽_{2^{d}}^{∗}. Let 𝔭 be a prime ideal in ℤ[ξ_{2^{d}−1}] lying over 2, and let ω = ω_{𝔭} be the Teichmüller character on 𝔽_{2^{d}}^{∗}. Then rank_{2}(M_{k}) equals the number of a, 0 < a < 2^{d} − 1, for which

𝔭 |̸ J(ω^{−a}, ω^{−(k−1)a}) = ∑_{x∈𝔽_{2^{d}}^{∗}} ω^{−a}(f(x))

(cf. Theorem 3.3). For 0 < a < 2^{d} − 1, we have

𝔭^{s(a)+s((k−1)a)−s^{∗}(ka)} || J(ω^{−a}, ω^{−(k−1)a})

(cf. (3.10)), since J(ω^{−a}, ω^{−(k−1)a}) is a unit if ka or (k − 1)a is divisible by 2^{d} − 1. The theorem now follows.

Let R_{k}(d) denote the number of solutions a, 0 < a < 2^{d} − 1, to equation (7.1). Thus by Theorem 7.3, R_{k}(d) = rank_{2}(M_{k}). The reader should observe the similarity of the problems of determining R_{k}(d), the number of solutions a, 0 < a < 2^{d} − 1, to equation (7.1), and of determining B_{k}(d), the number of solutions a, 0 < a < 2^{d} − 1, to equation (3.8). In the case of B_{k}(d) = dA_{k}(d) we obtained linear recurrences for all relevant values of k (see (4.4), (4.24), (4.8)). The next proposition shows that linear recurrences exist for the R_{k}(d) as well. We omit the proof, as the proposition can be proved by an approach similar to the one we used in the proofs of Theorems 4.6 and 4.8.

Proposition 7.4. Let k be a fixed integer ≥ 3. The generating function ∑_{d≥2} R_{k}(d)z^{d} for the numbers R_{k}(d) of solutions a, 0 < a < 2^{d} − 1, to equation (7.1) is a rational function in z, and, hence, the sequence (R_{k}(d))_{d≥e} satisfies a linear recurrence for e large enough.

A proof of this proposition in the style of the proofs of Theorems 4.6 and 4.8 also gives bounds on the degrees of the numerator and denominator polynomials of the rational generating function ∑_{d≥2} R_{k}(d)z^{d}. So, this allows us, at least for k not too large, to determine recurrences via the computer, by first computing enough numbers R_{k}(d) to guess a linear recurrence using gfun [23], and then applying Lemma 4.5.

In the next theorem, we determine R_{k}(d) explicitly for 3 ≤ k ≤ 9 by computing the corresponding rational generating functions.

Theorem 7.5. For 3 ≤ k ≤ 9, the generating functions ∑_{d≥2} R_{k}(d)z^{d} are respectively

∑_{d≥2} R_{3}(d)z^{d} = \frac{z^{2}(2 − z)}{(1 − z)(1 − z − z^{2})},  (7.2)

∑_{d≥2} R_{4}(d)z^{d} = \frac{2z^{2}}{1 − z^{2}} ,  (7.3)

∑_{d≥2} R_{5}(d)z^{d} = \frac{z^{3}(3 + 2z − 3z^{2})}{(1 − z)(1 + z^{2})(1 − z − z^{2})},  (7.4)

∑_{d≥2} R_{6}(d)z^{d} = \frac{z^{2}(2 + 4z^{2})}{1 − z^{2} − z^{4}},  (7.5)

∑_{d≥2} R_{7}(d)z^{d} = \frac{z^{2}(2 + 2z − 6z^{2} − 2z^{3} − 2z^{4} + 5z^{5})}{(1 − z)(1 − z − z^{3})(1 − z^{2} − z^{3})},  (7.6)

∑_{d≥2} R_{8}(d)z^{d} = \frac{6z^{3}}{1 − z^{3}} ,  (7.7)

∑_{d≥2} R_{9}(d)z^{d} = \frac{z^{2}(2 − 4z + 6z^{2} + 2z^{3} + 2z^{4} − 12z^{5} − 2z^{6} + 7z^{7})}{(1 − z)(1 − z − z^{2})(1 + z^{3} − z^{6})}.  (7.8)

Proof: These assertions can, in principle, be proved as we described above the statement of the theorem. However, it is instructive to exhibit the solutions to (7.1) in each case explicitly, from which (7.2)–(7.8) then follow easily by means of generating function calculus.

For the description of the solution sets we use a standard notation from the calculus of words (cf. [18]): Given an alphabet A, the set of all words (including the empty word) consisting of letters from A is denoted by A^{∗}. With that terminology, the solutions to (7.1) in the cases k = 3, …, 9 can be described as follows:

For k = 3, the binary representations of the solutions a to (7.1), 0 < a < 2^{d} − 1, are obtained by forming all possible rotations of the strings of length d from the set {0, 01}^{∗}\{0}^{∗}.

For k = 4, the binary representations of the solutions a to (7.1), 0 < a < 2^{d} − 1, are obtained by forming all possible rotations of the strings of length d from the set {01}^{∗}.

For k = 5, the binary representations of the solutions a to (7.1), 0 < a < 2^{d} − 1, are obtained by forming all possible rotations of the strings of length d from the set {0, 001, 0011}^{∗}\{0}^{∗}.

For k = 6, the binary representations of the solutions a to (7.1), 0 < a < 2^{d} − 1, are obtained by forming all possible rotations of the strings of length d from the set {01, 0011}^{∗}.

For k = 7, the binary representations of the solutions a to (7.1), 0 < a < 2^{d} − 1, are obtained by forming all possible rotations of the strings of length d from the set ({0, 001}^{∗} ∪ {01, 011}^{∗})\{0}^{∗}.

For k = 8, the binary representations of the solutions a to (7.1), 0 < a < 2^{d} − 1, are obtained by forming all possible rotations of the strings of length d from the set {001, 011}^{∗}.

For k = 9, the binary representations of the solutions a to (7.1), 0 < a < 2^{d} − 1, are obtained by forming all possible rotations of the strings of length d from the set ({0, 00011, 000111} ∪ {0001, 000101, 00010101, … })^{∗}\{0}^{∗}.

These assertions can be established in a way similar to the proof of Proposition 4.1, with use of the fact that the solutions a to (7.1), 0 < a < 2^{d} − 1, are characterized by the property that there is no instance of a 1 occurring in the same place in the binary expansions of a and (k − 1)a (mod 2^{d} − 1).

The formulas (7.2)–(7.8) for the generating functions follow, as we now demonstrate for the case k = 5.

From the above, the binary representation of a solution a to (7.1) with k = 5 must be some rotation of a nonzero string of length d obtained by concatenating the blocks 0, 001, and 0011. To identify the block in the cyclic binary representation of a which overlaps with the rightmost place of the binary representation of a, we underline the digit in that block where the overlap occurs. We have the following possibilities for such blocks: \underline{0}, \underline{0}01, 0\underline{0}1, 00\underline{1}, \underline{0}011, 0\underline{0}11, 00\underline{1}1, 001\underline{1}. Once we have chosen one of these possibilities, we have to “glue” this already chosen block with a (possibly empty) sequence of other blocks from {0, 001, 0011} to form a binary string representing a solution to (7.1), where the underlined place is considered as the rightmost place in the string (through appropriate rotation). Hence, in symbolic notation again, the set of all solutions to (7.1) is

(\{\underline{0}, \underline{0}01, 0\underline{0}1, 00\underline{1}, \underline{0}011, 0\underline{0}11, 00\underline{1}1, 001\underline{1}\} × \{0, 001, 0011\}^{∗})\\{0\}^{∗}.

In particular, a string taken from this set is a solution to (7.1) with corresponding d equal to the length of the string. Since the set \{\underline{0}, \underline{0}01, 0\underline{0}1, 00\underline{1}, \underline{0}011, 0\underline{0}11, 00\underline{1}1, 001\underline{1}\} contains one string of length 1, three strings of length 3, and four strings of length 4, its corresponding generating function is z + 3z^{3} + 4z^{4}. Similarly, the set {0, 001, 0011} has generating function z + z^{3} + z^{4}. Therefore, by elementary “generatingfunctionology” (see [30]), the generating function for the solutions a to (7.1), and, hence, the generating function ∑_{d≥2} R_{5}(d)z^{d}, is given by

(z + 3z^{3} + 4z^{4}) · \frac{1}{1 − (z + z^{3} + z^{4})} − \frac{z}{1 − z} .  (7.9)

Simplification of expression (7.9) gives (7.4).

We leave the details in the remaining cases to the reader.

Acknowledgements. The authors are grateful to S. Payne for pointing out the reference [22, Theorem 12.5.3] in the proof of Lemma 2.3, and to Jürgen Bierbrauer for computing a bound for the minimum distance of the code in Example 5.2. The second and fourth authors would like to express their gratitude to the Mathematische Forschungsinstitut Oberwolfach, where they first met and where part of this work initiated. The third author would like to thank the University of California at San Diego for the opportunity to spend a visit in Winter Quarter 1998, which brought together the first and third authors to work on this subject. The research of the fourth author was supported in part by NSA grant MDA 904-97-0104, and a grant from the University of Delaware Research Foundation.

References

[1] M. Antweiler and L. Bömer, Complex sequences over GF (p^{m}) with a two-level autocorrelation function and a large linear span, IEEE Trans. Inform. Theory, 38 (1992), 120–130.

[2] E. F. Assmus, Jr., and J. D. Key, Designs and their codes, Cambridge Tracts in Mathematics, 103, Cambridge University Press, Cambridge, 1992.

[3] B. C. Berndt and R. J. Evans, Sums of Gauss, Jacobi, and Jacobsthal, J. Number Theory, 11 (1979), 349–398.

[4] B. C. Berndt, R. J. Evans and K. S. Williams, Gauss and Jacobi sums, Wiley Interscience, 1998.

[5] W. G. Bridges, M. Hall, and J. L. Hayden, Codes and designs, J. Combin. Theory Ser. A 31 (1981), 155–174.

[6] J. Cannon and C. Playoust, An introduction to MAGMA, University of Sydney, Australia, 1993.

[7] W. E. Cherowitzo and L. Storme, α-flocks with oval herds and monomial hyperovals, preprint.

[8] D. Glynn, Two new sequences of ovals in finite Desarguesian planes of even order, Lecture Notes in Mathematics 1036, Springer-Verlag, 1983, 217–229.

[9] J. M. Goethals and P. Delsarte, On a class of majority logic decodable cyclic codes, IEEE Trans. Inform. Theory, 14 (1968), 182–188.

[10] S. W. Golomb, The use of combinatorial structures in communication signal designs, in: “Applications of Combinatorial Mathematics”, Chris Mitchell (ed.), vol. 60, 1997, 59–78.

[11] B. Gordon, W. H. Mills and L. R. Welch, Some new difference sets, Canad. J. Math. 14 (1962), 614–625.

[12] N. Hamada, On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its applications to error-correcting codes, Hiroshima Math. J. 3 (1973), 154–226.

[13] N. Hamada and H. Ohmori, On the BIB-design having the minimum p-rank, J. Combin. Theory Ser. A 18 (1975), 131–140.

[14] J. W. P. Hirschfeld, Projective Geometries over Finite Fields. Oxford University Press, 1979.

[15] D. Jungnickel, Difference Sets, in: “Contemporary Design Theory, A Collection of Surveys”, J. Dinitz, D. R. Stinson (eds.), Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York, 1992, 241–324.

[16] E. S. Lander, Symmetric Designs, An Algebraic Approach, Cambridge University Press, Cambridge, 1983.

[17] R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Encyclopedia of Mathematics and Its Applications, vol. 20, Cambridge University Press, Cambridge, 1997.

[18] M. Lothaire, Combinatorics on words, 2nd ed., Encyclopedia of Mathematics and Its Applications, vol. 17, Cambridge University Press, Cambridge, 1997.

[19] J. MacWilliams and H. B. Mann, On the p-rank of the design matrix of a difference set, Inform. Control 12 (1968), 474–488.

[20] F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes, North-Holland, 1977.

[21] A. Maschietti, Difference sets and hyperovals, Designs, Codes and Crypt. 14 (1998), 89–98.

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

[23] B. Salvy and P. Zimmermann, Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (1994).

[24] R. A. Scholtz and L. R. Welch, GMW sequences, IEEE Trans. Inform. Theory 30 (1984), 548–553.

[25] B. Segre, Ovals in a finite projective plane, Canad. J. Math. 7 (1955), 414–416.

[26] K. J. C. Smith, On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry, J. Combin. Theory 7 (1969), 122–129.

[27] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986; reprinted by Cambridge University Press, Cambridge, 1997.

[28] R. J. Turyn, Character sums and difference sets, Pacific J. Math. 15 (1965), 319–346.

[29] L. C. Washington, Introduction to Cyclotomic Fields, 2nd edition, Springer, 1997.

[30] H. S. Wilf, generatingfunctionology, 2nd ed., Academic Press, San Diego, 1994.

[31] Q. Xiang, On balanced binary sequences with two-level autocorrelation functions, IEEE Trans. Inform. Theory, to appear.

[32] K. Yamamoto, On Jacobi sums and difference sets, J. Combin. Theory Ser. A 3 (1967), 146–181.

[33] K. Yamamoto, On congruences arising from relative Gauss sums, in: “Number Theory and Combinatorics”, Japan 1984, World Scientific Publ., 1985, 423–446.

Department of Mathematics, University of California, San Diego, La Jolla, California 92093-0112, USA,

  E-mail address: revans@euclid.ucsd.edu

Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands,

  E-mail address: hollmann@natlab.research.philips.com

Institut für Mathematik, Universität Wien, Strudlhofgasse 4, A-1090 Vienna, Austria,

  E-mail address: kratt@pap.univie.ac.at
  WWW: http://radon.mat.univie.ac.at/People/kratt

Department of Mathematical Sciences, University of Delaware, Newark, DE 19716, USA,

  E-mail address: xiang@math.udel.edu