# Real-Time Scene Graph Generation

Maëlic Neau1,2 Paulo E. Santos1 Karl Sammut1 Anne-Gwenn Bosser2 Cédric
Buche2,3
1College of Science and Engineering, Flinders University, Australia
2Ecole Nationale d’Ingénieurs de Brest, France
3Naval Group Pacific, Australia
{neau, buche<EMAIL_ADDRESS>{paulo.santos<EMAIL_ADDRESS>
###### Abstract

Scene Graph Generation (SGG) can extract abstract semantic relations between
entities in images as graph representations. This task holds strong promises
for other downstream tasks such as the embodied cognition of an autonomous
agent. However, to power such applications, SGG needs to solve the gap of
real-time latency. In this work, we propose to investigate the bottlenecks of
current approaches for real-time constraint applications. Then, we propose a
simple yet effective implementation of a real-time SGG approach using YOLOV8
as an object detection backbone. Our implementation is the first to obtain
more than 48 FPS for the task with no loss of accuracy, successfully
outperforming any other lightweight approaches. Our code is freely available
at https://github.com/Maelic/SGG-Benchmark.

##  1 Introduction

Scene Graph Generation (SGG) is the task of generating a structured graph
representation from visual inputs. Given an image, visual regions
corresponding to objects of interest are extracted, and relations between
these objects are predicted in the form of $<subject,predicate,object>$ RDF
triplets. The connection of these triplets forms a directed acyclic graph
which can be interpreted as a structured representation of the scene. In
addition, subject and object nodes are traditionally associated with two-
dimensional coordinates that account for their respective position on the
input image.

During the past few years, this task has attracted a growing interest in the
community as a support for other downstream tasks such as Visual Question
Answering (VQA) [5], Image Captioning [34], or Reasoning of an embodied agent
[7, 17]. However, we observe a significant unbalance between the progress in
the SGG task itself and its adoption as a backbone for other downstream tasks.
This can be explained by different paradigms but one of them is surely the
lack of simple, low-cost, and effective approaches that could power downstream
tasks with low resources or real-time constraints (such as embodied agent
reasoning). In this work, we aim to redefine the task of SGG from the
perspective of real-time constraints, aiming at bridging the gap between
efficient and fast implementations.

Defining the current bottleneck of inference time in SGG is complex, as
approaches often rely on the aggregation of diverse modules. These modules
are, for the vast majority of approaches, paired as the following pipeline:

  1. 1.

The object detection module, which predicts candidate bounding box coordinates

  2. 2.

The features extractor, which associates to each bounding box candidate a
feature vector

  3. 3.

The relation prediction module, which takes as input the bounding boxes and
associated features to predict classes, pairs, and relations

In the literature, the (1) object detection and (2) feature extractor modules
rely on state-of-the-art approaches such as Faster-RCNN [26] or DETR [2]
equipped with a ResNeXt-101 model for feature extraction. To our knowledge, no
other feature extractor or bounding box regression module has been used in the
task, as approaches are mostly concerned with improving the relation
prediction stage considering that the two first stages are independent of the
last one. For real-time performance but also overall accuracy, Faster-RCNN,
and DETR are today far away from state-of-the-art object detectors such as
YOLO (You Only Look Once) [25, 9]. Nonetheless, they are still used because
their feature extraction component is deemed better than the ones used in
real-time object detectors. However, no quantitative study has been made in
this sense specifically for the task of Scene Graph Generation, which is the
first aim of this work.

A second aim of this work is to propose a new structure for Scene Graph
Generation which is more efficient for real-time processing. In current
designs, the workflow is to sample as many bounding box candidates as possible
from the object detection backbone to ease the relation prediction stage. The
idea here is that with more bounding boxes as node candidates, more pairs can
be created which will facilitate the learning of inter-dependencies between
relations. In practice nonetheless, this process is extremely resource-
intensive as the complexity of relations prediction grows exponentially with
the number of inputs. Another drawback of this method is the decrease in
accuracy of the predicted object coordinates and class labels. In fact, as the
$<subject,object>$ pairs are selected based on their potential of having a
relation rather than true confidence on the object detection backbone, some
nodes from the final graph can be of low confidence from the object detector.
On the other hand, some high-confidence objects detected by the object
detector can be excluded from the final graph after the relation prediction
stage.

In summary, in this work, we successfully leveraged the state-of-the-art real-
time object detector YOLOV8 as a feature extraction backbone for the task of
SGG and we proposed a new implementation that achieves a competitive runtime
latency of 20.5ms with an improved performance of 19.4% in average on a large
set of baseline models. Our approach can be easily implemented in any two-
stage Scene Graph Generation architecture as we make our code fully open-
source and simple to replicate.

##  2 Related Work

###  2.1 Scene Graph Generation

Since the first inception of the task [31], SGG has drawn widespread attention
in the computer vision and natural language processing communities. Popular
approaches combine object detection backbones such as the popular Faster-RCNN
[26] with a graph generation model in a two-stage pipeline [31, 38, 28, 14,
19, 29]. However, concerns about biases in large-scale datasets such as Visual
Genome [10] have been rapidly raised, resulting in the task of Unbiased SGG
[30, 27, 35, 32, 36, 6]. The idea is to improve predicate prediction using
different model-agnostic techniques and training strategies such as the Total
Direct Effect [27] or probability distribution [15] and evaluate them on a set
of baseline models [37, 28, 31]. On the other hand, new approaches [4, 13, 21,
20] are considering the task in a one-stage fashion, learning relationships
from image features directly. Even though they are very popular, two-stage
approaches are considered to be too complex and unsuited for real-time
applications by some [12, 4]. On the other hand, one-stage approaches suffer
from low accuracy in object detection and can be challenged to learn complex
dependencies in dense scenes [13].

###  2.2 Real-Time Scene Graph Generation

The term Real-Time Scene Graph Generation has not been widely adopted by the
community, unlike Real-Time Object Detection for instance. However, a set of
recent approaches are reporting latency metrics in their approach, showing a
growing interest in efficient implementations. RelationTransformer (RelTr) [4]
and SGTR [13] are two Transformer-based one-stage approaches to the task that
report low-latency with 13.4FPS and 6FPS, respectively. Lately, EGTR [8] is a
one-stage approach that reports almost state-of-the-art performance with a
lower latency of 14.7FPS 111Inference time reported in [8] using one NVIDIA
V100..

While those results are interesting for one-stage approaches, the real-time
performance of two-stage approaches has not been studied yet. At the same
time, the link between the performance of the object detector and the
performance of models on the task is unclear, as different approaches use
different backbones with different settings but yet compare their results
together. In this work, we aim to bridge this gap by proposing the first true
real-time (i.e. inference $>30$FPS) implementation of SGG while improving
overall accuracy. We also study the main parameters that influence latency for
Scene Graph Generation.

##  3 Approach

###  3.1 Features Extraction Backbone

We modify different SGG architectures originally based on Faster-RCNN to
evaluate the performance of YOLOV8 as a feature extractor. In previous work,
Faster-RCNN is equipped with a ResNeXt-101 backbone with an output channel
size of 256. YOLOV8 is equipped with a CSPDarknet53 backbone with a channel
size of 192. We modify the forward pass of YOLOV8 to extract features from the
backbone before the classification and regression heads, which correspond to
the last layers of what we call the neck in Yolo’s style architectures. YOLOV8
architecture is slightly different here from Faster-RCNN as it processes
features at three fixed scales, to better detect small, medium, and large size
objects. From the inner representation of the network, this corresponds to
layers 15, 18, and 21 respectively. To cope with this issue, we then modify
the original ROI Align algorithm of Faster-RCNN to assign to each of the three
feature maps extracted from the three layers the corresponding proposals,
based on every bounding box area size. Then, ROI Align is performed as in the
original implementation.

Next, we tried to understand the impact of those changes in the relation
prediction stage. To do so, we trained different relation prediction models by
keeping both backbones frozen. During training and evaluation, we purposely
input ground truth bounding boxes and pairs to evaluate only the prediction of
relations. This type of evaluation is known as predicate classification
(PredCls). In Fig. 1 we display a comparison of the performance of three
different baseline models, Motifs-TDE [27], VCTree-TDE [27] and Transformer
[27] equipped with the feature extractor of YoloV8 (CSPDarknet53) and Faster-
RCNN (ResNeXt-101). For each model, the metric used is F1@K which is the
harmonic average between the commonly used metric Recall@K, and meanRecall@K.
We observed almost no difference between the two, which can signify that
either the visual features are not important in the learning process of
relation prediction or that the quality of the features generated by the
YoloV8 backbone and Faster-RCNN ones are very similar. This is an interesting
finding, as the size and architecture of both backbones are very different.

Figure 1: Performance in F1@K for relation prediction of different models [37,
28, 27] equipped with Faster-RCNN and YOLOV8 backbones.

###  3.2 Object Classification

The traditional approach in object detection employs a bounding box regression
and a classification head after the feature extraction step. In the original
Faster-RCNN implementation, regression and classification are done in a
sequence, and then a final step of Non-Maximum Suppression (NMS) is applied.

In the case of the two-stage approach in SGG with a Faster-RCNN backbone, the
strategy employed is to decode object classes during the relation prediction
stage, to better capture object co-occurences. While in the original Faster-
RCNN implementation a simple softmax is applied to the class logits, SGG
approaches are introducing their own method to decode classes, for instance a
TreeLSTM for VCTree [28]. This makes the performance of SGG models to be
different than the original Faster-RCNN implementation. This can also lead to
severe biases in the comparison of models in the task of Scene Graph
Generation, as the difference in performance for object detection may hinder
the comparison of relation prediction modules.

On top of that, in SGG mode the step of NMS is performed after the relation
prediction stage which will also influence the predicted objects. As a result,
the performance of SGG models in object detection becomes slightly worse after
the relation training stage than before. We draw a comparison of the
performance of the Faster-RCNN model trained on the Visual Genome dataset with
different relation prediction heads, on the same validation set in Tab. 1. In
this table, we can see that the performance in object detection drops
significantly, from 1% for Motifs-TDE to almost 10% in mAP@50 for GPS-NET.
These results show a true dependence between the two stages of SGG methods, in
contrast to what is usually accepted in the community.

Backbone | Relation Head | mAP@50 | mAP@50-95
---|---|---|---
Faster-RCNN | - | 27.2 | 11.5
Motifs-TDE [27] | 26.2 | 11.6
VC-Tree [28] | 25.5 | 11.1
PE-NET [39] | 25.2 | 11.2
Transformer [27] | 24.2 | 10.6
GPS-NET [19] | 17.4 | 7.1
YOLOV8 | [27, 39, 19] | 35.1 | 20.0

Table 1: Performance on Object Detection of Faster-RCNN before and after the
Relation Prediction stage with different SGG models on the Visual Genome
dataset [10].

To solve this problem, we propose to completely make independent the first and
second stages of the Scene Graph Generation process. To do so, we freeze the
regression but also the classification head of YOLOV8 and perform NMS before
the relation prediction stage. The objective of the relation prediction stage
becomes then to predict only the pairs and associate predicates, in contrast
to also predicting the class labels of objects. This significantly lowers the
complexity of the relation prediction stage and thus the computational load of
the model. With this method, our performance in mAP stays similar after any
relation prediction training, which also helps to fairly evaluate the quality
of relation predicted by Scene Graph Generation models.

###  3.3 Candidate Selection

During the step of relation prediction, all proposals are considered valid
node candidates for the graph refinement process. Traditionally, a fixed
number of proposals (i.e. 80 proposals) is considered from the higher
confidence proposals output by the object detector. The idea here is that by
sampling a large number of proposals, it is easier to find valid pairs and
relations. However, this results in considerably enlarging the number of
computations required to generate a good graph, which is a bottleneck for
real-time applications. This issue also raises concerns about the objective of
the task, as it could be considered unfair to look for candidate nodes of the
graph based on their likelihood of having a relation rather than the true
confidence of the object detector. For instance, a low-confidence bounding box
chair (which could be ranked bottom 80 in the detected proposals) could be
selected as a node candidate instead of a higher-confidence bounding box kite
if the two objects are in the presence of a third one, table, as chair is more
likely to have a relation with table than kite. This paradigm will tend to
improve the performance of models for relation prediction but with the
drawback of lowering the accuracy in object detection and limiting the
generalization to new or unseen relations. The question here is: do we want
models to predict relations from a small set of highly confident objects in
the scene or do we want models to predict the most likely relations from a
larger set of objects, even though some of those objects are of low
confidence?

In this work, we believe the first approach is more beneficial for real-time
applications. We hypothesize that the gain in latency is more important than
the gain in accuracy by using a small number of proposals, such as 10 or 20
per image and that an optimal trade-off can be found. For the relation
prediction stage, as we are evaluating entire triplets and not solely the
predicate, the relation triplets score is computed with the following formula:

$\theta_{rel}=\theta_{obj}*\theta_{pred}*\theta_{subj}$ (1)

With $\theta_{pred}$ being the confidence score of a predicate given
$<subject,object>$ pair as candidate and $\theta_{obj},\theta_{subj}$ are the
respective confidence score of the object detector. This formula gives more
weight to the confidence of the subject and object than the predicate, which
makes the model’s overall performance rely more on the object detector than
the relation predictor. Thus, one would rather want to input only highly
confident proposals to the relation prediction stage. We evaluate this
hypothesis in the next sections.

##  4 Metrics

During the years, the SGG task has seen many metrics being proposed such as
Recall@K, meanRecall@K, or F1@K. All these metrics are used to validate the
performance of models, with different goals. MeanRecall@K is targeted into the
performance on rare and tail classes and F1@K is the harmonic average between
overall performance and tail classes performance. @K means that we compute the
recall on the top $k$ relations predicted after the final stage of an SGG
model. The mR@K and R@K metrics have been criticized a lot for being metrics
that could be easily cheated on. For instance, a simple model with no visual
features and only statistical biases about objects and predicates co-
occurrence in the dataset can attain a high mR@K and R@K, even outperforming a
lot of approaches that use visual features [16]. This is for sure not what we
want to benchmark SGG models for real-world applications. To cope with this
issue, we propose to use a new metric, the Informative Recall @K (IR@K) which
asserts the quality of generated scene graphs by comparing them with relations
contained in corresponding scene descriptions (i.e. detailed image captions).
As the scene descriptions are only used for evaluation, it is impossible to
tweak the model using frequency bias to boost the performance artificially. To
retrieve good-quality captions for the Visual Genome dataset [10], we used
annotated image descriptions from the COCO-captions [3] which intersect for
more than 50% with VG. Captions for the rest of the images were generated
using the state-of-the-art BLIP-2 model [11] for image captioning, which is
pre-trained on COCO-captions. Given the captions, we generated Textual Scene
Graphs using the Stanford NLP Parser, following the SPICE method [1]. Here the
idea is to use several parsing rules to extract $<subject,predicate,object>$
triplets from the free-form caption. Finally, we computed the cosine
similarity distance ($\theta=0.9$) between GLoVe language embeddings [24] of
triplets from the generated Scene Graphs and the Textual Scene Graph (TSG)
associated with the same image, as the vocabulary of the two distributions is
different. We kept only the top-1 distance for every triplet in the VSG as a
match with the corresponding TSG triplet and aggregated all results per image,
as in original R@k and mR@k implementations.

##  5 Experiments

In the following, we compare the performance in latency and accuracy metrics
between traditional two-stage approaches with Faster-RCNN equipped with a
ResNeXt-101 and our new architecture which uses YOLOV8 exclusively as an
object detection backbone. In SGG, the most widely used dataset is Visual
Genome [10]. The commonly used split of the data is called VG150 and contains
annotations from the top 150 object classes and top 50 predicate classes.
However, this split of the data suffers from severe biases [33, 23] and issues
such as the presence of ambiguous classes (e.g. the classes ”people”, ”men”
etc) [33, 18]. To cope with this problem, we decided to use the IndoorVG split
of the dataset, which is a smaller version with 83 object classes and 37
predicate classes. This split has been manually curated to remove wrong or
ambiguous classes [22].

Regarding our object detector, YOLOV8 comes in different variants, ranging
from nano to large. For the following experiments, we use the medium version,
YOLOV8m. Our YOLOV8 model has been trained for 100 epochs on the Visual Genome
dataset with a batch size of 16, following the official implementation
222https://github.com/ultralytics/ultralytics.

###  5.1 Comparison with two-stage approaches

We experimented our approach for five different relation prediction models:
Motifs-TDE [37, 27], VCTree-TDE [28, 27], Transformer [27], GPS-Net [19] and
PE-NET [39]. We computed the standard Recall@k metric for $k=[20,50,100]$ and
meanRecall@k for $k=[20,50,100]$. Both metrics for all settings of $k$ are
averaged in the F1@k metric, which efficiently represents the trade-off for
the model performance between head and tail predictions. For all approaches,
we re-trained the standard implementation by authors with both the Faster-RCNN
backbone and our modified YOLOV8 backbone. For all tests, we benchmark latency
on one Nvidia A6000 GPU with batch size 1 and image size 640*640. The latency
reported is the combination of object detection and relation prediction stages
for all models.

Figure 2: Latency versus F1@k for different models equipped with the Faster-
RCNN backbone and our modified YOLOV8 backbone.

In Fig. 2 we display the difference in latency and F1@k for the five different
models. Using YOLOV8, we experienced an average improvement of 19.4% in F1@k
compared to Faster-RCNN. This improvement is obviously due to the overall gain
of the accuracy of YOLOV8m in object detection, which performs at 35.1 mAP@50
versus 27.2 for Faster-RCNN on the Visual Genome dataset, see Tab. 1. However,
the gain in F1@k is not very strongly correlated to the gain in mAP@50, as we
measure a Pearson correlation coefficient of 0.80 between the two gains.
Regarding latency, we demonstrate an average improvement of 2.75x for using
YOLOV8 instead of Faster-RCNN, which is a considerable gap. The difference in
latency between the five models tested is also lower with YOLOV8 than Faster-
RCNN, this is due to the step of object classification which has been removed
in our implementation. As relation heads do not need to compute object
classes, computational complexity becomes lower and their average execution
time for relation prediction becomes very similar. The best model in F1@K, PE-
NET [39], is also the fastest one with a latency of 20.5ms which is a good
choice for real-time constraints. Under those settings, an average of 48FPS
can be attained, which is significantly higher than any other reported value
in the past for the task.

Figure 3: Latency versus IR@k for different models equipped with the Faster-
RCNN backbone and our modified YOLOV8 backbone.

As said earlier, the meanRecall@k and Recall@k metrics can be easily cheated
on and do not efficiently represent the performance of a model to produce
useful graphs for real-world applications, mainly because it does not take
into account the importance weight of relations to describe the scene. We used
the introduced IR@k metric with $k=[5,10]$ to evaluate this last point. Here
we purposely choose low values of $k$ as the main goal of this metric is to
represent the ability of models to output informative predictions with
confidence, such that top predictions can be directly sampled for reasoning.
We assume that in real-world applications a small number of high-quality
relations is more beneficial than a high number of medium to low-quality
relations to describe a scene.

We compare our approach with YOLOV8m and traditional Faster-RCNN in Fig. 3,
the metric reported is the average of IR@5 and IR@10. Surprisingly, we observe
a net improvement using YOLOV8 for all models. In contrast to F1@k,
performance is very close for all models, which highlights the importance of
proposal quality to produce informative scene graphs.

###  5.2 Latency and Number of Proposals

In the following, we dive into the principal variable responsible for latency
gain in Scene Graph Generation: the number of proposals. As explained before,
the second stage of SGG takes as input a fixed number of $n$ proposals as node
candidates and finds correct pairs and predicates. There could be a maximum of
$n*(n-1)$ possible pairs in the graph, thus when doing matching the
computational complexity is supposed to scale accordingly. To demonstrate this
hypothesis, we evaluate the performance of the PE-NET model [39] in both
latency and accuracy for different numbers of input proposals, ranging from 10
to 150 per image, with a step of 10. For all experiments, we ranked proposals
by confidence of the backbone and selected the top ones. For YOLOV8, proposals
are ranked after NMS.

Figure 4: Latency for the PE-NET model [39] using different number of
proposals per image, with batch size = 1.

We display the results of those experiments in Fig. 4. Interestingly, we
observe a plateau phenomenon using the Faster-RCNN above 100 proposals, which
doesn’t appear when using YOLOV8. By using 150 proposals with YOLOV8, the
latency is similar to 10 proposals with Faster-RCNN. To find the best trade-
off between latency and performance, we also measured the average F1@k for
different numbers of proposals, see Fig. 5. In this figure, we can see that
for both models, an optimal F1@k (left axis, plane line) is obtained at around
40 proposals per image. This means that the top 40 proposals returned by YOLO
or Faster-RCNN are of good enough quality to be valid node candidates for the
graph refinement step. In the same plot, we also measure the average IR@k for
the same set of settings (right axis, dotted line). Interestingly, we observe
a high IR@k for the lowest number of proposals, 10, even if the average F1@k
is not maximal. These results confirm the assumption that to obtain
informative graphs, the quality of object proposals is of utmost importance.
By crossing those numbers with latency per number of proposals (see Fig. 4),
we can find an optimal implementation for F1@k with $n=40$ and $n=18$ for an
optimal F1@k to IR@k trade-off for both YOLOV8 and Faster-RCNN.

Figure 5: Average F1@k and IR@k performance for the PE-NET model [39] using a
different number of proposals per image, with batch size 1.

##  6 Conclusion

In this work, we propose the first implementation of a true real-time Scene
Graph Generation procedure by leveraging the YOLOV8 object detector, with an
average improvement of 19.4% in the F1@k metric for the task. Our main finding
is that the performance and latency of SGG models are heavily correlated with
the quality and quantity of object proposals generated by the object detector.
However, regarding both overall performance and latency, an optimal trade-off
can be found by using 40 object proposals as input to the relation prediction
stage. We also share findings on the quality of generated graphs related to
the amount of informative relations they contain. In contrast to standard
evaluation metrics that measure the correctness of relations prediction, we
propose a new metric, the InformativeRecall@k (IR@k), which efficiently
benchmarks the ability of models to produce informative relations first. Using
this metric, we observed that a low number (i.e. 10) of high-quality proposals
produces a more informative graph even though relations for this number of
proposals are deemed of less quality by standard metrics. This last point
illustrates the limits and challenges of current evaluation metrics and
benchmarks used in the task which may not be appropriate to evaluate real-
world use cases of Scene Graph Generation.

## References

  * [1] Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould.  Spice: Semantic propositional image caption evaluation.  In Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part V 14, pages 382–398. Springer, 2016.
  * [2] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European conference on computer vision, pages 213–229. Springer, 2020.
  * [3] Xinlei Chen, Hao Fang, Tsung-Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco captions: Data collection and evaluation server.  arXiv preprint arXiv:1504.00325, 2015.
  * [4] Yuren Cong, Michael Ying Yang, and Bodo Rosenhahn.  RelTR: Relation Transformer for Scene Graph Generation, Aug. 2022.  arXiv:2201.11460 [cs] version: 2.
  * [5] Vinay Damodaran, Sharanya Chakravarthy, Akshay Kumar, Anjana Umapathy, Teruko Mitamura, Yuta Nakashima, Noa Garcia, and Chenhui Chu.  Understanding the role of scene graphs in visual question answering.  arXiv preprint arXiv:2101.05479, 2021.
  * [6] Xingning Dong, Tian Gan, Xuemeng Song, Jianlong Wu, Yuan Cheng, and Liqiang Nie.  Stacked Hybrid-Attention and Group Collaborative Learning for Unbiased Scene Graph Generation.  In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 19405–19414, New Orleans, LA, USA, June 2022. IEEE.
  * [7] Samir Yitzhak Gadre, Kiana Ehsani, Shuran Song, and Roozbeh Mottaghi.  Continuous scene representations for embodied ai.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14849–14859, 2022.
  * [8] Jinbae Im, JeongYeon Nam, Nokyung Park, Hyungmin Lee, and Seunghyun Park.  Egtr: Extracting graph from transformer for scene graph generation.  arXiv preprint arXiv:2404.02072, 2024.
  * [9] Glenn Jocher, Ayush Chaurasia, and Jing Qiu.  Ultralytics YOLO, Jan. 2023.
  * [10] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A. Shamma, Michael S. Bernstein, and Li Fei-Fei.  Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations.  International Journal of Computer Vision, 123(1):32–73, May 2017.
  * [11] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.  Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models.  In International conference on machine learning, pages 19730–19742. PMLR, 2023.
  * [12] Lin Li, Long Chen, Yifeng Huang, Zhimeng Zhang, Songyang Zhang, and Jun Xiao.  The Devil is in the Labels: Noisy Label Correction for Robust Scene Graph Generation.  In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 18847–18856, New Orleans, LA, USA, June 2022. IEEE.
  * [13] Rongjie Li, Songyang Zhang, and Xuming He.  SGTR: End-to-end Scene Graph Generation with Transformer.  In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 19464–19474, New Orleans, LA, USA, June 2022. IEEE.
  * [14] Rongjie Li, Songyang Zhang, Bo Wan, and Xuming He.  Bipartite Graph Network with Adaptive Message Passing for Unbiased Scene Graph Generation.  In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 11104–11114, Nashville, TN, USA, June 2021. IEEE.
  * [15] Wei Li, Haiwei Zhang, Qijie Bai, Guoqing Zhao, Ning Jiang, and Xiaojie Yuan.  PPDL: Predicate Probability Distribution based Loss for Unbiased Scene Graph Generation.  In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 19425–19434, New Orleans, LA, USA, June 2022. IEEE.
  * [16] Xingchen Li, Long Chen, Jian Shao, Shaoning Xiao, Songyang Zhang, and Jun Xiao.  Rethinking the Evaluation of Unbiased Scene Graph Generation, Oct. 2022.  arXiv:2208.01909 [cs].
  * [17] Xinghang Li, Di Guo, Huaping Liu, and Fuchun Sun.  Embodied semantic scene graph generation.  In Conference on robot learning, pages 1585–1594. PMLR, 2022.
  * [18] Yuanzhi Liang, Yalong Bai, Wei Zhang, Xueming Qian, Li Zhu, and Tao Mei.  VrR-VG: Refocusing Visually-Relevant Relationships.  In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 10402–10411, Seoul, Korea (South), Oct. 2019. IEEE.
  * [19] Xin Lin, Changxing Ding, Jinquan Zeng, and Dacheng Tao.  GPS-Net: Graph Property Sensing Network for Scene Graph Generation.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 3743–3752, Seattle, WA, USA, June 2020. IEEE.
  * [20] Si Liu, Zitian Wang, Yulu Gao, Lejian Ren, Yue Liao, Guanghui Ren, Bo Li, and Shuicheng Yan.  Human-centric Relation Segmentation: Dataset and Solution.  IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1–1, 2021.  Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * [21] Yichao Lu, Himanshu Rai, Jason Chang, Boris Knyazev, Guangwei Yu, Shashank Shekhar, Graham W. Taylor, and Maksims Volkovs.  Context-aware Scene Graph Generation with Seq2Seq Transformers.  In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 15911–15921, Montreal, QC, Canada, Oct. 2021. IEEE.
  * [22] Maëlic Neau, Paulo Santos, Anne-Gwenn Bosser, and Cédric Buche.  In defense of scene graph generation for human-robot open-ended interaction in service robotics.  In Robot World Cup, pages 299–310. Springer, 2023.
  * [23] Maëlic Neau, Paulo E Santos, Anne-Gwenn Bosser, and Cédric Buche.  Fine-grained is too coarse: A novel data-centric approach for efficient scene graph generation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11–20, 2023.
  * [24] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014.
  * [25] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 779–788, 2016.
  * [26] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  Advances in neural information processing systems, 28, 2015.
  * [27] Kaihua Tang, Yulei Niu, Jianqiang Huang, Jiaxin Shi, and Hanwang Zhang.  Unbiased Scene Graph Generation From Biased Training.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 3713–3722, Seattle, WA, USA, June 2020. IEEE.
  * [28] Kaihua Tang, Hanwang Zhang, Baoyuan Wu, Wenhan Luo, and Wei Liu.  Learning to Compose Dynamic Tree Structures for Visual Contexts.  In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 6612–6621, Long Beach, CA, USA, June 2019. IEEE.
  * [29] Wenbin Wang, Ruiping Wang, Shiguang Shan, and Xilin Chen.  Exploring Context and Visual Pattern of Relationship for Scene Graph Generation.  In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8180–8189, Long Beach, CA, USA, June 2019. IEEE.
  * [30] Bin Wen, Jie Luo, Xianglong Liu, and Lei Huang.  Unbiased Scene Graph Generation via Rich and Fair Semantic Extraction, Feb. 2020.  arXiv:2002.00176 [cs].
  * [31] Danfei Xu, Yuke Zhu, Christopher B. Choy, and Li Fei-Fei.  Scene Graph Generation by Iterative Message Passing.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5410–5419, 2017.
  * [32] Shaotian Yan, Chen Shen, Zhongming Jin, Jianqiang Huang, Rongxin Jiang, Yaowu Chen, and Xian-Sheng Hua.  PCPL: Predicate-Correlation Perception Learning for Unbiased Scene Graph Generation.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 265–273, Seattle WA USA, Oct. 2020. ACM.
  * [33] Jingkang Yang, Yi Zhe Ang, Zujin Guo, Kaiyang Zhou, Wayne Zhang, and Ziwei Liu.  Panoptic Scene Graph Generation.  In Shai Avidan, Gabriel Brostow, Moustapha Cissé, Giovanni Maria Farinella, and Tal Hassner, editors, Computer Vision – ECCV 2022, Lecture Notes in Computer Science, pages 178–196, Cham, 2022. Springer Nature Switzerland.
  * [34] Xuewen Yang, Yingru Liu, and Xin Wang.  Reformer: The relational transformer for image captioning.  In Proceedings of the 30th ACM International Conference on Multimedia, pages 5398–5406, 2022.
  * [35] Kanghoon Yoon, Kibum Kim, Jinyoung Moon, and Chanyoung Park.  Unbiased Heterogeneous Scene Graph Generation with Relation-aware Message Passing Neural Network, Dec. 2022.  arXiv:2212.00443 [cs] version: 1.
  * [36] Jing Yu, Yuan Chai, Yujing Wang, Yue Hu, and Qi Wu.  CogTree: Cognition Tree Loss for Unbiased Scene Graph Generation.  In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 1274–1280, Montreal, Canada, Aug. 2021. International Joint Conferences on Artificial Intelligence Organization.
  * [37] Rowan Zellers, Mark Yatskar, Sam Thomson, and Yejin Choi.  Neural Motifs: Scene Graph Parsing with Global Context.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5831–5840, Salt Lake City, UT, June 2018. IEEE.
  * [38] Hanwang Zhang, Zawlin Kyaw, Shih-Fu Chang, and Tat-Seng Chua.  Visual Translation Embedding Network for Visual Relation Detection.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3107–3115, Honolulu, HI, July 2017. IEEE.
  * [39] Chaofan Zheng, Xinyu Lyu, Lianli Gao, Bo Dai, and Jingkuan Song.  Prototype-based embedding network for scene graph generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 22783–22792, 2023.


meas}^{\mathbb{P}_{n}})f({Z^{\bm{s}(\mathbb{B})}},\Lambda^{\mathbb{P}_{n}})\frac{f(P,\mathcal{S}_{H})}{f(P^{\circlearrowright
H},\mathcal{S}_{H})}\leavevmode\nobreak\ ,$ (84)

where $\mathbb{B}$ is the support of $Q=\phi(H)[P]$, and that

$\displaystyle\mathbb{E}[N_{Q,m_{3}}]=f({Z^{\bm{s}(\mathbb{B})}},\Lambda_{\rm
meas}^{\mathbb{P}_{n}})f({Z^{\bm{s}(\mathbb{B})}},\Lambda^{\mathbb{P}_{n}})f^{m_{3}}(P^{\circlearrowright
H},\mathcal{S}_{H})\leavevmode\nobreak\ .$ (85)

They are independent estimates, and their ratio is hence

$\displaystyle\mathbb{E}\left[\frac{\hat{A}}{N_{Q,m_{3}}}\right]=f(P,\mathcal{S}_{H})f^{m_{3}-1}(P^{\circlearrowright
H},\mathcal{S}_{H})\leavevmode\nobreak\ .$ (86)


# Extended Cyclic Codes Sandwiched Between Reed–Muller Codes

Yan Xu, Changjiang Ji, Ran Tao, Sihuang Hu  Y. Xu and C. Ji are with School of
Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237,
China. R. Tao and S. Hu are with School of Cyber Science and Technology,
Shandong University, Qingdao, Shandong, 266237, China, and Key Laboratory of
Cryptologic Technology and Information Security, Ministry of Education,
Shandong University, Qingdao, Shandong, 266237, China. Research partially
funded by National Key R&D Program of China under Grant No. 2021YFA1001000,
National Natural Science Foundation of China under Grant No. 12001322,
Shandong Provincial Natural Science Foundation under Grant No. ZR202010220025,
and a Taishan scholar program of Shandong Province. This work was in part
presented at ISIT 2021. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The famous Barnes–Wall lattices can be obtained by applying Construction D to
a chain of Reed–Muller codes. By applying Construction
${\textup{D}}^{\textup{(cyc)}}$ to a chain of extended cyclic codes sandwiched
between Reed–Muller codes, Hu and Nebe (J. London Math. Soc. (2) 101 (2020)
1068-1089) constructed new series of universally strongly perfect lattices
sandwiched between Barnes–Wall lattices. In this paper, we first extend their
construction to generalized Reed–Muller codes, and then explicitly determine
the minimum vectors of those new sandwiched Reed–Muller codes for some special
cases.

