\documentclass[12pt,final,notitlepage,onecolumn]{article}%
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
%TCIDATA{Created=Sat Mar 27 17:33:36 2004}
%TCIDATA{LastRevised=Thursday, June 04, 2026 10:23:43}
%TCIDATA{<META NAME="ViewSettings" CONTENT="0">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{<META NAME="DocumentShell" CONTENT="s">}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\voffset=-2.5cm
\hoffset=-2.5cm
\setlength\textheight{24cm}
\setlength\textwidth{15.5cm}
\begin{document}

\begin{center}
\textbf{Rep\#2: An algebraic proof of an analytic lemma}

Darij Grinberg

[not completed, not proofread]

\bigskip
\end{center}

There is a rule of thumb that in 90\% of all cases when a proof in algebra or
combinatorics seems to use analysis, this use can be easily avoided. For
example, when a proof of a combinatorial identity uses power series, it is -
in most cases - enough to replace the words "power series" by "formal power
series", and there is no need anymore to worry about issues of convergence and
well-definedness\footnote{This is not entirely correct: For instance, often
one needs infinite sums of formal power series, and in this case one still has
to worry about their \textit{formal} convergence (i. e. that for any given
monomial, only finitely many of the summands have a nonzero coefficient in
front of this monomial). However, this is usually much easier than proving
analytical convergence.}. When a proof of an algebraic fact works in the field
$\mathbb{C}$, it will - in most cases - work just as well in the algebraic
closure of $\mathbb{Q}$, or in any algebraically closed field of
characteristic zero, and sometimes even the "algebraically closed" condition
can be lifted, and it is enough to consider a sufficiently large finite
algebraic extension of $\mathbb{Q}$. However, as always when it comes to such
rules of thumb, there are exceptions. Here is one lemma that is used in
various algebraic proofs, and which seems to be really much simpler to prove
using analytical properties of $\mathbb{C}$ than using pure algebra:

\begin{quote}
\textbf{Lemma 1.} Let $A\diagup\mathbb{Q}$ be a field extension. Let $n$ be a
positive integer, and let $\zeta_{1}$, $\zeta_{2}$, $...$, $\zeta_{n}$ be $n$
roots of unity in $A$ (of course, these roots of unity can be of different
orders, and there can be equal roots among them). Assume that $\dfrac{1}%
{n}\left(  \zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)  $ is an algebraic
integer. Then, either $\zeta_{1}+\zeta_{2}+...+\zeta_{n}=0$ or $\zeta
_{1}=\zeta_{2}=...=\zeta_{n}$.

\textit{Remark.} An element $s\in A$ is said to be an \textit{algebraic
integer} if it is integral over the subring $\mathbb{Z}$ of $\mathbb{Q}$.
\end{quote}

This Lemma 1 appears in \cite{1} as Lemma 4.22.

In this note, we will first discuss the standard proof of Lemma 1, which uses
complex numbers in a nontrivial way, and then a (much longer and uglier but)
purely algebraic-combinatorial one.

Both proofs begin by reducing Lemma 1 to a simpler fact:

\begin{quote}
\textbf{Lemma 2.} Let $A\diagup\mathbb{Q}$ be a finite-dimensional field
extension. Let $S$ be a finite set, and for every $s\in S$, let $\xi_{s}$ be a
root of unity in $A$. (Of course, these roots of unity can be of different
orders, and there can be equal roots among them.) Assume that $\sum
\limits_{s\in S}\xi_{s}\in\mathbb{Q}$ and $\left\vert \sum\limits_{s\in S}%
\xi_{s}\right\vert \geq\left\vert S\right\vert $. Then, $\xi_{s}=\xi_{t}$ for
any two elements $s$ and $t$ of $S$. (In other words, all the elements
$\xi_{s}$ for various $s\in S$ are equal.)
\end{quote}

Let us show how to derive Lemma 1 from this Lemma 2:

\textit{Proof of Lemma 1.} Let $\mathbb{A}$ be the ring of all algebraic
integers in $A$. Then, $\mathbb{Q}\cap\mathbb{A}=\mathbb{Z}$%
\ \ \ \ \footnote{In fact, let $s\in\mathbb{Q}\cap\mathbb{A}$. Then,
$s=\dfrac{a}{b}$ for some coprime integers $a$ and $b$ (because $s\in
\mathbb{Q}\cap\mathbb{A}$ yields $s\in\mathbb{Q}$), and there exist some
$n\in\mathbb{N}$ and integers $\alpha_{0}$, $\alpha_{1}$, $...$, $\alpha_{n}$
such that $\sum\limits_{k=0}^{n}\alpha_{k}s^{k}=0$ and $\alpha_{n}=1$ (because
$s\in\mathbb{Q}\cap\mathbb{A}$ yields $s\in\mathbb{A}$, so that $s$ is an
algebraic integer; in other words, $s$ is integral over $\mathbb{Z}$). Hence,
$0=\sum\limits_{k=0}^{n}\alpha_{k}s^{k}=\sum\limits_{k=0}^{n}\alpha_{k}\left(
\dfrac{a}{b}\right)  ^{k}=\sum\limits_{k=0}^{n}\alpha_{k}\dfrac{a^{k}}{b^{k}}%
$. Multiplying this equation by $b^{n}$, we obtain $0=\sum\limits_{k=0}%
^{n}\alpha_{k}a^{k}b^{n-k}=\sum\limits_{k=0}^{n-1}\alpha_{k}a^{k}%
b^{n-k}+\underbrace{\alpha_{n}}_{=1}a^{n}\underbrace{b^{n-n}}_{=b^{0}=1}%
=\sum\limits_{k=0}^{n-1}\alpha_{k}a^{k}b^{n-k}+a^{n}$, so that $a^{n}%
=-\sum\limits_{k=0}^{n-1}\alpha_{k}a^{k}b^{n-k}$. Hence, $b\mid a^{n}$ (since
$b\mid-\sum\limits_{k=0}^{n-1}\alpha_{k}a^{k}b^{n-k}$, because $b\mid b^{n-k}$
for every $k\in\left\{  0,1,...,n-1\right\}  $). Since $a$ and $b$ are
coprime, this yields that either $b=1$ or $b=-1$. Hence, $s=\dfrac{a}{b}$ must
lie in $\mathbb{Z}$. Thus, we have proven that every $s\in\mathbb{Q}%
\cap\mathbb{A}$ lies in $\mathbb{Z}$. Therefore, $\mathbb{Q}\cap
\mathbb{A}\subseteq\mathbb{Z}$, qed. This yields $\mathbb{Q}\cap
\mathbb{A}=\mathbb{Z}$ (since clearly $\mathbb{Z}\subseteq\mathbb{Q}%
\cap\mathbb{A}$).}.

We can WLOG assume that the field extension $A\diagup\mathbb{Q}$ is
finite-dimensional (in fact, we can otherwise replace $A$ by the field
$\mathbb{Q}\left(  \zeta_{1},\zeta_{2},...,\zeta_{n}\right)  $, which is
finite-dimensional over $\mathbb{Q}$\ \ \ \ \footnote{because $\zeta_{1}$,
$\zeta_{2}$, $...$, $\zeta_{n}$ are algebraic over $\mathbb{Q}$ (since
$\zeta_{1}$, $\zeta_{2}$, $...$, $\zeta_{n}$ are roots of unity)}) and normal
(in fact, we can otherwise replace $A$ by the normal closure of $A$). Then,
$A\diagup\mathbb{Q}$ is a finite-dimensional Galois extension (since
$\operatorname*{char}\mathbb{Q}=0$). Let $G$ be the Galois group of this
extension $A\diagup\mathbb{Q}$. Then, the product $\prod\limits_{\sigma\in
G}\sigma\left(  \dfrac{1}{n}\left(  \zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)
\right)  $ is the norm of the element $\dfrac{1}{n}\left(  \zeta_{1}+\zeta
_{2}+...+\zeta_{n}\right)  \in A$, and therefore $\prod\limits_{\sigma\in
G}\sigma\left(  \dfrac{1}{n}\left(  \zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)
\right)  \in\mathbb{Q}$. But on the other hand, $\prod\limits_{\sigma\in
G}\sigma\left(  \dfrac{1}{n}\left(  \zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)
\right)  \in\mathbb{A}$ \ \ \ \ \footnote{In fact, $\dfrac{1}{n}\left(
\zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)  $ is an algebraic integer, and thus
its conjugates $\sigma\left(  \dfrac{1}{n}\left(  \zeta_{1}+\zeta
_{2}+...+\zeta_{n}\right)  \right)  $ are algebraic integers for all
$\sigma\in G$, and therefore their product $\prod\limits_{\sigma\in G}%
\sigma\left(  \dfrac{1}{n}\left(  \zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)
\right)  $ is an algebraic integer as well. In other words, $\prod
\limits_{\sigma\in G}\sigma\left(  \dfrac{1}{n}\left(  \zeta_{1}+\zeta
_{2}+...+\zeta_{n}\right)  \right)  \in\mathbb{A}$, qed.}. Thus,
\[
\prod\limits_{\sigma\in G}\sigma\left(  \dfrac{1}{n}\left(  \zeta_{1}%
+\zeta_{2}+...+\zeta_{n}\right)  \right)  \in\mathbb{Q}\cap\mathbb{A}%
=\mathbb{Z}.
\]


Now,%
\begin{align*}
&  n^{\left\vert G\right\vert }\prod\limits_{\sigma\in G}\underbrace{\sigma
\left(  \dfrac{1}{n}\left(  \zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)  \right)
}_{\substack{=\dfrac{1}{n}\left(  \sigma\left(  \zeta_{1}\right)
+\sigma\left(  \zeta_{2}\right)  +...+\sigma\left(  \zeta_{n}\right)  \right)
\\\left(  \text{since }\sigma\text{ is a }\mathbb{Q}\text{-algebra
homomorphism}\right)  }}\\
&  =n^{\left\vert G\right\vert }\prod\limits_{\sigma\in G}\left(  \dfrac{1}%
{n}\left(  \sigma\left(  \zeta_{1}\right)  +\sigma\left(  \zeta_{2}\right)
+...+\sigma\left(  \zeta_{n}\right)  \right)  \right)
=\underbrace{n^{\left\vert G\right\vert }\left(  \dfrac{1}{n}\right)
^{\left\vert G\right\vert }}_{=1}\prod\limits_{\sigma\in G}\underbrace{\left(
\sigma\left(  \zeta_{1}\right)  +\sigma\left(  \zeta_{2}\right)
+...+\sigma\left(  \zeta_{n}\right)  \right)  }_{=\sum\limits_{k=1}^{n}%
\sigma\left(  \zeta_{k}\right)  }\\
&  =\prod\limits_{\sigma\in G}\sum\limits_{k=1}^{n}\sigma\left(  \zeta
_{k}\right)  =\sum\limits_{\kappa\in\left\{  1,2,...,n\right\}  ^{G}}%
\prod_{\sigma\in G}\sigma\left(  \zeta_{\kappa\left(  \sigma\right)  }\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the product rule}\right)  .
\end{align*}
Here, we let $\left\{  1,2,...,n\right\}  ^{G}$ denote the set of all maps
from the set $G$ to $\left\{  1,2,...,n\right\}  $. Hence,%
\[
\sum\limits_{\kappa\in\left\{  1,2,...,n\right\}  ^{G}}\prod_{\sigma\in
G}\sigma\left(  \zeta_{\kappa\left(  \sigma\right)  }\right)  =n^{\left\vert
G\right\vert }\underbrace{\prod\limits_{\sigma\in G}\sigma\left(  \dfrac{1}%
{n}\left(  \zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)  \right)  }_{\in
\mathbb{Z}}\in n^{\left\vert G\right\vert }\mathbb{Z}.
\]
If we denote $\prod\limits_{\sigma\in G}\sigma\left(  \zeta_{\kappa\left(
\sigma\right)  }\right)  $ by $\xi_{\kappa}$ for every $\kappa\in\left\{
1,2,...,n\right\}  ^{G}$, then this becomes $\sum\limits_{\kappa\in\left\{
1,2,...,n\right\}  ^{G}}\xi_{\kappa}\in n^{\left\vert G\right\vert }%
\mathbb{Z}$.

Hence, two cases are possible:

\textit{Case 1:} We have $\sum\limits_{\kappa\in\left\{  1,2,...,n\right\}
^{G}}\xi_{\kappa}=0$.

\textit{Case 2:} We have $\left\vert \sum\limits_{\kappa\in\left\{
1,2,...,n\right\}  ^{G}}\xi_{\kappa}\right\vert \geq n^{\left\vert
G\right\vert }$.

Let us first consider Case 2. In this case, we notice that for each map
$\kappa\in\left\{  1,2,...,n\right\}  ^{G}$, the element $\xi_{\kappa}%
=\prod\limits_{\sigma\in G}\sigma\left(  \zeta_{\kappa\left(  \sigma\right)
}\right)  \in A$ is a root of unity (in fact, $\sigma\left(  \zeta
_{\kappa\left(  \sigma\right)  }\right)  \in A$ is a root of unity for each
$\sigma\in G$\ \ \ \ \footnote{because $\zeta_{\kappa\left(  \sigma\right)  }$
is a root of unity, and because the map $\sigma$ sends roots of unity to roots
of unity (since $\sigma$ is a ring automorphism of $A$)}, and the product of
roots of unity is a root of unity again). Also, $\sum\limits_{s\in\left\{
1,2,...,n\right\}  ^{G}}\xi_{s}=\sum\limits_{\kappa\in\left\{
1,2,...,n\right\}  ^{G}}\xi_{\kappa}\in n^{\left\vert G\right\vert }%
\mathbb{Z}\subseteq\mathbb{Q}$ and
\begin{align*}
\left\vert \sum\limits_{s\in\left\{  1,2,...,n\right\}  ^{G}}\xi
_{s}\right\vert  &  =\left\vert \sum\limits_{\kappa\in\left\{
1,2,...,n\right\}  ^{G}}\xi_{\kappa}\right\vert \geq n^{\left\vert
G\right\vert }\ \ \ \ \ \ \ \ \ \ \left(  \text{since we are in Case 2}\right)
\\
&  =\left\vert \left\{  1,2,...,n\right\}  ^{G}\right\vert .
\end{align*}
Thus, Lemma 2 (applied to $S=\left\{  1,2,...,n\right\}  ^{G}$) yields that
$\xi_{s}=\xi_{t}$ for any two elements $s$ and $t$ of $S$. Consequently,
$\zeta_{\alpha}=\zeta_{\beta}$ for any two elements $\alpha$ and $\beta$ of
$\left\{  1,2,...,n\right\}  $ (because if we let $s\in\left\{
1,2,...,n\right\}  ^{G}$ be the map defined by $s\left(  \sigma\right)
=\left\{
\begin{array}
[c]{c}%
\alpha,\text{ if }\sigma=\operatorname*{id};\\
1,\text{ if }\sigma\neq\operatorname*{id}%
\end{array}
\right.  $ for every $\sigma\in G$, and let $t\in\left\{  1,2,...,n\right\}
^{G}$ be the map defined by $t\left(  \sigma\right)  =\left\{
\begin{array}
[c]{c}%
\beta,\text{ if }\sigma=\operatorname*{id};\\
1,\text{ if }\sigma\neq\operatorname*{id}%
\end{array}
\right.  $ for every $\sigma\in G$, then%
\[
\xi_{s}=\prod\limits_{\sigma\in G}\sigma\left(  \zeta_{s\left(  \sigma\right)
}\right)  =\prod_{\substack{\sigma\in G;\\\sigma=\operatorname*{id}}%
}\sigma\left(  \underbrace{\zeta_{s\left(  \sigma\right)  }}_{\substack{=\zeta
_{\alpha}\\\text{(since}\\\sigma=\operatorname*{id}\text{)}}}\right)
\cdot\prod_{\substack{\sigma\in G;\\\sigma\neq\operatorname*{id}}%
}\sigma\left(  \underbrace{\zeta_{s\left(  \sigma\right)  }}_{\substack{=\zeta
_{1}\\\text{(since}\\\sigma\neq\operatorname*{id}\text{)}}}\right)
=\underbrace{\prod_{\substack{\sigma\in G;\\\sigma=\operatorname*{id}}%
}\sigma\left(  \zeta_{\alpha}\right)  }_{=\operatorname*{id}\left(
\zeta_{\alpha}\right)  =\zeta_{\alpha}}\cdot\prod_{\substack{\sigma\in
G;\\\sigma\neq\operatorname*{id}}}\sigma\left(  \zeta_{1}\right)
=\zeta_{\alpha}\cdot\prod_{\substack{\sigma\in G;\\\sigma\neq
\operatorname*{id}}}\sigma\left(  \zeta_{1}\right)
\]
and similarly $\xi_{t}=\zeta_{\beta}\cdot\prod\limits_{\substack{\sigma\in
G;\\\sigma\neq\operatorname*{id}}}\sigma\left(  \zeta_{1}\right)  $, and
hence\footnote{Here, we use that $\xi_{t}$ is invertible (since $\xi_{t}$ is a
root of unity)} $\dfrac{\xi_{s}}{\xi_{t}}=\dfrac{\zeta_{\alpha}\cdot
\prod\limits_{\substack{\sigma\in G;\\\sigma\neq\operatorname*{id}}%
}\sigma\left(  \zeta_{1}\right)  }{\zeta_{\beta}\cdot\prod
\limits_{\substack{\sigma\in G;\\\sigma\neq\operatorname*{id}}}\sigma\left(
\zeta_{1}\right)  }=\dfrac{\zeta_{\alpha}}{\zeta_{\beta}}$, so that $\xi
_{s}=\xi_{t}$ yields $\zeta_{\alpha}=\zeta_{\beta}$). In other words,
$\zeta_{1}=\zeta_{2}=...=\zeta_{n}$. Thus, in Case 2, Lemma 1 is proven.

Now let us deal with Case 1. In this case,%
\[
0=\sum\limits_{\kappa\in\left\{  1,2,...,n\right\}  ^{G}}\xi_{\kappa}%
=\sum\limits_{\kappa\in\left\{  1,2,...,n\right\}  ^{G}}\prod_{\sigma\in
G}\sigma\left(  \zeta_{\kappa\left(  \sigma\right)  }\right)  =n^{\left\vert
G\right\vert }\prod\limits_{\sigma\in G}\sigma\left(  \dfrac{1}{n}\left(
\zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)  \right)  .
\]
Hence, $0=\prod\limits_{\sigma\in G}\sigma\left(  \dfrac{1}{n}\left(
\zeta_{1}+\zeta_{2}+...+\zeta_{n}\right)  \right)  $. Thus, there exists some
$\sigma\in G$ such that $0=\sigma\left(  \dfrac{1}{n}\left(  \zeta_{1}%
+\zeta_{2}+...+\zeta_{n}\right)  \right)  $ (because $A$ is a field, so the
product of some elements of $A$ can only be zero if some of the factors is
zero). Therefore, $0=\dfrac{1}{n}\left(  \zeta_{1}+\zeta_{2}+...+\zeta
_{n}\right)  $ (because $\sigma$ is an automorphism of the field $A$ and
therefore injective), and thus $0=\zeta_{1}+\zeta_{2}+...+\zeta_{n}$. Thus,
Lemma 1 is proven in Case 1.

Altogether, we have thus shown Lemma 1 in both Cases 1 and 2. This completes
the proof of Lemma 1 under the assumption that Lemma 2 has been proved.

Now, it remains to prove Lemma 2. First, here is the analytic proof:

\textit{First proof of Lemma 2.} The extension $A$ of the field $\mathbb{Q}$
is finite-dimensional, and therefore can be embedded into the algebraic
closure of $\mathbb{Q}$. The algebraic closure of $\mathbb{Q}$, in turn, can
be embedded into $\mathbb{C}$. So we can WLOG assume that $A$ is a subfield of
$\mathbb{C}$. Then, by the triangle inequality, $\left\vert \sum\limits_{s\in
S}\xi_{s}\right\vert \leq\sum\limits_{s\in S}\underbrace{\left\vert \xi
_{s}\right\vert }_{\substack{=1\text{\ (since }\xi_{s}\text{ is a}\\\text{root
of unity)}}}=\sum\limits_{s\in S}1=\left\vert S\right\vert $. But this
inequality must be an equality (since the opposite inequality $\left\vert
\sum\limits_{s\in S}\xi_{s}\right\vert \geq\left\vert S\right\vert $ also
holds), so we must have equality in the triangle inequality $\left\vert
\sum\limits_{s\in S}\xi_{s}\right\vert \leq\sum\limits_{s\in S}\left\vert
\xi_{s}\right\vert $. Hence, all the complex numbers $\xi_{s}$ for $s\in S$
must have the same argument, i. e., we must have $\arg\xi_{s}=\arg\xi_{t}$ for
any two elements $s$ and $t$ of $S$. But this yields $\xi_{s}=\xi_{t}$ for any
two elements $s$ and $t$ of $S$ (because $\arg\xi_{s}=\arg\xi_{t}$ and
$\left\vert \xi_{s}\right\vert =1=\left\vert \xi_{t}\right\vert $). This
proves Lemma 2.

This proof is short, however it uses the complex numbers in a substantial way.
Instead of just relying on their algebraic properties, like most proofs in
algebra do, it uses their geometric structure as well (modulus inequalities),
and thus cannot be directly translated into a suitably large algebraic
extension of $\mathbb{Q}$. But there is a different way to proceed:

\textit{Second proof of Lemma 2.} We are going to rely on the following lemma:

\begin{quote}
\textbf{Lemma 3.} Let $A$ be a field. Let $n$ be a positive integer, and for
every $i\in\left\{  1,2,...,n\right\}  $, let $\xi_{i}$ be a root of unity in
$A$. Then, there exists some root of unity $\zeta$ in $A$ and a sequence
$\left(  k_{1},k_{2},...,k_{n}\right)  $ of nonnegative integers such that
$\left(  \xi_{i}=\zeta^{k_{i}}\text{ for every }i\in\left\{
1,2,...,n\right\}  \right)  $ and $\gcd\left(  k_{1},k_{2},...,k_{n}\right)
=1$.
\end{quote}

The proof of this lemma can be found in \cite{2} (where it appears as Lemma
3). Actually it is a rather easy corollary of the known fact (\cite[Theorem
1]{2}) that any finite subgroup of the multiplicative group of a field is cyclic.

Another simple (but very useful, not only in this context) lemma that we need is:

\begin{quote}
\textbf{Lemma 4.} Let $B$ be a subfield of a field $A$. Let $U\in
B^{\alpha\times\beta}$ be a matrix, where $\alpha$ and $\beta$ are nonnegative
integers. Then, $\dim\operatorname*{Ker}_{A}U=\dim\operatorname*{Ker}_{B}U$.
Here, for any field extension $F\diagup B$, we denote by $\operatorname*{Ker}%
_{F}U$ the kernel of the linear map $F^{\beta}\rightarrow F^{\alpha}$ given by
$v\mapsto Uv$.
\end{quote}

\textit{First proof of Lemma 4.} It is known that for any field extension
$F\diagup B$, we have $\dim\operatorname*{Ker}_{F}U=\beta-\operatorname*{Rank}%
_{F}U$, where $\operatorname*{Rank}_{F}U$ denotes the rank of the linear map
$F^{\beta}\rightarrow F^{\alpha}$ given by $v\mapsto Uv$. It is also known
that $\operatorname*{rank}\nolimits_{F}U$ is the greatest integer $\nu$ such
that the matrix $U$ has a $\nu\times\nu$ minor with nonzero determinant.
Therefore, $\operatorname*{rank}\nolimits_{F}U$ does not depend on $F$, and
therefore $\operatorname*{rank}_{A}U=\operatorname*{rank}_{B}U$. Hence,
$\dim\operatorname*{Ker}_{A}U=\beta-\operatorname*{rank}_{A}U=\beta
-\operatorname*{rank}_{B}U=\dim\operatorname*{Ker}_{B}U$. This proves Lemma 4.

\textit{Second proof of Lemma 4.} By the Gaussian elimination algorithm (over
the field $B$), we can transform the matrix $U$ into a matrix $V$ which is in
row echelon form. In other words, we can find a matrix $V$ in row echelon form
and an invertible matrix $E\in B^{\alpha\times\alpha}$ such that $V=EU$ (here,
the matrix $E$ is the product of the elementary matrices corresponding to the
elementary row operations which constitute the steps of the Gaussian
elimination algorithm). Since $E$ is invertible, we have
\begin{equation}
\operatorname*{Ker}\nolimits_{F}\left(  EU\right)  =\operatorname*{Ker}%
\nolimits_{F}U \label{4proof2}%
\end{equation}
for every field extension $F\diagup B$. But we know that $\dim
\operatorname*{Ker}_{F}V=\beta-\operatorname*{Rank}_{F}V$, where
$\operatorname*{Rank}_{F}V$ denotes the rank of the linear map $F^{\beta
}\rightarrow F^{\alpha}$ given by $v\mapsto Vv$. The rank
$\operatorname*{Rank}_{F}V$ of the matrix $V$ is the number of all nonzero
rows of the matrix $V$ (because the matrix $V$ is in row echelon form). Hence,
for every field extension $F\diagup B$, we have%
\begin{align*}
\dim\underbrace{\operatorname*{Ker}\nolimits_{F}U}%
_{\substack{=\operatorname*{Ker}\nolimits_{F}\left(  EU\right)  \\\text{(by
(\ref{4proof2}))}}}  &  =\dim\operatorname*{Ker}\nolimits_{F}%
\underbrace{\left(  EU\right)  }_{=V}=\dim\operatorname*{Ker}\nolimits_{F}%
V=\beta-\underbrace{\operatorname*{Rank}\nolimits_{F}V}_{=\left(  \text{the
number of all nonzero rows of the matrix }V\right)  }\\
&  =\beta-\left(  \text{the number of all nonzero rows of the matrix
}V\right)  .
\end{align*}
Thus, $\dim\operatorname*{Ker}\nolimits_{F}U$ does not depend on the field
$F$. Hence, $\dim\operatorname*{Ker}_{A}U=\dim\operatorname*{Ker}_{B}U$, and
thus Lemma 4 is proven.

We will finally need a lemma about inequalities:

\begin{quote}
\textbf{Lemma 5.} Let $n$ be a nonnegative integer. Let $a_{1},a_{2}%
,\ldots,a_{n}$ be any $n$ rational numbers. Let $b$ and $N$ be two further
rational numbers such that $N\geq n$. Assume that
\begin{equation}
\left\vert b\right\vert \geq\left\vert a_{s}\right\vert
\ \ \ \ \ \ \ \ \ \ \text{for each }s\in\left\{  1,2,\ldots,n\right\}  .
\label{5ass1}%
\end{equation}
Assume furthermore that%
\begin{equation}
\sum_{s\in\left\{  1,2,\ldots,n\right\}  }a_{s}=Nb. \label{5ass2}%
\end{equation}
Then, $a_{s}=b$ for each $s\in\left\{  1,2,\ldots,n\right\}  $.
\end{quote}

\textit{Proof of Lemma 5.} Lemma 5 is vacuously true for $n=0$. Thus, we WLOG
assume that $n>0$.

Furthermore, Lemma 5 is very easy for $b=0$\ \ \ \ \footnote{\textit{Proof.}
Assume that $b=0$. Then, each $s\in\left\{  1,2,\ldots,n\right\}  $ satisfies
$\left\vert a_{s}\right\vert \leq0$ (since $b=0$ entails $\left\vert
b\right\vert =\left\vert 0\right\vert =0$, so that $0=\left\vert b\right\vert
\geq\left\vert a_{s}\right\vert $ by (\ref{5ass1}), and therefore $\left\vert
a_{s}\right\vert \leq0$) and thus $a_{s}=0$ (since the only rational number
whose absolute value is $\leq0$ is $0$), so that $a_{s}=b$ (since $a_{s}%
=0=b$). Thus, Lemma 5 holds for $b=0$.}. Thus, we WLOG assume that $b\neq0$.
This allows us to divide by $b$. For each $s\in\left\{  1,2,\ldots,n\right\}
$, we have%
\begin{align}
\dfrac{a_{s}}{b}  &  \leq\left\vert \dfrac{a_{s}}{b}\right\vert
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }x\leq\left\vert x\right\vert \text{
for any }x\in\mathbb{Q}\right) \nonumber\\
&  =\dfrac{\left\vert a_{s}\right\vert }{\left\vert b\right\vert }=\dfrac
{1}{\left\vert b\right\vert }\cdot\underbrace{\left\vert a_{s}\right\vert
}_{\substack{\leq\left\vert b\right\vert \\\text{(by (\ref{5ass1}))}%
}}\nonumber\\
&  \leq\dfrac{1}{\left\vert b\right\vert }\cdot\left\vert b\right\vert
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\dfrac{1}{\left\vert b\right\vert
}\geq0\right) \nonumber\\
&  =1. \label{5div2}%
\end{align}
Taking the sum of these $n$ inequalities, we obtain%
\[
\sum_{s\in\left\{  1,2,\ldots,n\right\}  }\dfrac{a_{s}}{b}\leq\sum
_{s\in\left\{  1,2,\ldots,n\right\}  }1=n\cdot1=n.
\]
Hence,%
\begin{align*}
n  &  \geq\sum_{s\in\left\{  1,2,\ldots,n\right\}  }\dfrac{a_{s}}{b}=\dfrac
{1}{b}\sum_{s\in\left\{  1,2,\ldots,n\right\}  }a_{s}=\dfrac{1}{b}%
Nb\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{5ass2})}\right) \\
&  =N\geq n.
\end{align*}
This chain of inequalities must be an equality (since the leftmost and the
rightmost sides of this chain are equal), so that all inequalities inbetween
must be equalities. In particular, the inequality (\ref{5div2}) (which says
that $\dfrac{a_{s}}{b}\leq1$ for every $s\in\left\{  1,2,...,n\right\}  $)
must become an equality. In other words, each $s\in\left\{  1,2,\ldots
,n\right\}  $ must satisfy $\dfrac{a_{s}}{b}=1$. In other words, each
$s\in\left\{  1,2,\ldots,n\right\}  $ must satisfy $a_{s}=b$. This proves
Lemma 5.

