Carmichaels Totientenfunktions-Vermutung

mathematische Vermutung

In der Mathematik ist die Eulersche Phi-Funktion (auch Totient von genannt) eine zahlentheoretische Funktion, die für jede positive natürliche Zahl angibt, wie viele zu teilerfremde natürliche Zahlen es gibt, die nicht größer als sind. Diese Totienten sind oft gleich, so ist zum Beispiel , weil zu den vier Zahlen 1, 2, 3 und 4 teilerfremd und zu den vier Zahlen 1, 3, 7 und 9 teilerfremd ist.

Der US-amerikanische Mathematiker Robert Carmichael stellte die folgende Behauptung im Jahr 1907 als Übungsaufgabe auf:[1]

Für jedes gibt es mindestens eine positive ganze Zahl , sodass gilt:

Carmichael war der Meinung, er hätte diese Behauptung bewiesen, und hat diese Behauptung 1907 als einen mathematischen Satz formuliert und sogar 1914 als Übungsaufgabe in sein Lehrbuch Theory of numbers (Kapitel 2) aufgenommen. Allerdings war sein Beweis fehlerhaft. Er zog im Jahr 1922 seine Behauptung zurück, nachdem mehrere Personen ihn auf eine Lücke im Beweis hingewiesen hatten, und erklärte die Vermutung als offenes Problem, die man nun Carmichaels Totientenfunktions-Vermutung oder kurz Carmichaels Vermutung bzw. Carmichaelsche Vermutung nennt (englisch Carmichael’s totient function conjecture).[2][3]

Man kann die Carmichaelsche Vermutung auch anders formulieren:

Es gibt keine Zahl , die von der Eulerschen Phi-Funktion genau einmal angenommen wird.

Oder als Frage formuliert:

Gibt es eine Zahl , die von der Eulerschen Phi-Funktion genau einmal angenommen wird?

Wenn die Carmichaelsche Vermutung stimmt, müsste man diese Frage mit „Nein!“ beantworten.

Beispiele

Bearbeiten
  • Sei  . Dann gibt es zu dieser Zahl nur die beiden Zahlen   und  , die zu   teilerfremd sind. Somit ist  . Es gibt aber auch zu   nur zwei teilerfremde Zahlen, nämlich   und  . Somit ist auch   und man hat eine zweite Zahl   gefunden, deren Totient gleich dem Totienten von   ist und es ist  . Auch   (weil 3 zu 1 und 2 teilerfremd ist). Es gibt somit sogar drei Zahlen, deren Totient gleich 2 ist.
  • Die folgende Tabelle gibt an, welche Zahlen   welchen Totienten   haben und welche anderen Zahlen   den gleichen Totienten besitzen. Man kann ihr entnehmen, dass die Carmichaelsche Vermutung zumindest bis   gilt. Man erkennt auch, dass   für   stets eine gerade Zahl   ist (siehe Eigenschaften der Eulerschen Phi-Funktion). Würde die Carmichaelsche Vermutung nicht stimmen, müsste irgendwann in der dritten Spalte eine 1 auftauchen.

  Zahlen  , sodass   ist (Folge A032447 in OEIS) Anzahl   dieser  
(Folge A014197 in OEIS)
1 1, 2 2
2 3, 4, 6 3
4 5, 8, 10, 12 4
6 7, 9, 14, 18 4
8 15, 16, 20, 24, 30 5
10 11, 22 2
12 13, 21, 26, 28, 36, 42 6
16 17, 32, 34, 40, 48, 60 6
18 19, 27, 38, 54 4
20 25, 33, 44, 50, 66 5
22 23, 46 2
24 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 10
28 29, 58 2
30 31, 62 2
32 51, 64, 68, 80, 96, 102, 120 7
36 37, 57, 63, 74, 76, 108, 114, 126 8
40 41, 55, 75, 82, 88, 100, 110, 132, 150 9
42 43, 49, 86, 98 4
44 69, 92, 138 3
46 47, 94 2
48 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 11
52 53, 106 2
54 81, 162 2
56 87, 116, 174 3
58 59, 118 2
60 61, 77, 93, 99, 122, 124, 154, 186, 198 9
64 85, 128, 136, 160, 170, 192, 204, 240 8
66 67, 134 2
70 71, 142 2
72 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 17

Untere Grenzen

Bearbeiten

Es gibt sehr hohe untere Grenzen für  , die die Carmichaelsche Vermutung widerlegen könnten. Carmichael selbst hat im Jahr 1922 bewiesen, dass jedes Gegenbeispiel zu seiner Vermutung (also ein Wert  , bei dem sich   von den Totienten aller anderen Zahlen unterscheidet) mindestens   sein muss.[2] Der US-amerikanische Mathematiker Victor Klee erweiterte im Jahr 1947 dieses Ergebnis auf  .[4] Masai und Vallette konnten im Jahr 1982 die untere Grenze für ein Gegenbeispiel auf   erhöhen.[5] Die beiden Mathematiker Schlafly und Wagon erhöhten die untere Grenze im Jahr 1994 auf  [6] und letztendlich zeigte der US-amerikanische Mathematiker Kevin Ford im Jahr 1998,[7] dass   eine untere Grenze sein muss.[8][9]

Schlafly und Wagon schrieben 1994:[6][10]

“We do not know of another unsolved problem in mathematics for which a lower bound on a counterexample is so high. (…) There can be little doubt that Carmichael’s conjecture is true.”

„Wir kennen kein anderes ungelöstes Problem in der Mathematik, bei dem die untere Schranke für ein Gegenbeispiel so hoch ist. (…) Es kann wenig Zweifel geben, dass Carmichaels Vermutung wahr ist.“

Aaron Schlafly, Stan Wagon

Eigenschaften, die ein Gegenbeispiel haben muss

Bearbeiten

Sei   ein Gegenbeispiel von Carmichaels Totientenfunktions-Vermutung mit   (es muss also für alle   gelten:  ). Dann muss gelten:

  •   ist eine gerade Zahl.[2]
Beweis:
Wäre   ungerade, so würde   gelten (siehe Eigenschaften der Eulerschen Phi-Funktion) und man hätte erst recht zwei Zahlen mit gleichem Totienten. Somit muss   eine gerade Zahl sein.  
  •   ist ein Vielfaches von 4.[2]
Beweis:
Wäre   kein Vielfaches von 4, so muss   wegen obiger Aussage eine gerade Zahl sein. Somit ist   und man hätte erst recht zwei Zahlen mit gleichem Totienten. Somit muss   ein Vielfaches von 4 sein.  
  • Sei   und   teilbar durch eine Primzahl der Form  . Dann gilt:[2]
  ist teilbar durch das Quadrat dieser Primzahl (also durch  ).
  •   muss durch die Quadrate der Primteiler von   teilbar sein.[4]
  •   darf nicht durch   teilbar sein.[4]
  •   darf nicht durch Fermat-Primzahlen   (also Primzahlen der Form   mit  ) teilbar sein (es sind, abgesehen von  , nur  ,  ,   und   bekannt).[4]
Beispiel:
Will man kontrollieren, ob   ein Gegenbeispiel von Carmichaels Totientenfunktions-Vermutung ist, so muss man die Primfaktorzerlegung von   betrachten. Die Quadrate der Primteiler von   sind   und  , und   muss durch   und   teilbar sein. Leider ist aber   nicht durch   teilbar, somit kommt   nicht als Gegenbeispiel in Frage. Wäre   auch durch   teilbar, wäre sie ein Kandidat für ein Gegenbeispiel, weil sie weder durch  ,  ,  ,   oder   teilbar ist. Aber selbst dann wäre es sehr unwahrscheinlich, dass   tatsächlich ein Gegenbeispiel ist.   ist eben nur ein Kandidat für ein Gegenbeispiel.
  • Sei   eine Primzahl, sodass   ein Teiler von   ist. Dann gilt:[11]
  teilt  .
Pomerance zeigte im Jahr 1974, dass die Existenz einer solchen ganzen Zahl höchst unwahrscheinlich ist. Wenn eine solche Zahl existiert, dann gibt es allerdings unendlich viele Gegenbeispiele zu Carmichaels Totientenfunktions-Vermutung. Wenn es keine solchen Zahlen gibt, bedeutet es aber noch immer nicht, dass Carmichaels Vermutung stimmt (  könnte ganz andere Teiler haben).

Aus den angeführten Sätzen wird klar, dass ein Gegenbeispiel zur Vermutung sehr viele Primteiler haben muss. Eine Strategie zum Beweis der Vermutung besteht darin, zu zeigen, dass das Gegenbeispiel unendlich viele Primteiler haben muss. Sei   die Menge dieser Primteiler eines Gegenbeispiels. Ford zeigte 2014,[12] dass die Menge   sehr „dünn“ ist: Sei   die Anzahl der Elemente aus  , die kleiner gleich   sind, dann ist nach Ford   für eine Konstante   mit dem Landau-Symbol  . Das macht einen Beweis über diese Strategie sehr schwierig.

Weitere Ergebnisse

Bearbeiten

Sei   die Anzahl der verschiedenen  , für die   gilt (wie in der dritten Spalte der obigen Tabelle). Dann gelten folgende Sätze:[10]

  • Sei   für eine ganze Zahl  . Dann existieren unendlich viele solche  .[13]
Beispiel:
Dieser von Paul Erdős im Jahr 1958 bewiesene Satz besagt, dass, wenn es ein   gibt mit  , es unendlich viele solche   gibt. Sei zum Beispiel  . Dann kann man obiger Tabelle entnehmen, dass für   jeweils exakt 3 verschiedene   existieren, für die jeweils   gilt. Somit gibt es unendlich viele   mit  . Das gilt auch für den Fall  , also den Fall eines Gegenbeispiels zu Carmichaels Vermutung. Gibt es also ein Gegenbeispiel zur Vermutung, so gibt es unendlich viele weitere Gegenbeispiele.
  • Für jede ganze Zahl   gibt es eine ganze Zahl  , sodass   ist.[8]
Beispiel:
Dieser Satz wurde von Wacław Sierpiński in den 1950er-Jahren vermutet und von Kevin Ford im Jahr 1999 bewiesen. Sei  . Dann gibt es laut diesem Satz ein  , sodass   ist. Tatsächlich kann man der obigen Tabelle entnehmen, dass in diesem Fall   ist, weil   ist. Es kann auch andere   geben, die diese Eigenschaft haben (zum Beispiel  ).

Auch diese beiden Sätze machen die Existenz eines Gegenbeispiels zu Carmichaels Vermutung sehr unwahrscheinlich.

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Robert Daniel Carmichael: On Euler’s  -function. Bulletin of the American Mathematical Society 13 (5), 1907, S. 241–243, abgerufen am 17. April 2022.
  2. a b c d e Robert Daniel Carmichael: Note on Euler’s  -function. Bulletin of the American Mathematical Society 28 (3), 1922, S. 109–110, abgerufen am 17. April 2022.
  3. Carmichaelsche Vermutung. Spektrum.de, abgerufen am 16. April 2022.
  4. a b c d Victor LaRue Klee: On a conjecture of Carmichael. Bulletin of the American Mathematical Society 53 (12), 1947, S. 1183–1186, abgerufen am 23. April 2022.
  5. Pierre Masai, Alain Valette: A lower bound for a counterexample to Carmichael’s conjecture. Boll. Un. Mat. Ital. 1 (6), 1982, S. 313–316, abgerufen am 23. April 2022.
  6. a b Aaron Schlafly, Stan Wagon: Carmichael’s conjecture on the Euler function is valid below 1010,000,000. Mathematics of Computation 63 (207), 1994, S. 415–419, abgerufen am 17. April 2022.
  7. Kevin Ford: The distribution of totients. Ramanujan Journal, Nr. 1–2, 1998, S. 67–151.
  8. a b Kevin Ford: The number of solutions of  . Annals of Mathematics 150 (1), 1999, S. 283–311, abgerufen am 17. April 2022.
  9. Jozsef Sándor, Borislav Crstici: Handbook of number theory II. Kluwer Academic Publishers, 2004, S. 228–229, abgerufen am 17. April 2022.
  10. a b Brian D. Beasley: The Resolved and Unresolved Conjectures of R. D. Carmichael. ACMS 21st Biennial Conference Proceedings, Charleston Southern University, S. 2–3, abgerufen am 23. April 2022.
  11. Carl Pomerance: On Carmichael’s conjecture. Proceedings of the American Mathematical Society 43 (2), 1974, S. 297–298, abgerufen am 23. April 2022.
  12. Kevin Ford: Sieving very thin sets of primes, and Pratt trees with missing primes. Int. Math. Res. Not. IMRN, Nr. 11, 2014, S. 2955–2971.
  13. Paul Erdős: Some remarks on Euler’s  -function. Acta Arithmetica 4, 1958, S. 10–19, abgerufen am 23. April 2022.