6
$\begingroup$

Let $M$ be an $n$ by $n$ matrix with each diagonal element equal to $k$ and each non-diagonal element equal to $k-1$ where $n$ and $k$ are positive integers. Let $k < n$ and we can assume both $k$ and $n$ are large.

What is

$$S_{M,k} = \sum_{x \in \mathbb{Z}^n} e^{-x^T M x}\;?$$

Is there some way to estimate this sum?

This was also posted to https://math.stackexchange.com/questions/1741157/how-to-estimate-a-specific-infinite-sum a few days ago.

Added examples

If $k=1$ we know $S_{M,1} \approx (\sqrt{\pi} +2\sqrt{n}e^{-\pi^2})^n \approx 1.7726372048^n$. I don't know a closed form approximation for any other value of $k$.

For $n=12$ and $k = 1, \dots, 12$ using computer code to approximate the sum we get $ 962.58329951, 267.409968069, 196.186732001, 171.404195004, 162.313077353, 158.96911585, 157.738949838, 157.286397212, 157.119912408, 157.058666071, 157.036134803, 157.027846013$.

In general it seems numerically that for every fixed $n$, $S_{M,k}$ converges fairly quickly to some value as $k$ increases towards $n$.

$\endgroup$
3
  • $\begingroup$ @AmirSagiv The sum is an instance of the Riemann Theta function which is why I added the theta-function tag. Specifically, it is $\theta(0|iM/\pi)$. $\endgroup$
    – Simd
    Apr 20, 2016 at 10:46
  • $\begingroup$ You might look at multidimensional Theta functions and references there. $\endgroup$ Apr 20, 2016 at 18:24
  • $\begingroup$ @RobertIsrael Thank you. I don't believe there exists a nice approximation for the Riemann Theta function in general but my problem has only two variables so I was hoping it might be much easier. $\endgroup$
    – Simd
    Apr 20, 2016 at 18:27

2 Answers 2

3
$\begingroup$

Let $s = k-1$, and write $x^T M x = \|x\|^2 + s (e \cdot x)^2$ where $e = (1,\ldots,1)$. Let $P_j = \{x \in \mathbb Z^n: e \cdot x = j\}$. Each $P_j$ is a translate of $P_0$, which is a subgroup of $\mathbb Z^n$. Then

$$S_{M,k} = \sum_{j\in \mathbb Z} e^{-s j^2} \sum_{x \in P_j} e^{-\|x\|^2} = \sum_{j \in \mathbb Z} e^{-s j^2} T(j)$$

where $T(j) = \sum_{x \in P_j} e^{-\|x\|^2}$. Now $P_{j+n} = e + P_j$, and if $x \in P_j$ we have $\|e + x\|^2 = n + 2 j + \|x\|^2$. Thus $$T(n+j) = e^{-n-2j} T(j)$$ so that $$T(mn + j) = e^{-m^2 n - 2 mj} T(j)$$ We just have to compute (or approximate) $T(0), \ldots, T(n-1)$, and then $$\eqalign{S_{M,k} &= \sum_{j=0}^{n-1} \sum_{m \in \mathbb Z} e^{-s(j+mn)^2} e^{-m^2n-2mj} T(j) = \sum_{j=0}^{n-1} e^{-sj^2} T(j) \sum_{m \in \mathbb Z} e^{-(n^2s+n) m(m+2j/n)}\cr &= \sum_{j=0}^{n-1} e^{-sj^2} T(j) \theta_3(i(ns+1)j, \exp(-n^2 s))} $$ where $\theta_3$ is a Jacobi theta function.

$\endgroup$
2
  • $\begingroup$ If $k=n$, how quickly does this grow with $n$? Is it exponential for example? $\endgroup$
    – Simd
    Apr 22, 2016 at 13:35
  • 2
    $\begingroup$ Note that $x^T M x = \|x\|^2$ if $e \cdot x = 0$. Let's say $n$ is even. For any $y \in \mathbb Z^{n/2}$, the vector $x = (y_1,-y_1,y_2,-y_2,\ldots,y_{n/2},-y_{n/2})$ has $x^T M x = \|x\|^2 = 2 \|y\|^2$. Thus for any $k$, $$S_{M,k} \ge \sum_{y \in \mathbb Z^{n/2}} e^{-2 \|y\|^2} = \left(\sum_{y \in \mathbb Z} e^{-2 y^2}\right)^{n/2}$$ which does grow exponentially in $n$. $\endgroup$ Apr 22, 2016 at 18:02
3
$\begingroup$

This is an optimistic approach and since it is long, I write it as an answer. First we set $$H(M,x)=\Sigma_{x\in \mathbb{Z}^n}{e^{-x^TMx}},$$ Which is your introduced summation. Let $J$ be the all one matrix with size $n$ and $I$ be the identity matrix. Since we have:$$M= kI+(k-1)(J-I),$$ we can see that the eigenvalues of the matrix $M$ are as follow: $$\lambda_1=\cdots=\lambda_{n-1}=1,\lambda_n=(n+1)(k-1).$$ Let $D={\rm diag}(\lambda_1,\lambda_2,\ldots,\lambda_n)$, which is a diagonal matrix of size $n$. Assume that $u_1,u_2,\ldots,u_n$ are the normalized eigenvectors of the later eigenvalues, respectively. Notice that you can find easily these eigenvectors in such a way that in the matrix $U=[u_1,u_2,\ldots,u_n]$, each two columns are orthogonal. By spectral decomposition, we have:$$M=U^TDU.$$ Now, we define the below summation: $$H(M,X)=\Sigma_{x_{ij}\in \mathbb{Z}}{e^{-X^TMX}},$$ where $X$ is an arbitrary integer matrix with size $n$. So, if we can estimate this summation, we can estimate an estimation for your summation. But, we have: $$H(M,X)=\Sigma_{x_{ij}\in \mathbb{Z}}{e^{-(UX)^TMUX}}=(UX)^Te^{-D}UX=e^{-\lambda_1}p_1p_1^T+\cdots+e^{-\lambda_n}p_np_n^T=\frac{1}{e}({p_1p_1^T+p_2p_2^T+\cdots+p_{n-1}p_{n-1}^T})+\frac{1}{e^{(n+1)(k-1)}}p_np_n^T,$$where in the last summation, I supposed that $UX$ is invertible, since in almost all cases it is. Note that we have $p_i=y_i^Tu_i^T$, where $X=[y_1,\ldots,y_n]^T$. Now, since you know completely the eigenvectores of $M$, by some matrix inequality and some special values of the matrix $X$, you can find a good upper bound for this summation. I think it can be seen as integer linear optimization problem.

I think this approach can be optimized. Also, maybe there are some better way by using Fourier transformation.

$\endgroup$
2
  • $\begingroup$ could you define the values $p_n$? $\endgroup$
    – Amir Sagiv
    Apr 20, 2016 at 10:46
  • 1
    $\begingroup$ @AmirSagiv: I added the definition of $p_n$. $\endgroup$
    – Shahrooz
    Apr 20, 2016 at 12:00

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.