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.
Metadata
Release files for fft-symmetric 0.2.0
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| fft_symmetric-0.2.0.tar.gz | 13.4 kB | Without provenance | Details for fft_symmetric-0.2.0.tar.gz |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| fft_symmetric-0.2.0-py3-none-any.whl | Python 3 | none | any | Details for fft_symmetric-0.2.0-py3-none-any.whl |
Total release size: 24.1 kB
Release files / fft_symmetric-0.2.0.tar.gz
| Download URL | fft_symmetric-0.2.0.tar.gz |
|---|---|
| Size | 13.4 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
d0ed17454b04f47d2dd90c2f7226fbb4a4693814cdd4a9de2b6073d184ef5cdf
|
|
BLAKE2b-256 checksum How to use checksums |
0e8fdcd92a66df14a642bbf10f8f17a50e7be365a3ad966297a63fe880832565
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.2.0 CPython/3.14.2
|
Release files / fft_symmetric-0.2.0-py3-none-any.whl
| Download URL | fft_symmetric-0.2.0-py3-none-any.whl |
|---|---|
| Size | 10.8 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
00415f8f1115e7a615996d5440a2a2c18139d460119483f0c5606d9aabdf9e09
|
|
BLAKE2b-256 checksum How to use checksums |
ceda9a52cf9c808a3960cb8bd57e853a73e608a8bde6238f3104b6821011c55a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.2.0 CPython/3.14.2
|
Security for fft-symmetric 0.2.0
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.