# How many strings of length |w| are unrelated?

For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated?

A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically equal to their individual Kolmogorov complexities added together: K(w1,w2)=K(w1)+K(w2)

• It doesn't make sense to ask "How many items are Y" if Y is a binary relationship between two items; that only makes sense if Y is a property of a single item. Are you looking for the maximum-sized subset of $\{0,1\}^{|w|}$ such that all pairs in the subset are unrelated by that definition?
– D.W.
Nov 25 '20 at 23:44
• The answer could potentially depend on which universal mechanism is used to define $K$. Nov 26 '20 at 22:27
• @YuvalFilmus two incompressible strings of a given length cannot be related by this K(w1,w2)=K(w1)+K(w2) as it would break that rule --since most strings are incompressible most are unrelated. Is this along the lines of an answer? How much could choice of K vary the answer--not more than a constant right?
– user122281
Nov 27 '20 at 3:46
• The choice of $K$ varies the Kolmogorov complexity by at most a constant. Nov 27 '20 at 4:51