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.