Hoofdcategorieën
Device Settings

Wiskundeknobbels kraken honderdtwintig jaar oud probleem

Door Yoeri Lauwers, woensdag 21 maart 2007 18:19
Bron: ABC News, views: 49.409

Achttien wetenschappers zijn erin geslaagd een wiskundeprobleem op te lossen dat zo complex is dat een uitgeschreven versie ervan het eiland Manhattan kan bedekken. De oplossing omvat zestig keer meer data dan het Human Genome Project.

Het probleem werd honderdtwintig jaar geleden geformuleerd door Sophus Lie, een Noorse wiskundige. In de loop van de negentiende eeuw deed hij onderzoek naar geometrische vormen en daarbij vond hij de 'Lie Groups' uit. Een van deze groepen, E8 genaamd, werd in 1887 ontdekt en wordt met zijn 248 dimensies beschouwd als de meest complexe van allemaal. Wetenschappers waren er tot voor kort zelfs van overtuigd dat het probleem niet opgelost kon worden. Hoewel de wetenschappers de afgelopen vier jaar van de straat gehouden werden door Sophus Lie, heeft de berekening vooralsnog geen praktisch nut. De onderzoekers hopen echter dat de opgedane kennis hen kan helpen om andere theoretische problemen op te lossen.

Lie Group E8Een Lie-groep of 'continue transformatiegroep' is een wiskundige verzameling waarop een groepsbewerking gedefinieerd is en waarmee continue symmetrieën gemodelleerd kunnen worden. Een voorbeeld van zo'n continue symmetrie is een rotatiesymmetrie: een vorm die ongewijzigd blijft bij omwenteling. Een spiegeling daarentegen is een niet-continue symmetrie. Tweakers die van voorgaande uitleg geen jota snappen, hoeven zich overigens niet te schamen want volgens professor Jeffrey Adams, een van de wetenschappers, zijn Lie-groepen zo complex dat zelfs de meeste wiskundigen ze niet begrijpen.

Volgende 18:48 EU-wetvoorstel om downloaden te criminaliseren afgekeurd
Vorige 17:28 Commissie wil hogere royalty's webcasts heroverwegen
Advertentie

Reacties

«  1  2  3  4  5  »

Tweakers die van voorgaande uitleg geen jota snappen, hoeven zich overigens niet te schamen want volgens professor Jeffrey Adams, een van de wetenschappers, zijn Lie-groepen zo complex dat zelfs de meeste wiskundigen ze niet begrijpen
dus: ik ben niet dom :P

Wat zijn wiskundigen? :?

Dat zijn mensen die niet in de gaten hebben dat wiskunde een werktuig is, en niet een doel.

die probleemjongeren van tegenwoordig :Y)

Wat is er met die probleem jongeren? wil je zeggen dat die allemaal dom zijn of zo?

volgens mij niet (
-wil hij dat niet zeggen
-dat vind ik niet
)

wtf? iemand voelt zich op de tenen getrapt!

Ik snap niet wat het plaatje hier mee temaken heeft
rotatiesymmetrie: een vorm die ongewijzigd blijft bij omwenteling. Een spiegeling daarentegen is een niet-continue symmetrie.
oke maar denk dat dit iets anders word bedoelt als het
plaatje waar je hoofdpijn van krijgt :Y)

Ik zou het plaatje ook niet echt proberen te snappen, want het weergeven van objecten met meer dan 4 dimensies is ontzettend lastig. Een object met 4 dimensies is bijv. een draaiende kubus.

Een object met 4 dimensies is een 3 dimensionaal object in een tijdlijn.

Als je het hebt over een 4D kubus, die wordt ook wel hypercube of iets specifieker tesseract genoemd, en dat is zeker geen draaiende kubus!

gamepower2005 bedoelt dat de kubus beweegt, wat overeenkomt met een 3 dimensionaal object in de tijd: het verandert van moment tot moment, dus het beweegt.

