# Tight running times for minimum $\ell_{q}$-norm load balancing: beyond
exponential dependencies on $1/\epsilon$

Lin Chen1111Research of Lin Chen was partly supported by NSF Grant 1756014.
Liangde Tao2 José Verschae3

1Department of Computer Science, Texas Tech University, US
<EMAIL_ADDRESS>
2Department of Computer Science, Zhejiang University, China
<EMAIL_ADDRESS>
3Institute for Mathematical and Computational Engineering,
Faculty of Mathematics and School of Engineering, Pontificia Universidad
Católica de Chile, Chile
<EMAIL_ADDRESS>
###### Abstract

We consider a classical scheduling problem on $m$ identical machines. For an
arbitrary constant $q>1$, the aim is to assign jobs to machines such that
$\sum_{i=1}^{m}C_{i}^{q}$ is minimized, where $C_{i}$ is the total processing
time of jobs assigned to machine $i$. It is well known that this problem is
strongly NP-hard.

Under mild assumptions, the running time of an $(1+\epsilon)$-approximation
algorithm for a strongly NP-hard problem cannot be polynomial on $1/\epsilon$,
unless $\text{P}=\text{NP}$. For most problems in the literature, this
translates into algorithms with running time at least as large as
$2^{\Omega(1/\varepsilon)}+n^{O(1)}$. For the natural scheduling problem
above, we establish the existence of an algorithm which violates this
threshold. More precisely, we design a PTAS that runs in
$2^{\tilde{O}(\sqrt{1/\epsilon})}+n^{O(1)}$ time. This result is in sharp
contrast to the closely related minimum makespan variant, where an exponential
lower bound is known under the exponential time hypothesis (ETH). We
complement our result with an essentially matching lower bound on the running
time, showing that our algorithm is best-possible under ETH. The lower bound
proof exploits new number-theoretical constructions for variants of
progression-free sets, which might be of independent interest.

Furthermore, we provide a fine-grained characterization on the running time of
a PTAS for this problem depending on the relation between $\epsilon$ and the
number of machines $m$. More precisely, our lower bound only holds when
$m=\Theta(\sqrt{1/\epsilon})$. Better algorithms, that go beyond the lower
bound, exist for other values of $m$. In particular, there even exists an
algorithm with running time polynomial in $1/\epsilon$ if we restrict
ourselves to instances with $m=\Omega(1/\epsilon\log^{2}1/\epsilon)$.

Keywords: Polynomial Time Approximation Scheme, Scheduling, Exponential Time
Hypothesis.

##  1 Introduction

We consider a classical scheduling problem on identical parallel machines.
Suppose we are given $m$ identical machines and $n$ jobs, each having a
processing time $p_{j}$. A feasible solution corresponds to an assignment of
jobs to machines. For a given assignment, let $C_{i}$ be the total processing
time of jobs assigned to machine $i$, that is, $C_{i}=\sum_{j\rightarrow
i}p_{j}$. Our objective is to minimize $\sum_{i=1}^{m}C_{i}^{q}$, where $q>1$
is an arbitrary constant. For either exact algorithms or approximation
schemes, minimizing $\sum_{i=1}^{m}C_{i}^{q}$ is equivalent to minimizing the
$\ell_{q}$-norm of machine loads, i.e., $(\sum_{i=1}^{m}C_{i}^{q})^{1/q}$. In
the standard 3-field scheduling notation by Graham et al. [13], this problem
is denoted as $P||\sum_{i}C_{i}^{q}$.

Our problem is well-known to be strongly NP-hard by a simple reduction from
3-partition. On the other hand, a classic result by Alon et al. [1] shows that
it admits a polynomial time approximation scheme (PTAS) with running time
$f(1/\epsilon)+n^{O(1)}$, where $f(1/\epsilon)$ is doubly exponential in
$1/\epsilon$. Very recently, improved running times have been obtained for
$P||\sum_{i}C_{i}^{q}$ and other closely related load balancing problems.
Particularly, for a variety of objective functions, which include both
$\sum_{i}C_{i}^{q}$ and the makespan objective $C_{\max}=\max_{i}C_{i}$,
Jansen et al. [20] show that the problem admits a PTAS with a running time of
$2^{\tilde{O}(1/\epsilon)}+\tilde{O}(n)$. On the negative side, for the
makespan objective, Chen et al. [7] show that such a running time is
essentially best possible under the exponential time hypothesis (ETH).
However, the lower bound does not hold for other objectives, including
$P||\sum_{i}C_{i}^{q}$, leaving open the possibility for improved running
times. In this paper, we study this question and explore the surprisingly rich
complexity landscape of $P||\sum_{i}C_{i}^{q}$ in the context of approximation
schemes.

Contribution Overview. We study the complexity landscape of approximation
schemes for $P||\sum_{i}C_{i}^{q}$. Consider some strongly NP-hard
optimization problem whose optimal value $\text{OPT}(I)$ is integral and upper
bounded by $\text{poly}(|I|_{u})$ for any instance $I$, where $|I|_{u}$ is the
input size written in unary. This implies that the problem does not admit a
fully polynomial-time approximation scheme (FPTAS) unless P=NP [11]. In the
majority of cases, for such problems the literature presents PTASs with
running time at least as large as $2^{\Omega(1/\epsilon)}+n^{O(1)}$, that is,
the dependency on $1/\epsilon$ is exponential. We show that
$P||\sum_{i}C_{i}^{q}$ does not fall into this case, and a running time
subexponential on $1/\epsilon$ is achievable. More precisely, we give a PTAS
with a running time of $2^{\tilde{O}(\sqrt{1/\epsilon})}+n^{O(1)}$. On the
other hand, we show that this running time is essentially tight, by providing
an almost matching lower bound under ETH. That is, we show that ETH rules out
a PTAS of running time $2^{O(({1/\epsilon})^{1/2-\delta})}+n^{O(1)}$ for any
$\delta>0$. We are not aware of any other PTAS for a strongly NP-hard problem
with such a tight subexponential behavior on $1/\varepsilon$.

Besides the results above, we give a fine-grained study on the upper and lower
bounds of the running time of a PTAS for $P||\sum_{i}C_{i}^{q}$. First of all,
we notice that our lower bound only holds for a small range of values of $m$,
depending on $\epsilon$. Moreover, for some other values, we can circumvent
the lower bound and obtain improved running times. More precisely, the lower
bound only holds when $m=\Theta(\sqrt{1/\epsilon})$. Quite surprisingly, when
$m$ is larger, namely $m=\Omega(1/\epsilon\log^{2}(1/\epsilon))$, an algorithm
that runs polynomially in $1/\epsilon$ exists, despite the problem being
strongly NP-hard in general and our stronger lower bound. If
$m=O(\sqrt{1/\epsilon})$ we can use a PTAS with running time
$(1/\epsilon)^{O(m)}$, which also breaks the lower bound for
$m=o(\sqrt{1/\epsilon})$. See Figure 1 for a depiction of our results. It
remains an open problem to obtain tight running times when
$m=\Theta({(1/\epsilon)^{\theta}})$ for $\theta\in(1/2,1]$.

Figure 1: Complexity landscape of $P||\sum_{i}C_{i}^{q}$. The time axis
specifies the dependency of the running time with respect to $1/\epsilon$. A
term of $n^{O(1)}$ needs to be added in the running of each algorithm.

Technical Contribution. Our main technical contribution lies in the lower
bound proof. For this, we give a fine-grained reduction from a variant of
Max3SAT to $P||\sum_{i}C_{i}^{q}$. To do so, we convert a set of clauses to a
set of jobs. We enforce that two jobs which represent variables in the same
clause are scheduled together in some carefully constructed gap (i.e., slot)
of a given size. For such a construction, it is imperative to use pairs of
numbers with unique sums, to guarantee that only these two jobs fit this gap.
Hence, our construction is tightly related to Sidon sets and Salem–Spencer
sets (also called progression-free sets), both of which have been studied
extensively in number theory (see, e.g., [10, 35, 33, 12]). A Sidon set
$S=\\{s_{1},s_{2},\ldots,s_{n}\\}$ is a subset of natural numbers where all
pairwise sums $s_{i}+s_{j}$, for $i\leq j$, are distinct. That is,
$s_{i}+s_{j}=s_{i^{\prime}}+s_{j^{\prime}}$ implies
$\\{i,j\\}=\\{i^{\prime},j^{\prime}\\}$. A weaker notion is that of a Salem-
Spencer set, that is, a set $S=\\{s_{1},s_{2},\cdots,s_{n}\\}$ with no
cardinality 3 progression, i.e., no triplet
$(i,j,k)\in\mathbb{Z}_{n}:=\\{1,2,\cdots,n\\}$ of pairwise different numbers
satisfies $s_{i}-s_{j}=s_{k}-s_{i}$. In other words, if $s_{j}+s_{k}=2s_{i}$
then $i=j=k$. Our lower bound could be proved by adapting known techniques if
a Sidon set $S\subseteq\mathbb{Z}_{N}$ (where
$\mathbb{Z}_{N}:=\\{1,2,\cdots,N\\}$) with cardinality $n$ exists for
$N=n^{1+o(1)}$. Unfortunately, this is impossible, as Erdös and Turán [10]
show that the cardinality of a Sidon set with $n$ elements requires
$N=\Omega(n^{2})$. We can circumvent this negative result by requiring only
some pairs of numbers to have a unique sum, where these pairs correspond to
the clauses in the given Max3SAT instance. Towards this, we first transform
the given Max3SAT instance, with variables $z_{j}$ for $j\in\mathbb{Z}_{n}$,
into a special structure such that all clauses can be divided into two
disjoint subsets $C_{1}$ and $C_{2}$: $C_{1}$ consists of clauses
$cl_{2},cl_{5},\cdots,cl_{n-1}$ such that $cl_{\ell}=(w_{\ell-1}\vee
w_{\ell}\vee w_{\ell+1})$, where $w_{j}\in\\{z_{j},\neg z_{j}\\}$ for all $j$;
and $C_{2}$ consists of clauses
$cl_{1}^{\prime},cl_{2}^{\prime},\cdots,cl_{n}^{\prime}$ such that
$cl_{\ell}^{\prime}=(z_{\ell}\oplus\neg z_{\tau(\ell)})$, where $\tau$ is a
permutation of $\mathbb{Z}_{n}$ and $\oplus$ is the XOR operation (see Section
3.1 for details). For $C_{1}$, we construct a set of numbers
$\\{\sigma(1),\sigma(2),\cdots,\sigma(n)\\}$ such that every adjacent sum
$\sigma(i)+\sigma(i+1)$ is unique, and this will be achieved through extending
a known construction of Salem-Spencer sets (Lemma 6). For $C_{2}$, we extend
the construction to additionally require that the $\sigma(i)$’s we construct
admit a linked unique sum. That is, there exists a subset of numbers
$E_{i}=\\{e_{i,1},e_{i,2},\ldots,e_{i,\omega}\\}\subseteq\mathbb{Z}_{n^{1+o(1)}}$
for every $i\in\mathbb{Z}_{n}$ such that $E_{i}\cap E_{i^{\prime}}=\emptyset$
for any $i^{\prime}\neq i$, and the sum of each pair
$\sigma(i)+e_{i,1},e_{i,1}+e_{i,2},\cdots,e_{i,\omega-1}+e_{i,\omega},e_{i,\omega}+\sigma(\tau(i))$
is unique in the sense that no other pairs in $S\cup E$ sum up to the same
value, where $E=\bigcup_{i=1}^{n}E_{i}$. Note that a linked unique sum is a
weaker notion than Sidon or Salem-Spencer, as for these there is no auxiliary
set $E$. Nevertheless, the property of linked unique sum is strong enough for
our reduction. The construction of the auxiliary set $E$ relies on further
extending our technique for constructing unique adjacent sums, together with a
group theoretic lemma that allows an “orthogonal” decomposition of the
permutation $\tau$ (Lemma 8). Our results may be of separate interest for
constructing fine-grained lower bounds on approximation or parameterized
algorithms for other problems.

Another crucial observation, which may also be of independent interest, is a
structural result needed for our PTAS with running time
$2^{\tilde{O}(\sqrt{1/\epsilon})}+n^{O(1)}$ (see Section 2.1). For many
objective functions (like $C_{\max}$) we can round the processing times to
powers of $1+\epsilon$ in order to bound the overall loss by a factor of
$1+O(\epsilon)$. We observe that for minimizing $\sum_{i}C_{i}^{q}$ it is
possible to consider a coarser grouping of jobs into sizes within a
$(1+\sqrt{\epsilon})$ factor. Broadly speaking, by imposing extra structure to
a near-optimal solution, we can use a Taylor expansion to bound the error, and
notice that the linear term of the polynomial expansion cancels out. This
leaves us only with the quadratic (and lower order) terms. This observation
might translate to other problems with $\ell_{q}$-norm objective, and even
other min-sum cost functions.

Related Work. Load balancing problems are fundamental in computer science and
have been studied extensively in the literature. In particular, the first PTAS
for $P||C_{\max}$ dates back to the 80’s [15] and there is a long history of
improvements on the running time for various identical machine scheduling
problems, including $P||C_{\max}$, $P||\sum_{i}C_{i}^{q}$,
$P||\sum_{j}w_{j}C_{j}$, etc.; see, e.g., [27, 2, 14, 37, 19, 20]. Recently,
more general objective functions based on arbitrary norms have been considered
[16]. Parameterized algorithms for scheduling problems have also been studied
extensively (see, e.g. [22, 31, 32, 25, 8]).

The exponential time hypothesis (ETH) is a widely accepted complexity
assumption introduced by Impagliazzo et al. [18, 17], which can be used to
obtain lower bounds on the running time of algorithms for various problems
(see, e.g., [28] for a survey). In 2014, Chen et al. [7] provide a concrete
lower bound on the running time of a PTAS for $P||C_{\max}$ under ETH. Later,
Jansen et al. [20] give a PTAS with running time
$2^{\tilde{O}(1/\epsilon)}+n^{O(1)}$ for $P||C_{\max}$, which almost matches
the lower bound.

Despite PTASs having been established for a variety of optimization problems,
much less is known regarding lower bounds on their running time. In addition
to $P||C_{\max}$, mentioned above, other well-known examples include multiple
knapsack [21], planar vertex cover, planar dominating set, and planar
traveling salesperson [29]. Interestingly, all of these lower bounds have an
almost linear dependency on $1/\epsilon$ in the exponent, which essentially
matches the best-known PTAS. Generally, Chen et al. [6] proved that if the
problem, parameterized by $1/\epsilon$, is W[1]-hard under a linear FPT
reduction, then there is no PTAS with $f(1/\epsilon)|I|^{o(1/\epsilon)}$
running time for an arbitrary computable function $f$, assuming all problems
in SNP cannot be solved in sub-exponential time. We are not aware of a PTAS
whose running time is subexponential in $1/\epsilon$, either for scheduling or
other strongly NP-hard problems.

Unlike approximation algorithms, subexponential running times on a parameter
have been observed in the field of parameterized algorithms and have received
significant attention. In particular, a variety of optimization problems in
planar graphs admit a fixed parameter tractable (FPT) algorithm that is
subexponential in the parameter, including, e.g., independent set [9],
dominating set [9], and multiway cut [24, 30, 36]. Note that, on the other
hand, a subexponential PTAS was ruled out for the planar dominating set
problem [29].

##  2 Approximation schemes

The goal of this section is to prove the following theorem.

######  Theorem 1.

For any sufficiently small $\epsilon>0$, there exists an algorithm that
outputs a $(1+\epsilon)$-approximate solution for the scheduling problem
$P||\sum_{i}C_{i}^{q}$ within $2^{\tilde{O}(\sqrt{1/\epsilon})}+n^{O(1)}$
time. More specifically, there exists a:

  * •

$(1+\epsilon)$-approximation algorithm AL1 that runs in time
$(1/\epsilon)^{O(m)}+n^{O(1)}$ for $m=O(\sqrt{1/\epsilon})$;

  * •

$(1+\epsilon)$-approximation algorithm AL2 that runs in time
$2^{\tilde{O}(\sqrt{1/\epsilon})}+n^{O(1)}$ for $m=(1/\epsilon)^{O(1)}$;

  * •

$(1+\epsilon)$-approximation algorithm AL3 that runs in time
$(1/\epsilon)^{O(1)}+n^{O(1)}$ for $m=\Omega(1/\epsilon\log^{2}(1/\epsilon))$.

In particular, for a sufficiently small $\epsilon$, we may run AL1 for
$m\leq\sqrt{1/\epsilon}$, run AL2 for $\sqrt{1/\epsilon}<m\leq
1/\epsilon^{2}$, and run AL3 for $m\geq 1/\epsilon^{2}$. This guarantees a
$2^{\tilde{O}(\sqrt{1/\epsilon})}+n^{O(1)}$ time algorithm for all values of
$m$ and $1/\epsilon$.

We remark that standard techniques round the processing time of a job to some
multiple of $1+\epsilon$, yielding an instance with $\tilde{O}(1/\epsilon)$
different types of jobs. However, such rounded instance cannot be solved to
optimality in time $2^{(1/\epsilon)^{1-\delta}}+n^{O(1)}$ for any constant
$\delta>0$ [7]. Hence, we need a new approach for Theorem 1.

We now give a brief overview of the proof of Theorem 1. Algorithm AL1 is based
on a standard dynamic programming, given in Appendix A.1. Algorithm AL2 is
based on an new observation (Lemma 3) which shows that we can classify
processing times on intervals of the form
$[\epsilon(1+\sqrt{\epsilon})^{h-1},\epsilon(1+\sqrt{\epsilon})^{h})$ for an
integer $h$. After preprocessing the instance (Lemma 1), we can focus on only
$\tilde{O}(1/\sqrt{\epsilon})$ such intervals. We show that there exists a
near-optimal solution where jobs are scheduled in an ordered way following the
mentioned classification. This algorithm is described in Section 2.1.
Algorithm AL3 (see Appendix A.3) is based on modifying the famous algorithm
for the bin packing problem by Karmarkar and Karp [23].

All the three algorithms will operate on a scheduling instance that is well-
structured, as implied by the following lemma. The structure can be achieved
through standard techniques, namely scaling and grouping of small jobs, see,
e.g., [2]. For an instance $I$, we denote by $\text{size}(I)$ the total
processing time of jobs in $I$, and by $m(I)$ the number of machines.

######  Lemma 1 (Alon et al. [2]).

For any sufficiently small $\epsilon>0$, given an arbitrary instance $I_{0}$
of $P||\sum_{i}C_{i}^{q}$, we can transform in linear time $I_{0}$ into a
well-structured rounded instance $I$ with less or equal number of jobs and
less or equal number of machines, that satisfies:

  * •

$\text{size}(I)=m(I)$;

  * •

the processing time of each job in $I$ belongs to $[\epsilon,1]$;

  * •

there exists an optimal solution for $I$ such that the load of each machine
belongs to $[1/2,2]$.

Furthermore, any $(1+\epsilon)$-approximation solution for $I$ can be
transformed into an $(1+O(\epsilon))$-approximation solution for $I_{0}$ in
linear time.

In the following, we focus exclusively on the instance after the
preprocessing. It is worth mentioning that for non-integral values of $q$, the
objective function can be irrational even for rational processing times. For
obtaining a PTAS this is however not a problem, as computing the objective
function up to an additive error of $\epsilon/\text{poly}(n)$ suffices for our
results. In what follows we omit this technicality, and assume that we can
compute the objective function without error.

###  2.1 Algorithm 2

In this subsection, we describe and analyze algorithm AL2.

######  Lemma 2.

Consider an instance after the preprocessing of Lemma 1. For any $\epsilon>0$,
there exists an algorithm AL2 that outputs a $(1+O(\epsilon))$-approximation
solution for $P||\sum_{i}C_{i}^{q}$ with $m^{\tilde{O}(1/\sqrt{\epsilon})}$
running time.

We know there exists an optimal solution
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}^{*}$ where the load of each
machine belongs to $[1/2,2]$. Let $L_{i}^{*}$ be the load of machine $i$ in
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}^{*}$ where $1/2\leq
L_{i}^{*}\leq 2$. Without loss of generality we further assume that
$L_{1}^{*}\leq L_{2}^{*}\leq\cdots\leq L_{m}^{*}$. For some integer $h\geq 1$,
let $\mathcal{G}_{h}$ be the set of jobs whose processing time lies in
$[\epsilon(1+\sqrt{\epsilon})^{h-1},\epsilon(1+\sqrt{\epsilon})^{h})$. Given
that $\epsilon\leq p_{j}\leq 1$, every job belongs to some set
$\mathcal{G}_{h}$ for $h\in\\{1,\ldots,\tau\\}$, where
$\tau=\tilde{O}(1/\sqrt{\epsilon})$. For simplicity, we call a job in
$\mathcal{G}_{h}$ a $\mathcal{G}_{h}$-job. The following structural result
contains the key observation for the existence of a PTAS with subexponential
time.

######  Lemma 3.

There exists a feasible solution $\hat{x}$ satisfying: i) its objective value
is at most $(1+O(\epsilon))OPT$, and ii) the machines can be ordered from $1$
to $m$ such that for any $1\leq i\leq m-1$ and $h$, the processing time of
every $\mathcal{G}_{h}$-job on machine $i+1$ is at most the processing time of
any $\mathcal{G}_{h}$-job on machine $i$.

###### Proof.

