# Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers

Let $$a(n)$$ be the Dirichlet inverse of the Euler totient function:

$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$

and let the matrix $$T(n,k)$$ be: $$T(n,k)=a(\gcd(n,k)) \tag{2}$$

It has been proven by both joriki and GH from MO that
for $$n>1$$: $$\Lambda(n) = \sum\limits_{k=1}^{\infty}\frac{T(n,k)}{k} \tag{3}$$

Let $$M(n,k)$$ be the lower triangular matrix:

$$M(n,k)=\underset{m\geq k}{\sum _{m=1}^n} a(\gcd (m,k)) \tag{4}$$

Conjecture 1: For $$1 < k \leq n$$, for all $$n$$: $$\;\;\;\;-(k-1) \leq M(n,k) \leq (k-1)$$ Conjecture 2: $$\sum_{k=1}^{k=n} M(n,k) = 1$$

$$\sum _{k=2}^n \frac{M(n,k)}{k}=\sum _{m=1}^n \left(\underset{k \mid m}{\sum _{k=1}^m} H_k \mu \left(\frac{m}{k}\right)-1\right) \tag{5}$$

I am interested in investigating:

$$\sum _{k=2}^x \frac{M(x,k)}{k} < C\left\lfloor x^{1/2+\epsilon}+\frac{1}{2}\right\rfloor \tag{6}$$

Therefore we form the linear programming problem $$(7)$$:

$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{k=1}^{k=n} \frac{y_{k}}{k} \\ \text{subject to constraints:} & n + \displaystyle\sum_{k=2}^{k=n}y_{k}=1 \\ & y_1 \geq -1 \\ \text{and for k>1:} & M(n,k) \leq y_k \leq M(n,k) & \tag{7} \end{array}$$ The solution to the linear programming problem $$(7)$$ (blue dots) will automatically coincide with LHS of $$(6)$$ (the red lines) as shown in this graph:

Because of the answer to this question here proven by Marcus Ritt and the other parallell answer here by Maxim, I find it natural to ask whether the output (the blue lines) from the following linear programming problem $$(8)$$ is greater than $$(7)$$. In the program I made the change that I put the upper variable bound to $$0$$ and the lower variable bound to the negated absolute value of the entries in the lower triangular matrix $$M(n,k)$$.

$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{k=1}^{k=n} \frac{y_{k}}{k} \\ \text{subject to constraints:} & n + \displaystyle\sum_{k=2}^{k=n}y_{k}=1 \\ & y_1 \geq -1 \\ \text{and for k>1:} & -|M(n,k)| \leq y_k \leq 0 & \tag{8} \end{array}$$

Can anything be said whether there exist a constant $$C$$ such that:
$$C$$ times the output from LP-problem $$(8)$$ $$\geq$$ The output from LP-problem $$(7)$$?

Or put in pictures. Is there a constant $$C$$ such that the irregular red curve is bounded by the irregular blue curve? That for $$C$$, however large, say $$C=1000$$ or greater.

What we do know given conjecture 1 above which implies that $$-|M(n,k)| \geq -(k-1)$$, is that the wiggly blue curve below is bounded by the smooth continuous blue curve $$f(x)$$:

From the answer at the operations research forum we also know that the solutions to the linear programming problem:

$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{k=1}^{k=n} \frac{y_{k}}{k} \\ \text{subject to constraints:} & n + \displaystyle\sum_{k=2}^{k=n}y_{k}=1 \\ & y_1 \geq -1 \\ \text{and for k>1:} & -(k-1) \leq y_k \leq 0 & \tag{9} \end{array}$$

is the continuous blue curve $$f(x)$$ and it is asymptotic to:

$$f(x)=C\left(-\left\lfloor \sqrt{2 (x-1)}+\frac{1}{2}\right\rfloor +H_{\left\lfloor \sqrt{2 (x-1)}+\frac{1}{2}\right\rfloor } + \text{Binomial term} \right) \tag{10}$$

($$C=2$$ was multiplied with later). Anyways, the the solutions to $$(8)$$ are always bounded by the solutions to $$(9)$$. The question is whether the solutions to $$(7)$$ are bounded by the solutions to $$(8)$$?

The binomial term can be found in the OEIS.

Edit: Minor error: $$f(x)$$ should have been $$f(n)$$ to suit the linear programming problem.

The answer, if it is to be found, lies in comparing this matrix from the solution of the Linear Programming tagged $$(8)$$ starting:

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

with the matrix from the solution of the Linear Programming tagged $$(7)$$ which essentially is the matrix $$M$$ except for the first column, starting: $$\begin{array}{llllllllllllllllll} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 0 & -2 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -1 & -1 & -1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 0 & 0 & 0 & -4 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -1 & -2 & -1 & -3 & 2 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 0 & -1 & 0 & -2 & 3 & -6 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -1 & 0 & -1 & -1 & 2 & -5 & -1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 0 & -2 & 0 & 0 & 0 & -4 & 0 & -2 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -1 & -1 & -1 & -4 & -1 & -3 & -1 & -1 & 4 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 0 & 0 & 0 & -3 & 0 & -2 & 0 & 0 & 5 & -10 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -1 & -2 & -1 & -2 & 2 & -1 & -1 & -2 & 4 & -9 & 2 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & 0 & -1 & 0 & -1 & 3 & 0 & 0 & -1 & 5 & -8 & 3 & -12 & \text{} & \text{} & \text{} & \text{} & \text{} \\ 1 & -1 & 0 & -1 & 0 & 2 & -6 & -1 & 0 & 4 & -7 & 2 & -11 & 6 & \text{} & \text{} & \text{} & \text{} \\ 1 & 0 & -2 & 0 & -4 & 0 & -5 & 0 & -2 & 0 & -6 & 0 & -10 & 7 & 8 & \text{} & \text{} & \text{} \\ 1 & -1 & -1 & -1 & -3 & -1 & -4 & -1 & -1 & -1 & -5 & -1 & -9 & 6 & 9 & -1 & \text{} & \text{} \\ 1 & 0 & 0 & 0 & -2 & 0 & -3 & 0 & 0 & 0 & -4 & 0 & -8 & 7 & 10 & 0 & -16 & \text{} \\ 1 & -1 & -2 & -1 & -1 & 2 & -2 & -1 & -2 & -1 & -3 & 2 & -7 & 6 & 8 & -1 & -15 & 2 \end{array}$$

Associated Mathematica program: https://pastebin.com/rHaXxVcj

Edit: 25.11.2019:

I am not entirely sure but I believe the question approximately boils down to:

Let: $$a(n)=\sum\limits_{d \mid n} \mu(d)d$$

Prove or disprove that there exists a constant $$c$$ such that the inequality: $$\sum\limits_{r=2}^{n} \frac{\sum\limits_{m=r}^{n} a(\gcd (m,r))}{r} \geq c\underset{\sum\limits_{k=2}^{r} -\left|\sum\limits_{m=k}^{n} a(\gcd (m,k))\right|\geq -(n-1)}{\sum _{r=2}^n} -\frac{\left|\sum\limits_{m=r}^{n} a(\gcd (m,r))\right|}{r} \tag{11}$$

holds for all $$n$$

I am asking because it has been proven that the right hand side is bounded from below by:

$$c\left(-\left\lfloor \sqrt{2 (n-1)}+\frac{1}{2}\right\rfloor +H_{\left\lfloor \sqrt{2 (n-1)}+\frac{1}{2}\right\rfloor } + \text{Binomial term} \right)$$

Mathematica:

Clear[a, b, nn];
nn = 60;
a[n_] := Total[MoebiusMu[Divisors[n]]*Divisors[n]];
Monitor[a1 =
Table[Sum[Sum[a[GCD[m, r]], {m, r, n}]/r, {r, 2, n}], {n, 1,
nn}];, n]
g1 = ListLinePlot[a1, PlotStyle -> {Red, Thick}];
Monitor[a2 =
Table[Sum[
If[Sum[-Abs[Sum[a[GCD[m, k]], {m, k, n}]], {k, 2,
r}] >= -(n - 1), -Abs[Sum[a[GCD[m, r]], {m, r, n}]]/r,
0], {r, 2, n}], {n, 1, nn}];, n]
g2 = ListLinePlot[a2, PlotStyle -> {Thick}];
Show[g2, g1]


It is as said conjectured that the blue curve times a constant is greater than the red curve. The blue curve is bounded from below by a function whose leading term is the floor function of a square root.

Same graph as above but for a 1000 times 1000 sized matrix:

Edit 30.4.2020: More efficient program and plot:

(*start*)
(*Mathematica*)
Clear[a];
nn = 2000;
constant = 2*Sqrt[2];
a[n_] := Total[Divisors[n]*MoebiusMu[Divisors[n]]];
Monitor[TableForm[
A = Accumulate[
Table[Table[If[n >= k, a[GCD[n, k]], 0], {k, 1, nn}], {n, 1,
nn}]]];, n]
TableForm[AB = Transpose[A]/Range[nn]];
AB[[1, All]] = 0;
g1 = ListLinePlot[Abs[Total[AB]], PlotStyle -> Red];
Clear[AB];
TableForm[B = -Abs[A]];
Clear[A];
B[[All, 1]] = Range[nn];
TableForm[B1 = Sign[Transpose[Accumulate[Transpose[B]]]]];
Clear[B]
Quiet[Show[
ListLinePlot[
v = ReplaceAll[
Flatten[Table[First[Position[B1[[n]], -1]], {n, 1, nn}]],
First[{}] -> 1], PlotStyle -> Blue],
Plot[constant*Sqrt[n], {n, 1, nn}, PlotStyle -> {Pink, Thick}], g1,
ImageSize -> Large]]
ListLinePlot[v/(constant*Sqrt[Range[nn]])];
(*end*)


The pink curve is 2*Sqrt(2)*Sqrt(x):

First, we have $$\begin{split} \sum_{k=1}^n M(n,k) &= \sum_{k=1}^n \sum_{m=k}^n \sum_{d|\gcd(m,k)} d\cdot\mu(d) \\ &= \sum_{m=1}^n \sum_{k=1}^m \sum_{d|\gcd(m,k)} d\cdot\mu(d). \end{split}$$
Second, denoting $$g:=\gcd(m,k)$$ and $$k':=\frac{k}{g}$$, we get: $$\begin{split} \ldots &= \sum_{m=1}^n \sum_{g|m} \sum_{k'=1\atop \gcd(k',m/g)=1}^{m/g} \sum_{d|g} d\cdot\mu(d) \\ &= \sum_{m=1}^n \sum_{g|m} \sum_{d|g} d\cdot\mu(d)\cdot\varphi(\frac{m}{g}), \end{split}$$ where $$\varphi(\cdot)$$ is Euler's totient function.
Introducing $$g':=\frac{g}{d}$$ and recalling formula (15), we finally get: $$\begin{split} \ldots &= \sum_{m=1}^n \sum_{d|m} \sum_{g'|m/d} d\cdot\mu(d)\cdot\varphi(\frac{m}{g'd}) \\ &= \sum_{m=1}^n \sum_{d|m} d\cdot\mu(d)\cdot\frac{m}{d} \\ &= \sum_{m=1}^n m \sum_{d|m} \mu(d) \\ &= \sum_{m=1}^n m\cdot \delta_{m,1} \\ &= 1. \end{split}$$