24 votos

¿Teoremas verdaderos "con probabilidad 1"?

Esta pregunta se inspira en esta pregunta cerrada por una sugerencia en meta.

Algunas afirmaciones que se consideran ciertas son difíciles de probar con las herramientas actuales. Sin embargo, hay algunos argumentos intuitivos que las apoyan, algunos de ellos precisos y otros imprecisos.

Un ejemplo de argumento preciso son los resultados del oráculo aleatorio en la complejidad computacional. Un resultado típico afirma que bajo un oráculo aleatorio, las clases P, NP, coNP son todas diferentes con probabilidad 1 . Se cree que los métodos utilizados para demostrar esto no son lo suficientemente fuertes como para demostrar realmente las respectivas conjeturas, ya que existen oráculos bajo los cuales (por ejemplo) P=NP.

Los ejemplos de argumentos imprecisos abundan en la teoría de los números. Se puede argumentar que "probablemente" sólo hay un número finito de primos de Fermat, y se puede llegar a una estimación heurística de la densidad de los primos gemelos.

Muchos algoritmos de factorización se analizan sólo de forma heurística. Sin embargo, en el caso del tamiz cuadrático, también hay un argumento bastante más complicado que muestra que una variante del tamiz cuadrático realmente funciona como se anuncia.

Ejemplos de sabor ligeramente diferente son la gran cantidad de resultados demostrados bajo la Hipótesis de Riemann y sus parientes. El célebre algoritmo de comprobación de la primalidad AKS puede verse como una versión mejorada de algoritmos anteriores cuyo análisis es condicional de RH; AKS se comporta de forma demostrable como se anuncia.

¿Conoce algún resultado similar? Me interesan sobre todo los resultados de los dos tipos siguientes:

  • Resultados que afirman que, en algún sentido preciso, alguna afirmación es verdadera "para la mayoría de los universos".
  • Argumentos no rigurosos que sugieren la validez de un enunciado y que (posiblemente) conducen a pruebas rigurosas.

P.D. Por favor, siéntase libre de reetiquetar.

20voto

user8269 Puntos 46

A veces se oye decir "La hipótesis de Riemann es cierta con probabilidad 1". Lo que se quiere decir es que la Hipótesis de Riemann es verdadera si una determinada afirmación $S$ sobre la función de Möbius $\mu(n)$ es cierto; $\mu(n)$ es un miembro de una familia muy natural de funciones, una familia sobre la que existe una medida de probabilidad natural; con probabilidad 1, una función elegida de esta familia satisface $S$ .

7voto

Anthony Cramp Puntos 126

Dos ejemplos, de tipos quizás opuestos:

  • casi todos los números reales son de base 10 normal, por lo tanto (lo más probable) $\pi$ es normal en base 10

  • Casi todos los números reales son trascendentales, por lo que existe un número trascendental. (Demostración mucho más fácil que exponer con pruebas un número trascendental individual).

6voto

rck Puntos 121

Un desarrollo algo interesante en las ecuaciones diferenciales parciales es el estudio de la wellposedness del problema de valor inicial para al azar datos iniciales. Un ejemplo es este reciente trabajo de Burq y Tzvetkov . Permítanme describir breve y vagamente lo que mostraron.

La buena composición de los problemas de valores iniciales

El enunciado más aproximado de la cuestión de la buena composición de los problemas de valores iniciales en ecuaciones diferenciales parciales es preguntar "si prescribimos la valor inicial en el momento $t = 0$ ¿existe una solución única para $t > 0$ ". Sin embargo, para precisar matemáticamente, el primer problema es especificar en qué sentido y en qué conjuntos permites que la solución exista y exiges que sea única (y también en qué sentido y en qué conjuntos prescribes los datos iniciales). Bueno, como las funciones definidas en cualquier colector forman un espacio vectorial, tenemos que nuestro conjunto tendrá al menos una estructura de espacio vectorial. Además, se sabe que un requisito físicamente natural para la wellposedness es una propiedad de aproximación: que dos datos iniciales que no difieran demasiado deberían generar soluciones que no difieran demasiado. Para cuantificar el "no diferir demasiado" nos lleva a requerir que nuestros conjuntos tengan topología (así obtenemos una noción de continuidad). De hecho, ésta es la noción habitual de "wellposedness":

Se dice que un problema de valor inicial está bien planteado si existe algún espacio vectorial topológico (de funciones definidas en $t=0$ ) $X$ de datos iniciales, y algún espacio vectorial topológico (de funciones definidas en $T > t\geq 0$ ) $Y$ de soluciones tal que existe una función continua $f:X\to Y$ la asignación de los datos iniciales a las soluciones.

