2
$\begingroup$

Let for $n\ge 1, P_n(x)= 1+2x+3x^2+\cdots + nx^{n-1}$. Prove that for any distinct positive integers j and k, $P_j(x)$ and $P_k(x)$ are relatively prime.

The above problem is 2014 Putnam A5. Solutions can be found here. I have the following questions about the solutions:

  • In the first solution, how did they compute that $w^n = nw - n+1$? I tried using the fact that $z$ is not a nonnegative real number and $P_i(z)=P_j(z)=0,$ but I wasn't able to deduce this result.
  • In the second solution, I can't understand the proof of Corollary 2. In particular, how can one apply lemma 1 to the polynomial $f(x/R)$ if $x/R$ isn't necessarily a root of $f$? Also, even if $x/R$ were a root of $f,$ it doesn't seem like the resulting coefficients of the polynomial would be increasing, which is a requirement of lemma 1. I'm not sure how they get the bound $|z|\ge r$, for similar reasons.

I tried proving a variant of Corollary 2 where $a_i/a_{i+1}$ is replaced by $a_{i+1}/a_i$ in the definitions of $r$ and $R$, but even if this corollary holds, it doesn't seem like it's useful for the given problem.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

We're given

$$P_n(x) = 1+2x+3x^2+\cdots +nx^{n-1} \tag{1}\label{eq1A}$$

With the first linked solution, there's a complex $z$ and integers $i \neq j$, with $P_i(z)=P_j(z)=0$ and $w = z^{-1} \neq 0, 1$. Thus, $z = w^{-1}$ so, using \eqref{eq1A} with $P_i(w^{-1})$ and multiplying both sides by $w^{-1}$, we get

$$\begin{equation}\begin{aligned} 0 & = \color{blue}{1 + 2w^{-1} + 3w^{-2} + \cdots + iw^{-(i-1)}} \\ & = (w^{-1} + 2w^{-2} + 3w^{-3} + \cdots + (i-1)w^{-(i-1)}) + iw^{-i} \\ & = (\color{blue}{1 + 2w^{-1} + \cdots + iw^{-(i-1)}}) - (1 + w^{-1} + \cdots + w^{-(i-1)}) + iw^{-i} \\ & = 0 - \frac{1-w^{-i}}{1-w^{-1}} + iw^{-i} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Using $n = i + 1$, this gives

$$\begin{equation}\begin{aligned} \frac{1-w^{-i}}{1-w^{-1}} &= iw^{-i} \\ \frac{w^{i}-1}{1-w^{-1}} & = i \\ w^{i}-1 & = i(1- w^{-1}) \\ w^{i+1}-w & = i(w - 1) \\ w^{i+1} & = (i+1)w - (i + 1 - 1) \\ w^n & = nw - n + 1 \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

A corresponding result applies for $P_j(w^{-1})$. Note another way to get this is to instead use, for $x \neq 1$, that

$$f_n(x) = 1 + x + x^2 + \cdots + x^n = \frac{x^{n+1}-1}{x - 1} \tag{4}\label{eq4A}$$

to then get

$$P_n(x) = \frac{df_n(x)}{dx} = \frac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2} \tag{5}\label{eq5A}$$


Regarding Corollary $2$ of the second solution, we have

$$f(x) = a_0 + a_{1}x + \cdots + a_{n}x^{n} \tag{6}\label{eq6A}$$

Then the solution says to use $f(x/R)$, but it should be $f(Rx)$ instead, for this to then become

$$\begin{equation}\begin{aligned} f(Rx) & = a_0 + (Ra_{1})x + \cdots + (R^{n}a_{n})x^{n} \\ g(x) & = b_0 + b_{1}x + \cdots + b_{n}x^{n} \end{aligned}\end{equation}\tag{7}\label{eq7A}$$

where $g(x) = f(Rx)$ and

$$b_i = R^{i}a_i \; \forall \; 0 \le i \le n \tag{8}\label{eq8A}$$

Using $R = \max\{a_0/a_1,\ldots,a_{n-1}/a_{n}\}$, and \eqref{eq8A}, we then get for all $0 \le i \le n-1$ that

$$\begin{equation}\begin{aligned} R & \ge a_{i}/a_{i+1} \\ Ra_{i+1} & \ge a_{i} \\ R^{i+1}a_{i+1} & \ge R^{i}a_{i} \\ b_{i+1} & \ge b_{i} \end{aligned}\end{equation}\tag{9}\label{eq9A}$$

Since this meets the conditions of lemma $1$, all roots $z_1$ of $g(x)$ have $\lvert z_1 \rvert \le 1$. Thus, with $f(Rx)$, all of its corresponding roots $z = Rz_1$ have $\lvert z \rvert = \lvert Rz_1\rvert = R\lvert z_1\rvert \le R$.

Showing $r \le \lvert z \rvert$ can be done similarly, except $f(rx)$ should be used instead of $f(x/r)$. A similar procedure to \eqref{eq7A} and \eqref{eq8A} gives, with $x \neq 0$, that

$$f(rx) = h(x) = c_0 + c_{1}x + \cdots + c_{n}x^{n} = x^{n}(c_0(x^{-1})^{n} + c_1(x^{-1})^{n-1} + \cdots + c_{n}) \tag{10}\label{eq10A}$$

with $c_{i+1} \le c_{i} \; \forall \; 0 \le i \le n - 1$. As stated in the solution, the polynomial in reverse using $\frac{1}{x}$ gives a set of positive, non-decreasing coefficients, so lemma $1$ applies to give that all roots $\left\lvert \frac{1}{z_1}\right\rvert \le 1 \; \to \; \lvert z_1 \rvert \ge 1$. Thus, with $f(rx)$, we have the roots $z = rz_1$, so $\lvert z\lvert = \lvert rz_1\rvert = r\lvert z_1\rvert \ge r$.

$\endgroup$
2
  • $\begingroup$ Thanks. Could you look at this Dyck path/modular arithmetic problem if you have time? $\endgroup$
    – user33096
    Commented Dec 18, 2022 at 0:34
  • $\begingroup$ @user33096 You're welcome. I've looked at your other problem, but I don't offhand know of anything I can add to what you've already done there so far. Nonetheless, if I think of anything later, I will certainly add a comment and/or answer there then. $\endgroup$ Commented Dec 18, 2022 at 1:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .