It's not like integer division is just polynomial division with $x=10$ or something -- the results of the division are different, because integer division does not assume a base of 10.
But polynomial division also focuses on an analogous detail: the resulting quotient having to be a polynomial. And the essential lesson of mathematics, and the idea of abstract mathematics, is that serious analogies are the sign of abstraction.
So what makes polynomials and integers similar -- in what sense are they similar? -- that we can perform a "long division" algorithm on them?
And you know: this is not the only analogy between integers and polynomials either. Here's a list, with a general "abstract" phrasing that works for both integers and polynomials:
- Division with remainder: For any $a,b$, there is some "unique" representation $a=qb+r$, where "uniqueness" is with respect to the property that $r<b$ (this $<$ ordering on the integers refers to the the ordering of the absolute value, and on the polynomials refers to the degree).
- Bezout's identity: For any $a, b$, the set $\{\lambda a + \mu b\}$ is precisely the multiples of $\mathrm{gcd}(a, b)$.
- Unique factorization: For any $a$, there exists a unique representation $a=p_1\dots p_n$ among $p_i$ that are "prime" ("irreducible") in the sense of not having any further factors. Well, is that really true? Not exactly: prime numbers can be factored with $-1$s and $1$s, and irreducible polynomials can be factored with constant polynomials. Well, this caveat has to do with stuff having itself as a factor, e.g. $x-2=(1/2)\cdot(2)\cdot(x-2)$ or $37=(-1)\cdot(-1)\cdot 1\cdot 37$. This means the other elements of this "factorization of the prime number" multiply to 1/are each "invertible" ("units"). So we should say we have unique factorization is "up to units".
- Greatest common divisors: For any $a, b$, there is a $\delta$ that divides both and is divided by all $d$ that divide both $a$ and $b$ (note that the term "divides" can exist in more generality than the assumptions of "division with remainder").
Well, the first thing we observe is that we should assume the existence of some notions of addition, subtraction and multiplication -- these seem to be the "fundamental" structures present among integers and polynomials (as opposed to e.g. rational numbers, rational functions which also require division or natural numbers which don't have subtraction).
We will omit discussing the properties of these operations for now, as we don't yet have enough to motivate them on.
Next, each of these discussed properties can be considered as special axioms for special cases of rings, domains where specific important theorems hold -- we call them, respectively:
- Euclidean domain: The ring is equipped with a natural number-valued magnitude function $\|\cdot\|:R\to\mathbb{Z}^{\ge 0}$, called the Euclidean function. For all $a,b$ in $R$ with $b$ non-zero (intuit out this condition), there exist $q, r$ with $\|r\|<\|b\|$ such that $a=qb+r$.
- Principal Ideal Domain: A ring where all ideals (additive subgroups invariant under multiplication by a ring element) are principal (a set of multiples of a generating element). Another abstraction is a "Bezout domain", which only requires that linear combinations of principal ideals are principal, but a PID should be seen as a more "natural" generalization.
- Unique factorization domain: A ring where every element has a unique factorization into irreducibles, modulo multiplication by a unit.
- GCD domain: A ring in which any two elements has a GCD.
(Quick comments on why the Euclidean function must map to the naturals: in fact, they could map to any "well-ordered set" (a totally ordered set in which every subset has a least element). The reason why this property is needed -- why we can't, e.g. map to the nonnegative reals -- is to ensure Euclid's algorithm terminates.)
The abstractions of the basic theorems about integers and polynomials occur as relationships between these domains. As it turns out, we will see that:
\[{\rm{ED}} \Rightarrow {\rm{PID}} \Rightarrow {\rm{UFD}} \Rightarrow {\rm{GCD}}\]
Before that, though, we can already play with some basic results we'd like, to get a feel of what axioms about ring addition and multiplication we should assume.
E.g.
- What should $\|0\|$ equal? Prove that 0 must have the least magnitude of any ring element, making up the axioms you need on the fly. You should require: additive identity, additive inverse, additive associativity.
- Try to prove some obvious results regarding Bezout's identity, like with $a$ and $b$ equal. You should require: left-distributivity, right-distributivity.
- Consider generalizations of two-element properties, like the Bezout identity, to multiple elements. You should require additive associativity, multiplicative associativity, additive commutativity, multiplicative commutativity.
Well, to be honest these all seem like fairly elementary properties that would be useful outside the cases of these special domains. Out of the following properties:
Presumably 6 (additive commutativity) is hardest to see the importance of, but it's relevant to note the relationships between these axioms. In fact, it is fairly simple to show that 1, 2 and 8 imply 6 (consider $(1+1)(x+y)$). As a result, addition -- the operation that multiplication distributes over -- is just generically seen as commutative.
Another important property often seen in algebraic problems is the ability to factor to find roots, i.e. to say that if $ab=0$, either $a$ or $b$ should be 0. This is known as an integral domain. The full sequence of inclusions, as we will see, is actually given by:
\[{\rm{ED}} \Rightarrow {\rm{PID}} \Rightarrow {\rm{UFD}} \Rightarrow {\rm{GCD}} \Rightarrow {\rm{ID}} \Rightarrow {\rm{Ring}}\]
The broader point of all this is that you should start often thinking of a lot of basic mathematical facts in the language of abstract algebra -- what kind of ring/domain is this result valid in? etc. -- because this is the most general setting in which a result is valid in, and you know exactly what it is "saying", i.e. what implies what.
- Left-distributivity
- Right-distributivity
- Additive associativity
- Additive identity
- Additive inverse
- Additive commutativity
- Multiplicative associativity
- Multiplicative identity
- Multiplicative commutativity
- Multiplicative inverse
Presumably 6 (additive commutativity) is hardest to see the importance of, but it's relevant to note the relationships between these axioms. In fact, it is fairly simple to show that 1, 2 and 8 imply 6 (consider $(1+1)(x+y)$). As a result, addition -- the operation that multiplication distributes over -- is just generically seen as commutative.
Another important property often seen in algebraic problems is the ability to factor to find roots, i.e. to say that if $ab=0$, either $a$ or $b$ should be 0. This is known as an integral domain. The full sequence of inclusions, as we will see, is actually given by:
\[{\rm{ED}} \Rightarrow {\rm{PID}} \Rightarrow {\rm{UFD}} \Rightarrow {\rm{GCD}} \Rightarrow {\rm{ID}} \Rightarrow {\rm{Ring}}\]
The broader point of all this is that you should start often thinking of a lot of basic mathematical facts in the language of abstract algebra -- what kind of ring/domain is this result valid in? etc. -- because this is the most general setting in which a result is valid in, and you know exactly what it is "saying", i.e. what implies what.
No comments:
Post a Comment