24 votos

Teorema de las "seis desviaciones estándar" de Spencer: ¿mejores constantes?

Esta pregunta es acerca de Joel Spencer famoso "seis desviaciones estándar" teorema. El teorema dice que cuando $$ L_i(x_1,\dots,x_n) = a_{i1} x_1 + \dots + a_{en} x_n, \quad 1 \leq i \leq n, $$ se $n$ lineal de las formas en $n$ variables con todas las $|a_{ij}| \leq 1$, entonces no existen números de $\varepsilon_1,\dots,\varepsilon_n \in \{-1,+1\}$ tal que $$ |L_i(\varepsilon_1,\dots,\varepsilon_n)| \leq K \sqrt{n} $$ para todos los $i$.

Se basa en el Teorema 1 en:

Spencer, Joel. Seis desviaciones estándar es suficiente. Trans. Amer. De matemáticas. Soc. 289 (1985), no. 2, 679-706. Texto completo en formato PDF (acceso abierto)

Como se señaló al final de la nota, el constante $K$ que Spencer obtenidos en realidad es $K=5.32$.

Pregunta: ¿alguien sabe de una prueba del Teorema que da un menor valor de la constante?

19voto

Blixtor Puntos 287

Una vez hecho el resultado original, es emocionante ver trabajar en la constante. Mi 5.32 ciertamente no estaba destinado a ser el mejor posible. Para los límites inferiores, el uso de matrices de Hadamard (con coeficientes +1, -1 en comparación con el sistema establecido con coeficientes 0,1) da un límite inferior de K = 1. - js

15voto

Arnaud Mortier Puntos 797

En su tesis doctoral, A. Belshaw encuentra$K=5.199$, pero también afirma que Kai Uwe Schmidt pudo obtener$K$ tan bajo como$3.65$. La idea del proceso se describe en la Sección 5.6, aunque los cálculos reales se basan en la "comunicación personal".

Ver summit.sfu.ca/system/files/iritems1/13657/etd8131_ABelshaw.pdf

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X