TITLE: Can $\Bbb R^+$ form a field?
QUESTION [3 upvotes]: Consider $\Bbb R$ as a vector space. We have a vector space isomorphism $\exp:\Bbb R \to \Bbb R^+$ where we define new operations $a+b:=ab$ and $kb:=b^k.$
Now a natural inquiry at this point might be:

Does $\Bbb R^+$ also form a field?

For $\Bbb R^+$ to form a field we need to define addition, subtraction, multiplication, and division. Addition has already been defined above as $a+b:=ab.$

REPLY [4 votes]: If I understand correctly, then the question asks whether it is possible to define a "multiplication" map $m: \Bbb R^+ \times \Bbb R^+\rightarrow \Bbb R^+$ such that, together with the "addition" map $a: \Bbb R^+ \times \Bbb R^+ \rightarrow \Bbb R^+$ sending $(a, b)$ to $a\cdot b$, makes $\Bbb R^+$ a field.
This is of course possible, in view that $\exp$ is an isomorphism of abelian groups from $(\Bbb R, +)$ to $(\Bbb R^+, \cdot)$.
We simply define the field structure on $\Bbb R^+$ by pushing out the field structure on $\Bbb R$ via the $\exp$ map.
More explicitly, we define $m: \Bbb R^+ \times \Bbb R^+ \rightarrow \Bbb R^+$ by sending $(a, b)$ to $\exp(\ln(a)\cdot \ln(b))$, which is equal to both $a^{\ln (b)}$ and $b^{\ln (a)}$.


TITLE: Does abundance of max cliques make it easy to solve COLORABILITY?
QUESTION [2 upvotes]: Let $q\geq 3$. We know that $q$-COLORABILITY is an NP-complete problem.
Suppose that $G$ is a graph such that each vertex of $G$ is part of a $q$-clique (i.e. $K_q$). Since we may assume that $G$ does not contain $K_{q+1}$, the condition is the same as saying that $G$ has a clique cover $S$ comprised of maximum cliques in $G$.
Does this condition make it easy to solve $q$-COLORABILITY of $G$? If not, would the following extra condition make it possible:
$|C\cap D|\leq 2$ for every two distinct members $C,D\in S$ ?
Remark: there are known results on $q$-COLORABILITY when $G$ has a clique edge cover $S$ such that (i) $|C\cap D|\leq 1$ for every two distinct members $C,D\in S$, and (ii) each vertex of $G$ belong to at most 2 members in $S$. For instance, see Walter Klotz, Clique Covers and Coloring Problems of Graphs.

REPLY [3 votes]: As written, the problem is NP-complete even when you require the elements of $S$ to be pairwise disjoint (which also implies that every vertex belongs to a unique element of $S$): as a reduction from $q$-COLOURABILITY, we can attach to each vertex $q-1$ new vertices to form a $q$-clique.
This does not contradict the results from the cited paper by Klotz, because in that paper, “clique cover” means “clique edge cover” rather than “clique vertex cover”.
If you restate the question with clique edge covers, i.e., requiring that each edge of $G$ is included in a $q$-clique, the problem is still NP-complete: similar to the above, we can attach to each edge $q-2$ new vertices to form a $q$-clique. This will make $|C\cap D|\le1$ for each distinct $C,D\in S$. (It will violate condition (ii), as every original vertex belongs to as many elements of $S$ as was its degree in the original graph.)


TITLE: Will a two-dimensional curve have finite length if the curve is bounded and its velocity (derivative) tends to zero?
QUESTION [0 upvotes]: Suppose we have a smooth curve $\vec{r}:[0,+\infty)\to\mathbb{R}^2$ that satisfies: 1) being bounded, i.e., $\exists M>0$ such that $\|\vec{r}(t)\|<M$ for all $t\in[0,+\infty)$; 2) its velocity tends to zero, i.e., $\lim_{t\to+\infty} r'(t)=0$. My question is: Can we prove $\vec{r}(t)$ has finite length, i.e., $\int_0^{+\infty}\|r'(t)\|dt<\infty$?
I found that some famous examples of bounded curves with infinity length do not satisfy the above conditions. For example, the Koch curve has infinity length but it is not smooth nor its velocity tends to zero; the graph of the function defined by $f(x) = x \sin(1/x)$ around zero has infinity length and is smooth but its velocity does not tend to zero.
I wonder is there a counterexample for my case, or it is sufficient for finite length?
Any ideas and suggestions are welcomed. Thanks in advance!

REPLY [1 votes]: Consider your second example $f(x) = x\sin\left(\frac{1}{x}\right)$ parametrized as
$$x(t) = 1/t\qquad (t\geq 1)$$
We compute
$$\|r'(t)\| = \sqrt{\left(\frac{df}{dt}\right)^2 + \left(\frac{dx}{dt}\right)^2} = \sqrt{\frac{(t\cos(t)-\sin(t))^2 +1}{t^4}}$$
which can be approximated by $\frac{1}{t}$ as $t\to \infty$, hence velocity tends to zero.  As you've pointed out, the other condition is satisfied and the curve has infinite length.
More generally, it should be possible to generate other counterexamples by taking functions whose smooth graphs are bounded with infinite length, and parametrizing them to slow down as they approach the appropriate $x$ coordinate.


TITLE: Solve $ab + cd = -1; ac + bd = -1; ad + bc = -1$ over the integers
QUESTION [2 upvotes]: I am trying to solve this problem:

Solve the system of equations
  \begin{align}
\begin{cases}
ab + cd = -1 \\
ac + bd = -1 \\
ad + bc = -1
\end{cases}
\end{align}
  for the integers $a$, $b$, $c$ and $d$.

I have found that the first equation gives $d = \dfrac{-1-cd}{a}$, which gives $a\neq0$. Other than that, I don't know where to start.
Tips, help or solution is very appreciated. Thanks!

REPLY [3 votes]: Hint
Subtract equation 2 from equation 1 and equ 3 from equ 1 to get
\begin{align*}
(a-d)(b-c)&=0\\
(a-c)(b-d)&=0
\end{align*}
From this we can infer that either $a=d$ or $b=c$ and either $a=c$ or $b=d$. Now try these possibilities in the system given. Can you proceed from here?

REPLY [2 votes]: Add equation 1 and 2, 1 and 3, 2 and 3 you get
$(a+d)(b+c)=-2$
$(a+c)(b+d)=-2$
$(a+b)(c+d)=-2$
All of them are integers, so it can only be $-2\times1$ or $2\times(-1)$.
List out all possibility the solutions can only be any permutation of $(1,1,1,-2)$ or $(-1,-1,-1,2)$

REPLY [1 votes]: Hint:
Squaring the equations gives
\begin{align}
\begin{cases}
a^2b^2 +2abcd+ c^2d^2 = 1 \\
a^2c^2 +2abcd +b^2d^2 = 1 \\
a^2d^2 + 2abcd+b^2c^2 = 1
\end{cases}
\end{align}
Subtracting them yields
\begin{align}
\begin{cases}
(a^2-b^2)(c^2-d^2)=0 \\
(a^2-c^2)(b^2-d^2)=0 \\
(a^2-d^2)(b^2-c^2)=0
\end{cases}
\end{align}
Now consider some cases.


TITLE: What's the domain of this function?
QUESTION [0 upvotes]: $$f(x,y,z) = \frac{1}{x-z}$$
I see two possible domains:
$$D = \{x,y,z \in \mathbb{R}\mid x \neq z\}$$
or $$D = \{x,z \in \mathbb{R}\mid x \neq z\}$$
Is it equally valid to say the function has either domain?

REPLY [2 votes]: The domain of the function is the set of inputs that are allowed into the function (i.e., the inputs that, when input into the function, make sense).
You are right that we cannot have $x = z$.  But look at how the function is defined.  It is $f(x,y,z)$.  It takes as input a vector with $3$ components, and it outputs a number.  So since the domain is the set of inputs that have an output, that means our domain must be a set of vectors with 3 components.
Here is how I would write the domain:
$D = \{ (x,y,z) \mid x,y,z \in \mathbb{R}, x \neq z \}$.  Here, $D$ is a subset of $\mathbb{R}^{3}$, which the space of vectors with 3 components and real numbers as components.
You can't just say the domain is $D = \{ x,y,z \in \mathbb{R} \mid x \neq z \}$ because this set is a subset of $\mathbb{R}$, not $\mathbb{R}^{3}$.  The input for the function $f(x,y,z)$ are vectors of the form $(a,b,c)$ with $a,b,c \in \mathbb{R}$ (i.e., $(a,b,c) \in \mathbb{R}^{3})$.


TITLE: Show that $a^p \equiv 1$ (mod $p^n$) $\Rightarrow a \equiv 1$ (mod $p^{n-1}$)
QUESTION [1 upvotes]: I'm trying to show that $a^p \equiv 1$ (mod $p^n$) $\Rightarrow a \equiv 1$ (mod $p^{n-1}$), where $p$ is an odd prime.
Since $a^p \equiv 1$ (mod $p^n$) $\iff aa^{p-1} \equiv 1$ (mod $p^{n-1}p$), I was hoping to use Fermat's theorem, which states that $a^{p-1} \equiv 1$ (mod $p$). I therefore tried substituting $a^{p-1}$ with $pk + 1$ in the equation but I didn't manage to solve it like that.
I've been trying to solve it algebraically for some time but is no where close so I could use some help and ideas.

