7
$\begingroup$

I noticed on the OEIS that there are various sequences (e.g. A050515-A050520) that describe arithmetic progressions whose totients are all equal. For example, we have $$\varphi(\{1,2\}) = 1$$ $$\varphi(\{8,10,12\}) = 4$$ $$\varphi(\{72,78,84,90\}) = 24$$ $$\varphi(353640 + [0,4]\cdot 210) = 80640$$ $$\varphi(583200 + [0,5]\cdot 30) = 155520$$ $$\varphi(1158419010 + [0,6]\cdot 210) = 264781440$$ (The notation above is somewhat sloppy; I'm trying to say that Euler's totient function equals the right-hand side when evaluated on anything in the set.) Is there a simple reason to believe that this pattern should continue? In other words, for any $k$, does there exist an arithmetic progression $P$ of length $k$ such that $\varphi$ is constant on $P$?

A lemma of H. Gupta [Indian J. Pure Appl. Math, 12(1) (1981)] states that a solution to $\varphi(x) = n$ cannot exceed $A(n)$ where $$A(n) = n\prod_{p\backslash n} {p\over p-1}$$ (the product is taken over all primes $p$ dividing $n$), so my first thought was that some kind of density argument could be made. But it actually does not seem like this is the reason for the arithmetic progressions popping up. Indeed, the ratio $${|\varphi^{-1}(n)|\over A(n)}$$ does not seem to have a positive $\limsup$ as $n$ gets large. One observation is that if $\varphi$ is constant on an arithmetic progression $P$, it is also constant on any dilate $m\cdot P$ of $P$, and some of these dilates might be contained in larger progressions on which $\varphi$ is also constant.

$\endgroup$
1
5
$\begingroup$

We have a conditional result.

See Theorem 4 of S. W. Graham, J. J. Holt, C. Pomerance, On the Solutions to $\phi(n) = \phi(n + k)$, Number Theory in Progress, eds. K. Gyory, H. Iwaniec, and J. Urbanowicz, eds., Vol. 2 (de Gruyter, Berlin, 1999), pp. 867-882.

Theorem 4 in above:

Suppose that $j$, $j+k$, $\ldots$, $j+qk$ all have the same prime factors. Define $B=\prod_{i=0}^q (j+ik)$. For $i=0,\ldots q$, let $$ b_i=\frac B{j+ik}, \ g=\mathrm{gcd}(b_0,b_1,\ldots, b_q), $$ $$ a_i=\frac{b_i}g=\frac B{(j+ik)g}. $$ Suppose that for some positive integer $r$, $$ a_0r+1, a_1r+1,\ldots, a_qr+1 $$ are all primes that do not divide $j$. If $n=j(a_0r+1)=\frac{Br}g+j$, then $$ \phi(n)=\phi(n+k)=\ldots=\phi(n+qk).$$

The first requirement $j, j+k, \ldots, j+qk$ all have the same prime factors is satisfied with $j=(q+1)\#$ and $k=j$, where $N\#=\prod_{p\leq N} p$ is the primorial.

The second requirement $a_0r+1, \ldots, a_qr+1$ are all primes, is nontrivial. Currently, this can be achieved conditionally on Prime $k$-tuples Conjecture.

$\endgroup$
1
  • $\begingroup$ This is really cool, I didn't see this paper. Thanks! $\endgroup$ – Marcel K. Goh Dec 31 '20 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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