Beyond 5G RIS mmWave Systems: Where Communication and Localization Meet

Jiguang He, Member, IEEE,
Fan Jiang, Member, IEEE,
Kamran Keykhosravi, Member, IEEE,
Joonas Kokkoniemi, Member, IEEE,
Henk Wymeersch, Senior Member, IEEE,
and Markku Juntti, Fellow, IEEE
J. He, J. Kokkoniemi, and M. Juntti are with Centre for Wireless Communications, FI-90014, University of Oulu, Finland (E-mail: firstname.lastname@oulu.fi).
F. Jiang, K. Keykhosravi, and H. Wymeersch are with Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden (E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>henkw@chalmers.se).
This work is supported by Horizon 2020, European Union's Framework Programme for Research and Innovation, under grant agreement no. 871464 (ARIADNE). This work is also partially supported by the Academy of Finland 6Genesis Flagship (grant 318927), the Swedish Research Council (grant no. 2018-03701), and the EU H2020 RISE-6G project.

Upcoming beyond fifth generation (5G) communications systems aim at further enhancing  key performance indicators and fully supporting brand new use cases by embracing emerging techniques, e.g., reconfigurable intelligent surface (RIS), integrated communication, localization, and sensing, and mmWave/THz communications. The wireless intelligence empowered by state-of-the-art artificial intelligence techniques has been widely considered at the transceivers, and now the paradigm is deemed to be shifted to the smart control of radio propagation environment by virtue of RISs. In this article, we argue that to harness the full potential of RISs, localization and communication must be tightly coupled. This is in sharp contrast to 5G and earlier generations, where localization was a minor additional service. To support this, we first introduce the fundamentals of RIS mmWave channel modeling, followed by RIS channel state information acquisition and link establishment. Then, we deal with the connection between localization and communications, from a separate and joint perspective.

Channel modeling, millimeter wave, simultaneous localization and communications, radio localization, reconfigurable intelligent surface.

§ INTRODUCTION

As the demand on the quality of services (QoSs) keeps rapidly growing,  upcoming beyond fifth generation (B5G) systems are envisioned to meet more stringent requirements, which are beyond those enabled by the ultra-reliable low-latency communication (URLLC), enhanced mobile broadband (eMBB), and massive machine-type communications (mMTC) in the current 5G system. In addition, B5G will also need to support diverse industry vertical applications, e.g., autonomous driving and industry 4.0. Hence, more challenges are brought on physical layer (PHY) transmissions, multi-access, network design, and resource management technologies. A plethora of disruptive techniques, e.g., holographic multiple-input multiple-output (MIMO), reconfigurable intelligent surface (RIS), artificial intelligence (AI) enabled communications and networking, and simultaneous localization and communications (SLAC), are under active investigation to fulfil the targeted QoS requirements for  B5G <cit.>.

In order to push data rates, interests towards high-frequency bands, e.g., millimeter wave (mmWave) and even THz, keep increasing <cit.>. At these frequencies, the transceivers need to be equipped with a large array of antennas, often called as massive MIMO (mMIMO), to compensate for severe free-space path loss through substantial beamforming gains. Due to the usage of high-resolution analog-to-digital converters (ADCs), a vast amount of power is consumed <cit.>. When the direct path between transmitter and receiver is blocked, received power drops drastically, adversely affecting QoS. Hence, there is a need for a low-power technology that can overcome link blockages.

The introduction of RIS to perform analog beamforming towards dedicated users <cit.> aims to address this need. An RIS is a surface or often a thin covering of a surface with controllable electromagnetic properties. The impedance values of the RIS elements can be controlled so that it realizes an array of phase shifters, thereby modifying the reflection properties and redirecting the impinging wave. Other possible ways to realize  smart surfaces are by metasurfaces, groups of strongly coupled meta-atoms, and holographic surfaces <cit.>. In addition to reflection, an RIS also has other operational functionalities, e.g., diffraction, refraction, polarization, and absorption, which together makes the intelligent control of wireless propagation channels feasible with enhanced spectral efficiency (SE), energy efficiency (EE), security, and network coverage <cit.>.

RISs have several characteristics that distinguish them from typical analog arrays. For instance, RISs usually possess a large aperture and a massive number of elements, so the users are likely in the near field. Also, mutual coupling exists among the RIS elements when sub-half-wavelength inter-element spacing is considered <cit.>.
To keep the cost down, a passive RIS (with no radio frequency (RF) chains) is usually made of inexpensive components with severe hardware limitations. Hence, when combined with high channel losses and many channel coefficients to be estimated,
channel estimation (CE) becomes extremely challenging, and may lead to prohibitive training overhead. On the other hand, directional high-gain antennas and a small number of multipath components lead to a sparse geometric channel with lower delay spread and higher coherence bandwidth, which should be exploited during CE.
Due to the low-rate change of the geometric parameters (user location and orientation), it becomes natural and necessary to harness location information to reduce CE overheads and predict link blockages. Furthermore, an RIS provides a low-cost means to localize users as it is an additional location reference that enables time and angle measurements <cit.>. Hence, the RIS itself provides the localization solution to solve the communication challenges.
Two exemplary scenarios are unmanned aerial vehicle (UAV) and autonomous driving systems, depicted in Fig. <ref>, where data transfer between the base station (BS) and mobile station (MS) and radio localization can be simultaneously enabled by RISs.
While there have been a large number of magazines and technical papers on the benefits of RIS for communication and localization separately, their intimate connection via SLAC has been largely ignored.

Typical applications for SLAC with RISs. A UAV serves as a mobile location reference and high-gain communication relay, which is configured to meet the MS's SLAC requirements. When the LoS is blocked, the RIS can be reconfigured to provide a strong backup path to the MS. Different from previous generations, localization and communication will reinforce each other, rather than compete for resources.

In this article, we provide an overview of the key research directions closely related to the realization of SLAC in
RIS mmWave systems: RIS channel modeling and parameter estimation,

and RIS-aided localization and communications. We first briefly review the salient properties of RIS channels and then describe different approaches to CE  (based on compressive sensing (CS) and data-driven deep learning (DL)).

Then, in contrast to the majority of the reported works on energy- and spectrum-efficient RIS-aided communications, we specially focus on the connection between localization and communications, as well as SLAC with RISs.

§ RIS CHANNELS:  MODELING AND ESTIMATION

In this section, we give an overview of the high frequency channel modeling of RISs, as well as the related challenges. Then, we show how to exploit the sparse and geometric nature of the channel when establishing links for communications and localization.

§.§ RIS mmWave Channel Modeling

Compared to low frequency systems, the mmWave and THz band channels tend to be simpler, but suffer more from non-line-of-sight (NLoS) propagation losses and hardware challenges (phase noise, nonlinearity) <cit.>.
The simplicity of the mmWave channel is due to small number of multipath components, in the addition to the  line-of-sight (LoS) path

With ongoing development  of mmWave and THz, spatio-temporal channel models comprising angle of arrival (AoA), angle of departure (AoD),  time-of-arrival (ToA), delay spread, and distribution of the NLoS paths, the signal processing techniques can be adapted to sparse channel conditions.

An illustration of an RIS system model with BS and MS antenna arrays and some LoS, NLoS, and RIS-aided channels, as well as AoA and AoD ranges of all possible paths. A control channel (CC) is established between the BS and RIS.

RISs have mainly gained interest as a means to overcome the large losses at high frequencies by controlling the radio propagation environment

<cit.>. Similarly, under optimized phase control, they can provide additional measurements of AoA, AoD, ToA, independent of the uncontrolled multipath, thus enabling or boosting localization and sensing capabilities <cit.>.
An illustration of a system with an RIS is given in Fig. <ref> with some of the components affecting the BS-MS MIMO channel matrix. These include amplitude and phase control at the BS/MS, the gains of the BS and MS antennas, RIS phase control matrix, and LoS, NLoS and RIS paths.

The RIS channels are modeled as compound channel between BS-RIS and RIS-MS with the phase control at the RIS. The channel models of the compound link depend on the environment, mobility of users and other network elements, and the frequency band. The phase control at RIS modifies the behavior of the compound link to maximize the channel gains. The RIS phase control depends on various aspects, but predominantly the type of the RIS itself and its limitations (element spacing, element gains, phase shifter resolutions, etc.). As a low-cost RIS will be HW-limited, each of these limitations must be carefully modeled. For instance, realistic models for mutual coupling are needed when RIS elements are spaced less than half a wavelength apart. An additional modeling challenge stems from the large aperture of the RIS, which pushes the far field of the array far away from radiation source, leading to wavefront curvature.
This near field region can be handled with beamforming algorithms via CE, but may result in decreased channel gains compared to far field operation.

There are many different types of RISs whose physical properties have impact on the control algorithms. The two most common in literature are phased reflective arrays and metasurface-based RISs <cit.>. The most commonly utilized RIS models in literature are phased reflective arrays as those allow easy way to model and modulate the phase shifts, and subsequently, the beamforming at the RIS.

In summary, the RIS channel models can be composed by combining the conventional static and mobile channel models with specific RIS hardware models and RIS control algorithms. There are many research challenges ahead to physically and algorithmically understand the behavior of the RISs and channels with RISs, how to estimate the channel, how to steer beams efficiently, and ultimately, how to simultaneously maximize the communication and localization performance.

§.§ RIS Channel Estimation

RISs possess several fundamental limitations that affect CE capabilities: (1) a large number of elements but no RF chains; (2) low computational power and small storage space; (3) severe hardware issues such as phase quantization and mutual coupling. All these properties should be taken into consideration when designing and developing efficient yet effective RIS-aided communication and localization protocols.  A systematic framework is sketched in Fig. <ref>, containing three approaches: pilot-based  approaches relying on CS <cit.>, blind beam alignment, and data-driven approaches. These are described now in detail.

A systematic framework for CS-aided RIS CE, RIS beam alignment, and DNN based data-driven approaches for RIS joint active and passive beamforming, channel parameters extraction, and even MS localization. The beam training matrix design is also of great importance for the above tasks, and can be enhanced by prior location information on MS and environmental objects. As for different SLAC objectives, a variety of loss functions can be considered accordingly.

§.§.§ RIS Channel Estimation via Compressive Sensing

In order to achieve the optimal or sub-optimal joint active and passive beamforming, it is essential to get an accurate channel state information (CSI) of all the individual channels or parameters therein. As discussed earlier, there exists inherent sparsity in the mmWave MIMO channels, benefiting from the poor scattering propagation environment, which can be leveraged in the CE algorithm development via advanced CS techniques, e.g., approximate message passing (AMP) and off-the-grid atomic norm minimization (ANM) <cit.>. However, for the purely passive RIS architecture without any connected baseband processing units, CE can only be performed either at the BS via uplink training or the MS via downlink training, due to the lack of observations at the RIS and its limited computation capabilities. When extending to multi-user RIS CE, a shared BS-RIS channel exists among all the users, and this fact should be considered for CE algorithm development.

In order to simplify the CE, a few active sensors or anchors can be deployed at the RIS, so that CE can be performed at the RIS, by alternations of uplink and downlink training.

With respect to the beam training matrix, if no prior knowledge about the MS location and environmental objects, e.g., scatters, reflectors, is available, a random construction or selection from part of unitary discrete Fourier transform (DFT) matrix or array response vectors are usually considered. The prior information on MS location and environmental objects can be transformed into the prior knowledge on channel parameters, e.g., AoAs and AoDs. Thus, a better beam training matrix can be designed with higher resolution, compared to the case without any prior information. This in turn brings better performance on RIS CE. On the other hand, the prior information can be used to reduce training overhead by beam selection, resulting in an increase on effective SE.

§.§.§ RIS Beam Alignment

Beam alignment, a one-step direct approach, can intentionally skip the CE process and directly focus on the optimal or suboptimal beam pair selection. It scans and chooses the best pair of beams, one for each terminal, according to a certain criterion, for data transmission. Meanwhile, a coarse MS location can be extracted from the selected beams. The criteria of choosing the best beam pair include maximizing the received power, multiple hypothesis testing, etc. These criteria work well in the high signal-to-noise ratio (SNR) regime and bring a promising performance in terms of beamforming gains and effective SE. Same as RIS CE, the prior location information can also help.
The weakness lies in that the performance of beam alignment will be determined by the resolution of the predetermined beams (closely related to training overhead) and the criterion of beam selection. When the number of RIS elements is large, its overhead will be inevitably high, which might prevent its usage for RIS-aided mmWave MIMO systems in practice.

§.§.§ RIS Data-Driven Approaches

In practice, a huge number of low-cost RIS elements are needed in order to compensate for the severe path loss occurred in the reflection route via RIS. Under such an extreme situation, advanced CS-based CE scheme and standard beam alignment may fail to deliver a satisfactory performance due to either the inevitably high complexity or training overhead. In this regard, data-driven approaches come into effect and may play a pivotal role in CE <cit.>, joint active and passive beamforming, MS localization, and SLAC (see Fig. <ref>). The dataset can be collected by fixing the beam training matrices (with reasonable sizes) at all the terminals, resulting in a reasonable training overhead. The labels include the exact (cascaded) channels or parameters therein, joint active and passive beamforming, MS location, or combinations of these. A fully connected DNN or its variant is then trained to map the received signals to the aforementioned labels. Besides, deep unfolding can also be applied with the aid of domain knowledge to mimic the conventional iterative CE algorithms, e.g., iterative reweighted method, projected gradient descent, yielding better estimation performance as well as speeding up the convergence. The training procedure can be done offline with parameter fine-tuning online with a negligible effort. The SLAC loss functions include the combinations of the normalized mean square error (NMSE), SE, and position error bound (PEB). After training, the DL model is used for real-time implementation with the same fixed beam training matrices as in the channel acquisition phase to collect observations. The output of DL model can be used for multiple purposes, as various loss functions can be applied, shown in Fig. <ref>.

§.§ Case Studies

Case study 1: CE via compressive sensing (ANM <cit.>)  and beam alignment in terms of effective SE, considering 16 BS and 16 MS antennas and 64 RIS elements, all with half-wavelength spacing. Each individual channel is modelled by following Section <ref>, and the CE is performed at the MS via downlink training. Beam alignment is conducted by creating single-layer beam codebooks at all the terminals.

scale only axis,

axis background/.style=fill=white,

legend style=at=(0.03,0.03), anchor=south west, legend cell align=left, align=left, draw=white!15!black
[color=red,line width=.7pt,dashed]
table[row sep=crcr]
0	0.334585279226303

5	0.209359094500542

10	0.0786723440885544

15	0.0504794605076313

20	0.0272031761705875

Deep Unfolding, $T_{\mathrm{p}} = 24$

[color=blue,line width=.7pt,dashed]
table[row sep=crcr]
0	0.303684681653976

5	0.116722382605076

10	0.0647066384553909

15	0.0340290516614914

20	0.0203601372241974

Deep Unfolding, $T_{\mathrm{p}} = 28$

[color=black,line width=.7pt]
table[row sep=crcr]
0	1.7489

5	0.7145

10	0.1516

15	0.0497

20	0.0268

Least Squares, $T_{\mathrm{p}} = 32$

(ylbl) [rotate = 90] at (-0.9,2.3)NMSE;
(xlbl) at (4, -0.3) SNR (dB);

Case study 2: CE via data driven approaches (deep unfolding) and least squares (which ignores the channel sparsity) in terms of NMSE, considering 1 BS and 16 MS antennas and 32 RIS elements, all with half-wavelength spacing. Each individual channel is modelled by following Section <ref>.

To demonstrate the relative performance of the different approaches, the usefulness of exploiting sparsity, as well as different performance metrics, we have conducted two case studies. The first case study (shown in Fig. <ref>) compares RIS channel estimation via compressive sensing  (using ANM <cit.>) with beam alignment, with performance measured in terms of the effective SE (i.e., accounting for the rate loss due to using $T_{\mathrm{p}}$ training signals compared to a frame time of duration $T_{\mathrm{c}}=500$).

CE via ANM outperforms the standard beam alignment due to its fixed beam resolution. As the effective SE is a function of the training overhead $T_{\mathrm{p}}/T_{\mathrm{c}}$, we observe that the performance does not further improve when we increase the training duration from $T_{\mathrm{p}} = 40$ to $T_{\mathrm{p}} = 56$ in the beam alignment. On the contrary, performance improvement can still be seen in the CE via ANM.
The second case study (shown in Fig. <ref>) compares  cascaded channel estimation via data-driven deep unfolding with the standard least squares approach (which ignores channel sparsity), in terms of NMSE.

Deep unfolding mimics the gradient descent algorithm for a regularized optimization problem, where both channel rank deficiency and noise effect are considered. Deep unfolding based cascaded channel estimation is capable of offering better estimation performance in terms of NMSE compared to the least squares estimation with lower training overhead $T_{\mathrm{p}}/T_{\mathrm{c}}$.

Communication  application
Prior location information      Prior map information     Localization and sensing application
Prior location information      Prior map information

RIS phase profile optimization                RIS phase profile optimization

Frame structure optimization         –     User tracking

RIS channel estimation                 RIS environment mapping
RIS link blockage prediction               RIS object sensing
Inter-RIS handover               Dedicated region (low energy, high secrecy, etc)

Overview of SLAC for possible applications in RIS-aided communication. Here, means that the information has limited impact, means that the information is useful, and means that the information provides significant performance benefits. We observe that location and map information can boost RIS-aided communication performance, and should themselves be provided with the aid of RIS.

§ RIS SIMULTANEOUS LOCALIZATION AND COMMUNICATION

Many practical applications can be enabled by virtue of RISs. The RIS mmWave MIMO channels contain the geometry information about the environmental objects and the terminals, which inextricably link the two important functionalities, i.e., communications and localization. This also emphasizes the importance of CSI acquisition, already discussed in Section <ref>, and the RIS control. An overview of how location and sensing information can be harnessed for communication and localization applications with RIS is provided in Table <ref>.
For this reason, we will discuss, in this section, RIS optimization for communications and localization performance separately, as well as their joint performance.

§.§ RIS for Communications

A typical use case of an RIS in wireless communications is to use it as a reflector enabling communications “around a corner" by using directive beamforming. In mmWave communications, the path loss of the radio wave propagation is very large requiring usually a LoS connection between the transmitter and the receiver. If the direct link is obstructed, a reflected “LoS"-like link may be created by an RIS. The reflection loss decreases the receive power level, but still it can in many cases be much higher than that caused by random scattering from uncontrolled channel. Due to its large area, an RIS can leverage the near-field effect and create not only directional beams, but also positional beams. Such beams focus energy and provide communication quality in a specific location, rather than a specific direction.
The RIS operation can be interpreted by at least two ways. One is to see it as a mechanism to control on the random wireless channel realization. The classical system design takes the wireless channel as it is so that the waveforms, channel codes, transmit and receive processing etc. are the functionalities that an engineer can design. The introduction of an RIS (or multiple RISs) in the channel changes the paradigm so that one can also design the channel to optimize communication-relevant performance metrics.
The other way to interpret the use of an RIS is to interpret it as a passive relay station. A true relay station amplifies the received signal directly in the amplify-and-forward (AF) protocol, or decodes and re-transmits it in the decode-and-forward (DF) one. The RIS can operate in some sense similarly to the AF relay without active power amplification or receive noise, because it is a passive element. However, similar order or even better power gains have been reported <cit.>.

The performance metrics for the communications include the link range or SE, for example. The former can be characterized as the probability of outage of given data rate as a function of the distance between the transmitter and the receiver. The latter is basically the achievable rate or the sum rate in the case of multiple users. Both depend on the signal-to-noise-plus-interference ratio (SINR) at the receiver. The target of the RIS control algorithm is to adjust the phase shifts so that the SINR is maximized by coherent combining of the propagated signal given the instantaneous CSI.

every tick label/.append style=font=
[rotate = 90] at (-2.2cm,2cm)$y (\mathrm{m})$;
[rotate = 0] at (.8cm,4.1cm)a) random, PEB $ (\mathrm{m})$;
[rotate = 0] at (6.3cm,4.1cm)b) random, SE $ (\mathrm{bits/s/Hz})$;
[rotate = 0] at (11.5cm,4.1cm)c) directional, SE $ (\mathrm{bits/s/Hz})$;

axis on top,
xlabel=$x (\mathrm{m})$,
scale only axis,
axis on top,
[thick,blue] graphics[xmin=-10,ymin=0,xmax=10,ymax=10] Figs/F5_random_PEB.eps;

