Metadata-Version: 2.4
Name: fft-symmetric
Version: 0.1.0
Summary: Fast Fourier transforms for symmetric groups over prime finite fields
Author: Walters Labs
License-Expression: MIT
Project-URL: Repository, https://github.com/walters-labs/fft-symmetric-py
Keywords: fft,symmetric-group,finite-fields,representation-theory
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# 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

```text
S_1 <= S_2 <= ... <= S_n
```

Input coefficients are ordered by lexicographic permutation image order.

```python
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:

```bash
PYTHONPATH=src python3 -m unittest discover -s tests
```

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

```bash
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:

```bash
PYTHONPATH=src python3 -m examples.timing
```

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