ECCC-Report TR11-088https://eccc.weizmann.ac.il/report/2011/088Comments and Revisions published for TR11-088en-usTue, 07 Jun 2011 18:27:02 +0300
Paper TR11-088
| How much commutativity is needed to prove polynomial identities? |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2011/088Let $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 $n$ is the number of variables of $f$. We show that there exists a polynomial $f$ with $Q(f)=\Omega(n^2)$. We pose the problem of constructing such an $f$ explicitly, pointing out that the solution may have applications to complexity of proofs. Tue, 07 Jun 2011 18:27:02 +0300https://eccc.weizmann.ac.il/report/2011/088