Solving polynomial equations,hlep

[scn7th]

we assume a,b,c,d are unknown variables,whose solution are either 0 or 1.So a power of a variable equals to itself(e.g,a^(n)=a).Would u please help me find a proper way to sovle the following simultaneous equations whose solutions are either 0 or 1?
-d-c+cd+bd+bc+ac-bcd-acd-abd-2abc+2abcd=0...(1)
d-2bd-ad+abd-abc+b+bcd-1=0 ...(2)
-bd+bc+bcd-ab+abd-2abcd+acd-c=0 ...(3)
-a-bd-bc+2bcd+ad-2acd+ac=0 ...(4)
ps:Those equations are not Boolean Equations.They are just normal polynomial equations which share the same solution set with the Boolean ones.

 

[Bill Simpson]

Hint: Are there 16 sets of things that you could calculate, one at a time? Why would I say 16 sets of things? Why would that be interesting? What would they be?

That should be enough.
Perhaps someone brighter than I can see some brilliant algebraic insight to avoid this, but I am assuming the poster would not be able to get a hint that would let him see that for himself.

 

[NascentOxygen]

Hi scn7th! http://img96.imageshack.us/img96/5725/red5e5etimes5e5e45e5e25.gif
I found 2 solutions. Here's my working. ☺[/size][/color]

 

[scn7th]

Hint: Are there 16 sets of things that you could calculate, one at a time? Why would I say 16 sets of things? Why would that be interesting? What would they be?

That should be enough.
Perhaps someone brighter than I can see some brilliant algebraic insight to avoid this, but I am assuming the poster would not be able to get a hint that would let him see that for himself.

yes there are 16 sets of solutions.it is not hard to get the answer by exhaustive search method.But I'm tring to find an algerithm which is more effective than ES method.have u got any other way to solve it?
What's more,thank u for ur help

 

[scn7th]

Hi scn7th! http://img96.imageshack.us/img96/5725/red5e5etimes5e5e45e5e25.gif
I found 2 solutions. Here's my working. ☺[/size][/color]

thank u man .I have seen that website and it has got the answer.would u please tell me your method to sovle it?Is there any effective algerithm except the exhaustive search?
looking forward to ur reply.

 

[NascentOxygen]

.I have seen that website and it has got the answer.would u please tell me your method to sovle it?Is there any effective algerithm except the exhaustive search?
looking forward to ur reply.

I have no idea how wolfram alpha solves that set of equations. But it does a good job, don't you think?

Sorry, I can't help with a manual method, but I'll monitor this thread and hope someone can.

 

[scn7th]

I have no idea how wolfram alpha solves that set of equations. But it does a good job, don't you think?

Sorry, I can't help with a manual method, but I'll monitor this thread and hope someone can.

yes it does a good job.I'll try to figure out how it work and reply it to u as soon as I get sth new.my email address is scn7th@163.com.
many thanks.

 

[Curious3141]

Here's a teensy-weensy insight.

First, exclude the solution (1,1,1,1) by inspecting eqn (2). It's obvious that we'll be left with the inconsistency -1 = 0.

So we know at least ONE of those variables MUST be 0.

Let's first work on the case where exactly one of the variables is zero. I'm referencing the original set of equations here.

IF d = 0, then a=b=c=1.

In eqn(2),

-abc+b-1 =0

b(1-ac) = 1

b = 1 AND ac = 0, which is inconsistent with the assumed solution (1,1,1,0). So d = 0 CANNOT be a solution.

So put d = 1 into everything:

-1-c + c +b + bc +ac -bc-ac-ab-2abc+2abc = 0

which reduces to:

-1 + b - ab = 0

b(1-a) = 1

b = 1 AND a = 0

Substitute into eqn(3), c = 1

Hence the solution is (0,1,1,1).

Now, let's work on the case where at least TWO of the variables are zero.

If at least two are zero, all of the "triples" abc, acd, abd, bcd will become 0, as will the "quadruple" abcd.

That means the equations will reduce to:

