Join-closed subgroup description rule

From Groupprops
Jump to: navigation, search

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


BEWARE! This term is nonstandard and is being used locally within the wiki. [SHOW MORE]

Definition

A subgroup description rule is join-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 join 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 a join-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 join is also polynomial in the log size. We can thus "efficiently" perform many operations and manipulations of subgroups that involve their intersection.

Relation with other properties

Related properties