30 Δεκ 2010

Μαθηματική επαγωγή και η εικασία του Goldbach

Η μαθηματική επαγωγή είναι ένα πολύ ισχυρό αποδεικτικό εργαλείο. Χρησιμοποιείται για να αποδείξουμε ότι μία πρόταση P(n) που εξαρτάται από κάποιον ακέραιο n ισχύει για όλους τους ακεραίους. Η στρατηγική είναι η εξής:
Εικόνα 1. 
  • Αρχικά εξετάζουμε αν μία πρόταση ισχύει για κάποιον ελάχιστο ακέραιο n0 (συνήθως αυτός είναι ο 1).
  • Υποθέτουμε ότι ισχύει για κάποιον αυθαίρετο ακέραιο n > n0 (αυτή είναι η επαγωγική υπόθεση)
  • Χρησιμοποιώντας την επαγωγική υπόθεση (δηλ. ότι ισχύει για τον n), αποδεικνύουμε ότι ισχύει και για τον επόμενο ακέραιο n+1.
Η λογική της μαθηματικής επαγωγής παρομοιάζεται συχνά με το φαινόμενο του ντόμινο (Εικ. 1). Εφόσον το τουβλάκι n ρίχνει το επόμενό του (η ισχύς της πρότασης για τον n έχει ως αποτέλεσμα την ισχύ της και για τον n+1) και το τουβλάκι n είναι αυθαίρετο, τότε και το επόμενο τουβλάκι n+1 θα ρίξει το επόμενό του, (n+1)+1 κ.ο.κ.

Ένα αντιπαράδειγμα

Πολλές φορές δεν είναι τόσο σαφής η χρησιμότητα της επαγωγής και το πόσο ισχυρό εργαλείο είναι. Πολλοί πιστεύουν ότι αν κάτι ισχύει μέχρι κάποιο αρκετά μεγάλο n τότε θα ισχύει για όλους τους ακεραίους. Ένα αντιπαράδειγμα είναι το παρακάτω.

Θέλουμε να εξετάσουμε την ισχύ της πρότασης
Ο αριθμός f(n) = n2 - n + 41 είναι πρώτος για κάθε n ≥ 1.
Πράγματι για n=1 έχουμε f(1) = 41, πού είναι πρώτος. Για n = 2 έχουμε f(2) = 43 που είναι πρώτος και για n = 3,4,\ldots,40 έχουμε αντίστοιχα
47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601
που είναι όλοι πρώτοι.
Όμως για n = 41 έχουμε f(41) = 1681 = 41×41, συνεπώς η πρόταση δεν ισχύει.

Η εικασία του Goldbach

To 1742 ο Γερμανός μαθηματικός Christian Goldbach σε ένα γράμμα του στον ελβετό μαθηματικό Leonhard Euler έγραψε:

"Κάθε άρτιος αριθμός μεγαλύτερος του 2 μπορεί να γραφτεί ως το άθροισμα δύο πρώτων αριθμών. Θεωρώ ότι αυτό είναι ένα βέβαιο θεώρημα, μόνο που δεν μπορώ να το αποδείξω."

Η πρόταση αυτή έγινε γνωστή ως η εικασία του Goldbach και παρά το ότι από τότε έχουν περάσει περισσότερα από 250 χρόνια, κανένας δεν έχει καταφέρει να την αποδείξει ή να την απορρίψει (να βρει, δηλαδή, έναν αριθμό για τον οποίο δεν ισχύει). Αν εξετάσουμε κατά σειρά τους πρώτους 12 άρτιους βλέπουμε ότι πράγματι
4 = 2+210 = 3+716 = 7+9 22 = 11+11
6 = 3+312 = 5+718 = 7+1124 = 11+13
8 = 3+514 = 7+720 = 7+1326 = 13+13
Μάλιστα η εικασία του Goldbach έχει επαληθευτεί για όλους τους αριθμούς μέχρι κάποιον αριθμό της τάξης του 1,6×1018 (ίσως και παραπάνω ο υπολογιστής που τα υπολογίζει ακόμα τρέχει).

Είναι όμως δυνατό να βρεθεί ένας αριθμός για τον οποίο δεν ισχύει η εικασία του Goldbach, δεδομένου ότι ισχύει μέχρι έναν τόσο μεγάλο αριθμό της τάξης του 1,6×1018; Δε μιλάμε τώρα για το 41 αλλά για έναν τεράστιο αριθμό...

Ένα πιο πειστικό αντιπαράδειγμα

Θέλουμε να εξετάσουμε την ισχύ της πρότασης
Ο αριθμός S(n) = 991n2 + 1 δεν είναι τέλειο τετράγωνο
Η πρόταση αυτή δεν ισχύει. Αν όμως αρχίσουμε να εξετάζουμε έναν-έναν τους αριθμούς S(n) δε μας φτάνουν ούτε 1000 ζωές για να βρούμε τον πρώτο αριθμό για τον οποίο δεν ισχύει, αφού ο μικρότερος αριθμός για τον οποίο η παραπάνω πρόταση είναι αναληθής είναι ο
n0 = 12.055.735.790.331.359.447.442.538.767 > 1,2×1028.
Για να κατανοήσουμε πόσο μεγάλος είναι αυτός ο αριθμός αρκεί να αναλογιστούμε το εξής:
Η ηλικία του σύμπαντος υπολογίζεται σήμερα από 13,5 ως 20 δισεκατομμύρια (σημερινά ηλιακά) χρόνια. Ας πάρουμε το μεγαλύτερο αριθμό από τους δύο.

Αν υπήρχε ένας άνθρωπος που εξέταζε αν η παραπάνω πρόταση ισχύει με ρυθμό έναν αριθμό το δευτερόλεπτο, τότε σήμερα δε θα είχε ξεπεράσει ούτε το 1018 (αριθμό κατά πολύ μικρότερο του 1028).

Πηγή (δύο παραδειγμάτων): Journey into Mathematics: An Introduction to Proofs του J.J. Rotman

4 σχόλια:

  1. Υπάρχει άλλη μία σχετικά διάσημη περίπτωση όπου η διάψευση μίας πρότασης στη θεωρία αριθμών γίνεται για τόσο μεγάλο $n$, που η απλή επισκόπηση των αριθμητικών δεδομένων μπορεί εύκολα να μας οδηγήσει σε λανθασμένο συμπέρασμα. Αναφέρομαι στη σχέση ανάμεσα στη συνάρτηση $\pi(x)$, που δίνει το πλήθος των πρώτων αριθμών που είναι $\leq x$, και στο λογαριθμικό ολοκλήρωμα $\mathrm{li}(x)=\int_0^x\frac{dt}{\ln t}$.

    Σύμφωνα με το θεώρημα των πρώτων αριθμών ισχύει η ασυμπτωτική σχέση $\pi(x)\sim\mathrm{li}(x)$ (νομίζω ότι ο Riemann το απέδειξε πρώτος). Για μικρές τιμές του $x$ ισχύει $\pi(x)<\mathrm{li}(x)$. Και όταν λέμε "μικρές τιμές" εννοούμε ότι δεν υπάρχουν σημεία τομής των δύο καμπυλών για $x<10^{14}$ (όπως αποδείχθηκε αυστηρά το 2008). Μάλιστα το καλύτερο άνω φράγμα που έχει βρεθεί έως τώρα (εν έτει 2000) για το πρώτο σημείο όπου $\pi(x)>\mathrm{li}(x)$, είναι γύρω στο $1.39822\cdot 10^{316}$. Αυτό σημαίνει ότι σίγουρα θα συναντήσουμε σημείο τομής των καμπυλών έως το $$1.39822\cdot 10^{316}$, αλλά μέχρι τώρα δεν έχει βρεθεί ούτε μία συγκεκριμένη τιμή για την οποία να ισχύει αυτή η ανισότητα!

    Ο πρώτος που απέδειξε ότι υπάρχει σημείο τομής των καμπυλών ήταν ο Littlewood, ενώ ο μαθητής του, ονόματι Skewes, βρήκε και το πρώτο συγκεκριμένο άνω φράγμα, που ήταν ο τερατώδης αριθμός $e^{e^{e^79}}$. Για πολύ καιρό αυτός ο αριθμός είχε τη φήμη του μεγαλύτερου αριθμού που υπεισήλθε ποτέ σε αυστηρή μαθηματική απόδειξη (βέβαια το ρεκόρ αυτό έχει καταρριφθεί εδώ και χρόνια)!

    Το παράδειγμα αυτό καθώς και αυτά που παρέθεσε ο csar μας δείχνουν ότι δεν μπορούμε να βγάζουμε ασφαλή συμπεράσματα στα μαθηματικά (και ιδίως στη θεωρία αριθμών) από στατιστικές παρατηρήσεις.

    ΧΛ

    Πηγή: wikipedia
    http://en.wikipedia.org/wiki/Logarithmic_integral
    http://en.wikipedia.org/wiki/Skewes%27_number

    ΑπάντησηΔιαγραφή
  2. Πολύ εντυπωσιακό το σχόλιό σου ΧΛ!

    Παρατηρώ ότι ο LaTeX interpreter δε δουλεύει τέλεια. Μέχρι να αντιμετωπιστεί αυτό το πρόβλημα, δύο συμβουλές για όσους γράφετε εξισώσεις στο LaTeX:
    - Μην αφήνετε κενά μέσα στην εξίσωση διότι ο editor του blogger μερικές φορές παίρνει την πρωτοβουλία και εισάγει "αόρατα" σύμβολα (όπως πχ το nonbreaking space), κάτι που μπερδεύει τον LaTeX interpreter.
    - Για απλά μαθηματικά (εκθέτες, δείκτες και κάποια απλά σύμβολα) μπορείτε να χρησιμοποιείτε και HTML tags (έχω βάλει μία σχετική σελίδα εδώ)

    Τέλος, αν θέλετε να δημιουργήσετε links στις πηγές σας μπορείτε να πειρκλείσετε το link σας σε <a href="url διεύθυνση">κείμενο που φαίνεται</a>

    ΑπάντησηΔιαγραφή
  3. Βασικά το σφάλμα ήταν δικό μου, γιατί έβαλα κατά λάθος διπλό "δολλάριο" (αντί για μονό) σε μία εξίσωση, και από κει και πέρα πήρε φαλάγγι και τις υπόλοιπες... Μήπως είναι δυνατόν στην προεπισκόπηση να γίνεται και η μετατροπή του κώδικα σε εξισώσεις; Αν ναι, θα μπορούμε να βλέπουμε τα σφάλματα πριν υποβάλουμε το τελικό κείμενο για δημοσίευση.

    ΧΛ

    ΑπάντησηΔιαγραφή
  4. dim-val
    ΛΑΘΟΣ αν το f(k)=k^2-k+41 ειναι πρωτος
    πρεπει να δειξεις οτι και το
    f(k+1)=(k+1)^2-(k+1)+41 ειναι πρωτος
    αυτο ειναι η επαγωγη.

    ΑπάντησηΔιαγραφή