Show that, $(-1)^{\mu(1)}+(-1)^{\mu(2)}+...+(-1)^{\mu(n)}<0$ and proof on conjecture of OEIS A209802

Question

Following is an experimental math claim.

We denote $\mu(a)$ as Möbius function

Let $$F(a)=\sum_{i=1}^{a}(-1)^{\mu(i)}.$$

Can it be shown that for every positive integer $a$, $F(a)<0$?

Table

$$\begin{array}{|c |c |} \hline a & F(a) \\ \hline 1 & -1 \\ \hline 2 & -2 \\ \hline 3 & -3 \\ \hline 4 & -2 \\ \hline 5 & -3 \\ \hline 6 &-4 \\ \hline 7 & -5 \\ \hline 8 &-4 \\ \hline 9 &-3 \\ \hline \vdots &\vdots \\ \hline \end{array}$$

source code PARI/GP

for(a=1,100,printf([a, sum(i=1,a,(-1)^moebius(i))]))
[1, -1][2, -2][3, -3][4, -2][5, -3][6, -4][7, -5][8, -4][9, -3][10, -4][11, -5][12, -4][13, -5][14, -6][15, -7][16, -6][17, -7][18, -6][19, -7][20, -6][21, -7][22, -8][23, -9][24, -8][25, -7][26, -8][27, -7][28, -6][29, -7][30, -8][31, -9][32, -8][33, -9][34, -10][35, -11][36, -10][37, -11][38, -12][39, -13][40, -12][41, -13][42, -14][43, -15][44, -14][45, -13][46, -14][47, -15][48, -14][49, -13][50, -12][51, -13][52, -12][53, -13][54, -12][55, -13][56, -12][57, -13][58, -14][59, -15][60, -14][61, -15][62, -16][63, -15][64, -14][65, -15][66, -16][67, -17][68, -16][69, -17][70, -18][71, -19][72, -18][73, -19][74, -20][75, -19][76, -18][77, -19][78, -20][79, -21][80, -20][81, -19][82, -20][83, -21][84, -20][85, -21][86, -22][87, -23][88, -22][89, -23][90, -22][91, -23][92, -22][93, -23][94, -24][95, -25][96, -24][97, -25][98, -24][99, -23][100, -22]

The claim holds $\le 10^4$ verified.

I searched but not found this sequence on OEIS. This one is closer A209802 (not same).

Your suggestions, comments, the answer are valuable to me. Apologies if the claim is just unsolvable. Thank you.

---

Edit, consequence: Partial sums of exponential Möbius function is always greater than $0$.

Let $n=p_1^{r_1}p_2^{r_2}...p_k^{r_k}$ where $r_i>0,(k\ge i\ge 1)$

$$g(n)=\prod_{1\le i\le k}\mu(r_i)$$

$$G(a)=\sum_{n=1}^ag(n)$$

$g(n)$ know as exponential Möbius function. sequence, link.

Sequence $G(a)$ link*,(A209802) knows as Partial sums of exponential Möbius function. It is conjecture that $G(a)>0$ in the comment section of the link*. And here is the proof.

Note

$$ g(n) = \begin{cases} 0, & \text{then $(-1)^{\mu(n)}=1$} \\ -1, & \text{then $(-1)^{\mu(n)}=1$} \\ 1, & \text{then $(-1)^{\mu(n)}\in\{1,-1\}$} \end{cases}$$

This implies $g(n)+(-1)^{\mu(n)}\ge 0$ and because we know (from following answers) $F(a)< 0$ we can conclude $G(a)\ge |F(a)|>0$.

Answer 1

$$|\mu(n)|=\sum_{d^2 |n}\mu(d)$$

$$\sum_{n\le x}|\mu(n)|=\sum_{d^2\le x} \mu(d)\lfloor x/d^2\rfloor\ge x\sum_{d^2\le x} \frac{\mu(d)}{d^2}-x^{1/2} $$

$$\sum_{n\le x} (-1)^{\mu(n)}= x-2\sum_{n\le x}|\mu(n)| \le x(1-2\sum_{d^2\le x} \frac{\mu(d)}{d^2})+2x^{1/2}$$

Conclude with $$\sum_{d^2\le x} \frac{\mu(d)}{d^2}\ge \zeta(2)-\frac1{x^{1/2}}$$

