Εικασία του Σινγκμάστερ

Η εικασία του Σινγκμάστερ είναι μια εικασία στη συνδυαστική θεωρία αριθμών, που πήρε το όνομά της από τον Βρετανό μαθηματικό Ντέιβιντ Σινγκμάστερ, ο οποίος την πρότεινε το 1971. Δηλώνει ότι υπάρχει ένα πεπερασμένο άνω όριο για τις πολλαπλότητες των καταχωρήσεων στο τρίγωνο του Πασκάλ (εκτός από τον αριθμό 1, ο οποίος εμφανίζεται άπειρες φορές). Είναι σαφές ότι ο μόνος αριθμός που εμφανίζεται άπειρες φορές στο τρίγωνο του Πασκάλ είναι το 1, επειδή οποιοσδήποτε άλλος αριθμός x μπορεί να εμφανιστεί μόνο μέσα στις πρώτες x + 1 σειρές του τριγώνου.

Δήλωση

Έστω N(a) ο αριθμός των φορών που εμφανίζεται ο αριθμός a > 1 στο τρίγωνο του Πασκάλ. Σε συμβολισμό Μεγάλο Ο (big O), η εικασία είναι:

$N(a)=O(1).$

Γνωστό όριο

Ο Σιγκμάστερ (1971) έδειξε ότι

$N(a)=O(\log a).$

Οι Άμποτ, Έρντος και Χάνσον (1974) (βλ. Βιβλιογραφικές αναφορές) βελτίωσαν την εκτίμηση σε:

$N(a)=O\left({\frac {\log a}{\log \log a}}\right).$

Το καλύτερο γνωστό προς το παρόν (άνευ όρων) όριο είναι

$N(a)=O\left({\frac {(\log a)(\log \log \log a)}{(\log \log a)^{3}}}\right),$

και οφείλεται στον Κέιν (2007). Οι Άμποτ, Έρντος και Χάνσον σημειώνουν ότι, υπό την προϋπόθεση της εικασίας του Κράμερ για τα κενά μεταξύ διαδοχικών πρώτων αριθμών,

$N(a)=O\left((\log a)^{2/3+\varepsilon }\right)$

ισχύει για κάθε $\varepsilon >0$.

Ο Σινγκμάστερ (1975) έδειξε ότι η Διοφαντική εξίσωση

${n+1 \choose k+1}={n \choose k+2}$

έχει απείρως πολλές λύσεις για τις δύο μεταβλητές n, k. Προκύπτει ότι υπάρχουν άπειρες καταχωρήσεις τριγώνου πολλαπλότητας τουλάχιστον 6: Για κάθε μη αρνητικό i, ένας αριθμός a με έξι εμφανίσεις στο τρίγωνο του Πασκάλ δίνεται από μία από τις δύο παραπάνω εκφράσεις με

$n=F_{2i+2}F_{2i+3}-1,$

$k=F_{2i}F_{2i+3}-1,$

όπου F_j είναι ο jth αριθμός Φιμπονάτσι (δεικτοδοτημένος σύμφωνα με τη σύμβαση ότι F₀ = 0 και F₁ = 1). Οι δύο παραπάνω εκφράσεις εντοπίζουν δύο από τις εμφανίσεις- δύο άλλες εμφανίζονται συμμετρικά στο τρίγωνο σε σχέση με αυτές τις δύο- και οι άλλες δύο εμφανίσεις είναι στο ${a \choose 1}$ και ${a \choose a-1}.$

Στοιχειώδη παραδείγματα

• Το 2 εμφανίζεται μόνο μία φορά- όλοι οι μεγαλύτεροι θετικοί ακέραιοι εμφανίζονται περισσότερες από μία φορές,
• 3, 4, 5 ο καθένας εμφανίζεται δύο φορές- άπειροι αριθμοί εμφανίζονται ακριβώς δύο φορές,
• όλοι οι περιττοί πρώτοι αριθμοί εμφανίζονται δύο φορές,
• Το 6 εμφανίζεται τρεις φορές, όπως και όλοι οι κεντρικοί διωνυμικοί συντελεστές εκτός από το 1 και το 2,

