3.2 The Number of Possible Rules

Given a particular signature, one may ask how many distinct possible canonical rules there are with that signature. As a first step, one can ask how many distinct elements can occur in the rule. If the rule signature has terms n_iki on both left and right, the maximum conceivable number of distinct elements is ∑n_ik_i. (For example, a possible canonical 2₂  2₂ rule is {{1,2},{3,4}}{{5,6},{7,8}}.)

But for many purposes we will want to impose connectivity constraints on the rule. For example, we may want the hypergraph corresponding to the relations on the left-hand side of the rule to be connected [9], and for elements in these relations to appear in some way on the right. Requiring this kind of “left connectivity” reduces the maximum conceivable number of distinct elements to (or 6 for 2₂  2₂). (If the right-hand side is also required to be a connected hypergraph, the maximum number of distinct elements is 1 + ∑n_i(k_i–1), or 5 for 2₂  2₂.)

Given a maximum number of possible elements m, an immediate upper bound on the number of rules is m^∑n_ik_i. But this is usually a dramatic overestimate, because most rules are not canonical. For example, it would imply 1,679,616 left-connected 2₂  2₂ rules, but actually there are only 562 canonical such rules.

The following gives the number of left-connected canonical rules for various rule signatures (for n₁anything there is always only one inequivalent left-connected rule):

Although the exact computation of these numbers seems to be comparatively complex, it is possible to obtain fairly accurate lower-bound estimates in terms of Bell numbers [10]. If one ignores connectivity constraints, the number of canonical rules is bounded below by BellB[∑n_i k_i]/∏n_i!. Here are some examples comparing the estimate with exact results both for the unconstrained and left-connected cases:

Based on the estimates, we can say that the number of canonical rules typically increases faster than exponentially as either n_i or k_i increases. (For 5≤n≤10874, one finds 2ⁿ<BellB[n]<2^{n log n}, and for larger n, 2ⁿ<BellB[n]<nⁿ.)

Note that given an estimate for unconstrained rules, an estimate for the number of left-connected rules can be found from the fraction of randomly sampled unconstrained rules that are left connected. For signature 1_p  1_q, the number of unconstrained canonical rules is BellB[p+q], but given the constraint of left-connectedness there is only ever one canonical rule in this case. When there are no connectivity constraints, the number of canonical rules for signature a  b is the same as for signature b  a. With the constraint of left connectivity, the number of 1₂  5₂ rules is slightly larger than 5₂  1₂ rules, because there are fewer constraints in the former case.

For any given signature, we can ask how many distinct elements occur in different canonical rules. Here are histograms for a few cases:

There are a number of features of rules that are important when using them in our models. First, if there are relations of arity k on the left-hand side of the rule, there must be relations of the same arity on the right-hand side if those relations are not just going to be inert under that rule. Thus, for example, a rule with signature a₂  b₃ will never (on its own) apply more than once, regardless of the values of a and b.

In addition, if a rule is going to have a chance of leading to growth, the number of relations of some arity on the right-hand side must be greater than the number of that arity on the left.

These two constraints, however, do not always apply if a complete rule involves several individual rules. Thus, for example, a complete rule containing individual rules with signatures 2₂  3₂2₁, 2₂1₁  1₂ can show growth, and can involve all relations. Note that since canonicalization is independent between different individual rules, the total number of possible inequivalent complete rules is just the product of the number of possible individual inequivalent rules.

When investigating cases where a large number of inequivalent rules are possible, it will often be convenient to do random sampling. If one picks a random rule first, and then canonicalizes it, some canonical rules will be significantly more common than others. But it is possible to pick with equal probability among canonical rules by choosing an integer between 1 and the total number of rules, then decoding this integer as discussed above to give the canonical rule.