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

Ιουνίου 6, 2008

Ρίζες στην τύχη

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

Έστω ότι f(x_1,\ldots,x_n) είναι ένα πολυώνυμο, βαθμού \le d σε κάθε μεταβλητή, και S \subseteq {\mathbb R} είναι ένα πεπερασμένο σύνολο.

Επιλέγουμε τους τυχαίους αριθμούς X_1,\ldots,X_n \in S ομοιόμορφα και ανεξάρτητα από το S. Δείξτε ότι

\displaystyle {\mathbb Pr}(f(X_1,\ldots,X_n) = 0) \le \frac{d}{|S|}.

Advertisements

8 Σχόλια »

  1. Έστω σταθεροποιημένα x_1,\cdots, x_{n-1} στοιχεία του S. Ορίζουμε f(x) = f(x_1,\cdots,x_{n-1},x).

    Υποθέτουμε επίσης ότι d\leq |S|, αλλιώς το πρόβλημα είναι τετριμμένο.

    Καταρχήν αν το S δεν περιέχει όλες τις ρίζες της f(x), αν αντικαταστήσουμε μερικά από τα στοιχεία του S που δεν είναι ρίζες του f(x) με τις ρίζες που δεν περιέχονται, έχουμε ότι P(f(X)=0)\leq P_1(f(X)=0) όπου η καινούρια πιθανότητα ορίζεται στο τροποποιημένο S. Η τελευταία πιθανότητα είναι ακριβώς ίση με \frac{d_1}{|S|}\leq \frac{d}{|S|} όπου d_1 το πλήθος των διακεκριμένων ριζών του f(x). Επομένως έχουμε ότι για το αρχικό S, P(f(X)=0)\leq \frac{d}{|S|}.

    Τώρα υπολογίζουμε τα εξής:

    P(f(X_1,\cdots, X_n)=0) =
    \ \ \  \sum_{x_1,\cdots,x_{n-1}\in S}
    \ \ \ \  P(f(X_1,\cdots, X_n)=0|X_1=x_1,\cdots, X_{n-1}=x_{n-1})
    \ \ \ \cdot P(X_1=x_1,\cdots, X_{n-1}=x_{n-1}).

    Αυτό είναι απλά ο νόμος της ολικής πιθανότητας. Αν θέσουμε X=X_n έχουμε τώρα ότι η παραπάνω πιθανότητα είναι,
    P(f(X_1,\cdots, X_n)=0) = \sum_{x_1,\cdots,x_{n-1}\in S}
    \ \ \ P(f(x_1,\cdots, x_{n-1},X)=0)\cdot
    \ \ \ \ \cdot P(X_1=x_1,\cdots, X_{n-1}=x_{n-1}).

    Κάθε ένα από τα P(f(x_1,\cdots, x_{n-1},X)=0) φράσσεται, όπως είδαμε πιο πάνω, από \frac{d}{|S|}, επομένως

    P(f(X_1,\cdots, X_n)=0) \leq
    \ \ \ \frac{d}{|S|}\sum_{x_1,\cdots,x_{n-1}\in S} P(X_1=x_1,\cdots, X_{n-1}=x_{n-1}).

    Όλα τα ενδεχόμενα {X_1=x_1,\cdots, X_{n-1}=x_{n-1}} είναι ξένα μεταξύ τους, οπότε οι πιθανότητές τους έχουν άθροισμα το πολύ ένα, επομένως παίρνουμε το ζητούμενο.

    Μου αρέσει!

    Σχόλιο από ikonst — Ιουνίου 13, 2008 @ 11:28 πμ

  2. Το αρχικό θεώρημα προφανώς δεν ισχύει αν το πολυώνυμο είναι ταυτοτικά 0 (θεώρησα περιττό να το γράψω – κακώς).

    Τι γίνεται όμως αν το πολυώνυμο μιας μεταβλητής που ορίζεις είναι ταυτοτικά 0 για μια συγκεκριμένη επιλογή των x_1,\ldots,x_{n-1}; Τότε δεν ισχύει το φράγμα d/|S|.

    Η απόδειξη θέλει επιδιόρθωση …

    Μου αρέσει!

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

  3. Σωστά, στην αρχή το είχα δει ότι χρειαζόταν έναν τέτοιο περιορισμό αλλά στην πορεία μου ξέφυγε. Θα το διορθώσω όταν μπορέσω.

    Μου αρέσει!

    Σχόλιο από ikonst — Ιουνίου 14, 2008 @ 8:41 πμ

  4. Θα κάνω μια δοκιμή για την επιδιόρθωση της ιδέας του ikonst.

    Νομίζω πως δεν βλάπτει τη γενικότητα να υποθέσουμε πως 0 \notin S .
    Αποδεικνύουμε το ζητούμενο με επαγωγή στο n .
    Για n έχουμε πολυώνυμο μιας μεταβλητής που -από το Θεμελιώδες
    Θεώρημα της Άλγεβρας- έχει το πολύ d ρίζες και άρα το φράγμα ισχύει.
    Υποθέστε ότι ισχύει για όλα τα πολυώνυμα με n-1 μεταβλητές και σταθεροποιήστε
    πολυώνυμο f(x_1,\ldots , x_n) που δεν είναι ταυτοτικά μηδέν.
    Τότε
    \mathbb{P}[f(X_1,\ldots , X_n)=0] = \sum_{x\in S} \mathbb{P}[f(X_1,\ldots , X_{n-1},x)=0| X_n=x] \mathbb{P}[X_n=x] =
    Τώρα, δεδομένου ότι X_n =x , το εναπομείναν πολυώνυμο αποτελείται από n-1 μεταβλητές
    και η επαγωγική υπόθεση δίδει ότι η πιθανότητα να ειναι μηδεν δεν είναι μεγαλύτερη από \frac{d}{|S|} .
    Συνεπώς \mathbb{P}[f(X_1,\ldots , X_n)=0] \leq \frac{d}{|S|} .

    Είναι επίσης αξιοσημείωτο το γεγονός πως το φράγμα δεν εξαρτάται από το n .

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαρτίου 10, 2012 @ 12:54 πμ

  5. Νομίζω ότι η απόδειξή σου έχει το ίδιο πρόβλημα με την προηγούμενη.

    Το πολυώνυμο f(X_1,\ldots,X_n) μπορεί να μην είναι ταυτοτικά μηδέν αλλά αυτό δε σημαίνει ότι ούτε το f(X_1,\ldots,X_{n-1},x) είναι αν η τελευταία μεταβλητή πάρει κάποια συγκεκριμένη τιμή. Π.χ. αν έχεις ένα πολυώνυμο δύο μεταβλητών xy-xy^2 και θέσεις y=1 το πολυώνυμο μιας μεταβλητής που απομένει είναι ταυτοτικά 0. Και αν το f(X_1,\ldots,X_{n-1},x) είναι ταυτοτικά 0 για κάποια τιμή του x τότε δε μπορείς να χρησιμοποιήσεις την επαγωγική σου υπόθεση.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 11, 2012 @ 11:26 πμ

  6. Θα κάνω μία ακόμη προσπάθεια.

    Γράψτε f(x, \vec y) αντί για f(x_1, \dots, x_n). Από το σχόλιο 4, το ζητούμενο ισχυει n = 1.
    Επαγωγικά υποθέστε ‘οτι ισχύει για πολυώνυμα που έχουν n-1 μεταβλητές.

    Έστω M = \{x \in S \colon f(x, \vec y) = 0 \; \forall \vec y \}. Φυσικά m := |M| \le d .
    Γράψτε επίσης \displaystyle f(x, \vec y) = x^m Q(x,\vec y) + x^{m-1} R_{m-1}(\vec y) + \dotsc +   x^0  R_{0}(\vec y),  (*)
    όπου τα πολυώνυμα R_j εξαρτώνται μόνον από το \vec y και το Q(x,\cdot) ίσως εξαρτάται από το x.
    Κατόπιν δείχνουμε ότι \text{deg} R_i \le d-m.

    Υποθέστε ότι m > 0. Αν ισούται με μηδέν, τα πολυώνυμα R_i(\cdot) δεν ορίζονται και άρα δεν έχουμε να αποδείξουμε τίποτα.
    Έστω x_0, \dots, x_{m-1} τα (διαφορετικά) στοιχεία του M. Θεωρήστε τις ακόλουθες m εξισώσεις:
    \displaystyle - x_i^m Q(x_i,\vec y) = x_i^{m-1} R_{m-1}(\vec y) + \dotsc +   x_i^0 R_{0}(\vec y).

    Αν \vec  r := (  R_{0}(\vec y), \dots, R_{m-1}(\vec y),)^T και \vec q := ( x_{0}^m Q(x,\vec y),  \dots,  x_{m-1}^m Q(x,\vec y))^T,
    τότε οι παραπάνω εξισώσεις μπορούν να γραφούν ως V \cdot r = -q
    όπου V είναι ο πίνακας Vandermonde
    V  = \begin{pmatrix}   1      & x_0    & x_0^2  & \cdots & x_0^{m-1} \\   1      & x_1    & x_1^2  & \cdots & x_1^{m-1} \\   1      & x_2    & x_2^2  & \cdots & x_2^{m-1} \\   \vdots & \vdots & \vdots & \ddots & \vdots    \\   1      & x_{m-1}    & x_{m-1}^2  & \cdots & x_{m-1}^{m-1} \end{pmatrix}

    http://en.wikipedia.org/wiki/Vandermonde_matrix

    Σύμφωνα με την wikipedia ο πίνακας V είναι αντιστρέψιμος για (ανα δύο) διαφορετικά x_i και συνεπώς
    \vec r = -V^{-1} \vec q. Τώρα, από την παρατήρηση ότι \deg Q \le d - m, παίρνουμε \deg R_{i} \le d -m .

    Συνεπώς
    \displaystyle \mathbb{P}(f(x,\vec y) = 0) = \sum_{x_i \in M} \mathbb{P}(x = x_i, f(x_i,\vec y) = 0)  + \sum_{x_i \in S\setminus M} \mathbb{P}(x = x_i, f(x_i,\vec y) = 0)
    \displaystyle = \sum_{\xi \in M} \mathbb{P}(x = \xi)  + \sum_{\xi \in S\setminus M} \mathbb{P}(x = \xi) \mathbb{P}(\underbrace{f(\xi,\vec y)}_{\text{deg} \le d - m} = 0)
    όπου τα πολυώνυμα n-1 μεταβλητών f(\xi, \vec y),  \xi \in S\setminus M δεν μηδενίζονται και των οποίων
    ο βαθμός είναι \le d-m (από την (*)).
    Η επαγωγική υπόθεση δίδει η τελευταία ποσότητα είναι
    \displaystyle\le \frac{m}{|S|} +  \frac{|S| - m}{|S|} \frac{d - m}{|S|} \le \frac{d}{|S|} .

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαρτίου 20, 2012 @ 6:33 μμ

  7. Στην 6η γραμμή από το τέλος ήθελα να γράψω \xi αντί του x_i .

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαρτίου 20, 2012 @ 6:50 μμ

  8. Σωστό.

    Αυτό είναι το Λήμμα Schwartz-Zippel.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 23, 2012 @ 1:13 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Blog στο WordPress.com.

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