1
$\begingroup$

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.

$\endgroup$
7
  • 6
    $\begingroup$ 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. $\endgroup$ Feb 17, 2010 at 3:22
  • 1
    $\begingroup$ 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). $\endgroup$ Feb 17, 2010 at 3:27
  • 10
    $\begingroup$ @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. $\endgroup$ Feb 17, 2010 at 3:27
  • $\begingroup$ 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" $\endgroup$
    – Portland
    Feb 17, 2010 at 3:47
  • $\begingroup$ 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)}$ ? $\endgroup$
    – Portland
    Feb 18, 2010 at 0:24

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

See here

$\endgroup$
0
1
$\begingroup$

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!)

$\endgroup$
4
  • $\begingroup$ I don't understand the manipulation you are performing, but sum 1/phi(4n) does not converge. $\endgroup$ Feb 18, 2010 at 12:21
  • $\begingroup$ @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) $\endgroup$
    – maks
    Feb 18, 2010 at 21:21
  • $\begingroup$ Just wonder how exactly you show that the first sum is bounded. I agree that it is true, but why is it obvious? $\endgroup$
    – fedja
    Feb 20, 2010 at 3:32
  • $\begingroup$ 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. $\endgroup$
    – maks
    Feb 21, 2010 at 1:14

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.