El promedio de sus vecinos

Os dejo el problema de esta semana:

Sea \{a_{ij}\}_{i, j \in\mathbb{Z}} una familia de números reales pertenecientes a [0,1], tal que cada a_{ij} coincide con el promedio de sus cuatro vecinos, es decir,

a_{ij}=\cfrac{a_{i+1, j}+a_{i-1, j}+a_{i, j+1}+a_{i, j-1}}{4}, \quad \forall i, j \in\mathbb{Z}.

Demostrar que a_{ij}=a_{0,0}, \forall i, j\in\mathbb{Z}.

Ánimo y a por él.

Share

Sin comentarios

  1. Trackback | 27 oct, 2009

    Bitacoras.com

  2. J. H. S. | 27 de octubre de 2009 | 09:52

    Vótalo Thumb up 0

    Comparar con este de aquí… Saludos.

  3. Dani | 27 de octubre de 2009 | 10:18

    Vótalo Thumb up 0

    Sí, pero ese es mucho más fácil. Siendo naturales basta con demostrar que si no fueran todos iguales siempre habría una sucesión de numeros estrictamente decreciente, lo cual es absurdo para naturales. Este caso es algo más sutil, creo.

  4. Dani | 27 de octubre de 2009 | 10:38

    Vótalo Thumb up 0

    ah, no! dice positivos, no “enteros” positivos (creo que esa parte la inventó mi subconsciente jajajaja

  5. hernan | 27 de octubre de 2009 | 14:03

    Vótalo Thumb up 0

    La condición de que el valor en cada punto sea igual al promedio de sus vecinos es análogo (en el dominio discretizado) a pedir que la función (en el dominio real) sea armónica.
    Y si el soporte es todo el plano, y si la función viene acotada (en [0,1] en nuestro caso), esto debe implicar que la función es constante (por un argumento similar, aunque más elemental, que el del caso real… propiedad que a su vez suele usarse para demostrar el teorema fundamental del álgebra).
    http://en.wikipedia.org/wiki/Harmonic_function#The_maximum_principle

  6. M | 27 de octubre de 2009 | 16:20

    Vótalo Thumb up 0

    Efectivamente, hernan. Esto es el teorema de Liouville para funciones armónicas (versión discreta). En el enlace que has puesto, y en la propuesta de J.H.S., vemos que el resultado es cierto bajo la hipótesis de acotación (por la izquierda o por la derecha) de los valores. Además también es cierto en cualquier dimensión (finita). A ver si se nos ocurre una prueba sencilla.

  7. orlin | 27 de octubre de 2009 | 16:41

    Vótalo Thumb up 0

    Creo que la solución puede ir por aquí…

    Si representamos esos números en una cuadrícula tal y como propone el problema de J.H.S. Entonces si nos ponemos encima de un punto aleatorio y giramos 45 grados, el resultado ha de ser el mismo (ya que cada número depende de la suma de los 4 más proximos), es decir, la distribución de los números en la cuadrícula no cambia. Por lo tanto ha de ser invariante si hacemos:

    a_{ij} \rightarrow a_{i-2,j}
    a_{ij} \rightarrow a_{i-1,j-1}
    a_{ij} \rightarrow a_{i,j-2}
    a_{ij} \rightarrow a_{i+1,j-1}
    a_{ij} \rightarrow a_{i+1,j+1}
    a_{ij} \rightarrow a_{i+2,j}
    a_{ij} \rightarrow a_{i,j+2}
    a_{ij} \rightarrow a_{i-1,j+1}

    Es decir, poniendonos en los 4 puntos más cercanos a a_{ij} y haciendo rotaciones de 45 grados.

    Ahora si cogemos puntos y usamos la fórmula del ejercicio, transformando el i, j convenientemente, se podrá obtener igualdades entre a_{i,j} y el resto.

    En mi desarrollo no he usado que los números están acotados y no sé en que parte del razonamiento debo incluirlo… :S

  8. hernan | 27 de octubre de 2009 | 17:11

    Vótalo Thumb up 0

    No se ve tan fácil:
    Acá hacen una demostración probabilística (un random walk), para el caso n-dimensional http://everything2.com/title/Z%255En+admits+no+bounded+harmonic+function

    orlin, la acotación es necesaria. Contraejemplo: un plano inclinado, por ej: a_{i,j} = i + j o a_{i,j} = i

  9. orlin | 27 de octubre de 2009 | 17:27

    Vótalo Thumb up 0

    No entiendo el contraejemplo Hernan, cada a_{i,j} es igual a cada número real entre [0,1] del problema. Los íncides i,j són solo para situarlos en el plano. Además en tu contraejemplo los a_{i,j} no tienen la simetría de la que yo hablo.
    Habrá algo que se me escapa…

  10. Gulliver | 28 de octubre de 2009 | 13:41

    Vótalo Thumb up 0

    Haciendo una transformación de Fourier discreta de a(x,y) en la variable y por ejemplo, la condición de armonicidad discreta se transforma en una ecuación tal como a_{x+1} + a_{x-1} - 2 a_x = k^2 a_x, donde k es un número real. Las soluciones son exponenciales, y por tanto no acotadas a menos que a(x,y) sea constante.

  11. hernan | 28 de octubre de 2009 | 15:35

    Vótalo Thumb up 0

    Parece prometedor encararlo por Fourier, pero no veo cómo puedes desacoplar la condición de armonicidad (que involucra todo el entorno) de manera que pueda expresarse como una condición en una sola variable. (Puedes explicarlo más?)

    Lo que sí veo es que, si hacemos la transforma discreta de Fourier bidimensional, A(u,v) = \sum \sum a_{x,y} e^{-i (u x + v y)} la condición de armonicidad en el dominio transformado lleva a que A(u,v) ( cos (u) + cos(v) -2) = 0 \; \forall u,v ; si el factor de la derecha puediera anularse para un (o varios) par(es) de frecuencias no triviales, cabria la posibilidad de tener un a_{x,y} acotado no constante, con esas componentes de Fourier. Pero sólo se anula en el origen (y en múltiplos de 2 \pi, que en la tranformada discreta de Fourier equivalen al origen). Lo cual “casi demuestra” que sólo cabe la solución de frecuencia cero (a_{x,y}= k)…

  12. smart | 29 de octubre de 2009 | 05:47

    Vótalo Thumb up 0

    En mi opinión es más sencillo que todo esto y tiene que ver con que cualquier a_{ij} \in [0,1] cerrado.

    En los dos casos extremos:

    a_{ij} = 0 =  \cfrac {a_{i+1j} + a_{i-1j} + a_{ij+1} + a_{ij-1} } { 4 }

    a_{ij} = 1 =  \cfrac {a_{i+1j} + a_{i-1j} + a_{ij+1} + a_{ij-1} } { 4 }

    sólo son posibles si todos los miembros de la suma son iguales e iguales al resultado:

    a_{ij} = 0  \Rightarrow a_{ij} = a_{i+1j} = a_{i-1j} = a_{ij+1} = a_{ij-1} = 0

    a_{ij} = 1  \Rightarrow a_{ij} = a_{i+1j} = a_{i-1j} = a_{ij+1} = a_{ij-1} = 1

    Ya que no hay ningún valor menor (en el caso de ser cero) o mayor (en el caso de ser 1) que “baje” o “suba” la media.

    Estas dos condiciones de los extremos son las que imponen que todos los elementos sean iguales, por lo tanto cualquier a_{ij} ha de ser necesariamente igual a a_{00}

    Saludos

  13. Dani | 29 de octubre de 2009 | 10:20

    Vótalo Thumb up 0

    en efecto si hubiera un a_{i j}=0,1 sería trivial. Sería igualmente trivial si \exists a_{i_0 j_0 }=sup \{ a_{ij}, \quad (i,j) \in \mathbb{Z} \times \mathbb{Z} \} o \exists a_{i_0 j_0}=inf \{ a_{ij}, \quad (i,j) \in \mathbb{Z} \times \mathbb {Z} \} Pero… ¿Puedes demostrar que eso es siempre cierto, es decir, que el supremo o el ínfimo del conjunto siempre se alcanza en algún a_{ij}?

  14. hernan | 30 de octubre de 2009 | 02:26

    Vótalo Thumb up 0

    Mi demostración por Fourier no es rigurosa, pero alguien que domine teoría de distribuciones y transformada de Fourier discreta podría emprolijarla, creo.

    Básicamente, lo que estoy suponiendo es que toda función acotada discreta en R^2 tiene una transformada de Fourier bidimensional… si aceptamos la inclusión de “deltas de Dirac”. Si y sólo si. (y creo que esto es generalizable para funciones de variable continua, y para R^n, y tiene que ver con una dualidad del espacio l^{\infty} con el espacio -en el dominio transformado- L^2, pero estas son honduras para mí).

    Si esto es correcto, creo que podría extenderse la demostración para demostrar casos de promedios más generales, siempre que conservemos simetría: por ejemplo, tomando los ocho vecinos más cercanos… puesto que cada par de vecinos simétrico aportaría un coseno ¿será verdad?
    No termino de creérmelo.

  15. hernan | 30 de octubre de 2009 | 02:30

    Vótalo Thumb up 0

    Perdón, quise decir “dualidad …con el espacio L^1
    http://en.wikipedia.org/wiki/Lp_space#Dual_spaces

  16. M | 31 de octubre de 2009 | 01:14

    Vótalo Thumb up 0

    Voy a responder a la cuestión n-dimensional asumiendo acotación superior e inferior de los valores.

    Sea a:\;\mathbb{Z}^n\to A\subset \mathbb{R}, con A acotado (superior e inferiormente), y tal que a es armónica, es decir:

    a(X)=\frac{1}{2n}(a(X+e_1)+a(X-e_1)+\ldots+a(X+e_n)+a(X-e_n)),

    siendo e_j las n-uplas canónicas: (1,0,\ldots,0),\ldots,(0,0,\ldots,0,1).

    Fijados j\in\{1,\ldots,n\} y \mu\in\{-1,+1\}, definimos la función incremento b(X):=a(X)-a(X+\mu e_j).

    1) b(X) es armónica: b(X+e_1)+b(X-e_1)+\ldots+b(X+e_n)+b(X-e_n)=(2n)b(X).

    2) b está acotada superiormente. Sea S_b:=\displaystyle{\sup_{X\in\mathbb{Z}^n}} b(X) y supongamos por reducción al absurdo que S_b>0.

    3) Por caracterización de supremo: para todo \epsilon>0, existe X tal que b(X)\geq S_b-\epsilon. Entonces, para este X se tendrá usando la condición de armonicidad (¿estará en el diccionario? :) ):

    b(X+\mu e_j)=(2n)b(X)-\bigg((b(X+e_1)+b(X-e_1))+\ldots+(b(X-\mu e_j))+\ldots+(b(X+e_n)+b(X-e_n))\bigg)\geq (2n)(S_b-\epsilon)-(2n-1)S_b=S_b-(2n)\epsilon.

    Del mismo modo,

    b(X+2\mu e_j)\geq (2n)b(X+\mu e_j)-(2n-1)S_b\geq S_b-(2n)^2\epsilon,

    y en general b(X+i\mu e_j)\geq S_b-(2n)^i\epsilon,\quad i\geq 0.

    4) Sea i natural mayor estricto que \dfrac{2(S_a-I_a)}{S_b}, donde S_a e I_a son, respectivamente el supremo e ínfimo de la función inicial a (si a no es constante entonces S_a\neq I_a). Fijemos \epsilon menor que \dfrac{S_b}{2(2n)^i}, y tomemos X tal que b(X)\geq S_b-\epsilon. Entonces:

    S_a-I_a\geq a(X)-a(X+i\mu e_j)=\displaystyle{\sum_{k=1}^i a(X+(k-1)\mu e_j)-a(X+k\mu e_j)}=\displaystyle{\sum_{k=1}^i} b(X+(k-1)\mu e_j),

    con b(X+(k-1)\mu e_j)\geq S_b-(2n)^{k-1}\epsilon>\dfrac{S_b}{2}. Luego, sigue que

    S_a-I_a>i\dfrac{S_b}{2}>S_a-I_a. Absurdo.

    5) Tenemos entonces que los supremos de las funciones incrementos b‘s son no positivos, y en particular:

    a(X)\leq a(X+\mu e_j),\forall X\in \mathbb{Z}^n,\; \mu=\pm 1,\;j=1,\ldots,n. Esto implica a partir de la condición de armonicidad que a debe ser constante.

    Veré si logro afinar algo más y eliminar la doble acotación inferior-superior, dejándola en acotación por un único lado como hipótesis. Por otro lado, no sé si J.H.S. (al respecto del link que indicó en su comentario) conoce una prueba más sencilla.

  17. Juan Carlos | 6 de noviembre de 2009 | 22:49

    Vótalo Thumb up 0

    Ahí va mi idea.

    Si X = {a:ZxZ -> R acotadas}, podemos definir en X la norma del supremo: |a| = sup {a(i,j):i,j pertenecen a Z}

    También podemos definir varias seminormas: norma-N (a) = max {a(i,j) : -N <= i,j X como Ta = b, donde b(i,j) = la media de los 4 vecinos. Es fácil comprobar que, por ejemplo, |Ta| X como Ta = c, donde c(0,0) = a(0,0), y c(i,j) = la media de los 4 vecinos para todo (i,j) (0,0).

    El enunciado se puede traducir diciendo que si Ta = a y a(i,j) está entre 0 y 1 para todo (i,j) de ZxZ, entonces a es constante.

    Mi idea es la siguiente:

    Conjetura 1 (estoy intentando demostrarla, es de carácter técnico): si a:ZxZ -> X cumple que a(i,j) = 0 para todo (i,j) (0,0), si llamamos x = a(0,0), entonces la aplicación reiterada del operador T’ sobre a converge puntualmente a la constante x en cada punto. De otra forma, la norma-N |T’^n(a) – x| -> 0 para cada N.

    Conjetura 2 (la demostración sería idéntica a la de la conjetura 1): si a:ZxZ -> cumple que a(i,j) = 1 para todo (i,j) (0,0), si llamamos x = a(0,0), entonces la aplicación reiterada del operador T’ sobre a converge puntualmente a la constante x en cada punto. De otra forma, la norma-N |T’^n(a) – x| -> 0 para cada N.

    Lema: la aplicación reiterada de T’ sobre a (a:ZxZ -> [0,1]) converge puntualmente a x = a(0,0) en cada punto. Es decir, la norma-N |T’^n(a) – x| -> 0. La demostración es sencilla, sería una especie de “lema del sandwich” entre las dos aplicaciones de las conjeturas 1 y 2.

    Teorema: si a está en las condiciones del enunciado (Ta = a), entonces trivialmente T’(a) = a. Se comprueba por inducción inmediatamente que T’^n(a) = a para todo n.
    Como T’^n(a) converge a la constante x = a(0,0) en norma-N para todo, y T’^n(a) es constante (respecto de n), se tiene: |T’^n(a) – x| = 0, por lo que T’^n(a)(i,j) = x para todo i,j entre -N y N, pero como N es arbitrario, T’^n(a)(i,j) = x para todo i,j. Por tanto, a(i,j) = T’^n(a)(i,j) = x, como queríamos demostrar.

    ¿Alguien que haya trabajado con alguna ecuación de difusión (como la del calor) y me eche una manilla en demostrar la conjetura 1 (o en demostrarme que es falsa y que estoy equivocado, que también puede ser)? Ahora mismo tan sólo se me ocurre acotar “a lo bruto”.

  18. Tanhäuser | 9 de noviembre de 2009 | 06:52

    Vótalo Thumb up 0

    ¡Tengo una prueba!

    Me ocupa un par de páginas. ¿Cómo os la puedo proporcionar?

  19. M | 9 de noviembre de 2009 | 16:27

    Vótalo Thumb up 0

    Hola Tanhäuser. ¿Y si la subes (en pdf o escaneado) a rapidshare?

    Conozco una prueba muy breve del caso no acotado (por uno solo de los extremos) general, pero no me parece muy asequible. La que puse arriba para el caso acotado sólo necesitaba el concepto de supremo. A ver si saco tiempo y la comento.

  20. Tanhäuser | 9 de noviembre de 2009 | 17:41

    Vótalo Thumb up 0

    Intentaré subirlar como dices, M.

    La idea que yo he seguido es muy simple. Pruebo que acotación+armonicidad implican que la sucesión a_{j,k} es 2-periódica en las dos variables. De ahí se sigue inmediatamente el resultado.

  21. M | 12 de noviembre de 2009 | 01:27

    Vótalo Thumb up 0

    Tanhäuser, cuando dices acotación+armonicidad, ¿te refieres a acotación por “ambos lados” (sup-inf), o impones sólo acotación por un lado?

    Por otra parte, para el caso bidimensional, imponiendo sólo acotación superior (o inferior), creo que se puede probar que los valores son constantes expresando la relación de armonicidad en forma matricial (al estilo de la fórmula de cinco puntos para discretizar la ecuación de Poisson). Se obtiene una matriz regular simétrica, tridiagonal por bloques, cuya inversa tiene un radio espectral que tiende a infinito si se aumenta la dimensión. Esto debería implicar no acotación de los valores, a menos que sean propiamente constantes. A ver si lo escribo bien con tiempo…

    El problema que indicaba J.H.S. en el segundo comentario de esta entrada aparece como problema 109 en el libro de Donald J. Newman, a problem seminar (de hecho, es el último problema del libro). La solución, que es bastante breve, parece ser igualmente válida en cualquier dimensión, pero usa técnicas de análisis funcional poco elementales (teorema de Krein-Milman).

  22. J. H. S. | 12 de noviembre de 2009 | 12:28

    Vótalo Thumb up 0

    @M:

    1. Apuesto que se refiere a acotación por arriba y por abajo.
    2. Mi opinión es que D. J. Newman era de otro planeta. Su solución a 109 es extraordinaria, por decir poco. ¿Has estudiado la prueba que dió del teorema del número primo? La más simple que se conoce. El punto de vista generalizado en ese rubro es que no puede haber una prueba más sencilla que la de él.

    Saludos.

  23. M | 14 de noviembre de 2009 | 20:48

    Vótalo Thumb up 0

    Gracias por la referencia, J.H.S. No conocía ninguna de las dos pruebas de D.J. Newman del PNT. Acabo de estudiar la primera prueba y me parece estupenda (y creo haberla entendido!). Sin embargo es un prueba indirecta, ya que lo que demuestra es un enunciado equivalente al PNT: \displaystyle{\sum_{n=1}^\infty \dfrac{\mu(n)}{n}} converge (…a 0; \mu es la función de Möbius).

    En comparación a la prueba 1 de Newman, no parece nada simple probar esta última equivalencia (ver, por ejemplo, aquí y aquí. En este último enlace, se alude en la sección -1. Equivalences- a un tal Diamond :) ).

  24. J. H. S. | 15 de noviembre de 2009 | 03:14

    Vótalo Thumb up 0

    Dichas equivalencias son resultados standard en un curso de Aritmética. Por otro lado, el escrito de Newman contiene ambos ataques. Primero hace uso de la equivalencia que mencionas y después indica como se le hace para establcer de modo directo el resultado.

    Saludos.

Escribe un comentario

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.