TITLE: Why is this not a triangulation of the torus?
QUESTION [5 upvotes]: I refer to example 4, fig.3.6, p.17 of Munkres' Algebraic Topology. He says the given triangulation scheme "does more than paste opposite edges together".
Not clear to me. For those who don't have the book to hand, a rectangle is divided into 6 equal squares by a horizontal midline and two verticals; each square has a south-west to north-east diagonal.

REPLY [1 votes]: Paste the top and bottom edges first to get a cylinder.
Look at the circle on one end. One half of the circle is identified with the other half as each is da. So collapse that circle down to a line. Now do the same at the other end.
Looks like a toothpaste tube with two bottoms and no top.
Now identify the two ad ends. You get a torus with one circle circle on it collapsed to a segment. Looks like this: https://mathcurve.com/surfaces.gb/klein/toredeklein.shtml


TITLE: Demonstrate that the sequence is decreasing
QUESTION [2 upvotes]: $$\left( 1-\frac{1}{n+1}\right)^n$$
How do I demonstrate that the sequence decreases? I tried using the newton binomial but I end up with a terribly complicated expression.

REPLY [1 votes]: And because there's even more ways to do it:
Let $f(x)=\left(1-\frac{1}{x+1}\right)^x$ and show that $f(x)$ is decreasing by differentiating $\log f(x) = x \log\frac{x}{x+1}$.
We get
$$ \frac{d}{dx} \log f(x) = = \log\frac{x}{x+1} + x\left(\frac1x - \frac1{x+1}\right) = \log\left(1-\frac1{x+1}\right) + \frac1{x+1}  $$
which is negative for $x>0$ because $\log(1-\alpha)< -\alpha$ for $\alpha\in(0,1)$.
Therefore $\log f(x)$ decreases, and so does $f(x)$, and so does $f(n)$.


TITLE: Calculating angular acceleration when moment of inertia tensor is singular
QUESTION [2 upvotes]: I am attempting to simulate the motion of a rigid body composed of point masses in a 3D coordinate system. In doing so, I need to calculate the angular acceleration of the rigid body due to external torque as such
$$\boldsymbol{\alpha} = \mathbf{I}^\mathrm{-1} \boldsymbol{\tau}$$
where $\boldsymbol{\alpha}$ is the angular acceleration, $\boldsymbol{I}$ is the moment of inertia tensor, and $\boldsymbol{\tau}$ is torque in the body frame. However, when I compose a rigid body of two point masses, the moment of inertia tensor is rank-deficient and thus non-invertible. In this case, how would the angular acceleration be calculated? Would a pseudoinverse suffice?

