Prove that this linear programming problem is bounded by $O(k^{1/2})$

Question

The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:

$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{n=1}^{n=k} \frac{x_{n}}{n} \\ \text{subject to constraints:} & k + \displaystyle\sum_{n=2}^{n=k}x_{n}=1 \\ & x_1 \geq -1 \end{array}$$

$n>1:$

$$-2(n-1) \leq x_n \leq 0 \tag{4}$$

That is, there is one linear programming problem for each $k$.

Based on a OEIS search, the solutions $f(k)$ to the linear programming problems (without the first column) appear to have the asymptotic:

$$f(k)=-\left(2 \sqrt{k}-2 \log \left(\sqrt{k}+1\right)-2 \gamma +1\right) \tag{5}$$ Is it true?

Please don't be so harsh on me. If the problem is ill defined in the latex I post the short Mathematica program from which I defined the optimization problem.

(*start*)
nn = 180;
TableForm[
  L2 = Table[
    LinearProgramming[
     Table[1/n, {n, 1, k}], {Table[If[n == 1, k, 1], {n, 1, k}]}, {{1,
        0}}, Table[
      If[n == 1, {-1, 1}, {-2 (n - 1), 0 (n - 1)}], {n, 1, k}]], {k, 
     1, nn}]];
t1 = Table[Sum[L2[[n, k]]/k, {k, 2, n}], {n, 2, nn}];
t2 = Table[-(2*k^(1/2) + 1 - 2*Log[k^(1/2) + 1] - 2*EulerGamma), {k, 
    2, nn}];
Show[ListLinePlot[t1], ListLinePlot[t2, PlotStyle -> Red]]
ListLinePlot[t1/t2]

The blue curve is the linear programming minimum and the red curve is the asymptotic.

The ratio between the linear programming minimum and the asymptotic tends to one.

So as I said this is NOT a bound on the partial sums of the Möbius inverse of the Harmonic numbers.

The solutions $x_n..x_k$ to the $k$-th linear programming problem form a number triangle:

$$\begin{array}{llllllllllll} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -2 & 0 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -2 & -1 & 0 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -2 & -2 & 0 & 0 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -2 & -3 & 0 & 0 & 0 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -2 & -4 & 0 & 0 & 0 & 0 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -2 & -4 & -1 & 0 & 0 & 0 & 0 & \text{} & \text{} & \text{} & \text{} \\ 1 & -2 & -4 & -2 & 0 & 0 & 0 & 0 & 0 & \text{} & \text{} & \text{} \\ 1 & -2 & -4 & -3 & 0 & 0 & 0 & 0 & 0 & 0 & \text{} & \text{} \\ 1 & -2 & -4 & -4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \text{} \\ 1 & -2 & -4 & -5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}$$

The first column is here equal to the all ones sequence because Mathematicas linear programming command seems to require it. But setting the constraint to begin with $k$ (in the linear program in the beginning of the question) makes it equivalent to the first column in the numerators for partial sums of the Möbius inverse of the Harmonic numbers.

Counting only the negative entries in each row we find with a OEIS search that their number appear to be nearest integer to square root of $n$, and from there it becomes easy to conjecture formula $(5)$.

Notice also that for all $k$:

$$\left\lfloor k^{\text{epsilon}+\frac{1}{2}}+\frac{1}{2}\right\rfloor=\left\lfloor \sqrt{k}+\frac{1}{2}\right\rfloor$$ holds for sufficiently small epsilons.

The partial sums of the Möbius inverse of the Harmonic numbers have the numerators:

$$J(m,k)=\begin{array}{lllllll} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & -1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & -2 & 0 & 0 & 0 & 0 \\ 4 & -1 & -1 & -1 & 0 & 0 & 0 \\ 5 & 0 & 0 & 0 & -4 & 0 & 0 \\ 6 & -1 & -2 & -1 & -3 & 2 & 0 \\ 7 & 0 & -1 & 0 & -2 & 3 & -6 \end{array}$$

given by the sum:

$$\sum _{n=1}^m \text{If}[n\geq k,a(\gcd (n,k)),0]$$

for
$n=1..m$,
$k=1..N$,
$m=1..N$. and where $a(n)$ is the Dirichlet inverse of the Euler totient function.

The properties are:

$$\sum_{k=1}^{k=n} \frac{J(n,k)}{k}=\lim_{s\to 1+} \sum_{m=1}^{m=N}H_m \sum_{d\mid m}\frac{\mu(d)}{d^{s-1}}$$ which is the partial sums of the Möbius inverse of the m-th harmonic number

$$\sum_{k=1}^{k=n}J(n,k)=1$$ as in the constraint in the linear programming problem. $$J(n,1)=n$$ as in the linear programming problem (but in the linear programming problem it is in the constraint and not the goal function because of some Mathematica technicality.)

The last property, for all $n$:

$$-2(k-1) \leq J(n,k) \leq 2(k-1)$$

is conjectural and differs from the linear programming problem. This last conjectural property should not be too hard to prove.

(*Numerators of the partial sums of the Möbius inverse of the \
Harmonic numbers*)(*start*)
Clear[T, n, k, a];
nn = 7;
a[n_] := If[n < 1, 0, Sum[d MoebiusMu@d, {d, Divisors[n]}]]
TableForm[
 M = Table[
   Table[Sum[If[n >= k, a[GCD[n, k]], 0], {n, 1, m}], {k, 1, nn}], {m,
     1, nn}]]
(*end*)

Answer 1

I assume the problem is as defined by the Mma code, that is, it has the constraints $k x_1 + \sum_{k = 2}^n x_k = 1$ and $-1 \leq x_1 \leq 1$. The problem is then equivalent to minimizing $$G = \frac 1 k + \sum_{i = 2}^k \left( \frac 1 i - \frac 1 k \right) x_i$$ with the constraints $$-2 (i - 1) \leq x_i \leq 0, \quad 2 \leq i \leq k, \\ -1 \leq C \leq 1, \quad C = \frac 1 k - \frac 1 k \sum_{i = 2}^k x_i.$$ The solution $P$ coincides with what would be given by the greedy algorithm starting from $x_2$: $$x_i = -2 (i - 1), \quad 2 \leq i \leq m, \\ x_{m + 1} = 1 - k - m + m^2, \\ x_i = 0, \quad m + 2 \leq i \leq k, \\ m = \left \lceil \frac {\sqrt {4 k - 3} - 1} 2 \right \rceil.$$ $m$ is chosen in such a way that $C = 1$ and $-2 m \leq x_{m + 1} < 0$. The edges incident to the vertex $P$ are given either by varying one coordinate $x_i$ and holding other coordinates fixed or by varying two coordinates $x_i$ and $x_j$ with $i < j$ and holding $x_i + x_j$ and other coordinates fixed. Moving away from $P$ along an edge of the first type decreases $G$ only if $x_i$ decreases, but then $C$ increases, which is impossible. Moving away from $P$ along an edge of the second type decreases $G$ only if $x_i$ decreases and $x_j$ increases, which is impossible for $P$. Therefore $P$ is optimal.

Since $m = (\sqrt {4 k - 3} - 1)/2 + O(1)$, we obtain $$G = -2 \sqrt k + \ln k + 2 \gamma + O(k^{-1/2}).$$