Number of integers coprime to l - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T23:46:46Z http://mathoverflow.net/feeds/question/98343 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98343/number-of-integers-coprime-to-l Number of integers coprime to l kolik 2012-05-30T08:54:30Z 2012-05-31T17:20:41Z <p>A long time ago I've seen a paper considering, given $\ell$ fixed, estimates for</p> <p>$$\sum_{n \leq x, (n, \ell) = 1} 1$$</p> <p>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</p> <p>$$\sum_{n \leq x} (n, \ell)$$ are essentially an equivalent variation of the problem, so references on this problem are welcome aswell.</p> <p>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. </p> http://mathoverflow.net/questions/98343/number-of-integers-coprime-to-l/98357#98357 Answer by Seva for Number of integers coprime to l Seva 2012-05-30T10:31:05Z 2012-05-31T17:20:41Z <p>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 <code>$$R = \sum_{d\mid l} \mu(d) \{x/d\}.$$</code> 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 <code>$\{x/d\}$</code> and estimate the resulting sums.</p> <hr> <p>As to the paper you mention, I think I was able to spot it out: is it "Extremal values of <code>$\Delta(x,N)=\sum_{n&lt;xN,(n,N)=1} 1-x\phi(N)$</code>" by P. Codeca and M. Nair, published in <em>Canad. Math. Bull.</em> <strong>41</strong> (3) (1998), pp. 335–347? Another paper by the same authors on the same subject: "Links between <code>$\Delta(x,N)=\sum_{n&lt;xN,(n,N)=1} 1-x\phi(N)$</code> and character sums", <em>Boll. Unione Mat. Ital. Sez. B Artic. Ric. Mat.</em> <strong>6</strong> (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, <em>Canad. J. Math.</em> <strong>7</strong> (1955), pp. 347–357.</p> http://mathoverflow.net/questions/98343/number-of-integers-coprime-to-l/98368#98368 Answer by js for Number of integers coprime to l js 2012-05-30T12:14:25Z 2012-05-30T14:26:09Z <p>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).</p> <p>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 <a href="http://www.numdam.org/numdam-bin/fitem?id=JTNB_1998__10_1_203_0" rel="nofollow">this paper</a> of Y.-F.S. Pétermann.</p> <p>Note also that sieve methods give nontrivial bounds on the quantity $\sum_{n \leq x, (n, \ell) = 1} 1$ (without Fourier analysis).</p>