lemmatheorem lemma corollarytheorem corollary

# Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra

Erik D. Demaine Computer Science and Artificial Intelligence Laboratory,
Massachusetts Institute of Technology<EMAIL_ADDRESS>Martin L.
Demaine11footnotemark: 1 David Eppstein Computer Science Department,
University of California, Irvine<EMAIL_ADDRESS>This work was supported in
part by the US National Science Foundation under grant CCF-1616248.

###### Abstract

We present new examples of topologically convex edge-ununfoldable polyhedra,
i.e., polyhedra that are combinatorially equivalent to convex polyhedra, yet
cannot be cut along their edges and unfolded into one planar piece without
overlap. One family of examples is acutely triangulated, i.e., every face is
an acute triangle. Another family of examples is stacked, i.e., the result of
face-to-face gluings of tetrahedra. Both families achieve another natural
property, which we call very ununfoldable: for every $k$, there is an example
such that every nonoverlapping multipiece edge unfolding has at least $k$
pieces.

##  1 Introduction

Can every convex polyhedron be cut along its edges and unfolded into a single
planar piece without overlap? Such edge unfoldings or nets are useful for
constructing 3D models of a polyhedron (from paper or other material such as
sheet metal): cut out the net, fold along the polyhedron’s uncut edges, and
re-attach the polyhedron’s cut edges [25]. Unfoldings have also proved useful
in computational geometry algorithms for finding shortest paths on the surface
of polyhedra [3, 5, 9].

Edge unfoldings were first described in the early 16th century by Albrecht
Dürer [16], implicitly raising the still-open question of whether every convex
polyhedron has one (sometimes called Dürer’s conjecture). The question was
first formally stated in 1975 by G. C. Shephard, although without reference to
Dürer [17, 23]. It has been heavily studied since then, with progress of two
types [15, 22]:

  1. 1.

finding restricted classes of polyhedra, or generalized types of unfoldings,
for which the existence of an unfolding can be guaranteed; and

  2. 2.

finding generalized classes of polyhedra, or restricted types of unfoldings,
for which counterexamples — ununfoldable polyhedra — can be shown to exist.

Results guaranteeing the existence of an unfolding include:

  * •

Every pyramid, prism, prismoid, and dome has an edge unfolding [15].

  * •

Every sufficiently flat acutely triangulated convex terrain has an edge
unfolding [21]. Consequentially, every acutely triangulated convex polyhedron
can be unfolded into a number of planar pieces that is bounded in terms of the
“acuteness gap” of the polyhedron, the minimum distance of its angles from a
right angle.

  * •

Every convex polyhedron has an affine transformation that admits an edge
unfolding [18].

  * •

Every convex polyhedron can be unfolded to a single planar piece by cuts
interior to its faces [3, 14].

  * •

Every polyhedron with axis-parallel sides can be unfolded after a linear
number of axis-parallel cuts through its faces [10].

  * •

Every triangulated surface (regardless of genus) has a “vertex unfolding”, a
planar layout of triangles connected through their vertices that can be folded
into the given surface [13].

  * •

For ideal polyhedra in hyperbolic space, unlike Euclidean convex polyhedra or
non-ideal hyperbolic polyhedra, every spanning tree forms the system of cuts
of a convex unfolding into the hyperbolic plane.

Previous constructions of ununfoldable polyhedra include the following
results. A polyhedron is topologically convex if it is combinatorially
equivalent to a convex polyhedron, meaning that its surface is a topological
sphere and its graph is a 3-vertex-connected planar graph.

  * •

Some orthogonal polyhedra and topologically convex orthogonal polyhedra have
no edge unfolding, and it is NP-complete to determine whether an edge
unfolding exists in this case [8, 1].

  * •

There exists a convex-face star-shaped topologically convex polyhedron with no
edge unfolding [24, 20].

  * •

There exists a triangular-face topologically convex polyhedron with no edge
unfolding [7].

  * •

There exist edge-ununfoldable topologically convex polyhedra with as few as 7
vertices and 6 faces, or 6 vertices and 7 faces [4].

  * •

There exists a topologically convex polyhedron that does not even have a
vertex unfolding [2].

  * •

There exist domes that have no Hamiltonian unfolding, in which the cuts form a
Hamiltonian path through the graph of the polyhedron [12]. Similarly, there
exist polycubes that have no Hamiltonian unfolding [11].

  * •

There exists a convex polyhedron, equipped with 3-vertex-connected planar
graph of geodesics partitioning the surface into regions metrically equivalent
to convex polygons, that cannot be cut and unfolded along graph edges [6].

In this paper, we consider two questions left open by the previous work on
edge-ununfoldable polyhedra with triangular faces [7], and strongly motivated
by O’Rourke’s recent results on unfoldings of acutely-triangulated polyhedra
[21]. First, the previous counterexample of this type involved triangles with
highly obtuse angles. Is this a necessary feature of the construction, or does
there exist an ununfoldable polyhedron with triangular faces that are all
acute? Second, how far from being unfoldable can these examples be? Is it
possible to cut the surfaces of these polyhedra into a bounded number of
planar pieces (instead of a single piece) that can be folded and glued to form
the polyhedral surface? (Both questions are motivated by previously posed
analogous questions for convex polyhedra, as easier versions of Dürer’s
conjecture [15, Open Problems 22.12 and 22.17].)

We answer both of these questions negatively, by finding families of
topologically convex edge-ununfoldable polyhedra with all faces acute
triangles, in which any cutting of the surface into regions that can be
unfolded to planar pieces must use an arbitrarily large number of pieces.
Additionally, we use a similar construction to prove that there exist edge-
ununfoldable stacked polyhedra [19], formed by gluing tetrahedra face-to-face
with the gluing pattern of a tree, that also require an arbitrarily large
number of pieces to unfold. We leave open the question of whether there exists
an edge-ununfoldable stacked polyhedron with acute-triangle faces.

##  2 Hats

Figure 1: Combinatorial structure of a hat

Our construction follows that of Bern et al. [7] in being based on certain
triangulated topological disks, which they called hats. The combinatorial
structure of a hat (in top view, but with different face angles than the hat
we use in our proof) is shown in Figure 1: It consists of nine triangles,
three of which (the brim, blue in the figure) have one edge on the outer
boundary of the disk. The next three triangles, yellow in the figure, have a
vertex but not an edge on the disk boundary; we call these the band of the
hat. The central three triangles, pink in the figure, are disjoint from the
boundary and meet at a central vertex; we call these the crown of the hat.

In both the construction of Bern et al. [7] and in our construction, the three
vertices of the hat that are interior to the disk but not at the center all
have negative curvature, meaning that the sum of the angles of the faces
meeting at these vertices is greater than $2\pi$. The center vertex, on the
other hand, has positive curvature, a sum of angles less than $2\pi$. When
this happens, we can apply the following lemmas:

###### Lemma

At any negatively-curved vertex of a polyhedron, any unfolding of the
polyhedron that cuts only its edges and separates its surface into one or more
simple polygons must cut at least two edges at each negatively-curved vertex.

######  Proof 2.1.

If only one edge were cut then the faces surrounding that vertex could not
unfold into the plane without overlap.

######  Lemma 2.2.

Let $D$ be a subset of the faces of a polyhedron, such that the polyhedron is
topologically a sphere and $D$ is topologically equivalent to a disk (such as
a hat). Then in any unfolding of the polyhedron (possible cutting it into
multiple pieces), either $D$ is separated into multiple pieces by a path of
cut edges from one boundary vertex of $D$ to another or by a cycle of cut
edges within $D$, or the set of cut edges within $D$ forms a forest with at
most one boundary vertex for each tree in the forest.

######  Proof 2.3.

If the cut edges within $D$ do not form a forest, they contain a cycle and the
Jordan Curve Theorem implies that this cycle separates an interior part of the
boundary from the exterior. If they form a forest in which some tree contains
two boundary vertices, then they contain a boundary-to-boundary path within
$D$, again separating $D$ by the Jordan Curve Theorem. The only remaining
possibility is a forest with at most one boundary vertex per tree.

######  Lemma 2.4.

For a hat combinatorially equivalent to the one in Figure 1, with positive
curvature at the center vertex and negative curvature at the other three
interior vertices, any unfolding that does not cut the hat into multiple
pieces must cut a set of edges along a single path from a boundary vertex to
the center vertex.

######  Proof 2.5.

By Lemma 2.2, each component of cut edges must form a tree with at most one
boundary vertex within the hat. But every tree with one or more edges has at
least two leaves, and every tree that is not a path has at least three leaves.
By Section 2, the only non-boundary leaf can be the center vertex, so each
component must be a path from the boundary to this vertex.

Up to symmetries of the hat, there are only two distinct shapes that the path
of Lemma 2.4 from the boundary to the center of a hat can have (Figure 2).
These two cuttings differ in how the crown triangles are attached to the band
and to each other, but they both cut the brim and band triangles in the same
way, into a strip of triangles connected edge-to-edge around the boundary of
the hat.

Figure 2: Two paths from a boundary vertex of a hat, through all three
negatively curved vertices, to the center vertex

Our key new construction is depicted in unfolded (but self-overlapping) form
in Figure 3. It is a hat in which all triangles are acute and isosceles:

  * •

The three brim triangles have apex angle $85^{\circ}$ and base angle
$47.5^{\circ}$.

  * •

The three band triangles have base angle $85^{\circ}$ and apex angle
$10^{\circ}$.

  * •

The three crown triangles are congruent to the band triangles, with base angle
$85^{\circ}$ and apex angle $10^{\circ}$.

As in the construction of Bern et al. [7], this leaves negative curvature
(total angle $425^{\circ}$ from five $85^{\circ}$ angles) at the three non-
central interior angles of the hat, and positive curvature (total angle
$30^{\circ}$) at the center vertex, allowing the lemmas above to apply. The
cut edges of the figure form a tree with a degree-three vertex at one of the
negatively curved vertices of the hat, and a leaf at another negatively curved
vertex, the one at which the self-overlap of the figure occurs, So the cutting
in the figure does not match in detail either of the two path cuttings of
Figure 2. Nevertheless, the brim and band triangles are unfolded as they would
be for either of these two path cuttings. It is evident from the figure that
this unfolding of the brim and band triangles cannot be extended to a one-
piece unfolding of the entire hat: if a crown triangle is attached to the
middle of the three unfolded band triangles (as it is in the figure) then
there is no room on either side of it to attach the other two crown triangles,
and a crown triangle attached to either of the other two band triangles would
overlap the opposite band triangle. We prove this visual observation more
formally below.

Figure 3: A hat made with acute isosceles triangles. Unlike Figure 2, the cuts
made to form the self-overlapping unfolding shown do not form a path.

######  Lemma 2.6.

The hat with acute triangles described above has no single-piece unfolding.

######  Proof 2.7.

As we have already seen in Lemma 2.4, any unfolding (if it exists) must be
along one of the two cut paths depicted in Figure 2. As a result, the
unfolding of the brim and band triangles (but not the crown triangles) must be
as depicted in Figure 3. In this unfolding, the three base sides of the
unfolded band triangles form a polygonal chain whose interior angles
(surrounding the central region of the figure where the pink crown triangles
are attached) can be calculated as $105^{\circ}$.

Figure 4: Each vertex of a regular pentagon lies on the perpendicular bisector
of the opposite side; in a path of three equal edges with the tighter angle
$105^{\circ}$, the last edge overlaps the perpendicular bisector of the first.

A regular pentagon has interior angles of $108^{\circ}$, and has the property
that each vertex lies on the perpendicular bisector of the opposite edge.
Because the interior angles of the chain of base sides of band triangles are
$105^{\circ}$, less than this $108^{\circ}$ angle, it follows that the band
triangle at one end of the chain extends across the perpendicular bisector of
the base edge at the other end of the chain. Further, it does so at a point
closer than the vertex of a regular pentagon sharing this same base edge
(Figure 4).

If a crown triangle were attached to one of the two base edges at the ends of
the chain of three base edges, its altitude would lie along the perpendicular
bisector of the base edge. And because the crown triangle has an apex angle of
$10^{\circ}$, sharper than the angle of an isosceles triangle inscribed within
a regular pentagon, its altitude extends across the perpendicular bisector
farther than the regular pentagon vertex, causing it to overlap with the band
triangle at the other end of the chain of three base edges.

Therefore, attaching a crown triangle to either the first or last of the band
triangle base edges in the chain of these three edges necessarily leads to a
self-overlapping unfolding. However, these two ways of attaching a crown
triangle are the only ones permitted by the two cases depicted in Figure 2.
Attaching a crown triangle to the middle of the three base edges, as in Figure
3, can only be done by cutting along a tree that is not a path. Therefore, no
unfolding exists.

The following construction is straightforward, and will allow us to construct
polyhedra with multiple hats while keeping the hats disjoint from each other.

######  Lemma 2.8.

The hat with acute triangles described above can be realized in three-
dimensional space, lying within a right equilateral-triangle prism whose base
is the boundary of the hat.

##  3 Acute Ununfoldable Polyhedra

We now use these hats to construct a topologically convex ununfoldable
polyhedron.

Figure 5: Tetrahedron with faces replaced by hats

######  Theorem 3.1.

There exists a topologically convex ununfoldable polyhedron whose faces are
all acute isosceles triangles.

######  Proof 3.2.

Replace the four faces of a regular tetrahedron by acute-triangle hats, all
pointing outward, as shown in Figure 5. Because each lies within a prism
having the tetrahedron face as a base, they do not overlap each other in
space. By Lemma 2.6, no hat can be unfolded into a single piece, so any
possible unfolding (even one into multiple pieces) must cut each hat along
some path between two of its three boundary vertices (at least; there may be
more cuts besides these). The four paths formed in this way are disjoint
except at their ends, and connect the four vertices of the tetrahedron,
necessarily forming at least one cycle that separates the tetrahedron into at
least two pieces.

Like the examples of Tarasov, Grünbaum, and Bern et al. [24, 20, 7], the
resulting polyhedron is also star-shaped, with the center of the tetrahedron
in its kernel.

##  4 Stacked Ununfoldable Polyhedra

A stacked polyhedron is a polyhedron that can be formed by repeatedly gluing a
tetrahedron onto a single triangular face of a simpler stacked polyhedron,
starting from a single tetrahedron [19]. To make ununfoldable stacked
polyhedra, we use a similar strategy to our construction of ununfoldable
polyhedra with acute-triangle-faces, in which we replace some faces of a
convex polyhedron by hats. However, the acute-triangle hat that we used
earlier cannot be used as part of a stacked polyhedron: in a stacked
polyhedron, every non-face triangle is subdivided into three smaller
triangles, but that is not true of the outer triangle of Figure 1. Instead, we
use the hat shown in Figure 6. As before, it has three brim triangles, three
band triangles, and three crown triangles, but they are arranged differently
and less symmetrically. We make the brim and band triangles nearly coplanar,
with shapes approximating those shown in the figure, but projecting slightly
out of the figure so that the result can be constructed as a stacked
polyhedron. We choose the crown triangles to be isosceles, and taller than the
isosceles triangles inscribed in regular pentagons, as in our acute-triangle
construction, so that (as viewed in Figure 6) they project out of the figure.

Figure 6: Hat for stacked polyhedra (top view, left, and exploded view as a
stacked polyhedron, right)

######  Lemma 4.1.

The hat described above has no single-piece unfolding.

######  Proof 4.2.

As with our other hat, the center vertex of this hat has positive curvature,
and the other three interior vertices have negative curvature, so by Lemma 2.4
any unfolding of the hat that leaves it in one piece must form a path
consisting of a single edge cutting from the boundary to the crown, two edges
cutting between the band and the crown, and one edge cutting to the center of
the crown.

There are many more cases than there were in Figure 2, but we can avoid case-
based reasoning by arguing that in each case, the brim and band triangles
unfold in such a way that the three edges between the band and crown triangles
form a polygonal chain with interior angles less than the $108^{\circ}$ angles
of the regular pentagon (in fact, close to $60^{\circ}$, because of the way we
have constructed this part of the hat to differ only by a small amount from
the top view shown in Figure 6. Therefore, just as in Figure 4, each edge at
one end of this chain of three edges overlaps the perpendicular bisector of
the edge at the other end of the chain.

Cutting along a path from a boundary edge of the hat to its center vertex
forces the three crown triangles to be attached to the unfolded brim and band
triangles on one of the two edges at the end of this path. However, our
construction makes the three crown triangles tall enough to ensure that, no
matter which of these two edges they are attached to, they will overlap the
edge at the other end of the path at the point where it crosses the
perpendicular bisector.

######  Theorem 4.3.

There exists an ununfoldable stacked polyhedron.

######  Proof 4.4.

We replace the four faces of a regular tetrahedron with the hat described
above. Each such replacement can be realized as a stacking of four tetrahedra
onto the face, so the result is a stacked polyhedron. As in Theorem 3.1, each
hat lies within a prism having the tetrahedron face as a base, so they do not
overlap each other in space; and the set of edges cut in any unfolding must
include at least four paths between the four tetrahedron vertices, necessarily
forming a cycle that cuts one part of the polyhedron surface from the rest.

A stacked hat with the same combinatorial structure as the one used in this
construction, with the center vertex positively curved and the surrounding
three vertices negatively curved, cannot be formed from acute triangles,
because that would leave the degree-four vertex with positive curvature. We
leave as an open question whether it is possible for an ununfoldable stacked
polyhedron to have all faces acute.

##  5 Very Ununfoldable Polyhedra

Both families of examples above can be made into very ununfoldable families.
In both cases, the approach is the same: instead of starting from a
tetrahedron, we start from a polyhedron with many triangular faces, and show
that attaching hats to more and more triangles requires more and more unfolded
pieces.

######  Theorem 5.1.

There exist topologically convex polyhedra with acute isosceles triangle faces
such that any unfolding formed by cutting along edges into multiple non-self-
overlapping pieces requires an unbounded number of pieces.

######  Proof 5.2.

For any integer $k\geq 1$, refine the regular tetrahedron by subdividing each
edge into $k$ equal-length edges and subdivide each face into a regular grid
of $\sum_{i=1}^{k}(2i-1)=k^{2}$ equilateral triangles of side length $1/k$,
for a total of $4k^{2}$ faces and (by inclusion-exclusion)
$\sum_{i=1}^{k+1}i-6(k+1)+4=2k^{2}+2$ vertices. Replace each equilateral
triangular face by an acute-triangle hat pointing outward. As in Theorem 3.1,
each hat lies within a prism having the face of the tetrahedron as a base, so
they do not overlap each other in space; and any unfolding into multiple
pieces must, in each hat, either cut along a cycle within the hat or cut along
some path connecting two of its three boundary vertices. Let $c$ be the number
of cycles within hats cut in this way, so that we have a system of at least
$4k^{2}+c$ disjoint paths connecting pairs of subdivided-tetrahedron vertices.

Now consider cutting the polyhedron surface along these paths, one by one.
Each cut either connects two subdivided-tetrahedron vertices that were not
previously connected along the system of cuts, or two subdivided-tetrahedron
vertices that were previously connected. If cutting along a path connects two
vertices that were not previously connected, it reduces the number of
connected components among these vertices; this case can happen at most
$2k^{2}+1$ times. If cutting along a path connects two vertices that were
previously connected, then that path and the path through which they were
previously connected form a Jordan curve that separates off two parts of the
surface from each other. Because there are $4k^{2}-c$ paths connecting pairs
of subdivided-tetrahedron vertices, only $2k^{2}+1$ of which can form new
connections, this case must happen at least $2k^{2}-1-c$ times. Because the
surface started with a single piece and undergoes at least $2k^{2}-1-c$
separations, it ends up with at least $2k^{2}-c$ pieces, which together with
the $c$ additional pieces formed by cycles within hats, form a total of at
least $2k^{2}$ pieces.

######  Theorem 5.3.

There exist topologically convex stacked polyhedra such that any unfolding
formed by cutting along edges into multiple non-self-overlapping pieces
requires an unbounded number of pieces.

######  Proof 5.4.

For any integer $k\geq 0$, refine the regular tetrahedron by choosing any face
and attaching to the face a very shallow tetrahedron whose apex is near the
in-center of the face, effectively splitting the face into three faces, and
repeating this process a total of $k$ times. Because each attachment increases
the number of faces by $2$ and the number of vertices by $1$, the result is a
stacked polyhedron with $4+2k$ triangular faces (not necessarily equilateral)
and $4+k$ vertices. Replace each triangle with a version of the hat from
Section 4 pointed outward, using the availability flexibility to make the
interface between the band and crown an equilateral triangle near the in-
center of the original triangle. As in Theorem 4.3, the result is a stacked
polyhedron; each hat lies within a prism having the face of the tetrahedron as
a base, so they do not overlap each other in space; and any unfolding into
multiple pieces must cut each hat along some path connecting two of its three
boundary vertices. As in Theorem 5.1, at most $3+k$ such paths can decrease
the number of connected components among the $4+k$ vertices, leaving at least
$1+k$ paths that separate the surface into at least $2+k$ pieces.

## Acknowledgments

This research was initiated during the Virtual Workshop on Computational
Geometry organized by E. Demaine on March 20–27, 2020. We thank the other
participants of that workshop for helpful discussions and providing an
inspiring atmosphere.

## References

  * [1] Zachary Abel and Erik D. Demaine.  Edge-Unfolding Orthogonal Polyhedra is Strongly NP-Complete.  In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011), 2011.  URL: https://www.cccg.ca/proceedings/2011/papers/paper43.pdf.
  * [2] Zachary Abel, Erik D. Demaine, and Martin L. Demaine.  A topologically convex vertex-ununfoldable polyhedron.  In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), Toronto, August 10–12, 2011, 2011.  URL: https://cccg.ca/proceedings/2011/papers/paper85.pdf.
  * [3] Pankaj K. Agarwal, Boris Aronov, Joseph O’Rourke, and Catherine A. Schevon.  Star unfolding of a polytope with applications.  SIAM Journal on Computing, 26(6):1689–1713, 1997.  doi:10.1137/S0097539793253371.
  * [4] Hugo A. Akitaya, Erik D. Demaine, David Eppstein, Tomohiro Tachi, and Ryuhei Uehara.  Minimal ununfoldable polyhedron.  In Abstracts from the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2019), pages 27–28, Tokyo, Japan, September 2019.  URL: https://erikdemaine.org/papers/MinimalUnunfoldable_JCDCGGG2019/.
  * [5] Boris Aronov and Joseph O’Rourke.  Nonoverlap of the star unfolding.  Discrete & Computational Geometry, 8(3):219–250, 1992.  doi:10.1007/BF02293047.
  * [6] Nicholas Barvinok and Mohammad Ghomi.  Pseudo-edge unfoldings of convex polyhedra.  Discrete & Computational Geometry, 2019.  doi:10.1007/s00454-019-00082-1.
  * [7] Marshall Bern, Erik D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, and Jack Snoeyink.  Ununfoldable polyhedra with convex faces.  Computational Geometry: Theory & Applications, 24(2):51–62, 2003.  doi:10.1016/S0925-7721(02)00091-3.
  * [8] Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Mark H. Overmars, Joseph O’Rourke, Steve Robbins, and Sue Whitesides.  Unfolding some classes of orthogonal polyhedra.  In Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG 1998), 1998.  URL: https://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-unfolding.ps.gz.
  * [9] Jindong Chen and Yijie Han.  Shortest paths on a polyhedron.  In Proceedings of the 6th Annual Symposium on Computational Geometry (SoCG 1990). ACM Press, 1990.  doi:10.1145/98524.98601.
  * [10] Mirela Damian, Erik D. Demaine, Robin Flatland, and Joseph O’Rourke.  Unfolding genus-2 orthogonal polyhedra with linear refinement.  Graphs and Combinatorics, 33(5):1357–1379, 2017.  doi:10.1007/s00373-017-1849-5.
  * [11] Erik D. Demaine, Martin L. Demaine, David Eppstein, and Joseph O’Rourke.  Some polycubes have no edge-unzipping.  Electronic preprint arxiv:1907.08433, 2019.
  * [12] Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara.  Zipper unfoldability of domes and prismoids.  In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada August 8th–10th, 2013, 2013\.  URL: https://cccg.ca/proceedings/2013/papers/paper_10.pdf.
  * [13] Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, and Joseph O’Rourke.  Vertex-unfoldings of simplicial manifolds.  In Discrete Geometry: In honor of W. Kuperberg’s 60th birthday, volume 253 of Pure and Applied Mathematics, pages 215–228. Marcel Dekker, 2003.
  * [14] Erik D. Demaine and Anna Lubiw.  A generalization of the source unfolding of convex polyhedra.  In Alberto Márquez, Pedro Ramos, and Jorge Urrutia, editors, Revised Papers from the 14th Spanish Meeting on Computational Geometry, volume 7579 of Lecture Notes in Computer Science, pages 185–199, Alcalá de Henares, Spain, June 2011.  doi:10.1007/978-3-642-34191-5_18.
  * [15] Erik D. Demaine and Joseph O’Rourke.  Geometric Folding Algorithms: Linkages, Origami, Polyhedra.  Cambridge University Press, July 2007.
  * [16] Albrecht Dürer.  The Painter’s Manual: A Manual of Measurement of Lines, Areas, and Solids by Means of Compass and Ruler Assembled by Albrecht Dürer for the Use of All Lovers of Art with Appropriate Illustrations Arranged to be Printed in the Year MDXXV.  Abaris Books, Inc., New York, 1977.  English translation of Unterweysung der Messung mit dem Zirkel un Richtscheyt in Linien Ebnen und Gantzen Corporen, 1525.
  * [17] Michael Friedman.  A History of Folding in Mathematics: Mathematizing the Margins.  Birkhäuser, 2018.  See in particular page 47.  doi:10.1007/978-3-319-72487-4.
  * [18] Mohammad Ghomi.  Affine unfoldings of convex polyhedra.  Geometry & Topology, 18:3055–3090, 2014.  doi:10.2140/gt.2014.18.3055.
  * [19] Branko Grünbaum.  A convex polyhedron which is not equifacettable.  Geombinatorics, 10(4):165–171, 2001.  URL: https://sites.math.washington.edu/~grunbaum/Nonequifacettablesphere.pdf.
  * [20] Branko Grünbaum.  No-net polyhedra.  Geombinatorics, 11:111–114, 2002.  URL: https://www.math.washington.edu/~grunbaum/Nonetpolyhedra.pdf.
  * [21] Joseph O’Rourke.  Edge-unfolding nearly flat convex caps.  In Bettina Speckmann and Csaba D. Tóth, editors, Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), volume 99 of LIPIcs, pages 64:1–64:14, 2018.  doi:10.4230/LIPIcs.SoCG.2018.64.
  * [22] Joseph O’Rourke.  Unfolding polyhedra.  Electronic preprint arxiv:1908.07152, 2019.
  * [23] G. C. Shephard.  Convex polytopes with convex nets.  Mathematical Proceedings of the Cambridge Philosophical Society, 78(3):389–403, 1975.  doi:10.1017/s0305004100051860.
  * [24] A. S. Tarasov.  Polyhedra that do not admit natural unfoldings.  Uspekhi Matematicheskikh Nauk, 54(3):185–186, 1999.  doi:10.1070/rm1999v054n03ABEH000171.
  * [25] Magnus J. Wenninger.  Polyhedron Models.  Cambridge University Press, 1971.


# A tight upper bound on the number of non-zero weights of a quasi-cyclic code
††thanks: This research is supported by Natural Science Foundation of China
(12071001).

Xiaoxiao Li1, Minjia Shi1
1School of Mathematical Sciences, Anhui University, Hefei, 230601, China

###### Abstract

Let $\mathcal{C}$ be a quasi-cyclic code of index $l(l\geq 2)$. Let $G$ be the
subgroup of the automorphism group of $\mathcal{C}$ generated by $\rho^{l}$
and the scalar multiplications of $\mathcal{C}$, where $\rho$ denotes the
standard cyclic shift. In this paper, we find an explicit formula of orbits of
$G$ on $\mathcal{C}\setminus\\{\mathbf{0}\\}$. Consequently, an explicit upper
bound on the number of non-zero weights of $\mathcal{C}$ is immediately
derived and a necessary and sufficient condition for codes meeting the bound
is exhibited. In particular, we list some examples to show the bounds are
tight. Our main result improves and generalizes some of the results in [21].

Keywords: Quasi-cyclic code, Hamming weight, upper bound, group action

##  1 Introduction

The importance of the number of distinct distances in a code was pointed out
by Delsarte in 1973 in [8]. In that paper, he studied for a given code $C$,
the relations between this value, the number of distinct distances for the
dual code $C^{\bot}$, and the minimum distances of $C$ and $C^{\bot}$,
obtaining interesting results on the weight distributions of cosets of a code.
It is easy to see that when one restricts the study to linear codes, then this
number coincides with the number of non-zero weights. The early researches on
determining the number of weights of a given linear code can be seen in [1, 2,
3, 11, 12, 17].

For a general linear code, it seems very difficult to obtain an explicit
formula for the number of non-zero weights of the code. A more modest goal is
to find acceptable bounds on the number of non-zero weights of a linear code.
Indeed, there have been several recent works investigating lower and upper
bounds on the number of non-zero weights of linear codes. Alderson [1]
determined necessary and sufficient conditions for the existence of full
weight spectrum codes, i.e., codes satisfy that there exist codewords of each
weight less than or equal to the code length. Shi $et$ $al$. in a series of
papers [20, 21, 22] studied the number of non-zero weights of linear codes.
Shi, Li, Neri and Sol$\acute{e}$ [20] derived upper and lower bounds on the
number of non-zero weights of cyclic codes. Chen and Zhang [7] obtained the
explicit upper bound on the number of non-zero weights of a simple-root cyclic
code and exhibit a necessary and sufficient condition for cyclic codes meeting
the bound. Moreover, in [7], their results improves and generalizes some of
the results in [20].

Motivated by the work [7] and [21], the objective of this paper is to
establish a tight upper bound on the number of non-zero weights of a quasi-
cyclic code of index $l(l\geq 2)$ with simple root. In [7], Chen and Zhang
pointed out the number of non-zero weights of a linear code is bounded from
above by the number of orbits of the automorphism group acting on the code.
Let $\mathcal{C}$ be a quasi-cyclic code of length $lm$ and index $l$(co-index
$m$). Let $G$ be the subgroup of $Aut(\mathcal{C})$ (the automorphism group of
$\mathcal{C}$) generated by $\rho^{l}$ and the scalar multiplications of
$\mathcal{C}$, where $\rho$ denotes the standard cyclic shift. The problem is
therefore converted to finding the number of orbits of $G$ on
$\mathcal{C}^{*}\setminus\\{\mathbf{0}\\}$. An explicit formula for the number
of orbits of $G$ on $\mathcal{C}^{*}$ is obtained. Consequently, an explicit
upper bound on the number of non-zero weights of $\mathcal{C}$ is immediately
derived and a necessary and sufficient condition for quasi-cyclic codes
meeting the bound is exhibited. We also note that [21, Section III] gave some
upper bounds on the number of non-zero weights of a special class of strongly
quasi-cyclic code, i.e., a quasi-cyclic code of co-index $m$ such that all its
nonzero codewords have period $m$. Comparing our results with those in [21,
Section III], our results remove the constrain “strongly” and characterize a
necessary and sufficient condition for the codes meeting the bounds.

The material is arranged as follows. Section 2 contains the necessary
terminology and definitions on linear codes, quasi-cyclic codes and group
actions. Section 3 presents the main results (see Theorems 1 and 2), which
give the tight upper bounds on the number of weights that a quasi-cyclic code
can have. Section 4 gives the proofs of Theorems 1 and 2 by counting the
number of orbits of $G$ on $\mathcal{C}^{*}$. Several examples in Section 5
show our bound is tight. Finally, we share our conclusions and some open
problems in in Section 6.

##  2 Background material

Let $\mathbb{F}_{q}$ be the finite field with $q$ elements and let
$\mathbb{F}^{*}_{q}=\mathbb{F}_{q}\setminus\\{0\\}$ be the multiplicative
group of the finite field $\mathbb{F}_{q}$. In this section, we review some
previously known facts about linear codes, automorphism group of a linear
code, and recall some notions and results about quasi-cyclic codes.

###  2.1 Linear codes and group actions

Let $\mathbb{F}_{q}^{n}$ be the set of all $n$-tuples whose coordinates belong
to $\mathbb{F}_{q}$. A linear code $\mathcal{C}$ of length $n$ over
$\mathbb{F}_{q}$ is a vector subspace of $\mathbb{F}_{q}^{n}$ over
$\mathbb{F}_{q}$. The dimension of the code is its dimension as an
$\mathbb{F}_{q}$-vector space, and is denoted by $k$. A linear code of length
$n$ and dimension $k$ over $\mathbb{F}_{q}$ will be denoted for brevity by
$[n,k]_{q}$ code. The elements of $\mathcal{C}$ are called codewords.

The Hamming weight of $\mathbf{x}\in\mathbb{F}_{q}^{n}$ is the number of
indices $i$ where $x_{i}\neq 0$, and it is denoted by $wt_{H}(\mathbf{x})$.
The set of weights of a linear code $\mathcal{C}$ (including the $\mathbf{}0$)
is denoted by $wt(\mathcal{C})$, and the number of nonzero weights of
$\mathcal{C}$ by $s(\mathcal{C})$, i.e.
$wt(\mathcal{C})=\\{wt_{H}(\mathbf{c})|\mathbf{c}\in\mathcal{C}\\}$ and
$s(C)=|wt(\mathcal{C})\setminus\\{0\\}|=|wt(\mathcal{C})|-1$.

######  Definition 1.

Let $\mathcal{C}$ be a linear code of length $n$ over $\mathbb{F}_{q}$. The
automorphism group of $\mathcal{C}$, denoted by $Aut(\mathcal{C})$, consists
of all $n\times n$ monomial matrices $A$ over $\mathbb{F}_{q}$ such that
$\mathbf{c}A\in\mathcal{C}$ for all $\mathbf{c}\in\mathcal{C}$.

Now we recall the result which is the number of non-zero weights of
$\mathcal{C}$ is bounded from the number of $G$-orbits, where $G$ is a
subgroup of $Aut(\mathcal{C})$, see [7, 19].

######  Proposition 1.

[7] Let $\mathcal{C}$ be a linear code of length $n$ over $\mathbb{F}_{q}$
with $s(\mathcal{C})$ non-zero weights and let $Aut(\mathcal{C})$ be the
automorphism group of $\mathcal{C}$. Suppose that $G$ is a subgroup of
$Aut(\mathcal{C})$. If the number of orbits of $G$ on
$\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to $N$, then
$s(\mathcal{C})\leq N$. Moreover, the equality holds if and only if for any
two non-zero codewords $\mathbf{c}_{1},\mathbf{c}_{2}\in\mathcal{C}^{*}$ with
the same weight, there exists an automorphism $A\in G$ such that
$\mathbf{c}_{1}A=\mathbf{c}_{2}$.

In order to determine the number of orbits of $G$ on $\mathcal{C}^{*}$, we
need two important lemmas from [7, 13].

######  Lemma 1.

[13] Let $\mathcal{C}$ be a linear code of length $n$ over $\mathbb{F}_{q}$
and let $Aut(\mathcal{C})$ be the automorphism group of $\mathcal{C}$. Suppose
that $G$ is a subgroup of $Aut(\mathcal{C})$. Then, the cardinality of
$G\backslash\mathcal{C}^{*}$ (the set of all the orbits of $G$ on
$\mathcal{C}^{*}$) is equal to

$|G\backslash\mathcal{C}^{*}|=\frac{1}{|G|}\sum_{g\in G}|\mbox{Fix}(g)|,$

where $\mbox{Fix}(g)=\\{\mathbf{c}\in\mathcal{C}|g\mathbf{c}=\mathbf{c}\\}$.

######  Lemma 2.

[7] Let $G$ be a finite group acting on a finite set $X$ and let $H$ be a
normal subgroup of $G$. It is clear that $H$ naturally acts on $X$. Suppose
the set of $H$-orbits are denoted by $H\backslash X=\\{Hx|x\in X\\}$. Then the
factor group $G/H$ acts on $H\backslash X$ and

$|G\backslash X|=|(G/H)\backslash(H\backslash X)|.$

###  2.2 Quasi-cyclic codes

In this subsection, we recall some definitions and results about quasi-cyclic
codes. For more detail information about cyclic codes and quasi-cyclic codes,
readers may refer to [5, 6, 9, 16, 15, 14, 18, 10].

Let $a_{1},a_{2},\ldots,a_{r}$ be integers, where $r\geq 2$ is a positive
integer. Let $\mbox{gcd}(a_{1},a_{2},\ldots,a_{r})$ be the greatest common
divisor of $a_{1},a_{2},\ldots,a_{r}$. Let $m$ be a positive integer with
$\mbox{gcd}(m,q)=1$. Let $\mathbb{F}_{q}[x]$ denote the polynomials in the
indeterminate $x$ with coefficients in $\mathbb{F}_{q}$. Let $\langle
x^{m}-1\rangle$ denote the ideal generated by $x^{m}-1$ in
$\mathbb{F}_{q}[x]$. Then, we have the quotient ring
$R_{m}=\mathbb{F}_{q}[x]/\langle x^{m}-1\rangle$. Actually, cyclic codes of
length $m$ over $\mathbb{F}_{q}$ are essentially ideals of $R_{m}$.

We denote by $\rho$ the standard shift operator on $\mathbb{F}^{n}_{q}$. A
linear code is said to be quasi-cyclic of index $l$ or $l$-quasi-cyclic code
if and only if it is invariant under $\rho^{l}$. Let $\mathcal{C}$ be a quasi-
cyclic code over $\mathbb{F}_{q}$ of length $n=lm$ and index $l$. Let

$\mathbf{c}=(c_{00},c_{01},\ldots,c_{0,l-1},c_{10},c_{11},\ldots,c_{1,l-1},\ldots,c_{m-1,0},c_{m-1,1},\ldots,c_{m-1,l-1})$

denote a codeword in $\mathcal{C}$.

Define a map $\phi$: $\mathbb{F}_{q}^{lm}\rightarrow R^{l}_{m}$ by

$\phi(\mathbf{c})=(\mathbf{c}_{0}(x),\mathbf{c}_{1}(x),\ldots,\mathbf{c}_{l-1}(x))\in
R_{m}^{l},$

where $\mathbf{c}_{j}(x)=\sum_{i=0}^{m-1}c_{ij}x^{i}\in R_{m}$. It is known
(cf. [14], for instance) that $\phi$ induces a one-to-one correspondence
between quasi-cyclic codes over $\mathbb{F}_{q}$ of index $l$ and length $lm$
and linear codes over $R_{m}$ of length $l$.

It is well known that every minimal ideal of $R_{m}$ is generated uniquely by
a primitive idempotent of $R_{m}$, see [10]. There is a one-to-one
correspondence between the primitive idempotents of $R_{m}$ and the
$q$-cyclotomic cosets modulo $m$. Let $m^{\prime}$ be the order of $q$ modulo
$m$, i.e., $m^{\prime}$ is the least positive integer such that $m$ is a
divisor of $q^{m^{\prime}}-1$. Suppose $\zeta$ is a primitive $m$-th root of
unity in $\mathbb{F}_{q^{m^{\prime}}}$ and there are $s+1$ distinct
$q$-cyclotomic cosets $\\{\Gamma_{j}\\}_{j=0}^{s}$ modulo $n$ with
$\Gamma_{0}=\\{i_{0}=0\\}$ and
$\Gamma_{t}=\\{i_{t},i_{t}q,i_{t}q^{2},\ldots,i_{t}q^{k_{t}-1}\\}$ for $1\leq
t\leq s$, where $k_{t}$ is the cardinality of the $q$-cyclotomic coset
$\Gamma_{t}$ for $0\leq t\leq s$. Then the quotient ring
$\mathbb{F}_{q^{m^{\prime}}}[x]/\langle x^{m}-1\rangle$ has exactly $m$
primitive idempotents given by

