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

Στα μαθηματικά, η εικασία του Καρμάικλ^[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 (ακολουθία A032447 στην OEIS)	αριθμός τέτοιων n (ακολουθία A014197 στην 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) να είναι διαφορετική από τις πηλίκα όλων των άλλων αριθμών) πρέπει να είναι τουλάχιστον 10³⁷ και ο Βίκτορ Κλι επέκτεινε αυτό το αποτέλεσμα σε 10⁴⁰⁰. Ένα κατώτερο όριο $10^{10^{7}}$ δόθηκε από τους Σλάφλι και Γουάγκον, και ένα κατώτερο όριο $10^{10^{10}}$ προσδιορίστηκε από τον Κέβιν Φορντ το 1998.^[4]

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

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

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

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

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

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

Δείτε επίσης

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

Weisstein, Eric W. (12 Δεκεμβρίου 2002). CRC Concise Encyclopedia of Mathematics. CRC Press. ISBN 978-1-4200-3522-3.
Karpenko, A. S. (2006). Lukasiewicz's Logics and Prime Numbers. Luniver Press. ISBN 978-0-9551170-3-9.
Agarwal, Ravi P. (2024). Mathematics Before and After Pythagoras: Exploring the Foundations and Evolution of Mathematical Thought. Springer Nature. ISBN 978-3-031-74224-8.
Farlow, Stanley J. (2 Οκτωβρίου 2019). Advanced Mathematics: A Transitional Reference. John Wiley & Sons. ISBN 978-1-119-56353-2.
Hutz, Benjamin (17 Απριλίου 2018). An Experimental Introduction to Number Theory. American Mathematical Soc. ISBN 978-1-4704-3097-9.
Broughan, Kevin (2 Νοεμβρίου 2017). Equivalents of the Riemann Hypothesis. Cambridge University Press. ISBN 978-1-107-19704-6.
Trif, Nick (13 Σεπτεμβρίου 2020). From Riemann Hypothesis to CPS Geometry and. Nick Trif. ISBN 979-8-6850-6529-2.
Deza, Elena (10 Φεβρουαρίου 2023). Perfect And Amicable Numbers. World Scientific. ISBN 978-981-12-5964-7.
Broughan, Kevin (2 Νοεμβρίου 2017). Equivalents of the Riemann Hypothesis: Volume 1, Arithmetic Equivalents. Cambridge University Press. ISBN 978-1-108-18700-8.
Lignon, Daniel (5 Νοεμβρίου 2024). Dictionnaire de (presque) tous les nombres entiers. Editions Ellipses. ISBN 978-2-340-10019-0.
Barot, Michael· González, Jesús Arturo Jiménez (28 Ιανουαρίου 2019). Quadratic Forms: Combinatorics and Numerical Results. Springer. ISBN 978-3-030-05627-8.

Παραπομπές

↑ Carr, Avery. «Carmichael's Totient Conjecture» (στα Αγγλικά). Ανακτήθηκε στις 22 Ιανουαρίου 2025.
↑ «Carmichael's Totient Function Conjecture». archive.lib.msu.edu. Ανακτήθηκε στις 22 Ιανουαρίου 2025.
↑ ^3,0 ^3,1 «Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου- σελίδα 355 Totient - Τοσοστική συνάρτηση, συνάρτηση φ του Euler» (PDF).
↑ ^4,0 ^4,1 Sándor & Crstici (2004) p. 228
↑ Sándor & Crstici (2004) p. 229

