TITLE: Definition of prime element in a Euclidean ring does not make sense. Herstein - Topics in Algebra
QUESTION [5 upvotes]: Herstein's Definition: In the Euclidean ring $R$, a nonunit $\pi$ is said to be a prime element of $R$ if whenever $\pi=ab$, where $a,b \in R$, then one of $a$ or $b$ is a unit in R.
$\mathbb Q$ is a field and hence a Euclidean ring. In $\mathbb Q$ every element except $0$ is a unit. So there are no prime elements in $\mathbb Q$?

REPLY [2 votes]: Yes there are no primes in a field. $5$ is a prime in $\mathbb{Z}$ but not in $\mathbb{Q}$
More generally if you have two rings $A\subset B$, being a prime in $A$ does not imply being a prime in $B$. As an example take $\mathbb{Z}\subset \mathbb{Z}[\sqrt{-2}]$. Then we have $3$ is a prime in $\mathbb{Z}$ while $3=(1+\sqrt{-2})(1-\sqrt{-2})$ is not a prime in $\mathbb{Z}[\sqrt{-2}]$


TITLE: Good Books on the history of Zero
QUESTION [3 upvotes]: I am looking for books that discuss the origins of the zero, specifically the differences in the use and concept of  the zero number among different civilizations (considering also the Mesoamerican cultures).

REPLY [0 votes]: Alain Schärlig, Du zéro à la virgule; Les chiffres arabes à la conquête de l'Europe, 1143–1585, Presses Polytechniques et Universitaires Romandes, Lausanne, 2010. 296 pp. ISBN: 978-2-88074-890-6. MR2741951
Rabindrnath Mukherjee, Discovery of zero and its impact on Indian mathematics, Das Gupta & Company Private Ltd., Calcutta, 1991. MR1314426
Georges Ifrah, From one to zero; A universal history of numbers, Penguin Books, New York, 1987. xvi+503 pp. ISBN: 0-14-009919-0.  MR0915160


TITLE: Can the remainder of a Taylor expansion be estimated from the coefficients?
QUESTION [2 upvotes]: Given a formula for the coefficients $c_n\in\mathbb C$ of a not analytically known function $f:\mathbb C\to\mathbb C, z\mapsto f(z)$'s Taylor series, is there any way to estimate the remainder term of the order $N$
$$r_N(z) := f(z) - \sum_{n=0}^N c_n z^n$$
within a given radius $|z|\le\rho$ (truly smaller than the convergence radius) that only depends on a finite amount of the $c_n$ or some limit thereof? In other words, is there a way to obtain a $R_N$ such that $|r_n(z)|\le R_n(\rho)\ \forall |z|\le\rho$?

REPLY [3 votes]: It seems to depend strongly upon what knowledge made you conclude that the radius of convergence is at least $\rho$? If for example, you happen to know that the function is analytic on a disk $D(0,\rho)$ and is uniformly bounded on that disk, say $|f(z)|\leq M<+\infty$ for all $|z|<\rho$ then indeed you can estimate the remainder. From Cauchy, integrating over a circle of radius $\rho-\epsilon$ and for $|z|<\rho$:
$$ f(z) = \oint_{\partial B} \frac{f(u)}{u-z}\frac{du}{2\pi i}
= \oint_{\partial B} \frac{f(u)}{u} \left( 1+ \frac{z}{u} + \cdots \right) \frac{du}{2\pi i}=\sum_{n=0}^{N} c_nz^n + R_N(z) $$
where (after taking the limit $\epsilon\rightarrow 0$):
$$ |R_N(z)| \leq \left|\oint_{\partial B} \frac{f(u)}{u} \frac{z^{N+1}}{u^{N+1}}\frac{1}{u-z}  \frac{du}{2\pi i}\right| \leq M \left(\frac{|z|}{\rho}\right)^{N+1} \frac{1}{\rho-|z|}$$
Without any uniform bounds on $|f|$ (or the sequence $c_n$), I don't have any reasonable suggestion. After all you may always add $10^{266} z^{N+1}$ without changing the radius of convergence.


TITLE: When to use probabilistic schemes
QUESTION [0 upvotes]: I have a box with $10$ bulbs, from which $3$ are broken. We randomly pick $2$ of them. What is the probability that at least $1$ bulb is broken?

I think here we could use the Bernoulli probabilistic scheme, but I'm not sure how to use it, and why it should be used here, and why we need to use probabilistic schemes?

REPLY [0 votes]: There are three successful outcomes for at least one broken. These are:
$BU, UB$ and $BB$.
We can easily compute the probability of each outcome whereby the "sum" is the probability that at least one is broken.
$P(B>0) = P(BU)+P(UB)+P(BB)$
$P(BU) = \frac{3}{10}\cdot \frac{7}{9} =  \frac{7}{30}$
$P(UB) = \frac{7}{10}\cdot {3}{9} = \frac{7}{30}$
$P(BB) = \frac{3}{10}\cdot \frac{2}{9} = \frac{1}{15}$
$P(B>0) = \frac{7}{30}+\frac{7}{30}+\frac{1}{15} = \frac{8}{15}$
This is also equal to $1 - P(UU) = 1 - \frac{7}{10}\cdot \frac{6}{9} = 1 - \frac{7}{15} = \frac{8}{15}$


TITLE: Extension operator for Lipschitz domain in Sobolev spaces
QUESTION [2 upvotes]: Suppose we have a Lipschitz domain $\Omega \subset \mathbb{R}^2$. Let $u$ be a function in the Sobolev space $W^{1\,,\,p}(\Omega)$. Since $\Omega$ is Lipschitz, there is an extension operator $P: W^{1\,,\,p}(\Omega) \to W^{1\,,\,p}(\mathbb{R}^2)$ such that
\begin{equation}
P \, u \, |_{\Omega}=u \tag{1}
\end{equation}
Q$1$. Can someone give me a reference for $(1)\,$?
Q$2$. How to extend $u$ in this case?

REPLY [5 votes]: Let us say that a domain $\Omega \subset \mathbb{R}^n$ is an extension domain if there exists a bounded linear operator $\mathcal{E} \colon W^{1,p}(\Omega) \to W^{1,p}(\mathbb{R}^n)$ such that $\mathcal{E}u(x) = u(x)$ for $x \in \Omega$.
It is proved in P. W. Jones, Quasiconformal mappings and extendability of functions in Sobolev spaces, Acta Math. 147 (1981), 71–88, that every uniform domain is an extension domain. Since domains with Lipschitz boundary are uniform, the result follows.
In general, the construction of the extension is done via a local reduction (change of variables that reduced the boundary of $\Omega$ to a particular shape) and a patching by means of partitions of unity. You can find several examples in standard books about Sobolev spaces.


TITLE: Determine the number of natural numbers smaller than $10^4$, in the decimal notation of which all the digits are distinct.
QUESTION [1 upvotes]: Determine the number of natural numbers smaller than $10^4$, in the decimal notation of which all the digits are distinct.
Please explain me the meaning of this question.
I am not asking a homework question. I just didn't understood  meaning of this question. Please don't close my question

REPLY [2 votes]: So first consider what we mean by a natural number in the decimal notation which is $\lt 10^4$. This is a positive integer with at most four digits.
We can write it as $$n=a_310^3+a_210^2+a_110^1+a_010^0=1000a_3+100a_2+10a_1+a_0$$
where we have $0\le a_0, a_1, a_2, a_3 \le 9$ and we normally write a decimal integer as a lot of digits with place value assumed $$n=a_3a_2a_1a_0$$ (where this is not multiplication but 'concatenation')
No repeated digits looks as though it means that $a_3, a_2, a_1, a_0$ are distinct when $n$ is expressed in this way. But some care is required with the digit zero, since we write $20$, which has no repeated digits, rather than $0020$, where the digits are repeated.


TITLE: How to find all solutions of $\tan(x) = 2 + \tan(3x)$ without a calculator?
QUESTION [1 upvotes]: Find all solutions of the equation $\tan(x) = 2 + \tan(3x)$ where $0<x<2\pi$.
By replacing $\tan(3x)$ with $\dfrac{\tan(2x) + \tan(x)}{1-\tan(2x)\tan(x)}$
I've gotten to $\tan^3 (x) - 3 \tan^2 (x) + \tan(x) + 1 =0$.
I am not sure how to proceed from there without the use of a calculator.

REPLY [0 votes]: $t=\tan x=1$ is easy to deal with
$$t^2-2t-1=0\implies -2t=1-t^2\implies\frac{2t}{1-t^2}=-1$$
$$\tan2x=-1=-\tan\frac\pi4=\tan\left(-\frac\pi4\right)$$
$$2x=n\pi-\frac\pi4$$ where $n$ is any integer


