<p>This is impossible. No finite number of bits of <span class="math-container">$f(a_0,\dots,a_n)$</span> suffices to determine any of <span class="math-container">$a_0,\dots,a_n$</span>; in fact, any nondegenerate real interval contains the values <span class="math-container">$f(a_0,\dots,a_n)$</span> for infinitely many vectors <span class="math-container">$(a_0,\dots,a_n)\in\mathbb Z^{n+1}$</span>, and this holds even you fix all but two of the <span class="math-container">$a_0,\dots,a_n$</span> in advance.</p>

CC BY-SA 4.0
2020-12-23T09:35:45.440Z
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
CC BY-SA 4.0
2020-12-23T10:09:55.810Z
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
CC BY-SA 4.0
2020-12-23T12:26:40.577Z
It is easy to check that explicit versions of [Baker's theorem](https://en.wikipedia.org/wiki/Baker%27s_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
CC BY-SA 4.0
2020-12-23T12:34:00.013Z
Thanks a lot! This is a great reference.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2021-02-09T15:06:33.220Z
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
CC BY-SA 4.0
2021-02-09T16:48:30.430Z
$(\log\max_ka_k)^{-O(1)}$ would be polylogarithmically many zeros; polynomially many zeros amounts to a bound $\exp(-(\log\max_ka_k)^{O(1)})$. As far as I remember, I only used the bounds referenced in the Wikipedia article, but I would first have to recall how exactly the argument went (it’s been several weeks).
Emil Jeřábek
CC BY-SA 4.0
2021-02-09T18:38:15.497Z
Hmm. I’m having trouble finding a completely explicit reference, as many of the results are only stated for homogeneous forms. There is something wrong with the bound in https://mathscinet.ams.org/mathscinet-getitem?mr=0498417 (I can only access the review), because for $n=1$ it degenerates ($\Omega'=1$, thus the bound as stated is just $|\Lambda|>1$, which cannot be true). Note that the bound we need here is on $|1-\log\alpha_i|$, where $\sum_{i\le n}a_ix^i=a_n\prod_{i<n}(x-\alpha_i)$; this would imply bounds on $|e-\alpha_i|$, which in turn give a bound on $|\sum_ia_ie^i|$.
Emil Jeřábek
CC BY-SA 4.0
2021-02-10T15:55:35.560Z
That is, my suggestion is to try to locate a copy of Baker's paper "The theory of linear forms in logarithms" (MR0498417) in a library and try to find out what exactly happens with the bound if $n=1$ (there's likely some condition omitted in the review). Assuming for the moment that it holds with $\Omega$ in place of $\Omega'$, this will give in your notation $\log|f(a_0,\dots,a_n)|>-Cn^{201}b(\log b)^2$, where $b=\log\max_k|a_k|$, and $C$ is $16^{200}\log2$ or so.
Emil Jeřábek
CC BY-SA 4.0
2020-12-23T06:59:19.387Z
2020-12-23T06:59:19.387Z
Emil Jeřábek
<p>If you know that the <span class="math-container">$a_i$</span>'s are all not too large, and you have a good approximation to <span class="math-container">$f(a_0,\dots,a_n)$</span>, I think LLL lattice basis reduction could be applicable (I haven't tried to verify the details).</p>
<p>Algorithms for <a href="https://en.wikipedia.org/wiki/Integer_relation_algorithm" rel="noreferrer">finding integer relations</a> look very closely related, and might possibly be directly applicable.</p>

CC BY-SA 4.0
2020-12-23T05:20:04.157Z
2020-12-23T05:20:04.157Z
D.W.
<p>Since <span class="math-container">$e$</span> is transcendental, the function <span class="math-container">$f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$</span> is injective,</p>
<p><span class="math-container">$$ 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$$</span></p>
<p>Since <span class="math-container">$f$</span> is injective, in principle, the numbers <span class="math-container">$a_i$</span> can be deduced given the output of <span class="math-container">$f$</span>.
And since the numbers <span class="math-container">$a_i$</span> are non-negative, any interval of the real numbers intersects the codomain of <span class="math-container">$f$</span> on only finitely many points.<span class="math-container">$^*$</span></p>
<p>I'm wondering whether, in practice, the integer coefficients <span class="math-container">$a_i$</span> can be recovered from the value of <span class="math-container">$f$</span>. Does it suffice to have only polynomially many (in <span class="math-container">$n$</span>) bits of <span class="math-container">$f$</span>? (i.e., polynomial in <span class="math-container">$n$</span>). And can this be done in polynomial time?</p>
<p>There is an exponential-time algorithm, namely: Simply enumerate all <span class="math-container">$a$</span> for which <span class="math-container">$f(a)\leq t$</span> for a given target value <span class="math-container">$t$</span>. In fact, in my application I know that <span class="math-container">$a_0+a_1+\cdots +a_n = 2^n$</span>, so the enumeration is quite simple.</p>
<hr />
<p>I have the same question for</p>
<p><span class="math-container">$$g(a_0,a_1,\ldots, a_n) = \sum_{k=0}^ne^{\frac{i\pi}{p}k}a_k$$</span></p>
<p>In my application, I can choose <span class="math-container">$p$</span>, e.g., a prime with <span class="math-container">$2n&lt;p$</span>, so that the contributions all lie in the north-east region of the complex plane.</p>
<p><span class="math-container">$^*$</span> (Thanks to Emil Jerabek for pointing out that, without that constraint, <span class="math-container">$f$</span> cannot be computed from finitely many bits).</p>

CC BY-SA 4.0
2020-12-23T10:34:10.433Z
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
CC BY-SA 4.0
2020-12-23T11:22:22.110Z
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
<cc.complexity-theory><time-complexity><nt.number-theory><polynomial-time>
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
Lieuwe Vinkhuijzen
# Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?

(Asked by: username_0 on 2020-12-22)

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).

**Tags:** cc.complexity-theory, time-complexity, nt.number-theory, polynomial-time

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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$.  

---

## 2 answers

### Answer by username_2 on 2020-12-23. Score: 6

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.

> **Comments:**
> **username_0**: 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$.  
> **username_2**: 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.  
> **username_2**: It is easy to check that explicit versions of [Baker's theorem](https://en.wikipedia.org/wiki/Baker%27s_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.  
> **username_0**: Thanks a lot! This is a great reference.  
> **username_0**: 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.  
> **username_2**: $(\log\max_ka_k)^{-O(1)}$ would be polylogarithmically many zeros; polynomially many zeros amounts to a bound $\exp(-(\log\max_ka_k)^{O(1)})$. As far as I remember, I only used the bounds referenced in the Wikipedia article, but I would first have to recall how exactly the argument went (it’s been several weeks).  
> **username_2**: Hmm. I’m having trouble finding a completely explicit reference, as many of the results are only stated for homogeneous forms. There is something wrong with the bound in https://mathscinet.ams.org/mathscinet-getitem?mr=0498417 (I can only access the review), because for $n=1$ it degenerates ($\Omega'=1$, thus the bound as stated is just $|\Lambda|>1$, which cannot be true). Note that the bound we need here is on $|1-\log\alpha_i|$, where $\sum_{i\le n}a_ix^i=a_n\prod_{i<n}(x-\alpha_i)$; this would imply bounds on $|e-\alpha_i|$, which in turn give a bound on $|\sum_ia_ie^i|$.  
> **username_2**: That is, my suggestion is to try to locate a copy of Baker's paper "The theory of linear forms in logarithms" (MR0498417) in a library and try to find out what exactly happens with the bound if $n=1$ (there's likely some condition omitted in the review). Assuming for the moment that it holds with $\Omega$ in place of $\Omega'$, this will give in your notation $\log|f(a_0,\dots,a_n)|>-Cn^{201}b(\log b)^2$, where $b=\log\max_k|a_k|$, and $C$ is $16^{200}\log2$ or so.  

---

### Answer by username_3 on 2020-12-23. Score: 5

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).

Algorithms for [finding integer relations](https://en.wikipedia.org/wiki/Integer_relation_algorithm) look very closely related, and might possibly be directly applicable.


---

