[seqfan] A269254, A034807 and Chebyshev polynomials

[Andrew N W Hone]

I think I have found the right idea for how to go about generalizing the pattern 
of factorization for the values of n with a_n = -1. It seems to me that the best way 
to think about it is in terms of Chebyshev polynomials. 

My first comment is just about nomenclature in the OEIS. Comparing with previous posts, 
and looking at A034807, I think the name of Chebyshev should appear in the title there 
instead of (or as well as?) the name "Lucas polynomials" (and "Cardan": should that be 
Cartan, due to the connection with Cartan matrices?). But what's in a name...? 
(At least Chebyshev is in the references and some of the comments for 
A034807, as well as Cartan matrices.) There is a difference of signs between the polynomials 
here (which I would call Chebyshev!) and the Lucas polynomials defined in A114525: I don't 
know enough of the early history to know whether Lucas himself actually considered these
polynomials, or only the integer sequences defined by them for fixed arguments. But I think 
more mathematicians would use the name Chebyshev here, because of their appearance 
in the theory of orthogonal polynomials, and their widespread use in numerical analysis. 

Getting onto the mathematical content, recall that the Chebyshev polynomials of the 
1st kind, denoted T_k(n),  can be defined by the recurrence 

T_{k+2} - n T_{k+1} + T_k = 0 

with initial values T_0 = 2, T_1 = n. (This differs by some factors of 2 from the 
classical definition, cf. http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html)   

Also the Chebyshev polynomials of the 2nd kind, denoted U_k(n), are given by the same recurrence, 

U_{k+2} - n U_{k+1} + U_k = 0 

with initial values U_0 = 1, U_1 = n. (This should agree with the classical 
definition.) 

With these definitions, both T_k(n) and U_k(n) are monic polynomials of degree k in n, 
for each k=0,1,2,... .

Now (T_k), (U_k) provide two linearly independent solutions of the 
same recurrence relation, which is the same as the recurrence for (s_k) 
in the definition of A269254; this means that for each n, s_k can be 
written as a linear combination of T_k(n) and U_k(n). One can do this, by 
matching the two initial values, but one finds is that in fact the 
neatest formula is 

s_k = U_k(n) + U_{k-1}(n). 

(The sequence (U_k) and its shift (U_{k-1}) are linearly independent, so 
also provide a basis for the solutions of the recurrence.)  

Before proceeding, it is helpful to recall an alternative way to 
define Chebyshev polynomials, via sine and cosine. Pick z (in 
general it will be a complex number) such that the argument n 
is given by 

n = 2 cos(z). 

Then T_k and U_k are defined for all integer k by 

T_k( 2 cos(z) ) = 2 cos(kz), 

U_k( 2 cos(z) ) = sin((k+1)z) / sin(z). 

A list a few Chebyshev polynomials of the 1st kind, but with
j denoting the argument instead of n, is as follows: 

T_0(j) = 2, T_1(j) = j, T_2(j) = j^2 -2, T_3(j) = j^3 - 3j, T_4(j) = (j^2-2)^2 - 2, 
T_5(j) = j^5 - 5j^3 + 5j, T_6 = ... , T_7(j) = j^7 - 7 j^5 + 14 j^3 - 7j, ... 

(Hopefully I didn't make any mistakes.) The point of giving this list is partly to 
show the choice of normalization, but also because T_2, T_3, T_4, T_5 have already 
cropped up in the discussion so far.

The way I have written T_4 is to illustrate the well known 
property 

T_{ab}(j) = T_a(T_b(j)), 

which follows immediately from the definition in terms of cosine.

My assertion is that all the cases with a_n = -1 belong to values of n 
which take the form 

n = T_p(j)

for suitable integers j, and because of the above property of these 
polynomials, it is sufficient to consider this formula with p prime only, 
since values of n arising from composite values of p already appear in the 
list corresponding to their smallest prime factor. This agrees with earlier 
suggestions of Bob Selcoe, and e.g. the comment in the last post of Hans Havermann 
in which he says that T_4 generates duplicates of values obtained from T_2. 

Now I'd like to indicate how properties of Chebyshev can be used to give 
simple proofs that a_n = -1 in the relevant cases. This is not yet a 
complete argument, as I have only just started thinking about the 
problem this way, but I think it should be possible to extend it to 
all primes p. 

As a start in this direction, let me explain a shorter way to prove the 
case p = 2, which is the result of Brad Klee about factorization when 

n = T_2(j) = j^2 -2. 

We need to show that s_k = s_k(n) factorizes when n = j^2 - 2. I claim that 
this reduces to the following explicit identity for Chebyshev polynomials: 

U_k(T_2(j)) + U_{k-1}(T_2(j)) = ( U_k(j) + U_{k-1}(j) ) ( U_k(j) - U_{k-1}(j) ). 

(The form of this identity looks consistent with some observations Bob Selcoe 
has shared with me off-list, in which he has noticed a link to values of Chebyshev 
polynomials in the OEIS, related to Brad Klee's factorization.) 

The above identity holds for all values of index k and argument j. The LHS is just the 
formula for s_k when n = j^2 - 2, while the RHS is the factorization of the 
sequence into a product of a pair of sequences (denoted by L_k / R_k in Brad's 
proof) each of which satisfies the same 2nd order recurrence. So to prove the 
factorization property, we just need to verify the above identity, and this 
can be done easily using trigonometric formulae. If we set 

j = 2 cos(w), 

so that n = 2 cos(z) = 2 cos(2w), then the LHS is 

( sin(2(k+1)w) + sin(2kw) ) / sin(2w) = sin((2k+1)w) / sin(w) 

(by using the formula for sin(a) + sin(b) and double angle for sine), 

while the left factor on the RHS is 

( sin((k+1)w) + sin(kw) ) / sin(w) = 2 sin((k+1/2)w) cos(w/2) / sin(w),  

and the right factor on the RHS is 

( sin((k+1)w) - sin(kw) ) / sin(w) = 2 cos((k+1/2)w) sin(w/2) / sin(w),  

so combining these two factors and using double angle twice more (but 
in the reverse direction) we immediately obtain LHS = RHS. 

The next step is to generalize this to the case p=3, to get a simpler 
proof than the one I gave for the factorization when 

n = T_3(j) = j^3 - 3j,
 
and to see how this should be extended to other primes p. 

All the best,
Andy 


________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Bob Selcoe [rselcoe at entouchonline.net]
Sent: 26 October 2017 18:50
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: A269254 and A034807

>>>Do we have a fourth, fifth, etc. here that will impact our number range?

My guess is no, using rows in A034807 as a basis.

We need only consider:

1.   m >=3, and
2.   prime rows, since composite rows repeat terms generated in earlier
rows.

Rows 2, 3 and 5 have been evaluated; 7th row only possible term is 843, but
a(843) = 3; all other rows >= 11 generate terms > 10000.

Cheers,
Bob Selcoe

--------------------------------------------------
From: "Hans Havermann" <gladhobo at bell.net>
Sent: Thursday, October 26, 2017 4:32 AM
To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: A269254 and A034807

> To summarize, if I wanted values up to 10000 that are known -1s:
>
> First: (7, 14, 23, 34, 47, 62, 79, 98, 119, 142, 167, 194, 223, 254, 287,
> 322, 359, 398, 439, 482, 527, 574, 623, 674, 727, 782, 839, 898, 959,
> 1022, 1087, 1154, 1223, 1294, 1367, 1442, 1519, 1598, 1679, 1762, 1847,
> 1934, 2023, 2114, 2207, 2302, 2399, 2498, 2599, 2702, 2807, 2914, 3023,
> 3134, 3247, 3362, 3479, 3598, 3719, 3842, 3967, 4094, 4223, 4354, 4487,
> 4622, 4759, 4898, 5039, 5182, 5327, 5474, 5623, 5774, 5927, 6082, 6239,
> 6398, 6559, 6722, 6887, 7054, 7223, 7394, 7567, 7742, 7919, 8098, 8279,
> 8462, 8647, 8834, 9023, 9214, 9407, 9602, 9799, 9998) because they belong
> to m^2-2.
>
> Second: (110, 322, 488, 702, 1298, 2158, 2702, 4862, 7940), excluding
> (322, 2702) already in first, because they belong to m^3-3*m, where m+1 is
> not prime.
>
> The case of m^4-4*m^2+2 creates only duplicates in first.
>
> Third: (123, 2525) because they belong to m^5-5*m^3+5*m, where m^2+m-1 is
> not prime.
>
> That's 107 values so far. Do we have a fourth, fifth, etc. here that will
> impact our number range?
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>

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