Jullie zeggen dus allebei hetzelfde ;)

Tijd is geen dimensie, dat is een verzinsel van bepaalde wetenschappers, wat door velen ook weer wordt ontkend.

Tijd is niets anders dan een hersenspinsel van de mens wat is gebaseerd op het rondwentelen van de aarde om zichzelf en om de zon.
Oftewel, pure beweging wat zich gewoon afspeeld in de voor ons gewoon bekende 3 dimensies.

Als je een 4-D object doorsnijdt met een verschuivende 3-D slice (ruimte/tijd) krijg je bewegende vormen.

Dus een tesseract is een kubus die ineens verschijnt, dan na een poosje weer verdwijnt. Vergelijk het met een kubus die je doorsnijdt waar je alleen het 2-D snijvlak ziet.

Een roterende kubus zou een hele andere, vreemd gedraaide 4-D vorm hebben (dit gaat mijn voorstellings vermogen ver te boven)

@mariusjr
De relativiteitstheorie niet gelezen? Tijd = massa, zonder massa dus geen tijd, dus in de ruimte (minder massa) gaat de tijd trager dan bijv. op aarde.

Ok das allemaal heel mooi nieuws ;) Kunnen wij Tweakers nu snellere processors verwachten of iets dergelijks? Of gaat dit verder echt nergens over?

@ Keesjelief: Je hebt helemaal gelijk, misschien moest ik me iets duidelijker uitdrukken. Ik bedoelde, zoals je zei, met mijn zin dat ik geen directe toepassing zie, daar moet ik aan toevoegen dat ik daardoor ook niet het directe nut van deze nieuwspost op Tweakers zie.

Deze voor het merendeel van de tweakers onbegrijpelijke post duid er dus alleen op dat de ontdekking misschien nog in de toekomst van pas kan komen (dat kan ook voor iets zijn wat totaal niets met Tweakers te maken heeft).

Maar misschien kan iemand anders me het nut van deze post hier op Tweakers uitleggen.

Veel mensen (waaronder ook de nieuwsposter en de poster hierboven blijkbaar) lijken meteen te vragen naar toepassingen en indien die niet direct bestaan de ontdekking maar te beschouwen als iets irrelevants wat ze alleen maar belastingcentjes kost of iets dergelijks.

Ik zou die mensen vriendelijk willen aanraden eens verder te kijken dan de neus lang is en zich te realiseren dat véél wiskunde in eerste instantie 'slechts' intrinsieke waarde lijkt te hebben, maar dat het regelmatig voorkomt dat in latere tijden, soms in totaal onverwachte hoek, er een toepassing opduikt. Anders gezegd, als we voortaan alleen nog waarde hechten aan wiskunde die direct praktisch toepasbaar is leidt dat (buiten andere bezwaren) in de toekomst óók tot een verschraling van de toegepaste wiskunde door het niet meer beschikbaar zijn van al gedaan theoretisch onderzoek naar objecten die opeens opduiken.

Eensch. Maar desalniettemin blijft het goed om kritisch te staan tegenover dit soort onderzoeken en oplossingen. Het nut van het kraken van RC-56 (hoewel geen wiskunde, wel een goed voorbeeld) ontging me, daar theoretisch al bewezen is dat het opgelost kan worden.

Het nut van kraken wordt mischien duidelijk als je bedenkt dat RC-56 een mogelijke candidaat was als 'veilige' methode om te versleutelen. b.v. jou creditcard gegevens enzo die je over inet verstuurd worden versleuteld.

Welk nut? Wat toon je aan? Eigenlijk helemaal niks. Het is niet alsof je met z'n allen de juistheid van het algoritme aan het testen bent. Je bent niet op zoek naar gaten.