REPLY [4 votes]: What you're describing can only happen if all the point masses are on a line, and there is a component of torque trying to spin them about that line. Well, if point masses are all on a line, then it is meaningless to ask how fast they are spinning about that axis. Classical point masses have no spatial extent: They are either moving or not moving; they cannot spin about their own axis. So the state where they are not spinning about this line is the exact same physical state as the state where they are spinning at 10000RPM about this line. The rotational velocity about this line is not measurable or meaningful.
Anyway, you should find that the component of $\alpha$ along a singular axis has no effect on the motion. Therefore, I expect that a pseudoinverse would work fine. (But I'm not sure.)


TITLE: Ado's theorem for metric Lie algebras?
QUESTION [13 upvotes]: Background
Ado's Theorem states that every finite-dimensional Lie algebra over a field of zero characteristic admits a faithful representation.
More precisely, if $\mathfrak{g}$ is a finite-dimensional Lie algebra over a field $K$ of zero characteristic, then there is a Lie algebra monomorphism $\rho: \mathfrak{g} \to \operatorname{End}(K^N)$ for some $N$, where $\operatorname{End}(K^N)$ is the Lie algebra of endomorphisms of $K^N$ relative to the commutator.
Now let $\mathfrak{g}$ be a finite-dimensional Lie algebra over $K$ and let $\langle-,-\rangle$ be an ad-invariant symmetric inner product; that is, a nondegenerate symmetric $K$-bilinear form such that for all $x,y,z \in \mathfrak{g}$,
$$\langle [x,y], z\rangle = \langle x,[y,z]\rangle.$$
We call such a Lie algebra a metric Lie algebra.
For example, $\operatorname{End}(K^N)$ itself is a metric Lie algebra, relative to the inner product
$$\langle X,Y \rangle := \operatorname{Tr}(XY),$$
for endomorphisms $X,Y$.
Semisimple and, more generally, reductive Lie algebras are metric, but there are others.  The relevant structure theorem is due to Medina and Revoy (MathSciNet link).
A final definition, added after Victor's comment below, is the following.   Given two metric Lie algebras, the orthogonal direct sum of the underlying vector spaces can again be given the structure of a metric Lie algebra, in which the original Lie algebras sit as orthogonal ideals.  This gives rise to the notion of an indecomposable metric Lie algebra as one which is not isomorphic (as metric Lie algebra) to the direct product of orthogonal (nonzero) ideals.
The following question is motivated by trying to construct Chern-Simons forms for Lie groups admitting a bi-invariant metric.  But this motivation aside, I think the question is natural.
Question

Does every (finite-dimensional) indecomposable metric
Lie algebra admit a faithful representation
$$\rho: \mathfrak{g} \to \operatorname{End}(K^N),$$
for some $N$, such that for all $x,y\in\mathfrak{g}$,
$$\langle x,y \rangle = c \operatorname{Tr}(\rho(x)\rho(y)),$$
for some nonzero $c \in K$?

REPLY [0 votes]: Given $\mathfrak{g}$, a necessary and sufficient condition for the existence of a single finite-dimensional representation whose trace form defines a non-degenerate bilinear form on the Lie algebra, is that $\mathfrak{g}$ is reductive.
And indeed there are many non-reductive Lie algebras with a symmetric invariant bilinear form. For instance, for every Lie algebra $\mathfrak{h}$, the semidirect product $\mathfrak{h}\ltimes\mathfrak{h}^*$ (with $\mathfrak{h}^*$ abelian, action being the coadjoint representation) admits such a form, for which both $\mathfrak{h}$ and $\mathfrak{h}^*$ are isotropic subspaces and the bilinear form is induced by the dual pairing.
Besides, for a general reductive Lie algebra $\mathfrak{g}$, not every non-degenerate bilinear form is a pull-back of the trace form of a representation.
For instance, if $\mathfrak{g}$ is semisimple and nonzero (and, to simplify, $K$ is uncountable) the number of possible representations (up to equivalence) is countable while the number of forms is uncountable (just using scalar multiplication). Even if one counts forms "up to scalar multiplication" (as in the OP's question), as soon as the space of invariant bilinear forms has dimension $\ge 2$ (which means that $\mathfrak{g}$ is nonzero and not absolutely simple), the number of forms "up to scalar multiplication" is too large.


text:
{\bf Problem.} Sides $\overline{AH}$ and $\overline{CD}$ of regular octagon $ABCDEFGH$ are extended to meet at point $P$. What is the degree measure of angle $P$?
{\bf Level.} Level 5
{\bf Type.} Prealgebra
{\bf Solution.} The sum of the angle measures of an octagon is $180(8-2) = 1080$ degrees, so each angle of a regular octagon measures $1080^\circ/8=135^\circ$.  Therefore, $\angle BCD= 135^\circ$, which means $\angle BCP = 180^\circ - \angle BCD = 45^\circ$.  Similarly, $\angle PAB = 45^\circ$.  Since $\angle ABC = 135^\circ$, the reflex angle at $B$ that is an interior angle of $ABCP$ has measure $360^\circ - 135^\circ = 225^\circ$.  The interior angles of quadrilateral $ABCP$ must sum to $360^\circ$, so we have  \begin{align*}
\angle P &= 360^\circ - \angle PAB - (\text{reflex }\angle B) - \angle BCP\\
&=360^\circ - 45^\circ - 225^\circ - 45^\circ = \boxed{45^\circ}.
\end{align*} [asy]
unitsize(0.6inch);
pair A,B,C,D,EE,F,G,H,P;

A = rotate(-67.5)*(1,0);
B = rotate(45)*A;
C=rotate(45)*B;
D = rotate(45)*C;
EE = rotate(45)*D;
F = rotate(45)*EE;
G = rotate(45)*F;
H = rotate(45)*G;

P = A + (rotate(-90)*(D-A));
draw (A--B--C--D--EE--F--G--H--A--P--C,linewidth(1));
label("$A$",A,S);
label("$B$",B,SE);
label("$C$",C,NE);
label("$D$",D,N);
label("$E$",EE,N);
label("$F$",F,W);
label("$G$",G,W);
label("$H$",H,S);
label("$P$",P,S);
[/asy]

Note that we also could have solved this problem by noticing that $\overline{FC}\parallel\overline{HA}$, so $\angle APD = \angle FCD$.  Since $\overline{CF}\parallel\overline {ED}$, we have $\angle FCD = 180^\circ - \angle CDE = 180^\circ - 135^\circ = 45^\circ$.

set_name: MATH


TITLE: Spivak's Calculus Chapter 28-1 (Fields)
QUESTION [0 upvotes]: Question in Textbook
The question defines a set F and then defines the operations on F through a table. In this chapter, Spivak outlines the properties that operators on a field must have. In the example in textbook he says that that the verifications of the conditions are simple, case by case checks. However, would that not be extremely long and tedious going through every case for every element in set F? Is there a simpler way to do this?

REPLY [0 votes]: The Field is only !$3$! elements.  It is very easy and short to check everything.
Axiom 1:  Addition is commutative.  If $a = b$ then $a+b= a+a=b+a$ so we only have to check if $a\ne b$ and there are only three such pairs.  $0 + 1 = 1=1+0; 0+2=2=2+0; 1+2=0=2+1$.  That's it.  We checked them all.
Axiom 2: Addition is associative.  The check $(a+b) + c = a+(b+c)$ is $27$ cases of $a,b,c$ but we can cut that down with commons sense. If $a,b$ or $c=0$ then $(a+b) + 0 = a+b = a +(b+0)$ and $(a+0)+c= a+c = a+(0+c)$ and $(0+b) +c = b+c = 0 + (b+c)$. (See axiom 3).  If none of $a,b,c=0$ then that is only $8$ cases but still we must have two of them equal or three of the equal and as addition is commutative:
$(a+a) + a = a+(a+a)$ and $(a+a)+b=a+(a+b)$ can be checked with $4$ cases.  And $(a+b) +a= a+(a+b)=a+(b+a)$.  And $(b+a)+a=(a+b)+a=a+(a+b)=(a+a) + b=b+(a+a)$.  so that associativity.
Axiom 3: $0+a = a+0= a$.  Just three things to check.  $0+0=0;1+0=1;2+0=0$ that's it we checked them ALL.
Axiom 4: even element has an additive inverse.  Only three to check.  $0+0=0$ so $0$ has an inverse.  $1+2 = 0$ so $1$ has an inverse. $2+1=0$ so $2$ has inverse.
Multiplication axioms are similar.
that was not a lot to do.
Showing no order can exist is figure: $0 = 1 + 1 + 1$  If $1 > 0$ then $1+1 > 0+1$ and $1+1+1 > 0+1+1$ and if $1< 0$ .... well same thing.


TITLE: Find the $a^3-b^2$ where $a,b$ satisfies this limit equation.
QUESTION [0 upvotes]: Find $a^3-b^2$ where a,b satisfies:
$\lim \limits_{x\to\infty} ((x^2+1)/(x+1) - ax-b) = 0.$
I tried equating it to $0$
I.e. \begin{align}&\left(\frac{x^2+1}{x+1} - ax-b\right)= 0 \\
& \implies \frac{x^2+1}{x+1} = ax+b \\
& \implies  x^2+1= ax^2 + ax + bx + b \end{align}
Then I compared the coefficients
Which gave
\begin{align}a&= 1,\\
a+b &= 0,\\
b &= 1, \end{align}
But if $a=b=1$ then how can $a+b =0$  am confused at this point.
Can't figure whats wrong with my steps

REPLY [0 votes]: Since $\frac{x^2+1}{x+1}$ is not a polynomial, we can't equate it directly to a linear polynomial.
However, as $x$ goes to $\infty$, it behaves as if it is linear. As you can see from the picture, though it is not a linear function, as $x$ grows bigger, it behaves almost linearly.

Since
$$\frac{x^2+1}{x+1}=x-1+\frac{2}{x+1},$$
we have
\begin{align}\lim_{x \to \infty} \left[\frac{x^2+1}{x+1}-ax-b\right]&=\lim_{x \to \infty} \left[(1-a)x+(-1-b)+\frac{2}{x-1}\right] \\
&= \lim_{x \to \infty}(1-a)x+(-1-b) \end{align}
Note that $\lim_{x \to \infty} \frac{2}{x-1}=0$.
You should be able to read off the value of $a$ and $b$ from the discussion above.


TITLE: What is polynomial $p = (X-X_{1})(X-X_{2}) \cdots (X-X_{m})$ in $R[X_{1}, \ldots, X_{m}][X]$?
QUESTION [1 upvotes]: In my textbook Analysis I by  by Amann/Escher, there are definitions as follows

Let $R$ be a nontrivial (not necessarily commutative) ring with unity.

The formal power series ring over $R$ is the set $R[\![X]\!] = (R^\Bbb N,+,\cdot)$ where addition $(+)$ is defined as

$$(p+q)_{n} :=p_{n}+q_{n}, \quad n \in \mathbb{N}, \quad p,q \in R^\Bbb N \tag1$$
and multiplication $(\cdot)$
$$(p q)_{n} :=(p \cdot q)_{n} :=\sum_{j=0}^{n} p_{j} q_{n-j}=p_{0} q_{n}+p_{1} q_{n-1}+\cdots+p_{n} q_{0}, \quad n \in \mathbb{N}, \quad p,q \in R^\Bbb N \tag2$$
We write $X$ for the power series $$X_{n} :=\begin{cases}{1} & \text{if }{n=1} \\ {0} & \text {otherwise }\end{cases} \tag3$$
Then it follows that $X^m := \underbrace{X \cdots X}_{m \text{ times}}$ is $$X_{n}^{m} =\begin{cases}{1,} & {n=m} \\ {0,} & {n \neq m}\end{cases} \quad m, n \in \mathbb{N} \tag4$$
For $a \in R$, we denote by $a X^{m}$ the power series, $$a X_{n}^{m} :=\begin{cases}{a} & \text{if } {m=n} \\ {0} & \text{otherwise}\end{cases} \quad m, n \in \mathbb{N} \tag5$$
If the context is clear, we write $a$ for $a X^{0}$.

A polynomial over $R$ is a formal power series $p \in R[\![X]\!]$ such that $\left\{n \in \mathbb{N} \mid p_{n} \neq 0\right\}$ is finite. The set of all polynomials over $R$ is denoted by $R[X]$.

If $p \in R[X]$, then there is some $n \in \mathbb{N}$ such that $p_{k}=0$ for $k>n$. Thus $p \in R[X]$ can be written in the form $$p=\sum_{k=0}^{n} p_{k} X^{k}=p_{0}+p_{1} X+p_{2} X^{2}+\cdots+p_{n} X^{n} \tag6$$

The authors go on to extend the above results to the case of formal power series and polynomials in $m$ indeterminates. In analogy to the $m=1$ cases, namely $R[X]$ and $R[\![X]\!]$ for $m \in \mathbb{N}^{+},$ we define addition and multiplication on the set $R^{\left(\mathrm{N}^{m}\right)}=\operatorname{Funct}\left(\mathbb{N}^{m}, R\right)$ by $$(p+q)_{\alpha} :=p_{\alpha}+q_{\alpha}, \quad \alpha \in \mathbb{N}^{m} \tag7$$
$$(p q)_{\alpha} :=\sum_{\beta \leq \alpha} p_{\beta} q_{\alpha-\beta}, \quad \alpha \in \mathbb{N}^{m} \tag8$$

In this situation, $p \in R^{\left(\mathrm{N}^{m}\right)}$ is called a formal power series in $m$ indeterminates over $R$. We set $R\left[\![X_{1}, \ldots, X_{m}\right]\!] :=\left(R^{\left(\mathbb{N}^{m}\right)},+, \cdot\right)$.
A formal power series $p \in R\left[\![X_{1}, \ldots, X_{m}\right]\!]$ is called a polynomial in $m$ indeterminates over $R$ if $\left\{\alpha \in \mathbb{N}^m \mid p_{\alpha} \neq 0\right\}$ is finite. The set of all such polynomials is written $R\left[X_{1}, \ldots, X_{m}\right]$.
Set $\color{blue}{X :=\left(X_{1}, \ldots, X_{m}\right)}$ and, for $\alpha \in \mathbb{N}^{m},$ denote by $X^{\alpha}$ the formal power series (that is, the function $\mathbb{N}^{m} \rightarrow R )$ such that $$X_{\beta}^{\alpha} :=\left\{\begin{array}{ll}{1,} & {\beta=\alpha,} \\ {0,} & {\beta \neq \alpha}\end{array}\right. \quad \beta \in \mathbb{N}^{m} \tag9$$
Then each $p \in R\left[X_{1}, \ldots, X_{m}\right]$ can be written uniquely in the form
$$p=\sum_{\alpha \in \mathbb{N}^{m}} p_{\alpha} X^{\alpha} \tag{10}$$

Then there is an exercise:

Show that the polynomial $$(X-X_{1})(X-X_{2}) \cdots (X-X_{m}) \in R[X_{1}, \ldots, X_{m}][X]$$ in one indeterminate $X$ over the ring $R[X_{1}, \ldots, X_{m}]$ satisfies $$(X-X_{1})(X-X_{2}) \cdots (X-X_{m})=\sum_{k=0}^{m}(-1)^{k} s_{k} X^{m-k}$$ where
$$\begin{align*} s_{0} &:=1 \in R \\ s_{1} & :=\sum_{1 \leq j \leq m} X_{j} \\ s_{2} & :=\sum_{1 \leq j<k \leq m} X_{j} \cdot X_{k} \\ & \mathrel{\vdots} \\ s_{k} & :=\sum_{1 \leq j_{1}<j_{2}<\cdots<j_{k} \leq m} X_{j_{1}} \cdot X_{j_{2}} \cdot \cdots \cdot X_{j_{k}} \\ & \mathrel{\vdots} \\ s_{m} & :=X_{1} X_{2} \cdots X_{m} \end{align*}$$
Notice that $s_k \in R[X_{1}, \ldots, X_{m}]$ is a elementary symmetric polynomial for all $1 \le k \le m$.

I have re-read the definitions several times but to no avail in understanding how the notation $(X-X_{1})(X-X_{2}) \cdots (X-X_{m})$ makes sense.
My question:

What is polynomial $p = (X-X_{1})(X-X_{2}) \cdots (X-X_{m})$ in $R[X_{1}, \ldots, X_{m}][X]$?

REPLY [1 votes]: I seem to got what's going on behind the scene.

In $(X-X_1)$, $X$ denotes the polynomial in $R[X_{1}, \ldots, X_{m}][X]$ such that $$X (n) :=\begin{cases} \overline{1} & \text{if } n=1 \\ \overline{0} & \text {otherwise }\end{cases}$$ where $\overline{1}$ is the multiplicative identity of $R[X_{1}, \ldots, X_{m}]$ and $\overline{0}$ the additive identity of $R[X_{1}, \ldots, X_{m}]$.
$X_1 = X_1^1 X_2^0 X_3^0 \ldots X_m^0$ is the polynomial in $R[X_{1}, \ldots, X_{m}]$ such that

$$X_1 (n_1, \ldots, n_m) = \begin{cases}
1 & \text{if $(n_1, \ldots, n_m)=(1, 0, \ldots, 0)$} \\
0 & \text{otherwise}
\end{cases}$$
where $1$ is the multiplicative identity of $R$ and $0$ the additive identity of $R$.

$X_2 = X_1^0 X_2^1 X_3^0 \ldots X_m^0$ is the polynomial in $R[X_{1}, \ldots, X_{m}]$ such that

$$X_2 (n_1, \ldots, n_m) = \begin{cases}
1 & \text{if $(n_1, \ldots, n_m)=(0, 1, 0, \ldots, 0)$} \\
0 & \text{otherwise}
\end{cases}$$
where $1$ is the multiplicative identity of $R$ and $0$ the additive identity of $R$.

In $(X-X_1)$, $X_1$ denotes the polynomial $X_1 X^0 \in R[X_{1}, \ldots, X_{m}][X]$.

To be more specific, $X_1 X^0$ is the polynomial such that
$$X_1 X^0 (n) = \begin{cases}
X_1 & \text{if } n = 0 \\
\overline{0} & \text{otherwise}
\end{cases}$$
where $\overline{0}$ is the additive identity of $R[X_{1}, \ldots, X_{m}]$.

In $(X-X_1)$, $-X_1$ denotes the additive inverse of $X_1 X^0$ in $R[X_{1}, \ldots, X_{m}][X]$.
$(X-X_1)$ denotes the sum of two polynomials $X$ and $-X_1$ in $R[X_{1}, \ldots, X_{m}][X]$.
$(X-X_1)(X-X_2)$ denotes the product of two polynomials $(X-X_1)$ and $(X-X_2)$ in $R[X_{1}, \ldots, X_{m}][X]$.


text:
\begin{document}

\title{A fast algorithm for solving linearly recurrent sequences}
\author{Seung Gyu Hyun, Stephen Melczer, Catherine St-Pierre}
\date{}

\maketitle

\begin{abstract}
We present an algorithm which computes the $D^{th}$ term of a sequence satisfying a linear recurrence relation of order $d$ over a field $\K$ in $O( \M(\bar d)\log(D) + \M(d)\log(d))$ operations in $\K$, where $\bar d \leq d$ is the degree of the squarefree part of the annihilating polynomial of the recurrence and $\M$ is the cost of polynomial multiplication in $\K$. This is a refinement of the previously optimal result of $O( \M(d)\log(D) )$ operations, due to Fiduccia.
\end{abstract}

\paragraph{Overview.}
Consider a sequence $(a_i)_{i\ge 0}$ with entries in a field $\K$ that is generated by the recurrence
\begin{equation}\label{eq:rec}
a_{i+d} = \sum_{j=0}^{d-1} c_{j} a_{i+j}
\end{equation}
for all $i \ge 0$, where $c_0 \neq 0$.  Given initial conditions $a_j$, for $0 \le j \le d-1$, along with the annihilating polynomial $P = x^d - \sum_{j=0}^{d-1} c_{j} x^j$, we are interested in the complexity of computing one term $a_D$ of the sequence for some index $D \gg 0$.

A naive solution entails computing all terms $a_0,\dots,a_D$, but one can do much better. It has been known since at least Fiduccia's work~\cite{Fiduccia85} that computing $a_D$ can be reduced to multiplication modulo $P$. Explicitly, define $\A=\K[x]/P$, together with the $\K$-linear form $\ell: \A \to\K$ given by $\ell(x^i) = a_i$ for $i=0,\dots,d-1$. Then, since the residue class of $x$ in $\A$ is a root of $P$, its powers $(x^i)$ in $\A$ satisfy~\eqref{eq:rec}, and so do the values $(\ell(x^i))_{i \ge 0}$; this implies that $\ell(x^i)=a_i$ holds for all values of $i \ge 0$. In other words, to compute $a_D$ it is enough to compute $R=x^D \bmod P$ as $R = r_0 + \cdots + r_{d-1} x^{d-1}$, since then $a_D = r_0 a_0 + \cdots + r_{d-1} a_{d-1}$.

Letting $\M$ denote a function such that polynomials of degree $n$ can be multiplied in $\M(n)$ operations (under the assumptions of~\cite[Chapter~8]{GaGe13}), computing $R$ costs $O(\M(d)\log( D))$ operations in $\K$; we can then deduce $a_D$ in $O(d)$ steps.

\paragraph{A new algorithm.}
In this note, we present an improvement over this previous result that is useful when $P$ has multiple factors of high multiplicities.

First, we reduce to the case where $P$ has the form $P=Q^m$, for squarefree $Q$. To that end, let $P = \prod_i Q_i^{m_i}$ be the squarefree factorization of $P$, with pairwise distinct $m_1,\dots, m_s$ and $Q_i$ squarefree of degree $f_i$ for all $i$; note $d = \sum_i f_i m_i$.  We can compute $x^D \bmod P$ by applying the Chinese Remainder Theorem to the quantities $x^D \bmod Q_i^{m_i}$, giving the following algorithm.

\begin{algorithm}[H]
  \caption{Computing one element in a linear recurrent sequence}
  \textbf{Input:}
  \begin{itemize}
  \item $P$: characteristic polynomial of the sequence
  \item $v=[a_0,\dots,a_{d-1}]$: vector of initial conditions
  \item $D$: index
  \end{itemize}
  \textbf{Output:} $D^{th}$ element of the sequence $(a_i)$ as in~\eqref{eq:rec}
  \begin{enumerate}
  \item compute the squarefree factorization of $P$ as $P = \prod_i Q_i^{m_i}$
  \item for $i=1,\dots,n$, compute $C_i = x^D \bmod Q_i^{m_i}$
  \item compute $R = x^D \bmod P$ by CRT as $R=r_0 + \cdots + r_{d-1} x^{d-1}$
  \item return $a_D =r_0 a_0 + \cdots + r_{d-1} a_{d-1}$.
  \end{enumerate}
\end{algorithm}

To compute the $C_i$'s efficiently, we will use bivariate computations. Indeed, for $i=1,\dots,s$ define $\A_i = \K[X]/Q_i^{m_i}$; then there exists a $\K$-algebra isomorphism
$$ \pi_i: \A_i = \K[X]/Q_i^{m_i} \to \K[y,x]/\langle Q_i(y),(x-y)^{m_i} \rangle. $$
Following van der Hoeven and Lecerf~\cite{HoLe17}, we will call $\pi_i$ the operation of {\em untangling} (this is a conversion from a univariate representation to a bivariate one) and its inverse {\em tangling}. (To be precise, van der Hoeven and Lecerf consider a mapping to $\K[y,x]/\langle Q_i(y),x^{m_i} \rangle$, which is isomorphic to $\K[y,x]/\langle Q_i(y),(x-y)^{m_i}\rangle$ through the shift $x \mapsto x+y$).

van der Hoeven and Lecerf prove that for a given index $i$, untangling can be done in $O(\M(f_i m_i) \log(m_i))$ operations in $\K$; note that input and output sizes are $f_i m_i$ in this case. They also give an algorithm for tangling of cost $O(\M(f_i m_i)\log^2(m_i) + \M(f_i) \log(f_i))$; we give below a Las Vegas algorithm of cost $O(\M(f_i m_i) \log(f_i m_i))$ for this task. Taking the existence of such algorithms for granted, we write
$$ C_i = x^D \bmod Q_i^{m_i} = \pi_i^{-1}( \delta_i ),\quad\text{with}\quad \delta_i=x^D \bmod \langle Q_i(y),(x-y)^{m_i}\rangle. $$
The following allows us to compute $\delta_i$ efficiently. Define coefficients $e_0,\dots,e_{m_i-1}$ by
$$x^D \bmod (x-1)^{m_i} = e_0 + e_1x + \cdots + e_{m_i - 1} x^{m_i -1},$$
and define $S_i(x) = (yx)^D \bmod (x-1)^{m_i} \in \K[y][x]$, where $y$ is seen as an element of $\K[y]/Q_i(y)$. Then
$$\delta_i = x^D \bmod (x-y)^{m_i} = S_i\left(\frac{x}{y}\right),$$
where we note $y$ is invertible in $\K[y]/Q_i(y)$ as $c_0 \neq 0$. Now,
$ S_i = y^D x^D \bmod (x-1)^{m_i}= y^D (e_0 + e_1x + \cdots + e_{m_i - 1} x^{m_i -1}),$
so that
$$\delta_i = y^De_0 + y^{D-1}e_1x + \cdots + y^{D-(m_i - 1)}e_{m_i - 1} x^{m_i -1}.$$

In this algorithm, we first need to compute coefficients $e_0,\dots,e_{m_i-1}$; assuming that $2,\dots,m_i-1$ are units in $\K$, they can be obtained in $O(\log(D) + \M(m_i))$ operations in $\K$. The powers of $y$ we need are computed modulo $Q_i$, in time $O( \M(f_i)\log (D) + m_i \M(f_i))$. Altogether, we obtain $\delta_i$ using $O( \M(f_i)\log (D) + \M(f_i m_i) ))$ operations in $\K$. As said above, we can deduce $C_i$ from $\delta_i$ in Las Vegas time $O(\M(f_im_i) \log( f_im_i)).$ Taking all $i$'s into account and using the super-linearity of $\M$, the total time to compute $C_1,\dots,C_s$ is thus
$$O( \M(\bar d)\log(D) + \M(d)\log(d)),$$
where $\bar d =\sum_i f_i \le d$ is the degree of the squarefree part of $P$.

Computing the squarefree factorization of $P$ and Chinese remaindering both cost $O(\M(d)\log d)$ \cite[Corollary~10.23]{GaGe13}, so the overall runtime is $O( \M(\bar d)\log(D) + \M(d)\log(d))$. This is to be compared with the cost $O( \M(d)\log(D) )$ of Fiduccia's algorithm.

\paragraph{Tangling and untangling.}
We conclude by sketching our new algorithm for tangling. van der Hoeven and Lecerf reduce the tangling operation to untangling by means of a divide-and-conquer process; we propose a direct reduction that uses transposition, inspired by an algorithm from~\cite{Shoup94} that applies in univariate situations.

In what follows we use the same notation as in the previous paragraphs, but we drop the subscript $i$ for clarity. In particular, we write $f=\deg(Q)$ and $n=fm$ for the degree of $Q^m$, that is, the input and output size. Given $\delta$ in $\K[y,x]/\langle Q(y), (x-y)^m\rangle$,  we want to find $C=c_0 + \cdots + c_{n-1} x^{n-1}$ such that $\pi(C)=\delta$; this simply means that
$$ C \bmod \langle Q(y), (x-y)^m\rangle = \delta.$$
Choose a random linear form $\lambda:\K[y,x]/\langle Q(y), (x-y)^m\rangle \to\K$. For $j \ge 0$, multiply the former equality by $x^j$ and apply $\lambda$; this gives
$$c_0 \lambda(x^j) + \cdots + c_{n-1} \lambda(x^{j+n-1}) = \lambda (x^j \delta).$$
Taking $j=0,\dots,n-1$, we can collect these equalities in a linear system $H A = L$, with
\begin{align*} \label{matrix_prod}
H=      \begin{bmatrix}
          \lambda(1)  &  \hdots      & \lambda(x^{n-1}) \\
          \vdots & \ddots & \vdots \\
          \lambda(x^{n-1})&\hdots  & \lambda(x^{2n-2})\\
        \end{bmatrix}
\qquad
A=      \begin{bmatrix}
          c_0 \\ \vdots \\ c_{n-1}\\
        \end{bmatrix}
\qquad
L=      \begin{bmatrix}
          \lambda(\delta)\\ \vdots \\ \lambda(x^{n-1}\delta)\\
        \end{bmatrix}.
\end{align*}
Once $H$ and $L$ are known, we can recover coefficients $A$ in $O(\M(n)\log(n))$ operations in $\K$, since the linear system is Hankel (for a generic choice of $\lambda$, matrix $H$ has full rank $n$). Hence, the main question is the efficient computation of the entries of matrices $H$ and $L$. Both are instances of the same problem: given a $\K$-linear form $\lambda$ over $\K[y,x]/\langle Q(y), (x-y)^m\rangle$, and $\beta$ in  $\K[y,x]/\langle Q(y), (x-y)^m\rangle$, compute the values $\lambda(\beta),\dots,\lambda(x^{n-1}\beta)$.

As already recognized by Shoup in the univariate case, this question is the transpose of the untangling map $\pi^{-1}$. As a result, using the so-called {\em transposition principle}~\cite{Shoup94,Kaltofen00,BoLeSc03}, we can deduce an algorithm of cost $O(\M(n)\log(n)) = O(\M(f m) \log(f m))$ for tangling, by transposition of van der Hoeven and Lecerf's untangling algorithm.

\bibliographystyle{plain}
\bibliography{abstract}

\end{document}

config: arxiv


TITLE: Does a bijective map from $(-\pi/2,\pi/2)\to (0,1)$ exist?
QUESTION [1 upvotes]: Does a bijective map from $(-\pi/2,\pi/2)\to (0,1)$ exist?

My first guess was using the sine function but it doesn't really comply with the bijective map since it goes from  $(-\pi/2,\pi/2)\to (-1,1)$. Am I missing something with the sine function or is there another way I can achieve this bijection?

REPLY [2 votes]: As @leibnewtz said, for any two intervals $(a,b), (c,d)$ there is a function as you asked. Consider
$$f(x)=\frac{x-a}{b-a}(d-c)+c.$$
In this case,
$$f(x) = \frac{x-(-\pi/2)}{\pi/2-(-\pi/2)}(1-0)+0 = \frac{ x + \pi/2}{\pi}=\frac{x}{\pi}+\frac{1}{2}$$
as @qaphla has pointed out.
Note that $f$ is continuous, $f(a)=c, f(b)=d$ and $f'(x)=\frac{d-c}{b-a}>0$, hence bijective.

REPLY [2 votes]: Take any bijection $f(x)$ from $(0,1)$ to $(0,1)$. Take a linear change of variable like $l_{-}(y) = \frac{1-2y}{2\pi} $ or $l_{+}(y) = \frac{1+2y}{2\pi} $. Then $f(l_\pm(y))$ is a bijection from $(-\frac{\pi}{2},\frac{\pi}{2})$ to $(0,1)$, because $l_{-}$ or $l_{+}$ maps  $(-\frac{\pi}{2},\frac{\pi}{2})$ to $(0,1)$ first, and is bijective.
Now for $f(x)$ you can take for instance $x\to x^p$ or $x\to \sin^p(2x/\pi)$, with  $p>0$, and you have at least a bijection with a sine function.


TITLE: Is a vortex crystal a supersolid?
QUESTION [4 upvotes]: Reading the article [Rev. Mod. Phys. 84, 759 (2012)] by Prokof'ev and Boninsegni, a supersolid is defined as a homogeneous phase of matter in which both density long-range order (i.e. ordered spatial modulation) and off-diagonal long-range order (i.e. superfluidity) exist simultaneously and appear spontaneously for the same species of particles.
Then several exotic examples are proposed, including solid $^{4}\mathrm{He}$ and dipolar quantum gases.
In my opinion, a more basic supersolid system should simply be a crystal of quantum vortices in a superfluid, since there is both superfluidity and spatial order.
This kind of state spontaneously emerge upon rotating a superfluid sample. Why is this broad and easily-accessible family of seemingly supersolid systems completely neglected? Am I missing something?

REPLY [1 votes]: I think that it's probably because the spatial order due to the vortex lattice emerges at a scale (i.e. the typical distance between vortices) that is greater than the scale of ODLRO. At this scale the system is practically in a hydrodynamic regime, in the sense that QM is not needed to describe it. In fact, the Tkachenko waves (that are basically elastic waves in the Abrikosov lattice of the vortices) can be studied, and derived, with classical hydrodynamics.
Moreover, vortices are expected to exist in a supersolid, but, as far as I know, their possible Abrikosov lattice would not constitute an example of  "supersolid-solid" (for the same reason given above). I'd rather say that it's the presence of vortices that inform you that you're observing a "super" state of matter, at least at a certain "mesoscopic" scale.


text:
\begin{document}

\title{Improved Bounds on the Restricted Isometry Constant for Orthogonal Matching Pursuit}

\author{Jinming Wen, Xiaomei Zhu and Dongfang Li}

\abstract{In this letter, we first construct a counter example to show that for any given positive integer $K\geq 2$ and for any $\frac{1}{\sqrt{K+1}}\leq t<1$, there always exist a $K-$sparse $\x$ and a matrix $\A$ with  the restricted isometry constant $\delta_{K+1}=t$ such that the OMP algorithm fails in $K$ iterations. Secondly, we show that even when $\delta_{K+1}=\frac{1}{\sqrt{K}+1}$, the OMP algorithm can also perfectly recover every $K-$sparse vector $\x$ from $\y=\A\x$ in $K$ iteration. This improves the best existing results which were independently given by Mo  et al. and Wang  et al.
}

\maketitle

\section{Introduction}
Consider the following linear model:
\begin{equation}
\label{e:model}
\y=\A\x
\end{equation}
where $\x\in \mathbb{R}^n$ is an unknown signal, $\y\in \mathbb{R}^m$ is an observation vector and $\A\in \mathbb{R}^{m\times n}$ (with $m<<n$) is a known sensing matrix. This model arises from compressed sensing, see, e.g., \cite{Don06} and one of the central goals is to recover $\x$ based on $\A$ and $\y$. It has been shown that under some suitable conditions, $\x$ can be recovered exactly, see, e.g., \cite{CanT05}.

The orthogonal matching pursuit (OMP) \cite{TroG07} is one of the commonly used algorithms to recover $\x$ from \eqref{e:model}. A vector $\x\in \mathbb{R}^n$ is $k-$sparse if $|\text{supp}(\x)|\leq k$, where $\text{supp}(\x)=\{i:x_i\neq0\}$ is the support of $\x$.
For any set $T\subset\{1,2,\ldots,n\}$, let $\A_T$ be the submatrix of $\A$ that only contains columns indexed by $T$ and
$\x_T$ be the restriction of the vector $\x$ to the elements indexed by $T$. Then the OMP can be described by Algorithm \ref{a:OMP}.

One of the commonly used frameworks for sparse recovery is the restricted isometry property,
which was introduced in \cite{CanT05}. For any $m\times n$ matrix $\A$ and any integer $k, 1\leq k\leq n$, the $k-$restricted isometry constant $\delta_k$ is defined as the smallest
constant such that
\begin{equation}
\label{e:RIP}
(1-\delta_k)\|\x\|_2^2\leq \|\A\x\|_2^2\leq(1+\delta_k)\|\x\|_2^2
\end{equation}
for all $k-$sparse vector $\x$.

It has conjectured in \cite{DaiM09} that there exist a matrix with $\delta_{K+1}\leq\frac{1}{\sqrt{K}}$ and a $K-$sparse $\x$ such that the OMP fails in K iterations \cite{MoS12}. Counter examples have independently given in \cite{MoS12} and \cite{WanS12} that there exist a matrix with $\delta_{K+1}=\frac{1}{\sqrt{K}}$ and a $K-$sparse $\x$ such that the OMP fails in K iterations. In this letter, we will give a counter example to show that for any given positive integer $K\geq 2$ and for any $\frac{1}{\sqrt{K+1}}\leq t<1$, there always exist a $K-$sparse $\x$ and a matrix $\A$ with $\delta_{K+1}=t$ such that the OMP algorithm fails in $K$ iterations. This result not only greatly improves the existing results, but also gives a counter example with $\delta_{K+1}<\frac{1}{\sqrt{K}}$ such that the OMP fails in K iterations.

It has respectively shown in \cite{DavW10} and \cite{LiuT10} that $\delta_{K+1}<\frac{1}{3\sqrt{K}}$ and $\delta_{K+1}<\frac{1}{(1+\sqrt{2})\sqrt{K}}$ are sufficient for OMP to recover every K-sparse $\x$ in K iteration. The sufficient condition has independently improved to $\delta_{K+1}<\frac{1}{1+\sqrt{K}}$ in \cite{MoS12} and \cite{WanS12}. In this letter, we will improve it to $\delta_{K+1}\leq\frac{1}{1+\sqrt{K}}$.

\begin{algorithm}[h!]
\caption{OMP \cite{TroG07}, \cite{WanS12} }  \label{a:OMP}
Input: measurements $\y$, sensing matrix $\A$
 and sparsity $K$.\\
Initialize: $k=0, r^0=\y, T^0=\emptyset$.\\
While $k<K$
\begin{algorithmic}[1]
\STATE $k=k+1$,
\STATE $t^k=\arg \max_j|\langle r^{k-1},\A_j\rangle|$,
\STATE $T^k=T^{k-1}\bigcup\{t^k\}$,
\STATE $\hat{\x}_{T^k}=\arg \min_{\x}\parallel\y-\A_{T^k}\x\parallel_2$,
\STATE $r^k=\y-\A_{T^k}\hat{\x}_{T^k}$.
\end{algorithmic}
Output: $\hat{\x}=\arg \min_{\x: \text{supp}(\x)=T^K}\parallel\y-\A\x\parallel_2$.
\end{algorithm}

\section{Main Results} In this section, we will give our main results. We will first construct a counter example to show the OMP algorithm may fail in $K$ iterations if $\frac{1}{\sqrt{K+1}}\leq\delta_{K+1}<1$.

\begin{theorem} \label{t:count}
For any given positive integer $K\geq 2$ and for any
\begin{equation*}
 \frac{1}{\sqrt{K+1}}\leq t<1
\end{equation*}
there always exist a $K-$sparse $\x$ and a matrix $\A$ with  the restricted isometry constant
$\delta_{K+1}=t$ such that the OMP  fails in $K$ iterations.
\end{theorem}

Our proof is similar to the method used in \cite{MoS12}, but the critical idea is different.

{\bf Proof.}  For any given positive integer $K\geq 2$, let
\begin{equation*}
\B=\begin{bmatrix}
\frac{K}{K+1}\I_{K}&  \frac{\1}{K+1} \\ \frac{\1^T}{K+1} & \frac{K+2}{K+1}
\end{bmatrix}
\end{equation*}
where $\1$ is a $K-$dimensional column vector with all of its entries being $1$ and $\I_{K}$ is the $K-$dimensional identity matrix.

By some simple calculations, we can show that the eigenvalues $\{\lambda_i\}_{i=1}^{K+1}$ of $\B$ are
\begin{align*}
&\lambda_1=\ldots=\lambda_{K-1}=\frac{K}{K+1}, \lambda_{K}=1-\frac{1}{\sqrt{K+1}}, \; \lambda_{K+1}=1+\frac{1}{\sqrt{K+1}}.
\end{align*}
let $s=t-\frac{1}{\sqrt{K+1}}$ and $\C=\B-s\I_{K+1}$. Then by the aforementioned two equations, the eigenvalues $\{\lambda_i\}_{i=1}^{K+1}$ of $\C$ are
\begin{align*}
&\lambda_1=\ldots=\lambda_{K-1}=\frac{K}{K+1}-s \\
&\lambda_{K}=1-\frac{1}{\sqrt{K+1}}-s=1-t, \; \lambda_{K+1}=1+\frac{1}{\sqrt{K+1}}-s.
\end{align*}

Since $ \frac{1}{\sqrt{K+1}}\leq t<1$, $\C$ is a symmetric positive definite matrix. Therefore, there exists an upper triangular
matrix $\A$ such that $\A^T\A=\C$. By the aforementioned inequations and \eqref{e:RIP}, $\delta_{K+1}(\A)=t$.

Let $\x=(1,1,\ldots,1,0)\in \mathbb{R}^{K+1}$, then $\x$ is $K-$sparse. Let $\e_{i}, 1\leq i\leq K+1$, denote the $i-th$ column of $\I_{K+1}$, then
one can easily show that,
\begin{align*}
\frac{K}{K+1}-s=\max_{1\leq i\leq K}|\langle\A\e_i, \A\x\rangle|\leq |\langle\A\e_{K+1}, \A\x\rangle|=\frac{K}{K+1}
\end{align*}
so the OMP fails in the first iteration. Therefore, the OMP algorithm fails in $K$ iterations for the given vector $\x$ and the given matrix $\A$.

In the following, we will improve the sufficient condition $\delta_{K+1}<\frac{1}{\sqrt{K}+1}$ \cite{MoS12}, \cite{WanS12} of the perfect recovery
 to $\delta_{K+1}\leq\frac{1}{\sqrt{K}+1}$.

\begin{theorem} \label{t:main}
Suppose that $\A$ satisfies the restricted isometry property of order $K+1$ with the
restricted isometry constant
\begin{equation}
\label{e:cond1}
\delta_{K+1}=\frac{1}{\sqrt{K}+1}
\end{equation}
then the OMP algorithm can perfectly recover any $K-$sparse signal $\x$ from
$\y=\A\x$ in $K$ iteration.
\end{theorem}

Before proving this theorem, we need to introduce the following two lemmas, where Lemma \ref{l:main2} was proposed in \cite{WanS12}.
\begin{lemma} \label{l:main1}
For each $\x, \x'$ supported on disjoint subsets $S, S'\subseteq \{1,\ldots, n\}$ with $|S|\leq s, |S'|\leq s'$, we have
\begin{equation}
\label{e:eq1}
|\langle \A\x, \A\x'\rangle|=\delta_{s+s'}\|\x\|_2\|\x'\|_2
\end{equation}
if and only if:
\begin{equation}
\label{e:eq2}
\frac{\|\A\x\|_2^2}{\|\x\|_2^2}+\frac{\|\A\x'\|_2^2}{\|\x'\|_2^2}=2.
\end{equation}
\end{lemma}

{\bf Proof.} Let
\begin{equation}
\label{e:x}
\bar{\x}=\x/\|\x\|_2, \bar{\x}'=\x'/\|\x'\|_2
\end{equation}
since $S\bigcap S'=\emptyset$, we have,
$\|\bar{\x}+\bar{\x}'\|_2^2=\|\bar{\x}-\bar{\x}'\|_2^2=2$. By \eqref{e:RIP}, we have
\begin{equation}
\label{e:rip2}
2(1-\delta_{s+s'})\leq \|\A(\bar{\x}\pm\bar{\x}')\|_2^2\leq 2(1+\delta_{s+s'})
\end{equation}
By the parallelogram identity and \eqref{e:x}, we have
\begin{equation}
\label{e:par}
|\langle \A\bar{\x}, \A\bar{\x}'\rangle|=\frac{1}{4}|\|\A(\bar{\x}+\bar{\x}')\|_2^2-\|\A(\bar{\x}-\bar{\x}')\|_2^2|\leq \delta_{s+s'}.
\end{equation}
By \eqref{e:x},  \eqref{e:eq1} holds if and only if the equality in \eqref{e:par} holds. By \eqref{e:rip2}, the equality in \eqref{e:par} holds if and only if
\begin{equation*}
\label{e:RIP2}
\|\A(\bar{\x}+\bar{\x}')\|_2^2=2(1-\delta_{s+s'}), \|\A(\bar{\x}-\bar{\x}')\|_2^2= 2(1+\delta_{s+s'})
\end{equation*}
or
\begin{equation*}
\label{e:RIP2}
\|\A(\bar{\x}-\bar{\x}')\|_2^2=2(1-\delta_{s+s'}), \|\A(\bar{\x}+\bar{\x}')\|_2^2= 2(1+\delta_{s+s'}).
\end{equation*}
Therefore, \eqref{e:eq1} holds if and only if
\begin{equation*}
\label{e:RIP2}
\|\A(\bar{\x}-\bar{\x}')\|_2^2+\|\A(\bar{\x}+\bar{\x}')\|_2^2= 4.
\end{equation*}
Obviously, the aforementioned equation is equivalent to \eqref{e:eq2}, so the lemma holds.

\begin{lemma} \label{l:main2}
For $S\subset\{1,2,\ldots,n\}$, if $\delta_{|S|}<1$, then
\begin{equation*}
(1-\delta_{|S|})\parallel\x\parallel_2\leq\parallel\A_S^T\A_S\x\parallel_2\leq(1+\delta_{|S|})\parallel\x\parallel_2
\end{equation*}
for any vector $\x$ supported on $S$.
\end{lemma}

We will prove it by induction. Our proof is similar to the method used in \cite{MoS12}, but the critical idea is different.

{\bf Proof of Theorem \ref{t:main}} Firstly, we prove that if \eqref{e:cond1} holds, then the OMP can choose a correct
index in the first iteration.

Let $S$ denote the support of the $K-$sparse signal $\x$ and let $\alpha=\max_{i\in S}|\langle\A\e_i, \A\x\rangle|$.
Then
\begin{equation*}
|\langle\A\x,\A\x\rangle|=|\sum_{i\in S}x_i\langle\A\e_i,\A\x\rangle|\leq\alpha\parallel\x\parallel_1\leq\alpha\sqrt{K}\parallel\x\parallel_2.
\end{equation*}
By \eqref{e:RIP}, it holds that
\begin{equation}
\label{e:lb1}
|\langle\A\x,\A\x\rangle|\geq(1-\delta_{K+1})\parallel\x\parallel_2^2.
\end{equation}
By the aforementioned two inequations, we have
\begin{equation}
\label{e:lb2}
\max_{i\in S}|\langle\A\e_i, \A\x\rangle|\geq\frac{(1-\delta_{K+1})\parallel\x\parallel_2}{\sqrt{K}}
\end{equation}
and if the equality in \eqref{e:lb2} holds, then the equality in \eqref{e:lb1} must also hold.

