Return to Answer

Now choose $k\approx \sqrt n$ and $m\approx \sigma\sqrt n$. Then if $\sigma<1$, our correction stays inside the degree span of $S$, and $$ 6en 2^{-n/m}e^{3n/k}K^m\approx 6en 2^{-\sigma^{-1}\sqrt n}e^{3\sqrt n}K^{\sigma\sqrt n}\, $$ which for small $\sigma>0$ is less than $e^{-\sqrt n}\ll \kappa n^{-2}$, so our correction has admissible size too.

Recall that the Chebyshev polynomial $T_d(y)=\frac 12[(x-\sqrt{x^2-1})^d+(x+\sqrt{x^2-1})^d]$ with even $d$ has all its roots real, is bounded by $1$ on $[-1,1]$, is decreasing on $(-\infty,1]$ and is greater than $4$ at $1-\frac C{d^2}$ for some absolute constant $C>0$. After proper rescaling and taking $Cd^{-2}\approx\delta\in(0,\frac 12)$, it turns into a polynomial $S_\delta(z)$ on $[0,1]$ such that the degree of $S$ is $\le C\delta^{-1/2}$, $|S(z)|\le S(0)=1$ for every $z\in[0,1]$ and $|S(z)|\le \frac 14$ when $z\in[\delta,1]$.

Now choose $k\approx \sqrt n$ and $m\approx \sigma\sqrt n$. Then if $\sigma<1$, our correction stays inside the degree span of $S$, and $$ 6en 2^{-n/m}e^{3n/k}K^m\approx 6en 2^{-\sigma^{-1}\sqrt n}e^{3\sqrt n}K^{\sigma\sqrt n}\, $$ which for small $\sigma>0$ is less than $e^{-\sqrt n}\ll \kappa n^{-2}$, so our correction has admissible size too. If you want both endpoint coefficients to be $1$ and they are $1$ and $-1$ in the polynomial we constructed, just multiply by $1-x^{d+1}$ doubling the degree.

Recall that the Chebyshev polynomial $T_d(y)=\frac 12[(x-\sqrt{x^2-1})^d+(x+\sqrt{x^2-1})^d]$ with even $d$ has all its roots real, is bounded by $1$ on $[-1,1]$, is decreasing on $(-\infty,1]$ and is greater than $4$ at $-1-\frac C{d^2}$ for some absolute constant $C>0$. After proper rescaling and taking $Cd^{-2}\approx\delta\in(0,\frac 12)$, it turns into a polynomial $S_\delta(z)$ on $[0,1]$ such that the degree of $S$ is $\le C\delta^{-1/2}$, $|S(z)|\le S(0)=1$ for every $z\in[0,1]$ and $|S(z)|\le \frac 14$ when $z\in[\delta,1]$.

Edit: For completeness, let me also give a short proof that a polynomial $P(x)=\sum_{j=0}^na_j x^j$ with real coefficients $a_j$ satisfying $|a_j|\le 1$, $|a_0|=|a_n|=1$ cannot have more than $C\sqrt n$ real roots.

By considering $P(\pm x)$, $x^nP(\pm 1/x)$, we see that it suffices to bound the number of roots on $(0,1]$.

Recall that the Chebyshev polynomial $T_d(y)=\frac 12[(x-\sqrt{x^2-1})^d+(x+\sqrt{x^2-1})^d]$ with even $d$ has all its roots real, is bounded by $1$ on $[-1,1]$, is decreasing on $(-\infty,1]$ and is greater than $4$ at $1-\frac C{d^2}$ for some absolute constant $C>0$. After proper rescaling and taking $Cd^{-2}\approx\delta\in(0,\frac 12)$, it turns into a polynomial $S_\delta(z)$ on $[0,1]$ such that the degree of $S$ is $\le C\delta^{-1/2}$, $|S(z)|\le S(0)=1$ for every $z\in[0,1]$ and $|S(z)|\le \frac 14$ when $z\in[\delta,1]$.

Now choose $\delta=\frac 1n$ and put $$ Q(z)=S_\delta(z/n)S_{2\delta}(z/n)S_{4\delta}(z/n)\dots S_{2^m\delta}(z/n) $$ where $2^m\delta\in[\frac 14,\frac 12)$. Then $Q$ still has all roots real, the degree of $Q$ is at most $C\sqrt n\sum_{j\ge 0}2^{-j/2}$, $Q(0)=1$ and $Q(k)\le 4^{-q-1}$ for $k\ge 2^q$ for $0\le q\le m$. The last estimate implies that $\sum_{k=1}^n |Q(k)|<1=Q(0)$ for not too small $n$. Hence, in the polynomial $$ \widetilde P(x)=\sum_{k=0}^n a_kQ(k)x^k $$ the constant term dominates the sum of all other ones, so $\widetilde P$ has no roots on $(0,1]$.

Now write the factorization $Q(z)=a\prod_s(z-\lambda_s)$, $\lambda_s\in\mathbb R$. Then $$ \widetilde P=a\left[\prod_s D_{\lambda s}\right]P $$ where $D_\lambda f=xf'-\lambda f$ is the differential operator that acts on the polynomials by multiplying the $k$-th coefficient by $k-\lambda$.

Representing $D_\lambda f=x^{\lambda+1}\frac{d}{dx}[x^{-\lambda}f]$ and using Rolle's theorem, we conclude that each application of $D_\lambda$ can reduce the number of roots of $f$ on $(0,1]$ by at most $1$. But the degree of $Q$ is only $C\sqrt n$ and we have lost all roots of $P$ on $(0,1]$ when passing from it to $\widetilde P$. The end.

This is not an answer, just a response to David's request to present a construction of a polynomial $P(x)=\sum_{j=0}^d a_jx^j$ of arbitrarily high degree $d$ whose coefficients are real, bounded by $1$ in absolute value, satisfy $|a_0|=|a_d|=1$, and whose number of distinct real roots is of order $\sqrt{d}$. I believe that I've also seen the statement about pure $0,\pm 1$ coefficients somewhere, but my attempt to retrieve the proof from my memory or to reinvent it failed, so it might be a hallucination.

We will use the standard "pigeonholing with a minor correction in the end" mumbo-jumbo.

Take big $n>m,k$

Let $P(x)=exT(x)$ where $T$ is the Chebyshev's polinomial of degree $m$ adjusted to the interval $[e^{-1},1]$. Then $P$ has no free term, is of degree $m+1$, and has the alternance points $y_1,\dots,y_{m+1}$ of heights at least $1$. The coefficients of $P$ are bounded by $K^m$ for some absolute $K>0$. Let $x_j=y_j^{1/k}$

Consider all polynomials $Q$ of degree $3n$ with coefficients $\beta_s\in{0,e^{(s/(3n))^2}}$. Since $|Q(x_j)|\le 3en$ for every $Q$ and every $j$, and the total number of $Q$-s is $2^{3n}$ we can (by pigeonholing) find a set of $2^{2n}$ $Q$-s such that their values at each $x_j$ are confined to some intervals $I_j$ of length $6en2^{-n/m}$.

Fix one such $Q_0$ in that set. Note that the number of $Q$ whose coefficients differ from those of $Q$ only within an interval of indices of length $n$ is at most $n2^n\ll 2^{2n}-1$. Thus we can find $Q_1$ in the same set such that $$ R(x)=Q(x)-Q_1(x)=\sum_{s=a}^b \alpha_s x^s $$ with $b>a+n$, $\alpha_s\in\{0,\pm e^{(s/(3n))^2}\}$, $\alpha_a,\alpha_b\ne 0$, $|R(x_j)|\le 6en2^{-n/m}$ for all $j$.

Dividing $R(x)$ by $e^{(a/(3n))^2}x^a$, and taking into account that $x_j\ge e^{-1/k}$ for all $j$, we get a polynomial $S(x)$ of degree $d=b-a\in[n,3n]$ with coefficients $\gamma_s\in\{0,\pm e^{\psi(s)}\}$ where $\psi(s)=[(s+a)/(3n)]^2-[a/(3n)]^2$ and such that $|S(x_j)|\le 6en 2^{-n/m}e^{3n/k}$.

The key point is that $\psi$ is strictly convex and $0$ at $0$, so $$ e^{\psi(s)}\le e^{s\psi(d)/d}-\kappa n^{-2} $$ for $1\le s\le d-1$ with some $\kappa>0$. This we can correct the intermediate coefficients by about $n^{-2}$ and still have them under the geometric progression joining $|\gamma_0|=1$ and $|\gamma_d|=e^{\psi(d)}$. Then, by a trivial linear change of variable, we'll turn $\gamma_d$ into $\pm 1$ and make all intermediate coefficients $\le 1$.

We will use this correction possibility to turn smallness at $x_j$ into an alternance. To this end, we will just add $ 6en 2^{-n/m}e^{3n/k}P(x^k)$. The coefficients of this correction are bounded by $6en 2^{-n/m}e^{3n/k}K^m$, it has no free term and the degree $(m+1)k$.

Now choose $k\approx \sqrt n$ and $m\approx \sigma\sqrt n$. Then if $\sigma<1$, our correction stays inside the degree span of $S$, and $$ 6en 2^{-n/m}e^{3n/k}K^m\approx 6en 2^{-\sigma^{-1}\sqrt n}e^{3\sqrt n}K^{\sigma\sqrt n}\, $$ which for small $\sigma>0$ is less than $e^{-\sqrt n}\ll \kappa n^{-2}$, so our correction has admissible size too.

That's it. You can see, however, that the alternance is minuscule, so you should exercise utmost care with your suggested replacement of negative coefficients, if it can work at all!

This is not an answer, just a response to David's request to present a construction of a polynomial $P(x)=\sum_{j=0}^d a_jx^j$ of arbitrarily high degree $d$ whose coefficients are real, bounded by $1$ in absolute value, satisfy $|a_0|=|a_d|=1$, and whose number of distinct real roots is of order $\sqrt{d}$. I believe that I've also seen the statement about pure $0,\pm 1$ coefficients somewhere, but my attempt to retrieve the proof from my memory or to reinvent it failed, so it might be a hallucination.

We will use the standard "pigeonholing with a minor correction in the end" mumbo-jumbo.

Take big $n>m,k$

Let $P(x)=exT(x)$ where $T$ is the Chebyshev's polinomial of degree $m$ adjusted to the interval $[e^{-1},1]$. Then $P$ has no free term, is of degree $m+1$, and has the alternance points $y_1,\dots,y_{m+1}$ of heights at least $1$. The coefficients of $P$ are bounded by $K^m$ for some absolute $K>0$. Let $x_j=y_j^{1/k}$

Consider all polynomials $Q$ of degree $3n$ with coefficients $\beta_s\in{0,e^{(s/(3n))^2}}$. Since $|Q(x_j)|\le 3en$ for every $Q$ and every $j$, and the total number of $Q$-s is $2^{3n}$ we can (by pigeonholing) find a set of $2^{2n}$ $Q$-s such that their values at each $x_j$ are confined to some intervals $I_j$ of length $6en2^{-n/m}$.

Fix one such $Q_0$ in that set. Note that the number of $Q$ whose coefficients differ from those of $Q$ only within an interval of indices of length $n$ is at most $n2^n\ll 2^{2n}-1$. Thus we can find $Q_1$ in the same set such that $$ R(x)=Q(x)-Q_1(x)=\sum_{s=a}^b \alpha_s x^s $$ with $b>a+n$, $\alpha_s\in\{0,\pm e^{(s/(3n))^2}\}$, $\alpha_a,\alpha_b\ne 0$, $|R(x_j)|\le 6en2^{-n/m}$ for all $j$.

Dividing $R(x)$ by $e^{(a/(3n))^2}x^a$, and taking into account that $x_j\ge e^{-1/k}$ for all $j$, we get a polynomial $S(x)$ of degree $d=b-a\in[n,3n]$ with coefficients $\gamma_s\in\{0,\pm e^{\psi(s)}\}$ where $\psi(s)=[(s+a)/(3n)]^2-[a/(3n)]^2$ and such that $|S(x_j)|\le 6en 2^{-n/m}e^{3n/k}$.

The key point is that $\psi$ is strictly convex and $0$ at $0$, so $$ e^{\psi(s)}\le e^{s\psi(d)/d}-\kappa n^{-2} $$ for $1\le s\le d-1$ with some $\kappa>0$. This we can correct the intermediate coefficients by about $n^{-2}$ and still have them under the geometric progression joining $|\gamma_0|=1$ and $|\gamma_d|=e^{\psi(d)}$. Then, by a trivial linear change of variable, we'll turn $\gamma_d$ into $\pm 1$ and make all intermediate coefficients $\le 1$.

We will use this correction possibility to turn smallness at $x_j$ into an alternance. To this end, we will just add $ 6en 2^{-n/m}e^{3n/k}P(x^k)$. The coefficients of this correction are bounded by $6en 2^{-n/m}e^{3n/k}K^m$, it has no free term and the degree $(m+1)k$.

Now choose $k\approx \sqrt n$ and $m\approx \sigma\sqrt n$. Then if $\sigma<1$, our correction stays inside the degree span of $S$, and $$ 6en 2^{-n/m}e^{3n/k}K^m\approx 6en 2^{-\sigma^{-1}\sqrt n}e^{3\sqrt n}K^{\sigma\sqrt n}\, $$ which for small $\sigma>0$ is less than $e^{-\sqrt n}\ll \kappa n^{-2}$, so our correction has admissible size too.

That's it. You can see, however, that the alternance is minuscule, so you should exercise utmost care with your suggested replacement of negative coefficients, if it can work at all!