FLINT3.7.0-dev
/

fmpq_dedekind_sum, fmpq_dedekind_sum_naive

Synopsis#include <flint/fmpq.h>
void fmpq_dedekind_sum(fmpq_t s, const fmpz_t h, const fmpz_t k)source
void fmpq_dedekind_sum_naive(fmpq_t s, const fmpz_t h, const fmpz_t k)source

Set ss to s(h,k)s(h, k), for any integers hh and kk. The naive version evaluates the defining sum with kk terms. fmpq_dedekind_sum uses the continued fraction of k/hk/h and costs about as much as an extended GCD.

By the reciprocity law s(h,k)+s(k,h)=(h/k+k/h+1/(hk))/12−1/4s(h,k) + s(k,h) = (h/k + k/h + 1/(hk))/12 - 1/4 for coprime h,k>0h, k > 0, the sum telescopes along the Euclidean algorithm [Hickerson1977]. With the partial quotients a1,…,ana_1, \ldots, a_n of k/(h mod k)k/(h \bmod k), the convergent matrix ∏i(ai110)=(m11m12m21m22)\prod_i \left(\begin{smallmatrix} a_i & 1 \\ 1 & 0 \end{smallmatrix}\right) = \left(\begin{smallmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{smallmatrix}\right) and the alternating sum t=a1−a2+⋯±ant = a_1 - a_2 + \cdots \pm a_n,

12 s(h,k)=t+m21−(−1)nm12m11−3⋅[n odd].12\, s(h, k) = t + \frac{m_{21} - (-1)^{n} m_{12}}{m_{11}} - 3 \cdot [n \text{ odd}].

The function evaluates this in machine words when kk fits in a slong and with the half-GCD continued fraction code otherwise. Writing s(h,k)=p/qs(h,k) = p/q in lowest terms, ∣s∣<k/12|s| < k/12 and q∣6kq \mid 6k.

References#

  • [Hickerson1977] D. Hickerson, "Continued fractions and density results for Dedekind sums", Journal für die reine und angewandte Mathematik 290 (1977), 113–116.
Cite this page

The FLINT team, “fmpq_dedekind_sum, fmpq_dedekind_sum_naive (fmpq.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpq/fmpq_dedekind_sum.html (generated 2026-11-02).