El trabajo principal es entonces encontrar un par adecuado de $(X,Y)$ tal que $f$ puede existir como una función (por lo que el dominio es el conjunto de $X$ y para cada elemento de $X$ sólo hay una imagen en $Y$ ) y es continua.

Problemas de regularidad

Ahora, está bastante claro que si haces $X$ más pequeño, entonces es "más fácil" encontrar el mapeo $f$ : hay "menos" elementos (menos comportamientos patológicos) de los que preocuparse, por lo que es más probable encontrar que el mapa de soluciones existe para todos los datos iniciales en $X$ . También está bastante claro que si se hace la topología Más fino la continuidad se hace más fácil de probar. Si la topología del espacio vectorial viene dada por una familia de seminormas, al añadir más seminormas el espacio se hace más "pequeño" y se genera una topología más fina.

En realidad, esto es así: dejar que $X$ estar en el $L^2$ -Escala de Sobolev de los espacios de funciones $H^s$ , donde $s$ mide el número de derivados que controla, cuanto mayor sea el $s$ más probable es que se pueda demostrar una declaración de bondad.

Burq y Tzvetkov estudiaron una ecuación particular -la ecuación de onda semilineal cúbica, en adelante 3SLW- en su artículo. Se sabe por resultados anteriores que, de hecho, hay un límite para la buena composición. En la escala de Sobolev, la 3SLW está bien compuesta con el tiempo de existencia $T$ posiblemente sólo finito para $\frac12<s<\frac34$ (algunos de los signos de desigualdad pueden ser en realidad no estrictos, pero no recuerdo en qué sentido van las inclusiones con seguridad), y con $T$ infinito cuando $s > \frac34$ . Para $0 < s < \frac12$ Sin embargo, se sabe que la wellposedness falla porque la ruptura de la continuidad (la topología de $X$ se vuelve demasiado gruesa).

Probabilidad de la buena composición

Sin embargo, se razona que la ruptura de la continuidad para 3SLW es una situación muy especial, y que la "mayoría" de los datos aproximados seguirán dando un buen comportamiento. En este sentido, la fijación de $s$ sea cualquier número entre 0 y 1, Burq y Tzvetkov construyeron una medida de probabilidad $\mu$ (véase más abajo) en $H^s$ tal que existe un conjunto de medidas completo $\Sigma\subset H^s$ tal que el mapa solución está bien definido (existencia y unicidad) en $\Sigma$ y $\Sigma$ es invariante bajo el flujo de solución (lo que implica que el tiempo de existencia es infinito). Además, con respecto a esta medida $\mu$ mostraron una "continuidad probabilística" del mapa de solución: es decir, definiendo el conjunto

$$ G(\epsilon,\delta):= \left\{ (V,U)\in X\times X \mid \|f(V)-f(U)\|_Y \geq \epsilon, \|V-U\|_X\leq \delta\right\} $$

de pares de puntos en los que la solución difiere en una gran cantidad al menos $\epsilon$ mientras que los datos difieren en una pequeña cantidad como máximo $\delta$ Burq y Tzvetkov pudieron demostrar que para cualquier $\epsilon$ ,

$$ \lim_{\delta\to 0} \left|G(\epsilon,\delta)\right|_{\mu\times\mu} = 0$$

en la medida del producto.

La medida

Usted se preguntará, bueno, ¿y si simplemente se define la medida a apoyar precisamente en $H^1 \subset H^s$ ? El punto principal de la construcción es que dado cualquier $H^s$ se puede construir la medida $\mu$ "aleatorizando" la función dada, de tal manera que la regularidad no aumenta. (Más concretamente, demostraron que si la función dada está en $H^s$ pero no en $H^r$ para $r > s$ entonces la medida $\mu$ que construyeron tendrán la propiedad de que $H^r$ tiene $\mu$ -medida cero. Así que la medida $\mu$ es esencialmente un objeto que vive en el espacio de baja regularidad).

5voto

John Fouhy Puntos 759

A continuación, la respuesta de Theo Buehler (originalmente un comentario).

Existen algunos resultados de este tipo en la teoría geométrica de grupos que se remontan al monumental trabajo de Gromov sobre los grupos hiperbólicos. Las afirmaciones son típicamente de la forma: Si el grupo tiene una presentación de tipo ... entonces con una probabilidad abrumadora es un grupo con tales y tales propiedades .

Eslogan: Todo teorema sobre todos los grupos es trivial o falso, pero puede cumplirse con probabilidad 1 .

Una muy buena introducción a estas ideas es el libro de Yann Olivier invitación a grupos aleatorios .

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