Linear-time multiplication in an automatic structure Created 2026-10-06 Updated 2026-10-14
Fix the first tape of a group multiplier automaton and use dynamic programming over automaton states and output-padding status, retaining predecessor pointers. The pumping of a group multiplier automaton bounds the search by layers, each of fixed size. This constructs a representative of in time without assuming uniqueness of representatives.
Apply the same pumping of a group multiplier automaton to the accepted pair containing the given representative . Since , there is a nonempty loop entirely after the tape containing has ended. Write , with the letters read during this loop. Repeating the loop any number of times leaves the other tape equal to , and the group multiplier automaton accepts the resulting padded convolution of words. Consequently
These words over an alphabet have distinct lengths because . Hence there are infinitely many representatives of in . No uniqueness of representatives was assumed in either part.