5
$\begingroup$

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<p$, 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).

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Dec 23 '20 at 10:34
  • $\begingroup$ 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$. $\endgroup$ – Lieuwe Vinkhuijzen Dec 23 '20 at 11:22
6
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ 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$. $\endgroup$ – Lieuwe Vinkhuijzen Dec 23 '20 at 9:35
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Dec 23 '20 at 10:09
  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Dec 23 '20 at 12:26
  • $\begingroup$ Thanks a lot! This is a great reference. $\endgroup$ – Lieuwe Vinkhuijzen Dec 23 '20 at 12:34
  • $\begingroup$ 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. $\endgroup$ – Lieuwe Vinkhuijzen Feb 9 at 15:06
4
$\begingroup$

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 look very closely related, and might possibly be directly applicable.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.