##  I Introduction

Reed–Muller (RM) codes were introduced by Muller [1] in 1954, and shortly
after Reed [2] developed a decoding algorithm. RM codes are among the oldest,
simplest and perhaps most ubiquitous family of codes. They are used in many
areas related to coding theory, such as electrical engineering and computer
science [3, 4, 5, 6]. Moreover, due to their favourable theoretical and
mathematical properties, RM codes have also been extensively studied in
theoretical computer science [7]. Despite the simplicity of their
construction, many of their important properties are still under investigation
[8].

The minimum distance of $r$-th order binary RM codes ${\mathcal{R}}(r,n)$ is
$2^{n-r}$. The set of minimum vectors (minimum weight codewords) of binary RM
codes was first described by Kasami et al. [9]. Delsarte, Goethals and
MacWilliams [10] characterized the set of minimum vectors of generalized RM
codes. In 1998, Charpin [11] gave a new proof of the results of [10] for some
particular case of generalized RM codes using Newton identities. In [12]
Leducq proved the same results using arguments from affine geometry.

The famous Barnes–Wall lattices $\textup{BW}_{2m}$ of dimension $2^{2m}$ (with
$m\in\mathbb{N}$) form an important infinite family of even lattices [13, 14].
One way to construct $\textup{BW}_{2m}$ is applying Construction D [15,
Chapter 8] to a chain of RM codes. Recently, Hu and Nebe [16] constructed new
series of $2^{2m}$-dimensional universally strongly perfect lattices
sandwiched between Barnes–Wall lattices. Those lattices can be obtained by
applying Construction ${\textup{D}}^{\textup{(cyc)}}$ [16, Definition 2.5] to
a chain of extended cyclic codes sandwiched between binary RM codes.

In this paper, we first generalize the construction in [16] to give new
extended cyclic codes sandwiched between generalized RM codes. Then we employ
the tools developed by Augot [17, 18] and Charpin [11] to explicitly determine
the minimum vectors of those new sandwiched RM codes for some special cases.
The paper is organized as follows. In Section II, we briefly introduce some
basic notations and relevant knowledge of cyclic codes, Newton identities,
affine polynomials and affine invariant codes. Then we give the construction
of extended cyclic codes sandwiched between RM codes in Section III. In
Section IV, we present the dual code and the minimum distance of those new
sandwiched RM codes. In Section V we show how to find the minimum vectors of
those codes. Some concluding remarks are given in Section VI.

##  II Preliminaries

The following notation will be used throughout this paper. Let $p$ be a prime,
$l$ a positive integer, $q=p^{l}$, and $\mathbb{F}_{q}$ the finite field of
order $q$. Let $n$ be a positive integer, $N=q^{n}-1$, and
$\mathbb{F}_{q^{n}}$ the finite field of order $q^{n}$.

###  II-A Group algebra

Let $\mathcal{M}$ be the group algebra
$\mathbb{F}_{q}[\mathbb{F}_{q^{n}}^{*},\times]$, where
$\mathbb{F}_{q^{n}}^{*}$ is the multiplicative group of $\mathbb{F}_{q^{n}}$.
An element of ${\mathcal{M}}$ is a formal sum

$x=\sum_{g\in\mathbb{F}_{q^{n}}^{*}}x_{g}(g),\ x_{g}\in\mathbb{F}_{q}.$

The scalar multiplication, addition and multiplication in ${\mathcal{M}}$ are
given as

$\displaystyle\lambda\left(\sum_{g\in\mathbb{F}_{q^{n}}^{*}}x_{g}(g)\right)$
$\displaystyle=\sum_{g\in\mathbb{F}_{q^{n}}^{*}}\lambda x_{g}(g),$
$\displaystyle\sum_{g\in\mathbb{F}_{q^{n}}^{*}}x_{g}(g)+\sum_{g\in\mathbb{F}_{q^{n}}^{*}}y_{g}(g)$
$\displaystyle=\sum_{g\in\mathbb{F}_{q^{n}}^{*}}(x_{g}+y_{g})(g),$
$\displaystyle\bigg{(}\sum_{g\in\mathbb{F}_{q^{n}}^{*}}x_{g}(g)\bigg{)}\bigg{(}\sum_{g\in\mathbb{F}_{q^{n}}^{*}}y_{g}(g)\bigg{)}$
$\displaystyle=\sum_{g\in\mathbb{F}_{q^{n}}^{*}}\Big{(}\sum_{hk=g\atop{h,k\in\mathbb{F}_{q^{n}}^{*}}}x_{h}y_{k}\Big{)}(g).$

We define the following $\mathbb{F}_{q}$-linear map from $\mathcal{M}$ into
$\mathbb{F}_{q^{n}}$:

$\rho_{s}\bigg{(}\sum_{g\in{\mathbb{F}_{q^{n}}^{*}}}x_{g}(g)\bigg{)}=\sum_{g\in{\mathbb{F}_{q^{n}}^{*}}}x_{g}(g^{s}),\
s\in\mathbb{Z}_{\geq 0}.$

Note that $\rho_{s}=\rho_{(s\mod N)}$ as $\mathbb{F}_{q^{n}}^{*}$ is a
multiplicative group of order $N$.

Let $\mathcal{A}$ be the group algebra $\mathbb{F}_{q}[\mathbb{F}_{q^{n}},+]$.
An element of ${\mathcal{A}}$ is a formal sum

$x=\sum_{g\in\mathbb{F}_{q^{n}}}x_{g}(g),\ x_{g}\in\mathbb{F}_{q}.$

The operations in ${\mathcal{A}}$ are given as

$\displaystyle\lambda\left(\sum_{g\in\mathbb{F}_{q^{n}}}x_{g}(g)\right)$
$\displaystyle=\sum_{g\in\mathbb{F}_{q^{n}}}\lambda x_{g}(g),$
$\displaystyle\sum_{g\in\mathbb{F}_{q^{n}}}x_{g}(g)+\sum_{g\in\mathbb{F}_{q^{n}}}y_{g}(g)$
$\displaystyle=\sum_{g\in\mathbb{F}_{q^{n}}}(x_{g}+y_{g})(g),$
$\displaystyle\bigg{(}\sum_{g\in\mathbb{F}_{q^{n}}}x_{g}(g)\bigg{)}\bigg{(}\sum_{g\in\mathbb{F}_{q^{n}}}y_{g}(g)\bigg{)}$
$\displaystyle=\sum_{g\in\mathbb{F}_{q^{n}}}\Big{(}\sum_{h+k=g\atop{h,k\in\mathbb{F}_{q^{n}}}}x_{h}y_{k}\Big{)}(g).$

Note that the multiplication in ${\mathcal{M}}$ and ${\mathcal{A}}$ are
distinct.

###  II-B Cyclic codes

A linear code ${\mathcal{C}}$ is _cyclic_ if any cyclic shift of a codeword is
also a codeword, i.e., whenever $(c_{0},...,c_{n-1})\in{\mathcal{C}}$ then so
is $(c_{n-1},c_{0},...,c_{n-2})$. Recall that $N=q^{n}-1$. Set
$[0,N-1]=\\{0,1,\cdots,N-1\\}$. Let $\alpha$ be a primitive element of
$\mathbb{F}_{q^{n}}$. We associate with the vector $(c_{0},c_{1},...,c_{N-1})$
in $\mathbb{F}_{q}^{N}$ the element $\sum_{i=0}^{N-1}c_{i}(\alpha^{i})$ in
${\mathcal{M}}$. It is not hard to check that a (primitive) cyclic code of
length $N$ over $\mathbb{F}_{q}$ is just an ideal of $\mathcal{M}$. The
_defining set $T$_ of $\mathcal{C}$ is the largest subset of the range
$[0,N-1]$, invariant under the multiplication by $q\pmod{N}$, such that any
codeword $x\in\mathcal{C}$ satisfies $\rho_{s}(x)=0,\ \forall s\in T.$ The set
$T$ is a union of $q$-cyclotomic cosets modulo $N$. Any $s\in T$ corresponds
to a zero of ${\mathcal{C}}$, say $\alpha^{s}$. The set $Z=\\{\alpha^{s}\ |\
s\in T\\}$ is the _zero set_ of ${\mathcal{C}}$. If $0\notin T$ we denote the
_extended code_ of ${\mathcal{C}}$ as

$\widehat{{\mathcal{C}}}=\left\\{\bigg{(}-\sum_{g\in{\mathbb{F}_{q^{n}}^{*}}}x_{g}\bigg{)}(0)+\sum_{g\in{\mathbb{F}_{q^{n}}^{*}}}x_{g}(g)~{}\Bigg{|}~{}\sum_{g\in{\mathbb{F}_{q^{n}}^{*}}}x_{g}(g)\in{\mathcal{C}}\right\\}.$

By convention, the attached symbol is labelled by $0$, and the defining set of
$\widehat{{\mathcal{C}}}$ is $T\cup\\{0\\}$.

Let $x\in\mathcal{C}$. The _Mattson–Solomon (MS) polynomial_ [19] of $x$ is
defined by

$M_{x}(X)=\sum_{s=0}^{N-1}\rho_{N-s}(x)X^{s}~{},$

whose coefficients are in $\mathbb{F}_{q^{n}}$. The _support_ of a codeword
$x$ with Hamming weight $w$ is

$supp(x)=\\{g\in\mathbb{F}_{q^{n}}^{*}\mid x_{g}\neq
0\\}=\\{g_{1},\ldots,g_{w}\\}.$

The _locator polynomial_ of $x$ is the polynomial over $\mathbb{F}_{q^{n}}$
defined as

$\sigma_{x}(X)=\prod_{i=1}^{w}(1-g_{i}X)=1+\sum_{j=1}^{w}\sigma_{j}X^{j}.$

The coefficients $\sigma_{j},1\leqslant j\leqslant w$, are the elementary
symmetric functions of the _locators_ $g_{i}$, $1\leqslant i\leqslant w$, that
is,

$\sigma_{j}=(-1)^{j}\sum_{1\leqslant i_{1}<i_{2}<\ldots<i_{j}\leqslant
w}g_{i_{1}}g_{i_{2}}\cdots g_{i_{j}}.$

For convenience we also write $\Lambda_{N-s}=\rho_{N-s}(x)$ for $0\leqslant
s\leqslant N$ and note that $\Lambda_{0}=\Lambda_{N}$.

###  II-C Newton identities

The Newton identities is a tool of great interest for describing a set of
codewords, particularly for minimum vectors of cyclic codes [17][18][11].

######  Theorem 1.

[18][11, Theorem 3.5] Let $x\in\mathcal{M}$ be a codeword of weight $w$. Let
$\Lambda_{1},\ldots,\Lambda_{N}$ be the coefficients of the MS polynomial of
$x$ and denote by $\sigma_{0},\ldots,\sigma_{w}$ the coefficients of the
locator polynomial of $x$ (note that $\sigma_{0}=1$). Then the $\sigma_{i}$
and the $\Lambda_{i}$ are linked by the generalized Newton identities:

$\displaystyle\forall\,j\geqslant 0,\
\Lambda_{j+w}+\sigma_{1}\Lambda_{j+w-1}+\ldots+\sigma_{w}\Lambda_{j}=0.$ (1)

We now consider the ring
$\mathbb{F}_{q^{n}}[\Lambda_{0},\ldots,\Lambda_{N-1},\sigma_{1},\ldots,\sigma_{w}]$
and the algebraic system provided from a given cyclic code $\mathcal{C}$ by
the Newton identities. Let $\mathcal{C}$ be a cyclic code in $\mathcal{M}$
with the defining set $T$. We define the system $\mathcal{S_{C}}(w)$, where
the $\Lambda_{i}$ and the $\sigma_{i}$ are the indeterminates, as follows:

$\mathcal{S_{C}}(w)=\left\\{\begin{array}[]{l}\Lambda_{w+1}+\Lambda_{w}\sigma_{1}+\ldots+\Lambda_{1}\sigma_{w}=0~{},\\\
\Lambda_{w+2}+\Lambda_{w+1}\sigma_{1}+\ldots+\Lambda_{2}\sigma_{w}=0~{},\\\
\qquad\vdots\\\
\Lambda_{w+N}+\Lambda_{w+N-1}\sigma_{1}+\ldots+\Lambda_{N}\sigma_{w}=0~{},\\\
\forall i\in[0,N-1]~{},~{}~{}\Lambda_{qi~{}mod~{}N}=\Lambda_{i}^{q}~{},\\\
\forall i\in[0,N-1]~{},~{}~{}\Lambda_{i+N}=\Lambda_{i}~{},\\\ \forall i\in
T~{},~{}~{}\Lambda_{i}=0~{}.\end{array}\right.$ (2)

The system $\mathcal{S_{C}}(w)$, consisting of $3N+|T|$ polynomials in $N+w$
variables over the field $\mathbb{F}_{q^{n}}$, defines an ideal in the ring
$\mathbb{F}_{q^{n}}[\Lambda_{0},\ldots,\Lambda_{N-1},\sigma_{1},\ldots,\sigma_{w}]$.

######  Corollary 2.

[11, Corollary 3.8] Let $\mathcal{C}$ be a cyclic code in $\mathcal{M}$ whose
minimum distance $\delta$ satisfies $\delta\geqslant w$. Then the minimum
distance of $\mathcal{C}$ is exactly $w$ if and only if the system
$\mathcal{S_{C}}(w)$ has at least one solution
$(\Lambda_{0},\ldots,\Lambda_{N-1},\sigma_{1},\ldots,\sigma_{w})\in\mathbb{F}_{q^{n}}^{N+w}$.
For any such solution the codeword $x$ whose MS polynomial is
$\sum^{N-1}_{s=0}\Lambda_{N-s}X^{s}$, is a codeword of $\mathcal{C}$ of weight
$w$. The $\sigma_{i},0\leqslant i\leqslant w$, are the coefficients of the
locator polynomial of $x$. The number of codewords of weight $w$ in
$\mathcal{C}$ is equal to the number of solutions of $\mathcal{S_{C}}(w)$.

###  II-D Affine polynomials

An _affine polynomial_ is a polynomial of the form

$f(X)=c+\gamma_{0}X+\gamma_{1}X^{q}+\ldots+\gamma_{k}X^{q^{k}}$

with coefficients in some extension field of $\mathbb{F}_{q}$. It is well
known that the roots of $f(X)$ form an affine space over $\mathbb{F}_{q}$.
Since the derivative of $f(X)$ is $\gamma_{0}$, the roots of $f(X)$ have
multiplicity one if and only if $\gamma_{0}\neq 0$. So $\gamma_{0}\neq 0$ is
necessary if we want to consider $f(X)$ as a locator polynomial.

Assume that the affine polynomial $f(X)$ splits in $\mathbb{F}_{q^{n}}$ with
roots of multiplicity one. Then $f(X)$ can be identified to be the codeword of
$\mathcal{A}$ whose support is the affine space of their roots and whose
symbols are from $\\{0,1\\}$. More precisely, define

$\displaystyle x=\lambda\sum_{g\in V_{k}}(g+h),~{}\lambda\in\mathbb{F}_{q},$
(3)

where $V_{k}$ is a subspace of $\mathbb{F}_{q^{n}}$ of dimension $k$ over
$\mathbb{F}_{q}$. Such a codeword can be identified, up to scalar
multiplication, with an affine polynomial whose roots are the elements of the
affine space $h+V_{k}$.

The following result presents the form of the locator polynomial of a codeword
whose support is coming from some subspace.

######  Proposition 3.

[11, Proposition 3.14] Let $\delta=q^{k}-1,\delta<N$, and set

${\mathcal{I}}_{k}=\\{q^{k}-q^{j}\mid j\in[0,k-1]\\}.$

Define the polynomial of degree $\delta$ ($\sigma_{\delta}\neq 0$):

$\sigma(X)=1+\sum_{i\in{\mathcal{I}}_{k}}\sigma_{i}X^{i},\sigma_{i}\in\mathbb{F}_{q^{n}}.$

Denote by $v_{i}$ the root of $\sigma(X)$ and set $g_{i}=v_{i}^{-1}$. Then (i)
and (ii) are equivalent.

  * (i)

$\sigma(X)$ splits in $\mathbb{F}_{q^{n}}$ with roots of multiplicity one.

  * (ii)

$\sigma(X)$ is the locator polynomial of codewords of the form (3) such that
$h=0$ and $V_{k}$ is the set $\\{0,g_{1},\cdots,g_{\delta}\\}$.

Let $u\in[0,N]$. We write the $q$-ary expansion of $u$ as
$u=\sum_{i=0}^{n-1}u_{i}q^{i},\ u_{i}\in[0,q-1]$. The $q$-_weight_ of $u$ is

$wt_{q}(u)=\sum_{i=0}^{n-1}u_{i}.$

######  Theorem 4.

[9, Theorem 9] Let $V_{k}$ be any subspace of $\mathbb{F}_{q^{n}}$ of
dimension k over $\mathbb{F}_{q}$, the field of order $q$. Then the power sum

$\sum_{v\in V_{k}}v^{i},\ i\in[1,q^{n}-1],$

are zero when the $q$-weight of $i$ is less than $k(q-1)$.

###  II-E Affine invariant codes

Addition and multiplication in the field $\mathbb{F}_{q^{n}}$ involve natural
transformations on elements of ${\mathcal{A}}$ including the following affine
permutations

$\sigma_{u,v}:\sum_{g\in\mathbb{F}_{q^{n}}}x_{g}(g)\longmapsto\sum_{g\in\mathbb{F}_{q^{n}}}x_{g}(ug+v),~{}~{}u\in\mathbb{F}_{q^{n}}^{*},~{}~{}v\in\mathbb{F}_{q^{n}}.$

The permutations $\sigma_{u,0}$ consist of shifting symbols unless the symbol
labelled by “$0$”. It is exactly the shift on codewords punctured in the
position “$0$”. On the other hand we have

$\sigma_{1,v}(\sum_{g\in\mathbb{F}_{q^{n}}}x_{g}(g))=(v)(\sum_{g\in\mathbb{F}_{q^{n}}}x_{g}(g)).$

Hence we see that a code $\mathcal{C}\subseteq{\mathcal{A}}$, which is
invariant under the permutations $\sigma_{u,v}$
$(u\in\mathbb{F}_{q^{n}}^{*},v\in\mathbb{F}_{q^{n}})$, is an ideal of
$\mathcal{A}$. Such a code is called an _affine-invariant code_.

Kasami et al. [20, 21] showed that an extended cyclic code is affine-invariant
if and only if its defining set satisfies a certain combinatorial property as
follows. Let $S=[0,q^{n}-1]$. We denote by $\preceq$ the partial order
relation on $S$ defined as follows:

$\forall s,t\in S:s\preceq t\Leftrightarrow s_{i}\leqslant t_{i},i\in[0,n-1],$

where $\sum_{i=0}^{n-1}s_{i}q^{i}$ is the $q\text{-}ary$ expansion of $s$ and
$\sum_{i=0}^{n-1}t_{i}q^{i}$ is the $q\text{-}ary$ expansion of $t$.

######  Lemma 5.

[20, 21, 11, Theorem 2.14] Let us define the map

$\Delta:T\subset S\mapsto\Delta(T)=\bigcup_{t\in T}\\{s\in S,\ s\preceq t\\}.$

Let ${\mathcal{C}}$ be an extended cyclic code, with the defining set $T$.
Then ${\mathcal{C}}$ is affine-invariant if and only if $\Delta(T)=T$.

##  III Definitions of sandwiched Reed–Muller codes

From now on, we set $n=2m$ and $\mathbb{F}_{q^{n}}=\mathbb{F}_{q}(\alpha)$
where $\alpha$ is a primitive element of $\mathbb{F}_{q^{n}}$. The following
notations will be used.

######  Notation 6.

  * (a)

Any integer $u$, $0\leqslant u\leqslant q^{n}-1$, has a unique expression as
$u=\sum_{i=0}^{{n}-1}u_{i}q^{i}$ with $u_{i}\in\\{0,1,\cdots,q-1\\}$. We
define

$\displaystyle O(u)$ $\displaystyle:=\sum_{0\leqslant i\leqslant{n}-1\atop
i\textup{~{}is~{}odd}}u_{i}\textup{ and }$ $\displaystyle E(u)$
$\displaystyle:=\sum_{0\leqslant i\leqslant{n}-1\atop
i\textup{~{}is~{}even}}u_{i}.$

Note that $q^{n}-1-u=\sum_{i=0}^{{n}-1}(q-1-u_{i})q^{i}$. Hence

$\displaystyle\begin{split}\textup{wt}_{q}(q^{n}-1-u)=n(q-1)-\textup{wt}_{q}(u),\\\
O(q^{n}-1-u)-E(q^{n}-1-u)=E(u)-O(u).\end{split}$ (4)

  * (b)

For $-1\leqslant r<{n}(q-1)$, put

$Z_{r}:=\\{\alpha^{u}\mid 0<u\leqslant
q^{n}-1,\textup{wt}_{q}(u)\leqslant{n}(q-1)-r-1\\}.$

  * (c)

For $0\leqslant r\leqslant{n}(q-1)$, let

$\Theta^{(r)}:=\\{\alpha^{u}\mid 0\leqslant u\leqslant
q^{n}-1,\textup{wt}_{q}(u)={n}(q-1)-r\\}.$

  * (d)

For $0\leqslant k\leqslant m(q-1)$, we put

$\Theta_{k}:=\\{\alpha^{u}\mid 0\leqslant u\leqslant q^{n}-1,\
|O(u)-E(u)|=k\\}.$

  * (e)

Note that $\textup{wt}_{q}(u)$ and $|O(u)-E(u)|$ have the same parity. For
$0\leqslant r\leqslant{n}(q-1)$, let

$\displaystyle M_{r}$ $\displaystyle:=$
$\displaystyle\begin{cases}M_{+}:=\\{0\leqslant k\leqslant
m(q-1)~{}|~{}k\textup{~{}is even}\\}&\textup{if }r\textup{\ is even}\\\
M_{-}:=\\{0\leqslant k\leqslant m(q-1)~{}|~{}k\textup{~{}is odd}\\}&\textup{if
}r\textup{\ is odd.}\\\ \end{cases}$

For $0\leqslant r\leqslant{n}(q-1)$ and $k\in M_{r}$, we define

$\displaystyle\Theta^{(r)}_{k}:$ $\displaystyle=\\{\alpha^{u}\mid 0\leqslant
u\leqslant q^{n}-1,\textup{wt}_{q}(u)={n}(q-1)-r,$
$\displaystyle\qquad|O(u)-E(u)|=k\\}$
$\displaystyle=\Theta^{(r)}\cap\Theta_{k}.$

Obviously $\Theta^{(r)}\cap\Theta_{k}=\emptyset$ if $k\not\in M_{r}$. It is
ready to see that $\Theta^{(r)}\cap\Theta_{k}$ is a union of $q$-cyclotomic
cosets modulo $N$ as $n=2m$ is even.

In order to compute the dimension of our new codes, now we use a counting
argument to show the size of the set $\Theta^{(r)}_{k}$.

######  Lemma 7.

For $0\leqslant r\leqslant{n}(q-1)$ and $k\in M_{r}$, we have

$\displaystyle\big{|}\Theta^{(r)}_{k}\big{|}=\begin{cases}2\left(\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r-k}{2}-iq+m-1\choose\frac{n(q-1)-r-k}{2}-iq}\right)\left(\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r+k}{2}-iq+m-1\choose\frac{n(q-1)-r+k}{2}-iq}\right)&k\neq
0\\\ \left(\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r}{2}-iq+m-1\choose\frac{n(q-1)-r}{2}-iq}\right)^{2}&k=0.\end{cases}$