Finally, we come to the \textit{proof of Lemma 2:}

First let us WLOG assume that $S\neq\varnothing$ (otherwise, Lemma 2 is
vacuously true).

The condition of Lemma 2 yields $\sum\limits_{s\in S}\xi_{s}\in\mathbb{Q}$. We
WLOG assume that $\sum\limits_{s\in S}\xi_{s}\geq0$ (because otherwise, we can
enforce $\sum\limits_{s\in S}\xi_{s}\geq0$ by replacing $\xi_{s}$ by $-\xi
_{s}$ for every $s\in S$; in fact, this is allowed because $-\xi_{s}$ is a
root of unity for every $s\in S$\ \ \ \ \footnote{This is because $\xi_{s}$ is
a root of unity for every $s\in S$, and because whenever an element $z\in A$
is a root of unity, the element $-z$ is a root of unity as well.}). Denote the
sum $\sum\limits_{s\in S}\xi_{s}$ by $N$. Then, $N=\sum\limits_{s\in S}\xi
_{s}\in\mathbb{Q}$. Also, $N=\sum\limits_{s\in S}\xi_{s}\geq0$ yields
$N=\left\vert N\right\vert =\left\vert \sum\limits_{s\in S}\xi_{s}\right\vert
\geq\left\vert S\right\vert >0$.

