Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers 2

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.