Here is a problem that I would really like to see solved. I have spent quite a bit of time on it myself, and have suggested it to a few other people, but it still resists all attacks, though it looks relatively simple.
As background, recall Euler’s totient function φ, defined for positive integers n by the rule that φ(n) is the number of integers in the interval from 0 to n−1 which are coprime to n. The one fact I need is that, if you sum φ(d) over the divisors d of n, the result is n. This is because φ(d) is the number of integers x in the interval from 0 to n−1 for which the greatest common divisor of x and n is n/d; and for every integer in this interval, gcd(n,x) is some divisor of n.
Now here is the problem.
Problem: Let n be a positive integer. Show that there exist subsets A1, A2, … An of {1,2,…n} with the properties
- |Ai| = φ(i) for i = 1,2,…,n;
- if lcm(i,j) ≤ n, then Ai and Aj are pairwise disjoint, where lcm denotes the least common multiple.
The conditions of the problem require, in particular, that the sets Ai for which i divides n should be pairwise disjoint; but by our earlier remark, there are just enough points to permit this.
I have tried several different attacks, which I won’t detail here; I don’t want to lead you into a blind alley. But I will make one remark.
One obvious construction to try is the greedy algorithm. Choose the sets A1, A2, …, in turn. When choosing Ai, we must avoid points lying in any Aj with j ≤ i and lcm(i,j) ≤ n; continue through the natural numbers until φ(i) points have been chosen. We win if no number greater than n needs to be chosen. This is very simple to implement computationally. It has been checked up to n = 1000 and succeeds in all cases.
I certainly feel that if the greedy algorithm succeeds in solving a problem, that problem should be easy!
Peter Cameron's Blog 
I meant to add two more things.
First, I have a ready-made application of a positive answer to this problem.
Second, both for its own sake and for the application, it would be nice to have not just an existence proof but an efficient construction.
From this it would follow that if a set of integers was such that each pair had a lowest common multiple less than n, then the sum of their totients must be at most n. Is that known?
Not to me!
I have been thinking about this particular corollary and here is a potential line of inquiry for it:
1) If there is a set S of integers with totients summing to more than n and pairwise LCM’s being at most n then both properties are also held by S* which is the set of all elements of S and all factors of S. Thus we might as well assume that S is a down-set in the partially ordered set of divisibility.
2) Let us suppose that S is such a down-set and that a_1, a_2, …, a_n are the maximal elements of S in the partially ordered set of divisibility. Then S = {k : exists i such that k | a_i}.
Then the sum of the totients of S (by the inclusion-exclusion principle) is equal to:
1) the sum over all i of the sum of the totients of the factors of a_i
2) minus the sum over all i, j of the sum of the totients of the common factors of a_i, a_j
3) plus the sum over all i, j, k of the sum of the totients of the common factors of a_i, a_j, a_k
4) and so on…
Since the sum of the totients of the common factors of a_i, a_j, a_k is equal to gcd(a_i, a_j, a_k) (and so on…), it follows that the sum of the totients of S is:
a_1 + a_2 + … + a_n – gcd(a_1, a_2) – gcd(a_1, a_3) – … + gcd(a_1, a_2, a_3) + … …
i.e. it is the sum over all non-empty subsets S of [n] of (-1)^{1 + |S|} gcd(a_i:i in S).
So we need to show that for all a_1, a_2, …, a_n, this is greater than or equal to min(lcm(a_i, a_j):1 <= i <= j <= n}.
For n=1 this states a_1 <= lcm(a_1, a_1), which is trivially true.
For n=2 it states a_1 + a_2 – gcd(a_1, a_2) <= lcm(a_1, a_2), which is equivalent to
a_1+a_2 <= gcd(a_1, a_2) + lcm(a_1, a_2), which is true because the two summands on the left hand side have the same product as the two summands on the right hand side but are (if different at all) nearer together.
So the first actual case is
a_1+a_2+a_3-gcd(a_1,a_2)-gcd(a_1,a_3)-gcd(a_2,a_3)+gcd(a_1,a_2,a_3) <= min(lcm(a_1, a_2), lcm(a_1,a_3), lcm(a_2,a_3)).
(as a correction to my other comment – max of LCM’s)
The greedy approach will work find for n < 10920. For n = 10920, making poor choices for A_1…A_839 can make picking A_840 impossible: A_840 has to be disjoint from sets with total size 11056. For an example, see http://paste.debian.net/1244717/
Note that in constructing the example, I deliberately made A_i with lcm(i,840) <= n and i != 780 disjoint. The natural implementation that always prefers small numbers will work for this n.
Interesting — thank you!
I had no expectation that the greedy algorithm would work, and was amazed that it seemed to do so well. If the result is true, as I hope, I don’t think the greedy algorithm is likely to be the way to do it. But no other approach I have tried works either…
Let i, n be positive integers, i <= n. Suppose by some process we have constructed A_1, A_2, …, A_{i-1}. Let
B_i = union {A_j: lcm(j,i) <= n, 1 <= j < i }.
Some observations are worth making.
(i) If we can prove that |B_i| n/2, then |B_i| = i – phi(i).
Proof. For 1 <= j < i, we have lcm(j, i) <= n only when j | i. Moreover, the sets A_j, 1 <= j < i, j | i, are pairwise disjoint. Therefore
|B_i| = sum_{j | i,1 <= j < i} |A_i| = sum_{j | i, 1 <= j < i} phi(j) = i – phi(i).
(iv) Also note that if i <= sqrt{n}, then
|B_i| <= sum_{j=1}^{i-1} phi(j) <= n – phi(i).
(v) If someone can deal with sqrt{n} < i <= n/2, we are done.
(vi) By (iii), the algorithm is tight since there is no choice for the phi(n) elements of A_n.
Oh dear, a few lines of my reply got mangled. Here is what they should be
(i) If we can prove that |B_i| n/2, then |B_i| = i – phi(i).
Proof. …