Challenge Math Challenge - September 2021

[fresh_42]

1. If $G$ is a topological group then, $inv(g) = (e,g) \longmapsto eg^{-1} = g^{-1}$ is continuous. Also, $(g, inv(h)) \longmapsto gh$ is continuous, since it is the composition of continuous maps. The other direction is trivial because $gh^{-1}$ is again the composition of continuous maps and hence gives the required continuous map for a topological group.

2. The kernel of both maps is empty since group operations are invertible. We can exhibit an inverses $x \longmapsto xg^{-1}$ and $x \longmapsto g^{-1}x$ respectively.

Kernel is an unlucky term in this context. The idea can be summarized by $\mu^{-1}_{g}=\mu_{g^{-1}}$ with $\mu_g(x)=xg.$

 

[jbergman]

5. A group $G$ together with a topology, such that the mapping on $G\times G$ (equipped with the product topology) to $G$ given by $(x,y)\longmapsto xy^{-1}$ is continuous, is called a topological group (e.g. a Lie group). Prove

1. (solved by @jbergman ) $G$ is a topological group if and only if inversion and multiplication are continuous.
2. (solved by @jbergman ) The mappings $x\longmapsto xg$ and $x\longmapsto gx$ are homeomorphisms for each $g\in G.$
3. Each open subgroup $U\leq G$ is closed, and each closed subgroup $U\leq G$ of finite index is open. If $G$ is compact, then each open subgroup is of finite index.
4. Let $H \leq G$ be a subgroup equipped with the subspace topology, $K\trianglelefteq G$ a normal subgroup, and $G/K$ equipped with the quotient space topology. Then $H$ and $G/K$ are again topological groups and the projection $\pi\, : \,G \twoheadrightarrow G/K$ is open.
5. $G$ is Hausdorff if and only if $\{1\}$ is a closed set in $G.$ $G/K$ is Hausdorff for a normal subgroup $K\trianglelefteq G,$ if and only if $K$ is closed in $G.$ If $G$ is totally disconnected, then $G$ is Hausdorff.
6. Let $G$ be a compact topological group and $\{X_j \;(j\in I)\}\subseteq G$ a family of closed subsets such that for all $i ,j\in I$ there is a $k\in I$ with $X_k\subseteq X_i\cap X_j.$ Then we have for any closed subset $Y\subseteq G$
   $$Y\cdot \left(\bigcap_{i\in I}X_i\right) = \bigcap_{i\in I} YX_i $$

Moving on to the first part 5.3

If $U$ is an open subgroup in $G$ and $c$ is a limit point of $U$, then the function $f(g) = gc^{-1}$ is a homeomorphism as we showed in 5.2, that also maps $c$ to $e$.

Since $c$ is a limit point of $U$, every open set containing $c$, contains points in $U$.

Now if we take an open set of the identity $V$, then $f^{-1}(V)$ is an open set containing $c$ and points in $U$.

Since $U$ also contains the identity we can take the intersection of an open set in $U$ containing the identity and $V$, call it $W$

However, that means that $hc^{-1}\in U$ for some point $h \in W$ which implies that $U$ contains all of its limit points and is closed, because $h^{-1}$ inverse is also in $U$ which shows that $c^{-1}$ is in $U$ hence $c$ is in $U$.

 

[fresh_42]

Moving on to the first part 5.3

If $U$ is an open subgroup in $G$ and $c$ is a limit point of $U$, then the function $f(g) = gc^{-1}$ is a homeomorphism as we showed in 5.2, that also maps $c$ to $e$.

Since $c$ is a limit point of $U$, every open set containing $c$, contains points in $U$.

Now if we take an open set of the identity $V$, then $f^{-1}(V)$ is an open set containing $c$ and points in $U$.

Since $U$ also contains the identity we can take the intersection of an open set in $U$ containing the identity and $V$, call it $W$

However, that means that $hc^{-1}\in U$ for some point $h \in W$ which implies that $U$ contains all of its limit points and is closed, because $h^{-1}$ inverse is also in $U$ which shows that $c^{-1}$ is in $U$ hence $c$ is in $U$.

A bit complicated.

A shorter version is:
Let $U\leq G$ be an open subgroup, and $g\in G-U.$ Then $gU\subseteq G-U$ is open because left multiplication is a homeomorphism, and
$$
G-U = \bigcup_{g\in G-U}g = \bigcup_{g\in G-U}gU
$$
is a union of open sets, i.e. open, i.e. $U$ is closed.

I will wait for the other parts.

 

[jbergman]

Continuing 5.3.

If $U$ is closed then each coset is also closed, again because left multiplication is a homeomorphism.

Since $U$ has finite index, $G$ is the union of $U$'s cosets. Also, cosets are disjoint, so the complement of any individual coset $gU$ is $G\backslash gU$. But $G\backslash gU$ is just the union of the other cosets which implies it is closed and it's complement must be open, hence $gU$ must be open since it equals the complement.

Still thinking about the compact case.

 

[fresh_42]

Continuing 5.3.

If $U$ is closed then each coset is also closed, again because left multiplication is a homeomorphism.

Since $U$ has finite index, $G$ is the union of

finitely many

$U$'s cosets. Also, cosets are disjoint, so the complement of any individual coset $gU$ is $G\backslash gU$. But $G\backslash gU$ is just the union of the

finitely many

other cosets which implies it is closed and it's complement must be open, hence $gU$ must be open since it equals the complement.

Still thinking about the compact case.

Well, compact means finite subcover, finite index means finitely many cosets of the open subgroup. Now combine these. The finite index is crucial. In formulas it is

Let $A\leq G$ be a closed subgroup of finite index. Then
$$
G-A = \bigcup_{g\in G-A}g = \bigcup_{g\in G-A}gA = \bigcup_{g=1}^n gA
$$
is a finite union of closed sets, hence $G-A$ is closed and $A$ is open.

 

[jbergman]

Thanks, I had the finite in there earlier, but dropped them in my edits.

 

[jbergman]

finitely many
finitely many
Well, compact means finite subcover, finite index means finitely many cosets of the open subgroup. Now combine these. The finite index is crucial. In formulas it is

Let $A\leq G$ be a closed subgroup of finite index. Then
$$
G-A = \bigcup_{g\in G-A}g = \bigcup_{g\in G-A}gA = \bigcup_{g=1}^n gA
$$
is a finite union of closed sets, hence $G-A$ is closed and $A$ is open.

Thanks for the hint. Let $A\leq G$ be an open subgroup of the compact space $G$.

Assume $A$ is not of finite index. Then the cosets of $A$ are again open because left multiplication is a homeomorphism and
$$
G = \bigcup_{g\in G} gA
$$
But since the cosets, $gA$ are distinct and open, they form an open cover of $G$ of which there is no finite subcover which is a contradiction. Hence $A$ must be of finite index.

 

[fresh_42]

Thanks for the hint. Let $A\leq G$ be an open subgroup of the compact space $G$.

Assume $A$ is not of finite index. Then the cosets of $A$ are again open because left multiplication is a homeomorphism and
$$
G = \bigcup_{g\in G} gA
$$
But since the cosets, $gA$ are distinct and open, they form an open cover of $G$ of which there is no finite subcover which is a controduction. Hence $A$ must be of finite index.

Right. Just two remarks. You can write this without contradiction. Simply consider all $gA$. They are an open cover. Therefore, there is a finite subcover. Since all cosets are disjoint, the cosets in the subcover all possible cosets, i.e. finite index. I'm not 100% sure whether this convention is the same in English literature. Here we use $U,V$ or even sometimes $O$ for the open sets, and $A,B$ for the closed ones. Of course this doesn't change anything, but it is easier to read.

 

[jbergman]

Right. Just two remarks. You can write this without contradiction. Simply consider all $gA$. They are an open cover. Therefore, there is a finite subcover. Since all cosets are disjoint, the cosets in the subcover all possible cosets, i.e. finite index. I'm not 100% sure whether this convention is the same in English literature. Here we use $U,V$ or even sometimes $O$ for the open sets, and $A,B$ for the closed ones. Of course this doesn't change anything, but it is easier to read.

Yes, in most of the books I have see $U,V$ for open sets. I am less familiar with the notation for closed sets.

 

[jbergman]

Yes, in most of the books I have see $U,V$ for open sets. I am less familiar with the notation for closed sets.

BTW, you have some nice insight articles! I am going to have to look through them. I've want to get a handle on representation theory.

 

[fresh_42]

Yes, in most of the books I have see $U,V$ for open sets. I am less familiar with the notation for closed sets.

My suspicion is that it has historical reasons. Topology was first developed and researched by Russian and German mathematicians. One could even say that Cantor and Dedekind kind of started the field:
https://www.physicsforums.com/threa...for-the-particular-names.962018/#post-6102165

A neighborhood is usually open, and Umgebung is the German word for neighborhood. Closed is abgeschlossen in German. I guess the abbreviations $U$ and $A$ came in handy for a quick distinction.

 

[jbergman]

My suspicion is that it has historical reasons. Topology was first developed and researched by Russian and German mathematicians. One could even say that Cantor and Dedekind kind of started the field:
https://www.physicsforums.com/threa...for-the-particular-names.962018/#post-6102165

A neighborhood is usually open, and Umgebung is the German word for neighborhood. Closed is abgeschlossen in German. I guess the abbreviations $U$ and $A$ came in handy for a quick distinction.

What is the meaning of $\trianglelefteq$ in 5.4?

 

[fresh_42]

What is the meaning of $\trianglelefteq$ in 5.4?

$K\trianglelefteq G$ means that $K$ is a normal subgroup of $G,$ i.e. $gKg^{-1}\subseteq K$ for all $g\in G.$ Normality is crucial, because it makes
$$
\varphi \, : \,G/K \times G/K \longrightarrow G/K\, , \,\varphi (gK,hK)=gh^{-1}K
$$
a well-defined function.

Hint: You could start with an open set $\overline{V} \subseteq G/K$.

 

[jbergman]

$H$ is obviously a topological group because restriction of a continuous map to a subset with the subspace topology is continuous.

Let $m$ and $m'$ represent the multiplication maps on $G$ and $G/K$ respectively.

Then,

$$\pi(m(g, h))=m'(\pi(g),\pi(h))$$

Sine the left is the composition of continuous maps, the right is continuous. $\pi$ is surjective onto $G/K$. Therefore $m'$ must be continuous, because if $m'^{-1}(U)$ mapped into a closed set in $G/K\times G/K$, $\pi^{-1}\times\pi^{-1}$ would also map to a closed subset since $G/K$ has the quotient topology.

Still thinking about how to show that $\pi$ is open. It must have something to do with the interplay of $H$. But, I'm not quite clear on how subgroups and a normal group interact.

 

[Not anonymous]

11. Let $S$ be a set of real numbers that is closed under multiplication (that is, if $a$ and $b$ are in $S$, then so is $ab$). Let $T$ and $U$ be disjoint subsets of whose union is $S$. Given that the product of any three (not necessarily distinct) elements of $T$ is in $T$ and that the product of any three elements of $U$ is in $U$, show that at least one of the two subsets $T, U$ is closed under multiplication.

Spoiler: Question 11

Proof by contradiction: Suppose neither of $T, U$ is closed under multiplication. Then there must exist $t_1, t_2 \in T$ (not necessarily distinct) such that $x \equiv t_1 t_2 \notin T \Rightarrow x \in U$ (since $T \cup U = S$ and $x \in S$) and similarly there must exist $u_1, u_2 \in U$ such that $y \equiv u_1 u_2 \notin U \Rightarrow y \in T$. Now consider the product $xy$.

Since $xy = t_1 t_2 y$ and $t_1, t_2, y \in T$ and it is given that product of any three elements of $T$ is in $T$, we must have $xy \in T$. (1)

But the product $xy$ is also expressible as $xy = x u_1 u_2$. Since $x, u_1, u_2 \in U$ and it is given that product of any three elements of $U$ is in $U$, we must have $xy \in U$. (2)

Conditions (1) and (2) are contradictory since $T$ and $U$ are disjoint subsets and hence $xy$ cannot belong to both the sets. The contradiction arises due to the assumption neither $T$ nor $U$ is closed under multiplication. Hence it must be the case that at least one of $T, U$ is closed under multiplication.

Addendum: While at least one of $T, U$ will be closed under multiplication given the conditions stated in the question, it is not always necessary that both will be closed under multiplication. For example, if $S$ is the set of all integers, $T$ is the set of all negative integers and $U$ is the set of all non-negative integers, then both $T, U$ meet the condition that the product of any three elements from the set is also in the same set, but only $U$ and not $T$ is closed under multiplication.

 

[fresh_42]

$H$ is obviously a topological group because restriction of a continuous map to a subset with the subspace topology is continuous.

Let $m$ and $m'$ represent the multiplication maps on $G$ and $G/K$ respectively.

Then,

$$\pi(m(g, h))=m'(\pi(g),\pi(h))$$

Sine the left is the composition of continuous maps,

Why is $\pi$ continuous? It is an algebraic function, not a topological.

the right is continuous. $\pi$ is surjective onto $G/K$. Therefore $m'$ must be continuous, because if $m'^{-1}(U)$ mapped into a closed set in $G/K\times G/K$, $\pi^{-1}\times\pi^{-1}$ would also map to a closed subset since $G/K$ has the quotient topology.

What is $U$? And closed is not the opposite of open!

Still thinking about how to show that $\pi$ is open. It must have something to do with the interplay of $H$. But, I'm not quite clear on how subgroups and a normal group interact.

 

[jbergman]

Why is $\pi$ continuous? It is an algebraic function, not a topological.

A quotient topology requires a surjective map from $f: X \mapsto Y$. Then the open sets $U \in Y$ are the sets such that $f^{-1}(U)$ is open in $X$. In our case $\pi$ is the map used to define the quotient topology on $G/K$.

What is $U$? And closed is not the opposite of open!

$U$ is in an open set in $G/K$.

 

[fresh_42]

A quotient topology requires a surjective map from $f: X \mapsto Y$. Then the open sets $U \in Y$ are the sets such that $f^{-1}(U)$ is open in $X$. In our case $\pi$ is the map used to define the quotient topology on $G/K$.

$U$ is in an open set in $G/K$.

Ok, right so far. Now simply "calculate" what $\pi (U)$ is and use the fact that arbitrary unions of open sets are open. You do not need something closed.

 

[jbergman]

Ok, right so far. Now simply "calculate" what $\pi (U)$ is and use the fact that arbitrary unions of open sets are open. You do not need something closed.

Can't I just replace closed with not open in my argument?

To restate, my argument is the following.

We know that
$m'(\pi(g), \pi(h))$ is continuous from my argument above, where $m' : G/K \times G/K \mapsto G/K$

For an open set $U \in G/K$, $m'^{-1}(U)$ maps to a set $X \times Y \in G/K \times G/K$.

If $X$ or $Y$ is not open, then $\pi^{-1}(X)$ or $\pi^{-1}(Y)$ because of the definition of the quotient topology. But we know that, $\pi^{-1}(X) \times \pi^{-1}(Y)$ is open since $m'(\pi(g), \pi(h))$ is continuous. Hence, $X$ and $Y$ must have been open.

I know it's stated a bit clumsy, but I am not versed in the working with products.

 

[fresh_42]

Can't I just replace closed with not open in my argument?

To restate, my argument is the following.

We know that
$m'(\pi(g), \pi(h))$ is continuous from my argument above, where $m' : G/K \times G/K \mapsto G/K$

For an open set $U \in G/K$, $m'^{-1}(U)$ maps to a set $X \times Y \in G/K \times G/K$.

If $X$ or $Y$ is not open, then $\pi^{-1}(X)$ or $\pi^{-1}(Y)$ because of the definition of the quotient topology. But we know that, $\pi^{-1}(X) \times \pi^{-1}(Y)$ is open since $m'(\pi(g), \pi(h))$ is continuous. Hence, $X$ and $Y$ must have been open.

I know it's stated a bit clumsy, but I am not versed in the working with products.

You were done when you showed that $m'$ is continuous. This means that $m'^{-1}(U)$ is open. It is the definition of a continuous function.

To show that $\pi$ is open, take an open set $V$ and calculate $\pi(V)=VK=\ldots .$

We have defined a topological group by continuity of $(g,h)\mapsto gh^{-1}$. So you have to show that $\varphi$ as defined in post #63 is continuous.

 

[jbergman]

You were done when you showed that $m'$ is continuous. This means that $m'^{-1}(U)$ is open. It is the definition of a continuous function.

To show that $\pi$ is open, take an open set $V$ and calculate $\pi(V)=VK=\ldots .$

Ahh, I finally get it!
$$\pi^{-1}(\pi(V)) = \pi^{-1}(VK) \bigcup_{k_i \in K} k_iV$$

Which is just the union of open sets, again using left multplication is a homeomorphism.

We have defined a topological group by continuity of $(g,h)\mapsto gh^{-1}$. So you have to show that $\varphi$ as defined in post #63 is continuous.

