text:
By Topic

• Abstract

SECTION I

## INTRODUCTION

The total energy consumption of three major telecommunication operators in China already accounted for approximately two thousandths of the comprehensive overall energy consumption of the Chinese society in 2014, as mentioned by the Vice President of China Mobile Communications Corporation in session 30 of Boao Forum for Asia Annual Conference 2016. Moreover, as the explosive growths of user demand in diverse wireless data services and computation power of mobile devices continue to intensify, energy consumption of wireless communication infrastructures has become a serious and vital issue, which cannot be effectively and efficiently accommodated by the current fourth generation (4G) of wireless communications technology [1]. Thus it is of great importance to develop and adopt green and energy-efficient broadband transmission schemes in the framework of the upcoming fifth generation (5G) communication systems. Massive multiple-input multiple-output (MIMO) [2], which is also known as large MIMO, full-dimension MIMO, or large-scale antenna systems, is one of those green communication technologies [3] that has the potential to significantly alleviate the energy and spectrum consumption crises in the near future. Massive MIMO is currently under extensive investigations by both scientists and industrialists. It is widely considered to be a promising and critical technology to meet the requirements of unprecedented high energy efficiency and high spectral efficiency for green communications and networking envisioned in 5G systems [4] [5] [6] [7] [8] [9], along with the forthcoming Internet of Things (IoT) [10].

Specifically, massive MIMO is capable of shifting most of the signal processing and computing loads from the user terminals (UTs) to the base stations (BSs), by leveraging time-division duplexing (TDD) and large antenna arrays with several hundred service antennas or more [11]. The energy consumption of battery-powered UTs can thus be significantly reduced, and the corresponding service life can be effectively prolonged. Furthermore, the exploitation of excess service antennas and law of large numbers at the BS enables the radiated energy to be extremely focused into certain intended regions in space, comparing with conventional MIMO schemes. This helps dramatically improve the signal beamforming sharpness and selectivity, which leads to much less interference between different UTs. Therefore, tens or more UTs are allowed to be simultaneously served in the same time-frequency resource block without badly interfering with each other [4] [5] [6]. Remarkable reduction in the required radiated power is also obtained in transmitting signals on both forward and reverse links [8], [9], while maintaining a certain system throughput. In addition to enhancing energy efficiency and spectral efficiency, the much sharper and finer wave beams with better directivity and selectivity, which are sophisticatedly generated by a massive MIMO BS under either line-of-sight or cluttered channel conditions, also benefit the physical layer security during signal transmissions [12], [13].

Physical layer security exploits the inherent characteristics and independent randomness of communication channels and noise to achieve secure transmissions [14]. Due to the open nature of wireless channels and the significance of information security, it has prompted decades of studies in various aspects since Wyner’s pioneering work [15]. Note that physical layer security does not compete with traditional cryptographic technologies that are based on computational complexity. The former has complementary features and can be utilized to further enhance the security level of existing communication systems from the physical layer, which is independent of the higher layers. Along with the framework of wireless communication system evolving from single-input single-output (SISO) to point-to-point MIMO, multi-user MIMO, and massive MIMO as the state-of-the-art, different physical layer security techniques [16] have emerged.

At present, massive MIMO is already envisioned as a key enabling technology for 5G wireless cellular systems, due to its potential to reap and greatly strengthen all the advantages of conventional MIMO. However, while massive MIMO has attracted extensive attention, relatively few work has been done on the combination of physical layer security and massive MIMO [12]. The potential of massive MIMO to further boost the performance of physical layer security is not yet well recognized. Although the research on secrecy performance of conventional MIMO has produced considerable results, use of large antenna arrays is introducing new vitality into this area of research. Massive MIMO is not merely an extension of conventional MIMO when physical layer security is incorporated. As the number of BS antennas grows large, conventional MIMO turns into massive MIMO and becomes inherently immune to some issues [17], which can be viewed as an example of how quantitative change leads to qualitative change.

Secure transmission in multi-cell multi-user massive MIMO system with maximum ratio transmission (MRT) precoding and artificial noise (AN) [18] at the BS is investigated in detail in [19], which shows that with massive MIMO BS, random AN shaping matrices can offer a favorable performance/complexity tradeoff compared with conventional AN shaping matrices. In conventional MIMO systems the latter is usually designed to lie in the null space of the main channel to ensure that legitimate UTs are not affected. However, the corresponding computational cost is not affordable in the case of a large channel matrix. With the benefits of massive MIMO, use of random AN to avoid computing the null space of a large matrix is a more attractive option due to its low complexity and considerable performance. The underlying reason is that unlike conventional MIMO, the interference of uncorrelated random AN vanishes as the number of BS antennas grows large. Additionally, the authors of [19] also point out that even with AN assistance, secure communication may not be guaranteed if the eavesdropper has too many antennas.

A key feature of massive MIMO is power scaling [8], which enables tremendous reduction in radiated energy expenditure while maintaining the system performance. It benefits both the battery-powered UTs and the BSs with low power consumption requirements, and makes massive MIMO a green technology. It also can be utilized to improve the secrecy performance of massive MIMO systems to a considerable extent. Exploiting the potential of power scaling law to secure wireless communication system is first reported in [20]. The assumptions of perfect channel state information (CSI) at the BS and a finite number of passive eavesdropper antennas are made in a single-cell scenario. A parameter called radiated power scaling (RPS) factor is proposed to optimally adjust the overall transmit power with different number of BS antennas. It demonstrates that with judiciously selected RPS factor, multiuser massive MIMO can decrease the achievable rate of an eavesdropper to almost zero while satisfying the rate requirements of legitimate UTs at a very low power consumption, without any assistance of AN or something else. The underlying essence is that by increasing the number of BS antennas and exploiting the power scaling law, we can properly adjust the RPS factor and choose a just-right transmit power to coherently focus the required energy to a specific spatial point through the sharp and fine beam generated by massive MIMO, while keeping the field strength anywhere else as low as possible, thus maximally suppressing the achievable rate of the eavesdropper. This is different from beamforming, which is aimed at targeting the specific signals to the intended UTs. The power scaling feature makes massive MIMO a natural green secure transmission technique. In [21], the above work is further extended to the scenario in which the numbers of single-antenna legitimate UTs and antennas at the eavesdropper grow proportionally with the number of BS antennas. The corresponding results show that the optimal RPS factor converges to a different constant limit compared with the case of finite antennas at the eavesdropper. The secrecy performance is mainly determined by the ratios between the numbers of BS antennas, legitimate UTs and eavesdropper antennas. This indicates that positive secrecy rate may not be guaranteed if the ratio between the number of eavesdropper antennas and the number of BS antennas exceeds a certain limit.

The secrecy performance of power scaling in multi-cell massive MIMO scenario is then examined in [22]. The effects of pilot contamination, the length and power of pilot sequence and the power of data stream are all taken into account. The analysis shows that positive secrecy rate is still achievable at low cost via power scaling only, provided that the number of eavesdropper antennas is smaller than a threshold. In [17], both no training-phase jamming and training-phase jamming attack are studied in detail for physical layer security of massive MIMO downlink communications from the information theory perspective. The authors propose a $\delta$-conjugate beamforming approach, which is also a power scaling strategy in essence, to achieve secure transmission without using stochastic encoding in the case of no training-phase jamming. Then pilot signal assignments encryption using cryptography and $\delta$-conjugate beamforming are used in combination to defend against the active training-phase jamming attack, which aims at steering the beams towards the eavesdropper. Note that the fundamental premise of successful defense against the attack is that the number of BS antennas is above a certain threshold, which is a monotonic increasing function of the number of antennas at the eavesdropper. Therefore, the proposed strategies will not work effectively if the eavesdropper has a sufficient number of antennas to break this security premise.

From the above, we can see that if the eavesdropper is equipped with much more powerful massive MIMO or multiple eavesdroppers collaborate to form a large enough antenna array, almost all the existing physical layer security approaches based on signal processing, e.g., beamforming, AN aided precoding, or power scaling, will lose the battle against the adversaries. This phenomenon is also partly observed in [23] and [24], which are mainly dealing with conventional MIMO physical layer security. The underlying principle is that by deploying sufficiently powerful antennas, the adversary will have abundant spatial freedom degrees to facilitate the related signal processing, such as collecting weak signals or neutralizing the jamming interference, which results in a significant degradation in terms of secrecy rate. However, most of the physical layer security research work has avoided this issue, and to the best of our knowledge, so far little work exists that specifically aims at addressing the security problems of counteracting powerful massive MIMO eavesdroppers.

As pointed out in the subsection ‘The Adversary Is Not Powerful’ in [25], instead of spending money on buying extra computing resources of little use, really smart adversaries would prefer to employ more and better antennas to increase the area of monitoring and the ability of interception, which is indeed affordable and more aggressive. Therefore, it is necessary to address the physical layer security issues pertaining to the defense against eavesdroppers armed with powerful massive MIMO in the upcoming 5G era, since large antenna arrays will become popular by then.

Motivated by the possibility of facing powerful large antenna arrays equipped eavesdroppers, in this paper we propose an original symbol phase rotated (OSPR) secure transmission strategy to defend against eavesdroppers who are capable of driving the secrecy rate on the forward communication link to zero with massive MIMO. The basic idea of the proposed OSPR scheme is to randomly change the phase of original symbols at the BS before the symbols are transmitted, so that the massive MIMO eavesdropper can only perfectly intercept the phase rotated symbols even in the best case, while legitimate UTs are able to infer the correct phase rotations and take the inverse operation to recover the original symbols. Note that massive MIMO is used at the BS to facilitate the random rotation of symbol phase. As long as the eavesdropper cannot acquire the corresponding rotated phase, its interception will be full of symbol errors, no matter how many antennas it has. The proposed OSPR approach protects the data symbols at the initial stage and circumvents the security problem by avoiding fighting directly against the powerful massive MIMO eavesdropper. Moreover, the OSPR scheme employs the massive MIMO technique and spends no extra power on AN or jamming, thus making it potentially a green secure candidate transmission technique for 5G.

The rest of this paper is organized as follows. In Section II the forward link system model is described. Sections III presents the proposed OSPR secure transmission scheme in detail. In Section IV, we analyze the security performance of OSPR scheme, and Section V provides some simulation results. Finally, Section VI concludes the paper.

Notation: Uppercase and lowercase boldface letters denote matrices and column vectors. ${ {X}}^{T}$, ${ {X}}^{*}$, ${ {X}}^{H}$ and ${ {X}}^{-1}$ denote the transpose, conjugate, conjugate transpose and inverse of matrix ${ {X}}$, respectively. ${ {I}}_{N}$ denotes the $N$-dimensional identity matrix, and ${ {0}}_{N}$ denotes the all-zero column vector of length $N$. ${\left |{x}\right |}$ denotes the absolute value of a complex scalar $x$. We use ${\left \|{\cdot }\right \|}$ to denote the Frobenius or Euclidean norm of a matrix or vector, and ${\mathrm{tr}}\left ({ {X}}\right )$ to denote the trace of matrix ${ {X}}$. The expectation and variance of the random variable $x$ are denoted by ${\mathop {\mathrm{ E}}}\left ({x}\right )$ and ${\mathop {\mathrm{ Var}}}\left ({x}\right )$, respectively. ${\mathbb {C}^{m \times n}}$ represents the space of all $m \times n$ matrices with complex elements. ${\textbf {x}}\sim \mathcal {CN}({ {0}}_{N},{\Sigma{ }})$ denotes a circularly symmetric complex Gaussian random vector ${\textbf {x}} \in {\mathbb {C}^{N \times 1}}$ with zero mean and covariance matrix ${\Sigma{ }}$.

