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$ – Emil Jeřábek supports Monica Jul 4 '17 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$ – XL _At_Here_There Jul 4 '17 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 Jul 4 '17 at 20:08
-
$\begingroup$ @Gamow right, but it excludes the case of Hartmanis-Stearns Conjecture. $\endgroup$ – XL _At_Here_There Jul 4 '17 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$ – Sasho Nikolov Jul 4 '17 at 21:03
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$ – Emil Jeřábek supports Monica Jul 5 '17 at 9:09
-
3$\begingroup$ I have chosen Jeffrey's post as the answer to the question, since his answer is posted earlier. $\endgroup$ – XL _At_Here_There Jul 5 '17 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$ – Emil Jeřábek supports Monica Jul 5 '17 at 12:50
-
3$\begingroup$ :D, great! Hope we can enjoy more topics. $\endgroup$ – XL _At_Here_There Jul 5 '17 at 13:25