系数增长

Question

在这个调查中，我不明白系数增长的必要性(第4.1.2段)和X^d\pm 1 或X^d \pm X^{d/2} +1 的选择，因为后来引入了没有提到系数增长的q。我想理解这一段及其重要性。

提前感谢

Answer 1

这里的目标是，对于任意两个多项式，a(X),b(X)\in \mathcal R_f:=\mathbb Z[X]/f(X)应该有一个乘积，其系数在绝对大小上尽可能地由a和b系数的绝对大小来控制。这意味着相对于q的系数很小的多项式的乘积本身相对于q有较小的ish系数，而系数约简模q不影响这一性质。对于a和b的广泛选择，我们将要求该属性保持不变，并且我们希望选择一个多项式f(X)，以保证所有a(X)和b(X)都能这样做。

如果我们看X^{d-1}系数在a(X)和b(X)的乘积中的约化模f(X)，比如说c(X):=a(X)b(X)，它是由c_{d-1}=\sum_{i=0}^{d-1}a_ib_{d-i-1}.给出的，这是一个d项的和，每个项都是两个系数的乘积，这使得我们不能期望这个积的定界系数比d||a||_\infty||b||_\infty更好。缩减模f可能会通过累积项和整数倍数来使事情变得更糟。我们可以用a\mod f作为矩阵来写出乘法的效果，从而使这种感觉更加精确，而这正是本文所做的。

最好的情况是: a)当乘积的一般系数为f(X)=X^d-1时，产品的j第四项的一般系数为c_j=\sum_{i=0}^{d-1}a_ib_{j-i\mod d},，它与我们的朴素界在还原前相匹配；b)当f(X)=X^d+1时，产品的j第四项的一般系数是c_j=\sum_{i=0}^{j}a_ib_{j-i}-\sum_{i=j+1}^{d-1}a_ib_{j+d-1-i},，在绝对值约简前再匹配我们的朴素界；或c)当产品的j第四项的一般系数是c_j=\sum_{i=0}^{j}a_ib_{j-i}时，当j=d-1的绝对值降低之前，f(X)=X^d与我们的朴素界相匹配，但由于其他原因，这是非常糟糕的选择。对于任何其他选择的f(X)，将有一个系数表达式，其中之和中的项数大于d，或者部分和被绝对值大于1的f(X)系数缩放。

形式f(X)= ^\pm X^{/2}\pm 1的多项式产生系数表达式，它最多是2d项的和，这导致了一个稍差的界。