# Cybertwin-enabled 6G Space-air-ground Integrated Networks: Architecture,
Open Issue, and Challenges

Zhisheng Yin1, , Tom H. Luan1, , Nan Cheng2, ,
Yilong Hui2, , and Wei Wang3 This work was supported by National Natural
Science Foundation of China (No. 62071356). Corresponding author: Tom H. Luan
and N. Cheng (email<EMAIL_ADDRESS>dr.nan.cheng@ieee.org). 1State
Key Lab. of ISN and School of Cyber Engineering, Xidian University, Xi’an,
710071, China  2State Key Lab. of ISN and School of Telecommunications
Engineering, Xidian University, Xi’an, 710071, China  3College of Electronic
Information Engineering, Nanjing University of Aeronautics and Astronautics,
Nanjing, 211106, China

###### Abstract

Space-air-ground integrated network (SAGIN) is considered as a core
requirement in emerging 6G networks, which integrates the terrestrial and non-
terrestrial networks to reach the full network coverage and ubiquitous
services. To envision the ubiquitous intelligence and the deep integration in
6G SAGIN, a paradigm of cybertwin-enabled 6G SAGIN is presented in this paper.
Specifically, a cybertwin-enabled SAGIN architecture is first presented, where
a novel five-dimension digital twin (DT) model is presented. Particularly,
three categories of critical technologies are presented based on the cybertwin
of SAGIN, i.e., cybertwin-based multi-source heterogeneous network
integration, cybertwin-based integrated cloud-edge-end, and cybertwin-based
integrated sensing-communication-computing. Besides, two open issues in the
cybertwin-enabled SAGIN are studied, i.e., the networking decision and
optimization and the cybertwin-enabled cross-layer privacy and security, where
the challenges are discussed and the potential solutions are directed. In
addition, a case study with federal learning is developed and open research
issues are discussed.

###### Index Terms:

Cybertwin, 6G, SAGIN, digital twin.

##  I Introduction

Space-air-ground integrated network (SAGIN) enables full network coverage
range, which can increase the network capability, provide seamless
connectivity, and enhance network performance [1]. In the emerging 6G
networks, the particular features of intelligence, complexity, dynamics, and
customization are emphatically concerned, aiming to cover full service
scenarios and full coverage. On the exploration of developing 6G networks,
SAGIN shows a considerable potential and has attracted extreme attentions in
academia and industry [2]. However, the key technologies and methods in SAGIN
network service fulfillment are still under investigating.

SAGIN is known as a multi-tier network consists of space networks, aerial
networks, and terrestrial networks, which are recognizably heterogeneous and
hold respective advantages and challenges[3]. Particularly, the space networks
of satellites broadcast widely and have strong damage resistance of disasters,
while the extra long-link transmission indicates long delay and the limited
resource (e.g., power, computing, and transponders, etc.) at satellite
manifests low processing capability. For the aerial networks, high-altitude
platforms (HAPs) and unmanned aerial vehicles (UAVs) can be dynamically
deployed to independently provide services or assist a special area, which is
flexible to self-organize and expand [4]. Whereas the terrestrial networks
develop faster and have relatively mature technologies, it holds appreciable
capability and supports rapid-rate transmissions and lower latency with high
throughput. Particularly, such multi-tier networks are dynamically
heterogeneous in multi-dimensional resources and different transmission
protocols. Considering the service fulfillment is significantly affected by
different network protocols, dynamic link conditions, and heterogeneous
resources, it renders the service fulfillment in SAGINs overwhelmingly
challenging. Specifically, there exposes challenges for SAGIN to intelligently
and effectively operate as a whole network, such as

  * •

Mobility: Low earth orbit (LEO) satellites operate under the high mobility
condition since its non-geostationary characteristics, which requires the
efficient communication and handover of satellite constellation to response
immediately. Besides, the aerial network provider such as the UAV is also
deployed with the high mobility and its opportunistic access strategy is hard
to guarantee the continuous communication. Thus the challenge of mobility
management also refers to the coordination between the three segments in
SAGIN.

  * •

Heterogeneity: SAGIN is a typical heterogeneous network, since it is consisted
of multi-tier networks with different network and communication protocols. The
terminals of SAGIN are expected to be designed as multi-mode and handover
among different access networks smoothly. However, the different node
resources have the differentiated functions, the key to reach the deep
integration in SAGIN is to adequately utilize the distinguished
characteristics and efficiency of such nodes for achieving the fusion with
maximum efficiency.

  * •

Latency: Compared with the terrestrial networks, the long transmission link
between satellite and the ground indicates the large latency. It is
challenging to complete a task/service with low latency through satellite.
Therefore, the latency-sensitive services are generally expected to be
executed in one-time transmission, which needs the high reliability of
communications.

Figure 1: DT mapping model in SAGIN.

With the vision that 6G networks connecting the physical world to the digital
world, the requirements of digitization and intelligence for SAGIN is an
irresistable trend. The digital twin (DT) technology provides a promising
paradigm. A DT is the precise virtual copy of a physical machine or system
mirrors almost every facet of a product, process or service [5, 6]. Initially,
the DT concept model is first presented in [7], which contains three main
parts, i.e., physical products in real space, virtual products in virtual
space, and the connections of data and information that ties the virtual and
real space together. Driven by but not limit to the DT, a cybertwin network
architecture for 6G is first presented in [8, 9], where the cybertwin serves
as communications assistant, network behavior logger, and digital asset owner.
Appreciated to this work, the cloud-centric network architecture and radio
access network (RAN) architecture are proactively given, and particularly
resources (computing, caching, and communications resources) allocation
coordinately and decoupling the control and user planes are addressed.
Particularly, a basic DT communication model are first presented in [10],
including inter-twin and intra-twin communication models, and a case study of
DT system for autonomous vehicles is conducted. Inspired by the investigations
of DT and cybertwin, it motivates us to consider a new framework of cybertwin-
driven SAGIN to decouple its complex network management and fulfill
diversified services.

In this paper, a novel cybertwin-enabled SAGIN architecture to enable the
digital reflection and the intelligent management of SAGIN is presented. The
main work includes the following.

  * •

To address the multi-tier heterogeneity and dynamic networking, we present the
cybertwin-enabled multi-source heterogeneous network integration in SAGIN,
where a cybertwin-enabled SAGIN resource orchestration flow is conducted to
support the service-oriented resource management.

  * •

To improve the networking efficiency and enhance an inherent coordination, we
further depict the cybertwin-enabled integrated cloud-edge-end in SAGIN, where
the integrated cloud-edge-end resource pool is established and the cybertwin-
enabled collaborations among local ends, edges, and the core cloud can be
reached. Considering the scene information and user intentions, the cybertwin-
enabled integrated sensing-communication-computing model is presented to
improve the differentiated service experiences.

  * •

Moreover, the future research issues and the potential solutions are directed
in the cybertwin-enabled SAGIN, i.e., AI-based networking decision and
optimization, and federated learning (FL) based cross-layer privacy and
security. In addition, a case study of model training in the cybertwin-enabled
SAGIN has been conducted through a FL approach.

##  II Cybertwin-enabled SAGIN Architecture

To represent the physical SAGIN entity digitally, we depict a five-dimension
SAGIN DT model to conduct the SAGIN cybertwin, which can be deployed at the
core and edge clouds in the physical SAGIN. Particularly, we define the five-
dimension SAGIN DT model and the DT mapping model is shown in Fig. 1.

Figure 2: Cybertwin-enabled SAGIN architecture.

  * •

Sat-DT represents the DT of satellites. It holds the activity information of
LEO satellites, including the orbiting logger and the dynamic resource status.

  * •

UAV-DT represents the DT of aerial UVAs. Similarly, it directs the mobility of
UAVs trajectory and holds the dynamic time-varying network status.

  * •

BS-DT represents the DT of terrestrial BSs. It manages the communication and
computation resources of BS.

  * •

Agent-DT represents the DT of mobile agent. It supervises and records the
activity information of mobile agent.

  * •

Connection between different kinds of DTs is established to exchange
information crossing multi-tier RANs.

Figure 3: Cybertwin-enabled SAGIN resource orchestration flow.

Fig. 2 shows our developed cybertwin-enabled SAGIN architecture, where the
physical space and the cybertwin space of SAGIN are included. In the SAGIN
physical space, there are three-layer connected radio access networks (RANs),
i.e., LEO satellite RAN, aerial RAN, and terrestrial RAN. The mobile agents
can access such three-layer RANs according to the different requirements.

With the data information collected from the SAGIN physical space, the
physical SAGIN can be reflected veritably by the DTs in SAGIN cybertwin space
and the cybertwin-enabled service function models can be realized by the data
analyzing and processing. Moreover, such service function models care be
mapped into the SAGIN physical entity to configure and adjust the network
operation and it the on-demand service can be directed. Particularly, we
present three categories of critical technologies based on the cybertwin of
SAGIN as follows, i.e., cybertwin-based multi-source heterogeneous network
integration, cybertwin-based integrated cloud-edge-end, and cybertwin-based
integrated sensing-communication-computing

Cybertwin-based Multi-source Heterogeneous Networking Integration in SAGIN

SAGIN is a typical multi-source heterogeneous network and the compatibility of
such multi-mode communications and networking is crucial for the integration
of multi-source heterogeneous networks in SAGIN. Particularly, how to
integrate the heterogeneous resource efficiently and effectively is still an
open issue. Considering the increasing diverse services which hold different
key performance indicators (KPIs), the service-oriented networking has
attracted great attentions and it shows potential in providing flexible
network service and enhanced network performance by accurately matching the
network resource and the service requirements.

Mobile agents such as multi-mode devices/terminals generally have different
KPIs and they are permitted to access satellite, aerial, and terrestrial RAN
selectively. Different service KPIs have different demands on resource, e.g.,
communication and computation resources. To improve the spectral efficiency
and satisfy the quality of service (QoS) of users, we arguably consider that
all the available resources in SAGIN are open to any agent and allocated by
orienting on-demand.

To achieve the deep integration of multi-source heterogeneous network in
SAGIN, we present a cybertwin-enabled SAGIN resource orchestration flow as
shown in Fig. 3. Particularly, the access layer is only responsible for
receiving and forwarding the access and service requests in the uplink, and
delivering data/contents to users in the downlink. According to the demand
indicators, cybertwin as the brain of SAGIN provides access policy and
resource orchestration, which holds the global information and makes decisions
on behalf of agents and physical network entity.

Figure 4: Cybertwin-based integrated cloud-edge-end in SAGIN

Moreover, in the cybertwin space, the four kinds of DTs with different
numerologies are grouped in a meeting and they can exchange information with
each other. Thus, the decisions of access selection and the resource
allocation for users are multilaterally bargained at that DT meeting. Without
loss of generality, each couple of entity and its DT are symbiotic and they
can identify each other. When the service requested by an agent is being
ended, the agent-DT can beforehand broadcast resource release information,
which can support a precognition and preparing for new services. In addition,
considering the DTs hold the behavior data logging of mobile agents, it can be
converted into a digital asset for the science/project experiment and sale
after removing sensitive information.

Cybertwin-based Integrated Cloud-edge-end in SAGIN

To support diversified and differentiated services from a prospective of on-
demand fulfillment, it is considerably imperative to regulate a consensus that
such multi-source heterogeneous resources can be shared and collaboratively
orchestrated. Benefiting from wide investigations of resource virtualization
and customized network functions such as network slicing, software-defined
networking (SDN), and network function virtualization (NFV) techniques[11],
hence since it is indispensable and reasonable to conduct the integrated
cloud-edge-end in SAGIN. Fig. 4 shows our developed cybertwin-based integrated
cloud-edge-end in SAGIN, it mainly consists of three-segment service and
resource providers, i.e., local end, edge network, and core cloud.
Particularly, although the core cloud has abundant computation resource and
supports the large-scale and complex services, mobile edge computing (MEC) is
proposed for decentralizing cloud services to the network edges to achieve
lower latency, and such three edge networks in SAGIN can collaboratively
construct the service function chain (SFC). Besides, the local terminals also
have certain processing capability and they can also share resource with other
services. From Fig. 4, it can be also seen that the cybertwin unit exists in
the cloud and edges and each DT of an end or service serves as the agent with
full authority to maximize the best service experience for its host.