We can also WLOG assume that $S=\left\{  1,2,...,n\right\}  $ for some
$n\in\mathbb{N}$ (because $S$ is a finite set, and we need the set $S$ only as
an index set for labeling the roots $\xi_{s}$ of unity). Consider this $n$.
Then, $n=\left\vert S\right\vert \neq0$ (since $S\neq\varnothing$), so that
$n$ is a positive integer. Thus, by Lemma 3, there exists some root of unity
$\zeta$ in $A$ and a sequence $\left(  k_{1},k_{2},...,k_{n}\right)  $ of
nonnegative integers such that $\left(  \xi_{i}=\zeta^{k_{i}}\text{ for every
}i\in\left\{  1,2,...,n\right\}  \right)  $ and $\gcd\left(  k_{1}%
,k_{2},...,k_{n}\right)  =1$. We WLOG assume that $k_{1}$ is the largest of
the integers $k_{1},$ $k_{2},$ $...,$ $k_{n}$ (otherwise, we can just
interchange the roots $\xi_{1},$ $\xi_{2},$ $...,$ $\xi_{n}$). Then,
$k_{1}\geq k_{s}$ for every $s\in\left\{  1,2,...,n\right\}  $. Therefore,
$k_{1}\geq1$ (because there exists at least one $s\in\left\{
1,2,...,n\right\}  $ such that $k_{s}\geq1$\ \ \ \ \footnote{since otherwise,
we would have $k_{1}=k_{2}=...=k_{n}=0$ (because $k_{1},$ $k_{2},$ $...,$
$k_{n}$ are all nonnegative), which would contradict $\gcd\left(  k_{1}%
,k_{2},...,k_{n}\right)  =1$.}, and therefore this $s$ satisfies $k_{1}\geq
k_{s}\geq1$).