###### Proof.

Firstly, we set

$\displaystyle\Delta^{(r)}_{k}$ $\displaystyle=\\{u\mid 0\leqslant u\leqslant
q^{n}-1,\textup{wt}_{q}(u)=n(q-1)-r,|O(u)-E(u)|=k\\},$ $\displaystyle S_{1}$
$\displaystyle=\\{u\in\Delta^{(r)}_{k}\mid O(u)-E(u)=k\\},$ $\displaystyle
S_{2}$ $\displaystyle=\\{u\in\Delta^{(r)}_{k}\mid E(u)-O(u)=k\\}.$

Then we have $|S_{1}|=|S_{2}|$ and

$|\Theta^{(r)}_{k}|=|\Delta^{(r)}_{k}|=\begin{cases}2|S_{1}|&\mbox{~{}if~{}}k\neq
0\\\ |S_{1}|&\mbox{~{}if~{}}k=0.\end{cases}$

Now we compute $|S_{1}|$. Suppose that $u\in S_{1}$. Then it is ready to check
that

$\displaystyle E(u)$ $\displaystyle=\frac{n(q-1)-r-k}{2},$ $\displaystyle
O(u)$ $\displaystyle=\frac{n(q-1)-r+k}{2}.$

Write $u=\sum_{i=0}^{{n}-1}u_{i}q^{i}$ with $u_{i}\in\\{0,1,\cdots,q-1\\}$,
and

$\displaystyle\widetilde{E}$
$\displaystyle=\left\\{(u_{0},u_{2},\cdots,u_{n-2})\mid
u_{i}\in[0,q-1],\sum_{0\leqslant i\leqslant{n}-1\atop
i\textup{~{}is~{}even}}u_{i}=\frac{n(q-1)-r-k}{2}\right\\},$
$\displaystyle\widetilde{O}$
$\displaystyle=\left\\{(u_{1},u_{3},\cdots,u_{n-1})\mid
u_{i}\in[0,q-1],\sum_{0\leqslant i\leqslant{n}-1\atop
i\textup{~{}is~{}odd}}u_{i}=\frac{n(q-1)-r+k}{2}\right\\}.$

It is not hard to check that $|\widetilde{E}|$ is the number of ways of
picking $\frac{n(q-1)-r-k}{2}$ objects from a set of $m$ objects, while no
object can be chosen more than $q-1$ times. By the principle of inclusion and
exclusion, we have

$|\widetilde{E}|=\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r-k}{2}-iq+m-1\choose\frac{n(q-1)-r-k}{2}-iq}.$

Similarly,

$|\widetilde{O}|=\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r+k}{2}-iq+m-1\choose\frac{n(q-1)-r+k}{2}-iq}.$

Hence,

$|S_{1}|=|\widetilde{E}||\widetilde{O}|=\left(\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r-k}{2}-iq+m-1\choose\frac{n(q-1)-r-k}{2}-iq}\right)\left(\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r+k}{2}-iq+m-1\choose\frac{n(q-1)-r+k}{2}-iq}\right).$

Then the claim follows directly. ∎

######  Definition 8.

[9, Theorem 1] [22, Chapter 13, Theorem 11] [23, Definition 5.14, Theorem
5.18] For $-1\leqslant r<{n}(q-1)$, define ${\mathcal{R}}_{q}(r,{n})^{*}$ to
be the length $q^{n}-1$ cyclic code with the zero set $Z_{r}$ where $Z_{r}$ is
as in Notation 6 (b). The extended code of ${\mathcal{R}}_{q}(r,{n})^{*}$ is
the _$r$ th-order generalized Reed–Muller_ code ${\mathcal{R}}_{q}(r,{n})$.
Note that ${\mathcal{R}}_{q}(-1,{n})=\\{0\\}$, and
${\mathcal{R}}_{q}({n},{n})=\mathbb{F}_{q}^{q^{n}}$ which is not an extended
cyclic code.

Kasami et al. [9] first determined the minimum distance of
${\mathcal{R}}_{q}(r,{n})^{*}$, then later Delsarte et al. [10] gave a
complete description of the minimum vectors. For a code ${\mathcal{C}}$ we
will use $\textup{dist}({\mathcal{C}})$ to denote its minimum distance.

######  Theorem 9.

[9, Theorem 5]For $0\leqslant r<{n}(q-1)$, write $r=\rho(q-1)+s$,
$0\leqslant\rho<n,0\leqslant s<q-1$. We have

$\displaystyle\textup{dist}({\mathcal{R}}_{q}(r,{n})^{*})$
$\displaystyle=(q-s)q^{{n}-\rho-1}-1,$
$\displaystyle\textup{dist}({\mathcal{R}}_{q}(r,{n}))$
$\displaystyle=(q-s)q^{{n}-\rho-1}.$

######  Theorem 10.

[10, Theorem 2.6.3][11, Theorem 3.18] For $0\leqslant r<{n}(q-1)$, write
$r=\rho(q-1)+s$, $0\leqslant\rho<n,0\leqslant s<q-1$. Assume that $s=0$. Then
the minimum vectors of the punctured code ${\mathcal{R}}_{q}(r,{n})^{*}$ are
the codewords of weight $\delta=q^{{n}-\rho}-1$, whose locators are the
nonzero elements of some subspace $V_{{n}-\rho}$ of $\mathbb{F}_{q^{n}}$ of
dimension ${n}-\rho$ over $\mathbb{F}_{q}$. These are in the algebra
$\mathcal{M}$ precisely the codewords

$x=\sum_{g\in V_{{n}-\rho}^{*}}\lambda(g)~{},~{}\lambda\in\mathbb{F}_{q}^{*},$

where $V_{{n}-\rho}^{*}=V_{{n}-\rho}\backslash\\{0\\}$. And the locator
polynomial of $x$ is

$\sigma_{x}(X)=1-\sum_{s\in\mathcal{I}_{n-\rho}}\frac{\Lambda_{\delta+s}}{\Lambda_{\delta}}X^{s},$

where ${\mathcal{I}}_{n-\rho}=\\{q^{n-\rho}-q^{j}\mid j\in[0,n-\rho-1]\\}.$

Similarly, the minimum vectors of the extended code ${\mathcal{R}}_{q}(r,{n})$
are the codewords of weight $q^{{n}-\rho}$ whose locators are the elements of
some affine subspace $h+V_{{n}-\rho},~{}h\in\mathbb{F}_{q^{n}}$, of
$\mathbb{F}_{q^{n}}$ of dimension ${n}-\rho$. These are in the algebra
$\mathcal{A}$ precisely the codewords

$x=\lambda\sum_{g\in V_{{n}-\rho}}(g+h),~{}\lambda\in\mathbb{F}_{q}^{*}.$

Now we define new classes of (extended) cyclic codes sandwiched between
generalized RM codes. For the binary case this was first introduced by Hu and
Nebe [16].

######  Definition 11.

Let $0\leqslant r<{n}(q-1)$ and $I\subset M_{r}$ be given. Put
$\overline{I}=M_{r}\setminus I$ and

$Z_{r,I}:=Z_{r-1}\bigg{\backslash}\bigg{(}\bigcup_{k\in
I}\Theta^{(r)}_{k}\bigg{)}=Z_{r}\bigcup\bigg{(}\bigcup_{k\in\overline{I}}\Theta^{(r)}_{k}\bigg{)}.$

Note that $Z_{r}\subseteq Z_{r,I}\subseteq Z_{r-1}$. Then, let
${\mathcal{C}}_{q}(r,I,{n})^{*}\subseteq\mathbb{F}_{q}^{q^{n}-1}$ be the
cyclic code with the zero set $Z_{r,I}$ and
${\mathcal{C}}_{q}(r,I,{n})\subseteq\mathbb{F}_{q}^{q^{n}}$ the extended code
of ${\mathcal{C}}_{q}(r,I,{n})^{*}$. Also we define

${\mathcal{C}}_{q}({n(q-1)},I,{n})=\begin{cases}{\mathcal{R}}_{q}({n(q-1)}-1,n)&\textup{if
}0\notin I,\\\
{\mathcal{R}}_{q}({n(q-1)},{n})=\mathbb{F}_{q}^{q^{n}}&\textup{otherwise.}\end{cases}$

######  Remark 12.

  * (a)

${\mathcal{R}}_{q}(r-1,{n})\subseteq{\mathcal{C}}_{q}(r,I,{n})\subseteq{\mathcal{R}}_{q}(r,{n})$.

  * (b)

${\mathcal{R}}_{q}(r-1,{n})={\mathcal{C}}_{q}(r,\emptyset,{n})$.

  * (c)

${\mathcal{R}}_{q}(r,{n})={\mathcal{C}}_{q}(r,M_{r},{n})$.

  * (d)

If $I\subseteq J\subseteq M_{r}$ then
${\mathcal{C}}_{q}(r,I,{n})\subseteq{\mathcal{C}}_{q}(r,J,{n})$.

Because of $(a)$ of Remark 12 we call those ${\mathcal{C}}_{q}(r,I,{n})$
_sandwiched Reed–Muller codes_. For a code $C$ we will use $\dim(C)$ to denote
its dimension.

######  Lemma 13.

[23, Theorem 5.5] For any $r$ such that $0\leqslant r\leqslant n(q-1)$,

$\dim({\mathcal{R}}_{q}(r,n))=\sum_{i=0}^{n}(-1)^{i}{n\choose i}{r-iq+n\choose
r-iq}.$

Here we give the dimension of our new codes by counting their zeros.

######  Theorem 14.

For any $r$ such that $0\leqslant r<n(q-1)$ and $I\subset M_{r}$,

$\displaystyle\dim({\mathcal{C}}_{q}(r,I,n))$
$\displaystyle=\sum_{i=0}^{n}(-1)^{i}{n\choose i}{n+r-iq\choose r-iq}$
$\displaystyle\ \ -2\sum_{k\in\overline{I}\atop k\neq
0}\left(\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r-k}{2}-iq+m-1\choose\frac{n(q-1)-r-k}{2}-iq}\right)\left(\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r+k}{2}-iq+m-1\choose\frac{n(q-1)-r+k}{2}-iq}\right)$
$\displaystyle\ \
-\mathbf{1}_{\overline{I}}(0)\left(\sum_{i=0}^{m}(-1)^{i}{m\choose
i}{\frac{n(q-1)-r}{2}-iq+m-1\choose\frac{n(q-1)-r}{2}-iq}\right)^{2},$

where $\mathbf{1}_{\overline{I}}(0)=1$ if $0\in\overline{I}$ and
$\mathbf{1}_{\overline{I}}(0)=0$ otherwise.

###### Proof.

For a cyclic code ${\mathcal{C}}$ of length $l$ we have
$\dim({\mathcal{C}})+|Z({\mathcal{C}})|=l$ where $Z({\mathcal{C}})$ is the
zero set of ${\mathcal{C}}$. So

$\dim({\mathcal{C}}_{q}(r,I,n)^{*})+|Z_{r}|+\sum_{k\in\overline{I}}\big{|}\Theta_{k}^{(r)}\big{|}=\dim({\mathcal{R}}_{q}(r,n)^{*})+|Z_{r}|=N.$

Then

$\dim({\mathcal{C}}_{q}(r,I,n))=\dim({\mathcal{C}}_{q}(r,I,n)^{*})=\dim({\mathcal{R}}_{q}(r,n))-\sum_{k\in\overline{I}}\big{|}\Theta_{k}^{(r)}\big{|},$

Now the result follows from Lemma 7 and Lemma 13. ∎

In the following we give an example of our new code.

######  Example 15.