Given an optimal solution $x^{*}$, we construct $\hat{x}$ as follows. For
machine $m$, we replace all $\mathcal{G}_{h}$-jobs with the same number of the
smallest $\mathcal{G}_{h}$-jobs. For machine $m-1$, we replace all
$\mathcal{G}_{h}$-jobs with the same number of the remaining smallest
$\mathcal{G}_{h}$-jobs, etc. Eventually, every $\mathcal{G}_{h}$-job on
machine $i+1$ is no greater than any $\mathcal{G}_{h}$-job on machine $i$. Let
$\hat{L}_{i}=L_{i}^{*}+\Delta_{i}$ be the new load of machine $i$.

By the definition of $\mathcal{G}_{h}$, we know that the largest
$\mathcal{G}_{h}$-job has a processing time at most $1+\sqrt{\epsilon}$ times
the smallest one. This implies that
$L_{i}^{*}/(1+\sqrt{\epsilon})\leq\hat{L}_{i}\leq(1+\sqrt{\epsilon})L_{i}^{*}$,
and hence $|\Delta_{i}|\leq\sqrt{\epsilon}L_{i}^{*}\leq 2\sqrt{\epsilon}$. In
order to bound the objective function, first write
$\sum_{i=1}^{m}(L_{i}^{*}+\Delta_{i})^{q}=\sum_{i=1}^{m}{L_{i}^{*}}^{q}(1+\Delta_{i}/L_{i}^{*})^{q}$.
Using a Taylor expansion of order 1 on the function $(1+x)^{q}$ around $x=0$,
we obtain that for some $0\leq\xi_{i}\leq\Delta_{i}/L_{i}^{*}\leq 1$,

$\displaystyle\sum_{i=1}^{m}(L_{i}^{*}+\Delta_{i})^{q}$
$\displaystyle=\sum_{i=1}^{m}{L_{i}^{*}}^{q}\left(1+q\frac{\Delta_{i}}{L_{i}^{*}}+\frac{q(q-1)}{2}(1+\xi_{i})^{q-2}\left(\frac{\Delta_{i}}{L_{i}^{*}}\right)^{2}\right)$
$\displaystyle\leq(1+O(\epsilon))\sum_{i=1}^{m}{L_{i}^{*}}^{q}+q\sum_{i=1}^{m}\Delta_{i}{L_{i}^{*}}^{q-1}$
$\displaystyle=(1+O(\epsilon))OPT+q{L_{1}^{*}}^{q-1}\sum_{k=1}^{m}\Delta_{k}+q\sum_{i=2}^{m}\left[({L_{i}^{*}}^{q-1}-{L_{i-1}^{*}}^{q-1})\sum_{k=i}^{m}\Delta_{k}\right]$
$\displaystyle\leq(1+O(\epsilon))OPT.$

The last equality uses Abel’s transformation (summation by parts). The last
inequality follows since, for each $i$, it holds that
$\sum_{k=i}^{m}\Delta_{k}\leq 0$, as the last $m-i$ machines received the
smallest $\mathcal{G}_{h}$-jobs for each $h$. ∎

Exploiting the ordering of the jobs and machines given by Lemma 3, we are able
to develop a dynamic programming based algorithm to prove Lemma 2, see
Appendix A.2.

##  3 Lower Bound

In this section, we will prove the following theorem.

######  Theorem 2.

Let $q>1$ be an arbitrary constant. Assuming ETH, there is no PTAS for
$P||\sum_{i}C_{i}^{q}$ that runs in
$2^{O((1/\varepsilon)^{1/2-\delta})}+n^{O(1)}$ time for any constant
$\delta>0$.

For the proof we give a fine-grained reduction from a variant of Max3SAT,
called 3SAT′ (which we elaborate in the following subsection), to
$P||\sum_{i}C_{i}^{q}$.

###  3.1 3SAT′ \- Max3SAT with a Special Structure

We study a variant of 3SAT, which we call 3SAT′, whose instances have the
following structure: There are $n$ variables $z_{1},\ldots,z_{n}$, where $n$
is a multiple of $3$. There are $4n/3$ clauses, such that the set of clauses
can be divided into two disjoint sets $C_{1}$ and $C_{2}$ such that:

  * •

In $C_{1}$, every clause is a disjunction (OR operator) of three literals. For
each variable $z_{i}$, exactly one literal in $C_{1}$ belongs to
$\\{z_{i},\neg z_{i}\\}$.

  * •

In $C_{2}$, every clause is of the form $z_{i}\oplus\neg z_{k}$, where
$\oplus$ denotes the XOR operator. Also, for every variable $z_{i}$, each
literal $z_{i}$ and $\neg z_{i}$ appears exactly once within $C_{2}$.

For example, $C_{1}=\\{(z_{1}\vee\neg z_{2}\vee z_{3})\\}$ and
$C_{2}=\\{(z_{1}\oplus\neg z_{2}),(z_{2}\oplus\neg z_{3}),(z_{3}\oplus\neg
z_{1})\\}$ defines a 3SAT′ instance for $n=3$. Let
$cl_{2},cl_{3},\cdots,cl_{n-1}$ be the clauses in $C_{1}$. By re-indexing we
can assume that $cl_{\ell}$ is of the form $(w_{\ell-1}\vee w_{\ell}\vee
w_{\ell+1})$, where $w_{j}\in\\{z_{j},\neg z_{j}\\}$ for all $j$. Also notice
that $|C_{1}|=n/3$ and $|C_{2}|=n$. Since every literal appears exactly once
in $C_{2}$, we define a permutation
$\tau:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ (i.e. a bijection) such that
$\tau(i)=k$ for each $(z_{i}\oplus\neg z_{k})\in C_{2}$.

Similarly to 3SAT, it is also difficult to distinguish instances of 3SAT′
where almost all clauses are satisfiable and instances where at most certain
fraction of the clauses can be satisfied, as implied by the following lemma.
See Appendix B for its proof.

######  Lemma 4.

Assuming ETH, there exists a constant $\beta\in(0,1)$ such that for any
sufficiently small $\epsilon^{\prime},\delta>0$ there is no algorithm with
running time $2^{O(n^{1-\delta})}$ that distinguishes between instances of
3SAT$\,{}^{\prime}$ with $4n/3$ clauses where at least
$(1-\epsilon^{\prime})\cdot 4n/3$ clauses are satisfiable, from instances
where at most $(\beta+\epsilon^{\prime})\cdot 4n/3$ clauses are satisfiable.

###  3.2 Overview of the reduction

We now briefly describe the structure of the constructed scheduling instance.
The detailed reduction will be presented in Appendix F. We remark that the
high-level structure of the scheduling instance resembles the classical
reduction and that of [7]. New technical ingredients are in job processing
times, as we will elaborate in Section 3.3.

For an instance $I_{sat}$ of 3SAT′ with $n$ variables, we construct the
following 6 kinds of jobs:

$\bullet$ Variable jobs: For each positive (or negative, resp.) literal, say,
$z_{i}$ (or $\neg z_{i}$, resp.), two pairs of variable jobs
$V_{i,+,1}^{\rho}$ and $V_{i,+,2}^{\rho}$ (or $V_{i,-,1}^{\rho}$ and
$V_{i,-,2}^{\rho}$, resp.) are constructed where $\rho\in\\{T,F\\}$. In total,
we construct 4 jobs for each (positive or negative) literal, i.e., 8 jobs for
each variable.

$\bullet$ Clause jobs: For each clause $cl_{\ell}$ of $C_{1}$, one clause job
$\textrm{CL}^{T}_{\ell}$ and two copies of clause job $\textrm{CL}_{\ell}^{F}$
are constructed. Recall that $|C_{1}|=n/3$, we construct $n$ clause jobs.

$\bullet$ Truth-assignment jobs, link jobs and dummy jobs: These three kinds
of jobs will be created suitably so that the conditions below (CO1 to CO4) are
satisfied.

$\bullet$ Gap jobs: Let $Q$ be a target makespan. We construct $\tilde{O}(n)$
gap jobs and the same number of machines to create gaps. Roughly speaking,
every feasible schedule whose objective value is not too large will have one
gap job on each machine, leaving a gap that must be filled up such that the
load of the machine is exactly $Q$. We will create 4 kinds of gaps (incurred
by gap jobs) satisfying the following conditions:

  * $\bullet$ CO1.

Variable-Truth gaps. To fill up these gaps, for any $i$ either
$V_{i,+,1}^{F}$, $V_{i,+,2}^{F}$, $V_{i,-,1}^{T}$, $V_{i,-,2}^{T}$, or
$V_{i,+,1}^{T}$, $V_{i,+,2}^{T}$, $V_{i,-,1}^{F}$, $V_{i,-,2}^{F}$ are used.
Truth-assignment jobs are created for this purpose.

  * $\bullet$ CO2.

Variable-Clause-Dummy gaps. For each clause $cl_{\ell}\in C_{1}$, there are
three variable-clause-dummy gaps. If the positive (or negative, resp.) literal
$z_{i}$ (or $\neg z_{i}$, resp.) is in $cl_{\ell}\in C_{1}$, then a variable-
clause-dummy gap is created so that it could only be filled up by
$\textrm{CL}_{\ell}^{\rho}$ and $V_{i,+,1}^{\rho^{\prime}}$ (or
$\textrm{CL}_{\ell}^{\rho}$ and $V_{i,-,1}^{\rho^{\prime}}$, resp.), where
$\rho,\rho^{\prime}\in\\{T,F\\}$, together with a dummy job. Further, the gap
ensures that $\textrm{CL}^{T}_{\ell}$ has to be scheduled with either
$V_{i,+,1}^{T}$ or $V_{i,-,1}^{T}$.

  * $\bullet$ CO3.

Variable-Link and Link-Link gaps. For each clause $(z_{i}\oplus\neg z_{k})\in
C_{2}$ we create a collection of Variable-Link and Link-Link gaps. To fill up
these gaps, either $V_{i,+,2}^{T}$ and $V_{k,-,2}^{F}$, or $V_{i,+,2}^{F}$ and
$V_{k,-,2}^{T}$ are used. Link jobs are created for this purpose (see Section
3.3 for more details on this construction).

  * $\bullet$ CO4.

Variable-Dummy gaps. Recall that 8 variable jobs are constructed for a
variable and only 7 of them are used for the 4 kinds of gaps above (either
$V_{i,+,1}^{\rho}$ or $V_{i,-,1}^{\rho}$ is left, where $\rho\in\\{T,F\\}$),
the remaining one together with a dummy job will be used to fill these gaps.

With this construction, it is not difficult to verify that if every gap is
filled exactly, $I_{sat}$ is satisfiable. To see why, if $V_{i,+,1}^{F}$,
$V_{i,+,2}^{F}$, $V_{i,-,1}^{T}$, $V_{i,-,2}^{T}$ are used in the variable-
truth gaps, then we let variable $z_{i}$ be true, otherwise we let it be
false. For any clause of $C_{1}$, say, $cl_{\ell}$, there is one
$\textrm{CL}_{\ell}^{T}$ and it must be scheduled with a true variable job,
say, $V_{i,+,1}^{T}$ if $z_{i}$ is a literal in $cl_{\ell}$ (or
$V_{i,-,1}^{T}$ if $\neg z_{i}$ is a literal in $cl_{\ell}$). If
$V_{i,+,1}^{T}$ (or $V_{i,-,1}^{T}$, resp.) is scheduled with
$\textrm{CL}_{\ell}^{T}$, then the positive (or negative, resp.) literal
$z_{i}$ (or $\neg z_{i}$, resp.) is in $cl_{\ell}$. Meanwhile the variable
$z_{i}$ is true (or false, resp.) since otherwise $V_{i,+,1}^{T}$ (or
$v_{i,-,1}^{T}$,resp.) are used to fill variable-truth gaps. Thus clause
$cl_{\ell}$ is satisfied. For any clause of $C_{2}$, say, $(z_{i}\oplus\neg
z_{k})$, if $V_{i,+,2}^{T}$ and $V_{k,-,2}^{F}$ (or $V_{i,+,2}^{F}$ and
$V_{k,-,2}^{T}$, resp.) are used to fill up the corresponding variable-link
and link-link gaps, then variables $z_{i}$ and $z_{k}$ are both true (false,
resp.) since otherwise $V_{i,+,2}^{T}$ and $V_{k,-,2}^{F}$ ($V_{i,+,2}^{F}$
and $V_{k,-,2}^{T}$, resp.) would have been used to fill up the variable-truth
gaps. Hence, $(z_{i}\oplus\neg z_{k})$ is satisfied. Similarly, if $I_{sat}$
is satisfiable, then every gap can be filled up.

Chen et al. [7] provided a reduction that meets the above requirement with job
processing times, and hence the target value $Q$, being $O(n^{1+\delta})$ for
arbitrarily small constant $\delta>0$. Unfortunately, using this reduction we
can only deduce a weaker lower bound of $2^{O((1/\epsilon)^{1/3-\delta})}$
(see Appendix C for a detailed discussion). For our purpose, we need to design
job processing times to achieve a stronger ratio-preserving property, as we
elaborate below.

Recall that we are given an instance of 3SAT′ with $n$ variables and $4n/3$
clauses. For a given solution, we say a machine is good if its load is exactly
$Q$ (in which case there is exactly one gap job on it and the gap is filled up
exactly), and is bad otherwise (in which case its load is at least $Q+1/2$ or
at most $Q-1/2$). Our scheduling instance will additionally satisfy the
following properties:

  * i.

There are $m=\tilde{O}(n)$ machines and the target makespan is
$Q=\tilde{O}(n)$.

  * ii.

Each processing time is a multiple of $1/2$ and the total job processing time
equals $mQ$.

  * iii.

Conditions CO1 to CO4 are satisfied. Additionally, the following ratio-
preserving properties are satisfied. For any $\vartheta\in(0,1)$ it holds
that:

    * –

If the 3SAT′ instance admits a truth assignment where at most $\vartheta n$
clauses are not satisfied, then the constructed scheduling instance admits a
feasible solution with at most $\vartheta_{1}n$ bad machines, for some
$\vartheta_{1}=\Theta(\vartheta)$. In particular, the load of these bad
machines is $Q+1$ or $Q-1$.

    * –

If any truth assignment for the 3SAT′ instance has at least $\vartheta n$
clauses that are not satisfied, then in any feasible schedule of the
constructed scheduling instance there are at least $\vartheta_{2}n$ bad
machines, for some $\vartheta_{2}=\Theta(\vartheta)$.

Before giving more details of the construction, we briefly argue that an
instance satisfying properties (i)-(iii) implies Theorem 2.

###### Proof Idea (Theorem 2).

Take $q=2$ for simplicity. We assume by contradiction that there exist some
sufficiently small $\delta>0$, such that for any $\epsilon>0$ there is an
$(1+\epsilon)$-approximation algorithm with running time
$2^{O((1/\epsilon)^{1/2-\delta})}+n^{O(1)}$. Let $\beta\in(0,1)$ be a
constant, and let $\epsilon^{\prime},\delta>0$ be sufficiently small numbers,
as in Lemma 4. We show that, for an appropriately chosen $\epsilon$, the PTAS
can be used to distinguish, in time $2^{n^{1-\delta}}$, 3SAT′ instances where
at least $(1-\epsilon^{\prime})\cdot 4n/3$ clauses are satisfiable, from 3SAT′
instances where at most $(\beta+\epsilon^{\prime})\cdot 4n/3$ clauses are
satisfiable, contradicting ETH by Lemma 4. Indeed, we first observe that every
bad machine will cause the objective value to increase by at least some fixed
constant. A straightforward but crucial observation follows from the fact
that, for load balancing problems, the total difference from the average load
is 0. That is, if $C_{i}=Q+\Delta_{i}$, then the cost is

$\displaystyle\sum_{i=1}^{m}C_{i}^{2}=\sum_{i=1}^{m}(Q+\Delta_{i})^{2}=\sum_{i=1}^{m}(Q^{2}+2T\Delta_{i}+\Delta_{i}^{2})=mQ^{2}+\sum_{i=1}^{m}\Delta_{i}^{2},$
(1)

where the last equality follows as $\sum_{i}\Delta_{i}=0$ (for general $q>1$,
a similar statement follows from a Taylor expansion, as in the proof of Lemma
3). Consequently, if at least $(1-\epsilon^{\prime})\cdot 4n/3$ clauses of
$I_{sat}$ are satisfiable, then at most $\Theta(\epsilon^{\prime}n)$ machines
will have a load of either $Q+1$ or $Q-1$, and hence the optimal objective
value of the constructed scheduling instance is at most
$mQ^{2}+\Theta(\epsilon^{\prime}n)$ by Eq (1). On the other hand, if at most
$(\beta+\epsilon^{\prime})\cdot 4n/3$ clauses of $I_{sat}$ are satisfiable for
some constant $\beta<1$, then $\Delta_{i}\geq 1/2$ for at least
$\Theta((1-\beta-\epsilon^{\prime})n)$ machines. By Eq (1) the optimal
objective value of the constructed scheduling instance is at least
$mQ^{2}+\Theta((1-\beta-\epsilon^{\prime})n)=mQ^{2}+\Theta(n)$ (see Lemma 41
for the detailed computation). Now we apply the efficient PTAS with
$\epsilon=\Theta(\frac{n^{1-\delta}}{mQ^{2}})\approx\Theta(1/n^{2+\delta})$.
Given the fact that $mQ^{2}\epsilon=\Theta(n^{1-\delta})$, if at least
$(1-\epsilon^{\prime})\cdot 4n/3$ clauses of $I_{sat}$ are satisfiable, then
the PTAS should return a schedule with objective value at most
$mQ^{2}+\Theta(\epsilon^{\prime}n)+\Theta(n^{1-\delta})=mQ^{2}+\Theta(\epsilon^{\prime}n)$.
Otherwise, the PTAS returns a schedule with objective value at least
$mQ^{2}+\Theta(n)$. Theorem 2 follows as our PTAS has a running time of
$2^{O((1/\epsilon)^{1/2-\delta})}+n^{O(1)}\leq 2^{O(n^{1-\delta})}$. ∎

Remark. One can verify that if $Q$ is larger, e.g., $Q=\Theta(n^{2})$, then
the above argument only rules out a PTAS of running time
$2^{O((1/\epsilon)^{1/4-\delta})}$. Hence, simultaneously enforcing the ratio-
preserving property while having $Q=\tilde{O}(n)$ is the main technical
challenge, which we overcome with our new number-theoretic constructions, as
we elaborate in the following.

The rest of the paper is organized as follows. In Section 3.3 we give an
overview of the main technical ingredients for the construction of the
processing times in our reduction. We also motivate our number theoretical
constructions, which are specified in Section 3.4. In Appendix F we present
the complete reduction. In Appendix G we show its correctness and conclude
Theorem 2.

###  3.3 Defining Processing times: Main Techniques

To illustrate the main technical ingredient, in the following part of this
subsection we will focus on conditions CO2 and CO3 while ignoring the other
conditions (which can be handled using the techniques for CO2 and CO3). Recall
that our goal is to create suitable gap jobs that can only be filled up by
specific jobs.

We can view each job, say, $V_{i,+,1}^{T}$, as a combination of three
components – the type-component $V_{\cdot,+,1}$ (indexed by $i$), the index-
component $i$, and the $T/F$-component $T$. Ignoring dummy jobs for
simplicity, conditions CO2 and CO3 involve 5 different type-components,
including $V_{\cdot,+,1}$, $V_{\cdot,+,2}$ $V_{\cdot,-,1}$ $V_{\cdot,-,2}$ and
$\textrm{CL}_{\cdot}$. Denote by $s(\cdot)$ the processing time of a job. We
can define the processing time of a job into a summation of three terms
corresponding to components, e.g.,
$s(V_{i,+,1}^{T})=\mu(V_{\cdot,+,1})+\sigma(i)+\eta(T)$, where the functions
$\mu,\sigma,\eta$ map the type-component, index-component and T/F-component of
a job to some positive integers. Now the question becomes: how can we define
functions $\mu,\sigma,\eta$ such that from their sum, e.g.,
$\mu(V_{\cdot,+,1})+\mu(\textrm{CL}_{\cdot})+\sigma(i)+\sigma(\ell)+\eta(T)+\eta(F)$,
we can conclude that it can only be added up by $s(V_{i^{\prime},+,1}^{\rho})$
and $s(\textrm{CL}_{\ell^{\prime}}^{\rho^{\prime}})$, where
$\\{i^{\prime},\ell^{\prime}\\}=\\{i,\ell\\}$ and
$\\{\rho,\rho^{\prime}\\}=\\{T,F\\}$. Notice that there are only a constant
number of different type-components and T/F-components, it is thus easy to
define $\mu$ and $\eta$. For example, let $\sigma_{max}$ be a sufficiently
large value that exceeds the maximal value of $\sigma$ and $\eta$, and define
$\mu(V_{\cdot,+,1}),\mu(V_{\cdot,+,2}),\mu(V_{\cdot,-,1}),\mu(V_{\cdot,-,2}),\mu(\textrm{CL}_{\cdot})$
to be
$10^{5}\sigma_{max},10^{4}\sigma_{max},10^{3}\sigma_{max},10^{2}\sigma_{max},10\sigma_{max}$,
then from the sum $\mu(V_{\cdot,+,1})+\mu(\textrm{CL}_{\cdot})$ it is very
easy to identify the type-components of two jobs.

The main difficulty lies in the function $\sigma$ as we require job processing
times to be $\tilde{O}(n)$, whereas $\sigma$ must map $[n]$ to
$[\tilde{O}(n)]$ such that

$\displaystyle\sigma(i)+\sigma(\ell)=\sigma(i^{\prime})+\sigma(\ell^{\prime})\implies\\{i,\ell\\}=\\{i^{\prime},\ell^{\prime}\\}.$
(2)

In other words, we require the sum $\sigma(i)+\sigma(\ell)$ to be unique among
the sums of all possible pairs $(i,\ell)$. Recall the special structure of
3SAT′, where each clause $cl_{\ell}\in C_{1}$ is of the form $(w_{\ell-1}\vee
w_{\ell}\vee w_{\ell+1})$ such that $w_{j}\in\\{z_{j},\neg z_{j}\\}$ for all
$j$. Hence, for condition CO2, it suffices to guarantee Eq (2) for
$i\in\\{\ell-1,\ell,\ell+1\\}$. Recall that a Salem-Spencer set is a set of
numbers where no three of which form an arithmetic progression, hence if we
let $\sigma$ map $[n]$ to a Salem-Spencer set of size $n$, Eq (2) always holds
for $\ell=i$. For our purpose, we need to generalize the construction of a
Salem-Spencer set such that in addition to $2\sigma(\ell)$, the sum of any two
adjacent numbers $\sigma(\ell)+\sigma(\ell+1)$ is also unique, as we show in
Lemma 6.

Condition CO3 is more complicated, as each clause of $C_{2}$ is of the form
$(z_{i}\oplus\neg z_{k})$ with $k=\tau(i)$, where the permutation $\tau$ is
arbitrary. If we consider the index-components of the two variable jobs
$V_{i,+,2}^{\rho}$ and $V_{k,-,2}^{\rho^{\prime}}$, we cannot guarantee that
$\sigma(i)+\sigma(k)=\sigma(i^{\prime})+\sigma(k^{\prime})$ implies
$\\{i,k\\}=\\{i^{\prime},k^{\prime}\\}$. Consider the following indirect
approach. Suppose for each $(z_{i}\oplus\neg z_{k})$ we can construct a pair
of jobs LN${}_{(i,k)}^{T}$ and LN${}_{(i,k)}^{F}$ (called link jobs), and
meanwhile create two gaps such that they must be filled up by
$V_{i,+,2}^{\rho_{1}}$ together with LN${}_{(i,k)}^{\rho_{1}^{\prime}}$, and
$V_{k,-,2}^{\rho_{2}}$ together with LN${}_{(i,k)}^{\rho_{2}^{\prime}}$
respectively, and furthermore,
$\\{\rho_{1},\rho_{1}^{\prime}\\}=\\{\rho_{2},\rho_{2}^{\prime}\\}=\\{T,F\\}$,
then we know that if both gaps are filled up, then either $V_{i,+,2}^{T}$ and
$V_{k,-,2}^{F}$, or $V_{i,+,2}^{F}$ and $V_{k,-,2}^{T}$ are used, which is
sufficient for condition CO3. Using this idea, instead of designing $\sigma$
such that the sum $\sigma(i)+\sigma(k)$ is unique, we seek to design $\sigma$
such the pair $(i,k)$ is “uniquely -linked” in the sense that there exists
some number $e_{i}=\tilde{O}(n)$ such that the sums $\sigma(i)+e_{i}$ and
$\sigma(k)+e_{i}$ are both unique among the sums of all pairs. Unfortunately,
requiring the uniqueness of $\sigma(i)+e_{i}$ and $\sigma(k)+e_{i}$ is still
too strong. We will show in Lemma 7 that for every $k=\tau(i)$ there exists a
sequence of $\omega=O(\frac{\log n}{\log\log n})$ numbers $e_{i,1}$,
$e_{i,2}$, $\ldots$, $e_{i,\omega}$ such that the sums $\sigma(i)+e_{i,1}$,
$e_{i,1}+e_{i,2}$, $\ldots$, $e_{i,\omega-1}+e_{i,\omega}$,
$e_{i,\omega}+\sigma(k)$ are all unique. Consequently, instead of creating one
pair of link jobs, we will create $\omega$ pairs of link jobs for each
$(z_{i}\oplus\neg z_{k})$, ensuring condition CO3.

###  3.4 Set of Integers with Unique Adjacent Sum and Linked Sum

In this section, we present our main technical contribution regarding the
number-theoretic constructions needed in our reduction.

Some notation. Recall that we let $\mathbb{Z}_{n}=\\{1,2,\cdots,n\\}$. All the
logarithms are taken with base $e$ unless stated otherwise. We will use
$\cdot$ in the subscript to denote an arbitrary index, e.g., $x_{\cdot}$
refers to $x_{i}$ for some $i$. We write vectors in boldface, e.g.
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}$. Vectors start with its
$0$-th coordinate. For any $\upsilon$-dimensional vector $\textstyle\bf c$,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[h]$ denotes its $h$-th
coordinate for $0\leq h\leq\upsilon-1$, and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}=\sum_{h=0}^{\upsilon-1}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[h]x^{h}$.

######  Lemma 5.

Let $N\in\mathbb{Z}^{+}$. There exists a subset
${\cal{S}}\subseteq\mathbb{Z}_{N}$ such that $|{\cal{S}}|\geq
N^{1-c_{0}\sqrt{\frac{1}{{\log N}}}}$ for some sufficiently large $c_{0}$ (in
particular, $c_{0}\geq 7$ suffices), and for any $y\in{\cal{S}}$ and $1\leq
h\leq 5$, the linear equation $h\cdot y=y_{1}+y_{2}+\cdots+y_{h}$ with
$y_{i}\in{\cal{S}}$ for all $i$ has a unique solution
$y_{1}=y_{2}=\cdots=y_{h}=y$.

The proof of Lemma 5 mainly utilizes the idea for constructing Salem–Spencer
sets [3] and can be found in Appendix D. In particular, we can show that
$|{\cal{S}}|\geq N^{1-7\sqrt{\frac{1}{{\log N}}}}$. For any integer
$d\in\mathbb{Z}^{+}$, we denote by ${\cal{S}}_{d}$ the subset of
$\mathbb{Z}_{d}$ that satisfies Lemma 5. Now we are ready to prove Lemma 6,
which is one of our two main number-theoretical results.

######  Lemma 6.

Let $N\in\mathbb{Z}^{+}$, $d=\lceil e^{(\sqrt{\log\log
N}+c)^{2}}\rceil=e^{{\mathcal{O}}(\sqrt{\log\log N})}\cdot\log N$ for some
sufficiently large $c$ ($c\geq 7$ suffices) and $x=5d+1$. There exists an
injection $\sigma:\mathbb{Z}_{N}\rightarrow\mathbb{Z}_{N^{\prime}}$ such that:

  * 1.

$N^{\prime}=N^{1+O(\frac{1}{\sqrt{\log\log N}})}$;

  * 2.

For any $i\in\mathbb{Z}_{N}$,
$\sigma(i)=\sum_{j=0}^{\gamma}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]x^{j}$ for some
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]\in{\cal{S}}_{d}$,
$0\leq j\leq\gamma$, where $\gamma=\lceil\frac{\log N}{\log\log
N}\rceil+O(\frac{\log N}{(\log\log N)^{3/2}})$;

  * 3.

For any $1\leq h\leq 5$ and $i\in\mathbb{Z}_{N}$, the equation
$h\cdot\sigma(i)=\sigma(i_{1})+\sigma(i_{2})+\cdots+\sigma(i_{h})$,
$i_{j}\in\mathbb{Z}_{N}$ has a unique solution $i_{1}=i_{2}=\cdots=i_{h}=i$.
Further, the equation
$h\cdot\sigma(i)=\sigma(i_{1})+\sigma(i_{2})+\cdots+\sigma(i_{k})$,
$i_{j}\in\mathbb{Z}_{N}$ has no feasible solution when $1\leq k<h$ or $h<k\leq
5$;

  * 4.

For any $i\leq N-1$, the linear equation
$\sigma(i)+\sigma(i+1)=\sigma(i_{1})+\sigma(i_{2})$, $i_{1}\leq i_{2}$ has a
unique solution $i_{1}=i$, $i_{2}=i+1$. Furthermore, the linear equation
$\sigma(i)+\sigma(i+1)=\sigma(i_{1})+\sigma(i_{2})+\cdots+\sigma(i_{k})$ has
no feasible solution when $k=1$ or $2<k\leq 5$.

###### Proof.

By Lemma 5 we know $|{\cal{S}}_{d}|\geq d^{1-c_{0}\sqrt{\frac{1}{{\log d}}}}$
for some constant $c_{0}$ (in particular, we can choose $c_{0}=7$). Let
$\hat{\cal{S}}\subseteq{\cal{S}}_{d}$ be an arbitrary subset such that
$|\hat{\cal{S}}|=2^{\omega}$ for some integer $\omega$ such that
$|\hat{\cal{S}}|\geq 1/2\cdot|{\cal{S}}_{d}|$, then it is easy to see that
$|\hat{\cal{S}}|=d^{1-\Theta(\sqrt{\frac{1}{{\log d}}})}$. Consider all the
integers that can be written as
$\sum_{i=0}^{\beta}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}[i]x^{i}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ for some integer $\beta$,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}[\beta])\in\hat{\cal{S}}^{\beta+1}$, and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}=(1,x,\cdots,x^{\beta})$, for
$x=5d+1$. It is easy to see that we obtain $|\hat{\cal{S}}|^{\beta+1}$
different integers constructed this way.

Simple calculations show that $|\hat{\cal{S}}|^{\beta+1}\geq N$ if

$\beta\geq\frac{\log N}{\log d}\left(1+\Theta\left(\sqrt{\frac{1}{\log
d}}\right)\right).$

Hence, by picking $\beta=\lceil\frac{\log N}{\log\log N}\rceil+O(\frac{\log
N}{(\log\log N)^{3/2}}),$ we can guarantee that $|\hat{\cal{S}}|^{\beta+1}\geq
N$. For $d\geq e^{(\sqrt{\log\log N}+7)^{2}}$, we notice that $\sqrt{\log
d}\geq\sqrt{\log\log N}+7$, hence

$|{\cal{S}}_{d}|\geq d^{1-7\sqrt{\frac{1}{{\log d}}}}=e^{\log d-7\sqrt{\log
d}}>e^{\log\log N}=\log N>\beta+1.$

Hence, we can define an arbitrary injection $g$ that maps
$j\in\\{0,1,\cdots,\beta\\}$ to a distinct number in ${\cal{S}}_{d}$.

Consider all the vector $\textstyle\bf a$’s. For any two vectors
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{j}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}$, we say they are close
if ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{j}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}$ differ by exactly one
coordinate, i.e., there exists some $0\leq j^{*}\leq\beta$ such that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[j]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[j]$ for all $j\neq j^{*}$
and ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[j^{*}]\neq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[j^{*}]$. We claim the
following.

######  Claim 1.

Vectors in $\hat{\cal{S}}^{\beta+1}$ can be ordered such that any two
consecutive vectors are close.

###### Proof.

Recall that $|\hat{{\cal{S}}}|=2^{\omega}$, hence we can map each
$a_{j}\in\hat{\cal{S}}$ to a distinct $\omega$-bit binary number (or more
specifically, a binary string) within $\\{0,1\\}^{\omega}$. Let
$\xi:\hat{\cal{S}}\rightarrow\\{0,1\\}^{\omega}$ be an arbitrary one-to-one
mapping, then we can define an extended mapping
$\xi^{\prime}:{\hat{\cal{S}}}^{\beta+1}\rightarrow\\{0,1\\}^{(\beta+1)\omega}$
such that $\textstyle\bf a$ is mapped to a $(\beta+1)\omega$-bit binary string
$\overline{\xi({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}[0])\xi({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}[1])\cdots\xi({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}[{\beta}])}_{2}$. If we can
order all $(\beta+1)\omega$-bit binary string such that every adjacent numbers
differ by exactly one bit, then the inverse of these binary strings gives a
sequence of $\textstyle\bf a$’s such that adjacent vectors are close.

Now we prove the following statement: for any $n\in\mathbb{Z}$, $n\geq 2$ and
an arbitrary string $b\in\\{0,1\\}^{n}$, all binary strings of $\\{0,1\\}^{n}$
can be ordered in a sequence starting with $b$ such that any two adjacent
strings differ by exactly one bit. We show this by induction. The statement is
clearly true for $n=2$. Suppose it is true for all $n\leq n^{\prime}$, we
prove it also holds for $n=n^{\prime}+1$. Consider the first bit of $b$, which
can be $0$ or $1$. Assume it is $1$ (the case of $0$ can be proved in a
similar way), then $b=1b_{1}$ for some $b_{1}\in\\{0,1\\}^{n^{\prime}}$.
According to the induction hypothesis, all binary strings of
$\\{0,1\\}^{n^{\prime}}$ can be ordered in a sequence starting with $b_{1}$
such that any two adjacent binary strings only differ by one bit. Let such a
sequence be $b_{1},b_{2},\cdots,b_{2^{n^{\prime}}}$, then all binary strings
of $\\{0,1\\}^{n^{\prime}+1}$ can be ordered as
$1b_{1},1b_{2},\cdots,1b_{2^{n^{\prime}}},0b_{2^{n^{\prime}}},0b_{2^{n^{\prime}}-1},\cdots,0b_{1}$.
Hence, the statement is true, and Claim 1 follows. ∎

Now consider an arbitrary ordering of vectors of $\hat{\cal{S}}^{\beta+1}$
that satisfies Claim 1. Let the sequence be
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{1},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{2},...$ where
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[\beta])$ denote the
$i$-th vector in the sequence. Recall that each
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$ is a
$(\beta+1)$-dimensional vector. Let ${prec}(i)$ be the unique coordinate where
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i-1}$ differ. Similarly, let
${succ}(i)$ be the coordinate where
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i+1}$ differ. By definition
it holds that ${prec}(i+1)={succ}(i)$. For the first and last vectors in the
sequence, we define additionally that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{1}[prec(1)]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{|\hat{\cal{S}}^{\beta+1}|}[succ(|\hat{\cal{S}}^{\beta+1}|)]=0$. Let
$\gamma=\beta+8$ and recall the injection
$g:\\{0,1,\cdots,\beta\\}\rightarrow{\cal{S}}_{d}$. We define $\sigma$ such
that

$\displaystyle\sigma(i)={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{prec(i)}]x^{\beta+1}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{succ(i)}]x^{\beta+2}+g\left(prec(i)\right)x^{\beta+5}+g\left(succ(i)\right)x^{\beta+6},\quad\text{if
$i$ is odd};$
$\displaystyle\sigma(i)={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{prec(i)}]x^{\beta+3}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{succ(i)}]x^{\beta+4}+g\left(prec(i)\right)x^{\beta+7}+g\left(succ(i)\right)x^{\beta+8},\quad\text{if
$i$ is even}.$

where ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}=(1,x,x^{2},\cdots,x^{\beta})$, while noting that
$prec(i),succ(i)\leq\beta<x$. Also, remark that all coeficients in the
polynomial expression belong to $\mathcal{S}_{d}$. Given that $x=5d+1$ and
$\beta=\frac{\log N}{\log d}\left(1+\Theta\left(\sqrt{\frac{1}{\log
d}}\right)\right)$, one can verify that

$\sigma(i)\leq(5d+1)^{\beta+9}=e^{(\beta+9)\log(5d+1)}\leq e^{\left(\frac{\log
N}{\log d}+{\mathcal{O}}\left(\frac{\log N}{(\log d)^{3/2}}\right)\right)(\log
d+{\mathcal{O}}(1))}\leq N^{\prime}=N^{1+O(\frac{1}{\sqrt{\log\log N}})},$

for any $i\leq N$, hence Properties 1 and 2 of Lemma 6 hold.

Consider the equation
$h\cdot\sigma(i)=\sigma(i_{1})+\sigma(i_{2})+\cdots+\sigma(i_{k})$ for
$k,h\leq 5$. The right-hand side of this equation can be expressed as
$\sigma(i_{1})+\sigma(i_{2})+\cdots+\sigma(i_{k})=\sum_{j=1}^{\gamma}b_{j}x^{j}$,
for some coefficients $b_{j}$. Notice as each coefficient
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]$ belongs to
$\hat{\cal{S}}\subseteq{\cal{S}}_{d}$, which is at most
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]\leq d<x/5$, then each
$b_{h}$ is a sum of at most $k\leq 5$ such coefficients, and thus $0\leq
b_{h}<x$. We obtain a similar statement for the left-hand side. Hence the
coefficients of terms of the same degree must coincide, and we have
$h\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[j]=\sum_{h=1}^{k}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i_{h}}[j]$ for all $0\leq
j\leq\beta.$ According to Lemma 5, we know the only solution for the above is
$k=h$ and $i_{1}=i_{2}=\cdots=i_{k}=i$, hence Property 3 is true.

It remains to prove Property 4. We suppose $i$ is odd in the following; the
case of $i$ being even can be proved analogously. Consider
$\sigma(i)+\sigma(i+1)$ which is equal to

$\displaystyle\sum_{j=0}^{\beta}b_{j}x^{j}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{prec(i)}]x^{\beta+1}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{succ(i)}]x^{\beta+2}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i+1}[{prec(i+1)}]x^{\beta+3}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i+1}[{succ(i+1)}]x^{\beta+4}$ $\displaystyle+$ $\displaystyle
g\left({prec(i)}\right)x^{\beta+5}+g\left({succ(i)}\right)x^{\beta+6}+g\left({prec(i+1)}\right)x^{\beta+7}+g\left({succ(i+1)}\right)x^{\beta+8}.$

As before, the coefficients of terms of the same degree must coincide. We know
that ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i+1}$ only differs at
coordinate $succ(i)=prec(i+1)$, hence
$b_{j}=2{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]$ for $j\neq succ(i)$.
If $\sigma(i_{1})+\sigma(i_{2})=\sigma(i)+\sigma(i+1)$, we know
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{1}}[j]+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{2}}[j]=2{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]$ for $j\neq succ(i)$,
and by the fact that ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[j]\in{\cal{S}}_{d}$ we
know it must hold that

$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{1}}[j]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{2}}[j]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]\quad\text{for all
}j\neq succ(i).$ (3)

Now consider the $succ(i)$-th coordinate. We know that among $i_{1}$ and
$i_{2}$ one is even and one is odd, for otherwise in
$\sigma(i_{1})+\sigma(i_{2})$ either the coefficients of $x^{\beta+1}$ and
$x^{\beta+2}$ are 0, or the coefficients of $x^{\beta+3}$ and $x^{\beta+4}$
are 0. In either case, this means that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$ or
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i+1}$ has a 0 coefficient,
which is a contradiction as $\mathcal{S}_{d}\subseteq\mathbb{Z}_{d}$. Let
$\\{i_{o},i_{e}\\}=\\{i_{1},i_{2}\\}$ where $i_{o}$ is odd and $i_{e}$ is
even. Then from $\sigma(i_{1})+\sigma(i_{2})=\sigma(i)+\sigma(i+1)$, we have

$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{o}}[{prec(i_{o})}]x^{\beta+1}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{o}}[{succ(i_{o})}]x^{\beta+2}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{e}}[{prec(i_{e})}]x^{\beta+3}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{e}}[{succ(i_{e})}]x^{\beta+4}+$ $\displaystyle+$ $\displaystyle
g\left({prec(i_{o})}\right)x^{\beta+5}+g\left({succ(i_{o})}\right)x^{\beta+6}+g\left({prec(i_{e})}\right)x^{\beta+7}+g\left({succ(i_{e})}\right)x^{\beta+8}$
$\displaystyle=$ $\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{prec(i)}]x^{\beta+1}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{succ(i)}]x^{\beta+2}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i+1}[{prec(i+1)}]x^{\beta+3}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i+1}[{succ(i+1)}]x^{\beta+4}+$ $\displaystyle+$ $\displaystyle
g\left({prec(i)}\right)x^{\beta+5}+g\left({succ(i)}\right)x^{\beta+6}+g\left({prec(i+1)}\right)x^{\beta+7}+g\left({succ(i+1)}\right)x^{\beta+8}.$

Now we can deduce that ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{o}}[{succ(i_{o})}]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{succ(i)}]$ and
$succ(i_{o})=succ(i)$ (since $g$ is an injection). Using Equation (3) we
conclude that ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{o}}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$. Similarly,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i+1}[prec(i+1)]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i_{e}}[prec(i_{e})]$,
$prec(i+1)=prec(i_{e})$. As $succ(i)=prec(i+1)$, Equation (3) yields that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i_{e}}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i+1}$.

Each vector in the sequence is unique, so we know $i_{o}=i$ and $i_{e}=i+1$.
Using that $i_{1}\leq i_{2}$ we obtain that $i_{1}=i$ and $i_{2}=i+1$. Hence,
Property 4 is proved. Lemma 6 follows. ∎

With Lemma 6, we are ready for the main result of this section.

######  Lemma 7.

Let $\tau$ be an arbitrary permutation of $\mathbb{Z}_{n}$. Then there exists
a set ${\cal{S}}=\\{s_{1},s_{2},\cdots,s_{n}\\}$ of positive integers together
with an auxiliary set $E=\bigcup_{i=1}^{n}E_{i}$ of positive integers such
that:

  * •

All integers in ${\cal{S}}\cup E$ are bounded by
$n^{1+O(\frac{1}{\sqrt{\log\log n}})}$;

  * •

$E_{i}=\\{e_{i,1},e_{i,2},\cdots,e_{i,\omega}\\}$ for all $i$, where
$\omega=O(\frac{\log n}{\log\log n})$;

  * •

$E_{i}\cap E_{i^{\prime}}=\emptyset$ for any $i^{\prime}\neq i$;

  * •

For every $i\in\mathbb{Z}_{n}$ and $k=\tau(i)$, each sum $s_{i}+e_{i,1}$,
$e_{i,1}+e_{i,2}$, $\cdots$, $e_{i,\omega-1}+e_{i,\omega}$,
$e_{i,\omega}+s_{k}$ is unique, that is, there is no other pair in
${\cal{S}}\cup E$ that adds up to the same value.

In particular, all these properties are satisfied by setting $s_{i}=\sigma(i)$
where $\sigma:\mathbb{Z}_{N}\rightarrow\mathbb{Z}_{N^{\prime}}$ is the
function specified in Lemma 6 by taking $N=n$.

We start with a natural proof idea. Recall Lemma 6, where
$\sigma(i)=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{\gamma}])\cdot(1,x,\cdots,x^{\gamma})={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ such that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]<x/5$, whereas when we
add two values, say, $\sigma(i)+\sigma(k)$, we can directly add each
coordinate ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[j]+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[j]$. Given $i$ and $k$,
how can we guarantee that the equation
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k}=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[0]+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[1]+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{\gamma}]+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k}[{\gamma}])={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{\ell}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{r}$ has a unique solution
$\\{\ell,r\\}=\\{i,k\\}$? A simple observation is that, since
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]\in{\cal{S}}_{d}$ (by
Property 3 of Lemma 6), we know that
$2{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]$ can only be expressed
as ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[j]+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]$, and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]$ can only be expressed
as ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]+0$. Consequently, we
may lift up the dimension by writing
$\sigma(i)=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[{\gamma}],0)\cdot(1,x,\cdots,x^{\gamma},x^{\gamma+1})$, and consider
the following sequence of numbers:

$\displaystyle($ $\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle 0)$ $\displaystyle\rightarrow$ $\displaystyle($ $\displaystyle
0,$ $\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{0}])$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle 0)$ $\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[0],$ $\displaystyle
0,\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{1}])$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle 0)$ $\displaystyle\rightarrow$ $\displaystyle\cdots$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma-1}],$
$\displaystyle 0,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma}])$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma}],\quad$
$\displaystyle 0)$

It is easy to verify that the sum of any two adjacent vectors in the above
sequence is unique, which gives possible values for $e_{i,j}$’s.
Unfortunately, numbers constructed in this way do not necessarily satisfy that
$E_{i}\cap E_{i^{\prime}}=\emptyset$. In particular, there might exist some
pair $i^{\prime},k^{\prime}$ with $k^{\prime}=\tau(i^{\prime})$ where
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[j]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i^{\prime}}[j]$ for
$j\leq\gamma-2$, and ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k}[j]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k^{\prime}}[j]$ for
$j\geq\gamma-1$. In this case, we have

$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i^{\prime}}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i^{\prime}}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k^{\prime}}[{\gamma-1}],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k^{\prime}}[{\gamma}],0)=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k}[{\gamma-1}],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma}],0),$

violating $E_{i}\cap E_{i^{\prime}}=\emptyset$.

How can we construct unique $e_{i,j}$’s? Towards this, we consider all the
one-to-one mappings
$g:{\cal{S}}^{\gamma+1}_{d}\rightarrow{\cal{S}}^{\gamma+1}_{d}$. Under
composition of functions, all such mappings form a group
$Aut({\cal{S}}^{\gamma+1}_{d})$. We are interested in the special mapping that
maps each ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$ to
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}$ (which corresponds to
the permutation $\tau$), which belongs to $Aut({\cal{S}}^{\gamma+1}_{d})$. We
show that any mapping in $Aut({\cal{S}}^{\gamma+1}_{d})$, and hence this
special mapping, can be decomposed into a sequence of simple mappings. More
precisely, we consider any finite set ${\cal{M}}$ and the group
$Aut({\cal{M}}^{\upsilon})$ of one-to-one mappings from ${\cal{M}}^{\upsilon}$
to itself. We call a mapping in $Aut({\cal{M}}^{\upsilon})$ an $h$-shuffler if
this mapping only changes the $h$-th coordinate of the input vector, i.e., an
$h$-shuffler $f$ satisfies that for any
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in{\cal{M}}^{\upsilon}$,

$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[\upsilon-1])=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[0],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[h-1],z,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[h+1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}[\upsilon-1])),$

for some $z\in{\cal{M}}$. We show the following group theoretic lemma which
states that any mapping of $Aut({\cal{M}}^{\upsilon})$ can be decomposed into
$2\upsilon$ $h$-shufflers; see Appendix E for the proof. Our $e_{i,j}$’s can
be obtained from these $h$-shufflers.

######  Lemma 8.

Let ${\cal{M}}$ be a finite set, $\upsilon\in\mathbb{Z}^{+}$ and
$Aut({\cal{M}}^{\upsilon})$ be the group of all one-to-one mappings from
${\cal{M}}^{\upsilon}$ to itself. The group operation is function composition
and denoted as $\circ$. For any $\pi\in Aut({\cal{M}}^{\upsilon})$, there
exist $h$-shufflers $f_{h},\hat{f}_{h}\in Aut({\cal{M}}^{\upsilon})$ for every
$1\leq h\leq\upsilon$ such that
$F({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\hat{F}(\pi({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}))$ for any
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in{\cal{M}}^{\upsilon}$,
where $F=f_{\upsilon-1}\circ f_{\upsilon-2}\circ\cdots\circ f_{0}$ and
$\hat{F}=\hat{f}_{\upsilon-1}\circ\hat{f}_{\upsilon-2}\circ\cdots\circ\hat{f}_{0}$.
Furthermore, $f_{h}$’s and $\hat{f}_{h}$’s can be constructed in time that is
polynomial in $|{\cal{M}}^{\upsilon}|$.

Lemma 8 implies a decomposition of $\pi$ into $h$-shufflers, i.e.,
$\pi=\hat{f}_{0}^{-1}\circ\hat{f}_{1}^{-1}\circ\cdots\circ\hat{f}_{\upsilon-1}^{-1}\circ
f_{\upsilon-1}\circ\cdots\circ f_{0}$.

With Lemma 8, we are ready to prove Lemma 7. We first set the value of all
parameters. Towards this, we will apply Lemma 6 twice.

At first, we apply Lemma 6 by taking $N=n$. Then we obtain
$\sigma:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n^{\prime}}$ where
$n^{\prime}=n^{1+{\mathcal{O}}(1/\sqrt{\log\log n})}$,
$\sigma(i)=\sum_{j=0}^{\gamma}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]x^{j}$ for
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]\in{\cal{S}}_{d}$ where
$\gamma=\lceil\frac{\log n}{\log\log n}\rceil+{\mathcal{O}}(\frac{\log
n}{(\log\log n)^{3/2}})$, $d=\lceil e^{(\sqrt{\log\log
n}+7)^{2}}\rceil=e^{{\mathcal{O}}(\sqrt{\log\log n})}\cdot\log n$ and
$x=5d+1$. Except $N$, all the other parameters, including
$n^{\prime},\sigma,x,d,\gamma$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$’s are fixed throughout
the following part of this section.

Next, we apply Lemma 6 again by setting $N=4\gamma+4$ where $\gamma$ takes the
value we determined above. By doing so we obtain another injection
$\sigma^{\prime}$. We have the following simple observation.

######  Observation 1.

If $\ell\leq 4\gamma+4$, then $\sigma^{\prime}(\ell)=o(\log^{2}n)<x^{2}$.

###### Proof.

Note that $\gamma=O(\frac{\log n}{\log\log n})$. By Lemma 6,
$\sigma^{\prime}(\ell)\leq(4\gamma+4)^{1+O(\frac{1}{\sqrt{\log\log(4\gamma+4)}})}=o(\gamma^{2})=o(\log^{2}n)$.
∎

Next, We will apply Lemma 8. In the following part of this paper, any
$\upsilon$-dimensional vector $\textstyle\bf c$ represents the number given by
the polynomial expression
$\sum_{i=1}^{\upsilon-1}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[i]x^{i}$; vectors and
polynomial expressions are used interchangeably. Given our permutation $\tau$,
we define $\hat{\tau}$ as a one-to-one mapping that maps each vector
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$ to
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}$, or equivalently, maps
$\sigma(i)$ to $\sigma(k)$ if $k=\tau(i)$. Notice that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$’s form a subset of
${\cal{S}}_{d}^{\gamma+1}$, so currently $\hat{\tau}$ is only defined on this
subset. We can extend $\hat{\tau}$ to ${\cal{S}}_{d}^{\gamma+1}$ such that for
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}\in{\cal{S}}_{d}^{\gamma+1}$
and ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}\neq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$, then
$\hat{\tau}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}})={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}$. Hence, $\hat{\tau}\in
Aut({\cal{S}}_{d}^{\gamma+1})$. According to Lemma 8, we can obtain
$h$-shufflers $f_{h}$ and $\hat{f}_{h}$ for all $0\leq h\leq\gamma$ such that
$f_{\gamma}\circ f_{\gamma-1}\circ\cdots\circ
f_{0}=\hat{f}_{\gamma}\circ\hat{f}_{\gamma-1}\circ\cdots\circ\hat{f}_{0}\circ\hat{\tau}$.

For ease of notation, define $F_{h}=f_{h}\circ f_{h-1}\circ\cdots\circ f_{0}$
and $\hat{F}_{h}=\hat{f}_{h}\circ\hat{f}_{h-1}\circ\cdots\circ\hat{f}_{0}$. As
$h$-shufflers only changes the $h$-th coordinate, we have the following
observation.

######  Observation 2.

The following statements are true:

  * •

For any $0\leq h\leq\gamma$

