Results 1 to 5 of 5

Math Help - gröbner bases help

  1. #1
    Junior Member
    Joined
    Sep 2008
    From
    Wilmington NC
    Posts
    30

    Cool gröbner bases help

    So... I am considering working with Gröbner bases and cryptanalysis for my thesis... and I have a mentor professor... but at the current moment I am unable to get in touch with him for help.

    As a summer seminar project I am giving a talk about the attached article. I have asked the only other professor that I consider knowledgeable in the subject matter and he was unable to help me with Question 1

    I seem to have run into a kink with the definition and last example on the bottom of page 5.

    1. I do not know what the plus is above the F in the definition
    2. I can not quite get how they reduced the polynomial to get what they got.
    Did they have to apply the algorithm twice?

    ALSO

    3. on page 7, why is LM(f2)=xyz^2?
    (which i think is sort of the same issue I am having in question 2)

    and if you're feeling generous....
    4. Do you think you could explain the Buchberger Algorithm in layman's terms.

    Thanks!
    -Emily

    Thanks for your help.
    -Emily
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by mlemilys View Post
    So... I am considering working with Gröbner bases and cryptanalysis for my thesis... and I have a mentor professor... but at the current moment I am unable to get in touch with him for help.

    As a summer seminar project I am giving a talk about the attached article. I have asked the only other professor that I consider knowledgeable in the subject matter and he was unable to help me with Question 1

    I seem to have run into a kink with the definition and last example on the bottom of page 5.

    1. I do not know what the plus is above the F in the definition
    2. I can not quite get how they reduced the polynomial to get what they got.
    Did they have to apply the algorithm twice?

    ALSO

    3. on page 7, why is LM(f2)=xyz^2?
    (which i think is sort of the same issue I am having in question 2)

    and if you're feeling generous....
    4. Do you think you could explain the Buchberger Algorithm in layman's terms.

    Thanks!
    -Emily

    Thanks for your help.
    -Emily
    that + in the second definition in page 5 indicates that h is a normal form of g. so you won't confuse it with just a reduction. in the example after the second definition, in page 5, h is actually a

    completely reduced form of g=x^2y+xy^2+y^2 (see page 6) and not just a normal form. if we want to find a normal form of g in that example it will be h=x+y^2+y. but we can also reduce

    g completely: g=(x+y)f_1 + f_2 +x+y+1. you see h=x+y+y is the one that the example gives. the S polynomials found in the second and third examples in page 7 are not correct.

    for example in the second example we actually have: S(f_1,f_2)=\frac{x^2yz^2}{4x^2z}f_1 - \frac{x^2yz^2}{xyz^2}f_2 = \cdots . the authors forgot about 4 in the denominator.

    you should also take a look at this, which is written by the creator of Grobner bases.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    From
    Wilmington NC
    Posts
    30
    so am i correct in assuming that the 1st example on pg 5 could be reduced again? but then i am unsure about which leading terms you would use to compute u and b...

    i suppose the question is how do you know when you have reached the reduced normal form?

    UPDATE: i worked through the example and understand the initial question regarding the 2nd example on p 5... i think i was making an algebra error...

    i and i believe you can not reduce any further in the example before that because you would end up with fractional monomials.... but then again 1/x could be written as x^(-1) which i think is still allowable so...
    HELP

    zomg- i am such a nincompoop, you referred me to that definition... derrrrr. thanks

    but stay tuned for more....
    Last edited by mlemilys; June 3rd 2009 at 12:45 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2008
    From
    Wilmington NC
    Posts
    30
    Quote Originally Posted by NonCommAlg View Post

    for example in the second example we actually have: S(f_1,f_2)=\frac{x^2yz^2}{4x^2z}f_1 - \frac{x^2yz^2}{xyz^2}f_2 = \cdots . the authors forgot about 4 in the denominator.
    are you sure about that in the paper the definition for computing the S-polynomial includes the LM(f), not the LT(f)...

    I am trying to get some answers from a book my professor gave me....
    Computational and Commutative Algebra 1, but the notation is so different I get confused...

    It is really nice to have someone to help me with this as my professor will be out the rest of the week. (assuming you offer me some more info)
    -thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by mlemilys View Post
    are you sure about that in the paper the definition for computing the S-polynomial includes the LM(f), not the LT(f)...
    the S-polynomial of f_1,f_2 is equal to \frac{m}{LT(f_1)}f_1 - \frac{m}{LT(f_2)}f_2, where m=\text{lcm}(LM(f_1),LM(f_2)). the idea of S-polynomial is to get rid of the leading terms of f_1,f_2. for an example,

    see section 6.3 in page 8 of the link i gave you in my previous post. as you see, in order to find the S-polynomial of f_1=xy-2y, \ f_2=2y^2-x^2, we first find m=xy^2. we also have

    LT(f_1)=xy, \ LT(f_2)=2y^2. thus the S-polynomial is \frac{xy^2}{xy}(xy-2y) - \frac{xy^2}{2y^2}(2y^2-x^2)=\frac{x^3}{2}-2y^2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bases
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: July 20th 2010, 11:45 PM
  2. bases
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 22nd 2009, 08:30 AM
  3. Gröbner base for some lexicographic order
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 7th 2008, 08:04 PM
  4. Grlex and Gröbner
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 7th 2008, 07:26 PM
  5. Bases
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: April 21st 2005, 06:35 AM

Search Tags


/mathhelpforum @mathhelpforum