SECTION II

## SYSTEM MODEL

In this paper, we consider secure transmissions on the forward link in a single-cell scenario, in the presence of a passive eavesdropper armed with an unlimited number of antennas to intercept the transmitted signals, as shown in Fig. 1. A massive MIMO BS with a large but finite number of antennas simultaneously sends $K$ mutually independent data streams to $K$ autonomous single-antenna legitimate UTs, where data stream $k$ is intended for UT $k$ only. The number of BS antennas is denoted by $N_{b}$, and the number of eavesdropper antennas is denoted by $N_{e}$. Then we have ${N_{e}}\gg {N_{b}}\gg {K}>{0}$, where $N_{b}$ and $K$ are finite, and $N_{e}$ is infinite. Hence, both the BS and the eavesdropper have massive MIMO antenna arrays while the latter is far more powerful. The considered massive MIMO system operates in TDD mode. Reverse training and channel reciprocity, which means that the forward link channel matrix is the transpose of the reverse link channel matrix, are both used in the proposed OSPR scheme.

Figure 1. System model of the considered scenario.

### A. Channel Matrix

We denote the channel matrix from the massive MIMO BS to the $K$ legitimate UTs on the forward link as TeX Source\begin{align} {{\textbf {H}}}=&\left [{ {\begin{array}{*{20}{c}} {{{{{\textbf {h}}}}_{r,1}}}\\ {{{{{\textbf {h}}}}_{r,2}}}\\ \vdots \\ {{{{{\textbf {h}}}}_{r,K}}} \end{array}} }\right ] = \left [{ {\begin{array}{*{20}{c}} {{{{{\textbf {h}}}}_{c,1}}}&{{{{{\textbf {h}}}}_{c,2}}}& \cdots &{{{{{\textbf {h}}}}_{c,{N_{b}}}}} \end{array}} }\right ]\notag \\=&\left [{ {\begin{array}{*{20}{c}} {{h_{1,1}}}& {{h_{1,2}}}& \cdots & {{h_{1,{N_{b}}}}}\\ {{h_{2,1}}}& {{h_{2,2}}}& \cdots & {{h_{2,{N_{b}}}}}\\ \vdots & \vdots & \ddots & \vdots \\ {{h_{K,1}}}& {{h_{K,2}}}& \cdots & {{h_{K,{N_{b}}}}} \end{array}} }\right ], \end{align} and the channel matrix from the massive MIMO BS to the massive MIMO eavesdropper as ${{{\textbf {G}}}}\in \mathbb {C}^{N_{e} \times {N_{b}}}$. The row vector ${{{{\textbf {h}}}}_{r,k}}\in \mathbb {C}^{1 \times {N_{b}}}$, $k = 1,2, \ldots ,K$, in (1) represents the channel vector from the BS to UT $k$. The column vector ${{{{\textbf {h}}}}_{c,i}}\in \mathbb {C}^{K \times 1}$, $i = 1,2, \ldots ,N_{b}$, in (1) represents the channel vector from the $i$th BS antenna to all $K$ UTs. We assume that all the channel matrix elements are independent and identically distributed (i.i.d.) $\mathcal {CN}(0,1)$ random variables; thus none of the terminals are collocated. All the channels are assumed to be flat fading and block-invariant within a certain coherent interval length $T$, which facilitates the exploitation of channel reciprocity.

### B. Transmitted Signal

The massive MIMO BS performs MRT precoding on the forward link. We assume that the BS adopts the optimal RPS factor derived in the limit case in [20, eq. (22)] to achieve a good energy efficiency and security performance trade-off. Then the final transmitted signal vector ${{{\textbf {x}}}}\in \mathbb {C}^{N_{b} \times 1}$ after MRT precoding at the massive MIMO BS is given by TeX Source$${{{\textbf {x}}}} = \sum \limits _{k = 1}^{K} {{{\textbf {x}}}}_{k}=\sum \limits _{k = 1}^{K} {\frac {{{{{\textbf {h}}}}_{r,k}^{H}}}{N_{b}}}{s_{k}},$$ where the mutually independent complex symbol $s_{k}$, $k = 1,2, \ldots ,K$, with uniform power constraint ${\mathop {\mathrm{ E}}}\left ({ {{{\left \|{ {s_{k}} }\right \|}^{2}}} }\right ) \le p_{_{S}}$, represents the original data symbol intended for UT $k$.

The total radiated power of the massive MIMO BS is given by TeX Source\begin{align} P_{total}=&{\mathrm{E}}\left ({ {{{\left \|{ {{{\textbf {x}}}} }\right \|}^{2}}} }\right )= \sum \limits _{k = 1}^{K} {\frac {{{{\left \|{ {{{{\textbf {h}}}}_{r,k}^{H}} }\right \|}^{2}}}}{{{{\left ({ {N_{b}} }\right )}^{2}}}}{{{\textbf {E}}}}\left ({ {{{\left \|{ {s_{k}} }\right \|}^{2}}} }\right )} \notag \\\mathop \approx \limits ^{(a)}&\sum \limits _{k = 1}^{K} {\frac {1}{N_{b}}{{{\textbf {E}}}}\left ({ {{{\left \|{ {s_{k}} }\right \|}^{2}}} }\right )}, \end{align} where step (a) follows the law of large numbers and the corresponding results in [8, eqs. (4) and (5)], when $N_{b}$ is large enough.

### C. Received and Intercepted Signals

The massive MIMO BS transmits the signal vector ${ {x}}$ on the forward link, then the $k$th UT receives signal $r_{b,k}$, $k = 1,2, \ldots ,K$, given by TeX Source\begin{align} r_{b,k}=&{{{{\textbf {h}}}}_{r,k}}{{{{\textbf {x}}}}} + {n_{k}}\notag \\=&\frac {{{{{{\textbf {h}}}}_{r,k}}{{{\textbf {h}}}}_{r,k}^{H}}}{N_{b}}{s_{k}} + \sum \limits _{i = 1,i \ne k}^{K} {\frac {{{{{{\textbf {h}}}}_{r,k}}{{{\textbf {h}}}}_{r,i}^{H}}}{N_{b}}} {s_{i}} + {n_{k}}, \end{align} and the massive MIMO eavesdropper intercepts signal vector ${{{\textbf {r}}}}_{e}\in \mathbb {C}^{N_{e} \times 1}$, given by TeX Source$${{{\textbf {r}}}}_{e} = {{{\textbf {G}}}}{{{{\textbf {x}}}}} + {{{{\textbf {n}}}}_{e}},$$ where all the entries of the receiver noise vectors ${n_{k}}$ and ${{{{\textbf {n}}}}_{e}}\in \mathbb {C}^{N_{e} \times 1}$ are i.i.d. $\mathcal {CN}(0,\sigma _{k}^{2})$ and $\mathcal {CN}(0,\sigma _{e}^{2})$ random variables, respectively.

SECTION III

## ORIGINAL SYMBOL PHASE ROTATED SECURE TRANSMISSION

The OSPR approach is proposed on the forward link transmission to defend against an eavesdropper armed with powerful enough massive MIMO. We consider the worst case in this paper that the number of antennas at the eavesdropper is infinite to meet the ‘sufficient powerful’ condition, as mentioned in Section II. Although some jamming techniques can achieve positive secrecy rate in the case that the eavesdropper has more antennas than the BS, they will need unlimited power to maintain a positive secrecy rate as the number of eavesdropper’s antennas grows infinitely large, which is unbearable and extremely energy inefficient. The eavesdropper with unlimited number of antennas will make most of the existing physical layer security approaches impotent. In this section, we thoroughly present the proposed OSPR green secure transmission scheme to address this issue, which has the following stages.

### A. Reverse Training

First, each of the $K$ UTs simultaneously sends a sequence of pilot signal to the massive MIMO BS on the reverse link. The pilot signals transmitted by different UTs all have a length of $\tau$ symbols, where $K\leq \tau <T$ and $T$ is the coherence interval length as defined in Section II. This guarantees that all the pilot signal sequences can be mutually orthogonal, which are the optimum training signals. The used pilot signals are denoted as matrix $\sqrt {{p_{_{P}}}} {\boldsymbol {\Phi }}$, where ${\boldsymbol {\Phi }} \in \mathbb {C}{^{K \times \tau }}$ is a unitary matrix with ${\boldsymbol {\Phi }}{{\boldsymbol {\Phi }}^{H}} = {{{{\textbf {I}}}}_{K}}$ and ${p_{_{P}}}$ is the power of the length $\tau$ pilot signal sequence. The mutually orthogonal pilot signals are known at the BS and the eavesdropper, and we assume that the massive MIMO BS is able to perfectly estimate the forward link channel matrix $\bf {{{\textbf {H}}}}$ by exploiting the received training pilot sequences and channel reciprocity.

### B. Randomly Rotate the Original Symbol Phase

At this stage, the massive MIMO BS utilizes the information of the obtained column vector ${{{{\textbf {h}}}}_{c,i}}\in \mathbb {C}^{K \times 1}$, $i = 1,2, \ldots ,N_{b}$, in (1) of the channel matrix $\bf {{\textbf {H}}}$ to change the phase of original complex symbol $s_{k}$, $k = 1,2, \ldots ,K$. The expansion of ${{{{\textbf {h}}}}_{c,i}}$ is expressed as TeX Source$${{{{\textbf {h}}}}_{c,i}} = \left [{ {\begin{array}{*{20}{c}} {{{\textbf {h}}_{1,i}}}\\ {{{\textbf {h}}_{2,i}}}\\ \vdots \\ {{{\textbf {h}}_{K,i}}} \end{array}} }\right ]\!,$$ where the complex vector element $h_{k,i}$, $k = 1,2, \ldots ,K$, represents the channel from the $i$th massive MIMO BS antenna to the $k$th UT.

The $i$th antenna is randomly chosen from the $N_{b}$ antennas at the BS. Then the phase rotated symbol for UT $k$ is given by TeX Source$${s_{ospr,k}} = {s_{k}} \cdot {e^{j\angle {h_{k,i}}}},$$ where $\angle {h_{k,i}}$ denotes the phase of the complex entry $h_{k,i}$. After finishing this random phase changing operation, ${s_{ospr,k}}$ is used to replace the original symbol ${s_{k}}$ in (2). The randomly rotated symbol ${s_{ospr,k}}$ will then be processed by MRT precoding method according to the steps shown in Section II, and the original symbol ${s_{k}}$ is hidden.