Carmichael, R. D. (1907), «On Euler's φ-function», Bulletin of the American Mathematical Society 13 (5): 241–243, doi:10.1090/S0002-9904-1907-01453-2
Carmichael, R. D. (1922), «Note on Euler's φ-function», Bulletin of the American Mathematical Society 28 (3): 109–110, doi:10.1090/S0002-9904-1922-03504-5
Ford, K. (1999), «The number of solutions of φ(x) = m», Annals of Mathematics 150 (1): 283–311, doi:10.2307/121103,
Zbl 0978.11053
Guy, Richard K. (2004), Unsolved problems in number theory (3rd έκδοση), Springer-Verlag, B39, ISBN 978-0-387-20860-2,
Zbl 1058.11001
Klee, V. L. Jr. (1947), «On a conjecture of Carmichael», Bulletin of the American Mathematical Society 53 (12): 1183–1186, doi:10.1090/S0002-9904-1947-08940-0,
Zbl 0035.02601
Pomerance, Carl (1974), «On Carmichael's conjecture», Proceedings of the American Mathematical Society 43 (2): 297–298, doi:10.2307/2038881,
Zbl 0254.10009
, http://www.math.dartmouth.edu/~carlp/PDF/carmichaelconjecture.pdf
Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, σελ. 228–229, ISBN 978-1-4020-2546-4,
Zbl 1079.11001
Schlafly, A.; Wagon, S. (1994), «Carmichael's conjecture on the Euler function is valid below 10^10,000,000», Mathematics of Computation 63 (207): 415–419, doi:10.2307/2153585,
Zbl 0801.11001
Danilov, L.V., "The Diophantine equation 'x³ - y²' ' = k ' and Hall's conjecture", 'Math. Notes Acad. Sci. USSR' 32(1982), 617-618.
Gebel, J., Pethö, A., and Zimmer, H.G.: "On Mordell's equation", 'Compositio Math.' 110(1998), 335-367.
I. Jiménez Calvo, J. Herranz and G. Sáez Moreno, "A new algorithm to search for small nonzero |'x3 - y2'| values", 'Math. Comp.' 78 (2009), pp. 2435-2444.
S. Aanderaa, L. Kristiansen and H. K. Ruud, "Search for good examples of Hall's conjecture", 'Math. Comp.' 87 (2018), 2903-2914.

Πηγές

Apostol, Thomas M. (1976), Introduction to Analytic Number Theory, New York: Springer, ISBN 0-387-90163-9, https://archive.org/details/introductiontoan00apos_0
Conway, John Horton; Guy, Richard K. (1996), The Book of Numbers, New York: Copernicus, ISBN 978-0-387-97993-9
Crandall, Richard; Pomerance, Carl (2005), Prime Numbers: A Computational Perspective (2nd έκδοση), Berlin, New York: Springer-Verlag, ISBN 978-0-387-25282-7
Singer, I. M.· Thorpe, J. A. (28 Μαΐου 2015). Lecture Notes on Elementary Topology and Geometry. Springer. ISBN 978-1-4615-7347-0.
Apostol, Tom M. (29 Ιουνίου 2013). Introduction to Analytic Number Theory. Springer Science & Business Media. ISBN 978-1-4757-5579-4.
Miller, P. D. (2006), Applied Asymptotic Analysis, American Mathematical Society, ISBN 9780821840788, https://books.google.com/books?id=KQvqBwAAQBAJ
Apostol, Thomas M. (1976), Introduction to Analytic Number Theory, New York: Springer, ISBN 0-387-90163-9, https://archive.org/details/introductiontoan00apos_0

[1] Carr, Avery. «Carmichael's Totient Conjecture» (στα Αγγλικά). Ανακτήθηκε στις 22 Ιανουαρίου 2025.

[2] «Carmichael's Totient Function Conjecture». archive.lib.msu.edu. Ανακτήθηκε στις 22 Ιανουαρίου 2025.

[:0-3] 3,0 ^3,1 «Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου- σελίδα 355 Totient - Τοσοστική συνάρτηση, συνάρτηση φ του Euler» (PDF).

[HBII228-4] 4,0 ^4,1 Sándor & Crstici (2004) p. 228

[HBII229-5] Sándor & Crstici (2004) p. 229

[1]

[2]

[3]

[4]

[5]