A very interesting polynomial problem that was longlisted for the IMO! 

1. Notice that it works for p(x)=x 2. Have a gut feeling that it will also work for powers of x. 3. Check for an arbitrary n that it indeed works for p(x)=x^n (not very hard) 4. Decide that you’re just gonna assume that there are no other solutions and that even if there are any, you can’t be bothered

0:01 I dunno why but I’ve read the problem on the thumbnail like : (prime number)(x-1)(prime number)(x+1) = (prime number)(x2-1) 10:07 Hey Michael, I was watching Bouldering at the Olympics and I was wondering at what time you will compete 😂

The proper way to deal with this problem is to write p(x) = a*x^n + q(x) where deg(q) < n. Then you compare coefficients on both sides of the equation and you'll get that deg(q) = 0

1:47 restarting windows

That was really elegant. Thank you very much!

What a nice problem. Thank you, professor!

5:38 if you suppose that p has a root then alpha could be complex. Why you didn't study the special complex case?(like i-1 , -i-1)

7:13 when you thought you did really well on the AP Bio exam but instead got a 4

Great explanation!

From 6:00 on, α = -1 + e^(2 i ​π θ) with θ rational will give a finite sequence of roots. You must take into account complex roots, as even the roots of real valued polynomials can be complex, and you are talking about any root of this polynomial. (More so, real-valued polynomials can have all imaginary roots) To resolve this issue, as mentioned in other commentaries (see Behnam Rohani), we can do the same trick to show that all (α - 1)^(2^k) -1 must also be roots. This means 1 and all α = +1 + e^(2 i ​π θ) with θ rational are the only numbers that yield a finite sequence. 0 is the only number satisfying both conditions.

brilliantly presented.

I think I found a different (maybe simpler?) method: Consider all the roots of P(x): r1, r2, ... The roots of the LHS are obviously r1 ± 1, r2 ± 1, ... The roots of the RHS must be the same, and for P(x^2 - 1) to equal 0, x^2 - 1 must be a root of P(x) Consider the (possibly complex) root of P(x) with the largest magnitude, let's call it rn Choose the root of the LHS, rn ± 1, with the plus-or-minus having the same sign as the real part of rn. Since rn±1 is a root of the LHS, it is also a root of the RHS. Thus P([rn±1]^2 - 1) = 0 The only values of P(x) that equal zero are its roots, therefore [rn ± 1]^2 - 1 = rk for some root rk of P(x) [rn ± 1]^2 - 1 = rk rn^2 ± 2rn + 1 - 1= rk rn(rn ± 2) = rk And since magnitudes are multiplicative: |rn||rn ± 2| = |rk| By our definition for rn, |rn| ≥ |rk| for all rk ∈ {r1, r2,...} And we chose the plus-or-minus to be in the same direction as the real part of rn, which means |rn ± 2| ≥ 2 > 1 (I'll leave showing that as HW) Multiplying those inequalities, we get |rn||rn ± 2| > |rk|, which is a contradiction, unless |rn| = |rk| = 0 Because its root with the greatest magnitude is 0, all the roots of P(x) must be zero. Therefore, P(x) = Ax^n As in the video, we can show A = 1 and that the constant polynomials P(x) = 0 or 1 work as well. It's also easy to show that all natural numbers work for n since: P(x - 1)P(x + 1) = P(x^2 - 1) (x - 1)^n (x + 1)^n = (x^2 - 1)^n [(x - 1)(x + 1)]^n = (x^2 - 1)^n (x^2 - 1)^n = (x^2 - 1)^n

I'll take a guess that this problem did not make it to the IMO because it doesn't admit non-trivial polynomials as solutions. Actual IMO problems generally do

Because you have to include complex numbers, you have to do it slightly differently... go in the opposite direction and say that if alpha is a root, so is (alpha + 1)^{1/2^n} - 1 for some complex 2^nth roots. The only way the sequence of such numbers can be finite is if alpha +1 is equal to 0 or 1, corresponding to roots of -1 or 0. You can then eliminate possible roots -1 as you did it there.

