Solutions to $\varphi(\varphi(a))=\varphi(\varphi(b))$

Not an answer, just a visualization:

import math
import matplotlib.pyplot as plt

def phi(x):
    result = []
    for n in x:
        amount = 0
        for k in range(1, n + 1):
            if math.gcd(n, k) == 1:
                amount += 1
        result.append(amount)
    return result

x = list(range(2000))

fig,axes = plt.subplots()
plt.scatter(x,phi(phi(x)),s=1)
fig.suptitle('phi(phi(x))')
plt.show()

compare to phi(x):

The question on the title

$\varphi(\varphi(a))=\varphi(\varphi(b))$ with $\varphi(a)\neq \varphi(b)$. There are infinitely many solutions.

Let $a=2^{k-1}3^2$ and $b=2^{k+1}$ for $k\geq 2$.

Then we have $\varphi(a)= 2^{k-2}\cdot (3^2-3) = 2^{k-1}\cdot 3$, and $\varphi(b)=2^k$.

This yields $\varphi(a)\neq \varphi(b)$. But, we have $\varphi(\varphi(a)) = 2^{k-2}\cdot 2=2^{k-1}$ and $\varphi(\varphi(b))=2^{k-1}$.

Consider the equation (1): $\phi(p-1)=\phi(q-1)$, $p\neq q$ are primes.

Conditional Proof of Infinitude of Solutions to (1)

If there are infinitely many $k$ satisfying $p=4k+1$, $q=6k+1$ are primes, and $(6,k)=1$, we have infinitely many nontrivial pairs of primes $p$ and $q$ such that $\varphi(p-1)=\varphi(q-1)$.

Requiring both $4k+1$ and $6k+1$ be primes is similar to Sophie Germain primes problem. In which, we require both $p$ and $2p+1$ be primes.

Unconditional Proof of Infinitude of Solutions to (1)

We apply the multidimensional Selberg sieve developed in James Maynard's paper.

We say $\mathcal{H}=\{h_1,\ldots, h_k\}$ is an admissible set if there is $x_p\in\mathbb{Z}$ such that $x_p\not\equiv h_i$ mod $p$ for all $1\leq i\leq k$.

The main result in Maynard's paper is that for any admissible set with $105$ elements, there are infinitely many positive integer $n$ such that at least two of $n+h_i$'s are prime. An example of such admissible set contains $105$ integers from $0$ to $600$. Thereby, proving that there are infinitely many prime gaps of size at most $600$.

A remark in Andrew Granville's paper states that Maynard's result can be applied to any admissible $k$-tuple of linear forms. A $k$-tuple of linear forms $\{g_i x + h_i| i=1,\ldots k\}$ is said to be admissible if for any prime $p$ there is $x_p\in\mathbb{Z}$ such that $p\nmid \prod_{i=1}^k (g_i x_p + h_i)$. So, if we obtain an admissible $105$-tuple $\{g_i x + h_i| i=1,\ldots, 105\}$ of linear forms, then there exists infinitely many positive integers $n$ such that at least two of $g_i n + h_i$ are prime.

First, we obtain $1271$ integers whose $\phi$ function value is $1000000000000000$. This could be found from here. By writing a python code, it is possible to obtain $300$ integers among them such that none of them is $1$ mod $p$ for any $p\leq 107$. Then take $105$ integers $b_1,\ldots, b_{105}$ from these $300$ integers.

Then for each prime $p$, there exists $x_p\in\mathbb{Z}$ such that $x_p\not\equiv 0$ mod $p$, and $p\nmid \prod_{i\leq 105}(b_i x_p +1 )$. Let $Q=\mathrm{LCM}(\prod_{p|b_1\cdots b_{105}}p, \prod_{p<107}p)$. By Chinese remainder theorem, there is a single congruence $v_0$ mod $Q$ such that $v_0\equiv x_p$ mod $p$ for each $p|Q$. Then $(v_0,Q)=1$ and $(b_i,Qy+v_0)=1$ for any $y\in\mathbb{Z}$ and $i\leq 105$. The $k$-tuple of linear forms $\{b_iQy+b_iv_0+1|i\leq 105\}$ becomes admissible. Thus, there are infinitely many positive integers $n$ such that at least two of $b_i(Qn+v_0)+1$ are primes. Let $p=b_i(Qn+v_0)+1$ and $q=b_j(Qn+v_0)+1$ are distinct primes. Then $\phi(p-1)=\phi(b_i)\phi(Qn+v_0)= \phi(b_j) \phi(Qn+v_0) = \phi(q-1)$. Hence there are infinitely many solutions to (1).

Remark

It is possible to remove the 'computer-assisted' part of proof by invoking Kevin Ford's paper. It is also possible to extend the result to the equation $$\phi(p_1-1)=\phi(p_2-1)=\cdots = \phi(p_k-1), \ \ p_i \ \textrm{'s are distinct primes}$$ that there are infinitely many solutions to the above.