Understanding the difference between a Flat, a locally flat and an Euclidean space Suppose a Riemannian manifold is such that the metric tensor in a coordinate system is given by

$$g_{ij}=\delta_{ij}$$
so that $$ds^2=g_{ij}dx^i dx^j=(dx^1)^2+(dx^2)^2+(dx^3)^2$$

(i) Is this space called (a) flat or locally flat, (b) Euclidean or  locally Euclidean?

(ii) Can we think of a simple space which is locally flat but not locally Euclidean or vice-versa?

(iii) What is the difference between a flat space and an Euclidean space?

(iv) What is a space called, if it has a metric $g_{ij}=C_i\delta_{ij}$ (where $C_i$ are some constants independent of the coordinates)?

Not-too-technical answer will be helpful because my understanding of differential geometry and manifolds is limited.

I think this question deserves an answer here in physics SE, since these notions are very common in Relativity.

For a manifold $M$ equipped with a metric (either Euclidean or Lorentzian) $g$, locally flat means that every point $p\in M$ admits an opens set $U \ni p$ endowed with coordinates $$\psi : U \ni q \mapsto (x^1(q),\ldots, x^n(q)) \in \psi(U) \subset \mathbb R^n$$
such that the metric in these coordinates takes the constant canonical form
$$g_{ab}(q) = \delta_{ab}\quad \mbox{Riemannian case}\:,$$
or
$$g_{ab}(q) = \eta_{ab}\quad \mbox{Lorentzian case}\:.$$
The point is that there is no guarantee that there is such a $U$ which covers the whole manifold. For this reason we use the adverb locally in front of flat.
An example is a two dimensional cylinder in $\mathbb R^3$ equipped with the metric induced by the standard metric on $\mathbb R^3$.

For a manifold $M$ equipped with a metric (either Euclidean or Lorentzian) $g$, globally flat means that there is a global coordinate system $$\psi : M \ni q \mapsto (x^1(q),\ldots, x^n(q)) \in \psi(M) \subset \mathbb R^n$$
such that the metric in these coordinates takes the constant canonical form
$$g_{ab}(q) = \delta_{ab}\quad \mbox{Euclidean case}\:,$$
or
$$g_{ab}(q) = \eta_{ab}\quad \mbox{Lorentzian case}\:.$$
In this case $(M,g)$ is isometrically identified with an open portion (possibly the whole space) of $\mathbb R^n$ equipped with the standard (Euclidean or Lorentzian) metric.

In view of the definitions above, the answer to your question (i) depends on the extension of your coordinate system. If it covers the whole manifold we have a globally flat manifold. If it is not the case, we can only say that a region of the manifold, the one covered by the coordinates, is flat.

Flat space and Euclidean space have more or less the same meaning. They usually indicate Minkowski spacetime (i.e. a spacetime isometrically isomorphic  to $\mathbb R^n$ equipped with the standard Minkowsky metric $\eta_{ab}$)  or $\mathbb R^n$ equipped with the standard Euclidean metric $\delta_{ab}$. However are a bit vague terms whose meaning (if global or local) should be understood from the context.

Regarding your last question. If all $C_i$ are positive, the metric can be recast into the standard form $\delta_{ij}$ simply rescaling (changing) the coordinates with a factor $1/\sqrt{C_i}$. If some constant is negative, with a similar procedure the metric can be reduced into a constant form $h_i \delta_{ij}$ where $h_i = \pm 1$, which is Lorentzian only if all $h_i$ are $+1$ but one (or all $h_i$ are $-1$ but one depending on the adopted convention). It is impossible that a $C_i$ vanishes because it would imply $det [g_{ij}]=0$ which is not admitted by definition of (non-degenerate) metric.

ADDENDUM. An apparently related question concerns the so called locally flat coordinates around a given point. This is an independent issue. These coordinates are also called Riemannian normal coordinates or Gaussian normal coordinates. Are coordinates $x^1,\ldots, x^n$ defined in a neighborhood of a point $p\in M$ such that exactly at $p$ the components of the metric have their canonical form (e.g. $g_{ab}(p)=\delta_{ab}$ or $g_{ab}(p)=\eta_{ab}$ depending on the nature of the metric) and  $\frac{\partial g_{ab}}{\partial x^c}|_p =0$. It is possible to prove that every manifold equipped with a smooth metric admits such a coordinate system for every given point $p\in M$.

It is also possible to extend the definition referring to a geodesic $\gamma\subset M$ instead of a point $p$: Exactly on  $\gamma$ the components of the metric have their canonical form (e.g. $g_{ab}(\gamma)=\delta_{ab}$ or $g_{ab}(\gamma)=\eta_{ab}$ depending on the nature of the metric) and  $\frac{\partial g_{ab}}{\partial x^c}|_\gamma =0$. This form gives rise to a very precise  mathematical description of Einstein's equivalence principle in GR when $\gamma$ is a timelike geodesic.

Once you have $ds^2=(dx^1)^2+(dx^2)^2+(dx^3)^2$, Pythagorean theorem holds locally, you get triangles with sum of angles = $\pi$ and you are locally homeomorphic to an Euclidean space. This may not hold globally, as for example you could very well be on a cylinder, which is not an Euclidian space. The same holds if $g_{ij}=C_i\delta_{ij}$ for positive constants $C_i$, as you can interpret it as an anisotropic scaling. I am not aware about a fundamental difference between locally flat and locally Euclidean, apart local flatness referring to embedded manifolds whereas locally Euclidean does not involve embedding.


How would I go about finding the roots of $(e^x-1)-k\arctan(x) = 0$? I have the equation $$(e^x-1)-k\arctan(x) = 0$$ where $0<k \leq \frac 2\pi$ and I was wondering how I would go about starting to determine the amount of real roots of this equation. So far I have just manipulated the equation to get different equations of $x$, however I'm unsure what to do with them.
Current equations for $x$  are  $x = \ln(k\arctan(x)-1)$ and $x = \frac{\tan(e^x-1)}{k}$

Of course $x=0$ is always a solution.  Otherwise, write the equation as $$k = \frac{e^x-1}{\arctan(x)}$$
Call the right side $f(x)$.  The singularity at $x=0$ is removable, with $\lim_{x \to 0} f(x) = 1$.  We also have $\lim_{x \to -\infty} f(x) = 2/\pi$ and $\lim_{x \to +\infty} f(x) = +\infty$.
It appears that $f(x)$ is increasing.  If so, for $2/\pi < k < 1$ and $1 < k < \infty$ there are two real roots ($x=0$ and the root of $f(x)=k$), otherwise there is only $x=0$.

Let $f(x)=e^x-1-k\arctan(x)$.  We have $f(0)=0.$  If $k=0$, obviously $x=0$ is the only solution.
If $k\neq0$, then $f'(x)=e^x-\frac k{1+x^2},$ so that $$f'(x)=0\iff (1+x^2)e^x=k.$$  Since $(1+x^2)e^x$ is increasing, goes to $0$ at $-\infty$ and goes to $\infty$ at $\infty$ we see that $f'$ has exactly one real zero, say $f'(x_0) = 0$.  We see that $f$ decreases on $(-\infty, x_0)$ and increases on $(x_0, \infty)$, so that $f$ attains its minimum at $x_0$.
Since we know that $f(0)=0$, it must be that $x_0<0$ and $x=0$ is the only solution.


Help with induction using divisibility. Need some help with this question for induction using divisibility: $8*19^n-2*3^{2n+2}$ is divisible by 10 for any positive integer.
What I have so far is proving the first value and $P_k$ and $P_{k+1}$

$P_1$ = $8*19^1-2*3^{2+2}$=-10; $P_1$ is true.

$P_k$ = $8*19^k-2*3^{2k+2}$= 10A

$P_{k+1}$ = $8*19^{k+1}-2*3^{2k+4}$ = 10B

I've just found myself stuck on the proof starting with:

$8*19^{k+1}-2*3^{2k+4}$=

Thanks for any help. If I could get an answer in the format of $P_k$ and $P_{k+1}$ that would greatly appreciated.

In fact, it works for non-negative integers $n$. Let $u_n:=8\times 19^n-2\times 9^{n+1}$ so $u_0=-10$ and $u_{k+1}-9u_k=80\times 19^k$, so $10|u_0$ and $10|u_k\implies 10|u_{k+1}$.

Let $P(n)$ be the statement that $10 \mid 8 \cdot 19^n - 2 \cdot 3^{2n + 2}$.

If we wish to establish that the statement holds for all nonnegative integers, we have to verify that $P(0)$ holds since that will be our base case.

Since $8 \cdot 19^0 - 2 \cdot 3^2 = 8 - 18 = -10 = 10 \cdot (-1)$, $P(0)$ holds.

If we wish to establish that the statement holds for all positive integers, we have to verify that $P(1)$ holds since that will be our base case.

Since $8 \cdot 19^1 - 2 \cdot 3^4 = 8 \cdot 19 - 2 \cdot 81 = 152 - 162 = -10 = 10 \cdot (-1)$, $P(1)$ holds.

Assume $P(k)$ holds for some positive integer $k$.  Then $10 \mid 8 \cdot 19^k - 2 \cdot 3^{2k + 2}$, so there exists $m \in \mathbb{Z}$ such that $8 \cdot 19^k - 2 \cdot 3^{2k + 2} = 10m$.

Let $n = k + 1$.  Then
\begin{align*}
8 \cdot 19^n - 2 \cdot 3^{2n + 2} & = 8 \cdot 19^{k + 1} - 2 \cdot 3^{2(k + 1) + 2}\\
& = 19 \cdot 8 \cdot 19^k - 2 \cdot 3^{2k + 4}\\
& = 19 \cdot 8 \cdot 19^k - 9 \cdot 2 \cdot 3^{2k + 2}\\
& = (10 + 9) \cdot 8 \cdot 19^k - 9 \cdot 2 \cdot 3^{2k + 2}\\
& = 10 \cdot 8 \cdot 19^k + 9(8 \cdot 19^k - 2 \cdot 3^{2k + 2})\\
& = 10 \cdot 8 \cdot 19^k + 9 \cdot 10m && \text{by the induction hypothesis}\\
& = 10(8 \cdot 19^k + 9m)
\end{align*}
Thus, if $10 \mid 8 \cdot 19^k - 2 \cdot 3^{2k + 2}$, $10 \mid 8 \cdot 19^{k + 1} - 2 \cdot 3^{2(k + 1) + 2}$.  Hence, $P(k) \implies P(k + 1)$.

Since $P(1)$ holds and $P(k) \implies P(k + 1)$ for each $k \geq 1$, $P(n)$ holds for each positive integer $n$.  The same steps that establish $P(k) \implies P(k + 1)$ also apply when $k$ is a nonnegative integer.

In fact, since $P(0)$ holds, $P(1)$ holds, and $P(k) \implies P(k + 1)$ for each $k \geq 1$, $P(n)$ holds for each nonnegative integer $n$.

Had we wished to prove that $P(n)$ holds for each nonnegative integer $n$, we could have skipped the step of establishing that $P(1)$ holds and instead assumed that $P(k)$ holds for some nonnegative integer $k$.


An Exercise of Finite Groups Prove that the group $F(2,5)$ given by $$\left<a,b,c,d,f \mid ab=c, bc=d, cd=f, df=a, fa=b\right>$$ is a finite cyclic group.

Here is brief description of a proof that $G = \langle a \rangle$ and hence abelian. This was done by hand, not by computer, and is easy if you know how to do coset enumeration. I am going to rename your generate $f$ as $e$ (do you not like $e$ for some reason?).

