Παραγωγή ομάδας από μικρό υποσύνολο

#1

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

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

της

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

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

lemonidas · #2

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$ όπου έπεται το ζητούμενο.. Η ιδέα αυτή όμως δεν γενικεύεται για γενικά πεπερασμένες (μη αβελιανές) ομάδες..

#3

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

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

Ilias_Zad · #4

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

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

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

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

θεωρούμε το

ένωση

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

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

το

ένωση

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

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

#5

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

Παίρνω ένα σύνολο $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

, τότε $s_{i_1} = s_{j_1} \cdots s_{j_q} s_{i_r}^{-1} \cdots s_{i_2}^{-1}$ και άρα το $S \setminus {s_{i_1}}$ γεννάει την

, άτοπο.
(β) Αν i_1 > j_i

τότε με παρόμοιο τρόπο καταλήγουμε σε άτοπο.
(γ) Αν i_1 = j=1

τότε $s_{i_2} \cdots s_{i_r} = s_{j_2} \cdots s_{j_q}$ και επαναλαμβάνουμε. Είτε θα καταλήξουμε σε άτοπο είτε σε q=r

και $s_{i_1} = s_{j_1}, \ldots, s_{i_r} = s_{j_r}$

Άρα $2^k \leqslant |G|$ και άρα $k \leqslant \log_2{|G|}$ .

Παραγωγή ομάδας από μικρό υποσύνολο

Παραγωγή ομάδας από μικρό υποσύνολο

Re: Παραγωγή ομάδας από μικρό υποσύνολο

Re: Παραγωγή ομάδας από μικρό υποσύνολο

Re: Παραγωγή ομάδας από μικρό υποσύνολο

Re: Παραγωγή ομάδας από μικρό υποσύνολο

Μέλη σε σύνδεση