lainformacion.com

Suma de fracciones positiva

Os dejo el problema de esta semana:

Probar que dados cualesquiera números reales \{x_i \}_{i=1, \ldots ,n} se verifica que:

\displaystyle{\sum_{i,j=1}^n \cfrac{x_i x_j}{i+j}} \geq 0

Suerte.

Curiosidades sobre algunas funciones complejas

Introducción

Como ya hemos visto en alguna ocasión los números complejos son un conjunto fascinante donde además ciertas propiedades de los números reales dejan de cumplirse o cambian de forma. Un ejemplo claro de ello es la imposibilidad de definir en \mathbb{C} un orden total coherente con las operaciones y con el orden de los números reales, hecho que vimos en este artículo.

Las funciones definidas sobre los números complejos tampoco se salvan de esto. Generalmente cumplen muchas de las propiedades que cumplen las correspondientes en \mathbb{R}, pero habitualmente aparece algún detalle que hace perdamos algo (o que ganemos). En este artículo vamos a ver tres funciones complejas y las compararemos con las reales para que se aprecien dichos cambios.
(Leer el resto del post)

Factorización de un primo de la forma 4k+1 en el anillo de los enteros gaussianos

Este artículo es una colaboración enviada por fede a gaussianos (arroba) gmail (punto) com.


Introducción

Un número primo de la forma 4k+1 es suma de los cuadrados de dos números enteros. Además la representación p=x^2 + y^2 es única si 0 < x < y.

Como x^2 + y^2 = (x+iy)(x-iy), la representación anterior da una factorización de un primo natural p = 4k+1 en el anillo de los enteros gaussianos. Además los factores (x+iy) y (x-iy) son primos en ese anillo.

Este post describe cómo obtener los enteros x,y que son solución de p=x^2 + y^2.

Describiendo el algoritmo

Podemos probar con un programa valores sucesivos de x hasta que encontremos la solución de x^2+y^2=p, y eso puede funcionar para primos pequeños como 100123456789 y 100987654321, pero no sirve para primos algo más grandes como el primo gemelo titánico más pequeño o el primo más pequeño de 2000 dígitos decimales.

La demostración de Zagier de que un primo de la forma 4k+1 es suma de dos cuadrados tampoco da un método práctico para encontrar la solución, ni las de Euler, Lagrange o Dedekind.

Tampoco la fórmula explícita de Gauss

x \equiv \dfrac{(2k)!}{2(k!)^2} \pmod{p}, \quad y \equiv (2k)!x \pmod{p}

es útil para calcular los valores de x e y.

Sin embargo existe un algoritmo muy simple para obtener la solución. Podemos describirlo de la siguiente forma:

Obtenemos un r < p tal que r = \pm \sqrt{-1} \pmod{p}, es decir, r^2 \equiv -1 \pmod{p}.

A continuación aplicamos el algoritmo de Euclides a \dfrac{p}{r}. El primer resto que encontramos menor que \sqrt{\dfrac{p}{2}} es el valor de x y el resto anterior es el valor de y.

El algoritmo se deriva de las demostraciones de Serret, Hermite y H.J. Smith, las primeras publicadas en el “Diario de Liouville” en 1848 y la última en el “Diario de Crelle” en 1855.

Calculadora de las componentes de los factores

Podéis probar el algoritmo introduciendo un primo en la casilla de abajo. Para encontrar primos de algunos centenares de dígitos, podéis copiar y pegar en la casilla de abajo primos cuyas 2 últimas cifras sean de la forma 4k+1 desde las páginas de “Prime Curios!”.

                                                   

  Paso  Resultado  Duración
1. Validación de entrada   
2. Busca no-residuo   
3. Calcula raíz de -1   
4. Alg.Euclides sobre p/r   
5. Comprobación  
 x =
 y =

Descripción de la calculadora

  • El paso 1 sólo verifica que el número introducido sea de la forma 4k+1.

    Los dos siguientes pasos sirven para obtener r = \sqrt{-1} \pmod{p}, y están basados en los resultados de la teoría elemental de residuos cuadráticos.

  • En el paso 2 se busca un no-residuo cuadrático t (es decir, un número que no sea un cuadrado \pmod{p}). Como la mitad de los números menores que p son no-residuos, y es rápido determinar si un número es o no un residuo cuadrático (calculando el símbolo de Jacobi), probando con números al azar podemos obtener rápidamente un no-residuo cuadrático.

    Sin embargo no está demostrado (todavía) que exista algoritmo determinista en tiempo polinomial para obtener un no-residuo cuadrático.

    La implementación devuelve el menor no-residuo, si éste es menor que 2000.

  • Una vez que tenemos un no-residuo t, en el paso 3 se obtiene r = t^{(p-1)/4} \pmod{p}.

    Por el criterio de Euler para residuos cuadráticos, r= \pm \sqrt{-1} \pmod{p}.

  • Que el paso 4 nos da la solución se justifica por el teorema de Serret:

    Si r^2 \equiv -1 \pmod{p}, \ r < p, la lista de cocientes parciales del desarrollo en fracción continua de \dfrac{p}{r} es simétrica (omando la lista de longitud par, lo que siempre es posible porque {}[a_0, \ldots, a_n] = [a_0, \ldots, a_n-1, 1]).

    A partir de los resultados mencionados en el post sobre fracciones continuas finitas, y con la notación usada alli, resulta que p = N[a_0,\ldots,a_h,a_h,\ldots ,a_0] = N[a_0,\ldots,a_h]^2 + N[a_0,\ldots,a_{h-1}]^2 .

    Por ser simétrica la fracción continua, los restos que se obtienen al aplicar el algoritmo de Euclides a \dfrac{p}{r} son los numeradores de los convergentes parciales (en orden inverso) y por tanto no hace falta calcular los numeradores de dichos convergentes parciales. Basta con aplicar el algoritmo de Euclides a \dfrac{p}{r} hasta que obtengamos un resto menor que \sqrt{\dfrac{p}{2}} .

  • Por último, en el paso 5 se comprueba si los valores obtenidos cumplen x^2 + y^2=p. Si no se cumple la igualdad, se concluye que el número p introducido no es primo (y los valores de t,r no serán, en general, correctos).

El teorema de Serret se demuestra fácilmente usando la relación entre numeradores y denominadores de los convergentes parciales consecutivos y las reglas de formación de esos numeradores y denominadores. De ese teorema se obtiene una demostración de que un primo de la forma 4k+1 es suma de dos cuadrados, que pertenece al grupo de demostraciones que parten de que, para un primo de esa forma, -1 es un cuadrado \pmod{p}

En cambio la demostración de H.J. Smith que exponemos a continuación no hace uso de este hecho.

La demostración de H.J. Smith

Usamos la notación {}[ a_0, a_1, \ldots, a_n ] para representar la fracción continua finita cuyos cocientes parciales son a_0,a_1, \ldots ,a_n. Designamos con N[ a_0, a_1, \ldots, a_n ] el numerador de la fracción {}[ a_0, a_1, \ldots, a_n ] .

Como {}[a_0, a_1, \ldots, a_{n-1}, 1 ] = [a_0, a_1, \ldots, a_{n-1} + 1 ], asumimos que el último cociente es siempre mayor que 1.

En el post sobre fracciones continuas vimos que se cumple

  • N[a_0, a_1, \ldots, a_n ] =  N[a_n, a_{n-1}, \ldots, a_0 ] ,
  • N[a_0,\ldots,a_k,\ldots,a_n] =  N[a_0,\ldots,a_k] N[a_{k+1},\ldots,a_n] +  N[a_0,\ldots,a_{k-1}]  N[a_{k+2},\ldots,a_n]

Estas identidades implican:

(1)   N[a_0,\ldots,a_h,a_h,\ldots ,a_0] = N[a_0,\ldots,a_h]^2 + N[a_0,\ldots,a_{h-1}]^2 .
(2)   N[a_0,\ldots,a_h,a_{h+1},a_h,\ldots ,a_0] = N[a_0,\ldots,a_{h}] (  N[a_0,\ldots,a_{h+1}] + N[a_0,\ldots,a_{h-1}] )  .

De esta última igualdad se concluye que si a_0 es mayor que 1 (y hay más de un cociente), N[a_0,\ldots,a_h,a_{h+1},a_h,\ldots ,a_0] no es primo.

Para un primo de la forma 4k + 1, sea S el conjunto de las fracciones \dfrac{p}{i}, \ \  2 \le i \le \dfrac{p-1}{2} , desarrolladas en fracción continua.

En el desarrollo en fracción continua de \dfrac{p}{i} = [a_0, a_1, \ldots, a_n ] se tiene que a_0 \ge 2 , porque i \le \dfrac{p-1}{2} , y a_n \ge 2 porque asumimos que el último cociente es mayor que 1.

La función f([a_0, \ldots, a_n ]) = [a_n, \ldots, a_0] asocia a cada elemento de S otro elemento de S, porque el numerador de una fracción continua no se altera si se invierte el orden de los cocientes y el denominador es un número menor que \dfrac {p}{2}, porque a_n \ge 2.

La función f es entonces una involución de S.

Si p=4k+1, el número de elementos de S es 2k-1, un número impar, y entonces f tiene por lo menos un punto fijo, es decir, existe un r, \  2 \le r \le \dfrac{p-1}{2} que da una fracción continua simétrica \dfrac{p}{r} = [a_0, \ldots, a_h, a_h, \ldots, a_0] (por la observación (2) anterior, el número de cocientes ha de ser par porque p es primo).

Entonces p es suma de 2 cuadrados por la observación (1) anterior.

Sea \dfrac{p}{r} = [a_0, \ldots, a_h, a_h, \ldots, a_0 ] = \dfrac{N[a_0, \ldots, a_h , a_h, \ldots, a_0]}{D[a_0, \ldots, a_h , a_h, \ldots, a_0]}.

Como

D[a_0,a_1,\ldots a_n] =   N[a_1,\ldots a_n], \ \ r=N[a_1,\ldots a_h, a_h, \ldots, a_0]

y como

 N[a_0 \ldots,a_n] N[a_1, \ldots,a_{n-1}] - N[a_0 \ldots,a_{n-1}] N[a_1, \ldots,a_n] = (-1)^{n-1}

tenemos que

 p N[a_1,\ldots,a_h,a_h,\ldots, a_1] - r^2 = 1

y por tanto

r^2 \equiv -1 \pmod{p}

.

Hamilton-Einstein: conectando lo grande y lo pequeño

Con el sugerente título

La conexión entre lo infinitamente grande y lo infinitamente pequeño

mi amigo Juanjo se inicia en el mundo de los blogs (¡¡ya era hora!!).

Como él mismo dice:

El objetivo de este blog es el de compartir conocimientos de Física, una ciencia que me apasiona y a la que trato de dedicarle tiempo. Espero que me acompañéis en mi viaje. El nombre del blog viene de dos grandísimos físico-matemáticos: Hamilton y Einstein. La unión de ambos pretende simbolizar lo que se va buscando hoy día en física: la Teoría Unificada, la Gran Teoría…

Teniendo en cuenta los conocimientos que posee estoy convencido de que hará de su blog un lugar muy interesante para todos los aficionados a la física y a las matemáticas.

La fuente

La fuente primordial de todas las matemáticas son los números enteros.

Herman Minkowski

INFINITUM. Citas matemáticas

Cuando uno conoce conjuntos así no puede más que estar de acuerdo con Minkowski.

¿Qué pensáis vosotros?

Raíces y probabilidad

Hoy, como es habitual, os traigo el problema de la semana. Es el siguiente:

Calcular la probabilidad de que la ecuación de segundo grado con coeficientes reales

ax^2+bx+c=0

tenga raíces reales.

Se entiende dicha probabilidad en el caso límite cuando N \to \infty, tomando coeficientes a,b,c \in \[ -N,N \].

Los curiosos enteros gaussianos

Introducción

Un joven Gauss

Un joven Gauss

El conjunto \mathbb{Z}=\{ \ldots -3,-2,-1,0,1,2,3 \ldots \} de los números enteros es un conjunto numérico bien conocido por todos nosotros. Y, aunque seguro que en menor medida, también lo es el conjunto \mathbb{C}=\{ a+bi; \; a, b \in \mathbb{R} \} de los números complejos, conjunto numérico muy interesante y muy útil en gran cantidad de problemas relacionados con muchas ramas de las matemáticas.

¿Qué ocurriría sin mezclamos las dos definiciones de estos conjuntos? Me explico:

¿Tendrá alguna utilidad considerar el conjunto de los números complejos cuyas partes real e imaginaria son números enteros?

No habría sido extraño que fuera algo así lo que pensó Gauss al introducir este conjunto en 1832 (aunque en realidad su motivación fue el estudio sobre sumas de cuadrados). Y la verdad es que acertó (como muchas otras veces). Encontró un conjunto realmente especial. Vamos a hablar un poco sobre él y sobre sus interesantes y curiosas propiedades.
(Leer el resto del post)

Monstruos numéricos

Este artículo ha sido promovido para portada en Menéame. Si te ha gustado y quieres votarlo haz click en este enlace y pincha en Menéalo.

Introducción

