Challenge Math Challenge - June 2021

[julian]

Hey @julian, Thanks for your reply, but I still have the same question,

you said that,
\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}} \qquad (*)
\end{align*}
is correct

Hi @kshitij. I'm preoccupied at the moment so I'll just address a couple of points.

I didn't say it was correct. I was saying that this condition:

\begin{align*}
\frac{\binom{2n+2}{n+1}}{2^{2n+2}} < \frac{1}{\sqrt{2n+3}} \qquad (*)
\end{align*}

is equivalent to this condition:

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}

which follows from the fact that

\begin{align*}
\frac{\binom{2n+2}{n+1}}{2^{2n+2}} = \frac{\binom{2n+1}{n}}{2^{2n+1}}
\end{align*}

Sorry, I'm tired at the moment. You do understand that you are supposed to be proving that $(*)$ is true - yeah?

 

[julian]

Even in your solution, I cannot think how to work backwards from,
\begin{align*}

\frac{1}{2} \cdot \frac{2n+1}{n+1} < \sqrt{\frac{2n+1}{2n+3}}

\end{align*}
to get,
\begin{align*}

\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}

\end{align*}

So you were assuming that

\begin{align*}
\frac{\binom{2n}{n}}{2^{2n}} < \frac{1}{\sqrt{2n+1}} \qquad (*)
\end{align*}

holds and you wanted to show that it follows that

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}} \qquad (**)
\end{align*}

is true.

We proved that:

\begin{align*}
\frac{1}{2} \cdot \frac{2n+1}{n+1} < \sqrt{\frac{2n+1}{2n+3}}
\end{align*}

We rewrite this as

\begin{align*}
\dfrac{\frac{1}{2} \cdot \frac{2n+1}{n+1} }{ \sqrt{\frac{2n+1}{2n+3}} } < 1
\end{align*}

and use it in our assumption $(*)$ to obtain:

\begin{align*}
\dfrac{\frac{1}{2} \cdot \frac{2n+1}{n+1} }{ \sqrt{\frac{2n+1}{2n+3}} } \cdot \frac{\binom{2n}{n}}{2^{2n}} < \frac{1}{\sqrt{2n+1}}
\end{align*}

We rewrite this as:

\begin{align*}
\left( \frac{1}{2} \cdot \frac{2n+1}{n+1} \right) \cdot\frac{\binom{2n}{n}}{2^{2n}} < \sqrt{\frac{2n+1}{2n+3}} \cdot \frac{1}{\sqrt{2n+1}}
\end{align*}

which is the same as

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}

i.e. we have proven that $(**)$ holds.

 

[kshitij]

Hi @kshitij. I'm preoccupied at the moment so I'll just address a couple of points.

I didn't say it was correct. I was saying that this condition:

\begin{align*}
\frac{\binom{2n+2}{n+1}}{2^{2n+2}} < \frac{1}{\sqrt{2n+3}} \qquad (*)
\end{align*}

is equivalent to this condition:

\begin{align*}
\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}
\end{align*}

which follows from the fact that

\begin{align*}
\frac{\binom{2n+2}{n+1}}{2^{2n+2}} = \frac{\binom{2n+1}{n}}{2^{2n+1}}
\end{align*}

Sorry, I'm tired at the moment. You do understand that you are supposed to be proving that $(*)$ is true - yeah?

I did realize my mistake, thank you for your help and also for showing how to work backwards from $\frac{\binom{2n}{n}}{2^{2n}} < \frac{1}{\sqrt{2n+1}}$ to $\frac{\binom{2n+1}{n}}{2^{2n+1}} < \frac{1}{\sqrt{2n+3}}$

 

[fresh_42]

I want to explicitly say thank you to @Office_Shredder for managing this month's Challenge thread. It was a great relief to have a break while he bothered incoming answers. Thanks a lot!

 

[julian]

Problem #5:

Question (a): Let $\sigma \in \text{Aut} (S_n)$ be an automorphism of the symmetric group $S_n$ $(n \geq 4)$ such that $\sigma$ sends transpositions to transpositions, then prove that $\sigma$ is an inner automorphism.

Question (b): Determine the inner automorphism groups of (i) the symmetric groups and (ii) the alternating groups for $n \geq 4$.

Answer (a):

The transpositions $(1,k)$ are a generating set for $S_n$ for $k = 2,3, \dots , n$. We have that $\sigma (1,k) = (a_k , b_k)$ for $k = 2,3, \dots , n$, where $a_k \not= b_k$ and where $a_k, b_k \in \{ 1,2, \dots , n \}$. As $(1,2)$ and $(1,3)$ don't commute, their images $(a_2,b_2)$ and $(a_3,b_3)$ don't commute. As such their intersection $\{ a_2 , b_2 \} \cap \{ a_3 , b_3 \}$ is a single number. WOLG we assume that $a_2 = a_3 = a$.

