Oneindig vele priemgetallen blijken hypercijfergevoelig

Hoe eenzaam kan een priemgetal zijn? Niet enkel kunnen ze omgeven worden door priemwoestijnen, ze kunnen ook aan cijfergevoeligheid lijden waardoor andere priemgetallen zo goed als onbereikbaar worden. In 2020 ontdekte Michael Filaseta van de universiteit van South Carolina een nog meer extreme contactstoornis bij sommige priemgetallen: zij bleken hypercijfergevoelig. Dit jaar bewees hij bovendien dat dit helemaal geen zeldzaam fenomeen is. Maar omdat ze zich enkel bij heel grote priemgetallen manifesteert, bleef deze eigenschap tot nu toe onder de radar.

Als het over getallen zijn, spreken we natuurlijk eerder over een “eigenschap” in plaats van een “aandoening”. Wiskunde hoeft geen Disney-animatie te zijn. In ieder geval, dit jaar bewees Filaseta dat hypercijfergevoeligheid helemaal geen zeldzame eigenschap is van priemgetallen. Maar omdat ze zich enkel bij heel grote priemgetallen manifesteert, bleef deze eigenschap tot nu toe onopgemerkt.

De afstand tussen twee opeenvolgende priemgetallen is een mogelijke maatstaf om hun eenzaamheid te meten. Bij een groter priemgetal $P$ verwachten we ook een groter gat tot het volgende priemgetallen aan te treffen, namelijk een priemvrije zone van gemiddelde lengte $\ln(P)$. Als een priemgat aanzienlijk groter is dan de verwachte $\ln(P)$ noemen wiskundigen (met gevoel voor dramatiek) dit een priemwoestijn.

Met dank aan Uitwiskeling

Bijvoorbeeld, na het priemgetal 1425172824437699411 strekt zich een woestijn uit van lengte 1476 (tot het volgende priemgetal), meer dan 35 keer het gat ln(1425172824437699411) 42 dat we zouden verwachten. Deze priemwoestijn is in 2008 gespot door Tomàs Oliveira e Silva.

De oasezoekers onder jullie verwijzen we graag door naar het hoofdstuk De eenzaamheid van de priemgetallen uit ons boek De pracht van priemgetallen, of naar het mooie, recente  boek van Alex van den Brandhof:

Voor een laatste stand van priemwoestijnzaken kunnen jullie altijd terecht op de webpagina van Jens Kruse Andersen.

Sinds 1978 al weten we dat sommige priemgetallen cijfergevoelig (digitally delicate) zijn. De vraag naar hun bestaan werd gelanceerd door de notoire probleemsteller Murray Klamkin, maar het antwoord danken we aan de legendarische probleemkraker Paul Erdős. We noemen een priemgetal cijfergevoelig als het geen priemgetal meer is zodra we 1 willekeurig cijfer wijzigen (in om het even welk ander cijfer). Zo is 294001 een cijfergevoelig priemgetal, want zodra je (exact) een van de zes cijfers verandert dan is het geen priemgetal meer. Als we bijvoorbeeld de eerste nul in 294001 veranderen in een 3, dan valt het getal uit elkaar als een product: $294301=7\times 42043$. In jargonterminologie hebben cijfergevoelige priemgetallen volgens de Hamming-metriek geen andere priemgetallen als buren, wat dus ook als een indicatie van eenzaamheid kan beschouwd worden.

Op het eerste zicht lijken cijfergevoelige priemgetallen erg zeldzaam, tot ver in de vorige eeuw wisten we zelfs niet dat ze bestonden. Het voorbeeld hierboven, 294001, is trouwens het kleinste priemgetal dat cijfergevoelig is. Maar in 1978 bewees Paul Erdős dat de cijfergevoelige priemgetallen met oneindig in aantal zijn. Dit geldt zelfs in ieder talstelsel (maar geen paniek, in dit artikel zullen we ons vertrouwde tientallig stelsel niet verlaten). Op de iconische foto hieronder leest Erdős de berekeningen van het wonderkind Terence Tao, die later, in 2011, bewees dat cijfergevoelige priemgetallen zelfs een positieve fractie vertegenwoordigen onder alle priemgetallen, waaruit blijkt dat het hier niet om een marginaal verschijnsel gaat.

Sommige getaltheoretici vermoeden zelfs dat op een gegeven moment op de getallenlijn ieder priemgetal cijfergevoelig wordt, en dat er dus slechts eindig veel priemgetallen bestaan die niet cijfergevoelig zijn. Maar dit is slechts speculatie, laten we ons bij de feiten houden, die zijn al voldoende wetenswaardig.

In het najaar van 2020 vestigden Michael Filaseta en Jeremiah Southwick in hun artikel
Primes that become composite after changing an arbitrary digit
de aandacht op een nog extremere vorm van cijfergevoeligheid. Immers, in sommige contexten laat men toe om in de (decimale) schrijfwijze een (priem)getal te beginnen met een aantal nullen. Dus bijvoorbeeld 294001 kan ook voorgesteld worden door 00294001. Maar hierdoor verdwijnt de cijfergevoeligheid van dit priemgetal, want 10294001 is terug een priemgetal! Bestaan er dan misschien wel hypercijfergevoelige priemgetallen (widely digitally delicate), priemgetallen die zelfs na het voorvoegen van een willekeurig aantal nullen cijfergevoelig blijven? Hieronder zien we Michael Filaseta met op zijn sweater de eerste twintig cijfergevoelige priemgetallen, maar geen hiervan blijkt hypercijfergevoelig.

Met dank aan Quanta Magazine.

Nochtans, tot verbazing van sommige specialisten, bewezen Filaseta en Southwick dat er oneindig veel priemgetallen moeten bestaan die hypercijfergevoelig zijn. Maar zelf konden ze geen voorbeeld geven. Het is immers een tool uit de wiskundige toverdoos om het bestaan van sommige objecten aan te tonen zonder effectief een ervan concreet te kennen. Existentiële bewijsvoering heet dit. Dit jaar deed Filaseta er nog een schepje bovenop, en bewees hij samen met zijn doctoraatsstudent Juillerat dat er voor iedere willekeurige lengte $k$ een rij van $k$ opeenvolgende priemgetallen bestaat die alle hypercijfergevoelig zijn. Een resultaat dat flirt met de ongeloofwaardigheid, en dat sommige wiskundigen in de verleiding bracht het vermoeden te opperen dat vanaf een bepaald punt ieder priemgetal hypercijfergevoelig moet zijn.

Zonder afbreuk te doen van de existentiële elegantie van Filaseta, kunnen we toch ook de constructieve bijdrage appreciëren van zijn collega Jon Grantham, die er in slaagde om een concreet hypercijfergevoelig priemgetal te vinden, dat we nu graag met jullie willen delen. Bereid je voor op wellicht het grootste getal dat ooit in een Eos-blog verscheen:

90396372102370945638814565897664411717914046722399568714088806427940663130321169
34850967511659843086053335172146529265646031754611621958998514725947297331071222
58404543870912699052653808779801711588900429434927845180788157760827763723443204
38358731608641322977038092749871021804967879180780958345060921734649698782711881
79734549711466510520072591941274714351219717736218095220183890792190660294452474
92646160567827636230677584407261407437252175001634387844273369947782015107697040
30069688191298350917119918760883431507235354860101043431491222908757868152966760
05793097845579069443568767997527332525621005614735839007092969418872320273092508
17867763286325557479344975393285510163111180003162836013957112532348887862314365
27910149646700274883085835628489844758513925117409356642935450897206587682412946
98656155492833473456154565072811521890237196777579962162801937208734470380740726
13176305613741748267103457055545365184429111379209209582667174874790838191016698
94876381003309650735731939020339925608394155521521571226987949200634519428696470
50367310216937779182581141282417776706149276626335167277256776495351014310419502
73034793306162313159336820131786333012784116298204250018981662084412774917388485
08899251813286743538728490401468601602756502441199129965403628516514008997633340
87274031877729944005178971300554636291328269528871432387745264969552111305078096
42104045065466317557214077287916720477966386264290238733662882693612868524255052
39472289369668341916073883613282466433600737551234372009973998756283404917065530
63764251277103060852676197745624887034181229773722089306276457543132000429261154
44808727207557383353231848786995000186431028958593379583773171116750700648654413
99549493822108565555383290564548000652811150332759917467132058214766522059471853
52720064364008511824228877615951766654731637165852717552240565639909453836759174
66952383851553384308190517061516024616904658768003048009007770606403664834928219
77025268736281020628213096574198125405222565567936041566271426463299821507731657
69632658983818107103057063768171468768523123329554877218203647082573554824808132
33882779888138961272890664929620290035185805730991033944911545921400248075473573
37517367086436862826703587620594102748396294563554261763144220907788496037601272
77755201321643792239357167852124415367200521086054253440470728507457509558592810
19650551609234155372645359009221943434188374368180817780684590275527752996882753
14671332420171538551165140438921986477434938983320298692408233327779069468648317
98875562424263075298400880234089389474115513324068533034908587230608008795505456
32218420603187714881679229250609583799972014502577347056111269476284160020402578
25709270892722762152979845106619343825011250520471461490584593759630528898175991
26119084145412790221305002215653042200430710947782841462241099490062742380328625
70123016119996876863984451214391411335482684730004645649381589231520564794888816
22076353619623748408417024213209016022242207918544872008917158393274098459546919
34528049774006663196621357345559283458549664269423239382525376962371040410311391
35518368310079594928246950610385853880033997879771516415145096484118783619636170
92854179752886569556428928859618530728803258511711230980264562347109007932071714
44048907403288660746539557983006232251954462326061814506555747164276322331886832
74623604406386718975737362016188288166073364846717465489367132732878740263131365
43388270670285357328371616744330342394198744892821964206916956439411933716673374
07370885041267453405744376431424022593175458937025994227972738433232768739044215
65112765095829984709497371420489838102177151224837889944491456651848659829406175
82273242082105257629549082049091082423189152696375173504693355462341581713751673
67560279546396263512492717808658371295667761721867484695363193090810381374172504
22494212994901297287701031058574468599004421789299349882600646274218762987865220
36816490375966714023327990100421066890271965644383060890065940555568642144556553
26329785479294475491379385058100746496414140830764235041924433266053913161683067
328820452080387458290975399249