If we have some string $x$ and a permutation $g$ which preserves the bits of $x$, we can store the value of $x$ on each of its $g$-orbits as well as $g$ instead of storing $x$ and we can reconstruct $x$ using this information in the obvious way.

Let $M_x$ be the set of Turing machines which print $x$ on their tape given any input, let $enc(M)$ be some reasonable encoding of Turing machines, and let $\langle g \rangle$ be the subgroup generated by $g$. Given $x \in \{0, 1\}^n$, we define

$K(x) = min_{M \in M_x} |enc(M)|$,

$Aut(x) = \{ g \in S_n \mid \forall i \in [n], x_i = x_{i^g} \}$,

$orb(g) = |\{ i^{\langle g \rangle} \mid i \in [n] \}|$,

and, for $g \in Aut(x)$, $b_{g,i}(x) = $ the value of $x$ on the $i$th orbit of $g$, ordering the orbits by the ordering already present on their lowest elements.

We extend $enc$ to $g \in S_n$ such that $enc(g)$ is the smallest encoding of a Turing machine which outputs $g$ in cycle notation on any input.

Finally, we define $GC(x) = min_{g \in Aut(G)} | b_{g, 1} ... b_{g, orb(g)} enc(g) |$.

I'm curious about the relationship between $K$ and $GC$. In particular, I suspect there exists some family of strings $x_{i \in \mathbb{N}}$ such that $K(x_i) \in o(GC(x_i))$ as functions of $i$, but I have no clue how to prove that or really why I suspect it, other than the fact that permutations just seem much less able to be clever than general Turing machines. The other natural thing to suspect would be that somehow these two things are measuring roughly the same thing and somehow this symmetry method is "complete" for the Kolmogorov sort of compression.


1 Answer 1


They are equivalent. For any $x$, let $g_x$ be a permutation with just two cycles: one consisting of $\{i \in [n] : x_i = 0\}$ (say, in ascending order) and one consisting of $\{i \in [n] : x_i = 1\}$ (also in ascending order). Then the "GC" description is just $01enc(g)$, whose length is $2 + K(g)$. But $K(g) \leq K(x) + O(1)$, since the above description of $g_x$ gives a uniform construction of $g_x$ from $x$. So we have $GC(x) \leq 2 + K(g) \leq K(x) + O(1)$.

  • $\begingroup$ Nice Josh, thanks, I'm really glad aesthetically that this is the case. $\endgroup$ Feb 2, 2018 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.