Q:

Any computable transcendental number that is computable in P time but not $O(n)$

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

A:

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

A:

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.

