El sedàs i el ritme dels primers

Els primers són l'objecte més antic i més estudiat de la teoria de nombres, i alhora el que pitjor entenem. Sabem que n'hi ha infinits des de fa 2.300 anys; sabem, amb precisió sorprenent, quants n'hi ha fins a qualsevol límit; i tanmateix no hi ha cap fórmula que els generi, ni sabem respondre preguntes que un nen podria formular. Aquesta càpsula recorre les dues cares: el mètode elemental per trobar-los i la llei estadística que els governa.

1. Què és un primer, i per què l'1 no ho és

Un primer és un enter més gran que 1 que només es divideix exactament per 1 i per ell mateix. La seva importància ve del teorema fonamental de l'aritmètica: tot enter més gran que 1 es descompon en producte de primers d'una única manera, tret de l'ordre. 60 = 2²·3·5, i no hi ha cap altra manera de fer-ho.

Els primers són, doncs, els àtoms de la multiplicació, i és per això que apareixen a tot arreu: qualsevol pregunta multiplicativa sobre enters acaba, tard o d'hora, sent una pregunta sobre primers.

2. N'hi ha infinits: la demostració d'Euclides

És una de les demostracions més elegants que existeixen, té 2.300 anys, i cap en un paràgraf.

Un matís que sovint es diu malament: la demostració no afirma que N sigui primer. Sovint no ho és. Amb els cinc primers primers: 2·3·5·7·11 + 1 = 2311, que sí que és primer; però 2·3·5·7·11·13 + 1 = 30031 = 59·509, compost. El que la demostració garanteix és que els seus factors són primers nous, no que N ho sigui.

3. El sedàs: trobar-los sense dividir mai

Saber que n'hi ha infinits no ens diu quins són. Per trobar-los tots fins a un límit N, el mètode més antic continua sent dels més eficients: el sedàs d'Eratòstenes, del bibliotecari d'Alexandria, cap al 240 aC.

La idea inverteix el plantejament natural. En lloc de preguntar-se «és 91 primer?» i posar-se a dividir per 2, 3, 5, 7…, el sedàs elimina: si tatxes tots els múltiples de tots els primers, el que sobrevisqui és primer per força. No es fa ni una sola divisió en tot el procés —només comptar de p en p, que és sumar.

Aquesta diferència és tot el seu poder. Per trobar els 154 primers fins a 900 amb divisions successives caldrien desenes de milers de comprovacions. Amb el sedàs, com pots verificar a la càpsula, calen deu escombrades.

4. Els dos detalls que la càpsula fa visibles

El sedàs s'explica sovint en tres línies, i en el procés es perden les seves dues propietats més interessants. Totes dues es veuen directament a la graella.

Els múltiples nous comencen a p²

Quan arribes al 5 i n'has de tatxar els múltiples, 10 ja estava tatxat (el va tatxar el 2), 15 també (el 3), 20 també (el 2). El primer múltiple de 5 que encara no estava tatxat és el 25 = 5².

La raó és general: qualsevol múltiple de p menor que p² s'escriu com k·p amb k < p, i per tant té un factor primer més petit que p, que ja el va tatxar abans. A la càpsula, l'escombrada distingeix aquests dos casos amb colors —vermell els nous, ambre els que ja hi eren— i el comptador et diu quants n'hi ha de cada mena. Amb N=400 i p=19, per exemple, de 20 múltiples només 2 són nous.

Pots parar en superar √N

Aquesta és una conseqüència directa de l'anterior, i és el que fa que el sedàs sigui tan barat. Si p > √N, aleshores p² > N, i el primer múltiple nou ja cauria fora de la graella: l'escombrada no tatxaria res.

Amb N = 900, √900 = 30, i el darrer primer útil és el 29. Per això a la càpsula el sedàs s'acaba després de deu clics. La barra d'estat mostra √N permanentment, i el Repte té un tipus de ronda dedicat precisament a aquesta decisió.

5. Comptar-los: la funció π(x)

Un cop tens la llista, la pregunta natural canvia: no quins són, sinó quants n'hi ha. Definim π(x) com la quantitat de primers menors o iguals que x. π(10) = 4, π(100) = 25, π(1000) = 168.

Mirant la graella no s'hi veu cap ordre: hi ha zones denses (entre 1 i 20 n'hi ha 8) i clarianes. Però si dibuixes π(x) com una escala —un graó per cada primer, que és exactament el que fa la Vista 2 de la càpsula— apareix una corba sorprenentment suau.

Gauss, cap al 1792 i amb quinze anys, es dedicava a comptar primers en taules per entretenir-se. Va notar que la densitat de primers prop d'un número x era aproximadament 1/ln x, i d'aquí que π(x) hagi de créixer com x/ln x. No ho va publicar ni ho va demostrar; ho va anotar al marge d'una taula de logaritmes.

6. El teorema dels nombres primers

L'enunciat és que la raó entre π(x) i x/ln x tendeix a 1 quan x creix. Es va trigar un segle a demostrar-ho: Hadamard i de la Vallée Poussin ho van aconseguir el 1896, independentment i gairebé alhora, fent servir eines d'anàlisi complexa que Riemann havia introduït el 1859.

La convergència és real però lenta, i això es pot veure a la càpsula:

La raó baixa, però amb una calma exasperant. Per a x = 10⁶ l'error encara és del 8%.

7. Els forats, i el que encara no se sap

La tercera vista mira l'altra cara: la distància entre primers consecutius. I aquí l'ordre desapareix del tot.

Els bessons. Parelles amb forat 2: 3–5, 5–7, 11–13, 17–19, 29–31, 41–43… En surten fins on s'ha mirat, i sembla que no s'acabin mai. Però ningú ha estat capaç de demostrar que n'hi ha infinits. La conjectura dels primers bessons és un dels problemes oberts més antics i famosos.

El 2013 hi va haver un avenç espectacular d'un matemàtic desconegut, Yitang Zhang, que treballava en una situació acadèmica precària: va demostrar que hi ha infinites parelles de primers separades per menys de 70 milions. No és 2, però va ser el primer resultat finit de tots. Un esforç col·laboratiu posterior va baixar aquesta cota fins a 246.

Les clarianes. A l'altre extrem, els forats poden ser tan grans com es vulgui: la successió n!+2, n!+3, …, n!+n està formada tota per compostos, i té llargada n−1. Existeixen buits de mil milions de números sense cap primer. De mitjana, però, el forat prop de x creix només com ln x — molt a poc a poc.

A la càpsula, els rècords de forat es marquen en vermell. Fins a 900, els rècords apareixen després del 2, 3, 7, 23, 89, 113, 523 i 887, amb forats de 1, 2, 4, 6, 8, 14, 18 i 20 respectivament.

8. Què fem a l'element interactiu

Vista «El sedàs». Cliques el número més petit que quedi sense tatxar —el sistema només et deixa clicar aquest, perquè és l'únic moviment vàlid de l'algorisme— i, amb un sol gest, s'escombren tots els seus múltiples. Els colors distingeixen els nous dels ja tatxats, i la narració et diu els números exactes. La barra d'estat porta el compte i mostra √N.

El botó «Acaba'l tot» completa el sedàs de cop, útil quan ja has entès el mecanisme i vols anar a les altres vistes o provar un N més gran.

Vista «Quants n'hi ha». L'escala de π(x) es va construint amb els primers que tu has confirmat, superposada a x/ln x. Fins que no acabes el sedàs, l'escala està incompleta —això és deliberat: la corba és el resultat de la teva feina, no una imatge pregravada.

Vista «Forats». Cada barra és la distància fins al primer següent. Verd els bessons, vermell els rècords.

9. Aparicions fora de les matemàtiques

Criptografia. És l'aplicació dominant. RSA es basa en una asimetria brutal: multiplicar dos primers de 300 xifres és instantani; recuperar-los a partir del producte és, fins on sabem, inabastable. Tota la seguretat de les connexions HTTPS, les signatures digitals i bona part de la banca en línia hi descansa. Val la pena notar la ironia: la seguretat depèn del fet que no sabem factoritzar bé, no de cap teorema demostrat.

Generació de claus. Per construir una clau RSA cal trobar primers enormes. No es fa amb el sedàs (impossible a aquesta escala) sinó amb tests probabilístics com Miller–Rabin, que declaren un número primer amb probabilitat d'error controlable. El teorema dels nombres primers és el que garanteix que la cerca acabarà: prop de 2²⁰⁴⁸, aproximadament 1 de cada 1.420 números senars és primer.

Funcions de dispersió i estructures de dades. Les taules de hash fan servir mides primeres per repartir millor les claus i reduir col·lisions. Molts generadors de nombres pseudoaleatoris tenen períodes que són primers de Mersenne —el Mersenne Twister, el més usat, té període 2¹⁹⁹³⁷−1.

Biologia. Les cigales dels gèneres Magicicada emergeixen en cicles de 13 o 17 anys, tots dos primers. La hipòtesi més acceptada és que un cicle primer minimitza les coincidències amb els cicles dels depredadors: un cicle de 12 anys coincidiria amb depredadors de període 2, 3, 4 i 6.

