Noether

Noether provides traits and blanket implementations for algebraic structures, from basic ones like magmas to more complex ones like fields. It leans heavily on the basic traits available in std::ops and num_traits.

Table of Contents

• Background
  • Inspirations
• Features
• Installation
• Usage
• Core Concepts
• Hierarchy of Algebraic Structures
• Operator Traits for Algebraic Structures
• API Overview
• Advanced Usage
• Performance
• Roadmap
• Contributing
• License

Background

Named after Emmy Noether, a pioneering mathematician in abstract algebra, this library aims to bridge the gap between abstract mathematics and practical programming in Rust. It enables developers to work with mathematical concepts in a type-safe, efficient, and expressive manner.

The goal is to provide a common interface for working with algebraic structures in Rust. Interestingly, these traits can be used to categorize implementations of various structs based on the properties they satisfy, and be applied in most cases for anything from scalar values to n-dimensional arrays.

Inspirations

Noether draws inspiration from several existing libraries and projects in the field of computational algebra:

1. simba: A Rust crate for SIMD-accelerated algebra.

2. alga: A Rust library for abstract algebra, providing solid mathematical abstractions for algebra-focused applications. alga defines and organizes basic building blocks of general algebraic structures through trait inheritance.

3. algebra: A Rust library for abstract algebra that organizes a wide range of structures into a logically consistent framework. It aims to create composable libraries and APIs based on algebraic classifications.

These libraries demonstrate the power and utility of representing algebraic structures in programming languages. Noether builds upon their ideas, aiming to provide a comprehensive and ergonomic framework for working with algebraic structures in Rust.

Other notable inspirations from different programming languages include:

• Haskell's Numeric Prelude and Edward A. Kmett's algebra package
• Agda's algebra module
• Idris' algebra module
• Scala's spire

Noether also draws insights from academic papers in the field:

• The Scratchpad II Type System: Domains and Subdomains
• Fundamental Algebraic Concepts in Concept-Enabled C++

Noether aims to bring the best ideas from these libraries and research to the Rust ecosystem, while taking advantage of Rust's unique features like zero-cost abstractions and powerful type system.

Features

• Traits for a wide range of algebraic structures (e.g., Magma, Semigroup, Monoid, Group, Ring, Field)
• Marker traits for important algebraic properties (e.g., Associativity, Commutativity)
• Blanket implementations to reduce boilerplate code
• Support for both built-in and custom types
• Zero-cost abstractions leveraging Rust's type system

Installation

Add this to your Cargo.toml:

[dependencies]
noether = "0.1.0"

Usage

Here is a rough example of Z₅ (integers modulo 5) using Noether:

use noether::{Field};
use std::ops::{Add, Sub, Mul, Div, Neg};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Z5(u8);

impl Z5 {
    fn new(n: u8) -> Self {
        Z5(n % 5)
    }
}

impl Add for Z5 {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Z5((self.0 + rhs.0) % 5)
    }
}

impl Sub for Z5 {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        self + (-rhs)
    }
}

impl Mul for Z5 {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        Z5((self.0 * rhs.0) % 5)
    }
}

impl Div for Z5 {
    type Output = Self;
    fn div(self, rhs: Self) -> Self {
        if rhs.0 == 0 {
            panic!("Division by zero in Z5");
        }
        self * rhs.multiplicative_inverse().unwrap()
    }
}

impl Neg for Z5 {
    type Output = Self;
    fn neg(self) -> Self {
        Z5((5 - self.0) % 5)
    }
}

impl Field for Z5 {
    fn multiplicative_inverse(&self) -> Option<Self> {
        match self.0 {
            0 => None,
            1 | 4 => Some(*self),
            2 => Some(Z5(3)),
            3 => Some(Z5(2)),
            _ => unreachable!(),
        }
    }
}

This example shows how to construct a well factored finite field using Noether, leveraging Rust's native operators and traits.

Core Concepts

1. Algebraic Structures: Traits representing mathematical structures with specific properties and operations.
2. Marker Traits: Traits like Associative and Commutative for compile-time property checks.
3. Blanket Implementations: Automatic implementations of higher-level traits based on more fundamental ones.
4. Zero-Cost Abstractions: Leveraging Rust's type system for efficiency without runtime overhead.
5. Extensibility: The library is designed to be easily extended with new types and structures.
6. Type Safety: Ensuring operations maintain closure within the same type and catching errors at compile-time.

Hierarchy of Algebraic Structures

                              ┌─────┐
                              │ Set │
                              └──┬──┘
                                 │
                              ┌──▼──┐
                              │Magma│
                              └──┬──┘
               ┌────────────────┼────────────────┐
               │                │                │
         ┌─────▼─────┐    ┌─────▼─────┐    ┌─────▼─────┐
         │Quasigroup │    │ Semigroup │    │Semilattice│
         └─────┬─────┘    └─────┬─────┘    └───────────┘
               │                │
           ┌───▼───┐        ┌───▼───┐
           │ Loop  │        │Monoid │
           └───┬───┘        └───┬───┘
               │                │
               └────────┐ ┌─────┘
                        │ │
                     ┌──▼─▼──┐
                     │ Group │
                     └───┬───┘
                         │
                ┌────────▼────────┐
                │  Abelian Group  │
                └────────┬────────┘
                         │
                    ┌────▼────┐
                    │Semiring │
                    └────┬────┘
                         │
                    ┌────▼────┐
                    │  Ring   │
                    └────┬────┘
          ┌───────────────────────┐
          │                       │
    ┌─────▼─────┐           ┌─────▼─────┐
    │  Module   │           │Commutative│
    └───────────┘           │   Ring    │
                            └─────┬─────┘
                                  │
                         ┌────────▼────────┐
                         │ Integral Domain │
                         └────────┬────────┘
                                  │
                    ┌─────────────▼─────────────┐
                    │Unique Factorization Domain│
                    └─────────────┬─────────────┘
                                  │
                      ┌───────────▼───────────┐
                      │Principal Ideal Domain │
                      └───────────┬───────────┘
                                  │
                         ┌────────▼────────┐
                         │Euclidean Domain │
                         └────────┬────────┘
                                  │
                              ┌───▼───┐
                              │ Field │────────────────────────┐
                              └───┬───┘                        │
                        ┌─────────┴──────────┐                 │
                        │                    │                 │
                  ┌─────▼─────┐        ┌─────▼─────┐     ┌─────▼─────┐
                  │   Finite  │        │ Infinite  │     │  Vector   │
                  │   Field   │        │   Field   │     │   Space   │
                  └─────┬─────┘        └───────────┘     └───────────┘
                        │
                  ┌─────▼─────┐
                  │   Field   │
                  │ Extension │
                  └─────┬─────┘
                        │
                  ┌─────▼─────┐
                  │ Extension │
                  │   Tower   │
                  └───────────┘

Operator Traits for Algebraic Structures

This module defines traits for various operators and their properties, providing a foundation for implementing algebraic structures in Rust.

An algebraic structure consists of a set with one or more binary operations. Let $S$ be a set (Self) and $\bullet$ be a binary operation on $S$. Here are the key properties a binary operation may possess, organized from simplest to most complex:

• (Closure) $\forall a, b \in S, a \bullet b \in S$ - Guaranteed by the operators provided
• (Totality) $\forall a, b \in S, a \bullet b$ is defined - Guaranteed by Rust
• (Commutativity) $\forall a, b \in S, a \bullet b = b \bullet a$ - Marker trait
• (Associativity) $\forall a, b, c \in S, (a \bullet b) \bullet c = a \bullet (b \bullet c)$ - Marker trait
• (Distributivity) $\forall a, b, c \in S, a * (b + c) = (a * b) + (a * c)$ - Marker trait

Additional properties to be implemented:

• (Idempotence) $\forall a \in S, a \bullet a = a$
• (Identity) $\exists e \in S, \forall a \in S, e \bullet a = a \bullet e = a$
• (Inverses) $\forall a \in S, \exists b \in S, a \bullet b = b \bullet a = e$ (where $e$ is the identity)
• (Cancellation) $\forall a, b, c \in S, a \bullet b = a \bullet c \Rightarrow b = c$ ($a \neq 0$ if $\exists$ zero element)
• (Divisibility) $\forall a, b \in S, \exists x \in S, a \bullet x = b$
• (Regularity) $\forall a \in S, \exists x \in S, a \bullet x \bullet a = a$
• (Alternativity) $\forall a, b \in S, (a \bullet a) \bullet b = a \bullet (a \bullet b) \wedge (b \bullet a) \bullet a = b \bullet (a \bullet a)$
• (Absorption) $\forall a, b \in S, a * (a + b) = a \wedge a + (a * b) = a$
• (Monotonicity) $\forall a, b, c \in S, a \leq b \Rightarrow a \bullet c \leq b \bullet c \wedge c \bullet a \leq c \bullet b$
• (Modularity) $\forall a, b, c \in S, a \leq c \Rightarrow a \vee (b \wedge c) = (a \vee b) \wedge c$
• (Switchability) $\forall x, y, z \in S, (x + y) * z = x + (y * z)$
• (Min/Max Ops) $\forall a, b \in S, a \vee b = \min{a,b}, a \wedge b = \max{a,b}$
• (Defect Op) $\forall a, b \in S, a *_3 b = a + b - 3$
• (Continuity) $\forall V \subseteq S$ open, $f^{-1}(V)$ is open (for $f: S \rightarrow S, S$ topological)
• (Solvability) $\exists$ series ${G_i} | G = G_0 \triangleright G_1 \triangleright \ldots \triangleright G_n = {e}, [G_i, G_i] \leq G_{i+1}$
• (Alg. Closure) $\forall p(x) \in S[x]$ non-constant, $\exists a \in S | p(a) = 0$

