# Is there an elementary expression for every real sequence?

By elementary expression for the sequence $$\{a_n\}_{n=0}^\infty$$, I mean an elementary function $$f : X \to \mathbb C$$, where $$\mathbb N \subset X \subset \mathbb R$$, such that $$f(n)=a_n$$ for all $$n$$. The set of elementary functions, is the smallest set that

• contains constant functions $$f(x)=c\in\mathbb C$$;
• contains $$f(x)=x$$;
• is closed under addition $$f(x) + g(x)$$, multiplication $$f(x)g(x)$$ and exponentiation $$f(x)^{g(x)}$$, where exponentiation is restricted to where $$f(x)\in\mathbb R^+$$ for convenience;
• is closed under composition $$f(g(x))$$
• is closed under exponentiation $$\exp f(x)$$ and logarithm $$\ln f(x)$$ by the principal branch.

In particular, trigonometric functions and their inverses are also elementary ($$\sin(x) = \frac{-i}2(e^{ix}-e^{-ix})$$, $$\arctan x=\frac{1}{2}i[\ln(1-ix)-\ln(1+ix)]$$, etc). And the Gaussian function $$\lfloor x\rfloor, x\in \mathbb R\backslash \mathbb Z$$ is elementary by fiddling with $$\arctan \cot x$$ (which resembles the fractional part function).

A very important elementary sequence is the prime number sequence $$p_n = \text{the } n^{\text {th}} \text{ prime}$$. This sequence IS elementary! To see this, construct $$c = \sum_{i=1}^{\infty} p_i 10^{-i(i+1)/2},$$ which converges and is a constant, thus satisfying our criteria despite containing infinite sums. We can then construct $$f(i)=\left\lfloor c10^{i(i+1)/2}\right\rfloor - \left\lfloor c10^{i(i-1)/2}\right\rfloor10^{i}$$ to extract the primes, since $$p_i < 10^i$$. In this way, we can construct elementary expressions for any positive integer sequence, as long as it can be bounded by another elementary sequence. And by a clever construction here (contains unfixed minor errors) or here (Chinese), we can see that all positive integer sequences can be bounded, and thus have elementary expressions. We can easily generalize this to all rational sequences. So the question is:

Can this result be generalized to real sequences?

(Of course, complex sequences easily follows.) Note that it does not suffice to use the counting argument, since there are $$\beth^{\mathbb N}_1 = \beth_1$$ real sequences, which is equal to the number of elementary expressions. And the method we used before cannot be generalized, because similar encodings will almost always involve fiddling with digits, which leads to decoding functions containing dense discontinuities. And elementary functions can't be discontinuous on a dense set.

