fft-symmetric

Fast Fourier transforms for symmetric groups over prime finite fields, implemented in Rust.

Installation

Add the crate to your project from crates.io:

cargo add fft-symmetric

API documentation is available on docs.rs, and source code and issue tracking are available in the GitHub repository.

This crate currently implements the semisimple case: for S_n over F_p, the constructor enforces p > n. The transform uses Young's seminormal representations and the subgroup chain

S_1 <= S_2 <= ... <= S_n

with coefficients ordered by lexicographic permutation order.

use fft_symmetric::SymmetricFft;

let fft = SymmetricFft::new(4, 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)?;
let mut identity = vec![0; fft.input_len()];
identity[0] = 1;
assert_eq!(fft.multiply(&unit, &inverse)?, identity);

for (shape, block) in transform.blocks() {
    println!("{shape}: {}x{}", block.rows(), block.cols());
}
# Ok::<(), Box<dyn std::error::Error>>(())

The library also exposes naive_dft as a small-rank correctness oracle. For group algebra products, use multiply; naive_multiply is available as a direct-convolution baseline. For units, use invert; it applies the FFT, inverts each Young block over the prime field, and applies the inverse FFT.