Without loss of generality, considering a comprehensive and intricate service
in SAGIN, a task offloading is generally executed when the local servers
cannot process timely to reduce the energy consumption of local end and the
latency. Different from traditional greedy schemes, a globally optimal
offloading strategy is prepared by such DTs in cybertwin space, where the
integrated cloud-edge-end resource pool is scheduled. Thus, a task workflow
can be carried out through a cooperation of local end, edge network, and core
cloud. Moreover, an assistance among local ends or task migration among edges
with different numerologies can be also executed according the result of DT
decision. Particularly, considering those services in remote areas where
satellite constellation provides the RAN, task migrations to cloud or other
edges can improve the service efficiency, due to the limited resource at
satellites.

Cybertwin-based Integrated Sensing-communication-computing in SAGIN

Figure 5: Cybertwin-enabled integrated sensing-communication-computing model
in SAGIN

A cybertwin-enabled integrated sensing-communication-computing model in SAGIN
is presented in Fig. 4, where the sensing layer, cybertwin layer, resource
layer, and service layer are included. We aim to conceive a service-orient
system model and conduct a cybertwin-centric guideline. Then the four-layer
cybertwin-enabled integrated sensing-communication-computing model is
introduced respectively through these four layers as follows.

Sensing layer: Mobile terminals with intelligent sensing devices can collect
visual environment information and electromagnetic spatial information through
sensors. The visual environment information contains the surrounding
environment and mobility of mobile agents, referring to environmental
monitoring, target detection and identification, and the state parameter
measurement. For instance, the road condition, traffic command information and
the state of vehicles in motion can be collected by the visual sensors mounted
on vehicles. The electromagnetic spatial information can reflect a state of
networking and communication, where the knowledge of spectrum occupancy and
channel state information etc. could be a local feedback to improve
communication performance. Particularly, we assume all the mobile agents,
satellite, UAV, and BS have the ability of spectrum sensing. Such sensed
information is updated in real-time and gathered in cybertwin.

Cybertwin layer: In the cybertwin space, the DTs hold its corresponding sensed
information respectively, which can be used to analyze and predict some
inertial behaviors and direct a quick response. To support customized
services, we conduct four main functions such as data logging, model training,
information exchange, and decision making in the cybertwin space of SAGIN. For
the function of data logging, the DT logs fresh and important information
which can be updated obeying a constraint of the age of information (AoI)
[12]. With the centralized database from sensing layer and global networking
information, the cybertwin can training communication and networking
optimization models for services with on-demand access, where the artificial
intelligence (AI) techniques can provide effective and flexible supports.
Particularly, the information exchange between different DTs provides a global
perspective for any local service, which enables improved resource sharing and
utilization. By the cybertwin, we assume all the complex decisions made by DTs
and the mobile agents and physical entity just execute its resource
corresponding orchestration strategy and service function chain, thus the
resource consumption of local mobile agents and access points can be
significant reduced.

Resource layer: Multi-source heterogeneous resources can be scheduled by the
orchestration strategy from the cybertwin and we assume a reserved resource in
the resource pool to ensure the system operation running and prepare for
urgent services or response to abnormal faults.

Service layer: We consider communication and computation services in the
service layer. Combining the sensed information and communication request, the
communication system is designed with compatible transmission and access
schemes which can support differentiated the communication requirement by
flexibly scheduling communication resource. Particularly, due to random
service requests and uncertain interference, discontinuous and available
spectrum resources require a fusion scheme of broad and narrow band to improve
the spectral efficiency, and an adaptive communication coverage is controlled
by the cybertwin and executed by mobile RAN entities in SAGIN. For the
computation services, the sensed information including the appropriate objects
for task offloading and migration are reported to the cybertwin and a
cooperative scheme can be realized. Besides, with analyzing the sensed
information and current networking status, a computation fusion model can be
directed to reduce the latency.

##  III Open Issues and Challenges

AI-based Networking Decision and Optimization in Cybertwin-enabled SAGIN

In the cybertwin-enabled SAGIN, to intelligently and efficiently manage such
multi-source heterogeneous network, the cybertwin uploads and updates various
function models of decision and optimization which maps different services.
Particularly, the DTs in SAGIN cybertwin hold many kinds of data, i.e., the
environment information, the networking state information, and the service
requested KPI, and it is expected immediately and accurately reflect the
physical space of SAGIN. Considering the service diversity, the great variety
and large volume of data, and the dynamic topology of physical SAGIN. it is
challenging to effectively and efficiently manage the network. Whereas, to
handle such challenges, AI-based approaches have the great potential in
networking decision and optimization[13].

Networking decision: Based on the data warehouse created in the cybertwin, the
function models of networking analysis, prediction, maintenance, etc. can be
trained and updated by AI algorithms for a specific application, which
achieves the model-decision making and decouples the control and service
layers of physical SAGIN. Particularly, due to the multi-tier heterogeneous
RANs in SAGIN, the access control decision is challenging to realize the
global optimization by using traditional random or fixed access strategies.
However, with the specific scenario information and the networking behavior
learning, AI-based access control model can be realized in the cybertwin space
and the model-decision can be delivered to the corresponding physical entity
expediently.

Networking optimization: Although we have developed an integrated cloud-edge-
end resource pool in SAGIN based on cybertwin, however, the resource from
different physical network providers shows differentiated characteristics,
which is leveraged to be constrained on specific indicators, i.e., delay,
bandwidth, power, and computation, etc. Therefore, it is challenging to
orchestrate and optimize the heterogeneous resources in SAGIN. To fulfill the
on-demand resource allocation, the resource classification can be first
conduct in the cybertwin according to the constrained KPIs. By information
exchange among DTs, specific networking optimization models can be trained by
AI-based approaches with using global resources. Particularly, these
optimization model can be pre-generated through simulations with historical
data in the cybertwin space, which is then mapped into the physical SAGIN
entities to execute a networking optimization.

FL-based Cross-layer Privacy and Security in Cybertwin-enabled SAGIN

We consider inter-DT communications among the DTs of SAGIN entity in the SAGIN
cybertwin, and thus the cybertwin provides an information exchange platform
through the meeting of DTs for users and entities in different physical
networks. However, it is hard to establish an uniform confidential mechanism
among the DTs to preserve the private data of host from being exposed to
adversaries, since the DT is possible to be falsely impersonated. Thus, the
physical SAGIN network is vulnerable to be attacked if the DT security could
not be ensured. Moreover, since the data hold in a DT is the digital asset
which has significant research values and economic benefits, it can be traded
in the digital market. The host of DT will experience the economic loss and
the privacy leak when its DT is confused.

Particularly, as a distributed ML approach, FL has been introduced to address
the issue of privacy protection, where the ML model can be trained at local
end and which is then sent to the edge/cloud server[14]. It sends the model
updates rather than raw data to the server for aggregation. However, for the
model transmissions via wireless communications, it is vulnerable to be
eavesdropped.

To address the challenges of privacy and security in cybertwin-enabled SAGIN,
we direct a potential research issue of FL-based cross-layer privacy and
security in cybertwin-enabled SAGIN. Particularly, the local private data can
be trained at the DT of this end and an secure transmission should be ensured
in physical layer when the local model is uploading and the aggregated model
is downloading.

##  IV A Case Study

In this section, we conduct a case study of cybertwin-enabled deep integration
in SAGIN. Particularly, considering the heterogeneity of SAGIN, heterogeneous
mobile agents served by different RANs of SAGIN, i.e., satellite network,
aerial network, and terrestrial network, only focus on its local resource and
it is difficult to join in a comprehensive training crossing different tiers.
To investigate the cybertwin-enabled comprehensive training in SAGIN, we train
a classification model based on the MNIST data set in the cybertwin space of
SAGIN. Specifically, we consider a simple system model of cybertwin-enabled
SAGIN where the physical RANs consisting of a LEO satellite, an UAV, and a
terrestrial BS. There are multiple user agents connecting to satellite, UAV,
and BS, respectively. Particularly, we conduct a simulation to evaluate the
model training with FL in cybertwin-enabled SAGIN and the system parameters
are specifically set as follows.

In satellite network, the height of satellite orbit is 600 Km, the maximum
beam gain is 46 dB, and the 3-dB angle of satellite beam is set to 0.4∘. The
rain attenuation parameters of satellite-terrestrial channel are set to -3.152
dB and 1.6 [15]. In the UAV-based aerial network, the horizontal distance from
UAV to the boundary of coverage is 100 m, the UAV altitude is 100 m, and
Rician fading model is adopted as the small-scale fading. The UAV transmit
power is set to 15 dB. The number of UAV downlink transmit antennas is four.
For the terrestrial network, the BS is equipped with four transmit antennas
and the transmission power is set to 40 dB. Besides, there are five users
connected to satellite, UAV, and terrestrial BS, respectively. In addition,
the learning model contains a flatten layer, a dense layer with 128 units, a
dropout layer with a scale of 0.2, and an output layer with 10 units. The data
set held by each user contains 200 samples. For the comparison, we also
evaluate the performance of independently performing FL in satellite network,
UAV-based network, and terrestrial network, respectively.

Figure 6: The model accuracy of FL in cybertwin-enabled SAGIN

Fig. 6 shows the model accuracy of FL in cybertwin-enabled SAGIN. From Fig. 6,
it can be seen that the FL in terrestrial network shows the fastest
convergence speed (convergence at about 100 s), followed by the UAV-based
network (convergence at about 150 s), and that in satellite network and SAGIN
are the slowest (convergence at about 300 s). This is because the delay of
communication link in satellite network is larger due to its long-distance
transmission link, followed by the UAV-based network, then is that in the
terrestrial network. Thus the date updates slower in Sat-DT than UAV-DT and
BS-DT, which leads to a longer time for training the model with Sat-DT.
Moreover, due to the straggler effect, the convergence speed is determined by
the segment with slowest convergence speed, therefore the model training of FL
in SAGIN converges slowly. In addition, it is observed that the higher model
accuracy can be achieved when performing FL in the cybertwin of SAGIN. This is
because all the heterogeneous mobile agents can participate in training in the
cybertwin of SAGIN, which converts the local training to a global training,
thereby the model accuracy increases.

##  V Conclusion

In this paper, to support the on-demand service and improve the networking
efficiency, a cybertwin-enabled SAGIN architecture has been presented to reach
the deep integration of multi-tier heterogeneous networks and envision the
ubiquitous intelligence towards 6G. Particularly, with the cybertwin, we have
presented three categories of critical technologies in SAGIN, i.e., cybertwin-
based multi-source heterogeneous network integration, cybertwin-based
integrated cloud-edge-end, and cybertwin-based integrated sensing-
communication-computing. They can support the implementation of cybertwin-
enabled SAGIN with improved networking efficiency and service experience. In
addition, we have presented and discussed two open research issues, and the
potential solutions have also been directed accordingly by the AI-based
approach and FL respectively. Finally, a case study of model training in
cybertwin-enabled SAGIN has been conducted through FL and the result shows an
increased model accuracy by the cybertwin-enabled networking integration in
SAGIN.