[at=(2.7cm,0cm),axis on top,
scale only axis,
ymode = log,

axis on top,
ytick pos=right,
[thick,blue] graphics[xmin=0,ymin=1e-4,xmax=1,ymax=1] F5_random_PEB_clb.png;

axis on top,
xlabel=$x (\mathrm{m})$,
scale only axis,
axis on top,
[thick,blue] graphics[xmin=-10,ymin=0,xmax=10,ymax=10] Figs/F5_random_Rate.eps;

[at=(8.2cm,0cm),axis on top,
scale only axis,

axis on top,
ytick pos=right,
[thick,blue] graphics[xmin=0,ymin=0.0361,xmax=1,ymax=1] Figs/F5_random_rate_clb.png;

axis on top,
xlabel=$x (\mathrm{m})$,
scale only axis,
axis on top,
[thick,blue] graphics[xmin=-10,ymin=0,xmax=10,ymax=10] Figs/F5_directional_Rate.eps;

[at=(13.5cm,0cm),axis on top,
scale only axis,

axis on top,
ytick pos=right,
[thick,blue] graphics[xmin=0,ymin=1.2841,xmax=1,ymax=10] Figs/F5_directional_rate_clb.png;

§.§ RIS for Localization

The RIS has been recognized as one of the key enabling technologies toward B5G localization <cit.>. A typical use case on an RIS in localization, is to use it as a location reference point when the LoS connection is obstructed. The reflected LoS path created by the RIS provides an informative measurement of the user's position. Even when LoS is present, the RIS can provide localization improvement, by turning multipath from a foe to a friend, and moreover controlling this multipath to optimize localization performance. In particular, the RIS has great potential to improve the estimation accuracy of the channel parameters (such as AoA, AoD, ToA, phase-of-arrival (PoA), and even Doppler shifts), by optimizing the adjustment of the phase profile or the current distribution in the RIS elements. As a result, the position estimation by utilizing the geometric relationship between the measurements and positions, is significantly improved.

As in communications, RIS operation for localization can be interpreted in several ways. First, an RIS with known position and orientation serves as a location reference (similar to a BS) in a global coordinate system. The signal from this reference provides measurements of ToA, AoA, and AoD, which enable more accurate localization.
A second interpretation is as a smart object with a unique signature, providing a distinguishable multipath component, thus aiding localization and environment mapping applications.

Since an RIS can operate as a reflector, a receiver, and a transmitter. For the most commonly used reflector mode, an RIS can be deployed to smartly forward the wave signals to user terminals or based station, where the multi-path propagation is fully utilized to localize users.
For the receiver mode, an RIS can be configured with a nearly continuous phase profile, acting as a lens.
Due to the large size of the RIS,
wavefront curvature can be harnessed to localize MS and help with system synchronization <cit.>.
For the transmitter mode, an RIS can
act similarly to analog transmit beamformer and generate phase-shift keying (PSK) modulated symbols as pilots, hence the channel and position estimation can be performed.

The performance metrics for localization include root mean-square error (RMSE) of position estimation and the localization coverage. Through Fisher information analysis, the Cramér–Rao bound of position can be derived, using as the PEB for localization frameworks.

§.§ RIS for Simultaneous Localization and Communications

With the development of 5G and beyond, emerging applications have posed stringent constraints on both communications and localization. For example, in autonomous driving, a large amount of information needs to be exchanged among vehicles and roadside infrastructure and decimeter-level localization accuracy at the MS side should simultaneously be achieved. In these emerging SLAC applications, the signal and algorithm designs, architecture, and standards, should be further investigated. The RIS can be a promising candidate technology in realizing SLAC applications, since, as we will see, it  shows great potential in achieving high SE communications and high accuracy localization performance.

Distinct from the conventional communications or localization framework, where either the communications metrics (SE, for example) or the localization performance (PEB) are considered, RIS-assisted SLAC requires a proper trade-off between communications and localization. Particularly, the optimal adjustment of the phase profile for the RIS should be designed to meet both the communications and localization requirements. In Fig. <ref>, we study the trade–off between communication and localization in a SISO system equipped with a single RIS (as in <cit.>).
The coherence time is assumed to be $T_{\mathrm{c}} =1000$ symbols, where we use $T_{\mathrm{p}} \geq 3$ symbol slots for transmitting specific pilots and the rest for communication. For each value of $T_{\mathrm{p}}$, the localization and communication performance are calculated in terms of PEB and SE, and illustrated as a curve in Fig. <ref>.
The RIS phase profile sequence can be random (when there is no a priori location information) or directional (when there is a priori location information) during pilot transmission, while it is always directional during communication, as it is based on the estimated channel from the pilots. We observe that such a priori location information can significantly boost both maximal SE (about a factor of 2) and minimal PEB (about a factor of 10). The size of the RIS has a major impact on the performance, where going from 256 elements to 1024 elements improves the maximal SE about 4 times and the minimal PEB about 2–4 times.

every tick label/.append style=font=

scale only axis,
xlabel=PEB (m),

ylabel=SE (bits/sec/Hz),
axis background/.style=fill=white,
legend style=legend cell align=left, align=left, draw=white!15!black
table[row sep=crcr]
1.30480188403431	0.509044143392504

0.69316653057187	0.944430338006331

0.67966509141396	0.956860261980761

0.65274294129124	0.982877544076358

0.617059493522002	1.01816680136696

0.615290218531637	1.01895148662671

0.607327798463853	1.02607416664252

0.596868659860817	1.03576007942208

0.58996379618294	1.04179838750879

0.5334846991374	1.09877001443511

0.52641794710384	1.10489219270629

0.486890701127268	1.14388853290773

0.479550382924707	1.15008881069794

0.474661323451583	1.15380033985119

0.416117480700892	1.20949170247794

0.410451544846717	1.21357701435165

0.370934950094065	1.24822995451552

0.369846467843982	1.24791399309777

0.348360087392495	1.2651216890624

0.34520448667136	1.26647762751203

0.321656331709534	1.28437743693813

0.320354350758033	1.2840938938251

0.319958852512859	1.28309048532748

0.31033326167662	1.28927600765772

0.297391484803666	1.29774730627529

0.294877480798975	1.29827605435454

0.293102367289686	1.29824650744272

0.291811488199265	1.29785436138921

0.288934979057943	1.2986075934963

0.286935632279876	1.29870958563317

0.286882138645885	1.29740637729835

0.280376162848701	1.3006905374953

0.279677703208094	1.29983498762987

0.275104980863081	1.3016736337719

0.273390923984971	1.30150497717863

0.271973020519089	1.30112525896036

0.270054586188421	1.301079478994

0.266953654999352	1.3018191544035

0.26677360909603	1.30058389599339

0.266273111160997	1.2995628096309

0.264688493912867	1.29926261231532

0.254685171615322	1.30444230026359

0.247217602134045	1.30781140689748

0.245709008031976	1.30738238377268

0.244823510671973	1.3065610367403

0.236803486458691	1.3100785754596

0.234348573574682	1.31016853181848

0.234187251141822	1.30888662492049

0.23089757540775	1.30944690699574

0.230331170536286	1.30839796483522

0.228977329016906	1.30780489955566

0.228653599574585	1.30661130079658

0.228114125353755	1.3055415372323

0.225737296220755	1.30552284144856

0.225696781988706	1.30416296707257

0.225041584431281	1.30315255040381

0.221335004977215	1.30385634220555

0.220026002669452	1.30319959785307

0.218978525996899	1.30239302909781

0.218428677338465	1.3013090648122

0.21792543980035	1.30019818979817

0.210911823637523	1.30259910117286

0.210372647010842	1.30149370510116

0.209365439511922	1.30063413659431

0.209181510827431	1.29933846239355

0.208664847621006	1.29821721457425

0.208575896562347	1.29687089076071

0.208555322666339	1.29548867096165

0.205448789468395	1.29570855736363

0.202592469221768	1.29577562370747

0.202480202853053	1.29443632348406

0.201662584834357	1.29345382066639

0.201531018399196	1.29212338392346

0.195988741504794	1.29348353435522

0.195305095304735	1.29241845674778

0.19528389599949	1.29102857327769

0.192276471345047	1.29108493246186

0.190706380548518	1.29043439765743

0.190528809306627	1.2891162676221

0.187618560062045	1.28908673483392

0.18742372249488	1.28777363229952

0.1840911775054	1.28791265288841

0.181019470269179	1.28790471296782

0.180825047833849	1.28658481979281

0.180503880408269	1.2853216203998

0.178964057001091	1.28460224130528

0.175098011965397	1.28489579733872

0.174779004802859	1.28362410816123

0.173110072304742	1.28293465905303

0.170058081695761	1.28282368856245

0.16794773972595	1.28229629490369

0.167385537929418	1.2811163683518

0.167308174048786	1.27973441896425

0.166838237437602	1.27851473487484

0.166470268721802	1.27725212739528

0.163345859681049	1.27711135100693

0.160707467673241	1.27675199823741

0.160299200029528	1.27549680275733

0.155756556252294	1.26307918789897

0.145591595493876	1.25259637688499

0.138488998280949	1.2407833603328

0.133486630689153	1.22813768745091

0.129066546451849	1.21522115138104

0.123821332498622	1.20246702490201

0.120159476999952	1.18917960900623

0.116984673807755	1.17570836214145

0.11312166740923	1.16236977173291

0.110202341170729	1.14874392132986

0.1078382133134	1.13495051127761

0.105494849480373	1.12112615961781

0.101560796414157	1.10762525976944

0.100302239053289	1.09350924053328

0.0981658200678553	1.07956368743439

0.0953190627273268	1.06573720404766

0.0934557567083041	1.05169313152375

0.0918930328881877	1.03757704474587

0.0900260119560939	1.02350245685764

0.0883989513135276	1.00937032915742

0.0829976343092993	0.938112098728886

0.0732205109147122	0.794960644566604

0.0661035330378302	0.651046386029367

0.061011940977584	0.506686464811199

0.0566723755759251	0.362097698755567

0.0530393358459759	0.217342382898789

0.0502190884146746	0.0724678675174054

0.0491911490434946	0.0144950059202273

[color=blue,dashdotted,line width=.7pt]
table[row sep=crcr]
10.2460800389039	0.0303286814460985

7.23972621140656	0.0484146564376182

6.41623305227605	0.0572024026118747

6.34425426335232	0.058071639825703

5.95756293077459	0.0637916232709858

5.9425466505274	0.0639764873260298

5.119327722441	0.0791279209461226

4.99773329217128	0.0814899698253305

4.90438304933655	0.083311859570106

3.56037090983407	0.125432677374751

3.50790436869849	0.127776613149916

3.41529991867243	0.132310109604992

3.33813232328282	0.136339598064804

3.22352106830044	0.142794322308356

3.13047205789398	0.14842317712591

3.11947001595292	0.148987398547086

2.97795110392379	0.158862177244116

2.84550505516468	0.16969920611697

2.70438466848499	0.182902200523445

2.58833428988724	0.194954423943016

2.56545395143356	0.197319016506982

2.48680950800548	0.2063926530104

2.32785123344734	0.227756558452093

2.32156193301257	0.228468461904636

2.26594375790861	0.23692207311607

2.26257489307883	0.237223842131269

2.25182224968223	0.238733375859986

2.19747903096664	0.24768991482754

2.19253805901873	0.24829910041553

2.13458354545896	0.258522834861348

2.13172279556519	0.258788990868674

2.1288195785866	0.259063507795749

2.11827277067172	0.260775890412637

2.10967113517426	0.262134408104921

2.09686471009303	0.264309892301109

2.07414415439791	0.268445693468022

1.995093297888	0.284203434550327

1.96727651798601	0.289802922785748

1.95288011474817	0.292601697180997

1.8793573387747	0.308689944987829

1.85241156457586	0.314620066158549

1.82303060790686	0.321264621382515

1.80952455969158	0.324190239958268

1.79863054167428	0.326507144683401

1.72471397638124	0.344884933881172

1.69210540460585	0.353205958828266

1.66227506950741	0.361027595279709

1.61669704442948	0.373669348266617

1.60389178773887	0.377050607603858

1.58423671873652	0.382549273884205

1.579132129958	0.383697394627281

1.5790531097809	0.383316290324186

1.57377258038731	0.3845227322226

1.57151522019827	0.384807104163725

1.57044064301137	0.384728834613715

1.5679343426238	0.385089854373026

1.55478847160486	0.388747843237162

1.54326397217652	0.39194894147215

1.52995071693302	0.395765682810316

1.49400144337613	0.407114926526873

1.47029247451506	0.414729072816318

1.45332403552914	0.420190607581548

1.42816420630552	0.428726870849693

1.41770893830837	0.432085269778973

1.41026681002942	0.434368615737034

1.40650808099491	0.435298673055403

1.40066931675864	0.437010964193399

1.39657735125902	0.438077308215638

1.39569200313745	0.437939271865056

1.38683192325	0.440818505873215

1.37343793520146	0.44547883390234

1.364844443692	0.448338282115706

1.34909447916763	0.454070134118562

1.33459518489552	0.459413819135966

1.32749575510109	0.461812642725848

1.32008328767228	0.464362902390779

1.31914634033609	0.464246648374615

1.31724839632623	0.46452798728641

1.30816447854481	0.467806603605944

1.29788139316291	0.47163351768813

1.2963777562107	0.471758273130937

1.28424062644775	0.476441313011061

1.27994429085436	0.477780142308053

1.27920665916969	0.477577914278379

1.25886743406134	0.485998997439128

1.25520324339644	0.487103485240604

1.24937361673417	0.489188117596369

1.24897454948333	0.48883099662592

1.24289622163314	0.49104287251665

1.24240493337246	0.490725656893512

1.23506444520697	0.493531792943253

1.22452594345893	0.497848350292051

1.22023897871326	0.49929491230028

1.21779362800645	0.499886010378487

1.18471821934823	0.515172837847034

1.18347786294167	0.515210433097905

1.17821385804066	0.51722928267568

1.17054234674886	0.520460990647897

1.10663481255938	0.5477077474376

1.05962196369942	0.567579410266824

1.0366371901507	0.574353757857826

0.984380896100287	0.599090111769461

0.955357596817647	0.610309488609151

0.931206677467976	0.618620710603934

0.89761835026544	0.63334913852423

0.866271033803814	0.646920794318039

0.840296884088597	0.656979695330505

0.821596139088078	0.661955400423955

0.808493496006184	0.662892066024433

0.78916996248602	0.668141204384875

0.783122504666424	0.663843400057315

0.751388517496409	0.6777307108922

0.739828758575576	0.67706450683303

0.723783237995654	0.679469968130484

0.707560205611881	0.68183838659742

0.698909049767705	0.678629812591186

0.685959090676876	0.678324033604178

0.671802322488866	0.678686384258807

0.625254114220916	0.660989908809855

0.550676561609536	0.601836043289572

0.500184327473309	0.515934696672332

0.462256572704183	0.414773782354263

0.431789672286948	0.303811222913827

0.406142383650883	0.185986897280874

0.380643074857495	0.0631810824256185

0.371130187844286	0.0127223041342043

table[row sep=crcr]
3.15597029653262	0.312440381830939

0.196470912440423	4.32821774138088

0.194983040304319	4.32889587569456

0.194208858306043	4.32714035053185

0.192025706664849	4.33003807354502

0.191597150738841	4.32708911311744

0.190867665016892	4.325119732886

0.190306007723441	4.32258894554951

0.189897541440427	4.31955119868946

0.183376056873733	4.33595804902158

0.183243512649851	4.33198315303812

0.181759137194172	4.3322008688356

0.18164835025179	4.32814902410569

0.181565846879806	4.32400915084576

0.142957928039322	4.42501610304393

0.142866367976623	4.42073283258283

0.121600971004578	4.46292500928971

0.121517387293109	4.45854359075208

0.117731582451119	4.46146776089974

0.117481565333889	4.45739504295889

0.103281030618402	4.47858413335504

0.103205647449746	4.47412756789912

0.103139340728034	4.46965533242965

0.102684004537081	4.46583679975771

0.0993856899808167	4.46668908075597

0.0992153198612711	4.46237407500661

0.0991685315233028	4.45785868829342

0.0991243893853927	4.45333884504311

0.0989477506748943	4.44903188650696

0.0988985374208163	4.44451950470663

0.0988617946035083	4.43998694035569

0.098649914931704	4.43573418881189

0.0985958933327346	4.43122849324853

0.0984535869876298	4.42686305174114

0.0984255740463785	4.42231537188413

0.0983383374948133	4.41786150228762

0.0983098682072906	4.41331420917842

0.0981134943806878	4.40903204323444

0.0980886820272507	4.40447841674786

0.0980661759574877	4.39992106799926

0.0980436219070679	4.39536371239081

0.0937279533994041	4.39739624175797

0.0919800865006644	4.39539031068434

0.091793348930658	4.39106169218693

0.0917666954023212	4.38649790708526

0.0877951781754996	4.38757187871996

0.0877365640619135	4.38304486259848

0.0877178610165255	4.37846203778841

0.0876456679948503	4.37395354339584

0.0876301150057686	4.36936612895713

0.0875491201096281	4.36486939061139

0.0875342356357972	4.36028083973195

0.0874929569004098	4.35572872403486

0.0874167353467313	4.35122466679946

0.0874011909138444	4.3466367344998

0.0873866658490259	4.34204735036089

0.0871827872443726	4.33771784395176

0.0870418583327863	4.33330102775834

0.0870296727847698	4.32870777735535

0.0870190003750447	4.32411242494953

0.087005178358151	4.3195213311254

0.0795245692364036	4.32464754372058

0.0795138880475028	4.32004044559361

0.0794012758104574	4.31555953657728

0.079389431851579	4.31095366294366

0.0793796581527018	4.30634520004566

0.0793700315001546	4.30173652843818

0.0793607467104146	4.29712740885418

0.079169754031608	4.29274151587031

0.0790170067171299	4.28830776298227

0.0790076315222014	4.28369819900326

0.0789554314887089	4.27914086436837

0.0789450901025781	4.27453236268481

0.0732078599875586	4.27663651139979

0.0731983430151091	4.27201883400781

0.073189293763305	4.26740060595393

0.0727589474056749	4.26325422078702

0.0727371230943979	4.2586496225303

0.0727292725088013	4.25402940056162

0.0721794582880189	4.25000983678006

0.072170785675337	4.24538976117608

0.0707978682105251	4.24225794456598

0.0696082912164176	4.23889953049363

0.0695999918953983	4.2342756475508

0.0695921432417348	4.22965126737513

0.069562456424987	4.22504994728171

0.0652531232205726	4.22482325956677

0.0652452146790895	4.22019350855064

0.0651682713640473	4.21563183964671

0.0630088130452903	4.21308533186129

0.0625252618190498	4.2089033702436

0.0625173442691081	4.20427036476884

0.0625107158650348	4.19963612857167

0.0625039864726404	4.19500197285231

0.0624693485108055	4.19039399963357

0.0593033414972039	4.18864548772003

0.0574884870354282	4.1855893992901

0.0574395166555883	4.18098600955849

0.0570390806262559	4.13486972697286

0.052681856703784	4.09190632364029

0.0488836099532183	4.04819472309008

0.0474821136099185	4.00262806566423

0.0448216518584223	3.95781850490543

0.0419169104135041	3.91301216992737

0.040766735355269	3.86708356716735

0.0399168927107164	3.82095863727412

0.0387695346215574	3.77496817901244

0.0379870283400719	3.72876217536957

0.0377839657481299	3.68225346247061

0.0370224386494744	3.63601118102039

0.0346997868769121	3.59045935310777

0.0343356330458953	3.54398843274485

0.0331527902035982	3.49785341250876

0.0319855148796575	3.45168183810175

0.0313727124189872	3.40527245378516

0.0305696868660617	3.35892176934948

0.0300472176233677	3.3124564713784

0.0295802938361884	3.26596370026627

0.0279176905005997	3.03319560655437

0.0245934167980933	2.56734578783816

0.0221418227142808	2.10098287357099

0.0206948954644802	1.63427753290027

0.0192556046050956	1.16746019367317

0.0179197657446447	0.700537829279667

0.0170271469419918	0.233525531086407

0.0165516047770128	0.0467064290587585

[color=red,dashdotted,line width=.7pt]
table[row sep=crcr]
3.55525805520476	0.249894449768866

3.29682731905295	0.29195710633555

3.17727383272465	0.308909539132132

2.61396853220534	0.383529730859502

2.43426378004107	0.405742152981371

2.290603677257	0.431661638656131

2.16822145807262	0.465651267777162

2.15049120286931	0.470636868525369

1.95756907861774	0.534747235321151

1.72999791059634	0.652171120827824

1.72005176506252	0.65773301231048

1.69127081390762	0.675314281742349

1.67677596262104	0.683944704936082

1.6635918691575	0.691788897454926

1.63775697184339	0.708004746217709

1.53819627442056	0.775224698220939

1.50636917610696	0.797174199314518

1.47787365461048	0.817129526591247

1.37047893265397	0.897955953172495

1.36957249435621	0.897751826037071

1.31775771096622	0.938479746641426

1.29270953156853	0.958506190859496

1.29227058558943	0.957898378749253

1.27875584811009	0.968562839185784

1.18253660028664	1.06194728748939

1.18123872254051	1.06231834234241

1.17638519735765	1.0667453088284

1.10551886891605	1.15737117662081

1.08706490003642	1.18365091071436

1.06481217619486	1.21740994386956

1.04020382257905	1.25697396369737

1.03102334737152	1.27141430306047

1.00058579468319	1.32403028733507

0.982210504417001	1.35638834230258

0.980823033703614	1.35755959363577

0.975385178229865	1.3662890952083

0.973262969223725	1.36884085852584

0.940194977283023	1.43059793770843

0.935244954989975	1.43877365234848

0.935153990750186	1.43745134752673

0.900053354650696	1.50611225592247

0.861778095776155	1.58537436963638

0.85904629396106	1.58970805426565

0.851411099936609	1.60496328451641

0.847064179978046	1.61303418307219

0.846927642933419	1.6116492077768

0.844496538264315	1.61544407529831

0.839522022899256	1.62506089103957

0.836762360805985	1.62967912184915

0.814330192072445	1.68095174433622

0.813926239599595	1.68015834991444

0.812880621264528	1.68092192440504

0.782728756011993	1.75484109958406

0.769944833326635	1.78639783467079

0.756116147287838	1.82132696824952

0.749559672179977	1.83704928228706

0.738876234119965	1.86407724989567

0.733919578563907	1.87561608996993

0.731701886437279	1.87968004222506

0.727979811422337	1.8878593475597

0.727051854723843	1.8883865234506

0.724476554515189	1.89342101300698

0.723129830348384	1.89508591926266

0.714997160243861	1.91537963108771

0.709003104169115	1.92984625008703

0.707524794249427	1.93185866559873

0.703390061186108	1.94121318887187

0.70085363558928	1.94615028716609

0.699285049183498	1.94840356702187

0.689504672378087	1.97352507618323

0.686448293185188	1.9799544671614

0.685064625025884	1.98169818522735

0.677857982701994	1.99985625967334

0.674848892367631	2.00622190584947

0.673615201228532	2.0075544618459

0.666680587310278	2.02518535317597

0.653966413363168	2.05992775911133

0.653252990151871	2.0597901935831

0.650918287734227	2.06443600637735

0.649507738270659	2.06636197793084

0.644086565016228	2.08025598119711

0.639455458761691	2.09193122259599

0.635693076990027	2.10108227942624

0.635525454235751	2.09929746064088

0.625894791759336	2.12673476107271

0.624717109346194	2.128090450526

0.622785652659815	2.13181994941347

0.620984106687893	2.13515804697563

0.610588183530163	2.16611052227255

0.61019234405489	2.16501368672572

0.606968480608447	2.17314735089883

0.604517260362538	2.1788058230185

0.603337579703918	2.18029349997592

0.599174648339189	2.19171294955959

0.596910621124829	2.19687187319401

0.592625830609482	2.20891336647393

0.581582410177898	2.2445736462389

0.579845737791615	2.24818041093468

0.565453895834846	2.2743267874425

0.541001901445997	2.33914923100119

0.512165184855515	2.42419136920704

0.497425066589972	2.45485439912998

0.480643921615977	2.49360495622316

0.459990186154532	2.54804798182379

0.441876808419352	2.59232354770169

0.428828753069075	2.61571384315343

0.424349127019436	2.60268551322343

0.414148214222821	2.61369649812219

0.404799491149975	2.62091291928712

0.399642507540488	2.60977957291401

0.390812517548664	2.61402643094713

0.380804958235953	2.62277310269025

0.371225212530788	2.62888702364196

0.359706079326193	2.6420942111563

0.354787028392699	2.62666137385444

0.348580961808024	2.61580490034792

0.342464224546423	2.60375252159446

0.337306181110975	2.58713425619299

0.311549105145091	2.49318580303513

0.272669149900694	2.21779181277169

0.242643913988121	1.87576074519151

0.22523569449423	1.48394643839359

0.21195252965569	1.07265192078123

0.199565170072578	0.65024514377547

0.189313735991052	0.218475462678594

0.185547841461144	0.0438170681985661

(t1) [rotate = 0] at (1.2*,1*)Increased $T_{\mathrm{p}}$;
(t1) [rotate = 0] at (1.15*,1.05*)$\longleftarrow$;

PEB vs. NLoS SE with $T_{\mathrm{p}}$ increasing from right to left, for a SISO system equipped with a single RIS of size $16\times 16$ (blue curves) and $32\times 32$ (red curves). The BS, RIS and the user are located at $(1,1,0)$, $(0,0,0)$, and $(5,5,-5)$, respectively. We consider directional or random RIS profiles for localization and communication. The rest of the parameters can be found in <cit.>.

The figure also clearly illustrates three distinct regimes: (i) communication and localization quality are bad
when $T_{\mathrm{p}}$ is too small,  as we obtain a poor estimation of the UE position, which leads to directing the signal to an incorrect location and subsequently a low SNR. In this regime, both PEB and SE can be improved by increasing  $T_{\mathrm{p}}$; (ii) good localization performance but low rate occurs when  $T_{\mathrm{p}}$ is too high, since too much of the coherence time is devoted to pilots, leading to excellent channel estimates, but no time to exploit them; (iii) a regime where both positioning and communication have good performance, near the peak of the PEB–SE curves, obtained by moderate values of  $T_{\mathrm{p}}$ (about 5% overhead for the directional RIS phase profiles and 25% for the random RIS phase profiles, irrespective of the RIS size).

§ OUTLOOK

We have argued that beyond 5G systems enabled by RIS will have to rely on a synergy between communications and localization, since (i) both services rely on the same physical channel; and (ii) one will rely on the other for optimized performance. This leads to the concept of SLAC, which relies on the co-design of communications and localization resources and the flexible trade-off and reinforcement between the two services. To realize SLAC, reliable geometric channel models (including RIS and their hardware effects), as well as low-complexity channel estimation and resource allocation routines must be developed.

More research and development are required to address the RIS and SLAC technologies towards a wide commercial usage, e.g., in cellular communications, UAV, industry 4.0, autonomous driving, and others.

Jiguang He (S'16–M'20) is a postdoctoral researcher at Centre for Wireless Communications (CWC), University of Oulu, Finland. His research interests span millimeter wave MIMO communications, reconfigurable intelligent surfaces for simultaneous localization and  communications.

Fan Jiang (S'12–M'18)
is a postdoctoral researcher with Chalmers University of Technology, Sweden.
His research interest includes signal processing for wireless communications, massive multiple-input multiple-output (MIMO) and millimeter wave systems, and localization, tracking, and navigation framework.

Kamran Keykhosravi(S'15–M'20)
is a

postdoctoral researcher at Chalmers University of Technology, Sweden. His main research interests include  information theory,  reconfigurable  intelligent  surfaces, and radio localization.

Joonas Kokkoniemi (S'12–M'18)

is a postdoctoral research fellow at Centre for Wireless Communications, University of Oulu.

His research interests are in THz band and mmWave channel modeling and communication systems.

Henk Wymeersch(S'02–M'06–SM'19) received the Ph.D. degree in Electrical Engineering/Applied Sciences in 2005 from Ghent University, Belgium. He
is currently a Professor in Communication Systems
at Chalmers University of Technology, Sweden.

Markku Juntti (S'93–M'98–SM'04–F'20) is currently a Professor in Centre for Wireless Communications at University of Oulu, Finland. In 1999–2000, he was a Senior Specialist with Nokia Networks. His research interests include signal processing for wireless networks as well as communication and information theory.


* Green & Kavanagh (2021) Green, A. M., & Kavanagh, B. J. 2021, Journal of Physics G Nuclear Physics, 48, 043001, doi: 10.1088/1361-6471/abc534
  * Kaurov et al. (2019) Kaurov, A. A., Dai, L., Venumadhav, T., Miralda-Escudé, J., & Frye, B. 2019, ApJ, 880, 58, doi: 10.3847/1538-4357/ab2888
  * Kayser et al. (1986) Kayser, R., Refsdal, S., & Stabell, R. 1986, A&A, 166, 36
  * Kelly et al. (2019) Kelly, P., Acebron, A., Alfred, A., et al. 2019, Flashlights: Many Extremely Magnified Individual Stars as Probes of Dark Matter and Stellar Populations to Redshift z 2, HST Proposal. Cycle 27, ID. #15936
  * Kelly et al. (2018) Kelly, P. L., Diego, J. M., Rodney, S., et al. 2018, Nature Astronomy, 2, 334, doi: 10.1038/s41550-018-0430-3
  * Kelly et al. (2022) Kelly, P. L., Chen, W., Alfred, A., et al. 2022, arXiv e-prints, arXiv:2211.02670.  https://arxiv.org/abs/2211.02670
  * Lu et al. (2021) Lu, P., Takhistov, V., Gelmini, G. B., et al. 2021, ApJ, 908, L23, doi: 10.3847/2041-8213/abdcb6
  * MacGibbon et al. (2008) MacGibbon, J. H., Carr, B. J., & Page, D. N. 2008, Phys. Rev. D, 78, 064043, doi: 10.1103/PhysRevD.78.064043
  * Mediavilla et al. (2017) Mediavilla, E., Jiménez-Vicente, J., Muñoz, J. A., Vives-Arias, H., & Calderón-Infante, J. 2017, ApJ, 836, L18, doi: 10.3847/2041-8213/aa5dab
  * Meena et al. (2022a) Meena, A. K., Arad, O., & Zitrin, A. 2022a, MNRAS, 514, 2545, doi: 10.1093/mnras/stac1511
  * Meena et al. (2022b) Meena, A. K., Zitrin, A., Jiménez-Teja, Y., et al. 2022b, arXiv e-prints, arXiv:2211.13334.  https://arxiv.org/abs/2211.13334
  * Miralda-Escude (1991) Miralda-Escude, J. 1991, ApJ, 379, 94, doi: 10.1086/170486
  * Narayan & Bartelmann (1996) Narayan, R., & Bartelmann, M. 1996, arXiv e-prints, astro, doi: 10.48550/arXiv.astro-ph/9606001
  * Neindorf (2003) Neindorf, B. 2003, A&A, 404, 83, doi: 10.1051/0004-6361:20030098
  * Niikura et al. (2019a) Niikura, H., Takada, M., Yokoyama, S., Sumi, T., & Masaki, S. 2019a, Phys. Rev. D, 99, 083503, doi: 10.1103/PhysRevD.99.083503
  * Niikura et al. (2019b) Niikura, H., Takada, M., Yasuda, N., et al. 2019b, Nature Astronomy, 3, 524, doi: 10.1038/s41550-019-0723-1
  * Oguri et al. (2018) Oguri, M., Diego, J. M., Kaiser, N., Kelly, P. L., & Broadhurst, T. 2018, Phys. Rev. D, 97, 023518, doi: 10.1103/PhysRevD.97.023518
  * Page & Hawking (1976) Page, D. N., & Hawking, S. W. 1976, ApJ, 206, 1, doi: 10.1086/154350
  * Rauch (1991) Rauch, K. P. 1991, ApJ, 374, 83, doi: 10.1086/170098
  * Schneider et al. (1992) Schneider, P., Ehlers, J., & Falco, E. E. 1992, Gravitational Lenses, doi: 10.1007/978-3-662-03758-4
  * Seitz & Schneider (1994) Seitz, C., & Schneider, P. 1994, A&A, 288, 1
  * Seitz et al. (1994) Seitz, C., Wambsganss, J., & Schneider, P. 1994, A&A, 288, 19
  * Serpico et al. (2020) Serpico, P. D., Poulin, V., Inman, D., & Kohri, K. 2020, Physical Review Research, 2, 023204, doi: 10.1103/PhysRevResearch.2.023204
  * Spera et al. (2015) Spera, M., Mapelli, M., & Bressan, A. 2015, MNRAS, 451, 4086, doi: 10.1093/mnras/stv1161
  * The LIGO Scientific Collaboration et al. (2021) The LIGO Scientific Collaboration, the Virgo Collaboration, the KAGRA Collaboration, et al. 2021, arXiv e-prints, arXiv:2111.03606, doi: 10.48550/arXiv.2111.03606
  * Tisserand et al. (2007) Tisserand, P., Le Guillou, L., Afonso, C., et al. 2007, A&A, 469, 387, doi: 10.1051/0004-6361:20066017
  * Tuntsov et al. (2004) Tuntsov, A. V., Lewis, G. F., Ibata, R. A., & Kneib, J. P. 2004, MNRAS, 353, 853, doi: 10.1111/j.1365-2966.2004.08115.x
  * Venumadhav et al. (2017) Venumadhav, T., Dai, L., & Miralda-Escudé, J. 2017, ApJ, 850, 49, doi: 10.3847/1538-4357/aa9575
  * Welch et al. (2022a) Welch, B., Coe, D., Diego, J. M., et al. 2022a, Nature, 603, 815, doi: 10.1038/s41586-022-04449-y
  * Welch et al. (2022b) Welch, B., Coe, D., Zackrisson, E., et al. 2022b, arXiv e-prints, arXiv:2208.09007.  https://arxiv.org/abs/2208.09007
  * Windhorst et al. (2018) Windhorst, R. A., Timmes, F. X., Wyithe, J. S. B., et al. 2018, ApJS, 234, 41, doi: 10.3847/1538-4365/aaa760
  * Windhorst et al. (2023) Windhorst, R. A., Cohen, S. H., Jansen, R. A., et al. 2023, AJ, 165, 13, doi: 10.3847/1538-3881/aca163


$C_{\Phi}=\\{x_{\alpha}(1)\mid\alpha\in\Phi\\})$ on every $X_{\alpha}$,
$\alpha\in\Phi$, except the case $G=G_{sc}(\mathbf{C}_{2},R)$, $1/2\notin R$,
where $R$ is e-interpretable in $G$ on the set $Y_{\alpha}$ from Proposition
5.

Proof. There are four cases to consider:

— roots included in the system $\mathbf{A}_{2}$,

— short roots of the system $\mathbf{G}_{2}$,

— roots included in the system $\mathbf{B}_{2}/\mathbf{C}_{2}$, where all
$X_{\alpha}$ are Diophantine,

— and $\mathbf{C}_{2}$ with the sets $Y_{\alpha}$.

Case 1. Suppose that we have a root system
$\mathbf{A}_{2}=\langle\alpha,\beta\rangle$ and we want to interpret the ring
$R$ on $X_{\alpha+\beta}$. We will turn the set $X_{\alpha+\beta}$ into a ring
$\langle X_{\alpha+\beta},\oplus,\otimes\rangle$ as follows.

For $x,y\in X_{\alpha+\beta}$ we define

$x\oplus y=x\cdot y.$

Note that if $x=x_{\alpha+\beta}(a)$, $y=x_{\alpha+\beta}(b)$, then
$xy=x_{\alpha+\beta}(a+b)$, which corresponds to the addition in $R$.

To define $x\otimes y$ for given $x,y\in X_{\alpha+\beta}$ we need some
notation. Let $x_{1},y_{1}\in G$ be such that

$x_{1}\in X_{\alpha}\text{ and }[x_{1},x_{\beta}(1)]=x;\quad y_{1}\in
X_{\beta}\text{ and }[x_{\alpha}(1),y_{1}]=y.$

Note that such $x_{1},y_{1}$ always exist and unique, if
$x=x_{\alpha+\beta}(a)$, $y=x_{\alpha+\beta}(b)$, then $x_{1}=x_{\alpha}(a)$,
$y_{1}=x_{\beta}(b)$. Now define

$x\otimes y:=[x_{1},y_{1}].$

Observe, that in this case

$[x_{1},y_{1}]=[x_{\alpha}(a),x_{\beta}(b)]=x_{\alpha+\beta}(ab).$

so corresponds to the multiplication in $R$. To finish the proof we need two
claims.

Claim 1. _The map $a\mapsto x_{\alpha+\beta}(a)$ gives rise to a ring
isomorphism $R\to\langle X_{\alpha+\beta},\oplus,\otimes\rangle$._

This is clear from the argument above.

Claim 2. _The ring $\langle X_{\alpha+\beta},\oplus,\otimes\rangle$ is
e-interpretable in $G$._

To see this, observe first that, as was mentioned above, $X_{\alpha+\beta}$ is
Diophantine in $G$. The defined addition is clearly Diophantine in $G$. Since
the subgroups $X_{\alpha}$ and $X_{\beta}$ are Diophantine in $G$ the
multiplication $\otimes$ is also Diophantine in $G$. This proves the case 1.

Case 2. Suppose that we want to interpret a ring $R$ on some short root of the
system $\mathbf{G}_{2}$. Since long roots of $\mathbf{G}_{2}$ form the
subsystem $\mathbf{A}_{2}$, then the ring $R$ is already interpreted on all
$X_{\alpha}$ for long roots $\alpha$ and it is sufficient to find a
Diophantine isomorphism $\mu:X_{\alpha}\to X_{\alpha+\beta}$, where $\alpha$
is long and $\beta$ is short.

We will use the relation

$[x_{\alpha}(t),x_{\beta}(u)]=x_{\alpha+\beta}(tu)x_{\alpha+3\beta}(-tu^{3})x_{\alpha+2\beta}(-tu^{2})x_{2\alpha+3\beta}(t^{2}u^{3}),$

that shows

$x_{\alpha+\beta}(t)=\mu(x_{\alpha}(t))=X_{\alpha+\beta}\cap[x_{\alpha}(t),x_{\beta}(1)]X_{2\alpha+3\beta}X_{\alpha+3\beta}X_{\alpha+2\beta}.$

Since $\mu$ is Diophantine, and $R$ is e-interpretable in $G$ on $X_{\alpha}$,
then $R$ is e-interpretable in $G$ also on $X_{\alpha+\beta}$ and therefore on
all $X_{\gamma}$ for all roots.

Case 3. Now let us consider the root system $\mathbf{C}_{2}$, where all
$X_{\gamma}$, $\gamma\in\Phi$, are Diophantine.

Of course, for $x,y\in X_{\gamma}$ we define

$x\oplus y=x\cdot y$

and it is equivalent to addition in $R$ for any root $\gamma\in\Phi$.

To define $x\otimes y$ for given $x,y\in X_{\gamma}$ we will start with
defining an isomorphism $\mu$ between $X_{\alpha}$ and $X_{\alpha+\beta}$,
where $\alpha$ is long, $\beta$ and $\alpha+\beta$ are short, with
$\mu(x_{\alpha}(t))=x_{\alpha+\beta}(t)$.

This isomorphism $\mu$ can be determined for example by

$x_{\alpha+\beta}(t)=\mu(x_{\alpha}(t))=X_{\alpha+\beta}\cap[x_{\alpha}(t),x_{\beta}(1)]\cdot
X_{\alpha+2\beta}.$

Now when $\mu$ is defined it is evidently sufficient to define the operation
$\otimes$ only for one $X_{\gamma}$. We will do it for
$\gamma=\alpha+\beta=e_{1}+e_{2}$.

Let $x,y\in X_{\alpha+\beta}$ and $x_{1}\in X_{\alpha}$ be defined as
$\mu^{-1}(x)$, $y_{2}\in X_{\beta}$ be $y^{w_{e_{1}}^{-1}}$. Then we will
define $x\otimes y$ as

$x\otimes y=X_{\alpha+\beta}\cap[x_{1},y_{2}]\cdot X_{\alpha+2\beta}.$

If $x=x_{\alpha+\beta}(a)$, then $x_{1}=x_{\alpha}(a)$; if
$y=x_{\alpha+\beta}(b)$, then $y_{2}=x_{\beta}(b)$. In this case
$[x_{1},y_{2}]=x_{\alpha+\beta}(ab)\cdot x_{\alpha+2\beta}(\pm ab^{2})$ and

$X_{\alpha+\beta}\cap x_{\alpha+\beta}(ab)\cdot x_{\alpha+2\beta}(\pm
ab^{2})\cdot X_{\alpha+2\beta}=x_{\alpha+\beta}(ab).$

Therefore the ring $\langle X_{\alpha+\beta},\oplus,\otimes\rangle\cong R$ is
e-interpretable in $G$.

Case 4. If $\Phi=\mathbf{C}_{2}$ and the sets $X_{\alpha}$ are not Diophantine
in $G$, then by Proposition 5 the subgroup
$Y_{e_{1}+e_{2}}=\\{x_{e_{1}+e_{2}}(t)x_{2e_{2}}(t)\mid t\in R\\}$ is
Diophantine in $G$.

We e-interpret $R$ on $Y_{e_{1}+e_{2}}$ turning it into a ring $\langle
Y_{e_{1}+e_{2}},\oplus,\otimes\rangle$ as follows.

For $x,y\in Y_{e_{1}+e_{2}}$ we define

$x\oplus y=x\cdot y.$

Note that if $x=x_{e_{1}+e_{2}}(a)x_{2e_{2}}(a)$,
$y=x_{e_{1}+e_{2}}(b)x_{2e_{2}}(b)$, then

$xy=x_{e_{1}+e_{2}}(a)x_{2e_{2}}(a)x_{e_{1}+e_{2}}(b)x_{2e_{2}}(b)=(x_{e_{1}+e_{2}}(a)x_{e_{1}+e_{2}}(b))(x_{2e_{2}}(a)x_{2e_{2}}(b))=x_{e_{1}+e_{2}}(a+b)x_{2e_{2}}(a+b),$

which corresponds to the addition in $R$.

To define $x\otimes y$ for given $x,y\in Y_{e_{1}+e_{2}}$ we need to use
several tricks.

First, let $x_{1}\in G$ be such that

$x_{1}\in X_{2e_{1}}C=C(\Gamma_{2e_{1}})\text{ and
}[x_{1},x_{e_{2}-e_{1}}(1)]=x.$

Note that if $x=x_{e_{1}+e_{2}}(a)x_{2e_{2}}(a)$, then necessarily
$x_{1}=x_{2e_{1}}(a)c$, $c\in Z(G)$.

Second, let $y_{2}$ be

$y^{w_{2e_{1}}(1)}=x_{\mathbf{w}_{2e_{1}}(e_{1}+e_{2})}(b)x_{\mathbf{w}_{2e_{1}}(2e_{2})}(b)=x_{e_{2}-e_{1}}(b)x_{2e_{2}}(b).$

We see that

$[x_{1},y_{2}]=[x_{2e_{1}}(a),x_{e_{2}-e_{1}}(b)x_{2e_{2}}(b)]=[x_{2e_{1}}(a),x_{e_{2}-e_{1}}(b)]=x_{e_{2}+e_{1}}(ab)x_{2e_{2}}(ab^{2}).$

If we set

$x\otimes y:=([x_{1},y_{1}]C(\Gamma_{2e_{2}})\cap
Y_{e_{1}+e_{2}})=x_{e_{1}+e_{2}}(ab)x_{2e_{2}}(ab),$

since $[x_{1},y_{1}]C(\Gamma_{2e_{2}})=x_{e_{2}+e_{1}}(ab)x_{2e_{2}}(t)c$,
$t\in R$, $c\in Z(G)$.

Therefore the case 4 is also complete. $\blacksquare$

Now we prove the converse of Theorem 4. The result, we believe, is known in
folklore.

######  Proposition 6.

All Chevalley groups $G_{\pi}(\Phi,R)$, where $R$ is an arbitrary commutative
ring are all e-interpretable in $R$ (not using constants from $R$ other then
integers).

Proof. We represent an $n\times n$-matrix $x=(x_{ij})$ with entries in $R$ by
an $n^{2}$-tuple $\overline{x}$ over $R$, where

$\overline{x}=(x_{11},\dots,x_{1n},x_{21},\dots,x_{n1},\dots,x_{nn}).$

The matrix multiplication $\otimes$ on tuples from $R^{n^{2}}$ is defined by

$\overline{x}\otimes\overline{y}=\overline{z}\Longleftrightarrow\bigwedge_{i,j=1}^{n}z_{ij}=P_{ij}(\overline{x},\overline{y}),$

where $P_{ij}(\overline{x};\overline{y})$ is integer polynomial
$\sum\limits_{k=1}^{n}x_{ik}y_{kj}$. The multiplication $\otimes$ is clearly
Diophantine. To finish the description of the interpretations of the groups
$G_{\pi}(\Phi,R)$ in $R$ it suffices to define the corresponding subsets of
$R^{n^{2}}$ by Diophantine formulas.

But it is so by definition of Chevalley groups, which are all defined by
finite system of polynomial equations with integer coefficients.
$\blacksquare$

We are not able to show that the elementary Chevalley group $E_{\pi}(\Phi,R)$
is e-interpretable in $R$ for any commutative ring $R$.

However, the following holds.

######  Theorem 5.

If an elementary Chevalley group $E_{\pi}(\Phi,R)$ has bounded elementary
generation, then $E_{\pi}(\Phi,R)$ is $e$-interpretable in $R$.

##  6\. Diophantine problem in Chevalley groups

In this section we study Diophantine problem in Chevalley groups over rings.
Our arguments are often similar to the corresponding ones for classical linear
groups from [77], so we either state the results without proofs and refer the
reader to [77] or give a short sketch of the proof.

###  6.1. General reductions

We consider here the Diophantine problems of the type
$\mathcal{D}_{C}(G_{\pi}(\Phi,R))$, where $C$ is a countable subset of
$G_{\pi}(\Phi,R)$ equipped with an enumeration $\nu:\mathbb{N}\to C$. Denote
by $R_{C}$ the set of all elements of $R$ that occur in matrices from $C$. The
enumeration $\nu$ gives rise to an enumeration $\mu:\mathbb{N}\to R_{C}$,
where to construct $\mu$ it suffices to enumerate matrices in $C$ with respect
to $\nu$, for each matrix $\nu(n)$ enumerate its entries in some fixed order,
and combine all these into an enumeration $\mu$.

Now we can prove the main result of the paper.

######  Theorem 6.

If $\Phi$ is an indecomposable root system of a rank $>1$, $R$ is an arbitrary
commutative ring with $1$, then the Diophantine problem in any Chevalley group
$G_{\pi}(\Phi,R)$ is Karp equivalent to the Diophantine problem in $R$. More
precisely:

  * 1)

If $C$ is a countable subset of $G_{\pi}(\Phi,R)$ then
$\mathcal{D}_{C}(G_{\pi}(\Phi,R))$ Karp reduces to $\mathcal{D}_{R_{C}}(R)$.

  * 2)

If $T$ is a countable subset of $R$ then there is a countable subset $C_{T}$
of $G_{\pi}(\Phi,R)$ such that $\mathcal{D}_{T}(R)$ Karp reduces to
$\mathcal{D}_{C_{T}}(G_{\pi}(\Phi,R))$.

Proof. 1) follows directly from Proposition 6 (see Lemma 7.1 from [77]). 2)
comes from Theorem 4. $\blacksquare$

######  Theorem 7.

Let $\Phi$ be an indecomposable root system of a rank $>1$ and $R$ an
arbitrary commutative ring with $1$. If the elementary Chevalley group
$E_{\pi}(\Phi,R)$ has bounded elementary generation, then the Diophantine
problem in $E_{\pi}(\Phi,R)$ is Karp equivalent to the Diophantine problem in
$R$.

Proof. The result follows from Theorem 5. $\blacksquare$

###  6.2. Diophantine problem in Chevalley groups over rings of algebraic
integers and number fields

By a _number field_ $F$ we mean a finite algebraic extension of $\mathbb{Q}$.
The _ring of algebraic integers_ $\mathcal{O}_{F}$ of a number field $F$ is
the subring of $F$ consisting of all roots of monic polynomials with integer
coefficients.

It is a classical result that the Diophantine problem in $\mathbb{Z}$ is
undecidable [75].

######  Theorem 8 (compare with Theorem 7.2 from [77]).

If $\Phi$ is a indecomposable root system of a rank $>1$, then the Diophantine
problem in all Chevalley groups $G_{\pi}(\Phi,\mathbb{Z})$ is Karp equivalent
to the Diophantine problem in $\mathbb{Z}$, in particular, it is undecidable.

The following is one of the major conjectures in number theory.

######  Conjecture 1.

The Diophantine problem in $\mathbb{Q}$, as well as in any number field $F$,
or any ring of algebraic integers $\mathcal{O}$, is undecidable.

For $\mathbb{Q}$ and any its finite extension $F$ the conjecture above is wide
open. However, for the rings of algebraic integers $\mathcal{O}_{F}$ of the
fields $F$ there are results where the undecidability of the Diophantine
problem is confirmed. Namely, it is known that $\mathbb{Z}$ is Diophantine in
$\mathcal{O}_{F}$ if $[F:\mathbb{Q}]=2$ or $F$ is totally real [33, 35], or
$[F:\mathbb{Q}]>3$ and $F$ has exactly two nonreal embeddings into the field
of complex numbers [84], or $F$ is an Abelian number field [96]. We refer to
two surveys and a book [83, 85, 95] for details on this matter.

The following result moves the Diophantine problem in Chevalley groups over
number fields or rings of algebraic integers from group theory to number
theory.

######  Theorem 9.

Let $\Phi$ be an indecomposable root system of a rank $>1$ and $R$ either a
number field or a ring of algebraic integers. Then Conjecture 1 holds for $R$
if and only if the Diophantine problem in the Chevalley group
$G_{\pi}(\Phi,R)$ is undecidable.

###  6.3. Diophantine problem in Chevalley groups over finitely generated
commutative rings

To move forward we need to recall some definitions.

The _characteristic_ of a ring with multiplicative identity (i.e. a _unitary_
ring) is the minimum positive integer $n$ such that
$1+\overset{n}{\dots}+1=0$. By _rank_ of a ring $R$ we refer to the rank of
$R$ seen as an abelian group (i.e. forgetting its multiplication operation):
that is, the maximum number $m$ of nonzero elements $r_{1},\dots,r_{m}\in R$
such that whenever $a_{1}r_{1}+\dots+a_{m}r_{m}=0$ for some integers
$r_{1},\dots,r_{m}$, we have $r_{i}a_{i}=0$ for all $i=1,\dots,m$. If $R$ is
an integral domain, then its rank coincides with its dimension as a
$\mathbb{F}_{p}$-vector space if $R$ has positive characteristic $p$, and
otherwise it coincides with the dimension of $R$ seen as a
$\mathbb{Z}$-module.

The following result from [47] describes the current state of the Diophantine
problem in finitely generated commutative rings. Note that in [33, 34] Denef
showed that the Diophantine problems in polynomial rings with coefficients in
integral domains are undecidable.

######  Theorem 10 ([47]).

Let $R$ be an infinite finitely generated associative commutative unitary
ring. Then one of the following holds:

  1. (1)

If $R$ has positive characteristic $n>0$, then the ring of polynomials
$\mathbb{F}_{p}[t]$ is e-interpretable in $R$ for some transcendental element
$t$ and some prime integer $p$; and $\mathcal{D}(R)$ is undecidable.

  2. (2)

If $R$ has zero characteristic and it has infinite rank then the same
conclusions as above hold: the ring of polynomials $\mathbb{F}_{p}[t]$ is
e-interpretable in $R$ for some $t$ and $p$; and $\mathcal{D}(R)$ is
undecidable.

  3. (3)

If $R$ has zero characteristic and it has finite rank then a ring of algebraic
integers $\mathcal{O}$ is e-interpretable in $R$.

This together with Theorem 6 implies the following result which completely
clarifies the situation with the Diophantine problem in Chevalley groups over
infinite finitely generated commutative unitary rings.

######  Theorem 11.

Let $\Phi$ be an indecomposable root system of a rank $>1$, $R$ is an
arbitrary infinite finitely generated commutative ring with $1$, and
$G_{\pi}(\Phi,R)$ the corresponding Chevalley group. Then:

  * 1)

If $R$ has positive characteristic then the Diophantine problem in
$G_{\pi}(\Phi,R)$ is undecidable.

  * 2)

If $R$ has zero characteristic and it has infinite rank then the Diophantine
problem in $G_{\pi}(\Phi,R)$ is undecidable.

  * 3)

If $R$ has zero characteristic and it has finite rank then the Diophantine
problem in some ring of algebraic integers $\mathcal{O}$ is Karp reducible to
the Diophantine problem in $G_{\pi}(\Phi,R)$. Hence if Conjecture 1 holds then
the Diophantine problem in $G_{\pi}(\Phi,R)$ is undecidable.

###  6.4. Diophantine problem in Chevalley groups over algebraically closed
fields

Let $R$ be an algebraically closed field. We need the following known results
about $R$ (see [77] for details and references).

  * 1)

If $A$ is a computable subfield of $R$ then the first-order theory $Th_{A}(R)$
of $R$ with constants from $A$ in the language is decidable. In particular,
the Diophantine problem $\mathcal{D}_{A}(R)$ is decidable.

  * 2)

If $A$ is a computable subfield of $R$ then the algebraic closure $\bar{A}$ of
$A$ in $R$ is computable.

######  Theorem 12.

Let $\Phi$ be an indecomposable root system of a rank $>1$, $R$ an
algebraically closed field, and $G_{\pi}(\Phi,R)$ the corresponding Chevalley
group. If $A$ is a computable subfield of $R$, then the Diophantine problem in
$G_{\pi}(\Phi,R)$ with constants from $G_{\pi}(\Phi,A)$ is decidable (under a
proper enumeration of $G_{\pi}(\Phi,A)$).

###  6.5. Diophantine problem in Chevalley groups over reals

Let $R=\mathbb{R}$ be the field of real numbers and $A$ a countable (or
finite) subset of $\mathbb{R}$.

Our treatment of the Diophantine problem in Chevalley groups over $\mathbb{R}$
is based on the following two results on the Diophantine problem in
$\mathbb{R}$ which are known in the folklore. For details we refer to [77].

######  Proposition 7 ([77], Proposition 7.4).

Let $A$ be a finite or countable subset of $\mathbb{R}$. Then the Diophantine
problem in $\mathbb{R}$ with coefficients in $A$ is decidable if and only if
the ordered subfield $F(A)$ is computable. Furthermore, in this case the whole
first-order theory $Th_{A}(\mathbb{R})$ is decidable.

Recall that a real $a\in\mathbb{R}$ is _computable_ if its standard decimal
expansion $a=a_{0}.a_{1}a_{2}\ldots$ is computable, i.e., the integer function
$n\mapsto a_{n}$ is computable. In other words, $a$ is computable if and only
if one can effectively approximate it by rationals with any precision. The set
of all computable reals $\mathbb{R}^{c}$ forms a real closed subfield of
$\mathbb{R}$, in particular $\mathbb{R}^{c}$ is first-order equivalent to
$\mathbb{R}$.

In the following Proposition we collect some facts about computable ordered
subfields of $\mathbb{R}$.

######  Proposition 8 ([77], Proposition 7.5).

The following holds:

  * 1)

Every ordered computable subfield of $\mathbb{R}$ is contained in
$\mathbb{R}^{c}$.

  * 2)

The ordered subfield $\mathbb{R}^{c}\leq\mathbb{R}$ with the induced order
from $\mathbb{R}$ is not computable.

  * 3)

If $F$ is a computable ordered field, then its real closure is also
computable. In particular, if $F$ is a computable subfield of $\mathbb{R}$
then the algebraic closure $\bar{F}$ of $F$ in $\mathbb{R}$ is a computable
ordered field.

  * 4)

If $a_{1},\ldots,a_{m}$ are computable reals then the ordered subfield
$\mathbb{Q}(a_{1},\ldots,a_{m})\leq\mathbb{R}$ with the induced order from
$\mathbb{R}$ is computable.

######  Corollary 3.

The following holds:

  * •

The Diophantine problem in $\mathbb{R}$ with coefficients in $\mathbb{R}^{c}$
is undecidable;

  * •

The Diophantine problem in $\mathbb{R}$ with coefficients in any finite subset
of $\mathbb{R}^{c}$ is decidable;

  * •

The Diophantine problem in $\mathbb{R}$ with coefficients in $\\{a\\}$, where
$a$ is not computable, is undecidable.

Recall that a matrix $A\in\,\mathrm{GL}\,_{n}(\mathbb{R})$ is called
_computable_ if all entries in $A$ are computable real numbers.

Chevalley groups $G_{\pi}(\Phi,\mathbb{R})$ are matrix algebraic groups over
$\mathbb{R}$, hence one can view their elements as matrices

######  Theorem 13.

Let $\Phi$ be an indecomposable root system of a rank $>1$ and
$G_{\pi}(\Phi,\mathbb{R})$ the Chevalley group over the field of real numbers
$\mathbb{R}$. If $A$ is a computable ordered subfield of $\mathbb{R}$ then the
first-order theory $Th(G_{\pi}(\Phi,\mathbb{R}))$ with constants from
$G_{\pi}(\Phi,A)$ is decidable. In particular, the Diophantine problem in
$G_{\pi}(\Phi,\mathbb{R})$ with constants from $G_{\pi}(\Phi,A)$ is decidable
(under a proper enumeration of $G_{\pi}(\Phi,A)$).

######  Theorem 14.

Let $\Phi$ be an indecomposable root system of a rank $>1$ and
$G_{\pi}(\Phi,\mathbb{R}^{c})$ the Chevalley group over the field of
computable real numbers $\mathbb{R}^{c}$. Then the following holds:

  * 1)

The Diophantine problem in the computable group $G_{\pi}(\Phi,\mathbb{R}^{c})$
is undecidable.

  * 2)

For any finitely generated subgroup $C$ of $G_{\pi}(\Phi,\mathbb{R}^{c})$ the
Diophantine problem in $G_{\pi}(\Phi,\mathbb{R}^{c})$ with coefficients in $C$
is decidable.

We say that a matrix $A\in\,\mathrm{GL}\,_{n}(\mathbb{R})$ is _computable_ if
all entries in $A$ are computable reals, i.e.,
$A\in\,\mathrm{GL}\,_{n}(\mathbb{R}^{c})$. Hence the computable matrices in
$\,\mathrm{SL}\,_{n}(\mathbb{R})$ are precisely the matrices from
$\,\mathrm{SL}\,_{n}(\mathbb{R}^{c})$. Since elements of a Chevalley group
$G_{\pi}(\Phi,\mathbb{R})$ are represented by matrices from
$\,\mathrm{SL}\,_{n}(\mathbb{R})$ we say that an element $g\in
G_{\pi}(\Phi,\mathbb{R})$ is computable if it is represented by a computable
matrix from $\,\mathrm{SL}\,_{n}(\mathbb{R}^{c})$.

######  Theorem 15.

Let $\Phi$ be an indecomposable root system of a rank $>1$ and
$G_{\pi}(\Phi,\mathbb{R})$ is the corresponding Chevalley group over the field
of reals $\mathbb{R}$. If an element $g\in E_{\pi}(\Phi,\mathbb{R})$ is not
computable then the Diophantine problem for equations with coefficients in
$\\{x_{\alpha}(1)\mid\alpha\in\Phi\\}\cup\\{g\\}$ is undecidable in any large
subgroup of $G_{\pi}(\Phi,\mathbb{R})$.

###  6.6. Diophantine problem in Chevalley groups over $p$-adic numbers

Similar to the case of reals one can define computable $p$-adic numbers for
every fixed prime $p$. Recall, that every $p$-adic number $a\in\mathbb{Q}_{p}$
has a unique presentation in the form $a=p^{m}\xi$, where $m\in\mathbb{Z}$ and
$\xi$ is a unit in the ring $\mathbb{Z}_{p}$. In its turn, the unit $\xi$ is
uniquely determined by a sequence of natural numbers
$\\{\xi(i)\\}_{i\in\mathbb{N}}$, where

$0\leq\xi(i)<p^{i+1},\ \xi(i+1)=\xi(i)(\text{ mod }p^{i+1}),\
(i\in\mathbb{N}).$

The $p$-adic number $a=p^{m}\xi$ is computable if the sequence $i\to\xi(i)$ is
computable. In this case the sequence $\\{\xi(i)\\}_{i\in\mathbb{N}}$ gives an
effective $p$-adic approximation of $\xi$. It is known (see, for example
[76]), that the set $\mathbb{Q}_{p}^{c}$ of all computable $p$-adic numbers
forms a subfield of $\mathbb{Q}_{p}$, such that
$\mathbb{Q}_{p}\equiv\mathbb{Q}_{p}^{c}$. Observe also that the ring
$\mathbb{Z}_{p}$ is Diophantine in $\mathbb{Q}_{p}$. More precisely, if $p\neq
2$, then $\mathbb{Z}_{p}$ is defined in $\mathbb{Q}_{p}$ by formula $\exists
y(1+px^{2}=y^{2})$, while if $p=2$ then $\mathbb{Z}_{p}$ is defined by the
formula $\exists y(1+2x^{3}=y^{3})$ (see [41]).

The following results were shown in [76]:

  * a)

$Th(\mathbb{Z}_{p},a_{1},\ldots,a_{n})$ is decidable if and only if each of
$a_{1},\ldots,a_{n}$ is a computable $p$-adic number.

  * b)

$Th(\mathbb{Q}_{p},a_{1},\ldots,a_{n})$ is decidable if and only if each of
$a_{1},\ldots,a_{n}$ is a computable p-adic number.

  * c)

If a $p$-adic integer $a$ is not computable then equations with constants from
$\mathbb{Q}\cup\\{a\\}$ are undecidable in $\mathbb{Z}_{p}$.

  * d)

If a $p$-adic number $a\in\mathbb{Q}_{p}$ is not computable then equations
with constants from $\mathbb{Q}\cup\\{a\\}$ are undecidable in
$\mathbb{Q}_{p}$.

######  Theorem 16.

Let $\Phi$ be an indecomposable root system of a rank $>1$. Then the following
holds:

  * 1)

Let $a_{1},\ldots,a_{m}\in\mathbb{Q}_{p}^{c}$ and
$A=\mathbb{Q}(a_{1},\ldots,a_{m})$ is the subfield of $\mathbb{Q}_{p}$
generated by $a_{1},\ldots,a_{m}$. Then the first-order theory
$Th(G_{\pi}(\Phi,\mathbb{Q}_{p}))$ with constants from $G_{\pi}(\Phi,A)$ is
decidable. In particular, the Diophantine problem in
$G_{\pi}(\Phi,\mathbb{Q}_{p})$ with constants from $G_{\pi}(\Phi,A)$ is
decidable (under a proper enumeration of $G_{\pi}(\Phi,A)$).

  * 2)

Let $a_{1},\ldots,a_{m}\in\mathbb{Z}_{p}^{c}$ and
$A=\mathbb{Z}(a_{1},\ldots,a_{m})$ is the subring of $\mathbb{Z}_{p}$
generated by $a_{1},\ldots,a_{m}$. Then the first-order theory
$Th(G_{\pi}(\Phi,\mathbb{Q}_{p}))$ with constants from $G_{\pi}(\Phi,A)$ is
decidable. In particular, the Diophantine problem in
$G_{\pi}(\Phi,\mathbb{Q}_{p})$ with constants from $G_{\pi}(\Phi,A)$ is
decidable (under a proper enumeration of $G_{\pi}(\Phi,A)$).

Proof. It follows from Theorem 6 and the results a) and b) above.
$\blacksquare$

We say that a matrix $A\in\,\mathrm{GL}\,_{n}(\mathbb{Q}_{p})$ is _computable_
if all entries in $A$ are computable p-adic numbers, i.e.,
$A\in\,\mathrm{GL}\,_{n}(\mathbb{Q}_{p}^{c})$. Hence the computable matrices
in $\,\mathrm{SL}\,_{n}(\mathbb{Q}_{p})$ are precisely the matrices from
$\,\mathrm{SL}\,_{n}(\mathbb{Q}_{p}^{c})$. Since elements of a Chevalley group
$G_{\pi}(\Phi,\mathbb{Q}_{p})$ are represented by matrices from
$\,\mathrm{SL}\,_{n}(\mathbb{Q}_{p})$ we say that an element $g\in
G_{\pi}(\Phi,\mathbb{Q}_{p})$ is computable if it is represented by a
computable matrix from $\,\mathrm{SL}\,_{n}(\mathbb{Q}_{p}^{c})$. Similarly,
we define computable elements in a Chevalley group
$G_{\pi}(\Phi,\mathbb{Z}_{p})$.

######  Theorem 17.

Let $\Phi$ be an indecomposable root system of a rank $>1$ and
$G_{\pi}(\Phi,\mathbb{Q}_{p})$ $(G_{\pi}(\Phi,\mathbb{Z}_{p}),p\neq 2)$ the
corresponding Chevalley group over $\mathbb{Q}_{p}$ $(\mathbb{Z}_{p})$. If an
element $g\in E_{\pi}(\Phi,\mathbb{Q}_{p})$ $(g\in
E_{\pi}(\Phi,\mathbb{Z}_{p}),p\neq 2)$ is not computable then the Diophantine
problem for equations with coefficients in
$\\{x_{\alpha}(1)\mid\alpha\in\Phi\\}\cup\\{g\\}$ is undecidable in any large
subgroup of $G_{\pi}(\Phi,\mathbb{Q}_{p})$
$(G_{\pi}(\Phi,\mathbb{Z}_{p}),p\neq 2)$.