By Lemma 2.1 in \cite{Can08}, for each $j\not\in S$, it holds
\begin{equation}
\label{e:ub}
|\langle\A\e_j,\A\x\rangle|\leq \delta_{K+1}\parallel\x\parallel_2.
\end{equation}
So if \eqref{e:cond1} holds and at least there is one equality in \eqref{e:lb1} or \eqref{e:ub} does not hold, then for each $j\not\in S$, it holds
\begin{equation*}
|\langle\A\e_j,\A\x\rangle|<\max_{i\in S}|\langle\A\e_i, \A\x\rangle|.
\end{equation*}
Therefore, it suffices to show that the equality in \eqref{e:lb1} and the equation in \eqref{e:ub} can not hold simultaneously.

Suppose both the equality in \eqref{e:lb1} and the equation in \eqref{e:ub} hold, then by Lemma \ref{l:main1}, $\parallel\A\e_j\parallel_2^2=1+\delta_{K+1}$. Let $\C=(\A_{S\bigcup j})^T\A_{S\bigcup j}$, then $C_{jj}=\parallel\A\e_j\parallel_2^2=1+\delta_{K+1}$, thus for each $i\in S$,
$C_{ij}=0$. In fact, suppose there exists one $i\in S$ such that $C_{ij}\neq0$, then
\begin{equation*}
\parallel\A_{S\bigcup j}^T\A_{S\bigcup j}\e_j\parallel_2\geq \sqrt{\sum_{i\in S}C_{ij}^2}>1+\delta_{K+1}
\end{equation*}
which contradicts Lemma \ref{l:main2}. Therefore, for each $i\in S$,
$C_{ij}=0$. However, in this case, we have
\begin{equation*}
|\langle\A\e_j,\A\x\rangle|=0
\end{equation*}
which contradicts the equality in \eqref{e:ub}. Thus the equality in \eqref{e:lb1} and the equation in \eqref{e:ub} can not hold simultaneously. Therefore,
if \eqref{e:cond1} holds, then the OMP can choose a correct index in the first iteration.

