--------------------------------------- Let Le(n) by the Lehmer n by n triadiagonal matrix whose entries are zero except at the main diagonal and the diagonals right above and right below wh\ ere for i from 1 to n [when applicble] 1/2 (i/2 - 1/2) Le(n)[i, i] = 1, Le(n)[i, i + 1] = X q , 1/2 (i/2 - 1) Le(n)[i, i - 1] = X q For example the 6 by 6 case looks as follows. [ 1/2 ] [1 , X , 0 , 0 , 0 , 0] [ ] [ 1/2 1/2 1/2 ] [X , 1 , X q , 0 , 0 , 0] [ ] [ 1/2 1/2 1/2 ] [0 , X q , 1 , X q , 0 , 0] [ ] [ 1/2 1/2 (3/2) ] [0 , 0 , X q , 1 , X q , 0] [ ] [ 1/2 (3/2) 1/2 2] [0 , 0 , 0 , X q , 1 , X q ] [ ] [ 1/2 2 ] [0 , 0 , 0 , 0 , X q , 1] and Let Q(n)(X,q) be its determinant. We will use George Andrews' pioneering\ reverse engineering approach to discover an explicit expression for these polynomials. By either directly computing the determinant, or better still using the obvi\ ous recurrence pointed out by D.H. Lehmer (n - 2) Q(n)(X, q) = Q(n - 1)(X, q) - q X Q(n - 2)(X, q) Just for fun, here are the first, 10, polynomials. Q(1)(X, q) = 1 Q(2)(X, q) = 1 - X Q(3)(X, q) = -X q - X + 1 2 2 2 Q(4)(X, q) = X q - X q - X q - X + 1 2 4 2 3 2 2 3 2 Q(5)(X, q) = X q + X q + X q - X q - X q - X q - X + 1 3 6 2 6 2 5 2 4 2 3 4 2 2 3 Q(6)(X, q) = -X q + X q + X q + 2 X q + X q - X q + X q - X q 2 - X q - X q - X + 1 3 9 3 8 3 7 2 8 3 6 2 7 2 6 2 5 Q(7)(X, q) = -X q - X q - X q + X q - X q + X q + 2 X q + 2 X q 2 4 5 2 3 4 2 2 3 2 + 2 X q - X q + X q - X q + X q - X q - X q - X q - X + 1 4 12 3 12 3 11 3 10 3 9 2 10 3 8 Q(8)(X, q) = X q - X q - X q - 2 X q - 2 X q + X q - 2 X q 2 9 3 7 2 8 3 6 2 7 2 6 2 5 6 + X q - X q + 2 X q - X q + 2 X q + 3 X q + 2 X q - X q 2 4 5 2 3 4 2 2 3 2 + 2 X q - X q + X q - X q + X q - X q - X q - X q - X + 1 4 16 4 15 4 14 3 15 4 13 3 14 4 12 Q(9)(X, q) = X q + X q + X q - X q + X q - X q + X q 3 13 3 12 3 11 2 12 3 10 2 11 3 9 - 2 X q - 3 X q - 3 X q + X q - 3 X q + X q - 3 X q 2 10 3 8 2 9 3 7 2 8 3 6 2 7 + 2 X q - 2 X q + 2 X q - X q + 3 X q - X q + 3 X q 2 6 7 2 5 6 2 4 5 2 3 4 2 2 + 3 X q - X q + 2 X q - X q + 2 X q - X q + X q - X q + X q 3 2 - X q - X q - X q - X + 1 5 20 4 20 4 19 4 18 4 17 3 18 Q(10)(X, q) = -X q + X q + X q + 2 X q + 2 X q - X q 4 16 3 17 4 15 3 16 4 14 3 15 4 13 + 3 X q - X q + 2 X q - 2 X q + 2 X q - 3 X q + X q 3 14 4 12 3 13 2 14 3 12 2 13 3 11 - 4 X q + X q - 4 X q + X q - 5 X q + X q - 4 X q 2 12 3 10 2 11 3 9 2 10 3 8 2 9 + 2 X q - 4 X q + 2 X q - 3 X q + 3 X q - 2 X q + 3 X q 3 7 2 8 3 6 2 7 8 2 6 7 2 5 - X q + 4 X q - X q + 3 X q - X q + 3 X q - X q + 2 X q 6 2 4 5 2 3 4 2 2 3 2 - X q + 2 X q - X q + X q - X q + X q - X q - X q - X q - X + 1 Let's try to tackle each coefficient one at a time, and then guess a polynom\ n ial in, q , that we will call, N The coefficient of X^0, i.e. the constant term, is always, 1 the sequence of coefficients of, X, for n from 1 to, 6, is 2 3 2 4 3 2 0, -1, -q - 1, -q - q - 1, -q - q - q - 1, -q - q - q - q - 1 You can see that it is 0 until n=, 1, but then it fits the polynomial N - q - --------- q (q - 1) 2 the sequence of coefficients of, X , for n from 1 to, 8, is 2 4 3 2 6 5 4 3 2 0, 0, 0, q , q + q + q , q + q + 2 q + q + q , 8 7 6 5 4 3 2 q + q + 2 q + 2 q + 2 q + q + q , 10 9 8 7 6 5 4 3 2 q + q + 2 q + 2 q + 3 q + 2 q + 2 q + q + q You can see that it is 0 until n=, 3, but then it fits the polynomial 2 3 (-q + N) (-q + N) ------------------- 3 2 (q + 1) q (q - 1) 3 the sequence of coefficients of, X , for n from 1 to, 10, is 6 9 8 7 6 0, 0, 0, 0, 0, -q , -q - q - q - q , 12 11 10 9 8 7 6 -q - q - 2 q - 2 q - 2 q - q - q , 15 14 13 12 11 10 9 8 7 6 18 -q - q - 2 q - 3 q - 3 q - 3 q - 3 q - 2 q - q - q , -q 17 16 15 14 13 12 11 10 9 - q - 2 q - 3 q - 4 q - 4 q - 5 q - 4 q - 4 q - 3 q 8 7 6 - 2 q - q - q You can see that it is 0 until n=, 5, but then it fits the polynomial 3 4 5 (-q + N) (-q + N) (-q + N) - -------------------------------- 2 3 6 (q + q + 1) (q + 1) (q - 1) q 4 the sequence of coefficients of, X , for n from 1 to, 12, is 12 16 15 14 13 12 0, 0, 0, 0, 0, 0, 0, q , q + q + q + q + q , 20 19 18 17 16 15 14 13 12 24 23 q + q + 2 q + 2 q + 3 q + 2 q + 2 q + q + q , q + q 22 21 20 19 18 17 16 15 14 + 2 q + 3 q + 4 q + 4 q + 5 q + 4 q + 4 q + 3 q + 2 q 13 12 28 27 26 25 24 23 22 21 + q + q , q + q + 2 q + 3 q + 5 q + 5 q + 7 q + 7 q 20 19 18 17 16 15 14 13 12 + 8 q + 7 q + 7 q + 5 q + 5 q + 3 q + 2 q + q + q You can see that it is 0 until n=, 7, but then it fits the polynomial 5 4 6 7 (-q + N) (-q + N) (-q + N) (-q + N) ------------------------------------------- 2 2 4 10 2 (q + 1) (q + 1) (q - 1) q (q + q + 1) 5 the sequence of coefficients of, X , for n from 1 to, 14, is 20 25 24 23 22 21 20 30 29 0, 0, 0, 0, 0, 0, 0, 0, 0, -q , -q - q - q - q - q - q , -q - q 28 27 26 25 24 23 22 21 20 35 - 2 q - 2 q - 3 q - 3 q - 3 q - 2 q - 2 q - q - q , -q 34 33 32 31 30 29 28 27 26 - q - 2 q - 3 q - 4 q - 5 q - 6 q - 6 q - 6 q - 6 q 25 24 23 22 21 20 40 39 38 37 - 5 q - 4 q - 3 q - 2 q - q - q , -q - q - 2 q - 3 q 36 35 34 33 32 31 30 29 - 5 q - 6 q - 8 q - 9 q - 11 q - 11 q - 12 q - 11 q 28 27 26 25 24 23 22 21 20 - 11 q - 9 q - 8 q - 6 q - 5 q - 3 q - 2 q - q - q You can see that it is 0 until n=, 9, but then it fits the polynomial 5 8 7 9 6 (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) - ------------------------------------------------------------------ 2 5 2 2 4 3 2 15 (q + 1) (q - 1) (q + q + 1) (q + 1) (q + q + q + q + 1) q 6 the sequence of coefficients of, X , for n from 1 to, 16, is 30 36 35 34 33 32 31 30 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, q , q + q + q + q + q + q + q , 42 41 40 39 38 37 36 35 34 33 q + q + 2 q + 2 q + 3 q + 3 q + 4 q + 3 q + 3 q + 2 q 32 31 30 48 47 46 45 44 43 42 + 2 q + q + q , q + q + 2 q + 3 q + 4 q + 5 q + 7 q 41 40 39 38 37 36 35 34 33 + 7 q + 8 q + 8 q + 8 q + 7 q + 7 q + 5 q + 4 q + 3 q 32 31 30 54 53 52 51 50 49 48 + 2 q + q + q , q + q + 2 q + 3 q + 5 q + 6 q + 9 q 47 46 45 44 43 42 41 40 + 10 q + 13 q + 14 q + 16 q + 16 q + 18 q + 16 q + 16 q 39 38 37 36 35 34 33 32 31 + 14 q + 13 q + 10 q + 9 q + 6 q + 5 q + 3 q + 2 q + q 30 + q You can see that it is 0 until n=, 11, but then it fits the polynomial 10 11 8 9 7 6 / (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) / ( / 2 2 3 6 2 4 3 2 (q + q + 1) (q + 1) (q - 1) (q - q + 1) (q + q + q + q + 1) 2 21 (q + 1) q ) 7 the sequence of coefficients of, X , for n from 1 to, 18, is 42 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -q , 49 48 47 46 45 44 43 42 56 55 54 53 -q - q - q - q - q - q - q - q , -q - q - 2 q - 2 q 52 51 50 49 48 47 46 45 44 - 3 q - 3 q - 4 q - 4 q - 4 q - 3 q - 3 q - 2 q - 2 q 43 42 63 62 61 60 59 58 57 56 - q - q , -q - q - 2 q - 3 q - 4 q - 5 q - 7 q - 8 q 55 54 53 52 51 50 49 48 - 9 q - 10 q - 10 q - 10 q - 10 q - 9 q - 8 q - 7 q 47 46 45 44 43 42 70 69 68 67 - 5 q - 4 q - 3 q - 2 q - q - q , -q - q - 2 q - 3 q 66 65 64 63 62 61 60 59 - 5 q - 6 q - 9 q - 11 q - 14 q - 16 q - 19 q - 20 q 58 57 56 55 54 53 52 51 - 23 q - 23 q - 24 q - 23 q - 23 q - 20 q - 19 q - 16 q 50 49 48 47 46 45 44 43 42 - 14 q - 11 q - 9 q - 6 q - 5 q - 3 q - 2 q - q - q You can see that it is 0 until n=, 13, but then it fits the polynomial 10 11 8 12 9 7 13 - (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) / 2 2 2 3 7 2 / ((q + 1) (q + q + 1) (q + 1) (q - 1) (q - q + 1) / 4 3 2 6 5 4 3 2 28 (q + q + q + q + 1) (q + q + q + q + q + q + 1) q ) n Let's look at the sequence of polynomials in, N = q , a that we got so far that are the coefficients of, X , of , Q(n)(X, q) for a from 1 to, 7 2 3 3 4 5 N - q (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) [- ---------, -------------------, - --------------------------------, q (q - 1) 3 2 2 3 6 (q + 1) q (q - 1) (q + q + 1) (q + 1) (q - 1) q 5 4 6 7 (-q + N) (-q + N) (-q + N) (-q + N) -------------------------------------------, 2 2 4 10 2 (q + 1) (q + 1) (q - 1) q (q + q + 1) 5 8 7 9 6 (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) - ------------------------------------------------------------------, 2 5 2 2 4 3 2 15 (q + 1) (q - 1) (q + q + 1) (q + 1) (q + q + q + q + 1) q 10 11 8 9 7 6 / (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) / ( / 2 2 3 6 2 4 3 2 (q + q + 1) (q + 1) (q - 1) (q - q + 1) (q + q + q + q + 1) 2 21 10 11 8 12 9 (q + 1) q ), - (-q + N) (-q + N) (-q + N) (-q + N) (-q + N) 7 13 / 2 2 2 3 7 (-q + N) (-q + N) / ((q + 1) (q + q + 1) (q + 1) (q - 1) / 2 4 3 2 6 5 4 3 2 28 (q - q + 1) (q + q + q + q + 1) (q + q + q + q + q + q + 1) q )] You don't have to be a Ramanujan, or George Andrews to conjecture that the n\ a umerator of the coefficient of , X , is always (so far) 2 a - 1 --------' ' | | j | | (N - q ) | | | | j = a Also obvious is the factor /(a + 1) a\ |---------| \ 2 / a q (1 - q) in the denominator. dividing by the former and multiplying by the latter, gives the following se\ quence for a from 1 to,, 7 1 1 1 [1, - -----, ----------------, - -----------------------------, q - 1 2 2 3 (q + 1) (q - 1) (q + q + 1) (q + 1) (q - 1) 1 ---------------------------------------, 2 2 4 2 (q + 1) (q + 1) (q - 1) (q + q + 1) 1 - --------------------------------------------------------------, 1/( 2 5 2 2 4 3 2 (q + 1) (q - 1) (q + q + 1) (q + 1) (q + q + q + q + 1) 2 2 3 6 2 4 3 2 (q + q + 1) (q + 1) (q - 1) (q - q + 1) (q + q + q + q + 1) 2 (q + 1))] We still have to guess an explicit expression for it. Let's look at the sequence of consecutive ratios 2 3 4 5 6 [1 - q, -q + 1, -q + 1, -q + 1, -q + 1, -q + 1] a These are obviously, 1 - q , hence a conjectured expression for the coefficie\ nt of X^a in the Lehner polynomial is 2 a - 1 --------' ' | | j | | (N - q ) | | | | j = a ------------------------------------------- /(a + 1) a\ / a - 1 \ |---------| | --------' | \ 2 / a |' | | j | q (1 - q) | | | (1 - q )| | | | | | | | | \ j = 1 / Plugging in N=q^n we conjecture that trunc(n/2) ----- \ a a (a (a - 1)) Q(n)(X, q) = ) (-1) X q qBinomial(n - a, a) / ----- a = 0 This took, 0.504, seconds.