Skip to main content

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)

Source distribution for fft-symmetric 0.2.0
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)

Table of built distributions (wheels) for fft-symmetric 0.2.0
File Interpreter ABI Platform Actions
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.

Release history Release notifications | RSS feed

This release

0.2.0 This release

2 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page