TITLE: History of the study of Verma modules in terms of Kazhdan Lusztig Theory
QUESTION [8 upvotes]: Let $\mathfrak{g}$ be a complex finite dimensional semisimple Lie algbera, $W$ be the Weyl group, $\rho$ be the half sum of positive roots, $M(\eta)$ be the Verma module of weight $\eta$ and $L(\eta)$ its unique simple quotient. Then it is well-known that $[M(w\cdot(-2\rho)):L(x\cdot(-2\rho))]=P_{w_0w,w_0x}(1)$, where $P_{u,v}$ is the Kazhdan Lusztig polynomial of $W$ and $w_0$ is the longest element in $W$. The above is an example that illustrating the fact that  one can study Verma modules in terms of Kazhdan Lusztig Theory.
For more evidences, we also have Kazhdan-Lusztig Conjectures for affine Lie algebra (See Masaki Kashiwara and Toshiyuki Tanisaki --- Characters of irreducible modules with
non-critical highest weights over affine Lie algebras) and the paper: RONALD S. IRVING--- The socle filtration of a Verma module.

I would like to have the brief/full history of the study of Verma modules in terms of Kazhdan Lusztig Theory. If possible, please provides reference(s) for each aspect of the study of Verma modules. It would be great to have history about Verma modules over different types of Lie algberas (semisimple, affine or even Kac Moody Lie algebra).

REPLY [5 votes]: It's probably too soon to expect a good historical overview, but for example Steve Kleiman has already written a scholarly article (The development of intersection homology theory) emphasizing the original KL (Kazhdan-Lusztig) conjecture.   This is available in arXiv versions or in the published version cited there.
One contributor easily overlooked is Vinay Deodhar, who probed further in what he called "KL theory".  See for example his influential joint paper Deodhar–Gabber–Kac - Structure of some categories of representations of infinite-dimensional Lie algebras (MSN), or the 1991 survey Deodhar - A brief survey of Kazhdan-Lusztig theory and related topics (MSN).   He soon dropped out of the research world because of illness in his immediate family, but was starting to get involved again when he himself developed serious health problems and later died.    But in the late 1970s, when I met him at IAS Princeton where Jantzen was then visiting, both he and Jantzen were getting close to the Kazhdan-Lusztig viewpoint.
There is also a characteristically readable textbook by Roger Carter, Lie algebras of finite and affine type.  See especially Chapters 19-20.  This is only the first step toward Verma modules and simple modules for general Kac-Moody algebras, but it conveys much of the flavor of the subject.
In the direction of quantum enveloping algebras, there are of course many papers and books (including the one by Lusztig, Introduction to quantum groups (MSN)) which suggest the open-ended nature of the representation theory there.    But in this and other directions, there is apparently no comprehensive history yet available.   Probably it's too soon for that.


TITLE: Do all vectors must have a "Direction " and "Magnitude"?
QUESTION [2 upvotes]: Pleases explain it as easy as possible,I started to learn linear algebra of vector a few week ago.If it so ,then the next question is that if I take an element(indeed a vector) of "any" vector space ,then how can I find its particular "magnitude" and "direction"?

REPLY [3 votes]: In short, no.  When you are just starting to study linear algebra, all of the vector spaces you will see for a while are finite-dimensional vector spaces where the scalar field is the real numbers, and in these vector spaces, both magnitude and direction make sense.  Every vector in these vector spaces has a magnitude, and almost every vector has a direction.  But there is one exception:  the zero vector has zero magnitude but does not have any definable direction.
More generally (and you should start seeing some of these more general examples pretty soon in your studies), the answer to your question depends on what you mean by a "vector."  In order for a vector to have a magnitude, the vector space must support a norm, and not all vector spaces do; similarly, in order for a vector to have a direction, the vector space must support an inner product, and not all vector spaces do.  An inner product can be used to define a norm, though, so if a vector field suports having directions for its vectors, then it supports magnitudes, too.
Getting back to finite-dimensional vector spaces where the scalar field is the real numbers, these spaces support both a norm and an inner product, so magnitude and direction both make sense.  Except for the zero vector, as above.


TITLE: Local extrema in Poisson equation
QUESTION [2 upvotes]: My question is related to this one:
Minima & maxima of Laplace's equation
I know that Laplace equation (like all elliptic 2nd order PDE) prohibits local extrema, and that maximal values may be found only on the edges of the domain.
My question is:
Does Poisson equation (adding sources) change this?
Intuitively, I would assume that it should, as if I solve the equation over a disk with a point charge in the middle, I would expect the potential to be maximal (and even explode) in the middle.
Does it mean that Poisson equation isn't elliptic, or does the original general claim regarding local extrema in elliptic equations hold only for homogeneous cases?

REPLY [3 votes]: These types of theorems assume smoothness, or at least some amount of differentiability, so when you add sources, you need to be careful what types of sources they are.
Delta-function sources are not smooth.  So, if you are solving Poisson's equation in an open region $\Omega$ and you put a delta-function source at $P \in \Omega$, then you've violated the assumptions of the theorem.  To restore the assumptions of the theorem, you can instead consider the open region $\Omega' = \Omega \setminus P$; that is, remove the point $P$.  On $\Omega'$, your sources are zero, so you have Laplace's equation on an open region, and it should be simple to convince yourself that the solution does not achieve a maximum in $\Omega'$.
What about other types of sources, which are more smooth?  E.g., consider an electrostatics problem with some nicely-behaved, smooth charge distribution $\rho$.  In this case, it is possible for the potential $\Phi$ to achieve a maximum somewhere where $\rho \neq 0$.  But there's nothing wrong with this, because if $\rho \neq 0$ then we are not talking about Laplace's equation.


TITLE: Subgroup of a (free) group.
QUESTION [2 upvotes]: Let $F$ be a group, generated by $x_1,...,x_m$ and $H$ be its subgroup such that $|F:H|=n < \infty$. How to prove that $H$ can be generated by $n(m-1)+1$ elements?

REPLY [1 votes]: An argument I find really nice uses algebraic topology and finite graphs. More information may be found in Hatcher's or Massey's book, or on my blog and its references.
Let $F$ be a free group and $H$ be a subgroup. We view $F$ as the fundamental group of a graph $X$ (for instance, a bouquet of $\mathrm{rk}(F)$ circles). Let $Y \twoheadrightarrow X$ be a covering satisfying $\pi_1(Y) \simeq H$. In particular, the covering induces a structure of graph on $Y$ making the covering cellular.
Furthermore, if $n=[F:H] < + \infty$, the covering $Y \twoheadrightarrow X$ is $n$-sheeted, hence $\chi(Y)=n \cdot \chi(X)$. If $T \subset X$ is a maximal subtree, then $ X$ is the disjoint union of $T$ and $\mathrm{rk}(F)$ edges, hence
$$\chi(X)= \chi(T)- \mathrm{rk}(F)=1- \mathrm{rk}(F);$$
in the same way, $\chi(Y)= 1- \mathrm{rk}(H)$. Therefore, $\mathrm{rk}(H)=1+n \cdot (\mathrm{rk}(F)-1)$.


TITLE: $x^3+48=y^4$ does not have integer (?) solutions
QUESTION [10 upvotes]: How does one find all positive integer solutions to the equation $x^3+48=y^4$?

REPLY [7 votes]: I realize this is a massive revive, but here is a solution without any powerful theorems about elliptic curves.
We have $x^3 + 64 = y^4 + 2^4$. It is easy to show all (odd) primes dividing the RHS are $1 \pmod{8}$. Now, looking modulo $16$ we deduce either $x \equiv 1 \pmod{16}$ and $y$ is odd or $x,y$ are both even. For the second case if $v_2(x) = 1$ we derive a contradiction because $v_2(LHS) = 3$ while $v_2(RHS) \ge 4$. If $v_2(x) \ge 2$ we have $v_2(LHS) \ge 6$. Thus we must have $v_2(y) = 1$ for $v_2(y^4 + 16) > 4$. Writing $y = 2k$ we need $v_2(k^4 + 1) \ge 2$. But this is absurd since $v_2(k^4 + 1) \le 1$ by checking modulo $4$. Thus it follows $x \equiv 1 \pmod{16}$.
But now utilize $x^3 + 64 = (x+4)(x^2 - 4x + 16)$. $x+4$ is $5 \pmod{8}$, which is absurd so we are done.


TITLE: Conditional Expectation of Increasing Function
QUESTION [1 upvotes]: Let $g$ be an increasing function and $X$ a normal random variable. Is $p \mapsto \mathbf{E}[g(X)\, | \,X  \le p]$ an increasing function? My intuition says that each 'increment' of p would add more to the running average and so it must be true.

REPLY [4 votes]: Assume the expectation exist. For $q > p$,
$$ \begin{align} E[g(X)|X \leq q]
& = \int_{-\infty}^q g(x)\frac {f_X(x)} {F_X(q)}dx \\
& = \frac {F_X(p)} {F_X(q)}\int_{-\infty}^p g(x)\frac {f_X(x)} {F_X(p)}dx +
\int_p^q g(x)\frac {f_X(x)} {F_X(q)}dx \\
& = E[g(X)|X \leq p] - \left(1 - \frac {F_X(p)} {F_X(q)}\right)\int_{-\infty}^p g(x)\frac {f_X(x)} {F_X(p)}dx + \int_p^q g(x)\frac {f_X(x)} {F_X(q)}dx \\
& \geq E[g(X)|X \leq p] - \left(1 - \frac {F_X(p)} {F_X(q)}\right) g(p)
\int_{-\infty}^p \frac {f_X(x)} {F_X(p)}dx
+ g(p)\int_p^q \frac {f_X(x)} {F_X(q)}dx \\
& = E[g(X)|X \leq p] - \left(1 - \frac {F_X(p)} {F_X(q)}\right) g(p)
+ \frac {F_X(q) - F_X(p)} {F_X(q)}g(p) \\
& = E[g(X)|X \leq p]
\end{align}$$
So yes your intuition is correct, it is increasing with $p$.


TITLE: Prove $f(x)=x^3$ is not uniformly continuous in $\mathbb{R}$
QUESTION [1 upvotes]: I wanted to post here my solution and check if I'm right.
Also, I wanted to know how can you prove it with "Formal" way with Epsilon-Delta (I saw some posts but most people jump immediately to a solution).
My try :
I will take the sequences $x_n=n$ and $y_n=n+\frac {1}{n}$
$|x_n-y_n|=|n-n-\frac {1}{n}|=\frac {1}{n} \rightarrow 0$ (when $n \rightarrow \infty$)
but $|f(x_n)-f(y_n)|=|n^3-(n+\frac{1}{n})^3|=\cdots=3n+\frac {3}{n} + \frac {1}{n^3} \rightarrow \infty$ (when $n\rightarrow \infty$).
which shows that the function is not uniformly continuous over $\mathbb{R}$.

REPLY [1 votes]: Yes, that's fine.
If you want's a $\varepsilon-\delta$ approach, it's almost the same thing. You want to prove that $f$ is not uniformly continuous, which means that$$(\exists\varepsilon>0)(\forall\delta>0)(\exists x,y\in\Bbb R):|x-y|<\delta\wedge\bigl|f(x)-f(y)\bigr|\geqslant1.$$Take $\varepsilon=1$. Now, if $\delta>0$, you take $n\in\Bbb N$ such that $\frac1n<\delta$. Now you take $x=n$ and $y=n+\frac1n$ and your computations show that, indeed,$$\bigl|f(x)-f(y)\bigr|\geqslant1.$$


TITLE: Sum of values of indexes stored in a sequence?
QUESTION [0 upvotes]: I have this model:
$V = \{1, 2, 3, 5\}$
$V_n = $ value of n-indexed element of set V
$W = \{0.01, 0.02, 0.05, 0.1\}$
$W_n = $ value of n-indexed element of set W
$X = $ any sequence of elements from set $V$, ex: $X = (1, 2, 2, 5)$
$X_n = $ value of n-indexed element of sequence X
Now, what I want to do is to properly describe that my parameter $S_X$ will return sum of $W's$ under same index as $V's$ stored in $X$.
I can't put it any clearer sadly, so I'll try to explain it with this pseudocode:
V = {1, 2, 3, 5}
W = {0.01, 0.02, 0.05, 0.1}
X = (1, 2, 2, 5)

sum = 0

for n = 0, n < count(X), n=n+1 do
  i = V.indexOf(X[n])
  val = W[i]

  sum += val
end

How can I describe that code as a $\sum$?

REPLY [0 votes]: $\sum_{i=1}^{len(w)}w_i$
$\sum_{i=1}^{len(w)}w_i$


text:
\section{Rigidity of the eigenvalue estimate}
\label{sec:proof}

Our proof of \cref{thm:kohn_obata} differs from the higher-dimensional proof given by Li, Son and Wang~\cite{LiSonWang2015} in two ways.  First, as already noted in the introduction, we need a result of Takeuchi~\cite{Takeuchi2019} to conclude that the kernel of the CR Paneitz operator coincides with the complexified space of CR pluriharmonic functions.  Second, we give a simple and direct proof that if $\lambda_1(\Box_b)=\kappa$, then the Webster curvature equals $\kappa$ and the pseudohermitian torsion vanishes identically.  The classification of such pseudohermitian manifolds then implies the conclusion.

\begin{proof}[Proof of \cref{thm:kohn_obata}]
 We begin by recalling the argument of Chanillo, Chiu and Yang~\cite{ChanilloChiuYang2010}: Recall that the spectrum of the Kohn Laplacian in $(0,\infty)$ consists only of point eigenvalues~\cite{BurnsEpstein1990}*{Theorem~1.3}.  Let $\lambda>0$ be a nonzero eigenvalue of $\Box_b$ and let $f\in C^\infty(M;\bC)$ be a nontrivial function such that $\Box_bf=\lambda f$.  Set $\kappa:=\inf R>0$.  \Cref{prop:bochner} implies that
 \begin{align*}
  0 & = \lp Pf,f\rp + \int_M \left( \lv f^{11}\rv^2 - \frac{1}{2}\lv \Box_b f\rv^2 + R\lv\dbbar f\rv^2 \right)\,\theta\wedge d\theta \\
  & \geq \frac{1}{2}\int_M \lambda(\kappa-\lambda)\lv f\rv^2
 \end{align*}
 with equality if and only if $f^{11}=0$ and $\lp Pf,f\rp=0$ and $R=\kappa$ on $\supp\,\lv\dbbar f\rv^2$.  In particular, $\lambda\geq\kappa$, and hence $\lambda_1(\Box_b)\geq\kappa$.  It follows immediately that $\Box_b$ has closed range in $L^2$.  A result of Kohn~\cite{Kohn1985} then implies that $(M^3,T^{1,0})$ is embeddable.

 We now consider the case of rigidity.  That is, suppose that $\lambda_1(\Box_b)=\kappa$ and let $f\in C^\infty(M;\bC)$ be a nontrivial function such that $\Box_bf=\kappa f$.

 First observe that $f\in\ker P_1\cap\ker P_{\bar 1}$.  Indeed, from the first paragraph it holds that $\lp Pf,f\rp=0$.  Let $u$ and $v$ be the real and imaginary parts, respectively, of $f$.  Since $P$ is a formally-self adjoint real operator, $\lp Pu,u\rp = \lp Pv,v\rp = 0$.  Therefore $u$ and $v$ are CR pluriharmonic functions~\cite{Takeuchi2019}*{Proof of Theorem~1.1}.  Since $P_1$ and $P_{\bar 1}$ are linear, we conclude that $f\in\ker P_1\cap\ker P_{\bar 1}$.

 Next observe that the set $U:=\left\{ p\in M\suchthat \dbbar f(p)\not=0\right\}$ is dense in $M$.  Indeed, let $V$ be the interior of $M\setminus U$ and suppose that $V\not=\emptyset$.  Since $\Box_bf=0$ on $V$, we have that $f=0$ on $V$ as well.  Thus $\Real f$ and $\Imaginary f$ both vanish on $V$.  By the above paragraph, $\Real f$ and $\Imaginary f$ are CR pluriharmonic functions on $V$.  Since $M$ is embeddable, the unique continuation property for holomorphic functions~\cite{BaouendiEbenfeltRothschild1999}*{Chapter~VII} implies that $\Real f=0$ and $\Imaginary f=0$ on $M$, contradicting the assumption $f\not=0$.  In particular, since $R=\kappa$ on $U$, it holds that $(M^3,T^{1,0},\theta)$ has constant Webster curvature $\kappa$.

 Now, since $P_1f=0$ and $\Box_bf=\kappa f$, it holds that
 \begin{equation}
  \label{eqn:P1-consequence}
  iA_{11}f^1 = \frac{\kappa}{2}f_1 .
 \end{equation}
 Combining \cref{eqn:P1-consequence} with the fact $f^{11}=0$ yields
 \[ if^1A_{11;}{}^{11} = \frac{\kappa}{2}f_1{}^{11} . \]
 Since $P_{\bar 1}f=0$, we then deduce that
 \[ if^1A_{11;}{}^{11} = \frac{i\kappa}{2}A^{11}f_1  . \]
 Applying \cref{eqn:P1-consequence} again yields
 \[ iA_{11;}{}^{11}f^1 = -\lv A_{11}\rv^2f^1 . \]
 Since $U$ is dense, we conclude that $iA_{11;}{}^{11}=-\lv A_{11}\rv^2$ on $M$.  Integrating over $M$ yields $A_{11}=0$.

 Finally, since $(M,T^{1,0},\theta)$ has vanishing pseudohermitian torsion and constant positive scalar curvature $\kappa$, it is isometric to a quotient of the round CR three-sphere $S_\kappa^3$ with constant Webster scalar curvature $\kappa$~\cite{Tanno1969}*{Proposition~4.1}.  It is known~\cite{Folland1972} that the eigenspace $\left\{ f\in C^\infty(S_\kappa^3) \suchthat \Box_bf = \kappa f \right\}$ is spanned by $z$ and $w$, the holomorphic coordinates on $\bC^2$.  Since there is no nontrivial linear combination of $z$ and $w$ which descends to a quotient of $S_\kappa^3$, we conclude that $(M^3,T^{1,0},\theta)$ is isometric to $S_\kappa^3$.
\end{proof}

config: arxiv


text:
\begin{document}
\title{Lattices from Codes for Harnessing Interference: An Overview and Generalizations}
\author{Yu-Chih Huang and Krishna R. Narayanan\\
Department of Electrical and Computer Engineering \\
Texas A\&M University\\
{\tt\small {\{jerry.yc.huang@gmail.com and krn@ece.tamu.edu\}} }}

\maketitle

\begin{abstract}
In this paper, using compute-and-forward as an example, we provide an overview of constructions of lattices from codes that possess the right algebraic structures for harnessing interference. This includes Construction A, Construction D, and Construction $\pi_A$ (previously called product construction) recently proposed by the authors. We then discuss two generalizations where the first one is a general construction of lattices named Construction $\pi_D$ subsuming the above three constructions as special cases and the second one is to go beyond principal ideal domains and build lattices over algebraic integers.
\end{abstract}

\section{Introduction}
One major challenge differentiating multi-user communications from its point-to-point counterpart is that in a multi-user scenario, signals from one node would cause interference to nodes within the transmission range. Recently, there has emerged a novel perspective of dealing with interference which tries to harness interference via structured codes \cite{nazer2011CF} \cite{wilson10} \cite{ordentlich12} to name a few. The main idea behind such paradigm is to enable the destination nodes (typically relay nodes in a larger network) to compute and forward functions of messages rather than decoding them individually. The chosen functions have to in some sense match the operation induced by the channel so that the structural gains offered by the channel can be exploited.

At the heart of this strategy lies lattices constructed from codes (or nested lattice codes of Erez and Zamir \cite{erez04} to be specific). In this paper, using the compute-and-forward paradigm \cite{nazer2011CF} as an example, we aim to provide an overview of constructions of lattices from codes that are suitable for this novel interference management technique and discuss two generalizations that will expand the design space. The discussion and generalizations naturally carry over to other applications that adopt lattices from codes including integer-forcing linear receivers, compute-and-forward transform, physical-layer network-coding, etc.

In \cite{nazer2011CF}, Nazer and Gastpar adopt nested lattice codes \cite{erez04} at each node and let the relay nodes adaptively choose linear combinations of lattice codewords that are close to (a version of) the received signal. Those functions are then mapped back to linear combinations of messages in the finite field. This approach is shown to provide significant gains over the conventional strategies. Feng \textit{et al.} in \cite{Feng10} study the algebraic structure of compute-and-forward and show that the key enabler of such paradigm is the use of a ring homomorphism for mapping linear integer combinations of lattice codewords to linear combinations of messages over a finite field. They then use the isomorphism theorems in algebra to develop a general framework of constructing practical compute-and-forward schemes. In \cite{Engin12}, Tunali \textit{et al.} replace the nested lattice code in \cite{nazer2011CF} by the one constructed over Eisenstein integers and show that superior average computation rates to those in \cite{nazer2011CF} are achievable.

Both the lattice codes in \cite{nazer2011CF} and \cite{Engin12} are from Construction A \cite{LeechSloane71} \cite{conway1999sphere} which constructs lattices from linear codes. On the one hand, such construction is particularly good for compute-and-forward as lattices constructed from it possess ring homomorphisms and it is shown in \cite{erez05} to produce good lattices when the underlying linear code is over a sufficiently large prime field, properties that are required to show the results in \cite{nazer2011CF} and \cite{Engin12}. On the other hand, one major issue of lattices from Construction A is that the decoding complexity typically depends on decoding the underlying linear code. Hence, the decoding complexity can be large.

In \cite{huang13ITW} \cite{huang14}, motivated by the theory developed in \cite{Feng10}, we propose a novel multilevel lattice construction called Construction $\pi_A$ (previously called product construction) which breaks the underlying linear code into the Cartesian product of linear codes over small prime fields. Using the Chinese Remainder Theorem (CRT), we show the existence of ring homomorphisms. Moreover, we show that Construction $\pi_A$ can produce good lattices by decoding level by level so that the results in \cite{nazer2011CF} and \cite{Engin12} can be recovered by such lattices under multistage decoding, which substantially reduces the decoding complexity.

In this paper, we will first review the compute-and-forward paradigm and the algebraic structure behind it. We will then provide an overview of constructions of lattices from codes which are suitable for compute-and-forward. Particularly, we will review Construction A, Construction D, and Construction $\pi_A$. In the end, we will discuss two generalizations which enlarge the design space. Due to the space limitation, we do not provide background on lattices and abstract algebra. The reader is referred to \cite{erez05} and \cite{Hungerford74} for details.

\subsection{Notations}
Throughout the paper, we use $\mbb{N}$, $\mbb{R}$, and $\mbb{C}$ to represent the set of natural numbers, real numbers, and complex numbers, respectively. $\mbb{Z}$, $\Zi$, and $\Zw$ are the rings of integers, Gaussian integers, and Eisenstein integers, respectively. We use $\Pp(E)$ to denote the probability of the event $E$. Vectors and matrices are written in lowercase boldface and uppercase boldface, respectively. Random variables are written in Sans Serif font. We use $\times$ to denote the Cartesian product and use $\oplus$ and $\odot$ to denote the addition and multiplication operations, respectively, over a ring.

\section{Problem Statement and the Compute-and-Forward Paradigm}
In this paper, we consider the compute-and-forward network first studied by Nazer and Gastpar \cite{nazer2011CF}. There are $K$ source node and $M$ destination node and the graph is fully connected with a channel coefficient $h_{mk}\in\mbb{C}$ associated with the edge from source node $k$ to destination node $m$ as shown in Fig.~\ref{fig:CF_model}. The source node $k$ encodes its message $\mathbf{w}_k\in\mbb{F}_p^{n}$ to form a codeword $\mathbf{x}_k\in\mbb{C}^N$ which satisfies the average power constraint $\mbb{E}[\msf{X}^2]\leq P$.

The received signal at the destination node $m$ is given by
\begin{equation}\label{eqn:y_m}
    \mathbf{y}_m = \sum_{k=1}^K h_{mk}\mathbf{x}_k + \mathbf{z}_m,
\end{equation}
where $\mathbf{z}_m\sim\mc{CN}(\mathbf{0},\mathbf{I})$.

\begin{figure}
    \centering
    \includegraphics[width=2.in]{CF_model}
    \caption{A compute-and-forward relay network where $S_1,\ldots,S_K$ are source nodes and $D_1,\ldots,D_M$ are destination nodes.}
    \label{fig:CF_model}
\end{figure}

Instead of individual messages, each destination node is only interested in computing a function of messages
\begin{equation}
    \mathbf{u}_m = f_m(\mathbf{w}_1, \ldots, \mathbf{w}_K).
\end{equation}

One can think of this network model as a part of a larger network in which the destination nodes are merely relay nodes. Then computing and forwarding functions at those relay nodes mimics the behavior of random linear network coding.

In \cite{nazer2011CF}, Nazer and Gastpar proposed a novel paradigm called compute-and-forward which exploits the algebraic structure of lattices. In their framework, each source node encodes its message by an identical nested lattice code $(\Lambda_f,\Lambda_c)$ \cite{erez04}. The transmitted signal at the source node $k$ is given by
\begin{equation}
    \mathbf{x}_k = (\mathbf{t}_k -\mathbf{u}_k) \mod \Lambda_c,
\end{equation}
where $\mathbf{t}_k$ is the lattice codeword corresponding to the message $\mathbf{w}_k$ and $\mathbf{u}_k$ is a random dither.

According to the channel parameters, the destination node $m$ computes a linear combination of transmitted signals with coefficients being integers $\mathbf{a}_m=[a_{m1},\ldots,a_{mK}]$ by quantizing the following signal to the nearest lattice point in $\Lambda_f$
\begin{align}\label{eqn:NG_y}
    \mathbf{y}'_m &= \left(\alpha_m\mathbf{y}_m + \sum_{k=1}^K a_{mk}\mathbf{u}_k\right) \mod \Lambda_c \nonumber \\
    &= (\mathbf{t}_{eq,m} + \mathbf{z}_{eq,m}) \mod \Lambda_c,
\end{align}
where
\begin{equation}\label{eqn:NG_t_eq}
    \mathbf{t}_{eq,m}= \sum_{k=1}^K a_{mk}\mathbf{t}_{mk} \mod \Lambda_c,
\end{equation}
is again a lattice codeword in $(\Lambda_f,\Lambda_c)$ and
\begin{equation}\label{eqn:NG_z_eq}
    \mathbf{z}_{eq,m} = \left(\alpha_m\mathbf{z}_m + \sum_{k=1}^K (\alpha_m h_{mk}-a_{mk})\mathbf{x}_k\right),
\end{equation}
is the effective noise. A version of the decoded lattice codeword $\mathbf{t}_{eq,m}$ is then mapped to the following function via $\sigma$
\begin{equation}\label{eqn:u_NG}
    \mathbf{u}_m = b_{m1} \mathbf{w}_1\oplus\ldots\oplus b_{mK} \mathbf{w}_K,
\end{equation}
where $b_{mk}\defeq \sigma(a_{mk})\in\mbb{F}_{p}$.

It is shown in \cite{nazer2011CF} that by choosing $\alpha_m$ to be the MMSE estimator, the following computation rate is achievable
\begin{equation}\label{eqn:com_rate_m}
        R(\mathbf{h}_m,\mathbf{a}_m) = \log^+\left(\left(\|\mathbf{a}_m\|^2-\frac{P|\mathbf{h}_m^*\mathbf{a}_m|^2}{1+P\|\mathbf{h}_m\|^2}\right)^{-1}\right).
    \end{equation}
where $\log^+(.)\defeq \max\{0,\log(.)\}$.

It has been shown by Feng \textit{et al.} \cite{Feng10} that the key to relate $\mathbf{t}_{eq,m}$ a linear integer combination of codewords to $\mathbf{u}_m$ a linear combination of messages is to choose the mapping $\sigma:\mbb{Z}\rightarrow \mbb{F}_p$ a ring homomorphism and the mapping adopted in \cite{nazer2011CF} happens to be one.

\section{Some Known Constructions from Codes}
In this section, we review some known lattice constructions from codes that are suitable for compute-and-forward. i.e., constructions from codes that possess the desired homomorphisms for exploiting the structural gains offered by the channels.

\subsection{Construction A Lattices}
We review the Construction A lattices over $\mbb{Z}$ and discuss some properties of such lattices and some related constructions. A depiction of Construction A can be found in Fig.~\ref{fig:const_A_Z}.

\begin{figure}
    \centering
    \includegraphics[width=2.5in]{const_A_Z}
    \caption{Construction A.}
    \label{fig:const_A_Z}
\end{figure}

{\bf \underline{Construction A}} \cite{LeechSloane71} \cite{conway1999sphere} Let $p$ be a prime. Let $n$, $N$ be integers such that $n\leq N$ and let $\mathbf{G}$ be a generator matrix of an $(N,n)$ linear code over $\mbb{F}_p$. Construction A consists of the following steps:
\begin{enumerate}
    \item Define the discrete codebook $C=\{\mathbf{x}=\mathbf{G}\odot\mathbf{w}:\mathbf{w}\in\mbb{F}_p^n\}$ where all operations are over $\mbb{F}_p$.
    \item Construct $\Lambda^*\defeq \mc{M}(C)$ where $\mc{M}:\mbb{F}_p\rightarrow \mbb{Z}/p\mbb{Z}$ is a ring isomorphism. (For $\mbb{Z}$, the natural mapping suffices.)
    \item Tile $\Lambda^*$ to the entire $\mbb{R}^N$ to form $\Lambda_{\text{A}}\defeq \Lambda^* + p\mbb{Z}$.
\end{enumerate}
Note that the existence of the ring isomorphism in step 2) is guaranteed since $p\mbb{Z}$ is a maximal ideal. It can be shown that a real vector $\boldsymbol\lambda$ belongs to $\Lambda_{\text{A}}$ if and only if $\sigma(\boldsymbol\lambda)\in C$ where $\sigma\defeq \mc{M}^{-1}\circ\hspace{-3pt}\mod p\mbb{Z}$ is a ring homomorphism.

After a long pursuit by pioneers like de Buda, Poltyrev, Loeliger, Forney, Rimoldi, Urbanke, and etc., Erez and Zamir in 2004 finally showed that lattice codes constructed from Construction A can achieve the AWGN capacity under lattice decoding (see \cite{erez04} and the reference therein) as $p\rightarrow\infty$. Such lattice codes are particularly suitable for compute-and-forward as after decoding the fine lattice point, one can use the ring homomorphism $\sigma$ to obtain the corresponding linear combination of messages over $\mbb{F}_p$.

Extensions of Construction A to other PIDs such as Gaussian integers $\Zi$ and Eisenstein integers $\Zw$ are possible \cite{conway1999sphere}. In \cite{Engin12}, following \cite{erez05}, Tunali $\textit{et al.}$ showed the goodness of Construction A lattices over $\Zw$. Motivating by the fact that $\Zw$ quantizes the complex field better than $\Zi$ does, they then used lattice codes generated from Construction A over $\Zw$ for compute-and-forward. Constructing practical ensembles of lattices from Construction A is also an active research area. Building upon non-binary low-density parity check (LDPC) codes, di Pietro \textit{et al.} \cite{diPietro12} (and Tunali $\textit{et al.}$ \cite{Engin12} as well) propose the low-density A (LDA) lattice ensemble from Construction A and show that such lattices can achieve the Poltyrev-limit under maximal likelihood decoding \cite{diPietro13}. Tunali $\textit{et al.}$ in \cite{Engin13ITW} further replace LDPC codes by spatially-coupled LDPC codes and present a BP-threshold of 0.19 dB from the Poltyrev-limit at a block length of $1.29\times 10^6$.

\subsection{Construction D Lattices}
We now consider the Construction D lattices \cite{BarnesSloane83} \cite[Page 232]{conway1999sphere}. Let $C^1 \subseteq C^2 \subseteq  \ldots \subseteq C^{L+1}$ be a sequence of nested linear codes over $\mbb{F}_p$ where $C^{L+1}$ is the trivial $(N,N)$-code and $C^l$ is a $(N,n^l)$-code for $l\in\{1,2,\ldots r\}$ with $n^1 \leq \ldots \leq n^r$. The codes are guaranteed to be nested by choosing $\{ \mathbf{g}_1,\ldots,\mathbf{g}_N \}$ which spans $C^{L+1}$ and then using the first $n^l$ vectors $\{ \mathbf{g}_1,\ldots,\mathbf{g}_{n^l} \}$ to generate $C^l$. We are now ready to state Construction D of lattices.

{\bf \underline{Construction D}} A lattice $\Lambda_{\text{D}}$ generated by Construction D with $L+1$ level is given as follows.
\begin{equation}
    \Lambda_{\text{D}} = \bigcup \left\{ p^L \mbb{Z}^N + \sum_{1\leq l \leq L} p^{l-1} \sum_{1\leq i \leq n^l} a_{li} \mathbf{g}_i |a_{li}\in\mbb{F}_p \right\},
\end{equation}
where all the operations are over $\mbb{R}^N$. Similar to Construction A, extensions of Construction D to other PIDs such as $\Zi$ and $\Zw$ are possible.

It was shown by Forney \cite{forney2000} that Construction D lattices with any fixed $p$ and sufficiently large $L$ can achieve the Poltyrev-limit under multistage decoding. Thus, one can choose $p=2$ and always work with the binary field. Therefore, in general, the decoding complexity of Construction D lattices is much smaller than that of Construction A lattices. There have been several attempts to construct practical ensemble of lattices from Construction D. In \cite{sakzad10}, Sakzad \textit{et al.} proposed the turbo lattices from Construction D together with turbo codes. Although no theoretical proofs showing the ability of achieving the Poltyrev-limit, simulation results reported that turbo lattices can approach the Poltyrev-limit to within 0.5 dB at $p_e=10^{-5}$ with the code length roughly 10000. In \cite{YanLingWu13}, Yan \textit{et al.} constructed sequences of nested polar codes and used them in conjunction with Construction D to generate polar lattices. Similar to the linear code counterpart (i.e., the polar codes), such lattices can be shown achieving the Poltyrev-limit and explicit constructions of good polar lattices are possible. Very recently, Vem \textit{et al.} in \cite{vem14} proposed a means to construct sequences of nested spatially-coupled LDPC codes and adopted Construction D to construct the so-called spatially-coupled LDPC lattices. This ensemble of lattices is shown to achieve the Poltyrev-limit under \textit{belief propagation decoding}.

To use Construction D lattices for compute-and-forward, there are some challenges that need to be conquered. First of all, to the best of our knowledge, there is no proof showing that Construction D can produce lattices that are good for MSE quantization. Therefore, efficient shaping techniques are called for. Secondly, unlike Construction A lattices, mapping linear integer combinations of lattice points to linear combinations of codewords over finite field is not an easy task. Hence, lattices from Construction D may not be straightforwardly applied to compute-and-forward if one insists on coding over finite field. On the other hand, if we are allowed to work over a finite-chain-ring, the second issue can be circumvented as Construction D lattices can be deemed as Construction A lattices with linear codes over finite-chain-rings \cite[Proposition 2]{feng11rings} and one can relate integer linear combinations of lattice points to linear combinations of codewords over finite-chain-rings. But then one has to pay extra attention to zero divisors.

\subsection{Construction $\pi_A$ Lattices}\label{sec:const_pi_A}
Motivated by the problems occurring when using Construction A and D lattices for compute-and-forward, the authors proposed a novel lattice construction called Construction $\pi_A$ \cite{huang13ITW} \cite{huang14} shown in Fig.~\ref{fig:lattice_const}. This construction is built upon the algebraic foundation established by Feng \textit{et al.} \cite{Feng10}.

\textbf{\underline{Construction $\pi_A$}} Let $p_1, p_2,\ldots, p_L$ be primes which are relatively prime. Let $n^l$, $N$ be integers such that $n^l\leq N$ and let $\mathbf{G}^l$ be a generator matrix of an $(N,n^l)$ linear code over $\mbb{F}_{p_l}$ for $l\in\{1,\ldots,L\}$. Construction $\pi_A$ consists of the following steps,

\begin{enumerate}
    \item Define the discrete codebooks $C^l=\{\mathbf{x}=\mathbf{G}^l\odot\mathbf{w}^l:\mathbf{w}^l\in\mbb{F}_{p_l}^{n^l}\}$ for $l\in\{1,\ldots,L\}$.
    \item Construct $\Lambda^* \defeq \mc{M}(C^1,\ldots,C^L)$ where $\mc{M}:\times_{l=1}^L \mbb{F}_{p_l}\rightarrow \mbb{Z}/\Pi_{l=1}^L p_l \mbb{Z}$ is a ring isomorphism.
    \item Tile $\Lambda^*$ to the entire $\mbb{R}^N$ to form $\Lambda_{\pi_A} \triangleq  \Lambda^* + \Pi_{l=1}^L p_l \mbb{Z}^N$.
\end{enumerate}
\begin{figure}
    \centering
    \includegraphics[width=2.5in]{lattice_const_Z}
    \caption{Construction $\pi_A$.}
    \label{fig:lattice_const}
\end{figure}
Note that the existence of the ring isomorphism in step 2) is guaranteed by CRT. It can be shown that a real vector $\boldsymbol\lambda$ belongs to $\Lambda_{\pi_A}$ if and only if $\sigma(\boldsymbol\lambda)\in C^1\times\ldots\times C^L$ where $\sigma\defeq \mc{M}^{-1}\circ\hspace{-3pt}\mod \Pi_{l=1}^L p_l\mbb{Z}$ is a ring homomorphism.

It has been shown that Construction $\pi_A$ is able to generate lattices that are simultaneously good for MSE quantization and Poltyrev good under multistage decoding \cite{huang14}. This means that the complexity of such lattices is only dominated by decoding the linear code whose field size is equal to the largest prime $\max_l p_l$ in the prime factorization rather than $\Pi_{l=1}^L p_l$. Unlike Construction A letting $p$ tend to infinity and Construction D letting $L$ tend to infinity, Construction $\pi_A$ let $\Pi_{l=1}^L p_l$ tend to infinity and allows one to play with these parameters. Moreover, in Construction $\pi_A$, the linear code in each level does not have to be nested in other linear codes; hence, the rate allocation is much easier than Construction D.

We further apply the Construction $\pi_A$ lattices to compute-and-forward and proposed the \textit{multistage} compute-and-forward scheme. The main enabler is to realize that any integer $a\in\mbb{Z}$ can be decomposed as $a = \mc{M}(b^1,\ldots,b^L)+\Pi_{l=1}^L p_l \tilde{a},$

where $\tilde{a}\in\mbb{Z}$ and $b^l\in\mbb{F}_{p_l}$ that can be obtained from $\sigma(a)$. i.e., any integer can be represented as its coordinate in $\times_{l=1}^L \mbb{F}_{p_l}$. The transmitter $k$ first splits its message into $L$ streams $\mathbf{w}_k^1,\ldots,\mathbf{w}_k^L$ where $\mathbf{w}_k^l\in\mbb{F}_{p_l}^{n^l}$. Each stream is then separately encoded by the linear code in that level. The encoder gathers all the coded streams and use $\mc{M}$ to map them to the constellation.

At the relay $m$, instead of \eqref{eqn:u_NG}, we opt to decode
\begin{equation}\label{eqn:u_MLCF}
    \mathbf{u}_m^l \defeq b_{m1}^l\odot \mathbf{w}_1^l \oplus\ldots\oplus b_{mK}^l\odot \mathbf{w}_K^l,
\end{equation}
for all $l\in\{1,\ldots,L\}$ level by level. In \cite{huang14}, we showed that the multistage compute-and-forward achieves the same computation rates as those in \cite{nazer2011CF} (see \eqref{eqn:com_rate_m} as well) with multistage decoding, which substantially decreases the decoding complexity.

\section{Generalizations}\label{sec:general}
In this section, we generalize the above lattice constructions in the following two aspects.

The first generalization discussed in this section is a novel lattice construction called Construction $\pi_D$. This construction is a direct consequence of CRT and subsumes Construction A, Construction D, and Construction $\pi_A$ as special cases. This will substantially expand the design space. Another thing one may have noticed is that all the lattices constructed so far are over PIDs such as $\mbb{Z}$, $\Zi$, and $\Zw$. Mathematicians have known how to construct lattices over other commutative rings for a long time (see for example \cite{boutros96} \cite{Kosit} and reference therein). The second generalization is to go beyond PIDs and allow one to build lattices over rings of algebraic integers. This will result in increased computation rates for some channel realizations.

\subsection{Construction $\pi_D$}\label{sec:pi_D}
Let $q\in\mbb{N}$ be any natural number whose prime factorization is given by $q=\Pi_{l=1}^L p_l^{e_l}$. From CRT, there exists a ring isomorphism $\mc{M}:\times_{l=1}^L \mbb{Z}_{p_l^{e_l}}\rightarrow \mbb{Z}/ q \mbb{Z}$. Moreover, $\sigma\defeq \mc{M}^{-1}\circ \hspace{-3pt}\mod q\mbb{Z}$ is a ring homomorphism.

\textbf{\underline{Construction $\pi_D$}} Let $q\in\mbb{N}$ whose prime factorization is given by $q=\Pi_{l=1}^L p_l^{e_l}$. Let $n^l$, $N$ be integers such that $n^l\leq N$ and let $\mathbf{G}^l$ be a generator matrix of an $(N,n^l)$ linear code over $\mbb{Z}_{p_l^{e_l}}$ for $l\in\{1,\ldots,L\}$. Construction $\pi_D$ consists of the following steps,

\begin{enumerate}
    \item Define the discrete codebooks $C^l=\{\mathbf{x}=\mathbf{G}^l\odot\mathbf{w}^l:\mathbf{w}^l\in(\mbb{Z}_{p_l^{e_l}})^{n^l}\}$ for $l\in\{1,\ldots,L\}$.
    \item Construct $\Lambda^* \defeq \mc{M}(C^1,\ldots,C^L)$ where $\mc{M}:\times_{l=1}^L \mbb{Z}_{p_l^{e_l}}\rightarrow \mbb{Z}/ q \mbb{Z}$ is a ring isomorphism.
    \item Tile $\Lambda^*$ to the entire $\mbb{R}^N$ to form $\Lambda_{\pi_D} \triangleq  \Lambda^* + q \mbb{Z}^N$.
\end{enumerate}

Similar to $\Lambda_{\pi_A}$, it can be shown that a real vector $\boldsymbol\lambda$ belongs to $\Lambda_{\pi_D}$ if and only if $\sigma(\boldsymbol\lambda)\in C^1\times\ldots\times C^L$ where $\sigma\defeq \mc{M}^{-1}\circ\hspace{-3pt}\mod q\mbb{Z}$ is a ring homomorphism.

Note that when setting $L=1$ and $e_1=1$, Construction $\pi_D$ reduces to Construction A over a finite field $\mbb{F}_{p_1}$. Setting $L=1$ makes it Construction A over a finite-chain-ring $\mbb{Z}_{p_1^{e_1}}$, which subsumes Construction D as a special case. Finally, when setting $e_1=\ldots=e_L=1$, we obtain Construction $\pi_A$. Hence, Construction $\pi_D$ is a general means of constructing lattices from codes and contains Construction A, Construction D, and Construction $\pi_A$ as special cases. Moreover, in Construction $\pi_D$, $q$ can take any natural number regardless its prime factorization. Thus, the proposed construction substantially expands the design space and further eases the rate allocation problem.

To show the ability to produce Poltyrev good lattices, for the proposed construction, one can follow the proof in \cite{huang14} with a careful treatment to those levels with $e_l\neq 1$. One option is to use Construction D for those levels, i.e., one uses a sequence of $e_l$ nested linear codes to construct a linear code over $\mbb{Z}_{p_l^{e_l}}$. Another option is to adopt a capacity-achieving linear code over $\mbb{Z}_{p_l^{e_l}}$ proposed in \cite{HitronErez12} at the $l$th level. On the other hand, for the goodness for MSE quantization, the proposed construction may suffer the same fate as Construction D unless we enforce $e_1=\ldots=e_L=1$ (Construction $\pi_A$).

\subsection{Lattices over Algebraic Integers}\label{sec:algebraic}
We particularly look at constructing lattices over rings of algebraic integers with degree 2, namely the quadratic integers. The reasons that we pick such rings are twofold. First of all, the channel coefficients we are trying to quantize lie in $\mbb{C}$, which is an extension field of $\mbb{R}$ with degree 2. Hence, it makes perfect sense to first investigate extensions with degree 2. Secondly, quadratic fields have been extensively studied and many properties have been discovered. This makes the generalization a lot easier. Please consult \cite{lang94} for background knowledge on algebraic number theory.

In a nutshell, a number field $\mbb{K}$ is a finite extension of $\mbb{Q}$ and its ring of integers is $\mfk{O}_{\mbb{K}}=\mbb{K}\cap\mbb{A}$ where $\mbb{A}$ is the ring of all algebraic integers. Any quadratic field can be expressed as $\mbb{Q}(\sqrt{d})$ with $0,1\neq d\in\mbb{Z}$ square-free. Its ring of integers is $\Ok=\mbb{Z}[\xi]$ where
\begin{equation}\label{eqn:zbasis}
        \xi = \left\{\begin{array}{ll}
        \sqrt{d},                                           & d\equiv 2,3\mod 4, \\
        \frac{1+\sqrt{d}}{2},                                    & d\equiv 1\mod 4.\\
        \end{array} \right.
\end{equation}
Note that when $d=-1$ and $d=-3$, we have $\Zi$ and $\Zw$, respectively. Not every $\mbb{Z}[\xi]$ forms a PID. In fact, for imaginary quadratic fields, there are exactly 9 of these are PIDs, which correspond to $d\in\{-1,-2,-3,-7,-11,-19,-43,-67,-163\}$. Fortunately, for such rings, there is a systematic way to identify prime ideals. Moreover, every prime ideal $\mfk{p}\in\Ok$ lies above $p$ is maximal in $\Ok$; hence, we still have the property that $\Ok/\mfk{p}\cong \mbb{F}_{p^f}$ where $f$ is the inertial degree.

\begin{example}\vspace{-5pt}
    Consider $\mbb{Q}[\sqrt{-15}]$ whose ring of integers is $\Ok=\mbb{Z}[\xi]$ with $\xi = \frac{1+\sqrt{-15}}{2}$. This is not a PID. One can show that $17\Ok$ splits into two prime ideals, namely $17\Ok = \mfk{p}\bar{\mfk{p}}$ where $\mfk{p}=(17,6+\sqrt{-15})$. Moreover, we have $\Ok/\mfk{p}\cong\mbb{F}_{17}$. In Fig.~\ref{fig:Z_15_homo}, we show the coset decomposition and the corresponding ring isomorphism.

    \begin{figure}
    \centering
    \includegraphics[width=2.5in]{Z_15_homo}
    \vspace{-15pt}
    \caption{Coset decomposition of $\Ok/\mfk{p}$ and the corresponding ring isomorphism $\mc{M}:\mbb{F}_{17}\rightarrow\Ok/\mfk{p}$.}
    \label{fig:Z_15_homo}
    \vspace{-15pt}
\end{figure}
\end{example}
\vspace{-5pt}
In what follows, we only present Construction A over $\Ok$ but its extensions to other constructions are possible.

{\bf \underline{Construction A over $\Ok$}} Let $n$, $N$ be integers such that $n\leq N$ and let $\mathbf{G}$ be a generator matrix of an $(N,n)$ linear code over $\mbb{F}_{p^f}$. Construction A over $\Ok$ consists of the following steps:
\begin{enumerate}
    \item Define the discrete codebook $C=\{\mathbf{x}=\mathbf{G}\odot\mathbf{y}:\mathbf{y}\in\mbb{F}_{p^f}^n\}$ where all operations are over $\mbb{F}_{p^f}$.
    \item Construct $\Lambda^*\defeq \mc{M}(C)$ where $\mc{M}:\mbb{F}_{p^f}\rightarrow \Ok/\mfk{p}$ is a ring isomorphism.
    \item Tile $\Lambda^*$ to the entire $\mbb{C}^N$ to form $\Lambda\defeq \Lambda^* + \mfk{p}^N$.
\end{enumerate}

We expect to show the goodness of such lattices and to benefit from it in the scenario where we have feedback from destination nodes by letting source nodes to choose the best ring of integers to work with. This framework can also be incorporated with the phase precoded approach in \cite{sakzad14} to further improve the performance.

\vspace{-5pt}
\bibliographystyle{ieeetr}
\bibliography{journal_abbr,prod}

\end{document}


TITLE: Finding the explicit sequence given the generating func $g(x) =\Sigma^\infty_{n=0}b_nx^n = \frac{1}{(1-x)^2(1-x^2)}$
QUESTION [0 upvotes]: I have the generating function $g(x) = \Sigma^\infty_{n=0}b_nx^n = \frac{1}{(1-x)^2(1-x^2)}$ and I'm asked to find the explicit formula for the sequence. After I split the fraction into two sums and reverted each sum into a summation expression, I could not figure out how to continue because the expression seemed tricky.
After I looked at the answer, the author took a different approach by saying that the expression can be rewritten as $\frac{1}{1-x}\cdot \frac{1}{1-x}\cdot \frac{1}{1-x^2}$, which equals $(\Sigma^\infty_{a=0}x^a)\cdot(\Sigma^\infty_{b=0}x^b)\cdot(\Sigma^\infty_{c=0}x^{2c})$, which would count all non-negative integer solutions for the equation $a + b + 2c = n$.
He then says that since $c \leq \lfloor n/2 \rfloor$, we it also equals to the amount of solutions for $a + b = n - 2k + 1$.
My problem is that then he says that now we can count all the solutions for the pairs $(a,b)$ which solve for the above, $\forall k\in \{0, 1, 2, \ldots, \lfloor n/2 \rfloor\}$, and the expression he uses to represent that is:
$$ \Sigma^{\lfloor n/2 \rfloor}_{k = 0} (n -2k + 1)$$
At first I didn't understand why the answer is this arithmetic sequence. I knew that the amount of different non-negative integer pairs $(a,b)$ such that $a+b = n$ is $\binom{n + 2 - 1}{2 - 1} = \binom{n + 1}{1}$, so put in our example I got:
$$\Sigma^{\lfloor n/2 \rfloor}_{k=0}\binom{n - 2k + 1 + 2 }{2 - 1} =
\Sigma^{\lfloor n/2 \rfloor}_{k=0}\binom{n - 2k + 2}{1}
=\Sigma^{\lfloor n/2 \rfloor}_{k=0}(n - 2k + 2)$$
The two don't match up.

REPLY [1 votes]: While this combinatorial approach is perfectly good, there's a standard approach based on the partial fraction decomposition
$$
\frac1{(1 - x)^2 (1 - x^2)} = \frac{1}{8 (1+x)}+\frac{1}{8 (1-x)}+\frac{1}{4 (1-x)^2}+\frac{1}{2 (1-x)^3}.
$$
The point is that each of the terms resulting from partial fractions (fortunately there are no irreducible quadratics here) have standard Taylor series:
\begin{align*}
\frac{1}{1+x} &= \sum_{n=0}^\infty (-1)^n x^n \\
\frac{1}{1-x} &= \sum_{n=0}^\infty x^n \\
\frac{1}{(1-x)^2} &= \sum_{n=0}^\infty (n+1) x^n \\
\frac{1}{(1-x)^3} &= \sum_{n=0}^\infty \frac{(n+2)(n+1)}2 x^n.
\end{align*}
Therefore
\begin{align*}
\frac1{(1 - x)^2 (1 - x^2)} &= \frac18 \sum_{n=0}^\infty (-1)^n x^n + \frac18 \sum_{n=0}^\infty x^n + \frac14 \sum_{n=0}^\infty (n+1) x^n + \frac12 \sum_{n=0}^\infty \frac{(n+2)(n+1)}2 x^n \\
&= \sum_{n=1}^\infty \frac{2 n^2+8 n+7+(-1)^n}8 x^n,
\end{align*}
and therefore
$$
b_n = \frac{2 n^2+8 n+7+(-1)^n}8.
$$


TITLE: number of galois extensions of local fields of fixed degree
QUESTION [5 upvotes]: Let $K$ be a local field (of characteristic 0) with (finite) residue field of characteristic $l$ and let $p$ be a prime.
Considering the cases, whether the $p$-th roots of unity are in $K$ and whether $l$ equals $p$ (and maybe whether $p=2$) or not, my question is:
How many Galois extensions of $K$ of degree $p$ exist?

REPLY [12 votes]: I am sorry if I see this question only now, but since no one gave the following answer, it seems worth posting it.
There is a general formula for the number of extensions of degree $d$ of a $p$-adic field $K$ contained inside a fixed algebraic closure $\overline{K}$, which is given by
$$
\# \{ L \mid K \subseteq L \subseteq \overline{K}, \, [L \colon K] = d \} = \sigma(h) \cdot \sum_{j = 0}^m \frac{p^{m+j+1} - p^{2j}}{p - 1} \cdot (p^{\varepsilon_p(j) \cdot d \cdot d_0} - p^{\varepsilon_p(j - 1) \cdot d \cdot d_0})
$$
where:

$\sigma$ denotes the sum of divisors function;
$h, m \in \mathbb{N}$ are the unique natural numbers such that $p \nmid h$ and $d = h \cdot p^m$;
$\varepsilon_p(j) := \sum_{k=1}^j p^{-k}$ if $j \geq 1$, $\varepsilon_p(0) := 0$ and $\varepsilon_p(-1) := -\infty$, i.e. $p^{\varepsilon_p(-1) \cdot d} = 0$. In particular, $p^{\varepsilon_p(j) \cdot d} \in \mathbb{N}$ if $-1 \leq j \leq m$;
$d_0 := [K \colon \mathbb{Q}_p]$.

This formula is due to Krasner, and has been proved in the paper "Nombre des extensions d'un degré donné d'un corps $\mathfrak{p}$-adique". The proof uses the same analytic techniques that go into the proof of the (much more famous) Krasner lemma.
Observe that this number is different from the number of $K$-isomorphism classes of extensions of $K$ having a given degree. This is of course due to the presence of non-Galois extensions. Here are two examples of this phenomenon:

if $q \neq p$ is a prime then there are $q + 1$ fields $K \subseteq L \subseteq \overline{K}$ having degree $[L \colon K] = q$, but there are only two isomorphism classes of these fields: one containing the only unramified extension, and the other containing the tamely and totally ramified extensions;
if $p \geq 3$ there are $1 + p + (p^2 - p) \cdot p$ extensions $\mathbb{Q}_p \subseteq L \subseteq \overline{\mathbb{Q}_p}$ such that $[L \colon \mathbb{Q}_p] = p$, but they form $1 + p + p^2 - p = p^2 + 1$ isomorphism classes. $p + 1$ of these contain a unique extension (which is Galois over $\mathbb{Q}_p$) and every other isomorphism class contains $p$ extensions (see for example Proposition 2.3.1 in the paper "A database of local fields" by Jones and Roberts).

Finally, let me remark that this formula is related to Serre's "mass formula", which is valid in any characteristic. This formula says that a certain "count" of totally ramified extensions of a local, non-Archimedean field $K$ of degree $d$ is equal to $d$. More precisely,
$$
\sum_{L \in \Sigma_d} (\# \kappa)^{d - 1 - \mathrm{v}_K(\mathrm{disc}(L/K))} = d
$$
where $\Sigma_d$ denotes the set of totally ramified extensions of $K$ which have degree $d$, and $\kappa$ is the residue field of $K$. Observe that if $p \nmid d$ then the formula can be written simply as $\# \Sigma_d = d$.
Two useful references for this are:

Serre's original paper "Une 'formule de masse' pour les extensions totalement ramifiées de degré donné d'un corps local";
Krasner's paper "Remarques au sujet d'une note de J.-P. Serre...", in which he reproves the formula using his methods.


TITLE: Convex, bounded and closed on the strong topology $\Rightarrow$ compact on the weak topology
QUESTION [1 upvotes]: The question reads like this:

Let $X$ be a reflexive Banach space and $K \subset X$ a set.
i) Given $r > 0$ define the application $T_r: X \rightarrow X$ as
$T(x) = rx$. Show that $T_r$ is continuous considering in $X$ the weak
topology in the domain and the counter-domain.
ii) Show that if $K$ is convex, bounded and closed in the strong
topology, then $K$ is compact on the weak topology.