## References

  * [1] S. Zhou, G. Wang, S. Zhang, Z. Niu, and X. Shen, “Bidirectional mission offloading for agile space-air-ground integrated networks,” _IEEE Wireless Commun._ , vol. 26, no. 2, pp. 38–45, Apr. 2019.
  * [2] X. You, C.-X. Wang, J. Huang, X. Gao, Z. Zhang, M. Wang, Y. Huang, C. Zhang, Y. Jiang, J. Wang _et al._ , “Towards 6g wireless communication networks: Vision, enabling technologies, and new paradigm shifts,” _Science China Information Sciences_ , vol. 64, no. 1, pp. 1–74, 2021.
  * [3] J. Liu, Y. Shi, Z. M. Fadlullah, and N. Kato, “Space-air-ground integrated network: A survey,” _IEEE Commun. Surveys Tuts._ , vol. 20, no. 4, pp. 2714–2741, 2018.
  * [4] T. Ma, H. Zhou, B. Qian, N. Cheng, X. Shen, X. Chen, and B. Bai, “UAV-LEO integrated backbone: A ubiquitous data collection approach for b5g internet of remote things networks,” _IEEE J. Sel. Areas Commun._ , 2021, early access.
  * [5] F. Tao, H. Zhang, A. Liu, and A. Y. C. Nee, “Digital twin in industry: State-of-the-art,” _IEEE Trans. Ind. Informat._ , vol. 15, no. 4, pp. 2405–2415, 2019.
  * [6] Y. Wu, K. Zhang, and Y. Zhang, “Digital twin networks: a survey,” _IEEE Internet Things J._ , 2021, early access.
  * [7] M. Grieves, “Digital twin: manufacturing excellence through virtual factory replication,” _White paper_ , vol. 1, pp. 1–7, 2014.
  * [8] Q. Yu, J. Ren, H. Zhou, and W. Zhang, “A cybertwin based network architecture for 6g,” in _2020 2nd 6G Wireless Summit (6G SUMMIT)_ , 2020, pp. 1–5.
  * [9] Q. Yu, J. Ren, Y. Fu, Y. Li, and W. Zhang, “Cybertwin: An origin of next generation network architecture,” _IEEE Wireless Commun._ , vol. 26, no. 6, pp. 111–117, 2019.
  * [10] T. H. Luan, R. Liu, L. Gao, R. Li, and H. Zhou, “The paradigm of digital twin communications,” _arXiv preprint arXiv:2105.07182_ , 2021.
  * [11] W. Zhuang, Q. Ye, F. Lyu, N. Cheng, and J. Ren, “SDN/NFV-empowered future IoV with enhanced communication, computing, and caching,” _Proc. IEEE_ , vol. 108, no. 2, pp. 274–291, 2020.
  * [12] J. Sun, L. Wang, Z. Jiang, S. Zhou, and Z. Niu, “Age-optimal scheduling for heterogeneous traffic with timely throughput constraints,” _IEEE J. Sel. Areas Commun._ , vol. 39, no. 5, pp. 1485–1498, 2021.
  * [13] Z. Jiang, S. Fu, S. Zhou, Z. Niu, S. Zhang, and S. Xu, “AI-assisted low information latency wireless networking,” _IEEE Wireless Commun._ , vol. 27, no. 1, pp. 108–115, 2020.
  * [14] K. Wei, J. Li, M. Ding, C. Ma, H. H. Yang, F. Farokhi, S. Jin, T. Q. S. Quek, and H. V. Poor, “Federated learning with differential privacy: Algorithms and performance analysis,” _IEEE Trans. Inf. Forensics Security_ , vol. 15, pp. 3454–3469, 2020.
  * [15] Z. Yin, M. Jia, N. Cheng, W. Wang, F. Lyu, Q. Guo, and X. Shen, “UAV-assisted physical layer security in multi-beam satellite-enabled vehicle communications,” _IEEE Trans. Intell. Transp. Syst._ , pp. 1–13, 2021.


# On certain properties of the
$p$-unitary Cayley graph over a finite ring

Tung T. Nguyen, Nguy$\tilde{\text{\^{e}}}$n Duy Tân  Department of
Kinesiology, Western University, London, Ontario, Canada N6A 5B7
<EMAIL_ADDRESS>Falculty of Mathematics and Informatics, Hanoi University
of Science and Technology, 1 Dai Co Viet Road, Hanoi, Vietnam
<EMAIL_ADDRESS>
###### Abstract.

In recent work [7], we study certain Cayley graphs associated with a finite
commutative ring and their multiplicative subgroups. Among various results
that we prove, we provide the necessary and sufficient conditions for such a
Cayley graph to be prime. In this paper, we continue this line of research.
Specifically, we investigate some basic properties of certain $p$-unitary
Cayeley graphs associated with a finite commutative ring. In particular, under
some mild conditions, we provide the necessary and sufficient conditions for
this graph to be prime.

###### Key words and phrases:

Cayley graphs, homogeneous sets, induced subgraphs, finite commutative rings.

###### 2020 Mathematics Subject Classification:

Primary 05C25, 05C50, 05C51

##  1\. Introduction

Let $G$ be an undirected graph. A homogeneous set in $G$ is a set $X$ of
vertices of $G$ such that every vertex in $V(G)\setminus X$ is adjacent to
either all or none of the vertices in $X$. A homogenous set $X$ is said to be
non-trivial if $2\leq X<|V(G)|$. As explained in [7, Section 1.1], the
existence of non-trivial homogeneous sets allows us to decompose $G$ as a
joined union of smaller graphs. Such a decomposition is important for many
problems in network theory and dynamical systems on them (see [5, 11, 13,
17]). In [7, Section 4], we study the prime property of various Cayley graphs
associated with a finite commutative ring. There, we provide necessary and
sufficient conditions for the existence of homogeneous sets in those Cayley
graphs under some mild conditions (see [7, Theorem 4.1]). In this paper, we
continue and expand this line of research to some other directions.
Specifically, we will investigate some basic properties of the $p$-unitary
Cayley graphs whose definition we will explain below.

Let $R$ be a finite commutative ring and $p$ a natural number. Let
$S=(R^{\times})^{p}$ be the set of all invertible $p$-th powers in $R$. Since
we only deal with undirected graphs in this paper; we will assume that
$-1\in(R^{\times})^{p}$.

######  Definition 1.1.

(See [20, Section 1.2]) The $p$-unitary Cayley graph $G_{R}(p)$ is the
undirected graph with the following data

  1. (1)

The vertex set $V(G_{R}(p))$ of $G_{R}(p)$ is $R.$

  2. (2)

Two vertices $a,b\in V(G_{R}(p))$ are connected if and only
$a-b\in(R^{\times})^{p}.$

######  Remark 1.2.

Because we want to deal with one prime at a time, we will assume that $p$ is a
prime number throughout the rest of this article.

######  Example 1.3.

The Cayley graph $X_{3,\operatorname{\mathbb{F}}_{13}}$ is described by Fig.
1. It is a connected, regular graph of degree $4.$

Figure 1. The Cayley graph $G_{\operatorname{\mathbb{F}}_{13}}(3)$

The case $p=1$, where $G_{R}(1)$ is often referred to as the unitary Cayley
graph associated with $R$, is studied extensively in the literature (see for
example [1, 3, 7, 14, 22]). When $R$ is a finite field of characteristics
$\ell\neq p$, $G_{R}(p)$ is called a generalized Paley graph. These
generalized Paley graphs have interesting arithmetic and spectral properties
and they have found various applications in coding and cryptography theory
(see [9, 12, 18, 20]).

In [7], amongst various results that we discover, we are able to classify all
prime unitary Cayley graphs (see [7, Theorem 4.35]). In light of this theorem,
the following question seems to be quite natural.

######  Question 1.4.

When is $G_{R}(p)$ a prime graph?

By definition, a connected component of $G$ (or of its complement $G^{c}$) is
necessarily a homogeneous set. Consequently, if $G_{R}(p)$ is prime, then it
must be connected and anticonnected unless $|V(G)|=2$ (recall that a graph is
called anticonnected if $G^{c}$ is connected). As a result, a closely related
question about $G_{R}(p)$ is the following.

######  Question 1.5.

When is $G_{R}(p)$ connected and anticonnected?

By [20, Corollary 2.5], we know the complete answer for 1.5 when $R$ is a
local ring such that $p$ is invertible in $R.$ The cases where either $p$ is
not invertible in $R$ or $R$ is not a local ring are more complicated and we
will deal with them in this work.

###  1.1. Outline

In Section 2, we recall some backgrounds in graph theory as well as some
relevant results in our previous work [7]. To proceed further, we remark that
by the structure theorem, $R=R_{1}\times R_{2}\times\ldots\times R_{d}$ where
$R_{i}$’s are finite local rings. We then see that $G_{R}(p)$ is the tensor
product of $G_{R_{i}}(p)$ (see Definition 2.2 for the definition of the tensor
product of graphs). More specifically

$G_{R}(p)\cong\prod_{i=1}^{d}G_{R_{i}}(p).$

From this tensor product decomposition, it seems natural to first study the
case where $R$ is a finite local ring. In this case, as expected, the behavior
of $G_{R}(p)$ depends on whether $p$ is invertible on $R$. In Section 3, we
discuss the case where $R$ is local and $p$ is invertible in $R$. Using the
results in [19], we are able to provide a complete answer to 1.4 (see 3.6). In
this section, we also study induced subgraphs of $G_{R}(p)$ which we need
later for the general case. However, this topic could be of independent
interest. Section 4 deals with the case where $R$ is local but $p$ is not
invertible in $R.$ In this case, using some rather involved ring-theoretic
arguments, we are also able to give a complete answer to 1.4 (see 4.15).
Additionally, we also investigate some induced subgraphs of $G_{R}(p)$ in this
case. As a by-product, we introduce some auxiliary polynomials $f_{p},g_{p}$
that possess some interesting arithmetic properties. Finally in Section 5, we
study 1.4 and 1.5 in the general case. Here, we provide the necessary and
sufficient conditions for $G_{R}(p)$ to be prime (see 5.5). We also discuss
some special cases where we can verify these conditions directly.

##  2\. Backgrounds and previous work

In this section, we discuss some fundamental concepts in graph theory. We also
recall some results in [7] that we will use throughout this article.

######  Definition 2.1 (Induced subgraph).

Let $G$ be a graph and $H\subseteq V(G)$ a non-empty subset. The induced
subgraph $\Gamma[H]$ on $H$ is the subgraph of $\Gamma$ with the following
data

  1. (1)

$V(G[H])=H$,

  2. (2)

$E(G[H])=\\{(x,y)\in E(G)|x,y\in H\\}$.

######  Definition 2.2 (Tensor product of graphs).

Let $G,H$ be two graphs. The tensor product $G\times H$ of $G$ and $H$ (also
known as the direct product) is the graph with the following data:

  1. (1)

The vertex set of $G\times H$ is the Cartesian product $V(G)\times V(H)$,

  2. (2)

Two vertices $(g,h)$ and $(g^{\prime},h^{\prime})$ are connected in $G\times
H$ if and only if $(g,g^{\prime})\in E(G)$ and $(h,h^{\prime})\in E(H).$

######  Definition 2.3 (Wreath product).

Let $\Gamma,\Delta$ be two graphs. We define the wreath product of $\Gamma$
and $\Delta$ as the graph $\Gamma\cdot\Delta$ with the following data

  1. (1)

The vertex set of $\Gamma\cdot\Delta$ is the Cartesian product
$V(\Gamma)\times V(\Delta)$,

  2. (2)

$(x,y)$ and $(x^{\prime},y^{\prime})$ are connected in $\Gamma\cdot\Delta$ if
either $(x,x^{\prime})\in E(\Gamma)$ or $x=x^{\prime}$ and $(y,y^{\prime})\in
E(\Delta)$.

######  Definition 2.4 (The complete graph $K_{n}$).

$K_{n}$ is the graph on $n$ vertices which are pairwisely connected.

We also recall the definition of certain Cayley graphs associated with a ring
as discussed in [7, Section 4].

######  Definition 2.5.

Let $R$ be a commutative ring, and $S$ a subgroup of the set $R^{\times}$ of
units of $R$ such that $-1\in S$. We denote ${\rm Cay}(R,S)$ the Cayley graph
$\text{Cay}((R,+),S)$. To be more specific, the vertex set of ${\rm Cay}(R,S)$
is $R$ and two vertices $a,b\in R$ are connected if and only if $a-b\in S.$

To study the prime property of ${\rm Cay}(R,S)$, we will make use of the
following result which was first discovered in [7].

######  Proposition 2.6.

