A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences

Abstract

In this paper, which may be considered a sequel to a recent article by Eric Rowland and Reem Yassawi, we present yet another approach for the automatic generation of automata (and an extension that we call congruence linear schemes) for the fast (log-time) determination of congruence properties, modulo small (and not so small!) prime powers, for a wide class of combinatorial sequences. Even more interesting than the new results that could be obtained is the illustrated methodology, that of designing ‘meta-algorithms’ that enable the computer to develop algorithms, that it (or another computer) can then proceed to use to actually prove (potentially!) infinitely many new results. This paper is accompanied by a Maple package, AutoSquared, and numerous sample input and output files, that readers can use as templates for generating their own, thereby proving many new ‘theorems’ about congruence properties of many famous (and, of course, obscure) combinatorial sequences.

Keywords::

• sequences modulo m
• constant term
• finite automaton
• automatic sequence

Acknowledgements

The second author (DZ) was supported in part by a grant from the National Science Foundation of the USA. The authors thank Shalosh B. Ekhad for its many diligent and tedious computations and proofs!

Notes

^1. Email: [email protected]