$e_{i}=\frac{1}{m}\sum_{j=0}^{m-1}\zeta^{-ij}x^{j}\ \ \ \ \mbox{for}\ 0\leq
i\leq m-1,$

see [6]. Moreover, $R_{m}=\mathbb{F}_{q}[x]/\langle x^{m}-1\rangle$ has
exactly $s$ primitive idempotents given by

$\varepsilon_{t}=\sum_{j\in\Gamma_{t}}e_{j}\ \ \ \mbox{for}\ \ 0\leq t\leq s.$

According to [10, Theorem 4.3.8], $R_{m}$ is the vector space direct sum of
the minimal ideals $R_{m}\varepsilon_{t}$ for $0\leq t\leq s$, in symbols,

$R_{m}=R_{m}\varepsilon_{0}\bigoplus
R_{m}\varepsilon_{1}\bigoplus\cdots\bigoplus R_{m}\varepsilon_{s}.$

Using the Discrete Fourier Transform, we have, for each $0\leq t\leq s$,

$R_{m}\varepsilon_{t}=\bigg{\\{}\sum_{j=0}^{k_{t}-1}\big{(}\sum_{u=0}^{k_{t}-1}c_{u}\zeta^{li_{t}q^{j}}\big{)}e_{i_{t}q^{j}}|c_{j}\in\mathbb{F}_{q}\bigg{\\}}.$
(1)

Therefore, $R_{m}^{l}$ is the direct sum of $(R_{m}\varepsilon_{t})^{l}$ for
$0\leq t\leq s$, in symbols,

$(R_{m})^{l}=(R_{m}\varepsilon_{0})^{l}\bigoplus(R_{m}\varepsilon_{1})^{l}\bigoplus\cdots\bigoplus(R_{m}\varepsilon_{s})^{l}.$

It follows that every $R_{m}$-linear code $\phi(\mathcal{C})$ of length $l$
can be decomposed as the direct sum

$\phi(\mathcal{C})=C_{0}\bigoplus C_{1}\bigoplus\cdots\bigoplus C_{s},$ (2)

where $C_{t}$ is a linear code over $R_{m}\varepsilon_{t}$ of length $l$ for
$0\leq t\leq s$ and $\mathcal{C}$ is a quasi-cyclic code over $\mathbb{F}_{q}$
of length $n=lm$ and index $l$. Actually, for each $1\leq t\leq s$, $C_{t}$ is
a subset of $(R_{m}\varepsilon_{t})^{l}$.

##  3 Statement of main results

In this section we give a tight upper bound on $s(\mathcal{C})$ which is the
number of non-zero weights of a quasi-cyclic code $\mathcal{C}$. In this
paper, we use two obvious automorphisms of a quasi-cyclic code $\mathcal{C}$:
one is the cyclic shift $\rho^{l}$ whose $\rho$ is the standard shift operator
and $l$ is the index of $\mathcal{C}$, and the other is the scalar
multiplication. According to Proposition 1, if the number of the orbits of the
group generated by these two automorphisms on $\mathcal{C}$ can be figured
out, then we have a upper bound of $s(\mathcal{C})$, naturally.

The main results of this paper are given below.

######  Theorem 1.

Let $\mathcal{C}$ be a quasi-cyclic code of length $lm$ and index $l$ over
$\mathbb{F}_{q}$. Suppose that

$\mathcal{C}=C_{t_{1}}\bigoplus C_{t_{2}}\bigoplus\cdots\bigoplus C_{t_{U}},$

where $0\leq t_{1}<t_{2}<\cdots<t_{U}\leq s$, $C_{t_{j}}$ is a linear code
over $R_{m}\varepsilon_{t_{j}}$ of length $l$ and also is a $[n=lm,K_{t_{j}}]$
quasi-cyclic code over $\mathbb{F}_{q}$ for $1\leq j\leq U$. Suppose that the
primitive idempotent $\varepsilon_{t_{j}}$ corresponds to the $q$-cyclotomic
coset $\\{i_{t_{j}},i_{t_{j}}q,\ldots,i_{t_{j}}q^{k_{t_{j}}-1}\\}$ for each
$1\leq j\leq U$. Then the number of orbits of $\langle\rho^{l}\rangle$ on
$\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}\frac{\mbox{gcd}(m,i_{t_{j_{1}}},i_{t_{j_{2}}},\ldots,i_{t_{j_{u}}})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)}{m},$

which is denoted by $N$. In particular,

$s(\mathcal{C})\leq N,$

with equality if and only if for any codewords
$\mathbf{c}_{1},\mathbf{c}_{2}\in\mathcal{C}^{*}$ with the same weight, there
exists an integer $i$ such that $\rho^{il}(\mathbf{c}_{1})=\mathbf{c}_{2}$.

Let $U=2$, then the formula in Theorem 1 can be concise and clear. As a direct
application of Theorem 1, we immediately obtain the following corollary.

######  Corollary 1.

Let $\mathcal{C}$ be a quasi-cyclic code of length $lm$ and index $l$ over
$\mathbb{F}_{q}$. Suppose that

$\mathcal{C}=C_{t_{1}}\bigoplus C_{t_{2}},$

where $0\leq t_{1}<t_{2}\leq s$, $C_{t_{j}}$ is a linear code over
$R_{m}\varepsilon_{t_{j}}$ of length $l$ and also is a $[n=lm,K_{t_{j}}]$
quasi-cyclic code over $\mathbb{F}_{q}$ for $1\leq j\leq 2$. Suppose that the
primitive idempotent $\varepsilon_{t_{j}}$ corresponds to the $q$-cyclotomic
coset $\\{i_{t_{j}},i_{t_{j}}q,\ldots,i_{t_{j}}q^{k_{t_{j}}-1}\\}$ for each
$1\leq j\leq 2$. Then the number of orbits of $\langle\rho^{l}\rangle$ on
$\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\frac{\mbox{gcd}(m,i_{t_{1}},i_{t_{2}})(q^{K_{t_{1}}}-1)(q^{K_{t_{2}}}-1)}{m}+\frac{\mbox{gcd}(m,i_{t_{1}})(q^{K_{t_{1}}}-1)}{m}+\frac{\mbox{gcd}(m,i_{t_{2}})(q^{K_{t_{2}}}-1)}{m}.$

######  Theorem 2.

Let $\mathcal{C}$ be a quasi-cyclic code of length $lm$ and index $l$ over
$\mathbb{F}_{q}$. Suppose that

$\mathcal{C}=C_{t_{1}}\bigoplus C_{t_{2}}\bigoplus\cdots\bigoplus C_{t_{U}},$

where $0\leq t_{1}<t_{2}<\cdots<t_{U}\leq s$, $C_{t_{j}}$ is a linear code
over $R_{m}\varepsilon_{t_{j}}$ of length $l$ and is also a $[n=lm,K_{t_{j}}]$
quasi-cyclic code over $\mathbb{F}_{q}$ for $1\leq j\leq U$. Suppose that the
primitive idempotent $\varepsilon_{t_{j}}$ corresponds to the $q$-cyclotomic
coset $\\{i_{t_{j}},i_{t_{j}}q,\ldots,i_{t_{j}}q^{k_{t_{j}}-1}\\}$ for each
$1\leq j\leq U$. Then the number of orbits of $\langle\rho^{l}\rangle\times M$
on $\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}\frac{\mbox{gcd}(m,i_{t_{j_{1}}},i_{t_{j_{2}}},\ldots,i_{t_{j_{u}}})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)}{m(q-1)}$
$\cdot\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{j_{1}}})},\ldots,\frac{m}{\mbox{gcd}(m,i_{t_{j_{u}}})}\bigg{)},$

which is denoted by $N$. In particular,

$s(\mathcal{C})\leq N,$

with equality if and only if for any codewords
$\mathbf{c}_{1},\mathbf{c}_{2}\in\mathcal{C}^{*}$ with the same weight, there
exists an integer $i$ and an element $a\in\mathbb{F}_{q}^{*}$ such that
$\rho^{il}(a\mathbf{c}_{1})=\mathbf{c}_{2}$.

By virtue of Theorem 2, we immediately obtain the following corollary.

######  Corollary 2.

Let $\mathcal{C}$ be a quasi-cyclic code of length $lm$ and index $l$ over
$\mathbb{F}_{q}$. Suppose that

$\mathcal{C}=C_{t_{1}}\bigoplus C_{t_{2}},$

where $0\leq t_{1}<t_{2}\leq s$, $C_{t_{j}}$ is a linear code over
$R_{m}\varepsilon_{t_{j}}$ of length $l$ and is also a $[n=lm,K_{t_{j}}]$
quasi-cyclic code over $\mathbb{F}_{q}$ for $1\leq j\leq 2$. Suppose that the
primitive idempotent $\varepsilon_{t_{j}}$ corresponds to the $q$-cyclotomic
coset $\\{i_{t_{j}},i_{t_{j}}q,\ldots,i_{t_{j}}q^{k_{t_{j}}-1}\\}$ for each
$1\leq j\leq 2$. Then the number of orbits of $\langle\rho^{l}\rangle\times M$
on $\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\begin{split}&\frac{\mbox{gcd}(m,i_{t_{1}},i_{t_{2}})(q^{K_{t_{1}}}-1)(q^{K_{t_{2}}}-1)}{m(q-1)}\cdot\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{1}})},\frac{m}{\mbox{gcd}(m,i_{t_{2}})}\bigg{)}\\\
&+\frac{\mbox{gcd}(m,i_{t_{1}})(q^{K_{t_{1}}}-1)}{m(q-1)}\cdot\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{1}})}\bigg{)}\\\
&+\frac{\mbox{gcd}(m,i_{t_{2}})(q^{K_{t_{2}}}-1)}{m(q-1)}\cdot\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{2}})}\bigg{)}.\end{split}$

##  4 Proofs of main results

This section is divided into three parts. First, we give the statement of some
lemmas. Next, we present the proofs of the main results.

###  4.1 Statement of some lemmas

Recall that $R_{m}=\mathbb{F}_{q}[x]/\langle x^{m}-1\rangle$. We have the
following two $\mathbb{F}_{q}$-linear maps on $R_{m}^{l}$, denoted by
$\rho^{l}$ and $\sigma_{a}$, respectively:

$\rho^{l}:R^{l}_{m}\rightarrow R^{l}_{m}$
$\rho^{l}\bigg{(}\sum_{i=0}^{m-1}c_{i0}x^{i},\sum_{i=0}^{m-1}c_{i1}x^{i},\ldots,\sum_{i=0}^{m-1}c_{i,l-1}x^{i}\bigg{)}=\bigg{(}\sum_{i=0}^{m-1}c_{i0}x^{i+1},\sum_{i=0}^{m-1}c_{i1}x^{i+1},\ldots,\sum_{i=0}^{m-1}c_{i,l-1}x^{i+1}\bigg{)}$

is a $\mathbb{F}_{q}$-vector space isomorphism of $R_{m}^{l}$, and for any
fixed element $a\in\mathbb{F}_{q}^{*}$,

$\sigma_{a}:R^{l}_{m}\rightarrow R^{l}_{m}$
$\sigma_{a}\bigg{(}\sum_{i=0}^{m-1}c_{i0}x^{i},\sum_{i=0}^{m-1}c_{i1}x^{i},\ldots,\sum_{i=0}^{m-1}c_{i,l-1}x^{i}\bigg{)}=\bigg{(}\sum_{i=0}^{m-1}ac_{i0}x^{i},\sum_{i=0}^{m-1}ac_{i1}x^{i},\ldots,\sum_{i=0}^{m-1}ac_{i,l-1}x^{i}\bigg{)}$

is a $\mathbb{F}_{q}$-vector space isomorphism of $R_{m}^{l}$. Both $\rho^{l}$
and $\sigma_{a}$ are also linear maps on $\mathbb{F}_{q}^{n}$ with $n=lm$,
which satisfy that for any element $\mathbf{c}$ of $\mathbb{F}_{q}^{n}$ and

$\mathbf{c}=(c_{00},c_{01},\ldots,c_{0,l-1},c_{10},c_{11},\ldots,c_{1,l-1},\ldots,c_{m-1,0},c_{m-1,1},\ldots,c_{m-1,l-1}),$

then

$\rho^{l}(\mathbf{c})=(c_{10},c_{11},\ldots,c_{1,l-1},c_{20},c_{21},\ldots,c_{2,l-1},\ldots,c_{00},c_{01},\ldots,c_{0,l-1})$

and

$\sigma_{a}(\mathbf{c})=(ac_{00},ac_{01},\ldots,ac_{0,l-1},ac_{10},ac_{11},\ldots,ac_{1,l-1},\ldots,ac_{m-1,0},ac_{m-1,1},\ldots,ac_{m-1,l-1}).$

For any quasi-cyclic code $\mathcal{C}$ of length $n=lm$ and index $l$, it is
readily seen that both $\rho^{l}$ and $\sigma_{a}$ belong to
$Aut(\mathcal{C})$. We know that $M=\\{\sigma_{a}|a\in\mathbb{F}_{q}^{*}\\}$
is a subgroup of $Aut(\mathcal{C})$. Clearly, the subgroup $M$ is cyclic with
order $q-1$. Since $\mbox{gcd}(l,n)=\mbox{gcd}(l,lm)=l$,
$\langle\rho^{l}\rangle$ is of order $m$. We mainly consider the subgroup of
$Aut(\mathcal{C})$ generated by $\rho^{l}$ and $M$ (denoted by
$\langle\rho^{l},M\rangle$).

Firstly, we consider the action of $\rho^{l}$ on $\mathcal{C}^{*}$. For each
integer $i$ with $0\leq i\leq m-1$, it is easy to check that
$|\mbox{Fix}(\rho^{il})|=|\mbox{Fix}(\rho^{\mbox{gcd}(il,n)})|=|\mbox{Fix}(\rho^{\mbox{gcd}(i,m)l})|$,
where

$\mbox{Fix}(\rho^{il})=\\{\mathbf{c}\in\mathcal{C}^{*}|\rho^{il}(\mathbf{c})=\mathbf{c}\\}.$

For an integer $r$ with $r|m$, the number of integers $i$ satisfying $0\leq
i\leq m-1$ and $\mbox{gcd}(i,m)=r$ is equal to $\varphi(\frac{m}{r})$, where
$\varphi$ is Euler’s totient function. By Lemma 1, one has

$|\langle\rho^{l}\rangle\setminus\mathcal{C}^{*}|=\frac{1}{m}\sum_{i=0}^{m-1}|\mbox{Fix}(\rho^{il})|=\frac{1}{m}\sum_{r|m}\varphi(\frac{m}{r})|\mbox{Fix}(\rho^{rl})|.$
(3)

######  Lemma 3.

Let $\mathcal{C}$ be a $[n=lm,K]$ quasi-cyclic code over $\mathbb{F}_{q}$
which is a linear code over $R_{m}\varepsilon_{t}$. Suppose that the primitive
idempotent $\varepsilon_{t}$ corresponds to the $q$-cyclotomic coset
$\\{i_{t},i_{t}q,\ldots,i_{t}q^{k_{t}-1}\\}$. Then the number of orbits of
$\langle\rho^{l}\rangle$ on
$\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\frac{\mbox{gcd}(m,i_{t})(q^{K}-1)}{m}.$

In particular,

$s(\mathcal{C})\leq\frac{\mbox{gcd}(m,i_{t})(q^{K}-1)}{m},$

with equality if and only if for any codewords
$\mathbf{c}_{1},\mathbf{c}_{2}\in\mathcal{C}^{*}$ with the same weight, there
exists an integer $i$ such that $\rho^{il}(\mathbf{c}_{1})=\mathbf{c}_{2}$.

###### Proof.

By Proposition 1, it is enough to count the number of orbits of
$\langle\rho^{l}\rangle$ on $\mathcal{C}^{*}$. By Eq. (3), we aim to find the
value of $|\mbox{Fix}(\rho^{rl})|$, for each divisor $r$ of $m$. To this end,
let $r$ be a divisor of $m$ and take a typical non-zero element

$\mathbf{c}=\big{(}\mathbf{c}_{0}(x),\mathbf{c}_{1}(x),\ldots,\mathbf{c}_{l-1}(x)\big{)}\in\mathcal{C}^{*},$

where $\mathbf{c}_{u}(x)\in R_{m}\varepsilon_{t}$ for $0\leq u\leq l-1$. By
Eq. (1), for each $0\leq u\leq l-1$,

$\mathbf{c}_{u}(x)=\sum_{j=0}^{k-1}(c_{u0}+c_{u1}\zeta^{i_{t}q^{j}}+\cdots+c_{u,k-1}\zeta^{(k-1)i_{t}q^{j}})e_{i_{t}q^{j}}\in
R_{m}\varepsilon_{t}.$

Note that
$e_{i_{t}q^{j}}=\frac{1}{m}\sum_{v=0}^{m-1}\zeta^{-i_{t}q^{j}v}x^{v}$, and
thus

$\begin{split}x^{r}e_{i_{t}q^{j}}&=\frac{1}{m}\sum_{v=0}^{m-1}\zeta^{-i_{t}q^{j}v}x^{v+r}\\\
&=\zeta^{i_{t}q^{j}r}\frac{1}{m}\sum_{v=0}^{m-1}\zeta^{-i_{t}q^{j}(v+r)}x^{v+r}\\\
&=\zeta^{i_{t}q^{j}r}e_{i_{t}q^{j}}.\end{split}$

Since
$\rho^{l}(\mathbf{c})=\big{(}x\mathbf{c}_{0}(x),x\mathbf{c}_{1}(x),\ldots,x\mathbf{c}_{l-1}(x)\big{)}$,
then we have

$\rho^{rl}(\mathbf{c})=\big{(}x^{r}\mathbf{c}_{0}(x),x^{r}\mathbf{c}_{1}(x),\ldots,x^{r}\mathbf{c}_{l-1}(x)\big{)}$

and

$\begin{split}x^{r}\mathbf{c}_{u}(x)&=x^{r}\bigg{(}\sum_{j=0}^{k-1}(c_{u0}+c_{u1}\zeta^{i_{t}q^{j}}+\cdots+c_{u,k-1}\zeta^{(k-1)i_{t}q^{j}})e_{i_{t}q^{j}}\bigg{)}\\\
&=\sum_{j=0}^{k-1}(c_{u0}+c_{u1}\zeta^{i_{t}q^{j}}+\cdots+c_{u,k-1}\zeta^{(k-1)i_{t}q^{j}})x^{r}e_{i_{t}q^{j}}\\\
&=\sum_{j=0}^{k-1}\zeta^{i_{t}q^{j}r}(c_{u0}+c_{u1}\zeta^{i_{t}q^{j}}+\cdots+c_{u,k-1}\zeta^{(k-1)i_{t}q^{j}})e_{i_{t}q^{j}},\end{split}$

for $0\leq u\leq l-1$. It follows that $\rho^{rl}(\mathbf{c})=\mathbf{c}$ if
and only if $x^{r}\mathbf{c}_{u}(x)=\mathbf{c}_{u}(x)$ for all $0\leq u\leq
l-1$ if and only if $\zeta^{i_{t}q^{j}r}=1$ for all $0\leq j\leq k-1$. Since
$\zeta$ is a primitive $m$-th root of unity and $\mbox{gcd}(m,q)=1$,
$\zeta^{i_{t}q^{j}r}=1$ precisely when $m$ is a divisor of $i_{t}r$
(equivalently, $\frac{m}{r}$ is a divisor of $i_{t}$). This leads to

$|\mbox{Fix}(\rho^{rl})|=\left\\{\begin{array}[]{ll}q^{K}-1,&\mbox{if}\ \
\frac{m}{r}|i_{t}\hbox{;}\\\ 0,&\mbox{if}\ \ \frac{m}{r}\nmid
i_{t}\hbox{.}\end{array}\right.$

By Eq. (3), the number of orbits of $\langle\rho^{l}\rangle$ on
$\mathcal{C}^{*}$ is equal to

$\begin{split}\frac{1}{m}\sum_{i=0}^{m-1}|\mbox{Fix}(\rho^{il})|&=\frac{1}{m}\sum_{r|m}\varphi(\frac{m}{r})|\mbox{Fix}(\rho^{rl})|\\\
&=\frac{q^{K}-1}{m}\sum_{r|m,\frac{m}{r}|i_{t}}\phi(\frac{m}{r})\\\
&=\frac{gcd(m,i_{t})(q^{K}-1)}{m}.\end{split}$

The proof is completed. ∎

Next, we turn to study the action of $\langle\rho^{l},M\rangle$ on
$\mathcal{C}^{*}$, where $\rho$ is the standard shift operator and $l$ is the
index of $\mathcal{C}$, and $M=\\{\sigma_{a}|a\in\mathbb{F}_{q}^{*}\\}$
consists of the scalar multiplications on $\mathcal{C}$. It is easy to check
that $\sigma_{a}\rho^{l}=\rho^{l}\sigma_{a}$ for any $a\in\mathbb{F}_{q}^{*}$.
According to the definitions of $\rho^{l}$ and $M$, we immediately get the
following results.

######  Lemma 4.

The subgroup $\langle\rho^{l},M\rangle$ of $Aut(\mathcal{C})$ is the direct
product of $\rho^{l}$ and $M$, that is

$\langle\rho^{l},M\rangle=\langle\rho^{l}\rangle\times M.$

In particular, $\langle\rho^{l},M\rangle$ is of order $m(q-1)$.

Based on Lemma 4, we use the method provided in Lemma 2 to determine the
number of orbits of the group $\langle\rho^{l},M\rangle$ acting on the quasi-
cyclic code.

######  Lemma 5.

Let $\mathcal{C}$ be a $[n=lm,K]$ quasi-cyclic code over $\mathbb{F}_{q}$
which is a linear code over $R_{m}\varepsilon_{t}$. Suppose that the primitive
idempotent $\varepsilon_{t}$ corresponds to the $q$-cyclotomic coset
$\\{i_{t},i_{t}q,\ldots,i_{t}q^{k-1}\\}$. Then the number of orbits of
$\langle\rho^{l}\rangle\times M$ on
$\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\frac{\mbox{gcd}\big{(}m,(q-1)i_{t}\big{)}(q^{K}-1)}{m(q-1)}.$

In particular,

$s(\mathcal{C})\leq\frac{\mbox{gcd}\big{(}m,(q-1)i_{t}\big{)}(q^{K}-1)}{m(q-1)},$

with equality if and only if for any codewords
$\mathbf{c}_{1},\mathbf{c}_{2}\in\mathcal{C}^{*}$ with the same weight, there
exists an integer $i$ and an element $a\in\mathbb{F}_{q}^{*}$ such that
$\rho^{il}(a\mathbf{c}_{1})=\mathbf{c}_{2}$.

###### Proof.

It is readily seen that the multiplicative cyclic group $\mathbb{F}_{q}^{*}$
is isomorphic to $M$; consequently, $M$ is a cyclic group of order $q-1$. In
particular, if $\xi$ is a primitive element of $\mathbb{F}_{q}$ (namely, the
cyclic group $\mathbb{F}_{q}^{*}$ is generated by $\xi$), then $\sigma_{\xi}$
is a generator of $M$. Recall that
$\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}=\\{\langle\rho^{l}\rangle(\mathbf{c})|\mathbf{c}\in\mathcal{C}^{*}\\}$
denotes the set of orbits of $\langle\rho^{l}\rangle$ on
$\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$, where
$\langle\rho^{l}\rangle(\mathbf{c})=\\{\rho^{i}l(\mathbf{c})|0\leq i\leq
m-1\\}$. Then $M$ acts on $\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}$ in
the following natural way:

$M\times\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}\rightarrow\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}$
$(\sigma_{a},\langle\rho^{l}\rangle(\mathbf{c}))\mapsto\langle\rho^{l}\rangle(a\mathbf{c}).$

By Lemma 2, the number of orbits of $M$ on $\mathcal{C}^{*}$ is equal to the
number of orbits of $M$ on $\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}$,
where the latter is equal to

$|(\langle\rho^{l}\rangle\times
M)\backslash\mathcal{C}^{*}|=\frac{1}{q-1}\sum_{r|(q-1)}\varphi\bigg{(}\frac{q-1}{r}\bigg{)}|\mbox{Fix}(\sigma^{r}_{\xi})|$
(4)

with
$\mbox{Fix}(\sigma^{r}_{\xi})=\\{\langle\rho^{l}\rangle(\mathbf{c})\in\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}|\langle\rho^{l}\rangle(\mathbf{c})=\langle\rho^{l}\rangle(\xi^{r}\mathbf{c})\\}$.
Therefore, our ultimate goal is to calculate the value of
$|\mbox{Fix}(\sigma^{r}_{\xi})|$. To this end, as we did in the proof of Lemma
3, let $r$ be a divisor of $q-1$ and take a typical non-zero element

$\mathbf{c}=\big{(}\mathbf{c}_{0}(x),\mathbf{c}_{1}(x),\ldots,\mathbf{c}_{l-1}(x)\big{)}\in\mathcal{C}^{*},$

where $\mathbf{c}_{u}(x)\in R_{m}\varepsilon_{t}$ for $0\leq u\leq l-1$. By
Eq. (1), for each $0\leq u\leq l-1$,

$\mathbf{c}_{u}(x)=\sum_{j=0}^{k-1}(c_{u0}+c_{u1}\zeta^{i_{t}q^{j}}+\cdots+c_{u,k-1}\zeta^{(k-1)i_{t}q^{j}})e_{i_{t}q^{j}}\in
R_{m}\varepsilon_{t}.$

The condition
$\langle\rho^{l}\rangle(\mathbf{c})=\langle\rho^{l}\rangle(\xi^{r}\mathbf{c})$
is equivalent to requiring that there exists an integer $z\geq 0$ such that
$\rho^{zl}(\mathbf{c})=\xi^{r}\mathbf{c}$. Simple algebraic calculations show
that

$\rho^{zl}(\mathbf{c})=\big{(}x^{z}\mathbf{c}_{0}(x),x^{z}\mathbf{c}_{1}(x),\ldots,x^{z}\mathbf{c}_{l-1}(x)\big{)}$

and

$\xi^{r}\mathbf{c}=\big{(}\xi^{r}\mathbf{c}_{0}(x),\xi^{r}\mathbf{c}_{1}(x),\ldots,\xi^{r}\mathbf{c}_{l-1}(x)\big{)},$

where for each $0\leq u\leq l-1$,

$x^{z}\mathbf{c}_{u}(x)=\sum_{j=0}^{k-1}\zeta^{i_{t}q^{j}z}(c_{u0}+c_{u1}\zeta^{i_{t}q^{j}}+\cdots+c_{u,k-1}\zeta^{(k-1)i_{t}q^{j}})e_{i_{t}q^{j}}$

and

$\xi^{r}\mathbf{c}_{u}(x)=\sum_{j=0}^{k-1}\xi^{r}(c_{u0}+c_{u1}\zeta^{i_{t}q^{j}}+\cdots+c_{u,k-1}\zeta^{(k-1)i_{t}q^{j}})e_{i_{t}q^{j}}.$

Therefore, $\rho^{zl}(\mathbf{c})=\xi^{r}\mathbf{c}$ if and only if
$x^{z}\mathbf{c}_{u}(x)=\xi^{r}\mathbf{c}_{u}(x)$ for $0\leq u\leq l-1$ if and
only if there exists an integer $z\geq 0$ such that
$\zeta^{i_{t}q^{j}z}=\xi^{r}$ for $0\leq j\leq k-1$. Since
$\xi\in\mathbb{F}_{q}$, there exists an integer $z\geq 0$ such that
$\zeta^{i_{t}q^{j}z}=\xi^{r}$ for $0\leq j\leq k-1$ if and only if there
exists an integer $z\geq 0$ such that $\zeta^{i_{t}z}=\xi^{r}$.

In the following we transform the equality $\zeta^{i_{t}z}=\xi^{r}$ into
numerical conditions. Suppose that $\omega$ is a primitive element of
$\mathbb{F}_{q}^{m^{\prime}}$, where $m^{\prime}$ is the least positive
integer such that $m$ is a divisor of $q^{m^{\prime}}-1$. Denote by
$\mbox{ord}(\alpha)$ the order of the element
$\alpha\in\mathbb{F}_{q}^{m^{\prime}}$. Note that $\zeta$ is a primitive
$m$-th root of unity, $\xi$ is a primitive $(q-1)$-th root of unity and $r$ is
a divisor $q-1$. Setting $\zeta=\omega^{\frac{q^{m^{\prime}}-1}{m}}$ and
$\xi=\omega^{\frac{q^{m^{\prime}}-1}{q-1}}$, we have

$\begin{split}\zeta^{i_{t}z}=\xi^{r}&\Leftrightarrow\omega^{\frac{(q^{m^{\prime}}-1)i_{t}z}{m}}=\omega^{\frac{(q^{m^{\prime}}-1)r)}{q-1}}\\\
&\Leftrightarrow\langle\omega^{\frac{(q^{m^{\prime}}-1)r)}{q-1}}\rangle\subseteq\langle\omega^{\frac{(q^{m^{\prime}}-1)i_{t})}{q-1}}\rangle\\\
&\Leftrightarrow\mbox{ord}(\omega^{\frac{(q^{m^{\prime}}-1)r)}{q-1}})\subseteq\mbox{ord}(\omega^{\frac{(q^{m^{\prime}}-1)i_{t})}{q-1}})\\\
&\Leftrightarrow\mbox{gcd}\big{(}q^{m^{\prime}}-1,\frac{(q^{m^{\prime}}-1)i_{t}}{m}\big{)}\bigg{|}\frac{(q^{m^{\prime}}-1)r}{q-1}\\\
&\Leftrightarrow\frac{(q^{m^{\prime}}-1)\mbox{gcd}(m,i_{t})}{m}\bigg{|}\frac{(q^{m^{\prime}}-1)r}{q-1}\\\
&\Leftrightarrow\frac{q-1}{r}\bigg{|}\frac{m}{\mbox{gcd}(m,i_{t})},\end{split}$

where $\langle\omega^{\frac{(q^{m^{\prime}}-1)r)}{q-1}}\rangle$ and
$\langle\omega^{\frac{(q^{m^{\prime}}-1)i_{t})}{q-1}}\rangle$ denote the
cyclic subgroups of $\mathbb{F}_{q^{m^{\prime}}}^{*}$ generated by
$\omega^{\frac{(q^{m^{\prime}}-1)r)}{q-1}}$ and
$\omega^{\frac{(q^{m^{\prime}}-1)i_{t})}{q-1}}$, respectively. It follows that
there exists an integer $z\geq 0$ such that $\zeta^{i_{t}z}=\xi^{r}$ if and
only if $\frac{q-1}{r}$ is a divisor of $\frac{m}{gcd(m,i_{t})}$. By Lemma 3,
$\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}$ has size
$\frac{gcd(m,i_{t})(q^{K}-1)}{m}$; then we have

$|\mbox{Fix}(\sigma^{r}_{\xi})|=\left\\{\begin{array}[]{ll}\frac{gcd(m,i_{t})(q^{K}-1)}{m},&\mbox{if}\
\ \frac{q-1}{r}|\frac{m}{gcd(m,i_{t})}\hbox{;}\\\ 0,&\mbox{if}\ \
\frac{q-1}{r}\nmid\frac{m}{gcd(m,i_{t})}\hbox{.}\end{array}\right.$

Returning to Eq. (4), the number of orbits of $\langle\rho^{l}\rangle\times M$
on $\mathcal{C}^{*}$ is equal to

$\begin{split}|(\langle\rho^{l}\rangle\times
M)\backslash\mathcal{C}^{*}|&=\frac{1}{q-1}\sum_{r|(q-1)}\varphi\bigg{(}\frac{q-1}{r}\bigg{)}|\mbox{Fix}(\sigma^{r}_{\xi})|\\\
&=\frac{1}{q-1}\sum_{r|(q-1)}\varphi(r)|\mbox{Fix}(\sigma^{\frac{q-1}{r}}_{\xi})|\\\
&=\frac{1}{q-1}\sum_{r|(q-1),r|\frac{m}{gcd(m,i_{t})}}\varphi(r)\frac{\mbox{gcd}(m,i_{t})(q^{K}-1)}{m}\\\
&=\frac{\mbox{gcd}(m,i_{t})(q^{K}-1)}{m(q-1)}\sum_{r|(q-1),r|\frac{m}{gcd(m,i_{t})}}\varphi(r)\\\
&=\frac{\mbox{gcd}\big{(}q-1,\frac{m}{gcd(m,i_{t})}\big{)}\mbox{gcd}(m,i_{t})(q^{K}-1)}{m(q-1)}\\\
&=\frac{\mbox{gcd}\big{(}m,(q-1)i_{t}\big{)}(q^{K}-1)}{m(q-1)}.\end{split}$

The proof is completed. ∎

###  4.2 Proof of Theorem 1 and Corollary 1

###### Proof.

It is easy to check that $\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}C_{t_{j_{1}}}\setminus\\{\mathbf{0}\\}\bigoplus
C_{t_{j_{2}}}\setminus\\{\mathbf{0}\\}\bigoplus\cdots\bigoplus
C_{t_{j_{u}}}\setminus\\{\mathbf{0}\\},$

which is a disjoint union. For all $j_{1},j_{2},\ldots,j_{u}$, $C_{t_{j_{v}}}$
is a linear code over $R_{m}\varepsilon_{t_{j_{v}}}$ of length $l$ with $1\leq
v\leq u$. Let $s_{j_{1}j_{2}\cdots j_{u}}$ be the number of orbits of
$\langle\rho^{l}\rangle$ acting on

$C_{t_{j_{1}}}\setminus\\{\mathbf{0}\\}\bigoplus
C_{t_{j_{2}}}\setminus\\{\mathbf{0}\\}\bigoplus\cdots\bigoplus
C_{t_{j_{u}}}\setminus\\{\mathbf{0}\\},$

which is denoted by $\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}$. Thus the
group $\langle\rho^{l}\rangle$ can act on the set
$\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}$ in the same way as the group
action on $\mathcal{C}$. Then, we have

$\mathcal{C}\setminus\\{\mathbf{0}\\}=\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}$

and

$|\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}|=\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}s_{j_{1}j_{2}\cdots j_{u}}.$

It is enough to compute the number of orbits of the group
$\langle\rho^{l}\rangle$ acting on $\mathcal{C}_{j_{1}j_{2}\cdots
j_{u}}^{\sharp}$.

According to Eq. (3), we only need to compute the value of
$|\mbox{Fix}(\rho^{rl})|$ for each $r$ of $m$. Let
$\mathbf{c}=\mathbf{c}_{t_{j_{1}}}+\mathbf{c}_{t_{j_{1}}}+\cdots+\mathbf{c}_{t_{j_{u}}}\in\mathcal{C}_{j_{1}j_{2}\cdots
j_{u}}^{\sharp}$, where $\mathbf{c}_{t_{j_{v}}}\in
C_{t_{j_{v}}}\setminus\\{\mathbf{0}\\}\subseteq(R_{m}\varepsilon_{t_{j_{v}}})^{l}$
for $v=1,2,\ldots,u$. Suppose that for each $v=1,2,\ldots,u$,

$\mathbf{c}_{t_{j_{v}}}=\big{(}\mathbf{c}_{{t_{j_{v}}},0}(x),\mathbf{c}_{{t_{j_{v}}},1}(x),\ldots,\mathbf{c}_{t_{j_{v}},l-1}(x)\big{)},$

where
$\mathbf{c}_{{t_{j_{v}}},v^{\prime}}(x)=\sum_{j=0}^{k_{t_{j_{v}}}-1}\sum_{u^{\prime}=0}^{k_{t_{j_{v}}}-1}c_{v^{\prime},u^{\prime},t_{j_{v}}}\zeta^{u^{\prime}i_{t_{j_{v}}}q^{j}}e_{i_{t_{j_{v}}}q^{j}}$
for $0\leq v^{\prime}\leq l-1$. Then we have

$\begin{split}\rho^{rl}(\mathbf{c})&=\rho^{rl}(\mathbf{c}_{t_{j_{1}}})+\rho^{rl}(\mathbf{c}_{t_{j_{1}}})+\cdots+\rho^{rl}(\mathbf{c}_{t_{j_{u}}})\\\
&=\bigg{(}x^{r}\sum_{v=1}^{u}\mathbf{c}_{{t_{j_{v}}},0}(x),x^{r}\sum_{v=1}^{u}\mathbf{c}_{{t_{j_{v}}},1}(x),\ldots,x^{r}\sum_{v=1}^{u}\mathbf{c}_{{t_{j_{v}}},l-1}(x)\bigg{)},\end{split}$

where for each $0\leq v^{\prime}\leq l-1$,

$\begin{split}x^{r}\sum_{v=1}^{u}\mathbf{c}_{{t_{j_{v}}},v^{\prime}}(x)=&\sum_{j=0}^{k_{t_{j_{1}}}-1}\zeta^{i_{t_{j_{1}}}q^{j}r}\sum_{u^{\prime}=0}^{k_{t_{j_{1}}}-1}c_{v^{\prime},u^{\prime},t_{j_{1}}}\zeta^{u^{\prime}i_{t_{j_{1}}}q^{j}}e_{i_{t_{j_{1}}}q^{j}}+\cdots\\\
&+\sum_{j=0}^{k_{t_{j_{u}}}-1}\zeta^{i_{t_{j_{u}}}q^{j}r}\sum_{u^{\prime}=0}^{k_{t_{j_{u}}}-1}c_{v^{\prime},u^{\prime},t_{j_{u}}}\zeta^{u^{\prime}i_{t_{j_{u}}}q^{j}}e_{i_{t_{j_{u}}}q^{j}}.\end{split}$

Then we can conclude that $\rho^{rl}(\mathbf{c})=\mathbf{c}$ if and only if
$\rho^{rl}(\mathbf{c}_{t_{j_{1}}})+\rho^{rl}(\mathbf{c}_{t_{j_{1}}})+\cdots+\rho^{rl}(\mathbf{c}_{t_{j_{u}}})=\mathbf{c}_{t_{j_{1}}}+\mathbf{c}_{t_{j_{1}}}+\cdots+\mathbf{c}_{t_{j_{u}}}$
if and only if
$x^{r}\sum_{v=1}^{u}\mathbf{c}_{{t_{j_{v}}},v^{\prime}}(x)=\sum_{v=1}^{u}\mathbf{c}_{{t_{j_{v}}},v^{\prime}}(x)$
for $1\leq v^{\prime}\leq l-1$ if and only if $\zeta^{i_{t_{j_{v}}}q^{j}r}=1$
for all $v$ and $j$ if and only if $m|(i_{t_{j_{v}}}q^{j}r)$ for all $v$ and
$j$ if and only if $m|(i_{t_{j_{v}}}r)$ for $1\leq v\leq u$ if and only if
$\frac{m}{r}|i_{t_{j_{v}}}$ for $1\leq v\leq u$. It follows that

$|\mbox{Fix}(\rho^{rl})|=\left\\{\begin{array}[]{ll}\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1),&\mbox{if}\
\ \frac{m}{r}|i_{t_{v}}\ \ \mbox{for}\ \mbox{all}\ v=1,2,\ldots,u\hbox{;}\\\
0,&\mbox{otherwise}\hbox{.}\end{array}\right.$

