Is there any known computable transcendental number such that its $n$th digit is computable in polynomial time, but not in $O(n)$?

  • 2
    $\begingroup$ It still doesn't make sense. Do you mean “... but not in time $O(n)$”, or what? $\endgroup$ Commented Jul 4, 2017 at 18:39
  • $\begingroup$ I mean in P time and not in $O(n)$. I am not sure if my English is wrong or yours, anyway thank you for your comment. $\endgroup$ Commented Jul 4, 2017 at 18:45
  • 2
    $\begingroup$ If the author manages to formulate this question in readable English, then it might be related to the Hartmanis-Stearns Conjecture: Every real number computed by a real-time multitape Turing machine is either transcendental or rational. $\endgroup$
    – Gamow
    Commented Jul 4, 2017 at 20:08
  • $\begingroup$ @Gamow right, but it excludes the case of Hartmanis-Stearns Conjecture. $\endgroup$ Commented Jul 4, 2017 at 20:39
  • 2
    $\begingroup$ I tried to make this understandable, but it's still not very clear. Do you mean not known to be computable in $O(n)$, or provably not computable in $O(n)$? What is the model of computation: single or multitape Turing machine, or something else? $\endgroup$ Commented Jul 4, 2017 at 21:03

2 Answers 2


Here is the construction of such a number. You can argue whether this means such a number is "known".

Take any function $f$ from $\mathbb{N}$ to $\{ 1, 2, \ldots, 8 \}$ where the $n$'th digit is not computable in $O(n)$ time. Such a function exists, for example, by the usual diagonalization technique. Interpret $f(n)$ as the $n$'th decimal digit of some real number $\alpha$. Now, for each $n$ of the form $2^{2^k}$, $k \geq 1$, change the digits of $\alpha$ in positions $n, n+1, \ldots, 3n$ to $0$'s. The resulting number $\beta$ evidently retains the property that the $n$'th digit is not computable in $O(n)$ time, but has infinitely many very good approximations by rationals, say to order $O(q^{-3})$, of the form $p/q$. Then by Roth's theorem $\beta$ cannot be algebraic. (It is not rational because it has arbitrarily long blocks of $0$'s set off by nonzeros on both sides.)


More generally, for any constant $k\ge1$, there are transcendental numbers computable in polynomial time, but not in time $O(n^k)$.

First, by the time hierarchy theorem, there exists a language $L_0\in\mathrm E$ not computable in time $O(2^{kn})$. We may assume $L\subseteq\{0,1\}^*$, and we may also assume that all strings $w\in L$ have length divisible by $3$.

Second, let $L_1$ be the unary version of $L_0$. For definiteness, for any $w\in\{0,1\}^*$, let $N(w)$ denote the integer whose binary representation is $1w$, and put $L_1=\{a^{N(w)}:w\in L_0\}$. Then $L_1\in\mathrm P$, but $L_1$ is not computable in time $O(n^k)$. Moreover, $L_1$ has the following property: for any $m$, $L_1$ does not contain any $a^n$ such that $2^{3m+1}\le n<2^{3m+3}$.

Third, let $$\alpha=\sum\{2^{-n}:a^n\in L_1\}.$$ (I’m assuming here that the question is about computing numbers in binary. If not, the $2$ above can be replaced with any desired base, it does not matter.)

Then $\alpha$ is computable in polynomial time, as we can compute its first $n$ bits by checking whether $a,a^2,\dots,a^n$ are in $L_1$. For the same reason, it is not computable in time $O(n^k)$, as the $n$-th bit determines whether $a^n\in L_1$.

For any $m$, let $$p=\sum\{2^{2^{3m+1}-n}:n\in L_1,n<2^{3m+1}\}=\lfloor\alpha2^{2^{3m+1}}\rfloor,$$ and $q=2^{2^{3m+1}}$. Then $$\left|\alpha-\frac pq\right|\le2^{-2^{3m+3}}=q^{-4}.$$ Thus, $\alpha$ has irrationality measure at least $4$, hence it is transcendental by Roth’s theorem.

  • 2
    $\begingroup$ Hmm, I see that I was scooped. I will leave the answer anyway, as it may be useful for someone. $\endgroup$ Commented Jul 5, 2017 at 9:09
  • 3
    $\begingroup$ I have chosen Jeffrey's post as the answer to the question, since his answer is posted earlier. $\endgroup$ Commented Jul 5, 2017 at 11:23
  • 6
    $\begingroup$ Yes. I’ll remind myself next time not to bother wasting time and effort on writing a thorough answer with all technical details, as it is apparently more valuable to post a few minutes earlier instead. $\endgroup$ Commented Jul 5, 2017 at 12:50
  • 3
    $\begingroup$ :D, great! Hope we can enjoy more topics. $\endgroup$ Commented Jul 5, 2017 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.