Codis correctors i senyals. Els codis Reed–Solomon i bona part de la teoria de cossos finits depenen de primers. I en la recerca d'intel·ligència extraterrestre, una seqüència de primers s'ha proposat repetidament com a senyal inequívocament artificial, perquè no hi ha cap procés físic conegut que la generi.

10. Curiositats

Eratòstenes també va mesurar la Terra. El mateix home que va inventar aquest sedàs va calcular la circumferència terrestre comparant l'ombra del migdia a Alexandria i a Siena, i li va sortir amb un error de potser un 2%. Era bibliotecari en cap d'Alexandria i els seus contemporanis el motejaven «Beta», perquè el consideraven el segon millor en tot. En diverses coses era el primer.

Gauss ho va conjecturar als 15 anys i no ho va dir a ningú. L'anotació sobre la densitat 1/ln x va aparèixer en una taula de logaritmes seva, i no es va conèixer fins després de la seva mort, en una carta de 1849. Legendre va publicar una conjectura equivalent el 1798, sense saber-ho.

La demostració «elemental» va provocar una batalla. Es creia que el teorema dels primers necessitava anàlisi complexa. El 1949, Paul Erdős i Atle Selberg en van trobar una demostració elemental (sense variable complexa). La disputa sobre a qui corresponia el mèrit va ser amarga i va enterbolir la relació entre tots dos per sempre; Selberg va rebre la medalla Fields el 1950.

Una funció aparentment innocent val un milió de dòlars. Riemann va relacionar el 1859 la distribució dels primers amb els zeros d'una funció complexa, ζ(s). La hipòtesi de Riemann afirma que tots els zeros no trivials tenen part real 1/2, i equival a dir que l'error de li(x) com a estimació de π(x) és el més petit possible. És un dels set problemes del mil·lenni de l'institut Clay, amb un milió de dòlars de premi. Segueix oberta des de fa 165 anys.

Hi ha un número on l'aproximació es gira, i ningú l'ha vist. Per a tot x que s'ha calculat mai, li(x) > π(x). Littlewood va demostrar el 1914 que això es capgira infinites vegades. El primer punt on passa es coneix com el número de Skewes, i les cotes conegudes el situen prop de 10³¹⁶ — molt més enllà del que cap ordinador podrà comprovar mai. És un exemple espectacular de per què l'evidència numèrica no és una demostració.

El primer més gran conegut supera els 41 milions de xifres. És un primer de Mersenne, de la forma 2ᵖ−1, trobat pel projecte distribuït GIMPS amb ordinadors de voluntaris. Imprimit a mida de llibre normal, ocuparia més de deu mil pàgines.

Els primers formen progressions aritmètiques tan llargues com es vulgui. Ben Green i Terence Tao ho van demostrar el 2004: per a qualsevol k, existeixen k primers igualment espaiats. Per exemple, 5, 11, 17, 23, 29 són cinc primers separats de 6 en 6. El teorema garanteix que n'hi ha de mil termes, tot i que ningú n'ha trobat mai cap de tan llarga.

L'espiral d'Ulam. El 1963, avorrit en una conferència, Stanisław Ulam va anar escrivint números en espiral en un paper i va marcar-ne els primers. Van aparèixer diagonals clarament visibles, que corresponen a polinomis quadràtics especialment rics en primers com n²+n+41 (que dona primers per a n = 0 fins a 39). Ningú sap explicar del tot per què.

11. Connexió amb altres àrees

Aquesta càpsula és la base del bloc. Reciprocitat quadràtica pren dos primers senars i pregunta com es relacionen entre ells; aquí veus d'on surten aquests primers i com de rars són. Fraccions contínues treballa amb √N per a N no quadrat perfecte, i la periodicitat que hi apareix depèn de l'estructura multiplicativa que els primers determinen.

Cap a l'àlgebra, el teorema de Lagrange de Taules de Cayley té una conseqüència directa aquí: si un grup té ordre primer, els únics subgrups possibles són el trivial i ell mateix, i per tant ha de ser cíclic. Hi ha exactament un grup de cada ordre primer, cosa que fa dels primers també els àtoms de la teoria de grups finits.

I cap a l'anàlisi, la connexió és la més profunda de totes. La funció zeta de Riemann s'escriu alhora com una suma sobre tots els enters i com un producte sobre tots els primers (el producte d'Euler). Aquesta doble identitat és el pont pel qual les eines contínues del càlcul —les mateixes famílies d'idees que trobaràs a Sèries de Fourier i al Pla d'Argand— entren a respondre preguntes sobre enters. El teorema dels nombres primers es va demostrar, precisament, travessant aquest pont.