<ph f="cmex">Pseudocyclic association schemes arising from the actions of </ph> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo>P</mo> <mo>G</mo> <mo>L</mo> <mo>(</mo> <mn>2</mn> <mo>,</mo> <msup> <mrow> <mn>2</mn> </mrow> <mrow> <mi>m</mi> </mrow> </msup> <mo>)</mo> </math> <ph f="cmr">and </ph> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo>P</mo> <mo>Γ</mo> <mo>L</mo> <mo>(</mo> <mn>2</mn> <mo>,</mo> <msup> <mrow> <mn>2</mn> </mrow> <mrow> <mi>m</mi> </mrow> </msup> <mo>)</mo> </math>

Henk D. L. Hollmann Philips Research Laboratories Prof. Holstlaan 4, 5656 AA Eindhoven The Netherlands email: henk.d.l.hollmann@philips.com Qing Xiang Department of Mathematical Sciences University of Delaware Newark, DE 19716, USA email: xiang@math.udel.edu

In Memory of Jack van Lint

Abstract
The action of P G L ( 2 , 2 m )   on the set of exterior lines to a nonsingular conic in P G ( 2 , 2 m )   affords an association scheme, which was shown to be pseudocyclic in [6] . It was further conjectured in [6] that the orbital scheme of P Γ L ( 2 , 2 m )   on the set of exterior lines to a nonsingular conic in P G ( 2 , 2 m )   is also pseudocyclic if m   is an odd prime. We confirm this conjecture in this paper. As a by-product, we obtain a class of Latin square type strongly regular graphs on nonprime-power number of points.

1 Introduction

Let X   be a finite set. A (symmetric) association scheme with d   classes on X   is a partition of X × X   into sets R 0   , R 1 , … , R d   (called associate classes or relations) such that
  • 1. R 0 = { ( x , x ) | x ∈ X }   (the diagonal relation),
  • 2. R i   is symmetric for i = 1 , 2 , … , d   ,
  • 3. for all i , j , k   in { 0 , 1 , 2 , … , d }   there is an integer p i j k   such that, for all ( x , y ) ∈ R k   , | { z ∈ X | ( x , z ) ∈ R i a n d ( z , y ) ∈ R j } | = p i j k .  
We denote such an association scheme by ( X , { R i } 0 ≤ i ≤ d )   . Elements x   and y   of X   are called i   -th associates if ( x , y ) ∈ R i   . The numbers p i j k   , 0 ≤ k , i , j ≤ d   , are called the intersection parameters of the scheme. That p i i 0   exists means that there is a constant number of i   -th associates of any element of X   , which is usually denoted by n i   . The numbers n 0 , n 1 , … , n d   are called the valencies (or degrees) of the scheme. We have
  • 1. n 0 = 1   , n 0 + n 1 + ⋯ + n d = | X | ,  
  • 2. p 0 j k = δ j , k   (Kronecker delta), p i j 0 = δ i , j n j   ,
  • 3. p i j k = p j i k   , p i j k n k = p i k j n j   .