La familia de los números naturales es muy grande, inmensa. En ella conviven infinitos (y numerables, es decir, contables) miembros que, aunque pueda parecer curioso tratándose de una familia, nunca nacieron y nunca morirán. Siempre han estado ahí y ahí continuarán.

Todos ellos son importantes y también todos ellos pueden ser útiles en cierto momento. En el transcurso de nuestro viaje por este camino temporal llamado vida nos encontramos (y nos seguiremos encontrando) con muchos de ellos. Bien es cierto que habitualmente toparemos con miembros más bien pequeños, de bajo valor númerico (aunque esto no significa que tengan poco valor). Pero de vez en cuando asistiremos a la aparición de algún miembro cuyo peso como número tiene cierta entidad.

Pero al fin y al cabo nuestra existencia es finita, terminará. Este hecho unido al carácter infinito de los números naturales hace que resulte imposible encontrarse con todos, que sea inviable conocer a todos los miembros de esta familia.

Uniendo estos dos hechos (generalmente nos encontraremos con números relativamente pequeños y nos es imposible conocerlos a todos en persona) es evidente que muchos números grandes quedarán fuera de nuestro alcance en el sentido de que no tendremos el placer de tenerlos delante.

Posiblemente los tres números que os voy a presentar hoy pertenezcan a estos últimos. Bueno, puede que el primero de ellos, por estar relacionado con un juego de mesa muy popular, sí sea conocido por vosotros, pero estoy convencido de que muchos de los que leáis este artículo añadiréis al menos dos números más a vuestra lista mental de miembros conocidos de la familia de los números naturales.
(Leer el resto del post)

Aleatoriedad sin azar

La generación de números aleatorios es una cuestión demasiado importante para dejarla al azar.

Donald Knuth

INFINITUM. Citas matemáticas

Curiosa frase, paradójica en cierto sentido, del protagonista de nuestro artículo de ayer.

La notación de Knuth, o cómo escribir ciertos números sin morir en el intento

Introducción

Los seres humanos tenemos 2 ojos, 5 dedos en cada mano y cada pie y la esperanza de vida en España ronda los 80 años actualmente. Un euro tiene 100 céntimos y un mileurista cobra 1000 euros mensuales. Podemos tener un coche de 12000 euros y una vivienda que nos cueste 200000 y ha habido semanas en las que el premio para la primera categoría del Euromillón ha rondado los 70 millones de euros (70000000 €).

Todas esas cantidades pueden ser escritas utilizando la notación habitual. Pero es evidente que cuanto mayor es el número esta forma de escribirlos se hace cada vez más engorrosa. Por suerte tenemos la potencias, gran arma para simplificar la escritura de ciertos números grandes.

Por ejemplo, si quisiéramos escribir la edad de la Tierra deberíamos escribir este número:

4550000000

que es la cantidad (en años) que se estima como edad de nuestro planeta. Utilizando las potencias la forma de escribirlo es más corta:

4,55 \cdot 10^9

Para esta cantidad puede que todavía no se perciba en toda su magnitud la utilidad de las potencias para esta tarea. Probemos con otra. Para escribir el número de átomos que se estima que hay en la Tierra tendríamos que escribir un 1 seguido de 51 ceros. Es decir, un número que ya tiene una cierta magnitud y, por qué no decirlo, bastante engorroso de escribir de la manera habitual. Nuestras amigas las potencias nos ayudan a simplificar esta tarea:

10^{51}

Hemos escrito el mismo número pero, como es evidente, de una forma bastante más cómoda.

Otro ejemplo más. A estas alturas casi todo sabréis qué es un googol. Sí, exacto, un 1 seguido de cien ceros. Escribir este número con la notación habitual alcanza ya el nivel de tarea insufrible. Otra vez las potencias nos ayudan con ella:

10^{100}

Pero, ¿qué ocurre si queremos escribir el número googelplex? Este número es un 1 seguidos de un googol de ceros y tiene ya unas dimensiones inimaginables para el ser humano. Bueno, os echo una mano:

10^{10^{100}}

Para representarlo hemos necesitado no sólo una potencia, sino dos. Vamos, una torre de potencias.

Con la ayuda de estas torres de potencias podemos representar número enormes que, como dije antes, escapan a nuestra percepción. La pregunta es: ¿podemos necesitar en algún momento escribir algún número cuya representación no pueda hacerse de forma sencilla con estas notaciones? La respuesta es . Y la notación de Knuth es una de las opciones más recomendables.
(Leer el resto del post)

Anterior