Suppose we restrict the logic, and permit only monotonic boolean functions? Sorry, what's the definition of these? (I'm only familiar with monotonically increasing...) -- Mike Stay staym@clear.net.nz

First, if X and Y are in the orbit then the 1's of X are not a subset of the 1's of Y. For suppose this is the case. Write down the period starting with X: X, ..., Y, ........, (X) Now add 1's to the first X to turn it into Y and regenerate the period using the monotonic update rule. We get: Y, ........, X, ..., (Y) i.e. the same period but starting with Y. But since the update rule is monotonic, adding 1's to the first term can only add 1's to *all* terms and can never subtract 1's. Thus, the total number of 1's in the period has increased which is impossible. Next, let X_1, X_2, ..., X_k be *any* sequence such that for any X_i, X_j the 1's of X_i are not a subset of the ones of X_j. For each X_i, let T_i be the logical expression which is the AND of the bits which are 1 in X_i. For example, if X_3 = [1 0 0 1 0 1] then T_3 = (x1&x4&x6). To derive the update rule for the first bit, let i_1, i_2, ..., i_s be the indices of the X's in which the first bit is set. The update rule is then: x1 := T_(i_1-1) | T_(i_2-1) | ... | T_(i_s-1) where T_0 = T_k. This works because the term T_i is *only* activated by X_i, which follows from the fact that no other X_j has all the 1's of X_i. The update rules for the other bits are constructed similarly. Thus, the maximum orbit is equal to the maximum number of subsets of n elements that can be chosen so that no subset is contained in any other. J.P. Grossman On Fri, 29 Nov 2002, Allan C. Wechsler wrote:

Ooh, that subject line is so deliciously jargony. You are probably wondering what the hell I mean.

Suppose you have an automaton consisting of an n-bit register, where each bit's next state is a boolean function of the states of all the other bits. We wish to find a rule (that is, an update function for each bit) and an initial state that maximizes the number of states that the automaton traverses before it repeats a state.

The obvious maximum of a 2^n-state trajectory is easily achieved by creating a binary counter. Each bit will be on next time in two cases: if it is now on and some bit to its right is off; or if it is now off and all the bits to its right are on. (This is just the standard carry rule, "flattened" to a boolean function of the present bit values.)

But note that this logic is required to take explicit notice that certain bits are off. Suppose we restrict the logic, and permit only monotonic boolean functions? We now expect that the 2^n maximum cannot be achieved, in general. We can still implement an n-bit counter with monotonic update rules, but it takes 2n actual bits. So a lower bound of the maximum achievable orbit of such an automaton is 2^[n/2].

Can anyone tighten these lower and upper bounds of 2^[n/2] and 2^n?

-A

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

On Fri, Nov 29, 2002 at 03:09:32PM -0500, Allan C. Wechsler wrote: ...

The obvious maximum of a 2^n-state trajectory is easily achieved by creating a binary counter. Each bit will be on next time in two cases: if it is now on and some bit to its right is off; or if it is now off and all the bits to its right are on. (This is just the standard carry rule, "flattened" to a boolean function of the present bit values.)

But note that this logic is required to take explicit notice that certain bits are off. Suppose we restrict the logic, and permit only monotonic boolean functions? We now expect that the 2^n maximum cannot be achieved, in general. We can still implement an n-bit counter with monotonic update rules, but it takes 2n actual bits. So a lower bound of the maximum achievable orbit of such an automaton is 2^[n/2].

Can anyone tighten these lower and upper bounds of 2^[n/2] and 2^n? When you say that 2n bits is required to implement an n-bit counter, does this means that you know how to do it with 2n bits, or is this actually a proven bound for something?

Here are a couple of thoughts that improve the upper and lower bounds: For an upper bound: if it ever happens that the state at time t+1 is greater than the state at time t, from then on the sequence of states has to increase. The longest chain (increasing sequence) has length n, so after that it doesn't have long to live. Similarly if the state ever decreases, it plummets to 0. Therefore, if the constant function 0 or 1 is the initial state, then the length is <= n+1, not optimal for n > 1. Otherwise, you can't hit both, for if the chain ever reaches 0 or 1, it is the final state. This gives an upper bound of 2^n - 1 achievable states. I think you can generalize this using > relations between time t and t+k, but I haven't figured out any nice conclusion. In general, the necessary and sufficient condition for a sequence of states to be realizable by a monotone automaton: whenever state s_k < s_{k+l}, (k,l > 0) then for all j > k also s_j < s_{j+l} And similarly, with < replaced by >. This is just repharasing the condition that the map s_k -> s_{k+1} is monotone. Note that a monotone function defined on a subset of n-bit numbers extends to everything, by the defining the value as the sup of values on lesser (bitwise) numbers in the subset. For lower bounds: first, any sequence of incomparable elements can be the sequence of states---eg any sequence of n-bit numbers with k bits turned on (eg a binary counter, with digits repeated negated). But you can append any ascending sequence to the end, to improve the 2^[n/2]. Second, you can repeat any antichain with k of the bits, combined with any valid sequence for the remaining bits that changes once every period. E.g. this implies immediately that if f(n) is the greatest number of states achievable by a monotone automaton on n-bit numbers, f(n+2) >= 2*f(n) + 1: n | Lower bound for f(n) | example[s] of sequence that attains this 1 2 {0, 1} 2 3 {01,10,11} or {00,01,11} 3 5 {010,100,011,101,111} built from (length 2 antichain, length 1 chain) capped off with ascending chain. Is length 6 or 7 possible? 4 7 {0101, 1001, 0110, 1010, 0111, 1011, 1111} (length 2 antichain , length 2 soln) capped with chain. 5 11 {01001, 10001, 01101, 10101, 11101, 01010, 10010, 01110, 10110, 11110, 11111} Bill Thurston