Distancia desde $x^n$ a polinomios menores

Question

Me interesa el $L_1$ distancia de $x^n$ a la $\mathbb R$ -span de $\{1,x,\ldots,x^{n-1}\}$ en algún intervalo. Podemos WLOG considerar el intervalo $[0,1]$ (digamos) porque el escalado y el desplazamiento sólo afectan a la distancia en un factor constante.

---

Hasta ahora tenemos estos resultados básicos:

Teorema $x^n$ no está en el $\mathbb R$ -span de $\{1,x,\ldots,x^{n-1}\}$

Prueba Supongamos que sí: $x^n = \sum_{i=0}^{n-1} a_i x^i$ . Diferenciar $n$ veces para obtener la contradicción $n! = 0$ .

Podemos reformular este teorema diciendo que $\| x^n - p(x) \| > 0$ para todos los polinomios de grado $< n$ .

Teorema No hay ninguna secuencia de polinomios en el tramo, con límite $x^n$ .

Prueba Tendríamos una secuencia $p_n(x) = \sum_{i=0}^{n-1} a_{i,n} x^i$ donde $x^n = \lim_{n \to \infty} p_n(x) = \sum_{i=0}^{n-1} (\lim_{n \to \infty} a_{i,n}) x^i$ Pero eso es una contradicción.

---

Junto con el resultado anterior, esto implica que debería haber alguna $h(n)$ tal que $\| x^n - p(x) \| > h$ .

Mi pregunta es sobre la búsqueda de algunos $h$ . ¿Cómo podríamos hacerlo? ¿Existen teoremas relevantes?

Mi primera idea fue que podríamos usar la inducción y encontrar alguna forma de decir: Dado que sólo podemos llegar a $r$ de la derivada sólo podemos llegar a $h(r)$ de la función en sí.. pero encontrar $h(r)$ parece tan difícil como encontrar $h$ en absoluto.

Answer 1

UPDATE Después de todo, tenía razón la primera vez.

Afirmo que el grado $n$ polinomio mónico con un mínimo de $L_1$ norma es $\prod_{k=1}^n (x-\cos^2(\pi k/(2n+2)))$ .

Según los argumentos estándar de compactación, existe tal polinomio mínimo, aunque no está claro si es o no único. Sea $f$ sea un polinomio que alcance el mínimo.

Lema: El polinomio $f$ tiene $n$ raíces distintas en el intervalo $(0,1)$ .

Prueba: Supongamos por el contrario que $f$ tenía menos raíces. Dejemos que $\rho_1$ , $\rho_2$ , ..., $\rho_m$ sean aquellas raíces de $f$ en $(0,1)$ que tienen multiplicidad impar. Entonces $f$ tiene el mismo signo, o el contrario, que $g(x) := \prod(x-\rho_i)$ en todas partes en $[0,1]$ . Para $\epsilon$ suficientemente pequeño, y la elección correcta del signo, $| f \pm \epsilon g(x) |_1 < |f|_1$ . $\square$

Que las raíces de $f$ sea $0 < \rho_1 < \rho_2 < \cdots < \rho_n <1$ y definir formalmente $\rho_0=0$ y $\rho_{n+1}=1$ para mayor comodidad.

