Two ordering problems

[Max Alekseyev]

On Thu, Aug 28, 2008 at 5:11 PM, Max Alekseyev <maxale at gmail.com> wrote:
> On Thu, Aug 28, 2008 at 4:05 PM,  <franktaw at netscape.net> wrote:
>> I'm pretty sure that  http://www.research.att.com/~njas/sequences/A009997 is
>> the desired sequence.  This can be interpreted as linear extensions of the
>> lattice 2^n induced by assigning a weight to each primitive element, and taking the sum
>> for the other nodes.  Taking the log of each divisor, we just need to match the
>> relative ordering of the sums.
>>
>> I don't really see how to prove the final step, but the primes are pretty
>> dense.  I would be astonished if any such arrangement cannot be obtained.
>
> Unfortunately, there exist such arrangements (for n>=5).
> Following the terminology of the paper
> http://arxiv.org/abs/math.CO/9809134 (cited in A009997), an order on
> the power set ("boolean term order") that is induced by some weights
> of the singletons is called coherent. An example of noncoherent order
> is given in Example 2.5 in the paper.

Oh, I misinterpreted your concern. Noncoherent orders are irrelevant here.

Below I will prove that every coherent boolean term order can be
induced by logarithms of some primes.

Suppose that a coherent boolean term order X is induced by weights w1
< w2 < ... < wn.
We need to show that it can be also induced by weights log(p1) <
log(p2) <  ... < log(pn) where pi are primes.

Let M be the minimum absolute value of the sum weights w1, ..., wn,
each taken with a coefficient -1, 0, or +1, with at least one non-zero
coefficient.
Let C = n*log(2) / M and W1 = C*w1, W2 = C*w2, ..., Wn = C*wn.

It is clear that that X is also induced by the weight W1, W2, ..., Wn
(actually, that is true for any constant C>0).

Choose pi in the in the interval [exp(Wi),2*exp(Wi)] (by Bertrand
postulate, such prime exists) so that
Wi < log(pi) < Wi + log(2).

Then for any subset of elements, the sum of the elements S satisfies
the inequality
S < P < S + n*log(2)
where P is the sum of the corresponding logarithms of primes.

By the choice of C, for two distinct subsets of weight and the sums of
their elements S1 and S2 (wlog, assume that S1 > S2)
S1 - S2 > n*log(2),
implying that for the sums of the corresponding logarithms of primes
P1 > S1 > S2 + n*log(2) > P2.
Therefore, S1 > S2 implies P1 > P2, and vice versa.
Hence, X is also induced by log(p1), ..., log(pn).

Regards,
Max