Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving polynomial equations,hlep!

  1. Apr 19, 2012 #1
    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: Apr 19, 2012
  2. jcsd
  3. Apr 20, 2012 #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.
     
  4. Apr 20, 2012 #3

    NascentOxygen

    User Avatar

    Staff: Mentor

    Hi scn7th! http://img96.imageshack.us/img96/5725/red5e5etimes5e5e45e5e25.gif [Broken]
    I found 2 solutions. Here's my working.
     
    Last edited by a moderator: May 5, 2017
  5. Apr 22, 2012 #4
    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
     
  6. Apr 22, 2012 #5
    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: May 5, 2017
  7. Apr 22, 2012 #6

    NascentOxygen

    User Avatar

    Staff: Mentor

    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.
     
  8. Apr 22, 2012 #7
    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.
     
  9. Apr 22, 2012 #8

    Curious3141

    User Avatar
    Homework Helper

    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: Apr 22, 2012
  10. Apr 22, 2012 #9
    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.
     
  11. Apr 22, 2012 #10

    Curious3141

    User Avatar
    Homework Helper

    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: Apr 22, 2012
  12. Apr 22, 2012 #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.
     
  13. Apr 22, 2012 #12
    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!
     
  14. Apr 22, 2012 #13
    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving polynomial equations,hlep!
  1. Solving a polynomial (Replies: 8)

  2. Solving polynomial (Replies: 1)

  3. Polynomial Equation (Replies: 2)

Loading...