TITLE: Least model over a certain configuration
QUESTION [3 upvotes]: I am interested in conditions under which there is a least model inside a (not saturated in general) model $N$ over certain configurations such as $M_0 \subseteq M_1, M_2$ with $M_1 \overset{\vert}{\smile}_{M_0} M_2$. The situation is simpler in an uncountably categorical theory, since $N$ has to be saturated and the intersection of all models containing $M_1M_2$ is $acl(M_1M_2)$.
Question: given $M_0 \subseteq M_1, M_2$ models with $M_1 \overset{\vert}{\smile}_{M_0} M_2$ inside the monster model of an uncountably categorical theory, is $acl(M_1M_2)$ a model?
On the face of it I don't see many reasons why it should be true. However, it is certainly true in almost strongly minimal theories and also in the classical example of an uncountably categorical theory that is not almost strongly minimal (the theory of $\bigoplus_{i < \omega} \mathbb Z/4\mathbb Z$).

REPLY [2 votes]: I think I have found the counterexample I was looking for.
The idea is to hack the example $\bigoplus_{i < \omega} \mathbb Z/4 \mathbb Z$ to keep it not almost strongly minimal, but to remove the feature that makes $acl(M_1M_2)$ into a model. What is happening is there is a formula $\phi(x) = 2x = 0$ which defines a vector space over $\mathbb Z/2\mathbb Z$ and hence is strongly minimal. Above each $b \in \phi(M)$ there is a set defined by $\psi(x, b) = 2x = b$ which is internal to $\phi$ but every element realises the same type so is not algebraic. When we have two models $M_1$ and $M_2$, $acl(M_1M_2)$ adds new elements to $\phi(M_1) \cup \phi(M_2)$, e.g. $m_1 + m_2$ for $m_i \in M_i$. So there need to be new elements in $\psi(x, m_1+m_2)$. However such an element can be found by taking $n_1+n_2$ where $n_i$ is in $\psi(x,m_i)$ which is therefore in $acl(M_1M_2)$. The idea is to remove the interaction between $\psi(x,b)$ for different $b$-s and so to remove the possibility of finding such an element in $acl(M_1M_2)$.
So the counterexample is as follows: There are two sorts $R$ and $V$. The sort $V$ is a vector space over $\mathbb Z/2\mathbb Z$ so is strongly minimal. $R = V^2$ but the group operation on $V^2$ is not in the language. Instead there is a projection map $\pi \colon R \to V, (a,b) \mapsto b$ onto the second coordinate and also a map $\sigma : R \times V \to R, ((a,b), c) \mapsto (a+c, b)$ describing the action of $V$ on each fibre $\pi^{-1}(b)$. Now fibres of $\pi$ are internal to $V$ as in the above example. However  if we now pick two models $m_1 \in M_1$ and $m_2 \in M_2$, then the type of an element in $\pi^{-1}(m_1+m_2)$ is not algebraic over $M_1M_2$.


TITLE: limit approximation without using l'hopital
QUESTION [0 upvotes]: I would like to calculate this limit without using l'hopital:
$$\lim _{x\to \infty }\frac{x^2\cdot \left(1+\dfrac{1}{\ln^2x}\right)^{1+2\ln^2x}-x^2+1}{x-2+x^2}$$
I thought about approximation, but I don't know how.

REPLY [2 votes]: $$\lim _{x\to \infty }\frac{x^{2}\left(1+\frac{1}{\left(\ln\left(x\right)\right)^{2}}\right)^{\left(1+2\left(\ln\left(x\right)\right)^{2}\right)}-x^{2}+1}{x^{2}+x-2}$$$$=\lim _{x\to \infty }\frac{\color{blue}{\left(1+\frac{1}{\left(\ln\left(x\right)\right)^{2}}\right)^{\left(1+2\left(\ln\left(x\right)\right)^{2}\right)}}-1+\frac{1}{x^{2}}}{1+\frac{1}{x}-\frac{2}{x^{2}}}$$
Then we have:
$$\color{blue}{\lim _{x\to \infty }\left(1+\frac{1}{\left(\ln\left(x\right)\right)^{2}}\right)^{\left(1+2\left(\ln\left(x\right)\right)^{2}\right)}}$$$$=\exp\left(\lim _{x\to \infty }\frac{^{1+2\left(\ln\left(x\right)\right)^{2}}}{\left(\ln\left(x\right)\right)^{2}}\right)$$$$=\exp\left(\lim _{x\to \infty }\frac{1}{\left(\ln\left(x\right)\right)^{2}}+2\right)$$$$=\exp\left(2\right)=e^{2}$$
So finally we have:$$\lim _{x\to \infty }\frac{x^{2}\left(1+\frac{1}{\left(\ln\left(x\right)\right)^{2}}\right)^{\left(1+2\left(\ln\left(x\right)\right)^{2}\right)}-x^{2}+1}{x^{2}+x-2}=e^2-1$$


TITLE: Counting in Two ways: $m^3 = 6 {m \choose 3} + 6 {m \choose 2} + m \quad \forall m \in \mathbb{N}$
QUESTION [7 upvotes]: I am having an issue in counting in two ways. How would I go about proving:
$$m^3 = 6 {m \choose 3} + 6 {m \choose 2} + m \quad \forall m \in \mathbb{N}$$
I can see that substituting formulas and simplifying would make the equality. I am not sure I can produce a combinatorial proof (but that is not required for the course I am in).

REPLY [4 votes]: We use the fact that usual powers can be expressed as a combination of falling factorials $x^{(k)}$, as well as the relation $x^{(k)}=k!\binom{x}{k}$ to yield the series:
$$x^n=\sum_{j=0}^n \left\{n \atop j\right\}j!\binom{x}{j}$$
where $\left\{n \atop j\right\}$ is a Stirling subset number. (See page 262 of Concrete Mathematics for a justification.) For $n=3$, we then have
$$\begin{align*}x^3&=0!\left\{3 \atop 0\right\}\binom{x}{0}+1!\left\{3 \atop 1\right\}\binom{x}{1}+2!\left\{3 \atop 2\right\}\binom{x}{2}+3!\left\{3 \atop 3\right\}\binom{x}{3}\\&=1\times0\times\binom{x}{0}+1\times1\times\binom{x}{1}+2\times3\times\binom{x}{2}+6\times1\times\binom{x}{3}\\&=x+6\binom{x}{2}+6\binom{x}{3}\end{align*}$$
and presto!


TITLE: Defining a bijection with binary strings
QUESTION [1 upvotes]: Let $n\in\mathbb N$. Then a binary string of length $n$ has the form $a_1a_2...a_n$ such that each $a_i$ is either 0 or 1. Define $E_n$ to be the set of all binary strings of length $n$ with even number of 1's, and define $O_n$ to be the set of all binary strings of length $n$ with odd number 1's.
Define a bijection $f: E_n \to O_n$.
Now, I'm really confused as to how to apply the idea of a bijection in an example like this and I'm not sure how to start. Any help would be appreciated..

REPLY [5 votes]: Easiest answer as I see it: flip $a_1$. This is a bijection as the inverse function is given by flipping $a_1$.


text:
\begin{definition}[Definition:Algebra of Sets/Definition 2]
An '''algebra of sets''' is a [[Definition:Ring of Sets|ring of sets]] with a [[Definition:Unit of System of Sets|unit]].
\end{definition}

config: wiki


TITLE: Question on Green's Theorem. (Answer should be positive).
QUESTION [1 upvotes]: Question: $\int_C (xy) dx + \exp(y^2) dy$ where C is the triangle with vertices: $(0,0)$, $(2,0)$, $(2,1)$.
Now applying the Green's Theorem I get: $\int_0^2\int_0^{1/2x} -xdydx$ which in the end gives me $-4/3$ while the answer is $4/3$. Am I missing something?

REPLY [1 votes]: the line integral $\int_C xy\,dx$(anticlockwise) is zero except on $(2,1)$ to $(0,0) $ so evaluates to
$$
\int_2^0 x(\frac{x}2)dx = -\frac43
$$


TITLE: Show that $f(t) = \det(A + tB)$ is a line
QUESTION [6 upvotes]: Suppose $A,B \in \mathbb{R}^{n \times n}$ where rank$(B) = 1$. Show that the function $f: \mathbb{R} \to \mathbb{R}$ where $$f(t) = \det(A + tB)$$ is a line, i.e., has the form $f = mt + b$.

So far, I really only have that $f(0) = \det(A) = b$. I thought about explicitly calculating the derivative as in,
$$ \lim_{t\to0} \frac{\det(A + tB) - b}{t}$$
but I'm not sure where I would go next. Also, I am not sure how to use that rank$(B) = 1$. Any help would be appreciated.

REPLY [0 votes]: Generalizing, suppose that we have square matrices ${\bf A}, {\bf B} \in {\Bbb R}^{n \times n}$, where matrix $\bf B$ is rank-$r$ and $r \leq n$. Hence, there exist matrices ${\bf U}, {\bf V} \in {\Bbb R}^{n \times r}$ such that ${\bf B} = {\bf U} {\bf V}^\top$. Assuming that matrix $\bf A$ is invertible and using the generalized matrix determinant lemma,
$$f (t) := \det \left( {\bf A} + t \, {\bf B} \right) = \det \left( {\bf A} + t \, {\bf U} {\bf V}^\top\right) = \cdots = \det \left( {\bf A} \right) \underbrace{\det \left( {\bf I}_r + t \, {\bf V}^\top {\bf A}^{-1} {\bf U} \right)}_{=: g (t)}$$
If $\color{blue}{r = 1}$, then $g (t)$ is affine in $t$. What if $r > 1$?


TITLE: Difference b/w $p$ and $P(X)$ i.e. output of Binomial Distribution ($BD$)? Is it possible to have $p=1$ but $BD=0$?
QUESTION [0 upvotes]: I have a confusion with Binomial Distribution. For Binomial Distribution we use the formula:
$P(x) = {n \choose k} \cdot p^x \cdot (1-p)^{n-x}$
Now let's suppose $p=1$ but if we put this $1$ in $P(x)$, we will get $P(x)=0$.
How can we define this situation?
Zulfi.

REPLY [1 votes]: Um, funny. If $p=1$, then when you repeat the experiment $n$ times, $P(X=n)=1$ and $P(X=k)=0$ for all other $k$. You can't use the formula to calculate $P(X=n)$, but for all other $P(X=k)$ the formula still works since $0^{n-k}=0$ if $k\ne n$.
Edit: If you read Hogg and Craig's "Intro to Mathematical Statistics", you will find that they define the binomial distribution with a restriction of $0<p<1$.


TITLE: why does the reduced row echelon form have the same null space as the original matrix?
QUESTION [11 upvotes]: What is the proof for this and the intuitive explanation for why the reduced row echelon form have the same null space as the original matrix?

REPLY [10 votes]: The short answer: Because you multiply nonsingular matrices from the left.
The long answer: Say you have a matrix $A$. Each Gaussian elimination step corresponds to some elementary matrix (which are nonsingular). Thus, there exists a nonsingular matrix $M$ (product of elementary matrices) such that $MA$ has reduced row echelon form.
Now, let $x$ be in the null space of $A$. Then, we have
$$MAx = M(Ax) = M0 = 0.$$
That is, $x$ is also in the null space of $MA$. On other hand, let $y$ be in the null space of $MA$. Then, we also have
$$Ay = M^{-1} (M A y) = M^{-1} 0 = 0.$$
Thus, the null spaces of $A$ and $MA$ are the same.


TITLE: Asymptotic distribution of OLS estimator in a linear regression
QUESTION [1 upvotes]: I know the standard way of finding the asymptotic distribution of the OLS estimator in a linear regression. Suppose
$$ y_i = x_i'\beta + u_i$$
where $u_i |X = x_i\sim N(0,\sigma^2)$.
Let $\hat{\beta}$ denote the OLS estimator of $\beta$. I know that
$$ \sqrt{n}(\hat{\beta} - \beta) \overset{d}\to N(0,\sigma^2 Q^{-1})$$
where $Q$ is the probability limit of $X'X$, as shown in page 17 of this document.
However, what's wrong with my attempt to derive the asymptotic distribution?
The CLT tells me
$$\sqrt{n} (\hat{\beta} - \beta) \overset{d}\to N(0, \mathrm{var}(\hat{\beta}))$$
Then define $U = [u_1, u_2, \dots, u_n]'$.
\begin{align}
\mathrm{var}(\hat{\beta}) &= E[(\hat{\beta} - \beta)^2 ] \\
&= E[( (X'X)^{-1}(X'U)) ( (X'X)^{-1}(X'U))'] \\
&= E[( (X'X)^{-1}(X'U)(U'X)(X'X)^{-1}] \\
&= E\bigg[(X'X)^{-1}\big(\sum_{i=1}^{n} x_i x_i' u_i^2 \big)(X'X)^{-1} \bigg] \\
&= E\bigg[(X'X)^{-1}\big(\sum_{i=1}^{n} x_i x_i' E[u_i^2|X] \big)(X'X)^{-1} \bigg] \\
&= E\bigg[(X'X)^{-1}\big(\sum_{i=1}^{n} x_i x_i'\big)(X'X)^{-1} \bigg]\sigma^2 \\
&= E\bigg[(X'X)^{-1}X'X(X'X)^{-1} \bigg]\sigma^2 \\
&= E[(X'X)^{-1}] \sigma^2
\end{align}
Obviously $E[(X'X)^{-1}] \neq Q^{-1}$, by Jensen's inequality. What went wrong?

REPLY [1 votes]: That's because
$$
\sqrt{n} (\hat{\beta}_n - \beta) \overset{d}{\not\to} N(0, \operatorname{Var}(\hat{\beta}_n)).
$$
Instead,
$$
\sqrt{n} (\hat{\beta}_n - \beta)\xrightarrow{d}N(0,\Sigma),
$$
where
$$
\Sigma=Q^{-1}\operatorname{Var}(x_1u_1)Q^{-1}=\sigma^2Q^{-1}QQ^{-1}=\sigma^2Q^{-1}
$$
and $Q=\operatorname{plim}n^{-1}\sum_{i=1}^n x_ix_i^{\top}$.


TITLE: limit as n approaches infinity of $(-1)^{n}$
QUESTION [2 upvotes]: How would I solve:
$\lim \limits_{n \to \infty} 1+(-1)^n$
Can I split $1$ and $(-1)^n$ up into two different limits added together?
$\lim \limits_{n \to \infty} 1+(-1)^n$  = $\lim \limits_{n \to \infty} 1$ + $\lim \limits_{n \to \infty} (-1)^n$
And if I did this, how would I solve for $\lim \limits_{n \to \infty} (-1)^n$
Thank you

REPLY [0 votes]: You can also think of it like this. We don't know if $\lim_{n \to ∞} (-1)^n$ exits. So we'll set y = $\lim_{n \to ∞} (-1)^n$ and see what happens.
$y = \lim_{n \to ∞} (-1)^n$ (let)
or, $\ln y = \lim_{n \to ∞} n[\ln (-1)]$
$\Rightarrow$ RHS does not exist [∵ $\ln (x)$ is only defined when $x = (0, \infty)$]
$\Rightarrow \lim_{n \to ∞} (-1)^n $ does not exist.
$\Rightarrow \lim_{n \to ∞} 1 + (-1)^n$ does not exist.
Cheers!


TITLE: In general, if $XY$ is independent of $Z$, does it necessarily imply that $Y$ is independent of $Z$?
QUESTION [1 upvotes]: If I have that $XY$ (the product) is independent of $Z$, can I say that $Y$ is independent of $Z$? I tried coming up with a counter example but haven't been able to find one yet.

REPLY [4 votes]: Of course not. If, for example, $Y=Z, X=\frac{1}{Z} \ldots $


text:
\begin{document}

\title{An elementary  proof of the halting property for chakravala algorithm}

\author{A. Bauval}

\begin{abstract} In 1930, A. A. K. Ayyangar allegedly produced the missing proof that the ancient Indian chakravala algorithm -- designed to solve Pell's equation -- always halts. Refining his own elementary arguments, we give a correct and shorter proof.
\end{abstract}

\maketitle

\renewcommand{\thefootnote}{}
\footnote{2010 \emph{Mathematics Subject Classification}:11A: Elementary number theory.}
\footnote{\emph{Key words and phrases}: Chakravala, Pell's equation, Algorithm, Halting problem.}
\renewcommand{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}

\section{Introduction}

The ancient empirical Indian `` cyclic algorithm'', to find a nontrivial solution of Pell's equation $x^2-ny^2=\pm1$ (where $n$ is some nonsquare positive integer) has long been considered as a small variant of the method later independently discovered by Europeans. As such, even renowned mathematicians credited Lagrange for the proof of its validity.\footnote{Ayyangar \cite{Ayyangar} and Selenius \cite{Selenius} give detailed historical analyses of many misconceptions about chakravala. See also \cite{sohum}.} In 1930, A. A. Krishnaswami Ayyangar \cite{Ayyangar} was the first to stress the originality of chakravala and (nearly) give the necessary proof that this more efficient algorithm also reaches the goal. His paper, though sometimes mentionned, does not seem to have been studied with much care,\footnote{Selenius \cite{Selenius} mentions six of Ayyangar's papers (perhaps including \cite{Ayyangar}, but with incomplete reference) but only as ``an attempt to "imitate" the {\sl chakrav\~ala\/} in the form of a continued fraction process'' and also writes: ``Though fairly reviewed, Ayyangar's work attracted very little attention, even in India.''}${}^,$\footnote{Edwards \cite{Edwards}, who does not mention Ayyangar, devotes more than one page (p. 35) of partial indications, through several exercises, to deduce the main properties of the Indian algorithm -- including what we call its halting property -- from those of the ``English'' one.} possibly due to the fact that his proof is rather lengthy. We give a correct and stronger version of his main theorem and use his own arguments to produce a much shorter proof of it.

It is a matter of taste to rephrase the study of both the Indian and European methods in terms of quadratic numbers, or of continued fractions and binary quadratic forms as Ayyangar did. We prefer to stick on using only elementary arithmetic on integers, thereby compromising the belief that the proof for chakravala is at least as hard as for the European algorithm, and was outside Bhaskara's reach (rather than just outside his experimental habits).

The paper is organized as follows: section \ref{best} introduces the two notions, ubiquitous in our paper, of ``best mod $k$ numbers'' -- integers whithin a congruence class which are best approximations of $\sqrt n$ in a certain sense -- and ``steps'', section \ref{description} presents chakravala algorithm --  roughly: a succession of steps -- section \ref{main} contains the main theorem -- according to which the algorithm is somehow reversible -- and sections \ref{twin} and \ref{halting without twins} use it repeatedly to explain why and how the process always halts.

\section{Best mod $k$ numbers, steps, reduced steps}\label{best}
We shall say that a positive integer $m$, chosen within a given congruence class mod $k$, is {\bf best mod $k$}, if $m^2$ is as near of $n$ as possible, i.e. for any positive $m'$ congruent to $m$ mod $k$, $|m^2-n|\le |m'^2-n|$. When  $k<\sqrt n$, such an $m$ must be one of the two elements $m_1,m_2$ of the class which are nearest to $\sqrt n$:
$$0<m_1<\sqrt n<m_2=m_1+k.$$
When only one of them is best, we shall call it {\bf strictly best}. If $k$ is even, it may happen that both are best, i.e. $n-m_1^2=m_2^2-n$. The following is a modified version of a property ``proved'' by Ayyangar\footnote{\cite{Ayyangar}, p. 237--238.}, in order to take this possibility into account.

\begin{prop}\label{propbest}
If some positive integers $k,k',m$ are such that
$$k<\sqrt n\quad{\rm and}\quad m^2-n=\varepsilon kk,\quad{\rm where}\quad\varepsilon=\pm1$$
then, the following are equivalent:
\begin{enumerate}[\upshape $(1)$]
\item $m$ is best mod $k$
\item $k'^2+k^2/4\le n$
\item $m\ge k'+\varepsilon k/2$
\end{enumerate}
and the inequalities in $(2)$ and $(3)$ are strict if and only if $m$ is strictly best.
\end{prop}

\begin{proof}If $m>\sqrt n$ then $\varepsilon=1$ and
$$(1)\Leftrightarrow m^2-n\le n-(m- k)^2\Leftrightarrow m^2-n\le km-k^2/2$$$$\Leftrightarrow kk'\le k(m-k/2)\Leftrightarrow(3)\Leftrightarrow m^2\ge k'^2+kk'+k^2/4\Leftrightarrow(2).$$
If $m<\sqrt n$ then  $\varepsilon=-1$ and
$$(1)\Leftrightarrow n-m^2\le(m+k)^2-n\Leftrightarrow n-m^2\le km+k^2/2,$$which is both equivalent to $kk'\le k(m+k/2)\Leftrightarrow(3)$ and to
$$ m^2+km-(n-k^2/2)\ge0\Leftrightarrow m\ge-k/2+\sqrt{n-k^2/4}$$$$\Leftrightarrow m^2\ge n-k\sqrt{n-k^2/4}\Leftrightarrow k\sqrt{n-k^2/4}\ge kk'\Leftrightarrow(2).$$
(This replaces Ayyangar's squaring argument\footnote{\cite{Ayyangar}, p. 237.}, which was not valid to prove $(3)\Rightarrow(2)$ in this case because $k'-k/2$ may be negative.)
\end{proof}

When these conditions are fulfilled (i.e. $k<\sqrt n$, $|m^2-n|=kk'$ and $m$ best mod $k$), we shall say that the triple $(k,m,k')$ is a {\bf step}. If $m$ is also best mod $k'$, we shall call the triple a {\bf reduced step} (this amounts to say that the reverse triple $(k',m,k)$ is also a step). By characterization $(2)$ of the proposition, any step $(k,m,k')$ satisfies $k'<\sqrt n$, and if $k'\ge k$, this step is reduced.

\section{Chakravala algorithm}\label{description}
Given a nonsquare positive integer $n$, this algorithm produces four sequences of numbers $a_i,b_i,k_i,m_i$, by the following recipe:
\begin{itemize}
\item start the $0$-th stage with $m_{-1}=0,a_0=1,b_0=0,k_0=1$
\item for the $i$-th stage, select $m_i$ congruent to $-m_{i-1}$ mod $k_i$ and best\footnote{If there are two such $m_i$'s, no matter which one is chosen, the sequence of $k_i$'s and the solution eventually produced will be the same. This will be made clearer in section \ref{twin}.} mod $k_i$
\item set $a_{i+1}=(a_im_i+nb_i)/k_i$ and $b_{i+1}=(a_i+m_ib_i)/k_i$
\item set $k_{i+1}=|a_{i+1}^2-nb_{i+1}^2|$ (which is equal to $|m_i^2-n|/k_i$)
\item if $k_{i+1}=1$ then stop, else do the $i+1$-th stage.
\end{itemize}

An easy induction shows that
\begin{itemize}
\item $a_{i+1}$ and $b_{i+1}$ are integers, because for $i>0$, $|a_i(-m_{i-1})+nb_i|=k_ia_{i-1}$ and $|a_i+(-m_{i-1})b_i|=k_ib_{i-1}$,
\item they are coprime, because $|a_ib_{i+1}-b_ia_{i+1}|=1$,
\item $k_{i+1}<\sqrt n$, because $(k_i,m_i,k_{i+1})$ is a step.
\end{itemize}

\section{Main theorem}\label{main}
Whenever the algorithm halts, it produces a nontrivial solution of Pell's equation ($|a_{i+1}^2-nb_{i+1}^2|=k_{i+1}=1$ and $b_{i+1}>0$). Ayyangar noticed that the $a_i,b_i$'s may be forgotten in this halting problem, and claimed to prove the equivalent halting property for the algorithm below. In its formulation, we shall call {\bf successor} of a step $(k,m,k')$ the step (or one of the two steps) $(k',m',k'')$ such that $m'$ is congruent to $-m$ mod $k'$ and best mod $k'$, and $k''=|m'^2-n|/k'$:

\begin{itemize}
\item start the $0$-th stage with $m_{-1}=0,k_0=1$
\item at the $i$-th stage, take for $(k_i,m_i,k_{i+1})$ a successor of $(k_{i-1},m_{i-1},k_i)$ (only $m_{i-1}$ and $k_i$ are used for this)
\item if $k_{i+1}=1$ then stop, else do the $i+1$-th stage.
\end{itemize}

For instance if $n=m^2\pm1$, the sequence is reduced to a single step $(1,m,1)$ and produces the solution $m^2-n.1^2=\mp1$.

The heart of  Ayyangar's paper consists in ``proving'' that ``the'' successor of any {\sl reduced} step (produced or not by the algorithm) is also reduced.\footnote{This theorem is false with his definition of ``reduced'' -- corresponding to what we would call ``strictly reduced'' (meaning that $m$ is {\sl strictly} best mod $k$ and $k'$): we shall see in section \ref{twin} that a strictly reduced step may have two ``twin successors'', which are reduced, but of course not strictly.} A corollary is that every step of the sequence produced by the algorithm is reduced (since the $0$-th step $(1,m_0,k_1)$ is).  The same conclusion follows directly (without induction) from the following strengthening of his theorem:

\begin{theo}A successor of {\bf any} step is reduced, i.e. for any positive integers $k,k',k'',m,m'$ such that $k<\sqrt n$, $kk'=|m^2-n|$, $k'k''=|m'^2-n|$ and $k'\mid m+m'$, if
$$(1)\quad k'^2+\frac{k^2}4\le n\quad{\rm and}\quad(2)\quad k''^2+\frac{k'^2}4\le n,$$
then
$$(3)\quad k'^2+\frac{k''^2}4\le n.$$
\end{theo}

\begin{proof} Since $(3)$ follows from $(2)$ if $k'\le k''$ and from $(1)$ if $k''\le k$, assume from now on that $k<k''<k'$. Let$$\varepsilon=\frac{m^2-n}{kk'},\quad\varepsilon'=\frac{m'^2-n}{k'k''},\quad{\rm and}\quad l=\frac{m+m'}{k'},$$
then
$$k'l(m'-m)=m'^2-m^2=\varepsilon'k'k''-\varepsilon kk'.$$
Simplifying by $k'$ and combining with $m'+m=k'l$ leads to$$(4)\quad m'=\frac12\left(k'l+\frac{\varepsilon'k''-\varepsilon k}l\right)>\frac12\left(k'l+\frac{(\varepsilon'-1)k''}l\right)$$(because $k<k''$) and
$$m=\frac12\left(k'l-\frac{\varepsilon'k''-\varepsilon k}l\right).$$
From this expression of $m$ and hypothesis $(1)$, we deduce
$$\frac12\left(k'l-\frac{\varepsilon'k''-\varepsilon k}l\right)\ge k'+\varepsilon\frac k2$$
hence $l$ cannot be equal to $1$ because $k''<k'$, and when $\varepsilon'=1$, it cannot either be equal to $2$ because $k<k''$. This allows to eliminate $l$ from the lower bound $(4)$:
\begin{itemize}
\item if $\varepsilon'=-1$ then $l\ge 2$ and
$$m'>\frac12\left(k'l-\frac{2k''}l\right)\ge\frac12\left(2k'-\frac{2k''}2\right)=k'-\frac{k''}2$$
\item if $\varepsilon'=1$ then $l\ge 3$ and
$$m'>\frac{k'l}2\ge\frac{3k'}2>k'+\frac{k''}2.$$
\end{itemize}
Since $m'\ge k'+\varepsilon'\frac{k''}2$ is equivalent to $(3)$, this ends the proof.

\end{proof}

\section{Halting with twins}\label{twin}
Recall from section \ref{best} that for any step, there is either a unique `` strict'' successor, or a pair of what we shall call {\bf twin successors} $(k,m_\pm,k')$ with $k$ even, $m_\pm=k'\pm k/2$ and $n=k'^2+k^2/4$. This possibility was missed by Ayyangar, but we shall see that such a ``forking'' in the algorithm is local -- i.e. after the next step, the two variants of the sequence merge back to a single one -- and may occur only once. Moreover, such an ``accident'' will turn out to be more happy than troublesome.

\medskip\noindent{\bf Example.}~
For $n=29$, $5<\sqrt n<6$ and $n-5^2=4<7=6^2-n$ hence the first step $(1,m_0,k_1)$ is given by $m_0=5$ and $k_1=4/k_0=4$. Then, $m_1$ must be congruent to $-5$ mod $4$. Since $3<\sqrt n<7$ and $n-3^2=20=7^2-n$, the second step is a ``twin successor'': either $(4,3,5)$ or $(4,7,5)$. If we choose $(k_1,m_1,k_2)=(4,3,5)$ and compute the following steps, the whole sequence will be $(1,5,4),(4,3,5),(5,7,4),(4,5,1)$, whereas if we choose $(4,7,5)$, we obtain $(1,5,4),(4,7,5),(5,3,4),(4,5,1)$. Computing the solution associated to these two sequences gives the same result: $70^2-13^2.29=-1$.

\medskip\noindent{\bf General computations.}~
When
$$(k_i,m_i,k_{i+1}=k)\quad{\rm and}\quad(k_{i+1},m_{i+1},k_{i+2})=(k,m_\pm,k')$$
are two consecutive steps produced by the algorithm, let us find the two next steps.

By the main theorem, a successor of $(k,m_+,k')$ (resp. $(k,m_-,k')$)  is $(k',m_-,k)$ (resp. $(k',m_+,k)$) and it is the only one, otherwise $k'$ would be equal to $k$ and all the previous (and following) steps would be of the form $(k,m_\pm,k)$, which is impossible since $k$ is even, whereas $k_0=1$.

Similarly, a successor of $(k',m_-,k)$ (resp. $(k',m_+,k)$) is $(k,m_i,k_i)$ and it is the only one, otherwise $k_i$ would be equal to $k'$ and $m_i$ to $m_+$ or $m_-$, which is impossible. Indeed, all the previous (and following) $k_j$'s would then be, alternatively, equal to $k$ or $k'$, hence $k'$ would be equal to $1$ and $k$ to $2$ (since it divides $m_i+m_\pm$) but for $n=1^2+2^2/4=2$, the sequence is merely $(1,1,1)$ and has no twin.

Let us summarize these computations and draw a consequence:
\begin{prop}\label{proptwins}The algorithm produces only one or two sequences. In the latter case, the two sequences are finite, of the form $$(1,m_0,k_1),(k_1,m_1,k_2)\ldots,(k_{i-1},m_{i-1},k_i)(k_i,m_i,k),(k,k'+k/2,k'),$$
$$(k',k'-k/2,k),(k,m_i,k_i),(k_i,m_{i-1},k_{i-1})\ldots,(k_2,m_1,k_1),(k_1,m_0,1),$$
and its reverse,
$$(1,m_0,k_1),(k_1,m_1,k_2)\ldots,(k_{i-1},m_{i-1},k_i)(k_i,m_i,k),(k,k'-k/2,k'),$$
$$(k',k'+k/2,k),(k,m_i,k_i),(k_i,m_{i-1},k_{i-1})\ldots,(k_2,m_1,k_1),(k_1,m_0,1),$$
\end{prop}

\begin{proof}Let us keep the notations of the previous computations to denote the first ``twin step'', if any.  By the main theorem, the two sequences of the proposition -- let us call them $s$ and $s'$ -- are produced by the algorithm. We shall show that they are the only ones. Let $s''$ be any other one. By the general computations above, $s''$ differs from $s$ only by extremely local forkings; in particular, it is finite and has the same length. By the main theorem, its reverse is also produced by the algorithm. By minimality of $i$, $s''$ and its reverse therefore coincide with $s$ up to the $i$-th step, hence $s''$ is equal to $s$ or $s'$.
\end{proof}

Moreover, an easy calculation shows that these two sequences produce the same $(a_j,b_j)$'s -- except the middle one -- hence the same solution of Pell's equation.

\section{Halting without twins}\label{halting without twins}

\begin{prop}When the sequence produced by the algorithm is unique, it is finite and of the form
$$(1,m_0,k_1),(k_1,m_1,k_2)\ldots,(k_2,m_1,k_1),(k_1,m_0,1).$$
\end{prop}

\begin{proof}By hypothesis, there is no twin successor in the sequence, hence there is no ``twin predecessor'' either, by reversal in the general computations of the previous section. By proposition \ref{propbest}, the set of possible steps is finite, hence if the sequence was infinite, the $(i+p)$-th step would be equal to the $i$-th step, for some $i\ge 0$ and $p>0$, so that (since there are no ``twin predecessors'') the $p$-th step would be equal to the $0$-th, $k_p$ would be $1$, and there would be no $p$-th step at all (the algorithm would stop at the end of the $(p-1)$-th stage). This contradiction ends the proof that the sequence is finite. Again, by the main theorem, the reverse sequence is also produced by the algorithm hence (by uniqueness) both are equal.
\end{proof}

\noindent{\bf Remark.} In the previous section, we saw that as soon as some twin step is met, the middle of the sequence is reached and the remaining $k_j,m_j$'s are known, hence only the remaining $a_j,b_j$'s need further computation. By the main theorem, the same happens as soon as we meet some step of the form $(k,m,k)$ or some pair of consecutive steps of the form $(k,m,k'),(k',m,k)$. Therefore, the last proposition contains the main result, from a pragmatic point of vue: either some twin step is met, or one of these two configurations.

config: arxiv


TITLE: If refraction slows down light, isn't it possible to hold light still?
QUESTION [10 upvotes]: I have a quick question about the refraction of light, and I'm sorry if it seems a bit simplistic or even stupid, but I'm still learning.
We know that when light passes through a denser medium, it slows down. However, is there a limit to that slowing down? If no, wouldn't it be possible, with some type of medium we make ourselves (like a crystal), to decrease the light's speed down to a point where we would be able to "see the photons moving forwards"?
I know it is way more complicated than that and that you can't see light unless some other light bounces off it, what I mean is slowing down light to an extreme and unusual speed). That sounds completely absurd but I can't seem to find what is wrong. Can anyone can explain it to me? :)

REPLY [12 votes]: Yes, light can be brought to a complete halt under the right conditions.
To understand how this happens you need to understand what is going on when light slows down in a medium. Light is an oscillating electromagnetic field, and when it passes though anything that contains charged particles (i.e. any matter made from electrons and protons) the electric fied of the light interacts with those charges.
When the light interacts with the charges we have to describe the light/matter system by a new wavefunction that includes all the interacting components. This means the light is not longer purely light - we have a quantum system that mixes up the light with the charged particles. If this mixing is very strong it produces a quasiparticle called a polariton. The polariton is a massive particle so it moves at less than the speed of light.
Under normal circumstances, e.g. light passing through glass, the interaction of the light and the medium is relatively weak and we probably wouldn't use a polariton description. Instead we'd use a classical description as described very nicely in the answers to Why do prisms work (why is refraction frequency dependent)?.
However it is possible to make systems that interact very, very strongly with the light. Specifically Bose-Einstein condensates. This interaction can be so strong that the polaritons become essentially motionless i.e. the light is brought to a stop. This was first achieved in 2001 by a group at the Harvard-Smithsonian Center for Astrophysics, who managed to bring light to a stop in a gas of rubidium atoms. At about the same time a group in Harvard achieved the same result using a Bose-Einstein condensate made from sodium atoms.
The experiments mentioned above require rather extreme conditions to work, but they involve basically the same physics that causes light to slow down by a factor of about 1.5 in glass.


TITLE: What would be an interesting linear bounded operator?
QUESTION [4 upvotes]: Can anyone give me an example of such an operator (preferably, but not necessary, self-adjoint) on a Hilbert space? Not the usual ones you would find in a textbook (multiplication, integral, shift, etc).
I'd would like to calculate the norm and spectrum of it. Also, ones that aren't on doubly infinite sequence spaces (like discrete Laplace operator) would be good.

REPLY [3 votes]: How about the Toeplitz operators on the Hardy-Hilbert space? ($H^2$ on the unit disk).


TITLE: Is this sum less when it contains less positive terms?
QUESTION [1 upvotes]: Problem
Let $\{X_n\}$ be a sequence of real numbers defined by $$x_n=
  \left\{
    \begin{array}{ccrcl}
      {\displaystyle\frac{1}{2k}} & \mbox{if} &
      {\displaystyle n} & {\displaystyle =} &
      {\displaystyle 2k - 1}
      \\[1mm]
      {\displaystyle\frac{1}{2k - 1}} & \mbox{if} &
      {\displaystyle n} & {\displaystyle =} &
      {\displaystyle 2k}
    \end{array}\right.
\\\epsilon_n=[\frac{1}{2}]^n\\
f(x)=\sum_{n:x_n<x}\epsilon_n
$$
(A)Compute f(1), f(1/2)
(B) Determine the set of discontinuities for the function
Solution
So with mathematica I computed $x_n=\{\frac{1}{2},1,\frac{1}{4},\frac{1}{3},\frac{1}{6},\frac{1}{5},\frac{1}{8},\frac{1}{7}...\}$
So, $f(1)=\frac{1}{2}+\sum_{n:x_n<1}\frac{1}{2}^2=\frac{1}{2}+\frac{1}{1-1/2}=\frac{1}{2}+2=\frac{3}{2}$
$f(\frac{1}{2})=\sum_{n:x_n<1/2}\frac{1}{2}^2=\frac{1}{1-1/2}=2$
Yet I noticed that the sum of all terms$=f(\infty)=$ $\sum_0^{\infty}\frac{1}{2}^2=\frac{1}{1-1/2}=2$
Why is $f(1)$ greater than the sum of all terms, when all terms are positive? Shouldn't $f(1)<f(\infty)$
For the points of discontinuity, I think the sequence should be continuous everywhere.
Choose $\delta$ such that $\delta=x_n-x_{n-3},$ Then $\forall \epsilon > 0$, $\forall y\in B_{\delta}(x_n),|x_n-y|<\delta$, $|f(x_n)-f(y)|=|f(x_n)-f(x_n)|<\epsilon$

REPLY [1 votes]: For calculating $f(1)$, see that $\{n\in\mathbb{N}:x_n<x\}=\{n\in\mathbb{N}:n\neq2\}$. $$f(1)=\sum_{\substack{n:x_n<x\\n \neq2}}\varepsilon^n=\dfrac12+\sum_{n=3}^\infty\left(\dfrac12\right)^n=\dfrac34$$
Similarly $$f\left(\dfrac12\right)=\sum_{n=3}^\infty\left(\dfrac12\right)^n=\dfrac14$$
So $f(x)=2>f(1)\:\:\forall\:x>1$.
$f(x)$ is discontinuous at every $x_n$. For see, $\displaystyle\lim_{x\to1^-}f(x)=\dfrac34\neq\lim_{x\to1^+}f(x)=2$


TITLE: Solve $I=\iiint\limits_\Omega z^2 dv$ using spherical coordinate system, $\Omega: x^2 +y^2 + z^2 \le R^2 \cap x^2 +y^2 + z^2 \le 2Rz$
QUESTION [2 upvotes]: Question: Solve $I=\iiint\limits_\Omega z^2 dv$ using spherical coordinate system. $\Omega$ is the common part of $x^2 +y^2 + z^2 \le R^2 $ and $ x^2 +y^2 + z^2 \le 2Rz$.
My attempt:Because $ r^2 \le R^2 and\ r^2 = 2R r\cos \varphi $, so $ 2R\cos \varphi \le r \le R$.
$$\int_0^{2\pi}d\theta \int_0^{\pi/2}\sin\varphi d\varphi \int_{2R\cos \varphi}^R r^2\cdot (r\cos\varphi)^2 dr = 2\pi\int_0^{\pi/2}\cos^2\varphi \sin \varphi d\varphi \int_{2R\cos \varphi}^R r^4 dr =$$
$$\frac{2\pi}5 \int_0^{\pi/2} cos^2\varphi \sin \varphi [R^5-({2R\cos \varphi})^5  ]d\varphi = \frac{2\pi R^5}5 \int_0^{\pi/2}(cos^2\varphi \sin \varphi-32cos^7\varphi \sin \varphi )d\varphi $$
Can anyone point out where is wrong? Is the lower boundary $ 2R \cos \varphi $ correct？
Update based on the answer:
$$I=\int_0^{2\pi}d\theta \int_0^{\pi/4}\sin\varphi \cos^2\varphi d\varphi \int_0^R r^4 dr - \int_0^{2\pi}d\theta \int_0^{\pi/2}\sin\varphi \cos^2\varphi d\varphi \int_0^{2R\cos \varphi} r^4 dr $$
Is this equation correct?

REPLY [2 votes]: Your second equation gives $0\leq r\leq 2R\cos(\varphi)$, so $0\leq r\leq \min{(R,2R\cos{\varphi})}$ is the correct bound.
You now need to break up the integral into the regions where each upper bound applies, integrate, and add them.


TITLE: Proper map from continuous if it maps compact sets to compact sets
QUESTION [1 upvotes]: Suppose that $X,Y$ are - say - normed vector spaces.
Let $f:X\to Y$ be such that for all sets $K\subset X$: $$f(K) \text{ compact}\iff K\text{ compact}.$$
Does it hold that $f$ is continuous?
Addendum: What if $X,Y$ are Hausdorff spaces?
————
Intuitively it seems that this is wrong because there are both proper maps which are not continuous and maps that compact sets to compact sets which are also not continuous.
However, if $f$ is a compact injection then $f$ is continuous.

REPLY [0 votes]: Yes, it is continuous. And it is enough that $X$ is Hausdorff compactly generated and $Y$ is Hausdorff.
If $X$ is compactly generated and we want to prove the continuity of $f$, then without loss of generality, $X$ is compact (as in the answer of the linked question), and so $f(X)$ is compact. Every closed $F ⊆ f(X)$ is compact, and so $f^{-1}(F)$ is compact since $f(f^{-1}(F)) = F$. Since $X$ is Hausdorff, $f^{-1}(F)$ is closed. That proves the continuity.
Moreover, we haven't used the full power of our assumption yet. For every $y ∈ Y$, the fiber $f^{-1}(y)$ is compact and discrete (every $A ⊆ f^{-1}(y)$ is compact and so closed since $f(A) ⊆ \{y\}$ is compact). Hence it is finite, and $f$ is finite-to-one.


TITLE: Proof of ∀(x,y)∈R[|x-y| ≥ |x| - |y|]
QUESTION [0 upvotes]: Is the following proof correct?
To prove: ∀(x,y)∈R[|x-y| ≥ |x| - |y|]; where R is the set of real numbers.
Proof:
Lemma: ∀(x,y)∈R[|x+y| ≤ |x| + |y|]
Since x and y are arbitrary real numbers we have,
∀(x,y)∈R[|x+(-y)| ≤ |x| + |-y|]
Since |y| = |-y|,
|x - y| ≤ |x| + |y| ⇔ -|x - y| ≥ -|x| - |y|⇒|x - y| ≥ -|x| - |y| ⇔|x - y| + |y| ≥ -|x|
Applying the Lemma we get, |x - y| + |y| ≥ |x - y + y| = |x|
Therefore, |x - y| ≥ |x| - |y|
This concludes the proof.

REPLY [2 votes]: Or more simply:

Proof. Applying the lemma we get $|x| = |(x-y)+y| \leq |x-y| + |y|$, and then adding $-|y|$ to both sides we get the desired result. $\blacksquare$


TITLE: Bounded gradient implies Lipschitz on non-convex set
QUESTION [2 upvotes]: There are loads of questions and answers concerning the following problem, but here we have a slight variation:
Let $U$ be an open subset of $\mathbb{R}^n$ and $f: U \rightarrow \mathbb{R}$ be differentiable such that the derivative is bounded by the constant $L \geq 0$. Show that $f$ is a globally lipschitz-function.
So, usually the domain is $\mathbb{R}^n$ and then this is pretty easy to show by using the mean-value-theorem. However, now we have an arbitrary open set as the domain and as far as I know, we need convexity of the set in order to use the MVT for two arbitrary points in the set. Does this statement still hold? If yes, what would the argument be? As a side note I have found this post Sub-gradient and super-gradient are bounded implies globally Lipschitz. which goes in the direction of my question, but does not answer it.

REPLY [6 votes]: Simple counterexample: $n=1$, $U=(-1,0)\cup(0,1)$, $f:U\to\Bbb R$ defined by $$f(x)=\begin{cases}1,&(x\in(-1,0)),
\\-1,&(x\in(0,1)).\end{cases}$$
Now $f'=0$ on all of $U$, although $f$ is not uniformly continuous, hence not Lipschitz.
Edit: If $U$ is an open disk in the plane with one radius removed then $U$ is connected, simply connected and contractible, but you can easily concoct an $f$ giving a counterexample.


TITLE: Show that $\hat{f}$ is integrable over $\mathbb{R}$ and $\int_E f$=$\int_{\mathbb{R}} \hat{f}$.
QUESTION [1 upvotes]: Let $f$ be integrable over $E$. Define $\hat{f}$ to be the extension of $f$ to all of $\mathbb{R}$  obtained by setting $\hat{f}$$\equiv 0$ outside of $E$. Show that $\hat{f}$ is integrable over $\mathbb{R}$ and $\int_E f$=$\int_{\mathbb{R}} \hat{f}$.

This is a problem from Royden 4th edition.
I am unsure how to proof this problem. We know $f$ is integrable over $E$. And we have thm. $26$ in the book that has the condition $h\equiv0$. However, I think I may need to use the Vitali's convergence theorem instead? A complete proof or concrete steps are appreciated.

REPLY [3 votes]: First, let's show that $\hat{f}$ is Lebesgue integrable on $\mathbb{R}$. Consider the set $E_{\alpha} = \{ x\in \mathbb{R}: \hat{f}(x) \geq \alpha\}$ for $\alpha \in \mathbb{R}$. We have two cases
$$\alpha \leq 0: E_{\alpha} = \{ x\in \mathbb{R}: \hat{f}(x) \geq \alpha\} = (\mathbb{R}\setminus E) \cup \{x\in E: f(x) \geq \alpha\}$$
$$\alpha > 0: E_{\alpha} = \{ x\in \mathbb{R}: \hat{f}(x) \geq \alpha\} = \{x\in E: f(x) \geq \alpha\}$$
So, it's Lebesgue measurable for any $\alpha \in \mathbb{R}$. This shows that $\hat{f}$ is integrable on $\mathbb{R}$. A simple calculation shows that
$$\int_\mathbb{R} \hat{f} = \int_{\mathbb{R}\setminus E} \hat{f} + \int_E \hat{f} $$
The first term in the RHS is zero. Also, the second term is equal to $\int_E f$. Therefore
 $$\int_\mathbb{R} \hat{f} =  \int_E f $$