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
...
I'd like to assign the solutions above to the respective variables:
x36=1, x44=0,x46=0 so that if I have another equation, say x44 + x2 ==
0, this equation will become x2 == 0 after the assignment.
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)? If yes, does this
necessarily mean that the system G (and hence e) is solvable for all
variables composing it?
Thanks a lot for your help.
Regards,
vpv
P.S. My code for computing G is:
N = 144
P = BooleanPolynomialRing(N, 'x',order='lex')
x=[]
for i in range(0,N):
x.append(P.gen(i))
E = [x[20] + x[15] + 1, x[21] + x[15] + 1, x[28] + x[15], x[29] +
x[15], x[63] + x[31] + x[15], x[63] + x[36], x[63] + x[37], x[63] +
x[39] + 1, x[63] + x[4\
4] + 1, x[63] + x[45] + 1, x[63] + x[46] + 1, x[79] + x[47] + 1, x[79]
+ x[20] + 1, x[79] + x[21] + 1, x[79] + x[28], x[79] + x[29], x[95] +
x[79] + x[31] +\
1, x[36] + 1, x[37] + 1, x[95] + x[39], x[44], x[45], x[95] + x[46],
x[95] + x[47] + x[111]]
I = ideal(E)
G=I.groebner_basis()
On Oct 14, 10:39 am, Martin Albrecht <[EMAIL PROTECTED]>
wrote:
> On Sunday 12 October 2008, vpv wrote:
>
>
>
> > Can someone please tell me why it is impossible to solve the following
> > system of boolean equations in SAGE:
>
> > sage: N=144
> > sage: P = BooleanPolynomialRing(N,'x',order='lex')
> > sage: t = []
> > sage: for i in range(0,N):
> > t.append(var(P.gen(i)))
> > sage: print "t",t
>
> > t [x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14,
> > x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28,
> > x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42,
> > x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56,
> > x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70,
> > x71, x72, x73, x74, x75, x76, x77, x78, x79, x80, x81, x82, x83, x84,
> > x85, x86, x87, x88, x89, x90, x91, x92, x93, x94, x95, x96, x97, x98,
> > x99, x100, x101, x102, x103, x104, x105, x106, x107, x108, x109, x110,
> > x111, x112, x113, x114, x115, x116, x117, x118, x119, x120, x121,
> > x122, x123, x124, x125, x126, x127, x128, x129, x130, x131, x132,
> > x133, x134, x135, x136, x137, x138, x139, x140, x141, x142, x143]
>
> > sage: e = [x20 + x15 + 1, x21 + x15 + 1, x28 + x15, x29 + x15, x63 +
> > x31 + x15, x63 + x36, x63 + x37, x63 + x39 + 1, x63 + x44 + 1, x63 +
> > x45 + 1, x63 + x46 + 1, x79 + x47 + 1, x79 + x20 + 1, x79 + x21 + 1,
> > x79 + x28, x79 + x29, x95 + x79 + x31 + 1, x36 + 1, x37 + 1, x95 +
> > x39, x44, x45, x95 + x46, x95 + x47 + x111]
>
> > sage: e
>
> > [x20 + x15 + 1,
> > x21 + x15 + 1,
> > x28 + x15,
> > x29 + x15,
> > x63 + x31 + x15,
> > x63 + x36,
> > x63 + x37,
> > x63 + x39 + 1,
> > x63 + x44 + 1,
> > x63 + x45 + 1,
> > x63 + x46 + 1,
> > x79 + x47 + 1,
> > x79 + x20 + 1,
> > x79 + x21 + 1,
> > x79 + x28,
> > x79 + x29,
> > x95 + x79 + x31 + 1,
> > x36 + 1,
> > x37 + 1,
> > x95 + x39,
> > x44,
> > x45,
> > x95 + x46,
> > x95 + x47 + x111]
>
> > sage: v = [x20, x21, x28, x29, x15, x63, x31, x36, x37, x39, x44, x45,
> > x46, x47, x79, x95, x111]
>
> > sage: s = solve(e,v)
>
> > sage-3.1.2/local/lib/python2.5/site-packages/sage/calculus/
> > equations.py in solve(f, *args, **kwds)
> > 1431 s = m.solve(variables)
> > 1432 except:
> > -> 1433 raise ValueError, "Unable to solve %s for %s"%(f,
> > args)
> > 1434 a = repr(s)
> > 1435 sol_list = string_to_list_of_solutions(a)
>
> > ValueError: Unable to solve [x20 + x15 + 1, x21 + x15 + 1, x28 + x15,
> > x29 + x15, x63 + x31 + x15, x63 + x36, x63 + x37, x63 + x39 + 1, x63 +
> > x44 + 1, x63 + x45 + 1, x63 + x46 + 1, x79 + x47 + 1, x79 + x20 + 1,
> > x79 + x21 + 1, x79 + x28, x79 + x29, x95 + x79 + x31 + 1, x36 + 1, x37
> > + 1, x95 + x39, x44, x45, x95 + x46, x95 + x47 + x111] for ([x20, x21,
> > x28, x29, x15, x63, x31, x36, x37, x39, x44, x45, x46, x47, x79, x95,
> > x111],)
>
> solve() is aimed at symbolic expressions and not boolean polynomials.
> Computing a lexicographical Gröbner basis should do the trick. (Maybe solve()
> should support boolean polynomials, but I'm not sure yet)
>
> 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
-~----------~----~----~----~------~----~------~--~---
