5
$\begingroup$

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).

  • 0
    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.2013-03-28

2 Answers 2

6

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.

  • 0
    @stan wagon: Gerald Edgar makes some comments [here](http://mathoverflow.net/questions/19218/). It might be the case that the problem is in Friedman's list [One Hundred and Two Problems in Mathematical Logic](http://www.jstor.org/stable/2271891), but I currently don't have access to check it myself.2012-12-19
1

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.