Pressearchiv

Bilder

Prof. Dr. Jürgen Willms
Prof. Dr. Jürgen Willms (Download )
Auch in der heute selbstverständlichen GPS-Technik im Auto spielen Autokorrelationen eine wichtige Rolle Quelle: FH Südwestfalen, Christian Klett
Auch in der heute selbstverständlichen GPS-Technik im Auto spielen Autokorrelationen eine wichtige Rolle Quelle: FH Südwestfalen, Christian Klett(Download )
02.12.2015

Einfacher Beweis für ein falsch bewiesenes Theorem

Prof. Dr. Jürgen Willms über Autokorrelationen, die Motivation zu forschen, die internationale Forschergemeinschaft und die Erkenntnis, dass eine einfache Darstellung meist die richtige ist

Meschede. Im Jahr 2014 erregte eine Publikation von Prof. Dr. Jürgen Willms in internationalen Fachkreisen große Aufmerksamkeit. Erschienen war seine Veröffentlichung unter dem Titel „Counterexamples to Theorem 1 of Turyn’s and Storer’s Paper On Binary Sequences“ im arXiv, dem Dokumentenserver der Cornell University. Über 50 Jahre lang hatte ein komplizierter Beweis der Autoren Turyn und Storer zum Autokorrelationsverhalten sogenannter „Barker-Folgen“ in der Fachwelt Bestand, bis der Mescheder Informatikprofessor einen Fehler in der Argumentation fand und eine Diskussion über die Richtigkeit des vermeintlich bewiesenen Theorems auslöste. Willms gelang es schließlich, mit eigenen Methoden einen Beweis zu erarbeiten, um kurz darauf durch einen Kollegen aus Magdeburg auf eine noch einfachere Lösung gebracht zu werden.

Wieso haben Sie den Beweis von Turyn und Storer überhaupt in Frage gestellt?

Ehrlich gesagt: aus Frustration. Ich habe mich während eines Forschungssemesters intensiv mit Autokorrelationen beschäftigt. Da ich den Beweis zu meinem Ärgernis nie richtig verstanden hatte, versuchte ich mit von mir entwickelten Methoden einen einfacheren und verständlicheren Beweis zu finden. Ich war sehr erstaunt, als ich dabei herausfand, dass die Beweisführung von Turyn und Storer in Teilen nicht korrekt ist und dass dies anscheinend in den vergangenen 50 Jahren niemandem aufgefallen war.

Wozu braucht man eigentlich Autokorrelationen?

Praktische Beispiele für den Einsatz binärer Folgen mit gutem Autokorrelationsverhalten kennen Sie bestimmt: GPS, Radartechnologie oder WLAN. Stellen Sie sich vor, Sie wollen für eines dieser Einsatzgebiete ein schwaches digitales Signal empfangen. Schwach bedeutet hier, dass Sie neben dem eigentlichen Signal viele andere Störgeräusche empfangen. Das gesuchte Signal ist sozusagen versteckt im Rauschen dieser unerwünschten Störungen. Man kann zeigen, dass sich das gesuchte Signal umso besser aus dem Rauschen herausfiltern lässt, je kleiner die Autokorrelationen des Signals sind.

Aha. Und welche Rolle spielen die „Barker-Folgen“?

Barker-Folgen sind dabei von besonderem Interesse, da sie unter allen binären Folgen das bestmögliche Autokorrelationsverhalten aufweisen. 1961 haben Turyn und Storer in einem viel zitierten Artikel vermeintlich bewiesen, dass es keine Barker-Folge mit der Länge n größer 13 gibt, falls n ungerade ist. Der veröffentliche Beweis, auf den seither in allen Standardpublikationen verwiesen wurde, ist sehr komplex und schwer nachvollziehbar.

Und im Nachhinein betrachtet wohl falsch. Gilt das auch für das aufgestellte Theorem?

Nein, ich konnte mit den von mir entwickelten Methoden einen neuen Beweis für das Barker-Problem ungerader Länge finden. Das Ergebnis habe ich im Herbst 2014 in einem weiteren Artikel veröffentlicht. Insgesamt war ich allerdings damit nicht ganz zufrieden. Der Beweis war nun korrekt und viele der zugrunde liegenden Ideen neu, aber das Ziel, einen einfachen und kurzen Beweis zu finden, hatte ich nicht ganz erreicht.

Aber das ist Ihnen im Anschluss noch gelungen?

Ja. Allerdings nicht alleine, sondern mit Hilfe von Prof. Dr. Kai-Uwe Schmidt. Er kannte meine erste Veröffentlichung und hatte mich im Sommer 2014 eingeladen, im Institut für Algebra und Geometrie der Universität Magdeburg einen Vortrag über meine Forschungsaktivitäten zu halten. Im Januar 2015 kontaktierte er mich wieder. Er hatte meinen zweiten Artikel gelesen und herausgefunden, dass meine Ideen auch ohne die von mir entwickelten Methoden angewandt werden können und zu einem sehr einfachen und kurzen Beweis führen. Das haben wir schließlich im gemeinsamen Artikel „Barker Sequences of odd length“ veröffentlicht. Geblieben ist meine grundlegende Idee und das Gefühl: Eine gute und verständliche Darstellung zeichnet sich oft durch Einfachheit aus.