Answer 2

If $Q(a)$ is the number of square free integers between $1$ and $a$, then $$\lim\limits_{a\to \infty }{\frac {Q(a)}{a}}={\frac {6}{\pi ^{2}}}$$ or for large enough $a$ $$\frac {Q(a)}{a} > \frac {6}{\pi ^{2}} -\varepsilon>\frac{1}{2}\Rightarrow\\ Q(a)>\frac{a}{2} \Rightarrow\\ Q(a) > a-Q(a) \Rightarrow$$ $$-Q(a) + (a-Q(a))<0 \tag{1}$$ And of course $$F(a)=\sum\limits_{x\in\text{Sqare Free}\\x\leq a}(-1)+\sum\limits_{x\notin\text{Sqare Free}\\x\leq a}1=\\ -Q(a)+(a-Q(a))<0$$

Answer 3

A basic upper bound

Since $\mu(n)$ is even if and only if $n$ is not square-free, we have

\begin{aligned} F(a) &=\sum_{\substack{n\le a\\n\text{ not square-free}}}1-\sum_{\substack{n\le a\\n\text{ square-free}}}1 \\ &=a-2\sum_{\substack{n\le a\\n\text{ square-free}}}1 \end{aligned}

Hence, all we need is to estimate the latter quantity, which can be done using the following fact

$$ \sum_{d^2|n}\mu(d)= \begin{cases} 1 & d\text{ square-free} \\ 0 & \text{otherwise} \end{cases} $$

Plugging this in, we have

\begin{aligned} \sum_{\substack{n\le a\\n\text{ square-free}}}1 &=\sum_{n\le a}\sum_{d^2|n}\mu(d)=\sum_{qd^2\le a}\mu(d) \\ &=\sum_{d\le\sqrt a}\mu(d)\sum_{q\le a/d^2}1 \\ &=a\sum_{d\le\sqrt a}{\mu(d)\over d^2}-\sum_{d\le\sqrt a}\mu(d)\{a/d^2\} \\ &\ge{a\over\zeta(2)}-a\sum_{d>\sqrt a}{\mu(d)\over d^2}-\sqrt a \\ &\ge{a\over\zeta(2)}-2\sqrt a-1 \end{aligned}

Plugging this back to $F(a)$, we deduce

$$ F(a)\le a-{2a\over\zeta(2)}+4\sqrt a+2=-Ka+4\sqrt a+2 $$

where $K=12\pi^{-2}-1\approx0.215854$.

Numerical analysis on the upper bound

To see when this quantity becomes negative, we can analyze the RHS. Since $-K<0$, we see that the upper bound we obtained is a concave-down quadratic curve, so it becomes negative as long as $a$ exceeds the larger root. Applying the quadratic formula, we get

$$ a>\left(2+\sqrt{2K+4}\over K\right)^2 $$

Plugging in the numerical value of $K$ gives that $F(a)<0$ holds for $a\ge362$. Since the OP has shown that $F(a)<0$ holds for $a\le10^4$, we conclude that $F(a)<0$ holds for all positive integer $a$.

Appendix: proof of an intermediate result

Since $\mu(n)\ge-1$ holds for all $n$, we can obtain a lower bound for the coefficient of $a$ in the above expansion:

$$ \sum_{d\le\sqrt a}{\mu(d)\over d^2}\ge\sum_{d\ge1}{\mu(d)\over d^2}-\sum_{d>\sqrt a}{1\over d^2} $$

To further estimate the latter sum, we can use the property of monotonic functions to find that

\begin{aligned} \sum_{d>\sqrt a}{1\over d^2} &<{1\over(\lfloor\sqrt a\rfloor+1)^2}+\sum_{d=\lfloor\sqrt a\rfloor+2}\int_{d-1}^d{\mathrm dt\over d^2} \\ &<\frac1a+\int_{\sqrt a}^\infty{\mathrm dt\over t^2}=\frac1a+{1\over\sqrt a} \end{aligned}

Thus, we have

$$ \sum_{d\le\sqrt a}{\mu(d)\over d^2}\ge\sum_{d\ge1}{\mu(d)\over d^2}-\frac1a-{1\over\sqrt a} $$

and using the knowledge of Euler product the infinite sum evaluates to $1/\zeta(2)$ exactly.