Het enige wat er gedaan wordt is gewoon alle mogelijkheden bij langs gaan om te kijken of je de juiste sleutel hebt. Ja, als je lang genoeg rekent met genoeg rekenpower vind je die vanzelf, maar dat betekent niet dat je iets ontdekt hebt ofzo. De wiskundigen die de encryptie bedacht hebben wisten dit al vanaf dag 0. De hele essentie van het algoritme is dat je zo enorm veel rekenkracht nodig hebt om 1 bericht te kraken! Na al dat rekenwerk is RC-56 nog net zo veilig als daarvoor. Er is 1 bericht gekraakt, maar alle andere communicatie is nog net zo veilig als daarvoor.

Je toont aan hoveel tijd er overheen gaat met een bepaald hoeveelheid computerkracht om alle combinaties langs te gaan.

Het hele principe dus van brute-force... Op hedendaagse computers met behoorlijk wat (eigen) wiskundig inzicht kan je een manier opzetten die mbv jou methode er nog korter over doet. Het blijft wel proberen .. maar als iemand binne 15 minuten elke keer de sleutel kan vinden op die manier ... wordt het behoorlijk onveilig

Precies. Ter aanvulling: toen Riemann zo rond 1850 zijn topologie (vorm van wiskunde) zeiden sommige geleerden: Dat is prachtige wiskunde maar helaas niet toepasbaar. Het werd dan ook 50 jaar lang "vergeten" totdat Einstein tegen een problem aanliep dat hij maar niet kon oplossen. Via een kennis kwam hij in aanraking met Riemann's topologie en hij zag meteen dat dat het was wat hij zocht. Vervolgens kon Einstein zijn relativiteitstheorie opstellen.

http://nl.wikipedia.org/wiki/Riemann

Het stukje "vooralsnog geen praktisch nut" zegt imo precies genoeg.

Ten tweede:
De onderzoekers hopen echter dat de opgedane kennis hen kan helpen om andere theoretische problemen op te lossen.
En dat is dus precies weer hetgeen jij zegt: er duikt wellicht later een toepassing op.

Oke, ik ben één van die tweakers die er geen snars van snapt.
met name dit stukje vind ik pretty vaag:
Een van deze groepen, E8 genaamd, werd in 1887 ontdekt en wordt met zijn 248 dimensies beschouwd als de meest complexe van allemaal.
248 dimensies(?!), ik ben nooit verder gekomen dan 4.

Edit: Oké, ik kom al tot de 11e dimensie http://nl.wikipedia.org/wiki/M-theorie :+

In wiskunde wordt zelfs vaak gewerkt met oneindig dimensionale ruimtes. Denk bijv. aan een ruimte die bestaat uit elementen die gevormd worden door oneindige rijtjes van getallen (x_1,x_2,...).

Afgezien daarvan ligt de Fourier-transformatie, theoretisch ook met oneindig veel demensies, aan de grondslag van de mp3's (Fourier was Franzoos uit de eind 18e/begin 19e eeuw trouwens, jammer dat hij de mp3's nooit heeft kunnen meemaken)
Alleen heeft men bij mp3's het aantal dimensies teruggebracht tot het bereik van de miniamele en maximale frequentie die het oor kan horen, waarbij iedere dimensie een frequentie vertegenwoordigd (simpel gezegd).

Simpeler kan, hoor: in je oor en in een equalizer gebeurt er ook een fourier-transformatie (die `blokjes' die op en neer gaan met de muziek zijn coefficienten van een Ftransform).

Dimensies zijn overal, ook als je ze niet als dusdanig herkent --- een landkaart die kleuren gebruikt om hoogte aan te geven, is 3D hoewel plat.

Op het eerste zicht lijkt stress in een 3D object mij al 6D omdat je in drie richtingen kunt `trekken' aan een object, plus rond 3 assen torsie uitoefenen?

@ Marvin:
Da's eigenlijk ook in principe nog 'meer dimensionaal': denk aan de grenzen tussen atoomstructuren (granen) in een metaal bijv. en nog meer dingen.

Ligt er maar aan waar je de grens trekt gewoon :)

temperatuur kan ook een dimensie zijn, of de absorbtie graad, of de hardheid, of de kleur, of de vorm, of de electronenconfiguratie etc. etc. etc.

Alles wat over meerdere coordinaten kan voorkomen is een dimensie.

In programmeertalen kun je in formules ook dimensies meegeven:

functie x(dimensie1, dimensie2, dimensie3 etc)

Het hele idee achter transformaties voor compressies is dat als je in een ander domein data kwantiseert en weer terugtransformeert, dit subjectief voor ons als mens weinig verschil geeft met de oringinele data. Zo'n transformatie is in sommige gevallen een Fourier transformatie, maar voor video bv. wordt een discrete cosinus transformatie gebruikt. Maar je kan het zo nauwkeurig (en complex) of onnauwkeurig (makkelijk) maken als je wil.

En een dimensie is niets meer dan een parameter die onafhankelijk (orthogonaal) is van andere dimensies. Als je bv. vooruit loopt (x-richting) heeft dit niets te maken met hoe je opzij loopt (y-richting) of je hoogte (z-richting). Zo heeft ook de temperatuur van je koffie niets te maken met de bandenspanning van je fiets of auto en dit kan je dan dus ook zien als twee dimensies. (klinkt eigenlijk wel grappig haha!)

@kidde: De Fourier-transformatie oneindig veel dimensies??? Hoe kom je er bij?

Bij mp3 is de frequentie gewoon 1 dimensie. Pure onzin dat iedere dimensie een frequentie vertegenwoordigt.

Bij mp3 is de frequentie gewoon 1 dimensie. Pure onzin dat iedere dimensie een frequentie vertegenwoordigt
Je leest het vekeerd: de frequentie is géén dimensie; iedere dimensie vertegenwóórdigt één frequentie. Het werkt als volgt:
f(x)=lim n→∞{ a1*sin(1x)+a2*sin(2x)+a3*sin(3x)+... ...+an*sin(nx) }
Hierbij is f(x) de vectorruimte, en iedere ansin(nx) een van de basisvectoren, dus is an een dimensie (eigenschap) die bij een bepaalde frequentie (nx) hoort (vool alle verschillende n is sin(nx) orthonormaal); althans, zo is het mij ooit geleerd door een wiskundig docente aan de uni Leiden. De = is alleen een echte = als n naar oneindig gaat (vandaar het oneindig aantal dimensies), maar des te hoger n is, des te hoger de frequentie, dus boven de frequentie van het menselijk gehoor kan je stoppen. Mogelijk kijken natuurkundigen er anders tegenaan.

Dat hoeven niet ruimte en tijd dimensies te zijn.

Net zoals de database die ik laatst ontworpen heb en 7 dimensies heeft. Aangezien mijn collega's alleen met Excel overweg kunnen, en Excel maar twee dimensies kent (rijen en kolommen) zijn ze lekker aan het puzzelen :Y)

meer info: http://en.wikipedia.org/wiki/Dimensional_database

Ben ik heeeel benieuwd waar jij 7 dimensies voor nodig hebt :Y)

Eh... Excel kent wel degelijk drie dimensies. Je kunt namelijk meer dan één werkblad aanmaken, zelfs in hetzelfde bestand. Daarmee creëer je een derde dimensie.

Dat hoeft niet. Een matrix kan al oneindig veel dimensies beschrijven. Iedere colom is bijvoorbeeld een dimensie. Een rij met getalletjes beschrijft voor iedere dimensie een getalletje. Vooral nuttig als je eigenvectoren gaat bepalen en dimensiereductie gaat doen. Je kunt dan in een handomdraai de dimensies overhouden die het meeste van de ruimte die de data opspant omvat. Ook wel bekend als Principle Component Analysis.

Nog even een toevoeging op het begrip dimensies

