Exploding cyclic differences

You have $n > 1$  numbers $a_1, a_2, \dots, a_n$.

At each step, you replace $$a_1, a_2, \dots, a_n$$ with $$a_1 - a_n, a_2 - a_1, a_3 - a_2, \dots, a_n - a_{n-1}$$

Now starting initially with $$a_1, a_2, \dots, a_n = 1, 0, 0, \dots, 0$$ you continue the above step $N$ times.

Let $S_N$ be the largest among the absolute values of the resulting $n$ numbers.

Show that there is a real number $\beta \ge \sqrt{2}$ (independent of $N$), such that

$$ S_N \ge \dfrac{\beta^N}{n}$$

i.e some of the numbers become exponentially large (could be negative), even though the total sum is $0$.

Scroll down for a solution.

.

.

.

.

.

.

We use complex numbers!

Since $n > 1$, we can find an $n^{th}$ root of unity $\zeta$, such that $ |\zeta - 1| \ge \sqrt{2}$.

 We can easily see this geometrically: $ |\zeta - 1|$ is the distance between $\zeta$ and $1$, so we just pick one of the vertices of the $n$-gon formed by the $n^{th}$ roots of unity that lies in the positive $y$ and negative $x$ quadrant.

Now given the state of numbers after $m$ steps as $a_1, a_2, \dots a_n$ define $$ V_m = \sum_{k=1}^{n} a_k \zeta^{k-1}$$

Note that $$|V_m| \le \sum_{k=1}^{n} |a_k \zeta^{k-1}| \le n S_m$$

Now consider 

$$V_m (1 - \zeta) = \sum_{k=1}^{n} a_k \zeta^{k-1} - \sum_{k=1}^{n} a_k \zeta^k $$

$$ = \sum_{k=1}^n (a_k - a_{k-1}) \zeta^{k-1} = V_{m+1}$$

with the convention that $a_{0} = a_n$ and using the fact that $\zeta^n = 1$.

Thus we have that $$V_{m+1} = V_m (1 - \zeta)$$

Now $V_0 = 1$ and therefore we have that

$$V_N = (1 - \zeta)^N$$

Thus we have that

$$n S_N \ge |V_N| = |1 - \zeta|^N $$

i.e.

$$ S_N \ge \dfrac{\beta^N}{n}$$

where $\beta = |1 - \zeta| \ge \sqrt{2}$.

$\textbf{Additional Remarks (Getting a Formula):}$

In fact, we can show that we can read off the exact values we get after $N$ steps, from the coefficients in the expansion of $(1 - x)^N$, subject to collapsing higher degree terms with $x^n = 1$, $x^{n+1} = x$ etc. 

Since the transformations are linear and $1,0,\dots,0$ is a cyclic shift of $0,\dots,1\dots, 0$, this is enough to give a general formula starting with any initial set of numbers.

Another approach to get a formula is to just use matrices and diagonalize/convert to jordan normal form etc.

Yet another approach is to view the cyclic sequence $a_1, a_2, \dots a_n$ as the infinite sequence $a_1, a_2, \dots, a_n, a_1, a_2, \dots, a_n, a_1, a_2 \dots $ and apply the forward difference formula, and replacing $a_{kn + r}$ with $a_r$.