A simple(?) problem involving small sets of integers

[Swammerdami]

Let A be a finite set of positive integers, and N = |A| be the size of A.

We shall say that A is pleasant if for all x,y ∈ A

x / gcd(x,y) ≤ N​

(The gcd(x,y) -- greatest common divisor -- is the largest positive integer that divides both x and y.)

For example, suppose A = {2, 3, 4, 5, 6}. N = 5 and A is "almost" pleasant. Almost every x,y pair gives x / gcd(x,y) ≤ 5 but there is one exception: 6 / gcd(6,5) = 6/1 = 6. But 6 > 5.

Your mission is to find all (finite) pleasant sets! (If you're not required to prove your list complete, this is not overly difficult!)


If there's interest I will follow-up with hints and some background on the problem.

 

[lpetrich]

Here are some pleasant sets: every {1, 2, ..., n} for some n. Every member is <= n, and thus, for every x, y in the set, x/gcd(x,y) <= n.

These are the only pleasant sets that include 1, because if there is some gap, the maximum member > N.

If the lowest member is 2, then every member > N must be even. This makes the maximum 2N: {2, 4, 6, ..., 2N}

Much the same is true for lowest member m. Every member > N must be divisible by m, and the maximum is m*N: {m, 2m, 3m, ..., N*m}

 

[Swammerdami]

Here are some pleasant sets: every {1, 2, ..., n} for some n. Every member is <= n, and thus, for every x, y in the set, x/gcd(x,y) <= n.

These are the only pleasant sets that include 1, because if there is some gap, the maximum member > N.

If the lowest member is 2, then every member > N must be even. This makes the maximum 2N: {2, 4, 6, ..., 2N}

Much the same is true for lowest member m. Every member > N must be divisible by m, and the maximum is m*N: {m, 2m, 3m, ..., N*m}

Thank you, lpetrich! You have correctly pointed out that
* If {u, ..., x, y, z} is pleasant than so is {au, ... ax, ay, az} for any multiplier a; and that
* {1, 2, 3, 4, ..., N} is a schema yielding an infinite number of pleasant sets (one for each N ).

There are some more pleasant sets:
* another schema (one pleasant set for each N)
* one unique small set which fits into no schema.

I'll wait a while before posting why this problem is "very special" for me!

 

[Swammerdami]

I was a young teenager when I overheard this problem from top mathematicians at a dining table at U.C. Berkeley. ("Here's a problem making the rounds on the East Coast.") The comment was briefer than my OP, and the subject immediately changed but I remembered the problem and tried to work on it for several months. I quickly found the three solutions; I conjectured there were no more; proved several theorems toward that fact; but full proof eluded me.

BTW, there is an alternate and equivalent statement of the problem: Instead of sets of positive integers, work with sets of positive rationals: A set of N positive rationals is pleasant if the quotient (reduced to lowest terms) of any two elements has numerator and denominator both ≤ N. (BTW, I first invented the term "pleasant set" just a few days ago when I wrote OP. AFAIK the problem had no particular name.)

I don't remember if the problem I originally overheard was expressed about sets of positive integers or about positive rationals, but the former is slightly easier to talk about. We can also stipulate that the N elements have no common factor: With that we need not consider {11, 22, 33, 44, 55} a solution distinct from {1, 2, 3, 4, 5}.

As I worked on the problem, I concluded that it was difficult ("impossible") to pack N integers into (k ... Nk) without violating the constraint. There wasn't "room enough" for them, except for the three specific solutions.

It struck me as a beautiful, almost important, fact! It seemed much PURER than many famous conjectures. For example Goldbach: "every even natural number greater than 2 is the sum of two prime numbers." So what?? Goldbach's is almost just a probabilistic fact: As numbers get larger the odds against a counterexample grow astronomically. But the "pleasant set" conjecture didn't seem "probabilistic": Outside the three exceptions, my playing-around suggested that non-trivial pleasant sets were IMPOSSIBLE!

- - - - - - - - - - - - -

Although proving uniqueness is very difficult, finding the three pleasant sets isn't so hard. Come on, Infidels! Earn yourselves a big Hoorah!

- - - - - - - - - - - - -

Although I abandoned my own meager effort, the problem stuck with me. In the early 1980's I found myself in the math library of the Chulalongkorn University in downtown Bangkok. I leafed through math journals and came across the problem. Someone had written a paper displaying the same theorems I had discovered myself. But no complete proof.

Circa 1990 I came across another paper, probably at the Stanford Library. It DID have a complete proof, but a proof which involved elliptic functions and worse -- well beyond my own pons asinorum. (There are LOTS of math journals and how I stumbled on these two papers without any search terms is itself a bit of a mystery!)

 

[Tigers!]

I always look forward to meeting pleasant numbers as opposed to those dastardly unpleasant ones.

 

[lpetrich]

I'll try to find all the small pleasant sets.

First, scale the solutions A = {a1,a2,...,an} such that gcd(A) = 1. This is always possible, because if A is a solution, then b*A is also a solution, and vice versa.

If every member of A is coprime (relatively prime) to every other member, then a/gcd(a,b) = a for all a and b in A. The maximum of a is the number of members N, so the a's are 1, 2, 3, ..., N.

Also, if A contains 1, then the only solution is the a's being 1, 2, 3, ..., N.

That also takes care of every solution with 1 or 2 members: {1} and {1,2}.


For 3 members, let us consider {q*a,q*b,c} where (a,b), (a,c), (b,c), and (q,c) are all coprime pairs.

This means that c <= 3 while the others can be larger. But since q*a and q*b are coprime to c, that also makes them <= 3, so we don't get a new solution.

We must consider some fancier divisibility: {a1*b2*b3, a2*b1*b3, a3*b1*b2} gcd(first two) = gcd(a1*b2,a2*b1) * b3 and (first one) / gcd(first two) = a1*b2/gcd(a1*b2,a2*b1)

I'm stumped.

I will consider {2, a, b} where a, b are > 1. If both a and b are odd, then a >= 3 and b > a, meaning at least 3, 5, and thus failing.

Therefore, at least one of the two must be even: {2, a, 2*b} where b > 1. If the remaining one, a, is even, then the triplet can be scaled down by 2. If it is odd, it, can only be 3, giving us {2, 3, 2*b}

The defining condition for the first and third ones gives us b <= 3, and for the second and third one, 2*b/gcd(3,b) <= 3, giving us b/gcd(3,b) <= 1. That means that b must be divisible by 3.

That gets us {2, 3, 6*b} and applying the defining condition to the third one gives us 2*b and 3*b, meaning that b = 1:

{2, 3, 6}


If one does {3, a, b} where a, b > 3, then a/gcd(a,3) <= 3, and if a and 3 are coprime, a <= 3. So a has to be divisible by 3. The same argument shows that b is also divisible by 3, giving us {3, 3a, 3b} giving us 3*{1,a,b} with solution 3*{1,2,3} = {3,6,9}.

 

[Swammerdami]

{2, 3, 6}

This is the N=3 case of the 2nd schema I alluded to above. This 2nd schema is closely related to the first schema ( {1,2,3,...,N} ).

(And there is a 3rd solution, a special and unique "pleasant" set with a specific size N.)

 

[lpetrich]

I tried solving with brute force, up to some maximum values in the lists. That has obvious limitations, I will concede, but that's a good way of looking for small-number solutions.

Length 3, maxval 1000
1 2 3
2 3 6

Length 4, maxval 500
1 2 3 4
2 3 4 6
3 4 6 12

Length 5, maxval 200
1 2 3 4 5
12 15 20 30 60

3:
6 / 3 2 1

4:
12 / 6 4 3 2
12 / 4 3 2 1

5:
60 / 5 4 3 2 1

 

[lpetrich]

There are two regular kinds of solution.

The first one is range(N): {1, 2, 3, ..., N}

The second one is lcm(x)/x for x = range(N)

The second one can be interpreted as a kind of inversion of the first one: inv(x) = lcm(x)/x making the second solution inv(range(N))

Repeating the inversion gives inv(inv(x)) = x/gcd(x) -- an irreducible solution, where a reducible one has gcd(all) > 1.

The pleasantness condition on an inverse lcm(all)/x for each x in a solution:

( lcm(all)/x ) / ( gcd( lcm(all)/x, lcm(all)/y ) ) =
( lcm(all)/x ) / ( lcm(all) / lcm(x,y) ) =
lcm(x,y) / x =
y / gcd(x,y)

So if some list is pleasant, then its inverse list is also pleasant.

The remaining solution is {2,3,4,6} and it is its own inverse.

 

[Swammerdami]

...

So if some list is pleasant, then its inverse list is also pleasant.

The remaining solution is {2,3,4,6} and it is its own inverse.

Congratulations. You've solved it!

 

[lpetrich]

Reduction: red(x) = x/gcd(x)

Irreducibility: isirr(x) = (gcd(x) == 1)

Reduction has an irreducible result: isirr(red(x)) = true

Inversion: inv(x) = lcm(x)/x

Inversion has an irreducible result: isirr(inv(x)) = true

Inverseion of inversion is reduction: inv(inv(x)) = red(x)

Having found solutions range, inv(range), and {2,3,4,6}, the next question is: are there any others?

 

[lpetrich]

That last one should have "plain" BBCode tags to suppress those emojis:

Having found solutions range(n), inv(range(n)), and {2,3,4,6}, the next question is: are there any others?

 

[lpetrich]

Of solutions known to me, the only self-inverses are: range(1) = {1}, range(2) = {1,2}, and {2,3,4,6}

 

[Swammerdami]

Having found solutions range(n), inv(range(n)), and {2,3,4,6}, the next question is: are there any others?

As I said, a paper circa 1990 claimed to have proved the non-existence of other solutions. It used a complicated argument involving, IIRC, elliptic functions. I chastise myself for not remembering more nor photo-copying the paper. Finding the paper now would require a formidable scavenger hunt!

It certainly makes { 2, 3, 4, 6 } a very special set indeed!

When I looked for more solutions in the 1960's I soon intuited that there weren't any. The packing increases in difficulty as N increases.

I felt that this conjecture -- when it was still just a conjecture -- was under-appreciated. Many conjectures are difficult puzzles whose proof, if any, must be almost magical! But this one -- call it the 2-3-4-6 Conjecture -- seems like it SHOULD have an easyish proof.

- - - - - - - - -

Another interesting conjecture, somewhat less well-known than Collatz, Goldbach etc., is one by Paul Erdős --  Erdős–Straus conjecture. (I think it's "difficulty/magicness" resembles that of Collatz/Goldbach rather than 2-3-4-6.)
To Prove:

For any positive integer n ≥ 2, there exist positive integers x, y, z with​

4/n = 1/x + 1/y + 1/z​