February 4th
Today I learned a little more about decidability of symbolic algebra series convergence. Specifically, I know that if we permit sums over multiple variables, then series convergence is undecidable. To be clear, for the time being we are allowing $\QQ[x_1,\ldots],\pi,i,|\bullet|,\exp,$ as well as addition, multiplication, and composition of these functions.
This is the easier than it appears, and in fact we claim that we can do this with only $\QQ$ and $|\bullet|.$ The key observation is that we can build a $0$-indicator over $\ZZ.$ As a lemma, we note that\[\frac12(x+y+|x-y|)=\begin{cases}x & x \gt y, \\ y & y \gt x,\end{cases}=\max\{x,y\}.\]It follows that we can construct $\max$ using only $|\bullet|.$ We remark that, at a high level, $|\bullet|$ is necessary because $\max$ is a non-smooth function, and $|\bullet|$ should be sufficient because $\max$ is piecewise differentiable. Now fix some $\varepsilon \gt 0,$ and we claim that\[\iota_0(q):=\max\left(0,-\frac1\varepsilon|q|+1\right)=\begin{cases} 1 & q=0, \\ 0 & |q|\ge\varepsilon.\end{cases}\]Note that we have not claimed behavior for $q\in(-\varepsilon,\varepsilon)\setminus\{0\},$ but if we fix $\varepsilon \lt 1,$ then this interval will contain no integers. So $\iota_0$ can still work as a $0$-indicator. Anyways, at $q=0,$ the above reads $\iota_0(0)=\max(0,1)=1.$ And if $|q|\ge\varepsilon,$ then\[-\frac1\varepsilon|q|+1 \lt 0,\]so $\iota_0(q)=0.$
Now we show that it is undecidable to determine if a series in multiple variables converges. In fact, we claim that an oracle which can determine if multivariate series converge can determine if a Diophantine equation in $\NN$ has roots, which we know to be undecidable from Hilbert's 10th. Fix some Diophantine equation $p(x_1,\ldots,x_n)=0$ for $p\in\ZZ[x_1,\ldots,x_n].$
We begin by lifting $p$ to a Diophantine with either $0$ or infinitely many solutions. Indeed, we quickly consider the polynomial\[\hat p(x_1,\ldots,x_{n+1}):=\left(x_{n+1}^2+1\right)p(x_1,\ldots,x_n).\]In particular, if $p$ has a natural root named $(y_1,\ldots,y_n),$ then $\hat p$ has infinitely many solutions by $(y_1,\ldots,y_n,y_{n+1})$ for any $y_{n+1}\in\NN.$ However, if $p$ has no solutions, then $\hat p$ can't have any solutions, for $\hat p=0$ requires either $x_{n+1}^2+1=0,$ which is impossible, or $p(x_1,\ldots,x_n)=0.$
From here, the killing blow is to look at\[\sum_{a_1,\ldots,a_{n+1}=0}^\infty\iota_0\left(\hat p(a_1,\ldots,a_{n+1})\right).\]We claim that this sum diverges if and only if $p$ has a natural root. We divide this into cases.
-
If $p$ has no natural roots, then $\hat p$ has no natural roots, so we must always have $\hat p(a_1,\ldots,a_{n+1})\in\ZZ\setminus\{0\}.$ Thus $\iota_0$ always returns $0,$ and the series converges.
-
If $p$ has a natural root, then $\hat p$ has infinitely many natural roots, so $\iota_0$ will return $1$ infinitely many times. Thus, the series diverges.
The claim follows, so being able to detect series convergence is enough to detect solutions to Diophantine equations, and we are done here.
I find it quite remarkable that this is doable with merely polynomials and $|\bullet|.$ I have been told that single-variable series convergence is undecidable with the usual suspects ($\QQ[x_1,\ldots],\pi,i,|\bullet|,\exp$), which must mean that decreasing the number of variables is a difficult task; I have not done this yet. If I put in $\floor\bullet$ and $\sqrt\bullet,$ then we recall that\[f_2(n)=\left(\left|\floor{\sqrt n}-\left(n-\floor{\sqrt n}^2\right)\right|,n-\floor{\sqrt n}^2\right)\]from a few days ago can surject $\NN\to\NN^2.$ It doesn't matter that $f_2$ isn't injective: if we have no roots, then we're only repeating $0$; and if we have roots, then the worst we can do is repeat $1,$ but we're already diverging anyways. My main qualm with $f_2$ is that $\sqrt\bullet$ isn't defined over all $\RR,$ so the set of functions we get are poorly defined. Also, $\floor\bullet$ introduces discontinuous functions, which is undesirable.
It might be possible to map $\NN\to\RR^\bullet$ in a way that is very close to $\NN^\bullet.$ In particular, we can build $\min(x,y)=-\max(-x,-y)$ and then, for $\varepsilon\in(0,1),$\[\min\left(\frac1\varepsilon\max(-|q|+1,0),1\right)=\begin{cases} 1 & |q|\le1-\varepsilon, \\ 0 & |q|\ge1.\end{cases}\]Thus, if we can get $\NN\to\RR^\bullet$ to be close enough to $\NN^\bullet$ so that $p(a_1,\ldots,a_n)=0$ implies we get some $p(x_1,\ldots,x_n)\le1-\varepsilon,$ then we can sum over the above indicator and still count the number of solutions to $p.$ This would finish, but of course the main difficulty is still that map $\NN\to\RR^\bullet.$