TITLE: Show that a function $f: A \to B$ is surjective if and only if it has a right inverse.
QUESTION [3 upvotes]: The textbook I'm reading from defines a right-inverse as follows:

Let $f: A \to B$ be a function. A right inverse of $f$ is a function $g: B \to A$ with the property that $f \circ g = id_B$ where $id_B$ is the identity function on $B$.

Now, I'm asked to show that $f: A \to B$ has a right inverse iff it is surjective. The author notes that I may use the axiom of choice in this proof. In other words, they say to assume that given a family of disjoint nonempty subsets of a set, there is a way to choose one element in each member of the family.
Proof Attempt: Suppose $f$ has a right inverse. So, there is a function $g: B \to A$ such that $f \circ g = id_B$. Now, choose an element $b \in B$. We observe that $g(b) \in A$ and that, by hypothesis,  $f(g(b)) = id_B(b) = b$. So, we have found an element of $A$ (namely $g(b)$) whose image under $f$ is $b$. Since the choice of $b$ was arbitrary, we conclude that $f$ is surjective.
For the converse, suppose that $f$ is surjective. We need to construct a function $g: B \to A$ such that $f \circ g = id_B$ for all $x \in B$. In order to do this, fix $b \in B$. Since $f$ is surjective, there exists an element $g(b) \in A$ such that $f(g(b)) = b$. However, we note that there may be more than one element of $A$ whose image is $b$ under $f$ (i.e. there may be more than one possible candidate for $g(b)$). In order to isolate a single candidate for $g(b)$, we proceed by cases.
Case 1: The function $f$ sends all elements of $A$ to $b \in B$.
In this case, we may conclude by the surjectivity of $f$ that $b$ is the only element of $B$. Therefore if we pick an element $s \in A$, we may define a function $g: B \to A$ where $g(b) = s$. Then, we simply observe that $f(g(b)) = f(s) = b = id_B(b)$. Since $b$ is the only element of $B$, we may immediately conclude that $g$ is a right inverse of $f$.
Case 2: Only the elements in a proper subset of $A$ are mapped to $b$ by the function $f$.
In this case, we can divide the set $A$ into two disjoint subsets $R$ and $S$ where $R$ is the set of all elements in $A$ that get mapped to $b$ by $f$ and $S$ is the set of all elements of $A$ that are not mapped to $b$ by $f$. By the axiom of choice, I can select a single element $p \in R$ and simply let $g(b) = p$. This shows that for any element $x$ of $B$, I can always find a single candidate for $g(x) \in A$ such that $f(g(x)) =x$. Then, we can properly define a function $g: B \to A$ that sends any $x \in B$ to the single candidate $g(x)$ that we have chosen, and, by construction, $g$ will be a right inverse of $f$. This completes the proof.
Is my proof correct? This is the first time I've done a proof requiring the axiom of choice, so I'm wondering if I've invoked it correctly. Are there any ways that I could improve the proof or details that perhaps I'm missing?

REPLY [5 votes]: The axiom of choice is equivalent to Zorn’s Lemma that is more useful to prove a lot of results.
You can consider this set
$\Lambda:=\{(h,C): C\subseteq B, h: C\to A , f\circ h=Id_C\}$
This set is non-empty because if you consider $a\in A$ then
$(h, \{f(a)\})\in \Lambda \neq \emptyset$ where $h(f(a))=a$
You can fix a particular order $<$ on $\Lambda$ :
$(h,C)< (r,S)$  if and only if $ C\subseteq S$ and $r_{|C}=h$
You can verify that $<$ a partial order on $\Lambda$.
Now we consider a chain $X\subset \Lambda$
Then $(\cup_{(h,C)\in X} h, \cup_{(h,C)\in X} C)\in \Lambda $ and it is a maggiorante for the chain $X$.
So by Zorn’s lemma there exists a maximal element $(h,C)$  for $(\Lambda,<)$.
You can prove that $C=B$ in the hypothesis that $f$ is surjective.
If there exists an element $b\in B/C$ by surjectivity of $f$ there exists an element $a\in A$ such that $f(a)=b$.
Then you can define $r: C\cup \{b\} \to A$ such that $r(x)=h(x)$ if $x\in C$ and $r(x)=a$ if $x=f(a)$.
So $(r,C\cup \{b\})\in \Lambda$ and $(h,C)<(r,C\cup \{b\})$ and it is not possible by maximality of $(h,C)$


text:
\begin{document}

\title[Brauer-Manin obstruction applied to \'etale covers]{Insufficiency of the Brauer-Manin obstruction applied to \'etale covers}
\subjclass[2000]{Primary 11G35; Secondary 14G05, 14G25, 14J20}
\keywords{Rational points, Hasse principle, Brauer-Manin obstruction, descent obstruction, Ch\^atelet surface, conic bundle}
\author{Bjorn Poonen}
\thanks{This research was supported by NSF grant DMS-0301280.}
\address{Department of Mathematics, University of California,
        Berkeley, CA 94720-3840, USA}
\email{poonen@math.berkeley.edu}
\urladdr{http://math.berkeley.edu/\~{}poonen/}
\date{June 8, 2008}

\begin{abstract}
Let $k$ be any global field of characteristic not~$2$.
We construct a $k$-variety $X$ such that $X(k)$ is empty,
but for which the emptiness cannot be explained
by the Brauer-Manin obstruction
or even by the Brauer-Manin obstruction applied to finite \'etale covers.
\end{abstract}

\maketitle

\section{Introduction}\label{S:introduction}

\subsection{Background}

Call a variety \defi{nice} if it is smooth, projective,
and geometrically integral.
(See Sections \ref{S:notation} and~\ref{S:obstructions} for
further terminology used here.)
Let $X$ be a nice variety over a global field $k$.
If $X$ has a $k$-point, then $X$ has a $k_v$-point for every place
$v$ of $k$; i.e., the set $X(\Adeles)$ of adelic points is nonempty.
The converse, known as the \defi{Hasse principle}, does not always hold,
as has been known at least since the 1940s: it can fail for genus-$1$
curves, for instance \cites{Lind1940,Reichardt1942}.
Manin \cite{Manin1971} showed that the Brauer group of $X$
can often explain failures of the Hasse principle:
one can define a subset
$X(\Adeles)^{\Br}$ of $X(\Adeles)$ that contains $X(k)$,
and $X(\Adeles)^{\Br}$ can be empty even when $X(\Adeles)$ is nonempty.

Conditional results \cites{Sarnak-Wang1995,Poonen-complete-intersection2001}
predicted that this Brauer-Manin obstruction
was insufficient to explain all failures of
the Hasse principle.
But the insufficiency was proved only in 1999,
when a groundbreaking paper of Skorobogatov~\cite{Skorobogatov1999}
constructed a variety for which one could prove
$X(\Adeles)^{\Br} \ne \emptyset$ and $X(k)=\emptyset$.
He showed that for a bielliptic surface $X$,
the set $X(\Adeles)^{\et,\Br}$
obtained by applying the Brauer-Manin obstruction to finite \'etale covers
of $X$ could be empty even when $X(\Adeles)^{\Br}$ was not.

\subsection{Our result}

We give a construction to show that even this combination of
finite \'etale descent and the Brauer-Manin obstruction
is insufficient to explain all failures of the Hasse principle.
Our argument does not use \cite{Skorobogatov1999},
so it also gives a new approach to constructing
varieties for which the Brauer-Manin obstruction is insufficient
to explain the failure of the Hasse principle.

The idea behind our construction can be described in a few lines,
though the details will occupy the rest of the paper.
Start with a nice curve $C$ such that $C(k)$ is finite and nonempty.
Construct a nice $k$-variety $X$
with a morphism $\beta \colon X \to C$ such that
\begin{enumerate}
\item[(i)] For each $c \in C(k)$,
the fiber $X_c:=\beta^{-1}(c)$ violates the Hasse principle.
\item[(ii)] Every finite \'etale cover of $X$
arises from an \'etale cover of $C$.
\item[(iii)] The map $\beta$ induces an isomorphism $\Br C \isomto \Br X$,
and this remains true after base extension by any finite \'etale
morphism $C' \to C$.
\end{enumerate}
Properties (ii) and~(iii) imply that $X(\Adeles)^{\et,\Br}$
is the inverse image under $\beta$ of $C(\Adeles)^{\et,\Br}$,
which contains the nonempty set $C(k)$.
Then by~(i), we have $X(\Adeles)^{\et,\Br} \ne \emptyset$
but $X(k)=\emptyset$.

Our $X$ will be a $3$-fold, and the general fiber of $\beta$
will be a Ch\^atelet surface (a kind of conic bundle over $\PP^1$).

\subsection{Commentary}

Suppose in addition that the Jacobian $J$ of $C$ is such that
the Mordell-Weil group $J(k)$ and the Shafarevich-Tate group $\Sha(J)$
are both finite.
(For instance, these hypotheses are known to hold if $C$ is any
elliptic curve over $\Q$ of analytic rank $0$.)
Then $C(\Adeles)^{\Br}$ is essentially (ignoring some technicalities
regarding the connected components at archimedean places)
equal to $C(k)$.
(Scharaschkin and Skorobogatov independently observed that this
follows from the comparison of the Cassels-Tate pairing with the
Brauer evaluation pairing in \cite{Manin1971}:
see \cite{Skorobogatov2001}*{\S6.2} for related results,
and \cite{Stoll2007}*{Theorem~8.6} for a significant generalization.)
Thus $X(\Adeles)^{\Br}$ is essentially a subset of
$\Union_{c \in C(k)} X_c(\Adeles)$.

Also, $X_c(\Adeles)^{\Br}=\emptyset$ for each $c \in C(k)$
(all failures of the Hasse principle for Ch\^atelet surfaces are explained by
the Brauer-Manin obstruction \cites{CT-Sansuc-SD1987I,CT-Sansuc-SD1987II}).
But the elements of $\Br X_c$ used to obstruct $k$-points on the fiber $X_c$
do not extend to elements of $\Br X$,
so it does not follow that $X(\Adeles)^{\Br}$ is empty.

\subsection{Outline of the paper}

Section~\ref{S:notation} introduces some basic notation.
Section~\ref{S:obstructions} recalls some cohomological obstructions
to rational points, and discusses how they relate to one another.
Our $X$, a Ch\^atelet surface bundle over $C$,
will be constructed as a conic bundle over $C \times \PP^1$;
Section~\ref{S:conic bundles} describes the type of conic bundle we need,
and Sections \ref{S:etale covers} and \ref{S:Brauer group}
compute the \'etale covers and Brauer group of this conic bundle.
The Brauer group calculations involve some group cohomology lemmas,
which have been relegated to an appendix.
Section~\ref{S:construction} constructs the particular $X$,
and Sections \ref{S:no BM} and~\ref{S:no descent}
compute $X(\Adeles)^{\Br}$ and $X(\Adeles)^{\et,\Br}$,
respectively.

\section{Notation}\label{S:notation}

Given a field $k$,
we fix a separable closure $\kbar$ of $k$ and define $G_k:=\Gal(\kbar/k)$.
For any $k$-variety $V$, define $\Vbar:=V \times_k \kbar$.
For any nice variety $V$, let $\kappa(V)$ be the function field.
If $D$ is a divisor on a nice variety $V$,
let $[D]$ be its class in $\Pic V$.

An \defi{algebraic group} over $k$
is a smooth group scheme of finite type over $k$.
If $G$ is an algebraic group over $k$ and $X$ is a $k$-variety,
let $H^1(X,G)$ be the cohomology set
defined using \v{C}ech $1$-cocycles for the \'etale topology;
it parameterizes isomorphism classes of torsors over $X$ under $G$.
If moreover $G$ is commutative,
then for any $i \in \Z_{\ge 0}$
define $H^i(X,G)$ as the usual \'etale cohomology group;
this is compatible with the previous definition when $i=1$.
Let $\Br X$ be the cohomological Brauer group $H^2(X,\G_m)$.

By a \defi{global field} we mean either a finite extension of $\Q$
or the function field of a nice curve over a finite field.
If $k$ is a global field, let $\Adeles$ be its ad\`ele ring.

\section{Cohomological obstructions to rational points}\label{S:obstructions}

Let $k$ be a global field.
Let $X$ be a nice $k$-variety.

\subsection{Brauer-Manin obstruction}
(See \cite{Skorobogatov2001}*{\S5.2}.)
There is an evaluation pairing
\[
	\Br X \times X(\Adeles) \to \Q/\Z,
\]
and $X(\Adeles)^{\Br}$ is defined as the set of elements of $X(\Adeles)$
that pair with every element of $\Br X$ to give $0$.
The reciprocity law for $\Br k$
implies $X(k) \subseteq X(\Adeles)^{\Br}$.
In particular, if $X(\Adeles) \ne \emptyset$
but $X(\Adeles)^{\Br} = \emptyset$,
then $X$ violates the Hasse principle.

\subsection{Descent obstruction}

(See \cite{Skorobogatov2001}*{\S5.3}.)
If $G$ is a (not necessarily connected) linear algebraic group over $k$,
and $f\colon Y \to X$ is a right torsor under $G$,
then any $1$-cocycle $\sigma \in Z^1(k,G)$
gives rise to a ``twisted'' right torsor $f^\sigma \colon Y^\sigma \to X$
under a twisted form $G^\sigma$ of $G$.
Moreover, the isomorphism type of the torsor depends only on
the cohomology class $[\sigma] \in H^1(k,G)$.
It is not hard to show that
\begin{equation}
\label{E:coverings}
        X(k) = \Union_{[\sigma] \in H^1(k,G)} f^\sigma(Y^\sigma(k)).
\end{equation}
Therefore $X(k)$ is contained in the set
\[
        X(\Adeles)^f :=
        \Union_{[\sigma] \in H^1(k,G)} f^\sigma(Y^\sigma(\Adeles)).
\]
Define
\[
        X(\Adeles)^\descent := \Intersection X(\Adeles)^f
\]
where the intersection is taken over all linear algebraic groups $G$
and all right torsors $Y \to X$ under $G$.
If $X(\Adeles)^\descent =\emptyset$, then we say that
there is a \defi{descent obstruction} to the existence of a rational point.

\subsection{Brauer-Manin obstruction applied to \'etale covers}

For reasons that will be clearer in Section~\ref{S:comparisons},
it is interesting to combine
descent for torsors under finite \'etale group schemes
with the Brauer-Manin obstruction:
define
\[
	X(\Adeles)^{\et,\Br}:= \Intersection_{\substack{\text{$G$ finite}\\ f \colon Y \to X}} \quad \Union_{[\sigma] \in H^1(k,G)} f^\sigma(Y^\sigma(\Adeles)^{\Br}),
\]
where the intersection is taken over all finite \'etale group schemes $G$
over $k$ and all right torsors $f \colon Y \to X$ under $G$.
We have $X(k) \subseteq X(\Adeles)^{\et,\Br} \subseteq X(\Adeles)^{\Br}$,
where the first inclusion follows from~\eqref{E:coverings},
and the second follows from taking $G=\{1\}$ and $Y=X$ in the definition
of $X(\Adeles)^{\et,\Br}$.

\subsection{Comparisons}
\label{S:comparisons}

Let $X(\Adeles)^\connected$
be defined in the same way as $X(\Adeles)^\descent$,
but using only {\em connected} linear algebraic groups
instead of all linear algebraic groups.
Harari \cite{Harari2002}*{Th\'eor\`eme 2(2)}
showed that $X(\Adeles)^{\Br} \subseteq X(\Adeles)^\connected$,
at least if $k$ is a number field.
In other words, the Brauer-Manin obstruction is strong enough to subsume
all descent obstructions from connected linear algebraic groups.
Also, an arbitrary linear algebraic group
is an extension of a finite \'etale group scheme
by a connected linear algebraic group, so one might ask:
\begin{question}
\label{Q:descent vs et-Br}
Does $X(\Adeles)^{\et,\Br} \subseteq X(\Adeles)^{\descent}$ hold
for every nice variety $X$ over a number field?
\end{question}

This does not seem to follow formally from Harari's result.
But Demarche, in response to an early draft of this paper,
has announced a positive answer~\cite{Demarche2008-preprint}.

\section{Conic bundles}\label{S:conic bundles}

In this section, $k$ is any field of characteristic not $2$.
Let $B$ be a nice $k$-variety.
Let $\calL$ be a line sheaf on $B$.
Let $\calE$ be the rank-3 vector sheaf $\OO \directsum \OO \directsum \LL$
on $B$.
Let $a \in k^\times$
and let $s \in \Gamma(B,\calL^{\tensor 2})$ be a nonzero global section.
The zero locus of
\[
        1 \directsum (-a) \directsum (-s)
        \in \Gamma(B,\OO \directsum \OO \directsum \LL^{\tensor 2})
        \subseteq \Gamma(B,\Sym^2 \calE)
\]
in $\PP\calE$ is a projective geometrically integral scheme $X$
with a morphism $\alpha\colon X \to B$.
If $U$ is a dense open subscheme of $B$ with a trivialization
$\LL|_U \isom \OO_U$
and we identify $s|_U$ with an element of $\Gamma(U,\OO_U)$,
then the affine scheme defined by $y^2-az^2=s|_U$ in $\Aff^2_U$
is a dense open subscheme of $X$.
Therefore we call $X$ the \defi{conic bundle given by $y^2-az^2=s$}.
In the special case where $B=\PP^1$, $\LL = \OO(2)$,
and the homogeneous form $s \in \Gamma(\PP^1,\OO(4))$ is separable,
$X$ is called the \defi{Ch\^atelet surface given by $y^2-az^2 =s(x)$},
where $s(x) \in k[x]$ denotes a dehomogenization of $s$.

Returning to the general case, we let $Z$ be the subscheme $s=0$ of $B$.
Call $Z$ the \defi{degeneracy locus} of the conic bundle.
Each fiber of $\alpha$ above a point of $B-Z$ is a smooth plane conic,
and each fiber above a geometric point of $Z$
is a union of two projective lines crossing transversely at a point.
A local calculation shows that if $Z$ is smooth over $k$,
then $X$ is smooth over $k$.

\begin{lemma}
\label{L:generic fiber}
The generic fiber $\Xbar_\eta$ of $\Xbar \to \Bbar$
is isomorphic to $\PP^1_{\kappa(\Bbar)}$.
\end{lemma}

\begin{proof}
It is a smooth plane conic,
and it has a rational point since $a$ is
a square in $\kbar \subseteq \kappa(\Bbar)$.
\end{proof}

\section{\'Etale covers of conic bundles}\label{S:etale covers}

Given a variety $X$, let $\Et(X)$ be the category of finite \'etale
covers of $X$.
We recall some well-known properties of $\Et(X)$:

\begin{lemma}
\label{L:Et}
Let $X$ be a regular integral variety over a field $k$.
Let $Z \subseteq X$ be a closed subvariety not equal to $X$ itself.
Let $U:=X-Z$.
Then
\begin{enumerate}
\item[(i)]
The inclusion $U \injects X$ induces
a fully faithful functor $\Et(X) \to \Et(U)$.
\item[(ii)]
If the codimension of $Z$ in $X$ is at least $2$,
then $\Et(X) \to \Et(U)$ is an equivalence of categories.
\end{enumerate}
\end{lemma}

\begin{proof}\hfill
\begin{enumerate}
\item[(i)] Use the description of \'etale covers of a normal
integral scheme given in \cite{SGA1}*{I.10.3}.
\item[(ii)] This is ``purity of the branch locus''
\cite{SGA2}*{X.3.3 and X.3.4}.
\qedhere
\end{enumerate}
\end{proof}

\begin{lemma}
\label{L:Et and P^1}
For any $k$-variety $X$, the projection $X \times \PP^1 \to X$
induces an equivalence of categories $\Et(X) \to \Et(X \times \PP^1)$.
\end{lemma}

\begin{proof}
This follows from the fact that $\PP^1$ has no finite \'etale covers
except for those induced by finite \'etale covers of $\Spec k$.
\end{proof}

\begin{lemma}
\label{L:etale covers of birational varieties}
A birational map $\phi\colon X \dashrightarrow Y$ between nice varieties
induces an equivalence of categories $\Et(Y) \to \Et(X)$.
\end{lemma}

\begin{proof}
Let $U = X-Z$ be the dense open subscheme of $X$ on which $\phi$ is defined.
Since $X$ is regular and $Y$ is proper, $Z$ has codimension at least $2$
in $X$.
We have functors $\Et(Y) \to \Et(U) \leftarrow \Et(X)$,
and the second is an equivalence of categories by Lemma~\ref{L:Et}(ii).
In the same way, $\phi^{-1}$ induces a functor $\Et(X) \to \Et(Y)$.
To see that these are inverse equivalences of categories,
use Lemma~\ref{L:Et}(i) to
compare with the equivalence $\Et(Y_1) \to \Et(X_1)$
where $X_1 \subseteq X$ and $Y_1 \subseteq Y$ are nonempty open subschemes
such that $\phi$ restricts to an isomorphism $X_1 \to Y_1$.
\end{proof}

\begin{proposition}
\label{P:etale covers of conic bundle}
Let $\alpha\colon X \to B$ be a conic bundle given by $y^2-az^2=s$
as in Section~\ref{S:conic bundles}, with smooth degeneracy locus.
Then $\Et(B) \to \Et(X)$ is an equivalence of categories.
\end{proposition}

\begin{proof}
By Lemma~\ref{L:generic fiber}, the nice $\kbar$-varieties
$\Xbar$ and $\Bbar \times \overline{\PP^1}$ are birational.
Lemmas \ref{L:Et and P^1} and~\ref{L:etale covers of birational varieties}
gives equivalences
$\Et(\Bbar) \to \Et(\Bbar \times \overline{\PP^1}) \to \Et(\Xbar)$.
The composite equivalence
$\Et(\Bbar) \to \Et(\Xbar)$
is induced by the base extension of a $k$-variety morphism,
so descent data for descending covers over $\kbar$ to covers over $k$
correspond under $\Et(\Bbar) \to \Et(\Xbar)$.
Thus $\Et(B) \to \Et(X)$ is an equivalence too.
\end{proof}

\section{Brauer group of conic bundles}\label{S:Brauer group}

The calculations of this section are similar to
well-known calculations that have been done for conic bundles over $\PP^1$:
see \cite{Skorobogatov2001}*{\S7.1}, for instance.

\begin{lemma}
\label{L:H^1 of Pic}
Let $X \to B$ be as in Section~\ref{S:conic bundles}.
If the degeneracy locus $Z$ is nice, then the homomorphism
$H^1(k,\Pic \Bbar) \stackrel{\alpha^*}\to H^1(k,\Pic \Xbar)$
is an isomorphism.
\end{lemma}

\begin{proof}
We compute $\Pic \Xbar$ in the following paragraphs
by constructing a commutative diagram of $G_k$-modules
\begin{equation}
\label{E:key}
\xymatrix{
0 \ar[r] & \Z \ar[r]^-{\lambda_1} \ar@{=}[d] & \tilde{\Z}^2 \ar[r]^-{\lambda_2} \ar[d]_{\tau_1} & \tilde{\Z}^2 \ar[r]^-{\lambda_3} \ar[d]_{\tau_2} & \Z \ar[r] \ar@{=}[d]_{\deg} & 0 \\
0 \ar[r] & \Z \ar[r]^-{\rho_1} & \Pic \Bbar \directsum \tilde{\Z}^2 \ar[r]^-{\rho_2} & \Pic \Xbar \ar[r]^-{\rho_3} & \Pic \Xbar_\eta \ar[r] & 0 \\
}
\end{equation}
with exact rows.

Let $\tilde{\Z}^2$ be the induced module $\Ind_{G_{k(\sqrt{a})}}^{G_k} \Z$:
as a group it is $\Z^2$, and an element $\sigma \in G_k$ acts on an element
of it either trivially or by interchanging the coordinates,
according to whether $\sigma$ fixes $\sqrt{a}$ or not.

Call a divisor of $\Xbar$ \defi{vertical} if it is supported on
prime divisors lying above prime divisors of $\Bbar$,
and \defi{horizontal} otherwise.
The fiber of $\alpha$ above the generic point of $\Zbar$
consists of two intersecting copies of $\PP^1_{\kappa(\Zbar)}$,
so $\alpha^{-1}(\Zbar)$ is a union of two prime divisors $F_1$ and $F_2$
of $\Xbar$.

Choose $L \in \Div B$ with $[L]=\LL$.
Since $Z$ is the zero locus of $s \in \Gamma(B,\LL^{\tensor 2})$,
the divisor $Z-2L$ is the divisor of some function $g \in \kappa(B)^\times$.
Let $U := B - \supp(L)$.
Then $X$ has an open subscheme $X'$ given by $y^2 - a = g t^2$
in the affine space $\Aff^2_U$ with coordinates $t$ and $y$.
The restrictions of $F_1$ and $F_2$ in $\Div X'$
are given by $y-\sqrt{a}=g=0$ and $y+\sqrt{a}=g=0$;
we may assume that the former is $F_1$.
The Zariski closures in $\Xbar$ of the divisors
given by $y-\sqrt{a}=t=0$ and $y+\sqrt{a}=t=0$
are horizontal; call them $H_1$ and $H_2$.
We choose a function $f \in \kappa(\Xbar)^\times$
that on the generic fiber
induces an isomorphism $\Xbar_\eta \to \PP^1_{\kappa(\Bbar)}$
(the usual parameterization of a conic);
explicitly, we take
\[
        f:= \frac{y-\sqrt{a}}{t} = \frac{g t}{y+\sqrt{a}}.
\]
A straightforward calculation shows that the divisor of $f$ on $\Xbar$ is
\begin{equation}
\label{E:divisor}
        (f) = H_1 - H_2 + F_1 - \alpha^* L.
\end{equation}

{\em Bottom row:}
Define $\rho_1$ by $\rho_1(1)=(-2\calL,(1,1))$.
Define $\rho_2(\calM,(m,n))=\alpha^*\calM + m[F_1] + n[F_2]$.
Let $\rho_3$ be restriction.
Each $\rho_i$ is $G_k$-equivariant.
Given a prime divisor $D$ on $\Xbar_\eta$,
its Zariski closure in $\Xbar$ restricts to give $D$ on $\Xbar_\eta$,
so $\rho_3$ is surjective.
The kernel of $\rho_3$
is generated by the classes of vertical prime divisors of $\Xbar$;
in fact, there is exactly one above each prime divisor of $\Bbar$
except that above $\Zbar \in \Div \Bbar$ we have $F_1, F_2 \in \Div \Xbar$.
This proves exactness at $\Pic \Xbar$ of the bottom row.
Since $s \in \Gamma(B,\LL^{\tensor 2})$,
we have $[Z]=2\LL$, and $[F_1]+[F_2] = \alpha^* [Z] = 2 \alpha^* \LL$.
Also, a rational function on $\Xbar$ with vertical divisor
must be the pullback of a rational function on $\Bbar$;
The previous two sentences prove exactness
at $\Pic \Bbar \directsum \tilde{\Z}^2$.
Injectivity of $\rho_1$ is trivial,
so this completes the proof that the bottom row of~\eqref{E:key}
is exact.

{\em Top row:}
Define
\begin{align*}
  \lambda_1(m) &= (m,m) \\
  \lambda_2(m,n) &= (n-m,m-n) \\
  \lambda_3(m,n) &= m+n.
\end{align*}
These maps are $G_k$-equivariant and
they make the top row of~\eqref{E:key} exact.

{\em Vertical maps:}
By Lemma~\ref{L:generic fiber},
we have an isomorphism $\deg \colon \Pic \Xbar_\eta \isom \Z$
of $G_k$-modules; this defines the rightmost vertical map in~\eqref{E:key}.
Define
\begin{align*}
   \tau_1(m,n) &= (-(m+n)\LL,(m,n)) \\
   \tau_2(m,n) &= m [H_1] + n [H_2].
\end{align*}
These too are $G_k$-equivariant.

Commutativity of the first square is immediate from the definitions.
Commutativity of the second square follows from~\eqref{E:divisor}.
Commutativity of the third square follows since $H_1$ and $H_2$
each meet the generic fiber $\Xbar_\eta$ in a single $\kappa(\Bbar)$-rational
point.
This completes the construction of~\eqref{E:key}.

We now take cohomology by applying results of Appendix~\ref{A:cohomology}.
Because of the vertical isomorphisms at the left and right ends
of~\eqref{E:key}, the two rows define the same class $\xi \in H^2(G_k,\Z)$.
We have $H^0(G_k,\tilde{\Z}^2) = \Z \cdot (1,1)$,
and Shapiro's lemma yields
\begin{equation}
\label{E:Shapiro}
        H^1(G_k,\tilde{\Z}^2)=H^1(G_{k(\sqrt{a})},\Z)=0,
\end{equation}
so Lemma~\ref{L:nonzero H^2} implies $\xi \ne 0$.
We are almost ready to apply Lemma~\ref{L:2-extension}
to the bottom row of~\eqref{E:key},
but first we must check the splitting hypotheses.
After restricting from $G_k$ to $G_{k(\sqrt{a})}$,
the injection $\rho_1$ is split by the projection
$\Pic \Bbar \directsum \Z^2 \to \Z$ onto the last factor,
and the surjection $\rho_3$ is split by the map sending a positive generator
of $\Pic \Xbar_\eta$ to $[H_1] \in \Pic \Xbar$.
Now Lemma~\ref{L:2-extension} yields an isomorphism
\[
        H^1(G_k,\Pic \Bbar \directsum \tilde{\Z}^2) \to H^1(G_k,\Pic \Xbar)
\]
and the first group equals $H^1(G_k,\Pic \Bbar)$ by~\eqref{E:Shapiro}.
\end{proof}

\begin{lemma}
\label{L:ruled}
If $W$ and $Y$ are nice $k$-varieties,
and $W$ is birational to $Y \times \PP^1$,
then the homomorphism $\Br Y \to \Br W$
induced by the composition $W \dashrightarrow Y \times \PP^1 \to Y$
is an isomorphism.
\end{lemma}

\begin{proof}
Use the birational invariance of the Brauer group
and the isomorphism $\Br(Y \times \PP^1) \isom \Br Y$.
\end{proof}

\begin{lemma}
\label{L:Br Xbar}
Let $X \to B$ be as in Section~\ref{S:conic bundles}.
If $\Br \Bbar=0$, then $\Br \Xbar=0$.
\end{lemma}

\begin{proof}
Apply Lemmas \ref{L:generic fiber} and~\ref{L:ruled}.
\end{proof}

\begin{proposition}
\label{P:Br X}
Let $X \to B$ be as in Section~\ref{S:conic bundles}.
Suppose in addition that
\begin{itemize}
\item $k$ is a global field (still of characteristic not $2$),
\item the degeneracy locus $Z$ is nice,
\item $\Br \Bbar=0$, and
\item $X(\Adeles) \ne \emptyset$.
\end{itemize}
Then $\alpha^*\colon \Br B \to \Br X$ is an isomorphism.
\end{proposition}

\begin{proof}
The Hochschild-Serre spectral sequence yields an exact sequence
\[
        \Br k
        \to \ker\left(\Br X \to \Br \Xbar \right)
        \to H^1(k,\Pic \Xbar)
        \to H^3(k,\G_m).
\]
Since $\Br k \to \Directsum_v \Br k_v$ is injective
and $X(\Adeles)\ne \emptyset$,
the homomorphism $\Br k \to \Br X$ is injective.
By Lemma~\ref{L:Br Xbar}, we have $\Br \Xbar=0$.
Finally, $H^3(k,\G_m)=0$.
Thus we obtain a short exact sequence, the second row of
\[
\xymatrix{
0 \ar[r] & \Br k \ar[r] \ar@{=}[d] & \Br B \ar[r] \ar[d] & H^1(k,\Pic \Bbar) \ar[d] \ar[r] & 0 \\
0 \ar[r] & \Br k \ar[r] & \Br X \ar[r] & H^1(k,\Pic \Xbar) \ar[r] & 0. \\
}
\]
The first row is obtained in the same way, and the vertical maps
are induced by $\alpha$.
The result now follows from Lemma~\ref{L:H^1 of Pic}.
\end{proof}

\begin{remark}
\label{R:alternative proof}
In response to an earlier draft of this paper,
Colliot-Th\'el\`ene has found an alternative proof
of Proposition~\ref{P:Br X}:
see~\cite{Colliot-Thelene2008-preprint}*{Proposition~2.1}.
This proof, which is a little shorter and works in slightly greater
generality, compares $\Br X$ and $\Br B$ using residue maps
instead of going through $H^1(k,\Pic \Xbar)$
and $H^1(k,\Pic \Bbar)$.
\end{remark}

\section{Construction}\label{S:construction}

{}From now on, $k$ is a global field of characteristic not $2$.
Fix $a \in k^\times$,
and fix relatively prime separable
degree-$4$ polynomials $P_\infty(x), P_0(x) \in k[x]$
such that the (nice) Ch\^atelet surface $\calV_\infty$ given by
\[
        y^2 - a z^2 = P_\infty(x)
\]
over $k$ satisfies $\calV_\infty(\Adeles)\ne \emptyset$
but $\calV_\infty(k)=\emptyset$.
(Such Ch\^atelet surfaces exist over any global field $k$
of characteristic not~$2$:
see \cite{Poonen-chatelet-preprint}*{Proposition~5.1 and \S11}.
If $k=\Q$, one may use the original example from~\cite{Iskovskikh1971},
with $a:=-1$ and $P_\infty(x):=(x^2-2)(3-x^2)$.)
Let $\tilde{P}_\infty(w,x)$ and $\tilde{P}_0(w,x)$ be the homogenizations
of $P_\infty$ and $P_0$.
Define $\LL:=\OO(1,2)$ on $\PP^1 \times \PP^1$
and define
\[
        s_1:=u^2 \tilde{P}_\infty(w,x) + v^2 \tilde{P}_0(w,x)
                \in \Gamma(\PP^1 \times \PP^1,\LL^{\tensor 2}),
\]
where the two copies of $\PP^1$ have homogeneous coordinates $(u,v)$
and $(w,x)$, respectively.
Let $Z_1 \subset \PP^1 \times \PP^1$ be the zero locus of $s_1$.
Let $F \subset \PP^1$ be the (finite) branch locus of the
first projection $Z_1 \to \PP^1$.

Let $\alpha_1 \colon \calV \to \PP^1 \times \PP^1$
be the conic bundle given by $y^2-az^2=s_1$,
in the terminology of Section~4.
Composing $\alpha_1$ with the first projection $\PP^1 \times \PP^1 \to \PP^1$
yields a morphism $\beta_1 \colon \calV \to \PP^1$
whose fiber above $\infty:=(1:0)$ is the Ch\^atelet surface $\calV_\infty$
defined earlier.

Let $C$ be a nice curve over $k$
such that $C(k)$ is finite and nonempty.
Choose a dominant morphism $\gamma \colon C \to \PP^1$,
\'etale above $F$, such that $\gamma(C(k))=\{\infty\}$.

Define the fiber product $X:= \calV \times_{\PP^1} C$
and morphisms $\alpha$ and $\beta$ as in the diagram
\[
\xymatrix{
X \ar[d]_{\alpha} \ar@/^2.5pc/[dd]^>>>>>>{\beta} \ar[rr] && \calV \ar[d]_{\alpha_1} \ar@/^2.5pc/[dd]^>>>>>>{\beta_1} \\
C \times \PP^1 \ar[rr]^{(\gamma,1)} \ar[d]_{1^{\operatorname{st}}} && \PP^1 \times \PP^1 \ar[d]_{1^{\operatorname{st}}} \\
C \ar[rr]^\gamma && \PP^1. \\
}
\]
Each map labeled $1^{\operatorname{st}}$ is the first projection.
Define $B:=C \times \PP^1$
and $s :=(\gamma,1)^* s_1 \in \Gamma(B,(\gamma,1)^* \OO(2,4))$.
Thus $X \stackrel{\alpha}\to B$ can alternatively be described as
the conic bundle given by $y^2-az^2=s$.
Its degeneracy locus $Z$ is $(\gamma,1)^* Z_1 \subset B$.

\section{No Brauer-Manin obstruction}\label{S:no BM}

We continue with the notation of Section~\ref{S:construction}.

\begin{lemma}
\label{L:curve Z}
The curve $Z$ is nice.
\end{lemma}

\begin{proof}
Since $P_0(x)$ and $P_\infty(x)$ are separable and have no common factor,
a short calculation shows that $Z_1$ is smooth over $k$.
We have $Z = Z_1 \times_{\PP^1} C$.
Since $Z_1$ and $C$ are smooth over $k$
and the branch loci of $Z_1 \to \PP^1$ and $C \to \PP^1$ do not intersect,
$Z$ is smooth too.
Since $Z_1$ is ample on $\PP^1 \times \PP^1$ and $\gamma$ is finite,
$Z$ is ample on $C \times \PP^1$.
Therefore, $Z$ is geometrically connected
by \cite{Hartshorne1977}*{Corollary~III.7.9}.
Since $Z$ is also smooth, it is geometrically integral.
\end{proof}

Lemma~\ref{L:curve Z} and the sentence before Lemma~\ref{L:generic fiber}
imply that the $3$-fold $X$ is nice.

\begin{theorem}
\label{T:no BM obstruction}
We have $X(k)=\emptyset$,
but $X(\Adeles)^{\Br}$ contains $\calV_\infty(\Adeles) \times C(k)$
and hence is nonempty.
\end{theorem}

\begin{proof}
Since $\gamma(C(k))=\{\infty\}$ and $\calV_\infty(k)=\emptyset$,
we have $X(k)=\emptyset$.

We have $\Br \Bbar = \Br(\Cbar \times \overline{\PP^1}) = \Br \Cbar = 0$,
by Lemma~\ref{L:ruled} and \cite{Grothendieck-Brauer3}*{Corollaire~5.8}.
Also, $X(\Adeles)$ contains $\calV_\infty(\Adeles) \times C(k)$,
so $X(\Adeles) \ne \emptyset$.
Thus Proposition~\ref{P:Br X} implies that $\Br B \to \Br X$ is an isomorphism.
Composing with the isomorphism $\Br C \to \Br B$ of Lemma~\ref{L:ruled}
shows that $\beta^* \colon \Br C \to \Br X$ is an isomorphism.
Hence, if $\beta_\Adeles \colon X(\Adeles) \to C(\Adeles)$
is the map induced by $\beta$,
then
\[
        X(\Adeles)^{\Br}
        = \beta_\Adeles^{-1}(C(\Adeles)^{\Br})
        \supseteq \beta_{\Adeles}^{-1}(C(k))
        = \calV_\infty(\Adeles) \times C(k).
\]
\end{proof}

\section{No Brauer-Manin obstruction applied to \'etale covers}\label{S:no descent}

We continue with the notation of Section~\ref{S:construction};
in particular, $X$ is the nice $3$-fold defined there.

\begin{theorem}
\label{T:no descent obstruction}
The set $X(\Adeles)^{\et,\Br}$ contains
$\calV_\infty(\Adeles) \times C(k)$
and hence is nonempty.
\end{theorem}

\begin{proof}
Lemma~\ref{L:Et and P^1} applied to $C$
and Proposition~\ref{P:etale covers of conic bundle}
applied to $X \to B = C \times \PP^1$
yield equivalences of categories
$\Et(C) \to \Et(C \times \PP^1) \to \Et(X)$.

Let $G$ be a finite \'etale group scheme over $k$,
and let $f\colon Y \to X$ be a right torsor under $G$.
The equivalence $\Et(C) \to \Et(X)$ implies that $f$ arises from
a right torsor $h \colon \calC \to C$ under $G$.
In other words, we have a cartesian square
\[
\xymatrix{
Y \ar[r]^f \ar[d]^b & X \ar[d]^\beta \\
\calC \ar[r]^h & C. \\
}
\]
For any $\sigma \in Z^1(k,G)$ with $\calC^\sigma(k) \ne \emptyset$,
the twisted morphism $b^\sigma \colon Y^\sigma \to \calC^\sigma$
is just like $\beta\colon X \to C$,
since in Section~\ref{S:construction}
we could have replaced $\gamma$ with the composition
$D \injects \calC^\sigma \stackrel{h^\sigma}\to C \stackrel{\gamma}\to \PP^1$
for any connected component $D$ of $\calC^\sigma$ containing a $k$-point;
thus $Y^\sigma(\Adeles)^{\Br}$
contains $\calV_\infty(\Adeles) \times \calC^\sigma(k)$
and $f^\sigma(Y^\sigma(\Adeles)^{\Br})$ contains
$\calV_\infty(\Adeles) \times h(\calC^\sigma(k))$.
Taking the union over all such $\sigma$,
and applying the analogue of~\eqref{E:coverings} for $h \colon \calC \to C$,
we see that
\[
        \Union_{[\sigma] \in H^1(k,G)} f^\sigma(Y^\sigma(\Adeles)^{\Br})
\]
contains $\calV_\infty(\Adeles) \times C(k)$.
Finally, intersect over all $G$ and all $f\colon Y \to X$.
\end{proof}

\begin{remark}
Suppose that $k$ is a number field.
As mentioned in Section~\ref{S:comparisons},
Demarche has announced a proof that
$X(\Adeles)^{\et,\Br} \subseteq X(\Adeles)^{\descent}$
holds for every nice $k$-variety $X$ \cite{Demarche2008-preprint}.
Assuming this, Theorem~\ref{T:no descent obstruction}
implies that $X(\Adeles)^{\descent}$ is nonempty for our $X$,
and in particular that even the descent obstruction is insufficient
to explain all failures of the Hasse principle.
\end{remark}

\begin{remark}
It is not true that $\beta$ induces an isomorphism $H^1(C,G) \to H^1(X,G)$
for every linear algebraic group $G$.
It fails for $G=\G_m$, for instance, as pointed out to me
by Colliot-Th\'el\`ene:
the composition $\Pic C \to \Pic X \to \Pic X_\eta \isom \Z$ is zero
but $\Pic X \to \Pic X_\eta$ is nonzero.

So the proof of Theorem~\ref{T:no descent obstruction}
does not directly generalize to prove $X(\Adeles)^{\descent} \ne \emptyset$.
\end{remark}

\begin{remark}
In~\cite{Colliot-Thelene1997} it is conjectured that for every nice variety
over a number field, the Brauer-Manin obstruction is the only
obstruction to the existence of a zero-cycle of degree~$1$.
In response to an early draft of this paper, Colliot-Th\'el\`ene
has verified this conjecture for the $3$-folds $X$
we constructed~\cite{Colliot-Thelene2008-preprint}*{Th\'eor\`eme~3.1}.
\end{remark}

\appendix
\section{Group cohomology}\label{A:cohomology}

In this section, $G$ is a profinite group and
\begin{equation}
\label{E:2-extension}
        0 \to \Z \to A \stackrel{\phi}\to B \to \Z \to 0
\end{equation}
is an exact sequence of discrete $G$-modules,
with $G$ acting trivially on each copy of $\Z$.
Let $C=\phi(A)$.
Split \eqref{E:2-extension} into short exact sequences
\begin{align*}
        0 \to \Z \to A &\to C \to 0 \\
                     0 &\to C \to B \to \Z \to 0.
\end{align*}
Take cohomology and use $H^1(G,\Z)=\Hom_{\conts}(G,\Z)=0$
to obtain exact sequences
\begin{align}
\nonumber  0 \to H^1(G,A) &\to H^1(G,C) \stackrel{\delta_2}\to H^2(G,\Z) \\
\label{E:delta_1}
           H^0(G,B) \to \Z &\stackrel{\delta_1}\to H^1(G,C) \to H^1(G,B) \to 0
\end{align}
Let $\xi = \delta_2(\delta_1(1)) \in H^2(G,\Z)$.
(Thus $\xi$ is the class of the $2$-extension~\eqref{E:2-extension}.)

\begin{lemma}
\label{L:nonzero H^2}
If $H^0(G,B) \to \Z$ is not surjective and $H^1(G,A)=0$, then $\xi \ne 0$.
\end{lemma}

\begin{proof}
Non-surjectivity of $H^0(G,B) \to \Z$ implies $\delta_1(1) \ne 0$,
and $H^1(G,A)=0$ implies that $\delta_2$ is injective.
Thus $\xi \ne 0$.
\end{proof}

\begin{lemma}
\label{L:2-extension}
If $\xi \ne 0$, and the injection $\Z \to A$ and the surjection $B \to \Z$
are both split after restriction to an index-$2$ open subgroup $H$ of $G$,
then the homomorphism $H^1(G,A) \to H^1(G,B)$ induced by $\phi$
is an isomorphism.
\end{lemma}

\begin{proof}
Let $I$ be the image of $\delta_2$
in $H^2(G,\Z) \isom \Hom_{\conts}(G,\Q/\Z)$.
Let $J$ be the image of $\delta_1$.
The splitting of the injection implies that
$I \subseteq \ker\left(\Hom_{\conts}(G,\Q/\Z) \to \Hom_{\conts}(H,\Q/\Z)\right)
\isom \Hom(G/H,\Q/\Z)$, so $\#I \le 2$.
The splitting of the surjection implies that $2J=0$,
but $J$ is cyclic, so $\# J \le 2$.
Since $\xi \ne 0$, the composition
$\Z \stackrel{\delta_1}\to H^1(G,C) \stackrel{\delta_2}\to H^2(G,\Z)$
is nonzero, so the induced map $J \to I$ is nonzero.
Therefore $\#I=\#J=2$ and $J \to I$ is an isomorphism.
In particular, $H^1(G,C) \isom H^1(G,A) \directsum J$,
and \eqref{E:delta_1} then yields
\[
        0 \to J \to H^1(G,A) \directsum J \to H^1(G,B) \to 0,
\]
with $J$ mapping identically to $0 \directsum J$.
Thus the map $H^1(G,A) \to H^1(G,B)$ is an isomorphism.
\end{proof}

\section*{Acknowledgements}

I thank Jean-Louis Colliot-Th\'el\`ene for several comments,
and in particular for suggesting the algebraic
approach in Section~\ref{S:etale covers}
replacing my original topological argument using
fundamental groups of complex varieties,
which worked only in characteristic~$0$.
I thank also Martin Olsson.

\end{document}

config: arxiv


TITLE: Solution of this non-linear PDE
QUESTION [2 upvotes]: What is the general solution $h: \mathbb{R}^2 \rightarrow \mathbb{C}$ (or maybe $h: \mathbb{C}^2 \rightarrow \mathbb{C}$ if necessary), $(x, y) \mapsto h(x, y)$ to the non-linear partial differential equation
$$
h_x^2 + h_y^2 = -1
$$
where the subscript denotes a partial derivative. I tried to approach the problem by looking at limiting cases and using ansatz, but nothing interesting came out.

REPLY [0 votes]: $h_x^2+h_y^2=-1$
$h_x^2=-h_y^2-1$
$h_x=\pm i\sqrt{h_y^2+1}$
$h_{xy}=\pm\dfrac{ih_yh_{yy}}{\sqrt{h_y^2+1}}$
Let $u=h_y$ ,
Then $u_x=\pm\dfrac{iuu_y}{\sqrt{u^2+1}}$
$u_x+\mp\dfrac{iuu_y}{\sqrt{u^2+1}}=0$
Follow the method in http://en.wikipedia.org/wiki/Method_of_characteristics#Example:
$\dfrac{dx}{dt}=1$ , letting $x(0)=0$ , we have $x=t$
$\dfrac{du}{dt}=0$ , letting $u(0)=u_0$ , we have $u=u_0$
$\dfrac{dy}{dt}=\mp\dfrac{iu}{\sqrt{u^2+1}}=\mp\dfrac{iu_0}{\sqrt{u_0^2+1}}$ , letting $y(0)=f(u_0)$ , we have $y=\mp\dfrac{iu_0t}{\sqrt{u_0^2+1}}+f(u_0)=\mp\dfrac{iux}{\sqrt{u^2+1}}+f(u)$ , i.e. $u=F\left(y\pm\dfrac{iux}{\sqrt{u^2+1}}\right)$


TITLE: Explicit solution for a linear program with two constraints
QUESTION [0 upvotes]: This is not a homework problem, although it wouldn't surprise me if it happens to exist in a textbook somewhere.  Is there an explicit solution for the linear program $$\max_x c^Tx ~~ s.t. \\ d^Tx = q \\ \mathbf{1}^Tx = 1 \\ x \geq 0$$where $\mathbf{1}$ denotes a vector of all ones?  Obviously, we know that there will be at most two non-zero entries $x_i$, and if we were to remove the constraint $d^Tx=q$ then the solution would simply have $x_i=0$ where $i$ is the index of the largest element of $c$.

REPLY [0 votes]: This post captured my imagination for some reason!
I spent a lot of time looking at the dual problem. I managed to simplify it down to this univariate piecewise-linear minimization:
$$\text{minimize} ~ \max_i c_i - (q-d_i) y$$
$y$ is actually the Lagrange multiplier for the $d^Tx=q$ constraint.
Assuming the original problem is feasible and otherwise non-trivial (i.e., $d\neq q\vec{1}$), the solution to the dual problem lies at a vertex: a point at which two of the values of $c_i - (q-d_i) y$ are equal. The two indices $i_1$ and $i_2$ that achieve this equality are the indices of the two non-zero elements of $x$. (Ties can be broken arbitrarily.) You can prove this with complementary slackness, if you are so inclined.
So the faster you can solve this piecewise linear minimization, the faster you can solve the problem.
But once it was clear that you could find a solution with no more than two nonzeros---that is, assuming it is feasible in the first place---the simplest thing to do is just to enumerate the pairs. That is, for each $i,j=1,2,\dots, n$, $i<j$ solve the two-variable problem analytically, and select the best result from all of those. In other words, for each pair of indices, consider the linear system
$$\begin{bmatrix} d_i & d_j \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x_i \\ x_j \end{bmatrix} = \begin{bmatrix} q \\ 1 \end{bmatrix}$$
There are three cases:

If $d_i=d_j=q$, the solution is $\max\{c_i,c_j\}$.
If $d_i=d_j$ and $d_i\neq q$, there is no solution; do not consider this pair.
Otherwise, solve for $x_i,x_j$. If $0\leq x_i,x_j\leq 1$, the solution is $c_ix_i+c_jx_j$.

Once you've scanned all the pairs, the candidate with the best objective function is your answer. (If none of the pairs yielded a candidate, the problem is infeasible.) So you have at most $n(n-1)/2$ candidates to consider, each of which costs $O(1)$ flops to solve. That's pretty darn cheap as algorithms go.
You don't have to settle for this brute force method, if you can instead find a way to solve that dual piecewise linear minimization more quickly. But when I began to look at this, I quickly concluded that it was probably an $O(n^2)$ enterprise as well. Once I realized that, I figured that there was little point in wasting my time on anything but the most obvious approach.


TITLE: The boundedness of Galerkin approximates in Navier-Stokes equations
QUESTION [1 upvotes]: Exercise 7.6 ( page 152 and page 157) In the book The Three-Dimensional Navier-Stokes Equations, James C. Robinson, Jose L. Rorigo, Witold Sadowski. Cambridge  University press:
" Let the domain be bounded and smooth in the space, and $\frac{1}{2}\frac{d}{dt}\|A^{s/2}u_n\|_2^2+\|A^{(s+1)/2}u_n\|_2^2\le|\langle P_n[(u_n\cdot\nabla )u_n)], A^su_n\rangle|$. Prove that
$\frac{d}{dt}\|A^{s/2}u_n\|_2^2+\|A^{(s+1)/2}u_n\|_2^2\le c\|u_n\|^2_{H^s}\|A^{s/2}u_n\|_2^2$"
Please help me to prove this exercise.
I try to perform three following steps, but I am not successful at Step 2:
Step 1:
$|\langle P_n[(u_n\cdot\nabla )u_n)], A^su_n\rangle|=|\langle A^{s/2}P_n[(u_n\cdot\nabla )u_n)], A^{s/2}u_n\rangle|$
Step 2:
$|\langle A^{s/2}P_n[(u_n\cdot\nabla )u_n)], A^{s/2}u_n\rangle|\le c\| A^{s/2}(u_n\cdot\nabla )u_n)\|_2\|A^{s/2}u_n\|_2
$
Step 3 ( using Young inequality):
$\| A^{s/2}(u_n\cdot\nabla )u_n)\|_2\|A^{s/2}u_n\|_2\le c\|u_n\|^2_{H^s}\|A^{s/2}u_n\|_2^2+ \|A^{(s+1)/2}u_n\|_2^2$
However, I can not prove Step 2$.
Thank you very much.

REPLY [1 votes]: Your step 2 won't work because $A$ and $P_n$ don't commute: you have to distinguish between the case $s=2k$ or $s=2k+1$, $k \in \mathbb{N}$.
For instance, if $s=2k$, you shall write by Cauchy-Schwarz
$$|\langle A^{s/2}P_n[(u_n\cdot\nabla )u_n)], A^{s/2}u_n\rangle|\le \| A^{s/2} P_n(u_n\cdot\nabla )u_n)\|_2\|A^{s/2}u_n\|_2,$$
so that
$$|\langle A^{s/2}P_n[(u_n\cdot\nabla )u_n)], A^{s/2}u_n\rangle|\le c\| P_n(u_n\cdot\nabla )u_n)\|_{H^s}\|A^{s/2}u_n\|_2,$$
by using standard elliptic regularity estimates for the Stokes operator $A$.


TITLE: ODE solution as power series
QUESTION [4 upvotes]: Consider the equation
$$(x+3)y''+2y'-4(x+3)y=0.$$
I was trying to solve it by finding the solution in the form of power series. However, I stuck while trying to find any regularity in the coefficients, while Wolfram Alpha provides a pretty much nice answer. Could you please point out the direction?

REPLY [0 votes]: You could certainly use power series, but I use the expansion about the point $x=-3$ rather than $x=0$ (since you have those $(x+3)$ terms). Alternatively, let $z(x)=(x+3)y(x)$, so $z'=(x+3)y'+y$ and $z''=(x+3)y''+2y'$. You can then find a fairly simple ODE for $z$ and solve it however you like.


TITLE: $K_{r+1}$-free graph with maximum number of edges contains $K_r$
QUESTION [1 upvotes]: If $n>r$ and $G$ be an $n$-vertex, $K_{r+1}$-free graph with the
maximum number of edges. Then $G$ contains $K_r$.

I was reading the proof of Turan's theorem and the author uses the above fact. I do not think that it is obvious and I guess it is true due to maximality. So I have decided to prove it.
Proof: Suppose that $G=(V(G),E(G))$ is a $K_r$-free graph and let $V(G)=\{v_1,\dots,v_n\}$, where $n\geq r+1$. There exists $k,\ell$ such that $v_{k}v_{\ell}\notin E(G)$. Consider the new graph $\widehat{G}=(V(G),E(G)\cup \{v_kv_{\ell}\})$ and we see that $e(\widehat{G})>e(G)$.
I claim that $\widehat{G}$ is a $K_{r+1}$-free graph. If this is not true, then $\{v_{i_1},\dots,v_{i_{r+1}}\}$ is a clique of size $r+1$ in $\widehat{G}$ for some $1\leq i_1<\dots<i_r\leq n$. But it is not a clique in $G$, then $\exists i,j$ such that $v_iv_j\notin E(G)$. It immediately implies that $v_iv_j=v_{k}v_{\ell}$. Consider $\{v_{i_1},\dots,v_{i_{r+1}}\}\setminus \{v_k\}$ and it is a clique of size $r$ in $\widehat{G}$ but not in $G$. Hence $\exists \alpha,\beta\neq k$ such that $v_{\alpha}v_{\beta}=v_{k}v_{\ell}$. Hence $(k=\alpha)\lor (k=\beta)$ which is a contradiction.
Therefore, we were able to construct the new graph $\widehat{G}$ which is $K_{r+1}$-free such that it has more edges than $G$.
I was wondering is there a more intuitive explanation\proof of this fact?

REPLY [2 votes]: As requested, expanding my comment to an answer:
Let $G$ be a maximal $K_{r + 1}$-free graph on $V$, meaning that $G \cup e$ contains $K_{r + 1}$ for every potential edge not already in $G$.  (The maximum graphs you're after are all of this form, since otherwise you could add an edge, but there are more maximal ones that are not maximum.)  Let's add a single edge to $G$, producing the graph $G \cup e$ that contains $K_{r + 1}$.  Now consider that $K_{r + 1}$-subgraph.  All but one of its edges belongs to $G$ (the exception is $e$).  But $K_{r + 1} - e$ contains a $K_r$ subgraph.  Therefore $G$ contains a $K_r$ subgraph.


TITLE: How is momentum conservation valid in the vertical direction in this scenario?
QUESTION [3 upvotes]: In the given situation, a small block of mass $m$ is projected
    horizontally with a speed $u$ on a large curved wedge of mass $M$.
    According to one of my books, the block will gain both horizontal
    velocity $V_x$ and vertical velocity $V_y$ as shown in the picture.

My questions are:

How does the block possibly attain a vertical velocity upward, though initially the momentum is $0$ in vertical direction ? How is momentum conserved in vertical direction even though the larger wedge cannot move vertically downward ?
Does it depend upon whether wedge is free to move or not ? (In this situation the wedge is said to be free to move).

Assume all surfaces to be friction-less.

REPLY [3 votes]: The block slides up. Like a ski jump arcade game (where the ball starts rolling horizontally but hits a ramp at the end and jumps up into the hoops) .

(source: bmigaming.com)
Momentum is not conserved in the z direction since obviously the ground is providing a normal force.  You could think of the "lost" momentum being transfered into an imperceptible change in the momentum of the earth.
Think about when you pick up a book: the book has vertical momentum even though your arm isnt moving in the opposite direction to conserve momentum.  Rather, the normal force from the floor is translated through your body so that the system of you + earth+book conserve momentum.

It does depend on whether the wedge can move or not:  if the wedge is totally free to move then instead of being projected upwards, the small block will "stick" to the wedge and the combined body will continue to move in the direction of the blocks initial velocity (with a new velocity preserving momentum of the combined system).  Of course in most real life scenarios the wedge will have some friction with the ground below it and so there will be a combination of these two effects (i.e. block energy is translated into both horizontal motion of wedge and vertical/horizontal motion of block).


TITLE: Hoffman and Kunze, Linear algebra , Chapter 3 , Corollary of theorem 17
QUESTION [0 upvotes]: Theorem $17.$ Let $V$ be a finite-dimensional vector space over the field $F.$ For each vector $\alpha$ in $V$ define
$$L_{\alpha}(f)=f(\alpha),\hspace{1cm}f\text{ in } V^{*}.$$
The mapping $\alpha \to L_{\alpha}$ is then an isomorphism of $V$ onto $V^{**}.$
Corollary. Let $V$ be a finite-dimensional vector space over the field $F.$ If $L$ is a linear functional on the dual space $V^{*}$ of $V,$ then there is a unique vector $\alpha$ in $V$ such that $$L(f)=f(\alpha)$$ for every $f$ in $V^{*}.$
The corollary being an obvious consequence is something that I am not able to see. This is probably because I started out this way :
Corollary says $\Bigg(\forall L\in V^{**}\Big(\exists \alpha \in V$ s.t$\big(\forall f \in V^{*} , L(f)=f(\alpha)\big)\Big)\Bigg).$
This means that $\Bigg(\exists L\in V^{**}$ s.t $\Big(\forall \alpha \in V\big(\exists f \in V^{*} $ s.t $ L(f)\ne  f(\alpha)\big)\Big)\Bigg)$ should be a false statement.
Going this way, suppose there exists such an $L$ and $f$ such that $L(f)\ne f(\alpha)$ for all $\alpha.$ Integrating this with Theorem $17,$ we see that $L\ne L_{\alpha}$ for any $\alpha.$ But $\{L_{\alpha}\}_{\alpha \in V}$ exhausts $V^{**}$ $\square .$

Is this the contradiction that I should arrive at? Also I highly believe that what I have done is unnecessary complication of the problem, if so, please put forth a simple one.

REPLY [2 votes]: If $V \ni \alpha \mapsto L_\alpha \in V^{\ast \ast}$ is an isomorphism, in particular it is surjective. So given $L \in V^{\ast\ast}$ there is an unique (because of injectiveness) $\alpha \in V$ such that $L = L_\alpha$. So, for all $f \in V^{\ast}$ you have $$L(f) = L_\alpha(f) = f(\alpha),$$as wanted.

REPLY [1 votes]: Simpler approach: let $L$ be the linear functional in the corollary. It lies in $V^{**}$ so by the theorem (and definition of isomorphism), there exists a unique $\alpha \in V$ that is mapped to $L$ by the isomorphism.
By the definition of the isomorphism, $L(f)=f(\alpha)$ for any $f \in V^*$. Moreover, uniqueness of this $\alpha$ implies that no other $\alpha' \in V$ can satisfy $L(f) = f(\alpha')$ for all $f \in V^*$ (else the isomorphism would also map $\alpha'$ to $L$, which contradicts injectivity of the isomorphism).


TITLE: How many of the integers between $1$ and $200$ are odd numbers or divisible by $3$ or divisible by $5$?
QUESTION [1 upvotes]: How many of the integers between $1$ and $200$ are odd numbers or divisible by $3$ or divisible by $5$?
\begin{align*}
 A_1 & = \left\lfloor{\frac{200}{3}} \right\rfloor = 66 && \text{(divisible by $3$)}\\
 A_2 & = \left\lfloor{\frac{200}{5}} \right\rfloor = 40 && \text{(divisible by $5$)}\\
 A_3 & = \left\lfloor{\frac{200}{2}} \right\rfloor = 100 && \text{(odd)}\\
| A_1 \cap A_2 | & = \left\lfloor{\frac{200}{3 \cdot 5}}\right\rfloor = 13\\
| A_1 \cap A_3 | & = \left\lfloor{\frac{200}{3 \cdot 2}}\right\rfloor = 33\\
| A_2 \cap A_3 | & = \left\lfloor{\frac{200}{5 \cdot 2}} \right\rfloor= 20\\
| A_1 \cap A_2 \cap A_3 | & = \left\lfloor{\frac{200}{5 \cdot 2 \cdot 3}}\right\rfloor = 6
\end{align*}
Therefore, by the principle exclusion inclusion theorem
 $= 66 + 40 + 100- (13 + 33 + 20) + 6 = 146$
Is this logically right?

REPLY [1 votes]: In this simple case you don't really need the Inclusion/Exclusion principle $-$ you can do it 'by hand'.
First, count the even numbers between $1$ and $30$ that are divisible by $3$ or $5$: these are $6,10,12,18,20,24,$ and $30$. So there are $7$ of them. (Or you could use Inclusion/Exclusion on this part only: $\frac{30}{6}+\frac{30}{10}-\frac{30}{30}=7$.)
Next, note that this pattern repeats exactly every $30$ numbers; so between $1$ and $210$, there are $49$ of them. Subtract $204$ and $210$ to get $47$ between $1$ and $200$.
Now add the odd numbers to get $147$.


TITLE: Hamiltonian paths in bipartite graphs with 2 sets of "almost" same cardinality
QUESTION [1 upvotes]: Suppose we have two finite disjoint sets $A, B \neq \emptyset$ such that $|A|$ and $|B|$ differ by at most $1$, and let $\Gamma = (A\cup B, E)$ where $E\subseteq \big\{\{a,b\}: a\in A, b\in B\big\}$ be a bipartite graph.
If $\Gamma$ is connected and at most $2$ vertices have degree $1$, does $\Gamma$ have a Hamiltonian path?
(It is easy to see that if $|A|, |B|$ differ by more than 1, $\Gamma$ cannot have a Hamiltonian path.)

REPLY [2 votes]: Counterexample. Draw a 4-cycle with vertices A, B, C, D and edges AB, BC, CD, DA; draw another 4-cycle with vertices E, F, G, H and edges EF, FG, GH, HE; draw a third 4-cycle with vertices I, J, K, L and edges IJ, JK, KL, LI. Draw another vertex M and edges AM, EM, IM. Draw another vertex N and edges BN and DN.
This is a connected bipartite graph on 14 vertices with 7 vertices on each side, every vertex has degree 2 or 3, and the longest path has 10 vertices.


TITLE: Are $\mathbb{Q}(\pi)$ and $\mathbb{Q}(\pi^2)$ equal?
QUESTION [0 upvotes]: The question was addressed here but I do not know how jo justify that $f(x)=X^2 - \pi^2$ is irreducible over $\mathbb{Q}(\pi^2)$. That is, $\pi \notin \mathbb{Q}(\pi^2)$. Any help would be appreciated.

REPLY [0 votes]: A bit different approach using valuation theory (fleshing out the incomplete argument given by Bernard).
Since $\pi$ is transcendental over $\bf Q$, $\mathbf Q[\pi]$ has a nontrivial $\pi$-adic valuation, i.e. $v_\pi(\sum_k{a_k}\pi^k)=\min\{k\mid a_k\neq 0\}=\max\{k\mid \pi^k\textrm{ divides }\sum_ka_k\pi^k\}$. This can be extended to a valuation on $\mathbf Q(\pi)$ by setting $v_\pi(\frac{f}{g})=v_\pi(f)-v_\pi(g)$.
Now, $v_\pi(\pi)=1$, and it is easy to see that $v_\pi(f)$ is even for any $f\in \mathbf Q(\pi^2)$, so $\pi\notin \mathbf Q(\pi^2)$.


TITLE: If $G_{\alpha} \cong S_4$ and $|\mbox{fix}(g)| \in \{0,3\}$ for $g \ne 1$. Then $G$ has transitive normal subgroup of index $2$.
QUESTION [0 upvotes]: Let $G$ be a transitive permutation group such that $|\mbox{fix}(g)| \in \{0,3\}$ for every nontrivial $g \in G$. Also suppose $|N_G(G_{\alpha}) : G_{\alpha}| = 1$, i.e. $G_{\alpha}$ is the only fixed point of all elements in $G_{\alpha}$ (by this assumption there exists some $g \in G$ such that $G_{\alpha} \ne G_{\alpha}^g$ and $G_{\alpha} \cap G_{\alpha}^g \ne 1$). Also note that by the assumption $|\mbox{fix}(g)| = 2$ for every nontrivial $g \in G_{\alpha}$.
Also assume $\operatorname{gcd}(|\Omega|, |G_{\alpha}|) \in \{1,3\}$ and $G_{\alpha} \cong S_4$ and that $G_{\alpha}$ has three non-regular orbits on $\Omega \setminus \{\alpha\}$ of size $12, 8$ and $6$. Consider the following argumentation:

Let $S$ be a Sylow $2$-subgroup of $G_{\alpha}$. Then $\alpha$ is the only fixed point of $S$ and therefore we have $N_G(S) \le G_{\alpha}$. This implies $N_G(S) = S$. By Grün's theorem, $G' \cap S = \langle S', S\cap S'^g : g \in G \rangle$. Now $S$ is a dihedral group of order $8$ and, if not all involutions of $S$ are conjugate in $G$, it follows that $G$ has a normal transitive subgroup $H$ of index $2$.

Why does $G$ has a normal transitive subgroup if not all involutions of $S$ are conjugate in $G$?
These are the things I comprehend: By the assumption $\operatorname{gcd}(|\Omega|, |G_{\alpha}|) \in \{1,3\}$ , every Sylow $2$-subgroup of $G_{\alpha}$ is also a Sylow $2$-subgroup of $G$. Also by looking at the orbit decompositions of $S$ on the orbits of $G_{\alpha}$, as they are divisible by $2$, $S$ could not have a single fixed point. So the case that it has two fixed point must be ruled out, again by orbit decomposition they must both lie in one orbit. Suppose it is $\Delta$ and $\alpha_1, \alpha_2$ are the fixed points $\ne \alpha$, then $S_{\alpha_1} \le G_{\alpha} \cap G_{\alpha_1}$ and $|\Delta| = |G_{\alpha} : G_{\alpha}\cap G_{\alpha_1}|$, but as $|G_{\alpha}\cap G_{\alpha_1}| \ge 8$ and $|G_{\alpha}| = 24$ we have $|\Delta| \le 3$, but the orbits are assumed to be larger. So $S$ has just $\alpha$ has its only fixed point. And $N_{G_{\alpha}}(S) = S$ as the number of Sylow $2$-subgroups is $3 = |G_{\alpha} : N_{G_{\alpha}}(S)|$ in $S_4$.
Also that every normal subgroup of index two must be transitive I see too, as the number of orbits is $|G : G_{\alpha}H|$, which is not divisible by $2$ as $G_{\alpha}$ contains a Sylow $2$-subgroup. So $2 = |G : H| = |G : G_{\alpha}H||G_{\alpha}H : H|$ implies $|G : G_{\alpha}H| = 1$.

REPLY [0 votes]: If $S = \{ 1, r, r^2, r^3, s, sr, sr^2, sr^3 \}$ is the dihedral group of order $8$, then for the involutions we have the conjugacy classes
$$
 \{ r^2 \}, \quad \{ s, sr^2 \}, \quad \{ sr, sr^3 \}.
$$
and $S' = \{ 1, r^2 \}$. Now
$$
 \langle r^2, s \rangle = \{ 1, r^2, s, sr^2 \} \cong C_2 \times C_2
$$
and
$$
 \langle r^2, sr \rangle = \{ 1, r^2, sr^3, sr^2 \} \cong C_2 \times C_2.
$$
but $\langle s, sr \rangle = S$. We have $|S \cap S'^g| = 2$ if $S'^g \le S$ and it has trivial intersection otherwise. Now if not all involutions are conjugate in $G$, then we have the following cases:
i) $S'^g = S'$ for all $g \in G$ with $S'^g \le S$. Hence $\langle S', S\cap S'^g \rangle = S'$.
ii) $S'^g \cap \{ s, sr^2 \} \ne \emptyset$ for some $g \in G$. Then
$\langle S', S \cap S'^g \rangle \cong C_2 \times C_2$.
iii) $S'^g \cap \{ sr, sr^3 \} \ne\emptyset$. Similar as ii).
In all cases by Grün's theorem we have $|G' \cap S| \le 4$. Hence as $SG'$ is a subgroup we have $|G : G'| = |G : SG'||SG' : S| = |G : SG'||S : S \cap G'|$ and therefore $|G : G'|$ is divisble by $2$, as it is abelian we can choose some normal subgroup of index $2$ in $G / G'$, its inverse image has index $2$ in $G$ and is normal.
EDIT: Proof that $H$ is transitive. As $\operatorname{gcd}(G_{\alpha}, |\Omega|) \in \{1,3\}$ by assumption and $|\Omega| = |G : G_{\alpha}|$, every Sylow $2$-subgroup of $G_{\alpha}$ is also a Sylow $2$-subgroup of $G$. Now by assumption $S$ is a Sylow $2$-subgroup of $G_{\alpha}$, and by the above also of $G$. Hence $|G : G_{\alpha}H|$ is not divisble by $2$. But as $G_{\alpha}H = G_{\{\Delta\}} = \{ g \in G : \Delta^g = \Delta \}$ for $\alpha \in \Delta$ is the stabilizer of the $H$-orbit $\Delta$, we have $|G : G_{\alpha}H|$ different orbits of $H$. We have $2 = |G : H| = |G : G_{\alpha}H||G_{\alpha}H : H|$, which gives $|G : G_{\alpha}H| = 1$ and hence $H$ is transitive (this by the way gives that every subgroup of index two must be transitive).


TITLE: Is there any analogs of Vassiliev invariants in higher dimensions?
QUESTION [8 upvotes]: http://www.artofproblemsolving.com/Forum/blog.php?u=55354&b=32193
Today I asked my TA for the knot theory class whether there exists any analogs for Vassilev invariants, like at least in $ (2,4) $ case (to me the question is how to define singularities properly?). Also I asked him whether there exists any basic classifications (I guess we still use something like triangular moves). He told me to ask the professor, but the professor is not accessible, so I ask in here. I know the question seemed primitive (definitely not a research type question), I just don't know where I can find the needed reference.
Another question I want to ask is whether there exists any good integral type invariants. I feel it is highly unlikely to find one, but I don't know why. I think one criterion such an integral has to satisfy is it can distinguish small knotted parts in comparison with unknot parts, and it should be able to distinguish images with its mirror images.

REPLY [5 votes]: First, let me recall briefly Vassiliev's theory (the way I understand it). I will skip many important details on the way.
Vassiliev's invariants first appeared as certain cohomology classes of the space of all knots in the 3-space. The strategy is as follows: instead of the space of all knots, which is infinite-dimensional, consider the space $V_d$ of maps from $\mathbf{R}$ to $\mathbf{R}^3$ given by polynomials of some fixed degree $d$ behaving in a prescribed way at infinity. This is a finite dimensional space and non-knots form a hypersurface $\Sigma_d$ in it. Using the Alexander duality one can reduce the computation of the cohomology of the complement of $\Sigma_d$ in $V_d$ to computing the Borel-Moore homology of $\Sigma_d$. [Note: there is a price to pay for replacing an open set with its complement -- we loose the information of how $\Sigma_d$ lies in $V_d$.] The Borel-Moore homology of $\Sigma_d$ can be computed by constructing a suitable semi-simplical resolution of $\Sigma_d$ (i.e. a semi-simplicial space with the geometric realization properly homotopy equivalent to $\Sigma_d$).
The geometric realization of a semi-simplicial space admits a natural filtration, which gives a spectral sequence converging to the Borel-Moore homology of $\Sigma_d$. There is a way to embed $V_d$ into some $V_{d'},d'>d$ so that knots are mapped to knots and unknots to unknots. Moreover, spectral sequences for $d'$  and $d$ are mapped to one another. This corresponds to the restriction map in cohomology, but constructing the maps on the level of spectral sequences is non-trivial. As $d$ goes to $\infty$ a part of the $E^1$ term of the spectral sequence stabilizes. It is a difficult theorem (Kontsevich-Vassiliev) that (at least over the rationals) the second and higher differentials vanish on the stable part and that if an element in the stable part is killed, it is killed in the first sheet by some stable element for all sufficiently large $d$.
So letting $d$ go to $\infty$ we get a vector subspace (in fact, a subring) in the cohomology of the space of all knots (equipped with the Whitney topology), together with a filtration on it. Vassiliev's conjecture says that this subspace is in fact the whole of the cohomology. By taking the $H^0$ part we get Vassiliev invariants and the Vassiliev filtration on them.
The most non-trivial part of the above is the actual construction of the semi-simplicial resolution of $\Sigma_d$ (since this gives a spectral sequence that collapses very fast).
The same strategy can be applied in many other cases, such as spaces of smooth functions without complicated singularities, spaces of mappings from $m$-dimensional CW-complexes to $m-1$ connected ones, spaces of smooth projective hypersurfaces, classical Lie groups etc. It can also be applied to spaces of knots in 3-manifolds other than $\mathbf{R}^3$ and in higher-dimensional manifolds. For $\mathbf{R}^n,n>3$ this gives a complete description of the cohomology: it is isomorphic to the cohomology of the Hochschild complex of the Poisson operad for $n$ odd and of the Gerstenhaber operad for $n$ even, as shown by V. Turchin arXiv:math/0010017. The case $n=3$ is much trickier. Some of these applications can be considered higher dimensional analogs of Vassiliev knot invariants.
Most of the above is described in detail in "Complements of the Discriminants of Smooth Maps" by Vassiliev. A brief synopsis can be found in Vassiliev's ICM 1994 talk.


TITLE: Checking on the injectivity, surjectivity and bijectivity of this function
QUESTION [1 upvotes]: While sitting in a determinant class, our Professor, while describing determinants, coined an observation which made me wonder. He stated that the determinant of a square matrix can be represented as a function in the following way -

Let $M$ be the set of all square matrices, then a function, say X, is defined from $M \to \mathbb{R}$ which returns the determinant of any square matrix $C \in M$ i.e.
  $$ X : M \to \mathbb{R}$$ which returns $|M|$

As soon as he said this, I began to wonder about the injectivity, surjectivity and bijectivity of this function.
 I was told that for a given $C \in M$, there exists only one unique determinant  $|M| \in \mathbb{R}$. But the converse is not true according to me. This can be proved by the following argument -
 Let's say that $$\begin{vmatrix}
x &5 \\
x &x\\
\end{vmatrix} = -6 $$
On solving for $x$, we obtain two values i.e $2$ and $3$, therefore the matrix is not unique for the given determinant i.e. for one image ($-6$), there exist multiple preimages. Hence, according to me, the function so defined is not injective, and consequently not bijective as well.
Now checking for surjectivity, we'll have to look for the equality of the codomain and the range of the function. In my opinion, for infinite square matrices, there will be infinite unique determinants belonging to $\mathbb{R}$. Hence the function should be surjective, but only for real entries into the matrix.
For complex entries, I don't think the function remains surjective, as the range will not coincide with the codomain (i.e. $\mathbb{R}$). However, in both cases, I feel that the function is neither injective not bijective.
I would like to know if I am right or not by knowing the views of the math-geeks sitting out there. Thanks!

REPLY [0 votes]: Surjectivity follows from considering the matrix
$$
\begin{bmatrix}
a & 0 & 0 & \dots & 0 & 0 \\
0 & 1 & 0 & \dots & 0 & 0 \\
0 & 0 & 1 & \dots & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \dots & 1 & 0 \\
0 & 0 & 0 & \dots & 0 & 1
\end{bmatrix}
$$
that is, the identity with just the top left entry changed to $a$ instead of $1$. This has determinant $a$ by multilinearity.
Injectivity can be shown false by considering the identity with the bottom right entry changed into $a$, which has determinant $a$ as well. If your matrices are not $1\times 1$, this falsifies injectivity.
However, the determinant is indeed injective on $1\times1$ matrices, because it's essentially the identity map.


TITLE: Why is the following not true: $(\vec{u} \times \vec{v}) \times \vec{u} = \vec{v}$
QUESTION [2 upvotes]: I don't believe the following is true.
$(\vec u \times \vec v) \times \vec u = \vec{v}$
I'd like to know why it isn't true, in better terms than "v is probably not perpendicular to u" and what the product actually is.

REPLY [2 votes]: I think the easiest way to see that it's not true is to say that $v = u$. Then $v \times u \times v = v \times v \times v  = 0 \not = v$
That's a pretty serious problem, and more than a heuristic as to why it's not true.


TITLE: Computational Complexity of Finding Adjacent Terms in Farey Sequence
QUESTION [3 upvotes]: The Farey sequence $\mathcal{F}_n$ is the list of all fractions in increasing order (in lowest terms) from $0$ to $1$, having denominator at most $n$. My question is, given some $a/b\in\mathcal{F}_n$ for known $n$, what is the most efficient method to find the fractions in $\mathcal{F}_n$ that are adjacent to $a/b$?
Here is one method. Suppose $\frac{a_0}{b_0}<\frac{a}{b}<\frac{a_1}{b_1}$ are consecutive terms of $\mathcal{F}_n$ for a known $n$. We want to find $a_0/b_0$ and $a_1/b_1$. By definition of $\mathcal{F}_n$, we want to minimize the differences $\frac{a}{b}-\frac{a_0}{b_0}$ and $\frac{a_1}{b_1}-\frac{a}{b}$. There is a well known property of Farey sequences that states if $a/b < a'/b'$ are adjacent terms in $\mathcal{F}_n$, then $\frac{a'}{b'}-\frac{a}{b}=\frac{1}{bb'}$. Then, the differences can be written as $$\frac{a}{b}-\frac{a_0}{b_0}=\frac{ab_0-a_0b}{bb_0}=\frac{1}{bb_0}, \frac{a_1}{b_1}-\frac{a}{b}=\frac{a_1b-ab_1}{b_1b}=\frac{1}{b_1b}.$$ Thus, $ab_0-a_0b=1$ and $a_1b-ab_1=1$. Since $\gcd(a,b)=1$ we can find $(a_0,b_0)$ and $(a_1, b_1)$ due to Bézout's Identity and the extended Euclidean algorithm.
Alternately, we could have drawn a tree diagram of sorts and used bounding arguments to arrive at the solutions.
Are there any other (maybe more efficient?) methods of finding $(a_0, b_0)$ and $(a_1,b_1)$? How can we find the computational complexities of such methods? Is there a method known to be most efficient? Any ideas are appreciated.

REPLY [1 votes]: Here is a slow way of computing the neighbors of $a/b$.
For any $m$ we can ask look at the fractions $0 \leq \frac{1}{m} \leq \frac{2}{m} \leq \dots \leq \frac{m-1}{m} \leq 1$ and ask where $\frac{a}{b}$ fits in here.
We wish to minimize $\frac{a}{b} - \frac{k}{m} = \frac{am-bk}{bm} $
This is just an application of the Euclidean algorithm.
For some $0 \leq r < b$, $am = k b + r $.  For a computer k = am/b where we use integer division.

Using the Euclidean algorithm we can speed of the process of long division.  We will get some expansion
$ \frac{a}{b} = \cfrac{1}{c_1 + \cfrac{1}{c_2 + \dots } } = [c_1, c_2, \dots ]$
The digits are $b_0=1, b_1 = c_1, b_2 =  c_2c_1 + 1, b_3 = c_3b_2 + b_1,\dots $
The algorithmic efficiency of the Euclidean algorithm is discussed on Wikipedia.  The number $T(a,b)$ of steps on the Euclidean algorithm for $a/b$ is very chaotic.
For two random $m$-bit numbers $0 < a,b < 2^m$, the number of steps is proportional to $m$.


TITLE: Pigeon-hole principle applied to the game of tic tac toe
QUESTION [0 upvotes]: In a game of tic tac toe, noughts and crosses are drawn inside an unoccupied cell of a 3 x 3 matrix by two players I, II in alternating moves. Player I draws crosses and Player II draws noughts. The game is won by the first player who draws a row or a column with the same symbol. If a game is not won by any player, which of the following statements are true and which are false.
(a) There is a column with at least 2 noughts
(b) there are 2 rows each with 2 noughts
(c) there are 2 rows and 2 columns with 2 crosses in each of these rows and columns
(d) there is on diagonal with at least 2 crosses.
How I am suppose to apply the pigeon-hole principle to this question. I understand that (a) is True but i do not understand why (b) to (d) are False.
Appreciate any help.
Thanks in advance.

REPLY [0 votes]: d. Not necessarily True or False.
Example where it's False:
(X O X)
(X O X)
(O X O)
Example where it's True:
(X X O)
(O O X)
(X O X)