The traits and blanket implementations provided serve several important purposes:

1. Closure: All Closed* traits ensure that operations on a type always produce a result of the same type. This is crucial for defining algebraic structures.

2. Reference Operations: The *Ref variants of traits allow for more efficient operations when the right-hand side can be borrowed, which is common in many algorithms.

3. Marker Traits: Traits like Commutative, Associative, etc., allow types to declare which algebraic properties they satisfy. This can be used for compile-time checks and to enable more generic implementations of algorithms.

4. Extensibility: New types that implement the standard traits (like Add, Sub, etc.) will automatically get the closed trait implementations, making the system more extensible and future-proof.

5. Type Safety: These traits help in catching type-related errors at compile-time, ensuring that operations maintain closure within the same type.

6. Generic Programming: These traits enable more expressive generic programming, allowing functions and structs to be generic over types that are closed under certain operations or satisfy certain algebraic properties.

API Overview

Noether provides traits for various algebraic structures, including:

• Magma: Set with a binary operation
• Semigroup: Associative magma
• Monoid: Semigroup with identity element
• Group: Monoid where every element has an inverse
• Ring: Set with two operations (addition and multiplication) satisfying certain axioms
• Field: Commutative ring where every non-zero element has a multiplicative inverse
• VectorSpace: An abelian group with scalar multiplication over a field
• Module: Similar to a vector space, but over a ring instead of a field
• Polynomial: Represents polynomials over a field
• FieldExtension: Represents field extensions

Each trait comes with methods defining the operations and properties of the respective algebraic structure. For a complete list of traits and their methods, please refer to the API documentation.

Advanced Usage

Noether's power lies in its ability to express complex mathematical concepts and algorithms generically. Here's an example of a function that works with any type implementing the Field trait:

use noether::Field;

fn polynomial_evaluation<F: Field>(coefficients: &[F], x: F) -> F {
    coefficients.iter().rev().fold(F::zero(), |acc, &c| acc * x + c)
}

// This function works for any type implementing the Field trait

You can use this function with any type that implements the Field trait, whether it's a built-in numeric type or a custom type like our Z5 from the earlier example.

Performance

Noether is designed with performance in mind, leveraging Rust's zero-cost abstractions. The use of trait-based polymorphism allows for efficient, monomorphized code when used with concrete types.

However, as with any abstract library, be aware that extensive use of dynamic dispatch (e.g., through trait objects) may incur some runtime cost. In most cases, the compiler can optimize away the abstractions, resulting in performance equivalent to hand-written implementations.

Roadmap

Future plans for Noether include:

• Implementing more advanced algebraic structures (e.g., Lattices, Boolean Algebras)
• Adding support for infinite fields and their operations
• Implementing algorithms for polynomial operations over fields
• Adding support for symbolic computation
• Implementing numerical methods for root finding and equation solving
• Enhancing documentation with more examples and tutorials
• Optimizing performance for common operations
• Adding a comprehensive test suite, including property-based tests
• Exploring integration with other mathematical libraries in the Rust ecosystem

Contributing

Contributions are welcome! Please feel free to submit issues, feature requests, or pull requests on the GitHub repository.

License

This project is licensed under the MIT License - see the LICENSE file for details.

We hope that Noether will be a valuable tool for cryptographers, mathematicians, scientists, and developers working with algebraic structures in Rust. If you have any questions, suggestions, or feedback, please don't hesitate to open an issue on our GitHub repository or contact the maintainers.

Happy coding with Noether!