# Coefficient Growth

In this survey, I don't understand the necessary of coefficient (paragraph 4.1.2) growth and the choice of $$X^d\pm 1$$ or $$X^d \pm X^{d/2} +1$$, since later introduces $$q$$ which doesn't mention the coefficient growth. I want to understand this paragraph please and its importance.

• Would you elaborate your question, especially "q"? Also please consider summerize the section from the book here instead of asking to read it. Thanks. Sep 15, 2022 at 17:58
• I don't see any mention of $q$ in section 4.1.2. $\mathcal{R}_{q,f}$ is introduced in the next section which is just the polynomial ring $\mathbb{Z}_q[x]/f(x)$. The ring of polynomials in $x$ with coefficients mod $q$ quotiented by a polynomial $f(x)$
– Lev
Sep 15, 2022 at 22:34

The goal here is that for any two polynomials $$a(X),b(X)\in \mathcal R_f:=\mathbb Z[X]/f(X)$$ should have a product whose coefficients are controlled as well as possible in absolute size by the absolute size of the coefficients of $$a$$ and $$b$$. This should mean that the products of polynomials with very small coefficients relative to $$q$$ will themselves have small-ish coefficients relative to $$q$$ and coefficient reduction modulo $$q$$ will not affect this property. We will require this property to hold for a wide range of choices of $$a$$ and $$b$$, and we want to choose a polynomial $$f(X)$$ that guarantees this for all $$a(X)$$ and $$b(X)$$.
If we look at the coefficient of $$X^{d-1}$$ in the product of $$a(X)$$ and $$b(X)$$ before reduction modulo $$f(X)$$, say $$c(X):=a(X)b(X)$$ it is given by $$c_{d-1}=\sum_{i=0}^{d-1}a_ib_{d-i-1}.$$ This is a sum of $$d$$ terms each of which is the product of two coefficients and this leads us to expect that we cannot hope to bound coefficients of the product better than $$d||a||_\infty||b||_\infty$$. Reduction modulo $$f$$ could potentially make matters worse by accumulating terms and scaling by integer multiples. We can make this feeling more precise by writing out the effect of multiplication by $$a\mod f$$ as matrix which acts on the coefficients of $$b$$ and this is what the paper does.
The best cases are when a) $$f(X)=X^d-1$$ when the general coefficient for the $$j$$th term of the product is $$c_j=\sum_{i=0}^{d-1}a_ib_{j-i\mod d},$$ which matches our naive bound before reduction, or b) when $$f(X)=X^d+1$$ when the general coefficient for the $$j$$th term of the product is $$c_j=\sum_{i=0}^{j}a_ib_{j-i}-\sum_{i=j+1}^{d-1}a_ib_{j+d-1-i},$$ again matching our naive bound before reduction in absolute value, or c) when $$f(X)=X^d$$ when the general coefficient for the $$j$$th term of the product is $$c_j=\sum_{i=0}^{j}a_ib_{j-i}$$ matching our naive bound before reduction in absolute value when $$j=d-1$$, but which is very bad choice for other reasons. For any other choice of $$f(X)$$ there will be a coefficient expression where the number of terms in the sum is greater than $$d$$ or where part of the sum is scaled by a coefficient of $$f(X)$$ that is greater than 1 in absolute value.
Polynomials of the form $$f(X)= 𝑋^𝑑\pm X^{𝑑/2}\pm 1$$ create coefficient expressions which are the sum of at most $$2d$$ terms which leads to a slightly poorer bound.