B5521 - ARITMETICA E GRUPPI (A-L)

Learning outcomes

At the end of the course, the student will become familiar with notions of set theory, arithmetic and modular arithmetic, and with group theory. The student will be able to apply this knowledge autonomously to prove algebraic statements with a rigorous language.

Course contents

Operations between sets; the power set and Cartesian product, their cardinalities. Relations, equivalence relations; total and partial order relations, their Hasse diagrams. Examples: divisibility and congruence among integers. Equivalence classes, quotient set. Example: Z/n. Partitions of a set, connection with equivalence relations. Injective, surjective, bijective applications; examples; composition of functions and their inverses; "being in bijection" is an equivalence relation between sets. Equivalence relation on the domain of a function and bijection between the associated quotient set and the image of the function.

Peano axioms for natural numbers; principle of induction. Examples of inductive proofs. Integers; construction of rational numbers from integers; brief notes on the construction of real numbers from rationals. Construction of complex numbers, only state the Fundamental Theorem of Algebra; inverse of a complex number. Definition of addition and multiplication on Z/n; these definitions are well-posed; examples. Notion of rings and fields, examples. Applications of congruences. Divisibility criteria for 3, 9, 11; divisibility criteria for 2, 5, 10, and their powers. Writing a number in different bases, divisibility criteria in other bases. Introduction to combinatorics: number of functions and number of injective (or bijective) functions between two finite sets; brief notes on counting surjective functions via inclusion-exclusion principle. Binomial coefficients, their properties (with bijective proofs); their combinatorial interpretations: subsets of a given cardinality, Newton's binomial, partition of a positive integer into non-negative integers, shortest paths on a grid. Number of partitions of a set with n elements: a recursive formula.

Concept of "having the same cardinality" and "having smaller cardinality" between infinite sets. Countable sets; 2N and Z are countable. The union of a countable number of countable sets is countable; the set of rational numbers is countable. The set of binary sequences is not countable. Consequences: the power set of natural numbers is not countable; the set of real numbers is not countable. Every set always has a smaller cardinality than its power set; the Cartesian product of a finite number of countable sets is countable; the set of finite-length words over a finite or countable alphabet is countable.

Prime numbers and irreducible numbers; primes are irreducible. Division with remainder in Z. GCD of two integers and its existence. Euclidean algorithm, Bézout's identity; examples. Diophantine equations. Irreducibles are prime. A class [a] is invertible in Z/n if and only if GCD(a,n)=1; therefore, Z/n is a field if and only if n is prime. Example of computing the inverse. The Fundamental Theorem of Arithmetic. Infinitude of prime numbers. Fermat's Little Theorem; another way to find the inverse of a class in Z/p.

Chinese Remainder Theorem. Euler's totient function and its properties. Euler's theorem. Solving linear congruences; examples. Systems of linear congruences: conditions for solutions; solving via Bézout's identity. Generalization of Fermat's Little Theorem to square-free integers. Introduction to cryptography. The RSA method. Examples.

Definition of a group; commutative and non-commutative groups. Examples and counterexamples of groups with respect to addition, multiplication, composition, set operations. The group of permutations of a set with itself. The group U_n of invertible elements in Z/n; the group GL(V) of automorphisms of a vector space onto itself. Cancellation laws, uniqueness of the neutral element and inverses. Subgroups: examples and properties. Order of an element; examples.

Homomorphisms of groups and their properties. Examples: exponential map from R to R*, and from Z to C_4={i, -1, -i, 1}. Connection with fields, vector spaces, subspaces, linear maps. Kernel and image of a homomorphism, their properties. Group isomorphisms; examples and counterexamples. Being isomorphic is an equivalence relation; the automorphism group Aut(G) of a group. The group R_n of rotations by multiples of 360/n degrees. The K_4 group of symmetries of a rectangle.

The intersection of subgroups is a subgroup. The subgroup generated by a subset; examples of groups generated by n elements and by infinitely many elements. Cyclic groups; their classification. Classification of subgroups of Z and Z/n; order of elements in Z and Z/n. Direct product of groups. The isomorphism in the Chinese Remainder Theorem is a bijection. If f: G→H is a homomorphism, then the order of each g in G divides the order of f(g); if f is an isomorphism, then the order of each g in G is equal to the order of f(g); the converse does not hold; examples. Homomorphisms from a cyclic group to any group.

Dihedral groups: rotations and symmetries. Generators; subgroups; examples. Embedding of the dihedral group into the symmetric group.

Symmetric group. Orbits and cycles of a permutation. Factorization of a permutation into the product of disjoint cycles; notation for elements of the symmetric group. The order of a permutation.

Actions of a group on a set. Examples: actions of the symmetric group S_n on polynomials in n variables and on K^n; actions of the dihedral group D_n on the vertices of a regular n-gon and on the diagonals; actions by left multiplication (or right division) of a group G on itself and on the set of left cosets of a subgroup; conjugation actions of a group G on itself and on its subgroups; actions of R*^2 on R^2 and of R_{>0}^2 on R^2.

