Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NON-COMMUTATIVE POLYNOMIAL:
Reports tagged with non-commutative polynomial:
TR11-088 | 7th June 2011
Pavel Hrubes

How much commutativity is needed to prove polynomial identities?

Let f be a non-commutative polynomial such that f=0 if we assume that the variables in f commute. Let Q(f) be the smallest k such that there exist polynomials g_1,g_1', g_2, g_2',\dots, g_k, g_k' with

f\in I([g_1,g_1'], [g_2, g_2'],\dots, [g_k, g_k'] )\,,

where [g,h]=gh-hg. Then Q(f)\leq {n\choose 2}, where ... more >>>




ISSN 1433-8092 | Imprint