New twist(?) on old point-counting problem

[Jonathan Post]

Thank you, Richard Mathar, for both getting to the underlying Math, and
crossreferencing usefully to OEIS.  I'm still only halfway clear on this.

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

First, a long-standing debate in Metamathematics is on whether or not there
are "coincidences" in mathematics. The conventional belief is: "No.  There
are just connections that you don't see." An example came up a few years ago
with "Moonshine" -- based on someone noticing that a large number related to
the Monster Group was also in an integer sequence about lattices. Or on
geniuses like Peter Lax and Olga Taussky Todd finding deep connections
between disciplines previously thought to be unconnected.

On the other side, Gregory Chaitin insists that integers themselves are
almost all real numbers, are riddled with "coincidences" -- and provably so,
and inextricably so.  That is, most of Mathematics is true "for no reason."

I suspect that most seqfans fall somewhere in the golden mean between these
metaphysical extremes.

So, is Richard Mathar joking, or is there an even deeper connection that David
Wilson did not see, and that I still don't see?

-- Jonathan Vos Post

On 10/27/06, Richard Mathar <mathar at strw.leidenuniv.nl> wrote:
>
>
> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061027/c8fed347/attachment-0002.htm>