Posted Earlier

The answer is yes. In fact, it should be true that we can find $a_0,\ldots, a_{19}$ so that any permutation of the $a_i$'s results in a polynomial with a root, but this solution does not prove that claim. Let $N = 20$ be even. Lemma 1: For any positive reals $a_0,\ldots, a_{N-1}$, there exists $c = c(a_0, \ldots, a_{N-1}) > 0$ so that, for $k > 0$, $P_k(x) = kx^N + a_{N-1}x^{N-1} + \cdots + a_0$ has a real root if and only if $k \leq c$. Proof: Such a root must be negative and exists if and only if there exists $x < 0$ such that \[ k = - \frac{a_{N-1}}{x} - \cdots - \frac{a_0}{x^N}. \]So, the root exists if and only if \[ k \leq \max_{x < 0} \left( -\frac{a_{N-1}}{x} - \cdots - \frac{a_0}{x^N}\right) \]and the right hand side is positive because as $x\to -\infty$, $-\frac{a_{N-1}}{x} - \cdots - \frac{a_0}{x^N}$ approaches $0$ from above. Thus $c$ exists. $\Box$ Lemma 2: $P_c(x)$ has a double root, and $P_c(x) < 0$ never holds. Proof: It clearly suffices to show that $P_c(x) < 0$ never holds. Indeed, fix $x_0$ with $P_c(x_0) < 0$. Note that $P_k(x_0)$ is a smooth, increasing function in $k$, so there exists $k>c$ with $P_c(x_0) < P_k(x_0) < 0$, and then $P_k$ has a root but $k > c$, contradiction. Since $P_c(x) < 0$ never holds, all roots must be double indeed. $\Box$ Now, let $c_0, \ldots, c_{N-1}$ be such that $\max(c_i) < \left(1 + \frac{1}{N^2}\right) \min(c_i)$. Lemma 3: All double roots of $P_k(x)$ are less than $-1$. Proof: Suppose that $x$ is a double root of $P_k(x)$. Then, \[ kx^N + c_{N-1} x^{N-1} + \cdots + c_0 = 0, Nkx^{N-1} + (N-1)c_{N-1}x^{N-2} + \cdots + c_1 = 0. \]In particular, this implies that \[ Nkx^N + Nc_{N-1} x^{N-1} + \cdots + Nc_0 - (Nkx^N + (N-1)c_{N-1}x^{N-1} + \cdots + c_1x) = 0, \]or \[ c_{N-1}x^{N-1} + 2c_{N-2}x^{N-2} + \cdots + Nc_0 = 0. \]But if $0 > x \geq -1$, then for $0 \leq i \leq \frac N2 - 1$, \begin{align*} (N-2i)c_{2i}x^{2i} + (N-2i-1)c_{2i+1}x^{2i+1} &\geq x^{2i} ((N-2i)c_{2i} - (N-2i-1)c_{2i+1}) \\ &\geq c_{2i} x^{2i} \left((N-2i) - (N-2i-1)\left(1 + \frac{1}{N^2}\right)\right) > 0, \end{align*}and summing gives $c_{N-1} x^{N-1} + \cdots + Nc_0 > 0$, contradiction. $\Box$ Lemma 4: If we swap two $c_i$'s, then $c$ changes. Proof: Suppose not. Without loss of generality say that we have swapped $c_i, c_j$ where $i > j$ and $c_i > c_j$. Let $P_c$ be the first polynomial (pre-swap) and $Q_c$ the second one. Then, \[ \triangle (x) = Q_c(x) - P_c(x) = c_ix^j + c_jx^i - c_ix^i - c_jx^j = (c_i-c_j)(x^j - x^i) \]has the same sign for all $x<-1$. Let $\alpha, \beta$ be double roots of $P_c, Q_c$, respectively. If $\triangle(x) < 0$ for all $x < -1$, then $Q_c(\alpha) < 0$, contradicting Lemma 2. If $\triangle(x) > 0$ for all $x < -1$, then $P_c(\beta) < 0$, contradicting Lemma 2. Thus we have a contradiction and $c$ must change. $\Box$ Now, let $b_0, \ldots, b_{N-1}$ be a permutation of $c_0, \ldots, c_{N-1}$ with $c = c(b_0,\ldots, b_{N-1})$ minimal. We claim that \[ a_i = \frac{b_i}{c+\varepsilon} \]works for sufficiently small $\varepsilon$. Indeed, suppose that we swap $a_i, a_j$. Let $\pi$ be the permutation of $\{0,1,\ldots, N-1\}$ that swaps $i,j$. Then, note that by Lemma 4 and by minimality of $c$, \[ c + \varepsilon(i,j) = c(b_{\pi(0)}, \ldots, b_{\pi(N-1)}) > c. \]Then, let $\varepsilon < \varepsilon(i,j)$ for all $i\neq j$. We claim that this will work. Note first that \[ x^N + a_{N-1}x^{N-1} + \cdots + a_0 = 0 \iff (c+\varepsilon) x^N + b_{N-1} + \cdots + b_0 = 0, \]so indeed $x^N + a_{N-1}x^{N-1} + \cdots + a_0$ does not have any real roots. On the other hand, for any permutation $\pi$ that swaps $i,j$, \[ x^N + a_{\pi(N-1)} x^{N-1} + \cdots + a_{\pi(0)} = 0 \iff (c+\varepsilon)x^N + b_{\pi(N-1)} x^{N-1} + \cdots + b_{\pi(0)} = 0, \]which does have real roots since $c+\varepsilon < c+\varepsilon(i,j)$. Thus these $a_0,\ldots, a_{N-1}$ indeed work.

