Tour:Interdisciplinary problems four (beginners)

This page is a Interdisciplinary problems page, part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Hard nuts four (beginners)| UP: Introduction four | NEXT: Confidence aggregator four (beginners)
PREVIOUS SECTION Interdisciplinary problems: Interdisciplinary problems three|NEXT SECTION Interdisciplinary problems: Interdisciplinary problems five
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. Moreover, some of these problems build on themes introduced in Tour:Interdisciplinary problems two (beginners) and Tour:Interdisciplinary problems three (beginners), so a review of those problems may be helpful.

Subsets of cyclic groups upto the square root size

1. NEEDS LOT OF THOUGHT: Prove that there exists a quadratic nonresidue mod $p$ represented by a positive integer less than $\sqrt{p} + 1$. (Hint: Look at the smallest quadratic nonresidue.) For full proof, refer: Number:Smallest quadratic nonresidue is less than square root plus one
2. Extend the previous result to prove that there exists a quadratic nonresidue mod $p$ represented by a prime integer less than $\sqrt{p} + 1$.
3. The $n^{th}$ Fermat number, $F_n$, is defined as $F_n := 2^{2^n} + 1$. A Fermat number that is prime is termed a Fermat prime. Prove that any quadratic nonresidue mod a Fermat prime, is a primitive root for it. Using this, prove that for a Fermat prime $F_n$, there exists a primitive root mod $F_n$ between 1 and $2^{2^{n-1}}$.
4. Prove that the multiplicative group mod $p$ is generated by the congruence classes of all primes $q$ less than $\sqrt{p} + 1$ (this is a generalization of the ideas of problems (1) and (2)). For full proof, refer: Number:Multiplicative group of a prime field is generated by all primes less than square root plus one

Quadratic residues and primality testing

Strong pseudoprimes and Rabin-Miller primality testing

Further information: Number:Strong pseudoprime, Number:Rabin-Miller primality test

1. Strong pseudoprime: Consider the following property for numbers $n$ and $a$ if $a^{n-1} \equiv 1 \mod p$, and further, the following holds. if $n - 1 = 2^ks$ where $s$ is odd, then in the sequence $a^s, a^{2s}, a^{2^2s}, \dots, a^{n-1}$, either all the entries are $1$ mod $n$, or the last entry which is not $1$ mod $n$, is -1 mod $n$. Prove that if $n$ is prime, the property holds for all $a$ relatively prime to $n$. A composite number $n$ is termed a strong pseudoprime to base $a$ if it satisfies the above property with $a$.
2. Prove that every strong pseudoprime to base $a$ is also a Fermat pseudoprime to base $a$.
3. For a positive integer $n$, define $H_n$ to be the set of $a$ such that $n$ is a strong pseudoprime to base $a$. Prove that $H_n$ is a subset of the group $G_n$ of all invertible elements mod $n$, under multiplication. Also, prove that $H_n$ contains the identity element and is closed under inverses.
4. NEEDS SOME THOUGHT: Prove that if $n$ is composite, then $H_n$ is a proper subset of the group $G_n$.
5. NEEDS LOT OF THOUGHT: Explore: Can you bound the ratio $\frac{|H_n|}{|G_n|}$ by a number strictly less than 1?

Quadratic residues

Further information: Number:Euler pseudoprime

1. Euler pseudoprime: Prove that if $p$ is an odd prime and $a$ is relatively prime to $p$, then $a^{(p-1)/2} \equiv \pm 1 \mod p$. We say that a composite number $n$ is an Euler pseudoprime to base $a$ if $a^{(n-1)/2} \equiv \pm 1 \mod n$.
2. Prove that a strong pseudoprime is an Euler pseudoprime.

Discrete logarithm

The multiplicative group of integers mod $p$ is a cyclic group of order $p - 1$. A discrete logarithm on this group is an isomorphism from this group to the group of integers mod $p - 1$.

1. Prove that there is a correspondence between primitive roots (generators of the multiplicative cyclic group) mod $p$ and discrete logarithms on the multiplicative group mod $p$. Hence, prove that there are $\varphi(p-1)$ discrete logarithms.
2. Assuming the availability of a discrete logarithm table mod $p$, explain how the problem of solving $a^x \equiv b \mod p$ (where $x$ is the unknown) reduces to solving a linear equation mod $p - 1$.

Combinatorics

Sidon subsets

A subset $S$ of an Abelian group $G$ is termed a Sidon subset if there do not exist four distinct $a,b,c,d \in S$ such that $a + b = c + d$ in $G$.

1. Suppose $a,b,c,d$ are four nonnegative integers. Prove that if $a^2 + b^2 = c^2 + d^2$ and $a + b = c + d$, then $\{ a,b \} = \{ c,d \}$.
2. Let $G$ be the cyclic group of order $4p^2$, for some prime $p$. For any integer $a$, let $\overline{a}$ denote the remainder on dividing $a$ by $p$. Consider the subset $S$ of $G$ given by $\{ 2ap + \overline{a^2} | a \in \{0,1,2,\dots,p-1 \} \}$. Prove that $S$ is a Sidon subset of $G$.
3. Bertrand's postulate states that for any positive integer $n$, there exists a prime $p$ such that $n \le p \le 2n$. Using Bertrand's postulate, prove that the cyclic group of order $n$, for any $n$, has a Sidon subset of size at least $\sqrt{n}/2$.

Fibonacci sequences

The Fibonacci numbers are defined as follows: $f_0 = 0$, $f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n \ge 2$. There is a formula for $f_n$, called Binet's formula:

$f_n = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt{5}}$

where $\varphi = \frac{1 + \sqrt{5}}{2}$. The formula is easily proved by induction.

1. Let $m$ be an odd positive integer. Prove that if there exists an integer $a$ such that $a^2 \equiv 5 \mod m$, then there exists a positive integer $b$ such that $2b = 1 + a$, and:

$f_n \cong \frac{b^n - (1 - b)^n}{a}$

Explore: Can you use this to determine the period of the Fibonacci sequence mod $m$?

The combinatorics of algebraic structures

Up to isomorphism

1. Suppose $S$ is a finite set of cardinality $n$. Consider the binary operations $S \times S \to S$, upto isomorphism. Two binary operations $*,\cdot$ are isomorphism if there is a permutation $\sigma:S \to S$ such that $\sigma(x * y) = \sigma(x) \cdot \sigma(y)$. Prove that the number of binary operations up to equivalence is between $(n^{n^2})/n!$ and $n^{n^2}$.
2. Consider all the possible binary operations on a set of size two. Classify all these binary operations up to isomorphism.

Up to isotopy

Let $(S,*)$ and $(T,\cdot)$ be magmas. An isotopy of magmas from $S$ to $T$ is a triple of bijective maps $\alpha, \beta, ,\gamma$ from $S$ to $T$, such that, for all $x,y \in S$:

$\alpha(x) \cdot \beta(y) = \gamma(x * y)$.

1. Classify all the magmas of size two up to isotopy.
2. Prove that if two groups are isotopic as magmas, they are isomorphic as groups.
3. Prove that any magma isotopic to a quasigroup is a quasigroup.

Universal algebra

Opposite group

Recall the notion of opposite from the interdisciplinary problems of part three.

1. Prove that the inverse map defines an isomorphism between any group and its opposite group. In other words, $g \mapsto g^{-1}$ is an isomorphism from a group to its opposite group.
2. Justify the natural bijection between left and right cosets of a subgroup in light of this isomorphism.

This page is a Interdisciplinary problems page, part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Hard nuts four (beginners)| UP: Introduction four | NEXT: Confidence aggregator four (beginners)
PREVIOUS SECTION Interdisciplinary problems: Interdisciplinary problems three|NEXT SECTION Interdisciplinary problems: Interdisciplinary problems five
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part