[seqfan] Re: A269254, A034807 and Chebyshev polynomials

[Andrew N W Hone]

Dear Seqfans, 

I've got a long post to make about A269254. After that, I have had a suggestion from Neil 
that we should stop posting to seqfan about this sequence for a while, but instead I should 
club together with the other people who have been actively working on the sequence, and 
together we should write a paper which gives a definitive explanation of the properties of the 
sequence. The paper can be submitted to Journal of Integer Sequences, and a link to the OEIS 
can be added once it has appeared. 

We should be able come up with a streamlined algorithm for extending the sequence 
arbitrarily far, and eliminate the need for further conjectures about how to determine 
subsequent terms. 

I am suggesting that (in alphabetical order) Hans Havermann, Brad Klee, Don Reble and Bob Selcoe 
should all be co-authors of the paper. Please accept my apologies if I omitted anyone, and do 
let me know (off list) who you are if you have been left out. Similarly, if anyone listed does not 
want to be involved in the paper then also let me know (off list), although I think this would be 
a shame. I'm happy to do most of the writing (in Latex), but I'd appreciate careful reading 
from my co-authors. I've got a lot of other projects on simultaneously, so I am not able to  
do this very quickly, but maybe we can have a draft circulating soon. 

On to the mathematics. I am extremely grateful to Don Reble for his recent comment for "those who 
don't know": I was one of those who didn't know, and in working out how to prove his statement I 
was led to the simplest formula for the terms s_k(n) thus far, with a simple explanation and proof of all 
the factorizations observed so far, and an infinite sequence of higher factorizations, which should allow 
us to give a succinct description of the properties of A269254. 

Recall the definition of Chebyshev polynomials T_k (non-standard) and U_k (standard) as in my 
previous posts. 

The main observation is the following: the terms of the sequence s_k(n) are given by the 
formula 

s_k(n) = U_{2k}( \sqrt{n+2} ) = \sin ( (2k+1) z /2 ) / \sin ( z / 2 ), 

where

z = 2 \cos z 

as before. The above formula may look curious, because the argument contains a square root, but recall that 
Chebyshev polynomials with even/odd index are even/odd functions, respectively, so the square root 
disappears and one finds polynomials in n. The above formula follows directly from the expressions in 
my previous posts, by using trigonometric identities. 

Now to prove Don Reble's statement, that s_k is composite whenever 2k+1 is,  
let 

2k+1 = ab 

(so a,b are both odd and >1), and note that 2nd kind Chebyshev polynomials have 
the property that 

U_{ab-1}(m) = U_{a-1}( T_b(m) ) U_{b-1}(m), 

which follows from the definitions of U_k, T_k in terms of sine and cosine. 
So if we let 

m = \sqrt{n+2} 

then we see that s_k(n) factorizes as 

s_k(n) = U_{a-1}( T_b(m) ) U_{b-1}(m), 

and since a-1,b-1 are both even, these factors are both polynomials in m, hence 
polynomials in the integer n, so this is a factorization into a pair of integers >1.

Now here is the main result that follows from the above formula (again proved simply by using  
trigonometric identities, but I omit the proof for now - wait for the paper!). 

Theorem. If n = T_p(j) for integer j, then s_k(n) can be factored as 

s_k( T_p (j) ) = s_k(j) r_k(j), 

where the factor 

r_k (j) = U_{p-1}( T_{2k+1}(\sqrt{j+2}) ) / U_{p-1} (\sqrt{j+2}) 

satisfies a linear recurrence of order p which is determined explicitly. In particular, 
for all odd p it is given by 

(S-1)(S^2 - T_2(j) S + 1)(S^2 - T_4(j) S +1) ... (S^2 -T_{p-1}(j) S +1) r_k = 0. 

(S denotes the shift operator which acts on any sequence according to S f_k = f_{k+1}.)

There are a few comments to make about this result: 

1) When p=2 it reproduces the result originally proved by Brad Klee: r_k is given by 

r_k(j) = T_{2k+1}(\sqrt{j+2}) ) / \sqrt{j+2}, 

which is an integer sequence, and satisfies the same recurrence as does s_k(j), that is  

(S^2 - j S + 1) r_k =0. 

2) For the purposes of factorization, as mentioned in many previous posts, we are only 
interested in cases where p is prime, since factorizations for n = T_p (j) for composite p=ab 
reduce to lower cases, due to the property T_{ab}(j) = T_a(T_b(j)). 

3) For odd (prime) p>1, the sequence r_k(j) is sequence of rational numbers, not necessarily 
integers, because the denominator is the integer 

U_{p-1} (\sqrt{j+2}) = s_{(p-1)/2}(j) = N, 

say, and this does not always divide the numerator R_k(j) = U_{p-1}( T_{2k+1}(\sqrt{j+2}) ). However, 
I claim that the sequence s_k(j) mod N is  is periodic with period p: clearly it vanishes mod N 
when k = (p-1)/2 mod p, and I further claim that it is non-vanishing for all other indices mod p. Hence 
the factorization in this case takes the form 

s_k( T_p(j) ) = s_k(j) R_k(j) / N 

where N divides the first factor whenever  k = (p-1)/2 mod p, and otherwise it must divide the 
second factor R_k(j). The case p = 3 is a special case of this, where N = j+1, and from these formulae 
it is easy to obtain the trisection results in earlier posts from me and Brad Klee (including 
explicit expressions for the recurrences satisfied by the trisections). 

I will now contact the relevant people off list, and hopefully we can clean up the entry for 
A269254 once the paper is written. In the mean time I do not plan to submit further messages 
to seqfan.

Best wishes to all,
Andrew Hone

________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Brad Klee [bradklee at gmail.com]
Sent: 30 October 2017 03:28
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: A269254, A034807 and Chebyshev polynomials

After: http://list.seqfan.eu/pipermail/seqfan/2017-October/018063.html

Verification of induction base cases when n = T_3(j), j>2, ( Cubic
Chebyshev )
===============================================
Define the initial conditions as j-polynomials, with offset zero,

Z_0(n) = -1 + Sum_{i=0}^n T_i( T_3( j ) ) ;               n=0,1,2 . . . 8;

X_0(n) = -1 + Sum_{i=0}^n T_i( j );                          n=3*k and
n=3*k+2; k=0,1,2;
X_0(n) = -1 + Sum_{i=0}^{(n-1)/3} T_{3*i}( j );      n =3*k+1; k=0,1,2;

Y_0(n) = Z_0(n) / X_0(n);                                             n
=0,1,2 . . . 8.

These definitions must and do satisfy the X recurrence up to index 8:

X_0(n) = T_3(j)*X_0(n-3) - X_0(n-6),                 n=6,7,8 ;

Explicitly the initial condition vectors are,

Z_0 = {1, 1 - 3 j + j^3, -1 - 3 j + 9 j^2 + j^3 - 6 j^4 + j^6, -1 + 6 j +
  9 j^2 - 29 j^3 - 6 j^4 + 27 j^5 + j^6 - 9 j^7 + j^9,
 1 + 6 j - 27 j^2 - 29 j^3 + 99 j^4 + 27 j^5 - 111 j^6 - 9 j^7 +
  54 j^8 + j^9 - 12 j^10 + j^12,
 1 - 9 j - 27 j^2 + 111 j^3 + 99 j^4 - 351 j^5 - 111 j^6 + 441 j^7 +
  54 j^8 - 274 j^9 - 12 j^10 + 90 j^11 + j^12 - 15 j^13 + j^15, -1 -
  9 j + 54 j^2 + 111 j^3 - 441 j^4 - 351 j^5 + 1275 j^6 + 441 j^7 -
  1728 j^8 - 274 j^9 + 1275 j^10 + 90 j^11 - 545 j^12 - 15 j^13 +
  135 j^14 + j^15 - 18 j^16 + j^18, -1 + 12 j + 54 j^2 - 274 j^3 -
  441 j^4 + 1728 j^5 + 1275 j^6 - 4707 j^7 - 1728 j^8 + 6733 j^9 +
  1275 j^10 - 5643 j^11 - 545 j^12 + 2925 j^13 + 135 j^14 -
  951 j^15 - 18 j^16 + 189 j^17 + j^18 - 21 j^19 + j^21,
 1 + 12 j - 90 j^2 - 274 j^3 + 1275 j^4 + 1728 j^5 - 6733 j^6 -
  4707 j^7 + 17577 j^8 + 6733 j^9 - 26181 j^10 - 5643 j^11 +
  24207 j^12 + 2925 j^13 - 14553 j^14 - 951 j^15 + 5796 j^16 +
  189 j^17 - 1519 j^18 - 21 j^19 + 252 j^20 + j^21 - 24 j^22 + j^24}

