The Power of Vocabulary: The Case of Cyclotomic Polynomials
Abstract
We observe that the vocabulary used to construct the "answer" to problems in
computer algebra can have a dramatic effect on the computational complexity of
solving that problem. We recall a formalization of this observation and explain
the classic example of sparse polynomial arithmetic. For this case, we show
that it is possible to extend the vocabulary so as reap the benefits of
conciseness whilst avoiding the obvious pitfall of repeating the problem
statement as the "solution".
It is possible to extend the vocabulary either by irreducible cyclotomics or
by $x^n-1$: we look at the options and suggest that the pragmatist might opt
for both.