¿Cómo traducir una intuición matemática en una demostración rigurosa?

Question

He visto muchas preguntas sobre cómo desarrollar la intuición matemática, pero a menudo tengo el problema contrario.

Varias veces me he encontrado con una situación en la que quiero resolver un problema matemático, y juego con él hasta que mi intuición llega al punto de tener una buena idea de cómo podría estructurarse la prueba completa. Pero luego, cuando llega el momento de escribir la prueba, tengo problemas para traducir esta intuición en una prueba rigurosa. Quiero poner el siguiente ejemplo, de este PDF de los problemas de formación de Putnam.

1.13. Demuestre que para cada $n\ge 2$ La expansión de $(1+x+x^2)^n$ contiene al menos un coeficiente par.

Cuando pensé por primera vez en este problema, quise ver los polinomios $\pmod{2}$ para que "coeficiente par" se simplifique a "coeficiente cero".

Entonces, al hacer algunos cálculos, noto un patrón.

\begin {align*} (1+x+x^2)^2&=(1+x+x^2)+x(1+x+x^2)+x^2(1+x+x^2) \\ &=1+x+x^2 \\ &+x+x^2+x^3 \\ &+x^2+x^3+x^4 \\ &=1+x^2+x^4 \end {align*}

Observo que al multiplicar un polinomio por $(1+x+x^2)$ es como sumar ese polinomio consigo mismo tres veces, cada una desplazada. El $x$ lo desplaza un lugar y el $x^2$ lo desplaza dos puestos.

Siguiendo este patrón, podemos obtener los coeficientes de $(1+x+x^2)^3$ de la siguiente manera:

\begin {array}{ccccc} 1&0&1&0&1&& \\ &1&0&1&0&1& \\ &&1&0&1&0&1 \\ \hline 1&1&0&1&0&1&1 \end {array}

Así que $(1+x+x^2)^3\equiv 1+x+x^3+x^5+x^6 \pmod{2}$

Hagamos un triángulo con algunos resultados más:

\begin {array}{cccccccc} 0:&&&&&&1&&&&& \\ 1:&&&&&1&1&1&&&& \\ 2:&&&&1&0&1&0&1&&& \\ 3:&&&1&1&0&1&0&1&1&& \\ 4:&&1&0&0&0&1&0&0&0&1& \\ 5:&1&1&1&0&1&1&1&0&1&1&1 \\ \end {array}

Vemos que la estructura de nuestro problema es esencialmente la misma que la de un autómata celular elemental (concretamente, la regla 150). Volveré sobre esto más adelante.

Observo otro patrón peculiar con el $1$ st, $2$ nd, y $4$ filas: Sólo hay $1$ s en los extremos y en el centro. Quizás este patrón continúe para todas las potencias de $2$ . Y lo hace, lo cual no es difícil de demostrar con la inducción.

Reclamación: $\forall n\ge 0,\ (1+x+x^2)^{2^n}\equiv 1+x^{2^n}+x^{2^{n+1}}\pmod{2}$

Caso base: $(1+x+x^2)^{2^0}\equiv 1+x+x^2\equiv 1+x^{2^0}+x^{2^1}\pmod{2}$

Paso inductivo:

\begin {align*} (1+x+x^2)^{2^n}& \equiv ((1+x+x^2)^{2^{n-1}})^2 \\ & \equiv (1+x^{2^{n-1}}+x^{2^n})^2 \\ & \equiv 1+x^{2^n}+x^{2^{n+1}} \pmod {2} \end {align*}

Aquí es donde entra la intuición que me resulta difícil de expresar con rigor. En uno de los $2^n$ de las filas, mire el $0$ equidistante del más a la izquierda $1$ y el $1$ en el centro. Si el más a la derecha $1$ no estaba allí, entonces eso $0$ se quedaría un $0$ para siempre debido a la simetría: cualquier efecto de la izquierda se anula con un efecto de la derecha.

Sin embargo, el extremo derecho $1$ existe, por lo que eventualmente cambiará que $0$ . Pero como los efectos son locales en este autómata, requerirá más de $2^n$ más filas hasta la más a la derecha $1$ afecta a la $0$ que estamos viendo (hay más de $2^n$ espacios entre ellos). En otras palabras, hemos demostrado que el $0$ se mantendrá un $0$ para todas las filas hasta el $2^{n+1}$ fila. Aplicando esta lógica en cada fila de potencia de dos, demostramos que siempre hay un coeficiente cero de la fila $2$ en adelante.

¿Hay alguna forma más rigurosa de expresar estos dos últimos párrafos? Y en general, ¿qué consejos tiene para traducir la intuición a una prueba rigurosa?

Answer 1

Has demostrado que estas cadenas binarias son simétricas, así que basta con demostrar el resultado sólo para las "medias cadenas". Imagina que cortas tu triángulo por la mitad. Sea $x_n$ sea el $n^{th}$ cadena de bits, cuya longitud es $n+1$ .

Tenemos $x_0 = 1$ , $x_1 = 11$ , $x_2 = 101$ etc.

Ahora puede dirigirse al $j^{th}$ bit en el interior $x_n$ como $x_{n,j}$ .

Este sistema de direccionamiento facilitará hablar más concretamente de la acción del autómata.

Se puede establecer una definición de "localidad de acción" diciendo que hay alguna función $f(a, b, c)$ tal que $\forall n, j: x_{n,j} = f(x_{n-1, j-1}, x_{n-1,j}, x_{n-1,j+1})$ (con algunas condiciones adicionales molestas sobre la frontera). Esto significa que el $j^{th}$ de la cadena actual puede calcularse mediante los bits cercanos de la cadena anterior. Aquí $f$ representa la acción de esta regla 150 que mencionas.

Ahora usa $f$ de nuevo para mostrar $ x_{n,j} = f(f(x_{n-2, j-2}, x_{n-2,j-1}, x_{n-2, j}), f(x_{n-2, j-1}, x_{n-2,j}, x_{n-2, j+1}), f(x_{n-2, j}, x_{n-2,j+1}, x_{n-2, j+2}))$

Ahora puedes ver cuando repetimos este procedimiento $k$ veces terminaremos con una profundidad de árbol de sintaxis abstracta trinaria $k$ . Para evitar tener que hablar de la estructura exacta de la expresión en el $k^{th}$ podemos razonar sobre este proceso de sustitución de manera puramente formal como un proceso que opera sobre el conjunto (contablemente infinito) de símbolos $\{ \underline{f}, \underline{(}, \underline{)} \} \cup \{ \underline{x_{i,j}} \}_{(i,j) \in \mathbb{N}^2}$ (aquí las comas no forman parte del conjunto de símbolos, sólo están ahí para separar unos símbolos de otros). Se puede demostrar por inducción que para cualquier $k$ que $x_{n,j}$ se calcula mediante una expresión que utiliza los símbolos $\{ \underline{f}, \underline{(}, \underline{)} \} \cup \{\underline{ x_{n-k, j-k}},\underline{ x_{n-k, j-k+1}}, …,\underline{ x_{n-k, j+k-1}},\underline{ x_{n-k, j+k} }\}$ (el $2k+1$ bits en el $(n-k)^{th}$ cadena centrada en el $j^{th}$ bit) entremezclado con aplicaciones de funciones de $f$ .

Fijar $n$ y que $k_n$ sea la distancia a la potencia anterior de $2$ . (Así que si $n=13$ , $k_n=5$ desde la anterior potencia de $2$ es $8$ ). Y definir $j_n \equiv (n-k_n)/2$ . Es el índice del bit central del $(n-k_n)^{th}$ cadena de bits.

Has demostrado que esos bits en los índices $\{ (n-k_n, m) \}_{1 \le m \lt n }$ son todos cero ya que $n-k_n$ es una potencia de $2$ . Así que cualquier expresión bien formada utilizando únicamente los símbolos $\{ \underline {f}, \underline{(}, \underline{)}\} \cup \{ \underline{x_{n-k_n, j_n-k_n}}, \underline{x_{n-k_n, j_n-k_n+1}}, …,\underline{x_{n-k_n, j_n+k_n-1}}, \underline{x_{n-k_n, j_n+k_n}}\}$ se evaluará a cero por $f(0,0,0) = 0$ y, en particular, la expresión que representa $x_{n,j_n}$ (creado a partir del $k_n$ iteraciones del procedimiento de sustitución formal de símbolos) evalúa a $0$ .

