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.