Cayley's theorem; examples and consequences.

Every permutation is a product of transpositions. Every transposition is a product of simple transpositions, hence the symmetric group is generated by simple transpositions. Another set of generators for the symmetric group.

Even and odd permutations, theorem: a permutation cannot be both even and odd. Sign of a permutation. Subgroup of even permutations, examples. The sign is the only nontrivial homomorphism from S_n to C*; a subgroup of S_n is either composed entirely of even permutations or is split evenly into even and odd permutations.

Conjugation and its properties (action of G on G by automorphisms); being conjugate is an equivalence relation. Conjugation in the dihedral group. Conjugation in the symmetric group; partitions; two permutations are conjugate if and only if they have the same cycle structure. Conjugacy classes and partitions of a natural number. Example: cyclic structures in S3 and S4, their cardinality, order, and sign.

Left and right cosets of a subgroup, examples. Cosets form a partition, and each has the same cardinality as the subgroup. Index of a subgroup; Lagrange’s theorem; applications: the order of an element divides the order of the group, every group of prime order is cyclic, Euler's theorem. Examples where left and right cosets coincide or not; normal subgroups. Center of a group and its properties.

A subgroup is normal if and only if it is a union of conjugacy classes. The kernel of a homomorphism is a normal subgroup. Compatible relations: correspondence between compatible relations and normal subgroups. If a subgroup is normal, then the set of its conjugates forms a group (called the quotient group), and the projection onto this quotient is a homomorphism. Examples of quotient groups.
Fundamental homomorphism theorem; examples and applications.

Product set of two subgroups of a group and its properties. Direct and semidirect products of groups; properties and examples. Examples of semidirect products that are not isomorphic. Brief notes on group presentations. The unit group of quaternions.

Orbits and stabilizers: definition, properties, examples. Centralizer of an element and normalizer of a subgroup. Stabilizers of elements in the same orbit are conjugate. Bijection between elements of an orbit and the cosets of the stabilizer; orbit formula and class formula; examples. Applications: if a group has order p^n then its center is nontrivial; if a group has order p^2, then it is abelian.

Sylow subgroups, examples: unipotent upper triangular matrices over Z/p.

p-sylow subgroups; examples: the 2-Sylow and 3-Sylow subgroups of the symmetric group S4; upper triangular matrices with 1 on the diagonal are p-Sylow in GL(n, Z/p). Normalizer of a subgroup and its properties. Sylow theorems: p-Sylow subgroups exist, are conjugate to each other, and their number satisfies divisibility and congruence conditions. Corollary: Cauchy's theorem. If there is a unique p-Sylow subgroup, then it is normal.

Applications of Sylow's theorems: the cardinality groups product of two primes; examples: classification of groups of order 15 and order 21. Cauchy's theorem as an application of Sylow's theorem. Groups of rigid motions of space that fix a polyhedron (or a polytope): the group of the cube (and of the hypercube), the group of the tetrahedron (and of the simplex). The correspondence theorem between subgroups that contain a given normal and the subgroups of the quotient (without proof, but with an example). A subgroup of GL(n,K) isomorphic to S_n. The group A1tilde of rigid motions of the real line that send integers to integers. Notes on the groups of tessellations. Notes on the groups of polyhedra and of some molecules.

Readings/Bibliography

Page of the course on the website Virtuale, with lecture notes.

It is also recommended to study the following textbook:

G. M. Piacentini Cattaneo: ALGEBRA, un approccio algoritmico,

Zanichelli

Teaching methods

In-class lessons and exercises. Tutoring. Homework assigned weekly, corrected by tutors and solved on the board by teachers.

Assessment methods

The exam is designed to verify the achievement of the following objectives: in-depth knowledge of the algebra concepts presented during the course; ability to use the tools provided to solve an algebraic problem. The exam consists of a written test and an oral test. To participate in each test, registration for the relevant exam session on the AlmaEsami website is required. Please remember that during the exams, you must show your university badge or other identification document. The written test involves solving exercises and problems and aims to assess the student's ability to apply the theoretical tools provided. During the written test, the use of books or notes, calculators or cell phones is not permitted, and it is not permitted to communicate with other people verbally or via messages of any kind. The written test is graded out of 30 and requires a minimum score of 18/30 to be admitted to the oral test. The results are posted on the AlmaEsami website.
The oral exam aims to verify theoretical knowledge of the subject, language skills and the ability to sustain a discussion on the topics of the course. The final evaluation will take into account the two tests as a whole and the relative verbalization will be carried out at the end of the oral exam. There are six exam sessions during the academic year: two in the winter session January-February, two or three in the summer session June-July, one or two in the autumn session of September. Their exact dates will be available on the AlmaEsami website well in advance.

Teaching tools

Lectures, homework, office hours..

Office hours

See the website of Luca Moci