(see [7, Theorem 4.1] and [7, Proposition 4.7]) Suppose that ${\rm Cay}(R,S)$
is connected and anti-connected. If ${\rm Cay}(R,S)$ is not prime, then there
exists a non-trivial ideal $I$ such that $I$ is a homogeneous set.
Furthermore, $I$ is a subset of the Jacobson radical of $R.$

##  3\. $G_{R}(p)$ where $R$ is a finite local ring of residue characteristics
$\ell\neq p$

###  3.1. When is $G_{R}(p)$ prime

Let $R$ be a local ring and $M$ its maximal ideal. Let $k=R/M$ be the residue
field. We suppose that ${\rm char}(k)\not=p$.

######  Proposition 3.1.

$M$ is a homogeneous set in $G_{R}(p).$ As a result, if $G_{R}(p)$ is prime,
then $R$ is a field.

###### Proof.

Since $R$ is finite, $R$ is henselian. Hence all roots of $x^{p}-a$ over $k$
lift to a root over $R$ by Hensel’s lemma. Thus
$(R^{\times})^{p}+M=(R^{\times})^{p}$ and $M$ is homogeneous. ∎

Since the Jacobson radical of a field is $0$, by 2.6, we know that the
question of whether $G_{R}(p)$ is prime reduces to the question of whether it
is connected and anticonnected. We remark that the graph $G_{R}(p)$ is not
always connected (Fig. 2 shows an example of a $p$-unitary Cayley graph with
$4$ connected components). In fact, in [20, Corollary 2.5], the authors
provide the precise condition for $G_{R}(p)$ to be connected. To recap this
result, we need to recall the definition of a primitive divisor.

######  Definition 3.2.

Let $\ell$ be a prime number and $m,n$ two natural numbers. We say that $n$ is
a primitive divisor of $\ell^{m}-1$ if $n|\ell^{m}-1$ and $n\nmid\ell^{a}-1$
for each $1\leq a\leq m-1.$ In this case, we write $n{\dagger}\ell^{m}-1.$

######  Proposition 3.3.

([20, Corollary 2.5] and [19, Corollary 3.1]) Suppose that $R=k$ is a field of
order $\ell^{m}$ where $\ell\neq p.$ Then $G_{R}(p)$ is connected if and only
one of the following conditions hold

  1. (1)

$p\nmid\ell^{m}-1.$ In this case $G_{R}(p)=K_{\ell^{m}},$

  2. (2)

$p|\ell^{m}-1$ and $\frac{\ell^{m}-1}{p}{\dagger}\ell^{m}-1.$

Figure 2. The Cayley graph $G_{\operatorname{\mathbb{F}}_{16}}(5)$

######  Corollary 3.4.

Suppose that $R=k$ is a field of order $\ell^{m}$ where $\ell\neq p.$ If
$\ell>p$ then $G_{R}(p)$ is connected.

###### Proof.

If $p\nmid\ell^{m}-1$, then the statement is true since
$G_{R}(p)=K_{\ell^{m}}$. Now, suppose that $p|\ell^{m}-1.$ If $1\leq a\leq
m-1$, then

$\ell^{a}-1\leq\ell^{m-1}-1<\frac{\ell^{m}-1}{\ell}<\frac{\ell^{m}-1}{p}.$

Consequently $\dfrac{\ell^{m}-1}{p}{\dagger}\ell^{m}-1$ and hence $G_{R}(p)$
is connected. ∎

######  Proposition 3.5.

Suppose that $R=k$ is a field of order $\ell^{m}$ where $\ell\neq p$. Assume
further that $G_{R}(p)$ is connected. The following conditions are equivalent.

  1. (1)

$p\nmid\ell^{m}-1.$

  2. (2)

$(R^{\times})^{p}=R^{\times}=R\setminus{0}$.

  3. (3)

$G_{R}(p)=K_{\ell^{m}}.$

  4. (4)

$G_{R}(p)$ is not anticonnected.

###### Proof.

The equivalence of $(1)-(2)-(3)$ follows from the fact that $R^{\times}$ is a
cyclic group of order $\ell^{m}-1.$ Clearly, $(3)$ implies $(4).$ We claim
that $(4)$ implies $(2)$ as well. Suppose, in fact, that $G_{R}(p)$ is not
anticonnected but $R^{\times}\neq(R^{\times})^{p}.$ Let $a\in
R^{\times}\setminus(R^{\times})^{p}.$ Let $\Phi_{a}:R\to R$ be the
multiplication by $a$ map. Since $a\not\in(R^{\times})^{p}$, under $\Phi_{a}$,
$G_{R}(p)$ is a subgraph of $G_{R}(p)^{c}.$ Since $G_{R}(p)$ is connected,
$G_{R}(p)^{c}$ is connected as well. This is a contradiction. We conclude that
$(R^{\times})^{p}=R^{\times}$. ∎

Combining 3.1, 3.3 and 3.5 we answer 1.4 in the case $R$ is a finite local
ring with residue characteristics $\ell\neq p.$

######  Theorem 3.6.

Suppose that $R=k$ is a finite local ring of residue characteristics $\ell\neq
p$. Then $G_{R}(p)$ is prime if and only if the following conditions hold

  1. (1)

$R$ is a finite field of order $\ell^{m}.$

  2. (2)

$p|\ell^{m}-1$ and $\frac{\ell^{m}-1}{p}{\dagger}\ell^{m}-1.$

###  3.2. Induced subgraphs of $G_{R}(p)$

In this section, we study various induced subgraphs of $G_{R}(p).$ This will
be helpful later on when we study the general case. First, we remark that by
3.1, we can safely assume that $R$ is a finite field of characteristics
$\ell\neq p.$ Therefore, we will assume that $R$ is a finite field throughout
this section. Furthermore, if $p\nmid|R|-1$ then $G_{p}(R)=K_{|R|}$.
Consequently, most of our results would be either obvious or in need of some
easy modifications. Therefore, we will also assume that $p$ is a divisor of
$|R|-1.$

Our main tool in this section is the theory of character sums and their Weil
bounds (see [2, 15]). To do so, we first make a connection between $G_{R}(p)$
and character theory. We know that $R^{\times}$ is a cyclic group of order
$|R|-1.$ By fixing a generator $g\in R^{\times}$, we have an embedding

$\iota:R^{\times}\hookrightarrow\operatorname{\mathbb{C}}^{\times},$

sending $g\mapsto\zeta_{|R|-1}$ where $\zeta_{|R|-1}$ is a primitive
$(|R|-1)$-th root of unity. Let $\chi:R^{\times}\to\operatorname{\mathbb{C}}$
be the character defined by $\chi(g)=\zeta_{|R|-1}^{\frac{|R|-1}{p}}.$ Then
$\chi$ is a character of order $p$. Furthermore, $\chi(x)=1$ if and only
$x\in(R^{\times})^{p}.$ We also define $\chi(0)=0$.

######  Remark 3.7.

We recall that in [7, 16], we define and study the Paley graph $P_{\chi}$ as
${\rm Cay}(R,\ker(\chi))$. The above discussion shows that
$P_{\chi}=G_{R}(p).$

To apply the Weil bound, we introduce the following auxiliary polynomials.

$P_{1}(x)=\frac{1}{p}\left(\frac{1-x^{p}}{1-x}\right)=\frac{1}{p}\left(1+x+\ldots+x^{p-1}\right),$

and

$P_{0}(x)=1-P_{1}(x)=\frac{p-1}{p}-\frac{1}{p}\left(x+x^{2}+\ldots+x^{p-1}\right).$

We can see that if $z$ is a $p$-th root of unity; i.e. $z^{p}=1$, then

$P_{1}(z)=\begin{cases}1&\text{if }z=1\\\ 0&\text{else.}\end{cases}$

Similarly

$P_{0}(z)=\begin{cases}0&\text{if }z=1\\\ 1&\text{else.}\end{cases}$

######  Lemma 3.8.

Suppose that $R=k$ is a field of characteristics $\ell\neq p$. Suppose that
$|R|\geq(p+1)^{4}$. Then $K_{3}$ is a subgraph of $G_{R}(p)$. More
specifically, there exists $a\in R\setminus\\{0,1\\}$ such that the induced
subgraph on $\\{0,1,a\\}$ is $3.$

###### Proof.

We will look for $a$ of the form $a=x^{p}$ where $x\in R^{\times}.$ With this
choice, we only need to make sure that $(1,x^{p})\in E(G_{R}(p)).$ In other
words, we need to find $x\neq 0$ such that $\chi(1-x^{p})=1.$ Let $T$ be the
set of all $a\in R$ such that either $a=0$ or $a^{p}=1.$ We know that
$|T|=p+1.$ Let $S$ be the set of all $x\in R^{\times}$ such that
$\chi(1-x^{p})=1.$ Let us consider the following function

$f(a)=P_{1}(\chi(1-a^{p}))=\frac{1}{p}\frac{\chi(1-a^{p})^{p}-1}{\chi(1-a^{p})-1}=\frac{1}{p}\sum_{k=0}^{p-1}\chi^{k}(1-a^{p}).$

We can see that if $a\in R$ then $0\leq|f(a)|\leq 1$. Additionally, if $a\in
T\setminus\\{0\\}$ then $f(a)=\frac{1}{p}$; $f(0)=1$. Furthermore, if
$x\not\in T$, then $f(a)=1$ if $a\in S$ and $f(a)=0$ otherwise. We conclude
that

$|S|=\sum_{a\in R}f(a)-\sum_{a\in
T}f(a)=\frac{1}{p}\sum_{k=0}^{p-1}\left(\sum_{a\in
R}\chi^{k}(1-a^{p})\right)-\frac{p+p}{p}.$

By the Weil bound, we know that for $1\leq k\leq p-1$

$\left|\sum_{a\in R}\chi^{k}(1-a^{p})\right|\leq(p-1)\sqrt{|R|}.$

On the other hand, when $k=0$ we have

$\left|\sum_{a\in R}1\right|=|R|.$

Therefore, by triangle inequality we have

$p|S|\geq|R|-(p-1)^{2}\sqrt{|R|}-2p.$

By an elementary calculation, we can see that that if $|R|\geq(p+1)^{4}$ then
$|S|>0.$ In other words, we can find $x\in(R^{\times})$ such that the induced
graph on $\\{0,1,x^{p}\\}$ is $K_{3}.$ ∎

######  Remark 3.9.

The bound $|R|>(p+1)^{4}$ also implies that the Waring problem for $R$ has an
exact answer (see [19, Example (a), Page 3].)

######  Corollary 3.10.

Suppose that $R=k$ is a field of characteristics $\ell\neq p$. Assume that
either $\ell$ is odd or $|R|>(p+1)^{4}$. Then $R_{R}(p)$ is a not bipartite
graph.

###### Proof.

$G_{R}(p)$ contains the $C_{\ell}$-cycle

$0\to 1\to\cdots\to\ell-1\to 0.$

Therefore, if $\ell$ is odd then $G_{R}(p)$ is not a bipartite graph.
Similarly, if $|R|>(p+1)^{4}$ then $\textbf{C}_{3}=K_{3}$ is an induced
subgraph of $G_{R}(p)$. Therefore, $G_{R}(p)$ is not a bipartite graph. ∎

######  Remark 3.11.

We wrote some Sagemath code to search for an example where $G_{R}(p)$ is
bipartite (by 3.10, we only need to consider the case $R$ is a finite field of
characteristics $2$). So far, our attempt has been unsuccessful. This leads us
to wonder whether such an example exists at all.

In [8], the authors show that for each $n$, the complete graph $K_{n}$ is an
induced subgraph of the generalized Paley graph
$G_{\operatorname{\mathbb{F}}_{\ell}}(2)$ as long as $\ell$ is large enough.
More generally, the main result in [6] shows that for a fixed graph $G$, $G$
is an induced subgraph of $G_{\operatorname{\mathbb{F}}_{\ell}}(2)$ if $\ell$
is big enough. At the time of our writing, it is unclear to us whether similar
results have been obtained for $G_{\operatorname{\mathbb{F}}_{\ell}}(p).$
Since the proof for this fact is quite standard and straightforward, we
provide it here for the sake of completeness.

