text:
\section{Indecomposable and uniserial objects}

Let $k$ be an algebraically closed field, let $R$ be an associative
$k$-algebra, and let $\mfam = \{ M_{\alpha}: \alpha \in I \}$ be a
family of orthogonal points. We are interested in the indecomposable
modules in the length category $\modf$.

Since $\modf$ is a length category, we have a
Krull-Remak-Schmidt-Azumaya theorem. So every object in $\modf$ has
a finite indecomposable decomposition, unique up to a permutation,
and $\enm_R(M)$ is a local ring for all indecomposable objects $M
\in \modf$. We say that $\modf$ is a \emph{uniserial category} if
every indecomposable object in $\modf$ is uniserial.

\begin{lem} \label{l:induni}
Let $M$ be an object of $\modf$, and consider the following conditions:
\begin{enumerate}
\item $M$ is uniserial,
\item $M$ has a unique minimal submodule,
\item $M$ is indecomposable.
\end{enumerate}
Then we have $1) \Rightarrow 2) \Rightarrow 3)$. In particular, all
conditions are equivalent if and only if $\modf$ is a uniserial category.
\end{lem}
\begin{proof}
The implication $1) \Rightarrow 2)$ is obvious. If $M = N_1 \oplus N_2$
is a direct decomposition with $N_i \ne 0$ for $i=1,2$, there are minimal
sub-modules $K_i \subseteq N_i$ for $i=1,2$. This shows that $2)
\Rightarrow 3)$. The last part is clear.
\end{proof}

The implication $3) \Rightarrow 1)$ in the above lemma clearly holds if
$M$ has length $n=2$. But already in the case $n=3$, it is very easy
to come up with counterexamples:

\begin{lem} \label{l:ce1}
Let $\mfam$ be a family of orthogonal points. If $\mfam$ contains modules
$S,T$ such that $\enm_R(K)=k$ for $K=S,T$ and $\dim_k \ext^1_R(S,T)
\ge 2$, then there exists an object $M$ in $\modf$ of length $n=3$ such
that $M$ is a non-uniserial $R$-module with a unique simple submodule.
\end{lem}
\begin{proof}
From McConnel, Robson \cite{mc-ro73}, proposition 3.3 it follows that there
exists non-split extensions $U,V$ of $S$ by $T$ such that $U$ and $V$ are
not isomorphic as $R$-modules. Let $M$ be the cokernel of the diagonal map
$T \to U \oplus V$, then $M$ is a non-uniserial module with the unique
simple submodule $T$ by McConnell, Robson \cite{mc-ro73}, proposition 6.1.
\end{proof}

\begin{lem} \label{l:ce2}
Let $\mfam$ be a family of orthogonal points. If $\mfam$ contains modules
$S,T,U$ such that $\enm_R(K)=k$ for $K=S,T,U$, $\ext^1_R(U,S),
\ext^1_R(U,T) \ne 0$, and $S,T$ are non-isomorphic, then there exists an
object $M$ in $\modf$ of length $n=3$ such that $M$ is indecomposable and
such that $S$ and $T$ are simple submodules of $M$.
\end{lem}
\begin{proof}
Let $\xi_1, \xi_2 \ne 0$ be extensions of $U$ by $S$ and $U$ by $T$, and let
$\psi_i$ be representatives of $\xi_i$ in Hochschild cohomology for $i=1,2$.
Let furthermore $M$ be the extension of $U$ by $S \oplus T$ given by $(\xi_1,
\xi_2)$. Then $M \cong S \oplus T \oplus U$ as a vector space over $k$, and
the $R$-module structure of $M$ is defined by the representatives $\psi_1,
\psi_2$. A calculation shows that $\enm_R(M)=k$ if $U$ is not isomorphic to
any of $S,T$, and that $\enm_R(M)=k[x]/(x^2)$ if $U$ is isomorphic to one of
the modules $S,T$. In either case, $\enm_R(M)$ is a local ring, and therefore
$M$ is indecomposable. Since $S \oplus T \subseteq M$, it is clear that $M$
has simple submodules $S,T$.
\end{proof}

\begin{lem} \label{l:ce3}
Let $\mfam$ be a family of orthogonal points. If $\mfam$ contains modules
$S,T,U$ such that $\enm_R(K)=k$ for $K=S,T,U$, $\ext^1_R(S,U),
\ext^1_R(T,U) \ne 0$, and $S,T$ are non-isomorphic, then there exists an
object $M$ in $\modf$ of length $n=3$ such that $M$ is indecomposable but
not uniserial.
\end{lem}
\begin{proof}
The proof is similar to the proof of the lemma \ref{l:ce2}: We consider
$M = U \oplus S \oplus T$ considered as a vector space over $k$, and let the
$R$-module structure of $M$ be given by non-split extension $\xi_S \in
\ext^1_R(S,U)$ and $\xi_T \in \ext^1_R(T,U)$ via Hochschild cohomology.
A calculation shows that $\enm_R(M)=k$ if $U$ is not isomorphic to $S$ or
$T$, and $\enm_R(M) \cong k[x]/(x^2)$ otherwise, so $M$ is indecomposable
in both cases. On the other hand, $M$ has to submodules of length $2$, so
$M$ is not uniserial.
\end{proof}

\begin{cor}
Let $\mfam$ be a family of orthogonal points such that the species of
$\mfam$ is a $k$-quiver. If $\modf$ is a uniserial category, then we
have
\begin{enumerate}
\item $\sum_{\beta \in I} \dim_k (\ext^1_R(M_{\alpha},M_{\beta})) \le 1$
for all $\alpha \in I$,
\item $\sum_{\alpha \in I} \dim_k (\ext^1_R(M_{\alpha},M_{\beta})) \le 1$
for all $\beta \in I$.
\end{enumerate}
\end{cor}
\begin{proof}
This follows from lemma \ref{l:ce1}, \ref{l:ce2} and \ref{l:ce3}.
\end{proof}

We shall later see that these conditions are also sufficient for $\modf$
to be a uniserial category. We remark that this criterion has been known
since the 60's, see Amdal, Ringdal \cite{am-ri68} and Gabriel \cite{ga73},
section 8.3.

config: arxiv


TITLE: An inequality concerning Lagrange's identity
QUESTION [5 upvotes]: Does the following inequality still hold
  $$(a^2_{1}+b^2_{2}+b^2_{3})(a^2_{2}+b^2_{3}+b^2_{1})(a^2_{3}+b^2_{1}+b^2_{2})\ge (b^2_{1}+b^2_{2}+b^2_{3})(a_{1}b_{1}+a_{2}b_{2}+a_{3}b_{3})^2 $$
  $$+\dfrac{1}{2}(b_{1}a_{2}b_{3}-b_{1}b_{2}a_{3})^2+\dfrac{1}{2}(b_{1}b_{2}a_{3}-a_{1}b_{2}b_{3})^2+\dfrac{1}{2}(a_{1}b_{2}b_{3}-b_{1}a_{2}b_{3})^2\tag{*}$$
  for $a_{i},b_{i}\in \mathbb R,i=1,2,3$?

we  know Lagrange's identity
$$(a^2_{1}+a^2_{2}+a^2_{3})(b^2_{1}+b^2_{2}+b^2_{3})=(a_{1}b_{1}+a_{2}b_{2}+a_{3}b_{3})^2+\sum_{i=1}^{2}\sum_{j=i+1}^{3}(a_{i}b_{j}-a_{j}b_{i})^2$$
then we have Cauchy-Schwarz inequality
$$(a^2_{1}+a^2_{2}+a^2_{3})(b^2_{1}+b^2_{2}+b^2_{3})\ge (a_{1}b_{1}+a_{2}b_{2}+a_{3}b_{3})^2$$

REPLY [1 votes]: We have the following identity.
$$(a^2+y^2+z^2)(b^2+x^2+z^2)(c^2+x^2+y^2)-(x^2+y^2+z^2)(ax+by+cz)^2-$$
$$-\frac{1}{2}(ayz-bxz)^2-\frac{1}{2}(ayz-cxy)^2-\frac{1}{2}(bxz-cxy)^2=$$
$$=(x^2+y^2)(x^2+z^2)(y^2+z^2)+a^2b^2c^2+a^2b^2(x^2+y^2)+a^2c^2(x^2+z^2)+b^2c^2(y^2+z^2)-$$
$$-2abxy(x^2+y^2)-2acxz(x^2+z^2)-2bcyz(y^2+z^2)-xyz(abz+acy+bcx).$$
I hope it can help.


TITLE: Isometries between spherical space forms
QUESTION [3 upvotes]: Let $S^n/\Gamma_i\,(i=1,2)$ be a $n$-dimensional spherical space form, where $\Gamma_i \subset SO(n+1)$ is a finite subgroup acting freely on $S^n$.
Suppose $S^n/\Gamma_1$ is diffeomorphic to $S^n/\Gamma_2$, can we show they are isometric?

REPLY [10 votes]: Yes, diffeomorphic spherical space forms are isometric. This famous result of Georges de Rham can be found in [de Rham, G.
Complexes à automorphismes et homéomorphie différentiable.
Ann. Inst. Fourier Grenoble 2 (1950), 51–67 (1951)]. The main tool is Reidemeister's torsion. For lens spaces the result was proved by W. Franz in 1935.


TITLE: Young Tableaux of $SU(N)$: Group or Algebra?
QUESTION [1 upvotes]: I am slightly confused about the use of Young Tableaux in the context of the Lie group and Lie algebras of $SU(N)$. A Young Tableaux has an associated representation which acts on a tensor e.g. $\psi_{[\mu,\nu]}$. From what I can tell this rep is of the Lie group $SU(N)$ rather then the Lie algebra $su(N)$. And as such Young Tableaux specify reps of Lie groups rather then Lie algebras. Is this correct?
That being said, with each Young Tableaux we can associate a Dynkin label - something that is defined on Lie algebras rather then Lie groups. Does this Dynkin diagram therefore correspond to Lie algebra rep associated with the Lie group rep defined above? If not how?
Lastly If this is the case then the issue of the complex rep arises. For a Lie group the complex rep seems to be defined as:
$$R(g)^*$$
whilst for the Lie algebra it is defined as:
$$-r(\zeta)^T$$
thus if we have a Young table for $R(g)^*$ is the corresponding Dynkin diagram for $-r(\zeta)^T$ or something else?

REPLY [3 votes]: Representations of the su$(n)$ algebra will exponentiate to representations of the SU$(n)$ group, preserving irreducibility so irreps of the algebra and the group share the same labelling scheme.
The Young diagrams (the tableaux are diagrams filled with entries) are partitions $\{\lambda\}=(\lambda_1,\lambda_2,\ldots,\lambda_p)$ with $\sum_p\lambda_p=\lambda$.  For su$(n)$ they will contain at most $n$ parts.  The Dynkin labels are differences of consecutive parts in the partition so that to the partition $\{\lambda\}$ corresponds the Dynkin label $(\lambda_1-\lambda_2,\lambda_2-\lambda_3\ldots)$.
As to the last part: it depends a bit if you consider the generators to be hermitian or anti hermitian.  In general complex conjugation will transform $e^{i \theta h}$ with $h$ hermitian in the algebra to $e^{-i\theta h^\dagger}$; in the simplest case where $h$ is in the Cartan subalgebra (thus diagonal with real eigenvalues), it will reverse the sign of the eigenvalues, so the conjugate irrep has weights which are the negatives of the original irrep.
In terms of Young diagrams conjugate irreps have conjugate diagrams, i.e. diagrams are reflected along the diagonal so that the rows and columns get swapped.  For instance $\{2,1,1\}$ for instance becomes $\{3,1\}$.


TITLE: Fourier coefficients of a trigonometric series : identical to trigonometric coefficients?
QUESTION [0 upvotes]: In this thread :
Is $H(\theta) = \sum \limits_{k=1}^{\infty} \frac{1}{k} \cos (2\pi n_k \theta)$ for a given sequence $n_k$ equal a.e. to a continuous function?
Brad Rodgers answers the question, but I don't understand why the Fourier coefficients of the function $\sum_{k \neq 0} \frac{1}{|k|}e^{2i\pi n_k}$, are the $\frac{1}{|k|}$ !
Of course it seems obvious but it is not easy to prove I think. There is trigometric series with Fourier coefficients that are not their trigonometric coefficients.
How can we prove this ? Thanks.

REPLY [1 votes]: The series that defines $H$ converges in $L^2[0,1],$ hence in $L^1[0,1].$ Therefore
$$\hat H (n) = \int_0^1 (\sum_{k \neq 0} \frac{1}{|k|}e^{2i\pi n_kt})e^{-i2\pi nt}\, dt = \sum_{k \neq 0} \frac{1}{|k|}(\int_0^1 e^{2i\pi n_kt}e^{-i2\pi nt}\, dt)$$
for all $n.$ Hence $\hat H (n_k) = 1/|k|, k \ne 0,$ and $\hat H (n) = 0$ for all other $n.$


TITLE: Is coreflectiveness transitive?
QUESTION [1 upvotes]: I may have a proof but I am not sure.
Let $A_1 \subseteq A_2 \subseteq B$ be a chain of coreflective subcategories. Let $b$ be an object of $B$. Then $b$ has a coreflection $a_2 \xrightarrow{c_2} b$ with $a_2 \in Obj(A_2)$, and $a_2$ itself has a coreflection $a_1 \xrightarrow{c_1} a_2$ with $a_1 \in Obj(A_1)$. Consider an arbitrary morphism $f : a'_1 \rightarrow b$ with $a'_1 \in Obj(A_1)$. By assumption $a'_1$ is also an object of $A_2$ so there exists a unique $f' : a'_1 \rightarrow a_2$ such that $f = c_2 \circ f'$. By coreflectiveness of $A_1$ in $A_2$, the morphism $f'$ can also be factored $f' = c_1 \circ f''$ for a unique $f''$. Then $(c_1 \circ c_2) \circ f'' = f$. To prove uniqueness of $f''$ for the latter equality, let $g : a'_1 \rightarrow a_1$ be another such morphism. Then $c_2 \circ (c_1 \circ g) = c_2 \circ f'= f$ so $c_1 \circ g = f'$ by uniqueness of $f'$. Then $c_1 \circ g = c_1 \circ f''$ so $g = f''$ by uniqueness of $f''$.

REPLY [2 votes]: Your proof is correct. Note that this is just a specific case of a more general fact : the composition of two left adjoint is left adjoint to the composition of their right adjoints. In other words : given functors $F_1:\mathcal{X}\to \mathcal{Y}$, $F_2:\mathcal{Y}\to \mathcal{Z}$, $G_1:\mathcal{Y}\to \mathcal{X}$ and $G_2:\mathcal{Z}\to \mathcal{Y}$ such that $F_1\dashv G_1$ and $F_2\dashv G_2$, then $F_2F_1\dashv G_1G_2$. The proof is obtained by simply composing the natural bijections :
$$\operatorname{Hom}_{\mathcal{Z}}(F_2F_1(X),Z)\cong \operatorname{Hom}_{\mathcal{Y}}(F_1(X),G_2(Z))\cong \operatorname{Hom}_{\mathcal{X}}(X,G_1G_2(Z)).$$
In your case $F_1$ and $F_2$ are the two inclusion functors; and in fact your proof itself is basically the particularisation of the composition I wrote above to your specific case.


TITLE: Can you explain us a simple example, for a mathematical function, of Kramers–Kronig relations?
QUESTION [1 upvotes]: I am interesting in learn easy facts about new issues of complex analysis. I've read in Wikipedia the statement of Kramers–Kronig relations.

Question. Please can you provide us a simple example for mathematicians of such theorem? I am asking thus about a $\chi_1(\omega)$ being the real part, and $\chi_2(\omega)$ the imaginary part respectively, of a complex function $\chi(\omega)$ satyisfying the hypothesis of the theorem, and how one gets from  such example one of those integrals. Since I can read the identities from Wikipedia, only are required the calculations for a simple example inspired in a mathematical function. Thanks in advance.

In the article of spanish Wikipedia there are different expressions for such identities (you can use these or previous).
In the english version of Wikipedia are referenced the genuine works due to Kramers and Kroning.

REPLY [0 votes]: Kramers Kronig relations are used in general to find the realtion between the real and imaginary parts of any complex numbers, e.g. if you know the real part then you can derive the imaginary part and vice versa. but there are some constraints to in these relations to be appicable for any complex function, so not all of the complex functions are KK transformable.
you can take a look at this link, i think it is helpfull
http://lampx.tugraz.at/~hadley/ss2/linearresponse/causality.php
also this
http://www.iam.kit.edu/wet/plainhtml/Download/Derivation_Kramers-Kronig.pdf


TITLE: Non-separating surfaces and the 2nd homology of a $3-$manifold
QUESTION [2 upvotes]: I have a question about the relation between non-separating surfaces and the nontrivial 2nd homology of a 3-manifold. The question is:
Let $\Sigma$ be a closed nonseparating surface embedded in a closed $3-$manifold $M,$ is it true that $\Sigma$ represents a nontrivial element in $H_{2}(M; \mathbb{Z}_{2})$? And on the other hand, is it true that every nontrivial element in $H_{2}(M;\mathbb{Z}_{2})$ can be represented by a nonseparating surface in $M$?

REPLY [1 votes]: The answer is Yes.
In fact this there is a construction due to Stallings that lets you construct non-separating surfaces in this way.
Take a $3$--manifold $M$, which is compact and look at $f:M\rightarrow S^{1}$. From compactness, we know that $H_{1}(M)$ has at least a $\mathbb{Z}$ component. In particular the map $f_{*}$ can be defined so that,
$f_{*}:H_{1}(M)\rightarrow H_{1}(S^1)=\mathbb{Z}$.
Now we can look at an inverse image of a point $a\in\mathbb{Z}$; that is $f^{-1}(a)$ is a surface and in particular we have defined an element in $H^{1}(M)$. By duality this gives an element in $H_{2}(M)$ which is non-zero and hence non-separating. I have left out some details, let me know if you need them and I'll fill them in.


text:
\begin{document}

\title{Thresholds for families of multisets,\\ with an application to graph pebbling}
\author{
Airat Bekmetjev\thanks{
Department of Mathematics,
Arizona State University,
Tempe, Arizona USA 85287-1804
(email: bekmetje@mathpost.la.asu.edu)}~\\

Graham Brightwell\thanks{
Department of Mathematics,
London School of Economics,
London, England WC2A 2AE
(email: g.r.brightwell@lse.ac.uk)}~\\

Andrzej Czygrinow\thanks{
Department of Mathematics,
Arizona State University,
Tempe, Arizona USA 85287-1804
(email: andrzej@math.la.asu.edu)}~\\

and\\

Glenn Hurlbert\thanks{
Department of Mathematics,
Arizona State University,
Tempe, Arizona USA 85287-1804
(email: hurlbert@math.la.asu.edu)}~\\
}

\maketitle

\newpage

\begin{abstract}
\noindent
In this paper we prove two multiset analogs of classical results.
We prove a multiset analog of Lov\' asz's version of the Kruskal-Katona Theorem
and an analog of the Bollob\'as-Thomason threshold result. As a corollary we
obtain the existence of pebbling thresholds for
arbitrary graph sequences. In addition, we improve both the lower and upper
bounds for the `random pebbling' threshold of the sequence of paths.
\vspace{0.2 in}

\noindent
{\bf 1991 AMS Subject Classification:}
05D05, 05C35, 05A20
\vspace{0.2 in}

\noindent
{\bf Key words:}
Pebbling number, threshold, multiset lattice, shadow
\vspace{0.8 in}
\end{abstract}

\newpage

\section{Introduction}\label{Intro}
Throughout this paper $G$ will denote a simple connected graph, and
$n=n(G)$ will denote the number of its vertices.
The vertex set of $G$ will be the set $[n]=\{1,2,\ldots,n\}$.

\subsection{Pebbling}\label{Pebbling}
Suppose $t$ pebbles are distributed onto the vertices of a graph $G$.
A pebbling step $[v,v\pr]$ consists of removing two pebbles from one vertex $v$
and then placing one pebble at an adjacent vertex $v\pr$.
We say a pebble can be {\it moved} to a vertex $z$, the {\it root} vertex,
if we can repeatedly apply pebbling steps so that in the resulting
distribution $z$ has at least one pebble.

For a graph $G$, a distribution $D$ of pebbles onto the vertices of $G$, and a
`root' vertex $z$, we say that $D$ is {\it $z$-solvable} if it is possible to
move a pebble to $z$; otherwise, $D$ is $z$-{\it unsolvable}.
Also $D$ is {\it solvable} if it is $z$-solvable for all $z$, and
{\it unsolvable} otherwise.

The {\it pebbling number} $pn(G)$ is the smallest integer $t$ such that
{\it all} distributions of $t$ pebbles to the vertices of $G$ are solvable.
In this paper we are concerned instead with the minimum $t$ such that
{\it almost all} distributions of $t$ pebbles to the vertices of $G$ are
solvable.
The interested reader is encouraged to read \cite{Hur} for the history of
and the many results on graph pebbling.

\subsection{Random Distributions}\label{RandomDists}

In this paper we are interested in the probabilistic pebbling model, in which
the pebbling distribution is selected uniformly at random from the set of all
distributions with a prescribed number $t$ of pebbles (we emphasize that the
pebbles are unlabeled and the vertices are labeled).  This is certainly not the
only possible random pebbling model; for instance one could consider the model
obtained by placing each of the pebbles uniformly at random on a vertex of $G$
-- this model will exhibit very different behavior.

We will study thresholds for the number $t$ of pebbles so that if
$t$ is essentially larger than the threshold, then a random
distribution is almost surely solvable, and if $t$ is essentially
smaller than the threshold, then a random distribution is almost surely
unsolvable.
Formally, our notion of a pebbling threshold is defined as follows.
Let $\bN$ denote the set of nonnegative integers, and let
$D_n:[n]\rar \bN$ denote a distribution of pebbles on $n$ vertices.
For a particular function $t = t(n)$, we consider the probability space
$\cD_{n,t}$ of all distributions $D_n$ of {\it size} $t$, i.e.\ with
$t=\sum_{i\in[n]}D_n(i)$ pebbles, with each such distribution being equally
likely.
Given a graph sequence $\cG=(G_1,\ldots,G_n,\ldots)$, where $G_n$ has vertex
set $[n]$, denote by $P_\cG(n,t)$ the probability that an element of
$\cD_{n,t}$ chosen uniformly at random is $G_n$-solvable.
We call a function $t=t(n)$ a {\it threshold} for $\cG$, and write
$t\in th(\cG)$, if the following two statements hold for every sequence
$\w=\w(n)$ tending to infinity (we write $\w\gg 1$):
({\it i})~$P_\cG(n,t\w)\rar 1$ as $n\rar\inf$, and
({\it ii})~$P_\cG(n,t/\w)\rar 0$ as $n\rar\inf$.
(Here and elsewhere, if $t\w$ and
$t/\w$ are not integers, they should be interpreted as taking on the nearest
integer value.)
Of course, the definition mimics the important threshold concept in random
graph theory. Unlike the situation in random graphs, however, it did not seem
obvious that even ``natural'' families of graphs have pebbling thresholds,
although the existence of a threshold for any graph sequence is conjectured
in \cite{Hur}.
The random pebbling model is also studied in \cite{CzyEHK}, where the following result
is proved.

\begin{theorem}\label{gen}
For any $\e > 0$ and any graph sequence $\cG=(G_1,\ldots,G_n,\ldots)$, where
$V(G_n)=[n]$ for each $n$, $th(\cG)\sub \Omega(\sn)\, \cap\ o(n^{1+\e})$.
\end{theorem}

In other words, {\it if} there is a threshold function $t(n)$ for a graph
sequence, then $t(n)$ cannot be essentially smaller than $\sn$ (the threshold
function for the family of complete graphs) or as large as $n^{1+\e}$.
Our results in this paper serve to improve the upper bound.

Better bounds were obtained in~\cite{CzyEHK} for graphs satisfying various
diameter and connectivity conditions, and threshold functions were found
for the classes of stars and wheels.
Also in \cite{CzyEHK}, bounds were found for the classes of paths and cycles.

\begin{theorem}\label{paths}
\begin{description}
\item {\bf (a)}
For the sequence of paths $\cP=(P_1,P_2,\ldots,P_n,\ldots)$,
we have $th(\cP)\sub \W(n)\cap o(n^{1+\e})$ for every $\e>0$.
\item {\bf (b)}
For the sequence of cycles $\cC=(C_1,C_2,\ldots,C_n,\ldots)$,
we have $th(\cC)\sub$ $\W(n)\cap$ $o(n^{1+\e})$ for every $\e>0$.
\end{description}
\end{theorem}

Our purpose in this paper is firstly to show that every graph sequence does
have a threshold, and secondly to prove much tighter bounds for the threshold
functions of classes of paths and cycles.

\begin{theorem}
\label{SeqThresh}
Let $\cG=(G_1,\ldots,G_n,\ldots)$ be any graph sequence,
and define $t=t(n)=\min\{r \mid P_\cG(n,r)\ge 1/2\}$.
Then $t\in th(\cG)$.
\end{theorem}

\begin{theorem}\label{Thpaths}
For the sequence of paths $\cP=(P_1,\ldots,P_n,\ldots)$ we have
\begin{description}
\item{\bf (a)} $th(\cP)\sub\Omega(n2^{c\sln})$, where $c$ is any
constant less than $1/\sq$;
\item{\bf (b)} $th(\cP)\sub O(n2^{2\sln})$.
\end{description}
\end{theorem}

Here and throughout, $\lg$ denotes the logarithm to base~2.
Our proofs apply equally well to the sequence of cycles
$\cC=(C_1,\ldots,C_n,\ldots)$.

In fact, Theorem \ref{SeqThresh} follows from a very general result about
thresholds in random multiset models.  For a natural number $n$, let
$\cM_n$ denote the partially ordered set ({\it poset}) of all multisets
of $[n]$, ordered by inclusion.  For $\cF_n$ a subfamily of $\cM_n$, and $t$ a
natural number, let $\cF_n(t)$ denote the family of $t$-element multisets in
$\cF_n$.  If $\cF_n\sub \cM_n$,
the family $\cF_n$ is said to be {\it increasing} if $E\sup F\in\cF_n$
implies $E\in\cF_n$, and {\it decreasing} if $E\sub F\in\cF_n$ implies
$E\in\cF_n$.

The size of $\cM_n(t)$ is ${n \pebb t} = {n+t-1 \choose t}$, and therefore
$P_t(\cF_n(t)) \equiv |\cF_n(t)|/{n\pebb t}$ is the probability that a
uniformly randomly chosen $t$-multiset of $[n]$ is in the family $\cF_n$.
We say that $t=t(n)$ is a {\it threshold} for a sequence
$(\cF_1,\ldots,\cF_n,\ldots)$ of increasing families of multisets if,
for any function $\w=\w(n)\gg 1$, we have $P_{t\w}(\cF_n(t\w))\rar 1$ and
$P_{t/\w}(\cF_n(t/\w))\rar 0$.

\begin{theorem}\label{threxist}
Let $\cF = (\cF_1,\dots,\cF_n,\ldots)$ be a sequence of increasing families,
with $\cF_n \subseteq \cM_n$ for each $n$.
Define $t = t(n) = \min \{ r \mid P_r(\cF_n(r)) \ge 1/2\}$.
Then $t \in th(\cF)$.
\end{theorem}

Theorem~\ref{threxist} is an analog of a result of Bollob\'as and
Thomason~\cite{BolTho}, stating that any sequence of increasing families
of the {\it subset lattice} has a threshold function.

One can view a particular distribution of $t$ pebbles to $n$ vertices as
a particular multiset of $t$ elements from the ground set $[n]$.
Thus the set of all solvable distributions for a particular graph on $n$
vertices corresponds to a family of multisets on $[n]$.
Since the set of all solvable distributions for a particular graph
has the increasing property, Theorem \ref{SeqThresh} is an immediate
consequence of Theorem \ref{threxist}.

In our proof of Theorem~\ref{threxist}, the crucial tool will be the following
1969 result of Clements and Lindstr\"om, extending an earlier result
of Macauley~\cite{Mac}, which is the multiset analog of the
celebrated Kruskal-Katona Theorem~\cite{Fra,Kat,Kru} for the subset lattice.

Given any subfamily $\cA\sub \cM_n(t)$, we define its {\it shadow}
$\sh\cA=\{C\in \cM_n(\t) \mid C\subset A\mbox{ for some } A \in\cA \}$, and set
$\sh^{i+1}\cA=\sh\sh^i\cA$.

For a multiset $A \in {\cal M}_n(t)$, and $i\in [n]$, let $A(i)$ denote
the multiplicity of $i$ in $A$.
The {\em colexicographic order} on ${\cal M}_n(t)$ is defined by setting
$A<B$ if $A\not=B$ and, for some $i \in [n]$, $A(i) < B(i)$ while
$A(j)=B(j)$ for $j>i$.

\begin{theorem} (Clements-Lindstr\"om)\label{CL}
Suppose that $\cF$ is a subset of $\cM_n(t)$, and that $\cG$ consists of the
first $|\cF|$ elements of $\cM_n(t)$ in colexicographic order.  Then, for any
$k \ge 1$,
$$
|\partial^k \cF| \ge |\partial^k \cG|.
$$
\end{theorem}

In other words, the size of the shadow (at any level) of a subset of $\cM_n(t)$
is minimized by taking an initial segment of the colexicographic order on
$\cM_n(t)$.

In 1979, Lov\'asz proved a version of the Kruskal-Katona theorem which was
used by Bollob\'as and Thomason~\cite{BolTho} to prove the existence of
threshold functions.
An analogous version of the Clements-Lindstr\"om theorem was
conjectured in \cite{Hur}.  We prove this conjecture in the next section.

For $x$ a non-negative real number, let ${x\pebb t}=(x)(x+1)\cdots (x+\t)/t!$.
(Note that this coincides with our earlier definition if $x$ is a natural
number.)

\begin{theorem}\label{lov}
Suppose that $\cA\sub\cM_n(t)$ and define $x$ by $|\cA|={x\pebb t}$.
Then $|\sh\cA |\ge {x\pebb\t}$.
\end{theorem}

For the case in which $\cA = {m \pebb t}$ for $m$ a natural number, the first
$|\cA|$ elements of $\cM_n(t)$ in colexicographic order are the $t$-multisets
of $\{1,\dots, m\}$.  The shadow of the family consisting of these
multisets is the family of $(\t)$-multisets of $\{1,\dots,m\}$, of size
${x \pebb \t}$, so Theorem~\ref{lov} is equivalent to Theorem~\ref{CL} in this
case.  For families of intermediate sizes, Theorem~\ref{lov} is a ``smoothed''
version of Theorem~\ref{CL}.

The rest of this paper is organized as follows. In Section \ref{Sets} we prove
Theorem \ref{lov} (Section \ref{Lsec}) and Theorem \ref{threxist}
(Section \ref{ExSec}).
Section \ref{PathThresh} is devoted to a proof of Theorem \ref{Thpaths}.

\section{Set Theory}\label{Sets}
In this section, we prove the two results concerning the multiset lattice.
First, verifying a conjecture from \cite{Hur}, we prove
our multiset analog of Lov\'asz's version of the Kruskal-Katona theorem.
Second, we establish our multiset analog of the
Bollob\'as-Thomason threshold theorem \cite{BolTho}.  As an immediate corollary
we obtain the existence of the pebbling threshold for any graph sequence.

\subsection{Multiset analog of Lov\'asz's Theorem}\label{Lsec}

Let $[n]\pebb t$ denote the family of $t$-element multisets of $[n]$,
and as before let ${n\pebb t} = {n+t-1 \choose t}$ denote its cardinality.
(For convenience in reading, the reader may enjoy using the terminology
``$n$ {\it pebble} $t$''.)
Also as before, let $x\pebb t$ denote the polynomial evaluation of
$n\pebb t$ for any real number $x$; that is,
$${x\pebb t}=(x)(x+1)\cdots (x+\t)/t!.$$

Let $\cA\sub {[n]\pebb t}$, and for any $A\in\cA$ and $i\in [n]$,
let $A(i)$ denote the multiplicity of $i$ in $A$.
We adopt the convention of writing an element of a multiset just once, with
its multiplicity written as an exponent; for example $\{1^j\}$ denotes the
multiset of $j$ ones. Also, for any multisubset $I$ of $[n]$ we set
$\cA-I=\{A-I\ |\ A\in\cA\}$.

In the proof of Theorem \ref{lov}, we make use of various different partitions
of a family $\cA\sub {[n] \pebb t}$.  For $0\le j\le t$, define the sets
$\cA_j=\{A\in\cA\ |\ A(1)=j\}$, forming a partition of $\cA$.
If $\cA ={[n]\pebb t}$, this partition gives rise to the relation
\medskip
\noindent
$${n\pebb t}\ =\ \sum_{j=0}^t\ {n-1\pebb j}\ ,$$
which has the polynomial equivalent
\begin{equation}\label{partn}
{x\pebb t}\ =\ \sum_{j=0}^t\ {x-1\pebb j}\ .
\end{equation}

For each $i\in [n]$, define the sets
$\cA^i=\{A\in\cA\ |\ A(i)>0 {\rm\ and\ } A(j)=0 {\rm\ for\ all\ } j<i\}$,
forming a second partition of $\cA$.
More important for us is that the sets $\cA_1,\ldots,\cA_t$ partition $\cA^1$.

A third partition of $\cA$ is given by $\cA =\cA^1\cup \cA_0$,
which in the case that $\cA ={[n]\pebb t}$ gives rise to the relation
$${n\pebb t}\ =\ {n\pebb\t}\ +\ {n-1\pebb t}\ ,$$
having the polynomial equivalent
\begin{equation}\label{split}
{x\pebb t}\ =\ {x\pebb\t}\ +\ {x-1\pebb t}\ .
\end{equation}

Given a family $\cA \sub \cM_n(t)$, and indices $i,j$ with
$1\le i<j\le n$, a {\it compression} of $\cA$ is obtained by taking
each member $A$ of $\cA$ such that $A(j)\ge 1$ and $A-\{j\}+\{i\} \notin \cA$,
and replacing it by $A-\{j\}+\{i\}$.

A family $\cA$ is said to be {\it compressed} if, for all $1\le i<j\le n$,
we have $A-\{j\}+\{i\}\in\cA$ whenever $A\in\cA$, i.e., $\cA$ is unchanged by
any compression.  Note that any family can be transformed into a compressed
one by a sequence of compressions.  Note also that initial segments of the
colexicographic order are compressed families, but that these are not the only
ones.

If $\cA$ is compressed and $C\in\sh\cA$, then $C=A-\{i\}$ for some
$A\in\cA$, $i\in [n]$.  Because $\cA$ is compressed, the set
$E=A-\{i\}+\{1\}$ is in $\cA$.  Since $C=E-\{1\}$, we see that
$\sh\cA\sub\cA^1-\{1\}$, which implies that
$$|\sh\cA |\lt |\cA^1|\ .$$
On the other hand, we know that $\cA^1-\{1\}\sub\sh\cA^1\sub\sh\cA$, and so
$$|\cA^1|\lt |\sh\cA |\ .$$
These two facts together imply the following lemma.

\begin{lemma}\label{f1}
Let $\cA\sub\cM_n(t)$ and suppose that $\cA$ is a compressed family.
Then $|\sh\cA |=|\cA^1|$.
\hfill$\pf$
\end{lemma}

The following lemma is proved by Clements in \cite{Cle}.

\begin{lemma}\label{comp}
Suppose that $\cA\sub\cM_n(t)$ and let $q(\cA)$ be a compression
of $\cA$.  Then $|\sh\cA|\ge |\sh q(\cA)|$.
\hfill$\pf$
\end{lemma}

With these tools we now can prove Theorem \ref{lov}.

\medskip
\noindent
{\it Proof of Theorem \ref{lov}.}
We use induction on $n$. Because of Lemma \ref{comp} we may assume that
$\cA$ is compressed.
If $|\cA^1|\ge {x\pebb\t}$ then we are done because of Lemma \ref{f1}.
So we will assume that $|\cA^1|<{x\pebb\t}$ and argue to a contradiction.

\vspace{0.2 in}
\noindent
{\bf Claim\ }
For each $0\le j\le t$ we have $|\cA_j|\ge {x-1\pebb t-j}$.
\vspace{0.2 in}

The truth of this claim yields the following contradiction.
Because the families $\cA_1,\ldots,\cA_t$ partition the family $\cA^1$, we have
$$|\cA^1|\
	=\ \sum_{j=1}^t\ |\cA_j|\
	\ge\ \sum_{j=1}^t\ {x-1\pebb t-j}\
	=\ \sum_{k=0}^{\t}\ {x-1\pebb k}\
	=\ {x\pebb\t}\ ,$$
using equation (\ref{partn}).
Thus we need only to prove the claim.

Induction on $j$ shows that $|\sh^j\cA_0|\ge {x-1\pebb t-j}$.
Indeed, for $j=0$ we know from equation (\ref{split}) that
$|\cA_0|>{x-1\pebb t}$.
Also, $\sh^j\cA_0$ is a family of $(t-j)$-multisets of the set $\{2,\ldots,n\}$
of size $n-1$, and so if $|\sh^j\cA_0|\ge {x-1\pebb t-j}$, then
$|\sh^{j+1}\cA_0|\ge {x-1\pebb t-j-1}$ (by induction on $n$ for the theorem).

Now, if $C\in\sh^j\cA_0$ then $C=A-I$ for some $A\in\cA_0$ and some
submultiset $I$ of $A$ of size $j$.  Because $\cA$ is compressed, the set
$E=A-I+\{1^j\}$ is in $\cA$, and in particular is in $\cA_j$.
Since $C=E-\{1^j\}$ we see that $\sh^j\cA_0\sub\cA_j-\{1^j\}$, which
implies that
$$|\cA_j|\
	=\ |\cA_j-\{1^j\}|\
	\ge\ |\sh^j\cA_0|\
	\ge\ {x-1\pebb t-j}\ .$$
This proves the claim, and the theorem follows.
\hfill$\pf$
\medskip

\subsection{Thresholds}\label{Thresholds}\label{ExSec}
The main result of this section is the analog of the Bollob\'as-Thomason
threshold theorem.

\medskip
\noindent
{\it Proof of Theorem \ref{threxist}.} We consider the two ``reference''
families:
$$
\begin{array} {rcl}
\cM_n(r;b) &=& \{ A \in \cM_n(r) \mid A(n) < b\} \quad (1\le b \le r), \\
\cN_n(r;b) &=& \{ A \in \cM_n(r) \mid A(n-b+1) = \cdots = A(n) =0 \} \\
&& (1\le b \le n-1).
\end{array}
$$
Note that each family $\cM_n(r;b)$ and $\cN_n(r;b)$ is an initial segment
of the colexicographic order on $\cM_n(r)$, and that, for any $k\ge 1$,
$$
\partial^k \cM_n(r;b) = \cM_n(r-k;b)\ ; \qquad \partial^k \cN_n(r;b)
= \cN_n(r-k;b)\ .
$$
We use these families, rather than general initial segments of the
colexicographic order, since their sizes are a little easier to estimate.
Our strategy is, for each $r$, to compare
$\overline{\cF_n(r)}=\cM_n(r)-\cF_n(r)$
with an appropriate member of one of these reference families,
at levels $r$ near $t$, somewhat above $t$, and somewhat below $t$.

First, we need some estimates on the probabilities of the reference families,
which we shall use repeatedly.  For any positive integers $n$, $r$ and $b$
with $b\le r$,
$$
|\cM_n(r;b)| = |\cM_n(r)| - |\cM_n(r-b)| = {n \pebb r} - {n \pebb r-b}\ ,
$$
and so
$$
\begin{array} {rcl}
P_r(\cM_n(r;b)) &=& 1 - \frac{(n+r-b-1)!r!}{(n+r-1)!(r-b)!} \\
&=& 1 - \left( \frac{r}{n+r-1}\right) \left(\frac{r-1}{n+r-2}\right) \cdots
\left(\frac{r-b+1}{n+r-b}\right).
\end{array}
$$
We derive the lower bounds
$$
\begin{array} {rcl}
P_r(\cM_n(r;b)) &\ge& 1 - \left(\frac{r}{n+r-1}\right)^b \\
&=& 1 - \left( 1 - \frac{n-1}{n+r-1}\right)^b \\
&\ge& 1 - \exp( -b(n-1)/(n+r-1))\ ,
\end{array}
$$
and the upper bounds
$$
\begin{array} {rcl}
P_r(\cM_n(r;b)) &\le& 1 - \left(\frac{r-b+1}{n+r-b}\right)^b \\
&=& 1 - \left( 1 + \frac{n-1}{r-b+1}\right)^{-b} \\
&\le& 1 - \exp( -b(n-1)/(r-b+1))\ .
\end{array}
$$

Similarly we see that, for positive integers $n$, $r$ and $b$ with $b\le n-1$,
$|\cN_n(r;b)| = |\cM_{n-b}(r)| = {n-b \pebb r}$, and so
$$
\begin{array} {rcl}
P_r(\cN_n(r;b)) &=& \frac{(n-b+r-1)!(n-1)!}{(n-b-1)!(n+r-1)!} \\
&=& \left( \frac{n-1}{n+r-1}\right) \cdots \left(\frac{n-b}{n-b+r}\right).
\end{array}
$$
This gives the bounds
$$
\begin{array} {rcl}
P_r(\cN_n(r;b)) &\ge& \left(\frac{n-b}{n-b+r}\right)^b \\
&=& \left( 1 + \frac{r}{n-b} \right)^{-b} \ge \exp(-rb/(n-b))\ ; \\
&&\\
P_r(\cN_n(r;b)) &\le& \left(\frac{n-1}{n+r-1}\right)^b \\
&=& \left( 1 - \frac{r}{n+r-1} \right)^b \le \exp(-rb/(n+r-1))\ .
\end{array}
$$

\bigskip

Recall that $t=t(n)$ is defined as the least integer such that
$P_t(\cF_n(t)) \ge 1/2$.
Let $\w=\w(n)$ be any function tending to infinity with $n$ such that
$t(n)/\w(n)$ takes integer values.  We shall show that
$P_{t/\w}(\cF_n(t/\w))\to 0$ as $n\to \infty$, or equivalently that
$P_{t/\w}(\overline{\cF_n(t/\w)}) \to 1$.
We may assume without loss of generality that $n\ge 3$ and $\w \ge 30$,
and so $t \ge 30$.

We fix $n$ for the moment and consider two cases.

\medskip

\noindent (1) \quad
Suppose that $t = t(n) \ge 2n-1$.

In this case, we set $b = \left \lfloor \frac{t}{2n-1}\right \rfloor$.  Note
that our assumption on $t$ ensures that $b\ge 1$, and that our choice of $b$
ensures that $b(n-1)/(t-b) \le 1/2$.  Now we have
$$
\begin{array}{rcl}
P_{t-1}(\cM_n(t-1;b)) &\le& 1 - \exp(-b(n-1)/(t-b)) \\
&\le& 1- e^{-1/2} \\
&<& 1/2 \\
&<& P_{t-1}(\overline{\cF_n(t-1)})\ .
\end{array}
$$
Then, since $\overline{\cF_n}$ is decreasing and $\cM_n(t-1;b)$ is an initial
segment of the colexicographic order, the Clements-Lindstr\"om Theorem implies
that
$$
\begin{array} {rcl}
P_{t/\w}(\overline{\cF_n(t/\w)}) &\ge&
P_{t/\w}(\partial^{t-1-t/\w}\overline{\cF_n(t-1)}) \\
&\ge& P_{t/\w}(\partial^{t-1-t/\w}\cM_n(t-1;b)) \\
&=& P_{t/\w}(\cM_n(t/\w;b)) \\
&\ge& 1 - \left( \frac{t/\w}{n+t/\w-1} \right)^b.
\end{array}
$$
If $n-1 \ge \frac{t}{\sqrt \w}$, then this gives
$P_{t/\w}(\overline{\cF_n(t/\w)}) \ge 1 - \frac{1}{\sqrt \w + 1}$.
On the other hand, if $n-1\le \frac{t}{\sqrt \w} \le \frac{t}{5}$, then
$\frac{t}{2n-1} \ge \frac{5n-5}{2n-1} \ge 2$, so
$b \ge \frac{1}{2}\frac{t}{2n-1} \ge \frac{t}{5(n-1)} \ge \sqrt \w/5$, so
$$
\begin{array}{rcl}
P_{t/\w}(\overline{\cF_n(t/\w)}) &\ge&
1 - \left( \frac{t/\w}{t/5b+t/\w} \right)^b \\
&=& 1 - \left( 1 - \frac{\w}{\w+5b}\right)^b \\
&\ge& 1 - \exp(-b\w/(\w+5b)) \\
&\ge& 1 - \exp(\sqrt \w / 10)\ .
\end{array}
$$

\medskip

\noindent (2) \quad
Now suppose that $t=t(n) \le 2n-2$.

This time we set $b=\left\lceil \frac{n+t-2}{t-1} \right\rceil$, and use
exactly the same method as in (1), but this time comparing with $\cN_n(t-1;b)$.
Indeed
$$
\begin{array}{rcl}
P_{t-1}(\cN_n(t-1;b)) &\le& \exp(-(t-1)b/(n+t-2)) \\
&\le& e^{-1} \\
&<& 1/2 \\
&<& P_{t-1} (\overline{\cF_n(t-1)})\ .
\end{array}
$$
As before we deduce that
$$
P_{t/\w}(\overline{\cF_n(t/\w)}) \ge P_{t/\w}(\cN_n(t/\w;b)) \ge
\exp(-tb/\w(n-b))\ .
$$
Now observe that $b \le 5n/t$, and so
$P_{t/\w}(\overline{\cF_n(t/\w)}) \ge \exp(-6/\w)$.

\medskip

Summarizing, we see that
$$
P_{t/\w}(\overline{\cF_n(t/\w)}) \ge \min\left\{1 - \frac{1}{\sqrt {\w(n)}+1},
1 - \exp(-\sqrt {\w(n)}/10),\exp(-6/\w(n)) \right\},
$$
so $P_{t/\w}(\overline{\cF_n(t/\w)}) \to 1$ as $n\to \infty$.

\bigskip

Now let $\w(n) \to \infty$ be such that $t(n)\w(n)$ takes integer values; we
claim that $P_{t\w}(\overline{\cF_n(t\w)}) \to 0$ as $n\to \infty$.  We may
assume that $n\ge 2$ and $\w(n)\ge 36$.

As before, we fix $n$ for the moment and consider two cases.

\medskip

\noindent (1) \quad
Suppose $t = t(n) \ge n/2$. In this case, we set
$b = \left\lceil \frac{n+t-1}{n-1}\right\rceil$, and note that
$b = 1 + \lceil t/(n-1) \rceil \le \frac{2t}{n-1} + \frac{2t}{n-1} = 4t/(n-1)$
and $b-1\le t\w/2$.
Observe that
\begin{eqnarray*}
P_t(\cM_n(t;b)) & \ge & 1 - \exp(-b(n-1)/(n+t-1)) \\
	& \ge & 1 - e^{-1} \\
	& > & 1/2 \\
	& \ge & P_t(\overline{\cF_n(t)}).
\end{eqnarray*}
This implies that
$P_{t\w}(\overline{\cF_n(t\w)}) \le P_{t\w}(\cM_n(t\w;b))$, since otherwise we
would have
$$
\left|\overline{\cF_n(t)}\right| \ge
\left|\partial^{t\w-t}\overline{\cF_n(t\w)}\right| >
\left|\partial^{t\w-t}\cM_n(t\w;b)\right| =
\left|\cM_n(t;b)\right|.
$$
Therefore we see that
$$
\begin{array}{rcl}
P_{t\w}(\overline{\cF_n(t\w)}) &\le& 1 - \exp(-b(n-1)/(t\w-b+1)) \\
&\le& 1 - \exp(-4t/(t\w/2)) \\
&=& 1 - \exp(-8/\w)\ .
\end{array}
$$

\medskip

\noindent (2) \quad
Now suppose $t \le (n-1)/2$.  Here we set
$b = \left\lfloor \frac{n}{2t+1} \right\rfloor \ge 1$, and observe that
$tb/(n-b) \le 1/2$.
We see that
\begin{eqnarray*}
P_t(\cN_n(t;b)) & \ge & \exp(-tb/(n-b)) \\
	& \ge & e^{-1/2} \\
	& > & 1/2 \\
	& \ge & P_t(\overline{\cF_n(t)})\ ,
\end{eqnarray*}
which, as before, implies that
$$
P_{t\w}(\overline{\cF_n(t\w)}) \le P_{t\w}(\cN_n(t\w;b)) \le
\left(\frac{n-1}{n+t\w-1}\right)^b.
$$

If $n-1 \le t\sqrt \w$, this yields
$P_{t\w}(\overline{\cF_n(t\w)}) \le 1/(1+\sqrt \w)$.  On the other hand, if
$n-1 \ge t\sqrt \w$, then
$\frac{n}{2t+1} \ge \frac{n-1}{3t} \ge 2$, so
$b \ge \frac{n-1}{6t} \ge \frac{\sqrt \w}{6}$, and
$$
\begin{array} {rcl}
P_{t\w}(\overline{\cF_n(t\w)}) &\le& \left( \frac{6tb}{6tb + t\w} \right)^b \\
&=& \left( 1 - \frac{\w}{6b+\w} \right)^b \\
&\le& \exp(-\w b/(6b+\w)) \\
&\le& \exp(-\sqrt \w / 12)\ .
\end{array}
$$

Combining all the cases gives
$$
P_{t\w}(\overline{\cF_n(t\w)}) \le \max \left\{
1- \exp(8/\w(n)), \frac{1}{1+\sqrt{\w(n)}}, \exp( -\sqrt {\w(n)}/12)
\right\},
$$
so $P_{t\w}(\overline{\cF_n(t\w)}) \to 0$ as $n\to \infty$.

This completes the proof.
\hfill$\pf$
\medskip

\section{The Threshold for Paths}\label{PathThresh}
For convenience we will assume that all logarithms and roots
take on the value of their nearest integer.
Let $P_n$ be the path on $n$ vertices, $c$ be any constant less than $1/\sq$,
$u=c\sln$, $t=n2^u$, and $p=(1+\e)2^u \ln n$, for some $\e>0$.
In addition, let $D_i$ be the random variable
which is the number of pebbles on vertex $i$ when a random
distribution of $t$ pebbles is selected, and let $S_i$ denote the
event that $D_i\le p$ and $T_i=\neg S_i$.
Finally, we will also need the following random variables
\begin{equation}\label{y+}
Y_i^+=\sum_{l=i}^n{D_l\over 2^{l-i}}
\end{equation}
and
\begin{equation}\label{y-}
Y_i^-=\sum_{l=1}^i{D_l\over 2^{i-l}}\ .
\end{equation}

\begin{lemma}\label{union}
Let $p,t,n,u$ be as above.
Then $\Pr [T_1\cup T_2\cup\cdots\cup T_n]\rar 0$.
\end{lemma}

\noindent
{\it Proof.}
For $1\le i\le n$, we have
$$\Pr [T_i]
	={{n\pebb t-p}\over {n\pebb t}}
	={(t-p+1)\cdots (t)\over (t+n-p)\cdots (t+n-1)}$$
$$\le\left({t\over t+n}\right)^p
	\le e^{-np/(t+n)}\ .$$
Therefore,
$$\Pr [T_1\cup\cdots\cup T_n]\le ne^{-p/(2^u+1)}=
\exp\left( \ln n \left( 1- {2^u \over 2^u+1}(1+\e) \right) \right) \rar 0.$$
\hfill$\pf$
\medskip

Note that the role of $u$ is not important in the above lemma.
However, we stated the lemma as such because of its use in the proof of
Theorem \ref{Thpaths}.

For the next lemma, we will need $m=\stln$, and $k=\lf n/m\rf$.
Partition $P_n$ into consecutively disjoint paths (blocks)
$B_1,\ldots,B_k$ of lengths $m$ or $m+1$.
For a randomly chosen distribution of $t$ pebbles on $P_n$ we denote by
$E_i$ the event that block $B_i$ contains no pebbles (is empty), and set
$F_i=\neg E_i$.

\begin{lemma}\label{mainlower}
Let $m,k$ be as above and let $s=s(n)$ be such that $n\gg ms^me^{m/s}$.
If $t=ns$ then $\Pr [F_1\cap\cdots\cap F_k]\rar 0$.
\end{lemma}

\noindent
{\it Proof.}
We will apply the second moment method.
Let $X_i$ be the indicator variable of $E_i$ and let $X=\sum_{i=1}^k X_i$.
We have
$$\Pr(X=0)\le{\sigma^2(X)\over (\bE(X))^2}$$
and
\begin{eqnarray*}
\sigma^2(X)&=&\bE (X^2)-(\bE(X))^2\\
&&\\
&=&\sum_{i,j}\bE (X_iX_j)-\sum_{i,j}\bE (X_i)\bE (X_j)\\
&&\\
&\le&\sum_i\bE (X_i^2)\ ,
\end{eqnarray*}
where the last inequality follows from the fact that
$\bE (X_iX_j)\le\bE (X_i)\bE (X_j)$ for $i\ne j$.
Therefore,
$$\sigma^2(X)\le\sum_i\bE (X_i^2)=\sum_i\bE (X_i)=\bE (X)\ .$$
We also have
\begin{eqnarray*}
\bE(X)&=&\left({n\over m}\right){{t+n-m-1\choose t}\over {t+n-1\choose t}}\\
&&\\
&\ge&\left({n\over m}\right)\left({n-m\over t+n-m}\right)^m\\
&&\\
&\sim&\left({n\over ms^m}\right)e^{-m^2/n -m/s}\\
&&\\
&\rar&\inf\ .
\end{eqnarray*}
Thus
$\Pr[X=0]\rar 0.$
\hfill$\pf$

\medskip
\noindent
{\it Proof of Theorem \ref{Thpaths} (a).}
We first remark that it is easy to check that $s=2^u$ satisfies
hypothesis of Lemma \ref{mainlower}.
Next, for each block $B=[i,j]$, let $Y_B^-=Y_i^-$ and $Y_B^+=Y_j^+$.
Then Lemma \ref{union} and Lemma \ref{mainlower} imply that with probability
tending to one there is a block $B$ of length $m$ which is empty and such
that both $Y_B^-$ and $Y_B^+$ are less than or equal to $(1+\e)2^u \ln n $.
Since $(1+\e)2^u \ln n <2^{m/2}$ for large enough $n$,
there is a vertex of $B$, namely the center vertex,
to which it is not possible to pebble using $Y_B^-$ and $Y_B^+$.
\hfill$\pf$
\medskip

We also shall prove that $th(P_n) \subseteq O(n2^{2\sln})$.
The argument is a modification of an idea from \cite{CzyEHK}.
We will use the fact \cite{CzyEHK} that any distribution of at least $2^m$
pebbles on a connected graph of $m+1$ vertices is solvable.

\medskip
\noindent
{\it Proof of Theorem \ref{Thpaths} (b).}
Let $m=\sln$, $k=\lf n/m\rf$, $s=2^{2m+2}$, $t=ns$, and
partition $P_n$ into consecutively disjoint paths (blocks)
$B_1,\ldots,B_k$, each with $m$ or $m+1$ vertices.
Let $Z_i$ denote the event that the $i$th block contains less than
$2^m$ pebbles.
We will show that $\Pr [Z_1\cup\cdots\cup Z_k]\rar 0$, which, by the remark
preceding the proof, implies the result.

We have that
$$\Pr [Z_1\cup\cdots\cup Z_k]
	\le k\sum_{i=0}^{2^m-1}
	{{i+m-1\choose i}{t+n-m-i-1\choose t-i}\over {t+n-1\choose t}}\ .$$
Since
${t+n-m-i-1\choose t-i}
	\le\left({t\over t+n-m-1}\right)^i{t+n-m-1\choose t}
	\le {t+n-m-1\choose t}
	\le\left({n\over n+t}\right)^m {t+n-1\choose t}$, we have
\begin{equation}\label{eq5}
{t+n-m-i-1\choose t-i}
	\le\left({n\over n+t}\right)^m{t+n-1\choose t}\ .
\end{equation}
For $0\le i < 2^m$, we have
\begin{equation}\label{eq6}
{i+m-1\choose i}\le 2^m2^{m^2}\ .
\end{equation}
Using (\ref{eq5}) and (\ref{eq6}), we see that
$$\Pr [Z_1\cup\cdots\cup Z_k]
	\le k2^{2m+m^2}\left({n\over n+t}\right)^m
	\le {n\over m}\left({1\over s}\right)^m 2^{2m+m^2}
	={1\over m}\rar 0\ .$$
\hfill$\pf$
\medskip

\bibliographystyle{plain}


TITLE: Show that $\frac{\sin x}{\cos 3x}+\frac{\sin 3x}{\cos 9x}+\frac{\sin 9x}{\cos 27x} = \frac{1}{2}\left(\tan 27x-\tan x\right)$
QUESTION [8 upvotes]: Show that
$$\frac{\sin x}{\cos 3x}+\frac{\sin 3x}{\cos 9x}+\frac{\sin 9x}{\cos 27x} = \frac{1}{2}\left(\tan 27x-\tan x\right)$$

REPLY [13 votes]: A more general result is in fact true.
$$\sum_{k=0}^{n} \dfrac{\sin\left(3^k x\right)}{\cos\left(3^{k+1} x\right)} = \dfrac{\tan\left(3^{n+1} x\right) - \tan(x)}2 \,\,\,\, (\spadesuit)$$
Take $n=2$ in $(\spadesuit)$, to get what you want.

To prove $(\spadesuit)$, first note that
$$\dfrac{\sin \left(3^k \cdot x \right)}{\cos \left(3^{k+1} \cdot x \right)} = \dfrac{\tan \left( 3^{k+1} \cdot x\right) - \tan \left(3^{k} \cdot x\right)}2 \,\,\,\, (\clubsuit)$$
Now telescopic summation gives you $(\spadesuit)$.

$(\clubsuit)$ is proved by noting the fact that
\begin{align}
\tan \left( 3^{k+1} \cdot x\right) - \tan \left(3^{k} \cdot x\right) & = \dfrac{\sin \left( 3^{k+1} \cdot x\right)}{\cos \left( 3^{k+1} \cdot x\right)} - \dfrac{\sin \left( 3^{k} \cdot x\right)}{\cos \left( 3^{k} \cdot x\right)}\\
& = \dfrac{\sin \left( 3^{k+1} \cdot x\right)\cos \left( 3^{k} \cdot x\right) - \sin \left( 3^{k} \cdot x\right)\cos \left( 3^{k+1} \cdot x\right)}{\cos \left( 3^{k+1} \cdot x\right)\cos \left( 3^{k} \cdot x\right)}\\
& = \dfrac{\sin \left(2 \cdot 3^k \cdot x\right)}{\cos \left( 3^{k+1} \cdot x\right)\cos \left( 3^{k} \cdot x\right)} = \dfrac{2 \sin \left(3^k \cdot x\right) \cos \left(3^k \cdot x\right)}{\cos \left( 3^{k+1} \cdot x\right)\cos \left( 3^{k} \cdot x\right)}\\
& = 2 \cdot \dfrac{\sin \left(3^k \cdot x \right)}{\cos \left(3^{k+1} \cdot x \right)}
\end{align}

REPLY [8 votes]: Hint::
$$\frac{\sin x}{\cos 3x}=$$
$$= \frac{1}{2} \cdot \frac{2 \cdot \sin x \cdot \cos x}{\cos x \cdot \cos 3x}$$
$$= \frac{1}{2} \cdot  \frac{\sin 2x}{\cos x \cdot \cos 3x}$$
$$= \frac{1}{2} \cdot \frac{ \sin(3x - x) }{ \cos x \cdot \cos3x }$$
$$= \frac{1}{2} \cdot \frac{ \sin 3x \cdot \cos x - \cos 3x \cdot \sin x}{ \cos x \cdot \cos3x}$$
$$= \frac{1}{2} \cdot \frac {\sin 3x \cdot \cos x}{\cos x \cdot \cos 3x} - \frac{1}{2} \cdot \frac{\cos 3x \cdot \sin x}{\cos x \cdot \cos 3x}$$
$$= \frac{1}{2} \cdot \left (\frac{\sin 3x}{\cos 3x} - \frac{\sin x}{\cos x} \right )$$
$$= \frac{1}{2} \cdot  \left (\tan 3x - \tan x \right )$$
Now successively replace $x$ with $3x$ and $9x$


text:
\section{Variation of the overlap with the SNR}

\subsection{Proof of \eqref{jacPos}}

 Setting $R=R_n(t,\epsilon)$ and dropping the time index in the Gibbs-bracket we have

\begin{align*}
\frac{d\,\EE\langle Q\rangle}{dR}=n\EE\big\langle Q(\langle {\cal L}\rangle-{\cal L})\big\rangle
\end{align*}
where $\cal L$ is given by \eqref{def_L}. $R$ appears both in the numerator and partition function that define the bracket $\langle -\rangle$, thus the difference appearing. This is the same mechanism as when we derived identity \eqref{GaussIPP}. We have already shown in the previous appendix that $-\EE\langle Q{\cal L}\rangle= \EE\langle Q^2\rangle-\frac12\EE[\langle Q\rangle^2]$. It remains to compute

\begin{align*}
\EE[\langle Q\rangle \langle {\cal L}\rangle]=\mathbb{E}\Big[\langle Q \rangle\frac{\big\langle \|\bx\|^2 \big\rangle}{2n} -  \langle Q \rangle^2 - \langle Q \rangle\frac{\tilde \bZ \cdot \langle \bx\rangle}{2n\sqrt{R}}  \Big]	\,.
\end{align*}
By formulas \eqref{SteinLemma} and \eqref{GaussIPP} in which the Hamiltonian is \eqref{Ht} we have (here $\nabla\equiv\nabla_{\tilde \bZ}$)
\begin{align*}
-\frac{1}{2n\sqrt{R}}\EE\big[\tilde \bZ \cdot \langle \bx\rangle\langle Q \rangle \big]	&= -\frac{1}{2n\sqrt{R}}\EE\big[\langle Q\rangle \nabla\cdot \langle \bx\rangle + \langle \bx\rangle\cdot \nabla \langle Q\rangle\big]\nn

&=-\frac{1}{2n}\EE\big[\langle Q\rangle \big(\big\langle \|\bx\|^2\big\rangle-\|\langle\bx\rangle\|^2\big) + \langle \bx\rangle\cdot \big(\langle Q\bx\rangle-\langle Q\rangle \langle \bx\rangle\big)\big]\nn

&\overset{\rm N}{=}-\frac{1}{2n}\EE\big[\langle Q\rangle \big\langle \|\bx\|^2\big\rangle\big]+\frac{1}{n}\EE\big[\langle Q\rangle \|\langle \bx \rangle \|^2\big]-\frac12\EE[\langle Q\rangle^2]\,.
\end{align*}
We used the following consequence of the Nishimori identity. Let $\bx,\bx^{(2)}$ be two replicas, i.e., conditionally (on the data) independent samples from the posterior \eqref{tpost}. Then $$\frac1n\EE\big[\langle \bx\rangle\cdot \langle \bx Q\rangle\big]=\frac1{n^2}\EE\big\langle (\bx^{(2)}\cdot \bx) (\bx\cdot \bX)\big\rangle\overset{\rm N}{=}\frac1{n^2}\EE\big\langle (\bx^{(2)}\cdot \bX) (\bX\cdot \bx)\big\rangle=\EE[\langle Q\rangle^2]\,.$$
We reach
\begin{align*}
\EE\big\langle Q(\langle {\cal L}\rangle-{\cal L})\big\rangle &=	\EE\langle Q^2\rangle-2\EE[\langle Q\rangle^2]+\frac{1}{n}\EE\big[\langle Q\rangle \|\langle \bx \rangle \|^2\big]\nn
&=\frac{1}{n^2}\EE\big\langle(\bx\cdot\bX)^2-2(\bx\cdot\bX)(\bx^{(1)}\cdot\bX)+(\bx\cdot\bX)(\bx^{(2)}\cdot\bx^{(3)})\big\rangle\nn

&\overset{\rm N}{=}\frac{1}{n^2}\EE\big\langle(\bx\cdot\bx^{(0)})^2-2(\bx\cdot\bx^{(0)})(\bx^{(1)}\cdot\bx^{(0)})+(\bx\cdot\bx^{(0)})(\bx^{(2)}\cdot\bx^{(3)})\big\rangle
\end{align*}
where $\bx^{(0)},\bx,\bx^{(2)}, \bx^{(3)}$ are replicas. Component-wise and after multiplying by $n$ this gives

\begin{align}
\frac{d\,\EE\langle Q\rangle}{dR} &=\frac{1}{n}\sum_{i,j=1}^n\EE\big\langle x_ix_i^{(0)} x_jx_j^{(0)} -2x_ix_i^{(0)}x_j^{(1)}x_j^{(0)}+x_ix_i^{(0)}x_j^{(2)}x_j^{(3)}\big\rangle\nn

&=\frac{1}{n}\sum_{i,j=1}^n\EE\big[\langle x_ix_j\rangle^2 -2\langle x_i\rangle \langle x_j\rangle \langle x_ix_j\rangle+ \langle x_i\rangle^2\langle x_j\rangle^2\big]\ge 0 \label{secondDer_f_pos}
\end{align}
which proves \eqref{jacPos}.\\

\subsection{Proof of \eqref{JacUV}}
 Identity \eqref{JacUV} follows from the following inequality that we prove now: $$\frac{\partial \EE\langle Q_V\rangle}{\partial R_V}\ge 0$$


TITLE: In what area of study does one encounter this principle in timetabling?
QUESTION [9 upvotes]: A while ago I saw an image like the one below in a lecture, which was supposed to represent a rail network in a (square) city:

The circles represent trains that are moving either North/South or East/West along the vertical and horizontal tracks.  The purpose of this picture was to show that, even though the grid is unevenly spaced, it is always possible to schedule the trains so that connections were perfectly timed:  that is, any time a train arrives at an intersection, there is another train also arriving at that intersection, in a perpendicular direction.
The math behind this is very simple, so my question is:  what is the area of study in which one would encounter an image like this?

REPLY [3 votes]: Not an answer, but two related, almost inverse topics suggesting in which
areas of mathematics they fall:
(1) The Lonely Runners Conjecture.
See, e.g., Terry Tao, "Some remarks on the lonely runner conjecture." Perhaps this could be classified as a mixture of number theory
and combinatorics.

Guillem Perarnau, Oriol Serra, "Correlation Among Runners and Some Results on the Lonely Runner Conjecture." Electr. J. Comb. 2016.

(2) "At Museum of Mathematics, Meet 2 Beavers That’ll Never Meet." This construction uses
Truchet Tiling.
Perhaps this could be classified as a mixture of topology and combinatorics.


TITLE: Definition of totally bounded set
QUESTION [2 upvotes]: A set $A$ in a metric space $(M, d)$ is said to be totally bounded if,
  given any $\epsilon>0$, there exist finitely many points
  $x_1,\ldots,x_n\in M$ such that
  $A\subset\bigcup_{i=1}^nB_\epsilon(x_i)$.
  That is, each $x\in A$ is within $\epsilon$ of some $x_i$.

The author then goes on to say:
In the definition of a totally bounded set $A$, we could easily insist that each $\epsilon$-ball be centered at a point of $A$.
Indeed, given $\epsilon>0$, choose $x_1,\ldots,x_n\in M$ so that $A\subset\bigcup_{i=1}^nB_{\epsilon/2}(x_i)$.
We may certainly assume that $A\cap B_{\epsilon/2}(x_i)\ne\varnothing$ for each $i$, -------- HOW??
and so we may choose a point $y_i\in A\cap B_{\epsilon/2}(x_i)$ for each $i$.
By the triangle inequality, we then have $A\subset\bigcup_{i=1}^nB_\epsilon(y_i)$. That is, $A$ can be covered by finitely many $\epsilon$-balls, each centered at a point in $A$.
What is the justification for the line marked "HOW??" above?

REPLY [1 votes]: What happens when $A\cap B(x_j)=\emptyset$ for some $j$? Then
$$A=A\backslash B(x_j)\subseteq\bigg(\bigcup B(x_i)\bigg)\backslash B(x_j)\subseteq\bigcup_{i\neq j} B(x_i)$$
In particular we can refine our covering $\{B(x_i)\}$ by removing $B(x_j)$ and still preserving all required properties.


TITLE: The boundary of a unbounded simply connected planar domain
QUESTION [0 upvotes]: Let $D$ be a unbounded simply connected planar open domain. Let $\partial D$ be its boundary. The question is the following:
Can $\partial D$ have a compact component?

REPLY [2 votes]: Suppose that $D\subset R^n$ is an open unbounded connected subset (a domain) whose boundary has a compact connected component. Then $E=R^n\setminus D$ has at least 2 connected components. Now, it follows from the Alexander duality that $H_{n-1}(D)\cong \tilde{H}^0(E)$ (the right hand side is the Chech cohomology). Hence, $H_{n-1}(D)$ has rank at least 1. In your case $n=2$ and the Hurewicz theorem implies that $\pi_1(D)$ is nontrivial. Contradiction.
In dimension 2 one can give a proof avoiding (co)homology, but I prefer this argument as more general.


TITLE: Elementary transformations of circles
QUESTION [1 upvotes]: Discuss the image of the circle $|z-2|=1$ and its interior under the
  following transformations.
a.) $w=\frac{z-2}{z-1}$
b.) $w=\frac{z-4}{z-3}$
c.) $w=\frac1z.$

