1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Featured Challenge Math Challenge by QuantumQuest #1

  1. Mar 16, 2017 #1
    Submitted by: @QuantumQuest
    Credit to: @stevendaryl

    RULES:

    1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
    2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
    3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
    4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

    CHALLENGE:
    Prove that if ##P(x), Q(x), R(x)## and ##S(x)## are all polynomials such that ##P(x^{5}) + xQ(x^{5}) + x^{2}R(x^{5}) = (x^{4} + x^{3} + x^{2} + x + 1)S(x)##, ##x - 1## is factor of ##P(x)##.
     
    Last edited: Mar 17, 2017
  2. jcsd
  3. Mar 16, 2017 #2

    Charles Link

    User Avatar
    Homework Helper
    Gold Member

    @QuantumQuest Looks like a good problem. I tried working it for a few minutes=I don't see a simple solution. :) :)
     
  4. Mar 16, 2017 #3
    Let ##\sigma_1=1,\sigma_2,\ldots,\sigma_5## be all the roots of the polynomial ## x^5-1##. Then ##\sigma_2,\ldots,\sigma_5## are the roots of the polynomial ##x^4+x^3+x^2+x+1##. Substitute these roots to our equality:
    $$P(1)+\sigma_jQ(1)+\sigma_j^2R(1)=0,\quad j=2,3,4,5$$
    This system of linear equations must imply $$P(1)=Q(1)=R(1)=0$$ I guess :)
     
    Last edited: Mar 16, 2017
  5. Mar 16, 2017 #4

    Charles Link

    User Avatar
    Homework Helper
    Gold Member

    If I may give an input here (I'm not really a judge=besides @QuantumQuest the judging is sort of being done by committee), this looks like a very good start, but the last step of showing ## P(1)=0 ## needs to be completed. If you write out the equations for ## j=2, \, j=3, \, and \, j=4 ##, you can get an answer for what ## P(1), Q(1), \, and \, R(1) ## needs to be. (By substitution method of the 3 equations and 3 unknowns.) I think it is then possible to show that this solution for ## P(1), Q(1), and \, R(1) ## is inconsistent with the 4th equation (## j=5 ##). This would likely result in the requirement that ## P(1)=Q(1)=R(1)=0 ## as @zwierz has conjectured. ## \\ ## Editing... I need to brush up on solutions for a set of linear homogeneous equations, but in any case, I do think the conjecture put forth by @zwierz is likely to be the case).
     
    Last edited: Mar 16, 2017
  6. Mar 16, 2017 #5

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    Four different solutions for a quadratic equation?
     
  7. Mar 16, 2017 #6

    Charles Link

    User Avatar
    Homework Helper
    Gold Member

    It's a set of linear equations with constant coefficients. Without checking it explicity, it is possible that a couple of the four equations could get repeated, etc.
     
  8. Mar 16, 2017 #7

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    It's a quadratic equation over a field with four different solutions. ##P(1) = P(x^5)## modulo ##(x^4+x^3+x^2+x+1)## is a scalar.
     
  9. Mar 16, 2017 #8
    I have checked that. The rank of the matrix=3
     
  10. Mar 16, 2017 #9

    stevendaryl

    User Avatar
    Staff Emeritus
    Science Advisor

    Here's my approach:

    We are given that

    [itex]P(x^5) + x Q(x^5) + x^2 R(x^5) = (1+x+x^2 + x^3 + x^4)S(x)[/itex]

    Now, having done a lot of power series, I recognize that [itex]1+x+x^2 + x^3 + x^4 = \frac{1-x^5}{1-x}[/itex]. (To prove this, multiply both sides by [itex]1-x[/itex]). So let me rewrite our equation as follows:
    [itex]P(x^5) + x Q(x^5) + x^2 R(x^5) = \frac{1-x^5}{1-x} S(x)[/itex]

    So what that means is that if [itex]x \neq 1[/itex] but [itex]x^5 = 1[/itex], then the right-hand side is 0. Wait a minute! How can [itex]x^5 = 1[/itex] unless [itex]x=1[/itex]? If you use complex numbers, there are 5 fifth-roots of 1!

    Let [itex]r = e^{2 \pi i/5}[/itex]. Then our 5 roots of 1 are:

    [itex]1, r, r^2, r^3, r^4[/itex]

    Raise any of those to the 5th power, and you get [itex]r^{5n} = e^{2 n \pi i} = 1[/itex] for [itex]n=0,1,2,3,4[/itex].

    So letting x be any of the roots (other than 1) will make the right-hand side equal to zero. That means that it also makes the left-hand side zero. So for each [itex]j=1,2,3,4[/itex], we have [itex]P((r^j)^5) + (r^j) Q((r^j)^5) + (r^j)^2 R((r^j)^5) = 0[/itex]. Since for any j, we have that [itex](r^j)^5 = 1[/itex], then we have 4 equations:

    1. [itex]P(1) + r Q(1) + r^2 R(1) = 0[/itex]
    2. [itex]P(1) + r^2 Q(1) + r^4 R(1) = 0[/itex]
    3. [itex]P(1) + r^3 Q(1) + r^6 R(1) = 0 \Rightarrow P(1) + r^3 Q(1) + r R(1) = 0[/itex] (since [itex]r^6 = r^5 \cdot r = r[/itex])
    4. [itex]P(1) + r^4 Q(1) + r^8 R(1) = 0 \Rightarrow P(1) + r^4 Q(1) + r^3 R(1) = 0[/itex] (since [itex]r^8 = r^5 \cdot r^3 = r^3[/itex])
    This is 4 equations and only 3 unknowns, so the only possible solution is the trivial one: [itex]P(1) = Q(1) = R(1) = 0[/itex].

    So 1 is a zero of [itex]P(x)[/itex], which means [itex]P(x)[/itex] has a factor of [itex]x-1[/itex].
     
  11. Mar 16, 2017 #10

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    I still think post #3 is a complete and sufficient proof. Passing to ##\mathbb{Q}[x]/(x^4+x^3+x^2+x+1)## and using the irreducibility (thus being prime) solves the equation at once.
     
  12. Mar 16, 2017 #11

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Edit: Ah, I missed the 5 in the original problem.
    The proof in post 3 should be sufficient, although it could have added that those roots are all different.
     
  13. Mar 16, 2017 #12

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    I missed the 5th power in the argument in the problem statement. See my edited post.
     
  14. Mar 16, 2017 #13

    Charles Link

    User Avatar
    Homework Helper
    Gold Member

    The ## x=\sigma_j ## for some j is used to make the 4 equations. The coefficient of ## S(x) ##, (x^4+x^3+x^2+x+1), is zero for any choice of j=2,3,4,5. Meanwhile ## \sigma_j^5=1 ## for all j.
     
  15. Mar 16, 2017 #14

    Charles Link

    User Avatar
    Homework Helper
    Gold Member

    We need to hear from @QuantumQuest , but I think the general consensus is that @zwierz has successfully solved it.
     
  16. Mar 16, 2017 #15

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Let ##P(x) = a_0 + a_1x + \dots a_n x^n## and ##S(x) = b_0 + b_1x + \dots b_m x_m##

    By comparing coefficients of ##x^0## we have:
    ##a_0 = b_0##

    Also, we have:

    ##a_1 = b_5 - b_0##

    To get this, compare the coefficients of ##x^3, x^4## and ##x^5##:

    ##x^3: \ 0 = b_0 + b_1 + b_2 + b_3## hence ##b_1 + b_2 + b_3 = -b_0##
    ##x^4: \ 0 = b_0 + b_1 + b_2 + b_3 + b_4## hence ##b_4 = 0##
    ##x^5: \ a_1 = b_1 +b_2 + b_3 + b_4 + b_5## hence ##a_1 = b_5 - b_0##

    Next: ##a_2 = b_{10} - b_5##

    ##x^8: \ 0 =b_4 + b_5 + b_6 + b_7 + b_8## hence ##b_6 + b_7 + b_8 = -b_5##
    ##x^9: \ 0 = b_5 + b_6 + b_7 + b_8 + b_9## hence ##b_9 = 0##
    ##x^{10}: \ a_2 = b_6 +b_7 + b_8 + b_9 + b_{10}## hence ##a_2 = b_{10} - b_5##

    The same argument applies for all coefficients modulo 5, giving, for ##k > 0##:

    ##a_k = b_{5k} - b_{5(k-1)}##

    This gives:

    ##a_0 + a_1 + \dots + a_n = b_{5n}##

    But, also ##b_{5(n+1)} = a_{n+1} + b_{5n} = b_{5n}##

    Hence ##b_{5k} = b_{5n}## for all ##k > n##, and so all these must be ##0##. So, finally we have:

    ##a_0 + a_1 + \dots + a_n = 0##, ##P(1) = 0## and ##(x-1)## is a factor of ##P(x)##.

    There must be a cleverer way!
     
  17. Mar 16, 2017 #16
    zwierz and Charles Link were speaking about the equation

    [tex]
    \left(\begin{array}{ccc}
    1 & \sigma_2 & \sigma_2^2 \\
    1 & \sigma_3 & \sigma_3^2 \\
    1 & \sigma_4 & \sigma_4^2 \\
    1 & \sigma_5 & \sigma_5^2 \\
    \end{array}\right)
    \left(\begin{array}{c}
    P(1) \\ Q(1) \\ R(1) \\
    \end{array}\right)
    = \left(\begin{array}{c}
    0 \\ 0 \\ 0 \\ 0 \
    \end{array}\right)
    [/tex]

    Yes, it can be concluded by an application by the Vandermonde determinant formula. It implies that the determinant of the [itex]3\times 3[/itex] upper block is non-zero.
     
  18. Mar 16, 2017 #17

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No need for linear algebra. I agree with @fresh_42

    ##P(1) + \sigma_j Q(1) + \sigma_j^2 R(1) = 0##

    is a quadratic in ##\sigma_j##, with at most ##2## distinct solutions for ##\sigma_j##.

    The 5th roots of 1 are clearly distinct.
     
    Last edited: Mar 16, 2017
  19. Mar 16, 2017 #18

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    I know. However, it's simply not necessary. To be honest this was how far I came, too. But the clue in post #3 doesn't need it. All that is really needed, is the fact, that the quotient ring doesn't have zero divisors and the extension is separable.
     
  20. Mar 16, 2017 #19

    QuantumQuest

    User Avatar
    Science Advisor
    Gold Member

    Do you need five equations?
     
  21. Mar 16, 2017 #20
    I see. The comments about polynomial division confused me. What was the point of those?

    Anyway, I think that three different solutions to the challenge can now be found from what has been written above.
     
    Last edited: Mar 16, 2017
  22. Mar 16, 2017 #21

    QuantumQuest

    User Avatar
    Science Advisor
    Gold Member

    The challenge just asks for polynomials. But what about my question

    and also what kind of roots are these? I didn't see any mention about those things.
     
  23. Mar 16, 2017 #22
    first I restore my remark: by the way, there is no need to assume P,Q,R to be polynomials. For example, nothing is changed if we put all the functions to be analytic or even of ##C^1(\mathbb{C},\mathbb{C})##, many different variants are also possible.

    I think that you should construct a formulation which would not admit so many ways to solve the problem.This makes it more trivial than it really is. For example, the solution from #15 is based upon hypothesis that all the functions are polynomials. Such a type solution can be excluded by proper formulation of the problem.

    I am not interested in discussing of such things.
     
  24. Mar 16, 2017 #23

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    In this case you might consider not to waste your time at all. A forum is based on communication, not on show-offs.
     
  25. Mar 16, 2017 #24
    I have now understood everything else from this thread but not the comments related to quotient rings.

    Despite that little gap in my understanding, I think I can safely judge that it is PeroK who was the first to give a proper answer to the challenge in hist post #15. His solution is not the nicest possible, and it did not get any responses, but it is correct after all, and I'm afraid that that earned the gold medal.

    fresh_42 was apparently the fastest one to realize how to prove the claim, but he did not post his proof for others see. It can be deduced from the post #5 that he could not have written that question if he had not already discovered a solution to the challenge. However, the rules of the challenge don't state that you can win the challenge by dropping a little piece of information, that eventually implies that the you must have known a solution. Sorry :wink: (Well, perhaps winning challenges isn't that important to mentors...)

    The proof attempt of zwierz got lot of attention, but he attempted the proving too quickly, and the original proof attempt contained a major gap concerning the ranks and kernels of certain matrices. In his post #8 zwierz guarantees that he has successfully filled the gap of the original proof attempt, but unfortunately he forgot to reveal how he proved his rank claim, and that means that he was not conforming to the rules of the challenge. Rules are rules, sorry :wink:

    stevendaryl wrote his version of the same idea in #9, but unfortunately also he forgot to examine the relevant ranks and kernels seriously. Although counting the numbers of parameters and checking sizes of matrices (i.e. numbers of columns and rows) is a good start, serious results concerning ranks and kernels cannot be replaced by a mere examination of matrix sizes.

    I was the one to point out in #16 that Vandermonde determinant formula could be used to deal with the remaining gap, but at that point that proof did not anymore belong any one contestant.
     
    Last edited: Mar 16, 2017
  26. Mar 16, 2017 #25
    You are speaking about the polynomial [itex]P(1) + zQ(1) + z^2R(1)[/itex] where [itex]z\in\mathbb{C}[/itex]. Why did fresh_42 speak about quotient rings?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted