The main idea is to consider the polynomial $P-Q$, and apply Descartes rule of signs to it (common roots of $P$ and $Q$ are roots of $P-Q$ as well; the common coefficients result in zero coefficients of $P-Q$, so one should obtain two bounds for the number of roots of $P-Q$ (using the degree and the previously obtained bound))

Any solution...

I posted it here. Hope, there is no annoying calculation error.

My approach uses a tad bit of calculus, so I'm unsure if it's a fakesolve. I also hope there isn't a calculation mistake of the bound. Here goes... We claim the maximum value is $3029$, and $n + \left \lfloor {\frac{n-1}{2}} \right \rfloor$ for general $n$ instead of $2020$. Construction for $n = 2020$: Let: $P(x) = (x^2 + 2x + 1)(x^2 - \alpha_1)(x^2 - \alpha_2)...(x^2 - \alpha_{1009})$. $Q(x) = (x^2 + x + 1)(x^2 - \alpha_1)(x^2 - \alpha_2)...(x^2 - \alpha_{1009})$. Here $\alpha_i$ represent real numbers, chosen such that no coefficient of $P(x)$ and $Q(x)$ is zero. Now $P(x)$ and $Q(x)$ share $1009 \cdot 2 = 2018$ real roots, $\sqrt{\alpha_i}$ for $i = 1, 2, ..., 1009$. Furthermore, since $(x^2 - \alpha_1)(x^2 - \alpha_2)...(x^2 - \alpha_{1009})$ only contains even powers of $x$, the even powers of $x$ in $P(x)$ and $Q(x)$ both arise from $(x^2+1)(x^2 - \alpha_1)(x^2 - \alpha_2)...(x^2 - \alpha_{1009})$, and so these coefficients are equal. There are $1011$ of these. $2018 + 1011 = 3029$. Bound: Let $R(x) = P(x) - Q(x)$. We focus on this polynomial instead. Claim 1: $P(x)$ and $Q(x)$ share $r$ common real roots and $s$ common coefficients $\Rightarrow R(x)$ has at least $r$ real roots and at most $s$ zero coefficients. Proof: The gcd of $P(x)$ and $Q(x)$ divides $R(x)$ by the Euclidean algorithm. Hence, since $P(x)$ and $Q(x)$ share $r$ common real roots $R(x)$ has at least these $r$ real roots. Furthermore, for each of the $s$ shared coefficients, $R(x)$ gets a zero coefficient. This could be in powers of $x$ greater than the degree of $R(x)$. Otherwise, it is non-zero, so altogether at most $s$ zero coefficients. $\square$. To maximise $r$ and $s$, we hence want to maximise the number of zero coefficients and real roots of $R(x)$. This is achieved by making all the real roots of $R(x)$ shared roots, and $\deg(R) = d-1$, where we then set $P(x)$ and $Q(x)$ both monic to provide another shared coefficient. We prove via strong induction, that: For a polynomial $R(x)$ with degree $d$, with a constant term and $k < d$ zero coefficients, the maximum number of roots is $d + \left \lfloor {\frac{d}{2}} \right \rfloor - k$. We deal only with monic polynomials: these arguments are invariant of scaling by a constant. Base cases: $n = 1$: We can only have 0 zero coefficients, which gives 1 real root as required. $n = 2$. If 0 zero coefficients, we get at most 2 real roots by Fundamental Theorem of Algebra. This is less than 3. If 1 zero coefficient, $R(x) = x^2 - \alpha^2$ for $\alpha$ non-zero real gives 2 real roots. $n > 2, k = d-1$. Then $R(x) = x^d + c$. For $d$ even, this yields at most 2 real roots, and $d + \left \lfloor {\frac{d}{2}} \right \rfloor - (d-1) = 1 + \left \lfloor {\frac{d}{2}} \right \rfloor > 2$. For $d$ odd, this yields exactly 1 real root. Inductive step: Assume the above holds for all degrees $m < n$, and for all zero coefficients $\lambda \le k$. Claim 2: Let the roots in ascending order be $a_1, a_2, ..., a_{\mu}$. Between any two roots, there must be a stationary point. Proof: If $a_i \neq a_{i+1}$, then the curve of $R(x)$ in this interval lies on one side of the x-axis, WLOG above. But then the curve is increasing at $a_i$, but decreasing at $a_{i+1}$, and so by the intermediate value theorem applied on $R'(x)$, there must be a value $z$ strictly in between where $R'(z) = 0$, hence stationary. If $a_i = a_{i+1}$, let there be $\lambda$ occurrences of the value of $a_i$ in the set of roots. Thus, $(x - a_i)^\lambda | R(x)$, or rather $R(x) = (x-a_i)^\lambda \cdot V(x)$. Hence $R'(x) = (x-a_i)^\lambda \cdot V'(x) + \lambda (x - a_i)^{\lambda - 1} \cdot V(x)$, and importantly $(x-a_i)^{\lambda-1}$ is a factor of $R'(x)$, so $a_i$ is a stationary point at least $\lambda-1$ times. By definition of $\lambda$, we have $\lambda-1$ pairs of consecutive roots both equal to $a_i$, and so we've found our stationary points. $\square$. Because of the power rule of differentiation, $R'(x)$ has $k$ zero coefficients. However, it has no constant term, so let $\frac{R'(x)}{x^b}$ be the first with a constant term. This removes $b$ zero coefficients. By the inductive hypothesis, we have degree $d - 1 - b$, $k - b$ zero coefficients, so $\frac{R'(x)}{x^b}$ has at most $d - 1 - b + \left \lfloor {\frac{d - 1 - b}{2}} \right \rfloor- k + b = d - 1 - k + \left \lfloor {\frac{d - 1 - b}{2}} \right \rfloor$ real roots. Note that $R'(x)$ has $x = 0$ as a root so we get at most $d - k + \left \lfloor {\frac{d - 1 - b}{2}} \right \rfloor$ real roots. This equates to at most $d - k + \left \lfloor {\frac{d - 1 - b}{2}} \right \rfloor$ turning points, which by Claim 2 means at most $d - k + 1+ \left \lfloor {\frac{d - 1 - b}{2}} \right \rfloor$ real roots. To maximise this, we set $b$ to its minimum 1, and get at most $d - k + \left \lfloor {\frac{d}{2}} \right \rfloor$ roots, which is what we wanted. $\square$. Now, following our optimisations from above, we let $P(x) = (x + c)R(x)$, $Q(x) = (x + c - 1)R(x)$, where $c$ is chosen to allow non-zero coefficients (this is always possible as each coefficient being zero is one equation, so only finitely many equations to avoid). Then for $P(x)$ of degree $n$, with $k + 1$ common coefficients (+1 to account for leading coefficient, removed in $R(x)$), and at most $n-1 + \left \lfloor {\frac{n-1}{2}} \right \rfloor - k$ common roots, $r + s \le n + \left \lfloor {\frac{n-1}{2}} \right \rfloor$. $\blacksquare$. Remarks: The construction for $n$ even doesn't follow from the proof of the bound, because the bound gives by integrating something of the form $a_d x^d + a_{d-1} x^{d-1} + a_{d-3} x^{d-3} + ... + a_0$ for $d$ odd which isn't as easy to define (and prove there exists the sufficient real roots) as products of differences of two squares.

