The OEIS is supported by the many generous donors to the OEIS Foundation.
From: Julien Cassaigne
Date: Wed, 20 Nov 1996
To: Steven Finch
Subject: Re: triple-free set constant
Dear Steve,
Here is the method I used to get a lower bound on f(k) and lambda.
Consider the example k = 36 (for which Graham, Spencer and Witsenhausen
give the value f(36) = 25, but I can only find f(36) >= 24). d(36) = 648.
Arrange the elements in the following way (call this D(36)):
1 2 4 8 16 32 64 128 256 512
3 6 12 24 48 96 192 384
9 18 36 72 144 288 576
27 54 108 216 432
81 162 324 648
243 486
Take the greatest element of every column. This certainly forms
a triple-free set, as a triple {x, 2x, 3x} is always arranged
in a triangle like this:
x 2x
3x
Now, we cannot use 162, 216, 144, 192 and 128 in our triple-free
set, as each of them would form a triple with the elements already
taken. Let's erase them from the diagram:
1 2 4 8 16 32 64 | ### 256 512 |
+-----+ +-----------+
3 6 12 24 48 96 | ### 384 |
+-----------+ +-----+
9 18 36 72 | ### 288 576 |
+-----+ +-----------+
27 54 108 | ### 432 |
+-----------+ +-----+
81 | ### 324 648 |
-----+ +-----------+
243 486 |
-----------+
The remaining part is exactly the diagram for d(21) = 108 = d(36)/6.
Observe that it is impossible to form a triple using elements of
this part and elements already taken (here we use the fact that
3 is less than the square of 2, which implies that the horizontal
segments in the boundary have length at most 2, and that any triple
overlapping the boundary involves a deleted element. So we can
recursively construct a triple-free set in D(21), and add our
10 selected elements to it. The final diagram is:
# 2 | # 8 16 | ## 64 | ### 256 512 |
+-----+ +-----------+ +-----+ +-----------+
3 | # 12 | ## 48 96 | ### 384 |
-----+ +-----+ +-----------+ +-----+
9 18 | ## 72 | ### 288 576 |
-----------+ +-----+ +-----------+
## 54 108 | ### 432 |
+-----------+ +-----+
81 | ### 324 648 |
-----+ +-----------+
243 486 |
-----------+
and we have a triple-free set with 24 elements. In fact, it is easier
to count deleted elements: we have 5 + 4 + 2 + 1 = 12 of them.
Let f'(k) be the size of the triple-free set constructed this way.
Then f'(k) <= f(k), and I would not be surprised if f'(k)=f(k).
Let's evaluate f'(k).
The number of columns in the diagram is [log_2(d(k))] + 1, and the
number of deleted elements is the number of lines minus one, i.e
[log_3(d(k))]. We thus have a recurrence formula on f'(k):
f'(k) = f'(k') + [log_2(d(k))] + 1
where
k' = k - [log_2(d(k))] - [log_3(d(k))] - 1
If d(k) is neither a power of 2 nor a power of 3, this gives
exactly d(k') = d(k) / 6. Otherwise, d(k') is the element of
D just below d(k) / 6.
The asymptotic behaviour of f'(k) is simple : f'(k) ~ k / C,
with C = log(6) / log(3).
Concerning the set K = {k(1), k(2), ...} where k(n) is the smallest
k for which f(k) = n, we have k(n) < k'(n) where k'(n) is the
smallest k for which f'(k)=n, and k'(n) ~ C n. More precisely,
let us study what happens when the element d(k+1) is added to the
diagram.
If d(k+1) is a power of 2, this new element cannot form any triple,
so we can just add it to the sum-free set: f'(k+1) = f'(k) + 1,
i.e. k+1 is in K' = {k'(1), k'(2), ...}.
If d(k+1) is a power of 3 (other than 1), e.g. in our example above
d(k+1)=729, then adding it would just increase the number of elements
to be deleted in the first step, and k' would not be changed:
f'(k+1) = f'(k), i.e. k+1 is not in K'.
Otherwise, the number of selected and deleted elements in the
first step would not change (d(k+1) being selected, d(k+1) / 3 deleted
instead of selected, and d(k+1) / 6 not deleted anymore: (k+1)' = k' + 1,
and f'(k+1) - f'(k) = f'(k'+1) - f'(k'), therefore k+1 is in K'
if and only if k'+1 is in K', with d(k'+1) = d(k+1) / 6.
We then have a procedure to decide if a number k is in K':
divide d(k) by 6 repetitively until we get a power of 2 or 3.
If d(k) = 2^i*3^j, then k is in K' if and only if i >= j.
Finally, let us turn to lambda = 1/3 sum {1/d(k), k in K}, or rather to
its lower bound lambda' = 1/3 sum {1/d(k), k in K'}. Using our
characterization for the elements of K', it can be computed exactly:
lambda' = 1/3 sum {2^(-i) 3^(-j), i >= j >= 0}
= 1/3 sum {2^(-h) 6^(-j), h >= 0, j >= 0}
= 1/3 * 2 * 6/5 = 4/5.
Now, the remaining question is whether the triple-free set we
have constructed is maximal. It is clearly maximal with respect
to inclusion, but there may be a completely different set which
gives a larger cardinal. As I was writing this message, I got
a few ideas on how to prove this, so let's try it.
[NOTE BY S. FINCH: attempted proof that f'(k)=f(k)
omitted - see further relevant comments below.]
Okay, I stop here for now. I will try to write more when I have
more inspiration.
Julien.
************************************************************************
From: Julien Cassaigne
Date: Fri, 22 Nov 1996
To: Steven Finch
Subject: Re: triple free set constant
...
Here is a much simpler proof that lambda >= 4/5 (from an
earlier message I sent you in April).
In general, proving lower bounds is not very difficult: it is
sufficient to exhibit the construction of a triple-free set.
What is difficult is to prove that it is maximal (and also
to discover the adequate set, but this difficulty is not visible
in the proof).
Consider the following subset of [1,n]:
S = { x | exists k, 1/(3.6^k) < x/n <= 1/6^k }.
S is the union of intervals [a(k)+1,b(k)], for 0 <= k <= log_6(n),
with a(k) = [n/(3.6^k)] and b(k) = [n/6^k].
The cardinal of S is 4/5 n + O(log(n)). For instance, for n = 100
we get the subset [1,2] union [6,16] union [34,100] that has exactly
80 elements. And it is not difficult to see that S is triple free:
if 1/(3.6^k) < x/n <= 2/(3.6^k),
then 1/6^k < 3x/n <= 1/(3.6^(k-1)), i.e. 3x is not in S;
and if 2/(3.6^k) < x/n <= 1/6^k,
then 1/6^k < 4/(3.6^k) < 2x/n <= 1/(3.6^(k-1)), i.e. 2x is not in S.
Julien.
************************************************************************
From: Julien Cassaigne
Date: Sat, 23 Nov 1996
To: Steven Finch
Subject: Re: triple free set constants essay now up
...
Concerning the values f(24)=17 and f(36)=25, I was indeed
convinced in April (and still when I wrote my message of
last Wednesday) that GWS were wrong. Now I still do not
know how these values can be obtained, but I am ready to
believe that they are correct, as I have found that my
construction is NOT optimal, i.e. eventually f'(k) < f(k).
A consequence of this is that my long message is not of
much use any more : there is a shorter way to prove that
lambda >= 4/5 (in fact, lambda > 4/5 now), and the last
part where I attempt to prove that f(k) = f'(k) is completely
useless.
In fact, it is very easy to see that f(k) = 2k/3 + O(sqrt(k)),
and I suspect that GWS were aware of this. This is a strong
argument in favor of their conjecture f(k) = 1 + [2k/3]
for k = 1, 2 (mod 3).
Here is the construction : take
S = { 2^i*3^j <= d(k) | i <> j (mod 3) }
Then S forms a regular pattern of density 2/3 in our triangular
array, with border effects concerning O(sqrt(k)) elements
(as the area of the triangle is about k). So f(k) >= 2k/3 + O(sqrt(k)).
Conversely, it is possible to pave most of the array (except some
border elements) with tiles {x, 2x, 3x}, and as at most two
elements of each tile can be in a triple-free set, we have
f(k) <= 2k/3 + O(sqrt(k)).
Curiously, this construction, although asymptotically optimal,
gives bad results for small values of k, whereas my construction
(which is just the greedy algorithm, starting with highest
numbers) is asymptotically very bad but gives almost correct
values (if GWS are right, the first incorrect values are
f'(24) and f'(36)).
...
Julien.
Copyright (c) 2002 Steven R. Finch.
All rights reserved.