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.
Contents
Subsets of cyclic groups upto the square root size
- NEEDS LOT OF THOUGHT: Prove that there exists a quadratic nonresidue mod represented by a positive integer less than . (Hint: Look at the smallest quadratic nonresidue.) For full proof, refer: Number:Smallest quadratic nonresidue is less than square root plus one
- Extend the previous result to prove that there exists a quadratic nonresidue mod represented by a prime integer less than .
- The Fermat number, , is defined as . 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 , there exists a primitive root mod between 1 and .
- Prove that the multiplicative group mod is generated by the congruence classes of all primes less than (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
- Strong pseudoprime: Consider the following property for numbers and if , and further, the following holds. if where is odd, then in the sequence , either all the entries are mod , or the last entry which is not mod , is -1 mod . Prove that if is prime, the property holds for all relatively prime to . A composite number is termed a strong pseudoprime to base if it satisfies the above property with .
- Prove that every strong pseudoprime to base is also a Fermat pseudoprime to base .
- For a positive integer , define to be the set of such that is a strong pseudoprime to base . Prove that is a subset of the group of all invertible elements mod , under multiplication. Also, prove that contains the identity element and is closed under inverses.
- NEEDS SOME THOUGHT: Prove that if is composite, then is a proper subset of the group .
- NEEDS LOT OF THOUGHT: Explore: Can you bound the ratio by a number strictly less than 1?
Quadratic residues
Further information: Number:Euler pseudoprime
- Euler pseudoprime: Prove that if is an odd prime and is relatively prime to , then . We say that a composite number is an Euler pseudoprime to base if .
- Prove that a strong pseudoprime is an Euler pseudoprime.
Discrete logarithm
The multiplicative group of integers mod is a cyclic group of order . A discrete logarithm on this group is an isomorphism from this group to the group of integers mod .
- Prove that there is a correspondence between primitive roots (generators of the multiplicative cyclic group) mod and discrete logarithms on the multiplicative group mod . Hence, prove that there are discrete logarithms.
- Assuming the availability of a discrete logarithm table mod , explain how the problem of solving (where is the unknown) reduces to solving a linear equation mod .
Combinatorics
Sidon subsets
A subset of an Abelian group is termed a Sidon subset if there do not exist four distinct such that in .
- Suppose are four nonnegative integers. Prove that if and , then .
- Let be the cyclic group of order , for some prime . For any integer , let denote the remainder on dividing by . Consider the subset of given by . Prove that is a Sidon subset of .
- Bertrand's postulate states that for any positive integer , there exists a prime such that . Using Bertrand's postulate, prove that the cyclic group of order , for any , has a Sidon subset of size at least .
Fibonacci sequences
The Fibonacci numbers are defined as follows: , , and for . There is a formula for , called Binet's formula:
where . The formula is easily proved by induction.
- Let be an odd positive integer. Prove that if there exists an integer such that , then there exists a positive integer such that , and:
Explore: Can you use this to determine the period of the Fibonacci sequence mod ?
The combinatorics of algebraic structures
Up to isomorphism
- Suppose is a finite set of cardinality . Consider the binary operations , upto isomorphism. Two binary operations are isomorphism if there is a permutation such that . Prove that the number of binary operations up to equivalence is between and .
- Consider all the possible binary operations on a set of size two. Classify all these binary operations up to isomorphism.
Up to isotopy
Let and be magmas. An isotopy of magmas from to is a triple of bijective maps from to , such that, for all :
.
- Classify all the magmas of size two up to isotopy.
- Prove that if two groups are isotopic as magmas, they are isomorphic as groups.
- 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.
- Prove that the inverse map defines an isomorphism between any group and its opposite group. In other words, is an isomorphism from a group to its opposite group.
- 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