# Difference between revisions of "Fraction of tuples satisfying groupy relation in subgroup is at least as much as in whole group"

(→Related facts) |
(→Proof: Fix \cap -> \times) |
||

Line 75: | Line 75: | ||

For <math>g \in G</math>, define <math>R_{g,n}</math> as the relation on <math>G^{n-1}</math> induced by <math>R</math> with the last coordinate <math>g</math>. Then: | For <math>g \in G</math>, define <math>R_{g,n}</math> as the relation on <math>G^{n-1}</math> induced by <math>R</math> with the last coordinate <math>g</math>. Then: | ||

− | <math>\! |R \cap (G^{n-1} \ | + | <math>\! |R \cap (G^{n-1} \times H)| = \sum_{h \in H} |R_{h,n}| \qquad (6)</math> |

Finally, we have: | Finally, we have: | ||

Line 83: | Line 83: | ||

Dividing (6) and (7) by <math>|G^{n-1} \times H|</math> and <math>|H^n|</math> respectively, we get: | Dividing (6) and (7) by <math>|G^{n-1} \times H|</math> and <math>|H^n|</math> respectively, we get: | ||

− | <math>\! \frac{|R \cap (G^{n-1} \ | + | <math>\! \frac{|R \cap (G^{n-1} \times H)|}{|G^{n-1} \times H|} = \frac{1}{|H|}\sum_{h \in H} \frac{|R_{h,n}|}{|G^{n-1}|}\qquad(8)</math> |

and: | and: | ||

Line 95: | Line 95: | ||

Plugging (10) into the summations on the right sides of (8) and (9), we get: | Plugging (10) into the summations on the right sides of (8) and (9), we get: | ||

− | <math>\! \frac{|R \cap H^n|}{|H^n|} \ge \frac{|R \cap (G^{n-1} \ | + | <math>\! \frac{|R \cap H^n|}{|H^n|} \ge \frac{|R \cap (G^{n-1} \times H)|}{|G^{n-1} \times H|} \qquad (11)</math> |

Combining (5) and (11) yields the desired results. | Combining (5) and (11) yields the desired results. | ||

+ | |||

==External links== | ==External links== | ||

* Related MathOverflow question: [http://mathoverflow.net/questions/39798/ In an inductive family of groups, does the probability that a particular word is satisfied converge?] | * Related MathOverflow question: [http://mathoverflow.net/questions/39798/ In an inductive family of groups, does the probability that a particular word is satisfied converge?] |

## Latest revision as of 02:50, 6 July 2019

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?