Challenge Micromass' big July Challenge

[andrewkirk]

Well, I have waded through the mire of messy integration to solve the mean for problem four.

WARNING: it is not pretty. Avert your eyes if you are easily distressed.

To calculate the mean we want to use Cartesian rather than Polar integration so that we can include the corners of the square $[-1,1]\times[-1,1]$. Fortunately, we don't need to calculate the cdf of L in Cartesian coordinates, which might be very messy. Instead we calculate the mean directly using Cartesian integration over the first quadrant, using only the pdfs of X and Y.

\begin{align*}
E[L]&=4\int_0^1\int_0^1 f_X{x}f_Y(y)\sqrt{x^2+y^2}\,dy\,dx\\
&=4\int_0^1\int_0^1 (1-x)(1-y)\sqrt{x^2+y^2}\,dy\,dx\\
&=4\int_0^1(1-x)\left[-\frac13 (x^2+y^2)^\frac32+ \frac12\left(y\sqrt{x^2+y^2}+x^2\log\left(\sqrt{x^2+y^2}+y\right)\right)\right]_0^1\,dx\\
%
&=4\int_0^1(1-x)\Bigg(\left(-\frac13 (x^2+1^2)^\frac32+ \frac12\left(1\sqrt{x^2+1^2}+x^2\log\left(\sqrt{x^2+1^2}+1\right)\right)\right)\\
&\quad\quad\quad-\left(
-\frac13 (x^2+0)^\frac32+ \frac12\left(0+x^2\log\left(\sqrt{x^2+0}+0\right)\right)
\right)
\Bigg)\,dx\\
%
&=4\int_0^1(1-x)\Bigg(-\frac13 (x^2+1)^\frac32+ \frac12\sqrt{x^2+1}+\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)\\
&\quad\quad\quad+\frac13 x^3-\frac12 x^2\log{x}\Bigg)dx\\
%
&=
4\left[\frac1{12}x^4-\frac1{15}x^5\right]_0^1+
%
4\int_0^1\Bigg(+\frac13 x(x^2+1)^\frac32 - \frac12 x\sqrt{x^2+1}\\
&\quad\quad\quad-\frac13 (x^2+1)^\frac32+\frac12 \sqrt{x^2+1}
+(1-x)\left(\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)
-\frac12 x^2\log{x}\right)\Bigg)dx\\
%
&=\frac13-\frac4{15}
+4\left[
\frac1{15}(x^2+1)^\frac52
-\frac16(x^2+1)^\frac32
\right]_0^1\\
&\quad\quad\quad+4\int_0^1\Bigg(
-\frac13 (x^2+1)^\frac32+\frac12 \sqrt{x^2+1}
+(1-x)\left(\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)
-\frac12 x^2\log{x}\right)\Bigg)dx\\
%
&=\frac1{15}+\frac1{15}\cdot 16\sqrt2-\frac16 8\sqrt2-\frac4{15}+\frac23\\
&\quad\quad\quad+4\int_0^1\Bigg(
-\frac13 (x^2+1)^\frac32+\frac12 \sqrt{x^2+1}
+(1-x)\left(\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)
-\frac12 x^2\log{x}\right)\Bigg)dx\\
%
&=0.090
+4\int_0^1\Bigg(
-\frac13 (x^2+1)^\frac32+\frac12 \sqrt{x^2+1}
+\frac12 x^2\log\left(1+\sqrt{x^2+1}\right)
-\frac12 x^2\log{x}\\
&\quad\quad\quad-\frac12 x^3\log\left(1+\sqrt{x^2+1}\right)
+\frac12 x^3\log{x}
\Bigg)dx
%
\end{align*}