REPLY [2 votes]: Actually,

$a^p \equiv 1 \bmod p^n \iff a \equiv 1 \bmod p^{n-1}$

The key relevant fact is this:

If $G$ is a cyclic group of order $m$ and $d$ divides $m$, then there is  exactly one subgroup of order $d$: $H=\{ x \in G : x^d=1 \}$.

The group in question is $G=U(p^n)$, the group of units mod $p^n$. Then $G$ has order $\phi(p^n)=p^{n-1}(p-1)$, a multiple of $p$. Let $H$ be the subgroup of order $p$.
If $a \equiv 1 \bmod p^{n-1}$ then $a=1+bp^{n-1}$ and so $a^p=(1+bp^{n-1})^p=1+cp^n \equiv 1 \bmod p^n$. In other words, $a=1+bp^{n-1} \in H$ for $b=0,\dots,p-1$. This gives us $p$ elements in $H$. Therefore, they are all the elements of $H$ since $H$ has order $p$.


TITLE: Taylor of second order for System of Differential Equations
QUESTION [1 upvotes]: I need to solve the next system
\begin{eqnarray}
x' &=& y+x(x^2 + y^2) \\
y' &=& -x + y(x^2 + y^2)
\end{eqnarray}
with $x(0) = 4$, $y(0) = 0$
I don't know how to start so I know use this method (Taylor of second order) with the case "$x' = f(x, t)$, $x(t_{0}) = x_{0}$" using the Taylor's expansion.

REPLY [1 votes]: The question asks how to solve the equation using Taylor series (which is well explained in the other answer). However the given equation can be solved analytically which is what I will show here even though this is not exactly what the question asks for. Having an analytical solution is anyway useful to check a numerical or series solution.

The two coupled ODEs can be combined to give us the two equations
$$xx' + yy' = (x^2+y^2)^2$$
$$y'x - yx' = -(x^2+y^2)$$
Since $2(xx'+yy') = (x^2+y^2)'$ and $(y/x)' = \frac{y'x-yx'}{x^2}$ we can define $R^2 = x^2+y^2$ and $\omega = \frac{y}{x}$ to get two simple uncoupled ODEs
$$R'= R^3~~~\text{and}~~~\omega' = -1-\omega^2$$
whose solution is
$$R(t) = \frac{1}{\sqrt{c-2t}}~~~\text{and}~~~\omega(t) = -\tan(t + d)$$
where $c,d$ are constants that can be fixed by imposing the initial conditions $R(0) = 4$ and $\omega(0) = 0$. The solution for $x(t)$ and $y(t)$ can now be found from the algebratic relationships
$$x^2+y^2 = R^2~~~\text{and}~~~\omega = \frac{y}{x}\implies x^2 = \frac{R^2}{1+\omega^2}~~~\text{and}~~~y^2 = \frac{R^2\omega^2}{1+\omega^2}$$
which gives us the solution
$$x(t) = \frac{4\cos(t)}{\sqrt{1-32t}}~~~\text{and}~~~y(t) = -\frac{4\sin(t)}{\sqrt{1-32t}}$$

We can Taylor expand the analytical solution to get a series solution
$$x(t) = 4+64 t+1534 t^2+40928 t^3+\frac{6876673 t^4}{6}+\mathcal{O}\left(t^5\right)$$
$$y(t) = -4 t-64 t^2-\frac{4606 t^3}{3}-\frac{122848 t^4}{3}+\mathcal{O}\left(t^5\right)$$
Notice the huge numbers that occur as the Taylor-coefficients above. This signifies that the solution is probably only valid in a short interval around $t=0$. This can be understood from the analytical solution as it blows up at $t = \frac{1}{32}$ which is also the convergence radius of the Taylor series.


TITLE: Second partial derivatives and chain rule doubt
QUESTION [1 upvotes]: In a problem in my textbook i had the following expression:
If $z = f(x,y)$ has continuous second-order partial derivatives and $x = r^{2}+s^{2}$ and $y = 2rs$, find $\displaystyle\frac{\partial z}{\partial r}$ and with this, $\displaystyle\frac{\partial^{2}z}{\partial r^{2}}$

I obtained that $\displaystyle\frac{\partial z}{\partial r}$ was:
$\displaystyle\frac{\partial z}{\partial r} = 2\displaystyle\frac{\partial z}{\partial x}+2r\displaystyle\frac{\partial z}{\partial x}+2s\displaystyle\frac{\partial z}{\partial y}$
However, I'm not sure on how to begin in order to find the second order partial derivative. I saw that in my textbook they obtained that:
$\displaystyle\frac{\partial}{\partial r} (\displaystyle\frac{\partial z}{\partial x})=\displaystyle\frac{\partial}{\partial x}(\displaystyle\frac{\partial z}{\partial x})\displaystyle\frac{\partial x}{\partial r}+\displaystyle\frac{\partial}{\partial y}(\displaystyle\frac{\partial z}{\partial x})\displaystyle\frac{\partial y}{\partial r}$
And similarly the same case for $\displaystyle\frac{\partial}{\partial r} (\displaystyle\frac{\partial z}{\partial y})$
So essentially from what I can understand from this, they are assuming that $\displaystyle\frac{\partial z}{\partial x}$ is a function of both x and y? How can we know that though? Or is it something that i should just know? (what could happen if the partial derivative is just expressed in terms of only x or only y?)

REPLY [1 votes]: There is a mistake in your computations. Note that
$$\frac{\partial z}{\partial r}=\frac{\partial z}{\partial x} \frac{\partial x}{\partial r}+\frac{\partial z}{\partial y}\frac{\partial y}{\partial r}=
 \frac{\partial z}{\partial x} 2r+\frac{\partial z}{\partial y}2s.$$
For the second derivative, it is useful to change notation by considering
$$\frac{\partial z}{\partial r}=g\cdot 2r+ h\cdot 2s,
$$
with $ \frac{\partial z}{\partial x}:=g(x,y)$ and $ \frac{\partial z}{\partial y}=h(x,y)$. All you need is to apply the partial derivative, as before. This answer can help you with notation.


TITLE: Solve the recurrence relation $u_{n+1}-5u_{n}+6u_{n-1}=2$ subject to $u_0=u_1=1$
QUESTION [0 upvotes]: This comes from a problem sheet I found online, which since seems to have been removed. Either way, here's my attempt:
For the homogeneous case, we have
$$w_{n+1}-5w_{n}+6w_{n-1}=2.$$
Its auxiliary equation $\lambda^2-5\lambda+6=0$ has solutions $\lambda=2$ and $\lambda=3$, so $w_n=A2^n+B3^n$, for constants $A,B$.
For the particular solution, I try guessing $v_n=C$, and get
$$C-5C+6C=2,$$
which implies $C=1$.
So the general solution is $u_n=1+A2^n+B3^n$.
Substituting in the initial conditions, I get
$$u_0=1+A+B=1$$
$$u_1=1+2A+3B=1,$$
which implies $A=B=0$.
So is the only solution is $u_n=1$ for all $n$, or is there a way to find other (less trivial) solutions?

REPLY [0 votes]: It would be more useful to have a solution to the general form
$$u_n=au_{n-1}+bu_{n-2}+c$$
To that end, let $u_n=f_n-p$, so that
$$f_n=af_{n-1}+bf_{n-2}+c-p(a+b-1)$$
Now let $p=\frac{c}{a+b-1}$ to get the canonical form of the generalized Fibonacci form,
$$f_n=af_{n-1}+bf_{n-2}$$
Using the methods that we have shown previously here, the general solution can be expressed as
$${{f}_{n}}=\frac{\left( {{f}_{1}}-{{f}_{0}}\beta  \right)\,{{\alpha }^{n}}-\left( {{f}_{1}}-{{f}_{0}}\alpha\right)\,{{\beta }^{n}}}{\alpha -\beta}\\
\alpha,\beta=\frac{1\pm\sqrt{a^2+4b}}{2}$$
The rest is straightforward. The result for $u_n=f_n-p$. In the present case we have the rather trivial solutions $f_n=0$ and $u_n=1$. But the general solution is valid for any $a,b,c$. I have tested this numerically for $(a,b,c)\in[-5,5]$, integers and non-integers alike.


TITLE: If I launch a coin, will it always fall down?
QUESTION [0 upvotes]: I was running in the university aisle (I was late for the statistics lesson) when I heard: "In normal condition there is a possiblity that if you launch a coin instead of falling down it'll go up". Is it true?
From my basic physic knowledge the coin will have to change its mass from positive to negative, correct? What is the possibility?

REPLY [1 votes]: The equation for the force of gravity is:
$$
GMm/r^2
$$
Where G is the gravitational constant, M is the mass of the gravitational source being looked at (in this case the Earth), m is the mass of the coin and r is the distance from the gravitational source.
Gravitational potential energy is defined as the work needed to move a mass from an infinite distance to a finite distance away from the source of gravity, the equation for this is:
$$
\int_∞^rGMm/r^2dr=-GMm/r
$$
This can be compared to the equation for kinetic energy to find where they cancel out. When they cancel you reach what is called "escape velocity"; at this speed the coin will go up and not come back down because, mathematically, the distance it travels before it stops accelerating is infinite. The equation for this can be worked out like this:
$$mv^2/2=GMm/r$$
$$v^2/2=GM/r$$
$$v^2=2GM/r$$
$$v=\sqrt(2GM/r)$$


TITLE: How many $4$ digits numbers can be obtained by using $1,1,2,3,4,5$?
QUESTION [0 upvotes]: My friend asked me this question. First I am wondering whether this problem is well defined.
However, my attemp was:
a. Counting all 4 digits numbers from $\{1,2,3,4,5\}$ which is $5 \cdot 4 \cdot 3 \cdot 2= 120$ options. I meant that no double $1$ will appear.
b. $4$ digits numbers with double $1$: there are $4$ ways to locate  $8$ twice. multiplying by $4 \cdot 3=12$ options to fill in the last two digits we get: $48$ options.
So eventually there are $168$ numbers that satisfy these conditions.
Am I correct? should it be written more rigorously?

REPLY [1 votes]: Take the complement of your second and third cases. $-11-$ and $-1-1$


TITLE: Small neighborhoods of singularities on varieties
QUESTION [8 upvotes]: In Singular points of complex hypersurfaces, John Milnor proves the following theorem:
Let $x \in V$ be a point on a variety $V$ in $\mathbb{R}^n$ or $\mathbb{C}^n$. Assume $x$ is either a smooth point or an isolated singularity. Let $D_{\epsilon}$ be the closed $\epsilon$-ball about $x$, $S_{\epsilon}$ its boundary (the sphere about $x$ of radius $\epsilon$), and $K = V \cap S_{\epsilon}$.  Then for $\epsilon$ sufficiently small, the pair $(D_{\epsilon}, V \cap D_{\epsilon})$ is homeomorphic to the pair $(CS_{\epsilon}, CK)$, where $C$ denotes taking the cone. (Theorem 2.10)
In Remark 2.11, Milnor observes that this theorem "likely" holds even if $x$ is a non-isolated singularity; in particular, it is known even in this case that "a suitably chosen neighborhood of any point is homeomorphic to the cone over something."
This book was written in 1968. What is the current status of this problem?

REPLY [4 votes]: Indeed the following theorem to me seems exactly you were looking for (see J. Bochnak, M. Coste, M-F. Roy, "Real algebraic geometry", Theorem 9.3.6 [Local conic structure]):
Let $E$ be a semialgebraic susbet of $\mathbb{R}^n$ and $x$ be a nonisolated point of $E.$ Let also $D_\epsilon$ be the closed $\epsilon$-ball around $x$ and $S_\epsilon$ its boundary. Set $K=S_\epsilon \cap E$. Then there for $\epsilon>0$ small enough the pair $(D_\epsilon,E∩D_\epsilon)$ is semialgebraically homeomorphic to the pair $(CS_\epsilon,CK)$, where $C$ denotes taking the cone.
Moreover the semialgebraic homeomorphism can be chosen as to preserve the distance from $x.$
Two words of remarks on the previous statement:

Every real or complex algebraic set in $\mathbb{R}^n$ or in $\mathbb{C}^n\simeq \mathbb{R}^{2n}$ is a semialgebraic set.
The point $x$ is any nonisolated point of $E$ (no matter singular - in whatever meaning this word has for a general semialgebraic set - or regular).


TITLE: Tricky trigonometric sum evaluation
QUESTION [4 upvotes]: Prove that the sum $$\sum_{k=1}^{n-1} (n-k)\cdot\cos\left(\frac{2k\pi}{n}\right) $$
Is an integer for any $n\geq 3$.
I found this in my textbook but am unable to evaluate this sum. Any help would be appreciated.

REPLY [4 votes]: We have (by replacing $k$ with $n-k$):
$$S=\sum_{k=1}^{n-1}(n-k)\cos\frac{2\pi k}{n} = \sum_{k=1}^{n-1}k\cos\frac{2\pi k}{n}$$
and by setting $\omega = \exp\frac{2\pi i}{n}$ it follows that:
$$ S = \Re \sum_{k=1}^{n-1} k \omega^k. $$
Since:
$$\begin{eqnarray*} (1-\omega)\sum_{k=1}^{n-1}k\omega^k&=&\sum_{k=1}^{n-1}k\omega^k-\sum_{k=1}^{n-1}k\omega^{k+1}=\sum_{k=1}^{n-1}k\omega^k-\sum_{k=2}^{n}(k-1)\omega^{k}\\&=&\omega-(n-1)+\sum_{k=2}^{n-1}\omega^k=-n\end{eqnarray*}$$
we have:

$$ S = \Re\frac{n}{\omega-1}=n\cdot\Re\frac{1}{\left(\cos\frac{2\pi}{n}-1\right)+i\sin\frac{2\pi}{n}} = -\frac{n}{2}.$$


TITLE: Approximate $\int_0^{\pi /2} \frac{ds}{\sqrt{1-x\sin^2s}}$
QUESTION [7 upvotes]: I am trying to approximate the following integral
$$K(x)=\int\limits_0^{\pi /2} \frac{ds}{\sqrt{1-x\sin^2s}}$$
with $0<x<1$.
I need to show that for x close to one that $K(x)\sim -\frac{1}{2}\ln(1-x)$.
My first attempt was to Taylor expand the function $f(x)= (1-x\sin^2s)^{-1/2}$ about $x=1$. I did this using $f(x)\approx f(1)+f'(1)(x-1)$. I integrated the result and found that $K(x)\sim \left[\frac{5-x}{4}\ln|\sec s + \tan s|\right]_0^{\pi/2} - \left[\frac{1-x}{4}\sec s \tan s \right]_0^{\pi/2}$, which goes to infinity when $s=\pi/2$.
I can't think of another way to approach this, so any advice would be helpful.

REPLY [3 votes]: The integral as written is the
complete elliptic integral of the first kind and it can be expressed in term of hypergeometric function:
$$K(x) = \frac{\pi}{2}\,_2F_1(\frac12,\frac12;1;x)\tag{*1}$$
We know when $\gamma = \alpha + \beta$, $\alpha$ and $\beta \ne 0, -1, -2, \ldots$, $|\arg(1-x)| < \pi$, $|1-x| < 1$, the hypergeometric function has following
expansion near $x = 1$:
$$\begin{align}
\,_2F_1(\alpha,\beta;\gamma;x) =
& \frac{-\Gamma(\gamma)}{\Gamma(\alpha)\Gamma(\beta)}
\sum_{n=0}^{\infty}\frac{(\alpha)_n(\beta)_n}{n!^2}(1-x)^n \times\\
& \left\{
\psi(\alpha+n)+\psi(\beta+n) -2\psi(1+n) + \log(1-x)
\right\}
\end{align}$$
where $(t)_n$ is the rising Pochhammer symbol and $\psi(t)$ is the
digamma function.
Substitute this back into $(*1)$ for $x$ near $1$, we have up to $O((1-x)\log(1-x))$,
$$K(x) \sim -\frac12 \left\{ 2\psi(\frac{1}{2}) - 2\psi(1) + \log(1-x)\right\}
          = \log 4 - \frac12\log(1-x)$$
Actually, we can derive this leading term by elementary means.
Let $\delta = \sqrt{\frac{1-x}{x}}$, $u = \cos s = \delta \sinh\theta$, we have
$$\begin{align}
K(x)
= & \frac{1}{\sqrt{x}}\int_0^{\frac{\pi}{2}} \frac{ds}{\sqrt{\delta^2 + \cos^2\!s}}\\
= & \frac{1}{\sqrt{x}}\int_0^1 \frac{du}{\sqrt{\delta^2 + u^2}\sqrt{1-u^2}}\\
= & \frac{1}{\sqrt{x}}\left\{
\int_0^1  \frac{du}{\sqrt{\delta^2 + u^2}} +
\int_0^1 \frac{1-\sqrt{1-u^2}}{\sqrt{\delta^2+u^2}} \frac{du}{\sqrt{1 - u^2}}
\right\}\\
= & \frac{1}{\sqrt{x}}\left\{
\int_0^1 \frac{du}{\sqrt{\delta^2 + u^2}} +
\int_0^{\frac{\pi}{2}}\frac{1-\sin s}{\sqrt{\delta^2 + \cos^2\!s}} ds
\right\}\\
= & \frac{1}{\sqrt{x}}\left\{
\int_0^{\sinh^{-1}\frac{1}{\delta}} d\theta +
\int_0^{\frac{\pi}{2}}\frac{1-\sin s}{\sqrt{\delta^2 + \cos^2\!s}} ds
\right\}\\
\end{align}$$
The $2^{nd}$ integral in the RHS has a finite limit as $\delta \to 0$.
If we replace it by its limit, we will introduce an error that won't affect
our determination of the leading term. Up to $o(1)$$\color{blue}{^{[1]}}$, we find:
$$\begin{align}
K(x)
\sim & \frac{1}{\sqrt{x}}\left\{\sinh^{-1}\frac{1}{\delta} + \int_0^{\frac{\pi}{2}}\frac{1-\sin s}{\cos s} ds
\right\}\\
= & \frac{1}{\sqrt{x}}\left\{ \log\left(\frac{1+\sqrt{1+\delta^2}}{\delta}\right) + \log 2\right\}\\
= & \frac{1}{\sqrt{x}}\left\{ \log\left(\frac{\sqrt{x}+1}{\sqrt{1-x}}\right) + \log 2\right\}\\
\sim & (1 + O(1-x))
\left\{\log\left(\frac{1 + O(1-x) + 1}{\sqrt{1-x}}\right) + \log 2\right\}\\
\sim & \log 4 - \frac12\log(1-x) + O((1-x)\log(1-x))
\end{align}$$
recovering the leading term as expected.
Notes

$\color{blue}{[1]}$ A more careful analysis shows the error introduced in this step is of the order $O(\delta^2\log\delta) = O((1-x)\log(1-x))$.


TITLE: Is this graph ergodic?
QUESTION [2 upvotes]: I had a long discussion with a friend of mine about if this simple graph is ergodic. I think it is because every state can be reached in an non-endless number of steps. My friend argues that it is not because there are no state transitions from each node to itself. Is that required? If somebody has a few examples for each case, it would perhaps helps me to understand it better --- other than the pure math...
A <----> B

Here the transition matrix:
     A    B
 A  0.0  1.0
 B  1.0  0.0

REPLY [0 votes]: Ergodic Markov chains are in places explicitly defined as being irreducible and aperiodic, for example in Randall, Dana. "Rapidly mixing Markov chains with applications in computer science and physics." Computing in Science & Engineering 8.2 (2006): 30-41.

Definition 1: A Markov chain is ergodic if it is

irreducible, that is, for all $x, y \in \Omega$, there is a
$t$ such that $P_t(x, y) > 0$, and
aperiodic, that is, for all $x, y \in \Omega$, $\gcd\{t: P_t(x, y)
> 0\} = 1$, where $\gcd$ is the greatest common
divider.


text:
\section{Numbers equal to Sum of Primes not Greater than its Prime Counting Function Value}
Tags: Prime Numbers, Prime-Counting Function

\begin{theorem}
Let $\pi \left({n}\right): \Z_{\ge 0} \to \Z_{\ge 0}$ denote the [[Definition:Prime-Counting Function|prime-counting function]]:
:$\pi \left({n}\right) =$ the count of the [[Definition:Prime Number|primes]] less than $n$
Consider the equation:
:$n = \displaystyle \sum_{p \mathop \le \pi \left({n}\right)} p$
where $p \le \pi \left({n}\right)$ denotes the [[Definition:Prime Number|primes]] not greater than $\pi \left({n}\right)$.
Then $n$ is one of:
:$5, 17, 41, 77, 100$
{{OEIS|A091864}}
\end{theorem}

\begin{proof}
We have that:
{{begin-eqn}}
{{eqn | l = \pi \left({5}\right)
      | r = 3
      | c =
}}
{{eqn | ll= \leadsto
      | l = 2 + 3
      | r = 5
      | c =
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \pi \left({17}\right)
      | r = 7
      | c =
}}
{{eqn | ll= \leadsto
      | l = 2 + 3 + 5 + 7
      | r = 17
      | c =
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \pi \left({41}\right)
      | r = 13
      | c =
}}
{{eqn | ll= \leadsto
      | l = 2 + 3 + 5 + 7 + 11 + 13
      | r = 41
      | c =
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \pi \left({77}\right)
      | r = 21
      | c =
}}
{{eqn | ll= \leadsto
      | l = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19
      | r = 77
      | c =
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \pi \left({100}\right)
      | r = 25
      | c =
}}
{{eqn | ll= \leadsto
      | l = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23
      | r = 100
      | c =
}}
{{end-eqn}}
{{ProofWanted|It remains to be shown that there are no others.}}
\end{proof}

config: wiki


TITLE: Prove all derivatives of $f(x)=\frac{1}{1+x}$ by induction
QUESTION [3 upvotes]: Problem
Prove all derivatives of:
$$ f(x)=\frac{1}{1+x} $$
by induction.
 Attempt to solve
I compute few derivatives of $f(x)$ so that i can form general expression for induction hypothesis. I compute all derivatives utilizing formula:
$$ \frac{d}{dx}x^n=nx^{n-1} $$
First 4 derivatives are:
$$ f'(x)=(-1)\cdot(1+x)^{-2}\cdot 1 = -\frac{1}{(1+x)^2} $$
$$ f''(x)=(-1)(-2)(1+x)^{-3}\cdot 1 = \frac{2}{(1+x)^3} $$
$$ f'''(x)=(-1)(-2)(-3)(1+x)^{-4}\cdot 1 = -\frac{6}{(1+x)^4} $$
$$ f''''(x)=(-1)(-2)(-3)(-4)(1+x)^{-5} \cdot 1 = \frac{24}{(1+x)^5} $$
Observe that $(-1)(-2)(-3)(-4)\dots (-n)$ can be generalized with:
$$ (-1)(-2)(-3)(-4)\dots(-n) = (-1)^n\cdot n! $$
Expression follows factorial of $n$ except every other value is positive and every other is negative. If i multiply it by $(-1)^n$ it is positive when $n \mod 2 = 0$ and negative when $n \mod 2 \neq 0$.
Rest of the expression can be generalized as:
$$ (1+x)^{-n-1} = (1+x)^{-(n+1)}=\frac{1}{(1+x)^{n+1}} $$
Combining these gives formula in analytic form:
$$ f(n)= \frac{(-1)^n \cdot n!}{(1+x)^{n+1}} $$
I can form induction hypothesis such that:
$$ \frac{d^n}{dx^n}\frac{1}{1+x} = \frac{(-1)^n\cdot n!}{(1+x)^{n+1}} $$
Induction proof
Base case
Base case when $n=0$:
$$ \frac{d^0}{dx^0}\frac{1}{1+x}=\frac{1}{1+x}=\frac{(-1)^0\cdot 0!}{(1+x)^{0+1}} $$
Induction step
$$ \frac{d^n}{dx^n}\frac{1}{1+x} =_{\text{ind.hyp}} \frac{(-1)^n\cdot n!}{(1+x)^{n+1+1}} $$
$$ \frac{d^n}{dx^n}\frac{1}{1+x} = \frac{(-1)^n\cdot n!}{(1+x)^{n+2}} $$
Now the problem is that formula i used for derivation can only be used recursively. I believe this is correct notation for $n$:th derivative but computing one is only defined recursively with formula i used:
$$ \frac{d}{dx} x^n = nx^{n-1} $$
Which is not defined for case:
$$ \frac{d^n}{dx^n}x^n = \text{
undefined} $$
The idea is to show that this recursion can be expressed in analytical form and it is valid for all $n\in \mathbb{Z}+$ by induction. Problem is i don't know how do you express this in recursive form and how do you get from recursion formula to the analytical one.

REPLY [2 votes]: Your hypothesis is
$$\frac{d^n}{dx^n}\frac1{1+x}=\frac{(-1)^nn!}{(1+x)^{n+1}}$$
We want to show that
$$\frac{d^{n+1}}{dx^{n+1}}\frac1{1+x}=\frac{(-1)^{n+1}(n+1)!}{(1+x)^{n+2}}$$
Let's verify:
\begin{align}
\frac{d^{n+1}}{dx^{n+1}}\frac1{1+x} &=\frac{d}{dx}\left(\frac{d^n}{dx^n}\frac1{1+x} \right)\\
&=\frac{d}{dx}\left(\frac{(-1)^nn!}{(1+x)^{n+1}} \right) \\
&=(-1)^n(n!) \frac{d}{dx}(1+x)^{-(n+1)} \\
&= (-1)^n(n!) (-(n+1)) (1+x)^{-(n+2)}\\
&=\frac{(-1)^{n+1}(n+1)!}{(1+x)^{n+2}}
\end{align}

REPLY [2 votes]: You inductive hypothesis is that
$$
\frac{d^nf}{dx^n}=\frac{(-1)^nn!}{(1+x)^{n+1}}.
$$
Your inductive step would then be
$$
\frac{d^{n+1}f}{dx^{n+1}}=\frac d{dx}\,\frac{d^nf}{dx^n}=\frac d{dx}\left(\frac{(-1)^nn!}{(1+x)^{n+1}}\right)
=\frac{-(n+1)(-1)^nn!}{(1+x)^{n+2}}=\frac{(-1)^{n+1}(n+1)!}{(1+x)^{n+2}},
$$
which shows that the formula holds.


text:
\section{Preliminaries}