• @YvesDaoust Since $p_n < 10^n$ I know it has at most $n$ digits. So by allocating $n$ digits for the $n$-th prime I can keep track of that easily. Commented Jun 19, 2020 at 7:39
• Great question! I have a doubt about the rules of this game: are infinite sums of functions allowed? If not, how are the trigonometric functions elementary? If yes, then why is not the Taylor series for some differentiable function that passes through each $(n, a_n)$ the general answer to this problem? (We know there is such a function even if we can't construct it through any means). Or even better just $\sum_{i \in \mathbb N} a_i*g(x-i)$ where $g(0)=1$ and is $0$ for every other integer. Commented Jun 20, 2020 at 13:56
• The sequence of "Busy Beaver" numbers can be bounded by an elementary sequence? Commented Jun 21, 2020 at 2:10
• Exponentiation $f(x)^{g(x)}$ is redundant, since it's defined in terms of $\exp$ and $\ln$. Commented Jun 22, 2020 at 22:12
• @DanielV The elementary functions include all constant functions whose value is a complex number. Therefore there are uncountably many of them. Commented Jun 26, 2020 at 0:17

In my answer I am using the convention that the complex logarithm $$\log$$ is a holomorphic function (the "principal branch" of $$Log$$) defined on $${\mathbb C}\setminus (-\infty,0],$$ where $$(-\infty,0]\subset {\mathbb R}$$. Accordingly, each elementary function is a holomorphic function on its natural domain which is an open subset of $${\mathbb C}$$. In particular, the floor function $$x\mapsto \lfloor x \rfloor, x\in {\mathbb R}$$, is not regarded as a restriction of an elementary function in this answer.

I will not attempt to solve the problem where one uses discontinuous logarithmic function: Most likely, this can be done by considering multivalued holomorphic functions of several variables (single-valued holomorphic functions on Riemann domains over $${\mathbb C}^{k+1}$$), but that would require substantially more work.

Every elementary function $$f\in {\mathcal E}$$ of the complex variable $$z$$ is defined by a formula $$\varphi$$ and a set of constants $$c_1,..., c_k\in {\mathbb C}$$. Treating the constants as independent complex variables $$w_1,...,w_k$$, we see that $$\varphi$$ defines a holomorphic function $$F_{\varphi}=F(z,w_1,...,w_k)$$ of $$k+1$$ complex variables defined on some open subset $$\Omega$$ of $${\mathbb C}^{n+1}$$, its "natural domain." The original elementary function $$f$$ then is obtained by evaluating: $$f(z)= F(z,c_1,...,c_k)$$.

For most of the discussion below, I will fix $$\varphi$$; the discussion will only use the above description of $$f$$ in terms of a holomorphic function $$F$$ of several variables.

For each $$n\in {\mathbb N}$$, define $$\Omega_n=\{\underline{w}=(w_1,...,w_k): (n,w_1,...,w_k)\in \Omega\}$$.

Let $$\Omega_\omega$$ denote the infinite product $$\Omega_1\times \Omega_2\times ...,$$ equipped with the product topology. I will use the notation $$\Delta$$ for the (small) diagonal in $$\Omega_\omega$$. Then each $$\overline{w}=(\underline{w}, \underline{w},....)\in \Delta$$ defines the sequence $$\theta(\overline{w}): n\mapsto F(n,w)$$, $$\theta: \Delta \to Seq=Map({\mathbb N}, {\mathbb C}).$$

Remark. $$\Omega_\omega, \Delta$$ and $$\theta$$ of course depend on the original holomorphic function $$F$$.

I will equip the set of complex sequences $$Seq$$ with the following sup-metric: $$d(\eta,\zeta)= \sup_{n\in {\mathbb N}} \min(|\eta(n)-\zeta(n)|, 1).$$ This metric is complete because the space $$\ell_\infty$$ is complete: If $$d(\eta,\zeta)<1$$ then the difference $$\eta-\zeta$$ is a sequence in $$\ell_\infty$$.

Similarly to the map $$\theta$$ I will define maps $$\theta_n: M_n \to Map(\{1,...,n\}, {\mathbb C})\cong {\mathbb C}^n$$. Here $$M_n$$ is the (small) diagonal in the product $$\Omega_1\times ...\times \Omega_n$$; it is a complex manifold of dimension $$k$$.

The map $$\theta_n$$ sends each finite sequence $$\overline{w}=\underbrace{(\underline{w},..., \underline{w})}_{n~ \hbox{times}}$$ to the map
$$j\mapsto F(j, \underline{w}), j\in \{1,...,n\},$$ $$\underline{w}=(w_1,...,w_k)$$.

Lemma 1. For each natural number $$n > k$$, the image of $$\theta_n$$ has measure zero in $${\mathbb C}^n$$.

Proof. This is a very general fact: Since $$M_n$$ is a complex manifold of dimension $$k and the map $$\theta_n: M_n\to {\mathbb C}^n$$ is $$C^1$$-smooth (actually, holomorphic), hence, its image has measure zero. qed.

Corollary 1. For each compact $$K\subset \Omega_\omega$$ the image $$\theta(\Delta\cap K)$$ is nowhere dense in $$Seq$$.

Proof. By Lemma 1, for each $$n>k$$ the image $$\theta_n(K\cap \Delta\cap \Omega_1\times ...\times \Omega_n)$$ is compact and nowhere dense in $$Map(\{1,...,n\}, {\mathbb C})$$. By compactness of $$K$$, for each sequence $$\sigma\in cl(\theta(K\cap \Delta))\subset Seq$$, the restriction of $$\sigma$$ to the integer interval $$[1,n]$$ lies in $$\theta_n(K\cap \Delta)$$. Hence, by Lemma 1, $$\sigma|_{[1,n]}$$ is the limit of a sequence $$\zeta_j\in Map(\{1,...,n\}, {\mathbb C}) \setminus \theta_n(K\cap \Delta\cap \Omega_1\times ...\times \Omega_n),$$ $$\lim_{j\to\infty}\zeta_j= \sigma|_{[1,n]}.$$

Extending each finite sequence $$\zeta_j$$ to the interval $$[n+1,\infty)\cap {\mathbb N}$$ by $$\sigma|_{[n+1,\infty)}$$ we obtain a sequence $$\hat\zeta_j\in Seq$$ which converges to $$\sigma$$ and, at the same time, $$\hat\zeta_j\notin cl(\theta(K\cap \Delta))$$. qed.

Corollary 2. $$\theta(\Delta)$$ is a union of countably many subsets of $$Seq$$ which are nowhere dense in $$Seq$$.

Proof. Since each $$\Omega_n$$ is an open subset of $${\mathbb C}^k$$, there exists a sequence of compact subsets $$K_j\subset \Delta\subset \Omega_\omega$$ whose union is the entire $$\Delta$$, $$j\in {\mathbb N}$$. Thus, by Corollary 1, $$\theta(\Delta)$$ is the countable union of nowhere dense subsets $$\theta(K_j) \subset Seq.$$
qed.

Now, back to elementary functions. There are only countably many formulae $$\varphi$$ defining elementary functions. Each formula $$\varphi$$ defines a holomorphic function of several variables $$F_\varphi$$. For each $$F=F_\varphi$$, by Corollary 2, the image of $$\theta=\theta_F: \Delta_F\to Seq$$ is a countable union of nowhere dense subsets. Taking the union over all formulae $$\varphi$$, we conclude:

Corollary 3. The set of sequences of complex numbers defined by elementary functions is a countable union of nowhere dense subsets of $$Seq$$.

Thus, by the Baire Category Theorem, since $$(Seq,d)$$ is a complete metric space, we obtain:

Theorem. The set of sequences of complex numbers defined by elementary functions has empty interior in $$Seq$$.

• Doing this via topology is great thinking! I've always been trying methods similar to Liouville's theorem on integration. I'll award you the bonus when I'm fully sure you're correct. Commented Jun 26, 2020 at 1:46
• I think an argument like this should work, but there are some nontrivial subtleties. For instance, it's not clear to me what topology you want to define on $\mathcal{E}_{\kappa,r}$, given that different elements of $\mathcal{E}_{\kappa,r}$ have different domains (so what does "compacts in their domain" mean?). For instance, if you consider functions of the form $\log(x+c)$ where $c$ is a constant, you want this to form a continuously varying family as $c$ varies, but the domain changes with $c$ and it's not obvious what topology you can use to make this work out. Commented Jun 26, 2020 at 2:00
• It's also not clear to me why $\theta$ would be continuous--for instance, if you have a family of functions $f_c(x)=\sin(cx)$, then $c\mapsto (f_c(n))$ is not continuous as a map $\mathbb{R}\to\ell_\infty$ (each $f_c(n)$ varies continuously with $c$, but they don't do so uniformly in $n$). I think you can fix this by just using $\mathbb{C}^\omega$ with the product topology instead of $\ell_\infty$, which is still not $\sigma$-compact. Commented Jun 26, 2020 at 2:14
• I have not checked all the details of the new argument but the proof of Corollary 2 looks wrong. Each $\Omega_n$ is $\sigma$-compact but the infinite product of all of them will not be $\sigma$-compact. (Also, re the floor function, my description of the complex version of it was wrong: the complex version would instead be $\lfloor\operatorname{Re}(z)\rfloor$, on the domain of complex numbers with non-integer real part. This is holomorphic on its domain, since it is locally constant. (Note that you can get a similar function very simply as $z-\operatorname{Log}(\exp(z))$.) Commented Jun 26, 2020 at 17:46
• There are some details that are confusing me as written, but I think I see a simpler argument that works very cleanly. Can't you just consider the product measure on $Seq$ and deduce quite quickly from Lemma 1 that $\theta(\Delta)$ has measure $0$? Commented Jun 26, 2020 at 18:10