Let $q=3,m=2,n=4,r=5$, $I=\\{1\\}\subseteq M_{5}=\\{1,3\\}$ and
$\overline{I}=\\{3\\}$. Let $\alpha$ be a primitive element of
$\mathbb{F}_{3^{4}}$. It’s not hard to compute that
$\Theta^{(5)}_{3}=\\{\alpha^{11},\alpha^{33},\alpha^{19},\alpha^{57}\\}$. The
zeros of ${\mathcal{R}}_{3}(4,4)^{*}$, ${\mathcal{R}}_{3}(5,4)^{*}$ and
${\mathcal{C}}_{3}(5,I,4)^{*}$ are

$\displaystyle Z_{4}$ $\displaystyle=\\{\alpha^{u}\ |\ 0<u\leqslant
80,\textup{wt}_{3}(u)\leqslant 3\\}$
$\displaystyle=\\{\alpha^{1},\alpha^{3},\alpha^{9},\alpha^{27},$
$\displaystyle\qquad\alpha^{2},\alpha^{6},\alpha^{18},\alpha^{54},\alpha^{4},\alpha^{12},\alpha^{36},\alpha^{28},\alpha^{10},\alpha^{30},$
$\displaystyle\qquad\alpha^{5},\alpha^{15},\alpha^{45},\alpha^{55},\alpha^{7},\alpha^{21},\alpha^{63},\alpha^{29},\alpha^{11},\alpha^{33},\alpha^{19},\alpha^{57},\alpha^{13},\alpha^{39},\alpha^{37},\alpha^{31}\\},$
$\displaystyle Z_{5}$ $\displaystyle=\\{\alpha^{u}\ |\ 0<u\leqslant
80,\textup{wt}_{3}(u)\leqslant 2\\}$
$\displaystyle=\\{\alpha^{1},\alpha^{3},\alpha^{9},\alpha^{27},$
$\displaystyle\qquad\alpha^{2},\alpha^{6},\alpha^{18},\alpha^{54},\alpha^{4},\alpha^{12},\alpha^{36},\alpha^{28},\alpha^{10},\alpha^{30}\\},$
$\displaystyle Z_{5}\cup\Theta^{(5)}_{3}$ $\displaystyle=\\{\alpha^{u}\ |\
0<u\leqslant 80,\textup{wt}_{3}(u)\leqslant 2\mbox{ and
}\textup{wt}_{3}(u)=3,|O(u)-E(u)|=3\\}$
$\displaystyle=\\{\alpha^{1},\alpha^{3},\alpha^{9},\alpha^{27},$
$\displaystyle\qquad\alpha^{2},\alpha^{6},\alpha^{18},\alpha^{54},\alpha^{4},\alpha^{12},\alpha^{36},\alpha^{28},\alpha^{10},\alpha^{30},$
$\displaystyle\qquad\alpha^{11},\alpha^{33},\alpha^{19},\alpha^{57}\\},$

respectively. Hence

${\mathcal{R}}_{3}(4,4)^{*}\subset{\mathcal{C}}_{3}(5,I,4)^{*}\subset{\mathcal{R}}_{3}(5,4)^{*}.$

By Lemma 13, we obtain

$\dim({\mathcal{R}}_{3}(4,4))=\sum_{i=0}^{4}(-1)^{i}{4\choose i}{8-3i\choose
4-3i}=50,$ $\dim({\mathcal{R}}_{3}(5,4))=\sum_{i=0}^{4}(-1)^{i}{4\choose
i}{9-3i\choose 5-3i}=66.$

By Lemma 7 we have

$|\Theta^{(5)}_{3}|=2\left(\sum_{i=0}^{2}(-1)^{i}{2\choose i}{0-3i+1\choose
0-3i}\right)\left(\sum_{j=0}^{2}(-1)^{j}{2\choose j}{3-3j+1\choose
3-3j}\right)=4.$

Hence

$\dim({\mathcal{C}}_{3}(5,I,4))=\dim({\mathcal{R}}_{3}(5,4))-|\Theta^{(5)}_{3}|=62.$

######  Theorem 16.

For any $0\leqslant r<{n}(q-1)$ and $I\subset M_{r}$, the code
${{\mathcal{C}}_{q}}(r,I,{n})$ is affine-invariant.

###### Proof.

Let $Z_{r,I}$ be the zero set of ${{\mathcal{C}}_{q}}(r,I,{n})^{*}$, and
$T_{r,I}$ the defining set of $C_{q}(r,I,n)$, where

$T_{r,I}=\\{i\mid 1\leqslant i\leqslant q^{n}-1,\alpha^{i}\in
Z_{r,I}\\}\cup\\{0\\}.$

For any $t\in T_{r,I}$ and $s\in[0,q^{n}-1]$, if $s\preceq t$ then we have
$s=t$ or $\textup{wt}_{q}(s)<\textup{wt}_{q}(t)$, which shows that $s\in
T_{r,I}$ according to the definition of $Z_{r,I}$. Hence
$\Delta(T_{r,I})=T_{r,I}$. Now by Lemma 5, the code $C_{q}(r,I,n)$ is affine-
invariant. ∎

##  IV Some properties of sandwiched Reed–Muller codes

Now we investigate the dual codes and the minimum distances of our new
sandwiched Reed–Muller codes.

###  IV-A Dual codes

The dual codes of generalized RM codes first appeared in unpublished notes of
S. Lin, then was given in [10, Theorem 2.2.1],

${\mathcal{R}}_{q}(r,{n})^{\perp}={\mathcal{R}}_{q}(n(q-1)-r-1,{n}),\
0\leqslant r<n(q-1).$

Here we prove the following result on the dual of sandwiched RM codes.

######  Theorem 17.

For $0\leqslant r<n(q-1)$, $I\subseteq M_{r}$ and
$\overline{I}:=M_{r}\setminus I$, we have

${\mathcal{C}}_{q}(r,I,n)^{\perp}={\mathcal{C}}_{q}(n(q-1)-r,\overline{I},n).$

###### Proof.

Recall that the zero set of ${\mathcal{C}}_{q}(r,I,n)^{*}$ is $Z_{r,I}$. It is
well-known that (c.f. [11, Definition 2.7]) the dual code of
${\mathcal{C}}_{q}(r,I,n)$ is also an extended cyclic code. More precisely,
${\mathcal{C}}_{q}(r,I,n)^{\perp}$ is the extended code of the cyclic code
whose zeros are

$\big{\\{}\beta^{-1}\ |\
\beta\in\mathbb{F}_{q^{n}}^{*}\setminus(Z_{r,I}\cup\\{\alpha^{0}\\})\big{\\}},$

and by Equation (4) it is not hard to check that this zero set is equal to
$Z_{n(q-1)-r,\overline{I}}$. This concludes our proof. ∎

###  IV-B Minimum distances

Now we show the following lower bounds on the minimum distances of sandwiched
RM codes.

######  Theorem 18.

For $0\leqslant r\leqslant{n}(q-1)-2$, write $r=\rho(q-1)+s$, where
$0\leqslant\rho\leqslant n-1,0\leqslant s<q-1$. Suppose $I\subseteq M_{r+1}$.

  1. 1.

If $\rho=n-1$ and $\\{q-1-s-1\\}\cap I=\emptyset$, then
$\textup{dist}({\mathcal{C}}_{q}(r+1,I,{n}))=q-s$.

  2. 2.

For $0\leqslant\rho\leqslant n-2$, we have111We use $\\{q-1-s\pm 1\\}$ to
denote $\\{q-1-s+1,q-1-s-1\\}$ for convenience.

$\textup{dist}({\mathcal{C}}_{q}(r+1,I,{n}))\begin{cases}=(q-s)q^{{n}-\rho-1}&\textup{if~{}}\rho\textup{\
is\ odd\ and\ }\\{q-1-s\pm 1\\}\cap I=\emptyset,\textup{\ or}\\\
&\quad\textup{if~{}}\rho\textup{\ is\ even\ and\ }\\{|s\pm 1|\\}\cap
I=\emptyset\\\ \geqslant(q^{2}-qs-1)q^{{n}-\rho-2}&\textup{if }\rho\textup{\
is\ odd\ and\ }\\{q-1-s\pm 1\\}\cap I=\\{q-1-s+1\\},\textup{\ or}\\\
&\quad\textup{if~{}}\rho\textup{\ is\ even,\ }s\neq 0\textup{ and }\\{|s\pm
1|\\}\cap I=\\{|s-1|\\}.\end{cases}$

###### Proof.

By (a) of Remark 12 and Theorem 9,

$\textup{dist}({\mathcal{R}}_{q}(r+1,{n}))\leqslant\textup{dist}({\mathcal{C}}_{q}(r+1,I,{n}))\leqslant\textup{dist}({\mathcal{R}}_{q}(r,{n}))=(q-s)q^{{n}-\rho-1}.$

We first review the minimum distance of ${\mathcal{R}}_{q}(r,{n})$. Consider
the set

$Z=\\{\alpha^{u}\ |\ 0<u<(q-s)q^{{n}-\rho-1}-1\\}.$

Note that

$\displaystyle(q-s)q^{{n}-\rho-1}-1=\begin{cases}q-s-1&\textup{if }\rho=n-1\\\
(q-s-1)q^{n-\rho-1}+\sum_{i=0}^{n-\rho-2}(q-1)q^{i}&\textup{if
}0\leqslant\rho\leqslant n-2\end{cases}$

which implies that for $0<u<(q-s)q^{{n}-\rho-1}-1$, we have
$0<\textup{wt}_{q}(u)\leqslant{n}(q-1)-r-1$. So $Z$ is a subset of $Z_{r}$,
the zero set of ${\mathcal{R}}_{q}(r,{n})^{*}$. Then the BCH bound gives

$\textup{dist}({\mathcal{R}}_{q}(r,{n})^{*})\geqslant(q-s)q^{{n}-\rho-1}-1.$

As ${\mathcal{R}}_{q}(r,{n})$ is affine invariant, we have by translation
invariance (c.f. [23, Corollary 5.26])

$\textup{dist}({\mathcal{R}}_{q}(r,{n}))\geqslant(q-s)q^{{n}-\rho-1}.$

Recall that the zero set of ${\mathcal{C}}_{q}(r+1,I,{n})^{*}$ is

$Z_{r+1,I}=Z_{r}\bigg{\backslash}\bigg{(}\bigcup_{k\in
I}\Theta^{(r+1)}_{k}\bigg{)}.$

Suppose that $0<u<(q-s)q^{{n}-\rho-1}-1$ and
$\textup{wt}_{q}(u)={n}(q-1)-r-1$. It is not hard to verify that there exists
some $j,0\leqslant j\leqslant n-\rho-1$ such that

$\displaystyle u=(q-s)q^{{n}-\rho-1}-1-q^{j}=\begin{cases}q-s-1-1&\textup{if
}\rho=n-1\\\
(q-s-1)q^{n-\rho-1}-q^{j}+\sum_{i=0}^{n-\rho-2}(q-1)q^{i}&\textup{if
}0\leqslant\rho\leqslant n-2.\end{cases}$

Case (i): If $\rho$ is odd, then

$E(u)-O(u)=\begin{cases}q-s-1-1&\textup{if }\rho=n-1\\\ q-s-1\pm 1&\textup{if
}\rho\leqslant n-3.\end{cases}$

So if $\rho=n-1$ and $\\{q-1-s-1\\}\cap I=\emptyset$ then $Z\subseteq
Z_{r+1,I}$. Also for $0\leqslant\rho\leqslant n-3$, if $\\{q-s-1\pm 1\\}\cap
I=\emptyset$, then $Z\subseteq Z_{r+1,I}$. Using a similar argument as above,
we can conclude that
$\textup{dist}({\mathcal{C}}_{q}(r+1,I,{n}))=\textup{dist}({\mathcal{R}}_{q}(r,{n}))$.
On the other hand, we can verify that the minimal $u$ such that
$E(u)-O(u)=q-s-1+1$ is

$u=\sum_{i=0}^{n-\rho-3}(q-1)q^{i}+(q-2)q^{{n}-\rho-2}+(q-s-1)q^{{n}-\rho-1}=(q^{2}-qs-1)q^{{n}-\rho-2}-1,$

where $0\leqslant\rho\leqslant n-3$. Therefore, if $\\{q-s-1\pm 1\\}\cap
I=\\{q-s-1+1\\}$ then

$\displaystyle\textup{dist}({\mathcal{C}}_{q}(r+1,I,{n})^{*})$
$\displaystyle\geqslant(q^{2}-qs-1)q^{{n}-\rho-2}-1.$

As ${\mathcal{C}}_{q}(r+1,I,{n})$ is also affine invariant, we have by
translation invariance

$\textup{dist}({\mathcal{C}}_{q}(r+1,I,{n}))\geqslant(q^{2}-qs-1)q^{{n}-\rho-2}.$

Case (ii): If $\rho$ is even, then $\rho\leqslant n-2$ and $E(u)-O(u)=s\pm 1$.
Similarly, if $\\{|s\pm 1|\\}\cap I=\emptyset$, we have $Z\subseteq Z_{r+1,I}$
and
$\textup{dist}({\mathcal{C}}_{q}(r+1,I,{n}))=\textup{dist}({\mathcal{R}}_{q}(r,{n}))$.
Note that the minimal $u$ such that $E(u)-O(u)=s-1$ is also
$(q^{2}-qs-1)q^{n-\rho-2}-1.$ Therefore, if $s\neq 0$ and $\\{|s\pm 1|\\}\cap
I=\\{|s-1|\\}$, then similarly as above we have

$\displaystyle\textup{dist}({\mathcal{C}}_{q}(r+1,I,n)^{*})$
$\displaystyle\geqslant(q^{2}-qs-1)q^{n-\rho-2}-1,$
$\displaystyle\textup{dist}({\mathcal{C}}_{q}(r+1,I,n))$
$\displaystyle\geqslant(q^{2}-qs-1)q^{n-\rho-2}.$

∎

######  Example 19.

Let $q=3,m=2$ and $n=4$. For $0\leqslant r\leqslant 6$ and $I\subseteq
M_{r+1}$, we use $[N,K,D]$ to denote the length, dimension and minimum
distance of the code $\mathcal{C}_{3}(r+1,I,4)$. With the aid of Magma
program, we list the parameters of these codes in Tables I-II.

TABLE I: The parameters of $\mathcal{C}_{3}(r+1,I,4)$ with even $r$ $I$ $r$ $[N,K,D]$ | 0 | 2 | 4 | 6
---|---|---|---|---
{1} | [81,5,54] | [81,27,18] | [81,62,6] | [81,80,2]
{3} | [81,1,81] | [81,19,27] | [81,54,9] | [81,76,3]
{1,3} | [81,5,54] | [81,31,18] | [81,66,6] | [81,80,2]
TABLE II: The parameters of $\mathcal{C}_{3}(r+1,I,4)$ with odd $r$ $I$ $r$ $[N,K,D]$ | 1 | 3 | 5
---|---|---|---
{0} | [81,9,45] | [81,40,9] | [81,70,5]
{2} | [81,11,36] | [81,39,16] | [81,72,4]
{4} | [81,5,54] | [81,33,18] | [81,66,6]
{0,2} | [81,15,27] | [81,48,9] | [81,76,3]
{0,4} | [81,9,45] | [81,42,9] | [81,70,5]
{2,4} | [81,11,36] | [81,41,16] | [81,72,4]
{0,2,4} | [81,15,27] | [81,50,9] | [81,76,3]

##  V Minimum vectors of sandwiched Reed–Muller codes

In this section, we determine the minimum vectors of
${\mathcal{C}}_{q}(r,I,n)$ for some special cases. We split our discussion
into two subsections as follows.

###  V-A Case (i): $r=\rho(q-1)+1,0\leqslant\rho\leqslant n-1$.

Throughout this subsection, we assume that
$r=\rho(q-1)+1,0\leqslant\rho\leqslant n-1$ and

$\begin{cases}\\{q,q-2,|q-4|\\}\cap I=\emptyset&\textup{if $\rho$ is odd},\\\
\\{1,3\\}\cap I=\emptyset&\textup{if $\rho$ is even}.\end{cases}$

(Note that this assumption is slightly stronger than that of Theorem 18.) By
Theorem 18, we have

$\textup{dist}({\mathcal{C}}_{q}(r,I,n))=\textup{dist}({\mathcal{R}}_{q}(r-1,n))=q^{n-\rho}.$

By (a) of Remark 12, the minimum vectors of ${\mathcal{R}}_{q}(r-1,n)$ are
also minimum vectors of ${\mathcal{C}}_{q}(r,I,n)$. Furthermore, we now show
that these are exactly the minimum vectors of ${\mathcal{C}}_{q}(r,I,n)$.

######  Proposition 20.

Let $r=\rho(q-1)+1,0\leqslant\rho\leqslant n-1$ and assume that

$\begin{cases}\\{q,q-2,|q-4|\\}\cap I=\emptyset&\textup{if $\rho$ is odd},\\\
\\{1,3\\}\cap I=\emptyset&\textup{if $\rho$ is even}.\end{cases}$

Let ${\mathcal{C}}_{q}={\mathcal{C}}_{q}(r,I,n)^{*}$ with length $N=q^{n}-1$.
Let $\delta=q^{n-\rho}-1$, let ${\mathcal{I}}_{n-\rho}=\\{q^{n-\rho}-q^{j}\mid
j\in[0,n-\rho-1]\\}$ and let ${\mathcal{S}}_{{\mathcal{C}}_{q}}(\delta)$ be
the newton identities system (2), written for the codewords of weight $\delta$
of ${\mathcal{C}}_{q}$. Then, any solution
$(\Lambda_{1},\cdots,\Lambda_{N},\sigma_{1},\cdots,\sigma_{\delta})$ of
${\mathcal{S}}_{{\mathcal{C}}_{q}}(\delta)$ satisfies the following:

  * (i)

$\Lambda_{1}=\Lambda_{2}=\cdots=\Lambda_{\delta-1}=0.$

  * (ii)

Let $u\in[1,\delta-1]$.

    * (a)

If $u\notin{\mathcal{I}}_{n-\rho}$, then $\Lambda_{\delta+u}=0$ and
$\sigma_{u}=0$.

    * (b)

If $u\in{\mathcal{I}}_{n-\rho}$, then
$\sigma_{u}=-\Lambda_{\delta+u}/\Lambda_{\delta}$.

  * (iii)

$\sigma(X)=1-\sum_{u\in{\mathcal{I}}_{n-\rho}}\frac{\Lambda_{\delta+u}}{\Lambda_{\delta}}X^{u}.$

###### Proof.

(i) Recall that the zero set of ${\mathcal{C}}_{q}(r,I,n)^{*}$ is

$\displaystyle
Z_{r,I}=Z_{r}\bigcup\bigg{(}\bigcup_{k\in\overline{I}}\Theta^{(r)}_{k}\bigg{)}.$

Note that $\delta=q^{n-\rho}-1=\sum_{i=0}^{n-\rho-1}(q-1)q^{i}$, so
$\textup{wt}_{q}(\delta)=n(q-1)-r+1$, and for any $1\leqslant
u\leqslant\delta-1$ we have $\textup{wt}_{q}(u)\leqslant n(q-1)-r$. If
$\textup{wt}_{q}(u)<n(q-1)-r$, then $\Lambda_{u}=0$ by definition. If
$\textup{wt}_{q}(u)=n(q-1)-r$, then it is not hard to check that

$|O(u)-E(u)|=\begin{cases}q-1\pm 1&\textup{if $\rho$ is odd},\\\ 1&\textup{if
$\rho$ is even},\end{cases}$

whence $\alpha^{u}\in Z_{r,I}$ and $\Lambda_{u}=0$. Hence for any $1\leqslant
u\leqslant\delta-1$ we always have $\Lambda_{u}=0$, which proves (i).

(ii) Set $t=\delta+u$ where $u\in[1,\delta-1]$. Then we can write

$\displaystyle t=\sum_{i=0}^{n-\rho-1}t_{i}q^{i}+q^{n-\rho},\
t_{i}\in[0,q-1].$ (5)

First we can easily check that $\textup{wt}_{q}(t)\leqslant(n-\rho)(q-1)$ for
any $\delta<t<2\delta$.

Assume that

$\textup{wt}_{q}(t)=(n-\rho)(q-1)=n(q-1)-r+1.$

Then by (5) and $\delta<t<2\delta$ there is only one $t_{j},1\leqslant
j\leqslant n-\rho-1$, equal to $q-2$, i.e. $t=\delta+q^{n-\rho}-q^{j}$, with
$j\in[1,n-\rho-1]$. Hence $u=q^{n-\rho}-q^{j}\in{\mathcal{I}}_{n-\rho}$. Next
assume that

$\textup{wt}_{q}(t)=(n-\rho)(q-1)-1=n(q-1)-r.$

By (5) there exist two cases, one of which is $t_{j},t_{k},j\neq
k,j,k\in[0,n-\rho-1]$, are equal to $q-2$, another is
$t_{l},l\in[0,n-\rho-1]$, is equal to $q-3$ (when $q\geqslant 3$). In either
case, it is not hard to verify that

$|O(t)-E(t)|=\begin{cases}q,~{}q-2\mbox{ or }|q-4|&\textup{if $\rho$ is
odd},\\\ 1\mbox{ or }3&\textup{if $\rho$ is even}.\end{cases}$

Therefore $\alpha^{t}\in Z_{r,I}$. If $\textup{wt}_{q}(\delta+u)\leqslant
n(q-1)-r-1$, then $\alpha^{t}\in Z_{r,I}$. Combining the above arguments, we
conclude that if $u\notin{\mathcal{I}}_{n-\rho}$, then $\alpha^{\delta+u}\in
Z_{r,I}$. Hence $\Lambda_{\delta+u}=0$.

Now we write the first $2\delta-1$ Newton identities, taking into account the
condition $\\{\Lambda_{i}=0,i\in[0,\delta-1]\\}$.

$\displaystyle I_{1}$
$\displaystyle:\Lambda_{\delta+1}+\Lambda_{\delta}\sigma_{1}=0$ $\displaystyle
I_{2}$
$\displaystyle:\Lambda_{\delta+2}+\Lambda_{\delta+1}\sigma_{1}+\Lambda_{\delta}\sigma_{2}=0$
$\displaystyle\cdots$ $\displaystyle I_{u}$
$\displaystyle:\Lambda_{\delta+u}+\sum_{i=1}^{u}\Lambda_{\delta+u-i}\sigma_{i}=0$
$\displaystyle\cdots$ $\displaystyle I_{2\delta-1}$
$\displaystyle:\Lambda_{2\delta-1}+\Lambda_{2\delta-2}\sigma_{1}+\cdots+\Lambda_{\delta}\sigma_{\delta-1}=0.$

We now proceed by induction on $u$. Since $1\notin{\mathcal{I}}_{n-\rho}$,
then $\Lambda_{\delta+1}=0$ and $I_{1}$ gives $\sigma_{1}=0$ (since
$\Lambda_{\delta}\neq 0$). Now we assume that for $s\in[1,u-1]$, if
$s\notin{\mathcal{I}}_{n-\rho}$ then $\sigma_{s}=0$ else
$\sigma_{s}=-\Lambda_{\delta+s}/\Lambda_{\delta}$. Consider every term
$\Lambda_{\delta+u-s}\sigma_{s},s<u$, of the identity $I_{u}$. By the
assumption we obtain

  1. 1.

If $s\notin{\mathcal{I}}_{n-\rho}$ then $\sigma_{s}=0$.

  2. 2.

If $s\in{\mathcal{I}}_{n-\rho}$ then $s=q^{n-\rho}-q^{j}$, where
$j\in[0,n-\rho-1]$. As $s<u<q^{n-\rho}-1$,

$u-s<q^{n-\rho}-1-q^{n-\rho}+q^{j}=q^{j}-1<(q-1)q^{n-\rho-1}.$

Hence, $u-s\notin{\mathcal{I}}_{n-\rho}$ implies $\Lambda_{\delta+u-s}=0$.

So the identity $I_{u}$ is in fact
$\Lambda_{\delta+u}+\Lambda_{\delta}\sigma_{u}=0$. If
$u\notin{\mathcal{I}}_{n-\rho}$ then $\Lambda_{\delta+u}=0$ and
$\sigma_{u}=0$, otherwise $\sigma_{u}=-\Lambda_{\delta+u}/\Lambda_{\delta}$,
which proves (ii).

(iii) This follows directly from (ii). ∎

Now we are ready to show that the minimum vectors of
${\mathcal{C}}_{q}(r,I,n)^{*}$ are exactly those of
${\mathcal{R}}_{q}(r-1,n)^{*}$.

######  Theorem 21.

Let $r=\rho(q-1)+1,\ 0\leqslant\rho\leqslant n-1$ and assume that

$\begin{cases}\\{q,q-2,|q-4|\\}\cap I=\emptyset&\textup{if $\rho$ is odd},\\\
\\{1,3\\}\cap I=\emptyset&\textup{if $\rho$ is even}.\end{cases}$

Then the minimum vectors of ${\mathcal{C}}_{q}(r,I,n)^{*}$ are the codewords

$x=\sum_{g\in V_{n-\rho}^{*}}\lambda(g),~{}\lambda\in\mathbb{F}_{q}^{*}$

where $V_{n-\rho}$ is any subspace of $\mathbb{F}_{q^{n}}$ of dimension
$n-\rho$ over $\mathbb{F}_{q}$ and
$V_{n-\rho}^{*}=V_{n-\rho}\backslash\\{0\\}$.

###### Proof.

Suppose that $x$ is a codeword of weight $\delta=q^{n-\rho}-1$ of
${\mathcal{C}}_{q}(r,I,n)^{*}$. By Proposition 20 we know that its locator
polynomial is

$\sigma(X)=1-\sum_{u\in{\mathcal{I}}_{n-\rho}}\frac{\Lambda_{\delta+u}}{\Lambda_{\delta}}X^{u}.$

Then from Proposition 3, the roots of $\sigma(X)$ are the nonzero elements of
some subspace $V_{n-\rho}$ of $\mathbb{F}_{q^{n}}$ of dimension $n-\rho$.
Therefore

$x=\sum_{g\in
V_{n-\rho}^{*}}\lambda_{g}(g),~{}\lambda_{g}\in\mathbb{F}_{q}^{*}.$

On the other hand, from Theorem 10 we know that the codeword $\sum_{g\in
V_{n-\rho}^{*}}(g)\in{\mathcal{R}}_{q}(r-1,n)^{*}$, so it is also a minimum
vector of ${\mathcal{C}}_{q}(r,I,n)^{*}$. This implies that
$\lambda_{g}=\lambda$ for some $\lambda\in\mathbb{F}_{q}^{*}$ and all $g\in
V_{n-\rho}^{*}$, otherwise this would contradict to the minimum distance of
${\mathcal{C}}_{q}(r,I,n)^{*}$. So

$x=\sum_{g\in V_{n-\rho}^{*}}\lambda(g),~{}\lambda\in\mathbb{F}_{q}^{*}.$

This concludes the proof. ∎

######  Theorem 22.

Let $r=\rho(q-1)+1,\ 0\leqslant\rho\leqslant n-1$ and assume that

$\begin{cases}\\{q,q-2,|q-4|\\}\cap I=\emptyset&\textup{if $\rho$ is odd},\\\
\\{1,3\\}\cap I=\emptyset&\textup{if $\rho$ is even}.\end{cases}$

Then the minimum vectors of ${{\mathcal{C}}_{q}}(r,I,n)$ in the algebra
$\mathcal{A}$ are precisely the codewords

$x=\lambda\sum_{g\in V_{n-\rho}}(g+h),~{}\lambda\in\mathbb{F}_{q}^{*}$

where $V_{n-\rho}$ is any subspace of $\mathbb{F}_{q^{n}}$ of dimension
$n-\rho$ over $\mathbb{F}_{q}$ and $h\in\mathbb{F}_{q^{n}}$.

###### Proof.

Note that ${{\mathcal{C}}_{q}}(r,I,n)$ is affine-invariant by Theorem 16.
Combining this with Theorem 21 we obtain the result. ∎

###  V-B Case (ii): $r=\rho(q-1)$, $\rho$ is even and $\\{0,2\\}\cap
I=\\{0\\}$

In this subsection we assume that $\rho=2\rho^{\prime}$ is even, so,
$r=\rho(q-1)$ is even.

######  Lemma 23.

Let $n=2m,\ r=\rho(q-1),\ 0\leqslant\rho\leqslant n-1$, $\rho=2\rho^{\prime}$
and $0\in I$. Let $V_{m-\rho^{\prime}}^{(2)}$ be a subspace of
$\mathbb{F}_{q^{n}}$ with dimension $m-\rho^{\prime}$ over
$\mathbb{F}_{q^{2}}$. Let $x=\sum_{g\in
V_{m-\rho^{\prime}}^{(2)}\backslash\\{0\\}}\lambda(g),\lambda\in\mathbb{F}_{q}^{*}$,
then $x\in{\mathcal{C}}_{q}(r,I,n)^{*}$.

###### Proof.

By definition we know that the zero set of ${\mathcal{C}}_{q}(r,I,n)^{*}$ is

$\displaystyle
Z_{r,I}=Z_{r}\bigcup\bigg{(}\bigcup_{k\in\overline{I}}\Theta^{(r)}_{k}\bigg{)}.$

Now we will prove that $\Lambda_{u}=0$ for all $\alpha^{u}\in Z_{r,I}$, which
implies that $x\in{\mathcal{C}}_{q}(r,I,n)^{*}$.

Let $\alpha^{u}\in Z_{r,I}$. If $\textup{wt}_{q}(u)\leqslant
n(q-1)-r-1=(n-\rho)(q-1)-1$, then by Theorem 4 and $V_{m-\rho^{\prime}}^{(2)}$
is naturally a subspace of dimension $n-\rho$ over $\mathbb{F}_{q}$, we have
$\Lambda_{u}=\sum_{g\in V_{m-\rho^{\prime}}^{(2)}\backslash\\{0\\}}g^{u}=0$.
Now assume that $\textup{wt}_{q}(u)=n(q-1)-r=(n-\rho)(q-1)$ and $O(u)\neq
E(u)$. Note that

$\textup{wt}_{q^{2}}(u)=E(u)+qO(u)=\textup{wt}_{q}(u)+(q-1)O(u).$

If $E(u)>(m-\rho^{\prime})(q-1)>O(u)$, we can readily check that
$\textup{wt}_{q^{2}}(u)<(m-\rho^{\prime})(q^{2}-1)$, then by Theorem 4 we have
$\Lambda_{u}=0$. If $E(u)<(m-\rho^{\prime})(q-1)<O(u)$, then similarly we have
$\textup{wt}_{q^{2}}(qu)<(m-\rho^{\prime})(q^{2}-1)$ and
$\Lambda_{qu}=\Lambda_{u}^{q}=0$, so $\Lambda_{u}=0$. This concludes our
proof. ∎

######  Lemma 24.

Let $n=2m,\ r=\rho(q-1),\ 0\leqslant\rho\leqslant n-1$, $\rho=2\rho^{\prime}$
and $\\{0,2\\}\cap I=\\{0\\}$. Let $V_{n-\rho}$ be a subspace of
$\mathbb{F}_{q^{n}}$ of dimension $n-\rho$ over $\mathbb{F}_{q}$ but not a
subspace of dimension $m-\rho^{\prime}$ over $\mathbb{F}_{q^{2}}$. Let
$x=\sum_{g\in V_{n-\rho}^{*}}\lambda(g)$, $\lambda\in\mathbb{F}_{q}^{*}$, then
$x\notin{\mathcal{C}}_{q}(r,I,n)^{*}$.

###### Proof.

Consider the polynomial

$f(X)=X^{q^{n-\rho}}\sigma(X^{-1})=X^{q^{n-\rho}}+\sum_{j=0}^{n-\rho-1}\gamma_{j}X^{q^{j}}$

where $\sigma(X)$ is the locator polynomial of $x$. As $V_{n-\rho}$ is not a
subspace of dimension $m-\rho^{\prime}$ over $\mathbb{F}_{q^{2}}$, there must
exist some odd $j\in\\{1,3,5,\cdots,n-\rho-1\\}$ such that $\gamma_{j}\neq 0$.
On the other hand, note that $\sigma_{q^{n-\rho}-q^{j}}=\gamma_{j}\neq 0$.

Now by Theorem 10, we get
$\sigma_{q^{n-\rho}-q^{j}}=-\Lambda_{\delta+q^{n-\rho}-q^{j}}/\Lambda_{\delta}\neq
0$. As $\Lambda_{\delta}\neq 0$, we have
$\Lambda_{\delta+q^{n-\rho}-q^{j}}\neq 0$, where $\delta=q^{n-\rho}-1$. We can
readily check that $\textup{wt}_{q}(\delta+q^{n-\rho}-q^{j})=(n-\rho)(q-1)$,
and $|O(\delta+q^{n-\rho}-q^{j})-E(\delta+q^{n-\rho}-q^{j})|=2$. As $2\notin
I$, we have $\delta+q^{n-\rho}-q^{j}\in Z_{r,I}$ and
$\Lambda_{\delta+q^{n-\rho}-q^{j}}=0$, which is a contradiction. Therefore
$x\notin{\mathcal{C}}_{q}(r,I,n)^{*}$. ∎

######  Theorem 25.

Let $n=2m,\ r=\rho(q-1),\ 0\leqslant\rho\leqslant n-1$, $\rho=2\rho^{\prime}$
and $\\{0,2\\}\cap I=\\{0\\}$, the minimum vectors of
${{\mathcal{C}}_{q}}(r,I,n)^{*}$ are the codewords

$x=\sum_{g\in
V_{m-\rho^{\prime}}^{(2)}\backslash\\{0\\}}\lambda(g),~{}\lambda\in\mathbb{F}_{q}^{*}$

where $V_{m-\rho^{\prime}}^{(2)}$ is any subspace of $\mathbb{F}_{q^{n}}$ of
dimension $m-\rho^{\prime}$ over $\mathbb{F}_{q^{2}}$.

###### Proof.

By Theorem 18 and Lemma 23 we have

$\textup{dist}({{\mathcal{C}}_{q}}(r,I,n)^{*})=\textup{dist}({\mathcal{R}}_{q}(r,n)^{*})=q^{2(m-\rho^{\prime})}-1.$

So the minimum vectors of ${{\mathcal{C}}_{q}}(r,I,n)^{*}$ are that of
${\mathcal{R}}_{q}(r,n)^{*}$. Now by Lemma 24, we can get that the minimum
vectors of ${{\mathcal{C}}_{q}}(r,I,n)^{*}$ are the codewords

$x=\sum_{g\in
V_{m-\rho^{\prime}}^{(2)}\backslash\\{0\\}}\lambda(g),~{}\lambda\in\mathbb{F}_{q}^{*}$

where $V_{m-\rho^{\prime}}^{(2)}$ is any subspace of $\mathbb{F}_{q^{n}}$ of
dimension $m-\rho^{\prime}$ over $\mathbb{F}_{q^{2}}$. This implies the
result. ∎

######  Theorem 26.

Let $n=2m,\ r=\rho(q-1),\ 0\leqslant\rho\leqslant n-1$, $\rho=2\rho^{\prime}$
and $\\{0,2\\}\cap I=\\{0\\}$. The minimum vectors of
${{\mathcal{C}}_{q}}(r,I,n)$ in the algebra $\mathcal{A}$ are precisely the
codewords

$x=\lambda\sum_{g\in
V_{m-\rho^{\prime}}^{(2)}}(g+h),~{}h\in\mathbb{F}_{q^{n}},~{}\lambda\in\mathbb{F}_{q}^{*}$

where $V_{m-\rho^{\prime}}^{(2)}$ is any subspace of $\mathbb{F}_{q^{n}}$ of
dimension $m-\rho^{\prime}$ over $\mathbb{F}_{q^{2}}$.

###### Proof.

We know that ${{\mathcal{C}}_{q}}(r,I,n)$ is affine-invariant by Theorem 16.
Combining this with Theorem 25 we obtain the result. ∎

##  VI Concluding remarks

In this paper we propose new families of extended cyclic codes sandwiched
between generalized RM codes, and explicitly determine their minimum vectors
for some special cases. Kudekar et al. [24] proved that RM codes achieve
capacity on the BEC both under bit-MAP and block-MAP decoding, thus solving a
long standing conjecture. Very recently, Reeves and Pfister [25] prove that
the family of binary RM codes achieves capacity on any BMS channel with
respect to bit-error rate. As our codes are sandwiched between RM codes, it
just follows directly that same results also hold for our new codes, i.e.,
achieve capacity on the BEC both under bit-MAP and block-MAP decoding, and
achieve capacity on any BMS channel with respect to bit-error rate. One
intriguing problem is to find an $n$-variable polynomial representation for
our new sandwiched RM codes. This will help us determine the minimum vectors
of those universally strongly perfect lattices of [16].

## References

  * [1] D. E. Muller, “Application of boolean algebra to switching circuit design and to error detection,” _Transactions of the IRE Professional Group on Electronic Computers_ , no. 3, pp. 6–12, 1954.
  * [2] I. Reed, “A class of multiple-error-correcting codes and the decoding scheme,” _Transactions of the IRE Professional Group on Information Theory_ , vol. 4, no. 4, pp. 38–49, 1954.
  * [3] E. Abbe and M. Ye, “Reed-Muller codes polarize,” _IEEE Transactions on Information Theory_ , vol. 66, no. 12, pp. 7311–7332, 2020.
  * [4] S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoǧlu, and R. L. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4298–4316, 2017.
  * [5] J. L. Massey, “Deep-space communications and coding: A marriage made in heaven,” in _Advanced Methods for Satellite and Deep Space Communications_. Springer, 1992, pp. 1–17.
  * [6] E. Arikan, “A survey of Reed-Muller codes from polar coding perspective,” in _2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo)_. IEEE, 2010, pp. 1–5.
  * [7] E. Abbe, A. Shpilka, and A. Wigderson, “Reed-Muller codes for random erasures and errors,” _IEEE Transactions on Information Theory_ , vol. 61, no. 10, pp. 5229–5252, 2015.
  * [8] E. Abbe, A. Shpilka, and M. Ye, “Reed–Muller codes: Theory and algorithms,” _IEEE Transactions on Information Theory_ , vol. 67, no. 6, pp. 3251–3277, 2020.
  * [9] T. Kasami, S. Lin, and W. Peterson, “New generalizations of the Reed-Muller codes–i: Primitive codes,” _IEEE Transactions on Information Theory_ , vol. 14, no. 2, pp. 189–199, 1968.
  * [10] P. Delsarte, J.-M. Goethals, and F. J. MacWilliams, “On generalized Reed-Muller codes and their relatives,” _Information and Control_ , vol. 16, no. 5, pp. 403–442, 1970.
  * [11] P. Charpin, “Open problems on cyclic codes,” _Handbook of coding theory_ , vol. 1, pp. 963–1063, 1998.
  * [12] E. Leducq, “A new proof of Delsarte, Goethals and MacWilliams theorem on minimal weight codewords of generalized Reed–Muller codes,” _Finite Fields and Their Applications_ , vol. 18, no. 3, pp. 581–586, 2012\.
  * [13] E. Barnes and G. Wall, “Some extreme forms defined in terms of abelian groups,” _Journal of the Australian Mathematical Society_ , vol. 1, no. 1, pp. 47–63, 1959.
  * [14] M. Broué and M. Enguehard, “Une famille infinie de formes quadratiques entières; leurs groupes d’automorphismes,” in _Annales scientifiques de l’École Normale Supérieure_ , vol. 6, no. 1, 1973, pp. 17–51.
  * [15] J. H. Conway and N. J. A. Sloane, _Sphere packings, lattices and groups_. Springer Science & Business Media, 2013, vol. 290.
  * [16] S. Hu and G. Nebe, “Strongly perfect lattices sandwiched between Barnes–Wall lattices,” _Journal of the London Mathematical Society_ , vol. 101, no. 3, pp. 1068–1089, 2020.
  * [17] D. Augot, “Étude algèbrique des mots de poids minimum des codes cycliques, méthodes d’algèbre linéaire sur les corps finis.” Ph.D. dissertation, Université Pierre et Marie Curie-Paris VI, 1993.
  * [18] ——, “Description of minimum weight codewords of cyclic codes by algebraic systems,” _Finite Fields and Their Applications_ , vol. 2, no. 2, pp. 138–152, 1996.
  * [19] H. Mattson and G. Solomon, “A new treatment of Bose-Chaudhuri codes,” _Journal of the Society for Industrial and Applied Mathematics_ , vol. 9, no. 4, pp. 654–669, 1961.
  * [20] T. Kasami, “Weight distributions of Bose-Chaudhuri-Hocquenghem codes,” _Coordinated Science Laboratory Report no. R-317_ , 1966.
  * [21] T. Kasami, S. Lin, and W. W. Peterson, “Some results on cyclic codes which are invariant under the affine group and their applications,” _Information and Control_ , vol. 11, no. 5-6, pp. 475–496, 1967.
  * [22] F. J. MacWilliams and N. J. A. Sloane, _The theory of error correcting codes_. Elsevier, 1977, vol. 16.
  * [23] E. Assmus Jr and J. Key, “Polynomial codes and finite geometries,” _Handbook of coding theory_ , vol. 2, no. part 2, pp. 1269–1343, 1998.
  * [24] S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoğlu, and R. L. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4298–4316, 2017.
  * [25] G. Reeves and H. D. Pfister, “Reed-Muller codes achieve capacity on BMS channels,” arXiv:2110.14631, 2021.