We begin by recalling the definition of differential privacy, and the variant of concentrated differential privacy that we use in this work.
\begin{definition}[Differential Privacy (DP) \cite{DworkMNS06}]
    \label{def:dp}
    A randomized algorithm $M:\cX^n \rightarrow \cY$
    satisfies $(\eps,\delta)$-differential privacy
    ($(\eps,\delta)$-DP) if for every pair of
    neighboring datasets $X,X' \in \cX^n$
    (i.e., datasets that differ in exactly one entry),
    $$\forall Y \subseteq \cY~~~
        \pr{}{M(X) \in Y} \leq e^{\eps}\cdot
        \pr{}{M(X') \in Y} + \delta.$$
    When $\delta = 0$, we say that $M$ satisfies
    $\eps$-differential privacy or pure differential
    privacy.
\end{definition}

\begin{definition}[Concentrated Differential Privacy (zCDP)~\cite{BunS16}]
    A randomized algorithm $M: \cX^n \rightarrow \cY$
    satisfies \emph{$\rho$-zCDP} if for
    every pair of neighboring datasets $X, X' \in \cX^n$,
    $$\forall \alpha \in (1,\infty)~~~D_\alpha\left(M(X)||M(X')\right) \leq \rho\alpha,$$
    where $D_\alpha\left(M(X)||M(X')\right)$ is the
    $\alpha$-R\'enyi divergence between $M(X)$ and
    $M(X')$.\footnote{Given two probability distributions
    $P,Q$ over $\Omega$,
    $D_{\alpha}(P\|Q) = \frac{1}{\alpha - 1}
    \log\left( \sum_{x} P(x)^{\alpha} Q(x)^{1-\alpha}\right)$.}
\end{definition}

Note that zCDP and DP are on different scales, but are otherwise can be ordered from most-to-least restrictive.  Specifically, $(\eps,0)$-DP implies $\frac{\eps^2}{2}$-zCDP, which implies roughly $(\eps \sqrt{2 \log(1/\delta)}, \delta)$-DP for every $\delta > 0$~\cite{BunS16}.

\medskip Both these definitions are closed under post-processing and can be composed with graceful degradation of the privacy parameters.
\begin{lemma}[Post Processing \cite{DworkMNS06,BunS16}]\label{lem:post-processing}
    If $M:\cX^n \rightarrow \cY$ is
    $(\eps,\delta)$-DP, and $P:\cY \rightarrow \cZ$
    is any randomized function, then the algorithm
    $P \circ M$ is $(\eps,\delta)$-DP.
    Similarly if $M$ is $\rho$-zCDP then the algorithm
    $P \circ M$ is $\rho$-zCDP.
\end{lemma}

\begin{lemma}[Composition of CDP~\cite{DworkMNS06, DworkRV10, BunS16}]\label{lem:composition}
    If $M$ is an adaptive composition of differentially
    private algorithms $M_1,\dots,M_T$, then
    \begin{enumerate}
        \item if $M_1,\dots,M_T$ are
            $(\eps_1,\delta_1),\dots,(\eps_T,\delta_T)$-DP
            then $M$ is $(\sum_t \eps_t , \sum_t \delta_t)$-DP, and

        \item if $M_1,\dots,M_T$ are $\rho_1,\dots,\rho_T$-zCDP
            then $M$ is $(\sum_t \rho_t)$-zCDP.
    \end{enumerate}

\end{lemma}

We can achieve differential
privacy via noise addition proportional to
sensitivity~\cite{DworkMNS06}.

\begin{definition}[Sensitivity]
    Let $f : \cX^n \to \R^d$ be a function,
    its
    \emph{$\ell_2$-sensitivity} is defined to be
    $

    \Delta_{f,2} = \max_{X \sim X' \in \cX^n} \| f(X) - f(X') \|_2,$
    Here, $X \sim X'$ denotes that $X$ and $X'$
    are neighboring datasets (i.e., those that
    differ in exactly one entry).
\end{definition}

For functions with bounded $\ell_1$-sensitivity,
we can achieve $\eps$-DP by adding noise from
a Laplace distribution proportional to
$\ell_1$-sensitivity. For functions taking values
in $\R^d$ for large $d$ it is more useful to add
noise from a Gaussian distribution proportional
to the $\ell_2$-sensitivity, to get $(\eps,\delta)$-DP
and $\rho$-zCDP.

\begin{lemma}[Gaussian Mechanism] \label{lem:gaussiandp}
    Let $f : \cX^n \to \R^d$ be a function
    with $\ell_2$-sensitivity $\Delta_{f,2}$.

    Then the Gaussian mechanism
    $$M_{f}(X) = f(X) +
       N\left(0, \left(\frac{\Delta_{f,2}}{\sqrt{2\rho}}\right)^2 \cdot \id_{d \times d}\right)$$
    satisfies $\rho$-zCDP.
\end{lemma}

config: arxiv


TITLE: How to calculate $P ( X = 1 | X + Y \geq 0)$
QUESTION [1 upvotes]: Hi I am currently studying for my exam and are to calculate $P ( X = 1 | X + Y \geq 0)$ where Y does not depend on X and
$$
P_X(x) =
\begin{cases}
0.2 \ \ \ ,x=-1 \\
0.3 \ \ \ ,x=0 \\
0.5 \ \ \ ,x=1 \\
0 \ \ \ \text{otherwise}
\end{cases}
$$
and
$$
P_Y(y) =
\begin{cases}
0.3 \ \ \ ,y=-1 \\
0.4 \ \ \ ,y=0 \\
0.3 \ \ \ ,y=1 \\
0 \ \ \ \text{otherwise}
\end{cases}
$$
I know that by conditional probability we have
$$
P ( X = 1 | X + Y \geq 0)  = \frac{P(X=1 \cap X+Y \geq 0)}{P(X+Y \geq 0)}
$$
which I have tried to calculate by calculating all of the above options, which are a lot, but I know the answer is $50/77$ which I do not get. How do I calcucate the above? I know that I can't use the fact that X and Y are independent as they depend in this particularly case.

REPLY [1 votes]: Working from your comment that said:

$P(X=1 | X+Y \geq 0) = \frac{P(X=1) \cdot P(Y=-1) + P(X=1) \cdot P(Y=0) + P(X=1) \cdot P(Y=1)}{P(X=-1) \cdot P(Y=1) + P(X=0) \cdot P(Y=0) + P(X=0) \cdot P(Y=1) + P(X=1) \cdot P(Y=0)}$

Your numerator looks good, but your denominator is missing a few cases -- specifically, the cases $\{X = 1, Y = 1\}$ and $\{X = 1, Y = -1\}$.


TITLE: Can a beam of light be modulated close to it's frequency?
QUESTION [1 upvotes]: I'm wondering if it would be possible to modulate a signal using photon pulses - where the frequency of the signal would be close to the frequency of the light. Also would it be possible to transmit multiple of these signals in parallel and have them not interfere with each other.
Thought experiment A:
I have a laser: green(500nm, 600kGhz) which can be controlled to emit individual photons. I feed a binary signal into this laser with the same frequency as the light frequency (600kGhz). For each 1 in the signal, the laser will emit a photon and for each 0 the laser will not emit a photon. Example: For an '1 1 0 1' bit stream - the laser is emitting photon A, waiting for the photon A to travel it's wavelength, it emits photon B, waits for photons A+B to travel their wavelength, does nothing, waits for photons A+B to travel another wavelength and then emits photon C. Using this scheme, I can transmit 600,000 GigaBits of information / sec to an observer 1 mile away by having a light sensor which would either sense a photon or not sense a photon at each wavelength interval.
Would this be possible ? How about if I emit/not emit a photon at 2*wavelength period ? What's the maximum signal frequency for which this would work ?
Thought experiment B:
Assuming the previous scenario works I have 2 signals + 2 lasers as described above :green(500nm, 600kGhz) & red(700nm, ~430kGhz).
Can I pass the two photon 'beams' through an optical fiber (ignoring material properties of the fiber such as loss & lower light speed), have the mixed beams emerge 1 mile away, separate them using a prism and measure the original signal on each beam using a photon sensor ?
Basically Would I be able to transmit a 600,000 GigaBit/s signal + a 430,000 GigaBit/s signal through an optical fiber using this method ? Or would the two signals somehow interfere with each other ?
Thanks!

REPLY [1 votes]: There are (at least) a couple problems with your proposals:
In experiment A, you start with "a laser ... which can be controlled to emit individual photons." However, such a laser is, as far as I know, impossible to make, because the stimulated emission process that generates the output in the laser is a random process, emitting photons at random times. This "shot noise" problem (although it's normally looked at as a receiver problem rather than a source problem) gives a well-known result in optical communications that it requires about 9 photons per bit to transmit a signal reliably.
As for experiment B, when you modulate a signal, the signal bandwidth is spread by the bandwidth of the modulation. So if you modulate a 600 THz signal with a 600 THz signal, the bandwidth of the modulated signal is now 600 THz. The initially "green" beam is now spread across the whole spectrum (from 300 - 900 THz). This effect will prevent demultiplexing your 600 THz signal (modulated at more than 50 THz) from your 650 THz signal at the receiving end.


TITLE: Four kissing circles
QUESTION [10 upvotes]: How can one go about solving the following problem?

Inscribe a circle in an arbitrary triangle. Call it's radius $r_1$.
  Inscribe three more circles so that each one is tangent to two sides of
  the triangle and the first circle (i.e., each at a different corner). Call the
  radii $r_2, r_3, r_4$. Find a relationship between $r_1, r_2, r_3$ and
  $r_4$.

The most promising method of attack for me was to consider the isosceles triangles at each corner: the base being the tangent line to the point of intersection of the angle bisector of the triangle and the first circle. But I'm stuck.
Any suggestions much appreciated.

REPLY [4 votes]: I'm using the same notation as in the link mentioned by David Mitra. By similarity we have
$$
\frac{r}{OA}=\frac{r_a}{OA-r-r_a}=\sin\left(\frac{\alpha}{2}\right)
$$
where $\alpha=\angle A$. Then
$$
\frac{r_a}{r} = \frac{1-\sin(\alpha/2)}{1+\sin(\alpha/2)}
= \frac{1-\cos((\beta+\gamma)/2)}{1+\cos((\beta+\gamma)/2)}
= \tan\left(\frac{\beta+\gamma}{4}\right)^2
$$
where we used that $\alpha+\beta+\gamma=\pi$. Similarly
$$
\frac{r_b}{r} = \tan\left(\frac{\alpha+\gamma}{4}\right)^2
\qquad\qquad
\frac{r_c}{r} = \tan\left(\frac{\alpha+\beta}{4}\right)^2
$$
Therefore, $\sqrt{r_ar_b}+\sqrt{r_ar_c}+\sqrt{r_br_c}$ can be written as
$$
\begin{split}
\frac{\sqrt{r_ar_b}+\sqrt{r_ar_c}+\sqrt{r_br_c}}{r}
= \frac{\sin(\rho)\sin(\sigma)\cos(\tau)+\sin(\rho)\cos(\sigma)\sin(\tau)
+\cos(\rho)\sin(\sigma)\sin(\tau)}{\cos(\rho)\cos(\sigma)\cos(\tau)}
\end{split}
$$
where $\rho=(\beta+\gamma)/4$, $\sigma=(\alpha+\gamma)/4$, and $\tau=(\alpha+\beta)/4$. Note that $\rho+\sigma+\gamma=\pi/2$.
Consider $x$, $y$, $z$ such that $x+y+z=\pi/2$. Then
$$
\begin{split}
\sin(x)\sin(y)\cos(z) &= \frac{1}{2}(\cos(x-y)-\cos(x+y))\cos(z)
\\&=
\frac{1}{4}(\cos(x-y+z)+\cos(x-y-z) -\cos(x+y+z)-\cos(x+y-z))
\\&= \frac{1}{4}( \cos\left(\frac{\pi}{2}-2y\right) + \cos\left(-\frac{\pi}{2}+2x\right) - \cos\left(\frac{\pi}{2}\right)-\cos\left(\frac{\pi}{2}-2z\right)
\\&=\frac{1}{4}\left( \sin(2y)+\sin(2x)-\sin(2z)\right)
\end{split}
$$
And similarly
$$
\begin{split}
\cos(x)\cos(y)\cos(z) &= \frac{1}{2}(\cos(x-y)+\cos(x+y))\cos(z)
\\&=
\frac{1}{4}(\cos(x-y+z)+\cos(x-y-z) +\cos(x+y+z)+\cos(x+y-z))
\\&=\frac{1}{4}\left( \sin(2y)+\sin(2x)+\sin(2z)\right)
\end{split}
$$
This means that $(\sqrt{r_ar_b}+\sqrt{r_ar_c}+\sqrt{r_br_c})/r$ is equal to
$$
\frac{\sqrt{r_ar_b}+\sqrt{r_ar_c}+\sqrt{r_br_c}}{r} = \frac{\sin(2\rho)+\sin(2\sigma)+\sin(2\tau)}{\sin(2\rho)+\sin(2\sigma)+\sin(2\tau)}=1
$$


TITLE: If $m$ and $a$ are co-prime positive integers then show that $ax \equiv b \pmod m$ has a solution, and any two solutions differ by a multiple of m.
QUESTION [2 upvotes]: If $m$ and $a$ are co-prime positive integers then show that $ax \equiv b \pmod m$ has a solution, and any two solutions differ by a multiple of m.

I begun by using the definition of co-prime integers, s.t $au + mv = 1$. But I have no idea what to do next.

REPLY [0 votes]: Another  perhaps more primitive attempt:
Consider the product $ax_n$ for $x_n=0,1…m-1$.  If b is between and including 0 and m-1 then there must be one $x_k$ so that $ax_k=b$ (mod m). Otherwise there must be (at least) one other number c different from b, with two different number $x_k$ and $x_l$ such that $ax_k=ax_l = c $ (mod m), that is $ax_k-ax_l=a(x_k-x_l)=0=m $ (mod m) but a and m are coprime which a contradiction, so the unique solution must exist that is $x_k=x_l$ (mod m) and $x_k=x_l +nm$.


TITLE: If $f_n,g_n \in L^1$ and $f_n,g_n \to 0$, show $\int_A (2f_n g_n)/(1+f_n^2+g_n^2)\to 0$, when $A$ has finite measure
QUESTION [1 upvotes]: Let $(f_n)$ and $(g_n)$ be sequences of nonnegative function in $L^1(\mathbb R)$, for which
$$
f_n \to 0, \\
g_n \to 0,
$$
almost everywhere.
Show
$$
\int_A \frac{2f_n g_n}{1+f_n^2+g_n^2} \to 0,
$$
when $A \subset \mathbb R$ is a set of finite measure.
Define
$$
h_n = \frac{2f_n g_n}{1+f_n^2+g_n^2}.
$$
I know
$$
h_n \le 2f_n g_n,
$$
but I can't use a convergence theorem, because the product of integrable function may fail to be integrable.
I considered uniform integrability
$$
\text{Since }
f_n \in L^1: \forall \epsilon, \exists \delta : m(B) < \delta \to \int_B f_n <\epsilon,
$$
where $m(\cdot)$ is Lebesgue measure.
To use that, I write $A=\cup_m B_{n,m}$ where the index $n$ is associated to $f_n$.
I can't go further.

REPLY [1 votes]: The only suggestion you might still need is: $2f_ng_n \le f_n^2 + g_n^2$. This is what gives the bound ($\frac{a}{1+a} \le 1$).


TITLE: Question 10 chapter 11 of Principles of Mathematical Analysis of Rudin, W.
QUESTION [1 upvotes]: I hope you can help me with the question 10 of chapter 11 of the book Principles of Mathematical Analysis of Walter Rudin. My question is:
In this exercise, he asked to prove that if $\mu(X)<+\infty$ and $f\in L^2(\mu)$ on X, then $f\in L^1(\mu)$ on X. I thought strange to prove this proposition without the hypotheses that $f$ is mensurable. Do you think is possible to prove from $\mu(X)<+\infty$ and $f\in L^2(\mu)$ that $f$ is mensurable? Or the hypotheses that $f$ is mensurable is also necessary?
Thanks in advance!

REPLY [2 votes]: $L^2(\mu)$ contains only measurable functions, we have
$$ L^2(\mu) = \left\{f \colon X \to \mathbf R : f \text{ is measurable}, \int_X |f|^2\, d\mu < \infty \right\} $$


text:
\section{Cover-time-based analysis of asynchronous Q-learning}
\label{sec:analysis-cover-time}

In this section, we sketch the proof of Theorem~\ref{thm:main-asyn-Q-learning-cover-time}. Before continuing, we recall the definition of $\tcovertime$ in \eqref{eq:defn-cover-time}, and further introduce a quantity

\begin{equation}
	\tcoverall := \tcovertime \log \frac{T}{\delta}.
	\label{defn:tcover-all}
\end{equation}

There are two useful facts regarding $\tcoverall$ that play an important role in the analysis.

\begin{lemma}
\label{lem:connection-cover-time}
	Define the event $$\mathcal{K}_{l}:=\Big\{ \exists(s,a)\in\mathcal{S\times\mathcal{A}}\text{ s.t.~it is not visited within iterations }\big(l\tcoverall,(l+1)\tcoverall\big]\, \Big\},$$ and set $L:=\lfloor\frac{T}{\tcoverall}\rfloor$. Then one has $\mathbb{P}\left\{ \bigcup\nolimits_{l=0}^{L}\mathcal{K}_{l}\right\}   \leq\delta.$

\end{lemma}

\begin{proof} See Section~\ref{sec:proof-lemma-connection-cover-time}. \end{proof}

 In other words, Lemma~\ref{lem:connection-cover-time} tells us that with high probability, all state-action pairs are visited at least once in every time frame $(l\tcoverall,(l+1)\tcoverall]$ with $0\leq l\leq \lfloor {T}/{\tcoverall} \rfloor$. The next result is an immediate consequence of Lemma~\ref{lem:connection-cover-time}; the proof can be found in Section~\ref{sec:proof-lemma-control-beta3}.

\begin{lemma}
\label{lemma:control-beta3-cover-time}
	For any $\delta>0$, recall the definition of $\tcoverall$ in \eqref{defn:tcover-all}.
	Suppose that $T>\tcoverall$ and $0<\eta<1$. Then with probability exceeding $1-\delta$ one has

\begin{align}
\label{eqn:beta3-cover-time}

	\Bigg | \prod_{j=1}^{t}\big(\bm{I}-\bm{\Lambda}_{j}\big)\bm{\Delta}_{0} \Bigg|

	\leq  (1-\eta)^{\frac{t}{2\tcoverall}} \|\bm{\Delta}_0 \|_{\infty} \bm{1}
\end{align}

	uniformly over all $t$ obeying $T\geq  t \geq  \tcoverall$ and all vector $\bm{\Delta}_{0} \in \mathbb{R}^{|\cS||\cA|}$.

\end{lemma}

With the above two lemmas in mind, we are now positioned to prove Theorem~\ref{thm:main-asyn-Q-learning-cover-time}.
Repeating the analysis of \eqref{eqn:recursion} (except that Lemma~\ref{lemma:control-beta3} is replaced by Lemma~\ref{lemma:control-beta3-cover-time}) yields

\begin{align*}
\hspace{-0.02in}	|\bDel_t| \leq
	\begin{cases}
	\gamma \sum_{i=1}^t \linf{\bDel_{i-1}} \prod_{j=i+1}^{t} (\bm{I}-\bLam_j)\bLam_i \one
		+ \tau_1 \|\bm{V}^{\star}\|_{\infty} \one + \linf{\bDel_0} \one,  & t< \tcoverall \\
		\gamma \sum_{i=1}^t \linf{\bDel_{i-1}} \prod_{j=i+1}^{t} (\bm{I}-\bLam_j)\bLam_i \one
		+ \tau_1 \|\bm{V}^{\star}\|_{\infty} \one + (1-\eta)^{ \frac{t}{2\tcoverall} } \linf{\bDel_0} \one,   &   \tcoverall \leq t \leq T
	\end{cases}
\end{align*}

with probability at least $1-2\delta$. This observation resembles \eqref{eqn:recursion}, except that $\tcover$ (resp.~$\mumin$) is replaced by $\tcoverall$ (resp.~$\frac{1}{\tcoverall}$). As a consequence, we can immediately use the recursive analysis carried out in Section~\ref{sec:recursion} to establish a convergence guarantee based on the cover time. More specifically, define

\begin{align}
	\widetilde{\rho} &:= (1-\gamma)  \Big( 1 - (1-\eta)^{ \frac{\tcoverall}{2\tcoverall}} \Big) = (1-\gamma)  \Big( 1 - (1-\eta)^{\frac{1}{2} } \Big) .
	\label{eq:defn-rho-tilde}
\end{align}

Replacing $\rho$ by $\widetilde{\rho}$ in Theorem~\ref{thm:intermediate} reveals that with probability at least $1-6\delta$,

\begin{align}
\label{eqn:beethoven-covertime}
	\| \bm{Q}_t - \bm{Q}^{\star} \|_{\infty} \leq (1- \widetilde{\rho} )^{ k } \frac{\| \bm{Q}_0 - \bm{Q}^{\star} \|_{\infty}}{1-\gamma}
	+ \frac{c \gamma}{1-\gamma} \|\bm{V}^{\star}\|_{\infty} \sqrt{\eta\log\Big(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\Big)}
	 +\varepsilon

\end{align}

holds for all $t\leq T$, where $k \defn \max \big\{0, ~\big\lfloor \frac{t - \tth}{\tcoverall} \big\rfloor \big\}$ and we abuse notation to define

\begin{align*}
	\tth := 2\tcoverall\log\frac{1}{(1-\gamma)^{2}\varepsilon}.
\end{align*}

Repeating the proof of the inequality \eqref{eqn:mozart} yields

\begin{align*}
	(1- \widetilde{\rho} )^{k} \frac{\|\bDel_0\|_{\infty}}{1-\gamma} \leq \varepsilon,
\end{align*}

whenever $t \geq \tth + \tcoverall  + \frac{2\tcoverall}{(1-\gamma)\eta } \log\big(\frac{1}{\varepsilon(1-\gamma)^2}\big)$,
with the proviso that $\eta < 1/2$. In addition, setting $\eta = \frac{(1-\gamma)^{4}}{c^{2}\gamma^{2}\varepsilon^{2}\log\big(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big)}$ guarantees  that

\begin{equation*}
	\frac{c \gamma}{1-\gamma} \|\bm{V}^{\star}\|_{\infty} \sqrt{\eta\log\Big(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\Big)}
	\leq \frac{c \gamma}{(1-\gamma)^2} \sqrt{\eta\log\Big(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\Big)}
	\leq \varepsilon.
\end{equation*}

In conclusion, we have 	$\| \bm{Q}_t - \bm{Q}^{\star} \|_{\infty}\leq 3\varepsilon$ as long as

\begin{equation*}
	t \geq \frac{c'\tcoverall}{(1-\gamma)^5\varepsilon^2 } \log\Big(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\Big) \log \Big(\frac{1}{\varepsilon(1-\gamma)^2}\Big),
\end{equation*}

for some sufficiently large constant $c'>0$. This together with the definition \eqref{defn:tcover-all} completes the proof.


TITLE: How do we define capillary number in 2D (two dimensions)
QUESTION [0 upvotes]: In 3D the capillary number $Ca$ is defined as:
$$Ca=\frac{\nu \rho U}{\gamma}$$
where $\nu$ is the kinematic viscosity ($m^2/s$), $U$ is the velocity ($m/s$)and $\gamma$ is the interfacial tension ($N/m$) and $\rho$ is the density in $kg/m^3$ .
However in 2D I will have $\rho$ in units of $kg/m^2$ (2D simulation), so how to find capillary number?

REPLY [3 votes]: Rather than leave these as comments, I guess I should answer it since this has come up before.
A 2D simulation does not mean there is no third dimension. Rather, it means we are saying there is no variation in the third dimension such that $\frac{\partial}{\partial z} = 0$. But that depth direction still exists and we typically just call it a "unit depth" or $\Delta z = 1$.
For some people, sometimes, they like to define things differently and actually adjust their units. I've come across this in papers looking at mass-spring systems where in 3D, $k = E l$ where $E$ is the Youngs Modulus and $l$ is the spring length. And in 2D, they just say that $k = E$. I don't like this approach, it's somewhat confusing, and can cause problems in a code written to handle 1, 2 and 3D without rewriting everything.
However, if you want to insist that your units of density are $kg/m^2$ you can. Just remember that your kinematic viscosity is defined as $\nu = \mu/\rho$. Since your dimensions on $\rho$ have changed, so have your dimensions on $\nu$ which is now going to be $m/s$ instead of $m^2/s$. This means your definition of $Ca$ is still the same.
But this just highlights why it's not a great idea to start dropping a length dimension from everything. It just gets really confusing and confers no benefit.


TITLE: Measure of card shuffling randomness
QUESTION [3 upvotes]: I've read online that you need to shuffle a deck of cards at least 7 times (depending on the game being played) for the deck to be 'random enough', i.e. that it is nearly impossible to predict the suit or face of the next card above chance levels.
How can this be evaluated in a general sense? How can we start from a deck of cards and calculate its randomness value? So not working with specific techniques like seeing if the faces are in increasing order or something like that (because then we would need to describe every card counting technique which exists, which is impossible).

REPLY [4 votes]: There is no "measure" like the one you are looking for. The proof establishes a measure of the randomness of a probability function on all permutations, not a measure of the randomness of an individual permutation/configuration of the deck. No individual deck configuration is "more random" than another in any sense that is meaningful for probability and statistics.
Rather, we are measuring how far a probability function is away from an "ideal" probability function.
Given a finite set $X$ and a probability function $p:X\to\mathbb R^{\geq 0}$, we can define the distance from that probability function to the uniform probability function as a vector distnce. If $X=\{x_1,\dots,x_N\}$, then treat $p$ as the vector $(p(x_1),p(x_2),\dots,p(x_N))$ and compute the Euclidean distance of that vector to $(1/N,1/N,\dots,1/N)$, the uniform probability vector.
You might think that measure is arbitrary, but it is actually closely related to the "standard deviation." It is a remarkably useful measure of how far from "uniform" a probability function is.
(I'm not sure this distance is the distance used in the paper, I forget, but it is a useful example of the type of distance used to measure "How close to uniform randomness is this random variable?")
Now, in this case, you have $N=52!$, because $X$ is the space of all possible permutations of the cards. $52!$ is a huge number, and you are not going to be able to write out the vectors.
But that doesn't mean you can't compute estimates for this distance.
The model for $X$ in shuffling is the group of permutations $\Sigma_{52}$. And a single riffle shuffle has a probability function $r:\Sigma_{52}\to\mathbb R^{\geq 0}$ which is mostly zero - that is, most permutations cannot result from a single riffle shuffle. But the fact that $X=\Sigma_{52}$ is a group lets us do clever math to deal with repeated riffle shuffles. And we can get good estimates for our measurement.
The number of riffle shuffle outputs is roughly $2^{52}=4.5\times 10^{15}$. So the number of different outputs from $4$ riffle shuffles is at most $2^{52\cdot 4}=4.1\times 10^{62}<52!\approx 8.1\times 10^{67}$. Indeed, only one in ever rougly $20,000$ permutations can even be output after four shuffles. So if you want a chance for every permutation after shuffling, you'd have to shuffle at least $5$ times. But the riffle shuffle isn't uniform - each of its roughly $2^{52}$ outputs are not equally likely. You are likely, for example, to initially cut closer to the middle of the deck than near an end.
What the proof shows is that you get significantly closer to the ideal with each shuffle up to $7$, and then the progress slows. Additional shuffles do improve the measure, but not by much.


TITLE: Mathematical description of the curve of a straight line in optics
QUESTION [0 upvotes]: If you look at a square object from far away, all the edges look perfectly flat, but if the square is something like 2 feet by 2 feet, for example, and you get close enough to it, you can see that the edges all curve due to perspective. If you align your face with the center of it, the top edge curves downward on the left and right side, and the bottom edge curves upward on the left and right side. The closest term I can find to this is 'barrel distortion', although I'm not 100% sure that is exactly the concept I'm referring to.
Is there any sort of function or equation which describes the shape of this curve? I'm sure there must be, but my googling hasn't brought me anything.
I'm not sure what the appropriate tags for this question are, apologies. I asked this on the Math stackexchange but I didn't get any answers.

REPLY [0 votes]: It's the field of distortion wave aberration (geometrical point-spread function), optical imaging
Reference:
Lecture notes


TITLE: Slope in algebra I
QUESTION [0 upvotes]: What is a good project for teaching y=mx + b and having students discover slopes of lines in classroom or on the classroom buildings?

REPLY [0 votes]: I used to begin by getting students on a large piece of A3 squared paper (with axes drawn) to plot $(x, y)$ coordinates for those numbers that have a difference of $4$. This would then teach them about the line $y=x+4$ whether they choose both positive or negative numbers is interesting; in nearly all cases most groups chose coords that could be place in the top right quadrant.
Anyway; once this line has been plotted; repeat with (say) differences of $5, -3$ and $0$.
After they know about the lines $y=x+c$ for some $c$ I went onto more creative worded requests like "Plot $20$ coordinates $(x, y)$ such that the $y$-coordinate is twice as much as the $x$". Obviously this teaches about $y=2x$. Repeat similar requests to the above, scaffolding the relationship in their minds, then after a while, they begin to see the role of the coefficient of $x$ and the constant term.
The slope of the line becomes obvious when you begin to choose those different multiples, even choosing fraction say $\frac{1}{2}$ is an interesting conversation. After a little thought though, the relationship becomes obvious in their minds, or that was my experience.
The trick then I found, was to be able to give them the task of "sketch the line $y=2x+1$ for $x \in (-6, 6)$". This took a few lessons; I had a group of 14 year olds who were working at C/D grade GCSE. It worked after a few lessons and they were able to line sketch quite easily by the end of it.
The tough bit was moving onto coordinates of intersecting lines....


TITLE: Why do we assume Kinetic friction to be constant?
QUESTION [3 upvotes]: My Physics teacher told me that friction exists because of bonds made between the surfaces of two objects. As we try to move an object, we break the bonds and this causes release of energy which is heat. He told us that Kinetic friction is smaller than static friction because when we move an object, it doesn't get much time to make strong bonds!
My question is, if such things happen in real world, then as we increase the speed of the object the surfaces would get lesser and lesser time to make bonds and friction would decrease . But this doesn't happen. Why?

REPLY [0 votes]: There are two reasons for friction:

Interlocking
Bonds or cold welding

When an object is at rest it makes bonds with the surface and the irregularities on the surface of both of the objects get interlocked due to which the friction at that time is called static friction and has the highest friction force. But when you apply force and make the object move then the bonds between them break down and the friction now is called kinetic friction which is due to only interlocking between the surface of two objects. The kinetic friction formula is normal × friction coefficient (which is constant) so if you increase the force you don't change the normal force due to which the friction remains constant.


TITLE: Does $\lim_{x\rightarrow 0}\frac{\ln(x)}{\cot(x)}$ exist or not?
QUESTION [4 upvotes]: I stumbled on the following limit in a calculus textbook today:
\begin{equation*}
\lim_{x\rightarrow 0}\frac{\ln(x)}{\cot(x)}
\end{equation*}
According to the book's solutions and Mathematica, this limit exists and is equal to 0. I can see why $0$ is obtained using l'Hôpital's rule twice:
\begin{equation*}
...=\lim_{x\rightarrow0}\frac{\left(\frac{1}{x}\right)}{-\csc^2(x)}=-\lim_{x\rightarrow0}\frac{\sin^2(x)}{x}=-\lim_{x\rightarrow0}\frac{2\sin(x)\cos(x)}{1}=2\sin(0)\cos(0)=0
\end{equation*}
If I recall correctly, l'Hôpital's rule is applicable when we have:
\begin{equation*}
\lim_{x\rightarrow a}\frac{f(x)}{g(x)}
\end{equation*}
even if $f$ and $g$ are not derivable at precisely $a$, so there should be no issue in using it on the above limit.
However, I can't reconcile the fact that $\ln(x)$ is defined over $]0,+\infty[$ (and usually, only $\lim_{x\rightarrow0^+}\ln(x)$ exists) with the fact that the above limit exists (both as $x\rightarrow0^+$ and as $x\rightarrow0^{-}$).
It seems to me that only
\begin{equation*}
\lim_{x\rightarrow 0^+}\frac{\ln(x)}{\cot(x)}
\end{equation*}
should exist and thus the "bilateral limit" (with $x\rightarrow 0$) does not exist since the limit with $x\rightarrow0^-$ doesn't.
Is there something I am missing?

REPLY [0 votes]: Sometimes some tacit assumptions are omitted by authors, and sometimes there are oversights and typos. It should have said $\lim_{x\to 0^+}\;.$
We have $\lim_{x\to 0^+}(x\ln x)=0$  and $\lim_{x\to 0^+}\frac {\tan x}{x}=1.$
For $\pi /2>x>0$   we have $\cot x \ne 0$ and $$\frac {\ln x}{\cot x}=(\ln x)(\tan x)=(x\ln x)\cdot\frac {\tan x}{x}.$$
So $\lim_{x\to 0^+} \frac {\ln x}{\cot x}=0\cdot 1=0.$


TITLE: Relationship between stress-energy tensor for a point particle and its Lagrangian
QUESTION [4 upvotes]: The Lagrangian for a (relativistic) point particle with rest mass $m$ and velocity $v$ is:
$$L=-\frac{m}{\gamma (v)}$$
(using $c=1$). Over on Wikipedia we can find the Stress-energy tensor for said particle; if the four-velocity is $u^\mu=(\gamma (v),\gamma (v)v)$ then the stress-energy is:
$$T^{\mu\nu}=\frac{mu^\mu u^\nu}{\gamma (v)} \delta^3({\bf x}-{\bf x}_p(t)).$$
Interestingly, the negative of the trace of the stress-energy in this case is:
$$-\eta_{\mu\nu}T^{\mu\nu}=\frac{m}{\gamma (v)} \delta^3({\bf x}-{\bf x}_p(t))$$
Which, when integrated over all of space, gives the appropriate Lagrangian for the particle, meaning it serves as a Lagrangian density. Is this just some kind of coincidence for point particles, or are there other cases where the Lagrangian density is equal to the negative trace of the stress-energy tensor?

REPLY [1 votes]: The delta function is a density, so the correct relation should be with a tensor density, namely: $$\mathfrak{T}^{\mu  \nu} \equiv T^{\mu  \nu} \sqrt{|g|} = m  \frac{\mathrm{d}x^\mu}{\mathrm{d}s} \frac{\mathrm{d} x^ \nu}{\mathrm{d} s} \delta(x - x(s))$$ for a point-like particle of mass $m$ on worldline $x(s)$ parametrized by its arc-length $s$.
The Einstein field equations imply a continuity equation for the stress tensor which, when stated in terms of the tensor density, is $\partial \mathfrak{T}^{\mu \nu}/\partial x^ \nu +  \Gamma^\mu_{ \nu \rho} \mathfrak{T}^{ \nu  \rho} = 0$.
Upon substitution of the expression for the tensor density, you get:
\begin{align}
\frac{\partial \mathfrak{T}^{\mu \nu}}{\partial x^ \nu} &= m \frac{\mathrm{d} x^\mu}{\mathrm{d} s} \frac{\mathrm{d} x^ \nu}{\mathrm{d} s} \frac{\partial}{\partial x^ \nu}(\delta(x - x(s)))\\
&= -m \frac{\mathrm{d} x^\mu}{\mathrm{d}s} \frac{\mathrm{d}}{\mathrm{d} s} (\delta(x - x(s)))\\& = \frac{\mathrm{d}}{\mathrm{d} s} \left(m \frac{\mathrm{d}x^\mu}{\mathrm{d} s}\right) \delta(x - x(s))\\
 \Gamma^\mu_{ \nu \rho} \mathfrak{T}^{ \nu \rho} &=  \Gamma^\mu_{ \nu \rho} m \frac{\mathrm{d} x^ \nu}{\mathrm{d}s} \frac{\mathrm{d} x^ \rho}{\mathrm{d}s} \delta(x - x(s))
\end{align}
or, collecting terms:
$$\left(\frac{\mathrm{d}}{\mathrm{d}s} \left(m \frac{\mathrm{d}x^\mu}{\mathrm{d}s}\right) +  \Gamma^\mu_{ \nu \rho} m \frac{\mathrm{d}x^ \nu}{\mathrm{d}s} \frac{\mathrm{d}x^\rho}{\mathrm{d}s}\right) \delta(x - x(s)) = 0.$$
Taking an integral with respect to x removes the delta function which, assuming the mass (m) is non-zero and constant, results in the geodesic equation:
$$\frac{\mathrm{d}^2 x^\mu}{\mathrm{d}s^2} +  \Gamma^\mu_{ \nu \rho} \frac{\mathrm{d}x^\nu}{\mathrm{d}s} \frac{\mathrm{d}x^\rho}{\mathrm{d}s} = 0.$$