1. ## 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

-Emily

2. Originally Posted by mlemilys
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

-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.

3. 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....

4. Originally Posted by NonCommAlg

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

5. Originally Posted by mlemilys
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.$