Questions

Martin’s conjecture is an attempt to classify the behavior of definable functions on the Turing degrees. Roughly speaking, it says that every definable function on the Turing degrees is either eventually constant or eventually equal to some (transfinite) iterate of the Turing jump.

A bit more precisely, say that a function \(f\colon 2^\omega \to 2^\omega\) is Turing invariant if for all \(x \equiv_T y\), \(f(x) \equiv_T f(y).\) We can quasi-order Turing invariant functions as follows: say that \(f\) is Martin below \(g,\) written \(f \leq_M g\), if for all \(x\) in some cone of Turing degrees, \(f(x) \leq_T g(x)\). Define Martin equivalence (written \(f \equiv_M g\)) likewise.

Martin’s conjecture is usually divided into two parts. Part 1 says that every Turing invariant Borel function \(f \colon 2^\omega \to 2^\omega\) is either Martin equivalent to a constant function or Martin above the identity function. The question above is related to part 1.

When studying Martin’s conjecture, it has proven useful to work with pointed perfect trees: perfect binary trees \(T\) such that every path through \(T\) computes \(T\). The most important aspect of such trees is that they contain an element of every Turing degree in some cone of Turing degrees.

A positive answer to the question above would not, to my knowledge, solve part 1 of Martin’s conjecture, but I would consider it a major step towards a solution (and a negative answer would imply that Martin’s conjecture is false). In particular, it would imply a number of statements closely related to part 1 of Martin’s conjecture whose technical details are too lengthy to easily explain here (but feel free to email me if you’re curious).

By a “complexity preserving basis theorem,” I mean a statement of the following form: given an infinite, computable binary tree \(T\) and \(x \in 2^\omega\), there is some \(y\in[T]\) such that the initial segment complexity of \(x\) relative to \(y\) is not much less than the unrelativized initial segment complexity of \(x\). Of course, the answer to this question may depend on the interpretation of “initial segment complexity” and “doesn’t change much.” So the actual question is to find interesting theorems that fit this general format.

Probably the most natural way to interpret the statement of “complexity preserving basis theorem” given above is to take “initial segment complexity” to mean plain (or perhaps prefix free) Kolmogorov complexity and to take “doesn’t change much” to mean “doesn’t change by more than an additive constant.” Unfortunately, this version of the statement is false.

Proposition.  There is an infinite, computable binary tree \(T\) and \(x \in 2^\omega\) such that for all \(y \in [T]\), \(C(x\upharpoonright n) - C^y(x \upharpoonright n)\) is not bounded by any constant.

Proof. Let \(x\) be the all \(0\)s sequence and let \(T\) be a tree all of whose paths are random reals. Note that for any \(n\), \(C(x\upharpoonright n)\) is equal to \(C(n)\) up to a constant error term and that this also holds relative to any oracle. Since every \(y \in [T]\) lowers the complexity of infinitely many \(n\) by arbitrarily large finite amounts, it also lowers the complexity of infinitely many initial segments of \(x\) by arbitrarily large amounts.

It is not hard to modify the proof to use prefix free complexity instead of plain complexity or to show that the gap between \(C(x\upharpoonright n)\) and \(C^y(x \upharpoonright n)\) is infinitely often \(\Omega(\log(n))\). On the other hand, it is easy to prove a complexity preserving basis theorem with \(\log\) error.

Proposition.  For every infinite, computable binary tree \(T\) and \(x \in 2^\omega\), there is some \(y \in [T]\) such that for all \(n\), \(C^y(x \upharpoonright n) \geq C(x\upharpoonright n) - O(\log(n)).\)

In light of these observations, there are a few options for trying to find an interesting complexity preserving basis theorem.

• Use some notion of complexity other than plain or prefix free.
• Preserve the complexity of infinitely many initial segments of \(x\) rather than all initial segments of \(x\).
• Preserve complexity of initial segments conditional on their length rather than their unconditional complexity.

I am especially interested in the first option and, in particular, in the case of a priori complexity (see section 3.16 of Downey and Hirschfeldt or section 5.3 of Shen, Uspensky and Vereshchagin), which I will denote \(KM\).

Question.  For every infinite, computable binary tree \(T\) and \(x \in 2^\omega\), is there some \(y \in [T]\) such that for all \(n\), \(KM^y(x\upharpoonright n) \geq KM(x\upharpoonright n) - O(1)\)?

One reason that I find this question interesting is that a priori complexity is closely related to Hausdorff measure. In fact, having positive Hausdorff measure can be characterized in terms of a priori complexity using ideas similar to the point-to-set principle of Jack and Neil Lutz.

A second reason is that both computability and 1-randomness have characterizations in terms of a priori complexity. Thus an a priori complexity preserving basis theorem would constitute a common generalization of both the cone avoiding basis theorem and the randomness preserving basis theorem of Reimann-Slaman/Downey-Hirschfeldt-Miller-Nies.

