Wiskundemeisjes

Een week of wat geleden is een mooie website gelanceerd waar je gratis een twee uur durende wiskundefilm kunt downloaden. De film is gemaakt door Jos Leys (graphics en animaties) en wiskundigen van de ENS in Lyon: Etienne Ghys (scenario en wiskunde) en Aurélien Alvarez (realisatie and post-productie).

De film gaat over dimensies. Aan bod komen de dimensies 2, 3 en 4, en ook complexe getallen en de Hopf-vezeling. De film besluit met een aanschouwelijk bewijs dat de stereografische projectie cirkels projecteert als cirkels.

Ik heb de film nog niet gezien, maar de trailer ziet er mooi uit! De film wordt verspreid onder een 'Creative Commons' licentie: je mag de film verder verspreiden en publiek tonen, maar je mag er geen commercieel gebruik aan geven. Alle verdere informatie, inclusief de trailer, is hier te vinden. Maar de trailer staat natuurlijk ook op YouTube:

Nog even en de wiskundemeisjes kunnen hun huizen inrichten met wiskundig verantwoorde meubels. Kriskras tipte ons eerst over deze fractaltafel van Platform Wertel Oberfell.

Een paar dagen later mailde Kriskras ons ook nog deze fractalkast van Takeshi Miyakawa.

Dit zou natuurlijk allemaal prachtig staan op mijn fractaltapijt. Dankzij Petra kunnen we ook nog iets moois aan de muur hangen: wandkasten gebaseerd op het werk van John Conway.

Deze keer vragen we aan Ronald Cramer wie zijn favoriete (nog levende!) wiskundige is. Cramer is leider van de onderzoeksgroep Cryptology and Information Security op het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam en hoogleraar Cryptologie aan de Universiteit Leiden. Hij wil geen absolute favoriet aanwijzen, maar wil wel verklappen wie één van zijn favorieten is: Avi Wigderson.

Avi Wigderson

Wigderson werd in 1956 geboren in Haifa en is sinds 1999 hoogleraar discrete wiskunde en theoretische informatica aan de School of Mathematics van het Institute for Advanced Study te Princeton.

Ronald Cramer legt uit hoe de cryptologie sinds de jaren veertig een stormachtige ontwikkeling heeft doorgemaakt, en wat Wigdersons aandeel daarin is.

Cryptologie stond al eeuwenlang bekend als de kunst van het geheimschrift. In de jaren veertig kwam Claude Shannon van MIT met een wiskundige theorie van communicatie. Daarmee werd de basis gelegd voor een wiskundige basis van de cryptologie. De ontwikkeling van de public key cryptologie in de jaren zeventig was de volgende grote stap voorwaarts. Daarmee werd namelijk een oplossing voorgesteld voor de paradox van de geheime geheime-sleuteluitwisseling: voor veel cryptologische systemen heb je een geheime sleutel nodig, maar die moet natuurlijk ook uitgewisseld worden tussen de partijen die met elkaar willen kunnen communiceren. Daarna kwam de digitale handtekening, weer een volstrekt nieuwe toepassing.

Tegenwoordig is cryptologie overal, het wordt bijvoorbeeld veel gebruikt op internet en bij mobiele telefonie. In de nabije toekomst krijgen de huidige technieken (die vooral gebaseerd zijn op RSA) mogelijk grotere concurrentie van elliptische-krommencryptologie, en wie weet zelfs van de quantumcryptologie.

Tot en met de jaren zeventig ging cryptologie vooral over uni-laterale veiligheid: het beveiligen van communicatiekanalen tegen indringers (geheimhouden van de boodschap, of kunnen controleren dat de boodschap echt afkomt van de persoon waarvan je wil dat de boodschap komt): de ``good guys'' beschermen tegen de ``bad guys''. In de jaren tachtig deed de multi-laterale veiligheid zijn intrede. Een voorbeeld hiervan vormen de zogenaamde zero knowledge bewijzen, waarmee je in principe een sceptische partij van de ``waarachtigheid van stellingen kunt overtuigen'' zonder ook maar iets van je bewijzen prijs te geven. Dat is een speciaal geval van secure computation, waarmee partijen die elkaar geen geheime data willen toevertrouwen toch kunnen samenwerken en veilig functies kunnen uitrekenen op die wederzijds geheime data.