Como aprendemos en cualquier clase de cálculo, para minimizar una función, debemos averiguar cómo cambia cuando se perturba la entrada. Sea $g$ sea cualquier polinomio de grado $<n$ . Para los pequeños $\epsilon$ el teorema de la función implícita nos dice que $f + \epsilon g$ tiene $n$ raíces en $(0,1)$ dado por funciones suaves $\rho_i(\epsilon)$ . (Utilizamos el lema para saber que $f'(\rho_k) \neq 0$ para poder aplicar el teorema de la función implícita). Establecemos $\rho_0(\epsilon)=0$ y $\rho_{n+1}(\epsilon) = 1$ .

Entonces $$|f+\epsilon g|_1 = \sum_{k=0}^n (-1)^{n-k} \int_{\rho_k(\epsilon)}^{\rho_{k+1}(\epsilon)} f+\epsilon g$$ $$ = \sum_{k=0}^n (-1)^{n-k} \left( \int_{\rho_k}^{\rho_{k+1}} f+\epsilon g + \int_{\rho_k}^{\rho_k(\epsilon)} f+\epsilon g - \int_{\rho_{k+1}}^{\rho_{k+1}(\epsilon)} f+\epsilon g \right)$$ $$=|f|_1 + \epsilon \sum_{k=0}^n (-1)^{n-k} \int_{\rho_k}^{\rho_{k+1}} g + \mbox{error}$$ donde el error proviene de las dos últimas integrales.

Veamos estas integrales. Como $\rho_k$ es una función suave, tenemos $\rho_k(\epsilon)= \rho_k + O(\epsilon)$ por lo que la anchura del intervalo es $O(\epsilon)$ . También, $f(\rho_k) =0$ y $f$ es suave por lo que $f(x) = O(\epsilon)$ para $x \in (\rho_k, \rho_k+O(\epsilon))$ . Finalmente, $g$ está acotado, por lo que $g=O(1)$ . Así que nuestros términos de error son todos de la forma $$\int_{\rho_k}^{\rho_k + O(\epsilon)} \left( O(\epsilon) + \epsilon O(1) \right) = O(\epsilon^2).$$ Así que $$|f+\epsilon g|_1 = |f|_1 + \epsilon \sum_{k=0}^n (-1)^{n-k} \int_{\rho_k}^{\rho_{k+1}} g + O(\epsilon^2).$$

Vemos que la derivada direccional de $| \ |_1$ en la dirección $g$ existe. Por lo tanto, si $f$ debe ser de un mínimo de $| \ |_1$ , entonces debemos tener
Criterio: Para cada polinomio $g$ de grado $< n$ tenemos $$\sum_{k=0}^n (-1)^{n-k} \int_{\rho_k}^{\rho_{k+1}} g=0$$

---

Unicidad de la solución: Primero mostraré que hay una única $n$ -tupla $(\rho_1, \ldots, \rho_n) \in [0,1]^n$ que obedece al criterio. Obsérvese que el criterio es lineal en $g$ por lo que basta con comprobar el criterio para los monomios de grado $<n$ . Para simplificar la notación, me limitaré al caso $n=2m$ . Es conveniente cambiar el nombre $(\rho_1, \ldots, \rho_{2m})$ como $(\alpha_1, \beta_1, \alpha_2, \beta_2, \ldots, \beta_m)$ .

Aplicación del criterio con $g=x^{k-1}$ vemos que, para $1 \leq k \leq n$ tenemos $$\frac{1}{k} \left( \alpha_1^k - (\beta_1^k-\alpha_1^k) + (\alpha_2^k-\beta_1^k) - \cdots +(1-\beta_m^k) \right)=0.$$ Equivalentemente $$2 \sum \frac{\alpha_i^k}{k} + \frac{1}{k} = 2 \sum \frac{\beta_i^k}{k} \ \mathrm{for} \ 1 \leq k \leq n.$$

Ahora viene la parte que me pareció inteligente. Organizar lo anterior $n$ ecuaciones en una función generadora: $$\sum \frac{\alpha_i^k x^k}{k} + \frac{1}{2} \sum \frac{x^k}{k} = \sum \frac{\beta_i^k x^k}{k} + O(x^{n+1}).$$ Esto da $$\sum \log \frac{1}{1-\alpha_i x} + \frac{1}{2} \sum \log \frac{1}{1-x} = \sum \log \frac{1}{1-\beta_i x} + O(x^{n+1})$$ o $$\prod (1-\alpha_i x) \sqrt{1-x} = \prod (1-\beta_i x) + O(x^{n+1}).$$ Set $\prod(1-\alpha_i x) = 1+a_1 x + a_2 x^2 + \cdots + a_m x^m$ y $\prod(1-\beta_i x) = 1+b_1 x + b_2 x^2 + \cdots + b_m x^m$ . Así que $$\left( 1+a_1 x + a_2 x^2 + \cdots + a_m x^m \right) \sqrt{1-x} = \left( 1+b_1 x + b_2 x^2 + \cdots + b_m x^m \right) + O(x^{n+1}).$$

Escribiendo nuestra esta serie de potencias una equiparación de coeficientes de $x^k$ para $k\leq n$ obtenemos lineal ecuaciones para el $a_i$ y $b_j$ . En particular, el conjunto de soluciones es un espacio lineal y no debería ser muy difícil (no lo he comprobado) ver que es un espacio de dimensión cero. Por lo tanto, sujeto al problema del álgebra lineal, la solución es única.

El punto práctico clave es que los ordenadores resuelven las ecuaciones lineales muy rápidamente. Así que tuve Mathematica ve y resuelve estas ecuaciones por mí para varios valores de $n$ . Para $n=10$ Tengo $$a(x) = \frac{1}{1024} \left( 1024 - 2816 x + 2816 x^2 - 1232 x^3 + 220 x^4 - 11 x^5 \right)$$ $$b(x) = \frac{1}{1024} \left( 1024 - 2304 x + 1792 x^2 - 560 x^3 + 60 x^4 - x^5 \right).$$ Así que escribí $1024, -2816, 2816, -1232, 220, -11$ y $1024, -2304, 1792, -560, 60, -1$ en La enciclopedia de Sloane e inmediatamente se enteró de que se trataba de coeficientes de Polinomios de Chebyshev del primer y segundo tipo. Me costó un poco de tiempo conseguir todos los problemas de indexación, pero finalmente me di cuenta de que esto significaba que mi solución era $$f(x) = \prod_{k=1}^n (x-\cos^2(\pi k/(2n+2))).$$

---

Una vez que sabemos que la solución es única, basta con comprobar que $f$ obedece al Criterio. Sea $h$ sea la función $[0,1] \to \{ -1 , 1 \}$ que cambia de signo en los números $\cos^2(\pi k/(2n+2))$ . Queremos demostrarlo:

Reclamación Para cualquier polinomio $g$ de grado $<n$ tenemos $$\int_0^1 h(x) g(x) dx=0.$$

La forma de $h$ sugiere poner $x=\cos^2 t$ , por lo que queremos $$\int_0^{\pi/2} h(\cos^2 t) g(\cos^2 t) (2 \sin t \cos t) dt=0.$$ Ahora, $h(\cos^2 t)$ cambia las señales en $k \pi/(2n+2)$ . Sea $\sigma$ sea la función de onda cuadrada: $\sigma(u)$ es $\pm 1$ y cambia de signo en múltiplos enteros de $\pi$ . Así que queremos $$\int_{0}^{\pi/2} \sigma( (2n+2) t) g((\cos (2t)+1)/2) \sin(2t) dt=0.$$ Configurar $u=2 t$ y observando que el integrando es una función par, obtenemos $$\int_{-\pi}^{\pi} \sigma( (n+1) u) g((\cos u+1)/2) \sin u \ du=0.$$

Además, si $g$ es un polinomio de grado $<n$ entonces el polinomio $\hat{g}(w) := g((u+1)/2)$ también tiene grado $<n$ . Así que nuestro objetivo es mostrar:

Para cualquier polinomio $\hat{g}$ de grado $<n$ tenemos $\int_{-\pi}^{\pi} \sigma((n+1) u) \hat{g}(\cos u) \sin u \ du=0$ .

Basta con comprobarlo para una base de polinomios $\hat{g}_0$ , ..., $\hat{g}_{n-1}$ utilizamos los polinomios de Chebyshev, de modo que $\hat{g}_m(\cos u) = \cos (mu)$ . Así que nuestro objetivo puede reescribirse como mostrar que $$\int_{- \pi}^{\pi} \sigma((n+1) u) \cos (mu) \sin u \ du=0 \ \mathrm{for} \ 0 \leq m < n$$ o que $$\frac{1}{2} \int_{- \pi}^{\pi} \sigma((n+1) u) \left( \sin ((m+1) u) - \sin((m-1) u) \right) du \ \mathrm{for} \ 0 \leq m < n.$$

Pero $\sigma(v)$ tiene una serie de Fourier bien conocida $\sin(v) + \frac{1}{3} \sin 3 v + \frac{1}{5} \sin (5v) + \cdots$ Así que $\sigma((n+1)u)$ tiene una serie de Fourier que comienza $\sin((n+1)u) + \cdots$ . Vemos que $\sigma((n+1) u)$ es ortogonal a las funciones $\sin (ru)$ para $r \leq n$ que establece inmediatamente la reclamación requerida. QED

Answer 2

Para minimizar $$ \int_0^1\left|x^n-a_{n-1}x^{n-1}-a_{n-2}x^{n-2}-\dots-a_0\right|\;\mathrm{d}x\tag{1} $$ podemos diferenciar con respecto a cada $a_k$ para llegar a los puntos críticos $$ \int_0^1\operatorname{sgn}(x^n-a_{n-1}x^{n-1}-a_{n-2}x^{n-2}-\dots-a_0)\;x^k\tag{2}\;\mathrm{d}x=0 $$ para $k=0\dots n-1$ .

El mínimo $P(x)=x^n-a_{n-1}x^{n-1}-a_{n-2}x^{n-2}-\dots-a_0$ debe tener $n$ raíces distintas en $(0,1)$ . Si no, entonces hay un polinomio $Q(x)$ de grado $< n$ que tiene el mismo signo que $P(x)$ para todos $x\in[0,1]$ . Entonces para algunos $\epsilon>0$ , $\int_0^1|P(x)-\epsilon Q(x)|\mathrm{d}x<\int_0^1|P(x)|\mathrm{d}x$ .

Dejemos que $0< x_1< x_2<\dots< x_n<1$ sean las raíces de $P(x)$ . Por $(2)$ tenemos que $$ \frac{1}{k+1}\left[(x_1^{k+1}-0)-(x_2^{k+1}-x_1^{k+1})+(x_3^{k+1}-x_2^{k+1})-\dots+(-1)^{n-1}(1-x_n^{k+1})\right]=0 $$ para cada $k=0\dots n-1$ lo que equivale a $$ x_n^k-x_{n-1}^k+x_{n-2}^k-\dots+(-1)^{n-1}x_1^k=\tfrac12\tag{3} $$ para cada $k=1\dots n$ . Ecuación $(3)$ tiene raíces $$ x_j=\sin^2\left(\frac{\pi}{2}\frac{j}{n+1}\right)\tag{4} $$ para $j=1\dots n$ . Es decir, ya que $\displaystyle \operatorname{Re}\left(\frac{1}{e^{ix}+1}\right)=\frac12$ , $$ \begin{align} &\sum_{j=1}^n(-1)^{n-j}\sin^{2k}\left(\frac{\pi}{2}\frac{j}{n+1}\right)\\ &=(-\tfrac14)^k\sum_{j=1}^n(-1)^{n-j}\sum_{m=0}^{2k}\binom{2k}{m}(-1)^m\exp\left(i\pi\frac{(k-m)j}{n+1}\right)\\ &=(-\tfrac14)^k(-1)^{n}\sum_{m=0}^{2k}\binom{2k}{m}(-1)^m\left(\frac{(-1)^{k-m+n}-1}{\exp\left(i\pi\frac{k-m}{n+1}\right)+1}-1\right)\\ &=(\tfrac14)^k\sum_{m=0}^{2k}\binom{2k}{m}(-1)^{k-m+n}\frac{(-1)^{k-m+n}-1}{\exp\left(i\pi\frac{k-m}{n+1}\right)+1}\\ &=(\tfrac14)^k\sum_{m=0}^{2k}\binom{2k}{m}\frac{1-(-1)^{k-m+n}}{\exp\left(i\pi\frac{k-m}{n+1}\right)+1}\\ &=(\tfrac14)^k\sum_{m=0}^{2k}\binom{2k}{m}\frac12\left(1-(-1)^{k-m+n}\right)\\ &=(\tfrac14)^k\sum_{m=0}^{2k}\binom{2k}{m}\frac12\\ &=\frac12\tag{5} \end{align} $$ Así, el polinomio mónico mínimo es $$ P(x)=\prod_{j=1}^n\left(x-\sin^2\left(\frac{\pi}{2}\frac{j}{n+1}\right)\right)\tag{6} $$