By applying the method used in \cite{MoS12} or \cite{WanS12} and the aforementioned proof, one can similarly show that if \eqref{e:cond1} holds, then the OMP can  choose a correct index in the latter iterations, so the theorem is proved.

\section{ Future Work}

In the future, we will prove or disprove whether $\frac{1}{\sqrt{K}+1}<\delta_{K+1}<\frac{1}{\sqrt{K+1}}$ is a sufficient condition for the OMP to recover every $K-$spares signal $\x$ from $\y=\A\x$ in $K$ iterations.

\vskip3pt
\ack{This work has been supported by NSFC (Grant No. 11201161, 11171125, 91130003) and FRQNT.
}

\vskip5pt

\noindent Jinming Wen (\textit{Dept. of Mathematics and Statistics, McGill University, Canada, H3A 2K6})
\vskip3pt

\noindent Xiaomei Zhu (\textit{College of Electronics and Information Engineering, Nanjing University of Technology,  China, 211816; Dept. of Electrical and Computer Engineering,  McGill University, Canada, H3A 2A7})

\vskip3pt
\noindent E-mail: njiczxm@njut.edu.cn

\noindent Dongfang Li (\textit{School of Mathematics and Statistics, Huazhong University of Science and
Technology, China, 430074; Dept. of Mathematics and Statistics, McGill University, Canada, H3A 2K6})
\vskip3pt


