Skip to content

Latest commit

 

History

History
87 lines (56 loc) · 2.56 KB

README.md

File metadata and controls

87 lines (56 loc) · 2.56 KB

Subgroups of ℤ/nℤ × ℤ/nℤ

Project proposed by Olivier Brunat

This project explores the problem of describing the subgroups of the group ℤ/nℤ × ℤ/nℤ, which poses a challenging question in finite abelian group theory. While the subgroups of a cyclic group are easy to describe, determining the subgroups of a product like ℤ/nℤ × ℤ/nℤ is much more complex.

Theoretical Overview

We will explore:

  • Lattices in ℤᵐ and integer matrices.
  • Subgroups of ℤᵐ generated by the column vectors of integer matrices.
  • Hermite and Smith normal forms of integer matrices, which have applications beyond this project, including cryptography.

Additionally, we will explore the finite group theory approach via Goursat’s lemma and compare both approaches.

Practical Implementation

The project includes the development of algorithms to:

  • Compute the Hermite and Smith normal forms of an integer matrix.
  • Generate the subgroup lattice of ℤ/nℤ × ℤ/nℤ for a given integer n.

Requirements

  • OCaml and related tools (e.g., opam, dune for managing OCaml projects).
  • Ensure you have installed necessary libraries via opam:
opam install dune

Setup

  1. Clone the repository:
git clone https://github.com/napoknot21/subgroups.git
cd subgroups
  1. Build the project using the Makefile:
make
  1. Run the program:
./run.sh <n>

Replace <n> with the integer value for n to generate the lattice of subgroups for ℤ/nℤ × ℤ/nℤ.

Example Usage

For n = 12, you would run:

./run.sh 12

This will output the lattice of subgroups of ℤ/12ℤ × ℤ/12ℤ.

File Structure

  • bin/: Contains compiled binaries.
  • lib/: Source code for algorithms.
  • test/: Test cases and example inputs.
  • rapport/: Contains the final project report with theoretical background and algorithm analysis.
  • soutenance/: Presentation materials for the project defense.

Output

The output will display:

  • Hermite and Smith normal forms of the input matrix.
  • The lattice of subgroups for ℤ/nℤ × ℤ/nℤ.

Contribution Guidelines

Feel free to fork this repository and submit pull requests. Ensure that all contributions are well-documented and include relevant test cases.

Final Report

The final deliverable includes:

  • A report detailing the mathematical theory and the algorithms implemented.
  • Discussion of the challenges encountered and a comparison of the two approaches, including a performance analysis.