Posted by: yanzhang | July 1, 2008

## Algebra 101 – You Can? Really?

One gratuity we mathematician wannabes love to throw around (especially around college age) is “degrees of freedom.” The jury is out on whether the physicist wannabes are more judicious when they do it, but most of us have developed at least a passable idea of when we seem to have enough “wiggle room,” at least erring on the side of assuming we have too much (when a problem looks difficult, say with an air of superiority: “mm. We cannot give up now, because we definitely have enough degrees of freedom.” which will earn you looks of awe when someone else actually solves the problem, giving you time to BS a reason on why you had enough degrees of freedom in the first place). The asymmetry is that we are actually usually very good at telling when we have very few degrees of freedom, which is why this problem scared the hell out of me, because at first glance it seems impossible (try, for example, f = 1 + x^2 + x^3 + x^4):

Take a polynomial f in Q[x]. Prove that we can multiply it by another polynomial in Q[x] such that the product contains only terms of the form ax^p, a in Q and p prime.

Proof and Analysis:

Consider Q[x] modded out by (f). This is a vector space of dimension deg(f) (read: finite). Hence, there is some nontrivial linear combination of monomials with prime degree that sum to 0 (mod f), which is equivalent to our claim.

Alternatively (this is how I got it at first): consider the k-dimensional vector space V of polynomials generated by f, xf, … x^{k-1} f. This is a k-dimensional vector space inside the vector space X generated by 1, x, … x^{deg(f) + k – 1}. Note the co-rank of V inside X is independent of k! Now consider the vector space P generated by x^p, p prime. P’, the intersection of P and X, has increasing rank as k goes to infinity, so eventually P’ has rank exceeding the corank of V, meaning P’ and V has some nontrivial intersection. Note this proof is basically the same as the first proof, but has slightly different intuition.

Andrew Dudzik claims that he usually sees this problem with “prime” replaced with “powers of 2,” which is ingenious since it fools you into thinking you have to use powers of 2 somehow (whereas if your mathematical intuition is fairly strong you’d have a feel that the “primes” were just a red herring in this problem). I suggest that when you give this problem to your friends you use the even more devious version that I came up with: force the degrees of the monomials to be divisible by [deg(f) – 1].

-Y

Source: Berkeley Problems in Mathematics (de Souza, Silva) / Andrew Dudzik