1
$\begingroup$

When thinking about an unrelated problem, I wanted to sum

$$\sum_{k\in[\sqrt n,2\sqrt n]}\#\{j\leq k/5:\gcd(k,j)=1\}$$and I wanted this sum to be$\Theta(n)$. From the wikipediaI can see that if we take away the restriction of$\leq n/5$ we do have our result. A natural definition to consider given this is the following

$$\varphi(n,\varepsilon):=\#\{k\leq\varepsilon n:\gcd(k,n)=1\}$$

My question is the following

Question. Can we prove that for every fixed$\varepsilon\in(0,1)$ we have$\varphi(n,\varepsilon)=\Theta(\varphi(n))$?

I've been trying to do an averaging argument to prove that it holds true for almost every$n$ (which at least would've been enough for my original application), but I'm not too well-versed in number theory so I haven't been succesful

askedNov 20 at 18:05
Bruno Andrades's user avatar
$\endgroup$
2
  • $\begingroup$I don't know (yet?) about $\varphi(n,\varepsilon)$, but I can prove that your sum is $\Theta(n)$ for arbitrary values of $\frac{1}{5}$. Would you consider that an answer?$\endgroup$CommentedNov 20 at 20:26
  • $\begingroup$@DermotCraddock sure!$\endgroup$CommentedNov 20 at 20:37

1 Answer1

5
$\begingroup$

The answer is yes. Almost surely there's an answer already on this site, but since I couldn't find it after searching, I'll provide a complete proof—the general method is important to remember.

The key idea is to apply the fundamental identity$$\sum_{d\mid m} \mu(d) = \begin{cases} 1, &\text{if } m=1, \\ 0, &\text{if } m>1\end{cases}$$with$m=\gcd(j,n)$. For any real numbers$x<y$, we obtain\begin{align*}\#\{ x < j \le y\colon \gcd(j,n)=1\} &= \sum_{x<j\le y} \sum_{d\mid\gcd(j,n)} \mu(d) \\&= \sum_{d\mid n} \mu(d) \sum_{\substack{x<j\le y \\ d\mid j}} 1 \\&= \sum_{d\mid n} \mu(d) \biggl( \Bigl\lfloor \frac yd\Bigr\rfloor - \Bigl\lfloor \frac xd\Bigr\rfloor \biggr) \\&= \sum_{d\mid n} \mu(d) \biggl( \frac{y-x}d + O(1) \biggr) \\&= (y-x) \sum_{d\mid n} \frac{\mu(d)}d + O\biggl( \sum_{d\mid n} |\mu(d)| \biggr) \\&= (y-x)\frac{\phi(n)}n + O(2^{\omega(n)}),\end{align*}where$\omega(n)$ is the number of distinct prime factors of$n$.

In particular,$\phi(n) \gg_\delta n^{1-\delta}$ and$2^{\omega(n)} \ll_\delta n^\delta$ for every$\delta>0$, so the above provides an asymptotic formula as soon as the interval$(x,y]$ has length greater than$n^\delta$. In particular, taking$(x,y] = (0,\varepsilon n]$ handles the question in the OP.

answeredNov 20 at 20:44
Greg Martin's user avatar
$\endgroup$
3
  • 1
    $\begingroup$There's a typo in the last equality, it should be $\phi(n)/n$, right?$\endgroup$CommentedNov 20 at 20:48
  • $\begingroup$Right, @BrunoAndrades, $\sum_{d \mid n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$.$\endgroup$CommentedNov 20 at 21:13
  • $\begingroup$Thanks for the answer! That's a nice trick to know$\endgroup$CommentedNov 20 at 22:15

You mustlog in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.