fft-symmetric 0.2.0

Fast Fourier transforms for symmetric groups over prime finite fields

fft-symmetric-py

FFT (fast Fourier transform) of the symmetric group over finite fields in Python.

This package implements the semisimple case: for S_n over F_p, the constructor enforces p > n. Fourier blocks use Young's seminormal representations and the subgroup chain

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

Input coefficients are ordered by lexicographic permutation image order.

from fft_symmetric import SymmetricFFT

fft = SymmetricFFT(4, 101)
values = [1] * fft.input_len

transform = fft.fft(values)
recovered = fft.ifft(transform)
assert recovered == values

identity = [1] + [0] * (fft.input_len - 1)

product = fft.multiply(values, values)
assert len(product) == fft.input_len

inverse = fft.invert(identity)
assert fft.multiply(identity, inverse) == identity

for shape, block in transform.blocks.items():
    print(shape, block.rows, block.cols)

The package also exposes naive_dft and naive_multiply as small-rank correctness or timing baselines.

Group Algebra Inversion

For the semisimple case p > n, the Fourier transform decomposes F_p[S_n] into matrix blocks indexed by partitions of n. Multiplication is blockwise:

widehat(fg)_lambda = widehat(f)_lambda widehat(g)_lambda

So a group-algebra element is invertible exactly when every Fourier block is an invertible matrix, and inversion is:

widehat(f^{-1})_lambda = widehat(f)_lambda^{-1}

Use SymmetricFFT.invert(values) for coefficient-space inversion, or SymmetricFFT.invert_transform(transform) if you already have the Fourier blocks and want to avoid recomputing the transform.

Run tests with:

PYTHONPATH=src python3 -m unittest discover -s tests

Run the opt-in timing-sensitive multiplication test with:

PYTHONPATH=src FFT_SYMMETRIC_RUN_TIMING=1 python3 -m unittest \
    tests.test_core.CoreTests.test_multiplication_is_faster_than_naive

Run the timing example with:

PYTHONPATH=src python3 -m examples.timing

Set FFT_SYMMETRIC_TIMING_MAX_N=7 or higher if you want a longer run.