JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 2, No 2 (1993)

Paul Terwilliger

This is the continuation of an article from the previous issue. In this part, we focus on the thin P- and Q-polynomial association schemes. We provide some combinatorial characterizations of these objects and exhibit the known examples with diameter at least 6. For each example, we give the irreducible modules for the subconstituent algebra. We close with some conjectures and open problems.

for parts II and III appear in part I. TERWILLIGER (a) E*AhE*AkE* = E*AkE*AhE* (b) For all y, z e X with (x, y), (x, z) e Ri, the number of w e X with (x, w) e Rj, (y, w) EUR Rh, (w, z) EUR Rk equals the number of w' EUR X with (x, w') e Rj, (y, w') e Rk, (w', z) e Rh. (Part (i) provides a way to interpret parts (iii), (v) below), (ii) We have the implications where \bullet TH: Y is thin with respect to x. \bullet C: E*TE* is commutative for all integers i (0<i<D). \bullet S: E*TE* is symmetric for all integers i (0 < i < D). \bullet G: For all y, z e X such that (x, y), (x, z) are in the same associate class of Y, there exists g e Aut(Y) such that To get TH*, C*, and S*, replace "thin" by "dual-thin" and E* by Ei in TH, C, and S. (Hi) Suppose Y is P-polynomial with respect to the ordering A0, A1, ..., AD. Then where (iv) Suppose Y is Q-polynomial with respect to the ordering E0, E1, ..., ED. Then where WS* denotes the statement obtained from WS by replacing E*, A^{\tt>\hskip-.5e>} by EJ,, A* for all integers i/> (0 < V < D). (v) Suppose Y is P-polynomial with respect to the ordering A0, A1,..., AD, and Q-polynomial with respect to the ordering E0, E1, ..., ED. Then for each integer i (1 < i < D), the statements all hold if i e {1, D}, and are all equivalent if 2 < i < D - 1 . For each integer i ( 1 < i < D ) , the statements all hold if i e {1, D}, and all are equivalent if 2 < i < D -
1. Now consider the statements \bullet VWS: Lines (214)-(218) hold for all integers i (2 < i < D - 1). \bullet VWS*: Lines (219)-(223) hold for all integers i (2<i<D- 1). Then TH, C, S, WS, VWS, TH*, C*, S*, WS*, VWS*, are all equivalent. The bulk of this section is devoted to proving Theorem 5.1. We will prove parts (i), (ii), then a technical lemma, then parts (iii), (iv), then three more technical lemmas, and finally part (v). Proof of (i). The numbers being equated in (b) are the corresponding entries of the two sides in (a). Proof of (ii). TH -* C: By part (ii) of Lemma 3.4, we may express the standard module V as an orthogonal direct sum of irreducible T-modules. Now fix any integer i (0 < i < D), and apply E* to each module in this sum. In each case the image is an E*TE*-module, with dimension at most 1 by TH. Now E*V is a direct sum of one-dimensional E*TE*-modules. But E*V is a faithful E*TE*-module, so E*TE* is commutative by our comments at the end of Section
1. C -{\tt>\hskip-.5e>} TH: Suppose dim.E*W > 2 for some irreducible T-module W and some integer i (0 < i < D). Then on the one hand, E*W is an irreducible E*TE* -module, for if E*W properly contains a nonzero E*TE*-module U then TU = W by the irreducibility of W, and a contradiction. On the other hand, E*TE* is commutative, so each irreducible E*TE*-module has dimension 1 by our comments at the end of Section
1. This gives a contradiction, so TH holds. TERWILLIGER S -* C: Fix an integer i (0 < i < D), and pick any a, b e E*TE*. Then a, b, and ab are symmetric, so Now E*TE* is commutative, so C holds. G -> S: Fix an integer i (0 < i < D), pick any a e E*TE*, and pick any y, z EUR X. It suffices to show ayz = azy. Assume (x, y), (x, z) EUR Ri, otherwise ayz, azy are both
0. By G, there exists some g e Aut(Y) such that gx = x, gy = z, and gz = y. But g commutes with everything in the Bose- Mesner algebra M, and everything in the dual Bose-Mesner algebra M*(x), hence everything in T, so g commutes with a. Now and we are done. We have now proved (212). The proof of (213) is similar, so we have proved part (ii) of Theorem 5.1. D Definition 5.2. With the notation of Theorem 5.1, assume Y is P-polynomial with respect to the ordering A0, A1, ...,AD. For each n e 1Z, (0 < n < D), let Tn denote the subalgebra of T generated by matrices Also, for all integers i, n (0 < i < D, 0 < n), set LEMMA 5.3. With the notation of Theorem 5.1, assume Y is P-polynomial with respect to the ordering A0, A1, ..., AD. Then the following six statements are equivalent for all n EUR 1Z (0 < n < D). . WS': [(E*A*E*)+, (E*A<E*)-] EUR E*Ti-f+1E* for all integers i, {, C tt EUR {1, 2}, n < i < D + 1 - \sterling , 3 - C < < < 2i - 2n + 1). \bullet WS": [(E*A{\tt<\hskip-.5e<}E*)+, (E*A<E*)-] = 0 for all integers i, \sterling , C ( \sterling EUR { l , 2 } , n < i < D + 1 - f, 3 - \sterling < C < 2i - 2n + 1). \bullet WS"': (E*A2E*)+, (E*A^E*)- (1 < C < 2i - 2n + 1) mutually commute, for each integer i ([n] <i < D). \bullet THn: dim E*W < 1 for all irreducible Tn-modules W and all integers i ([n] < i<D). \bullet Cn: E*TnE* is commutative for all integers i ([n] <i< D). \bullet Sn: E*TnE* is symmetric for all integers i ([n] <i < D). Proof of Lemma 5.3. The proof is by induction on 77 = D, D-1, D-1 - Observe each of the six statements is trivially true if 17 = D, so assume n < D. Since we have the implication xn -{\tt>\hskip-.5e>} xn+1 for each x EUR {WS' WS", WS"', TH, C, S}, it suffices to prove WS', WS”, WS'", THn, Sn, Sn are equivalent under the assumption that WS' WS", W S " ' , THn+1, Cn+1, and Sn+1 all hold. WS' -> WS": Fix integers i, f, < satisfying the bounds in WS' Then i - {\S} + 1 > n + 1, so E*Ti-{\S}+1E* C E*Tn+1E*, implying the commutator in WS', is symmetric by Sn+1. But this commutator is antisymmetric by construction , so it equals
0. WS” -> WS"': Fix an integer i ([n] < i < D). Then we must show (E*,A*E*)-, (E*A(E*)- commute for all integers v, C (2 < v, C < 2i - 2n + 1). We will do this by induction on i = [n], [n] + 1, .... Observe the commutator of these two matrices equals This will be 0 if the middle terms mutually commute. But this is the case, since the first and third terms in (226) commute by induction, and the second term in (226) commutes with the other two by WS". WS"' -{\tt>\hskip-.5e>} THn : The proof will involve two claims. Claim
1. Pick any integer i ([n] < i < D), and suppose w is a common eigenvector for Then TERWILLIGER is a common eigenvector for whenever (228) is not
0. Proof of Claim
1. Assume (228) is not 0, otherwise there is nothing to prove Observe (E*A2E*)- is included in (227), so for some A e C. In fact A ^ 0, for otherwise contradicting the assumption that (228) is not
0. Now pick any integer \sterling (1 < C < 2i - 2n - 1). Observe (E*Ac+2E*)- is included in (227), so Also observe ( E * A 2 E * ) + , ( E * A ^ E * ) - commute by WS"', so and E * A E * w is an eigenvector for ( E * A ^ E * ) - . This proves Claim
1. Now let W denote an irreducible Tn-module such that E*W ^ 0 for some integer i ([n] < i < D). Claim
2. There exist integers j, k ([n] n< j < k < D) and nonzero vectors Wi e E*W (j < i < k) such that Moreover, W = Span{wj, wj+1,..., wk}. Proof of Claim
2. Set Suppose for the moment that k < [n] , so that k = n - 1, and pick any nonzero wk EUR E*W . Then (229)-(233) holds with j = k, and the claim is proved. Now assume k > [n]. Now the matrices (E*A(E*)- (1 < C < 2k - 2n + 1) mutually commute by VWS"', and we observe they are contained in Tn, so they have a common eigenvector w := wk EUR E*W. Now (233) holds. Define the vectors wi ([n] < i < k - 1 ) by and set Now (229), (230) hold. By Claim 1 and induction on i - k, k - 1,..., each wi (j,[n] < i < k) is a common eigenvector for the matrices Pick any integer i (j, [n] < i < k). Then E*AE* = (E*AE*)- is included in (234), so (231) holds. Now assume i > j + 1, so in particular i > n +
1. Then (E*A2E*)- is included in (234), so Replacing i by i + 1 in the lines above, we obtain (232). Now is a Tn-module by (229)-(233), and hence equals W by the irreducibility of W. This proves Claim 2, and THn is immediate. THn -{\tt>\hskip-.5e>} Cn: Observe Tn is closed under conjugate-transpose by (224), (225), so by the discussion at the end of Section 1, we may express the standard module V as an orthogonal direct sum of irreducible Tn-modules. Now fix any integer i ([n] <i< D), and apply E* to each module in this sum. In each case the image is an E*TnE*-module, and has dimension at most 1 by THn. Now E*V is a direct sum of one dimensional E*TnE*-modules. But E*V is a faithful E*TnE*-module, so E*TnE* is commutative. Cn -{\tt>\hskip-.5e>} Sn: By a monomial in Tn, we mean a matrix of the form TERWILLIGER where n, i0, i1, .,., in are integers (0 < n, [n] < i0, i1, ..., in < D) , with and The monomial is balanced if i0 - in. The integer n is the length of the monomial. It suffices to show that every balanced monomial in Tn is symmetric. Let be any balanced monomial in Tn. Then u is immediately seen to be symmetric if n < 1, so assume n >
2. By induction on n, we may assume each balanced monomial in Tn with length less than n is symmetric. First assume ij = i0 for some integer j (1 < j < n - 1), and set Then u1, u2 are balanced, contained in Tn, and have length less than n, so u1, u2 are symmetric by induction. But u1, u2 commute by assumption, so and u is symmetric. Now assume ij ^ i0 for all integers j (1 < j < n - 1). Then or by (235), so Now set Now u4 is balanced, is contained in Tn, and has length less than n, so u4 is symmetric by induction. But now so u is symmetric. Sn -> WS': The commutator in WS' is actually 0, since it is antisymmetric by construction, and contained in the symmetric space E*Tn,E*. This proves Lemma 5.3. Proof of part (iii) of Theorem 5.1. In view of part (ii) of Theorem 5.1, it suffices to show TH -{\tt>\hskip-.5e>} TH*, C -> S, S -> WS, and WS -{\tt>\hskip-.5e>} S. The first implication is from part (v) in Lemma 3.9. The second implication is just Co -> S0 in Lemma 5.3. The third implication holds, since E*AE*AkE* is the transpose of E*AkE*AE*. The last implication will follow if we can show WS -{\tt>\hskip-.5e>} WS', since WS' -> S0 = S by Lemma 5.3. To do this, fix integers i,f, ( such that Then a direct calculation yields But the expression in (236) is some linear combination of the matrices by (71), and hence is 0 by WS. Now WS' follows from (237). This proves part (iii) of Theorem 5.1. Proof of part (iv) of Theorem 5.1. Similar to part (iii). To prove part (v) of Theorem 5.1, we need some lemmas concerning a P- and Q-polynomial scheme Y with diameter at least
3. For notational convenience, we will take Y to be the scheme given in Theorem 4.1. The cases I, IA, II, IIA, IIB, IIC, III refer to part (iv) of Theorem 4.1. TERWILLIGER LEMMA 5.4. Let the scheme Y = (X, {Ri}0<i<D) be as in Theorem 4.1. Pick any x EUR X, and write A* = A*(x). Then where Proof of (i). One may routinely verify (242)-(247) for each of Case I, IA, II, HA, IIB, IIC, III (or see [71]). Indeed /9 = q + q-1 (in Case I, IA), ft = 2 (in Case II, HA, IIB, IIB, IIC), and /3 = -2 (in Case III). Now let C denote the expression on the right side of (239). Expanding the commutator in (238), one observes this commutator equals C. To show C = 0, we observe and show Fix the integers i, j (0 <i,j< D), and recall by (46) that Evaluating EiCEj using this, we find But by Lemma 3.2 and Definition 3.10, by (246), and certainly so EiCEj = 0 by (250). We now have (249), and hence (238), (239). Lines (240), (241) hold by a dual argument, so Lemma 5.4 is proved. LEMMA 5.5. Let the scheme Y = (X, {Ri}0<i<D) be as in Theorem 4.1, and let 0, 7, 7*, 8, Q* be as in Lemma 5.4. Fix any x e X, and write E* = E*(x) (0 < i < D). Then (i) where and h0, hD are indeterminates. where TERWILLIGER ana en, e, are indeterminants. where (iv) Let h*, e*+, e*-, g*+, g*- denote the constants obtained from (252), (254), (255), (257), (258) by replacing &* by 6j (0 < j < D). Then the equations (251), (253), (256) still hold after replacing 7, Q, A, hi, e+, g+ and E* (0 < j < D) by 7*, Q", A*, h*, e*+, g*+, and Ej (0 < j < D), respectively. Proof of (i)-(iii). Pick any integers i, j (0 < i, j < D, 0 < i - j < 2), where i - j = 0 (in part (i)), i - j = 1 (in part (ii)), and i - j = 2 (in part (iii)). Now multiply both sides of (239) on the right by E* and on the left by E*. Writing the result as a linear combination of monomials, we get (i)-(iii). In part (i), one finds one needs /3 + 1 ^ 0 to carry this out. But this holds, for otherwise we are in Case I or Case I A, with q + g-1 + 1 = / 9 + 1 = 0, forcing q3 = 1 and contradicting (16). Part (iv) is obtained by a similar argument, so Lemma 5.5 is proved. LEMMA 5.6. Let the scheme Y - (X, {Ri}0<i<D) be as in Theorem 4.1, and let hi,h*, e+, e*+, g+, g*+ be as in Lemma 5.5. Then To get e*+, e*-, g*+, g * - , replace Bj by 0j (0 < j < D) in the above formulae. In particular, Proof. In each of (254), (255), (257), (258), equate the expression on the right with the corresponding expression above. In each case, the resulting equation is equivalent to (242) or (243). The last assertion is immediate from (7). We now return to the proof of Theorem 5.1. Proof of part (v) of Theorem 5.1. Line (216) holds for i = 1, since both sides are 0, and (215) is certainly true for i = D . For the first part of (v), it now suffices to show (214)-(218) are equivalent for all integers i (1 < i < D) . Fix such an integer i. Now lines (217), (218) are equivalent by (251), (259). Using we find by (251) that Now (214), (218) are equivalent, since and 1 + hD is indeterminant. Similarly so (215), (217) are equivalent, and so (216), (218) are equivalent. Now (214)-(218) are all equivalent. The lines (219)-(223) can be treated in a similar manner, so consider the last assertion TERWILLIGER of part (v). The statements TH, C, S, WS, TH*, C*, S*, WS* are equivalent by parts (i)-(iv) of Theorem 5.1, and the implications S -> VWS, S* -> VWS* are immediate, so it suffices to show VWS -> TH and VWS* -> TH*. VWS -+ TH: Assume VWS. Then it suffices to show WS' (in the language of Lemma 5.3), since WS' -> TH1 by that Lemma, and since TH1 -> TH by Lemma 3.6. Thus it suffices to pick integers i, f, C satisfying and show Case (\sterling , C) = (1, 2) or (2, 1). Immediate from (217), (218). Case (\sterling , C) = (1, 3). Assume for the moment that 0 = 0 in (242). Then by the statement below (247), we are in Case I or Case IA, with q + q-1 = /? =
0. But then q2 = -1 and then q4 = 1, so D = 3 by (16). But now (265) can be seen to hold using A3 e Span{E0, I, A, A2}, so we may assume ft ^
0. Now multiply both sides of (253) on the left by E*AE*, and solve for E*AE*AE*AE*AE*. We conclude this matrix is a linear combination of the symmetric matrices E*AE*AE*AE*AE*, E*A2E*A2E*, E*AE*AE*AE*, plus a matrix (which we will denote by K) contained in E*Ti-1E*. Now observe since E*Ti-1E* is closed under transpose. Thus (265) holds, and we are done in the present case. Case \sterling = 2n for some integer n > 3 - \sterling . This case will follow if we can show Observe e- ^ 0 by (261), so we may solve for E * A E * A 2 E * in (253). Inspecting the other terms in (253), we find (266). Case C = 2n + 1 for some integer n > 3 - \sterling . This will follow if we can show Observe g- ? 0 by (263), so we may solve for E*AE*A2E* in (256). Inspecting the other terms in (256), we find (267). We are now done in the present case. The above four cases exhaust the possibilities in (264), so we have proved VWS -{\tt>\hskip-.5e>} TH. The implication VWS* -> TH* is obtained by a dual argument, so we have now proved part (v) of Theorem 5.1. COROLLARY 5.7. Suppose the scheme Y = (X, {Ri}0<i<D) in Theorem 5.1 is P-polynomial with respect to the ordering A0, A1,..., AD of the associate matrices, and Q-polynomial with respect to the ordering E0, E1,..., ED of the primitive idempotents. Further assume the intersection numbers satisfy or the Krein parameters satisfy Then Y is thin. Proof. Pick any x EUR X, and write A* = A*(x), E* = E*(x) (0 < i < D). Now (268) implies VWS by (219), since E*AE* = 0 whenever pi = 0 (0 < i < D) by (64). Similarly (269) implies VWS*, since EiA*Ei = 0 whenever gi = 0 by (65). In either case, Y is thin by part (v) of Theorem 5.1. This proves Corollary 5.7. n
6. Examples of thin P- and Q-polynomial schemes In this section we exhibit the known thin P- and Q-polynomial schemes with diameter at least
6. For each example, we give the irreducible T(x)-modules. If the scheme has more than one P- and Q-polynomial structure, we view each structure as a separate scheme. Information on the examples can be found in the books of Bannai and Ito [3] and Brouwer, et al. [11]. See also [23], [63], [74], and the references below. We suppress the details of our calculations. 1Y and Y represent, respectively, the bipartite half and antipodal quotient of a P-polynomial scheme Y. (Bannai and Ito [3, p. 316]). Example 6.1. Let D denote an integer at least
3. Then for each example below, Y = (X, {Ri}0<i<D) is a thin P- and Q-polynomial scheme. The constants 91, r1, r2, s, s*, and the case given in parenthesis, refer to LS(Y), as indicated in (82)-(88). (1) The Johnson scheme J(D, N)(2D < N) [22], [52], [61], [71], [73], [75]. TERWILLIGER X = all subsets of {1,2,..., N} of order D, (2) The Odd graph OD+1 [9], [50], [76]. J(D, 2D + 1) has another P-polynomial structure R0, RD, R1, RD-1,... in terms of the original one. (3) J(2D, 4D) [67]. (4) J(2D + 1, 4D + 2) [67]. (5) The generalized Johnson scheme JPn(D, N)(2D < N) [25]. X - all D dimensional subspaces of a fixed N dimensional vector space over the finite field GF(pn), where (6) The dual polar spaces of rank D [16], [64]. Let U denote a finite vector space with one of the following nondegenerate forms: A subspace of U is called isotropic whenever the form vanishes completely on that subspace. In each of the above cases, the dimension of any maximal isotropic subspace is D. X = set of all maximal isotropic subspaces of U. where TERWILLIGER (7) 2A2D-1(pn)' [41]. 2 A 2 D - 1 (p n ) has another Q-polynomial structure E0, ED, E1, E D - 1 , ... in terms of the original one above. where (8) 1D2D(pn). (9) 1D2D+1(pn). where (10) Hemmeter's scheme HemD(pn) [12]. Let X denote the vertex set of the scheme CD-1(pn) (p odd), and let X+ := {x+|x e X } , X - := { x - | x e X} denote two copies of X. For all integers i (0 < i < D - 1), and for all x, y e X with (x, y) e Ri: where (11) 1Hem2D(pn)- Same data as 8. (12) 1Hem2D+1(pn). Same data as
9. The bipartite half of Hemmeter's scheme is known as Ustimenko's scheme [40]. (13) The Hamming scheme H(D, q) (q > 2) [27], [52], [61], [71], [73], X = ail D-tuples of elements from the set {1, 2 , . . . , q}, (x, y) 6 Ri iff x,y differ in exactly i coordinates (x, y e X), (14) H(D,2)' (D even) [76], If D is even, H(D, 2) has another P-polynomial structure R0, RD-1, R2. RD-3, ... and another Q-polynomial structure E0, E D - 1 , E2, E D - 3 , . . . in terms of the original ones. With respect to the original P-polynomial structure and the new Q-polynomial structure, or with respect to the new P-polynomial structure and the original Q-polynomial structure: (With respect to the new P-polynomial structure and the new Q-polynomial structure, we get the original scheme). (15) 1H(2D, 2) [52], [71], [73]. (16) 1H(2D + 1, 2) [52], [71], [73]. 1H(2D + 1, 2) has another P-polynomial structure R0, RD, R1, RD-1, ... and another Q-polynomial structure E0, E2, E 4 , . . . , E3, E1 in terms of the original ones. (17) 1E(2D + 1, 2)' [76]. With respect to the new P-polynomial structure and the original Q-polynomial structure: (18) 1H(2D + 1, 2)" [67]. With respect to the original P-polynomial structure and the new Q-polynomial structure: (19) 1H(2D + 1, 2)'" [72]. With respect to the new P-polynomial structure and the new Q-polynomial structure: (20) H(2D, 2) [72]. We note H(2D + 1, 2) is isomorphic to 1H(2D + 1, 2). (21) 1H(4D, 2) [67]. (22) 1H(4D + 2,2) [67]. (23) Ordinary 2D-cycle. (24) Ordinary (2D + 1)-cycle. Proof. It is well known that the above schemes are P- and Q-polynomial. A recent reference is [11, p253]. Also, the given schemes are thin. Indeed, the examples other than 10, 11, and 12 can be shown to satisfy condition G of Theorem 5.1. Example 10 is thin by Corollary 5.7, and Examples 11, 12 can be shown to satisfy condition VWS of Theorem 5.1. Example 6.1, continued. Let the scheme Y = (X, {Ri}0<i<D) be as in Example 6.1. Fix any x EUR X, and let W denote an irreducible T(x)-module with diameter d >
1. Then W is strong. Let p, v, e denote the endpoint, dual endpoint, and auxiliary parameter of W, respectively, and recall TERWILLIGER by (93), (98), (204). Then additional restrictions are given below. The parameters ai(W) (0 < i < d), b i ( W ) (0 < i < d - 1), c i ( W ) (1 < i < d) of LS(W) are also given. (1) J(D, N). (2) OD+1. (3) J(2D, 4D). If v = D - d: If v = D - d - 1 : (4) J(2D + 1, 4D + 2). If e = D - d - 2 u : If e = D - d - 2 u + 2: (5) Jq(D,N). where TERWILLIGER (6) Dual polar spaces. (7) 2A2D-1(pn)'. (8) 1D2D(pn). If u = D - d: If u, = D-d-1: (9) 1D2D+1(pn). If e = 2v-D + d: If e = 2v-D + d-2: TERWILLIGER (10) HemD(pn). (11) 1Hem2D(pn)- Same as (8). (12) 1Hem2D+1(pn). Same as (9). (13) H(D, q). (14) H ( D , 2)' (15) 1H(2D, 2). If u = D - d: If u = D - d - 1 : (16) 1H(2D + 1, 2). If D - d is even: If D - d is odd: (17) 1H(2D +1, 2)'. TERWILLIGER (18) 1H(2D + 1, 2)". If D - d is even: If D - d is odd: (19) 1H(2D + 1, 2)'". If D - d is even: If D - d is odd: (20) H(2D, 2). If v = D - d: If v = D-d-1:\\ (21) 1H(4D, 2). If v = D-d; If v = D - d - 1 : (22) lH(4D + 2,2). TERWILLIGER If e = d - D: If e = d-D + 2: (23) Ordinary 2D-cycle. If ( u , v , d , e ) = ( 1 , 1 , D-2,0): (24) Ordinary (2D + 1)-cycle. If (n, v, d, e) - (1, 1 , D - 1 , 1): Note 6.2. As indicated in [11, p195], there are 5 known infinite families of P- and Q-polynomial schemes with unbounded diameter D, that are not listed in Example 6.1. They are (i) the Doob schemes (IIC, r = 12, s = s* = -4) [11, p27], [24], (ii) the schemes Hq(D, N)(N > D) of bilinear forms (I, s = s' = r, = 0, r2 = q=-N-1) [3, p306], [23], [35], (iii) the schemes Altq(N) (D = [N]) of alternating forms (I, a = s* = r1 = 0, r2 = g-D-1 (if N is even), r2 = q-D-3 (if N is odd))[3, p307], [37], (iv) the schemes Herq(D) of Hermitean forms (I, s = s* = r1 = 0,r2 = - q - D - 1 ) [3, p308], [42], and (v) the schemes Quadq(N)(D = [N+1]) of quadratic forms (I, s = s' = r1 = 0, r2 = q-D-3 (if N is even), r2 = q-D-1 (if N is odd) [3, p308], [26], [32], [33], [34], The schemes (i)-(v) are not thin if D > 3, since they can-be shown to violate condition VWS in Theorem 5.1. Every known P- and Q-polynomial scheme with diameter at least 6 is listed in (i)-(v) above or in Example 6.1 [11, p253].
7. Directions for further research In this section we give some conjectures and problems concerning a commutative association scheme Y = (X, {Ri}0<i<D) with diameter D >
3. We refer the reader to Definitions 3.5, 3.7 and 3.10 for the meaning of thin, P-polynomial, and Q-polynomial, respectively. Conjecture
1. Suppose Y is thin and imprimitive. Then the subschemes and quotient schemes of Y are thin. (See [3, p134, p140] for the definitions of imprimitive, subscheme, and quotient scheme). For 2, 3 below, assume Y is P-polynomial, thin, but not Q-polynomial. Conjecture
2. If D is sufficiently large, then either (2a) Y is bipartite, and the bipartite half 1Y is thin and Q-polynomial, or (2b) Y is antipodal, and the antipodal quotient Y is thin and Q-polynomial. Problem
3. Find all examples that come under (2a), (2b) above. For 4-6 below, assume Y is P- and Q-polynomial, but not thin. Conjecture
4. Y has only one P-polynomial structure and only one Q-polynomial structure. Furthermore, pk = qk for all integers i, j, k (0 < i, j, k < D). Problem
5. Fix any x EUR X, and find the structure of those irreducible T(x)- modules that are not thin. If W is such a module, how big can the dimensions TERWILLIGER of the E*(x)W (0<i<D) be? Conjecture
6. For each x e X, there exists a nonthin irreducible T(x)-module with endpoint 1, and a nonthin irreducible T(x)-module with dual endpoint
1. For 7-11 below, assume Y is thin, P- and Q-polynomial. Conjecture
7. Either (7a) The endpoint of W is at most the dual endpoint of W, for all x e X and all irreducible T(x)-modules W, or (7b) the endpoint of W is at least the dual endpoint of W, for all x EUR X and all irreducible T(x)-modules W. (See (72), (79) for the definition of endpoint and dual endpoint). Conjecture
8. Every irreducible T(x)-module with diameter at least 1 is strong, for every x EUR X . See Definition 4.4 and Theorem 4.10. Conjecture
9. For all integers u, v, d, e satisfying (270), (271), and all x EUR X, let mult[u, v, d, e](x) denote the multiplicity with which the irreducible T(x)- module with endpoint u, dual endpoint v, diameter d, and auxiliary parameter e appears in the standard module V. If there is no such module, set mult [u, v, d, e](x) =
0. If Conjectures 7, 8 hold, we further conjecture that mult [u, v, d, e](x) is determined by n, v, d, e and the intersection numbers of Y (and hence is independent of x). Conjecture
10. Fix any x e X and consider the ring R := {a|a e T(x), the entries of a are all integers}. Then R contains (is generated by?) E*(x), Ai (0 < i < D). Now let W denote a strong irreducible T(x)-module, with endpoint u, dual endpoint v, diameter d, and auxiliary parameter e. For each a e R, the eigenvalues of the restriction of a to W can be computed in terms of u, v, d, e, and the intersection numbers of Y. Since a has integer entries, these eigenvalues must be algebraic integers. This "feasibility condition" restricts (u, v, d, e) beyond (270), (271) for many Y. We conjecture ai(W) (0 < i < d) and Ci(W)bi-1(W) (1 < i < d) (which are eigenvalues of a = E * ( x ) A E * ( x ) and a = E * ( x ) A E * ( x ) A E * ( x ) , respectively), are rational integers. Problem
11. Find all the thin P- and Q-polynomial schemes Y with sufficiently large diameter (see [27], [41], [50], [52], [66], [71], [72], [75], [76]). If necessary, assume some combination of Conjectures 7, 8, 9,
10. For 12-15 below, assume Y is P-polynomial. Conjecture
12. Fix any vertex x e X, write E* = E*(x) (0 < i < D), T = T(x), and assume where Tn (n e 1Z, 0 < n < D) is the subalgebra of T from Definition 5.2. Then either Y is Q-polynomial, or else Y is antipodal, and the antipodal quotient Y is Q-polynomial (see Lemma 5.5). Conjecture
13. Suppose the intersection numbers of Y satisfy p0 = 1 (so that Y is antipodal). Then Y is thin. Conjecture
14. Suppose the intersection numbers of Y satisfy pi i+1 = p 0 - ( p 1 + 1)pi (0 < i < D - 1) . Suppose further that there does not exist vertices x, y, z, w EUR X with (x, y), (y, z), (z, w),(w, x), (y, w) e Rl, (x, z) EUR R2 (i.e., K is the point graph of a regular near polygon [11, p199]). Then Y is thin. Conjecture
15. Suppose Y is primitive, but not a Hamming scheme (part 13 in Example 6.1) or an ordinary cycle. Suppose further that G = Aut(Y) acts distance-transitively on X (see[11, p136] for a definition of distance-transitive). Then according to Praeger, Saxl, and Yokoyama [58], either (i) G is almost simple (i.e., S C G C Aut(S) for some nonabelian finite simple group S), or (ii) G is affine (i.e., G has an elementary abelian normal subgroup which is regular on X). We conjecture that (i) holds if and only if Y is thin. Problems 16-17 refer to the algebra T defined in Section
1. Problem
16. Find the commutative association schemes Y where T is a finite dimensional vector space over C. Let us say these schemes are of finite type. We conjecture that if Y is P- and Q-polynomial with or TERWILLIGER then Y is finite type. (See Corollary 5.7). Conjecture
17. Referring to the previous problem, suppose Y is of finite type. Then T is semisimple. Note. A distance biregular graph is a certain generalization of a P-polynomial scheme [21], [31], [55], [57], We expect most of the results of this paper can be extended to these objects. It is requested that progress on the above conjectures and problems be reported to us.