Azar y aritm´ etica

arXiv:0909.0922v2 [math.PR] 10 Sep 2009

Un cap´ıtulo de la teor´ıa probabil´ıstica de n´ umeros

Harald Andr´es Helfgott H. A. Helfgott, School of Mathematics, University of Bristol, Bristol, BS8 1TW, United Kingdom E-mail address: [email protected]

2000 Mathematics Subject Classification. Primary 11K99 Resumen. Sea ω(n) el n´ umero de divisores primos de un entero n. Sea n un entero tomado al azar entre 1 y N . Qu´e se puede decir del valor que entonces tomar´ a ω(n)? Cu´ al es su esperanza? Cu´ al es su distribucion en el limite? Cu´ al es la probabilidad que ω(n) tome valores que se alejen mucho de su esperanza? Estudiamos estas preguntas a guisa de introducci´ on a la teor´ıa de n´ umeros probabil´ıstica. Trataremos varios t´ opicos centrales de la teor´ıa de probabilidades sin suponer conocimientos previos en el ´ area. No asumiremos ni teor´ıa de la medida ni an´ alisis complejo. En los ejercicios, entre otros t´ opicos, se desarrollar´ an las bases de la teor´ıa de cribas como una aplicaci´ on de ideas probabil´ısticas.

Al miaj gepatroj

´Indice general Cap´ıtulo 1. Los divisores primos 1.1. La esperanza 1.2. La varianza 1.3. El l´ımite central 1.4. Grandes desviaciones: cotas superiores. Valores cr´ıticos. 1.5. Grandes desviaciones: cotas inferiores. Entrop´ıa.

1 1 7 18 31 38

Ap´endice A. Rudimentos de probabilidades

53

Ap´endice B.

59

Comentarios finales

Bibliograf´ıa

61

´Indice alfab´etico

63

v

vi

´INDICE GENERAL

Prefacio Este es un estudio de los factores primos de un n´ umero tomado al azar. El objeto principal es servir de introducci´ on a la teor´ıa probabil´ıstica de n´ umeros y, al mismo tiempo, a varios temas centrales en la teor´ıa de las probabilidades en general: la varianza, el l´ımite central, las grandes desviaciones, la entrop´ıa. La historia de la teor´ıa de n´ umeros probabil´ıstica comienza con Hardy y Ramanujan [5], quienes fueron los primeros en analizar el tema central de este libro: la distribuci´on del n´ umero ω(n) de divisores primos de un n´ umero entero aleatorio n. En el curso de la generaci´ on siguiente – notablemente con el teorema de Erd¨os y Kac [4], el cual estudiaremos en la secci´ on 1.3 – se fueron asimilando conceptos y t´ecnicas de la teor´ıa de probabilidades en general al estudio incipiente del tema. El ´area ha seguido desarroll´andose hasta nuestros d´ıas, gracias tanto a especialistas en teor´ıa de n´ umeros como a probabilistas. No asumiremos ning´ un conocimiento de an´ alisis complejo ni de teor´ıa de la medida. Al final de cada secci´ on, se encontrar´ a una serie de notas y problemas; esencialmente se trata de ejercicios guiados o esbozos de pruebas a seguir y completar con l´apiz y papel. Entre otros t´opicos, las notas de fin de secci´ on desarrollan las bases de la teor´ıa de cribas, tanto como una aplicaci´ on de conceptos probabil´ısticos, como para uso en el texto principal. Mi objetivo ha sido dar las pruebas que me parecen ser las m´ as naturales, antes que las m´ as conocidas. El texto presente est´ a basado en las notas de clase de un curso que dict´e en Julio y Agosto de 2007 bajo los auspicios del IMCA (Instituto de Matem´atica y Ciencias Afines) en Lima, Per´ u. Agradezco tanto al IMCA como a la Universidad Mayor de San Marcos por su hospitalidad.

´INDICE GENERAL

vii

Notaci´ on Sean d y n n´ umeros enteros. Escribimos d|n cuando queremos decir que d divide a n exactamente, es decir, sin dejar resto: 3|6, 5|15, 1|n para todo n. Escribimos d ∤ n cuando d no divide a n, es decir, cuando la division de n por d deja resto: 4 ∤ 6, 7 ∤ 15, (n + 1) ∤ n para todo n. La letra p siempre designar´a a un n´ umero primo. La funci´on Λ(n) (funci´on de von Mangoldt) se define como sigue: ( log p si n = pα para alg´ un primo p y alg´ un entero α > 0 Λ(n) = 0 si no es as´ı. Denotamos por ⌊x⌋ el m´ aximo entero n que no sea mayor que x. Por ejemplo, ⌊2,75⌋ = 2, ⌊7⌋ = 7, ⌊π⌋ = 3. Cuando decimos “logaritmo” o escribimos log x, tenemos siempre en mente al logaritmo en base e, a menos que otra base se especifique explicitamente (“logaritmo en base 2”, por ejemplo). Al contrario de los escritores franceses, utilizaremos la notaci´ on log2 x para el logaritmo base 2 de x, y log log x para el logaritmo (base e) del logaritmo (base e) de x. Utilizaremos la notaci´ on O, o de Landau dadas dos funciones f , g, (a) se escribe f (x) = O(g(x)) cuando existen constantes c1 , c2 > 0 tales que |f (x)/g(x)| < c1 para todo x > c2 ; (b) se escribe f (x) = o(g(x)) cuando l´ımx→∞ f (x)/g(x) = 0. Est´a claro que 2 3 2 f (x) = o(g(x)) implica f (x) = O(g(x)), pero no viceversa. Ejemplos: P x = O(x ), x = 3 o(x ), f (x) = O(f (x)) (para todo f ), sin x = O(1), x sin x = O(x), n≤x 1/n = O(log n), P Q n n≤x (−1) /n = O(1), n≤x (1−1/n) = o(1). En particular, f (x) = O(1) quiere decir que f est´ a acotada por una constante, y f (x) = o(1) quiere decir que f tiende a cero cuando x va al infinito. Escribimos Oc (1), oδ,z (1) si dichas constantes dependen de c o δ y z, por ejemplo. La expresi´ on “f (x) ≪ g(x)” es un sin´ onimo de “f (x) = O(g(x))”; la expresi´ on “f (x) ≫ g(x)” es un sin´ onimo de “g(x) = O(f (x))”. Escribimos f (x) ∼ g(x) cuando queremos decir que f es asint´otica con respecto a g, i.e., l´ım f (x)/g(x) = 1. x→∞

Si decimos que f (x) = o(g(x)) (o f (x) ∼ g(x)) “cuando x → 0”, queremos decir que l´ımx→0 f (x)/g(x) = 0 (o, respectivamente, l´ımx→0 f (x)/g(x) = 1). Denotamos por Prob(E) la probabilidad del evento aleatorio E, por E(X) la esperanza de la variable aleatoria X y por Var(X) la varianza de la variable X. Ver el ap´endice A.

CAP´ıTULO 1

Los divisores primos 1.1.

La esperanza

Definici´ on de esperanza. Ejemplos. Recordemos que, si se tiene una variable aleatoria X que toma los valores x1 , x2 , . . . , xn con probabilidades p1 , p2 , . . . , pn , donde p1 + p2 + . . . + pn = 1, entonces la esperanza se define como la cantidad n X pi xi . i=1

As´ı, por ejemplo, si X es el valor que da un dado arrojado al aire,   1 con probabilidad 1/6      con probabilidad 1/6 2 X= 3 con probabilidad 1/6    ... ...    6 con probabilidad 1/6

y por lo tanto

E(X) =

n X

pi xi =

i=1

Si X es un dado trucado, muy bien   1 X = 2, 3, . . . , 5   6 y entonces

E(X) =

X i

pi xi =

1 1 1 7 · 1 + · 2 + ... + · 6 = . 6 6 6 2

podr´ıa tener la distribuci´on con probabilidad 1/18 con probabilidad 1/9 en cada caso con probabilidad 1/2

1 1 1 1 83 · 1 + · 2 + ... + · 5 + · 6 = . 18 9 9 2 18

Esperanza y sumas. Denotamos por E(X) la esperanza de una variable aleatoria X. Sean X1 , X2 , . . . , Xn variables aleatorias. Es f´acil ver que (1.1.1)

E(X1 + . . . + Xn ) = E(X1 ) + . . . + E(Xn ).

Aplicaci´ on 1. Denotemos por τ (n) el n´ umero de divisores de un entero n. Cu´ anto es τ (n), en promedio? Para que nuestra pregunta tenga sentido, debemos decir como estamos escogiendo n. Fijemos un entero N . Tomamos n al azar entre 1 y N , con la distribuci´on uniforme. Estamos preguntando cu´ al es el valor de E(τ (n)). 1

2

1. LOS DIVISORES PRIMOS

Para todo entero m, definimos (1.1.2)

Xm

( 0 si m ∤ n, = 1 si m|n.

(Formalmente, lo que tenemos es una variable aleatoria X que toma valores n entre 1 y N con la distribuci´ on uniforme, y varias variables aleatorias Xm que dependen de X.) Ahora bien, X Xm = τ (n). P Est´a claro que lo que queremos calcular es E( Xm ). Ya sabemos (1.1.1) que ! X X E(Xm ). Xm = E m

m

Ahora bien, cu´ al es el valor de E(Xm )? Calculamos: (1.1.3)       1 N 1 1 1 N 1 X 1= + O(1) = +O = . E(Xm ) = Prob(Xm = 1) = N N m N m m N n≤N m|n

(Aqu´ı, como de ahora en adelante, O(1) quiere decir “una cantidad x tal que |x| ≤ C para alguna constante C” y O(1/N ) quiere decir “una cantidad x tal que |x| ≤ C/N ”. La ecuaci´ on ⌊N/m⌋ = N/m + O(1) nos est´ a diciendo simplemente que el valor absoluto de la diferencia entre ⌊N/m⌋ y N/m es siempre menor que una constante – en verdad, menor que 1.) Por lo tanto ! X 1 X X 1 X + O = log N + O(1). E(Xm ) = Xm = E m N m m m≤N

m≤N

concluimos que E(τ (n)) = log N + O(1).

(1.1.4)

Aplicaci´ on 2. Sea ω(n) el n´ umero de divisores primos de n. Cu´ anto es ω(n), en promedio? Calculemos:   X X X 1 X 1 E(ω(n)) = E  + O Xp  = . E(Xp ) = p N p≤N

p≤N

p≤N

p≤N

Ahora bien (1.1.5)

X1 = log log N + O(1) p

p≤N

(teorema de Chebyshev-Mertens, 1875; ver los ejercicios). Por lo tanto (1.1.6)

E(ω(n)) = log log N + O(1).

1.1. LA ESPERANZA

3

Aplicaci´ on 3. Cu´ antos factores primos de un tama˜ no dado tiene un n´ umero tomado al azar? Precisemos el rango. Sean dados δ0 , δ1 tales que 0 ≤ δ0 < δ1 < 1. Tomemos n entre 1 y N bajo la distribuci´ on uniforme. Queremos saber la esperanza E(Y ) del n´ umero Y de factores primos de n entre N δ0 y N δ1 . Calculemos:      X X 1 1 +O E(Y ) = E  Xp  = p N δ δ δ δ N

0 0) de manera m´ as precisa. Desigualdad de Markov. Sea X una variable aleatoria que toma siempre valores no negativos. Sea t ≥ E(X). Entonces (1.1.7)

Prob(X ≥ t) ≤

E(X) t

(desigualdad de Markov).

Esto tiene sentido: si, en promedio, cae 1 cm de lluvia al d´ıa, la probabilidad que caigan m´ as de 10 cm no puede ser m´ as de 0,1. (Por otra parte, dado que cae 1 cm de lluvia al d´ıa en promedio, la probabilidad que caigan 0 cm puede ser tan cercana a 1 como se quiera: muy bien podr´ıan haber cien a˜ nos de sequ´ıa y un d´ıa de diluvio. Esto nos muestra que una desigualdad tan general como la de Markov puede valer solo para la cola superior de la distribuci´ on, no para la cola inferior.) La prueba es sencilla: por la definici´on de la esperanza, tenemos E(X) ≥ 0 · Prob(X < t) + t · Prob(X ≥ t) = t · Prob(X ≥ t), y por lo tanto Prob(X ≥ t) ≤

E(X) . t

Aplicaciones. Obtenemos de manera inmediata que

(1.1.8)

log N + O(1) , t log log N + O(1) . Prob(ω(n) ≥ t) ≤ t Prob(τ (n) ≥ t) ≤

4

1. LOS DIVISORES PRIMOS

Podemos mejorar la segunda cota en (1.1.8) de la manera siguiente. Es f´acil ver que τ (n) ≥ 2ω(n) . Luego Prob(ω(n) ≥ t) ≤ Prob(τ (n) ≥ 2t ) ≤

(1.1.9)

log N + O(1) . 2t

Qu´e tan mejor es esto que la segunda l´ınea de (1.1.8)? Consideremos t = (1 + ǫ) log 2 log N . 2+o(1) , mientras que (1.1.9) nos da Entonces (1.1.8) nos da Prob(ω(n) ≥ t) ≤ log 1+ǫ Prob(ω(n) ≥ t) ≤

1 + o(1) , (log N )ǫ

lo cual es una cota mucho m´ as fuerte (es decir, baja). Por otra parte, si t est´ a entre log log N y log2 log N , la desigualdad (1.1.9) no nos da nada. Esto se debe al hecho que, si bien τ (n) = 2ω(n) gran parte del tiempo, E(τ (n)) = log N , mientras que E(ω(n)) = log log N ; en otras palabras, E(τ (n)) 6= 2E(ω(n)) . Las colas superiores de la distribuci´ on de ω(n) cobran gran efecto cuando ω(n) se pone en el exponente, al punto que afectan considerablemente la esperanza de E(τ (n)) (o la de E(2ω(n) ), la cual es del mismo orden de magnitud1). Tendremos la oportunidad de estimar las distribuciones de ω(n) y τ (n) con mayor precisi´on m´ as tarde. Notas y problemas 1. Sumas por partes. La siguiente t´ecnica es u ´til a menudo; la necesitaremos inmediatamente en la prueba de Chebyshev-Mertens y una y otra vez en el futuro. Digamos que tenemos que calcular N X

h(n),

n=1

donde h(n) = (f (n + 1) − f (n)) · g(n). Entonces N X

h(n) =

n=1

=

N X

(f (n + 1) − f (n)) · g(n) =

n=1 N +1 X n=2

f (n)g(n − 1) −

N X

N X

n=1

f (n + 1)g(n) −

N X

f (n)g(n)

n=1

f (n)g(n)

n=1

= (f (N + 1)g(N ) − f (1)g(1)) −

N X

n=2

f (n)(g(n) − g(n − 1)).

P Esta t´ecnica (sumar por partes) es u ´til cuando la suma N n=1 f (n)(g(n)−g(n−1)) PN es, por alg´ un motivo, m´ as facil de calcular que n=1 (f (n + 1) − f (n)) · g(n), o ya ha sido evaluada. 1 Es decir, es de tama˜ no comparable, qu´ıtese o p´ ongase un factor constante.

1.1. LA ESPERANZA

5

Se puede ver que el proceso es an´ alogo a la integraci´ on por partes. (Uno puede, incluso, ver a la sumaci´on por partes como un caso especial de la integraci´ on por partes, mediante el uso de una integral de Lebesgue.) 2. Probaremos el teorema de Chebyshev-Mertens (ecuaci´ on (1.1.5)). a) Todo n´ umero entero positivo puede ser expresado como un producto de primos de manera u ´nica2. En otras palabras, para todo entero positivo n, Y n= pvp (n) , p

(1.1.10)

donde vp (n) es el m´ aximo entero no negativo k tal que pk |n. Tome logaritmos a ambos lados y muestre que X log n = Λ(d), d|n

(1.1.11)

donde Λ(d) = log p si d es una potencia pα de un primo p, y Λ(d) = 0 si no es as´ı (funci´ on de von Mangoldt). b) Sea Xd como antes, es decir, la variableP aleatoria que toma el valor 1 cuando d|n y el valor 0 cuando d ∤ n. Sea Y = d|n Λ(d)Xd . Entonces, por (1.1.10), Y siempre toma el valor log n. Concluya que E(Y ) = log N + O(1).

c) Al mismo tiempo, tenemos que   X X 1 N , E(Y ) = Λ(d)E(Xd ) = Λ(d) · N d d≤N

d≤N

as´ı que

(1.1.12)

(1.1.13)

  1 N = log N + O(1). Λ(d) · N d d≤N
on de Como N1 ⌊ Nd ⌋ = 1d − O N1 , estamos a un paso de obtener una estimaci´ P Λ(d) d≤N d :   X Λ(d) X 1 = log N + O(1) + Λ(d) · O d N d≤N d≤N   X 1 ·O = log N + O(1) + Λ(d) . N X

d≤N

2Este hecho es a veces llamado el teorema fundamental de la aritm´ etica. Puede parecer extra˜ no que un enunciado tan familiar tenga un nombre tan grandilocuente; empero, el hecho que un enunciado nos sea sumamente natural no quiere decir que no deba ser probado, o que sea cierto. Hay an´ alogos del conjunto de enteros Z, los as´ı llamados anillos de enteros de los campos algebraicos; en la gran mayor´ıa de ellos, el teorema fundamental de la aritm´etica deja de ser cierto. (Si bien todo elemento a´ un se factoriza en elementos irreducibles, ya no lo hace de manera u ´ nica.) Tenemos, por ejemplo, las dos factorizaciones √ √ √ 6 = 2 · 3 = (1 + −5)(1 − −5) en el anillo de enteros del campo algebraico Q( −5).

6

1. LOS DIVISORES PRIMOS

P S´ olo nos falta acotar d≤N Λ(d). d) Por (1.1.12), tenemos   X 1 N = log N + O(1), Λ(d) · N d d≤N   X 1 N/2 N Λ(d) · + O(1) = log N/2 d 2 d≤N

y por lo tanto     X X N N Λ(d) ≤ −2 Λ(d) · d 2d N 2

≤d≤N

d≤N

= N (log N + O(1)) − N

(1.1.14)

para todo N . Por lo tanto, X X Λ(d) = Λ(d) + d≤N

N (1 + ǫ) log log N ) ≤ 2 ǫ log log N (1.2.9) 1 Prob(ω(n) < (1 − ǫ) log log N ) ≤ 2 + oǫ (1) ǫ log log N para todo ǫ > 0. Notas y problemas 1. Nuevamente nos planteamos la pregunta: cu´ antos primos hay entre 1 y N ? Tratemos de ver si podemos atacar el problema usando la varianza, antes que la esperanza. La idea central est´ a clara: los primos son algo que se desv´ıan de la norma, y podemos usar la desigualdad de Chebyshev (Teorema 1.1) para obtener una cota sobre la probabilidad de eventos que se desv´ıan de una norma. Podemos usar la desigualdad (1.2.7) (la cual hemos probado utilizando la desigualdad de Chebyshev) con x = log log n, y obtenemos Prob(ω(n) = 1) ≤

1 log log N + O(1) = . (log log N )2 + O(log log N ) log log N + O(1)

Por lo tanto, hay a lo m´ as log log N N +O(1) primos entre 1 y N . Esta es una cota sumamente d´ebil: la cota (1.1.18) era mucho mejor. Podemos utilizar la desigualdad de Chebyshev de otra manera para obtener una cota m´ as fuerte?

10

1. LOS DIVISORES PRIMOS

Veremos que es as´ı, y luego veremos que la gran ventaja de lo que haremos sobre lo que hicimos en las notas en la secci´ on anterior es que el que m´etodo que seguiremos ahora tambien sirve para obtener cotas sobre muchas cosas aparte del n´ umero de primos entre 1 y N . P Lo que estamos haciendo es evaluar la varianza de X = p Xp . Al hacer tal cosa, utilizamos el hecho que las variables Xp , p ≤ N 1/3 (digamos) son casi independientes en pares. Hay todav´ıa un hecho m´ as general que no estamos usando: para p1 < p2 < . . . < pk cualesquiera tales que p1 p2 · · · pk es bastante menor que N , las variables Xp1 , Xp2 , . . . , Xpk son mutuamente independientes, o casi. Qu´e podemos hacer con esto? a) Defina ( 1/p si p ∤ n, (1.2.10) Zp = −(1 − 1/p) si p|n,

(1.2.11)

donde n es un entero aleatorio entre 1 y N . Verifique que E(Zp ) = O(1/N ). b) Para todo d sin divisores cuadrados4, defina Y Zp . Zd = p|d

Verifique que E(Zd ) = O(τ (d)/N ). Ya sabemos que τ (d) es peque˜ no en promedio (ver (1.1.4)). Concluya que, si d1 , d2 son distintos y carecen de divisores cuadrados, (1.2.12)

E(Zd1 )E(Zd2 ) = N −2 · O(τ (d1 ))O(τ (d2 )),

E(Zd1 Zd2 ) = N −1 · O(τ (d1 d2 )) ≤ N −1 · O(τ (d1 ))O(τ (d2 )),

y por lo tanto (1.2.13)

(1.2.14)

E(Zd1 Zd2 ) = E(Zd1 )E(Zd2 ) + N −1 · O(τ (d1 ))O(τ (d2 )). P P c) Defina Z = ∗d≤M Zd , donde M = N 0,49 . (El asterisco ∗ en la suma ∗d≤M quiere decir que d recorre s´ olo a los enteros sin divisores cuadrados.) Podemos ver que (1.2.13) es una versi´ on aproximada de (1.2.2); es razonable tratar de obtener una versi´ on aproximada de (1.2.4) en consecuencia. Muestre que E(Z) = O(N −1/2 ), X∗ X∗ Var(Z) = Var(Zd ) + O(N −0,01 ) = E(Zd2 ) + O(N −0,01 ) d≤M

(1.2.15)

d≤M

 Q , donde φ(d) = d· p|d(1− 1/p) Muestre tambi´en que E(Zd2 ) = (funci´ on de Euler). Por consiguiente, X∗ φ(d)
Var(Z) = + O N −0,01 ≪ log M ≤ log N. 2 d φ(d) +O d2



τ (d) N

d≤M

4Es decir, d no divisible por 4, ni por 9, ni por 16, ni por 25, . . .

1.2. LA VARIANZA

11

d) Por la desigualdad de Chebyshev, (1.2.16)

(1.2.17)

2. (1.2.18)

(1.2.19)

Var(Z) . x2 Ahora bien, si el n´ umero n es primo y mayor que M , Q entonces, para cada d sin divisores cuadrados, la variable Zd tomar´ a el valor p|d 1/p = 1/d (por la definici´on de Zd ; ver (1.2.10) y (1.2.11)). Por lo tanto, si n es primo y mayor que M , P 1 X 1 X∗ 1 d≤M ≫ P 1d ≫ ≫ log M ≫ log N, Z= d d m m2 d≤M d≤M P donde utilizamos el hecho que la suma m m12 converge. Se infiere inmediatamente que Prob(|Z − E(Z)| ≥ x) ≤

Prob(n es primo y mayor que M ) ≤ Prob(|Z − E(Z)| ≥ x) P con x = ∗d≤M 1/d − E(Z) ≫ log N − O(N −1/2 ) ≫ log N . Por (1.2.15) y (1.2.16), concluimos que 1 Prob(n es primo y mayor que M ) ≪ , log N y por lo tanto 1 + Prob(n ≤ M ) Prob(n es primo) ≪ log N M 1 1 + ≪ = log N N log N para n tomado al azar entre 1 y N . En otras palabras, el n´ umero de primos entre 1 y N es ≪ logNN . ´ Esta es esencialmente la misma cota que ya obtuvimos en §1.1, Problema 2d . La ventaja del m´etodo presente reside en su suma flexibilidad: v´ease el problema siguiente. Procediendo como lo hicimos en el problema anterior, probaremos que 1 Prob(tanto n como n + 2 son primos) ≪ (log N )2 para n tomado al azar entre 1 y N . a) Comenzamos definiendo ( 2/p si p ∤ n y p ∤ n + 2, Zp = −(1 − 2/p) si p|n o p|n + 2, donde n es un entero aleatorio entre 1 y N , y Y Zd = Zp . p|d

De la misma manera que antes, se puede ver que E(Zd1 Zd2 ) y E(Zd1 )E(Zd2 ) son sumamente peque˜ nos para d1 , d2 distintos y sin divisores cuadrados.

12

1. LOS DIVISORES PRIMOS

P 1 b) Podr´ıamos definir, como antes, Z = ∗d≤M Zd , donde M = N 2 −ǫ . (El asteP risco ∗ en la suma d≤M denota que la suma recorre solo a los d sin divisores cuadrados.) PEsto podr´ıa dar resultados. Empero, tenemos el derecho de definir Z = ∗d≤M cd Zd , para cd ’s arbitrarios; hacemos esto, y afrontamos la tarea de encontrar los cd que nos den el mejor resultado. (Esta tarea de optimizaci´ on nos dar´ a una mejora cuantitativa, antes que cualitativa; podr´ıamos obtener (1.2.18) sin este paso. Por suerte, ciertos c´alculos finales nos ser´ an m´ as simples de esta manera que si escogieramos cd = 1.) Como antes, la idea es usar E(Z 2 ) , x2 donde x es el valor que Z toma cuando n y n + 2 son ambos primos. Muestre que, cuando n y n + 2 son ambos primos, X∗ τ (d) Z= . cd d Prob(|Z| ≥ x) ≤

d≤M

Muestre tambi´en que E(Z 2 ) =

X∗

d≤M

(1.2.20) =

X∗

d≤M





c2d E(Zd2 ) + O N −1 

X∗

d≤M

2 

|cd |τ (d)3  

  2   Y X∗ 2 τ (d) 1− + O N −1  |cd |τ (d)3   . c2d d p d≤M

p|d

c) Debemos, entonces, encontrar el m´ınimo de  X∗ Q  2 c2d τ (d) 1 − p|d d p d≤M

(1.2.21)

 

(1.2.22)

X∗

d≤M

2

 cd τ (d) d

La preguntas es: como escogemos cd de tal manera que (1.2.21) sea m´ınimo? O, m´ as bien: cu´ al es el m´ınimo valor tomado por (1.2.21)? Para ad , bd cualesquiera, !2 X X X ad bd ≤ a2d · b2d (desigualdad de Cauchy) d

d

d

con igualdad s´ olo cuando ~a y ~b son proporcionales, i.e., cuando hay alg´ un r tal que ad = rbd para todo dP(o ad = 0 para todo d). (Prueba de la desigualdad de Cauchy: tenemos d N 1/u . Diremos que n es u-desmenuzable si no tiene factores primos > N 1/u . Si n no tiene factores cuadrados, n ser´ a u-desmenuzable si y s´ olo si (1.2.25)

gcd(n, P (z)) > N. Q Q Como P (z) = p≤z p y n = p|n p son productos, y como preferimos trabajar con sumas, sacamos logaritmos en (1.2.25): log gcd(n, P (z)) > log N. ( 1 si p|n, Ahora bien, log gcd(n, P (z)) = p≤z (log p) · Xp , donde Xp = 0 si p ∤ n. Por lo tanto, nuestra tarea es acotar P

(1.2.26)

Prob(X > log N ), P

donde X = p≤z (log p) · Xp y n es tomado al azar entre N y 2N . b) Podemos acotar Prob(X > log N ) mediante Markov, o mediante Chebyshev, que no es sino Markov aplicado a X 2 , o a (X − E(X))2 ; de la misma manera, podemos acotar Prob(X > log N ) mediante la desigualdad de Markov aplicada a X k , para un k positivo de nuestra elecci´on. Para cualquier variable aleatoria X y cualquier n´ umero par k > 0 (o para cualquier n´ umero k > 0 y cualquier variable aleatoria X que tome s´ olo valores no negativos), (1.2.27)

Prob(X > t) ≤

E(X k ) . tk

Esto no es sino Markov aplicado a X k . Las desigualdades de Markov y Chebyshev son los casos k = 1 y k = 2 de (1.2.27). A la utilizaci´ on de (1.2.27) para k general se le llama acotaci´ on por momentos. (La expresi´ on k E(X ) es llamada un momento.) c) Usaremos (1.2.27) para estimar (1.2.26). Escogeremos k al final; no ser´ a una constante, sino una funci´on de N . Veamos: Prob(X > log N ) ≤

E(X k ) , (log N )k

16

1. LOS DIVISORES PRIMOS

P

donde X =



E(X k ) = E 

X

p1 ,...,pk ≤z

X

=

p1 ,...,pk ≤z

X

=

p1 ,...,pk ≤z

(1.2.28)

(1.2.29)

· Xp . Proseguimos:

p≤z (log p)



(log p1 ) · · · (log pk ) · Xp1 · · · Xpk 

(log p1 ) · · · (log pk ) · E (Xp1 · · · Xpk )

  (log p1 ) · · · (log pk ) · E Xp′1 · · · Xp′l ,

donde p′1 < . . . < p′l son los primos distintos entre p1 , . . . , pk . (Por ejemplo, si k = 4 y p1 = 3, p2 = 2, p3 = 7, p4 = 2, entonces l = 3 y p′1 = 2, p′2 = 3, p′3 = 7.) Sabemos que       2N N 1 2N 2 1 ′ ′ − ≤ ≤ , E(Xp1 . . . Xpl ) = N m m N m m

donde m = p′1 p′2 . . . p′l . (Esta puede parecer una cota muy mala, pero, en este 1 problema, es mejor para nuestra salud que ≤ m + N1 .) Concluimos que X 2(log p1 )(log p2 ) · · · (log pk ) E(X k ) = p′1 p′2 · · · p′l p1 ,...,pk ≤z

d) Para estimar la suma (1.2.29), tenemos que estimar cuantas veces los primos distintos p′1 < p′2 < · · · < p′l aparecen disfrazados de p1 , p2 , . . . , pk . Hay lk maneras de colorear k objetos con l colores. As´ı, E(X k ) ≤ 2

k X

X

lk

(log z)k−l

p′1 0 y todo k > 0. Entonces X1 , X2 , X3 , . . . convergen en distribuci´ on a X. La idea principal de la prueba es que los momentos de una distribuci´on X b determinan la serie de Taylor de X(t) alrededor de t = 0. La condici´ on E(X k ) < C k asegura que la serie de Taylor alrededor de t = 0 tenga radio de convergencia b y, por ende, determina X. Para ver una prueba infinito; as´ı, la serie determina X, completa, consultar, por ejemplo, [2, §30, Teoremas 30.1 y 30.2]. 1 |E(X k )| < C k se cumple para casi toda variable X “razonable”. La condici´ on k! He aqu´ı un ejemplo de un X para el cual la condici´ on no se cumple, y, m´ as a´ un, la conclusi´on del teorema no es cierta: sea X = eY , donde Y es una variable de distribuci´ on normal. 5. Las condiciones del teorema del l´ımite central se pueden relajar de varias formas. La siguiente es una de las formas m´ as comunes. Teorema 1.6 (Teorema del l´ımite central – Lindeberg). Sean X1 , X2 , X3 , . . . variables aleatorias mutuamente independientes. Sean v uX n X p u n Var(Xj ). (Xj − E(Xj )), sn = Var(Sn ) = t Sn = j=1

j=1

Supongamos que, para todo ǫ > 0, Z n X 1 (1.3.17) l´ım t2 fj (t)dt < ∞, n→∞ s2n |t|≥ǫsn

(condici´ on de Lindeberg)

j=1

donde fj es la funci´ on de densidad de Xj . Entonces Sn /sn tiende en distribuci´ on 2 /2 1 −t √ a la normal 2π e cuando n → ∞. Si Xj es discreta, entonces, claro est´ a, la condici´ on de Lindeberg se escribe n X 1 n→∞ s2n

l´ım

j=1

X

x:|x|≥ǫsn

x2 Prob(Xj = x) < ∞.

Esbozo de una prueba. Se procede como en la primera demostraci´on que dimos del teorema del l´ımite central. La condici´ on de Lindeberg sirve para mostrar que   n X 1 2 2 \ Xj /sn (t) − 1 − t Var(Xj )/sn = 0 l´ım n→∞ 2 j=1

1.3. EL L´IMITE CENTRAL

29

para todo t. Esto nos permite mostrar que n Y 1 2 2 \ + o(1) Sn /sn = 1 − t Var(Xj )/sn 2 j≤n Y 12 2 2 = e− 2 t Var(Xj )/sn + o(1) = e−t /2 + o(1), j≤n

que es lo que deseamos.



Para una prueba completa, ver [6, XV.6, Teorema 1]. La condici´ on de Lindeberg (1.3.17) es b´ asicamente necesaria ([6, XV.6, Teorema 2]). 6. Sea ( 1 si p2 |n Cp = 0 si p2 ∤ n, √ P donde n es tomado al azar entre 1 y N . Sea C = p≤N Cp . (Como, para p > N , P P no hay entero n ≤ N tal que p2 |n, tenemos que C = p Cp = p≤√N Cp .) En otras palabras, C es la variable aleatoria que da el n´ umero de cuadrados de primos que dividen un entero tomado al azar entre 1 y N . Estudiemos la distribuci´on de C. a) Muestre que E(C) =

X

√ p≤ N

Cp =

  X 1   X 1 −1/2 −1/2 + O N = + O N . 2 p2 √ p p

p≤ N

b) Muestre que Prob(C = 0) =

Y p

(1.3.18)

1 1− 2 p



  + O N −1/2 .

 Q  Por consiguiente, l´ımN →∞ Prob(C = 0) existe y es igual a p 1 − p12 . El evento C = 0 no es sino el evento que n carezca de divisores cuadrados (i.e. d2 ∤ n para todo entero d > 1). c) Muestre que, para todo k ≥ 0,      Y X∗ 1 1 · 1 − 2 + O (N/m)−1/2  Prob(C = k) = 2 p √ m p∤m

1≤m≤ N ω(m)=k

=

X∗

m≥1 ω(m)=k

  1 1 Y · 1 − + O(N −1/2 ), m2 p2 p∤m

30

1. LOS DIVISORES PRIMOS

P olo sobre enteros sin divisores cuadrados. Por donde ∗ denota una suma s´ lo tanto, l´ımN →∞ Prob(C = k) existe y es igual a  X∗ 1 Y  1 · . 1 − m2 p2 m≥1 ω(m)=k

p∤m

Tenemos, entonces, que C converge a una distribuci´on discreta cuando N → ∞. Esta distribuci´ on no es la normal (ya que es discreta) ni se le parece (no es sim´etrica alrededor de E(C): la probabilidad de C < 0 es cero, pero la probabilidad de C > 2E(C) tiende a un valor P positivo). LoPcrucial aqu´ı es que l´ımN →∞ E(C) < ∞, es decir, el hecho que p E(Xp ) = p p12 converge. P P En cambio, cuando examin´abamos X = p Xp , ten´ıamos que, como p p1 diverge, la esperanza E(X) tend´ıa a ∞ cuando N → ∞ y la distribuci´on l´ımite era la normal. d) Muestre que, para todo k,

donde λ = (1.3.19)

P

1 p p2 .

Prob(C = k) ≪

λk k!

La distribuci´on

λk −λ e k! es la famosa distribuci´ on de Poisson; se trata del l´ımite n → ∞ de la distribuci´ on de Yn = Yn,1 + . . . + Yn,n , donde {Yi,j }i,j≥1 son variables mutuamente independientes con la distribuci´on ( 1 con probabilidad λ/n Yn,j = 0 con probabilidad 1 − λ/n. (Demuestre que Yn tiende, en efecto, a (1.3.19).) Hemos, entonces, acotado la distribuci´on de C por una distribuci´on de Pois´ son de esperanza λ. Esta no es una cota “ajustada”: pruebe que Prob(C = k) ≪ǫ para todo ǫ > 0, y, en consecuencia, Prob(C = k) = o cuando k → ∞, e incluso Prob(C ≥ k) = o e) Sea

ǫk k!



λk k!



1 k!





.

( 1 si p|m y p|n Dp = 0 de lo contrario,

1.4. GRANDES DESVIACIONES: COTAS SUPERIORES. VALORES CR´ITICOS.

31

donde (m, n) es un par de n´ umeros entre P 1 y N tomados al azar de acuerdo a la distribuci´ on uniforme. Sea D = p Dp . Entonces el evento D = 0 no es sino el evento que m y n sean primos entre si. Muestre que  Y 1 Prob(D = 0) = 1 − 2 + O(N −1 ), p p  X∗ 1 Y  1 · 1 − 2 + O(N −1 ). Prob(D = k) = m2 p m≥1 ω(m)=k

p∤m

Compare esto con (1.3.18). Como en (6d ), concluya que   1 . Prob(D ≥ k) = o k! 1.4.

Grandes desviaciones: cotas superiores. Valores cr´ıticos.

Sean X1 , X2 , . . . variables aleatorias mutuamente independientes con la distribuci´on ( 0 con probabilidad 1/2 (1.4.1) Xj = 1 con probabilidad 1/2. P Sea X = j≤n Xj . Sabemos que E(X) = 12 n y que la distribuci´on de X ser´ a cercana a la 1 1 normal alrededor de 2 n. Qu´e pasa lejos de 2 n? En general, hablamos de p peque˜ nas desviaciones cuando la distancia entre el valor de X y la esperanza E(X) es O( Var(X)), y de grandes desviaciones cuando la distancia es comparable a Var(X) o E(X). Podemos preguntarnos, por ejemplo, que tan a menudo se dan las grandes desviaciones ω(n) < 21 log log n o ω(n) > 6 log log n. En el caso de las variables (1.4.1), podemos hacer los c´alculos a mano. Tenemos n
−n Prob(X = m) = 2 · m para todo m. Por lo tanto, X n Prob(Y > an) = 2−n m m≥an

para todo a, donde   n 1 · 2 · 3 · ···n n(n − 1) · · · (n − m + 1) n! = = := m (n − m)!m! (1 · 2 · · · · (n − m)) · (1 · 2 · · · · m) 1 · 2 · ···m

es el n´ umero de maneras de escoger m cosas de entre n cosas. (Tenemos n posibilidades para la primera cosa elegida, n−1 posibilidades para la segunda, . . . , n−m+1 posibilidades para la m–´esima, y no importa en qu´e orden de los m! ´ordenes posibles hayamos elegido maneras de escoger.) las m cosas. Por lo tanto, hay n(n−1)···(n−m+1) 1·2····m
n Fijemos un a ∈ [1/2, 1]. Como m 7→ m es decreciente para m ≥ 12 n, tenemos     n n (1.4.2) 2−n ≤ Prob(Y > an) ≤ (n + 1)2−n . ⌈an⌉ ⌈an⌉

32

1. LOS DIVISORES PRIMOS

Ahora bien, log n! = log 1 + log 2 + · · · + log n = as´ı que (1.4.3)

Z

n 1

log x dx + O(log n) = n log n − n + 1 + O(log n),

  n log = n log n − ((n − m) log(n − m) + m log m) + O(log n) m   m m m m · log 1 − + + O(log n). log = −n · 1 − n n n n

Por (1.4.2) y (1.4.3), para a ≥ 12 ,

2−n + O(log n) (aa (1 − a)(1−a) )n = n(−a log a − (1 − a) log(1 − a) − log 2) + O(log n).

log(Prob(Y > an)) ∼ log

En otras palabras, Prob(Y > an) = e(H+o(1))n , donde (1.4.4)

H = −a log

1−a a − (1 − a) log . 0,5 0,5

La forma de (1.4.4) puede resultar familiar para los f´ısicos (o qu´ımicos). Elaboraremos esta observaci´ on para m´ as adelante; ahora, pasemos a estudiar ω(n). *** ′ ′ ′ Sean X2 , X3 , X5 , . . . variables mutuamente independientes con la distribuci´on ( 1 con probabilidad p1 (1.4.5) Xp′ = 0 con probabilidad 1 − p1 . P anto Sea X ′ = p≤N Xp′ . La esperanza E(X ′ ) es log log N + O(1). Nos preguntaremos cu´ ′ ′ es la probabilidad Prob(X < a log log N ), a < 1, o Prob(X > a log log N ), a > 1. Markov acota las cotas mediante E(X ′ ), Chebyshev mediante E(X ′2 ); muy bien pode′ mos usar E(X ′k ), o incluso E(eX ). En efecto, para a positivo y α ≥ 0,   ′ E eαX (1.4.6) Prob(X ′ > a log log N ) ≤ α·a log log N , e y, para a positivo y α ≤ 0,   ′ E eαX (1.4.7) Prob(X ′ < a log log N ) ≤ α·a log log N . e As´ı como la desigualdad de Chebyshev es simplemente la desigualdad de Markov aplicada a la variable X ′2 , las desigualdades (1.4.6) y (1.4.7) son simplemente la desigualdad de ′ ametro α como Markov aplicada a la variable eαX ; tenemos la libertad de escoger el par´ m´ as nos convenga. (La aplicaci´ on de la desigualdad de Markov a una variable de la forma ′ eαX es a veces denominada el m´etodo de momentos exponenciales; los momentos “usuales” son E(X ′ ), E(X ′2 ), E(X ′3 ),. . . )

1.4. GRANDES DESVIACIONES: COTAS SUPERIORES. VALORES CR´ITICOS.

33

′

C´ omo evaluar E(eαX )? Tenemos ′

eαX = eα

P

p≤N

Xp′

=

Y

′

eαXp .

p≤N ′

′

′

Como X2′ , X3′ , X5′ , . . . son mutuamente independientes, las variables eαX2 , eαX3 , eαX5 , . . . tambi´en lo son, y por lo tanto    Y Y  ′ ′ ′ E(eαX ) = E  eαXp  = E eαXp . p≤N

Es f´acil calcular que

  1 ′ E eαXp = 1 + (eα − 1). p

En consecuencia, (1.4.8)

p≤N

α   Y Y 1 α 1 e −1 αX ′ = (1 + (e − 1)) ≪ E e 1+ . p p p≤N

p≤N

(Esto es cierto a´ un si α < 0, o incluso α = −∞. Demuestre la desigualdad en (1.4.8) Q si ´esta no lo convence de inmediato; use el hecho que p≤N (1 + 1/p2 ) ≪ 1, puesto que Q 2 e?).) Ahora bien, p (1 + 1/p ) converge (por qu´  P P Y 1 1 1 p≤N p ≪ e p≤N p , ≪ 1+ (1.4.9) e p p≤N P y, como p≤N p1 = log log N + O(1) (Chebyshev-Mertens (1.1.17)), obtenemos que eα −1    α ′ = (log N )e −1 . (1.4.10) E eαX ≪α elog log N Podemos ahora sustituir (1.4.10) en (1.4.6) y (1.4.7). Nos queda escojer el valor ´optimo de α. Para a > 1 y α > 0, α

(log N )e −1 α Prob(X > a log log N ) ≪α α·a log log N = (log N )e −1−αa ; e para a < 1 y α < 0, ′

α

α (log N )e −1 = (log N )e −1−αa . eα·a log log N Debemos minimizar eα − 1 − αa para a positivo y fijo, cuid´ andonos que α sea negativo si a > 1, y positivo si a < 1. Sacando derivadas, vemos que eα − 1 − αa es m´ınimo para a dado cuando α = log a. Entonces

Prob(X ′ < a log log N ) ≪α

(1.4.11)

Prob(X ′ > a log log N ) ≪a (log N )−(a log a+1−a) para a > 1,

Prob(X ′ < a log log N ) ≪a (log N )−(a log a+1−a) para a < 1.

Hemos obtenido las cotas superiores que dese´ abamos para las grandes desviaciones de X ′ = P ′ ′ ıcitas en (1.4.11) dependen p≤N Xp , donde Xp es como en (1.4.5). Las constantes impl´ de a, pero de manera continua; por lo tanto, la misma constante puede servir para todo

34

1. LOS DIVISORES PRIMOS

a ≤ A, A dado. (La constantes impl´ıcitas en (1.4.11) dependen de manera continua de eα − 1 = elog a − 1 = a − 1, por lo cual la dependencia en a es continua a´ un cerca de a = 0.) ***

Como de costumbre, pasamos a examinar las variables X2 , X3 , X5 , . . . dadas por ( 1 si p|n, Xp = 0 si p ∤ n, donde n es tomado al azar entre 1 y N con la distribuci´on uniforme. Sea X = ω(n) = P un v´alidas; partamos de ellas. p≤N Xp . Las desigualdades (1.4.6) y (1.4.7) son a´ P Q El problema es evaluar E(eαX ) = E(eαω(n) ). Si bien eαX = eα p≤N Xp = p≤N eαXp ,  Q  P
no podemos concluir que E(eαX ) = E eα p≤N Xp = p≤N E eαXp , ya que las variables Xp no son mutuamente independientes. Empero, podemos mostrar sin mucha dificultad que   α X eαω(n) Y Y 1 1 e α α 1 ≤ 1+e + 2 + ... ≪ 1+ ≪ (log N )e n p p p n≤N

p≤N

p≤N

(por (1.4.9)) y deducir con m´ as trabajo de esto que X α eαω(n) ≪ N (log N )e −1 n≤N

(ver problema 1). Por lo tanto, E(eαω(n) ) ≪ (log N )e concluimos (por (1.4.6) y (1.4.7)) que (1.4.12)

α −1

. Fijamos α = log a como antes, y

Prob(ω(n) > a log log N ) ≪a (log N )−(a log a+1−a)

Prob(ω(n) < a log log N ) ≪a (log N )−(a log a+1−a)

si a > 1, si a < 1.

Las constantes impl´ıcitas en (1.4.12) dependen de a de manera continua – a´ un en la vecindad de a = 0. *** Tanto (1.4.11) como (1.4.12) son cotas superiores. Encontraremos dentro de poco cotas inferiores muy cercanas a estas cotas superiores; mientras tanto, content´emonos con una aplicaci´ on de (1.4.12). Cu´ antos enteros n entre 1 y N 2 pueden expresarse como el producto n = a · b de dos enteros a, b entre 1 y N ? En otras palabras: si escribimos una tabla de multiplicaci´ on de 1000 por 1000 (digamos), habr´a un mill´ on de n´ umeros en la tabla, y todos estos n´ umeros estar´ an entre 1 y un mill´ on; empero, como hay muchas repeticiones, podemos preguntarnos: cu´ antos de los n´ umeros entre 1 y un mill´ on est´ an presentes en la tabla? Este es el conocido problema de la tabla de multiplicaci´ on. Lo encontramos por primera vez en §1.2, ejercicio 4, donde probamos que el n´ umero de enteros n ≤ N 2 que aparecen en la tabla (i.e., n = a · b para alg´ un par 1 ≤ a, b ≤ N ) es o(N 2 ). Ahora estableceremos una cota superior bastante m´ as ajustada.

1.4. GRANDES DESVIACIONES: COTAS SUPERIORES. VALORES CR´ITICOS.

35

Comenzamos de la misma manera que antes: tomamos conciencia de que, si bien la esperanza de ω(n) (para n tomado al azar) es E(ω(n)) = log log N 2 + O(1) = log log N + O(1), la esperanza de ω(a · b) (para a, b tomados al azar) es E(ω(a·b)) = E(ω(a)+ω(b)−ω(mcd(a, b))) = E(ω(a))+E(ω(b))−O(1) = 2 log log N +O(1). Por lo tanto, el n´ umero de divisores ω(n) de todo n´ umero n = a·b (n ≤ N 2 , a, b ≤ N ) debe estar ya sea en la cola de la distribuci´on de ω(n) o en la cola de la distribuci´on de ω(a · b). Ahora que sabemos como acotar las colas distantes (es decir, las grandes desviaciones) de P ω(n) = X = p Xp , podremos dar una buena cota superior para la (poca) probabilidad de ω(n) dentro de una u otra distribuci´on. Estamos en una situaci´ on que ya es propia no s´ olo de las probabilidades, sino de la estad´ıstica. La situaci´ on es as´ı: hay una variable aleatoria observable U ; su distribuci´on se desconoce, pero se tienen dos conjeturas acerca de ´esta. Hablemos, entonces, de la distribuci´ on 1 y la distribuci´ on 2. La esperanza E1 (U ) de U seg´ un la distribuci´on 1 es (digamos) u1 , mientras que la esperanza E2 (U ) de U seg´ un la distribuci´on 2 es u2 > u1 . La tarea es determinar cu´ al de las dos distribuciones es m´ as veros´ımil. Debemos ponernos de acuerdo en un valor cr´ıtico t entre u1 y u2 . Si, despues de n mediciones de U , vemos que el promedio X = n1 (U1 + U2 + . . . + Un ) es menor que t, decidiremos la disputa en favor de la distribuci´on 1; si X ≥ t, daremos la raz´ on a 2. La pregunta es: que valor cr´ıtico t debemos escoger? Si la distribuci´ on 1 es la verdadera distribuci´on de U , la probabilidad de decidir la disputa err´ oneamente a favor de la distribuci´on 2 es Prob1 (X ≥ t) (donde Prob1 (. . . ) denota la probabilidad de un evento si se asume que la distribuci´on 1 es la cierta). Si la distribuci´ on 2 es la cierta, la probabilidad de errar a favor de la distribuci´on 1 es Prob2 (X < t) (donde Prob2 (. . . ) denota la probabilidad de un evento si se asume que la distribuci´ on 2 es la cierta). Resulta sensato, entonces, escoger el valor de t entre u1 y u2 para el cual Prob1 (X ≥ t) + Prob2 (X < t) sea m´ınimo. En el caso del problema de la tabla de multiplicaci´ on, estamos ante una situaci´ on parecida. Fijaremos un t entre 1 y 2. Para todo n = a · b, a, b ≤ N , tendremos ya sea ω(n) < t log log N o ω(n) ≥ t log log N . En el primer caso, cualquier par a, b ≤ N tal que n = a · b tendr´a que estar en el conjunto {(a, b) : 1 ≤ a, b ≤ N, ω(a · b) < t log log N }, y el n´ umero de elementos de este conjunto es N 2 multiplicado por Prob(ω(a · b) < t log log N ), donde a y b son tomados al azar entre 1 y N con la distribuci´on uniforme. En el segundo caso – es decir, ω(n) ≥ t log log N – el n´ umero n estar´ a en el conjunto {n : 1 ≤ n ≤ N, ω(n) ≥ t log log N }, cuyo n´ umero de elementos es N 2 multiplicado por Prob(ω(n) ≥ t log log N ),

36

1. LOS DIVISORES PRIMOS

donde n es tomado al azar entre 1 y N 2 con la distribuci´on uniforme. Por lo tanto, el conjunto de enteros n ≤ N 2 tales que n = a · b para alg´ un par a, b ≤ N tiene a lo m´ as (1.4.13)

N 2 · (Prob(ω(n) ≥ t log log N ) + Prob(ω(a · b) < t log log N ))

elementos. Queremos, entonces, escoger t tal que (1.4.13) sea tan peque˜ no como se pueda. Para hacer esto, debemos primero estimar (1.4.13). Gracias a nuestra cota de grandes desviaciones (1.4.12), Prob(ω(n) ≥ t log log N ) = Prob(ω(n) ≥ t log log N 2 − t log 2) (1.4.14)

= Prob(ω(n) ≥ t(1 − o(1)) · log log N 2 )

≤ (log N )−I(t)(1+o(1)) ,

donde I(t) = t log t + 1 − t. Queda acotar Prob(ω(a · b) < t log log N ). Est´a claro que ω(a · b) = ω(a) + ω(b) − ω(mcd(a, b)).

Por §1.3, ejercicio 6e, la probabilidad que mcd(a, b) sea > ǫ log log N es ≪ (log N )−100 (o cualquier otra potencia que se quiera). (Hay varias maneras simples de evitar el uso del ejercicio 6e; la ventaja de este u ´ltimo es que nos permite continuar sin salir nunca de un marco probabil´ıstico.) Bastar´ a, entonces, con estimar la probabilidad que (ω(a), ω(b)) quede en un cuadrado Cta ,tb de lado ǫ log log N que contenga el punto (ta log log N, tb log log N ), donde ta + tb ≤ t + ǫ. El m´ aximo de tal probabilidad, multiplicado por el n´ umero de cuadrados a considerar (el cual es O(1/ǫ2 ) = Oǫ (1)), nos dar´ a una cota superior para la probabilidad de ω(a · b) ≤ t. Como a y b son variables independientes, la cota de grandes desviaciones (1.4.12) nos dice que la probabilidad que (ω(a), ω(b)) est´e dentro de Cta ,tb es ≪ (log N )−(I(ta )+I(tb ))+O(ǫ) , donde I(t) = t log t + 1 − t. Nos estamos preguntando, entonces, cu´ al es el m´ aximo de I(ta ) + I(tb ), bajo la condici´ on que ta + tb ≤ t. Sacamos la segunda derivada de I(x) y vemos que siempre es positiva. Por afica de x 7→ I(x) se curva hacia arriba,
lo tanto, la gr´ b . Como t est´ a entre 1 y 2, y I(x) es decreciente en el y, as´ı, 21 (I(ta ) + I(tb )) ≥ I ta +t 2 ta +tb
intervalo entre 1/2 y 2/2 = 1, vemos que I ≥ I(t/2+ǫ) = I(t/2)+O(ǫ). Concluimos 2 que (log N )−(I(ta )+I(tb ))+O(ǫ) ≤ (log N )−2I(t/2)+O(ǫ) .

Por lo tanto, (1.4.15) que

Prob(ω(a · b) ≤ t log log N ) ≤ (log N )−2I(t/2)+O(ǫ) .

Comparando (1.4.14) y (1.4.15), vemos que tenemos que escoger t ∈ [1, 2] de tal manera m´ın(I(t), 2I(t/2))

sea m´ aximo. Ahora bien, I(t) es creciente y 2I(t/2) es decreciente en el intervalo [1, 2]. Por lo tanto, el m´ aximo de m´ın(I(t), 2I(t/2)) se alcanza cuando I(t) = 2I(t/2). Resolvemos I(t) = 2I(t/2), y encontramos t = log1 2 . Hemos probado el siguiente resultado:

1.4. GRANDES DESVIACIONES: COTAS SUPERIORES. VALORES CR´ITICOS.

37

Teorema 1.7 (Erd˝os [3]). El n´ umero de enteros n entre 1 y N 2 que pueden ser expresados como el producto n = a · b de dos enteros a, b entre 1 y N es  “ ”  1 −I log +ǫ 2 2 Oǫ N · (log N ) para cualquier ǫ > 0, donde I(t) = t log t + 1 − t.   Num´ericamente, I log1 2 = 0,08607 . . . .

Notas y problemas

P

αω(n) , donde α > 0. Si se usan m´ 1. Debemos estimar etodos anal´ıticos – n≤N e que no trataremos para evitar el an´ alisis complejo – esto es rutina (dentro del m´etodo de Selberg–Delange – ver, e.g., [9, II.5]). Veremos como obtener de manera elemental una cota superior “del orden correcto” (es decir, ≪ la asint´otica verdadera). a) Primero deduzca de (1.1.5) que  Y 1 ≪ log N, 1+ p p≤N

(1.4.16)

Y

p≤N

b) Acotemos

(1.4.17)

P



≪ log N.

eαω(n) /n:   Y 1 1 1 ≤ 1 + eα + 2 + 3 + ... p p p p≤N e α Y α 1 1 ≪α (log N )e . ≤ 1 + + 2 + ... p p

n≤N

X eαω(n) n

n≤N

1 1 1 + + 2 + ... p p

p≤N

P P αω(n) α c) Podr´ıamos concluir que n≤N eαω(n) ≪ N n≤N e n ≪ N (log N )e , lo cual es correcto, pero esta cota se aleja de la realidad por un factor de (log N ) (como veremos despu´es). C´ omo obtendremos una mejor cota? P (Como dijimos, es rutina obtener la “suma parcial” n≤N eαω(n) a trav´es del an´alisis P αω(n) −s (no elemental) de la funci´ on L(s) = ∞ n . Estamos tratando de obtener n=1 e P P αω(n) meramente de la suma parcial n≤N eαω(n) n−1 , y la suma parcial n≤N e quiz´ as de un par de propiedades de eαω(n) .)

La convoluci´ on f ∗ g de dos funciones f, g : Z+ → C es (f ∗ g)(n) = P ıa anal´ıtica de n´ umeros, es conved|n f (d)g(n/d). A menudo, en la teor´ niente expresar una funci´on como la convoluci´ on de dos otras. Ya podemos obtener la suma parcial de h(n) = eαω(n) ∗ 1, donde 1 : Z+ → C es la funci´on

38

1. LOS DIVISORES PRIMOS

1(n) = 1: X X XX X 1 h(n) = eαω(d) · 1 = eαω(d) n≤N

(1.4.18)

n≤N d|n

≤

X

d≤N

eαω(d)

m≤N d|m

X eαω(d) α N =N ≪α N (log N )e . d d d≤N

d≤N

Ahora bien, queremos conocer la suma parcial de eαω(n) , no la de eαω(n) ∗ 1. d) Utilicemos el hecho que log = 1 ∗ Λ. (Esto no es sino (1.1.10).) Tenemos que X XX eαω(n) log(n) = eαω(n) Λ(n/d). n≤N

n≤N d|n

Ahora bien, ω(n) − 1 ≤ ω(d) ≤ ω(n) para todo n y todo d|n tales que Λ(n/d) 6= 0. As´ı, X XX eαω(n) log(n) ≪ eαω(d) Λ(n/d). n≤N

n≤N d|n

De (1.1.14) y (1.4.18), se deduce que X XX X eαω(d) Λ(n/d) = Λ(m) eαω(d) n≤N d|n

d≤N

≪ Por lo tanto,

X

n≤N

(1.4.19)

X

d≤N

m≤N/d

α

eαω(d) · N/d ≪α N (log N )e . α

eαω(n) log(n) ≪α N (log N )e .

Usando la t´ecnica de la suma por partes (§1.1, nota (1)), deduzca de esto que X α eαω(n) ≪α N (log N )e −1 . n≤N

La constante impl´ıcita en ≪ depende de α, tanto aqu´ı como antes. La dependencia es continua en α (o, si se prefiere, en β = eα ; la dependencia es continua a´ un en la vecindad de β = 0). 1.5.

Grandes desviaciones: cotas inferiores. Entrop´ıa.

Consideremos dos compartimientos separados por una membrana porosa. Llen´emoslos con un gas:

1.5. GRANDES DESVIACIONES: COTAS INFERIORES. ENTROP´IA.

39

De cu´ antas maneras puede ocurrir que haya m part´ıculas en el compartimiento de la izquierda y
n − m en el de la derecha?
n n n! maneras de escoger m part´ıculas de entre n; por lo tanto, hay m Hay m = m!(n−m)! maneras que haya m part´ıculas en la izquierda y n − m en la derecha. Como log n! = log 1 + log 2 + . . . + log n = n log n − n + O(log n),   n log = log n! − log m! − log(n − m)! m = n log n − m log m − (n − m) log(n − m) + O(log n) (1.5.1)   m m n−m n−m = −n · log + log + O(log n). n n n n Qu´e pasa si cada una de las 2n maneras de colocar n part´ıculas en dos compartimientos es igualmente probable? (Hay 2n maneras porque, dada cada part´ıcula, podemos elegir en cual de dos compartimientos puede encontrarse.) Obtenemos de (1.5.1) que la probabilidad que la proporci´ on de part´ıculas en el comportamiento izquierdo sea r = m n es n
log m = e−n(r log r+(1−r) log(1−r)+log 2)+O(log n) 2n = en(H(r)+o(1)) . donde

H(r) = −(r log r + (1 − r) log(1 − r) + log 2)   r 1−r = − r log + (1 − r) log . 0,5 0,5 La cantidad H(r) no es sino la famosa entrop´ıa. Comp´arese con (1.4.4). Claro est´ a, no hay raz´ on f´ısica por la cual podamos asumir que todas las disposiciones iniciales son igualmente probables; muy bien podemos comenzar llenando s´ olo uno de los compartimientos con gas. Empero, resulta poco sorprendente que, en la pr´ actica y con el paso del tiempo, el sistema tienda a las proporciones (r : 1 − r) que resultar´ıan m´ as probables si las 2n disposiciones fueran igualmente probables. Lo que hemos mostrado es que esto es lo mismo que decir que la entrop´ıa H(r) del sistema tiende a crecer. (Esta tendencia es muy clara, ya que H(r) est´ a en el exponente de en(H(r)+o(1)) ; por eso se habla, en la termodin´ amica, de una ley seg´ un la cual la entrop´ıa siempre crece.) *** Ahora que vemos que las expresiones del tipo r log r aparecen en un modelo de un fen´omeno natural, resulta sensato esperar que el hasta ahora curioso exponente de a log a+ 1 − a en (1.4.11) y (1.4.12) no sea simplemente una consecuencia de nuestra incapacidad. Nuestra tarea consiste ahora en dar cotas inferiores cercanas a las cotas superiores en (1.4.11) y (1.4.12), y de esta manera mostrar que el exponente a log a+1−a verdaderamente describe la probabilidad de las grandes desviaciones. Comenzemos, como de costumbre, examinando variables mutuamente independientes ′ on X2 , X3′ , . . . de distribuci´ ( 1 con probabilidad 1p ′ Xp = 0 con probabilidad 1 − p1 .

40

1. LOS DIVISORES PRIMOS

P Sea X ′ = p≤N Xp′ . Queremos dar cotas inferiores para Prob(X > a log log N ), a > 1, y Prob(X < a log log N ), a < 1. Utilizaremos el m´etodo del ladeo exponencial. Definimos nuevas variables Y2 , Y3 , Y5 , . . . mutuamente independientes y de distribuci´on   −1 1 con probabilidad a · 1 + a−1 p p     (1.5.2) Yp = 0 con probabilidad 1 − 1 · 1 + a−1 −1 . p p

(Est´a claro que estamos “ladeando” las variables hacia 1, pero donde est´ a la “exponencial”? −1  En Yp , la probabilidad 1/p se ha vuelto a/p = a1 ·(1/p)· 1 + a−1 ; la probabilidad 1−1/p p −1  . Si Xp tomara los valores 2, 3, · · · con probabilidades se ha vuelto a0 · (1/p) · 1 + a−1 p

no nulas, multiplicar´ıamos dichas probabilidades por a2 , a3 , · · · , respectivamente. El factor −1  de 1 + a−1 est´ a all´ı simplemente para asegurar que la suma de las probabilidades sea p 1.) P Sea Y = p≤N Yp . El evento Prob(Y > a log log N ) no es una gran desviaci´on, sino un evento probable. Por el teorema del l´ımite central, Z 1 p 2 1 √ e−x /2 dx + o(1) Prob(a log log N < Y ≤ a log log N + a log log N ) = 2π 0 (1.5.3) 1 ≥ + o(1), 5 √ (digamos). Sea I el intervalo (a log log N, a log log N + a log log N ]. Comparemos X Prob(X ′ > a log log N ) = Prob(Xp′ = xp ∀p ≤ N ) {xp }p≤N : xp ∈{0,1} P p≤N xp >a log log N

(1.5.4) =

y (1.5.5) Prob(Y ∈ I) =

=

Y

{xp }p≤N : xp ∈{0,1} p≤N P p≤N xp >a log log N

X

{xp }p≤N : xp ∈{0,1} P p≤N xp ∈I

(

a p

1 p

1−

1 p

si xp = 1 si xp = 0

  si xp = 1 Y a − 1 −1 · 1+ p si xp = 0 p≤N

Y

X

Prob(Xp′ = xp ∀p ≤ N ) ·

{xp }p≤N : xp ∈{0,1} P p≤N xp ∈I

(

Prob(Yp = xp ∀p ≤ N )

X

{xp }p≤N : xp ∈{0,1} p a log log N . Claro est´ a, en (1.5.5), el t´ermino Prob(Xp′ = xp ∀p ≤ N ) aparece con dos factores; uno de ellos es   Y Y a − 1 −1 1 −(a−1) 1+ 1+ ≪a ≪a (log N )−(a−1) , p p p≤N

p≤N

y el otro es

p≤N

xp ∈ I, sabemos que Y

P

p≤N

p≤N : xp =1

P

a=a

p≤N : xp =1

P

Como

Y

p≤N

xp

.

xp ≤ a log log N +

a ≤ aa log log N +

√

√ a log log N . Por ende,

a log log N

.

Concluimos que Prob(Y ∈ I) ≪a Prob(X > a log log N ) · aa log log N +

√

a log log N

Por lo tanto

Prob(X ′ > a log log N ) ≫a Prob(Y ∈ I) · a−(a log log N +

Como sabemos que Prob(Y ∈ I) > (1.5.6)

1 5

√

· (log N )−(a−1) .

a log log N )

· (log N )a−1 .

+ o(1) (por (1.5.3)), obtenemos

1 −(a log log N +√a log log N ) a · (log N )a−1 5 1/2 −1/2 ) ≫ (log N )−(a log a−a+1)−O((a log a)·(log log N )

Prob(X ′ > a log log N ) ≫a

para a > 1. Mediante exactamente el mismo m´etodo, podemos obtener (1.5.7)

1/2

Prob(X ′ < a log log N ) ≫a (log N )−(a log a−a+1)−O((a

log a)·(log log N )−1/2 )

.

para a < 1. Hemos obtenido, entonces, cotas inferiores para complementar a (1.4.11). La constante impl´ıcita en ≫ es continua en a. *** A´ un nos falta derivar cotas inferiores similares para las variables ( 1 si p|n Xp = 0 si p ∤ n. Veremos que hay un m´etodo muy general para ir de resultados sobre Xp′ a resultados sobre Xp . Ya pudimos haberlo utilizado para traducir las cotas superiores Prob(X ′ > a log log N ) ≪ . . . en cotas superiores Prob(X > a log log N ) ≪ . . . . Hemos esperado hasta ahora en parte porque el m´etodo depende de un resultado t´ecnico com´ unmente considerado dif´ıcil: el lema fundamental de la teor´ıa de cribas. (Ver el problema 1 al final de esta secci´ on; en ´este se desarrolla una prueba de una versi´ on d´ebil del lema fundamental – la u ´nica versi´ on que necesitaremos.)

42

1. LOS DIVISORES PRIMOS

P Como de costumbre, comenzaremos truncando las sumas. Definimos Sm = p≤m Xp , P y, en vez de trabajar con X = SN = p≤N Xp , trabajaremos con Sg(N ) , donde g(N ) es un poco menor que N . Acotaremos la diferencia X − Sg(N ) al final, ya que a estas alturas esa parte es rutinaria. Escogeremos g(N ) en el u ´ltimo paso. P ′ ′ . Debemos comparar S ′ = as precisamente, mostrar X Sea Sm g(N ) con Sg(N ) , o, m´ p≤m p que Prob(Sg(N ) > a log log N ) (o Prob(Sg(N ) < a log log N )) es aproximadamente igual a ′ ′ ′ Prob(Sg(N ) > a log log N ) (o con Prob(Sg(N ) < a log log N )). Ya tenemos cotas para Sg(N ) , ′ gracias a (1.5.6) y (1.5.7) (con X = Sg(N ) ). Tenemos, por una parte, (1.5.8)

Prob(Sg(N ) > a log log N ) =

X

Prob(Xp = xp ∀p ≤ g(N )),

X

Prob(Xp′ = xp ∀p ≤ g(N ))

{xp }p≤g(N) : xp ∈{0,1} P p≤g(N) xp >a log log N

y, por otra, ′ Prob(Sg(N ) > a log log N ) =

{xp }p≤g(N) : xp ∈{0,1} P p≤g(N) xp >a log log N

(1.5.9) =

X

Y

{xp }p≤g(N) : xp ∈{0,1} p≤g(N ) P p≤g(N) xp >a log log N

(

1 p

1−

1 p

si xp = 1 si xp = 0.

Q Consideraremos primero los t´erminos de (1.5.8) con p:xp =1 p ≤ N 1−ǫ . (Aqu´ı ǫ > 0 es un n´ umero fijo cualquiera entre 0 y 1.) Q Sea m = p:xp =1 p. Supongamos que m ≤ N 1−ǫ . Sea S = {p ≤ g(N ) : xp = 0}. Entonces 1 Prob(Xp = xp ∀p ≤ g(N )) = Prob(Xp = 0 ∀p ∈ S), m donde en el lado derecho de la ecuaci´ on las variables Xp dependen de un n´ umero n tomado al azar entre 1 y N/m, no entre 1 y N . Por el lema fundamental de las cribas (problema 1, teorema 1.8), Prob(Xp = 0 ∀p ∈ S) = =

Y

p∈S

Y

p∈S

1 1− p 1 1− p

 

· (1 + OA ((log N/m)−A )) · (1 + OA ((log N )−A ))

N/m ´ltimo ciertamente tiene para cualquier A, siempre y cuando log g(N ) ≪ loglog log(N/m) . Esto u   lugar si g(N ) = o logloglogNN (donde utilizamos el hecho que m ≤ N 1−ǫ ).

1.5. GRANDES DESVIACIONES: COTAS INFERIORES. ENTROP´IA.

Asumamos, entonces, g(N ) ≪ X

log N log log N .

{xp }p≤g(N) : xp ∈{0,1} P p≤g(N) xp >a log log N Q 1−ǫ p:xp =1 p ≤N

43

Podemos entonces concluir que

Prob(Xp = xp ∀p ≤ g(N ))

es igual a X

{xp }p≤g(N) : xp ∈{0,1} P p≤g(N) xp >a log log N Q 1−ǫ p:xp =1 p ≤N

Q

p:xp =1 p

lo cual no es sino (1 + OA ((log N )−A ) ·

Y 

1

p:xp =0

1 1− p

X

{xp }p≤g(N) : xp ∈{0,1} P p≤g(N) xp >a log log N Q 1−ǫ p:xp =1 p ≤N



· (1 + OA ((log N )−A )),

Prob(Xp′ = xp ∀p ≤ g(N )),

Q es decir, la suma de los t´erminos de (1.5.9) con p:xp =1 p ≤ N 1−ǫ , multiplicada por (1 + OA ((log N )−A )) . (Este es el paso crucial del m´etodo: hemos logrado ir de una suma que involucra a Prob(Xp = xp ∀p ≤ g(N )) a una suma que involucra a Prob(Xp′ = xp ∀p ≤ g(N )), donde las variables Xp′ son las variables mutuamente independientes que estudiamos al principio de la secci´ on.) Q Nos queda acotar los t´erminos de (1.5.8) y (1.5.9) con p:xp =1 p > N 1−ǫ . En un caso como el otro, el total de tales t´erminos es a lo m´ as X 1 Q , p∈Q p Q

Q⊂P 1−ǫ p∈Q p>N

donde P es el conjunto de los primos p ≤ g(N ). Por un resultado intermedio (1.5.20) en la prueba del lema fundamental de las cribas, X

Q⊂P 1−ǫ p∈Q p>N

Q

Q

1 p∈Q p



≪ (log g(N )) · log



N 1−ǫ g(N )

−

“ “ 1−ǫ ”” ·(1+o(1)) log N g(N)

para cualquier A > 0, donde utilizamos el hecho que log(N ) = o Concluimos que



log N log log N

≪A (log N )−A 

.

′ −A Prob(Sg(N ) > a log log N ) = Prob(Sg(N ) > a log log N ) + OA (log N )   para cualquier A > 0, bajo la condici´ on que g(N ) = o logloglogNN .

(1.5.10)




44

1. LOS DIVISORES PRIMOS

La desigualdad (1.5.6) puede aplicarse directamente a Sg(N ) : como la definici´on de las variables Xp′ no involucra a N , podemos simplemente utilizar g(N ) en vez de N . Obtenemos ′ −(a log a−a+1)+o(1) Prob(Sg(N . ) > a log log N ) ≫ (log g(N )) Si log log N − log log g(N ) = o(log log N ), entonces log g(N ) > (log N )1−o(1) . Por ende, ′ −(a log a−a+1)+o(1) Prob(Sg(N ) > a log log N ) ≫ (log N )

bajo la condici´ on que log log N − log log g(N ) = o(log log N ). La ecuaci´ on (1.5.10) nos permite deducir de esto que (1.5.11)

Prob(Sg(N ) > a log log N ) ≫ (log N )−(a log a−a+1)+o(1)

Empero, procederemos de manera distinta. Mostraremos que la probabilidad que X − Sg(N ) > ǫ′ log log N se satisfaga es muy peque˜ na – si es que g(N ) satisface una cierta condici´ on f´acil de cumplir. P Por Chebyshev-Mertens, g(N ) x) ≤ eαx para cualquier α. Si log log N − log log g(N ) + O(1) = o(x), podemos escoger α = A + 1 para A arbitariamente grande, y entonces (1.5.12) nos da que (1.5.13)

Prob(X − Sg(N ) > x) ≪A e−Ax

para N suficientemente grande. Escogemos x = ǫ′ log log N (con ǫ′ > 0 arbitrariamente peque˜ no) y A = A′ /ǫ′ (para A′ arbitrariamente grande). Concluimos que (1.5.14)

Prob(X − Sg(N ) > ǫ′ log log N ) ≪A′ (log N )−A

′

para N suficientemente grande, si se cumple la condici´ on que log log N − log log g(N ) = o(log log N ). Atemos los cabos. Por (1.5.11), ′ −(a log a−a+1)+o(1) (1.5.15) Prob(X > a log log N ) ≥ Prob(Sg(N ) > a log log N ) ≫ (log N )

para a > 1. Pasemos al caso a < 1. Por (1.5.11) y (1.5.14), ′ ′ Prob(X < a log log N ) ≥ Prob(Sg(N ) < (a − ǫ ) log log N )

− Prob(X − Sg(N ) > ǫ′ log log N ) ′

′

′

′

≫ (log N )−((a−ǫ ) log(a−ǫ )−(a−ǫ )+1)+o(1) − OA′ ,ǫ′ ((log N )−A )

para A′ arbitrariamente grande y ǫ′ > 0 arbitrariamente peque˜ no. Como t → t log t − t + 1 es continua, esto implica que (1.5.16)

Prob(X > a log log N ) ≫ (log N )−(a log a−a+1)+o(1) .

1.5. GRANDES DESVIACIONES: COTAS INFERIORES. ENTROP´IA.

45

- (a*log(a) - a + 1) 0

-0.5

-1

-1.5

-2 0

0.5

1

1.5

2

2.5

3

Figura 2. La distribuci´ on de ω(n), vista desde lejos, en escala logar´ıtmica. ´ Este es el gr´ afico de y = −I(x) = −(x log x − x + 1). La probabilidad de ω(n) > t log log N (si t > 1) o ω(n) < t log log N (si R ∞t < 1) es igual a (log N )−I(t)+o(1) , lo cual es lo mismo que (log N )o(1) · t (log N )−I(x) dx (si Rt t > 1) o (log N )o(1) · 0 (log N )−I(x) dx (si t < 1). Queda solamente verificar que existe un g(N ) que satisface las condiciones impuestas:   log N log g(N ) = o log log N y log log N − log log g(N ) = o(log log N ). La funci´on g(N ) = log N (log log N )2

(por ejemplo) satisface ambas condiciones. Hemos obtenido nuestro objetivo. Recordando (1.4.12) y X = ω(n), concluimos que

(log N )−(a log a+1−a)+o(1) ≪a Prob(ω(n) > a log log N ) ≪a (log N )−(a log a+1−a) si a > 1,

(log N )−(a log a+1−a)+o(1) ≪a Prob(ω(n) < a log log N ) ≪a (log N )−(a log a+1−a) si a < 1,

donde n es tomado al azar entre 1 y N . Las constantes dependen de a de manera continua. Notas y problemas 1. Lema fundamental de las cribas (versi´ on d´ebil). 1/s Sea z = N , donde s → ∞ cuando N → ∞. Sea P un conjunto de primos ≤ z. Queremos determinar cu´ antos enteros n ≤ N son coprimos con todo p ∈ P.

46

1. LOS DIVISORES PRIMOS

a) Cu´ antos enteros n ≤ N son impares? La respuesta es el n´ umero de enteros n ≤ N (es decir, N ) menos el n´ umero de enteros n ≤ N que son pares (es decir, ⌊N/2⌋). Muy bien – la respuesta es N − ⌊N/2⌋ = N/2 + O(1). Cu´ antos enteros n ≤ N son coprimos con 2 y 3? Tomamos los N enteros n ≤ N , restamos los ⌊N/2⌋ enteros divisibles por 2 y los ⌊N/3⌋ enteros divisibles por 3, y nos damos cuenta que hemos sustra´ıdo los enteros divisibles tanto por 2 como por 3 (es decir, divisibles por 6) por partida doble; tendremos que contarlos una vez de vuelta. Vemos, entonces, que el n´ umero de enteros n ≤ N coprimos con 2 y 3 es       N N N N N N − + + 3 · O(1) − + =N− N− 2 3 6 2 3 6    1 1 = 1− 1− N + O(1). 2 3

(1.5.17) X Q⊂P

Seguimos razonando de la misma manera (enfoque que tiene el nombre de principio de inclusi´ on-exclusi´ on) y concluimos que la probabilidad que un n ≤ N tomado al azar sea coprimo con todo p ∈ P es igual a |Q|

(−1)

X

Prob(n es divisible por todo p ∈ Q) = X

= Q

|Q|

(−1)

Q⊂P 1−ǫ p∈Q p≤N

1 N

$

Q

N p∈Q p

%

|Q|

(−1)

Q⊂P

+ Q

X

$

1 N

Q

N p∈Q p

|Q|

(−1)

Q⊂P 1−ǫ p∈Q p>N

1 N

$

%

Q

N p∈Q p

%

para cualquier ǫ > 0. Muestre que esto es  Y 1 1− + O(error) + O(N −ǫ ) + O(error), p p∈P

donde (1.5.18)

error = Q

X

Q⊂P p>N 1−ǫ

p∈Q

Q

1 p∈Q p

.

Habremos terminado una vez que acotemos este t´ermino de error, b) Podemos escribir (1.5.18) de la siguiente manera: (1.5.19)

error =

∞ X k=0

P∗

X∗

N 1−ǫ 2k 3A logloglogloglogNN . Si s ≫ log log N , el error ser´ a ≪A (log N )−A para todo A > 0. d) Hemos probado

(1.5.21)

Teorema 1.8 (Lema fundamental de las cribas, version d´ebil). Sea z = N 1/s , donde s ≫ log log N . Sea P un subconjunto de {p ≤ z : p primo}. Entonces, para n tomado al azar entre 1 y N ,  Y 1 Prob(n es coprimo con todo p ∈ P ) = (1 + o(1)) · 1− . p p∈P

(1.5.22)

Expl´ıcitamente, Prob(n es coprimo con todo p ∈ P )    Y 1 + O (log z) · s−(1−2ǫ)s·(1+o(1)) + O(N 1−ǫ ) = 1− p p∈P  Y 1 −A = (1 + OA ((log N ) )) · 1− p p∈P

para cualquier ǫ > 0 y cualquier A > 0.

Nota. La versi´ on fuerte del lema fundamental de las cribas consiste en la aseveraci´ on que (1.5.21) rige no s´ olo para s ≫ log log N , sino para todo s → ∞. No probaremos la versi´ on fuerte aqu´ı.

48

1. LOS DIVISORES PRIMOS

2. El lema fundamental es muy razonable: como la probabilidad que n sea coprimo con un p ∈ P dado es 1 − 1/p, la ecuaci´ on (1.5.21) nos dice (como muchas otras cosas que hemos probado) que los eventos p|n se comportan hasta cierto punto como variables mutuamente independientes. Empero, si z = N 1/s y s no va a ∞ cuando N → ∞, la ley (1.5.21) no rige. Mostremos esto en el caso m´ as simple. Si z = N 1/2 y P es el conjunto de todos los primos p ≤ P , entonces n es coprimo con todo p ∈ P s´ı y s´ olo s´ı n es primo. La probabilidad que n sea primo es (1 + o(1)) ·

(1.5.23)

1 log N

(este es el teorema de los n´ umeros primos, el cual no probaremos). La aseveraci´ on   Q 1 (1.5.21) nos dar´ıa, de otro lado, (1 + o(1)) · p≤N 1/2 1 − p . Se puede mostrar que  Y  2e−γ 1 (1 + o(1)), = (1.5.24) 1− p log N 1/2 p≤N

donde γ es la constante de Euler γ = 0,577 . . . . Lo importante aqu´ı es que 2e−γ 6= 1, por lo cual la predicci´on natural (1.5.24) no es compatible con la realidad (1.5.23). 3. Desviaciones moderadas. p p 1 Var(X) a) Si X − E(X) est´ a en la escala de Var(X) (es decir, entre 1000 p nas y 1000 Var(X), por ejemplo), hablamos del l´ımite central, o de peque˜ desviaciones. Si X − E(X) est´ a en la escala de Var(X) o E(X), hablamos de grandes desviaciones. A´ un nophemos examinado el caso en el cual X − E(X) es bastante m´ as grande que Var(X) y bastante m´ as peque˜ no que Var(X); como cabr´ıa esperar, esto se llama una desviaci´ on moderada. Lo que queremos examinar es Prob(X > (1 + ∆(N )) log log N ) y Prob(X < (1 − ∆(N )) log log N ),

donde ∆(N ) > 0, ∆(N ) = o(1) y (log log N )−1/2 = o(∆(N )). (Si ∆(N ) = o(1) no se cumpliera, tendr´ıamos una gran desviaci´on; si (log log N )−1/2 = o(∆(N )) no se cumpliera, tendr´ıamos una peque˜ na desviaci´on.) b) Las cotas superiores de grandes desviaciones son a´ un v´alidas, como podemos ver repasando sus pruebas. Por lo tanto: Prob(X > (1 + ∆(N )) log log N ) ≤ (log N )−I(1+∆(N )) , donde I(a) = a log a − a + 1. Mediante una serie de Taylor, verifique que I(1 + ∆(N )) =

1 1 2 ∆ (N ) + O(∆3 (N )) = ∆2 (N ) · (1 + o(1)). 2 2

Concluimos que 1

Prob(X > (1 + ∆(N )) log log N ) ≤ (log N )− 2 ∆

2 (N )·(1+o(1))

,

1.5. GRANDES DESVIACIONES: COTAS INFERIORES. ENTROP´IA.

49

y, similarmente, 1

Prob(X < (1 − ∆(N )) log log N ) ≤ (log N )− 2 ∆

2 (N )·(1+o(1))

.

c) Las cotas inferiores tendr´an que ser rehechas con m´ as cuidado: el sumando de o(1) en el exponente de (1.5.15) y (1.5.16) es ahora demasiado burdo, ya que −(a log a + 1 − a) ser´ a bastante m´ as peque˜ no que o(1). Las cotas (1.5.6) y (1.5.7) son a´ un v´alidas. Muestre que, como estamos asumiendo (log log N )−1/2 = o(∆(N )), las cotas (1.5.6) y (1.5.7) toman la forma (1.5.25)

1

2 (N )·(1+o(1))

1

2 (N )·(1+o(1))

Prob(X ′ > (1 + ∆(N )) log log N ) ≫ (log N )− 2 ∆

Prob(X ′ < (1 − ∆(N )) log log N ) ≫ (log N )− 2 ∆

.

d) La transici´on de X ′ a X se hace como antes. La u ´nica dificultad reside en el hecho que ya no basta probar que Prob(X − Sg(N ) > ǫ′ log log N ) es peque˜ na; ′ debemos asegurarnos que Prob(X − Sg(N ) > ǫ ∆(N ) log log N ) sea peque˜ na. Para esto tendremos que modificar el valor de g(N ). Sustituya x = ǫ′ ∆(N ) log log N y A = 1/ǫ en (1.5.13) y obtenga (1.5.26)

Prob(X − Sg(N ) > ǫ′ ∆(N ) log log N ) ≤ (log N )−∆(N ) ,

bajo la suposici´ on que log log N − log log g(N ) + O(1) = o(∆(N ) log log N ). Como 12 ∆2 (N ) = o(∆(N )), el t´ermino de error (1.5.26) es mucho m´ as chico − 12 ∆2 (N )(1+o(1)) . que el t´ermino principal (log N ) e) Muestre que se puede definir g(N ) de tal manera que   log N y log log N − log log g(N ) = o(∆(N ) log log N ). log g(N ) = o log log N √ Recuerde que ∆(N ) ≫ log log N .) Concluya que (1.5.27)