We prove that $a \in \{ a_k , b_k \}$ for $k >3$. Assume otherwise, that is assume that for some $k > 3$ we have that $a_k \not= a \not= b_k$. As $(1,k)$ does not commute with $(1,2)$ we must have that $b_2 \in \{ a_k , b_k \}$. Similarly, $b_3 \in \{ a_k , b_k \}$ as $(1,k)$ and $(1,3)$ don't commute. Therefore, $(a_k , b_k) = (b_2 , b_3)$. But then we would have

\begin{align*}
\sigma (2,3) = \sigma ( (1,3) (1,2) (1,3)) = (a , b_3) (a , b_2) (a , b_3) = (b_2 , b_3) = \sigma (1,k)
\end{align*}

which is in contradiction with the fact that $\sigma$ is injective.

Thus the transpositions $(a_k , b_k)$ transforms the element $a$, and WLOG we can assume $a_k = a$ for all $k$. All the integers $b_k \not= a$ and are all distinct. So we have that $\sigma (1 , k) (a) = (a , b_k) (a) = b_k$, $\sigma (1 , k) (b_k) = (a , b_k) (b_k) = a$, and $\sigma (1 , k) (b_{k'}) = (a , b_k) (b_{k'}) = b_{k'}$ for $k' \not= k$.

Consider the element $\tau \in S_n$ defined by $\tau (1) = a$ and $\tau (k) = b_k$. We have

\begin{align*}
\tau (1,k) \tau^{-1} (a) & = \tau (1,k) (1)
\nonumber \\
& = \tau (k)
\nonumber \\
& = b_k
\end{align*}

and

\begin{align*}
\tau (1,k) \tau^{-1} (b_k) & = \tau (1,k) (k)
\nonumber \\
& = \tau (1)
\nonumber \\
& = a
\end{align*}

and when $k' \not= k$:

\begin{align*}
\tau (1,k) \tau^{-1} (b_{k'}) & = \tau (1,k) (k')
\nonumber \\
& = \tau (k')
\nonumber \\
& = b_{k'}
\end{align*}

Thus we have shown that $\sigma$ agrees with the inner automorphism $\tau t \tau^{-1}$ on all the generators $t = (1,k)$ of the group $S_n$ and so it is an inner automorphism of $S_n$.

QED

Answer (b) (i):

Lemma 1: Let $G$ be a group with centre $Z (G)$. Then $\text{Inn} (G) \simeq G / Z (G)$.

Proof: Let $h \in G$. An inner automorphism $\phi_h$ of $G$ is given by $\phi_h (g) = h g h^{-1}$

Define a group homomorphism:

\begin{align*}
\varphi : G \rightarrow \text{Inn} (G)
\end{align*}

by

\begin{align*}
\varphi (h) = \phi_h .
\end{align*}

$\varphi$ is clearly surjective. We identify the kernel of $\varphi$. We have that:

\begin{align*}
h \in \text{ker} \varphi & \Longleftrightarrow \phi_h (g) = g \quad \text{for all } g \in G
\nonumber \\
& \Longleftrightarrow h g h^{-1} = g \quad \text{for all } g \in G
\nonumber \\
& \Longleftrightarrow h g = g h \quad \text{for all } g \in G
\nonumber \\
& \Longleftrightarrow h \in Z (G) .
\end{align*}

We then apply the first isomorphism theorem.

QED

The centre of $S_n$ for $n \geq 4$ is the identity permutation $e$.

Proof: Suppose that $\rho$ is an arbitrary element of $S_n$ which is not the identity. Choose $i$ such that $j = \rho (i) \not= i$. Because $n \geq 4$ there is $k \not= \{ i , j \}$ and let $\tau = (j,k)$. Then:

\begin{align*}
\tau \rho \tau^{-1} (i) = \tau \rho (i) = \tau (j) = k \not= j = \rho (i)
\end{align*}

so that $\rho$ does not belong to the centre.

QED

Using this result in lemma 1 we obtain that

\begin{align*}
\text{Inn} (S_n) \simeq S_n , \qquad \text{for } n \geq 4 .
\end{align*}

Answer (b) (ii):

The centre of $A_n$ for $n \geq 4$ is the identity permutation $e$.

Proof: Suppose that $\rho$ is an arbitrary element of $A_n$ which is not the identity. Choose $i$ such that $j = \rho (i) \not= i$. Because $n \geq 4$ we can choose distinct $k$ and $l$ such that $k , l \not= \{ i , j \}$ and let $\tau = (j,k,l) = (j,l) (j,k) \in A_n$. Then:

\begin{align*}
\tau \rho \tau^{-1} (i) = \tau \rho (i) = \tau (j) = k \not= j = \rho (i)
\end{align*}

so that $\rho$ does not belong to the centre.

QED

Using this result in lemma 1 we obtain that

\begin{align*}
\text{Inn} (A_n) \simeq A_n , \qquad \text{for } n \geq 4 .
\end{align*}

 

[julian]

Problem #8:

By definition

\begin{align*}
H (p) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p -1} = \frac{a}{b} .
\end{align*}

If we can show that:

\begin{align*}
(p - 1)! \left( 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{p - 1} \right) = k p^2
\end{align*}

where $k$ is an integer then we would have

\begin{align*}
H (p) = \frac{k p^2}{(p - 1)!} .
\end{align*}

Since none of the factors in $(p - 1)!$ divide $p$ no $p$ in the numerator can be canceled out. Thus $p^2$ would divide the numerator.

In the polynomial

\begin{align*}
g (x) = (x-1)(x-2) \cdots (x - (p - 1)) = x^{p-1} + a_1 x^{p - 2} + \cdots + a_{p -2} x + a_{p - 1} \quad (*)
\end{align*}

the term $a_{p - 2}$ is given by

\begin{align*}
a_{p -2} = - (p -1)! \left( 1 + \frac{1}{2} + \cdots + \frac{1}{p - 1} \right)
\end{align*}

If we can show that $- a_{p - 2} = k p^2$ that will solve the problem.

We have $a_{p - 1} = (p - 1)!$.

Fermat's little theorem says that $a^{p - 1} \equiv 1 \; (\text{mod } p)$ for any integer $a$. It follows that modulo $p$, that $x^{p - 1} - 1$ has the roots $p - 1$ roots $1,2, \dots , p-1$. So that:

\begin{align*}
h (x) = x^{p - 1} - 1 \equiv (x-1)(x-2) \cdots (x - (p - 1)) \; (\text{mod } p) .
\end{align*}

Note that modulo $p$, $h (x)$ and $g (x)$ have the same roots.

Also, Wilson's theorem says that:

\begin{align*}
(p - 1)! \equiv -1 \; (\text{mod } p)
\end{align*}

Using all of the above in the polynomial $g (x) - h (x)$ we obtain

\begin{align*}
f (x) & = g (x) - h (x)
\nonumber \\
& = x^{p-1} + a_1 x^{p - 2} + \cdots + a_{p -2} x + a_{p - 1} - x^{p - 1} + 1
\nonumber \\
& \equiv a_1 x^{p - 2} + a_2 x^{p -3} + \cdots + a_{p -2} x \; (\text{mod } p)
\nonumber \\
& \equiv 0 .
\end{align*}

As this is a polynomial of degree $p - 2$ with the $p - 1$ solutions by Lagrange's theorem $p$ divides all the coefficients.

Putting $x = p$ in $(*)$ gives

\begin{align*}
(p-1)! = p^{p-1} + a_1 p^{p - 2} + a_2 p^{p -3} + \cdots + a_{p -2} p + a_{p - 1}
\end{align*}

Subtracting $(p - 1)!$ from both sides, dividing by $p$, and then rearranging gives

\begin{align*}
- a_{p - 2} = p^{p-2} + a_1 p^{p - 3} + \cdots + a_{p - 3} p .
\end{align*}

As we are taking $p \geq 5$, and as each of the coefficients $a_1, a_2, \dots a_{p - 3}$ is proportional to $p$ the RHS is equal to $k p^2$ where $k$ is an integer.

If $p$ were equal to 3 we couldn't say that the term $a_1 p^{p - 3}$ is proportional to $3^2$ as $a_1 p^{p - 3} = a_1$. The result clearly doesn't apply to $H (3)$:

\begin{align*}
H (3) = 1 + \frac{1}{2} + \frac{1}{3} = \frac{11}{6} .
\end{align*}

 

[julian]

This is a variation on the first proof I gave for problem #8 in the previous post. It avoids mod arithmetic and knowing theorems:

Again we solve the problem by showing that

\begin{align*}
- a_{p -2} = (p -1)! \left( 1 + \frac{1}{2} + \cdots + \frac{1}{p - 1} \right)
\end{align*}

is equal to $k p^2$ where $k$ is an integer.

First we prove that if $p$ is prime and $0 < i < p$, then $p | \binom{p}{i}$. We have

\begin{align*}
\binom{p}{i} = \frac{p}{i!} (p - 1) (p - 2) \cdots (p - i + 1)
\end{align*}

As none of the factors in $i!$ can divide $p$ the $p$ cannot be cancelled. Hence $p$ divides $\binom{p}{i}$.

Consider the polynomial

\begin{align*}
f (x) = (x +1) (x + 2) \cdots (x + p - 1) = x^{p - 1} - a_1 x^{p - 2} + a_2 x^{p - 3} - \cdots - a_{p - 2} x + a_{p - 1}
\end{align*}

where the $a_i$'s are the same as before. We will prove that the coefficients $a_1, \dots , a_{p - 2}$ are all divisible by $p$ when $p$ is an odd prime.

Proof: Note that

\begin{align*}
f (x + 1) = (x +2) (x + 3) \cdots (x + p)
\end{align*}

and so

\begin{align*}
(x + 1) f (x + 1) = f (x) (x + p)
\end{align*}

implying

\begin{align*}
p f (x) = (x + 1) f (x) - x f(x) .
\end{align*}

Hence,

\begin{align*}
& p x^{p - 1} - p a_1x^{p - 2} + p a_2 x^{p - 3} - \cdots - p a_{p - 2} x + p!
\nonumber \\
& = [(x + 1)^p - x^p] - a_1 [(x + 1)^{p - 1} - x^{p - 1}] + a_2 [(x + 1)^{p - 2} - x^{p - 2}] - \cdots -
\nonumber \\
& - a_{p - 2} [(x + 1)^2 - x^2] + [(x + 1) - x](p - 1)!
\nonumber \\
& = x^{p - 1} \binom{p}{1} + x^{p - 2} \binom{p}{2} + x^{p - 3} \binom{p}{3} + \cdots + \binom{p}{p - 1} x + 1
\nonumber \\
& + (-a_1) \left[ x^{p - 2} \binom{p - 1}{1} + x^{p - 3} \binom{p - 1}{2} + \cdots + \binom{p - 1}{p - 2} x + 1 \right]
\nonumber \\
& + a_2 \left[ x^{p - 3} \binom{p - 2}{1} + x^{p - 4} \binom{p - 2}{2} + \cdots + \binom{p - 2}{p - 3} x + 1 \right]
\nonumber \\
& \vdots
\nonumber \\
& +(-a_{p - 2}) \left[ x \binom{2}{1} + 1 \right]
\nonumber \\
& + (p - 1)!
\end{align*}

By equating coefficients if of $x^{p - 2} , x^{p - 3} , \cdots , x$ we obtain:

\begin{align*}
p (- a_1) & = \binom{p}{2} + \binom{p - 1}{1} (-a_1)
\nonumber \\
p a_2 & = \binom{p}{3} + \binom{p - 1}{2} (-a_1) + \binom{p - 2}{1} a_2
\nonumber \\
& \vdots
\nonumber \\
p (-a_{p-2}) &= \binom{p}{p - 1} + \binom{p - 1}{p - 2} (-a_1) + \cdots + \binom{2}{1} (-a_{p - 2}) .
\end{align*}

From the first equation, using that $p | \binom{p}{2}$, we have that $p | (-a_1)$. Using this in the second equation together with $p | \binom{p}{3}$, we have that $p | a_2$. And so on. So we have $p | (-a_1) , a_2 , \cdots , (-a_{p - 2})$.

QED

Putting $x = p$ into

\begin{align*}
(x-1)(x-2) \cdots (x - (p - 1)) = x^{p-1} + a_1 x^{p - 2} + \cdots + a_{p -2} x + (p - 1)!
\end{align*}

then rearranging gives

\begin{align*}
- a_{p - 2} = p^{p-2} + a_1 p^{p - 3} + \cdots + a_{p - 3} p .
\end{align*}

As we are taking $p \geq 5$, and as each of the coefficients $a_1, a_2, \dots a_{p - 3}$ is proportional to $p$ the RHS is equal to $k p^2$ where $k$ is an integer. Solving problem #8.

QED

 

[julian]

Problem #6:

By definition

\begin{align*}
d = \min_{(x,y) \in C^2 , x \not= y} d (x,y)
\end{align*}

where $d(x,y)$ be the Hamming distance of $x$ and $y$. A bound is proved by bounding the quantity

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y)
\end{align*}

in two different ways. On the one hand, there are $\# C$ choices for $x$ and for each such choice, there are $\# C - 1$ choices for $y$. Since by definition $d (x,y) \geq d$ for all $x$ and $y$ ($x \not= y$), it follows that

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y) \geq \# C (\# C - 1) d .
\end{align*}

The other inequality is obtained by writing down all the $\# C$ codewords of $C$ into a $\# C \times n$-matrix. Let $n_{i , \alpha}$ denote the number of times the element $\alpha$ of the alphabet (with $q$ elements) occurs in the $i$th column. For each choice of $\alpha$ in the $i$th column there are $\# C - n_{i , \alpha}$ elements not equal to $\alpha$ in the same column. Then

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y) & = \sum_{i = 1}^n \sum_{\alpha} n_{i , \alpha} (\# C - n_{i , \alpha})
\nonumber \\
& = \sum_{i = 1}^n \left( (\# C)^2 - \sum_\alpha n_{i , \alpha}^2 \right) \qquad ( \sum_{\alpha} n_{i , \alpha} = \# C)
\nonumber \\
& \leq \sum_{i = 1}^n \left( (\# C)^2 - \frac{(\# C)^2}{q} \right) \qquad ( (\# C)^2 = (\sum_{\alpha} n_{i , \alpha} \cdot 1)^2 \leq (\sum_{\alpha} n_{i , \alpha}^2) (\sum_{\alpha} 1^2) )
\nonumber \\
&= n \cdot (\# C)^2 \cdot \left( 1 - \frac{1}{q} \right) .
\end{align*}

Combining the two bounds gives

\begin{align*}
\# C (\# C - 1) d \leq (\# C)^2 \cdot n \cdot \left( \frac{q - 1}{q} \right)
\end{align*}

or

\begin{align*}
d (\# C - 1) \leq \# C \cdot n \cdot \left( \frac{q - 1}{q} \right) \qquad (*)
\end{align*}

If $d < n \cdot \dfrac{q - 1}{q}$ the bound $(*)$ can be rearranged as

\begin{align*}
\# C \leq \frac{d}{d - n \cdot \dfrac{q - 1}{q}} .
\end{align*}

 

[julian]

Problem #7:

We start with a reminder of the definition of the Cantor dust. Define $C_1$ as:

\begin{align*}
C_1 & = [0,1] - ( \frac{1}{3} , \frac{2}{3})
\nonumber \\
& = [0 , \frac{1}{3}] \cup [\frac{2}{3} , 1]
\end{align*}

Take the two intervals and split them into thirds. Then remove each of their open middle thirds to get

\begin{align*}
C_2 = [0 , \frac{1}{9}] \cup [\frac{2}{9} , \frac{1}{3}] \cup [\frac{2}{3} , \frac{7}{9}] \cup [\frac{8}{9} ,1]
\end{align*}

To get the next set $C_3$, split each of the four intervals of $C_2$ into three equal parts and remove their open middle thirds. Continue this way for each $k$. The Cantor dust is the intersection of all these $C_k$:

\begin{align*}
\text{Cantor dust} = C = \cap_{k = 1}^\infty C_k .
\end{align*}

To prove it is uncountable, first we express any number $x$ in the unit interval $[0,1]$ in its tri-adic expansion

\begin{align*}
x = \sum_{k = 1}^\infty \frac{n_k}{3^k} .
\end{align*}

where $n_k$ takes the values zero, one or two. We can write the tri-adic expansion in base three notation, to obtain

\begin{align*}
x = . n_1 n_2 n_3 \dots
\end{align*}

As with the decimal expansion, the base three expansion's coefficients $n_k$ are unique, provided we always round up. Thus we will say that

\begin{align*}
.102222 \dots = .110000 \dots
\end{align*}

for example (the case $.2222 \dots$ we leave as it is).

In terms of the base three expansion

\begin{align*}
C = \{ . n_1 n_2 n_3 \dots : \text{where } n_k \text{ is equal to either zero or two} \}
\end{align*}

We prove that the Cantor dust is uncountable by contradiction. We assume there is a bijective map $\phi : \mathbb{N} \rightarrow C$ and then prove that there is a number in $C$ that not in the image of $\phi$, contradicting that $\phi$ is surjective.

Let us list the images of our assumed bijection $\phi : \mathbb{N} \rightarrow C$:

\begin{align*}
\phi (1) & = . a_1 a_2 a_3 \dots
\nonumber \\
\phi (2) & = . b_1 b_2 b_3 \dots
\nonumber \\
\phi (3) & = . c_1 c_2 c_3 \dots
\nonumber \\
\phi (4) & = . d_1 d_2 d_3 \dots
\nonumber \\
& \;\; \vdots
\end{align*}

Note that the $a_i, b_j$, etc are now fixed numbers that are either $0$ or $2$, given to us by the assumed bijection. We will construct a new number $.n'_1 n'_2 n'_3 \dots$ that cannot appear in the above list, thereby contradicting the assumption that $\phi$ is surjective. Set

\begin{align*}
n'_k = \left\{
\begin{matrix}
0, & \text{if the } kth \text{ entry of } \phi (k) \not= 0
\nonumber \\
2, & \text{if the } kth \text{ entry of } \phi (k) = 0
\end{matrix}
\right.
\end{align*}

Note that $n'_1$ is $0$ if $a_1 = 2$ and is $2$ if $a_1 = 0$. Thus

\begin{align*}
.n'_1 n'_2 n'_3 \dots \not= . a_1 a_2 a_3 \dots = \phi (1) .
\end{align*}

Likewise, $n'_2$ is $0$ if $b_2 = 2$ and is $2$ if $b_2 = 0$ and so

\begin{align*}
.n'_1 n'_2 n'_3 \dots \not= . b_1 b_2 b_3 \dots = \phi (2) .
\end{align*}

And so on indefinitely. Since the base three expansions are unique, and since each $n'_k$ is defined so that it is not equal to the $kth$ term in $\phi (k)$, we must have that $.n'_1 n'_2 n'_3 \dots$ is not equal to any $\phi (k)$, meaning that $\phi$ cannot be surjective.

With Cantor dust, the portion of the object corresponding to the initial one-third of the original segment is an exact replica of the complete object, but at 1/3rd its scale. Note, moreover, that you need 2 copies of the scaled-down object to cover the object at full-scale. Hence, the Hausdorff–Besicovitch dimension is

\begin{align*}
d = \frac{\ln 2}{\ln 3} = 0.630923 \dots
\end{align*}

 

[fresh_42]

Problem #5:

Question (a): Let $\sigma \in \text{Aut} (S_n)$ be an automorphism of the symmetric group $S_n$ $(n \geq 4)$ such that $\sigma$ sends transpositions to transpositions, then prove that $\sigma$ is an inner automorphism.

Question (b): Determine the inner automorphism groups of (i) the symmetric groups and (ii) the alternating groups for $n \geq 4$.

Answer (a):

The transpositions $(1,k)$ are a generating set for $S_n$ for $k = 2,3, \dots , n$. We have that $\sigma (1,k) = (a_k , b_k)$ for $k = 2,3, \dots , n$, where $a_k \not= b_k$ and where $a_k, b_k \in \{ 1,2, \dots , n \}$. As $(1,2)$ and $(1,3)$ don't commute, their images $(a_2,b_2)$ and $(a_3,b_3)$ don't commute. As such their intersection $\{ a_2 , b_2 \} \cap \{ a_3 , b_3 \}$ is a single number. WOLG we assume that $a_2 = a_3 = a$.

We prove that $a \in \{ a_k , b_k \}$ for $k >3$. Assume otherwise, that is assume that for some $k > 3$ we have that $a_k \not= a \not= b_k$. As $(1,k)$ does not commute with $(1,2)$ we must have that $b_2 \in \{ a_k , b_k \}$. Similarly, $b_3 \in \{ a_k , b_k \}$ as $(1,k)$ and $(1,3)$ don't commute. Therefore, $(a_k , b_k) = (b_2 , b_3)$. But then we would have

\begin{align*}
\sigma (2,3) = \sigma ( (1,3) (1,2) (1,3)) = (a , b_3) (a , b_2) (a , b_3) = (b_2 , b_3) = \sigma (1,k)
\end{align*}

which is in contradiction with the fact that $\sigma$ is injective.

Thus the transpositions $(a_k , b_k)$ transforms the element $a$, and WLOG we can assume $a_k = a$ for all $k$. All the integers $b_k \not= a$ and are all distinct. So we have that $\sigma (1 , k) (a) = (a , b_k) (a) = b_k$, $\sigma (1 , k) (b_k) = (a , b_k) (b_k) = a$, and $\sigma (1 , k) (b_{k'}) = (a , b_k) (b_{k'}) = b_{k'}$ for $k' \not= k$.

Consider the element $\tau \in S_n$ defined by $\tau (1) = a$ and $\tau (k) = b_k$. We have

\begin{align*}
\tau (1,k) \tau^{-1} (a) & = \tau (1,k) (1)
\nonumber \\
& = \tau (k)
\nonumber \\
& = b_k
\end{align*}

and

\begin{align*}
\tau (1,k) \tau^{-1} (b_k) & = \tau (1,k) (k)
\nonumber \\
& = \tau (1)
\nonumber \\
& = a
\end{align*}

and when $k' \not= k$:

\begin{align*}
\tau (1,k) \tau^{-1} (b_{k'}) & = \tau (1,k) (k')
\nonumber \\
& = \tau (k')
\nonumber \\
& = b_{k'}
\end{align*}

Thus we have shown that $\sigma$ agrees with the inner automorphism $\tau t \tau^{-1}$ on all the generators $t = (1,k)$ of the group $S_n$ and so it is an inner automorphism of $S_n$.

QED

Answer (b) (i):

Lemma 1: Let $G$ be a group with centre $Z (G)$. Then $\text{Inn} (G) \simeq G / Z (G)$.

Proof: Let $h \in G$. An inner automorphism $\phi_h$ of $G$ is given by $\phi_h (g) = h g h^{-1}$

Define a group homomorphism:

\begin{align*}
\varphi : G \rightarrow \text{Inn} (G)
\end{align*}

by

\begin{align*}
\varphi (h) = \phi_h .
\end{align*}

$\varphi$ is clearly surjective. We identify the kernel of $\varphi$. We have that:

\begin{align*}
h \in \text{ker} \varphi & \Longleftrightarrow \phi_h (g) = g \quad \text{for all } g \in G
\nonumber \\
& \Longleftrightarrow h g h^{-1} = g \quad \text{for all } g \in G
\nonumber \\
& \Longleftrightarrow h g = g h \quad \text{for all } g \in G
\nonumber \\
& \Longleftrightarrow h \in Z (G) .
\end{align*}

We then apply the first isomorphism theorem.

QED

The centre of $S_n$ for $n \geq 4$ is the identity permutation $e$.

Proof: Suppose that $\rho$ is an arbitrary element of $S_n$ which is not the identity. Choose $i$ such that $j = \rho (i) \not= i$. Because $n \geq 4$ there is $k \not= \{ i , j \}$ and let $\tau = (j,k)$. Then:

\begin{align*}
\tau \rho \tau^{-1} (i) = \tau \rho (i) = \tau (j) = k \not= j = \rho (i)
\end{align*}

so that $\rho$ does not belong to the centre.

QED

Using this result in lemma 1 we obtain that

\begin{align*}
\text{Inn} (S_n) \simeq S_n , \qquad \text{for } n \geq 4 .
\end{align*}

Answer (b) (ii):

The centre of $A_n$ for $n \geq 4$ is the identity permutation $e$.

Proof: Suppose that $\rho$ is an arbitrary element of $A_n$ which is not the identity. Choose $i$ such that $j = \rho (i) \not= i$. Because $n \geq 4$ we can choose distinct $k$ and $l$ such that $k , l \not= \{ i , j \}$ and let $\tau = (j,k,l) = (j,l) (j,k) \in A_n$. Then:

\begin{align*}
\tau \rho \tau^{-1} (i) = \tau \rho (i) = \tau (j) = k \not= j = \rho (i)
\end{align*}

so that $\rho$ does not belong to the centre.

QED

Using this result in lemma 1 we obtain that

\begin{align*}
\text{Inn} (A_n) \simeq A_n , \qquad \text{for } n \geq 4 .
\end{align*}

Right. You could have saved some time in the second part by observing that $A_n$ are simple for $n>4$ and $S_n\cong A_n \rtimes \mathbb{Z}_2$ which have no center. For $n=4$ the Klein four-group adds to the candidates for a center, but $V_4$ isn't Abelian.

 

[fresh_42]

Problem #8:

By definition

\begin{align*}
H (p) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p -1} = \frac{a}{b} .
\end{align*}

If we can show that:

\begin{align*}
(p - 1)! \left( 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{p - 1} \right) = k p^2
\end{align*}

where $k$ is an integer then we would have

\begin{align*}
H (p) = \frac{k p^2}{(p - 1)!} .
\end{align*}

Since none of the factors in $(p - 1)!$ divide $p$ no $p$ in the numerator can be canceled out. Thus $p^2$ would divide the numerator.

In the polynomial

\begin{align*}
g (x) = (x-1)(x-2) \cdots (x - (p - 1)) = x^{p-1} + a_1 x^{p - 2} + \cdots + a_{p -2} x + a_{p - 1} \quad (*)
\end{align*}

the term $a_{p - 2}$ is given by

\begin{align*}
a_{p -2} = - (p -1)! \left( 1 + \frac{1}{2} + \cdots + \frac{1}{p - 1} \right)
\end{align*}

If we can show that $- a_{p - 2} = k p^2$ that will solve the problem.

We have $a_{p - 1} = (p - 1)!$.

Fermat's little theorem says that $a^{p - 1} \equiv 1 \; (\text{mod } p)$ for any integer $a$. It follows that modulo $p$, that $x^{p - 1} - 1$ has the roots $p - 1$ roots $1,2, \dots , p-1$. So that:

\begin{align*}
h (x) = x^{p - 1} - 1 \equiv (x-1)(x-2) \cdots (x - (p - 1)) \; (\text{mod } p) .
\end{align*}

Note that modulo $p$, $h (x)$ and $g (x)$ have the same roots.

Also, Wilson's theorem says that:

\begin{align*}
(p - 1)! \equiv -1 \; (\text{mod } p)
\end{align*}

Using all of the above in the polynomial $g (x) - h (x)$ we obtain

\begin{align*}
f (x) & = g (x) - h (x)
\nonumber \\
& = x^{p-1} + a_1 x^{p - 2} + \cdots + a_{p -2} x + a_{p - 1} - x^{p - 1} + 1
\nonumber \\
& \equiv a_1 x^{p - 2} + a_2 x^{p -3} + \cdots + a_{p -2} x \; (\text{mod } p)
\nonumber \\
& \equiv 0 .
\end{align*}

As this is a polynomial of degree $p - 2$ with the $p - 1$ solutions by Lagrange's theorem $p$ divides all the coefficients.

Putting $x = p$ in $(*)$ gives

\begin{align*}
(p-1)! = p^{p-1} + a_1 p^{p - 2} + a_2 p^{p -3} + \cdots + a_{p -2} p + a_{p - 1}
\end{align*}

Subtracting $(p - 1)!$ from both sides, dividing by $p$, and then rearranging gives

\begin{align*}
- a_{p - 2} = p^{p-2} + a_1 p^{p - 3} + \cdots + a_{p - 3} p .
\end{align*}

As we are taking $p \geq 5$, and as each of the coefficients $a_1, a_2, \dots a_{p - 3}$ is proportional to $p$ the RHS is equal to $k p^2$ where $k$ is an integer.

If $p$ were equal to 3 we couldn't say that the term $a_1 p^{p - 3}$ is proportional to $3^2$ as $a_1 p^{p - 3} = a_1$. The result clearly doesn't apply to $H (3)$:

\begin{align*}
H (3) = 1 + \frac{1}{2} + \frac{1}{3} = \frac{11}{6} .
\end{align*}

Right. The result is known as the Theorem of Wolstenholme.

 

[fresh_42]

Problem #6:

By definition

\begin{align*}
d = \min_{(x,y) \in C^2 , x \not= y} d (x,y)
\end{align*}

where $d(x,y)$ be the Hamming distance of $x$ and $y$. A bound is proved by bounding the quantity

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y)
\end{align*}

in two different ways. On the one hand, there are $\# C$ choices for $x$ and for each such choice, there are $\# C - 1$ choices for $y$. Since by definition $d (x,y) \geq d$ for all $x$ and $y$ ($x \not= y$), it follows that

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y) \geq \# C (\# C - 1) d .
\end{align*}

The other inequality is obtained by writing down all the $\# C$ codewords of $C$ into a $\# C \times n$-matrix. Let $n_{i , \alpha}$ denote the number of times the element $\alpha$ of the alphabet (with $q$ elements) occurs in the $i$th column. For each choice of $\alpha$ in the $i$th column there are $\# C - n_{i , \alpha}$ elements not equal to $\alpha$ in the same column. Then

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y) & = \sum_{i = 1}^n \sum_{\alpha} n_{i , \alpha} (\# C - n_{i , \alpha})
\nonumber \\
& = \sum_{i = 1}^n \left( (\# C)^2 - \sum_\alpha n_{i , \alpha}^2 \right) \qquad ( \sum_{\alpha} n_{i , \alpha} = \# C)
\nonumber \\
& \leq \sum_{i = 1}^n \left( (\# C)^2 - \frac{(\# C)^2}{q} \right) \qquad ( (\# C)^2 = (\sum_{\alpha} n_{i , \alpha} \cdot 1)^2 \leq (\sum_{\alpha} n_{i , \alpha}^2) (\sum_{\alpha} 1^2) )
\nonumber \\
&= n \cdot (\# C)^2 \cdot \left( 1 - \frac{1}{q} \right) .
\end{align*}

Combining the two bounds gives

\begin{align*}
\# C (\# C - 1) d \leq (\# C)^2 \cdot n \cdot \left( \frac{q - 1}{q} \right)
\end{align*}

or

\begin{align*}
d (\# C - 1) \leq \# C \cdot n \cdot \left( \frac{q - 1}{q} \right) \qquad (*)
\end{align*}

If $d < n \cdot \dfrac{q - 1}{q}$ the bound $(*)$ can be rearranged as

\begin{align*}
\# C \leq \frac{d}{d - n \cdot \dfrac{q - 1}{q}} .
\end{align*}

The bound is called Plotkin bound.