This site is supported by donations to The OEIS Foundation.
User:Antti Karttunen/Speculations/On internal construction of A089840
From OeisWiki
Goal
To determine which clause-combinations (informally defined e.g. in http://oeis.org/A089840/a089840p.txt form a bijection of binary trees, and moreover, which combinations are minimal representations of the said bijection.
Questions and attempts at answer
The following is a set of questions approaching this topic, and some of my attempted answers or speculations about them. Some might turn out very trivial after a bit more concentration on it. Some other time I might have confused myself.
Some notes regarding A089840. Last edited Fri Sep 24 2010 by karttu. Any single clause is always a bijection when acting on infinite binary trees. (I.e. maps to some member of Thompson's V group.) 1) Q: When is a clause a minimal clause in Thompson's V? A: When it doesn't contain any V moved with the relative positions of it two leaves (L&R) left intact, e.g. as: L R L R \./ x \./ \./ --> \./ 2) Q: When does a single clause form a valid, minimal presentation of A089840-permutation? A: When it is form-preserving (i.e. the source and the destination tree are of the same shape). (Doesn't need to be a minimal clause in Thompson's V. The only requirement is that the leaves-permutation is not an identity permutation). 3) Q: When does a multiple set of clauses form a valid bijection? (E.g. a member of A089840) A: When their ranges are disjoint. (Computed for the latter clauses from the domains restricted by the implications of the previous clauses.) 4) Q: When is the range of a latter clause disjoint from all the previous clauses? A: When it transfers an implied nil (leaf) to a position where a previous clause has transferred a subtree (a non-leaf node), and this viz-a-vis all previous clauses. That is, only if, for all previous clauses, this clause transfers an implied nil (not necessarily the same in all cases but in any case, implied nil _with respect to that specific previous clause_) to some of those positions, where any previous clause has transferred a subtree. E.g. with just a binary tree rotation and the default clause: RL RR L RL L \./ \./ RR L () L () \./ --> \./ otherwise X -> X e.g. also: \./ --> \./ the latter clause does not transfer an implied nil to the position L, which leads to conflict in ranges. But this works: RL RR L RL L \./ \./ RR L () () L \./ --> \./ otherwise \./ --> \./ otherwise . -> . Here the last clause (the default-clause . -> .) has implied nil only at the root, because the intertwining clause (swap) "steals" all the larger trees from its domain. In general, preceding clauses steal all those trees from the latter clauses' domains, that match to their source trees. 5) Q: When is a latter clause unnecessary? A: if it is a super-tree of any previous clause, that is, if gcst(latter_clause,previous_clause) = previous_clause. In that case, the latter clause is never "activated", as the previous clause will match to all cases where it would match. This means that there would not be any implied nils with respect to that previous clause. (in other words, if it has no implied ?'s with _all_ the previous clauses). Thus, for any starting clause, its shape & size sets an upper limit how many successor clauses there can possibly be. (Not true, because for any non-trivial tree, we have an infinity of different trees larger than it, but not its supertrees! So we must iterate over the increasing total size (sum of all) clauses present, for example.) On the other hand, when the latter clause lacks a branch present in the previous clause, it means that the "stump" is implied to match some _genuine_ subtree of the tree located at the same position in the source clause of the previous clause. Usually, if the subtree in the previous clause is just \./ the implied genuine subtree must then be just (). However, larger cases are possible as well. E.g. when the transferred subtree in the previous clause is \./ \./ \./ then if the latter clause has just X in that position of its source clause, it implies that X can be either \./ N N \./ N N \./ or \./ or \./ or N (a leaf itself). and FURTHERMORE, that there MUST be an implied nil or non-existing node, either at: \./ N N \./ \./ or \./ or in both positions, in all cases. So there can be implied nils (leaves) on any internal node of the previous clause's transferred subtree, but "compulsory implied nils" only on leaves. (As a tree matching to the latter clause can be just "one-leaf-short" of not matching to a previous clause.) To get each set of compulsory implied nils in one disjunction, collect together those 1-bits in (and P (P xor T)) which have a common root (among those 1-bits), but themselves have no children. (i.e. are leaves). To check disjointness of ranges, _all_ "compulsory implied non-internal-nodes" of a particular subtree MUST BE OVER AN EXISTING INTERNAL NODE in the destination tree of the previous clause. E.g. if the previous clause has the following subtree transformation in some part of its source/destination trees: \./ \./ \./ \./ \./ --> \./ \./ \./ then a succeeding clause cannot have just a leaf X there, as: X X \./ --> \./ as that would match also \./ \./ \./ \./ which would lead to a range clash, unless there are implied nils elsewhere in the latter clause with regards to this clause. There is a conjunction of disjunctions of implied nils. (Each disjunction is formed from internal vertices of a subtree of of the previous clause, which is _left out_ of the dest-tree of the succeeding clause.) Conjunction is formed from several such sets collected from disctinct "outlying" subtrees. To avoid range clash, _all_ the compulsory implied nils (i.e. the leaves of an outlier-subtree) of _some_ (at least one) "disjunction" (in the set of all "conjunctions") must be transferred to a place where the previous clause transfers an internal node. This condition must be true viz-a-vis all previous clauses. (Of course the "some disjunction" does not need be same in all cases.) The place where the implied nil leaves are transferred is computed from the latter clause's destination tree, and they are compared to the previous clause's destination tree. So form first (bitand prev-clause-src (bitxor prev-clause-src this-clause-src)) to get those nodes that are in prev-clause-src, but not in this-clause-src. <But do we need also to check the positions where the prev-clause-src's implied nils (with respect to earlier clauses) are over the existing internal nodes of this-clause-src?> Then do some operation to separate them to a different sets, depending on whether they belong to same subtree or not, and get only the leaves of those subtrees. Then we have a set (conjunction) of the sets (disjunctions) of compulsory implied nils. NOTE: the set of implied nils/nil-leaves depends on all the clauses before this clause, not just of that against which we compare this. In general, the more clauses there are before that clause, the smaller it is. Then, transform those implied nils (by latter clause's shape-transformation src->dst) to new locations. For each such transferred disjunction (a set of implied nils obtained from one specific subtree), check that (bitand transferred-implied-nil-leaves-of-one-disjuction internal-nodes-of-prev-clauses-dest-tree) == transferred-implied-nil-leaves-of-one-disjuction i.e. that all will be on the existing internal nodes of the prev-clauses-dest-ree. If the above test does not match for _some_ of the disjunctions in the set of all disjunctions, then the clause has a range clash with the said previous clause. 6) Q: When can be the last (necessary, and non-default) clause be multiplied (with itse inverse, actually) out of the clause-sequence, to get a shorter clause-sequence of a different bijection? (Better formulated as: When does it result a shorter clause-sequence when the clause-sequence is multiplied with the inverse of the last non-default clause, if shape-preserving?) A: At least (to be checked!) when its source and destination trees are genuine subtrees of each previous clause's source and destination trees (respectively). E.g. consider the elements 253, 258 and 264 of A089840 for which that operation _cannot_ be done. Also, if by such multiplication one obtains e.g. an identity permutation, then one knows that the whole clause-sequence has the same effect as the last clause alone, so it is not a minimal clause-sequence, and thus is to be discarded. (Note: one might have to do that "multiply by the inverse of last" operation multiple times, to reduce the clause-sequence to identity. Maybe there's another way.) 7) Q: Can the duplicates be pruned with internal considerations only? (And especially, by not comparing to the preceding elements of A089840?) A: ??? (Maybe we can prune the duplicates having the same clauses, but in different order, just by testing all "lexicographically less" orderings of the clauses, and if any of them tests as a valid bijective combination, then we can discard this one? But is it true that the various permutations of the clauses would always produce the same bijection???!) 8) Q: Is it easy to develop and algorithm that composes two clause-sequences (elements of A089840), and gives the result, _without_ running the "transformator" externally on binary trees. A: ??? Develop some clause-optimizator routine, that simplifies clause-sequences and prunes off unnecessary clauses. 9) Q: Can we prove that group A089840 is not finitely generated? A: Maybe if we can prove that there's an infinite number of elements like 253, 258 and 264. Or, provided that we have a finite set of generators, none having more than u clauses, that by whichever we multiply them together, the resulting clause-sequence, when reduced to simplest terms, can never have more than k*u clauses. (The number of clauses in A089840 is not bounded.)
Note that the successive powers of *A074679 offer a counter-example to the penultimate sentence, that there would not be more than k*u clauses. I think that in this case, on the contrary, the number of clauses will increase indefinitely.
