10
$\begingroup$

Let $M$ be a real symmetric integer valued positive definite matrix with $\det(M) \geq 1$. I would like write code to compute

$$S_M= \sum_{x \in \mathbb{Z}^n} e^{-x^TMx}.$$

One option is to simply iterate over the vectors $x$ starting with ones with small coefficients and stop if things seem to be converging. Apart from the obvious problem of determining when to stop, this method is tremendously slow if $M$ is even $10$ by $10$.

It is tempting to look at the integral $\int_{x \in \mathbb{R}^n} e^{-x^TMx}\;dx$ instead but this equals $\sqrt{\frac{\pi^n}{\det(M)}}$ which is potentially a terrible approximation (it can for example be much less than $1$ where $S_M \geq 1$).

How can one compute a good approximation for $S_M$? Even an algorithm that runs $2^n$ time would be a huge improvement over what I have currently.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
14
$\begingroup$

You are trying to compute a multi-dimensional theta function, and this question is studied in depth in this 2003 Math. Comp. article by Deconinck, Heil, Bobenko, van Hoeij,and Schmies.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Thank you for this. Please excuse my ignorance but would you be able explicitly to show an example? The Riemann theta function seems to require that $Im(\Omega)$ is strictly positive definite but my matrix $M$ is real. mathoverflow.net/questions/64261/… shows that there is a Maple function RiemannTheta. How would you use it in my case? Or equivalently, how would you use the Mathematica function SiegelTheta? $\endgroup$
    – Simd
    Commented Mar 20, 2016 at 21:16
  • 1
    $\begingroup$ In your case, $S_M = \Theta\left(0 \vert \tfrac{1}{\pi} i M\right)$, where $\tfrac{1}{\pi} i M$ is indeed complex symmetric with strictly positive definite imaginary part. $\endgroup$
    – Branimir Ćaćić
    Commented Mar 20, 2016 at 22:53
  • $\begingroup$ For anyone interested, I tried the code as implemented at github.com/abelfunctions/abelfunctions/wiki/Getting%20Started and it is very slow. About 10 seconds for a 9 by 9 matrix and too slow to compute for a 12 by 12 matrix. I don't know if the version implemented by Mathematica is much faster as I don't have access to it. $\endgroup$
    – Simd
    Commented Mar 31, 2016 at 6:19
  • $\begingroup$ @Lembik what was the exact code you ran? $\endgroup$
    – Igor Rivin
    Commented Mar 31, 2016 at 9:15
  • $\begingroup$ It was essentially identical to the code at github.com/abelfunctions/abelfunctions/issues/121 . $\endgroup$
    – Simd
    Commented Mar 31, 2016 at 14:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .