Asymptotic Maximal Density of Weakly Triple-Free Sets

The analysis given here is based on splitting the interval [1, n] in a very
special way, patterned after related discussions concerning double-free sets 
and strongly triple-free sets.  We assume familarity with these.

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

                 (1/3) * ( 1*(1 - 1/2)
                         + 2*(1/2 - 1/3) 
                         + 2*(1/3 - 1/4)
                         + 3*(1/4 - 1/6)
                         + 4*(1/6 - 1/8)
                         + 5*(1/8 - 1/9)
                         + 5*(1/9 - 1/12)
                         + 6*(1/12 - 1/16)
                         + 7*(1/16 - 1/18)
		         + 7*(1/18 - 1/24)
                         + 8*(1/24 - 1/27)
		         + 8*(1/27 - 1/32)
                         + 9*(1/32 - 1/36)
		         + 10*(1/36 - 1/48)                          
			 + 11*(1/48 - 1/54)
			 + 11*(1/54 - 1/64)
                         + 12*(1/64 - 1/72)
			 + 13*(1/72 - 1/81)
                         + 13*(1/81 - 1/96)
			 + 14*(1/96 - 1/108)
                         + 14*(1/108 - 1/128)
			 + 15*(1/128 - 1/144)
			 + 16*(1/144 - 1/162)			  
			 + 16*(1/162 - 1/192)  
			 + 17*(1/192 - 1/216)
			 + 18*(1/216 - 1/243)
			 + 18*(1/243 - 1/256)
			 + 19*(1/256 - 1/288)
			 + 20*(1/288 - 1/324)
			 + 20*(1/324 - 1/384)
			 + 21*(1/384 - 1/432)
			 + 22*(1/432 - 1/486)
			 + 22*(1/486 - 1/512)
			 + 23*(1/512 - 1/576)
			 + 24*(1/576 - 1/648)
			 + 24*(1/648 - 1/729)         
                         ... )

Like the strongly triple-free case, no exact expression for the sum is 
known.  Let us explain, for example, how the 13*(1/81 - 1/96) term arose.

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

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

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

The coefficient 13 in the 13*(1/81 - 1/96) term arises since 13 is 
the weak independence number of the graph.   I don't know if this idea 
has been given a name before.  The weak independence number is defined to 
be the maximum possible cardinality of foreign vertices.  Three vertices
u, v and w are foreign given that the following condition holds:

	if u, v are adjacent (say), then u, w are non-adjacent and
	v, w are non-adjacent
or
	if u, v are adjacent and v, w are adjacent (say),
	then the "upper-triangles"

		   v - w     	       v - u
		   |	     and       |		
		   u		       w

	don't occur.

Observe that an independent set of vertices is vacuously foreign, i.e.,
foreignness is a generalization of non-adjacency in grid graphs.

For the above example, we indicate the set of foreign vertices of maximum 
cardinality (replacing the remaining 6 vertices by ## - observe that
we cannot use any of these, as each would form an "upper-triangle" with
vertices already taken).

     			1  -  ## -  9  -  27  -  ##  
			|     |     |     |          
      			2  -  6  -  ## -  54  
			|     |     |            
      			## -  12 -  36  
			|     |     |    
     			8  -  ## -  72 
			|     |            
     			## -  48  
			|            
     			32    
			|     
			64  

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

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 5 in the 5*(1/8 - 1/9) term arises since 5 is the 
weak independence number of the graph:

      			   1  -  3   
			   |     |           
      			   ## -  6  
			   |      
      			   4  
			   |  
     			   8  

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 weak 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.

Summing the 36 terms above gives a lower bound of 0.78. Cassaigne improved
on this and gave a proof that the weakly triple-free set constant is at
least 4/5.  Here is his e-message.  In his exposition, he denoted the 
k-th integer of the form 2^i*3^j by d(k)  (for example, d(6)=8),  the 
k-th weak independence number by f(k) (for example, f(6)=5 and f(19)=13) 
and the weakly triple-free set constant by lambda.

Graham, Spencer & Witsenhausen [3] wondered if f(k) = 1 + [2*k/3] if k is
1 or 2 mod 3.  They also wondered (as did Erdös & Graham [4]) whether
lambda is irrational.

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