Bound the error in estimating a relative totient function - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T02:28:53Z http://mathoverflow.net/feeds/question/88777 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88777/bound-the-error-in-estimating-a-relative-totient-function Bound the error in estimating a relative totient function Aaron Meyerowitz 2012-02-17T21:44:51Z 2012-02-22T08:06:02Z <p>Let $n=p_1^{e_1}\cdots p_k^{e_k}$ be an integer with $k$ prime factors. We know that the number of integers less than $n$ and coprime to it is<br> $$\Phi(n)=n-\sum_i\frac n{p_i}+\sum_{i \lt j}\frac n{p_ip_j}-\cdots+(-1)^{k}\frac n{n}=nr$$ where $r=\prod(1-\frac 1{p_i})$.</p> <p>For any positive integer $x$, the number of integers less than or equal to $x$ and relatively prime to $n$ is given exactly by the alternating sum $$\Phi(n,x)=x-\sum_i\lfloor{x/{p_i}}\rfloor+\sum_{i \lt j}\lfloor x/{p_ip_j}\rfloor-\cdots+(-1)^{k}\lfloor x/{n}\rfloor$$</p> <blockquote> <p>How large and how small can the error $\Phi(n,x)-xr$ be? Can the absolute value of the error exceed $k$?</p> </blockquote> <p>Certainly the error can be no more (in absolute value) than $2^k$, probably it is easy to show that it could not be more than the middle binomial coefficient $\binom k{\lfloor k/2 \rfloor}$. I can see that it could get (almost) as large as <code>$k$</code> by imitating the following example: </p> <p>The integers $1122659, 2245319, 4490639, 8981279, 17962559, 35925119, 71850239$ are a Cunningham chain as is $2,5,11,23,47$ in that each member is prime and one more than twice the previous one. If $n$ is the product of the $7$ primes from the first chain and $x=1122659\cdot64-1=71850175$ then all seven terms $x/{p_i}$ are just a bit less than an integer so, without the rounding down to an integer, the estimate $rx$ will too small by about $7$ (the other terms are quite small). Of course it is not known for sure that there are arbitrary length chains. Maybe a similar idea could get an error of order $2k$ or $k^2.$</p> <p><strong>later</strong> Thanks for the answers. I give one of my own below explaining that actually the best we could hope for is $2^{k-1}$ and then exhibiting a construction of D. H. Lehmer which attains $(1-2/q)2^{k-1}$ for arbitrary $q$. This is pretty much a result of the other answers, but I thought it was worth showing off the construction (which is not immediately clear from the article).</p> http://mathoverflow.net/questions/88777/bound-the-error-in-estimating-a-relative-totient-function/88801#88801 Answer by Gerhard Paseman for Bound the error in estimating a relative totient function Gerhard Paseman 2012-02-18T02:38:53Z 2012-02-18T02:38:53Z <p>Westzynthius showed that for large k, and n the kth primorial, there were gaps of length greater than p_k g(p_k), where g was some increasing function involving log(p_k) and iterated log of p_k, the kth prime. This implies that there will be horizontal segments of at least that length in the graph Aaron Meyerowitz suggests. I'll do the arithmetic later, but I expect it to lead to an error of something like k log(k) minimum. Using Jacobsthal's function and Iwaniec's estimate, it is likely that the error is bounded by k^2.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2012.02.17</p> http://mathoverflow.net/questions/88777/bound-the-error-in-estimating-a-relative-totient-function/88836#88836 Answer by Alan Haynes for Bound the error in estimating a relative totient function Alan Haynes 2012-02-18T15:57:55Z 2012-02-19T16:11:33Z <p>First of all as you remark above, it is easy to see by elementary means that the error is at most $2^k$. It was an old conjecture of Erdos that this error term could be improved to $o(2^k)$. However this conjecture turns out not to be true!</p> <p>In 1951 Vijayaraghavan proved that the error term $O(2^k)$ is best possible in the sense that for any $k\in\mathbb{N}$ and $\delta >0$ you can find an integer $n$ with exactly $k$ distinct prime factors, and a real number $x$, such that</p> <p>$$\Phi(n,x)-xr>2^{k-1}-\delta.$$</p> <p>Vijayaraghavan's paper is <em>On a problem in elementary number theory. J. Indian Math. Soc. 15, (1951)</em>.</p> <p>For a more detailed and up to date discussion you could look at the more recent paper <em>Codecà, Nair, An extension of a result of Lehmer on numbers coprime to n. Ramanujan J. 16 (2008), no. 1, 59–71.</em></p> http://mathoverflow.net/questions/88777/bound-the-error-in-estimating-a-relative-totient-function/89162#89162 Answer by Aaron Meyerowitz for Bound the error in estimating a relative totient function Aaron Meyerowitz 2012-02-22T07:30:19Z 2012-02-22T08:06:02Z <p>In fact the absolute value could not be greater than $2^{k-1}.$ Let $\{z\}=z-\lfloor z \rfloor$ denote the fractional part of $z$, then $$\Phi(n,x)-xr=0-\sum_i\{x/{p_i}\}+\sum_{i \lt j}\{ x/{p_ip_j}\}-\cdots+(-1)^{k}\{x/{n}\}$$ is a sum of $2^k$ terms, each between $0$ and $1$, half added and half subtracted. There is no reason to expect the first $k$ primes to give the optimal gap, and in fact they do not. For that matter, the question would be as interesting to me if the $p_i$ are simply relatively prime integers. The references given by Alan Haynes are apt and lead one to look at the article <a href="http://dx.doi.org/10.4153/CJM-1955-038-5" rel="nofollow">The distribution of totatives</a> by D. H. Lehmer. Even there the key example is a bit hard to work out. If $q$ is any integer and $p_1\lt\dots\lt p_k$ are $k$ primes all of the form $p_i=c_iq-1$ then for $n=p_1p_2\cdots p_k$ there is a number $1 \lt x \lt n$ for which $|\Phi(n,x)-xr| \gt 2^{k-1} \frac{q-2}{q}.$ Let $C=\prod c_i$ It is esy to see that $$n=Cq^k-(\sum_iC/c_i)q^{k-1}+(\sum_{i\lt j}C/c_ic_j)q^{k-2}-\cdots+(-1)^k.$$ A similar expression holds for any product of several of the $p_i.$ The essentially unique extremal $x$ is $$\frac{n +(-1)^kp_1}{q}-1.$$ At this point I will simply illustrate with $k=4.$ Then </p> <p>$$n=c_{1}c_{2}c_{3}c_{4}{q}^{4}- \left( c_{1}c_{2}c_{3}+c_{1}c_{2}c_{4}+c_{1}c_{3}c_{4}+c_{2}c_{3}c_{4} \right) {q}^{3}$$$$+ \left( c_{1}c_{2}+c_{1}c_{3}+c_{1}c_{4}+c_{2}c_{3}+c_{2}c_{4}+c_{3}c_{4} \right) {q}^{2}- \left( c_{1}+c_{2}+c_{3}+c_{4} \right) q+1$$ </p> <p>and $$x=c_{1}c_{2}c_{3}c_{4}{q}^{3}- \left( c_{1}c_{2}c_{3}+c_{1}c_{2}c_{4}+c_{1}c_{3}c_{4}+c_{2}c_{3}c_{4} \right) {q}^{2}$$$$+ \left( c_{1}c_{2}+c_{1}c_{3}+c_{1}c_{4}+c_{2}c_{3}+c_{2}c_{4}+c_{3}c_{4} \right) {q}- \left( c_{2}+c_{3}+c_{4} \right)-1$$ So $$x/p_1p_2p_3p_4-\lfloor x/p_1p_2p_3p_4\rfloor =x/n \approx 1/q$$ while, each term $$x/p_i-\lfloor x/p_i\rfloor=1-\frac{c_i-c_1+1}{c_iq-1} \approx 1-1/q$$ and each term $$x/(p_ip_j)-\lfloor x/(p_ip_j)\rfloor=\frac{c_ic_jq-(c_i+c_j)+c_1-1}{c_ic_jq^2-(c_i+c_j)q+1}\approx 1/q.$$ The terms of one sign are very about $1/q$ and those of the other are about $1-1/q.$ this accounts for the entire summation being close to $(1-2/q)2^{k-1}$ </p> <p>The other extreme is at $n-1-x$.</p>