TITLE: $k[x,y]/(f^p-a)$ is a reduced ring
QUESTION [1 upvotes]: Let $k$ be a an imperfect field of characteristic $p>0$ and let $a\in k$ be an element without a $p$'th root. Let $0\neq f=\alpha x+\beta y$. Then the ring $k[x,y]/(f^p-a)$ is reduced.

Showing this is equivalent to showing that whenever $f^p-a$ divides $g^n$ then $f^p-a$ already divides $g$. Intuitively I think the reason for this is that in an algebraic closure of $k$ we have $(f-a^{1/p})^p$ divides $g^n$. So $f-a^{1/p}$ divides $g$ (because it is a prime element). So in $k$ we must have that $f^p-a$ divides $g$.
How can I make this rigorous? Especially the last step?

REPLY [1 votes]: In fact, it is an integral domain: the polynomial $f^p-a$ is irreducible in $k[x,y]$. In order to show this we use the Eisenstein's criterion. Note that $f^p-a=\alpha^px^p+\beta^py^p-a$. Multiplying by $\alpha^{-p}$ doesn't change anything, so we may instead consider the polynomial $x^p+b^py^p-c$, $c\notin k^p$. Now note that the polynomial $b^py^p-c$ is irreducible in $k[y]$ (see here), and we are done.


TITLE: If $\underline{u}$ is a vector, does $u$ indicate its magnitude?
QUESTION [0 upvotes]: If $\underline{u}$ is a vector, does $u$ indicate its magnitude? $|\underline{u}|$ also indicates the magnitude, doesn't it?

REPLY [4 votes]: $|\underline{u}|$ also indicates the magnitude, doesn't it? - Yes.
The problem is that there are a number of conventions which people use and misuse.
The notation for a vector can be written as $\underline u, \,\vec u$ and $\mathbf u$.
Without any further information perhaps the "safest" way forward is to assume that $u$ represents the component of a vector in a given direction.
So $\underline u = u\,\hat u$ where $\hat u$ is unit vector in some given direction and $u$ is the component of vector $\underline u$ in the $\hat u$ direction.
As an example, you might write $\underline x = -3 \hat i$ but it could also be written as $\underline x = -3 \hat x$ where $\hat i = \hat x$ as alternative labels for the unit vector pointing in the positive x-direction.

REPLY [3 votes]: As has been pointed out, there are various conventions. To answer your first question, while not always the case, it is very common for $u$ to denote the magnitude of $\underline{u}$, so that $\underline{u}=u\hat u$, where $\hat u$ is the unit normal vector in the direction of $\underline{u}$. To use Farcher's example, if $\underline{u} = -3\hat i$, following this convention,
$u = 3$ and $\hat u = -\hat i$.


TITLE: (Long) Detailed Proof of Kőnig's Lemma (Explicit, Down to Axiom of Choice)
QUESTION [10 upvotes]: Kőnig's Lemma states that in an infinite, locally finite, connected graph $G$, there exists an infinite one-way path (a ray). The proof of it in my graph theory book (Introduction to Graph Theory, 4th ed., Wilson) had a sour taste to it, like it was covering something up. So I checked out proofs from other sources, which also seemed to cover up something which felt very close to the foundation (i.e. using the axioms). After looking it up I found out that this is indeed the case, as it results directly from the axiom of dependent choice (DC).
This wasn't a question on an assignment for me or anything, but I wanted to try to give a more detailed, albeit lengthy proof of the lemma with more explicit constructions and play-by-play, highlighting some of the key points and bare bones math going on here (including the general statement of the lemma and the use of DC), to the best of my understanding. I was hoping that anyone with time to spare hands could review or give comment, make sure everything I'm stating things correctly! And of course, I would be happy if this helps anyone in a similar predicament that comes to read this in the future, or helps anyone to appreciate the deeper levels of a simple theorem.
I've enabled the "answer your own question" box so I can post my proof separately, but I encourage/challenge others to do the same and make a detailed construction as an exercise, especially during these times of isolation!
Below I'll prove a similar theorem which uses Kőnig's Lemma in a more general form (but sweeps DC under the rug). It's a good reference because it's easier to understand without a super explicit construction:

Let $G$ be a countable graph such that every finite subgraph of $G$ is $k$-colourable. Then $G$ is $k$-colourable.

Proof
Since $G$ is countable, its vertices are enumerable as $v_1$, $v_2$, $v_3$, etc. Let $G_n$ be the (finite) subgraph induced by vertices $v_0$ through $v_n$. Since each vertex $v_n$ corresponds to a finite induced subgraph $G_n$, there are countably many $G_n$. Since $G_n \subset G_{n+1}$ for all $n$ by construction, the union over all $G_n$ yields $G$. Since each $G_n$ is finite, there are countably many corresponding sets $C_n$ of valid $k$-colourings of $G_n$, each non-empty with a finite number of elements given by the chromatic polynomial of $G_n$, $P_{G_n}(k)$. If we consider a colouring of $G_{n+1}$ and remove vertex $v_{n+1}$, we are left with a valid colouring of $G_n$: removing vertices does not invalidate a colouring. And so this valid colouring of $G_n$ must be an element of $C_n$. In general, for every colouring $c_{n+1} \in C_{n+1}$ of $G_{n+1}$ there is some colouring $c_{ind} \in C_{n}$ such that $c_{ind} \prec c_{n+1}$ (i.e. $c_{ind}$ is induced on $G_n$ by $c_{n+1}$). Kőnig's Lemma states that since there are countably many non-empty $C_n$ that follow these conditions, we must have a countable set of $c_n \in C_n$ such that $c_n \prec c_{n+1}$ for all $n$. If there were not, then all inductive sequences of colourings would terminate at some finite point $t$. If we take $\tau$ to be the maximum such $t$ over all sequences, then $C_{\tau + 1}$ must be empty, contradictory to our assumption that all $G_n$ are $k$-colourable (and in turn that all $C_n$ are non-empty). Therefore there is a countable set of inductive valid $k$-colourings $c_n$, and their union gives us a valid $k$-colouring of $G$.
Thus, $G$ is $k$-colourable. $\blacksquare$
The general form of Kőnig's Lemma can be stated as follows (paraphrasing Infinite Graphs - A Survey, by Nash-Williams, 1967):

Given a countable sequence of finite, non-empty, disjoint sets $S_n$ and a relation $\prec$ on $\bigcup S_n$, if for each element $s_{n+1} \in S_{n+1}$ there exists an $s_n \in S_n$ such that $s_n \prec s_{n+1}$, then there exists a countable sequence of elements $(s_n)$ such that $s_n \prec s_{n+1}$ for all $n$.

The end of the $k$-colouring proof I gave is basically the proof of this theorem. In this general form, the $S_n$ can be thought of as "configuration spaces" (finite sets of valid configurations), and the relation $\prec$ can be thought of as an inductive consistency relation. In the $k$-colouring proof, our configuration spaces are the $C_n$ and they are finite due to the chromatic polynomial of $G_n$, though I didn't explicitly construct them so we can't show that they are disjoint. But as I mentioned, this is still easier to understand without explicit construction. This is because we iterate out $G$ vertex by vertex, and as a result, we get a natural correspondence between the iterated subgraphs and their colourings. In proving the graph theoretic result about the existence of an infinite one-way path, the iteration scheme is not vertex by vertex, and so more explicit construction is needed to make the simple argument as above. That will be in my proof below, and similar methods can be used to construct a more explicit proof of this $k$-colourability result, and one for planarity as well!

