Restricted Totient Sums $\sum_{n=1}^{\sqrt {L-1}}\widehat \varphi(B_n,n)$

145 Views Asked by At

Let the Euler totient function be:$$ (1) \qquad \qquad\varphi(n) = \sum_{k=1, \atop gcd(k,n)=1}^{n}1$$

And let the following 2 functions be variations of the original Euler totient function:

$$(2) \qquad \qquad \widehat \varphi(n) = \sum_{k=1, \atop {gcd(k,n)=1 \atop k \space mod \space 2 \space \neq \space n \space mod \space 2}}^{n}1$$

$$(3) \qquad \qquad \varphi(B,n) = \sum_{k=1, \atop gcd(k,n)=1}^{B}1$$

To summarize and clarify:

$(1)$ Is simply the Euler totient function without modifications, i.e, the count of number smaller than $n$ that are coprime to $n$.

$(2)$ Is Euler totient function, modified so that it only counts the numbers smaller than $n$ that are coprime to it, but also do not have the same parity, i.e - if $n$ is odd, then it only counts coprimes that are even, and if $n$ is even, it only counts coprimes that are odd. Obviously, for the case where $n$ is even, it does not matter, but for the case of $n$ odd, it does change the count, because odd $n$ may have coprimes that are odd as well. In this function (2) we do not count them.

$(3)$ In that modification, we count numbers smaller than $n$ which are coprime to it, up to a certain bound $B$. For example, $\varphi(3,7) = 3$. Although all numbers smaller than $7$ are coprime to it, we only count those $\leqslant B = 3$.

Finally, I am interested in a sum which involves both modifications. For a limit $L$, consider the following sum: $$(4) \qquad \qquad S = \sum_{n=1}^{\sqrt {L-1}}\widehat \varphi(\sqrt {L-n^2},n)$$

To express it in a more clear way, further denote $B_n = \sqrt {L-n^2}$, so we can rewrite the sum as follows:

$$(5) \qquad \qquad S = \sum_{n=1}^{\sqrt {L-1}}\widehat \varphi(B_n,n)$$

Calculating totients $(1)$ is well known and I won't go into details about it. I am also aware of efficient ways to evaluate the totient summatory function $\sum_{k=1}^n \varphi (k)$. However, efficiently calculating $(2)$ and $(3)$ is something I do not know how to do. Evaluating them in a naive way, as well as evaluating the sum in a naive way is simple enough. But for large $L$ it is inefficient.

Any insights regarding $(2), (3), (4) , (5)$ will be appreciated. Thank you.

1

There are 1 best solutions below

1
On

We have \begin{align*} S &= \sum_{n=1}^{\sqrt {L-1}}\hat \phi\big(\sqrt {L-n^2},n\big) \\ &= \sum_{n=1}^{\sqrt {L-1}} \sum_{\substack{1\le k\le \sqrt{L-n^2} \\ \gcd(k,n)=1 \\ k\not\equiv n\pmod2}} 1 \\ &= \#\big\{ (n,k)\in \Bbb N^2\colon k^2+n^2 \le L, \, \gcd(k,n)=1 ,\, k\not\equiv n\pmod2 \big\}. \end{align*} Other than the parity restriction, this is simply counting "primitive" lattice points in a quarter-circle of radius $\sqrt L$. The number of lattice points in general in such a quarter-circle is approximately $\frac\pi4 L$, and it is not hard to show that the number of primitive lattice points in that region is approximately $\frac1{\zeta(2)}\frac\pi4 L = \frac{3}{2\pi} L$. Searching for "primitive lattice points" will reveal many references to the method of proof: it begins by noting that $\sum_{d\mid\gcd(k,n)} \mu(d)$ equals $1$ if $\gcd(k,n)=1$ and $0$ otherwise, then exchanging the order of summation.

The parity restriction should reduce this by a further factor of $\frac23$ (primitive lattice points must be (odd,odd), (odd,even), or (even,odd); all occur with roughly the same frequency, and the (odd,odd) ones no longer count), for a final count of approximately $\frac L\pi$.