Well, my argument to show that $m'$ is continuous is essentially the same for the inverse map $i'$ and then from 5.1 we know that is equivalent to showing that $\phi$ is continuous.

Briefly,

$\pi(i(g)) = i'(\pi(g))$ and again the left is continuous so the right side must be, and since $\pi$ is surjective and continous, $i'$ must also be.

 

[fresh_42]

Ahh, I finally get it!
$$\pi^{-1}(\pi(V)) = \pi^{-1}(VK) \bigcup_{k_i \in K} k_iV$$

Which is just the union of open sets, again using left multplication is a homeomorphism.

Well, my argument to show that $m'$ is continuous is essentially the same for the inverse map $i'$ and then from 5.1 we know that is equivalent to showing that $\phi$ is continuous.

Briefly,

$\pi(i(g)) = i'(\pi(g))$ and again the left is continuous so the right side must be, and since $\pi$ is surjective and continous, $i'$ must also be.

Modulo some typos, yes.

$\pi(V)=VK=\displaystyle{\bigcup_{k\in K}Vk}=\pi(V)\subseteq G/K$ and the $Vk$ are open.

Here is the version without using part (a):

Let $\overline{V}\subseteq G/K$ be an open set, and $(gK,hK)\in \varphi^{-1}(\overline{V}).$ Since $(g,h)\longmapsto \pi(gh^{-1})=gh^{-1}K$ is continuous, there are open neighborhoods $V_g,V_h\subseteq G$ of $g,h$ such that $V_gV_h^{-1}\subseteq \pi^{-1}(\overline{V}).$ Since $\pi$ is open, $\pi(V_g)\times \pi(V_h)=V_gK\times V_hK\subseteq G/K\times G/K$ is an open neighborhood of $(gK,hK)\in G/K\times G/K.$ This proves that $\varphi$ is continuous since $V_gK\times V_hK\subseteq \varphi^{-1}(\overline{V}).$

 

[Not anonymous]

13. Let $d := d_1d_2...d_9$ be a number with not necessarily distinct nine decimal digits. A number $e := e_1e_2...e_9$ is such that each of the nine digit numbers formed by replacing just one of the digits $d_j$by the corresponding digit $e_j$ is divisible by $7$ for all $1 \leq j \leq 9$. A number $f := f_1f_2...f_9$is formed the same way by starting with $e,$ i.e. each of the nine numbers formed by replacing a $e_k$ by $f_k$ is divisible by $7$. Example: If $d = 20210901$ then $e_6 \in \{0, 7\}$ since $7 \, | \, 20210001$ and $7 \, | \, 20210701$.
Show that, for each $j, d_j - f_j$ is divisible by $7$.

Spoiler: Question 13

Let $D_{j}$ denote the number obtained by replacing $d_j$ by $e_j$ in $d$ for all $1 \leq j \leq 9$. So, for example, $D_1$ will have the decimal representation $e_1 d_2...d_9$. Similarly let $E_{j}$ denote the number obtained by replacing $e_j$ by $f_j$ in $e$ for all $1 \leq j \leq 9$.

The numeric values of $D_j, E_j$ are given by:
$D_j = (\sum_{i=1}^9 10^{9-i}d_i) - 10^{9-j}d_j + 10^{9-j}e_j = d - 10^{9-j}d_j + 10^{9-j}e_j$
$E_j = (\sum_{i=1}^9 10^{9-i}e_i) - 10^{9-j}e_j + 10^{9-j}f_j = e - 10^{9-j}e_j + 10^{9-j}f_j$
for all $1 \leq j \leq 9$.

Since $D_j \equiv 0 \, \text{mod 7}$, we get $(d - 10^{9-j}d_j + 10^{9-j}e_j)\, \text{mod 7} = 0 \Rightarrow$

$10^{9-j}e_j \, \text{mod 7} \equiv 10^{9-j}d_j\, \text{mod 7} - d \, \text{mod 7}$ (Eq. 1)

Similarly, since $E_j$ is divisible for 7 for $j = 1, 2, ...,9$, we have $E_j \equiv 0 \, \text{mod 7}$ and therefore $(e - 10^{9-j}e_j + 10^{9-j}f_j)\, \text{mod 7} = 0 \Rightarrow$

$10^{9-j}f_j \, \text{mod 7} \equiv 10^{9-j}e_j\, \text{mod 7} - e \, \text{mod 7}$ (Eq. 2)

Substituting based on (Eq.1) in (Eq. 2) gives:
$10^{9-j}f_j \, \text{mod 7} \equiv 10^{9-j}d_j\, \text{mod 7} - d \, \text{mod 7} - e \, \text{mod 7} \Rightarrow$
$10^{9-j}(d_j - f_j) \, \text{mod 7} \equiv d \, \text{mod 7} + e \, \text{mod 7}$ (Eq. 3)

