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$?


1 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.

  • $\begingroup$ why should we assume l is unary? $\endgroup$
    – Kaveh
    Commented Jun 5, 2017 at 20:05
  • $\begingroup$ good point. It seems that the interesting case would be inputs of the form $(1^d,l)$, where $l$ is given in binary and $d<<l$ (say $d\approx\log l)$. $\endgroup$
    – Ariel
    Commented Jun 5, 2017 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.