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

Ιουνίου 14, 2012

Ομάδες και γεννήτορες

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

Αν G είναι μια πεπερασμένη ομάδα με n στοιχεία δείξτε ότι υπάρχουν k στοιχεία της G, με k\le \log_2 n, που παράγουν την G.

Advertisements

2 Σχόλια »

  1. Νομίζω πως η παρακάτω απόδειξη είναι standard.

    Έστω \gamma_1, \ldots , \gamma_k οι γεννήτορες τη G.
    Ονομάστε G_i την ομάδα που παράγεται από τα \gamma_1,\ldots,\gamma_i , i=1,\ldots ,k.
    Τότε |G_1| \geq 2 και, επαγωγικά, |G_i| \geq 2^i. Το τελευταίο είναι
    σωστό διότι, από το θεώρημα του Lagrange, η τάξη της G_i διαιρεί την τάξη
    της G_{i+1} (ως γνήσια υποομάδα) και άρα |G_{i+1}| \geq 2 \cdot |G_i|\geq 2^{i+1}, από επαγωγική υπόθεση.
    Συνεπώς, n = |G| = |G_k| \geq 2^k και το ζητούμενο έπεται.

    Είχατε κατά νου πιθανοθεωρητική απόδειξη ;

    Μου αρέσει!

    Σχόλιο από henk&christos — Ιουνίου 18, 2012 @ 7:30 μμ

  2. Σωστό.

    Όχι, δεν έχω άλλη απόδειξη κατά νου. Μια παρατήρηση μόνο για την απόδειξή σου: αν ξεκινήσεις όπως ξεκίνησες, αν απλά δηλ. υποθέσεις ότι οι \gamma_1,\ldots,\gamma_k είναι γεννήτορες, τότε δε σου εγγυάται τίποτα ότι δεν έχεις G_{i+1} = G_i για κάποιο i. Το πρόβλημα αίρεται απλά: υποθέτεις ότι το σύνολο γεννητόρων που παίρνεις είναι ελάχιστο, δε μπορείς δηλ. να παραλείψεις κανένα από αυτούς και να εξακολουθήσεις να παράγεις τη G.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 18, 2012 @ 7:34 μμ


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: