text:
\begin{document}

\maketitle

\begin{abstract}
We show that for any cardinal $\omega<\kappa \leq \mathfrak{c}$ with $cf(\kappa) > \omega$, there are $\mathfrak{c}$ many AD families whose $\Psi$-spaces are pairwise non-homeomorphic and they can be Luzin families or branch families of $2^\omega$.
\end{abstract}

\section{Introduction}
Denote by $\fin$ the set of finite sets of the natural numbers,  $\omega$. If $\ada$ is an almost disjoint family (AD family, for short) on $\omega$, define the topological space $\Psi (\ada) = (\omega \cup \ada,  \tau)$ as follows: $\omega$ is a discrete subset of $\Psi (\ada)$; basic neighborhoods of a point $x\in \ada$ are of the form $\{ x\} \cup (x\setminus F)$, where $F \in \fin$.

$\Psi$-spaces have been well studied through the years because they are candidates to give examples or counterexamples of many topological concepts. There are nice properties $\Psi$-spaces satisfy: they are Hausdorff, separable, first countable, locally compact, zero dimensional. For topological and combinatorial aspects of $\Psi$-spaces see \cite{FM} and \cite{M}, respectively.

Daniel Bernal-Santos and Salvador García-Ferreira wondered if $C_p (\Psi (\ada))$ and $C_p (\Psi (\adb))$ are homeomorphic whenever $\ada$ and $\adb$ are homeomorphic as subspaces of $\cantor$. To understand better the space $C_p (\Psi (\ada))$ they wondered for a more elementary question:

\begin{pregunta}[Bernal-Santos, García-Ferreira] \label{Q1}
If $X, Y \subseteq \cantor$ are homeomorphic, are $\Psi (\ada_X)$ and $\Psi (\ada_Y)$ homeomorphic?
\end{pregunta}

Here, $\ada_X$ is the family of branches determined by $X$ as a subspace of $\cantor$.   It is well known that under $\mathsf{MA +\neg CH}$, every set $X\in \cantor$ of size less than the continuum is a $Q$-set, and thus, $\Psi (\ada_X)$ normal (call a family $\ada$ {\it normal} if its $\Psi$-space is normal). Like this, there are many topological properties of $X\subseteq\cantor$ that have effect on the $Psi$-space $\Psi (\ada_X)$. One might think that $\mathsf{MA +\neg CH}$ is a good ingredient to conjecture that the answer is affirmative. However, we answer negatively to Question \ref{Q1} since Theorem \ref{T2} shows that in $\mathsf{ZFC}$ there are different types of spaces $\Psi (\ada_X), \Psi (\ada_Y)$ even when $X$ and $Y$ are homeomorphic.

Recall that an AD family $\ada$ is \tits{Luzin} if it can be enumerated as
$$
\ada = \langle A_\alpha : \alpha < \omega_1 \rangle
$$
in such way that $\forall \alpha < \omega_1 \forall n\in \omega \; \; (|\{ \beta < \alpha : A_\alpha \cap A_\beta \subseteq n  \}|< \omega)$. Normal and Luzin families are in some sense ``orthogonal", precisely because the normality of their $\Psi$-spaces holds in the former and breaks down badly in the last. We show in Theorem \ref{T1} that in $\mathsf{ZFC}$ there are different types of $\Psi$-spaces for Luzin families.

Focusing on AD families of size $\omega_1$, Michael Hru\v{s}\'ak formulated the following question:

\begin{pregunta}[Hru\v{s}\'ak] \label{Q2}

Is consistent that there is an almost disjoint family $\ada$  such that $\Psi (\ada) \simeq \Psi (\adb)$, whenever $\adb\subseteq\ada$ and $\vert\ada\vert=\vert\adb\vert$\,?
\end{pregunta}

Observe that $2^\omega < 2^{\omega_1}$ (in particular $\mathsf{CH}$), implies that the answer to Question \ref{Q2} is negative by the simple fact that given $\ada$ of size $\omega_1$, there are only $\mathfrak{c}$ many subspaces $\Psi(\adb)$ for which $\Psi(\ada) \simeq \Psi(\adb)$ (there are only $\mathfrak{c}$ permutations of $\omega$), and there are $2^{\omega_1}$ many subsets of $\ada$ of size $\omega_1$. We believe that it is a very interesting question; we conjecture that the answer is no but our methods do not work to solve it.

\section{Basic facts}

Our notation is standard and follows closely \cite{FM} and \cite{M}. We use, like them, $f(A)$ to denote the evaluation of the function $f$ at the point $A$ in its domain while $f[A]$ denotes the image of the set $A$ under the function $f$. For sets $A$ and $B$, we say that $A\subseteq^* B$, in words that  $A$ is almost contained in $B$, if $A\setminus B$ is a finite set.  Likewise, $A=^*B$ if and only if $A\subseteq^* B$ and $B\subseteq^* A$. If $X \subseteq \cantor$, $x\in \cantor$, we denote
\[
\gorro{x\downarrow n} = \{ x\rest k \in \dosfin: n\leq k \}, \;
\]
$\gorro{x} :=  \gorro{x\downarrow 0}, \; \gorro{X} = \bigcup_{x\in X} \gorro{x}$ and $\mathcal{A}_X = \{ \gorro{x} : x\in X \}$. Families of the form $\ada_X$, where $X\subseteq \cantor$, are canonical AD families on $\dosfin$, and there are of any size below the continuum. Under a correspondence between $\omega$ and $\dosfin$ we can consider $\Psi(\ada_X)$. Perhaps the families $\ada_X$ were first studied by F. Tall \cite{T} when he showed that if $X\subseteq  \cantor$, then $X$ is a $Q$-set if and only if $\Psi (\ada_X)$ is normal.

   The following Lemma shows how a homeomorphism between $\Psi$-spaces looks like.

\begin{lema}\label{L0}
Let $\ital{A}, \ital{B}$ almost disjoint families on $\omega$, and $H: \Psi (\mathcal{A}) \to \Psi (\mathcal{B})$ be bijective. Then $H$ is a homeomorphism if and only if $H[\omega] = \omega$ and for every $x\in \mathcal{A}$, $H[x]$ and $H(x)$ as subsets $\omega$ are almost equal.
\end{lema}

\begin{proof}
$\Rightarrow )$ Since $H$ must send isolated points to isolated points, it is clear that $H[\omega] = \omega$. Now, let $x\in \mathcal{A}$ and $\{ H(x)\} \cup (H(x) \setminus F)$ be a neighborhood of $H(x)$, where $F\in \fin$. By continuity, there is $F'\in \fin$ such that $H(x) \cup H[x\setminus F'] = H[\{ x\} \cup (x\setminus F')]  \subseteq \{ H(x)\} \cup (H(x) \setminus F)$. So, $H[x] \setminus F'=H[x\setminus F'] \subseteq H(x) \setminus F$. Use the fact that $H$ is open and similar arguments to get $H[x] \supseteq^* H(x)$.
\\ \\
$\Leftarrow )$ We will see that $H$ is continuous; to see that $H$ is open use similar arguments. Let $x\in \mathcal{A}$ and $\{ H(x) \} \cup (H(x) \setminus F )$ be a neighborhood of $H(x)$, where $F\in \fin$. Since $H[x] =^* H(x)$, there is $F' \in \fin$ such that $H[x\setminus F'] =H[x]\setminus F' \subseteq H(x)\setminus F$. So, $H[\{ x\} \cup (x\setminus F')] \subseteq \{ H(x) \} \cup (H(x) \setminus F)$.
\end{proof}

For $s\in \dosfin$, let $\langle s \rangle = \{ t\in \dosfin : s \subseteq t \}$ and $[\langle s \rangle ] = \{ x\in \cantor : s \subseteq x \}$.

\begin{lema}
Let $X\subseteq \cantor$ be a set of size $\kappa$, $cf(\kappa) > \omega$. Then there are infinitely many $n\in \omega$ for which there are $s, t\in 2^n$ such that $|[\langle s \rangle] \cap X| = \kappa = |[\langle t \rangle ] \cap X|$.
\end{lema}

\begin{proof}
Suppose for a contradiction that for every $ n\in \omega$ there is a unique $s_n\in 2^n$ such that $X_n =[\langle s_n \rangle] \cap X$ has size $\kappa$. Let $Y_n = X \setminus X_n$. Notice that $|Y_n|< \kappa$, and since $cf(\kappa) > \omega$, $Y = \bigcup_{n\in \omega} Y_n$ has size less than $\kappa$. This is a contradiction because $ X \setminus Y = \bigcap_{n\in \omega} X_n \subseteq  \bigcap_{n\in \omega} [\langle s_n \rangle]$ has size $\kappa$ and it contains at most one point.
\end{proof}

In the following, we are going to consider AD families of a fixed size $\kappa \leq \mathfrak{c}$, with $cf(\kappa) > \omega$.

Notice that by the previous Lemma, one can actually get infinitely many $n\in \omega$ for which there is $s\in 2^n$ such that $|[\langle s^\frown 0 \rangle] \cap X| = \kappa = |[\langle s^\frown 1 \rangle ] \cap X|$. For an AD family $\ada$ on $\omega$, we obtain the next observation by considering $\{ \chi (A) : A \in \ada \} \subseteq \cantor$, where $\chi$ is the characteristic function.

\begin{obs}\label{L1}
Let $\mathcal{A}$ be an $AD$ family of size $\kappa$ with $cf(\kappa)>\omega$. Then $$\forall n\in \omega\ \exists m > n (|\{ x \in \ada : m \in x  \}|=|\{ x \in \ada : m \notin x  \}| = \kappa).$$
\end{obs}

\begin{lema}\label{L2}
Let $\ada, \adb$ be $AD$ families of size $\kappa$ with $cf(\kappa)>\omega$ and $h : \ada \to \adb$ be a bijection. Then for all $n\in \omega$ there are $x,y,z \in \ada$ such that
\begin{enumerate}
\item $max\{x\cap y\} > n \ \wedge\ x\cap y \subsetneq x\cap z;$ and
\item $max\{h(x)\cap h(y)\} > n \ \wedge\  h(x)\cap h(y) \subsetneq h(x)\cap h(z).$
\end{enumerate}
\end{lema}

\begin{proof}
Fix $n\in \omega$. By Remark \ref{L1}, choose $m>n$ large enough and $\ada' \in [\ada]^{\kappa}$ such that for every $x\in \ada'$, $m\in x$ and $m \in h(x)$. Now, fix $y\in \ada'$ and consider $\{ x\cap y : x \in \ada' \wedge x\neq y\}$. There are $F\in \fin$ and $\ada'' \in [\ada']^{\kappa}$ such that for all $x\in \ada''$, $x\cap y = F$. There are also $G \in \fin$ and $\adb ' \in [h[\ada'']]^{\kappa}$ such that for all $w\in \adb'$, $w\cap h(y) = G$. Let $\ada''' = h^{-1}[\adb']$.

For any $x,z \in \ada'''$, we have $x\cap y = z \cap y$ and $h(x)\cap h(y) = h(z) \cap h(y)$. This implies that $x\cap y \subseteq x\cap z$ and $h(x)\cap h(y) \subseteq h(x) \cap h(z)$. Observe that it is possible to find $x,z$ such that the contentions are proper.
\end{proof}

\begin{de}
Let $\ada, \adb$ be AD families on $\omega$ of size $\kappa$, $h: \ada \to \adb$ bijective. We say that $h$ is of \tits{dense oscillation} if for each $\ada' \in [\ada]^\kappa$ there are $ x, y, z\in \ada'$ such that $|x\cap z \setminus x\cap y| \neq |h(x)\cap h(z)\setminus h(x)\cap h(y)|$.
\end{de}

\begin{prop}\label{P1}
Let $\ada, \adb$ be AD families of size $\kappa$ with $cf(\kappa)>\omega$ and $h: \ada \to \adb$ be of dense oscillation. Then, there is no homeomorphism from $\Psi (\ada)$ to $\Psi (\adb)$ that extends $h$.
\end{prop}

\begin{proof}
Suppose for a contradiction that $H: \Psi (\ada) \to \Psi (\adb)$ is a homeomorphism extending $h$. By Lemma \ref{L0}, for every $A\in \ada$, $H[A]=^* H(A)$. So, for $A\in \ada$, consider the finite sets $F_A = \{ n \in A : H(n) \notin H(A) \}$ and $G_A = \{ n\in H(A) : H^{-1}(n) \notin A \}$.

There are $\ada' \in [\ada]^{\kappa}$ and $F,G \in \fin$ such that for all $A\in \ada'$, $F= F_A$ and $G=G_A$.  If $x, y, z \in \ada'$, then $(x\cap z \setminus x\cap y) \cap F = \emptyset $ and
\[
\Big(\left( H(x)\cap H(z) \right)\setminus \left(H(x)\cap H(y)\right)\Big) \cap G = \emptyset.
\]
Moreover, $m \in x \setminus F$ implies $H(m) \in H(x)$ and $H(m) \in H(x) \setminus G$ implies $H^{-1}(m) \in x$.  From this, one can deduce that $$|x\cap z \setminus x\cap y| = |H(x)\cap H(z)\setminus H(x)\cap H(y)|,$$ contradicting the dense oscillation property of $H\rest \ada = h$.
\end{proof}

\begin{de}
Let $A, B \subseteq \omega$.
\begin{itemize}
\item $A$ and $B$ are \tits{oscillating} if
\[
\forall \{ x, y \} \subseteq A\ \forall \{ w, z \} \subseteq B \ (|y-x| \neq |z-w|).
\]

\item $A$ and $B$ are \tits{almost oscillating} if there is $n \in \omega$ such that $  A\setminus n$ and $ B \setminus n$ are oscillating.
\end{itemize}
\end{de}

\begin{prop}\label{P2}
There are $\mathfrak{c}$ many infinite subsets of $\omega$ pairwise almost oscillating.
\end{prop}

\begin{proof}
From $\omega$, we construct first two oscillating sets $A=\bigcup A_n, B= \bigcup B_n$. Fix $A_0 = \{ 0\}, B_0 =\{ 1\}$. Suppose constructed $A_n=\{ a_0, \ldots, a_n\}, B_n=\{ b_0, \ldots, b_n\}$ oscillating. Let $a_{n+1}\in \omega$ such that $a_{n+1} - a_n > b_n - b_0$ and $b_{n+1}\in \omega$ such that $b_{n+1} - b_n > a_{n+1} - a_0$. Observe that $A_{n+1} = A_n \cup \{ a_{n+1} \}, B_{n+1} = B_n \cup \{ b_{n+1} \}$ are oscillating as well as will be $A$ and $B$.

Notice that the construction is hereditary. That is, for any $X\in [\omega]^\omega$, there are $A,B \in [X]^\omega$ oscillating. This allows to define a Cantor tree induced by this partitions. Each branch of the Cantor set, $f\in2^\omega$, represents a decreasing sequence of infinite sets of naturals $\langle A_{f\rtt n} : n\in \omega \rangle$ such that for any other branch $g\in2^\omega$, we have that $A_{f\rtt k}, A_{g\rtt l}$ are oscillating whenever  $k,l > \Delta (f,g)$. Now, for every branch $\langle A_{f\rtt n} : n\in \omega \rangle$ consider a pseudointersection $P_f$ of $\{ A_{f\rtt n} : n\in \omega \}$. Observe that for any two branches $\langle A_{f\rtt n} : n\in \omega \rangle$, $\langle A_{g\rtt n} : n\in \omega \rangle$, their pseudointersections $P_{f}$, $P_{g}$ are almost oscillating.
\end{proof}

\begin{coro}\label{C1}
Let $\ada, \adb$ be AD families and $h: \ada \to \adb$ a bijection. If $A=\{ |x\cap y| : x,y \in \ada \}$ and $B=\{ |x\cap y| : x,y \in \adb \}$ are almost oscillating, there is $\ada' \in [\ada]^{\kappa}$ such that $h \rest \ada'$ is of dense oscillation.
\end{coro}

\begin{proof}
Let $n \in \omega$ such that $A\setminus n$ and $B \setminus n$ are oscillating. By iterating finitely many steps of Remark \ref{L1}, we can get $\ada' \in [\ada]^{\kappa}$ and  $F, G\in \fin$, with $|F|, |G| > n$, such that for every $x \in \ada'$, $F \subseteq x$ and $G \subseteq h(x)$. If $\ada'' \in [\ada']^\kappa$, apply Lemma \ref{L2} to $h\rest_{\ada''} : \ada'' \to h[\ada'']$ and get $x,y,z \in \ada''$ such that $x\cap y \subseteq x \cap z$ and $h(x)\cap h(y) \subseteq h(x) \cap h(z)$. Thus, there are $a_0,a_1 \in A\setminus n$ and $ b_0, b_1 \in B \setminus n$ such that $|x\cap z \setminus x\cap y| = a_0 -a_1  \neq b_0 -b_1 = |h(x)\cap h(z)\setminus h(x)\cap h(y)|.$
\end{proof}

\begin{coro}\label{C2}
Let $\ada, \adb$ be AD families and $h: \ada \to \adb$ a bijection. If $\{ |x\cap y| : x,y \in \ada \}$ and $\{ |x\cap y| : x,y \in \adb \}$ are almost oscillating, there is no homeomorphism from $\Psi (\ada)$ to $\Psi (\adb)$ that extends $h$.
\end{coro}

\begin{proof}
If $H:\Psi (\ada) \to \Psi (\adb)$ is such homeomorphism, by Corollary \ref{C1} there is $\ada' \in [\ada]^{\kappa}$ such that $H\rest_{\ada'} : \ada' \to H[\ada']$ is of dense oscillation. If $W = \bigcup_{A \in \ada'} A$, then $Z= \ada' \cup W$ is a subspace of $\Psi (\ada)$ and $H\rest_Z$ is a homeomorphism contradicting Proposition \ref{P1}.
\end{proof}

\section{$\mathfrak{c}$ many types of $\Psi$-spaces}

Next we construct $\mathfrak{c}$ many AD families whose $\Psi$-spaces are pairwise non-homeo\-mor\-phic for each of the classes of Luzin families and branch families of $\cantor$.

\begin{theorem}\label{T1}
There are $\mathfrak{c}$ different Luzin families with non-homeomorphic $\Psi$-spaces.
\end{theorem}

\begin{proof}
Given $L = \{ k_n : n\in \omega  \} \subseteq \omega$ such that $k_n > \sum_{i < n} k_i$, construct a Luzin family $\ada_L$ as follow: Choose a partition $\{A_n : n\in \omega \}$ of $\omega$ into infinite sets. Suppose constructed $A_\beta$, $\beta < \alpha$. Enumerate $\{A_\beta : \beta < \alpha \}$ as $\{ B_n : n\in \omega \}$  and for each $n \in \omega$, pick $a_n \subseteq B_n \setminus \bigcup_{i < n} B_i$ such that $|(\bigcup_{i \leq n} a_i ) \cap B_n| = k_n$. Let $A_\alpha = \bigcup_{n\in \omega} a_n$ and $\ada_L=\{A_\alpha:\alpha<\omega_1\}$. Observe that for any $\omega < \alpha, \beta < \omega_1$, there is $n\in \omega$ with  $|A_\alpha \cap A_\beta| = k_n$. It is easy to see that $\ada_A = \{ A_\alpha : \omega < \alpha < \omega_1 \}$ is a Luzin family. Construct all the Luzin families below from the same partition $\{A_n : n\in \omega \}$.

Now, by Proposition \ref{P2}, let $\{ P_\alpha : \alpha < \mathfrak{c} \}$ be a pairwise almost oscillating family of sets of $\omega$. For every $\alpha < \mathfrak{c}$, let $Q_\alpha = \{ q_n^\alpha : n\in \omega \} \subseteq P_\alpha$ such that for every $n\in \omega$, $q_n ^\alpha > \sum_{i<n} q_i^\alpha$. Notice that $\{Q_\alpha : \alpha < \mathfrak{c} \}$ is also a pairwise almost oscillating family of sets of $\omega$. By Corollary \ref{C2}, $\{ \ada_{Q_\alpha} : \alpha < \mathfrak{c}\}$ is the desire collection of Luzin families.
\end{proof}

\begin{theorem}\label{T2}
Given a cardinal $\kappa \leq \mathfrak{c}$ of uncountable cofinality, there are $\mathfrak{c}$ different homeomorphic subsets of $\cantor$ of size $\kappa$ with non-homeomorphic $\Psi$-spaces.
\end{theorem}
\begin{proof}
Given $A \in [\omega]^\omega$, consider the tree $S_A \subseteq \dosfin$ defined by $\emptyset \in S_A$ and
$$  s\in Lev_n (S_A) \implies (s^\frown 1 \in S_A) \wedge (s^\frown 0 \in S_A \longleftrightarrow n \in A).$$

Let $X$ be any subset of size $\kappa$ of the set of branches $[S_A] \subseteq \cantor$. Notice that for all $x,y\in X$, $\Delta (x,y) = |\gorro{x}\cap \gorro{y}| \in A$.

Again, by Proposition \ref{P2}, let $\{ P_\alpha : \alpha < \mathfrak{c} \}$ be a pairwise almost oscillating family of sets of $\omega$. Note that if $A, B  \in [\omega]^\omega$, then $[S_A] \simeq [S_B] \simeq\cantor$ and $A \cap B =^* \emptyset$ implies that $|[S_A] \cap [S_B]| < \omega$. Hence, we can choose $X_\alpha \in [[S_{P_\alpha}]]^{\kappa}$ such that the $X_\alpha$'s are all different, but $X_\alpha \simeq X_\beta$, whenever $\alpha, \beta < \mathfrak{c}$. By Corollary \ref{C2}, $\{ X_{\alpha} : \alpha < \mathfrak{c}\}$ is the desire collection of subsets of $\cantor$.
\end{proof}

\begin{coro}\label{C3}
Let $\ada$ be an AD family of size $\kappa$. If there are $\ada_0, \ada_1 \in [\ada]^{\kappa}$ such that $\{ |x\cap y| : x,y \in \ada_0 \}$ and $\{ |x\cap y| : x,y \in \ada_1 \}$ are almost oscillating, then $\Psi (\ada) \not\simeq \Psi (\ada_0)$.
\end{coro}

\begin{proof}
If $h : \ada_0 \to \ada$ is a bijection, by Corollary \ref{P1} there is $\ada_0' \in [h^{-1}[\ada_1]]^{\kappa}$ such that $h\rest_{\ada_0'} : \ada_0' \to h[\ada_0']$ is of dense oscillation. Hence, there can not be a homeomorphism between $\Psi (\ada_0 ')$ and $\Psi (h[\ada_0'])$ that extends $h\rest_{\ada_0'}$, then neither one between $\Psi (\ada_0)$ and $\Psi (\ada)$ that extends $h$.
\end{proof}

Motivated by Corollary \ref{C3}, a positive answer to the following question implies a positive answer to Question \ref{Q2}. However, we do not even know if $\mathsf{CH}$ answers:

\begin{pregunta}\label{Q3}
Let $\ada$ be an AD family on $\omega$ of size $\omega_1$. Are there $\ada_0, \ada_1 \in [\ada]^{\omega_1}$ such that $\{ |x\cap y| : x,y \in \ada_0 \}$ and $\{ |x\cap y| : x,y \in \ada_1 \}$ are almost oscillating?
\end{pregunta}

The arguments under $\mathsf{CH}$ below Question \ref{Q2} say that if $\ada$ is an uncountable AD family, then there is $\ada_0$ such that $\Psi (\ada) \not\simeq \Psi (\ada_0)$. However, the sets $\{ |x\cap y| : x,y \in \ada_0 \}$ and $\{ |x\cap y| : x,y \in \ada \}$ are far from being almost oscillating (the first is contained in the second).


TITLE: Fixed-Point Free Involutions
QUESTION [0 upvotes]: I am looking to solve this problem:
A permutation $\alpha$ on the set $\{1, 2, . . . , n\}$ is an involution if $\alpha^2 (i)=i$ for all $i = 1,2,\ldots,n$. An element is a fixed point of $\alpha$ if $α(i)=i$. Use exponential generating function to find the number of fixed-point-free involutions on the set $\{1,2,\ldots,2m\}$.

Firstly, I am a bit confused as to the definition of an involution. I see online that an involution is a permutation that is it's own inverse, but I am not quite clear on what that means exactly. I saw somewhere that, for example, "the four involution permutations on $3$ elements are $\{1,2,3\}$, $\{1,3,2\}$, $\{2,1,3\}$, and $\{3,2,1\}$." Is there a reason that $\{2,3,1\}$ and $\{3,1,2\}$ are excluded from this list?
Any guidance on the definition of an involution as well as how to solve this problem would be appreciated.

REPLY [2 votes]: An involution is a permutation that is its own inverse, but that can be a bit hard to parse at first. Let's see a concrete example:
The map $x \mapsto -x$ from $\mathbb{Z} \to \mathbb{Z}$ is an involution. Intuitively why? Because we flip $\mathbb{Z}$ across $0$. Formally why? Because if we apply this transformation twice, we have $-(-x) = x$, and we've gotten back where we started. This is the defining characteristic of an involution: we can flip once, but if we flip again we get back where we started.
(As a quick exercise: consider the $8$ symmetries of a square. Which ones are involutions? The answer is below the fold.)

 We want the symmetries of a square that, if we do them twice, we get back where we started. There are $4$ obvious "flips" -- flip vertically, flip horizontally, and flip across either of the two diagonals. There's also the bonus involution "rotate $180^\circ$". The identity is an involution for kind of silly reasons, so we're up to $6$ involutions. The remaining two symmetries are a $90^\circ$ rotation clockwise or counterclockwise, and neither of these are involutions since if you do them twice you don't get back where you started.

Every involution pairs up an element with somebody else, just look to see who you get flipped to. So the $x \mapsto -x$ involution from earlier pairs $1$ with $-1$, $2$ with $-2$, etc... Except there's a special point: $0$ gets paired with itself! We say that $0$ is a fixed point of the involution, and these are very special. Fixed points hold the answer to lots of counting problems, but I digress.
In this problem, we want to count the number of involutions where everybody gets a friend. That is, we want our involution to have no fixed points.
(As another quick exercise, can you come up with a fixed point-free involution on $\mathbb{Z}$? Again, I'll include one under the fold)

 There are lots of options, but $x \mapsto \begin{cases} x+1 & x \text{ is even} \\ x-1 & x \text{ is odd} \end{cases}$ works. Notice $0$ gets paired with $1$, $2$ gets paired with $3$, etc. Can you formally show that this really is an involution?

Now, it should be clear that a fixed point free involution (on a finite set) can only exist if we're permuting an even number of things. After all, if everyone has a friend, then we have $2m$ many elements where $m$ is the number of pairs. For your example of involutions on a $3$ element set, notice we can:

swap $1$ and $2$ (leaving $3$ fixed)
swap $1$ and $3$ (leaving $2$ fixed)
swap $2$ and $3$ (leaving $1$ fixed)
don't swap anyone (leaving $1$, $2$, and $3$ fixed)

At this point, can you answer your own question about why the remaining two permutations are not involutions?

Ok, on to the main point of your question. How can we count the number of fixed point free involutions on the set $[2m] = \{1,2,3,\ldots,2m-1, 2m\}$? It's hard to know precisely how to answer this without knowing what aspects of exponential generating functions you've seen. But here's one approach which is hinting at the idea of species. I'm going to be somewhat quick with my description (this answer is already quite long), but you can read more in these excellent notes.
We know that an involution without fixed points divides a set into pairs. Conversely, if we divide a set into pairs, then we get a unique involution by swapping the two paired elements.
So we want to partition $2m$ into blocks of size $2$. In terms of "structure" (again, see the linked notes), this means we want to

divide $\{1, 2, 3, \ldots, 2m-1, 2m\}$ into blocks
each block should have structure "I have $2$ elements"
the set of blocks should have no structure

But this nested notion of putting structure on blocks, each of which has structure is exactly where exponential generating functions show their full power! This maneuver corresponds to the composition of generating functions!
In particular, "I have $2$ elements" is expressed by the exponential generating function $\frac{x^2}{2!}$ (do you see why?). Then "I have no structure" is expressed by $e^x$ (again, do you see why?)
So now, by the composition theorem for exponential generating functions, we see the number of ways to divide $m$ objects into blocks of size $2$ is the composite of the above functions. That is, $e^{\frac{x^2}{2}}$. Indeed, we can check that
$$e^{\frac{x^2}{2}} = 1 + \frac{x^2}{2!} + 3 \frac{x^4}{4!} + 15 \frac{x^6}{6!} + 105 \frac{x^8}{8!} + \ldots$$
which matches what we expect for small values of $m$.

I hope this helps ^_^


text:
\subsection{Locally Computed Gradient}
Consider the link $l\sim (i,j)$, since $w_l=w_{ij}=w_{ji}$ and $w_{ii}=1-\sum_{s\in N_i}w_{is}$, we have:
\begin{equation}\label{diff}
\frac{\text{d}w_{st}}{\text{d}w_l}=
\begin{cases}
+1 &\text{if } s=i \text{ and } t=j\\
+1 &\text{if } s=j \text{ and } t=i\\
-1 &\text{if } s=i \text{ and } t=i\\
-1 &\text{if } s=j \text{ and } t=j\\
0 &\text{else.}
\end{cases}
\end{equation}
 The gradient $g_l$ of the function $h(\mathbf{w})$ for $l\sim (i,j)$ can be calculated as follows:
\begin{align}
g_l&=\frac{\text{d}\hfill h(\mathbf{w})}{\text{d}w_l}\nonumber \\
&=\frac{\text{d}\hfill f(W)|_{W=I-\mathcal{I}\times \text {diag}(\mathbf{w})\times \mathcal{I}^T}}{\text{d}w_l}\nonumber \\
&=\sum_{s,t}\frac{\partial f}{\partial w_{st}}\frac{\text{d}w_{st}}{\text{d}w_l}\nonumber \\
&=\frac{\partial f}{\partial w_{ij}}\frac{\text{d}w_{ij}}{\text{d}w_l}+\frac{\partial f}{\partial w_{ji}}\frac{\text{d}w_{ji}}{\text{d}w_l}+\frac{\partial f}{\partial w_{ii}}\frac{\text{d}w_{ii}}{\text{d}w_l}+\frac{\partial f}{\partial w_{jj}}\frac{\text{d}w_{jj}}{\text{d}w_l}\nonumber\\
&=\frac{\partial f}{\partial w_{ij}}+\frac{\partial f}{\partial w_{ji}}-\frac{\partial f}{\partial w_{ii}}-\frac{\partial f}{\partial w_{jj}}\nonumber\\
&=p\big ((W^{p-1})_{ji}+(W^{p-1})_{ij}-(W^{p-1})_{ii}-(W^{p-1})_{jj}\big ).\label{line4}
\end{align}
In the last equality we used equation \eqref{derivativef}.

It is well know from graph theory that if we consider $W$ to be the adjacency matrix of a weighted graph $G$, then $(W^s)_{ij}$ is a function of the weights on the edges of the $i-j$ walks (i.e.~the walks from $i$ to $j$) of length exactly $s$ (in particular if the graph is unweighted $(W^s)_{ij}$ is the number of distinct $i-j$ $s$-walks \cite{West2000}).  Since for a given $p$ the gradient $g_l$, $l\sim (i,j)$, depends on the $\{ii, jj, ij, ji\}$ terms  of the matrix $W^{p-1}$,  $g_l$ can be calculated locally by using only the weights of links and nodes at most $\frac{p}{2}$ hops away from $i$ or $j$\footnote{
	If a link or a node is more than $p/2$ hops away both from node $i$ and node $j$, then it cannot belong to a $i-j$ walk of length $p$.
}
. Practically speaking, at each step, nodes $i$ and $j$ need to contact all the nodes up to $p/2$ hops away in order to retrieve the current values of the weights on the links of these nodes and the values of weights on the nodes themselves. For example, when $p=2$, then the minimization is the same as the minimization of the Frobenius norm of $W$ since $Tr(W^2)=\sum _{i,j}w_{ij}^2=||W||_F^2$, and the  gradient $g_l$ can be calculated as $g_l=2\times (2W_{ij}-W_{ii}-W_{jj})$ which depends only on the weights of the vertices incident to that link and the weight of the link itself.

An advantage of our approach is that it provides a trade-off between locality and optimality. In fact, the larger the parameter $p$, the better the solution of problem \eqref{tracemin} approximates the solution of problem \eqref{minim}, but at the same time the larger is the neighborhood from which each node needs to retrieve the information. When $p=2$, then $g_l$ where $l\sim (i,j)$ only depends on the weights of subgraph induced by the two nodes $i$ and $j$. For $p=4$, the  gradient $g_l$ depends only on the weights found on the subgraph induced by the set of vertices $N_i\cup N_j$, then it is sufficient that nodes $i$ and $j$ exchange the weights of all their incident links.

config: arxiv


TITLE: What do $\Gamma$-sets classify?
QUESTION [16 upvotes]: The category $\Gamma^{\mathrm{op}}$ is defined to be a skeleton of the category of finite pointed sets (see also this question).  Then $\Gamma$-spaces, meaning space-valued presheaves $\Gamma^{\mathrm{op}}\to \mathrm{Spaces}$, can be used to present spaces with commutative and associative multiplication up to all higher homotopies.  This is similar to how the category $\Delta^{\mathrm{op}}$ can be defined as a skeleton of the category of finite total orders with distinct endpoints, and presheaves $\Delta^{\mathrm{op}}\to \mathrm{Spaces}$ (simplicial spaces) can be used to present spaces with associative multiplication up to all higher homotopies.
It is known that the topos of simplicial sets is the classifying topos for total orders with distinct endpoints.  Does the topos of set-valued presheaves on $\Gamma$ have a similar interpretation?

REPLY [2 votes]: Of course the above answer of @AndreasBlass exhausts it all, but it may be still amusing to compute directly the statement in the previous comment by @CharlesRezk.
One additional piece of information is this: for an object $X$ in a topos $T$, giving a geometric morphism from a topos $E$ to $T/X$ is equivalent to giving a geometric morphism $f:E\to T$ together with a point $1\to f^*(X)$.
Applying this to $T=Psh(fSet^{op})$ and $X=$ the generic object, which is the embedding $X:(fSet^{op})^{op}\to Set$ gives that the category of pointed objects of $E$ is equivalent to the category of gm's from $E$ to $Psh(fSet^{op})/X$. Now the latter is equivalent to presheaves over the Grothendieck construction of $X$ which in turn is equivalent to the category of finite pointed sets (objects are pairs $(n,i)$ where $n$ is a finite set and $i$ is an element of $X(n)$, i.~e. of $n$, etc....), as a particular case of the equivalence
$$
Psh(C^{op})/\hom_C(c,-)\simeq Psh((c/C)^{op})
$$


text:
\begin{document}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}

\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{clm}[thm]{Claim}
\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{notation}[thm]{Notation}
\newtheorem{question}[thm]{Question}
\theoremstyle{remark}

\newtheorem{exm}[thm]{Example}
\newtheorem{rem}[thm]{Remark}
\def\N{{\mathbb N}}
\def\G{{\mathbb G}}
\def\Q{{\mathbb Q}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\P{{\mathbb P}}
\def\A{{\mathbb A}}
\def\Z{{\mathbb Z}}
\def\v{{\mathbf v}}
\def\x{{\mathbf x}}
\def\O{{\mathcal O}}
\def\M{{\mathcal M}}
\def\kbar{{\bar{k}}}
\def\tr{\mbox{Tr}}
\def\id{\mbox{id}}
\def\qed{{\tiny $\clubsuit$ \normalsize}}

\renewcommand{\theenumi}{\alph{enumi}}

\title{The arithmetic puncturing problem and integral points}

\author{David McKinnon}
\author{Yi Zhu}

\begin{abstract}
In this paper, we provide evidence to support a positive answer to a question of Hassett and Tschinkel.  In particular, if an algebraic variety $V$ has a dense set of rational points, they ask whether or not the set of $D$-integral points is potentially dense, where $D$ is a set of codimension at least two.  We give a positive answer to this question in many cases, including varieties whose generic linear section is a smooth rational curve, and certain $K3$ surfaces.  We also discuss some stronger notions of integrality of points, and give some positive answers to some cases of the analogous question in the stronger context.
\end{abstract}

\maketitle

\vspace{-5pt}
\section{Introduction}

In \cite{HT}, as Problem 2.13 (``The Arithmetic Puncturing Problem"), Hassett and Tschinkel ask the following question:

\begin{question}\label{htquestion}
Let $X$ be a projective variety with canonical singularities and $D$ a subvariety of codimension $\geq 2$.  Assume that rational points on $X$ are potentially dense.  Are integral points on $(X,D)$ potentially dense?
\end{question}

\vspace{.1in}

In the paper, they provide positive answers to this question in various cases, including toric varieties and products of elliptic curves.  The purpose of this paper is to provide a larger set of positive answers to Question~\ref{htquestion}, to ask a stronger version of Question~\ref{htquestion} (namely Question~\ref{mzquestion}), and to give a positive answer to the stronger question in a large number of cases.

Of course, the hypothesis that $D$ has codimension two cannot be removed, as there are countless well known examples of varieties with a dense set of rational points but a degenerate set of integral points if $D$ is a divisor.

In order to state the stronger question, we need to fix some notation and definitions.  Let $X$ be a projective algebraic variety, $D\subset X$ a Zariski closed subset, both defined over a number field $k$.  Let $M_k$ be the set of places of $k$.  The following definition is a slight generalization of Definition 1.4.3 in \cite{Vo}:

\begin{dfn}
Let $S$ be a finite set of places of $k$.  A subset $R\subset X(k)-D(k)$ is called {\em $(D,S)$-integralizable} if and only if there are global Weil functions $\lambda_{D,v}$ and non-negative real numbers $n_v$ such that $n_v=0$ for all but finitely many places $v$ for each $v$, and such that
\[\lambda_{D,v}(P)\leq n_v\]
for all $v\in M_k-S$ and $P\in R$.
\end{dfn}

This generalizes \cite{Vo} only in that we do not demand that $S$ contain the set of infinite places of $k$.  For definitions and discussion of Weil functions (called ``local height functions'' by \cite{Si}), see \cite{La}, \cite{Si}, and \cite{Vo}.

The particular case of this new definition that most interests us in this paper is the following:

\begin{dfn}
A subset $R\subset X(k)$ is {\em everywhere $D$-integral} if and only if $R$ is $(D,\emptyset)$-integralizable.
\end{dfn}

We can now state the stronger version of Question~\ref{htquestion}:

\begin{question}\label{mzquestion}
Let $X$ be a projective variety with canonical singularities and $D$ a subvariety of codimension $\geq 2$.  Assume that rational points on $X$ are potentially dense.  Are everywhere $D$-integral points on $X$ potentially dense?
\end{question}

The classical notion of an integral point is simple one whose coordinates don't have denominators.  In affine space over $\Q$, an integral point in this sense is one whose closure in a model over $\mbox{Spec}(\Z)$ does not intersect the closure of the hyperplane at infinity.  One can generalize this notion to that of an $S$-integral point, by permitting intersections over a finite set $S$ of places.  If $S'$ is the union of $S$ with the set of infinite places of $k$, then this corresponds precisely to our notion of $(D,S')$-integralizable, only with the additional requirement that $n_v=0$ for all finite $v\not\in S$.

The remainder of the paper is structured as follows.  Section 2 establishes a few preliminaries, regarding various different notions of integral point and comparing them.  Section 3 contains the main theorems regarding everywhere integral points and Question~\ref{mzquestion}, and Section 4 proves results about more classical notions of integral points and Question~\ref{htquestion}.  The central philosophy of the paper is to prove preliminary results on curves, and then use those to prove results in higher dimension when the variety in question is covered by curves.

\section{Funding}

The first author was supported by a Discovery Grant from the Natural Sciences and Engineering Research Council of Canada.

\section{Preliminaries}

In this paper, we will consider four different notions of integrality:

\begin{enumerate}
\item Total $(D,\emptyset)$-integrality, where $n_v=0$ for all finite places $v$ but there are still constraints at the infinite places.
\item  Sets of integral points in the truly classical sense, which correspond to $(D,\infty)$-integral points, where $\infty$ represents the set of infinite places of $k$.
\item Everywhere $D$-integral sets.
\item $(D,S)$-integralizable sets.
\end{enumerate}

Note that the last two notions of integrality apply only to sets -- they are not well defined for individual points.  Applied to sets, each of these four notions of integrality are related in the following ways:

Classical $(D,\emptyset)$-integrality is the strongest notion of integrality that we will consider, but Zariski dense sets of classical $(D,\emptyset)$-integral points do exist.  For example, if $D$ is empty, then every rational point is classically $(D,\emptyset)$-integral.  Any set of classically $(D,\emptyset)$-integral points is also $(D,\infty)$-integral, everywhere $D$-integral, and $(D,S)$-integralizable for any $S$.

The notions of ``classically $(D,\infty)$-integral sets of points'' and ``everywhere $D$-integral sets'' are incomparable.  The set of points in $\P^1(\Q)$ of the form $[n:1]$ for $n\in\Z$ is classically $D$-integral for $D=\infty$, but is not everywhere $D$-integral, because if $\lambda_\infty$ is the Weil function for $\infty$ at the infinite place, then for any real number $B$, there are only finitely many $n$ for which $\lambda_\infty(n:1)\leq n$.  Conversely, let $X=\P^2$, with $D=\{[0:0:1],[0:1:0],[0:1:1],[1:0:0],[1:0:1],[1:1:0],[1:1:1]\}$.  Then since every rational point in $\P^1$ is congruent to one of the seven points in $D$ modulo $2$, there are no classically $D$-integral points ... but by setting $n_2=2$, one easily obtains an infinite set of everywhere $D$-integral points, for example points of the form $\{[2k+1:2:2]\}$ for any odd integer $k$.

Finally, a set which satisfies any of the first three definitions of integrality is automatically $(D,S)$-integral for any choice of $S$ (if we require $S$ to contain all the infinite places).

We would like to be able to prove results for classical everywhere $D$-integral sets of points, but have not yet been able to surmount the additional technical obstacles created by the additional restriction.

If $D$ is a very ample divisor, then there are no infinite, everywhere $D$-integral sets.

\begin{thm}
Let $X$ be a projective algebraic variety, $D$ a very ample divisor on $X$ (all defined over a number field $k$), $R$ an everywhere $D$-integral subset of $X(k)$.  Then $R$ is finite.
\end{thm}

\noindent
{\it Proof:} \/ We start by proving the theorem for $X=\P^n_k$ and $D=\{x_0=0\}$.  Any set of everywhere $D$-integral points is a set of $k$-rational points in the affine piece $x_0\neq 0$ whose coordinates have $v$-adic absolute value absolutely bounded for each infinite place $v$.  Moreover, there is an integer $N$ such that every point in $R$ can be written as a fraction of integers in $\O_k$ whose denominator divides $N$.  Thus, every coordinate of every point of the set $R$ lies in a compact subset of Minkowski space (that is, the product of the archimedean completions of $k$ modulo complex conjugation), and is a subset of the lattice $\frac{1}{N}\O_k$, so by the geometry of numbers $R$ must be finite.  It follows that the set $R$ must be finite.

More generally, let $X$ be an arbitrary projective variety, $D$ an arbitrary very ample divisor.  Then there is an embedding $\phi\colon X\to\P^n$ such that $\phi^*(\{x_0=0\})=D$.  Furthermore, $\phi(R)$ must be an everywhere $\{x_0=0\}$-integral set, so it must be finite, implying the finiteness of $R$.  \qed

\vspace{.1in}

By contrast, if $D=\emptyset$, then an everywhere $D$-integral set is simply a set of rational points, and there are many examples of Zariski dense sets of rational points.  In this article we provide nontrivial examples of such sets, in order to illuminate the spectrum of possibilities.

\section{Everywhere Integral Points}

We begin with a theorem about everywhere integral points on curves with respect to an arithmetic zero-cycle.

\begin{thm}\label{curveintegral}
Let $V$ be an algebraic variety defined over a number field $k$, and let $\mathcal{V}$ be a model of $V$ over $\mbox{Spec}(\O_k)$.  Let $C$ be an irreducible curve on $V$, and let $\mathcal{C}$ be its closure in $\mathcal{V}$.  Let $D$ be a Zariski closed subset of $V$, and let $\mathcal{D}$ be its closure in $\mathcal{V}$.

For every place $v$ of $k$, let $n_v$ be a non-negative real number such that $n_v=0$ for all but finitely many places $v$.  Choose Weil functions $\lambda_{D,v}$ for each place $v$.  Assume that there is a point $P\in C(k)$ satisfying
\[\lambda_{D,v}(P)\leq n_v\]
for every place $v$.

If $D\cap C=\emptyset$ and $C(k)$ is infinite, then there are infinitely many points $Q\in C(k)$ satisfying
\[\lambda_{D,v}(Q)\leq n_v\]
\end{thm}

\noindent

\noindent
{\it Proof:} \/ Let $S$ be the set of places $v$ of $k$ such that either $v$ is archimedean, or $\mathcal{D}\cap\mathcal{C}$ is supported on $v$.  Note that $S$ is finite.

For each $v\not\in S$, $\lambda_{D,v}(Q)=0$ for all $Q\in C$, so we may restrict our attention to $v\in S$.

If $v$ is finite with corresponding prime $\pi$ of $\O_k$, then the condition $\lambda_{D,v}(P)<n_v$ depends only on the residue class of $P$ modulo a suitable power of $\pi$.  (See for example subsection 2.2.2 of \cite{BG}.)  Thus, the collection of all $Q\in C(k)$ satisfying $\lambda_{D,v}(Q)\leq n_v$ for all finite $v$ contains the set of points $Q$ such that $Q\equiv P\pmod N$ for some suitable nonzero $N\in\O_k$.

If $v$ is infinite, then the restriction $\lambda_{D,v}(Q)\leq n_v$ defines the complement of an open disk in the $v$-adic topology.

There are now two cases: either the geometric genus of $C$ is zero, or one.

If the geometric genus of $C$ is zero, then the theorem now follows immediately from the Weak Approximation Theorem for $\P^1$.

Weak Approximation does not hold for curves of genus one, however, so we must work a bit harder.  The set $B$ of points $Q$ such that $Q\equiv P\pmod N$ for some nonzero $N\in \O_k$ contains the image on $C$ of a coset of a finite index subgroup $A$ of the Mordell-Weil group of the normalization $\tilde{C}$ of $C$ over $k$.  It remains to show that $B$ contains an infinite subset satisfying $\lambda_{D,v}(Q)\leq n_v$ for all the infinite places $v$.

The subgroup $A$ is infinite by assumption, so it contains a point $R\neq P$ of infinite order.  If we let $\C'$ be the completion of $\tilde{C}$ with respect to the product of all the infinite $v$-adic topologies, it becomes a finite union of complex tori.  By Kronecker's Theorem in diophantine approximation (see for example Theorem 443 of \cite{HW}), the identity element of $C'$ is a limit point of the subgroup $A$.  After translation by some element in the inverse image of $R$, and pushing forward to $C$, we see that $B$ has infinite intersection with arbitrarily small neighbourhoods of $R$ (in the product of infinite topologies).  A small enough such neighbourhood will consist entirely of points satisfying $\lambda_{D,v}(Q)\leq n_v$ for all the infinite places $v$, so the theorem is proven.  \qed

\vspace{.1in}

The main theorems of this section crucially use Theorem~\ref{curveintegral} to establish the density of integral points in higher dimension.

\begin{thm}\label{rcvaintegral}
Let $X$ be a projective variety defined over a number field $k$, embedded in $\P^n$ so that the intersection of $X$ with a generic linear space of codimension $\dim X-1$ is a curve of genus zero.  Let $D$ be an algebraic subset of $X$ of codimension at least two.  Then, possibly after some finite extension of $k$, there is a Zariski dense set of everywhere $D$-integral points on $X$.  In particular, Question~\ref{mzquestion} has a positive answer for $(X,D)$.
\end{thm}

\noindent
{\it Proof:} \/ We first choose a model $\mathcal{X}$ for $X$ over $\mbox{Spec}\O_k$, and let $\mathcal{D}$ be the closure of $D$ in $\mathcal{X}$.  Choose a global Weil function $\lambda_D$ for $D$, with corresponding local Weil functions $\lambda_{D,v}$.

Choose an algebraic point $P$ not contained in the support of $D$ or the singular set of $X$, and define non-negative real numbers $n_v$ by $n_v=\lambda_{D,v}(P)$.  After a finite extension of $k$, we may assume that $P$ is $k$-rational.  Since this is the only time when a finite extension of $k$ is necessary, we will fix that finite extension now and assume hereafter that $k$ is large enough.

A generic linear space of codimension $\dim X-1$ through $P$ intersects $X$ in a curve of genus zero, which must be birational to $\P^1_k$ by Bertini's Theorem because it contains the smooth point $P$.  Let $A$ be the set of linear spaces $L$ that satisfy the following conditions:
\begin{itemize}
\item $L$ is defined over $k$.
\item $L$ contains $P$.
\item $L\cap X$ is a curve of genus zero that is smooth at $P$.
\item $L\cap D$ is empty, so that $\mathcal{L}\cap\mathcal{D}$ is an arithmetic zero-cycle, where $\mathcal{L}$ is the closure of $L$ in $\mathcal{X}$.
\end{itemize}
By Theorem~\ref{curveintegral}, for any $L\in A$, there are infinitely many rational points $Q$ on $L\cap X$ such that
\[\lambda_{D,v}(Q)\leq n_v\]
for all $v$.  The union of such curves is dense in $X$.  To see this, note that the union of all linear spaces $L$ that pass through $P$ and are defined over $k$ is Zariski dense in $X$.  The conditions of being smooth at $P$ and intersecting $D$ trivially are both nonempty open conditions (because $D$ has codimension at least two in $X$), so the union of the curves in $A$ must be dense in $X$.  We conclude that there is a Zariski dense set of everywhere $D$-integral points, as desired.  \qed

\vspace{.1in}

\begin{rem}
	Theorem~\ref{rcvaintegral} applies in a great many cases.  For example, if $X$ is a cone over a rational normal curve in projective space and $D$ is a finite set of points on $X$, then Theorem~\ref{rcvaintegral} implies that the set of everywhere $D$-integral points on $X$ is potentially Zariski dense.
\end{rem}

We can prove a variation on Theorem~\ref{rcvaintegral} using the group structure on an elliptic surface.

\begin{thm}\label{ellintegral}
Let $\pi\colon X\to\P^1$ be an elliptic surface, defined over a number field $k$, and let $\mathcal{E}$ be the corresponding elliptic curve over $k(t)$.  Let $S$ be the identity section of $\pi$ (that is, the section corresponding to the identity element of $\mathcal{E}$).  Assume that there is a curve $C$ on $X$ with an infinite set of $k$-rational points, and such that $C$ is not a component of a fibre of $\pi$, such that $C$ does not correspond to a torsion point of $\mathcal{E}$.  Let $D$ be a finite set of points on $X$ such that $D\cap S=\emptyset$.  Then there is an everywhere $D$-integral set of points on $X$.  In particular, Question~\ref{mzquestion} has a positive answer for $(X,D)$.
\end{thm}

\noindent
{\it Proof:} \/ By replacing $C$ with a suitable multiple of itself (in the group law on $\mathcal{E}$), we may assume that $C\cap D=\emptyset$.  (For each fibre $F$ of $\pi$ that intersects $D$, either $C\cap F$ has infinite order on $F$ -- in which case any large enough multiple of $C$ will be disjoint from $D$ on $F$ -- or else multiply $C$ by a positive integer $n$ divisible enough so that $nC\cap F=S\cap F\not\in D$.)
Let $\mathcal{X}$ be a regular model of $X$ over $\mbox{Spec}(\O_k)$, and let $\mathcal{C}$ and $\mathcal{D}$ be the closures of $C$ and $D$, respectively, in $\mathcal{X}$.

By Theorem~\ref{curveintegral}, $C$ contains an infinite, everywhere $D$-integralizable set of points.

Moreover, by Silverman's Specialization Theorem (Theorem 11.4 of Chapter III of \cite{Si2}), we may assume that all but finitely many of those everywhere $D$-integral points lies on a smooth fibre of $\pi$, and has infinite order as an element of that fibre.

We conclude that there is an infinite set $G$ of $k$-rational points on $\P^1$ such that for all $P\in G$, $\pi^{-1}(P)$ is a smooth elliptic curve containing an everywhere $D$-integral point of infinite order, and such that $\pi(D)\cap G=\emptyset$.

Any fibre $F$ of $\pi$ with $\pi(F)\in G$ is therefore a smooth elliptic curve with $F\cap D=\emptyset$, and with an everywhere $D$-integral point $P$ of infinite order.  Again by Theorem~\ref{curveintegral}, all such fibres contain an infinite set of everywhere $D$-integral points.  \qed

\section{$S$-integral Points}

We begin by proving the following variation on Theorem~\ref{curveintegral}.  It will play a similarly central role in this section.

\begin{thm}\label{curvesintegral}
Let $V$ be an algebraic variety defined over a number field $k$, and let $\mathcal{V}$ be a model of $V$ over $\mbox{Spec}(\O_k)$.  Let $C$ be an irreducible curve on $V$, and let $\mathcal{C}$ be its closure in $\mathcal{V}$.  Let $D$ and $N$ be Zariski closed subsets of $V$, and let $\mathcal{D}$ and $\mathcal{N}$ be their closures in $\mathcal{V}$, respectively.  Let $L=D\cup N$, and let $S$ be a set of places of $k$ that contains all the archimedean places of $k$.

For every place $v$ of $k$ with $v\not\in S$, let $n_v$ be a non-negative real number such that $n_v=0$ for all but finitely many places $v$.  Choose Weil functions $\lambda_{L,v}$ for each place $v$.  Assume that there is a point $P\in C(k)$ satisfying
\[\lambda_{L,v}(P)\leq n_v\]
for every place $v\not\in S$.

If $N\cap C=\emptyset$ and $C$ contains an infinite set of $(D,S)$-integral points, then there are infinitely many points $Q\in C(k)$ satisfying
\[\lambda_{L,v}(Q)\leq n_v\]
for every place $v\not\in S$.
\end{thm}

\noindent
{\it Proof:} \/  Since $C(k)$ is infinite, it follows that $C$ must have geometric genus zero or one.  The condition that $C$ contain a dense set of $D$-integral points implies that $C$ must intersect $D$ in at most two places of $C$ (places in the sense of points of the normalization of $C$), and that $C\cap D=\emptyset$ if $C$ has genus one.

The case in which $C\cap D=\emptyset$ follows {\em a fortiori} from Theorem~\ref{curveintegral}, so we assume that $C$ is a genus zero curve with either one or two places supported on $D$.  Let $\pi\colon \tilde{C}\to C$ be the normalization map over $k$.  The set of points $R$ of $\tilde{C}$ with $\pi(R)\not\in D$ are a principal homogeneous space for an arithmetic group ($\mathbb{G}_a$ if there is one place of $C$ on $D$, and $\mathbb{G}_m$ if there are two places), so by choosing a point $R_0$ on $\tilde{C}$, we can give the $(\pi^*D,S)$-integral points of $\tilde{C}$ the structure of an arithmetic group $G$.  The set $B$ of points $Q$ of $C$ such that $Q\equiv P\pmod N$ for some nonzero $N\in\O_k$ -- which, as before, is contained in the set of points $Q$ satisfying $\lambda_{L,v}(Q)\leq n_v$ for all $v$ not in $S$ -- contains the image on $C$ of a coset of a finite index subgroup $A$ of $G$, and is therefore infinite, as desired.  \qed

\begin{rem}
Note that the naive analogue of Theorem~\ref{curvesintegral} in the setting of Theorem~\ref{curveintegral} is false.  That is, if $C$ is isomorphic to $\mathbb{G}_a$ or $\mathbb{G}_m$, then even if $C\cap D$ is empty (over $k$), it's possible that the set of everywhere $D$-integral points of $C$ are finite and nonempty.  In both cases, the integral points of $C$ are a finitely generated abelian group.  If we choose $k=\Q$, and consider the archimedean place of $\Q$, then the only limit points of the integral points of $C$ are the place(s) at infinity.  Thus, if the set $\{Q\mid \lambda_{D,\infty}(Q)\leq n_\infty\}$ does not include a place at infinity, then it will be finite and discrete.
\end{rem}

Theorem~\ref{curvesintegral} enables us to prove the following result, in the same spirit as Theorem~\ref{rcvaintegral}.

\begin{thm}
Let $X$ be a projective variety defined over a number field $k$, embedded in $\P^n$ so that the intersection of $X$ with a generic linear space of codimension $\dim X-1$ is a curve of genus zero.  Let $D$ be a proper Zariski closed subset of $X$ whose codimension one (in $X$) component has degree at most two.  Let $S$ be a finite set of places of $k$, containing all the archimedean places.  Then, possibly after some finite extension of $k$, there is a Zariski dense set of everywhere $(D,S)$-integral points on $X$.
\end{thm}

\noindent
{\it Proof:} \/ The proof is eerily similar to the proof of Theorem~\ref{rcvaintegral}.  We first choose a model $\mathcal{X}$ for $X$ over $\mbox{Spec}\O_k$, and let $\mathcal{D}$ be the closure of $D$ in $\mathcal{X}$.  Choose a global Weil function $\lambda_D$ for $D$, with corresponding local Weil functions $\lambda_{D,v}$.  Also, write $D=D'+N$, where $D'$ is a (Weil) divisor and $N$ is a cycle of codimension at least two.  (The components of $N$ need not all have the same dimension.)

Choose an algebraic point $P$ not contained in the support of $D$ or the singular set of $X$, and define non-negative real numbers $n_v$ by $n_v=\lambda_{D,v}(P)$.  After a finite extension of $k$, we may assume that $P$ is $k$-rational, and that the unit group of the ring of integers $\O_k$ is infinite.  Since this is the only time when a finite extension of $k$ is necessary, we will fix that finite extension now and assume hereafter that $k$ is large enough.

A generic linear space of codimension $\dim X-1$ through $P$ intersects $X$ in a curve of genus zero, which must be birational to $\P^1_k$ by Bertini's Theorem because it contains the smooth point $P$.  Let $A$ be the set of linear spaces $L$ that satisfy the following conditions:
\begin{itemize}
\item $L$ is defined over $k$.
\item $L$ contains $P$.
\item $L\cap X$ is a curve of genus zero that is smooth at $P$.
\item $L\cap N$ is empty, so that $\mathcal{L}\cap\mathcal{N}$ is an arithmetic zero-cycle, where $\mathcal{L}$ is the closure of $L$ in $\mathcal{X}$.
\end{itemize}
By Theorem~\ref{curvesintegral} applied to $D'$ and $N$, for any $L\in A$, there are infinitely many rational points $Q$ on $L\cap X$ such that
\[\lambda_{D,v}(Q)\leq n_v\]
for all $v\not\in S$.  (Since $D'$ has degree at most two, the curve $L\cap X$ is a curve of genus zero whose normalization is either $\P^1$, $\mathbb{G}_a$, or $\mathbb{G}_m$.  The first two kinds of curves cannot have a finite but nonempty set of integral points for any $k$, and the infinitude of the unit group of $\O_k$ ensures the same for $\mathbb{G}_m$.)  The union of such curves is dense in $X$.  To see this, note that the union of all linear spaces $L$ that pass through $P$ and are defined over $k$ is Zariski dense in $X$.  The conditions of being smooth at $P$ and intersecting $N$ trivially are both nonempty open conditions (because $N$ has codimension at least two in $X$), so the union of the curves in $A$ must be dense in $X$.  We conclude that there is a Zariski dense set of $(D,S)$-integral points, as desired.  \qed


TITLE: The (most probable) color of the card in the box
QUESTION [2 upvotes]: There are an equal number of red, yellow, green, and blue cards. Take one of them and put it in the box. Suppose that red cards was most selected, followed by yellow, green, and blue when we selected cards outside the box randomly. What is the color of the card in the box?$^1$

This is the problem suggested in the lecture$^2$ yesterday, and I tried to solve the problem by this way:

Formally(?) Edited Problem There are $n$ red cards, $n$ yellow cards, $n$ green cards, and $n$ blue cards. First, take one of them and put it in the box. Second, take any number of cards among the rest and examine their color. After the second step, we found that $n_r \ge n_y \ge n_g \ge n_b$, where $n_r, n_y,n_g,n_b$ is the number of (red, yellow, green, blue) cards taken in second step. What is the most probable color of the card in the box?

Attempted Solution
Let $n$ be the number of each red, yellow, green, and blue cards. Let $A$ be the event that red cards are most selected, followed by yellow, green, and blue when we get cards randomly. $R$ the event that the red card is in the box, $Y$ that the yellow card is in the box, $G$ green, and $B$ blue. Then the probability that the color of the card in the box is red, yellow, green, and blue each is $P(R|A)$, $P(Y|A)$, $P(G|A)$, and $P(B|A)$. Now let's find $P(R|A)$. By the law of total probability,
$$
P(R|A)=\frac{P(R\cap A)}{P(A)}=\frac{P(A|R)P(R)}{P(A|R)P(R)+P(A|Y)P(Y)+P(A|G)P(G)+P(A|B)P(B)}.
$$
When the red card is in the box, there are $n-1$ red card, and $n$ yellow, green, and blue card each outside the box. Then there are $\binom{n+3}{4}$ ways to select red card most, followed by yellow, green, and blue cards among total $n(n+1)^3$ ways; $\binom{n+3}{4}$ is the number of the way of choosing four elements among $0,1,\dots,n-1$ with repitition. Thus,
$$
P(A|R)=\frac{\binom{n+3}{4}}{n(n+1)^3}.
$$
Now find $P(A|Y)$. When the yellow card is in the box, there are $n-1$ yellow card, and $n$ red, green, and blue card each outside the box. We select either $n$ red cards or less than $n$ red cards. When we select $n$ red cards, there are $\binom{n+2}{3}$ ways, and when we select less than $n$ red cards, there are $\binom{n+3}{4}$ ways among $n(n+1)^3$ ways. Thus,
$$
P(A|Y)=\frac{\binom{n+3}{4}+\binom{n+2}{3}}{n(n+1)^3}.
$$
In similar way, we can find that
$$
P(A|G)=\frac{\binom{n+3}{4}+\binom{n+2}{3}+\binom{n+1}{2}}{n(n+1)^3},\qquad P(A|B)=\frac{\binom{n+3}{4}+\binom{n+2}{3}+\binom{n+1}{2}+\binom{n}{1}}{n(n+1)^3}.
$$
Since $P(R)=P(Y)=P(G)=P(B)=\frac{1}{4}$, we get
\begin{align}
P(R|A)&=\frac{\binom{n+3}{4}}{4\binom{n+3}{4}+3\binom{n+2}{3}+2\binom{n+1}{2}+\binom{n}{1}}\\
P(Y|A)&=\frac{\binom{n+3}{4}+\binom{n+2}{3}}{4\binom{n+3}{4}+3\binom{n+2}{3}+2\binom{n+1}{2}+\binom{n}{1}}\\
P(G|A)&=\frac{\binom{n+3}{4}+\binom{n+2}{3}+\binom{n+1}{2}}{4\binom{n+3}{4}+3\binom{n+2}{3}+2\binom{n+1}{2}+\binom{n}{1}}\\
P(B|A)&=\frac{\binom{n+3}{4}+\binom{n+2}{3}+\binom{n+1}{2}+\binom{n}{1}}{4\binom{n+3}{4}+3\binom{n+2}{3}+2\binom{n+1}{2}+\binom{n}{1}}.
\end{align}
Since $P(R|A)<P(Y|A)<P(G|A)<P(B|A)$, the most probable color of the card in the box is blue.
My question: Is my attempted solution correct? What is an alternative solution of the problem?

$^1$ I interpreted this question as "Find the most probable color of the card in the box."
$^2$ The lecture is not about math, but math education.

REPLY [0 votes]: With your formal statement of the problem, it is really very simple: the cards don't care in what order the steps happen - each is equally likely to end up picked in any particular single draw. So if you imagined first having picked the $n_i$ cards for $i = r, g, b, y$ (the second step) then what is left in the pile is $n-n_i$ for each colour. So the probability that the card in the box is color $i$ is $$P(i) = \frac{n-n_i}{4n - \sum_i n_i}.$$
You can generalize to any initial numbers in the pile, not necessarily the same for each color: you will get something very similar $$P(i) = {n_{i,0} - n_i\over n_{t}-\sum_i n_i},$$
where $n_t = \sum_i n_{i,0}$ is the total number of cards in the beginning.

EDIT: I was assuming at first that the numbers $n_i$ were actually known, but when looking through your attempted solution, I'm now guessing that what you want is a probability conditional only on the event that $n_r \geq n_y \geq n_g \geq n_b$. I can adapt my argument for that purpose though.
Let's wrap all the information about the values of the $n_i$'s in some variable $N$ (it is an ordered quadruple). Let $\cal N$ be the set of all values of $N$ for which the inequality is true, and consider a particular outcome where the $n_i$'s have values that satisfy it, that is $N \in \cal N$. What I have found above then is $P(i|N)$. We don't need to bother finding $P(N)$, because we can claim from the formula for $P(i|N)$ that for every $N \in \cal N$,
$$ P(b|N) \geq P(g|N) \geq P(y|N) \geq P(r|N) $$
and at least for $n \geq 2$, for each of the inequalities above there is at least one case in which it is strict; for example, for the middle one, that would be $(1, 1, 0, 0)$. So now we have
$$ P(b\cap N\in{\cal N}) = \sum_{N\in \cal N}P(N)P(b|N) > \sum_{N\in \cal N}P(N)P(g|N) = P(g\cap N\in\cal N) $$
and similarly for the others. Dividing by $P(N\in\cal N)$, which is the same for all of them, we find $P(b|N\in{\cal N}) > P(g|N\in{\cal N}) > P(y|N\in{\cal N}) > P(r|N\in{\cal N})$.


TITLE: Lagrange optimization of reciprocals
QUESTION [1 upvotes]: Suppose we want to find the $x_i$ such that $$\sum_{i=1}^p\frac{1}{1+x_i}$$
has an extreme value, such that the $x_i$ are all non-negative, and $\sum_{i=1}^n x_i=p$.
This should be doable with lagrange multipliers, but how? The inequality is tricky, so I considered replacing the $x_i$ with $x_i^2$. However, each entry of the gradient gives you $(1+x_i^2)^{-2}2x_i=\lambda 2x_i$, so I'm not quite sure how to proceed. It seems obvious that you get a min when all the $x_i$ are 1, but what about the maximum?
Edit: It was noted that I need to check the boundary points for the maximum. Is there a systematic technique to do this? I suspect that the max will be attained when all but one of the $x_i$ is zero, but how do you start when the boundary contains so many points?

REPLY [1 votes]: Let
$$ L = \sum_{i=1}^n \frac{1}{1+x_i} - \lambda \left( \sum_{i=1}^n x_i -p \right). $$
Then
$$ \frac{\partial L}{\partial x_j} = \frac{-1}{(1+x_j)^2}-\lambda, $$
and so we discover that if the gradient of $L$ is zero (required for an internal extremum), all of the $x_j$ are equal, and in particular, equal to $p/n$, by the constraint. In this case, the value of $L$ is
$$ \frac{n}{1+p/n} = \frac{n^2}{n+p} = \frac{n(n+p)-np-p^2+p^2}{n+p} = n-p + \frac{p^2}{n+p} $$.
What if we don't have this case? Then the extremum occurs on the boundary, i.e. when one of the $x_i$ at least is zero. By symmetry we can assume $x_n=0$, and $L$ becomes
$$ L\mid_{x_n=0} = 1 + \sum_{i=1}^{n-1} \frac{1}{1+x_i} - \lambda \left( \sum_{i=1}^{n-1} x_i - p \right). $$
Ah, but this is exactly the same problem as we solved before, but with $n$ replaced by $n-1$. Hence the extremum is at $x_i=p/(n-1)$, and so the value is
$$ 1+ \frac{(n-1)^2}{n-1+p} = \frac{n-1+p-(n-1)+n(n-1)}{n-1+p} = n-p+\frac{p^2}{n-1+p}. $$
Similarly, if $k$ of the $x_i$ are zero, we find
$$ k+\frac{(n-k)^2}{n-k+p} = k+n-k-p + \frac{p^2}{n-k+p} = n-p + \frac{p^2}{n-k+p}, $$
which obviously increases as $k$ increases. Hence the global maximum is when $k=n-1$, with value $n-1+\frac{1}{1+p}$, whereas the global minimum is when all the $x_i$ are $p/n$ (can check this is a minimum using the Hessian), with value $\frac{n}{1+p/n}$.


TITLE: Discrete Math - Hasse Diagrams
QUESTION [1 upvotes]: This is one of many questions of similar type I have to do for an assignment and im troubled with what to do. The question is as follows:

Consider a relation R defined on the set A = {−7, −6, −5, −4, −3, −2,
  −1, 0, 1, 2, 3, 4, 5, 6, 7}. Determine for the following if the
  relations are reflexive, symmetric, anti-symmetric, transitive,
  partial orders, equivalence relations. (a) R = {(a, b)|a ≤ b}, if this
  is a partial order, draw the Hasse diagram.

I understand the definitions of what symmetric, anti-symmetric, reflexive and transitive are but im troubled with understanding a partial order. Also how can one draw a hasse diagram? Is there any logic/rules to apply?
thanks!

REPLY [3 votes]: To draw a Hasse diagram of a finite poset follow the algorithm below, but first notice that on any finite poset $P$, given $x,y\in P$ such that $x\neq y$, then $x$ and $y$ aren't comparable or there is a chain of covers from one to the other.
Now for the algorithm: Let $x,y,z\in P$

To each $p\in P$ associate a point $(a_p,b_p)$ on the euclidean plane in such a way that $x<y$, then $b_x<b_y$, if $x\neq y$.
If $x$ is covered by $y$, then draw a line from $(a_x,b_x)$ to $(a_y,b_y)$.
Ensure that, if $x\neq z\neq y$, $(a_z, b_z)$ is not in the line that goes from $(a_x,b_x)$ to $(a_y,b_y)$.


TITLE: Fastest way in sage to obtain the generating function
QUESTION [1 upvotes]: I want to get more generating function for this :
http://www.findstat.org/StatisticsDatabase/St000683
What is the quickest way to do this in SAGE and obtain $F_n$ for $n \geq 7$ as in the link? (when clicking "
click to show generating function ") Maybe thats also a good opportunity to ask, wheter there exist good introductions to SAGE specialising in algebra and/or combinatorics.

REPLY [1 votes]: This question is based on a MO question https://mathoverflow.net/questions/259038.
That link you provided contains code for $F_n$ in general. As the page describes, the following code computes the number of points below a given Dyck path $D$ such that the diagonal to the north-east hits the path between two down steps, and the diagonal to the north-west hits the path between two up steps:
def statistic(D):
    H = D.heights()
    left_bad_points = [(i+1, H[i+1]) for i in range(len(D)-1) if D[i] == D[i+1] == 1]
    right_bad_points = [(i+1, H[i+1]) for i in range(len(D)-1) if D[i] == D[i+1] == 0]
    result = 0
    for i,h in enumerate(D.heights()):
        for j in range(h-2,-1,-2):
            if (any((i-a + j-b) == 0 for (a,b) in left_bad_points) and
                any((i-a - j+b) == 0 for (a,b) in right_bad_points)):
                result += 1
    return result

so you can then simply compute the following values as
sage: q = var("q")
sage: sum( q^statistic(D) for D in DyckWords(6) )
q^15 + 2*q^10 + 2*q^9 + 2*q^8 + 7*q^7 + 5*q^6 + 6*q^5 + 16*q^4 + 24*q^3 + 22*q^2 + 28*q + 17
sage: sum( q^statistic(D) for D in DyckWords(7) )
q^21 + 2*q^15 + 2*q^14 + 2*q^13 + 2*q^12 + 9*q^11 + 5*q^10 + 8*q^9 + 7*q^8 + 24*q^7 + 37*q^6 + 37*q^5 + 40*q^4 + 80*q^3 + 69*q^2 + 67*q + 37
sage: sum( q^statistic(D) for D in DyckWords(8) )
q^28 + 2*q^21 + 2*q^20 + 2*q^19 + 2*q^18 + 2*q^17 + 11*q^16 + 5*q^15 + 8*q^14 + 9*q^13 + 11*q^12 + 29*q^11 + 48*q^10 + 48*q^9 + 59*q^8 + 70*q^7 + 123*q^6 + 163*q^5 + 171*q^4 + 214*q^3 + 205*q^2 + 164*q + 81
sage: sum( q^statistic(D) for D in DyckWords(9) )
q^36 + 2*q^28 + 2*q^27 + 2*q^26 + 2*q^25 + 2*q^24 + 2*q^23 + 13*q^22 + 5*q^21 + 8*q^20 + 9*q^19 + 13*q^18 + 11*q^17 + 38*q^16 + 55*q^15 + 54*q^14 + 70*q^13 + 91*q^12 + 92*q^11 + 182*q^10 + 197*q^9 + 316*q^8 + 355*q^7 + 421*q^6 + 508*q^5 + 641*q^4 + 632*q^3 + 554*q^2 + 405*q + 179
sage: sum( q^statistic(D) for D in DyckWords(10) )
q^45 + 2*q^36 + 2*q^35 + 2*q^34 + 2*q^33 + 2*q^32 + 2*q^31 + 2*q^30 + 15*q^29 + 5*q^28 + 8*q^27 + 9*q^26 + 13*q^25 + 13*q^24 + 16*q^23 + 41*q^22 + 67*q^21 + 57*q^20 + 70*q^19 + 104*q^18 + 121*q^17 + 119*q^16 + 227*q^15 + 254*q^14 + 333*q^13 + 519*q^12 + 596*q^11 + 704*q^10 + 822*q^9 + 1105*q^8 + 1476*q^7 + 1663*q^6 + 1683*q^5 + 1965*q^4 + 1912*q^3 + 1475*q^2 + 990*q + 399