Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an integer polynomial $P(x) = a_0 + a_1 x + \cdots + a_n x^n$, there ought to be a reasonable bound on the "complexity" of its possible irreducible integer polynomial factors that allows us to restrict to finitely many possible factors. This would allow us to use trial division to test the irreducibility of $P$ (although this is a pretty bad test of irreducibility).

As an example, in response to another math.SE question I gave a straightforward bound $$|x| \le \max(1, \left| \frac{a_0}{a_n} \right| + \cdots + \left| \frac{a_{n-1}}{a_n} \right|) = M$$

on the absolute value of the complex roots of $P$. This bound implies a horrible bound on the absolute values of the coefficients of an irreducible factor of degree $d$ (the $k^{th}$ coefficient has absolute value at most $a_n {d \choose k} M^k$), and I am wondering if it is possible to do substantially better.

Here's one precise form of this question. Given a polynomial $P \in \mathbb{Z}[x]$ of degree $n$ define its length $L(P)$ to be the sum of the absolute value of its coefficients.

What is the smallest exponent $e_{n,d}$ for which there exists a constant $c_{n, d}$ such that, for all $P \in \mathbb{Z}[X]$ of degree $n$ and all irreducible factors $Q$ of $P$ in $\mathbb{Z}[x]$ of degree $d$, we have the inequality $L(Q) \le c_{n, d} L(P)^{e_{n,d}}$?

share|improve this question
    
David Boyd had a nice paper on such inequalities back in the 1970s or 80s. Sorry I can't be more specific, as I am away from my references. –  Gerry Myerson Jan 5 '12 at 1:23
    
@Gerry D. Boyd's results were also discovered independently by others, e.g. M. Laugevin, C. Stewart, and M. Mignotte. These and other related results are presented in Chapter 4 of Mignotte's Mathematics for Computer Algebra - which should prove of interest to Qiaochu. –  Bill Dubuque Jan 5 '12 at 2:17
    
I changed \text{max} to \max. It's a standard operator name in TeX. –  Michael Hardy Jan 5 '12 at 3:03
    
@Bill, my recollection is that Boyd's paper (or at least part of it) was of the nature of a survey, not claiming originality for the results, but collecting many in one place. Mignotte's book is more recent and I wish I had remembered it to recommend it to Qiaochu. –  Gerry Myerson Jan 5 '12 at 22:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.