A third and final reason is that a version of this statement follows from work of Reimann and thus it seems reasonable to hope that the question has a positive answer.

Proposition.  If \(h\colon \mathbb{N} \to \mathbb{N}\) is a computable, nondecreasing, unbounded function such that \(h(n + 1) \leq h(n) + 1\) then for all infinite, computable binary trees \(T\) and \(x \in 2^\omega\) such that for all \(n\), \(KM(x\upharpoonright n) \geq h(n)\), there is some \(y \in [T]\) such that for all \(n\), \(KM^y(x\upharpoonright n) \geq h(n) - O(1)\).

Proof. By work of Reimann, the assumptions imply that there is some measure \(\mu\) and a representation \(z\) of \(\mu\) such that \(x\) is \(\mu\)-random relative to \(z\) and \(\mu\) is \(h\)-bounded (i.e. for every string \(\sigma\) of length \(n\), \(\mu([\sigma]) \leq 2^{-h(n)}\), where \([\sigma]\) denotes the basic open set in \(2^\omega\) defined by \(\sigma\)). Since \(x\) is \(\mu\)-random relative to \(z\), a modification of the randomness preserving basis theorem shows that there is some \(y\in[T]\) such that \(x\) is \(\mu\)-random relative to \(y\oplus z\). Since \(\mu\) is \(h\)-bounded, this implies the conclusion.

Essentially the challenge of the question above is to remove the assumption that \(h\) is computable in the above proposition.

I am also interested in the other two options. For example, I would like to know the answer to the following question.

Question.  For every infinite, computable binary tree \(T\) and \(x \in 2^\omega\), is there some \(y \in [T]\) such that for all \(n,\) \(C^y(x\upharpoonright n \mid n) \geq C(x\upharpoonright n \mid n) - O(1)\)?

A priori complexity and monotone complexity are two variations on Kolmogorov complexity. Like all variations on Kolmogorov complexity, they differ from the standard version (i.e. “plain” Kolmogorov complexity) by at most a log factor. It is known that both a priori and monotone complexity differ from most other complexity notions by more than a constant factor. However, for a long time it was an open question to determine if they differed from each other by more than a constant factor. This question was answered by Gacs and later improved by Day to show that they differ by at least a loglog factor.

A priori complexity is closely connected to the concept of Hausdorff measure in geometric measure theory. For example, the property of a set \(A \subseteq \mathbb{R}\) having positive Hausdorff measure in dimension \(s\) can be characterized in terms of the a priori complexity of initial segments of its elements.

It seems natural, then, to wonder if monotone complexity is also connected to any concepts in geometric measure theory. If so, there is a chance that the Gacs-Day theorem could be translated to an interesting result in that setting.

Alexander Shen and Andrei Romashchenko have observed that “topological” arguments can be used to prove theorems about Kolmogorov complexity, typically the existence of one or more strings with some special properties related to Kolmogorov complexity. Shen and Romashchenko’s arguments use topological facts along the following lines: if \(F\colon D^2 \to D^2\) is a continuous function from the disk to itself which extends the identity map \(S^1 \to S^1\) on the boundary of the disk then the image of \(F\) contains the entire disk.

This raises the question of whether other theorems from topology can be used to prove statements about Kolmogorov complexity. An obvious candidate is Brouwer’s fixed point theorem: every continuous map \(F \colon D^2 \to D^2\) from the disk to itself has a fixed point. Shen and Romashchenko mention Brouwer’s fixed point theorem in their article, but do not seem to explicitly ask whether it can be used in the theory of Kolmogorov complexity.

It is not hard to find examples of countable structures with no computable presentations. One example is the minimal \(\omega\)-model of RCA₀. However, I don’t know of any really compelling example that would seem familiar to a mathematician working outside of logic. This is quite unlike the case for uncomputable problems in general, which do seem to show up in many parts of mathematics (e.g. Hilbert’s 10th problem). I feel that as a logician I should be able to tell a mathematician either “here’s an example of a structure that you think about but has no computable presentation” or “as far as we know, all countable structures that ‘normal’ mathematicians think about have computable presentations.”

Note that there are structures in mathematics for which it is not completely trivial to show that they have a computable presentation. For example, there is a computable presentation of the algebraic closure of the rationals, but this depends on some facts about polynomials over the rationals which are not needed to simply construct the algebraic closure mathematically.

This question obviously depends a lot on what “natural” means. It is easy to come up with theories which interpret very little arithmetic but have no computable models (e.g. a theory whose models essentially consist of infinite paths through some computable infinite binary tree with no computable infinite paths). But all such theories that I know about either interpret some amount of arithmetic (e.g. ZFC has no computable models) or feel like they were designed specifically not to have computable models.