A Canada EGMO TST problem

Question

The Canada EGMO TST was held around a month ago across the nation, and I wish to give a talk at local math club about the problems.

I was able to solve $4$ problems, but there is one problem that I simply have no idea how to approach. However I would very much like to go through all of them during the talk.

The problem is as follows:

At least $d$ coefficients of a polynomial $P(x)$ of degree $d$ with real coefficients are equal to 1. Find the maximal value of $d$ such that $P(x)$ has $d$ real roots.

The only thought I have about this problem is that if all coefficients were $1$, then all the roots are on the unit circle in $\mathbb{C}$, and $1$ is not a root, hence it can have at most $1$ real root, namely $-1$. But I have no idea how changing one of the coefficients would affect the distribution of the roots

Any hints or thoughts are appreciated.

Answer 1

This is a structure finder-structure avoider question, so we use those ideas to help us find constraints. I went into a lot more detail so that you can talk about solving this problem in a guided manner, instead of taking random stabs in the dark / being lucky. (EG It does not involve us guessing at the start that $d=4$ is the answer just because we stumbled on some polynomial that satisfies the conditions. It also shows how the constraints lead us to finding such a polynomial.)

Observation 1: To use Descarte Rule of Signs to minimize the number of positive and negative roots, we need a lot of the coefficients to be 0 in order for there to be few sign changes. Currently, $P(x)$ has a lot of non-zero coefficients, so what other polynomial can we consider?

Let the polynomial be $P(x) = 1 + x + \ldots + (1+A)x^k + \ldots + x^d$.
Observe that $(x-1) P(x) = x^{d+1} + Ax^{k+1} - Ax^k - 1 $. This is the polynomial with a lot of zero coefficients, so let's apply Descarte Rule of Signs to see what we can conclude.

Case 1: $ k \neq 0, d $. So we have 4 non-zero coefficients.
The naive direct application of Descartes tells us that

• Since there are 4 non-zero coefficients, there can be at most 3 sign changes irregardless of what their values are.
• Hence there are at most 3 positive roots (with multiplicity), and at most 3 negative roots (with multiplicity).
• So there are at most 6 real roots to $(x-1)P(x) = 0$.
• Thus at most 5 real roots to $P(x) = 0$.

Case 2: $ k = 0$ or $ d$
Since the number of terms is reduced, we will have fewer sign changes and hence fewer real roots. Henceforth, let's ignore this case and come back to it if needed (Spoiler: we won't need to).

Observation 2: Descarte Rule of signs tells us to hunt down those sign changes, so let's do so instead of just looking at the number of non-zero coefficients.

Let's study if all of those sign changes are possible. In particular, since the signs of $A(-x)^{k+1} $ and $ -A(-x)^k$ are the same, which means that there are at most 2 negative roots, so there are at most 4 real roots to $P(x) = 0$. (As you will see below, all of the other sign changes are indeed possible, though I encourage you to verify this for yourself at this stage).

Observation 3: Descarte Rule of Signs tells us we want a lot of sign changes. What values of $k$ and $A$ will allow for that?

Finally, we guess that the answer is indeed $d = 4$, and it remains to find such a polynomial. Let's revisit what constants will allow us to have the desired sign changes in $(x-1)P(x)$.

• To get the max of 3 positive roots (but then having to exclude $x=1$), we require 1/ $ A < 0 $ and 2/ hope we don't only have 1 positive root.
• To get the max of 2 negative roots, since $A<0$, we want 1/ $k$ is even and $k \neq 0, 4$, so $k = 2$, 2/ $d+1$ is odd, which is satisfied with $d=4$, and 3/ hope we don't have 0 negative roots.
• So we should be considering $x^4 + x^3 + x^2 + x + 1 = |A| x^2$.
  By AM GM, since $ x^4 + x^3 + x^2 + x + 1 \geq 5 x^2$, hence $|A| > 5$ is a necessary condition for (distinct) positive real roots.
• Furthermore, this $|A| > 5 $ condition is sufficient. EG By considering the graph of $f(x) = x^4 + x^3 + x^2 + x + 1$ and $g(x) = |A|x^2$, showing that $ f(-\infty) > g(-\infty), f(-1) < g(-1), f(0) > g(0), f(1) < g(1), f(\infty) > g(\infty)$, so there is a real root in each of those 4 regions.
  

Note: If you count roots with multiplicity, then $A = -5$ suffices. This is Umesh's construction.