\begin{align*}
&=0.090
-\frac13\cdot\frac18\left[x\sqrt{x^2+1}(2x^2+5)+3\sinh^{-1}x\right]_0^1\\
&\quad\quad\quad+\frac12\cdot\frac12\left[x\sqrt{x^2+1}+\sinh^{-1}x\right]_0^1\\
&\quad\quad\quad+\frac12\cdot\frac1{18}\left[
-2x^3+3x\sqrt{x^2+1}+6x^3\log(1+\sqrt{x^2+1})-3\sinh^{-1} x\right]_0^1\\
&\quad\quad\quad-\frac12\cdot\frac19\left[
x^3(3\log x-1)\right]_0^1\\
&\quad\quad\quad-\frac12\cdot\frac1{48}\left[
-3x^4+4x^2\sqrt{x^2+1}-8\sqrt{x^2+1}+12x^4\log(1+\sqrt{x^2+1})
\right]_0^1\\
&\quad\quad\quad+\frac12\cdot\frac1{16}\left[x^4(4\log x - 1)\right]_0^1
\end{align*}
The alert reader will have noticed that in evaluating the fourth and sixth definite integrals here it appears I will have to perform an illegal operation in evaluating \log 0. However, we can validate such a step by observing that the formulas actually being evaluated are (x^4\log x) and (x^3\log x) in the fourth and six items respectively. We can show by l'Hopital's rule that the limit of these formulas as x goes to zero from above is 0. Hence we can use that, since it is only the limit, not the value of the antiderivative at 0, that determines the value of the definite integral.

Let us continue:
\begin{align*}
&=0.090
-\frac1{24}\left[1\cdot\sqrt{1+1}(2+5)+3\sinh^{-1}1-(0)\right]
+\frac14\left[\sqrt{2}+\sinh^{-1}1-(0)\right]\\
&\quad\quad\quad+\frac1{36}\left[-2+3\sqrt{2}+6\log(1+\sqrt{2})-3\sinh^{-1} 1-(0)\right]\\
&\quad\quad\quad-\frac1{18}\left[1(3\cdot 0-1)-(0)\right]\\
&\quad\quad\quad-\frac1{96}\left[
-3+4\sqrt{2}-8\sqrt{2}+12\log(1+\sqrt{2})-(-8)\right]\\
&\quad\quad\quad+\frac1{32}\left[1\cdot (4\cdot 0 - 1)-(0)\right]\\
%
&=0.52
\end{align*}
which matches the value calculated earlier by numerical integration. What a relief!

 

[mfb]

The calculation is much shorter if you use polar coordinates and make the radius depend on the angle.

 

[PeroK]

The inner sum should give the probability that people have birthdays on exactly d (specified) days, right? Why don't you directly extend it to 365 and consider that only? We don't need the double sum.
$$\sum_{j=1}^{d}(-1)^{j+1} \binom{d}{j} \left(\frac j d \right)^n$$
For d=365 and n=2016, it gives 0.230987.

That's the inclusion/exclusion I was looking for earlier.

I missed that!

 

[haruspex]

Problem 1.
(I assume it means average distance between two points, not two numbers.)
The obvious approach is a quadruple integral, $\int\int\int\int\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$. The first integral can be handled with a tan substitution, leading to integral of sec³, with a standard but messy result, or a sinh substitution, leading to a sinh^-1 term. Either way, the second integral looks very nasty.

We can do better by noting that lines in which the endpoints differ by a vector (x,y) have a relative frequency (1-x)(1-y). This leads to the double integral $\int\int(1-x)(1-y)\sqrt {x^2+y^2}.dxdy/\int\int(1-x)(1-y)dxdy=4\int\int(1-x)(1-y)\sqrt {x^2+y^2}.dxdy$.
Multiplying out, we get an xy term, an x term, a y term and a "1" term. The xy term can be integrated twice easily. The x and y terms can also be integrated twice, though it involves integrating sec⁵ (I think).
But for the "1" term we have the same horrendous second integral as before.

Any better ideas?

 

[mfb]

Go to polar coordinates for the "1" term.

 

[haruspex]

Go to polar coordinates for the "1" term.

Doh! I looked at that when I had the quadruple integral and it didn't help, but I didn't retry it with the simpler integral.
Thanks!

 

[rcgldr]

Following up on mfb's post for number 6, a similar formula I had from the early 1990's, for dropping n balls into a plinko like box, each ball with an equal probability of ending up in 1 of d slots (note a real plinko box (bean machine) would have a bell curve distribution, not a uniform distribution, this was being used as an analogy for comparing error rates at the bit level versus a block level on tape drives and hard drives).

correction - was (-1)^(j+1), corrected to (-1)^(j+d):

$\left( \sum_{j=1}^{d} (-1)^{j+d} \begin{pmatrix} d\\j\end{pmatrix} j^n \right) \ / \ (d^n)$

for d = 365, and n = 2016, the result is

