Προβλήματα Μαθηματικών

Ιουνίου 2, 2008

Τα πάντα είναι πολυώνυμα mod p

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 9:52 μμ

Αν p είναι ένας πρώτος αριθμός, δείξτε ότι κάθε συνάρτηση

f:\{0,1,\ldots,p-1\} \to \{0,1,\ldots,p-1\}

μπορεί να παρασταθεί από ένα πολυώνυμο p(x) = a_0+a_1x+\cdots+a_{p-1}x^{p-1} \bmod p.

Advertisements

2 Σχόλια »

  1. Ορίζουμε

    b_i=i(i-1) .. \left(i-(i-1)\right)
    \ \ \ \cdot \left(i-(i+1)\right) .. (i-p+1) \pmod{p}

    a_i=b_i^{-1}\cdot f(i)

    (Το b_i^{-1} συμβολίζει το αντίστροφο του b_i \pmod{p} το οποίο υπάρχει αφού κανένας από τoυς παράγοντες i-k του b_i δεν είναι διαιρετός από το p, άρα (b_i,p)=1, άρα υπάρχει λύση της ισοτιμίας b_i x\equiv 1 \pmod{p}), και τότε ορίζουμε

    p(x) = a_0(x-1)(x-2)..(x-p+1)
    \ \ \  + a_1(x-0)(x-2)..(x-p+1) + \cdots
    \ \ \  + a_{p-1}(x-0)(x-1) .. (x-p+2)

    Πιο γενικά μπορούμε να πούμε ότι εάν K σώμα και σημεία (a_0,b_0), (a_1,b_1), (a_2,b_2),\ldots, (a_n,b_n) \in K^2 με διαφορετικά a_i, τότε υπάρχει μοναδικό πολυώνυμο P(X)\in K[X] με βαθμό το πολύ n, για το οποίο να ισχύει P(a_i)=b_i για όλα τα i.

    Αλέξανδρος Συγκελάκης

    Μου αρέσει!

    Σχόλιο από cretanman — Ιουνίου 4, 2008 @ 4:09 μμ

  2. Σωστά. Η μέθοδος σου είναι η λεγόμενη παρεμβολή Lagrange προσαρμοσμένη στο τυχόν σώμα.

    Για το αρχικό πρόβλημα υπάρχει και μια άλλη μέθοδος, όχι όμως καλύτερη: τα διαφορετικά πολυώνυμα που μπορεί κανείς να φτιάξει αν επιλέξει ως συντελεστές όλα τα στοιχεία του σώματος και βαθμός μέχρι p-1 είναι όλα τους διαφορετικά και ως συναρτήσεις. Δεν υπάρχουν δηλ. δύο διαφορετικά πολυώνυμα που να παίρνουν πάντα τις ίδιες τιμές.

    Μετά παρατηρεί κανείς ότι το πλήθος των διαφορετικών συναρτήσεων είναι ακριβώς το ίδιο με αυτό των πολυωνύμων, δηλ. p^p. Άρα υπάρχει 1-1 αντιστοιχία ανάμεσα στις συναρτήσεις και τα πολυώνυμα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 4, 2008 @ 10:06 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: