This question is a follow up to this excellent mathematics stackexchange question.

Let $\mu(n)$ be the Möbius function, $\phi(n)$ Euler's totient function, $\sigma(n)$ the sum of divisors function and $\tau(n)$ the number of divisors function. Define the set $S_N,$ for a natural number $N,$ by

$$S_N = \lbrace (m,n) \in \mathbb{N} \times \mathbb{N} \mid m \ne n, \, \mu(m)=\mu(n), \, \phi(m)=\phi(n),$$ $$\sigma(m)=\sigma(n), \, \tau(m)=\tau(n) \textrm{ and } \text{max} \lbrace m,n \rbrace \le N \rbrace .$$

How large is the set $ S_N $ ?

  • 2
    $\begingroup$ "Order" is a really overloaded word; what's wrong with "size"? $\endgroup$ – Qiaochu Yuan Nov 22 '10 at 22:23
  • $\begingroup$ @Qiaochu Yes, there's the tacit assumption that there are an infinity of pairs satisfying the given relationships, but at the moment I'll hedge my bets in that direction. Although, of course, any information on the size of $S_N$ is very welcome. $\endgroup$ – Derek Jennings Nov 23 '10 at 8:24
  • 1
    $\begingroup$ Have you found any such $m,n$? $\endgroup$ – Gerry Myerson Jul 6 '11 at 12:47
  • $\begingroup$ Are there any squarefree examples (that is, $\mu(m)=\mu(n)\ne0$)? $\endgroup$ – Greg Martin Jan 12 '12 at 22:53

As all of $\mu$, $\tau$, $\phi$, and $\sigma$ are multiplicative, if $(a,b)$ is such a pair and $n$ is relatively prime to $ab$ then $(an,bn)$ is another pair. So, as there is at least one pair there are an infinite number of them, and for $N$ large enough there is a constant C such that there are at least $CN$ such pairs. Also, if $(c,d)$ is another such pair with $(c,d)$ with $cd$ relatively prime to $ab$ then $(ac,bd)$ and $(ad,bc)$ are more pairs.

If we define a primitive pair as a pair that cannot be decomposed as above, then I suspect that there are an infinite number of primitive pairs, but I have no idea how to prove it.

Edit: In the answer to this question the pairs {1836, 1824), {5236, 4960}, {5742, 5112}, {6764, 6368}, {9180, 9120} and {9724, 9184} are found so there is at least one such pair.


To motivate the intuition that there are probably an infinite number of primitive pairs, here is a simple algorithm for computing relative prime pairs:

  1. Choose a set of small primes $B$ (for example the primes less than 20)
  2. Compute a set of primes $P$ such that for $p\in P$ both $\sigma(p)=p+1$ and $\phi(p)=p-1$ factor completely using the primes in $B$
  3. For each prime in $P$ create a variable $X_p$, where $X_p=1$ if $p|m$, $X_p=-1$ if $p|n$ and $X_p=0$ otherwise.
  4. Each member of $B$ creates 2 linear equality constraints on the $X_p$ and we add another constraint $\sum_{p\in P}X_p = 0$ constraining $m$ and $n$ to have the same number of prime factors. Since they are square free and have the same number of prime factors, both $\mu$ and $tau$ will be equal.
  5. Enumerate the $\{-1,0,1\}^k$ lattice points that satisfy the constraints. These will give the prime factors of $m$ and $n$.

In theory step 5 can be problematic, in practice it is easy to find many. For example, letting $B$ be the primes less than 20, letting $P$ be the qualifying primes less than 1000, we quickly get hundreds of pairs, the smaller of which are: (15265, 15169), (27962, 26355), (30199, 30217), (64255, 63791), (66526, 62535) (72713, 72703), (89089, 89585), (149739, 145915), (166315, 165319), (182942, 171795), (233597, 235135), (307021, 307951), (344137, 344129), (392227, 391859), (483769, 485317), (622599, 605815), (873301, 876211), (967759, 968297),

It is left as an exercise to the reader to extend this to non square free pairs.

As the size of $P$ seems to grow much faster than $B$ it is plausible that we will generate more new pairs as we grow $B$.


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.