# FeaturedChallenge Math Challenge by QuantumQuest #1

1. Mar 16, 2017

### Greg Bernhardt

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. Mar 16, 2017

@QuantumQuest Looks like a good problem. I tried working it for a few minutes=I don't see a simple solution. :) :)

3. Mar 16, 2017

### zwierz

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
4. Mar 16, 2017

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
5. Mar 16, 2017

### Staff: Mentor

Four different solutions for a quadratic equation?

6. Mar 16, 2017

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.

7. Mar 16, 2017

### 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.

8. Mar 16, 2017

### zwierz

I have checked that. The rank of the matrix=3

9. Mar 16, 2017

### stevendaryl

Staff Emeritus
Here's my approach:

We are given that

$P(x^5) + x Q(x^5) + x^2 R(x^5) = (1+x+x^2 + x^3 + x^4)S(x)$

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

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

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

$1, r, r^2, r^3, r^4$

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

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 $j=1,2,3,4$, we have $P((r^j)^5) + (r^j) Q((r^j)^5) + (r^j)^2 R((r^j)^5) = 0$. Since for any j, we have that $(r^j)^5 = 1$, then we have 4 equations:

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

So 1 is a zero of $P(x)$, which means $P(x)$ has a factor of $x-1$.

10. Mar 16, 2017

### 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.

11. Mar 16, 2017

### 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.

12. Mar 16, 2017

### Staff: Mentor

I missed the 5th power in the argument in the problem statement. See my edited post.

13. Mar 16, 2017

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.

14. Mar 16, 2017

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

15. Mar 16, 2017

### PeroK

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!

16. Mar 16, 2017

### jostpuur

$$\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)$$

Yes, it can be concluded by an application by the Vandermonde determinant formula. It implies that the determinant of the $3\times 3$ upper block is non-zero.

17. Mar 16, 2017

### PeroK

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
18. Mar 16, 2017

### 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.

19. Mar 16, 2017

### QuantumQuest

Do you need five equations?

20. Mar 16, 2017

### jostpuur

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
21. Mar 16, 2017

### QuantumQuest

and also what kind of roots are these? I didn't see any mention about those things.

22. Mar 16, 2017

### zwierz

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.

23. Mar 16, 2017

### 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.

24. Mar 16, 2017

### jostpuur

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 (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

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
25. Mar 16, 2017

### jostpuur

You are speaking about the polynomial $P(1) + zQ(1) + z^2R(1)$ where $z\in\mathbb{C}$. Why did fresh_42 speak about quotient rings?