Intereting Posts

Matrix determinant lemma with adjugate matrix
Mean of an increasing function over exponential distribution
Examples when vector $(X,Y)$ is not normal 2D distribution, but X and Y are.
The additive groups $\mathbb{R}^n$ for $n\geq 1$ are all isomorphic.
How to prove that this function is primitive recursive?
Why do we need Hausdorff-ness in definition of topological manifold?
Induction Proof: Fibonacci Numbers Identity with Sum of Two Squares
Evaluating the elliptic integral $\int_{-\pi}^\pi\frac{dx}{\sqrt{(t-2\cos x)^2-4}}$
Lie algebra and left-invariant vector fields
Odds of guessing suit from a deck of cards, with perfect memory
Probability of a set that has infinite Lebesgue measure
Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction
Noetherian ring with finitely many height $n$ primes
$f'(c) \ge 0 , \forall c \in (a,b)$ then $f$ is increasing in $$ , proof of this without Mean Value theorem
asymptotic expansion from 3 leading terms

I’d like to be able to construct polynomials $p$ whose graphs look like this:

We can assume that the interval of interest is $[-1, 1]$. The requirements on $p$ are:

- What algorithm is used by computers to calculate logarithms?
- Is a non-repeating and non-terminating decimal always an irrational?
- Numbers $p-\sqrt{q}$ having regular egyptian fraction expansions?
- Accelerating Convergence of a Sequence
- How can I choose the best algorithm to integrate ODE's numerically?
- Showing that the sequence $x_n=\frac{1}{3}x_{n-1}(4+x_{n-1}^3)$ where $x_0=-0.5$ quadratically converges

(1) Equi-oscillation (or roughly equal, anyway) between two extremes. A variation of 10% or so in the values of the extrema would be OK.

(2) Zero values and derivatives at the ends of the interval, i.e. $p(-1) = p(1) =p'(-1) = p'(1) = 0$

I want to do this for degrees up to around 30 or so. Just even degrees would be OK.

If it helps, these things are a bit like Chebyshev polynomials (but different at the ends).

The one in the picture has equation $0.00086992073067855669451 –

0.056750328789339152999 t^2 +

0.60002383910750621904 t^4 –

2.3217878459074773378 t^6 +

4.0661558859963998471 t^8 –

3.288511471137768132 t^{10} + t^{12}$

I got this through brute-force numerical methods (solving a system of non-linear equations, after first doing a lot of work to find good starting points for iteration). I’m looking for an approach that’s more intelligent and easier to implement in code.

Here is one idea that might work. Suppose we want a polynomial of degree $n$. Start with the Chebyshev polynomial $T_{n-2}(x)$. Let $Q(x) = T_{n-2}(sx)$, where the scale factor $s$ is chosen so that $Q(-1) = Q(1) = 0$. Then let $R(x) = (1-x^2)Q(x)$. This satisfies all the requirements except that its oscillations are too uneven — they’re very small near $\pm1$ and too large near zero. Redistribute the roots of $R$ a bit (somehow??) to level out the oscillations.

**Comments on answers**

Using the technique suggested by achille hui in an answer below, we can very easily construct a polynomial with the desired shape. Here is one:

The only problem is that I was hoping for a polynomial of degree 12, and this one has degree 30.

Also, I was expecting the solution to grow monotonically outside the interval $[-1,1]$, and this one doesn’t, as you can see here:

- All roots of the quartic equation $a x^4 + b x^3 + x^2 + x + 1 = 0$ cannot be real
- Polynomial $P(x,y)$ with $\inf_{\mathbb{R}^2} P=0$, but without any point where $P=0$
- construct polynomial from other polynomials
- What are some meaningful connections between the minimal polynomial and other concepts in linear algebra?
- Is $x^3-9$ irreducible over the integers mod 31?
- Content of a polynomial
- Polynomials representing primes
- Common factors of cyclotomic polynomials and polynomials with prime coefficients
- How to transform the general quintic to the Brioschi quintic form?
- Is an ideal generated by multilinear polynomials of different degrees always radical?

Starting with any Chebyshev polynomial of $1^{st}$ kind $T_n(x), n > 2$,

and any positive root $a$ of it. Compose $T_n(ax)$ with any polynomial $q(x)$

which is monotonic over $[-1,1]$ that satisfies $q(-1) = -1, q(1) = 1$ and

$q'(-1) = q'(1) = 0$ , then $T_n(a q(x))$ is something you want. For example,

$$

T_n\left(\cos\left(\frac{\pi}{2n}\right) \frac{x(3-x^2)}{2}\right)

$$

Here the Newton version of the Asymptote code that does the job. Now it runs really fast in the range requested. The polynomial is encoded by its roots (stored in the x array). Thanks to the kind soul who had the patience to type 4 spaces in the beginning of each line :).

**Edit.** Since bubba wanted to know where the main iteration step came from, here is a short explanation. First of all, as I said, it is convenient to work with the sum $f(x)=\sum_k\log|x-x_k|$ instead of the product $\prod_k (x-x_k)$ (for both numerical and analytic reasons). This sum dives to $-\infty$ at each root $x_k$ and achieves a local maxima $y_{k-1}$ and $y_k$ at some points $z_{k-1}\in(x_{k-1},x_k)$ and $z_k\in(x_k,x_{k+1})$. Now, let’s make a leap of faith and assume that $y_{k-1}$ and $y_k$ are not very different and also that the $z$-points are approximately in the middle of the corresponding intervals (the first assumption is bound to happen sooner or later if our algorithm works at all and the second one is actually poorly justified by itself but more reasonable than any other wild guess about the location). We want to shift the root $x_k$ so that the maxima $y_{k-1}$ and $y_k$ will become equal. Linearizing and assuming that the intervals $(x_{k-1},x_k)$ and $(x_k,x_{k+1})$ are of approximately equal length, we see that the partial derivatives of $f(z_{k-1})$ and $f(z_k)$ with respect to $x_k$ are about $\frac{1}{4(x_{k+1}-x_{k-1})}$ and $-\frac{1}{4(x_{k+1}-x_{k-1})}$ respectively, so, solving the corresponding linear equation, we get the correction $p=(y_k-y_{k-1})(x_{k+1}-x_{k-1})/8$ to apply to $x_k$. That explains the main formula. Unfortunately, if we just use it literally, a lot of crazy things may happen up to the loss of the order of roots, so we should make sure that our shifts are not too large at the early stages when the disbalances are quite large. The second line is a mere truncation of the shifts to the size which, we believe, will constitute only a fraction of the distance between roots (which initially is $2/n$), so that no rearrangement of roots or screwing up of the Newton iteration scheme will occur. The exact choice of the constant $0.3$ is empirical (i.e., I just checked that it worked in the requested range and, say, $0.5$ did not). The formal justification of the algorithm will require quite a lot of careful estimates (you can easily notice that some of the assumptions I made are on the border of wishful thinking) but, since all we need is one sequence of polynomials of not too high degree, I thought it

would be worth trying without worrying too much about formal proofs because the final result is verifiable and once you get it, who cares what steps led to it? I know, this is a dismal thing to say for a mathematician, but, since I’m wearing a programmer’s hat here,

I decided I could try to get away with it :).

```
int n=51;
//The number of intermediate roots plus 1 (degree-3)
real[] x,y,z;
//The root array, the maximum array. and the critical point array
for(int k=0;k<n+1;++k) {x[k]=2*k/n-1; if(k>0) z[k-1]=(x[k-1]+x[k])/2;}
//Just initialized the roots to an arithmetic progression
//and the critical points to midpoints between roots
real f(real t)
{
real s=2*log(1-t^2);
for(int k=1;k<n;++k) s+=log(abs(t-x[k]));
return s;
}
//This is just the logarithm of the absolute value of the polynomial
//with double roots at +1,-1 and simple roots at x[k], k=1,...,n-1
real g(real t)
{
real s=2*(1/(t+1)+1/(t-1));
for(int k=1;k<n;++k)
s+=1/(t-x[k]);
return s;
}
//This is the derivative of f
real G(real t)
{
real s=-2*(1/(t+1)^2+1/(t-1)^2);
for(int k=1;k<n;++k)
s-=1/(t-x[k])^2;
return s;
}
//This is the derivative of g
for(int m=0;m<15*n+30;++m)
//The outer cycle; the number of iterations is sufficient
//to cover n up to 70 with the roots found with machine precision (1E-15)
{
for(int k=0;k<n/2;++k)
{
real a=z[k];
a-=g(a)/G(a);
y[k]=f(a); y[n-1-k]=y[k];
z[k]=a; z[n-1-k]=-a;
}
//Newton update of critical points with symmetry taken into account
real[] xx=copy(x);
for (int k=1;k<n/2;++k)
{
real p=(y[k]-y[k-1])*(xx[k+1]-xx[k-1])/8;
if (abs(p)>0.3/n) p*=0.3/n/abs(p);
x[k]+=p; x[n-k]-=p;
}
//The main iteration step: move each roots to balance the maxima
//adjacent to it. It can be done
//better if we look beyond the adjacent maxima to evaluate what will
//happen but, since it works in a reasonable time, I was too lazy to bother.
}
write(x);
write(y);
//outputs the roots and the maxima of f. Note that the roots at +1 and -1
//are double and the rest are simple.
pause();
//Just doesn't let the window close before you look at it.
```

- Is $123456788910111121314\cdots$ a $p$-adic integer?
- Using generating functions find the sum $1^3 + 2^3 + 3^3 +\dotsb+ n^3$
- What is a vector?
- Lagrange multiplier constrain critical point
- Does there exist coprime numbers $a$ and $b$ such that $a^n+b$ is composite for every $n$?
- Recurrence relation (linear, second-order, constant coefficients)
- Closed points are dense in $\operatorname{Spec} A$
- Showing that projections $\mathbb{R}^2 \to \mathbb{R}$ are not closed
- A contest question on probability
- Expected number of rolling a pair of dice to generate all possible sums
- Covering with most possible equal size subsets having pairwise singleton intersections
- How can 0.149162536… be normal?
- linear algebra over a division ring vs. over a field
- Find the velocity of a flow
- What is a good complex analysis textbook?