Τροποποίηση από Putnam

#1

Έστω

μια πεπερασμένη ομάδα και $S \subseteq G$ ένα σύνολο γεννητόρων της

με $S \neq G$ και $s \in S \Rightarrow s^{-1} \in S$ .

Επιλέγουμε ανεξάρτητα και ομοιόμορφα στην τύχη (με επανατοποθέτηση)

στοιχεία $g_1,\ldots,g_m$ του

και θέτουμε $g = g_1\cdots g_m$ . Να δειχθεί ότι υπάρχει $b \in (0,1)$ ούτως ώστε το όριο

$\displaystyle{ \lim_{m \to \infty} \frac{1}{b^m} \sum_{x \in G} \left( \Pr(x=g) - \frac{1}{n}\right)^2}$

να είναι θετικό και πεπερασμένο.

#2

Επαναφορά.

Nick1990 · #3

Δημήτρη, να υποθέσω ότι n είναι η τάξη της ομάδας;

#4

Ναι. Επίσης τώρα που του ξαναβλέπω επιτρέπεται και το b=1

.

#5

Βάζω μια λύση:

Έστω $x_1,\ldots,x_n$ τα στοιχεία του

με

το ταυτοτικό στοιχείο. Έστω επίσης $n \times n$ πίνακας

όπου όλα τα στοιχεία του ισούνται είτε με

είτε με

με $A_{ij} = 1/|S|$ αν και μόνο αν $x_ix_j^{-1} \in S$ . Ισχύει δηλαδή ότι $A_{ij} = P(g_1 = x_ix_j^{-1})$ όπου το g_1

είναι τυχαίο στοιχείο του

. Επαγωγικά είναι $A^n_{ij} = P(g_1 \ldots g_n = x_ix_j^{-1})$ όπου τα $g_1,\ldots,g_n$ επιλέγονται ομοιόμορφα και ανεξάρτητα στην τύχη από το

. Τέλος αν γράψουμε $\mathbf{v}^T = (p_1,\ldots,p_n)$ για το διάνυσμα των πιθανοτήτων $p_i = P(g_1\ldots g_m = x_i)$ και $\mathbf{u}^T = (1,0,\ldots,0)$ τότε $\mathbf{v} = A^m \mathbf{u}$ .

Ο πίνακας

είναι συμμετρικός αφού $x_ix_j^{-1} \in S \Leftrightarrow x_jx_i^{-1} \in S$ . Οπότε έχει μια ορθοκανονική βάση ιδιοδιανυσμάτων $\mathbf{u}_1,\ldots,\mathbf{u}_n$ έστω με ιδιοτιμές $\lambda_1,\ldots,\lambda_n$ . Μπορώ να υποθέσω ότι $\mathbf{u}_1^T = \frac{1}{\sqrt{n}}(1,\ldots,1)$ και άρα $\lambda_1 = 1$ . Επιπλέον από γνωστή θεωρία είναι $|\lambda_i| \leqslant 1$ για κάθε

.

Γράφω τώρα $\mathbf{u} = \sum \alpha_i \mathbf{u}_i$ και παίρνοντας εσωτερικό γινόμενο με το $\mathbf{u}_1$ βρίσκω $\alpha_1 = 1/\sqrt{n}$ . Επιπλέον επειδή A^m u_1 = u_1

είναι

$\displaystyle{\mathbf{w} := A^m \left(\mathbf{u} - \frac{1}{\sqrt{n}}\mathbf{u}_1\right) = \mathbf{v} - \frac{1}{n}\mathbf{u}_1 = \left(p_1-\frac{1}{n},\ldots,p_n - \frac{1}{n} \right)^T}$

Οπότε μας ενδιαφέρει το $\|\mathbf{w}\|^2$ . Είναι όμως

$\displaystyle{\mathbf{w} = A^m\left( \sum_{i=2}^n \alpha_i \mathbf{u}_i\right) = \sum_{i=2}^n \alpha_i \lambda_i^m \mathbf{u}_i}$ και άρα

$\displaystyle{ \|\mathbf{w}\|^2 = \sum_{i=2}^n \alpha_i^2 \lambda_i^{2m}.}$

Παίρνοντας τώρα $b = \max\limits_{i \geqslant 2}\{|\lambda_i|^2: \alpha_i \neq 0\}$ έχουμε το ζητούμενο εκτός και αν $\alpha_i\lambda_i = 0$ για κάθε $i \geqslant 2$ . Θα δείξουμε ότι αυτό είναι αδύνατο. Πράγματι τότε θα είχαμε

$\displaystyle{ A \left(\mathbf{u} - \frac{1}{\sqrt{n}}\mathbf{u}_1\right) = A\left( \sum_{i=2}^n \alpha_i \mathbf{u}_i\right) = 0}$

που δίνει $A \mathbf{u} = (1/n,\ldots,1/n)^T$ . Το τελευταίο όμως ισχύει αν και μόνο αν η πρώτη στήλη του

έχει τιμές μόνο 1/n

κάτι που θα ίσχυε αν και μόνο αν S = G

. Αυτό όμως έχει αποκλειστεί στην εκφώνηση.

Υ.Γ. 1 Ότι το

είναι σύνολο γεννητόρων δεν χρησιμοποιήθηκε. Είχα την εντύπωση ότι με αυτό θα αποφεύγαμε και την περίπτωση b=1

. Αυτή η συνθήκη πράγματι αποφεύγει την περίπτωση $\lambda_i=1$ για κάποιο

, δεν αποφεύγει όμως την περίπτωση $\lambda_i=-1$ για κάποιο

. Αυτό θα μπορούσε να αποφευχθεί αν π.χ. η ομάδα είχε περιττή τάξη.]

Υ.Γ. 2 Η άσκηση είναι τροποποίηση του προβλήματος Α6 του Putnam του 2011. (Δείτε π.χ. εδώ.) η διαφορά είναι ότι εκεί η ομάδα είναι αβελιανή αλλά το πρόβλημα δυσκολεύει επειδή δεν υπάρχει η συνθήκη $x \in S \Rightarrow x^{-1} \in S$ που κάνει τον

συμμετρικό πίνακα. Από ότι φαίνεται και εκεί πρέπει να επιτρέψουμε την περίπτωση b=1

π.χ. για την περίπτωση $G=C_2 = \langle g \rangle$ και $S = \{g\}$

Τροποποίηση από Putnam

Τροποποίηση από Putnam

Re: Τροποποίηση από Putnam

Re: Τροποποίηση από Putnam

Re: Τροποποίηση από Putnam

Re: Τροποποίηση από Putnam

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