TITLE: Dimension of intersection of affine subspaces
QUESTION [1 upvotes]: As an assignment we are to calculate the dimension of the intersection of two affine subspaces $A$,$B$ in $\mathbb{R}^6$ each defined by a system of linear equations of at most 6 variables and a constant.
How does one calculate that?
I tried to stack together the equations and simplify, then parametrize the solution as a $\vec v$ + {set of parametrized vectors}.
Then the dimensionality of their intersection should be the size of the set. But when I carry out the calculations I get a contradiction.
Is my procedure valid?
How else could I arrive at the solution? What are other methods of finding the intersection?
*Edit:
Does contradiction indicate that the intersection is empty?
*Edit2: I add code I used to check if I made any numerical errors.
After running the code, result is EmptySet()
The first 3 rows of $M$ is the augumented form of $A$.
The bottom 3 rows of $M$ is the augumented form of $B$
import sympy

M = Matrix([
[3, 4,  6,  0,  0,  0, 3],
[4, 0,  0,  1,  1,  0, 2],
[0, 1, -4,  0,  0,  0, 8],
[0, 1,  1, -1, -1,  2, 0],
[0, 0, -1,  1,  1, -2, 0],
[0, 1, -7,  0,  0,  0, 0]])

x1,x2,x3,x4,x5,x6 = sympy.symbols('x1,x2,x3,x4,x5,x6')
result = sympy.linsolve(M,(x1,x2,x3,x4,x5,x6))

REPLY [1 votes]: Yes: the fact that you got the output EmptySet() indicates that the intersection of the two affine spaces is empty.
Using W|A confirms this result.


TITLE: Relation between the inverse of finitely generated ideals and the inverse of their powers.
QUESTION [1 upvotes]: Let $D$ be an integral domain, $K$ its field of fractions, and $J_1,...,J_n$ are ideals of $D$ such that $(\sum_{i=1}^{n} J_i)^{-1}=D$. How can we prove that this implies $(\sum_{i=1}^{n} J_i^m)^{-1}=D$ for all $m\ge1$ ?

I know that the converse is true since $\sum_{i=1}^{n}{J_i}^{m}\subseteq\sum_{i=1}^{n}J_i$. I tried to prove it by induction on $m$ but it did not work.
This question is part of the proof of the lemma 4.2 in the the paper Some remarks on star-operations by Hedstorm and Houston.

REPLY [0 votes]: Note that $x\in (D:_K \sum_{i=1}^{n} J_i)$ iff $xJ_i\subseteq D$ for all $i=1,\dots,n$.
Let me prove the case $n=2$. I'll show that

$(J_1+J_2)^{-1}=D$ implies $(J_1^{m_1}+J_2^{m_2})^{-1}=D$ for any $m_1,m_2\ge 1$.

First set $m_1=1$. Then pick an $x\in(J_1+J_2^{m_2})^{-1}$, so $xJ_1\subset D$ and $xJ_2^{m_2}\subset D$. Since $(xJ_2)J_2^{m_2-1}\subset D$, and $(xJ_2)J_1\subset D$, by induction we get $xJ_2\subset D$, hence $x\in(J_1+J_2)^{-1}=D$. Now use induction on $m_1$.


TITLE: Conditions for Newton's method to converge.
QUESTION [1 upvotes]: I would like to know some, easy to use,  conditions for Newton's method to converge. I know a condition that states that the method will converge for a function $f(x)$  If for an interval $[a, b]$ it is true that $$f(a)<0<f(b)$$ $$f'(x) >0$$ and $$f''(x) >0$$, but I would like to know how can I find $[a, b]$, should I do this by trial and error?  And how can I generally use this method?

REPLY [1 votes]: In many cases we can prove that $f'(x)>0$ and $f''(x)\geq  0$ for all $x$ without knowing anything about $a$ and $b.$ Then we may be able to prove there exists $a, b$ with $f(a)<0<f(b)$. In this case you can begin the iteration anywhere.
In practice a less restrictive but sufficient set of conditions is
(i).  There exists $c$ with $f(c)=0.$
(ii).There exist $a>c$ (the same $c$ as in (i)) such that $f(a)>0$ and such that $f'(x)>0$ for $c<x\leq a.$
(iii). $f'$ is increasing  on $(c,a).$ (That is, $c<x<y<a\implies f'(x)\leq f'(y)$ .)
For a non-linear function $f,$ condition (i), (ii) and (iii) imply that $f(x)>0$ for $c<x\leq a$ and that the sequence $a_{n+1}=a_n-f(a_n)/f'(a_n),$ with $a_1=a,$ is strictly decreasing and remains in $(c,a]$ so it has a limit $d,$ and that $f(d)=0$ (so $d=c$).
Example. Let $f(x)=x^4-10.$ We know there exists $c\in (0,2)$ with $f(c)=0$ because $f(0)<0<f(2)$. We have $f'(x)=4x^3 >0$ for $x>0$,  hence $f'(x)>0$ for $x>c.$  We have $f''(x)=12x^2\geq 0$ , hence  $f'$ is increasing for $x>c.$ So we can begin an iteration with $a=a_1=2.$


TITLE: Projective representations of loop groups
QUESTION [3 upvotes]: If $G$ is a Lie group and we take its loop group $LG$ why do we deal with projective representations of $LG$ and central extensions thereof? Where does the extra complexity come in to require us to consider this extra, very complicated, step?

REPLY [2 votes]: Well, we are usually concerned about these exotic objects at the algebraic level. They pop up when we consider spinor representations of the orthogonal group. Lets write $\gamma_{\alpha}$ for the generators of the Clifford algebra which are represented by $\Gamma_{\alpha}$. They satisfy
$$\Gamma_{\alpha}\Gamma_{\beta}+\Gamma_{\beta}\Gamma_{\alpha}=2\eta_{\alpha\beta}$$
where $\eta_{\alpha\beta}$ is nondegenerate. (If it's degenerate, we have a Grassmann algebra and not a Clifford algebra, but it's not terrible.)
So we have commutators of the generators of the Clifford algebra. We will leave it as an exercise for the reader to determine
$$[\Gamma_{\alpha},\Gamma_{\beta}]=\text{something quadratic}$$
and
$$[\Gamma_{\alpha},\Gamma_{\mu}\Gamma_{\nu}]=2\eta_{\alpha\mu}\Gamma_{\nu}-2\eta_{\alpha\nu}\Gamma_{\mu}.$$
Now we expect commutators of quadratic terms to look like
$$[\Gamma_{\alpha}\Gamma_{\beta},\Gamma_{\mu}\Gamma_{\nu}]\sim a\Gamma_{\sigma}\Gamma_{\tau}+b\cdot\textbf{1}$$
and wouldn't it be lovely if we could make this an equality and ditch the constant multiple of the identity operator $b\textbf{1}$? This would make the representation of quadratic guys a closed algebra!
We find if we write an arbitrary element of these generated algebra as $a\cdot\textbf{1}+b^{\mu\nu}\Gamma_{\mu}\Gamma_{\nu}$ (where we use Einstein summation convention) we have an algebra, provided one condition on the matrix $b^{\mu\nu}$ namely we need
$$ b^{\mu\nu}=-b^{\nu\mu}.$$
This says we have a "representation" of the orthogonal Lie algebra. Is it a representation? Yes and no. No, it's technically not a "vanilla representation"; but with all this extra structure, we have a central extension of the orthogonal lie algebra.
Wouldn't it be lovely, after all this work, if we could do the same thing to other Lie algebras? That's how we get started with losing ourselves in the jungle of loop groups, its central extensions, etc.


TITLE: Velocity addition for tachyons
QUESTION [5 upvotes]: How does the velocity of a tachyon transform under a Lorentz boost? Suppose we only consider motion along the $x$ direction for simplicity. If the velocity of the tachyon is $u$ in the lab frame, what is the velocity $u'$ of the tachyon in a frame moving with velocity $v$ (slower than $c$) relative to the lab frame? Can we still use the formula
$$
u' = \frac{u-v}{1-\frac{uv}{c^2}}
$$

REPLY [6 votes]: The short answer is that it is valid, but that misses a lot of subtleties.
Using three-vectors for velocity in special relativity is fairly unnatural even for ordinary speeds, and it's worse for tachyons, since their three-velocity can be "infinite" and, in a certain sense, "time reversed" (see below), and those situations can't be described properly with three-vectors.
It's better to use a four-vector to represent speed. The four-velocity at a point is just a tangent vector to the worldline at that point. A three-velocity $(u_x,u_y,u_z)$ is equivalent to an unnormalized four-velocity of $(1,u_x,u_y,u_z)$, or any positive scalar multiple of that.
All four-vectors transform in the same way. Under a Lorentz boost in the $x$ direction by $v, |v|<1$ (using a three-velocity $v$ in anticipation of recovering the formula quoted in the question), that four-velocity becomes $(γ(1 - vu_x), γ(u_x - v1), u_y, u_z)$. You can renormalize that to make the time component equal to $1$ again, getting
$$\left( 1,\; \frac{u_x-v}{1-vu_x},\; \frac{u_y}{γ(1-vu_x)},\; \frac{u_z}{γ(1-vu_x)} \right)$$
and if you drop the $1$, and add explicit factors of $c$, you get a generalization of the formula from the question (which is the special case where $u_y=u_z=0$).
Nothing in that derivation depends on the speed $u$ being light speed or less as such. However, when you renormalize the boosted four-vector, you have to divide by the time component, and when the speed is tachyonic (and only when it's tachyonic), that time component may be zero. In that case, you can represent the speed by a "formally infinite" three-velocity that has an infinite magnitude and a direction like that of any nonzero vector. However, this is mathematically suspect, and really the only reason it makes sense is because it's equivalent to the four-vector form. There is also no natural reason for the velocity to be treated as "infinite" in the first place. Whether a velocity is "infinite" in this sense is frame-dependent and hence not really a property of the velocity.
The time component can also be negative, and because of that, when you divide by it, you lose sign information. (This is when "the tachyon appears to travel backwards" as you observed in a comment.) Whether the sign information matters depends on the nature of the hypothesized tachyons. If tachyons have an arrow of time, and the four-velocity points in the direction of increasing proper time (as one normally imagines it does for sublight speeds), then the direction of the arrow of time is lost in the conversion. However, if tachyons have an arrow of time, then you can use them to send signals into your own past (using a "tachyonic antitelephone"), so perhaps they can't have one and the loss of sign information doesn't matter.
Ultimately, though, the three-velocity is just a poor way of thinking about the velocity of tachyons, even though it can be adapted to that purpose. It's better to stick with the four-velocity for both subluminal and superluminal speeds.


TITLE: Find $\angle BDC$
QUESTION [4 upvotes]: Quadrilateral $ABCD$ , $\angle ABD = 17^{\circ}, \angle DBC = 34^{\circ}, \angle ACB = 43^{\circ}, \angle ADB = 13^{\circ}$, Find $\angle BDC$.

REPLY [7 votes]: Nice problem!
Let $X$ be a point symmetric to $A$ with respect to $BD$. Let $Y$ be a point symmetric to $A$ with respect to $BX$. Let $Z$ be a point symmetric to $A$ with respect to $DX$.

Then $DA=DX=DZ$, $BA=BX=BY$, and $AX=XY=XZ$. Angle chasing gives
$$\angle ZXY=360^\circ - \angle AXZ - \angle YXA = 360^\circ - 2\angle AXD - 2\angle BXA = \angle XDA + \angle ABX = 2\angle BDA + 2 \angle ABD = 2\cdot 13^\circ+2\cdot 17^\circ = 60^\circ$$
which along with $XZ=XY$ implies that $XYZ$ is equilateral. Thus
$$\angle BZA = \angle BZX + \angle XZA = 30^\circ + 13^\circ = 43^\circ.$$
We also have
$$\angle DBZ = \angle DBX + \angle XBZ = 2\angle ABD = 34^\circ.$$
This means that $Z=C$. Therefore
$$\angle CDB = \angle ZDB = 3\angle BDA = 39^\circ.$$

Below is a trigonometric solution. Let $\angle CDB = x$. We use Snellius' theorem thrice:
\begin{align}
\frac{AC}{DC} & = \frac{\sin(13^\circ + x)}{\sin 64^\circ}, \\
\frac{DC}{CB} & = \frac{\sin 34^\circ}{\sin x}, \\
\frac{CB}{AC} & = \frac{\sin 86^\circ}{\sin 51^\circ}.
\end{align}
Multiplying yields
$$1=\frac{\sin(13^\circ + x)\sin 34^\circ \sin 86^\circ}{\sin 64^\circ \sin x \sin 51^\circ}$$
so $$\sin(13^\circ + x)\sin 34^\circ \sin 86^\circ = \sin 64^\circ \sin x \sin 51^\circ.$$
Using $2\sin A \sin B = \cos(A-B) - \cos(A+B)$ twice we get
$$\sin(13^\circ + x)\left(\cos 52^\circ - \cos 120^\circ \right) = \sin x \left(\cos 13^\circ + \cos 65^\circ\right).$$
Since $\cos 120^\circ = -\frac 12$, we have
$$\sin(13^\circ + x) \cos 52^\circ + \frac 12 \sin(13^\circ + x) = \sin x \cos 13^\circ + \sin x \cos 65^\circ.$$
Multiplying by two and using $2\sin A \cos B = \sin(A+B) + \sin(A-B)$ we infer
$$\sin(65^\circ + x) + \sin(x-39^\circ) + \sin(13^\circ + x) = \sin(x+13^\circ) + \sin(x - 13^\circ) + \sin(x+65^\circ) + \sin(x-65^\circ).$$
Therefore
$$\sin(x - 39^\circ) = \sin(x-13^\circ) + \sin(x-65^\circ).$$
We use now $\sin A + \sin B = 2 \sin \frac{A+B}2 \cos\frac{A-B}2$:
$$\sin(x-39^\circ) = 2\sin(x-39^\circ)\cos 26^\circ$$
or
$$\sin(x-39^\circ)(1-2\cos 26^\circ)=0.$$
Since $\cos 26^\circ \neq \frac 12$, we have $\sin(x-39^\circ)=0$ and so $x=39^\circ$.


TITLE: Question Regarding Limits and Confusing Notation
QUESTION [1 upvotes]: My calculus teacher assigns us online homework to do.  He never went over any question that looks like this (he in fact said we shouldn't be concerned with this):
Yet, I need to answer this right to progress with my homework.  It stinks because if I get it wrong, I lose points on my homework average.
So, could someone help explain to me what's going on here, and perhaps guide me to a point where I can try to figure out the solution myself?  I'm not asking for a straight answer (although if thats what you want to provide, go for it [since I was told I don't have to know this stuff]), but this stuff really confuses me.  Thank you for your help.
Oh, and in case you need it, here's the original prompt (the question I posted above is just a part of a series of questions that go along with this prompt):

REPLY [3 votes]: I think the question is quite confusingly worded. It took me several minutes to figure out what it meant -- and it's not as if I don't know the subject matter well.
What must be going on is that you're supposed to imagine reading something like this in a proof:

bla bla bla, and therefore we know that $f$ is continuous, and that $f(c)\ne 0$. We can then apply the definition of continuity with $\varepsilon = $ _______ to find a $\delta$ such that $f(x)$ has the same sign as $f(c)$ for every $x\in(c-\delta,c+\delta)$. Thus, bla bla bla

One of $|f(c)|$ and $|c|$ will make this into a valid argument if you fill it into the blank, and one will produce nonsense. Your task is to select the valid one.
In order to answer the question you need (1) to remember the definition of continuity, and (2) to be able to distinguish a nonsense argument from a valid one. The second of these abilities is often considered too advanced a skill to demand of pre-university students these days (they're supposed to be satisfied with accepting the teacher's judgement in each case), which is probably why your teacher is not allowed to say you must be able to do it...

REPLY [1 votes]: Without loss of generality we may assume that $f(c)$ is positive.
Let $\epsilon =f(c)$.  By the definition of continuity of $f$ at $c$, there is a $\delta>0$ such that if $|x-c|<\delta$ (and $a\lt c-\delta$, and $c+\delta \lt b$, to make sure we stay in our interval) then $|f(x)-f(c)|<\epsilon$.
Now if you have some experience with inequalities, you should be able to reach the conclusion.
If the "without loss of generality" is not persuasive, if $f(c)<0$, let $g(x)=-f(x)$, apply the above argument to $g(x)$, and see what this says about $f(x)$.
I did not use precisely the language of the question. But you should now be able to see enough of what is going on to be able to answer that question.
Comment: It will be helpful to draw a picture while figuring out what the second paragraph is saying.


TITLE: Why is arc length independent of parametrization?
QUESTION [1 upvotes]: For example, say a curve $C$ can be parametrized as $x_1(t)$, $y_1(t)$ over an interval $A$ and $x_2(t), y_2(t)$ over an interval $B$. Why is the arc length computed using the first parameterization the same as the length computed using the second parameterization? Is this always the case, or are there any exceptions?

REPLY [2 votes]: Let $\phi = (x_1, y_1)$, $\psi = (x_2, y_2)$. Note the definition of the surface integral claims that,
$$\int_{C}1\,dS := \int_{A}\sqrt{\det(D\phi(t)^TD\phi(t))}\,dt$$
is well defined, independent of the parameterization $(A, \phi)$. That is, it claims that
$$\int_{A}\sqrt{\det(D\phi(t)^TD\phi(t))}\,dt = \int_{B}\sqrt{\det(D\psi(s)^TD\psi(s))}\,ds.$$
Set $F = \psi^{-1} \circ \phi \colon A \to B$. Note that $F$ is a diffeomorphism.
By the change of variables formula for integration substituting $s = F(t)$, we have
\begin{align}
\int_{B}\sqrt{\det(D\psi(s)^TD\psi(s))}\,ds = \int_{A}\sqrt{\det(D\psi(F(t))^TD\psi(F(t)))}|\det(DF(t))|\,dt.
\end{align}
We have $\phi(t) = \psi(F(t))$, so $D\phi(t) = D\psi(F(t))DF(t)$. Thus
\begin{align}
\sqrt{\det(D\phi(t)^TD\phi(t))} &= \sqrt{\det(DF(t)^TD\psi(F(t))^TD\psi(F(t))DF(t))} \\
&= \sqrt{\det(D\psi(F(t))^TD\psi(F(t)))}|\det(DF(t))|.
\end{align}
Thus $\int_{A}\sqrt{\det(D\phi(t)^TD\phi(t))}\,dt = \int_{B}\sqrt{\det(D\psi(s)^TD\psi(s))}\,ds$, so the surface integral is well defined, independent of the parameterization. The above proof works for surfaces of arbitrary dimension, and with small modification, works for integrals of any function $f \colon C \to \mathbb{R}$, not just $f = 1$. Technically the sets $A$ and $B$ should be open though.


TITLE: Are the abelian absolute Galois groups of these local fields isomorphic?
QUESTION [6 upvotes]: For a field $F$ we denote by $F^{\mathrm{ab}}$ the compositum of all finite Galois abelian extensions of $F$.

Is $\mathrm{Gal}(\mathbb{Q}_2(\sqrt[8]{3})^{\mathrm{ab}}/\mathbb{Q}_2(\sqrt[8]{3})) \cong \mathrm{Gal}(\mathbb{Q}_2(\sqrt[8]{48})^{\mathrm{ab}}/\mathbb{Q}_2(\sqrt[8]{48})) ? $

Equivalently,

Is every finite abelian group which is a Galois group of some finite Galois extension of $\mathbb{Q}_2(\sqrt[8]{3})$, is also a Galois group of some finite Galois extension of $\mathbb{Q}_2(\sqrt[8]{48})$ (and vice versa) ?

REPLY [8 votes]: Although @znt has gotten the answer through pari, I think it may be instructive to outline my argument.
It all depends on the transition function of Higher Ramification Theory: for a finite extension $K\supset k$ of local fields, $\varphi^K_k$ is a function from $\Bbb R^{\ge0}$ to itself, polygonal and concave, in which, if the (finitely many) vertices are $\{(x_i,y_i)\}$, each $x_i$ is a lower number of a ramification break, and $y_i$ is the corresponding upper number. Perhaps the most useful property of the transition function is that it is functorial: if $L\supset K\supset k$, then $\varphi^L_k=\varphi^K_k\circ\varphi^L_K$.
Although you’ll see below that there are other methods of calculating $\varphi^K_k$, here’s a relatively painless way for totally ramified extensions, if you know a prime element $\pi$ of the integers of the big field. Let $F(X)\in k[X]$ be the minimal $k$-polynomial for $\pi$, and draw the Newton copolygon of $F(X+\pi)$.
The copolygon of $g(X)=\sum_na_nx^n$ is the intersection of all the lower halfplanes $\eta\le n\xi+v(a_n)$, where you may take $v$ to be the (additive) valuation for which $v(k^\times)=\Bbb Z$. One sees that the segments of the copolygon are in one-to-one correspondence with the vertices of the Newton polygon: there’s a segment along the line $\eta=n\xi+v(a_n)$ if and only if $(n,v(a_n))$ is a vertex of the polygon.
And you get the transition function from this process by stretching the boundary of the copolygon horizontally by a factor of $e^K_k$, the ramification index (equal to the degree since our extension is presumed totally ramified). That is, every point $(\xi,\eta)$ on the boundary of the copolygon gets moved to the point $(e^K_k\xi,\eta)$ on the graph of the transition function. The function achieved in this way is shifted one unit up and one to the right from that defined in most standard texts, like Corps Locaux of Serre. In all cases, the infinite segment in the graph has slope $1/e^K_k$, and in the case of wildly ramified extensions, all slopes are powers of $1/p$.
Now calculate the transition functions of $\Bbb Q_2(3^{1/8})$, $\Bbb Q_2(\sqrt3\,)$, and $\Bbb Q_2(\sqrt2\,)$, all as extensions of $\Bbb Q_2$.
I won’t go through the details, except to say that $(X+1)^8-3$ and $(X+1)^2-3$ are the Eisenstein polynomials for the first two of the fields above. You find that the transition functions are: $\varphi^{\Bbb Q_2(3^{1/8})}_{\Bbb Q_2}$ has vertices $(2,2)$, $(4,3)$, and $(8,4)$;
$\varphi^{\Bbb Q_2(\sqrt3\,)}_{\Bbb Q_2}$ has the single vertex at $(2,2)$, and $\varphi^{\Bbb Q_2(\sqrt3\,)}_{\Bbb Q_2}$ has the single vertex at $(3,3)$.
Even though the transition function of $\Bbb Q_2(\sqrt2,\sqrt3\,)$ over $\Bbb Q_2$ can be calculated directly knowing that a prime element is $\pi=1-(\sqrt3-1)\big/\sqrt2$, you can also get it from the transition functions of the subfields, using functoriality. The upper numbers ($\eta$-values) of the subfields must appear among the upper numbers of the whole extension. Since these numbers are $2$ and $3$, $\varphi^{\Bbb Q_2(\sqrt2,\sqrt3\,)}_{\Bbb Q_2}$ must have the vertices $(2,2)$ and $(4,3)$.
All the above is straightforward and easy. But I wanted the transition function of the extension $\Bbb Q_2(\sqrt2,3^{1/4})$ over $\Bbb Q_2(\sqrt2,\sqrt3\,)$. For that I needed a prime element, and I found
$$
\beta=\frac{\frac{3^{1/4}-1}{\pi}-1}{\pi^2}-1\,,
$$
for which the minimal polynomial over $\Bbb Q_2(\sqrt2,\sqrt3\,)$ is of form $X^2+u_1\pi X+u_2\pi$, for units $u_i$. The upshot is that the transition function has the single vertex $(2,2)$. Compose this function first, then the transition function $\varphi^{\Bbb Q(\sqrt2,\sqrt3\,)}_{\Bbb Q_2}$, and you see that the transition function for the degree-eight extension $\Bbb Q_2(\sqrt2,3^{1/4})$ over $\Bbb Q_2$ has two vertices $(2,2)$ and $(6,3)$. The slope ratio at the lefthand vertex is $4$ rather than $2$.
And that’s enough to get our conclusion that $\Bbb Q_2(\sqrt2,3^{1/8})$ is totally ramified of degree $16$ over $\Bbb Q_2$, since its transition function must  have a vertex with height $4$, coming from the subfield $\Bbb Q_2(3^{1/8})$. So the full transition function has vertices $(2,2)$, $(6,3)$, and $(14,4)$.


TITLE: Maximising Entropy of Random Variable taking Positive Integer Values
QUESTION [2 upvotes]: A random variable $X$ takes positive integer values and $E[X]=6$. What distribution of the random variable $X$ maximises the entropy $H(X)$? What if $X$ can only take a finite number of values?
Ignoring the expected value bit, effectively I want to take some form of uniform distribution on the natural numbers (I know this can't be done) since if $X$ takes a finite number of values then the distribution which maximises entropy is the uniform distribution on those values.
I have a feeling that you might not be able to maximise the entropy in the infinite value case but I don't know how I would show that.
Any help or hints appreciated.

REPLY [2 votes]: The following heuristic argument suggests that the entropy $H(X)$ is largest when
$$p_k={1\over5}\left({5\over6}\right)^k\qquad(k\geq1)\ .\tag{1}$$
The value obtained in this way is
$$H(X)=6\log 6-5\log 5\ .$$
We have to maximize
$$H({\bf p}):=-\sum\nolimits_{k\geq1} p_k\log p_k$$
under the constraints
$$\sum\nolimits_{k\geq1} p_k=1,\quad \sum\nolimits_{k\geq1}k p_k=6\ .\tag{2}$$
We set up the "Lagrangian"
$$\Phi:=-\sum\nolimits_{k\geq1} p_k\log p_k-\lambda\left(\sum\nolimits_{k\geq1} p_k-1\right)-\mu\left(\sum\nolimits_{k\geq1}k p_k-6\right)$$
and obtain the equations
$$\Phi_{.k}=-\log p_k -1-\lambda -\mu k=0\qquad(k\geq1)\ .$$
It follows that
$$p_k=Ae^{-Bk}\qquad(k\geq1)\ ,$$
where $A$ and $B$ have to be determined using the constraints $(2)$. Doing the computation one finds the $p_k$ given in $(1)$.


TITLE: Sub-Graph of a Minimum Spanning tree
QUESTION [2 upvotes]: I am going through all the exercises in my book for revision of a class test next week, and i am really confused about this sub-graph question.
Currently my thinking leads me to believe that since we already have a minimum spanning tree G therefore since we have sub-nodes present in that minimum spanning tree, a G' has to exist. As far as the condition goes, i'm at a bit of a loss.

A graph X′ is a sub-graph of graph X if the node and edge sets of X′
  are subsets of the node and edge sets of X respectively. Let us have
  (V,T) as a minimum spanning tree of G and  G′=(V′,E′) be a connected
  sub-graph of G.
(a)  Prove that (V′,E′∩T) is a sub-graph of a minimum spanning tree of G′.
(b) Under what condition is (V′,E′∩T) a minimum spanning tree of G′?
  Prove your claim.

thanks in advance!

REPLY [1 votes]: I suppose it's a little bit late to help you for your test, but here goes.
First, when you write "minimum spanning tree," all spanning trees in a given graph have the same number of nodes and the same number of edges. So I'm going to assume that what we are dealing with is a weighted graph, and we are discussing minimal weight spanning trees.
Now $(V',E'\cap T)$ clearly has no cycles, so it can be extended to a spanning tree of $G'$, perhaps in many ways. Among those ways, pick one, call it $T^+$ of minimal weight: we want to show $T^+$ is a minimum weight spanning tree for $G'$.
Well, suppose it isn't. Then there's a different tree, $T^-$, that is a spanning tree for $G'$ and has smaller weight than $T^+$. Now prove that you can extend $T^-$ to be a spanning tree $T^*$ for $G$ by adding some of the edges of $T$ (this, I think, is where you're going to have to add some details to fill out this sketch). But then $T^*$ has weight less than that of $T$, contradiction.
For (b), since we have proved $(V',E'\cap T)$ is a subgraph of a minimum spanning tree of $G'$, it follows that it is a minimum spanning tree of $G'$ if and only if it is a spanning tree of $G'$.


TITLE: How can I compose the proof?
QUESTION [1 upvotes]: Prove that $$\Big(\frac{21}{20}\Big)^{100}>100.$$
I have tried proving that $$100\log\Big(\frac{21}{20}\Big)>2$$ but I was not able to evaluate it properly.

REPLY [1 votes]: \begin{align}\Big({21\over20}\Big)^{100} &= (1+{1\over 20})^{100}\\
&={100\choose 0} +{100\choose 1} ({1\over 20})^{1} +{100\choose 2} ({1\over 20})^{2} +{100\choose 3} ({1\over 20})^{3} +... \\
&>1+5+12+20+24,5+23,5+18 =105
\end{align}


TITLE: Show that the power series of complex function is defined and holomorphic
QUESTION [1 upvotes]: Let $(a_k)_{k\geq 0}$ be a sequence of complex numbers such that for
all $C>0$, $\lim_{k\to\infty}\mid a_k\mid C^k=0$. Show that
$$f(z)=\sum\limits^{\infty}_{k=0}a_k \exp(2i\pi kz)$$ is defined for
all $z$; that $f$ is entire, and that $f(z+1)=f(z)$ for all
$z\in\mathbb{C}$

I have proved the part $f(z+1)=f(z)$. To show that $f(z)$ converges and entire, I want to use the theorem

If $\{f_n\}^{\infty}_{n=1}$ is a sequence of holomorphic functions
that converges uniformly to a function $f$ in every compact subset of
$\Omega$, then $f$ is holomorphic in $\Omega$.

So I need to see what function it converges to, and $\sum\limits^{\infty}_{k=0}a_k e^{2i\pi kz}$ converges uniformly to that function in every compact subset of complex plane. But I am not sure how to proceed. Can you explain if this is the right idea, and if not, could you give me other suggestions? Thanks!

REPLY [2 votes]: It suffices to show that
$$ \tag{*}
 F(w) = \sum_{k=0}^\infty a_k w^k
$$
defines an entire function, because then $f(z) = F(e^{2\pi i z})$ is entire as the composition of entire functions.
Given $R > 0$ choose any $C > R$, then
$$
 |a_k w^k| \le |a_k| R^k = |a_k| C^k \left( \frac{R}{C} \right)^k  \le \left( \frac{R}{C} \right)^k
$$
for all $|w| \le R$ and all sufficiently large $k$, which (by the Weierstrass M-test) implies that the series $(*)$ converges uniformly on the disk $|w| \le R$.
In other words, the condition $\lim_{k\to \infty} |a_k | C^k = 0$ for all $C > 0$ implies (and actually is equivalent to) that the radius of convergence of the power series $(*)$ is infinity.
So your idea of proving uniform convergence on compact sets is correct, but (in the general case of arbitrary coefficients $a_k$) there is no closed form for the limit function. The Weierstrass M-test helps because it can be used to prove uniform convergence without knowing the limit function. This is closely related to the Cauchy criterion which can be used to prove convergence of a sequence without knowing the limit.


TITLE: If $Y\sim\operatorname{Beta}(a,1-a)$ and $Z\sim\operatorname{Exp}(1)$, then $YZ\sim\operatorname{Gamma}(0,1)$?
QUESTION [6 upvotes]: I have two random variables

$Y \sim \operatorname{Beta}(a, 1 - a)$
$Z \sim \operatorname{Exp}(1)$

If $Y$ and $Z$ are independent, why is the distribution of $X = YZ \sim \operatorname{Gamma}(a, 1)$?
$f_X(x) = \int_0^\infty|\frac{1}{y}|f_Y(y)f_Z(\frac xy)dy$
$f_X(x) = \int_0^\infty \frac{1}{y}\frac{1}{\Gamma(\alpha)\Gamma(1-\alpha)}y^{\alpha-1}(1-y)^{-\alpha}e^{-\frac{x}{y}}dy$
but I can't derive more than it.
How can I proof $YZ \sim \operatorname{Gamma}(a, 1)$ ?

REPLY [0 votes]: You could use Mellin transform to get distribution for $YZ$. For a product of two RVs, there is a very simple theorem, which states that Mellin transform of product distribution is the product of Mellin transform of the constituent RVs. So there is simple algorithm - Mellin transform of $Y$ multiplied by Mellin transform of $Z$, and then do inverse Mellin transform to get final PDF. It is just like using Fourier transform for sum of two RVs.
$$
M(YZ) = M(Y) M(Z)
$$
For exponential distribution $Y = \exp(-x)$
$$
M(Y) = \Gamma(s)
$$
For $Z = B(a, 1-a)$ one could easily get
$$
M(Z) = \frac{ \Gamma(s+a-1) }{\Gamma(s) \Gamma(a)}
$$
Therefore, for product
$$
M(YZ) = \frac{ \Gamma(s+a-1) }{\Gamma(a)}
$$
which gives us pretty obvious inverse transform in the form of
$$
PDF(x|YZ) = M^{-1}\{\frac{ \Gamma(s+a-1) }{\Gamma(a)} \} = \frac{ \exp(-x) x^{a-1} }{\Gamma(a)} 1_{x>0}
$$


TITLE: Proving that a set is countable
QUESTION [3 upvotes]: My attempt is as follows:
We will start by considering each ‘walk’ as some set of steps.
So a walk of length $m$ can be represented by the set $S_m =$ {$x_1, x_2, x_3, … , x_m$}.
To each of these steps we assign at random a value of $0$ or $1$.
The number of possible walks of a certain length, say $n$, is the same as the number of functions from $S_n$ to {$0, 1$}, which is $2^n$.
Now, the question tells us that the number of steps in a certain walk can get ‘very large’ so, assuming we begin the walk at the entrance to the pub, it would be silly to have walks consisting only of a ‘very large’ number of backward steps. It may, therefore, be better to write the number of possible walks of length $n$ as being $\leqslant 2^n$
The set of all possible random walks is then the disjoint union
$S = \bigcup_{r = 1}^{L} S_r$, where $L$ is possibly a very large number, the cardinality of which is $\leqslant 2^1 + 2^2 + 2^3 + ... +2^L$ So the cardinality is bounded above by a finite quantity, so there is a bijection $f : \mathbb{N}_{i} \mapsto S$ for some $1 \leqslant i \leqslant 2^1 + 2^2 + 2^3 + ... +2^L$ hence the set is countable.
The context is a little peculiar, so I'm not entirely convinced that my interpretation of the question is correct, so if anyone could give me some feedback on this that'd be great.

REPLY [0 votes]: Let a walk be marked as $X= ${$x_1, x_2........, x_m$} where $x_i$ are $0$ or $1$.
Let $f(X) = \sum x_i 2^i \in \mathbb N$.
Suffices to prove $f$ is injective, that is, if $f(X) = f(W)$ then $X = W$.  This is precisely a matter of proving no natural number has binary expressions.
Can you do that?


TITLE: Stopping time $\max \{n: S_n \le t\}$
QUESTION [1 upvotes]: Let $\{X_n\}_{n \in \mathbb{N}}$ be iid and non-negative.
Let $$N(t): = \max \{n: \ X_1 + \cdots + X_n \le t \}.$$
Is $N(t)$ a stopping moment with respect to the natural filtration $\{\mathcal{F}_n\}_{n \in \mathbb{N}}$ generated by $\{X_n\}_{n \in \mathbb{N}}$ ?
How about $N(t) + 1$?
I think that both are stopping moments.
Here is my solution:
$$\{N(t) \le k \} = \{N(t) =0 \} \cup \cdots \cup \{N(t) = k \}$$
Is $\{N(t) =0 \} = \{ X_0 \le t\} \cap \bigcap_{n \ge 1} \{S_n > t\} \in \mathcal{F}_0 $? We know for sure that $\{ X_0 \le t\} \in \mathcal{F}_0$.
Next, $$\{N(t) =1 \} = \{ X_0 \le t\} \cap \{ X_0 + X_1 \le t\} \cap \bigcap_{n \ge 2} \{S_n > t\}$$
And again, by measurability of $X_0, X_1, \ldots$ and the fact that we have the natural filtration, we have: $\{ X_0 \le t\}\in \mathcal{F}_0 \subset \mathcal{F}_1$ and $ \{ X_0 + X_1 \le t\} \in \mathcal{F}_1$.
$$\{N(t) = k \} = \bigcap_{0 \le n \le k} \{S_n \le t\} \cap \bigcap _{n \ge k+1} \{S_n > t\},$$ where $\bigcap_{0 \le n \le k} \{S_n \le t\} \in \mathcal{F}_n$ but I'm not sure about the second intersection.
When it comes to that infinite intersections, I know that each of $\{S_n > t \}$ is measurable in $\mathcal{F}_n$, but for the filtration $\{\mathcal{F}_n \} _{n \in \mathbb{N}}$ we have that $\mathcal{F}_n \subset \mathcal{F}_{n+1}$ not the other way around.
And when it comes to $N(t) + 1$ it is a general fact that $\tau$ - stopping time $\implies \tau +1$ is a stopping time.
So could you tell me what I can do with the infinite intersections?
Or maybe my reasoning is incorrect and there should be no infinite intersections here?

REPLY [1 votes]: No, $N(t)$ is, in general, not a stopping time. The condition $\{N(t) \leq k\} \in \mathcal{F}_k$ means, roughly, that we can decide whether $N(t)(\omega) \leq k$ given the information up to time $k$, i.e. the values $X_1(\omega),\ldots,X_k(\omega)$. This is obviously not satisfied here because in order to decide whether $N(t)(\omega) \leq k$ we need to know whether $S_{k+1}(\omega) > t$ (and for this we also need $X_{k+1}(\omega)$).

As you already noted, we have
$$\{N(t)=0\} = \{X_0 \leq t\} \cap \bigcap_{n \geq 1} \{S_n>t\}.$$
Since $\{S_1>t\} \subseteq \{S_2>t\} \subseteq \dots$ (because of the non-negativity of $X_n$), this simplifies to
$$\{N(t)=0\} = \{X_0 \leq t\} \cap \{S_1>t\} = \{X_0 \leq t\} \cap \{X_0+X_1 > t\};$$
this set is, in general, not contained in $\mathcal{F}_0$. This implies that $N(t)$ is not a stopping time. However, using the formula
$$\{N(t)=k\} = \bigcap_{0 \leq n \leq k} \{S_n \leq t\} \cap \{S_{k+1}>t\}$$
it is not difficult to see that $N(t)+1$ is a stopping time.


text:
\section{The Witness Complex and Map}  \label{sec:witness:map}

In this section, we define a simplicial multivalued \emph{witness map} $\cFW$ on a complex $\cW$ that is a variant of the \emph{witness complexes} introduced by \cite{deSilva04}.
The goal is to obtain an outer approximation of a continuous map $f: X \to X$ when the only data that we have is a time series $\Gamma = \{x_0,\ldots,x_{T-1}\}$ near an invariant set $\Lambda \subset X$.
To construct a multivalued map that approximates $f$, we view
the data as ``witnesses" to a set of $\ell$ nearby landmarks, $L = \{l_1,\ldots,l_{\ell}\}$.
There are many possible methods to choose appropriate landmarks. One strategy, as mentioned in \Sec{AlphaComplex}, is the max-min procedure of \cite{deSilva04}; but \label{page:landmarks} there are many other possible
methods, and indeed it is not necessary that $L$ be a subset of $\Gamma$.
The landmarks can be viewed either as the centers of the cells of an $\alpha$-grid $\cA_\alpha(L)$, or as the vertices of a witness complex $\cW(\Gamma,L)$.
We show below that if the data satisfy certain density criteria and the landmarks are (more or less) uniformly spaced, then there is an $\alpha$ for which the witness complex is identical to the  $\alpha$-complex $\cK_\alpha(L) = N(\cA_\alpha(L))$.

The temporal ordering of $\Gamma$ and the witness relation give rise to both an SMM $\cFW$ and an associated CMM, $\FW$, on the $\alpha$-grid.
We show that when the map $f$ is Lipschitz and the trajectory $\Gamma$ is dense enough,
there is an $\alpha$ such that $\FW$ is an outer approximation of $f$.

\subsection{Witness Complex}\label{sec:WitnessComplex}

A witness complex is a simplicial complex based on a finite data set $\Gamma$ that
is intended to be more parsimonious than more traditional Rips or \v{C}ech complexes (recall \App{Complexes}) \cite{deSilva04, deSilva08}. The vertices of the complex are taken from a set of landmarks $L$ whose cardinality is much smaller than that of $\Gamma$.
The complex $\cW(\Gamma,L)$ consists of those subsets of $L$ that have a \emph{witness} in $\Gamma$. For example, de Silva and Carlsson say a point $x \in \bR^n$ is
a \emph{weak} witness to a $k$-simplex if the $k+1$ nearest
landmarks to $x$ are the vertices of the simplex. If, in addition, $x$ is
equidistant from each of the vertices, then it is a \emph{strong}
witness to the simplex .

Another way to define witness complexes is through a general construction of Dowker \cite{Dowker52} that associates abstract simplicial complexes with a relation; that is, by the selection of a subset
\beq{WitnessRelation}
	R \subset \Gamma \times L.
\eeq
For example, the strong witness complex corresponds to the relation
$
	R_{0} = \{ (x,l) \in \Gamma \times L : d(x,l) = d(x,L)\}
$.
We say that a point $x$ is a witness to a point $l$ if $(x,l) \in R$.  Thus,
\[
	W_R(\Gamma, l) = \{x\in\Gamma: (x,l) \in R\}
\]
is the set of witnesses to the landmark $l$.
Following Dowker, a relation gives rise to two abstract simplicial complexes, by vertical and  horizontal slices, respectively.
In our notation, the witness complex is the former: the vertices of each simplex in the complex share a witness:
$
	\bigcap_{l \in \sigma} W_R(\Gamma,l) \neq \emptyset .
$

We will use a more easily computed version of the witness complex,  a \emph{clique} complex, which is the maximal complex with a given set of edges (recall \App{Complexes}).
The clique complex for a given relation \Eq{WitnessRelation} is
\beq{CliqueComplex}
	\cW_R(\Gamma,L) = \{ \sigma: W_R(\Gamma, l) \cap W_R(\Gamma, l') \neq \emptyset,\, \forall l,l' \in \sigma\} .
\eeq
Note that, though the vertices of each edge in $\sigma$ must share a witness, there need not be a common witness to every vertex in $\sigma$.

There are many possible choices for the witness relation $R$.
\label{page:epsilon}
We choose to use a fuzzy version of the strong-witness relation:
\beq{FuzzyWitness}
	R_\eps = \{ (x,l) \in \Gamma \times L: d(x,l) \le d(x,L)+ \eps \}.
\eeq
That is, $x$ witnesses all landmarks no more than $\eps$ farther from $x$ than its nearest landmark.\footnote

{In the notation of \cite{deSilva04}, this relation corresponds to the
complex $W(D,\eps,1)$, where $D$ denotes the matrix of distances
between landmarks and witnesses.}

The parameter $\eps$ represents the \emph{fuzziness} of the boundary between cells.
The definition \Eq{FuzzyWitness} becomes the strong witness relation
for $\eps = 0$.
We will denote the set of witnesses to a landmark using \Eq{FuzzyWitness} by
$
	W_\eps(\Gamma, l),
$
and the resulting clique complex \Eq{CliqueComplex} by $\cW_\eps(\Gamma,L)$.

An example is shown in \Fig{WitnessRelation} for an orbit of the
logistic map on $[0,1]$ for a parameter value just above the first
period-doubling accumulation point. Here, the landmarks were selected to be every
$30^{th}$ point in the sorted data, an orbit of length $T=300$. The
relation \Eq{FuzzyWitness} for $\eps = 0.01$ is the set of (blue) points near the
diagonal. For the case shown, each point in $\Gamma$ is a witness to at most two landmarks, and so the maximum dimension of a simplex in the complex \Eq{CliqueComplex} is one.

\InsertFig{WitnessRelation}{Witnesses (blue points) defined by the relation \Eq{FuzzyWitness}  for the logistic map, $f(x) = 3.56x(1-x)$ with $\eps = 0.01$. The orbit $\Gamma$, shown along the horizontal axis (black points), has $T= 300$ points, and there are $\ell = 10$ landmarks, shown along the vertical axes (red points). The witness relation defines six one-dimensional simplices (the line segments along the vertical axis), giving a complex with Betti number $\beta_0 = 4$. These correspond to the four major bands in the chaotic attractor of $f$.}{WitnessRelation}{3in}

One way to compute the relation \Eq{FuzzyWitness} is to sort
the rows of the $T \times \ell$ distance matrix $D_{tj} = d(x_t,l_j)$
in order of increasing size; thus, for the sorted matrix $D^s_{t,1} =
d(x_t,L)$. Then $x_t$ is a witness to all of the landmarks in the
first few columns of the $t^{th}$ row of $D^s$, namely those for which
$D^s_{t,j} \le D^s_{t,1} +\eps$.  The main computational expense
here---the distance calculations---can be reduced using a
$kd$-tree \cite{Friedman77}.
In addition, most implementations of efficient $k$-nearest-neighbor
algorithms return their results sorted in size order.  See
\App{Complexity} for more discussion of algorithms and complexity.

The following section describes how the complex $\cW_\eps(\Gamma,L)$ using the witness
relation \Eq{FuzzyWitness} can be related to an $\alpha$-complex using the same landmark set, under some conditions on the selection of the landmarks and $\alpha$.

\subsection{Equivalence Conditions for $\cK_\alpha(L)$ and $\cW_\eps(\Gamma,L)$}\label{sec:equivalence}

The witness complex is based on the set of landmarks $L$ in $\bR^n$ that can also be viewed as the centers of an $\alpha$-grid $\cA_\alpha(L)$. Since the $\alpha$-diagram limits to
the Voronoi-diagram, it is clear that for large enough $\alpha$,
$|\cW_\eps(\Gamma,L)| \subset |\cA_\alpha(L)|$.
Moreover, for large enough $\alpha$, the associated $\alpha$-complex $\cK_\alpha(L)$ is a clique complex---just as we have assumed for the fuzzy witness complex using \Eq{CliqueComplex}.
We will show here that when this is the case---and if the landmarks are
not too closely spaced---then
$\cW_\eps(\Gamma,L) \subset \cK_\alpha(L)$. Conversely, when the data $\Gamma$ are
dense enough on $|\cA_\alpha(L)|$ we will see that
$\cK_\alpha(L) \subset \cW_\eps(\Gamma,L)$. Consequently, when both sets of conditions are
satisfied, the complexes are the same. As the hypotheses to obtain
these results are independent, we state these two results separately.

\begin{theorem} \label{thm:AlphaSubsetWitness}
For a set of landmarks $L$, a time series $\Gamma$, and $\alpha, \eps > 0$, let $\cK_\alpha(L)$
be the $\alpha$-complex \Eq{NerveComplex} and $\cW_\eps(\Gamma,L)$ be the fuzzy witness complex
\Eq{CliqueComplex} using the relation \Eq{FuzzyWitness}. Suppose that there is a $\delta > 0$
such that $\Gamma$ is $\delta$-dense on $|\cA_\alpha(L)|$ and  $\delta \le \eps/2$.
Then $\cK_\alpha(L) \subseteq \cW_\eps(\Gamma,L)$.
\end{theorem}

\begin{proof}
Suppose $\sigma \in \cK_\alpha(L)$, i.e., there is a $y \in |\cA_\alpha(L)|$
such that $\Delta = d(y,L) = d(y,l_i) \le \alpha$ for all $l_i \in \sigma$. We will show that there is an $x \in \Gamma$ that witnesses all the vertices in $\sigma$, i.e.,
\[
	x \in \bigcap_{l\in\sigma} W_\eps(\Gamma,l).
\]
Since $\Gamma$ is $\delta$-dense, for any $y \in |\cA_\alpha(L)|$, there is at least one point $x \in \Gamma \bigcap B_\delta(y)$. Since $d(y,L) = \Delta$ and $d(x, y) \le \delta$, it follows that
\[
	d(x,L) \ge \Delta - \delta.
\]
Since $x \in B_\delta(y)$, for any $l_i \in \sigma$,
\[
	d(x, l_i) \le \Delta + \delta
	 \le d(x,L) + 2\delta
	 \le d(x,L) + \eps
\]
since $\delta \leq \eps / 2$. Hence, $x \in W_\eps(\Gamma, l_i)$ for
each vertex of $\sigma$ and therefore, $\sigma \in \cW_\eps$.
\end{proof}

Note that \Thm{AlphaSubsetWitness} applies even when the witness complex is not
defined as a clique complex. However, to show the converse---as we do next---requires
the clique assumption and also relies on the use of the Euclidean metric.

\begin{theorem} \label{thm:WitnessSubsetAlpha}
Suppose $\cK_\alpha(L)$ and $\cW_\eps(\Gamma,L)$ are as in \Thm{AlphaSubsetWitness},
and define
\[
	M = \max_{x \in \Gamma} d(x,L) \quad \mbox{and}\quad
	\beta = \min_{i\neq j} d(l_i, l_j).
\]
If $\alpha$ is chosen so that so that $\cK_\alpha(L)$ is a clique complex and
\beq{AlphaBound}
	M + \eps \le \alpha \le \tfrac{\beta}{\sqrt2},
\eeq
then $\cW_\eps(\Gamma,L) \subseteq \cK_\alpha(L)$.
\end{theorem}

\begin{proof}
Note that $\cK_\alpha(L)$ and $\cW_\eps(\Gamma,L)$ have the same vertex set, and by assumption each complex is a clique complex. This means that $\cK_\alpha$ and $\cW_\eps$ are each determined completely by their edges. It follows that we only need to verify that every edge in $\cW_\eps$ is also an edge in $\cK_\alpha$.

Supposing that $\langle l_1,l_2 \rangle \in
\cW_\eps$, then these landmarks share a witness, i.e., there is
an $x \in \Gamma$ such that $d(x ,l_i) \le d(x,L) +
\eps$ for $i \in \{1,2\}$. We want to show that there is a point $y \in
|\cA_\alpha(L)|$ such that $d(y,l_1) = d(y,l_2) = \Delta = d(y,L) \le \alpha$.
In the Euclidean metric there is always a point $y$ equidistant from the two
landmarks such that $d(y,l_i) = \tfrac12 d(l_1,l_2)$. Therefore, since
$d(l_1,l_2) \le d(x,l_1) + d(x,l_2) \le 2(d(x,L) + \eps)$, then
\[
	\Delta \le d(x,L) + \eps  \le M+\eps \le \alpha,
\]
by \Eq{AlphaBound}. Let $l_3 \in L$ be next closest landmark to $y$, besides $l_1$ and $l_2$, and define $\beta_1 = d(l_3,l_1)$, and $\beta_2 = d(l_3, l_2)$.
As illustrated in \Fig{ProofFig}, $\Delta' = d(l_3, y)$ is
minimized when $\beta_1 = \beta_2 = \beta$. In this case,
the segment from $l_3$ to $y$ is the
perpendicular bisector of the segment from $l_1$ to $l_2$ and so we
have $\Delta \le \Delta'$ only if $\Delta  \le \frac{\beta}{\sqrt{2}}$.
Since $\Delta \le \alpha$, this condition is assured by \Eq{AlphaBound}, and it follows
that $\langle l_1,l_2\rangle \in \cK_\alpha$. Since $\cK_\alpha$ is a clique complex we have shown that $\cW_\eps \subseteq \cK_\alpha$.
\end{proof}

\InsertFig{ProofFig}{An illustration of the spacing between three landmarks $l_1,l_2,$ and $l_3$, as in the proof of \Thm{WitnessSubsetAlpha}. The point $y$ is the midpoint between the two landmarks $l_1$ and $l_2$. By assumption, the distance from $l_3$ to $l_1$ or $l_2$ is at least $\beta$, and it is thus minimized when $\beta_1 = \beta_2 = \beta$.}{ProofFig}{3in}

In order to apply \Thm{WitnessSubsetAlpha}, $\cK_\alpha(L)$ must be a
clique complex, which is not always true. However, since the Delaunay complex $\cD(L)$ (recall \App{Complexes}),
is a clique complex (the Voronoi cells cover $\bR^d$); then $\cK_\infty(L) = \cD(L)$
is a clique complex as well. Indeed, whenever $\alpha$ is larger than the radius
of the biggest circumsphere that defines an $n$-dimensional simplex in
$\cD(L)$, then $\cK_\alpha(L) = \cD(L)$. For the simple case of a hexagonal
array of landmarks in $\bR^2$, these circumcircles all have
radius $\beta/\sqrt{3}$, so it is easy to determine when $\cK_\alpha(L)$
is clique. For the trivial case when $\alpha < \beta/2$, the
$\alpha$-balls about each landmark are disjoint, so the
$\alpha$-complex is trivial, and also a clique complex.

When both \Thm{AlphaSubsetWitness} and \Thm{WitnessSubsetAlpha} hold,
then $\cW_\eps(\Gamma,L) = \cK_\alpha(L)$. In this case, a map defined using the
witness relation may have the same homology as a map on $\cA_\alpha(L)$. It is
to this issue that we turn next.

\subsection{Witness Map}\label{sec:WitnessMap}
Abstractly, we can define a cellular multivalued map on a grid $\cA(L)$ that contains the orbit $\Gamma$ using any witness relation: whenever $x \in A_i$ and there is a witness $x_t \in \Gamma$ to the landmark $l_i$, then the image of $x$ should include the cells that $x_{t+1}$ witnesses. The appropriate map is defined similarly to the cellular map
$\FA$, \Eq{CellularMap}, but only using the data $\Gamma$ and the witness relation $R$.

To obtain a cellular map that induces a simplicial map on the witness complex, we assume that the hypotheses of Thms.~\ref{thm:AlphaSubsetWitness}--\ref{thm:WitnessSubsetAlpha} are satisfied. In this case, there are values of $\alpha$ and $\eps$ such that $\cK_\alpha(L) = \cW_\eps(\Gamma,L)$.

\begin{definition}[Cellular Witness Map] Suppose that $\alpha$ and $\eps$ are selected as in Thms.~\ref{thm:AlphaSubsetWitness}--\ref{thm:WitnessSubsetAlpha}. The witness map $\FW: |\cA_\alpha(L)|\rightrightarrows |\cA_\alpha(L)|$ for the fuzzy witness complex $\cW_\eps(\Gamma, L)$ is the cellular multivalued map
\beq{CellularWitnessMap}
	\FW(x) := \bigcap_{A_i \in \cA_\alpha(L) \,:\, x\in A_i} \{ A_j \in \cA_\alpha(L):
		\, \exists\, x_t \in W_\eps(\Gamma,l_i) \text{ s.t. } x_{t+1} \in W_\eps(\Gamma,l_j) \}.
\eeq
\end{definition}
\noindent
Since by hypothesis the nerve $\cK_\alpha(L) = N(\cA_\alpha(L))$ is also the witness complex, the CMM $\FW$ induces a simplicial multivalued map
\[
	\cFW: \cW_\eps(\Gamma,L) \rightrightarrows \cW_\eps(\Gamma, L)
\]
in precisely the same way that $\cFK$ was induced by $\FA$, namely by \Eq{FKDefinition}.
In other words, a simplex $\tau \in \cFW(\sigma)$ whenever there are witnesses to $\sigma$ that have images, under the temporal ordering of $\Gamma$, that are witnesses to $\tau$.  Indeed, the hypotheses of \Thm{AlphaSubsetWitness} imply that each nonempty image simplex $\tau \in \cFW(\sigma)$, which is automatically in $\cK_\alpha(L)$ since $A_\tau \neq \emptyset$, is also in the witness complex, since $\cK_\alpha(L) \subset \cW_\eps(\Gamma,L)$. Thus to guarantee that the image is in $\cW_\eps(\Gamma,L)$, we need $\Gamma$ to be sufficiently dense on the $\alpha$-shape ($\delta \le \eps/2$).
Under the additional conditions of \Thm{WitnessSubsetAlpha}, the complexes $\cK_\alpha(L)$ and $\cW_\eps(\Gamma,L)$ coincide and we can view the witness map as having the domain $\cW_\eps(\Gamma,L)$ as well. Thus to guarantee that the domain is well-defined we need that the landmarks are more-or-less uniformly spaced ($\beta$ is not too small), and that each point in $\Gamma$ is not too far from a landmark ($M$ is not too large).

The fact that the $\alpha$ and witness complexes coincide
gives us hope that $\FW$ will carry the same information about homology as the outer
approximation $\FA$. The following theorem ensures that this indeed is
the case when the original map $f$ satisfies a Lipschitz condition on
the grid.

\begin{theorem} \label{thm:WitnessEnclosure}
Suppose that $Y = |\cA_\alpha(L)|$ is compact and $f$ is Lipschitz on $Y$ with constant $c$. Then if $\Gamma$ is $\delta$-dense on $Y$ and $\delta \le \frac12 \eps \min\{1, \frac1c\}$, $\FW$ is an outer approximation of $f$.
\end{theorem}

\begin{proof}
We need to show that for any $y \in Y$, $f(y) \in \FW(y) $. Note that any such $y \in A_i$ for some $\alpha$-cell $A_i$ and $f(y) \in A_j$ for some other $\alpha$-cell $A_j$. We need to show that $A_j \subset \FW(A_i)$, or specifically, that there is an $x_t \in \Gamma$ such that $x_t \in W_\eps(\Gamma,l_i)$ and $x_{t+1} = f(x_t) \in W_\eps(\Gamma,l_j)$, where $l_i$ and $l_j$ are the landmarks associated with the $\alpha $-cells $A_i$ and $A_j$, respectively.
Since $\Gamma$ is $\delta$-dense, it follows that there is $x \in \Gamma$ with $d(x, y) \le \delta$. Thus, $x$ is at most $\delta$ closer to any landmark than $y$ (whose closest landmark is $l_i$),
\beq{max:dist}
	 	d(x,L) \ge d(y,l_i) - \delta,
\eeq
and consequently:
\beq{is:witness}
		 d(x, l_i) \le d(x, y) + d(y, l_i) \le d(x,L) + 2\delta,
\eeq
Since $2\delta \le \eps$, it follows that $x \in W_\eps(\Gamma, l_i)$. In addition, since $d(f(x), f(y)) \le cd(x , y)$ and $2c\delta \le \eps$, the same reasoning as \Eq{is:witness} leads to $f(x) \in W_\eps(\Gamma,l_j)$.

Note that the points $y$ and $f(y)$ may be in multiple $\alpha$-cells, but the construction above applies to each cell, and so the conclusion  is unaffected.
\end{proof}

We have shown that, under the conditions of
Thms.~\ref{thm:AlphaSubsetWitness}--\ref{thm:WitnessEnclosure}:
\begin{itemize}
\item
the witness complex computed from data has the same homology as the
union of a set of $\alpha$-cells that cover the data, and
\item when
viewed as a multivalued map on $\bR^n$, $\FW$ is an outer approximation
of the dynamical system $f$.
\end{itemize}
Since the cellular map $\FW$ is semicontinuous
(recall \Sec{cellular:maps}), we know that whenever it is acyclic,
then it is an enclosure of $f$. In this case, the acyclic carrier
theorem implies that
the induced map on homology can be computed
from any continuous selector to the witness
map \cite[Thm.~13.3]{Munkres84}. However, note that acyclicity cannot
be guaranteed; it must be checked when the map is numerically
constructed.
\label{page:acyclicity}

\subsection{Computing the Map on Homology}\label{sec:Homology}

In our approach, all of the information about the topology of the invariant set $\Lambda \subset X$
is contained in the simplicial complex
$\cW = \cW_\eps(\Gamma,L)$, so our computation of the map $f_*$, the action induced by $f$ on the homology groups, relies heavily on this simplicial complex. We begin by recalling
the notion of a chain map.
A chain map from one simplicial complex to another consists of a homomorphism between the vertex sets, a homomorphism between the edge sets, etc., each of which commutes with the boundary operator. Commutation implies, for example, that the boundary of the image of a $k$-simplex is mapped to the image of the boundary of the $k$-simplex. An important feature of a chain map, $\varphi$, is that it induces a well-defined map in homology, $\varphi_*$ \cite{Munkres84}.

Our strategy in calculating $f_*$ is to pick an appropriate chain map,
$\varphi$, so that $f_*$ coincides with $\varphi_*$.  That is, we select $\varphi: \cW \to \cW$ to be a \emph{chain selector}, so that $\varphi(\sigma) \in \cF_{\cW}(\sigma)$ for each $\sigma \in \cK$.
Such a selector can easily be constructed using as a piecewise linear map between the
topological realizations of the simplicial complexes. That is, we
consider $|\varphi|: |\cW| \to |\cW|$.
If $\varphi$ is a chain selector for the simplicial multivalued map $\cFW$, then it follows that $|\varphi|$ is a continuous selector for $\FW$ and hence, $\varphi_* = f_*$.

In summary, the strategy is as follows. To compute
the Conley index of an isolated invariant set,
it is sufficient to construct a cellular multivalued map
$\FA$ that encloses $f$. Yet computing the $\alpha$-grid on a given
data set and its associated cellular multivalued map $\FA$ can be
computationally expensive.  In this section, we have shown how to
construct a sparser simplicial complex---the witness complex
$\cW_\eps(\Gamma, L)$.  In addition, we define two associated
multivalued witness maps - the cellular map, $\FW$, defined implicitly
on $|\cA_\alpha(L)|$ and the combinatorial simplicial map, $\cFW$, defined on
the finitely determined complex $\cW_\eps(\Gamma,L)$. Moreover, when the
hypotheses of the theorems in this section can be verified, then
$\cW_\eps(\Gamma,L) = \cK_\alpha(L)$ and $\FW$ encloses the
dynamical system $f$.  Then any continuous selector for this map will
capture the homomorphism on homology $f_*$.  We get this continuous selector of $\FW$ by constructing a continuous selector of $\cFW$ and taking its geometric realization.

config: arxiv


TITLE: $f_0(x)=x$, $f_1(x)=x(1-x)$,...,$f_{n+1}(x)=f_n(x)(1-f_n(x))$ Prove that $f_n$ converges to $0$ on [0,1].
QUESTION [0 upvotes]: I'm trying to prepare for an upcoming test. This is a question I found on a previous midterm that I've been trying to solve:
Consider the sequence of functions defined on [0,1] given by:
$f_0(x)=x$, $f_1(x)=x(1-x)$,...,$f_{n+1}(x)=f_n(x)(1-f_n(x))$
Prove that $f_n$ converges to $0$.
I'm not quite sure how to prove this.
One idea I had was to try to use Theorem 7.9 in Rudin by defining:
$M_n = \sup_{x\in [0,1]} |f_n(x)|$
and trying to show that $M_n \to 0$ as $n \to \infty$ but that hasn't gotten me anywhere. Can anyone give me a hand?
Thank you kindly.

REPLY [1 votes]: $(1).$ For $x=0$ or $x=1:$ We have  $f_1(x)=0,$ and by induction on $n\ge 1$ we have $f_n(x)=0$ for all $n\ge 1.$
$(2).$ For $x\in (0,1):$ We have  $f_0(x)\in (0,1).$ If $f_n(x)\in (0,1)$ then $f_{n+1}(x)=f_n(x)(1-f_n(x))\in (0,f_n(x)).$ So by induction on $n\ge 0$ the sequence $(f_n(x))_{n\in \Bbb N_0}$ is decreasing and bounded below by $0,$ so it has a limit $L\in\Bbb R,$ and we have
$L=\lim_{n\to\infty}f_n(x)=$ $\lim_{n\to\infty}f_{n+1}(x)=$ $=\lim_{n\to\infty}f_n(x)(1-f_n(x))=L(1-L)=L-L^2.$
So $L=L-L^2,$ so $L^2=0.$
Addendum: We can handle $(1)$ and $(2)$ together by noting that for any $x\in [0,1]$ we have $f_0(x)\in [0,1]$ and we have $f_n(x)\in [0,1]\implies f_{n+1}(x)\in [0,f_n(x)]\subseteq [0,1].$


TITLE: Deriving symmetry of equality in FOL
QUESTION [1 upvotes]: In FOL with equality, the axioms of equality are:

$\forall x(x=x).$
Let $\varphi$ be a formula with free occurences of $x$, and define $\varphi'$ by replacing some or all of the free occurences of $x$ in $\varphi$ with $y$, then $\forall x\forall y(x=y\rightarrow(\varphi\rightarrow\varphi')).$

The symmetric property of equality becomes a theorem that follows from these, and I've tried the following:
Let $\varphi\equiv x=x$ and $\varphi'\equiv y=x$, then by the second schema:
$$\forall x\forall y(x=y\rightarrow(x=x\rightarrow y=x)).$$
It's pretty tempting to proceed as follows:
$$\forall x\forall y(x=y\rightarrow(\top\rightarrow y=x))$$
$$\forall x\forall y(x=y\rightarrow y=x).$$
My doubt however is, is it wrong to assume that the formula $x=x$ is always true, even when all occurences of $x$ are unbound? Does the universal quantification shown in the first axiom make a difference?

REPLY [1 votes]: is it wrong to assume [in the proof of simmetry of equality] that the formula $x=x$ is always true?

No, it works.
More detailed proof :
1) $\vdash \forall x (x=x)$ --- axiom 1
2) $\vdash ∀x∀y(x=y → (x=x → y=x))$ --- from axiom-schema 2 : $∀x∀y(x=y → (\phi[z/x] → \phi[z/y]))$, where $\phi(z) := (z=x)$
3) $x=y$ --- assumed [a]
4) $x=x$ --- from 1) by $\forall$-elim (i.e. Universal Instantiation)
5) $x=y → (x=x → y=x)$ --- from 2) by $\forall$-elim
6) $(x=x → y=x)$ --- from 3) and 5) by $\to$-elim (aka Modus Ponens)
7) $y=x$ --- from 4) and 6)
8) $(x=y \to y=x)$ --- from 3) and 7) by $\to$-intro (aka Conditional Proof), discharging [a]