Now $e = \sum_{i=1}^{9} 10^{9-i}e_i$. Using (Eq. 1), we get $$
e \, \text{mod 7} \equiv \sum_{i=1}^{9} (10^{9-i}d_i \, \text{mod 7} - d \, \text{mod 7}) \equiv (\sum_{i=1}^{9} (10^{9-i}d_i \, \text{mod 7}) - 9d \, \text{mod 7} \equiv -8d \, \text{mod 7}$$ (Eq. 4)

Applying (Eq. 4) in (Eq. 3) gives $10^{9-j}(d_j - f_j) \, \text{mod 7} \equiv d \, \text{mod 7} - 8d \, \text{mod 7} \equiv -7d \, \text{mod 7} = 0 \, \text{mod 7}$. Since $10^{9-j} \, \text{mod 7} \neq 0$ for any integer valued $j$, it follows that $(d_j - f_j) \equiv 0 \, \text{mod 7}$, i.e. Hence proved that $d_j - f_j$ must be divisible by 7 for all allowed values of $j$.

 

[fresh_42]

Spoiler: Question 13

Let $D_{j}$ denote the number obtained by replacing $d_j$ by $e_j$ in $d$ for all $1 \leq j \leq 9$. So, for example, $D_1$ will have the decimal representation $e_1 d_2...d_9$. Similarly let $E_{j}$ denote the number obtained by replacing $e_j$ by $f_j$ in $e$ for all $1 \leq j \leq 9$.

The numeric values of $D_j, E_j$ are given by:
$D_j = (\sum_{i=1}^9 10^{9-i}d_i) - 10^{9-j}d_j + 10^{9-j}e_j = d - 10^{9-j}d_j + 10^{9-j}e_j$
$E_j = (\sum_{i=1}^9 10^{9-i}e_i) - 10^{9-j}e_j + 10^{9-j}f_j = e - 10^{9-j}e_j + 10^{9-j}f_j$
for all $1 \leq j \leq 9$.

Since $D_j \equiv 0 \, \text{mod 7}$, we get $(d - 10^{9-j}d_j + 10^{9-j}e_j)\, \text{mod 7} = 0 \Rightarrow$

$10^{9-j}e_j \, \text{mod 7} \equiv 10^{9-j}d_j\, \text{mod 7} - d \, \text{mod 7}$ (Eq. 1)

Similarly, since $E_j$ is divisible for 7 for $j = 1, 2, ...,9$, we have $E_j \equiv 0 \, \text{mod 7}$ and therefore $(e - 10^{9-j}e_j + 10^{9-j}f_j)\, \text{mod 7} = 0 \Rightarrow$

$10^{9-j}f_j \, \text{mod 7} \equiv 10^{9-j}e_j\, \text{mod 7} - e \, \text{mod 7}$ (Eq. 2)

Substituting based on (Eq.1) in (Eq. 2) gives:
$10^{9-j}f_j \, \text{mod 7} \equiv 10^{9-j}d_j\, \text{mod 7} - d \, \text{mod 7} - e \, \text{mod 7} \Rightarrow$
$10^{9-j}(d_j - f_j) \, \text{mod 7} \equiv d \, \text{mod 7} + e \, \text{mod 7}$ (Eq. 3)

Now $e = \sum_{i=1}^{9} 10^{9-i}e_i$. Using (Eq. 1), we get $$
e \, \text{mod 7} \equiv \sum_{i=1}^{9} (10^{9-i}d_i \, \text{mod 7} - d \, \text{mod 7}) \equiv (\sum_{i=1}^{9} (10^{9-i}d_i \, \text{mod 7}) - 9d \, \text{mod 7} \equiv -8d \, \text{mod 7}$$ (Eq. 4)

Applying (Eq. 4) in (Eq. 3) gives $10^{9-j}(d_j - f_j) \, \text{mod 7} \equiv d \, \text{mod 7} - 8d \, \text{mod 7} \equiv -7d \, \text{mod 7} = 0 \, \text{mod 7}$. Since $10^{9-j} \, \text{mod 7} \neq 0$ for any integer valued $j$, it follows that $(d_j - f_j) \equiv 0 \, \text{mod 7}$, i.e. Hence proved that $d_j - f_j$ must be divisible by 7 for all allowed values of $j$.

Well, one can write it a bit shorter, but the ideas are the same.

We are given that for all $1\leq j\leq 9$
$$
(e_j-d_j)10^{9-j}+d \equiv 0\equiv (f_j-e_j)10^{9-j}+e \mod 7\quad (*)
$$
Thus $\sum_{j=1}^9(e_j-d_j)10^{9-j}+d=e-d+9d\equiv e+d\equiv 0\mod 7.$ Now add the first and second relation from $(*)$ for any particular value $j$ and get
$$
0 \equiv (f_j-d_j)10^{9-j}+e+d \equiv (f_j-d_j)10^{9-j} \mod 7
$$
Because $7$ is prime and $7\,\nmid\,10^{9-j}$ this implies $7\,|\,(d_j-f_j).$

 

[jbergman]

Modulo some typos, yes.

$\pi(V)=VK=\displaystyle{\bigcup_{k\in K}Vk}=\pi(V)\subseteq G/K$ and the $Vk$ are open.

Here is the version without using part (a):

Let $\overline{V}\subseteq G/K$ be an open set, and $(gK,hK)\in \varphi^{-1}(\overline{V}).$ Since $(g,h)\longmapsto \pi(gh^{-1})=gh^{-1}K$ is continuous, there are open neighborhoods $V_g,V_h\subseteq G$ of $g,h$ such that $V_gV_h^{-1}\subseteq \pi^{-1}(\overline{V}).$ Since $\pi$ is open, $\pi(V_g)\times \pi(V_h)=V_gK\times V_hK\subseteq G/K\times G/K$ is an open neighborhood of $(gK,hK)\in G/K\times G/K.$ This proves that $\varphi$ is continuous since $V_gK\times V_hK\subseteq \varphi^{-1}(\overline{V}).$

One surprising fact to me is the fact that $\pi$ is open implies that if there is an open set $U \in gK$, then the entire coset is open, since $\pi^{-1}(\pi(U)) = gK$. This must be related to 5.5.

 

[fresh_42]

One surprising fact to me is the fact that $\pi$ is open implies that if there is an open set $U \in gK$, then the entire coset is open, since $\pi^{-1}(\pi(U)) = gK$. This must be related to 5.5.

$\pi^{-1}(\pi(U)) =U \neq_{i.g} gK$

$\pi$ is open means that it maps open sets to open sets, so there are open neighborhoods around the images of those points.

 

[Not anonymous]

14. An ellipse, whose semi-axes have lengths $a$ and $b$, rolls without slipping on the curve $y = c \sin(x/a)$. How are $a, b, c$ related, given that the ellipse completes one revolution when it traverses one period of the curve?

Partial or incomplete answer, but I am posting this because I think the approach is not too far off from the correct, complete answer and so would like to know if and what mistake, if any, exists in my attempted solution. Since I don't get simple, closed-form expressions relating $a, b$ and $c$, I suspect there might be a mistake in at least one of the intermediate equations, but I am unable to find where the mistake arises.

Spoiler: Question 14

The ellipse's circumference must be equal to the length one period of the mentioned curve (a sinusoidal wave) if the ellipse completes exactly one revolution when rolls over one period of the wave.

The circumference of the ellipse, assuming $a$ is the semi-major axis and $b$ is the the semi-minor axis, is $$C = 4a \int_{0}^{\pi / 2} \sqrt {1 - (1 - b^2/a^2) \sin^2{θ}} \, dθ$$

The length of a curve $y = f(x)$ between $x=x_1$ and $x=x_2$, assuming that $f(x)$ is differentiable in the range $[x_1, x_2]$, is given by $\int_{x_1}^{x_2} \sqrt {(1 + (f'(x))^2} \, dx$. For $y = c \sin(x/a)$, $y' = f'(x) = \dfrac {c} {a} \cos (x/a)$ and therefore the length $L$ of one period of the curve is given by $$
L = \int_{\frac{x}{a} = 0}^{2 \pi} \sqrt {1 + \dfrac {c^2} {a^2} \cos^2 (x/a)} \, dx = \int_{\frac{x}{a} = 0}^{2 \pi} \sqrt {1 + \dfrac {c^2} {a^2} (1 - \sin^2 (x/a))} \, dx = \int_{\frac{x}{a} = 0}^{2 \pi} \sqrt {\dfrac{a^2+c^2}{a^2}} \sqrt {1 - \dfrac {c^2} {a^2 + c^2} \sin^2 (x/a)} \, dx
$$

Due to the symmetry of sine wave's shape, the length of the curve between $\frac{x}{a} = 0$ and $\frac{x}{a} = 2π$ equals 4 times the length of the curve between $\frac{x}{a} = 0$ and $\frac{x}{a} = π/2$. Using this property, and defining $z = x/a$ and substituting for $x, dx$ accordingly in the above equation for $L$, we get $$
L = 4 \sqrt {a^2+c^2} \int_{z = 0}^{π/2} \sqrt {1 - \dfrac {c^2} {a^2 + c^2} \sin^2 z} \, dz
$$

Since $L = C$, we get $$
\dfrac {4 \sqrt {a^2+c^2}} {4a} = \dfrac {\int_{0}^{\pi / 2} \sqrt {1 - (1 - b^2/a^2) \sin^2{θ}} \, dθ} {\int_{0}^{π/2} \sqrt {1 - \dfrac {c^2} {a^2 + c^2} \sin^2 z} \, dz}
$$

When I first attempted to solve this, I had wrongly used $\pi$ instead of $2\pi$ as the upper bound for one of the integrals and that led to neat and simple relations between $a, b, c$ and I believed that a similar simple relations would be found even after correcting that error, but that didn't happen. I thought I could try equating the constants outside the integrals in expressions for $L$ and $C$ and similarly equate the multipliers of the $\sin^2(.)$ expression inside the 2 integrands to get at least one of the possibly many valid relations between the $a, b, c$, but equating $4\sqrt {a^2+c^2}$ to $4a$ leads to $c=0$ and that cannot be a valid solution. Where is the mistake?

Thanks in advance!

 

[jbergman]

$\pi^{-1}(\pi(U)) =U \neq_{i.g} gK$

$\pi$ is open means that it maps open sets to open sets, so there are open neighborhoods around the images of those points.

This doesn't make sense to me...

If $U \subset \bigcup_{k_i \in K} gk_i$ is open in $G$, then
$\pi(U) = gK$ which must be open in $G/K$.

Therefore, $\pi^{-1}(gK) = \bigcup_{k_i \in K} gk_i$, which must be open in $G$.

Where is the above logic incorrect?

 

[fresh_42]

Partial or incomplete answer, but I am posting this because I think the approach is not too far off from the correct, complete answer and so would like to know if and what mistake, if any, exists in my attempted solution. Since I don't get simple, closed-form expressions relating $a, b$ and $c$, I suspect there might be a mistake in at least one of the intermediate equations, but I am unable to find where the mistake arises.

Spoiler: Question 14

The ellipse's circumference must be equal to the length one period of the mentioned curve (a sinusoidal wave) if the ellipse completes exactly one revolution when rolls over one period of the wave.

The circumference of the ellipse, assuming $a$ is the semi-major axis and $b$ is the the semi-minor axis, is $$C = 4a \int_{0}^{\pi / 2} \sqrt {1 - (1 - b^2/a^2) \sin^2{θ}} \, dθ$$

The length of a curve $y = f(x)$ between $x=x_1$ and $x=x_2$, assuming that $f(x)$ is differentiable in the range $[x_1, x_2]$, is given by $\int_{x_1}^{x_2} \sqrt {(1 + (f'(x))^2} \, dx$. For $y = c \sin(x/a)$, $y' = f'(x) = \dfrac {c} {a} \cos (x/a)$ and therefore the length $L$ of one period of the curve is given by $$
L = \int_{\frac{x}{a} = 0}^{2 \pi} \sqrt {1 + \dfrac {c^2} {a^2} \cos^2 (x/a)} \, dx = \int_{\frac{x}{a} = 0}^{2 \pi} \sqrt {1 + \dfrac {c^2} {a^2} (1 - \sin^2 (x/a))} \, dx = \int_{\frac{x}{a} = 0}^{2 \pi} \sqrt {\dfrac{a^2+c^2}{a^2}} \sqrt {1 - \dfrac {c^2} {a^2 + c^2} \sin^2 (x/a)} \, dx
$$

Due to the symmetry of sine wave's shape, the length of the curve between $\frac{x}{a} = 0$ and $\frac{x}{a} = 2π$ equals 4 times the length of the curve between $\frac{x}{a} = 0$ and $\frac{x}{a} = π/2$. Using this property, and defining $z = x/a$ and substituting for $x, dx$ accordingly in the above equation for $L$, we get $$
L = 4 \sqrt {a^2+c^2} \int_{z = 0}^{π/2} \sqrt {1 - \dfrac {c^2} {a^2 + c^2} \sin^2 z} \, dz
$$

Since $L = C$, we get $$
\dfrac {4 \sqrt {a^2+c^2}} {4a} = \dfrac {\int_{0}^{\pi / 2} \sqrt {1 - (1 - b^2/a^2) \sin^2{θ}} \, dθ} {\int_{0}^{π/2} \sqrt {1 - \dfrac {c^2} {a^2 + c^2} \sin^2 z} \, dz}
$$

When I first attempted to solve this, I had wrongly used $\pi$ instead of $2\pi$ as the upper bound for one of the integrals and that led to neat and simple relations between $a, b, c$ and I believed that a similar simple relations would be found even after correcting that error, but that didn't happen. I thought I could try equating the constants outside the integrals in expressions for $L$ and $C$ and similarly equate the multipliers of the $\sin^2(.)$ expression inside the 2 integrands to get at least one of the possibly many valid relations between the $a, b, c$, but equating $4\sqrt {a^2+c^2}$ to $4a$ leads to $c=0$ and that cannot be a valid solution. Where is the mistake?

Thanks in advance!

If I should check your calculations, then you will have to write way more lines of calculation.

The solution is actually very easy and short. Write the circumference of the ellipse as
$C=\int_{0}^{2\pi}\sqrt{(-a\sin \left(\theta\right))^2+(b\cos\left(\theta\right))^2}\,d\theta$ and keep the polar coordinates for $L$! Next simply bring those integrals in a comparable form for $C=L$ and conclude the solution.

 

[fresh_42]

This doesn't make sense to me...

If $U \subset \bigcup_{k_i \in K} gk_i$ is open in $G$, then
$\pi(U) = gK$ which must be open in $G/K$.

Therefore, $\pi^{-1}(gK) = \bigcup_{k_i \in K} gk_i$, which must be open in $G$.

Where is the above logic incorrect?

And the construction $gk_i$ in $G$ doesn't make any sense to me. It confuses the distinction between elements of $G$ and elements of $G/K$.

Why do you look at $U\subseteq \{g\cdot k\,|\,k\in K\}$ at all? Yes, you get $\pi(U)=gK$, so what?

$\pi^{-1}(gK)=\{g\}$ not $U$.

 

[jbergman]

And the construction $gk_i$ in $G$ doesn't make any sense to me. It confuses the distinction between elements of $G$ and elements of $G/K$.

I am not sure the confusion. A coset in $G$ consists of the set of elements, $gK = \bigcup g_i \exists k \in K s.t. g_i k = g$. In $G/K$ that set becomes a single element.

Why do you look at $U\subseteq \{g\cdot k\,|\,k\in K\}$ at all? Yes, you get $\pi(U)=gK$, so what?

$\pi^{-1}(gK)=\{g\}$ not $U$.

I know it isn't $U$. I never claimed it was. $U$ isn't a saturated open subset unless it is the entire coset. It also isn't a single element $g$ since all elements of the coset in $G$ map to the same element $gK$.

Either I have a giant misunderstanding or we are having some miscommunication issue here.

 

[fresh_42]

Either I have a giant misunderstanding or we are having some miscommunication issue here.

I guess misunderstanding.

One surprising fact to me is the fact that $\pi$ is open implies that if there is an open set $U \in gK$, then the entire coset is open, since $\pi^{-1}(\pi(U)) = gK$. This must be related to 5.5.

I did not understand $U\in gK$. This is a mixture of $G$ and $G/K$. If you say open, then you have to say open in what.

 

[jbergman]

I guess misunderstanding.

I did not understand $U\in gK$. This is a mixture of $G$ and $G/K$. If you say open, then you have to say open in what.

Sorry for the confusion. I am not sure how people typically notate these things.

 

[fresh_42]

Sorry for the confusion. I am not sure how people typically notate these things.

One convention is to write cosets with an overline: $gK=\overline{g}$. If you write $gK$ then it is unclear whether you mean $gK=\{gk\,|\,k\in K\}\subseteq G$ or $gK\in G/K$.

So $U\subseteq G$ and $\overline{U}\subseteq G/K$ is a possibility to distinguish $G$ from $G/K$. And, of course, we could also write everything in $G/K$ as images of $\pi\, : \,G \twoheadrightarrow G/K$ namely $gK=\overline{g}=\pi(g) \in G/K\, , \,\overline{U}=\pi(U)\subseteq G/K.$

So $gK \subseteq G$ is actually the misleading notation. It would be better to write $\pi^{-1}(\overline{g}).$ This has also the advantage, that it is immediately obvious that $gK\subseteq G$ is closed, as it is the pre-image of a closed set $(\overline{g}\in G/K$ is a singleton and therefore closed, at least in $T_1$ topologies) under a continuous function.

 

[julian]

Problem #7:

Spoiler

Write

\begin{align*}
f (x) = x - (1+x) \log (1+x) + \frac{3x^2}{2 (3+x)}
\end{align*}

We must show that $f (x) \leq 0$ for $x > -1$.

The first derivative is

\begin{align*}
\frac{d}{dx} f (x) = - \log (1+x) + \frac{3 x (x + 6)}{2(3+x)^2}
\end{align*}

This has a zero at $x=0$, with $f (0) = 0$.

The second derivative is

\begin{align*}
\frac{d^2}{dx^2} f (x) = - \frac{x^2 (x + 9)}{(1+x) (3+x)^3}
\end{align*}

which is zero at $x = 0$, so we may have a maximum, a minimum or an inflection.

As

\begin{align*}
\frac{d}{dx} f (x) = - \int_0^x \frac{y^2 (y + 9)}{(1+y) (3+y)^3} dy
\end{align*}

we have $\frac{d}{dx} f (x)$ is positive for all $-1 < x < 0$ and we have $\frac{d}{dx} f (x)$ is negative for all $x > 0$.

Which means the function $f (x)$ is monotonically increasing for $-1 < x < 0$ and monotonically decreasing for $x > 0$. So $f(x)$ has a global maximum of zero at $x = 0$ for $x > -1$.

ADDITONAL: The third derivative, $f''' (0)$, is zero but the fourth derivative, $f'''' (0)$, is negative, so by the higher derivative test the function $f(x)$ has a local maximum at $x = 0$.

 

[julian]

Problem #9 parts 5 and 6.

Spoiler

5.

We prove $\frac{2^{2n-1}}{n} \leq \binom{2n}{n}$ by induction. The base case is trivial $\frac{2^1}{1} \leq \binom{2}{1}$.

We assume

\begin{align*}
\frac{2^{2n-1}}{n} \leq \binom{2n}{n} .
\end{align*}

This together with $4n \leq 2(2n+1)$ implies

\begin{align*}
4n \cdot \frac{2^{2n-1}}{n} \leq 2 (2n+1) \binom{2n}{n}
\end{align*}

or

\begin{align*}
\frac{1}{n+1} \cdot 2^{2n+1} \leq \frac{(2n + 2) (2n+1)}{(n+1)^2} \binom{2n}{n}
\end{align*}

or

\begin{align*}
\frac{2^{2(n+1)-1}}{n + 1} \leq \binom{2(n+1)}{n+1}
\end{align*}

completing the inductive argument.

We prove $\binom{2n}{n} \leq 2^{2n-1}$ by induction. The base case is trivial $\binom{2}{1} \leq 2^1$.

We assume

\begin{align*}
\binom{2n}{n} \leq 2^{2n-1} .
\end{align*}

This together with $2n+1 \leq 2 (n+1)$ implies

\begin{align*}
2 \frac{2n+1}{n+1} \binom{2n}{n} \leq 4 \cdot 2^{2n-1}
\end{align*}

which easily becomes

\begin{align*}
\binom{2(n+1)}{n+1} \leq 2^{2(n+1)-1}
\end{align*}

completing the inductive argument.
6.

We prove $\prod_{p \leq n} p < 4^n$ by induction. The base cases $n = 2$ obviously works (I guess the for the case $n = 1$ you use the convention that $\prod_{p \leq 1} p = 0$ as 1 is not a prime).

Assume $\prod_{p \leq m} p < 4^m$ for all $m < n$, we wish to prove the result $\prod_{p \leq n} p < 4^n$.

This is easy if $n$ is not prime because then

\begin{align*}
\prod_{p \leq n} p = \prod_{p \leq n-1} p < 4^{n-1} < 4^n .
\end{align*}

We now consider the case where $n$ is prime. As we are considering primes greater than 2, we can write $n = 2k+1$.

Consider

\begin{align*}
\binom{2k+1}{k} = \frac{(2k+1) \cdots (q) \cdots (k+2)}{k!} = (2k+1) \cdots \frac{(q)}{k!} \cdots (k+2)
\end{align*}

where $q$ is a prime. As none of the factors in $k!$ can divide $q$ the $q$ cannot be cancelled. Hence $q$ divides $\binom{2k+1}{k}$. Hence, $\binom{2k+1}{k}$ is divisible by all prime numbers greater than or equal to $k + 2$ and less than or equal to $2k + 1$, that is, it is divisible by

\begin{align*}
Q = \prod_{k+2 \leq p \leq 2k+1} p = \dfrac{\prod_{p \leq 2k+1} p}{\prod_{p \leq k+1} p}
\end{align*}

So that $Q \leq \binom{2k+1}{k}$. But

\begin{align*}
\binom{2k+1}{k} & < \binom{2k+1}{0} + \binom{2k+1}{1} + \cdots + \binom{2k+1}{k - 1} + \binom{2k+1}{k}
\nonumber \\
& = \frac{1}{2} \left( \binom{2k+1}{0} + \binom{2k+1}{1} + \cdots + \binom{2k+1}{2k} + \binom{2k+1}{2k + 1} \right)
\nonumber \\
& = \frac{1}{2} (1+1)^{2k + 1} = 4^k .
\end{align*}

Hence $Q < 4^k$, or in other words

\begin{align*}
\dfrac{\prod_{p \leq 2k+1} p}{\prod_{p \leq k+1} p} < 4^k
\end{align*}

which by the inductive hypothesis implies

\begin{align*}
\prod_{p \leq 2k+1} p < 4^k \prod_{p \leq k+1} p < 4^{2k + 1} .
\end{align*}

Completing the inductive argument.

 

[fresh_42]

(I guess the for the case $n=1$ you use the convention that $\prod_{p\leq 1}p=0$ as $1$ is not a prime).

No. The usual convention for an empty product is, to set it equal to $1$. This is because $0$ isn't part of multiplicative groups, and $1$ is their neutral element. It is the same reason why empty sums are considered to be $0.$ And it preserves the important functional equation $\exp(0+0)=\exp(0)\cdot\exp(0).$

 

[julian]

Problem #9 part 4.

Spoiler

By definition of $\text{ord}_p (N)$ it is the exponent of $p$ in the prime number decomposition of the number $N!$. Using part 1 of the question we have that the exponent of $p$ in the prime number decomposition of $\binom{2n}{n}$, denote it $\nu_p (n)$, is given by

\begin{align*}
\nu_p (n) & = \text{ord}_p (2n) - 2 \text{ord}_p (n)
\nonumber \\
& = \left( \left\lfloor \frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \right) + \left( \left\lfloor \frac{2n}{p^2} \right\rfloor - 2 \left\lfloor \frac{n}{p^2} \right\rfloor \right) + \cdots \quad (*)
\end{align*}

When $p^k >2n$ we have that $\left( \left\lfloor \frac{2n}{p^k} \right\rfloor - 2 \left\lfloor \frac{n}{p^k} \right\rfloor \right) = 0$. Otherwise each such term in $(*)$ is either 0 or 1 as $\left\lfloor 2a \right\rfloor - 2 \left\lfloor a \right\rfloor$ is either 0 or 1. Let $k_{max}$ be the largest integer such that $p^{k_{max}} \leq 2n$. Then $\nu_p (n) \leq k_{max}$.

So if $p^r | \binom{2n}{n}$ then

\begin{align*}
p^r \leq p^{\nu_p (n)} \leq p^{k_{max}} \leq 2n .
\end{align*}

 

[benorin]

Spoiler: #1

#1) "Um, I'll take what is the Bohr-Mollerup Theorem for 200 points, Alex."

I want you honest opinions here, what do you think of my new signature? Simple yet amazing truth but is it too long?

Who's grading this month, @fresh_42 ? I think I should also get credit for #1) bc of the quoted post, the Bohr-Mollerup Theorem:

It is trivial from this theorem's definition of the Gamma function to obtain the form of it given in the problem (by existence + uniqueness of the Gamma function), but if you like I can furnish the leg work.

 

[MathematicalPhysicist]

Who's grading this month, @fresh_42 ? I think I should also get credit for #1) bc of the quoted post, the Bohr-Mollerup Theorem:

View attachment 289735

It is trivial from this theorem's definition of the Gamma function to obtain the form of it given in the problem (by existence + uniqueness of the Gamma function), but if you like I can furnish the leg work.

Is there a prize for the highest grades?
Otherwise I wouldn't care if I got graded or not.

 

[fresh_42]

Is there a prize for the highest grades?

Well, we would have to ask @Greg Bernhardt. Maybe we could create a badge for it.

Otherwise I wouldn't care if I got graded or not.

I have written a TeX-file and created a pdf listing all of my problems and solutions up to the end of the year. It has 530 pages. Additionally, we have had many problems from other members. This means: the counting has to be done by somebody else! I suggest an Excel sheet.

 

[Not anonymous]

15. For a partition $\pi$ of $N := \{1, 2, ..., 9\}$, let $\pi(x)$ be the number of elements in the part containing $x$. Prove that for any two partitions $\pi_1$ and $\pi_2$, there are two distinct numbers $x$ and $y$ in $N$ such that $\pi_j(x) = \pi_j(y)$ for $j=1,2$.

Spoiler: Question 15

Claim 1: Suppose a partition $\pi_1$ of $N = \{1,2,...,9\}$ has 4 distinct numbers, say $a_1, a_2, a_3, a_4$, such that $\pi_1(a_1) = \pi_1(a_2) = \pi_1(a_3) = \pi_1(a_4)$. Then there cannot be another partition $\pi_2$ of $N$ such that $\pi_1(x) = \pi_1(y)$ but $\pi_2(x) \neq \pi_2(y)$ for all distinct $x, y \in N$. In other words, for any other partition $\pi_2$ of $N$, we can find distinct $x, y \in N$ such that $\pi_j(x) = \pi_j(y)$ for $j=1,2$

Proof by contradiction: Suppose there exists a partition $\pi_2$ of the form claimed to not exist above. Then we must have $\pi_2(a_i) \neq \pi_2(a_j)$ for all $i, j \in \{1,2,3,4\}$ with $i \neq j$. Hence $\pi_2(a_1), \pi_2(a_2), \pi_2(a_3), \pi_2(a_4)$ must all be distinct, i.e. each of $a_1, a_2, a_3, a_4$ must belong to a different part in $\pi_2$ and this implies that $\pi_2$ has at least 4 parts of distinct cardinalities. Thus, the number of numbers in $\pi_2$ must be at least $1+2+3+4 = 10$, but this contradicts the fact that $\pi_2$ is a partition of $N$ and hence must have only 9 distinct numbers. This proves that any other partition of $\pi_2$ of $N$ must be such that there will exist at least 2 distinct numbers $x, y \in \{a_1, a_2, a_3, a_4\}$ such that $\pi_2(x) = \pi_2(y)$. And since by definition of $a_i$'s, $\pi_1(x) = \pi_1(y)$, we have found $x,y$ such that $\pi(x) = \pi(y)$ in both $\pi_1$ and $\pi_2$.

---

Now consider the following cases for $\pi_1$.

Case 1: $\pi_1$ has at least 1 part with a cardinality of 4 or more (i.e. the part is a subset of $N$ with at least 4 elements) or has at least 2 parts with the same cardinality and these equal-sized parts have 2 or more elements.

In this case, it is easy to see that there are at least 4 distinct numbers in $N$, say $a_1, a_2, a_3, a_4$, such that $\pi_1(a_1) = \pi_1(a_2) = \pi_1(a_3) = \pi_1(a_4)$. We simply take any 4 numbers from the largest cardinality part in $\pi_1$ as that part is stated to have 4 or more elements. This $\pi_1$ clearly satisfies the condition of claim 1.

Case 2: All parts in $\pi_1$ have a cardinality of 3 or less and at most one part in $\pi_1$ can have a cardinality of 2 or 3.

In this case, since at most one part can have a cardinality greater than 1 and the maximum allowed cardinality of a part is 3, $\pi_1$ must have at least 4 parts whose cardinality is 1 (single element parts). This is because the maximum number of elements contained in the parts of size more than one is $2+3=5$ (one part of size 2, one part of size 3) and the remaining $9-5=4$ numbers must be covered by single-element parts. Here again, $\pi_1$ clearly satisfies the condition of claim 1.

Cases (1) and (2) cover all possible ways to form a partition $\pi_1$ of $N$. Since in both cases $\pi_1$ meets the condition stated in claim 1, it follows that it is not possible to have another partition $\pi_2$ of $N$ such that $\pi_1(x) \neq \pi_2(y)$ for all distinct $x, y \in N$. In other words, for any other partition $\pi_2$ of $N$, we can find distinct $x, y \in N$ such that $\pi(x) = \pi(y)$ in both $\pi_1$ and $\pi_2$. Hence proved.

 

[nuuskur]

The well known Maschke's theorem for Problem 4 :)

 

[fresh_42]

The well known Maschke's theorem for Problem 4 :)

But Maschke is easy enough to prove, fulfills the requirement to learn something, and last but not least doesn't provide a counterexample for $\operatorname{char}\mathbb{F}\,\mid\,|G| .$

 

[nuuskur]

IIRc the result is the group algebra is semisimple if and only if \mathrm{char}F \not\mid |G|.

 

[fresh_42]

IIRc the result is the group algebra is semisimple if and only if \mathrm{char}F \not\mid |G|.

Sure. Otherwise, there wouldn't be a counterexample.

 

[Office_Shredder]

It's funny, number 3 is just a continuous version of number 2 (if your random variables take discrete values with probabilities that can be expressed as integer ratios as each other, then #3 turns into #2 I think) but somehow, #3 seemed obviously true to me and #2 seemed like a crazy result when I first read it.Anyway, here's a proof for #3.

Edit: ahh my dog posted this when I started typing. I'll remove this when I finish writing the proof.

Spoiler

It suffices to show for $r>1$, that $P(r-1 < |X-Y| \leq r) \leq 2P(|X-Y| \leq 1)$, since then
$$P(|X-Y| \leq r) = P(| X-Y| \leq 1) + \sum_{k=2}^r P(r-1 < |X-Y| \leq r) \leq P(| X-Y| \leq 1) + 2(r-1)P(| X-Y| \leq 1).$$

 

[fresh_42]

It's funny, number 3 is just a continuous version of number 2 (if your random variables take discrete values with probabilities that can be expressed as integer ratios as each other, then #3 turns into #2 I think) but somehow, #3 seemed obviously true to me and #2 seemed like a crazy result when I first read it.Anyway, here's a proof for #3.

Edit: ahh my dog posted this when I started typing. I'll remove this when I finish writing the proof.

Spoiler

It suffices to show for $r>1$, that $P(r-1 < |X-Y| \leq r) \leq 2P(|X-Y| \leq 1)$, since then
$$P(|X-Y| \leq r) = P(| X-Y| \leq 1) + \sum_{k=2}^r P(r-1 < |X-Y| \leq r) \leq P(| X-Y| \leq 1) + 2(r-1)P(| X-Y| \leq 1).$$

Yes, and it's a bit short. I post my solution which is a bit more detailed.

Fix an integer $m,$ and let $S:=(x_1,\ldots,x_m)$ be a random sequence of $m$ elements, where each $x_i$ is chosen, randomly and independently, according to the distribution of $X.$ By the previous statement (problem #2)
$$
|S_r| <(2r-1)|S_1|.
$$
Therefore, the expectation of $|S_r|$ is smaller than that of $(2r-1)|S_1|.$ However, by the linearity of expectation it follows that the expectation of $|S_b|$ is precisely $m+m(m-1)p_b$ for every $b>0.$ Thus
$$
m+m(m-1)p_r< (2r-1)(m+(m-1)p_1),
$$
implying that for every integer $m,$
$$
p_r< (2r-1)p_1+\dfrac{2r-2}{m-1} \stackrel{m\to \infty }{\longrightarrow } (2r-1)p_1
$$

It can be proven that even the strict inequality
$$\operatorname{prob}\left(|X-Y|\leq 2\right) < 3\cdot \operatorname{prob}\left(|X-Y|\leq 1\right)$$
holds, in which case we speak of the 1-2-3 theorem.

 

[julian]

Problem #8:

Spoiler

We have

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq a \right) & = P \left( \sum_{k=1}^n X_k \geq na \right)
\nonumber \\
& = P \left( e^{t \sum_{k=1}^n X_k} \geq e^{tna} \right)
\nonumber \\
& \leq e^{- tna} E (e^{t \sum_{k=1}^n X_k}) \qquad \qquad (\text{Chernoff bound})
\nonumber \\
& = e^{- tna} \prod_{k=1}^n E (e^{t X_k}) \qquad (\text{independent random variables}) \quad (*)
\end{align*}

Let $E(X_k) = 0$, $E(X_k^2) = \sigma_k^2 \leq \sigma^2$ and that $| X_k | \leq B$. We have for $i > 2$ that $E (X_k^i) = E (X_k^{i-2} X_k^2) \leq B^{i-2} \sigma_k^2$, so that

\begin{align*}
R_k & = \sum_{i=2}^\infty \frac{t^{i-2} E(X_k^i)}{i! \sigma_k^2} \leq \sum_{i=2}^\infty \frac{t^{i-2} B^{i-2} \sigma_k^2}{i! \sigma_k^2}
\nonumber \\
& = \frac{1}{(t B)^2} \sum_{i=2}^\infty \frac{t^i B^i}{i!}
\nonumber \\
& = \frac{e^{tB} - 1 - tB}{(t B)^2}
\end{align*}

Then

\begin{align*}
E (e^{t X_k}) & = E \left( 1 + t X_k + \sum_{i=2}^\infty \frac{t^i X_k^i}{i!} \right)
\nonumber \\
& = 1 + t^2 \sigma_k^2 R_k
\nonumber \\
& \leq e^{t^2 \sigma_k^2 R_k}
\nonumber \\
& = \exp \left\{ t^2 \sigma_k^2 \frac{e^{tB} - 1 - tB}{(t B)^2} \right\}
\end{align*}

Using this in $(*)$

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq a \right) & \leq e^{- tna} \prod_{k=1}^n \exp \left\{ t^2 \sigma_k^2 \frac{e^{tB} - 1 - tB}{(t B)^2} \right\}
\nonumber \\
& = e^{- tna} \exp \left\{ n t^2 \tilde{\sigma}^2 \frac{e^{tB} - 1 - tB}{(tb)^2}
\right\} \quad (**)
\end{align*}

(where we have defined $\tilde{\sigma}^2 = \frac{1}{n} \sum_{k=1}^n \sigma_k^2 \leq \sigma^2$). We minimise the RHS of $(**)$ with respect to $t$:

\begin{align*}
& \frac{d}{dt} \exp \left\{ n t^2 \tilde{\sigma}^2 \frac{e^{tB} - 1 - tB}{(tB)^2} - tna \right\}
\nonumber \\
& = \exp \left\{ n t^2 \tilde{\sigma}^2 \frac{e^{tB} - 1 - tB}{(tb)^2} - tna \right\} n (\tilde{\sigma}^2 \left( \frac{B e^{tB} - B}{B^2} \right) - a) = 0
\end{align*}

We have a tighter bound when $t = \frac{1}{B} \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right)$. Using this in $(**)$:

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq a \right) & \leq \exp \left\{ n \tilde{\sigma}^2 \frac{ (\frac{aB}{\tilde{\sigma}^2} + 1) - 1 - \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right)}{B^2} - \frac{na}{B} \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right) \right\}
\nonumber \\
& = \exp \left\{ \frac{n \tilde{\sigma}^2}{B^2} \left[ \frac{aB}{\tilde{\sigma}^2} - \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right) - \frac{aB}{\tilde{\sigma}^2} \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right) \right] \right\}
\nonumber \\
& = \exp \left\{ - \frac{n \tilde{\sigma}^2}{B^2} f \left( \frac{aB}{\tilde{\sigma}^2} \right) \right\}
\end{align*}

where $f(u) = (1+ u) \log (1+ u) - u \geq 0$ for $u \geq 0$ (as $f(0) = 0$ and $f'(u) = \log (1 + u) \geq 0$). We can use the inequality $u - (1+u) \log (1+ u) \leq - \dfrac{3u^2}{2(u + 3)}$ ($u > -1$), corresponding to problem #7, to obtain

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq a \right) & \leq \exp \left\{ - \frac{a^2}{\dfrac{2 \tilde{\sigma}^2}{n} + \dfrac{2Ba}{3n}}
\right\}
\nonumber \\
& \leq \exp \left\{ - \frac{a^2}{\dfrac{2 \sigma^2}{n} + \dfrac{2Ba}{3n}} \right\} \qquad (\sigma^2 \geq \tilde{\sigma}^2)
\end{align*}

Put

\begin{align*}
a = \sqrt{ \frac{2 \sigma^2 T}{n}} + \frac{2BT}{3n}
\end{align*}

then

\begin{align*}
a^2 = \frac{2 \sigma^2 T}{n} + 2 \sqrt{ \frac{2 \sigma^2}{n}} \frac{2B}{3n} T^{3/2} + \left( \frac{2B}{3n} \right)^2 T^2
\end{align*}

and

\begin{align*}
\frac{2 \sigma^2}{n} + \frac{2B}{3n} a = \frac{2 \sigma^2}{n} + \sqrt{ \frac{2 \sigma^2}{n}} \frac{2B}{3n} \sqrt{T} + \left( \frac{2B}{3n} \right)^2 T
\end{align*}

so that

\begin{align*}
- \frac{a^2}{\frac{2 \sigma^2}{n} + \frac{2B}{3n} a} \leq - \frac{a^2}{\frac{2 \sigma^2}{n} + \sqrt{ \frac{2 \sigma^2}{n}} \frac{2B}{3n} \sqrt{T} + \frac{2B}{3n} a} = - T
\end{align*}

So finally

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq \sqrt{ \frac{2 \sigma^2 T}{n}} + \frac{2BT}{3n} \right) \leq e^{-T} .
\end{align*}

 

[fresh_42]

Problem #8:

Spoiler

We have

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq a \right) & = P \left( \sum_{k=1}^n X_k \geq na \right)
\nonumber \\
& = P \left( e^{t \sum_{k=1}^n X_k} \geq e^{tna} \right)
\nonumber \\
& \leq e^{- tna} E (e^{t \sum_{k=1}^n X_k}) \qquad \qquad (\text{Chernoff bound})
\nonumber \\
& = e^{- tna} \prod_{k=1}^n E (e^{t X_k}) \qquad (\text{independent random variables}) \quad (*)
\end{align*}

Let $E(X_k) = 0$, $E(X_k^2) = \sigma_k^2 \leq \sigma^2$ and that $| X_k | \leq B$. We have for $i > 2$ that $E (X_k^i) = E (X_k^{i-2} X_k^2) \leq B^{i-2} \sigma_k^2$, so that

\begin{align*}
R_k & = \sum_{i=2}^\infty \frac{t^{i-2} E(X_k^i)}{i! \sigma_k^2} \leq \sum_{i=2}^\infty \frac{t^{i-2} B^{i-2} \sigma_k^2}{i! \sigma_k^2}
\nonumber \\
& = \frac{1}{(t B)^2} \sum_{i=2}^\infty \frac{t^i B^i}{i!}
\nonumber \\
& = \frac{e^{tB} - 1 - tB}{(t B)^2}
\end{align*}

Then

\begin{align*}
E (e^{t X_k}) & = E \left( 1 + t X_k + \sum_{i=2}^\infty \frac{t^i X_k^i}{i!} \right)
\nonumber \\
& = 1 + t^2 \sigma_k^2 R_k
\nonumber \\
& \leq e^{t^2 \sigma_k^2 R_k}
\nonumber \\
& = \exp \left\{ t^2 \sigma_k^2 \frac{e^{tB} - 1 - tB}{(t B)^2} \right\}
\end{align*}

Using this in $(*)$

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq a \right) & \leq e^{- tna} \prod_{k=1}^n \exp \left\{ t^2 \sigma_k^2 \frac{e^{tB} - 1 - tB}{(t B)^2} \right\}
\nonumber \\
& = e^{- tna} \exp \left\{ n t^2 \tilde{\sigma}^2 \frac{e^{tB} - 1 - tB}{(tb)^2}
\right\} \quad (**)
\end{align*}

(where we have defined $\tilde{\sigma}^2 = \frac{1}{n} \sum_{k=1}^n \sigma_k^2 \leq \sigma^2$). We minimise the RHS of $(**)$ with respect to $t$:

\begin{align*}
& \frac{d}{dt} \exp \left\{ n t^2 \tilde{\sigma}^2 \frac{e^{tB} - 1 - tB}{(tB)^2} - tna \right\}
\nonumber \\
& = \exp \left\{ n t^2 \tilde{\sigma}^2 \frac{e^{tB} - 1 - tB}{(tb)^2} - tna \right\} n (\tilde{\sigma}^2 \left( \frac{B e^{tB} - B}{B^2} \right) - a) = 0
\end{align*}

