An answer to the Gamma question

Author: Benoit Monin

Paper Information

Title:An answer to the Gamma question
Authors:Benoit Monin
Proceedings:LICS PDF files
Editors: Anuj Dawar and Erich Grädel
Keywords:Computability, Turing degrees, Coarse computability

ABSTRACT. We answer in this paper an open question (known as the "Gamma question"), related to the recent notion of coarse computability, which stems from complexity theory. The question was formulated by Andrews, Cai, Diamondstone, Jockusch and Lempp in "Asymptotic density, computable traceability and 1-randomness" (2016, Fundamenta Mathematicae). The Gamma value of an oracle set measures to what extent each set computable with the oracle is approximable in the sense of density by a computable set. The closer to 1 this value is, the closer the oracle is to being computable. The Gamma question asks whether this value can be strictly in between 0 and 1/2.

In this paper, we pursue some work initiated by Monin and Nies in "A unifying approach to the Gamma question" (2015, LICS). Using notions from computability theory, developed by Monin and Nies, together with some basic techniques from the field of error-correcting codes, we are able to give a negative answer to this question.

The proof we give also provides an answer to a related question, asked by Denis Hirschfeldt in the expository paper "Some questions in computable mathematics" (2017, Computability and Complexity). We also solve the Gamma problem for bases other than 2, answering another question of Monin and Nies.

Talk:Jul 10 10:20 (Session 53B)