# Integer programming of free energy

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?

• 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. – 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!

• 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. – Pietro Majer Jan 29 '17 at 22:19
• 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. – Pat Devlin Jan 29 '17 at 22:24
• 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...$ – Pietro Majer Jan 29 '17 at 22:45
• Ok. Great example. (Perhaps you could add that to the original post) – Pat Devlin Jan 29 '17 at 22:47
• I think it's related to transcend number theory – Jun Li Jan 29 '17 at 23:54