We have a tighter bound when $t = \frac{1}{B} \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right)$. Using this in $(**)$:

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq a \right) & \leq \exp \left\{ n \tilde{\sigma}^2 \frac{ (\frac{aB}{\tilde{\sigma}^2} + 1) - 1 - \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right)}{B^2} - \frac{na}{B} \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right) \right\}
\nonumber \\
& = \exp \left\{ \frac{n \tilde{\sigma}^2}{B^2} \left[ \frac{aB}{\tilde{\sigma}^2} - \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right) - \frac{aB}{\tilde{\sigma}^2} \log \left( \frac{aB}{\tilde{\sigma}^2} + 1 \right) \right] \right\}
\nonumber \\
& = \exp \left\{ - \frac{n \tilde{\sigma}^2}{B^2} f \left( \frac{aB}{\tilde{\sigma}^2} \right) \right\}
\end{align*}

where $f(u) = (1+ u) \log (1+ u) - u \geq 0$ for $u \geq 0$ (as $f(0) = 0$ and $f'(u) = \log (1 + u) \geq 0$). We can use the inequality $u - (1+u) \log (1+ u) \leq - \dfrac{3u^2}{2(u + 3)}$ ($u > -1$), corresponding to problem #7, to obtain

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq a \right) & \leq \exp \left\{ - \frac{a^2}{\dfrac{2 \tilde{\sigma}^2}{n} + \dfrac{2Ba}{3n}}
\right\}
\nonumber \\
& \leq \exp \left\{ - \frac{a^2}{\dfrac{2 \sigma^2}{n} + \dfrac{2Ba}{3n}} \right\} \qquad (\sigma^2 \geq \tilde{\sigma}^2)
\end{align*}

Put

\begin{align*}
a = \sqrt{ \frac{2 \sigma^2 T}{n}} + \frac{2BT}{3n}
\end{align*}

then

\begin{align*}
a^2 = \frac{2 \sigma^2 T}{n} + 2 \sqrt{ \frac{2 \sigma^2}{n}} \frac{2B}{3n} T^{3/2} + \left( \frac{2B}{3n} \right)^2 T^2
\end{align*}

and

\begin{align*}
\frac{2 \sigma^2}{n} + \frac{2B}{3n} a = \frac{2 \sigma^2}{n} + \sqrt{ \frac{2 \sigma^2}{n}} \frac{2B}{3n} \sqrt{T} + \left( \frac{2B}{3n} \right)^2 T
\end{align*}

so that

\begin{align*}
- \frac{a^2}{\frac{2 \sigma^2}{n} + \frac{2B}{3n} a} \leq - \frac{a^2}{\frac{2 \sigma^2}{n} + \sqrt{ \frac{2 \sigma^2}{n}} \frac{2B}{3n} \sqrt{T} + \frac{2B}{3n} a} = - T
\end{align*}

So finally

\begin{align*}
P \left( \frac{1}{n} \sum_{k=1}^n X_k \geq \sqrt{ \frac{2 \sigma^2 T}{n}} + \frac{2BT}{3n} \right) \leq e^{-T} .
\end{align*}

Very good!

I knew the Chernoff bound as Markov inequality ...

The Markov inequality says that for a monotone increasing function $f: \mathbb{R}\longrightarrow [0,\infty )$ and a constant $a\in \mathbb{R}$
$$
f(a)\cdot P(X\geq a) \leq E(f(X))
$$
and in particular for $f(a)>0$
$$
P(X\geq a) \leq \dfrac{E(f(X))}{f(a)}.
$$

... but I also thought nobody would solve this one. The name of the inequality in the statement (#8) is Bernstein inequality.