For the item i) i used that a linear application between Banach spaces is continuous when both spaces use the weak topology if and only if it's continuous when both use the strong topology. Since $T_r$ is bounded on the strong topology, it is continuous on it, and thus continuous on the weak topology.
I don't get how this should help with the item ii).

REPLY [1 votes]: Continuous functions map compact sets to compact sets. So i), together with Banach-Alaoglu, shows that all balls centered at $0$ are compact.
Being bounded, $K$ is inside a ball. Being convex and closed, it is weakly closed. A closed subset of a compact set, in a Hausdorff space, is compact.
Also, you don't really need any theory for i). If $x_n\to x$ weakly, this means that $f(x_n)\to f(x)$ for all $f\in X^*$. Now
$$
f(T_rx_n)=f(rx_n)=rf(x_n)\to rf(x)=f(rx)=f(T_rx),\qquad f\in X^*.
$$
So $T_rx_n\to T_rx$ weakly and $T_r$ is continuous (note that one is working with nets here, but nothing changes in the argument).


TITLE: A fair coin is continually flipped until heads appears for the 10th time. Find the number of expected tails
QUESTION [3 upvotes]: A fair coin is continually flipped until heads appears for the 10th time. Find the number of  expected tails.
Im very lost in this problem, can someone help? I think I have to use neg binomial, but not sure, any help will be appreciated!

REPLY [2 votes]: GrahamKemp, Could you expand on that a bit? I didn't understand the part about the variables having a geometric distribution. – shardulc

Sure.   By definition: a (zero-based) geometric random variable is a count of failures before the first success in an indefinite sequence of iid Bernoulli trials.   So if a fair coin is flipped indefinitely, the count of tails before the first head has a Geometric$_0(1/2)$ Distribution.   And so too does the count of tails between the first and second head, and so on.
Let $T_1$ be the count of tails before the first head, and $T_k$ the count of tails between the $k-1$ and $k$-th heads.
$$T_k~\sim~\mathcal{Geo}_0(1/2)~\iff~ \mathsf P({T_k}=t)~=~\tfrac {1}{2}(1-\tfrac 12)^{t}~=~(\tfrac 1 2)^{t+1}$$
The expectation of such a random variable is $$\begin{align}\mathsf E(T_k)~=~&\tfrac{1-\tfrac 12}{\tfrac 12}\\[1ex]~=~&1\end{align}$$
Now if we count tails until the first head, then repeat times ten, we have counted of tails until the tenth head.   Thus this is a sum of the ten iid geometric random variables.  $~T~=~\sum_{k=1}^{10}T_k$
Hence by the Linearity of Expectation the expected count of tails before the tenth head is: $$\begin{align}\mathsf E(T)~=~&\sum_{n=1}^{10}\mathsf E(T_k)\\[1ex]~=~&10\end{align}$$
That is all.
$\Box$


TITLE: Possibility of positive definite matrix
QUESTION [1 upvotes]: For the variables $s\in\mathbb R, s > 0$, the vector $v\in\mathbb R^n$, and the symmetric positive definite matrix $M \in \mathbb R^{n \times n}$, are there cases in which
\begin{align}
\frac{1}{s^2} \left( v v^T - s M \right)
\end{align}
becomes positive definite?

I am aware that $v\cdot v^T$ is always positive definite, so I did (with an arbitrary vector $u\in\mathbb R^n$)
\begin{align}
u^T \cdot \frac{v\cdot v^T - M\cdot s}{s^2} \cdot u \overset!> 0 \\
\Leftrightarrow
u^T \cdot M \cdot u < u^T \cdot \frac{v\cdot v^T}{s} \cdot u
\end{align}
where the right side would be always positive for any $u$.
For background information: $s$ is the value of a function at a specific position, $v$ the gradient at that position of that function and $M$ the respective Hessian.

REPLY [2 votes]: If $n=1$, the answer is obviously yes. Just choose $s$ small enough. Otherwise it's no. To see this, choose any $w$ which is perpendicular to $v$. If your  matrix is $A$, then $w^TAw = -\frac 1{s}w^TMw < 0$.


TITLE: Infimum upper bound
QUESTION [1 upvotes]: Let $h:[0,1]\to[0,1]$ be a $\mathcal{C^1}$ function such that $h'(x)<0$ for all $x\in(0,1)$. I am trying to show that (not sure if it is true):
$$
\inf_{f\in \mathcal{H}}\left(\int_0^1\int_0^1 h(|x-y|)(f(x)-f(y))^2dxdy\right) < 2\int_0^1 h(x)dx
$$
where $\mathcal{H} = \left\{f\in L^2([0,1]) : \int_0^1 f(t)dt = 0 \text{ and } \int_0^1 f^2(t)dt = 1\right\}$.

REPLY [0 votes]: Based on the previous comment, it is enough to find a function $f\in \mathcal{H}$ such that
$$
\int\int_{|x-y| < u} (f(x)-f(y))^2 dxdy < 2u
$$
for almost every $u\in (0,1)$.