For i ∈ { 0 , 1 , … , d }   , let A i   be the adjacency matrix of the relation R i   , that is, the rows and columns of A i   are both indexed by X   and ( A i ) x y : = { 1 if ( x , y ) ∈ R i , 0 if ( x , y ) / ∈ R i .   The matrices A i   are symmetric ( 0 , 1 )   -matrices and A 0 = I , A 0 + A 1 + ⋯ + A d = J ,   where J   is the all one matrix of size | X |   by | X |   . By the definition of an association scheme, we have A i A j = ∑ k = 0 d p i j k A k   for any i , j ∈ { 0 , 1 , … , d }   . So A 0 , A 1 , ⋯ , A d   form a basis of the commutative algebra generated by A 0 , A 1 , ⋯ , A d   over the reals (which is called the Bose-Mesner algebra of the association scheme). Moreover this algebra has a unique basis E 0 , E 1 , ⋯ , E d   of primitive idempotents; one of the primitive idempotents is 1 | X | J   . So we may assume that E 0 = 1 | X | J   .
Let m i = r a n k E i   . Then m 0 = 1 , m 0 + m 1 + ⋯ + m d = | X | .   The numbers m 0 , m 1 , … , m d   are called the multiplicities of the scheme. Since we have two bases of the Bose-Mesner algebra, we may consider the transition matrices between them. Define P = ( p j ( i ) ) 0 ≤ i , j ≤ d   (the first eigenmatrix) and Q = ( q j ( i ) ) 0 ≤ i , j ≤ d   (the second eigenmatrix) as the ( d + 1 ) × ( d + 1 )   matrices with rows and columns indexed by 0 , 1 , 2 , … , d   such that ( A 0 , A 1 , … , A d ) = ( E 0 , E 1 , … , E d ) P ,   and | X | ( E 0 , E 1 , … , E d ) = ( A 0 , A 1 , … , A d ) Q .   Of course, we have P = | X | Q − 1 , Q = | X | P − 1 .   Note that { p j ( i ) | 0 ≤ i ≤ d }   is the set of eigenvalues of A j   and the zeroth row and column of P   and Q   are as indicated below.
P = ( 1 n 1 ⋅ ⋅ ⋅ n d 1 . . . 1 ) , Q = ( 1 m 1 ⋅ ⋅ ⋅ m d 1 . . . 1 )   Before we proceed further, we give some examples of association schemes.
Example 1.1 Let X   be a finite set and let G   be a group acting transitively on X   . We say that G   acts generously transitively on X   if the orbits of the induced action of G   on X × X   are all symmetric. (The orbits of G   on X × X   are usually called the orbitals of the action of G   on X   .) It is clear that if G   acts generously transitively on X   , then the orbitals of G   on X   can be taken as the relations of an association scheme, which will be called the orbital scheme of G   on X   . The next example arises in this way.
Example 1.2 We consider cyclotomic schemes defined as follows. Let q   be a prime power and let q − 1 = e f   with e > 1   . Let C 0   be the subgroup of the multiplicative group of F q   of index e   , and let C 0 , C 1 , … , C e − 1   be the cosets of C 0   . We require − 1 ∈ C 0   . Define R 0 = { ( x , x ) : x ∈ F q }   , and for i ∈ { 1 , 2 , … , e }   , define R i = { ( x , y ) | x , y ∈ F q , x − y ∈ C i − 1 }   . Then ( F q , { R i } 0 ≤ i ≤ e )   is an e   -class symmetric association scheme (the R i   are the orbitals of the action of G   on F q   , where G = { x ↦ a x + b | a ∈ C 0 , b ∈ F q }   ). The intersection parameters of the cyclotomic scheme are related to the cyclotomic numbers ([12,p. 25] ).
Namely, for i , j , k ∈ { 1 , 2 , … , e }   , given ( x , y ) ∈ R k   ,
p i j k = | { z ∈ F q | x − z ∈ C i − 1 , y − z ∈ C j − 1 } | = | { z ∈ C i − k | 1 + z ∈ C j − k } | . (1)
The first eigenmatrix P   of this scheme is the following ( e + 1 )   by ( e + 1 )   matrix (with the rows of P   arranged in a certain way) P = ( 1 f ⋅ ⋅ ⋅ f 1 . . . P 0 1 )   with P 0 = ∑ i = 1 e η i C i   , where C   is the e   by e   matrix:
C = ( 1 1 . . . 1 1 )   and η i = ∑ β ∈ C i ψ ( β )   , 1 ≤ i ≤ e   , for a fixed nontrivial additive character ψ   of F q   . See [1] for more details.
Next we introduce the notion of a pseudocyclic association scheme.
Definition 1.3 Let ( X , { R i } 0 ≤ i ≤ d )   be an association scheme. We say that ( X , { R i } 0 ≤ i ≤ d )   is pseudocyclic if there exists an integer t   such that m i = t   for all i ∈ { 1 , ⋯ , d }   .
The following theorem gives combinatorial characterizations for an association scheme to be pseudocyclic.
Theorem 1.4 Let ( X , { R i } 0 ≤ i ≤ d )   be an association scheme, and for x ∈ X   and 1 ≤ i ≤ d   , let R i ( x ) = { y | ( x , y ) ∈ R i }   . Then the following are equivalent.
(1). ( X , { R i } 0 ≤ i ≤ d )   is pseudocyclic.
(2). For some constant t   , we have n j = t   and ∑ k = 1 d p k j k = t − 1   , for 1 ≤ j ≤ d   .
(3). ( X , ℬ )   is a 2 − ( v , t , t − 1 )   design, where ℬ = { R i ( x ) | x ∈ X , 1 ≤ i ≤ d }   .
For a proof of this theorem, we refer the reader to [2,p. 48] and [6,p. 84] . Part (2) in the above theorem is very useful. For example, we may use it to prove that the cyclotomic scheme in Example  1.2 is pseudocyclic. The proof goes as follows. First, the nontrivial valencies of the cyclotomic scheme in Example  1.2 are all equal to f   . Second, by ( 1 ) and noting that − 1 ∈ C 0   , we have
∑ k = 1 e p k j k = ∑ k = 1 e | { z ∈ C 0 | 1 + z ∈ C j − k } |
= | C 0 | − 1 = f − 1
Pseudocyclic schemes can be used to construct strongly regular graphs and distance regular graphs of diameter 3 ([3] , [2,p. 388] ). In view of this, it is of interest to construct pseudocyclic association schemes, as remarked by the authors of [2] (see [2,p. 389] ). The cyclotomic schemes are examples of pseudocyclic association schemes on prime-power number of points. Very few examples of pseudocyclic association schemes on nonprime-power number of points are currently known (see [11] , [2,p. 390] and [6] ). One class of such examples comes from the action of P G L ( 2 , 2 m )   on the set of exterior lines to a nonsingular conic in P G ( 2 , 2 m )   . We will give a quick review of this class of association schemes in Section 2, and also include a proof of the pseudocyclicity of these association schemes. In [6] , it was further conjectured that the orbital scheme of P Γ L ( 2 , 2 m )   on the set of exterior lines to a nonsingular conic in P G ( 2 , 2 m )   is also pseudocyclic if m   is an odd prime. We will confirm this conjecture in Section 3. As a by-product, we obtain a class of Latin square type strong regular graphs on nonprime-power number of points.

2 The Elliptic Schemes

In the rest of this paper, we always assume that q = 2 m   , where m   is a positive integer.
Let O = { ( ξ , ξ 2 , 1 ) | ξ ∈ F q } ∪ { ( 0 , 1 , 0 ) } .   Then O   is a nonsingular conic in P G ( 2 , q )   . A line of P G ( 2 , q )   is called exterior (resp.
secant) if it meets O   in 0 (resp. 2) points. Let ℰ   (resp. ℋ   ) be the set of exterior (resp.
secant) lines to O   . Then | ℰ | = q ( q − 1 ) 2 , and | ℋ | = ( q + 1 ) q 2 .   The subgroup of P G L ( 3 , q )   fixing O   setwise is isomorphic to P G L ( 2 , q )   (cf. [5,p. 158] ).
Hence P G L ( 2 , q )   acts on ℰ   and ℋ   , respectively. Moreover, it is shown in [8] that P G L ( 2 , q )   acts generously transitively on both ℰ   and ℋ   . Therefore we obtain two association schemes, one on ℰ   and the other on ℋ   . The association scheme on ℰ   will be called the elliptic scheme, and the association scheme on ℋ   is called the hyperbolic scheme.
Since the point ( 1 , 0 , 0 )   is the nucleus of O   (i.e., the point at which all tangent lines to O   meet), we see that each line in ℰ ∪ ℋ   can be written as ( 1 , x , y ) ⊥ = { ( a 0 , a 1 , a 2 ) ∈ F q 3 | a 0 + a 1 x + a 2 y = 0 }   for some x , y ∈ F q   . Let T r : F q → F 2   be the trace map. Also for e ∈ F 2   we define T e = { x ∈ F q | T r ( x ) = e } ,   and T e * = T e \ { 0 }   . Then ( 1 , x , y ) ⊥   is in ℰ   (resp. ℋ   ) if and only if T r ( x y ) = 1   (resp.
T r ( x y ) = 0   ). Given two lines ℓ = ( 1 , x , y ) ⊥   and m = ( 1 , z , u ) ⊥   , we define ρ ^ ( ℓ , m ) = x 2 u 2 + y 2 z 2 + ( x + z ) ( y + u ) .   We remark that the function ρ ^   comes from the cross-ratio of four points on a projective line (see [8] for details). The following theorem in [8] gives a simple description of the orbitals of the action of P G L ( 2 , q )   on ℰ   by using the function ρ ^   .
Theorem 2.1 The orbitals of the action of P G L ( 2 , q )   on ℰ   are Γ 0   (the diagonal class), and Γ a = { ( ℓ , m ) | ρ ^ ( ℓ , m ) = a }   for all a ∈ T 0 *   .
There is a similar description of the orbitals of P G L ( 2 , q )   on ℋ   in [8] . Since we are only concerned with the elliptic scheme in this paper, we omit that description. The pair ( ℰ , { Γ a } )   is an association scheme on ℰ   with ( q − 2 ) 2   classes. The intersection parameters of this scheme are computed in [8] . For a , b , c ∈ T 0 *   , given ( ℓ , m ) ∈ Γ c   , we use p a , b c   to denote | { k ∈ ℰ | ( ℓ , k ) ∈ Γ a a n d ( k , m ) ∈ Γ c } |   . We have:
Theorem 2.2 Let a , b , c ∈ T 0 *   . Then for any v ∈ T 1   ,
p a , b c = { 1 + 2 δ T r ( a c ) , 1 , if a + b + c = 0 ; ∑ τ | { z ∈ F q | z 2 + z = v + a c / τ 2 } | , otherwise, (2)
where the last sum is over the two elements τ ∈ F q   satisfying τ 2 + τ = a + b + c   . Also for all a ∈ T 0 *   , the valency n a = q + 1   .
The association scheme ( ℰ , { Γ a } )   is pseudocyclic. This is already known in [6] . For convenience of the reader, we include a proof here.
Theorem 2.3 The association scheme ( ℰ , { Γ a } )   is pseudocyclic.
Proof: By Theorem  2.2 , the nontrivial valencies of the association scheme ( ℰ , { Γ a } )   are all equal to q + 1   . By Part (2) of Theorem  1.4 , it suffices to prove that ∑ a ∈ T 0 * p a , b a = q   for all b ∈ T 0 *   .
By Theorem  2.2 , for a , b ∈ T 0 *   , we have p a , b a = ∑ τ 2 + τ = b ( 1 − ( − 1 ) T r ( a / τ ) ) .   Fixing τ ∈ F q \ { 0 , 1 }   with τ 2 + τ = b   , we have
∑ a ∈ T 0 * p a , b a = ∑ a ∈ T 0 * ( 1 − ( − 1 ) T r ( a / τ ) + 1 − ( − 1 ) T r ( a / ( τ + 1 ) ) )
= 2 ( q / 2 − 1 ) − ∑ a ∈ T 0 * ( ( − 1 ) T r ( a / τ ) + ( − 1 ) T r ( a / ( τ + 1 ) ) )
= 2 ( q / 2 − 1 ) − ( − 1 − 1 )
= q
This completes the proof. □  

3 Pseudocyclic fusion schemes of the elliptic schemes

As we have seen in the last section, the elliptic scheme ( ℰ , { Γ a } )   is pseudocyclic. In this section, we will consider the fusion scheme of ( ℰ , { Γ a } )   obtained by merging the classes Γ a   via the Frobenius automorphism x ↦ x 2   of F q   . Specifically, for a ∈ T 0 *   , define Δ a = ∪ i ∈ C a Γ i ,   where C a : = { a , a 2 , a 4 , … , a 2 m − 1 }   . Let ℛ   be a set of orbit representatives of T 0 *   under the action of the Frobenius automorphism. Then Δ 0 : = Γ 0   , and Δ a   , a ∈ ℛ   are the orbitals of P Γ L ( 2 , q )   on ℰ   . Therefore ( ℰ , { Δ a } )   is also an association scheme. The (nontrivial) intersection parameters of this fusion scheme will be denoted by P a , b c   , where a , b , c ∈ ℛ   .
We have for a , b , c ∈ ℛ   , P a , b c = ∑ e ∈ C a ∑ f ∈ C b p e , f g ,   where g ∈ C c   . (This is independent of the choice of g ∈ C c   .) Now, if m   is prime, then each C a   , a ∈ ℛ   , has size m   , so the nontrivial valencies of the fusion scheme ( ℰ , { Δ a } )   are all equal to m ( q + 1 )   . Hollmann [6,p. 133] made the following conjecture.
Conjecture 3.1 If m   is an odd prime, then ( ℰ , { Δ a } )   is pseudocyclic.
As far as we know, there is no published proof of this conjecture. There is one sentence on Page 390 of [2] stating the above conjecture as a fact. But this was not backed up by a proof.
Note that the nontrivial valencies of ( ℰ , { Δ a } )   are all equal to m ( q + 1 )   when m   is prime. So in order to prove Conjecture  3.1 , by Part (2) of Theorem  1.4 , we need to show that
∑ c ∈ ℛ P c , c b = m ( q + 1 ) − 1 , (3)
for all b ∈ ℛ   . (Here we implicitly used the fact that P c , c b = P c , b c   since all nontrivial valencies are all equal when m   is prime.) Simplifying the left hand side of ( 3 ), we see that ( 3 ) is equivalent to
∑ k = 0 m − 1 ∑ c ∈ T 0 * p c , c 2 k b = m ( q + 1 ) − 1 . (4)
Now, the k = 0   term of the left hand side of ( 4 ) is equal to q   as seen in the proof of Theorem  2.3 . So in order to prove ( 4 ), we have to show that
∑ k = 1 m − 1 ∑ c ∈ T 0 * p c , c 2 k b = ( m − 1 ) ( q + 1 ) , (5)
for all b ∈ T 0 *   .
We will prove a stronger result:
Theorem 3.2 Let m   be an odd integer, and let k   be any integer in { 1 , 2 , … , m − 1 }   satisfying gcd ( k , m ) = 1   . Write σ = 2 k   . Then
∑ c ∈ T 0 * p c , c σ b = q + 1 , (6)
for all b ∈ T 0 *   .
The most important ingredient in our proof of Theorem  3.2 is a family of polynomials H α , γ ( X )   introduced in [7] . In fact we discovered these polynomials while working on a proof of Theorem  3.2 . We now define the polynomials H α , γ ( X )   and quote the main theorem from [7] .
Let m ≥ 1   be an integer, let k   be any integer in { 1 , … , m − 1 }   with gcd ( k , m ) = 1   , and let r ∈ { 1 , … , m − 1 }   be such that k r ≡ 1   (mod m   ). Write σ = 2 k   and use T r ( X )   to denote the following polynomial in F 2 [ X ]   .
T r ( X ) : = X + X 2 + ⋯ + X 2 m − 1 .   For α , γ   in { 0 , 1 }   , we define the polynomial H α , γ ( X ) : = γ T r ( X ) + ( α T r ( X ) + ∑ i = 0 r − 1 X σ i ) σ + 1 X 2 .   (Note that H α , γ ( X )   is indeed a polynomial in X   with coefficients in F 2   and H α , γ ( 0 ) = 0   .
Also see [7] for connections between H α , γ ( X )   and the Dickson polynomials.) The following is the main theorem from [7] .
Theorem 3.3 Let m , k   be positive integers with gcd ( k , m ) = 1   , let r ∈ { 1 , … , m − 1 }   be such that k r ≡ 1 ( m o d m )   , and let α , γ ∈ { 0 , 1 }   . Then the mapping H α , γ : x ↦ H α , γ ( x )   , x ∈ F q   , maps T 0   bijectively to T 0   , and maps T 1   bijectively to T r + ( α + γ ) m   . In particular, the polynomial H α , γ ( X )   is a permutation polynomial of F q   if and only if r + ( α + γ ) m ≡ 1   (mod 2).
We are now ready to give the proof of Theorem  3.2 .
Proof of Theorem  3.2 : Recall that from Theorem  2.2 , for b , c ∈ T 0 *   ,
p c , c σ b = { 1 + 2 δ T r ( b c ) , 1 , if c σ + c + b = 0 ; ∑ τ 2 + τ = c σ + c + b | { z ∈ F q | z 2 + z = v + b c / τ 2 } | , if c σ + c + b ≠ 0 ,
where v   is any element with T r ( v ) = 1   . Since b ∈ T 0 *   and m   is odd, we can find a unique c 0 ∈ T 0 *   such that c 0 σ + c 0 = b   . So
∑ c ∈ T 0 * p c , c σ b = 1 + 2 δ T r ( b c 0 ) , 1 + 2 ∑ c ∈ T 0 * , c σ + c + b ≠ 0 ∑ τ 2 + τ = c σ + c + b δ T r ( b c / τ 2 ) , 1
= 1 + 2 | { ( c , τ ) ∈ F q * × F q * | τ 2 + τ = c σ + c + b , T r ( c ) = 0 , T r ( b c / τ 2 ) = 1 } | .
For convenience, we define N k ( b ) : = | { ( c , τ ) ∈ F q * × F q * | τ 2 + τ = c σ + c + b , T r ( c ) = 0 , T r ( b c / τ 2 ) = 1 } | .   Our goal is to prove that N k ( b ) = q / 2   for all b ∈ T 0 *   .
For later use, we define the polynomial f ( X ) : = ∑ i = 0 r − 1 X σ i ∈ F 2 [ X ] ,   where r   is an integer satisfying k r ≡ 1   (mod m   ).
Since b ∈ T 0 *   and m   is odd, we can write b = β + β 2   with β ∈ T 0 *   . Then the equation τ 2 + τ = c σ + c + b   involved in the definition of N k ( b )   becomes
c σ + c = ( β + τ ) + ( β + τ ) 2 . (7)
Noting that m   is odd, we see that for any τ ∈ F q   , there is a unique solution c ∈ T 0   of ( 7 ), namely c = f ( τ + β ) + r T r ( τ + β ) = f ( τ + β ) + r T r ( τ ) ,   where in the last equality we used the fact that β ∈ T 0   . Therefore we have
N k ( b ) = { | { τ ∈ F q * : b ( f ( τ + β ) + T r ( τ ) ) τ 2 ∈ T 1 } | , if r is odd; | { τ ∈ F q * : b f ( τ + β ) τ 2 ∈ T 1 } | , if r is even.
We will consider the r   odd case and the r   even case separately.
Case 1. r   is odd. Let x = b / τ 2   , where b = β + β 2 ∈ T 0 *   and τ ∈ F q *   . Then
T r ( b ( f ( τ + β ) + T r ( τ ) ) τ 2 ) = T r ( x ∑ i = 0 r − 1 ( β + b / x ) σ i + x T r ( b / x ) )
= T r ( ∑ i = 0 r − 1 x 2 ( β 2 + b / x ) σ i ) + T r ( x ) T r ( b / x )
= T r ( ∑ i = 0 r − 1 x σ r − i ( β 2 + b / x ) ) + T r ( x ) T r ( b / x )
= T r ( ( β 2 + b / x ) ( f ( x ) + x 2 + x ) ) + T r ( x ) T r ( b / x )
= T r ( β 2 ( f ( x ) + f ( x ) x + f ( x ) 2 x 2 ) ) + T r ( x ) T r ( b x ) ,
where in the last step, we used b = β + β 2   . Now noting that for x ∈ F q *   , H 0 , 0 ( x ) = f ( x ) + f ( x ) x + f ( x ) 2 x 2 .   (One can prove this directly, or see Lemma 3.1 in [7] .) Therefore, in this case, we have
N k ( b ) = | { x ∈ T 0 * | β 2 H 0 , 0 ( x ) ∈ T 1 } | + | { x ∈ T 1 | β 2 H 0 , 0 ( x ) + b / x ∈ T 1 } | . (8)
For the first summand in ( 8 ), noting that H 0 , 0 ( 0 ) = 0   and H 0 , 0   maps T 0   to T 0   bijectively (Theorem  3.3 ), we have
| { x ∈ T 0 * | β 2 H 0 , 0 ( x ) ∈ T 1 } | = | β 2 T 0 * ∩ T 1 |
= ( q / 2 − 1 ) − | β 2 T 0 * ∩ T 0 * | .
Since T 0 *   is a ( q − 1 , q / 2 − 1 , q / 4 − 1 )   (Singer) difference set in the cyclic group F q *   , and β ≠ 0 , 1   , we see that | β 2 T 0 * ∩ T 0 * | = q / 4 − 1   . Hence | { x ∈ T 0 * | β 2 H 0 , 0 ( x ) ∈ T 1 } | = ( q / 2 − 1 ) − ( q / 4 − 1 ) = q / 4 .   For the second summand in ( 8 ), using b = β + β 2   , we see that T r ( β 2 H 0 , 0 ( x ) + b / x ) = T r ( β 2 ( H 0 , 0 ( x ) + 1 / x + 1 / x 2 ) ) .   For any x ∈ T 1   , we have
H 1 , 0 ( x ) = ( 1 + f ( x ) ) σ + 1 x 2
= 1 + f ( x ) + ( 1 + f ( x ) ) / x + ( 1 + f ( x ) ) 2 / x 2
= 1 + 1 / x + 1 / x 2 + H 0 , 0 ( x ) .
Also by Theorem  3.3 , H 1 , 0   maps T 1   bijectively to T r + m = T 0   . Hence
| { x ∈ T 1 | β 2 H 0 , 0 ( x ) + b / x ∈ T 1 } | = | { x ∈ T 1 | β 2 ( H 0 , 0 ( x ) + 1 / x + 1 / x 2 ) ∈ T 1 } |
= | β 2 T 1 ∩ T 1 |
= q / 4 .
Therefore we have N k ( b ) = q / 4 + q / 4 = q / 2 .   Case 2. r   is even. This case is similar to Case 1 and actually easier. Let x = b / τ 2   . By the same computations as those in the r   odd case, we find that T r ( b f ( τ + β ) τ 2 ) = T r ( β 2 H 0 , 0 ( x ) ) .   By Theorem  3.3 , H 0 , 0   maps T 0 *   bijectively to T 0 *   , and maps T 1   bijectively to T r = T 0   .
Therefore,
| { τ ∈ F q * | b f ( τ + β ) τ 2 ∈ T 1 } | = | { x ∈ F q * | β 2 H 0 , 0 ( x ) ∈ T 1 } |
= | { x ∈ T 0 * | β 2 H 0 , 0 ( x ) ∈ T 1 } | + | { x ∈ T 1 | β 2 H 0 , 0 ( x ) ∈ T 1 } |
= | β 2 T 0 * ∩ T 1 | + | β 2 T 0 ∩ T 1 |
= 2 | β 2 T 0 * ∩ T 1 |
= q / 2 .
In summary, in both cases, we have shown that N k ( b ) = q / 2   for all b ∈ T 0 *   . The proof is complete.
Remark 3.4 More general results can be proved in the same fashion as above. Let e , f ∈ F 2   . Define N k , e , f ( b ) : = | { ( c , τ ) ∈ F q * × F q * | τ 2 + τ = c σ + c + b , T r ( c ) = e , T r ( b c / τ 2 ) = f } | .   Then using the same arguments as those in the proof of Theorem  3.2 , we find that N k , 0 , 0 ( b ) = q / 2 − 3   , N k , 1 , 0 ( b ) = q / 2 − 1   , and N k , 1 , 1 ( b ) = q / 2   , for all b ∈ T 0 *   .
Now we can finish the proof of Conjecture  3.1 .
Theorem 3.5 If m   is an odd prime, then ( ℰ , { Δ a } )   is pseudocyclic.
Proof: Since m   is prime, the nontrivial valencies of the scheme are all equal to m ( q + 1 )   .
To finish the proof, we need to prove ( 3 ) for all b ∈ ℛ   . As we have seen in the analysis before the statement of Theorem  3.2 , ( 3 ) is equivalent to ( 5 ). Since m   is an odd prime, any integer k ∈ { 1 , 2 , … , m − 1 }   is relatively prime to m   . So we can apply Theorem  3.2 to obtain ∑ c ∈ T 0 * p c , c σ b = q + 1 ,   for all b ∈ T 0 *   . Now ( 5 ) follows. This completes the proof. □  

4 Latin square type strongly regular graphs

A strongly regular graph srg ( v , k , λ , μ )   is a graph with v   vertices that is regular of valency k   and that has the following properties:
  • 1. For any two adjacent vertices x , y   , there are exactly λ   vertices adjacent to both x   and y   .
  • 2. For any two nonadjacent vertices x , y   , there are exactly μ   vertices adjacent to both x   and y   .
It is well known [9,p. 407] that strongly regular graphs are equivalent to two-class association schemes. An srg ( v , k , λ , μ )   is said to be of Latin square type if ( v , k , λ , μ ) = ( n 2 , t ( n − 1 ) , n + t 2 − 3 t , t 2 − t ) ,   where 1 ≤ t ≤ n + 1   . Any Latin square of order n   gives rise to a Latin square type srg (actually called Latin square graph in this case) with parameters ( n 2 , 3 ( n − 1 ) , n − 2 , 6 )   (see [9,p. 273] ). Many examples of Latin square type srg on prime-power number of points are known [10] . In contrast, not too many examples of Latin square type srg on nonprime-power number of points are known.
In [3] , it was shown that pseudocyclic association schemes can give rise to Latin square type srg. We quote the following theorem from [3] . A proof can be found in [4] .
Theorem 4.1 Let ( X , { R i } 0 ≤ i ≤ d )   be a pseudocyclic association scheme on d t + 1   points.
Then the graph G   whose vertex set is X × X   , and where two distinct vertices ( x , y )   and ( x ′ , y ′ )   are adjacent if and only if ( x , x ′ ) ∈ R i   and ( y , y ′ ) ∈ R i   for some i ≠ 0   , is a Latin square type srg with parameters ( | X | 2 , t ( | X | − 1 ) , | X | + t 2 − 3 t , t 2 − t ) .  
Using Theorem  4.1 , one can obtain Latin square type srg from the pseudocyclic association scheme ( ℰ , { Γ a } )   (the elliptic scheme). These srg have parameters ( 1 2 q 2 ( q − 1 ) 2 , 1 2 ( q − 2 ) ( q + 1 ) 2 , 1 2 ( 3 q 2 − 3 q − 4 ) , q ( q + 1 ) ) .   We note that the Latin square type srg arising from ( ℰ , { Γ a } )   were mentioned in [4] , in which another construction of these srg was given. Now since we have shown that the fusion scheme ( ℰ , { Δ a } )   of the elliptic scheme ( ℰ , { Γ a } )   is also pseudocyclic when m   is an odd prime. We obtain more Latin square type srg via Theorem  4.1 .
Theorem 4.2 Let q = 2 m   , where m   is an odd prime. Then there exists a Latin square type srg with parameters ( 1 2 q 2 ( q − 1 ) 2 , m ( q + 1 ) ( q ( q − 1 ) 2 − 1 ) , λ , μ ) ,   where λ = q ( q − 1 ) 2 + m 2 ( q + 1 ) 2 − 3 m ( q + 1 )   and μ = m 2 ( q + 1 ) 2 − m ( q + 1 )   .
Proof: Straightforward. □  
Acknowledgements: The second author thanks Philips Research Eindhoven, the Netherlands, where part of this work was carried out. The research of the second author is supported in part by NSF grant DMS 0400411.
References

  1. E. Bannai and A. Munemasa, Davenport-Hasse theorem and cyclotomic schemes, unpublished notes.
  2. A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance Regular Graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], 18. Springer-Verlag, Berlin, 1989.
  3. A. E. Brouwer and R. Mathon, unpublised notes.
  4. T. Fujisaki, A four-class association scheme derived from a hyperbolic quadric in P G ( 3 , q )   , Adv. Geom. 4 (2004), 105–117.
  5. J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Second edition. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 1998.
  6. Henk D. L. Hollmann, Association schemes, Master Thesis, Eindhoven University of Technology, 1982.
  7. Henk D. L. Hollmann and Qing Xiang, A class of permutation polynomials of F 2 m   related to Dickson polynomials, Finite Fields Appl. 11 (2005), 111–122.
  8. Henk D. L. Hollmann and Qing Xiang, Association schemes arising from the action of P G L ( 2 , q )   fixing a nonsingular conic in P G ( 2 , q )   , submitted. Preprint available at http://www.math.udel.edu/ ∼   xiang/paper.html
  9. J. van Lint and R. M. Wilson, A Course in Combinatorics, Second edition, Cambridge University Press, 2001.
  10. S. L. Ma, A survey of partial difference sets, Des. Codes Cryptogr. 4 (1994), 221–261.
  11. R. Mathon, 3   -class association schemes, Proceedings of the Conference on Algebraic Aspects of Combinatorics (Univ. Toronto, Toronto, Ont., 1975), 123–155. Congressus Numerantium, No. XIII, Utilitas Math., Winnipeg, Man., 1975.
  12. T. Storer, Cyclotomy and Difference Sets, Lectures in Advanced Mathematics, No. 2 Markham Publishing Co., Chicago, Ill. 1967