Bound the error in estimating a relative totient function - MathOverflow

Bound the error in estimating a relative totient function

2012-02-17T21:44:51Z

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
$$\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})$.

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$$

How large and how small can the error $\Phi(n,x)-xr$ be? Can the absolute value of the error exceed $k$?

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 $ k $ by imitating the following example:

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.$

later 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).

Answer by Gerhard Paseman for Bound the error in estimating a relative totient function

2012-02-18T02:38:53Z

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.

Gerhard "Ask Me About System Design" Paseman, 2012.02.17

Answer by Alan Haynes for Bound the error in estimating a relative totient function

2012-02-18T15:57:55Z

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!

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

$$\Phi(n,x)-xr>2^{k-1}-\delta.$$

Vijayaraghavan's paper is On a problem in elementary number theory. J. Indian Math. Soc. 15, (1951).

For a more detailed and up to date discussion you could look at the more recent paper Codecà, Nair, An extension of a result of Lehmer on numbers coprime to n. Ramanujan J. 16 (2008), no. 1, 59–71.

Answer by Aaron Meyerowitz for Bound the error in estimating a relative totient function

2012-02-22T07:30:19Z

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 The distribution of totatives 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

$$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$$

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}$

The other extreme is at $n-1-x$.