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

<p>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$.</p>

<p>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&lt;2^{3m+3}$.</p>

<p>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.)</p>

<p>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$.</p>

<p>For any $m$, let
$$p=\sum\{2^{2^{3m+1}-n}:n\in L_1,n&lt;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 <a href="https://en.wikipedia.org/wiki/Roth%27s_theorem" rel="noreferrer">Roth’s theorem</a>.</p>

CC BY-SA 3.0
2017-07-05T09:09:35.717Z
Hmm, I see that I was scooped. I will leave the answer anyway, as it may be useful for someone.
Emil Jeřábek
CC BY-SA 3.0
2017-07-05T11:23:31.903Z
I have chosen Jeffrey's post as the answer to the question, since his answer is posted earlier.
XL _At_Here_There
CC BY-SA 3.0
2017-07-05T12:50:48.190Z
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.
Emil Jeřábek
CC BY-SA 3.0
2017-07-05T13:25:46.590Z
:D, great! Hope we can enjoy more topics.
XL _At_Here_There
CC BY-SA 3.0
2017-07-05T09:07:54.750Z
2017-07-05T09:07:54.750Z
Emil Jeřábek
<p>Here is the construction of such a number.  You can argue whether this means such a number is "known".</p>

<p>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.)</p>

CC BY-SA 3.0
2017-07-05T08:55:12.640Z
2017-07-05T23:40:26.060Z
2017-07-05T23:40:26.060Z
Jeffrey Shallit
<p>Is there any known computable transcendental number such that its $n$th digit is computable in polynomial time, but not in $O(n)$?</p>

CC BY-SA 3.0
2017-07-04T18:39:59.320Z
It still doesn't make sense. Do you mean “... but not in time $O(n)$”, or what?
Emil Jeřábek
CC BY-SA 3.0
2017-07-04T18:45:19.090Z
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.
XL _At_Here_There
CC BY-SA 3.0
2017-07-04T20:08:58.920Z
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.
Gamow
CC BY-SA 3.0
2017-07-04T20:39:31.713Z
@Gamow right， but it excludes the case of Hartmanis-Stearns Conjecture.
XL _At_Here_There
CC BY-SA 3.0
2017-07-04T21:03:07.837Z
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?
Sasho Nikolov
CC BY-SA 3.0
2017-07-05T11:28:31.767Z
@SashoNikolov thank you for your editing.
XL _At_Here_There
<cc.complexity-theory><comp-number-theory>
Any computable transcendental number that is computable in P time but not $O(n)$
XL _At_Here_There
# Any computable transcendental number that is computable in P time but not $O(n)$

(Asked by: username_0 on 2017-07-04)

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

**Tags:** cc.complexity-theory, comp-number-theory

> **Comments:**
> **username_1**: It still doesn't make sense. Do you mean “... but not in time $O(n)$”, or what?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: @username_2 right， but it excludes the case of Hartmanis-Stearns Conjecture.  
> **username_3**: 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?  
> **username_0**: @SashoNikolov thank you for your editing.  

---

## 2 answers

### Answer by username_4 on 2017-07-05. Score: 19 | Accepted answer

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.)


---

### Answer by username_1 on 2017-07-05. Score: 11

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](https://en.wikipedia.org/wiki/Roth%27s_theorem).

> **Comments:**
> **username_1**: Hmm, I see that I was scooped. I will leave the answer anyway, as it may be useful for someone.  
> **username_0**: I have chosen Jeffrey's post as the answer to the question, since his answer is posted earlier.  
> **username_1**: 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.  
> **username_0**: :D, great! Hope we can enjoy more topics.  

---

