Cómo estimar una suma infinita específica

Question

Dejemos que $M$ ser un $n$ por $n$ con cada elemento diagonal igual a $k$ y cada elemento no diagonal igual a $k-1$ donde $n$ y $k$ son enteros positivos. Sea $k < n$ y podemos suponer que ambos $k$ y $n$ son grandes.

¿Qué es?

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

¿Hay alguna forma de estimar esta suma?

Answer 1

Podemos escribir $$M=I+(k-1)ee^\top \text{ with } e=(1,\ldots,1)^\top$$ por lo que obtenemos los valores propios $$ \lambda_1=1,\ldots,\lambda_{n-1}=1,\lambda_n=n(k-1)+1$$ a los vectores propios ortonormales $$v_1,\ldots,v_n \text{ with } v_n=\frac{1}{\sqrt{n}}e\text{.}$$ Podemos escribir el término del exponente como $$x^\top Mx=x^\top x + (k-1)(x^\top e)(e^\top x)$$ Conectando el término dado $$\sum_{x\in \mathbb{Z}^n} e^{-x^\top M x} = \sum_{x\in \mathbb{Z}^n} \exp \bigl(-(\lVert x\rVert_2^2 + (k-1)(x^\top e)^2 )\bigr)$$ ahora descomponemos $\mathbb{Z}^n$ en superficies de hipercubos con ayuda de $\lVert x\rVert_\infty = \max_{i=1,\ldots,n}\lvert x_i\rvert$ .

$$\sum_{x\in \mathbb{Z}^n} e^{-x^\top M x} = e^0 + \sum_{r=1}^\infty\sum_{\stackrel{x\in \mathbb{Z}^n}{\lVert x\rVert_\infty=r}} \exp \bigl(-(\lVert x\rVert_2^2 + (k-1)(x^\top e)^2 )\bigr)\text{.}$$ Para obtener una estimación de lo anterior, utilizamos el vector propio (independiente de $k$ ) $$v=(r,-r,0,\ldots,0) \text{ with } v^\top Mv=2r^2$$ con la menor norma 2 al menor valor propio $1$ y obtener $$\sum_{x\in \mathbb{Z}^n} e^{-x^\top M x} \leq e^0 + \sum_{r=1}^\infty\Bigl\lvert\{x\in \mathbb{Z}^n\big\vert\lVert x\rVert_\infty=r\}\Bigr\rvert e^{-2r^2}\text{.}$$ El número de puntos de este conjunto es el número de puntos del hipercubo completo menos el número de puntos del hipercubo más pequeño $$\Bigl\lvert\{x\in \mathbb{Z}^n\big\vert\lVert x\rVert_\infty=r\}\Bigr\rvert=(2r+1)^n-(2(r-1)+1)^n=(2r+1)^n-(2r-1)^n$$ Por lo tanto, $$\sum_{x\in \mathbb{Z}^n} e^{-x^\top M x} \leq 1 + \sum_{r=1}^\infty \bigl((2r+1)^n-(2r-1)^n\bigr)e^{-2r^2}\text{.}$$ Del mismo modo, podemos utilizar el vector propio $$v=(r,\ldots,r) \text{ with } v^\top Mv=nr^2+(k-1)(nr)^2=nr^2(1+n(k-1))$$ con la mayor norma 2 al mayor valor propio $\lambda_n=n(k-1)+1$ para obtener una estimación de abajo $$\sum_{x\in \mathbb{Z}^n} e^{-x^\top M x} \geq 1 + \sum_{r=1}^\infty \bigl((2r+1)^n-(2r-1)^n\bigr)\exp\bigl(-nr^2(1+n(k-1))\bigr)\text{.}$$

---

Añadido: Para un límite superior utilizamos $(k-1)(x^\top e)^2 \geq 0$ para todos $x\in \mathbb{Z}^n$ junto con $\lVert x\rVert_2^2=\sum_{i=1}^n x_i^2$ y $e^{a+b}=e^a\cdot e^b$ para conseguir $$\sum_{x\in \mathbb{Z}^n} e^{-x^\top M x} \leq \sum_{x\in \mathbb{Z}^n} \prod_{i=1}^n e^{-x_i^2}=\sum_{x_1\in \mathbb{Z}} \sum_{x_2\in \mathbb{Z}}\cdots \sum_{x_n\in \mathbb{Z}}\prod_{i=1}^n e^{-x_i^2}=\sum_{x_1\in \mathbb{Z}} e^{-x_1^2} \sum_{x_2\in \mathbb{Z}}\cdots \sum_{x_n\in \mathbb{Z}}\prod_{i=2}^n e^{-x_i^2}\text{.}$$ Por lo tanto, tenemos un límite superior $$\sum_{x\in \mathbb{Z}^n} e^{-x^\top M x} \leq \Bigl(\sum_{x\in \mathbb{Z}} e^{-x^2}\Bigr)^n$$ Y con la ayuda de esta respuesta obtenemos $$\sum_{x\in \mathbb{Z}^n} e^{-x^\top M x} \leq \Bigl(\sqrt{\pi}+2\sqrt{\pi}\sum_{m=1}^{\infty}\exp(-m^2\pi^2) \Bigr)^n\text{.}$$ La estimación es de nuevo independiente de $k$ pero debe ser nítida/exacta para $k=1$ . ( $k=1\Rightarrow M=I$ )