The answer is $\boxed{yes}.$ We will construct it somewhat explicitly. Set $M(x) = (x^2 + 4x + 4)(x^{18} + x^{16} + x^{14} + \cdots + x^2 + 1).$ Observe that $M(x) = x^{20} + 4x^{19} + 5x^{18} + 4x^{17} + 5x^{16} + \cdots + 5x^2 + 4x + 4.$ Select some arbitrarily small $\epsilon > 0$, say $\epsilon = 10^{-10^{10^{10}}}.$ Consider the polynomial $Q(x) = (4-10 \epsilon)x^{19} + (5 + 9 \epsilon)x^{18} + (4 - 9\epsilon)x^{17} + (5 + 8 \epsilon)x^{16} + \cdots + (4-2\epsilon)x^3 + (5+\epsilon)x^2 + (4-\epsilon)x + 4.$ Consider the maximal $t \in \mathbb{R}$ so that $tx^{20} + Q(x)$ has a real root. Clearly $t > 0$ because $Q(x)$ has a root. Since $tx^{20} + Q(x)$ has even degree, it must have a double root (since the roots pair up as complex conjugates). We claim that $t \ge 0.99.$ Indeed, when $t = 0.99$, $t(-2)^{20} + Q(-2) \le 0$, and so $tx^{20} + Q(x)$ has a root. We also claim that $t \le 1.01.$ Indeed, we claim that $R(x) = 1.01 x^{20} + Q(x) \ge 0$ for all $x \in \mathbb{R}$ in this case. Observe that $R(x) - M(x) = 0.01x^{20} + \epsilon (R_1(x))$, for some polynomial $R_1$ of degree $19$ and with all coefficients in $[-10000, 10000].$ As $M(x) \ge (x+2)^2(x^{18} + 1) \ge (x+2)^2$, we're easily done here by considering cases when $x \in [-1, 0]$ and $x \in (- \infty, -1).$ So we have that for $0.99 \le t \le 1.01$, $tx^{20} + Q(x)$ has a double root and is always nonnegative. We claim that this double root $r$ is less than $-1.$ If not, then we have that $R(x) = tx^{20} + Q(x)$ has some root in $[-1, 0).$ Note that $R(r) = M(r) + \epsilon R_1(r) + (t-1)r^{20},$ where $R_1$ s some degree $19$ polynomial with all coefficients in $[-10000, 10000].$ Since $r \in [-1, 0)$, we have that $M(r) \ge 1.$ However, $\epsilon R_1(r) \in [-0.000001, 0.000001]$ by our definition of $\epsilon$ and $(t-1) r^{20} \in [-0.01, 0.01]$ by our bounds on $t.$ Hence $r$ is indeed less than $-1.$ Set $T(x) = x^{20} + \frac{1}{t}Q(x).$ To summarize our progress so far, we have found a polynomial $T(x) = x^{20} + a_{19}x^{19} + a_{18}x^{18} + \cdots + a_2 x^2 + a_1 x + a_0$ such that $T(x) \ge 0$ for all $x \in \mathbb{R}$, $T$ has a double root $r$ less than $-1$, all $a_i$'s are positive, and $a_{19} < a_{17} < a_{15} < \cdots < a_1 < a_0 < a_2 < a_4 < \cdots < a_{18}.$ We'll show that for any swapping of two of the $a_i$'s, $T(r)$ becomes less than zero. This would finish, as then taking $T(x) + \varepsilon$ for some arbitrarily small $\varepsilon$ would work. So let's show this. Suppose that we swap $a_i$ and $a_j$. We consider three cases on the parities of $i, j.$ Observe that the net change in $T(r)$ after the swapping is $(a_i - a_j)(r^j - r^i).$ We'll show that this is always negative by considering three cases. Case 1. $i, j$ are both even. WLOG $i > j$. Then $a_i > a_j$ and $r^j < r^i$, so we're done. Case 2. $i, j$ are both odd. WLOG $i > j.$ Then $a_i < a_j$ and $r^j > r^i,$ so we're done. Case 3. $i, j$ are of different parities. Suppose that $i$ is even and $j$ is odd. Then $a_i > a_j$ and $r^j < r^i,$ so we're done. As the net change in $T(r)$ is negative in all three cases, we're done by just taking $T(x) + \varepsilon$ to be our polynomial. $\square$

Consider $P_\sigma(x)=x^{20}+a_{\sigma(19)}x^{19}+a_{\sigma(18)}x^{18}+\cdots +a_{\sigma(0)}$, for all $\sigma$ permutating the numbers 0 to 19. We do some smoothing. Pick $(a_{19},a_{17},\cdots,a_1,a_0,a_2,\cdots,a_{18})=(10000,10000+\epsilon,10000+2\epsilon, \cdots 10000+19\epsilon+t)$. When $t=0$, we substitute $x=-100$. Since $\frac{|a_{19}100^{19}|}{20}>|100^{20}|,|a_{18}100^{18}|,|a_{17}100^{17}|,\cdots ,|a_{0}|$, $P(100)<0$.

Meanwhile, $P(x)>0$ for all $x\geq 0$. Fix $t$ as the minimum value of itself such that $P(x)\geq 0$ for all $x$. There is a root $y$ of $P(x)$ by continuity, which is clearly negative. If $-1\leq y<0$, then $a_{19}y^{19}+a_{18}y^{18}>a_{18}(y^{18}+y^{19})\geq 0$. Grouping the rest similarly in pairs, and using $y^{20}>0$, $P(y)>0$, a contradiction. Hence $y<-1$, and $y^{19}<y^{17}<\cdots <y^1<y^0<y^2<\cdots y^{18}$. Since $a_{19}<a_{17}<\cdots<a_1<a_0<a_2\cdots <a_{18}$, by rearrangement inequality, $0=P(y)>P_\sigma(y)$ for $\sigma\neq Id$. Adding small $\delta$ to $t$, $P(x)>0$ for all $x$, while $P_\sigma(x)$ ($\sigma\neq Id$) take both positive and negative values. So we are done.

