Versión gaussiana del teorema de Dvoretzky

FACULTAD DE MATEMÁTICAS DEPARTAMENTO DE ANÁLISIS MATEMÁTICO Trabajo Fin de Grado VERSIÓN GAUSSIANA DEL TEOREMA DE DVORETZKY Juan Galán Casado - Grado en Matemáticas Julio 2024 Dirigido por: Carlos Hugo Jiménez Gómez Rafael Villa Caro Índice general Resumen................................ 1 Summary................................ 3 1. Definiciones y resultados iniciales 7 1.1. Geometría convexa . . . . . . . . . . . . . . . . . . . . . . . 7 1.2. Distancia de Banach- Mazur . . . . . . . . . . . . . . . . . . 17 1.3. Medidas ............................. 19 1.4. Medidas de probabilidad . . . . . . . . . . . . . . . . . . . . 22 2. El Teorema de Dvoretzky 31 2.1. Las versiones del Teorema de Dvoretzky . . . . . . . . . . . 32 2.2. Versión gaussiana . . . . . . . . . . . . . . . . . . . . . . . . 34 3. Prueba gaussiana del Teorema de Dvoretzky 37 3.1. Resultados previos . . . . . . . . . . . . . . . . . . . . . . . 37 3.2. Teorema de Dvoretzky . . . . . . . . . . . . . . . . . . . . . 42 Bibliografía 45 Resumen El objetivo de este trabajo es presentar todas las herramientas necesarias para entender el Teorema de Dvoretzky en sus versiones más clásicas para después poder probar una más novedosa, la versión gaussiana, enunciada y demostrada usando matrices aleatorias con distribución gaussiana. Para ello, primero deberemos definir los conceptos básicos de Geometría Convexa, establecer las relaciones existentes entre algunos espacios y sus bolas unitarias e introducir la distancia de Banach- Mazur. Después trataremos algunos elementos esenciales de Teoría de la Probabilidad que nos harán falta para al fin poder explicar con detalle el mencionado Teorema y la demostración usando matrices aleatorias. 1 Summary The aim of this project is to present all the necessary tools to understand Dvoretzky’s Theorem in its more classical versions, and then to be able to prove a more novel one, the Gaussian version, formulated and proven using random matrices. To achieve this, we must first define the basic concepts of convex geometry, establish the relationships between some spaces and their unit balls, and introduce the Banach-Mazur distance. Then, we will address some essential elements of probability theory that we will need in order to finally explain the aforementioned theorem in detail and provide the proof using random matrices. 3 10 CAPÍTULO 1. DEFINICIONES Y RESULTADOS INICIALES No convexo No simétrico Figura 1.3: Ejemplos de conjunto simétrico pero no convexo y viceversa. Decimos que T es un cuerpo convexo si es convexo, cerrado, acotado y con el interior no vacío. Proposición 1.7. (Espacios normados y cuerpos convexos simétricos). 1. Sea X= (Rn,∥·∥)un espacio normado, entonces, su bola unitaria, BX:={x∈X| ∥x∥ ≤ 1}, es un cuerpo convexo simétrico en Rn. 2. Recíprocamente, sea Kun cuerpo convexo simétrico en Rn. Entonces, K es la bola unitaria del espacio normado X= (Rn,∥·∥K)con ∥·∥K la norma dada por el funcional de Minkowski de K, definido para todo x∈Rncomo ∥x∥K:= ´ınf{t > 0 : x t∈K}.(1.2) Demostración. 1. La bola unitaria es cerrada y acotada por definición y la simetría es trivial por la positividad de la norma. La convexidad se tiene sin más que usar la desigualdad triangular y la homogeneidad de la norma. 2. Basta comprobar que ∥·∥Kverifica la definición de norma (definición 1.1) y observar que x∈Ksi y sólo si ∥x∥K≤1. En efecto, se puede observar que los ejemplos de bolas dados en las Figuras 1.1 y en 1.2 son convexos y simétricos. Vemos en la Figura 1.4 un ejemplo de polígono convexo y simétrico en R2y cómo se define la norma dada por su funcional de Minkowski. 1.1. GEOMETRÍA CONVEXA 11 Figura 1.4: Funcional de Minkowski . Definición 1.8. Llamamos combinación convexa de los puntos x1, . . . , xm∈Rna una suma de la forma m X i=1 λixi, donde los λison números reales no negativos y Pm i=1 λi= 1. Sea T⊂Rn, la envolvente convexa de T, denotada como Conv(T), es el conjunto convexo más pequeño que contiene a T. Formalmente, se define como el conjunto de todas las combinaciones convexas de puntos en T, esto es: Conv(T) = (m X i=1 λixi|xi∈T, λi≥0, m X i=1 λi= 1, m ∈N). Alternativamente, la envolvente convexa de Ttambién puede ser descrita como la intersección de todos los conjuntos convexos que contienen a T: Conv(T) = \{C⊆Rn|T⊆CyCes convexo}. Llamamos politopo ndimensional a la envolvente convexa de una colección finita de puntos en Rn. El siguiente resultado clásico de Análisis Funcional nos será de utilidad en su versión finito dimensional. 12 CAPÍTULO 1. DEFINICIONES Y RESULTADOS INICIALES Colección finita de puntos Envolvente convexa Figura 1.5: Un politopo ndimensional es la generalización a ndimensiones del concepto de polígono en 2 dimensiones o de poliedro en 3. Teorema 1.9. (Teorema de Hahn-Banach, versión geométrica en Rn). Sea Cun subconjunto convexo no vacío de Rny sea p∈Rntal que p /∈C. Entonces, existe un vector v∈Rny un número real αtales que: ⟨p, v⟩> α ≥ ⟨x, v⟩para todo x∈C. Definición 1.10. Sea VyWespacios vectoriales. Una aplicación T:V→W se llama una aplicación lineal si para todos u, v ∈Vyλ∈R, se cumple: 1. T(u+v) = T(u) + T(v) 2. T(λu) = λT(u) Definición 1.11. Dado un espacio vectorial X, el espacio dual de X, denotado por X∗, es el conjunto de todas las aplicaciones lineales y continuas de Xen R. Definición 1.12. Sea E⊆Rn, el complemento ortogonal de Ese define como E⊥:={x∈X| ⟨x, y⟩= 0 para todo y∈E}. Definición 1.13. Sea E⊆Rn, la proyección ortogonal de un vector x∈Rn sobre Ees el único vector PE(x)∈Etal que: x−PE(x)∈E⊥. La proyección ortogonal de un conjunto K⊂Rnsobre Ese define entonces como PE(K):={PE(x)|x∈K} 1.1. GEOMETRÍA CONVEXA 13 Proposición 1.14. Sea E⊂Rny sean x∈Rnye∈E. Se tiene que ⟨x, e⟩=⟨PE(x), e⟩. Demostración. Sea x∈Rn, entonces, por definición, x−PE(x)∈E⊥y, por tanto, ⟨x−PE(x), e⟩= 0 para todo e∈E. Ahora, por linealidad del producto escalar se tiene que ⟨x, e⟩=⟨PE(x), e⟩para todo e∈E. Proposición 1.15. Sean X= (Rn,∥·∥)un espacio normado, Ksu bola unitaria y E⊆Rnun subespacio vectorial. Entonces, la bola unitaria de (E, ∥·∥E) es la intersección K∩E, donde ∥·∥Ees la norma inducida en Epor la norma ∥·∥de X, es decir, ∥y∥E=∥y∥para todo y∈E. Definición 1.16. Dado un subconjunto Kde Rn, el conjunto polar K◦se define como K◦:={y∈Rn:⟨x, y⟩ ≤ 1para todo x∈K}. Ejemplos 1.17. Se tiene: 1. (Bn 2)◦=Bn 2. Veámoslo. Dado x= 0,x ∥x∥∈Bn 2, por lo que, si x∈(Bn 2)◦, se tiene que ⟨x, x ∥x∥⟩=∥x∥ ≤ 1, de donde se deduce que x∈Bn 2. Ahora, si x∈Bn 2ya∈Bn 2, entonces ⟨x, a⟩≤∥x∥∥a∥ ≤ 1. Por lo que x∈(Bn 2)◦y se completa la prueba. 2. (Bn 1)◦=Bn ∞. La prueba es similar a la anterior, usando la desigualdad ⟨x, y⟩ ≤ ∥x∥∞∥y∥1. 14 CAPÍTULO 1. DEFINICIONES Y RESULTADOS INICIALES 3. Si Ees un elipsoide con semiejes a1, . . . , an>0, entonces E◦es un elipsoide con semiejes 1/a1,...,1/an. 4. Si Kes un politopo de kvértices y mcaras, entonces K◦es un politopo de kcaras y mvértices. Proposición 1.18. (Propiedades del polar). Sean KyLconjuntos convexos en Rn. Entonces: 1. K◦es convexo. 2. (K∪L)◦=K◦∩L◦. 3. Si K⊂L, entonces L◦⊂K◦. 4. Sea λ > 0, entonces (λA)◦= (1/λ)A◦ Demostración. 1. Sean y1, y2∈K◦yλ∈[0,1]. Queremos probar que para todo x∈K, ⟨x, λy1+ (1 −λ)y2⟩ ≤ 1. Utilizando la linealidad del producto escalar, obtenemos: ⟨x, λy1+ (1 −λ)y2⟩=λ⟨x, y1⟩+ (1 −λ)⟨x, y2⟩. Dado que y1, y2∈K◦, por definición tenemos que ⟨x, y1⟩ ≤ 1y ⟨x, y2⟩ ≤ 1, por lo que λ⟨x, y1⟩+ (1 −λ)⟨x, y2⟩ ≤ 1, lo que completa la prueba. 2. (K∪L)◦={x∈Rn|⟨x, y⟩ ≤ 1para todo y∈K∪L}={x∈ Rn|⟨x, y⟩ ≤ 1para todo y∈K}∩{x∈Rn|⟨x, z⟩ ≤ 1para todo z∈ L}=K◦∩L◦ 3. Sea x∈L◦,entonces, por definición, ⟨x, y⟩ ≤ 1para todo y∈L, por lo que ⟨x, z⟩ ≤ 1para todo y∈Ky se tiene que x∈K◦. 1.1. GEOMETRÍA CONVEXA 15 4. Probemos que (λA)◦⊆(1/λ)A◦ Sea y∈(λA)◦. Por definición, esto significa que: ⟨x, y⟩ ≤ 1para todo x∈λA. Esto se puede reescribir como ⟨λa, y⟩ ≤ 1para todo a∈Ay, usando la linealidad del producto escalar, λ⟨a, y⟩ ≤ 1para todo a∈A. Sin más que dividir ambos lados de la desigualdad por λse prueba que y∈(1/λ)A◦y se deduce la primera inclusiòn. Aplicando lo anterior a λ−1yλA se obtiene la otra inclusión. Se tienen también las siguientes propiedades. Proposición 1.19. (Propiedades del polar II). Sea K⊆Rn. 1. Si Kes acotado, entonces el origen es interior a K◦. 2. Si el origen es interior a K, entonces K◦es acotado. 3. En consecuencia, si Kes un cuerpo convexo con el origen en su interior, K◦también lo es. Además, se tiene que (K◦)◦=K. Demostración. 1. Sea K acotado, por la definición 1.6, existe una constante R > 0 tal que K⊂RBn 2. Usando la proposición 1.18 y el ejemplo 1.17, tenemos: (RBn 2)◦=1 RBn 2⊂K◦, lo que implica que el origen es interior a K◦. 2. Recíprocamente, si el origen es interior a K, existe ε > 0tal que εBn 2⊂K. Usando de nuevo la proposición 1.18 y el ejemplo 1.17, tenemos: K◦⊂(εBn 2)◦=1 εBn 2, lo que implica que K◦es acotado. 3. Se sigue de la definición (K◦)◦={x∈Rn| ⟨x, y⟩ ≤ 1para todo y∈K◦}. 16 CAPÍTULO 1. DEFINICIONES Y RESULTADOS INICIALES Proposición 1.20. Sea Kun cuerpo convexo en Rncon el origen en su interior y sea E⊂Rnun subespacio vectorial. Se tiene que (K∩E)◦E=PE(K◦), donde (K∩E)◦Edenota el polar en el subespacio vectorial Een lugar de en todo Rn, es decir, (K∩E)◦E={y∈E:⟨x, y⟩ ≤ 1para todo x∈K∩E}. Demostración. La inclusión de izquierda a derecha, por la Proposición 1.18, es equivalente a probar que (PE(K◦))◦⊆K∩E. Sea pues x∈ (PE(K◦))◦, entonces ⟨x, y⟩ ≤ 1para todo y∈PE(K◦), es decir, ⟨x, PE(z)⟩ ≤ 1para todo z∈K◦. Dado que x∈Ey usando la Proposición 1.14, tenemos que 1≥ ⟨x, PE(z)⟩=⟨x, z⟩. Se sigue entonces que x∈(K◦)◦=Ky que x∈K∩E. Veamos ahora la otra inclusión. Sea x∈PE(K◦), entonces existe y∈ K◦tal que x=PE(y). Dicha ycumple que ⟨y, z⟩ ≤ 1para todo z∈K. Sea z∈K∩E, tenemos que probar que ⟨x, z⟩ ≤ 1. De nuevo, dado que z∈Ey usando la Proposición 1.14, tenemos que ⟨x, y⟩=⟨PE(y), z⟩=⟨y, z⟩ ≤ 1. Proposición 1.21. (Espacio dual). Sea X= (Rn,∥·∥)un espacio normado, la bola unidad del espacio dual X∗es el polar de la bola unitaria de X. Todas estas proposiciones que establecen una relación entre espacios y sus bolas unitarias (1.7, 1.15 y 1.21) se pueden resumir en el cuadro 1.1: Espacio Bola unidad espacio normado Xde dimensión n cuerpo convexo simétrico Ken Rn subespacio E⊂Xsección K∩E espacio dual X∗polar K◦ Cuadro 1.1: Correspondencias 1.2. DISTANCIA DE BANACHMAZUR 17 1.2. Distancia de Banach- Mazur La distancia de Banach-Mazur es una medida de cuánto se necesita deformar un espacio normado para que se parezca a otro dado. Es una forma de medir la similitud entre dos espacios normados. Daremos dos definiciones que son equivalentes siempre que estemos en espacios de dimensión finita, una en el contexto del Análisis Funcional y la otra en Geometría Convexa. Definición 1.22. Sean XeYespacios normados. Una aplicación lineal T:X→Yes acotada si existe algún M > 0 tal que ∥Tx∥ ≤ M∥x∥para todo x∈X. Si Tes una aplicación lineal, el ínfimo de las Men la definición anterior es la denominada norma de T: ∥T∥= sup x∈X\{0} ∥Tx∥ ∥x∥= sup ∥x∥=1 ∥Tx∥= sup ∥x∥≤1∥Tx∥. Una aplicación lineal T:X→Yse denomina un isomorfismo si es biyectiva y tanto Tcomo T−1son acotadas. XeYse dicen isomorfos si existe un isomorfismo entre ellos. Veamos ahora las dos definiciones mencionadas. Definición 1.23. (Analítica). Sean XeYdos espacios normados isomorfos. La distancia de Banach-Mazur entre XeYse define como d(X, Y ):= ´ınf{∥T∥∥T−1∥ | T:X→Yes un isomorfismo}. (Geométrica). Sean KyLcuerpos convexos simétricos en Rn. La distancia de Banach-Mazur entre KyLes d(K, L):= ´ınf{ab > 0|1 bL⊆TK ⊆aL para una aplic. lineal Ten Rn}. 18 CAPÍTULO 1. DEFINICIONES Y RESULTADOS INICIALES En lo que sigue del trabajo, d(·,·)denotará la distancia de Banach- Mazur analítica o geométrica, según el contexto. Ambas definiciones, analítica y geométrica, de la distancia de Banach- Mazur para el caso de espacios de dimensión finita están conectadas a través de la correspondencia entre espacios normados y cuerpos convexos simétricos descritos en la sección anterior. De esta manera, la distancia de Banach-Mazur (analítica) entre los espacios XeYes la misma que la distancia de Banach-Mazur (geométrica) entre sus bolas unitarias BX yBY. Veámoslo con más detalle. Si T:X→Yes un isomorfismo, entonces podemos usar las normas de los operadores TyT−1vistas en la definición 1.22 para relacionar las inclusiones de los cuerpos convexos KyL. Vamos a usar la norma dada por el funcional de Minkowski, definida en la proposición 1.7. Dado que ∥Tx∥L≤ ∥T∥∥x∥K, si x∈K, entonces ∥x∥K≤1, y se tiene ∥Tx∥L≤ ∥T∥. Esto implica que T(K)⊆ ∥T∥L. De manera similar, ∥T−1y∥K≤ ∥T−1∥∥y∥L, y, si y∈L, entonces ∥y∥L≤1y se tiene ∥T−1y∥K≤ ∥T−1∥. Esto implica que T−1L⊆ ∥T−1∥K y, aplicando Ta ambos lados y dividiendo por ∥T−1∥, se llega a L ∥T−1∥⊆ T(K). Es decir, los a, b que aparecen en la definición geométrica son, de hecho, las normas de TyT−1respectivamente y las definiciones son, por tanto, completamente equivalentes. Proposición 1.24. (Propiedades de la distancia analítica Banach- Mazur). Sean X,YyZespacios normados de dimensión n. Entonces: 1. d(X, Y )≥1. Además, d(X, Y )=1si y solo si XeYson isométricos; 2. d(X, Y ) = d(Y, X); 3. d(X, Y )≤d(X, Z)d(Z, Y ); 4. d(X, Y ) = d(X∗, Y ∗). Teniendo en cuenta la equivalencia de definiciones, se pueden dar las mismas propiedades para la versión geométrica, teniendo en cuenta la Proposición 1.21: Proposición 1.25. (Propiedades de la distancia geométrica Banach- Mazur). Sean K,LyMcuerpos convexos simétricos en Rn. Entonces: 1.3. MEDIDAS 19 1. d(K, L)≥1. Además, d(K, L)=1si y solo si KyLson isométricos; 2. d(K, L) = d(L, K); 3. d(K, L)≤d(K, M)d(M, L); 4. d(K, L) = d(K◦, L◦). Ejemplos 1.26. Se pueden calcular: d(Bn p, Bn q) = n|1 p−1 q| d(Bn 2, Bn 1) = √n d(Bn 2,E) = 1 para cualquier elipsoide E ⊂ Rn. Una propiedad importante que no probaremos aquí es que dado un cuerpo convexo simétrico K,d(K, Bn 2)≤√n. Es decir, el cubo n-dimensional y la bola de ℓn 1son los cuerpos convexos simétricos más diferentes a la bola euclídea ndimensional. Vemos algunos ejemplos gráficamente con n= 2 en la Figura 1.6. 1 √2B2 ∞⊂B2 2⊂B2 ∞B2 1⊂B2 2⊂√2B2 1 Figura 1.6 1.3. Medidas Definición 1.27. Sea Xun conjunto no vacío. Llamamos σ-álgebra sobre Xa una familia A ⊆ P(X)no vacía de subconjuntos de Xque verifique: 26 CAPÍTULO 1. DEFINICIONES Y RESULTADOS INICIALES En particular, para t≥1, la cola está acotada por la densidad: P(g≥t)≤1 √2πe−t2/2. Demostración. Se tiene por definición que P(g≥t) = 1 √2πZ∞ t e−x2/2dx. Hacemos el cambio de variable x=t+yy usamos que e−y2/2≤1: P(g≥t) = 1 √2πZ∞ 0 e−t2/2e−tye−y2/2dy ≤e−t2/2 √2πZ∞ 0 e−tydy. Resolviendo la última integral Z∞ 0 e−tydy =e−ty −t ∞ 0 =1 t obtenemos la cota superior deseada. La cota inferior se sigue de la identidad Z∞ t (1 −3x−4)e−x2/2dx =1 t−1 t3e−t2/2, lo que completa la prueba. Proposición 1.50. (Distribución normal truncada). Sea g∼ N(0,1), entonces para todo t≥1se tiene que Eg21{g≥t}=t·1 √2πe−t2/2+P(g≥t)≤t+1 t1 √2πe−t2/2 Demostración. Usamos la función de densidad de N(0,1) e integramos por partes: Eg21{g≥t}=1 √2πZ∞ t x2e−x2/2dx =−1 √2πxe−x2/2 ∞ t +1 √2πZ∞ t e−x2/2dx Y concluimos que Eg21{g≥t}=t·1 √2πe−t2/2+P(g≥t) La desigualdad final se sigue de la proposición 1.49. 1.4. MEDIDAS DE PROBABILIDAD 27 Definición 1.51. Sea (Ω,F,P)un espacio de probabilidad. Sean X1, X2, . . . , Xnvariables aleatorias definidas en este espacio. Entonces, se dicen independientes si para todos los conjuntos medibles de Lebesgue A1, A2, . . . , An⊆R, se cumple que: P(X1∈A1, X2∈A2, . . . , Xn∈An) = P(X1∈A1)·. . . ·P(Xn∈An). Esto es equivalente a decir que el valor de una de ellas no proporciona información alguna sobre el valor de las demás. Sean X1, X2, . . . , Xnvariables aleatorias independientes. Se dicen idénticamente distribuidas o i.i.d. si tienen la misma distribución, es decir, si para todos i, j y para todo A⊆Rmedible Lebesgue se cumple que P(Xi∈A) = P(Xj∈A) Proposición 1.52. Sea X1, X2, . . . , Xnun conjunto de variables aleatorias independientes. Entonces, se cumple que E"n Y i=1 Xi#= n Y i=1 E[Xi] Veamos una proposición para ejemplarizar la independencia. Lema 1.53. (Acotación del coseno hiperbólico). Se tiene cosh(x)≤exp(x2/2) para todo x∈R. Demostración. Comparemos las series de Taylor de ambas expresiones: cosh(x) = ∞ X n=0 x2n (2n)!;ex2/2= ∞ X n=0 x2n 2nn!. Comparando elemento a elemento: (2n)! n! 2n=1·2·3·. . . ·2n (1 ·2·3·. . . ·n)·2n= 2·3· 4·5· 6·. . . ·  2n  2· 4· 6·. . . ·  2n>1. 28 CAPÍTULO 1. DEFINICIONES Y RESULTADOS INICIALES Teorema 1.54. (Desigualdad de Hoeffding). Sean X1, ..., XNv.a. independientes con distribución simétrica de Bernouilli y a= (a1, ..., aN)∈RN. Entonces, para todo t≥0se tiene P N X i=1 aiXi≥t!≤exp −t2 2∥a∥2 2. Demostración. Podemos suponer sin pérdida de generalidad que ∥a∥2= 1.Multiplicamos por una constante λ > 0arbitraria y aplicamos exponencial: P N X i=1 aiXi≥t!=P exp λ N X i=1 aiXi!≥exp(λt)!Markov ≤ ≤e−λtE"exp λ N X i=1 aiXi!#.(1.4) E"exp λ N X i=1 aiXi!#Prop. 1.52 = N Y i=1 E[exp(λaiXi)] .(1.5) Fijemos i. Puesto que Xitoma valores −1y1con probabilidades 1/2cada uno, tenemos Eexp(λaiXi) = exp(λai) + exp(−λai) 2= cosh(λai).(1.6) Usando en (1.6) el Lema 1.53 se prueba que Eexp(λaiXi)≤exp(λ2a2 i/2) Encadenando (1.4) y (1.5), tenemos P N X i=1 aiXi≥t!≤e−λt N Y i=1 exp(λ2a2 i/2) = exp −λt +λ2 2 N X i=1 a2 i! = exp −λt +λ2 2. 1.4. MEDIDAS DE PROBABILIDAD 29 Si tomamos λ=ttenemos P N X i=1 aiXi≥t!≤exp(−t2/2), lo que completa la prueba. Definición 1.55. Una matriz aleatoria es una matriz cuyos elementos son variables aleatorias definidas en un espacio de probabilidad (Ω,A,P). Formalmente, una matriz aleatoria Ade dimensión m×nse puede escribir como: A=     X11 X12 ··· X1n X21 X22 ··· X2n . . .. . ..... . . Xm1Xm2··· Xmn      donde cada Xij, para i= 1, . . . , m yj= 1, . . . , n, es una variable aleatoria. Definición 1.56. Una matriz aleatoria gaussiana es una matriz aleatoria cuyos elementos son variables aleatorias independientes e idénticamente distribuidas según una distribución normal N(µ, σ)para ciertos µ∈Ryσ > 0. Capítulo 2 El Teorema de Dvoretzky Como ya comentamos en la introducción del trabajo, el Teorema de Dvoretzky es un resultado fundamental en Análisis y en Geometría Convexa. En términos sencillos, establece que a cualquier cuerpo convexo simétrico se le puede hacer una sección de dimensión grande tal que la sección es ”parecida” a la bola euclídea. Por ejemplo, podemos pensar en secciones bidimensionales de un cubo tridimensional (Figura 2.1). Como mencionamos en la sección relativa a la distancia Banach- Mazur, los cuadrados y rectángulos están lejos de ser un un disco, pero el hexágono que se obtiene al intersecar un plano de una manera determinada se aproxima más. Figura 2.1: Sección del cubo en R3 31 32 CAPÍTULO 2. ELTEOREMA DE DVORETZKY 2.1. Las versiones del Teorema de Dvoretzky El Teorema fue probado por primera vez en 1961 por el matemático de nacionalidad israelí que da nombre al Teorema, Aryeh Dvoretzky dando solución a una conjetura del francés Alexander Grothendieck. Teorema 2.1. (Versión original del Teorema de Dvoretzky). Sea (X, ∥·∥)un espacio normado de dimensión n. Para cualquier ε > 0, existe un subespacio Ede Xde dimensión m=m(n, ε)→ ∞ cuando n→ ∞ tal que d(E, ℓm 2)≤ 1 + ε. Este se puede enunciar equivalentemente de forma geométrica. Teorema 2.2. (Versión geométrica del Teorema de Dvoretzky). Sea Kun cuerpo convexo simétrico en Rn. Para cualquier ε > 0, existe una sección K∩Ede K mediante un subespacio Ede Rnde dimensión m=m(n, ε)→ ∞ cuando n→ ∞tal que (1 −ε)Bm 2⊆K∩E⊆(1 + ε)Bm 2.(2.1) Teniendo en cuenta la definición geométrica de la distancia de Banach- Mazur (1.23), la cadena de contenciones (2.1) implica la cota d(E, ℓm 2)≤ 1 + εde la versión original. Por otra parte, (2.1) se puede expresar, gracias a la Proposición 1.15, de la siguiente manera: (1 −ε)(Bn 2∩E)⊆K∩E⊆(1 + ε)(Bn 2∩E). Ahora, tomando polares y usando la Proposición 1.20 y las propiedades del polar (Proposición 1.18) podemos enunciar la versión geométrica de manera análoga usando proyecciones sobre un subespacio de menor dimensión en lugar de haciendo secciones: Teorema 2.3. (Versión geométricaproyecciones). Sea Kun cuerpo convexo simétrico en Rn. Para cualquier ε > 0, existe un subespacio E⊆Rnde dimensión m=m(n, ε)→ ∞cuando n→ ∞tal que (1 −ε)Bm 2⊆PE(K)⊆(1 + ε)Bm 2.(2.2) La primera demostración de Dvoretzky utilizó técnicas de Geometría Convexa y Análisis Funcional. Este resultado fue notable porque reveló 2.1. LAS VERSIONES DEL TEOREMA DE DVORETZKY 33 una propiedad oculta de los espacios de alta dimensión: aunque los cuerpos convexos pueden ser complicados, contienen secciones grandes que son casi ”esféricas” o euclídeas, y éstas tienen propiedades útiles en algunos contextos. Es importante notar que la mención a la dimensión del subespacio es clave para la relevancia del Teorema, pues, obviamente, a cualquier cuerpo convexo simétrico de cualquier dimensión se le puede hallar una bola euclídea de dimensión 1 (un intervalo) que lo atraviese. Dicha sección no sería parecida a un subespacio euclídeo, sería exactamente euclídeo, pero no aporta ninguna información relevante. Este primer resultado probó que conforme hacemos crecer la dimensión del cuerpo convexo simétrico, la de la sección que podemos hallar también crece, pero no daba ninguna estimación de en qué magnitud lo hacía. Por todo esto, el Teorema fue rápidamente reconocido como un descubrimiento extraordinario en el Análisis Funcional y la Geometría Convexa y abrió el camino para que otros matemáticos buscaran pruebas alternativas y dieran cotas para la dimensión del subespacio tomado. Así, en 1971, el también israelí Vitali Milman presentó una de las reformulaciones del Teorema más importantes hasta la fecha. Este utilizó para la demostración el fenómeno de concentración de medida, un fenómeno antiintuitivo en el que, en espacios de alta dimensión, la mayor parte de la medida (o masa) se concentra alrededor de una región relativamente pequeña del espacio. Teorema 2.4. (Teorema de Dvoretzky- Milman). Para todo espacio normado de dimensión n,X= (Rn,∥·∥), y para cada ε∈(0,1), existe un entero m≥ cε2log ny un subespacio Fde dimensión mde Xque satisface d(F, ℓm 2)≤1+ε, donde c es una constante que sólo depende de ε. Este enunciado es significativo porque introduce explícitamente la relación logarítmica entre la dimensión ndel espacio normado y la dimensión del subespacio Fque exhibe propiedades euclidianas aproximadas. La constante mdepende inversamente del error ε, significando que una menor tolerancia al error permite obtener subespacios de menor dimensión pero que se aproximan mucho a ℓm 2. 34 CAPÍTULO 2. ELTEOREMA DE DVORETZKY 2.2. Versión gaussiana Antes de introducir el resultado central del trabajo debemos definir algunos conceptos nuevos. Definición 2.5. El diámetro de un subconjunto T⊂Rnse define como diam(T):= sup{∥s−t∥2:s, t ∈T}. El radio de un subconjunto T⊂Rnse define como rad(T):= sup x∈T∥x∥2. La anchura gaussiana de un subconjunto T⊂Rnse define como w(T):=Esup x∈T⟨g, x⟩, donde ges un vector n-dimensional cuyas componentes son variables aleatorias normales estándar, N(0,1), iid. La complejidad gaussiana de un subconjunto T⊂Rnse define como γ(T):=Esup x∈T|⟨g, x⟩|, donde ges un vector n-dimensional cuyas componentes son variables aleatorias normales estándar, N(0,1), iid. Para un conjunto acotado T⊂Rn, la dimensión estable de Tse define como d(T):=w(T)2 diam(T)2. Tanto la anchura como la complejidad gaussianas son formas de medir cúanto se extiende en promedio el conjunto Tcuando se toma una direccion aleatoria. 2.2. VERSIÓN GAUSSIANA 35 Observación 2.6. Si T⊂Rncontiene al origen, rad(T)≤diam(T). Obviamente w(T)≤γ(T), y se tiene la igualdad si Tes simétrico respecto al origen, es decir, si T=−T. Ahora ya tenemos todos los elementos necesarios para enunciar la versión gaussiana del Teorema de Dvoretzky que probaremos en el siguiente capítulo. Teorema 2.7. (Versión gaussiana del teorema de Dvoretzky). Sea Auna matriz aleatoria gaussiana m×ncon entradas i.i.d. N(0,1),T⊂Rnun conjunto acotado, y sean ε∈(0,1) yc > 0tales que m≤cε2d(T),(2.3) donde d(T)es la dimensión estable de T. Entonces, con probabilidad al menos 0,99, tenemos (1 −ε)rBm 2⊆Conv(AT)⊆(1 + ε)rBm 2,(2.4) donde r:=w(T), la anchura gaussiana de T. En lo que sigue, vamos a abusar de notación, entendemos Acomo la propia matriz o como la aplicación lineal dada por ella, según el contexto. Notemos en primer lugar que el rango de Adebe ser máximo, m, pues en caso contrario la imagen por Aestaría contenida en un subespacio de dimensión menor que m, por lo que no podría contener una bola de dimensión m. Así, cuando Aes una matriz m×ncon rango my al ser Tun conjunto convexo acotado de Rn, por resultados de álgebra lineal, AT es un subespacio de Rmy, en concreto, la proyección de Tsobre el subespacio F, donde F= ker(A)⊥. La cadena de contenciones (3.4) es, por tanto, una manera distinta de expresar (2.2). La hipótesis (3.3), sobre la dimensión de la matriz aleatoria, quiere decir que, en particular, si mes el mayor entero tal que se cumple dicha desigualdad (esto es, ⌊cε2d(T)⌋) entonces se cumple (3.4). Para obtener una cota como la del mencionado enunciado de Milman (Teorema 2.4) habría que probar que la dimensión estable de cualquier conjunto convexo acotado es mayor o igual que log(m). 42 CAPÍTULO 3. PRUEBA GAUSSIANA DEL TEOREMA DE DVORETZKY Usando la desigualdad triangular y la definición de r+y de r−, obtenemos: r−≤sup x∈T⟨Ax, y⟩ ≤ r+ para todo y∈Sm−1. Por homogeneidad, esto es equivalente a r−∥y∥2≤sup x∈T⟨Ax, y⟩ ≤ r+∥y∥2 para todo y∈Rm. Teniendo en cuenta que sup x∈T⟨Ax, y⟩= sup x∈AT⟨x, y⟩ y aplicando el lema 3.2 para V=AT, se completa la prueba. 3.2. Teorema de Dvoretzky Enunciemos de nuevo la versión gaussiana del Teorema de Dvoretzky y veamos que la prueba se sigue de los resultados que acabamos de ver. Teorema 3.5. (Versión gaussiana del teorema de Dvoretzky). Sea Auna matriz aleatoria gaussiana m×ncon entradas i.i.d. N(0,1),T⊂Rnun conjunto acotado, y sean ε∈(0,1) yc > 0tales que m≤cε2d(T),(3.3) donde d(T)es la dimensión estable de T. Entonces, con probabilidad al menos 0,99, tenemos (1 −ε)rBm 2⊆Conv(AT)⊆(1 + ε)rBm 2,(3.4) donde r:=w(T), la anchura gaussiana de T. Demostración. Trasladando Tsi es necesario, podemos asumir que Tcontiene el origen. Aplicando el Teorema 3.4, sólo tenemos que verificar que r−≥(1 −ε)w(T)yr+≤(1 + ε)w(T), lo cual por definición se tendría si C√mrad(T)≤εw(T).(3.5) 3.2. TEOREMA DE DVORETZKY 43 Para verificar esta desigualdad, recordemos que por hipótesis y por definición de dimensión estable tenemos m≤cε2d(T)≤ε2w(T)2 diam(T)2 siempre que la constante c > 0se elija suficientemente pequeña. Ahora, dado que Tcontiene el origen, rad(T)≤diam(T). Esto implica (3.5) y completa la prueba. Bibliografía [1] K. Ball. An elementary introduction to modern Convex Geometry, volume 31 of Math. Sci. Res. Inst. Publ. Cambridge University Press, Cambridge, 1997. [2] C. Clason. Introduction to Functional Analysis. Springer Nature, 2020. [3] L. Tzafriri J. Lindenstrauss. Classical Banach Spaces I and II. Number v. 1 in Classical Banach Spaces I and II. Springer, 1996. [4] V. Milman. Dvoretzky’s theorem — thirty years later. Geometric & Functional Analysis GAFA, 2(4), 1992. [5] V. D. Milman. A New Proof of the Theorem of A. Dvoretzky on Sections of Convex Bodies, volume 5. 1971. [6] J. P. Penot. Elements of Functional Analysis. 12 2016. [7] V. D. Milman S. Artstein-Avidan, A. Giannopoulos. Asymptotic Geometric Analysis, Part I, volume 202. American Mathematical Soc., 2015. [8] V. D. Milman S. Artstein-Avidan, A. Giannopoulos. Asymptotic Geometric Analysis, Part II, volume 261. American Mathematical Society, 2021. [9] R. Schneider. Convex bodies: the Brunn–Minkowski Theory, volume 151. Cambridge University Press, 2013. [10] N. Tomczak-Jaegermann. The banach-mazur distance between symmetric spaces. Israel Journal of Mathematics, 46(1), 1983. 45 46 APÉNDICE . BIBLIOGRAFÍA [11] G. Schechtman V. D. Milman. Asymptotic Theory of Finite Dimensional Normed Spaces. Springer, 2014. [12] M. A. S. Ruas V. I. Bogachev. Measure Theory, volume 1. Springer, 2007. [13] R. Vershynin. Lectures in Geometric Functional Analysis, volume 3. 2011. [14] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.