Math Challenge - October 2018

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #1
12,877
9,511

Main Question or Discussion Point

Summer is coming and brings .... Oops, time for a change!

Fall (Spring) is here and what's better than to solve some tricky problems on a long dark evening (with the power of returning vitality all around).

RULES:
a) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored. Solutions will be posted around 15th of the following month.
b) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
c) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
d) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.
e) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems. In case of an inadvertent posting of a solution the post will be deleted.

We have quite a couple of old problems, which are still open. Seven of Ten in each of the September threads to be exact:
https://www.physicsforums.com/threads/basic-math-challenge-september-2018.954490/
https://www.physicsforums.com/threads/intermediate-math-challenge-september-2018.954495/
so you can still try to solve them. Answers will be given on demand if someone is interested in it, otherwise we will leave them as is. Maybe someone will come one day and tackle them.

As it seems more and more unnecessary to split threads between "Basic" and "Intermediate" as apperently "Calculus" and "other" were more significant, we decided to post all questions with a varying number of them in one thread instead, so that everyone can pick the problems he likes best, regardless of what we think is difficult or not. I also want to thank @wrobel for the problem about Noether's theorem which he provided.

Some of the questions are on a level, which could be solved by High Schoolers. I will mark them with an "H" and hope those of you which aren't in school anymore will leave them for actual high school students - maybe at least for two week. Thanks.

1. Solve and describe the solution step by step in quadrature a Lagrangian differential equation with Lagrangian
$$L(t,x,\dot x)=\frac{1}{2}\dot x^2-\frac{t}{x^4}.$$(by @wrobel )

2. (solved by @Math_QED )
a) Let ##X## be a set and ##\mathcal{F}=\{\,\{\,x\,\}\,|\,x\in X\,\}##. Determine the ##\sigma-##algebra ##\sigma(\mathcal{F})##.
b) Let ##X## be a set and ##S\subseteq \mathcal{P}(X)##. Show that for ##A\in \sigma(S)## there is an ##S_0\subseteq S## such that ##S_0## is countable and ##A \in \sigma(S_0)##.
(by @fresh_42 )

3. Let [itex]f(x)\in\mathbb{Q}[x][/itex] be a degree 5 polynomial with splitting field [itex]K[/itex]. Suppose that there is a unique extension [itex]F/\mathbb{Q}[/itex] such that [itex]F\subset K[/itex] and [itex][K:F]=3[/itex]. Show that [itex]f(x)[/itex] is divisible by a degree 3 irreducible element of [itex]\mathbb{Q}[x][/itex]. (by @Infrared )

4. a) Let ##f\, : \,\mathbb{R}^2 \longrightarrow \mathbb{R}## be defined as
$$
f(x,y) =
\begin{cases}
1 & \text{if } x \geq 0 \text{ and }x \leq y < x+1\\
-1 & \text{if } x \geq 0 \text{ and }x+1 \leq y < x+2\\
0 & \text{elsewhere }
\end{cases}
$$
Now calculate ##\int_\mathbb{R}\left[\int_\mathbb{R}f(x,y)\,d\lambda(x) \right] \,d\lambda(y)## and ##\int_\mathbb{R}\left[\int_\mathbb{R}f(x,y)\,d\lambda(y) \right]\,d\lambda(x)\,,## and why isn't it a contradiction to Fubini's theorem.
4. b) (solved by @benorin ) Show that the integral
$$
\int_A \dfrac{1}{x^2+y}\,d\lambda(x,y)
$$
with ##A=(0,1)\times (0,1)\subseteq \mathbb{R}^2## is finite. (by @fresh_42 )

5. a) Let [itex]n[/itex] be a positive integer. Let [itex]a_1,\ldots,a_k[/itex] be (positive) factors of [itex]n[/itex] such that [itex]\gcd(a_1,\ldots,a_k,n)=1[/itex]. How many solutions [itex](x_1,\ldots,x_k)[/itex] does the equation [itex]a_1x_1+\ldots+a_kx_k\equiv 0\mod n[/itex] have subject to the restriction that [itex]0\leq x_i<n/a_i[/itex] for each [itex]i[/itex]?
5. b) How does the solution change if [itex]\gcd(a_1,\ldots,a_k,n)=d>1[/itex]? (by @Infrared)

6. (solved by @lpetrich ) Calculate
a) $$\sum_{n=0}^\infty \left(\dfrac{2}{2+3i} \right)^n$$
b) $$\sum_{n=0}^\infty \left(2\sqrt{n}-4\sqrt{n+1}+2\sqrt{n+2} \right)$$
c) $$\sum_{n=3}^\infty \dfrac{8n}{(n^2-1)^2}$$
d) $$\lim_{x \to 0}\dfrac{\cos(x^2)-\sqrt{1+x^3}}{x^3}$$
(by @fresh_42 )

7. (solved by @benorin )
7. a) Determine ##\int_1^\infty \frac{\log(x)}{x^3}\,dx\,.##
7. b) Determine for which ##\alpha## the integral ##\int_0^\infty x^2\exp(-\alpha x)\,dx## converges.
7. c) Find a sequence of functions ##f_n\, : \,\mathbb{R}\longrightarrow \mathbb{R}\, , \,n\in \mathbb{N}## such that $$\sum_\mathbb{N}\int_\mathbb{R}f_n(x)\,dx \neq \int_\mathbb{R}\left(\sum_\mathbb{N}f_n(x) \right) \,dx$$
7. d) Find a family of functions ##f_r\, : \,\mathbb{R}^+\longrightarrow \mathbb{R}\, , \,r\in \mathbb{R}## such that
$$
\lim_{r \to 0}\int_\mathbb{R}f_r(x)\,dx \neq \int_\mathbb{R} \lim_{r \to 0} f_r(x) \,dx
$$
7. e) Find an example for which
$$
\dfrac{d}{dx}\int_\mathbb{R}f(x,y)\,dy \neq \int_\mathbb{R}\dfrac{\partial}{\partial x}f(x,y)\,dy
$$
(by @fresh_42 )

