Thomas Kahle
In dieser Folge beschäftigen wir uns mit kombinatorischen Problemen, die aus der Elektrotechnik stammen. Ein Golomblineal ist ein dünn besetztes Lineal, auf dem jede Länge nur an maximal einer Stelle abgelesen werden kann. Eine mathematische Variante davon sind die Sidonmengen und es wird euch erleichtern in der SZ zu lesen, dass es Sidonmengen gibt, sodass jede hinreichend große Zahl als Summe von 3 Zahlen daraus geschrieben werden kann. Ach ja und dann kann man das Ganze noch zwei-dimensional machen. Als Hausaufgabe gibt es was mit Schach, dazu müsst ihr aber bis ganz zum Ende hören.
- GameDevTycoon
- Solomon Golomb
- Math Genealogy of Solomon Golomb
- Rep-Tiles
- Cheskers
- Golomblineale
- Golomb-Folge
- Suche nach optimalen Golomb-Linealen auf distributed.net
- OGR-28 ist fertig.
- SZ Artikel (mit Paywall)
- Cédric Pilattes Preprint
- Costas-Arrays
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Automatisch generiertes Transkript (nicht geprüft)
Hallo, herzlich willkommen zu einer neuen Folge Eigenraum, schön, dass ihr wieder eingeschaltet habt.
Mein Name ist Thomas, ich bin Mathematiker und ich denke, dass es nicht genug Mathe-Podcasts gibt.
Und deswegen mache ich hier den Eigenraum.
Und ihr habt eingeschaltet trotz dieses seltsamen Titels. Ich habe der Folge keinen sehr verlockenden Titel gegeben, also schon wieder einen Fehler gemacht für meine Reichweite.
Die Downloadzahlen spiegeln irgendwie immer die Attraktivität des Titels wieder, denke ich.
Wenn man eine Folge Chat-GPT nennt, dann hat das gleich andere Auswirkungen als Gulump, Sidon und Kostas.
Die Folge mit den wenigsten Downloads bisher war übrigens diese Mathe-Jogging-Folge.
Also falls ihr die noch nicht gehört habt, könnt ihr euch die ja nochmal hören oder
wenigstens runterladen.
Dann seht ihr das in den Downloadzahlen. Das ist ja sowieso so, ich tracke euch ja nicht, außer wenn ihr das auf Spotify hört,
was ich nicht so richtig empfehlen kann.
Also wenn ihr es auf einer richtigen Podcast-App hört, dann werdet ihr nicht getrackt und
ich sehe nur, dass es jemand runtergeladen hat und nicht, weil ihr eingeschaltet habt
und ob ihr es gehört habt oder sowas.
Ich denke, die Mathe-Jogging-Folge ist gar nicht so schlecht.
Ihr könntet sie nicht nur runterladen, sondern auch anhören.
Aber vielleicht hab ich mit dem Titel Mathe-Jogging gleich zwei Zielgruppen verschreckt.
Also Mathe und Sport.
Wer Mathe nicht mag, würde hier nicht einschalten, aber wer Sport nicht mag, vielleicht doch.
Kennt noch jemand dieses Spiel Game Dev Tycoon? Das hab ich 2013 gespielt.
Jetzt hat eins meiner Kinder das wieder entdeckt.
Wir haben das noch mal gespielt, zum zehnjährigen Jubiläum. und entwickelt Computerspiele.
Da kommt's immer drauf an, die richtigen Kombinationen von Thema und Spielprinzip zu finden.
Vampir-Wirtschaftssimulationen funktionieren dann nicht so gut wie ein abstraktes, matte, casual Game auf dem Game Boy oder so.
Na ja, die Hörerin, die man wegen des Titels verloren hat, die holt man mit dem Inhalt nicht rein.
Deswegen ist es wichtig, einen guten Titel zu wählen. Ich werd mich anstrengen, beim nächsten Mal
einen attraktiveren Titel zu wählen, damit ihr, die ihr nicht eingeschaltet habt, das wieder hört.
Schluss. Sidon, Goulomb, Kostas, das sind Namen von Mathematikern. Ihr habt es euch vielleicht schon gedacht.
Leider nicht von Mathematikerinnen, sondern von Mathematikern.
Und in der Mathematik hat man ja sehr viel, dass so alles irgendwie nach Leuten benannt wird.
Also beim Arzt ist das jetzt zum Beispiel nicht so.
Wenn der Arzt dann nicht sagen würde, sie bekommen Antibiotikum gegen ihre Lungenentzündung,
dann würde er sagen, sie bekommen Gaustherapie gegen ihre Euler-Krankheit oder so,
wenn da auch alles nach Leuten benannt werde.
Aber so ist es eben in der Mathematik. Die waren unterschiedlich bekannt und aktiv.
Der bekannteste und aktivste war Solomon Golomb. Das war ein amerikanischer Mathematiker und Ingenieur.
Der ist 2016 gestorben, also noch gar nicht so lange her.
Der hat 25 Doktortöchter und Söhne und schon 81 Promotionsnachfahren, also in dieser mathematischen Genealogie,
der großen Stammfolge im Sinne von Promotion.
Also da kann man viel mehr Söhne und Töchter haben, als man biologisch haben kann.
Obwohl das, ach naja, da will ich jetzt nicht so genau drüber spekulieren.
Also jedenfalls hat er 81 Promotionsnachfahren.
Also Leute, die bei ihm promoviert haben oder promoviert haben bei Leuten, die bei ihm promoviert haben. Und so weiter. und.
Der war auch sehr an so Spielen interessiert, also war nicht nur ein Mathematiker und Elektrotechnik-Professor,
sondern der hat auch Spiele erfunden.
Zum Beispiel gilt er als der Erfinder von Reptiles. Das sind so Puzzle, so geometrische Figuren, die sich zerlegen lassen,
so ähnlich wie Paketierungen aus der letzten Folge, in kleinere Versionen von sich selbst.
Verlinke ich euch mal. Außerdem hat er ein Spiel erfunden, was eine Mischung aus Schach und Dame ist.
Und weil Schach auf Englisch Chess heißt und Dame Checkers, hat er es Chesscores genannt.
Das habe ich auch noch nicht gespielt.
Außerdem hat er Pentominus erforscht. Das sind so Analoge von Tetris-Steinen, aber mit fünf Quadraten, wie das Pent in Pentomino
naheliegt.
Angeblich soll diese Arbeit über die Pentominus, also welche gibt es davon und wie viele und
so, sogar Tetris inspiriert haben.
Aber ich weiß ja auch nicht so genau, ob das stimmt. So Simon Sidon war ein ungarischer Mathematiker, der ist 1941 schon gestorben und hat angeblich
sehr zurückgezogen gelebt.
Sein Wikipedia-Eintrag ist auch nur ungefähr zwei Zeilen lang und laut der mathematischen
Genealogie, die es übrigens auch im Internet gibt, hatte er keine Nachfahren, keine Doktorsöhne
oder Töchter. Aber Paul Erdös soll jedenfalls mal gesagt haben, dass er ein verrückterer
Mathematiker als der Durchschnittsmathematiker sei. Also das soll, glaube ich, jedenfalls
positiv sein. Das habe ich in der Süddeutschen Zeitung gelesen. Aber da kommen wir gleich
noch dazu. Und dann gibt es noch John Costas. Das war noch ein amerikanischer Mathematiker
und auch Elektroingenieur. Und der ist 2008 gestorben und hatte auch keine Promotionsnachfahren.
Und um die drei soll es jetzt gehen. Und zwei von denen sind Elektroingenieure.
Komisch, oder? Also heute geht es mal los mit ein bisschen Elektroingenieur-Gewesen.
Und deswegen tauchen wir jetzt mal ein bisschen ein in die Messtheorie.
Aber nicht irgendwelche Spannungen oder Felder oder sowas, sondern was viel Einfacheres.
Lineale.
Ihr kennt ja sicher lineale. Also so ein Stück aus Holz aus der Schule, auf dem irgendwie Markierungen sind.
Zum Beispiel jeden Millimeter oder jeden Zentimeter eine Markierung.
Und dann kann man das irgendwo dran halten und sehen, wie lang was ist.
Und ist euch schon mal aufgefallen, wie ineffizient so ein normales Lineal ist?
Sagen wir mal, wir wollen jetzt nur so ganze Zentimeter Strecken abmessen.
Wenn ich hier einen Zentimeter abmessen will, dann kann ich meine Strecke auf dem Lineal von 0 bis 1 da dran halten.
Oder ich kann meine Strecke von 1 bis 2 da dran halten. Oder meine Strecke von 2 bis 3.
Also diese Strecke 1 Zentimeter lang, die ist total oft markiert auf meinem Lineal.
Viel öfter, als ich es eigentlich brauche. Denn wenn ich 1 Zentimeter messen will, brauche ich ja nur eine von diesen Stellen.
Ich weiß gar nicht, ob das was über den Charakter aussagt, also welche man dann nimmt.
Es gibt bestimmt Leute, die, wenn die 1 Zentimeter messen wollen, die dann immer von 0 bis 1 messen.
Und manche, die irgendwie mal von 3 bis 4 und mal von 5 bis 7 messen.
Naja, und da fragt man sich natürlich, habt ihr bestimmt auch schon mal gemacht,
kann man das auch effizienter machen? Stellen wir uns mal ein Lineal vor, was so
Länge 6 hat. Und wir wollen jetzt mal nur Zentimeter messen, also keine Millimeter
oder so. Und auf dem Lineal, stell ich mal vor, also so einem 6 cm langen Lineal,
und da gibt es aber nur vier Markierungen. Und die Markierungen sind bei 0, also am
Anfang. Bei 6, also am Ende, sind so Striche. Also das Holz geht ja noch ein bisschen weiter
immer hinter dem letzten Strich unter. Und dann noch bei 1 und bei 4. Und damit meine
ich also, die alte, also alle Markierungen sind weg, aber dann da, wo früher die 1 war,
ist eine Markierung, und da, wo jetzt früher die 4 war, ist eine Markierung. Und das Lineal,
behaupte ich, ist ziemlich nützlich, um Zentimeter zu messen. Weil die Länge 1, die kann ich
nämlich zwischen 0 und 1 messen. Die Länge 2 kann ich auch messen, die ist nämlich zwischen
4 und 6. Die Länge 3 kann ich auch messen, zwischen 1 und 4. Und die Länge 5 kann ich
auch messen, die ist zwischen 1 und 6. Und die Länge 6 kann ich auch messen, das ist
nämlich die Länge des Lineals von 0 bis 6. Also alle Längen in Zentimetern von 1 bis 6,
kommen vor. Und keine kommt doppelt vor. Also wenn ich jetzt alle Abstände, die ich überhaupt mit
meinem Lineal messen kann, betrachte, also immer alle Abstände zwischen zwei Markierungen betrachte,
dann kommt gar keine Doppelt vor. Also niemals, wenn ich n Zentimeter abmessen.
Will, bin ich vor die Wahl gestellt, welche von den n Zentimeter Markierungen
auf meinem Lineal will ich überhaupt nehmen. Das ist doch sehr effizient, oder? Und das
ist die Definition eines Goulomb Lineals. Ein Goulomb Lineal, benannt nach dem
Mathematiker Solomon Goulomb, von dem ich euch oben erzählt habe, der vielleicht
Tetris mit beeinflusst hat, der hat sich mit sowas beschäftigt. Und ein Golomb-Lineal ist
also ein Lineal, also Markierung, auf einem Holzstück, sodass keine Länge doppelt vorkommt.
Dass jetzt bei meinem kleinen Beispiel jede Länge genau einmal vorkommt, das ist noch
eine Zusatzeigenschaft.
Leider, leider kann man das nicht immer verlangen. Leider, leider, leider gibt es kein Lineal mit 5 Markierungen, mit dem man alle Längen,
bis zu seiner Länge, was auch immer die dann sein mag, genau abmessen kann.
Aber jede auf genau eine Art und Weise. Also man muss sich entscheiden, entweder ich kann jede Länge abmessen, dann gibt es manche
aber doppelt, oder ich will jede Länge nur höchstens einmal haben.
Wir machen das zweite. Jeder Länge höchstens einmal vorkommt und sowas nennen wir ein Golomb-Lineal,
nach Solomon Golomb. Und dieses Lineal mit den fünf Markierungen, das hat dann Länge
11. Also man kann sich jetzt fragen, was ist das kürzeste Lineal? Also wenn ich mir vorgebe,
dass ich fünf Markierungen haben will, was ist dann das kürzeste Lineal, sodass keine,
Länge doppelt vorkommt? Und diese Markierungen, die glaube ich nur an die ganzen Zentimeter-Stellen
Also sowas mit reellen Zahlen oder sowas, hier sind jetzt ganz zahlige Abstände gemeint
und wir kommen in keine Schwierigkeiten mit reellen Zahlen.
Und das hat tatsächlich Anwendung in der Elektrotechnik. Also das tritt beim Verstärkerbau oder Verteilung von Frequenzen in einem Frequenzband auf.
Ich bin jetzt ein bisschen auf dünnem Eis, aber da gibt es irgendwie den Begriff der
Intermodulationsverzerrung, vielleicht finde ich sehr bald noch was über diesen Begriff heraus.
Und der tritt auf, wenn zwei oder mehr Signale miteinander interagieren und dadurch neue
Frequenzen und Signale erzeugen, die nicht in den ursprünglichen Signalen vorhanden waren.
Also zum Beispiel die Summe von zwei Frequenzen oder die Differenz von zwei Frequenzen, die
tritt dann auch auf. Und wenn jetzt man so mehrere Signale mischt und man hat dann bei verschiedenen Kombinationen
mehrfach die gleiche Summe, dann würde diese Störung sich noch verstärken.
Also wenn man zweimal die gleiche Summe hat oder zweimal die gleiche Differenz, dann würde,
die Störung sich noch verstärken.
Dann verstärkt sie es noch. Und wenn man dann seine Frequenzen so entlang eines Kolumb-Lineals tut,
dann tritt es eben nicht auf, dass die Störungen sich noch gegenseitig verstärken.
Und das hört sich dann irgendwie besser an oder im WLAN gibt es weniger Störungen.
Und das ist eigentlich interessant, weil es ist ein mathematisches Problem,
was ganz anders erzählt wird als das, was man ursprünglich machen will.
Also man will irgendwie so einen Kanal optimal ausnutzen. Ich habe irgendwie meinen Kanal, die Frequenzen, möglichen Frequenzen für meine WLAN-Übertragung
und will da jetzt ein paar Frequenzen auszeichnen. Und wie soll ich die wählen?
Dass Störungen möglichst minimiert werden. Führt dann auf so eine Art kombinatorisches Problem eigentlich. Also ein ganz diskretes Problem.
Also gehen wir noch mal zurück zu unserem Beispiel der Länge 6. Das nennt man
übrigens ein perfektes Golomb-Lineal. Also da hat man die Markierung 0, 1, 4, 6
und wir können auch alle Längen von 1 bis 6 da abmessen.
So was gibt es dann mit fünf Markierungen eben nicht mehr. Die Anzahl der Markierungen nennt man übrigens die Ordnung eines Lineals.
Also man hat diese Golomb-Lineale und die haben dann immer eine Länge und eine Ordnung.
Ordnung ist die Anzahl der Markierungen, Länge ist eben wie lang sie ist, wie weit ist es
vom ersten bis zum letzten.
Und mit fünf Markierungen stellt sich dann eben raus, wie man zeigen kann, dass man eine Länge 11 braucht.
Und das Optimum ist, die Markierungen zu machen an 0, 1, 4, 9, 11 und ihr könnt das gerne
zu Hause ausprobieren, dann kann man nicht mehr alle Längen finden bis 11, die 6 fehlt,
nämlich. In der Mitte fehlt die 6.
Man kann also auch noch so eine Art Effizienz definieren, die fragt dann, wie viele von
den Längen, die möglich wären, kommen auch wirklich vor.
Weil die Definition war ja, dass man will, jede Länge höchstens einmal haben, und dafür
hat man dann nicht alle, und die Effizienz fragt eben, wie viele kommen vor.
Und bei diesen 5 Markierungen hat man eben die 6 nicht, da 1 von 11 fehlt.
So, und wenn man das jetzt immer länger macht, ist diese Effizienz, die geht so gegen 60 Prozent ungefähr.
Und das ist das mathematische Problem, mit dem wir uns jetzt mal noch so ein bisschen beschäftigen wollen.
Das ist übrigens ein computerzugängliches, wie soll ich sagen, ein berechenbares Problem,
also wenn man sich die Anzahl der Markierungen vorgibt, dann kann man auch das kürzeste
Golomb-Lineal berechnen.
Oder die kürzesten, wenn es mehrere gibt. die Golomb-Lineale sind und diese Anzahl von Markierungen haben.
Und das ist auch eine interessante Geschichte der Citizen Science, die Webseite distributed.net,
das ist auch eine sehr alte Webseite, die hat nämlich so Clients veröffentlicht,
mit denen man zu Hause sich beteiligen konnte an der Suche nach solchen optimalen Golomb-Linealen.
Und alle längsten Golomb-Lineale, längsten optimalen Golomb-Lineale, die man kennt,
sind von dieser Internet-Suche gefunden worden.
Also das war früher, als noch nicht alles so auf Strom sparen optimiert war, da hatte
man so Bildschirmschoner.
Seht die at home? Habe ich ja hier in diesem Podcast oder in einem anderen Podcast auch schon mal besprochen.
Die die freie Rechenzeit benutzt haben, also die CPU ausgelastet haben, wenn man nicht
am Rechner war, zum Beispiel weil ein Bildschirmschoner lief oder so.
Und distributed.net war eben auch so ein verteiltes Rechenprogramm, was verschiedene kryptographische
Aufgaben und eben auch diese Suche nach den optimalen Golomb-Linealen über mehrere Rechner
die freiwillig daran teilnehmen und ihre CBU-Zeitspenden verteilt.
Und der Rekord, wo man das optimale Golomb-Lineal erkennt, ist eben 28 Markierungen.
Und sowohl 28, 27, 26, 25, diese vier optimalen Golomb-Lineale wurden alle mit distributed.net-Clients gefunden.
Also, ehrlicherweise muss man sagen, es gab schon vorher Vermutungen dafür, was das optimale Optimum ist,
aber dieses distributed.net hat eben die Enumeration gemacht und sichergestellt,
und sichergestellt, dass es nichts Kürzeres mehr gibt durch Auflisten aller anderen Möglichkeiten.
Und das war erst 2022, als diese 28 Markierungen linear fertig waren.
Und das kürzeste Lineal hat eine Länge von 585 und eben diese 28 Markierungen und eine
Effizienz von über 65 Prozent. Das heißt, 65 Prozent der möglichen Längen erscheinen auch, lassen sich dann auch da
abmessen.
Laut den Statistiken von DistributedNet haben sich über 65.000 verschiedene Rechner aus
über 80 Ländern an dieser Suche beteiligt.
Also ich weiß, dass ich damit auch teilgenommen habe, früher, ganz früher.
Und ich konnte sogar noch mit den Statistiken und Hilfe einer alten E-Mail-Adresse, die
früher mal hatte, rausfinden, dass ich auch an distributed.net teilgenommen habe. Am 16.
Januar 1999 zum ersten Mal. Und ich habe auch an OGR24, also die Suche nach den Länge 24
und Länge 25 Optimal Gulamp Bruders, habe ich auch teilgenommen. Aber dann 27 und 28
irgendwie nicht mehr, dann hatte ich glaube ich nur noch Laptops und wollte Energie sparen.
So, das Ganze kann man jetzt auch noch mathematischer betrachten und mathematisch verallgemeinern.
Wenn ich zum Beispiel so einen Goulomb-Lineal im Computer abspeichern will, was ist eine
Datenstruktur, was ist das mathematische Objekt, mit dem ich das abspeichern würde?
Da würde ich mir vielleicht einfach nur die Längen von links gemessen, wo die Markierungen sind, abspeichern.
Das sind also ganze Zahlen, so wie ich das vorhin in diesem Beispiel des perfekten Lineals
der Länge 6 eingeführt habe.
Da hatte ich ja die Zahlen oder Markierung 0, 1, 4, 6.
Und dann ist das mathematische Problem, diese Goulomb-Eigenschaft, dass keine zwei Differenzen,
also Abstände aus dieser Menge gleich sind. Also wenn ich zwei verschiedene Zahlen daraus
nehme und die Differenz bilde, dann kommt immer eine andere Zahl heraus. Es kommt also
nie vor, dass a-b gleich c-d ist für vier verschiedene Zahlen a, b, c, d in dieser Menge,
wobei aber b gleich c sein darf und so weiter. Aber da ich diese Zahlen a, b, c, d beliebig
wählen kann, kann ich auch auf beiden Seiten der Gleichung plus das rechnen. Also ich habe
a-b gleich c-d kommt nie vor.
Kann ich bei dieser Gleichung auch plus b und plus d rechnen, dann steht da als gleiche
Bedingung a plus d gleich c plus b kommt niemals vor.
Und a, b, c, d waren quasi beliebige Zahlen. Also dass man sich auf die Differenzen konzentriert hat, ist eigentlich völlig egal.
Man kann auch eine Menge von Zahlen suchen, sodass nie zwei Summen gleich sind.
Also eine Menge von Zahlen zu suchen, sodass nie zwei Differenzen gleich sind, ist sehr,
verwandt damit, im Prinzip das gleiche Problem wie eine Summe von Zahlen zu suchen, sodass
die zwei Summen gleich sind?
Der einzige Unterschied ist, dass man jetzt bei den, wenn man nie zwei Summen gleich nimmt,
da darf man auch zweimal die gleiche Zahl nehmen, dann ist es eine perfekte
Übereinstimmung zwischen den beiden Problemen. Und so eine Menge, so dass nie
zwei Summen gleich sind, die nennt man eine Sidonmenge. Und die endlichen Sidonmengen sind also einfach nur die Golomb-Lineale. Also probieren wir es nochmal aus,
bei unserem 0, 1, 4, 6, da sind also auch nie zwei Summen gleich.
Also wenn ich 1 plus 4 rechne, kommt 5 raus und wenn ich 0 plus 4 rechne, kommt
4 raus und wenn ich 0 plus 4 rechne und 1 plus 6 oder 1 plus 1 und 4 plus 0, also es
kommen nie zwei Summen sind gleich. Also die Golomb-Eigenschaft entspricht dieser Sidon-Eigenschaft.
So eine Bemerkung noch, die Kommutativität ist natürlich vorausgesetzt. Also 0 plus
1 ist das gleiche wie 1 plus 0, aber das wusste ich auch schon vorher und das steht jetzt
dieser Definition nicht im Weg. Also ich betrachte nur Summen von Zahlen, die bis
auf Reihenfolge definiert sind, Paare. So und jetzt kann man aber eine interessante
Verallgemeinerung machen, indem man eben unendliche Sidon-Mengen betrachtet. Also
bei dem Lineal ist die Vorstellung jetzt ein bisschen schwierig, aber für die
Mathematik und Kombinatorik ist es interessant, eine unendliche Sidon-Menge
zu betrachten. Und sowas existiert. Das ist also eine Folge von Zahlen, Zahl 1, Zahl 2, Zahl 3, Zahl 4
und so weiter, so dass nie zweimal die gleiche Summe auftritt. Also wenn ich zi
plus zj für zwei Zahlen daraus nehme, dann sind die Summen verschieden für,
jedes Paar ij. Außer dass natürlich z1 plus z2 gleich z2 plus z1 ist dieses
Kommutativitätsproblem wie oben. Also bis auf diese Kommutativität habe ich nie
nie zwei gleiche Summen.
Und das wichtigste Problem über diese Sidon-Mengen ist zu bestimmen, wie dicht sie sein können.
Also erst mal, es existieren unendliche Sidon-Mengen, das ist möglich, aber man fragt sich, wie
viele Zahlen kann man da reinpacken, denn je mehr Zahlen ich da reinpacke, desto mehr,
verschiedene Summen bekomme ich natürlich auch.
Also diese Sidon-Eigenschaft, die man möchte, um erfüllt zu sein, braucht die eben, dass
die Menge dünn ist, wie man das nennt.
Und da gab es kürzlich einen Durchbruch und über den, wo sogar in der Süddeutschen
Zeitung berichtet, das finde ich ganz klasse, das ist so Mathematik-Fachberichterstattung
in der Süddeutschen Zeitung gibt. Also super Sache. Und in dem Artikel wird über einen
Durchbruch berichtet. Bei dem Artikel ist ein etwas lustiges Beispiel drin. Da ist als
Beispiel für so eine Sidonmenge aber 1, 4, 7, 12 drin. Also nochmal 1, 4, 7, 12. Was
nach meiner obigen Diskussion keine Sidonmenge wäre, weil es kein Goulomb-Lineal ist. Von
1 nach 4 ist es 3 und 4 nach 7 ist es 3. Und 1 plus 7 ist das gleiche wie 4 plus 4. Aber
Ich glaube, die haben mit der anderen Definition gearbeitet, dass man nicht eben 4 plus 4 nehmen darf.
Aber lassen wir das mal beiseite.
Also unendliche Siedlermengen existieren und wie die Süddeutsche Zeitung berichtet,
ist jetzt ein Durchbruch gelungen einem 24-jährigen Mathematiker Cedric Pilat,
einem Doktorand in Oxford.
Und dem ist es gelungen, eine Vermutung von Paul Erdös zu beweisen.
Das passiert ja auch nicht jeden Tag.
Es gibt eine Sied und Menge, sodass sich jede hinreichend große Zahl als Summe von drei
Zahlen aus der Menge schreiben lässt.
Okay, was ist das für eine komische Vermutung? Ich habe eben schon darüber gesprochen, dass diese Sidon-Mengen irgendwie dünn sind, denn ich will nie
zwei gleiche Summen haben, also darf ich nicht zu viele Zahlen nehmen.
Und jetzt könnte ich mich aber fragen, kann ich mir so eine perfekte Sidon-Menge
erschaffen? Ich hatte ja mein Goulomb-Lineal, wo jede Differenz vorkommt.
Kann ich es vielleicht schaffen, dass keine Zahl doppelt als Summe vorkommt,
aber jede Zahl als Summe vorkommt? Jede Zahl genau einmal? Und das ist nicht
möglich. Also das kann man sich überlegen. Also nicht möglich, es ist viel zu viel
verlangt. Dann könnte man sich vielleicht das Problem ein bisschen abschwächern.
Kann ich eine Sidonmenge finden, so dass jede hinreichend große Zahl sich schreiben lässt als Summe aus der Sidonmenge? Auch das ist nicht möglich.
Und die Vermutung von Erdös war jetzt, wenn ich drei Zahlen aus der Sidonmenge
nehme, dann reicht's für jede hinreichend große Zahl. Also die Vermutung war, es
Es gibt eine Sidon-Menge, die also dünn ist, nie zweimal die gleiche Summe, so dass sich
jede hinreichend große Zahl als Summe von drei Zahlen aus der Sidon-Menge schreiben.
Und das hat er bewiesen. Und darüber wurde in der Süddeutschen Zeitung berichtet.
Vielleicht weil er 24 Jahre erst ist, der Mathematiker, der das bewiesen hat.
Eine schöne Sache. So, die Zeit ist schon wieder ganz schön fortgeschritten und ihr wisst immer noch nicht,
warum Kostas im Titel vorkommt.
Nun ja, also die Elektroingenieuren, die haben sich nämlich nicht nur für die eindimensionale
Variante dieser Golomb-Lineale interessiert, die sind ja bekannt dafür, sie streben ja
immer nach der höchsten Allgemeinheit und Abstraktion und kamen daher auch auf die Idee,
ein zweidimensionales Problem davon zu betrachten.
Also so ein Golomb-Lineal, das hat eine Dimension, das ist wie so ein Strich, und es gibt keine
identischen Abstände zwischen seinen Markierungen und die zweidimensionale Variante davon ist
sogenanntes Costas Array. Da hat man anstelle von Markierungen auf einer Linie,
hat man Punkte in einem quadratischen Raster. Also wer weiß, was eine Matrix ist,
stellt sich eine Matrix vor, alle anderen stellen sich ein Schachbrett vor und auf
dem Schachbrett werden jetzt bestimmte Positionen markiert, zum Beispiel indem
man eine Figur hinstellt, einen Turm. Und die Punkte werden so ausgewählt, dass in
meinem quadratischen Schachbrett genau ein Punkt in jeder Zeile und ein Punkt
in jeder Spalte ausgewählt wird. Also auf einem 8x8 Schachbrett tue ich 8 Türme, sodass
dass sie sich nicht schlagen können.
Okay, in jeder Zeile und jeder Spalte genau einer. Und das ist noch nicht so schwer, das ist einfach nur eine Permutation, wie die Expertinnen
sofort gemerkt haben.
Und jetzt hat so ein Costas Array, ein zweidimensionales Golomb-Lineal, die Eigenschaft, dass die Differenzvektoren,
wenn ich das jetzt als Koordinaten nehme, also links unten ist 0,0 und rechts oben ist
7,7 oder 1,1 oder 8,8, dass dann die Differenzvektoren alle verschieden sind.
Wenn ich zwei Termine nehme und ihren Differenzvektor nehme, dann ist dieser Differenzvektor einzigartig.
Also so ähnlich wie eine zweidimensionale Variante des Golomb-Lineals.
Und Costas hat das erforscht, weil es da wieder Anwendungen beim Sonar irgendwie gab.
Habe ich auch nicht so genau verstanden, als ich versucht habe, es durchzulesen, aber lassen wir das.
Ist aber faszinierend, weil die Veröffentlichungen dazu zu ungefähr gleichen Teilen in Kombinatorikjournalen und Elektrotechnikjournalen erschienen sind.
Da findet man zum Beispiel Journal of Combinatorial Theory A, also in einem bekannten Kombinatorik-Mathematik-Journal Veröffentlichung von Golomb zu dem Thema und in Proceedings of IEEE, also den Veröffentlichung der amerikanischen Ingenieursvereinigung.
Und Kostas hat auch in IEEE Transactions Information Theory, glaube ich, veröffentlicht.
Also sehr schön. So, also die Mitmachaufgabe heute. Könnt ihr mal wieder was machen. Ihr nehmt euch ein 8x8 Schachbrett
und stellt 8 Türme so hin, dass sie sich nicht schlagen können. In jeder Reihe und jeder Spalte genau einer.
Und dann schaut ihr euch die Abstandsvektoren der Türme an und da darf keiner doppelt vorkommen.
Also wenn ihr zum Beispiel alle Türme so entlang der Diagonalen stellt, also 1, 1, 2, 2, 3, 3, 4, 4, 5, 5,
dann habt ihr verloren. Dann habt ihr zwar die Bedingung erfüllt, dass sie sich nicht schlagen können,
aber von 1,1 zu 2,2 ist es einmal schräg rüber und von 2,2 zu 3,3 ist es auch einmal schräg rüber.
Für ein 4x4 Schachbrett könnt ihr das gleich lösen. Macht da 1,1,2,2 und dann stellt er die
die letzten beiden so einmal gedreht, 90 Grad gedreht hin.
Könnt ihr euch mal für 4x4 überlegen. Und für 8x8 ist es möglich.
Und wenn ich die Tabelle, wenn ich die OEIS richtig lese, dann sollte es 444 Möglichkeiten geben, die ihr habt.
Das sind die guten Nachrichten, also es gibt sehr viele Möglichkeiten,
das zu lösen, das Rätsel. Die schlechte Nachricht ist, dass es acht Fakultät
gleich 40.320 Möglichkeiten gibt, überhaupt nur die Türme hinzustellen.
Also von den 40.320 Möglichkeiten sind die 39.000 und ein paar zerquetschte leider falsch.
Und wenn man sich jetzt mal für die Größe des Quadrats, also ein anderes als 8x8, 9x9, 10x10 und so anschaut,
wie viele von diesen Costus Arrays man kennt, also wie viele Lösungen von diesem Turmproblem,
dann wird das immer mehr und hat bei 16 irgendwie so ein Maximum.
Über 2.500 16x16 Costus Arrays gibt es und interessanterweise geht es danach wieder runter.
Also für 23x23 Kostas Arrays gibt es schon wieder unter 100 und für 32x32 und 33x33 sind meines Wissens nach keine bekannt.
Also es gibt Größen, für die keine Kostas Arrays bekannt sind.
Also da kann man sich noch sehr schön beteiligen und irgendwie scheint das so ein Phänomen zu sein,
was ist nur für kleine Felder oder ganz bestimmte Größen der Felder.
Es gibt dann so Konstruktionen, die unendliche Familien von immer wieder größer werdenden
Kostas-Arrays erzeugen, aber eben nur für ganz bestimmte Größen, sowas wie zwei Potenzen
oder irgendwelche speziellen Zahlen.
Und für 33 ist es eben nicht bekannt, ob es da ein Kostas-Array gibt.
Nicht mal ein einziges.
Im Vergleich zu den 444, die es für 8x8 gibt.
So, dann habt ihr ja eure Hausaufgabe und ich kann hier für heute Schluss machen.
Ich hoffe, es hat euch ein bisschen gefallen. Schickt mir Feedback auf Mastodon und empfehlt uns weiter. Also bis bald. Tschüss!