X_0 = {1, 1, -1 + j + j^2, -1 - 2 j + j^2 + j^3, 1 - 3 j + j^3,
 1 + 3 j - 3 j^2 - 4 j^3 + j^4 + j^5, -1 + 3 j + 6 j^2 - 4 j^3 -
  5 j^4 + j^5 + j^6, -1 - 3 j + 9 j^2 + j^3 - 6 j^4 + j^6,
 1 - 4 j - 10 j^2 + 10 j^3 + 15 j^4 - 6 j^5 - 7 j^6 + j^7 + j^8}

Y_0 = {1, 1 - 3 j + j^3, 1 + 4 j - 4 j^2 - j^3 + j^4,
 1 - 8 j + 8 j^2 + 6 j^3 - 6 j^4 - j^5 + j^6,
 1 + 9 j - 30 j^3 + 27 j^5 - 9 j^7 + j^9,
 1 - 12 j + 12 j^2 + 43 j^3 - 43 j^4 - 34 j^5 + 34 j^6 + 10 j^7 -
  10 j^8 - j^9 + j^10,
 1 + 12 j - 12 j^2 - 79 j^3 + 79 j^4 + 103 j^5 - 103 j^6 - 53 j^7 +
  53 j^8 + 12 j^9 - 12 j^10 - j^11 + j^12,
 1 - 15 j + 140 j^3 - 378 j^5 + 450 j^7 - 275 j^9 + 90 j^11 -
  15 j^13 + j^15,
 1 + 16 j - 16 j^2 - 188 j^3 + 188 j^4 + 526 j^5 - 526 j^6 -
  596 j^7 + 596 j^8 + 339 j^9 - 339 j^10 - 103 j^11 + 103 j^12 +
  16 j^13 - 16 j^14 - j^15 + j^16}

Then define bilinear basis vectors,

B_i = {X_0(6+i)*Y_0(6+i),X_0(6+i)*Y_0(3+i),X_0(6+i)*Y_0(i),X_0(3+i
)*Y_0(6+i),X_0(3+i)*Y_0(3+i),X_0(3+i)*Y_0(i)}

With the earlier coefficient vectors v_{k}, again it's easy to verify that,

B_{i} dot v_{k} = 0;               i=0,1,2, k = 0,1;
===> B_{i} dot v_{2} = 0,   i=0,1,2.

For each of three subsequences, these j-polynomials satisfy the base case.

===============================================

A Mathematica algorithm for verifying the complete induction proof
evaluates in less than one tenth of one second.
( cf. second post of http://community.wolfram.com/groups/-/m/t/1210746 )
This essentially reproves the theorem earlier claimed by Andrew Hone,
( cf. http://list.seqfan.eu/pipermail/seqfan/2017-October/018035.html ),
with m^2 (m + 3) - 1 = 1 - 3 j + j^3 under index shift m = j - 1.

Also worth mentioning that definitions above for X(n) and Z(n) appear to be
valid for all values of n.

"What is in a name?" To my eyes, A269254 at first /was/ something of an
unseen rose. Now we have a budding sight, which combines simple linear
algebra and the Chebyshev polynomials. Yet a thorny question remains. Are
the Chebyshev cases the only cases with interesting factorization?

Regards,

Brad

--
Seqfan Mailing list - http://list.seqfan.eu/