The answer that is provided are, respectively: $$\{w:Rew\le\frac12\},\{w:Rew\ge \frac32\},\{w:|w-\frac23|\le\frac13\}.$$
Not sure how they got that. I know each of the circles has a pole and those poles lies on the circle, so the image has to be a straight line, but how do I go about finding those lines? Is there an algebraic or a more easy recognizable method to follow?

REPLY [2 votes]: The usual mantra is 'three points defined a circle (or line)'. This is usually the quickest way to find the answer.
We'll use the fact that $1,3,2+i$ are in the original circle.
(a) $1\mapsto \infty$ so it is a line. $3 \mapsto \frac{1}{2}$, and $2+i \mapsto \frac{i}{1+i} = \frac{1}{2}(1+i)$. Hence we have a line through $\frac{1}{2},\frac{1}{2} + \frac{i}{2}$. This is clearly the line $\mathrm{Re} w = \frac{1}{2}$. To check which side of the line is which, note that $z=2$ is in the interior, and $2 \mapsto 0$ so the region is $\mathrm{Re} w \le \frac{1}{2}$
(b) I'll leave to you.
(c) You could do this as the above too. Alternatively, note $$|z-2| = 1 \iff (z-2)(z^\star-2) = 1 \iff 1 - 2/z - 2/z^\star+3/zz^\star = 0$$ and then using $w=1/z$ we find
$$3ww^\star - 2w -2w^\star + 1 = 0 \iff \left(w-\frac 2 3 \right)\left(w^\star-\frac 2 3 \right) = \frac 1 9$$
which gives the result. Again, one point is enough to tell you where the interior is.


TITLE: Showing $8(\arctan(\sqrt2-1)) = \pi$
QUESTION [3 upvotes]: My friend is saying  $$8(\arctan(\sqrt2-1)) = \pi$$
I know $4\arctan(1) = \pi$
I thought of $4\arctan(\sqrt2-1) + 4\arctan(\sqrt2-1)$
But I got stuck somewhere
How to solve?

REPLY [2 votes]: Your friend is saying  $$8(\arctan(\sqrt2-1)) = \pi$$
in other words removing inverse function he is saying
$$  (\sqrt2-1)=\tan \frac{\pi}{8}=t $$
that you can say using double angle formula for tan
$$\tan \pi/4 = \frac{2t}{1-t^2} $$
which is same thing as saying
$$ 1=\frac{2 (\sqrt2-1)}{1-(3-2\sqrt2)}$$
thats same thing as saying ... after cancelling $2$ in numerator & denominator:
$$ 1=\frac{\sqrt2-1}{\sqrt2-1}$$
So he is right.


TITLE: Permutations of "MATHEMATICS" containing "MAT"
QUESTION [1 upvotes]: I want to determine how many permutations of the word "MATHEMATICS" are possible with the constraint that it must contain the string "MAT".
There are $9$ ways to write the string "MAT" and then $8!$ ways of writing the remaining letters but by simulation this appears to overcount. I believe it is the repetition of the letters in "MAT" that is making this tricky.

REPLY [4 votes]: Glue the letters "MAT" and consider them as a single letter. Then you have the $9$ letters, namely $MAT, H, E, M, A, T, I, C, S$. There are $9!$ ways to permute these letters, as we have no repetitions of letters.
Now the only possibility of doublecounting is when we have the letters of the other "MAT" triple together. So to take care of this, glue this letters to get $7$ letters, namely $MAT, H, E, MAT, I, C, S$. These can be permuted in $\frac{7!}{2!}$ ways.  Now just subtract these number from the first one, as the second one gives you the number of combinations that appear twice in the upper combinations. Finally the number you're after is:
$$9! - \frac{7!}{2!}$$


TITLE: Basis of subgroup of a free abelian group
QUESTION [2 upvotes]: We have this theorem:
** Let $F$ be a free abelian group of rank $n$ and let $H$ be a subgroup
of $F.$  There exists a basis $\{x_1,...,x_n\}$ of $F$ and integers $d_1,...,d_r > 0 $ such
that
• $di\vert d_{i+1}$ for $i = 1,...,r$
• $\{d_1x_1,\ldots,d_rx_r\}$ is a basis of H.**

I am confused with this.  $\mathbb{Z}*\mathbb{Z}$ is a free abelian group with basis $(1,0)$ and $(0,1)$.  Let $H=2\mathbb{Z}*3\mathbb{Z}$ be a subgroup of $\mathbb{Z}*\mathbb{Z}$ with basis $2(1,0)$ and $3(0,1)$.  $\mathbf {But}$ $2$ does not divide $3$.  What is the problem here?

REPLY [2 votes]: In your example, take $\;B:=\{\,(2,3)\,,\,(1,2)\,\}\;$ , then show:
1) $\;B\;$ is a $\,\Bbb Z\,-$ linearly independent set and is thus a basis of $\;\Bbb Z\times\Bbb Z\;$ ;
2) $\;C:=\left\{\,1\cdot(2,3)\,,\,6\cdot(1,2)\,\}=\{\,(2,3)\,,\,\,(6,12)\,\right\}\;$ are $\;\Bbb Z\,-$ linearly independent and a basis of $\;2\Bbb Z\times3\Bbb Z\;$ as required.