Posts in category Topologie
Dikke en dunne verzamelingen
Gisteren hebben we gekeken naar de wiskunde achter het vermoeden van Duffin en Schaeffer. Wat daar niet goed uit de verf kwam waren de noties van `dikke’ en `dunne’ verzamelingen. Daar doen we vandaag wat aan.
Zoals gisteren en in de krant beschreven gaat het vermoeden van Duffin en Schaeffer over benaderingen van irrationale getallen met behulp van breuken. De situatie is als volgt: neem een rij (xn)n van positieve reële getallen en noem een irrationaal getal α goed benaderbaar, volgens de gegeven rij, als er oneindig veel natuurlijke getallen n bestaan met voor elk van die n een breuk t/n met noemer n bestaat zó dat |α-t/n|<xn.
De vraag is dan natuurlijk of er irrationale getallen zijn die goed te benaderen zijn. Gisteren hebben we gezien dat als x_n=n-2 alle irrationale getallen goed te benaderen zijn. Met een beroep op de gisteren ook genoemde Categoriestelling van Baire kunnen we laten zien dat er altijd heel veel goed benaderbare irrationale getallen zijn. Net als gisteren bekijken we voor elke n de intervallen (0,xn), (1/n-xn,1/n+xn) … (1-1/n-xn,1-1/n+xn), (1-xn,1). Hun vereniging noemen we An.
Neem een (klein) interval (a,b) binnen (0,1); dan geldt voor elke n met 1/n<b-a dat An en (a,b) een niet-lege doorsnede hebben (bedenk maar eens waarom dat zo is). Dit betekent dat indien we voor elke n de verzamelingen An, An+1, An+2, … verenigen tot de verzameling On we een verzameling krijgen die met elk intervalletje getallen gemeen heeft. De stelling van Baire garandeert nu dat er heel veel getallen bestaan die tot alle On behoren, en dus tot oneindig veel van de An (denk daar ook maar eens goed over na). Al die getallen zijn dus goed benaderbaar, volgens de gegeven rij.
In topologische zin is het complement van die verzameling goed benaderbare getallen nogal dunnetjes, in het Engels: meagre; de verzameling goed benaderbare getallen is dus, topologisch gesproken, bijna het hele interval (0,1) een dikke verzameling dus.
Het vermoeden van Duffin en Schaeffer ging over een andere notie van dik en dun. Laten we de verzameling goed benaderbare getallen, bij de rij (xn)n, even noteren met G(x). De nu bewezen stelling kijkt naar de (totale) lengte van de intervalletjes die we hierboven gebruikt hebben. Voor elke n is de totale lengte van An gelijk aan 2×n×xn. Als de xn-en te klein zijn zal de verzameling G(x) volgens deze notie als dun aangemerkt worden in die zin dat de kans dat een irrationaal getal goed benaderbaar is gelijk is aan 0.
De stelling van Dimitris Koukoulopoulos en James Maynard spreekt uit dat voor elke rij (xn)n de verzameling G(x) hetzij kans gelijk aan 1 heeft om geraakt te worden, hetzij kans 0; een tussenweg is er niet. Daarnaast geeft de stelling precies aan voor welke rijen kans 1 geldt en voor welke rijen kans 0.
We hebben hier dus twee soorten `dik en dun’ gezien: topologisch en kanstheoretisch. Beide noties worden in de Analyse toegepast om te laten zien dat bepaalde objecten bestaan: als je laat zien dat de verzameling van die dingen `dik’ is is die zeker niet leeg.
Voor topologen is de verzameling goed benaderbare getallen altijd `dik’; voor kansrekenaars is hij soms `dik’ en soms `dun’. Dit klinkt paradoxaal, maar is het niet: het is `gewoon’ een gevolg van de definities. En het illusteert wel treffend de titel van de column die gisteren is aangehaald: ‘De kans is nul’ is niet hetzelfde als ‘dat gaat niet gebeuren’.
Het vermoeden van Duffin en Schaeffer
Recentelijk is het Duffin-Schaeffer-vermoeden bewezen. U kunt de preprint hier lezen. In de krant is er ook aandacht aan besteed. Ik wil hier iets meer over de wiskunde achter dit vermoeden vertellen.
Het vermoeden, nu dus een stelling, zegt iets over het benaderen van irrationale getallen met behulp van rationale getallen. De vraag is in het algemeen hoe efficiëent dergelijke benaderingen kunnen zijn.
Nu zullen de meningen over wat efficiënt is uiteen lopen maar de benaderingen die we in de praktijk gebruiken, namelijk afgekapte decimale ontwikkelingen, zijn het niet echt. Als die afgekapte ontwikkelingen als breuk schrijft is die breuk vrijwel nooit te vereenvoudigen: de benadering 3.14159265358979323846264338327 van π levert een onvereenvoudigbare breuk met een grote teller en een grote noemer.
Een goede benadering is er een waar de nauwkeurigheid groot is, vergeleken met de grootte van teller en noemer. Zo kun je 22/7 een goede benadering van π noemen omdat het verschil 22/7-π kleiner is dan 1/49. Het criterium dat we hier hanteren is: p/q is een goede benadering van α als |α-p/q| kleiner is dan 1/q2. Overigens is 19/6 ook een goede benadering: 19/6-π is kleiner dan 1/36.
Een beetje spelen met een rekenmachientje laat zien dat er geen goede benaderingen van π zijn met noemers 8 of 9.
Het vermoeden van Duffin en Schaeffer, nu dus de stelling van Dimitris Koukoulopoulos en James Maynard, gaat overigens niet over individuele irrationale getallen als π of √2. Het bekijkt de zaak van de andere kant en doet uitspraken over hoeveel irrationale getallen veel goede benaderingen hebben.
Je kunt bijvoorbeeld een vaste noemer n nemen en kijken welke getallen een goede benadering met noemer n hebben. Hierbij beperken we ons tot het interval (0,1); getallen in andere intervallen krijgen we door over een geheel getal op te schuiven.
Nu is meteen duidelijk welke getallen een goede benadering met noemer n hebben: die liggen in de intervalletjes van de vorm (k/n-1/n2,k/n+1/n2), met k=1,…,n-1, en in (0,1/n2) en (1-1/n2,1).
De totale lengte van die intervallen is gelijk aan 2/n (reken maar na).
Hiermee kun je voorspellingen doen: omdat 2/10+2/11+2/12+2/13+2/14+2/15 kleiner is dan 1 zijn er getallen zonder goede benadering met noemers 10 tot en met 15.
Noem de vereniging van de intervalletjes hierboven even An. Met behulp van de Categoriestelling van Baire kun je bewijzen dat er een relatief `dikke’ deelverzameling van het interval (0,1) is waarvan elk element tot oneindig veel van de An behoort en dus oneindig veel goede benaderingen heeft.
Dit nu is de aard van de stelling van Dimitris Koukoulopoulos en James Maynard: deze geeft, bij bepaalde definities van `goede benadering’, voorwaarden onder welke de verzameling getallen met oneindig veel goede benaderingen heel `dik’ is of juist heel `dun’, waarbij `dik’ en `dun’ ondubbelzinnige definities hebben. Daarnaast geeft de stelling ook een dichotomie: `dik’ en `dun’ zijn de enige mogelijkheden. Het is nooit zo dat ongeveer de helft van de getallen oneindig veel goede benaderingen hebben; de kans is altijd gelijk aan nul (wat niet betekent dat er geen getallen zonder oneindig veel goede benaderingen zijn) of gelijk aan één.
In het krantenartikel wordt nog het volgende voorbeeld van `mooie’ benaderingen gegeven: als hierboven moet |α-p/q| kleiner zijn dan 1/q2, maar q moet zelf ook een kwadraat zijn. In dat geval is de kans op oneindig veel mooie benaderingen gelijk aan nul, maar de bovengenoemde stelling van Baire garandeert toch dat er heel veel irrationale getallen met oneindig veel goede benaderingen zijn.
Ten slotte: voor de definitie van `goed’ waar dit stuk mee begon geldt dat <emelk irrationaal getal oneindig veel goede benaderingen heeft. Dat bewijs je niet met de methoden die hier beschreven zijn, daar moet je wat dieper de getaltheorie in duiken. Zie hiervoor de Wikipediapagina’s over Benaderingsstelling van Dirichlet en over Kettingbreuken.
More on machine learning and CH
A few days ago I wrote about a paper establishing an independence result in the field of machine learning. Here I offer a few more comments.
In the paper the authors comment on the relation between their result and actual machine learning. That relation may seem tenuous because none of the functions involved in the arguments is related to any kind of algorithm.
Indeed the constructions of the compression schemes are very non-constructive in that they use repeated applications of the Axiom of Choice.
Now the inequality 2ℵ0>ℵω implies there are no compression schemes whatsoever. But it may be of interest to know that consistent examples of compression schemes must be nonconstructive. It turns out that, with the aid of a few standard results from Descriptive Set Theory it is relatively easy to show outright that there are no Borel measurable monotone compression schemes and hence no Borel measurable learning functions for the class of problems studied in the paper mentioned above either.
The details can be found in this note.
KP zag een gat
Op twitter raakte ik betrokken in een discussie over gaten, in het bijzonder over het aantal gaten dat een rietje heeft. Het antwoord hangt natuurlijk af van wat je als `gat’ aanmerkt maar als je er wiskundigen (in dit geval Ionica Smeets en mij) bij haalt dan krijgt je `één’ als antwoord. En dat komt omdat wiskundigen precies hebben afgesproken wat een `gat’ is en die afspraak leidt tot dat antwoord.
Wat is een gat dan?
We (de wiskundigen dan) beschouwen het rietje als een oppervlak en we tellen de gaten in dat oppervlak door vanuit een vast punt op dat oppervlak krommen te tekenen die beginnen en eindigen in dat punt. Dat is wat lastig met een fysiek rietje dus nemen we een rietje van een heel elastisch materiaal en door het aan één kant op te rekken kun je er een ringvormig gebied in het platte vlak van maken. Het tekenen gaat daar wat makkelijker; je kunt de krommen met touwtjes of elastiekjes maken; dat scheelt uitgummen als het papier te vol wordt.
Bij sommige krommen kun je het elastiekje laten krimpen tot het zo klein is als het vaste punt en zonder dat het elastiekje buiten het werkgebied komt. Bij andere lukt dat niet, bijvoorbeeld één keer (tegen de klok in) om het binnengebied gaat (of twee keer, of drie keer, …).
Een kromme die niet tot het vaste punt samengetrokken kan worden zonder buiten het werkgebied te komen wijst, wiskundig gesproken, op een gat. Dit betekent niet dat we vinden dat er oneindig veel gaten in het gebied zitten. Je kunt namelijk bewijzen (en dat kost enig werk) dat elke kromme (elastiekje) vervormd kan worden tot die ene kromme die één keer linksom het binnengebied gaat; daarbij wordt het aantal keren dat de kromme om het binnengebied gaat bewaard.
Dus een kromme die drie keer om het binnengebied gaat kun je vervormen tot drie keer achtereen die ene kromme, met behoud van richting.
Omdat elke kromme eigenlijk een aantal keer de ene basiskromme doorloopt vinden we dat het gebied één gat heeft.
Een T-stuk
Verderop in de twitterlijn kwam dit plaatje tevoorschijn: een bouwsel van twee rietjes dat eigenlijk een T-stuk voorstelde. Nu heeft een T-stuk drie openingen maar wiskundig gesproken zijn er maar twee gaten. Dat is met de nieuwe grens van 280 karakters net in één tweet uit te leggen:
Buig gaten 1 en 3 naar links zo dat je een broek krijgt; krimp de pijpen in tot je een zwembroekje overhoudt. Leg het broekje op tafel waarbij je gat 2 onder houdt en zover oprekt dat het de buitenrand wordt. Strijk alles glad: cirkelschijf met twee gaten.
Er zijn nu twee basiskrommen: neem een punt ergens in het midden en teken een kromme die één keer om het linkergat gaat en één keer om het rechtergat (beide tegen de klok in).
Elke andere kromme die in het gekozen punt begint en eindigt is te vervormen tot eentje die de basiskrommen doorloopt. Hierbij is het wat ingewikkelder dan bij één gat. De volgorde is van belang: eerst links dan rechts is niet hetzelfde als eerst rechts dan links.
Dus: twee basiskrommen en daarmee twee gaten.
Gaten in de kaas
Gaten (bubbels) in de kaas kun je niet met krommen detecteren: je kunt elke kromme tot een punt vervormen buiten alle holtes om. In dat geval gebruikt men (virtuele) ballonnen: een ballon waar een gat binnen ligt kun je niet geheel binnen de kaas samentrekken. Je kunt zelfs `basisballonnen’ definiëren en laten zien dat elke andere ballon tot een combinatie van basisbalonnen te vervormen is maar dat afspreken is een stuk ingewikkelder dan bij het doorlopen van krommen.
Recent Comments