8. Let ##f##, ##g##: ##\mathbb{R} \rightarrow \mathbb{R}## be two functions with ##f\,''(x) + f\,'(x)g(x) - f(x) = 0##. Show that if ##f(a) = f(b) = 0## then ##f(x) = 0## for all ##x\in [a,b]##. (by @QuantumQuest )

9. (solved by @nuuskur ) Let ##\hat{\mathbb{C}}=\mathbb{C}\cup \{\,\infty\,\}## with the usual Euclidean topology on ##\mathbb{C}## and
$$
\hat{\mathcal{T}}=\{\,U\subseteq \hat{\mathbb{C}}\,|\,\infty \notin U \,\wedge \,U\subseteq \mathbb{C}\text{ open}\,\}\,\cup \,\{\,U\subseteq \hat{\mathbb{C}}\,|\,\infty \in U \,\wedge \,U^C\subseteq \mathbb{C}\text{ compact}\,\}
$$
9. a) ##\hat{\mathcal{T}}## is a topology on ##\hat{\mathbb{C}}##.
9. b) ##(\hat{\mathbb{C}},\hat{\mathcal{T}})## is Hausdorff.
9. c) ##(\hat{\mathbb{C}},\hat{\mathcal{T}})## is compact.
(by @fresh_42 )

10. (solved by @lpetrich )
10. a) Show that ##D_4=\langle r,s\,|\,r^2=s^2=rsrs=1\rangle## is the smallest non-cyclic group.
10. b) Show that the converse of Lagrange's theorem is false, i.e. that there is a finite group with ##n## elements which has no subgroup to one of the divisors of ##n\,.##
10. c) Give an example of a non-Abelian finite and a non-Abelian infinite group.
10. d) Show that ##A_5## is simple, i.e. has only trivial normal subgroups.
(by @fresh_42 )

11. (solved by @lpetrich ; @Math_QED ) Calculate $$
\int_{-\infty}^{+\infty}\dfrac{4}{x^2-x+1}\,dx
$$
(by @fresh_42 )

H 12. Let [itex](x_n)[/itex] be a sequence of positive real numbers such that [itex]x_{n+1}\geq\dfrac{x_n+x_{n+2}}{2}[/itex] for each [itex]n[/itex]. Show that the sequence is (weakly) increasing, i.e. [itex]x_n\leq x_{n+1}[/itex] for each [itex]n[/itex]. (by @Infrared )

H 13. Let [itex]p(x)[/itex] be a non-constant real polynomial. Suppose that there exists a real number [itex]a[/itex] such that [itex]p(a)\neq 0[/itex] and [itex]p'(a)=p''(a)=0\,.[/itex] Show that not all of the roots of [itex]p[/itex] are real. (by @Infrared )

H 14. Find the area enclosed by the curve ##r^2 = a^2\cos 2\theta\,##. (by @QuantumQuest )

H 15. (You may use wolframalpha.com for calculations) One tiny night-active and long-living beetle decided one night to climb a sequoia. The tree was exactly ##100\, m## high at this time. Every night the beetle made a distance of ##10\, cm##. The tree grew every day evenly ##20\, cm## along its entire length.
Did the beetle eventually reach the top of the tree? And if so, how many nights will he need at least? (by @fresh_42 )

H 16. Show that ##\lim_{n \to \infty} \sqrt[n]{p_1a_1^n + p_2a_2^n + \cdots + p_ka_k^n} = max \{a_1, a_2, \cdots ,a_k\}## where ##p_1, p_2, \cdots, p_k \gt 0## and ##a_1, a_2, \cdots, a_k \geq 0##.
(by @QuantumQuest )

H 17. Show that the sequence ##(a_n)## with ##a_1 = \sqrt[]{b}##, ##a_{n+1} = \sqrt[]{a_n + b}## for ##n = 1, 2, 3, \ldots## converges to the positive root of the equation ##x^2 - x - b = 0##. (by @QuantumQuest )
 
Last edited:
  • Like
Likes YoungPhysicist, Math_QED, pinball1970 and 2 others

Answers and Replies

  • #2
984
173
This one is a geometric series, ##A = \sum_{n=0}^\infty a^n##, for a = 2/(2+3i).

One can find ##A## by finding its finite counterpart, ##A(m) = \sum_{n=0}^m a^n##, and then taking m -> oo. That finite counterpart's value can be found from
$$(1 - a)A(m)= \sum_{n=0}^m a^n - a \sum_{n=0}^m a^n = \sum_{n=0}^m a^n - \sum_{n=1}^{m+1} a^n = 1 - a^{m+1}$$
All the terms cancel except for the first sum's first term and the second sum's last term, giving us
$$A(m) = \frac{1 - a^{m+1}}{1 - a}$$
Taking the limit ##m \to \infty##, the sum will be finite only if |a| < 1, and if that is the case, then
$$A = \frac{1}{1 - a} $$
Since in our current problem, ##|a| = 2/\sqrt{13} < 1##, the series sum will be finite, and its value is
$$A = \frac{1}{1 - \frac{2}{2+3i}} = \frac{2+3i}{3i} = 1 - 2i/3$$
 
