Problem 977: Dedekind Sum Computation

Mathematical Foundation

Definition 1 (Sawtooth Function). The periodic sawtooth function $((x)) : \mathbb{R} \to \mathbb{R}$ is defined by:

Lemma 1 (Odd Symmetry). For all $x \in \mathbb{R}$, $((-x)) = -((x))$.

Proof. If $x \in \mathbb{Z}$, then $-x \in \mathbb{Z}$, so $((-x)) = 0 = -((x))$. If $x \notin \mathbb{Z}$, write $x = n + \theta$ with $n \in \mathbb{Z}$ and $0 < \theta < 1$. Then $-x = -(n+1) + (1-\theta)$, so $\lfloor -x \rfloor = -(n+1)$ and:

Theorem 1 (Dedekind Reciprocity Law). For coprime positive integers $h, k$:

Proof. (Sketch via the Rademacher—Grosswald approach.) Consider the function $f(z) = \cot(\pi z)\cot(\pi hz/k)$ and integrate around a rectangle with vertices at $\pm iR$ and $k \pm iR$. The residues at $z = r/k$ ($r = 0, 1, \ldots, k-1$, avoiding integer multiples of $k/h$ if any) contribute terms involving $s(h,k)$, while the contour deformation and a symmetric treatment in $h$ and $k$ yield the reciprocity formula. Full details are in Rademacher & Grosswald, Dedekind Sums (1972), Chapter 2. $\square$

Theorem 2 (Antisymmetry of the Sum over Reduced Residues). For all $k \ge 2$:

Proof. We show that the map $h \mapsto k - h$ is an involution on $\{h : 1 \le h \le k-1, \gcd(h,k)=1\}$ that negates $s(h,k)$.

First, $\gcd(k-h, k) = \gcd(h,k) = 1$, and $1 \le k-h \le k-1$, so the map is a well-defined involution on the reduced residue system.

Now we show $s(k-h, k) = -s(h,k)$. We have:

Since $(k-h)r/k = r - hr/k$, and $r \in \mathbb{Z}$, we get:

by Lemma 1 (noting that $hr/k \in \mathbb{Z}$ iff $k \mid hr$ iff $k \mid r$ since $\gcd(h,k)=1$, which does not occur for $1 \le r \le k-1$).

Therefore:

Summing over all $h$ with $\gcd(h,k)=1$, the involution $h \leftrightarrow k-h$ pairs terms that cancel:

Theorem 3 (Main Result). $\displaystyle\sum_{k=2}^{100}\sum_{\substack{h=1 \\ \gcd(h,k)=1}}^{k-1} 12k \cdot s(h,k) = 0.$

Proof. By Theorem 2, the inner sum $\sum_h s(h,k) = 0$ for each $k \ge 2$. Multiplying by the constant $12k$ preserves this:

Summing over $k = 2, \ldots, 100$ gives $0$. $\square$

Editorial

Compute the weighted sum of Dedekind sums: S = sum over k=2..100, h=1..k-1 with gcd(h,k)=1 of 12ks(h,k) where s(h,k) = sum_{r=1}^{k-1} ((r/k)) * ((hr/k)) and ((x)) is the sawtooth function: x - floor(x) - 1/2 for non-integer x, 0 otherwise. Key insight: s(h,k) + s(k-h,k) = 0 for all valid h,k with gcd(h,k)=1. Since pairing h with k-h covers all coprime residues, the total sum is 0. We by Theorem 3, the answer is 0. Finally, iterate over verification, one may compute directly.

Pseudocode

By Theorem 3, the answer is 0
For verification, one may compute directly:

Complexity Analysis

• Time: $O(1)$ using the theoretical result (Theorem 3). For direct verification: $O(N^4)$ where $N = 100$ (three nested loops of size $O(N)$ each, with the GCD check).
• Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;
// By symmetry s(h,k) + s(k-h,k) = 0 for all coprime h,k
// so sum over all coprime h of 12k*s(h,k) = 0 for each k
int main() { cout << 0 << endl;     return 0;
}

"""
Problem 977: Dedekind Sum Computation

Compute the weighted sum of Dedekind sums:
    S = sum over k=2..100, h=1..k-1 with gcd(h,k)=1 of 12*k*s(h,k)

where s(h,k) = sum_{r=1}^{k-1} ((r/k)) * ((hr/k))
and ((x)) is the sawtooth function: x - floor(x) - 1/2 for non-integer x, 0 otherwise.

Key insight: s(h,k) + s(k-h,k) = 0 for all valid h,k with gcd(h,k)=1.
Since pairing h with k-h covers all coprime residues, the total sum is 0.

Answer: 0

Methods:
    - sawtooth(x): Sawtooth function ((x)) using exact Fraction arithmetic
    - dedekind_sum(h, k): Direct computation of s(h,k)
    - dedekind_reciprocity_check(h, k): Verify reciprocity law
    - verify_pairing_symmetry(k_max): Verify s(h,k) = -s(k-h,k) for small k
"""

from math import gcd
from fractions import Fraction


def sawtooth(x):
    """((x)) = x - floor(x) - 1/2 for non-integer x, 0 for integer x."""
    if x == int(x):
        return Fraction(0)
    return x - int(x) - Fraction(1, 2)

def dedekind_sum(h, k):
    """Compute s(h,k) = sum_{r=1}^{k-1} ((r/k)) * ((hr/k))."""
    s = Fraction(0)
    for r in range(1, k):
        s += sawtooth(Fraction(r, k)) * sawtooth(Fraction(h * r, k))
    return s


def dedekind_reciprocity_check(h, k):
    """
    Verify the Dedekind reciprocity law:
    s(h,k) + s(k,h) = (h/k + k/h + 1/(hk))/12 - 1/4
    for gcd(h,k) = 1.
    """
    lhs = dedekind_sum(h, k) + dedekind_sum(k, h)
    rhs = (Fraction(h, k) + Fraction(k, h) + Fraction(1, h * k)) / 12 - Fraction(1, 4)
    return lhs == rhs


def verify_pairing_symmetry(k_max=30):
    """Verify that s(h,k) + s(k-h,k) = 0 for all coprime h < k."""
    for k in range(2, k_max + 1):
        for h in range(1, k):
            if gcd(h, k) == 1:
                s1 = dedekind_sum(h, k)
                s2 = dedekind_sum(k - h, k)
                assert s1 + s2 == 0, f"Symmetry failed for h={h}, k={k}"
    return True

# Verification

# Known small values
assert dedekind_sum(1, 2) == Fraction(0)
assert dedekind_sum(1, 3) == Fraction(1, 18)
assert dedekind_sum(1, 5) == Fraction(1, 5)

# Reciprocity check
assert dedekind_reciprocity_check(1, 5)
assert dedekind_reciprocity_check(2, 7)
assert dedekind_reciprocity_check(3, 11)

# Pairing symmetry
verify_pairing_symmetry(20)

# By the pairing argument s(h,k) = -s(k-h,k), the full sum is 0
answer = 0
print(answer)