1

2 (N )·(1+o(1))

1

2 (N )·(1+o(1))

Prob(X ′ > (1 + ∆(N )) log log N ) ≪ (log N )− 2 ∆

Prob(X ′ < (1 − ∆(N )) log log N ) ≪ (log N )− 2 ∆

.

1/2 f ) Podemos escribir √ t = ∆(N )·(log log N ) . (La desviaci´on es entonces ∆(N )· (log log N ) = t log log N .) Est´a claro que 1

(log N )− 2 ∆

2 (N )·(1+o(1))

1 2 (1+o(1))

= e− 2 t

As´ı, (1.5.25) y (1.5.27) nos dicen que la normal nos da, por lo menos, una idea aproximada de la escala de la probabilidad de las desviaciones moderadas. 4. Podemos utilizar el lema fundamental (a´ un en su versi´ on debil) para dar una prueba alternativa del teorema de Erd˝os-Kac (teorema 1.3). (Lo siguiente est´ a muy cercano del camino seguido originalmente por Erd˝os y Kac mismos.) Sea
√ g(x) una funci´ on tal que g(x) = O x1/ log log x y log log x − log log g(x) = o( log log N ); podemos tomar g(x) = x1/ log log x , como en la primera prueba que dimos del teorema.

50

1. LOS DIVISORES PRIMOS

Proc´edase como en esa prueba hasta (1.3.13), i.e., muestre que podemos trabajar con la suma truncada X 1 · (Xp − 1/p). Sg(N ) = p log log g(N ) p≤g(N )

Podemos luego utilizar el lema fundamental en la misma manera que lo usamos en esta secci´ on, y as´ı mostrar que ′ Prob(Sg(N ) ≤ t) = Prob(Sg(N ) ≤ t) + o(1)

′ ′ para todo t, donde Sg(N ) es la suma de variables mutuamente independientes Xp : ′ Sg(N ) = p

1 log log g(N )

·

X

p≤g(N )

(Xp′ − 1/p).

′ En otras palabras, Sg(N ) tiende a la misma distribuci´on que Sg(N ) – es decir, tiende a la normal. 5. Entrop´ıa relativa. Consideremos tres compartimientos separados por membranas porosas. Llen´emoslos de gas. Sea pj la probabilidad que una part´ıcula dada (todas son intercambiables) est´e en el compartimiento j:

p1 p2 p3 Cu´ al es la probabilidad que haya n1 = r1 · n part´ıculas en el primer compartimiento, n2 = r2 · n en el segundo, y n3 = r3 · n en el tercero? La probabilidad de una configuraci´on espec´ıfica – es decir, la probabilidad que nj part´ıculas espec´ıficas est´en en el compartimiento j – es pn1 1 · pn2 2 · pn3 3 . El n´ umero de configuraciones con nj part´ıculas en la c´amara j es n! . n1 ! · n2 ! · n3 !

Luego, la probabilidad que haya nj = rj · n part´ıculas en el compartimiento j es P = pn1 1 pn2 2 pn3 3

n! . n1 ! · n2 ! · n3 !

1.5. GRANDES DESVIACIONES: COTAS INFERIORES. ENTROP´IA.

51

Cu´ anto es esto, aproximadamente? Como en el caso que vimos al principio de la secci´ on, extraemos el logaritmo: log P = n1 log p1 + n2 log p2 + n3 log p3 + n log n − n + O(log n)

− ((n1 log n1 − n1 ) + (n2 log n2 − n2 ) + (n3 log n3 − n3 ) + O(log n))   n2 /n n3 /n n1 /n + n2 log + n3 log + O(log n) = − n1 log p1 p2 p3   r2 r3 r1 + r2 log + r3 log + O(log n). = −n r1 log p1 p2 p3

Por lo tanto, P = e−n(H+o(1)) r1 p1

+ r2 log pr22 + r3 log pr33 . En general, definimos X rj H= rj log (entrop´ıa relativa) pj

donde H = r1 log

y tenemos que la probabilidad que una proporci´ on rj de las part´ıculas est´en en el comportamiento j es P = e−n(H+o(1)) . 6. La entrop´ıa relativa y los primos. Sea una partici´ on {los primos} = P1 ∪ P2 ∪ P3 tal que, para cada j = 1, 2, 3,   Y log z1 pj ≪ log z0

(P1 ∩ P2 = P1 ∩ P3 = P2 ∩ P3 = ∅)

p∈Pj z0 2, los n´ umeros n y m no pueden ser ambos primos, lo cual ser´ıa una posibilidad si estuvieramos hablando de variables independientes. En todo el texto, obedecimos a una restricci´on autoimpuesta: nos abstuvimos de usar teor´ıa de la medida y an´ alisis complejo. Para proseguir en el estudio de la teor´ıa probabil´ıstica de n´ umeros, es necesario usar los dos. El an´ alisis complejo es sumamente u ´til para el estudio de los primos. Toda la teor´ıa anal´ıtica de n´ umeros depende del an´ alisis; se trata de un caso cl´ asico de c´ omo el estudio de lo continuo puede ayudar Pen el estudio de lo discreto. La idea principal es que, para estudiar sumas finitas, como n≤N Λ(n), N P variable, debemos estudiar sumas infinitas n Λ(n)n−s , s variable. Estas sumas infinitas se tratan como funciones complejas de s, generalmente anal´ıticas o merom´orficas. La teor´ıa de la medida se considera hoy en d´ıa como necesaria para desarrollar la teor´ıa de probabilidades sobre una base rigurosa. Si se profundiza en el estudio de la teor´ıa probabil´ıstica de n´ umeros sobre una base puramente intuitiva, se llega f´acilmente al punto donde el lenguaje mismo falta. Veamos, por ejemplo, el caso de las caminatas aleatorias. Tomemos un n´ umero n al azar. Consideremos los primos p = 2, 3, 5, . . . en orden. En cada paso, si p divide n, damos un paso a la derecha; si p no divide n, damos un paso mucho m´ as corto a la izquierda. Billingsley [1] prob´o que la caminata que resulta tiende en distribuci´ on al mismo l´ımite que una caminata aleatoria, es decir, el movimiento Browniano. Ahora bien, qu´e quiere decir que una caminata “tiende” a un cierto tipo de crecimiento en distribuci´ on? No se trata simplemente de una sucesi´on de n´ umeros que convergen a otro n´ umero. Resulta dif´ıcil formular el resultado – ni que decir de su prueba – sin la teor´ıa de la medida. Hay dos desarrollos recientes notables. En primer lugar, la teor´ıa de cribas ha probado ser m´ as flexible y potente de lo que se cre´ıa hasta ahora, si se suplementa con otros m´etodos; est´ an all´ı resultados inesperados en la teor´ıa anal´ıtica de n´ umeros obtenidos por Friedlander-Iwaniec, Goldston-Pintz-Yildirim, y otros. En segundo lugar, la teor´ıa 59

60

B. COMENTARIOS FINALES

erg´ odica no s´ olo esta iluminando la teor´ıa de n´ umeros – inclu´ıdo el estudio de los primos – sino que esta haciendo posibles pruebas de resultados que no se cre´ıan anteriormente accesibles. Un ejemplo muy reciente e impresionante es el teorema de Green y Tao sobre los n´ umeros primos en progresiones aritm´eticas; no es que su prueba establezca propiedades sumamente delicadas de los n´ umeros primos, sino m´ as bien que muestra que algunas leyes muy precisas no son delicadas, al punto que deben regir para todo subconjunto de los enteros con ciertas propiedades generales – propiedades que los primos satisfacen. Toda la teor´ıa erg´ odica esta basada sobre la teor´ıa de la medida, y ser´ıa imposible comenzar el estudio de la primera sin utilizar la segunda. La bibliograf´ıa tiene como fin ser u ´til antes que completa. El libro de Tenenbaum [9] es una introducci´ on est´ andar y detallada al tema, con mucho m´ as an´ alisis que la presente monograf´ıa. El libro de Iwaniec y Kowalski [8] se ha vuelto la obra can´ onica de la teor´ıa anal´ıtica de n´ umeros para la ´epoca actual. Feller [6] es un texto cl´asico de probabilidades del cual generaciones se han beneficiado. Todos los art´ıculos citados est´ an entre los esenciales sobre el tema; la mayor parte de ellos son de lectura razonablemente accesible.

Bibliograf´ıa [1] P. Billingsley, Prime numbers and Brownian motion, Amer. Math. Monthly, 80 (1973), 1099–1115. [2] P. Billingsley, Probability and measure, 3rd ed., Wiley, 1995. [3] P. Erd˝ os, Una desigualdad asint´ otica en la teor´ıa de n´ umeros (en ruso), Vestnik Leningrad Univ. Mat. Mekh. i Astr 13 (1960), 41–49. [4] P. Erd˝ os and Mark Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Am. J. of Math. 62 No. 1/4, (1940), pp. 738-742. [5] G.H. Hardy y S. Ramanujan, The normal number of prime factors of a number, Quart. J. Math. 48 (1917), pp. 76-92. [6] W. Feller, An introduction to probability theory and its applications, 2nd ed., Wiley, 1970, 2 vols. [7] A. Granville, Harald Cram´er and the distribution of prime numbers, Scand. Actuarial J. 1 (1995), pp. 12–28. [8] H. Iwaniec and E. Kowalski, Analytic number theory, AMS Colloquium Publications, v. 53, American Mathematical Society, Providence, 2004. [9] G. Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge University Press, 1995. [10] P. Tur´ an, On a theorem of Hardy and Ramanujan, J. London Math. Soc. 9 (1934), 274–276.

61

´Indice alfab´ etico

funci´ on funci´ on funci´ on funci´ on funci´ on

O(f ), o(f ), 2 Λ(n), 5 ω(n), 2 τ (n), 1 teorema de convergencia de L´evy, 27

caracter´ıstica, 20 de densidad, 53 de probabilidad, 53 de von Mangoldt, 5 zeta de Riemann, 7

Hadamard, J., 7 Halberstam, H., 23

Billingsley, P., 23

independencia de variables, 55 de eventos, 55 en pares, 55 m´ utua, 55 intervalos di´ adicos, 6

Chebyshev, P., 7 condici´ on de Lindeberg, 22, 28, 29 conjetura de Hardy-Littlewood, 14 conjetura de los primos gemelos, 14 convergencia en distribuci´ on, 56, 59 convoluci´ on, 37 criba de Selberg, 13 lema fundamental, 41–43, 45, 47

Kac, M., 23 l´ımite central, 18, 23, 48 teorema del, 19, 21, 22 ladeo exponencial, 40

de la Vall´ee Poussin, C., 7 desigualdad de Chebyshev, 8, 9, 23, 32, 56 de Markov, 3, 8, 32 desviaci´ on estandar, 56 desviaciones grandes, 31, 38, 48 moderadas, 48 distribuci´ on de Poisson, 30 normal, 19, 28, 30 distribuci´ on uniforme, 54 divisores, 1 divisores primos, 2

modelo de Cram´er, 59 momentos, 15, 21 m´etodo de momentos, 21 momentos variables, 15, 17 momentos exponenciales, 32 n´ umero de primos hasta N , 5, 9 n´ umeros desmenuzables, 15, 17, 46 P. L´evy, 27 principio de inclusi´ on-exclusi´ on, 46 probabilidad condicional, 55 problema de la tabla de multiplicaci´ on, 14, 34, 37

entrop´ıa, 38, 39 relativa, 50 Erd˝ os, P., 14, 23, 37 esperanza, 1, 55 esperanza condicional, 56

sumas por partes, 4 teorema de Chebyshev-Mertens, 2, 5, 7 de convergencia de L´evy, 21 63

64

de Erd˝ os-Kac, 23, 49 de los n´ umeros primos, 7, 14, 48 fundamental de la aritm´etica, 5 transformada de Fourier, 19, 21, 25 valor cr´ıtico, 35 variables de Bernoulli, 53 varianza, 7, 56

´INDICE ALFABETICO ´