Mixed integer program and continuous Diophantine approximation

Question

Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.

$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$

subject to :

• $\left\lvert\left(\frac{\ln(j)}{2\pi}\right)t - z_j\right\rvert \leq \frac{r}{2\pi} \quad \text{ for } 2 \leq j \leq n$.

• $z_j\geq 0 \quad \text{ for } 2 \leq j \leq n$.

• $\sum_{j=2}^n z_j \geq 1$.

• $t \geq 0$.

Note that $(z_j)_{j=2}^n$ is a non-zero vector of natural numbers. Suppose, we write the optimal value $t^*$ as a function of $n$ and $r$ i.e. say $t^* = t^*(n,r)$.

1. How does $t^*(n,r)$ depend on $n$ and $r$?

2. Is it independent of $n$ and only dependent on $r$?

3. Is it polynomial or exponential in $n$?

4. Could we derive a good upper bound for $t^*(n,r)$?

Answer 1

It certainly depends on both $n$ and $r$. Here are plots of $t^*(n,r)$ for $n\in\{2,3,4,5\}$ and $r\in\{0.01,0.02,\dots,0.99\}$, obtained via mixed integer linear programming.

$$n=2$$

---

$$n=3$$

---

$$n=4$$

---

$$n=5$$