From the archive, 5

The first of my two papers with Paul Erdős was published in 1990 in a conference proceedings, and is a bit inaccessible; I have never managed to find a copy on the web. The Hungarians are collecting electronic copies of all Paul’s papers; they have reached 1989. I thought I had run out of the few reprints the publishers sent me. So it was very timely that I found a small stash of copies on a shelf in my office.

I will summarise the theorems and conjectures in the paper. As far as I know, most of the conjectures are still open. I found these problems were a lot of fun to work on!

The title is “On the number of sets of integers with various properties”, and the paper does just that. We start by remarking that the largest subsets of {1…n} with various properties have been much studied, and that for properties closed under taking subsets, there is a close relationship between the two questions: if the largest subset has size m, then the number of subsets lies between 2m and the total number of subsets of size at most m. A related question is the Hausdorff dimension of the set of all subsets of the natural numbers with the property in question. (This number will be zero if the number of sets grows slower than exponentially, but the converse is not true. We’ll see an example below.)

We proceed to consider special cases.

Sum-free sets (no solution of x+y = z)

The largest subset has size n/2 (rounded up). We conjectured that the number of subsets was asymptotically c·2n/2, with two different constants depending on the parity of n. This became known as the Cameron–Erdős conjecture, and was proved independently by Sasha Sapozhenko and Ben Green. In the paper we give lower bounds for the constants; this is the major part of the paper, and the one we worked on in Cambridge in 1988, as I have told elsewhere. Green’s proof show that these are the actual values.

The Hausdorff dimension is 1/2.

Sidon sequences (no solution of x+y = z+w)

Known results about Sidon sequences, together with the generalities we began with, show that the number lies between 2(1+o(1))√n and n(1+o(1))√n. We make no conjecture as to the correct value, but we do show that the ratio of the number of Sidon sequences to 2m, where m is the size of the largest Sidon sequence, tends to infinity.

All partial sums distinct

We give lower and upper bounds of n(1+o(1))log n/log 3 and n(1+o(1))log n/log 2. We remark that, for sequences satisfying either of the stronger conditions that each term is at least twice the preceding term, or that each term is greater than the sum of all previous terms, we have an answer, namely n(1+o(1))log n/log 4.

Product-free sets (no solutions of xy = z)

There is a simple lower bound of 2n−√n.

The Hausdorff dimension is 1. This follows from the fact that there exist such sets with upper density greater than 1−ε for any positive ε. On the other hand, there is no set with upper density 1.

No term divides the product of all others

We give a lower bound of 2(c+o(1))π(n) in this case, where the constant c is 1.814….

For sequences with all pairwise products distinct, the upper bound is given by the same expression. The proof uses the result in Erdős’ famous Tomsk paper.

Requiring divisibility (of any two terms, the smaller divides the larger)

The number of such sequences with largest term n is twice the number of ordered factorisations of n (the 2 because we can include or exclude 1). This is very irregular, but our count is the sum function. Kalmár showed in 1930 that this is asymptotically cnα, where α = 1.7286… is the real number greater than 1 for which ζ(α) = 2. (I believe that Paul felt that he should have discovered this.)

Forbidding divisibility (no term divides another)

We showed that the number is between c1n and c2n, where c1 = 1.55967… and c1 = 1.59…, and conjectured that it is (c+o(1))n for some constant c. This is probably not too hard.

Paul had proved that a divisor-free sequence has lower density zero. It follows that the Hausdorff dimension of the set of such sequences is zero (despite the exponential growth).

Any two terms coprime

There is an obvious lower bound of 2π(n) (from sets of prime numbers). We show lower and upper bounds which are this function multiplied by e(c+o(1))√n, where c = 1/2 for the lower bound and c = 2 for the upper.

No two terms coprime

Since any set of even numbers satisfies the constraint, there is a lower bound of 2n/2⌋. We give an argument of Carl Pomerance to show an upper bound just n times as large.

The Hausdorff measure of the set of even numbers is 1/2. We conjectured that the set of all subsets of the natural numbers with no two entries coprime differs from the set of even numbers by a null set with respect to 1/2-dimensional Hausdorff measure.

Sum of reciprocals at most s

We conjecture that (f(n))1/n tends to a limit c(s) as n→∞. We prove that the limit inferior of this quantity is at least 21−es.

There are a few more things in the paper, but that is enough to go on with, I think.

About Peter Cameron

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

1 Response to From the archive, 5

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 )

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.