$\vdash ∀x∀y(x=y \to y=x)$ --- from 8) by $\forall$-intro (i.e. Universal generalization) twice.


TITLE: Are cyclic quadrilaterals halved by this polygonal chain?
QUESTION [2 upvotes]: I tried to help one of my friends with her exercise, who is actually younger than me, but I can't figure it out myself. The problem is the following:
We have a cyclic quadrilateral, whose diagonals are perpendicular. Is the ABCO quadrilateral's area half the whole? This can also be proved by showing that the areo of the ABCO and AOCD is the same.

After some heavy thinking I am currently at the following state:

I now that the whole's area is $\frac{x*y}{2}$, which must be equal to the following, kind of ugly expression:
$$2*(\frac{x*\sqrt{r^2-\frac{x^2}{4}}}{2}+\frac{x*cos(45°+\frac12arccos(\frac{y}{2r})*cos(45°-\frac12arccos(\frac{y}{2r}))*r}{2})$$
Now I'm sure it can be solved (and by replacing the variables I get a near-correct result to the area according to geogebra), but I don't think that it would be the most elegant solution, there might be some shorter ways to do it.

REPLY [1 votes]: The area of a cyclic orthodiagonal quadrilateral is given by $\frac{1}{2}(ac + bd)$, where $a,b,c,d$ are the side lengths.
On the other hand, the altitudes from $O$ to each side have length equal to half of the opposite side. That means that the area of quadrilateral $ABCO$ is given by $\frac{1}{2}a(\frac{c}{2}) + \frac{1}{2}b(\frac{d}{2}) = \frac{1}{4}(ac + bd)$.


TITLE: Finding a minimum of a function, measuring the sum of the squares of distance from some points of the $\mathbb{R}^n$
QUESTION [1 upvotes]: Given are a finite number of points $a_1, ..., a_m \in \mathbb{R}^n$. Consider the sum of the squares of distance:
$$f(x) = \sum_{k=1}^m ||x-a_k||^2, x \in \mathbb{R}^n$$
with $||.||$ being the Euclidian norm.
I first want to prove that $f$ has one but only one local minimum $x_0 \in \mathbb{R}^n$, and want to find it.
Finally, I want to prove that $x_0$ is also a global maximum.
My approach so far was to try to differentiate $f$. For $x = (x_1, ..., x_n), a_k = (a_{1k}, ..., a_{nk}) \in \mathbb{R}^n$, we would get:
$$f(x) = \sum_{k=1}^m ||x-a_k||^2 = \sum_{k=1}^m \sum_{j=1}^n (x_j - a_{jk})^2 = \sum_{k=1}^m \sum_{j=1}^n (x_j^2 - 2x_j a_{jk} + a_{jk}^2) \\ = (x_1^2 - 2 x_1 a_{11} + a_{11}^2) + ... + (x_n^2 - 2 x_1 a_{n1} + a_{n1}^2) + ... + (x_1^2 - 2 x_1 a_{1m} + a_{1m}^2) + ... + (x_n^2 - 2 x_1 a_{nm} + a_{nm}^2)$$
and therefore, I would get that
$$\nabla f(x) = \pmatrix{2x_1 - 2a_{11} + ... + 2x_1 - 2 a_{1m} \\ .. \\ 2x_n - 2a_{n1} + ... + 2x_n - 2 a_{nm}} = \pmatrix{2m x_1 - \sum_{k=1}^m 2a_{1k} \\ ... \\ 2m x_n - \sum_{k=1}^m 2 a_{nk}}$$
and therefore, it would appear that $x_0 = (\sum_{k=1}^m a_{1k}, ..., \sum_{k=1}^m a_{nk})$ would be a candidate for a local minimum because that's where $f'(x) = 0$ (and it would be the only candidate, so there can only be one). Would this be correct so far?
To show that it is a local minimum, I would either need to find a neighborhood $U_{x_0} \subseteq \mathbb{R}^n$ of $x_0$, so that $\forall x \in U_{x_0}$, we have that $f(x) ≥ f(x_0)$, or I would need to show that the Hesse matrix $H_f(x_0)$ is positive definite, would I?
I've skipped this for now, because I've been thinking more about how to show that $x_0$ is also a global maximum. Would it be sufficient to show that $lim_{||x|| \to \infty} f(x) = \infty$? Intuitively, it's obvious that that's the case, because the further we move away from $x_0$, the bigger the squares of distance described by this function "will grow". So if we just "move away far enough" from $x_0$, we would know that $f(x)$ would definitely become larger than $f(x_0)$, hence if $x_0$ would not be a global minimum, there would need to be another minimum, which we know there isn't.
I don't really know how to mathematically justify that, so if anyone could come up with a better solution for the second part, it would be appreciated.

REPLY [1 votes]: Since you are dealing with a moment of inertia, the claim just follows from the Huygens-Steiner/parallel axis theorem: the absolute minimum is attained by the centroid of $\{a_1,\ldots,a_m\}$.
On the other hand, your argument is perfectly fine, but you do not need to compute any Hessian matrix, since the moment of inertia is a convex function as a sum of convex functions, hence it may have only a global minimum.


TITLE: Solution of ODE is also lip-continuous, if ODE is lip-continuous?
QUESTION [1 upvotes]: Let G$ \subset \Bbb R \times \Bbb R^N$ and $f:G \to \Bbb R^N $continuous. Let $f$ be local lipschitz-continuous  in G.
Show that the solution of the ODE $x'=f(t,x), x(\tau)=\xi$, which is $(t,\tau,\xi) \mapsto x(t,\tau,\xi)$ is local lipschitz-continuous in $\tau$, using Grönwall's inequality.

My attempt:
We can apply Picard-Lindelöf and know that there exists exact one solution to this ODE.
We know that $x'$ has got a solution then:
$x= \xi + \int_\tau^t f(s,x(s))ds  =\int_\tau^t f[s,x(s)- f(s,\xi)+ f(s,\xi)]ds $
Because $f$ is locally lipschitz, $f(s,\xi)$ is bounded on G.
Let $h:=max|f(t,\xi)|$ and $|x(t)-\xi|<\epsilon \forall t\in G$ ,then:
$|x-\xi|< \int_\tau^t f|(s,x(s))- f(s,\xi)|+ |f(s,\xi)|ds$ < $L \int_\tau^t[|x(s)-\xi|+h]ds$ <$\int_\tau^t(L\epsilon+h) ds$ <$(t-\tau)(L\epsilon+h)$ < $)<$$ c(L\epsilon+h)$
choose c= $(L\epsilon+h)^{-1}$ and I don't know how to go on or whether it is OK or not....any hint how to begin maybe or to continue ?
Thanks in advance.

