@inproceedings{ChDu20,
  author = {Chyzak, Frédéric and Dumas, Philippe},
  title = {A {G}röbner-basis theory for divide-and-conquer recurrences},
  booktitle = {ISSAC'20},
  year = {2020},
  editor = {Leykin, Anton},
  pages = {99--106},
  publisher = {ACM Press},
  abstract = {Divide-and-conquer recurrences relate values of a given sequence at indices of the form $b^\ell n + r$ for fixed~$b\geq2$ and various pairs~$(\ell,r)$. Using systems of such recurrences makes it possible to express the behaviour of a quantity according to congruence classes modulo~$b^\ell$. The study of such systems is poorly developed so far. In particular, no consistency check is available and no theory of initial values has been developed yet. In an ongoing study in order to fill this gap, we have introduced a noncommutative multivariate polynomial setting to represent divide-and-conquer systems. This setting involves at the same time variables that behave like words in purely noncommutative algebras and variables governed by commutation rules like in skew polynomial extensions. In the present work, we initiate the study of left ideals of such polynomials and we develop their Gröbner-basis theory, including the usual division and Buchberger algorithms. Strikingly, the nature of commutations generally prevents the leading monomial of a polynomial product to be the product of the leading monomials. To overcome the difficulty, we consider a specific monomial ordering, together with a restriction to monic divisors in intermediate steps. We also develop a variant of the $F_4$ algorithm with distinguishing features.},
  doi = {10.1145/3373207.3404055}
}