Asymptotic Maximal Density of Strongly Triple-Free Sets

The analysis given here is based on splitting the interval [1, n] in a
very special way, patterned after a discussion by Eppstein.  A related 
proof was given elsewhere concerning double-free sets and we assume 
familarity with this.

The outcome of our analysis is an infinite series representation for the 
strongly triple-free set constant:

                  (1/3) * ( 1*(1 - 1/2)
                          + 1*(1/2 - 1/3) 
                          + 2*(1/3 - 1/4)
                          + 2*(1/4 - 1/6)
                          + 3*(1/6 - 1/8)
                          + 3*(1/8 - 1/9)
                          + 4*(1/9 - 1/12)
                          + 4*(1/12 - 1/16)
                          + 5*(1/16 - 1/18)
			  + 5*(1/18 - 1/24)
                          + 6*(1/24 - 1/27)
			  + 6*(1/27 - 1/32)
                          + 7*(1/32 - 1/36)
			  + 7*(1/36 - 1/48)
                          + 8*(1/48 - 1/54)
			  + 8*(1/54 - 1/64)
                          + 9*(1/64 - 1/72)
			  + 9*(1/72 - 1/81)
                          + 10*(1/81 - 1/96)
			  + 11*(1/96 - 1/108)
                          ... )

Note that the expected pattern for the integer coefficients just 
broke down (the last term has 11, not 10). Unlike the double-free case,  
no exact expression for the sum is known. Let us explain, for example, 
how the 11*(1/96 - 1/108) term arose.

First, consider all integers m satisfying  n/108 <= m <= n/96 and which
are 1 or 5 modulo 6.  To each of these integers m, associate a grid graph 
with 20 vertices:

      			1  -  3  -  9  -  27 -  81
			|     |     |     |     
      			2  -  6  -  18 -  54 
			|     |     |     
      			4  -  12 -  36 
			|     |     |
     			8  -  24 -  72   
			|     |
     			16 -  48
			|     |    
     			32 -  96 
			|
			64

using the shorthand notation introduced when we studied double-free sets.
The vertices are labeled by integers 1 <= 2^i*3^j <= 96  where x and 2*x 
are linked vertically and y and 3*y are linked horizontally.

The coefficient 11 in the 11*(1/96 - 1/108) term arises since 11 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/96 - 1/108 arises since this is the proportion of 
of integers from [1, n] which fall in [n/108, n/96].

Let us now do a smaller example. Consider all integers m = 1,5 mod 6 
satisfying  n/9 <= m <= n/8.  To each of these integers m, associate a 
grid graph with 6 vertices:

      			   1  -  3   
			   |     |           
      			   2  -  6  
			   |      
      			   4  
			   |  
     			   8  

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

Each of these grid 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/3 comes from
the fact that we have fragments associated only with integers m=1,5 mod 6.

Zimmermann (and, independently, Calkin) found a fast method to compute 
the independence numbers to arbitrary size and hence to estimate the
strongly triple-free set constant.  The method rested on the truth of
a conjecture which was subsequently proved by Cassaigne - details are
found in Cassaigne & Zimmermann [2].  

Is the strongly triple-free set constant irrational? Can this method be 
extended to estimate the strongly quadruple-free set constant (where x 
in S implies that 2*x, 3*x and 4*x are avoided)?

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