Another Cameron–Erdős problem solved

In 1990, Paul Erdős and I published a paper on the topic of counting subsets of the first n natural numbers satisfying some restriction.

The case we worked hardest on, and which attracted the most interest (it has its own Wikipedia page) concerned sum-free sets, those containing no solution to the equation x+y = z. We conjectured that the number of such sets is asymptotically c.2n/2, where the constant c depends on the parity of n (that is, there are two different constants, one for even numbers and one for odd). We made substantial progress on this, and the proof was given independently by Ben Green and Sasha Sapozhenko. It was rather pleasing to me that we had divided the sets into three classes, and proved the result for two of the three; Ben Green showed that the third class is asymptotically smaller.

But we considered many other problems in the paper. Some we solved, but for many we were able to say something, though less than a solution.

One example was sets satisfying the condition that no element of the set divides any other. We conjectured that the number f(n) of such sequences grows exponentially, in the sense that (f(n))1/n tends to a limit as n→∞. By giving upper and lower bounds for f(n), we were able to show that the putative limit would be between 1.56 and 1.59. I thought this might be one of the first to fall …

I am happy to report that our conjecture has been proved by Rodrigo Angelo in the latest edition of Integers. It is a lovely proof, short but intricate; though my acquaintance with Paul was rather brief, I do believe that he would have enjoyed it.

Unfortunately the proof gives no information about the limit, either its numerical value or its status as rational, algebraic or transcendental. So still work to do.

About Peter Cameron

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

Leave a Reply

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

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

Google photo

You are commenting using your Google 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.