-d -c +cd +bd +bc +ac = 0 ---eqn (1')
d - 2bd - ad +b -1 = 0 ---eqn (2')
-bd +bc -ab -c = 0 ---eqn(3')
-a -bd -bc +ad +ac =0 --eqn(4')

Consider eqn(2') and rearrange:
d + b = 2bd + ad + 1

ad is clearly non-negative. The MAX value of bd = 1, which leads to an inconsistency 1 = 3 + ad. So b and d cannot be 1 simultaneously.

If d = 0 and b = 0, then ad = -1, another inconsistency.

So (b = 0, d = 1) [possibility A] OR (b = 1, d = 0) [possibility B] are the only tenable solutions.

Let's try possibility A first. From eqn (3'):

c = 0

Substitute into eqn (1'):

-1 = 0 (inconsistency).

This is a contradiction. Hence possibility A is excluded.

Focus on possibility B. From eqn(3'),

c - a - c = 0 and hence a=0.

Put a = 0 into eqn (1'): c=0.

This leads to the solution (0,1,0,0), which can be verified to solve the original equations.

The complete solution set is therefore (0,1,1,1) and (0,1,0,0).

Et voila!

PS: My solution is contingent on the assumption that the variables are restricted to be 0 or 1. I don't know how to solve the general case, even the Diophantine one. But if we can make that assumption (as the OP stated), then we can prove that these are the only admissible solutions, which is useful to the OP, I think.

 

[scn7th]

Here's a teensy-weensy insight.

First, exclude the solution (1,1,1,1) by inspecting eqn (2). It's obvious that we'll be left with the inconsistency -1 = 0.

So we know at least ONE of those variables MUST be 0.

Now, let's SUPPOSE that at least TWO are zero. We can solve this case quite easily.

If at least two are zero, all of the "triples" abc, acd, abd, bcd will become 0, as will the "quadruple" abcd.

That means the equations will reduce to:

-d -c +cd +bd +bc +ac = 0 ---eqn (1')
d - 2bd - ad +b -1 = 0 ---eqn (2')
-bd +bc -ab -c = 0 ---eqn(3')
-a -bd -bc +ad +ac =0 --eqn(4')

Consider eqn(2') and rearrange:
d + b = 2bd + ad + 1

ad is clearly non-negative. The MAX value of bd = 1, which leads to an inconsistency 1 = 3 + ad. So b and d cannot be 1 simultaneously.

If d = 0 and b = 0, then ad = -1, another inconsistency.

So (b = 0, d = 1) [possibility A] OR (b = 1, d = 0) [possibility B] are the only tenable solutions.

Let's try possibility A first. From eqn (3'):

c = 0

Substitute into eqn (1'):

-1 = 0 (inconsistency).

This is a contradiction. Hence possibility A is excluded.

Focus on possibility B. From eqn(3'),

c - a - c = 0 and hence a=0.

Put a = 0 into eqn (1'): c=0.

This leads to the solution set (0,1,0,0), which can be verified to solve the original equations.

Let's work on the case where exactly one of the variables is zero.

IF d = 0, then a=b=c=1.

In eqn(2),

-abc+b-1 =0

b(1-ac) = 1

b = 1 AND ac = 0, which is inconsistent with the assumed solution (1,1,1,0). So d = 0 CANNOT be a solution.

So put d = 1 into everything.:

-1-c + c +b + bc +ac -bc-ac-ab-2abc+2abc = 0

which reduces to:

-1 + b - ab = 0

b(1-a) = 1

b = 1 AND a = 0

Test that on eqn(3), c = 1

Hence the solution is (0,1,1,1).

The complete solution set is (0,1,1,1) and (0,1,0,0).

Et voila!

Curious3141,thank u for ur detailed analysis.Indeed, I want to find algerithm to solve it by computer.I have got one algerithm but I don't know whether it is better than ES method.Here it is:
transform the set of equations into the following form:
a(c-cd-bd-2bc+2bcd)+cd+bd+bc-bcd-d-c=0...(5)
a(bd-d-bc)+b+bcd-1+d-2bd=0...(6)
a(bd-b-2bcd+cd)+bc-bd+bcd-c=0...(7)
a(d-1-2cd+c)+2bcd-bd-bc=0...(8)
then multiply(c-cd-bd-2bc+2bcd) to each of (6)(7)(8),
here we get:
-(cd+bd+bc-bcd-d-c)(bd-d-bc)+(c-cd-bd-2bc+2bcd) (b+bcd-1+d-2bd)=0...(9)
-(cd+bd+bc-bcd-d-c)(bd-b-2bcd+cd)+(c-cd-bd-2bc+2bcd) (bc-bd+bcd-c)=0...(10)
-(cd+bd+bc-bcd-d-c)(d-1-2cd+c)+(c-cd-bd-2bc+2bcd)(2bcd-bd-bc)=0...(11)
at last we eliminate a.but we must pay attention when the common factor of a in (5),which is c-cd-bd-2bc+2bcd,and the terms without a,which is cd+bd+bc-bcd-d-c.When they are both equal to 0,the equations (10)(11) are useless.
repeat the elimination until d=constant or 0=0.
here we can get:
0=0,which means d can be either 0 or 1.by using backsubsititution we can get a set of solutions.However ,this set of solutions is larger than the real one because the common factors of a,b or c and the terms without a,b or c can be both 0 during the elimination.
Then we can use ES method by putting back the set of solutions we have got to equations (6)(7)(8),to eliminate the false solutions.
The worst situation is the first common factor and the terms without a are both 0.The set of equations are euqal to:
a(c-cd-bd-2bc+2bcd)+cd+bd+bc-bcd-d-c=0...(5)
-(cd+bd+bc-bcd-d-c)(bd-d-bc)+(c-cd-bd-2bc+2bcd) (b+bcd-1+d-2bd)=0...(9)
0=0...(12)
0=0...(13)
the solutions we get from backsubsititution is still smaller than the ones we get from (5) by ES method(by putting 0,0,0,0;0,0,0,1;……1,1,1,1 into equation (5) to exam which one is the solution).However,this method depends greatly on the first common factor and I don't know the whole calculation is better or worse than the ES method.

 

[Curious3141]

Sorry, scn7th I have to be away from my PC, but I just wanted to let you know that I rearranged my solution to be more smooth-flowing. You quoted the pre-edit version, so please take note. '

I haven't been able to read through your solution, but mine is definitely an improvement on having to test all possibilities exhaustively if you're working by hand. Moreover, it constitutes a definitive proof that those are the only solutions possible contingent on your assumptions regarding the variables being either 0 or 1, a very important thing to do.

EDIT: However, if you're looking for a computer science algorithm to systematically solve it, I'm afraid I'm not the best person to help you. My method does depend on some intuitive and very human insights into the structure of the equations, tough to get a program to replicate that.

 

[chingkui]

If you really insist on using a general polynomial solving algebraic algorithm, then google "Grobner basis". In your case, testing all 16 combinations would be much easier.

 

[scn7th]

Sorry, scn7th I have to be away from my PC, but I just wanted to let you know that I rearranged my solution to be more smooth-flowing. You quoted the pre-edit version, so please take note. '

I haven't been able to read through your solution, but mine is definitely an improvement on having to test all possibilities exhaustively if you're working by hand. Moreover, it constitutes a definitive proof that those are the only solutions possible contingent on your assumptions regarding the variables being either 0 or 1, a very important thing to do.

EDIT: However, if you're looking for a computer science algorithm to systematically solve it, I'm afraid I'm not the best person to help you. My method does depend on some intuitive and very human insights into the structure of the equations, tough to get a program to replicate that.

Your method is just another good way to solve it by hand.Actually,my project is to solve a large set of equations with many variables and I have take the 4-variable set of equations as a simple example.I believe I have found the algerithms though they is not effectvie in my case,which are Wu's method and Grobner basis.
Thanks anyway!

 

[scn7th]

If you really insist on using a general polynomial solving algebraic algorithm, then google "Grobner basis". In your case, testing all 16 combinations would be much easier.

I have googled Grobner basis and found it useful in solving polynomial equations.Besides, I have also found Wu's method,which seems to be more proper to my euqations.thanks a lot for your hint!