Crate fft_symmetric 

Fast Fourier transforms for symmetric groups over prime fields.

This crate implements the ordinary, semisimple representation-theoretic Fourier transform for S_n over a prime field F_p, with the standing requirement p > n. That condition is deliberate: it ensures char(F_p) does not divide |S_n| = n!, so the group algebra is semisimple and Young’s seminormal representations are valid over the field.

The transform of a function f: S_n -> F_p is the block diagonal family

f_hat(lambda) = sum_{g in S_n} f(g) rho_lambda(g),

one matrix block for each partition lambda of n. The irreducible representations rho_lambda are Young seminormal representations indexed by standard tableaux in last-letter order.

Ordering conventions

Input coefficients are ordered by SymmetricFft::permutations, which is lexicographic order on permutation images. Permutations use zero-based images internally: the identity in S_3 has images [0, 1, 2], and the transposition (1 2) in usual one-based notation has images [1, 0, 2].

Matrix entries are stored row-major. Blocks in a FourierTransform are keyed by Partition.

Example

use fft_symmetric::{Partition, SymmetricFft};

let fft = SymmetricFft::new(3, 101)?;
let values = vec![1; fft.input_len()];
let transform = fft.fft(&values)?;
let recovered = fft.ifft(&transform)?;
assert_eq!(recovered, values);
let product = fft.multiply(&values, &values)?;
assert_eq!(product.len(), fft.input_len());

let mut unit = vec![0; fft.input_len()];
unit[0] = 5;
let inverse = fft.invert(&unit)?;
assert_eq!(fft.multiply(&unit, &inverse)?, {
    let mut identity = vec![0; fft.input_len()];
    identity[0] = 1;
    identity
});

let shape = Partition::new(vec![2, 1])?;
let block = transform.block(&shape).unwrap();
assert_eq!((block.rows(), block.cols()), (2, 2));

Structs

FourierTransform

The Fourier transform of a function on S_n.

Matrix

A dense matrix over a PrimeField.

Partition

An integer partition, used to index irreducible representations of S_n.

Permutation

A permutation of {0, ..., n - 1}.

PrimeField

A runtime prime field F_p.

SymmetricFft

Precomputed plan for Fourier transforms on S_n over F_p.

Tableau

A standard Young tableau.

Enums

FftError

Errors returned by construction, arithmetic helpers, and transforms.

Functions

all_permutations

Returns all permutations of size n in lexicographic image order.

partitions

Returns all integer partitions of n in reverse lexicographic order.

standard_tableaux

Returns all standard Young tableaux of a given shape.