# Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?

Since $$e$$ is transcendental, the function $$f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$$ is injective,

$$f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots a_ne^n$$

Since $$f$$ is injective, in principle, the numbers $$a_i$$ can be deduced given the output of $$f$$. And since the numbers $$a_i$$ are non-negative, any interval of the real numbers intersects the codomain of $$f$$ on only finitely many points.$$^*$$

I'm wondering whether, in practice, the integer coefficients $$a_i$$ can be recovered from the value of $$f$$. Does it suffice to have only polynomially many (in $$n$$) bits of $$f$$? (i.e., polynomial in $$n$$). And can this be done in polynomial time?

There is an exponential-time algorithm, namely: Simply enumerate all $$a$$ for which $$f(a)\leq t$$ for a given target value $$t$$. In fact, in my application I know that $$a_0+a_1+\cdots +a_n = 2^n$$, so the enumeration is quite simple.

I have the same question for

$$g(a_0,a_1,\ldots, a_n) = \sum_{k=0}^ne^{\frac{i\pi}{p}k}a_k$$

In my application, I can choose $$p$$, e.g., a prime with $$2n, so that the contributions all lie in the north-east region of the complex plane.

$$^*$$ (Thanks to Emil Jerabek for pointing out that, without that constraint, $$f$$ cannot be computed from finitely many bits).

• The reason you give in your first sentence is insufficient for injectivity of $f$. The correct reason is that $e$ is transcedental, and therefore not a zero of a polynomial. Also, it is not clear from the question whether $n$ is fixed. – Andrej Bauer Dec 23 '20 at 10:34
• Yes, thanks. We can think of $n$ as the size of the problem, in the sense that I wish to know whether we only need $poly(n)$ many bits of $f$ in order to determine the values of $a$. – Lieuwe Vinkhuijzen Dec 23 '20 at 11:22

This is impossible. No finite number of bits of $$f(a_0,\dots,a_n)$$ suffices to determine any of $$a_0,\dots,a_n$$; in fact, any nondegenerate real interval contains the values $$f(a_0,\dots,a_n)$$ for infinitely many vectors $$(a_0,\dots,a_n)\in\mathbb Z^{n+1}$$, and this holds even you fix all but two of the $$a_0,\dots,a_n$$ in advance.
• Thanks; in hindsight, that is obvious. I should have mentioned that, in my application, all the $a_i$ are non-negative, so this degenerate case is avoided. In this case, any real interval only contains finitely many values of $f$. – Lieuwe Vinkhuijzen Dec 23 '20 at 9:35
• I see. I’m not sure how to directly exploit nonnegativity, but bounds such as $|a_i|\le2^n$ might be enough to get an efficient solution; I’ll think about it. – Emil Jeřábek Dec 23 '20 at 10:09
• It is easy to check that explicit versions of Baker's theorem indeed imply that an approximation of $f(a_0,\dots,a_n)$ to $\mathrm{poly}(n,\log B)$ bits of precision is enough to uniquely determine the input among $(a_0,\dots,a_n)\in\{-B,\dots,B\}^{n+1}$. Now, the question is if we can also compute it efficiently. The first place to look at is the LLL algorithm as already mentioned in the other answer, but I have to stop now. – Emil Jeřábek Dec 23 '20 at 12:26
• Thanks again for the answer; we are having some trouble locating explicit versions of Baker's theorem. Therefore, if you would be so kind as to provide a reference, we would be much obliged. A modest statement would suffice, I believe, namely that $\left| \sum_{k}^na_ke^k \right|$ is bounded away from $0$ by at least $\text{polylog}\left(1/\max_k a_k\right) = \text{log}(\max_k a_k)^{-O(1)}$ whenever the $a_k$ are not all zero, i.e., the value is of the form $0.000...0x$ for only polynomially many zeroes. – Lieuwe Vinkhuijzen Feb 9 at 15:06
If you know that the $$a_i$$'s are all not too large, and you have a good approximation to $$f(a_0,\dots,a_n)$$, I think LLL lattice basis reduction could be applicable (I haven't tried to verify the details).