I’d like to see this solved

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!

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, open problems. Bookmark the permalink.

9 Responses to I’d like to see this solved

  1. 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.

  2. Luke Pebody says:

    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?

      • Luke Pebody says:

        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)).

      • Luke Pebody says:

        (as a correction to my other comment – max of LCM’s)

  3. Bertram says:

    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…

  4. Tony Forbes says:

    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.

  5. Tony Forbes says:

    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. …

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.