Wiskundig gezien is een dimensie gewoon een variabele. Als je bijvoorbeeld de prijs van een pc uitrekent met:
prijs = prijs kast + prijs moederbord + prijs gk * aantal gk's + aantal manuren * prijs per manuur
Dan heb je al een vergelijking met 6 variabelen, ofwel 6 dimensies. Veel dimensies is dus helemaal niet bijzonder. Zie bijvoorbeeld ook de posts van kidde over mp3's en van Xenan over een database.

Als je het gaat hebben over ruimte, of over het afbeelden van een vergelijking met veel variabelen, dan is het werken met veel dimensies opeens heel lastig. Wij kunnen ons bij 4 ruimte-dimensies nog net wat voorstellen, maar daarboven niet.

Wat er bij de Lie groep met dimensies bedoeld wordt weet ik niet precies, maar ik weet wel dat je met veel dimensies al snel heel complexe dingen kunt maken, als je meerdere vergelijkingen op moet stellen. (mijn voorbeeld met de pc had maar 1 vergelijking, waardoor het heel eenvoudig bleef. Het wordt al lastiger als de prijs van de manuren weer af zou hangen van de totaalprijs van de pc of zoiets)

Wij kunnen ons bij 4 ruimte-dimensies nog net wat voorstellen, maar daarboven niet.
Heb ik eerder gehoord ja, zelfs van een docent lineare algebra. Het kan wel volgens, maar het is makkelijker als je de dingen in je hoofd terugvertaald naar 3d structuren. Bijv 5d: eerste stap een xyz coordinaat (3d), op iedere coordinaat ligt een bol met een bepaalde straal en kleur (5d).

Maargoed dat werkt natuurlijk maar tot een bepaald vlak: als je een enkel punt bekijkt. Als je bovenstaand voorbeeld in een serie van 1000 antwoorden bekijkt wordt het al een stuk lastiger om bij te houden ;-)

Edit: zie ook voor een dergelijk idee (maar dan voor theoretische natuurkundige dimensies, daar gaat dir probbleem natuuurlijk niet over) http://www.tenthdimension.com/medialinks.php (verder naar beneden gepost door KrissCross)

correctie: niet straal, maar bvb materiaalsoort. een bol wordt namelijk in dezelfde 3 dimensies gedefiniëerd als zijn de de 3-dimensionale afstand tot een punt. kleur is wel een goede 4e of 5e dimensie (die dan weer uit verschillende dimensies is opgebouwd)

In de wiskunde is een dimensie niets meer dan een vrijheidsgraad; natuurkundig ken je drie dimensies vrij goed, alles kan een x, y en z coördinaat hebben. Dus drie vrijheidsgraden, 3 dimensionaal. Maar je hebt bijvoorbeeld een boodschappenlijstje, 2 ei, 1 boter, 3 melk en 2 karbo's, dat zijn 4 niet optelbare elementen, en je boodschappenlijstje is dus 4 dimensionaal. (je kan het in een viervector uitdrukken (3,2,4,2). Dimensies hoeven dus niet spatiaal (ruimtelijk) te zijn.

edit: hmm. ben niet de enige met verduidelijking. Overigens dat filmpje van tenthdimension.com is niet erg goed doordacht vanuit een fysisch perspectief.