Now, $N=\underbrace{\sum\limits_{s\in S}}_{=\sum\limits_{s\in\left\{
1,2,...,n\right\}  }}\underbrace{\xi_{s}}_{=\zeta^{k_{s}}}=\sum\limits_{s\in
\left\{  1,2,...,n\right\}  }\zeta^{k_{s}}$. Also, $N\geq\left\vert
S\right\vert =n$ (since $S=\left\{  1,2,...,n\right\}  $).

Choose a positive integer $m$ such that $\zeta$ is a $m$-th root of unity.
(Such $m$ indeed exists, since $\zeta$ is a root of unity.) Then, $\zeta
^{m}=1$.

We need to introduce two notations:

\begin{itemize}
\item If $\mathcal{A}$ is an assertion, then we denote by $\left[
\mathcal{A}\right]  $ the truth value of $\mathcal{A}$ (defined by $\left[
\mathcal{A}\right]  =\left\{
\begin{array}
[c]{c}%
1,\text{ if }\mathcal{A}\text{ is true;}\\
0,\text{ if }\mathcal{A}\text{ is false}%
\end{array}
\right.  $).

\item If $U$ is a matrix, and $u$ and $v$ are two positive integers, then
$U_{u,v}$ denotes the entry of the matrix $U$ at the $\left(  u,v\right)  $-th
place (if such an entry exists). If $w$ is a vector, and $i$ is a positive
integer, then $w_{i}$ denotes the $i$-th coordinate of the vector $w$.
\end{itemize}

We notice a trivial but important fact: If $a$, $b$ and $q$ are three integers
such that $a\leq q\leq b$, and if $h_{j}$ is an element of $A$ for every
$j\in\left\{  a,a+1,...,b\right\}  $, then%
\begin{equation}
\sum_{j=a}^{b}\left[  j=q\right]  h_{j}=h_{q}. \label{sum-lemma}%
\end{equation}
\footnote{This is because%
\begin{align*}
\sum\limits_{j=a}^{b}\left[  j=q\right]  h_{j}  &  =\sum\limits_{j\in\left\{
a,a+1,...,b\right\}  }\left[  j=q\right]  h_{j}=\sum\limits_{\substack{j\in
\left\{  a,a+1,...,b\right\}  ;\\j=q}}\underbrace{\left[  j=q\right]
}_{=1\text{ (since }j=q\text{ is true)}}h_{j}+\sum\limits_{\substack{j\in
\left\{  a,a+1,...,b\right\}  ;\\j\neq q}}\underbrace{\left[  j=q\right]
}_{=0\text{ (since }j=q\text{ is false)}}h_{j}\\
&  =\underbrace{\sum\limits_{\substack{j\in\left\{  a,a+1,...,b\right\}
;\\j=q}}h_{j}}_{\substack{=h_{q}\text{ (since }q\in\left\{
a,a+1,...,b\right\}  \\\text{(because }a\leq q\leq b\text{ and }q\in
\mathbb{Z}\text{))}}}+\underbrace{\sum\limits_{\substack{j\in\left\{
a,a+1,...,b\right\}  ;\\j\neq q}}0h_{j}}_{=0}=h_{q}.
\end{align*}
}

Now, define a $\left(  k_{1}+m\right)  \times\left(  k_{1}+m\right)  $-matrix
$U\in\mathbb{Q}^{\left(  k_{1}+m\right)  \times\left(  k_{1}+m\right)  }$ by%
\begin{equation}
\left(
\begin{array}
[c]{c}%
U_{i,j}=\left\{
\begin{array}
[c]{c}%
\left[  j=i\right]  -\left[  j=i+m\right]  ,\ \ \ \ \ \ \ \ \ \ \text{if
}i\leq k_{1};\\
\sum\limits_{s\in\left\{  1,2,...,n\right\}  }\left[  j=i-k_{s}\right]
-N\left[  j=i\right]  ,\ \ \ \ \ \ \ \ \ \ \text{if }i>k_{1}%
\end{array}
\right.  \\
\text{for every }i\in\left\{  1,2,...,k_{1}+m\right\}  \text{ and }%
j\in\left\{  1,2,...,k_{1}+m\right\}
\end{array}
\right)  .\label{A}%
\end{equation}
\footnote{If you know the theory of resultants, you will recognize this matrix
$U$ as the Sylvester matrix of the two polynomials $X^{m}-1$ and
$\sum\limits_{s\in\left\{  1,2,...,n\right\}  }X^{k_{s}}-N$ (or as a
transposed and, possibly, row-permuted version of this Sylvester matrix -
depending on how one defines the Sylvester matrix of two polynomials).} Hence,%
\begin{align}
U_{i,j}  & =\left[  j=i\right]  -\left[  j=i+m\right]  \label{A<}\\
& \ \ \ \ \ \ \ \ \ \ \text{ for every }i\in\left\{  1,2,...,k_{1}\right\}
\text{ and }j\in\left\{  1,2,...,k_{1}+m\right\}  \nonumber
\end{align}
(by (\ref{A}), because $i\in\left\{  1,2,...,k_{1}\right\}  $ yields $i\leq
k_{1}$) and%
\begin{align}
U_{i,j}  & =\sum\limits_{s\in\left\{  1,2,...,n\right\}  }\left[
j=i-k_{s}\right]  -N\left[  j=i\right]  \label{A>}\\
& \ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{  k_{1}+1,k_{1}%
+2,...,k_{1}+m\right\}  \text{ and }j\in\left\{  1,2,...,k_{1}+m\right\}
\nonumber
\end{align}
(by (\ref{A}), because $i\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $
yields $i>k_{1}$). Thus, for any vector $h\in A^{k_{1}+m}$ and every
$i\in\left\{  1,2,...,k_{1}\right\}  $, we have%
\begin{align}
\left(  Uh\right)  _{i} &  =\sum_{j=1}^{k_{1}+m}U_{i,j}h_{j}=\sum_{j=1}%
^{k_{1}+m}\left(  \left[  j=i\right]  -\left[  j=i+m\right]  \right)
h_{j}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{A<})}\right)  \nonumber\\
&  =\underbrace{\sum_{j=1}^{k_{1}+m}\left[  j=i\right]  h_{j}}%
_{\substack{=h_{i}\text{ (by (\ref{sum-lemma}) (applied to }a=1\text{,}%
\\q=i\text{ and }b=k_{1}+m\text{), since }1\leq i\leq k_{1}+m\text{)}%
}}-\underbrace{\sum_{j=1}^{k_{1}+m}\left[  j=i+m\right]  h_{j}}%
_{\substack{=h_{i+m}\text{ (by (\ref{sum-lemma}) (applied to }a=1\text{,}%
\\q=i+m\text{ and }b=k_{1}+m\text{), since}\\1\leq i+m\leq k_{1}+m\text{,
because }i\leq k_{1}\text{)}}}\nonumber\\
&  =h_{i}-h_{i+m}.\label{Uh<}%
\end{align}
Besides, for any vector $h\in A^{k_{1}+m}$ and every $i\in\left\{
k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $, we have%
\begin{align}
\left(  Uh\right)  _{i} &  =\sum_{j=1}^{k_{1}+m}U_{i,j}h_{j}=\sum_{j=1}%
^{k_{1}+m}\left(  \sum\limits_{s\in\left\{  1,2,...,n\right\}  }\left[
j=i-k_{s}\right]  -N\left[  j=i\right]  \right)  h_{j}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{A>})}\right)  \nonumber\\
&  =\sum\limits_{s\in\left\{  1,2,...,n\right\}  }\underbrace{\sum
_{j=1}^{k_{1}+m}\left[  j=i-k_{s}\right]  h_{j}}_{\substack{=h_{i-k_{s}}\text{
(by (\ref{sum-lemma}) (applied to }a=1\text{, }q=i-k_{s}\\\text{and }%
b=k_{1}+m\text{), since }1\leq i-k_{s}\leq k_{1}+m\text{,}\\\text{because
}i>k_{1}\geq k_{s}\text{ yields }i\geq k_{s}+1\text{)}}}-N\underbrace{\sum
_{j=1}^{k_{1}+m}\left[  j=i\right]  h_{j}}_{\substack{=h_{i}\text{ (by
(\ref{sum-lemma}) (applied to }a=1\text{,}\\q=i\text{ and }b=k_{1}+m\text{),
since }1\leq i\leq k_{1}+m\text{)}}}\nonumber\\
&  =\sum\limits_{s\in\left\{  1,2,...,n\right\}  }h_{i-k_{s}}-Nh_{i}%
.\label{Uh>}%
\end{align}


Now, for any $\vartheta\in A$, we define a vector $\overline{\vartheta}\in
A^{k_{1}+m}$ by setting $\overline{\vartheta}_{i}=\vartheta^{k_{1}+m-i}$ for
every $i\in\left\{  1,2,...,k_{1}+m\right\}  $. That is,%
\[
\overline{\vartheta}=\left(  \vartheta^{k_{1}+m-1},\vartheta^{k_{1}%
+m-2},\ldots,\vartheta^{0}\right)  \in A^{k_{1}+m}.
\]
In particular, for $\vartheta=\zeta$, we obtain the vector $\overline{\zeta
}\in A^{k_{1}+m}$ with entries
\[
\overline{\zeta}_{i}=\zeta^{k_{1}+m-i}\ \ \ \ \ \ \ \ \ \ \text{for every
}i\in\left\{  1,2,...,k_{1}+m\right\}  .
\]
Thus, for every $i\in\left\{  1,2,...,k_{1}\right\}  $, we have%
\begin{align}
\left(  U\overline{\zeta}\right)  _{i} &  =\underbrace{\overline{\zeta}_{i}%
}_{=\zeta^{k_{1}+m-i}}-\underbrace{\overline{\zeta}_{i+m}}_{=\zeta
^{k_{1}+m-\left(  i+m\right)  }}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{Uh<}), applied to }h=\overline{\zeta}\right)  \nonumber\\
&  =\underbrace{\zeta^{k_{1}+m-i}}_{=\zeta^{k_{1}-i+m}=\zeta^{k_{1}-i}%
\zeta^{m}}-\underbrace{\zeta^{k_{1}+m-\left(  i+m\right)  }}_{=\zeta^{k_{1}%
-i}}=\zeta^{k_{1}-i}\left(  \underbrace{\zeta^{m}}_{=1}-1\right)
=\zeta^{k_{1}-i}\underbrace{\left(  1-1\right)  }_{=0}\nonumber\\
&  =0.\label{awi1}%
\end{align}
Besides, for every $i\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $, we
have%
\begin{align}
\left(  U\overline{\zeta}\right)  _{i} &  =\sum\limits_{s\in\left\{
1,2,...,n\right\}  }\underbrace{\overline{\zeta}_{i-k_{s}}}_{\substack{=\zeta
^{k_{1}+m-\left(  i-k_{s}\right)  }\\=\zeta^{k_{1}+m-i+k_{s}}\\=\zeta
^{k_{1}+m-i}\zeta^{k_{s}}}}-N\underbrace{\overline{\zeta}_{i}}_{=\zeta
^{k_{1}+m-i}}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{Uh>}), applied to
}h=\overline{\zeta}\right)  \nonumber\\
&  =\sum\limits_{s\in\left\{  1,2,...,n\right\}  }\zeta^{k_{1}+m-i}%
\zeta^{k_{s}}-N\zeta^{k_{1}+m-i}=\zeta^{k_{1}+m-i}\left(  \underbrace{\sum
\limits_{s\in\left\{  1,2,...,n\right\}  }\zeta^{k_{s}}}_{=N}-N\right)
\nonumber\\
&  =\zeta^{k_{1}+m-i}\underbrace{\left(  N-N\right)  }_{=0}=0.\label{awi2}%
\end{align}


Consequently, $\left(  U\overline{\zeta}\right)  _{i}=0$ for every
$i\in\left\{  1,2,...,k_{1}+m\right\}  $ \ \ \ \ \footnote{In fact, let
$i\in\left\{  1,2,...,k_{1}+m\right\}  $. Then, either $i\in\left\{
1,2,...,k_{1}\right\}  $ or $i\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}
$ must hold. But in both cases, $\left(  U\overline{\zeta}\right)  _{i}=0$ (in
fact, in the case $i\in\left\{  1,2,...,k_{1}\right\}  $, the equation
$\left(  U\overline{\zeta}\right)  _{i}=0$ follows from (\ref{awi1}), and in
the case $i\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $, the equation
$\left(  U\overline{\zeta}\right)  _{i}=0$ follows from (\ref{awi2})).\ Thus,
$\left(  U\overline{\zeta}\right)  _{i}=0$ is proven.}. In other words,
$U\overline{\zeta}=0$, so that
\begin{equation}
\overline{\zeta}\in\operatorname*{Ker}\nolimits_{A}U. \label{zetainKer}%
\end{equation}


Next, we shall show that $\operatorname*{Ker}\nolimits_{\mathbb{Q}}%
U\subseteq\operatorname*{span}\left\{  \overline{1}\right\}  $ (of course,
$\overline{1}\in\mathbb{Q}^{k_{1}+m}$, since $1\in\mathbb{Q}$). In combination
with (\ref{zetainKer}), this will let us apply Lemma 4 and readily obtain
$\overline{\zeta}\in\operatorname*{span}\left\{  \overline{1}\right\}  $,
which will quickly lead us to $\zeta=1$.

Let $h\in\operatorname*{Ker}_{\mathbb{Q}}U$ be a vector. Then, $h\in
\mathbb{Q}^{k_{1}+m}$ and $0=Uh$. Consequently, every $i\in\left\{
1,2,...,k_{1}\right\}  $ satisfies $0=\left(  Uh\right)  _{i}=h_{i}-h_{i+m}$
(by (\ref{Uh<})), so that%
\begin{equation}
h_{i}=h_{i+m}\ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{  1,2,...,k_{1}%
\right\}  . \label{h1}%
\end{equation}
Besides, every $i\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $ satisfies%
\begin{align*}
0  &  =\left(  Uh\right)  _{i}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}0=Uh\right) \\
&  =\sum\limits_{s\in\left\{  1,2,...,n\right\}  }h_{i-k_{s}}-Nh_{i}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{Uh>})}\right)  ,
\end{align*}
so that%
\begin{equation}
\sum\limits_{s\in\left\{  1,2,...,n\right\}  }h_{i-k_{s}}=Nh_{i}%
\ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}%
+m\right\}  . \label{h2}%
\end{equation}


The vector $h\in\mathbb{Q}^{k_{1}+m}$ has $k_{1}+m$ coordinates: $h_{1}$,
$h_{2}$, $...$, $h_{k_{1}+m}$. So we have a finite sequence $\left(
h_{1},h_{2},...,h_{k_{1}+m}\right)  $ of length $k_{1}+m$. We will now extend
this sequence in both directions: We define a number $h_{i}\in\mathbb{Q}$ for
every $i\in\mathbb{Z}\setminus\left\{  1,2,...,k_{1}+m\right\}  $ by setting
$h_{i}=h_{\pi\left(  i\right)  }$, where $\pi:\mathbb{Z}\rightarrow\left\{
1,2,...,k_{1}+m\right\}  $ is the map defined by%
\[
\pi\left(  i\right)  =\left(  \text{the element }x\text{ of the set }\left\{
1,2,...,k_{1}+m\right\}  \text{ which satisfies }x\equiv i\operatorname{mod}%
k_{1}+m\right)  .
\]
Thus, a number $h_{i}\in\mathbb{Q}$ is defined for every $i\in\mathbb{Z}$, and
we get a two-sided infinite sequence $\left(  ...,h_{-2},h_{-1},h_{0}%
,h_{1},h_{2},...\right)  $ which extends the sequence $\left(  h_{1}%
,h_{2},...,h_{k_{1}+m}\right)  $ of coordinates of the vector $h$. It is clear
that $h_{i}=h_{\pi\left(  i\right)  }$ for every $i\in\mathbb{Z}%
$\ \ \ \ \footnote{In fact, two cases are possible: either $i\in
\mathbb{Z}\setminus\left\{  1,2,...,k_{1}+m\right\}  $ or $i\in\left\{
1,2,...,k_{1}+m\right\}  $. But in both cases, we have $h_{i}=h_{\pi\left(
i\right)  }$ (in fact, in the case $i\in\mathbb{Z}\setminus\left\{
1,2,...,k_{1}+m\right\}  $, we have $h_{i}=h_{\pi\left(  i\right)  }$ by the
definition of $h_{i}$; on the other hand, in the case $i\in\left\{
1,2,...,k_{1}+m\right\}  $, we have $h_{i}=h_{\pi\left(  i\right)  }$ because
of $i=\pi\left(  i\right)  $).}. Consequently,
\begin{equation}
h_{i}=h_{j}\text{ for any two integers }i\text{ and }j\text{ which satisfy
}i\equiv j\operatorname{mod}k_{1}+m \label{period}%
\end{equation}
(because $i\equiv j\operatorname{mod}k_{1}+m$ yields $\pi\left(  i\right)
=\pi\left(  j\right)  $ and thus $h_{i}=h_{\pi\left(  i\right)  }%
=h_{\pi\left(  j\right)  }=h_{j}$). In other words, the sequence $\left(
...,h_{-2},h_{-1},h_{0},h_{1},h_{2},...\right)  $ is periodic with period
$k_{1}+m$. Thus, $\left\{  h_{i}\mid i\in\mathbb{Z}\right\}  =\left\{
h_{1},h_{2},...,h_{k_{1}+m}\right\}  $, so that $\left\{  \left\vert
h_{i}\right\vert \mid i\in\mathbb{Z}\right\}  =\left\{  \left\vert
h_{1}\right\vert ,\left\vert h_{2}\right\vert ,...,\left\vert h_{k_{1}%
+m}\right\vert \right\}  $.

