A Polynomial Time Algorithm for Calculating Fourier-Dedekind Sums

Guoce Xin, Xinyu XuExp. Math 2025 · DOI

TL;DR

This paper introduces a novel polynomial-time algorithm for computing Fourier-Dedekind sums, a class of number-theoretic objects with applications in various fields. By leveraging modular Barvinok's simplicial cone decomposition and a constant term concept, the authors provide an efficient and practical solution to an open problem in the field.

What Problem Does This Paper Address?

Dedekind sums and their generalizations, Fourier-Dedekind sums, are fundamental in number theory, geometry, and algorithmic complexity. While it was known that these sums are efficiently computable, a fast and practical algorithm for their calculation remained an open problem, as highlighted in the book "Computing the Continuous Discretely" by Beck and Robins. This paper directly addresses this challenge by proposing such an algorithm.

Methods

The core of the paper's contribution lies in developing a polynomial-time algorithm for computing Fourier-Dedekind sums. The approach is built upon two key ideas:

  • Constant Term Concept: The authors utilize a concept related to extracting constant terms from rational functions, as described in prior work. This involves defining a "CT" (Constant Term) operator.
  • Modular Barvinok's Simplicial Cone Decomposition: The algorithm leverages a simplified version of Barvinok's algorithm, which is known for its polynomial-time complexity in fixed dimensions. This technique is applied to decompose the problem into manageable parts.

The paper also details how this algorithm can be readily adapted to existing software packages like LattE, facilitating its practical implementation. The methodology involves expressing the Fourier-Dedekind sum as a constant term of a specific rational function and then applying the decomposition technique.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and theoretical results, with an appendix showcasing computational experiments.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper successfully translates a theoretical understanding of Fourier-Dedekind sums into a practical, efficient algorithm, solving a long-standing open problem.
  • Elegance of Barvinok's Algorithm: The work demonstrates the power and adaptability of Barvinok's algorithm for problems beyond its original scope, showcasing its utility in number-theoretic computations.
  • Unification through Fourier-Dedekind Sums: The paper implicitly highlights the importance of Fourier-Dedekind sums as unifying entities for various Dedekind sum variations and as building blocks for more complex structures like Ehrhart quasipolynomials.
  • Software Integration: The ease with which the proposed algorithm can be integrated into existing computational tools like LattE is a significant practical insight, promoting wider adoption and application.

Key Results

The primary result is the development of a polynomial-time algorithm for calculating Fourier-Dedekind sums. While the paper doesn't present extensive quantitative benchmarks in the main text, the appendix provides computational experiments demonstrating the algorithm's performance. These experiments, using a custom implementation called LLLCTEuclid, show that the algorithm can compute these sums efficiently, with execution times measured in seconds even for complex cases. For instance, example computations on pages 5-8 showcase the algorithm's ability to handle inputs with multiple parameters and produce results.

Limitations and Future Work

The paper is presented as a draft announcement, with a complete version to be finished later. The authors acknowledge that the appendix's computational experiment section is using an algorithm still under construction. Future work would likely involve a more thorough analysis of the algorithm's complexity bounds and a comprehensive comparison with existing methods on a wider range of benchmarks. The paper also suggests that the algorithm can be easily adapted into the LattE package, implying that further development could focus on optimizing this integration.

Summary updated

BibTeX
@article{xin2025polynomial,
  author = {Guoce Xin and Xinyu Xu},
  title = {{A Polynomial Time Algorithm for Calculating Fourier-Dedekind Sums}},
  journal = {Exp. Math.},
  year = {2025},
  doi = {10.1080/10586458.2024.2364264},
}
Figure