######  Theorem 3.12.

Let $G$ be an undirected graph. Let $p$ be a fixed prime number and $R$ a
prime finite field of characteristics $\ell\neq p$; i.e,
$R=\operatorname{\mathbb{F}}_{\ell}$. Assume further that $p|\ell-1.$ Then
there exists a constant $C$ depending on $p$ and $G$ such that if $\ell>C$
then $G$ is isomorphic to an induced subgraph of $G_{R}(p).$

###### Proof.

Let $k=|G|.$ The key idea in our proof is to find
$y\in\operatorname{\mathbb{F}}_{\ell}$ and a tuple
$(a_{1},a_{2},\ldots,a_{k})\in\operatorname{\mathbb{Z}}^{k}$ such that the
induced graph on $\\{y^{a_{1}},y^{a_{2}},\ldots,y^{a_{k}}\\}$ is $G$. We can
choose $(a_{1},a_{2},\ldots,a_{k})$ in such a way that $a_{i}-a_{j}$ are
pairwisely different. For example, we can take $a_{i}=2^{i-1}.$ In order to
make sure that the induced graph on
$\\{y^{a_{1}},y^{a_{2}},\ldots,y^{a_{k}}\\}$ is $G$, it is sufficient to find
$y\in\operatorname{\mathbb{F}}_{\ell}$ such that $\chi(y)=1$ and

$\chi(y^{a_{j}-a_{i}}-1)=\begin{cases}1&\text{if }(i,j)\in V(G)\\\ \neq
1&\text{else.}\end{cases}$

Let $S$ be the set of all such $y$. Our goal is to show that $|S|>0$ whenever
$\ell$ is sufficiently large. Similar to the proof of 3.8, we will do so by a
counting argument. Let $C=(c_{ij})$ be the adjacency matrix of $G.$ Define the
following function

$f(x)=P_{1}(\chi(x))\prod_{i<j}P_{c_{ij}}(\chi(x^{a_{j}-a_{i}}-1)).$

Let $T$ be the set of $y$ such that either $y=0$ or $y$ is a root of the
equation $y^{a_{j}-a_{i}}-1$ for some $i<j.$ Then $T$ is a finite set. For
each $x\in\operatorname{\mathbb{F}}_{\ell}$, $0\leq|f(x)|\leq 1.$ Furthermore,
if $x\in\operatorname{\mathbb{F}}_{\ell}\setminus T$, then $f(x)=1$ if $x\in
S$ and $f(x)=0$ otherwise. Therefore, we have

$|S|=|\sum_{y\in\operatorname{\mathbb{F}}_{\ell}}f(y)-\sum_{y\in
T}f(y)|\geq|\sum_{y\in\operatorname{\mathbb{F}}_{\ell}}f(y)|-|T|.$

By the Weil bound, we also have

$|\sum_{y\in\operatorname{\mathbb{F}}_{\ell}}f(y)|\geq\frac{(p-1)^{N}}{p^{{|G|\choose
2}+1}}\ell-C\sqrt{\ell},$

where $N$ is the number of $(i,j)$ such that $i<j$ and $(i,j)\not\in V(G)$ and
$C$ is a constant depending on $G$ and $p$ only. We conclude that

$|S|\geq\frac{(p-1)^{N}}{p^{{|G|\choose 2}+1}}\ell-C\sqrt{\ell}-|T|.$

Therefore, for $\ell$ big enough, $|S|>0.$ In other words, we can find $y$
such that the induced graph on $\\{y^{a_{1}},y^{a_{2}},\ldots,y^{a_{k}}\\}$ is
$G.$ ∎

######  Remark 3.13.

In [1, Theorem 9.1] the authors classify all $G_{R}(1)$ which are perfect. In
particular, they show that the graph $G_{R}(1)$ is always a perfect graph if
$R$ is a finite local ring. However, things are different when $p>1$. In fact,
by 3.12, for each $p$ there exists a constant $C_{p}$ such that if
$\ell>C_{p}$, then the cycle graph $\textbf{C}_{5}$ is an induced subgraph of
$G_{\operatorname{\mathbb{F}}_{\ell}}(p)$. Consequently
$G_{\operatorname{\mathbb{F}}_{\ell}}(p)$ is not perfect.

##  4\.  $G_{R}(p)$ where $p$ is a local ring of residue characteristics $p$

In this section, we study 1.4 and 1.5 in the case $R$ is a local field of
residue characteristics $p.$ We will start our investigation with the
following lemma.

######  Lemma 4.1.

Suppose that $R$ is an $\operatorname{\mathbb{F}}_{p}$-algebra and ${\rm
Cay}(R,(R^{\times})^{p})$ is connected. Then $R$ is a finite field.

###### Proof.

Let $H_{1}$ (respectively $H_{2}$) be the abelian group of generated by
$R^{\times}$ (respectively $(R^{\times})^{p}).$ We claim that

$H_{2}=H_{1}^{p}=\\{a^{p}|a\in H_{1}\\}.$

Let $x$ be an element of $H_{2}$. Then we can write

$x=\sum_{i=1}^{d}n_{i}r_{i}^{p},$

where $n_{i}\in\operatorname{\mathbb{Z}}$ and $r_{i}\in R^{\times}.$ By
Fermat’s little theorem, we know that $n_{i}^{p}=n_{i}$ for all $1\leq i\leq
d.$ Therefore, we can write

$x=\sum_{i=1}^{d}n_{i}^{p}r_{i}^{p}=\left(\sum_{i=1}^{d}n_{i}r_{i}\right)^{p}.$

We conclude that $x\in H_{1}^{p}$. Therefore, $H_{2}\subseteq H_{1}^{p}.$ By a
similar argument can show that $H_{1}^{p}\subseteq H_{2}.$ This shows that
$H_{2}=H_{1}^{p}.$

Now, because ${\rm Cay}(R,(R^{\times})^{p})$ is connected, we must have
$H_{2}=R.$ Consequently $H_{1}^{p}=R$ and hence $R=R^{p}.$ This implies that
the Frobenius map $\Phi:R\to R$ sending $r\mapsto r^{p}$ is an isomorphism.
Since $M$ is nilpotent, we must have $M=0.$ In other words, $R$ is a field. ∎

######  Corollary 4.2.

Let $R$ be a finite local commutative ring such that $k=R/M$ has
characteristics $p.$ Suppose that ${\rm Cay}(R,(R^{\times})^{p})$ is
connected. Then $M=pR$ and $R/pR$ is a finite field.

###### Proof.

Apply 4.1 for the ring $R/p.$ ∎

######  Proposition 4.3.

Let $S$ be a subset of $R$. Then ${\rm Cay}(R,S)$ is connected if and only if
${\rm Cay}(R/p,\varphi(S))$ is. Here $\varphi:R\to R/p$ is the canonical map.

###### Proof.

Let $H$ be the abelian group generated by $S.$ By definition, $\varphi(H)$ is
the abelian group generated by $\varphi(S).$ As a result, if ${\rm Cay}(R,S)$
is connected, then ${\rm Cay}(R/p,\varphi(S))$ is connected as well.

Now, suppose that ${\rm Cay}(R/p,\varphi(S))$ is connected. We then have
$\varphi(H)=R/p$. We claim that $H=R.$ Let $r\in R.$ Because $\varphi(H)=R/p$,
we can find $h_{1}\in H$ such that $\phi(h_{1})=\phi(r).$ This implies that
$r-h_{1}\in\ker(\varphi)=pR.$ Therefore, we can write

$r=h_{1}+pr_{1},$

where $h_{1}\in H$ and $r_{1}\in R.$ Keeping the same process, we see that for
each $n\geq 1,$ we can find $(h_{1},h_{2},\ldots,h_{n})\in H^{n}$ and
$r_{n}\in R$ such that

$r=h_{1}+ph_{2}+\cdots+p^{n-1}h_{n}+p^{n}r_{n}.$

Because $p$ is nilpotent, we can find $n\in\operatorname{\mathbb{N}}$ such
that $p^{n}=0.$ Consequently, in the above equation, we would have

$r=h_{1}+ph_{2}+\cdots+p^{n-1}h_{n}\in H.\qed$

Let $(R,M)$ be a local ring and $\phi:R\to R/M:=k$ be the canonical map.

######  Proposition 4.4.

Let $(R,M)$ be a finite commutative local ring such that $k=R/M$ has
characteristics $p.$ Let $a\in k^{\times}.$ Then

  1. (1)

There exists $x\in R^{\times}$ such that $\phi(x^{p})=a.$

  2. (2)

Suppose that $M=pR$. If $x_{1},x_{2}\in R^{\times}$ such that
$\phi(x_{1}^{p})=\phi(x_{2}^{p})=a$, then $x_{1}^{p}\equiv
x_{2}^{p}\pmod{p^{2}R}.$

###### Proof.

Since $k^{\times}$ is a cyclic of order prime to $p$, we have
$k^{\times}=(k^{\times})^{p}.$ Therefore, we can find $b\in k^{\times}$ such
that $a=b^{p}.$ Let $x$ be any lift of $b$ to $R$; namely $\phi(x)=b$. We then
see that $x\in R^{\times}$ and

$\phi(x^{p})=\phi(x)^{p}=b^{p}=a.$

For the second part, we observe that we have

$0=(\phi(x_{1})^{p}-\phi(x_{2})^{p})=(\phi(x_{1})-\phi(x_{2}))^{p}.$

Because $R/pR$ is a field, we must have $\phi(x_{1})=\phi(x_{2}).$ In other
words, $x_{1}=x_{2}+pa$ for some $a\in R.$ We can then see that
$x_{1}^{p}\equiv x_{2}^{p}\pmod{p^{2}R}$. ∎

######  Corollary 4.5.

Suppose that $M=pR$ and $p^{2}R=0.$ Then, for each $a\in k^{\times}$, there
exists a unique $y\in(R^{\times})^{p}$ such that $\phi(y)=a.$ In other words,
the induced map $\phi:(R^{\times})^{p}\to k^{\times}=(k^{\times})^{p}$ is an
isomorphism.

By 4.3 and 4.4, we have the following.

######  Proposition 4.6.

Let $(R,M)$ be a finite commutative local ring such that $k=R/M$ has
characteristics $p.$ Then ${\rm Cay}(R,(R^{\times})^{p})$ is connected if and
only $M=pR$. Furthermore, in the case $p=2$, ${\rm Cay}(R,(R^{\times})^{p})$
is connected if and only if $M=pR=0$ if and only if $R$ is a field if and only
if $G_{R}(p)\cong K_{|R|}.$

###### Proof.

The forward direction follows from 4.2. Now suppose that $M=pR.$ By 4.3,
$G_{R}(p)$ is connected if and only if $G_{R/p}(p)=G_{k}(p)$ is also connect
where $k=R/M$. Since $k=R/M$ is a finite field of characteristics $p$,
$|k^{\times}|$ is a group with order prime to $p.$ As a result,
$k^{\times}=(k^{\times})^{p}=k\setminus\\{0\\}$ and hence $G_{k}(p)=K_{|k|}$
the complete graph on $|k|$ nodes. In particular, it is connected. We conclude
that $G_{R}(p)$ is connected as well.

Let us consider the case $p=2$. Because $G_{R}(p)$ is connected, by the above
argument, we know that $M=2R$ and $R/M$ is a field of characteristics $p=2.$
We claim that $M=0$. In fact, by our assumption that $G_{R}(2)$ is an
undirected graph, $-1\in(R^{\times})^{2}$; i.e, there exists $x\in R$ such
that $x^{2}=-1.$ Let $\bar{x}\in R/M=R/2R$ be the projection of $x$ to the
residue field of $R$. Then $\bar{x}^{2}=\overline{-1}=\bar{1}.$ Consequently
$(\bar{x}-1)^{2}=0$. Since $R/2R$ is a field, we must have $\bar{x}=1.$ In
other words, we can write $x=1+2a$ for some $a\in R.$ We then have