Impressive method!

There is a much simpler solution: Suppose the leading two terms of P(x) is ax^(n+k)+bx^n, then examine the expansion of P(x-1)P(x+1), we will have all the "diagonal terms" the same as P(x^2-1), like [a(x+1)^(n+k)][a(x-1)^(n+k)] = a(x^2-1)^(n+k). What's left over is the "cross term". Specifically we examine the cross term of the first two leading term: 2ab[(x+1)^k+(x-1)^k](x^2-1)^n. We can see that this will produce a term of x^(2n+k) which any other cross term is unable to produce. As a result we can concluded that 2ab must be 0. So P(x) is either a constant or a single term of X^n

Another way to accomplish the same result is to plug in \alpha -1 into the equation (assuming \alpha is a root of P(x) ), and according to the same reasoning as before, it tells us that (\alpha -1)^(2^k) -1 must be a root for P(x), but now, the only values of \alpha that don't make P(x) a polynomial with infinite terms are 0,1,2. Comparing it with the previous roots \alpha=0,-1,-2, they have only 0 in common, so P(x) only has a root of 0 (Why is that? Notice that any \alpha results in new roots (\alpha -1)^(2^k) -1 and (\alpha +1)^(2^k) -1, so the choices of \alpha=-1,-2 would create infinitely many roots using the first form, and \alpha=1,2 is also a problem considering the second form).

For the complex case, the answer would be the same. We already know immediately from video that the solution set is contained in the (unit circle + zero)(denoted S). Do the same trick with p(x+1). For x to be a solution, (x-1)^2-1 must also be a solution. There are only three points in S which remain in S after such transformation: 0, z, and z* (z’s conjugate). This means our solution set is contained in these 3 points. However, (z+1)^2-1 and (z*+1)^2-1 are not one of these 3 points so they are not solutions either. Only 0 can be the root.

I'm a customary viewer of this channel but I got amazed every time this guy hits the blackboard.

If first root is -1+e^(i*pi/2^k) for any k, then we get finite set of roots

A more rigorous justification for the "special" values of α is to argue that, for p(x) to have only a finite number of roots, some roots must be repeated, ie, (α+1)^2^k - 1 = (α+1)^2^m - 1 for some k>m>0. This implies that (α+1)^2^m((α+1)^(2^k-2^m) - 1) = 0, which implies that (α+1) = 0 or (α+1)^2 - 1 = 0, ie, α = -1, 0 or -2.

Any tips on learning functional equations ? Like a list of types of functional equations(like they have for diff eq) or any book recommendations?

Great stuff Michael. Side note, have you been watching Olympic climbing or olympics in general?

If we plug x=alpha-1 into the equation we also get zero so (alpha-1)^2^k-1 is also a root, there should have been x-1 and x-2 terms in p(x) but ofc it doesn't matter since the exponents would be zero as well...

If alpha+1 is a root of unity, then the list is also finite. I think a cleaner way of doing this is to let alpha be a root of greatest magnitude, so that all roots r of p satisfy |r|

if we assume that non-constant polynomials have at least one root, we must consider complex roots (note that even real polynomials can have complex roots). then, there are infinitely many choices for α making (α+1)^(2^k) stationary. Just start with say α+1 = -1 and keep taking square roots, α+1 = ±i, α+1 = (±1±i)/√2 and so on. All these will end in (α+1)^(2^k) = 1 for large enough k.

You can simplify the solution and also easily include complex roots (wich many pointed out made the proof incomplete) by substituting q(x) = p(x-1), then the equation is: q(x) * q(x+2) = q(x^2) so if r is a root of q then r^2 also is this means that roots must be either on unit circle or 0, because otherwise magnitude of r becomes larger/smaller anytime you square it, generating infinite roots we similarly write q(x) = A * (x-r1)^n * (x-r2)^m * ... each root will give us factor of (x-r)^n * (x+2-r)^n on the left side of the equation (x^2 - r)^n on the right side All the roots on the right side are in the form of +/- sqrt(r) so if r is on unit circle they also are on unit circle and if r=0 the roots are also 0 this means every root of the right side is either 0 or on unit circle On the left side we have factor x+2-r so it has a root r-2 We need to find r so that r-2 is either 0 or on unit circle, so it can appear also on the right side but since r is also either zero or on unit circle we know that real value of r