REPLY [0 votes]: I think your interpretation of the task description might be off. You are to show
$$|x(t;τ_1,ξ)-x(t;τ_2,ξ)|\le c(t)·|τ_1-τ_2|,$$
 where $x(t;τ_k,ξ)$ are the solutions with initial conditions $x(τ_k;τ_k,ξ)=ξ$.
Using Grönwall, one finds the standard estimate
$$
|x(t;τ_1,ξ)-x(t;τ_2,ξ)|\le e^{L|t-τ_2|}·|x(τ_2;τ_1,ξ)-ξ|
$$
Thus it remains to find a bound for $|x(τ_2;τ_1,ξ)-ξ|$. But that is just
$$
|x(τ_2;τ_1,ξ)-ξ|\le \int_{τ_1}^{τ_2}|f(s,x(s;τ_1,ξ))|\,ds\le \sup|f|·|τ_1-τ_2|
$$
where the supremum is over some bounded subset of $G$.


TITLE: Is there a math concept or terminology for complex numbers with identical imaginary part and opposite real part?
QUESTION [7 upvotes]: As we know, complex conjugation is the reflection symmetry of a complex with respect to the real axis. Is there a standard terminology for a pair of complex numbers which have identical imaginary parts and opposite real parts? If not, why such kinds of complex numbers are not as important as conjugate complex so that there is even no special math concept for them?

REPLY [0 votes]: For non-zero complex $z = re^{i\theta}, ~\overline{z} = re^{-i\theta}.$
For non-zero complex $z = x + iy = re^{i\theta}$,
$w = -x + iy$ can be similarly expressed as  $re^{i(\pi - \theta)} = re^{-i\theta} \times e^{i\pi} = -\overline{z}.$
Alternatively, $(x - iy) \times -1 = (-x + iy).$


TITLE: Probability Game quesiton regarding Biassed coin
QUESTION [0 upvotes]: We're given an unfair coin with the following probability:
H-2/5
T-3/5
Two players play a game where each of them chooses a sequence of 3 tosses of this unfair coin,then the coin is tossed again and again until one of the sequences emerges.
Player A chooses the sequence TTT,is there a sequence Player B can choose such that his probability to win will be greater than half?
TTT seems tempting but H must have accurred before such a sequence completes , but i have no idea how to write it mathematically.

REPLY [0 votes]: Claim: If any of the first three rolls is H, then HTT beats TTT. Hence in the HTT vs. TTT game, TTT wins with probability $(3/5)^3=27/125$ and HTT wins with probability $98/125$.
proof: Suppose at least one of the first three rolls is H, and for contradiction, suppose that TTT appears before HTT. Choose the first occurrence of TTT. By assumption these are not the first three flips of the game. The flip immediately preceding this occurrence of TTT can't be T by choice of "first occurrence" nor can it be H since then HTT would have won. Contradiction.
So TTT only wins if the first three rolls are all T's, which happens 27/125 of the time.
I'm not sure, but it may well be that B can always pick a string to beat A (on average) if she is allowed to choose after A and knows what A chose.


