Recently Professor Peter Cameron posed a number theory problem which is related to graphs of groups. The problem is:


Let $n$ be a positive integer. Show that there exist subsets $A_1, A_2, …,A_n$ of $\{1,2,…n\}$ with the properties

  1. $|A_i| = \varphi(i)$ for $i = 1,2,…,n$;

  2. if $\mathrm{lcm}(i,j) ≤ n$, then $A_i$ and $A_j$ are disjoint, where $\mathrm{lcm}$ denotes the least common multiple.

Professor Cameron gave some motivations for this question in his blog.

I checked it for a lot of numbers and the results seems to be true. Also, it seems that for some class of numbers there are patterns. For example if $n$ is prime and the statement is true, then it seems that it is true for the multiples of it.

My question: Is it sufficient that we prove this problem for prime numbers?

The first version of the paper published. Congratulate to Veronica Phan, a medical student who knows mathematics well. I think she is the first medical student which has common paper with professor Cameron. Paper

  • 1
    $\begingroup$ We should add that (on his blog) Peter also observed that the greedy algorithm (build each set with the first numbers that are not forbidden) works for all tested values of $n$ (up to 1000), which seems to be super strong evidence to me. I tested it for a few more values, and it miraculously works. $\endgroup$ Jul 5, 2022 at 9:43
  • 2
    $\begingroup$ @GordonRoyle, there's a comment that for $n=10920$ it's possible for the greedy algorithm to go wrong. (More specifically, there's more than one greedy algorithm, and the choice of non-prohibited elements to assign to each $A_i$ matters). $\endgroup$ Jul 5, 2022 at 9:58
  • $\begingroup$ Shahrooz, could you be a bit more precise about the patterns? Maybe give examples of assignments which show a relationship between $n=2$, $n=5$, $n=10$? $\endgroup$ Jul 5, 2022 at 10:02
  • $\begingroup$ Peter, OK... But now I do not have access to my computer and I am writing with my phone. $\endgroup$
    – Shahrooz
    Jul 5, 2022 at 10:18

1 Answer 1


Let $F_n$ be a set of all irreducible fraction $\frac{p}{q}$ such that $0<\frac{p}{q}\leq 1,1\leq p,q\leq n$ and for $i\in \{1,...,n\}$, $D_i$ be subset of $F_n$ which contain all irreducible fraction of the form $\frac{k}{i}$. We have $D_i$ are pairwise disjoint and $|D_i|=\varphi(i)$. So we want a function $f:F_n\rightarrow \{1,...,n \}$ then we can take $A_i=f(D_i)$.

We construct $f$ as follow: if $\frac{m-1}{n}<\frac{p}{q}\leq \frac{m}{n}$ then $f(\frac{p}{q})=m$. If $f(\frac{p}{q})=f(\frac{p'}{q'})=m$ then $|\frac{p}{q}-\frac{p'}{q'}|<\frac{m}{n}-\frac{m-1}{n}=\frac{1}{n}$ (#).

-If $f(\frac{k}{i})=f(\frac{l}{i}), i\leq n$ then by (#) we have $|\frac{k-l}{i}|<\frac{1}{n}$, because $i\leq n$ we must have $k-l=0\Rightarrow k=l$. So the restriction of $f$ to $D_i$ is injective for all $i\in \{1,...,n\}$, therefore $|A_i|=|D_i|=\varphi(i)$.

-If $m\in A_i\cap A_j,i\neq j$, then there exist irreducible fractions $\frac{k}{i}\in D_i,\frac{l}{j}\in D_j$ such that $f(\frac{k}{i})=f(\frac{l}{j})=m$, by (#) we have $\frac{P}{Q}=|\frac{k}{i}-\frac{l}{j}|<\frac{1}{n}$ with $\frac{P}{Q}$ is irreducible. Because $i\neq j$ so $\frac{k}{i}\neq \frac{l}{j}\Rightarrow \frac{P}{Q}>0\Rightarrow P\geq 1$.
We have $\frac{P}{Q}=\frac{|k\frac{lcm(i,j)}{i}-l\frac{lcm(i,j)}{j}|}{lcm(i,j)}>0\Rightarrow Q\leq lcm(i,j)$ (because $\frac{P}{Q}$ is irreducible) and $\frac{P}{Q}<\frac{1}{n}\Rightarrow Q>Pn\geq n$ so $lcm(i,j)>n$. So if $lcm(i,j)\leq n$, $A_i,A_j$ must be disjoint.
So $A_1,...,A_n$ are subsets of $\{1,...,n\}$ we want.

  • 3
    $\begingroup$ That is a beautiful construction - how did you find it? $\endgroup$ Jul 10, 2022 at 5:29
  • 2
    $\begingroup$ @GordonRoyle I try to attack it, and i find that this problem relate to this fomula: en.wikipedia.org/wiki/Euler%27s_totient_function#Divisor_sum. I want to find formula similar like that to solve the problem, but seem like it hard to find good formula. But there a nice trick using fraction that have denominator n to proof that formula. So I assume there some mysterius formula that I need to proof, so I need to extend to all fraction that have denominator not greater than n. And it work. $\endgroup$ Jul 10, 2022 at 6:10
  • 2
    $\begingroup$ I wish I could up vote this more than once! $\endgroup$ Jul 10, 2022 at 7:38
  • $\begingroup$ @veronicaPhan very nice solution... you can share it by professor Cameron. He is so eager to see this answer. $\endgroup$
    – Shahrooz
    Jul 10, 2022 at 13:14
  • 1
    $\begingroup$ @Shahrooz he has known it $\endgroup$ Jul 10, 2022 at 14:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .