9
$\begingroup$

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

$\endgroup$
  • 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
19
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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