Counting the number of integers with their least prime factor greater than $x$ between $ax$ and $ax+x$

elementary-number-theoryfractional-partmobius-functionprime numbers

Let:

$x \ge 2, a \ge 1$ be integers.
$x\#$ be the primorial for $x$
$\mu(i)$ be the möbius function.
$\text{lpf}(x)$ be the least prime factor of $x$.
$p_k$ be the $k$th prime which is the highest prime less than or equal to $x$
$r(m,d)$ be the remainder when $m$ is divided by $d$

It follows that the count of $i$ such that $ax < i \le ax+x$ and $\text{lpf}(i) > x$ is:

$$\sum_{i|p_k\#}\left(\left\lfloor\frac{ax+x}{i}\right\rfloor – \left\lfloor\frac{ax}{i}\right\rfloor\right)\mu(i)$$

My question is whether I am correct that this value can be restated as:

$$\prod_{j=1}^k\left(\frac{p_j-1}{p_j}\right)x – \sum_{i|p_k\#}\left(\frac{r(ax+x,i)-r(ax,i)}{i}\right)\mu(i)$$

which implies that:

$$\prod_{j=1}^k\left(\frac{p_j-1}{p_j}\right)x \ge \sum_{i|p_k\#}\left(\frac{r(ax+x,i) – r(ax,i)}{i}\right)\mu(i)$$

Here is my reasoning:

$\sum\limits_{i|p_k\#}\left(\left\lfloor\frac{ax+x}{i}\right\rfloor – \left\lfloor\frac{ax}{i}\right\rfloor\right)\mu(i) = \sum\limits_{i|p_k\#}\left[\left(\frac{ax+x}{i}-\frac{r(ax+x,i)}{i}\right) – \left(\frac{ax}{i}-\frac{r(ax,i)}{i}\right)\right]\mu(i)$

$=\sum\limits_{i|p_k\#}\left(\frac{ax+x}{i}-\frac{ax}{i}\right)\mu(i) – \sum\limits_{i|p_k\#}\left(\frac{r(ax+x,i)}{i}-\frac{r(ax,i)}{i}\right)\mu(i)$

$=\sum\limits_{i|p_k\#}\left(\frac{x}{i}\right)\mu(i) – \sum\limits_{i|p_k\#}\left(\frac{r(ax+x,i)-r(ax,i)}{i}\right)\mu(i)$

$=\prod\limits_{j=1}^k\left(\frac{p_j-1}{p_j}\right)x – \sum\limits_{i|p_k\#}\left(\frac{r(ax+x,i)-r(ax,i)}{i}\right)\mu(i)$

Did I make a mistake?

Best Answer

As far as I can tell, everything is correct. However, I do have a few comments about my work to verify some of your statements.

First, you wrote

It follows that the count of $i$ such that $ax < i \le ax+x$ and $\text{lpf}(i) > x$ is:

$$\sum_{i|p_k\#}\left(\left\lfloor\frac{ax+x}{i}\right\rfloor - \left\lfloor\frac{ax}{i}\right\rfloor\right)\mu(i)$$

However, you don't specify how you can state "It follows ...". I found you asked at A question about the Mobius Function, where Terry Tao answered. He explains how to use the Möbius inversion formula along with the function

$F_n(x) := \sum_{i|n} \lfloor \frac{x}{i} \rfloor \mu(i)$

In particular, he stated

Indeed, the quantity $F_{p_k\#}(x)$ (that is, the number of natural numbers up to x that have no prime factor less than or equal to $p_k$) is more commonly denoted $\pi(x,p_k)$ in the analytic number theory literature.

As such, $F_{p_k\#}(ax + x) - F_{p_k\#}(ax)$, which is what your expression is, gives what you state that it does. Possibly due to number theory not being my area of expertise, I wasn't aware of this & had some trouble determining it. Therefore, I don't think that you should assume it's obvious to readers here, especially as you're using the "elementary-number-theory" tag for your question, so the people reading it would encompass a fairly wide range of knowledge & expertise. In this case, I suggest you should have just included a link to that post. If you had, it would've saved me quite a bit of time & effort in trying to determine & verify your statement.

I also note you implicitly used the Möbius inversion again to get to your last line. In particular, it states in Möbius Function that

$\frac{\phi(n)}{n} = \sum_{d \mid n}\frac{\mu(d)}{d}$

Using $n = p_k\#$, along with the definition at Euler's totient function of

$\varphi(n)=n\prod_{p\mid n}\left(1-{\frac {1}{p}}\right)$

gives that

$\prod\limits_{j=1}^k\left(\frac{p_j-1}{p_j}\right) = \sum\limits_{i|p_k\#}\left(\frac{\mu(i)}{i}\right)$

This, I suspect, is more generally widely known than your earlier statement, but I suggest it still would be a good idea to briefly mention what you're using.

In general, keep in mind that, even if the person reading your text is familiar with the proof of what you're using in a statement, they may have trouble recognizing it if they haven't used or thought about it for a long time. As such, it could take them longer, & cause them more difficultly, to understand what you're stating than if you had given more details. Thus, unless it is something quite basic for your expected audience, I believe it's better to offer at least some minimal explanation.

Related Solutions

Reasoning with fractional parts and the Möbius function.

https://octave-online.net/

    N = 300; mu = zeros(1,N); mu(1) = 1; for n = [1:N], mu(n+n:n:end) = mu(n+n:n:end)-mu(n); end;
    P = primes(N); L = length(P);
    X = zeros(L,N); X(1,:) = [1:N]; 
    for l = [2:L], p = P(l-1); X(l,1:p-1) = X(l-1,1:p-1); X(l,p:N) = X(l-1,p:N)-X(l-1,floor([p:N]/p)); end;
    plot(X(5:5:end,:).');

Reasoning about $\left(\left\lfloor\frac{2x}{i}\right\rfloor -2\left\lfloor\frac{x}{i}\right\rfloor\right)$

I have several comments. First, in what you're trying to show of

$\sum\limits_{i|\dfrac{p_k\#}{2}}\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) = -1$ or $0$

you don't define what $x$ is. As such, for now, I will assume it can represent any integer.

Next, a minor issue is that in your argument (1), you are using the negative of $\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor$ used in what you're trying to show. To me at least, it would be slightly less confusing to use the same expression instead to show the result is always $1$ or $0$.

With your argument (2), you say that the expression

$f_1 \dots \dfrac{f_j-1}{2} \dots f_n = \dfrac{(f_1 \dots f_j \dots f_n) - (f_1 \dots f_n)}{2} < \dfrac{f1 \dots f_j \dots f_n-1}{2}$

is true

if for any factor $f_j$, $r(x,f_j) \le \dfrac{f_j-1}{2}$

However, the expression is true in all cases where there are at least $2$ factors $\gt 1$ since the middle part is just expanding the left side, and the right side inequality is true as long as "$f_1 \dots f_n \gt 1$". Also, I also found the way you're expressing it to be a bit confusing. You are using "$f_1 \dots f_n$" to mean the product of all factors $f_i$ for $i$ from $1$ to $n$ except for $i = j$. I can see this from the context, but it is, as far as I know, not a standard or clear way to indicate this. Instead, I suggest you use product notation, with an indication to not include $i = j$ in the product where appropriate, to write your expression. In this case, it could be written instead as

$$\frac{f_j - 1}{2}\prod_{i=1,\; i\neq j}^n f_i = \frac{\prod_{i=1}^n f_i - \prod_{i=1,\; i\neq j}^n f_i}{2} \lt \frac{\prod_{i=1}^n f_i - 1}{2}$$

Next, you go on to state that:

So, only if for all factors $f_j$ of $i$, $r(x,f_j) > \dfrac{f_j-1}{2}$ will:

$\left(\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i) =\mu(i)$

I don't see how you came to this conclusion. Also, note it doesn't always hold. For example, if $i = 15$ and $x = 25$, then $f_j = 3$ is a factor of $i$, with $r(25, 3) = 1$, but $\frac{3-1}{2} = 1$, so it's not true that $r(x,f_j) > \dfrac{f_j-1}{2}$ in this case. However, $\left\lfloor\dfrac{2x}{i}\right\rfloor - 2\left\lfloor\dfrac{x}{i}\right\rfloor = \left\lfloor\dfrac{50}{15}\right\rfloor - 2\left\lfloor\dfrac{25}{15}\right\rfloor = 3 - 2 \times 1 = 1$.

However, the logic in the rest of the proof seems to be correct based on the second part of your (2) being true.

If I've misunderstood or misrepresented anything, please let me know. Thanks.

Best Answer

Related Solutions

Reasoning with fractional parts and the Möbius function.

Reasoning about $\left(\left\lfloor\frac{2x}{i}\right\rfloor -2\left\lfloor\frac{x}{i}\right\rfloor\right)$

Related Question