39
$\begingroup$

Let $$\mathcal L=\left\{\sum_{n=1}^{\infty}a_n:\exists P(x),Q(x)\in\mathbb{Z}[x],\forall k\in\mathbb{N},Q(k)\neq 0,a_n=\frac{P(n)}{Q(n)},\sum_{n=1}^{\infty}a_n\text{ converges}\right\}.$$ We have $\sum_{n=1}^{\infty}\frac{1}{n(n+1)}=1$, hence for all $a/b\in\mathbb{Q}$ we have $a/b\in\mathcal L$, so that $\mathbb{Q}\subseteq\mathcal L$. Furthermore, $\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}$, thus $\mathcal L\neq\mathbb{Q}$. In addition, $\mathcal L$ is countable, and therefore $\mathcal L\neq \mathbb{R}$. This is all I can say about $\mathcal L$ for now. A natural question arises.

Do we know of an explicit real number that is not in $\mathcal L$ (from what we showed such a number exists and is irrational)?

$\endgroup$
16
  • 5
    $\begingroup$ @DaveL.Renfro maybe there was a modification but the post seems correctly stated to me, it is juste the sums of series which general terms are given by f(n) where f is a rational fraction of polynomials $\endgroup$ Commented 2 days ago
  • 4
    $\begingroup$ Your statement is perfectly valid don’t worry. The problem however is really hard $\endgroup$ Commented 2 days ago
  • 5
    $\begingroup$ For $\log2$, we have $$\log2=1-{1\over2}+{1\over3}-{1\over4}+\dotsb={1\over2}+{1\over12}+{1\over30}+\dotsb=\sum{1\over(2n-1)(2n)}$$ $\endgroup$ Commented 2 days ago
  • 5
    $\begingroup$ Doesn't it work with $\displaystyle\sum_{n=0}^\infty 2^{-n^2}$ ? As the number is irrational, no finite summation will achieve it and no polynomial can produce a sufficiently fast decrease of the terms. $\endgroup$ Commented 2 days ago
  • 5
    $\begingroup$ I would also try $\sum 10^{-n!}$ working on the base 10 coefficients which are very sparse. With @GerryMyerson ‘s comments probably that alternating series are not the answer $\endgroup$ Commented 2 days ago

1 Answer 1

16
$\begingroup$

Every value of $\mathcal L$ is computable, hence any fixed noncomputable real such as a Chaitin halting probability $\Omega_U$ does not lie in $\mathcal L$. Indeed, let $a_n=P(n)/Q(n)$ with $P,Q\in\mathbb Z[x]$, $\deg P=d$, $\deg Q=D$, and $Q(k)\neq0$ for all $k$. If $D-d\le1$ then $$a_n=\frac{p_d}{q_D}\,\frac1{n^{D-d}}+O\!\left(\frac1{n^{D-d+1}}\right),$$ so $a_n\sim c/n$ when $D-d=1$ or $a_n\to c\neq0$ when $D-d\le0$. Thus $\sum a_n$ cannot converge, and convergence forces $D-d\ge2$.

Write $B=\sum_i |p_i|$ for the coefficients of $P$, let $q_D$ be the leading coefficient of $Q$, and set $S=\sum_{i<D}|q_i|$. Take $$N=\max\!\{2,\;1+\lceil \tfrac{2S}{|q_D|}\rceil\}.$$ For $n\ge N$ we have $|P(n)|\le B n^d$ and $|Q(n)|\ge |q_D|n^D - S n^{D-1}\ge \tfrac{|q_D|}{2}n^D$, hence $$|a_n|\le \frac{2B}{|q_D|}\,n^{-(D-d)}\le \frac{K}{n^2}\qquad (K:=2B/|q_D|).$$ Therefore $\sum_{n\ge M}|a_n|\le K/(M-1)$ for every $M\ge N$. Given $\varepsilon>0$, choose $$M\ge \max\!\{N,\;1+\lceil K/\varepsilon\rceil\}$$ to get $\sum_{n\ge M}|a_n|\le \varepsilon$. This produces a computable modulus of Cauchy convergence, so $\sum_{n=1}^\infty a_n$ is a computable real. Since $\Omega_U$ is noncomputable, it follows that $\Omega_U\notin\mathcal L$.

Moreover, there is an explicit computable real outside $\mathcal L$: effectively enumerate all pairs $(P_i,Q_i)$ with $Q_i(k)\neq0$ and $\deg Q_i\ge\deg P_i+2$, let $s_i=\sum_{n\ge1}P_i(n)/Q_i(n)$ (each $s_i$ computable by the bound above), write $s_i$ in canonical binary expansion and let $d_i$ be its $2i$-th binary digit. Define $\xi=0.b_1b_2b_3\ldots$ by setting $b_{2i-1}:=0$ and $b_{2i}:=1-d_i$. Then $\xi\notin\mathcal L$ and $\xi$ is computable.

$\endgroup$
3
  • $\begingroup$ How are you sure that there is a infinite number of zero digits $d_i$? Otherwise, you would obtain a non-canonical binary expansion for $\xi$. I suggest to define $d_i$ as the $2i$-th binary digit of $s_i$ and place zeroes on odd positions. $\endgroup$ Commented yesterday
  • $\begingroup$ @ChristopheBoilley: thank you. I implemented your suggestion into an updated solution. $\endgroup$ Commented yesterday
  • $\begingroup$ Note also that the condition $\forall k,\ Q_i(k)\neq 0$ is indeed computable, because the set of possible roots can be bounded knowing the coefficients. That is not obvious. $\endgroup$ Commented 12 hours ago

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.