Take the 2-minute tour ×

Happened to get this from a friend.

How does one show that for all pairs of real numbers $x$ and $y$, there is $n \in \mathbb{N}$ such that $$ x < \frac{\Phi(n+2)}{\Phi(n)} < y$$ where $\Phi$ is the Euler's totient function.

$\textbf{Added.}$ This seems to be somewhat related to the problems given here: $\textbf{J 8}, \textbf{J 9}, \textbf{J 10}$ at this link.

share|improve this question
No one pointed out that this is impossible if $x\ge y$? No one pointed out that this is impossible if $y\le0$? –  Gerry Myerson Aug 11 '11 at 7:16

2 Answers 2

up vote 11 down vote accepted

Okay, here is an answer assuming plausible conjectures about linear equations in primes.

Lemma: For any real numbers $(a,b)$ with $0 < a < b < 1$, there is a positive integer $n$ such that $\phi(n)/n \in (a,b)$. Moreover, for any integer $k$, we can arrange that $n$ is relatively prime to $k$.

Proof: Let $N$ be larger than $k$, and large enough that $b(1-1/N)>a$. Consider the product $\prod_{p >N} (1-1/p)$, where the product runs over primes greater than $N$. This infinite product is $0$, because $\sum 1/p=\infty$. So there is some $M$ such that $\prod_{N < p < M} p$ is less than $b$. Choose the first such $M$ for which this happens. Then $\prod_{N < p < M} p > b (1-1/M) > a$ by the choice of $M$. Take $n=\prod_{N< p < M} p$. QED

Now, to answer your question. Choose intervals $(a_1, b_1)$ and $(a_2, b_2)$ with $0 < a_i < b_i < 1$ such that $x < a_2/b_1 < b_2/a_1 < y$. Using the lemma, find $n_1$ and $n_2$ such that $\phi(n_i)/n_i \in (a_i, b_i)$, the $n_i$ are both odd, and $GCD(n_1, n_2) = 1$.

Now, if you believe the generalized Hardy-Littlewood conjecture then there are infinitely many pairs $(q_1, q_2)$ of prime numbers such that $n_1 q_1 +2 = n_2 q_2$. For $q_1$ large enough, $n:=n_1 q_1$ has the desired property.

Unfortunately, this equation is one of the ones to which Green and Tao's results do not apply. (In their terminology, $\psi_1$ and $\psi_2$ are linearly dependent.) You might be able to dodge this issue by asking for $q_1$ and $q_2$ to be almost prime rather than prime. (Almost prime meaning a product of two large primes.) I'm not enough of an expert to know whether that trick would work in this setting; if you seriously care about the question, you might try e-mailing Terry Tao.

share|improve this answer

Let p_1,...,p_k be the set of all primes less than or equal to N. For any subset S of {1,...,k} we can find a congruence class modulo prod p_i so that p_i divides n if i in S and p_i divides n+1 if i not in S. Thus the contribution to Phi(n+1)/Phi(n) coming from those primes can be made to be whatever we specify (and it in particular can be made to approximate whatever positive real we like to within whatever error). Furthermore, it can be shown that if we average over n in that congruence class, the average log of the contribution to Phi(n+1)/Phi(n) coming from larger primes is O(1/N). Thus, we can find such an n so that the contribution from larger primes is negligible.

share|improve this answer
Here's a MathJax tutorial :) –  barto Jun 16 '14 at 11:42

Your Answer