Now, let $\nu\in\mathbb{Z}$ be some integer for which $\left\vert h_{\nu
}\right\vert =\max\left\{  \left\vert h_{i}\right\vert \mid i\in
\mathbb{Z}\right\}  $. (Such an integer $\nu$ exists because the set $\left\{
\left\vert h_{i}\right\vert \mid i\in\mathbb{Z}\right\}  =\left\{  \left\vert
h_{1}\right\vert ,\left\vert h_{2}\right\vert ,...,\left\vert h_{k_{1}%
+m}\right\vert \right\}  $ is finite and thus has a maximum.) We denote the
rational number $h_{\nu}$ by $q$. Our next goal is to prove that $h_{i}=q$ for
every $i\in\mathbb{Z}$.

First, we note that%
\begin{equation}
\text{if an integer }\mu\text{ satisfies }\pi\left(  \mu\right)  \in\left\{
1,2,...,k_{1}\right\}  \text{ and }h_{\mu}=q\text{, then }h_{\mu+m}=q\text{.}
\label{opt1}%
\end{equation}
\textit{Proof of (\ref{opt1}).} In fact, if an integer $\mu$ satisfies
$\pi\left(  \mu\right)  \in\left\{  1,2,...,k_{1}\right\}  $ and $h_{\mu}=q$,
then%
\begin{align*}
h_{\mu+m}  &  =h_{\pi\left(  \mu\right)  +m}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by (\ref{period}) (applied to }\mu+m\text{ and }\pi\left(  \mu\right)
+m\text{ instead of }i\text{ and }j\text{),}\\
\text{because }\mu+m\equiv\pi\left(  \mu\right)  +m\operatorname{mod}%
k_{1}+m\text{ (since }\mu\equiv\pi\left(  \mu\right)  \operatorname{mod}%
k_{1}+m\text{)}%
\end{array}
\right) \\
&  =h_{\pi\left(  \mu\right)  }\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{h1}), applied to }i=\pi\left(  \mu\right)  \right) \\
&  =h_{\mu}=q,
\end{align*}
so that (\ref{opt1}) is proven.

Besides, we note that%
\begin{align}
&  \text{if an integer }\mu\text{ satisfies }\pi\left(  \mu\right)
\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  \text{ and }h_{\mu}=q\text{,
then}\nonumber\\
&  h_{\mu-k_{s}}=q\text{ for every }s\in\left\{  1,2,...,n\right\}  .
\label{opt2}%
\end{align}
\textit{Proof of (\ref{opt2}).} In fact, let an integer $\mu$ satisfy
$\pi\left(  \mu\right)  \in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $ and
$h_{\mu}=q$. Then, $h_{\pi\left(  \mu\right)  }=h_{\mu}=q$, and thus
$\left\vert h_{\pi\left(  \mu\right)  }\right\vert =\left\vert q\right\vert
=\left\vert h_{\nu}\right\vert =\max\left\{  \left\vert h_{i}\right\vert \mid
i\in\mathbb{Z}\right\}  \geq\left\vert h_{\pi\left(  \mu\right)  -k_{s}%
}\right\vert $ for every $s\in\left\{  1,2,...,n\right\}  $. On the other
hand, (\ref{h2}) (applied to $i=\pi\left(  \mu\right)  $) yields
$\sum\limits_{s\in\left\{  1,2,...,n\right\}  }h_{\pi\left(  \mu\right)
-k_{s}}=Nh_{\pi\left(  \mu\right)  }$ (since $\pi\left(  \mu\right)
\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $). Hence, Lemma 5 (applied
to $a_{s}=h_{\pi\left(  \mu\right)  -k_{s}}$ and $b=h_{\pi\left(  \mu\right)
}$) yields that%
\[
h_{\pi\left(  \mu\right)  -k_{s}}=h_{\pi\left(  \mu\right)  }%
\ \ \ \ \ \ \ \ \ \ \text{for each }s\in\left\{  1,2,\ldots,n\right\}  .
\]
Since $h_{\pi\left(  \mu\right)  }=q$ and $h_{\pi\left(  \mu\right)  -k_{s}%
}=h_{\mu-k_{s}}$ (because $\pi\left(  \mu\right)  \equiv\mu\operatorname{mod}%
k_{1}+m$ yields $\pi\left(  \mu\right)  -k_{s}\equiv\mu-k_{s}%
\operatorname{mod}k_{1}+m$, and therefore (\ref{period}) (applied to
$\pi\left(  \mu\right)  -k_{s}$ and $\mu-k_{s}$ instead of $i$ and $j$) yields
$h_{\pi\left(  \mu\right)  -k_{s}}=h_{\mu-k_{s}}$), this rewrites as%
\[
h_{\mu-k_{s}}=q\ \ \ \ \ \ \ \ \ \ \text{for each }s\in\left\{
1,2,...,n\right\}  .
\]
Thus, (\ref{opt2}) is proven.

Next let us prove that%
\begin{equation}
\text{if an integer }\mu\text{ satisfies }h_{\mu}=q\text{, then }h_{\mu
+m}=q\text{.} \label{opt11}%
\end{equation}
\textit{Proof of (\ref{opt11}).} In fact, let an integer $\mu$ satisfy
$h_{\mu}=q$. Then, either $\pi\left(  \mu\right)  \in\left\{  1,2,...,k_{1}%
\right\}  $ or $\pi\left(  \mu\right)  \in\left\{  k_{1}+1,k_{1}%
+2,...,k_{1}+m\right\}  $ (because $\pi\left(  \mu\right)  \in\left\{
1,2,...,k_{1}+m\right\}  $). But in both of these cases, $h_{\mu+m}=q$ holds
(in fact, in the case when $\pi\left(  \mu\right)  \in\left\{  1,2,...,k_{1}%
\right\}  $, we have $h_{\mu+m}=q$ by (\ref{opt1}), and in the case when
$\pi\left(  \mu\right)  \in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $, we
have%
\begin{align*}
h_{\mu+m}  &  =h_{\mu-k_{1}}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by (\ref{period}) (applied to }\mu+m\text{ and }\mu-k_{1}\text{ instead
of }i\text{ and }j\text{),}\\
\text{since }\mu+m\equiv\mu-k_{1}\operatorname{mod}k_{1}+m
\end{array}
\right) \\
&  =q\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{opt2}), applied to
}s=1\right)
\end{align*}
). Thus, $h_{\mu+m}=q$ must hold, and (\ref{opt11}) is proven.

We note that, obviously, (\ref{opt11}) is a generalization of (\ref{opt1}).
But now we will generalize (\ref{opt11}) even further (albeit trivially): We
will show that%
\begin{equation}
\text{if two integers }\delta\text{ and }\varepsilon\text{ satisfy }h_{\delta
}=q\text{ and }\delta\equiv\varepsilon\operatorname{mod}m\text{, then
}h_{\varepsilon}=q\text{.} \label{opt1mod}%
\end{equation}
\textit{Proof of (\ref{opt1mod}).} In fact, let an integer $\delta$ satisfy
$h_{\delta}=q$. We will first show that $h_{\delta+\rho m}=q$ for every
nonnegative integer $\rho$. In fact, this is clear by
induction\footnote{\textit{Induction base:} For $\rho=0$, we have
$h_{\delta+\rho m}=h_{\delta+0m}=h_{\delta}=q$, and thus $h_{\delta+\rho m}=q$
is proven for $\rho=0$.
\par
\textit{Induction step:} Let $\phi$ be a nonnegative integer. Assume that
$h_{\delta+\rho m}=q$ holds for $\rho=\phi$. Then, $h_{\delta+\rho m}=q$ holds
for $\rho=\phi+1$ as well (because $h_{\delta+\left(  \phi+1\right)
m}=h_{\left(  \delta+\phi m\right)  +m}=q$ (by (\ref{opt11}), applied to
$\mu=\delta+\phi m$), because $h_{\delta+\phi m}=q$, since $h_{\delta+\rho
m}=q$ holds for $\rho=\phi$). This completes the induction step.
\par
Thus, the induction proof of $h_{\delta+\rho m}=q$ is complete.}. Now, for any
integer $\varepsilon$ satisfying $\delta\equiv\varepsilon\operatorname{mod}m$,
there exists a nonnegative integer $\rho$ satisfying $\varepsilon\equiv
\delta+\rho m\operatorname{mod}k_{1}+m$\ \ \ \ \footnote{In fact,
$\dfrac{\varepsilon-\delta}{m}\in\mathbb{Z}$ (since $\delta\equiv
\varepsilon\operatorname{mod}m$). Now, let $\rho$ be the residue of
$\dfrac{\varepsilon-\delta}{m}$ modulo $k_{1}+m$. Then, $\rho\geq0$ and
$\rho\equiv\dfrac{\varepsilon-\delta}{m}\operatorname{mod}k_{1}+m$, so that
$\rho m\equiv\varepsilon-\delta\operatorname{mod}k_{1}+m$ and thus
$\varepsilon\equiv\delta+\rho m\operatorname{mod}k_{1}+m$.}, and thus
\begin{align*}
h_{\varepsilon}  &  =h_{\delta+\rho m}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by (\ref{period}) (applied to }\varepsilon\text{ and }\delta+\rho
m\text{ instead of }i\text{ and }j\text{),}\\
\text{since }\varepsilon\equiv\delta+\rho m\operatorname{mod}k_{1}+m
\end{array}
\right) \\
&  =q
\end{align*}
(because we have proven $h_{\delta+\rho m}=q$ above). This completes the proof
of (\ref{opt1mod}).

