Symmetry of information up to logarithmic terms

The concatenation construction in Basic conditional-complexity inequalities, with $x$ and $y$ exchanged, gives $C(x,y)\le C(y)+C(x\mid y)+O(\log (C(x)+2)+\log (C(y)+2))\mathrm{.}$

Put $a=C(x,y)$ and enumerate the finite set $A=\{(u,v):C(u,v)\le a\}$ by dovetailing all programs of length at most $a$; it has fewer than $2^{a+1}$ elements. Let $A_y=\{u:(u,y)\in A\}$ and $b=\lfloor {\log }_2\mathrm{\mid }{A}_y\mathrm{\mid }\rfloor$. Given $y,a,b$, the ordinal of $x$ in the enumeration of $A_y$ is a conditional description, so $C(x\mid y)\le b+O(\log (a+2))\mathrm{.}$ The set of $v$ whose fibre has at least $2^b$ elements is computably enumerable from $a,b$ and has fewer than $2^{a+1-b}$ members. The ordinal of $y$ in that enumeration gives $C(y)\le a-b+O(\log (a+2))\mathrm{.}$ Both decoder bounds transfer to the fixed machines by conditional optimality and Invariance theorem for plain Kolmogorov complexity. Adding them yields $C(x\mid y)+C(y)\le C(x,y)+O(\log (C(x,y)+2))$.

The elementary upper bounds on pair complexity make $\log (C(x,y)+2)$ no larger than the displayed logarithmic order. Combining steps 1.1 and 1.2 proves the equality. Applying it after swapping $x,y$ proves the stated symmetry.