In algebra, a Landau–Mignotte bound (sometimes only referred to as Mignotte's bound) is one of a family of inequalities concerning a univariate integer polynomial f(x) and one of its factors h(x). A basic version states that the coefficients of h(x) are bounded independently of h(x) by an exponential expression involving only the degree and coefficients of f(x), i.e. only depending on f(x). It has applications in computer algebra where these bounds can give a priori estimates on the run time and complexity of algorithms.
Basic version For f ( x ) , h ( x ) ∈ Z [ x ] {\displaystyle f(x),h(x)\in \mathbb {Z} [x]} such that h ( x ) {\displaystyle h(x)} divides f ( x ) {\displaystyle f(x)} denote by ‖ h ‖ 1 {\displaystyle \|h\|_{1}} resp. ‖ f ‖ 1 {\displaystyle \|f\|_{1}} the sum of the absolute values of the coefficients of h ( x ) {\displaystyle h(x)} resp. f ( x ) {\displaystyle f(x)} and let n {\displaystyle n} be the degree of f ( x ) {\displaystyle f(x)} , then
‖ h ‖ 1 ≤ 2 n ‖ f ‖ 1 {\displaystyle \|h\|_{1}\leq 2^{n}\|f\|_{1}}
Notation
f , g , h ∈ C [ x ] {\displaystyle f,g,h\in \mathbb {C} [x]} will be univariate complex polynomials which later will be restricted to be integer polynomials, i.e. in Z [ x ] {\displaystyle \mathbb {Z} [x]} . Explicitly
f = ∑ i = 0 n f i x i , g = ∑ i = 0 m g i x i , h = ∑ i = 0 k h i x i . {\displaystyle f=\sum \limits _{i=0}^{n}f_{i}x^{i},\ \ \ g=\sum \limits _{i=0}^{m}g_{i}x^{i},\ \ \ h=\sum \limits _{i=0}^{k}h_{i}x^{i}.}
n , m , k {\displaystyle n,m,k} are the degrees, the leading coefficients are f n , g m , h k {\displaystyle f_{n},g_{m},h_{k}} . Define norms by considering the coefficients as vectors, explicitly
‖ f ‖ ∞ = max 0 ≤ i ≤ n | f i | , ‖ f ‖ 2 = ( ∑ i = 0 n | f i | 2 ) 1 / 2 , ‖ f ‖ 1 = ∑ i = 0 n | f i | . {\displaystyle \|f\|_{\infty }=\max _{0\leq i\leq n}|f_{i}|,\ \ \ \|f\|_{2}=\left(\sum \limits _{i=0}^{n}|f_{i}|^{2}\right)^{1/2},\ \ \ \|f\|_{1}=\sum \limits _{i=0}^{n}|f_{i}|.}
By the fundamental theorem of algebra f {\displaystyle f} has n {\displaystyle n} roots z 1 , z 2 , … , z n {\displaystyle z_{1},z_{2},\ldots ,z_{n}} (with multiplicity). Set the Mahler measure of f {\displaystyle f} to be
M ( f ) = | f n | ∏ i = 1 n max { 1 , | z i | } . {\displaystyle M(f)=|f_{n}|\prod \limits _{i=1}^{n}\max\{1,|z_{i}|\}.}
Similarly define ‖ g ‖ 2 {\displaystyle \|g\|_{2}} , M ( h ) {\displaystyle M(h)} , etc.
Landau's inequality and other basic properties Landau proved in 1905 a key inequality linking the Mahler measure of a polynomial to its Euclidean norm.
M ( f ) ≤ ‖ f ‖ 2 {\displaystyle M(f)\leq \|f\|_{2}}
In general norms obey the following inequalities
‖ f ‖ ∞ ≤ ‖ f ‖ 2 ≤ ‖ f ‖ 1 ≤ n + 1 ‖ f ‖ 2 ≤ ( n + 1 ) ‖ f ‖ ∞ . {\displaystyle \|f\|_{\infty }\leq \|f\|_{2}\leq \|f\|_{1}\leq {\sqrt {n+1}}\|f\|_{2}\leq (n+1)\|f\|_{\infty }.}
The Mahler measure satisfies M ( f ) ≥ | f n | {\displaystyle M(f)\geq |f_{n}|} which for non-trivial integer polynomials implies M ( f ) ≥ 1 {\displaystyle M(f)\geq 1} . See also Lehmer's conjecture. The Mahler measure is multiplicative, i.e. if f = g h {\displaystyle f=gh} then
M ( f ) = M ( g ) M ( h ) . {\displaystyle M(f)=M(g)M(h).}
Mignotte's bound Mignotte used Landau's inequality in 1974 to prove a basic version of the following bounds in the notation introduced above. For complex polynomials in C [ x ] {\displaystyle \mathbb {C} [x]} , if h {\displaystyle h} divides f {\displaystyle f} then
‖ h ‖ 1 ≤ 2 k M ( h ) ≤ 2 k | h k | | f n | ‖ f ‖ 2 ≤ 2 n | h k | | f n | ‖ f ‖ 2 {\displaystyle \|h\|_{1}\leq 2^{k}M(h)\leq 2^{k}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}\leq 2^{n}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}}
and individual coefficients obey the inequalities
| h i | ≤ ( k i ) M ( h ) ≤ ( k i ) | h k | | f n | ‖ f ‖ 2 ≤ ( n i ) | h k | | f n | ‖ f ‖ 2 {\displaystyle |h_{i}|\leq {\binom {k}{i}}M(h)\leq {\binom {k}{i}}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}\leq {\binom {n}{i}}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}}
If additionally f {\displaystyle f} and h {\displaystyle h} are integer polynomials in Z [ x ] {\displaystyle \mathbb {Z} [x]} then 0 < | h k | | f n | ≤ 1 {\displaystyle 0<{\frac {|h_{k}|}{|f_{n}|}}\leq 1} and if f {\displaystyle f} is additionally monic then even | h k | | f n | = 1 {\displaystyle {\frac {|h_{k}|}{|f_{n}|}}=1} . In these cases one can simplify by omitting the fraction. Including products in the analysis we have the following theorem. Let f , g , h ∈ Z [ x ] {\displaystyle f,g,h\in \mathbb {Z} [x]} such that g h {\displaystyle gh} divides f {\displaystyle f} then
‖ g ‖ ∞ ‖ h ‖ ∞ ≤ ‖ g ‖ 2 ‖ h ‖ 2 ≤ ‖ g ‖ 1 ‖ h ‖ 1 ≤ 2 m + k ‖ f ‖ 2 ≤ 2 n n + 1 ‖ f ‖ ∞ , {\displaystyle \|g\|_{\infty }\|h\|_{\infty }\leq \|g\|_{2}\|h\|_{2}\leq \|g\|_{1}\|h\|_{1}\leq 2^{m+k}\|f\|_{2}\leq 2^{n}{\sqrt {n+1}}\|f\|_{\infty },}
‖ h ‖ ∞ ≤ ‖ h ‖ 2 ≤ ‖ h ‖ 1 ≤ 2 k ‖ f ‖ 2 ≤ 2 n ‖ f ‖ 2 ≤ 2 n ‖ f ‖ 1 , {\displaystyle \|h\|_{\infty }\leq \|h\|_{2}\leq \|h\|_{1}\leq 2^{k}\|f\|_{2}\leq 2^{n}\|f\|_{2}\leq 2^{n}\|f\|_{1},}
‖ h ‖ ∞ ≤ ‖ h ‖ 2 ≤ ‖ h ‖ 1 ≤ 2 k ‖ f ‖ 2 ≤ 2 k n + 1 ‖ f ‖ ∞ ≤ 2 n n + 1 ‖ f ‖ ∞ , {\displaystyle \|h\|_{\infty }\leq \|h\|_{2}\leq \|h\|_{1}\leq 2^{k}\|f\|_{2}\leq 2^{k}{\sqrt {n+1}}\|f\|_{\infty }\leq 2^{n}{\sqrt {n+1}}\|f\|_{\infty },}
| h i | ≤ ( k i ) M ( h ) ≤ ( k i ) ‖ f ‖ 2 ≤ ( n i ) ‖ f ‖ 2 , {\displaystyle |h_{i}|\leq {\binom {k}{i}}M(h)\leq {\binom {k}{i}}\|f\|_{2}\leq {\binom {n}{i}}\|f\|_{2},}
‖ h ‖ ∞ ≤ ( k ⌊ k / 2 ⌋ ) ‖ f ‖ 2 ≤ ( n ⌊ n / 2 ⌋ ) ‖ f ‖ 2 ≤ ( n ⌊ n / 2 ⌋ ) ‖ f ‖ 1 . {\displaystyle \|h\|_{\infty }\leq {\binom {k}{\lfloor k/2\rfloor }}\|f\|_{2}\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{2}\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{1}.}
Using Stirling's formula applied to binomial coefficients we get asymptotically a slight improvement when using binomial coefficients
‖ h ‖ ∞ ≤ ( n ⌊ n / 2 ⌋ ) ‖ f ‖ 2 ≈ 2 n 2 π n ‖ f ‖ 2 . {\displaystyle \|h\|_{\infty }\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{2}\approx 2^{n}{\sqrt {\frac {2}{\pi n}}}\|f\|_{2}.}
From the bounds on the individual coefficients one can deduce the following related bound. If f ∈ Z [ x ] {\displaystyle f\in \mathbb {Z} [x]} is reducible then it has a non-trivial factor h {\displaystyle h} of degree k ≤ ⌊ n / 2 ⌋ {\displaystyle k\leq \lfloor n/2\rfloor } such that
‖ h ‖ ∞ ≤ ( ⌊ n / 2 ⌋ ⌊ n / 4 ⌋ ) ‖ f ‖ 2 ≤ ( ⌊ n / 2 ⌋ ⌊ n / 4 ⌋ ) ‖ f ‖ 1 . {\displaystyle \|h\|_{\infty }\leq {\binom {\lfloor n/2\rfloor }{\lfloor n/4\rfloor }}\|f\|_{2}\leq {\binom {\lfloor n/2\rfloor }{\lfloor n/4\rfloor }}\|f\|_{1}.}
Combining this with Stirling's formula to replace the binomial coefficients leads to more explicit versions. While the upper bounds that are independent of h {\displaystyle h} and only depend on f {\displaystyle f} are of great theoretical interest and aesthetic appeal, in practical application one has usually information about the degree k {\displaystyle k} of h {\displaystyle h} . This is why the sharper bounds that additionally depend on k {\displaystyle k} are often more relevant.
Sharpness of bounds
Cyclotomic polynomials For f = x n − 1 {\displaystyle f=x^{n}-1} the cyclotomic polynomials h = Φ n ( x ) {\displaystyle h=\Phi _{n}(x)} is an irreducible divisor of degree k = φ ( n ) {\displaystyle k=\varphi (n)} , Euler's totient function. In this case
‖ f ‖ 2 = 2 {\displaystyle \|f\|_{2}={\sqrt {2}}} and it is custom to denote ‖ h ‖ ∞ = A ( n ) {\displaystyle \|h\|_{\infty }=A(n)} . A result of Vaughan states for infinitely many positive integers n {\displaystyle n}
‖ h ‖ ∞ = A ( n ) > e ( n ( log 2 ) / ( log log n ) ) , {\displaystyle \|h\|_{\infty }=A(n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)},}
a superpolynomial bound in the degree n {\displaystyle n} . Comparing with Mignotte's bound and using Stirling's formula as well as bounds for Euler's totient function we get for infinitely many n {\displaystyle n}
e ( n ( log 2 ) / ( log log n ) ) < ‖ h ‖ ∞ ≤ ( k ⌊ k / 2 ⌋ ) ‖ f ‖ 2 = ( φ ( n ) ⌊ φ ( n ) / 2 ⌋ ) 2 ≈ 2 φ ( n ) 2 π φ ( n ) 2 ≥ 2 e − γ n / ( log log n ) 2 π e − γ n / ( log log n ) . {\displaystyle e^{\left(n^{(\log 2)/(\log \log n)}\right)}<\|h\|_{\infty }\leq {\binom {k}{\lfloor k/2\rfloor }}\|f\|_{2}={\binom {\varphi (n)}{\lfloor \varphi (n)/2\rfloor }}{\sqrt {2}}\approx 2^{\varphi (n)}{\sqrt {\frac {2}{\pi \varphi (n)}}}{\sqrt {2}}\geq 2^{e^{-\gamma }n/(\log \log n)}{\frac {2}{\sqrt {\pi e^{-\gamma }n/(\log \log n)}}}.}
This leaves a gap between Mignotte's upper bound and what is known to be attained through cyclotomic polynomials. Cyclotomic polynomials cannot close this gap by a result of Bateman that states for every ε > 0 {\displaystyle \varepsilon >0} for all sufficiently large positive integers n {\displaystyle n} we have
‖ h ‖ ∞ = A ( n ) < e ( n ( log 2 + ε ) / ( log log n ) ) . {\displaystyle \|h\|_{\infty }=A(n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}.}
Also note that despite the superpolynomial growth of Vaughan's lower bound in practice looking at examples of cyclotomic polynomials the coefficients of h = Φ n ( x ) {\displaystyle h=\Phi _{n}(x)} are far smaller than Mignotte's bound.
A family of polynomials with exponential growth in the coefficients of its factors Abbot gives the following example related to cyclotomic polynomials. Set
H ( x ) = ( x + 1 ) ( x 2 + x + 1 ) = x 3 + 2 x 2 + 2 x + 1 , F ( x ) = H ( x ) ⋅ H ( − x ) = − x 6 + 1 {\displaystyle H(x)=(x+1)(x^{2}+x+1)=x^{3}+2x^{2}+2x+1,\ \ \ F(x)=H(x)\cdot H(-x)=-x^{6}+1}
and consider for positive integers j {\displaystyle j}
h = h j = H ( x ) j , f = f j = F ( x ) j . {\displaystyle h=h_{j}=H(x)^{j},\ \ \ f=f_{j}=F(x)^{j}.}
Note that the degrees are k = 3 j {\displaystyle k=3j} resp. n = 6 j {\displaystyle n=6j} . Abbot shows that asymptotically for large j {\displaystyle j} we have
‖ h j ‖ ∞ ≥ 6 j 1 3 j + 1 , ‖ f j ‖ ∞ ≈ 2 j 2 π j . {\displaystyle \|h_{j}\|_{\infty }\geq 6^{j}{\frac {1}{3j+1}},\ \ \ \|f_{j}\|_{\infty }\approx 2^{j}{\sqrt {\frac {2}{\pi j}}}.}
Using Mignotte's bound in the version
‖ h ‖ ∞ ≤ 2 k n + 1 ‖ f ‖ ∞ {\displaystyle \|h\|_{\infty }\leq 2^{k}{\sqrt {n+1}}\|f\|_{\infty }}
we compare
3 n / 6 π 3 n ≈ 6 j 1 3 j + 1 2 j 2 π j ≲ ‖ h ‖ ∞ ‖ f ‖ ∞ ≤ 2 k n + 1 = 2 n / 2 n + 1 {\displaystyle 3^{n/6}{\sqrt {\frac {\pi }{3n}}}\approx {\frac {6^{j}{\frac {1}{3j+1}}}{2^{j}{\sqrt {\frac {2}{\pi j}}}}}\lesssim {\frac {\|h\|_{\infty }}{\|f\|_{\infty }}}\leq 2^{k}{\sqrt {n+1}}=2^{n/2}{\sqrt {n+1}}}
Ignoring the root terms leads to
1.2009 n ≈ 3 6 n ≲ ‖ h ‖ ∞ ‖ f ‖ ∞ ≲ 2 n ≈ 1.4142 n . {\displaystyle 1.2009^{n}\approx {\sqrt[{6}]{3}}^{n}\lesssim {\frac {\|h\|_{\infty }}{\|f\|_{\infty }}}\lesssim {\sqrt {2}}^{n}\approx 1.4142^{n}.}
Abbot claims that
An exhaustive search in low degrees suggests that this family of factorizations is close to extremal. While there is still an exponential gap between the example and Mignotte's bound, the example shows that exponential growth is the right order for such a general bound. Note that Abbot also compares Mignotte's bound with other types of bounds and gives examples where Mignotte's bound is best and examples where other bounds are better. Also note that, while the cyclotomic polynomials h = Φ n ( x ) {\displaystyle h=\Phi _{n}(x)} from the previous section are irreducible factors, the factors h = h j = H ( x ) j = ( x + 1 ) j ( x 2 + x + 1