quasipoly-ogf

Utilities to convert quasi-polynomial sequences into ordinary generating functions (OGFs). Given one polynomial per residue class, the library builds the rational generating function, returns a reduced form, and rewrites it using a minimal power denominator (1 - x^d)^k.

Features

• Accept quasi-polynomials with symbolic rational coefficients (SymPy compatible).
• Returns both a fully reduced rational form and a minimal power-denominator form.
• Includes helper utilities for forward differences and cyclotomic analysis.
• Tested with Python's standard unittest.

Installation

pip install -e .

Requirements: Python >= 3.10 and sympy>=1.12.

Input format

A quasi-polynomial of period m is provided as a list polys of length m. polys[r] is the coefficient list of the polynomial used when n ≡ r (mod m), with coefficients in ascending powers of n:

# p_r(n) = c0 + c1*n + c2*n**2
polys = [
    [c0, c1, c2],  # residue 0
    ...
]

Usage

from quasipoly_ogf import quasi_polynomial_ogf

# Example: period 2, p_0(n) = n, p_1(n) = n + 1
polys = [[0, 1], [1, 1]]
result = quasi_polynomial_ogf(polys)

print("Reduced form:", result.expr_reduced)
print("Power denominator form:", result.expr_power)
print("(d, k) =", (result.d, result.k))

Outputs

quasi_polynomial_ogf returns an OGFResult with:

• expr_reduced = P(x)/Q(x) where P and Q are coprime.
• expr_power = R(x)/(1 - x**d)**k with minimal (d, k).
• The intermediate numerators/denominators are provided in num_*, den_*.

Mathematical notes

For each residue class r, the partial generating function has the form A_r(x) = x**r * G_r(x**m), where G_r is obtained from the forward difference expansion of p_r(m*k + r) in the binomial basis. Summing all residues yields a rational expression whose denominator divides (1 - x**m)**(D+1) where D is the maximum degree among p_r.

The power-denominator rewrite factors the reduced denominator into cyclotomic polynomials. Let Q(x) = Π Φ_n(x)^{e_n}. The minimal (d, k) is: d = lcm{ n : e_n > 0 } and k = max e_n. The numerator is multiplied by the missing cyclotomic factors so that the denominator becomes (1 - x**d)**k.

Limitations

• Denominators must factor into cyclotomic polynomials; otherwise a ValueError is raised by to_power_denom.
• Coefficients should be exact (integers, rationals, or SymPy rationals) to avoid floating-point artifacts.

Running tests

python -m unittest -q