# Why are polynomials easier to handle with than integers?

This may seems to be an elementary question, but I found no answers on MO nor google.

I have always heard "polynomials are easier to handle with than integers". For example:

1. When $n$ is quite large, maybe 200 or more, it's relatively easier to factorize a polynomial $f$ of degeree $n$ than to factorize an integer with $n$ bytes.

2. When multiplying large integers, we see them as polynomials,use techniques such as FFT,intepolations to multiply polynomials,and then back to integers.

3.The zeta functions of $F[x]$ and $\mathbb{Z}$, and the former are easier to study than the latter.

Of course there are other examples, but because of my shortage of knowledge, I can only lise these above.

So my question is (as in the titile): Why are polynomials easier to handle with than integers? I ask this because contrary to our intuitives, polynomials are "more complex" objects than integers.

-
The most elementary thing that always simplifies "function field number theory" in my experience the following: In a polynomial $a_0+a_1x+\cdots+a_nx^n$, we may think of $a_i$ as the "$i$th digit" in the expansion of the polynomial. When you add polynomials, there is no carry-over. This makes life much simpler. For example, $Z/p^2\to \Z/p$ is not a split epimorphism of abelian groups, but $Z/p[t]/(t^2)\to Z/p$ is split. –  Amritanshu Prasad Oct 29 '10 at 4:17
There is differentiation on polynomials. This is no simple operation like this on integers, although people do think about getting good analogues of it (e.g., Buium). For example, a polynomial in Q[x] is squarefree iff it is relatively prime to its derivative, and gcd(f,f') can be computed rather efficiently. There is no simple way to determine if an integer is squarefree without in some way factoring it. –  KConrad Oct 29 '10 at 6:20
Long division with polynomials is much easier than long division of integers (do students even learn that any more?). That's also probably due to the "no carry-over" mentioned in Amri's comment. –  QuantumBrian Oct 29 '10 at 8:36

How Halloweeny can you get with your questions? The norm on $Z$ is Archimedean and the norm on $F[X]$ is non-Archimedean, and, in general, non-Archimedean maths is easier than Archimedean...

-
maths instead of math! I thought Bugs Bunny was American. –  KConrad Oct 29 '10 at 15:17

In the Euclidean division of polynomials, quotient and remainder are uniquely defined, and compatible with addition. This fails for integers.

There is no integer analogue of constant polynomials. I guess that the search for the "field with one element" is in a sense motivated by this.

-

Divisibility of polynomials is a much more rigid property than in integers. Given an integer $n$, another $N$ has a non-zero probability $\frac1n$ to be a multiple of $n$. On the contrary, the probability (no rigour here) that a random'' polynomial $P\in{\mathbb C}[X]$ be a multiple of a given one $q$ is zero. For instance, $P$ is a multiple of $X$ iff $P(0)=0$, an event of probability $0$.

If you increase the structure, by either considering multi-variate polynomials, or polynomials with coefficients in $\mathbb Z$, you simplify'' even more, in the sense that you have additional criteria for divisibility of primality (Newton's polygon, Eisenstein's criterion, ...), and you have a huge theory (Galois' theory) which you can use and abuse.

Edit. An example of the powerness of polynomials that I like a lot is the following.

Theorem. Let $k$ be a field and $A_0,A_1,B_0,B_1\in M_n(k)$ be given, with $A_0,A_1$ invertible. Let $X$ be an indeterminate. If $XA_0+B_0$ and $XA_1+B_1$ are equivalent in $M_n(k[X])$, the there exist $G,H\in GL_n(k)$ such that $GA_0=A_1H$ and $GB_0=B_1H$.

The case where $A_0=A_1=I_n$ is at the basis of the theory of similarity invariants.

-
To summary, shall we say it's because polynomials are "data structures" on which we have more operations, such as differentials, mod p, decompositons over various entended fields...etc ? –  zhaoliang Oct 29 '10 at 10:18
Yes, that's the point. –  Denis Serre Oct 29 '10 at 10:46
These probabilities are related to the finiteness of the residue fields at maximal ideals. The analogue is true in $F[X]$ where $F$ is a finite filed: if it has $q$ elements, and $P$ has degree $d$, the probability of a random polynomial to be a multiple of $P$ is $q^{-d}$. –  Laurent Moret-Bailly Oct 29 '10 at 16:20

Following the commentary by Amri, I think that his idea can be explained in terms of graduations: The natural graduation of $F[X]$ over $F$, generated by the degree, allows us to compute simultaneously a lot of $F$-sums without mixing information. Maybe the rest of facts can be also described by graduation properties? (I'm not taking into account trivial graduations for $Z$).

-