4
$\begingroup$

Suppose I have two lists $\alpha_1,\dots,\alpha_k$ and $\beta_1,\dots,\beta_k$ of real numbers such that all $2k$ numbers are mutually algebraically-independent over the rationals. For each $i \in \{1,\dots,k\}$, let $\phi_k$ be the affine linear map $x \mapsto \alpha_i x + \beta_i$.

Let $I$ be the image of the integers, $\mathbb Z$, under some finite sequence of applications of these maps and/or their inverses. (That is, $I = \phi_{i_\ell}^{e_\ell} \circ \cdots \circ \phi_{i_1}^{e_1} ({\mathbb Z})$ for some $\ell \geq 1$, $e_j \in \{+1,-1\}$, and $i_j \in \{1,\dots,k\}$).

Is the sequence of maps $\phi_{i_1}^{e_1}, \dots, \phi_{i_\ell}^{e_\ell}$ is reconstructible from $I$? (Is there a unique sequence of applications of these maps and inverses such to find $I$ from ${\mathbb Z}$?)

It seems that a formal statement would be that these maps generate a free group within the group of affine linear maps. My intuition is that two distinct ways to generate an element of $I$ with these maps would create an algebraic relation between these algebraically-independent elements, but explicitly building the relation is cumbersome.

$\endgroup$

3 Answers 3

5
$\begingroup$

The sequence of maps $\phi_{i_1}^{e_1},\dots,\phi_{i_{\ell}}^{e_{\ell}}$ is not uniquely determined by the image set $\phi_{i_{\ell}}^{e_{\ell}}\circ\dots\circ\phi_{i_1}^{e_1}(\mathbb{Z})$. One reason for this is that all commutators $\phi_i\phi_j\phi_i^{-1}\phi_j^{-1}$ are translations $x\mapsto x+b$, so any two commutators commute with one another. Thus, for example, $$ \phi_1\phi_2\phi_1^{-1}\phi_2^{-1}\phi_3\phi_4\phi_3^{-1}\phi_4^{-1} = \phi_3\phi_4\phi_3^{-1}\phi_4^{-1}\phi_1\phi_2\phi_1^{-1}\phi_2^{-1}. $$

I would guess that commutativity of commutators is the only source of counterexamples to the proposed question.

$\endgroup$
3
  • 1
    $\begingroup$ Incidentally, while the $\phi_i$ cannot generate a free group when $k>1$, one can probably show that they generate a free semigroup. I would guess that the answer to the original question would be "yes" if one required all the $e_j$ to equal $1$. $\endgroup$ Aug 3, 2013 at 0:21
  • $\begingroup$ Thanks! I'm pretty sure you are right with the free semigroup, which is how I developed the construction (that is, until I realized I needed inverses as well). $\endgroup$ Aug 5, 2013 at 14:11
  • 1
    $\begingroup$ This is correct. The product is a polynomial in the $\alpha_i$ and $\beta_i$, with the coefficient of $\beta_{i_j}$ a degree $j-1$ monomial in the $\alpha_i$. Thus from the polynomial we can determine the sequence $i_j$, so it is injective. $\endgroup$
    – Will Sawin
    Aug 5, 2013 at 14:16
3
$\begingroup$

The group is not free, because it is solvable. The subgroup of maps that are just translations, without scaling, is normal and abelian, with abelian quotient.

$\endgroup$
4
  • $\begingroup$ The way he is defining his group, the subgroup of translations may be trivial. $\endgroup$ Aug 2, 2013 at 20:27
  • $\begingroup$ Even if it were trivial, say if $k=1$, then the group would still be solvable. $\endgroup$
    – Will Sawin
    Aug 3, 2013 at 0:00
  • $\begingroup$ The case k=1 is not important to me. Also, the group of translations are not within this group, since that would require $\alpha_1 = 1$, which is not transcendental over the rationals. $\endgroup$ Aug 5, 2013 at 14:10
  • $\begingroup$ @DerrickStolee: Will Sawin isn't saying that the $\phi_i$ themselves are translations. He's arguing that, if $G$ is the group generated by your finitely many maps $\phi_i:x\mapsto \alpha_i x+\beta_i$, then the map $f\mapsto f'(0)$ defines a group homomorphism $G\to\mathbb{R}^*$. The kernel of this homomorphism consists of the translations in $G$, and hence is abelian. The image of the homomorphism is a subgroup of $\mathbb{R}^*$, so it too is abelian. Thus $G$ is solvable, so if $k>1$ then $G$ is not free. $\endgroup$ Aug 6, 2013 at 21:25
1
$\begingroup$

I am not sure I really understand the question, but: suppose $k=2,$ and our maps are $\phi_1, \phi_2.$ Then the composition of your maps is $\phi: x -> \alpha_1 \alpha_2 x + \alpha_2 \beta_1 + \beta_2.$ Now, it is not too hard to recover the two numbers $\rho = \alpha_1 \alpha_2$ and $\sigma = \alpha_2 \beta_1 + \beta_2$ from the image of the integers under $\phi.$ But now, the set $\alpha_1 \alpha_2 = \rho; \alpha_2 \beta_1 + \beta_2 = \sigma$ is an (affine) two dimensional variety in $\mathbb{R}^4,$ so there will be a point with coordinates $\alpha_1^\prime, \alpha_2^\prime, \beta_1^\prime, \beta_2^\prime$ which are not algebraically related to the original $\alpha_1, \alpha_2, \beta_1, \beta_2,$ so picking $\phi_3, \phi_4$ with the new $\alpha, \beta$ we obtain a counterexample for $k=4.$ Of course, I am not sure what the OP means by "mutually algebraically independent", I would assume that means that for no pair $x_1, x_2$ (where $x$es are one of $\alpha_i, \beta_j$) is there a bivariate polynomial $ \in \mathbb{Z}[x, y]$ which vanishes for $x=x_1, y=x_2.$

More thoughts

In fact, the problem has a number of aspects?

Does knowing the action on $\mathbb{Z}$ imply knowing the action?

In general, of course the answer is NO, since while the "rotational" part of the action can be computed from the action on the integers (the set of differences of values at $\mathbb{Z}$ will be a lattice in $\mathbb{R}$), but the translational part can only be determined up to integer multiple of some magic quantity (that is, transformations $\phi_k=\alpha(z + \beta + k)$ will have the same effect on the integers for all integers $k$). However, with the given set of components, as in the OP's question, being able to get two different $\phi_k$ would imply an algebraic relation. BUT, that relation might be a consequence of the group laws.

Now, suppose we do know the product map. Do we know that there is a unique way to get it? As @MichaelZieve points out, the answer is no, and since we are in an algebraic group, the group laws are the only obstructions.

Finally, is the commutation of commutators the only law in the affine group? Since this is true in any two-step solvable group, this looks a little suspicious.

$\endgroup$
1
  • 1
    $\begingroup$ I'm sure that by "mutually algebraically independent" the OP meant that there is no nonzero $H(x_1,\dots,x_k,y_1,\dots,y_k)\in\mathbb{Z}[x_1,x_2,\dots,x_k,y_1,y_2,\dots,y_k]$ such that $H(\alpha_1,\alpha_2,\dots,\alpha_k,\beta_1,\beta_2,\dots,\beta_k)=0$. That's the standard definition of algebraic independence over $\mathbb{Q}$. $\endgroup$ Aug 3, 2013 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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