August 2023 – A Point of View.

Composition of Polynomials

Let me share with you an observation I discovered recently that helps solve some difficult looking Olympiad problems. Suppose we have two polynomials, say, $P$ and $R$ that are with real coefficients and the degree of $P$ is multiple of the degree of $R.$ Let for example the degree of $P$ be $k\ell$ and the degree of $R$ be $\ell$ . Then it turns out that it holds

$\displaystyle P(x)=R(T(x) +\Delta (x)) \qquad (1)$

where $T(x)$ is a polynomial with real coefficients of degree $k$ and $\Delta(x)$ is a function satisfying $\displaystyle \lim_{|x|\to \infty} \Delta(x)=0.$
In what follows, I plan to prove it and illustrate how it helps solve two Olympiad problems, the first one given at Romanian Master of Mathematics, 2023.

We can choose real numbers $a_0, a_1,\dots,a_k$ so that the two polynomials:

$\displaystyle R(a_0y^k+a_1y^{k-1}+\dots+a_{k-1}y+a_k)\qquad (2)$

and $P(y)$ have the same coefficients in front of $y^{k\ell}, y^{k\ell-1},\dots, y^{k\ell-k}$ . It can be done by consecutively determining the coefficients $a_0,a_1,\dots a_k$ . Next, we can write

$\displaystyle P(y)=R\big(a_0y^k+a_1y^{k-1}+\dots+a_{k-1}y+a_k + \Delta(y)\big)\qquad (3)$

where $\Delta(y)$ is some quantity that can be uniquely determined in case $|y|$ is sufficiently large, since $R$ is monotonic for large $|y|$ . We claim that $\Delta(y)\to 0$ as $|y|\to\infty$ . Indeed, assume on the contrary, it’s not the case. Then there will be $\varepsilon>0$ and infinitely many $y$ with magnitude as large as we want such that $|\Delta(y)|\ge \varepsilon$ . Let $a_k':=a_k+\Delta(y)$ . Then

