# Hausdorff Dimension of closure of cycles in $d$-maps on the circle

Nicholas Payne  Northeastern University, Boston, MA 02115, USA
<EMAIL_ADDRESS>and  Mrudul Thatte  Columbia University, New York, NY
10027, USA<EMAIL_ADDRESS>
###### Abstract.

We study the dynamics of the map $x\mapsto dx(\text{mod }1)$ on the unit
circle. We characterize the invariant finite subsets of this map which are
called cycles and are graded by their degrees. By looking at the combinatorial
properties of the base-d expansion of the elements in the cycles, we prove a
conjecture of Curt McMullen that the Hausdorff dimension of the closure of
degree-m cycles is equal to $\log m/\log d$.

##  1\. Introduction

Degree-$d$ maps on the unit disk have many interesting geometric, topological
and analytic properties, which are closely related to hyperbolic geometry. The
dynamics of these maps has an important application in classifying dynamical
systems generated by polynomials in single complex variable
[goldberg1992fixed] and it provides useful information about Julia sets and
Mandelbrot sets [keller2000invariant, douady1984etude]. To get an
understanding of this family of maps, people studied the behaviour of these
maps restricted to the boundary unit circle [goldberg1992fixed,
goldberg1993fixed]. In the paper [mcmullen2010dynamics], McMullen gave a
complete description of simple (i.e. degree 1) cycles of these boundary maps,
showing that those simple cycles are an analogue of simple closed geodesics on
hyperbolic surfaces in the sense that the closure of union of simple cycles
has Hausdorff Dimension 0 and the closure of union of simple closed geodesics
has Hausdorff Dimension 1.

Here we consider degree-$d$ holomorphic maps from the unit disk onto itself.
We focus on one such map $z\mapsto z^{d}$. The restriction of this map to the
boundary circle is equivalent to the map $x\mapsto dx\ \text{(mod 1)}$ on
$\mathbb{R}/\mathbb{Z}.$ Combinatorial features of this map has been studied
recently in [PZ, zakeri2021cyclic, tan2022counting]. In this paper, we study
cycles of higher degrees in this map, and in particular, calculate the
Hausdorff dimension of their closure, which confirms a conjecture of McMullen.

######  Definition 1 ($d$-map).

Let $d\in\mathbb{N}$. We define a $d$-map to be the map on the unit circle
$S^{1}=\mathbb{R}/\mathbb{Z}$ given by

(1) $x\mapsto dx\ \text{(mod 1)},\forall x\in S^{1}.$

In other words, if the base-$d$ expansion of a point is
$(0.b_{1}b_{2}b_{3}....)_{d}$, then $d$-map takes it to the point whose
base-$d$ expansion is $(0.b_{2}b_{3}b_{4}....)_{d}$.

We say that a $d$-map has degree $d$.

######  Definition 2 (Cycle).

Let $d$ be a positive integer greater than 1. A finite set $C\subset S^{1}$ is
called a cycle for the $d$-map if and only if the $d$-map restricted to $C$ is
a transitive permutation. In terms of the base-$d$ expansion, $C$ is given by

(2) $C=\\{(0.\overline{b_{i}b_{i+1}....b_{n}b_{1}b_{2}....b_{i-1}})_{d}|1\leq
i\leq n\\},$

where $n$ is the size of the cycle and $b_{1},b_{2},...,b_{n}$ are fixed
digits in $\\{0,1,...,d-1\\}$.

Here are some examples of cycles. Consider the case $d=2$. Here,
$\\{0\\}=\\{(0.\overline{0})_{2}\\}$ is the only 1-element cycle and
$\\{\frac{1}{3},\frac{2}{3}\\}=\\{(0.\overline{01})_{2},(0.\overline{10})_{2}\\}$
is the only 2-element cycle. For an integer $n>2$, there are multiple
$n$-element cycles. For example, there are two 3-element cycles:
$\\{\frac{1}{7},\frac{2}{7},\frac{4}{7}\\}$ and
$\\{\frac{3}{7},\frac{5}{7},\frac{6}{7}\\}$.

Now we define an important invariant of a cycle, called degree.

######  Definition 3 (Degree of a cycle).

Let $d$ be a positive integer greater than 1. Let $C$ be a cycle for $d$-map.
The degree of $C$ is the smallest non-negative integer $m$ for which there
exists a degree-$m$ map $f:S^{1}\rightarrow S^{1}$ such that $f$ and the
$d$-map agree on $C$. It is denoted by $deg(C)$.

######  Remark 1.

Note that $0\leq deg(C)\leq d$ by definition.

######  Remark 2.

The cycles which contain only one element are fixed points of $d$-map and have
degree 0. All other cycles have positive degree.

Now, we give two examples.

######  Example 1.

Consider $d=2$ and $C=\\{\frac{3}{7},\frac{5}{7},\frac{6}{7}\\}$. Under the
2-map,

$\frac{3}{7}\mapsto\frac{6}{7},\ \frac{5}{7}\mapsto\frac{3}{7},\
\frac{6}{7}\mapsto\frac{5}{7}.$

Here the cyclic order of the points in $C$ is preserved. As we jump on the
points in the cycle from
$\frac{3}{7}\rightarrow\frac{5}{7}\rightarrow\frac{6}{7}$ (jump over 0) and
back to $\frac{3}{7}$, we complete one full circle. As we jump on the images
of these points, $\frac{6}{7}\rightarrow$ (jump over 0 to)
$\frac{3}{7}\rightarrow\frac{5}{7}$ and back to $\frac{6}{7}$, again we
complete one circle. This means that the degree of $C$ is 1. We can show this
by explicitly constructing a suitable map $f:S^{1}\to S^{1}$ as follows:

$f(x)=\left\\{\begin{array}[]{l l}x+\frac{3}{7}&\quad\text{if
$x\in\left[\frac{3}{7},\frac{4}{7}\right]$}\\\ &\\\
3\left(x-\frac{4}{7}\right)&\quad\text{if
$x\in\left[\frac{4}{7},\frac{5}{7}\right]$}\\\ &\\\ 2x-1&\quad\text{if
$x\in\left[\frac{5}{7},\frac{6}{7}\right]$}\\\ &\\\
\frac{5}{7}+\frac{1}{4}\left(x-\frac{6}{7}\right)&\quad\text{if
$x\in\left[\frac{6}{7},\frac{10}{7}\right]$}\\\ \end{array}\right.$

Observe that $f$ agrees with the 2-map, and it is of degree 1. As there are no
maps with smaller degree, $deg(C)=1$.

######  Example 2.

Consider $d=3$ and $C=\\{\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5}\\}$.
Under the 3-map,

$\frac{1}{5}\mapsto\frac{3}{5},\ \frac{2}{5}\mapsto\frac{1}{5},\
\frac{3}{5}\mapsto\frac{4}{5},\ \frac{4}{5}\mapsto\frac{2}{5}.$

So, as we jump on the points in the cycle from
$\frac{1}{5}\rightarrow\frac{2}{5}\rightarrow\frac{3}{5}\rightarrow\frac{4}{5}$
(jump over 0) and back to $\frac{1}{5}$, we complete one full circle. As we
jump on the images of these points, $\frac{3}{5}\rightarrow$ (jump over 0 to)
$\frac{1}{5}\rightarrow\frac{4}{5}\rightarrow$ (jump over 0 to) $\frac{2}{5}$
and back to $\frac{3}{5}$, we complete two circles. So, the degree of $C$ is
2. We can show this by explicitly constructing a suitable map $f:S^{1}\to
S^{1}$ as follows:

$f(x)=\left\\{\begin{array}[]{l l}\frac{3}{5}+4(x-\frac{1}{5})&\quad\text{if
$x\in\left[\frac{1}{5},\frac{3}{10}\right]$}\\\ &\\\
2(x-\frac{3}{10})&\quad\text{if
$x\in\left[\frac{3}{10},\frac{2}{5}\right]$}\\\ &\\\ 3x-1&\quad\text{if
$x\in\left[\frac{2}{5},\frac{3}{5}\right]$}\\\ &\\\
\frac{4}{5}+2(x-\frac{3}{5})&\quad\text{if
$x\in\left[\frac{3}{5},\frac{7}{10}\right]$}\\\ &\\\
4(x-\frac{7}{10})&\quad\text{if
$x\in\left[\frac{7}{10},\frac{4}{5}\right]$}\\\ &\\\
\frac{2}{5}+\frac{1}{2}\left(x-\frac{4}{5}\right)&\quad\text{if
$x\in\left[\frac{4}{5},\frac{6}{5}\right]$}\\\ \end{array}\right.$

Observe that $f$ agrees with the 3-map, and it is of degree 2. As there are no
maps with smaller degree, $deg(C)=2$.

######  Definition 4 (Closure of cycles).

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$. We define $E_{m,d}$ as
the closure of the union of degree-$m$ cycles for $d$-map.

(3) $E_{m,d}=\overline{\\{c\in S^{1}|c\text{ is in a cycle of degree-$m$ for
the $d$-map}\\}}$

Curtis McMullen discussed in [mcmullen2010dynamics] the simple (i.e. degree 1)
cycles for the $d$-map and and computed the Hausdorff Dimension of their
closure $E_{1,d}$. Recall that Hausdorff Dimension is defined as follows.

######  Definition 5 (Hausdorff Dimension).

The Hausdorff Dimension of a set $E$ is defined as

(4) $dim_{H}(E)=\inf\ \\{\delta\geq 0|\ \inf\
\\{\sum{r_{i}^{\delta}|E\subset\bigcup{B(x_{i},r_{i})}}\\}=0\\}.$

######  Theorem 1 (McMullen).

Let $d$ be a positive integer greater than 1. Then $dim_{H}(E_{1,d})=0.$

In this paper, we generalize the above results by showing the following.

######  Theorem 2.

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$. Then,

$dim_{H}(E_{m,d})=\frac{\log m}{\log d}.$

This paper is organized in the following way:

In Section 2, we get a lower bound on the Hausdorff Dimension of $E_{m,d}$ by
calculating the Hausdorff Dimension of a subset of $E_{m,d}$.

In Section 3, we prove the upper bound by imitating the proof of Theorem 1 in
paper [mcmullen2010dynamics] using combinatorial arguments, and conclude by
proving Theorem 2.

##  2\. Lower Bound

In this section, we define and study two useful invariants of a cycle called
crossing number and Digit Portrait, which are directly related to the degree
of the cycle. Then we use these properties to construct a subset of $E_{m,d}$
which has Hausdorff Dimension $\frac{\log m}{\log d}$.

######  Definition 6 (Crossing).

Let $d$ be a positive integer greater than 1. Let
$C=\\{c_{1},c_{2},...,c_{n}\\}$ be a cycle for $d$-map such that

$0<c_{1}<c_{2}<....<c_{n}<1$

Let $c_{n+1}=c_{1}$. For any $1\leq i\leq n$, the pair $(c_{i},c_{i+1})$ is
called a crossing generated by $\mathbf{C}$ (or simply a crossing) iff

(5) $0<dc_{i+1}\text{(mod 1)}<dc_{i}\text{(mod 1)}<1$

The total number of such crossings is called the crossing number of C.

(6) $\eta(C)=\text{\\# (crossings generated by C)}$

######  Remark 3.

If $n=1$, then there are no crossings. The crossing number is 0 which is the
degree of 1-element cycles.

######  Remark 4.

As we jump on $S^{1}$ in the counterclockwise direction and trace the points
of the cycle from $c_{1}\rightarrow c_{2}\rightarrow....\rightarrow c_{n}$ and
(jump over 0) back to $c_{1}$, we complete one full circle. When we trace the
images of these points, $dc_{1}\text{(mod 1)}\rightarrow dc_{2}\text{(mod
1)}\rightarrow......\rightarrow dc_{n}\text{(mod 1)}$ and back to
$dc_{1}\text{(mod 1)}$, we may jump over 0 multiple times. Each time we jump
over 0, we have a crossing. The crossing number of the cycle is equal to its
degree. We provide a rigorous proof of this intuitive result below.

######  Lemma 1.

Let $d$ be a positive integer greater than 1. Let
$C=\\{c_{1},c_{2},...,c_{n}\\}$ be a cycle for $d$-map with
$0<c_{1}<c_{2}<....<c_{n}<1$. Then, the crossing number of $C$ is equal to its
degree or

$\eta(C)=deg(C)$

###### Proof.

The case $n=1$ is obvious, so assume $n>1$ and let $c_{n+k}=c_{k}$, for all
$k\in\mathbb{N}.$

Let $1\leq i_{1}<i_{2}<...<i_{\eta(C)}\leq n$ be such that for all $1\leq
t\leq\eta(C)$, the pair $(c_{i_{t}},c_{i_{t}+1})$ is a crossing generated by
$C$.

First, we prove $deg(C)\geq\eta(C)$. Assume for the sake of argument that
$\eta(C)>deg(C)$. We can divide $S^{1}$ or $[0,1)$ in intervals
$I_{1},I_{2},...,I_{deg(C)}$ such that on each $I_{r}$, there exists a
continuous non-decreasing map $g_{r}$ to $[0,1)$ which agrees with the $d$-map
on $I_{r}\cap C$.

Note that there are exactly $\eta(C)$ sets of the type
$\\{c_{i_{t}},c_{i_{t}+1},...c_{i_{t+1}}\\}.$ By our assumption that
$\eta(C)>deg(C),$ we can find a $t$ such that
$\\{c_{i_{t}},c_{i_{t}+1},...c_{i_{t+1}}\\}\subset I_{r}$ for some $r$. In
other words,

$0<g_{r}(c_{i_{t}+1})=dc_{i_{t}+1}\text{(mod 1)}<dc_{i_{t}}\text{(mod
1)}=g_{r}(c_{i_{t}})<1,$

a contradiction of the non-decreasing nature of $g_{r}$. Thus,
$deg(C)\geq\eta(C)$.

Now we prove that $deg(C)\leq\eta(C)$ by constructing an appropriate map
$f:S^{1}\rightarrow S^{1}$ of degree $\eta(C)$. To start, we divide $S^{1}$
into $\eta(C)$ intervals of the type
$\left[\frac{c_{i_{t}}+c_{i_{t}+1}}{2},\frac{c_{i_{t+1}}+c_{{i_{t+1}}+1}}{2}\right]$,
each of which is mapped onto $S^{1}.$ We take the endpoints of each such
interval to 0, and points of $C$ to their images under the $d$-map. In
between, we make $f$ linear. We define

$f(x)=\left\\{\begin{array}[]{l l}\frac{dc_{i_{t}+1}\text{(mod
1)}}{\frac{c_{i_{t}+1}-c_{i_{t}}}{2}}\
(x-\frac{c_{i_{t}}+c_{i_{t}+1}}{2})&\quad\text{if
$x\in\left[\frac{c_{i_{t}}+c_{i_{t}+1}}{2},c_{i_{t}+1}\right]$}\\\ &\\\
dc_{i}\text{(mod 1)}+{\frac{dc_{i+1}\text{(mod 1)}-dc_{i}\text{(mod
1)}}{c_{i+1}-c_{i}}}\ (x-c_{i})&\quad\text{if
$x\in\left[c_{i},c_{i+1}\right]\subset\left[c_{i_{t}+1},c_{i_{t+1}}\right]$}\\\
&\\\ dc_{i_{t+1}}\text{(mod 1)}+{\frac{1-dc_{i_{t+1}}\text{(mod
1)}}{\frac{c_{i_{t+1}+1}-c_{i_{t+1}}}{2}}}\ (x-c_{i_{t+1}})&\quad\text{if
}x\in\left[c_{i_{t+1}},\frac{c_{i_{t+1}}+c_{{i_{t+1}}+1}}{2}\right]\end{array}\right.$

where intervals are taken in counter-clockwise direction.

So, $f$ is a continuous function for all $t$, and the restriction of $f$ gives
a bijection

$\left[\frac{c_{i_{t}}+c_{i_{t}+1}}{2},\frac{c_{i_{t+1}}+c_{{i_{t+1}}+1}}{2}\right)\leftrightarrow
S^{1}.$

Since $f$ has degree $\eta(C)$ and $f|_{C}$ agrees with the $d$-map, by
Definition 3, $deg(C)\leq\eta(C).$ This, combined with above, completes the
proof.

∎

Now that we have established the relation between the degree and the crossing
number of a cycle, we need a tool to estimate the crossing number. We observe
that the crossing number of a cycle is related to the order of points in the
cycle, and hence the digits in the base-$d$ expansion of points of the cycle.
We define an invariant of the cycle called Digit Portrait which characterizes
these digits.

######  Definition 7 (Digit Portrait).

Let $d$ be a positive integer greater than 1. Let $C$ be a cycle for $d$-map.
The Digit Portrait of $C$ is the non-decreasing map
$F:\\{0,1,2,...,(d-1)\\}\rightarrow\\{0,1,2,...,|C|\\}$ which satisfies

$F(j)=|\ C\ \cap\ [0,(j+1)/d)\ |\ \ \forall\ 0\leq j\leq(d-1)$

or

$F(j)=\text{\\# (elements of $C$ whose base-$d$ expansion starts with a digit
less than $j+1$)}.$

Let $dig(C)$ be the number of distinct positive values taken by $F$. Note that
if a digit $j$ is absent in the base-$d$ expansion of a point in $C$, then
$F(j)=0$ or $F(j)=F(j-1)$. So, $dig(C)$ is also the number of distinct digits
which appear in the base-$d$ expansion of any point in $C$. To estimate the
crossing number of $C$, we need the second interpretation of $dig(C)$.

######  Example 3.

Consider $d=4$ and the cycle
$C=\\{(0.\overline{0012})_{4},(0.\overline{0120})_{4},(0.\overline{1200})_{4},(0.\overline{2001})_{4}\\}$.
Note that

$0=(0.0)_{4}<(0.\overline{0012})_{4}<(0.\overline{0120})_{4}<\frac{1}{4}=(0.1)_{4}<(0.\overline{1200})_{4}<\frac{2}{4}=(0.2)_{4}<(0.\overline{2001})_{3}<\frac{3}{4}=(0.3)_{4}$

The Digit Portrait of $C$ is the map
$F:\\{0,1,2,3\\}\rightarrow\\{0,1,2,3,4\\}$ given by:

$F(0)=2,F(1)=3,F(2)=4,F(3)=4.$

$F$ takes the values 2, 3 and 4. So, $dig(C)$ is 3. There are exactly 3 digits
(0, 1 and 2) which appear in the base-4 expansion of the points in $C$.

Now we establish the relation between $dig(C)$ and the crossing number of $C$.

######  Lemma 2.

Let $d$ be a positive integer greater than 1, and
$C=\\{c_{1},c_{2},...,c_{n}\\}$ be a cycle for the $d$-map with
$0<c_{1}<c_{2}<....<c_{n}<1$ and $n>1$. Then, the crossing number of $C$ is at
most the number of distinct digits which appear in the base-$d$ expansion of a
point in $C$. In other words,

$\eta(C)\leq dig(C).$

###### Proof.

Let $1\leq i<n$. Let $c_{i}\in[j_{1}/d,(j_{1}+1)/d)$ and
$c_{i+1}\in[j_{2}/d,(j_{2}+1)/d)$. In other words, the base-$d$ expansions of
$c_{i}$ and $c_{i+1}$ begin with the digits $j_{1}$ and $j_{2},$ respectively.
Note that $j_{1}\leq j_{2}$ because $c_{i}<c_{i+1}$.

If $j_{1}=j_{2}=j$, then

$0<dc_{i}\text{(mod 1)}=dc_{i}-j<dc_{i+1}-j=dc_{i+1}\text{(mod 1)}<1.$

In this case, $(c_{i},c_{i+1})$ cannot be a crossing. So, $(c_{i},c_{i+1})$ is
a crossing only if $j_{1}<j_{2},$ i.e., $c_{i}$ is the largest element of
$C\cap\ [j_{1}/d,(j_{1}+1)/d)$ and $c_{i+1}$ is the smallest element of $C\
\cap\ [j_{2}/d,(j_{2}+1)/d)$.

Thus, there are at most $(dig(C)-1)\ i$’s for which $1\leq i<n$ and
$(c_{i},c_{i+1})$ is a crossing. For some cycles, $(c_{n},c_{1})$ is an
additional crossing. So, there are at most $dig(C)\ i$’s for which $1\leq
i\leq n$ and $(c_{i},c_{i+1})$ is a crossing. ∎

Together, Lemma 1 and Lemma 2 give a way of estimating the degree of a cycle
by looking at the digits in the base-$d$ expansion of a point in the cycle.
Now we use this to get a sufficient condition for a point to be in the closure
of the cycles of fixed degree.

######  Lemma 3.

Let $m,d\in\mathbb{N}$ with $1\leq m\leq d$ and $1<d$. Then, any point in
$S^{1}$ whose base-$d$ expansion contains at most $m$ distinct digits lies in
$E_{m,d}$.

###### Proof.

Let $\alpha\in S^{1}.$ Let
$\alpha={(0.\alpha_{1}\alpha_{2}\alpha_{3}.....)}_{d}$ such that $\forall\
r,\alpha_{r}\in\\{b_{1},b_{2},...,b_{m}\\}\subset\\{0,1,...,(d-1)\\}.$ Here,
$b_{1},b_{2},...,b_{m}$ are fixed digits in base-$d$ such that
$b_{1}<b_{2}<...<b_{m}.$

To prove that $\alpha$ lies in $E_{m,d}$, we will show that for all
$q\in\mathbb{N},$ there exists a degree-$m$ cycle $C$ for the $d$-map that
intersects $d^{-q}$ neighborhood of $\alpha$. Any periodic point whose
base-$d$ expansion contains exactly $m$ distinct digits is in a cycle of
degree at most $m$. To get the maximum possible degree, we need maximum
possible crossings. This can be achieved with the following construction:

Let $N\in\mathbb{N}$ such that for all $1\leq t\leq m,$ $N$ is greater than
the number of times $b_{t}$ appears in the first $q$ digits of $\alpha$. Let
$\langle b_{t}\rangle$ denote $b_{t}b_{t}b_{t}...b_{t}\ \ (N\text{\ times})$.
Consider the following point:

(7) $c={(0.\overline{\alpha_{1}\alpha_{2}\alpha_{3}...\alpha_{q}\langle
b_{m}\rangle\langle b_{1}\rangle\langle b_{m-1}\rangle\langle
b_{1}\rangle....\langle b_{2}\rangle\langle b_{1}\rangle b_{m}})}_{d}$

Clearly, $c$ is in $d^{-q}$ neighborhood of $\alpha$. It is a point of cycle
$C=\\{c_{1},c_{2},...c_{q+2N(m-1)+1}\\}$ for the $d$-map with
$0<c_{1}<c_{2}<...<c_{q+2N(m-1)+1}$.

Now we need to prove that $deg(C)=m$. For each $1\leq t\leq m$, let $i_{t}$ be
such that the largest element of $C$ whose base-$d$ expansion starts with the
digit $b_{t}$ is $c_{i_{t}}$. Note that $c_{i_{1}}$ is at least
${(0.b_{1}b_{m})}_{d}$. For $t>1$, $\ c_{i_{t}}$ is at least ${(0.\langle
b_{t}\rangle)}_{d}$. For each $1\leq t<m,\ c_{i_{t}+1}$ is the smallest
element of $C$ whose base-$d$ expansion starts with the digit $b_{t+1}$. Note
that the base-$d$ expansion of $c_{i_{t}+1}$ starts with $0.b_{t}\langle
b_{1}\rangle$.

So, for all $1\leq t<m$,

$0<dc_{i_{t}+1}\text{(mod 1)}<dc_{i_{t}}\text{(mod 1)}<1,$

i.e., $(c_{i_{t}},c_{i_{t}+1})$ is a crossing.

Note that $c_{q+2N(m-1)+1}=c_{i_{m}}$ and $c_{i_{m}+1}=c_{1}=c_{i_{1}}$. So,

$0<dc_{i_{m}+1}\text{(mod 1)}<{(0.b_{2})}_{d}<dc_{i_{m}}\text{(mod 1)}<1,$

i.e., $(c_{i_{m}},c_{i_{m}+1})$ is a crossing.

Thus, the crossing number of $C$ is at least $m$.

$\eta(C)\geq m$

From Lemma 2, we know that the crossing number of $C$ is at most the number of
distinct digits in the base-$d$ expansion of a point $C$, which in this case,
is $m$.

$\eta(C)\leq dig(C)=m$

Therefore, $\deg(C)=\eta(C)=m$.
∎

The following result follows immediately.

######  Proposition 1.

$E_{d,d}=S^{1}$. Thus, $dim_{H}(E_{d,d})=1=\frac{\log d}{\log d}.$

###### Proof.

Note that since base-$d$ has only $d$ digits, the set of all points of $S^{1}$
whose base-$d$ expansion contains at most $d$ distinct digits is $S^{1}$
itself. So, we have $S^{1}\subset E_{d,d}\subset S^{1}$ or $E_{d,d}=S^{1}.$

∎

Now, we use Lemma 3 to construct a subset of $E_{m,d}$. Let $m$ and $d$ be
positive integers with $d>1$ and $1\leq m\leq d$, and let $A_{m,d}$ be the set
of points in $S^{1}$ whose base-$d$ expansion contains the digits from 0 to
$(m-1)$ only. Clearly, $A_{m,d}\subset E_{m,d}$.

The structure of $A_{m,d}$ is similar to the structure of Cantor’s set. Here,
we start with $X_{0}=[0,1]$. Write $X_{0}$ in $d$ closed intervals of length
$1/d$. Let $X_{1}$ be union of first $m$ of these intervals.

$X_{1}=\bigcup_{i=0}^{m-1}{[i/d,{(i+1)}/d]}$

$X_{1}$ is the union of $m$ intervals of length $1/d$. Divide each such
interval in $d$ equal parts and take the first $m$ in $X_{2}.\ X_{2}$ is the
union of $m^{2}$ intervals of length $1/{d^{2}}$.

Repeat the process. If $X_{i}$ is the union of $m^{i}$ intervals of length
$d^{-i}$, then divide each such interval in $d$ equal parts and take the first
$m$ in $X_{i+1}$.

$A_{m,d}=\bigcap_{i=0}^{\infty}{X_{i}}$

Now we calculate the Hausdorff Dimension of $A_{m,d}$.

######  Lemma 4.

$dim_{H}(A_{m,d})=\frac{\log m}{\log d}$.

###### Proof.

First, we prove that the Hausdorff dimension of $A_{m,d}$ is at most
$\frac{\log m}{\log d}$. Let $\beta>0$. Note that for all $i,A_{m,d}\subset
X_{i}$. So, for each $i$, we have $m^{i}$ intervals of length $d^{-i}$ that
form a covering of $A_{m,d}$. Letting $\beta=\frac{\log m}{\log
d}+\varepsilon$ for some $\varepsilon>0$,

$\lim_{i\to\infty}{m^{i}{(d^{-i})}^{\beta}}=\lim_{i\to\infty}{m^{i}(d^{-i\varepsilon})((d^{\frac{\log
m}{\log d}})^{-i})}=\lim_{i\to\infty}{d^{-i\varepsilon}}=0$

This means that, for any $\beta>\frac{\log m}{\log d}$, we can cover $A_{m,d}$
such that the summation of $\beta$ powers of the lengths of the intervals in
the cover is as small as we like. So,

$dim_{H}(A_{m,d})\leq\frac{\log m}{\log d}.$

Now we need to show that the Hausdorff dimension of $A_{m,d}$ is at least
$\frac{\log m}{\log d}$. Note that we can consider $A_{m,d}$ as a subset of
$[0,m/d],$ a compact set. So, for any countable cover $(U_{r})$ of $A_{m,d}$,
we can find finitely many open sets $V_{1},V_{2},...,V_{p}$ such that

$\bigcup_{r=0}^{\infty}{U_{r}}\subset\bigcup_{r=0}^{p}{V_{r}}\text{\quad and}$
$\sum_{r=0}^{p}{|V_{r}|^{\beta}}\leq\sum_{r=0}^{\infty}{|U_{r}|^{\beta}}.$

We next get a lower bound on $\sum_{r=0}^{p}{|V_{r}|^{\beta}}$. Let
$b\in\mathbb{N}$ such that for all $r,d^{-b}\leq|V_{r}|$. Additionally, for
all $1\leq i\leq b$, let $N_{i}$ be the number of $V_{r}$’s which satisfy
$d^{-i}\leq|V_{r}|<d^{-i+1}$. Observe that if $|V_{r}|<d^{-i+1}$, then $V_{r}$
can intersect at most two intervals in $X_{i-1}$. Hence, $V_{r}$ can contain
at most $2m^{b-i+1}$ intervals in $X_{b}$, which has $m^{b}$ intervals. So,

$\sum_{i=0}^{b}{2m^{b-i+1}N_{i}}\geq m^{b}$

or

$\sum_{i=0}^{b}{m^{-i}N_{i}}\geq\frac{1}{2m}$

For $\beta=\frac{\log m}{\log d}$,

$\sum_{r=0}^{p}{|V_{r}|^{\beta}}\geq\sum_{i=0}^{b}{{(d^{-i})}^{\beta}N_{i}}=\sum_{i=0}^{b}{m^{-i}N_{i}}\geq\frac{1}{2m}.$

In other words, the summation of $\frac{\log m}{\log d}$ powers of the lengths
of the intervals which form a cover of $A_{m,d}$ has a positive lower bound.
Thus,

$dim_{H}(A_{m,d})\geq\frac{\log m}{\log d}.$

∎

Since $A_{m,d}\subset E_{m,d},$ we immediately get a lower bound on the
Hausdorff Dimension of $E_{m,d}:$

######  Theorem 3.

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$. Then,

$dim_{H}(E_{m,d})\geq\frac{\log m}{\log d}$

∎

##  3\. Upper Bound

In this section, we first find an upper bound on the number of degree-$m$
cycles for $d$-map which have $n$ elements. We extend this result to
precycles. Then, we find an appropriate covering of $E_{m,d}$ to prove that
its Hausdorff Dimension is at most $\frac{\log m}{\log d}$.

######  Definition 8 (Partition generated by a cycle).

Let $C=\\{c_{1},c_{2},...,c_{n}\\}$ be a degree-$m$ cycle for $d$-map such
that $0<c_{1}<c_{2}<....<c_{n}<1$. Let $\sigma$ be the map on
$\\{1,2,....,n\\}$ which satisfies:

$dc_{r}\text{(mod 1)}=c_{\sigma(r)},\forall\ 1\leq r\leq n$

Note that $\sigma$ is a permutation of $\\{1,2,....,n\\}$ because $C$ is a
cycle.

Let $1\leq i_{1}<i_{2}<...<i_{m}\leq n$ be such that for all $1\leq t\leq
m,(c_{i_{t}},c_{i_{t}+1})$ is a crossing generated by $C$. From the ordering
of the elements of $C$ and the definition of crossing, we conclude that:

$\sigma(i_{t})>\sigma(i_{t}+1)\text{ and
}\sigma(i_{t}+1)<\sigma(i_{t}+2)<...<\sigma(i_{t+1}),\ \forall\ 1\leq t<m$

and

$\sigma(i_{m})>\sigma(i_{m}+1)\text{ and
}\sigma(i_{m}+1)<...<\sigma(n)<\sigma(1)<...<\sigma(i_{1})$

Now we construct a partition of $\\{1,2,..,n\\}$ using the above property of
$\sigma$.

$P_{t}=\left\\{\begin{array}[]{l l}\\{\sigma(r)|i_{t}<r\leq
i_{t+1}\\}&\quad\text{if $1\leq t<m$}\\\ \\{\sigma(r)|i_{m}<r\leq
n\\}\cup\\{\sigma(r)|1\leq r\leq i_{1}\\}&\quad\text{if
$t=m$}\end{array}\right.$

$\\{P_{t}|1\leq t\leq m\\}$ is a partition of $\\{1,2,..,n\\}$, called as the
partition generated by $C$ and it is denoted by $P(C)$.

######  Remark 5.

Both $P(C)$ and the map $\sigma$ are useful counting $n$-element degree-$m$
cycles, as we show below.

######  Example 4.

Let us consider the instance where $d=3$ and

$C=\\{(0.\overline{00102})_{3},(0.\overline{01020})_{3},(0.\overline{02001})_{3},(0.\overline{10200})_{3},(0.\overline{20010})_{3}\\}.$

Note that here, $n=5$. Under the 3-map,

$\displaystyle c_{1}$
$\displaystyle=(0.\overline{00102})_{3}\mapsto(0.\overline{01020})_{3}=c_{2}$
$\displaystyle c_{2}$
$\displaystyle=(0.\overline{01020})_{3}\mapsto(0.\overline{10200})_{3}=c_{4}$
$\displaystyle c_{3}$
$\displaystyle=(0.\overline{02001})_{3}\mapsto(0.\overline{20010})_{3}=c_{5}$
$\displaystyle c_{4}$
$\displaystyle=(0.\overline{10200})_{3}\mapsto(0.\overline{02001})_{3}=c_{3}$
$\displaystyle c_{5}$
$\displaystyle=(0.\overline{20010})_{3}\mapsto(0.\overline{00102})_{3}=c_{1}$

So, $\sigma$ is the permutation of $\\{1,2,3,4,5\\}$ which takes 1, 2, 3, 4, 5
to 2, 4, 5, 3, 1 respectively. $(c_{3},c_{4})$ and $(c_{4},c_{5})$ are the
crossings generated by the cycle. So, $i_{1}=3$ and $i_{2}=4$, and the
partition generated by $C$ is given by:

$P(C)=\\{P_{1},P_{2}\\}\text{ where }P_{1}=\\{\sigma(r)|3<r\leq
4\\},P_{2}=\\{\sigma(r)|4<r\leq 5\\}\cup\\{\sigma(r)|1\leq r\leq 3\\}$

or

$P(C)=\\{\\{3\\},\\{1,2,4,5\\}\\}$

Now, we will show that if some properties of a cycle such as degree, the
partition it generates and its digit portrait are given, then we can construct
the cycle (find its points). Later, we will use this result to count the
number of cycles of fixed degree and cardinality.

######  Lemma 5.

Given positive integers $d,m,n$, $P=\\{P_{1},P_{2},...,P_{m}\\}$ which is a
partition of $\\{1,2,...,n\\}$, positive integer $i_{1}<|P_{m}|$ and a non-
decreasing map $F:\\{0,1,2,...,(d-1)\\}\rightarrow\\{0,1,2,...,n\\}$ with
$F(d-1)=n$, there exists at most one cycle $C$ for $d$-map such that:

  1. (1)

$C=\\{c_{1},c_{2},...,c_{n}\\}$ with $0<c_{1}<c_{2}<....<c_{n}<1$

  2. (2)

$deg(C)=m$

  3. (3)

$P(C)=P$ or $P$ is the partition generated by $C$

  4. (4)

If, for all $1<t\leq m$, $i_{t}=i_{t-1}+|P_{t}|$, then $(c_{i},c_{i+1})$ is a
crossing for all $i\in\\{i_{1},i_{2},...,i_{m}\\}$.

  5. (5)

$F$ is the Digit Portrait of $C$.

###### Proof.

Suppose $C$ is a cycle for $d$-map which satisfies all the conditions above,
and let $\sigma$ be the map on $\\{1,2,....,n\\}$ given by:

$\sigma(r)=\left\\{\begin{array}[]{l l}{(r-i_{t})}^{\text{th}}\text{ element
of }P_{t}&\quad\text{if $i_{t}<r\leq i_{t+1}$ and $1\leq t<m$}\\\
{(r-i_{m})}^{\text{th}}\text{ element of }P_{m}&\quad\text{if $i_{m}<r$}\\\
{(r+n-i_{m})}^{\text{th}}\text{ element of }P_{m}&\quad\text{if $r<i_{1}$}\\\
\end{array}\right.$

where, for all $1\leq t\leq m$, the elements of $P_{t}$ are in increasing
order. Note that $\sigma$ is uniquely determined by $m,n,P$ and $i_{1}$.
Comparing this with the definition of partition generated by a cycle, we
conclude that

$dc_{r}\text{(mod 1)}=c_{\sigma(r)},\forall\ 1\leq r\leq n$

Let $b:\\{1,2,....,n\\}\rightarrow\\{0,1,2,....,(d-1)\\}$ given by:

$b(r)=\left\\{\begin{array}[]{l l}0&\quad\text{if $r<F(0)$}\\\ j&\quad\text{if
$F(j-1)<r\leq F(j)$ and $1\leq j\leq(d-1)$}\end{array}\right.$

Note that $b$ is uniquely determined by $n,d$ and $k$. Comparing this with the
definition of Digit Portrait, we conclude that

$c_{r}\in[\ \frac{b(r)}{d},\frac{b(r)+1}{d}\ ),\ \forall\ 1\leq r\leq n$

or

$b(r)=\text{the first digit in the base-}d\text{ expansion of }c_{r},\text{for
all}\ 1\leq r\leq n$

Also,

$b(\sigma(r))=\text{the first digit in the base-}d\text{ expansion of
}c_{\sigma(r)}$ $\quad\quad=\text{ the second digit in the base-}d\text{
expansion of }c_{r}$

Thus, we conclude that

$c_{r}={(0.\overline{b(r)b(\sigma(r))b(\sigma^{2}(r)).....b(\sigma^{d-1}(r))}\
)}_{d}$

In other words, the cycle $C$ is uniquely determined by $\sigma$ and $b$.
∎

######  Remark 6.

$(c_{i},c_{i+1})$ can be a crossing only if the first digits of the base-$d$
expansions of $c_{i}$ and $c_{i+1}$ differ. So, cycle $C$ satisfying all
conditions in the above lemma can exist only if

$\\{F(0),F(1),...,F(d-1)\\}\subset\\{i_{1},i_{2},...i_{m}\\}\cup\\{n\\}$

We will use this in the proof of the following lemma.

######  Lemma 6.

Let $d,m,n\in\mathbb{N}$ with $1\leq m\leq d$ and $n,d>1$. Then the number of
cycles $C$ for $d$-map satisfying $|C|=n$ and $deg(C)=m$ is at most
$O(n^{d-m+1}m^{n-1}).$

###### Proof.

$d,m,n$ are given. Now we need $P=\\{P_{1},P_{2},...,P_{m}\\}$ which is a
partition of $\\{1,2,...,n\\}$, positive integer $i_{1}<|P_{m}|$ and a non-
decreasing map $F:\\{0,1,2,...,(d-1)\\}\rightarrow\\{0,1,2,...,n\\}$ with
$F(d-1)=n$ to fix a degree-$m$, $n$-element cycle.

Let $T$ be the set of ordered $(m+1)$-tuples $(P_{1},P_{2},...,P_{m},i_{1})$
such that $P=\\{P_{1},P_{2},...,P_{m}\\}$ is a partition of $\\{1,2,...,n\\}$,
$i_{1}\in\mathbb{N}$ and $i_{1}\leq|P_{m}|$. We want an upper bound on the
size of T, denoted here as $\\#(T)$.

$\displaystyle\\#(T)$
$\displaystyle=\sum_{\begin{subarray}{c}a_{1}+a_{2}+...+a_{m}=n\\\
a_{i}\in\mathbb{N}\end{subarray}}{a_{m}\
{n\choose{a_{1}}}{{n-a_{1}}\choose{a_{2}}}...{{{n-a_{1}-a_{2}-...-a_{m-1}}\choose{a_{m}}}}}$
$\displaystyle=\sum_{\begin{subarray}{c}a_{1}+a_{2}+...+a_{m}=n\\\
a_{i}\in\mathbb{N}\end{subarray}}{a_{m}\cdot\frac{n!}{a_{1}!\ a_{2}!\
....a_{m}!}}$
$\displaystyle=\sum_{\begin{subarray}{c}a_{1}+a_{2}+...+a_{m}=n\\\
a_{i}\in\mathbb{N}\end{subarray}}{\frac{n!}{a_{1}!\ a_{2}!\ ....a_{m-1}!\
(a_{m}-1)!}}$
$\displaystyle\leq\sum_{\begin{subarray}{c}a_{1}+a_{2}+...+a_{m-1}+(a_{m}-1)=n-1\\\
a_{i}\in\mathbb{N}\cup\\{0\\}\end{subarray}}{n\cdot\frac{(n-1)!}{a_{1}!\
a_{2}!\ ....a_{m-1}!\ (a_{m}-1)!}}$ $\displaystyle=n\cdot m^{n-1}$

After fixing an element of $T$, we need to fix a non-decreasing map $F$ from
$\\{0,1,2,...,(d-1)\\}$ to $\\{0,1,2,...,n\\}$ with $F(d-1)=n$ and
$\\{F(0),F(1),...,F(d-1)\\}\subset\\{i_{1},i_{2},...i_{m}\\}\cup\\{n\\}$.
Observe that there are $(n+1)^{(d-m-1)}$ or $(n+1)^{(d-m)}$ choices for $F$,
depending on if $n$ is in $\\{i_{1},i_{2},...i_{m}\\}$ or not.

Using Lemma 5, we conclude that the number of degree-$m$ $n$-element cycles
for $d$-map is at most $O(n^{d-m+1}m^{n-1})$.

∎

To conclude this section (and to show our desired result), we first introduce
precycles.

######  Definition 9 (Precycle).

Let $d$ be a positive integer greater than 1. A finite set $C_{P}\subset
S^{1}$ is called a precycle for $d$-map, if and only if $C_{P}=\\{c\cdot
d^{i}\text{ (mod 1)}|i\in\mathbb{N}\cup\\{0\\}\\}$ for some $c\in S^{1}$. In
other words, a precycle is the forward orbit of a rational point in $S^{1}$.
It can be written in terms of base-$d$ expansion of its points as

$C_{P}=\\{(0.b_{r}b_{r+1}...b_{n_{1}}\overline{b_{1}^{\prime}b_{2}^{\prime}....b_{n_{2}}^{\prime}})_{d}|1\leq
r\leq
n_{1}\\}\cup\\{(0.\overline{b_{k}^{\prime}b_{k+1}^{\prime}...b_{n_{2}}b_{1}^{\prime}....b_{k-1}^{\prime}})_{d}|1\leq
k\leq n_{2}\\},$

where $n_{1}$ is a fixed non-negative integer, $n_{2}$ is a fixed positive
integer and all $b_{r},b_{k}^{\prime}$ are fixed digits in
$\\{0,1,2,...,d-1\\}$.

######  Remark 7.

Every precycle $C_{P}$ includes a cycle. If $n_{1}=0$, then $C_{P}$ itself is
a cycle.

######  Example 5.

Consider $d=2$ and $C_{P}=\\{\frac{1}{3},\frac{2}{3},\frac{5}{6}\\}$. $C_{P}$
can be written as

$C_{P}=\\{\frac{5}{6}\cdot d^{i}\text{(mod 1)}|i\in\mathbb{N}\cup\\{0\\}\\}$

or

$C_{P}=\\{\frac{5}{6}\\}\cup\\{\frac{1}{3},\frac{2}{3}\\}=\\{(0.1\overline{10})_{2}\\}\cup\\{(0.\overline{01})_{2},(0.\overline{10})_{2}\\}$

######  Remark 8.

We can define degree, crossing, crossing number, digit portrait and partition
for a precycle simply by replacing $C$ by $C_{P}$ in the respective
definitions.
In the case where $C_{P}$ is a precycle but not a cycle, the map $\sigma$ in
the definition of partition (Definition 8) is not a permutation. Under
$\sigma$, one element of $\\{1,2,...,n\\}$ has no preimages, one has two
preimages and all other elements have exactly one preimage.

######  Lemma 7.

Let $d,m,n\in\mathbb{N}$ with $1\leq m\leq d$. Then the number of precycles
$C_{P}$ for the $d$-map satisfying $|C_{P}|=n$ and $deg(C_{P})=m$ is at most
$O(n^{d-m+3}m^{n-1})$.

###### Proof.

Similar to the argument used to prove Lemma 6. Note that the increase in the
exponent of $n$ is due to the small change in the nature of the map $\sigma$
in the definition of partition (Definition 8).
∎

Finally, we find a suitable covering of $E_{m,d}$ and get an upper bound on
its Hausdorff Dimension, as desired.

######  Theorem 4.

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$. Then

$dim_{H}(E_{m,d})\leq\frac{\log m}{\log d}$

###### Proof.

Fix a positive integer $n>1$, and let

$\mathscr{C}_{P}(n)=\\{C_{P}|C_{P}\text{ is a precycle for
$d$-map},deg(C_{P})\leq m,|C_{P}|\leq n\\}.$

From Lemma 7, we have $|\mathscr{C}_{P}|$ is at most $O(n^{d-m+4}m^{n})$ (note
the change in exponent due to the inequality).

Let $C$ be a degree-$m$ cycle for $d$-map, and $c\in C$. There exists a
degree-$m$ map $f:S^{1}\rightarrow S^{1}$ which agrees with $d$-map on $C$.
Letting $f^{n}$ denote $f$ composed $n$ times, we note that
$|(f^{n})^{\prime}(c)|=d^{n}$. See McMullen [mcmullen2010dynamics] for
details. It follows there exists a point $x$ in $O(d^{-n})$ neighborhood of
$c$ for which two of $x,f(x),f^{2}(x),...,f^{n}(x)$ coincide. Generalizing,
each point of any degree-$m$ cycle for the $d$-map lies in $O(d^{-n})$
neighborhood of an element in $\mathscr{C}_{P}$. Thus, $E_{m,d}$ lies in a
$O(d^{-n})$ neighborhood of $\mathscr{C}_{P}$ which has at most
$O(n^{d-m+4}m^{n})$ elements.

Let $\beta=\frac{\log m}{\log d}+\varepsilon$ for some $\varepsilon>0.$

$\displaystyle\lim_{n\to\infty}{{(d^{-n})}^{\beta}n^{d-m+4}m^{n}}$
$\displaystyle=\lim_{n\to\infty}{(d^{\frac{\log m}{\log
d}})^{-n}d^{-n\varepsilon}n^{d-m+4}m^{n}}$
$\displaystyle=\lim_{n\to\infty}{d^{-n\varepsilon}n^{d-m+4}}$
$\displaystyle=0$

For any $\beta>\frac{\log m}{\log d}$, we can cover $E_{m,d}$ such that the
summation of $\beta$ powers of the lengths of the intervals in the cover is as
small as we like. So, $dim_{H}(E_{m,d})\leq\frac{\log m}{\log d}$.

∎

We are now ready to prove Theorem 2.

######  Theorem 2.

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$. Then,

$dim_{H}(E_{m,d})=\frac{\log m}{\log d}.$

###### Proof.

Follows from Theorems 3 and 4. ∎

## Acknowledgment

The authors would like to thank Prof. Curtis McMullen for suggesting the
problems and giving valuable comments. This project was undertaken by M.T. in
SPUR (the Summer Program in Undergraduate Research) at MIT Mathematics
Department in Summer 2014. M.T. would like to thank Prof. David Jerison and
Prof. Pavel Etingof for their guidance and insightful discussions during the
program. We also thank our mentor Xuwen Zhu for her help and support for
completing this paper.

## References


[table]capposition=top

# Direct Construction of Optimal Z-Complementary Code Sets for all Possible
Even Length by Using Pseudo-Boolean Functions

Gobinda Ghosh, Sudhan Majhi, Palash Sarkar, and Ashish Kumar Upadhyay

###### Abstract

Z-complementary code set (ZCCS) are well known to be used in multicarrier
code-division multiple access (MCCDMA) system to provide a interference free
environment. Based on the existing literature the direct construction of
optimal ZCCSs are limited to its lengths. In this paper, we are interested to
construct optimal ZCCSs of all possible even lengths using Pseudo-Boolean
functions. The maximum column sequence peak-to-man envelop power ratio (PMEPR)
of the proposed ZCCSs ¨¨is upper-bounded by two which may provide an
additional advantage to control PMEPR in an ZCCS based MC-CDMA system along
with the capability of supporting a large number of users.

###### Index Terms:

Multicarrier code-division multiple access (MC-CDMA), generalized Boolean
function (GBF), pseudo-Boolean function (PBF), Z-complementary code set
(ZCCS), zero correlation zone (ZCZ),pick to mean everage power ratio (PMPER)

##  I Introduction

Multicarrier code-division multiple access (MC-CDMA) is a multiple access
scheme used in orthogonal frequency division multiplexing (OFDM)-based
telecommunication systems, allowing the system to support multiple users at
the same time over same frequency band. When the number of users in a channel
increases, it is found that the performance of MC-CDMA degrades as a result of
multi user interference (MUI)[mahadevappa2002mitigating] and multipath
interference (MPI). Complete-complementary code (CCC)[liu2014new] has perfect
cross- and auto-correlation characteristics, which allows for simultaneous
interference-free transmission in the multi-carrier-digital mobile (MC-CDMA)
system. A major disadvantage of CCC is that the number of supported users is
limited by the number of row sequences in each complementary matrix. The set
size of the ZCCS system is much bigger than that of the CCC system
[sarkar2018optimal], which enables for a considerably greater number of users
to be supported by a ZCCS-based MC-CDMA system, as opposed to a CCC-based MC-
CDMA system, where the number of subcarriers is equal to the number of users.
In recent literature, research on generalized Boolean functions (GBFs) based
constructions of complementary sequences have been found great attention in
the sequence design community [sarkar2018optimal] [wu2018optimal],
[rathinakumar2008complete], [davis1999peak], [paterson2000generalized],
[sarkar2020direct]. The GBFs based construction of CCCs were extended to
optimal ZCCSs in [sarkar2018optimal] and [wu2018optimal]. However, GBFs based
construction of optimal ZCCSs has a limitation on the sequence lengths which
is in the form of power-of-two
[sarkar2018optimal],[sarkar2020direct],[wu2018optimal] and [wu2020z]. By
extending the idea of GBFs to PBFs, recenly, a direct construction of optimal
ZCCSs has been introduced in [sarkar2021pseudo] which is able to provide non-
power-of-two length sequences but limited to the form $p2^{m}$, where $p$ is a
prime number and $m$ is a positive integer. Another direct construction Like
GBFs based constructions, PBFs based constructions are also known as direct
constructions in the literature. Direct constructions are feasible for rapid
hardware generation [sarkar2018optimal] of sequences. Besides direct
constructions, many indirect constructions can be found in [das2020new], [b],
[c], [a] and [d] which are dependent on some kernel at its initial stages. The
limitation on the lengths of optimal ZCCS through direct constructions in the
existing literature motivates us in searching of PBFs to provide more
flexiblity on the lengths. In search of new ZCCS, in this paper, we have
proposed a direct construction of optimal ZCCS for all possible even length
using PBFs. We also showed that the proposed construction is also able to
maintain a minimum coloumn sequence PMPER 2, unlike the existing direct
construction of optimal ZCCSs of non-power-of-two lengths. The PBF reported in
[sarkar2021pseudo] appears as a special case of proposed construction.
The rest of this work is organised in the following way. In Section II, we
will go over a few definitions. Section III offers a comprehensive description
of the ZCCS’s construction. Section IV of this article ends the study by
comparing our findings to those of previous researchers.

##  II Preliminary

This section presents a few basic definitions and lemmas for use in the
proposed construction. Let $\textbf{x}_{1}=[x_{1,0},x_{1,1},\ldots,x_{1,N-1}]$
and $\textbf{x}_{2}=[x_{2,0},x_{2,1},\ldots,x_{2,N-1}]$ be a pair of sequences
whose components are complex numbers. Let $\tau$ be an integer, we define
[sarkar2018optimal]

$\Theta(\textbf{x}_{1},\textbf{x}_{2})({\tau})=\begin{cases}\sum_{i=0}^{N-1-\tau}x_{1,i+\tau}x^{*}_{2,i},&0\leq\tau<N,\\\
\sum_{i=0}^{N+\tau-1}x_{1,i}y^{*}_{2,i-\tau},&-N<\tau<0,\\\
0,&\text{otherwise},\end{cases}$ (1)

and when $\textbf{x}_{1}=\textbf{x}_{2}$,
$\Theta(\textbf{x}_{1},\textbf{x}_{2})(\tau)=\mathcal{A}_{{\textbf{x}_{1}}}(\tau)$.
This functions $\Theta$ and $\mathcal{A}$ are known as Aperiodic Cross-
Correlation Function (ACCF) of $\textbf{x}_{1}$ and $\textbf{x}_{2}$ and
Aperiodic Auto-Correlation Function (AACF) of $\textbf{x}_{1}$ respectively
and $*$ denotes the complex conjugate.
Let ${B}=\\{B^{0},B^{1},\ldots,B^{M-1}\\}$ be a collection of $M$ matrices
each of dimensions $K\times N$, i.e,

$B^{\delta}=\big{[}b_{0}^{\delta},b_{1}^{\delta},\ldots,b_{K-1}^{\delta}\big{]}^{T}_{K\times
N}$ (2)

where the notation T is used to denote the transpose of a matrix, each
$b_{i}^{\delta}$ is a complex-valued sequences of length $N$ i.e,
$b_{i}^{\delta}=\\{b_{i,0}^{\delta},b_{i,1}^{\delta},\ldots,b_{i,N-1}^{\delta}\\}$.
Suppose $B^{\delta_{1}},B^{\delta_{2}}\in B$, where
$0\leq\delta_{1},\delta_{2}\leq M-1$, We define the ACCF between
$B^{\delta_{1}}$ and $B^{\delta_{2}}$ as

$\Theta(B^{\delta_{1}},B^{\delta_{2}})(\tau)=\displaystyle\sum_{i=0}^{K-1}\Theta(b_{i}^{\delta_{1}},b_{i}^{\delta_{2}})(\tau)$
(3)

When the following equation holds, we refer to the set $B$ as ZCCS.

######  Definition 1 ([sarkar2018optimal])

Code set $B$ is called a ZCCS if

$\displaystyle\Theta(B^{\delta_{1}},B^{\delta_{2}})(\tau)=\begin{cases}KN,&\tau=0,\delta_{1}=\delta_{2},\\\
0,&0<|\tau|<Z,\delta_{1}=\delta_{2},\\\
0,&|\tau|<Z,\delta_{1}\neq\delta_{2},\end{cases}$ (4)

where $Z$ denotes ZCZ width. With the parameter $K,N,M$ and $Z$. We denote the
set of matrices $B$ as a $(M,Z)-ZCCS_{K}^{N}$. When $K=M$ and $Z=N$, $B$ we
denote it by $(K,K,N)$-CCC.

###### Lemma 1

For A $(M,Z)-ZCCS_{K}^{N}$, there always exists an inequality

$M\leq K\left\lfloor\frac{N}{Z}\right\rfloor$ (5)

when $M=K\left\lfloor\frac{N}{Z}\right\rfloor$ then ${B}$ is called optimal.

###### Lemma 2

(Constrction of CCC[rathinakumar2008complete])
Let $g:\mathbb{Z}_{2}^{m}\rightarrow\mathbb{Z}_{q}$ be a second-order GBF and
$\tilde{g}$ be the reversal of $g$ i.e,
$\tilde{g}(y_{0},y_{1},\ldots,y_{m-1})\\!=\\!g(1\\!-\\!y_{0},1\\!-\\!y_{1},\ldots,1\\!-\\!y_{m-1})$.
Assume that the graph $G(g)$ contains vertices denoted as
$y_{\beta_{0}},y_{\beta_{1}},\ldots,y_{\beta_{n-1}}$ such that, after
executing a deletion operation on those vertices, the resultant graph reduced
to a path. We define the weight of each edge by $\frac{q}{2}$. Let the binary
representation of the integer ${r}$ is
$\mathbf{r}=(r_{0},r_{1},\ldots,r_{n-1})$. Define the $G_{r}$ to be

$\Big{\\{}g\\!+\\!\frac{q}{2}\Big{(}(\mathbf{v}+\mathbf{r})\cdot\mathbf{y}\\!+\\!dy_{\gamma}\Big{)}:\mathbf{v}\in\\{0,1\\}^{n},d\in\\{0,1\\}\Big{\\}},$
(6)

and $\bar{G}_{r}$ to be

$\Big{\\{}\tilde{g}\\!+\\!\frac{q}{2}\Big{(}(\mathbf{v}+\mathbf{r})\cdot\bar{\mathbf{y}}\\!+\\!\bar{d}y_{\gamma}\Big{)}:\mathbf{v}\in\\{0,1\\}^{n},d\in\\{0,1\\}\Big{\\}},$
(7)

where we denote $(\cdot)\cdot(\cdot)$ as the dot product of two real-valued
vectors $(\cdot)$ and $(\cdot)$, $\gamma$ specifies the label for either of
the path’s end vertices.
$\mathbf{y}=(y_{\beta_{0}},y_{\beta_{1}},\ldots,y_{\beta_{n-1}})$,
$\bar{\mathbf{y}}=(1-y_{\beta_{0}},1-y_{\beta_{1}},\ldots,y_{\beta_{n-1}})$,
and $\mathbf{v}=(v_{0},v_{1},\ldots,v_{n-1})$. Then
$\\{\Psi(G_{r}),\Psi^{*}(\bar{G}_{r}):0\leq r<2^{n}\\}$ forms
$(2^{n+1},2^{n+1},2^{m})$-CCC, where $\Psi^{*}(\cdot)$ denotes the complex
conjugate of $\Psi(\cdot)$.

###  II-A Pseudo-Boolean Functions (PBFs)

A degree $i$ monomial is a product of $i$ distinct varibles among
$y_{0},y_{1},\ldots,y_{m-1}$. PBFs are functions
$F:\\{0,1\\}^{m}\rightarrow\mathbb{R}$ that are represented as a linear
combination of monomials among $\\{y_{0},y_{1},\ldots,y_{m-1}\\}$ where
$y_{i}$’s are Boolean variable and coeffecients are drawn from $\mathbb{R}$.
The highest degree of the monomials are called the degree of $F$. As an
example $\frac{4}{3}x_{2}x_{1}+x_{0}$ is a 2nd order PBF of three variables
$x_{0},x_{1}$ and $x_{2}$. It is clear that when this coeffecients are drawn
from $\mathbb{Z}_{q}$ and the range of the fuction $F$ changed to $Z_{q}$ the
function becomes a Generalized Boolean Function (GBF)[sarkar2021pseudo].

Let $p_{1},p_{2},\ldots,p_{l}$ be prime numbers and
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{l})$ where
$\lambda_{i}=0,1,\ldots,p_{i}\\!-\\!1$. Let $g$ be a 2nd order boolean
function of $m$ variable. We define the following PBFs with the help of $g$ as

$\begin{split}&M^{\lambda}\\!=\\!g(y_{0},y_{1},\ldots,y_{m-1})\\!+\\!\frac{\lambda_{1}q}{p_{1}}(y_{m}\\!+\\!2y_{m+1}\\!+\\!\ldots\\!+\\!\\\
&2^{s_{1}-1}y_{m+s_{1}-1})\\!+\\!\frac{\lambda_{2}q}{p_{2}}(y_{m+s_{1}}\\!+\\!2y_{m+s_{1}+1}\\!+\\!\ldots\\!+\\!\\\
&2^{s_{2}-1}y_{m+s_{1}+s_{2}-1})\\!+\\!\ldots\\!+\\!\frac{\lambda_{l}q}{p_{l}}(\\!y_{m+\sum_{i=1}^{l-1}s_{i}}\\!+\\!2y_{m+\sum_{i=1}^{l-1}s_{i}+1}\\!+\\!\\\
&\ldots\\!+\\!y_{m+\sum_{i=1}^{l}s_{i}-1})\end{split}$ (8)

and

$\begin{split}&N^{\lambda}\\!=\\!\tilde{g}(y_{0},y_{1},\ldots,x_{m-1})\\!+\\!\frac{\lambda_{1}q}{p_{1}}(y_{m}\\!+\\!2x_{m+1}\\!+\\!\ldots\\!+\\!\\\
&2^{s_{1}-1}y_{m+s_{1}-1})\\!+\\!\frac{\lambda_{2}q}{p_{2}}(y_{m+s_{1}}\\!+\\!2y_{m+s_{1}+1}\\!+\\!\ldots\\!+\\!\\\
&2^{s_{2}-1}y_{m+s_{1}+s_{2}-1})\\!+\\!\ldots\\!+\\!\frac{\lambda_{l}q}{p_{l}}(\\!y_{m+\sum_{i=1}^{l-1}s_{i}}\\!+\\!2y_{m+\sum_{i=1}^{l-1}s_{i}+1}\\!+\\!\\\
&\ldots\\!+\\!y_{m+\sum_{i=1}^{l}s_{i}-1})\end{split}$ (9)

where each $y_{i}$’s are Boolean variables from above it is clear that both
$M^{\lambda}$ and $N^{\lambda}$ are PBF of variables $m+\sum_{i=1}^{l}s_{i}$.
We choose $s_{i}$ such a way that $p_{i}\leq 2^{s_{i}}-1$. If $p_{i}|q$
$\forall i$, then $M^{\lambda}$ and $N^{\lambda}$ reduces to GBFs
Let $h$ be a $q$-ary function of $n$ variable i.e,

$h:\\{0,1\\}^{n}\rightarrow\mathbb{Z}_{q}$ (10)

Let $\mathbf{r}=(r_{0},r_{1},\ldots,r_{n-1})$ be the binary representation of
the integer $r$ where, $0\leq r<2^{n}$ and let
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{l})$. We define the
following sets of PBFs:

$\Omega_{r}^{\lambda}\\!\\!=\\!\\!\Big{\\{}{M}^{\lambda}+h(\mathbf{v})\\!+\\!\frac{q}{2}\Big{(}(\mathbf{v}+\mathbf{r})\cdot{\mathbf{y}}\\!+\\!{d}y_{\gamma}\Big{)}:\mathbf{v}\in\\{0,1\\}^{n},d\in\\{0,1\\}\Big{\\}}$
(11)

and

$\Lambda_{t}^{\lambda}\\!\\!=\\!\\!\Big{\\{}{N}^{\lambda}+h(\mathbf{v})\\!+\\!\frac{q}{2}\Big{(}(\mathbf{v}+\mathbf{r})\cdot\bar{\mathbf{y}}\\!+\\!\bar{d}y_{\gamma}\Big{)}:\mathbf{v}\in\\{0,1\\}^{n},d\in\\{0,1\\}\Big{\\}}$
(12)

Let us assume that $g$ be the GBF as defined in Lemma 2 and
$g^{\mathbf{v},\mathbf{r},d,h}\\!\\!=\\!\\!g+h(\mathbf{v})+\frac{q}{2}((\mathbf{v}+\mathbf{r})\cdot\mathbf{y}\\!+dy_{\gamma}),s^{\mathbf{v},\mathbf{r},d,h}\\!\\!=\\!\\!\tilde{g}+h(\mathbf{v})+\frac{q}{2}((\mathbf{v}+\mathbf{r})\cdot\bar{\mathbf{y}}\\!+\bar{d}y_{\gamma})$.
We also assume
$M^{\mathbf{v},\mathbf{r},d,\lambda,h}=M^{\lambda}+h(\mathbf{v})\\!\\!+\\!\frac{q}{2}((\mathbf{v}+\mathbf{r})\cdot\mathbf{y})\\!+\\!dy_{\gamma}$,
in (11), and
$N^{\mathbf{v},\mathbf{r},d,\lambda,h}=N^{\lambda}+h(\mathbf{v})\\!+\\!\frac{q}{2}((\mathbf{v}+\mathbf{r})\cdot\bar{\mathbf{y}}\\!+\\!\bar{d}y_{\gamma})$,
in (12). As per our assumption, for any choice of
$\mathbf{v},\mathbf{r}\in\\{0,1\\}^{n}$, and $d\in\\{0,1\\}$, the functions
$g^{\mathbf{v},r,d,h}$ and $s^{\mathbf{v},\mathbf{r},d,h}$ are
$\mathbb{Z}_{q}$-valued GBFs of $m$ variables. For any choice of
$\mathbf{v},\mathbf{r}\in\\{0,1\\}^{n},d\in\\{0,1\\}$,
$\lambda=(\lambda_{1},\lambda_{2},\ldots\lambda_{l})$ and $h$ the functions
$M^{\mathbf{v},\mathbf{r},d,\lambda,h}$ and
$N^{\mathbf{v},\mathbf{r},d,\lambda,h}$ are PBFs of $m+\sum_{i=0}^{l}s_{i}$
variables. We define $\Psi(M^{\mathbf{v},\mathbf{r},d,\lambda,h})$, the
complex-valued sequence corresponding to
$M^{\mathbf{v},\mathbf{r},d,\lambda,h}$, as

$\begin{split}\Psi(M^{\mathbf{v},\mathbf{r},d,\lambda,h})=&(\omega^{M^{\mathbf{v},\mathbf{r},d,\lambda,h}_{0}}_{q},\omega^{M^{\mathbf{v},\mathbf{r},d,\lambda,h}_{1}}_{q},\ldots,\\\
&\omega_{q}^{M^{\mathbf{v},\mathbf{r},d,\lambda,h}_{2^{m+\sum_{i=0}^{l}s_{i}}-1}}),\end{split}$
(13)

$\begin{split}&~{}~{}~{}\Psi_{Trun}(M^{\mathbf{v},r,d,\lambda,h})\\\
&=\underbrace{(w_{p_{1}}^{\lambda_{1}(0)}w_{p_{2}}^{\lambda_{2}(0)}\ldots
w_{p_{l}}^{\lambda_{l}(0)})w_{q}^{g_{0}^{\mathbf{v},\mathbf{r},d,h}},\ldots,(w_{p_{1}}^{\lambda_{1}(0)}{w_{p_{2}}^{\lambda_{2}(0)}\ldots
w_{p_{l}}^{\lambda_{l}(0)})w_{q}^{g_{2^{m}-1}^{\mathbf{v},\mathbf{r},d,h}}}}\\\
&~{}~{}~{}~{}\underbrace{(w_{p_{1}}^{\lambda_{1}(1)}w_{p_{2}}^{\lambda_{2}(0)}\ldots
w_{p_{l}}^{\lambda_{l}(0)})w_{q}^{g_{0}^{\mathbf{v},t,d,h}},\ldots(w_{p_{1}}^{\lambda_{1}(1)}w_{p_{2}}^{\lambda_{2}(0)}\ldots
w_{p_{l}}^{\lambda_{l}(0)})w_{q}^{g_{2^{m}-1}^{\mathbf{v},\mathbf{r},d,h}}},\ldots,\\\
&~{}~{}~{}\underbrace{(w_{p_{1}}^{\lambda_{1}(i_{1})}w_{p_{2}}^{\lambda_{2}(i_{2})}\ldots
w_{p_{l}}^{\lambda_{l}(i_{l})})w_{q}^{g_{0}^{\mathbf{v},\mathbf{r},d,h}},\ldots,(w_{p_{1}}^{\lambda_{1}(i_{1})}w_{p_{2}}^{\lambda_{2}(i_{2})}\ldots
w_{p_{l}}^{\lambda_{l}(i_{l})})w_{q}^{g_{2^{m}-1}^{\mathbf{v},\mathbf{r},d,h}}},\ldots\\\
&~{}~{}~{}\underbrace{(w_{p_{1}}^{\lambda_{1}(p_{1}-1)}w_{p_{2}}^{\lambda_{2}(p_{2}-1)}\ldots
w_{p_{l}}^{\lambda_{l}(p_{l}-1)})w_{q}^{g_{0}^{\mathbf{v},\mathbf{r},d,h}},\ldots(w_{p_{1}}^{\lambda_{1}(p_{1}-1)}w_{p_{2}}^{\lambda_{2}(p_{2}-1)}\ldots
w_{p_{l}}^{\lambda_{l}(p_{l}-1)})w_{q}^{g_{2^{m}-1}^{\mathbf{v},\mathbf{r},d,h}}},\end{split}$
(14) $\begin{split}&~{}~{}~{}\Psi_{Trun}(N^{\mathbf{v},r,d,\lambda,h})\\\
&=\underbrace{(w_{p_{1}}^{\lambda_{1}(0)}w_{p_{2}}^{\lambda_{2}(0)}\ldots
w_{p_{l}}^{\lambda_{l}(0)})w_{q}^{s_{0}^{\mathbf{v},\mathbf{r},d,h}},\ldots,(w_{p_{1}}^{\lambda_{1}(0)}{w_{p_{2}}^{\lambda_{2}(0)}\ldots
w_{p_{l}}^{\lambda_{l}(0)})w_{q}^{s_{2^{m}-1}^{\mathbf{v},\mathbf{r},d,h}}}}\\\
&~{}~{}~{}~{}\underbrace{(w_{p_{1}}^{\lambda_{1}(1)}w_{p_{2}}^{\lambda_{2}(0)}\ldots
w_{p_{l}}^{\lambda_{l}(0)})w_{q}^{s_{0}^{\mathbf{v},t,d,h}},\ldots(w_{p_{1}}^{\lambda_{1}(1)}w_{p_{2}}^{\lambda_{2}(0)}\ldots
w_{p_{l}}^{\lambda_{l}(0)})w_{q}^{s_{2^{m}-1}^{\mathbf{v},\mathbf{r},d,h}}},\ldots,\\\
&~{}~{}~{}\underbrace{(w_{p_{1}}^{\lambda_{1}(i_{1})}w_{p_{2}}^{\lambda_{2}(i_{2})}\ldots
w_{p_{l}}^{\lambda_{l}(i_{l})})w_{q}^{s_{0}^{\mathbf{v},\mathbf{r},d,h}},\ldots,(w_{p_{1}}^{\lambda_{1}(i_{1})}w_{p_{2}}^{\lambda_{2}(i_{2})}\ldots
w_{p_{l}}^{\lambda_{l}(i_{l})})w_{q}^{s_{2^{m}-1}^{\mathbf{v},\mathbf{r},d,h}}},\ldots\\\
&~{}~{}~{}\underbrace{(w_{p_{1}}^{\lambda_{1}(p_{1}-1)}w_{p_{2}}^{\lambda_{2}(p_{2}-1)}\ldots
w_{p_{l}}^{\lambda_{l}(p_{l}-1)})w_{q}^{s_{0}^{\mathbf{v},\mathbf{r},d,h}},\ldots(w_{p_{1}}^{\lambda_{1}(p_{1}-1)}w_{p_{2}}^{\lambda_{2}(p_{2}-1)}\ldots
w_{p_{l}}^{\lambda_{l}(p_{l}-1)})w_{q}^{s_{2^{m}-1}^{\mathbf{v},\mathbf{r},d,h}}},\end{split}$
(15)

where,
$M^{\mathbf{v},\mathbf{r},d,\lambda,h}_{r^{\prime}}=M^{\mathbf{v},\mathbf{r},d,\lambda,h}(r_{0},r_{1},\ldots,r_{m+\sum_{i=0}^{l}s_{i}-1})$,
and the binary representation of the integer $r^{\prime}$ is
$(r_{0},r_{1},\ldots,r_{m+\sum_{i=0}^{l}s_{i}-1})$. The $r^{\prime}$-th
component of $\Psi(M^{\mathbf{v},\mathbf{r},d,\lambda,h})$ is given by

$\begin{split}&w_{q}^{M_{r^{\prime}}^{v,r,d,h}}\\\
&=\omega_{q}^{{g}^{\mathbf{v},\mathbf{r},d,h}(r_{0},r_{1},\ldots,r_{m-1})}\omega_{p_{1}}^{\lambda_{1}\sum_{i=0}^{i=s_{1}-1}2^{i}r_{m+i}}\\\
&\omega_{p_{2}}^{\lambda_{2}\sum_{i=0}^{i=s_{2}-1}2^{i}r_{m+s_{1}+i}}\ldots\omega_{p_{l}}^{\lambda_{l}\sum_{i=0}^{i=s_{l}-1}2^{i}r_{m+\sum_{j=1}^{l-1}s_{j}+i}}\\\
&=\omega_{q}^{{g}_{j}^{\mathbf{v},\mathbf{r},d,h}}\omega_{p_{1}}^{\lambda_{1}(i_{1})}\omega_{p_{2}}^{\lambda_{2}(i_{2})}\ldots\omega_{p_{l}}^{\lambda_{l}(i_{l})}\\\
\end{split}$ (16)

where $(r_{0},r_{1},\ldots,r_{m-1})$ is the binary representation of the
integer $j$. Since $M^{\mathbf{v},r,d,\lambda,h}$ is a
$m\\!+\\!\sum_{i=1}^{l}s_{i}$ variable PBF therefore the length of
$\Psi(M^{\mathbf{v},r,d,\lambda,h})$ is $2^{s_{1}}2^{s_{2}}\ldots
2^{s_{l}}2^{m}$. Any element of $\Psi(M^{\mathbf{v},r,d,\lambda,h})$ is of the
form
$w_{q}^{g_{j}^{\mathbf{v},\mathbf{r},d,h}}w_{p_{1}}^{\lambda_{1}(i_{1})}w_{p_{2}}^{\lambda_{2}(i_{2})}\ldots
w_{p_{l}}^{\lambda_{l}(i_{l})}$, where $0\leq
i_{k}\\!\leq\\!2^{s_{k}\\!}-\\!1$, $0\leq j\leq 2^{m}-1$ and $0\leq k\leq l$.
If $S=\\{P_{1},P_{2},\ldots,P_{k}\\}$ be collection of PBFs then

$\Psi(S)=\begin{bmatrix}\Psi(P_{1})\\\ \Psi(P_{2})\\\ \vdots\\\
\Psi(P_{k})\end{bmatrix},$ (17)

Now we truncate the sequence as follows we reomove all the elements of the
form
$w_{q}^{g_{j}^{\mathbf{v},\mathbf{r},d,h}}\\!w_{p_{1}}^{\lambda_{1}(i_{1})}\\!w_{p_{2}}^{\lambda_{2}(i_{2})}\\!\ldots\\!w_{p_{l}}^{\lambda_{l}(i_{l})}$
from $\Psi(M^{\mathbf{v},r,d,\lambda,h})$ if atleast one of $i_{k}\geq p_{k}$
where $0\leq i_{k}\leq 2^{s_{k}}-1$ , $1\leq k\leq l$ and $0\leq j\leq
2^{m}-1$. Therefore after the trancation we left with a squence
$\Psi_{Trun}(M^{\mathbf{v},r,d,\lambda,h})$ (14) where each elements of
$\Psi_{Trun}(M^{\mathbf{v},r,d,\lambda,h})$ is of the form
$w_{q}^{g_{j}^{\mathbf{v},\mathbf{r},d,h}}\\!w_{p_{1}}^{\lambda_{1}(i_{1})}\\!w_{p_{2}}^{\lambda_{2}(i_{2})}\\!\ldots\\!w_{p_{l}}^{\lambda_{l}(i_{l})}$,
$0\\!\leq i_{k}\leq\\!p_{k}\\!-\\!1$ , $0\\!\leq\\!j\\!\leq\\!2^{m}\\!-\\!1$
and $1\leq\\!k\\!\leq\\!l$. Clearly we can make $p_{1}p_{2}\ldots p_{k}2^{m}$
number of the elements of the form
$w_{p_{1}}^{\lambda_{1}(i_{1})}w_{p_{2}}^{\lambda_{2}(i_{2})}\ldots
w_{p_{l}}^{\lambda_{l}(i_{l})}w_{q}^{s_{j}^{\mathbf{v},\mathbf{r},d,h}}$ if we
vary all the $i_{k}$’s from $0$ to $p_{k}\\!-\\!1$ and $j$ from $0$ to
$2^{m}\\!-\\!1$. Hence the length of
$\Psi_{Trun}(M^{\mathbf{v},r,d,\lambda,h})$ is $p_{1}p_{2}\ldots p_{k}2^{m}$.
In this way we obtain the sequence $\Psi_{Trun}(M^{\mathbf{v},r,d,\lambda,h})$
as defined in (14). Similarly by the same way we obtain the sequence
$\Psi_{Trun}(N^{\mathbf{v},r,d,\lambda,h})$ (15). Equation (14) and (15)
contains $p_{1}p_{2}\ldots p_{l}$ parenthesis and each parenthesis has a
sequence of length length $2^{m}$.

##  III Proposed Construction of ZCCs

###### Lemma 3

([vaidyanathan2014ramanujan] ) Let $t$ and $t^{\prime}$ be two non-negative
integers, where $0\leq t\neq t^{\prime}<p_{i}$, $p_{i}$ is a prime number as
defined in Section-II. Then
$\displaystyle\sum_{j=0}^{p_{i}-1}\omega_{p_{i}}^{(t-t^{\prime})j}=0.$

###### Theorem 1

Let $g:Z_{2}^{m}\rightarrow Z_{q}$ be a GBF as defined in Lemma 2. Let $2\leq
p_{i}<2^{s_{i}}$ and $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{l})$
where $1\leq i\leq l$ and $0\leq\lambda_{i}\leq p_{i}$. Then the set of codes

$\begin{split}\bigg{\\{}{\psi_{Trun}}(\Omega_{r}^{\lambda}),{\psi_{Trun}}(\Lambda_{r}^{\lambda}):0\leq
r<2^{n},&0\leq\lambda_{i}<p_{i}-1\bigg{\\}}\end{split}$ (18)

forms a
$(\prod_{i=1}^{l}p_{i}2^{n+1},2^{m})-ZCCS_{2^{n+1}}^{2^{m}\prod_{i=1}^{l}p_{i}}$.

###### Proof:

From (14) and (15) it can be observed that each parenthesis of
$\Psi_{Trun}(M^{\mathbf{v},r,d,\lambda,h})$ and
$\Psi_{Trun}(N^{\mathbf{v},r,d,\lambda,h})$ can be expressed as
$\omega_{p_{1}}^{\lambda_{1}(i_{1})}\omega_{p_{2}}^{\lambda_{2}(i_{2})}\ldots\omega_{p_{l}}^{\lambda_{l}(i_{l})}\Psi(g^{\mathbf{v},\mathbf{r},d,h})$
and
$\omega_{p_{1}}^{\lambda_{1}(i_{1})}\omega_{p_{2}}^{\lambda_{2}(i_{2})}\ldots\omega_{p_{l}}^{\lambda_{l}(i_{l})}\Psi(s^{\mathbf{v},\mathbf{r},d,h})$
respectively. From (11), (14), Lemma 2 and Lemma 3 the ACCF between
$\Psi_{Trun}(\Omega_{r}^{\lambda})$ and
${\Psi_{Trun}}(\Omega_{r^{\prime}}^{\lambda^{\prime}})$ for $\tau=0$ can be
derived as,

$\begin{split}\Theta&({\Psi_{Trun}}(\Omega_{r}^{\lambda}),{\Psi_{Trun}}(\Omega_{r^{\prime}}^{\lambda^{\prime}}))(0)\\\
&=\displaystyle\sum_{\mathbf{v},d}\Theta({\Psi_{Trun}}(M^{\mathbf{v},\mathbf{r},d,\lambda,h}),{\Psi_{Trun}}(M^{\mathbf{v},\mathbf{r}^{\prime},d,\lambda^{\prime},h}))(0)\\\
&=\displaystyle\sum_{\mathbf{v},d}\Theta({\Psi}(g^{\mathbf{v},\mathbf{r},d,h}),{\Psi}(g^{\mathbf{v},\mathbf{r}^{\prime},d,h}))(0)\sum_{\alpha=0}^{p_{1}-1}\omega_{p_{1}}^{(\lambda_{1}-\lambda_{1}^{\prime})\alpha}\\\
&\
\sum_{\alpha=0}^{p_{2}-1}\omega_{p_{2}}^{(\lambda_{2}-\lambda_{2}^{\prime})\alpha}\ldots\sum_{\alpha=0}^{p_{l}-1}\omega_{p_{l}}^{(\lambda_{l}-\lambda_{l}^{\prime})\alpha}\\\
&=\Theta(\Psi(G_{r}),\Psi(G_{r^{\prime}}))(0)\sum_{\alpha=0}^{p_{1}-1}\omega_{p_{1}}^{(\lambda_{1}-\lambda_{1}^{\prime})\alpha}\sum_{\alpha=0}^{p_{2}-1}\omega_{p_{2}}^{(\lambda_{2}-\lambda_{2}^{\prime})\alpha}\\\
&\ldots\sum_{\alpha=0}^{p_{l}-1}\omega_{p_{l}}^{(\lambda_{l}-\lambda_{l}^{\prime})\alpha}\\\
&=\begin{cases}p_{1}p_{2}\ldots
p_{l}2^{m+n+1},&r=r^{\prime},\lambda=\lambda^{\prime},\\\
0,&r=r^{\prime},\lambda\neq\lambda^{\prime},\\\ 0,&r\neq
r^{\prime},\lambda=\lambda^{\prime},\\\ 0,&r\neq
r^{\prime},\lambda\neq\lambda^{\prime}.\end{cases}\end{split}$ (19)

Now, Using (11), (14), Lemma 2 and the ACCF between
${\Psi_{Trun}}(\Omega_{t}^{\lambda})$ and
${\Psi_{Trun}}(\Omega_{t^{\prime}}^{\lambda^{{}^{\prime}}})$ for
$0<|\tau|<2^{m}$ can be derived as,

$\begin{split}&\Theta({\Psi_{Trun}}(\Omega_{t}^{\lambda}),{\Psi_{Trun}}(\Omega_{t^{{}^{\prime}}}^{\lambda^{{}^{\prime}}}))(\tau)\\\
&=\Theta(\Psi(G_{r}),\Psi(G_{r^{{}^{\prime}}}))(\tau)\prod_{i=1}^{l}\sum_{\alpha=0}^{p_{i}-1}\omega_{p_{i}}^{(\lambda_{i}-\lambda_{i}^{{}^{\prime}})(\alpha)}\\\
&+\Theta(\Psi(G_{r}),\Psi(G_{r^{{}^{\prime}}}))(\tau-2^{m})\displaystyle\sum_{\alpha=0}^{p_{1}-2}\omega_{p_{1}}^{\lambda_{1}(\alpha+1)-\lambda_{1}^{{}^{\prime}}\alpha}\\\
&\prod_{i=2}^{l}\displaystyle\sum_{\alpha=0}^{p_{i}-1}\omega_{p_{i}}^{\lambda_{i}(\alpha)-\lambda_{i}^{\prime}(\alpha)}+\Theta(\psi(G_{r}),\psi(G_{r^{{}^{\prime}}}))(\tau-2^{m})\\\
&\displaystyle\sum_{j=1}^{l-2}\prod_{i=1}^{j}\omega_{p_{i}}^{\lambda_{i}(p_{i}-1)-\lambda^{{}^{\prime}}_{i}(0)}\displaystyle\sum_{\alpha=0}^{p_{j+1}-2}\omega_{p_{j+1}}^{\lambda_{j+1}(\alpha+1)-\lambda^{{}^{\prime}}_{j+1}(\alpha)}\prod_{k=j+2}^{l}\\\
&\displaystyle\sum_{\alpha=0}^{p_{k}-1}\omega_{p_{k}}^{\lambda_{p_{k}}(\alpha)-\lambda^{{}^{\prime}}_{p_{k}}(\alpha)}+\Theta(\psi(G_{r}),\psi(G_{r^{{}^{\prime}}}))(\tau-2^{m})\\\
&\prod_{i=1}^{l-1}w_{p_{i}}^{\lambda_{i}(p_{i}^{\alpha_{i}}-1)-\lambda_{i}^{{}^{\prime}}(0)}\displaystyle\sum_{\alpha=0}^{p_{l}^{\alpha_{l}}-2}\omega_{p_{l}}^{\lambda_{l}(\alpha+1)-\lambda^{{}^{\prime}}_{l}\alpha}\end{split}$
(20)

From Lemma 2 we have

$\begin{split}\Theta(\Psi(G_{r}),\Psi(G_{r^{{}^{\prime}}}))(\tau)=0,~{}0<|\tau|<2^{m}.\end{split}$
(21)

From (20) and (21),We have

$\begin{split}\Theta({\Psi_{Trun}}(\Omega_{t}^{\lambda}),{\Psi_{Trun}}(\Omega_{t^{{}^{\prime}}}^{\lambda^{\prime}}))(\tau)=0,0<|\tau|<2^{m}.\end{split}$
(22)

From (19) and (22) We have

$\begin{split}\theta&({\Psi_{Trun}}(\Omega_{t}^{\lambda}),{\Psi_{Trun}}(\Omega_{t^{\prime}}^{\lambda^{\prime}}))(\tau)\\\
&=\begin{cases}p_{1}p_{2}\ldots
p_{l}2^{m+n+1},&r=r^{\prime},\lambda=\lambda^{\prime},\tau=0,\\\
0,&r=r^{\prime},\lambda\neq\lambda^{\prime},0<|\tau|<2^{m},\\\ 0,&r\neq
r^{\prime},\lambda=\lambda^{\prime},0<|\tau|<2^{m},\\\ 0,&r\neq
r^{\prime},\lambda\neq\lambda^{\prime},0<|\tau|<2^{m}.\end{cases}\end{split}$
(23)

Similarly, it can be shown that

$\begin{split}\theta&({\Psi^{*}_{Trun}}(\Lambda_{r}^{\lambda}),{\Psi_{Trun}^{*}}(\Lambda_{r^{\prime}}^{\lambda^{\prime}})(\tau)\\\
&=\begin{cases}p_{1}p_{2}\ldots
p_{l}2^{m+n+1},&r=r^{\prime},\lambda=\lambda^{\prime},\tau=0,\\\
0,&r=r^{\prime},\lambda\neq\lambda^{\prime},0<|\tau|<2^{m},\\\ 0,&r\neq
r^{\prime},\lambda=\lambda^{\prime},0<|\tau|<2^{m},\\\ 0,&r\neq
r^{\prime},\lambda\neq\lambda^{\prime},0<|\tau|<2^{m}.\end{cases}\end{split}$
(24)

From Lemma 2 we have

$\Theta(\Psi(G_{r}),\Psi^{*}(\bar{G}_{r}))(\tau)=0,~{}|\tau|<2^{m}.$ (25)

From Lemma 2, (11), (12), (14) and (15) the ACCF between
${\Psi_{Trun}}(\Omega_{t}^{\lambda})$ and
${\Psi_{Trun}^{*}}(\Lambda_{t^{{}^{\prime}}}^{\lambda^{{}^{\prime}}})$ for
$\tau=0$ can be derived as

$\begin{split}&\Theta({\Psi_{Trun}}(\Omega_{r}^{\lambda}),{\Psi_{Trun}^{*}}(\Lambda_{r^{{}^{\prime}}}^{\lambda^{{}^{\prime}}})(0)\\\
&=\Theta(\Psi(G_{r}),\Psi^{*}(\bar{G}_{r^{{}^{\prime}}}))(0)\sum_{\alpha=0}^{p_{1}-1}\omega_{p_{1}}^{(\lambda_{1}+\lambda_{1}^{{}^{\prime}})\alpha}\sum_{\alpha=0}^{p_{2}-1}\omega_{p_{2}}^{(\lambda_{2}+\lambda_{2}^{{}^{\prime}})\alpha}\\\
&\ldots\sum_{\alpha=0}^{p_{l}-1}\omega_{p_{l}}^{(\lambda_{l}+\lambda_{l}^{{}^{\prime}})\alpha}\end{split}$
(26)

From (25), and (26) we have

$\Theta({\Psi_{Trun}}(\Omega_{r}^{\lambda}),{\Psi_{Trun}^{*}}(\Lambda_{r^{{}^{\prime}}}^{\lambda^{{}^{\prime}}})(0)=0$
(27)

By the similar calculation as in (20), we have

$\Theta({\Psi_{Trun}}(\Omega_{r}^{\lambda}),{\Psi_{Trun}^{*}}(\Lambda_{r^{{}^{\prime}}}^{\lambda^{{}^{\prime}}})(\tau)=0,\forall~{}0<|\tau|<2^{m}$
(28)

Hence by (23), (24), (27) and (28) we conclude the set

$\begin{split}\Bigg{\\{}{\psi_{Trun}}(\Omega_{r}^{\lambda}),{\psi_{Trun}}^{*}(\Lambda_{r}^{\lambda}):0\leq
r<2^{n},&0\leq\lambda_{i}\leq p_{i}-1\Bigg{\\}}\end{split}$ (29)

forms a
$(\prod_{i=1}^{l}p_{i}2^{n+1},2^{m})-ZCCS_{2^{n+1}}^{2^{m}\prod_{i=1}^{l}p_{i}}$
∎

###### Remark 1

If we take only one prime say $p_{1}=p$ and $\lambda=\lambda_{1}$ then the
result of theorem 1 reduced to $(p2^{n+1},2^{m})-ZCCS_{2^{n+1}}^{p2^{m}}$
which was proposed in [sarkar2021pseudo]

###### Corollary 1

Our construction gives optimal ZCCS of length of this form
$(p_{1}p_{2}\ldots,p_{l})2^{m}$ where $p_{i}$’s are any prime numbers. Due to
the fact from the fundamental theorem of arithmetic [baker1984concise] that
any number can be expressed as product of prime numbers therefore the optimal
ZCCS obtained by using our suggested construction gives all possible length of
this form $n2^{m}$, where $n$ is any positive integer greater than $1$. If
$m=1$ we get all possible even length optimal ZCCS.

###### Corollary 2

([sarkar2020direct] ) Let us assume that $G(h)$ is path where the edges have
the identical weight of $\frac{q}{2}$. Then $h(u)$ can be expressed as

$h(u_{0},u_{1},\ldots,u_{n-1})=\frac{q}{2}\sum_{\alpha=0}^{n-2}u_{\pi(\alpha)}u_{\pi(\alpha+1)}+\sum_{\alpha=0}^{n-1}v_{\alpha}u_{\alpha}+v$

where $v,v_{0},v_{1},\ldots v_{n-1}\in\mathbb{Z}_{q}$. From (11), it is clear
that the ith column of $\psi_{Trun}(\Omega_{t}^{\lambda})$ is obtained by
fixing $(y_{0},y_{1},\ldots,y_{{m+\sum_{i=1}^{l}s_{i}}-1})$ at
$(i_{0},i_{1},\ldots,i_{{m+\sum_{i=1}^{l}s_{i}}-1})$ in the following
expression

$\\!\\!\Big{\\{}M^{\lambda}\\!\\!+h(u)+\\!\frac{q}{2}\Big{(}(\mathbf{v}+\mathbf{r})\cdot\mathbf{y}\\!+\\!dy_{\gamma}\Big{)}:\mathbf{d}\in\\{0,1\\}^{n},d\in\\{0,1\\}\Big{\\}},$

where $(i_{0},i_{1},\ldots,i_{2^{m+\sum_{i=1}^{l}s_{i}}-1})$ is the binary
representation of $i$, and $0\leq i<2^{m+\sum_{i=1}^{l}s_{i}}$, .Because the
ith column sequence of $\Psi_{Trun}(\Omega_{t}^{\lambda})$ is derived from a
GBF whose graph is a path over n vertices, hence from [7] the ith column
sequence of $\Psi_{Trun}(\Omega_{t}^{\lambda})$ is a q-ary Golay sequence, and
the PMEPR is upper limited by 2. So the PMEPR of each column of
$\Psi_{Trun}(\Omega_{t}^{\lambda})$ is at most 2. Similarly, the PMEPR of each
column of $\Psi_{Trun}(\Lambda_{t}^{\lambda})$ has upper limit by 2. Thus, the
maximum column sequence PMEPR of
$(\prod_{i=1}^{l}p_{i}2^{n+1},2^{m})-ZCCS_{2^{n+1}}^{2^{m}\prod_{i=1}^{l}p_{i}}$.
is at most 2.

###### Example 1

Let us assume that $q\\!=\\!2$, $p_{1}\\!=\\!3$, $p_{2}\\!=\\!2$,
$p_{3}\\!=\\!2$ $m=3$, $k=1$ and $s_{1}=2$, $s_{2}=1$ and $s_{3}=1$. Let us
take the GBF $f:\\{0,1\\}^{2}\rightarrow\mathbb{Z}_{2}$ as follows:
$f=y_{1}y_{2}+y_{0}$, where $G(f\arrowvert_{y_{0}=0})$ and
$G(f\arrowvert_{y_{0}=1})$ give a path with $x_{1}$ as one of the end
vertices. From (11) and (12) we have

$\begin{split}&M^{\lambda}=y_{1}y_{2}+y_{0}+\frac{2\lambda_{1}}{3}(y_{3}+2y_{4})+\lambda_{2}y_{5}+\lambda_{3}y_{6},\\\
&N^{\lambda}=\bar{y}{{}_{1}}\bar{y}{{}_{2}}+\bar{y}{{}_{0}}+\frac{2\lambda_{1}}{3}(y_{3}+2y_{4})+\lambda_{2}y_{5}+\lambda_{3}y_{6},\end{split}$
(30)

where $\lambda_{1}=0,1,2$, $\lambda_{2}=0,1$ and $\lambda_{3}=0,1$ From (13)
and (14), we have

$\begin{split}\Omega_{r}^{\lambda}&=\left\\{M^{\lambda}+h(u)+d_{0}y_{0}+r_{0}y_{0}+dy_{1}:d_{0},d\in\\{0,1\\}\right\\}\\\
\Lambda_{r}^{\lambda}&=\left\\{N^{\lambda}+h(u)+d_{0}\bar{y}_{0}+r_{0}\bar{y}_{0}+\bar{d}y_{1}:d_{0},d\in\\{0,1\\}\right\\},\end{split}$
(31)

where $(r_{0})$ is the binary vector representation of $r$. Therefore,

$\displaystyle\begin{split}\Big{\\{}\bar{\psi}(\Omega_{r}^{\lambda}),\bar{\psi}^{*}(\Lambda_{r}^{\lambda}):0\leq
r\leq 1,0\leq\lambda_{1}\leq 2,0\leq&\lambda_{2}\leq 1,\\\
&0\leq\lambda_{3}\leq 1\Big{\\}}\end{split}$

forms a Optimal $(48,8)$-ZCCS${}_{4}^{96}$.

TABLE I: Comparison of the Proposed Construction with [sarkar2018optimal,
das2020new, sarkar2020direct, wu2020z, sarkar2021pseudo, shen2021new]

Source | Based On | Parameters | Coditions | Optimal
---|---|---|---|---
[sarkar2018optimal] | Direct | $(2^{k+p},2^{m-p})-ZCCS_{2^{k+1}}^{2^{m}}$ | $k+p\leq m$ | yes
[das2020new] | Indirect | $(K,M)-ZCCS_{M}^{K}$ | $K,M\geq 2$ | yes
[sarkar2020direct] | Direct | $(2^{n+p},2^{m-p})-ZCCS_{2^{n}}^{2^{m}}$ | $p\leq m$ | yes
[wu2020z] | Direct | $(2^{k+v},2^{n-v})-ZCCS_{2^{k}}^{2^{m}}$ | $v\leq m,k\leq m-v$ | yes
[sarkar2021pseudo] | Direct | $(p2^{k+1},2^{m})-ZCCS_{2^{k+1}}^{p2^{m}}$ | $m\geq 2$ | yes
[shen2021new] | Direct | $(q^{v+1},q^{m-v})-ZCCS_{q}^{q^{m}}$ | $v\leq m$ | yes
[das2020new] | Indirect | $(K,M^{N+1})-ZCCS_{M}^{M^{N+1}P}$ | $K,M\geq 2$ | yes
Theorem 1 | Direct | $(n2^{k+1},2^{m})-ZCCS_{2^{k+1}}^{n2^{m}}$ | $n\in\mathbf{Z}^{+},m\geq 2$ | yes

##  IV Conclusions

In this work, we have proposed a straightforward construction of optimal ZCCS
with all feasible even lengths with maximum lengths coloumn sequence PMPER is
at most 2. This work has its own peculiarity since for the first time this
design provides all feasible even length of Optimal ZCCS unlike the prior
construction which can only supply restricted lengths of optimal ZCCS via
direct construction.