Number of grid points in d-dimensional sphere of radius r

Question

Given integers $d$ and $l$, compute the number of grid points $x \in N^d$ that satisfy $\sum_i x_i^2 \leq l$ (i.e. $||x||_2^2 \leq l$). (Think of $l$ as $r^2$).

The problem is obviously in #P. Is it in P or a smaller class? What if in place of $l_2$ we use $l_p$?

Answer 1

I'll assume $l,d$ are given in unary, otherwise the problem has a trivial exponential lower bound as the number of solutions can be $\Omega(2^d)$, e.g. in the case of $l=d$, each entry could be zero or one.

If we are given $1^l,1^d$, then this can be solved in polynomial time. Suppose $d=2^k$ (this will simplify things), and let $A(d,l)$ be the recursive algorithm for counting the number of solutions which is defined as follows:

$A(d,l)=\sum\limits_{l'=0}^l A\left(\frac{d}{2},l'\right)A\left(\frac{d}{2},l-l'\right)$

I'm pretty sure $A$ can be made to run in polynomial time using memoization, by keeping a $d\times l$ size table of the values we computed so far.