Asymptotic Maximal Density of Double-Free Sets

The proof given here is based on splitting the interval [1, n] in a
very special way, patterned after a discussion by Eppstein.  In the end, 
we take the limit as n approaches infinity, so it is best to think of 
n as large.

The penultimate step of our analysis is an infinite series representation
for the double-free set constant:

	          (1/2) * ( 1*(1 - 1/2)
                          + 1*(1/2 - 1/4) 
                          + 2*(1/4 - 1/8)
                          + 2*(1/8 - 1/16)
                          + 3*(1/16 - 1/32)
                          + 3*(1/32 - 1/64)  
                          + 4*(1/64 - 1/128)
                          + 4*(1/128 - 1/256)                      
                          ... )

In the final step, this is easily shown to sum to 2/3, as was to be 
proved.  Let us explain, for example, how the 4*(1/128 - 1/256) term
arose.

First, consider all odd integers m satisfying  n/256 <= m <= n/128. 
To each of these integers m, associate a linear graph with 8 vertices:

	   m - 2m - 4m - 8m - 16m - 32m - 64m - 128m 

The coefficient 4 in the 4*(1/128 - 1/256) term arises since 4 is 
the independence number of the graph.  The independence number is 
defined to be the maximum possible cardinality of non-adjacent vertices.  

The factor 1/128 - 1/256 arises since this is the proportion of 
of integers from [1, n] which fall in [n/256, n/128].

Let us now do a smaller example. Consider all odd integers m satisfying  
n/8 <= m <= n/4.  To each of these integers m, associate a linear graph 
with 3 vertices:

			m - 2m - 4m 

The coefficient 2 in the 2*(1/4 - 1/8) term arises since 2 is the 
independence number of the graph.  The factor 1/4 - 1/8 arises since 
this is the proportion of integers from [1, n] which fall in [n/4, n/8].

Each of these linear graphs are disconnected fragments of a much larger
graph G.  The graph G encodes information about the interval [1, n].  
Each fragment includes only certain values up to n,  and each value
from 1 to n is included in exactly one such fragment.  Our analysis is
based on the simple observation that we can choose the optimal subset
independently in each fragment without worrying about what's happening
in any other fragments.

After this, we add together all the independence numbers multiplied
by the correct proportionalities.  The initial coefficient 1/2 comes from
the fact that we have fragments associated only with odd integers m.

One last note:  the two linear graphs mentioned above could more simply 
be written as

	     1 - 2 - 4 - 8 - 16 - 32 - 64 - 128

and

		       1 - 2 - 4 

as if we omitted m.  We'll adopt this shorthand notation in subsequent
discussions.

Copyright (c) 2002 Steven R. Finch.
All rights reserved.