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

Ιουνίου 7, 2010

Πώς να βρείτε αν μια ομάδα δεν είναι αβελιανή (αντιμεταθετική)

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 9:55 πμ

Μια ομάδα G με N στοιχεία σας δίνεται μέσω του πίνακα πολλαπλασιασμού της M. Αν τα στοιχεία της ομάδας είναι τα g_1, g_2, \ldots, g_N τότε το (i,j) στοιχείο του N\times N πίνακα M είναι το k αν και μόνο αν g_i g_j = g_k.

Αν για κάποια i,j έχουμε M_{i,j} \neq M_{j,i} τότε προκύπτει φυσικά ότι η ομάδα δεν είναι αντιμεταθετική.

Αν σας δώσουν μια ομάδα με τεράστιο N και αν για κάθε φορά που ζητάτε να μάθετε το στοιχείο M_{i,j} πληρώνετε ένα ευρώ βρείτε ένα τρόπο να ελέγχετε αν η ομάδα είναι αντιμεταθετική χωρίς να κάνετε πολλούς ελέγχους.

Είναι αποδεκτό να κάνετε λάθος, το να συμπεράνετε δηλ. ότι η ομάδα είναι αβελιανή ενώ δεν είναι, αλλά αυτό πρέπει να συμβαίνει με πολύ μικρή πιθανότητα, ας πούμε 10^{-6}.

Η μέθοδός σας μπορεί να χρησιμοποιεί τυχαίους αριθμούς.

Advertisements

3 σχόλια »

  1. Υπόδειξη:

    Πάρτε στην τύχη δύο στοιχεία της ομάδας και ελέγξτε (κοιτώντας τον πίνακα πολλαπλασιασμού) αν αντιμετατίθενται. Αν όχι τότε η απάντηση είναι φυσικά ότι η ομάδα δεν είναι αβελιανή. Αν ναι, τότε υπάρχει πιθανότητα η ομάδα να μην είναι αβελιανή.

    Βρείτε ένα άνω φράγμα για αυτή την πιθανότητα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 12, 2010 @ 5:28 μμ

  2. σχετικα υπαρχουν καποια πραγματα στο εξης link
    http://forum.math.uoa.gr/viewtopic.php?f=36&t=6073

    Μου αρέσει!

    Σχόλιο από ef8sof — Ιουνίου 16, 2010 @ 5:22 μμ

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

    Έχουμε λοιπόν, αν a, b \in G είναι τυχαία στοιχεία (ανεξάρτητα) και Z είναι το κέντρο της ομάδας (στοιχεία της που αντιμετατίθενται με τα πάντα) και C(a) είναι η υποομάδα των στοιχείων της G που αντιμετατίθενται με το a, ότι

    P(ab \neq ba) = P(b \notin C(a)) = P(b \notin C(a) \& a \notin Z)
    = P(b \notin C(a) | a \notin Z) P(a \notin Z) \ge \frac{1}{2}\cdot \frac{1}{2} = \frac{1}{4}.

    άρα η πιθανότητα σφάλματος στην περίπτωση που η ομάδα δεν είναι αβελιανή είναι το πολύ \frac{3}{4}. Αν θέλουμε η πιθανότητα σφάλματος να είναι το πολύ 10^{-6} δεν έχουμε παρά να επαναλάβουμε k ανεξάρτητες φορές το πείραμα αυτό οπότε η πιθανότητα σφάλματος γίνεται (3/4)^k και για να είναι αυτό το πολύ 10^{-6} αρκεί να πάρουμε k \ge 6 \log 10 / \log(4/3).

    Το σημαντικό εδώ, και μάλλον αναπάντεχο, είναι ότι η το k δεν εξαρτάται καθόλου από το πόσο μεγάλη είναι η ομάδα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 16, 2010 @ 11:33 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

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

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