Intersection-closed subgroup description rule
This article defines a property that can be evaluated for a subgroup description rule, viz a rule for describing a subgroup of a group given an encoding
Definition
A subgroup description rule is intersection-closed if we have an algorithm that, given a group with an encoding, and two subgroups of the group, each described using the subgroup description rule, outputs a description of their intersection using the subgroup description rule, such that:
- The size of the description of the intersection is bounded by a polynomial in the sizes of the descriptions of the two subgroups, the logarithm of the size of the group, and the size of the encoding.
- The time taken is also a polynomial in the sizes of the descriptions, the size of the encoding and the logarithm of the size of the group
Facts
If we have an intersection-closed subgroup description rule, that in particular means that given a log-size encoding and given two subgroups with descriptions that are polynomial in the log size, the description of their intersection is also polynomial in the log size. We can thus "efficiently" perform many operations and manipulations of subgroups that involve their intersection.