Last edited:
  • #3
984
173
Here we must find ##R = \sum_{n=0}^{\infty} (2\sqrt{n} - 4\sqrt{n+1} + 2\sqrt{n+2})##. For the solution, we can split this sum up into three sums, and then rearrange those sums. That procedure can be justified for finite sums, though not for infinite ones, because those infinite ones may diverge. So I consider the finite version
$$R(m) = \sum_{n=0}^m (2\sqrt{n} - 4\sqrt{n+1} + 2\sqrt{n+2})$$
Splitting up the sum gives
$$R(m) = \sum_{n=0}^m 2\sqrt{n} - \sum_{n=0}^m 4\sqrt{n+1} + \sum_{n=0}^m 2\sqrt{n+2} = \sum_{n=0}^m 2\sqrt{n} - \sum_{n=1}^{m+1} 4\sqrt{n} + \sum_{n=2}^{m+2} 2\sqrt{n}$$
Here also, all but the first and last terms cancel, and I find
$$R(m) = (0 + 2 - 4) + (-4\sqrt{m+1} + 2\sqrt{m+1} + 2\sqrt{m+2}) = - 2 + 2(\sqrt{m+2} - \sqrt{m+1})$$
Taking the limit of ##m \to \infty##, ##\sqrt{m+2} - \sqrt{m+1} \to 1/(2m) \to 0##, and the sum that we seek is ##R = -2##.
 
Last edited:
  • #4
984
173
We must find
$$S = \sum_{n=3}^\infty \frac{8n}{(n^2-1)^2}$$
This seems like a rather difficult sum, but it can be solved by splitting the summand:
$$\frac{8n}{(n^2-1)^2} = 2 \left( \frac{1}{(n-1)^2} - \frac{1}{(n+1)^2} \right)$$
Taking a finite sum as before,
$$S(m) = \sum_{n=3}^m \frac{8n}{(n^2-1)^2} = \sum_{n=3}^m 2 \left( \frac{1}{(n-1)^2} - \frac{1}{(n+1)^2} \right) = 2 \left( \sum_{n=3}^m \frac{1}{(n-1)^2} - \sum_{n=3}^m \frac{1}{(n+1)^2}\right)$$
But here, one can take infinite limits of the split sums, and for ##m \to \infty##,
$$S = 2 \left( \sum_{n=3}^\infty \frac{1}{(n-1)^2} - \sum_{n=3}^\infty \frac{1}{(n+1)^2}\right)$$
Adjusting the summation limits and taking the difference,
$$S = 2 \left( \sum_{n=2}^\infty \frac{1}{n^2} - \sum_{n=4}^\infty \frac{1}{n^2}\right) = 2 \sum_{n=2}^3 \frac{1}{n^2} = 2 \left( \frac14 + \frac19 \right) = \frac{13}{18}$$
Thus, the sum that we seek is ##S = 13/18##.
 
  • #5
984
173
We must find
$$L = \lim_{x \to 0} \frac{ \cos(x^2) - \sqrt{1 + x^3} }{x^3}$$
Both the numerator and the denominator are zero at the limit point ##x = 0##, and there is no way to simplify this expression. So we must use L'Hôpital's rule. The numerator and denominator separately are
$$ \left\{ \cos(x^2) - \sqrt{1 + x^3} , x^3 \right\} $$
It is evident that both parts are zero for x = 0. Following L'Hôpital's rule, I take the derivative of both parts with respect to x:
$$ \left\{ -2x\sin(x^2) - \frac{3x^2}{2\sqrt{1 + x^3}} , 3x^2 \right\} $$
Here also, both parts are zero for x = 0. I then use L'Hôpital's rule again, taking another derivative:
$$ \left\{ -4x^2\cos(x^2) - 2\sin(x^2) + \frac{9x^4}{4(1 + x^3)^{3/2}} - \frac{3x}{\sqrt{1 + x^3}} , 6x \right\} $$
Here also, both parts are zero for x = 0. I then use L'Hôpital's rule yet again.
$$ \left\{ -12x\cos(x^2) + 8x^3\sin(x^2) - \frac{81x^4}{8(1 + x^3)^{5/2}} + \frac{27x^4}{2(1 + x^3)^{3/2}} - \frac{3}{\sqrt{1 + x^3}} , 6 \right\} $$
This time, both parts are nonzero for x = 0. Substituting that value gives
$$ \{ -3, 6 \} $$
giving us ##L = (-3)/6 = -1/2##.

This value can be found in a more hand-wavy fashion, by doing series expansions:
$$ \cos(x^2) = 1 + O(x^4) , \sqrt{1 + x^3} = 1 + \frac12 x^3 + O(x^6)$$
Thus,
$$L = \lim_{x \to 0} \frac{ (1 + O(x^4)) - (1 + \frac12 x^3 + O(x^6))}{x^3} = \lim_{x \to 0} \frac{ - \frac12 x^3 + O(x^4)}{x^3} = \lim_{x \to 0} \left( - \frac12 + O(x) \right) = - \frac12$$
Also giving -1/2 for the value that we seek.
 
  • #6
984
173
We must find
$$I = \int_{-\infty}^{+\infty} \frac{4}{x^2 - x + 1} dx$$
As a first step, I notice that x appears only in the integrand's denominator. It appears in a quadratic polynomial there, and this suggests completing the square: ##x^2 - x + 1 = (x - \frac12)^2 + \frac34##. This suggests that we ought to shift the variable of integration: ##x \to x + 1/2##:
$$I = \int_{-\infty}^{+\infty} \frac{4}{(x - \frac12)^2 + \frac34} dx = \int_{-\infty}^{+\infty} \frac{4}{x^2 + \frac34} dx$$
The bounds of integration are unaffected by the change of variables.

For the next step, we get the denominator into form ##x^2 + 1##, and we do that with ##x \to (\sqrt{3}/2) x##. This can readily be integrated:
$$I = \int_{-\infty}^{+\infty} \frac{4}{x^2 + \frac34} dx = \int_{-\infty}^{+\infty} \frac{8}{\sqrt{3}} \frac{1}{x^2 + 1} dx = \frac{8}{\sqrt{3}} \arctan x |_{x = -\infty}^{+\infty} = \frac{8\pi}{\sqrt{3}}$$
Here also, the bounds of integration are unaffected by the change of variables.

Thus, we get the value that we seek:
$$I = \frac{8\pi}{\sqrt{3}}$$
 
  • #7
Math_QED
Science Advisor
Homework Helper
2019 Award
1,490
581
What a coincidence. Yesterday I was trying to solve (2b) for my measure theory course. Seems like I have more motivation to somve it now :)
 
  • #8
984
173
This problem can be divided into three parts: finding the order of ##D_4 = <r, s | r^2 = s^2 = rsrs = 1>##, finding all groups with smaller orders, and showing that they are all cyclic.

For the first part, we find all the elements of D4. We start with 1, r, and s, multiply them, add any additional elements to this list, and repeat until we find no more elements. As we multiply, we use the presentation rules to simplify the results. Here is the first iteration:
  • (r) (r) = rr = 1
  • (r) (s) = rs
  • (s) (r) = sr = rr sr ss = r rsrs s = rs
  • (s) (s) = ss = 1
This gives us an additional element, rs. The next iteration has
  • (r) (rs) = r rs = rr s = s
  • (s) (rs) = s rs = rr srs = r
  • (rs) (r) = rs r = rsr ss = rsrs s = s
  • (rs) (s) = rs s = r ss = r
  • (rs) (rs) = rsrs = 1
This iteration gives no additional elements, and thus, the complete set of elements of D4 is {1, r, s, rs}. Note also that D4 is abelian.

So we must now find all groups with fewer than four elements.

I will do that with the help of the Latin-square property of the group operation table.

Proof of the Latin-square property. Each row and each column contains all of the elements, with each one present only once in each individual row and column. For row element r and column element a, we find table entry b = ra. So each a has at least one b corresponding to it. But a = r-1b, so that each b has at least one a corresponding to it. This means that there is a bijection between the a's and the b's, and thus for a finite group, at least, each row contains all the group elements, repeated exactly once. This proof can be adapted for columns, with the same result for them.

The converse is not necessarily true, however, and I must check on whether or not I have found a group.

For order 1, a group contains only the identity element, making it the identity group. This group is cyclic: Z1.

For order 2, we use elements 1 and r, and start with this operation table:
$$ \begin{matrix} 1 & r \\ r & ? \end{matrix} $$
From the Latin-square property, the missing entry is obviously 1:
$$ \begin{matrix} 1 & r \\ r & 1 \end{matrix} $$
Thus, r2 = 1 and this gives us the cyclic group Z2.

For order 3, we use elements 1, r, and s, and start with this operation table:
$$ \begin{matrix} 1 & r & s \\ r & ? & ? \\ s & ? & ? \end{matrix} $$
For entries 2,3 and 3,2, the elements cannot be r or s, and they are thus 1, Filling it in:
$$ \begin{matrix} 1 & r & s \\ r & ? & 1 \\ s & 1 & ? \end{matrix} $$
Entry 2,2 must thus be s and entry 3,3 r. This gives us the complete table:
$$ \begin{matrix} 1 & r & s \\ r & s & 1 \\ s & 1 & r \end{matrix} $$
Thus, r2 = s and r3 = 1, and this gives us the cyclic group Z3.

Thus, all the groups smaller than D4 are cyclic groups.

An alternate approach would be to use the theorem that all prime-order groups are cyclic.

Proof of that theorem: consider a cyclic subgroup generated by some element other than the identity. Its order must be greater than 1, and must evenly divide the group's order. By primeness, the only possible order that that subgroup can have is the group's order. Meaning that the group must be identical to that subgroup, and that it must therefore be cyclic.

The only orders less than 4 are 1, 2, and 3. Order 1 is for the identity group, Z1. Orders 2 and 3 are prime, meaning that their groups must be cyclic.
 
  • #9
what is ##\lambda## in problem 4?
 
  • #10
984
173
Here is a group for which the converse of Lagrange's theorem does not hold: A4, the alternating group of index 4, the group of all even permutations of 4 symbols. it has subgroups with orders 1, 2, 3, 4, and 12, but not 6.

I was able to verify that result with a brute-force calculation, by taking every nonempty subset of the elements of A4 and filling out a group from each one. But I have an alternative to that proof that I shall present here.

Here is an outline of the proof. If A4 has an order-6 subgroup, then that subgroup must be a normal one. If it is, then it must contain complete conjugacy classes of its parent group. But it is not possible for an order-6 subgroup to do so, therefore, A4 has no order-6 subgroups. I will prove as much as I can of each step.


An order-6 subgroup of A4 has index 2, and every index-2 subgroup of a group is normal. Proof: if a subgroup has index 2, that means that it has only two cosets, itself and the remainder of the group's elements. This choice of cosets is the only one possible for this subgroup. That means that both left and right cosets are this set of cosets, and this identity means that the subgroup is normal.


