# What is the asymptotic of the irregular blue curve? Is it $(8x)^{1/2}$ or is it something else?

From Terry Tao's post here there is the statement:

"Conversely, if one can somehow establish a bound of the form

$$\displaystyle \sum_{n \leq x} \Lambda(n) = x + O( x^{1/2+\epsilon} ) \tag{1}$$

for any fixed $${\epsilon}$$, then the explicit formula can be used to..."

I don't know about the word "fixed", but the irregular behaviour of the blue curve below gives plenty of room for an $${\epsilon}$$, if it is true that the asymptotic is $$(8x)^{1/2}$$, and if it is also true that it bounds the partial sums of the Möbius transform of the Harmonic numbers minus $$x$$. But we don't know and can't conclude any such bounds from this question. I am only asking about the asymptotics of a certain sum that is connected to / a truncated absolute value version of the numerators of the expansion of the primes.

Let:

$$\varphi^{-1}(n) = \sum_{d \mid n} \mu(d)d \tag{2}$$

Then for $$n>1$$:

$$\Lambda(n) = \sum\limits_{k=1}^{\infty}\frac{\varphi^{-1}(\gcd(n,k))}{k} \tag{3}$$

Form the table: $$A(n,k)=\sum_{\substack{i=k\\\ n \geq k}}^n \varphi^{-1}(\gcd (i,k)) \tag{4}$$

From numerical evidence it appears that:

$$\sum _{k=1}^{x} \text{sgn}\left(\left(\text{sgn}\left(x+\sum _{j=2}^k -|A(x,j)|\right)+1\right)\right)+1 \sim (8x)^{1/2} \tag{5}$$

Is it true or is the asymptotic something else?

Question:

The complicated sign formula in $$(5)$$ comes from what we are really doing which is to ask: What is the asymptotic of the least $$k$$ for which the function $$F(x)$$:

$$F(x)=x+\sum _{j=2}^k -|A(x,j)| \tag{6}$$

is negative? For $$k=1..x$$.

Plot of the numerical evidence where the irregular blue curve is that least $$k$$ for which the function $$F(x)$$ is negative and thereby also the LHS of (5) while the smooth red curve is the conjectured asymptotic $$(8x)^{1/2}$$: Efficient Mathematica program to generate the plot. Setting nn=10000 gives the plot above:

(*start*)
(*Mathematica*)
Clear[a, f, p];
nn = 1000;
p = 0;
f[n_] := n*Log[n]^p;
(*Clear[f];*)
(*f[n_] := n*Log[n]^4/(Pi*8)^2/8;*)
a[n_] := DivisorSum[n, MoebiusMu[#] # &];
Monitor[TableForm[
A = Accumulate[
Table[Table[If[n >= k, a[GCD[n, k]], 0], {k, 1, nn}], {n, 1,
nn}]]];, n]
TableForm[B = -Abs[A]];
Clear[A];
B[[All, 1]] = N[Table[f[n], {n, 1, nn}]];
TableForm[B];
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[Sqrt[8*f[n]], {n, 1, nn}, PlotStyle -> {Red, Thick}],
ImageSize -> Large]]
ListLinePlot[v/Table[Sqrt[8*f[n]], {n, 1, nn}]]
(*end*)


Variant of the Mathematica program above: https://pastebin.com/GJ81MQez

Inefficient Mathematica program to generate the LHS in (5):

Clear[varphi];
nn = 20;
constant = 2*Sqrt;
varphi[n_] := Total[Divisors[n]*MoebiusMu[Divisors[n]]];
Monitor[TableForm[
A = Table[
Table[Sum[If[n >= k, varphi[GCD[i, k]], 0], {i, k, n}], {k, 1,
nn}], {n, 1, nn}]];, n]
Table[1 +
Sum[Sign[(1 + Sign[x + Sum[-Abs[A[[x, j]]], {j, 2, k}]])], {k, 1,
x}], {x, 1, nn}]


which starts: {2, 3, 4, 5, 6, 5, 7, 7, 10, 7, 11, 10, 11, 10, 11, 11, 14, 13, 14, 13}

For my own memory to remember where to start editing tomorrow I write this Mathematica program:

Clear[varphi];
nn = 40;
varphi[n_] := Total[Divisors[n]*MoebiusMu[Divisors[n]]];
Table[1 +
Sum[Sign[(1 +
Sign[x +
Sum[-Abs[
Sum[If[x >= j, varphi[GCD[i, j]], 0], {i, j, x}]], {j, 2,
k}]])], {k, 1, x}], {x, 1, nn}]


There are previous efforts related to this question. Here is one of them.

A construction: $$\sqrt{x} \log ^2(x)=\sqrt{x} \left(x-\left(\sqrt{x}-\log (x)\right) \left(\sqrt{x}+\log (x)\right)\right)$$

• Proof of von Mangoldt function formula: math.stackexchange.com/a/51708/8530, mathoverflow.net/a/162214/25104 – Mats Granvik May 1 at 11:05
• Sqrt(8) in the OEIS: oeis.org/A010466 – Mats Granvik May 1 at 11:08
• Could you say clearly if the "blue curve" represents $\sum_{n \leq x} \Lambda(n) -x$ or something else? – YCor May 28 at 20:11
• The irregular blue curve is not $\sum_{n \leq x} \Lambda(n) -x$. I will try to edit and clarify. It uses negated absolute values of the terms in the same expansion as $\sum_{n \leq x} \Lambda(n)$ though. – Mats Granvik May 28 at 20:33
• You don't have to give a complicated formula with signs, you can just say "Let $F(n)$ be the least $k$ such that .... is negative" – Will Sawin May 28 at 21:02

Let us denote the left hand side of $$(1)$$ by $$\psi(x)$$. It is known that $$|\psi(x)-x|$$ is not bounded by a constant times $$x^{1/2}$$. In fact Littlewood (1914) proved that $$\psi(x)-x=\Omega_{\pm}(x^{1/2}\log\log\log x).$$ This is Theorem 15.11 in Montgomery-Vaughan: Multiplicative number theory I.

Setting:

$$F(x)=x\log(x)+\sum _{j=2}^k -|A(x,j)| \tag{1}$$

appears to give the asymptotic $$\sqrt{8x\log(x)}$$ for the least $$k$$ such that $$F(x)$$ is negative.

In general it appears that the least $$k$$ such that:

$$F(x)=f(x)+\sum _{j=2}^k -|A(x,j)| \tag{2}$$

is negative, has the asymptotic: $$\sqrt{8f(x)}$$.

See the Mathematica program in the question, by setting p=1.