[seqfan] A269254, A034807 and Chebyshev polynomials

Andrew N W Hone A.N.W.Hone at kent.ac.uk
Fri Oct 27 08:37:41 CEST 2017

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/