TITLE: Equivalency of all norms on a finite dimensional vector space: compactness theorems vs. the open mapping theorem
QUESTION [4 upvotes]: Going through my functional analysis course notes, I feel like there are two different proofs for the following theorem.

In $\mathbb{R}^n$ (or $\mathbb{C}^n$), any two norms are equivalent.

One uses the compactness-related extreme value theorem (i.e., a continuous function on compact set must achieve its maximum and minimum values), while the other uses the open mapping theorem (i.e, for every continuous linear mapping $T$ from a Banach space $X$ onto another Banach space $Y$, and every $U \in X$ open, $T(U)$ is open). These two theorems use different hypothesis and are not equivalent. Therefore, I am suspicious that I am doing something wrong.
My questions is whether both these proofs are correct, or if I am doing something wrong here.
Common steps of both proofs

Define (recall) the $\|.\|_\text{sup}$ norm as $\|x\| = \sup_{i} |x_i|$.
(*) Show that for any norm $\|.\|_b$ on $\mathbb{R}^n$, there exist an $M_b > 0$, such that for all $x \in \mathbb{R}^n$, $\|x\|_b \leq M_b \|x\|_\text{sup}$ (see for example here on how to find $M_b$).

Proof with extreme value theorem

From (*) we deduce that any norm $\|x\|_b$ is continuous w.r.t the $\|x\|_\text{sup}$ norm.
(+) Use the fact that the unit sphere (of the sup norm) is compact in $\mathbb R^n$, (*), and the extreme value theorem to deduce that $\|x\|_b$ achieves a minimum $m_b$ on the unit sphere (of the sup norm). In other words, there exists $m_b > 0$ such that $\|x\|_b \geq m_b \|x\|_\text{sup}$ for all $x \in \mathbb R^n$.
Combining (+) and (*), we get that any norm $\|.\|_b$ and $\|.\|_\text{sup}$ are equivalent $\blacksquare$

Proof with the open mapping theorem
This is the proof that I am not sure about.

From the open mapping theorem, one can prove that (see for example here for a proof):

Let $\|.\|_1$ and $\|.\|_2$ be norms on a Banach space $X$, such that $\|x\|_1 \leq\|x\|_2$. Then, the norms are equivalent.

Now combine this with (*) with the fact that $\mathbb R^n$ is complete (Banach), and you get that any norm in $\mathbb{R}^n$ is equivalent to the $\|.\|_\text{sup}$ norm $\blacksquare$

REPLY [2 votes]: We cannot apply the open mapping theorem as we do not know a priori that $(\mathbb{R}^n, \Vert \cdot \Vert_b)$ is a Banach space.
In fact the main motivation (for me) to prove the equivalence of the norms is to show that any finite-dimensional normed space is a Banach space.


TITLE: Why is the magnetic field vector of light so weak compared to it’s electric field vector?
QUESTION [0 upvotes]: As this article describes,
https://physics.aps.org/story/v26/st13
The magnetic field vector of light is extremely weak. It seems odd to me why this has never been explained in my science curriculum, considering how important the development of the theory of electromagnetism is.
Hence, what is the origin of this disparity in strength?

REPLY [2 votes]: It's not fair to compare $E$ and $B$ (They have a different units). Consider the energy density associated with them (considering monochromatic waves and take average and all)
$$u_B=\frac{1}{2\mu_0}B^2\ \ \ \ \text{and} \ \ \ \ \ u_E=\frac{\epsilon_0}{2}E^2$$
$$\frac{u_B}{u_E}=\frac{B^2}{E^2}c^2$$
Further $E=cB\Rightarrow u_B=u_E.$


TITLE: Solving non-linear second order differential equation: radius of curvature $= k \theta$
QUESTION [1 upvotes]: I'm trying to find any curve where the radius of curvature increases linearly with angular displacement. So in polar coordinates
radius of curvature $= k \theta$
$$ \frac{(r^2 + r'^2)^{3/2}}{r^2 + 2r'^2 - rr''} = k \theta$$
where k is a constant
I just need a single curve that fits this equation, does not matter if it is defined as an integral or power series. But, best to have a closed form solution. Thank you.

REPLY [0 votes]: If $\psi $ is angle between radius vector and tangent and primes are taken with respect to arc length, then we need to solve for $ r,\theta $ via $ \psi$ for reciprocal radius of curvature:
$$ \dfrac{d \psi}{ds} + \dfrac{\sin \psi}{r} = k\, \int  \dfrac{\sin \psi}{r} ds, \, r^{'} = \cos \psi,\, \theta^{'}= \dfrac{\sin \psi}{r}.  $$
EDIT1:
As a first step numerical solution is given below for assumed boundary conditions near origin.


TITLE: Average distance to perimeter of a polygon?
QUESTION [3 upvotes]: Trying to calculate heat transfer which is a function of distance of each molecule to the closest wall for various container shapes.  For example, a rectangular prism versus a cylinder.
So I think that  a 'thin' rectangular prism of volume V average distance to wall can be much less than average distance of a cylinder.  Reducing only to the cross section, assuming a rectangle of dimension $x$, $.5x$, versus a cylinder of of radius $\sqrt{\frac{x^2}{2 \pi}}$ (which is same volume I think) what is the average distance from a point in the circle to the perimeter versus the average distance of a point in the rectangle to its closest perimeter?
For a circle I have this idea that if inscribe a smaller circle inside the big circle with the same center point, such that the smaller circle contains 1/2 the volume of the outer circle, then the average distance is radius of outer circle minus radius of inner circle.  Is that correct?
For the rectangle I don't quite know  -- whether the same approach could be used to inscribe a rectangle of the same aspect ratio which contains 1/2 the area of the outer rectangle and the average distance is the length of the perpendicular connecting the inner and outer rectangle?
Is this a correct approach?

REPLY [1 votes]: The expected distance from a unit circle to a randomly chosen point inside the circle is given by
$$
\frac{1}{\pi}\int_{0}^{1}(1-r)(2\pi r)dr=\left(r^2-\frac{2}{3}r^3\right)\bigg\vert_{0}^{1}=\frac{1}{3};
$$
as a function of the area of the circle, then, the expected distance is
$$
{d}_{\text{circle}}(A)=\frac{1}{3\sqrt{\pi}}\sqrt{A} \approx 0.1881 \sqrt{A}
$$
(which holds for circles of any size).  For a square of side length $2$, the expected distance from the square to a random interior point (which can be calculated by considering a single quadrant) is
$$
\int_{0}^{1}y(2-2y)dy = \left(y^2-\frac{2}{3}y^3\right)\bigg\vert_{0}^{1}=\frac{1}{3}
$$
as well, so
$$
d_{\text{square}}(A)=\frac{1}{6}\sqrt{A} \approx 0.1667 \sqrt{A}
$$
for an arbitrary square.  Finally, for a $2\times 4$ rectangle, you need to consider the short and long sides differently.  Essentially you have two $2 \times 1$ end caps that behave like the square (so the average distance is $1/3$), and a $2\times 2$ central block for which the average distance is just $1/2$.  The two components have equal areas, so the overall average distance is the average of $1/2$ and $1/3$, or $5/12$.  Since the area of the entire rectangle is $8$, we have
$$
d_{\text{rect}}(A)=\frac{5}{24\sqrt{2}}\sqrt{A} \approx 0.1473 \sqrt{A}
$$
for any rectangle with aspect ratio $2$.
If it helps, you can think of "unrolling" each shape, while preserving its area, so that the set of points at distance $d$ from the perimeter lies along $y=d$.  For the circle and the square (and for any regular polygon), this gives a triangle with base equal to the original shape's perimeter.  For the rectangle, though, it gives a trapezoid, because the points maximally distant from the perimeter are a line segment, not a single point.


TITLE: What is the expected value E(C) that the insurance company is expected to pay?
QUESTION [0 upvotes]: Discrete probability
When all factors are taken into account, an insurance company estimates that the probability of the owners’ of certain house making a claim for $\$5000$ is $0.1$. Furthermore the company estimates the probability of a $\$450,000$ claim( total loss of the home) is $0.005$. Let $X$ represent the dollar amount the company will pay on a claim in a given year. What values can $X$ take on?
I just want to know if I’m doing this correctly all I would do is add to find the $x$ right  which would look like $5000(0.1)+450,000(0.005)=2750$

REPLY [1 votes]: You have correctly calculated the expected value the company will pay out.  That is not what the question asks, though it is what the title asks.  The question asks what amounts the company might pay.  There should be three or four of them.  I don't think the question is clear whether one of them is possible.


TITLE: Applying the mean value theorem to sine function
QUESTION [0 upvotes]: Prove that  $ \pi x\cos(\frac{1}{2}\pi x^2) = c$ has a solution in $0 < x< 1$ for $c=1$?
Is this true for all positive values of $c$?

I said define $f:[0,1] \to \mathbb{R}$ by $f(x) =\sin(\frac{1}{2}\pi x^2)-cx$. Then $f$ is (in particular) continuous on $[0,1]$ and differentiable on $(0,1)$ so by the MVT there exists $\xi \in (0,1)$ s.t. $f'(\xi) = \frac{f(1)-f(0)}{1-0} = 1-c$. But also since $f$ is differentiable we can write $f'(\xi) = \pi \xi \cos(\frac{1}{2}\pi \xi^2)-c$.
So there does exist a solution when $c=1$ since then $f'(\xi) =0$.
Is it right to say that since $f'(\xi) = 1-c \ne 0$ for any $c \ne 1$, the equation has no solutions for all other positive values of $c$?

REPLY [1 votes]: You properly showed that the maximum corresponds to
$$\pi  \cos \left(\frac{\pi  x^2}{2}\right)-\pi ^2 x^2 \sin \left(\frac{\pi
   x^2}{2}\right)=0$$
Let $\frac{\pi  x^2}{2}=y$ to reduce the problem to
$$\cos (y)-2 y \sin (y)=0$$ Use a series expansion around $y=0$ to get
$$\cos (y)-2 y \sin (y)=1-\frac{5 y^2}{2}+\frac{3 y^4}{8}-\frac{13 y^6}{720}+O\left(y^8\right)$$ which is a cubic in $y^2$.
It is has only one real root given by the hyperbolic method and then
$$y=\sqrt{\frac{1}{13} \left(90-20 \sqrt{3} \cosh \left(\frac{1}{3} \cosh
   ^{-1}\left(\frac{731 \sqrt{3}}{25}\right)\right)\right)}\approx 0.653266$$
while the exact solution, given by Newton method, is $0.653271$.
Just continue from here to have a quite good approximation.
Edit
Another possible solution could be to use the series expansion of
$$z=\cos (y)-2 y \sin (y) $$  and use series reversion to get
$$y^2=\sum_{n=0}^p a_n (z-1)^n$$ where the $a_n$ make the sequence
$$\left\{-\frac{2}{5},\frac{3}{125},-\frac{68}{28125},\frac{293}{984375},-\frac{1672}
   {41015625},\frac{5449628}{913623046875},-\frac{126516512}{138566162109375}\right
   \}$$ which is not recognized by $OEIS$.
Making $z=0$ leads to
$$y=\sqrt{\frac{177404762809276}{415698486328125}} \approx  0.65327105$$  while the exact solution is  $0.65327119$
This makes, as an approximation,
$$c_{max}=1.608836120431054$$ while its exact value should be $1.608836120431092$.
None of these numbers are recognized by inverse symbolic calculators.


text:
\section{Symbol notation and basic identities}

\subsection{Symbols}

We first  develop more compact notation for symbols, replacing  $d^{-1}$ with parentheses, $\wedge$ with juxtoposition,
and $\Lambda_\ell$ with $\ell$.

\begin{definition}
A {\bf pre-symbol} is a parenthesized word in a generating set (no inverses) such that
\begin{itemize}
\item There is exactly one fewer pair of parentheses than letters.
\item  Every pair of parentheses contains exactly one letter which is not further parenthesized, which we call its free letter.
\item Every pair of parentheses is either nested or disjoint.

\end{itemize}
\end{definition}

The third condition disambiguates repeated parentheses in the standard way.
The first two conditions imply that at least one
single letter is parenthesized by itself and one letter is unparenthesized, within any pair of parentheses with at least two letters as well as for the entire word.
Examples include   $a(b(c))$, $(a) b (c)$,  $(a(e)) (a) (c) b$, and $((a)(a)b)c$.

\begin{definition}

The {\bf depth} of a pre-symbol is the number of pairs of parentheses (one less than the length of the word).

A {\bf sub-(pre-)-symbol} of a pre-symbol  consists of either a  letter or a pair of parentheses and its contents.  The sub-(pre-)symbols
of a pre-symbol form a poset under {\bf containment}.
Two symbols are  {\bf equivalent} if  their containment posets are isomorphic, through an isomorphism which preserves labels.
\end{definition}

Thus for example $((a)(a)b)c$ is equivalent to $c((a)b(a))$.
Alternatively, equivalent  symbols can be obtained from one another by a series of permutations of the immediate contents
of any pair of parentheses, as well as permutation of outermost sub-symbols.  (One could have an  outmost set of parentheses
to make this and other aspects of symbols more uniform, but
we have chosen not to as the current definition seamlessly fits with our letter-linking definitions.)

Symbols are
reminiscent of parenthesizations in non-associative algebras such as Lie algebras, and the containment poset of a symbol is a rooted tree.
We will develop  a duality with Lie brackets, but this duality is not
based on such superficial similarity.

\begin{definition}
The shortened (pre-)symbol of a depth-$j$ list is obtained inductively as follows.
\begin{itemize}
\item The shortened symbol of $\Lambda_\ell$ is $\ell$.
\item If the shortened symbol of $L_a$ is $\sigma$ and that of $L_b$ is $\tau$ then the shortened symbol of $d^{-1} L_a \wedge L_b$ is $(\sigma) \tau$
-- that is, the shortened symbol of $L_a$ parenthesized and followed by that  of $L_b$.

\end{itemize}
\end{definition}

Equivalent symbols will give rise to isomorphic lists.
From now on, we use shortened (pre-)symbols to describe letter-linking invariants.

Recall that in our definition of linking of lists,
the lists in question must
be comprised of different letters.  We capture this condition as follows.

\begin{definition}
Consider a pair of parentheses in a pre-symbol, whose immediate contents are of the form $(\sigma_1) \ldots (\sigma_k) \ell$,
where each $\sigma_i$ is a symbol
and $\ell$ is the free
letter.  An almost-symbol is {\bf valid}  for this pair of parentheses if the free letters of $\sigma_i$ are all different from $\ell$.
Define a {\bf symbol} to be pre-symbol which is valid for all its pairs of parentheses.
\end{definition}

In other words, free letters may be repeated, but not at neighboring levels.

 \subsection{Homomorphism identities}

In Section~\ref{independence} we showed that the letter-linking functions $\Phi_\sigma$ are well
defined, but we should recall that they are only defined on subsets of the free group,
since the definition of $d^{-1} \Lambda_\mu \wedge \Lambda_\tau$
requires the vanishing of  $\Phi_\mu$.
 Always implicit in our statements of identities in this paper, in particular those in this section, is that equalities hold
 only where all quantities involved are defined.

 Recall that multiplication in free groups corresponds to concatenation of words, which we  denote by $w_1 \cdot w_2$.

\begin{proposition}
$\Phi_\sigma(w_1 \cdot w_2) = \Phi_\sigma(w_1) + \Phi_{\sigma}(w_2)$.
\end{proposition}

\begin{proof}
Inductively apply two facts.  First, when all defined, the coboundings on $w_1 \cdot w_2$ can be chosen to be the union of those on $w_1$ and $w_2$.
Secondly,  $\wedge$ distributes over union of coboundings.
\end{proof}

Recall that taking inverses in free groups corresponds to reversing the letters in a word and changing all intrinsic signs to their opposite,
which we denote by $w^{-1}$.

\begin{proposition}
$\Phi_\sigma(w^{-1}) = -\Phi_\sigma(w)$.
\end{proposition}

\begin{proof}
Define compatible involutions on lists and their coboundings by reversing letters and taking inverses, but leaving extrinsic signs unchanged.
Inductively we can choose $\Lambda_\sigma(w^{-1})$ as the image
of $\Lambda_\sigma(w)$ under this involution.  Under this involution,  counts of lists are multiplied by $-1$, as the orientations of
corresponding intervals
will not change (as they will change twice) while the signs of the corresponding letters will change.
\end{proof}

The homomorphisms $\Phi_\ell$, for a generator $\ell$, are  the composite of the map from the free group to its abelianization followed by
projection onto the $\ell$-summand of the abelianization.  We view the other homomorphisms
$\Phi_\sigma$ as derived from this abelianization.

\subsection{Leibniz identities}

 The geometry of intervals gives rise to key relations.

\begin{definition}
The {\bf intersection} $I \cap J$ of two oriented intervals is their intersection, with orientation given by the product of orientations.

If $S_i$, for $i = 1, \ldots, n$ are sets of intervals, define $\bigcap S_i$ to be $\bigcup_{I_1 \in S_1, \cdots, I_n \in S_n} I_1 \cap \cdots \cap I_n$.

\end{definition}

The following two facts are immediate from the definitions.

\begin{lemma}[Associativity]
$(I \cap J) \cap K = I \cap (J \cap K)$ and
$((x_i, \epsilon) \cap I) \cap J = (x_i, \epsilon) \cap ( I \cap J ).$
\end{lemma}

\begin{proposition}[Leibniz Rule]
$\partial (I \cap J) = (\partial I \cap J) \cup (I \cap \partial J$).  More generally
$$\partial \bigcap_{i = 1 \cdots n}  S_i = \bigcup_i S_1 \cap \cdots \cap S_{i-1} \cap \partial S_i \cap S_{i+1} \cap \cdots \cap S_n.$$
\end{proposition}

Here we are using  $\cap$ from Definition~\ref{intersection} for intersecting sets of signed letters with lists.

\begin{proposition}\label{arnoldgen}(Leibniz Relation)
$$\Phi_{\sigma_1 (\sigma_2) \cdots (\sigma_{k-1}) (\sigma_{k})}
+  \Phi_{(\sigma_1) \sigma_2  \cdots (\sigma_{k-1}) (\sigma_{k})} + \cdots
+  \Phi_{(\sigma_1) (\sigma_2)  \cdots \sigma_{k-1} (\sigma_{k})}
+  \Phi_{(\sigma_1) (\sigma_2)  \cdots (\sigma_{k-1}) \sigma_{k}} = 0.$$
\end{proposition}

The first two cases of this identity have distinct names.  The $k = 2$ case, which can be rewritten as
$\Phi_{(\sigma) \tau} = -\Phi_{\sigma (\tau)}$, is known as an antisymmetry relation.
It should be considered in contrast with the fact that by definition, or essentially by commutativity of intersection,
 $\Phi_{(\sigma) \tau} = \Phi_{\tau (\sigma)}$.  We call the $k=3$ case the Arnold identity, with the connection to the
 identity with the same name in topology, which figures prominently in our work in Section~\ref{mainsection}.

\begin{proof}[Proof of Proposition~\ref{arnoldgen}]
The relation follows from a slightly more general fact.  Let $a_1, \cdots, a_k$ be distinct letters, and $d^{-1} L_{a_i}$ coboundings of lists in those letters.
Because $\partial \bigcap_i d^{-1} L_{a_i}$ is the boundary of a collection of intervals, its count is zero.  Thus by the Leibniz rule
$$\phi(\bigcup_i (d^{-1}L_{a_1} \cap d^{-1}L_{a_2}  \cap \cdots \cap {\widehat{d^{-1}L_{a_i}}} \cap \cdots \cap d^{-1}L_{a_k}) \wedge L_{a_i}) = 0.$$
Setting $L_{a_i}$ to be $\Lambda_{\sigma_i}$ in this equality establishes the Leibniz Relation.
\end{proof}

\subsection{Commutator identities}

We start with a result which could independently be deduced from stronger results in the next section.  The current treatment motivates those
results and illustrates  the proof technique for the stronger Theorem~\ref{definedonlcs} below.

 \begin{proposition}\label{cobracket1}
 $\Phi_{(\sigma) \tau}  [v, w] = \Phi_{\sigma}(v) \Phi_\tau(w) -  \Phi_\tau(v) \Phi_\sigma(w).$
 \end{proposition}

\begin{proof}

By convention $\Phi_\sigma(v)$ and $\Phi_{\sigma}(w)$ are defined, and thus so are $\Phi_\sigma(v^{-1})$ and $\Phi_{\sigma}(w^{-1})$.
We use the  lists and cobounding intervals which define them to produce the list $\Lambda_\sigma(vwv^{-1}w^{-1})$ as the union of
lists identified with $\Lambda_\sigma(v)$, $\Lambda_\sigma(w)$, $\Lambda_\sigma(v^{-1})$, and $\Lambda_\sigma(w^{-1})$, which
we also assume to be chosen to respect the inverse involution.
Call the generator in these lists $a$.  The inverse involution matches occurrences of
$a^{\pm 1}$ in $\Lambda_\sigma(v)$ with those
of $a^{\mp 1}$ in $\Lambda_\sigma(v^{-1})$ and similarly for $w$, $w^{-1}$, through which we choose our cobounding $d^{-1} \Lambda_\sigma([v,w])$.
  Similarly choose $\Lambda_\tau([v,w])$ as the union of lists which can be identified with
  $\Lambda_\tau(v)$, $\Lambda_\tau(w)$, $\Lambda_\tau(v^{-1})$, and $ \Lambda_\tau(w^{-1})$.  See Figure~\ref{secondfigure} for a schematic.

\begin{figure}[h]
\includegraphics[width=10cm]{Commutator_Computation.eps}
\caption{Schematic  for Proposition~\ref{cobracket1}.  \\
 $\Lambda_\sigma(v)$ \& $\Lambda_\sigma(v^{-1})$ are denoted by red circles;
$\Lambda_\sigma(w)$ \& $\Lambda_\sigma(w^{-1})$ by blue circles; $\Lambda_\tau(v)$ \& $\Lambda_\tau(v^{-1})$ by  green squares;
 $\Lambda_\tau(w)$ \& $\Lambda_\tau(w^{-1})$ by orange squares. }\label{secondfigure}
\end{figure}

With these choices  consider  $d^{-1} \Lambda_\sigma([v,w]) \wedge  \Lambda_\tau([v,w])$, starting with the intervals which cobound
across $v$ and $v^{-1}$.  Such intervals do not intersect $\Lambda_\tau(w^{-1})$.  Their intersections with $\Lambda_\tau(v)$ and
$\Lambda_\tau(v^{-1})$ are matched under
the inverse involution we have used to define our lists.  And these intervals have full intersections with $\Lambda_\tau(w)$, yielding a total contribution
of $\Phi_\sigma(v) \cdot \Phi_\tau(w)$ to $\Phi_{(\sigma) \tau}  [v, w]$.

Analysis of the coboundings across $w$ and $w^{-1}$ are similar, with only intersections
with $\Lambda_{\tau}(v^{-1})$ contributing, yielding $ -  \Phi_\tau(v) \Phi_\sigma(w).$
\end{proof}

\begin{definition}
Let $G$ be a group.  Inductively define the lower central series of groups by $\gamma_i G = [\gamma_{i-1} G, G]$, with $\gamma_0 G = G$.
Inductively define the derived groups by $G^{(i)} = [G^{(i-1)}, G^{(i-1)}]$,  with $G^{(0)} = G$.
\end{definition}

We may inductively apply Proposition~\ref{cobracket1}, starting with the immediate fact that $\Phi_\ell$  vanishes on commutators, to see that
$\Phi_\sigma$ vanishes on the derived group $F_n^{(i)}$ for $i$  greater than the depth of $\sigma$.

But we  now show that the letter-linking functions $\Phi_\sigma$  in fact vanish on the  lower central series.

\begin{theorem}\label{definedonlcs}
If the depth of a symbol is less than $i$, then the corresponding letter-linking invariant vanishes on $\gamma_i F_n$.  Thus if
the depth of $\sigma$ is equal to $i$, $\Phi_\sigma$ is defined on $\gamma_i F_n$.
\end{theorem}

\begin{proof}
We argue inductively, starting with the immediate fact that $\Phi_\ell$ vanishes on commutators.

Let $\sigma$ be a symbol of depth $i-1$.  Let $w \in \gamma_{i-1} F_n$ and $v \in F_n$, so $[w^{-1}, v]$ represents
an element of $ \gamma_i F_n$,
and consider $\Phi_\sigma ([w^{-1} ,v]) = \Phi_\sigma ( w^{-1} v w v^{-1} )$.  As $\Phi_\sigma$ is defined on $w$ and $w^{-1}$ we choose
to construct $\Lambda_\sigma [w^{-1},v]$ starting with $\Lambda_\sigma w$ and $\Lambda_\sigma w^{-1}$, whose counts  will cancel.

We complete $\Lambda_\sigma [w,v]$ through a construction of  $\Lambda_\sigma v w  v^{-1} \backslash \Lambda_\sigma w$,
which allows us to show the  count vanishes.
Such a construction is the ultimate  case of a second inductive claim that for any symbol $\tau$ of
depth less than or equal to $i-1$, the list
$\Lambda_\tau v w v^{-1} \backslash \Lambda_\tau w$ is defined and is comprised of letters with particular forms in
$v \cup v^{-1}$ and $w$, namely:
\begin{itemize}
\item The letters in $v \cup v^{-1}$   are preserved under the $v$-$v^{-1}$ involution.
\item The letters in $w$  are a union of  lists $\Lambda_{\hat{\tau}_k} w$ for some collection of symbols
$\{ \hat{\tau}_k \}$ each of depth less than that of $\tau$.
\end{itemize}
For brevity we call lists of letters in $v \cup v^{-1}$ and in $w$ with these properties type-one and type-two, respectively.
Type-one pairs immediately have zero count, and type-two letters have zero count as well since each
$\Lambda_{\hat{\tau}_k} w$ has zero count by our
primary inductive hypothesis.

We prove this second claim through an induction on the depth of $\tau$.
We may use the vanishing statement of our theorem  up to depth $i - 2$.
For depth zero, $\Lambda_\ell v w v^{-1} \backslash \Lambda_\ell w$ consists of occurrences of $\ell$ in $v v^{-1}$, which
indeed occur in pairs preserved under involution, and thus is comprised entirely of type-one letters.

Next assume $\tau = (\mu_1) \mu_2$ where the claim has been verified for the $\mu_i$.  We choose the cobounding of the type-one subset of
$\Lambda_{\mu_1} v w v^{-1} \backslash \Lambda_{\mu_1}w$ by cobounding pairs which correspond with one another under involution.
We then cobound the type-two pairs, a cobounding which exists by inductive assumption because the depth of $\mu_1$ is less than $i-1$.
Consider the four cases for intersection arising in
 $(d^{-1} \Lambda_{\mu_1} v w v^{-1} \backslash d^{-1} \Lambda_{\mu_1} w) \wedge
(\Lambda_{\mu_2} v w v^{-1} \backslash  \Lambda_{\mu_2} w)$:

\begin{itemize}
\item The intersection of type-one pairs in $\Lambda_{\mu_2} v w v^{-1} \backslash \Lambda_{\mu_2} w$ with  type-one
cobounding intervals in $d^{-1} \Lambda_{\mu_1} v w v^{-1} \backslash  d^{-1} \Lambda_{\mu_1} w^{-1}$
is a collection of type-one pairs.
\item The intersection of a type-one cobounding interval for $\mu_1$ with any list of letters in $w$, in particular any of
the $\Lambda_{\hat{\mu_2}_k w}$, is the list itself.  Thus the intersection of all such cobounding intervals  with a union of
 $\Lambda_{\hat{\mu_2}_k w}$ is another such union.  Because the depth of $\hat{\mu_2}_k$ is less than that of $\mu_2$ it is less
 than that of $\tau$.
 \item Type-two cobounding intervals are contained in $w$, so their intersection with type-one pairs is empty.
 \item The intersection of type-two cobounding intervals from some $d^{-1} \Lambda_{\hat{\mu_1}_j} w$ with all the type-two pairs
 from some $\Lambda_{\hat{\mu_2}_k} w$ is by definition $\Lambda_{(\hat{\mu_1}_j) \hat{\mu_2}_k} w $.  Thus the union of all
 such intersections is the union of lists $\Lambda_{\hat{\tau}_\alpha} w$.
\end{itemize}

With this second induction step and thus the second induction claim established, we apply it for $\tau = \sigma$.  We deduce
that the count of $\Lambda_\sigma v w v^{-1} \backslash \Lambda_\sigma w$ is zero, completing our main induction.
\end{proof}

\begin{corollary}\label{lcsdefined}
The $\Phi_\sigma$ of depth $i$ are well defined on the lower central series subquotients $\gamma_i F_n / \gamma_{i+1} F_n$.
\end{corollary}

config: arxiv


TITLE: Projective plane, fixed point
QUESTION [0 upvotes]: How to show, that for every continuous $f:  X\rightarrow X$ there exists $x \in X$, such that $f(x) = x$, where X is a real projective plane $\mathbb{R}P^2$.
In other words: every continuous map of RPP to itself has a fixed point.
EDIT
Probably it's easier to proof, that existence of fixed point in map from $S^2$ to itself implies needed fact.

REPLY [0 votes]: As mentioned in the comments, this link reduces your question to the following implication, which you said you don't know how to do:

(1) for any continuous map $f : S^{2n} \to S^{2n}$ there exists $x \in S^{2n}$, such that $f(x) =x$ or $f(x) = -x$;

implies

(2) any continous map $g: \mathbb R P^{2n} \rightarrow \mathbb RP^{2n}$ has a fixed point.

To prove this implication, given a continuous $g: \mathbb R P^k \rightarrow \mathbb RP^k$, define $f : S^k \to S^k$ as follows. First, let $p : S^k \to \mathbb R P^k$ be the universal covering map. By composition we obtain $g \circ p : S^k \to \mathbb R P^k$. Applying the general lifting lemma, we obtain a continuous map $f = \widetilde{g \circ p} : S^k \to S^k$ such that $p \circ f = g \circ p$. Applying (1), we obtain $x$ such that $f(x)=x$ or $f(x)=-x$, and it follows that
$$g(p(x)) = p(f(x)) = p(\pm x) = p(x)
$$
and so $p(x)$ is the required fixed point of $g$.


TITLE: An explicit separation between time-constructibility and space-constructibility?
QUESTION [11 upvotes]: Show a function $f(n)$ which is space-constructible but not time-constuctible.
Is this problem related to a possible separation between complexity classes DTIME(f(n)) and SPACE(f(n))?

REPLY [2 votes]: If all space-constructible functions are time-constructible, then $EXP-TIME=EXP-SPACE$. To prove that (and to give an example of a non-trivial space-constructible but presumably not time-constructible function), let us take an arbitrary (possibly $EXP-SPACE-COMPLETE$) problem $L\in EXP-SPACE$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a DTM $M$ in $2^{n^k}$ space. Now define the function
$$f(n)=\left\{\begin{array}{ll}
  8n+2  & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\
  8n+1 & \mbox{else}
 \end{array}
\right.$$
The condition can be decided in $2n$ space, thus $f$ is space-constructible. If $f$ was time constructible, then it is easy to see that we could solve $L$ in exponential time.
This answer uses the same idea.


TITLE: Finding angle in a triangle with one median and an isosceles triangle in it
QUESTION [6 upvotes]: In the following figure $AF=BD=DC$ and $AE=EF$. Find the angle $\alpha$.

I tried so many different things (constructing triangles, drawing parallel lines, using Ceva theorem in triangles $ABD$ and $CBE$, ...). Any help for solving this will be much appreciated.
A geomtrical solution (without trigonometry) would be very nice.

REPLY [4 votes]: Here is a purely geometric proof without any trigonometry.

Draw the three lines $a, \, b, \, c$ such that:
$$A \, \in \, a \,\,\text{ and } \,\, a \, || \, BC$$
$$B \, \in \, b \,\,\text{ and } \,\, b \, || \, CA$$
$$C \, \in \, c \,\,\text{ and } \,\, c \, || \, AB$$
Furthermore, let
$$B^* \, = \, a \, \cap \, c \,\,\, \text{ and } \,\,\, A^* = b \, \cap \, c$$
Then, $ABA^*C$ and $ABCB^*$  are parallelograms and furthermore
$$AB = CA^* = CB^*$$ as well as
$$AB^* = BC$$
Apply Menelaus' theorem to the triangle $BCE$ intersected by the line that passes through the collinear points $A, \, F,\, D$:
$$\frac{AB}{AE} \cdot \frac{EF}{CF} \cdot \frac{DC}{BD} = 1$$
Since by assumption $AE = EF$ and $BD = CD$, one concludes that
$$AB = CF$$
Combining this latter fact with the earlier conclusions, one observes that
$$CF = AB = CA^* = CB^*$$ which is possible if and only if triangle $\Delta \, A^*B^*F$ has $90^{\circ}$ angle at vertex $F$, i.e. $\angle \, A^*FB^* = 90^{\circ}$. But that means that:
$$\angle \, AFB^* = 180^{\circ} - \angle \, A^*FB^* = 180^{\circ} - 90^{\circ} = 90^{\circ}$$
Recall that by assumption $AF = BD = DC = \frac{1}{2}\,BC$. But by construction, $ABCB^*$ is a parallelogram and $AB^* = BC$ so
$$\Delta \, AFB^*  \, \text{ is a triangle with the properties that } \, \angle \, AFB^* = 90^{\circ} \,\, \text{ and } \,\, AF = \frac{1}{2}\, AB^* $$
which is possible if and only if $$\angle \, FAB^* = 60^{\circ}$$
However, $AB^*$ is parallel to $BC$ and consequently, by the properties of a pair of parallel lines intersected by a third line,
$$\angle \, ADB = \angle \, DAB^* = \angle \, FAB^* = 60^{\circ}$$


text:
\begin{document}

\title{On sums of coefficients of Borwein type polynomials over arithmetic progressions}

\author{Jiyou Li}
\address{Department of Mathematics, Shanghai Jiao Tong University, Shanghai, P.R. China}
\email{lijiyou@sjtu.edu.cn}

\thanks{This work was supported in part by the National Science Foundation of China (11771280).}
\author{Xiang Yu}
\address{Department of Mathematics, City University of Hong Kong, Kowloon Tong, Hong Kong}
\email{xianyu3-c@my.cityu.edu.hk}
\maketitle

\begin{abstract}
	We obtain asymptotic formulas for sums over arithmetic progressions of coefficients of polynomials of the form
	$$\prod_{j=1}^n\prod_{k=1}^{p-1}(1-q^{pj-k})^s,$$
	where $p$ is an odd prime and $n, s$ are positive integers. Let us denote by $a_i$ the coefficient of $q^i$ in the above polynomial and suppose that  $b$ is an integer. We prove that
		$$\Big|\sum_{i\equiv b\mmod 2pn}a_i-\frac{v(b)p^{sn}}{2pn}\Big|\leq p^{sn/2},$$
		where $v(b)=p-1$ if $b$ divisible by $p$ and $v(b)=-1$ otherwise. This improves a recent result of Goswami and Pantangi \cite{GP}.
\end{abstract}

\section{Introduction}

For an odd prime $p$ and positive integers $n, s$, let  the sequence $(a_i)$ be defined by
\begin{equation}\label{eq:P}
\Big(\frac{(q;q)_{pn}}{(q^p;q^p)_n}\Big)^s=\sum_{i=0}^{sn^2(p-1)p/2} a_i q^i,
\end{equation}
where here and henceforth we use the standard definition of $q$-shifted factorial:
$$
(a;q)_0=1,\quad (a;q)_n=\prod_{k=1}^{n-1}(1-aq^k),\quad n\geq 1.$$

 In 1990, Peter Borwein discovered some intriguing sign patterns of the coefficients $a_i$ for three different cases $(p, s)=(3, 1), (3, 2), (5, 1)$. They have three  repeating sign patterns of $+--$, $+--$ and $+----$, respectively.
Equivalently, the sign of $a_i$ is determined by $i$ modulo $p$.
These conjectures were formalized by Andrews in 1995 \cite{GA}.

\begin{conjecture}[First Borwein conjecture]
	For the polynomials $A_n(q)$, $B_n(q)$ and $C_n(q)$ defined by
	$$
	\frac{(q;q)_{3n}}{(q^3;q^3)_n}=A_n(q^3)-qB_n(q^3)-q^2C_n(q^3),$$
	each has non-negative coefficients.
\end{conjecture}

\begin{conjecture}[Second Borwein conjecture]
	For the polynomials $\alpha_n(q)$, $\beta_n(q)$ and $\gamma_n(q)$ defined by
	$$
	\Big(\frac{(q;q)_{3n}}{(q^3;q^3)_n}\Big)^2=\alpha_n(q^3)-q\beta_n(q^3)-q^2\gamma_n(q^3),$$
	each has non-negative coefficients
\end{conjecture}

\begin{conjecture}[Third Borwein conjecture]
	For the polynomials $v_n(q),\phi_n(q),\chi_n(q),\psi_n(q)$ and $\omega_n(q)$ defined by
	$$ \frac{(q;q)_{5n}}{(q^5;q^5)_n}=v_n(q^5)-q\phi_n(q^5)-q^2\chi_n(q^5)-q^3\psi_n(^5)-q^4\omega_n(q^5),$$
	each has non-negative coefficients.
\end{conjecture}

Many attempts have been made to prove these conjectures, including several important generalizations; see for instance
\cite{GA, Be, BW, BS, B, IKS, RP, W1, W2, AZ}.    However, all these conjectures had been open for many years.
It was not until 2019 that  Wang \cite{CW} first gave an analytic proof of the first Borwein conjecture using the saddle point method and a formula discovered by Andrews [\cite{GA}, Theorem 4.1] for the polynomials $A_n(q), B_n(q)$ and $C_n(q)$. It is not clear whether his method  can be applied to other conjectures.  Even for the first Borwein conjecture, a combinatorial or algebraic proof would be  very interesting.

Instead of evaluating $a_i$ directly, it is natural to consider the sums  of the coefficients of polynomials in the Borwein conjectures over arithmetic progressions. Let $d$ be a positive integer divisible by $p$ and let $b$ be an integer. If we define $$
S_{d,b}:=\sum_{i\equiv b \mmod d}a_i,$$

then the positivity (negativity) part of the Borwein conjectures follows from the positivity (negativity, respectively) of $S_{d, b}$ for sufficiently large $d$, for example, $d> sn^2(p-1)p/2$. Please note that here $S_{d,b}$ should be $S_{p, s,n, d,b}$. For notational simplicity, the subscripts $p$, $s$ and $n$ are omitted when there is no confusion.

Using estimates of exponential sums, Zaharescu \cite{AZ} first studied $S_{d, b}$ for a large class of $d$. Let us denote by $[x]$ and $\{x\}$ the usual integer part and fractional part of a real number $x$, respectively. For an integer $b$, define $v(b)=p-1$ if $b$ is divisible by $p$ and $v(b)=-1$ otherwise. Zaharescu proved the following result.
\begin{theorem}[Zaharescu]
Let $s,n$ be positive integers, let $p,q$ be two distinct odd primes with $q\leq n$, and let $b$ be an integer number. Then
	$$
	\Big|S_{pq,b}-\frac{v(b)p^{sn}}{pq}\Big|\leq \frac{(p-1)(q-1)p^{s[n/q]-1}2^{sq(p-1)\{n/q\}}}{q}.
	$$
\end{theorem}
For instance, when $(p,s)=(3,1)$, Zaharescu's bound gives
$$
\Big|S_{3q,b}-\frac{2\cdot 3^n}{3q}\Big|\leq \frac{2(q-1)3^{[n/q]-1}2^{2q \{n/q\}}}{q}
$$
for $b$ divisible by $3$. Note that to ensure that this bound is nontrivial, $q$ must be a prime no greater than $n$.

For the case $(p,s)=(3,1)$, Li \cite{Li} removed the condition that $q$ is a prime and in fact obtained an estimate with a very small error bound.
He showed that
\begin{theorem}[Li]
	Fix $p=3$, $s=1$.  Let $n,b $ be integers with $n\geq 1$. Then
	$$ \left|S_{3n, b}-\frac{v(b) 3^n}{3n}\right|\leq   2^{n}.$$
\end{theorem}

Goswami and Pantangi \cite{GP} generalized this bound to general cases $(p, s)$ and $d=pn$ following Li's argument and Li--Wan's sieving argument. They proved the following result.
\begin{theorem}[Goswami and Pantangi]
	Let $p$ be an odd prime, and let  $n, b$ be integers with $n\geq 1$.  Then
	$$
	\Big|S_{pn, b}-\frac{v(b) p^{sn}} {pn}\Big|\leq p^{sn/2}.
	$$
\end{theorem}

In this paper, we improve Goswami and Pantangi's result to arithmetic progressions with a larger common difference of $2pn$. Our main result is the following:
\begin{theorem}\label{thm:main}
     Let $p$ be an odd prime, and let $n, b$ be integers with $n\geq 1$. Then
	$$\Big|S_{2pn, b}-\frac{v(b)p^{sn}}{2pn}\Big|\leq p^{sn/2}.$$
\end{theorem}

\begin{corollary}
  For an odd prime $p$ and an integer $b$, define
  $$ N_{p,s,b}:=\begin{cases}
  \inf \{n\in \N: (p-1)p^{sn/2-1}>2n\},& \text{if}\ p\mid b;\\
  \inf\{n\in\N: p^{sn/2-1}>2n\},& \text{otherwise}.
  \end{cases}$$
  Then for all $n\geq N_{p,s,b}$, we have
  $$
  S_{2pn, b}\begin{cases}
  >0, & \text{if}\ p\mid b;\\
  <0, & \text{otherwise}.
  \end{cases}
  $$
\end{corollary}

The main idea of this paper is to shift the problem to a subset-sum type problem (see Section \ref{sec:reduction}), which can be handled by the Li--Wan sieve. We remark that both Goswami and Pantangi's argument and ours rely on the algebraic structures of certain sets in the additive groups $\Z/pn\Z$  and $\Z/2pn\Z$, respectively. When $d$ becomes larger than $2pn$, the argument does not work due to the lack of the algebraic structure. To give a reasonable bound of $S_{b,d}$ for large $d$, one has to obtain non-trivial estimates for exponential sums over a small subset of the additive group $\Z/d\Z$, which in general is a difficult problem in number theory.

This paper is organized as follows. In Section 2, we reduce the problem to a subset-sum type problem. The Li--Wave sieve is introduced in Section 3 and some useful lemmas are presented in Section 4. Finally, in Section 5, we prove our main result.

{\bf Notation.} The congruence notion $a\equiv b\ {\rm mod}\ n$ means $a-b$ is divisible by $n$. We use  $|E|$ to denote the cardinality of the set $E$. If $F(x)=\sum_{n=0}^\infty a_nx^n$ is a formal power series, then we use $[x^n]F(x)=a_n$ to denote the coefficient of $x^n$ in $F(x)$. If $S$ is a statement, we use $1_S$ to denote the indicator function of $S$, thus $1_S = 1$ when $S$ is true and $1_S$ = 0 when $S$ is false.

\section{Reduction to a subset-sum type  problem}\label{sec:reduction}

As in \cite{Li} and \cite{GP}, we first reduce the problem to a subset-sum type  problem over the additive group of integers modulo $2pn$. The starting point is the equality $(1-q^j)=-q^j(1-q^{-j})$, allowing us to write  \eqref{eq:P} as
\begin{align}\label{eq:PP}
\Big(\frac{(q;q)_{pn}}{(q^p;q^p)_n}\Big)^s=\quad(-1)^{sn(p-1)/2}q^{e}\prod_{j=-(n-1)}^n\prod_{k=1}^{(p-1)/2}(1-q^{pj-k})^s.
\end{align}
where $e=e_{p,s,n}=sn(p-1)(2pn+1-p)/8$. If we denote by $b_{i}$ the coefficient $q^i$ in the Laurent polynomial
$$
b_i=[q^i]\prod_{j=-(n-1)}^n\prod_{k=1}^{(p-1)/2}(1-q^{pj-k})^s,$$
then we deduce from \eqref{eq:PP} that $a_{i}=(-1)^{sn(p-1)/2} b_{i-e}$. In particular, we have
\begin{align}\label{eq:ab}
S_{2pn,b}=\sum_{i\equiv b\ {\rm mod}\ {2pn}} a_{i}= (-1)^{sn(p-1)/2} \sum_{i\equiv b-e\ {\rm mod}\ {2pn}} b_{i}.
\end{align}

On the other hand, let $D$ denote the set
\begin{align}\label{eq:D}
D=\{pj-k:-(n-1)\leq j\leq n,\ 1\leq k\leq \frac{p-1}{2}\}.
\end{align}
Given integers $0\leq m_i\leq |D|$, $1\leq i\leq s$ and $b$,  define the quantity $N_D(m_1,m_2,\dots,m_s,b)$ as
$$
N_{D}(m_1,m_2,\dots,m_s,b):=|\{(V_1,V_2,\dots,V_s): V_i\subset D,\ |V_i|=k_i,\ 1\leq i\leq s,\ \sum_{i=1}^s\sum_{x\in V_i}x\equiv b\ {\rm mod}\ 2pn\}|.
$$
That is, $N_{D}(m_1,m_2,\dots,m_s,b)$ is the number of ordered $s$-tuples of subsets of $D$ with cardinalities $m_i$, $1\leq i\leq s$ whose elements sum to $b$. The well-known subset-sum problem is to count the number of subsets with prescribed cardinality whose elements sum to a given element. Thus the problem of counting $N_{D}(m_1,m_2,\dots,m_s,b)$ can be viewed as a generation of the subset-sum problem and it is the usual subset-sum problem when $s=1$.
  To study the parity property of $N_D(m_1,m_2,\dots,m_s,b)$,  we define $N_D(b)$ to be their alternating sum
\begin{align}\label{eq:ND}
N_D(b):=\sum_{0\leq m_i,\dots,m_s\leq |D|}(-1)^{\sum_{i=1}^s m_i}N_{D}(m_1,m_2,\dots,m_s,b).
\end{align}

Clearly, we have $N_D(b)=\sum_{i\equiv b\ {\rm mod}\ {2pn}} b_i$, which together \eqref{eq:ab} leads to
\begin{align}\label{eq:Sb}
S_{2pn,b}= (-1)^{sn(p-1)/2}N_D(b-e).
\end{align}
The above equality establishes a connection between $S_{2pn,b}$ and $N_D(b)$, and the main problem is then reduced to counting $N_{D}(b)$ or more precisely to counting $N_D(m_1,m_2,\dots,m_s,b)$, which is  a subset-sum type problem over the additive group of integers modulo $2pn$ that can be computed by the sieve formula of Li and Wan.

\section{The Li--Wan sieve}

For the purpose of the proof, we briefly introduce  the Li--Wan sieve \cite{Li2}. Suppose that $m$ is a positive integer and  $A$ is a finite set. Let $A^m$ be the Cartesian product of $m$ copies $A$. For subset $X$  of $A^m$, let $\overline{X}$ be the set of elements in $X$ with distinct coordinates
$$
\overline{X}=\{(x_1,x_2,\dots,x_m)\in X:x_i\neq x_j,\ \forall\, i\neq j\}.
$$
A sieve formula discovered by Li and Wan \cite{Li2} gives an approach to computing $|\overline{X}|$  through a simpler way than the usual inclusion-exclusion sieve.  The new sieve formula
shows that there exists a large number of cancellations in the summation in the inclusion-exclusion principle. The number of terms in the summation is significantly reduced from $2^{{m \choose 2}}$ to $m!$.

 Let $S_m$ be the symmetric group on the set $\{1,2,\dots,m\}$. Given a permutation $\tau\in S_m$, we can write it a product disjoint cycles $\tau=C_1C_2\cdots C_{c(\tau)}$, where $c(\tau)$ denotes the number of disjoint cycles of $\tau$. We define the signature of $\tau$ to be $\sign(\tau)=(-1)^{m-c(\tau)}$. We also define the set $X_\tau$ to be
$$
X_\tau=\{(x_1,x_2,\dots,x_m)\in X:x_i\ \text{are equal for}\ i\in C_j, 1\leq j\leq c(\tau)\}.
$$
In other words, $X_\tau$ is the set of elements in $X$ that are invariant under the action of $\tau$ defined by $\tau \circ (x_1,x_2,\dots,x_m):=(x_{\tau(1)},x_{\tau(2)},\dots,x_{\tau(m)})$.  The Li--Wan sieve gives a formula for calculating sums over $\overline{X}$ via sums over $\overline{X}_\tau$.
\begin{theorem}[\cite{Li2}, Theorem 2.6]\label{thm:Li-Wan}
	Let $f:X\to \mathbb{C}$ be a complex-valued function defined over $X$. Then we have
	\begin{align*}
	\sum_{x\in\overline{X}} f(x)=\sum_{\tau\in S_m}\sign(\tau)\sum_{x\in X_\tau}f(x).
	\end{align*}
\end{theorem}

A permutation $\tau\in S_m$ is said to be of type  $(c_1,c_2,\dots,c_m)$ if it has exactly $c_i$ cycles of length $i$, $1\leq i\leq m$. Let $N(c_1,c_2,\dots,c_m)$ denote the number of permutations of type $(c_1,\dots,c_m)$. By the orbit-stabilizer theorem, we have the well-known formula
\begin{align}\label{eq:N}
N(c_1,c_2,\dots,c_m)=\frac{m!}{1^{c_1}c_1!2^{c_2}c_2!\cdots m^{c_m}c_m!}.
\end{align}
If we define an $m$-variate polynomial $Z_m$ via
$$
Z_m(t_1,t_2,\dots,t_m)=\frac{1}{m!}\sum_{\sum ic_i=m}N(c_1,c_2,\dots,c_m)t_1^{c_1}t_2^{c_2}\cdots t_m^{c_m},$$
then it follows from \eqref{eq:N} that $Z_m$ satisfies the generating function
\begin{align}\label{eq:exp}
\sum_{m\geq 0}Z_m(t_1,t_2,\dots,t_m)u^m=\exp\Big(t_1u+t_2\frac{u^2}{2}+t_3\frac{u^3}{3}+\cdots\Big).
\end{align}

\section{Some useful lemmas}

In this section, we present some lemmas that will be used later.
\begin{lemma}[\cite{Li}, Lemma 2.3]\label{lem:a}
Suppose that $\ell$ is a positive integer with	$1\leq \ell\leq m$. If $t_i=a$ if $\ell\mid i$ and $t_i=0$ otherwise, then we have
\begin{align*}
Z_m(t_1,t_2,\dots,t_m)=Z_m(\underbrace{0,\dots,0}_{\ell-1},a,\underbrace{0,\dots,0}_{\ell-1},a,\dots)=[u^m]{(1-u^\ell)^{-a/\ell}}.
\end{align*}

\end{lemma}

\begin{lemma}\label{lem:b}
	Suppose that $\ell $ is a positive integer with	$1\leq \ell \leq m$, and that  $B$ be a finite set of complex numbers. If $t_i=\sum_{z\in B}z^{i}a$ for $\ell \mid i$ and $t_i=0$ otherwise, then we have
	\begin{align*}
	&Z_m(t_1,t_2,\dots,t_m)=Z_m(\underbrace{0,\dots 0}_{\ell-1},\sum_{z\in B}z^\ell a,\underbrace{0,\dots,0}_{\ell-1},\sum_{z\in B}z^{2\ell}a,\dots)=[u^m]\prod_{z\in B}(1-z^\ell u^\ell)^{-a/\ell}.
	\end{align*}
\end{lemma}
\begin{proof}
	Substituting the values of $t_i$ into \eqref{eq:exp}, we see that
	\begin{align*}
	Z_m(t_1,t_2,\dots,t_m)&=
	[u^m] \exp\Big(a\sum_{i=1}^\infty \frac{\sum_{z\in B}z^{\ell i} u^{\ell i}}{\ell i}\Big)\\
	&=[u^m] \exp\Big(-\frac{a}{\ell}\sum_{z\in B}\log (1-z^\ell u^\ell )\Big)\\
	&=[u^m]\prod_{z\in B}(1-z^\ell u^\ell)^{-a/\ell}.
	\end{align*}
\end{proof}

\begin{lemma}\label{lem:c}
Suppose that $p$ is an odd prime and $n$ is a positive integer. 	Let $G=\Z/2pn\Z$ be the additive group of order $2pn$, and let $D$ be the set defined  in \eqref{eq:D}. For a positive integer $m$, let $X=D^m$ and
   define the character sum $S_m(\chi)$ by
	\begin{align}\label{eq:Smchi}
	S_m(\chi)=\frac{1}{m!}\sum_{(x_{1},x_{2},\dots,x_{m})\in \overline{X}}\chi(x_{1})\chi(x_{2})\cdots\chi(x_{m}),
	\end{align}
	for a character $\chi:G\to\myC$ on $G$.
	Denote by $o(\chi)$ the order of the character $\chi$. Then we have
	$$
	S_m(\chi)=\begin{cases}
	(-1)^m [u^m] (1-u^{o(\chi)})^{\frac{|D|}{o(\chi)}}, & \text{if}\ p\nmid\ o(\chi);\\
	(-1)^m[u^m] \prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k) u^{\frac{o(\chi)}{p}})^{\frac{|G|}{o(\chi)}},& \text{if}\ p \mid \ o(\chi).
	\end{cases}$$
\end{lemma}
\begin{proof}
	Using  Theorem \ref{thm:Li-Wan}, we can write $S_m(\chi)$ as
	\begin{align}\label{eq:S1}
	S_m(\chi)=\frac{1}{m!}\sum_{\tau\in S_k}\sign(\tau)\sum_{(x_1,x_2,\dots,x_m)\in X_\tau}\chi(x_1)\chi(x_2)\cdots\chi(x_m).
	\end{align}
	Let $\tau=C_1\cdots C_{c(\tau)}$ be a disjoint cycle product of $\tau$. Then from the definition of $X_\tau$, we see that
	\begin{align}\label{eq:S2}
	\sum_{(x_1,x_2,\dots,x_m)\in X_\tau}\chi(x_1)\chi(x_2)\cdots\chi(x_m)=\prod_{i=1}^{c(\tau)} \Big(\sum_{x\in D} \chi^{\ell_i}(x)\Big),
	\end{align}
	where $\ell_i$ denotes the length of the cycle $C_i$, $1\leq i\leq c(\tau)$.

	Let $[D]$ denote the image of $D$ under the quotient map $q:\Z\to G$ that sends $a$ to $a+2pn\Z$. We observe from \eqref{eq:D} that $[D]$ is a disjoint union of translations of the subgroup $pG$, where $pG=\{pg:g\in G\}$. Precisely, we have $[D]=\bigcup_{k=1}^{(p-1)/2}(pG-k)$, which implies that
	$$
	\sum_{x\in D}\chi(x)=\sum_{k=1}^{(p-1)/2}\sum_{x\in pG}\chi(x-k)=\Big(\sum_{k=1}^{(p-1)/2}\overline{\chi}(k)\Big)\sum_{x\in pG}\chi(x).
	$$
   The sum $\sum_{x\in pG}\chi(x)$ vanishes unless $\chi$ is a trivial character on $pG$ for which $o(\chi)=1$ or $p$. This implies that
   \begin{itemize}
		\item if $o(\chi)\neq 1,p$, then $\sum_{x\in D}\chi(x)=0$;
		\item if $o(\chi)=1$, then $\sum_{x\in D}\chi(x)=|D|$;
		\item if $o(\chi)=p$, then $\sum_{x\in D}\chi(x)=(\sum_{k=1}^{(p-1)/2}\overline{\chi}(k))|G|/p$.
	\end{itemize}
	It follows from the above classification that in the case $p\nmid o(\chi)$,  $\sum_{x\in D} \chi^{i}(x)=|D|$ if $o(\chi)\mid i$ and $\sum_{x\in D} \chi^{i}(x)=0$ otherwise; in the case $p\mid o(\chi)$,  $\sum_{x\in D}\chi^{i}(x)=(
	\sum_{k=1}^{(p-1)/2}\overline{\chi}^{i}(k))|G|/p$ if $\frac{o(\chi)}{p}\mid i$ and $\sum_{x\in D} \chi^{i}(x)=0$ otherwise. Thus we have two cases.

	{\bf Case 1: $p\nmid o(\chi)$.} In this case, we have $\sum_{x\in D}\chi^{i}(x)=|D|1_{o(\chi)\mid i}$. From \eqref{eq:S1} and \eqref{eq:S2}, we deduce that
	\begin{align*}
	S_m(\chi)&=\frac{1}{m!}\sum_{\tau\in S_m}\sign(\tau)\prod_{i=1}^\ell \Big(\sum_{x\in D} \chi^{\ell_i}(x)\Big)\\
	&=\frac{1}{m!}\sum_{\sum i c_i=m}N(c_1,c_2,\dots,c_m) (-1)^{m-\sum_{i=1}^m c_i}\prod_{i=1}^m (|D|1_{o(\chi)\mid i})^{c_i}\\
	&=(-1)^mZ_m(\underbrace{0,\dots,0}_{o(\chi)-1},-|D|,\underbrace{0,\dots,0}_{o(\chi)-1},-|D|,\dots)\\
	&=(-1)^m [u^m] (1-u^{o(\chi)})^{\frac{|D|}{o(\chi)}}.
	\end{align*}
	The last step is due to Lemma \ref{lem:a}.

	{\bf Case 2: $p\mid o(\chi)$}. In this case, we have $\sum_{x\in D}\chi^{i}(x)=(\sum_{k=1}^{(p-1)/2}\overline{\chi}^{i}(k))\frac{|G|}{p}1_{\frac{o(\chi)}{p}\mid i}$. A similar calculation as in case 1 shows that \begin{align*}
	S_m(\chi)&=(-1)^mZ_m(\underbrace{0,\dots,0}_{\frac{o(\chi)}{p}-1},\sum_{k=1}^{(p-1)/2}\overline{\chi}^{\frac{o(\chi)}{p}}(k)\frac{|G|}{p},\underbrace{0,\dots,0}_{\frac{o(\chi)}{p}-1},\sum_{k=1}^{(p-1)/2}\overline{\chi}^{\frac{2o(\chi)}{p}}(k)\frac{|G|}{p},\dots)\\
	&=(-1)^m[u^m] \prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k) u^{\frac{o(\chi)}{p}})^{\frac{|G|}{o(\chi)}},
	\end{align*}
	where we used Lemma \ref{lem:b}.

\end{proof}

\begin{lemma}\label{lem:d}
	Let be $p$ be an odd prime, and let $r$ be an integer with $1\leq r\leq p-1$. Then we have
	$$\prod_{k=1}^{(p-1)/2}(1-e^{2\pi i k r/p})^2=pe^{\pi i (\frac{p^2-1}{4p}r+\frac{p-1}{2})}.$$
\end{lemma}
\begin{proof}
	Let $P$ denote the product on the left-hand side. Then we have
	\begin{align*}
	|P|^2=P\overline{P}&=\prod_{k=1}^{(p-1)/2}(1-e^{2\pi i k r/p})^2\prod_{k=1}^{(p-1)/2}(1-e^{-2\pi i k r/p})^2\\
	&=\prod_{k=1}^{(p-1)/2}(1-e^{2\pi i k r/p})^2\prod_{k=1}^{(p-1)/2}(1-e^{2\pi i (p-k) r/p})^2=\prod_{k=1}^{p-1}(1-e^{2\pi i k r/p})^2=p^2,
	\end{align*}
	where we used the fact that $\{e^{2\pi i k r/p},\ 1\leq k\leq p-1\}$ is a complete list of the primitive $p$-th roots of unity. This gives $|P|=p$.

	 Then we are to determine the argument of $P$. From the elementary equality $(1-e^{i\theta})^2=2(1-\cos(\theta))e^{i(\theta+\pi)}$, we see that $\arg((1-e^{2\pi i rk/p})^2)=2\pi rk/p+\pi\mmod{2\pi}$, which yields
	\begin{align*}
	\arg(P)=  \sum_{k=1}^{(p-1)/2} (2\pi  rk/p+\pi)\mmod{2\pi}=\pi(\frac{p^2-1}{4p}r+\frac{p-1}{2})\mmod{2\pi}.
	\end{align*}

	Combining the results of modulus and argument of $P$, we conclude that
	$$P=\prod_{k=1}^{(p-1)/2}(1-e^{2\pi i k r/p})^2=pe^{\pi i (\frac{p^2-1}{4p}r+\frac{p-1}{2})}.
	$$