Next, let us generalize (\ref{opt2}): Namely, let us show that%
\begin{equation}
\text{if an integer }\mu\text{ satisfies }h_{\mu}=q\text{, then }h_{\mu-k_{s}%
}=q\text{ for every }s\in\left\{  1,2,...,n\right\}  . \label{opt21}%
\end{equation}
\textit{Proof of (\ref{opt21}).} In fact, let an integer $\mu$ satisfy
$h_{\mu}=q$, and let $s\in\left\{  1,2,...,n\right\}  $. Then, there exists
some $\lambda\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $ such that
$\lambda\equiv\mu\operatorname{mod}m$\ \ \ \ \footnote{In fact, the $m$
integers $k_{1}+1,$ $k_{1}+2,$ $...,$ $k_{1}+m$ are $m$ consecutive integers,
and therefore they leave all possible residues modulo $m$. Therefore, in
particular, one of these $m$ integers leaves the same residue modulo $m$ as
$\mu$; in other words, one of these $m$ integers is congruent to $\mu$ modulo
$m$. In other words, there exists some $\lambda\in\left\{  k_{1}%
+1,k_{1}+2,...,k_{1}+m\right\}  $ such that $\lambda\equiv\mu
\operatorname{mod}m$.}. Hence, $h_{\lambda}=q$ (by (\ref{opt1mod}), applied to
$\delta=\mu$ and $\varepsilon=\lambda$). But $\lambda\in\left\{  k_{1}%
+1,k_{1}+2,...,k_{1}+m\right\}  \subseteq\left\{  1,2,...,k_{1}+m\right\}  $
yields
\[
\pi\left(  \lambda\right)  =\left(  \text{the element }x\text{ of the set
}\left\{  1,2,...,k_{1}+m\right\}  \text{ which satisfies }x\equiv
\lambda\operatorname{mod}k_{1}+m\right)  =\lambda
\]
(because $\lambda$ itself is an element of the set $\left\{  1,2,...,k_{1}%
+m\right\}  $ and satisfies $\lambda\equiv\lambda\operatorname{mod}k_{1}+m$).
Hence, $\lambda\in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}  $ rewrites as
$\pi\left(  \lambda\right)  \in\left\{  k_{1}+1,k_{1}+2,...,k_{1}+m\right\}
$. Thus (\ref{opt2}) (applied to $\lambda$ instead of $\mu$) yields
$h_{\lambda-k_{s}}=q$. Thus, $h_{\mu-k_{s}}=q$ (by (\ref{opt1mod}), applied to
$\delta=\lambda-k_{s}$ and $\varepsilon=\mu-k_{s}$) because $\lambda
-k_{s}\equiv\mu-k_{s}\operatorname{mod}m$ (since $\lambda\equiv\mu
\operatorname{mod}m$). This proves (\ref{opt21}).

We record a trivial generalization of (\ref{opt21}): Let us prove that
\begin{equation}
\text{if some }s\in\left\{  1,2,...,n\right\}  \text{ and two integers }%
\delta\text{ and }\varepsilon\text{ satisfy }h_{\delta}=q\text{ and }%
\delta\equiv\varepsilon\operatorname{mod}k_{s}\text{, then }h_{\varepsilon
}=q\text{.} \label{opt2mod}%
\end{equation}
\textit{Proof of (\ref{opt2mod}).} In fact, let some $s\in\left\{
1,2,...,n\right\}  $ and an integer $\delta$ satisfy $h_{\delta}=q$. We will
first show that $h_{\delta-\rho k_{s}}=q$ for every nonnegative integer $\rho
$. In fact, this is clear by induction\footnote{\textit{Induction base:} For
$\rho=0$, we have $h_{\delta-\rho k_{s}}=h_{\delta-0k_{s}}=h_{\delta}=q$, and
thus $h_{\delta-\rho k_{s}}=q$ is proven for $\rho=0$.
\par
\textit{Induction step:} Let $\phi$ be a nonnegative integer. Assume that
$h_{\delta-\rho k_{s}}=q$ holds for $\rho=\phi$. Then, $h_{\delta-\rho k_{s}%
}=q$ holds for $\rho=\phi+1$ as well (because $h_{\delta-\left(
\phi+1\right)  k_{s}}=h_{\left(  \delta-\phi k_{s}\right)  -k_{s}}=q$ (by
(\ref{opt21}), applied to $\mu=\delta-\phi k_{s}$), because $h_{\delta-\phi
k_{s}}=q$, since $h_{\delta-\rho k_{s}}=q$ holds for $\rho=\phi$). This
completes the induction step.
\par
Thus, the induction proof of $h_{\delta-\rho k_{s}}=q$ is complete.}. Now, for
any integer $\varepsilon$ satisfying $\delta\equiv\varepsilon
\operatorname{mod}k_{s}$, there exists a nonnegative integer $\rho$ satisfying
$\varepsilon\equiv\delta-\rho k_{s}\operatorname{mod}k_{1}+m$%
\ \ \ \ \footnote{In fact, $k_{s}\mid\delta-\varepsilon$ (since $\delta
\equiv\varepsilon\operatorname{mod}k_{s}$). In other words, $\delta
-\varepsilon=k_{s}w$ for some $w\in\mathbb{Z}$. Consider this $w$. Now, let
$\rho$ be the residue of $w$ modulo $k_{1}+m$. Then, $\rho$ is a nonnegative
integer and satisfies $\rho\equiv w\operatorname{mod}k_{1}+m$, so that $\rho
k_{s}\equiv wk_{s}=k_{s}w=\delta-\varepsilon\operatorname{mod}k_{1}+m$ and
thus $\varepsilon\equiv\delta-\rho k_{s}\operatorname{mod}k_{1}+m$.}, and
thus
\begin{align*}
h_{\varepsilon}  &  =h_{\delta-\rho k_{s}}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by (\ref{period}) (applied to }\varepsilon\text{ and }\delta-\rho
k_{s}\text{ instead of }i\text{ and }j\text{),}\\
\text{since }\varepsilon\equiv\delta-\rho k_{s}\operatorname{mod}k_{1}+m
\end{array}
\right) \\
&  =q
\end{align*}
(because we have proven $h_{\delta-\rho k_{s}}=q$ above). This completes the
proof of (\ref{opt2mod}).

Our next goal is to show that%
\begin{align}
&  \text{if some }\lambda\in\left\{  1,2,...,n\right\}  \text{ and two
integers }\delta\text{ and }\varepsilon\text{ satisfy }h_{\delta}=q\text{
and}\nonumber\\
&  \delta\equiv\varepsilon\operatorname{mod}\gcd\left(  k_{1},k_{2}%
,...,k_{\lambda}\right)  \text{, then }h_{\varepsilon}=q. \label{optgcd}%
\end{align}
\textit{Proof of (\ref{optgcd}).} In fact, let us prove (\ref{optgcd}) by
induction over $\lambda$.

\textit{Induction base:} If $\lambda=1$, then (\ref{optgcd}) follows from
(\ref{opt2mod}), applied to $s=1$ (because $\lambda=1$ yields $\gcd\left(
k_{1},k_{2},...,k_{\lambda}\right)  =\gcd\left(  k_{1}\right)  =k_{1}=k_{s}$
due to $s=1$). Hence, (\ref{optgcd}) is proven for $\lambda=1$, so that the
induction base is complete.

\textit{Induction step:} Let $s\in\left\{  1,2,...,n\right\}  $ be such that
$s>1$. Assume that (\ref{optgcd}) holds for $\lambda=s-1$. Our aim is then to
prove that (\ref{optgcd}) holds for $\lambda=s$.

In fact, since (\ref{optgcd}) holds for $\lambda=s-1$, we have:%
\begin{equation}
\text{if two integers }\delta\text{ and }\varepsilon\text{ satisfy }h_{\delta
}=q\text{ and }\delta\equiv\varepsilon\operatorname{mod}\gcd\left(
k_{1},k_{2},...,k_{s-1}\right)  \text{, then }h_{\varepsilon}=q.
\label{optgcdProof1}%
\end{equation}
Our goal is to prove that (\ref{optgcd}) holds for $\lambda=s$; in other
words, our goal is to prove that%
\begin{equation}
\text{if two integers }\delta\text{ and }\varepsilon\text{ satisfy }h_{\delta
}=q\text{ and }\delta\equiv\varepsilon\operatorname{mod}\gcd\left(
k_{1},k_{2},...,k_{s}\right)  \text{, then }h_{\varepsilon}=q.
\label{optgcdProof2}%
\end{equation}


In fact, let $\delta$ and $\varepsilon$ be two integers satisfying $h_{\delta
}=q$ and $\delta\equiv\varepsilon\operatorname{mod}\gcd\left(  k_{1}%
,k_{2},...,k_{s}\right)  $.

Let $D=\gcd\left(  k_{1},k_{2},...,k_{s-1}\right)  $. Then, $\gcd\left(
k_{1},k_{2},...,k_{s}\right)  =\gcd\left(  \underbrace{\gcd\left(  k_{1}%
,k_{2},...,k_{s-1}\right)  }_{=D},k_{s}\right)  =\gcd\left(  D,k_{s}\right)
$. Hence, $\delta\equiv\varepsilon\operatorname{mod}\gcd\left(  k_{1}%
,k_{2},...,k_{s}\right)  $ rewrites as $\delta\equiv\varepsilon
\operatorname{mod}\gcd\left(  D,k_{s}\right)  $. Thus, $\gcd\left(
D,k_{s}\right)  \mid\delta-\varepsilon$. Hence, there exists an integer $\Phi$
such that $\delta-\varepsilon=\Phi\gcd\left(  D,k_{s}\right)  $.

