fta

Fundamental Theorem of Arithmetic as a coordinate system.

Every positive integer has a unique prime factorization. fta treats that factorization as a coordinate system — each prime is an axis, each exponent is a coordinate. Under this embedding, divisibility becomes geometry.

The central object is Lattice(n): the complete divisibility structure of an integer. Give it a number; get back every way it can be cleanly subdivided and how those subdivisions relate to each other.

No assumptions about what the integers represent. The domain sits entirely outside this package.

Install

pip install fta

Usage

from fta import Lattice

L = Lattice(12)

L.members()          # (1, 2, 3, 4, 6, 12)    — all divisors
L.covers(3)          # (6,)                    — immediate parent in Hasse diagram
L.covered_by(6)      # (2, 3)                  — immediate children
L.hasse_edges()      # all (child, parent) pairs
L.meet(4, 6)         # 2                       — gcd
L.join(4, 6)         # 12                      — lcm
L.divides(3, 6)      # True
L.depth(4)           # 2                       — steps from bottom (1)
L.height(4)          # 1                       — steps to top (n)
L.members_lte(6)     # (1, 2, 3, 6)            — downward closure
L.members_gte(3)     # (3, 6, 12)              — upward closure
L.primes()           # (2, 3)                  — prime axes
L.coordinate(12)     # {2: 2, 3: 1}            — prime exponent vector

Standalone utilities:

from fta import factorize, smallest_divisor_gte

factorize(360)                  # {2: 3, 3: 2, 5: 1}
smallest_divisor_gte(3600, 250) # 300 — smallest divisor of 3600 that is >= 250

Applications

Lattice(n) is useful anywhere you need to know how an integer can be hierarchically subdivided. The arithmetic is the same across all of these — only the interpretation of the integers changes.

Signal processing — Given a time horizon (e.g. 86400 seconds = one day) and a finest meaningful unit (e.g. 60 seconds = one minute), Lattice(86400) gives every valid measurement window and how they relate. The divisibility structure ensures windows at different scales are arithmetically coherent with each other.

Database partitioning — Choosing partition sizes that divide cleanly into each other avoids remainder handling and uneven splits. Lattice(n) for your table size gives every valid partition size and the hierarchy between them.

Compiler / loop tiling — A CPU cache line is 64 bytes, an AVX register is 256 bits, a memory page is 4096 bytes. Valid tile sizes must divide the working set size cleanly. Lattice(n).members() enumerates all valid tile sizes; covers() gives the next level up in the memory hierarchy.

Music / tuning theory — Just intonation intervals are ratios of small integers. The divisibility lattice of a frequency denominator gives all harmonically related intervals and their relationships.

Scheduling — Valid sub-period sizes for a time period (e.g. tasks that fit evenly into a one-hour window). members() gives every valid granularity; covers() gives the next coarser level.

Mathematical background

Under the prime exponent coordinate embedding:

The Hasse diagram of the divisibility lattice is the graph where m2 covers m1 iff m2/m1 is prime — one step along a single prime axis.

License

MIT