Expansion factor of a ring R

Question

On page 8 of this cryptography paper BGV, they defined the expansion factor of a ring R, $\gamma_R$, to be max$\{\|a \cdot b\|/\|a\|\|b\|:a,b \in R\}$. For $R=\mathbb{Z}[x]/(x^d+1)$, the norm $\|r\|$ for $r \in R$ is the Euclidean norm of the coefficient vector of $r$. Why is $\gamma_R$ at most $\sqrt{d}$ by Cauchy-Schwarz? To me it seems $\gamma_R$ should be at most 1 since $\gamma_R = \|r_1 \cdot r_2\|/\|r_1\|\|r_2\|$ for some $r_1,r_2 \in R.$ Then Cauchy-Schwarz says $\|r_1 \cdot r_2\| \le \|r_1\|\|r_2\|$. So $\gamma_R \le \|r_1\|\|r_2\|/\|r_1\|\|r_2\| = 1.$

Answer 1

You should have made an attempt to define your notations here, rather than using a link. Anyhow, suppose $a=\sum\limits_{i=0}^{d-1}\,a_i\,x^i$ and $b=\sum\limits_{i=0}^{d-1}\,b_i\,x^i$. Then, $a\cdot b=\sum\limits_{i=0}^{d-1}\,\left(\sum\limits_{j=0}^{d-1}\,a_{j}b_{i-j}\right)\,x^i$, where $b_{-\mu}:=-b_{d-\mu}$ for all $\mu=1,2,\ldots,d-1$. Therefore, $$\|a\cdot b\|=\sqrt{\sum_{i=0}^{d-1}\,\left(\sum_{j=0}^{d-1}\,a_jb_{i-j}\right)^2}\leq \sqrt{\sum_{i=0}^{d-1}\,\left(\sum_{j=0}^{d-1}\,a_j^2\right)\left(\sum_{j=0}^{d-1}\,b_{i-j}^2\right)}$$ by the Cauchy-Schwarz Inequality. Thus, $$\|a\cdot b\|\leq \sqrt{\sum_{i=0}^{d-1}\,\|a\|^2\,\|b\|^2}=\sqrt{d}\,\|a\|\,\|b\|\,.$$

Answer 2

In this cryptography paper [BFV][1], they defined the expansion factor of a ring R, ${{\delta }_{R}}$,to be ${{\delta }_{R}}\text{=}\max \{\frac{\left\| a\cdot b \right\|}{\left\| a \right\|\cdot \left\| b \right\|}:a,b\in R\}$. For $R=Z[x]/{{x}^{d}}+1$, the norm $\|a \|$ for $a\in R$ is the infinity norm of the coefficient vector of a. Why is the boundary of the element on R multiplied by the expansion factor after the multiplication operation? [See this picture][2] on page 6 of the paper or other parts of the paper, why is the final boundary multiplied by ${{\delta }_{R}}$? What is the role of the expansion factor? And is ${{\delta }_{R}}$ always less than 1?