~= 0.23098718155802874302697567890329631779588686618349968487

To explain this sum, note that there are $d^n$ total possible cases, each of n people can have one of d possible birthdays.

For all the birthdays to fall on a single day, there are ...
For all the birthdays to fall on exactly two days, there are ...
For all the birthdays to fall on exactly three days, there are ...
For all the birthdays to fall on exactly 365 days, there are

The probability of all the birthdays to fall on exactly 365 days = the number of cases for exactly 365 days divided by the total number of cases, $d^n$ .

 

[PeroK]

To explain this sum, note that there are $d^n$ total possible cases, each of n people can have one of d possible birthdays.

For all the birthdays to fall on a single day, there are
$\begin{pmatrix} d\\1\end{pmatrix} 1^n$ cases.

For all the birthdays to fall on exactly two days, there are
$\begin{pmatrix} d\\2\end{pmatrix} 2^n$ cases minus the number of single day cases.

For all the birthdays to fall on exactly three days, there are
$\begin{pmatrix} d\\3\end{pmatrix} 3^n$ cases minus the number of exactly two day cases.

For all the birthdays to fall on exactly 365 days, there are
$\begin{pmatrix} d\\365\end{pmatrix} 365^n$ cases minus the number of exactly 364 day cases.

I must confess, I don't see this argument. First, why is the final number the total number of cases minus the exactly 364 cases? What about all the 363, 362 etc cases? The same for the others: the number of exactly 3-day cases should be the total number of 3-day cases minus the number of exactly 2-days cases minus the number of exactly 1-day cases.

Second, that calculation for the number of 2-days cases (not exact) includes as separate 2-day cases day-1/day-2 and day-1/day-3, which counts the subcase of all day-1 twice.

 

[PeroK]

In fact, the probability that $n$ people have birthdays covering exactly any $x$ days is:

$$ \binom{d}{x} \sum_{j=1}^{x}(-1)^{j+x} \binom{x}{j} \left(\frac j d \right)^n$$

It's only when $x = d$ that the initial binomial term disappears.

Note also, a minor point, that it should be in general $(-1)^{j+x}$. It's only $(-1)^{j+1}$ when $x$ is odd.

 

[PeroK]

In fact, the probability that $n$ people have birthdays covering exactly any $x$ days is:

$$ \binom{d}{x} \sum_{j=1}^{x}(-1)^{j+x} \binom{x}{j} \left(\frac j d \right)^n$$

It's only when $x = d$ that the initial binomial term disappears.

Note also, a minor point, that it should be in general $(-1)^{j+x}$. It's only $(-1)^{j+1}$ when $x$ is odd.

Here's a counting argument that I think works:

Let $N_i$ be the number of ways that exactly any $i$ days can be birthdays:

$\binom{d}{2} 2^n = N_2 + 2\binom{d}{2}$

As all the $N_2$ cases are covered and every pair chosen generates $2$ cases where only 1 day is covered. Hence:

$N_2 = \binom{d}{2} (2^n - 2) = \binom{d}{2} \sum_{j=1}^{2} (-1)^{j+2} \binom{2}{j} j^n$

And:

$\binom{d}{3} 3^n = N_3 + \binom{d}{3}(3(2^n) - 3)$

All the $N_3$ cases are generated, plus for every triple there are 3 sets of $2^n$ cases where at most 2 days are covered, but this counts twice each of the three cases where only one day is covered. Hence:

$N_3 = \binom{d}{3}(3^n - 3(2^n) + 3)$

And, in general - or for the last day - we get the series of alternating inclusions and exclusions.

 

[rcgldr]

In fact, the probability that $n$ people have birthdays covering exactly any $x$ days is:

$$ \binom{d}{x} \sum_{j=1}^{x}(-1)^{j+x} \binom{x}{j} \left(\frac j d \right)^n$$

It's only when $x = d$ that the initial binomial term disappears.

Note also, a minor point, that it should be in general $(-1)^{j+x}$. It's only $(-1)^{j+1}$ when $x$ is odd.

Here's a counting argument that I think works:

Let $N_i$ be the number of ways that exactly any $i$ days can be birthdays:

$\binom{d}{2} 2^n = N_2 + 2\binom{d}{2}$

As all the $N_2$ cases are covered and every pair chosen generates $2$ cases where only 1 day is covered. Hence:

$N_2 = \binom{d}{2} (2^n - 2) = \binom{d}{2} \sum_{j=1}^{2} (-1)^{j+2} \binom{2}{j} j^n$

And:

$\binom{d}{3} 3^n = N_3 + \binom{d}{3}(3(2^n) - 3)$

All the $N_3$ cases are generated, plus for every triple there are 3 sets of $2^n$ cases where at most 2 days are covered, but this counts twice each of the three cases where only day is covered. Hence:

$N_3 = \binom{d}{3}(3^n - 3(2^n) + 3)$

And, in general - or for the last day - we get the series of alternating inclusions and exclusions.

I think everything you've mentioned is correct. Brain fade on my wording, especially since I had done this back in 1992 where I first determined this series based on observation, and ended up with a similar description of the terms of the series as alternating corrections (inclusions and exclusions).

http://rcgldr.net/misc/prob.rtf

I also posted here about that series back in 2012, the series is shown in posts #1 and #12, wondering if there was a better way than the alternating series. It includes some of the observation process, with comments on the series in posts 16 through 19.

https://www.physicsforums.com/threads/permutation-7-identical-items-32-distinct-containers.588810

I've got some notes about this, but haven't found them yet.

 

[Erland]

I will give solution of Problem 4. I use andrewkirks notation:

Is the following then an accurate representation of what the set $\mathcal B$ is intended to be in problem 4?

Let $C^0$ be the set of all continuous functions from $\mathbb R\to \mathbb R$.
Given a set $S$ of functions $\mathbb R\to\mathbb R$, we say $S$ is 'pointwise closed' if, for any countable subset $(f_n)_{n\in\mathbb N}$ of $S$ that converges pointwise to a function $f:\mathbb R\to\mathbb R$, the function $f$ is also in $S$.

Then $\mathcal B$ is defined to be the intersection of all sets of functions $S$ that contain $C^0$ and are pointwise closed.

micromass says that this is correct.

Here is my solution:

Since all continuous functions are Borel measurable, and all pointwise limits of Borel measurable functions are Borel measurable (W. Rudin, Real and Complex Analysis, 3rd ed, Corollary (a), p. 15, McGraw-Hill, Singapore, 1986), it follows that all functions in $\mathcal B$ are Borel measurable functions.

Conversely, let $\Omega$ be the set of all countable ordinals.

We define $C^\alpha$, for $\alpha\in \Omega$, by recursion thus:
$C^0$ is as above. For $\alpha>0$, $C^\alpha$ is the set of all pointwise limits of functions in $\cup_{\beta<\alpha} C^\beta$.

We prove that $\mathcal B=\cup_{\alpha\in\Omega}C^\alpha$.

To see this, we first notice that by transfinite induction, any pointwise closed set $S$ of real valued functions on $\mathbb R$ which contains $C^0$ contains $C^\alpha$ for all $\alpha\in\Omega$. This means that $\cup_{\alpha\in\Omega}C^\alpha\subset\mathcal B$.

Conversely, $C^0\subset\cup_{\alpha\in\Omega}C^\alpha$. Also, for any sequence $(f_n)_{n\in\mathbb N}$ of functions in $\cup_{\alpha\in\Omega}C^\alpha$, there is a sequence of countable ordinals $(\alpha_n)_{n\in\mathbb N}$, such that $f_n\in C^{\alpha_n}$ for all $n\in\mathbb N$.
The supremum of any countable subset of $\Omega$ is a countable ordinal (a consequence of $\aleph_0^2=\aleph_0$), so there is an $\alpha\in \Omega$ such that $f_n\in C^\alpha$ for all $n\in\mathbb N$. Therefore, if such a sequence $(f_n)_{n\in\mathbb N}$ is pointwise convergent, its limit lies in $C^{\alpha+1}$. It follows that $\cup_{\alpha\in\Omega}C^\alpha$ is pointwise closed.
This means that $\mathcal B\subset\cup_{\alpha\in\Omega}C^\alpha$.

Hence, $\mathcal B=\cup_{\alpha\in\Omega}C^\alpha$.

Next, we prove by transfinite induction that if $f,g\in C^\alpha$, then $f+g\in C^\alpha$ and $\min(f,g)\mathcal \in C^\alpha$ for all $\alpha\in \Omega$: This is true for $\alpha=0$. Assume that it holds for all $\beta<\alpha$, for some $\alpha>0$ ($\alpha\in\Omega$). Let $f,g\in C^\alpha$. Then there are two sequences $(f_n)_{n\in\mathbb N}$ and $(g_n)_{n\in\mathbb N}$ of functions in $\cup_{\beta<\alpha}C^\beta$ which converge pointwise to $f$ and $g$, respectively. Then, to each $n\in \mathbb N$ there are $\gamma_n<\alpha$ and $\delta_n<\alpha$ such that $f_n\in C^{\gamma_n}$ and $g_n\in C^{\delta_n}$. With $\beta_n=\max(\gamma_n,\delta_n)$, $f_n,g_n\in C^{\beta_n}$, and, by the induction hypothesis, $f_n+g_n\in C^{\beta_n}$ and $\min(f_n,g_n)\in C^{\beta_n}$. Since $(f_n+g_n)_{n\in \mathbb N}$ and $\min (f_n,g_n)_{n\in \mathbb N}$ converge pointwise to $f+g$ and $\min(f,g)$, respectively, those limit functions lie in $C^\alpha$.
The conclusion now follows by transfinite induction.

It follows that if $f,g\in \mathcal B$, then $f+g\in \mathcal B$ and $\min(f,g)\in\mathcal B$.

By a similar, somewhat simpler, argument, $f \in \mathcal B$ implies $rf\in \mathcal B$ for all $r\in \mathbb R$.

Next, let $\mathcal E$ be the family of all sets $E\subset\mathbb R$ such that $\chi_E\in\mathcal B$, where $\chi_E$ is the characteristic function of $E$.

Then, $\mathcal E$ contains all bounded open intervals $(a,b)\subset \mathbb R$, for if we put
f_n(x)=\begin{cases} 0, \qquad x\le a\\ \frac{2n}{b-a}(x-a), \qquad a&lt;x&lt;a+\frac{b-a}{2n}\\1,\qquad a+\frac{b-a}{2n}\le x\le b -\frac{b-a}{2n}\\<br /> \frac{2n}{b-a}(b-x),\qquad b-\frac{b-a}{2n}&lt;x&lt;b\\0,\qquad x\ge b\end{cases}
for all $n\in \mathbb N$, then $(f_n)_{n\in \mathbb N}$ is a sequence in $C^0$ which converges pointwise to $\chi_{(a,b)}$.

If $E,F\in\mathcal E$, then, by the above, $\chi_{\mathbb R\setminus E}=1-\chi_E\in\mathcal B$ and $\chi_{E\cup F}=\min(\chi_E+\chi_F,1)\in \mathcal B$, so $\mathbb R\setminus E\in \mathcal E$ and $E\cup F\in\mathcal E$.
Assume that $E_n\in\mathcal E$, for all $n \in \mathbb N$. Then, by induction, $\cup_{k=1}^n E_k\in\mathcal E$, for all $n\in \mathbb N$.
It follows that $\chi_{\cup_{n=1}^{\infty} E_n}=\lim_{n\to\infty} \chi_{\cup_{k=1}^{\infty} E_k}$ (pointwise), so $\chi_{\cup_{n=1}^{\infty} E_n}\in \mathcal B$ and $\cup_{n=1}^{\infty} E_n\in \mathcal E$.
This means that $\mathcal E$ is a $\sigma$-algebra which contains all bounded open intervals in $\Bbb R$. It follows that $\mathcal E$ contains all Borel sets.

From this and the above, it follows that $\mathcal B$ contains all simple Borel measurable functions, since these are linear combinations of characteristic functions of Borel sets.
Now, if $f:\mathbb R\to [0,\infty)$ is a positive Borel measurable function, then there is a sequence $(s_n)_{n\in\mathbb N}$ of simple Borel meaurable functions which converges pointwise to $f$ (W. Rudin, Real and Complex Analysis, 3rd ed, Theorem 1.17, p. 15, McGraw-Hill, Singapore, 1986). Hence $f\in \mathcal B$. Every real Borel measurable function $f$ can be written as a difference $f_+-f_-$, where