Every normal subgroup contains complete conjugacy classes of its parent group. Proof: a normal subgroup H of group G has the property that g.H.g-1 = H for every g in G. That is true by definition of every conjugacy class in G. Imagine what would happen if member a of class C was in H and b was not. Since both a and b are in C, there is some g in G such that g.a.g-1 = b. But from the definition of normal subgroup, g.a.g-1 must be in H for all g in G. Thus, C must either be a subset of H or else disjoint to it -- either all in or all out.


The next step is to find the sizes of the conjugacy classes of A4. That also can be done by brute force, but I will use an alternative approach. A4 is a subgroup of S4, the symmetric group of index 4, the group of all permutations of 4 symbols.

There is a theorem that states that all classes of the symmetric group are sets of elements that share the same lengths of permutation cycles. That means that the classes of S4 may be designated ##{1^4, 1^2 \cdot 2, 2^2, 1 \cdot 3, 4}##. The first one is the identity-element class (1234 only), the second one has elements like 1243, the third one elements like 1342, etc. They have sizes ##{1^4: 1, 1^2 \cdot 2: 6, 2^2: 3, 1 \cdot 3: 8, 4: 6}##, determined from ##n! / \prod_k (n_k)^{m_k} (m_k)!## for mk of each cycle length nk, totaling n.

The group A4 contains all the even permutations in S4. An even permutation is one that can be constructed from an even number of length-2 cycles, and likewise for an odd permutation. The even-odd distinction is called parity. A cycle with length n can be constructed from (n-1) length-2 cycles, and that means that the classes of S4 have parity ##{1^4: even, 1^2 \cdot 2: odd, 2^2: even, 1 \cdot 3: even, 4: odd}##.

Thus, A4 contains S4 classes ##{1^4, 2^2, 1 \cdot 3}##, with lengths 1, 3, 8. That last one looks impossible for A4, with order 12, but there is a theorem that some symmetric-group classes split into pairs of alternating-group classes with half their size. In particular, symmetric-group classes whose cycles all have distinct odd lengths. So ##1^4## does not split, ##2^2## does not split, but ##1 \cdot 3## does, into two classes with size 4.

In summary, A4 has this class content and sizes: ##{1^4: 1, 2^2: 3, 1 \cdot 3_1: 4, 1 \cdot 3_2: 4}##.


The final step is to try to find some combination of class sizes that makes 6, the missing subgroup order for A4. Every subgroup must contain the identity element, so we have 5 elements left over. Including class ##2^2## gives 2 left over, and neither of the ##1 \cdot 3## classes can fit into what remains. Including either of the two ##1 \cdot 3## classes gives 1 left over, with no room for either the ##2^2## class or the other ##1 \cdot 3## class.

Thus proving that A4 has no subgroups with size 6, thus making A4 a counterexample to the converse of Lagrange's theorem.
 
Last edited:
  • #11
984
173
I will select a nonabelian infinite group, and a nonabelian finite group that is a subgroup of the nonabelian infinite group. Proving the latter to be nonabelian proves the former to also be nonabelian.

For the nonabelian infinite group, I will use O(2), the set of all two-dimensional rotations and reflections. Its rotation elements R(θ) and reflection elements S(θ) for angle θ are
$$ R(\theta) = \begin{pmatrix} \cos\theta & - \sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} , \ S(\theta) = \begin{pmatrix} \cos\theta & \sin\theta \\ \sin\theta & - \cos\theta \end{pmatrix} $$

For the nonabelian finite group, I will use Dih(3), a subgroup of O(3). Its elements are {R(0), R(2π/3), R(4π/3), S(0), S(2π/3), S(4π/3)}. Select S(0) and S(2π/3) and multiply them in both directions:

S(0).S(2π/3) = R(4π/3)
S(2π/3).S(0) = R(2π/3)

The two R's are clearly unequal, therefore Dih(3) is nonabelian and also O(2).
 
  • #12
12,877
9,511
what is ##\lambda## in problem 4?
It indicates Lebesgue integration. But ##d\lambda(x,y) = dx\,dy## works as well here.
 
  • #13
984
173
The group A5 is the group of all even permutations of 5 symbols.

I will show that A5 is simple by using some results from my solution for 10b. In particular, every normal subgroup of a group must include complete conjugacy classes of that group, including the identity-element class.

We start with the classes of S5, the group of all permutations of 5 symbols. With their parities and sizes, the are:
$${1^5: even\ 1, 1^3 \cdot 2: odd\ 10, 1 \cdot 2^2: even\ 15, 1^2 \cdot 3: even\ 20, 2 \cdot 3: odd\ 20, 1 \cdot 4: odd\ 30, 5: even\ 24}$$
Selecting out the even ones for A4 and splitting the ones that get split, I find
$${1^5: 1, 1 \cdot 2^2: 15, 1^2 \cdot 3: 20, 5_1: 12, 5_2: 12}$$
I then used Mathematica to find the sums of all selections of the class sizes that include the identity class. They are {1, 13, 16, 21, 25, 28, 33, 36, 40, 45, 48, 60}. Of these, only 1 and 60 evenly divide the order of A5, 60, and that means that A5 has no nontrivial normal subgroups. Thus, A5 is simple.
 
  • #14
12,877
9,511
What a coincidence. Yesterday I was trying to solve (2b) for my measure theory course. Seems like I have more motivation to somve it now :)
The trick is to include in your Ansatz what you will finally need.
 
  • #15
12,877
9,511
This problem can be divided into three parts: finding the order of ##D_4 = <r, s | r^2 = s^2 = rsrs = 1>##, finding all groups with smaller orders, and showing that they are all cyclic.

For the first part, we find all the elements of D4. We start with 1, r, and s, multiply them, add any additional elements to this list, and repeat until we find no more elements. As we multiply, we use the presentation rules to simplify the results. Here is the first iteration:
  • (r) (r) = rr = 1
  • (r) (s) = rs
  • (s) (r) = sr = rr sr ss = r rsrs s = rs
  • (s) (s) = ss = 1
This gives us an additional element, rs. The next iteration has
  • (r) (rs) = r rs = rr s = s
  • (s) (rs) = s rs = rr srs = r
  • (rs) (r) = rs r = rsr ss = rsrs s = s
  • (rs) (s) = rs s = r ss = r
  • (rs) (rs) = rsrs = 1
This iteration gives no additional elements, and thus, the complete set of elements of D4 is {1, r, s, rs}. Note also that D4 is abelian.

So we must now find all groups with fewer than four elements.

I will do that with the help of the Latin-square property of the group operation table.

Proof of the Latin-square property. Each row and each column contains all of the elements, with each one present only once in each individual row and column. For row element r and column element a, we find table entry b = ra. So each a has at least one b corresponding to it. But a = r-1b, so that each b has at least one a corresponding to it. This means that there is a bijection between the a's and the b's, and thus for a finite group, at least, each row contains all the group elements, repeated exactly once. This proof can be adapted for columns, with the same result for them.

The converse is not necessarily true, however, and I must check on whether or not I have found a group.

For order 1, a group contains only the identity element, making it the identity group. This group is cyclic: Z1.

For order 2, we use elements 1 and r, and start with this operation table:
$$ \begin{matrix} 1 & r \\ r & ? \end{matrix} $$
From the Latin-square property, the missing entry is obviously 1:
$$ \begin{matrix} 1 & r \\ r & 1 \end{matrix} $$
Thus, r2 = 1 and this gives us the cyclic group Z2.

For order 3, we use elements 1, r, and s, and start with this operation table:
$$ \begin{matrix} 1 & r & s \\ r & ? & ? \\ s & ? & ? \end{matrix} $$
For entries 2,3 and 3,2, the elements cannot be r or s, and they are thus 1, Filling it in:
$$ \begin{matrix} 1 & r & s \\ r & ? & 1 \\ s & 1 & ? \end{matrix} $$
Entry 2,2 must thus be s and entry 3,3 r. This gives us the complete table:
$$ \begin{matrix} 1 & r & s \\ r & s & 1 \\ s & 1 & r \end{matrix} $$
Thus, r2 = s and r3 = 1, and this gives us the cyclic group Z3.

Thus, all the groups smaller than D4 are cyclic groups.

An alternate approach would be to use the theorem that all prime-order groups are cyclic.

Proof of that theorem: consider a cyclic subgroup generated by some element other than the identity. Its order must be greater than 1, and must evenly divide the group's order. By primeness, the only possible order that that subgroup can have is the group's order. Meaning that the group must be identical to that subgroup, and that it must therefore be cyclic.

The only orders less than 4 are 1, 2, and 3. Order 1 is for the identity group, Z1. Orders 2 and 3 are prime, meaning that their groups must be cyclic.
Right. Except, that the argument is missing why ##D_4## is not cyclic. The smaller ones are cyclic, because you can name them and they are unique, no other way to define a group structure on them.
 
  • #16
12,877
9,511
Here is a group for which the converse of Lagrange's theorem does not hold: A4, the alternating group of index 4, the group of all even permutations of 4 symbols. it has subgroups with orders 1, 2, 3, 4, and 12, but not 6.

I was able to verify that result with a brute-force calculation, by taking every nonempty subset of the elements of A4 and filling out a group from each one. But I have an alternative to that proof that I shall present here.

Here is an outline of the proof. If A4 has an order-6 subgroup, then that subgroup must be a normal one. If it is, then it must contain complete conjugacy classes of its parent group. But it is not possible for an order-6 subgroup to do so, therefore, A4 has no order-6 subgroups. I will prove as much as I can of each step.


An order-6 subgroup of A4 has index 2, and every index-2 subgroup of a group is normal. Proof: if a subgroup has index 2, that means that it has only two cosets, itself and the remainder of the group's elements. This choice of cosets is the only one possible for this subgroup. That means that both left and right cosets are this set of cosets, and this identity means that the subgroup is normal.


Every normal subgroup contains complete conjugacy classes of its parent group. Proof: a normal subgroup H of group G has the property that g.H.g-1 = H for every g in G. That is true by definition of every conjugacy class in G. Imagine what would happen if member a of class C was in H and b was not. Since both a and b are in C, there is some g in G such that g.a.g-1 = b. But from the definition of normal subgroup, g.a.g-1 must be in H for all g in G. Thus, C must either be a subset of H or else disjoint to it -- either all in or all out.


The next step is to find the sizes of the conjugacy classes of A4. That also can be done by brute force, but I will use an alternative approach. A4 is a subgroup of S4, the symmetric group of index 4, the group of all permutations of 4 symbols.

There is a theorem that states that all classes of the symmetric group are sets of elements that share the same lengths of permutation cycles. That means that the classes of S4 may be designated ##{1^4, 1^2 \cdot 2, 2^2, 1 \cdot 3, 4}##. The first one is the identity-element class (1234 only), the second one has elements like 1243, the third one elements like 1342, etc. They have sizes ##{1^4: 1, 1^2 \cdot 2: 6, 2^2: 3, 1 \cdot 3: 8, 4: 6}##, determined from ##n! / \prod_k (n_k)^{m_k} (m_k)!## for mk of each cycle length nk, totaling n.

The group A4 contains all the even permutations in S4. An even permutation is one that can be constructed from an even number of length-2 cycles, and likewise for an odd permutation. The even-odd distinction is called parity. A cycle with length n can be constructed from (n-1) length-2 cycles, and that means that the classes of S4 have parity ##{1^4: even, 1^2 \cdot 2: odd, 2^2: even, 1 \cdot 3: even, 4: odd}##.

Thus, A4 contains S4 classes ##{1^4, 2^2, 1 \cdot 3}##, with lengths 1, 3, 8. That last one looks impossible for A4, with order 12, but there is a theorem that some symmetric-group classes split into pairs of alternating-group classes with half their size. In particular, symmetric-group classes whose cycles all have distinct odd lengths. So ##1^4## does not split, ##2^2## does not split, but ##1 \cdot 3## does, into two classes with size 4.

In summary, A4 has this class content and sizes: ##{1^4: 1, 2^2: 3, 1 \cdot 3_1: 4, 1 \cdot 3_2: 4}##.


The final step is to try to find some combination of class sizes that makes 6, the missing subgroup order for A4. Every subgroup must contain the identity element, so we have 5 elements left over. Including class ##2^2## gives 2 left over, and neither of the ##1 \cdot 3## classes can fit into what remains. Including either of the two ##1 \cdot 3## classes gives 1 left over, with no room for either the ##2^2## class or the other ##1 \cdot 3## class.

Thus proving that A4 has no subgroups with size 6, thus making A4 a counterexample to the converse of Lagrange's theorem.
A lot shorter would have been: ##(123)\in A_4## and conjugation with transpositions shows, that all ##8## ##3-##cycles can be generated.
 
  • #17
12,877
9,511
I will select a nonabelian infinite group, and a nonabelian finite group that is a subgroup of the nonabelian infinite group. Proving the latter to be nonabelian proves the former to also be nonabelian.

For the nonabelian infinite group, I will use O(2), the set of all two-dimensional rotations and reflections. Its rotation elements R(θ) and reflection elements S(θ) for angle θ are
$$ R(\theta) = \begin{pmatrix} \cos\theta & - \sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} , \ S(\theta) = \begin{pmatrix} \cos\theta & \sin\theta \\ \sin\theta & - \cos\theta \end{pmatrix} $$

For the nonabelian finite group, I will use Dih(3), a subgroup of O(3). Its elements are {R(0), R(2π/3), R(4π/3), S(0), S(2π/3), S(4π/3)}. Select S(0) and S(2π/3) and multiply them in both directions:

S(0).S(2π/3) = R(4π/3)
S(2π/3).S(0) = R(2π/3)

The two R's are clearly unequal, therefore Dih(3) is nonabelian and also O(2).
Yes. ##Dih(3)=D_6=S_3## is the smallest of those groups. In the infinite case, ##GL_n(\mathbb{R}## would have been easier, but the orthogonal group works as well.
 
  • #18
12,877
9,511
The group A5 is the group of all even permutations of 5 symbols.

I will show that A5 is simple by using some results from my solution for 10b. In particular, every normal subgroup of a group must include complete conjugacy classes of that group, including the identity-element class.

We start with the classes of S5, the group of all permutations of 5 symbols. With their parities and sizes, the are:
$${1^5: even\ 1, 1^3 \cdot 2: odd\ 10, 1 \cdot 2^2: even\ 15, 1^2 \cdot 3: even\ 20, 2 \cdot 3: odd\ 20, 1 \cdot 4: odd\ 30, 5: even\ 24}$$
Selecting out the even ones for A4 and splitting the ones that get split, I find
$${1^5: 1, 1 \cdot 2^2: 15, 1^2 \cdot 3: 20, 5_1: 12, 5_2: 12}$$
I then used Mathematica to find the sums of all selections of the class sizes that include the identity class. They are {1, 13, 16, 21, 25, 28, 33, 36, 40, 45, 48, 60}. Of these, only 1 and 60 evenly divide the order of A5, 60, and that means that A5 has no nontrivial normal subgroups. Thus, A5 is simple.
I don't understand your notation ##{1^5: even\ 1, 1^3 \cdot 2: odd\ 10, 1 \cdot 2^2: even\ 15, 1^2 \cdot 3: even\ 20, 2 \cdot 3: odd\ 20, 1 \cdot 4: odd\ 30, 5: even\ 24}##

Yes, parts of 10.b. can be used here, but I don't really understand what you've done. The trick is to look at ##3-##cycles again, and possibly find a proof, which in general will work for ##n>5## as well. Maybe you can explain your abbreviations and especially what those classes are which you are talking about.
 
  • #19
984
173
Right. Except, that the argument is missing why ##D_4## is not cyclic. The smaller ones are cyclic, because you can name them and they are unique, no other way to define a group structure on them.
I'll fill in the gap.
In my previous post on problem 10a, I had found that D4 has elements {1, r, s, rs} where r2 = s2 = (rs)2 = 1 and the group is abelian.

Every non-identity element of D4 has order 2, while if D4 was cyclic, it would have two elements with order 4, and one element with order 2. Therefore, D4 is not cyclic.

Also, D4 has two generators, r and s here, while a cyclic group has only one generator. Each generator of D4 generates only two elements, 1 and itself, and not all four elements.
 
  • #20
984
173
I don't understand your notation ##{1^5: even\ 1, 1^3 \cdot 2: odd\ 10, 1 \cdot 2^2: even\ 15, 1^2 \cdot 3: even\ 20, 2 \cdot 3: odd\ 20, 1 \cdot 4: odd\ 30, 5: even\ 24}##
My notation is, for each conjugacy class, (cycle content): (parity) (number of elements)
Yes, parts of 10.b. can be used here, but I don't really understand what you've done. The trick is to look at ##3-##cycles again, and possibly find a proof, which in general will work for ##n>5## as well. Maybe you can explain your abbreviations and especially what those classes are which you are talking about.
The elements of symmetric and alternating groups are permutations, and permutations can be expressed as sets of disjoint cycles. Each cycle has a length, and every symmetric-group conjugacy class shares a set of cycle lengths. I abbreviate repeated lengths by taking a power: 111 = 13. Thus, for S3, the conjugacy classes and their cycle lengths are
  • 111 = 13 ... 123 = (1)(2)(3)
  • 12 = 1.2 .., 132 = (1)(32) ... 321 = (2)(31) ... 213 = (3)(21)
  • 3 = 3 ... 231 = (231) ... 312 = (321)
where for cycle (i1 i2 ... in), location i1 gets value i2, location i2 gets value i3, ..., location in gets value i1.
 
  • #21
Math_QED
Science Advisor
Homework Helper
2019 Award
1,490
581
The trick is to include in your Ansatz what you will finally need.
Yeah, I just found the solution. The proof is actually a one-liner (if you ommit the trivial steps).
 
  • #22
12,877
9,511
My notation is, for each conjugacy class, (cycle content): (parity) (number of elements)

The elements of symmetric and alternating groups are permutations, and permutations can be expressed as sets of disjoint cycles. Each cycle has a length, and every symmetric-group conjugacy class shares a set of cycle lengths. I abbreviate repeated lengths by taking a power: 111 = 13. Thus, for S3, the conjugacy classes and their cycle lengths are
  • 111 = 13 ... 123 = (1)(2)(3)
  • 12 = 1.2 .., 132 = (1)(32) ... 321 = (2)(31) ... 213 = (3)(21)
  • 3 = 3 ... 231 = (231) ... 312 = (321)
where for cycle (i1 i2 ... in), location i1 gets value i2, location i2 gets value i3, ..., location in gets value i1.
This is too cryptic for me. Again:
  • How are the conjugacy classes defined? Conjugation of what by what?
  • What is a cycle content?
  • Number of elements of what? Elements in a cycle, permutation, conjugacy class? What?
  • "... and every symmetric-group conjugacy class shares a set of cycle lengths"
    I have no idea what you mean by sharing, and what the set of lengths should be? Conjugation can change a length, so what is it you are talking about?
  • And why do you consider ##S_5## at all? It is irrelevant and confusing, especially as you do not feel the need to define what you are inventing.
 
  • #23
12,877
9,511
Yeah, I just found the solution. The proof is actually a one-liner (if you ommit the trivial steps).
I have 15 with the trivial steps, and as ##\sigma-##algebras aren't an everyday business on PF, a few more than just the definition of the one needed might be a good idea. :wink:
 
  • #24
Math_QED
Science Advisor
Homework Helper
2019 Award
1,490
581
I have 15 with the trivial steps, and as ##\sigma-##algebras aren't an everyday business on PF, a few more than just the definition of the one needed might be a good idea. :wink:
Sure haha, but I have to wait to post a solution to till half October anyway :rolleyes:. I also found (a), but maybe I cheated a little because my textbook gave as example the algebra that set generates (and then the sigma algebra comes with an educated guess).
 
  • #25
984
173
This is too cryptic for me. Again:
  • How are the conjugacy classes defined? Conjugation of what by what?
  • What is a cycle content?
  • Number of elements of what? Elements in a cycle, permutation, conjugacy class? What?
  • "... and every symmetric-group conjugacy class shares a set of cycle lengths"
    I have no idea what you mean by sharing, and what the set of lengths should be? Conjugation can change a length, so what is it you are talking about?
  • And why do you consider ##S_5## at all? It is irrelevant and confusing, especially as you do not feel the need to define what you are inventing.
The conjugacy classes are defined the usual way in group theory: Conjugacy class - Wikipedia. For a group G and element x in it, a conjugacy class is the set of all values of g.x.g-1 for all g in G.

The cycle content is the set of lengths of cycles in it.

The number of elements is for the conjugacy class.

Sharing a set of cycle lengths means all the elements having the same set of cycle lengths. There is a theorem about permutations that conjugation of a permutation does not change its cycle lengths. Symmetric group - Wikipedia and Alternating group - Wikipedia both discuss the contents of the groups' conjugacy classes. For the symmetric group, "two elements of Sn are conjugate in Sn if and only if they consist of the same number of disjoint cycles of the same lengths."

I brought in S5 because I wanted to derive the sizes of the classes of A5. An is Simple contains my argument about class sizes and normal subgroups near the bottom of the second page.
 

Related Threads on Math Challenge - October 2018

Replies
42
Views
6K
Replies
175
Views
12K
Replies
67
Views
6K
Replies
63
Views
5K
Replies
82
Views
7K
Replies
16
Views
3K
Replies
62
Views
5K
Replies
57
Views
5K
Replies
28
Views
3K
Replies
20
Views
3K
Top