Tour:Interdisciplinary problems two (beginners)

This page is a Interdisciplinary problems page, part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Examples peek two (beginners)| UP: Introduction two | NEXT: Inquiry problems two (beginners)
NEXT SECTION Interdisciplinary problems: Interdisciplinary problems three
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

The problems here relate ideas in group theory to ideas in other subjects. Learners who already have some experience with the other subjects may try these problems to cement their understanding of what has been learned in parts one and two of the tour.

Topology

A topological group is a set $G$ with a topology as well as a group structure, so that the inverse map is continuous with respect to the topology, and the multiplication map is continuous as a map from $G \times G$ to $G$.

We'll need to remember the following facts about topological groups:

• For a topological group $G$ and an element $g \in G$, the left multiplication by $g$, given by $x \mapsto gx$, is a homeomorphism. It sends open subsets to open subsets and closed subsets to closed subsets. Similarly, right multiplication by $g$ is a homeomorphism.
• An arbitrary union of open subsets of a topological space is open.
• A finite intersection of open subsets of a topological space is open.
• The subset of a topological space is closed if and only if its complement is open.

1. Prove that if $A$ is an open subset of a topological group $G$, then so is $Ax$ for any $x \in G$.
2. Prove that if $A,B$ are subsets of $G$, and either $A$ or $B$ is open, then $AB$ is open.
3. Prove that if $A,B$ are subsets of $G$, with $A$ closed and $B$ finite, then $AB$ is closed.
4. (For those who know product topology) Prove that if $A$ is a nonempty open subset of $G$, there exist nonempty open subsets $B,C$ of $G$ such that $BC \subseteq A$.
5. A topological group can also be defined as a set $G$ with a group structure and topology, such that the map $(x,y) \mapsto xy^{-1}$ is continuous as a map from $G \times G$ with the product topology, to $G$. Prove that this is equivalent to the usual definition of topological group.

Category theory

In most of the problems below, the key is to translate the statements from category theory. Most of the problems here have already been solved either in the results presented in the part, or in the mind's eye test problems.

The collections of groups, monoids etc. as categories

The questions mentioned here use only the object structure of the categories and do not refer to the morphisms.

1. Consider the functor from the category of groups to the category of monoids, that sends a group to its underlying monoid (forgetting the inverse map). Prove that this functor is injective on objects. In other words, two different groups cannot be mapped to the same monoid.
2. Consider the functor from the category of monoids to the category of semigroups, that sends a monoid to its underlying semigroup. Prove that this functor is injective on objects. In other words, two different monoids cannot be mapped to the same semigroup.
3. Consider the functor from the category of semigroups to the category of magmas, that sends a semigroup to its underlying magma. Prove that this functor is injective on objects.

The collection of groups, monoids etc. as categories with inclusion maps as the morphisms

1. Consider the category whose objects are groups, with the morphisms being the inclusion map of a subgroup in a group. Prove that this is a category, with composition of morphisms being composition of subgroup inclusions.
2. Consider a functor from this category to the category whose objects are monoids, with the morphisms being inclusion maps of a submonoid in a monoid. Prove that this functor is full, faithful and injective.
3. Consider a functor from the category of monoids with inclusion maps of submonoids, to the category of semigroups with inclusion maps of subsemigroups. Prove that the functor is faithful, but not full.
4. Consider the functor from the category of semigroups, with inclusion maps of subsemigroups, to the category of magmas, with inclusion maps of submagmas. Prove that the functor is full, faithful and injective.
5. Consider the composition functor from the category of groups with inclusion maps of subgroups to the category of magmas with inclusion maps of submagmas. Prove that the functor is full, faithful and injective.

Groups and monoids as morphisms

1. Prove that the morphisms from an object to itself in any (locally small) category form a monoid under composition.
2. Prove that the invertible morphisms from an object to itself in any (locally small) category form a group under composition. (this group is termed the automorphism group of the object).
3. Prove that there is a one-to-one correspondence between monoids and categories with one object.
4. An initial object in a category is an object with the property that there is a unique morphism from it to any object. Prove that the automorphism group of the initial object in any category is the trivial group.
5. A terminal object in a category is an object with the property that there is a unique morphism to it from any object. Prove that the automorphism group of the terminal object in any category is the trivial group.

Measure theory

A left-invariant measure $\mu$ on a group $G$ is a measure with the property that for any $g \in G$, the map $x \mapsto gx$ is a measure-preserving transformation. In other words, for any measurable subset $S$ of $G$, $gS$ is measurable and $\mu(gS) = \mu(S)$.

In the exercises, we shall assume that $G$ is a group with left-invariant measure $\mu$.

1. Prove that if $A$ is a finite or countable subset of $G$, and $B$ is a measurable subset, then $AB$ is measurable, and $\mu(AB) \le |A|\mu(B)$.
2. Prove that it is not necessarily true, for measurable subsets $A,B$ of $G$, that $\mu(AB) \le \mu(A)\mu(B)$.

Combinatorics

Sidon subsets

1. A subset $S$ of an abelian group $G$ is termed a Sidon subset if we cannot find distinct $a,b,c,d \in S$ such that $a + b = c + d$. Prove that if $S$ is a Sidon subset of $G$, and $T$ is a subset of $S$, then $T$ is also a Sidon subset of $G$.
2. Prove that if $H$ is a subgroup of an Abelian group $G$, and $S$ is a Sidon subset of $H$, then $S$ is a Sidon subset of $G$.
3. Prove that any Sidon subset of an abelian group $G$ of order $n$ is contained in a Sidon subset of $G$ of size at least $n^{1/3}$.
4. Prove that if $G$ is an abelian group of order $n$, and $S$ is a Sidon subset of size $m$, then $\binom{m}{2} \le n$. Using this, show that $m \le 1 + 2\sqrt{n}$.
5. For any subset $S$ of an abelian group $G$, define $g + S$ as the set $\{ g + s \mid s \in S \}$ (this is the additive notation equivalent for what we'd call $gS$ in multiplicative notation). Prove that if $S$ is a Sidon subset of $G$, so is $g + S$ for any $g \in G$.
6. A maximal Sidon subset in an abelian group is a Sidon subset that is not properly contained in any bigger Sidon subset. Prove that a maximal Sidon subset of an abelian group cannot be contained in any proper subgroup.

Sidon subsets in other structures

1. NEEDS LOT OF THOUGHT (be careful about non-commutativity while solving this): Call a subset $S$ of a group $G$ (now, not necessarily Abelian) a Sidon subset if we cannot find distinct $a,b,c,d \in S$, such that $ab = cd$. Explore: Is it still true that any Sidon subset of the group of order $n$ is contained in a Sidon subset of size at least $n^{1/3}$? If not, does there exist a modification of $n^{1/3}$ that works? Explore: Is it still true that if $G$ has order $n$, and $S$ is a Sidon subset of size $m$, then $\binom{m}{2} \le n$? If not, does there exist a modification of this that works?
2. (For those who remember quasigroups) Define a Sidon subset in a commutative quasigroup, and prove that the bounds of problems (3) and (4) from the previous section continue to work for commutative quasigroups.

Fibonacci sequences

1. A Fibonacci sequence in an Abelian group $G$ is defined as follows. $f_0$ and $f_1$ are defined as arbitrary elements of $G$, and $f_n$ is defined inductively as $f_{n-1} + f_{n-2}$. Prove that if $G$ is a nontrivial finite Abelian group of order $n$, any Fibonacci sequence in $G$ is periodic, and that the period is at most $n^2 - 1$.
2. The set of sequences in an Abelian group $G$ can itself be viewed as an Abelian group, where the $n^{th}$ term of the sum of two sequences, is defined as the sum of the $n^{th}$ terms. Describe explicitly the identity element, additive inverses, and sums in this group. Prove that the Fibonacci sequences form a subgroup of this group. Find the size of the subgroup comprising Fibonacci sequences for a finite Abelian group $G$ of size $n$

The combinatorics of algebraic structures

Number of structures

(Note: For those familiar with the notion of isomorphism, the problems below do not ask for the number of structures upto isomorphism, rather, they ask for the total number of structures possible).

1. Suppose $S$ is a finite set of cardinality $n$. Find the number of binary operations $S \times S \to S$, i.e., the number of possible magma structures on $S$.
2. Find the number of commutative magma structures on $S$, i.e., find the number of commutative binary operations on $S$.
3. Find the number of commutative unital magma structures on $S$, i.e., find the number of commutative binary operations with a two-sided neutral element.

The combinatorics of associativity

1. Write all the possible ways of parenthesizing the expression $a * b * c * d$ (there are five possible ways). Make a graph where two ways of parenthesization are connected by an edge if we can reach from one to the other by a single application of the associativity law. Prove that the graph obtained is cyclic, i.e., it is a pentagon.
2. Find an expression for the number of ways of parenthesizing the expression $a_1 * a_2 * \dots * a_n$ (this number is often termed a Catalan number).

The combinatorics of quasigroups

1. Prove that if $G$ is a finite commutative quasigroup with an odd number of elements, then every element of $G$ can be uniquely expressed as a square.

Universal algebra

A variety of algebras is described by an operator domain, that specifies a list of $n$-ary operations for varying values of $n$, and a collection of universal identities that these operations need to satisfy. For instance, the variety of groups is described by an operator domain with three operations: the 0-ary operation that yields the identity element, the unary operation for the inverse map, and the binary operation for the multiplication. There are three universal laws these operations must satisfy: associativity, the identity element property, and the inverse property.

1. Prove that if $\mathcal{V}$ is a variety of algebras, $A$ is an algebra in $\mathcal{V}$, and $B$ is a subalgebra of $A$ (in the sense that $B$ is closed under all the operations of $A$), then $B$ is also in $\mathcal{V}$ (you need to argue that all the universal identities true in $A$ continue to be true in $B$).
2. Consider the following variety of algebras. There is only one binary operation $*$, satisfying the following conditions (with all variables universally quantified):
   • $x * x = y * y$
   • $x * (x * x) = x$
   • $((x * x) * ((x * x) * x)) = x$
   • $(x * ((y * y) * y)) * ((z * z) * z) = x * ((y * y) * (y * ((z * z) * z))$.

Prove that any group is a member of this variety of algebras, where $x * y = xy^{-1}$. Conversely, prove that any member of this variety of algebras that is a nonempty set can be given a group structure in a unique way.

1. Add a constant operation to the above variety of algebras to make it correspond precisely with the variety of groups. (Essentially, declare a constant $e$ such that $x * x = e$ for all $x$).

This page is a Interdisciplinary problems page, part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Examples peek two (beginners)| UP: Introduction two | NEXT: Inquiry problems two (beginners)
PREVIOUS SECTION Interdisciplinary problems: Interdisciplinary problems one|NEXT SECTION Interdisciplinary problems: Interdisciplinary problems three
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part