⚡Η ακολουθία Golay–Rudin–Shapiro: χάος από ±1 και μερικά αθροίσματα που μένουν θετικά

Η ακολουθία Golay–Rudin–Shapiro είναι μια απολύτως προσδιορισμένη ακολουθία που, όταν τη βλέπουμε για πρώτη φορά, μοιάζει σχεδόν τυχαία. Κάθε όρος της είναι \(+1\) ή \(-1\), αλλά πίσω από τις συνεχείς εναλλαγές κρύβεται μια εξαιρετικά αυστηρή δυαδική δομή.

Ο αναδρομικός ορισμός

\[ a(0)=1,\qquad a(2n)=a(n),\qquad a(2n+1)=(-1)^n a(n). \]

Οι πρώτοι όροι, αρχίζοντας από \(n=0\), είναι

\[ 1,\ 1,\ 1,\ -1,\ 1,\ 1,\ -1,\ 1,\ 1,\ 1,\ 1,\ -1,\ -1,\ -1,\ 1,\ -1,\ldots \]

Ο δυαδικός κανόνας

Υπάρχει ένας κομψός τρόπος να υπολογίσουμε τον \(a(n)\) απευθείας. Γράφουμε τον \(n\) στο δυαδικό σύστημα και μετράμε πόσες φορές εμφανίζεται το μπλοκ \(11\), επιτρέποντας και επικαλύψεις. Αν το πλήθος αυτό είναι \(r(n)\), τότε

\[ a(n)=(-1)^{r(n)}. \]

Για παράδειγμα, \(7=(111)_2\). Το μπλοκ \(11\) εμφανίζεται δύο φορές, άρα \(a(7)=(-1)^2=1\). Αντίθετα, \(6=(110)_2\) περιέχει μία εμφάνιση, οπότε \(a(6)=-1\).

Το ερώτημα των μερικών αθροισμάτων

Ορίζουμε

\[ s(n)=\sum_{k=0}^{n}a(k). \]

Οι πρώτες τιμές είναι

\[ 1,\ 2,\ 3,\ 2,\ 3,\ 4,\ 3,\ 4,\ 5,\ 6,\ 7,\ 6,\ 5,\ 4,\ 5,\ 4,\ldots \]

Παρατηρούμε ότι παραμένουν θετικές. Είναι άραγε αυτό αληθές για κάθε \(n\); Ναι.

Η απόδειξη ότι \(s(n)>0\) για κάθε \(n\ge0\)

Ομαδοποιούμε τους όρους ανά δύο. Από την αναδρομή έχουμε

\[ \begin{aligned} s(2N+1) &=\sum_{m=0}^{N}\bigl(a(2m)+a(2m+1)\bigr)\\ &=\sum_{m=0}^{N}a(m)\bigl(1+(-1)^m\bigr). \end{aligned} \]

Όταν το \(m\) είναι περιττό, η παρένθεση μηδενίζεται. Όταν \(m=2j\), ισούται με \(2\), και επειδή \(a(2j)=a(j)\), παίρνουμε

\[ \boxed{\displaystyle s(2N+1)= 2s\!\left(\left\lfloor\frac{N}{2}\right\rfloor\right)}. \]

Για τους άρτιους δείκτες, όταν \(N\ge1\),

\[ \begin{aligned} s(2N) &=s(2N-1)+a(2N)\\ &=2s\!\left(\left\lfloor\frac{N-1}{2}\right\rfloor\right)+a(N). \end{aligned} \]

Τώρα εφαρμόζουμε ισχυρή επαγωγή. Έχουμε \(s(0)=1\). Αν όλα τα προηγούμενα μερικά αθροίσματα είναι τουλάχιστον \(1\), τότε

\[ s(2N+1)\ge2 \]

και, επειδή \(a(N)\in\{-1,1\}\),

\[ s(2N)\ge2\cdot1-1=1. \]

Άρα \(s(n)\ge1\) για κάθε \(n\ge0\). Το πλήθος των \(+1\) υπερβαίνει πάντοτε το πλήθος των \(-1\) σε κάθε αρχικό τμήμα της ακολουθίας.

Γιατί είναι διάσημη;

Η ακολουθία έχει πολύ μικρότερες συσχετίσεις από όσες θα περίμενε κανείς από έναν τόσο απλό ντετερμινιστικό κανόνα. Οι σχετικοί πολυωνυμικοί σχηματισμοί παρουσιάζουν ισχυρή ακύρωση, με μέγεθος της τάξης της τετραγωνικής ρίζας του πλήθους των όρων. Αυτή η «ψευδοτυχαία» συμπεριφορά την έκανε σημαντική στην αρμονική ανάλυση, στη θεωρία ακολουθιών και σε εφαρμογές επικοινωνιών και ραντάρ.

Μια ακολουθία μπορεί να μοιάζει τυχαία, να εμφανίζει ισχυρές ακυρώσεις και ταυτόχρονα να μην αφήνει ποτέ το σωρευτικό της άθροισμα να φτάσει στο μηδέν.

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →

Σχετικά άρθρα