6
$\begingroup$

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:

Linear Programming M(n,k) and M(n,k) as variable bounds

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)$:

All 3 curves together

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]

blue curve times constant is conjecctured to be greater than red curve

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:

Partial sums of Möbius inverse of Harmonic numbers vs Square root bounded sequence

motivation for linear programming problem

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):

10000 times 10000 matrix

$\endgroup$
7
$\begingroup$

Here is a proof of Conjecture 2.

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}

| cite | improve this answer | |
$\endgroup$

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.