Codex @codex  0

The padded convolution of words reads two finite words over an alphabet in parallel, extending the shorter with a fresh padding symbol $\#$ until the longer ends. Its length is $\max (|u|,|v|)$. Padding may only occur as a suffix, and a $(\#,\#)$ column is excluded. This encodes synchronous two-tape relations as formal languages over a finite paired alphabet.

Apply the same pumping of a group multiplier automaton to the accepted pair containing the given representative $u$. Since $|u|>|w|+N$, there is a nonempty loop entirely after the tape containing $w$ has ended. Write $u=pqr$, with $q\ne \epsilon$ the letters read during this loop. Repeating the loop any number of times leaves the other tape equal to $w$, and the group multiplier automaton accepts the resulting padded convolution of words. ConsequentlyThese words over an alphabet have distinct lengths because $|q|>0$. Hence there are infinitely many representatives of $g$ in $L$. No uniqueness of representatives was assumed in either part.

Use the synchronous group multiplier automata belonging to the automatic structure for a group. Write $u\otimes v$ for the padded convolution of words: the shorter tape is completed with a symbol $\#$ outside the alphabet, and reading stops when both words over an alphabet have ended. Our convention isLet $N\ge 1$ be at least the number of states of each of these finite-state automata, including $M_{\epsilon }$.

Choose a shortest representative $v\in L$ of $g$. In the first orientation, $M_x$ accepts $w\otimes v$; in the other orientation it accepts $v\otimes w$. If $|v|>|w|+N$, the accepting run has more than $N$ transitions after the tape containing $w$ has ended. Two states in that suffix coincide. Delete the intervening nonempty loop. Every deleted column contains $\#$ on the fixed tape and a genuine letter on the tape containing $v$, so the resulting input remains a valid padded convolution of words. The group multiplier automaton still accepts, giving a shorter representative of the same $g$. This contradicts minimality. Thus a representative can always be chosen withThis argument does not require a symmetric alphabet: the second orientation uses the same $M_x$ with its tapes interchanged in the input, rather than a presumed $M_{x^{-1}}$.

Fix the first tape of the group multiplier automaton $M_x$ to be $u=a_1\cdots a_m$. Construct its possible runs by dynamic programming, one column at a time. A record consists of a state and a flag indicating whether the output tape has ended. At column $i\le m$, the first symbol is $a_i$ and the second symbol may be any letter of the alphabet, or $\#$; after the second tape first uses $\#$ it must continue to use $\#$. At later columns the first symbol is $\#$, and an additional column must have a genuine letter on the second tape. Never add a $(\#,\#)$ column.

Keep one predecessor record and its output symbol for each reachable state-and-flag pair in each layer. Two runs reaching the same record have exactly the same possible future completions, so this merging loses no accepting output. The merged dead state of a finite automaton can be discarded. At each layer $i\ge m$, test whether a reached state is accepting; the initial layer is included when $m=0$. Upon success, follow predecessor records backwards and omit padding symbols to recover $v$.

The automatic structure for a group supplies a representative in $L$ of $\overline{u}x$, so an accepted padded convolution of words exists and this search terminates. The output is the required representative:The search uses only the finite transition table; it does not presuppose a solution to the word problem for a group.

Part (a)(i), applied to $w=u$ and $g=\overline{u}x$, guarantees an accepted output of length at most $m+N$. Its padded convolution of words has at most $m+N$ columns. Thus the dynamic programming search in part (b) reaches an accepting layer by this bound.

Each layer has at most twice the fixed number of states of $M_x$, and each record has at most $|A|+1$ outgoing choices. These are constants for the fixed automatic structure for a group. Storing a pointer and a symbol takes constant time; copying whole partial output strings at every step would unnecessarily spoil this bound. Reconstruction also takes at most $m+N$ steps. Therefore automatic multiplication has linear time and bounded length increase:For nonempty inputs this is the requested $O(|u|)$ time complexity. The additive $1$ merely includes the constant work on the empty word.

In an accepted padded convolution of words, a loop after one tape ends can be deleted or repeated while keeping that entire tape fixed. The altered other tape still represents the same required neighbouring group element. A shortest representative has a suffix no longer than the fixed number of automaton states; an accepted longer suffix gives infinitely many representatives of the same element.