(δεν αποκλείεται κατ' αρχήν ένας τέτοιος συντελεστής να εμφανιστεί πέντε, επτά ή περισσότερες φορές, αλλά δεν είναι γνωστό τέτοιο παράδειγμα)

• όλοι οι αριθμοί της μορφής ${p \choose 2}$ για τον πρώτο αριθμό $p>3$ εμφανίζονται τέσσερις φορές,
• Άπειροι πολλοί εμφανίζονται ακριβώς έξι φορές, συμπεριλαμβανομένου καθενός από τους ακόλουθους:

$120={120 \choose 1}={120 \choose 119}={16 \choose 2}={16 \choose 14}={10 \choose 3}={10 \choose 7}$

$210={210 \choose 1}={210 \choose 209}={21 \choose 2}={21 \choose 19}={10 \choose 4}={10 \choose 6}$

$1540={1540 \choose 1}={1540 \choose 1539}={56 \choose 2}={56 \choose 54}={22 \choose 3}={22 \choose 19}$

$7140={7140 \choose 1}={7140 \choose 7139}={120 \choose 2}={120 \choose 118}={36 \choose 3}={36 \choose 33}$

$11628={11628 \choose 1}={11628 \choose 11627}={153 \choose 2}={153 \choose 151}={19 \choose 5}={19 \choose 14}$

$24310={24310 \choose 1}={24310 \choose 24309}={221 \choose 2}={221 \choose 219}={17 \choose 8}={17 \choose 9}$

Ο επόμενος αριθμός στην άπειρη οικογένεια του Σινγκμάστερ (που δίνεται με βάση τους αριθμούς Φιμπονάτσι), και ο επόμενος μικρότερος αριθμός που εμφανίζεται έξι ή περισσότερες φορές, είναι $a=61218182743304701891431482520$:

$a={a \choose 1}={a \choose a-1}={104 \choose 39}={104 \choose 65}={103 \choose 40}={103 \choose 63}$

• Ο μικρότερος αριθμός που εμφανίζεται οκτώ φορές - και μάλιστα ο μόνος γνωστός αριθμός που εμφανίζεται οκτώ φορές - είναι ο 3003, ο οποίος είναι επίσης μέλος της άπειρης οικογένειας αριθμών του Singmaster με πολλαπλότητα τουλάχιστον 6:

$3003={3003 \choose 1}={78 \choose 2}={15 \choose 5}={14 \choose 6}={14 \choose 8}={15 \choose 10}={78 \choose 76}={3003 \choose 3002}$

Δεν είναι γνωστό αν άπειροι αριθμοί εμφανίζονται οκτώ φορές, ούτε καν αν οποιοσδήποτε άλλος αριθμός εκτός από τον 3003 εμφανίζεται οκτώ φορές.

Ο αριθμός των φορών που εμφανίζεται το n στο τρίγωνο του Πασκάλ είναι

∞, 1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, 2, 2, 2, 2, 3, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 4, 2, 2, ... (ακολουθία A003016 στην OEIS)

Σύμφωνα με τους Άμποτ, Έρντος και Χάνσον (1974), ο αριθμός των ακεραίων αριθμών όχι μεγαλύτερων από το x που εμφανίζονται πάνω από δύο φορές στο τρίγωνο του Πασκάλ είναι $O(x^{\frac {1}{2}})$.

Ο μικρότερος φυσικός αριθμός μεγαλύτερος από το 1 που εμφανίζεται (τουλάχιστον) n φορές στο τρίγωνο του Πασκάλ είναι

2, 3, 6, 10, 120, 120, 3003, 3003, ... (ακολουθία A062527 στην OEIS)

Οι αριθμοί που εμφανίζονται τουλάχιστον πέντε φορές στο τρίγωνο του Πασκάλ είναι οι εξής

1, 120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520, ... (ακολουθία A003015 στην OEIS)

Από αυτά, εκείνα που ανήκουν στην άπειρη οικογένεια του Σινγκμάστερ είναι τα εξής

1, 3003, 61218182743304701891431482520, ... (ακολουθία A090162 στην OEIS)

Ανοικτά ερωτήματα

Δεν είναι γνωστό αν κάποιος αριθμός εμφανίζεται περισσότερες από οκτώ φορές, ούτε αν κάποιος άλλος αριθμός εκτός από το 3003 εμφανίζεται τόσες φορές. Το εικαζόμενο πεπερασμένο άνω όριο θα μπορούσε να είναι τόσο μικρό όσο το 8, αλλά ο Σινγκμάστερ πίστευε ότι θα μπορούσε να είναι 10 ή 12. Είναι επίσης άγνωστο αν κάποιος αριθμός εμφανίζεται ακριβώς πέντε ή επτά φορές.

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

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
• Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
• Θεωρία Αριθμών και Εφαρμογές
• Υπολογιστική Θεωρία Αριθμών

Δείτε επίσης

• Θεωρία αριθμών
• Αλγεβρική θεωρία αριθμών
• Συζυγής μιγαδικός αριθμός
• Δεύτερη Εικασία Χάρντι-Λίτλγουντ
• Ελλειπτική καμπύλη
• e (μαθηματική σταθερά)
• Πυθαγόρεια τετράδα
• Άρτιοι και περιττοί αριθμοί
• Τετραγωνικός αριθμός
• Κρυπτογραφία ελλειπτικών καμπυλών
• Προβλήματα του Λαντάου
• Εικασία του Κράμερ
• Εικασία του Γκόλντμπαχ
• Θεμελιώδες θεώρημα αριθμητικής
• Αλγεβρική γεωμετρία
• Υπόθεση H του Σίνζελ
• Κλάση συζυγίας
• Ευκλείδειος χώρος

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

• Mezo, Istvan (19 Αυγούστου 2019). Combinatorics and Number Theory of Counting Sequences. CRC Press. ISBN 978-1-351-34638-2. 
• Shahriari, Shahriar (22 Ιουλίου 2021). An Invitation to Combinatorics. Cambridge University Press. ISBN 978-1-108-75642-6. 
• Rubinstein-salzedo, Simon (19 Ιουλίου 2023). Transition To Proofs. World Scientific. ISBN 978-981-12-7210-3. 
• Bauer, Craig (14 Μαΐου 2020). Discrete Encounters. CRC Press. ISBN 978-0-429-68289-6. 
• Singmaster, David (21 Σεπτεμβρίου 2021). Adventures In Recreational Mathematics (In 2 Volumes). World Scientific. ISBN 978-981-12-5162-7. 
• Zazkis, Rina· Mason, John (23 Μαΐου 2021). The Learning and Teaching of Number: Paths Less Travelled Through Well-Trodden Terrain. Taylor & Francis. ISBN 978-0-429-75796-9. 
• Wells, David (4 Σεπτεμβρίου 1997). The Penguin Dictionary of Curious and Interesting Numbers. Penguin UK. ISBN 978-0-14-192940-8. 
• Ribenboim, Paulo (9 Μαρτίου 2013). The Little Book of Bigger Primes. Springer Science & Business Media. ISBN 978-1-4757-4330-2. 
• Dickson, Leonard Eugene (2005) [1920]. History of the Theory of Numbers. Volume II: Diophantine analysis. Mineola, NY: Dover Publications. ISBN 978-0-486-44233-4. MR 0245500. Zbl 1214.11002. 
• Devlin, Keith (1994). All the Math That's Fit to Print: Articles from The Guardian. Cambridge University Press. ISBN 978-0-88385-515-7. 
• Singmaster, David (23 Φεβρουαρίου 2016). Problems For Metagrobologists: A Collection Of Puzzles With Real Mathematical, Logical Or Scientific Content. World Scientific. ISBN 978-981-4663-66-3. 

Παραπομπές

• Beck, Matthias; Geoghegan, Ross (2010), The Art of Proof: Basic Training for Deeper Mathematics, New York: Springer, ISBN 978-1-4419-7022-0 .
• Bóna, Miklós (2011), A Walk Through Combinatorics (3rd έκδοση), New Jersey: World Scientific, ISBN 978-981-4335-23-2 .
• Borwein, Jonathan M.; Borwein, Peter B. (July 1998), Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, Wiley, σελ. 91–101, ISBN 978-0-471-31515-5, http://www.wiley.com/WileyCDA/WileyTitle/productCd-047131515X.html 
• Smith, Karl J. (NaN). «Pascal's Triangle». The Two-Year College Mathematics Journal 4 (1): 1. doi:10.2307/2698949. 
• Rumney, M.; Primrose, E.J.F. (Δεκεμβρίου 1969). «Some Generalizations of the Pascal Triangle». The Mathematical Gazette 53 (386): 388–394. doi:10.2307/3612469. https://archive.org/details/sim_mathematical-gazette_1969-12_53_386/page/388. 
• 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, Richardl; 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