mathematica.gr

Δημοσιεύτηκε: **Παρ Οκτ 08, 2010 12:24 pm**

Να δειχθεί ότι για κάθε πεπερασμένη ομάδα

υπάρχει ένα υποσύνολο

της

με $|S| \leqslant \log_2|G|$ το οποίο παράγει την

. Να δειχθεί επίσης ότι υπάρχουν άπειρες ομάδες για τις οποίες το φράγμα δεν μπορεί να βελτιωθεί.

Δημοσιεύτηκε: **Κυρ Οκτ 10, 2010 6:18 pm**

Demetres έγραψε:Να δειχθεί ότι για κάθε πεπερασμένη ομάδα υπάρχει ένα υποσύνολο της με $|S| \leqslant \log_2|G|$ το οποίο παράγει την . Να δειχθεί επίσης ότι υπάρχουν άπειρες ομάδες για τις οποίες το φράγμα δεν μπορεί να βελτιωθεί.

Μια πρώτη προσπάθεια (μισή)...

Αρχικά το παράδειγμα:

Οι ομάδες της μορφής $Z_2^r = Z_2 \times Z_2....\times Z_2$ παράγονται από τα σύνολα της μορφής {(1,0....,0), (0,1,....0),....(0,...1)}

τα οποία είναι r το πλήθος όπου η τάξη της ομάδας είναι 2^r

. Για τις άπειρες αυτές ομάδες το φράγμα δεν βελτιώνεται αφού το παραπάνω σύνολο αποτελεί βάση του αντίστοιχου διανυσματικού χώρου..

Από αυτό το παράδειγμα μπορούμε να γενικεύσουμε για πεπερασμένες (άρα και πεπερασμένα παραγόμενες) αβελιανές όμως ομάδες για τις οποίες γνωρίζουμε ότι θα είναι ισόμορφες με κάποια ομάδα της μορφής:
$Z_{p_1^{r_1}} \times Z_{p_2^{r_2}}....\times Z_{p_n^{r_n}}$ όπου τα p_i

είναι πρώτοι όχι αναγκαστικά διαφορετικοί. Τετριμένα μια τέτοια ομάδα παράγεται από ένα υποσύνολο n στοιχείων αντίστοιχα με το αρχικό παράδειγμα. Τώρα η τάξη της ομάδας είναι $\Pi p_i^{r_i}$ και το υποσύνολο είναι τάξης n.. Όμως $p_i \geq 2, r_i \geq 1$ και άρα $|G| \geq 2^n$ όπου έπεται το ζητούμενο.. Η ιδέα αυτή όμως δεν γενικεύεται για γενικά πεπερασμένες (μη αβελιανές) ομάδες..

Δημοσιεύτηκε: **Δευ Οκτ 11, 2010 1:52 am**

Σωστά μένει να αποδειχθεί και για μη αβελιανές ομάδες. Δίνω μια μικρή υπόδειξη

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Δημοσιεύτηκε: **Δευ Οκτ 11, 2010 4:25 pm**

Η ομάδα δεν πρέπει να είναι η τετριμμένη για να ισχύει το ζητούμενο.
Θεωρούμε $A=\{x\}$ , με

τυχαίο (όχι το ταυτοτικό) στοιχείο στο

.
Έστω ότι παράγει

στοιχεία. Τότε αν δεν χτυπάει ένα στοιχείο

θεωρούμε το

ένωση

.
Επειδή το gspan(A)

έχει κενή τομή με το span(A)

το

ένωση

παράγει ένα σύνολο τουλάχιστον

στοιχείων.
Αν δεν παράγουμε ούτε με αυτό όλη την ομάδα συνεχίζουμε έτσι.

Δημοσιεύτηκε: **Δευ Οκτ 11, 2010 5:43 pm**

Σαφώς η λύση του Ηλία είναι πολύ πιο σύντομη από την δική μου. Βάζω όμως και τον δικό μου τρόπο επίλυση.

Παίρνω ένα σύνολο $S = \{s_1,\ldots,s_k\}$ το οποίο να γεννάει την

με

ελάχιστο. Ισχυρίζομαι ότι τα 2^k

στοιχεία της μορφής $s_{i_1} \cdots s_{i_r}$ όπου $1 \leqslant i_1 < \cdots < i_r \leqslant k$ , είναι διαφορετικά μεταξύ τους. Πράγματι αν $s_{i_1} \cdots s_{i_r} = s_{j_1} \cdots s_{j_q}$ τότε
(α) Αν i_1 < j_i