The analogy between integers and polynomials

Integers and polynomials form number systems which have the following things in common:

  • The two number systems closed under addition, subtraction and multiplication.
  • Objects in the respective number systems can be factored into “primes.” You’re familiar with what an prime integer is. A prime polynomial is just a polynomial that doesn’t factor further. To make this more precise we have to specify what sorts of coefficients the factors can have.The simplest case is if the factors are allowed to have complex coefficients. In this case, according to the Fundamental Theorem of Algebra and the factor theorem a polynomial with complex coefficients can be factored into a constant times linear factors; so the “prime polynomials” are just the linear polynomials (ax – b) where a and b are complex numbers.The next simplest case is the case where the factors are allowed to have real coefficients. In this case, using the fundamental theorem of algebra and the fact that the roots of a polynomial with real coefficients come in complex conjugate pairs one can prove that every polynomial with real coefficients can be factored into linear polynomials and irreducible quadratic polynomials with real coefficients, so the “prime polynomials” are the linear polynomials (ax – b) where a and b are real and the quadratic polynomials Ax^2 + Bx + C which have real coefficients and non-real roots.Things become more complicated if we require that the coefficients be rational numbers. Most polynomials with rational coefficients do not factor further into polynomials with rational coefficients; I mentioned this the fifth paragraph of my post titled The Rational Root Theorem. So in this case most polynomials are prime, though obviously there are exceptions (to find one just take two polynomials with rational coefficients and multiply them together!)
  • Both integers and polynomials obey unique prime factorization.One needs to be a little bit careful here. A straightforward point is that two factorizations are considered to be the same if they differ only in the order of the factors, e.g. (x – 1)(x + 2) is considered to be the same factorization as (x + 2)(x – 1). More subtly, two factorizations are considered to be the same if the factors differ by units. The units of a number system like the integers or the polynomials are the elements which have inverses that are also integers/polynomials. The units in the set of integers are 1 and -1 (the latter of which is its own inverse). The units in the set of polynomials are the nonzero constant polynomials (the inverse of f(x) = a  is g(x) = 1/a). So for example the factorization 15 =  (3)(5) is considered to be the same as 15 = (-3)(-5). Similarly the factorization of 2x^2 – 12x + 10 given by (2x – 2)(x – 5)
    is considered to be the same as (x – 1)(2x – 10). Once one makes these qualifications, an integer has only one factorization into primes numbers and a polynomial has only one factorization into prime polynomials.
  • Long division is possible.Given an integer ‘a’ and an integer ‘b’ one can write a = b*q + r in exactly one way with ‘r’ is between 0 and b. Here ‘q’ is called the “quotient” of ‘a’ upon division by ‘b’ and ‘r’  is called the remainder.Similarly, if f(x) is a polynomial and g(x) is a polynomial then one can write f(x) = g(x)q(x) + r(x)in exactly one way with the degree of r(x) between 0 and the degree of g(x); again, q(x) is called the quotient and r(x) is called the remainder.
  • Neither the integers nor the polynomials are closed under division but they have natural extensions that are closed under division: the smallest number system that the integers can be extended to which is closed under division is the rational numbers and the smallest number system that the polynomials can be extended to which is closed under division is the set of rational functions. Combining this with unique prime factorization one can say that every rational number/rational function factors uniquely into prime integers/polynomials (possibly with negative exponents to account for the denominators).
  • Both rational numbers and rational functions have partial fraction decompositions. In class we talked about how to find the partial fraction decomposition of something like f(x) = 1/[(x - 1)(x + 2)] by writing it as A/(x – 1) + B/(x +2) and solving for A and B.More generally, given a rational function f(x)/g(x) with f(x) having smaller degree than g(x), one can factor g(x) into prime polynomials and write f(x)/g(x) as a sum of terms each one of which has denominator consisting of only a single prime polynomial (possibly raise to a power). This is covered thoroughly in Section 11.6 of the text.What we didn’t talk about in class is how one can write a number like 1/15 as a sum of two terms rational number search with denominator a prime factor of 15. We try to write1/15 = x/3 + y/5.where ‘x’ and ‘y’ are integers. As in the case of rational functions, we clear the denominators to get 1 = 5x + 3y. The question now is how to find ‘x’ and ‘y’ that work. In contrast with the case of rational functions the situation here is more subtle: the methods that we discussed in class that work for rational functions don’t work here. In this particular case we can eyeball the solution x = 2 and y = -3 to decompose 1/15 as1/15 = 2/3 – 3/5but this evades the general issue: suppose that n is a product of two primes p and q and that we want to write 1/n = x/p + y/q for some integers a and b: is this possible and if so how do we find ‘a’ and ‘b’ that work?

    Equivalently, given primes p and q how can we find integers x and y such that

    1 = px + qy ?

    The answer to this question was known to the ancient Greeks: it comes from the so-called Euclidean algorithm. There’s much to say here but I’ll refrain from doing so now; postponing the discussion for later. Instead I’ll just remark that the fact that it’s more difficult to prove a statement about integers than about polynomials is in fact typical in mathematics. For example, Andrew Wiles proved Fermat’s Last Theorem around 1995 but the the polynomial analog had already been proven around 1900.

    ————–

    A book that I like which expands on some of the themes that I mention above is Ronald Irving’s Integers, Polynomials and Rings. The analogy between integers and polynomials runs still deeper than what I have discussed here but we’ve reached a suitable breaking point.  I hope this will be useful for you in organizing some of what we’ve been doing in class.

Exponential growth and order of magnitude reasoning

In Unit 7 we’re covering the exponential and logarithm functions. One of the features of exponential functions that takes the most time to get used to is how fast they grow.

A famous illustration of the surprisingly fast rate of exponential growth is the Wheat and chessboard problem has been popularized in several children’s books which you may have encountered before; for example One Grain Of Rice: A Mathematical Folktale. The premise of the story is that a wise man is offered a gift by a king and the wise man asks to be given rice for 64 days, one grain on the first day, two grains on the second day, four grains on the first day, and so on. The king readily agrees as the amount of rice as it initially seems like the wise man is asking for a few grains of rice but as the days go on the king discovers that the wise man was implicitly asking for far more rice than the kingdom could possibly produce.

One day in 4th period precalculus I commented that the number of terms in the formula for the determinant of a 100 by 100 matrix is 100! which is bigger than the number of atoms in the observable universe. Many students were incredulous; claiming that the number of atoms in the universe was so big this couldn’t possibly be true. I used Wolfram Alpha to compute that 100! is approximately 10^(158) and those students who were incredulous remained so.

I think that the source of confusion is not a lack of intuition about chemistry or physics or astronomy but rather a lack of understanding how big a number 10^(158) is. Hopefully I can give some sense of this via a plausibility argument for my claim from class via a Fermi Calculation.

[Disclaimer: I have no subject matter expertise in astronomy or astrophysics, the numbers that I give below are just the numbers that I found with a quick internet search from apparently reputable sources; it's possible that the expert consensus for some of these numbers is very different from the numbers quoted or that I've misunderstood something crucial. Despite this, I think that the analysis below will carry some pedagogical value.]

Number of Atoms in the Observable Universe: Many of you are in chemistry and so are familiar with the fact that Avogadro number is the number of particles in a mole of a substance. So, e.g. there are Avogadro number of hydrogen atoms in 1 grams of hydrogen. The sun is mostly made up of hydrogen. The more massive the elements are that compose the sun, the fewer atoms there are in the sun, so if we assume that the sun is made up entirely of hydrogen we’ll get an upper bound on the number of atoms in the sun of the sun. The mass of the sun is less 10^(34) grams and Avogadro’s number is less than 10^(24) so the number of atoms in the sun is less than (10^(24))(10^(34)) = 10^(58).

We can use this as an estimate of the mass of the solar system. In class some of you commented that the calculation above neglects the masses of other objects other than stars like Earth. But the mass of Earth is a billionth the mass of the sun, and indeed the mass of Jupiter (the largest planet in the universe) is a thousandth of the mass of the sun. The mass of the asteroid belt is only 4% of that of the moon which is in turn less than a 10 billionth the mass of the sun. So the sun is by far the dominant mass in the solar system; everything else combined is less than 1% of the mass of the sun. Intuitively this makes sense; if other objects were of comparable mass then the dynamics of the solar system would be more complicated than what they are; everything wouldn’t rotate around the sun in such a clean fashion.

Now, I claimed that 100! is bigger than the number of atoms the observable universe, not just in the solar system. One issue is that there are stars that are bigger than the sun. The most massive stars known stars seem to have ~ 300 times the mass of the sun. But suns aren’t the most massive stellar objects in the universe, that honor belongs to supermassive black holes which are “on the order of hundreds of thousands to billions of solar masses.” To be conservative let’s imagine that every star is a supermassive black hole of a trillion (10^12) solar masses. Assuming that such a black hole is made out of hydrogen atoms; (I actually don’t know what kind of matter a black hole is considered to be!) the number of atoms is no more than:

(10^(58))(10^(12)) = 10^(70)

Okay, now the universe doesn’t just have one stellar object, it has many stellar objects. Nevertheless, there are no more than a trillion (10^(12)) stars in the Milky Way Galaxy. Even the most massive galaxy discovered has no more than a quadrillion (10^(15)) stars. So the largest number of atoms that a galaxy could have is bounded above by

(10^(70))(10^15) = 10^(85).

Now, the current best estimate for the number of galaxies in the observable universe is about 500 billion, to be conservative let’s use the number of ten trillion (10^16). Then an upper bound on the number of atoms that the observable universe could have is

(10^(85))(10^(16)) = 10^(101).

This number is less than 100! ~ 10^(158); not only a little bit smaller but an unimaginable amount.

I’ll note that National Solar Observatory webpage allegedly has an article estimating the number of atoms in the universe as 10^(78).

Conclusion: Our natural intuitions are not well calibrated to thinking accurately about exponentially large or exponentially small quantities; accurately thinking about them requires a combination of care and re-calibrated intuition gained from experience with working with such quantities.

The Rational Root Theorem

The rational root theorem states :

Let   P(x) = a_{n}x^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_{0}   be a polynomial with integer coefficients. Suppose that a = \frac{p}{q} is a root of   P(x)   where p and q have no common factors. Then a_{0} is divisible by p and a_{n} is divisible by q.

Since each of a_{n} and a_{0} have finitely many factors, for a given polynomial this theorem generates a finite list of rational numbers with the property that all rational roots of the polynomial are on the list. Thus, the rational root theorem gives a finite algorithm that can be used to find all rational roots of a given polynomial.

Some high school textbooks suggest that in order to find the roots of a polynomial with integer coefficients, one should use the rational root theorem to find all candidate rational roots of a polynomial equation and then plug them into the polynomial to determine whether they’re roots. The assumption implicit in this is that it will often happen that a polynomial with integer coefficients has a rational root. While this is often case for the high school textbook problems which have been contrived, this is seldom the case for general polynomials with integer coefficients and as such the textbook presentation of the application of the rational root theorem to find roots of a polynomial is misleading.

Polynomials with integer coefficients almost never have rational roots

Mathworld has a nice article with a picture illustrating which degree 5 polynomials x^5 + px + q with p, q integers factor further into polynomials with rational coefficients and which ones don’t; the former type corresponding to yellow boxes. From the picture it’s clear that the vast majority of polynomials of the type under consideration do not factor further into polynomials with rational coefficients. But if a polynomial does not factor further into polynomials with rational coefficients it can have no linear factors with rational coefficients so by the factor theorem it has no rational root.

The limited data illustrated is by no means a proof, however, the picture should be enough to dispel the notion that the rational root theorem provides a good method of finding the roots of a polynomial with integer coefficients. In fact, it has been proven that in a statistical sense, almost no polynomial with integer coefficients factors into polynomials with rational coefficients at all, this is even stronger than saying that a polynomial doesn’t have a linear factor with rational coefficients..

For practical applications one doesn’t need to find the exact values of the roots of a polynomial

It suffices to find a decimal approximation to the value of the root of a polynomial. While the number of decimals needed varies, according to Wikipedia

While the decimal representation of π has been computed to more than a trillion (1012) digits,[21] elementary applications, such as estimating the circumference of a circle, will rarely require more than a dozen decimal places. For example, the decimal representation of π truncated to 11 decimal places is good enough to estimate the circumference of any circle that fits inside the Earth with an error of less than one millimetre, and the decimal representation of π truncated to 39 decimal places is sufficient to estimate the circumference of any circle that fits in the observable universe with precision comparable to the radius of a hydrogen atom.

There are methods such as Newton’s method that almost always work to find very good decimal approximations to the roots of a polynomial. Newton’s method uses calculus but no more than the basics.