Noether

Noether提供了一系列抽象代数结构的特性和泛型实现，从基本的像模糊集（magma）到更复杂的如域（field）。它大量依赖于std::ops和num_traits中提供的基特性。

目录

• 背景
  • 灵感来源
• 特性
• 安装
• 用法
• 核心概念
• 代数结构层次
• 代数结构的运算符特性
• API概述
• 高级用法
• 性能
• 路线图
• 贡献
• 许可协议

背景

以抽象代数先驱艾米·诺特（Emmy Noether）命名，这个库旨在弥合抽象数学与Rust实际编程之间的差距。它允许开发者以类型安全、高效和可表达的方式处理数学概念。

目标是为Rust中的代数结构提供一个通用接口。有趣的是，这些特性可以用来根据它们满足的性质对各种结构的实现进行分类，并应用于从标量值到n维数组等几乎所有情况。

灵感来源

Noether从计算代数领域的几个现有库和项目中汲取灵感

1. simba：一个用于SIMD加速代数的Rust crate。

2. alga：一个用于抽象代数的Rust库，为针对代数应用的抽象提供坚实的数学抽象。alga通过特性继承定义并组织一般代数结构的基本构建块。

3. algebra：一个用于抽象代数的Rust库，将广泛的结构组织到一个逻辑一致的框架中。它旨在基于代数分类创建可组合的库和API。

这些库展示了在编程语言中表现代数结构的力量和实用性。Noether建立在它们的想法之上，旨在为Rust中的代数结构提供全面且易用的框架。

来自不同编程语言的其它有意义的灵感包括

• Haskell的数值预定义和Edward A. Kmett的algebra包
• Agda的代数模块
• Idris的代数模块
• Scala的spire

Noether也从该领域的学术论文中汲取灵感

• 《Scratchpad II类型系统：域和子域》
• 概念增强C++中的基础代数概念

Noether旨在将这些库和研究中的最佳想法带到Rust生态系统，同时利用Rust的独特功能，如零成本抽象和强大的类型系统。

特性

• 广泛的代数结构特性（例如，Magma、半群、幺半群、群、环、域）
• 重要代数属性的标记特性（例如，结合性、交换性）
• 泛型实现以减少样板代码
• 支持内置和自定义类型
• 利用Rust类型系统的零成本抽象

安装

将其添加到您的Cargo.toml

[dependencies]
noether = "0.1.0"

用法

以下是一个使用Noether的Z₅（模5的整数）的示例

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!(),
        }
    }
}

此示例展示了如何使用Noether构建一个良好分解的有限域，利用Rust的本地运算符和特性。

核心概念

1. 代数结构：代表具有特定属性和操作的数学结构的特性。
2. 标记特性：如Associative和Commutative的编译时属性检查特性。
3. 泛型实现：基于更基础的特性的高级特性的自动实现。
4. 零成本抽象：利用Rust的类型系统以效率为代价而无需运行时开销。
5. 可扩展性：该库被设计为易于通过新的类型和结构进行扩展。
6. 类型安全：确保操作保持同一类型内的封闭性并在编译时捕获错误。

代数结构层次

                              ┌─────┐
                              │ 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   │
                  └───────────┘

代数结构的运算符特性

此模块定义了各种运算符及其特性的特性，为在Rust中实现代数结构提供基础。

代数结构由一个集和一个或多个二元运算组成。令$S$为一个集（Self），$\bullet$是$S$上的一个二元运算。以下是一个二元运算可能具有的关键属性，按从简单到复杂的顺序组织

• (封闭性) $\forall a, b \in S, a \bullet b \in S$ - 由提供的运算符保证
• (完备性) $\forall a, b \in S, a \bullet b$被定义 - 由Rust保证
• (交换性) $\forall a, b \in S, a \bullet b = b \bullet a$ - 标记特性
• (结合性) $\forall a, b, c \in S, (a \bullet b) \bullet c = a \bullet (b \bullet c)$ - 标记特性
• (分配性) $\forall a, b, c \in S, a * (b + c) = (a * b) + (a * c)$ - 标记特性

要实现的其他属性

• (幂等性) $\forall a \in S, a \bullet a = a$
• (单位元) $\exists e \in S, \forall a \in S, e \bullet a = a \bullet e = a$
• (逆元) $\forall a \in S, \exists b \in S, a \bullet b = b \bullet a = e$（其中$e$是单位元）
• (消去性) $\forall a, b, c \in S, a \bullet b = a \bullet c \Rightarrow b = c$（如果存在零元素则$a \neq 0$）
• (可除性) $\forall a, b \in S, \exists x \in S, a \bullet x = b$
• (正规性) $\forall a \in S, \exists x \in S, a \bullet x \bullet a = a$
• (交替性) $\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)$
• (吸收性) $\forall a, b \in S, a * (a + b) = a \wedge a + (a * b) = a$
• (单调性) $\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$
• (模性) $\forall a, b, c \in S, a \leq c \Rightarrow a \vee (b \wedge c) = (a \vee b) \wedge c$
• (可交换性) $\forall x, y, z \in S, (x + y) * z = x + (y * z)$
• (最小/最大运算) $\forall a, b \in S, a \vee b = \min{a,b}, a \wedge b = \max{a,b}$
• (缺陷运算) $\forall a, b \in S, a *_3 b = a + b - 3$
• (连续性) $\forall V \subseteq S$ 开放，$f^{-1}(V)$是开放的（对于$f: S \rightarrow S, S$ 拓扑的）
• (可解性) $\exists$ 级数 ${G_i} | G = G_0 \triangleright G_1 \triangleright \ldots \triangleright G_n = {e}, [G_i, G_i] \leq G_{i+1}$
• (算法闭包) 对于所有属于 S[x] 的非常数 p(x)，存在一个 a 属于 S，使得 p(a) = 0

提供的特性和通用实现服务了几个重要目的

1. 闭包：所有 Closed* 特性确保对类型的操作总是产生相同类型的结果。这对于定义代数结构至关重要。

2. 引用操作：当右侧可以借用时，特质的 *Ref 变体允许进行更高效的运算，这在许多算法中很常见。

3. 标记特性：如 Commutative、Associative 等特性允许类型声明它们满足哪些代数属性。这可以用于编译时检查和启用算法的更通用实现。

4. 可扩展性：实现标准特性（如 Add、Sub 等）的新类型将自动获得封闭特性实现，使系统更具可扩展性和前瞻性。

5. 类型安全：这些特性有助于在编译时捕获类型相关的错误，确保操作保持同一类型内的封闭性。

6. 泛型编程：这些特性使泛型编程更具表现力，允许函数和结构体针对满足某些运算或代数属性的类型进行泛化。

API概述

Noether 提供了各种代数结构的特性，包括

• Magma：具有二元运算的集合
• Semigroup：结合律的 magma
• Monoid：具有单位元素的半群
• Group：每个元素都有逆元的半群
• Ring：具有两个运算（加法和乘法）并满足某些公理的集合
• Field：每个非零元素都有乘法逆元的交换环
• VectorSpace：具有域上的标量乘法的阿贝尔群
• Module：类似于向量空间，但乘法运算在环上而不是在域上
• Polynomial：表示域上的多项式
• FieldExtension：表示域扩展

每个特性都包含定义相应代数结构运算和属性的方法。有关特性和其方法的完整列表，请参阅API 文档。

高级用法

Noether 的强大之处在于其能够以泛型方式表达复杂的数学概念和算法。以下是一个与实现 Field 特性的任何类型一起工作的函数示例

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

您可以使用此函数与任何实现 Field 特性的类型一起使用，无论是内置数字类型还是类似我们之前示例中的 Z5 的自定义类型。

性能

Noether 考虑到性能，利用 Rust 的零成本抽象。基于特质的泛型多态允许在具体类型上使用时生成有效的单态代码。

然而，与任何抽象库一样，请注意，大量使用动态分派（例如，通过特质对象）可能会产生一些运行时成本。在大多数情况下，编译器可以优化掉抽象，从而实现与手动实现相当的性能。

路线图

Noether 的未来计划包括

• 实现更高级的代数结构（例如，格，布尔代数）
• 添加对无限域及其运算的支持
• 实现域上的多项式运算的算法
• 添加对符号计算的支撑
• 实现根查找和方程求解的数值方法
• 增强文档，添加更多示例和教程
• 优化常见运算的性能
• 添加一个全面的测试套件，包括属性测试
• 探索Rust生态系统与其他数学库的集成

贡献

欢迎贡献！请随时在我们的GitHub仓库提交问题、功能请求或拉取请求。

许可协议

本项目采用MIT许可证 - 有关详细信息，请参阅LICENSE文件。

我们希望Noether将成为密码学家、数学家、科学家和Rust中处理代数结构的开发人员的有价值工具。如果您有任何问题、建议或反馈，请随时在我们的GitHub仓库上提出问题或联系维护者。

用Noether快乐编码！