Using Eq. (3), the number of orbits of $\langle\rho^{l}\rangle$ on
$\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}$ is

$\begin{split}s_{j_{1}j_{2}\cdots
j_{u}}&=|\langle\rho^{l}\rangle\backslash\mathcal{C}_{j_{1}j_{2}\cdots
j_{u}}^{\sharp}|\\\
&=\frac{1}{m}\sum_{i=0}^{m-1}|\mbox{Fix}(\rho^{il})|=\frac{1}{m}\sum_{r|m}\varphi(\frac{m}{r})|\mbox{Fix}(\rho^{rl})|\\\
&=\frac{1}{m}\sum_{r|m,\frac{m}{r}|i_{t_{v}},1\leq v\leq
u}\varphi(\frac{m}{r})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)\\\
&=\frac{\mbox{gcd}(m,i_{t_{j_{1}}},i_{t_{j_{2}}},\ldots,i_{t_{j_{u}}})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)}{m}.\end{split}$

Therefore, the number of orbits of $\langle\rho^{l}\rangle$ on
$\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}\frac{\mbox{gcd}(m,i_{t_{j_{1}}},i_{t_{j_{2}}},\ldots,i_{t_{j_{u}}})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)}{m}.$

Let $U=2$, then we have

$|\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}|=|\langle\rho^{l}\rangle\backslash\mathcal{C}_{t_{1},t_{2}}^{\sharp}|+s_{t_{1}}+s_{t_{2}}.$

By Lemma 3, we immediately get

$|\langle\rho^{l}\rangle\backslash\mathcal{C}_{t_{1}t_{2}}^{\sharp}|=\frac{\mbox{gcd}(m,i_{t_{1}},i_{t_{2}})(q^{K_{t_{1}}}-1)(q^{K_{t_{2}}}-1)}{m},$
$s_{t_{1}}=\frac{\mbox{gcd}(m,i_{t_{1}})(q^{K_{t_{1}}}-1)}{m},s_{t_{2}}=\frac{\mbox{gcd}(m,i_{t_{2}})(q^{K_{t_{2}}}-1)}{m},$

which gives the desired result. ∎

###  4.3 Proof of Theorem 2 and Corollary 2

###### Proof.

It is easy to check that $\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}C_{t_{j_{1}}}\setminus\\{\mathbf{0}\\}\bigoplus
C_{t_{j_{2}}}\setminus\\{\mathbf{0}\\}\bigoplus\cdots\bigoplus
C_{t_{j_{u}}}\setminus\\{\mathbf{0}\\},$

which is a disjoint union. For all $j_{1},j_{2},\ldots,j_{u}$, $C_{t_{j_{v}}}$
is a linear code over $R_{m}\varepsilon_{t_{j_{v}}}$ of length $l$ with $1\leq
v\leq u$. Let $s_{j_{1}j_{2}\cdots j_{u}}$ be the number of orbits of
$\langle\rho^{l}\times M\rangle$ acting on

$C_{t_{j_{1}}}\setminus\\{\mathbf{0}\\}\bigoplus
C_{t_{j_{2}}}\setminus\\{\mathbf{0}\\}\bigoplus\cdots\bigoplus
C_{t_{j_{u}}}\setminus\\{\mathbf{0}\\},$

which is denoted by $\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}$. Thus the
group $\langle\rho^{l}\times M\rangle$ can act on the set
$\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}$ in the same way as the group
action on $\mathcal{C}$. Then, we have

$\mathcal{C}\setminus\\{\mathbf{0}\\}=\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}$

and

$|(\langle\rho^{l}\times
M\rangle)\backslash\mathcal{C}^{*}|=\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}s_{j_{1}j_{2}\cdots j_{u}}.$

It is enough to compute the number of orbits of the group
$\langle\rho^{l}\times M\rangle$ acting on $\mathcal{C}_{j_{1}j_{2}\cdots
j_{u}}^{\sharp}$.

According to Eq. (4), the number of orbits of $\langle\rho^{l}\rangle\times M$
on $\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}$ is equal to

$|(\langle\rho^{l}\rangle\times M)\backslash\mathcal{C}_{j_{1}j_{2}\cdots
j_{u}}^{\sharp}|=\frac{1}{q-1}\sum_{r|(q-1)}\varphi(\frac{q-1}{r})|\mbox{Fix}(\sigma^{r}_{\xi})|$

with
$\mbox{Fix}(\sigma^{r}_{\xi})=\\{\langle\rho^{l}\rangle(\mathbf{c})\in\langle\rho^{l}\rangle\backslash\mathcal{C}_{j_{1}j_{2}\cdots
j_{u}}^{\sharp}|\langle\rho^{l}\rangle(\mathbf{c})=\langle\rho^{l}\rangle(\xi^{r}\mathbf{c})\\}$.
Therefore, it is enough to calculate the value of
$|\mbox{Fix}(\sigma^{r}_{\xi})|$. Note that
$\langle\rho^{l}\rangle(\mathbf{c})=\langle\rho^{l}\rangle(\xi^{r}\mathbf{c})$
is equivalent to requiring that there exists an integer $z$ such that
$\rho^{zl}(\mathbf{c})=\xi^{r}\mathbf{c}$.

Let
$\mathbf{c}=\mathbf{c}_{t_{j_{1}}}+\mathbf{c}_{t_{j_{2}}}+\cdots+\mathbf{c}_{t_{j_{u}}}\in\mathcal{C}^{\sharp}$,
where $\mathbf{c}_{t_{j_{v}}}\in
C_{t_{j_{v}}}\setminus\\{\mathbf{0}\\}\subseteq(R_{m}\varepsilon_{t_{j_{v}}})^{l}$
for $v=1,2,\ldots,u$. Then $\rho^{zl}(\mathbf{c})=\xi^{r}\mathbf{c}$ if and
only if

$\rho^{zl}(\mathbf{c}_{t_{j_{v}}})=\xi^{r}\mathbf{c}_{t_{j_{v}}}\ \ \
\mbox{for}\ \ \ \ v=1,2,\ldots,u.$ (5)

From the proof of Lemma 5, we have that the equalities (5) hold if and only if

$\frac{q-1}{r}\bigg{|}\frac{m}{\mbox{gcd}(m,i_{t_{j_{v}}})}\ \ \ \mbox{for}\ \
\ \ v=1,2,\ldots,u.$

It follows from the proof of Theorem 1 that if $\frac{q-1}{r}$ is a divisor
$\frac{m}{gcd(m,i_{t_{j_{v}}})}$ for $v=1,2,\ldots,u$, then

$|\mbox{Fix}(\sigma^{r}_{\xi})|=\frac{\mbox{gcd}(m,i_{t_{j_{1}}},i_{t_{j_{2}}},\ldots,i_{t_{j_{u}}})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)}{m};$

otherwise, $|\mbox{Fix}(\sigma^{r}_{\xi})|=0$. Therefore,

$\begin{split}s_{j_{1}j_{2}\cdots j_{u}}=&|(\langle\rho^{l}\rangle\times
M)\backslash\mathcal{C}_{j_{1}j_{2}\cdots j_{u}}^{\sharp}|\\\
=&\frac{1}{q-1}\sum_{r|(q-1)}\varphi\bigg{(}\frac{q-1}{r}\bigg{)}|\mbox{Fix}(\sigma^{r}_{\xi})|\\\
=&\frac{\mbox{gcd}(m,i_{t_{j_{1}}},i_{t_{j_{2}}},\ldots,i_{t_{j_{u}}})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)}{m(q-1)}\cdot\\\
&\sum_{r|(q-1),\frac{q-1}{r}\big{|}\frac{m}{gcd(m,i_{t_{j_{v}}})},v=1,2,\ldots,u}\varphi(\frac{q-1}{r})\\\
=&\frac{\mbox{gcd}(m,i_{t_{j_{1}}},i_{t_{j_{2}}},\ldots,i_{t_{j_{u}}})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)}{m(q-1)}\cdot\\\
&\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{j_{1}}})},\ldots,\frac{m}{\mbox{gcd}(m,i_{t_{j_{u}}})}\bigg{)}.\end{split}$

Therefore, the number of orbits of $\langle\rho^{l}\times M\rangle$ on
$\mathcal{C}^{*}=\mathcal{C}\setminus\\{\mathbf{0}\\}$ is equal to

$\sum_{\\{j_{1},j_{2},\ldots,j_{u}\\}\subseteq\\{1,2,\ldots,U\\},1\leq<j_{1}<j_{2}<\cdots<j_{u}\leq
U}\frac{\mbox{gcd}(m,i_{t_{j_{1}}},i_{t_{j_{2}}},\ldots,i_{t_{j_{u}}})\prod_{v=1}^{u}(q^{K_{t_{j_{v}}}}-1)}{m(q-1)}$
$\cdot\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{j_{1}}})},\ldots,\frac{m}{\mbox{gcd}(m,i_{t_{j_{u}}})}\bigg{)}.$

Let $U=2$, we have

$\langle\rho^{l}\rangle\backslash\mathcal{C}^{*}=s^{\prime}_{t_{1}t_{2}}+s^{\prime}_{t_{1}}+s^{\prime}_{t_{2}}.$

By Lemma 5, we see that

$\begin{split}s^{\prime}_{t_{1}t_{2}}=&\frac{\mbox{gcd}(m,i_{t_{1}},i_{t_{2}})(q^{K_{t_{1}}}-1)(q^{K_{t_{2}}}-1)}{m(q-1)}\cdot\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{1}})},\frac{m}{\mbox{gcd}(m,i_{t_{2}})}\bigg{)},\\\
s^{\prime}_{t_{1}}=&\frac{\mbox{gcd}(m,i_{t_{1}})(q^{K_{t_{1}}}-1)}{m(q-1)}\cdot\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{1}})}\bigg{)},\\\
s^{\prime}_{t_{2}}=&\frac{\mbox{gcd}(m,i_{t_{2}})(q^{K_{t_{2}}}-1)}{m(q-1)}\cdot\mbox{gcd}\bigg{(}q-1,\frac{m}{\mbox{gcd}(m,i_{t_{2}})}\bigg{)},\end{split}$

giving the desired result. ∎

##  5 Remarks and examples

######  Remark 1.

The reference [21, Theorem 5] says that if $\mathcal{C}$ is a $[n=lm,K]$
strongly quasi-cyclic code of co-index $m$ over $\mathbb{F}_{q}$, then
$s(\mathcal{C})\leq\frac{q^{K}-1}{m}$. If $\mbox{gcd}(m,i_{t})=1$, then Lemma
3 generalizes and improves [21, Theorem 5] by removing the constrain
“strongly” and characterizing a necessary and sufficient condition for the
codes meeting bounds.

We include three examples to show that the upper bounds given in Lemma 3 and
Theorem 1 are tight.

######  Example 1.

Take $m=9$, $l=2$ and $q=2$ in Lemma 3. All the distinct $2$-cyclotomic cosets
modulo $9$ are given by

$\Gamma_{0}=\\{0\\},\Gamma_{1}=\\{1,2,4,5,7,8\\},\Gamma_{2}=\\{3,6\\}.$

Consider the linear code $\mathcal{C}$ over $R_{m}\varepsilon_{2}$, where the
primitive idempotent $\varepsilon_{2}$ corresponds to $\Gamma_{2}$. Suppose
$\zeta$ is a primitive $m$-th root of unity. Actually, let
$h(x)=\prod_{r\in\Gamma_{2}}(x-\zeta^{r})=x^{2}+x+1$, then
$g(x)=(x^{m}-1)/h(x)$ is a generator polynomial of $R_{m}\varepsilon_{2}$. Let
$[1,g(x)]$ be the generator matrix of $\mathcal{C}$ over
$R_{m}\varepsilon_{2}$. Then $K=1\cdot|\Gamma_{2}|=2$. By Lemma 3, we have

$s(\mathcal{C})\leq\frac{\mbox{gcd}(m,i_{t})(q^{K}-1)}{m}=\frac{\mbox{gcd}(9,3)(2^{2}-1)}{9}=1.$

Hence, the number of non-zero weights of $\mathcal{C}$ must be equal to $1$.
Moreover, Lemma 3 also tells us that all the non-zero codewords of
$\mathcal{C}$ are in the same $\langle\rho^{l}\rangle$-orbit.

######  Example 2.

Take $m=15$, $l=3$ and $q=2$ in Lemma 3. All the distinct $2$-cyclotomic
cosets modulo $15$ are given by

$\Gamma_{0}=\\{0\\},\Gamma_{1}=\\{1,2,4,8\\},\Gamma_{2}=\\{3,6,9,12\\},\Gamma_{3}=\\{7,11,13,14\\},\Gamma_{4}=\\{5,10\\}.$

Consider the linear code $\mathcal{C}$ over $R_{m}\varepsilon_{0}$, where the
primitive idempotent $\varepsilon_{0}$ corresponds to $\Gamma_{0}$. Actually,
let $h(x)=x-1$, then $g(x)=(x^{m}-1)/h(x)$ is a generator polynomial of
$R_{m}\varepsilon_{0}$. Let

$\left(\begin{array}[]{ccc}1&0&g(x)\\\ 0&1&0\\\ \end{array}\right)$

be the generator matrix of $\mathcal{C}$ over $R_{m}\varepsilon_{0}$. Then
$K=2\cdot|\Gamma_{0}|=2$. By Lemma 3, we have

$s(\mathcal{C})\leq\frac{\mbox{gcd}(m,i_{t})(q^{K}-1)}{m}=\frac{\mbox{gcd}(15,0)(2^{2}-1)}{15}=3.$

Using the Magma software programming [4], we see that the weight distribution
of the quasi-cyclic code $\mathcal{C}$ is $1+x^{15}+x^{30}+x^{45}$, showing
that the exact value of $s(\mathcal{C})=3$.

######  Example 3.

Take $m=9$, $l=2$ and $q=2$ in Theorem 1. All the distinct $2$-cyclotomic
cosets modulo $9$ are given by

$\Gamma_{0}=\\{0\\},\Gamma_{1}=\\{1,2,4,5,7,8\\},\Gamma_{2}=\\{3,6\\}.$

Consider the quasi-cyclic code $\mathcal{C}=C_{0}\bigoplus C_{2}$, where
$C_{0}$ is a linear code over $R_{m}\varepsilon_{0}$ and $C_{2}$ is a linear
code over $R_{m}\varepsilon_{2}$, where the primitive idempotent
$\varepsilon_{0}$ and $\varepsilon_{2}$ corresponds to $\Gamma_{0}$ and
$\Gamma_{2}$, respectively. Actually, let $h_{1}(x)=x+1$ and
$h_{2}(x)=x^{2}+x+1$, then $g_{1}(x)=(x^{m}-1)/h_{1}(x)$ and
$g_{2}(x)=(x^{m}-1)/h_{2}(x)$ are the generator polynomial of
$R_{m}\varepsilon_{0}$ and $R_{m}\varepsilon_{2}$, respectively. Let
$[1,g_{i}(x)]$ be the generator matrix of $C_{i}$ over $R_{m}\varepsilon_{i}$
with $i=0,2$. Then $K_{1}=1\cdot|\Gamma_{0}|=1$ and
$K_{2}=1\cdot|\Gamma_{2}|=2$. By Theorem 1, we have

$s(\mathcal{C})\leq\frac{\mbox{gcd}(9,0,3)(2-1)(2^{2}-1)}{9}+\frac{\mbox{gcd}(9,0)(2-1)}{9}+\frac{\mbox{gcd}(9,3)(2^{2}-1)}{9}=3.$

Using the Magma software programming [4], we see that the weight distribution
of the quasi-cyclic code $\mathcal{C}$ is $1+3x^{6}+3x^{12}+x^{18}$, showing
that the exact value of $s(\mathcal{C})=3$. Moreover, Lemma 3 also tells us
that any two non-zero codewords of $\mathcal{C}$ with the same weight are in
the same $\langle\rho^{l}\rangle$-orbit.

######  Remark 2.

The reference [21, Theorem 3] says that if $\mathcal{C}$ is a $[n=lm,K]$
strongly quasi-cyclic code of co-index $m$ over $\mathbb{F}_{q}$, then

$s(\mathcal{C})\leq\frac{l(q^{K}-1)}{\mbox{lcm}(q-1,n)}=\frac{\mbox{gcd}(lm,q-1)(q^{K}-1)}{m(q-1)}.$

If $\mbox{gcd}(m,i_{t})=1$, then Lemma 5 says that

$s(\mathcal{C})\leq\frac{\mbox{gcd}(m,q-1)(q^{K}-1)}{m(q-1)}\leq\frac{\mbox{gcd}(lm,q-1)(q^{K}-1)}{m(q-1)}.$

Therefore, Lemma 5 generalizes and improves [21, Theorem 3] by removing the
constrain “strongly” and characterizing a necessary and sufficient condition
for the codes meeting bounds.

Next, we also include three examples to show that the upper bounds given in
Lemma 5 and Theorem 2 are tight.

######  Example 4.

Take $m=91$, $l=2$ and $q=9$ in Lemma 5. $\Gamma_{2}=\\{8,72,11\\}$ is the
$9$-cyclotomic coset modulo $91$ containing $8$. Consider the linear code
$\mathcal{C}$ over $R_{m}\varepsilon_{2}$, where the primitive idempotent
$\varepsilon_{2}$ corresponds to $\Gamma_{2}$. Suppose $g(x)$ is a generator
polynomial of $R_{m}\varepsilon_{2}$. Let $[1,g(x)]$ be the generator matrix
of $\mathcal{C}$ over $R_{m}\varepsilon_{2}$. Then $K=1\cdot|\Gamma_{2}|=3$.
By Lemma 5, we have

$s(\mathcal{C})\leq\frac{\mbox{gcd}(m,(q-1)i_{t})(q^{K}-1)}{m(q-1)}=\frac{\mbox{gcd}(31,(9-1)8)(9^{3}-1)}{91(9-1)}=1.$

Hence, the number of non-zero weights of $\mathcal{C}$ must be equal to $1$.
Moreover, Lemma 3 also tells us that all the non-zero codewords of
$\mathcal{C}$ are in the same $\langle\rho^{l}\times M\rangle$-orbit.

######  Example 5.

Take $m=39$, $l=2$ and $q=5$ in Lemma 5. $\Gamma_{1}=\\{1,5,8,25\\}$ is the
$5$-cyclotomic coset modulo $39$ containing $1$. Consider the linear code
$\mathcal{C}$ over $R_{m}\varepsilon_{1}$, where the primitive idempotent
$\varepsilon_{1}$ corresponds to $\Gamma_{1}$. Suppose $g(x)$ is a generator
polynomial of $R_{m}\varepsilon_{1}$. Let $[1,g(x)]$ be the generator matrix
of $\mathcal{C}$ over $R_{m}\varepsilon_{2}$. Then $K=1\cdot|\Gamma_{1}|=4$.
By Lemma 5, we have

$s(\mathcal{C})\leq\frac{\mbox{gcd}(m,(q-1)i_{t})(q^{K}-1)}{m(q-1)}=\frac{\mbox{gcd}(39,(5-1)1)(5^{4}-1)}{39(5-1)}=4.$

Using the Magma software programming [4], we see that the weight distribution
of the quasi-cyclic code $\mathcal{C}$ is
$1+156x^{59}+156x^{62}+156x^{63}+156x^{66}$, showing that the exact value of
$s(\mathcal{C})=4$. Moreover, Lemma 3 also tells us that any two non-zero
codewords of $\mathcal{C}$ with the same weight are in the same
$\langle\rho^{l}\times M\rangle$-orbit.

######  Example 6.

Take $m=26$, $l=2$ and $q=3$ in Theorem 2. All the distinct $3$-cyclotomic
cosets modulo $26$ are given by

$\Gamma_{0}=\\{0\\},\Gamma_{1}=\\{1,3,9\\},\Gamma_{2}=\\{2,4,6\\},\Gamma_{3}=\\{4,10,12\\},\Gamma_{4}=\\{5,15,19\\},$
$\Gamma_{5}=\\{13\\},\Gamma_{6}=\\{7,11,21\\},\Gamma_{7}=\\{8,20,24\\},\Gamma_{8}=\\{14,16,22\\},\Gamma_{9}=\\{17,23,25\\}.$

Consider the quasi-cyclic code $\mathcal{C}=C_{1}\bigoplus C_{5}$, where
$C_{1}$ is a linear code over $R_{m}\varepsilon_{1}$ and $C_{5}$ is a linear
code over $R_{m}\varepsilon_{5}$, where the primitive idempotent
$\varepsilon_{1}$ and $\varepsilon_{5}$ corresponds to $\Gamma_{1}$ and
$\Gamma_{5}$, respectively. Let $g_{1}(x)$ and $g_{2}(x)$ be the generator
polynomial of $R_{m}\varepsilon_{1}$ and $R_{m}\varepsilon_{5}$, respectively.
Let $[1,g_{1}(x)]$ be the generator matrix of $C_{1}$ over
$R_{m}\varepsilon_{1}$, and $[0,g_{2}(x)]$ be the generator matrix of $C_{5}$
over $R_{m}\varepsilon_{5}$. Then $K_{1}=1\cdot|\Gamma_{1}|=3$ and
$K_{2}=1\cdot|\Gamma_{5}|=1$. By Theorem 2, we have

$\begin{split}s(\mathcal{C})\leq&\frac{\mbox{gcd}(26,1,13)(3^{3}-1)(3-1)}{26(3-1)}\cdot\mbox{gcd}\bigg{(}3-1,\frac{26}{\mbox{gcd}(26,1)},\frac{26}{\mbox{gcd}(26,13)}\bigg{)}\\\
&+\frac{\mbox{gcd}(26,1)(3^{3}-1)}{26(3-1)}\cdot\mbox{gcd}\bigg{(}3-1,\frac{26}{\mbox{gcd}(26,1)}\bigg{)}\\\
&+\frac{\mbox{gcd}(26,13)(3-1)}{26(3-1)}\cdot\mbox{gcd}\bigg{(}3-1,\frac{26}{\mbox{gcd}(26,13)}\bigg{)}\\\
=&4.\end{split}$

Using the Magma software programming [4], we see that the weight distribution
of the quasi-cyclic code $\mathcal{C}$ is
$1+2x^{26}+26x^{32}+26x^{36}+26x^{38}$, showing that the exact value of
$s(\mathcal{C})=4$. Moreover, Lemma 3 also tells us that any two non-zero
codewords of $\mathcal{C}$ with the same weight are in the same
$\langle\rho^{l}\times M\rangle$-orbit.

##  6 Conclusion

In this paper, we establish an explicit upper bound on the number of non-zero
weights of any quasi-cyclic code with simple-root by counting the number of
orbits of $\langle\rho^{l}\times M\rangle$ on the code (see Section 3 and
Section 4); at the same time, we show that a quasi-cyclic code achieves the
bound if and only if any two codewords with the same weight are in the same
$\langle\rho^{l}\times M\rangle$-orbit. Many examples (see Section 5) are
included to show that our bound is tight. Our main result and its corollaries
generalize and improve some of the results in [21].

A possible direction for future work is to find tight upper bounds for the
number of non-zero weights of quasi-cyclic codes with repeated-root.

## References

  * [1] T. Alderson, A note on full weight spectrum codes, Trans. Comb., vol. 8, no. 3, pp. 15-22, 2019.
  * [2] T. Alderson and A. Neri, Maximum weight spectrum codes, Adv. Math. Commun., vol. 13, no. 1, pp. 101-119, 2019.
  * [3] E. Assmus and E. Mattson, New 5-designs, J. Combinatorial Theory, vol. 6, no. 2, pp. 122-151, 1969.
  * [4] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput., vol. 24, no. 3-4, pp. 235-265, 1997.
  * [5] P. Charpin, Open problems on cyclic codes, in Handbook of Coding Theory, V. S. Pless and C. W. Huffman, Eds. New York: Elsevier, pp. 963-1063, 1998.
  * [6] B. Chen, H. Liu and G. Zhang, Some minimal cyclic codes over finite fields, Discrete Math., vol. 331, pp. 142-150, 2014.
  * [7] B. Chen and G. Zhang, A tight upper bound on the number of non-zero weights of a cyclic code, IEEE Trans. Inform. Theory, doi: 10.1109/TIT.2022.3208438, 2022.
  * [8] P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Informatioin and Control, vol. 23, no. 5, pp. 407-438, 1973.
  * [9] C. Ding, The weight distribution of some irreducible cyclic codes, IEEE Trans. Inform. Theory, vol. 55, no. 3, pp.955-960, 2009.
  * [10] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003.
  * [11] R. Hill, An extension theorem for linear codes, Des., Codes Cryptogr., vol. 17, nos. 1-3, pp. 151-157, 1999.
  * [12] R. Hill and P. Lizak, Extensions of linear codes, in Proc. IEEE Int. Symp. Inf. Theory, Sep. 1995, p. 345.
  * [13] A. Kerber, Applied Finite Group Actions, Springer-Verlag, 1999.
  * [14] K. Lally and P. Fitzpatrick, Algebraic structure of quasi-cyclic codes, Discr. Appl. Math., vol. 111, pp. 157-175, 2001.
  * [15] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, 2003.
  * [16] S. Ling and P. Sole, On the algebraic structure of quasi-cyclic codes I: Finite fields, IEEE Trans. Inform. Theory, vol. 47, no. 7, pp. 2751-2760, 2001.
  * [17] F. J. Macwilliams, A theorem on the distribution of weights in a systematic code, Bell Syst. Tech. J., vol. 42, no. 1, pp. 79-94, Jan. 1963.
  * [18] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North Holland, 1983.
  * [19] J. J. Rotman, Advanced Modern Algebra, Prentice Hall, 2003.
  * [20] M. Shi, X. Li, A. Neri and P. Sole, How many weights can a cyclic code have?, IEEE Trans. Inform. Theory, vol. 66, no. 3, pp. 1449-1459, 2020.
  * [21] M. Shi, A. Neri and P. Sole, How many weights can a quasi-cyclic code have?, IEEE Trans. Inform. Theory, vol. 66, no. 11, pp. 6855-6862, 2020.
  * [22] M. Shi, H. Zhu, P. Sole and G. D. Cohen, How many weights can a linear code have?, Des. Codes Cryptogr., vol. 87, no. 1, pp. 87-95, 2019.