Given $k$, $f(x) = e^{x_1}+e^{x_1+x_2}+\cdots+e^{x_1+x_2+\cdots+x_k},$ $x=(x_1,x_2,\ldots,x_k),$ where $x_i \in \{0,1\}$.

We want to compute: $\inf_{x \neq y}|f(x)-f(y)|$ or a lower bound of $\inf_{x \neq y} |f(x)-f(y)|$.

Now I just know that $f$ is an injection when $x$ is rational. Anyone know if there is an analytic solution of this?

  • $\begingroup$ Let $g(k)$ denote that minimum. Then clearly $g(k)$ is decreasing, and it likely decreases to 0. I bet how quickly it does so will probably depend on the fact that $e$ is transcendental, and the continued fraction decomposition very well may come into play. $\endgroup$ – Pat Devlin Jan 29 '17 at 22:51

Evaluating the minimum $\delta_k:=\min_{x\neq y}|f(y)-f(x)|$ over distinct strings $x, y\in \{0,1\}^k$ seems a hard diophantine problem. It is quite cheap to prove that $\delta_k$ is $O(1/k)$ and decreasing, so that in particular the infimum over all finite strings is zero; actually, it's zero even among strings $x$ and $y$ with at most $2$ non-zero coordinates.

For positive integers $p,q$ consider the strings $x:=1\ 0^{p+q}$ and $y:=0^q\ 1^2\ 0^{p-1}$ of length $k:=p+q+1$. One has $f(x)=(p+q+1)e$ and $f(y)=q+e+pe^2$, so $fy)-f(x)=pe^2-(p+q)e+q=(e-1)(pe-q)$. By Dirichlet's approximation theorem, $|pe-q|$ can be made less than $1/n$ by some $1\le q\le n$, and $p=O(q)$, from which it follows $\delta_k=O(1/k)$.


I'm confused. Why not $x = 0$ and $y=(0, 0, \ldots , 0, 1)$? This has $f(y) - f(x) = e -1$, which is clearly best possible [though not unique]. (As you note, $f$ is an injection, so different strings must have at least one of these summands different, and the closest they can be is $e^1 - e^0$.)

Edit: as pointed out in the comments, the above is by no means a proof. (All the same, I still put it forward as a conjecture.)

Second edit: I now see (again from the comments) that the above conjecture is not at all correct, and the problem is still very much open!

  • $\begingroup$ It is not clear to me that $e-1$ is the best possible... In fact, I don't think it is true: f(x)-f(y) is a polynomial with integer coefficients evaluated in $e$, that could be very small, for $k$ large. $\endgroup$ – Pietro Majer Jan 29 '17 at 22:19
  • $\begingroup$ Oh. I see what you mean. Sorry about that. All the same, I feel like being bold and conjecturing that my answer is still correct. I'll think on a proof. $\endgroup$ – Pat Devlin Jan 29 '17 at 22:24
  • 2
    $\begingroup$ For instance, for $k=12$, the strings $y:=(000000001100)$ and $x:=(100000000000)$ produce respectively $f(y)=8+e+3e^2$ and $f(x)=12e$, so $f(y)-f(x)=8-11e+3e^2=0.26...$ $\endgroup$ – Pietro Majer Jan 29 '17 at 22:45
  • $\begingroup$ Ok. Great example. (Perhaps you could add that to the original post) $\endgroup$ – Pat Devlin Jan 29 '17 at 22:47
  • $\begingroup$ I think it's related to transcend number theory $\endgroup$ – Jun Li Jan 29 '17 at 23:54

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.