\end{proof}

\section{Proof of Theorem \ref{thm:main}}

As mentioned in the last part of Section \ref{sec:reduction}, the main problem is reduced to counting the quantity  $N_D(m_1,\dots,m_s,b)$. We shall use some character theory to estimate it. Again, let $G=\Z/2pn\Z$ be the additive group of order $2pn$ and let $D$ be the set defined in \eqref{eq:D}. Let $X_i=D^{m_i}$ be the  Cartesian product of $m_i$ copies of $D$, $1\leq i\leq s$. For an ordered $m$-tuple $x=(x_1,x_2,\dots,x_m)\in D^m$, denote by $\sigma(x):=\sum_{i=1}^m x_m$ the sum of its coordinates. Using the fact that $\frac{1}{|G|}\sum_{\chi\in G}\chi(x)$ is $1$ if $x=0_G$ and is $0$ otherwise,  we can express $N_D(m_1,m_2,\dots,m_2,b)$ as
\begin{align}\label{eq:NDD}
\begin{split}
&N_{D}(m_1,m_2,\dots,m_s,b)\\
 =&\frac{1}{m_1!m_2!\cdots m_s!}\sum_{(x_1,x_2,\dots,x_s)\in \overline{X_1}\times \overline{X_2}\times \cdots\times \overline{X}_s}1_{\sigma(x_1)+\sigma(x_2)+\cdots+\sigma(x_s)=b}\\
 =&\frac{1}{m_1!m_2!\cdots m_s!}\sum_{(x_1,x_2,\dots,x_s)\in \overline{X_1}\times \overline{X_2} \cdots\times \overline{X}_s}\frac{1}{|G|}\sum_{\chi\in\widehat{G}}\chi(\sigma(x_1)+\sigma(x_2)+\cdots+\sigma(x_s)-b)\\
=&\frac{1}{|G|}\sum_{\chi\in\widehat{G}}\overline{\chi}(b)\prod_{i=1}^s\frac{\sum_{x_i\in \overline{X_i}}\chi(\sigma(x_i))}{m_i!}\\
 =&\frac{1}{|G|} \sum_{\chi\in\widehat{G}}\overline{\chi}(b)\prod_{i=1}^s S_{m_i}(\chi),
\end{split}
\end{align}
where the character sum $S_{m_i}(\chi)$ is defined as in  \eqref{eq:Smchi}.

Now we are ready to estimate $N_D(b)$. By Lemma \ref{lem:c} and equation \eqref{eq:NDD}, we have
\begin{align}
\begin{split}\label{eq:NDb0}
N_D(b)&=\sum_{0\leq m_i\leq |D|,1\leq i\leq s} (-1)^{\sum_{i=1}^s m_i}N_D(m_1,m_2,\dots,m_s,b)\\
     &\quad=\frac{1}{|G|}\Big(\sum_{\chi\in\widehat{G}:p\mid o(\chi)}\overline{\chi}(b)\sum_{0\leq m_i\leq |D|,1\leq i\leq s}\prod_{i=1}^s [u^{m_i}]\prod_{k=1}^{(p-1)/2}\big(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k)u^{\frac{o(\chi)}{p}}\big)^{\frac{|G|}{o(\chi)}}\\
&\quad+\sum_{\chi\in\widehat{G}:p\nmid o(\chi)}\overline{\chi}(b)\sum_{0\leq m_i\leq |D|,1\leq i\leq s}\prod_{i=1}^s[u^{m_i}]\big(1-u^{o(\chi)}\big)^{\frac{|D|}{o(\chi)}}\Big).
\end{split}
\end{align}
We note that
\begin{align*}
\sum_{0\leq m_1,\dots,m_s\leq |D|}\prod_{i=1}^s [u^{m_i}]\prod_{k=1}^{(p-1)/2}\big(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k)u^{\frac{o(\chi)}{p}}\big)^{\frac{|G|}{o(\chi)}}&=\prod_{i=1}^s\Big(\sum_{m_i=0}^{|D|}[u^{m_i}]\prod_{k=1}^{(p-1)/2}\big(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k)u^{\frac{o(\chi)}{p}}\big)^{\frac{|G|}{o(\chi)}}\Big)\\
&=\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k))^{\frac{s|G|}{o(\chi)}}
\end{align*}
and similarly
\begin{align*}
\sum_{0\leq m_i\leq |D|,1\leq i\leq s}\prod_{i=1}^s[u^{m_i}](1-u^{o(\chi)})^{\frac{|D|}{o(\chi)}}=(1-1^{o(\chi)})^{\frac{s|D|}{o(\chi)}}=0.
\end{align*}
Substituting these into \eqref{eq:NDb0}, we obtain
\begin{align}\label{eq:NDb}
N_D(b)=\frac{1}{|G|}\sum_{\chi\in\widehat{G}:p\mid o(\chi)}\overline{\chi}(b)\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k))^{\frac{s|G|}{o(\chi)}}.
\end{align}

We split the sum \eqref{eq:NDb} into two parts:
\begin{align*}
N_D(b)&=\frac{1}{|G|}\sum_{\chi\in\widehat{G}:o(\chi)=p}\overline{\chi}(b)\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k))^{\frac{s|G|}{p}}+\frac{1}{|G|}\sum_{\chi\in\widehat{G}:p\mid o(\chi),o(\chi)>p}\overline{\chi}(b)\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k))^{\frac{s|G|}{o(\chi)}}\\
&=\frac{1}{|G|}\sum_{\chi\in\widehat{G}:o(\chi)=p}\overline{\chi}(b)\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}(k))^{\frac{s|G|}{p}}+O\Big(\max_{\chi\in\widehat{G}:p\mid o(\chi),o(\chi)>p}\Big|\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k))\Big|^{\frac{s|G|}{2p}}\Big).
\end{align*}
Note that the implied constant in the big O notation can be $1$. Since $G=\Z/2pn\Z$,  we have $|G|=2pn$ and thus $N_D(b)$ is equal to
\begin{align}\label{eq:NDb2}
N_D(b)=\frac{1}{2pn}\sum_{\chi\in\widehat{G}:o(\chi)=p}\overline{\chi}(b)\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}(k))^{2sn}+O\Big(\max_{\chi\in\widehat{G}:p\mid o(\chi),o(\chi)>p}\Big|\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k))\Big|^{sn}\Big).
\end{align}
Using Lemma \ref{lem:d}, we have
\begin{align}\label{eq:NDb3}
N_D(b)&=\frac{p^{sn}}{2pn}\sum_{r=1}^{p-1}e^{2\pi i \frac{b}{p}r}e^{ \pi i sn(\frac{p^2-1}{4p}r+\frac{p-1}{2})}+O(p^{sn/2}).
\end{align}
Note that for a character $\chi$ with $p\mid o(\chi)$, the character $\chi^{\frac{o(\chi)}{p}}$ is of order $p$. Thus Lemma \ref{lem:d} also implies that
$|\prod_{k=1}^{(p-1)/2}(1-\overline{\chi}^{\frac{o(\chi)}{p}}(k))|=\sqrt{p}$ for a character $\chi$ with $p\mid o(\chi)$ and consequently the error term in \eqref{eq:NDb2} is $O(p^{sn/2})$.

The sum in \eqref{eq:NDb3} is a geometric series with common ratio of $e^{2\pi i(\frac{b}{p}+sn\frac{p^2-1}{8p})}$, so $N_D(b)$ is equal to
\begin{align}\label{eq:NDb1}
N_D(b)=\frac{p^{sn}}{2pn}e^{\pi i sn\frac{p-1}{2}}(p-1)+O(p^{sn/2})=(-1)^{sn(p-1)/2}\frac{(p-1)p^{sn}}{2pn}+O(p^{sn/2}).
\end{align}
if $
b+sn(p^2-1)/8=0\mmod{p}$, and $N_D(b)$ is equal to
\begin{align}\label{eq:NDb4}
\begin{split}
N_D(b)
&=\frac{p^{sn}}{2pn}e^{\pi i  sn\frac{p-1}{2}}\frac{e^{2\pi i (\frac{b}{p}+sn\frac{p^2-1}{8p})}-1}{1-e^{2\pi i (\frac{b}{p}+sn\frac{p^2-1}{8})}}+O(p^{sn/2})\\
&=-(-1)^{sn(p-1)/2}\frac{p^{sn}}{2pn}+O(p^{sn/2}),
\end{split}
\end{align}
otherwise, where we used $p^2-1=0\mmod {8}$ for an odd prime $p$.

In view of \eqref{eq:Sb}, equations \eqref{eq:NDb1} and\eqref{eq:NDb4} imply that
$$S_{2pn,b}=\frac{(p-1)p^{sn}}{2pn}+O(p^{sn/2})$$ if
\begin{align}\label{eq:condition}
b-e+sn\cdot\frac{p^2-1}{8}=0\mmod{p},
\end{align}
and
\begin{align*}
S_{2pn,b}=-\frac{p^{sn}}{2pn}+O(p^{sn/2})
\end{align*}
otherwise. Recall that $e=sn(p-1)(2pn+1-p)/8$. A direct calculation shows that the condition \eqref{eq:condition} can be simplified as
$$b-\frac{n(n-1)}{2}\cdot\frac{p-1}{2}\cdot sp=0\mmod{p},$$
which is equivalent to $p\mid b$, since $\frac{n(n-1)}{2}$ is always an integer and $p-1$ is an even number.
This completes the proof. \qed


TITLE: Difference in writing answer for $\int\dfrac{12x^3-24x^2+5}{x^2-2x}dx$
QUESTION [1 upvotes]: I have this integral:
$\int\dfrac{12x^3-24x^2+5}{x^2-2x}dx$
I solved using partial fractions and got an answer:
$6x^2-\frac{5}{2}\ln(x)+\frac{5}{2}\ln(x-2) +C$
But I am using "My Math Lab" online homework which is not accepting my answer as written above.  I resolved it and got the same answer, and after some frustration, I plugged it into Wolfram Alpha and got this answer:
$6x^2-\frac{5}{2}\ln(x)+\frac{5}{2}\ln(2-x)+C$
So the only difference is $\ln(2-x)$ instead of what I wrote as $\ln(x-2)$.
What's more frustrating is MyMathLab still marked this wrong, and said the answer is actually:
$6x^2+\frac{5}{2}\ln\bigg|\frac{x-2}{x}\bigg|+C$
My first question is, why did Wolfram Alpha's answer say $\ln(2-x)$ instead of my original calculation that I found to be $\ln(x-2)$?  Why is this switch occurring?
My second question is, why did MyMathLab mark mine and Wolfram Alpha's answer incorrect?  Is this one of the limitations of MyMathLab grading, where two answers are actually the same and correct, but only look different?  Or is Wolfram Alpha wrong?  Why was the correct answer written the way it was?  Where did $\frac{5}{2}\ln\bigg|\frac{x-2}{x}\bigg|$ come from?

REPLY [1 votes]: The solutions have different domains.
Your answer is a valid solution for $x > 2$.
Wolfram's answer is a valid solution for $0<x<2$.
MyMathLab's answer is a valid solution for $x\in(-\infty,0)\cup(0,2)\cup(2,\infty)$ -- but it's not the only possible antiderivative on this domain, because it doesn't take into account that the integration constant is allowed to change at $x=0$ and $x=2$ where the integrand isn't defined.


TITLE: Find Galois group of $x^3+x^2-2x-1\in\mathbb{Q}[x]$
QUESTION [4 upvotes]: Find Galois group of $f(x)=x^3+x^2-2x-1\in\mathbb{Q}[x]$ over $\mathbb{Q}$.

This is not a duplication of this question because in the other question they are given a further data.
My attempt:
Let $E$ be the splitting field of $f$ over $\mathbb{Q}$. Let $\zeta=\exp(\frac{2\pi i}{7}), \alpha=\zeta+\zeta^{-1}$. We can notice that $f(\alpha)=0$, $f$ is irreducible in $\mathbb{Q}$ and $\deg(f)=3$. Thus $\text{irr}(\alpha,\mathbb{Q})=f$. Furthermore, we know that $[\mathbb{Q}(\zeta):\mathbb{Q}]=6$. We know that $\alpha\in E$. Thus we have this fields building:

And here I stuck. Thanks for helping.

REPLY [3 votes]: This is a pedestrian answer first, then we restate in the framework of Galois theory.

I will denote by $u$ a fixed primitive $7$.th root of unity (instead of $\zeta$ or even $\zeta_7$, which is hard to type.)
Let $a$ be the element $u+u^{-1}$. We know its conjugates, and introduce letters for them:
$$
\begin{aligned}
a &= u^1 + u^{-1} = u^1 + u^6\ ,\\
b &= u^2 + u^{-2} = u^2 + u^5\ ,\\
c &= u^3 + u^{-3} = u^3 + u^4\ .
\end{aligned}
$$
Then the given polynomial decomposes as
$$
X^3 + X^2 - 2X - 1
=(X-a)(X-b)(X-c)\ .
$$
To see this, we check the relations of Vieta.
$$
\begin{aligned}
a+b+c
&=
u+u^2+u^3+u^4+u^5+u^6
\\
&=
-1\ ,\\[2mm]
ab+ac+bc
&=ab + c(a+b)
\\
&=u^3(1+u^5)(1+u^3) + u^3(1+u)(-1-u^3-u^4)\\
&=u^3(1+u^3+u^5+u)-u^3(1+u^3+u^4+u+u^4+u^5)\\
&=-u^3(u^4+u^4)\\
&=-2\ ,\\[2mm]
abc
&=u^{1+2+3}(1+u^5)(1+u^3)(1+u)\\
&=u^6(1+u+u^3+u^5)(1+u)\\
&=u^6(1+u+u^3+u^5+u+u^2+u^4+u^6)\\
&=u^6\cdot u\\
&=1\ .
\end{aligned}
$$
The computation was done explicitly to show with bare hands that $a,b,c$ are the conjugates of $a$ in $E$, which is thus $\Bbb Q(a)$. (We have $b=a^2-2$ and $c=a^3-3a$.)

Let us give the Galois touch to the situation. The Galois group of the cyclotomic extension $\Bbb Q(u)$ over $\Bbb Q$ has the Galois substitutions $s_k:u\to u^k$ for $k\in\{1,2,3,4,5,6\}= \Bbb F_7^\times$, and the structure corresponds to the multiplicative structure of $\Bbb F_7^\times$, because $s_k\circ s_n\ u=s_k(s_n(u))=s_k(u^n)=(u^n)^k=u^{kn}=s_{kn}\ u$.
In particular, $s_{-1}=s_6$ is an element of order two, which stabilizes $a=u+u^{-1}$. There is a correspondence now between the subgroups of $\operatorname{Gal}(\Bbb Q(u):\Bbb Q)\cong \Bbb F_7^\times\cong(\Bbb Z/6,+)$ and the intermediate fields, normal corresponding to normal. But the Galois Group is commutative, each subgroup is normal. The subgroup of order two $\{1,s_6\}$ corresponds to $\Bbb Q(a)$. The Galois group of $\Bbb Q(a)$ over $\Bbb Q$ is $\cong \Bbb Z/3$, seen as the group of all six Galois substitutions of $\Bbb Q(u)$, modulo the subgroup generated by $s_6$, since $s_6$ acts trivially on $a$.


TITLE: Is there a constructive proof of this characterization of $\ell^2$?
QUESTION [22 upvotes]: I would like to revisit this question, which can be equivalently stated as:

Proposition.  Let $(a_n)$ be a sequence of real (or complex) numbers such that $\sum a_n b_n$ converges for every $(b_n) \in \ell^2$.  Then $(a_n) \in \ell^2$.

The proof given here by Bruno Stonek is the only one I know, which applies the uniform boundedness principle to the linear functionals $(b_n) \mapsto \sum_{n=1}^m a_n b_n$ in $(\ell^2)^*$.  But I am inclined to agree with GEdgar's comment on Davide Giraudo's answer that this approach, though slick, is "far too advanced".
One could write the contrapositive as:

Let $(a_n)$ be a sequence of real numbers which is not $\ell^2$.  Then there exists $(b_n) \in \ell^2$ such that $\sum a_n b_n$ diverges.

A natural way to try to prove that statement would be to explicitly construct such a $(b_n)$, by somehow manipulating $(a_n)$.  Our current proof is far from constructive in that sense, since the uniform boundedness principle essentially just says that the set of such $(b_n)$ is comeager in the Hilbert space $\ell^2$, and then uses Baire to assert it is nonempty.
So my question:

Can anyone think of a way to explicitly construct $(b_n)$?  Or alternatively, is there some reason to think that such a construction might be impossible?

For instance, as a wild guess, perhaps one could show that any map sending each $(a_n) \notin \ell^2$ to an appropriate $(b_n)$ would have to be nonmeasurable in some sense.

REPLY [22 votes]: One can construct explicitly such a sequence $(b_n)$ and this is probably explained in several books of examples and counterexamples in Analysis. Here we go.
Assume without loss of generality that $a_1\ne0$ and, for every $n\geqslant1$, let $$A_n=\sum\limits_{k=1}^na_k^2,\qquad b_n=\dfrac{a_n}{A_n}.
$$
The result the OP is interested in is a consequence of the two claims below.

Claim 1: For every $(a_n)$, the sequence $(b_n)$ is in $\ell^2$.
Claim 2: For every $(a_n)$ not in $\ell^2$, the sequence $(a_nb_n)$ is not in $\ell^1$.

To prove claim 1, note that, for every $n\geqslant2$, $a_n^2=A_n-A_{n-1}$ hence $$
b_n^2=\frac{A_n-A_{n-1}}{A_n^2}\leqslant\frac{A_n-A_{n-1}}{A_nA_{n-1}}=\frac1{A_{n-1}}-\frac1{A_n},
$$
hence the series $\sum\limits_nb_n^2$ converges (and its sum is at most $2/a_1^2$). (This step does not use the hypothesis that the sequence $(a_n^2)$ is not summable hence that $A_n\to+\infty$).
To prove claim 2, note that, for every $N$ and every $2\leqslant k\leqslant N$,
$$
a_kb_k=\frac{a_k^2}{A_k}\geqslant\frac{a_k^2}{A_N}=\frac{A_k-A_{k-1}}{A_N}.
$$
Since the sequence $(a_n^2)$ is not summable, $A_N\to+\infty$ when $N\to\infty$. Hence, for every given $n\geqslant1$, there exists some $N\geqslant n$ such that $A_N\geqslant2A_n$. For every such $N$,
$$
\sum\limits_{k=n+1}^Na_kb_k\geqslant\frac{A_N-A_{n}}{A_N}\geqslant\frac12.
$$
This proves that $\sum\limits_{k=n+1}^Na_kb_k$ does not converge to zero when $n$ and $N\to\infty$. Hence, the series $\sum\limits_ka_kb_k$ diverges.


TITLE: If I am given N congruent circles with radii R, and they are equidistantly spaced upon a sphere, can I figure out if the sphere's covered?
QUESTION [0 upvotes]: If I am given a set of N congruent circles with radii R, where the number of circles allows them to be placed on a sphere so the distance between the centers of every pair of different circles in the set is separated by the same distance, can I figure out if the sphere's covered?
Hopefully without requiring access to a supercomputer... (Didn't think that'd be a possibility, but I'm working with 'large' numbers...)
I previously asked: "What is the minimum radius of N congruent circles that are placed on a sphere equidistant from each other, so that the sphere is covered by circles?"
That was intended to produce a general answer to a generalization of the question: "How wide a radius of a field do I need 10,000 field emitters to emit, so the total field covers the Earth", but since the previous question can't produce the answer I wanted, I'm making this question.
Discussion about the differences between the questions, go here please...

REPLY [2 votes]: I presume that by "equidistant from each other" you mean "equidistant from their neighbours".
The problem is you can't in general put $N$ points equidistant on a sphere (you can do that only for some small values of $N$).
But if $N$ is large you can safely approximate each circle with a regular hexagon and treat the sphere as if it were a plane covered with hexagonal tiles. Since the area of a hexagon of radius $R$ is $(3/2)\sqrt3 R^2$ and the area of a sphere or radius $R_{sph}$ is $4\pi R_{sph}^2$, you need approximately
$$
N={8\pi \over 3\sqrt3}{R_{sph}^2\over R^2}
$$
circles to cover your sphere. By inverting this you can find $R$ if $N$ is given.


text:
\revision{red}{
\section{Solving linear systems}
\label{sec:KKT}
}

Search directions and centrality corrections are obtained by solving several Newton systems such as 	\eqref{eq:NS_aff_dual}-\eqref{eq:NS_aff_comp_tk}, all with identical left-hand side matrix but different right-hand side.
\revision{red}{Specifically,} each Newton system has the form
\begin{align}
	\label{eq:NewtonSystem}
	\left[
	\begin{array}{ccccccccccc}
		\revision{red}{-\prho I} 		&& A^{T} 	&& I		&&	-c		&&		\\
		A 		&& \revision{red}{\drho I} 			&&		&&	-b		&&		\\
		-c^{T} 	&& b^{T}		&&		&& \revision{red}{\grho}			&& -1 	\\
		S 		&&  			&& X		&&			&&		\\
		 		&&  			&&		&& \kappa	&& \tau
	\end{array}
	\right]
	\left[
	\begin{array}{l}
		\delta_{x}\\
		\delta_{y}\\
		\delta_{s}\\
		\delta_{\tau}\\
		\delta_{\kappa}
	\end{array}
	\right]
	=
	\left[
		\begin{array}{l}
			\xi_{d}\\
			\xi_{p}\\
			\xi_{g}\\
			\xi_{xs}\\
			\xi_{\tau \kappa}
		\end{array}
	\right]
	,
\end{align}
where $\xi_{p}, \xi_{d}, \xi_{g}, \xi_{xs}, \xi_{\tau \kappa}$ are \revision{red}{appropriate} right-hand side vectors.
\revision{red}{The purpose of this section is to provide further details on the techniques used for the resolution of \eqref{eq:NewtonSystem}, and their implementation in Tulip.
}

\revision{red}{
\subsection{Augmented system}
}

    First, we eliminate $\delta_{s}$ and $\delta_{\kappa}$ as follows:
    \begin{align}
    	\delta_{s} 		&= X^{-1}(\xi_{xs} - S\delta_{x}),\\
    	\delta_{\kappa} 	&= \tau^{-1}(\xi_{\tau \kappa} - \kappa \delta_{\tau}),
    \end{align}
    which yields
    \begin{align}
    	\label{eq:NewtonSystem_reduced}
    	\left[
    	\begin{array}{ccccccccccc}
    		\revision{red}{-(\Theta^{-1} + \prho I)}		&& A^{T} 	&&	-c		\\
    		A 			&&  \revision{red}{\drho I}			&&	-b		\\
    		-c^{T} 		&& b^{T}		&&	\tau^{-1} \kappa \revision{red}{ + \grho}
    	\end{array}
    	\right]
    	\left[
    	\begin{array}{l}
    		\delta_{x}\\
    		\delta_{y}\\
    		\delta_{\tau}
    	\end{array}
    	\right]
    	=
    	\left[
    		\begin{array}{l}
    			\xi_{d} - X^{-1} \xi_{xs}\\
    			\xi_{p}\\
    			\xi_{g} +\tau^{-1} \xi_{\tau \kappa}
    		\end{array}
    	\right]
    	,
    \end{align}
    where $\Theta = XS^{-1}$.

    \revision{red}{As outlined in \cite{Andersen2000,Wright1997}}, a solution to \eqref{eq:NewtonSystem_reduced} is obtained by first solving
    \begin{align}
    	\label{eq:augsys_hsd}
    	\left[
    	\begin{array}{ccccccccccc}
    		\revision{red}{-(\Theta^{-1} + \prho I)}		&& A^{T} 	\\
    		A 			&& \revision{red}{\drho I}
    	\end{array}
    	\right]
    	\left[
    	\begin{array}{l}
    		p\\
    		q
    	\end{array}
    	\right]
    	&=
    	\left[
    		\begin{array}{l}
    			c\\
    			b
    		\end{array}
    	\right]
    	,
    \end{align}
    and
    \begin{align}
    	\label{eq:augsys_hsd_bis}
    	\left[
    	\begin{array}{ccccccccccc}
    		\revision{red}{-(\Theta^{-1} + \prho I)}		&& A^{T} 	\\
    		A 			&& \revision{red}{\drho I}
    	\end{array}
    	\right]
    	\left[
    	\begin{array}{l}
    		u\\
    		v
    	\end{array}
    	\right]
    	&=
    	\left[
    		\begin{array}{l}
    			\xi_{d} - X^{-1} \xi_{xs}\\
    			\xi_{p}
    		\end{array}
    	\right]
    	.
    \end{align}
    \revision{red}{Linear systems of the form \eqref{eq:augsys_hsd} and \eqref{eq:augsys_hsd_bis} are referred to as \emph{augmented systems}.}
    Then, $\delta_{x}, \delta_{y}, \delta_{\tau}$ are computed as follows:
    \begin{align}
    	\delta_{\tau} 	&= \frac{\xi_{g} + \tau^{-1}\xi_{\tau \kappa} + c^{T}u + b^{T}v}{\tau^{-1} \kappa \revision{red}{+ \grho} - c^{T}p + b^{T}q},\\
    	\delta_{x} 		&= u + \delta_{\tau} p,\\
    	\delta_{y} 		&= v + \delta_{\tau} q.
    \end{align}
    \revision{red}{Note that \eqref{eq:augsys_hsd} does not depend on the right-hand side $\xi$.
    Thus, it is only solved once per IPM iteration, and its solution is reused when solving subsequent Newton systems.

    Finally, as pointed in \cite{Friedlander2012}, the augmented system's structure motivates the following observations.
    First, the use of primal-dual regularizations controls the effective condition number of the augmented system, which, in turn, improves the algorithm's numerical behavior.
    Second, the augmented system's matrix is symmetric quasi-definite.
    This allows the use of efficient symmetric indefinite factorization techniques, which only require one symbolic analysis at the beginning of the optimization.
    In particular, dual regularizations ensure that this quasi-definite property is retained even when $A$ does not have full rank.
    Third, directly solving the augmented system implicitly handles dense columns in $A$, which make the system of normal equations dense \cite{Wright1997}.
    We have also found this approach to be more numerically stable than a normal equations system-based approach.
    }

\revision{red}{
\subsection{Black-box linear solvers}

    The augmented system may be solved using a number of techniques, with direct methods --namely, symmetric factorization techniques-- being the most popular choice.
    Importantly, the algorithm itself is unaffected by \emph{how} the augmented system is solved, provided that it is solved accurately.
}
    Our implementation leverages Julia's multiple dispatch feature and built-in support for linear algebra,
	thus allowing to disentangle the algorithmic framework from the linear algebra implementation.

	First, the interior-point algorithm is defined over abstract linear algebra structures.
	Namely, the constraint matrix $A$ is \revision{red}{treated} as an \texttt{AbstractMatrix}, whose concrete type is only known once the model is instantiated.
	Julia's standard library includes extensive support for linear algebra, thus removing the need for a custom abstract linear algebra layer.

	\revision{red}{
        Second, while the reduction from the Newton system to the augmented system is performed explicitly, the latter is solved by a black-box linear solver.
        Specifically, we design an \texttt{AbstractKKTSolver} type, from which concrete linear solver implementations inherit.
        The \texttt{AbstractKKTSolver} interface is deliberately minimal, and consists of three functions:\footnote{In Julia, a \texttt{!} is appended to functions that mutate their arguments.} \texttt{setup}, \texttt{update!}, and \texttt{solve!}.

        A linear solver is instantiated at the beginning of the optimization using the \texttt{setup} function.
        Custom options can be passed to \texttt{setup} so that the user can select a linear solver of their choice.
        At the beginning of each IPM iteration, the linear solver's state is updated by calling the \texttt{update!} function.
        For instance, if a direct method is used, this step corresponds to updating the factorization.
        Following the call to \texttt{update!}, augmented systems can be solved through the \texttt{solve!} function.
        Default, generic, linear solvers are described in Section \ref{sec:implementation:linalg}, and an example of specialized linear solver is given in Section \ref{sec:res:colgen}.
        Specific details are provided in Tulip's online documentation.\footnote{\url{https://ds4dm.github.io/Tulip.jl/dev/}}
    }

	\revision{red}{Finally}, specialized methods are automatically dispatched based on the (dynamic) type of $A$.
	These include matrix-vector and matrix-matrix product, as well as matrix factorization routines.
	We emphasize that the dispatch feature is a core component of the Julia programming language, and is therefore entirely transparent to the user.
	Consequently, one can easily define custom routines that exploit certain properties of $A$, so as to speed-up computation or reduce memory overheads.
	Furthermore, this customization is entirely independent of the interior-point algorithm, thus allowing to properly assess the impact of different linear algebra implementations.

\iffalse
    Finally, the augmented systems \eqref{eq:augsys_hsd} and \eqref{eq:augsys_hsd_bis} are first reduced to the normal equations system, by pivoting out the diagonal block $-\Theta^{-1}$.
    In the case of \eqref{eq:augsys_hsd_bis}, the normal equations write
    \begin{align}
    	\label{eq:normaleq}
    	(A \Theta A^{T}) v &= \xi_{p} + A \Theta^{-1}(\xi_{d} - X^{-1} \xi_{xs})
    	.
    \end{align}
    One then recovers $u = \Theta^{-1}(A^{T}v - \xi_{d} + X^{-1} \xi_{xs})$.

    The normal equations are typically solved by a direct method, namely by computing a Cholesky factorization of the positive definite matrix $A \Theta A^{T}$.
    This factorization is computed only once per iteration, and is re-used in subsequent solves.
    Further details on the practical computation of the Cholesky factors will be given in Section \ref{sec:implementation} and Section \ref{sec:linalg}.
\fi


text:
\begin{document}

\begin{abstract}
In this short paper I introduce a concept of \emph{possibility} in order to vindicate Everett's Theory of many worlds. The main idea is that there is only one world: the real. After the wave-collapse, we have again only one world, but many possible worlds which have a different grade of possibility. In this sense \emph{possible} exclude the \emph{reality}, opposing a long modal tradition.
\end{abstract}

\maketitle

\section{Symbolic Notation}
\noindent Be given the eigen-value problem $\mathcal{O}\phii = \lambda_i\phii$, where $\mathcal{O}$ is an hermitian operator (a particular linear operator) representing mathematically an observable $O$. An observable is anything which we can measure. von Neumann spoke of \emph{Gr\"osse}. $\phii$ is an eigen-vector, representing the eigen-state in which the wave-function collapses after a measurement. Finally, $\lambda_i$ is a real number: the measure of $O$. I will write the wave-collpase this way:
\begin{equation}
m_i(\mathcal{O}) \to \phii \vDash m_i(\mathcal{O}) = \lambda_i
\end{equation}

\noindent I.e. the measurement $m_i$ on $\mathcal{O}$ collapses the wave-function of $\mathcal{O}$ in one of its eigen-state $\phii$ in which is it true that $m_i(\mathcal{O}) = \lambda_i$, it is true that $\mathcal{O}$ measures just $\lambda_i$. I would insist on this notation. The arrow $\to$ suggests an implication from the measurement to the collapse. Obviously, this arrow is a meta-linguistic sign. The formulation of the conseguent suggests a parallel with Model Theory. The eigen-vector is a sort of model in which a formula is true or false (in this case, true). In fact, we can speak of measurement only in the context of an eigen-state.\\
One could observe that we neglected the amplitude of probability associated to a \emph{possible} eigen-state. As you can see below, we can express that a measurement implies a collapse with a propability $P = r_i$ in the following manner:
\begin{equation}
m_i(\mathcal{O}) \xrightarrow{P = r_i} \phii \vDash m_i(\mathcal{O}) = \lambda_i
\end{equation}

\section{Modal Definitions}
\noindent Let us state that $\vert\varphi_{\mathcal{O}}\rangle = c_i\phii + c_j\phij$ and that $m_i(\mathcal{O}) \to \phii \vDash m_i(\mathcal{O}) = \lambda_i$;\footnote{I.e. the measurement $m_i$ on an observable $O$ collapses the wave-function $\vert\varphi_{\mathcal{O}}\rangle$ in the eigen-state $\phii$ in which the eigen-value of the operator associated to $O$ equals $\lambda_i$. In other words, it is true in the eigen-state $\phii$ that the eigen-function $m_i(\mathcal{O})$ has the value $\lambda_i$.}, then $\phij$ is \textbf{possible} as regards $\phii$; on the contrary, if were $m_j(\mathcal{O}) \to \phij \vDash m_j(\mathcal{O}) = \lambda_j$, $\phii$ would be \textbf{possible} as regards $\phij$. \emph{Possibility} is no more in this context a predicate, but a  \emph{relation amongs eigen-states}. Symbolically:
\begin{definition} (Relative Possibility) If $\vert\varphi_{\mathcal{O}}\rangle = c_i\phii + c_j\phij$ and $m_i(\mathcal{O}) \to \phii \vDash m_i(\mathcal{O}) = \lambda_i$, then $\phij\sim\phii$.\footnote{We use the symbol $\sim$, following C.I. Lewis to indicate the possibility.}
\end{definition}

\noindent In other terms: $\phij$ is possible for $\phii$.\\
\noindent $\phii$ is \emph{possible tout-court} when it exists a real eigen-state of which $\phii$ is possible (see below \textbf{Definition 2}). If we have that $m_j(\mathcal{O}) \to \phij \vDash m_j(\mathcal{O}) = \lambda_j$, then $\phii$ is possible as regards $\phij$. Nevertheless, it could be another measurement $m_i$ such that $m_i(\mathcal{O}) \to \phii \vDash m_i(\mathcal{O}) = \lambda_i$. In this situation, $\phii$ is \emph{real} and \emph{no} more  possible. But we had not required that $\phii$ be possible as regards \emph{any} eigen-state, but only that there be \emph{at least} an eigen-state, of which $\phii$ were possible. Of course, if $\phii$ is possible as regards $\phij$, then it is possible tout-court (symbolically, $\sim\phii$\footnote{I hope that using the same symbol denoting both a relation and a predicate be not confusing.}).
\begin{definition}\label{def2} (Possible) $\sim\phii \overset{\mbox{\tiny{def}}}{=} \exists \phij\quad\text{such that}\quad\phii\sim\phij$.
\end{definition}

\noindent $\sim$, understood as a relation and not as an operator, is
anti-simmetrical, transitive, but \emph{not} reflexive. According our
definition, the possibility excludes the reality. In fact, only the braches originating with the measurement which don't become real are possible.
\begin{align}
&\neg(\phii\sim\phii)\quad\quad&(\text{Anti-Simmetry})\\
&\phii\sim\phij \to \neg(\phij\sim\phii)&(\text{Not Reflexivity})\\
&(\phii\sim\phij \wedge \phij\sim\phik) \to \phii\sim\phik&(\text{Transitivity})
\end{align}

\begin{definition} (Determinism) If $\vert\emptyset\rangle\sim\phii$, then $\phii$ is a deterministic eigen-state ($\mathsf{Det}(\phii)$) and $m_i$ a deterministic process.
\end{definition}

\noindent In other words, if there are no possibilities apart a unique eigen-state, then this eigen-state is deterministic. There is no choice to make. $\phii$ must realize itself. On the contrary;
\begin{definition} (Absurdity) If $\phii\sim \vert 1\rangle$, then $\phii$ is an absurd eigen-state.
\end{definition}

\section{Shaping the Universe of Possible Worlds}
\noindent Until now, we saw that possibility excludes reality. So we can imagine a world splitted up in two distinct parts, possible and real, with a sharp limit between them. This way, the realm of possible can sound caothic. Any non-real branch is on the same ontological level than another non-real branch. I think that we can distinguish many grades of possibility. There is a possibility near the real, and there is a possibility too far from our sight. The fact that in next presidentials Obama could be not re-elected is a possibility; also the existence of a fancy figure is a possibility. But we reckon that we are facing two types of possibilities, or that the first possibility is more possible that the second.\\
So what we need is a map where drawing any branch arising from the wave collapse. The idea is to assign a length to a branch. A branch longer than another, is so more possible. How assigning a length? The length of a branch is its probability. So if the branch $b_i$ has a probability $1/3$ and the branch $b_j$ a probability $1/2$, then the second branch is more possibile (nearer the reality) than the first.
\begin{definition} (Comparison amongs Diverse Possibilities) Be $\vert\varphi_{\mathcal{O}}\rangle = c_i\phii + c_j\phij + c_k\phik$ and $m_i(\mathcal{O}) \to \phii \vDash m_i(\mathcal{O}) = \lambda_i$, then if $m_i(O) \xrightarrow{P = \vert c_j\vert^2} \phij \vDash m_i(\mathcal{O}) = \lambda_j$\footnote{As noted above $m_i(\mathcal{O}) \xrightarrow{P = \vert c_j\vert^2} \phij \vDash m_i(\mathcal{O}) = \lambda_j$ means that the measurement  $m_i$ on $O$ has a value $\lambda_j$ with a probability $\vert c_j\vert^2$. I.e., $m_i$ implies with a probability $P = \vert c_j\vert^2$ a collapse in the eigen-state $\phij$ in which the value of the eigen-function $m_i(\mathcal{O})$ equals $\lambda_j$.} and $m_i(\mathcal{O}) \xrightarrow{P = \vert c_k\vert^2} \phik \vDash m_i(\mathcal{O}) = \lambda_k,$ with $c_j \leq c_k$ and $c_j,c_k \in \mathbb{C}$, then $\phik$ is more possible as regards $\phii$ than $\phij$; where $\phij,\phik$ are not realized eigen-states and $\phii$ the eigen-state caused by $m_i$.
\end{definition}

\noindent \textbf{Example:} $\vert\varphi_{\mathcal{O}}\rangle = c_1\1 + c_2\2 + c_3\3 +\ldots+ c_n\phin$, but only $\3$ becomes the eigen-state in which $m_i(\mathcal{O}) = \lambda_3$, then, as regards $\3$ all the $\1,\2,\4,\phi5,$\\
\noindent $\ldots,\phin$ are only possible, with diverse grade of possibility.

\begin{definition}(Relation amongs Possibilities) Be $\vert\varphi_{\mathcal{O}}\rangle = c_1\1 +\ldots+c_n\phin,$\\
\noindent $c_1,c_n \in \mathbb{C}$; if $m_i(\mathcal{O}) \to \phii \vDash m_i(\mathcal{O}) = \lambda_i,$ then $\forall j \neq i, \phij\sim\phii$ and given two eigen-states whatever $\phij$ and $\phik$ such that $\vert c_j\vert^2 \geq \vert c_k\vert^2$, then $(\phij\simpm\phik)\sim\phii$. I.e., $\phij$ is more possible for $\phii$ than $\phik$.
\end{definition}

\noindent As we have stressed, an eigen-state is possible only as regards a real eigen-state. In the following, we omit the reference to the real eigen-state, if not necessary to understand. We may say, therefore, that the relation $\simpm$ orders the eigen-states of a wave-function according to their possibility as regards a $\phii$.
\begin{definition} (Transitivity)  $(\phij\simpm\phii \wedge \phii\simpm\phik) \to \phij\simpm\phii$
\end{definition}

\begin{definition} ($\phii$ and $\phik$ have the Same Grade of Possibility) $(\phii\simpm\phik \wedge \phik\simpm\phii) \to \phik\sim^=\phii$
\end{definition}

\noindent I.e. if one eigen-state is more possible than another, and this last is more possible than the first, then the two eigen-state have the same probability.

\begin{definition} (Simmetry) $\phii\sim^=\phii$
\end{definition}

\begin{definition} (Lower bound) It exists an eigen-state $\phij$ such that $\forall \phii, \phii \simpm\phij$.\footnote{The \emph{event} $\phij$ is the less probable event (always in reference to a real event). \textbf{NB:} $\phij$ is the less possible event but not for that \emph{impossible}.}
\end{definition}

\begin{definition} (Upper bound) It exists an eigen-state $\phij$ such that $\forall \phii, \phij\simpm\phii$.\footnote{$\phij$ is the eigen-state most possible as regards the real one, but it is \textbf{not} \emph{necessary}.}
\end{definition}

\noindent  Absurdity is the relation between a possible event with $P = 0$\footnote{I.e. with probability equal to $0$.} and a deterministic eigen-state with $P = 1$. For example, be $\vert\varphi_{\mathcal{O}}\rangle = c_1\1 + c_2\vert \emptyset \rangle$, then $\vert\varphi_{\mathcal{O}}\rangle$ can collapse only on $\1$; therefore, $\vert \emptyset \rangle$ is absurd as regards $\1$. In the same situation, $\1$ is deterministic as regards $\vert \emptyset \rangle$.

\begin{definition} (Impossible) An eigen-state $\phii$ is \emph{impossible} (not in a relation of absurdity), when $\forall \vert\varphi_{\mathcal{O}}\rangle = c_1\1 +\ldots+c_n\phin$ and every eigen-function $m_i$ $P(\phii) = 0$ \textnormal{[i.e. $\neg\Diamond\phii$]}.
\end{definition}

\noindent In other words, an eigen-state is impossible when it doesn't exist a wave-function of which it is a possible eigen-state.

\begin{definition} (Necessary) On the contrary, an eigen-state $\phii$ is \emph{necessary} (not in a relation of determinism) when $\forall \vert\varphi_{\mathcal{O}}\rangle = c_1\1+\ldots+c_n\phin$ and every measurement $P(\phii) = 1$ \textnormal{[$\Box\phii$]}.\footnote{$\phii$ is not only deterministic, but deterministic in a context whatever.}
\end{definition}

\noindent We can re-phrase the two previous definitions as follows:
\begin{definition} $\phii$ is impossible when it is in a relation of absurdity in every context \textnormal{[$\neg\Diamond \phii$]}.\footnote{For example, $\phii$ can be absurd in a given situation, but it can be not only possible, but also real in another situation. It is impossible when it is absurde in any context.}
\end{definition}

\begin{definition} $\phii$ is necessary when it is deterministic in every context \textnormal{[$\Box\phii$]}.\footnote{In fact, $\phii$ can be deterministic in a given context and be only possible in another context. When it is deterministic always, despite any particular situation, then it is necessary.}
\end{definition}

\noindent We can explain the difference between \emph{being deterministic} and \emph{being necessary} with an example: $\phii$ is in a relation of determinism with an eigen-state $\phij$ when the square of the module of the weight associated to $\phii$, ($\vert c_i\vert^2$) equals $1$. So, $\phii$ is not always deterministic, but only when its probability is $1$. When it is \emph{always} deterministic, then it is necessary.\\
Classical Physics is deterministic; therefore, the raining today is a deterministic fact, but not necessary. It could not rain. It would be sufficient that the initial conditions were different. In this case, it is deterministic, according to the present situation, that it rains, but it is not necessary. It exists obviously at least a situation in which it doesn't rain. For example in the desert.\\
On the contrary, if it rains despite any possible context, then raining is really necessary. A similar argument obtains for the impossibility, inasmuch \emph{necessity} and \emph{impossibility} are related together by definition:
\begin{definition} $\Box A \overset{\mbox{\tiny{def}}}{=} \neg\sim\neg A$.
\end{definition}

\section{The Branching after the Wave-Collpase}
\noindent Let us state that it exists a wave-function $\vert\varphi_{\mathcal{O}_i}\rangle = c_1\1 +\ldots + c_n\phin$. The measurement collapses the state in which the system lays in an eigen-state $\phii$, as regards to which any other eigen-state is only possible. We make a choice among these possible eigen-state, taking a $\phij$.\\
\noindent Now, we measure the observable $O_j$ and its wave-function collapses in the eigen-state $\phij$. We choose amongs the possible states for $\phij$ a $\phik \neq \phii$. As our relation of possibility is transitive, $\phik$ will be possible by $\phij$ for $\phii$ in our first measurement. But what is the difference between $\phij$ and $\phik$ as regards $\phii$ in our first measurement?\\
\noindent Intuitively, $\phik$ is more far than $\phij$ from $\phii$. A way to compute the distance could be to use again the probability, compounding the probability of $\phij$ for $\phii$ with that of $\phik$ for $\phii$, as in an oriented graph. The vertices are the states or the eigen-states (real or possible) and the arrows their probabilities.\\
\noindent In this case, we have $\phii \overset{R}{\to} \phij$ and $\phij \overset{S}{\to} \phik$. Then, the distance between the vertices $\phii$ and $\phik$ equals $S \circ R$: $\phii \xrightarrow{S \circ R = T} \phik$. Now, the distance of $\phik$ from $\phii$ is $P(\phik\boldsymbol{\vert}\phij)$, i.e. the conditioned probability of $\phik$, given $\phij$.
\vspace{12pt}

\section{Note}
\noindent Finally, the set of the probabilities associated to a wave-function $\vert\varphi_{\mathcal{O}}\rangle, \mathcal{P}_{\vert\varphi_{\mathcal{O}}\rangle} = \lbrace \vert c_1\vert^2, \vert c_2\vert^2,\ldots, \vert c_n\vert^2 \rbrace$ is well ordered by the relation $\simpm$. This well ordered set $\mathcal{P}^{\simpm}_{\vert\varphi_{\mathcal{O}}\rangle}$ has an \emph{infimum} (see above the \emph{lower bound}), a \emph{supremum} (see above the \emph{upper bound}) and any couple of probabilities in it has a $\min$ and a $\sup$. So, $\mathcal{P}^{\simpm}_{\vert\varphi_{\mathcal{O}}\rangle}$ is a lattice. Furthermore, because $P(\neg\phii) = 1-P(\phii)$, $\mathcal{P}^{\simpm}_{\vert\varphi_{\mathcal{O}}\rangle}$ is orto-complemented. Finally, it is \emph{distributive}. Also it is a Boolean Algebra: $\mathfrak{O} = <\vert c_i\vert^2_{i \in \mathbb{N}}, \neg, +, 0, 1>$.

\nocite{cramer}
\nocite{everett}
\nocite{neumann}

\bibliography{quantum}
\bibliographystyle{amsalpha}

\end{document}


TITLE: Proving homotopy invariance of cellular homology by constructing a chain homotopy
QUESTION [2 upvotes]: I'm trying to follow an argument in Lück's "Algebraische Topologie: Homologie und Mannigfaltigkeiten" (to which there apparently doesn't exist an english translation). The aim is to check homotopy invariance of cellular homology by constructing a chain homotopy.
Let me sketch the argument. Let $h\colon (X,A)\times [0,1]\to (Y,B)$ be a cellular homotopy from $f_0$ to $f_1$. Using the CW-structure on $[0,1]$ with the two 0-cells {0}, {1} and one 1-cell, we identify
$$
C_n((X,A)\times [0,1])=C_n(X,A)\oplus C_n(X,A)\oplus C_{n-1}(X,A).
$$
Then $C_n(h)$ is of the form $C_n(f_0)\oplus C_n(f_1)\oplus u_{n-1}$, where $u_{n-1}$ is some map $C_{n-1}(X,A)\to C_n(Y,B)$.
Now we would like to compute the $n$th differential of $C_*((X,A)\times [0,1])$ under the above identification. Since it is a map from $C_n(X,A)\oplus C_n(X,A)\oplus C_{n-1}(X,A)$ to $C_{n-1}(X,A)\oplus C_{n-1}(X,A)\oplus C_{n-2}(X,A)$, we can denote it by a 3x3-matrix.
My computation yielded
$$
\begin{pmatrix}
c_n & 0 & 0 \newline 0 & c_n & 0 \newline -id & id & c_{n-1}
\end{pmatrix},
$$
where $c_n$ is the $n$th differential of $C_*(X,A)$.
In the book, however, I find
$$
\begin{pmatrix}
c_n & 0 & (-1)^n \newline 0 & c_n & (-1)^{n-1} \newline -id & id & c_{n-1}
\end{pmatrix}.
$$

Question: What is meant by $(-1)^n\colon C_{n}(X,A)\to C_{n-2}(X,A)$ and how can I
  understand that the second matrix above is the correct expression?

Edit: Apparently, the correct form of the the matrix representing the $n$th differential of $C_*((X,A)\times [0,1])$ is
$$
\begin{pmatrix}
c_n & 0 & 0 \newline 0 & c_n & 0 \newline (-1)^{n+1}\cdot id & (-1)^n\cdot id & c_{n-1}
\end{pmatrix}
$$
or
$$
\begin{pmatrix}
c_n & 0 & 0 \newline 0 & c_n & 0 \newline (-1)^{n}\cdot id & (-1)^{n+1}\cdot id & c_{n-1}
\end{pmatrix},
$$
depending on the orientation of the 1-cell in $[0,1]$.

REPLY [1 votes]: I hope it will be interesting for topologists  to see this result on cellular homotopy as a special case of a result on filtered spaces $X_\ast$  and of the homotopy invariance of the fundamental crossed complex functor
$\Pi: ($filtered spaces$)\to ($crossed complexes$)$
defined using the fundamental groupoid and relative homotopy groups. The difficult part is to construct  a natural transformation
$\zeta :   \Pi X_\ast  \otimes \Pi Y_\ast \to \Pi (X_\ast \otimes Y_\ast )$
(which is an isomorphism for cellular filtrations) and this uses cubical methods. This is all explained in our book published by the EMS and advertised here.


TITLE: Integrate a gaussian distrbution over a sphere surface
QUESTION [1 upvotes]: I want to integrate an off-center guassian distribtuion function over the surface of a sphere with radius of R. Here is the function:
$$ f(x,y,z) = A \exp(-\frac{(x-x_{s})^2+(y-y_{s})^2}{d^2})$$
$x_s, y_s, R, d$ and $A$ are all constant paramaters, and I can't replace them with numbers. The goal is to have a function based on all these parameters, that I can later use in my model.
In Mathemtica. I can solve a centric gussian but as it gets off-center(as I put $x_s$ and $y_s$) it can not be sovled.
To be able to easily integrate over surface of sphere I transform the equations to spherical coordinates and I have:
$$ \int_{0}^{2\pi} \int_{0}^{\pi} A R^2 \sin(\phi)\exp( -2 \frac{ (R \sin(\phi) \cos(\theta)-X_s)^2 + (R \sin(\phi) \sin(\theta)-Y_s)^2 }{d^2}) d\phi d\theta$$
But still I can not sovle this with MATLAB or Mathematica.
And I believe I can't solve it numerically because since I have parameters in there, solving it numerically would mean that for each element of integration I will have a different exp term. So I will just have a function with 1000 exponential terms (assuming I divide surface to 1000 elements) and that would be not practically useful.
Am I doing sth wrong? Any suggestions please?

REPLY [1 votes]: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
$\left\{\begin{array}{l}
\ds{\on{f}\pars{x,y,z} \equiv
A \exp\pars{-\,{\bracks{x - x_{s}}^{2} +
\bracks{y - y_{s}}^{2} \over d^{2}}}}
\\[1mm]
\ds{\bbox[5px,#ffd]{\iint_{\mathcal{S}}\on{f}\pars{x,y,z}
\,\dd S}:\ {\LARGE ?}}.
\\[1mm]
\mathcal{S} \equiv \braces{\pars{x,y,z}\ \mid\
x^{2} + y^{2} + z^{2} = R^{2}\,,\ R > 0}
\end{array}\right.$

Lets
$\ds{\vec{r} \equiv x\,\hat{x} + y\,\hat{y} + z\,\hat{z}\quad}$ and
$\ds{\quad\vec{r}_{s} \equiv x_{s}\,\hat{x} + y_{s}\,\hat{y} + 0\,\hat{z}}$. Then,
\begin{align}
&\bbox[5px,#ffd]{\iint_{\mathcal{S}}\on{f}\pars{x,y,z}
\,\dd S} =
\iint_{S}A\exp\pars{-\,{\verts{\vec{r} - \vec{r}_{s}}^{2} - z^{2} \over d^{2}}}\,\dd S
\\[5mm] = &\
A\int_{0}^{2\pi}
\\ &\
\!\!\!\!\!\int_{0}^{\pi}\!\!\!\!\!
\exp\pars{-\,{\bracks{R^{2} -2Rr_{s}\cos\pars{\theta} + r_{s}^{2}} - R^{2}\cos^{2}\pars{\theta} \over d^{2}}}\ \times
\\ &\ \phantom{\int_{0}^{2\pi}\int_{0}^{\pi}}
R^{2}\sin\pars{\theta}\,\dd\theta\,\dd\phi
\\[5mm] = &\
2\pi AR^{2}\exp\pars{-\,{R^{2} + r_{s}^{2} \over d^{2}}}\ \times
\\ &\
\int_{-1}^{1}
\exp\pars{-\,{-2Rr_{s}\,\xi - R^{2}\xi^{2} \over d^{2}}}
\,\dd\xi
\\[5mm] = &\
\left.2\pi ARd
\exp\pars{-\,{R^{2} + r_{s}^{2} \over d^{2}}}
\int_{-d/R}^{d/R}
\expo{\xi^{2}\ +\ 2\overline{r}_{s}\,\xi}
\,\dd\xi\,\right\vert_{\ \overline{r}_{s}\ =\ r_{s}\,/d}
\\[5mm] = &\
2\pi ARd
\exp\pars{-\,{R^{2} + r_{s}^{2} \over d^{2}}}\ \times
\\ &\
\braces{%
{1 \over 2}\expo{-\overline{r}_{s}^{2}}\root{\pi}
\bracks{\on{erfi}\pars{{d \over R} - \overline{r}_{s}} +
\on{erfi}\pars{{d \over R} + \overline{r}_{s}}}}
\\[5mm] = &\
\pi^{3/2}ARd
\exp\pars{-\,{R^{2} + 2r_{s}^{2} \over d^{2}}}\ \times
\\ &\
\bracks{\on{erfi}\pars{{d \over R} - {r_{s} \over d}} +
\on{erfi}\pars{{d \over R} + {r_{s} \over d}}}
\end{align}
whith $\ds{r_{s} = \root{x_{s}^{2} + y_{s}^{2}}\quad}$ and
$\ds{\quad\on{erfi}\pars{z} \equiv
-\ic\on{erf}\pars{\ic z}}$.

$\ds{\overline{\underline{\mbox{Note that}}}}$
$\ds{\ \color{red}{\on{erfi}\pars{z} \in \mathbb{R}}}$ when
$\ds{\color{red}{z \in \mathbb{R}}}$.

$\ds{\on{\large erfi}\quad\mbox{and}\quad\on{\large erf}\quad}$ belong to the
Error Function Family.