Solving polynomial equations,hlep

  • Thread starter scn7th
  • Start date
  • Tags
    Polynomial
In summary: Consider eqn(2') and rearrange:d + b = 2bd + ad + 1ad 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 = 0Substitute into eqn (
  • #1
scn7th
7
0
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.
 
Last edited:
Mathematics news on Phys.org
  • #2
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.
 
  • #3
Hi scn7th! http://img96.imageshack.us/img96/5725/red5e5etimes5e5e45e5e25.gif [Broken]
I found 2 solutions. Here's my working.
 
Last edited by a moderator:
  • #4
Bill Simpson said:
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
 
  • #5
NascentOxygen said:
Hi scn7th! http://img96.imageshack.us/img96/5725/red5e5etimes5e5e45e5e25.gif [Broken]
I found 2 solutions. Here's my working.

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.
 
Last edited by a moderator:
  • #6
scn7th said:
.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.
 
  • #7
NascentOxygen said:
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.
 
  • #8
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! :biggrin:

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.
 
Last edited:
  • #9
Curious3141 said:
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! :biggrin:

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.
 
  • #10
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. :smile:'

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. :smile:
 
Last edited:
  • #11
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.
 
  • #12
Curious3141 said:
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. :smile:'

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

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!
 
  • #13
chingkui said:
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!
 

What is a polynomial equation?

A polynomial equation is an equation where the variable(s) and coefficients are raised to non-negative integer powers and combined using the operations of addition, subtraction, and multiplication.

How can I solve a polynomial equation?

To solve a polynomial equation, you can use various methods such as factoring, the quadratic formula, or the rational root theorem. The method used depends on the form of the equation and the degree of the polynomial.

What is the degree of a polynomial equation?

The degree of a polynomial equation is the highest power of the variable in the equation. For example, the degree of a polynomial equation 3x^2 + 2x + 5 is 2.

What are the different types of solutions for a polynomial equation?

A polynomial equation can have real or complex solutions. Real solutions are the values of the variable that make the equation true when plugged in. Complex solutions involve imaginary numbers and occur when the equation cannot be solved using real numbers.

Are there any shortcuts for solving polynomial equations?

Yes, there are some shortcuts for solving certain types of polynomial equations. For example, if the equation is a quadratic equation in the form ax^2 + bx + c = 0, you can use the quadratic formula to find the solutions. Additionally, if the equation is a binomial raised to a power, you can use the binomial theorem to expand and solve it.

Similar threads

Replies
3
Views
2K
Replies
9
Views
1K
  • Math POTW for Secondary and High School Students
Replies
1
Views
903
Replies
4
Views
920
  • General Math
Replies
3
Views
709
Replies
9
Views
1K
  • General Math
Replies
4
Views
1K
  • General Math
2
Replies
44
Views
4K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
Replies
1
Views
1K
Back
Top