VicKmath7 wrote: The main idea is to consider the polynomial $P-Q$, and apply Descartes rule of signs to it (common roots of $P$ and $Q$ are roots of $P-Q$ as well; the common coefficients result in zero coefficients of $P-Q$, so one should obtain two bounds for the number of roots of $P-Q$ (using the degree and the previously obtained bound)) I am having a hard time trying to find a solution with this idea, can someone write a full solution please? Thanks

Lemma : For a number $k \in \mathbb{N}$ , $k$ distinct natural numbers $i_1 , i_2 , ... , i_k$ and $k$ arbitrary non-zero real numbers $a_1 , a_2 , ... , a_k$ , define the polynomial $P(x)$ such below : $$P(x)=a_{k}x^{i_k} + ... + a_{2}x^{i_2} + a_{1}x^{i_1}$$Then this polynomial has at most $2(k-1)$ non-zero real roots , counted with multiplicity. Proof : We'll prove our claim by induction on $k$ . Firstly , we can assume that $P(0) \neq 0$. Now suppose that $r_1 , r_2 , ... , r_s$ are all negative real roots of $P(x)$ with multiplicity $d_1 , d_2 , ... , d_s$ and $r'_1 , r'_2 , ... , r'_t$ are all its positive real roots with multiplicity $d'_1 , d'_2 , ... , d'_t$ respectively. Now note that for each $1 \le i \le s$ and $1 \le j \le t$ ; numbers $r_i$ and $r'_j$ are non-zero real roots of $P'(x)$ with multiplicity $d_i-1$ and $d'_j-1$ , and also by Mean value theorem , $P'(x)$ has a non-zero real root in each of the intervals $(r_i , r_{i+1})$ and $(r'_j , r'_{j+1})$. So $P'(x)$ has at least $S$ non-zero real roots ; counted with multiplicity : $$S=\sum{(d_i-1)} + \sum{(d'_j-1)} +(s-1)+(t-1)=\sum{d_i} + \sum{d'_j} -2$$Thus while $P'(x)$ is a polynomial with exactly $k-1$ non-zero coefficients in $\mathbb{R}[x]$ , by our induction step for $k-1$ we can get that $P(x)$ has at most $2(k-1)$ real roots and we're done. Now , if $P(x)$ and $Q(x)$ has $r$ common coefficients , then $R(x)=P(x)-Q(x)$ has $2021-r$ non-zero coefficients. So if $r \le 1010$ , then while $P(x)$ and $Q(x)$ are not equal , we have $r+s \le 3029$ and if $r \ge 1011$ , then by Lemma $R(x)$ has at most $4040-2r$ real roots and we have $r+s \le 4040-r \le 3029$. For construction , consider these polynomials : $$P(x)=(x^2+x+1)(x^2-r_1)(x^2-r_2)...(x^2-r_{1009})$$$$Q(x)=(x^2+x-1)(x^2-r_1)(x^2-r_2)...(x^2-r_{1009})$$where positive real numbers $r_1 , r_2 , ... , r_{1009}$ are chosen such that $P(x)$ and $Q(x)$ have non-zero coefficients. Now obviously the leading coefficient and coefficients of odd-degreed monomials are common between $P(x)$ and $Q(x)$ and also they have $2018$ common roots. So the maximum value of $r+s$ is $3029$ and we're done.

Shayan-TayefehIR wrote: Lemma : For a number $k \in \mathbb{N}$ , $k$ distinct natural numbers $i_1 , i_2 , ... , i_k$ and $k$ arbitrary non-zero real numbers $a_1 , a_2 , ... , a_k$ , define the polynomial $P(x)$ such below : $$P(x)=a_{k}x^{i_k} + ... + a_{2}x^{i_2} + a_{1}x^{i_1}$$Then this polynomial has at most $2(k-1)$ non-zero real roots , counted with multiplicity. Proof : We'll prove our claim by induction on $k$ . Firstly , we can assume that $P(0) \neq 0$. Now suppose that $r_1 , r_2 , ... , r_s$ are all negative real roots of $P(x)$ with multiplicity $d_1 , d_2 , ... , d_s$ and $r'_1 , r'_2 , ... , r'_t$ are all its positive real roots with multiplicity $d'_1 , d'_2 , ... , d'_t$ respectively. Now note that for each $1 \le i \le s$ and $1 \le j \le t$ ; numbers $r_i$ and $r'_j$ are non-zero real roots of $P'(x)$ with multiplicity $d_i-1$ and $d'_j-1$ , and also by Mean value theorem , $P'(x)$ has a non-zero real root in each of the intervals $(r_i , r_{i+1})$ and $(r'_j , r'_{j+1})$. So $P'(x)$ has at least $S$ non-zero real roots ; counted with multiplicity : $$S=\sum{(d_i-1)} + \sum{(d'_j-1)} +(s-1)+(t-1)=\sum{d_i} + \sum{d'_j} -2$$Thus while $P'(x)$ is a polynomial with exactly $k-1$ non-zero coefficients in $\mathbb{R}[x]$ , by our induction step for $k-1$ we can get that $P(x)$ has at most $2(k-1)$ real roots and we're done. Now , if $P(x)$ and $Q(x)$ has $r$ common coefficients , then $R(x)=P(x)-Q(x)$ has $2021-r$ non-zero coefficients. So if $r \le 1010$ , then while $P(x)$ and $Q(x)$ are not equal , we have $r+s \le 3029$ and if $r \ge 1011$ , then by Lemma $R(x)$ has at most $4040-2r$ real roots and we have $r+s \le 4040-r \le 3029$. For construction , consider these polynomials : $$P(x)=(x^2+x+1)(x^2-r_1)(x^2-r_2)...(x^2-r_{1009})$$$$Q(x)=(x^2+x-1)(x^2-r_1)(x^2-r_2)...(x^2-r_{1009})$$where positive real numbers $r_1 , r_2 , ... , r_{1009}$ are chosen such that $P(x)$ and $Q(x)$ have non-zero coefficients. Now obviously the leading coefficient and coefficients of odd-degreed monomials are common between $P(x)$ and $Q(x)$ and also they have $2018$ common roots. So the maximum value of $r+s$ is $3029$ and we're done. can you explain more about the lemma and mean value theorem?

faraz3866 wrote: Shayan-TayefehIR wrote: Lemma : For a number $k \in \mathbb{N}$ , $k$ distinct natural numbers $i_1 , i_2 , ... , i_k$ and $k$ arbitrary non-zero real numbers $a_1 , a_2 , ... , a_k$ , define the polynomial $P(x)$ such below : $$P(x)=a_{k}x^{i_k} + ... + a_{2}x^{i_2} + a_{1}x^{i_1}$$Then this polynomial has at most $2(k-1)$ non-zero real roots , counted with multiplicity. Proof : We'll prove our claim by induction on $k$ . Firstly , we can assume that $P(0) \neq 0$. Now suppose that $r_1 , r_2 , ... , r_s$ are all negative real roots of $P(x)$ with multiplicity $d_1 , d_2 , ... , d_s$ and $r'_1 , r'_2 , ... , r'_t$ are all its positive real roots with multiplicity $d'_1 , d'_2 , ... , d'_t$ respectively. Now note that for each $1 \le i \le s$ and $1 \le j \le t$ ; numbers $r_i$ and $r'_j$ are non-zero real roots of $P'(x)$ with multiplicity $d_i-1$ and $d'_j-1$ , and also by Mean value theorem , $P'(x)$ has a non-zero real root in each of the intervals $(r_i , r_{i+1})$ and $(r'_j , r'_{j+1})$. So $P'(x)$ has at least $S$ non-zero real roots ; counted with multiplicity : $$S=\sum{(d_i-1)} + \sum{(d'_j-1)} +(s-1)+(t-1)=\sum{d_i} + \sum{d'_j} -2$$Thus while $P'(x)$ is a polynomial with exactly $k-1$ non-zero coefficients in $\mathbb{R}[x]$ , by our induction step for $k-1$ we can get that $P(x)$ has at most $2(k-1)$ real roots and we're done. Now , if $P(x)$ and $Q(x)$ has $r$ common coefficients , then $R(x)=P(x)-Q(x)$ has $2021-r$ non-zero coefficients. So if $r \le 1010$ , then while $P(x)$ and $Q(x)$ are not equal , we have $r+s \le 3029$ and if $r \ge 1011$ , then by Lemma $R(x)$ has at most $4040-2r$ real roots and we have $r+s \le 4040-r \le 3029$. For construction , consider these polynomials : $$P(x)=(x^2+x+1)(x^2-r_1)(x^2-r_2)...(x^2-r_{1009})$$$$Q(x)=(x^2+x-1)(x^2-r_1)(x^2-r_2)...(x^2-r_{1009})$$where positive real numbers $r_1 , r_2 , ... , r_{1009}$ are chosen such that $P(x)$ and $Q(x)$ have non-zero coefficients. Now obviously the leading coefficient and coefficients of odd-degreed monomials are common between $P(x)$ and $Q(x)$ and also they have $2018$ common roots. So the maximum value of $r+s$ is $3029$ and we're done. can you explain more about the lemma and mean value theorem? Mean value theorem: if $f(x)$ is differentiable between $[a,b]$ then there exists a $f’(c)$ such that $f'(c)=\frac{f(b)-f(a)}{b-a}$ or in other words, there exists a point with $x$ coordinate $c$ such that the tangent at $c$ has the same slope as the secant containing $(a,f(a))$ and $(b,f(b))$.