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.
Best Answer
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<n$ 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$.