Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider $\mathbb{Z}^{n}$ for $n = 2^r$ where $r \geq 1$ . Look at the iterates of the following function $T$ from $\mathbb{Z}^n$ to itself. $T((a_1, a_2, \ldots, a_n)) = (|a_1 - a_n|, |a_2 - a_1|, |a_3 - a_2|, \ldots, |a_n - a_{n-1}|)$.

It has been proved that when $n = 2^{r}$, then for every $(a_1, a_2, \ldots, a_n) \in \mathbb{Z}^n - \{0\}$, there exists some $i \geq 1$, such that $T^{i}((a_1, a_2, \ldots, a_n)) = 0.$ This does not hold for other values of $n$. Note that, if $T^{i}((a_1, a_2, \ldots, a_n)) = 0$, then $T^{j}((a_1, a_2, \ldots, a_n)) = 0$ for all $j > i.$

Findings so far are the following.

(i) $T(k(a_1, a_2, \ldots, a_n)) = k T((a_1, a_2, \ldots, a_n))$ for all $k \in \mathbb{Z}$.

(ii) $T(k + (a_1, a_2, \ldots, a_n)) = T((a_1, a_2, \ldots, a_n))$ for all $k \in \mathbb{Z}$, where $k + (a_1, a_2, \ldots, a_n) = (k + a_1, k + a_2, \ldots, k + a_n).$

(iii) Let, $S_{i} = \{(a_1, a_2, \ldots, a_n) \in Z^{n} : T^{i}((a_1, a_2, \ldots, a_n)) = 0 \text{ and } T^{i-1}((a_1, a_2, \ldots, a_n)) \neq 0\}$ for $i \geq 1$. Note that $S_i$ s are disjoint also their union is equal to $\mathbb{Z}^n$.

The questions that I have are the following.

(i) What's the maximum value of $i$ such that $S_{i}$ is not empty? Putting it in other words, what's the maximum number of times the function T needs to be applied to a vector so that it gets mapped to $0$ vector.

(ii) Since the function $T$ is homogeneous, notions from projective space can be borrowed. How could projective geometry be applied here?

share|improve this question
    
Is $Z$ the ring of integers? What do the bars in expressions like $|a_1-a_n|$ mean? –  Mariano Suárez-Alvarez Sep 29 '10 at 8:44
    
They mean absolute values. –  debapriyay Sep 29 '10 at 8:46
    
I understand the absolute value only if $Z$ is the integers. Further question: Furthermore I do not understand the definition of $T$. What is $a$ here? Which ``earlier paper'' are you referring to? –  Sebastian Petersen Sep 29 '10 at 8:52
    
Yes $Z$ is the set of integers. Each $a_{j} \in Z$ for all $j = 1,2, \ldots, n.$ The earlier paper, I referred is the following. A number-theoretic game Prithvi Ramesh Published in Resonance, January 2003, P.84-88 –  debapriyay Sep 29 '10 at 9:11
4  
btw, I'm not sure if the linear-algebra and algebraic-geometry tags fit here. –  Martin Brandenburg Sep 29 '10 at 9:25

2 Answers 2

The answer is infinity for $n>2$.

Suppose that there is an $i$ such that $T^i(x)=0$ for all integer vectors $x$. Then the same follows for all rational vectors by homogenuity, and then for all real vectors by approximation.

But there is a real vector that never reaches zero. For example, for $n=4$ consider $$ (a^3,a^2,a,1) $$ where $a>1$ satisfies $a^3=a^2+a+1$. The next iteration is $$ (a^3-1,a^3-a^2,a^2-a,a-1) = (a-1)\cdot (a^2+a+1, a^2, a, 1) = (a-1)\cdot (a^3, a^2, a, 1) . $$ Note that it is proportional to the original vector. By induction it follows that the $n$th iteration equals $(a-1)^n$ times the original vector, hence it never becomes zero.

An obvious modification of this example works for every $n>2$.

share|improve this answer
    
I don't think for any $a \in Z$, and for $a > 1$, the relation $a^{3} = a^{2} + a + 1$ holds. Can you provide a real example in support of your claim. –  debapriyay Oct 18 '10 at 12:08
    
Surely $a$ is irrational. The example is a rational approximation of $(a^3,a^2,a,1)$ multiplied by a common denominator (to make integers from rationals). For each particular approximation, the procedure ends up at zero eventually. But the number of steps needed for that grows infinitely as approximations gets closer to the limit vector $(a^3,a^2,a,1)$. Because this vector never reaches zero as the above calculation shows. –  Sergei Ivanov Oct 18 '10 at 21:11

This is not an answer though. I am trying still to solve the problem. I would like to get comments on the approach that I am following. The approach in nutshell is described below. I am trying to characterize the sets $S_{i}$. Note that, any $a \in S_{1}$ can be derived from the single vector $(1, 1, \ldots, 1)$, by doing either $k + (1, 1, \ldots, 1)$ or $k (1, 1, \ldots, 1).$

Similarly, any $a \in S_{2}$ can be derived from any of the following vectors by applying $k + <the vector>$ and $k.<the vector>$. The vectors are (i) $(0, 1, 0, 1, \ldots, 0, 1)$, (ii) $(1, 0, 1, 0, \ldots, 1, 0)$ and all the vectors that can be formed from the vector $(1, 0, 1, 2, 1, 0, 1, 2, \ldots, 1, 0, 1, 2)$ by shifting the elements of the vectors by one position in the right.

This can be verified. Can we now iterate in some way this to come to a value of $i$ such that no such vectors can be formed and then we stop. $i-1$ then is the answer.

Is it a viable approach? Or am I missing something?

share|improve this answer

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.