TITLE: A meaningful distinction between determinism and causality
QUESTION [2 upvotes]: Causality is generally accepted to be a fundamental physical principle. But quantum mechanics is acausal (e.g. there is no 'why' as to the result of a measurement of the position of a particle in an infinite 1D square potential well). In which case what is a distinction between causality and determinism, that has a meaningful non-acausal definition of causality.
It seems to me that "causality = determinism + quantum mechanics". It seems that it doesn't provide any new concepts, it's just a flawed attempt to reconcile determinism with the arbitrary probabilistic nature of QM, which are ultimately unreconcilable. Does anyone agree with this idea? If not, I would like someone to try and convince me that I'm wrong.
I am fully aware that a lot of threads barking up this tree, and I have tried reading many of them, but none seem to crystallize my problem very well.

REPLY [5 votes]: Let's clarify the concepts:

Determinism: for a given experimental set up, every experiment will yield the same results. QM are not deterministic, if you measure a superposition of states, you could get one or the other, with certain probability, and there is nothing you can do about it.
Causality: causes happen before its effects. QM is causal, because if you have a system in superposition and do a measurement on it, you destroy the decoherence and make it collapse. But this happens as you measure, not before. You cannot change the outcome of the experiment you did yesterday.

And let me throw another one:

Teleology: everything happens for a reason. Giraffes evolved to have a long neck so they could eat from the high branches. The electron jumped to a lower level so it would release a photon and you could read. This is a matter of pure philosophy, not science.

Your "there is no 'why' as to the result of a measurement of the position of a particle in an infinite 1D square potential well" falls into the teleological approach, not on the causality. Causality tells you that I pressed the button on the machine before the measurement, but it is completely irrelevant why I did it.


TITLE: If the odds of something occuring are $5/68$, given $36$ attempts, how can I calculate the odds of it occuring $x$ number of times?
QUESTION [0 upvotes]: If the odds of something occurring are $5/68$, given $36$ attempts, how can I calculate the odds of it occurring $x$ number of times?

Basically is there a general form equation for this kind of calculation?
Background
I heard of the binomial distribution, probably in high school or something but it's been a while. Wikipedia was somewhat helpful but I can't figure out how to make a generic equation out of what it's telling me.

REPLY [0 votes]: Bernoulli's Formula (in binomial distribution): the probability of something with probability (in one single try) $\;p\;$ happening $\;k\;$ times in $\;n\;,\;\;n\ge k\;$ ,
 tries is
$$P_n(k):=\binom nk p^k(1-p)^{n-k}$$
with
$$\binom nk:=\frac{n!}{k!(n-k)!}$$


text:
\begin{document}

\baselineskip 5.5truemm

\vskip0.4truecm \centerline{\bf STRONG LIMIT THEOREMS IN THE MULTI-COLOUR}
\centerline{\bf GENERALIZED ALLOCATION SCHEME}

\vskip0.5truecm

\centerline{
  {\sc Alexey Chuprunov} and {\sc Istv\'an Fazekas}}

\bigskip
Department of Math. Stat. and Probability, Chebotarev Inst. of Mathematics and Mechanics,
Kazan State University, Universitetskaya 17, 420008 Kazan, Russia, e-mail: achuprunov@mail.ru

Faculty of Informatics, University of Debrecen,  P.O. Box 12, 4010 Debrecen, Hungary,
e-mail: fazekasi@inf.unideb.hu, tel: 36-52-512900/75211

\bigskip

\begin{abstract}
The generalized allocation scheme is studied.
Its extension for coloured balls is defined.
Some analogues of the Law of the Iterated Logarithm and the Strong Law of Large Numbers are obtained for the number of boxes containing fixed numbers of balls.
\end{abstract}

\renewcommand{\thefootnote}{}
{\footnotetext{
{\bf Key words and phrases:}
generalized allocation scheme, conditional probability, Law of the Iterated Logarithm, Law of Large Numbers, exponential inequality.

{\bf 2000 Mathematics Subject Classification:}      60F15 Strong theorems.

The publication was supported by the T\'AMOP-4.2.2.C-11/1/KONV-2012-0001 project. The project has been supported by the European Union, co-financed by the European Social Fund.
}}

\section{Introduction}
\label{sectIntr} \setcounter{equation}{0}

The generalized allocation scheme is widely studied (see \cite{Kol99}, \cite{Kol03}, \cite{pavlov}).
The scheme contains several special cases such as the usual allocation scheme (see \cite{Weiss}, \cite{Renyi}, \cite{KSC})
and the random forests (see \cite{Kol99}, \cite{pavlov}).

In the generalized scheme of allocations of balls into boxes, the distribution of the contents of the boxes is represented as the conditional distribution
of independent random variables given that their sum is fixed.
More precisely, the generalized allocation scheme is defined as follows.
Let $\eta_1, \dots,\eta_N$ be non-negative integer-valued random variables.
If there exist independent random variables $\xi_1,\dots,  \xi_N$ such that the  joint  distribution of $\eta_1, \dots, \eta_N$ admits the representation
\begin{equation}  \label{EtaXi0}
\P\{\eta_1=k_1, \dots, \eta_N=k_N\}  =  \P\{\xi_1=k_1, \dots, \xi_N=k_N\,\,\, |\,\,\, \xi_1+\dots +\xi_N=n\},
\end{equation}
where $k_1,\dots, k_N$ are arbitrary non-negative integers with $k_1+\dots + k_N=n$, we say that the distribution of $\eta_1, \dots,\eta_N$  is represented by a generalized  allocation
scheme with parameters $n$ and $N$, and independent random variables $\xi_1,\dots, \xi_N$.
In view of independence of the random variables $\xi_1,\dots, \xi_N$, the study of several
questions of the generalized allocation scheme can be reduced to problems of sums of independent random variables.
Let $\mu_{snN}$ be the number of the random variables $\eta_1, \dots, \eta_N$  being equal to $s$, $s=0,1,\dots, n$.
Observe that
\begin{equation}  \label{mu0}
\mu_{snN}=\sum\nolimits_{j=1}^N \I_{\{\eta_j=s\}}
\end{equation}
is the number of boxes containing $s$ balls.
Here $\I_{\{. \}}$ denotes  the indicator of a set.

In \cite{ChuFaz2010} an exponential inequality  for the tail of the conditional expectation of sums of centered independent random variables was obtained.
That inequality was applied  to prove analogues of the Law of the Iterated Logarithm and the  Strong Law of Large Numbers for conditional expectations.
As corollaries, certain strong theorems for the generalized allocation scheme were obtained.

In the present paper we introduce the multi-colour version of the generalized allocation scheme.
Then we prove analogues of the Law of the Iterated Logarithm and Law of Large Numbers for the numbers of boxes containing fixed numbers of balls.
Our theorems are extensions of the results of \cite{ChuFaz2010}.
To prove our theorems, we use some basic inequalities of \cite{ChuFaz2010}.

\section{The multi-colour scheme and the main results}
\label{sectRes} \setcounter{equation}{0}

Now we introduce the multi-colour version of the generalized allocation scheme.
Let $K$ be a fixed positive integer, it will denote the number of different colours.
$n_i$ denotes the number of balls of $i$th colour, $i=1,2,\dots, K$.
Then $n= n_1 + \dots + n_K$ is the total number of balls.
Let $N$ denote the number of boxes.
The generalized allocation scheme of allocation $n$ balls into $N$ boxes when there are $K$ different colours among the balls is the following.

Let $\xi_{i1},\dots, \xi_{iN}$, $1\le i\le K$, be an array of independent non-negative integer valued random variables.
Denote by $\etab_{1}, \dots, \etab_{N}$  a set of $K$-dimensional random vectors with the following property.
The  joint  distribution of $\etab_{1}, \dots, \etab_{N}$ admits representation
\begin{equation}  \label{EtaXi}
\P\{{\etab_{1}=\kb_{1}, \dots, \etab_{N}=\kb_{N}}\}  = \prod_{i=1}^K \P\{\xi_{i1}=k_{i1}, \dots, \xi_{iN}=k_{iN}\,\, |\,\, \xi_{i1}+\dots +\xi_{iN}=n_i\},
\end{equation}
for arbitrary non-negative integers valued vectors  ${\kb_j}=(k_{1j}, k_{2j},\dots k_{Kj})$, $1\le j\le N$ with $k_{i1}+\dots + k_{iN} = n_i$, $i=1, \dots ,K$.
Then we say that $\eta_{i1}, \dots, \eta_{iN}$, $i=1, \dots ,K$, obey a multi-colour generalized allocation scheme of placing of $n_i$ $i$th colour balls ($1\le i\le K$) into $N$ boxes.
$\eta_{ij} = k_{ij}$ means that after allocating $n$ balls into $N$ boxes, in the $j$th box there are $k_{ij}$ balls of $i$th colour.

The number of boxes containing $s_i$ balls of $i$th colour for any  $1\le i\le K$, is
\begin{equation}  \label{mu}
\mu_{{\sb \nb}N}=  \sum_{j=1}^N \I_{\{{\etab_{j}=\sb}\}} =\sum_{j=1}^N\prod_{i=1}^K \I_{\{\eta_{ij}=s_i\}}
\end{equation}
where ${\sb}=(s_1, s_2,\dots, s_K)$ and   ${\nb}=(n_1, n_2,\dots ,n_K)$ .

Let $i$ be fixed.
Let the random variables $\xi_{i1},\dots, \xi_{iN}$ be identically distributed.
In Kolchin's generalized allocation scheme usually power law distributions are considered (see [2]).
For our model it means that the random variables $\xi_{i1}, \dots, \xi_{iN}$ are distributed as follows:
$q_{ik}=\P\{\xi_{i1}=k\}= ({b_{ik}\theta^k})/({k!B_i(\theta)}) $
where $b_{i0}, b_{i1}, \dots $ is a certain sequence of non-negative numbers, and $ B_i(\theta)=\sum_{k=0}^{\infty} {b_{ik}\theta^k}/{k!} $ for each fixed $i\in \{ 1,2,\dots, K\}$.

\begin{exmp}   \label{Poiss1}
The usual (that is not generalized) multi-colour allocation.
Let $\xi_{ij}$ have Poisson distribution, i.e. for each $i$ and $j$ let $\P (\xi_{ij}= k) = \frac{\lambda_i^k}{ k!} e^{-\lambda_i}$, $k=0,1,\dots$.
Then
$$
\prod_{i=1}^K \P\{\xi_{i1}=k_{i1}, \dots, \xi_{iN}=k_{iN}\,\,\, |\,\,\, \xi_{i1}+\dots +\xi_{iN}=n_i\} =
\prod_{i=1}^K \frac{n_i!}{k_{i1}!\dots k_{iN}!} \left( \frac{1}{N} \right)^{n_i}
$$
if $k_{i1}+\dots +k_{iN}=n_i$.
That is for each fixed $i$ the vector $\{\eta_{i1}, \dots, \eta_{iN}\}$ has polynomial distribution.
Now $\{\eta_{i1}=k_{i1}, \dots, \eta_{iN}=k_{iN}\} $ means that the box contents are $k_{i1}, \dots, k_{iN}$ after allocating $n_i$ balls into $N$ boxes
during the usual random allocation procedure.
Moreover, the allocations of balls of different colours are independent.
We see that $\mu_{{\sb \nb}N}$ is the number of boxes containing $s_i$ balls of $i$th colour ($i=1,2,\dots, K$).

We see that the parameter $\theta$ used in the generalized allocation scheme is the same as $\lambda$ in the above usual allocation procedure.

We remark that in \cite{ChuFaz2005} using direct methods, we proved the following.
If $n,N \to \infty$ so that $n/N \to \lambda_0$, then
\begin{equation}  \label{limMu}
\frac{\mu_{rnN}}{N} \to  \frac{\lambda_0^r}{ r!} e^{-\lambda_0}
\end{equation}
almost surely.
Here $\mu_{rnN}$ is the number of boxes with $r$ balls (after allocating $n$ balls into $N$ boxes in the usual random allocation procedure).
In \cite{ChuFaz2009} we extended this result for generalized allocations.
 \hfill $\Box$
\end{exmp}

In what follows,  we consider  sequences of non-negative numbers $b_{i0}, b_{i1}, \dots$ with $b_{i0}>0, b_{i1}>0$
and assume that the convergence radius $R_i$ of the series
\begin{equation}   \label{B}
B_i(\theta)=\sum\nolimits_{k=0}^{\infty}\frac{b_{ik}\theta^k}{k!}
\end{equation}
is positive for each fixed $i$.
 Let us introduce the integer-valued random variable $\xi_i(\theta)$  (where $\theta >0$) with distribution
\begin{equation}   \label{xi}
 {\P}\{\xi_i(\theta)=k\}=\frac{b_{ik}\theta^k}{k!B_i(\theta)},\,\,\,k=0,1,2,\dots.
\end{equation}
 By \cite{Kol99}, one has
$$
m_i(\theta)=  {\E}\xi_i(\theta)=  \frac{\theta B'_i(\theta)}{B_i(\theta)}
$$
and
\begin{equation}  \label{sigma}
\sigma^2_i(\theta)=  {\D}^2\xi_i(\theta)=
\frac{\theta^2 B^{''}_i (\theta)}{B_i(\theta)}+ \frac{\theta B'_i(\theta)}{B_i(\theta)}- \frac{\theta^2 (B'_i(\theta))^2}{(B_i(\theta))^2}.
\end{equation}
The last equality implies that
\begin{equation}  \label{sigma_theta}
\sigma^2_i(\theta)=\theta m'_i(\theta).
\end{equation}
Let $0<\theta'_i<\theta^{''}_i<R_i$.
If $\sigma^2_i(\theta)=0$ for some $\theta\in [\theta'_i, \theta^{''}_i]$, then the random variable $\xi_i(\theta)$ is a constant.
Since $b_{i0}>0, b_{i1}>0$, the random variable $\xi_i(\theta)$ is not a constant.
Therefore $\sigma^2_i(\theta)$, $\theta\in [\theta'_i, \theta^{''}_i]$ is a positive continuous function.
Consequently,
\begin{equation}  \label{C1C2}
0<C_1 =\inf_{\theta\in [\theta'_i, \theta^{''}_i]} \sigma_i^2(\theta) \le \sup_{\theta\in [\theta'_i, \theta^{''}_i]}\sigma_i^2(\theta)= C_2<\infty, \,\,\,\,1\le i\le K.
\end{equation}
By \eqref{sigma_theta} and \eqref{C1C2}, we have
$$
0<\frac{C_1}{\theta^{''}_i}=\inf_{\theta\in [\theta'_i, \theta^{''}_i]}m'_i(\theta) \le \sup_{\theta\in [\theta'_i, \theta^{''}_i]}m'_i(\theta)= \frac{C_2}{\theta'_i}<\infty,
\,\,\,\,1\le i\le K.
$$
So $m_i(\theta)$, $\theta\in [\theta'_i, \theta^{''}_i]$, is a positive, continuous, strictly increasing function.
We will denote by $m^{-1}_i$ the inverse function of $m_i$.

We see that the random variable $\xi_i(\theta)$ has all moments, if $\theta<R_i$.

Throughout the paper let  $\xi_{i1}(\theta), \dots , \xi_{iN}(\theta)$ be independent copies of $\xi_i(\theta)$ where
$\xi_i(\theta)$ has distribution \eqref{xi}.

We shall prove limit theorems when the number of boxes and the number of balls converge to infinity (the number of colours is fixed).

First we study the asymptotic behaviour along a fixed subsequence.
The subsequence will be indexed by $t$ ($t$ can be considered as the discrete time $t=1,2,\dots$, and $t$ will go to $\infty$).

Let $n_{it}$ denote the number of balls of $i$th colour at time $t$.
Let ${\nb}_t=(n_{1t},\dots n_{Kt})$.
Let $N_t$ be the number of boxes at time $t$,  assume that  $N_t<N_{t+1}$, $t\in\N$.
Let ${\alphab}_t=(\alpha_{1t},\dots, \alpha_{Kt})=(n_{1t}/{N_t},\dots, n_{Kt}/N_t)$ be the ratios of the numbers of balls and the number of boxes,
and let $\theta_{it}= m_i^{-1}(\alpha_{it})$,
\begin{equation}  \label{must}
p_{{\sb}t}=\prod_{i=1}^K\frac{b_{is_i}\theta^{s_i}_{it}}{s_i!B_i(\theta_{it})} ,\quad
\sigma^2_{{\sb}t}=p_{{\sb}t}(1-p_{{\sb}t})\quad \mbox{\text and} \qquad
\mu_{{\sb}t}=\sum_{i=1}^{N_t} \I_{\{\etab_i={\sb}\}}.
\end{equation}
At time $t$, $\mu_{{\sb}t}$ is the number of boxes containing $s_1,s_2,\dots s_K$ balls of colours $1,2,\dots, K$, respectively.

We remark that if $b_{is_i}=0$ for some $1\le i\le K$, then $\mu_{{\sb}t}=0$.
So we can concentrate on the case $b_{is_i}>0$ for all $1\le i\le K$.

We will prove the following analogue of the Law of the Iterated Logarithm for $\mu_{{\sb}t}$.

\begin{thm}    \label{Theorem1.1}

Let $0<\alpha'_i<\alpha''_i$ be such that $m_i^{-1}(\alpha''_i)<R_i$, $1\le i\le K$.
Suppose that $0<\alpha'_i<\alpha_{it}<\alpha''_i$  for all $t\in \N$,  $1\le i\le K$.
Let ${\sb}$ be fixed and we assume  that $b_{is_i}>0$ for each fixed $1\le i\le K$.
Then we have
$$
\limsup_{t\to\infty}\frac{|\mu_{{\sb}t}-\E\mu_{{\sb}t}|}{\sqrt{N_t\ln(N_t)}\sigma_{{\sb}t} } \le
4\sqrt{1+\frac{K}{2}}\,\,\,\, \,\,\,\mbox{\text almost surely.}
$$
\end{thm}

Now, we turn to a version of the previous theorem.
We shall consider the asymptotic behaviour in a sector instead of along a subsequence.
More precisely, the number of boxes and the numbers of balls will tend to infinity, while their ratios remain bounded.
Let $\alpha_i={n_i}/{N}$ be the ratio of the number of balls of $i$th colour and the number of boxes,
and let $\theta_{i\alpha_i}= m_i^{-1}(\alpha_{i})$, $i=1,2,\dots, K$.
We shall use the notation
\begin{equation}  \label{psnN}
p_{{\sb}\nb N}=\prod_{i=1}^K\frac{b_{is_i}\theta^{s_i}_{i\alpha_i}}{s_i!B_i(\theta_{i\alpha_i})} ,\quad
\sigma^2_{{\sb}\nb N}=p_{{\sb}\nb N}(1-p_{{\sb}\nb N}).
\end{equation}

We can again concentrate on the case $b_{is_i}>0$ for all $1\le i\le K$.

\begin{thm}    \label{Theorem1.2}

Let $0<\alpha'_i<\alpha''_i$ be such that $m_i^{-1}(\alpha''_i)<R_i$, $1\le i\le K$.
Let ${\sb}$ be fixed and assume that $b_{is_i}>0$, $1\le i\le K$.
Then for $\mu_{{\sb \nb}N}$ defined in \eqref{mu}, we have
\begin{equation}  \label{eqno{(1.10)}}
\limsup_{\begin{subarray}{c}{\nb\to\infty}, N\to\infty,\\ \alpha'_i<\alpha_i<\alpha''_i,\,\,1\le i\le K\end{subarray}}
\frac{|\mu_{{\sb \nb}N}-\E\mu_{{\sb}\nb N}|}{\sqrt{N\ln(N)}\sigma_{{\sb \nb}N}}  \le
4\sqrt{1+\frac{3K}{2}}\,\,\,\, \,\,\,\mbox{\text almost surely.}
\end{equation}
\end{thm}

\begin{cor}  \label{Corollary1.1}
Let $0<\alpha'_i<\alpha''_i$ be such that $m_i^{-1}(\alpha''_i)<R_i$, $1\le i\le K$.
Let ${\sb}$ be fixed.
Assume that $b_{i s_i} > 0$, $1\le i\le K$.
Let $d_N\in\R$, $N\in \N $ be such that $\lim_{N\to\infty}\frac{\sqrt{N\ln(N)}}{d_N}=0$.
Then for $\mu_{{\sb \nb}N}$ defined in \eqref{mu} we have
$$
\lim_{\begin{subarray}{c}{\bf n},N\to\infty,\\
\alpha'_i<\alpha_i<\alpha''_i,\,\,1\le i\le K\end{subarray}}
\frac{\mu_{{\sb \nb}N}-\E\mu_{{\sb \nb}N}}{d_N }=0 \,\,\,\, \,\,\,\mbox{\text almost surely.}
$$
\end{cor}

Using Corollary  \ref{Corollary1.1}, we obtain the following SLLN.

\begin{thm}    \label{Theorem1.3}
Let $N\to\infty$,  $n_i\to \infty$ such that $n_i/N = \alpha_i\to\alpha_{i0}$, \,  $m_i(\theta_{\alpha_{i0}})=\alpha_{i0}$ and
$0<\theta_{\alpha_{i0}}<R_i$, $1\le i\le K$.
Then for $\mu_{{\sb}\nb N}$ defined in \eqref{mu}, we have
\begin{equation}  \label{eqno{(1.11)}}
\frac{1}{N}\mu_{{\sb \nb}N}  \to  \prod_{i=1}^K\frac{b_{is_i}\theta^{s_i}_{\alpha_{i0}}}{s_i!B_i(\theta_{\alpha_{i0}})}
 \end{equation}
almost surely as $N\to\infty$, $n_i\to\infty$ such that $n_i/N = \alpha_i\to\alpha_{i0}$, \, $1\le i\le K$.
\end{thm}

\begin{exmp}   \label{Poiss2}
We apply Theorem \ref{Theorem1.3} to the usual (that is not generalized) multi-colour allocation mentioned in Example \ref{Poiss1}.
Let $\xi_{ij}$ have Poisson distribution with parameter $\lambda$.
Then $b_{ij}=1$, $B_i(\lambda)=e^{\lambda}$.
As $m_i (\lambda)= \E \xi_{i1} = \lambda$, the parameter $n_i/N =\alpha_i$ coincides with $\lambda_i$.
Therefore, by \eqref{eqno{(1.11)}},
$$
\frac{1}{N}\mu_{{\sb \nb}N}  \to  \prod_{i=1}^K \frac{\lambda^{s_i}_{{i0}}}{s_i!e^{\lambda_{i0}}},
$$
as $N\to\infty$,  $n_i\to \infty$ such that $n_i/N = \lambda_{i0}$.
 \hfill $\Box$
\end{exmp}

\begin{exmp}   \label{GeomPoiss}
Consider the allocation of $n_1+n_2$ balls into $N$ boxes with the following method.
First we allocate $n_1$ indistinguishable balls into $N$ boxes.
Then we allocate $n_1$ distinguishable balls into the same $N$ boxes.
Assume that the two allocations are independent.
So we have the following allocation scheme
 $$
 \P\{{\etab_{1}=\kb_{1}, \dots, \etab_{N}=\kb_{N}}\}  = \prod_{i=1}^2 \P\{\xi_{i1}=k_{i1}, \dots, \xi_{iN}=k_{iN}\,\, |\,\, \xi_{i1}+\dots +\xi_{iN}=n_i\}.
$$
We know, that the first allocation is the same as the partition of the positive integer number $n$ into $N$ positive integer summands.
Therefore it is easy to prove (see \cite{Kol99}, Example 1.2.2) that in the generalized allocation scheme
$$
\P\{\eta_{\rm 1 1}=k_{11}, \dots, \eta_{\rm 1 N}=k_{1N}\}  =
\P\{\xi_{11}=k_{11}, \dots, \xi_{1N}=k_{1N}\,\,\, |\,\,\, \xi_{11}+\dots +\xi_{1N}=n_1\},
$$
we should choose geometrical random variables $ \xi_{1j}$, $j=1,\dots, N$.
That is with the usual notation $\P\{\xi_{1j}=k\}=p^k(1-p)$, $k=0,1,2\dots$, $0<p<1$.
Therefore $b_{1k}=k!$, $B_1(p) = 1/(1-p)$, $m_1(p) = \E \xi_{1j} = 1/p$.
So the relation of our parameters is $\theta = 1/\alpha$.
The second allocation scheme
$$
\P\{\eta_{\rm 2 1}=k_{1}, \dots, \eta_{\rm 2 N}=k_{N}\}  =
\P\{\xi_{21}=k_{21}, \dots, \xi_{2N}=k_{iN}\,\,\,|\,\,\, \xi_{21}+\dots +\xi_{2N}=n_2\},
$$
is the usual one with Poisson random variables $ \xi_{2j}$.
That is $\P\{\xi_{2j}=k\}=e^{-\lambda}\frac{\lambda^k}{k!}$, $k=0,1,2\dots$, $0<\lambda$.
Therefore, by Theorem \ref{Theorem1.3}, we have
$$
\frac{1}{N}\mu_{{\sb\nb}N} \to \left(\frac{1}{\alpha_{10}}\right)^{s_1}\left(1-\frac{1}{\alpha_{10}}\right) e^{-\alpha_{20}}\frac{\alpha_{20}^{s_2}}{s_2!}
,\,\,\,\mbox{\text as}\,\,\, n_i,N\to\infty\,\,\,\mbox{\text such that}\,\,\,\,n_i/N= \alpha_i\to\alpha_{i0}, \,\,i=1,2,
$$
almost surely, where $1<  \alpha_{10}$, $0< \alpha_{20}$.
\hfill $\Box$
 \end{exmp}

\begin{rem}    \label{Remark1}
For each fixed $i\in\{1,2,\dots,K\}$ let $\zeta_{ij}$, $j\in{\N}$, be independent identically distributed random variables with finite expectation $m_i= \E\zeta_{ij}$.
Assume that  $\{ \zeta_{ij}\, : \, j\in{\N}\}$, $1\le i\le K$, are independent sets of random variables.
By the Kolmogorov Law of Large Numbers we have
 $$
 \frac{1}{N}\sum_{j=1}^N\prod_{i=1}^K\zeta_{ij}\to\prod_{i=1}^K m_{i},\,\,\,\,\,\mbox{\rm almost surely} \,\,\,\,\,\mbox{\rm as}\,\,\,\,\,\,N\to\infty.
 $$
Theorem \ref{Theorem1.3} is an analogue of this assertion for an independent sequence of sets of dependent indicators.
 \hfill $\Box$
\end{rem}

Now return to scheme \eqref{EtaXi}.
Let $s$ be a fixed non-negative integer number.
Denote by $\mu_{s{\nb}N}$ the number of boxes containing altogether $s$ balls regardless of their colour.
Then we have
\begin{equation}  \label{eqno{(1.12)}}
\mu_{s{\nb}N}=\sum_{{\sb}=(s_1, s_2,\dots s_K), s_1 + s_2 + \dots +s_K=s} \mu_{{\sb \nb}N}
=\sum_{s_1 + s_2 + \dots +s_K=s}\sum_{j=1}^N\prod_{i=1}^K\I_{\{\eta_{ij}=s_i\}}.
\end{equation}
Since the number of vectors ${\sb}=(s_1, s_2,\dots ,s_K)$ such that $s_1 + s_2 + \dots +s_K=s$ is finite, Theorem \ref{Theorem1.3} implies the following.

\begin{cor}  \label{Corollary1.2}
Let $N\to\infty$,  $n_i\to \infty$ such that $n_i/N =\alpha_i\to\alpha_{i0}$ and $m_i(\theta_{\alpha_{i0}})=\alpha_{i0}$ for some $0<\theta_{\alpha_{i0}}<R_i$, $1\le i\le K$.
Then for $\mu_{s{\nb}N}$ defined in \eqref{eqno{(1.12)}}, we have
\begin{equation}  \label{eqno{(1.13)}}
\frac{1}{N}\mu_{s{\nb}N} \to \sum_{ s_1 + s_2 + \dots +s_K=s} \prod_{i=1}^K\frac{b_{is_i}\theta^{s_i}_{\alpha_{i0}}}{s_i!B_i(\theta_{\alpha_{i0}})}
\end{equation}
almost surely as $N\to\infty$,  $ n_i\to\infty$ such that $n_i/N=\alpha_i\to\alpha_{i0}$, $1\le i\le K$.
\end{cor}

\begin{rem}    \label{Remark2}
Consider again the usual allocation.
That is the case then $\xi_{ij}$ has  Poisson distribution with parameter $\lambda$.
Then $b_{ij}=1$, $B_i(\lambda)=e^{\lambda}$, $m_i(\lambda)=\lambda$.
Therefore the limit in \eqref{eqno{(1.13)}} has the following form
$$
\sum_{s_1 + s_2 + \dots +s_K=s} \prod_{i=1}^K \frac{\lambda^{s_i}_{i0}}{s_i!e^{\lambda_{i0}}}=
e^{-(\lambda_{10}+\lambda_{20}+\dots +\lambda_{K0})}\frac{(\lambda_{10}+\lambda_{20}+\dots +\lambda_{K0})^s}{s!}.
$$
This limit coincides with the limit of $\frac{1}{N}\mu_{snN}$ at the usual random allocation of $n$ balls into $N$ boxes
when $\frac{n}{N}\to \lambda_{10}+\lambda_{20}+\dots +\lambda_{K0}$  (see \eqref{limMu}).

So the following problem arises: what kind of distributions of $\xi_{ij}=\xi_{ij}(\theta)$ satisfy this property.
More precisely: which power series distributions satisfy that for each $K$ the multi-colour limit in \eqref{eqno{(1.13)}}
is the same as the single colour limit when $\frac{n}{N}\to \alpha_{10}+\alpha_{20}+\dots +\alpha_{K0}$.

If it is valid, then for $B_i=B$, $s=0$ and $\alpha_{10}=\alpha_{20}=\dots =\alpha_{K0}=\frac{\alpha}{K}$ using \eqref{eqno{(1.13)}}, we obtain
\begin{equation}  \label{eqno{(1.15)}}
 \left(\frac{b_0}{B\left(\frac{\alpha}{K}\right)}\right)^K  =  \frac{b_0}{B(\alpha)}.
\end{equation}
 Since
  $$
 \left(\frac{b_0}{B\left(\frac{\alpha}{K}\right)}\right)^K  \to  e^{-(b_1/b_0)\alpha}, \quad \mbox{\rm as}\,\,\,\,K\to\infty,
 $$
 from \eqref{eqno{(1.15)}} it follows that $B(\alpha)=b_0 e^{(b_1/b_0)\alpha}$, therefore $\xi_{ij}$ has a  Poisson distribution.
  \hfill $\Box$
 \end{rem}

\begin{rem}    \label{Remark3}
Now we show that in scheme \eqref{EtaXi0} the distribution of $\eta_1,\dots , \eta_N$ determines the underlying power series distribution (up to a multiplicative constant).
So consider scheme \eqref{EtaXi0} both with $\P(\xi_i=k) = \frac{b_k\theta^k}{k!B(\theta)}$ and $P(\xi_i=k) =\frac{\tilde{b}_k\theta^k}{k!\tilde{B}(\theta)}$.
Let $n,N\to\infty$ such that $\frac{n}{N}\to\alpha$, where $\alpha<\infty$.
 By Theorem \ref{Theorem1.3},
$\frac{1}{N}\mu_{0nN}\to\frac{b_0}{B(\alpha)}$ almost surely and at the same time $\frac{1}{N}\mu_{0nN}\to\frac{\tilde{b}_0}{\tilde{B}(\alpha)}$ almost surely
as $n,N\to\infty$ such that $n/N\to \alpha$.
So $\frac{b_0}{B(\alpha)} = \frac{\tilde{b}_0}{\tilde{B}(\alpha)}$ which implies $B(\alpha) = (b_0/\tilde{b}_0)\tilde{B}(\alpha)$.
 \hfill $\Box$
 \end{rem}

\section{Proofs}
\label{sectProofs} \setcounter{equation}{0}

In order to prove Theorem \ref{Theorem1.1} we need the following lemma.
Consider the events
\begin{equation}  \label{eqno{(2.1)}}
A_{iN}(n_i)=\{\xi_{i1}(\theta_{i\alpha_i})+\xi_{i2}(\theta_{i\alpha_i})+\dots + \xi_{iN}(\theta_{i\alpha_i})=n_i\}
\end{equation}
where $\theta_{i\alpha_i}=m^{-1}_i(\alpha_i)$, $\alpha_i = n_i/N$.

\begin{lem} \label{Lemma2.1}
(Lemma 3.1 in \cite{ChuFaz2009}.)
Let $0< \alpha'_i< \alpha''_i$ be such that $m^{-1}_i( \alpha''_i)<R_i$.
Then there exists $N_0\in{\N}$ with the following property:
if $n_i, N$ are positive integers such that $N>N_0$  and $ \alpha'_i\le\alpha_i\le \alpha''_i$,
then we have
\begin{equation}  \label{eqno{(2.2)}}
 \P (A_{iN}(n_i)) > \frac{1}{4\sigma_i(\theta_{i\alpha_i})\sqrt{N}}.
\end{equation}
\end{lem}

{\sc Proof of Theorem \ref{Theorem1.1}.}
We want to apply Theorem 3.1 of \cite{ChuFaz2010}.
By the independence of the random variables $\xi_{ij}$, $1\le i\le K$, $1\le j\le N$, and by \eqref{EtaXi}, we see that the general framework of that theorem covers our model.

Let $A_t=\cap_{i=1}^K A_{iN}(n_{it})$.
Using first \eqref{EtaXi} and \eqref{eqno{(2.2)}}, then \eqref{C1C2}, we obtain
$$
\P(A_t)> \frac{1}{(4\sqrt{N_t})^K}\prod_{i=1}^K\frac{1}{\sigma_i(\theta_{it})} \ge\frac{C''}{N_t^{K/2}}.
$$
As $C''>0$, condition (3.1) of \cite{ChuFaz2010} is valid with $\beta=\frac{K}{2}$.
We have $\sigma^2_{{\sb}t}= p_{{\sb}t}(1-p_{{\sb}t})$.
Here
$$
p_{{\sb}t}=\prod_{i=1}^K \frac{b_{is_i}\theta^{s_i}_{it}}{s_i!B_i(\theta_{it})}>
\prod_{i=1}^K\frac{b_{is_i}(\theta'_i)^{s_i}}{s_i!B_i(\theta''_{i})}>0
$$
as $b_{is_i}>0$.
Since $b_{i0}$, $b_{i1}>0$, therefore we have
$$
1-p_{{\sb}t}>\prod_{i=1}^K\left(1-\frac{b_{is_i}\theta^{s_i}_{it}}{s_i!B_i(\theta_{it})}\right)>c>0.
$$
 So for some $c_2>0$ the relation $\sigma^2_{{\sb}t}\ge c_2$ is valid for each $t$, i.e. (3.2) of \cite{ChuFaz2010} is satisfied.
 Thus Theorem \ref{Theorem1.1} follows from Theorem 3.1 of \cite{ChuFaz2010}.
 \hfill $\Box$

 In order to prove Theorem \ref{Theorem1.2}, we need the following corollary of Theorem 2.1 of \cite{ChuFaz2010}.
 We shall use the following notation.
 $\sigma^2$  is the variance of $\I_{\{(\xi_{1j},\dots\xi_{Kj})={\sb}\}}$,
 $\rho$ is the variance of $\I_{\{(\xi_{1j},\dots\xi_{Kj})={\sb}\}}-\I'_{\{(\xi_{1j},\dots\xi_{Kj})={\sb}\}}$,
 where $\I'_{\{(\xi_{1j},\dots\xi_{Kj})={\sb}\}}$ is an independent copy of $\I_{\{(\xi_{1j},\dots\xi_{Kj})={\sb}\}}$.
 $A_{{\nb}N}=\cap_{i=1}^K A_{iN}(n_{i})$ where $A_{iN}(n_{i})$ is defined in \eqref{eqno{(2.1)}}.
 $Z$ is a centered Gaussian random variable with variance $1$.

\begin{lem} \label{Lemma2.2}
Let $\varepsilon\ge 4\sqrt{2}\sigma$.
Then we have
\begin{equation}  \label{eqno{(2.3)}}
\P\left\{ \frac{|\mu_{{\sb \nb}N}-\E \mu_{{\sb\nb}N}|}{\sqrt{N}}
\ge \varepsilon\right\} \le \frac{\sqrt{2}}{{\P}(A_{{\nb}N})} e^{-\frac{\varepsilon^2}{16\sigma^2}}(1+B),
\end{equation}
where
\begin{equation}  \label{eqno{(2.4)}}
B=B(N, \sigma,\varepsilon)=
\frac{\rho}{32}\left(\frac{\varepsilon^2}{8\sigma^4\sqrt{N}}\right)^2f_2\left(\frac{2\varepsilon^2}{8\sigma^4\sqrt{N}}\right)
+\O\left(\frac{8\sigma^2}{\varepsilon^2}\right)
\end{equation}
and
$$
f_2(x)=2\E\{Z^2\exp(x|Z|)\}-1.
$$
\end{lem}

{\sc Proof of Theorem \ref{Theorem1.2}.}
First we remark that limsup exists and it is unique for a multiindex sequence in a sector.
That is
$$
\limsup_{\begin{subarray}{c}{\nb\to\infty}, N\to\infty,\\ \alpha'_i<\alpha_i<\alpha''_i,\,\,1\le i\le K\end{subarray}}
\frac{|\mu_{{\sb \nb}N}-\E\mu_{{\sb}\nb N}|}{\sqrt{N\ln(N)}\sigma_{{\sb \nb}N}}
$$
is well-defined.

Since  $b_{is_i}>0$, $b_{i0}>0$, $b_{i1}>0$ and $\alpha'_i < \alpha < \alpha''_i $,   for all $1\le i\le K$,
therefore we have $0<c_1 \le \sigma^2_{{\sb \nb}N}\le 1/4$, and $\rho \sigma_{{\sb \nb}N} \rho_{{\sb \nb}N}\le 1/2$.
Let $z$ be a fixed positive number.
Therefore for  $B$ from \eqref{eqno{(2.4)}}, we have $B(N, \sigma, z \ln(N) \sigma_{{\sb \nb}N})  \le L<\infty$
as $N,{\nb}\to \infty$ such that $\alpha'_i<\alpha_i<\alpha''_i$,  $1\le i\le K$.

Now let $z>4\sqrt{1+\frac{3K}{2}}$.
Then $\frac{z^2}{16}-\frac{K}{2}-K>1$.
Therefore, by \eqref{eqno{(2.3)}} and \eqref{eqno{(2.2)}}, we have
$$
\sum_{N=N_0+1}^{\infty}\sum_{\begin{subarray}{c}
N\alpha'_i<n_i<N\alpha''_i,\\1\le i\le K\end{subarray}}
\P\left\{ \frac{|\mu_{{\sb \nb}N}-\E \mu_{{\sb \nb}N}|}{\sqrt{N\ln(N)}\sigma_{{\sb \nb}N}} \ge z\right\}=
$$
$$
= \sum_{N=N_0+1}^{\infty}\sum_{\begin{subarray}{c}
N\alpha'_i<n_i<N\alpha''_i,\\1\le i\le K\end{subarray}}
\P\left\{ \frac{|\mu_{{\sb\nb}N}-\E \mu_{{\sb\nb}N}|}{\sqrt{N}} \ge z\sqrt{\ln(N)}\sigma_{{\sb\nb}N}\right\}\le
$$
$$
\le \sup_{\begin{subarray}{c}N>N_0,\\\,\,
N\alpha'_i<n_i<N\alpha''_i,\\1\le i\le K\end{subarray}}
(1+B)\sum_{N=N_0+1}^{\infty}\sqrt{2}\frac{N^{K/2}}{C''}\prod_{i=1}^K(N(\alpha''_i-\alpha'_i))e^{-\frac{\ln(N) z^2}{16}}\le
$$
$$
\le \sup_{\begin{subarray}{c}N>N_0,\\\,\,
N\alpha'_i<n_i<N\alpha''_i,\\1\le i\le K\end{subarray}}
(1+B)\frac{\sqrt{2}}{C''} \left(\prod_{i=1}^K((\alpha''_i-\alpha'_i))\right)\sum_{N=N_0+1}^{\infty}N^{-\frac{z^2}{16}+K+\frac{K}{2}}<\infty.
$$
Consequently, by the Borel-Cantelli lemma, we have
$$
\limsup_{\begin{subarray}{c}{\nb},N\to\infty,\\
\alpha'_i<\alpha_i<\alpha''_i,\,\,1\le i\le K\end{subarray}}
\frac{|\mu_{{\sb \nb}N}-\E\mu_{{\sb}\nb N}|}{\sqrt{N\ln(N)}\sigma_{{\sb \nb}N}}  \le z\,\,\,\, \,\,\,\mbox{\text almost surely.}
$$
This and the choice of $z$ imply \eqref{eqno{(1.10)}}.
 \hfill $\Box$

In order to prove Theorem \ref{Theorem1.3}, we need the following lemma.

\begin{lem}  \label{Lemma2.3}
(Lemma 4.1 of \cite{ChuFaz2009}.)
Let $i\in\{ 1, \dots , N \}$ be fixed.
Let $0< \alpha'_i< \alpha^{''}_i$ be such that $m^{-1}_i( \alpha^{''}_i)<R_i$.
Let $\theta_{\alpha_i} = m^{-1}(\alpha_i)$.
 For any $0\le s_i<\infty$, as $N, n_i\to \infty$, uniformly for $\alpha'_i<\alpha_i<\alpha''_i$ we have
$$
{\E}\left(\frac{1}{N}\mu_{s_in_iN}\right) =\P\{\eta_{ij}=s_i\}=
\frac{b_{is_i}\theta_{\alpha_i}^{s_i}}{s_i!B_i(\theta_{\alpha_i})}
\cdot\sqrt{\frac{N}{N-1}}\cdot
\frac{ \frac{1}{\sqrt{2\pi}}\exp\left\{-\frac{\left(n_i-s_i-\frac{n_i}{N}(N-1)\right)^2}{2
\sigma^2_i(\theta_{\alpha_i})(N-1)}\right\}+\o_{1i}(1)}
{\frac{1}{\sqrt{2\pi}}+\o_{2i}(1) },
$$
where $\o_{1i}, \o_{2i}\to 0$.
Here $\mu_{s_in_iN}$ is the number of boxes containing $s_i$ balls after placing $n_i$ balls into $N$ boxes.
\end{lem}

{\sc Proof of Theorem \ref{Theorem1.3}.}
Observe that
\begin{equation}  \label{eqno{(2.5)}}
\frac{1}{N} \mu_{{\sb\nb}N}= \frac{\mu_{{\sb\nb}N}-\E\mu_{{\sb\nb}N}}{N}+\E\left(\frac{1}{N}\mu_{{\sb\nb}N}\right).
\end{equation}
By  \eqref{mu} and Lemma  \ref{Lemma2.3}, we obtain
$$
{\E}\left(\frac{1}{N}\mu_{{\sb\nb}N}\right)
=\prod_{i=1}^K\P\{\eta_{ij}=s_i\}=\prod_{i=1}^K \frac{b_{is_i}\theta_{\alpha_i}^{s_i}}{s_i!B_i(\theta_{\alpha_i})}
\cdot\sqrt{\frac{N}{N-1}}
\cdot \frac{\frac{1}{\sqrt{2\pi}}\exp\left\{-\frac{\left(n_i-s_i-\frac{n_i}{N}(N-1)\right)^2}{2\sigma^2_i(\theta_{\alpha_i})(N-1)}\right\}+\o_{1i}(1)}
{\frac{1}{\sqrt{2\pi}}+\o_{2i}(1) }.
$$
Therefore we have
\begin{equation}  \label{eqno{(2.6)}}
\E\left(\frac{1}{N}\mu_{{\sb\nb}N}\right)\to
\prod_{i=1}^K\frac{b_{is_i}\theta^{s_i}_{\alpha_{i0}}}{s_i!B_i(\theta_{\alpha_{i0}})},\,\,\,\mbox{\text as}\,\,\, n_i,N\to\infty\,\,\,
\mbox{\text such that}\,\,\,\,n_i/N= \alpha_i\to\alpha_{i0}, \,\,\,\,1\le i\le K.
\end{equation}
By Corollary 1.1
\begin{equation}  \label{eqno{(2.7)}}
\frac{\mu_{{\sb\nb}N}-\E \mu_{{\sb\nb}N}}{N}\to 0,\,\,\,\mbox{\text as}\,\,\, n_i,N\to\infty\,\,\,\mbox{\text such that}
\,\,\,\,n_i/N= \alpha_i\to\alpha_{i0}, \,\,\,\,1\le i\le K,\,\,\,\mbox{\text almost surely}.
\end{equation}
From  \eqref{eqno{(2.5)}}, by \eqref{eqno{(2.6)}} and \eqref{eqno{(2.7)}}, follows \eqref{eqno{(1.11)}}.
 \hfill $\Box$

config: arxiv


TITLE: How to find intersection point of two 3D lines
QUESTION [1 upvotes]: I know the $x,y,z$ values of the 4 points that create two lines. I also know the $x,y$ value of the crossing point. How do I get the $z$ of the crossing point?

REPLY [1 votes]: given four points $\mathbf{a,b,c,d}$, form the parametric equations
$\mathbf{a}+t \mathbf{(b-a)}$ and $\mathbf{c}+s \mathbf{(d-c)}$, where $s,t \in \mathbb R$ are parameters.
This will look like $\ell_1:=\{(a_1,a_2,a_3)+t(b_1-a_1,b_2-a_2,b_3-a_3) \mid t \in \mathbb R\}$, and analogous for $\ell_2$.
If you know the $x,y$ values for the intersection, then there is a system of linear equations:
$x=a_1+t(b_1-a_1)=c_1+s(d_1-c_1)$ and $y=a_2+t(b_2-a_2)=c_1+s(d_2-c_2)$. Solve these for $s,t$ and plug them back into the parametric equations to get the $z$ value.


TITLE: Efficient method for computing the product of the first 8 terms of a recursive sequence
QUESTION [2 upvotes]: The problem I am trying to solve is the following:
Let $x_1=97,$ and for $n>1,$ define $x_n=\frac{n}{x_{n-1}}.$ Calculate $x_1x_2 \cdots x_8.$
I tried the painstaking fail safe method for the manual computation of each term.
$x_2=\frac{2}{97}$, $x_3=\frac{291}{2}$, $x_4=\frac{8}{291}$, $x_5=\frac{1455}{8}$, $x_6=\frac{48}{1455}$, $x_7=\frac{10185}{48}$, and $x_8=\frac{384}{10185}$.
However, I realize that actually finding the product of these terms is highly inefficient and impractical in a math contest with no calculator.
My question is, what I can I do to solve this more timely? Is there a closed form shortcut?
Thank you.

REPLY [3 votes]: Notice that $x_1·x_2 = \color {red}{2}$, $x_2·x_3 = \color {red}{3}$, and the same pattern continues to $x_7 · x_8 = \color {red}{8}$. Therefore, multiplying $$(x_1·x_2)·(x_3·x_4)·(x_5·x_6)·(x_7·x_8)$$ is equal to $2·4·6·8 = 384$ for all situations, regardless of $x_1$.

Your answer is 384.

The closed form is 384, and the same for recursive.


TITLE: Find the area of the parallelogram with vertices (4,1), (6, 6), (7, 7), and (9, 12).
QUESTION [0 upvotes]: I am trying to find the area of the parallelogram with vertices (4,1), (6, 6), (7, 7), and (9, 12).
So I believe the way to solve this problem is through the cross product and then taking the magnitude. However, I got the wrong answer and I am now rethinking my methods.
My original work:
Point A:(4,1)
Point B: (6,6)
Point C:(7,7)
Point D: (9,12)
I took the cross product of AB and AC and took the magnitude of that and ended up getting sqrt(369).
I would appreciate the help. I am kind of stumped.

REPLY [0 votes]: area should be 3 square units.


TITLE: Newton's method with Hessian Matrix
QUESTION [2 upvotes]: Let's say we want to use Newton's method to find optimal $x_*$ for $f:\mathbb{R}^n \to \mathbb{R}$ , with
$x_{t+1} = x_t + H_f(x_t)^{-1}\nabla f(x_t) $
Can $H_f(x_t)^{-1}$ be calculated only once and used in every iteration step, or do we need to calculate it every time?
Does equation $H_f(x_0)(x_*-x_0) = \nabla f(x_0)$ need to be calculated only once to recieve optimal value?

REPLY [1 votes]: "Can $H_f(x_t)^{−1}$ be calculated only once and used in every iteration step, or do we need to calculate it every time?"
No, the equation
$$
H_f(x_t)(x_{t+1} - x_t) = - \nabla f(x_t)
$$
needs to be solved at every iteration. This is the reason every iteration in Newton's method is costly compared to other methods with slower convergence. The exception is the quadratic problem
$$
\min f(x) , \quad f(x) = \frac{1}{2}x^T A x + b^T x
$$
with $\nabla f(x) = A x + b$ and $H_f(x) = A$. This problem is exactly solved by one step of Newton's.
$$
\begin{align} A(x_1 - x_0) &= - A x_0 - b \\
x_1 &= -A^{-1}b
\end{align}
$$
for which we see that $\nabla f(x_1) = 0$. Provided that $A$ is positive semidefinite this is a solution to $\min f(x)$.


TITLE: How is the coradical filtration defined?
QUESTION [0 upvotes]: I have seen the coradical filtration of a coalgebra $C$ defined as follows:
$C_0 = \text{sum of all simple subcoalgebras of }C$;
for any $n\geq 1$, let $C_n$ be $\Delta^{-1}\left(C\otimes C_{n-1}+C_{n-1}\otimes C\right)$.
Now I am trying to prove that this really is a coalgebra filtration, and something seems not to work. Is it possible that $C_n$ should rather be $\Delta^{-1}\left(C\otimes C_0+C_{n-1}\otimes C\right)$ ? Or is this secretly the same?
(Motivation: I am working with the dual algebra $C^{\ast}$, at least in the case of $C$ finite-dimensional. In this case, if $J$ denotes the Jacobson radical of $C^{\ast}$, then we have $C_n^{\perp}=J^{2^n}$ if $C_n$ is defined as $\Delta^{-1}\left(C\otimes C_{n-1}+C_{n-1}\otimes C\right)$, we have $C_n^{\perp}=J^{n+1}$ if $C_n$ is defined as $\Delta^{-1}\left(C\otimes C_1+C_{n-1}\otimes C\right)$. Now, if my computations are right, $\left(C_0,C_1,C_2,...\right)$ is a coalgebra filtration if and only if $\left(C^{\ast},C_0^{\perp},C_1^{\perp},C_2^{\perp},...\right)$ is an algebra filtration. The latter holds for $C_n^{\perp}=J^{n+1}$ but not for $C_n^{\perp}=J^{2^n}$...)

REPLY [0 votes]: I am voting to close this. $C_n$ should be defined as $\Delta^{-1}\left(C\otimes C_0+C_{n-1}\otimes C\right)$. My wrong definition was due to my bad memory. Sorry for spamming.


TITLE: algebraic dependence over Q
QUESTION [0 upvotes]: Are numbers $\sqrt{2}$ and $e$ algebraically dependent over $\mathbb{Q}$?
If yes, they belong to the same Mahler class. However, $\sqrt{2}$ is A-number, while $e$ is S-number.
On the other hand, if we consider non-zero polynomial $P(x,y) = x^2y - 2y$, then clearly $P(\sqrt{2},e) = 0$, hence they are algebraically dependent.
What is wrong?
Thank you in advance.

REPLY [0 votes]: That's a factoring mistake; but to answer your question: no.
y(x^2-1)=0  has two solutions but e != 0 so only the second need apply.
It's easy to prove that this approach doesn't work; given that e is transcendental.
I am sure there are stronger proofs but here is an elementary one:
Suppose they were algebraically dependent over R:
say for P(e,sqrt(2))
now let m=sqrt(2)
Separate even and odd powers of m in P(e,m)
= Q(e,m^(2n)) + R(e,m^(2p+1); here n,p can be zero.
Rewrite it as
Q(e,m^(2n)) + m*S(e,m^(2p))
Form Q(e,m^(2n)) - m*S(e,m^(2p)).
Then multiply and we get:
Q()^2 - m^2 * S()^2. and all terms in m are even and thus multiples of 2.
But this would be an algebraic polynomial in e over R .
Which doesn't exist.
QED


text:
\begin{document}

\title{The metric dimension of the annihilating-ideal graph of a finite commutative ring}
\author{David Dol\v zan}
\date{\today}

\address{D.~Dol\v zan:~Department of Mathematics, Faculty of Mathematics
and Physics, University of Ljubljana, Jadranska 21, SI-1000 Ljubljana, Slovenia; e-mail:
david.dolzan@fmf.uni-lj.si}

 \subjclass[2010]{05C25, 16P60, 13F10}
 \keywords{finite ring, metric dimension, annihilating-ideal graph}
  \thanks{The author acknowledges the financial support from the Slovenian Research Agency  (research core funding No. P1-0222)}

\bigskip

\begin{abstract}
We determine the metric dimension of the annihilating-ideal graph of a local finite commutative principal ring and a finite commutative principal ring with two maximal ideals. We also find the bounds for  the metric dimension of the annihilating-ideal graph of an arbitrary finite commutative principal ring.
\end{abstract}

\maketitle

\section{Introduction}

\bigskip

One of the most important and active areas in algebraic combinatorics is the study
of graphs associated with different algebraic structures. This field has attracted many researchers during the past 30 years.

One of the most basic concepts in the study of rings is the notion of a zero-divisor. Thus, in 1988, Beck \cite{beck88} first introduced the concept of the zero-divisor graph of a commutative ring. In 1999, Anderson and Livingston \cite{andliv99} made a slightly different definition of the zero-divisor graph in order to be able to investigate the zero-divisor structure of commutative rings.

In \cite{AndBad08}, Anderson and Badawi introduced a similar notion of a total graph of a
commutative ring $R$ as the graph with all elements of $R$ as vertices, and for distinct
$x, y \in R$, the vertices $x$ and $y$ are adjacent if and only if $x + y$ is a zero-divisor in $R$.

In \cite {behboodi1} and \cite {behboodi2}, the authors defined and investigated an ideal-theoretic version of the zero-divisor graph, called the annihilating-ideal graph of a commutative ring. If $R$ is a commutative ring, then its annihilating-ideal graph, $\AG(R)$, is the graph whose vertices are the nonzero ideals of $R$ which have nontrivial annihilators, and in which there is an edge between two distinct ideals $I$ and $J$ if and only if $IJ = 0$. The annihilating-ideal graph is a natural object of study, since many facts about zero-divisors are easily expressed in the language of ideals. The annihilating-ideal graph eliminates some of the redundancy of the standard zero-divisor graph, and encodes some the the ring theoretic information more efficiently.
On the other hand, since the annihilator-ideal graph reflects only information about the ideals of a ring, it cannot make certain fine distinctions between nonisomorphic rings which have very similar zero-divisor behavior. For example, $\AG(\ZZ_{16})$ and $\AG(\ZZ_{81})$ are isomorphic as graphs (each is a path of length 3) despite the fact that $\ZZ_{16}$ and $\ZZ_{81}$ are not isomorphic as rings.  Much study has been devoted to the subject of annihilating-ideal graphs (see for example \cite{aalipour, alini, curtis, nikandish, shaveisi, tamizh}).

The sequence of edges $x_0 - x_1$, $ x_1 - x_2$, ..., $x_{k-1} - x_{k}$ in a graph is called \emph{a path of length $k$}. The \DEF{distance} between vertices $x$ and $y$ is the length of the shortest
path between them, denoted by $d(x,y)$.
The \DEF{diameter} $\diam{\Gamma}$ of the graph $\Gamma$ is the longest distance between any two vertices of the graph.

For an ordered subset $W=\{ w_1,w_2,\ldots,w_k\}$ of the vertex set of graph $G$ and a vertex $v$ of $G$ the $k$-vector
$r(v|W)=(d(v,w_1),d(v,w_2),\ldots,d(v,w_k))$ is called the \DEF{representation} of $v$ with respect to $W$. A set $W$ is called a \DEF{resolving set} for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set of minimal cardinality for $G$ is a \DEF{basis} of $G$ and the cardinality of the basis is called the \DEF{metric dimension} of $G$, denoted by $\MD(G)$ \cite{chartrand}. Motivated by the problem of uniquely determining the location of an intruder in a network, Slater \cite{slater} introduced the concept of a metric dimension. The metric dimension was then studied by Harary and Melter \cite{harary} and it has appeared in various applications of graph theory, for example pharmaceutical chemistry \cite{cameron, chartrand}, robot navigation \cite{khuller}, combinatorial optimization \cite{sebo} and sonar and coast guard long range navigation \cite{slater}.
It turns out that determining the metric dimension of a graph remains a NP-complete problem even in special cases like bounded-degree planar graphs \cite{diaz}, or split graphs, bipartite graphs and their complements, line graphs of bipartite graphs \cite{epstein}.

Recently, Faisal et al. \cite{faisal} studied the metric dimension of the commuting graph of a dihedral group. In the ring setting, the metric dimension of a zero-divisor graph of a commutative ring was studied in \cite{pirzada}, while the metric dimension of a total graph of a finite commutative ring was studied in \cite{dolzan1}.

In this paper, we study the metric dimension of the annihilating-ideal graph of a commutative ring. Our main result is to exactly determine the metric dimension of the annihilating-ideal graph of a local finite commutative principal ring and a finite commutative principal ring with two maximal ideals. We also find the bounds for  the metric dimension of the annihilating-ideal graph of an arbitrary finite commutative principal ring (see Theorem \ref{main}).

\bigskip

\bigskip
\section{The metric dimension of the annihilating-ideal graph}
\bigskip

In this section, we shall investigate the metric dimension of the annihilating-ideal graph of a finite ring.
As is well known (see for example \cite[Theorem VI.2]{mcdonald}), every finite commutative ring can be written as a direct sum of local rings. Also,
(see for example \cite[Proposition IV.7]{mcdonald}) the Jacobson radical $J$ of a finite ring $R$ is nilpotent. Thus there exists $n \in \NN$ such that $J^n=0$ and $J^{n-1} \neq 0$. We shall call this $n$ \emph{the nilpotency order} of $J$.
Recall, that a ring $R$ is called a \emph{chain ring} if all its ideals form a chain under inclusion. A well known result (see for example \cite[Theorem XVII.5]{mcdonald}) states that every finite principal local commutative ring is a chain ring.

Next, we shall also need the following definition.

\bigskip

\begin{Def}
Let $v$ be a vertex of a graph $G$. Then the \emph{open neighbourhood} of $v$ is $N(v)=\{u \in V(G); \text{ there exists an edge } uv \text { in G}\}$ and the \emph{closed neighbourhood} of $v$ us $N[v]=N(v) \cup \{v\}$.

\end{Def}

\bigskip

We now have to investigate the distances between the ideals in $\AG(R)$. We know that any two ideals in $\AG(R)$ are at distance at most 3 (see \cite[Theorem 2.1]{behboodi1}). The next lemma describes the distances between ideals in $\AG(R)$ in more of a detail.

\bigskip

\begin{Lemma}\label{distance2}
Let $R$ be a finite ring and $R \simeq R_1 \times R_2 \times \ldots \times R_n$ where for each $i=1,2,\ldots,n$, the ring $R_i$ is a local ring with the Jacobson radical $J_i$ of nilpotency order $n_i$. Let $\pi_s$ denote the canonical projection of $R$ onto $R_s$.  Let $M, N$ be distinct ideals in $\AG(R)$. Then $d(M,N) = 3$  if and only if $R_s \in \{\pi_s(M), \pi_s(N)\}$ for all $s=1,2, \ldots, n$ and there exists $k \in \{1,2, \ldots, n\}$ such that $0 \notin \{\pi_k(M), \pi_k(N)\}$.
\end{Lemma}
\begin{proof}
 Let $I_{s,k}$ be an ideal of $R$ such that $\pi_i(I_{s,k})=0$ for all $i \neq s$ and $\pi_s(I_{s,k})=J_s^k$.

If $0 \in \{\pi_k(M), \pi_k(N)\}$ for all $k  \in \{1,2, \ldots, n\}$, then $d(M, N)=1$. If there exists $s \in \{1,2,\ldots,n\}$ such that $R_s \notin \{\pi_s(M), \pi_s(N)\}$ then $M$ and $N$ are both connected to $I_{s,n_s-1}$, so $d(M,N) \leq 2$. Conversely, suppose that $R_s \in \{\pi_s(M), \pi_s(N)\}$ for all $s=1,2,\ldots,n$ and there exists $k \in \{1,2, \ldots, n\}$ such that $0 \notin \{\pi_k(M), \pi_k(N)\}$. The latter condition yields that $d(M,N) \neq 1$. If $d(M,N) = 2$ then there exists $T \in \AG(R)$ such that $T$ is connected to $M$ and $N$. However, this implies that $\pi_s(T)=0$ for all $s=1,2,\ldots,n$ which is a contradiction.
\end{proof}

\bigskip

Suppose $R$ is a a finite commutative principal ring with exactly $n$ maximal ideals.
In the next theorem, we exactly determine the metric dimension of $\AG(R)$ in case $n \leq 2$ and find the bounds for metric dimension of $\AG(R)$ in case $n \geq 3$.

\bigskip

\begin{Theorem}\label{main}
Let $R$ be a finite commutative principal ring. Then $R \simeq R_1 \times R_2 \times \ldots \times R_n$ where for each $i=1,2,\ldots,n$, the ring $R_i$ is a local chain ring with the Jacobson radical $J_i$ of nilpotency order $n_i$. Moreover, the following statements hold.
\begin{enumerate}
\item
If $n=1$ then $\MD(\AG(R)) =\lfloor{\frac{n_1-1}{2}}\rfloor$.
\item
If $n =2$ then $\MD(\AG(R)) = n_1 + n_2 -2+\epsilon$, where $\epsilon=1$ if $R_1, R_2$ are both fields and $\epsilon=0$ otherwise.
\item
If $n \geq 3$ then $\left(\sum_{i=1}^n{n_i}\right)-n+\epsilon \leq \MD(\AG(R)) \leq \sum_{i=1}^n{n_i}$, where $\epsilon=0$ if none of $R_1,R_2,\ldots,R_n$ are fields and $\epsilon=\lceil\log_2(\beta)\rceil$, where $\beta$ denotes the number of rings $R_i$ that are fields.
\end{enumerate}
\end{Theorem}
\begin{proof}
By the comments at the beginning of this section, we know that $R \simeq R_1 \times R_2 \times \ldots \times R_n$ where for each $i=1,2,\ldots,n$, the ring $R_i$ is a local chain ring with the Jacobson radical $J_i$ of nilpotency order $n_i$.

Suppose first that $n=1$. Since $R$ is a local chain ring, the set of vertices in $\AG(R)$ is equal to $\{J, J^2, \ldots, J^{n_1-1} \}$, where $J=J_1$ denotes the Jacobson radical of $R$ of nilpotency order $n_1$. If $n_1 \leq 2$, then $\AG(R)$ is either an empty graph or a singleton, so we can assume that $n_1 \geq 3$. By Lemma \ref{distance2}, we have that $\diam{\AG(R)} \leq 2$. This implies that if $X$ is a resolving set for $\AG(R)$, no two vertices outside $X$ can have exactly the same neighbours in $X$. Now, for each $k \in \{1,2,\ldots,n_1-2\}$, observe that $N[J^{k+1}] = N[J^{k}] \cup \{ J^{n_1-k-1}\}$.

This implies that any vertex $J^k$ in the resolving set differentiates between two sets of vertices: the vertices $\{J, \ldots, J^{n_1-k-1}\}$ that are not connected to $J^k$ and the vertices $\{J^{n_1-k}, \ldots, J^{n_1-1}\}$ that are connected to $J^k$. The resolving set has to contain all vertices such that any two vertices are differentiated for by at least one of the vertices in the resolving set. So, if the resolving set contains $s$ vertices, then the remaining $n_1-1-s$ vertices have to be differentiated into singletons by putting $s$ differentiating markers between them. But to separate  $n_1-1-s$ vertices into singletons one needs to put down at least $n_1-2-s$ differentiaing markers. Therefore,
$s \geq n_1-2-s$ and thus $s \geq \frac{n_1-2}{2}$. Since $s$ is an integer, $s \geq \lceil{\frac{n_1-2}{2}}\rceil=\lfloor{\frac{n_1-1}{2}}\rfloor$. We have thus proved that each resolving set contains at least $\lfloor\frac{n_1-1}{2}\rfloor$ elements, so $\MD(\AG(R)) \geq \lfloor{\frac{n_1-1}{2}}\rfloor$.
Conversely, we prove that $X=\{J, J^2, \ldots, J^{\lfloor{\frac{n_1-1}{2}}\rfloor}\}$ is a resolving set for a local chain ring $R$ with the Jacobson radical $J$ of nilpotency order $n_1$. If $n_1$ is even, then  $X=\{J, J^2, \ldots, J^{\frac{n_1}{2}-1}\}$ and each $J^{\frac{n_1}{2}-1+k}$ is connected exactly to the first $k-1$ elements from $X$. On the other hand, if $n_1$ is odd, then  $X=\{J, J^2, \ldots, J^{\frac{n_1-1}{2}}\}$ and each $J^{\frac{n_1-1}{2}+k}$ is connected exactly to the first $k$ elements from $X$. Thus, $\MD(\AG(R)) \leq \lfloor{\frac{n_1-1}{2}}\rfloor$.

Suppose now that $n \geq 2$.
Let $\pi_s$ denote the canonical projection of $R$ onto $R_s$.  Choose $s \in \{1,2,\ldots,n\}$ and $k \in \{0,1,\ldots,n_s-1\}$ and let $I_{s,k}$ be an ideal of $R$ such that $\pi_i(I_{s,k})=0$ for all $i \neq s$ and $\pi_s(I_{s,k})=J_s^k$.

Consider first the case $n=2$. Now, we have three possibilites.

If $R_1$ and $R_2$ are both fields, then define $X=\{I_{1,0}\}$ and observe that $\vert X \vert = 1 = n_1+n_2-2 + 1$. Since $\AG(R)$ has only two vertices, $X$ is obviously a resolving set.

If exactly one of the rings $R_1$ and $R_2$ is a field (say, $R_2$) then define $X=\{I_{1,k}; k \in \{0,1,\ldots,n_1-2\} \}$ and observe that $\vert X \vert = n_1-1 = n_1+n_2-2$. Choose $M \neq L \in \AG(R)$. Then $M=J_1^{m_1} \times J_2^{m_2}$ and $L=J_1^{l_1} \times J_2^{l_2}$
for some integers $0 \leq m_1, m_2 \leq n_1$ and $0 \leq l_1, l_2 \leq 1$. Since $M \neq L$, we have $m_1 \neq l_1$ or $m_2 \neq l_2$. If $m_1=0$ then $M=R_1 \times 0$, so $M \in X$ and we can reason similarly for $l_1$. So, we can assume that $m_1, l_1 \geq 1$. Suppose first that $m_1 \neq l_1$. We can also suppose without loss of generality that $m_1 < l_1$. Since $m_1 \geq 1$, we have $d(M,I_{1,n_1-m_1-1}) > 1$, while $d(L,I_{1,n_1-m_1-1}) = 1$.  So, suppose now that $m_1=l_1$. Then we can assume without loss of generality that $M=J_1^{m_1} \times 0$ and $L=J_1^{m_1} \times R_2$. But then by Lemma \ref{distance2}, we get $d(M,I_{1,0}) = 2$, while $d(L,I_{1,0}) = 3$.
This proves that $X$ is a resolving set.

Finally, suppose neither of $R_1$ and $R_2$ are fields.
Define $X=\{I_{s,k}; s \in \{1,2\}$ and $k \in \{0,1,\ldots,n_s-2\} \}$ and observe that $\vert X \vert = n_1-1+n_2-1 = n_1+n_2-2$.
Again, choose $M \neq L \in \AG(R)$. Then $M=J_1^{m_1} \times J_2^{m_2}$ and $L=J_1^{l_1} \times J_2^{l_2}$
for some integers $0 \leq m_1, m_2 \leq n_1$ and $0 \leq l_1, l_2 \leq n_2$. Since $M \neq L$, we have $m_1 \neq l_1$ or $m_2 \neq l_2$.
We can assume without loss of generality that $m_1 < l_1$. If $m_1=0$ then $M=R_1 \times J_2^{m_2}$ and this implies by Lemma \ref{distance2} that $d(M,I_{2,0}) = 3$, while $d(L,I_{2,0}) \leq 2$. On the other hand, if $m_1 \geq 1$, then $d(M,I_{1,n_1-m_1-1}) > 1$, while $d(L,I_{1,n_1-m_1-1}) = 1$.
This proves again that $X$ is a resolving set.

Since in all three cases, we have $\vert X \vert = n_1+n_2-2 + \epsilon$, where $\epsilon=1$ if $R_1, R_2$ are both fields and $\epsilon=0$ otherwise. Therefore, we have proved that in the case $n=2$, we have $\MD(\AG(R)) \leq n_1+n_2-2+\epsilon$.

Suppose now that $n \geq 3$. Define $X=\{I_{s,k}; s \in \{1,2,\ldots,n\}$ and $k \in \{0,1,\ldots,n_s-1\} \}$ and observe that $\vert X \vert = \sum_{i=1}^n{n_i}$.
Choose $M \neq L \in \AG(R)$. Then $M=J_1^{m_1} \times J_2^{m_2} \times \ldots \times J_n^{m_n}$ and $L=J_1^{l_1} \times J_2^{l_2} \times \ldots \times J_n^{l_n}$
for some integers $m_1, m_2, \ldots, m_n, l_1, l_2, \ldots, l_n$ with $0 \leq m_i,l_i \leq n_i$ for all $i \in \{1,2,\ldots,n\}$. Since $M \neq L$, we have $i$ such that $m_i \neq l_i$. We can suppose without any loss of generality that $m_i < l_i$. Therefore $m_i \leq n_i-1$ and $d(M,I_{i,n_i-m_i-1}) > 1$, while $d(L,I_{i,n_i-m_i-1}) = 1$.
This proves that $X$ is a resolving set and thus $\MD(\AG(R)) \leq \sum_{i=1}^n{n_i}$.
We have thus established all the upper bounds stated in the theorem in the case $n \geq 2$.

We now have to find the lower bounds.
Therefore, let $n \geq 2$ and let $X$ be the resolving set for $\AG(R)$.  For $s \in \{1,2,\ldots,n\}$ and $k \in \{0,1,\ldots,n_s-1\}$ , let $L_{s,k}$ be an ideal of $R$ such that $\pi_i(L_{s,k})=R_i$ for all $i \neq s$ and $\pi_s(L_{s,k})=J_s^{n_s-k}$.

If $I_{s,k}, \ldots, I_{s,k+t} \notin X$ for some $0 \leq t \leq n_s-2-k$, then by Lemma \ref{distance2}, we have  $d(L_{s,k}, I)=\ldots=d(L_{s,k+t+1},I)$ for all ideals $I$ in $X$. Since again by Lemma \ref{distance2}, we have
$d(L_{s,k},L_{s,k+r})=2$ for all $1 \leq r \leq n_s-1-k$, then we can conclude that at least $t$ of the ideals $L_{s,k}, \ldots, L_{s,k+t+1}$ are elements of $X$ .
Consequently, for every $s \in \{1,2,\ldots,n\}$ we have
\begin{equation}\tag{a}\label{ILeq}
\vert \{I_{s,k}; I_{s,k} \notin X, k=0,1,\ldots, n_s-2\} \vert \leq \vert \{L_{s,k}; L_{s,k} \in X, k=0,1,\ldots, n_s-1\} \vert.
\end{equation}

If $n=2$, define $\II = \emptyset$ and $\LL=\emptyset$ and if $n \geq 3$, define the sets $\II = \bigcup_{s=1,k=0}^{n,n_s-2}{I_{s,k}}$, $\LL =  \bigcup_{s=1,k=0}^{n,n_s-1}{L_{s,k}}$.

Let $N_F = \{s  \in \{1,2,\ldots, n\}; R_s $ is a field$\}$, so $\beta = \vert N_F \vert$. If $\beta \leq 1$ then define $\MM = \emptyset$. Assume now that $\beta \geq 2$. For each subset $N_F' \subseteq N_F$ of cardinality $1 \leq t \leq \beta$, we shall prove that there exists an integer $k \geq \lceil\log_2(t)\rceil$ and distinct ideals $M_1, M_2, \ldots, M_{k} \in X$ such that $\{M_1, M_2, \ldots, M_{k}\} \cap (\II \cup \LL) = \emptyset$. We shall prove this by induction on $t$.  If $t=1$, there is obviously nothing to prove.

Now, assume that the statement holds for $t$ and let us prove it holds also for $t+1$. Choose $s_1, s_2 \in N_F'$. The fact that $X$ is a resolving set gives us the following two possibilities: either at least one of the ideals $I_{s_1,0}$ and $I_{s_2,0}$ is in $X$, or there exists an ideal $M \in X$ such that $d(I_{s_1,0},M) \neq d(I_{s_2,0},M)$. Obviously, $I_{s_1,0}, I_{s_2,0}, M \notin \II \cup \LL$, so in each case we have found an ideal in $X$ that is not in $\II \cup \LL$. Denote this ideal by $N$. Now, $\pi_s(N) \in \{0,R_s\}$ for all $s \in N_F'$. Let $N_F'(1) = \{s; \pi_s(N)=0\}$ and $N_F'(2)=N_F' \setminus N_F'(1)$. Denote by $f_1$ and $f_2$ the cardinalities of $N_F'(1)$ and $N_F'(2)$, respectively. Suppose that $f_1 \geq f_2$ (in the other case the proof is symmetrical). Thus, $f_1 \geq \frac{t}{2}$ and by the induction hypothesis there exists an integer $k \geq \lceil\log_2(\frac{t}{2})\rceil$ and distinct ideals $M_1, M_2, \ldots, M_{k} \in X$ such that $\{M_1, M_2, \ldots, M_{k}\} \cap (\II \cup \LL) = \emptyset$. We define $M_{k+1} = N$.  Since $d(I_{s_1',0},N) = d(I_{s_2',0},N)$ for all $s_1',s_2' \in N_F'(1)$, the ideal $N$ is distinct from all the ideals $M_1, M_2, \ldots, M_{k}$.  Thus, we have found $1+k \geq 1 + \lceil\log_2(\frac{t}{2})\rceil \geq \lceil\log_2(t)\rceil$ ideals in $X \setminus \II \cup \LL$ and the statement follows.
We now use this statement for the set $N_F$ of cardinality $\beta$ and let $\MM$ denote the set of ideals obtained in this way, where $\vert \MM \vert \geq \lceil\log_2(\beta)\rceil$.

Now define $X' = (X \cup \II \cup \MM) \setminus \LL = (X \cup \II) \setminus \LL$.
Again, suppose first that $n=2$. If $R_1$ is not a field, then $X$ contains by the inequality (\ref{ILeq}) at least $n_1-1$ of the ideals from the set $\{I_{1,0}, I_{1,1}, \ldots, I_{1,n_1-2}, L_{1,0}, L_{1,1},\ldots,L_{1,n_1-1}\}$ (obviously this also holds in case $R_1$ is a field, since then $n_1-1=0$).
Similarly, we find $n_2-1$ ideals from $X$ from the set $\{I_{2,0}, I_{2,1}, \ldots, I_{2,n_1-2}, L_{2,0}, L_{2,1},\ldots,L_{2,n_1-1}\}$. However, if $I_{1,0} = L_{2,0} \in X$ then again by the inequality (\ref{ILeq}) we know that there are $n_1-2$ ideals in $X$ from the set $\{I_{1,1}, I_{1,2}, \ldots, I_{1,n_1-2}, L_{1,1}, L_{1,2},\ldots,L_{1,n_1-1}\}$. Similarly, if $I_{2,0} = L_{1,0} \in X$ then we find $n_2-2$ ideals in $X$ from the set  $\{I_{2,1}, I_{2,2}, \ldots, I_{2,n_1-2}, L_{2,1}, L_{2,2},\ldots,L_{2,n_1-1}\}$. This always yields at least  $n_1+n_2-2$ ideals in $X$, so $\vert X \vert \geq n_1+n_2-2$ if at least one of the rings $R_1$ and $R_2$ is not a field, and $\vert X \vert \geq 1 = n_1 + n_2 - 2 + 1$ otherwise.  Therefore,
$\MD(\AG(R)) \geq n_1+n_2-2+\epsilon$, where $\epsilon = 1$ if $R_1, R_2$ are both fields and $\epsilon=0$ otherwise.

If $n \geq 3$, we have $\vert X' \vert \leq \vert X \vert$ by the inequality (\ref{ILeq}). The fact that $n \geq 3$ implies that $\II \cap \LL = \emptyset$, so by the construction of $X'$, we have $I_{s,k} \in X'$ for all  $s \in \{1,2,\ldots,n\}$ and $k \in \{0,1,\ldots,n_s-2\}$. Thus, since $\II \cap \MM = \emptyset$, we arrive at $\vert X' \vert \geq \left(\sum_{i=1}^n{n_i}\right)-n+\epsilon$, where $\epsilon=\lceil\log_2(\beta)\rceil$.
This yields $\vert X \vert \geq \vert X' \vert \geq \left(\sum_{i=1}^n{n_i}\right)-n+\epsilon$, therefore
$\MD(\AG(R)) \geq \left(\sum_{i=1}^n{n_i}\right)-n+\epsilon$ and thus the theorem holds.
\end{proof}

\bigskip

\bigskip


TITLE: Monoidal triangulated categories
QUESTION [5 upvotes]: I have a monoidal (not symmetric) triangulated category $(A,\otimes, 1)$ with unit 1.
Define $C$ the localizing subcategory of $A$ generated by the unit 1.

is $(C, \otimes, 1) $ a symmetric monoidal triangulated category?
Do we have a natural isomorphism $c\otimes a\cong a\otimes c$ for any $a\in A$ and any $c\in C$ ?

REPLY [5 votes]: The answer to question 2, even with the assumption that $a\in C$, is no in general. It follows that the answer to question 1 is also no.
For a counterexample, one can consider for example a (derived) category of bimodules. Let $k$ be a base commutative ring, and $R$ a (say) flat $k$-algebra. Consider the derived category $A= D(R\otimes_k R^{op})$ of $(R,R)$-bimodules over $k$. This is monoidal under $\otimes^\mathbb L_R$, with unit $R$ viewed as an $R$-bimodule in the canonical way.
An explicit example is given by the polynomial ring $R= k[t]$. In this case, $R\otimes_k R^{op} = k[t_0,t_1]$.
There is $k[t_0,t_1]$-linear extension $0\to k[t]\to k[t_0,t_1]/(t_0-t_1)^2\to k[t]\to 0$, where the rightmost map is the algebra map $t_0,t_1\mapsto t$, while the leftmost map is $P\mapsto (t_0-t_1)P(t_0,t_0)$. One easily checks that this is an extension: first, the rightmost map is clearly a bimodule map. For the leftmost map, one checks that $(t_0-t_1)t_1P(t_0,t_0) = (t_0-t_1)t_0P(t_0,t_0)$. Indeed it suffices to check it when $P = 1$ and then the relation is $t_0t_1-t_1^2 = t_0^2-t_1t_0$ which is a rephrasing of the relation $(t_0-t_1)^2 = 0$.
Second, suppose $P(t,t) = 0$. Then $P$ is divisible by $(t_0-t_1)$, to $P = (t_0-t_1)Q$ for some $Q$, and now $(t_0-t_1)Q = (t_0-t_1)Q(t_0,t_0)$ modulo $(t_0-t_1)^2$, because $Q-Q(t_0,t_0)$ is divisible by $(t_0-t_1)$. It follows that $P$ is in the image of the leftmost map.
This extension corresponds to a morphism $k[t]\to \Sigma k[t]$ in $A$, with fiber $E= k[t_0,t_1]/(t_0-t_1)^2$. In particular, $E$ belongs to $C$.
Another object in $C$ is $k$ where $t_0,t_1$ act trivially. Indeed, it is the mapping cone of $k[t]\xrightarrow{t}k[t]$ (this is a bimodule map, as $t$ is central).
I claim that $E\otimes^\mathbb L_{k[t]}k \not\simeq k\otimes_{k[t]}^\mathbb L E$.
To see this, we first observe that these derived tensor products are underived. The key lemma for this is:
Lemma: Suppose $(t_0-t_1)$ divides $t_0 P$. Then $(t_0-t_1)$ divides $P$.
Proof: The assumption implies that $tP(t,t) = 0$ in $k[t]$. But $t$ is not a zero divisor, so $P(t,t) = 0$ and the conclusion follows.
Now we use this lemma twice : suppose $t_0 P = 0$ in $E$. This means $(t_0-t_1)^2\mid t_0P$ in $k[t_0,t_1]$. It follows that $(t_0-t_1)$ divides $t_0 P$, and thus by the lemma, it divides $P$. Write $P= (t_0-t_1)Q$, and it follows easily that $(t_0-t_1) \mid t_0 Q$, so that by the lemma, $(t_0-t_1)$ divides $Q$, and so $(t_0-t_1)^2$ divides $P$. So $P = 0$ in $E$.
By symmetry, the same holds for $t_1$, and so the action of $t_0$ and $t_1$ on $E$ is injective, which proves the claim that the tensor products are underived.
Now, $E\otimes_{k[t]}k$ is therefore $E/t_1 E\cong k[t_0,t_1]/((t_0-t_1)^2, t_1) = k[t_0,t_1]/(t_0^2,t_1)\cong k[t_0]/(t_0)^2$, on which $t_0$ acts nontrivially while $t_1$ acts trivially. Conversely, $k\otimes_{k[t]}E\cong k[t_1]/(t_1^2)$, on which $t_0$ acts trivially but $t_1$ nontrivially. It follows that they are not isomorphic as bimodules, hence not isomorphic in the derived category either.


TITLE: Confusing integral
QUESTION [0 upvotes]: $$\int_{-\infty}^{\infty}(x-a)^2e^{-\lambda (x-a)^2}dx$$
I've tried setting $$u=x-a$$ but I get stuck after that...
$$\int_{-\infty}^{\infty}u^2e^{-\lambda u^2}du$$
I know that the answer should be $$\frac{1}{2\lambda} + a^2$$
Solution Manual Answer

REPLY [0 votes]: $$
\begin{align}
I=\int_{-\infty}^{\infty}x^2\mathrm e^{-\lambda (x-a)^2}\mathrm dx&=\int_{-\infty}^{\infty}(u+a)^2\mathrm e^{-\lambda u^2}\mathrm du\qquad (\text{putting }x-a=u, \,x=a+u,\,\mathrm dx=\mathrm du)\\
&=\int_{-\infty}^{\infty}(u^2+2au+a^2)\mathrm e^{-\lambda u^2}\mathrm du\\
&=\underbrace{\int_{-\infty}^{\infty}u^2\mathrm e^{-\lambda u^2}\mathrm du}_{I_1}+2a\underbrace{\int_{-\infty}^{\infty}u\mathrm e^{-\lambda u^2}\mathrm du}_{I_2}+a^2\underbrace{\int_{-\infty}^{\infty}\mathrm e^{-\lambda u^2}\mathrm du}_{I_3}\\
&=I_1+2aI_2+a^2I_3
\end{align}
$$
$I_2=0$ because is the integral of an odd function over a symmetric interval.
$I_3=\sqrt{\frac{\pi}{\lambda}}$ is a known gaussian integral
For $I_1$ differentiating w.r.t $\lambda$ and integrating we have
$$\begin{align}
I_1=
\int _{-\infty }^{\infty }\left(u^{2}\mathrm e^{-\lambda u^{2}}\right)\,du=\int _{-\infty }^{\infty }\left(-\frac {\partial }{\partial \lambda}\mathrm e^{-\lambda u^2}\right)\mathrm du=-\frac {\partial }{\partial \lambda}\underbrace{\int _{-\infty }^{\infty }\mathrm e^{-\lambda u^2}\mathrm du}_{I_3=\sqrt{\frac{\pi}{\lambda}}}=\frac{1}{2\lambda}\sqrt{\frac{\pi}{\lambda}}
\end{align}
$$
So we have
$$
I=I_1+2aI_2+a^2I_3=\frac{1}{2\lambda}\sqrt{\frac{\pi}{\lambda}}+2a\cdot 0+a^2 \sqrt{\frac{\pi}{\lambda}}=\sqrt{\frac{\pi}{\lambda}}\left(\frac{1}{2\lambda}+a^2\right)
$$
The integral in your book is
$$
\mathcal I=A\cdot I=A\cdot\sqrt{\frac{\pi}{\lambda}}\left(\frac{1}{2\lambda}+a^2\right)=\frac{1}{2\lambda}+a^2
$$
if $A\cdot\sqrt{\frac{\pi}{\lambda}}=1$ that is $A=\sqrt{\frac{\lambda}{\pi}}$.


TITLE: When can one use logarithms to multiply matrices
QUESTION [2 upvotes]: If $a,b \in \mathbb{Z}_{+}$, then $\exp(\log(a)+\log(b))=ab$. If $A$ and $B$ are square matrices, when can we multiply $A$ and $B$ using logarithms? If $A \neq B^{-1}$, should $A$ and $B$ be symmetric?

REPLY [4 votes]: If $A$ and $B$ commute, i.e. $AB=BA$, then the same identity holds for an appropriate definition of $\exp$ and $\log$. If $A$ and $B$ do not commute, then things are much more complicated.

REPLY [1 votes]: When they commute, or: when they have the same eigenvectors, or if $AB=BA$


TITLE: What is the equation of intersection between a line segment and a square?
QUESTION [0 upvotes]: If we have a line segment l and an axis-aligned fixed size square s, what is the algebraic equation of length of intersection between l and s? (with respect to center of s)
EDIT: in fact we are searching the length of subsegment of l that is inner the square

REPLY [1 votes]: Consider the line segment connecting points $(x_0,y_0)$ and $(x_1,y_1)$ in the Cartesian plane, of length $\ell = \sqrt{(x_1-x_0)^2 + (y_1-y_0)^2}$.
The entire length of the line segment is interior to the square if and only if both its endpoints are interior to the square.  So it makes sense to begin the determination of length with a check on which of the endpoints (if either) fall inside the square.

Let the (filled) square with axis-parallel sides be $[a,a+s] \times [b,b+s]$.  A point $(x,y)$ is in the square if and only if:
  $$ 0 \le x-a \le s \;\text{ and }\; 0 \le y-b \le s $$

There are three cases:  both inside, one inside & one outside,  both outside.  Other than the first of these cases, the length you want will depend on locating intersections between line segments, a topic that has been explored here before.
In the second case (one endpoint inside, one outside), there is always a single intersection to locate (between the given line segment and one edge of the square).
In the third case (both endpoints outside) we have the most difficult checks to perform.  The given line segment may have no intersection with edges, it may have distinct intersections with two edges, or it might one intersection at a corner of the square (which zero length you might consider equivalent to missing the square entirely).
There is no apparent value to trying to package all those possible outcomes into one "algebraic equation", but if you explain why you need this, it can be done with a certain amount of complexity.


TITLE: Easy argument for "connected simple real rank zero Lie groups are compact"?
QUESTION [9 upvotes]: Let $G$ be a connected simple Lie group. It is known that if $G$ has real rank zero, then $G$ is compact.
Background: every connected (semi)simple Lie group $G$ (with Lie algebra $\mathfrak{g}$) has a polar decomposition $G=KAK$, where $K$ arises from a Cartan decomposition $\mathfrak{g}=\mathfrak{k} + \mathfrak{p}$ (the group $K$ has Lie algebra $\mathfrak{k}$) and $A$ is an abelian Lie group such that its Lie algebra $\mathfrak{a}$ is a maximal abelian subspace of $\mathfrak{p}$. The real rank of $G$ is defined as the dimension of $\mathfrak{a}$. (Equivalently, the real rank can be defined in a similar way through the Iwasawa decomposition (see http://en.wikipedia.org/wiki/Iwasawa_decomposition)).
A possible way of obtaining the result that "connected simple real rank zero implies compact" is by looking at a list of (connected) simple Lie groups (see for example http://en.wikipedia.org/wiki/List_of_simple_Lie_groups) and check that all such Lie groups with real rank zero are compact. This, however, is not as explanatory as I would like.
Question: Is there an easy and explanatory proof of the fact mentioned above that connected simple real rank zero Lie groups are compact?
Perhaps, one might be able to use that the Lie algebra of a noncompact simple Lie group contains a copy of the real rank one Lie algebra $\mathfrak{sl}(2,\mathbb{R})$?
An easy special case: If $G$ is a connected simple real rank zero Lie group with finite center, then the implication easily follows from the $KAK$-decomposition. Indeed, if $G$ has finite center, the group $K$ in this decomposition is a (maximal) compact subgroup of $G$. This directly implies that $G$ is compact if it has real rank zero.
Using Riemannian symmetric spaces: if $X$ is a Riemannian symmetric space, and $G$ is the connected component of the isometry group of $X$, then the real rank of $G$ is the largest $n \in \mathbb{N}$ such that $X$ contains an $n$-dimensional closed, simply connected, connected, totally geodesic flat submanifold. It follows that $G$ has real rank zero if and only $X$ is compact. This can also be used to prove the fact mentioned above, but as far as I know, one still needs to consider all possible spaces $X$ that might occur. Or is there an easier way here?

REPLY [9 votes]: (Real rank 0) $\ \Rightarrow\ (\mathfrak a = 0) \ \Rightarrow\ (\mathfrak p=0) \ \Rightarrow\ (\mathfrak g$ is a compact Lie algebra).
Therefore this comes down to (e.g. Bourbaki, Lie Groups, Chap IX, §1, no 4):

THEOREM (H. Weyl) Let G be a connected Lie group whose Lie algebra is compact semi-simple. Then G is compact and its centre is finite.

(Of that, I don't know an "easier" proof than what you'll find in Bourbaki or Hilgert-Neeb.)


TITLE: Existence of $d$-regular expander graph that can be represented as a bipartite graph
QUESTION [3 upvotes]: It is easy to derive from the definition of expander graphs that a $n$-vertex expander graph $G$ does not have a $o(n)$-vertex/edge separator. I was wondering if we can build a $d$-regular expander graph that is also a bipartite graph? Thus I have a sparse bipartite graph example that does not have a $o(n)$-vertex/edge separator.
Note that by definition this bipartite graph is not exactly a bipartite expander graph, which only requires that every small subset on the left side of the bipartite graph to have large neighbors on the right.

REPLY [4 votes]: The obvious thing to try would be to convert a non-bipartite regular expander to a bipartite one using the bipartite double cover, which preserves regularity. But it might not preserve expansion; in particular, if you have only a small number of vertices involved in odd cycles, they would become a bottleneck in the double cover.
But if all you need is constant expansion (rather than stronger properties like, say, being a Ramanujan graph) then converting a non-bipartite graph to a bipartite one while preserving constant expansion is easy: just subdivide each edge to make it bipartite (as Yixin Cao already suggested in comments), and then add enough extra edges to the subdivision vertices to make it regular again.
For the stronger expansion that you get from Ramanujan graphs, see Marcus, Spielman, and Srivastava "Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees", FOCS 2013. Judging from the abstract (I haven't read the paper carefully) they appear to be using the bipartite double cover idea, but with a bit more care to avoid the bottlenecks.


TITLE: Groups Math Proof Help
QUESTION [0 upvotes]: Show that the indicated set $G$ with the specified operation forms a group by showing that the four axioms in the definition of a group are satisfied.
$G = \mathbb Z_5$ under addition mod $5$.
I am confused and do not know how to begin. I am not really sure what $\mathbb Z_5$ under addition mod $5$ means.

REPLY [0 votes]: In General $G = \mathbb Z_n$ under addition mod $n$ forms a group.
$G = \mathbb Z_n$ means the set of elements under modulo n
  = { 0,1,...., n-1}

  Now, to check if this is a group under addition modulo n, all you have to check is for the associativity property, the existence of an identity element in the above set and the existence of inverse for each of the elements in the above set.


TITLE: Mechanism for a photon to impart momentum to an atom
QUESTION [1 upvotes]: Picture a simple hydrogen atom with one electron which is bound to a proton (nucleus). When trying to impart momentum to the atom, we may specify the photon wavelength to be $\lambda = 121.57$ nm to access the 1s-2s electronic transition. But in this picture, where exactly does the photon's momentum go and how does it get there?
We know that the electron can only occupy quantized states and the transition is instantaneous. The photon energy has decreased the electric potential energy between the proton-electron pair by $hc/\lambda$. But do not the quantized orbits occupied by electrons have well-defined momentum, too? Since the electron's momentum now that it has gone from 1s to 2s may not necessarily be the photon's total original momentum, $h/\lambda$, where does the rest of this momentum go? And is this momentum transfer an instantaneous process as well?
I believe a partial answer is that the entire atom has momentum imparted to it, but what is the mechanism to make the nucleus start moving if the photon was wholly absorbed by just the electron and the electron cannot simply drift off its quantized orbit (which would then pull on the nucleus via Coulomb interaction)? Perhaps answering this question may help elucidate the above: is imparting momentum by photons with wavelengths corresponding to particular transitions more efficient than photons with arbitrary wavelength?

REPLY [0 votes]: First of all let us make it clear that the atom is a quantum mechanical entity, and there are no orbits around the center of mass of electron-nucleus, which look like planetary orbits. There are orbitals, quantum mechanical probability locations , i.e. after many measurements for the hydrogen atom, this is where the electron (dot) will be found:

As far as momentum goes, conservation of momentum implies that the whole atom acquires a momentum when a photon transition happens with the correct ( within a width) frequency.
It is the atom that is interacting with the photon, not the individual electron.
If the photon does not have an energy level frequency, it may  interact with the neutral atom through scattering off spill over fields, transferring momentum and energy to the whole atom, with very low probability. In various energy regions there are different names for this. Special calculations are needed , for example here,  according to the energy of the photons.


TITLE: Prove that any continuous map $f:\mathbb{R}P^n\to \mathbb{R}P^m$, $m<n$, induces trivial homomorphism between fundamental groups
QUESTION [1 upvotes]: Question: Given a continuous map $f:\mathbb{R}P^n\to \mathbb{R}P^m$, where $m<n$, show that $f$ induces trivial homomorphism $f_\#:\pi_1(\mathbb{R}P^n)\to \pi_1(\mathbb{R}P^m)$.
$\mathbb{R}P^n$ stands for the $n$-dimensional real projective plane, $\pi_1(\mathbb{R}P^n)$ stands for its fundamental group.
My attempt:
Consider the standard quotients $\pi_1:S^n\to \mathbb{R}P^n$ and $\pi_2:S^m\to \mathbb{R}P^m$, then $f\pi_1:S^n\to \mathbb{R}P^m$ lifts to $\tilde f:S^n\to S^m$, and since for any $x\in S^n$ there is $\pi_2\tilde f(x)=f\pi_1(x)=f\pi_1(-x)=\pi_2\tilde f(-x)$ we see that $\tilde f(x)=\tilde f(-x)$ or $-\tilde f(-x)$ must be true. The sets $B_1=\{x\in S^n\mid \tilde f(x)=\tilde f(-x)\}$ and $B_2=\{x\in S^n\mid \tilde f(x)=-\tilde f(-x)\}$ are both open by a convergence point sequence argument using the fact that the functions are all continuous. Note that $S^n=B_1\cup B_2$, one of $B_1,B_2$ must be empty. If $B_2$ is empty then by the universal property of quotient there exists $g:\mathbb{R}P^n\to S^m$ such that $g\pi_1=\tilde f$, therefore by the surjectivity of $\pi_1$ we see that $g$ is a lifting of $f$ and by the Lifting Criterion we are done. So it remains to show that either $B_2$ must be empty, or to give a lift of $f$ when $B_2$ is not empty.
I don't know how to proceed. Any hint or solution is appreciated. Thanks in advance.

REPLY [0 votes]: I find my way. The Borsuk-Ulam Theorem tells that any continuous map $S^n\to \mathbb{R}^n$ must map some pair of antipodal points to a same point, hence we just embed $S^m$ into $\mathbb{R}^n$ using $m<n$ and we see that $B_1$ is not empty, so $B_2$ must be empty and by the universal property of quotient we are done.
Thanks for your answers anyway.


TITLE: Trapezoids - Which definition has a stronger case?
QUESTION [12 upvotes]: Today my daughter Ella asked me "Is a trapezoid an irregular polygon?" and I realized I cannot give her a definitive answer.
According to the Internet, trapezoids are alternately defined as having only one pair of parallel lines, and also at least one pair of parallel lines.  My understanding is that this is simply an unresolved ambiguity in mathematics.
My question is, which definition has the stronger case?  So far I have this:
The case for "only one":

Many people seem to think this is more intuitive and/or traditional

The case for "at least one":

Inclusive definitions are generally more useful (if this true I'd like to learn why)
It's the only definition that fits with the concept of trapezoidal sums in calculus

What am I missing?

REPLY [2 votes]: It's something of a truism to say that inclusive definitions are better, because any properties proved of a more general category automatically apply to all special cases contained within it.
However, consider the following theorems:

Theorem.  The angle bisectors of any rectangle intersect at four points which form the vertices of a square.
Theorem.  The perpendicular bisectors of any rhombus intersect at four points which form the vertices of another rhombus.

(See Figures.)

These theorems are true statements if rectangle and rhombus are defined exclusively, i.e. if "rectangle" is defined as "a quadrilateral that is equiangular but not equilateral" and if "rhombus" is defined as "a quadrilateral that is equilateral but not equiangular".  However, if inclusive definitions are used, these theorems are false, because if the rectangle (resp. rhombus) is a square, then the angle bisectors (resp. perpendicular bisectors) would be concurrent, and the "figure" formed by them would be a single point.
In other words:  the theorems are true for the general category only if the more specific category is excluded.  Depending on whether or not you think these theorems are things you want to be true in your theory, this could be a reason in support of adopting exclusive definitions.
There is another option, of course:  one could define "rectangle" and "rhombus" inclusively, but in the statement of the theorem specify in the hypothesis that it is true of a non-square rectangle or a non-square rhombus.  But if you have to do this often enough, at a certain point it might make sense to introduce a name for "non-square rectangle" and "non-square rhombus" -- and then we are right back to exclusive definitions again.
What about trapezoids, the topic the OP specifically asks about?  As discussed in this answer, if trapezoids are defined exclusively, then it is possible to calculate the area of a trapezoid given only its four lengths (provided you know which ones are the parallel ones and which ones are the non-parallel ones).  (Even if you do not know which sides are the parallel ones, you can determine that the area must be one of six uniquely determined possible values.)  However, if trapezoid are defined inclusively, then the four lengths do not determine the area at all, as the area of a trapezoid with side lengths $a,b,a,b$ can take on any real value between $0$ and $ab$.
(Related:  For historical background on when the "inclusive" definitions of quadrilaterals came to be standard, see also this answer on MESE.)


TITLE: Exact differential equations and holonomic constraints
QUESTION [1 upvotes]: I understand that if a constraint equation given on a differential form is exact, that means it is also holonomic since I can find a solution. But there are other types of differential equations, like separable and linear, such that I can find an equation in the form of a holonomic constraint. Why is it that being exact is a condition, rather than just having a solution of the type $f(x,y) = 0$?

REPLY [1 votes]: Here I would like to mention the notion of a semi-holonomic constraint
$$ \sum_{j=1}^n a_j(q,t)~ \mathrm{d}q^j + a_t(q,t)~\mathrm{d}t~=~0, \tag{1'}$$
which puts an
inexact differential equal to zero.
It is possible to incorporate semi-holonomic constraints into Lagrange equations, cf. e.g. my Phys.SE answer here.
Note that eq. (1') does not mean that we demand that the $n+1$ co-vector components
$$ a_t(q,t)~= a_1(q,t)~= \ldots ~=~a_n(q,t)~=~0 \qquad\qquad (\longleftarrow \text{Wrong!} )
\tag{2'}$$
of a co-vector (1') should be zero. Perhaps this potential misunderstanding (2') is secretly the core of OP's question?
Rather eq. (1') means that
$$ \sum_{j=1}^n a_j(q,t)~ \dot{q}^j + a_t(q,t)~=~0. \tag{3'}$$
In particular, a holonomic constraint
$$f(q,t)~=~0 \tag{0}$$
can be put on the above semi-holonomic form
$$ \mathrm{d}f~=~\sum_{j=1}^n \frac{\partial f}{\partial q^j}~ \mathrm{d}q^j +  \frac{\partial f}{\partial t}~\mathrm{d}t~=~0 .\tag{1}$$
Explicitly, eq. (1) means that the total time derivative
$$ \frac{df}{dt}~\equiv~ \sum_{j=1}^n \frac{\partial f}{\partial q^j}~ \dot{q}^j +  \frac{\partial f}{\partial t}~=~0\tag{3}$$
is zero.

References:

H. Goldstein, Classical Mechanics, Section 2.4.


TITLE: Suppose $f(z)$ is analytic on $\mathbb{C}\setminus\{0\}$ and $|f(z)| \leq |z|^{5/2} + |z|^{-1/2}$ for all $z\in \mathbb{C}\setminus\{0\}$...
QUESTION [1 upvotes]: This is a question from a previous qualifying exam that I'm working through to study for my own upcoming qual. I can't seem to figure out where to go with it, so if someone could walk me through this proof, it would be very helpful.
Problem:
Suppose $f(z)$ is analytic on $\mathbb{C}\setminus\{0\}$ and $|f(z)| \leq |z|^{5/2} + |z|^{-1/2}$ for all $z\in \mathbb{C}\setminus\{0\}$. Prove that $f(z)$ is a polynomial of degree at most two.
Thoughts:
I don't think I can use that there exists a power series $f(z) = \sum_{k=0}^\infty a_kz^k$, because zero is excluded from the domain. (Is this right?)
I was thinking of instead using that there exists a Laurent series (since it can be in an annulus) such that
$$
f(z) = \sum_{k=0}^\infty a_kz^k + \sum_{k=1}^\infty a_{-k}z^{-k},
$$
and then try to bound this somehow? Can someone please walk me through this or a better method for this problem?
Update (based on answer from @Martin R):
Continuing with the Laurent series
$$
f(z) = \sum_{-\infty}^{\infty} a_kz^k,
$$
a generalization of the Cauchy Integral Theorem yields the coefficients
$$
a_k = \frac{1}{2\pi i} \oint_\gamma \frac{f(z)}{z^{k+1}}\; dz
$$
for a positively oriented curve $\gamma: \{|z|=r,\; r>0\}$. We now consider the magnitude of these coefficients, such that
$$
|a_k| = \left\vert\frac{1}{2\pi i}\right\vert\cdot\left\vert \oint_\gamma \frac{f(z)}{z^{k+1}}\; dz\right\vert = \frac{1}{2\pi }\cdot\left\vert \oint_\gamma \frac{f(z)}{z^{k+1}}\; dz\right\vert
$$
Since we have a bound for $f(z)$, we can use the ML estimation lemma such that
$$
|a_k| \leq \frac{1}{2\pi}\cdot ML,
$$
where $M = \max_{|z|=r} \left\vert\frac{f(z)}{z^{k+1}}\right\vert = \frac{\max_{|z|=r} |f(z)|}{r^{k+1}}$ and $L = 2\pi r$ is the length of the curve, which yields
$$
|a_k| \leq \frac{1}{2\pi}\cdot \left(\frac{\max_{|z|=r} |f(z)|}{r^{k+1}}\right)\cdot 2\pi r = \frac{\max_{|z|=r} |f(z)|}{r^{k}}.
$$
The given bound on $f(z)$ is $|f(z)| \leq |z|^{5/2} + |z|^{-1/2}$, thus we have
$$
|a_k| \leq \frac{r^{5/2} + r^{-1/2}}{r^{k}} = r^{5/2-k} + r^{-1/2-k}.
$$
Now, since we want this result to hold for all $z\in \mathbb{C}\setminus \{0\}$, we must consider what happens as $r$ gets very large.
For $k>\frac{5}{2}$, we find that $|a_k|\to 0$ as $r\to\infty$. Similarly, for $k<-\frac{1}{2}$. Thus, for this bound to hold, we must have $-\frac{1}{2} < k < \frac{5}{2}$.
Returning to our original Laurent series then, we must have
$$
f(z) = \sum_{k>-1/2}^{k<5/2} a_kz^k = \sum_{k=0}^{2} a_kz^k,
$$
since $k$ must be an integer. This means that $f(z)$ must be a polynomial of degree 2 or less, as desired. $\blacksquare$

REPLY [3 votes]: If $f$ is analytic in $\Bbb C \setminus \{ 0 \}$ then – as you said – it can be developed into a Laurent series
$$
 f(z) = \sum_{n=-\infty}^\infty a_n z^n \, ,
$$
and the coefficients of the Laurent series are given by
$$
 a_n = \frac{1}{2 \pi i}\int_\gamma \frac{f(z)}{z^{n+1}} \, dz
$$
where $\gamma$ is any closed curve surrounding the origin exactly once in counter-clockwise (mathematical positive) direction.
Choosing a circle of radius $r$ as the integration path and taking absolute values then shows that
$$
 |a_n| \le \frac{\max_{|z|=r} |f(z)|}{r^n}
$$
for all $r > 0$.
Now assume that $f$ satisfies a growth condition
$$ \tag{$*$}
 |f(z)| \le A |z|^\alpha + B |z|^{-\beta}
$$
with non-negative real constants $A, B, \alpha, \beta$. Then
$$ \tag{$**$}
|a_n| \le A r^{\alpha - n} + B r^{-\beta -n}
$$
for all $r > 0$. If $n > \alpha$ then the right-hand side of $(**)$ tends to zero for $r \to \infty$, so that necessarily $a_n = 0$. And if $n < - \beta$ then the right-hand side of $(**)$ tends to zero for $r \to 0$, so that also $a_n = 0$.
This shows that if $f$ satisfies the growth condition $(*)$ then $a_n \ne 0$ is only possible for $-\beta \le n \le \alpha$, i.e. $f$ is a rational function with the finite Laurent series
$$
 f(z) = \sum_{n = \lceil - \beta \rceil}^{\lfloor \alpha \rfloor} a_n z^n \, .
$$
In your case, with $\alpha = 5/2$ and $\beta = -1/2$, the only non-zero Laurent coefficients are in the range $-1/2 \le n \le 5/2$, and $f(z) = a_0 + a_1 z + a_2 z^2$ is a polynomial of degree at most two.