Let $H$ be the subgroup $\langle a \rangle$ of $G$ and label the cosets $H$, $Hb$, and $Hd$ 1,2, and 3. Then we get the following chain of implications.

1a=1 by definition.
1b=2 by definition.
1d=3 by definition.
1c=2 from 1ab=1c.
2c=3 from 1bc=1d.
3e=1 from 1de=1a.
3b=1 from 3ea=3b.
3d=2 from 3bc=3d.
2e=2 from 2cd=2e.
3a=2 from 3de=3a.
1e=3 from 1ea=1b.
2d=3 from 1cd=1e.

So we have $1d=2d=3$, so $1=2$, and hence $b \in H = \langle a \rangle$, and it now follows easily that $G=\langle a \rangle$.

Hint: Observe that calling the elements $a_i,\;\;i=1,..,5$, then you have $a_ia_{i+1}=a_{i+2}$, and it goes around it when it reaches the end: try to find the unit of the group $1_F$, and then try to prove its isomorphic to some $\mathbb{Z}_n$


The number of scalar additions required to compute $P(QR)$ Let $P$, $Q$, $R$ be matrices of order $3\times5, 5\times7$ and $7\times3$ respectively. What is the number of scalar additions required to compute $P(QR)$?
Do we have any formula to compute this? If we had to square a square matrix of order $n\times n$ how will the results change? Thanks...

Answer = $ 126 $. To get every number in the matrix $QR$, we need $6$ additions and there are $15$ numbers like that. similar calculation for the next step gives $4$ additions repeated $9$ times. So , we need $ 6*15 + 9*4 = 126 $ additions.

Just an observation is  that .. the dimension of the product Matrix P(QR) is $9(3 \times 3)$ and 9 is dividing 126 ...so from this way can we find the number of scalar addition of the matrix.


Convergence of the sequence $\frac{1}{e^k \sin{k}}$ Does the sequence $\frac{1}{e^k \sin{k}}$ converge?

If $\sin{k}$ acts as a random variable (taking on values in $(-1, 1)$), then it seems like we should be able to prove that the sequence converges with high probability. I wonder if it can be decided absolutely.

It converges to $0$, in fact $\frac{1}{k^7\sin{k}}$ already converges to $0$, see Theorem 2 here. This theorem gives a nice characterization of the irrationality measure of $\pi$ as the borderline number $\mu$ such that $\frac{1}{k^{u-1}\sin{k}}$ converges to $0$ for $u>\mu$, and diverges for $u<\mu$. So $\frac{1}{k^7\sin{k}}$ converges because $\mu$ is known to be less than $8$, and $\frac{1}{k^{1/2}\sin{k}}$ diverges because it has to be at least $2$. Whether $\frac{1}{k^2\sin{k}}$ converges is an open question, but the conventional wisdom is that $\mu=2$.

Interestingly enough, the sequence $\frac{1}{k^{u-1}\xi_k}$, where $\xi_k$ are independent random variables uniformly distributed on $[-1,1]$ converges to $0$ almost surely if and only if $\sum\frac{1}{k^{u-1}}<\infty$. So $\sin{k}$ being a "random variable" uniformly distributed on $[-1,1]$ is in fact equivalent to $\mu=2$.

Convergence of similar sequences $\frac{\tan k}{k^{u-1}}$ is analysed here, also implicitly using the irrationality measure of $\pi$.

NOT A PROOF. But here are my thoughts. I don't think it will converge. As k continues to get larger, it will hit closer and closer multiples of pi. For example, k=3, 31, 314, 3141, 31415, ... etc. As these values of k occur, sin(k) will get closer and closer to zero. Since sin(k) is in the denominator, the effect will cause the $k^{th}$ sequence element to get bumpy, which happens when one divides by zero (or numbers close to zero). Yes, there is the $e^{k}$ in the denominator that makes the sequence appear to converge quickly, but again those approximate multiples of pi become more accurate as $k \rightarrow \infty$.

This picture shows what happens at $x=\pi, 2\pi,...$ , and what will happen as the values of k get closer to a multiple of $\pi$.


why does the quotient become messy when we switch the terms of the divisor when using long division? If we were to use long divison to divide $x^2 - y^2$ by $x + y$, the long division easily gives $x-y$. But if I were to use long division to divide $x^2 - y^2$ by $y + x$ instead, the quotient becomes lengthy and fruitless. Forgive me if I'm fundamentally flawed. I don't seem to understand this at all.

Everything will be turned around, if you are dividing by $y+x$ then just turn the equation around to read $-y^2+x^2$ and it will come out nicely as you say. However, it does not matter the order.
$$\frac{x^2-y^2}{y+x}=-y+\frac{x^2+yx}{y+x}=-y+x$$

As you can see, you just have to be careful!:)

Dividing $x^2-y^2$ by $y+x$ gives:$$\frac{x^2}{y}-y-\frac{x^3}{y^2}+x+\frac{x^4}{y^3}-\frac{x^2}{y}-\frac{x^5}{y^4}+\frac{x^3}{y^2}+\frac{x^6}{y^5}-\frac{x^4}{y^3}-\frac{x^7}{y^6}+\frac{x^5}{y^4}+\frac{x^8}{y^7}-\frac{x^6}{y^5}-\cdots$$  The pattern of signs is + - - +, and every fractional term cancels with the fifth term following, leaving $-y + x$. So going at it this way is lengthy but not fruitless. It seems the order does not affect the result, only the ease of attaining it, at least in this example.


Show that a p-group has a faithful irreducible representation over $\mathbb{C}$ if it has a cyclic center A p-group is a group of order $p^d$ where p is a prime.

If the center has order $p^m$ (since its order must divide the order of the group) then we have a one dimensional faithful irreducible representation of the center which would map a generator of the center to $e^{2\pi i/m}$. Could we then induce a representation on the whole group? If so, how do we know this is faithful and irreducible? If not, how else could we prove this?

The induced representation is faithful, but not necessarily irreducible. But, since the centre of the $p$-group $P$ is cyclic, the unique subgroup $K$ of $Z(P)$ with $|K|=p$ is contained in every nontrivial normal subgroup of $P$. Since the induced representation is faithful, at least one of its irreducible constituents does not have $K$ in its kernel, and then that consituent must be faithful.

T(A)T(B)=T(AB)
If all the matrics are distinct than T is called group and there are one to one correspondance between matrix's and group element of G .
So there is a isomerism bet. G and T .if isomerism is perfect T and G thn this type of representation is called faithfully representation of group G.


How to explain this paradox involving coin-tosses? I do this experiment:
I flip fair coin, if it comes heads on first toss I win.
If it comes tails, I flip it two times more and if both heads I win.
Else, I flip it 3 more times, if it comes heads all three I win.
On the n'th turn I flip it n times, and if I get n heads I win and quit the game.

Before I start, I calculate probability I win at some point: 1/2+1/2^2+1/2^3... = 1.
So I am guaranteed to win this game always.

However I started to play, and it came tails first toss, now I calculate probability I win 1/2^2+1/2^3+1/2^4...=1/2.

Before I start I was guaranteed to win, but now only 50% chance I will win? What went wrong with the mathematical reasoning?

You are wrong about your probability of winning at the beginning.

Let $p_n$ be the probability that you have not won by stage $n$.

Then the probability that you have will not have won at stage $n+1$ is $p_n(1-(\frac{1}{2})^{n+1})$.

So the probability that you never win is $\prod_{n=1}^\infty (1-(\frac{1}{2})^n)$.  This is not zero.

Specifically, this is $\phi(\frac{1}{2})$ where $\phi$ is the Euler function.

In particular, $$\log(\phi(\frac{1}{2}))=-\sum_{n=1}^\infty \frac{1}{n}\frac{1}{2^n-1}$$

which converges.

What went wrong with your reasoning?

"Before I start..." is not the same as "now (i.e. AFTER you have started)"!


How exactly is the probability of at least one event happening dependent on the probability of all events happening? Say we have $P(A) = 0.60,\, P(B) = 0.50$ .

Normally to find the probability of at least one happening, we find the probability of neither of them happening:

$$P(A^c \cap B^c) = 0.40 \times 0.50 = 0.20$$

and then subtract it from $1$ ( getting $0.80$). I know that this is incorrect because we are also given that $P(A \cap B) = 0.35$, thus $A,B$ are not independent. How would one go about finding the probability of at least one occurring in this case?

The event $C=$"at least one from A or B happened" is the same as the event $C=A\cup B$.

So.. just use one of the most basic results in probabilities: $$P(A\cup B)=P(A)+P(B)-P(A\cap B)=0.5+0.6-0.35=0.75.$$

Hint: The probability of A happening and B not happening is $0.6-0.35=0.25$.


Are Mathematicians Pluralists About Math? This has been rangling around my head for awhile. With the death of Hilbert's program via Gödel's Incompleteness Theorems (and the prior damage done to Logicism via Russell's Paradox), have mathematicians become pluralists, of some sort, about their discipline?

In 'Varieties of Logic', Stewart Shapiro says,  "Pluralism about a given subject, such as truth, logic, ethics or etiquette, is the view that different accounts of the subject are equally correct, or equally good, or equally legitimate, or perhaps even true."

I dont like the truth bit, but that aside, to make a comparison to geometry, it seems as if with the advent of Non-Euclidean geometries, we couldn't lay down a determinate answer to some questions since the answer depends on the geometry being assumed (Parallel Postulate, for example). As a non-mathematician, it seems as if to mathematicians it's not so much that one or another mathematical system is "true" because the question of which is true is some kind of mistake in the way the above question about the Parallel Postulate is.

Whichever mathematical system we assume does not seem to be inherently off the table because what matters is if the structure is interesting in what it allows one to prove (or fail to prove). There's a notion of interestingness that seems to be at play: triviality proves everything so it gets the axe, paraconsistency slides in for avoiding that.

The above, in addition to a sort of practical pluralism (e.g. logicians or mathematicians on occasion apply particular formalisms to particular domains), does this suggest some kind of mathematical pluralism (or even logical pluralism) is implicitly accepted by mathematicians? Or would they, when pressed, revert to the standard maths?

I couldn't find any other questions about this or polls (would be interesting to see one). But as someone who just reads about maths and logic for fun, it interests me.

I can't really speak for mathematicians in general, but from what I've observed I wouldn't say we ascribe to pluralism. Many mathematicians - those not directly involved in logic - don't even think much about Incompleteness, because the undecidable statements aren't relevant to their field.

Among logicians, including myself, the prevailing opinion seems to be this: there's some sort of "overarching" universe, inside which all the possible mathematical universes are situated. So it's not that (for example) it's "equally correct" to say that the Continuum Hypothesis (a famous example of an independent statement in set theory) is true and that the Continuum Hypothesis is false. It's that it is correct to say that in some universes the Continuum Hypothesis is true and in others it's false.

Another way of thinking about it: Euclidean geometry is correct on an infinite plane. Spherical geometry is correct on the surface of a sphere. We don't say either is the "correct" set of axioms; we just say each applies to a different space. That's not pluralism, that's just limiting the scope of the axioms - instead of talking about everything, they're talking about their own respective situations.

Now, some logicians have firm ideas about what is and isn't true in the overarching universe; for example, I read once that Kurt Godel firmly believed that $2^{\aleph_0} = \aleph_4$, which would be one way for the Continuum Hypothesis to be false. But most of them seem to just not really care - they only care what's going on inside all those smaller universes.

Answering in a completely personal, psychological and somewhat emotive fashion:

After having worked with very productive researchers in signal processing and artificial intelligence, I saw that everyone has their own understanding about the mathematical objects they are using. Some thought in terms of methafors, subjective images, others in a more formal, proof/rational/logic way. Both types, and I am not trying to be exhaustive here, yielded great researchers in this practical but highly mathematically-suported area.

Going a little to the phylosophic side, people like Nietzsche and Jung have a very poignant view of "truth". Nietzsche claims that "God is dead" in a way that seems to be the same as "absolutism is dead". Jung says that truth is "Whatever works". Darwin says something similar. Einstein says everything is relative. He really means that: Nothing is able to exist, let alone be described, by only itself.

My point is that we are subject to our minds when we do maths. We have our own cognitive biases and everyone thinks of the "same" objects differently, although we are frequently still able to understand ourselves. Furthermore, it is virtually impossible for a mathematician to grasp every pertinent theory within his lifetime. Each one has its specific axioms, propositions based entirely on intuition. These intuitions allow us to handle specific problems the best way.

So yes, I think mathematics is completely plural these days. Use the theory that works best for you! The goal is to solve something specific, after all!


Well-ordering of sets of cardinal numbers Proposition For every cardinal number $m$ there is a definite next larger cardinal number.

This proposition is proved on page 136 of "Proofs from the Book" using the fact that any set of ordinal numbers is well-ordered. However the latter fact is presented without proof.

The reasoning looks kind of strange to me because it seems that we are proving the well-orderedness of any set of cardinal numbers by means of the same property for sets of ordinal numbers. (And I have a feeling that the proof for ordinals should be even harder than that of cardinals, but I must be wrong!)

I don't have any background in set theory or logic, but I was hoping someone could either direct me to a "non-technical" reference or perhaps share some insights on this. Thanks!

I would recommend one of two books for you to learn about the foundations of set theory,

Proofs and Fundamentals by Ethan D. Bloch
Topology by James B. Munkres


Is a set $U$ consisting of the single point $p$ open or closed? I'm guessing here that $U$ would have to be closed, especially since for example the proof of the theorem that the union of two closed sets is closed is also valid if one of the sets is $U$. Still, I'd like to make sure my approach is correct:

Since p is the single point in U, that means $\exists r>0, B_r(p)\subset U$ can never be true, so $p$ is not an interior point, which means it has to be a boundary point, which means since $p$ is the only point in $U$, $U$ contains all its boundary points which means $U$ is closed.

I assume you're in a general metric space $(X,d)$. Consider {x} as a subset of $X$, and consider a point $y \neq x $ in $X$ . What can you say about d(x,y) (is it larger than 0)?  If so, can you construct a ball $B(y,r)$, for all $y \neq x $ that does not intersect the set {$x $}? (Remember that the complement of a closed set is open.)

let (X,d) be a metric space. we show X-{p} is open. let x belong to X-{p} and define r=d(x,p) then B(x, r/2) is a subset of X-{p}. in actually we show that each point in X-{p} is interior and  complement of {p} is open.this means {p} is close.


The square roots of different primes are linearly independent over the field of rationals I need to find a way of proving that the square roots of a finite set
  of different primes are linearly independent over the field of
  rationals.

I've tried to solve the problem using elementary algebra
and also using the theory of field extensions, without success. To
prove linear independence of two primes is easy but then my problems
arise. I would be very thankful for an answer to this question.

Below is a simple proof from one of my old sci.math posts, followed by reviews of a few related papers.

Theorem $\ $  Let $\rm\,Q\,$ be a field with $2 \ne 0,\,$ and $\rm\ L = Q(S)\ $ be an extension of $\rm\,Q\,$ generated by $\rm\, n\,$  square roots  $\rm\ S = \{ \sqrt{a}, \sqrt{b},\ldots \}$ of $\rm\ a,b,\,\ldots \in  Q.\,$
If every nonempty subset of $\rm\,S\,$ has product $\rm\not\in Q\,$ then each successive
adjunction  $\rm\ Q(\sqrt{a}),\  Q(\sqrt{a},\sqrt{b}),\,\ldots$ doubles  degree over $\rm Q,\,$ so, in total, $\rm\, [L:Q]  = 2^n.\,$  Thus the $\rm 2^n$ subproducts of the product of $\rm\,S\, $ are a basis of $\rm\,L\,$ over $\rm\,Q.$

Proof $\ $ By induction on the tower height $\rm\,n =$ number of root adjunctions. The Lemma below implies $\rm\ [1, \sqrt{a}\,]\ [1, \sqrt{b}\,] = [1, \sqrt{a}, \sqrt{b}, \sqrt{ab}\,]\ $  is a $\rm\,Q$-vector space basis of $\rm\, Q(\sqrt{a}, \sqrt{b})\ $ iff $\ 1\ $ is the only basis element in $\rm\,Q.\,$
We lift this to $\rm\,  n > 2\,$ i.e. to $\, [1, \sqrt{a_1}\,]\ [1, \sqrt{a_2}\,]\cdots [1, \sqrt{a_n}\,]\,$ with $2^n$ elts.

$\rm n = 1\!:\ L = Q(\sqrt{a})\ $  so  $\rm\,[L:Q] = 2,\,$   since $\rm\,\sqrt{a}\not\in Q\,$ by hypothesis.

$\rm n > 1\!:\ L = K(\sqrt{a},\sqrt{b}),\,\ K\ $  of height  $\rm\,n\!-\!2.\,$  By induction   $\rm\,[K:Q]  =  2^{n-2} $ so we need only show $\rm\, [L:K] = 4,\,$ since then  $\rm\,[L:Q] = [L:K]\ [K:Q] = 4\cdot 2^{n-2}\! = 2^n.\,$ The lemma below shows $\rm\,[L:K] = 4\,$  if  $\rm\ r = \sqrt{a},\ \sqrt{b},\ \sqrt{a\,b}\ $  all $\rm\not\in K,\,$
true by induction on  $\rm\,K(r)\,$ of height $\rm\,n\!-\!1\,$ shows $\rm\,[K(r):K] = 2\,$ $\Rightarrow$ $\rm\,r\not\in K.\quad$   QED

Lemma $\rm\ \ [K(\sqrt{a},\sqrt{b}) : K] = 4\ $ if  $\rm\ \sqrt{a},\ \sqrt{b},\ \sqrt{a\,b}\ $  all $\rm\not\in K\,$ and $\rm\, 2 \ne 0\,$ in $\rm\,K.$

Proof $\ \ $  Let  $\rm\ L = K(\sqrt{b}).\,$ $\rm\,  [L:K] = 2\,$ by  $\rm\,\sqrt{b}  \not\in K,\,$  so it suffices to show $\rm\, [L(\sqrt{a}):L] = 2.\,$ This fails only if  $\rm\,\sqrt{a} \in L = K(\sqrt{b})$ $\,\Rightarrow\,$ $\rm \sqrt{a}\ =\  r + s\ \sqrt{b}\ $  for $\rm\ r,s\in K,\,$ which is false, because squaring yields $\rm\,(1):\ \ a\ =\ r^2 + b\ s^2 + 2\,r\,s\  \sqrt{b},\, $ which is contra to hypotheses as follows:

$\rm\qquad\qquad rs \ne 0\ \ \Rightarrow\ \  \sqrt{b}\ \in\  K\ \ $ by solving $(1)$ for $\rm\sqrt{b},\,$ using  $\rm\,2 \ne 0$

$\rm\qquad\qquad\  s = 0\ \ \Rightarrow\ \  \ \sqrt{a}\ \in\  K\ \ $  via  $\rm\ \sqrt{a}\ =\  r + s\ \sqrt{b}\ =\ r \in K$

$\rm\qquad\qquad\  r = 0\ \ \Rightarrow\ \  \sqrt{a\,b}\in K\ \ $  via  $\rm\ \sqrt{a}\ =\ s\ \sqrt{b},\, \ $times $\rm\,\sqrt{b}\quad\quad$ QED

In the classical case $\rm\:Q\:$ is the field of rationals and the square roots
have radicands being distinct primes. Here it is quite familiar that a
product of any nonempty subset of them is irrational since, over a UFD,
a product of coprime elements is a square iff each factor is a square
(mod units). Hence the classical case satisfies the theorem's hypotheses.

Elementary proofs like that above are often credited to Besicovitch
(see below). But I have not seen his paper so I cannot say for sure
whether or not Besicovic's proof is essentially the same as above.
Finally, see the papers reviewed below for some stronger results.

2,33f  10.0X
Besicovitch, A. S.
On the linear independence of fractional powers of integers.
J. London Math. Soc. 15 (1940). 3-6.

Let  $\ a_i = b_i\ p_i,\ i=1,\ldots s\:,\:$ where the  $p_i$  are  $s$  different primes and
the  $b_i$  positive integers not divisible by any of them. The author proves
by an inductive argument that, if  $x_j$  are positive real roots of
 $x^{n_j} - a_j = 0,\  j=1,...,s ,$ and  $P(x_1,...,x_s)$  is a polynomial with
rational coefficients and of degree not greater than  $n_j - 1$  with respect
to  $x_j,$ then  $P(x_1,...,x_s)$  can vanish only if all its coefficients vanish. $\quad$ Reviewed by W. Feller.

15,404e  10.0X
Mordell, L. J.
On the linear independence of algebraic numbers.
Pacific J. Math. 3 (1953). 625-630.

Let $K$ be an algebraic number field and  $x_1,\ldots,x_s$  roots of the equations
$\ x_i^{n_i} = a_i\ (i=1,2,...,s)$ and suppose that (1) $K$ and all $x_i$ are real, or
(2) $K$ includes all the $n_i$ th roots of unity, i.e. $ K(x_i)$ is a Kummer field.
The following theorem is proved. A polynomial $P(x_1,...,x_s)$ with coefficients
in $K$ and of degrees in $x_i$, less than $n_i$ for $i=1,2,\ldots s$, can vanish only if
all its coefficients vanish, provided that the algebraic number field $K$ is such
that there exists no relation of the form  $\ x_1^{m_1}\ x_2^{m_2}\:\cdots\: x_s^{m_s} = a$, where $a$ is a number in $K$ unless  $\ m_i \equiv 0 \mod n_i\ (i=1,2,...,s)$. When $K$ is of the second type, the theorem was proved earlier by Hasse [Klassenkorpertheorie,
Marburg, 1933, pp. 187--195] by help of Galois groups. When $K$ is of the first
type and $K$ also the rational number field and the $a_i$ integers, the theorem was proved by Besicovitch in an elementary way. The author here uses a proof analogous to that used by Besicovitch [J. London Math. Soc. 15b, 3--6 (1940) these Rev. 2, 33].  $\quad$  Reviewed by H. Bergstrom.

46 #1760  12A99
Siegel, Carl Ludwig
Algebraische Abhaengigkeit von Wurzeln. (German)
Acta Arith. 21 (1972), 59-64.

Two nonzero real numbers are said to be equivalent with respect to a real
field  $R$  if their ratio belongs to  $R$. Each real number  $r \ne 0$  determines
a class  $[r]$  under this equivalence relation, and these classes form a
multiplicative abelian group  $G$  with identity element $[1]$. If  $r_1,\dots,r_h$
are nonzero real numbers such that $r_i^{n_i}\in R$ for some positive integers $n_i\
(i=1,...,h)$, denote by $G(r_1,...,r_h) = G_h$ the subgroup of $G$ generated by
$[r_1],\dots,[r_h]$ and by $R(r_1,...,r_h) = R_h$ the algebraic extension field of
$R = R_0$ obtained by the adjunction of $r_1,...,r_h$. The central problem
considered in this paper is to determine the degree and find a basis of $R_h$
over $R$. Special cases of this problem have been considered earlier by A. S.
Besicovitch [J. London Math. Soc. 15 (1940), 3-6; MR 2, 33] and by L. J.
Mordell [Pacific J. Math. 3 (1953), 625-630; MR 15, 404]. The principal
result of this paper is the following theorem: the degree of $R_h$ with respect
to $R_{h-1}$ is equal to the index $j$ of $G_{h-1}$ in $G_h$, and the powers $r_i^t\
(t=0,1,...,j-1)$ form a basis of $R_h$ over $R_{h-1}$. Several interesting
applications and examples of this result are discussed. $\quad$ Reviewed by H. S. Butts

Assume that there was some linear dependence relation of the form

$$ \sum_{k=1}^n c_k \sqrt{p_k} + c_0 = 0 $$

where $ c_k \in \mathbb{Q} $ and the $ p_k $ are distinct prime numbers. Let $ L $ be the smallest extension of $ \mathbb{Q} $ containing all of the $ \sqrt{p_k} $. We argue using the field trace $ T =  T_{L/\mathbb{Q}} $. First, note that if $ d \in \mathbb{N} $ is not a perfect square, we have that $ T(\sqrt{d}) = 0 $. This is because $ L/\mathbb{Q} $ is Galois, and $ \sqrt{d} $ cannot be a fixed point of the action of the Galois group as it is not rational. This means that half of the Galois group maps it to its other conjugate $ -\sqrt{d} $, and therefore the sum of all conjugates cancel out. Furthermore, note that we have $ T(q) = 0 $ iff $ q = 0 $ for rational $ q $.

Taking traces on both sides we immediately find that $ c_0 = 0 $. Let $ 1 \leq j \leq n $ and multiply both sides by $ \sqrt{p_j} $ to get

$$ c_j p_j + \sum_{1 \leq k \leq n, k\neq j} c_k \sqrt{p_k p_j} = 0$$

Now, taking traces annihilates the second term entirely and we are left with $ T(c_j p_j) = 0 $, which implies $ c_j = 0 $. Since $ j $ was arbitrary, we conclude that all coefficients are zero, proving linear independence.


Proving $\frac{1}{1\cdot3} + \frac{1}{2\cdot4} + \cdots + \frac{1}{n\cdot(n+2)} = \frac{3}{4} - \frac{(2n+3)}{2(n+1)(n+2)}$ by induction for $n\geq 1$ I'm having an issue solving this problem using induction. If possible, could someone add in a very brief explanation of how they did it so it's easier for me to understand?

$$\frac{1}{1\cdot3} + \frac{1}{2\cdot4} + \cdots + \frac{1}{n\cdot(n+2)} = \frac{3}{4} - \frac{(2n+3)}{2(n+1)(n+2)}$$

How do I prove the above equation for all integers where $n\geq1$?

First, check the formula for $n=1$. So:
$$\frac1{1\cdot 3}=\frac34-\frac{2\cdot1+3}{2(1+1)(2+1)}$$
Since this is true, we have shown the so called base case.

Now substitute in the formula $n$ by $n+1$ to get the statement that you have to show:

$$\frac1{1\cdot 3}+\frac1{2\cdot 4}+\cdots+\frac1{(n+1)(n+3)}=\frac34-\frac{2n+5}{2(n+2)(n+3)}\qquad (*)$$

The good news is that you can (and should) assume that the formula is valid for the $n$ first positive integers, so
$$\begin{align}&\left(\frac1{1\cdot 3}+\frac1{2\cdot 4}+\cdots+\frac1{n(n+2)}\right)+\frac1{(n+1)(n+3)}\\
&=\frac34-\frac{2n+3}{2(n+1)(n+2)}+\frac1{(n+1)(n+3)}
\end{align}$$
and you should obtain $(*)$ with straightforward computings.

Perhaps my explanation is not very brief but I hope it to be useful.


Solutions to $x^3+y^3+z^3 = x^2 + y^2 + z^2=x+y+z=0$ I need to prove that $xyz=1$.
dealing trew this problem I get that $x+y= \frac{2}{3}$ and that results that $z = -\frac{2}{3}$.
after all i got $xyz= - \frac{10}{27}$

When I was before dealing with this, I over and over get that $xyz=0$.

You can't prove this for rational numbers x,y,z . There is at least one counter example:
$x = y = z = 0$ is a solution which contradicts $xyz = 1$.

hint:

Assume $xyz=1$
then $1|xyz$
so $xyz=1a$


An element of a group $G$ is not conjugate to its inverse if $\lvert G\rvert$ is odd Prove that if $G$ is a finite group of odd order, then no $x\in$$G$ , other than $x=1$, is conjugate to its inverse.

This question is from Advanced Modern Algebra (exer 2.79) by Joseph J. Rotman.

The hint states that if $x$ and $x^{-1}$ are conjugate, how many elements are in $x^{G}$?

What I know so far:

$\left\lvert x^{G}\right\rvert$ is odd (greater than 1, otherwise it's in the center) and is a divisor of |$G$|
|Z($G$)| has a common factor (other than 1) with size of the orbit $\left\lvert x^{G}\right\rvert$ so that the center is not just the identity. This is from the class equation.
The centralizer of $x$ has odd size and $\lvert C_{G}(x) \rvert \cdot \lvert x^{G}\rvert=\lvert G\rvert$

I don't see the implication of $x$ and its inverse being conjugate has other than their orbits having the same size and laying in the same conjugacy class.

Is the info I have useful? Any help would be appreciated.

Suppose $x \neq 1$ is conjugate to $x^{-1}$.
Let $C(x)$ be the conjugate class containing $x$.
If $x = x^{-1}$, then $x^2 = 1$.
Hence $|G|$ is divisible by $2$.
This is a contradiction.
Hence $x \neq x^{-1}$.
Since $|C(x)|$ is odd, $C(x)$ contains $y$ which is neither $x$ nor $x^{-1}$.
Since $x$ is conjugate to $y$, $x^{-1}$ is conjugate to $y^{-1}$.
Hence $y^{-1} \in C(x)$.
Since $y \neq y^{-1}$, we must conclude that $|C(x)|$ is even.
This is a contradiction.

$|G|$ is odd implies that no element (other that 1) has even order. Suppose $x$ conjugate to its inverse, then  $x=g(gx)^{-1}$ implies $gx=g^2(gx)^{-1}$, so we obtain that $g^2=1$, a contradiction is found.


Algorithm to generate a prime number which is n-digits long Is there an algorithm which, given the number of digits n, generates a prime number which is      n-digits long, in polynomial time complexity?

It is believed (though it is a much stronger result than anyone has been able to prove) that for $N$ large enough there is a prime between $N$ and $N+C(\log N)^2$, for some small positive constant $C$ (I think $C=2$ will do). So in practice you could take some $n$-digit number $N$ and then just test $N,N+1,N+2,\dots$ until you find a prime, and you would expect to find one in time polynomial in $n$. Of course in practice you wouldn't test the even numbers, indeed, you might sieve the whole interval for small factors first before applying any other primality tests.

I don't know if there is any algorithm proved to find a prime in polynomial time. We don't have any useful formulas guaranteed to give primes.

Such polynomial algorithm (depending on n) in unknow to humanity currently - but try this online tool for arbitrary precision calculations if you need to generate some n-digit primary number

https://www.alpertron.com.ar/ECM.HTM

For e.g. 20-digit number type:

N(100000000000000000000000000000)
and click 'factor' button - it will will return:
  100000000000000000000000000319


Feynman/Einstein/etc and Basic Maths Did famous physicists/mathematicians do basic arithmetic (add/sub/div/mult) in their heads, or would they work them out on paper?

Is there a scale of difficulty for this?  I.e. "Erdos could do 5 digit multiplication in his head, but Feynman could at most do 3 digit reliably".

Or do they all do it on pencil/paper?

It to a large extent depends on how much logically one thinks. One can do the same by breaking a big problem into smaller simpler ones. In Feynman's 'Surely you are joking Mr. Feynman',  Feynman mentions how he defeats a Japanese abacus expert.. simply by breaking a problem  logically into known steps.

Does anyone do all basic arithmetic in their head?  No, so the answer to your first question is that they certainly did some basic arithmetic on paper.

As far as a scale of skill in mental math... I would sincerely doubt this exists.  This would have to be similar to a World Records maintaining group, and maintain a record for all "famous" researchers.  Of course, then they'd have to define famous.

I would be willing to bet that you will only find individual stories of the mental math capabilities of mathematicians or physicists, but with no organization maintaining a ranking system or scale.

Related: Euler carried a math problem to 50 decimal places in his head: http://library.thinkquest.org/22494/stories/Euler.htm  Then again, he was Euler. :)


How can I find $\int\tan\;x\;\cos\;2x\;\mathrm dx$? My question is ; How can I solve the following integral question?

$$\int\tan\;x\;\cos\;2x\;\mathrm dx$$

Thanks in advance,

$\int\tan\;x\;\cos\;2x\;\mathrm dx$

=$\int\frac{sinx}{cosx}\;\cos\;2x\;\mathrm dx$

=$-\int\frac{1}{cosx}\;\cos\;2x\;\mathrm -sinx dx$                    $\frac{d(cosx)}{dx}$ = -sinx.dx

=$-\int\frac{1}{cosx}\;\cos\;2x\;\mathrm d(cosx)$

cos2x=2${cos^2x}$-1

=$-\int\frac{1}{cosx}\cdot(2{cos^2x}$-1) d(cosx)$

=$-\int(2{cosx}-\frac{1}{cosx}) d(cosx)$

= $-[\int(2{cosx}d(cosx)$ - $\int\frac{d(cosx)}{cosx}$

= $-[{cos^2x} + C1 - log (cosx) -C2]$

=$log(cosx)-{cos^2x}+C2-C1$ [C2,C1 - Integral Constants]


$\mathcal{l}_1$ norm replaced with reweighted $\mathcal{l}_2$ In this paper, (section 2, page 2)$\mathcal{l}_1$ norm is replaced with reweighted $\mathcal{l}_2$ in an optimization problem. I don't understand how $\lVert x\rVert_1$ is replaced with $x^TWx$ and ow the solution has changed to its weighted version.

$$\min_x \lVert x\rVert_1 \quad \text{subject to} \quad Ax=b $$
$$\Downarrow$$
$$x^TWx \quad \text{subject to} \quad Ax=b$$
$$\Downarrow$$
$$x^{k+1}=(W^k)^{-1}A^T(A(W^k)^{-1}A^T)^{-1}b$$

The formula for $x^{k+1}$ comes from constraint optimization, in particular, Lagrange multipliers: given a problem of the form

$$
\min f(x)\\
s.t. g(x)=0
$$
introduce the Lagrangian $\mathcal{L}(x,\lambda)=f(x)+\lambda g(x)$. Then, a solution to the minimization problem is a stationary point for the Lagrangian, that is,

$$
\partial_x \mathcal{L}(x,\lambda)=\partial_x f(x)+\lambda \partial_x g(x) =0\\
\partial_\lambda \mathcal{L}(x,\lambda)= g(x)=0.
$$

In your case, the Lagrangian is $\mathcal{L}(x,\lambda)=\frac{1}{2}x^TWx+\lambda^T(Ax-b)$ (the factor 1/2 does not change the point where the minimum is achieved, but simplifies calculations later), which leads to the system

$$
W^Tx+A^T\lambda=0\\
Ax=b,
$$
Now, the first equation can be solved for $x$, giving $x=-W^{-1}A^T\lambda$, which plugged in the second gives $-AW^{-1}A^T\lambda=b$, or $\lambda=-(AW^{-1}A^T)^{-1}b$. Plug this back in the first equation and you get

$$
W^Tx-A^T(AW^{-1}A^T)^{-1}b=0\Rightarrow x=(W^T)^{-1}A^T(AW^{-1}A^T)^{-1}b
$$
which is the formula you see.

It appears that they are taking $W$ to be a diagonal matrix with diagonal entries $W_{ii} = |x_i|^{-1}$ (more precisely, they're taking a sequential approach where the matrix $W$ in the $k$'th iteration has diagonal entries
$|x^{k-1}_i|^{-1}$, where $x^{k-1}$ is the result of the $k-1$'th iteration).
Assuming everything converges nicely to a solution with all nonzero entries, this should work nicely.  I'm not sure what would happen if the optimal solution has some entries of $0$.

EDIT:  Going from the step 2 to step 3 is just the standard "normal equations" formula for solving a weighted linear least-squares problem in the case where $A$ has full row rank. Let's try a toy example: $$A = \pmatrix{1 & 8 & 12},\ b = 4 $$
for which it's not hard to see the optimal solution of the $\ell_1$ problem is
$$ x = \pmatrix{0\cr 0\cr 1/3\cr}$$
Start with $W = I$.  The optimal solution to the least-squares problem

maximize $x^T W x$ subject to $Ax = b$

is

$$x = W^{-1} A^T  (AW^{-1} A^T)^{-1} b = \pmatrix{4/209\cr 32/209\cr 48/209}
\approx \pmatrix{0.01913875598\cr 0.1531100478\cr 0.2296650718}$$

Now we take $W$ to be the diagonal matrix with diagonal entries
$209/4, 209/32, 209/48$, and get

$$ x =  W^{-1} A^T  (AW^{-1} A^T)^{-1} b =\pmatrix{4/2241 \cr 256/2241 \cr 64/249}\approx \pmatrix{0.001784917448 \cr 0.1142347166\cr 0.2570281124\cr}$$

The next few iterations are approximately

$$ \pmatrix{0.0001610759876\cr 0.08247090565\cr 0.2783393066},\
 \pmatrix{0.00001420449501\cr 0.05818161157\cr 0.2945444086},\
  \pmatrix{0.000001231478183\cr 0.04035307711\cr 0.3064311793}$$

and it does look plausible that this is converging to the optimal solution of the $\ell_1$ problem.


Hyperbolic Geometry and Circles How does the angle of parallelism relate to the arc of a circle and a point outside?

In Hyperbolic Geometry, I'm trying to figure out what happens to the "visibility" of a circle when a point outside increases in distance away from the circle.

So given a point p outside the circle, there exists two tangents from the circle that cross point p. As p moves farther away these tangents move and the arc between them increases. I'm given the equations for the angle of parallelism(2arcTan(e^-x)) and the length of the circle (2piSinH(r)).

I know the angle goes to 0 as x->infinity.

I would prefer the answer to finding an expression to finding the "visibility" of the circle arc or at least a hint in the right direction to be able to know where to assume the angle of parallelism lies in relation to a point outside a circle.

Consider a circle $c$ centered at point $C$ and consider $P$ a point outside the circle as shown below. (I am using here the Klein model.)

Let $\lambda$ be the angle of visibility of the circle if it is seen from $P$.

The first observation is that if $P$ goes to the infinity then the angle of visibility goes to zero just like in Euclidean geometry. That is, the farther we are from the circle, the smaller it looks. This is not surprising.

Second, note that the angles at the tangent points are right angles. If, again, $P$ goes to the infinity then  $\gamma$ tends to $\Pi(r)$, the angle of parallelism belonging to the radius of our circle.

While in the Euclidean geometry $2\gamma$ would tend to $\pi$, in Hyperbolic geometry $2\gamma$ tends to $2\Pi(r)$ as the $P$ back away from the center of circle.

Then: the arc lenghth is proportional to the angle at the center.

I don't know if this answers the question.

Just an first long comment to get the question clear, will be updated later.

I am just puzzeling along, but I guess this will be to long for a comment.

Lets first work out the Euclidian case (then at least we know where we are talking about)

So (at the same time filling in some gaps)

We have a circle $C$ with centre $O$ with some fixed radius $r$ and a point $P$ outside this circle

From $P$ we have two tangents $t_1$ and $t_2$ to circle $C$.

Lets call the points where $t_1$ and $t_2$ touch $C$ , $T_1$ and $T_2$ and then the question is what is the arc of visibility (the arc of $C$ facing between $T_1$ and $T_2$ facing $P$ ?

and how long is it as function of $\angle T_1PT_2$ (do I have this all correct?)

A bit geometry learns us that that arc has the length $r (\pi -\angle T_1PT_2 ) $ (yes radians please)
Just because all we know about the kite $OT_1PT_2$ , $\angle OT_1P$ and $\angle OT_2P$  (see https://en.wikipedia.org/wiki/Kite_%28geometry%29 )

then the question is what is the same then in hyperbolic geometry.

So what is the same?
$\angle OT_1P$ and $\angle OT_2P$ are still $\pi/2$ radians.

what is different?
- thats more for the next edit.

please update the question accordingly and we can continue the puzzle :)


Show that $|f(p_n)|1$ but that $|p-p_n|1000$. Let $f(x)=(x-1)^{10}$.

The root of the equation , $p=1$.

The approximates of the root, $p_n=1+\frac{1}{n}$

Show that $|f(p_n)|<10^{-3}$ whenever $n>1$ but that $|p-p_n|<10^{-3}$ requires that $n>1000$.

I started to solve it by the following way:

$|p-p_n|<10^{-3}\Rightarrow |1-(1+\frac{1}{n})|<10^{-3}\Rightarrow |\frac{1}{n}|<10^{-3}\Rightarrow |n|>1000\Rightarrow n>1000$

And

$f(p_n)=[(1+\frac{1}{n})-1]=\frac{1}{n}$; whenever $n>1$

But how to show

$|f(p_n)|<10^{-3}$ ?

You forgot the power of $10$ when you computed $f(p_n)$.


What is an ordered basis? To my understanding, $$e_1 = \{1,0,\ldots,0\},\quad e_2 = \{0,1,\ldots,0\}, \quad \ldots, \quad e_n = \{0,0,\ldots,1\}$$ is an ordered basis for a vector space of dimension $n$. But the group of basis, which implies no ordering is not ordered.

For example: $$\{1,0,\ldots,0\},\quad \{0,1,\ldots,0\},\quad \ldots, \quad\{0,0,\ldots,1\}$$ is not ordered basis, but a basis, for a vector space of dimension $n$.

Is this correct? Thanks!

The difference, of course, is the ordering. An ordered basis $B$ of a vector space $V$ is a basis of $V$ where some extra information is provided: namely, which element of $B$ comes "first", which comes "second", etc. If $V$ is finite-dimensional, one approach would be to make $B$ an ordered $n$-tuple, or more generally, we could provide a total order on $B$.

The difference can be obscured however by common abuse of notation and abuse of terminology regarding bases vs. ordered bases. For example, it would be quite common to say that
$$\{e_1,\ldots,e_n\}$$
is an ordered basis, even though it is just a set and not an ordered $n$-tuple, because the indexes tell you what the intended ordering is.

Let's consider $\mathbb{R}^3$. An example of a plain-old, vanilla basis would be a set
$$\left\{\begin{array}{ccc} & a & \\  & & \alpha\\ \mathbf{a}& & \end{array}\right\}$$
where $a$, $\alpha$, and $\mathbf{a}$ are a basis of $\mathbb{R}^3$ (which I have intentionally written and labeled in a way such that there would be no implied order). An example of an ordered basis could be
$$(a,b,c)$$
which is an ordered $3$-tuple where $a$ comes first, $b$ comes second, and $c$ comes third (reinforced by the fact that that is in alphabetical order), or equivalently, I could have said
$$\{a,b,c\}$$ is an ordered basis where the ordering is specified by $a<b<c$.

A basis is a set of vectors that spans a vector space (or vector subspace), each vector inside can be written as a linear combination of the basis, the scalars multiplying each vector in the linear combination are known as the coordinates of the written vector; if the order of vectors is changed in the basis, then the coordinates needs to be changed accordingly in the new order.

That is the reason why the authors say: "an ordered basis", when they write about, by example, a basis $\{v_1, v_2, \dots, v_n\}$ then it is implicit that an order is said and it is an ordered basis.


Poisson process - expected number of arrivals in time interval I came across this question and can't figure out if I'm missing something or if the answer is just "$3$". Can anyone clarify?

Question:

"The number of people arriving at a certain "take away" drive-through restaurant follows a Poisson process with mean one. Suppose that the waiters can only process three orders in any given four minute interval, and assume that they can process these orders instantaneously. What is the expected number of people that will actually leave the drive through restaurant with their orders filled, in any given four minute interval?"

I'm assuming by "mean", the question means $\lambda=1$ so then $\mathrm{E}[N(4)]= \lambda \cdot 4 = 4$. Then of those $4$, only $3$ can have their orders filled.

The only alternative I can think is that by "mean" the question means $\mathrm{E}[N(t)] = 1$, but then only one person is served in any time interval, even if that interval is infinite.

hint

You want the mean number of customers served. There will either be $0,1,2$ or $3$ depending on how many arrive (it's $3$ if three or more arrive). You know the distribution of how many arrive is Poisson with mean $4$. So you can calculate the expected value. It will be less than $3$.

You first assumption is right. A Poisson process with $\lambda = 1$.


Find an integer $a$ such that $a\sqrt{2} $ has a given decimal part Suppose I want to find integers such that when I multiply it by an irrational number (e.g $\sqrt{2}$), its decimal part contains 0.14159... as starting digits. How do I find them? Is there a pattern for the digits of such numbers?

It is fairly easy to compute $\sqrt{2}$ to arbitrarily high precision.  See for example this page reporting a little more than one million digits.

If we are searching for a fixed initial string of length $n$, then of course if it can be located in $\sqrt{2}$ further along, that string can be brought to the front by multiplying by the appropriate power of ten.  One then has a (not necessarily minimum) solution for $a$.  In this case the string "14159" is found seven times within the first million digits.

Finding the minimum value of $a$ seems to be a difficult computational challenge.

We can show that there exists no integer such that $a \cdot \sqrt{2}$ has the full decimal part of $\pi$. Suppose there were such an integer $a$ such that $a \cdot \sqrt{2} = B + \pi -3$, where $B \in \mathbb{Z}$. Then, we would  also have that $a \cdot \sqrt{2} + 3 -B = \pi$. But then notice that the LHS is an algebraic number, whereas the RHS is a transcendental number. Contradiction.


$AB=BA$ if there is an orthonormal basis of $\mathbb{R}^n$ of eigenvectors Show that if there is an orthonormal basis of $\mathbb{R}^n$ that consists of
  eigenvectors of both of the $n \times n$ matrices $A$ and $B$, then $AB = BA$.

I'm not sure if what I have done suffices to solve the problem, but let $(v_1,v_2,v_3,v_4)$ be the basis of orthonormal eigenvevtors of $A$ and $B$.

Then for example, $Av_1=\lambda_1 v_1$ and $Bv_1=\mu_1 v_1$ (where $\lambda$ and $\mu$ are corresponding eigevalues).

Then we have $$ABv_1=A\mu_1 v_1=\mu_1 A v_1=\mu_1 \lambda_1 v_1 = \lambda_1 B v_1=BAv_1$$

And since we can do this for all $(v_1,v_2,v_3,v_4)$, thus $AB=BA$

If that that does not suffice, could anybody point out why? Thanks!

That's fine. If two linear things agree on a basis then they agree everywhere. You should definitely make sure you can prove that!

HINT: Show that they agree on this orthonormal basis.

$$AB(v_{j}) = \lambda_{j}\mu_{j}v_{j} = BAv_{j}$$

for $1\leq j \leq n$.


Rationalising the denominator: $\frac{11}{3\sqrt{3}+7}$ For my homework, I have been asked to rationalise and simplify this surd;

$$\frac{11}{3\sqrt{3}+7}$$

Each time I do this I get the wrong answer. The method I am using is;

$$ \frac{11}{3\sqrt3+7} \times \frac{3\sqrt3-7}{3\sqrt3-7} $$

I ended up with $$\frac{33+11\sqrt3-77}{9+3+21+7\sqrt3-21-7\sqrt3}$$

This ends up no where near the right answer, even once it is simplified. Can someone tell me where I'm going wrong?

Many thanks!

You're mistakenly multiplying $\rm\; a * b\sqrt{3} \ =\ ab + a\sqrt{3}\:\,\;$ but $\rm\; ab\:\sqrt{3}\;$ is correct.

In other words $\rm\; b\:\sqrt{3}\;$ means $\rm b * \sqrt{3}\:,\;$ not $\rm\; b + \sqrt{3}\:.$

Also, to rationalize the denominator use $\rm\; (a+b\sqrt 3)\:(a-b\sqrt 3)\ =\ a^2 - 3 b^2$

the answer is

$$-\frac{33\sqrt3-77}{22}$$


Expectations of functions of normal random variables so I am a TA in an intro stats class and I stumbled upon a brain teaser question that even I am not quite sure how to solve. I thought some of you might be able to help. The question is as follows:

You have a normal random variable with mean $\mu$ and standard deviation $\sigma$. The students are asked to calculate the $E[f(X)]$ for three functions (and the question specifies that for the last two, you should express the solution as the standard normal CDF, $\phi$:

a) $f(x)=e^{ax}$ where a is an element of $R$

b) $f(x)=(e^{ax}-b)^+$ where a is an element of $R$ and $b>0$$

c) $f(x)=(x-a)^+$ where a is an element of $R$

So, my approach to part (a) was calculating the same as you would for a moment generating function (i.e. just expand it to get $1 + aE(x) + a^2E(x^2)/2! + a^3E(x^3)/3!+...+$) however, I am not sure that that is the correct approach to this question. Then, for the last two questions, I am not sure how to approach them. Any kind of help would be greatly appreciated!

Let us solve (c) and see if you can adapt the ideas below to (a) and (b).

First, to compute $E[f(X)]$ by expanding $f$ into a series is definitely not the first idea one should try. Rather, use the definition (in the density case), that is,
$$
E[f(X)]=\int_\mathbb Rf(x)g(x)\mathrm dx,
$$
where $g$ is the density of the distribution of $X$.
Second, $X=\sigma Z+\mu$ where $Z$ is standard normal hence it suffices to solve (c) when $X$ has density $\varphi$. Thus, one looks for
$$
E[f(X)]=\int_a^\infty (x-a)\varphi(x)\mathrm dx.
$$
Third, $\varphi'(x)=-x\varphi(x)$ hence $(x-a)\varphi(x)=-\varphi'(x)-a\varphi(x)$ and
$$
E[f(X)]=\left.-\varphi(x)\right|_a^\infty-a\int_a^\infty\varphi(x)\mathrm dx=\varphi(a)-a+a\Phi(a).
$$

For (a): The MGF of the normal distribution can be found here: http://www.cc.gatech.edu/~lebanon/notes/mgf.pdf

You basically find the MGF of the standard normal distribution and use that to calculate the MGF of the normal distribution.

For (b), (c) use linearity of expectation.


Extend Petersen's Theorem This was a homework problem.
Petersen's Theorem: Every cubic, bridgeless graph contains a perfect matching.
Show that Petersen’s theorem (Theorem 8.11) can be extended somewhat by proving that if $G$ is a bridgeless graph, every vertex of which has degree $3$ or $5$ and such that $G$ has at most two vertices of degree $5$, then $G$ has a $1$-factor.
My idea was about splitting into $3$ cases, $0$ $5$-degree vertices, $1$ $5$-degree vertice and $2$ $5$-degree vertices. With $0$, it's obvious, but I can't figure out $1$ and $2$.
This is what I've done.
Case 1: $G$ has $0$ vertices of degree $5$.
Automatically proven by using thm 8.11 (every $3$-regular bridgeless graph contains a $1$-factor)
Case 2: $G$ has $1$ vertice of degree $5$
Consider $S$ is a subset of $V(G)$
Let $|S| = k$ and $|Ko(G - s)| = j$. ($Ko$ being the number of components of a graph)
$3  (k-1) + 5 \ge 3j$ or $3  (k-1) + 5 \ge 3(j-1) + 5$
$3  (k-1) + 5 \ge 3j \implies 3k - 3 + 5 \ge 3j \implies 3k + 2 \ge 3j \implies k + ⅔ \ge j$
or $3  (k-1) + 5 \ge 3j-3+5 \implies 3 k \ge j$
Case 3: G has 2 vertices of degree 5
$3  (k-2) + 5(2) \ge  3j \implies 3k - 6 + 10 \ge 3j \implies 3k + 4 \ge 3j \implies k + 4/3 \ge j$
or $3(k-2) + 5(2) \ge 3(j-1)+5 \implies 3k+4 \ge 3j+2 \implies 3k+2 \ge 3j$
or $3(k-2) + 5(2) \ge 3(j-2)+10 \implies 3k+4 \ge 3j+4 \implies k \ge j$
Where do I go from here? Is my setup completely wrong?

There are some typos/mistakes in the inequalities in the cases $1$ and $2$. After they are fixed you get in case $1$ that $k\geq j+2/3$. However since they are both integers, $k\geq j$, which is what you need to apply Tutte's theorem. In case $2$ you only get $k\geq j+4/3$, which means that either $k\geq j$ (which is good), or, potentially, that $k=j-1$, which would be bad. However, this is actually not possible: either there is at least one edge between the vertices if $S$ or there isn't. If there is then $3(k−2)+5(2)-2\geq 3j$ and we are back to $k\geq j+2/3$. But if there isn't then all $3k+4$ edges go out to $j=k+1$ components, with all of them getting odd number and at least 3 each - which is is not possible (you can check why). So in all cases $k\geq j$ and you can apply Tutte's theorem.


A function in which addition and multiplication behave the same way Exponents have a well-known property:

$$x^ax^b = x^{a+b}$$

but

$$x^{a} + x^{b} \neq x^{a+b}$$

Similarly,

$$\log(a) + \log(b) = \log(ab) $$

But

$$\log(a)\log(b) \neq \log(ab)$$

So my question is this:

Is there a function $f$ on $\mathbb{R}$ or some infinite subset of $\mathbb{R}$ with the following properties

$$(1)\quad f(x)f(y) = f(x+y)$$
$$(2)\quad f(x)+f(y) = f(x+y)$$
ie
$$(3)\quad f(x)+f(y) = f(x)f(y)$$

It seems that $(2)$ requires the function to be linear...

Your title expresses interest in "a function in which addition and multiplication behave the same way". That's condition (3) alone. Conditions (1) and (2) are unnecessarily-strong requirements that artificially restrict the possible solutions. Be that as it may ...

Let's invoke condition (3) with three arbitrary values, $x$, $y$, $z$.

$$\begin{align}
f(x) + f(y) = f(x)\cdot f(y) \\
f(x) + f(z) = f(x)\cdot f(z)
\end{align}$$
Subtracting, we get
$$f(y) - f(z) = f(x)\cdot(\;f(y)-f(z)\;)\quad\to\quad\left(f(x)-1\right)\cdot\left(f(y)-f(z)\right) = 0$$
For all choices of $x$, $y$, $z$, at least one factor must vanish. We conclude that $f$ must be some constant; say, $k$. (The vanishing of the first factor requires specifically that $k=1$, but we'll go ahead and absorb this into the more-general statement.)

Then condition (3) reduces to
$$k + k = k\cdot k \quad\to\quad k(k-2) = 0$$
so that $k = 0$ or $k = 2$. That is, we have two ways to satisfy condition (3):

  $$f(x) \equiv 0 \qquad\text{or}\qquad f(x) \equiv 2$$

Imposing conditions (1) and (2) limits the solutions to just the first.

Any functions where both sum and product = 2 will work. zero will not work because it results in division by zero. $(x+y)/(x*y)-1=0$


Calculating the Limit of a Function without use of L'Hospital's Rule or Power Series I came across this question the other day and have been trying to solve it by using some simple algebraic manipulation without really delving into L'Hospital's Rule or the Power Series as I have just started learning limit calculations.
We needed to find :
$$\lim_{x \to 0} \frac {x\cos x - \sin x}{x^2\sin x}$$
I approached this problem in two different ways and know what the flaw is, however I have been unable to justify why this is so.

Let $$f(x) = \frac {x\cos x - \sin x}{x^2\sin x}$$
Therefore, dividing by $x$,
$$f(x) = \frac {\cos x - \frac{\sin x}{x}}{x\sin x}$$
Using standard limit properties,
$$\lim_{x \to 0}f(x) = \frac{\lim_{x \to 0}\cos x - \lim_{x \to 0}\frac{\sin x}{x}}{\lim_{x \to 0}x\sin x}$$
Since $$\lim_{x \to 0} \frac {\sin x}{x}=1$$
$$\lim_{x \to 0}f(x)= \frac{\lim_{x \to 0}\cos x-1}{\lim_{x \to 0}x\sin x}$$

Rewriting the above as $$\lim_{x \to 0}\frac{(\cos x -1)x}{x^2\sin x}$$ and using the fact that $\lim_{x \to 0} \frac {\sin x}{x}=1$ and $\lim_{x \to 0}\frac{\cos x -1}{x^2}= -\frac{1}{2}$,
we get $$\lim_{x \to 0}f(x)=-\frac{1}{2}$$

I know that the answer is wrong although I am not able to understand why.
I believe it is because I cannot combine the numerator and denominator into a single limit function. Using a similar trick, I also obtained the limit to be $-\frac{3}{8}$.

Questions:

1) Could someone please explain why combining the numerator and denominator into a single limit is wrong? (The reason I even went ahead with such a manipulation was, we are allowed to separate the numerator and denominator while expanding the limit of a rational function so I felt that the reverse should also work).

2) As you can notice, I have not used L'Hospital's Rules or Power Series expansion of $\sin x $and $\cos x$. When I used L'Hospital's Rule, I noticed that I needed to go upto the third or fourth derivative to get rid of the $\frac{0}{0}$ indeterminate form. So would there be a better way of approaching such limits?

Thank You.

First, note that both of your answers are incorrect: the actual answer is $\frac{-1}{3}$.

For your questions:

The problem is actually earlier than that: it is not necessarily the case that $\lim \frac{f(x)}{g(x)} = \frac{\lim f(x)}{\lim g(x)}$ unless both limits exist, and $\lim g(x) \neq 0$. In this case, that latter condition isn't satisfied, so this method does not work. In particular, when you write:

$$\lim_{x\to 0}f(x) = \dfrac{\lim_{x\to 0}\cos(x) - \lim_{x\to 0}\frac{\sin(x)}{x}}{\lim_{x\to 0} x\sin(x)},$$

what you've actually written is $\lim\limits_{x\to 0}f(x) = \frac{\mbox{[something]}}{0}$, which is obviously nonsense, and so everything after that is necessarily flawed.

L'Hôpital's rule (he's not a hospital!) is how I'd approach this. There might be a trick to do it quickly, but it's not obvious if there is.

1) If I understand your question, you are conjecturing that:

$$
\lim_{x \to a} \frac{f(x)}{g(x)}= \frac{\lim_{x \to a} f(x)}{\lim_{x \to a} g(x)}
$$

This is wrong. You may try to prove it, but as a simple counterexample should suffice:

Let $f(x)=x$ and $g(x) =x$. Then:
$$
\lim_{x \to a} \frac{f(x)}{g(x)}= \lim_{x \to a} \frac{x}{x} = 1
$$
And the result holds even for $a=0$.
but:
$$
\frac{\lim_{x \to a} f(x)}{\lim_{x \to a} g(x)}= \frac{a}{a}
$$
And the last one is undetermined for $a =0$, since $a/a$ is not within a limit expression anymore. This would actually hold if ${\lim_{x \to a} g(x)}\neq 0$, but this exception was precisely the case you had in hand.

2) You have a rather complicate expression there. I don't see any elegant/short solution to it, but using power series seems pretty much fair and straight forward.

There could be some property related to limits and some known transform such as Initial value theorem from Laplace's transform, but that wouldn't enter into my book as a "better" solution.


Constrained combinations of balls in jars Not sure how to solve the following problem. Imagine we have balls of $n$ different colors. There are $m$ balls of each color, so in total we have $nm$ number of balls.

The question is how many combinations are there to place these $nm$ marbles into $k$ jars keeping in mind that:

Each jar must have exactly $l$ balls ($l \leq n$ and $m < k$).
Each jar should not contain $2$ balls of the same color.

The second constraint makes the problem especially hard for me. I'm not sure where to start. If you could help me or point to the paper/article with similar problem, that would be great.

Thank you in advance!

Finding a closed form seems difficult. Here are some ideas.

Let us consider the case where the jars are numbered.

Consider a $n\times k$ matrix with every entry being either $0$ or $1$. If a ball of $i$ th type is present in $j$ th bin, then $(i,j)$ th entry of the matrix is $1$, else it is zero. Each column may be visualized as a 'bin'. We count the matrices such that

every column contains exactly $l$ ones.
every row contains at most $m$ ones.

Lets assume that $kl\le mn$ (else such matrices do not exist). The strategy is to count all the matrices with restriction (1) and then subtract the number of matrices that do not conform to restriction (2).

The number of matrices with the restriction (1) is ${\binom{n}{l}}^k$. Let $r_i$ be the row sum of the $1\le i\le n$ th row. We have the equation,
$$r_1+r_2+\dots +r_n=kl \quad \quad \quad \quad (A)$$

A solution of (A) where at least one $r_i$ exceeds $m$ (and $r_i\le k \quad \forall 1\le i\le n$) corresponds to some matrices that do not conform with (2). Number of such matrices is
$$\sum_{S}\binom{k}{r_1}\binom{k}{r_2}\cdots \binom{k}{r_n}$$ where $S=\{(r_1,r_2,\dots r_n), \sum r_i=kl \text{ AND at least one }r_i \text{ exceeds }m \}$

Hence the number of valid matrices is $${\binom{n}{l}}^k-\sum_{S}\binom{k}{r_1}\binom{k}{r_2}\cdots \binom{k}{r_n}$$
This is far from a closed form as we are iterating over a set of ordered tuples which are the solutions of (A)

An upper bound: We associate a solution of (A)  where at least one $r_i>m$ with a matrix where in every row, all the ones are stacked up to the left followed by $0$'s (if any). Each solution of (A)  where at least one $r_i>m$ corresponds to a unique matrix and vice versa.

Number of such solutions is (by inclusion-exclusion)
$$E:=\sum_{i=1}^{\lfloor \frac{kl}{m+1}\rfloor}(-1)^{i+1}\binom{n}{i}\binom{kl-(m+1)i+n-1}{n-1}-\sum_{i=1}^{\lfloor \frac{kl}{k+1}\rfloor}(-1)^{i+1}\binom{n}{i}\binom{kl-(k+1)i+n-1}{n-1}$$

Hence, the upper bound is ${\binom{n}{l}}^k-E$

The upper bound will be exact if $k=m+1$.

The case of identical bins seems still more harder.

You need $l \times k=n \times m$, in which case we can be more specific and say $l<n$ and $m<k$, right?


Is it possible to solve $\int \sin^2(\pi t) dt$ without using trig identities? Perhaps by using integration by parts? Is it possible to solve $\int \sin^2(\pi t) dt$ without using trig identities? Perhaps by using integration by parts? I've tried the latter, but It seems that you get an infinite loop?

I would greatly appreciate it if people could please take the time to demonstrate this.

Integrating by parts with $u=\sin(x),\ dv=\sin(x)dx$:
$$\int \sin^2(x)dx=-\cos(x)\sin(x)+\int\cos^2(x)dx=-\cos(x)\sin(x)+x-\int\sin^2(x)dx$$
We deduce:
$$\int\sin^2(x)dx=\frac{x}{2}-\frac{\cos(x)\sin(x)}{2}$$

This can be done by using the reduction formula derived from integration by parts...                                                                   $\int \sin^n xdx =\frac{-1}{n} \sin^{n-1}x\cos x\ + \frac{n-1}{n}\int\sin^{n-2}x\ {d}x$   now by doing a little substitution letting $u=πt$ gives $du=πdt$  solving for $dt$ gives $dt=\frac{du}{π}$ with this substitution our problem looks like this... $\int\sin^2u\frac{1}{π}\ {d}u   \ = \frac{1}{π}\int(\sin^2u)\ {d}u$      now by using the reduction formula gives $\frac{-1}{2}\sin u\cos u\ +\frac{1}{2}\int\ {d}x$ and finally the answer becomes $\frac{-1}{2}\sin(πt)\cos(πt)\ + \frac{1}{2}(πt)$ or we could rewrite as                  $[\frac{-\sin(2πt)}{4}\ +\frac{(πt)}{2}+\ c ]$ final answer hope it helps...


How do I prove this very basic gcd equivalence for the case where there is no common divisor except 1? I want to prove the basic property of gcd that for some integer $a,b$ $gcd(a,b) = 1$ iff there exists some integers $k$ and $l$ in  $ak + bl = 1$. I've been using this basic property for a long time and always assumed it to be true, but cannot find a basic proof for this.

I would express the gcd as the smallest linear combination of a and b, but this will force me to conclude that since 1 is the smallest linear combination, then the iff condition is satisfied. But this doesn't seem to be the right approach however intuitive, since I did not prove the implication both ways. Is there a way I could formally prove this?

One direction is easy,  namely if $ax+by=1$, then the gcd is $1$.

For the converse you can use the Euclidean algorithm.  See Bezóut's identity . ..

The proof is rather long. but if you're interested you could look in this book which is a number theory book. http://www.fuchs-braun.com/media/532896481f9c1c47ffff8077fffffff0.pdf
The theorem is called theorem 1.3 and it is stated and proven on page seven


Use the graph of f to find the limit How can I use the graph of f to find the limit?

$\displaystyle \lim_{x \to 1^−}f(x)$
$\displaystyle \lim_{x\to 1^+}f (x)$

I am not sure where to start

Look to the graph!

When you come from numbers smaller than 1, the function gets bigger and bigger, so it goes to $\infty$. Therefore we have $\lim_{x\rightarrow1^{-}} = +\infty$.

When you come from numbers smaller than 1, the function gets smaller and smaller, so it goes to $-\infty$. Therefore we have $\lim_{x\rightarrow1^{+}} = -\infty$.

Also, make sure to get the right notation. The post has been edited, but it wasn't correct before the edit.

Just looking at the graph we have:
$$
\lim_{x\to 1^-}f(x)=+\infty, \quad \lim_{x\to 1^+}f(x)=-\infty.
$$


Simultaneously diagonalizable without distinct eigenvalues It is a well known result that if $u$ and $v$ are two diagonalizable endomorphisms of a $\mathbb{C}$ finite-dimensional linear space $E$, if $u$ (or $v$) has distinct eigenvalues and if $u$ and $v$ commute, then $u$ and $v$ are simultaneously diagonalizable.

I am wondering what happens when we drop the hypothesis that $u$ or $v$ has distinct eigenvalues ? The usual proof consists in saying that if $(\lambda_{1},\ldots,\lambda_{n})$ are the distinct eigenvalues of $u$ and $E_{i} = \mathrm{ker}(u- \lambda_{i} \mathrm{Id})$ then $g_{\vert E_{i}}$ (the endomorphism induced by $g$ on $E_{i}$) is diagonalizable. Then if $B_{i}$ is a basis of $E_{i}$ composed of eigenvectors for $g$, $(B_{1},\ldots,B_{n})$ is a basis of $E$ which diagonalize both $u$ and $v$.

What changes if the engenvalues are not distinct ?

An n by n matrix is "diagonalizable" if and only if there are n independent Eigenvectors.  Two matrices are "simultaneously diagonalizable" if they have the same eigenvectors.  Distinct Eigenvalues are irrelevant.


Probability of visiting state $s_1$ of a Markov chain more than $N$ times in $L$ steps. Assume we have a two-state Markov chain, with $s_1$ and $s_0$ denoting the two states. The initial state of the Markov chain is either $s_1$ or $s_0$ with probability $p_1$ or $p_0$, respectively. The transition probability between states $s_i$ and $s_j$ is $p_{ij}$.

My question is, given the initial state probability $p_1$ for state $s_1$, which is the probability that after $L$ steps, state $s_1$ has been visited more than $N$ times? Notice that remaining in state $s_1$ counts as an other visit to this state.

I thought that this was a quite straight forward question, but after some research in probability and stochastic processes books I found no theorem with this result. I tried to proof it my self, but I the solution looks like being quite tedious.

I would really appreciate if somebody can point me the right direction in how to calculate this probability.

cheers

Pol

This is my answer to my own question. I wanted to get an expression easy to work with, but this is the best I got.

The question is to compute the probability $P(N_1 \geq N | L)$ that is the probability that the number of visits to state $s_1$ (denoted by $N_1$) is larger than $N$ after $L$ state transitions. If state $s_1$ is revisited from state $s_1$ this is counted as an another visit. I count the visits to state $s_1$ as the number of state transitions that start from $s_1$; that is, the number of times that transitions $s_1 \rightarrow s_0$ and $s_1 \rightarrow s_0$ occur.

I denote by $P_1(n,l|s_i)$ the probability of visiting exactly $n$ times state $s_1$ in $l$ state transitions when the initial state is $s_i$. Then $P(N_1 \geq N | L)$ is
\begin{equation}
P(N_1 \geq N | L)=p_1\sum_{i=N_1}^{L}P_1(i,L|s_1)+p_0\sum_{i=N_1}^{L-1}P_1(i,L|s_0),
\end{equation}

where the second term sums up to $L-1$ only because the initial state is $s_0$. I now compute $P_1(i,l|s_1)$

\begin{equation}
P_1(i,l|s_1)=\sum_{j=1}^{l-i+1}  \underbrace{p_{11}^{i-j}p_{10}^{j}\binom{i-1}{j-1}}_{A0}  \underbrace{p_{01}^{j-1}p_{00}^{l-i-j+1}\binom{l-i}{j-1}}_{B0}+ \sum_{j=1_{l>i}}^{l-i}   \underbrace{p_{11}^{i-j}p_{10}^{j}\binom{i}{j}}_{A1}\underbrace{p_{01}^{j}p_{00}^{l-i-j}\binom{l-i-1}{j-1}}_{B_1},
\end{equation}

where in $A0$-$B0$ and $A1$-$B1$ the final state is assumed to be $s_0$ and $s_1$, respectively.  First I explain $A0$-$B0$. To visit state $s_1$ a total of $i$ times is it necessary to have exactly a total of $i$ $s_1 \rightarrow s_0$ and/or $s_1 \rightarrow s_1$ state transitions. In particular,  there are  $i-j$ and $j$ $s_1\rightarrow s_1$ and $s_1 \rightarrow s_0$ state transitions, respectively. Since the final state is $s_0$, and  $s_1 \rightarrow s_0$ transition occurs $j$ times, there must be a total of $j-1$ $s_0 \rightarrow s_1$  state transitions. The total number of state transitions is $l$, then the total number of $s_0 \rightarrow s_0$ state transitions must be $l-j-i+1$. Now lets focus on $A0$, for each  $s_0 \rightarrow s_1$ transition a set of $s_1\rightarrow s_1$ state transitions may occur (note 1),  the total number of $s_1\rightarrow s_1$ transition sets is $j$ (i.e., number of $s_0 \rightarrow s_1$ transitions plus one). In total there must be $i-j$   $s_1\rightarrow s_1$ state transitions spread over $j$ $s_1\rightarrow s_1$ transition sets, the total number of possible combinations is the is the weak composition (note 2)  of $j$ naturals that sum up to $i-j$ (note 3). $B0$ is obtained similarly, for each $s_1\rightarrow s_0$ transition there might be a set of $s_0\rightarrow s_0$ transitions. Hence there are a total $l-i-j+1$ $s_0\rightarrow s_0$ transitions spread over  $j$ $s_0\rightarrow s_0$ transitions sets.  Hence, the total number of possible combinations  is the weak composition of $j$ natural numbers that sum up to $l-i-j+1$.

Now I will explain $A1$-$B1$. In this case the final state is $s_1$, and the number of $s_1 \rightarrow s_0$ state transitions is the same as the number of $s_0 \rightarrow s_1$ state transitions. The total number of  $s_1 \rightarrow s_0$ and $s_0 \rightarrow s_1$ state transitions is $j$, the total number of $s_1 \rightarrow s_1$ is $i-j$, and the total number of $s_0 \rightarrow s_0$ is $l-j-i$. The total number of $s_1 \rightarrow s_1$ state transition sets is $j+1$, and the total  number of $s_0 \rightarrow s_0$ state transition sets is $j$. The total number possible combinations of having $i-j$ $s_1 \rightarrow s_1$ state transitions spread over $j+1$ transitions sets is the weak combination of $j+1$ natural numbers that add to $i-j$. Following the same rationale, the  total number possible combinations of having $l-j-i$ $s_0 \rightarrow s_0$ state transitions spread over $j$ transitions sets is the weak combination of $j$ natural numbers that add to $l-j-i$.

To compute $P_1(i,l|s_0)$ we can make use of $P_1(i,l|s_1)$,

\begin{equation}
P_1(i,l|s_0)=\sum_{j=1}^{l-i}p_{00}^{j-1}p_{01}P_1(i,l-j|s_1),
\end{equation}

where the term $p_{00}^{j-1}p_{01}$ corresponds to first transition probability from $s_0$ to $s_1$.

It is still needed to check all possible cases, and the limits of the sums. However, I think that this is pretty much it.

Notes

(note 1)A state transition set, is a group of transitions that occur
one after the other, the sets can be empty.
(note 2)The weak composition is the total number of possible combinations of summing
up any $j$ natural number (including $0$) so that they sum up to
$m$, and is given by $\binom{m+j-1}{j-1}$.
(note 3)An explanation for that is the following: each time we go from $s_0$ to state $s_1$ we can stay in $s_1$ for $n$ transitions or to go to $s_0$ directly. In total we must have $i-j$  $s_1\rightarrow s_1$ state transitions, so the sum of all the $n$'s (one for each time we go from $s_0$ to $s_1$) must be equal to $i-j$, the total number of possible combinations of $n$'s is the weak composition of $j$ natural numbers that sum up to $i-j$.

If you are in state 1 then the chance that you will move to state 2 is a geometric distribution with parameter $p_{21}$. Similarly a change from 1 to 2 is a geometric distribution with parameter $p_{12}.

If you start in State 1 (assuming this counts as a visit), then to visit more than $N$ times you need to leave this state and return at least $N$ times. Alternatively, if you start in State 2, you need to leave this state at least $N+1$ times and return $N$ times.

Now the sum of geometric distributions is a negative binomial distribution so your probability is

$$P(n>N)={p_1 \sum_{k=N}^{L-N}NB(N,p_{21})\sum_{j=k}^{L-N}NB(N,p_{12})} + {(1-p_1) \sum_{k=N}^{L-N}NB(N,p_{21})\sum_{j=k}^{L-(N+1)}NB(N,p_{12})} $$

Where $NB$ is the negative binomial probability for $k$ and $j$ as applicable.

Note this is the solution to the question as originally posed, where staying in state $p_1$ does not count as a visit.

For the revised question, the problem can be restated as not being in State 2 for more than $L-N$ steps. A modification of the above should get you there.


$X_n$ are r.v.s, is it true that $E[\sum_{n=1}^{\infty} X_n] = \sum_{n=1}^{\infty} E[X_n] $? $X_n$ are r.v.s, is it true that $E[\sum_{n=1}^{\infty} X_n] = \sum_{n=1}^{\infty} E[X_n] $?

My feeling is that this is not necessarily true. But cannot come up with an example.

Can someone provide a counterexample or give a proof for this statement?

If $X_n$ are defined on the same probability space then the theorem is true and a proof is demonstrated in this question.

If $X_n$ are defined on different probability spaces then clearly $+$ must be defined on them for the question to have any meaning.

If $X$ is defined as the number of Farmer Brown's sheep in the paddock at 10am and $Y$ as the position of an electron in the CERN supercollider at the same time (for some frame of reference) then clearly it is not meaningful to speak of adding them.


What is the best strategy for Cookie-Clicker-esque games? Today, I stumbled across the game Cookie Clicker, which I recommend you avoid until you have at least a few hours of time to waste.

The basic idea behind the game is this:  You have a large stash of currency, which constantly increases at the given rate.  At any given time, you have a series of upgrades, each of which has a cost $c_n$ and each of which has production value $p_n$.  Upon purchasing an upgrade, the cost is deducted from my bank, and the rate of income is increased by the production value.

For example, if I have $1,000$ cookies increasing at a rate of $10$ cookies per second, I could purchase an upgrade $(150,2)$ which will have an end result result of $850$ cookies increasing at $12$ cookies per second.

I stumbled across this question which asked about one possible heuristic, but the heuristic in question was proven to have some flaws.  (I also stole much of my notation from there)

I found the following formula to give the "time improvement" of any single upgrade, which is the amount of time that will be saved by purchasing that upgrade.

$$\text{Time Improvement} =\frac{g-x+\text{min}(0,x-c_1)}{p_0}-\frac{g-x+\text{min}(c_1,x)}{p_0+p_1}$$
Where $p_0$ is current production rate, $x$ is my current stash, and $g$ is the goal as to how many total cookies I want to have.  Basically, this takes into account how long it is expected to take at the current and future rate, and how long it will take to re-earn the spent money/wait to earn the money to spend.  Also, larger values are considered better.

From this, my strategy has been to purchase the upgrade with the highest time improvement.  If I do not yet have enough money to buy the required upgrade, I set that upgrade's cost as my current goal and repeat the strategy.  I don't think this is optimal though.

Although the game has no defined end, I am going set a goal of $4$ billion cookies, enough to buy the antimatter condenser.  Assume that I have an initial rate of $0.1$ cookies per second.   Here is the list of main upgrades in the game, although there are several other powerups:

Cost per item, Increase of cookies per second
15, 0.1
100, 0.5
500, 4
3000, 10
10000, 40
40000, 100
200000, 400
1666666, 6666
123456789, 98765

Upon purchasing an upgrade, the cost of that upgrade increases by $15\%$, although the production value remains the same.

What is the best strategy for games similar to this?  Given a list of upgrades, how should I make my purchases to minimize the time it takes to reach four billion?

You said you were looking for the best time improvement, but the object of the game is to maximize your cookie count. With a long-term strategy you can play the game in bursts by periodically choosing an optimal investment, then letting it run by itself in a background tab for the subsequent period of time.

So let's choose an idle period $T$ of 1 hour or 3600 seconds. The goal then is to maximize your score $C(t)$ at $t=T$ by investing in terms that contribute to $C$, but with the restriction that $C(t) \ge 0$ always. The terms of $C$ correspond to the investments in factories (cursor, grandma, ...).

You can invest in a term $nBt$ where $B$ is the factory's base yield (e.g. grandmas are 15) and $n$ is the number of factories you invested in. However the $i$th factory costs $P\times(1.15)^{i-1}$ where $P$ is the first price. The cost then of $n$ factories is the sum of exponenentials:

$$\sum_{i=1}^n P\times(1.15)^{i-1} = P {1 - (1.15)^n \over 1 - 1.15} \\
= {P\over 0.15} \times (1.15^n - 1)
$$

Assuming you had no factories to start with, and you want to purchase (unknown) $n$ factories to leave it alone for (known) $T$ seconds. Your net gain $G(n)$ at that time is

$$
G(n) = nBT - {P\over 0.15} \times (1.15^n - 1)
$$
The best $n$ in this isolated case is probably found where $G'(n)=0$:
$$
BT - {P\over 0.15}{(1.15)^n \ln 1.15 } = 0\\
n = {\ln 0.15 - \ln\ln1.15 \over \ln1.15}+ {1\over \ln1.15}\ln({BT\over P})\\
n = 0.505822 + 7.155 \times \ln({BT\over P})
$$

So, the sweet spots for T=3600 are

Factory       B          P      n (for T=3600)
--------  -----   --------   ----
Cursor      0.1         15   23.2
Grandma     0.5        100   21.1
Farm          4        500   24.5
Factory      10       3000   18.2
Mine         40      10000   19.5
Shipment    100      40000   16.2
Alchemy     400     200000   14.6
Portal     6666    1666666   19.6

This roughly says that a strategy for maximizing cookies is to buy about 20 of the current best factories, go away and then come back in an hour then sell everything.
Of course it doesn't cover how you get to afford the $n$ units in the first place.
So I have to admit this is at best a first step towards a more complete strategy.

I'd suggest starting buying a few of the smaller ones if your starting out, and move up from there. You definitely want the anti-matter condenser, but those do get pricy. One strategy i have used (and am using as I'm typing this) is to let the game run on it's own for a while, come back, buy a few more things, and continue. This has proven successful on many occasions. I've used this strategy since day one and now have 90,000,000,000 cookies (and counting), and this is only day 2. I also have a a fair amount of "makers", so its not like i'm just stockpiling all my cookies.