Así que como $n$ incrementos, $x_{n,j_n}$ traza el camino de los bits centrales a los que se refería, todos los cuales son cero.

Reflexiones generales sobre la formalización: Hay ciertos dispositivos técnicos que son caballos de batalla del proceso de formalización. Dos de ellos los he utilizado en esta prueba:

• indexar el tiempo y el espacio, con un sistema de coordenadas numéricas
• codificación de un sistema de evolución temporal como aplicación de funciones

Un tercer dispositivo que he utilizado no es tan común, y proviene de la informática y la lógica:

• razonamiento sobre la computación mediante el razonamiento sobre las sustituciones de cadenas

Algo de lo que me he ido dando cuenta es que estos dispositivos no son obvios (al menos para mí). La humanidad tardó mucho tiempo en descubrir el sistema de coordenadas cartesianas y en utilizarlo para formalizar la intuición geométrica. Se tardó aún más en desarrollar la idea de que casi todos los objetos matemáticos podían codificarse como una intrincada torre de conjuntos (ZFC).

Supongo que para mí es una cuestión de construir una biblioteca de estos dispositivos y vincularlos a las intuiciones correctas mediante el uso repetido.

En ciertos ámbitos, como la programación informática, hay muy pocas herramientas para convertir la intuición en prueba. Se han creado un par de dispositivos muy buenos como

• invariantes del bucle
• La lógica de Hoare

pero los programas multihilo y los que asignan un montón siguen siendo un área de investigación activa.

Answer 2

He aquí una respuesta a la pregunta. Si $\, n\ge 2\, $ entonces la primera $4$ entradas en cada fila, a saber, $\, 1 0 1 0, 1 1 0 1, 1 0 0 0, 1 1 1 0, \dots, \,$ repetir en un periodo de $4$ . Hay un $0$ en cada uno de estos primeros $4$ entradas. Esta no era la prueba que querías porque es demasiado simple.

Su prueba es esencialmente la siguiente. Te has dado cuenta de algo sobre un $0$ en la fila $\, 2^n \,$ y que este $0$ continúa hasta la fila $\, 2^{n+1}. \,$ Formalizamos esta observación trabajando con polinomios sobre el campo con dos elementos. Definamos los polinomios de Laurent $\, y(n) := x^n + x^{-n} \,$ y como la característica del campo es $2$ , $\, y(0) = 1 + 1 = 0. \,$ Utilizando el álgebra simple de los exponentes obtenemos que $\, y(n)y(m) = y(n+m) + y(n-m), \,$ y los casos especiales $\, y(n)^2 = y(2n) \,$ y $\, y(2^n) = y(1)^{2^n}. $

Definir los polinomios de fila $\, r(m) := (1 + y(1))^m. \,$ La fila general es $\, r(m) = r(2^n+k) \,$ donde $\, 0\le k < 2^n. \,$ Observe que $\, r(2^n) = 1 + y(1)^{2^n} = 1 + y(2^n). \,$ También $\, r(m) = 1 + \sum_{i=1}^m c_i y(i), \,$ donde $\, c_i \,$ es el coeficiente de $\, y(i). \,$ Te has dado cuenta de que $\, c_{2^{n-1}} = 0 \,$ ¿pero cómo demostrarlo? Calculamos que $$\, r(m) = (1 \!+\! y(2^n)) r(k) = (1 \!+\! y(2^n))(1 \!+\! cy(2^{n-1}) \!+\! t) = (1 \!+\! y(2^n))(1 \!+\! t) \!+\! c y(3\,2^{n-1}) \,$$ donde $\, t \,$ son todos los términos con $\, y(i), \,$ y $\, i\ne 2^{n-1}, \,i < 2^n. \,$ Pero $\, y(2^n)y(i) = y(2^n-i) \!+\! y(2^n+i) \,$ y como $\, i \ne 2^{n-1} \,$ no conseguimos $\, y(2^{n-1}) \,$ términos en el producto $\, (1 \!+\! y(2^n))(1 \!+\! t). \,$ Eso lo demuestra.

Esto responde a su pregunta particular, pero ¿qué pasa con la intuición frente al rigor? Creo que no hay una buena respuesta a esa pregunta. Siempre hay que buscar patrones o regularidades y casos simples o extremos. Hay que tener suerte y ayuda tener mucha experiencia de fondo a la que recurrir.