Power series to find the inverse of any function in Z_2[x]?

[Treadstone 71]

Is it possible to use power series to find the inverse of any function in Z_2[x]?

 

[matt grime]

Things in Z_2[x] aren't (necessarily) functions (on anything), they are polynomials in one indeterminate. (Ie power series don't even make sense, unless there are only finitely many nonzero coefficients, ie it is a polynomial)

What makes you think that any element in there, except 1, has a multiplicative inverse, purely in the ring theoretic sense?

Exercise, let f be a poly in Z_2[x], and let df denote its degree, show d(fg)=df.dg

 

[Treadstone 71]

1-x is invertible as a power series, I am told.

 

[HallsofIvy]

What makes you think that any element in there, except 1, has a multiplicative inverse, purely in the ring theoretic sense?

The original post didn't say anything about multiplicative inverse, just inverse. I would have been inclined to assume that "inverse function" was meant. In that sense, the inverse of 1- x (which equals 1+ x in Z_2[x]) would be itself: 1+ x.

 

[matt grime]

But to consider these as functions is a little odd since it mentions not the domain or range of what they are functions from or to. Since this is posted in the abstract algebra section I think I made prefectly sensible inferral.

The point still holds that speaking of power series in a ring of polynomials is not valid whatever the situation is.

If the question was when can we find polynomials f and g such that f(g(x))=g(f(x))=x then obviously only degree one polys will suffice, and either of those is self inverse under composition in this sense.

 

[Treadstone 71]

Why are power series not in the ring of polynomials? Specifically, a ring of polynomials mod some constant.

 

[matt grime]

Because by definition polynomials only have with finitely many nonzero coefficients, power series may have infinitely many non-zero coefficients.
Ie
1+x+x^2+...
isn't a polynomial so isn't in the ring of polynomials; it's just a definition.

Certainly a polynomial is a power series, but a power series is not in general a polynomial.

I'm not sure why i feel the need to point this out, but for hallsofivy: since the original question asked about using power series to find inverses of things in Z_2[x] (things that are not functions) i felt that the intention was to compute (1+x)^{-1} the multiplicative inverse since it mentioned power series. of course if we were thinking of the space Z_2[x] mod x^n then of course the idea of using power series 'works' since x^n is nilpotent. when i say 'works' i of course mean can be used to construct the answer since the formal power series 1+x+x^2+.. terminates. upon applying mod x^n

As for the other idea of invese: I'm not sure what it means, even if we think of functions on C, to use power series to find the inverse function of f(z)=1+z,or rather I'm not sure why you'd do that.treadstone: could you perhaps clear up this mystery. did you intend to work out (1+x)^{-1} (which doesn't exist in Z_2[x]) or the polynomial (I cannot and will not call them functions) g(x) such that g(1+x)=x.Incidentally, note that if you are considering functions from Z_2 to Z_2 that there are exactly 4 of these, whereas there are infinitely many polynomials in Z_2[x]

 

[Treadstone 71]

Initially, I thought for some reason that Z2[x] is a field. I've seen on an assignment somewhere that any polynomial has a multiplicative inverse written in the form of a power series. I didn't have any idea why power series aren't in the ring of polynomials. I mean, if Z2[x] didn't contain any polynomials, then it should be finite in cardinality. However it isn't, since for any poly of degree n, one can always write down one of degree n+1. This was all for an extra credit question on the final so I didn't have time to think it all the way through.

Anyway, I had to show that there are no surjective homomorphisms between Z2[x] and Z2XZ2XZ2. By assuming that any element in Z2[x] has a multiplicative inverse written as some power series, I showed that the kernel of any homomorphism between those two rings must be 0, and therefore the homomorphism must be injective. With the additional hypothesis that the hypothesis that it is also surjective, there would be an isomorphism between Z2[x] and Z2 X Z2 X Z2, which is impossible. It's a proof by contradiction, basically.

Unfortunately I didn't know that A) power series aren't in rings of polynomials (though I find this odd) and B) therefore Z2[x] is not a field.

 

[Hurkyl]

Maybe taking a step back would be a good idea:

What is the definition of "polynomial"? Of "power series"? Of the ring "R[x]" (where R is a commutative ring)?

 

[matt grime]

If Z_2[x] were a field then of course there is no hom from it to (Z_2)^3 since any ring hom from a field is either an injection or an isomorphism, both of which are impossible for cardinality reasons in this case (ie we can remove the hypothesis that the notional map is surjective).

 

[matt grime]

Initially, I thought for some reason that Z2[x] is a field. I've seen on an assignment somewhere that any polynomial has a multiplicative inverse written in the form of a power series. I didn't have any idea why power series aren't in the ring of polynomials. I mean, if Z2[x] didn't contain any polynomials, then it should be finite in cardinality.

I said it didn't make sense to talk about power series. Whilst a poly is a power series, you cannot blithely talk about power series in Z_2[x] unless you check it only has finitely many non-zero coefficients, ie it is a polynomial.

Unfortunately I didn't know that A) power series aren't in rings of polynomials (though I find this odd)

well, it is just a definition. look up the definition of polynomial.

 

[Treadstone 71]

http://mathworld.wolfram.com/Polynomial.html

It doesn't say explicitly about finite power.

But here's my argument: elements in Z2[x] are of the form a+bx+cx^2+...+zx^n where the coefficients are 0 or 1. But the cardinality of the ring is infinite! i.e., the highest power (degree) can be made ARBITRARILY large. That's pretty much like an infinite series, isn't it? For if m is the highest degree in Z2[x], then there are only 2^m elements in Z2[x].

 

[shmoe]

http://mathworld.wolfram.com/Polynomial.html
It doesn't say explicitly about finite power.

Look at their general form for a polynomial, eq. (1). It is a sum with n terms. It has a first and a last term. Both of these are giant flags saying "finite number of terms", even if they aren't mentioning it explicitly.

A polynomial has a finite number of terms, that's how they are defined.

But here's my argument: elements in Z2[x] are of the form a+bx+cx^2+...+zx^n where the coefficients are 0 or 1. But the cardinality of the ring is infinite! i.e., the highest power (degree) can be made ARBITRARILY large. That's pretty much like an infinite series, isn't it? For if m is the highest degree in Z2[x], then there are only 2^m elements in Z2[x].

Z_2[x] has polynomials of as high a degree as you like. This is not the same as saying you have a polynomial with "infinite degree". The polynomials 1, x, x^2, x^3, x^4, ... are all in Z_2[x], but none of them has an infinite number of terms.

 

[Hurkyl]

I somehow suspect your book didn't define polynomials by saying "Go look at Mathworld's page".

i.e., the highest power (degree) can be made ARBITRARILY large. That's pretty much like an infinite series, isn't it?

In some sense, yes. But in a more practical sense, certainly not.

There is a huge difference between "arbitrarily large" and "infinite", though the difference is subtle at first. The term "arbitrarily large" necessarily refers to some class of objects (such as the collection of polynomials over Z_2), where as "infinite" is generally applied to a single object (such as the list of coefficients of a power series).

 

[Treadstone 71]

Well then, goodbye 20 marks