Now, the two integers $\dfrac{D}{\gcd\left(  D,k_{s}\right)  }$ and
$\dfrac{k_{s}}{\gcd\left(  D,k_{s}\right)  }$ are coprime, so that by Bezout's
Theorem, there exist integers $u$ and $v$ such that $u\dfrac{D}{\gcd\left(
D,k_{s}\right)  }+v\dfrac{k_{s}}{\gcd\left(  D,k_{s}\right)  }=1$. In other
words, $1=u\dfrac{D}{\gcd\left(  D,k_{s}\right)  }+v\dfrac{k_{s}}{\gcd\left(
D,k_{s}\right)  }=\dfrac{uD+vk_{s}}{\gcd\left(  D,k_{s}\right)  }$, so that
$uD+vk_{s}=\gcd\left(  D,k_{s}\right)  $. Hence, $\delta-\varepsilon
=\Phi\underbrace{\gcd\left(  D,k_{s}\right)  }_{=uD+vk_{s}}=\Phi\left(
uD+vk_{s}\right)  =\Phi uD+\Phi vk_{s}$. Hence, $\delta-\Phi uD=\varepsilon
+\Phi vk_{s}\equiv\varepsilon\operatorname{mod}k_{s}$.

Now, applying (\ref{optgcdProof1}) to $\delta-\Phi uD$ instead of
$\varepsilon$, we obtain $h_{\delta-\Phi uD}=q$ (because $\delta\equiv
\delta-\Phi uD\operatorname{mod}\gcd\left(  k_{1},k_{2},...,k_{s-1}\right)  $,
since $\gcd\left(  k_{1},k_{2},...,k_{s-1}\right)  =D$). Therefore, applying
(\ref{opt2mod}) to $\delta-\Phi uD$ instead of $\delta$, we obtain
$h_{\varepsilon}=q$ (because $\delta-\Phi uD\equiv\varepsilon
\operatorname{mod}k_{s}$). This proves (\ref{optgcdProof2}). Since
(\ref{optgcdProof2}) is precisely the assertion of (\ref{optgcd}) for
$\lambda=s$, this yields that (\ref{optgcd}) holds for $\lambda=s$. This
completes the induction step, and thus the assertion (\ref{optgcd}) is proven.

Now, we finally claim that%
\begin{equation}
\text{any integer }\varepsilon\text{ satisfies }h_{\varepsilon}=q\text{.}
\label{optEnd}%
\end{equation}
\textit{Proof of (\ref{optEnd}).} In fact, we have $h_{\nu}=q$ (by the
definition of $q$) and $\nu\equiv\varepsilon\operatorname{mod}\gcd\left(
k_{1},k_{2},...,k_{n}\right)  $ (because $\gcd\left(  k_{1},k_{2}%
,...,k_{n}\right)  =1$). Hence, (\ref{optgcd}) (applied to $\lambda=n$ and
$\delta=\nu$) yields $h_{\varepsilon}=q$, and thus (\ref{optEnd}) is proven.

Now, (\ref{optEnd}) leads to $h=q\cdot\overline{1}$\ \ \ \ \footnote{where
$\overline{\vartheta}\in A^{k_{1}+m}$ is the vector defined by $\overline
{\vartheta}_{i}=\vartheta^{k_{1}+m-i}$ for every $i\in\left\{  1,2,...,k_{1}%
+m\right\}  $} (because for every $i\in\left\{  1,2,...,k_{1}+m\right\}  $,
the assertion (\ref{optEnd}) (applied to $\varepsilon=i$) yields
$h_{i}=q=q\cdot\underbrace{1^{k_{1}+m-i}}_{=\overline{1}_{i}}=q\cdot
\overline{1}_{i}=\left(  q\cdot\overline{1}\right)  _{i}$), so that
$h\in\operatorname*{span}\left\{  \overline{1}\right\}  $.

Forget that we fixed $h$. Thus we have proven that every $h\in
\operatorname*{Ker}_{\mathbb{Q}}U$ satisfies $h\in\operatorname*{span}\left\{
\overline{1}\right\}  $. Consequently,
\begin{equation}
\operatorname*{Ker}\nolimits_{\mathbb{Q}}U\subseteq\operatorname*{span}%
\left\{  \overline{1}\right\}  , \label{Kerin}%
\end{equation}
and thus $\dim\operatorname*{Ker}_{\mathbb{Q}}U\leq\dim\operatorname*{span}%
\left\{  \overline{1}\right\}  =1$ (because $\overline{1}$ is not the zero
vector, since $\overline{1}_{i}=1^{k_{1}+m-i}\neq0$ for every $i\in\left\{
1,2,...,k_{1}+m\right\}  $).

Now, Lemma 4 (applied to $B=\mathbb{Q}$) yields
\begin{equation}
\dim\operatorname*{Ker}\nolimits_{A}U=\dim\operatorname*{Ker}%
\nolimits_{\mathbb{Q}}U, \label{dimKer=}%
\end{equation}
so that $\dim\operatorname*{Ker}_{\mathbb{Q}}U\leq1$ yields $\dim
\operatorname*{Ker}_{A}U\leq1$.

Also note that $\overline{\zeta}$ is not the zero vector, since its last
coordinate is $\overline{\zeta}_{k_{1}+m}=\zeta^{k_{1}+m-\left(
k_{1}+m\right)  }=\zeta^{0}=1\neq0$. Hence, (\ref{zetainKer}) shows that
$\operatorname*{Ker}_{A}U$ contains a nonzero vector. Thus, $\dim
\operatorname*{Ker}_{A}U\geq1$. Combining this with $\dim\operatorname*{Ker}%
_{A}U\leq1$, we obtain $\dim\operatorname*{Ker}_{A}U=1$. In view of
(\ref{dimKer=}), this rewrites as $\dim\operatorname*{Ker}%
\nolimits_{\mathbb{Q}}U=1$. Hence, $\operatorname*{Ker}\nolimits_{\mathbb{Q}%
}U$ is a $1$-dimensional vector subspace of $\operatorname*{span}\left\{
\overline{1}\right\}  $ (by (\ref{Kerin})). Since the vector space
$\operatorname*{span}\left\{  \overline{1}\right\}  $ is itself $1$%
-dimensional, this entails that $\operatorname*{Ker}\nolimits_{\mathbb{Q}%
}U=\operatorname*{span}\left\{  \overline{1}\right\}  $ (because the only
$1$-dimensional vector subspace of a $1$-dimensional vector space is the whole
space). Therefore, $\overline{1}\in\operatorname*{Ker}\nolimits_{\mathbb{Q}}U$
(since $\overline{1}\in\operatorname*{span}\left\{  \overline{1}\right\}  $).

But obviously $\operatorname*{Ker}\nolimits_{\mathbb{Q}}U\subseteq
\operatorname*{Ker}\nolimits_{A}U$. Thus, $\overline{1}\in\operatorname*{Ker}%
\nolimits_{\mathbb{Q}}U\subseteq\operatorname*{Ker}\nolimits_{A}U$.

But recall that $\dim\operatorname*{Ker}_{A}U\leq1$. Hence, any two vectors in
$\operatorname*{Ker}_{A}U$ are linearly dependent. Since we know that
$\overline{1}\in\operatorname*{Ker}\nolimits_{A}U$ and $\overline{\zeta}%
\in\operatorname*{Ker}\nolimits_{A}U$, this yields that the vectors
$\overline{1}$ and $\overline{\zeta}$ are linearly dependent. Thus, there
exist elements $u$ and $v$ of $A$ such that $\left(  u,v\right)  \neq\left(
0,0\right)  $ and $u\overline{1}+v\overline{\zeta}=0$. Consider these $u$ and
$v$. Now, every $i\in\left\{  1,2,...,k_{1}+m\right\}  $ satisfies%
\[
\left(  u\overline{1}+v\overline{\zeta}\right)  _{i}=u\underbrace{\overline
{1}_{i}}_{=1^{k_{1}+m-i}=1}+v\underbrace{\overline{\zeta}_{i}}_{=\zeta
^{k_{1}+m-i}}=u+v\zeta^{k_{1}+m-i},
\]
so that $\left(  \underbrace{u\overline{1}+v\overline{\zeta}}_{=0}\right)
_{i}=0$ becomes $u+v\zeta^{k_{1}+m-i}=0$, and therefore
\begin{equation}
u=-v\zeta^{k_{1}+m-i}\ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{
1,2,...,k_{1}+m\right\}  . \label{finalstep}%
\end{equation}
Applying this to $i=k_{1}+m$, we obtain $u=-v\zeta^{k_{1}+m-\left(
k_{1}+m\right)  }=-v\zeta^{0}=-v$. Thus, $v\neq0$ (because if $v$ were $0$,
then we would have $u=-v=-0=0$, and thus $\left(  u,v\right)  =\left(
0,0\right)  $, contradicting $\left(  u,v\right)  \neq\left(  0,0\right)  $).
On the other hand, applying (\ref{finalstep}) to $i=k_{1}+m-1\ \ \ \ $%
\footnote{Here, we use that $k_{1}+m-1\in\left\{  1,2,...,k_{1}+m\right\}  $,
which is because $k_{1}\geq1$ and $m\geq1$.}, we obtain $u=-v\zeta
^{k_{1}+m-\left(  k_{1}+m-1\right)  }=-v\zeta^{1}=-v\zeta$. Comparing $u=-v$
with $u=-v\zeta$, we obtain $-v=-v\zeta$, which yields $1=\zeta$ (since
$v\neq0$). Hence, for any two elements $s$ and $t$ of $S$ we have $\xi
_{s}=\zeta^{k_{s}}=1^{k_{s}}=1$ and $\xi_{t}=\zeta^{k_{t}}=1^{k_{t}}=1$, so
that $\xi_{s}=\xi_{t}$. This completes the proof of Lemma 2.

\begin{thebibliography}{9}                                                                                                %


\bibitem {1}Pavel Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex
Schwendner, Elena Udovina and Dmitry Vaintrob, \textit{Introduction to
representation theory}, March 9, 2009.\newline\url{http://math.mit.edu/~etingof/replect.pdf}

\bibitem {2}Darij Grinberg, \textit{Rep\#2a: Finite subgroups of
multiplicative groups of fields}.
\end{thebibliography}


\end{document}