The answer is yes. Consider the polynomial $$P_t(x)=x^{20}+(t+1)x^{19}+(t+20)x^{18}+(t+2)x^{17}+(t+19)x^{16}+\cdots+(t+10)x+(t+11)$$where the coefficients of $x^{2k}$ are $t+11+k$ for $1 \leq k \leq 9$, and the coefficients of $x^{2k-1}$ are $t+11-k$ for $1 \leq k \leq 9$. Claim 1: $P_0 (x)$ has no real roots. Proof: Let $P_0(x)=x^{20}+c_{19}x^{19}+c_{18}x^{18}+c_{17}x^{17}+\cdots c_0$, then $$\min\{c_{18},c_{16},\cdots,c_0\}>\max\{c_{19},c_{17},\cdots,c_1\}$$For any real $x$ and $i=1,3,5,\cdots,17$, we have $$\frac{c_{i-1}}{2}x^{i-1}+\frac{c_{i+1}}{2}x^{i+1}\geq\sqrt{c_{i-1}c_{i+1}}|x|^i\geq c_i|x|^i$$Also, $x^{20}+\frac{c_{18}}{2}x^{18}\geq c_{19} |x|^{19}$, $\frac{c_0}{2}>0$, hence, $$P_0(x) \geq \left(x^{20}+\frac{c_{18}}{2}x^{18}-c_{19} |x|^{19}\right) +\sum_{i=1}^9 \left(\frac{c_{2i-1}}{2} x^{2i-1} + \frac{c_{2i+1}}{2} x^{2i+1} - c_{2i} |x|^{2i}\right) + \frac{c_0}{2} > 0$$ Claim 2: There exists $t>0$ such that $P_t (x)$ has a real root. Proof: Consider the function $f(t)=P_t \left(-\frac{t}{2}\right)=-\frac{1}{2^{20}}t^{20}+t$. When $t$ is sufficiently big, $f(t)<0$, but $f(0)=P_0 (0)=11>0$, hence $f(t)$ has a real root, and there exists $t>0$ such that $f(t)=P_t \left(-\frac{t}{2}\right)=0$. Set $u\in\mathbb{R}$ such that $P_u (x)$ has a real root. Let $$S=\{t\in[0,u]|P_t (x) \text{ no real root}\}$$$$T=\{t\in[0,u]|P_t (x) \text{ has real root}\}$$From the above claims, $0\in S$, $u \in T$. Claim 3: For any $t\in T$, all real roots of $P_t (x)$ are in the interval $\left(-u-1,-1-\frac{1}{u+10}\right)$. Proof: It is clear that for $x\geq 0$, $P_t(x)>0$. For $-1-\frac{1}{u+10}\leq x\leq 0$, we have $$P_t(x)=x^{20}+((t+1)x^{19}+(t+20)x^{18})+\cdots+((t+10)x+(t+11))>0$$For $x\leq -u-1$, we have $$P_t(x)=(x^{20}+(t+1)x^{19})+\cdots+((t+12)x^2+(t+10)x)+(t+11)>0$$Hence the claim is proven. Choose a sufficiently small $\varepsilon$ such that $$\varepsilon ((u+1)^{19}+(u+1)^{18}+\cdots+(u+1)+1)<\frac{1}{u+10}$$Then, choose sufficiently big $N\in\mathbb{N}$ such that $\frac{u}{N}<\varepsilon$. Dividing the interval $[0,u]$ into $N$ equal subintervals, we consider the endpoints $$0, \frac{u}{N}, \frac{2u}{N}, \cdots, \frac{N-1}{N}u, u$$Since $0 \in S$, $u \in T$, there exists $k$ with $0\leq k\leq N-1$ such that $\frac{ku}{N}\in S$, $\frac{k+1}{N}u \in T$. Claim 4: $P(x)=P_{\frac{ku}{N}}(x)$ satisfies the condition. Proof: Let $Q(x)=P_{\frac{k+1}{N}u}(x)$. Since $\frac{ku}{N} \in S$, $P(x)$ has no real roots. Since $\frac{k+1}{N}u \in T$, $Q(x)$ has a real root. Letting $a$ be a real root of $Q(x)$, we observe that by Claim 3, $-u-1 < a < -1-\frac{1}{u+10}$. As $\frac{u}{N}<\varepsilon$, as well as how $\varepsilon$ is chosen, $$|P(a)-Q(a)|<\varepsilon(|a|^{19}+|a|^{18}+\cdots+|a|+1)<\frac{1}{u+10}$$Since $P(x)$ has no real roots, $0<P(a)<\frac{1}{u+10}$. Let $P(x)=x^{20}+b_{19}x^{19}+\cdots+b_0$. By interchanging $b_i$ and $b_j$, we obtain the polynomial $R(x)$. We now show $R(a)<0$, and using $R(x)>0$ for sufficiently large $x$, we will be done. $$P(a)-R(a)=b_i a^i + b_j a^j - b_j a^i - b_i a^j =a^j (a^{i-j}-1)(b_i-b_j) =a^i (a^{j-i}-1)(b_j-b_i)$$Case 1: $2\mid i$, $2\mid j$. Since $b_j-b_i \geq 1$, $a^i \geq 1$, $a^{j-i}-1\geq \frac{1}{u+10}$, hence $P(a)-R(a)\geq \frac{1}{u+10}$, and $R(a)<0$. Case 2: $2\nmid i$, $2\nmid j$. Since $b_j - b_i \leq -1$, $a^i \leq -1$, $a^{j-i}-1 \frac{1}{u+10}$, hence $P(a)-R(a)\geq\frac{1}{u+10}$, and $R(a)<0$. Case 3: $2\nmid i$, $2\mid j$. Since $b_i-b_j \leq -1$, $a^j \geq 1$, $a{i-j}-1 \leq -1$, hence $P(a)-R(a)\geq 1$, and $R(a) < 0$. Case 4: $2\mid i$, $2\nmid j$. Since $b_i - b_j \leq -1$, $a^j \leq -1$, $a^{i-j} \leq -1$, hence $P(a)-R(a) \geq 1$, and $R(a) < 0$. We are done.

Pick $\epsilon$ to be a sufficiently large number and we show that there exists a polynomial $$P(x)=x^{20}+\left(\frac{x}{\epsilon}+1\right)(a_{18}x^{18}+a_{16}x^{16}...+1)$$satisfying the condition. This will proves the claim since we can pick $a_{2n+1}=\frac{1}{\epsilon}a_{2n}$ for each $0\leq n\leq 10$. Notice that $P(-\epsilon)=\epsilon^{20}$ Now define $P_{i,j}(x)$ to be the result of $P(x)$ after solving coefficient $a_i,a_j$. Then $P_{i,j}(x)$ has a root is equivalent to \begin{align*} P(x)-P_{i,j}(x)&\geq P(x)\text{ for some }x\\ (x^i-x^j)(a_i-a_j)&\geq P(x)\text{ for some }x\hspace{20pt}(1) \end{align*}In fact, we will pick $a_{18}>a_{16}>...>a_0>a_{19}>...>a_1$, and show that $(1)$ holds for some $x\leq -\epsilon$. Indeed, (1) is going to hold if $$(1-x^{2n+1})(a_0-a_{2n+1})\geq P(x) \text{ for some } x$$and $$(x^{2m+2}-x^{2m})(a_{2m+2}-a_{2m})\geq P(x)\text{ for some }x$$for all $m,n$. In particular, if we pick $x=-\epsilon$, we only need, $$a_0-\frac{1}{\epsilon}a_{2n+2}\geq \frac{\epsilon^{20}}{1+\epsilon^{2n+1}} \hspace{20pt}(2)$$$$a_{2m+2}-a_{2m}\geq \frac{\epsilon^{20}}{\epsilon^{2m+2}-\epsilon^{2m}}\hspace{20pt}(3)$$It is easy to choose $a_0,...,a_{2m}$ to merely satisfy $(2)$ and $(3)$, namely we can pick $a_0$ very large and $$a_{2m+2}=a_{2m}+\frac{\epsilon^{20}}{\epsilon^{2m+2}-\epsilon^{2m}}$$Then $$a_{18}=a_0+\frac{\epsilon^{20}}{\epsilon^{2}-1}\left(1+\frac{1}{\epsilon^2}+...+\frac{1}{\epsilon^{16}}\right)$$Since $a_0$ is large enough, $\frac{1}{\epsilon}a_{18}<<a_0$, therefore $(2)$ and $(3)$ holds. Now we have proved that $P_{i,j}(x)$ has a real root for each pair of $(i,j)$. The only problem is that $P$ may have real roots as well. That is $P_{min}<0$. To tackle this issue, we define $P^c(x)$ to be the polynomial if we replace $a_0,a_1,...,a_{18}$ with $ca_0,ca_1,...,ca_{18}$. Suppose $P^c(x)$ attains it minimum of the interval $[-\infty,-\epsilon]$ at $x_c$, which is equal to $P^c_{\min}(x)$. Now in view of $(2),(3)$ it suffices to have $$c(a_0-\frac{1}{\epsilon}a_{2n+2})\geq\frac{P_{\min}^c}{-x_c^{2n+1}+1}\hspace{20pt}(4)$$and$$c(a_{2m+2}-a_{2m})\geq\frac{P_{\min}^c}{x_c^{2m+2}+x_c^{2m}}\hspace{20pt}(5)$$ Notice that $P_{\min}$ is a continuous function in $c$. Meanwhile, since $P^1_{\min}<0$ and $P^2_{\min}=\epsilon^{20}>0$ by intermediate value theorem there exists $0<c<1$ such that $P^c_{\min}=0$ (if there are several $c$ pick the smallest one). Then we pick $\delta$ so small such that $$(c+\delta)(a_0-\frac{1}{\epsilon}a_{2n+2})\geq\frac{P^{c+\delta}(x_c)}{x_c^{2n+1}+1}$$$$(c+\delta)(a_{2m+2}-a_{2m})\geq \frac{P^{c+\delta}(x_c)}{x_c^{2m+2}+x_c^{2m}}$$still holds then we are done.