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.

$\endgroup$

1 Answer 1

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.

$\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
    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$ 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
    Mar 31, 2016 at 6:19
  • $\begingroup$ @Lembik what was the exact code you ran? $\endgroup$
    – Igor Rivin
    Mar 31, 2016 at 9:15
  • $\begingroup$ It was essentially identical to the code at github.com/abelfunctions/abelfunctions/issues/121 . $\endgroup$
    – Simd
    Mar 31, 2016 at 14:58

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.