[seqfan] Re: A269254, A034807 and Chebyshev polynomials

[Andrew N W Hone]

P.S. There was an obvious typo in a formlula that should have read n = 2 \cos z. 

Sorry for posting again when I said I wouldn't!
________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Andrew N W Hone [A.N.W.Hone at kent.ac.uk]
Sent: 31 October 2017 11:50
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: A269254, A034807 and Chebyshev polynomials

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/

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