# The second moment and fourth moment of $\mathcal{P}(V)$?

Backgroud: I am reading the paper "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures". (here is the link). And I got stuck in understanding the computation of moment.

Question statement: In section 4.3 of the paper, It defined: For any $$V=[\mathbf{v}_1,\cdots,\mathbf{v}_n] \in GL_n(\mathbb{R})$$ and any integer $$k \ge 1$$, the $$k$$-th moment of $$\mathcal{P}(V)$$ over a vector $$\mathbf{w} \in \mathbb{R}^n$$ is $$\text{mom}_{V,k}(\mathbf{w}) = \mathbb{E}[\langle\mathbf{u},\mathbf{w}\rangle ^k]$$ where $$\mathbf{u}$$ is uniformly distributed over the parallelepiped $$\mathcal{P}(V)$$.
Then authors said a straightforward calculation shows that for any $$\mathbf{w} \in \mathbb{R}^n$$, second moments and fourth moments are $$\text{mom}_{V,2}(\mathbf{w}) = \frac{1}{3}\sum_{i=1}^{n} \langle \mathbf{v}_i,\mathbf{w}\rangle^2 =\frac{1}{3}\mathbf{w}V^tV\mathbf{w}^t$$

$$\text{mom}_{V,4}(\mathbf{w}) = \frac{1}{5}\sum_{i=1}^{n} \langle \mathbf{v}_i,\mathbf{w}\rangle^4 + \frac{1}{3}\sum_{i \neq j} \langle \mathbf{v}_i,\mathbf{w}\rangle^2 \langle \mathbf{v}_j,\mathbf{w}\rangle^2$$

But it seems not such straightforward for me... I have trouble in understanding the calculation of these second and fourth moments.

My effort: For second moment, by the definition, we have $$\text{mom}_{V,2} = \mathbb{E}[\langle\mathbf{u},\mathbf{w}\rangle ^2] = \int \langle\mathbf{u},\mathbf{w}\rangle ^2 f(\mathbf{u}) \text{d}\mathbf{u} = \frac{1}{|\mathcal{P}(V)|} \int \langle\mathbf{u},\mathbf{w}\rangle ^2 \text{d}\mathbf{u}$$

the last equality is because $$\mathbf{u}$$ is uniformly distributed over the parallelepiped $$\mathcal{P}(V)$$. Now I can't move forward. The same is fourth moments.

• The notation looked annoyingly like exponential function, but I believe it is the expectation operator. Feel free to undo if I misinterpreted Apr 28 at 12:26
• @kodlu, yes ,it is expectation operator, the original paper used Exp notation so I copied here. The notation you edited makes it more clear.
– zbo
Apr 28 at 13:22

It's instructive to look at the proof of Lemma 1 where $$\mathbf v$$ is rewritten $$\mathbf u=\mathbf xV$$ where $$\mathbf x$$ is a uniform sample from $$[-1,1]^n$$. Thus $$\mathbb E(\langle \mathbf u,\mathbf w\rangle^2)=\mathbb E_{\mathbf u}(\mathbf w\mathbf u^T\mathbf u\mathbf w^T)=\mathbf wV^T\mathbb E_{\mathbf x}(\mathbf x^T\mathbf x)V\mathbf w^T.$$

The expectation of $$\mathbf x^T\mathbf x$$ is the covariance matrix of $$n$$ i.i.d. uniform random variables on $$[-1,1]$$. Independence means that the off-diagonal terms are 0 and that the diagonal terms are $$\mathbb E(X^2)=\frac12\int_{-1}^1t^2dt=\frac 13$$ where $$X$$ is a random variable uniformly distributed on $$[-1,1]$$. So that $$\mathbb E_{\mathbf x}(\mathbf x^T\mathbf x)=\frac13 I_n$$ and so $$\mathbb E(\langle \mathbf u,\mathbf w\rangle^2)=\frac13\mathbf wV^TV\mathbf w^T$$ as claimed.

I haven't fully expanded out the 4th moment, but again the terms will be integrals products of i.i.d. random variables $$X_iX_jX_kX_\ell$$ uniform on $$[-1,1]$$. Terms where any variable is represented to an odd power will be zero which only leaves terms $$X_i^4$$ and $$X_i^2X_j^2$$ with $$i\neq j$$. These should correspond to the two sums.

• Got this! I am trying to find the relation of $\text{mom}_{V,2}(\mathbf{w})$ and $\frac{1}{3}\sum_{i=1}^{n} \langle \mathbf{v}_i,\mathbf{w}\rangle^2$ first. Then try to find the relation of $\frac{1}{3}\sum_{i=1}^{n} \langle \mathbf{v}_i,\mathbf{w}\rangle^2$ and $\frac{1}{3}\mathbf{w}V^tV\mathbf{w}^t$.
– zbo
Apr 29 at 6:59
• But it seems the relation should be $\mathbf{w}V^tV\mathbf{w}^t$ = $(\sum_{i=1}^{n} \langle \mathbf{v}_i,\mathbf{w}\rangle)^2$. That is $\mathbf{w}V^tV\mathbf{w}^t = (w_1,\cdots, w_n)(\mathbf{v}_1^t,\cdots,\mathbf{v}_n^t)^t(\mathbf{v}_1,\cdots,\mathbf{v}_n)(w_1,\cdots,w_n)^t = (w_1\mathbf{v}_1^T+\cdots+w_n\mathbf{v}_n^t) (\mathbf{v}_1w_1+\cdots+\mathbf{v}_nw_n) =(\sum_{i=1}^{n} \langle \mathbf{v}_i,\mathbf{w}\rangle)^2$.
– zbo
Apr 29 at 7:07
• Please corret me if am wrong.
– zbo
Apr 29 at 7:08
• It seems another question. Should I put this in the question body?
– zbo
Apr 29 at 7:10
• My mistake. The authors said Vectors of $\mathbb{R}^n$ will be row vectors denoted by bold lowercase letters. I think they are trying to let $V$ be form of row vectors $\mathbf{v}_1,\cdots, \mathbf{v}_n$. So $V^TV = \mathbf{v}_1^T\mathbf{v}_1+\cdots+\mathbf{v}_n^T\mathbf{v}_n$
– zbo
May 5 at 2:44