Positivity is undecidable in tensor products of free algebras

Abstract

It is well known that an element of the algebra of noncommutative $\ast$-polynomials is positive in all $\ast$-representations if and only if it is a sum of squares. This provides an effective way to determine if a given $\ast$-polynomial is positive, by searching through sums of squares decompositions. We show that no such procedure exists for the tensor product of two noncommutative $\ast$-polynomial algebras: determining whether a $\ast$-polynomial of such an algebra is positive is coRE-hard. We also show that it is coRE-hard to determine whether a noncommutative $\ast$-polynomial is trace-positive. Our results hold if noncommutative $\ast$-polynomial algebras are replaced by other sufficiently free algebras such as group algebras of free groups or free products of cyclic groups.