What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?

Question

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.

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)$.