TITLE: p-adic number for polynomial
QUESTION [1 upvotes]: I have three polynomials:
$$f=x^5+x^4+4x^3+3x^2+3x$$
$$g=x^5+4x^3+2x^2+3x+6$$
$$p=x^2+3$$
Question: what is $v_p(fg)$?
First, I have multiplied f and g:
$h :=f \cdot g = x^{10}+x^9+8x^8+9x^7+24x^6+29x^5+36x^4+39x^3+27x^2+18x $
Then I have divided that $h$ with $x^2+3$ to get a factor to know how often $h$ contains $x^2+3 $:
$(x^2+3) \cdot (x^6+x^5+2x^4+3x^3+3x^2+2x)$
When I divide $x^6+x^5+2x^4+3x^3+3x^2+2x$ again by $x^2+3$ then I get a rest:
$(x^4+x^3-x^2+6) \cdot (x^2+3) + 2x-18$
Does that mean that $h$ contains $x^2+3$ only once and
$v_p(f \cdot g)=1$?
Is that the correct way to find the p-adic number? Or is there a better conventional one?
I appreciate every hint.

REPLY [2 votes]: Because $x^2+3$ is irreducible in $\Bbb{Z}[x]$ (Eisenstein) it is the minimal polynomial of $i\sqrt3$. You can then check that

$f(i\sqrt3)=0$, so $f(x)$ must be divisible by $x^2+3$. A long division shows that $f(x)/(x^2+3)=x+x^2+x^3$, and you can check this is not a multiple of $x^2+3$.
$g(i\sqrt3)=0$, so $g(x)$ is also divisible by $x^2+3$. A long division gives a quotient that I leave to you.

Anyway, looks like $fg$ should be divisible by $(x^2+3)^2$, so you have made a mistake somewhere. As Hagen pointed out, we have for all discrete valuations
$\nu_p$ the formula $\nu_p(fg)=\nu_p(f)+\nu_p(g)$ that comes in handy.


TITLE: How to write truth table?
QUESTION [0 upvotes]: our teacher gave us two expressions

(A+B')(A'+B')

and

(p+q')->(p^q)

How can I set up a truth table for these.
I couldn't figure out the first problem, but on the second problem i have this:

But this is just what was copied from the book and I don't understand it. On the right side what are the 0 and 1 values representing. Is it representing that the whole statement is true or false?

REPLY [1 votes]: So '+' means "or" ($\vee$) and '^' means "and" ($\wedge$) (btw, in latex, these two symbols are \vee and \wedge, respectively).  You make the table of every piece of the equation:
------------------------------------------------------------
| p | q | !q | p or !q | p and q | (p or !q) --> (p and q) |
------------------------------------------------------------
| T | T |  F |    T    |    T    |            T            |
| T | F |  T |    T    |    F    |            F            |
| F | T |  F |    F    |    F    |            T            |
| F | F |  T |    T    |    F    |            F            |
------------------------------------------------------------

Remember, $p \rightarrow q$ is true when either $p$ is false or both $p$ and $q$ are true.  So this means the expression $(p \vee \neg q) \rightarrow (p \wedge q)$ is only true when either both $p$ and $q$ are true or when $p$ is false and $q$ is true (which makes the hypothesis of the implication false).


TITLE: Prove that the following sequence is constant
QUESTION [1 upvotes]: Suppose that ($S_n$) converges and has only finitely many distinct terms . Show that $S_n$ is constant for large $n$
What I have tried
Let $M$ the set of distinct elements of the sequence ($S_n$)  $M$={$t_1,t_2,....,t_r$} let $m$=min{$|t_i-t_j| $: $i$ is not equal to $j$} due to ($S_n$) is convergent for any positive epsilon there is $N$ such that $|S_n-S|<$ epsilon whenever $n>N$ let epsilon = m so there is $N_m$ Such that $|S_n-S|<$ $m$ whenever $n>N_m$  this satisfies if $|S_n-S|=0$ so $S_n=S$ whenever $n>N_m$

REPLY [1 votes]: Let $s=\lim_{n\rightarrow\infty} S_n$. Since  $S_n$ has only finitely many distinct terms there are infinitely many terms of $S_n$ that have the same value let $t$. Consider the subsequence $\{S_{k_n}\}_n$ that consists of all these terms i.e. $S_{n_k}=t=constant$. Then
$$s=\lim_{n\rightarrow\infty} S_n=\lim_{n\rightarrow\infty} S_{k_n}=t$$
since for a convergent sequence all subsequences converge to the same limit.
Now, by the definition of the limit we have that for large $n$ infinitely many terms of $S_n$ lie in an $\varepsilon$-ball around the value $t$ (where we choose some $\varepsilon >0$).
Morever, since $S_n$ attains finite distinct values for $\varepsilon >0$ small enough and large $n$ the $\varepsilon$-ball around the value $t$ doesn't contain any other of the finitely many values of the terms of $S_n$, i.e. for large $n$ the sequence is constant and equal to $t$.