On Tuesday 14 October 2008, vpv wrote:
> Hello Martin,
>
> Thank you very much for your reply. As you suggested, I computed the
> lexicographical Gröbner basis of the ideal generated by the
> polynomials e. It is:
>
> G = [x15 + x111 + 1, x20 + x111, x21 + x111, x28 + x111 + 1, x29 +
> x111 + 1, x31 + x111, x39, x46, x47 + x111, x63 + 1, x79 + x111 + 1,
> x95, x36 + 1, x37 + 1, x44, x45]
>
> How can I now from the expression for G, obtain solutions in the form:
>
> x36 == 1
> x44 == 0
> x46 == 0
> ...
You'd loop over your Gröbner basis, extract the necessary information and
assign the variables. Ideally the variety command on an ideal would just work
(tm) but it doesn't work for boolean polynomials. Here's a workaround:
sage: sr = mq.SR(2,1,1,4,gf2=True,polybori=True)
sage: F,s = sr.polynomial_system()
sage: gb = F.groebner_basis()
sage: R = F.ring().cover_ring() # PolyBoRi -> Singular
sage: gb2 = [R(f) for f in gb]
sage: Ideal(gb2).variety()
[{s001: 1, s103: 1, s101: 0, x103: 0, s000: 1, x101: 0, k003: 0, k100: 1,
k001: 0, k200: 0, x200: 0, k202: 1, x202: 1, w102: 1, w100: 1, w201: 1, s002:
0, w203: 0, k101: 1, s102: 1, s100: 0, x102: 0, x100: 1, k002: 1, k000: 1,
x201: 1, k201: 0, x203: 1, k203: 0, k103: 0, w103: 1, k102: 1, w101: 1, w200:
0, s003: 0, w202: 1}]
> Two more questions: in general, is it true that if a Grobner basis
> exists for a given ideal, then at least one of the equations in the
> Grobner basis will depend on a single variable (e.g. the equation
> x37+1==0 in G above depends only on x37)?
A Gröbner basis always exists for ideal in the rings we're talking about. The
triangular shape (one equation will depend on a single variable, the next on
two etc.) is guaranteed for
- lexicographical Gröbner bases over
- zero-dimensional (finite number of solutions) and
- radical (f is in I for all f^n in I)
ideals.
The last two conditions are satisfied for ideals in the boolean polynomial
ring because they are equivalent to ideals over GF(2) with the field
polynomials added. So you're good and can expect the triangular shape.
> If yes, does this
> necessarily mean that the system G (and hence e) is solvable for all
> variables composing it?
Yes.
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: [EMAIL PROTECTED]
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
