MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Using the first 100,000 values of $\varphi(n)$ it seems that the following is true.

Let $\mathcal A$ be a finite subset of $\mathbb{N}$, $\forall n\in \mathbb{N} \setminus \mathcal{A}$, $\displaystyle \frac{1}{\varphi(2n)} - \frac{1}{\varphi(2n+1)} \geqslant \frac{1}{2n\ln (2n)} $.

Is this true? Is there a stronger lower bound?

P.S.: I looked at Handbook of Number Theory I by Mitrinović and Sándor which has a lot of info about $\varphi (n)$ but it doesn't appear there.

share|cite|improve this question
Intuitively, this seems very false, considering for example those n for which 2n+1 is the product of the first k odd primes, for large k. – Peter McNamara Feb 17 '10 at 3:22
What is the role of $\mathcal{A}$ here? Do you mean that you believe that his inequality holds for all but finitely many natural numbers? (The way it is phrased, the conjecture would be asserting the inequality holds for every $n\notin \mathcal{A}$, for every finite subset $\mathcal{A}$ of $\mathbb{N}$, which would be equivalent to claiming the result always holds). – Arturo Magidin Feb 17 '10 at 3:27
@Peter: Your idea can be turned into a proof that the difference is negative infinitely often. Namely, in the arithmetic progression of integers n such that 2n+1 is divisible by the first k odd primes for a fixed large k, use Dirichlet's theorem to make n prime. – Bjorn Poonen Feb 17 '10 at 3:27
Arturo, You are right I didn't write it clearly, I basically meant to say "for all positive integers except a finite number of them" – Portland Feb 17 '10 at 3:47
Thanks to everyone. One of the reasons I was interested to prove the initial statement was to show that $\displaystyle \sum_{n\geqslant 1} \frac{(-1)^n}{\varphi (n)}$ diverges (which I suspect, but don't know for sure). It is trivial to show that $\displaystyle \sum_{n\geqslant 1} \frac{1}{\varphi (n)}$. Any other idea to to study $\displaystyle \sum_{n\geqslant 1} \frac{(-1)^n}{\varphi (n)}$ ? – Portland Feb 18 '10 at 0:24

As already mentioned in the comments, one cannot expect inequalities of the form $$\varphi(an+b)>\varphi(cn+d)$$ (provided $ad\neq bc$) to hold for all n. In fact, as is proved here for any polynomials $\{a_ix+b_i\}_{1\le i\le m}$ none of which are a multiple of the other the following holds for infinitely many $n\in \mathbb{N}$ $$ \varphi (a _1 n+b _1) > \varphi (a _2 n+b _2) > \cdots >\varphi (a _m n+b _m) $$ And besides that there are solutions to $\varphi(2n)=\varphi(2n+1)$ (but it is unknown if there is infinitely many of them. Here is the relevant sequence) so I don't think there is a simple lower bound to $$\left|\frac{1}{\varphi(2n)}-\frac{1}{\varphi(2n+1)}\right|$$ If you want an estimate or an average then it is a different matter.

share|cite|improve this answer

Gjergji is right about the reference to my paper - but I wanted to point out that the specific fact that is needed, namely that inequalities of the form $\phi(an+b) > \phi(cn+d)$ hold infinitely often (provided $ad\ne bc$), was proved earlier:

D. J. Newman, Euler’s $\phi$ function on arithmetic progressions, Amer. Math. Monthly 104 (1997), no. 3, 256–257.

The proof essentially follows Peter and Bjorn's outline, if I remember correctly.

share|cite|improve this answer

See here

share|cite|improve this answer
Nice, thanks fedja. – Portland Feb 18 '10 at 3:03

As a matter of fact your sum diverges, a little manipulation shows that $$\sum_{n \leq X} \frac{(-1)^n}{\phi(n)} = \sum_{n \leq X, 2|n} \frac{1}{\phi(n)} - \sum_{n \leq X, (n,2)=1} \frac{1}{\phi(n)} = \sum_{n \leq X/2} \frac{1}{\phi(2n)} -\sum_{n \leq X,(n,2)=1}\frac{1}{\phi(n)}$$ The above equala to $$\sum_{n \leq X/2, (n,2)=1} \frac{1}{\phi(2n)} + \sum_{n \leq X/2, 2|n} \frac{1}{\phi(2n)} - \sum_{n \leq X, (n,2)=1} \frac{1}{\phi(n)}$$ By multiplicativity of $\phi(n)$ we have $\phi(2n) = \phi(n)$ when $(n,2)=1$. Thus the first sum above is a sum over $1/\phi(n)$ and the above equation simplifies to $$ - \sum_{X/2 < n \leq X, (n,2)=1} \frac{1}{\phi(n)} + \sum_{n \leq X/4} \frac{1}{\phi(4n)}$$ It follows that $$\sum_{n \leq X} \frac{(-1)^n}{\phi(n)}= -\sum_{X/2 < n \leq X, (n,2)=1} \frac{1}{\phi(n)} + \sum_{n \leq X/4} \frac{1}{\phi(4n)} \sim c \cdot \log{X}$$ because the first sum on the right converges to a constant, while the second sum on the right is asymptotically $c \cdot \log{X}$.

EDIT: Put details, erased mention of an earlier confusion about $(-1)^{n+1}$ not being a multiplicative function :P (it is!)

share|cite|improve this answer
I don't understand the manipulation you are performing, but sum 1/phi(4n) does not converge. – David Speyer Feb 18 '10 at 12:21
@David: I did put details. Of course sum{1/phi(4n)} diverges, why do you mention that? (i.e just to avoid any confusion: I'm claiming that \sum{(-1)^n/phi(n)} diverges) – maks Feb 18 '10 at 21:21
Just wonder how exactly you show that the first sum is bounded. I agree that it is true, but why is it obvious? – fedja Feb 20 '10 at 3:32
It's not obvious! I just didn't want to make my post too long. At first I just computed an asymptotic for \sum{n <= X} 1/phi(n) within o(1) precision. However note that for our purpose it's enough to show that the sum over X/2 <= n <= X is O(loglog x) which is a consequence of n/(loglog n) <= phi(n) <= n. – maks Feb 21 '10 at 1:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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