Answer 2

Podemos observar dos enfoques.

1,Matriz de transformación

La matriz $M$ puede transformarse como se indica a continuación:

$$ M=E+(k-1)\mathbf{11^{\text{T}}} $$

donde, $E\in\mathbf{R}^{n\times n}$ es una matriz idéntica y $\mathbf{1}\in\mathbf{R}^n$ es un vector único. Por lo tanto la forma cuadrática puede ser calculada siguiendo la operación:

$$ \begin{aligned} \mathbf{x^{\text{T}}}M\mathbf{x}=& \mathbf{x^{\text{T}}}(E+(k-1)\mathbf{11^{\text{T}}})\mathbf{x} \\ =& \mathbf{x^{\text{T}}}E\mathbf{x}+(k-1)\mathbf{x^{\text{T}}}(\mathbf{11^{\text{T}}})\mathbf{x} \\ =& \mathbf{x^{\text{T}}}\mathbf{x}+(k-1)(\mathbf{x^{\text{T}}1})^2 \\ =& \|\mathbf{x}\|^2+n^2(k-1)\bar{\mathbf{x}}^2 \end{aligned} $$

donde, $\bar{\mathbf{x}}$ es el valor medio descrito del vector $\mathbf{x}$ .

2,Descomposición de la matriz

La matriz $M$ también puede descomponerse como sigue:

$$ M=P^{\text{T}}DP $$

donde la matriz $P\in\mathbf{R}^{(n+1)\times n}$ y la matriz diagonal $D\in\mathbf{R}^{(n+1)\times(n+1)}$ están abajo:

$$ \begin{aligned} &P_{ij}= \begin{aligned} \begin{cases} -1 & (i=j) \\ 1 & (i=n+1) \\ 0 & (\text{otherwise}) \end{cases} \end{aligned} \\ \\ &D_{ij}= \begin{aligned} \begin{cases} 1 & (i=j\neq n+1) \\ k-1 & (i=j=n+1) \\ 0 & (\text{otherwise}) \end{cases} \end{aligned} \end{aligned} $$

Por lo tanto, se puede calcular la forma cuadrática:

$$ \begin{aligned} \mathbf{x^{\text{T}}}M\mathbf{x}=& \mathbf{x^{\text{T}}}P^{\text{T}}DP\mathbf{x} \\ =& \mathbf{y^{\text{T}}}D\mathbf{y} \\ =& \mathbf{x^{\text{T}}}\mathbf{x}+(k-1)(\mathbf{x^{\text{T}}1})^2 \\ =& \|\mathbf{x}\|^2+n^2(k-1)\bar{\mathbf{x}}^2 \end{aligned} $$

donde, $\mathbf{y^{\text{T}}}=[-\mathbf{x^{\text{T}}} \ \ (\mathbf{x^{\text{T}}1})]\in\mathbf{R}^{n+1}$ .

En total

La suma puede simplificarse como sigue:

$$ \sum_{\mathbf{x}\in\mathbf{Z}^n} e^{-\mathbf{x^{\text{T}}}M\mathbf{x}}= \exp(-\|\mathbf{x}\|^2-n^2(k-1)\bar{\mathbf{x}}^2) $$

Cuando el tamaño $n$ se acerca al infinito, la suma converge a cero excepto $\mathbf{x}=\mathbf{0}$ . Porque la forma cuadrática es una función definitiva positiva:

$$ \mathbf{x^{\text{T}}}M\mathbf{x}=\|\mathbf{x}\|^2+n^2(k-1)\bar{\mathbf{x}}^2>0 \ \ \ (\mathbf{x}\neq\mathbf{0} \ \text{and} \ 0<k<n) $$

Aunque, al realizar este cálculo, es posible obtener un valor finito aunque $n$ es enorme. Entonces, $\mathbf{x}$ debe mantener dos condiciones. La primera propiedad es $\bar{\mathbf{x}}=0$ y la segunda es que $\mathbf{x}$ es un vector disperso (que incluye una gran cantidad de ceros).