fft-symmetric 0.1.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

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

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.

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.