4
$\begingroup$

Background

In the following question, User1 asks whether an infinite sum of irrational numbers can be rational. Multiple answers1 indicate the answer to this question is 'yes'. For instance, Rasmus Erlemann notes that

$$\tan \frac{\pi}4=\sum_{n=0}^\infty \frac{(-1)^n 2^{2n+2}(2^{2n+2}-1)B_{2n+2}}{(2n+2)!}\left(\frac{\pi}4\right)^{2n+1}=1, $$ by the Maclaurin series of $\tan(\cdot)$.

The Question

This question is asked in a similar spirit. I wonder whether there are any infinite series consisting solely of non-computable terms, that amount to a computable number. Examples of such non-computable numbers can found over here. They include Chaitin's constants.

To make the question more precise, define $$ C = \sum_{k=1}^{\infty} u_{k} . $$ Here, all $u_{k}$ are non-computable numbers. I am looking for explicit examples of infinite series such that $C$ is a computable number, and all $u_{k}$ are both positive and linearly independent over $\mathbb{Q}$.

Added

Although user TonyK answers my initial question correctly, I would like to add another restriction to make the question more interesting. I furthermore require that every sum of a finite subset of summands of the infinite series is also non-computable. This makes TonyK's example unworkable, since, for instance, the sum of the first two terms is computable: $$ \alpha u_{1} + (1-\alpha)u_{1} = u_{1}, $$ where $\alpha$ is non-computable and $u_{1}$ is a positive computable term.


Notes

[1] If you're interested in such series, I encourage you to also take a look at my recent answer. It involves a class of representations of numbers, called rational zeta series, that offers a fruitful way to approach this problem. For instance, the answer includes the series identity $$\sum_{n=1}^{\infty} \left[ \zeta(2n)-1 \right] = \frac{3}{4} . $$

$\endgroup$
1
  • $\begingroup$ Isn't such a manipulation enough to show theoretically? If we have infinitely many $u_i$'s that are both positive and linearly independent over $\mathbb{Q}$, then let's say, that they sum to an uncomputable sum: $$\sum_{i=1}^{\infty} u_{i}=U$$ What I think is true but it's not a proof, that the following is true, and the final result also has the required properties: $$\sum_{i=1}^{\infty} \frac{C* u_{i}}{C}=U$$ $$\frac{1}{C} \sum_{i=1}^{\infty} C* u_{i}=U$$ $$\frac{1}{U} \sum_{i=1}^{\infty} C* u_{i}=C$$ $$\sum_{i=1}^{\infty} \frac{C* u_{i}}{U}=C$$ $\endgroup$ Feb 21 at 13:17

2 Answers 2

4
$\begingroup$

Let $\alpha\in(0,1)$ be an uncomputable number, and let $\sum u_k$ be any convergent series of positive computable terms linearly independent over $\Bbb Q$. Then the series $$\alpha u_1+(1-\alpha)u_1+\alpha u_2+(1-\alpha)u_2+\cdots$$ satisfies your conditions (because any linear dependency over $\Bbb Q$ would give us a way to compute the uncomputable $\alpha$).

You asked for an explicit example, so take for instance $u_k=p_k^{-3/2}$, where $p^k$ is the $p$th prime.

$\endgroup$
4
  • $\begingroup$ Hmmm, although this answer is probably correct, it somewhat feels like a trick. I'd prefer an answer in which the terms don't cancel out the non-computable numbers. I'm not sure, however, how this restriction ought to be incorporated within the question. Do you have any suggestions? $\endgroup$
    – Max Muller
    Feb 21 at 12:28
  • 2
    $\begingroup$ I can't read your mind, Max! $\endgroup$
    – TonyK
    Feb 21 at 12:31
  • $\begingroup$ I've added a restriction. I hope you don't take offence at this -- I'm grateful for the effort you've put in your answer, and for the opportunity it has provided to formulate a more focussed question. $\endgroup$
    – Max Muller
    Feb 21 at 12:46
  • 2
    $\begingroup$ @MaxMuller It doesn't really matter whether TonyK takes offence, it's against site norms to change a question in a way that invalidates existing answers. When you have a question that allowed an answer you didn't expect, the thing to do would be to post a new question and leave your original one (unless no one's posted an answer yet). Also, based on the title alone I came to give a worse version of TonyK's answer so if you are going to leave this question changed, it would be nice to at least change the title accordingly. $\endgroup$
    – Mark S.
    Feb 21 at 14:12
1
$\begingroup$

Let $\mathbb{F}$ denote any countable subfield of $\mathbb{R}$. Given any finite sequence $A=\left<\alpha_1,\cdots,\alpha_n\right>$ of real numbers, there is a dense set of numbers $x$ such that $x$ is linearly independent (over $\mathbb{F}$) with $A$. In fact, there are only countably many $x$ which are linearly dependent with $A$. Indeed, since $\mathbb{F}$ is countable then for each $n\in\mathbb{N}$ we also have $\mathbb{F}^n$ being countable, and then the set of finite sequences in $\mathbb{F}$, denoted by $\mathbb{F}^{<\omega} = \bigsqcup_{n\in\mathbb{N}}\mathbb{F}^n$, is also countable since it's a countable union of countable sets. Any linearly dependent $x$ could be expressed as $x=\sum_{k=1}^n q_k \alpha_k$, where each $q_k\in \mathbb{F}$, thus we have a surjection $\mathbb{F}^{<\omega} \to \operatorname{span}(A)$ defined by $q\mapsto \sum_k q_k \alpha_k$, and this proves that $\operatorname{span}(A)$ is countable.

In the case where $\mathbb{F}$ is the field of computable numbers, it's straightforward (although tedious) to explicitly construct the required enumeration of $\mathbb{F}^{<\omega}$. Firstly, using something like Godel numbering, there's an explicit bijection $\mathbb{N}^{<\omega}\to \mathbb{N}$. The set of computer programs can then be injected into $\mathbb{N}$ using that kind of encoding, since a computer program can be encoded as a finite sequence of symbols from some at-most-countable alphabet. This lets us inject $\mathbb{F}$ into $\mathbb{N}$, by sending each computable number to the smallest encoding of any program which computes it. The injection $\mathbb{F}\to\mathbb{N}$ extrapolates to an injection $\mathbb{F}^{<\omega} \to \mathbb{N}^{<\omega}$, and finally we can inject $\mathbb{F}^{<\omega}\to \mathbb{N}^{<\omega}\to \mathbb{N}$. This injection can be used to construct an explicit bijection $\mathbb{F}^{<\omega}\to \mathbb{N}$.

Finally, given any real numbers $a<b$, we can produce an explicit $x\in [a,b]$ such that $x$ is uncomputable and $x$ is linearly independent with $A$. In fact, there's an explicit function $(A,a,b)\mapsto x$ that we can define. To do this, first let $n\mapsto s_n$ denote the explicit enumeration of $\operatorname{span}(A)$, which we had found before. Next let $r_n=\frac{s_n-a}{b-a}$, then the $r$ sequence is just a sequence in the interval $[0,1]$. Carry out the usual diagonalization to produce some $z\in[0,1]$ such that $z\neq r_n$ for all $n$. This $z$ can be produced explicitly as a function of the $r$ sequence: the $n$'th decimal digit of $z$ is assigned to $0$ whenever the $n$'th digit of $r_n$ is not $0$, and otherwise the $n$'th digit of $z$ is assigned to $1$. Finally let $x=a + (b-a)\cdot z$, then we have $x\in [a,b]$ and $x\neq s_n$ for all $n$.


To answer your question, recursively define a sequence of numbers such that: $\sigma_1\in (0,1)$ is uncomputable, and for each $n\in\mathbb{N}$ we select an uncomputable $\sigma_{n+1}\in(\frac{\sigma_n+1}{2}, 1)$ such that $\sigma_{n+1}$ is linearly independent (over $\mathbb{F}$) with $A=\left<1, \sigma_1, \cdots, \sigma_n\right>$. These $\sigma_n$ numbers can be selected using the explicit method we outlined previously. Now the full $\sigma$ sequence is linearly independent over $\mathbb{F}$, and in fact the extended sequence $\{1\}\cup\sigma$ is also linearly independent, so no nontrivial linear combination of $\sigma$ will ever be computable. If we let $\alpha_0=\sigma_0$ and $\alpha_{n+1} = \sigma_{n+1}-\sigma_n$, we can prove that likewise the $\alpha$ sequence is linearly independent over $\mathbb{F}$, and they are all uncomputable. We can prove by induction that $1-\sigma_n \leq 2^{1-n}$ and thus $\sigma_n\to 1$, and since we have $\sum_{k\leq n}\alpha_k = \sigma_n$ then it follows that $\sum_{n=1}^\infty \alpha_k = 1$.

The method carried out to produce this example is entirely constructive; the $\alpha$ sequence we produce is explicit. The $\alpha$ sequence is not that complicated, either. In fact, there's a computable sequence of computer programs such that the $n$'th program approximates $\alpha_n$, in the sense that it produces a sequence of rational numbers which limits to $\alpha_n$. The modulus of convergence is uncomputable, since each of the $\alpha_n$ are uncomputable, but nonetheless we have convergence. These are referred to as "recursively approximable" numbers, and they are computable relative to an oracle to the halting problem.

The above methods can be easily generalized, and we can have our summation converge to any value whatsoever. Also, in some sense, most sequences will be uncomputable and linearly independent. In the same way that the field of computable numbers is an infinite dimensional vector space over $\mathbb{Q}$, likewise the recursively approximable numbers are infinite dimensional over the computable numbers. We can construct more elaborate fields using Turing jump, and a similar phenomenon occurs for those larger structures.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .