Ask Your Question

Class to which an element belong in a quotient ring

asked 2017-10-01 02:47:36 +0200

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

Fellow Sages:

I wish to determine whether certain elements of the quotient ring $Q:=\mathbb{F}_{2}[x]/\langle (x^{5}-1)^2\rangle$ are units and, in the case they are indeed units, I would also like to compute their multiplicative orders. How can one go about doing this?

In case you consider that my previous questions is a wee bit too broad, I have a related question which is more specific: if $p(x) \in \mathbb{F}_{2}[x]$ and $k \in \mathbb{N}$, how does one even determine a representative of the class (in the quotient ring $Q$) to which $(p(x))^{k}$ belongs? The naïve approach does not seem to work here: in my viewpoint, the code

F = GF(2)

R.<x> = PolynomialRing(F)

S.= R.quo((x^5-1)^2)

b=x^5-1 b^2;
SHOULD output [0] because the image of $(x^{5}-1)^2$ under the natural projection $\mathbb{F}_{2}[x] \to Q$ is exactly equal to the zero element of the quotient ring $Q$, but it does not yield that (it outputs the polynomial $x^{10}+1$, duh!). Do you know how it is that I am supposed to modify it in order to get the class in $Q$ to which the power in question belongs? Thanks in advance for your insightful replies!
edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2017-10-01 22:19:37 +0200

dan_fulea gravatar image

updated 2017-10-01 22:20:55 +0200

The given code could not be fully understood. (What is "output [0]"?)

However, the following way to view the things should be enough to proceed in the given case, and in a similar more general one.

We start with:

sage: F = GF(2)
sage: R.<x> = F[]
sage: factor( x^5-1 ) 
(x + 1) * (x^4 + x^3 + x^2 + x + 1)

So the ring obtained by taking $R$ modulo $(x^5-1)^2$ is isomorphic to $$ \mathbb F_2[x]/(x+1)^2\ \times \ \mathbb F_2[x]/(x^4 + x^3 + x^2 + x+1)^2\ .$$ (Chinese R.T.)

A an element in the cartesian product of rings is a unit iff each cartesian component of the element is a unit.

Let $P$ be irreducible in $R$. An element in $$ \mathbb F_2[x]/P^2$$ is a unit, iff its image in the field $ \mathbb F_2[x]/P$ is a unit, i.e. is not zero. (Since a polynomial $1+rP$ has the inverse $1-rP$ in the ring $R/(P^2)$.)

Some sample sage code:

sage: F = GF(2)
sage: R.<x> = F[]
sage: S.<u> = R.quotient( [ (x^5-1)^2 ] )
sage: u.is_unit()
sage: 1/u
sage: HF = Hom( S, F )
sage: f = HF( [F(1)] )
sage: f(u)
sage: F25.<v> = GF(2**4, modulus=x^4 + x^3 + x^2 + x + 1 ) 
sage: HF25 = Hom( S, F25 )
sage: g = HF25( [v] )
sage: g(u)
sage: # let us test if u^3+u+1 is a unit in S
sage: y = u^3 + u + 1
sage: f(y)
sage: f(y).is_unit()
sage: g(y)
v^3 + v + 1
sage: g(y).is_unit()
sage: y.is_unit()
sage: 1/y
u^9 + u^6 + u^4 + u^3 + u^2
sage: # let us compute the multiplicative order of y
sage: f(y).multiplicative_order()
sage: g(y).multiplicative_order()
sage: y^15
u^8 + u^7 + u^6 + u^5 + u^3 + u^2 + u
sage: y^30
sage: y^10
u^8 + u^2 + 1
sage: y^6

So the multiplicative order of $y=u^3+u+1$ was computed by mapping it to the two fields, compute there the multiplicative orders, take the lcm of them. (Well, the one field is simple, order is one for "each" unit.) Then compute the $y$--power of order this lcm. If it is one, this is the order. Else take the square. In our case, $y^{30}=1$ in $S$. But no divisor of $30$ "works instead", so the order is $30$.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2017-10-01 02:47:36 +0200

Seen: 221 times

Last updated: Oct 01 '17