### C. Broadcast the Reference Signal

After the process of random phase rotation is finished, the massive MIMO BS uses the $i$th antenna which is chosen in the last step to directly broadcast a reference signal. The reference signal has a length of $\lambda$ symbols, where $1\leq \lambda < T-\tau$. We assume that the reference signal is known to all terminals including the massive MIMO eavesdropper.

Then UT $k$ can estimate the corresponding channel information $h_{k,i}$ by exploiting the forward link broadcasted reference signal, and we assume the estimation is perfect. With the acquired knowledge of $h_{k,i}$, UT $k$ is able to obtain the rotation phase $\angle {h_{k,i}}$. It is worth emphasizing that only the selected $i$th antenna is used to broadcast the reference signal, and one symbol length may be enough for UT $k$ to estimate the CSI $h_{k,i}$ in the ideal situation. So the related resource burden for broadcasting the reference signals is small.

### D. Data Transmission and Symbol Recovery

The massive MIMO BS then sends the signal vector ${\textbf {x}}$ to all legitimate UTs, which contains the rotated symbol ${s_{ospr,k}}$, $k = 1,2, \ldots ,K$, not the original symbol ${s_{k}}$. The $k$th legitimate UT first receives the signal $r_{b,k}$, then its receiver outputs ${\hat s_{ospr,k}}$ which is the detection result based on (4). Finally, the UT $k$ recovers the original symbols by taking the following inverse operation TeX Source$${\hat s_{k}} = {\hat s_{ospr,k}} \cdot {e^{j\left ({ { - \angle {h_{k,i}}} }\right )}},$$ where the angle information $\angle {h_{k,i}}$ is obtained by exploiting the reference signal in the last step, ${\hat s_{k}}$ is the final recovered result of the original symbol ${s_{k}}$.

### E. Structure of the Coherence Interval

All the activities above and the structure of the corresponding coherence interval are summarized in Fig. 2. The massive MIMO eavesdropper intercepts the transmission signals all the time.

Figure 2. The coherence interval structure of the OSPR secure transmission scheme.

Moreover, in the case that the coherence interval is long enough to accommodate multiple data symbols, the random phase rotation process in the proposed OSPR security scheme can be further used symbol by symbol or on demand to enhance the secrecy performance, since there are many antennas at the massive MIMO BS that can be randomly chosen without repetition. In this situation, the reference signal broadcasting step is repeated, in order to let the legitimate UTs acquire the updated information of the rotated phase, which can be equivalently viewed as the encryption key in traditional cryptography. The corresponding structure is also presented in Fig. 2.

SECTION IV

## SECURITY ANALYSIS

In this section, the secrecy performance of the proposed OSPR secure transmission scheme on the forward link is analyzed in detail. We present the analysis by closely following each of the steps of the OSPR scheme described in Section III. The massive MIMO eavesdropper is assumed to have perfect knowledge of the mechanism about the OSPR scheme. The importance of equipping large number of antennas at the BS is presented. We show that the massive MIMO eavesdropper can hardly obtain the real data symbols although it is armed with an unlimited number of antennas.

### A. Security at the Stage of Reverse Training

At this stage, the $K$ legitimate UTs transmit the mutually orthogonal pilot signals to the massive MIMO BS. We consider the worst case scenario that the massive MIMO eavesdropper can perfectly intercept the pilot signals. Then it is able to perfectly infer the CSI between itself and the legitimate UTs. However, it cannot extract any information about the main channel ${\textbf {H}}$. This is because, first, all terminals are not colocated and all the channels are independent as presented in Section II, and second, no information of ${\textbf {H}}$ is used by any UT in the reverse training phase. Hence, even if the massive MIMO eavesdropper has an infinite number of antennas and can exploit powerful blind channel estimation techniques, it can hardly acquire any information about ${\textbf {H}}$.

### B. Security at the Stage of Random Phase Rotation

The massive MIMO BS performs the channel estimation, random phase rotation, MRT precoding and other necessary signal processing and computations locally and quietly, without radiating any signals. Thus the massive MIMO eavesdropper can do nothing but wait. It is obvious that no information can be intercepted and the powerful eavesdropper antenna array is useless at this stage.

### C. Security at the Stage of Reference Signal Broadcasting

We consider the worst case scenario that the massive MIMO eavesdropper is able to perfectly intercept the reference signal broadcasted by the $i$th BS antenna, and perfectly obtain the CSI between itself and the $i$th antenna which is randomly selected at the massive MIMO BS. Nonetheless, the massive MIMO eavesdropper still cannot extract any information about the main channel CSI matrix ${\textbf {H}}$ from the intercepted reference signal. The reason is similar to the case at the stage of reverse training, and it is not further repeated here.

Moreover, the massive MIMO eavesdropper can hardly get the overall information about the CSI matrix ${\textbf {G}}$ between itself and the BS by learning the reference signal, since only one antenna among the large number of candidate antennas at the BS is randomly chosen to broadcast the reference signal, and all the channels are time-varying. Nor can the eavesdropper know which antenna is chosen to broadcast the reference signal in the considered scenario, since the random selection process is locally performed at the massive MIMO BS, and the intercepted reference signal can provide little useful information when the entire knowledge of the channel matrix ${\textbf {G}}$ is absent.

### D. Security at the Stage of Data Transmission

At this stage, the massive MIMO BS transmits the processed data symbols through the open wireless medium. We consider the worst case scenario that the massive MIMO eavesdropper is able to perfectly estimate the equivalent CSI, which is the product of the precoding matrix and the channel matrix ${\textbf {G}}$, by exploiting powerful channel estimation approaches (either blind or not). Furthermore, it can perfectly extract ${s_{ospr,k}}$, $k = 1,2, \ldots ,K$, which is the de facto symbol transmitted by the massive MIMO BS, from the intercepted signal vector ${{\textbf {r}}}_{e}$ without any contamination by cancelling all the interferences and receiver noises.

However, the perfectly obtained equivalent CSI cannot be exploited to extract useful information about the main channel matrix ${\textbf {H}}$, since the massive MIMO eavesdropper only acquires little knowledge of the channel matrix ${\textbf {G}}$ at the last stage of reference signal broadcasting. Hence, the massive MIMO eavesdropper knows little about the CSI matrix ${\textbf {G}}$, ${\textbf {H}}$ and which antenna is randomly chosen to change the phase of the original symbol $s_{k}$, according to the analysis above. Then it can hardly acquire the information of $\angle {h_{k,i}}$. Thus even if the massive MIMO eavesdropper has an unlimited number of antennas and knows that the symbol ${s_{ospr,k}}$ is not the right one, it cannot recover the original symbol $s_{k}$ without the knowledge of $\angle {h_{k,i}}$. Finally, the legitimate UTs can recover the original symbol to correctly acquire the transmitted information, while the massive MIMO eavesdropper only obtains the signals that are randomly rotated.

### E. Effect of the Massive Antennas at the BS

The BS adopts massive MIMO techniques to improve the energy efficiency. More importantly, the large number of BS antennas enhances the secrecy performance of the proposed OSPR secure transmission scheme. This is because the OSPR scheme randomly selects one antenna among all the BS antennas to encrypt the original symbol. The random selection process is the key factor of the OSPR secure transmission strategy. The more candidate antennas at the BS available for random selection, the harder it is for the massive MIMO eavesdropper to guess which antenna is chosen and acquire the information of $\angle {h_{k,i}}$, and successfully recover the original symbols.

Consider the simple case that the BS has two antennas and only one UT is served. The random phase rotation process of the OSPR security scheme is used symbol by symbol in this case. Since there are only two antennas at the BS, the eavesdropper can acquire the entire knowledge of the two column vectors of channel matrix ${\textbf {G}}$ by intercepting the reference signal twice or more, during one coherence interval. Then it can exploit the perfectly estimated equivalent CSI matrix, which is the product of precoding matrix and the channel matrix $\bf G$, at the data transmission stage to further infer the information of the channel matrix ${\textbf {H}}$. From the perspective of the powerful massive MIMO eavesdropper, now it may be able to exhaustively test the rotated phase $\angle {h_{k,i}}$, and finally recover the original symbol. However, if the BS has a massive number, e.g., tens or hundreds of antennas, then the channel matrix ${\textbf {G}}$ will be too large for the eavesdropper to exhaustively learn during one coherence interval. Therefore, the massive MIMO eavesdropper can hardly recover the original symbol when the BS has enough antennas to randomly choose from. This presents the key role of the large antenna array at the BS on enhancing the security performance.

SECTION V

## SECURITY PERFORMANCE EVALUATION

In this section, we evaluate the security performance of the proposed OSPR secure transmission scheme, and simulation results are presented.

We consider the practical case that the original symbol $s_{k}$, $k = 1,2, \ldots ,K$, is finite alphabet quadrature phase-shift-keying (QPSK) modulated, and the constellation is TeX Source\begin{align} \left \{{ {\frac {\sqrt {2}}{2}\left ({ {1 + j} }\right ),\frac {\sqrt {2}}{2}\left ({ {1 - j} }\right ),\frac {\sqrt {2}}{2}\left ({ { - 1 + j} }\right ),\frac {\sqrt {2}}{2}\left ({ { - 1 - j} }\right )} }\right \},\notag \\[-2pt] {}\end{align} where the modulated symbol power is normalized. We set $N_{b} = 64, 128, 256, 512, 1024$ and $K =16$, where $N_{b} = 64$ is assumed to be large enough for the proposed OSPR scheme to work properly, as mentioned in Section IV. This assumption is made for the convenience of simulations. The signal-to-noise ratio (SNR) of the $k$th UT is ${\mathrm{SNR}}_{k} = \frac {1}{\sigma _{k}^{2}}$. We consider the worst case scenario that the eavesdropper has an unlimited number of antennas, i.e., $N_{e} = \infty$, and ${\sigma _{e}^{2}} = 0$, which means that the corresponding ${\mathrm{SNR}}_{e} = \infty$. Therefore, it can perfectly intercept the transmitted signal symbol ${s_{ospr,k}}$.

We emphasize that if the chosen $\angle {h_{k,i}} \leq \frac {\pi }{4}$ or ${\angle {h_{k,i}} \ge \frac {7\pi }{4}}$, then the original symbol $s_{k}$ will not be rotated since QPSK modulation is employed. Otherwise, the original symbol will be rotated to the corresponding quadrant, and replaced by the QPSK symbol that is in the same quadrant. The legitimate UTs are aware of these rules. Furthermore, throughout this paper, we assume that all the channel estimations are perfect.

