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

Question

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

Answer 1

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 2

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.