Samen met Oded Goldreich en Silvio Micali liet Avi Wigderson in het midden van de jaren tachtig eerst zien dat zero knowledge bewijzen mogelijk waren voor ``alle stellingen die een bewijs toelaten dat efficiënt getoetst kan worden,'' de zogenaamde NP-talen. In een volgende artikel lieten ze zien dat alle functies die efficiënt berekend kunnen worden ook veilig berekend kunnen worden (veilig in de zin van secure computation en onder de aanname dat hooguit een zekere fractie van de partijen samenzweert). Dat verschafte de cryptologie in één klap schitterende nieuwe vergezichten, aangezien heel veel veiligheidsproblemen in principe opgevat kunnen worden als secure computation problemen. Hoewel ze theoretisch efficiënt zijn, zijn hun methoden allerminst praktisch. Er bleef dus veel werk over, en dat is nog altijd in volle gang.

De klap op de vuurpijl kwam in 1988. Shafi Goldwasser, Michael Ben-Or en weer Avi Wigderson lieten toen zien dat die stelling zelfs bewezen kan worden zonder enige aannames op beperkingen op de rekenkracht van mogelijke aanvallers en dus in wezen informatie-theoretisch (of combinatorisch) van aard is, in plaats van complexiteits-theoretisch. Met andere woorden, de stelling geldt ook als er een aanvaller zou komen die efficiënt grote getallen kan factorizeren of die een quantumcomputer heeft. Overigens, deze fundamentele stelling werd tegelijkertijd en onafhankelijk bewezen op het CWI, door David Chaum, Ivan Damgaard en Claude Crépeau.

Cramers eigen onderzoek in de cryptologie is zeer sterk beïnvloed door dit resultaat. In de afgelopen jaren zijn daarbij interessante verbindingen ontstaan tussen informatietheoretisch veilige secure computation aan de ene kant, en combinatoriek, coderingstheorie, algebraïsche meetkunde en algebraïsche getaltheorie aan de andere kant. Cramer heeft daar op het International Congress of Mathematicians (ICM) in Madrid in 2006 zeer genoeglijk met Wigderson over gesproken.

Avi Wigderson werkt nu al drie decennia aan talloze onderwerpen in de combinatoriek, complexiteitstheorie, algoritmen en cryptologie. Wat zijn werk steeds kenmerkt is zijn vermogen tot het leggen van diepe, vruchtbare verbanden tussen problemen uit de theoretische informatica en de zuivere wiskunde. In 1994 werd Wigderson op het ICM in Zürich met de Nevanlinna-prijs onderscheiden vanwege zijn grensoverschrijdende werk. Sindsdien heeft hij allerminst stilgezeten. Cramer vindt zijn recente werk over randomness extractors (samen met Omer Reingold en Salil Vadhan) bijvoorbeeld weer een schitterend resultaat.

Elk jaar in augustus is er een leuke tweedaagse vakantiecursus voor wiskundeleraren (ook die op het hbo) en andere belangstellenden. Zo ook dit jaar. De vakantiecursus wordt op twee plaatsen gegeven: op 22 en 23 augustus op de TU in Eindhoven en op 29 en 30 augustus op het CWI in Amsterdam.

De vakantiecursus wordt georganiseerd door het CWI, in samenwerking met de Nederlandse Vereniging voor Wiskundeleraren (NVvW).

Het thema van dit jaar is: Wiskunde en profil – het gezicht van de wiskunde. Het programma ziet er zeer divers en heel leuk uit. De sprekers zijn:

• Prof.dr.ir. C. Vuik: Iteratieve methoden voor niet-lineaire vergelijkingen
• Prof.dr. J. van Maanen: Wiskundige genieën, (hoe) werden ze opgeleid?
• Prof.dr. J.H. Geuvers: De kunst van het bewijzen
• Dr. P. Grünwald: Kansloos: van Willem Ruijs tot Lucia de B.
• Dr. L. Taelman: RSA
• Dr. M.D.G. Swaen: De ware wiskunde
• Drs. B. Zevenhek: Fibonacci op de universiteit
• Prof.dr. E. Postma: De zaak Zonnebloemen

Zie deze site voor alle informatie die je maar wil over aanmelden, het programma, enzovoorts.

Tot nu toe hebben we de lolcats van de wiskundemeisjes weten te weren, maar met het exemplaar dat Reinie ons stuurde was er geen houden meer aan...

Meer van deze min of meer grappige poezen staan op I can has cheezburger? (niet geschikt voor mensen die van correcte spelling houden).

Op 5 juni werd het boek De Bètacanon gepresenteerd, zoals we toen ook al schreven. Ruben Naeff, wiskundige en muzikant, schreef voor de gelegenheid een Bètacanon om te zingen: Nul, plaattektoniek, wc, voor zangkwartet, twee promovendi en piano quatre-mains.

De uitvoering was erg mooi, dus we zijn ook erg blij dat de canon nu ook te beluisteren is op de site van de Volkskrant. Ook kun je daar een leuk filmpje zien, waarin Ruben vertelt over de totstandkoming van de canon.

En wat misschien nog wel het leukste is: de zeef van Eratosthenes zit ook in de canon! De zeef van Eratosthenes is een methode om alle priemgetallen tot een bepaald getal, bijvoorbeeld 1729, te vinden, en werkt als volgt.

• Eén. Maak een lijst van alle gehele getallen tussen 2 en 1729.
• Twee. Omcirkel 2 en streep alle veelvouden van 2 door: 4, 6, 8, et cetera, tot 1728.
• Drie. Zoek het eerste getal op de lijst dat niet omcirkeld of doorgestreept is. Stop als zo'n getal niet aanwezig is.
• Vier. Omcirkel het getal van stap 3 en streep alle veelvouden van dit getal op de lijst door. Ga daarna terug naar stap 3.

Je begrijpt dat de laatste zin van stap 4 dit algoritme zeer geschikt maakt om in canon te zingen!

Op zoek naar informatie over Farey sequences plukte ik Introduction to number theory van Daniel E. Flath uit de bibliotheek. In de inleiding las ik

My own conscious interest in Diophantine equations goes back to a long winter's night in a St. Louis basement in 1962 when my father and I tried to solve the notorious problem of the monkey and the coconuts as presented by Martin Gardner.

Ik was gelijk benieuwd naar deze blijkbaar beruchte puzzel. Toevallig heb ik de verzamelde columns van Gardner op mijn laptop staan en een zoekopdracht 'monkey coconuts' leidde me naar The Second Scientific American Book of Mathematical Puzzles and Diversions. Ik ga de eerste twee bladzijden van zijn column hier gewoon kopiëren, want beter opschrijven dan Gardner kan ik het toch niet.

In the October 9, 1926, issue of The Saturday Evening Post appeared a short story by Ben Ames Williams entitled "Coconuts." The story concerned a building contractor who was anxious to prevent a competitor from getting an important contract. A shrewd employee of the contractor, knowing the competitor's passion for recreational mathematics, presented him with a problem so exasperating that while he was preoccupied with solving it he forgot to enter his bid before the deadline. Here is the problem exactly as the clerk in Williams's story phrased it:

"Five men and a monkey were shipwrecked on a desert island, and they spent the first day gathering coconuts for food. Piled them all up together and then went to sleep for the night. But when they were all asleep one man woke up, and he thought there might be a row about dividing the coconuts in the morning, so he decided to take his share. So he divided the coconuts into five piles. He had one coconut left over, and he gave that to the monkey, and he hid his pile and put the rest all back together.

By and by the next man woke up and did the same thing. And he had one left over, and he gave it to the monkey. And all five of the men did the same thing, one after the other; each one taking a fifth of the coconuts in the pile when he woke up, and each one having one left over for the monkey. And in the morning they divided what coconuts were left, and they came out in five equal shares. Of course each one must have known there were coconuts missing ; but each one was guilty as the others, so they didn't say anything. How many coconuts were there in the beginning?"

Williams neglected to include the answer in his story. It is said that the offices of The Saturday Evening Post were showered with some 2,000 letters during the first week after the issue appeared. George Horace Lorimer, then editor-in-chief, sent Williams the following historic wire: FOR THE LOVE OF MIKE, HOW MANY COCONUTS? HELL POPPING AROUND HERE.