$f_+(x)=\begin{cases}f(x),\qquad f(x)\ge 0\\ 0,\qquad f(x)<0\end{cases}$ and $f_-=f-f_+$, and $f_+$ and $f_-$ both are positive Borel measurable functions, so $f\in \mathcal B$.
It follows that $\mathcal B$ contains all Borel measurable functions.

We have proved that $\mathcal B$ is the set of Borel measurable functions.

 

[Kaura]

I am a bit late to the party but none the less for Problem 6 I wrote a script to serve as a way to get experimental probability

Spoiler

function birthday(people, trials) {

var k;
var f;
var total = 0;

for (k = 0; k < trials; k++) {

var success = true;
var days = [];

for (f = 0; f < people; f++) {
days[f] = Math.floor(Math.random()*365);
}

for (f = 0; f < 365; f++) {
if (days.indexOf(f) == -1) {
success = false;
f = 365;
}
}

if (success === true) {
total++;
}
}

var chance = total / trials;

console.log(chance);

}

Entering in birthday(2016, 1000000) to the console served as a way to run 1000000 trials
This returned a value of 0.23017 probability
This is close to some of the other values I have seen in the thread so it might be close to the answer
If my code if incorrect for the situation please tell me
Also if you want to run the code for yourself in the console I would advise setting the trails parameter to 10000 or less as it more can take forever to run

 

[mfb]

This is close to some of the other values I have seen in the thread so it might be close to the answer

We have the analytic answer already.
Here are more digits, all correct unless WolframAlpha has a bug:
0.23098718155802874302697567890329631779588686618349968487

 

[haruspex]

Go to polar coordinates for the "1" term.

So, to complete the calculation:
1.
$I_1=\int\int\sqrt{x^2+y^2}=\int_{\theta=0}^{\pi/2}\int_{r=0}^{1}r^2drd\theta+2\int_{\theta=0}^{\pi/4}\int_{r=0}^{\sec(\theta)}r^2drd\theta$
$=\pi/6+\frac 23\int_0^{\pi/4}(\sec^3(\theta)-1)d\theta=\pi/6+\frac 13\left[\sec(\theta)\tan(\theta)+\ln|\sec(\theta)+\tan(\theta)|-2\theta\right]_0^{\pi/4}$
$=\frac 13\sqrt 2+\frac 13\ln(1+\sqrt 2)$
2. The 'x' and 'y' terms are equivalent, so we combine them:
$I_2=2\int\int x\sqrt{x^2+y^2}=\frac 23\int((1+y^2)^{\frac 32-y^3}dy=\frac 23\int_0^{\pi/4}\sec^5(\theta)d\theta-1/6$
Writing $s=\sin(\theta)$:
$\int_0^{\pi/4}\sec^5(\theta)d\theta=\int_0^{1/\sqrt 2}(1-s^2)^{-3}ds$
The integrand can be written $\frac 1{16}(3(1-s)^{-1}+3(1+s)^{-1}+3(1-s)^{-2}+3(1+s)^{-2}+2(1-s)^{-3}+2(1+s)^{-3})$
whence $I_2=\frac 14\ln(1+\sqrt 2)+\frac 5{12}\sqrt 2-\frac 16$
3. $I_3=\int\int xy\sqrt{x^2+y^2}=\frac 14\int\sqrt{x+y}=\frac 14\frac 23\frac 25 2^{\frac 52}=\frac 4{15}\sqrt 2$

Pulling the three integrals together, I₁-I₂+I₃, and applying the normalisation factor of 4:
average length of line $=\frac 13\ln(1+\sqrt 2)+\frac {11}{15}\sqrt 2-\frac 23$

 

[Kaura]

0.23098718155802874302697567890329631779588686618349968487

0.3537% error on my part then which makes me happy

 

[andrewkirk]

I will give solution of Problem 4.

That's an interesting approach. I've only read part of it so far, as other distractions keep butting in. I have a question on what I've read thus far, re the following:

We define $C^\alpha$, for $\alpha\in \Omega$, by recursion thus:
$C^0$ is as above. For $\alpha>0$, $C^\alpha$ is the set of all pointwise limits of functions in $\cup_{\beta<\alpha} C^\beta$.

This is a recursive definition. Don't we need well-orderedness of $\Omega$, or some similar constraint, for a recursive definition to be meaningful? Can you demonstrate, or provide a reference, supporting the well-orderedness of the countable ordinals?

Thanks

Andrew

 

[Erland]

This is a recursive definition. Don't we need well-orderedness of $\Omega$, or some similar constraint, for a recursive definition to be meaningful? Can you demonstrate, or provide a reference, supporting the well-orderedness of the countable ordinals?

All sets of ordinals are well ordered. In fact, if we use von Neumann's definition of ordinals

https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals

an ordinal $\alpha$ is identical to the set of all ordinals smaller than $\alpha$. This means that $\Omega$ is the same as the smallest uncountable ordinal, which is also the smallest uncountable cardinal $\aleph_1$.

 

[fresh_42]

I'll try to finish it (somehow - and hope I haven't forgotten some cases).

5.
Notation: $G$ is a $p$-group, and in our case of order $p^2$ or $p^3 \; , \; Z = Z(G)$ its center and $G' = [G,G]$ its commutator subgroup. $<a_i>$ will denote a subgroup generated by elements $a_i$ of $G$ and $|H| , |a|$ the order of a group $H$ or an element $a$, resp. The cyclic group of order $n$ will be denoted $C_n$. (And $\times$ will be the direct product, as usual.)

First of all:
All $p$-groups are nilpotent (the upper central series terminate and have abelian quotients) and therefore have a non-trivial center. If $G \diagup Z$ is cyclic, then $G$ is abelian, because all elements could be written $g = a^n \cdot z$ with a generator $aZ$ of $G \diagup Z$ and a center element $z$.

If $|G| = p^2$ then $G \diagup Z$ is either $\{1\}$ or isomorphic to $C_p$ In both cases $G$ is abelian. (The second case can therefore not appear, but it doesn't matter.) I.e. all groups of order $p^2$ are abelian and thus all subgroups are normal and the only possibilities are $G ≅ C^2_p$ or $G ≅ C_{p^2}.$

From now on let us assume $|G| = p^3.$ Again $Z ≠ \{1\}$ which leaves the cases $|Z| \in \{p,p^2,p^3\}$.
$|Z|=p^2$ is impossible for $G \diagup Z ≅ C_p$ and $G$ would be abelian, i.e. $|Z| = |G| = p^3$.
If $|Z|=p^3$ then $G$ is abelian, all subgroups are normal and $G$ has to be isomorphic to one of $C_{p^3} \; , \; C_{p^2} \times C_{p} \; , \; C_p^3$

So we are left with the following situation: $|G| = p^3 \; , \; |Z| = p$ and $G \diagup Z$ is not cyclic of order $p^2$. Thus $G \diagup Z ≅ C_p \times C_p$ by the previous result, which is abelian. Furthermore $G' = [G,G] \subseteq Z$ which is only possible for $G' = Z ≅ C_p$. ($G' = \{1\}$ would imply $G$ abelian.)

All group elements beside $1$ have orders $p$ or $p^2$. There is at least one element of order $p$ in $G \diagup Z ≅ C_p \times C_p$ so we have two non-central elements $a$ and $b$ of order $(|a|,|b|) = (p,p)$ or w.l.o.g. $(|a|,|b|) = (p^2,p)$ and a central element in $G'$ of order $p$. So either $G ≅ A := <a,b \; | \; a^p = b^p = [a,b]^p = 1>$ or $G ≅ B := <a,b \; | \; a^{p^2} = b^p = 1 , [a,b] = a^p>.$
The group $D := <a,b \; | \; a^{p^2} = b^p = [a,b] = 1>$ is isomorphic to $B$ by interchanging the generators.

In case $p=2 \; ,\; A$ are the quaternions $Q_8$ with $a = i \; , \; b= j \; , \; ab = k$ and $B$ is the dihedral group $D_4$ (with $8$ elements).

 

[micromass]

So either $G ≅ A := <a,b \; | \; a^p = b^p = [a,b]^p = 1>$ or $G ≅ B := <a,b \; | \; a^{p^2} = b^p = 1 , [a,b] = a^p>.$

If you write groups as a presentation, then you risk the groups to be trivial, or not having the order you want. So how are you sure that $A$ and $B$ have order $p^3$?

 

[fresh_42]

If you write groups as a presentation, then you risk the groups to be trivial, or not having the order you want. So how are you sure that $A$ and $B$ have order $p^3$?

I don't know other group names. The case $p=2$ would suggest a generalized quaternion group for the $A's$, but those are dicyclic, and higher dihedral groups for the $B's$, but those contain reflexions. However, I admit I did everything to avoid group characters and the unit circle. I thought that might get too complicated, resp. too far from standard knowledge. (To be honest: it has been so long ago that I studied them that I've forgotten most of it.) Maybe there is another way to show the result by more emphasis on conjugation classes and orbits.

I know that $G \diagup Z$ is not cyclic of order $p^2$, i.e. $G \diagup Z ≅ C_p^2$. (The other cases have been ruled out or treated before.) So it is generated by two elements $aZ$ and $bZ$ of order $p \, (mod \, Z)$ and therefore I have $p^2$ elements modulo $Z$.
And $G' = [G,G] = Z$ is cyclic of order $p$. So I get $p \cdot p^2 = p^3$ elements in $G$.

Since $G$ is not abelian and $a \notin Z$ has been chosen in the w.l.o.g statement, I can choose an element $b \notin Z$ of order $p$ that doesn't commute with $a$, i.e. $1 \neq [a,b]$ generates $Z = G' ≅ C_p$. For this purpose I can take a representative $b$ of the set $G \diagup{<a>}$. If such a $b$ would commute with $a$ it would be a central element of $G$. If all those elements were of order $p^2$ then $G \diagup Z \ncong C_p^2.$

Finally, the groups $A$ and $B$ cannot be isomorphic since $B$ contains an element of order $p^2$ and $A$ doesn't.

 

[micromass]

You can't define a group only by giving the presentation. You have then no guarantee that $a\neq b$ as generators of the group. There are many similar issues. So what you've proven is that there are at most $2$ nonabelian groups. But a presentation alone doesn't suffice in defining a group.

 

[fresh_42]

You can't define a group only by giving the presentation.

Why not? A group $G$ defined as $<a,b \;|\; \mathcal{R}_i (a,b)>$ is defined as the quotient of the free group $\mathcal{F}(a,b)$ and its normal subgroup generated by all relations $\mathcal{R}_i (a,b)$ (and their conjugates).

I have shown that $G$ of order $p^2$ is isomorphic to a group in $\{C_p^2,C_{p^2} \}$, the abelian groups $G$ of order $p^3$ are isomorphic to a group in $\{C_p^3,C_{p^2} \times C_p, C_{p^3} \}$ and the non-abelian groups $G$ of order $p^3$ are isomorphic to $G \cong (G\diagup Z) \ltimes Z \cong (C_p \times C_p) \ltimes C_p$ with the center $Z=G' = [G,G]$ of $G$ and cyclic groups $C_p$. The representations only show the two basic non-abelian possibilities of the structure of the semi-direct product.

Do you mean that I have to show that $G \diagup Z$ is isomorphic to a subgroup of $G$?

 

[micromass]

Why not? A group $G$ defined as $<a,b \;|\; \mathcal{R}_i (a,b)>$ is defined as the quotient of the free group $\mathcal{F}(a,b)$ and its normal subgroup generated by all relations $\mathcal{R}_i (a,b)$ (and their conjugates).

You have no guarantee about the order of this group, neither about whether the generators are distinct or not.

I have shown that $G$ of order $p^2$ is isomorphic to a group in $\{C_p^2,C_{p^2} \}$, the abelian groups $G$ of order $p^3$ are isomorphic to a group in $\{C_p^3,C_{p^2} \times C_p, C_{p^3} \}$ and the non-abelian groups $G$ of order $p^3$ are isomorphic to $G \cong (G\diagup Z) \ltimes Z \cong (C_p \times C_p) \ltimes C_p$ with the center $Z=G' = [G,G]$ of $G$ and cyclic groups $C_p$. The representations only show the two basic non-abelian possibilities of the structure of the semi-direct product.

Right, if you say the group is $(C_p\times C_p)\ltimes C_p$, then you know that this is a group of $p^3$. So THAT is a good answer. Just giving the presentation gives you no guarantees about the orders.[/QUOTE]

 

[fresh_42]

Ok, you're right. E.g. if $a$ is of order $4$ in $D_4$ then $a^2$ generates the center which isn't obvious by the representation itself. I thought I could bypass this by showing $Z = [G,G]$.