# free group generated by polynomials

Someone recently asked me how to proof that $x+1$ and $x^3$ generate a free group. A colleague has worked out a proof. I have a vague memory that this has been studied, maybe a Monthly problem? Does anyone know any history on this?

Edit: Sorry for my omission of key point. The group operation here is function composition on the reals, or the integers. Each of the polynomials can be viewed as a permutation of Z = all integers (or on the reals). Viewed in that way, do they generate a free group (of rank two).

-
If your group operation is addition, hopefully it's easy to see that $a(x+1) + b(x^3)$ is never the zero polynomial unless $a=b=0$, so the map $\mathbb{Z}^2 \to (\mathrm{your\,group})$ given by $(a, b)\mapsto a(x+1) + b(x^3)$ is an isomorphism. If you mean under multiplication, then replace $a(x+1) + b(x^3)$ with $(x+1)^a(x^3)^b$ in what I said, and the same still holds. Am I missing something? –  Billy Dec 16 '12 at 16:04
(Oh - perhaps you mean as functions $\mathbb{R}\to \mathbb{R}$ or something, rather than polynomials? That sounds less easy!) –  Billy Dec 16 '12 at 16:06
Minor nitpickery: $x\to f(x)=x^3$ is hardly a permutation on $\mathbb{Z}$, and it certainly doesn't have an inverse on that domain (what is $f^{-1}(2)$?). Either you need to be working over $\mathbb{R}$ or you're considering the free monoid, which is a different matter entirely. –  Steven Stadnicki Mar 28 '13 at 17:54

This is a question asked by Harvey Friedman (I don't know where and when) and which was first solved by Samuel White in 1988, The group generated by $x \mapsto x + 1$ and $x \mapsto x^p$ is free, Journal of Algebra, Volume 118, Issue 2, 1 November 1988, Pages 408–422.

There's an earlier incomplete solution by Zassenhaus in On a problem by Harvey Friedman Communications in Algebra, Volume 6, Issue 16, 1978.

You can find further references in item II.40 of de la Harpe's book Topics in Geometric Group theory.

-
Here's a link to the relevant section of de la Harpe's book which I was not allowed to include in the answer: books.google.com/books?id=cRT01C5ADroC&pg=PA37 –  Martin Dec 16 '12 at 16:27
And here are the two further references given by de la Harpe: dx.doi.org/10.1112/S002461079600436X and dx.doi.org/10.1112/jlms/s2-43.2.255 –  Martin Dec 16 '12 at 16:31
Thanks to all for the quick and complete answers! –  stan wagon Dec 16 '12 at 16:39
@stan wagon: Gerald Edgar makes some comments here. It might be the case that the problem is in Friedman's list One Hundred and Two Problems in Mathematical Logic, but I currently don't have access to check it myself. –  Martin Dec 19 '12 at 21:59

Not sure about a free group, but a free semigroup is easy to prove. Suppose that we had $$g_1 \circ g_2 \circ \cdots \circ g_m(x) = h_1 \circ h_2 \circ \cdots \circ h_n(x)$$ where each $g_i$ and $h_i$ is either $x \mapsto x+1$ or $x \mapsto x^3$. Since both generators are invertible (as maps $\mathbb{R} \to \mathbb{R}$), we may assume that $g_1 \neq h_1$. Say $g_1$ is $x \mapsto x^3$, that $h_1$, $h_2$, ..., $h_k$ are $x \mapsto x+1$ and $h_{k+1}$ is $x \mapsto x^3$. (If all the $h$'s are $x \mapsto x+1$ then we have $p(x)^3 = x+k$, clearly wrong.)

So, instead, we have $p(x)^3 = q(x)^3+k$. Now look up your favorite proof of Fermat's Last Theorem for polynomials. Here are the first two I found: 1 2.

-