$(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]=(F_{\gamma-1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]=\cdots=(F_{h}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[h],$
$(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]=(\hat{F}_{\gamma-1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]=\cdots=(\hat{F}_{h}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[h];$

  * •

For any $0\leq h\leq\gamma$,

$(F_{h-1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]=(F_{h-2}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]=\cdots=(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[h],$
$(\hat{F}_{h-1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]=(\hat{F}_{h-2}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]=\cdots=(\hat{F}_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}))[h]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[h].$

Now we are ready to construct a unique linking sequence for every $i$.
Intuitively, note that since $\sigma^{\prime}(h)<x^{2}$, then
$\sigma^{\prime}(h)$ occupies two “bits”in the polynomial (that is, two
coordinates). With this in mind, we let
$\hat{\sigma}^{\prime}(i)=(0,\sigma^{\prime}(i))$. Moreover, we define
$\hat{\sigma}^{\prime}(0)=(0,0)$. Now consider the following two sequences,
starting from ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}$, respectively, and end
up at the same vector:

$\displaystyle($ $\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle 0,$ $\displaystyle\hat{\sigma}^{\prime}(0))$ $\displaystyle:=$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{0}_{i}$
$\displaystyle\rightarrow$ $\displaystyle($ $\displaystyle 0,$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0],$
$\displaystyle\hat{\sigma}^{\prime}(1))$ $\displaystyle:=$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{1}_{i}$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle 0,$ $\displaystyle\hat{\sigma}^{\prime}(2))$ $\displaystyle:=$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{2}_{i}$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle(F_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0],$ $\displaystyle
0,\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle(F_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[1],$
$\displaystyle\hat{\sigma}^{\prime}(3))$ $\displaystyle:=$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{3}_{i}$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle(F_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0],$
$\displaystyle(F_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],\quad$
$\displaystyle 0,$ $\displaystyle\hat{\sigma}^{\prime}(4))$ $\displaystyle:=$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{4}_{i}$
$\displaystyle\rightarrow$ $\displaystyle\cdots$ $\displaystyle\rightarrow$
$\displaystyle($
$\displaystyle(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0],$
$\displaystyle(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[1],\quad\cdots,\quad$
$\displaystyle(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[\gamma-1],$
$\displaystyle 0,\quad$
$\displaystyle(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[\gamma],$
$\displaystyle\hat{\sigma}^{\prime}(2\gamma+1))$ $\displaystyle:=$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{2\gamma+1}_{i}$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0],$
$\displaystyle(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[1],\quad\cdots,\quad$
$\displaystyle(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[\gamma-1],$
$\displaystyle(F_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[\gamma],\quad$
$\displaystyle 0,$ $\displaystyle\hat{\sigma}^{\prime}(2\gamma+2))$
$\displaystyle:=$ $\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{2\gamma+2}_{i}$

and

$\displaystyle($ $\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma}],\quad$
$\displaystyle 0,$ $\displaystyle\hat{\sigma}^{\prime}(4\gamma+4))$
$\displaystyle:=$
$\displaystyle\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{0}_{k}$
$\displaystyle\rightarrow$ $\displaystyle($ $\displaystyle 0,$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma}],\quad$
$\displaystyle(\hat{F}_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[0],$
$\displaystyle\hat{\sigma}^{\prime}(4\gamma+3))$ $\displaystyle:=$
$\displaystyle\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{1}_{k}$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle(\hat{F}_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma}],\quad$
$\displaystyle 0,$ $\displaystyle\hat{\sigma}^{\prime}(4\gamma+2))$
$\displaystyle:=$
$\displaystyle\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2}_{k}$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle(\hat{F}_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[0],$ $\displaystyle
0,\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma}],\quad$
$\displaystyle\hat{F}_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[1]),$
$\displaystyle\hat{\sigma}^{\prime}(4\gamma+1))$ $\displaystyle:=$
$\displaystyle\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{3}_{k}$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle(\hat{F}_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[0],$
$\displaystyle\hat{F}_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[1],\quad\cdots,\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma-1}],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}[{\gamma}],\quad$
$\displaystyle 0,$ $\displaystyle\hat{\sigma}^{\prime}(4\gamma))$
$\displaystyle:=$
$\displaystyle\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{4}_{k}$
$\displaystyle\rightarrow$ $\displaystyle\cdots$ $\displaystyle\rightarrow$
$\displaystyle($
$\displaystyle(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[0],$
$\displaystyle(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[1],\quad\cdots,\quad$
$\displaystyle(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[\gamma-1],$
$\displaystyle 0,\quad$
$\displaystyle(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[\gamma]),$
$\displaystyle\hat{\sigma}^{\prime}(2\gamma+3))$ $\displaystyle:=$
$\displaystyle\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2\gamma+1}_{k}$
$\displaystyle\rightarrow$ $\displaystyle($
$\displaystyle(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[0],$
$\displaystyle(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[1],\quad\cdots,\quad$
$\displaystyle(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[\gamma-1]),$
$\displaystyle(\hat{F}_{\gamma}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}))[\gamma],\quad$
$\displaystyle 0,$ $\displaystyle\hat{\sigma}^{\prime}(2\gamma+2))$
$\displaystyle:=$
$\displaystyle\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2\gamma+2}_{k}$

Consider each vector in the above sequence, say,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{2}_{i}$. According to
Observation 2, we know

$\displaystyle($
$\displaystyle(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0],$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[1],\quad$
$\displaystyle\cdots,$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma-1}],\quad$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[{\gamma}],$
$\displaystyle 0,\quad$ $\displaystyle\hat{\sigma}^{\prime}(2))$
$\displaystyle=$ $\displaystyle($
$\displaystyle(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0],$
$\displaystyle(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[1],$
$\displaystyle\cdots,$
$\displaystyle(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[\gamma-1],\quad$
$\displaystyle(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[\gamma],$
$\displaystyle 0,\quad$ $\displaystyle\hat{\sigma}^{\prime}(2))$

More generally, it is easy to verify that every
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{2j}_{i}$ is the
concatenation of the vector
$\left(F_{j-1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}),0\right)$ and
$\hat{\sigma}^{\prime}(2j)$, and each
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{2j+1}_{i}$ is a combination
$SW_{j}\left(\left(F_{j-1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}),0\right)\right)$ and
$\hat{\sigma}^{\prime}(2j+1)$, where $SW_{j}$ is a one-to-one mapping that
swaps two coordinates of a vector. A similar statement holds for
$\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2j}_{k}$’s and
$\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2j+1}_{k}$’s. Since
$SW_{j}$’s, $F_{j}$’s and $\hat{F}_{j}$’s are all one-to-one mappings, and
$\sigma^{\prime}$ is an injection, each of the vectors in the sequence above
is unique. More precisely, we have the following.

######  Lemma 9.

For any $0\leq h\leq 2\gamma+1$ and $1\leq i\leq n$,

  * •

If ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h^{\prime}}_{i^{\prime}}$,
then $h=h^{\prime}$ and $i=i^{\prime}$;

  * •

If $\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h}_{i}=\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{h^{\prime}}_{i^{\prime}}$,
then $h=h^{\prime}$ and $i=i^{\prime}$.

Furthermore, by the fact that $F_{\gamma}=\hat{F}_{\gamma}\circ\hat{\tau}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{k}=\hat{\tau}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i})$, we have the following
observation:

######  Observation 3.

${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{2\gamma+2}_{i}=\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2\gamma+2}_{k}.$

Next, we consider any two adjacent vectors in the above sequence. We observe
that they differ at exactly three positions – the last coordinate (i.e.,
$\hat{\sigma}^{\prime}(j)$’s), and other two coordinates such that one of the
two vectors has $0$ coordinate. Other coordinates, e.g.,
$(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0]$ in
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{2}_{i}$ and
$(F_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0]$ in
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{3}_{i}$ are identical
according to Observation 2. This leads to the following Lemma.

######  Lemma 10.

For any $0\leq h\leq 2\gamma+1$ and $1\leq i\leq n$,

  * •

If ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h+1}_{i}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h^{\prime}}_{i^{\prime}}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h^{\prime\prime}}_{i^{\prime\prime}}$ where $h^{\prime}\leq
h^{\prime\prime}$, then $h^{\prime}=h$, $h^{\prime\prime}=h+1$,
$i^{\prime}=i^{\prime\prime}=i$;

  * •

If $\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h}_{i}+\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h+1}_{i}=\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h^{\prime}}_{i^{\prime}}+\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h^{\prime\prime}}_{i^{\prime\prime}}$ where $h^{\prime}\leq
h^{\prime\prime}$, then $h^{\prime}=h$, $h^{\prime\prime}=h+1$,
$i^{\prime}=i^{\prime\prime}=i$.

###### Proof.

We prove the first statement, that is,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h+1}_{i}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h^{\prime}}_{i^{\prime}}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h^{\prime\prime}}_{i^{\prime\prime}}$ implies $h^{\prime}=h$,
$h^{\prime\prime}=h+1$, $i^{\prime}=i^{\prime\prime}=i$. The second statement
can be proved in the same way.

We first consider the last coordinate of the summation
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h+1}_{i}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h^{\prime}}_{i^{\prime}}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h^{\prime\prime}}_{i^{\prime\prime}}$, which is
$\sigma^{\prime}(h)+\sigma^{\prime}(h+1)=\sigma^{\prime}(h^{\prime})+\sigma^{\prime}(h^{\prime\prime})$.
If $h=0$, according to Property 3 of Lemma 6, $1\times\sigma^{\prime}(1)$ can
only be expressed as $0+\sigma^{\prime}(1)$, hence we have $h^{\prime}=0$ and
$h^{\prime\prime}=1$. If $h\geq 1$, according to Property 4 of Lemma 6, we
have $h^{\prime}=h$ and $h^{\prime\prime}=h+1$.

Consider other coordinates of the equation
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h+1}_{i}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i^{\prime}}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h+1}_{i^{\prime\prime}}$. On
the left-side it is either $a$ or $2a$ where $a\in{\cal{S}}_{d}$. Consider the
equation $a=b+c$ where $b,c\in\\{0\\}\cup{\cal{S}}_{d}$. By Lemma 5, there do
not exist two numbers in ${\cal{S}}$ that add up to $a$, hence we know
$b,c\in\\{0,a\\}$. Similarly if $2a=b+c$ for $a\in{\cal{S}}_{d}$ and
$b,c\in\\{0\\}\cup{\cal{S}}_{d}$, then $b$ and $c$ are both nonzero, for
otherwise the linear equation $2y=y_{1}$ admits a solution, which is a
contradiction to that ${\cal{S}}_{d}$ satisfies Lemma 5. Hence, $2a=b+c$ for
$a,b,c\in{\cal{S}}_{d}$, and again by Lemma 5 we have $b=c=a$. Hence, we
conclude that each coordinate of
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h}_{i^{\prime}}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h+1}_{i^{\prime\prime}}$
must be the same as ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h}_{i}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h+1}_{i}$, respectively. By
Lemma 9, it follows that $i^{\prime}=i^{\prime\prime}=i$. ∎

Using the same argument, we know if
$2{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}_{i}^{2\gamma+2}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}_{i^{\prime}}^{h^{\prime}}+\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}_{i^{\prime\prime}}^{h^{\prime\prime}}$, then
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}_{i}^{2\gamma+2}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}_{i^{\prime}}^{h^{\prime}}=\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}_{i^{\prime\prime}}^{h^{\prime\prime}}$. Thus the following is also
true.

######  Lemma 11.

$2{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}_{i}^{2\gamma+2}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}_{i^{\prime}}^{h^{\prime}}+\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}_{i^{\prime\prime}}^{h^{\prime\prime}}$, then
$h^{\prime}=h^{\prime\prime}=2\gamma+2$,
$(i^{\prime},i^{\prime\prime})=(i,\tau(i))$.

We are now ready to prove Lemma 7.

###### Proof of Lemma 7.

The sequence of $E_{i}$ that links $\sigma(i)$ and $\sigma(k)$ for $k=\tau(i)$
is exactly ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{0}_{i}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{1}_{i},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{2}_{i},\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{2\gamma+2}_{i}=\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2\gamma+2}_{k}$,
$\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2\gamma+1}_{k}$, $\cdots$,
$\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{1}_{k},\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{0}_{k}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}$ (recall that by a vector
$\textstyle\bf b$ we mean the integer
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ with $x=5d+1=O(\log n)$).
The uniqueness of each linking sequence is ensured by Lemma 9 and Lemma 10.
The largest number is bounded by $x^{\gamma+5}=n^{1+O(\frac{1}{\sqrt{\log\log