REPLY [4 votes]: Dependent Choice is quite significantly stronger than what is necessary to prove Kőnig's lemma. And although the "obvious proof" uses Dependent Choice, we can do with much less. Indeed, Kőnig's lemma is equivalent to the statement "Every countable family of finite sets admits a choice function".
This principle is very weak. It follows from "the countable union of finite sets is countable", which follows from "the countable union of countable sets is countable", which follows from "every countable family of sets admits a choice function", which follows from Dependent Choice. None of these implications is reversible, either.
In fact, Kőnig's lemma follows even from "every set can be linearly ordered", or "every infinite set contains a countably infinite subset".
Suppose that $G$ is a locally finite graph. We may assume that it is cycle-free, otherwise pick any cycle, and loop through it infinitely many times. Now that the graph is cycle-free, we may also assume it is connected, otherwise we can restrict to a connected component.
Fix a node, $g_0\in G$. Then we have a tree with $g_0$ being the root. Define $T_n$ to be the set of vertices for which the unique path from $g_0$ has exactly $n$ nodes. Because $G$ is cycle-free and connected, these paths are indeed unique, and every node in $G$ lies in some $T_n$.
Claim 1. For each $n$, $T_n$ is finite.
Proof. $T_0=\{g_0\}$. Suppose that $T_n$ is finite, then elements of $T_{n+1}$ are all neighbours of elements of $T_n$. But as $G$ is locally finite, $T_{n+1}$ is a subset of a finite union of finite sets, which means it is finite. $\square$
Say that a vertex $g$ in $G$ is terminal if there is some $\ell_g$ such that all paths going from $g_0$ through $g$ are at most of length $\ell_g$.
Claim 2. For each $n$, $T_n$ contains at least one node which is not terminal.
Proof. If all the nodes in $T_n$ are terminal, let $\ell = \max\{\ell_g\mid g\in T_n\}$, then $G=\bigcup_{k\leq \ell}T_k$, and so $G$ is finite. But we assumed that $G$ is infinite. $\square$
Claim 3. If $g\in T_n$ and $g$ is not terminal, then there is some $g'\in T_{n+1}$ such that $g'$ is a neighbour of $g$, and $g'$ is also not terminal.
Proof. If $g$ is connected only to terminal nodes in $T_{n+1}$, let $\ell$ be $\max\{\ell_{g'}\mid g'\in T_{n+1}\text{ and it is a neighbour of }g\}$. That means that every path from $g_0$ going through $g$ must have at most $\ell$ vertices, and so $g$ is terminal as well. $\square$
Let $T'_n$ denote the subset of $T_n$ of those nodes which are not terminal. Since $T'_n$ is finite, say with $k_n$ elements, the set $S_n=\{f\colon\{0,\dots,k_n-1\}\to T'_n\mid f\text{ is a bijection}\}$ is also finite, and non-empty. Let $F$ be a choice function from $\{S_n\mid n\in\Bbb N\}$.
Finally, define $f$ on the graph as follows: $$f(g)=\begin{cases}
F(n+1)(i) & g\in T_n, i=\min\{j<k_{n+1}\mid F(j)\text{ is a neighbour of }g\},\\
g & \text{otherwise}.\end{cases}$$
That is, $f$ either "stops" if there are only terminal nodes, or picks the neighbour with the least index in the enumeration of $T'_{n+1}$, if such neighbour exists.
And now I claim that applying the recursion theorem on $f$, with $g_0$ as a starting point, will produce a ray. That is, a sequence $s$ such that $s_0 = g_0$ and $s_{n+1} = f(s_n)$.
Claim 4. The sequence $s$ is a ray.
Proof. It is enough to claim that for all $n$, $s_n$ is not a terminal node. For $n=0$ we already know that $g_0$ is not terminal. But by Claim 3, if $s_n$ is not terminal, then there is some neighbour in $T_{n+1}$ which is also not terminal, so $s_{n+1}=f(s_n)$ must be such neighbour, and in particular it is not terminal. $\square$

You can see from this proof how the various choice principles I've pointed out allow us to prove the existence of the choice function $F$.

If the countable union of finite sets is countable, then we take the union of all the $T'_n$, it is countable, so we may enumerate it, and use this enumeration to define $F$.
If every set can be linearly ordered, we may linearly order the union of the $T'_n$s, which again provides us with a uniform enumeration, as a linear ordering of a finite set is a well-ordering.
If every infinite set has a countably infinite subset, then the union of the $T'_n$s has a countably infinite subset, it follows that it must meet infinitely many $T'_n$s, but by the uniqueness of the paths, we can then create a countable subtree, and use the enumeration, again.

Finally, to obtain the countable choice for families of finite sets axiom, let $\{A_n\mid n\in\Bbb N\}$ be a family of non-empty finite sets. We define $G_n$ to be the set of choice functions from $A_k$ for $k<n$, i.e. $\prod_{k<n}A_k$, and let $G=\bigcup_{n\in\Bbb N}G_n$, with the edge relation defined as follows: $\{f,g\}$ is an edge if and only if there is some $n$ such that $\operatorname{dom} g=\{0,\dots,n\}$ and $f=g\restriction\{0,\dots,n-1\}$, or vice versa.
That is, an edge is between two functions such that the one extends the other by a single new choice. It is easy to see this is locally finite, as each $A_n$ is finite. So there is a ray, from which we define a choice function from the entire family $\{A_n\mid n\in\Bbb N\}$.


TITLE: Why do I get $0.098765432098765432...$ when I divide $8$ by $81$?
QUESTION [13 upvotes]: I got this remarkable thing when I divided $16$ by $162$, or, in a simplified version, $8$ by $81$.  It's $0.098765432098765432\cdots$, or more commonly known as $0.\overline{098765432}$, with all the one-digit numbers going backwards...except for $1$.  Yeah, it's missing the $1$.  One, how do I get this remarkable outcome and two, why is it missing the $1$?

REPLY [7 votes]: More generally, in base $b$ (any integer $>1$)
$$ \dfrac{b-1}{b^2} + \dfrac{b-2}{b^3} + \ldots + \dfrac{2}{b^{b-1}} =
\dfrac{(b-2)(b^{b-1} - 1)}{b^{b-1} (b-1)^2}$$
so that
$$ \eqalign{
\dfrac{b-1}{b^2}& + \dfrac{b-2}{b^3} + \ldots + \dfrac{2}{b^{b-1}} +
\dfrac{0}{b^{b}} + \dfrac{b-1}{b^{b+1}} + \dfrac{b-2}{b^{b+3}} + \ldots
= \sum_{j=0}^\infty b^{-j(b-1)} \dfrac{(b-2)(b^{b-1} - 1)}{b^{b-1} (b-1)^2}\cr
&= \dfrac{b^{b-1}}{b^{b-1}-1} \dfrac{(b-2)(b^{b-1} - 1)}{b^{b-1} (b-1)^2}= \dfrac{(b-2)}{(b-1)^2}}$$
What you have is the case $b=10$.


TITLE: combinatorics help question, dont understand
QUESTION [0 upvotes]: I've got this maths question and i've no idea how to do it.
http://vvcap.net/db/iCEsjpXBaSTQDmRI6eYz.htp
The same question has been posted up on another forum, someone has given a solution, but i don't understand it. http://vvcap.net/db/Ttdif9ANgn2tkHesy4US.htp If anyone could explain to me what's going on in the second link, that'd be good. Cheers.
Please explain as basically as possile

REPLY [0 votes]: So you have a set, $A$ that is all the numbers from $1$ to $11$. The first subset of $A$ you should look at is $\{2,4,6,8,10\}$, which is all the even numbers from $A$, notice there are $5$ of them. Now look at the subset $\{1,3,5,7,9,11\}$, the set of odd numbers in $A$, there are $6$ of them. We need to build subsets of $A$. So let's do it!
First, we note that the subset must have an even number of elements! Why? If it did not then we could not have the same amount of even and odd numbers. For example, if we tried to make a one element subset, then it would consists of a single odd and no evens or an even and no odds, which is a problem. So now we only need to make even subsets.
The easiest is a subset with $0$ elements chosen. There is only $1$ way to take an element from the set of even and odds (that is to choose none of them!). So this can be done in $1$ way.
Now let's make a subset with $2$ elements. This means we have to choose $1$ odd and $1$ even. There are $6$ total odd numbers, so we can do this in $\binom{6}{1}=6$ total ways. But we want to choose that AND an even number, which can be done in $\binom{5}{1}=5$ ways because there are $5$ even numbers. The AND 'logic' means we need to multiply. So the total number of $2$ element subsets of $A$ we could make is
$$
\binom{6}{1}\binom{5}{1}=6(5)=30
$$
Let's go back to the $0$ subset we made. What did we do? We chose $0$ elements from the evens and $0$ elements from the odds. But isn't that $\binom{6}{0}$ and $\binom{5}{0}$? We choose $0$ from the evens AND $0$ from the odds, that gave us
$$
\binom{6}{0}\binom{5}{0}=1(1)=1
$$
ways to do it. Which is what we got!
So notice that in general, if we want to make a subset of $A$ by choosing $n$ elements from the evens and odds, we can do it in
$$
\binom{6}{n}\binom{5}{n}
$$
ways!
We are almost done. We just need to figure out our $n$'s! We now we could choose $0$ from each set. We can do $1$. Et cetera. But notice we can't choose more than $5$ because though the odd number set has $6$ elements, the evens only has $5$ elements. So the most we can choose is $5$ elements from each set. So we need to do this for $n=0,1,2,3,4,5$. How do we get our answer. Well, we add them! Each one of them is a way we can make a subset of $A$ with equal amounts of odds and evens. So their total gives us all the ways to do it. Using what we found above, the total is...
$$
\binom{6}{0}\binom{5}{0}+\binom{6}{1}\binom{5}{1}+\binom{6}{2}\binom{5}{2}+\binom{6}{3}\binom{5}{3}+\binom{6}{4}\binom{5}{4}+\binom{6}{5}\binom{5}{5}
$$
$$
=1+30+150+200+75+6=462
$$
So there are $462$ total ways to make subsets using the numbers from $A$ so that there are the same number of even and odd numbers in the set! Hopefully, that cleared up your confusions.
EDIT: To answer your commented question:
That is multiplication as $\binom{6}{1}=6$ and $\binom{5}{1}=5$. Maybe you haven't learned this. But the amount of ways to choose $n$ objects from $T$ total things is
$$
\binom{T}{n}
$$
You can read more about this here. Now this number is given by
$$
\binom{T}{n}=\frac{T!}{n!(T-n)!}
$$
In case you have never seen it for some reason, $T!$ means we multiply $T$ by all the numbers from $T$ down to $1$. So $5!=5\times 4 \times 3 \times 2 \times 1=120$. We also define $0!=1$ Now lets go back to the example, we have
$$
\binom{6}{1}=\frac{6!}{1!(6-1)!}=\frac{6!}{1!5!}=\frac{6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{1 \times (5 \cdot 4 \cdot 3 \cdot 2 \cdot 1)}=6
$$
Similarly, we have
$$
\binom{5}{1}=\frac{5!}{1!(5-1)!}=\frac{5!}{1!4!}=5
$$
So then
$$
\binom{6}{1}\binom{5}{1}=6(5)=30
$$
So you can do the same with all the rest of the numbers. Doing them in order yields the numbers written: $1$, $30$, $150$, $200$, $75$, and $5$, respectively.


TITLE: Size bound on Büchi automaton for complement
QUESTION [3 upvotes]: For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by
$$
\begin{array}{llll}
 u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' \in Q \mbox{ we have a path} \\
& & \mbox{from $s$ to $s'$ labeled by $v$ iff we have} \\
& & \mbox{such a path labeled by $w$ and} \\
& & \mbox{we have such a path which passes through a state from $F$} \\
& & \mbox{labeled by $v$ iff we have such a path labeled by $w$}.
\end{array}
$$
for $u, v \in A^{\ast}$. Now setting
$W_{ss'} := \{ w \in A^{\ast} \mid \mbox{there is a path labeled $w$ from $s$ to $s'$}\}$ and $W_{ss'}^{F} := \{ w \in A^{\ast} \mid \mbox{there is a path labeled $w$ from $s$ to $s'$ going through a state in $F$}\}$ we have
$$
 [w]_{\sim_{\mathcal A}} = \bigcap_{\substack{s,s'\in Q \\ w \in W_{ss'}}} W_{ss'} \cap \bigcap_{\substack{s,s' \in Q \\ w \in A^{\ast} \setminus W_{ss'}}} A^{\ast}\setminus W_{ss'}
 \bigcap_{\substack{s,s'\in Q \\ w \in W_{ss'}^F}} W_{ss'}^F \cap \bigcap_{\substack{s,s' \in Q \\ w \in A^{\ast} \setminus W_{ss'}^F}} A^{\ast}\setminus W_{ss'}^F.
$$
This equivalence is defined here and also in the the chapter Automata on infinite objects by Wolfgang Thomas in the Handbook of Theoretical Computer Science, Volume II. In this book it is said

Let us consider the complexity of the complementation process and the equivalence test. Given a Büchi automaton with $n$ states, there are $n^2$ different pairs $(s,s')$ and hence $O(2^{2n^2})$ different $\sim_{\mathcal A}$-classes. This leads to size bound of $O(2^{4n^2})$ states for the complement automaton.

As in the above formula, for each set $W_{ss'}$ (and $W_{ss'}^F$) we can decide wether it occurs in the intersection (and hence determines if one complement $A^{\ast}\setminus W_{ss'}$ and $A^{\ast} \setminus W_{ss'}^F$ occurs) we have $2^{n^2}\cdot 2^{n^2}$ options (different then $|Q^{2^{2Q}}|$ which would be given by the identification of the classes with functions $f : Q \to 2^Q \times 2^Q$ in the wikipedia article).

But why does this lead to a size bound of $O(2^{4n^2})$ for the complement automaton?

I do not see how to get a complement automaton such that this size bound could be easily seen?

REPLY [4 votes]: Once you have the bound $2^{2n^2}$ on the number of classes, you can note that each state in the complement automaton corresponds to an $\omega$-regular language of the form $L_{f}L_{g}^\omega$, with $L_f$ and $L_g$ being functions from $Q$ to $2^Q\times 2^Q$.
Each such language is determined by $L_f$ and $L_g$, and there are $2^{2n^2}$ options for these functions, so you get a total of $(2^{2n^2})^2=2^{4n^2}$ options.
UPDATE FOLLOWING COMMENT:
The correspondence of the number $2^{4n^2}$ to the states of the constructed automaton is not exact. Observe that for every language $L_f$, we can construct a nondeterministic NFA $A_f$ (as is done in Theorem 1 in the Wikipedia link you posted). Moreover, the size of $A_f$ is polynomial in the size of the original NBW $A$. Thus, the size of an NBW for $L_fL_g^\omega$ is polynomial. You then take a union of $2^{4n^2}$ such automata, and obtain the complement NBW, so the size of the complement NBW is:
$$2^{4n^2}\cdot poly(n)=2^{4n^2 +\log poly(n)}=2^{O(4n^2)}$$
So it's a little less tight than $O(2^{4n^2})$, but it's still only singly exponential (perhaps there is a tighter analysis, but I'm not aware of one).