New twist(?) on old point-counting problem

[Richard Mathar]

dw> From seqfan-owner at ext.jussieu.fr  Fri Oct 27 17:50:54 2006
dw> From: "David Wilson" <davidwwilson at comcast.net>
dw> To: "Sequence Fans" <seqfan at ext.jussieu.fr>
dw> Subject: New twist(?) on old point-counting problem
dw> 
dw> (Best viewed in fixed width)
dw> 
dw> Let f be defined as
dw> 
dw> f(x, y) = 
dw>     0, if y > x
dw>     1, if y = 0
dw>     2*SUM(k >= 1 and x-k^2 >= y; f(x-k^2, y-1)), otherwise.
dw> ...
dw> Now use the xth row of this table as differences to generate sequence S_x. For example, taking x = 3, the third row is (1 2 4 8). Using these as differences, we generate the sequence:
dw> 
dw>                   8     8     8    ...
dw>                4    12    20    28    ...
dw>             2     6    18    38    66    ...
dw>    S_3 = 1     3     9    27    65    131   ...
dw> 
dw> S_3 is indexed starting at 0.
dw> 
dw> It appears that S_x(n) gives the number of points in Z^n with norm <= sqrt(x). For example, there are S_3(4) = 65 points of Z^4 norm <= sqrt(3), namely:

For n=2 the sequence is A057655, for n=3 A117609, for n=4 A046895.
Associated are A005408, A058331, A055426
(if the roles of x and n are interchanged in being the major/minor index).

Indeed, miracously, this backward difference scheme seems also to work for S_4(x):

    16  16 16 16  16               <= this now 2^4 instead of 2^3
   8  24 40  56 72  88
  4  12 36 76 132 204 292 ..
 4 8  20 56 132 264 468 760 ..
1 5 13 33 89 221 485 953 1713 ..  <= these as given below

One can write the interior points in Z^n in the generalized spherical coordinates,
x[0]= r cos(phi0)*cos(phi1)*....cos(phin_3)*cos(phin_2)*cos(phin_1)
x[2]= r cos(phi0)*cos(phi1)*....cos(phin_3)*cos(phin_2)*sin(phin_1)
x[3]= r cos(phi0)*cos(phi1)*....cos(phin_3)*sin(phin_2)
...
So the restriction to a maximum radius "r" means that one can count the
number of combinations of angles phi0 up to phin_1 which have an integer
representation of these trigonometric products. This might be helpful to
get a recursion that builds these finite differences and proves this
nosliw observation.

S_1(1)=3
S_2(1)=3
S_3(1)=3
S_4(1)=5
S_5(1)=5
S_6(1)=5
S_7(1)=5
S_8(1)=5

S_1(2)=5
S_2(2)=9
S_3(2)=9
S_4(2)=13
S_5(2)=21
S_6(2)=21
S_7(2)=21
S_8(2)=25

S_1(3)=7
S_2(3)=19
S_3(3)=27
S_4(3)=33
S_5(3)=57
S_6(3)=81
S_7(3)=81
S_8(3)=93

S_1(4)=9
S_2(4)=33
S_3(4)=65
S_4(4)=89
S_5(4)=137
S_6(4)=233
S_7(4)=297
S_8(4)=321

S_1(5)=11
S_2(5)=51
S_3(5)=131
S_4(5)=221
S_5(5)=333
S_6(5)=573
S_7(5)=893
S_8(5)=1093

S_1(6)=13
S_2(6)=73
S_3(6)=233
S_4(6)=485
S_5(6)=797
S_6(6)=1341
S_7(6)=2301
S_8(6)=3321

S_1(7)=15
S_2(7)=99
S_3(7)=379
S_4(7)=953
S_5(7)=1793
S_6(7)=3081
S_7(7)=5449
S_8(7)=8893

S_1(8)=17
S_2(8)=129
S_3(8)=577
S_4(8)=1713
S_5(8)=3729
S_6(8)=6865
S_7(8)=12369
S_8(8)=21697


S_1(1)=3
S_1(2)=5
S_1(3)=7
S_1(4)=9
S_1(5)=11
S_1(6)=13
S_1(7)=15
S_1(8)=17

S_2(1)=3
S_2(2)=9
S_2(3)=19
S_2(4)=33
S_2(5)=51
S_2(6)=73
S_2(7)=99
S_2(8)=129

S_3(1)=3
S_3(2)=9
S_3(3)=27
S_3(4)=65
S_3(5)=131
S_3(6)=233
S_3(7)=379
S_3(8)=577

S_4(1)=5
S_4(2)=13
S_4(3)=33
S_4(4)=89
S_4(5)=221
S_4(6)=485
S_4(7)=953
S_4(8)=1713

S_5(1)=5
S_5(2)=21
S_5(3)=57
S_5(4)=137
S_5(5)=333
S_5(6)=797
S_5(7)=1793
S_5(8)=3729

In Maple:

CountLessSph := proc(dim,radsquared)
	local i,cnts ;
	cnts := 0 ;
	for i from -trunc(sqrt(radsquared)) to trunc(sqrt(radsquared)) do
		if radsquared-i^2 >= 0 then
			if dim > 1 then
				cnts := cnts+CountLessSph(dim-1,radsquared-i^2) ;
			else
				cnts := cnts+1 ;
			fi ;
		fi ;
	od ;
	RETURN(cnts) ;
end:

for dim from 1 to 8 do
	for rads from 1 to 8 do
		printf("S_%d(%d)=%d\n",rads,dim,CountLessSph(dim,rads)) ;
	od ;
od ;

--Richard