Wie de rest van de column wil lezen (met daarin verschillende versies van dit probleem én methodes om de oplossing te vinden) moet vooral het boek van Gardner kopen. Enthousiaste lezers mogen (for the love of Mike) natuurlijk ook in de reacties vertellen hoeveel kokosnoten er lagen toen de mannen gingen slapen.

Ik las vorige week alweer een roman met wiskunde erin: Gifted, van Nikita Lalwani.

Het boek gaat vooral over de jeugd van het Indiase meisje Rumi, dat met haar ouders in Cardiff (Wales) woont. Haar ouders zijn opgegroeid in India en naar het Verenigd Koninkrijk verhuisd omdat vader Mahesh daar wilde gaan werken. Hij is wiskundige, en Rumi blijkt wiskundig zeer getalenteerd te zijn. Haar vader besluit haar te begeleiden en zet haar onder een strak studieregime, zodat ze misschien al wel op haar vijftiende naar Oxford kan om wiskunde te gaan studeren.

Rumi is op school een buitenbeentje, maar thuis verwijten haar ouders haar dat ze te ver van de Indiase waarden afstaat. Haar ouders zijn erg streng. Rumi voelt zich sterk aangetrokken tot India, maar wil ook verliefd worden en wat vrijheid. Het boek brengt de eenzaamheid, machteloosheid en het verlangen van Rumi soms pijnlijk goed over. De wiskunde is vooral een achtergrond voor deze kanten van het verhaal.

Edit: Het boek is in het Nederlands verschenen bij De Bezige Bij onder de titel Begaafd.

Het is weer eens tijd voor een fijne puzzel!

Twee robots worden met parachutes gedropt op een lange lijn. De robots laten hun parachute liggen op de plek waar ze landen en kennen maar vier verschillende instructies. Jij moet de robots zo programmeren dat ze elkaar op den duur tegenkomen. Allebei de robots krijgen hetzelfde programma en gaan dat tegelijk uitvoeren. Dit zijn de instructies die de robots kennen:

• Doe een stap naar links.
• Doe een stap naar rechts.
• Ga naar regel [nummer].
• Als je op een parachute staat, doe dan [één van de andere drie instructies].

Een voorbeeld van een programma is

1. Doe een stap naar links.
2. Ga naar regel 1.

Alleen is dit niet zo'n handig programma, omdat de robots hiermee elkaar niet gaan tegenkomen. Met wat voor programma lukt dat wél? De robotjes landen trouwens precies een geheel aantal stappen van elkaar en het programma moet uit een eindig aantal stappen bestaan.

De echte liefhebbers kunnen zich ook afvragen wat er gebeurt als de robotjes landen op een cirkel in plaats van een lijn...

Bij Martijn las ik over GPcode, een nieuw virus waarvan ik hoop dat het nooit op mijn laptop komt. Dit virus versleutelt namelijk je bestanden met het vrijwel onbreekbare RSA (voor de liefhebbers: met een 1024 bit sleutel). Als je niet weet wat RSA is, of hoe het werkt, lees het dan het voortreffelijke artikel Hoe werkt RSA? op Kennislink. Uit dat artikel komt de volgende korte samenvatting van de werking van RSA.

1. Kies grote priemgetallen p en q (minstens 100 cijfers elk).
2. Bepaal de modulus m = p x q.
3. Bereken n = (p-1)(q-1).
4. Kies een vercijferexponent e waarvoor ggd(e,n) = 1.
5. Bereken d zo, dat e x d = 1 mod n.
6. Maak de getallen m en e bekend. Samen vormen die de openbare sleutel.
7. Houd d geheim. Dat is de geheime sleutel.
8. Vercijferen: E(x) = x^e mod m
9. Ontcijferen: D(y) = y^d mod m

GPcode codeert de bestanden met hun openbare sleutel en de makers eisen losgeld voor de geheime sleutel. Wat een schobbejakken! Op Viruslist van Kapersky worden cryptografen opgeroepen om te helpen om de sleutel te factoriseren. Ben jij daar goed in? Surf dan naar het forum en help mee (en let niet op alle onzin die op het forum verschijnt).