Fraction of tuples satisfying groupy relation in subgroup is at least as much as in whole group
This article is about a result whose hypothesis or conclusion has to do with the fraction of group elements or tuples of group elements satisfying a particular condition.
View other such statements
Statement
Suppose is a finite group. Suppose
is a
-ary relation on
with the property that if we consider a
-tuple
, and we fix all coordinates except the
coordinate, the set of possibilities for
forms a subgroup of
.
Suppose is a subgroup of
. Then, we have:
In other words, the fraction of -tuples from
satisfying
is at least as much as the fraction of
-tuples in
satisfying
.
Related facts
Applications
- Commuting fraction in subgroup is at least as much as in whole group
- Commuting fraction in subring of finite non-associative ring is at least as much as in whole ring
- Commuting fraction in subring of finite Lie ring is at least as much as in whole ring
- Associating fraction in subring of finite non-associative ring is at least as much as in whole ring
- Fraction of tuples for iterated Lie bracket word in subring of finite Lie ring is at least as much as in whole ring
Facts used
- Index satisfies transfer inequality: This states that if
, then
. However, the form in which we use it is the conditional probability formulation, which states that:
(Note: The letters have interchanged roles compared to the formulation of the result on its original page.)
Proof
Given: Finite group , groupy
-ary relation
on
. Subgroup
of
.
To prove:
Proof: We prove the statement by induction on . The proof for the base case
and the induction step are similar, but we give both proofs.
Proof of base case: In the base case, the relation has only one element, which means that it is just a subset of
. The groupiness now says that this subset is a subgroup.Then, fact (1) yields that:
Inverting both sides and flipping the inequality sign yields:
Proof of induction step: Suppose we have shown the result for all -ary relations. We now need to show it for the
-ary relation
.
Define as the subset of
comprising those values of
such that
. Each such
is a subgroup, and:
Also, we have:
Dividing both sides of (1) by and both sides of (2) by
, we get respectively:
By fact (1), we have , yielding:
Thus, each of the summands to (4) is bigger than the corresponding summand to (3), and thus we get:
Multiplying both denominators by , we get:
For , define
as the relation on
induced by
with the last coordinate
. Then:
Finally, we have:
Dividing (6) and (7) by and
respectively, we get:
and:
Each is groupy. Thus, by induction, each
satisfies:
Plugging (10) into the summations on the right sides of (8) and (9), we get:
Combining (5) and (11) yields the desired results.
External links
- Related MathOverflow question: In an inductive family of groups, does the probability that a particular word is satisfied converge?