515 – Caratheodory’s characterization of measurability (Homework 3)

April 12, 2012

This set is due Friday, April 27.

The goal of these problems is to prove Carathéodory‘s theorem that “extracts” a measure from any outer measure. In particular, when applied to Lebesgue outer measure, this construction recovers Lebesgue measure.

305 – A brief update on n(3)

April 12, 2012

This continues the previous post on A lower bound for $n(3)$.

Only recently I was made aware of a note dated November 22, 2001, posted on Harvey Friedman‘s page, “Lecture notes on enormous integers”. In section 8, Friedman recalls the definition of the function $n(k)$, the length of the longest possible sequence $x_1,x_2,\dots,x_n$ from $\{1,2,\dots,k\}$ with the property that for no $i, the sequence $x_i,x_{i+1},\dots,x_{2i}$ is a subsequence of $x_j,x_{j+1},\dots,x_{2j}$.

Friedman says that “A good upper bound for $n(3)$ is work in progress”, and states (without proof):

Theorem. $n(3)\le A_k(k)$, where $k=A_5(5)$.

Here, $A_1,A_2,\dots$ are the functions of the Ackermann hierarchy (as defined in the previous post).

He also indicates a much larger lower bound for $n(4)$. We need some notation first: Let $A(m)=A_m(m)$. Use exponential notation to denote composition, so $A^3(n)=A(A(A(n)))$.

Theorem. Let $m=A(187196)$. Then $n(4)>A^m(1)$.

He also states a result relating the rate of growth of the function $n(\cdot)$ to what logicians call subsystems of first-order arithmetic. A good reference for this topic is the book Metamathematics of First-order Arithmetic, by Hájek and Pudlák, available through Project Euclid.

There is a recent question on MathOverflow on this general topic.

305 – Derived subgroups of symmetric groups

April 11, 2012

One of the problems in the last homework set is to study the derived group of the symmetric group $S_n$.

Recall that if $G$ is a group and $a,b\in G$, then their commutator is defined as

${}[a,b]=aba^{-1}b^{-1}$.

The derived group $G'$ is the subgroup of $G$ generated by the commutators.

Note that, since any permutation has the same parity as its inverse, any commutator in $S_n$ is even. This means that $G'\le A_n$.

The following short program is Sage allows us to verify that, for $3\le i\le 6$, every element of $(S_i)'$ is actually a commutator. The program generates a list of the commutators of $S_i$, then verifies that this list is closed under products and inverses (so it is a group). It also lists the size of this group. Note that the size is precisely ${}|A_i|$, so $(S_i)'=A_i$ in these 4 cases:

305 – Cube moves

April 11, 2012

Here is a small catalogue of moves of the Rubik’s cube. Appropriately combining them and their natural analogues under rotations or reflections, allow us to solve Rubik’s cube starting from any (legal) position. I show the effect the moves have when applied to the solved cube.