Math Challenge - June 2021

  • #51
julian
Gold Member
659
147
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?
 
Last edited:
  • #52
julian
Gold Member
659
147
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.
 
  • #53
218
27
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 realise 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}}##
 
  • #54
15,553
13,661
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!
 
  • #55
julian
Gold Member
659
147
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*}
 
Last edited:
  • #56
julian
Gold Member
659
147
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 cancelled 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*}
 
Last edited:
  • #57
julian
Gold Member
659
147
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
 
Last edited:
  • #58
julian
Gold Member
659
147
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*}
 
Last edited:
  • #59
julian
Gold Member
659
147
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*}
 
  • #60
15,553
13,661
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.
 
  • #61
15,553
13,661
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 cancelled 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.
 
  • #62
15,553
13,661
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.
 

Related Threads on Math Challenge - June 2021

  • Last Post
5
Replies
114
Views
3K
Replies
56
Views
3K
Replies
102
Views
3K
  • Sticky
  • Last Post
2
Replies
39
Views
871
Replies
86
Views
6K
Replies
67
Views
4K
Replies
93
Views
2K
Replies
100
Views
2K
Replies
46
Views
8K
Replies
156
Views
11K
Top