Positivity is undecidable in tensor products of free algebras

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