Math Challenge by QuantumQuest #1

[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)$.

 

[Charles Link]

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

 

[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 :)

 

[Charles Link]

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 :)

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

 

[fresh_42]

... this looks like a very good start, but the last step of showing P(1)=0P(1)=0 P(1)=0 needs to be completed. ...

Four different solutions for a quadratic equation?

 

[Charles Link]

Four different solutions for a quadratic equation?

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.

 

[fresh_42]

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.

 

[zwierz]

t'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.

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

 

[stevendaryl]

Spoiler: Solution using complex roots of 1

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

 

[fresh_42]

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.

 

[mfb]

Edit: Ah, I missed the ⁵ in the original problem.
The proof in post 3 should be sufficient, although it could have added that those roots are all different.

 

[mfb]

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

 

[Charles Link]

Wait, why can we plug in 1?

I see why P(r) + r Q(r) + r² R(r) = 0, but why can we replace r by 1?

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.

 

[Charles Link]

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

 

[PeroK]

Spoiler

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!

 

[jostpuur]

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.

zwierz and Charles Link were speaking about the equation

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

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

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.

 

[PeroK]

zwierz and Charles Link were speaking about the equation

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

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.

 

[fresh_42]

zwierz and Charles Link were speaking about the equation

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

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.

 

[QuantumQuest]

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 :)

Do you need five equations?

 

[jostpuur]

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

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

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.

 

[QuantumQuest]

by the way, there is no need to assume P,Q,R to be polynomials. For example, nothing changes if we put $P,Q,R\in C^1(\mathbb{C},\mathbb{C})$

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

Do you need five equations?

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

 

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

The challenge just asks for polynomials.

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.

But what about my question

I am not interested in discussing of such things.

 

[fresh_42]

I am not interested in discussing of such things.

In this case you might consider not to waste your time at all. A forum is based on communication, not on show-offs.

 

[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 anyone contestant.

 

[jostpuur]

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

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?

 

[stevendaryl]

stevendaryl wrote his version of the same idea in #9, but unfortunately also he forgot to examine the relevant ranks and kernels seriously.

Actually, I got to the point of 4 homogeneous equations for the 3 quantities $P(1), Q(1), R(1)$. At that point, I just started algebraically solving--you know--use the first equation to solve for $P(1)$ in terms of $Q(1)$ and $R(1)$, plug that into the second. Solve the second equation for $Q(1)$ in terms of $R(1)$, and plug that into the 3rd equation. If you get all zeroes by the third step, although the derivation is messy and unenlightening.

My (incorrect, or at best incomplete) summary was just an attempt to spare readers from seeing boring high-school level algebra by trying to step back and reflect on the reason you get zero.

 

[QuantumQuest]

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 anyone contestant.

First I really appreciate the efforts to learn through the solutions posted. But let me clarify things. The challenge problem was posted with the purpose to be solved in an efficient and simple way, as it was originally given in a contest many years ago. There's absolutely no point for anyone to try the most cumbersome things conceived to solve it. My original solution (20+ years ago) as the other three I've worked out through years are all simple and there's no real need to use anything other than what the problem implies.