Finding units in polynomial quotient rings

[gonzo]

Is there a simple method for finding all the units in a polynomial quotient ring over a finite field? For example:

$${F_2[x] \over x^7-1}$$

I can see the easy ones like 1, and all power of x, but I wanted a general rule or method for finding all of them if it exists (besides testing each individually, which can get tedious for big rings).

Thanks.

 

[matt grime]

What does it mean to be a unit? f is a unit if there is a g such that fg=1, now what does it mean for two polys to equal 1 in this ring (remember an element of this ring is just an equivalence class of polynomials)?

 

[gonzo]

That's how I got the set of the powers of x. What I'm missing is the proof that this is the only set of units for this case and the general case. Or maybe there are two separate general cases, x^n-1 and other not so simple polynomials?

 

[matt grime]

Finding the units of this (or a number field, say) is, I believe, a genuinely hard problem (as in impossible to do in general by any other means than just 'doing it').

EDIT: I think i might take that back: we're just finding the f with hcf(f,x^n - 1)=1. And that ought to be reasonably easy in this case, right?

 

[gonzo]

That's what I was wondering. At first I thought the general problem was hard, but I realized that with these roots of unity polynomials there are often easier answers.

If the polynomial is irreducible, then all elements are units, since it is a field. So then I was wondering if with a reducible polynomial if it was just related to the factors of the polynomial in question.

Which is basically what you wrote ... all polynomials that don't share a factor with x^n-1. For a general polynomial, this would of course be tedious to list out, so the question is if there is a short cut with this type of polynomial.

The problem I was really trying to get at is that given the ideal in this ring:

<1+x+x^3>

Lits all generators of this ideal. I thought the easiest way to do this would be to multiply this generator by all the units if they were easily listable, since that would give you the same ideal again. But maybe there is an easier way to do this? (besides the long way by hand)

I was looking for generalized short cuts to make future problems like this easier. (and to understand the situation better).

 

[gonzo]

It occurred to me that I might be doing this backwards. If all polynomials that don't share a factor with x^7-1 are units, then to find the generators of the ideal it would be easier to first find the non-generators ... in other words, all products with the factors of the x^7-1, since that is much smaller number to work with.

It's still a bit of a brute force excercise, so I was hoping for a cleaner way to do it. But it would work, right?

 

[Hurkyl]

It's still a bit of a brute force excercise

It's not that bad, is it? It amounts to little more than factoring your polynomials.


A chinese remainder theorem approach might work too -- if k is your base field, f is a polynomial that factors into pqr, then you can analyze the quotient ring k[x]/(f) by studying the three quotient fields k[x]/(p), k[x]/(q) and k[x]/(r).

 

[gonzo]

Well, in my example, it's not that bad since it's easy to factor and only has 3 factors. But it can easily get out of hand if there are a lot of factors since you have to check all combinations of them.

Which is why I was looking for a non-brute force method. But maybe there isn't one? Not even for cyclotomic polynomials?

 

[Hurkyl]

Knowing what is not a unit is essentially equivalent to knowing the factorization of your polynomial.

But it can easily get out of hand if there are a lot of factors since you have to check all combinations of them.

Which is why I was looking for a non-brute force method.

I'm not sure what you mean by that... or why you call using the factorization of your polynomial a brute force method.

 

[gonzo]

It's brute force because I then have to multiply all the factors in every combination with my ideal generator, with every other polynomial in the ring, to get the non-generators.

Or I have to multiple all the polynomials that don't share a factor in every combination with my generator to get all the generators.

I can't see any easy way to do this that isn't horrible and brute force.

Factoring is easy: $x^7-1=(1+x)(1+x+x^3)(1+x^2+x^3)$

But how else besides brute force am I going to find all the generators of the ideal <1+x+x^3>? I thought the units approach would be easiest in the hopes there there wouldn't be many, maybe only powers of x. But it seems that there are a lot more units than that, anything that doesn't share one of the above factors. So either way seems really messy.

 

[Hurkyl]

What do you mean by "find" then? I had assumed you meant one of the following:

(1) An easy criterion for checking if something is a generator of that ideal
(2) A simple parametrization of the generators

But this last post makes it sound like you actually want a list of all s generators. If so, then you cannot possibly do it in less than s work!

(Just to check -- do you see how to get both (1) and (2)?)

 

[gonzo]

I see how to get both 1 and 2 ... well, okay, not exactly two. I can describe 2 as "a product of all factors that don't share a factor with x^7-1" or something like that.

The problem I am faced with seems to be to actually _list_ all the generators. But I'll settle for a concise parameterization.

Did you have something in mind for 2) that was really simple? I don't see how.

 

[Hurkyl]

I'm looking at the chinese remainder theorem approach. We have the isomorphism:

[tex]
\def\F{\mathbb{F}_2}

\F[x] / (x^7 + 1) \cong
(\F[r] / (r + 1)) \oplus (\F / (s^3 + s + 1)) \oplus
(\F[t] / (t^3 + t^2+ 1))
[/tex]

Each component of the isomorphism is just reduction modulo the appropriate polynomial. (I've changed the indeterminate for clarity) The unit group of the thing on the right is easy to compute.

The isomorphism sends $x^3 + x + 1 \rightarrow \langle 1, 0, t^2 + t \rangle$, and it's easy to list the generators of the ideal $( \langle 1, 0, t^2 + t \rangle )$. (Note that $t^2 + t$ is a unit!)

If you want to map back to the original ring, you just apply the chinese remainder theorem.


For a more lowbrow description -- you simply analyze the problem modulo x+1, then again modulo x³ + x + 1, then again modulo x³ + x² + 1. Once you've done that, you just reassemble everything to get your answer.

 

[gonzo]

Okay, that's about where I was at (although I hadn't thought of it in the isomorphism terms, which is a bit cleaner). Thanks. I guess I was looking for something that doesn't exist, but that itself is good to know.