Zou iedereen alsjeblieft willen vergeten dat ze ooit van tenthdimension.com gehoort hebben. Het verhaal wat daar vertelt wordt heeft geen enkele relevantie voor het begrip dimensie. Zowel in de natuurkunde als in de wiskunde. Wiskundig gezien is het zelfs kin klare onzin. (Om maar een voorbeeld te noemen het gene dat in dat filmpje "de vijfde dimensie' (misschien was het zesde zou ik het filmpje nog eens voor moeten terug zien) gemoent wordt is wiskundig gezien alweer een oneindig dimensionaal object. In iedergeval met de meest gangbare definities van dimensie, maar geen definitie die ik ooit gehoord heb zou aan dat gene 5 dimensies toekennen.)

Helaas heeft de link in kwestie een grote verspreidingsgraad. (zo groot dat hij in vrijwel elke discussie over dimensies opduikt.) Er worden daarmee veel mensen op het verkeerde been gezet. Ik zou daarom iedereen hartelijk willen verzoeken deze link niet steeds weer te posten.

(Om eerlijk te zijn, het filmpje is niet helemaal slecht tot een dimensie of drie a vier geeft het een redelijkt idee over hoe je over diminsies na kan denken. Echter wat daarna komt slaat gewoon nergens op.)

Als je het boek gelezen zou hebben dan zou je dit niet zeggen. Dat filmpje is maar een introductie van het eerste hoofdstuk van 'Imagining the Tenth Dimension'.

Het is een filosofisch boek dat enkel probeert een idee te geven hoe wij met onze beperkte mogelijkheden om in meer dan 4D te denken. Nergens pretendeert de auteur dat het gaat om de realiteit.

Realiteit heeft niks met wiskunde te maken.

En de auteur pretendeerd weldegenlijk iets te zeggen over hoe je kan denken over het (wiskundige) begrip dimensie. Hij faalt hier echter door ten toon te spreiden dat hij niks van het concept heeft begrepen.

Filosofie bedrijven is geen vrij brief om met wollige bewoordingen vaag te zijn over wat je bedoelt. (Hoewel als je naar de europese filosofie kijkt je soms anders zou geloven.)

Spirograaf voor geleerden :+

Maar wát hebben ze nu opgelost ? Een formule om zo'n ding te tekenen ?

Dat kunnen ze op internet al lang...

Een spirograaf is iets anders dan Lie Groep.

Maar als je met die reactie komt, ga ik al niets eens een poging nemen om het duidelijker te maken.

Veel mensen kunnen gewoon niet zo abstract denken. laat staan in zoveel dimensies.

Toch niet. Leuk voorbeeld. De spirograaf is precies het goede voorbeeld. Je beweging is symmetrisch.......

f*ck, hoe leg ik dat uit. Ik zie het wel maar kan het niet uitleggen.

Iemand?

@G3rtjuh:
Jouw reactie doet me denken aan een uitspraak van een professor die ik altijd heb onthouden:

Als je een theorie niet uit kan leggen aan je moeder, dan begrijp je 'm zelf niet goed.

Als jij daadwerkelijk Lie groepen begrijpt, dan zou het geen probleem voor je moeten zijn om het voor Mr1ncr3d1bl3 duidelijker te maken waar het om gaat.

Staat al in het bericht dat we er lekker helemaal niks aan hebben. Dus eigenlijk snap ik ook niet waarom ze de moeite hebben genomen om het op te lossen. Behalve om het te 'kunnen;

Dat heeft wel zijn waarde, in de snarentheorie oa.

Een voorbeeld van zo'n continue symmetrie is een rotatiesymmetrie: een vorm die ongewijzigd blijft bij omwenteling.
een bol?

een bol heeft daarentegen maar 3 dimensies, geen 248

Je kunt in een Euclidische ruimte van willekeurige dimensie n een bol definiëren, nl. als de verzameling van alle punten die dezelfde norm ("afstand tot de oorsprong") hebben.

Edit: grappig gemod? :?

Of een cilinder of een vaas of ... , maar dan in 248 dimensies.


is het voor jou pas nuttig als er "weer sneller geheugen" mee kan worden ontwikkeld of zo?

de wereld is wiskunde, het heelal is wiskunde, imo is het interessanter hier geld in te stoppen dan in een nieuwe gevechtshelicopter
«  1  2  3  4  5  »

Op dit item kan niet meer gereageerd worden.

Volgende 18:48 EU-wetvoorstel om downloaden te criminaliseren afgekeurd
Vorige 17:28 Commissie wil hogere royalty's webcasts heroverwegen
VNU Media logo Hosted by True

© 1998 - 2012 Tweakers.net B.V. - Alle rechten voorbehouden - Contact - Jouw privacy - Algemene Voorwaarden

Uitgever van:

Website van het jaar 2011