First, we analyze the symbol error rate (SER) of the massive MIMO eavesdropper. We assume that the eavesdropper aims at intercepting the symbols sent to the $k$th UT. Since the rotated symbol ${s_{ospr,k}}$ can be perfectly intercepted, the SER of the eavesdropper is the probability $\Pr \left \{{ {\frac {\pi }{4} < \angle {h_{k,i}} < \frac {7\pi }{4}} }\right \}$ when the $i$th BS antenna is randomly chosen, where $\Pr \left \{{ {\frac {\pi }{4} < \angle {h_{k,i}} < \frac {7\pi }{4}} }\right \}$ is exactly the probability that the original symbol $s_{k}$ is rotated. This is due to the employed OSPR secure transmission scheme. The $\angle {h_{k,i}}$ is uniformly distributed over the range $\left [{ {0,2\pi } }\right ]$, since ${h_{k,i}}$ is an i.i.d. $\mathcal {CN}(0,1)$ random variable as defined in Section II. We also assume that the $i$th antenna is randomly chosen with equal probability from all the BS antennas. Therefore, the SER ${P_{e,SER}}$ of the powerful massive MIMO eavesdropper is given by TeX Source\begin{align} {P_{e,SER}}=&\sum \limits _{i = 1}^{N_{b}} {\frac {1}{N_{b}}} \cdot \Pr \left \{{ {\frac {\pi }{4} < \angle {h_{k,i}} < \frac {7\pi }{4}} }\right \}\notag \\[-2pt]=&\Pr \left \{{ {\frac {\pi }{4} < \angle {h_{k,i}} < \frac {7\pi }{4}} }\right \} \notag \\[-2pt]=&\frac {3}{4}. \end{align}

The eavesdropper SER simulation result is shown in Fig. 3. We set $N_{b} = 64$ and the random phase rotation process is used once in every coherence interval. We assume that the length of data transmission shown in Fig. 2 in one coherence interval is 1, for the convenience of simulation. Then 10000 coherence intervals are simulated, which means 10000 symbols are tested in total. The original QPSK symbol is ${\left \{{ {\frac {\sqrt {2}}{2}\left ({ {1 + j} }\right )} }\right \}}$, which is in the first quadrant of the modulated constellation. The X axis in Fig. 3 denotes the quadrant where the intercepted symbols fall in. From the plot we can see that 2529 symbols intercepted by the massive MIMO eavesdropper are in the first quadrant, which means the remaining 7471 symbols are wrong. Thus the simulated SER is 0.7471, or approximately 0.75. This verifies the analytical result. The figure also shows that the number of symbols in different quadrant are almost identical, since the rotated angle $\angle {h_{k,i}}$ is uniformly distributed over the range $\left [{ {0,2\pi } }\right ]$. The high SER of the eavesdropper indicates a great reduction of the successfully recovered original information, and corroborates the security performance of the proposed OSPR scheme.

Figure 3. SER of the massive MIMO eavesdropper.

Next, the SER plot for the $k$th legitimate UT as a function of ${\mathrm{SNR}}_{k}$ when the OSPR scheme is employed, is shown in Fig. 4. 10000, 100000 and 1000000 symbols are simulated for the case of 64, 128 and 256 BS antennas, respectively. 5000000 symbols are simulated for the case of 512 and 1024 BS antennas. We can see that as the number of BS antennas increases, the SER performance becomes better and better. The performance enhancement is significant. The reason is that with more antennas at the BS, the ability to cancel the intra-cell interference and noise, i.e., the second and third terms in (4), becomes stronger. Fig. 4 also shows that increasing the SNR cannot effectively improve the SER performance, when the number of BS antennas is not large enough compared with the number of served UTs. Fig. 3 and Fig. 4 demonstrate the effectiveness of the proposed OSPR secure transmission scheme. The SER of massive MIMO eavesdropper is high, while the massive MIMO BS can work properly and the legitimate UTs can recover the original symbols normally. Therefore, the signal transmission stage can be secured by the OSPR scheme to a large extent.

Figure 4. SER of the $k$th user terminal.

Fig. 5 illustrates the total radiated power of the massive MIMO BS as a function of the number of BS antennas $N_{b}$, from simulation results based on (3). We can see that the power consumption decreases significantly as the number of BS antennas increases. The plot demonstrates that with more BS antennas, the corresponding wireless system is able to achieve better energy efficiency, which potentially makes the proposed OSPR approach a green secure transmission scheme.

Figure 5. The total radiated power of the massive MIMO BS.
SECTION VI

## CONCLUSION

In this paper, we have proposed a novel secure transmission scheme called OSPR to defend against eavesdroppers armed with massive antennas in a single-cell scenario. The proposed OSPR secure transmission scheme has been introduced step by step. The corresponding security performance has been comprehensively investigated under certain assumptions. Practical simulation results with finite alphabet QPSK inputs have been provided to further corroborate the effectiveness of the proposed scheme. We have shown that as long as the BS is equipped with a sufficient number of antennas, the powerful massive MIMO eavesdropper will not be able to recover most of the original symbols (i.e., the SER is high), even if it has an infinite number of antennas, while the legitimate UTs are able to correctly recover the original symbols. Thus the security performance of the system is guaranteed to a large extent. We have also shown that the proposed OSPR scheme does not affect the high energy efficiency of the massive MIMO BS, and it involves no jamming like approach which is power consuming. This makes the proposed OSPR scheme a good candidate for green and secure transmissions.

Note that the assumptions made in this paper are optimistic. The effects of imperfect CSI, imperfect channel estimation and multi-cell scenario have not been considered. They are left for future work along with a detailed information theoretic analysis.

## Footnotes

This work was supported in part by the National Natural Science Foundation of China under Grant 91338105 and Grant 61502518, the China Scholarship Council under Grant 201306110074, the Four-Year Doctoral Fellowship through The University of British Columbia, the Natural Sciences and Engineering Research Council of Canada, the Institute for Computing, Information, and Cognitive Systems/TELUS People and Planet Friendly Home Initiative through The University of British Columbia, TELUS, and the other industry partners.

Corresponding author: B. Chen

## References

No Data Available

## Cited By

No Data Available

None

## Multimedia

No Data Available
This paper appears in:
No Data Available
Issue Date:
No Data Available
On page(s):
No Data Available
ISSN:
None
INSPEC Accession Number:
None
Digital Object Identifier:
None
Date of Current Version:
No Data Available
Date of Original Publication:
No Data Available

Comment Policy


text:
# Strain Ellipsoid

Let us refer again to the sphere inscribed within our cube that undergoes homogeneous strain. Giving this sphere axes $$\lambda _1$$, $$\lambda _2$$ and $$\lambda _3$$, we find that these remain orthogonal through the homogeneous deformation and can be used to describe the long, medium, and short dimensions of the resulting ellipsoid. (Figure 1, Several basic types of homogeneous strain imposed on a cube of ideally uniform composition.

FIGURE 1

In each case, the inscribed circle and ellipse represent cross sections through the strain ellipsoid before and after deformation. The types of strain shown are: (a) uniform extension; (b) uniform flattening; and (c) plane strain. Note that no strain occurs in the intermediate direction.)

Together, these are called the principal strain axes of the strain ellipsoid. Just as stress can be said to exist at every point within a body, so is there a corresponding strain ellipsoid for these points, once deformation has taken place. Thus, comparison between the "before" and "after" shape and axes of the sphere inscribed within our cube provides us with a measure of the amount and type of strain.

It is standard practice for geologists to derive the principal axes of stress by superimposing them on the strain ellipsoid. ( Figure 2, Note that this superposition assumes homogeneous strain, i.e., maximum shortening occurs in the direction of maximum principal stress, and maximum extension in the direction of minimum principal stress).

FIGURE 2

This is an optimistic simplification (as we have seen, the principal axes of stress and strain coincide only under conditions of homogeneity), but can be very useful. It has, for example, offered considerable insight into basic mechanisms and patterns of deformation-particularly faulting and fracturing-on many scales. This will become increasingly clear in the following two sections on folding and faulting.

Because of their frequent use of structural cross sections, geologists have also found it advantageous to make use of a strain ellipse-essentially a cross section through the strain ellipsoid along the $$\lambda _1$$ $$\lambda _3$$ plane (i.e., the one that involves $$\sigma _1$$ and $$\sigma _3$$). The justification for this is, again, dependent on the assumption of homogeneous strain. Because of the regional nature of most tectonism, and the layered nature of lithologic sequences, many geologic examples of strain can be considered to approximate plane strain (see part c of Figure 1). In this type of deformation, the intermediate axis remains the diameter of the "original" sphere (the $$\lambda _2$$ axis-- parallel to $$\sigma _2$$-- in part c of Figure 1), while shortening and stretching occur along the other two axes.

Thus, two dimensions are sufficient to describe the strain at a particular point. If we are ready to accept the assumption of homogeneous strain, the strain ellipse becomes one of our principal indicators for the summation- of-local-strains method. (Figure 3 Hypothetical cross section and diagram to illustrate domains of pure and simple shear in a series of folds that show progressively greater total strain.

FIGURE 3

The shape of the strain ellipse can be the same for either type of shear and cannot be used to derive detailed strain history.)

As shown by Figure 4, (Example of how the strain ellipse – here constructed from deformed oolites – can be used as a descriptive guide to deformation intensity and orientation.

FIGURE 4

Shown is a cross section through the south Mountain fold of western Maryland, U.S) the strain ellipse can be an important guide to the general degree and style of deformation.

Some natural materials, such as ooids, spherulites, pebbles, certain fossils, and reduction spots in shales, can be used as qualitative ellipses or, in some cases, ellipsoids. However, because volume changes frequently occur during deformation (especially in carbonates) any quantitative determinations of strain based on such materials must be used with caution.

In principle, any object whose initial shape is known can act as a strain indicator. Such an indicator can be important to the subsurface explorationist, since it may be the only direct evidence available for how much strain has affected the fabric-and thus porosity and permeability-of a lithologic section. In most cases, the degree of tectonic influence on grain texture is fairly apparent from petrographic study. Strain indicators are primarily useful where this may not be clear and where special circumstances warrant mathematical determinations of strain. Specific techniques for measuring finite strain from oolites and spherulites are given by Ramsay (1967) and Ramsay and Huber (1985).

Nearly all deformation in nature is in-homogeneous. Not only do originally planar surfaces become complexly curved, but volume changes that involve both loss and addition of material frequently take place. Because of their pronounced heterogeneity in composition, thickness, and thus strength, rocks do not behave passively during deformation, but adjust in complex ways. Some units become strain-hardened and are able to withstand and transfer greater and greater amounts of stress as deformation progresses; other lithologies, in contrast, are fated to absorb stress by flowage, recrystallization, and the development of secondary fabrics such as cleavage.

Again, despite the dominance of inhomogeneity in nature, both local and regional deformational history can be reconstructed by assuming near-homogeneous strain domains. On a large scale, this often establishes the regional nature of stress and strain. Geologists often estimate a regional strain ellipse based on the orientation of major structural trends. This is called the mean strain ellipse and is often useful in explaining such trends in terms of plate interactions.

format: plain


text:
# Freyd-Mitchell Embedding Theorem

Jump to navigation Jump to search

## Theorem

Let $\AA$ be a small abelian category.

Then there exists a ring with unity $R$ and a fully faithful and exact functor $F : \AA \to R \text{-} \mathbf{Mod}$ to the category of left $R$-modules.

## Source of Name

This entry was named for Peter John Freyd and Barry M. Mitchell.


text:
# Are there any disadvantages of TeX being Turing complete?

I have read that TeX is Turing complete. I was wondering if making TeX Turing complete gave raise to unwanted effects.

-
Yes, there is a drawback: instead of "only" writing your thesis you start to code LaTeX packages like tikz-timing, standalone, svn-multi and many more. This wouldn't happen if it wasn't Turing complete. – Martin Scharrer May 31 '12 at 18:10

Yes, there is a drawback: instead of "only" writing your thesis you start to code LaTeX packages like tikz-timing, standalone, svn-multi and many more. This wouldn't happen if it wasn't Turing complete.

Having it Turing complete enables an infinite number of additions, but of course required some initial investment when TeX was created. All TeX distributions I know make sure that TeX's power can't be used to harm the user, e.g. shell escape is disabled or restricted by default and you can't overwrite files using an absolute or parent folder etc. There is no real drawback for the user but a lot of benefits.

-
+1 and more for investing so much time on great packages that have made not only my life so much easier! The answer itself, however, is just wrong, technically and socially: 1: I doubt that for any of the algorithms you have implemented Touring-completeness is actually required. 2: All good PhD students spend (too much?) time on (over-engineered) side projects that are supposed to ease their writing. I have seen many; there is absolutely no evidence, that the turing-completeness of the tool is the driver for procrastination :-) – Daniel Jun 2 '12 at 8:41
@Daniel: I implemented parsers in TeX. I doubt this is possible without Turing completeness. Also, my point is that this wouldn't have happened without (La)TeX being so extensible. Without it I would have of course found other ways for procrastination. So my answer stands. ;-) – Martin Scharrer Jun 2 '12 at 8:47
Parsing is a point, but only if the language the parser is supposed to accept is context sensitive; context-free or regular languages could be parsed by simpler machines. Well, I will now stop being picky. What really matters is that, even though you have been providing us with many great packages, the halting problem of thesis writing turned out as decidable :-) – Daniel Jun 3 '12 at 14:34

## First Disadvantage: Hard to Analyse

One big disadvantage of being Turing complete is that TeX "programs" are subject to Rice's theorem, which basically means that for a given document d and TeX source file f, it is undecidable in general whether f generates d (or not).

There are a lot of corollaries to this theorem, but for TeX the most important one is that it is impossible in general to find out what exactly some piece of TeX source does, especially not with another computer program, short of executing it with TeX.

This actually lies behind the apparent impossibility to convert TeX into something else. It is simply computationally impossible unless "something else" is either just another syntactic variant of TeX source or somehow "isomorphic" with dvi or pdf.

This extends to seemingly simple tasks, i.e. it is also undecidable, in general, whether (or not) a piece of TeX source will produce the letter "d" at some point in time, will have undefined labels, will output colored text, will produce more than one page or whatever other basic property of a document you'd like to find out.

This situation is completely different for non-Turing-complete notations like RTF, HTML or FO.

## Second Disadvantage: High Demands on Engines

Another consequence is that there is no "almost compliant" TeX engine. While it is no problem to support a subset of HTML because it is rather easy to estimate what happens when parts of the formalism are not supported, for TeX even the slightest deviation from the intended behaviour can lead to arbitrary devastating and unexpected consequences.

This means all "alternative" TeX engines either just don't get the basic task of document generation right (like ant or exTeX), or are so near to the original TeX that it is hard to see what alternative they really offer (like NTS).

The only thing that works is to start from the original TeX engine and add things on top which it couldn't do before, like with pdftex, eTeX, xetex or LuaTeX.

## Third Disadvantage: Low Fault Tolerance

Turing-complete formalisms have so much expressive power that it is hard to deal gracefully with errors.

If I randomly replace half of a HTML file by gibberish, then a browser will still be able to render those parts which look like HTML almost correctly.

For a "TeX program" with errors, if it doesn't conform to some strict "markupish" syntax standard like LaTeX, the engine will be unable to generate meaningful output from the correct parts if the computation as a whole fails.

-
That indeed are points that actually are related to Turing-completenes and that really do matter. – Daniel Jun 2 '12 at 8:05
Great answer, Stephan! :) – Paulo Cereda Jun 2 '12 at 11:06
@PauloCereda I've always considered Rice's Theorem the most influential result around the halting problem because it is the basis for a large part of Software industry (everything having to do with testing, QA etc.). – Stephan Lehmke Jun 2 '12 at 21:28

Turing's result is that essentially any non trivial programming language is computationally equivalent. If it has the power to encode arithmetic, it can do anything that any programming language can do (rough paraphrase).

Thus if you want a formatting language that can do arithmetic, or to be able to measure boxes and take different decisions depending on lengths matching user-specifiable conditions, then a Turing complete language is almost inevitable.

-
"almost inevitable" is debatable here, as neither arithmetic nor the ability to measure boxes and take decisions requires Touring-completeness. Basically, touring completeness requires three properties: (1) variables and the possibility to do arithmetic on them (an inc operation is enough) (2) a test operation (if) and (3) an endless loop construct (such as recursion orgoto or while). Number 3 is the key point here: Only if you really need some sort of "endless computation", Touring-completness is inevitable. – Daniel May 31 '12 at 20:45
HTML+CSS is an example of a complete layouting language that isn't Turing complete. – Lie Ryan Jun 1 '12 at 0:05
@LieRyan also of course the vast majority of complex layouts in a web page (such as this one) use javascript in addition to css and that of course is Turing complete again. – David Carlisle Jun 1 '12 at 0:17
BTW, @Daniel, it's "Turing" (named after Alan Turing), not "Touring". – mlp Jun 1 '12 at 5:13
IF you haven't got any comments to make ON THIS ANSWER, please take this discussion elsewhere. – David Carlisle Jun 2 '12 at 19:06

One unwanted effect is the possibility for creating and releasing malicious code, because TeX has the capability to write to the local filesystem. Also, using the special modes for passing content through to PDF machinery, it is possible to embed malicious content inside a PDF document generated from TeX source.

Neither of these possibilities actually require that TeX be Turing-complete, but it becomes much easier to hide malicious code if it is.

-
This is limited by sensible write18 limitations that should be standard on most distributions. A related point is that some inputs to TeX programs don't halt. This isn't in general a problem, but if you want to build a service that runs TeX on a server, then there is a danger of malicious people clogging your server with infinite loops. – Seamus May 31 '12 at 19:19
How do these potentially problematic features relate to whether the program is Turing-complete? – Mico May 31 '12 at 19:19
@Mico I guess the more general implicit question is "What are the disadvantages to TeX being so darn powerful?" – Seamus May 31 '12 at 19:36
@Mico Turing completeness makes it easier to hide the dangerous code. I'm sure you could use write18 without ever seeing this command in a TeX source and hence any naive analysis would not able to catch it. – Christian Lindig Jun 13 '12 at 5:04
@Mico, as ChristianLindig mentioned, for some sub-Turing-complete languages it is possible to solve the halting problem (for example, trivially, in a total language (en.wikipedia.org/wiki/Total_functional_programming). On the other hand, it is guaranteed that, in a Turing complete language, not only are there programs that will not halt, but it is not even possible always to tell in advance (i.e., without running it) whether or not a given program will halt. – L Spice Jun 17 '15 at 20:12

There is quite some confusion about the exact meaning and relevance of Turing-completness in the question as well as in the answers so far.

@Mico I guess the more general implicit question is "What are the disadvantages to TeX being so darn powerful?" – Seamus

Seamus' comment puts it very well. In fact, I am pretty sure that neither the examples given by Martin, nor David nor Todd actually require TeX to be Turing-complete for any practical purpose.

Turing-completeness basically requires three properties:

1. Variables (registers) that can be modified by primitive arithmetic: An inc operation (+1) is enough.
2. A test operation (if)
3. An endless loop construct, such as goto or while or recursion.

Number 3 is the important point here. You need to have the necessity to do "endless calculations" to actually require Turing-completeness. Given that for any practical purpose the output of TeX is finite, intuitively Turing-completeness is not really required. (Of course, we do need \loop and recursive macro expansion, but it would probably be sufficient if we bound them to, lets say, a billion iterations.)

The only real disadvantage of Turing-completeness is that the halting problem (the question if a program eventually terminates or not) is undecidable.

-
In tex/pdftex, tex the program uses only a fixed amount of memory. Isn't "infinite tape" also a requirement for a Turing machine? – Aditya Jun 2 '12 at 18:49
@Aditya: That is true, "infinite state" is formally also a requirement of a Turing machine. So TeX as a language is turing-complete (TC), the tex machine that interprets this language, however, is actually a linear bounded automaton, LBA. This, of course, holds for any real-world computing machine (there is no computer with unlimited memory...), so in colloquial usage the term TC usually implies a "given that the machine is an LBA with enough memory". – Daniel Jun 3 '12 at 7:39
(Why do people cling to state so much?) Turing completeness does not require state (so scrap #1), if you have functions, fun t f => t (~true) and fun t f => f (~false) can act as bools and if-construct at the same time (scrap #2). All you need is #3, e. g. in the form of recursion. (Untyped) lambda calculus has all you need, but three fixed functions suffice (actually, one is enough). And that can be done in TeX… – nobody Mar 28 '13 at 22:53
Here you go: \def\k#1#2{#1} \def\s#1#2#3{#1{#3}{#2{#3}}} \def\X#1{#1\s\k} % one combinator to compute everything \def\I{\X\X} \def\S{\X{\X{\X{\X\X}}}} % S re-implemented on top of X \def\O{\S\I\I} \O\O % (constant space) endless loop, SII(SII) -> SII(SII) – nobody Mar 28 '13 at 23:29
@nobody: Yes, SKI is Turing-complete, as are μ-recursive functions and all the other computation models that are based on recursion. However, recursive functions are way more than #3, they just hide "data state" in "control flow state" (#1) and conditionals in termination (#2). So they are all, but not minimal primitives (even though elegant). – Daniel Apr 1 '13 at 16:39

Turing completeness implies that processing a document might not terminate. Obviously this is a bug caused by looping code but that it is possible at all could run against intuition of non-programmers. Personally I am willing to pay this price in exchange for the power it gains but it is one of the costs of Turing completeness.

Addendum: The undecidability of the halting problem for Turing-complete languages further implies that TeX cannot incorporate a program analysis phase to detect non-terminating code. While possible, it also does not implement a heuristic.

Another consequence is that LaTeX code is difficult to analyze in general without executing it. This makes it hard to analyze it in particular for security problems like it would be useful if LaTeX is provided as an online service.

-
I have a feeling that even systems that fail to be Turing complete can have inputs that don't halt. So it's a cost of something strictly weaker than Turing completeness. – Seamus May 31 '12 at 19:35
Having non terminating loops isn't directly related to Turing Completeness. It is trivial to design a language that isn't Turing Complete but has non-terminating programs. For example a language with a single command \wait that never terminates, would have that property., or less trivially a language without any of TeXs arithmetic or testing commands but which let you do \def\oops{\oops}\oops – David Carlisle May 31 '12 at 19:35
I did not claim that non-termination implies Turing completeness. Hence, I agree that there exist non-Turing complete languages that permit to write non-terminating code. The question was about drawbacks of Turing completeness and possible non-termination is one such drawback. – Christian Lindig May 31 '12 at 20:02
@DavidCarlisle,Seamus: Well, the important point here is that for a Touring-complete language the halting problem (will a program terminate or not) is undecidable, whereas for a regular language as sketched by David it is. – Daniel May 31 '12 at 20:20

I tried to restrain myself from answering this question, but I could not hold it. :)

Simply put, Turing complete means that you can perform any computational task (well, any Turing-computable function). If you can simulate a universal Turing machine, you have a Turing complete system.

Gosh, I wrote "Turing" four times in that sentence. :)

Now, to the point of your question: the disadvantages of TeX being Turing complete. I'd say that, despite the fact that you can perform any task, there's no garantee for it being executed efficiently. And being able to do any task doesn't mean it will be easy. At all. So it'd say the tricky part here is how.

TeX being Turing complete means that I could, say, write something extremely complex with it. I could, but just don't ask me how. :)

-
an illustration of this appears in a tugboat article by Andrew Mark Greene, "BaSiX -- an interpreter written in TeX". (but just because you can, doesn't necessarily mean that you should.) – barbara beeton Jun 1 '12 at 23:13
Thanks @barbara, great article! :) – Paulo Cereda Jun 1 '12 at 23:37
The point about time efficiency of (La)TeX is really valid. I guess that everybody know what I speak about who used \tracingmacros once and had to go through the complete mess of (mostly font-related) macro listings... – yo' Jun 2 '12 at 11:53

One of the minor side effects is frustrating people who think they're going to knock off a quick little TeX-to-Foo converter. Or rather it frustrates people who find the resulting converter on the internet and expect it to do something sensible with the document they want to convert.

To actually work, every TeX-to-Foo converter has to be a full blown TeX compiler.

-

Compare the following:

"It's risky to design minilanguages that are only accidentally Turing-complete. If you do this the odds are good that, sometime in the future, some clever fellow is going to think he needs to press your language into doing loops and conditionals for him. Because these are only available in an obfuscated way, he'll produce obfuscated code. The results may be serviceable in the short term, but are likely to be a nightmare for those who come after him."

The Art of Unix Programming, Eric S. Raymond

-
So your point is that TeX is accidentally Turing-complete? With what I should compare this? – percusse Sep 30 '12 at 22:16
TeX is actually intentionally TC, as goes a well-known story of Knuth about its development. Nonetheless, this is very true. – Ryan Reich Sep 30 '12 at 23:28
I've been trying to find the story you mention via Google, and haven't had much luck... – Mohan Oct 1 '12 at 18:45


text:
Question

# Let $$f=\displaystyle \left\{\left(x,\frac{{x}^{2}}{1+{x}^{2}} \right):x\in R \right\}$$ be a function from $$R$$ to $$R$$ then range of $$f$$ is .

A
(0,)
B
[0,1]
C
(1,0)
D
(,0)

Solution

## The correct option is B $$[0,1]$$$$f(x)=\cfrac { { x }^{ 2 } }{ { x }^{ 2 }+1 }$$is defined for all real $$x$$now, say$$y=\cfrac { { x }^{ 2 } }{ { x }^{ 2 }+1 } \\ \Rightarrow y{ x }^{ 2 }+y={ x }^{ 2 }\\ \Rightarrow { x }^{ 2 }(1-y)=y\\ \Rightarrow x=\sqrt { \cfrac { y }{ 1-y } }$$$$x$$ is defined only when,$$\cfrac { y }{ 1-y } \ge 0\\ \Rightarrow \cfrac { y(y-1) }{ { (1-y) }^{ 2 } } \ge 0\\ \Rightarrow y(1-y)\ge 0\\ \therefore y\quad \epsilon \quad [0,1]$$Mathematics

Suggest Corrections

0

Similar questions
View More

People also searched for
View More


text:
# Given two parallel line segments, how do I tell if and where they overlap?

To find if two line segments intersect I am this code

The problem is this code:

// if abs(angle)==1 then the lines are parallell,
// so no intersection is possible
if(abs(deg)==1) return null;

At that point we know that the lines are parallel, but we don't know if they overlap and where.

If I have a line segment 5,5 to 10,10 and another line segment 7,7 to 12,12 then I'd like to determine that the line segment 7,7 to 10,10 is the overlap.

-

This method will work for all lines in any dimension.

Parametrize your line using the vector equation of a line:

$\textbf{r} = t\textbf{s} + \textbf{c}$

Then the $t$ values of the two line segments (assuming they do intersect) will correspond to certain intervals. The overlap will correspond to the $t$ values of the intersection of these intervals.

For your example the line is parametrized by:

$\textbf{r} = t\binom{1}{1}$

The first line segment corresponds to $t$ values in the interval $[5,10]$ and the second to $[7,12]$. Thus the overlap corresponds to points with $t$ value in $[7,10]$, i.e. the line segment joining $(7,7)$ to $(10,10)$.

-

One way would be to determine the coordinate of the intersection of the line which supports the segment with the $x$-axis, for example. If the two endpoints of the segment are $(a,b)$ and $(c,d)$, then $(x,0)$ is colinear to these if and only if

$$\frac{x-a}{c-a}=\frac{0-b}{d-b}$$

From here, it is easy to get $x$ as a simple function of $a,b,c,d$. If you have two parallel segments, you can tell if they have the same support line if you get the same $x$ in the formula above.

If the two segments are on the same support line, then you can say if they intersect by looking at their projections on the $x$-axis.

For example, in your case, the segments are obvious on the same line $(x=0)$. And they intersect, because $[5,10]$ and $[7,12]$ intersect.

-

If two lines are parallel they will either overlap nowhere or everywhere

-
The question is about line segments. –  alex.jordan Feb 19 '12 at 21:22
I don't see how that changes much –  Awk34 Feb 23 '12 at 23:58
Line segments that are parallel might partially overlap. On the $x$-axis, consider the intervals $[0,2]$ and $[1,3]$. They neither overlap nowhere nor everywhere. –  alex.jordan Feb 24 '12 at 0:38
I thought the same when I looked at it...but this is not about intersections of two parallel lines. It is about finding where two bits of the same line overlap. –  fretty Jun 25 '12 at 10:41

I assume everything takes place in ${\mathbb R}^2$. Let the two segments be $\sigma_1:=[{\bf a},{\bf b}]$, and $\sigma_2:=[{\bf p},{\bf q}]$ and denote by $g_i$ the line spanned by $\sigma_i$. The common points of $g_1$ and $g_2$ are obtained by solving the system $$(1-s){\bf a}+ s{\bf b}=(1-t) {\bf p}+ t{\bf q}\ ,$$ resp. \eqalign{(b_1-a_1)s+ (q_1-p_1)t&=p_1-a_1\cr (b_2-a_2)s+ (q_2-p_2)t&=p_2-a_2\cr}\qquad(*) for $s$ and $t$.

If the determinant $$\Delta:=({\bf b}-{\bf a})\wedge({\bf q}-{\bf p})=(b_1-a_1)(q_2-p_2)-(b_2-a_2)(q_1-p_1)$$ is nonzero then $g_1$ and $g_2$ intersect in exactly one point, and the system $(*)$ has exactly one solution $(s_*,t_*)$. If both $s_*$ and $t_*$ are in the interval $[0,1]$ then the point $${\bf z}:=(1-s_*){\bf a}+ s_*{\bf b}=(1-t_*) {\bf p}+ t_*{\bf q}$$ is the unique point common to the two segments $\sigma_1$ and $\sigma_2$.

If $\Delta=0$ then the two lines $g_1$ and $g_2$ are disjointly parallel or coincide. This means that the system $(*)$ has no solutions or infinitely many solutions $(s,t)$. The truth will come to the fore using Gaussian elimination. The second (more interesting) case obtains when the second equation $(*)$ is in fact a multiple of the first equation.

At this point we know that in fact $g_1=g_2$, and we have to test whether a certain equation of the form $$\ell:\quad b s+ q t=p$$ has solutions $(s,t)\in[0,1]^2=:Q$. This involves intersecting $\ell$ with the square $Q$ which in itself is an interesting thing to program.

-


text:
# Summation Notation Ambiguity

1. Mar 13, 2010

### hbweb500

I am working on a problem that uses the notation:

$$\sum_{i,j=1}^n A_{i,j}$$

Where A is an (n x n) matrix. I am a little unsure of what the summation is over, due to the odd notation "i,j = 1". My first guess is that this is shorthand for

$$\sum_{i=1}^n \sum_{j=1}^n A_{i,j}$$

But I am wondering if it could also mean the sum over the diagonal elements of the matrix, i.e.:

$$\sum_{i=1}^n A_{i,i}$$

I am guessing it is the first, but I want to make absolutely sure.

2. Mar 13, 2010

### LCKurtz

Yes, your first guess is the standard interpretation.

3. Mar 13, 2010

### hbweb500

Thanks!

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Summation Notation Ambiguity Date
Summation Notation/Product Jun 13, 2013
How do I write this in summation notation? Feb 11, 2013
Summation Notation for [(i^3)/(N^3)] Jan 14, 2013
Is my summation notation correct? Jan 14, 2013
Summation/Sigma Notation Apr 15, 2012


text:
# A simplified notation for OLS regression

## A simplified regression notation

We introduced some new notation in the textbook, to make the formulae simpler and more focused. In particular, our formula for regressions is slightly different from the traditional formula. We think that it is good practice to write out the formula for each regression that is analyzed. For this reason, it important to use a notation for the regression formula that is as simple as possible and focuses only on what we care about. Our notation is intuitive, but it’s slightly different from traditional practice. Let us explain our reasons.

Our approach starts with the definition of the regression: it is a model for the conditional mean. The formulaic definition of the simple linear regression is $$E[y \mid x]= \alpha + \beta x$$ .

The formulaic definition of a linear regression with three right-hand-side variables is

$E[y \mid x_1, x_2, x_3]= \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \beta_3 x_3$

The regression formula we use in the textbook is a simplified version of this formulaic definition. In particular, we have $$y^E$$ on the left-hand side instead of $$E[y \mid ...]$$. So $$y^E$$ is just a shorthand for the expected value of $$y$$ conditional on whatever is on the right-hand side of the regression.

Thus, the formula for the simple linear regression is $$y^E = \alpha + \beta x$$, and $$y^E$$ is the expected value of $$y$$ conditional on $$x$$. The formula for the linear regression with three right-hand-side variables is

$y^E= \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \beta_3 x_3$

and here $$y^E$$ is the expected value of $$y$$ conditional on $$x_1$$, $$x_2$$, and $$x_3$$. Having $$y^E$$ on the left-hand side makes notation much simpler than writing out the conditional expectation formula $$E[y \mid ...]$$, especially when we have many right-hand-side variables.

In contrast, the traditional regression formula has the variable $$y$$ itself on the left-hand side, and has an additional element, the error term. This different notation acknowledges the fact that the actual value of $$y$$ is equal to its expected value (defined by the model) plus a deviation from it. For example, the traditional formula for the linear regression with three right-hand-side variables is

$y= \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \beta_3 x_3 + e$

Importantly, it does not imply, that the model is about the conditional mean.

Our notation is simpler, because it has fewer elements. More importantly, our notation makes it explicit that the regression is a model for the conditional mean. It focuses on the data that analysts care about (the right-hand-side variables and their coefficients), without adding anything else. Especially for introductory courses, we believe, it’s a better way.

Note that there are reasons to go beyond this notations. With causal analysis, we may come back to the traditional model and have a term capturing unobserved heterogeneity (often denoted by u not e.) For instance, when introducing potential outcomes, it may be useful. For prediction, we may also have a model with explicitly having a prediction error: the difference between actual and predicted value for a given $$y_i$$.

But, well, for most uses of a regression model, we suggest building on the expected value as a starting point to push the idea of regression as a model of conditional mean, and using our shorthand to simplify notation.

Tags:

Updated:


text:
# summarize: Produce Summary Tables for Data Sets In papeR: A Toolbox for Writing Pretty Papers and Reports

## Description

The function produces summary tables for factors and continuous variables. The obtained tables can be used directly in R, with LaTeX and HTML (by using the xtable function) or Markdown (e.g. by using the function kable).

## Usage

 1 2 3 4 5 6 summarize(data, type = c("numeric", "factor"), variables = names(data), variable.labels = labels, labels = NULL, group = NULL, test = !is.null(group), colnames = NULL, digits = NULL, digits.pval = 3, smallest.pval = 0.001, sep = NULL, sanitize = TRUE, drop = TRUE, show.NAs = any(is.na(data[, variables])), ...)

## Arguments

 data data set to be used. type print summary table for either numeric or factor variables. variables character vector defining variables that should be included in the table. Per default, all numeric or factor variables of data are used, depending on type. variable.labels, labels labels for the variables. If variable.labels = NULL (default) variables is used as label. If variable.labels = TRUE, labels(data, which = variables) is used as labels. Instead of variable.labels one can also use labels. group character specifying a grouping factor. Per default no grouping is applied. test logical or character string. If a group is given, this argument determines whether a test for group differences is computed. For details see summarize_numeric and summarize_factor. colnames a vector of character strings of appropriate length. The vector supplies alternative column names for the resulting table. If NULL default names are used. digits number of digits to round to. For defaults see summarize_numeric and summarize_factor. digits.pval number of significant digits used for p-values. smallest.pval determines the smallest p-value to be printed exactly. Smaller values are given as “< smallest.pval”. This argument is passed to the eps argument of format.pval. See there for details. sep logical. Determines whether separators (lines) should be added after each variable. For defaults see summarize_numeric and summarize_factor. sanitize logical (default: TRUE) or a sanitizing function used to clean the input in order to be useable in LaTeX environments. Per default toLatex.character is used. drop logical (default: TRUE). Determines whether variables, which contain only missing values are dropped from the table. show.NAs logical. Determines if NAs are displayed. Per default, show.NAs is TRUE if there are any missings in the variables to be displayed (and FALSE if not). For details see summarize_numeric and summarize_factor. ... additional arguments for summarize_numeric and summarize_factor. See there for details.

## Value

A special data.frame with additional class summary containing the computed statistics is returned from function summarize. Addtional attributes required for the xtable.summary or print.xtable.summary function are contained as attributes. These are extracted using the function get_option.

## Author(s)

Benjamin Hofner

For details see summarize_numeric and summarize_factor.

Conversion to LaTeX tables can be done using xtable.summary and print.xtable.summary.

get_option

## Examples

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 if (require("nlme")) { ## Use dataset Orthodont data(Orthodont, package = "nlme") ## Get summary for continuous variables (tab1 <- summarize(Orthodont, type = "numeric")) ## Change statistics to display summarize(Orthodont, quantiles = FALSE, type = "numeric") summarize(Orthodont, quantiles = FALSE, count = FALSE, type = "numeric") summarize(Orthodont, mean_sd = FALSE, type = "numeric") ## Get summary for categorical variables (tab2 <- summarize(Orthodont, type = "fac")) ## use fraction instead of percentage summarize(Orthodont, percent = FALSE, type = "fac") ## Using the tables with Markdown if (require("knitr")) { kable(tab1) kable(tab2) } ## Using the tables with LaTeX if (require("xtable")) { xtable(tab1) ## grouped table xtable(summarize(Orthodont, group = "Sex")) xtable(tab2) } }

### Example output

Loading required package: car

Attaching package: 'papeR'

The following object is masked from 'package:utils':

toLatex

Factors are dropped from the summary
Factors are dropped from the summary
Factors are dropped from the summary
Factors are dropped from the summary
Non-factors are dropped from the summary
Non-factors are dropped from the summary
Factors are dropped from the summary
NOTE: Output requires \usepackage{booktabs} in your preamble.
\begin{center}
% latex table generated in R 3.4.4 by xtable 1.8-3 package
% Mon Dec 31 17:31:57 2018
\begin{tabular}{llrrr}
\toprule
& Level &   & N & \% \\
\cmidrule{2-2} \cmidrule{4-5}
Subject & M16 &  &   4 & 3.7 \\
& M05 &  &   4 & 3.7 \\
& M02 &  &   4 & 3.7 \\
& M11 &  &   4 & 3.7 \\
& M07 &  &   4 & 3.7 \\
& M08 &  &   4 & 3.7 \\
& M03 &  &   4 & 3.7 \\
& M12 &  &   4 & 3.7 \\
& M13 &  &   4 & 3.7 \\
& M14 &  &   4 & 3.7 \\
& M09 &  &   4 & 3.7 \\
& M15 &  &   4 & 3.7 \\
& M06 &  &   4 & 3.7 \\
& M04 &  &   4 & 3.7 \\
& M01 &  &   4 & 3.7 \\
& M10 &  &   4 & 3.7 \\
& F10 &  &   4 & 3.7 \\
& F09 &  &   4 & 3.7 \\
& F06 &  &   4 & 3.7 \\
& F01 &  &   4 & 3.7 \\
& F05 &  &   4 & 3.7 \\
& F07 &  &   4 & 3.7 \\
& F02 &  &   4 & 3.7 \\
& F08 &  &   4 & 3.7 \\
& F03 &  &   4 & 3.7 \\
& F04 &  &   4 & 3.7 \\
& F11 &  &   4 & 3.7 \\
\cmidrule{2-2} \cmidrule{4-5}
Sex & Male &  &  64 & 59.3 \\
& Female &  &  44 & 40.7 \\
\bottomrule
\end{tabular}
\end{center}

papeR documentation built on March 23, 2021, 1:08 a.m.


text:
### Sample Papers

Download the PDF Sample Papers Free for off line practice and view the Solutions online.

### Book Store

Currently only available for.
CBSE

### Test Series

Pre-Board Question Papers are now available online for students to practice and excel the exams based on the latest syllabus and marking scheme given by respective boards.

# CBSE Class 12 History Solved Question Paper 2016

1.

Point out one similarity and one dissimilarity between Lingayats and Nayanars.

Similarity between lingayats and Nayanars –

i. Both opposed the caste system

ii. Both worshipped lord Shiva

Dissimilarity –

i. Nayanars were not confined to any particular region while the lingayats were popular in Karnataka

ii. Nayanars worshipped Shiva in both an idol and linga form whereas Lingayats worshipped only the linga form

2177 Views

2.

Mention any two changes that were observed after 1900 BCE in Harappan civilisation. What could have brought these changes ? Explain.

Changes observed after 1900 BCE in Harappan Civilization:

i. There is a decline in the material culture and disappearance of distinctive artefacts.

ii. Long distance trade disappeared along with craft specialisation.

Reasons for changes:

i. Climatic change and deforestation.

ii. Excessive floods and overuse of the landscape.

2201 Views

3.

“The battle between the hoe and the plough was a long one”. Substantiate the statement with reference to the Santhals and Paharis of Raj Mahal Hills during 18th century.

The battle between the hoe and the plough was a long one:

i. The British wanted to bring more land under cultivation for increasing agricultural produce and revenue.They failed to convince the Paharias to practice settled
agriculture.

ii. Hill folk in the Rajmahal hills were known as Paharias. They depended on forest produce and shifting cultivation or their living and grew a variety of pulses and millets for consumption.

iii. The British gave land to Santhals (Damin-i-koh) to settle in cultivate. The Santhals cleared land and converted it into cultivable land.

iv. Santhals displaced the Paharias. They practiced plough agriculture and ploughed land to grow rice and cotton.

1806 Views

4.

“The mid first millennium BCE is often regarded as a major turning point in world history.” Justify.

The reasons:

i. Emergence of various thinkers like Socrates, Buddha etc in different parts of the world

ii. Development of kingdoms and cities

iii. Changes in social and economic life

iv. Emergence of Upanishads in India and compilation of Rig Veda.

1621 Views

5.

Examine how Lord Dalhousie’s policy of annexation created dissatisfaction amongst the people of Awadh.

Lord Dalhousie’s policy of annexation:

i. Imposition of Subsidiary Alliance reduced the powers of the Nawab. Soon after the Nawab was dethroned by the British and exiled on the basis of misgovernment. Many people followed the Nawab when he left Lucknow

ii. Dissolution of the court and its culture led many people to lost their livelihood. There was widespread sense of grief and loss

iii. The sepoys of the British army who came from Awadh carried over their grievances to the sepoy lines

iv. The new land revenue system introduced by the British imposed high taxes and was unpopular. The dissatisfaction resulted in a popular revolt.

1414 Views

6.

Who was John Marshall ? How did he mark a change in the Indian Archeology ?

John Marshall was an archaeologist

He announced the discovery of a new civilization i.e. Indus Valley Civilization/ Harappa culture

5212 Views

7.

Highlight any four aspects observed by the Portuguese Traveller Barbosa on the Urban Core of the Vijayanagara Empire.

Barbosa has described that the houses of ordinary people are thatched:

i. Houses are well built and strong

ii. Houses were arranged according to occupations in long streets with many open places

iii. Entire area had many shrines and small temples which indicates the prevalence of variety of cults

iv. Rainwater tanks and temple tanks served as sources of water for the people.

1627 Views

8.

State the inherent problems faced by Al-Biruni in the task of understanding Indian Social and Brahmanical practices. Mention any two sources that provided him the support.

Problems faced by Al-Biruni in understanding India:

i. He could not understand Sanskrit language and found it difficult to translate Sanskrit into Arabic and Persian.

ii. Could not understand the difference in religious beliefs and practices and self-absorption of Brahmanas local population

He depended on Brahmanical works like

i. Vedas and Puranas

1659 Views

9.

How did Indian hill stations become racial enclaves for the Europeans in the 19th century ? Explain two reasons.

i. Europeans recreated settlements reminiscent of their homes.

ii. Churches and educational institutions were set up by the British.

1767 Views

10.

Every citizen in a free state should be treated in a manner that satisfied not only his material wants but also his spiritual sense of the self respect and the majority community has an obligation to try and understand the problems of the minorities and empathise with their aspiration.

How could a citizen of a free nation express his imbibed values of equality and social justice while dealing with the members of the minority community ? Explain.

i. Abolishing social dogmas

ii. Respecting rights of the minority community.

iii. Granting them privileges, Equality, Social justice.

iv. Integration into mainstream and creating opportunities for them.

1155 Views


text:
# Noethers theorem, physics and mathematics

1. Mar 28, 2015

### JVM

Hello,

First of all, I'm sorry for the long post. I've tried to make it self consistent, but some prior knowledge will be assumed in both physics and differential geometry.
Also maybe some math will be displayed wrongly, it's my first time here...

In physics people usually describe Noether's theorem by calculating the variation of the Lagrangian, which for a symmetry of the theory will need to be equal to a total derivative:

\delta \mathcal{L} = \epsilon^A \partial_{\mu} (\frac{\delta \mathcal{L}}{\delta \partial_{\mu}\phi^i} \Delta_A \phi^i) = \epsilon^A \partial_{\mu} K_A^{\mu}.

Then a Noether Current can be defined as

J^{\mu}_A = -\frac{\delta \mathcal{L}}{\delta \partial_{\mu}\phi^i} \Delta_A \phi^i + K_A^{\mu}.

For fields which abide the equations of motion this current is then conserved: $\partial_{\mu} J^{\mu}_A = 0$. This is just because the variation of the action will be set to zero using Stokes and assuming the fluctuations on the boundaries will go to zero fast enough.

In mathematics it is done a little different. So far I've tried to describe everything as good as possible such that a reader with some physics background is familiar with everything. Now comes a little differential geometry and I will assume that some basic stuff is known, so if you're not too familiar with it I guess you shouldn't let this question bore you.

A Liouville vectorfield

D \in \mathcal{X}(TQ),

where Q is some smooth manifold, is defined such that her flow has the following form:

\begin{align*}
\Phi_t : TQ &\rightarrow TQ \\
(q^i,v^i) &\mapsto (\bar{q}^i = q^i, \bar{v}^i = e^t v^i)
\end{align*}.

The energy function associated to a function $L$ is then defined as

E_L = D(L) -L.

The Lagrangian vector field associated to a regular function L on TQ is the the vector field $\Gamma$ such that

i_{\Gamma}\omega_L = -dE_L

where

\omega_L = d\theta_L

is the Poincare-Cartan 2-form associated to L, and d is the exterior derivative. Finally we can now introduce Noether's theorem;

Let Y be a vector field on TQ, such that:

\mathcal{L}_Y \theta_L = df

for some function f, and:

Y(E_L) = 0.

Then Y is a symmetry of $\Gamma$ and associated to Y there is a first integral F, determined by

F = f - <Y,\theta_L>.

And with every first integral F of $\Gamma$ there is a symmetry Y which abides the above mentioned properties.

Now comes the question...

Although in physics we are usually interested in invariance of the action, especially in field theory (for example for space-time symmetries), the Noether theorem I just described gives a one to one correspondence between the symmetry of the Lagrangian and the conserved quantities. Now I know that what I just described is valid for mechanics and not field theory, and when you want to describe field theory in this geometric formalism you need to look at jet bundles. Is it then so that when you use jet bundles you will eventually get a correspondence between the action and conserved quantities?
And am I wrong to think that actually in mechanics the symmetries will be described with the action as well?

2. Mar 28, 2015

### Geometry_dude

While I have not understood this stuff completely myself (gotta learn this one day), I think this might help:

http://physics.stackexchange.com/questions/82410/noether-first-and-second-theorem

EDIT: In the general theory, when everything is "nice" (smooth, you have actual lie groups etc..), you typically have a base manifold $\mathcal Q$ and a (or more) smooth section $\phi \in \Gamma^\infty \left( \mathcal Q, E \right)$ of a vector bundle $E$ that is equipped with a connection $\nabla$ (out of which one can construct a differential $d$). The action $\mathcal S$ is then a complex/real functional on that space of sections defined as follows:
$$\mathcal S \left( \phi \right) = \int_{\Omega \subseteq \mathcal Q} \mathcal L \left( \phi, \nabla \phi \right) \quad .$$
Here $\mathcal L$ is a map that takes the section and ''derivatives'' (beware of the relativity principle!) as input and spits out a complex/real density.

To get any conserved quantities you need a Lie group action (horizontal, vertical or both) on $E$, that leaves this integral invariant. Note that a similiar construction can be put up for principal bundles instead of vector bundles.

Hope this helps.

Last edited: Mar 28, 2015
3. Mar 29, 2015

### JVM

And thank you for the link to the discussion on stackexchange.

I think that what you said, and what is said in the stackexchange discussion, that Lie group actions are needed, is indeed the formulation that is usually used in physics. But the theorem I described I think is on a higher than that, in the sense that it does not need to make use of any action of a Lie group.

I'm not sure, but maybe the following application of the theorem helps to find the link with the formulation in physics:

If

X \in \mathcal{X}(Q)

such that X^c(L) = 0 (the complete lift), then Y := X^c is a Noether symmetry (as described in my first post) and the first integral is of the form

F = X^v (L)

where X^v is the vertical lift of X.

4. Mar 29, 2015

### Geometry_dude

Well, as far as I understand it - and I am not very deep in the subject, in the ''standard mass point mechanics without crazy constraints'' case you have a Lagrangian $L \in C^\infty \left( T \mathcal Q , \mathbb R \right)$ and some kind of natural symplectic structure $\omega$ on the tangent bundle. Then this gives you a Hamiltonian system on the tangent bundle and for every smooth function $f$ on the tangent bundle you can take the corresponding Hamiltonian vector field $X_f$, which should be a constant of motion if and only if its flow preserves the Lagrangian $L$:

$$\mathcal L _ {X_f} L = 0$$

I don't know how that relates to Noether though and so I can't construct the generalization for ''field theory''.

5. Apr 19, 2015

### Geometry_dude

I have continued thinking about this, because I find it quite interesting myself. It's really hard to find references that explain this stuff in a rigorous, coordinate free and understandable way.

As far as I have figured it out, the variation of the action only gives you the Euler-Lagrange equations if you have some way to transform the integral of the stuff you don't like into an integral over the boundary of your integration domain, which you require to vanish.

For example, if the action is a functional on the space of differentiable curves (then the Lagrangian takes the corresponding curve on the tangent bundle and spits out a function on the domain of the curve), i.e.

$$\mathcal S \left( \gamma \right) := \int\limits_{(\tau_1, \tau_2) \subseteq R} L \left( \gamma \left( \tau \right), \frac{d}{d \tau} \right) \, d \tau$$

, you just use that $df/d\tau \, d\tau = d f$ and you get out "the bad part", because $f$ is constant on $\partial[\tau_1, \tau_2] = \lbrace \tau_1, \tau_2 \rbrace$.

Something similiar can be done in the case of tensor fields. If $\phi, \chi$ are tensor fields of same valence on an orientable pseudo-Riemannian manifold $\left( \mathcal Q, g \right)$ with canonical volume form $\mu$ and Levi-Civita connection $\nabla$, then we can define the action as
$$\mathcal S \left( \phi \right) = \int\limits_{\Omega} L \left( \phi, \nabla \phi \right) \, \mu$$
where, for convenience, $\Omega$ is compact.

The variation now works in complete analogy to http://en.wikipedia.org/wiki/Functional_derivative#Formula assuming that the variation tensor field $\chi$ vanishes on the boundary $\partial \Omega$. Using that for vector fields $X$ we have $\mathcal L _X \mu = \text{div} X \, \mu$ with $\text{div} X = \text{tr} (\nabla X)$ and Stoke's theorem, we arrive at

$$\frac{\partial L}{\partial \phi} = \text{div} \frac{\partial L}{\partial \left( \nabla \phi \right)}$$

Having this, one can in principle set up a Noether's theorem, whose proof is analogous to the standard one. I haven't gotten to this yet though. :)

EDIT:

I have also thought about the other approach. To get a kind of Lagrangian mechanics on the tangent bundle, you need a 1-form $\theta$ ("momentum") and a function $L$ ("Lagrangian") on the tangent bundle, then you can consider vector fields $X$ that satisfy
$$\mathcal L _X \theta = d L$$
whose integral curves represent the solution of this equation of motion. My statement from above that the Lagrangian is preserved under the flow of $X$ was wrong, because it does not follow from the above equation. Indeed the Lagrangian is usually not a constant of motion.

Last edited: Apr 19, 2015
6. Apr 19, 2015

### Terandol

I'm not sure if you are aware of it or not but in my opinion one of the best sources that deals with variational problems and proves, among many other things, Noether theorems in the very general setting of local functionals defined for the infinite jet bundle of any fibered manifold (so in the simplest case of a particle moving on the line say, you think of the motions of the particle as sections of the trivial bundle $\mathbb{R}\times \mathbb{R}\to \mathbb{R}$ but the theorems automatically hold for vector/tensor fields or even something like Chern Simons or Yang Mills theories where the fields are connections on a principal bundle since these are all examples of sections of fiber bundles) is the following book by Ian Anderson: http://math.uni.lu/~jubin/seminar/bicomplex.pdf.

In it is constructed the variational bicomplex which I think is a very interesting way of encoding these variational type problems into a bicomplex (it is essentially the differential forms on the infinite jet bundle but bigraded and with two differentials that kind of split the exterior derivative into horizontal and vertical components) and then you can use the tools of homological algebra like cohomology and spectral sequence arguments to try and solve the problems which started out as more analysis/differential equations type questions.

7. Apr 20, 2015

### JVM

Hey,

Thanks for the input.

I have seen how to find the Euler-Lagrange equations for fields (there might be several different approaches), by using second order jet bundles, and indeed sections. It is like follows.

Suppose that the Lagrangian L

L \in C^{\inf}(J^1 \pi)

and C a compact m-dimensional submanifold of your underlying manifold M. Then if \phi is a local section of \pi, and \phi is an extremal of L, then \phi satisfies

(j^2\phi)*(\frac{\partial L}{\partial u^a} - \frac{d}{dxî}\frac{\partial L}{\partial u_i^a})

where \phi is an extremal of L when

\int (j^1\phi)*d_{X^1}L \Omega

With X a vertical vector field on the bundle, which vanishes on the border.

(This is from 'The geometry of jet bundles' by David Saunders; http://bookshub.org/book/9780521369...es-English-Subsequent-Edition-by-D-J-Saunders , I'm sorry for the link to some site which sells the book, it was just the first link I found on the book.)

(And I'm sorry for these \phi in the sentences)

8. Apr 22, 2015

### JVM

So I'm sorry if I was unclear before, but my main question was about the link between the different formulations of Noethers theorem in physics and mathematics, or if they are actually not equivalent and it is simply the case of using the same terms in different contexts.
Especially because in physics the action is the main object and in differential geometry it is the Lagrangian in concern for the symmetries, as far as I've read/learned.