Facebook Page
Twitter
RSS
+ Reply to Thread
Page 1 of 2 12 LastLast
Results 1 to 10 of 17
  1. MHB Master
    MHB Site Helper
    Peter's Avatar
    Status
    Offline
    Join Date
    Jun 2012
    Location
    Hobart, Tasmania
    Posts
    2,863
    Thanks
    2,625 times
    Thanked
    895 times
    Awards
    MHB Model User Award (2018)  

MHB Model User Award (2015)  

MHB Model User Award (Jul-Dec 2013)
    #1
    i am studying finite fields and trying to get an idea of the nature of finite fields.

    In order to achieve this understanding I am bring to determine the elements and the addition and multiplication tables of some finite fields of small order.

    For a start I am trying to determine the elements andthe addition and multiplication tables of the finite field of order 8.

    Can someone show me how to get started on this problem?

    Peter

    ***EDIT*** Just reflecting that maybe I should have started with $ \displaystyle \mathbb{F}_2 \text{ and } \mathbb{F}_3 $ but $ \displaystyle \mathbb{F}_8 $ seemed a bit less "special" and more general!
    Last edited by Peter; July 19th, 2014 at 21:21.

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Location
    Advertising world
    Posts
    Many
     

  3. MHB Master
    MHB Site Helper
    MHB Math Scholar
    Deveno's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    just south of canada
    Posts
    1,967
    Thanks
    423 times
    Thanked
    4,380 times
    Thank/Post
    2.227
    Awards
    MHB Advanced Algebra Award (2015)  

MHB Advanced Algebra Award (Jul-Dec 2013)
    #2
    $\Bbb F_8$ will have a "medium-large" multiplication table (64 entries) but it's do-able with some patience. Ditto for addition.

    The key to creating such a table is finding an irreducible polynomial of degree 4 in $\Bbb Z_2[x]$, and expressing every element of $\Bbb F_8$ as $\Bbb Z_2$-linear combinations of $1,u,u^2,u^3$, where $u$ is a root of the irreducible polynomial you found. This will make the addition table easy.

    Now, if you happen to find an element $b \in \Bbb F_8$ of order 7, the multiplication table will be easy. Good luck!

    (Hint: try $x^4 + x^3 + x^2 + x + 1$. It clearly has no linear factors...does it have quadratic factors?).

  4. MHB Master
    MHB Global Moderator
    MHB Math Scholar
    MHB POTW Director
    Euge's Avatar
    Status
    Offline
    Join Date
    Jun 2014
    Posts
    1,883
    Thanks
    1,884 time
    Thanked
    4,945 times
    Thank/Post
    2.626
    Awards
    MHB Topology and Advanced Geometry Award (2017)  

MHB Analysis Award (2017)  

MHB Advanced Algebra Award (2016)  

MHB Topology and Advanced Geometry Award (2015)  

MHB Analysis Award (2015)
    #3
    I think Deveno's example has 16 elements. A model for $\mathbb{F}_8$ is $F := Z_2[x]/(x^3+x+1)$. Letting $u = x + (x^3+x+1)$, we have $u^3 = u + 1$ and we can write

    $F = \{0,1,u, u+1,u^2,u^2+1, u^2+u, u^2+u+1\}$.

    With this, you can make a table.

  5. MHB Master
    MHB Site Helper
    Peter's Avatar
    Status
    Offline
    Join Date
    Jun 2012
    Location
    Hobart, Tasmania
    Posts
    2,863
    Thanks
    2,625 times
    Thanked
    895 times
    Awards
    MHB Model User Award (2018)  

MHB Model User Award (2015)  

MHB Model User Award (Jul-Dec 2013)
    #4 Thread Author
    Quote Originally Posted by Deveno View Post
    $\Bbb F_8$ will have a "medium-large" multiplication table (64 entries) but it's do-able with some patience. Ditto for addition.

    The key to creating such a table is finding an irreducible polynomial of degree 4 in $\Bbb Z_2[x]$, and expressing every element of $\Bbb F_8$ as $\Bbb Z_2$-linear combinations of $1,u,u^2,u^3$, where $u$ is a root of the irreducible polynomial you found. This will make the addition table easy.

    Now, if you happen to find an element $b \in \Bbb F_8$ of order 7, the multiplication table will be easy. Good luck!

    (Hint: try $x^4 + x^3 + x^2 + x + 1$. It clearly has no linear factors...does it have quadratic factors?).

    Thanks Deveno think I get this BUT, just to be sure:

    You write:

    "The key to creating such a table is finding an irreducible polynomial of degree 4 in $\Bbb Z_2[x]$, and expressing every element of $\Bbb F_8$ as $\Bbb Z_2$-linear combinations of $1,u,u^2,u^3$, where $u$ is a root of the irreducible polynomial you found."

    What is the theorems/logic behind this reasoning?

    Peter

    - - - Updated - - -

    Quote Originally Posted by Euge View Post
    I think Deveno's example has 16 elements. A model for $\mathbb{F}_8$ is $F := Z_2[x]/(x^3+x+1)$. Letting $u = x + (x^3+x+1)$, we have $u^3 = u + 1$ and we can write

    $F = \{0,1,u, u+1,u^2,u^2+1, u^2+u, u^2+u+1\}$.

    With this, you can make a table.
    Thanks Euge appreciate your help!

    I guess the logic here is that $ \displaystyle \mathbb{F}_8 $ is isomorphic to $F := Z_2[x]/(x^3+x+1)$ so that you can use this 'model' to determine/calculate the elements of $ \displaystyle \mathbb{F}_8 $. Is that correct?

    What logic and results/theorems did you use to establish that $F := Z_2[x]/(x^3+x+1)$ was a 'model' for (isomorphic to) $ \displaystyle \mathbb{F}_8 $?


    Thanks again for your help.

    Peter

  6. MHB Master
    MHB Global Moderator
    MHB Math Scholar
    MHB POTW Director
    Euge's Avatar
    Status
    Offline
    Join Date
    Jun 2014
    Posts
    1,883
    Thanks
    1,884 time
    Thanked
    4,945 times
    Thank/Post
    2.626
    Awards
    MHB Topology and Advanced Geometry Award (2017)  

MHB Analysis Award (2017)  

MHB Advanced Algebra Award (2016)  

MHB Topology and Advanced Geometry Award (2015)  

MHB Analysis Award (2015)
    #5
    Yes, Peter, I meant $F$ is isomorphic to $\mathbb{F}_8$. I used the fact that the quotient of a commutative ring by a maximal ideal is a field to claim that $F$ is a field. Since $x^3+x+1$ is irreducible over $\mathbb{Z}_2$ (since it doesn't have any roots in $\mathbb{Z}_2$), the ideal $(x^3+x+1) $ is maximal in $\mathbb{Z}_2$. So I can use fact I mentioned to deduce that $F$ is a field.

  7. MHB Master
    MHB Site Helper
    Peter's Avatar
    Status
    Offline
    Join Date
    Jun 2012
    Location
    Hobart, Tasmania
    Posts
    2,863
    Thanks
    2,625 times
    Thanked
    895 times
    Awards
    MHB Model User Award (2018)  

MHB Model User Award (2015)  

MHB Model User Award (Jul-Dec 2013)
    #6 Thread Author
    Quote Originally Posted by Euge View Post
    Yes, Peter, I meant $F$ is isomorphic to $\mathbb{F}_8$. I used the fact that the quotient of a commutative ring by a maximal ideal is a field to claim that $F$ is a field. Since $x^3+x+1$ is irreducible over $\mathbb{Z}_2$ (since it doesn't have any roots in $\mathbb{Z}_2$), the ideal $(x^3+x+1) $ is maximal in $\mathbb{Z}_2$. So I can use fact I mentioned to deduce that $F$ is a field.

    Thanks Euge OK, yes but how did you figure that $ \displaystyle \mathbb{Z}_2 {x}/ (x^3 + x + 1} $ had 8 elements and further, how did you come up with this field in the first place what mental process did you work though ...

    Peter

  8. MHB Master
    MHB Global Moderator
    MHB Math Scholar
    MHB POTW Director
    Euge's Avatar
    Status
    Offline
    Join Date
    Jun 2014
    Posts
    1,883
    Thanks
    1,884 time
    Thanked
    4,945 times
    Thank/Post
    2.626
    Awards
    MHB Topology and Advanced Geometry Award (2017)  

MHB Analysis Award (2017)  

MHB Advanced Algebra Award (2016)  

MHB Topology and Advanced Geometry Award (2015)  

MHB Analysis Award (2015)
    #7
    To answer both your questions, Peter, let's consider the polynomial ring $\mathbb{Z}_p[x]$, where $p$ is a prime. Let $f(x)$ be any polynomial of degree $n$ in $\mathbb{Z}_p[x]$. Since $pg = 0$ for all $g \in Z_p$, it follows that $pv = 0$ for all $v$ in $\mathbb{Z}_p[x]/(f(x))$. So the factor ring $\mathbb{Z}_p[x]/(f(x))$ has the structure of a vector space over $\mathbb{Z}_p$. You can also see that $\mathbb{Z}_p[x]/(f(x))$ is a $\mathbb{Z}_p$-vector space by observing that it is a module over $\mathbb{Z}_p$ and $\mathbb{Z}_p$ is a field.

    Let

    $f(x) = a_0 + a_1 x + \cdots + a_n x^n$

    where $a_n \neq 0$. If $u = x + (f(x))$, then

    $u^n = -(a_0/a_n) - (a_1/a_n)u - \cdots - (a_{n-1}/a_n)u^{n-1}$.

    By the division algorithm for polynomials, it follows that every element of $\mathbb{Z}_p[x]/(f(x))$ can be represented uniquely as a polynomial in $\mathbb{Z}_p[u]$ of degree less than $n$. This shows that the set $\{1,u, u^2,\ldots,u^{n-1}\}$ is a $\mathbb{Z}_p$-basis for $\mathbb{Z}_p[x]/(f(x))$. Therefore $\mathbb{Z}_p[x]/(f(x))$ has $|\mathbb{Z}_p|^n = p^n$ elements. Choosing $f(x)$ to be irreducible will make $\mathbb{Z}_p[x]/(f(x))$ a field with $p^n$ elements.

    In the special case that $p = 2$ and $f(x) = x^3 + x + 1$, we get the field $F$ with 8 elements.
    Last edited by Euge; July 20th, 2014 at 02:16.

  9. MHB Master
    MHB Site Helper
    MHB Math Scholar
    Deveno's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    just south of canada
    Posts
    1,967
    Thanks
    423 times
    Thanked
    4,380 times
    Thank/Post
    2.227
    Awards
    MHB Advanced Algebra Award (2015)  

MHB Advanced Algebra Award (Jul-Dec 2013)
    #8
    Quote Originally Posted by Euge View Post
    I think Deveno's example has 16 elements. A model for $\mathbb{F}_8$ is $F := Z_2[x]/(x^3+x+1)$. Letting $u = x + (x^3+x+1)$, we have $u^3 = u + 1$ and we can write

    $F = \{0,1,u, u+1,u^2,u^2+1, u^2+u, u^2+u+1\}$.

    With this, you can make a table.
    My bad, for some reason I got $4\cdot 2( = 2^3)$ confused with $2^4$

    Quote Originally Posted by Peter View Post
    Thanks Euge OK, yes but how did you figure that $ \displaystyle \mathbb{Z}_2[x]/ (x^3 + x + 1} $ had 8 elements and further, how did you come up with this field in the first place what mental process did you work though ...

    Peter
    You only need an irreducible polynomial of the proper degree. For consider, we can write every element in:

    $\Bbb Z_2[x]/(x^3 + x + 1)$ as a coset of the form:

    $a + bx + cx^2 + (x^3 + x + 1)$

    This can be represented as the triple: $(a,b,c)$.

    We have two choices for $a$, two choices for $b$, two choices for $c$, giving $2 \cdot 2\cdot 2 = 8$ distinct cosets.

    (this is because we can for any polynomial, write:

    $p(x) = q(x)(x^3 + x + 1) + r(x)$, where $r(x) = a + bx + cx^2$ (possibly any of $a,b,c$ are 0)).

    So we can list the 8 elements of $\Bbb F_8$ as either:

    $(0,0,0) \iff 0$
    $(1,0,0) \iff 1$
    $(0,1,0) \iff u = x + (x^3 + x + 1)$
    $(1,1,0) \iff 1+u$
    $(0,0,1) \iff u^2$
    $(1,0,1) \iff 1+u^2$
    $(0,1,1) \iff u+u^2$
    $(1,1,1) \iff 1+u+u^2$

    **********

    Let's try to find an element of order 7.

    $u^2 \neq 1$ so $u$ is not order 2.
    $u^3 = 1+u$ (since $u^3 + u + 1 = 0$, so $u^3 + (u + u) + (1+1) = u + 1$, and the last two terms on the left are 0).

    So $u$ is not of order 3.

    $u^4 = u(u^3) = u(1+u) = u+u^2 \neq 1$
    $u^5 = u(u^4) = u(u+u^2) = u^2 + u^3 = 1+u+u^2$
    $u^6 = u(u^5) = u(1+u+u^2) = u+u^2+u^3 = 1+u+u+u^2 = 1+u^2$
    $u^7 = u(u^6) = u(1+u^2) = u+u^3 = 1+u+u = 1$

    so $u$ is an element of order 7.

    So, for example, to calculate:

    $(1+u)(1+u^2) = u^3u^6 = u^9 = u^2$.

    We could use $u^3 = 1+u$ to do this, too:

    $(1+u)(1+u^2) = (1+u^2) + u(1+u^2) = 1 + u^2 + u + u^3 = 1 + u + u^2 + 1 + u = (1 + 1) + (u + u) + u^2$

    $ = 0 + 0 + u^2 = u^2$.

  10. MHB Master
    MHB Site Helper
    MHB Math Scholar
    Deveno's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    just south of canada
    Posts
    1,967
    Thanks
    423 times
    Thanked
    4,380 times
    Thank/Post
    2.227
    Awards
    MHB Advanced Algebra Award (2015)  

MHB Advanced Algebra Award (Jul-Dec 2013)
    #9
    Some other things to consider with finite fields:

    Every field has a multiplicative identity, $1$.

    It follows that the subgroup of $(F,+)$ for a finite field $F$, generated by $1$ is a finite cyclic group. Thus, $1$ has finite additive order in $F$.

    Since this is an abelian group, we have a natural $\Bbb Z$-action:

    $\displaystyle k \cdot 1 = \sum_{i = 1}^k 1$, often written as:

    $k \cdot 1 = 1 + 1 + \cdots + 1$ ($k$ summands).

    Since $\langle 1\rangle$ is cyclic, every element can be written in this form.

    This action gives $\langle 1\rangle$ a natural ring multiplication, as:

    $(k\cdot 1)(m\cdot 1) = (km)\cdot 1$.

    It follows that $\langle 1\rangle \cong \Bbb Z_n$, for some integer $n$ (called the characteristic of $F$).

    Now we know $F$ contains no zero-divisors (since all non-zero elements are units, and units are NEVER zero-divisors, and vice versa). Hence our copy of $\Bbb Z_n$ inside $F$ likewise contains no zero-divisors.

    Hence, $n$ is prime. For emphasis: EVERY finite field has prime characteristic.

    We can thus regard $F$ as an extension of the ring $\Bbb Z_p$, for some prime $p$, and this defines a $\Bbb Z_p$-action on $F$:

    $(k \cdot 1)\cdot x = (k\cdot 1)x$ (the multiplication on the right, is that of $F$).

    As Euge notes, this means we have a vector space over the field $\Bbb Z_p$.

    As this vector space is finite, it must have a finite basis, say: $\{x_1,x_2,\dots,x_n\}$.

    This means every element of $F$ is UNIQUELY expressible as:

    $a_1x_1 + a_2x_2 +\cdots + a_nx_n$, for $a_1,a_2,\dots,a_n \in \Bbb Z_p$.

    Well, we can simply COUNT these elements: there are $p$ choices for each "coefficient" of the $x_j$, which gives us:

    $|F| = p^n$.

    So every finite field has $p^n$ elements for some prime $p$, and some natural number $n > 0$.

    So, for example, there is NO field that has 6 elements, or 12, or 15.

    One might wonder...well, how many fields of order $p^n$ are there? The answer is rather startling: exactly one (up to isomorphism).

    Not only is every finite field of order $p^n$, but for every $p$ and every $n$, there IS a field of that order, and every other field of that order is isomorphic to it.

    There is another surprising fact about finite fields: the multiplicative group of a finite field is CYCLIC.

    Finite fields have a simple subfield structure: for example, a finite field of order 16, has a very simple lattice of subfields:

    $\Bbb F_{16} - \Bbb F_8 - \Bbb F_2$.

    At this point you might want to hazard a guess about what the group $\text{Gal}(\Bbb F_{16}/\Bbb F_2)$ looks like, and try to conjecture what polynomial in $\Bbb F_2[x]$ that $\Bbb F_{16}$ might be the splitting field of.
    Last edited by Deveno; July 28th, 2014 at 02:07.

  11. MHB Master
    MHB Site Helper
    Peter's Avatar
    Status
    Offline
    Join Date
    Jun 2012
    Location
    Hobart, Tasmania
    Posts
    2,863
    Thanks
    2,625 times
    Thanked
    895 times
    Awards
    MHB Model User Award (2018)  

MHB Model User Award (2015)  

MHB Model User Award (Jul-Dec 2013)
    #10 Thread Author
    Quote Originally Posted by Euge View Post
    To answer both your questions, Peter, let's consider the polynomial ring $\mathbb{Z}_p[x]$, where $p$ is a prime. Let $f(x)$ be any polynomial of degree $n$ in $\mathbb{Z}_p[x]$. Since $pg = 0$ for all $g \in Z_p$, it follows that $pv = 0$ for all $v$ in $\mathbb{Z}_p[x]/(f(x))$. So the factor ring $\mathbb{Z}_p[x]/(f(x))$ has the structure of a vector space over $\mathbb{Z}_p$. You can also see that $\mathbb{Z}_p[x]/(f(x))$ is a $\mathbb{Z}_p$-vector space by observing that it is a module over $\mathbb{Z}_p$ and $\mathbb{Z}_p$ is a field.

    Let

    $f(x) = a_0 + a_1 x + \cdots + a_n x^n$

    where $a_n \neq 0$. If $u = x + (f(x))$, then

    $u^n = -(a_0/a_n) - (a_1/a_n)u - \cdots - (a_{n-1}/a_n)u^{n-1}$.

    By the division algorithm for polynomials, it follows that every element of $\mathbb{Z}_p[x]/(f(x))$ can be represented uniquely as a polynomial in $\mathbb{Z}_p[u]$ of degree less than $n$. This shows that the set $\{1,u, u^2,\ldots,u^{n-1}\}$ is a $\mathbb{Z}_p$-basis for $\mathbb{Z}_p[x]/(f(x))$. Therefore $\mathbb{Z}_p[x]/(f(x))$ has $|\mathbb{Z}_p|^n = p^n$ elements. Choosing $f(x)$ to be irreducible will make $\mathbb{Z}_p[x]/(f(x))$ a field with $p^n$ elements.

    In the special case that $p = 2$ and $f(x) = x^3 + x + 1$, we get the field $F$ with 8 elements.
    Thanks Euge most helpful a most important piece of logic for me was when you write:

    "This shows that the set $\{1,u, u^2,\ldots,u^{n-1}\}$ is a $\mathbb{Z}_p$-basis for $\mathbb{Z}_p[x]/(f(x))$. Therefore $\mathbb{Z}_p[x]/(f(x))$ has $|\mathbb{Z}_p|^n = p^n$ elements. Choosing $f(x)$ to be irreducible will make $\mathbb{Z}_p[x]/(f(x))$ a field with $p^n$ elements. "

    This links the degree of the minimal polynomial and the number of elements in $ \displaystyle \mathbb{Z}_p $ to the number of elements in the field of interest previously I was missing that link! ...

    Thanks again,

    Peter

Similar Threads

  1. Replies: 2
    Last Post: August 31st, 2013, 21:34
  2. Total order relations on a finite set
    By Fernando Revilla in forum Questions from Other Sites
    Replies: 7
    Last Post: June 10th, 2013, 18:51
  3. Finite Simple Group of Order Two
    By masters in forum Chat Room
    Replies: 0
    Last Post: May 6th, 2013, 15:33
  4. Integral closure in finite extension fields
    By pantboio in forum Linear and Abstract Algebra
    Replies: 1
    Last Post: March 20th, 2013, 14:57
  5. [SOLVED] Finite group of order 4n+2 then elements of odd order form a subgroup.
    By caffeinemachine in forum Linear and Abstract Algebra
    Replies: 4
    Last Post: December 5th, 2012, 18:14

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards