6
$\begingroup$

A long time ago I've seen a paper considering, given $\ell$ fixed, estimates for

$$ \sum_{n \leq x, (n, \ell) = 1} 1 $$

Of course, this is easy to estimate with a trivial error term of $O(\varphi(l))$. However in the paper I am looking for the authors attempted obtaining better bounds, using some Fourier analysis (in particular the Fourier series for the fractional part of x). I think, bounds in the sum

$$ \sum_{n \leq x} (n, \ell) $$ are essentially an equivalent variation of the problem, so references on this problem are welcome aswell.

The reason why I am interested in this problem is ... pure curiosity. I am curious to see how the Fourier methods meshed in, and what kind of bounds they gave, even though of course we cannot really expect anything too fantastic in this problem.

$\endgroup$
1
  • $\begingroup$ I vaguely remember that the journal in question is likely to be the Canadian Math. Bulletin, or the Canadian Math. Journal, but I could be completely wrong on this hunch (so far my attempts at googling with "canadian" have failed). $\endgroup$
    – kolik
    May 30, 2012 at 8:56

2 Answers 2

7
$\begingroup$

It is easy to explain "how the Fourier analysis meshed in". Namely, using the standard notation for the Möbius function, the Euler's totient function, and the integer / fractional part functions, your sum can be written as $$ \sum_{n\le x} \sum_{d\mid(n,l)} \mu(d) = \sum_{d\mid l} \mu(d) \lfloor x/d \rfloor = x \sum_{d\mid l} \frac{\mu(d)}d + R = \frac{\phi(l)}lx + R, $$ where $$ R = \sum_{d\mid l} \mu(d) \{x/d\}. $$ As Fedor Petrov observed, this already suffices to improve the remainder term from $\phi(l)$ to $\tau(l)$ and indeed, to the number of square-free divisors of $l$, which is $2^{\omega(l)}$. To get better estimates, one can try to plug in the Fourier expansion for $\{x/d\}$ and estimate the resulting sums.


As to the paper you mention, I think I was able to spot it out: is it "Extremal values of $\Delta(x,N)=\sum_{n<xN,(n,N)=1} 1-x\phi(N)$" by P. Codeca and M. Nair, published in Canad. Math. Bull. 41 (3) (1998), pp. 335–347? Another paper by the same authors on the same subject: "Links between $\Delta(x,N)=\sum_{n<xN,(n,N)=1} 1-x\phi(N)$ and character sums", Boll. Unione Mat. Ital. Sez. B Artic. Ric. Mat. 6 (2) (2003), pp. 509–516. I could find one more paper on this problem published in a Canadian journal: "The distribution of totatives" by D.H. Lehmer, Canad. J. Math. 7 (1955), pp. 347–357.

$\endgroup$
4
  • 2
    $\begingroup$ It already gives much better bound then $O(\varphi(l))$, namely, $O(\tau(l))$. $\endgroup$ May 30, 2012 at 10:39
  • 1
    $\begingroup$ Well, I know how it meshed in. I want to see the real work :-) $\endgroup$
    – kolik
    May 30, 2012 at 11:19
  • $\begingroup$ Thank you ! It is amazing that you've found the reference :-) $\endgroup$
    – kolik
    Jun 2, 2012 at 3:21
  • $\begingroup$ I was looking for the paper by Codeca and Nair in the Math. Bulletin $\endgroup$
    – kolik
    Jun 2, 2012 at 3:22
0
$\begingroup$

As written above by Seva, one is led with exponential sums of the form $$ \sum_{d|\ell} \mu(d) e^{\frac{2 i \pi y}{d}} $$ where $y = hx$ is an integer multiple of $x$. If one wants to reduce the trivial error term $O( \tau(\ell))$ to $O(\varepsilon \tau(\ell))$, one must consider the range $h \ll \frac {1}{\varepsilon}$ (at least). But I doubt that something really useful can be said about this particular sum, due to presence of the arithmetic factor $1_{d| \ell}$ (let alone the Möbius function).

If the condition $d|\ell$ is dropped (the sum is over a whole interval), then the best known results (to my knowledge) on this kind of sums are contained in this paper of Y.-F.S. Pétermann.

Note also that sieve methods give nontrivial bounds on the quantity $\sum_{n \leq x, (n, \ell) = 1} 1$ (without Fourier analysis).

$\endgroup$
1
  • $\begingroup$ Is there any sieve method that gives good estimates when $x=o(2^{\omega(l)})$? $\endgroup$
    – Chao Xu
    Oct 23, 2016 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.