1:05 I expected you to say x^n for all natural n.

I did a similar thing, suppose you have a root x, then this implies roots x*(x+2) and x*(x-2). For any complex number either x+2 or x-2 has a modulus strictly larger than 1, showing that for each root there must exist another root with a strictly larger modulus, if the modulus of x is positive. So either there are infinitely many roots (p=0), no roots (p=constant), or the only root is 0 (p=ax^n). This reduces further to p=0, 1, x^n through standard algebra.

4:30 what i find interesting is that the number of roots approximatetly doubles each application. from a, you get (a+1)^2 - 1 and (a-1)^2 - 1 from those you get (a+1)^4-1, ((a+1)^2-2)^2-1, (a-1)^4-1, ((a-1)^2-2)^2-1 The number of newfound roots and old roots differ by only one at every step. 6:40 Notice here that -2 does not provide finitely many roots, as (-2-1)^2 = 9, and 9-2=7, 7^2=49, we have 48 as a root. Similarly, -1 cannot be a finite root, we get 3 as a root, and therefore 7 and so on. 9:17 The algebraic comparison agrees with the finding that -2 and -1 are not valid roots

The problem is interesting indeed!

essentially the idea should be: find constant solutions. assuming p isnt constant let x be a root, we find a sequence from constantly squaring which gives us infiite roots unless the process terminates, by splitting up the starting points you can find all the points that this sequence stops changing, we can then just check A(x-a1)^n(x-a2)^m... to see what powers work

P(x)=C or P(x) is polynomial having finite number of roots (including complex)P(x) = C => C^2=C => C=0 or C=1Now consider the case of P(x) having finite number of rootsLet m is maximal by absolute value root of P(x) (including complex) Then m^2+2m and m^2-2m are also roots of P(x) abs(m^2+2m) m=0 or abs(m+2)

