13
$\begingroup$

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

Problem:

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

$\endgroup$
4
  • 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

34
$\begingroup$

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.

$\endgroup$
5
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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