Let $H(q)$ be the set of reduced residues $mod(q)$ and $\Phi(a)$ Euler totient function. How can I evaluate
$\min_{q\leq x}\frac{1}{q}\sum_{a\epsilon\ H(q)}\frac{\Phi (a)}{a}$

$\begingroup$ I'm not sure whether you're looking for a closed form, asymptotic, or efficient algorithm but for $1\le x\le 1000$ the only values where $\min_{q\leq x}\frac{1}{q}\sum_{a\epsilon\ H(q)}\frac{\Phi (a)}{a}$ seems to change are $x\in\{1,2,4,6,12,30,210,420,630,840\}$. $\endgroup$– Steven ClarkOct 20, 2021 at 17:26

$\begingroup$ Expecially, I am looking for lower bound in term of x of the minimum above. I guess that most changes of minimum are at q=primorial? $\endgroup$– Andrej LeškoOct 21, 2021 at 7:48

$\begingroup$ I ment upper bound. $\endgroup$– Andrej LeškoOct 21, 2021 at 14:35
1 Answer
Let us find a good approximation for your sum for a given large $q$. I will use the notation $\varphi(a)$ for the Euler function. First of all, by Möbius inversion, $$ \sum_{a\in H(q)}\frac{\varphi(a)}{a}=\sum_{a\leq q}\left(\sum_{d\mid (a,q)}\mu(d)\right)\frac{\varphi(a)}{a}=\sum_{d\mid q}\mu(d)S_d(q), $$ where $$ S_d(q)=\sum_{bd\leq q}\frac{\varphi(bd)}{bd}. $$ To evaluate this sum, notice that $$ \frac{\varphi(m)}{m}=\sum_{d\mid m}\frac{\mu(d)}{d}, $$ hence $$ S_d(q)=\sum_{bd\leq q}\sum_{d_1\mid bd}\frac{\mu(d_1)}{d_1}=\sum_{d_1\leq q}\frac{\mu(d_1)}{d_1}\#\{bd\leq q: d_1\mid bd\}. $$ Now, $d_1\mid bd$ iff $\frac{d_1}{(d,d_1)}\mid b$, so the weight inside our sum is $$ \left[\frac{q/d}{d_1/(d,d_1)}\right]=\frac{q(d,d_1)}{dd_1}+O(1). $$ Therefore, $$ S_d(q)=\frac{q}{d}\sum_{d_1\leq q}\frac{\mu(d_1)(d,d_1)}{d_1^2}+O(\ln q) $$ (the constant in O is absolute) The sum in the main term is $$ \sum_{d_1\leq q}\frac{\mu(d_1)(d,d_1)}{d_1^2}=\sum_{d_1}\frac{\mu(d_1)(d,d_1)}{d_1^2}+O\left(\sum_{d_1>q}\frac{d}{d_1^2}\right)=\prod_{p}\left(1\frac{(p,d)}{p}\right)+O(dq^{1}), $$ because $(d,d_1)$ is multiplicative as a function of $d_1$. Thus, $$ S_d(q)=\frac{q}{d}\prod_{p}\left(1\frac{(p,d)}{p}\right)+O(\ln q)=\frac{q}{d}\prod_{p\mid d}\left(\frac{p}{p+1}\right)\prod_p\left(1\frac{1}{p^2}\right)+O(\ln q)= $$ $$ =\frac{6q}{\pi^2 d}\prod_{p\mid d}\frac{p}{p+1}+O(\ln q). $$ Plugging this into the initial formula, we obtain $$ \sum_{a\in H(q)}\frac{\varphi(a)}{a}=\frac{6q}{\pi^2}\sum_{d\mid q}\frac{\mu(d)}{d}\prod_p \frac{p}{p+1}+O(\sigma_0(q)\ln q). $$ Using multiplicativity once more, we get $$ \sum_{a\in H(q)}\frac{\varphi(a)}{a}=\frac{6q}{\pi^2}\prod_{p\mid q}\left(1\frac{1}{p+1}\right)+O(\sigma_0(q)\ln q). $$ So, up to an error of order $q^{1+o(1)}$ the quantity you want to minimise is $$ \frac{6}{\pi^2}\prod_{p\mid q}\left(1\frac{1}{p+1}\right), $$ therefore your guess about primorials above is essentially correct and the minimum is asymptotic to $$ \frac{6}{\pi^2}\prod_{p\leq \ln x}\left(1\frac{1}{p+1}\right)=\frac{6}{\pi^2}\prod_{p\leq \ln x}\left(1\frac{1}{p}\right)\left(1\frac{1}{p^2}\right)^{1}\sim \frac{e^{\gamma}}{\ln\ln x}. $$

$\begingroup$ Thank you , but can i deduce from your proof that $\min_{q\leq x}\frac{1}{q}\sum_{a\epsilon\ H(q)}\frac{\Phi (a)}{a} <\frac{e^{\gamma}}{\ln\ln x}$ for every relatively big $x$? $\endgroup$ Oct 21, 2021 at 14:30

$\begingroup$ @Andrej Leško, probably not. This inequality is rather close to $e^\gamma \varphi(P)\ln\ln P<P$ for all primorials $P$, which is equivalent to the Riemann hypothesis, see here: math.stackexchange.com/a/302592 $\endgroup$ Oct 21, 2021 at 17:53

$\begingroup$ We can find trivial lower bound from the fact that for $a\epsilon{}H(q)$, $a+n\cdot q$ can be prime only when $(a,n)=1$, so $ \pi(x;q,a)<\frac{x}{a\cdot q}\cdot \Phi (a) $ and after summation over $a$ , $\pi(x)<\frac{x}{q}\sum_{a\epsilon\ H(q)}\frac{\Phi (a)}{a}$ for every $q<\sqrt(x) $ $\endgroup$ Oct 22, 2021 at 8:31