Explanation of A123937

[David Wilson]

This is a hurried attempt to provide background on the genesis of A123937.  I am sure that a most of what I write here is a poor rehash of basic theory, and this whole post probably equates to a few lines of generating function theory.

For d and n in Z+, let A_d(n) be the set of integer points on the d-sphere of radius sqrt(n) centered at the origin, that is:

    [1] a_d(n) = #({P in Z^d : |P|^2 = n}).

A table of a_d(n) for a few small values of d and n:

Table of a_d(n)

 \d|  0    1    2    3    4    5     6     7      8      9      10
 n\|
---+--------------------------------------------------------------
 0 |  1    1    1    1    1    1     1     1      1      1       1
 1 |  0    2    4    6    8   10    12    14     16     18      20
 2 |  0    0    4   12   24   40    60    84    112    144     180
 3 |  0    0    0    8   32   80   160   280    448    672     960
 4 |  0    2    4    6   24   90   252   574   1136   2034    3380
 5 |  0    0    8   24   48  112   312   840   2016   4320    8424
 6 |  0    0    0   24   96  240   544  1288   3136   7392   16320
 7 |  0    0    0    0   64  320   960  2368   5504  12672   28800
 8 |  0    0    4   12   24  200  1020  3444   9328  22608   52020
 9 |  0    2    4   30  104  250   876  3542  12112  34802   88660
10 |  0    0    8   24  144  560  1560  4424  14112  44640  129064

Each sequence a_d is a column of this table. All of these column sequences already exist in the OEIS.

It turns out that a_d can be gotten by convolving the sequence j = (1,2,0,0,2,...) = A000122 d times with the convolutional identity sequence e = (1,0,0,0,0,...) = A000007. We could say that a_d = j^d as a "convolutional power".

The generating function of a_d is t(x)^d where t is the generating function of j. t turns out to be the Jacobi theta function theta_3, as noted on A000122. If we apply the finite difference transform to the sequence of generating functions {t(x)^d}, we obtain the sequence {(t(x)-1)^d}. Expanding these functions back to sequences gives the sequence of sequences {b_d} where b_d = (j-e)^d as a convolutional power. This allows us to constuct a table of b_d:

Table of b_d(n)

 \d|  0    1    2    3    4    5    6    7    8    9    10
 n\|
---+------------------------------------------------------
 0 |  1    0    0    0    0    0    0    0    0    0     0
 1 |  0    2    0    0    0    0    0    0    0    0     0
 2 |  0    0    4    0    0    0    0    0    0    0     0
 3 |  0    0    0    8    0    0    0    0    0    0     0
 4 |  0    2    0    0   16    0    0    0    0    0     0
 5 |  0    0    8    0    0   32    0    0    0    0     0
 6 |  0    0    0   24    0    0   64    0    0    0     0
 7 |  0    0    0    0   64    0    0  128    0    0     0
 8 |  0    0    4    0    0  160    0    0  256    0     0
 9 |  0    2    0   24    0    0  384    0    0  512     0
10 |  0    0    8    0   96    0    0  896    0    0  1024

It turns out that the process we used to get from the a_d table to the b_d table, namely, converting columns of a_d to generating functions, applying the finite difference transform to the gf's, and expanding the resulting functions back to columns of b_d, is the same as applying the finite difference transform to the rows of the a_d table to obtain rows of the b_d table.

An inductive proof starting with b_d = (j-e)^d where j-e = (0,2,0,0,2,...) shows that b_d(d) = 2^d and b_d(n) = 0 for n < d. This means that the nth element of the nth row of the b_d table is the last nonzero element in that row, which in turn implies that the nth row of the a_d table, that is, the number of integer points P with |P|^2 = n, is a polynomial of degree n in d.

If, instead of [1], we had started with

    [1] a_d'(n) = #({P in Z^d : |P|^2 <= n})

which counts points inside as well as on the d-sphere, the nth row of a_d' table would be gotten by adding termwise the rows 0 through n of the a_d table. The sequence a_d' has generating function t(x)^d/(1-x). Similarly, the nth row of the corresponding b_d' table is the sum of rows 0 through n of the b_d table, and sequence b_d has generating function (t(x)-1)^d)/(1-x). The table of b_d', omitting the superdiagonal zeroes, is sequence A123937.

The recurrence given in the title of A123937 follows from the relation

    b_d = (1,1,1,1,1,...) = A000012 if d = 0; (j-e) * b_{d-1}' if d >= 1.

I know this is a spotty exposition, but I'm sure the loose ends could be tied together by a real number theorist.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061109/3e347d67/attachment-0001.htm>