5
$\begingroup$

Let $n\geq 3$ be a natural number and Consider the following game:

Correspond an integer to each vertices of an equiangular polygon (at least two of the numbers are unequal).

(1) Replace the number of each vertices with the number obtained by the sum of its neighborhood numbers minus its own number. (Edit: Do this for all vertices at once, not one by one)

This gives us a new equiangular polygon with an integer corresponded to each of its vertices.

Again do as in (1) and Continue the progress.

Let $A$ be the set containing the numbers corresponded to vertices of this polygon in this (infinite) process. Now the question is:

what are the possible values of $n$ if we want $A$ to be a bounded set of integers!?

$\endgroup$
12
  • $\begingroup$ Voted up because its a nice problem. But is it a problem for MO?? $\endgroup$
    – user30293
    Commented Jul 27, 2013 at 10:40
  • $\begingroup$ Could you clarify -- is (1) done on a vertex-by-vertex basis or "all vertices at once"? (I assume the latter) $\endgroup$
    – J.J. Green
    Commented Jul 27, 2013 at 11:08
  • $\begingroup$ What role does the equiangularness of the polygon play? Would the question be the same for a cycle of numbers with the same replacement rule? $\endgroup$ Commented Jul 27, 2013 at 11:36
  • $\begingroup$ Why the 'teaching' tag for this question? $\endgroup$ Commented Jul 27, 2013 at 12:46
  • 1
    $\begingroup$ If $n$ is even, an alternating string of plus and minus $1$s becomes an alternating string of plus and minus $3$s, then $9$s, $27$s, etc. (This assumes "neighborhood numbers" means the two adjacent numbers, and also that all vertices are done at once, as J.J. Green commented.) So there's "half" an answer.... $\endgroup$ Commented Jul 27, 2013 at 12:56

1 Answer 1

5
$\begingroup$

For any $n$ there is always a (certainly non-constant) initial choice of integer labels $v=(v_1,\dots,v_n)$ of the vertices of the $n$-gone for which the set of numbers $A$ is unbounded.

The question is more subtle if you ask for which $n$ it is possible to find a non-constant integer choice of labels for which the set of numbers $A$ is bounded. The answer is then: it is possible if and only if $n$ is either a multiple of $4$ or a multiple of $6$. $$ *$$

The iteration you consider is described by a simple symmetric circulant matrix $L$ of order $n$ (in the notation of the link, the non-zero coefficients are $c_0=-1$, $c_1=c_{n-1}=1$). It has therefore $n$ real eigenvalues (repeated according to their multiplicity, which is either $1$ or $2$) $$\lambda_k=2\cos(2\pi k/n) -1,\qquad k=1,\dots, n\ . $$

In particular, the spectral radius of $L$ is larger than $1$, corresponding to $\lambda_{ \lfloor n/2\rfloor} $ . Since $\mathbb{Z}^n$ spans linearly $\mathbb{R}^n$, some element $v$ of $\mathbb{Z}^n$ must have a non-zero component w.r.to $\lambda_{ \lfloor n/2\rfloor} $ in the spectral decomposition, implying that $A=\{L^k v\}_{k\ge0}$ is unbounded. Note that $v$ is certainly not a constant vector, as required. Also note that for even $n$, $\lambda_{n/2}=-3$ corresponds to the example in Barry Cipra's comment.

For what $n$ it is possible to find non-constant integer labels $v=(v_1,\dots,v_n)$ of the vertices for which $A=\{L^k v\}_{k\ge0}$ is bounded? This is certainly the case if $n$ is a multiple of $4$: then we have the eigenvector $(1,0,-1,0,\dots)$ of the eigenvalue $-1$. If $n$ is a multiple of $6$, $L$ is singular with a $2$ dimensional kernel spanned by the $6$-periodic vectors $(1,0,-1,-1,0,1,\dots)$ and $(1,1,-1,-1,1,1,\dots)$. Of course these generate bounded orbits.

Conversely, assume that $n$ is such that there exists a non-constant $v\in \mathbb{Z}^n$ that generates a bounded orbit $\{L^k v\}_k $ . If $L$ is singular, $n$ must be a multiple of $6$, as it follows from the above expression for the eigenvalues. If $L$ is not singular the orbit $\{L^k v\}_k $ is periodic, that is, $L^m v = v$ for some $m$. So $1$ is one of the eigenvalues of $L^m$, which are of the form $\lambda_k^m$, and this is only possible if $\lambda_k=-1$ or $\lambda_k=1$. In the former case, $k=0$ and $v$ is a simple eigenvalue of $L$ with constant coordinates, which is not the case. In the latter case, $\cos(2\pi k/n)=0$, which implies that $n=4k$.

$\endgroup$
4
  • $\begingroup$ If $A$ stays bounded, you'll wind up repeating things, which requires eigenvalues that are roots of unity. Doesn't this pretty much finish things? $\endgroup$ Commented Jul 27, 2013 at 15:52
  • $\begingroup$ Indeed, I was editing to elaborate on this point. So everything reduces to checking when 0, 1, or -1 is an eigenvalue of L. $\endgroup$ Commented Jul 27, 2013 at 18:55
  • $\begingroup$ @Pietro: Please explain two parts: whay "$\Bbb{Z}^n$ spans linearly $\Bbb{R}^n$" ? and in the last paragraph, when $L$ is singular how do you conclude that $6 | n$ ? $\endgroup$
    – user30300
    Commented Jul 28, 2013 at 6:03
  • $\begingroup$ @Sally: The first statement just means that $\mathbb{Z}^n$ is not contained in any proper linear subspace of $\mathbb{Z}^n$ (in particular, it is not contained in the eigenspace of all eigenvalues less than 1 in absolute value). Second statement: $L$ is singular iff $\lambda_k=0$ for some $1\le k \le n$, that is $\cos(2\pi k/n)=1/2$, so $n=6k$ or $5n=6k$. $\endgroup$ Commented Jul 28, 2013 at 7:54

You must log in to answer this question.