or, you could realize that the product of any two solutions (polynomials p satisfying the equation) is again a solution, so you only have to examine polynomials of degree 1 (or 2 if you don't know complex numbers) and are done in like 5 minutes.

This is nice, but there is a solution which does not involve looking at the roots at all, which I think is easier to come up with on your own by trying some example p(x)s and seeing why they don't work, at least for me. First, we know p(x)=0 is a solution. Next, consider the case where p(x) is a nonzero polynomial. As explained in the video, p(x) must be monic, i.e. leading coefficient=1. Let p(x)=x^(n_1)+a_2*x^(n_2)+...+a_k*x^(n_k) be the polynomial, where n_1 > n_2 > ... > n_k >= 0 and a_2, ..., a_k are nonzero. There are two cases: (1) k=1, in which case p(x) is just x^(n_1), which, as discussed in the video, is a solution for all non-negative integers n_1=0 (2) k >= 2, in which case a_2 is nonzero. Using this assumption, we will show that p(x) is not a solution, which suffices to show the only solutions are p(x)=0 and p(x)=x^(n_1) Then, the first three terms of biggest degree in p(x-1)p(x+1) will be: (x-1)^(n_1)(x+1)^(n_1) + a_2(x-1)^(n_1)(x+1)^(n_2) + a_2(x-1)^(n_2)(x+1)^(n_1) + a_2^2*(x-1)^(n_2)(x+1)^(n_2) which simplifies to: (x^2-1)^(n_1) + a_2(x-1)^(n_1)(x+1)^(n_2) + a_2(x-1)^(n_2)(x+1)^(n_1) + a_2^2*(x^2-1)^(n_2) Next, the first two terms of biggest degree in p(x^2-1) will be: (x^2-1)^(n_1) + a_2(x^2-1)^(n_2) Subtract q(x)=(x^2-1)^(n_1) + a_2^2*(x^2-1)^(n_2) from both sides. Then, p(x-1)p(x+1) is left with: a_2(x-1)^(n_1)(x+1)^(n_2) + a_2(x-1)^(n_2)(x+1)^(n_1) plus several terms of degree less than 2n_2 and p(x^2-1) is left with: (a_2-a_2^2)(x^2-1)^(n_2) plus several terms of degree less than 2n_2. Since a_2 is nonzero, from inspection, we see that the degree of p(x-1)p(x+1)-q(x) is n_1+n_2 while the degree of p(x^2-1)-q(x) is at most 2n_2 (i say at most because it is possible that a_2-a_2^2=0, in which case p(x^2-1)-q(x) has degree less than 2n_2). Since n_1 > n_2, it follows that n_1+n_2 > 2n_2, so the degree of p(x-1)p(x+1)-q(x) is strictly greater than that of p(x^2-1)-q(x). Thus, p(x-1)p(x+1)-q(x) does not equal p(x^2-1)-q(x), so p(x-1)p(x+1) does not equal p(x^2-1), as was to be proven.

elegant.

If you let alpha=a root of unity -1 wouldn't that give finite options as well? I think they should specify that P has at least one real root.

Elegant sol

Let q(x)=p(x-1) so q(x)q(x+2)=q(x^2). If r is a root of q so is r^2. Hence r is 0 or on the unit circle. If r is a root then (r-2)^2 is a root, so 0 is not a root, and all roots are on the unit circle. The only r on the unit circle for which (r-2)^2 is on the unit circle is r=1. Hence the only nonconstant q are (x-1)^n, so p is constant or x^n. [extending another user’s comment].

Everyone: polynomials These guys: pOlYaLs

What about the case when P(x) doesn't have real roots? Unless maybe I misunderstood and alpha can be complex

Question: how to prove those solutions are the ONLY solutions? The given solution identifies only the set of p(x) solutions that have one or more real roots. What about possible polynomials that have NO real roots? (There AREN'T any that satisfy the functional equation, but how to prove that?)

What about complex roots?

What about complex roots? alpha=i-1 might also work...

I did not like this problem,but your explanation is great!

What about when alpha + 1 is a root 2^p of unity?

6:45 Wait, why can't it be A*x^l*(x+1)^m*(x+2)^2*Q(x) where Q(x) has no roots?

Clearly 0,1,x and powers of x satisfy this equation. Now check possibility of kx^n, for nonzero k. Then we can see this is possible only for k =1 Now check the possibilty of x^n +x^m.. which will lead to a relation(x+1/x-1)^n-m = -1., but this is not true for real x.. x has to be a complex number... So as a conclusion Solution.. 0 and non negative integral powers of real variable x. We dont want negative powers as we need polynomial solutions. Plz..give me suggestions for correction, if any

p^2(x^2 -1)

No HW today,go to the beach🏄‍♂️

My attempt before watching the video If deg P = 0, P(x) = 1 or P(x) = 0 If deg P != 0 deg P(x^2 + 1) = deg P + 1 deg (P(x-1)P(x+1)) = 2 deg P 2 deg P = deg P + 1 deg P = 1 P(x) = ax + b such that a(x - 1) + b + a(x + 1) + b = a(x^2 - 1) + b If x = 1 we have 2b + 2a = b, b = -2a If x = -1 we have 2b - 2a = b, b = 2a -2a = 2a, a = 0 and so is b, which contradicts deg P = 1. Thus there is no solution P where deg P != 0

Aren't there finitely many roots when alpha=(alpha+1)^(2^k)-1 for some k? And doesn't this introduce a new infinite class of solutions?

Great

Great answer. But I am curious - what if p(x)=0 does not have roots? Then there is no alpha such that p(alpha)=0 and there can be another possible p(x) s.

Well obviously if x≠+-1 p^2=p meaning p=0 or 1😎😎😎😎😎😎😎😎😎

What does it mean for a problem to be longlisted?

Alpha has to be e^(2piim/k)+1

You never proved the sequence ak = (α + 1)^2^k - 1; a0 = α has finitely many distinct values iff α is in {0, -1, -2}. Clearly, it doesn't work for α > 0 (the sequence is strictly growing) or for α < -1, but I don't think it's as clear that for, say, α in you don't get ai = aj for some i ≠ j as the sequence appears to be bounded in .

The sulution is actully wrong because alpha can be a complex number

hmm, what if p(x) has no real roots? if alpha is a complex number, (alpha+1)^(2^k)-1 can be equal to alpha for some value of k, and we won't necessarily have infinite roots. :/? Finding such values foe alpha is not that hard. alpha = (-3+i.sqrt(3))/2 is such a number, and alpha^4 = alpha. Needless to say, the quadratic x^2+3x+3 for which alpha is a root, does not have the property we are looking for. It's easy to show that the only linear p(x) = ax +b that has this property is p(x) = +-x and the only quadratic p(x) is p(x)= +-x^2. We can easily show that x^n and -x^n have this property, and c.x^n for c/= +-1 does not have this property. I can argue that if P(x) and Q(x) have this property, P+Q can never have it, unless P+Q=0. I was thinking that since x^n is a base for the vector space of polynomials and every other polynomial is a linear combination of x^n's, no other polynomial can have this property. But now I noticed that even that is not enough, because I have not shown if P or Q does not have this property what can happen. This problem wan not supposed to be this hard! I wonder if we can argue that if P does not have any real roots, P(x-1)P(x+1) can never be equal to P(x^2-1). I tried it, but I wasn't successful at all.

I think the detailed induction is unnecessary. Once we know that the roots are closed under the unary operation that adds one, squares and then subtracts one, let's compare that to the input. Given a complex number z other than -2, we have |(z+1)^2-1|=|z^+2z|=|z| |z+2|>|z|. Consequently, the set S of all magnitudes of zeros of p other than 0, -1, or -2 is a set of nonnegative real numbers that satisfies this property: For each r in S, there is some t in S such that t>r. It's well-known that any such set of real numbers is either empty or infinite, but one can given an easy argument if you wish, using if you prefer, induction, or some other fundamental approach. In a any case, that's why the polynomial p cannot have any zeros other than 0, -1, -2. From that, showing that either p=0 or p=1 is as shown. It's a nice problem, Michael. Thanks for your videos.

what about non-constant polynomials without any roots?

this polynomial does not have to have roots, right?

Polinom may have no roots

P(x)=x İts fitts too

Question unclear: polynomial over what ring?

At the stage when we determine alpha values to be 0, -1 or -2, don’t we have to prove that there are no more possibilities? I suppose that is a nitpick, but anyways

9:55 l can be any number, not just positive stuff

here is a question, you said alpha is root of p(x) then so is (alpha+1)^{2^k}-1 , you seem like assmuming alpha is real nubmer, but you have to prove it .

NOTE: BAD MATH FOLLOWS: p^2(x^2-1) = p(x^2-1) p^2 = p p = {0, 1} That's what I got from the thumbnail, where I just treated p as a variable. But I knew it was too simple, so p(x) must be functional notation. And, yet, it does get the right answer. Seems like one where how you do it is more important than the actual answer, which might be why the problem didn't make it in.

cool

Please try imo2021 q 2

Could you tell the year in which this appear🙄🙄

actually thats a bad place to stop, cuz there may be complex roots

Hi, I found a solution in a second : f(x)=x !!! ok, .....

sste video me gusta mucjo guapu guapuuuu jejejepreci presiii mipresi aldier mated four Life techers four love 😘💕😘💕💕😘 pon POUM heheeheh basinha bainga basinga dimitri aurtobjs gracies pel bideo NIGGA

?