I have a question on the first Theorem from the article Complexity of Oscillations in Infinite Binary Sequences by P. Martin-Löf, which could be downloaded from the publisher or from here.
Theorem 1: Let $f$ be a resursive function such that $$ \sum_{n=1}^{\infty} 2^{-f(\omega)} = +\infty. $$ Then, for every binary sequence $x_1, x_2, \ldots, x_n,\ldots,$ $$ K(x_1x_2 \ldots x_n | n) < n - f(n) $$ for infinitely many $n$.
I understand that the function $g(n)$ is constructed to get rid of the constant $c$. But the rest I am extremely unsure:
1) How are the $A_n$ constructed, is here $m = g(n)$ assumed (see the side note in red) because we construct strings of length $n$ by appending strings of length $n - g(n)$ to $x_1 \cdots x_m$? Also latter we use that $x_1 x_2 \cdots x_n \in A_n$ if and only if $$ K_B(x_1 \ldots x_n | n) < n - g(n) $$ which means there must exist a program $p$ of length $p < n - g(n)$ such that $B(p, n) = x_1\ldots x_n$. But where does this $p$ come from? Has it something to do with the $x_1 \cdots x_m$ used in the construction?
2) Why does $\sum_n \mu(A_n) = \infty$
"force the $A_n$ to circle around the tree [...] therefore, if $x_1x_2 \cdots$ is a fixed infinite sequence, the initial segment $x_1x_2 \cdots x_n$ will belong to $A_n$ for infinitely $n$."
For example if $A_n = (1/2, 1)$ for each $n$ also fulfill $\sum_n \mu(A_n) = \infty$, but here nothing circles around, it just stayes fixed, or if $\mu(A_n) = 1/n$ it will also diverge, but I could easily imagine $A_n$ such that not every infinitely sequence has infinitely many prefixes in infinitely many $A_n$.
No $m$ need not be equal to $g(n)$. In fact $g(n) = m + f(n)$. The construction is concerned with the sequences of lenght $n$ that follow $x_1 \ldots x_m 1\ldots 1$ we are not appending $n - g(n)$ digits (as far as I understand).
For example $m = 2$ $n = 4$ $g(n)=2$ $2^{n-g(n)}-1=3$. The sequences we have are $$x_1 x_2 1 1\\ x_1x_2 10\\ x_1x_2 01\\ $$ note that it is important to have $g(n) \geq m$ since if $n - g(n)$ is too large, there won't be sequences available.
That is, we might have $m = 2$ $n = 5$ $g(n)=3$ $2^{n-g(n)}-1=3$. The sequences we have are $$x_1 x_2 x_31 1\\ x_1x_2x_3 10\\ x_1x_2x_3 01\\ $$
But we could'n have $m = 4$ $n = 5$ $g(n)=2$ $2^{n-g(n)}-1=7$. The sequences we have are $$x_1 x_2 x_3 x_41\\ x_1x_2x_3 x_4 0\\ ????????????????\\ $$