text:
\begin{document}

\title{\Large A Micro-Scale Mobile-Enabled Implantable Medical Sensor}

\author{M. Okwori, A. Behfarnia, P. Vuka,~\IEEEmembership{Student Members,~IEEE,} \\ A. Eslami, ~\IEEEmembership{Member,~IEEE}

\thanks{The material in this paper was presented, in part, at the 17th International Conference on Nanotechnology (IEEE-NANO), 2016 \cite{vuka2017mobile}.}

\thanks{M. Okwori, A. Behfarnia, P. Vuka and A. Eslami are with the Department of Electrical Engineering and Computer Science, Wichita State University, Wichita, KS, USA ~(emails: \{mxokwori, axbehfarnia, pxvuka\}@shockers.wichita.edu, and ali.eslami@wichita.edu).}
}

\IEEEtitleabstractindextext{
\vspace{-.7 in}
\begin{abstract}
Micro-scale implantable medical devices (IMDs) extend the immense benefits of sensors used in health management. However, their development is limited by many requirements and challenges, such as the use of safe materials, size restrictions, safe and efficient powering, and selection of suitable wireless communication technologies. Some of the proposed wireless communication technologies are the terahertz (THz) radio frequency (RF), and ultrasound.

This paper investigates the use of {\em magnetic induction-based backscatter communication} as an alternative technology. In particular, the goal is to provide a practical design for a micro-scale IMD, referred to as a ``biomote'' here,  that can communicate with a wearable or handheld device such as a cell phone, tablet, or smart watch.
First, it is demonstrated that communication via magnetic induction can be established between a biomote and such an external reader. Then, low-power modulation and error-correction coding schemes that can be implemented in micro-scale are explored for the mote. With the aim of increasing reliability and accuracy of measurements through mass deployment of biomotes, suitable low-power media access control (MAC) schemes are proposed, and the feasibility of their implementation in micro-scale is highlighted. Next, assuming that the human body is an additive white Gaussian noise (AWGN) channel, the performance of the mote is simulated and analyzed.
Results of this analysis asserts that a communication range of at least few centimeters is achievable with an acceptable bit error rate.

Finally, from the analysis of the MAC schemes, the optimum number of motes to be deployed for various read delays and transmission rates is obtained.
\end{abstract}

\begin{IEEEkeywords}
Biomote, Implantable Medical Device, Low-Power Modulation, Error-Correction Coding, Resource-Constrained MAC
\end{IEEEkeywords}}

\maketitle
\IEEEdisplaynontitleabstractindextext
\IEEEpeerreviewmaketitle

\section{Introduction\label{sec:Introduction}}

Miniaturization of IMDs to micro-scale, and ultimately nano-scale, holds great promises for enabling various in-vivo applications leading to early detection of cancer and heart attacks, deployment of nanorobots, and realization of smart drug delivery \cite{durairaj2012nano,bourzac2012carrying}.
 A number of fields are actively being investigated in the quest to develop smaller IMDs. These efforts include development of biocompatible nanomaterials, nano-electronic components, battery-less or external powering techniques, and suitable communication techniques. Biocompatible materials such as biopolymeric materials \cite{yates2013life} and DNA-based polymer coatings \cite{hong2018compact} have been proposed. Nano-scale electronic components such as diodes, bistable switches, and nanowires have been fabricated and characterized in laboratories \cite{haselman2010future}. Also, there are ongoing efforts towards battery-less, energy harvesting, or external powering of micro- to nano-scale devices \cite{liu2008mems,Deterre2012, mujeeb2015optical, Charthad2015mm,Ho2014}. A variety of communication techniques are also being investigated for deployment in IMDs. Three major approaches are the use of terahertz (THz) radio frequency (RF) communication \cite{jornet2011channel,akyildiz2016realizing,akyildiz2014teranets,akkari2016joint}, ultrasonic communication \cite{Peisino2013,Davilis2010,Galluccio2012challenges}, and optical communication \cite{schuettler2012hermetic,nafari2015metallic,song2012signal,shinagawa2013compact}.

THz communication employs electromagnetic waves in a terahertz frequency band to communicate data, thereby resulting in two major benefits. First, it requires an antenna size of a few micrometers, which satisfies the biomote's size limitation \cite{zakrajsek2016lithographically,jornet2013graphene,llatser2012graphene}. Second, it can potentially
provide a large bandwidth. However, THz communication for biomotes undergoes extremely high attenuation in body tissues, as evidenced by a penetration depth of only up to a few hundred micrometers in fresh tissue \cite{pickwell2006biomedical,oh2013measurement}. This high attenuation limits its effective communication range inside the body to less than 1 or 2 cm. Optical and near-infrared communications also suffer from the same issues \cite{mujeeb2015optical}.

Acoustic waves propagate very well in water and appear suitable for communication in the human body which is comprised of 65\% water. In addition, the Food and Drug Administration (FDA) allows an intensity of $7.2\ mW/mm^2$ for diagnostic ultrasound applications \cite{Charthad2015mm,Galluccio2012challenges,Davilis2010}, which is about two orders of magnitude higher than the safe RF exposure limit in the body ($10-100\  \mu W/mm^2$ \cite{federal1996guidelines,ieee1992ieee}). Despite these advantages, ultrasonic communication needs to overcome major challenges before being employed in a biomote. The large impedance mismatch at the air-tissue interface causes more than 99.95\% of the acoustic energy to be reflected back into the tissue \cite{freitas1999nanomedicine,dove2003notes,cannata2003design}. This results in a large attenuation due to the large reflection at the air-tissue interface. Also, the small size of the biomote requires a correspondingly small ultrasonic transducers to generate and detect acoustic waves. The thickness of this transducer, which is often a piezoelectric device, is inversely related to its resonating frequency. As such, the small size of the device results in a large resonating frequency. This is a significant drawback since attenuation of acoustic waves inside the body increases exponentially with both frequency and distance. For instance, at 15.4 MHz, the signal attenuation in 10 cm in blood (best case), liver, and heart (worst case) can be calculated as 31.4 dB, 115.19 dB, and 162.68 dB, respectively \cite{Galluccio2012challenges,Peisino2013}.

 The challenges mentioned above might be overcome if a network of biomotes is deployed. \cite{pierobon2014routing,akyildiz2014teranets,akyildiz2010electromagnetic,Seo2013}. However, that bears its own complications. For THz communication, the line-of-sight requirement, and complicated implementation circuitry make implementation of the networking very difficult in micro-devices working in an uncontrolled environment such as the human body. Also, an ultrasonic-based network of motes will require one or more interrogators to be implanted under the skin in order to receive the ultrasonic signal and convert it to a radio signal that can be detected by an external wireless reader \cite{Seo2013}.

An alternative means of communication is the use of magnetic fields. Magnetic induction for powering and near-field communication (NFC) with medical implants has been studied in the literature (e.g., see\cite{ghovanloo2007wide,sutardja2017isolator, Goodarzy2015,Simard2010}). While measurement ranges of a few centimeters have been achieved, the smallest implants are at least a few millimeters in each dimension. To the best of our knowledge, this work is the first comprehensive study on magnetic-induction communication and powering of implantable {\em micro}-devices.
In this work, we present a proof-of-concept for a biomote that is externally powered and communicates using magnetic induction to a hand-held device for processing and diagnosis.
A possible design for the biomote, and how it can be used are illustrated in Figs. \ref{fig:Biomote_design} and \ref{fig:Biomote_application}, respectively.  The biomote has a communication circuitry, a dumbbell substrate, an inductive coil, and a micro- (or nano-) biosensor. When an NFC-enabled reading device, such as a cell phone, is held over the mote, the two coils are coupled, and power is induced in the mote. The mote then uses backscatter communication to send its measured data to the reading device.

\begin{figure}
\centering
{\includegraphics[width =3in , height=2 in]{Images/mote_design}}
\caption{Biomote structure showing circuit, inductive coil and sensor.}
\label{fig:Biomote_design}
\end{figure}

\begin{figure}
\centering
{\includegraphics[width =3 in , height=2.4 in]{Images/mote_application}}
\caption{Biomote sending sensed data to a coupled reader.}
\label{fig:Biomote_application}
\end{figure}

The main contributions of this work are summarized as follows:
\begin{itemize}
\item We model the magnetic induction-based communication for a micro-scale coil in the mote, and provide a detailed analysis demonstrating that communication can very well be achieved within the reception sensitivity of today's handheld devices. In our analysis, we illustrate the trade-offs that emerge from the selection of resonance and subcarrier frequencies, and permeability of the coil's core material. We further discuss the impact of all the above on the communication bandwidth and signal attenuation.
\item We consider the size and complexity limitations of the mote to choose simple and efficient modulation and error-control coding techniques. We then provide evidence of the feasibility of implementation of the selected schemes in micro-scale.
\item We evaluate the performance of the proposed physical layer, i.e., modulation and error-control coding schemes, by simulating the bit error rate at the reader. From the evaluation, we obtain the maximum distance between the mote and the reader for an acceptable BER.

\item We then use the results of the physical layer analysis to investigate the implementation requirements and performance of simple and efficient MAC schemes. We consider three schemes: binary tree protocol, slotted ALOHA, and code division multiple access (CDMA). We also provide evidence of the feasibility of their implementation in micro-scale. In our analysis, we investigate the relationship between the mote transmission rate and the read-time required for various numbers of motes deployed. In case of CDMA, we also explore the relationship between the spreading code length and the number of successful readings from the motes deployed.  From the simulation results, we recommend optimum mote design parameters and utilization specifications.
\end{itemize}

The rest of the paper is organized as follows. Section \ref{sec:Methodology} provides a detailed design of the biomote's physical and MAC layers, including the inductive coil and selection of the modulation, error-control coding, and MAC schemes. Section \ref{sec:Results-and-Discussion} presents simulation results for the analysis of both the physical layer and the MAC layer schemes. Section \ref{sec:Conclusion} concludes the paper.

\section{Design of Micro-Scale Biomote} \label{sec:Methodology}

A block diagram demonstrating the building components of our proposed device is shown in Fig. \ref{fig:block_diagram}. The main blocks are the following: an inductive coil as a transceiver antenna, modulation and error-correction blocks, sensors to collect data, and a MAC scheme. Once the reader and the biomote are placed close to each other, the biomote starts collecting energy from the reader through inductive coupling, such that the induced voltage at the mote turns on all the blocks. In the following sections, the implementation of these blocks, except the sensor, is comprehensively investigated to address the major challenges for the proposed micro-scale device.

\begin{figure}
\centering
{\includegraphics[width =5 in , height=2 in]{Images/block_diagram}}
\caption{ Block diagram of the mote showing powering and communication systems.}
\label{fig:block_diagram}
\end{figure}

\subsection{Micro-Scale Magnetic Induction-Based Communication}\label{subsec:System-Design-and}

Environment, size of antenna, and complexity of a device are crucial points in determining the type of modulation in wireless communication. Taking these into account, and inspired by passive radio-frequency identification (RFID), we employ load modulation (a.k.a. modulated backscatter) to transmit data from the biomote to the reader. In load modulation, the impact of a coupled biomote on the reader can be modeled by a transformed impedance \cite{sun2010magnetic}, denoted here by $Z_{br}$. Controlling $Z_{br}$ at the mote using an on-off switching circuit could change the voltage at the reader. If timing of the switching circuit is controlled by data at the biomote (sensor output), this data can be transferred to the reader. The reader then applies a bandpass filter to extract transmitted data. Load modulation works in a ``near field'' where the distance between a transmitting coil and a receiving coil does not exceed $\lambda/2\pi$, where $\lambda$ is the wavelength. Since the resonance frequencies considered in this paper are less than $100$ MHz and the communication range is within a few centimeters, load modulation can be safely employed.

\begin{figure}
\centering
{\includegraphics[width =6 in , height=2 in]{Figs/Coil_to_Coil}}
\caption{ Communication using magnetic induction between reader and biomote: (a) structure, (b) parameters of equivalent circuit: $N$ is the number of turns, $a$ is the radius of a coil, $d$ is the diameter of wire (thickness), $r$ is the distance between devices, $R_0$  is the resistance of unit length, $R$ is the resistance of a coil, $L$ is self inductance, and $M$ is mutual induction between coils.}
\label{fig:C_2_C}
\end{figure}

In order to measure the received power at the reader, we use equivalent circuits for transceiver coils. Fig. \ref{fig:C_2_C} shows the structure and parameters of the equivalent circuit of antenna coils. We select the parameters in a way that the hight and diameter of the biomote does not exceed $250 \,  \mu m$.
Here, we use copper and gold for the coils of the reader and biomotes, respectively. Also, we assume that the voltage in the reader is $3.8$ v (the voltage of iphone 6 \cite{wiki_phone}).
As can be seen in Fig. \ref{fig:C_2_C}, coils on both sides along with parallel capacitors ($C_r$ and $C_b$) form resonant circuits. For our analysis in this paper, we consider three resonant frequencies: $1$, $13.56$, and $100$ MHz. It should be noted that, due to the skin effect, this frequency affects the resistance of the coils, and hence, their impedance.

The power transmitted by the reader and received at the biomote can be obtained as
\begin{align}
\notag &P_t = Re \Big\{ \frac{ V_{r}^2}{( Z_{br} + Z_r )} \Big\}, \\
&P_r = Re \Big\{ \frac{Z_L \ V_{rb}^2}{( Z_{rb} + Z_b + Z_L)^2} \Big\},

\label{eq:power_r}
\end{align}
respectively. Her, $Z_b$ is the impedance of the coil at the biomote, $Z_r$ is the impedance of the coil at the reader, $Z_{br}$ is the impact of biomote 's impedance on the reader, $Z_{rb}$ is the impact of reader's impedance on the biomote, $V_{rb}$ is the induced voltage by the reader on the biomote, and $Z_L$ is the impedance of the load at the biomote. The analysis leading to eq. (\ref{eq:power_r}) is well-known, and its details can be found in \cite{sun2010magnetic}.
It is worth noting that these equations hold for the best case scenario when the two coils are positioned in a coaxial fashion. However, the analysis can be extended to a biomote with a tri-directional (3D) coil to address the problem of orientation. More information about 3D coils can be found in \cite{3DCoil97} and \cite{3DCoil14}.

\begin{figure} [t]
\centering
{\includegraphics[width =4.6 in , height=3.2 in]{Figs/Backscattering2}}
\caption{ Signal powers at the reader: (a) transmitted and received powers at the reader, (b) received backscatter power at the reader compared to noise. Parameters are chosen as follows: $d= 6$ cm (distance between devices), $f_c = 1$ MHz (resonance frequency), and $f_s = 62.5$ KHz (subcarrier frequency).
}
\label{fig:BackS}
\end{figure}

To gain a better understanding, Fig. \ref{fig:BackS} shows both the transmitted power and the received power at the reader. As can be seen, the transmitted power peaks at the resonance frequency ($f_c$),  $1$ MHz in this figure. The received backscatter power (from the biomote) experiences a roundtrip path loss ($PL$) and a sideband attenuation ($A_s$). To minimize $PL$, regardless of changing the coils' parameters such as the number of turns, one could use ferrite cores with high permeability materials in both of them. To reduce $A_s$, as shown in Fig. \ref{fig:BackS}, we can see that the closer the sideband is to the resonance frequency, the less we are affected by the attenuation. However, if the distance between the resonance frequency and the subcarrier frequency ($f_s$) is reduced, the available bandwidth will also be reduced. Hence, the trade-off between attenuation and bandwidth should be considered in an optimum design.
It is also worth mentioning that the subcarrier signal at the mote can be obtained from the carrier signal using a frequency divider which is essentially a very simple shift register. Therefore, we often have $f_s = \frac{f_c}{2^n}$, where $n$ is the length of the shift register.

 \renewcommand{\arraystretch}{1.6}
\begin{table}
\centering
\caption{Received backscatter power at the reader from the biomote. Distance between the two devices is $6$ cm. Here, $P_{tx}$ and $P_{re}$ are the peaks of the transmitted power and the received backscatter power at the reader, respectively. $f_s$ is the frequency of switching load at the biomote, $L$ is path loss, and $A_s$ is sideband attenuation.}
\label{tb:calc_fc}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{1}{|p{4.8em}|} {\footnotesize Resonance Frequency (MHz)} & $R_r$ \footnotesize $(\Omega)$  & $P_{tx}$ \footnotesize $(dB)$ & $R_b$ \footnotesize $(\Omega)$ & $ \mu$ & $f_s$ &$P_{re}$ \footnotesize $(dBm)$ & \multicolumn{1}{p{7.3em}|} {\small Total Loss \footnotesize$(dB)$ \quad \ \ \ $=\ 2\, (PL) + A_s$} \\
\hline
 \renewcommand{\arraystretch}{1.55}
$f_c = 1$ & $5.881$ & $3.90$ & $0.7533$ &  \makecell{$1$\\ $10$ \\ $50$}  & \Large $\frac{f_c}{16}$ & \makecell{$- 128.37$ \\ $-108.38$  \\ $-95.47$} &  \makecell{ $2\, (61.14) + 40$ \\  $2\,(41.14)+60$  \\  $2\,(27.17)+75$ }  \\ \hline
$f_c = 13.56$ & $19.64$ & $-1.34$ & $0.7542$ & \makecell{ $1$ \\ $10$ }  & \Large  $\frac{f_c}{64}$ &  \makecell{$-98.82$ \\ $-80.88$ } &  \makecell{ $2\,(43.74)+40$ \\  $2\,(23.77)+62 $}  \\  \hline
$f_c = 100$& $52.13$ & $-5.58$ & $0.8577$ & $1$ & \large  $\frac{f_c}{128}$& $- 87.95$ &  $2\,(31.18)+50$ \\
\hline
\end{tabular}
\end{table}

Table \ref{tb:calc_fc} shows the received backscatter power at the reader which is located $6$ cm away from a biomote. The calculations are obtained for different values of $f_c$ and relative permeability ($\mu$) of the ferrite core. As can be seen in Table \ref{tb:calc_fc}, increasing $f_c$ reduces path loss. In addition, since $f_c$ is directly proportional to $f_s$ as explained above, increasing $f_c$ leads to a larger bandwidth.
For instance, if $f_c$ is increased from $1$ MHz to $13.56$ MHz, then the bandwidth will also increase from $120$ KHz to $1690$ KHz, assuming that $f_s = f_c/16$.
This achievement, however, is obtained at the price of a higher quality factor ($Q$), which implies higher sideband attenuation. Therefore, increasing $f_c$ reveals a trade-off between available bandwidth and total loss. To address this, one could reduce $f_s$ to avoid severe sideband attenuation, while maintaining an acceptable bandwidth. For example, in Table \ref{tb:calc_fc}, when $f_c$ is increased from $1$ MHz to $13.56$ MHz, $f_s$ is reduced four times.

This reduction keeps sideband attenuation low, while providing approximately $400$ KHz of bandwidth which can be considered acceptable given the bit rate requirements of our particular application.

Another factor that impacts received power is relative permeability or $\mu$. The $\mu$ of a medium that mostly contains air and blood is expected to be around $1$. Although the permeability of a medium is not in our control, one could fill the core of a coil and its surrounding package with a high permeability material such as ferrite to increase the received power. The permeability of ferrite, depending on a number of factors, can be as high as $1700$ \cite{hu2005science}. Since the medium here is a combination of the mote, the human tissue, and the air, its permeability will be a function of that of the ferrite core, the human body, and the air. The core, with the highest permeability, is only a fraction of the medium (approximately $1/240$). Taking this into consideration, the resultant permeability of the entire medium is assumed to be about $10$.

We would like to make two more points regarding the use of highly permeable cores, which also help in further understanding the numbers in Table \ref{tb:calc_fc}.  Although higher values of $\mu$ decrease path loss, they cause higher sideband attenuation. Hence, total loss needs to be paid attention to while considering the use of a high permeability core. Another drawback of high permeability materials is that their $\mu$ often decreases with increasing frequency. The value of $\mu$ for ferrite, for example, could reduce from more than $600$ to $1$ as the frequency increases from $1$ MHz to $100$ MHz \cite{hu2005science}. Thus, while increasing the frequency provides a higher bandwidth, it practically negates the effect of $\mu$ on reducing $PL$.

The sensitivity of the reader also plays a vital role in detecting the backscattered power from the biomote. Sensitivity is the lowest signal power from which  useful information can be obtained. Given the sensitivity, usable received signals are usually within certain power levels. For example, the reference signal receive power (RSRP) as the LTE signal strength indicator could range from $-45$ dBm for excellent signals to $-140$ dBm for poor signals \cite{LTE_RSRP}\cite{LTE_RSRP2}. Taking $-100$ dBm as sufficient received power at the reader, design parameters could be selected similar to those of Table \ref{tb:calc_fc}. Section \ref{sec:Results-and-Discussion} provides more on the achievable communication range and quality as a function of design parameters and noise power.

\subsection{Modulation and Error-Correction Coding for Micro-Scale Design}\label{subsec:physical_layer_design}

Taking complexity and power consumption into consideration, ASK and BPSK are selected for load modulation in the biomote. These modulation techniques are among the simplest digital modulation techniques, and are employed in various biomedical implants\cite{cho2006ask}. Their implementation has also been demonstrated in micro-scale \cite{Hassouni2015design,burasa2016high}, with rates of $160$ kbps and $500$ kbps reported, respectively.

In order to increase the efficiency of magnetic induction-based communication, error-correction coding is introduced at the biomote. Though complex coding schemes can achieve low bit error rates, they are computationally intensive and, hence, unsuitable for the biomote with its size and power constraints. Short linear block codes, namely Hamming (15,11) and Reed-Solomon (31,26), were selected  since they are less complex and can be implemented in micro-scale. Both codes can be implemented on a very small die area using shift registers \cite{yang2012product}.
In this work, since the biomote can only send information, it will need to only implement the encoding circuit. Decoding will be handled at the receiver with much more power and high-end processor. This is quite advantageous because in most error-correction mechanisms, decoding is a significantly more complicated process than encoding.

Hamming code (15,11) has a minimum distance of four, thus can detect three errors and correct one error. Reed-Solomon (RS) codes perform better than Hamming codes because they have the ability to correct both random and burst errors. RS codes are constructed using generator polynomials of degree $2t$. An RS (n,k) code can correct $t$ errors, where $t=\lfloor \frac{n-k}{2} \rfloor$. The RS codes (31,26) can, therefore, correct two errors. Hamming (15,11) provides a code rate of 0.733, compared to 0.8387 for RS (31,26).

\subsection{MAC Layer for Micro-Scale Design}\label{subsec:mac_layer_design}
The probability of failure of micro-scale sensors warrants the deployment of a large number to capture readings that can be averaged to obtain more accurate and realistic measurements. MAC layer protocols are very well advanced and widely deployed, but their implementation in micro-scale needs to be investigated and analyzed. In this section, we evaluate lightweight MAC schemes, identify their implementation requirements, and investigate the feasibility of their implementation in micro-scale.

The particular scheme utilized depends on factors such as the complexity of nodes, performance requirements, and the network structure.

Due to the power and complexity restrictions at the mote, we consider three MAC schemes as candidates for implementation at the mote, including two dynamic protocols and one static scheme. The three candidates are evaluated for simplicity and efficiency, and two are selected for simulation and analysis.  The schemes considered are binary tree protocol, slotted ALOHA, and CDMA, each of which has specific design requirements. Table \ref{tb:mac_implementation} summarizes the required components in each scheme and provides evidence of their implementation in micro-scale in the literature.
As can be noted, we ruled out TDMA and FDMA due to the additional complexity imposed on mote's circuitry. FDMA requires implementation of an oscillator and other circuitry on the mote to generate the sub-carrier frequency \cite{bletsas2009anti}. TDMA requires a network controller to assign unique time slots to different motes, via extra messages exchanged between the motes and the reader  \cite{das2014performance}.

\renewcommand{\arraystretch}{1.6}
\begin{table} [t]
\small
\centering
\caption{Requirements and Evidence of Feasibility of Implementation of Considered MAC Schemes. }
\label{tb:mac_implementation}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{1}{|p{1em}|}{ Scheme} & { Requirements} & \multicolumn{1}{p{14em}|}{  Implementation in Micro-Scale}\\ \hline

Binary Trees &  \makecell{Unique Address\\ Synchronization \\ Internal Clocks}  &  \makecell{Shift Registers \cite{yang2012product} \\ J-K Flip-Flop Synchronization Circuit \cite{salles2017dissipated} \\ Ferromagnetic
Cladding \cite{zhang2014low}}\\ \hline

Slotted ALOHA & \makecell{Unique Address\\ Synchronization \\ Internal Clocks \\ Random Number Generators}     &  \makecell{Shift Registers \cite{yang2012product} \\J-K Flip-Flop Synchronization Circuit  \cite{salles2017dissipated} \\Ferromagnetic
Cladding \cite{zhang2014low}\\ Feedback Shift Registers \cite{Datta2017}}   \\ \hline

CDMA &  \makecell{Spreading Codes \\ Synchronization \\ Internal Clocks \\ Chipset and Data Multiplier}       &   \makecell{Pre-Generated and Stored on Shift Registers \cite{yang2012product}  \\J-K Flip-Flop Synchronization Circuit  \cite{salles2017dissipated} \\Ferromagnetic
Cladding \cite{zhang2014low}\\  XOR Gates \cite{bharti2017implementation}}       \\

\hline
\end{tabular}
\end{table}

The binary tree protocol is used to select one mote from those in the interrogation zone of the reader. This is done by the reader sending commands and narrowing it down to a particular mote. The average number of iterations required to select a single mote from $N$ motes is given as
\begin{equation}
L(N)=\frac{\log{(N)}}{\log{2}}+1.
\end{equation}
Each mote is given a unique address and is required to synchronize its response to identification commands with all other motes. Synchronization among sensors has been tackled in a number of ways in the literature. The scheme used depends on the desired precision, duration of synchronization, area of sensor network, whether all or just portions of nodes need to be synchronized, energy, and infrastructure constraints in achieving the synchronization scheme \cite{Cox2005time}. In our design, we utilize the unidirectional scheme, where the reader sends a syncing message to all motes after powering. This resets and synchronizes the individual clocks of the motes. An appropriate sequence detection circuit using J-K flip-flops has been designed in micro-scale in \cite{salles2017dissipated}. The high number of exchanges of command messages required to select a mote makes this scheme less efficient than the other two schemes for our design. Therefore, it is not included in the simulation results presented in the next section.

A simple MAC scheme is slotted ALOHA. This scheme is reader driven and stochastic in scheduling the reception of packets from motes. It utilizes a randomly generated wait time in the cyclic sending of data, which ensures a fair probability that more than one mote can successfully transfer readings without collision.

Implementation of the slotted ALOHA scheme requires time synchronization in all motes and  random number generators. In the literature, a couple of suitable lightweight techniques have been proposed to generate pseudo-random numbers \cite{Luby1996}. We propose to use a linear feedback shift register (LFSR)-based circuit because it provides high-speed binary sequences and can be miniaturized \cite{Datta2017}. The authors of \cite{mandal2016} report implementation of a pseudo-random number generator based on a nonlinear feedback shift register using a micro-scale CMOS process.

Another option we consider is CDMA, which involves multiplying the data with orthogonal spreading codes before modulation and transmission. The receiver is able to separate and decode data from each sensor by correlating the received signal with the code of all sensors sequentially. Implementation requires the synchronization of transmission times from all sensors because non-synchronization results in multi-access interference \cite{benkic2007proposed}. The problem of good cross correlation between the spreading codes to prevent primary collision is limited in our application because the number of motes contending for access at a point in time is limited. For implementation in micro-scale, XOR gates can be used to multiply the spreading code with the sensed data, and the static spreading codes are assigned to the motes during the design stage and stored using registers. Implementation of XOR gates in micro-scale has been demonstrated in \cite{bharti2017implementation}.

\section{Simulation Results}\label{sec:Results-and-Discussion}
To bring clarity and make concrete sense of the proposed design for both physical layer and MAC layers, we set up numerical simulations for several realistic scenarios. Through physical-layer evaluation, we derive BERs corresponding to error-correction coding techniques described in section \ref{subsec:physical_layer_design} for various communication ranges between the reader and biomotes. Taking into account the results obtained in the physical-layer analysis, particularly the communication range, we evaluate the MAC protocols described in section \ref{subsec:mac_layer_design}. The analysis provides useful insights to questions such as: What read-time is required for a given data rate and number of deployed motes at a specific location of interest? What data rate should be employed at the mote for a desired read duration and a total number of motes deployed? From simulation results, design parameters and utilization specifications can be recommended to answer these questions for different scenarios.

\subsection{Physical-Layer Simulation Setup}\label{sec:sim-setup}
The focus of the physical-layer analysis is on determining the maximum distance between the mote and the reader for which communication can be achieved. The magnetic induction-based model is simulated using the design parameters shown in Table \ref{tb:parameters_sim}.
In this design, we assume that noise power is the summation of thermal noise and noise figure. Thermal noise is expected to be around $-120$ dBm for a bandwidth of $200$ KHz and temperature of $290^{\circ}$ \cite{wiki_noise}. Also, the noise figure, which is added by electronic circuits is expected to be $15$ dB or less \cite{Noise_Fig}. Taking the worst case, we assume $-105$ dBm as total noise at the reader. We also assume that the core of coils are filled with air, which implies $\mu = 1$.
The power induced in the external reader is evaluated for various separation distances. We simulate the BER achieved using ASK and BPSK for three conditions each: without error-correction coding, with Hamming (15,11) code, and with RS (31,26) code.
 \renewcommand{\arraystretch}{1}
\begin{table}
\centering
\caption{Simulation Parameters for Physical-Layer Analysis.}
\label{tb:parameters_sim}
\begin{tabular}{|c|c|}
\hline
 Parameters & Value \\ \hline
 External Coil Radius & $5$ cm \\
Implant Coil Radius & $50$  $\mu$m \\
Noise Power &  $-105$ dBm \\
Carrier Frequency & $13.56$  MHz \\
Permeability & $1$ \\
\hline
\end{tabular}
\end{table}

\subsection{Physical-Layer Simulation Results}\label{sec:sim-setup}
Fig. \ref{fig:power} shows the magnitude of backscattered power induced in the external reader with respect to the distance between the two devices.  As the distance increases above $6$ cm, received power falls below $-100$ dBm, making the signal detection difficult. As a result, given the design parameters of Table \ref{tb:parameters_sim}, the effective communication range would be around 6 cm.

\begin{figure}
\centering
{\includegraphics[width =4.8 in , height=2.8 in]{Figs/Power}}
\caption{ Backscattered induced power in external reader from biomote as a function of separating distance between two devices.}
\label{fig:power}
\end{figure}

Fig. \ref{fig:codings} depicts system performance in terms of BER for ASK, BPSK, BPSK alongside the Hamming code, and BPSK alongside the RS code. It can be observed that the BER for distances above $6$ cm reaches above $0.01$ in all cases.
In our application, given the short packet length (see Section \ref{sec:sim-setup}) and large number of motes deployed, it is safe to assume that a BER of about $10^{-3}$ would be acceptable. According to the figure, this BER is achievable for distances between $5$ to $6$ cm.
When comparing the performance with respect to both modulation and error-correction coding, BPSK along with the RS code performs the best. In general, various implants may require different BERs, depending upon data rate and the format of data transmitted. Once the required BER is known, the respective combination of modulation and error coding can be selected according to this figure.

\begin{figure}
\centering
{\includegraphics[width =4.8 in , height=2.8 in]{Figs/Codings}}
\caption{ Performance of using error-correction coding in the system: bit error rate (BER) versus various separating distances between reader and biomote.}
\label{fig:codings}
\end{figure}

\subsection{MAC Scheme Simulation Setup}\label{sec:sim-setup}

The main focus of our analysis for slotted ALOHA is to address the question of how long it would take the reader to obtain readings from all motes in its interrogation zone, and also to address the concern of what transmission rate to deploy at the motes. The three parameters of interest in our investigation are the time duration to obtain readings from all motes, transmission data rate of the motes, and number of motes contending for access at a particular location. These three parameters are henceforth referred to as $Read-time$, $Rate$, and $Number\ of \ Motes$, respectively. Two scenarios are considered in evaluating the performance of slotted ALOHA. Scenario 1 corresponds to a global deployment of the motes over the entire human body, and Scenario 2 to a local deployment of motes at only one region of interest. Simulations are carried out for packet lengths of $8$ and $64$ bytes.

In Scenario 1, the $Number\ of \ Motes$ at a particular location is not constant but rather a function of the total number of motes globally deployed, the volume of the human body, and the area of the interrogation zone of the reader. As such, for the $Number\ of \ Motes$ increasing in steps of $10$, we evaluate the $Read-time$ required to read all motes at various $Rates$. The interest here is to recommend the $Read-time$ required for the desired $Rate$, if the total number of motes deployed globally is known. For this analysis, we use the average volume of the human body and the volume of the interrogation zone of the reader. The volume of the interrogation zone is determined using a maximum communication range of $5$ cm which is recommended by our physical layer analysis. In Scenario 2, the $Number\ of\ Motes$ is fixed and is equal to the number of motes locally deployed. In this case, we set the $Read-time$ to values between $2$ and $10$ seconds in steps of $2$ seconds, and evaluate the $Number\ of \ Motes$ with successful transmissions. Our interest here is to recommend the number of motes to be deployed locally for various values of $Rate$ and $Read-time$.

In our simulation of the slotted ALOHA, we assume that each mote would have one data packet for transmission. It is also assumed that the reader is capable of processing all received packets during one slot duration. As a result, no queues are formed at either the mote or the reader. Our analysis do not consider the time taken to receive packet acknowledgments, and it is assumed that packet failures are due to collisions as a result of multiple transmissions on a slot. For both scenarios, we ran $100$ simulations to obtain the average number of successful motes out of the $Number\ of \ Motes$.

The focus of our analysis for CDMA is to determine how many motes can successfully communicate with the reader in a reading session. We evaluate this by randomly assigning static spreading codes of lengths $16$, $32$, $64$, $128$, and $256$ to the motes, and uniformly sampling from the pool of motes. Our analysis is based on the assumption of equal transmission energy for motes and synchronization of the start time of transmissions. Also, we only consider multiple access interference due to data transmissions of other motes.

In addition to the above, we present a performance comparison of the two MAC schemes for two read durations: short and long. The short read duration and the long read duration are arbitrarily set to $128$ slots and $128 \times 10$ slots, respectively. For the simulation, packet length is set to 64 bytes and transmission rate to 20 kbps, resulting in a short read duration of $3.28$ seconds and a long read duration of $32.8$ seconds.

\subsection{Results of MAC Layer Analysis }\label{sec:sim-setup}
Results of the Scenario 1 analysis are shown in Fig. \ref {fig:scenario_1}. For $Rates$ varying from $1$ to $600$ kbps, we obtain the highest number of contending motes that all achieve successful transmissions in specific $Read-times$. This was done for data packet lengths of 8 and 64 bytes. From this, we can infer what combinations of $Read-time$, $Rate$, and $Number\ of \ Motes$ are feasible. For instance, for a mote operating at $200$ kbps, at a $Read-time$ of $10$ seconds and a packet length of 64 bytes, $91$ motes can be successfully read in the interrogation zone. Therefore, assuming an interrogation zone of $5$ cm radius and average volume of the human body as $6.643\times 10^5\ cm^3$,
\begin{figure}[t]
\centering
{\includegraphics[width =5.4 in , height=3.7 in]{Images/mfig_scenerio_1_combined2}}
\caption{Transmission rates to achieve successful transmission from all motes for various numbers of contending motes in specific read-times.}
\label{fig:scenario_1}
\end{figure}
\begin{figure} [H]
\centering
{\includegraphics[width =5.4 in , height=3.7 in]{Images/mfig_scenerio_2_combined}}
\caption{Recommended number of motes to locally deploy for various rates and read-times.}
\label{fig:scenario_2}
\end{figure}
 \noindent the recommended $Number\ of \ Motes$ to be deployed globally in the human body would be $230,906$. Similar deductions can be made for a data-packet length of 8 bytes. The packet length utilized depends on the application requirement. For Scenario 2, the results are shown in Fig. \ref {fig:scenario_2}. From these results, the optimum number of motes for local deployment can be recommended for any choice of $Rate$ and $Read-time$. For example, for a mote operating at a rate of $200$ kbps with 64-byte data packets, an optimum number of $130$ motes can be deployed for a desired read duration of $20$ seconds.

Results of the CDMA analysis are shown in Fig. \ref{fig:cdma_throughput}. As can be seen, there is a positive correlation between the number of successful motes and the length of codes. It was observed that for every length of codes, the number of successful motes rises to a peak and then drops as the number of motes contending for access increases beyond a particular point.
\begin{figure}[t]
\centering
{\includegraphics[width =3.5 in , height=2.34 in]{Images/cdma_plot}}
\vspace{-0.1 in}
\caption{Number of successful transmissions for various number of motes using static CDMA codes of length C.}
\label{fig:cdma_throughput}
\end{figure}

Figs. \ref{fig:aloha_vs_cdma} and \ref{fig:aloha_vs_cdma2} show results of the comparison of the two MAC schemes. In  Fig. \ref{fig:aloha_vs_cdma}, we evaluated the performance for a short-read time set to $128$ slots for the slotted ALOHA and spreading code length of $128$ for the CDMA scheme. The spread signal from a code length of $128$ will take the same transmit duration as $128$ slots in the ALOHA. Results show the superior performance of CDMA for all numbers of motes beyond $20$, with a decline in performance at $120$ motes. This is due to ALOHA's low utilization efficiency of the $128$ available slots, as most slots are not selected in the random back-off process and remain empty. For long-read times, the analysis in Fig. \ref{fig:aloha_vs_cdma2} shows a superior performance of the slotted ALOHA scheme for number of deployed motes up to $50$, beyond which performance begins to oscillate around that of the CDMA. For a much longer read duration, by either increasing the communication rate or the number of available slots, the ALOHA scheme will read all the deployed motes. The increase in duration has no impact on the CDMA performance. We can infer from the results that for implantable medical device applications that require a short-read time, CDMA will be a better choice but at the expense of implementing more complex procedures in micro-scale.  Slotted ALOHA can be used in applications where long-read durations can be tolerated.

\begin{figure}[t]
\centering
{\includegraphics[width =3.5 in , height=2.34 in]{Images/cdma_vs_aloha1}}
\vspace{-0.1 in}
\caption{Comparison of successful transmissions for CDMA and Slotted ALOHA for short-read durations, D = $128$ slots, data rate is $20$ kbps and packet length is $64$ bytes.}
\label{fig:aloha_vs_cdma}
\end{figure}
\begin{figure}[t]
\centering
{\includegraphics[width =3.5 in , height=2.34 in]{Images/cdma_vs_aloha2b}}
\vspace{-0.1 in}
\caption{Comparison of successful transmissions for CDMA and Slotted ALOHA for long-read durations D is $128 \times 10$ slots, data rate is $20$ kbps and packet length is $64$ bytes.}
\label{fig:aloha_vs_cdma2}
\end{figure}

\section{Conclusion}\label{sec:Conclusion}
In this work, we first established the major challenges of implementing the existing wireless communication technologies in micro-scale implantable medical devices which we referred to as ``biomotes''. To overcome these challenges, we proposed the use of magnetic induction-based backscatter communication. First, we demonstrated that communication via magnetic induction can be established between a micro-scale IMD and a handheld device as an external reader. To increase the communication range, we adapted suitable low-power modulation and error-correction coding schemes at the physical layer. We also investigated the feasibility of implementing these schemes in micro-scale. To increase the reliability and accuracy of measurements via mass deployment, we proposed suitable low-power MAC schemes and investigated the feasibility of their implementation in micro-scale. Assuming reasonable design parameters and the human body as an AWGN channel, performance of the proposed biomote was analyzed. For a BER of $10^{-3}$ both with and without error-correction coding, we obtained communication ranges of between $5$ and $6$ cm for BPSK and ASK modulations. Results obtained from our analysis of the MAC schemes can be used as guidelines for selecting mote design parameters such as data rate, as well as mote utilization specifications such as read duration required and optimum number of motes to be deployed. While mass deployment of such IMDs can increase reliability, MAC schemes with simple complexity must be incorporated. In summary, it was found that magnetic induction is a formidable candidate for communication between micro-scale IMDs and external readers such as NFC-enabled handheld devices.

\bibliographystyle{ieeetran}
\bibliography{Ref_new}

\IEEEpeerreviewmaketitle

\end{document}


TITLE: Solving recurrence relation of form $T(n/2 + c)$
QUESTION [7 upvotes]: It is obvious that the Master Theorem cannot be applied to the recurrences of the following form:
$T(n) = 4T(n/2 + 2) + n$
Since I am only interested in the $\theta$ bound of the recurrence and not the exact solution, what is the best way to approach this problem?

REPLY [1 votes]: A different approach. Try the recursion tree method (consult CLRS)
$ T(n)=T(n/2+2)+n$
Using the tree we get, at level $i$, the sum as
$4^i c(n/2^i)+ 2*4^i $ stopping at $T(3)$ (assuming it to be a constant value).
It stops when $n=2^i$ and hence $i=\log n$ , Therefore summing the equation from $i=0$ to $i=\log n$ we get
$(2^{\log n} - 1) + (2^{2\log n}-1)/3 $ , which gives $\theta(n^2)$.


TITLE: Taylor remainder in integral form
QUESTION [2 upvotes]: Let f be infinitely differentiable function on $\mathbb{R}$ and let
  $x_0 \in \mathbb{R}$.
We can write the function $f(x)$ as
$$f(x)=f(x_0)+\int_{x_0}^x{f'(t)dt}$$  or
  $$f(x)=f(x_0)-\int_{x_0}^x{f'(t)d(x-t)}$$
With partial integration we get
$$f(x)=f(x_0)+f'(x_0)(x-x_0)-\int_{x_0}^{x}{f''(t)\cdot t \ dt}$$
And with induction it can be proved that
$$f(x)=f(x_0)+\frac{f'(x_0)}{1!}(x-x_0)+\cdots
 +\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_{n+1}$$ where $$R_{n+1}=-\frac{1}{n!}\cdot \int_{x_0}^x{f^{(n+1)}(t)\cdot t^ndt}$$

The first line is pretty clear to me. However I fail to see how the second equality is equivalent to the first. This $d(x-t)$ confuses me a lot. I also know that we choose $f'(t)=u$ so $f''(t)dt=du$ however not sure what we are choosing as $dv$. Any help is appreciated.

REPLY [1 votes]: There are some errors in the second and third equations, so it is understandable how you are confused.
Here is what is going on starting from the first equation $$f(x)=f(x_0)+\int_{x_0}^x{f'(t)dt}.$$ We integrate by parts using $u=f'(t)$ and $v=x-t$, so $dv=-dt$.  We thus have
\begin{align*}
\int_{x_0}^x{f'(t)dt} &=-\int_{x_0}^x f'(t)(-dt) \\
&=-(f'(t)(x-t))\Big|_{x_0}^x+\int_{x_0}^xf''(t)(x-t)dt \\
&=f'(x_0)(x-x_0)+\int_{x_0}^xf''(t)(x-t)dt.
\end{align*}
Plugging this back into the first equation we have $$f(x)=f(x_0)+f'(x_0)(x-x_0)+\int_{x_0}^xf''(x)(x-t)dt.$$ This is almost what the (erroneous) third equation says, but with $x-t$ instead of $-t$ in the integrand.
(Looking back on this, you can see the second equation as an attempt to rewrite the integral in the form $\int udv$ with $u=f'(t)$ and $v=x-t$.  However, it is incorrect, since if you rewrite the integral with $d(x-t)$, you must also change the bounds of integration to be in terms of $x-t$ instead of in terms of $t$.)


TITLE: Ruzsa-type inequalities for additive energy
QUESTION [4 upvotes]: As the subject says, I have some questions about some Ruzsa-type inequalities for additive-energy. It would be wonderful if anyone could shed some light.
First, the definition: let $E(A,B)$ be the number of all quadruples $(a,a',b,b') \in A \times A \times B \times B$ such that $a+b = a' + b'$ denote the additive energy of the sets $A$, $B$, and let $F(A,B)= \frac{|A|^{2}|B|^{2}}{E(A,B)}$.
Now let $A, B, C \subset G$ be subsets of an additive group $G$ so that $|A|=|B|=|C|=N$. Do the following inequalities hold?
1) If $F(A,B), F(A,C) \leq  K\cdot N$, then $\min{(F(A, B+C), F(B, C+A), F(C, A+B))} \leq K^{c} N$, for some constant $c$.
2) If $F(A,A) \leq K\cdot N$, then for all non-negative integers $k,l$ there's a constant $c$ depending on them such that $F(k \cdot A, l \cdot A) \leq K^{c} N$.

REPLY [5 votes]: 1) No. Let $A=B=C$ be a set that is a union of interval $\{1,\dots,N\}$ and $N$ random elements from $\{1,\dotsc,N^2\}$. Then $F(A,A)=KN$ for some constant $K$. On the other hand, $A+A$ is basically the interval $\{1,\dotsc,N^2\}$. So, $F(A,A+A)\approx N^2$.
2) Example above show that it fails for $k=1$ and $l=2$ (from the context I assume that $k\cdot A$ means $k$-fold sumset $A+\dotsb+A$, not the $k$-dilate $\{ka:a\in A\}$. If  dilates were meant, then the assertion is true, and one can deduce this from the Balog–Szemerédi–Gowers theorem).
I want to add that there do exist Ruzsa-type inequalities for additive energy. Instead of sumsets, they involve a suitable extension of additive energy to more than two sets. See Razborov's paper on the product theorem in the free group (in section 6), for example.


TITLE: max and minimum qudratic function problem
QUESTION [1 upvotes]: A piece of wire $20$ metres long is cut into $2$ pieces and each piece is bent to form a square. Determine the length of the two pieces so that the sum of the areas of the two squares is a minimum.
We have to solve it using the vertex method. however i dont know where to begin with. i dont know how to setup the equation. please help. the answer is $10$ metres each.

REPLY [0 votes]: Hint: Let $x$, and $20-x$ be the length of the $2$ pieces of wire. The sum of areas of the $2$ squares is: $\dfrac{x^2}{16} + \dfrac{(20-x)^2}{16} = f(x) $. Can you simplify it to a quadratic function and use the "vertex" technique?


TITLE: How to denote a set of exponents for a polynomial expression?
QUESTION [0 upvotes]: I'm finding it difficult to use proper set notation and I need help making the notation more simplified and readable.
What I'm trying to do
I am trying to define a $d$-order polynomial function $f^d=f^d(\alpha, \beta; \theta)$, where $\alpha$ and $\beta$ are the two dimensions of the function and $\theta$ is a vector of coefficients. What I find challenging is defining the structure of the polynomial depending on the order $d$. I need the notation to resolve to:

$f^1(\alpha, \beta; \theta) = \theta_0 + \theta_1 \alpha + \theta_2 \beta$
$f^2(\alpha, \beta; \theta) = \theta_0 + \theta_1 \alpha + \theta_2 \beta + \theta_3 \alpha \beta+ \theta_4 \alpha^2 + \theta_5 \beta^2$
$\vdots$
$f^d(\alpha, \beta; \theta)$ = ??

What I have so far
What I have come up with so far is the following:
Let $\mathcal{P}^d$ be the set of exponent tuples $(a, b)$, such that:
$$
\mathcal{P}^d = \left\{ (a, b) ~|~ a, b \in \{0,..., d\}, a + b \leq d \right\}
$$
Then,
$$
f^d(\alpha, \beta; \theta) = \sum_{i=0}^{|\mathcal{P^d}|} \theta_i \cdot \alpha^{a_i} \cdot\beta^{b_i} \quad \text{for each } (a_i, b_i) \in \mathcal{P}^d
$$
Where the coefficient vector is $\theta \in \mathbb{R}^{|\mathcal{P}^d|}$ and $(a_i, b_i)$ is the exponent tuple of the $i$th term.
Even though it sort-of works, I find this notation somewhat cumbersome and hard to understand.
I checked if it works for $d=1, 2$. For example:

$\mathcal{P}^1 = \{(0, 0), (0, 1), (1, 0)\}$ and therefore $f^1(\alpha, \beta; \theta) = \theta_0 \alpha^0 \beta^0 + \theta_1 \alpha^1 \beta^0 + \theta_2 \alpha^0 \beta^1$
$\mathcal{P}^2 = \{(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (0, 2)\}$

My questions

How do I simplify the definition of $f^d$ in terms of notation?
What is a standard way to write this kind of polynomial?
Is there a way I can omit having to define $\mathcal{P}^d$?

REPLY [0 votes]: Why not use double indices? $$f^d(\alpha,\beta; \theta) = \sum_{i=0}^d \sum_{j=0}^{d-i} \theta_{i,j} \alpha^i \beta^j $$


TITLE: Why is reflected light polarised?
QUESTION [23 upvotes]: Why is reflected light polarised?
I have learnt about Brewster's angle, and how at a particular angle all light reflected is polarised, but do not understand why. Is this something that could be explained to a guy that doesn't have a Ph.D in physics?

REPLY [0 votes]: A reflection of light is caused by a wave front inducing an oscillation in a charged particle which then causes a new wavefront to form. In a reflective surface, the valence electrons are the charged particles that absorb those incident wavefronts. Atomic electrons have more freedom to move parallel to the material’s surface, especially if they are electrons in the conductive band of a metal like silver.
For the electron to move perpendicular to the surface of the material, the electron would have to move towards and away from the atomic nucleus. This movement is restricted to particular quanta determined by the electron orbitals the electron can transition into and out of.
So, waves vibrating parallel with the surface of the material can induce continuous movement in the electrons of the material’s surface while waves perpendicular is limited to electron shell configurations.


TITLE: Number of inversions from the inversion table
QUESTION [0 upvotes]: In Stanley's "Enumerative Combinatorics", he claims in the proof of colloray 1.3.13 that "If $I(w) = (a_1,...,a_n)$, then $inv(w) = a_1+...+a_n$. I don't really see why this is true, could anyone explain this to me?

REPLY [0 votes]: It follows almost immediately from the observation made just after the example in which Stanley explains $I(w)$:

Clearly $a_i$ is the number of entries $j$ of $w$ to the left of $i$ satisfying $j>i$.

In other words, $a_i$ is the number of pairs $\langle j,i\rangle$ of elements of $w$ such that $j$ is to the left of $i$ and $j>i$. Those pairs are precisely the inversions of $w$ having $i$ as their second element. Each inversion of $w$ has exactly one $i\in[n]$ as its second element. Thus, $a_1+a_2$ is the number of inversions of $w$ having $1$ or $2$ as second element, $a_1+a_2+a_3$ is the number having $1$ or $2$ or $3$ as second element, and so on. In particular, we can sum over all possible second elements to find that
$$\operatorname{inv}(w)=\sum_{k=1}^na_k\;.$$
The observation that I highlighted is a direct consequence of the definition of $I(w)$. We insert elements of $[n]$ into the table in descending order. When we insert $k$ into the string, the $n-k$ larger members of $[n]$ have already been inserted, and we place $k$ so that $a_k$ of them are to its left. The remaining numbers to be added to the string are all smaller than $k$, so those $a_k$ numbers are the only numbers larger than $k$ that end up on the left of $k$. Thus, $a_k$ is indeed the number of entries $j$ to the left of $k$ that are bigger than $k$, and hence the number of inversions having $k$ as second element.


text:
\begin{document}
\begin{abstract}
We give concrete DG-descriptions of certain stable categories
of maximal Cohen-Macaulay modules. This makes in possible to describe the latter as generalized cluster categories in some cases.
\end{abstract}

\maketitle
\section{Introduction}
Throughout $k$ is a field.  Let $(R,m)$ be a local complete noetherian
Gorenstein $k$-algebra of Krull dimension $n$ with an isolated
singularity and with $R/m\cong k$. Then it is well-known that the
stable category of Cohen-Macaulay $R$-modules $\underline{\MCM}(R)$ is
an $n-1$-Calabi-Yau category. This category is also sometimes called
the singularity category of $R$.

Assume given a Cohen-Macaulay $R$-module $N$ such that
$\Lambda=\End_R(R\oplus N)$ has finite global dimension and is a Cohen-Macaulay $R$-module. Thus
$\Lambda$ is a non-commutative crepant resolution of $R$ in the sense
of \cite{VdB32}. Under these conditions Iyama has shown that $N$ is an
$n-1$-cluster tilting object in $\underline{\MCM}(R)$
\cite[Thm 5.2.1]{iyama} and it is a natural question if $\underline{\MCM}(R)$ may
be obtained by one of the standard constructions of CY-categories with
cluster tilting object \cite{Amiot,Guo}.

\medskip

Assume for simplicity that $N$ contains no repeated
summands and no summands isomorphic to $R$. Let $(S_i)_{i=0,\ldots,l}$
be the simple $\Lambda$-modules with~$S_0$ corresponding to the summand
$R$ of $R\oplus N$. Let $e_0$ the idempotent given by the
projection $R\oplus N\r R$. Put $l=\Lambda/\rad\Lambda$ and $l^0=le_0$.

In this note we observe the following (Lemma \ref{ref-4.1-3}, Theorem \ref{ref-5.1.1-5}, Remark
\ref{ref-5.1.2-6})
\begin{theorem}
\label{ref-1.1-0}
Let $(T_lV,d)\r \Lambda$ be a finite minimal model for $\Lambda$ (see
\S\ref{secpreliminaries}).

Put $\Gamma=T_lV/T_lV e_0T_lV$. Then one has
\[
\underline{\MCM}(R)\cong \Perf(\Gamma)/\langle (S_i)_{i\neq 0}\rangle
\]
and furthermore $\Gamma$ has the following properties:
\begin{enumerate}
\item $\Gamma$ has finite dimensional cohomology in each degree;
\item $\Gamma$ is
concentrated in degrees $\le 0$;
\item $H^0(\Gamma)=\Lambda/\Lambda e_0\Lambda$;
\item
As a graded algebra $\Gamma$ is of the form
$T_{l^0} V^0$ for $V^0=(1-e_0)V(1-e_0)$.
\end{enumerate}
\end{theorem}
The miminal model $(T_lV,d)$ always exists for abstract reasons (see Lemma \ref{ref-4.1-3} below)
but to use Theorem~\ref{ref-1.1-0} effectively one must be able to
describe it. There are at least two cases where this is easy:
\begin{itemize}
\item $\Lambda$ is $3$-Calabi-Yau. It then follows from \cite{VdBsuper} that the minimal
model of $\Lambda$ is derived from a super potential.
\item $\Lambda$ is Koszul.
\end{itemize}

We obtain in particular (see Proposition \ref{ref-5.2.1-16} below)
\begin{proposition} \
\label{ref-1.2-1} Assume that $\Lambda$ is 3-Calabi Yau.

Then
$\underline{\MCM}(R)$ is the generalized cluster category associated
to a quiver with super potential as introduced by Claire Amiot in \cite{Amiot}.
\end{proposition}
The Koszul case is well taylored to quotient singularities.
In \S\ref{ref-6.4-23} we consider the case where
$R=k[[x_1,\ldots,x_n]]^G$ for $G\cong \ZZ/m\ZZ$ acting linearly
(Proposition \ref{ref-6.5.1-26}) with weights $(\xi^{a_i})_i$
for $\xi$ a primitive $m$'th root of unity and $0\le a_i\le m-1$, $\gcd(a_i,m)=1$, $\sum_i a_i\cong 0$ mod $m$. We
given an explicit description of $\Gamma$ in this case.

As an application (Proposition \ref{ref-6.6.1-28} below) of this
explicit description of $\Gamma$ we obtain a new proof of the following result from
\cite{AIR,iyama2}
\begin{proposition}
\label{ref-1.3-2}
Assume $\sum_i a_i=m$.
  Let $P$ be the quiver with vertices $[m-1]\overset{\text{def}}{=}\{1,\ldots,m-1\}$ and for
  each $j\in [m-1]$ and $i\in [n]$ such that $j+a_i\in [m-1]$ an arrow
  $x_i:j\r j+a_i$ with relations $x_ix_{i'}=x_{i'}x_i$. Let $C$ be the
  path algebra of~$P$ modulo these relations. Let
  $\Theta_C=\RHom_{C^e}(C,C\otimes C)$ be the inverse dualizing
  complex of~$C$ \cite{Keller11,VdB29}. Then there is a quasi-isomorphism of DG-algebras
\[
\Gamma\cong T_C(\Theta_{C}[n-1])
\]
In particular $
\underline{\MCM}(R)
$
is a generalized $n-1$-cluster category.
\end{proposition}
\section{Acknowledgement}
As said Proposition \ref{ref-1.3-2} was proved independently in
\cite{AIR} (see also \cite{iyama2}).  Some time ago the authors had been looking at explicit
DG-models for certain stable categories of maximal Cohen-Macaulay
models (based on Theorem \ref{ref-1.1-0}). We knew that Proposition
\ref{ref-1.3-2} was true in the 3-dimensional case (as then it is
a consequence of Proposition \ref{ref-1.2-1}) and expected a
suitable generalization to hold in higher dimension as well. However
we became distracted by other interests.

In May 2010 the authors learned about the precise statement of Proposition
\ref{ref-1.3-2} from a very interesting lecture by Osamu Iyama at the OberWolfach
meeting ``Interactions between Algebraic Geometry and Noncommutative
Algebra'' (see \cite{iyama2}). In that lecture the result was derived from
a very general statement about graded Calabi-Yau algebras of Gorenstein parameter 1.

We expected the result to be a consequence of Theorem
\ref{ref-1.1-0} as well and this is indeed the case although the
derivation is a little more involved than we anticipated. Nonetheless since the methods
in \cite{AIR} appear to be quite different from ours we decided it would
be useful to write down our own proof.

We are very grateful to Dong Yang for his careful reading of the first
version of this manuscript. His comments have helped us to improve the exposition.
Dong Yang has also informed us that he and Martin Kalck have a different approach to some of
our results based on ``recollement''.
\section{Notation and conventions}
Throughout $l$ is a separable algebra over the ground field $k$. If we
refer to an ``algebra'' $\Gamma$ then we mean an $l$-algebra. In other
words $\Gamma$ is implicitly equipped with a ring homomorphism $l\r
\Gamma$. Unadorned tensor products are over $k$.
\section{Preliminaries}
\label{secpreliminaries}
In this paper we deal with two settings. The ``complete'' case and the
``graded'' case. This mainly affects our definition of a tensor
algebra. Let $V$ be an $l$-bimodule and denote by $T^\circ_lV$ the
ordinary tensor algebra of $V$. In the complete case $T_lV$ is the
completion of $T_l^\circ V$ at the twosided ideal $(T^\circ_lV)_+$
generated by $V$. If $V$ carries an additional $\ZZ$-grading (in a homological sense) then $T_l V$ refers to the graded
completion of $T^\circ_lV$ at $(T^\circ_lV)_+$. In the graded case $V$
will be equipped with an \emph{additional} (non-homological) grading which we sometimes
refer to as the ``Adams grading'' (following \cite{LPWZ}).  In this case
$T_lV$ is simply $T_l^\circ V$ equipped with the extended Adams
grading.
\begin{itemize}
\item In the complete case we deal with (DG-)algebras which can be
  written as of $T_lV/I$ with $V$ a finitely  generated (graded)
  $l$-bimodule and $I$ a (graded) closed ideal in $T_lV$.
\item In the graded case we deal with graded (DG-)algebras which can be
  written as of $T_lV/I$ with $V$ a finitely generated
  (bi)graded $l$-bimodule and $I$ a (bi)graded ideal.
Unless otherwise specified the Adams grading will be left bounded in each
homological degree.
\end{itemize}
Below we will use finite minimal models for some
algebras.  For us a finite minimal model of an algebra $\Lambda$
will be a DG-algebra of the form $(T_lV,d)$ for a finitely generated
graded $l$-bimodule $V$ living in degrees $\le 0$ such that $dV$ is in the
twosided ideal generated by $V\otimes_l V$, together with a
quasi-isomorphism $T_lV\r\Lambda$ (with $\Lambda$ being viewed as a DG-algebra
concentrated in degree zero).
\begin{lemma}
\label{ref-4.1-3} Let $\Lambda$ be either complete of the from $l+\rad \Lambda$ or graded
of the form $\Lambda=l+\Lambda_1+\cdots$. Assume $\dim \sum_i \Tor^\Lambda_i(l,l)<\infty$. Then
$\Lambda$ has a finite minimal model with
\begin{equation}
\label{ref-4.1-4}
V=\bigoplus_{i\ge 1} \Tor^\Lambda_i(l,l)[i-1]
\end{equation}
Conversely if $\Lambda$ has a finite minimal model $T_lV$ then $V$ is given by the
formula \eqref{ref-4.1-4}.
\end{lemma}
\begin{proof} This follows from the bar-cobar formalism. In the graded
  case it has been proved explicitly in \cite{LPWZ} (see \S1.1 in
  loc.\ cit.). One checks that the proof also goes through in the
  complete case (see e.g.\ \cite[Prop. A.5.4]{VdBsuper}).
\end{proof}
For our examples we only need the case where $\Lambda$ is a Koszul algebra
or a completion thereof. In that case it is trivial to construct the minimal
model directly (see Proposition \ref{ref-6.1.1-18} and Remark \ref{ref-6.1.2-20} below).
\section{Stable categories of Cohen-Macaulay modules}
In this section we show how to obtain explicit models for some
stable categories of Cohen-Macaulay modules. In order
to have somewhat concise statements we intentionally do not
work in the greatest possible generality.
\subsection{General results}
In this section we assume  that $(R,m)$ is a complete local noetherian Gorenstein
$k$-algebra with an isolated singularity (by complete
  local we mean either literally complete local or else $\NN$-graded local and $R/m=k$). Let
  $(M_i)_{i=1,\ldots,l}$ be indecomposable finitely generated maximal
Cohen-Macaulay
  $R$-modules which are pairwise non-isomorphic and
also not isomorphic to $R$. Put $M_0=R$,
  $M=\bigoplus_i M_i$ and $\Lambda=\End_R(M)$. Assume that $\Lambda$ has
finite global dimension so that $\Lambda$ is a non-commutative crepant
resolution of $R$ in the sense of~\cite{VdB32}.

Let $e_i\in \Lambda$ be
  the idempotent given by the projection $M\r M_i$ and put $P_i=\Lambda e_i$.
 Let $S_i=P_i/\rad P_i$ be the
corresponding simple $\Lambda$-module. Put $l=\sum_i ke_i$.
\begin{theorems}
\label{ref-5.1.1-5}
 Let $T_lV$ be a finite minimal model of $\Lambda$ (cfr Lemma \ref{ref-4.1-3}). Let $\underline{\MCM}(R)$ be the stable
  category of maximal Cohen-Macaulay $R$-modules (graded if we are in
  the graded context).  Put $\Gamma=T_lV/T_lV e_0 T_lV$.
\begin{enumerate}
\item
 The $(S_i)_{i\neq 0}$ are perfect
  $\Gamma$-modules and furthermore there is an exact
  equivalence
\[
 \underline{\MCM}(R)=\Perf(\Gamma)/\langle (S_i)_{i\neq 0}\rangle
\]
\item The DG-algebra $\Gamma$ has finite dimensional
  cohomology in each degree. Furthermore $H^0(\Gamma)=\Lambda/\Lambda
  e_0\Lambda$.
\end{enumerate}
\end{theorems}
\begin{remarks} \label{ref-5.1.2-6} Put $V^0=(1-e_0)V(1-e_0)$ and
  $l^0=l/le_0$. Then it is not hard to see that
\[
T_lV/T_lV e_0 T_lV\cong T_{l^0}V^0
\]
\end{remarks}
\begin{proof}[Proof of Theorem \ref{ref-5.1.1-5}] We first prove (1).
According to Lemma \ref{ref-5.1.3-8}  below we have
 an equivalence
\[
D^b_f(\Lambda)/\langle (S_i)_{i\neq 0}\rangle\cong D^b_f(R):
\]
which sends $P_0$ to $R$.

Hence using Buchweitz's theorem \cite{BuchweitzAlone} we get
\begin{multline}
\label{ref-5.1-7}
\underline{\MCM}(R)=D^b_f(R)/\langle R\rangle=\biggl (D^b_f(\Lambda)/\langle (S_i)_{i\neq 0}
\biggr)/
\langle P_0\rangle\\
=D^b_f(\Lambda)/\langle P_0,(S_i)_{i\neq 0}\rangle
=\biggl(D^b_f(\Lambda)/\langle P_0\rangle\biggr)/\langle (S_i)_{i\neq 0}\rangle
\end{multline}
To obtain our conclusion it is now sufficient to prove
\[
D^b_f(\Lambda)/\langle P_0\rangle=\Perf(T_lV/T_lV e_0 T_lV)
\]
By hypotheses $\Lambda$ has finite global dimension and hence $D^b_f(\Lambda)=\Perf(\Lambda)
=\Perf(T_lV)$.
We may now conclude as in \cite[Lemma 7.2]{Keller11} (and proof).

\medskip

Since $H^i(\Gamma)=\Hom_{\Perf(\Gamma)}(\Gamma,\Gamma[i])$ and
$\Perf(\Gamma)\cong D^b_f(\Lambda)$ the second statement is an immediate consequence
of Proposition \ref{ref-5.1.4-11} below.
\end{proof}
\begin{lemmas}
\label{ref-5.1.3-8}
The functor
\begin{equation}
\label{ref-5.2-9}
\Xi:D^b_f(\Lambda)\r D^b_f(R):N\mapsto e_0N
\end{equation}
induces an equivalence
\[
D^b_f(\Lambda)/\langle (S_i)_{i\neq 0}\rangle\cong D^b_f(R):
\]
\end{lemmas}
\begin{proof}
  Let $U\in D^b_f(R)$. Since $P_0$ is a vector bundle on $\Spec R-\{m\}$
we have that $P_0\otimes_R U$ has finite dimensional cohomology.

Let $N$ be such that for $n\ge N$ we have $H^{-n}(U)=0$.  We claim
that for $n\ge N$ we have that $H^{-n}(P_0\Lotimes_R U)$ is an
extension of $(S_i)_{i\neq 0}$, i.e. $e_0 H^{-n}(P_0\Lotimes_R U)=0$.
Indeed
\begin{equation}
\label{ref-5.3-10}
e_0 H^{-n}(P_0\Lotimes_R U)=H^{-n}(e_0\Lambda e_0\Lotimes_R U)\cong
H^{-n}(R\Lotimes_R U)=H^{-n}(U)=0
\end{equation}
  Define $\Phi(U)=\tau_{\ge -N} ( P_0\Lotimes_R U)$.
Then $\overline{\Phi(U)}$ is a well defined
object of $D^b_f(\Lambda)/\langle (S_i)_{i\neq 0}\rangle$. We claim that
$\overline{\Phi(-)}$ yields a quasi-inverse to \eqref{ref-5.2-9}.

If $U\in D^b_f(R)$ then the computation \eqref{ref-5.3-10} shows that
$\Xi\overline{\Phi}(U)=U$. Conversely assume $V\in D^b_f(\Lambda)$. Then
$\overline{\Phi}\Xi(V)=\tau_{\ge -N}(P_0\Lotimes_R e_0 V)$. Let $C$ be the cone
of $P_0\Lotimes_R e_0 V=\Lambda e_0\Lotimes_R e_0 V\r V$.  We see $e_0C=0$.
In other words the cohomology of $C$ is given by extensions of $(S_i)_{i\neq 0}$.
Furthermore by our choice of $N$ we have $e_0H^{-n}(V)=H^{-n}(e_0V)=0$
for $n\ge N$ and hence $H^{-n}(V)$ is an also an extension
of $(S_i)_{i\neq 0}$ for such $n$.
Thus working modulo $\langle (S_i)_{i\neq 0}\rangle$ we have
\[
\tau_{\ge -N}(P_0\Lotimes_R e_0 V)=\tau_{\ge -N}V=V
\]
which finishes the proof.
\end{proof}
\begin{propositions}
\label{ref-5.1.4-11}
The category
$D^b_f(\Lambda)/\langle P_0\rangle$ is $\Hom$-finite and in addition
\begin{equation}
\label{ref-5.4-12}
\Hom_{D^b_f(\Lambda)/\langle P_0\rangle}(\Lambda,\Lambda)=\Lambda/\Lambda e_0\Lambda
\end{equation}
\end{propositions}
\begin{proof}
Since $\Lambda$ has finite global dimension to prove $\Hom$-finiteness
it is sufficient to prove for any $M\in D^b_f(\Lambda)$:
\begin{equation}
\label{ref-5.5-13}
\dim \Hom_{D^b_f(\Lambda)/\langle P_0\rangle}(\Lambda,M)<\infty
\end{equation}
If $N\in\mod(\Lambda)$ then there is a map
\begin{equation}
\label{phidef}
\phi:P_0^n\r N
\end{equation}
such that $\coker\phi\in \langle (S_i)_{i\neq 0}\rangle$.
Using $\phi$ we can ``resolve'' any $M\in D^b_f(\Lambda)$ with a complex
$P\in \langle P_0\rangle$ such that $\cone(P\r M)$ modulo $\langle
(S_i)_{i\neq 0}\rangle$ is an object $M_1$ in $\mod(\Lambda)[n]$ for
$n\gg 0$.

Hence to prove
\eqref{ref-5.5-13} we have
reduced ourselves to the cases $M\in \mod(\Lambda)[n]$ for $n\gg 0$ or $M=S_i[p]$ for
$i\neq 0$ and $p\in \ZZ$.

To deal with the case $M=S_i[p]$ let $N$ be an extension of
$(S_i)_{i\neq 0}$ in $\mod(A)$. Then $\Hom^i_{D^b_f(\Lambda)}(P_0,N)=0$
from which we easily deduce
\begin{equation}
\label{ref-5.6-14}
\Hom_{D^b_f(\Lambda)/\langle P_0\rangle}^i(\Lambda,N)
=
\begin{cases}
N &\text{if $i=0$}\\
0& \text{otherwise}
\end{cases}
\end{equation}
Thus this case is clear.

To deal with the other case it is sufficient to show the following statement.
Assume $M\in \mod(\Lambda)$ then
\begin{equation}
\label{ref-5.7-15}
\Hom^i_{D^b_f(\Lambda)/\langle P_0\rangle}(\Lambda,M)=0
\end{equation}
for $i> 0$.
Let $p$ be a map $\Lambda\r M[i]$ in $D^b_f(\Lambda)/\langle P_0\rangle$ with $i>0$. Then
$p$ is represented in $D^b_f(\Lambda)$ by a diagram of the following kind
\[
\xymatrix{
& C\ar[dr]^{p'}\ar[dl]_{q} &\\
\Lambda && M[i]
}
\]
such that $P\overset{\text{def}}{=}\cone q\in \langle P_0\rangle$. It
is easy to see that we may assume that this diagram is an actual
diagram of complexes and that in addition $C$ is a finite complex of
finitely generated projectives. Then it follows that we may also
assume that $P$ is a finite complex of finite direct sums of $P_0$.

The
composition $P[-1]\r C\xrightarrow{p'} M[i]$ factors through
$\sigma_{\le -i}(P[-1])$ where $\sigma_{\le -i}$ denotes ``naive'' truncation.
Hence $\sigma_{\le -i}(P[-1])\in \langle P_0\rangle$.

 We then obtain a morphism
of distinguished triangles in $D^b_f(\Lambda)$
\[
\xymatrix{
P[-1]\ar[r]\ar[d] & C\ar[d]^{p'}\ar[r]^q\ar@{-}[d] & \Lambda\ar@{.>}[d]\\
\sigma_{\le -i}(P[-1])\ar[r]& M[i]\ar[r] & Z
}
\]

where $Z$ is the cone of the lower leftmost map.
We see that $Z$ has no cohomology in degree zero and hence
$\Hom_{D^b_f(\Lambda)}(\Lambda,Z)=0$. Thus $p'$ factors
through $\sigma_{\le i}(P[-1])$.  So $p$ (which is the image of $p'$ in
$D^b_f(\Lambda)/\langle P_0\rangle$) is the zero map. This finishes
the proof of \eqref{ref-5.7-15} for $i>0$.

It follows also from  \eqref{ref-5.7-15} that $\Hom_{D^b(\Lambda)/\langle
  P_0\rangle}(\Lambda,-)$ is a right exact functor on
$\mod(\Lambda)$.  To compute $\Hom_{D^b(\Lambda)/\langle
  P_0\rangle}(\Lambda,M)$ let $\bar{M}=\coker \phi$ (cfr \eqref{phidef}). Applying
\eqref{ref-5.7-15} together with \eqref{ref-5.6-14} to the right exact
sequence
\[
  P_0^n \r M \r \bar{M}\r 0
\]
we obtain
\[
\Hom_{D^b(\Lambda)/\langle P_0\rangle}(\Lambda,M)=\bar{M}
\]
Applying this identity with
$M=\Lambda$ we immediately obtain \eqref{ref-5.4-12}.
\def\qed{}\end{proof}
\subsection{Application to Claire Amiot's generalized cluster categories}
Let $(Q,w)=(Q_0,Q_1,w)$ be a quiver with super potential (thus $w$ is
an element of the completed path algebra $\widehat{kQ}$). The
Ginzburg algebra $\Gamma(Q,w)$ is the DG-algebra
$(k\widetilde{Q},d)$ where $\widetilde{Q}$ is the graded quiver
with vertices $Q_0$ and arrows
\begin{itemize}
\item The original arrows $a$ in $Q_1$ (degree 0);
\item Opposite arrows $a^\ast$ for $a\in Q_1$ (degree -1);
\item Loops $c_i$ at vertices $i\in Q
 _0$ (degree -2). We put
  $c=\sum_i c_i$.
\end{itemize}
The differential is
\begin{align*}
da&=0\qquad a\in Q_1\\
da^\ast&=\frac{\partial w}{\partial a}\qquad a\in Q_1\\
dc&=\sum_{a\in Q_1} [a^\ast,a]
\end{align*}
Let $\widehat{\Gamma}(Q,w)$ be the graded completion of $\Gamma(Q,w)$
at path length.  The cohomology in degree zero of $\widehat{\Gamma}(Q,w)$ is
called the Jacobian algebra of $(Q,w)$ and is denoted by $\Pscr(Q,w)$. Concretely
one has
\[
\Pscr(Q,w)=\widehat{kQ}\left/\left\langle \left(\frac{\partial w}{\partial
    a}\right)_{a\in Q_1}\right\rangle\right.
\]
Put
\[
\Cscr_{Q,w}=\Perf(\widehat{\Gamma}(Q,w))/\langle (S_i)_{i\in Q_0} \rangle
\]
where $S_i$ is the simple
$k\widetilde{Q}$ representation corresponding to the vertex $i$ (this is
perfect because of \cite[\S2.14]{KY}).  In
\cite[Thm 3.6]{Amiot} Claire Amiot shows that if $\Pscr(Q,w)$ is finite
dimensional then $\Cscr_{Q,w}$ is a 2-CY category
with cluster tilting object $\widehat{\Gamma}(Q,w)$.
The endomorphism ring of this cluster tilting object is  $\Pscr(Q,w)$.

\medskip

Assume now that $R$ is a complete local 3-dimensional Gorenstein domain with
residue field $k$ with an isolated singularity.
Assume that $N$
is a Cohen-Macaulay $R$-module whose summands are not isomorphic to
$R$ and pairwise non-isomorphic such that in addition the following property
holds:

\begin{itemize}
\item For $\Lambda=\End_R(R\oplus N)$ one has $\Lambda\cong H^\ast(\widehat{\Gamma}(Q,w))$
  for some finite quiver and potential $w$.
\end{itemize}
This condition is equivalent to
the 3-Calabi-Yau property for $\Lambda$ (see
\cite{Gi,Keller11,VdBsuper}).

Let $0$ be the vertex of $Q$ corresponding to the $R$-summand of $R\oplus N$.
Let $(Q^0,w^0)$ be obtained from $(Q,w)$
by deleting all edges in $Q$ which are adjacent to $0$ and all paths
 in $w$ which pass through $0$.
By Theorem \ref{ref-5.1.1-5}
one obtains
\begin{propositions}
\label{ref-5.2.1-16}
One has an exact equivalence of triangulated categories
\[
\underline{\MCM}(R)\cong \Cscr_{Q^0,w^0}
\]
\end{propositions}
\begin{examples}
Assume that $R=k[[t,x,y,z]]/(xy-zt)$. Then $R$ has a non-commutative crepant resolution
$\End_R(R\oplus I)$ with $I=(x,z)$. The corresponding quiver is
\[
\xymatrix{
0
\ar@<1.5ex>@/^0.5em/[rr]|p\ar@/^0.5em/[rr]|q&&
1
\ar@<1.5ex>@/^0.5em/[ll]|r\ar@/^0.5em/[ll]|s
}
\]
with super potential
\[
w=psqr-prqs
\]
We see that $Q^0$ consists of the single vertex $1$ and $w^0=0$. Hence
\[
\widehat{\Gamma}(Q^0,w^0)=k[c]
\]
with $\deg c=-2$.
Using the definitions in \cite{Keller6} it
follows that $\underline{\MCM}(R)$ is the cluster category associated
to the single vertex/no loops quiver; which is simply the category of $\ZZ/2\ZZ$
graded finite dimensional vector spaces.
\end{examples}
\section{Minimal models for Koszul algebras}
The first few sections contain no new material. Their main purpose is to make explicit some formulas.
Throughout we follow a version of the Sweedler convention. An element
$a$ of a tensor product $X\otimes Y$ is written as $a'\otimes a''$ (thus we suppress
the summation sign) and a similar convention for longer tensor
products.
\subsection{The general case}
\label{ref-6.1-17}
Below $A=T_l^\circ V/(R)$ is a finitely generated quadratic algebra
(thus $V$ is a finitely generated $l$-bimodule and $R\subset V\otimes_l V$).  We put
\[
J_n=\bigcap_{i=0}^{n-1} V^{\otimes i-1}\otimes R\otimes V^{\otimes n-1-i}
\]
and in particular
$J_1=V$, $J_2=R$.

We note that $A$ is naturally $\NN$-graded by giving $V$ degree $1$ (as usual this is referred to
as the Adams grading).

The canonical map
\[
J_n\mapsto J_i\otimes_l J_{n-i}
\]
is denoted by $\delta_i$ (or $\delta_{i,n-i}$ for clarity). It has degree zero for the Adams grading.
Following our convention we write.
\[
\delta_i(a)=\delta_i(a)'\otimes \delta_i(a)''
\]

Put
\[
\tilde{V}=\bigoplus_{n>0} J_n[n-1]
\]
and
\[
\tilde{A}=T_l\tilde{V}
\]
For $a\in J_n$ considered as an element of degree $n-1$ in $\tilde{A}$
we put
\[
da=(-1)^{i-1}\sum_i \delta_i(a)'\otimes \delta_i(a)''
\]
It is easy to see that $d^2=0$.
\begin{propositions}
\label{ref-6.1.1-18} Assume that $A$ is Koszul. Then the map $q:\tilde{A}\r A$  induced
from the projection map $\tilde{V}\r J_1=V$
is a quasi-isomorphism.
\end{propositions}
\begin{proof} This follows in the standard way from the bar-cobar
  formalism (see Lemma \ref{ref-4.1-4}). For the benefit of the reader we give a direct proof.

By definition the fact that $A$ is Koszul means that the following complex of graded left $A$-modules is exact
\begin{equation}
\label{ref-6.1-19}
\cdots \r A\otimes_l J_2\r A\otimes_l J_1\r A\r l\r 0
\end{equation}
where the differential is given by
\[
d:A\otimes_l J_n\r A\otimes_l J_{n-1}:a\otimes b\mapsto a\delta_{1,n-1}(b)'\otimes \delta_{1,n-1}(b)''
\]
Put
\[
M=(T_l\tilde{V})_+\overset{\text{def}}{=}\bigoplus_{n\ge 1} \tilde{V}^{\otimes_l
  n}\subset T_l\tilde{V}
\]
We consider $M$ as a left $\tilde{A}$ sub DG-module of $\tilde{A}$. As left graded $\tilde{A}$-module
we have
\[
M=\tilde{A}\otimes_l (J_1\oplus J_2[1]\oplus J_3[2]\oplus\cdots)
\]
Let $\tilde{C}$ be the cone of
the inclusion map $i:M\r \tilde{A}$. As graded $\tilde{A}$-modules we have
\[
\tilde{C}=\tilde{A}\otimes_l (l\oplus J_1[1]\oplus J_2[2]\oplus\cdots)
\]
As $\coker i=l$ the obvious map $\tilde{C}\r l$ is a a quasi-isomorphism.

Put $C=A\otimes_{\tilde{A}}\tilde{C}$. Then one checks that $C$ is
precisely the complex \eqref{ref-6.1-19} (without the right most $l$). Thus
$C\r l$ is a quasi-isomorphism as well and hence so is the canonical
map $\tilde{C}\r C$.

We now equip $\tilde{C}$ with an ascending filtration of
sub-DG-$\tilde{A}$-modules as follows: $F_0 \tilde{C}=\tilde{A}$,
$F_1\tilde{C}=\tilde{A}\otimes(k\oplus J_1[1])$, \dots. We equip $C$ with the
similar filtration.
The canonical
map $\tilde{C}\r C$ is a map of filtered DG-$\tilde{A}$-modules.

Assume we have shown that $\tilde{A}\r A$ is a quasi-isomorphism in
Adams degree $\le n$. Then $(\tilde{C}/F_0\tilde{C})_{n+1}\r (C/F_0C)_{n+1}$ is
a quasi-isomorphism.
 Given that $\tilde{C}_{n+1}\r C_{n+1}$
is a quasi-isomorphism we deduce that $F_0\tilde{C}_{n+1}=\tilde{A}_{n+1}\r A_{n+1}=(F_0C)_{n+1}$ is also a
quasi-isomorphism.
\end{proof}
\begin{remarks}
\label{ref-6.1.2-20} It is easy to see that a suitable analogue of Proposition \ref{ref-6.1.1-18}
holds for the completed rings $(T^\circ_lV/(R))\,\hat{}$. Indeed this simply means
that the directs sums involved in the grading become direct products. Taking
direct products of vector spaces is an extremely well behaved functor so
it does not break anything. We will rely on this fact below without further
elaboration.
\end{remarks}
\subsection{Polynomial rings}
We recall the familiar finite minimal model for polynomial rings.
Assume $A=k[x_1,\ldots,x_n]$.  If we put $V=\sum_i kx_i$ then $J_n=\wedge^n V\subset V^{\otimes n}$.
Write $x_{S}=\wedge_{i\in S} x_i$ for $S\subset [n]$, $[n]=\{1,\ldots,n\}$, $S\neq \emptyset$. In the wedge product $\wedge_{i\in S} x_i$
we assume that the indices of the variables are in ascending order.

Specializing \S\ref{ref-6.1-17} to this situation we obtain that
$\tilde{A}$ is equal to $k\langle(x_S)_{S\neq \emptyset}\rangle$ with differential
\begin{equation}
\label{ref-6.2-21}
dx_S=\sum_{S=A\coprod B,A\neq\emptyset,B\neq\emptyset}(-1)^{|A|-1} \epsilon_{A,B} x_A x_{B}
\end{equation}
where $\epsilon_{A,B}$ is the sign defined by
\[
\wedge_{i\in S} x_i=\epsilon_{A,B}\left(\wedge_{i\in A} x_i\right)\wedge \left(\wedge_{i\in B} x_i\right)
\]
\subsection{Crossed products}
We now assume that $k$ has characteristic zero.
Assume that $\Lambda=A\# G$ is a crossed product with $A=k[x_1,\ldots,x_n]$ and
$G$ a finite group acting linearly on $A$. Since
the construction of the finite minimal model of $A$ is functorial (it
is an application of the general construction in~\S\ref{ref-6.1-17})
 we obtain a finite minimal model for $\Lambda$ of the form
\begin{equation}
\label{ref-6.3-22}
\tilde{\Lambda}=\biggl(k\langle (x_S)_S\rangle\# G,d\biggr)
\end{equation}
(with $l=kG$).
The differential is $kG$-linear and on the variables $(x_S)_{S\neq \emptyset}$
it is given by the formula \eqref{ref-6.2-21}.
\subsection{Crossed products for cyclic groups}
\label{ref-6.4-23}
In this section we specialize to the case where $G$ is the cyclic
group $\ZZ/m\ZZ$. We now assume that $k$ is algebraically closed of
characteristic zero so that we may assume that $G$ acts diagonally on
$V=kx_1+\cdots+kx_n$.  Fix a primitive $m$'th root of unity~$\xi$. We
write $\chi_i$ for the character of $G$
\[
\chi_i(\bar{a})=\xi^{ai}
\]
and we let $e_i$ be the corresponding primitive idempotent
\[
e_i=\frac{1}{m}\sum_{a=0}^{m-1} \chi_i(\bar{a})\bar{a}=\frac{1}{m}\sum_{a=0}^{m-1}\xi^{ai} \bar{a}
\]
so that we have
\[
kG=\sum_{i=0}^{m-1} ke_i
\]
We assume that $G$ acts on the variable $x_i$  by the character $\chi_{a_i}$ for some $0\le a_i\le m-1$. Thus
in $\Lambda=A\# G$ with $A=k[x_1,\ldots,x_n]$ we have the relation
\[
\bar{a}\cdot x_i=\xi^{aa_i} x_i\cdot \bar{a}
\]
which implies
\begin{align*}
e_j\cdot x_i=x_i \cdot e_{j+a_i}
\end{align*}
(from now we tacitly reduce indices modulo $m$). Specializing \eqref{ref-6.3-22} we obtain a finite minimal model $\tilde{\Lambda}$ for $\Lambda$ which is
freely generated over $l$ by the variables $(x_S)_S$ subject to the relations
\[
e_j\cdot x_S=x_S \cdot e_{j+d(S)}
\]
where
\[
d(S)=\sum_{i\in S} a_i
\]
and with differential as in \eqref{ref-6.2-21}.
\subsection{McKay quiver description}
We reformulate the results of the previous section in quiver language.
Let $Q$ be the
quiver with vertices $\{0,\cdots,m-1\}$ (taken modulo $m$) and arrows
$x_{j,i,j+a_i}$ for $i=1,\ldots,n$, $j=0,\ldots,m-1$ starting at $j$
and ending at $j+a_i$.  Then $\Lambda$ is a quotient of the path algebra of
$Q$ where the arrow $x_{i,j,j+a_i}$ is sent to
$e_jx_i=x_ie_{j+a_i}=e_jx_ie_{j+a_i}\in \Lambda$. The relation $x_kx_l=x_lx_l$ in
$\Lambda$ leads to the relation
\begin{equation}
\label{ref-6.4-24}
x_{j,k,j+a_k}\cdot x_{j+a_k,l,j+a_k+a_l}=x_{j,l,j+a_l}\cdot x_{j+a_l,k,j+a_k+a_l}
\end{equation}
on $Q$. The path algebra of $Q$ module all such relations is precisely $\Lambda$.

To describe the algebra $\tilde{\Lambda}$ we introduce the graded quiver
$\tilde{Q}$ with the same vertices as $Q$ and with arrows
$x_{j,S,j+d(S)}$ of homological degree $-|S|+1$ going from $j$ to
$j+d(S)$. The differential on $k\tilde{Q}$ is given by
\begin{equation}
\label{ref-6.5-25}
dx_{j,S,j+d(S)}=\sum_{S=A\coprod B,A\neq\emptyset,B\neq\emptyset}(-1)^{|A|-1} \epsilon_{A,B} x_{j,A,j+d(A)} \cdot x_{j+d(A),B,j+d(S)}
\end{equation}
Let $\tilde{Q}^0$ be the quiver obtained from $\tilde{Q}$ by dropping
all arrows adjacent to $0$. Thus the arrows in $\tilde{Q}^0$ are
of the form $x_{j,S,j+d(S)}$ with $j\neq 0$, $j+d(S)\neq 0$. Specializing
Theorem \ref{ref-5.1.1-5} to the current situation we obtain the
following result which we will formulate in the complete setting
for variety. Note that by Remark \ref{ref-6.1.2-20} this makes little difference.
\begin{propositions}
\label{ref-6.5.1-26}
Let $A=k[x_1,\ldots,x_n]$ and assume that the cyclic group $G=\ZZ/m\ZZ$ acts
linearly on $A$ with weights $(\xi^{a_1},\ldots,\xi^{a_n})$ satisfying the
additional properties $\sum_ia_i\cong 0\text{ mod } 0$ and $\gcd(a_i,m)=1$.
Then
\[
\underline{\MCM}(\hat{A}^G)\cong \Perf(k\tilde{Q}^0,d)/\langle
(S_i)_{i=1,\ldots,m-1}\rangle
\]
where the differential is given by \eqref{ref-6.5-25} (taking into
account that arrows adjacent to the vertex $0$ should be suppressed
on the righthand side). The DG-algebra $(k\tilde{Q}^0,d)$ has finite
dimensional cohomology and
\[
H^0(k\tilde{Q}^0,d)\cong \hat{\Lambda}/\hat{\Lambda} e_0\hat{\Lambda}
\]
\end{propositions}
\begin{proof} This is a straight translation of Theorem \ref{ref-5.1.1-5}.
The conditions on the numbers $(a_i)_i$ are to insure that $\hat{A}^G$ is
Gorenstein and has an isolated singularity.
\end{proof}
\begin{examples} We discuss an example that occurred in \cite{IY,
KMVdB}. Assume that $G=\ZZ/2\ZZ$ acts with weights $(-1,-1,-1,-1)$
on $k[x_1,x_2,x_3,x_4]$. The resulting McKay quiver looks like
\[
\xymatrix{
0
\ar@<3ex>@/^0.5em/[rr]|{x_1}
\ar@<2ex>@/^0.5em/[rr]|{x_2}
\ar@<1ex>@/^0.5em/[rr]|{x_3}\ar@/^0.5em/[rr]|{x_4}&&
1
\ar@<3ex>@/^0.5em/[ll]|{x_1}
\ar@<2ex>@/^0.5em/[ll]|{x_2}
\ar@<1ex>@/^0.5em/[ll]|{x_3}\ar@/^0.5em/[ll]|{x_4}&&
}
\]
with relations
\[
x_ix_j=x_jx_i
\]

The quiver $\tilde{Q}^0$ contains a single vertex $1$ and loops
$x_{ij}$, $i<j$ and $x_{1234}$ respectively of degree $-1$ and $-3$. The differential is given by
\[
dx_{1234}=-[x_{12},x_{34}]-[x_{23},x_{14}]+[x_{24},x_{13}]
\]
where as usual $[-,-]$ denotes the graded commutator.
\end{examples}
\subsection{The minimal case}
In this section we impose the additional condition.
\begin{equation}
\label{ref-6.6-27}
\sum_i a_i=m
\end{equation}
It was proved in \cite{AIR} that if condition \eqref{ref-6.6-27}
holds then $\underline{\MCM}(\hat{A}^G)$ has a description as a higher cluster
category. In this section we indicate how to prove this starting from
Proposition \ref{ref-6.5.1-26}.

We order the vertices of $\tilde{Q}^0$ by their label. We we say that
an arrow $x_{j,S,j+d(S)}$ is ascending if $j+d(S)>j$ (recall that the
sum $j+d(S)$ is reduced $\mod m$). Otherwise we say that the arrow is
descending.

Let $P$ be the quiver with the same vertices as $\tilde{Q}^0$ but only
with ascending arrows of the form $x_{j,i,j+a_i}$ subject to relations
\[
x_{j,k,j+a_k}\cdot x_{j+a_k,l,j+a_k+a_l}=x_{j,l,j+a_l}\cdot x_{j+a_l,k,j+a_k+a_l}
\]
Let $C$ be the resulting path algebra. As in \cite{Keller11,VdB29} we
define the inverse dualizing complex of $C$ as
\[
\Phi_C=\RHom_{C^e}(C,C\otimes C)
\]
\begin{propositions}
\label{ref-6.6.1-28}
There is a quasi-isomorphism of DG-algebras
\begin{equation}
\label{tensor}
(k\tilde{Q}^0,d)\cong T_C(\Theta_{C}[n-1])
\end{equation}
In particular $
\underline{\MCM}(\hat{A}^G)
$
is a generalized $n-1$-cluster category.
\end{propositions}
The fact that $\underline{\MCM}(\hat{A}^G)$ has an $n-1$-cluster tilting object
has already been established by Iyama \cite[Thm 5.2.1]{iyama}. So we only need
to be concerned with proving \eqref{tensor}.
The rest of this section will be devoted to this.

Let $\tilde{P}$ be the quiver with the same vertices as $\tilde{Q}^0$
but only with ascending arrows.  Let $D$ be the $k\tilde{P}$ bimodule
generated by the descending arrows. Then we have
\[
k\tilde{Q}^0=T_{k\tilde{P}}D
\]
Furthermore if we look at the formula \eqref{ref-6.5-25} we see that both
$k\tilde{P}$ and $D$ are closed under the differential $d$ (it is here
that \eqref{ref-6.6-27} is used).

Hence we need to prove two things
\begin{enumerate}
\item The natural map $k\tilde{P}\r C$ is a quasi-isomorphism.
\item
$D\cong \Phi_{k\tilde{P}}[n-1]$
\end{enumerate}
The first statement follows from the following lemma
\begin{lemmas}
The algebra $C$ is Koszul over $l^0\overset{\text{def}}{=}l/le_0$. Furthermore $k\tilde{P}$ is the
minimal model for $C$ constructed in \S\ref{ref-6.1-17}.
\end{lemmas}
\begin{proof}
We give $A$ an additional grading by putting $\deg x_i=a_i$. It is easy to
see that the minimal resolution of $S_i$ for $C$ is obtained by resolving $k$
as a graded $A$-module for the Adams grading
and then truncating in degrees $\le m-i$ for the additional grading. It is clear
that this resolution is linear for the Adams grading.

Given the explicit form of the relations of $C$ one verifies immediately that
$k\tilde{P}$ is indeed the finite minimal form constructed in \S\ref{ref-6.1-17}.
\end{proof}
Now we prove the second statement.  We first discuss some generalities
on bimodules and differentials.

Let $E$ be a DG-algebra and assume that $P$,$Q$ are graded DG-$E$-bimodules. We write
$
P\otimes_{E^w} Q
$
for the quotient of $P\otimes_E Q/[E,P\otimes_E Q]$. The dual of an $E$-bimodule $Q$
is by definition
$
Q^\ast=\Hom_{E^e}(Q,{}_EE\otimes E_E)
$.
This is again a DG-$E$-bimodule through the surviving inner bimodule structure
on $E\otimes E$.

If $\omega\in (P\otimes_{E^e} Q)_n$ then we obtain an induced map of
degree $n$
\[
\omega^\circ:P^\ast\r Q:\phi\mapsto (-1)^{|\phi(\omega')'|(|\omega''|+|\phi(\omega')''|)}\phi(\omega')''\omega''\phi(\omega')'
\]
We say that $\omega$ is non-degenerate if $P$, $Q$ are finitely generated
projective $E$-bimodules and $\omega^\circ$ induces an isomorphism $P^\ast\cong Q[n]$.
If $d\omega=0$
then $\omega^\circ$ is a morphism of DG-bimodules.

\medskip

As $E$-bimodule $E$ is quasi-isomorphic to the cone of
\[
0\r \Omega_{E/l}\xrightarrow{\sigma} E\otimes_l E\r 0
\]
where $\Omega_{E/l}$ is the bimodule of non-commutative differentials. As
a graded $E$-bimodule $\Omega_{E/l}$ is generated by elements $Db$ subject to the standard
relations.\footnote{Using $db$ would lead to confusion with the differential
on $E$} One has $\sigma(Db)=b\otimes 1-1\otimes b$. The operator $D$
has degree zero, whence $d(Db)=D(db)$.

We denote the cone of $\sigma$ by $\tilde{\Omega}_{E/l}$. If $b\in
E$ then $Db$ considered as an element of degree $|b|-1$ of
$\tilde{\Omega}_{E/l}$ is written as $\tilde{D}b$.

Hence $\tilde{\Omega}_{E/l}$ is generated by $\tilde{D}b$ and an
$l$-central element $g$ of degree zero (this represents the generator
$1\otimes 1$ of $E\otimes_l E$). The differential on
$\tilde{\Omega}_{E/l}$ is given by
\begin{equation}
\label{ref-6.7-29}
\begin{aligned}
dg&=0\\
d(\tilde{D}b)&=-\tilde{D}(db)+[b,g]
\end{aligned}
\end{equation}
We compute $\tilde{\Omega}_{k\tilde{P}/l^0}$. For $j<j+d(S)$ write
$\tilde{x}_{j,d(S),j+d(S)}=\tilde{D} x_{j,S,j+d(S)}$. Thus $|\tilde{x}_{j,d(S),j+d(S)}|=
-|S|$.
Furthermore we
introduce loops $\tilde{x}_{j,\emptyset,j}$ at $j$ of degree zero which correspond to
$-ge_j$. Then $\tilde{\Omega}_{k\tilde{P}/l^0}$ is the free bimodule
with generators $\tilde{x}_{j,d(S),j+d(S)}$ for $j\le j+d(S)$,
$S\subsetneq [n]$ with $[n]=\{1,\ldots,n\}$. A simple computation using
the formulas \eqref{ref-6.7-29}
yields
\begin{multline}
\label{ref-6.8-30}
d(\tilde{x}_{j,S,j+d(S)})=\sum_{S=A\coprod B,B\neq \emptyset} (-1)^{|A|}\epsilon_{A,B}
\tilde{x}_{j,A,j+d(A)}\cdot
x_{j+d(A),B,j+d(S)}\\-\sum_{S=A\coprod B,A\neq \emptyset} \epsilon_{A,B} x_{j,A,j+d(A)}\cdot
\tilde{x}_{j+d(A),B,j+d(S)}
\end{multline}
We define an element $\omega\in \tilde{\Omega}_{k\tilde{P}/l^0}\otimes_{k\tilde{P}^e}D$ by
the following formula
\[
\omega=\sum_{S\subsetneq [n]),j\le j+d(S)}
(-1)^{|S|-1}\epsilon_{S,S^c}\tilde{x}_{j,S,j+d(S)}\otimes x_{j+d(S),S^c,j}
\]
One verifies
\begin{enumerate}
\item $|\omega|=-n+1$.
\item $d\omega=0$.
\item $\omega$ is non-degenerate.
\end{enumerate}
It follows that $\omega$ defines an isomorphism
$\omega^\circ:\Theta_{k\tilde{P}}=\tilde{\Omega}_{k\tilde{P}/l^0}^\ast\r D[-n+1]$.
Hence the proof is complete.

\def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\ifx\undefined\bysame
\newcommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\,}
\fi

config: arxiv


TITLE: First Order Logic - Proving Rule to Be Derivable
QUESTION [1 upvotes]: I am trying to understand how to prove if a rule is derivable or not using sequent calculus.
A practice problem in my book I am learning from has the following question:
Consider the rule:
$$\frac{}{\Gamma \hspace{10pt} \exists x\phi \hspace{10pt} \forall x\phi }$$
Determine whether this rule is derivable or not.
I think you need to start from the assumption rule to state $\Gamma \phi \models \phi$ and then make inferences from there. My intuition wants to say that this is not a derivable rule since the existential quantifier is less strict than the universal quantifier, but I'm not sure how to prove it or if my intuition is even correct...
Thank you in advance for helping me work through this problem.
Edit: I am working with the calculus defined in the book Mathematical Logic by H.-D. Ebbinghaus, J. Flum, and W. Thomas in chapter IV.

REPLY [1 votes]: To prove that an inference rule is invalid, you just need provide a model in which the rule fails. In your case, you need to provide a language, a formula $φ$ in that language and a structure over that language where $\exists x\ ( φ(x) )$ is true but $\forall x\ ( φ(x) )$ is false.