$0=x^{2}+1=(1+2a)^{2}+1=2(1+2a+2a^{2}).$

Since $1+2a+2a^{2}\in R^{\times}$, we conclude that $2=0$ in $R.$ This shows
that $M=2R=0$ and $R$ is a field of characteristics $2.$ In this case
$R^{\times}=(R^{\times})^{2}=R\setminus\\{0\\}.$ Consequently
$G_{R}(p)=K_{|R|}.$ ∎

######  Corollary 4.7.

$G_{R}(p)$ is a connected bipartite undirected graph if and only if $p=2$ and
$R=\operatorname{\mathbb{F}}_{2}.$

###### Proof.

$G_{R}(p)$ contains the $p$-cycle

$0\to 1\to\cdots\to p-1\to 0.$

Consequently, if $p$ is odd, then $G_{R}(p)$ contains an odd cycle and
therefore it is not bipartite. Let us consider the case $p=2$. By 4.6, we know
that $G_{R}(p)=K_{|R|}$ in this case. Therefore, $G_{R}(p)$ is bipartite if
and only $|R|=2.$ In other words, $R=\operatorname{\mathbb{F}}_{2}.$ ∎

######  Proposition 4.8.

Let $(R,M)$ be a finite commutative local ring such that $k=R/M$ has
characteristics $p.$ Suppose that $G_{R}(p)$ is connected. Then ${\rm
Cay}(R,(R^{\times})^{p})$ is anti-connected if and only if $R$ is not a field.

###### Proof.

If $R$ is a field then $G_{R}(p)=K_{|R|}.$ As a result, the complement of
$G_{R}(p)$ is the empty graph $E_{|R|}$ and hence,$G_{R}(p)$ is not
anticonnected. Conversely, suppose that $R$ is not a field. We claim that
$G_{R}(p)$ is anticonnected. First of all, since $G_{R}(p)$ is connected, 4.3
implies that $M=pR.$ We claim that $\varphi(R\setminus(R^{\times})^{p})=k$
where $k=R/M=R/pR$ and $\varphi\colon R\to R/p$ is the canonical projection
map. Let $\bar{x}\in k^{\times}$. By 4.4, we can find $y\in R^{\times}$ such
that $\varphi(y^{p})=\bar{x}.$ We claim that $y^{p}+a\not\in(R^{\times})^{p}$
for each $a\in pR\setminus p^{2}R.$ We remark that, by definition
$\varphi(y^{p}+a)=\bar{x}$, and $pR\setminus p^{2}R\not=\emptyset$ (if
$pR=p^{2}R$ then $p=p^{2}c$ for some $c\mathrm{i}R$, hence $p=0$ since
$1-pc\in R^{\times}$, a contraction). Suppose to the contrary that
$y^{p}+a=z^{p}$ for some $z\in R.$ Over $R/p$, we then have

$0=\bar{z}^{p}-\bar{y}^{p}=(\bar{z}-\bar{y})^{p}.$

Because $R/p$ is a field, we conclude that $\bar{z}=\bar{y}.$ In other words,
we can write $z=y+pt$ for some $t\in R.$ We then have

$a=z^{p}-y^{p}=(y+pt)^{p}-y^{p}=p^{2}w$

for some $w\in R.$ Because $a\in pR\setminus p^{2}R$, we can write $a=pb$ for
some $b\in R^{\times}$. We then have $p(b-pw)=0$. Because $b-pw\in
R^{\times}$, we conclude that $p=0$ and hence $pR=0.$ This is a contradiction
since we assume that $R$ is not a field. ∎

By 4.6 and 4.8, we have a complete answer to 1.5. We now focus on 1.4. For
this question, we have the following key observation which is discovered
through various experiments with Sagemath.

######  Proposition 4.9.

Let $(R,M)$ be a finite commutative local ring such that $k=R/M$ has
characteristics $p.$ Then $p^{2}R$ is a homogeneous set in ${\rm
Cay}(R,(R^{\times})^{p})$.

###### Proof.

By [7, Proposition 4.4], for $p^{2}R$ to be a homogeneous set in $G_{R}(p)$ we
need to show that

$p^{2}R+(R^{\times})^{p}\subseteq(R^{\times})^{p}.$

Let $x\in(R^{\times})$ and $a\in R$, we claim that
$x^{p}+p^{2}a\in(R^{\times})^{p}.$ From the equation

$x^{p}+p^{2}a=x^{p}(1+p^{2}(ax^{-p})),$

we can assume that $x=1.$ While Hensel’s lemma does not apply directly, we can
modify it to fit our situation. Specifically, we claim that there for each
$n\geq 1$, we can find $x_{n}\in R$ such that

$x_{n}^{p}\equiv 1+p^{2}a\pmod{p^{n+1}}.$

We remark the above congruence immediately implies that $x_{n}\in R^{\times}$.
For $n=1$, we can take $x_{1}=1+ap$. In this case

$x_{1}^{p}=(1+ap)^{p}=1+ap^{2}+\sum_{k=2}^{p}{p\choose k}(ap)^{k}\equiv
1+ap^{2}\pmod{p^{2}}.$

Suppose that the statement has been verified for all $n$. We claim that it is
also true for $n+1.$ In fact, let $x_{n+1}=x_{n}+p^{n}b$ for some $b\in R.$ We
then have

$x_{n+1}^{p}=(x_{n}+p^{n}b)^{p}\equiv x_{n}^{p}+x_{n}^{p-1}p^{n+1}b\equiv
1+p^{2}a+(x_{n}^{p}-1-p^{2}a+x_{n}^{p-1}p^{n+1}b)\pmod{p^{n+2}}.$

By the induction hypothesis, we can write $x_{n}^{p}-1-p^{2}a=p^{n+1}c_{n}$
for some $c_{n}\in R.$ If we take $b=-(x_{n}^{-1})^{p-1}c_{n}$ then

$x_{n+1}^{p}\equiv 1+p^{2}a\pmod{p^{n+2}}.$

Since $p$ is nilpotent in $R$, $p^{n}=0$ for some large enough $n.$ Therefore,
we can find $n$ such that $x_{n}^{p}=1+p^{2}a.$ This shows that
$1+p^{2}a\in(R^{\times})^{p}.$ ∎

By [7, Corollary 4.2] and 4.5, we have the following.

######  Corollary 4.10.

For each $m\geq 1$, we define

$R_{m}=R/p^{m}.$

Then $G_{R}(p)$ is the wreath product of $G_{R_{2}}(p)$ and $E_{n}$ where
$n=|p^{2}R|$; i.e. (see Definition 2.3 for the definition of the wreath
product of two graphs)

$G_{R}(p)\cong G_{R_{2}}(p)\cdot E_{n}.$

Furthermore, $G_{R_{2}}(p)$ is a regular graph of degree $|R_{1}|-1.$

######  Example 4.11.

Figure Fig. 3 shows the graph $G_{\operatorname{\mathbb{Z}}/25}(5).$ It is a
regular graph of degree $4.$

Figure 3. The Cayley graph $G_{\operatorname{\mathbb{Z}}/25}(5)$

We now show that $p^{2}R$, under mild conditions, is the maximal homogeneous
set in $G_{R}(p).$

######  Proposition 4.12.

Let $(R,M)$ be a finite commutative local ring such that $k=R/M$ has
characteristics $p.$ Let $a\in M^{2}\setminus M.$ Then

$(a+(R^{\times})^{p})\cap(R^{\times})^{p}=\emptyset.$

###### Proof.

The key argument for the proof of this proposition is somewhat similar to the
one given in 4.8. For the sake of completeness, we provide it here for the
reader’s convenience. Let us assume to the contrary that
$(a+(R^{\times})^{p})\cap(R^{\times})^{p}\neq\emptyset$. Then we can find
$x,y\in R^{\times}$ such that

$a+x^{p}=y^{p}.$

By projecting this equation over the residue field $R/M$ we see that
$(\bar{x}-\bar{y})^{p}=0.$ Consequently, $\bar{x}=\bar{y}.$ In other words, we
can write $y=x+m$ for some $m\in M.$ We then have

$a=y^{p}-x^{p}=(x+m)^{p}-x^{p}=pm\left(\sum_{k=1}^{p-1}\dfrac{{p\choose
k}}{p}x^{k}m^{p-k-1}\right)+m^{p}\in M^{2}.$

This contradicts our assumption that $a\not\in M^{2}.$ ∎

We have the following corollary.

######  Corollary 4.13.

Suppose that $I$ is a proper ideal in $R$ and $I$ is a homogeneous set in
$G_{R}(p).$ Suppose further that $G_{R}(p)$ is connected. Then $I\subseteq
p^{2}R$. In other words, $p^{2}R$ is the maximal ideal which is also a
homogeneous set in $G_{R}(p).$

###### Proof.

Because $I$ is a homogeneous set, by [7, Proposition 4.4] we know that

$I+(R^{\times})^{p}\subseteq(R^{\times})^{p}.$

By 4.12, we know that for each $a\in I$, $a\in M^{2}.$ Because $G_{R}(p)$ is
connected, by 4.6, we know that $M=pR.$ As a result, $a\in p^{2}R.$ Since this
is true for all $a\in I$, we conclude that $I\subseteq p^{2}R.$ ∎

######  Remark 4.14.

We remark that we do not require $G_{R}(p)$ to be anticonnected in the proof
of 4.13.

######  Theorem 4.15.

Let $(R,M)$ be a finite commutative local ring such that $k=R/M$ has
characteristics $p.$ Then ${\rm Cay}(R,(R^{\times})^{p})$ is a prime graph if
and only if the following conditions hold.

  1. (1)

$R$ is not a field.

  2. (2)

$M=pR$.

  3. (3)

$p^{2}R=0.$

###### Proof.

First, let us assume that $G_{R}(p)$ is a prime graph. Then $G_{R}(p)$ must be
connected and anticonnected. By 4.6, and 4.8 we conclude that $M=pR$ and $R$
is not a field. Furthermore, by 4.9, $p^{2}R$ is a homogeneous set in
$G_{R}(p).$ Because $G_{R}(p)$ is prime, we must have $p^{2}R=0.$

Conversely, suppose that the three conditions above are satisfied. We claim
that $G_{R}(p)$ is prime. First, 4.6, and 4.8 shows that $G_{R}(p)$ is
connected and anticonnected. Suppose that $G_{R}(p)$ is not prime. By 2.6, we
know that there exists a proper ideal $I$ in $R$ such that $I\neq 0$ and $I$
is a homogeneous set in $G_{R}(p).$ By 4.13, we know that $I\subseteq p^{2}R.$
By our assumption $p^{2}R=0$ and therefore $I=0.$ This is a contradiction. We
conclude that $G_{R}(p)$ is a prime graph. ∎

######  Remark 4.16.

A particular example of rings that satisfy the conditions of 4.15 is the class
of Galois rings (see [4, Section 6.1])

$R=GR(p^{2},r)=\operatorname{\mathbb{Z}}[x]/(p^{2},f(x)),$

where $f(x)\in\operatorname{\mathbb{Z}}[x]$ is an irreducible polynomial
modulo $p.$

######  Remark 4.17.

In general, a ring that satisfies the conditions of 4.15 must be a quotient
ring of the Laurent series over a Cohen ring (see [21, Theorem 10.160.8]).

###  4.1. Induced subgraphs of $G_{R}(p)$

In Section 3.2 we study various induced subgraphs of $G_{R}(p)$ where $R$ is a
field of characteristics $\ell\neq p.$ In this section, we study a similar
problem for $G_{R}(p)$ where $R$ is a local ring of residue characteristics
$p.$ Since our main interest lies in the case $G_{R}(p)$ is connected, we will
make that assumption throughout this section. By 4.3, this would imply that
$M=pR.$ Furthermore, in the case $p=2$, $G_{R}(p)=K_{|R|}$ and hence our
problem is rather trivial in this case. Therefore, we will also assume that
$p\geq 3.$

######  Lemma 4.18.

The following conditions are equivalent.

  1. (1)

$K_{3}$ is an induced subgraph of $G_{R}(p).$

  2. (2)

There exists $a\in R^{\times}$ such that the induced subgraph on
$\\{0,1,-a^{p}\\}$ is $K_{3}.$ In other words, there exists $a\in R^{\times}$
such that $1+a^{p}\in(R^{\times})^{p}.$

###### Proof.

Clearly $(2)$ implies $(1)$. Let us show that $(1)$ implies $(2)$ as well. By
assumption, there exists $u_{1},u_{2},u_{3}\in R$ such that the induced graph
on $\\{u_{1},u_{2},u_{3}\\}$ is $K_{3}.$ By definition,
$u_{2}-u_{1}\in(R^{\times})^{p}$ and $u_{1}-u_{3}\in(R^{\times})^{p}$. Hence
there exists $a\in R^{\times}$ such that
$a=\left(\dfrac{u_{1}-u_{3}}{u_{2}-u_{1}}\right)^{p}$. We can then see that
the induced subgraph on

$\left\\{\frac{u_{1}-u_{1}}{u_{2}-u_{1}},\frac{u_{2}-u_{1}}{u_{2}-u_{1}},\frac{u_{3}-u_{1}}{u_{2}-u_{1}}\right\\}=\left\\{0,1,\frac{u_{3}-u_{1}}{u_{2}-u_{1}}\right\\}=\left\\{0,1,-a^{p}\right\\}$

is also $K_{3}.$ ∎

Inspired by 4.18, we define the following polynomial

$f_{p}(x)=(1+x)^{p}-x^{p}-1\in\operatorname{\mathbb{Z}}[x].$

The introduction of $f_{p}(x)$ is suggested to us by Dr. Ha Duy Hung. We thank
him for sharing this idea.

######  Example 4.19.

Here are some examples of $f_{p}(x)$ for small $p.$

$f_{3}(x)=3x(x+1).$ $f_{5}(x)=5x(x+1)(x^{2}+x+1),$
$f_{7}(x)=7x(x+1)(x^{2}+x+1)^{2},$
$f_{11}(x)=11x(x+1)(x^{2}+x+1)(x^{6}+3x^{5}+7x^{4}+9x^{3}+7x^{2}+3x+1).$

######  Proposition 4.20.

$K_{3}$ is an induced subgraph of $G_{R}(p)$ if and only there exists $a\in
R^{\times}$ such that $a+1\in R^{\times}$ and $f_{p}(a)=0.$

###### Proof.

If $a\in R^{\times}$ such that $1+a\in R^{\times}$ and $f_{p}(a)=0$ then the
induced graph on $\\{0,1,-a^{p}\\}$ is $K_{3}.$ Converesly, suppose that
$K_{3}$ is an induced subgraph of $G_{R}(p).$ By 4.18, we can find $a\in
R^{\times}$ such that

$1+a^{p}=b^{p},$

for some $b\in R^{\times}.$ By 4.10,we can assume that $p^{2}R=0$. By taking
this equation over $R/pR$, we conclude that $b\equiv 1+a\pmod{p}.$
Consequently

$b^{p}\equiv(1+a)^{p}\pmod{p^{2}R}.$

Since $p^{2}R=0$, we conclude that $b^{p}=(1+a)^{p}$ and that $f_{p}(a)=0.$ We
remark that since $b\equiv 1+a\pmod{pR}$ and $b\in R^{\times}$, $1+a\in
R^{\times}$ as well. ∎

Let us next discuss a particular factor of $f_{p}(x).$

######  Lemma 4.21.

Suppose that $p>3.$ Let $m$ be the multiplicity of $x^{2}+x+1$ in $f_{p}(x).$
Then

$m=\begin{cases}1&\text{if }p\equiv 2\pmod{3}\\\ 2&\text{else.}\end{cases}$

###### Proof.

Let $\zeta_{3}$ be a primitive $3$-root of unity. Then the minimal polynomial
of $\zeta_{3}$ is $\Phi_{3}(x)=x^{2}+x+1$ and $m$ is the multiplicity of
$\zeta_{3}$ in $f_{p}(x).$ Therefore, in order to calculate $m$, we need to
study $f_{p}^{(k)}(\zeta_{3})$ for $k\geq 0.$ First, we observe that

$\zeta_{3}+1=-\zeta_{3}^{2}.$

Consequently

$f_{p}(\zeta_{3})=(-\zeta_{3}^{2})^{p}-\zeta_{3}-1=-(\zeta_{3}^{2p}+\zeta_{3}^{p}+1)=\zeta_{3}^{2}+\zeta_{3}+1=0.$

Similarly, we have

$f_{p}^{\prime}(\zeta_{3})=p[(-\zeta_{3}^{2})^{p-1}-\zeta_{3}^{p-1}]=p\zeta_{3}^{p-1}(\zeta_{3}^{p-1}-1).$

We can see that $f_{p}^{\prime}(\zeta_{3})=0$ if and only if $p\equiv
1\pmod{3}.$ Finally, assume now that $p\equiv 1\pmod{3}$ then

$f_{p}^{\prime\prime}(\zeta_{3})=p(p-1)[(-\zeta_{3}^{2})^{p-2}-\zeta_{3}^{p-2}]=p(p-1)\neq
0.\qed$

######  Corollary 4.22.

Suppose that $p>3$. There exists a polynomial
$g_{p}(x)\in\operatorname{\mathbb{Z}}[x]$ such that

$f_{p}(x)=px(x+1)(x^{2}+x+1)^{m}g_{p}(x),$

with $g(\zeta_{3})\neq 0.$ Here

$m=\begin{cases}1&\text{if }p\equiv 2\pmod{3}\\\ 2&\text{if }p\equiv
1\pmod{3}.\end{cases}$

######  Remark 4.23.

We have verified that $g_{p}(x)$ is irreducible for all $p<10^{4}.$ We wonder
whether this is the case for all $p$.

We have the following partial observation.

######  Lemma 4.24.

If $a\in\operatorname{\mathbb{C}}$ is a repeated root of $f_{p}(x)$, then
$a^{2}+a+1=0.$ Consequently, $g_{p}(x)$ is separable over
$\operatorname{\mathbb{Z}}[x].$

###### Proof.

Because $a$ is a repeated root of $f_{p}(x)$, we have
$f_{p}(a)=f_{p}^{\prime}(a)=0.$ We have

$0=f_{p}^{\prime}(a)=p\left((a+1)^{p-1}-a^{p-1}\right)=0.$

There exists $\lambda\in\operatorname{\mathbb{C}}$ such that $\lambda^{p-1}=1$
and $a+1=\lambda a.$ We then see that $a=\frac{1}{\lambda-1}.$ Substituting
this into the equation $f_{p}(a)=0$, we have

$\left(\frac{\lambda}{\lambda-1}\right)^{p}-\left(\frac{1}{\lambda-1}\right)^{p}-1=0.$

Using the fact that $\lambda^{p-1}=1$, we see that

$0=\lambda^{p}-(\lambda-1)^{p}-1=\lambda-(\lambda-1)^{p}-1=(\lambda-1)(1-(\lambda-1)^{p-1}).$

We conclude that $(\lambda-1)^{p-1}=\lambda^{p-1}=1.$ We can find $0\leq
k,l\leq p-1$ such that

$\lambda=e^{\frac{2k}{p-1}i}=\cos\left(\frac{2k}{p-1}\right)+i\sin\left(\frac{2k}{p-1}\right),$
$\lambda-1=e^{\frac{2l}{p-1}i}=\cos\left(\frac{2l}{p-1}\right)+i\sin\left(\frac{2l}{p-1}\right).$

We conclude that

$\sin\left(\frac{2k}{p-1}\right)=\sin\left(\frac{2l}{p-1}\right),\cos\left(\frac{2k}{p-1}\right)=1+\cos\left(\frac{2l}{p-1}\right).$

From this, we can see that

$\cos\left(\frac{2k}{p-1}\right)=\frac{1}{2},\cos\left(\frac{2l}{p-1}\right)=-\frac{1}{2}.$

We conclude either $\lambda=\frac{1+\sqrt{3}i}{2}$ or
$\lambda=\frac{1-\sqrt{3}i}{2}.$ We then have $a=\pm\zeta_{3}$; i.e,
$a^{2}+a+1=0.$ By 4.22, $g_{p}(a)\neq 0$. We conclude that $g_{p}(x)$ has no
repeated roots. ∎

We now show that there is an analogous statement over
$\operatorname{\mathbb{F}}_{p}[x].$

######  Proposition 4.25.

Let
$h_{p}(x)=\dfrac{1}{p}f_{p}(x)=(x^{2}+x+1)^{m}g_{p}(x)\in\operatorname{\mathbb{Z}}[x]$
where $m$ is given in 4.21. The following conditions are equivalent.

  1. (1)

$a\in\bar{\operatorname{\mathbb{F}}}_{p}$ is a repeated root of $h_{p}(x)$.

  2. (2)

$a$ is a root of $h_{p}(x)$ and
$a\in\operatorname{\mathbb{F}}_{p}\setminus\\{0,-1\\}$.

Furthermore, in this case, the multiplicity of $a$ is exactly $2.$

###### Proof.

Clearly $h^{\prime}_{p}(x)=(x+1)^{p-1}-x^{p-1}$. Suppose that $h_{p}$ has a
root $a\in\operatorname{\mathbb{F}}_{p}\setminus\\{0,-1\\}$. Then
$h^{\prime}_{p}(a)=(a+1)^{p-1}-a^{p-1}=1-1=0$.

Now we suppose that $h_{p}$ has a multiple root
$a\in\bar{\operatorname{\mathbb{F}}}_{p}$. From
$0=h^{\prime}_{p}(a)=(a+1)^{p-1}-a^{p-1}$, we see that $a\not=0$, $a\not=-1$
and $\left(\dfrac{a+1}{a}\right)^{p-1}=1$. Hence
$\lambda:=\dfrac{a+1}{a}\in\operatorname{\mathbb{F}}_{p}$ and thus
$a=\dfrac{1}{\lambda-1}\in\operatorname{\mathbb{F}}_{p}$.

Finally, we note that

$h_{p}^{\prime\prime}(a)=(p-1)\left((a+1)^{p-2}-a^{p-2})\right)=(p-1)\left(\frac{1}{a+1}-\frac{1}{a}\right)=-\frac{p-1}{a(a+1)}\neq
0.$

Therefore, the multiplicity of $a$ is $2.$ ∎

######  Proposition 4.26.

Suppose that $p\equiv 1\pmod{3}$. Then $K_{3}$ is an induced subgraph of
$G_{R}(p).$

###### Proof.

Let $k=R/pR$, the residue field of $R.$ Since $p\equiv 1\pmod{3}$,
$k^{\times}$ is a cyclic group of order divisible by $3.$ Consequently, we can
find $a_{0}\in k^{\times}$ such that $a_{0}\neq 1$ and $a_{0}^{3}=1.$ In other
words, $a_{0}^{2}+a_{0}+1=0.$ By Hensel’s lemma, we can lift $a_{0}$ to a root
$a\in R$; namely $a^{2}+a+1=0$ and $\bar{a}=a_{0}$ where $\bar{x}$ is the
projection of $x$ to $k.$ We remark that since $1+\bar{a}=1+a_{0}\neq 0$,
$1+a\in R^{\times}.$ Furthermore, by 4.21 we have $f_{p}(a)=0$. By 4.20, we
conclude that the induced graph on $\\{0,1,-a^{p}\\}$ is $K_{3}.$ ∎

######  Remark 4.27.

The converse of 4.26 is not true. The smallest counterexample is $p=59.$ In
this case, we can check that $a=4$ is a solution of $g_{p}(x)=0$ over
$\operatorname{\mathbb{Z}}/p$ and hence of $f_{p}(x)=0$ over
$\operatorname{\mathbb{Z}}/p^{2}.$ For prime $p<500$, $g_{p}(x)$ has a root in
$\operatorname{\mathbb{F}}_{p}$ if and only if
$p\in\\{59,79,83,179,193,227,337,419,421,443,457\\}.$ It seems that there
exists infinitely many $p$ such that $g_{p}(x)$ has a root in
$\operatorname{\mathbb{F}}_{p}.$

##  5\. The general case

In Section 3 and Section 4, we provide complete answers for 1.5 and 1.4. In
this section, we study these questions in the general case; namely

(5.1) $R=\prod_{i=1}^{d}R_{i}.$

where $R_{i}$’s are finite local rings whose maximal ideals are $M_{i}$’s. For
the rest of this section, we will fix the decomposition given in Eq. 5.1. With
this decomposition, we have an isomorphism

$G_{R}(p)\cong G_{R_{1}}(p)\times G_{R_{2}}(p)\times\cdots\times
G_{R_{d}}(p).$

We first deal with 1.5. By Weichsel’s Theorem (see [10, Theorem 5.9 and
Corollary 5.10], we have the following.

######  Proposition 5.1.

$G_{R}(p)$ is connected if and only if the following conditions hold

  1. (1)

$G_{R_{i}}(p)$ is connected for each $1\leq i\leq d$,

  2. (2)

At most one of the $G_{R_{i}}(p)$ is a bipartite graph.

When $R$ is a local ring, via 3.3 (for the case $p\in R^{\times}$) and 4.6
(for the case $p\not\in R^{\times}$) we provide the explicit conditions for
$G_{R}(p)$ to be connected. In this case, we also provide some sufficient
conditions for $G_{R}(p)$ to be non-bipartite (see 3.10 and 4.7). For the
general case, we have the following observation.

######  Proposition 5.2.

Suppose that $G_{1},G_{2}$ are graphs.Then the directed product $G_{1}\times
G_{2}$ is always anti-connected.

###### Proof.

Let $(u_{1},u_{2})$ and $(v_{1},v_{2})$ be two vertices in $G_{1}\times
G_{2}.$ Then we have the following path in $(G_{1}\times G_{2})^{c}$

$(u_{1},u_{2})\to(u_{1},v_{2})\to(u_{2},v_{2}).$

∎

######  Corollary 5.3.

Suppose that $d\geq 2$. Then $G_{R}(p)$ is anticonnected.

We now return to 1.4. Under the decomposition $R=\prod_{i=1}^{d}R_{i}$, we
know that each ideal $I$ is $R$ is of the form

$I=I_{1}\times I_{2}\times\cdots\times I_{d},$

where $I_{i}$ is an ideal in $R_{i}$ for each $1\leq i\leq d.$ We have the
following lemma.

######  Lemma 5.4.

Suppose that $I=I_{1}\times I_{2}\times\cdots\times I_{d}$ is a proper ideal
in $R$; i.e., $I\neq R.$ Then $I$ is a homogeneous set in $R$ if and only if
the following conditions hold

  1. (1)

$I_{i}$ is a homogeneous set in $R_{i}$ for each $1\leq i\leq d$,

  2. (2)

$I_{i}\neq R_{i}$ for each $1\leq i\leq d.$

###### Proof.

This statement follows from the fact that $I$ is a homogeneous set in $R$ if
and only if

$I+(R^{\times})^{p}\subseteq(R^{\times})^{p}.$

Under the decomposition given in Eq. 5.1 this is equivalent to

$I_{i}+(R_{i}^{\times})^{p}\subseteq(R^{\times})^{p},\forall 1\leq i\leq d.$

This condition is equivalent to the conditions $(1)+(2)$ above. ∎

######  Theorem 5.5.

Suppose that $d\geq 2$. $G_{R}(p)$ is prime if and only if the following
conditions hold

  1. (1)

$G_{R_{i}}(p)$ is a connected graph for each $1\leq i\leq d$,

  2. (2)

$G_{R}(p)$ is connected,

  3. (3)

If $p$ is invertible in $R_{i}$ then $R_{i}$ is a field,

  4. (4)

If $p$ is not invertible in $R_{i}$ then $M_{i}=pR_{i}$ and $p^{2}R_{i}=0$.
Here $M_{i}$ is the maximal ideal in $R_{i}.$

###### Proof.

Suppose that $G_{R}(p)$ is prime. Then $(1),(2)$ hold. We note that if $p$ is
not invertible in $R$ and $G_{R_{i}}(p)$ is connected, we must have
$M_{i}=pR_{i}$ (by 4.2). For each $1\leq i\leq d$, we define

$J_{i}=\begin{cases}M_{i}&\text{if $p\in R_{i}^{\times}$}\\\
p^{2}M_{i}&\text{else.}\end{cases}$

Then $J=\prod_{i=1}^{d}J_{i}$ is a homogeneous set in $G_{R}(p)$. Because
$G_{R}(p)$ is prime, we must have $J=0$ or equivalently $J_{i}=0$ for each
$1\leq i\leq d.$

Conversely, suppose that all conditions are satisfied. We claim that
$G_{R}(p)$ is prime. Suppose to the contrary that $G_{R}(p)$ is not prime. By
5.3, we know that $G_{R}(p)$ is also anticonnected. By [7, Theorem 4.1], there
exists a non-zero proper ideal $I$ in $R$ such that $I$ is a homogeneous set
in $R.$ Let us write $I=\prod_{i=1}^{d}I_{i}$. By 5.4, we know that each
$I_{i}$ is a homogeneous set in $R_{i}.$ By the definition of $J_{i}$ together
with 4.13, we know that $I_{i}\subseteq J_{i}$ for each $1\leq i\leq d.$ By
our assumption, we must have $I_{i}=\\{0\\}$ and hence $I=0.$ This is a
contradiction. ∎

######  Remark 5.6.

We note that condition $(1)$ is described explicitly in 3.3 (for the case
$p\in R_{i}^{\times})$ and in 4.6 (for the case $p\not\in R^{\times}.)$

We provide some partial results where the conditions in 5.5 can be described
more explicitly. First, by Weichsel’s theorem 5.1 and the fact that
$G_{R_{i}}(p)$ is not bipartite if $2\in R_{i}^{\times}$ (see 3.10) we have
the following.

######  Proposition 5.7.

Suppose that there exists at most one $i$ such that $2\not\in R_{i}^{\times}.$
Then $G_{R}(p)$ is connected if and only $G_{R_{i}}(p)$ is connected for all
$1\leq i\leq d.$

When $p=2$, we have the following.

######  Theorem 5.8.

Suppose that $d\geq 2.$ Then $G_{R}(2)$ is prime if and only if the following
conditions hold.

  1. (1)

There exists at most one $1\leq i\leq d$ such that
$R_{i}=\operatorname{\mathbb{F}}_{2}$.

  2. (2)

If $2$ is not invertible in $R_{i}$ then $R_{i}$ is a field of characteristics
$2.$

  3. (3)

If $2$ is invertible in $R_{i}$ then $R_{i}$ is a field of characteristics
$\ell\neq 2.$

###### Proof.

The necessary conditions follow from 5.5. We now show that they are sufficient
as well. If $2$ is invertible in $R_{i}$ then $G_{R_{i}}(2)$ is connected and
not bipartite by 4.2 and 3.10. On the other hand, if $2$ is not invertible in
$R_{i}$ then $G_{R_{i}}(2)\cong K_{|R_{i}|}$ by 4.6. In particular, it is
bipartite if and only $|R_{i}|=2.$ We can then see that under the above
conditions, all conditions mentioned in 5.5 are satisfied. Therefore,
$G_{R}(p)$ is prime. ∎

## Acknowledgements

We thank Dr. Ha Duy Hung for some correspondences around the arithmetics of
the polynomial $f_{p}.$

## References

  * [1] Reza Akhtar, Megan Boggess, Tiffany Jackson-Henderson, Isidora Jiménez, Rachel Karpman, Amanda Kinzel, and Dan Pritikin, _On the unitary Cayley graph of a finite ring_ , Electron. J. Combin. 16 (2009), no. 1, Research Paper 117, 13 pages.
  * [2] WEIL André, _Sur les courbes algébriques et les variétés qui s’ en déduisent_ , no. 1041, Actualités Sci. Ind, 1948.
  * [3] Milan Bašić and Aleksandar Ilić, _Polynomials of unitary Cayley graphs_ , Filomat 29 (2015), no. 9, 2079–2086.
  * [4] Gilberto Bini and Flaminio Flamini, _Finite commutative rings and their applications_ , vol. 680, Springer Science & Business Media, 2012.
  * [5] Stefano Boccaletti, Ginestra Bianconi, Regino Criado, Charo I Del Genio, Jesús Gómez-Gardenes, Miguel Romance, Irene Sendina-Nadal, Zhen Wang, and Massimiliano Zanin, _The structure and dynamics of multilayer networks_ , Physics reports 544 (2014), no. 1, 1–122.
  * [6] Béla Bollobás and Andrew Thomason, _Graphs which contain all small graphs_ , European Journal of Combinatorics 2 (1981), no. 1, 13–15.
  * [7] Maria Chudnovsky, Michal Cizek, Logan Crew, Ján Mináč, Tung T Nguyen, Sophie Spirkl, and Nguyên Duy Tân, _On prime Cayley graphs_ , arXiv preprint arXiv:2401.06062 (2024).
  * [8] Stephen D Cohen, _Clique numbers of graphs_ , Quaestiones Mathematicae 11 (1988), no. 2, 225–231.
  * [9] Dina Ghinelli and Jennifer D Key, _Codes from incidence matrices and line graphs of Paley graphs_ , Advances in Mathematics of Communications 5 (2011), no. 1, 93.
  * [10] Richard Hammack, Wilfried Imrich, and Sandi Klavžar, _Handbook of product graphs_ , CRC press, 2011.
  * [11] Priya B Jain, Tung T Nguyen, Ján Mináč, Lyle E Muller, and Roberto C Budzinski, _Composed solutions of synchronized patterns in multiplex networks of kuramoto oscillators_ , Chaos: An Interdisciplinary Journal of Nonlinear Science 33 (2023), no. 10.
  * [12] Jérôme Javelle, _Cryptographie quantique: Protocoles et graphes_ , Ph.D. thesis, Université de Grenoble, 2014.
  * [13] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, _Multilayer networks_ , Journal of Complex Networks 2 (2014), no. 3, 203–271.
  * [14] Walter Klotz and Torsten Sander, _Some properties of unitary Cayley graphs_ , The electronic journal of combinatorics (2007), R45–R45.
  * [15] Christian Mauduit and András Sárközy, _On finite pseudorandom binary sequences i: Measure of pseudorandomness, the legendre symbol_ , Acta Arithmetica 82 (1997), no. 4, 365–377.
  * [16] Ján Mináč, Lyle Muller, Tung T Nguyen, and Nguyen Duy Tân, _On the graph of a quadratic character_ , To appear in Mathematica Slovaca (2023).
  * [17] Tung T Nguyen, Roberto C Budzinski, Federico W Pasini, Robin Delabays, Ján Mináč, and Lyle E Muller, _Broadcasting solutions on networked systems of phase oscillators_ , Chaos, Solitons & Fractals 168 (2023), 113166.
  * [18] Ricardo A Podestá and Denis E Videla, _Spectral properties of generalized Paley graphs and their associated irreducible cyclic codes_ , arXiv preprint arXiv:1908.08097 (2019).
  * [19] by same author, _The waring’s problem over finite fields through generalized Paley graphs_ , Discrete Mathematics 344 (2021), no. 5, 112324.
  * [20] by same author, _Waring numbers over finite commutative local rings_ , Discrete Mathematics 346 (2023), no. 10, 113567.
  * [21] The Stacks project authors, _The stacks project_ , https://stacks.math.columbia.edu/tag/04GE, 2024.
  * [22] Huadong Su, _On the diameter of unitary cayley graphs of rings_ , Canadian Mathematical Bulletin 59 (2016), no. 3, 652–660.