Question related to the 'bit size' of polynomials

Question

While reading through notes about polynomial factorization (click here for the content I'm working through), I'm a little stuck on how to understand the following statement:

Corollary 5.75 The bit size of the irreducible factors in ℚ[x] of an f(x)∈ℤ[x] with leading coefficient 1 is polynomial in the bit size of f(x).

which follows a proof on Mignotte's bound (the norm involved there is the $2$-norm:

Theorem 5.74 (Mignotte) Let us assume that the polynomials f(x),g(x)∈ℂ[x] have complex coefficients and leading coefficient 1 and that g(x)|f(x). If deg(g(x))=m, then ∥g(x)∥≤2m∥f(x)∥.

Now I'm not even sure what the definition for the bit size of a polynomial $f = \sum_i f_i x^i$ is. I didn't find one in the notes linked to.

I reckon it could be something like $$ (1 + \deg(f)) \lg(||f||_\infty) $$ or $$ \sum_{i} lg|f_i| $$

If it is the first one, I am able to find that the bit size of any irreducible factor $g$ of $f \in \mathbb{Z}[x]$ is bounded by a polynomial in that of $f$.

Using the well known relationships between the $p$-norms, we have

$$ \begin{eqnarray} & ||g||_\infty \leq ||g||_2 &\leq 2^{\deg(g)} ||f||_2 \\ \overset{\text{apply } lg_2}{\implies} & lg_2(||g||_\infty) &\leq \deg(g) + lg_2(||f||_\infty) \\ \overset{\deg(g)\leq\deg(f)}\implies & (1 + \deg(g))lg_2(||g||_\infty) &\leq (1 + \deg(f))\deg(g) + (1 + \deg(f))\lg_2 ||f||_\infty \end{eqnarray} $$

If it is the second definition (which would be more precise), then let $$ [n]:=\{1,\,\dots,\,n\} $$ and $$ f = \prod_{i \in [n]} (x - \alpha_i) $$ be the complex factorization into linear factors of $f$ and $I \subseteq [n]$ be the set with $$ g = \prod_{j \in J} (x - \alpha_j) $$

Then, one should probably consider the following statement:

Let us express the coefficients of g(x) using its roots:
$$ \begin{eqnarray} g(x) &= \prod_{i\in I} (x − \alpha_i ) = \sum_{J \subseteq I}\left((-1)^{|J|} \prod_{j \in J}\alpha_j x^{m - |J|} \right) \\ &= \sum_{i=0}^m(-1)^{m-i}\left(\sum_{J \subseteq I, |J|=m-i} \prod_{j \in J}\alpha_j\right)x^i \end{eqnarray} $$

which for $f$ would be $$ f(x) = \sum_{i=0}^n(-1)^{n-i}\left(\sum_{J \subseteq [n], |J|=n-i} \prod_{j \in J}\alpha_j\right)x^i $$

but how would one proceed, or is this even what was meant?

I would be glad if somebody could shed some light on the corollary I quoted/the definition of 'bit size' that is probably applied here and maybe tell me where I'm completely off track/ help me to make sense of this.

EDIT:
Further ahead in the notes linked to, $n\lg||f|| = n\lg||f||_2$ seems to be referred to as the bit size of $f$:

Corollary 5.77 If $f(x) \in ℤ[x]$ is a square-free polynomial with degree $n$, then there is a prime $p=O((n\lg n+2n \lg ||f||)^2)$ (that is, the absolute value of $p$ is polynomial in the bit size of $f$) such that the polynomial $f(x)( mod p)$ is square-free in $\mathbb{F}_p[x]$.

This seems unintuitive to me.
However, since $||f||_2 \leq \sqrt {\deg f + 1} ||f||_\infty$, we have $$ (\deg f + 1) lg||f||_2 \leq (\deg f + 1)\lg\sqrt {n + 1} + (\deg f + 1) \lg ||f||_\infty $$ which I find more intuitive.

Answer 1

I've found the definition as a comment after another definition, namely Definition 5.72:

Definition 5.72 The norm of a polynomial $f(x)= \sum_{i=0}^n a_ix_i \in \mathbb{C}[x]$ with complex coefficients is the real number $||f(x)||=\sqrt{\sum_{i=0}^n|ai|^2}$.

The inequality $max_{i=0}^n|a_i|\leq||f(x)||$ implies that a polynomial $f(x)$ with integer coefficients can be described using $O(n\lg||f(x)||)$ bits.