Εικασία του Καρμάικλ

Από testwiki
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση

Στα μαθηματικά, η εικασία του Καρμάικλ[1][2] αφορά την πολλαπλότητα των τιμών της συνάρτησης του Όιλερ φ(n)[3], η οποία μετρά τον αριθμό των ακεραίων αριθμών που είναι μικρότεροι και και μεταξύ τους πρώτοι του n. Δηλώνει ότι για κάθε n υπάρχει τουλάχιστον ένας άλλος ακέραιος m ≠ n τέτοιος ώστεφ(m) = φ(n). Ο Ρόμπερτ Καρμάικλ διατύπωσε για πρώτη φορά αυτή την εικασία το 1907, αλλά ως θεώρημα και όχι ως εικασία. Ωστόσο, η απόδειξή του ήταν ελαττωματική και το 1922 ανακάλεσε τον ισχυρισμό του και δήλωσε την εικασία ως ανοιχτό πρόβλημα.

Παραδείγματα

Η συνάρτηση φ(n)[3] είναι ίση με 2 όταν το n είναι μία από τις τρεις τιμές 3, 4 και 6. Έτσι, αν πάρουμε οποιαδήποτε από αυτές τις τρεις τιμές ως n, τότε οποιαδήποτε από τις άλλες δύο τιμές μπορεί να χρησιμοποιηθεί ως m για την οποία φ(m) = φ(n).

Αντίστοιχα, το ολικό πηλίκο είναι ίσο με 4 όταν το n είναι μία από τις τέσσερις τιμές 5, 8, 10 και 12, και είναι ίσο με 6 όταν το n είναι μία από τις τέσσερις τιμές 7, 9, 14 και 18. Σε κάθε περίπτωση, υπάρχουν περισσότερες από μία τιμές του n που έχουν την ίδια τιμή του φ(n).

Η εικασία δηλώνει ότι αυτό το φαινόμενο των επαναλαμβανόμενων τιμών ισχύει για κάθε n.

k αριθμοί n τέτοιοι ώστε φ(n) = k Πρότυπο:OEIS αριθμός τέτοιων n Πρότυπο: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

Κατώτερα όρια

Υπάρχουν πολύ υψηλά κατώτερα όρια για την εικασία του Καρμάικλ που είναι σχετικά εύκολο να προσδιοριστούν. Ο ίδιος ο Καρμάικλ απέδειξε ότι οποιοδήποτε αντιπαράδειγμα στην εικασία του (δηλαδή μια τιμή n τέτοια ώστε η φ(n) να είναι διαφορετική από τις πηλίκα όλων των άλλων αριθμών) πρέπει να είναι τουλάχιστον 1037 και ο Βίκτορ Κλι επέκτεινε αυτό το αποτέλεσμα σε 10400. Ένα κατώτερο όριο 10107 δόθηκε από τους Σλάφλι και Γουάγκον, και ένα κατώτερο όριο 101010 προσδιορίστηκε από τον Κέβιν Φορντ το 1998.[4]

Η υπολογιστική τεχνική που διέπει αυτά τα κατώτερα όρια εξαρτάται από ορισμένα βασικά αποτελέσματα του Κλι, τα οποία καθιστούν δυνατή την απόδειξη ότι το μικρότερο αντιπαράδειγμα πρέπει να διαιρείται με τα τετράγωνα των πρώτων αριθμών που διαιρούν την ολική τιμή του. Τα αποτελέσματα του Κλι συνεπάγονται ότι το 8 και οι πρώτοι αριθμοί Φερμά (πρώτοι αριθμοί της μορφής 2k + 1) εξαιρουμένου του 3 δεν διαιρούν το μικρότερο αντιπαράδειγμα. Κατά συνέπεια, η απόδειξη της εικασίας είναι ισοδύναμη με την απόδειξη ότι η εικασία ισχύει για όλους τους ακέραιους που συμπίπτουν με το 4 (mod 8).

Άλλα αποτελέσματα

Ο Φορντ απέδειξε επίσης ότι αν υπάρχει ένα αντιπαράδειγμα στην εικασία, τότε ένα θετικό ποσοστό (με την έννοια της ασυμπτωτικής πυκνότητας) των ακεραίων αριθμών είναι επίσης αντιπαράδειγμα.[4]

Αν και η εικασία είναι ευρέως αποδεκτή, ο Καρλ Πόμερανς έδωσε μια επαρκή συνθήκη για έναν ακέραιο n που αποτελεί αντιπαράδειγμα στην εικασία (Πρότυπο:Harv). Σύμφωνα με αυτή τη συνθήκη, ο n είναι αντιπαράδειγμα αν για κάθε πρώτο αριθμό p τέτοιο ώστε ο p − 1 να διαιρεί τοφ(n), ο p2 διαιρεί τον  n. Ωστόσο, ο Πόμερανς έδειξε ότι η ύπαρξη ενός τέτοιου ακέραιου αριθμού είναι εξαιρετικά απίθανη. Ουσιαστικά, μπορεί κανείς να δείξει ότι αν οι πρώτοι k πρώτοι p που είναι σύμφωνοι με το 1 (mod q) (όπου q είναι πρώτος αριθμός) είναι όλοι μικρότεροι από qk+1 τότε ένας τέτοιος ακέραιος θα διαιρείται με κάθε πρώτο αριθμό και επομένως δεν μπορεί να υπάρξει. Σε κάθε περίπτωση, η απόδειξη ότι το αντιπαράδειγμα του Πόμερανς δεν υπάρχει απέχει πολύ από την απόδειξη της εικασίας του Καρμάικλ. Ωστόσο, αν υπάρχει, τότε υπάρχουν άπειρα πολλά αντιπαραδείγματα, όπως ισχυρίζεται ο Φορντ.

Ένας άλλος τρόπος για να διατυπώσουμε την εικασία του Καρμάικλ είναι ότι, αν το A(f) δηλώνει τον αριθμό των θετικών ακεραίων n για τους οποίους φ(n) = f, τότε το A(f) δεν μπορεί ποτέ να είναι ίσο με 1. Σχετικά, ο Βάτσλαβ Σιερπίνσκι υπέθεσε ότι κάθε θετικός ακέραιος εκτός του 1 εμφανίζεται ως τιμή του A(f), μια εικασία που αποδείχθηκε το 1999 από τον Κέβιν Φορντ.[5]

Εξωτερικοί σύνδεσμοι

Δείτε επίσης

Βιβλιογραφία

Παραπομπές

Πρότυπο:Reflist

Πηγές

Πρότυπο:Portal bar Πρότυπο:Authority control

  1. ↑ Πρότυπο:Cite web
  2. ↑ Πρότυπο:Cite web
  3. ↑ 3,0 3,1 Πρότυπο:Cite web
  4. ↑ 4,0 4,1 Sándor & Crstici (2004) p. 228
  5. ↑ Sándor & Crstici (2004) p. 229
Ανακτήθηκε από «https://el.wiki.beta.math.wmflabs.org/w/index.php?title=Εικασία_του_Καρμάικλ&oldid=3082»