$\displaystyle R\big(a_0y^k+a_1y^{k-1}+\dots+a_{k-1}y+a'_k\big)-P(y)\qquad(4)$

would be a polynomial of degree $k\ell-k$ and with a senior coefficient of magnitude at least $C\cdot \varepsilon$ for some constant $C$ . This means that it’s not possible $(4)$ be zero for large enough $|y|$ .

Problem 1 (RMM 2023, p5). Let $P,Q,R,S$ be non constant polynomials with real coefficients, such that $P(Q(x))=R(S(x))$ and the degree of $P$ is multiple of the degree of $R.$ Prove that there exists a polynomial $T$ with real coefficients such that

$\displaystyle P(x)=R(T(x))$

Solution. As shown, there exists a polynomial $T(y)$ such that

$\displaystyle P(y)=R\big(T(y)+\Delta(y)\big)$

where

$\displaystyle \lim_{y\to\pm\infty} \Delta(y)=0.$

Putting $y:=Q(x)$ yields

$\displaystyle R(S(x))=P(Q(x))=R(T(Q(x)) +\Delta(Q(x))).$

It follows

$\displaystyle S(x)=T(Q(x)) +\Delta(Q(x))$

which means that $S(x)=T(Q(x))$ since otherwise it’s impossible that $\Delta(Q)\to 0$ as $Q\to \pm\infty$ . $\square$

Problem 2. (AoPS [2]). Let $P\in\mathbb{Z}[X]$ be a polynomial with even degree such that its leading coefficient is a perfect square and there exists an infinite amount of integers $k$ such that $P(k)$ is a perfect square. Prove that there exists a polynomial $Q$ with integer coefficients such that $P(x)=Q(x)^2.$

Solution. Let $\deg(P)=2n$ . We apply $(1)$ to $R(u)=u^2.$ Thus, there exists a polynomial $Q(x)=a_0x^n+a_1x^{n-1}+\dots +a_0$ with rational coefficients such that the two polynomials

$\displaystyle (a_0x^n+a_1x^{n-1}+\dots + a_n)^2$

and $P(x)$ have the same coefficients in front of $x^{2n},x^{2n-1},\dots,x^n$ . One can see that in this particular case the coefficients must be rational since they are obtained by consecutively solving linear equations with integer coefficients. We can write

$\displaystyle P(x)=(a_0x^n+a_1x^{n-1}+\dots + a_n+\Delta(x))^2$

where $\displaystyle \Delta(x)\to 0$ as $|x|\to\infty,$ according to $(3).$ Since $a_i$ are rational numbers and $P(x)$ is a perfect square for infinite number of integer values of $x$ , it easily follows $\Delta(x)=0$ for infinite number of integers $x$ . This means

$\displaystyle P(x)=Q(x)^2.$

But since $Q(x)$ has integer coefficients, it can be derived that in fact the coefficients of $Q$ are integers.

References.
[1] RMM 2023, problem 3, AoPS page
[2] https://artofproblemsolving.com/community/c6h3138145p28455449

The Hidden Polar Line

I decided to freshen up this blog by posting some interesting geometric stuff. That’s why I kindly asked my friend Nevena Sybeva to write something she likes. Here it is!

An interesting geometric problem by Konstantin Knop appeared In the last issue of the Kvant magazine (2023, 5) [2]. I want to present a solution I found that uses some projective properties like cross-ratio, pole/polar, etc., and illustrates these topics. The first two sections are preliminary, they can be skipped if one knows these things. The last section is devoted to the mentioned problem in Kvant.

Cross – ratio

Definition. (cross-ratio on a line). Given four points $A, B,C, D$ on a line their cross ratio is defined as

$\displaystyle [A,B,C,D]=\frac{AC}{BC}:\frac{AD}{BD}$ .

Here we assume that we have endowed the line with a direction so if $AB$ points to this direction it is positive, otherwise it’s negative. Thus, $[A,B,C,D]$ is a real number – positive or negative.

Definition. (cross-ratio, general definition). Given four points $A, B,C, D$ that can lie on a line, circle (or more generally, on a conic) their cross ratio is defined as

$\displaystyle [A,B,C,D]=\frac{A-C}{B-C}:\frac{A-D}{B-D}$

where $A,B,C,D$ are viewed as complex numbers on the given plane. So, in this more general case, the cross – ratio is a complex number. Usually, we use the same notation as above

$\displaystyle [A,B,C,D]=\frac{AC}{BC}:\frac{AD}{BD}$ .

with a convention that $AB$ is equal to the complex number $B-A.$ Here are some basic properties of the cross-ratio that will be used.

Property 1. The cross-ratio is preserved by the projective transformations of a projective line.

Property 2. For any points $F,A,B,C,D$ that lie on same line (conic) it holds

$\displaystyle [A,B,C,D]=[A,B,F,D]\cdot [A,B,C,F] \qquad (1)$

Property 3.

$\displaystyle [A,B,C,D]=1/[A,B,D,C]$

$\displaystyle [A.B,C,D]=[C,D,A,B]$

Pole and polar

Definition. Let $k (O; R)$ be a given circle. To each point $E\neq O$ on the plane we assign its polar line $p_E$ which passes through the point $E',$ that is inverse to $E$ with respect to $k (O; R),$ and is perpendicular to $OE.$
Thus, each (pole) $E$ corresponds to its polar line $p_E.$

Some basic properties of polars are illustrated on fig. 3.

The polar $p_E$ of an external point $E$ crosses $k$ at two points $F$ and $G$ . The lines $EF$ and $EG$ are tangent to the circle. If $EAB$ and $ECD$ are secants to $k$ , the polar $p_E$ passes through points $T=AC\cap BD$ and $S=AD\cap BC$ .
For the above configuration it holds

$[A,F,C,D]=[C,D,F,B]\qquad (2)$

Let us prove $(2)$ by using pairs of similar triangles in figure 3:

$\displaystyle [A,F,C,D]=\frac{AC}{FC}\cdot \frac{FD}{AD}=\frac{DB\cdot\frac{EA}{ED}}{FD\cdot\frac{EC}{EF}}\cdot \frac{CF\cdot\frac{ED}{EF}}{CB\cdot\frac{EA}{EC}}$

$\displaystyle =\frac{CF}{FD}\cdot \frac{DB}{CB}= [C,D,F,B].$

The main problem

Problem (Kvant magazine [2], M2735) Let $k$ be a circle with a center $O$ and diameter $AB$ . The points $C$ , $D$ , $X$ and $Y$ on $k$ are chosen so that the line segments $CX$ and $DX$ intersect segment $AB$ at points symmetric with respect to $O$ and $XY$ is parallel to $AB$ . Let lines $AB$ and $CD$ intersect at point $E$ . Prove that the tangent to $k$ through $Y$ passes through $E,$ see fig. 4.

This statement is naturally translated into the language of poles and polars. We have to prove that $Y$ lies on the polar $p_E$ of $E$ with respect to $k$ (according to polar’s properties in the previous section). So, it suffices to prove that the lines $XO$ and $p_E$ intersect on $k$ .

Let $p_E$ itersects $k$ at $F$ as shown in fig 5. We will prove that $F\in XO.$ This is equivalent to

$\displaystyle [A,F,C,D]=[A,F',C,D]$

where $F':= XO\cap k.$ Since $[A,F',C,D]=[A,O,C',D']$ it boils down to prove

$\displaystyle [A,F,C,D]=[A,O,C',D'] \qquad (3)$

where $\displaystyle C':= CX\cap AB; D':= DX\cap AB.$

Let us do calculations on the right side of $(3)$ using that $C'O=OD'$

$\displaystyle [A,O,C',D']=\frac{AC'}{OC'}:\frac{AD'}{OD'}=-\frac{AC'}{AD'}$

Hence

$\displaystyle [A,O,C',D']^2={\left(\frac{AC'}{AD'}\right)^2}= {\frac{AC'}{AD'}\cdot \frac{BD'}{BC'}}={[C',D',A,B]}.$

But

$[C,'D',A,B]= [C,D,A,B]$

so using properties $(1)$ and $(2)$ we get

$[C',D',A,B]=[C,D,A,B]=[A,F,C,D]\cdot[C,D,F,B]= [A,F,C,D]^2$

which means

$\displaystyle [A,F,C,D]^2=[A,O,C',D']^2.$

Note that $[A,F,C,D]$ and $[A,O,C',D']$ have both a negative sign because $F$ lies between $C$ and $D$ ( $EF$ is a tangent to $k$ ). This proves $(3)$ and completes the proof.

References.
[1] DOBOS, SÁNDOR. “Cross Ratio in Use.” The Mathematical Gazette, vol. 95, no. 534, 2011, pp. 444–53. JSTOR.
[2] Kvant magazine, 2023, 5, M2735.

Sequence of Polynomials.

Assume we have to construct an infinite sequence of numbers $a_0, a_1,\dots$ so that for each $n\in \mathbb{N}$ the polynomial $P_n(x):=a_0+a_1x+\dots+a_nx^n$ has $n$ (distinct) real roots. Is it possible?

As expected, the answer depends on the set of numbers $X$ from which we are allowed to choose the coefficients. It is possible in case $X=\mathbb{R},$ but when $X=\mathbb{Z}$ the answer is negative. The first case was given at IMC 2014 as problem 3. It was made a bit more complicated, but the idea is simple. The second case was ELMO shortlist2023, A3.
As we will see in this blog post, the only condition on $X$ that matters in order a sequence of coefficients like that to exist is that there must be numbers in $X$ with magnitude as small as we want. Otherwise it’s impossible. Let me first give the statements of the two mentioned problems.

Problem 1 (IMC 2014, p3). Let $n$ be a positive integer. Show that there are positive real numbers $a_0, a_1, \dots, a_n$ such that for each choice of signs the polynomial

$\displaystyle \pm a_nx^n\pm a_{n-1}x^{n-1} \pm \dots \pm a_1x \pm a_0$

has $n$ distinct real roots.

Problem 2 (ELMO shortlist 2023, A3). Does there exist an infinite sequence of integers $a_0, a_1, a_2, \dots$ such that $a_0 \neq 0$ and, for any integer $n> 0$ , the polynomial

$\displaystyle P_n(x)=\sum_{k=0}^na_kx^k$

has $n$ distinct real roots?

You see that the first problem claims something stronger – you can pick the sign of $a_n$ as you want and all those polynomial will still have $n$ real roots. I’ll present first a construction for Problem 1.

Solution of Problem 1.

The idea is to determine consecutively the values of $a_n.$ Assume we’ve found positive real numbers $a_0,a_1,\dots,a_{n-1}$ so that any polynomial

$\displaystyle P_{n-1}= a_{n-1}x^{n-1} \pm \dots \pm a_1x \pm a_0$

has $n-1$ distinct real roots. We’ll prove that for a sufficiently small $a_n, a_n>0$ , the polynomial:

$\displaystyle P_n := a_n x^n \pm a_{n-1}x^{n-1} \pm \dots \pm a_1x \pm a_0$

will do the job. Fix some polynomial $P_{n-1}=\pm a_{n-1}x^{n-1} \pm \dots \pm a_1x \pm a_0$ . Draw a picture in your mind of the graph of $P_{n-1}$ – how it goes up and down and intersects the abscisse axe at the points $x_1<x_2<\dots<x_{n-1}$ . There are some cases that have to be considered. For example, let $n-1$ be even. Consider first the case when $P_{n-1}$ is positive on the left side of $x_1.$ In this case it must be also positive on the right side of $x_{n-1}$ . Now, take $a_{n}>0$ small enough so that $P_{n}(x) := a_nx^n+P_{n-1}(x)$ differs only slightly from $P_{n-1}$ in the interval $[x_1-\epsilon, x_{n-1}+\epsilon]$ . That is, $P_n$ will still have $n-1$ distinct roots in this interval. Moreover, $P_n(x)$ will be positive near the left side of $x_1.$ But since $n$ is odd and $a_n>0,$ it follows $\lim_{x\to-\infty}P(x)=-\infty$ . Hence, $P_n(x)$ will have an additional root $x', x'<x_1.$

The case when $P_{n-1}$ is negative on the left side of $x_1$ goes in a similar way. Considering all possible polynomials $P_{n-1},$ (there are $2^n$ of them), we can choose small enough positive $a_n$ appropriate for all of them. The case when $n-1$ is odd is similar. $\square$

Let us now focus on Problem 2. The condition $a_i\in\mathbb{R}, i=0,1,\dots$ is replaced by $a_i\in\mathbb{Z}, i=0,1,\dots.$ Note that the idea used in Problem 1 doesn’t work now since we cannot choose the magnitude of $a_n$ be as small as we want. But, maybe another approach is possible? The answer this time is “NO”. As it turns out, if $a_0,a_1,\dots$ satisfies the requirement then there exists $n$ with $|a_n|$ as small as we want.

Solution of Problem 2.

The answer is “no”. Clearly $a_k\ne 0, k=0,1,\dots ,$ since otherwise $P_k(x)$ would have at most $k-1$ roots. Assume on the contrary, sequence like that exists. Suppose $P_n(x)$ has $n$ distinct real roots $x_1<x_2<\dots<x_n.$ Then $P_n'(x)$ has $n-1$ distinct real roots $y_i,\, x_i<y_i<x_{i+1}, i=1,2,\dots,n-1.$ So, if the claim holds for a sequence $(a_n)$ it also holds for the sequence $na_n, n=0,1,\dots .$ That’s why, we can assume without loss of generality that $|a_n|$ takes as large values as we want, since otherwise we would transfer the claim to $na_n.$ This means that there exist infinitely many $a_n$ for which

$\displaystyle |a_n|\ge \max_{0\le i\le k} |a_i| .$

For these $n,$ the polynomial $P_n(x)$ cannot have a real root with magnitude larger than $2,$ that is, all roots of $P_n(x)$ are in $[-2,2].$ In the same way as above, $P_n^{(k)}(x)$ has $n-k$ distinct real roots $-2<\xi_1<\xi_2<\dots<\xi_{n-k}<2$ for each $k<n.$ Note that the constant term of $P_n^{(k)}(x)$ is $k! a_k .$ We have

$\displaystyle |\xi_1\xi_2\cdots \xi_{n-k}|=|a_k k!|\ge k!.$

But on the other hand, since $|\xi_i|\le 2, i=1,2,\dots,n-k,$ we get

$\displaystyle |\xi_1\xi_2\cdots \xi_{n-k}|\le 2^{n-k}$

which implies $2^{n-k}\ge k!.$ Now, we put $k:=n/2$ and get

$\displaystyle 2^{n/2}\ge (n/2)!$

which is false for sufficiently large $n,$ contradiction. $\square$

We can prove in the same way that any sequence of real numbers that satisfies the given condition must have terms with magnitude as small as we want. It’s also redundant to require that the roots of $P_n(x)$ be distinct.

References.
[1] IMC 2014, Problem 3., AoPS thread
[2] ELMO Shortlist 2023, Problem 3. AoPS thread.