## References

  * [1] Abe E. _Chevalley groups over local rings_. Tohoku Math. J., 21(3), 1969, 474–494.
  * [2] Abe E. _Normal subgroups of Chevalley groups over commutative rings_. Contemp. Math., 83, 1989, 1–17.
  * [3] Abe E., Suzuki K. _On normal subgroups of Chevalley groups over commutative rings._ Tohoku Math. J., 28(1), 1976, 185–198.
  * [4] Abe E., Hurley J. _Centers of Chevalley groups over commutative rings_. Comm. Algebra, 1988, 16(1), 57–74.
  * [5] Ax J., Kochen S. _Diophantine problems over local fields._ I, II, Amer. J. Math. 1965, 87, 605–648.
  * [6] Ax J., Kochen S. _Diophantine problems over local fields._ III, Amer. J. Math. 1966, 83, 437–456.
  * [7] Avni N., Lubotzky A., Meiri C. _First order rigidity of non-uniform higher rank arithmetic groups._ Invent. Math., 217(1), 2019, 219–240.
  * [8] Avni N., Meiri C. _On the model theory of higher rank arithmetic groups_. arXiv:2008.01793, 2022.
  * [9] Beidar C.I., Mikhalev A.V. _On Mal’cev’s theorem on elementary equivalence of linear groups_. Contemporary mathematics, 131(1), 1992, 29–35.
  * [10] Belegradek O. V. _The model theory of unitriangular groups_. Ann. Pure App. Logic, 1994, 68, 225–261.
  * [11] Borel A. _Properties and linear representations of Chevalley groups._ Seminar in algebraic groups, M., 1973, 9–59.
  * [12] Bragin V., Bunina E. _Elementary equivalence of linear groups over rings with a finite number of central idempotents and over Boolean rings_. Journal of Mathematical Sciences, 201, 2014, 438–445.
  * [13] Bourbaki N. _Groupes et Algébres de Lie._ Hermann, 1968.
  * [14] Bunina E. _Elementary equivalence of unitary linear groups over rings and skewfields._ Russian Mathematical Surveys, 53(2), 1998, 137–138.
  * [15] Bunina E., Mikhalev A.V. _Combinatorial and logical aspects of linear groups and Chevalley groups_. Acta Applicandae Mathematicae, 85(1–3), 2005, 57–74.
  * [16] Bunina E. _Elementary equivalence of Chevalley groups over fields._ J. Math Sci, 152, 2008, 155–190.
  * [17] Bunina E. _Elementary equivalence of Chevalley groups over local rings_. Sbornik: Mathematics, 201(3), 2010, 321–337.
  * [18] Bunina E. _Automorphisms of Chevalley groups of different types over commutative rings_. Journal of Algebra, 355(1), 2012, 154–170.
  * [19] Bunina E. _Isomorphisms and elementary equivalence of Chevalley groups over commutative rings._ Sbornik: Mathematics, 210(8), 2019, 1067–1091.
  * [20] Bunina E. _Regular bi-interpretability of Chevalley groups over local rings._ Arxiv.org/abs/2208.13623, 2022.
  * [21] Carter R.W. _Simple groups of Lie type_ , 2nd ed. Wiley, London et al., 1989.
  * [22] Casals-Ruiz M., Kazachkov I. _On systems of equations over free products of groups_. Journal of Algebra, 2011, 333(1), 368–426.
  * [23] Casals-Ruiz M., Kazachkov I. _On Systems of Equations Over Free Partially Commutative Groups_. Memoirs of the American Mathematical Society, 2011, American Mathematical Society.
  * [24] Ciobanu L., Diekert V., Elder M. _Solution sets for equations over free groups are EDT0L languages_. International Journal of Algebra and Computation, 2016, 26(5), 843–886.
  * [25] Ciobanu L., Elder M. _The complexity of solution sets to equations in hyperbolic groups_ , arXiv:2001.09591 [math.GR].
  * [26] Chang C., Keisler H. _Model Theory_. North Holland, 1990.
  * [27] Chevalley C. _Certain schemas des groupes semi-simples._ Sem. Bourbaki, 219, 1960–1961, 1–16.
  * [28] Cohn P. _On the structure of the $GL_{2}$ of a ring_. Publ. Math. Inst. Hautes Et. Sci., 30, 1966, 365–413.
  * [29] Dahmani F., Guirardel V. _Foliations for solving equations in groups: free, virtually free, and hyperbolic groups_ , Journal of Topology, 2016, 3(2), 343–404.
  * [30] Davis M., Putnam H., Robinson J. _The Decision Problem for Exponential Diophantine Equations_. Annals of Mathematics, 74(3), 1961, 425–436.
  * [31] Demazure M., Gabriel P. _Groupes algébriques._ I. North Holland, Amsterdam et al., 1970, 1–770.
  * [32] Denef J., Lipshitz L. _Diophantine Sets over Some Rings of Algebraic Integers_. Journal of the London Mathematical Society, 1978, 18(3), 385-391.
  * [33] J. Denef, _Hilbert’s tenth problem for quadratic rings._ Proc. Amer. Math. Soc. 48 (1975), 214-220.
  * [34] J. Denef, _The Diophantine problem for polynomial rings of positive characteristic_ , in: Logic Colloquium ’78, North-Holland, 1979, 131-145.
  * [35] J. Denef, Diophantine sets of algebraic integers, II, Trans. Amer. Math. Soc. 257, 1980, 227–236.
  * [36] Diekert V., Jez A., Plandowski W. _Finding all solutions of equations in free groups and monoids with involution._ Inf. Comput., 2016, 251, 263–286.
  * [37] Diekert V., Lohrey M. _Word equations over graph products_. International Journal of Algebra and Computation, 2008, 18(3), 493–533.
  * [38] Diekert V., Muscholl A, _Solvability of equations in graph groups is decidable_. International Journal of Algebra and Computation, 2006, 16(6), 1047–1069.
  * [39] Duchin M., Liang H., Shapiro M. _Equations in nilpotent groups_. Proc. Amer. Math. Soc., 2015, 143(11), 4723–4731.
  * [40] Ershov Yu. _On elementary theories of local fields_. Algebra i Logika, Sem 4, 1965, 2, 5–30.
  * [41] Ershov Yu. _Decidability problems and constructible models_. Moscow, Nauka, 1980.
  * [42] Ershov Yu. _Algorithmic problems of the theory of fields (positive aspects)_. Handbook of Mathematical Logic, 1982, 3, 268–353, Nauka.
  * [43] Ershov Yu., Goncharov S. _Constructive models._ Siberian School of Algebra and Logic. Consultants Bureau, New York, 2000.
  * [44] Garreta A., Miasnikov A., Ovchinnikov D. _Full rank presentations and nilpotent groups: structure, Diophantine problem, and genericity_. Journal of Algebra, 2020, 556, 1–34.
  * [45] Garreta A., Miasnikov A., Ovchinnikov D. _Diophantine problems in solvable groups_. Bulletin of Mathematical Sciences, 2020, 10(1), DOI: 10.1142/S1664360720500058
  * [46] Garreta A., Miasnikov A., Ovchinnikov D. _Diophantine problems in rings and algebras: undecidability and reductions to rings of algebraic integers_ , arXiv: 1805.02573
  * [47] Garreta A., Miasnikov A., Ovchinnikov D. _Diophantine problems in commutative rings_ , Preprint.
  * [48] Goncharov S. _Countable Boolean allgebras and decidability_. Novosibirsk: Science books, 1996 (in Russian).
  * [49] Hazrat R., Vavilov N. _$K_{1}$ of Chevalley groups are nilpotent_. Journal of Pure and Applied Algebra, 179(1-2), 2003, 99–116.
  * [50] Hodges W. _Model Theory_. Cambridge University Press, Cambridge, 1993.
  * [51] Humphreys J. _Introduction to Lie algebras and representation theory._ Springer–Verlag New York, 1978.
  * [52] Iwahori N., Matsumoto H. _On some Bruhat decomposition and structure of the Hecke rings of $p$-adic Chevalley groups_, Publ. Math. Inst. Haut. Etudes Sci., 1965, 25, 5–48.
  * [53] Jarden M., Lubotzky A. _Elementary equivalence of profinite groups_. Bulletin of the London Mathematical Society, 40(5), 887–896.
  * [54] Jez A. _Recompression: a simple and powerful technique for word equations_. Journal of the ACM, 63(1):4:1–4:51, 2016, ISSN 0004-5411/2015. doi: 10.1145/2743014. URL http://dx.doi.org/10.1145/2743014.
  * [55] Jez A. _Word equations in linear space_. arXiv:1702.00736 [cs.FL]
  * [56] Keisler H.J. _Ultraproducts and elementary models_. Indagationes Mathematicae, 23, 1961, 477–495.
  * [57] Kharlampovich O., Myasnikov A. _Irreducible affine varieties over a free group. II: Systems in triangular quasi-quadratic form and description of residually free groups._ J. of Algebra, 1998, 200(2), 517–570.
  * [58] Kharlampovich O., Myasnikov A. _Model theory and algebraic geometry in groups, non-standard actions and algorithmic problems_. Proceedings of the Intern. Congress of Mathematicians 2014, Seoul, v. 2, invited lectures, 223–244.
  * [59] Kharlampovich O., Myasnikov A. _Undecidability of Equations in Free Lie Algebras_. Transactions of the American Mathematical Society, 2017, 08 ??
  * [60] Kharlampovich O., Myasnikov A. _Equations in Algebras_. International Journal of Algebra and Computation, 2018, 28(8), 1517-1533.
  * [61] Kharlampovich O., Myasnikov A. _Elementary theory of free non-abelian groups_. Journal of Algebra. 302, 2006, 451–552.
  * [62] Kharlampovich O., Myasnikov A., Sohrabi M. _Rich groups, weak second order logic, and applications_. arXiv:2109.13133v1, 2021.
  * [63] Khelif A. _Bi-interpretabilit´e et structures QFA: ´etude des groupes r´esolubles et des anneaux commutatifs_. C. R. Acad. Sci. Paris, Ser. I, 345, 2007, 59–61.
  * [64] Kopeiko V.I., The stabilization of symplectic groups over a polynomial ring, Math. U.S.S.R. Sbornik, 1978, 34, 655-669.
  * [65] Kunyavskii B., Plotkin E., Vavilov N. _Bounded generation and commutator width of Chevalley groups: function case_. arXiv:2204.10951, 2022.
  * [66] Kunyavskii B., Plotkin E., Vavilov N. ???
  * [67] Lasserre C. _Polycyclic-by-finite groups and first-order sentences_. J. Algebra, 396, 2013, 18–38.
  * [68] Makanin G. S. _Equations in a free group_ (Russian). Izv. Akad. Nauk SSSR, Ser. Mat., 1982, 46(1),199–1273 (transl. in Math. USSR Izv., 21, 1983; MR 84m:20040).
  * [69] Makanin G. S. _Decidability of the universal and positive theories of a free group_. Izv. Akad. Nauk SSSR, Ser. Mat., 1985, 48(1), 735–749 (transl. in Math. USSR Izv., 1985, 25; MR 86c:03009).
  * [70] Maltsev A.I. _On elementary properties of linear groups_. Problems of Mathematics and Mechanics, Novosibirsk, 1961 (in Russian).
  * [71] Maltsev A.I. _On isomorphic matrix representations of infinite groups_. Rec. Math. [Mat. Sbornik] 8(50), 1940, 405–422 (Russian. English summary).
  * [72] Maltsev A.I. _Constructive algebras_ I, Yspehi, Mat. Nayk, 1961, 3, 3–60.
  * [73] Marker D. _Model theory: an introduction_. Springer, 2002.
  * [74] Matsumoto H., _Sur les sous-groupes arithmétiques des groupes semi-simples deployés_. Ann. Sci. Ecole Norm. Sup., 4eme ser., 2, 1969, 1–62.
  * [75] Matijasevich Yu. _The Diophantineness of enumerable sets_. Doklady Akademii Nauk USSR, 1970, 191, 279–282.
  * [76] A. Myasnikov and V. Remeslennikov, Recursive p-adic numbers and elementary theories of finitely generated pro-p groups, 1988 American Mathematical Society, Mathematics of the USSR-Izvestiya, Volume 30, Number 3.
  * [77] Myasnikov A., Sohrabi M. _The Diophantine problem in the classical matrix groups_. Izv. RAN. Ser. Mat., 85(6), 2021, 205–244.
  * [78] Myasnikov A., Sohrabi M. _Bi-interpretability with $\mathbb{Z}$ and models of the complete elementary theories of $\,\mathrm{SL}\,_{n}(\mathcal{O})$, $\,\mathrm{GL}\,_{n}(\mathcal{O})$, $T_{n}(\mathcal{O})$, $n\geqslant 3$_. Arxiv:2004.03585, 2020.
  * [79] Myasnikov A. G., Sohrabi M. _On groups elementarily equivalent to a group of triangular matrices $T_{n}(R)$_, arXiv:1609.09802.
  * [80] Nies A. _Separating classes of groups by first-order formulas_. International Journal of Algebra and Computation, 13, 2003, 287–302.
  * [81] Nies A. _Describing groups_. The Bulletin of Symbolic Logic, 13(3), 2007, 305–339.
  * [82] Oger F., Sabbagh G. _Quasi-finitely axiomatizable nilpotent groups_. Journal of Group Theory, 9(1), 2006, 95–106.
  * [83] Pheidas T., Zahidi K. _Undecidability of existential theories of rings and fields: A survey_. Contemporary Mathematics, 2000, 270, 49–106.
  * [84] T. Pheidas, _Hilbert’s Tenth Problem for a class of rings of algebraic integers_ , Proc. Amer. Math. Soc. 104, 1988, 611–620.
  * [85] B. Poonen, Hilbert’s Tenth Problem over rings of number-theoretic interest, Notes for Arizona Winter School on ”Number theory and logic”,2003.
  * [86] Poonen B. _Hilbert’s Tenth Problem over rings of number-theoretic interest_. Notes for Arizona Winter School on “Number theory and logic”, 2003.
  * [87] Rabin M. _Computable algebra, general theory and theory of computable fields_ , Trans Amer. Math. Soc., 1960, 95(2), 341–360.
  * [88] Razborov A. _On systems of equations in a free group_. Math. USSR, Izvestiya, 1985, 25(1), 115–162.
  * [89] Razborov A. _On systems of equations in a free group._ PhD thesis, Steklov Math. Institute, Moscow, 1987.
  * [90] Rips E., Sela Z. _Canonical representatives and equations in hyperbolic groups_. Inventiones mathematicae, 1995, 120(1), 489–510.
  * [91] Romankov V. _Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings_. Algebra and Logic, 1977, 16(4), 310–320.
  * [92] Segal D., Tent K. _Defining $R$ and $G(R)$_. arXiv:2004.13407, 2020.
  * [93] Sela Z. _Diophantine geometry over groups. VI. The elementary theory of a free group._ Geom. Funct. Anal. 16(3), 2016, 707–730.
  * [94] Shelah S., _Every two elementarily equivalent models have isomorphic ultrapowers_. Israel J. Math., 10, 1971, 224–233.
  * [95] Shlapentokh A. _Hilbert’s Tenth Problem: Diophantine Classes and Extensions to Global Fields_. New Mathematical Monographs, 2007, Cambridge University Press.
  * [96] H. N. Shapiro, A. Shlapentokh, Diophantine relationships between algebraic number fields, Communications on Pure and Applied Mathematics, 42,8, 1989, 1113–1122.
  * [97] Smolensky A., Sury B., Vavilov N. _Gauss decomposition for Chevalley groups, revisited_. International Journal of Group Theory, 2012, 01(1), 3–16.
  * [98] Stein M.R. _Surjective stability in dimension $0$ for $K_{2}$ and related functors_. Trans. Amer. Soc., 178(1), 1973, 165–191.
  * [99] Steinberg R. _Lectures on Chevalley groups_. Yale University, 1967.
  * [100] Suslin A.A. _On a theorem of Cohn_. J. Sov. Math., 17(2), 1981, 1801–1803.
  * [101] Swan R. _Generators and relations for certain special linear groups_. Adv. Math., 6, 1971, 1–77.
  * [102] Szmielew W. _Elementary properties of Abelian groups_. Fundamenta Mathematica, 41, 1955, 203–271.
  * [103] Taddei G. _Normalite des groupes elementaire dans les groupes de Chevalley sur un anneau_ Contemp. Math., 55(II), 1986, 693–710.
  * [104] Tarski A. _A decision method for elementary algebra and geometry_. 2nd revised ed., Berkeley, Los Angeles, 1951.
  * [105] Vavilov N.A. _Structure of Chevalley groups over commutative rings_. Proc. Conf. Nonassociative Algebras and Related Topics (Hiroshima, 1990), World Scientific, Singapore, 1991, 219–335.
  * [106] Vavilov N.A., Plotkin E.B. _Chevalley groups over commutative rings. I. Elementary calculations._ Acta Applicandae Math., 45, 1996, 73–115.
  * [107] Zilber B.I. _Some model theory of simple algebraic groups over algebrailcally closed fileds._ Colloq. Mathematics. 2, 1984, 173–180.