Number of ways combination By how many dieffernet way can you place $3$ identical balls in $4$ boxes?
I used  $\binom{n+r-1}n$ =$\binom{6}4=15$ . Is it right?

As there is a fair bit of confusion in some of the comments and in the posted solutions, let me write out an answer.  Throughout I will assume that the boxes are distinguishable.

First of all, a direct count:  There are only three ways to write $3$ as the sum of positive integers $3=3,\;3=2+1,\;3=1+1+1$  Each gives us a pattern for your box fills.

$3=3$, for example, gives us $\fbox 4$ solutions:  $\{3,0,0,0\},\;\{0,3,0,0\},\;\{0,0,3,0\},\{0,0,0,3\}$.  A quicker way to count is to simply remark that the solution is determined by specifying which box gets all the balls and there are $4$ choices.

$3=2+1$ gives us $\fbox {12}$.  The pattern is $\{2,1,0,0\}$ and we have $4$ places to put the $2$ and then $3$ places to put the   $1$, and $4\times 3=12$

$3=1+1+1$ gives us $\fbox 4$ as there are $4$ places to put the $0$.

Combining these we get $$4+12+4=\fbox {20}$$

Second method: Stars and Bars.  This is the formula you are trying to use, but mixing up the variables. To be sure, for larger collections a direct count is impractical so it's good to learn the general technique. To do it properly, write the balls as three stars in a line $$\star\star\star$$  We now insert three bars in the spaces between them and on either side, for example $$\star / \star // \star$$  Interpreting the bars as the gaps between the boxes we see that the indicated pattern corresponds to the solution $\{1,1,0,1\}$. Similarly $$//\star\star/\star$$ corresponds to the solution $\{0,0,2,1\}$ and $$\star\star\star///$$ gives us $\{3,0,0,0\}$.

In this way we see that the set of solutions is in bijection with the ways to place the three stars in six slots.  Hence the answer is $$\binom 63=\fbox {20}$$

I refer you to "Number of ways of distributing n identical objects among r groups" also in the Mathematics section of Stack Exchange.  Looks like you are almost there; the answer is {n+r /choose r} = 35 in your case, if I have understood your question properly. (NB The order in which the balls are placed is not accounted for in a combination calculation, so there are quite a few ways of distributing the balls as, e.g., 2 in 1 box and 1 in another here.)


Example for $\|f_n\|_p = 1$ and $\|f_n - f_m\|_p = 1$ for $m \neq n$ Let $X=[0,1]$ with Lebesgue measure. Let $p = [1,\infty]$. Give an example of $f_n$ such that $\|f_n\|_p = 1$ for all $n$ and $\|f_n - f_m\|_p = 1$ for $m \neq n$.

I find it hard to guarantee $\|f_n - f_m \| = 1$. Anyone has an idea how to make it happen?

Construct such a sequence in $L^p(1,\infty)$, say $g_n(t)=2^{-1/p}1_{(n,n+2)}(t)$ if $n=1,2$ and $g_n(t)=2^{-1/p}( 1_{(2,3)}(t) +1_{(n+1,n+2)}(t))$, and then put $f_n(t)=t^{-2/p}g_n(1/t)$.

To see that the norm of the difference is one just calculate
$$
\int_0^1 |f_n-f_m|^p = \int_0^1 t^{-2}|g_n(1/t)-g_m(1/t)|^p dt =\int_1^\infty |g_n(s)-g_m(s)|^p ds =\| g_n-g_m\|_p^p ,
$$
where we used the change of variables $s=1/t$.


Peano and induction according to Schaum's Outline As some of you may have noticed, I've been coming at Peano from a few different angles. This time I'm stuck on what the Schaum's Outline Abstract Algebra version might mean. Here's Schaum's Peano:

$1 \in \mathbb{N}$.
For each $n \in \mathbb{N},\:$ $\exists!\; n^* \in \mathbb{N}$ called the successor of $n$.
For each $n \in \mathbb{N}$ we have $n^* \neq 1$.
If $m, n \in \mathbb{N}$ and $m^* = n^* \implies m = n.$
Any subset $K$ of $\mathbb{N}$ having the properties (i) $1 \in K$, (ii) $k^* \in K$ whenever $k \in K$ is equal to $\mathbb{N}.$

It then says

  states that the first natural number is $1$

which I can only assume is because 2. says there is a successor to a member of $\mathbb{N}$ called $n^*$ and nothing in $\mathbb{N}$ may have $1$ as a successor. That implies that $1$ cannot have as a successor $1$. To me this only establishes that $1^*$ of $1$ is something else in $\mathbb{N}$, but yes, there is an order to $\mathbb{N}$ where $1$ must be first. Then,

  states that distinct natural numbers $m$ and $n$ have distinct
  successors $m + 1$ and $n + 1$.

Not sure where it is getting $m + 1$ and $n + 1$. This seems like an unwarranted supposition based on a semantic understanding of the word successor, as yet not stated or proven.

Then it goes on with a proposition aimed at establishing induction.

$P(m): m^* \neq m, \quad \forall\, m \in \mathbb{N}$

Then with the five postulates above, it wants to establish the $P$ proposition above. So, define

$K = [k : k \in \mathbb{N}, P(k) \;is\: true]$

  Then  $1 \in \mathbb{N}$ by 1., and $1^* \neq 1$ by 3. Thus, $P(1)$ is true and $1 \in K$. Next let $k$ be any element of $K$, then (a) $P(k): k^* \in k$ is true.

I guess this comes from simply repeating the proposition using items from $K$?

  Now if $(k^*)^* = k^*$ it follows from 4. that $k^* = k$, a contradiction of (a). Hence $P(k^*): (k^*)^* \neq k^*$ is true and so $k^* \in K$. Now $K$ has the two properties stated in postulate 5, thus, $K = \mathbb{N}$ and the proposition is true for all $m \in \mathbb{N}$.

What's eating me is whether the $k^* \neq k$ then $(k^*)^* \neq k^*$ really means "next", i.e., is this enough to really establish a successor as "the next number?" I don't see the original postulates really establishing this -- or are they?

$1 \in \mathbb{N}$.
  For each $n \in \mathbb{N},\:$ $\exists!\; n^* \in \mathbb{N}$ called the successor of $n$.
  For each $n \in \mathbb{N}$ we have $n^* \neq 1$.
  If $m, n \in \mathbb{N}$ and $m^* = n^* \implies m = n.$
  Any subset $K$ of $\mathbb{N}$ having the properties (i) $1 \in K$, (ii) $k^* \in K$ whenever $k \in K$ is equal to $\mathbb{N}.$

Maybe it would help to visualize the set of natural numbers with arrows indicating succession.

$1\to 2 \to 3 \to 4 \to \cdots$

In this chain of numbers:

There is exactly one outgoing arrow from each number, i.e. the successor relation is a function (axiom 2).
$1$ has no incoming arrow, i.e. no number has a successor of $1$ (axiom 3).
Every number has at most one incoming arrow, i.e. the successor function is one-to-one or injective (axiom 4).
There are no natural numbers that will not be included in the chain of numbers pictured above. In other words, you would be able to reach any number if you start at $1$ and repeatedly went from one number to the next (axiom 5).


Minimum value of $|z-w|$ where $z,w \in \mathbb C$ such that $|z|=11$, and $|w+4+3i|=5$? I was thinking about the problem:

What is the minimum value of $|z-w|$ where $z,w \in \mathbb C$ such that $|z|=11$, and $|w+4+3i|=5$?

My attempts: I notice that $|z-w| \geq |z|-|w|=11-|w|$. Also if i take $w=u+iv$ then $|w+4+3i|=5$ gives $|w|^2+8u+6v=0$. Now i can not proceed. Can someone point me in the right direction? Thanks in advance for your time.

Let $z=a+bi$ and $w=c+di$.

Now, $|z|=11\implies \sqrt{a^2+b^2}=11\implies a^2+b^2=121$, so $z$ is constrained to this circle (shown in blue below).

On the other hand, $|w+4+3i|=5\implies \sqrt{(c+4)^2+(d+3)^2}=5\implies (c+4)^2+(d+3)^2=25$, so $w$ is constrained to this circle (in red below).

The task is to minimize $|z-w|=\sqrt{(a-c)^2+(b-d)^2}$ subject to the two constraints above. Geometrically, we are looking to find the shortest distance between any two points which lie on the blue and red circles, respectively. A little calculus reveals the minimum is $1$ and is obtained when $a=-44/5$, $b=-33/5$ and $c=-8$, $d=-6$, as shown below.


Do you write plus/minus if a variable squares equals the square root of a number? For example, if I have $x^2 = \sqrt{49}$. I know that $7$ is the number, but as my final answer, do I write that $x = +\sqrt{7}$ and $-\sqrt{7}$ or just $x = \sqrt{7}$?

For any $a>0$, if you have an equation $x^{2}=a$, then note that both $(\sqrt{a})^{2}=a$ and $(-\sqrt{a})^{2}=a$. Thus, both $a$ and $-a$ are solutions, and hence, they must both be considered. In your case, you have $x^{2}=\sqrt{49}=7$. Therefore, both $x=\sqrt{7}$ and $x=-\sqrt{7}$ satisfy this equation.

It depends on which field you expect/require the answer to be in:

If the answer is allowed to be a complex number, then the equation $x^2 = \sqrt{49}$ can be rewritten as $x^2 = 7$ OR $x^2 = -7$, which collectively yield four values: $x = +\sqrt{7}$, $x = -\sqrt{7}$, $x = +i\sqrt{7}$, and $x = -i\sqrt{7}$.

If the answer is required to be a real number, then the equation $x^2 = \sqrt{49}$ can be rewritten as $x^2 = 7$ OR $x^2 = -7$, which, since $x^2 = -7$ has no real solution, yields only two values: $x = +\sqrt{7}$ and $x = -\sqrt{7}$.

If the answer is required to be a rational number, or a number in an extension of the rationals which does not contain $\sqrt{7}$, then of course there is no solution.


Justifying a recurrence relationship I have a recurrence relationship here that I have to justify:

$A_n = A_{n-1} + A_{n-2} + 1 $ and $A_0 $ = 1 and $A_1 $ = 1

I know that the first step is to turn this into a characteristic equation of order 2, and then go on to solve that equation. I can't seem to get over that first hump in finding the characteristic equation for the above recurrence relationship. I think it's the + 1 that's stopping me from being able to factor out $x^{n-2} $ to find the appropriate quadratic equation to solve. I just wanted to know how I can go about starting this one as I know how to do the rest.

Like we do for linear ODEs, we can talk about homogeneous equation and particular solution.

Here homogeneous equation is $A_n=A_{n-1}+A_{n-2}$ or similarly $A_{n+2}-A_{n+1}-A_n=0$

leading to characteristic equation  $r^2-r-1=0$ with solution $r=\varphi,\bar\varphi$

And $A_n=a\,\varphi^n+b\,\bar\varphi^n$ characteristic of Fibonacci sequence.

Now when considering the whole equation with an RHS, you need to find a particular solution for it. Equation's linearity ensures that the sum of the general homogeneous solution and the particular solution is the overall general solution.

Here there is an obvious particular solution $A_n=-1$ since $-1=-1-1+1$.

But you can also search for polynomial solutions $A_n=(cn+d)$ and after substitution find $cn+d=2cn+2d-3c+1\iff c=0,d=-1$.

Finally, $A_n=a\,\varphi^n+b\,\bar\varphi^n-1$ and you find $a,b$ so that the values for $A_0$ and $A_1$ agree to initial conditions.

$\begin{cases}A_0=a+b-1=1\\ A_1=a\varphi+b\bar\varphi-1=1\end{cases}\iff\begin{cases}a=1+\dfrac 1{\sqrt{5}}\\b=1-\dfrac 1{\sqrt{5}}\end{cases}$

  $A_n=(\varphi^n+\bar\varphi^n)+\frac 1{\sqrt{5}}(\varphi^n-\bar\varphi^n)-1$

For this specific case, it can be observed that it is $2$ times the Fibonacci Sequence's closed form minus $1$.

So that is,

$$\frac{2}{\sqrt 5}\left( \left( \frac{1+\sqrt 5}{2} \right)^n - \left( \frac{1- \sqrt 5}{2} \right)^n \right) -1$$

One can prove this with induction.


Substitution To Find Most General Unifier Could someone give me some advice on how to do this problem?

For the the following pair of expressions, find the substitution that is
the most general unifier (mgu) or explain why the two expressions cannot be unified. b and c are constants, f and g are functions, and w, x, y, z are variables.

Thanks.

A unifier of two terms $t$ and $t$' is a substitution function $\phi$ that maps variables to terms such that $\phi t = \phi t'$, i.e., applying $\phi$ to the variables in each term yields the same term. For example, given $t = f(x)$ and $t' = f(a)$ where $a$ is a constant and $f$ is a function name (not a variable) then $\phi\ x \mapsto a$ is a unifier since $\phi t = f(a) = \phi t'$.

The unifier $\phi$ for $t$ and $t'$ is the most general unifier if for any other unifier $\psi$ (s.t. $\psi t = \psi t'$) then their exists some other unifier $\Phi$ such that $\psi = \Phi \circ \phi$, i.e., $\psi$ factors through $\phi$.  For example, given $t = f(x, a)$ and $t' = f(y, a)$ then $\psi\ x \mapsto c, \psi\ y \mapsto c$ is a unifier, but it is not the most general. The most general is $\phi\ x \mapsto y$, since $\psi$ factors though $\phi$ with $\Phi\ y \mapsto c$ (or equivalently $\phi\ y \mapsto x$ and $\Phi\ x \mapsto c$). The usual simple unification algorithm will generate an mgu; basically just pick the simplest unification (unify variables to variables, not to some other constants/ground terms).

Parameter 1:
w and y : matching, variable w has to be replaced by y.
Parameter 2:
c and z : matching, variable z has to be replaced by constant c.
Parameter 3:
f(w,b,w) and y: after variable replacement w to y
f(y,b,y) and y: y cannot be replaced by f(y,b,y), it is a recursive call. It cannot be unified.


Diamond in Subtle Cardinals In the Jensen-Kunen manuscript on combinatorial principles, they define the notion of a subtle cardinal:

Definition. A regular cardinal $\kappa$ is subtle if for all $C$ club, $(A_\alpha)_{\alpha\in C}$ a sequence such that $A_\alpha\subseteq\alpha$ for all $\alpha$, there exists $\alpha,\beta\in C$ such that $\alpha<\beta$ and $A_\alpha=\alpha\cap A_\beta$.

They then proceed to show that $\lozenge(\kappa)$ holds for $\kappa$ subtle with the following argument:

By induction on limit $\alpha<\kappa$ define $(S_\alpha,C_\alpha)$ such that $S_\alpha\subseteq \alpha$, $C_\alpha$ club in $\alpha$ and $\forall\gamma\in C_\alpha\;S_\gamma\ne\gamma\cap S_\alpha$ if possible.
Claim: Let $S\subseteq\kappa$, then $\{\alpha<\kappa\;\vert\;S\cap\alpha=S_\alpha\}$ is stationary.
Proof: Suppose not. Then there is a pair $(S,C)$, $C$ club in $\kappa$ and $\forall\alpha\in C\;S_\alpha\ne\alpha\cap S$.
Let $C^*$ be the set of limit points in $C$. Then $a\in C^*\to\forall\gamma\in C_\alpha\;S_\gamma\ne\gamma\cap S_\alpha$.
By the subtlety of $\kappa$, however, there are $\alpha,\beta\in C^*$ such that $\alpha<\beta$, $C_\alpha=\alpha\cap C_\beta$, $S_\alpha=\alpha\cap S_\beta$. Hence $\alpha\in C_\beta$. Contradiction!

I'm trying to understand this proof but have a few questions. First of all, how do we know that $C_\alpha$ and $C_\beta$ are defined? The definition of $(S_\alpha,C_\alpha)$ says "if possible" so what if at $\alpha,\beta$ it is not possible to find these sets?
Secondly, the definition gives us a way to find $\alpha,\beta$ such that $A_\alpha=\alpha\cap A_\beta$, but how does one do this for $(S_\alpha,C_\alpha)$ simultaneously as in the proof? Would it be necessary to code $\kappa\times\kappa$ with $\kappa$ by some bijection?

Regarding your first question: Say that we've constructed $((S_\alpha, C_\alpha) \mid \alpha < \beta)$ for some $\beta < \kappa$. There are two cases:

$(\dagger)$If there is some $S \subseteq \alpha$ such that $\{ \beta < \alpha \mid S_\beta \neq S \cap \beta \}$ is non-stationary, we may fix a club $C \subseteq \alpha$ such that for all $\beta \in C \colon S_\beta \neq S \cap \beta$. In this case let $C_\alpha := C$ and $S_\alpha := S$. (We need some choice to pick these $C$'s and $S$'s at every stage.)

Otherwise let $C_\alpha := S_\alpha := \alpha$.

Before we repeat the proof with more details, let us verify the following:

Lemma. Let $\kappa$ be subtle. Then for every club $C \subseteq \kappa$ and for every sequence $( (A_\alpha, B_\alpha) \mid \alpha < \kappa)$ such that $A_\alpha, B_\alpha \subseteq \alpha$ there exist $\alpha < \beta$ such that $\alpha, \beta \in C$, $A_\alpha = A_\beta \cap \alpha$ and $B_\alpha = B_\beta \cap \alpha$.

Proof. For each $\alpha < \kappa$ let $C_\alpha := \{ \langle x, y \rangle \mid x \in A_\alpha, y \in B_\alpha \} \cap \alpha$, where $\langle ., . \rangle \colon \operatorname{Ord} \times \operatorname{Ord} \to \operatorname{Ord}$ is the Gödel pairing function. Fix a club $D \subseteq \kappa$ such that for all $\alpha \in D$ we have $x,y < \alpha \to \langle x,y \rangle < \alpha$. (Since $\kappa$ is regular, such a club exists. You can use the normal function theorem to prove this.)

Now $E := D \cap C$ is a club and since $\kappa$ is subtle, there exist $\alpha < \beta$ such that $\alpha, \beta \in E$ and $C_\alpha = C_\beta \cap \alpha$. Since $\alpha$ is closed under the Gödel pairing function, we may recover all of $A_\alpha$ and all of $B_\alpha$ from $C_\alpha$. In fact, we have
$$
A_\alpha = \{ x < \alpha \mid \exists y < \alpha \colon \langle x,y \rangle \in C_\alpha \}
$$
and similarly for $B_\alpha, A_\beta, B_\beta$.

Hence $A_\alpha = A_\beta \cap \alpha$ and $B_\alpha \cap B_\beta \cap \alpha$. Q.E.D.

Let $((S_\alpha, C_\alpha) \mid \alpha < \kappa)$ be the sequence that we've constructed above.

Claim.  $(S_\alpha \mid \alpha < \kappa)$ witnesses $\Diamond_\kappa$.

Proof. Suppose not. Then there is some $A \subseteq \kappa$ such that $\{ \alpha < \kappa \mid S_\alpha = A \cap \alpha \}$ is not stationary. Fix a club $C \subseteq \kappa$ such that for all $\alpha \in C \colon A \cap \alpha \neq S_\alpha$ and let $C^*$ be the club of all limit points of $C$. If $\alpha \in C^*$, then $C \cap \alpha$ is a club in $\alpha$ and for all $\beta \in C \cap \alpha \colon A \cap \beta \neq S_\beta$. Therefore, in our construction, we could have picked $C_\alpha := C \cap \alpha$ and $S_\alpha := A \cap \alpha$. In particular, for all $\alpha \in C^*$ we are in the "first case" $(\dagger)$ of our construction.

By the Lemma above, we may now pick $\alpha < \beta$, $ \alpha, \beta \in C^*$ such that $C_\alpha = C_\beta \cap \alpha$ and $S_\alpha = S_\beta \cap \alpha$. Since $C_\alpha$ is unbounded in $\alpha$ and $C_\beta$ is closed, we have $\alpha \in C_\beta$. But $S_\beta \cap \alpha = S_\alpha$ - contradicting the fact that we have been in the "first case" $(\dagger)$ of our construction at stage $\beta$. Q.E.D.

The proof of the lemma in the answer fails if $A_\alpha$ or $B_\alpha$ is empty; then reconstruction from $C_\alpha$ fails. A simpler argument works. Take the club consisting of $\alpha$ such that for all $\beta \leq \alpha$, $2\beta+1 < \alpha$. Then let $C_\alpha = \{2 \beta:\beta \in A_\alpha\}\cup \{ 2 \beta+1:\beta \in B_\alpha\}$


How to show that $\sigma(n)=k$ has a finite # of solutions $k\in\mathbb{N}$? I wish the question is clearly explained in the title. Thanks in advance.

Since $n$ divides $n$ then
$
k=\sigma(n) \ge n.
$
Hence there are at most $k$ solutions.


Permutation and Combination I'm currently learning permutation and combination in my discrete math class and I'm kind of lost. So I know this is the general set of formulas:

r-permutations    no repetition    n!/(n-r)!
r-combinations    no repetition    n!/r!(n-r)!
r-permutations    repetition       n^r
r-combinations    repetition       (n+r-1)!/r!(n-1)!

But when do I know a problem allows repetition or not? This may sound like a really stupid question to people who already know this pretty well but I'm new to this and don't really understand.

Figuring out how to interpret a real world situation can be quite hard.I think that best approach is practice.On this page you can find some examples how to apply formulas on real world situations.

I have 100 books for 100 users, I want to distribute 1 book to 1 user for 1 week. How many weeks I can distribute all the 100 books to all the 100 users without repetition of the book to the users?

What is the formula to calculate this?

Thanking you for the help.


Discrete Mathematics - Trees Question: Prove that if a tree has a node of degree $n$, it has at least $n$ nodes of degree $1$.

My answer: From each of $n$ edges adjacent to the node of degree $n$ a path starts. Each of these paths eventually ends in a leaf. Since the tree has no cycles, then all these leaves are different, hence the tree has at least $n$ leaves, and degree of a leaf is $1$, thus, the tree has at least $n$ nodes of degree $1$.

I'm not sure about the strength of this argument. Can anybody give me some idea about my answer please.

Let v be a node with degree n in a finite graph.
Let v(k) be the k-th vertex for which v,v(k) is an edge.
Let p(k) be a path of maximal length from v through v(k).
As the path has no loops and is finite it will end in a leaf.

Now prove there are at least n leaves.

Suppose the tree has $k$ vertices.Then it has $k-1$ edges.

Assume on the contrary that there are at most $n-1$ leaves. Then the number of edges is at least:
$$\frac{n+(n-1)+2(k-n)}{2}=\frac{2k-1}{2} > k-1$$
Contradiction.


Prove ca ≡ cb (mod m) if and only if a ≡ b mod (m/gcd(c, m) ) I can't seem to answer this question without assuming that gcd(c,m) = 1. Is the question missing any information?

Let $g=\gcd(c,m)$ and write $c=gd$, $m=gn$.  Then $\gcd(d,n)=1$, because otherwise $g$ would not be the greatest common divisor of $c$ and $n$.  Therefore
$$\eqalign{
  ca\equiv cb\pmod m
  &\iff m\mid ca-cb\cr
  &\iff gn\mid gd(a-b)\cr
  &\iff n\mid d(a-b)\cr
  &\iff n\mid a-b\cr
  &\iff a\equiv b\ \Bigl({\rm mod}\frac{m}{\gcd(c,m)}\Bigr)\ .\cr}$$
Note that the second last step is true because $\gcd(d,n)=1$.

Let $\,d=a\!-\!b.\,\ m\mid cd\iff m\mid cd,md\!\!\overset{\large\ \ (1)}\iff m\mid (cd,md) = (c,m)d\iff m/(c,m)\mid d$

where in $(1)$ we used the GCD Universal Property and the GCD Distributive Law


Rigorous definition of sum of two random variables? I've looked everywhere, but I seem unable to find a rigorous definition (in the set-theoretical sense of a random variable being a mapping from a sample space to the real number line) of the sum of two random variables (X + Y).

How do you rigorously define the sum of two random variables X + Y?

Given random variables $X, Y : \Omega\to\mathbb R$ defined on the same probability space $\Omega$, the definition of $X+Y$ is simply the pointwise sum:
$$(X+Y)(\omega) = X(\omega)+Y(\omega)$$
If $X$ and $Y$ are defined on different probability spaces, $X:\Omega_1 \to \mathbb R$ and $Y:\Omega_2 \to \mathbb R$, then $X+Y$ is undefined. However, in this case we can define a new probability space $\Omega = \Omega_1 \times \Omega_2$ and random variables $X_1, Y_1$ on $\Omega$ by
\begin{align*}
X_1(\omega_1,\omega_2) &= X(\omega_1)\\
Y_1(\omega_1,\omega_2) &= Y(\omega_2)
\end{align*}
in which case $X_1$ has the same distribution as $X$, $Y_1$ has the same distribution as $Y$, and $X_1$ and $Y_1$ are independent. In this case, the sum $X_1+Y_1$, which is defined pointwise as above, may be considered as a replacement for the non-existent sum $X+Y$, as long as independence between the two summands is what we were looking for.

It actually defined as an analogue of the product of the polynomial with $X, Y$ independent and P was defined in double dimension

$$(P(x + y) = t) =  \sum_{I = 0}^t f_x(I)g_x(t - I)$$


All periods in string I want to find all the periods in a string. Moreover, I want to do it in a linear time and using a prefix function. I've noticed a pattern, that I want to generalize to an algorithm, though, unfortunately, I am not able to achieve O(len(s)) time, so I'd like to get some clues, how to optimize the algorithm.

Here is what I came to. Consider a string and prefix function (just like in KMP algorithm):

abababab

00121234

I have noticed, that if we have a period of length t, then in indices k * t for natural k >= 2 value of prefix function is >=t. The problem is that if I'd check all the prefixes of given string to satisfy this condition, then it would obviously take O(len(s)^2) time. What can be done to improve the speed of the algorithm?

This is already way too late. But shouldn't this be $O(n \log{n})$? $n$ being $len(s)$. You are doing $\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n} $ work, which integrates to $n \ln{n}$.

Prefix function precomputation is $O(n)$, so it wouldn't matter.


Number theory congruence Prove that $n^{12} - a^{12}$ is divisible by $91$ if $n$ and $a$ are co prime to $91$

What I tried:

$91$ divides $n^{12}-a^{12}$
Therefore $n^{12}-a^{12}=91k$
But $91=13\times7$
$n^{12}-a^{12}=(13\times7)k$
$n^{12}=(13\times7)k+a^{12}$
$n^{12}$ divides $91$
Therefore $n$ is co prime to $91$

Suppose $n,a$ are integers, relatively prime to $91$.

Since $91=7\cdot 13$, it follows that $n,a$ are relatively prime to $7$ and $13$.

Applying Fermat's little Theorem with the prime $13$, we get
\begin{align*}
&\begin{cases}
n^{12}\equiv 1\;(\text{mod}\;13)\\[4pt]
a^{12}\equiv 1\;(\text{mod}\;13)\\
\end{cases}\\[4pt]
\implies\;&n^{12}-a^{12}\equiv 0\;(\text{mod}\;13)\\[4pt]
\implies\;&13{\,{\mid}\,}\bigl(n^{12}-a^{12}\bigr)\\[4pt]
\end{align*}
and applying Fermat's little Theorem with the prime $7$, we get
\begin{align*}
&\begin{cases}
n^{6}\equiv 1\;(\text{mod}\;7)\\[4pt]
a^{6}\equiv 1\;(\text{mod}\;7)\\
\end{cases}\\[4pt]
\implies\;&\begin{cases}
n^{12}\equiv 1\;(\text{mod}\;7)\\[4pt]
a^{12}\equiv 1\;(\text{mod}\;7)\\
\end{cases}\\[4pt]
\implies\;&n^{12}-a^{12}\equiv 0\;(\text{mod}\;7)\\[4pt]
\implies\;&7{\,{\mid}\,}\bigl(n^{12}-a^{12}\bigr)\\[4pt]
\end{align*}
hence, since $7{\,{\mid}\,}\bigl(n^{12}-a^{12}\bigr)$ and $13{\,{\mid}\,}\bigl(n^{12}-a^{12}\bigr)$, it follows that $91{\,{\mid}\,}\bigl(n^{12}-a^{12}\bigr)$.

As regards your proof attempt, the problem doesn't ask you to prove that $n$ is relatively prime to $91$.

It's given that $n,a$ are relatively prime to $91$, and the goal is to prove that $91{\,{\mid}\,}\bigl(n^{12}-a^{12}\bigr)$.

Note that in the first line of your proof attempt, you assume what you are required to prove, and of course, that's not a legal assumption.

Two things should leap to mind.  And a third thing comes with practice.

1) $91 = 13*7$ so to prove $91|M$ it will work to prove a) $7|M$ and b) $13|M$.  If you can prove a) and b) you are done.

2) $n^{12} - a^{12} = (n^6 - a^6)(n^6 + a^6) = (n^3 - a^3)(n^3 + a^3)(n^6 + a^6)=....$.  The expression $n^{12}-a^{12}$ is "very" factorable.  If we can prove that of the many factors that $7$ and/or $13$ must divide at least one of the factors that will help.  There are so many factors something working out is likely.

And with practice:

3) $12 = 13 -1$ and $13$ is prime.  So Euler's Theorem/Fermats Little Theorem will probably come into play.

.....

Factor $n^{12} -a^{12}$ completely.

$n^{12}-a^{12} = (n-a)(n^11 + n^10a + .... +na^{11} + a^{12})=$

$(n^2 - a^2)(n^{10} + n^8a^2 + .... + n^2a^8 + a^{10})=$

$(n^3 - a^3)(n^9 + n^6a^3 + n^3a^6 + a^9)=$

$(n^4-a^4)(n^8 + n^4a^4 + a^8)=$

$(n^6 - a^6)(n^6 + a^6) =$

$(n^6+a^6)(n^3 + a^3)(n^2+a^2)(n+a)(n-a)$.

Those probably have different remainders when divided by $7$ or $13$.  One of them can probably be proven to be $0$. but... that may be hard to figure out.  Let's put a pin in it and look at 3)

3) Fermat's little theorem states if $\gcd(k,13)=1$ then $k^{12}\equiv 1 \pmod {13}$.  And $n,a$ are coprime to $91$ so they are coprime to $13$ so

$a^{12} \equiv 1 \pmod {13}$ and $n^{12} \equiv 1 \pmod {13}$ so $n^{12}-a^{12}\equiv 1-1 \equiv 0 \pmod 13$ so $13|(n^{12} - a^{12})$.

So now we just need to prove $7|n^{12} - a^{12}$....

Back to the factoring... oh, wait!....

Fermat's Little Theorem states $n^6\equiv 1\pmod 7$ and $a^6\equiv \pmod 7$ so $n^{12}-a^{12} = (n^6- a^6)(n^6 + a^6)\equiv (1-1)(n^6 + a^6)\equiv 0 \pmod 7$ so $7|n^{12}-a^{12}$.

And we are done!

We didn't need to do that factoring stuff at all.

Still it'd be interesting to see if we can do it by considering just the factors.  But we don't have to.


Find the smallest positive integer for which x mod 3 = 2 and x mod 4 = 3 I came across a question on a piece of homework and my solution yields no possible solutions.

Find the smallest positive integer for which
x mod 3=2 and x mod 4=3 (and then find the next one)

So I figure (by the Quotient-Remainder Theorem)

n mod 3 = 2 => n = 3q + 2
n mod 4 = 3 => n = 4q + 3

No problems thus far and everything works out fine logically so I set the equations equal to each other and find that q = -1.
Wait, it can't be negative. So I put it on a graph to check my comprehension and like I thought that is the only point at which they meet is outside my possible domain.
Could someone point out the error in my logic here? Or perhaps I've misinterpreted the question? Apologies if the answer is simple and I've missed it.

If $x\pmod4\equiv3$, then $x=4k+3$ for some integer $k$.  Considering this equation modulo $3$, we get

$$x\equiv k\equiv2\pmod3$$

So for some integer $a,k=3a+2$.  Combining these, we get

$$x=4k+3=4(3a+2)+3=12a+11$$

well, guy, you can solve your problem using modular arithmetic and I think this is the best way for this problem.
pay attention:

x≡2 in base 3
In base 4    x≡3
We can say:
 x≡-1  in base 3  and   x≡ -1 in base 4
According to modular arithmetic rules we have:
x≡ -1 in base 12
As a result, x can be written in form of (x =  12k – 1)
If k = 1, then x is 11 which is the smallest integer with the properties mentioned in the problem.
By giving positive integers to k, we can create more numbers:
(k = 1) x = 11, (k = 2) x = 23, (k = 3) x = 35 and …


The abelian subgroups are subgroups of the normalizer of intersection of the subgroups. Suppose $P$ and $Q$ are subgroups of order $9$ with $|P\cap Q|=3$. Why is it that $P$ and $Q$ are subgroups of the $N_G(P\cap Q)$.

The only thing I know is that $P\cap Q$ is a subgroup of $P$ (as well as Q). Also since the order of P(same with $Q$) is $9$ (which is $3^2$) and so abelian which implies that $P\cap Q$ is normal in $P$ (also in $Q$). Is it useful? Please enlighten me.Why is it that $P$ and $Q$ are subgroups of the $N_G(P\cap Q)$.

Let $p\in P$, $q\in Q$, and $a\in P\cap Q$ be arbitrary.

To show that $P$ and $Q$ are both subgroups of $N_G(P\cap Q)$, it suffices to show that $pap^{-1}$ and $qaq^{-1}$ are both in $P\cap Q$. Since both $P$ and $Q$ are abelian, we have that $pap^{-1} = a = qaq^{-1}$ which must be in $P\cap Q$ by assumption about $a$.

Thus, both $P$ and $Q$ are subgroups of $N_G(P\cap Q)$.

Note that this is true for any pair of abelian groups $A,B\le G$. If $a\in A$, $b\in B$, and $x\in A\cap B$, then $x = axa^{-1} = bxb^{-1}$. Thus $A,B\le N_G(A\cap B)$.


Number of $K_{10}$ always increases Let $G=(V,E)$ be a graph with $n\geq 10 $ vertices. Suppose that when we add any edge to $G$, the number of complete graphs $K_{10}$ in $G$ increases. Show that $|E|\geq 8n-36$.

[Source: The probabilistic method, Alon and Spencer 3rd ed., p.12, problem 5]

For the base case $n=10$, we know $G$ must have $44=8\cdot 10-36$ edges.

We know every vertex in $G$ must have degree $\geq 8$; otherwise adding an edge connecting that vertex cannot increase the number of $K_{10}$. This gives $|E|\geq 4n$.

The solution to this problem uses a clever application of Theorem 1.3.3 (in "The Probabilistic Method, 3rd edition").  Since not everyone has access to the text, I will state the theorem (with necessary definitions) here first.

Definition: Let $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ be a family of pairs of subsets of an arbitrary base set.  $\mathcal{F}$ is a $(k,\ell)$-system if $|A_{i}|=k$ and $|B_{i}|=\ell$ for $1\leq i\leq h$, $A_{i}\cap B_{i}=\emptyset$ for all $1\leq i\leq h$, and $A_{i}\cap B_{j}\neq \emptyset$ for all $i\neq j$ with $1\leq i, j\leq h$.

Theorem (1.3.3) If $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ is a $(k,\ell)$-system, then $h\leq \binom{k+\ell}{k}$.

Now, the strategy to solve the original problem is to create a cleverly chosen $(k,\ell)$-system and apply the result.

Let $h$ be the number of edges not in $G$ and list the non-edges of $G$ as $\{e_1, e_2, ..., e_h\}$.  For each $e_{i}$ associate a set of 10 vertices that form a $K_{10}$ if $e_{i}$ were to be added to $G$.  The hypothesis guarantees that there is at least one such set of $10$ vertices; if there is more than one, pick one arbitrarily.  We will call this "potential" $K_{10}$, $K_{10}^{i}$ to denote that it is formed by adding edge $e_{i}$.  Each edge $e_{i}$ has two endpoints, call them $v_{i, 1}$ and $v_{i,2}$.  Form the set $A_{i}=\{v_{i, 1}, v_{i, 2}\}$.  Form the set $B_{i}=V(G)-V(K_{10}^{i})$, i.e. all the vertices in $G$ that are not in $K_{10}^{i}$, the chosen $K_{10}$ formed by adding edge $e_{i}$.  We want to verify that $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ is a $(2, n-10)$-system.

Clearly, $|A_{i}|=2$ and $|B_{i}|=n-10$ for $1\leq i\leq h$.  Also clear is that $A_{i}\cap B_{i}=\emptyset$ for $1\leq i\leq h$ since the vertices in $A_{i}$ are contained in $K_{10}^{i}$.  For any $i\neq j$ note that at least one vertex of $e_{i}$ is not in $K_{10}^{j}$ otherwise, both $e_{i}$ and $e_{j}$ would need to be added to make $K_{10}^{j}$ a complete graph.  Thus, at least one vertex in $A_{i}\in B_{j}$ implying that $A_{i}\cap B_{j}\neq \emptyset$.  Thus, we do have a $(2, n-10)$-system.

By the theorem 1.3.3, $h\leq \binom{2+(n-10)}{2}=\binom{n-8}{2}$.  Since $h$ counts the number of non-edges of $G$, we can conclude that $G$ has at least $\binom{n}{2}-\binom{n-8}{2}$ edges.

And, (the easy part)
\begin{align*}
\binom{n}{2}-\binom{n-8}{2} &= \frac{1}{2}\left(n(n-1) - (n-8)(n-9)\right) \\
&= \frac{1}{2}\left(n^2-n -(n^2 - 17n + 72)\right) \\
&= 8n-36.
\end{align*}

You already have most of the needed information for a proof. Using induction and very little additional work, you'll have your proof.

We'll say graph $G$ has property $\mathcal{P}$ if adding any extra edge will increase its number of $K_{10}$s. Say, you have such a $G$ with $n > 10$ vertices. Now, what can you say (with respect to property $\mathcal{P}$) about the graph with $n-1$ vertices obtained by deleting an arbitrary vertex $v$ from $G$? You can use this answer, minimum degree information of $v$ and the principle of induction to finish the proof.


Find a formula for the Jones polynomial of the disjoint union of two diagrams $K_1$ and $K_2$ Find a formula for the Jones polynomial of the disjoint union of two diagrams $K_1$ and $K_2$.

I am having a lot of trouble with this seemingly easy question. I understand that a Jones polynomial looks like this:

$$V_K(t) = L_K(t^{-1/4}), \text{where}$$
$$L_K(A) = (-A^3)^{- \omega (K)} \cdot \langle K \rangle$$

But I don't understand how to apply this to two disjoint diagrams. Any help would be appreciated.

Update: Online resources have been telling me to using the Skein relation, and so I feel as if the approach I'm taking is not good.

$V(Sn)(t) = (-t^{-1/2} - t^{1/2})^{n-1}$ where $Sn$ is a n component unlink. This result comes from An Introduction to Quantum and Vassiliev Knot Invariants by David M. Jackson Iain Moffatt, P30.


Upper bound to a series with binomial coefficients Let $c>0$ and $m$ be a positive integer. The following sum is convergent, but how fast does it grow with $m$ as $m$ is large?
$$
f(m)= \sum\limits_{n=1}^{\infty} \binom{n + m}{n} e^{-c \,  n}
$$

Is there a polinom in $m$, $g(m)$, such that
$$f(m) \leq g(m) ?$$

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\mc}[1]{\,\mathcal{#1}}
 \newcommand{\mrm}[1]{\,\mathrm{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\color{#f00}{\mrm{f}\pars{m}} & \equiv
\sum_{n = 1}^{\infty}{n + m \choose n}\expo{-c\, n}
\\[5mm] & =
\sum_{n = 1}^{\infty}{-\pars{n + m} + n - 1 \choose n}\pars{-1}^{n}\expo{-c\, n}
\quad\pars{~Binomial "Negation"~}
\\[5mm] & =
\sum_{n = 1}^{\infty}{-m - 1 \choose n}\pars{-\expo{-c}}^{n} =
\bracks{1 + \pars{-\expo{-c}}}^{-m - 1}\,\,\, -\,\,\, 1\quad
\pars{~Newton\ Binomial~}
\\[5mm] & =
\color{#f00}{{1 \over \pars{1 - \expo{-c}}^{m + 1}} - 1}
\end{align}


Why hyperreal numbers are built so complicatedly? I have seen approaches at building hyperreal systems by using complicated notions like ultrafilters and the like.

Why not just postulate the existence of infinitesimal element $\varepsilon$ and infinite $\omega=1/\varepsilon$ like we do with complex numbers and build a field system around them?

There are ways to build a field by throwing in an infinitesimal to the reals and then whatever else you need. For example, the field of formal Laurent series (ordered so that monomials with positive coefficients are first ordered by the power of x, e.g. $0 <x <1<100<1/x$) is basically that. The Levi-Civita field is similar.

However, neither of those actually have the properties needed to answer questions about calculus. You need to throw a lot in in just the right way to get all simple statements to pass through, as Nate Eldredge alluded to.

As an aside, the basic idea behind of the construction isn't too complicated. I like Terry Tao's voting analogy. A hyperreal is a sequence of reals that vote each time you ask about a property  (like "are you bigger than 5?"). How to determine which infinite collections of voters count as good majorities is handled by some technical stuff, but you don't have to worry about that to get the idea.

Details matters!

As an example, if you just postulate the existence of infinitely big naturals you will have troubles because

$\{\omega \in \Bbb{N} \ : \ \omega \ \mbox{is infinitely big}\}$

is a non-empty set without minimum.

Those complicated constructions arised to avoid this and a lot of other gaps that could appear if we are not careful enough.


How can I find videos of mathematics at graduate level, especially on linear algebraic groups I am studying mathematics by myself, and I find it very helpful to watch online course videos.

There are many such videos on undergraduate courses, such as elementary calculus, abstract algebra, general topology and so on. But, it is difficult for me to find videos at graduate level. I find this, but most of the courses provide only notes.

So, would you please share some links of videos of mathematical courses at graduate level? Or of videos that are enlightening to a mathematical student at this level? Especially on Linear Algebraic Groups, Algebraic Geometry and related topics.

Thanks for answering. Also, many thanks to the colleges and teachers providing these videos, which are really very precious for studying math.

Here is a link to about 40 hours of lectures given in 2007/08 by L. Goettsche on Algebraic Geometry as part of the Postgraduate Diploma program at the Abdus Salam International Centre for Theoretical Physics in Trieste, Italy.

There are many at DNAtube, such as: http://www.dnatube.com/video/6899/A-Par ... DE-Formula , and many others from this author. And more on YouTube, such as at: http://www.youtube.com/watch?v=4JFFLruvqP4 by the same author. But Algebraic Groups & Geometry in particular not sure.


What are all the positive integers $n$ such that $2^n$ ends in $n$? What are all the positive integers $n$ such that $2^n$ ends in $n$?

Example: $2^{36} = 68719476736$ ends in $36$.

Firstly, $n$ should be even.

Now

  $2^n=10i+4$ or $2^n=10i+6$

Unit digits agree when

  $n=20j-6$ or $n=20j+16$

that gives $2^{n}=100k+84$ or $100k+36$ respectively.

Since $20j-6 \pmod{ 4} \not \equiv  100k+84 \pmod{4}$,

we only need to try

  $n=100\ell+36$

Upcoming solutions are $736$, $8736$, $48736, \ldots$

Well last two digit possibilities

04 08 16 32 64 28 56 12 24 48 96 92 84 68 36 72 44 88 76 52.

Now we can check the results using a calculator.


Calculus: The tangent line intersects a curve at two points. Find the other point. The line tangent to $y = -x^3 + 2x + 1$ when $x = 1$ intersects the curve in another point.  Find the coordinates of the other point.
This was never taught in class, and I have a test on this tomorrow.  This question came off of my test review worksheet, and I don't understand how to solve it.  The answers are on the back, and for this one it says the answer is (-2,5), but I don't understand how to get that.
I did the derivative and substituted 1 for x to get the slope of the line:
$y = -x^3 + 2x + 1$
$y' = -3x^2 + 2$
$y' = -3 + 2$
$y' = -1$
I don't know where to go from here.

We first describe the normal computational approach, and then a more conceptual approach.

Computational approach: You can find the equation of the tangent line. After some work you will end up with $y=3-x$.

Substitute $3-x$ for $y$ in the equation of the curve. We end up with a cubic equation $x^3-3x+2=0$.

This equation has $x=1$ as a root.  Divide $x^3-3x+2$ by $x-1$. You will get $x^2+x-2$, which factors as $(x-1)(x+2)$. That gives the $x=-2$.

Conceptual approach: Just  imagine finding the equation of the tangent line, as we did above, but don't do the actual work. When we substitute for $y$ in the equation of the curve,  we  end up with a cubic equation of the shape $P(x)=x^3+ax+b=0$.

Since we are not doing the work, we won't find $a$ or $b$.

The tangent line at $x=1$ kisses the curve at $x=1$.  Thus the equation $P(x)=0$ has $x=1$ as a double root. So the sum of the roots is $1+1+w$, where $w$ is our mystery number.

The sum of the roots of $P(x)=0$ is the negative of the coefficient of $x^2$, in this case, $0$. So $1+1+w=0$ and therefore $w=-2$.


How to prove $e^x=\lim_{n\to\infty}\left(1+\dfrac{x}{n}\right)^n$ Define
$$e=\lim_{n\to\infty}\left(1+\dfrac{1}{n}\right)^n,$$
how to prove that
$$e^x=\lim_{n\to\infty}\left(1+\dfrac{x}{n}\right)^n,$$
for all $x$.
Thank you.

Use the definition

$$
e = \lim_{n \rightarrow \infty} \left( 1 + \frac{1}{n} \right)^n
$$

Then

$$
e^x = \left( \lim_{n \rightarrow \infty} \left( 1 + \frac{1}{n} \right)^n \right)^x
= \lim_{n \rightarrow \infty} \left( 1 + \frac{1}{n} \right)^{nx}
= \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{nx} \right)^{nx}
= \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right)^{n}
$$

By applying $\log$ and  using L'Hospital's rule $$\lim_{n \to \infty}\frac{\log\left(1+\frac{x}{n}\right)}{\frac{1}{n}}=\lim_{n\to \infty}\frac{\frac{1}{1+\frac{x}{n}}\left(\frac{-x}{n^2}\right)}{\frac{-1}{n^2}}=x$$


Modular arithmetic proposition I am trying to solve this Modular arithmetic problem but I have no idea how to verify if the proposition holds or not.

  $\forall a,b \in \mathbb{Z}: (a \equiv b \pmod{5}  \Rightarrow 2a \equiv 2b \pmod{5} )$

Try it this way:

$$ a \equiv b \pmod 5  \implies \exists (k_a, k_b, m \in \Bbb N) : \\a = 5k_a+m , \\b = 5k_b+m,  \\0 \leq m <5
$$
Okay, now what about comparing $2a$ and $2b$?

One thing to try is to multiply those relations above by 2, getting
$$
2a = 10k_a+2m , \\2b = 10k_b+2m,  \\0 \leq 2m <10
$$
If $2m < 5$ it is easy to see that $2a \equiv 2b$ by using multipliers $k'_a = 2k_a$ and $k'_b = 2k_b$.  That leaves the headache of the possibility that $2m > 5$.

Can you see how to handle that case and thus complete the proof?  (Hint - what happens if you use $k'_a = 2k_a + 1$ ?)

You can prove this directly.

$$a \equiv b \pmod {5} \iff 5|(b-a) \iff b-a = 5k ~(\text{for some } k \in \Bbb Z)\\ \iff 2b-2a =5(2k) \iff 5|(2b-2a) \iff 2a \equiv b \pmod {5}.$$


Pdf for distance between two uniform random points in a circle This is my first post in the group and I would be very thankful for any help. I am trying to develop a probability distribution for a performance analysis in my thesis. I am trying to look in to literature which provides the probability distribution for distance between two random points in a unit circle.

I would try to explain the problem. Suppose we have a point X and we have point x1 in the unit circle C1 which contains X. There is another unit circle X2 right next to the circle X1. There is a point x2 in the unit circle X2. Let d1 be the distance between X and x1 and d2 be the distance between X and x2. All the points are distributed within respective circles with random distribution. I want to know the probability distribution for d1/d2. Has anyone worked with a similar problem or anybody can direct me towards any literature.

Thank you so much for the help.
Cheers,
Waqas

Where is your problem? Google is your friend!

If you google the words:

distance random points in circles

the first hit gives you the book:
An introduction to geometrical probability  by A.M. Mathai.

To find in Google:

http://books.google.de/books/about/An_Introduction_to_Geometrical_Probabili.html?id=FV6XncZgfcwC&redir_esc=y

If you look into the book in Google preview,
on page 217 you find a chapter treating your problem.

Maybe you can read it yourself ;-)!

Ciao

Karl

Please look at this work 1 which has investigated the interference from neighbor cells, and hence, investigated the distribution of distances between users. Hope it works for you.


How to say that there may exist elements in two sets such that their intersection is not null? I have a very basic understanding of set theory. I am trying to put some English sentences into mathematical notations and I am stuck at this one thing.

I have two sets A and B and they may not be disjoint, i.e., it may be possible that for some cases, their intersection is null and for some cases, they may have overlapping elements. Consider, for example, two courses which may have unique students or there may be a few students who take up both the courses. If $A=\{a_1, a_2, ..., a_n\}$ denotes the first course and $B=\{b_1, b_2, ..., b_n\}$ denotes the second course, then how do I convey this information mathematically?

Is this notation correct?

$\exists{i \in A,j \in B}$ s.t. $A \cap B \ne \emptyset$

This translates to "there exists some $i$ in $A$ and some $j$ in $B$ for which the intersection of $i$ and $j$ is not null". However, does this also put a constraint that there must exist some $i$ and some $j$ for which the intersection is not null? If yes, then what is the right way to denote this information?

Thanks in advance.

From the discussion in the comments, it sounds like your main purpose is to caution the reader. In that case, you don't need to use terse mathematical symbols. On the contrary, it's probably better to use English so that the reader doesn't skim over the warning. So, something like "Note that $A$ and $B$ might not be disjoint" or "Caution: We cannot assume that $A$ and $B$ are disjoint".

The notation is

$$A\cap B\ne \emptyset$$

which means that $A$ and $B$ have at least one element in common (their intersection is not an empty set), or

$$\exists i\in A,B$$

which means there exists (at least) one element which is in $A$ and $B$.


Jacobi Theta Functions? For the Jacobi theta function $\vartheta_3(z|\tau)$ there exists an equality (by Whittaker & Watson)

\begin{equation}
\vartheta_3(z|\tau) = \sum_{n=-\infty}^{\infty} e^{n^2 \pi i \tau + 2 n i z} = \sqrt{\frac{1}{-i\tau}} \sum_{n=-\infty}^{\infty} e^{\frac{(z-n\pi)^2}{\pi i \tau}}
\end{equation}

Is there something similar for this "modified version" of the Jacobi theta function?

$$\sum_{n=1}^{\infty} n\,e^{n^2 \pi i \tau}$$

I tried to use the relation shown above, but it results nothing.

Well, I got a relation for the $n^2$ case

$$\sum_{n=1}^{\infty} n^2\,e^{n^2 \pi i \tau}$$

I just 'broke' the sum into parts,
$$\sum_{n=-\infty}^{-1} + \sum_{n=1}^{\infty}$$
remembering that $n=0$ contributes with nothing, than I took a derivative with respect to $\tau$ and set $z=0$. I got:

$$\sum_{n=1}^\infty n^2\,e^{n^2 \pi i \tau} = \frac{(-i\tau)^{-3/2}}{2\pi} \left(\frac{1}{2}+\sum_{n=1}^\infty e^{\frac{n^2\pi}{i\tau}}\right) - \pi (-i\tau)^{-5/2}\sum_{n=1}^\infty n^2\,e^{\frac{n^2\pi}{i\tau}}$$

It looks like equalities for
$$\sum_{n=1}^\infty n^{2k}\,e^{n^2 \pi i \tau}, \quad k\in\mathbb{N}$$
are allways possible to get by 'recurrence'. The problem is with odd powers...

The Fourier transform of $1_{y > 0}$ is $PV.(\frac{1}{2i \pi y})+\frac{1}{2}\delta(y)$, thus the Fourier transform of $y \ 1_{y > 0}$  is $\frac{d}{dy}PV.(\frac{-1}{4\pi^2 y})+\frac{1}{4i \pi}\delta'(y)$

and of
 $T(y) = \sum_{n=1}^\infty n \delta(y-n)$  is $\hat{T}(y)=\sum_n  \frac{d}{dy} PV.(\frac{-1}{4 \pi^2 (y-n)})+\frac{1}{4i\pi}\delta'(y-n)=\sum_n  \frac{d^2}{d^2y} \frac{\log |y-n|}{-4\pi^2}+\frac{1}{4i\pi}\delta'(y-n)$.

With $\hat{h}(y) = e^{-\pi y^2 x},h(y) = \frac{1}{\sqrt{x}}e^{-\pi y^2 /x}$

$$\sum_{n=1}^\infty n e^{- \pi n^2 x} = \langle T, \hat{h} \rangle=\langle \hat{T},h \rangle
 = \sum_{n=-\infty}^\infty \frac{i  n}{2 x^{3/2}}e^{-\pi n^2 /x}-\frac{1}{4\pi^2} \int_{-\infty}^\infty \log |y-n| h''(y)dy$$

$$\sum _{k=1}^{\infty } k e^{\pi  i k^2 (-x)}=\sum _{n=1}^{\infty } -\frac{i \left(x+\sqrt[4]{-1} \pi  n \sqrt{x} e^{\frac{i \pi  n^2}{x}} \text{erf}\left(\frac{\sqrt[4]{-1} \sqrt{\pi } n}{\sqrt{x}}\right)\right)}{\pi  x^2}-\frac{i}{2 \pi  x}$$


Taylor Series of $\frac{1}{1-\cos x}$ The problem is, as the title suggests, to find the Power Series Expansion of $\frac{1}{1- \cos x}$ around $x=c$.

What I've tried:

Direct Computation: Derivatives get very ugly quickly, and don't yield a nice formula that I can recognize as a "series."
Tried finding the integral of $\frac{1}{1- \cos x}$, finding it's series and then differentiating it to get the new series.
Tried reverse of the above, differentiating and finding it's series, then integrating (very messy).
Then I tried some substitution "tricks", like using the series of $\frac{1}{1-x}$ and then plugging in the series expansion for $\cos x$, but that's a double sum that I struggled to produce anything useful from
:$\displaystyle \sum_{k=0}^\infty\left(\sum_{n=0}^\infty\frac{(-1)^nx^{2n}}{(2n)!}\right)^k$

I am literally at my witts end with this problem. I have spent perhaps a day or two trying to figure it out, because I feel that I am so close - but just barely missing something. I do not want the solution posted - now it's personal and I have to figure it out, but I would greatly appreciate a hint in the right direction, or to point out a mistake that I may be overlooking.

As @hjpotter92 suggest, you have
$$\frac{1}{1-\cos(x)} = \frac{1}{2\sin^2(x/2)} = -\frac{\text{d}}{\text{d}x}(\cot(x/2)).$$
Now you can exploit the series expansion of
$$\cot(x)=\sum_{n=0}^\infty\frac{(-1)^n 2^{2n}B_{2n}}{(2n)!}x^{2n-1}, \quad \forall 0<\left|x\right|<\pi.$$
Now, by evaluating in $x/2$, differentiating each coefficient and changing the sign, you get
$$\frac{1}{1-\cos(x)} =\sum_{n=0}^\infty\frac{(-1)^{n+1} 2(2n-1)B_{2n}}{(2n)!}x^{2n-2}, \quad \forall 0<\left|x\right|<2\pi,$$
where $B_n$ are the Bernoulli numbers.

integration of 1/1-cos(x)=
= 1/1-cos(x)(1+cos(x)/1+cos(x)
= 1+cos(x)/[1-cos(x)][1+cos(x)]
= 1+cos(x)/[sin(x)][sin(x)
= 1/sin(x)[sin(x)]+cos(x)/sin(x)[sin(x)]
= cosec(x)[cosec(x)+cot(x)cosec(x)
= -cot(x)+cosec(x)+c


How many bingo card combinations are there? Bingo cards have $5$ rows and $5$ columns. The column names are B,I,N,G,O. Each column has $15$ possible numbers to choose from $1-15$ for $B$, $16-30$ for $I$, $31-45$ for $N$, and so forth.

The third space on the $N$ is 'daubed' or blocked out, so the card only has $24$ numbers.

I don't think $75$ choose $24$ is right. Is $15$ choose $5$ times $4$ plus $15$ choose $4$ (because of the $N$ column) the correct answer$?$ (Which I calculate to $13377$ combinations, which seems too small.)

There are four complete columns of 5 and one with only 4 numbers. For column 1 there are: $$5! {15 \choose 5}$$ Since there are 5 numbers out of a possible 15 used in the column and these can be permuted in any order (in 5! ways). This also holds for the other 3 complete columns. The same method works for the column of 4 giving instead: $$4! {15 \choose 4} $$

Therefore the total answer is: $$ \left (5! {15 \choose 5} \right)^4 4! {15 \choose 4} = 552446474061128648601600000 $$

Since no number is ever repeated on a bingo card under the 'B' the first position has 15 possibilities the second position has 14 the third position has 13 and so on so the correct equation would be 15 * 14 * 13 * 12 * 11 * 4 because B, I, G and O each have that number of possibilities (or 360,360) and under the N where there is a free space it would be 15 * 14 * 13 * 12 (or  32760)
(360.360 × 4) + 32,760 = 1,474,200 possibilities.


Natural isomorphisms and the axiom of choice The definitions of "natural transformation", "natural isomorphism between functors", and "natural isomorphism between objects" captures - among other things - the intuitive notion of "an isomorphism that does not depend on an arbitrary choice" (from Wikipedia). The standard example is a finite dimensional vector space $V$ being naturally isomorphic to its double dual $V$** because the isomorphism doesn't depend on the choice of basis.
What I wonder:

Does this informal notion of choice have to do
with the formal notion of choice in the axiom of
choice?
Is "being naturally
isomorphic" somehow related
to "being provably isomorphic from $ZF$ without $AC$"?
Or are these completely unrelated concepts?

"Naturality" in a categorical sense is much more than "not depending on choices", and, also, is essentially unrelated to issues about the Axiom of Choice.

In the example of vector spaces over a field, we can look at the category of _finite_dimensional_ vector spaces, to avoid worrying about using AxCh to find elements of the dual. The non naturality of any isomorphisms of finite-dimensional vectorspaces with their duals resides in the fact that, provably, as a not-hard exercise, there is no collection of isomorphisms $\phi_V:V\rightarrow V^*$ of isomorphisms of f.d. v.s.'s $V$ to their duals, compatible with all v.s. homs $f:V\rightarrow W$.

In contrast, the isomorphism $\phi_V:V\rightarrow V^{**}$ to the second dual, by $\phi_V(v)(\lambda)=\lambda(v)$ is compatible with all homs, as an easy exericise! This latter compatibility is the serious meaning of "naturality".

True, if capricious or random choices play a role, the chance that the outcome is natural in this sense is certainly diminished! But that aspect is not the defining property!

Edit (16 Apr '12): as alancalvitti notes, the ubiquity of adjunctions, and the naturality and sense of "naturality", and counter-examples to naive portrayals, deserve wider treatment at introductory levels. After all, this can be done with almost no serious "formal" category-theoretic overhead, and pays wonderful returns, at the very least organizing one's thinking. Distinguishing "characterization" from "construction-to-prove-existence" is related. E.g., "Why is the product topology so coarse?": to say that "it's the definition" is unhelpful; to take the categorical definition of "product" and _find_out_ what topology on the cartesian product of sets is the categorical product topology is a do-able, interesting exercise! :)

I'm no expert but I think they're different. My understanding is that "natural isomorphism" has always been a little vaguely defined but the concept is fairly intuitive.

It's a case where there is clearly a "best" or simplest isomorphism. Like the Chinese Remainder Theorem perhaps. Cmn ~ Cm x Cn where m, n are relatively prime. There may be more than one isomorphism but one stands out as the most natural or most obvious, I guess.

Generally the "natural" isomorphisms are easily and unambiguously provable. It's recognising that such a connection exists that's the real art. Funnily enough I find the axiom of choice much vaguer (and have never been a fan).

I'm probably way off...


Equation of a flat top gaussian I'm trying to map a set of data points that seems to form a kind of a flat top gaussian in one dimension. I'm used to fitting data to a gaussian using non-linear least squares. I'm trying to understand how to do the same, for a flat top gaussian?

The approach is the same.  A Gaussian distribution has two parameters, the mean and standard deviation.  You add up the square of the error of each point to get an error function, which depends on those two parameters, then minimize the error function to find the best fit set of parameters.  For your case, you need to define the "flat topped Gaussian" as a function of some number of parameters.  You might just chop off the head of the Gaussian at $\pm n \sigma$, leading to something like $$M(\mu , \sigma , n,x)=\begin {cases} \frac K{\sqrt {2 \pi \sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma ^2}}&|x| \gt n \sigma \\ \frac K{\sqrt {2 \pi \sigma^2}} e^{-\frac{(n \sigma-\mu)^2}{2\sigma ^2}}&|x| \le n \sigma\end {cases}$$ where you choose $K$ as a function of $n$ so the integral over the distribution remains $1$  Now compute the error of each point from $M$, square it, add them all up, and that is your error function to minimize over the parameters.

This is my implementation in Matlab.
I use FWHM (full width half maximum) which is the location where the Gaussian is equal to 0.5.
FunctionResult

function[y] = flatTopGaussian(sizex,FWHM,plot_result)
% Produces a flat top Gaussian.
%   Equal to 1 between -FWHM/2,FWHM/2
%   Gaussian function for the other values
% Inputs
%   sizex:  length of y
%   FWHM:   Full width half maximum
%   plot_result: should we plot the result

%%
% sizex=200;
% FWHM=2*20;
x_vec=-sizex/2+1:sizex/2;
sigma=FWHM/2.355;
[y] = 2*createGaussianPeak_1D(sizex, sigma);
y(abs(x_vec)<FWHM/2)=1;

%% Plotting
if plot_result
    flat_win=zeros(size(x_vec)); flat_win(abs(x_vec)<FWHM/2)=1;
    figure(1); plot(x_vec,flat_win,x_vec,y);
end
end

function [y] = createGaussianPeak_1D(sizex,output_sigma)
sxh = ceil((sizex) / 2);
mult = -0.5 / (output_sigma * output_sigma);
y=zeros(1,sizex);
for j=1:sizex
    jh = j - sxh;
    y(j) = exp(mult * (jh * jh));
end
end


General approach for problems like "If a coin is tossed $n$ times, what is the probability that heads and tails appear $x$ and $y$ times"? If a fair coin is tossed four times. What is the probability that two heads and two tails will result?

I was solving the question above, since the sample space was small, I was able to list down all possible combinations, but what if the number of coins was let's say 20, how would one solve it?

I think I've found a solution to my own question-
The sample space $n(S)=2^4$ combinations.
let A be the event of occurrence of heads $x$ times.
Therefore, the combinations in which heads may appear $x$ times is $\dbinom{4}{x}$.
So, the probability $P(A)$ that heads will appear $x$ times is -
$P(A)=\frac{\dbinom{4}{x}}{\Large n(S)}$

First thing is to note that any two heads two tails flip (e.g. HHTT, HTTH) because of independence of flips has probability of $\frac{1}{2^4}$ of happening. Now all we must do is count how many of these type of events there are. Well if we want 2 out of the 4 flips to be heads (thus other two must be tails), which is $4 \choose 2$ now putting this together we have that. The probability of getting two heads out of two flips is ${4 \choose 2} \frac{1}{2^4}$.

Now extending this to $n$ flips. The probability of seeing $x$ heads we have is
$${ n\choose x}\left(\frac{1}{2}\right)^n$$


What is the first digit of $2^{43} $? What is the first digit of the number $2^{43}$?

I know how to do this task if it was the last digit to be calculated.

Hint: Using the fact that $2^{10}=1024=10^3\cdot(1+0.024)$ you can decompose $2^{43}=8\cdot (2^{10})^4$. I think you can take it from here.

yes it will easy to find last digit. bcoz lot of sources and many ssc and banking queation ask only last digit.
here, it is also tricky question we can break 2^43 as 2^3 *1024*1024*1024*1024 as you can see multication of 1024  four times always gives 1 as leading digit. u can see thing by breaking 1024 as 1000+24 to power 4 now you will get idea after that multiply with 8 will always give 8 as leading digit.
pls leave comment if any doubt:


What is a commutator I've read wikipedia, tried examples ($S_3$ stuff) but I cannot understand why they are called "commutators" or what the set of them is.

Why is the set of commutators called "commutator subgroup"? (I read this one among other, I have done reading even I don't link all the tabs!)

It's in Lang's Undergraduate Algebra - page 35, question 10 part b. It's in A Book of Abstract Algebra by Pinter (page 152), but I still have no idea what this is.

My goal is to show that if $H$ is a subgroup of $G$ that contains all the commutators that $G/H$ is Abelian - please don't do this for me. I'm stuck with trying to work out what H is not the question.

See... if the result is true ($G/H$ being Abelian) then H is the set of things that don't commute because I'm factoring them out with the quotient operation. The identity of H will be left in the result (necessarily) thus the commutators that = the identity (ie the things that actually commute) are left in the group.

So is this set of commutators $=\{x|x=aba^{-1}b^{-1}, \forall a,b\in G\}$ the reason I need this clarified is because then an Abelian group only has one commutator, the identity.

Also the commutators don't actually commute! For example $(1,3)$ and $(1,3)(1,2)$ in $S_3$. Have I actually got the definition and the name has just confused me? Also both books say "a commutator of G is an element of the form" but there might only be one (for an Abelian one)

Could someone clarify please?

Oh group generated means "the union of all the groups generated by each element of the set, generated as in $<g>=\{e,g,g^2....\}$"

If $a,b\in G$ then $ab=ba$ is equivalent to $aba^{-1}b^{-1}=e$ and so the commutator of $a$ and $b$ is a measure of the failure of $a$ and $b$ commuting with each other. However, as a measure alone, it is somewhat binary: either group elements commute or they don't.

There are two ways we can quantify this measure. The first is by looking at (subgroups of) the symmetric group. Then, instead of asking if $a$ and $b$ commute, we can ask how many elements are moved around by their commutator.

The second way is to look at the commutator subgroup as a measure of how noncommutative a group is. A group is commutative if it has a trivial commutator subgroup (and highly noncommutative if the commutator subgroup is the entire group). But we can then ask if the commutator subgroup is abelian. And if not, if it's commutator subgroup is abelian. And we can repeat the process of taking commutator subgroups many times and ask if we ever find the trivial group, and if so, how many times does it take?  And if not, how many times does it take before we keep on getting the same group repeating itself?  This gives the notion of solvable groups and their degree of sol ability. A similar notion gives nilpotent groups and their degree of nilpotency. Both are measures of how close to abelian our groups actually are.

We call it commutator, because it shows us the operation in the group is "how far" from commutativity.

Let $(G,\cdot)$ be a group. For all $g,h \in G$ we have $[g,h]=g^{-1}h^{-1}gh=e$ if and only if the group $(G,\cdot)$ is commutative.


Reason why addition and multiplication are both required - unlike boolean algebra where NOR is enough? Apologies for the simplicity of this question.

In Boolean Algebra the introduction of the function {NOR} is sufficient to create, with suitable finite combinations of this function, all possible sets of states for a set of n two state variables (so all n placed functions of two state variables can be expressed as finite combinations of NOR). There are similar combinations of two or one place boolean functions that achieve this objective e.g. it could also be any of {OR, NOT}, {$\Rightarrow$, NOT}, {AND, NOT}, {NAND}.

The question is : Is there a similar 'high level' objective behind providing both '+' and '$\times$' two place functions in arithmetic, and is there any reasoning which shows why '+' and '$\times$' are both required to meet the objective and whether there are any other function combinations that meet the objective ?

The fact that every boolean function can be expressed as some finite-length combination of $NOR$'s means that $\{NOR\}$ is an 'expressive complete' set of operators. And indeed, there are many other expressive complete sets for Boolean algebra, such as $\{\neg, \land \}$' $\{\neg, \lor\}$, and $\{\neg, \rightarrow \}$

You seem to be asking what the equivalent would be for natural numbers. That is, are there any expressively complete sets of operators to capture any function defined over the natural numbers? Are addition and multiplication always required as part of such a complete set? Or are there sets that are complete without addition or multiplication?

The answer is that there is no finite set of operators that is complete for the natural numbers. The reason is that the set of all finite-length expressions that you can create from given any finite set of operators is enumerable, but the set of all functions from natural numbers to natural numbers is not. In fact, even just the set of all 1-place functions defined over the natural numbers (which includes functions like $f(n)=n^2$) is not enumerable. Therefore, for any finite set of operators, there are functions from natural numbers to natural numbers that cannot be expressed using those operators.

Of course, this means that in particular, having just addition and multiplication would not be complete. Sure, we can express the earlier mentioned $f(n)=n^2$ in terms of multiplication: $f(n)=n*n$. But how would you capture something like a function $f(n)=2^n$?  You can't use something like:

$$f(n)=\underbrace{2\cdot 2 \cdot 2 ... \cdot 2}_{n \text{ times}}$$

because that expression is a different expression for each $n$, and when we define expressive completeness, we are looking a single, fixed expression. Indeed, as such, the recursive definitions offered by some of the comments and Answers to your comment cannot be used either.

Finally, as Mauro point out in the comments, the big difference between the domains of Boolean Algebra and the natural numbers is that the domain of the first contains just two elements, whereas the latter contains infinitely many. So from that perspective, it maybe shouldn't be all that surprising that there is no finite and expressively complete set of operators for the natural numbers. It's infinity rearing its ugly head again!

In Peano axiomatic, one defines

$m+0 = m$ and $m + S(n) = S(m+n)$

and

$m\cdot 0 = 0$ and $m\cdot S(n) = m\cdot n+ m$,

where $S(n)=n+1$ is the successor function. So multiplication is based on addition.


What's the point in being a "skeptical" learner I have a big problem:

When I read any mathematical text I'm very skeptical. I feel the need to check every detail of proofs and I ask myself very dumb questions like the following: "is the map well defined?", "is the definition independent from the choice of representatives" etc... Even if  the author of the paper/book says that something is a easy to check, I have this impulse to verify by myself.

I think that this approach is philosophically a good thing, but it leads to severe drawbacks:

I waste a lot of time in reading few lines of mathematics, and at the end of the day I look at what I've done and I realize that I managed to go through a few theorems without learning enough. Remember that  when one  is a (post)graduate student (s)he has plenty of things to learn, so the time is almost never enough.
This kind of learning could be affordable for undergraduate texts, but very often is almost impossible to read a paper with a skeptics point of view. At a certain point things become very complicated and the only way out is to accept results on faith.

And finally the real object of my question:

3. Despite the big effort I've employed in reading very carefully something, after few  weeks or months I obviously forget the details. So, for example if I try to read again a proof after a while, maybe I would remember the big picture but probably I would check again the details as though I'd never done it yet.

Therefore, even if the common rules for a mathematician say that "learning" should ideally be done skeptically, I've finally realized that maybe this is not very healthy. Now, could you recommend  a sort of royal road for reading mathematics? It should be a middle way between accepting every result as true and going through every detail. I'd like to know  what to do in practice.

I have the following advice for reading papers:  read them (up to) three times.

The first time through, you do not check that the claims are correct.  You are attempting to get broad structural understanding.  Don't even look at the proofs.  Many details will be left dangling.  This is fine.  This is your first pass.  If you are doing a lot of reading, leave a note to yourself that you have read this paper coarsely.

If there is something in the paper justifying further understanding, read it again.  This time, read through the proofs quickly.  Again, don't check any details.  Just ask yourself: "Is this the sort of argument I have seen before?  Does this structure of proof match the broad structure I got from my first reading?"  If you are doing a lot of reading, or might come back to this paper in the future, leave a note to yourself that you have read this paper.

If there is still something in the paper to justify detailed understanding, read it a third time.  Check every line.  Ask yourself "why should I believe this is true" as often as possible.  If a particular claim needs an additional idea (for you to believe it), record this idea in the margin nearby.  If you are doing a lot of reading, or might come back to this paper in the future, leave a note to yourself that you have read this paper in detail.

You leave notes to yourself because you trust yourself to have applied the appropriate level of skepticism to the things you have read.

There are not enough hours in the day to read everything at the detailed level.  For results that are entirely predictable, you should arrive at that conclusion after one or maybe two readings (and you will have recorded that you believe those results at that level).  Only the results with complexity or surprise should merit a third read.

Is this method perfect?  No.  Does it help allocate time better?  I think so.

How does this apply to textbooks?  You can certainly write in your textbooks, so leaving notes should be no problem.  Clearly, the "big theorems" should be read three (or more) times.  Other results may only need to be believed at the "plausible" (coarse, once read) or "likely" (medium, twice read) level.  Is this ideal?  Probably not, but neither of us is immortal, so some accommodation of finite time must occur.

I have the same "problem" like you, I want to understand every detail. And by this my progress is slow and I always have the feeling that there is still so much to learn and still so much to do.

But one thing I learned as time passed by, that some domains have certain standard arguments and how to think about certain constructions behind merely formal checking. And until you have not internalized them checking them makes it sometimes hard to follow arguments or understand the reasoning behind it.

Maybe I give you an example from my recent studies. I had to study group theory approximately 6 months ago and entered the field with almost no knowledge about it behind the basic definitions. I started reading certain papers and felt almost (and still do...) overwhelmed. In the domain I am concerned with a special class of groups called Frobenius groups arise, they have one quite obvious definition in terms of permutations groups, and then many others. It took me a while to handle them all, see all the connections and all the implications. When I now look at them they are much less intimidating and it is much easier to follow certain arguments about them, and also to remind facts about them.

So if you always have such a though time, then either the paper you are reading is a though one, or it might indicate that you are not familiar enough with some basic arguments and ways of thinking in your domain.

Maybe adapt the following strategy, if you have a specific paper. Read it and take notes what is not clear and what is clear to you, and try to think more deeply about selected portions of it. Then put it aside and the next week just study the field as a whole (reading books about the topic, secondary literature, other papers) and then after approximately a week come back to your paper and do the same again, and hopefully it is now easier to read it; work through it again, taking notes, think about it, but then put it aside again for another week and do "general research" again. Do this until you understand the paper. I know this might be time-consuming, especially if you have some deadline, but if not than this might work out well and gives you good overall knowledge in the end.


Unfirom convergence of sequence of functions Let $\{f_n(x)\}$ be sequence of functions defined on a set $E$. Let for any $n$ we have $|f_n(x)|\leqslant c_n$ and $c_n\to 0$ as $n\to \infty$. Does it follow that $f_n$ converges uniformly on $E$?

I can't prove it rigorously.

Yes,

By the given hypothesis if $f(x)=\lim_{n\to \infty} f_n(x)$ then $f(x)=0$.

So $M_n=\sup_{x\in E} |f_n(x)-f(x)|=\sup_{x\in E} |f_n(x)|\leq c_n\to 0$ for $n\to \infty $

Thus $f_n$ converges uniformly to $f$

Counterexample is the following:

Let $f_n(x)=x^n$ on $E=[0,1)$. For any fixed $n$ we see that $|f_n(x)|=x^n<1=c_n$ and $c_n\to 1\neq 0$ but $\{f_n(x)\}$ does not coverges uniformly on $E$.


$\hom(V,W)$ is canonic isomorph to $\hom(W^*, V^*)$ Introduction My Semester just started and we have a new Professor for Linear Algebra II (replacing our former Professor). Apparently we are behind our schedule and thus we only had a brief introduction (5 Minutes on the Blackboard) about the Dual Space and canonical isomorphisms.

In the current problem set there is this optional (not mandatory and not accredited) exercise which I understand as good as nothing about:

  Problem: Let $V$ and $W$ be finite dimensional $\mathbb{K}$-Vectorspaces$^{1)}$. Show that $\hom(V,W)$ is canonical isomorph to $\hom(W^*,V^*)$ and find the canonical isomorphism.

  $^{1)}$ ($\mathbb{K}$ denotes a field here, I presume in english literature they write $\mathbb{F}$)

Hint (given by my tutor): $$ \Phi: \hom(V,W) \longrightarrow  \hom(W^*,V^*) \\ \Psi \longmapsto (\varphi \longmapsto \varphi\circ \Psi)$$
My problems are vast now:

The literature I am reading does a bad job at explaining this topic
The online literature I find seems to be way beyond my level, they usually include tensor algebra to solve this. So I fall down the math rabbit hole see, On "familiarity" (or How to avoid "going down the Math Rabbit Hole"?)
I don't understand the Hint, I did not encounter such a function before, not even in Analysis and I don't know what's happening. I can only guess that it is a function that somehow completes a circle.

On the bright side:

I believe to understand what a canonical isomorphism is. My Professor said it is an isomorphism that does not involve making a choice for a basis. In the above function we do not make such a decision and therefore it would be a candidate for a canonical isomorphism.
If I would understand the above function, I'd merely have to show that it is injective (trivial Kern) and surjective to complete the task. Unfortunately, as far, we've only done such things using an explicit Matrix and not a function.
I do know the definition of the Dual Space, also using the Kronecker Delta.  (although I know nothing about it's meaning and geometric intrepreation, if there is any)
The way my tutors sell this exercise it's supposed to be very easy, once the definitions are clear.

To-Do-List:

Understand the function, know what's happening.
Show that the function is surjective
Show that the function is injective  (trivial Kern)

First notice that if $E$ is a linear space then its dual $E^*$ is the linear space of the  linear forms $$\varphi: E\rightarrow \Bbb K$$

Now if $\Psi\in \operatorname{hom}(V,W)$ i.e. a linear transformation $\Psi:V\rightarrow W$ then $\Phi(\Psi)\in \operatorname{hom}(W^*,V^*)$ since
$$\underbrace{\Phi(\Psi)(\varphi)}_{\in V^*}=\varphi\circ\Psi:V\xrightarrow{\Psi} W\xrightarrow{\varphi} \Bbb K\quad \forall \varphi\in W^*$$
and we prove easily that $\Phi$ is a linear transformation:
$$\Phi(\Psi)(\varphi+\lambda\psi)=\Phi(\Psi)(\varphi)+\lambda\Phi(\Psi)(\psi)$$
and if $\Psi\ne0$ hence there's $x\in V$ such that $W\ni\Psi(x)\ne0$ hence with $\varphi=(\Psi(x))^*$ the linear form such that
$$(\Psi(x))^*(\Psi(x))=1$$
we see that
$$\Phi(\Psi)(\varphi)\ne0$$
hence $\Phi$ is injective, moreover, since
$$\dim \operatorname{hom}(V,W)=\dim V\times\dim W=\dim V^*\times\dim W^*=\dim\operatorname{hom}(W^*,V^*)$$
we see that $\Phi$ is bijective.

The isomorphism is simply the transpose...

This is as easy as things come, really :-)


For sets $A$, $B$, and $C$, why is $A\times B\times C$ is not the same as $(A\times B)\times C$. I have an intuitive sense as to why the associative law does not apply here, but can someone provide me with a more concrete reason as to why it doesn't? Thanks!

Fill in more details in: .... because $(1,2,3)$ has only one set of $()$ while $((1,2),3)$ has two sets of $()$. So they can't possibly be the same.

For finite sets $A, B$ and $C$, since there exists a isomorphism between $A\times B\times C$ and $(A\times B)\times C$, probably the only difference is the notation. But things change when some of them are infinite.


In how many different ways can the flags be arranged in a line? One red flag, three white flags and two blue flags are arranged
   in a line such that:

  $a.)$ No two adjacent flags are of the same color

  $b.)$ The flags at the two ends of the line are of different colors
  In how many different ways can the flags be arranged?

$\color{green}{a.)\ 6 }\\
 b.)\ 4 \\
 c.)\ 10 \\
 d.)\ 2$

I did

Total ways$-$when same flags are considered as one
$-$flags at the two ends of the line are of different colours[w-w,b-b]

$=\left(\dfrac{6!}{3!\times 2!}\right)-(3!)-(2)=52$

which is not in options.

I look for a short and simple way.

I have studied maths upto $12$th grade.

Hint:

If you do not start or end the line with a white flag then it is unavoidable that $2$ white flags will be adjacent.

You can arrange it like $$W @ W @ W @     OR     @ W @ W @ W$$
Where $$W = \text{White Flag}\\ @ = \color{blue}{\text{Blue}}/\color{red}{\text{Red}} \text{ flag}$$
White flags are more and $\color{red}{\text{red}}$ are $2$ and $1$. With this order, no two flags of same color will be adjacent.

Now, for $$W @ W @ W @$$ $W$'s can be arranged in only one order but $\color{red}{\text{red}}$ and \color{blue}{\text{blue}} can be arranged in $$\frac{3!}{2!} = 3$$ ways. Dividing $2!$ because it includes $2$ \color{blue}{\text{blues}} of same color.

Same for $$@ W @ W @ W$$

Hence, answer is $3 + 3 = 6$.


Can an infinite dimensional hilbert space have a finite orthonormal basis? Let $H$ be a Hilbert space with infinite dimension. Is it possible that there is a finite orthonormal basis $O$ for $H$, i.e. a set whose linear span is dense in $H$? What if $H$ is separable?

This is no homework. Intuitively, I think it is not possible, but could not prove it.

No. The span of finitely many elements is finite-dimensional and therefore already closed.

As already stated by Andre S., it is not possible that a Hilbert space of infinite dimension contains a finite orthonormal basis. Moreover, an infinite-dimensional Hilbert space is separable if and only if it has a (then necessarily countable) orthonormal basis, see https://en.wikipedia.org/wiki/Hilbert_space#Separable_spaces.


Show that the infimum of $T(v)=\|v-u\|_\infty$ is not attained Let $X=\{u\in C([0,1]):\ u(0)=0\}$ with the norm $\|u\|=\|u\|_\infty$. Let $f\in X^\star$ be defined by $$\langle f,u\rangle=\int_0^1u(x)dx $$

Let $M=\{u\in X:\ \langle f,u\rangle=0\}$ and consider the functional $T_u:M\to\mathbb{R}$ for $u\in X\setminus M$ defined by $$T_u(v)=\|v-u\|$$

Is true that the infimum of $T_u$ is not assumned for any $v\in M$? or equivalently: is there any $v\in M$ such that $$\inf_{w\in M}\|w-u\|=\|v-u\|$$

Thank you

I believe this is correct now.

Let $u \in X$, $U = \int_0^1u$ and $\hat v = u - U$. We first show that $\hat v$ minimizes $T_u$ in the extended domain $\widehat M = \{v \in C[0, 1]: \int_0^1 v = 0\}$. It is obvious that $\hat v \in \widehat M$.

First, observe that $T_u(\hat v) = \|\hat v - u\| = |U|$.

Then, for $w \in \widehat M$,

\begin{align*}
T_u(w) & = \|w - u\| \\
& \ge \left|\int_0^1 (w - u) \right| \\
& = \left|\int_0^1 u\right| = |U|.
\end{align*}
This shows that $\hat v$ minimizes the extended $T_u$.

Next, we show that there exists a sequence $v_1, v_2, \ldots$ in $M$ such that $T_u(v_n) \to |U|$ as $n \to \infty$. For each $n$, define $\tilde v_n \in C[0, 1]$ by $\tilde v_n(x) = x^{1/n}\hat v(x)$. Finally, define $v_n(x) = \tilde v_n(x) - 2x\int_0^1 \tilde v_n(y) dy$.

\begin{align*}
\tilde v_n(x) & = x^{1/n}\hat v_n(x) \\
& = x^{1/n}(u(x) - U) \\
v_n(x) & = x^{1/n}\hat v_n(x) - 2x\int_0^1 y^{1/n}\hat v_n(y)dy \\
& = x^{1/n}\left(u(x) - U\right) - 2x\int_0^1 y^{1/n}(u(y) - U)dy \\
\therefore \quad
|v_n(x) - u(x)|
& \le \left|(x^{1/n} - 1)u(x) - x^{1/n}U\right| + 2x\left|\int_0^1 y^{1/n}(u(y) - U)dy\right| \\
& \le \left|(x^{1/n} - 1)u(x) - x^{1/n}U\right| + 2x\left|\int_0^1 y^{1/n}(u(y) - U)dy\right| \\
\end{align*}
Let us now show that the sequence $I_n = \int_0^1 y^{1/n}(u(y) - U)dy$ converges to $0$.
Suppose $\epsilon > 0$ is given.
We know that the sequence of functions $(x^{1/n})$ converges uniformly on an interval $[x', 1]$ for any $x' > 0$, so we can pick $x' \in (0, \epsilon]$ and $N$ such that for $n > N$, $1 - x^{1/n} < \epsilon$ for $x > x'$. Then,
\begin{eqnarray*}
|I_n| & = &
\left|\int_0^1 y^{1/n}(u(y) - U) dy\right| \\
& \le & \left|\int_0^{x'} y^{1/n}(u(y) - U)dy\right| + \left|\int_{x'}^1 y^{1/n}(u(y) - U) dy\right| \\
& \le & \epsilon \|u - U\| + \left|\int_{0}^1 (y^{1/n} - 1)(u(y) - U) dy\right| + \left|\int_0^1 (u(y) - U) dy\right| \\
& \le & \epsilon \|u - U\| + \epsilon \|u - U\| = 2\epsilon \|\hat v\|.
\end{eqnarray*}
Therefore, $I_n \to 0$. Consequently, the sequence of functions $(2x|I_n|)$ converges uniformly to $0$.

We have dealt with the second part of $|v_n(x) - u(x)|$. We will show that the first part, $J_n(x) = \left|(x^{1/n} - 1)u(x) - x^{1/n}U\right|$, has a converging upper bound $|U|$. Suppose $\epsilon > 0$ is given. Same as before, we use the uniform convergence of the sequence $(x^{1/n})$ on an interval $[x', 1]$ with $x' > 0$ to choose $x' < \epsilon$ and $N$ such that $n > N$ implies $1 - x^{1/n} < \epsilon$ for $x \in [x', 1]$. Then, for $x < x'$, we have
\begin{align*}
J_n & = \left|x^{1/n}(u(x) - U) - u(x)\right| \\
& \le \left|x^{1/n}\right|\cdot\left|u(x) - U\right| + |u(x)| \\
& \le \epsilon \|u\| + \epsilon
\end{align*}and for $x \ge x'$, we have
\begin{align*}
J_n & = \left|(x^{1/n} - 1)u(x) - x^{1/n}U\right| \\
& \le \left|x^{1/n} - 1\right|\cdot|u(x)| + \left|x^{1/n}\right|\cdot|U| \\
& \le \epsilon \|u\| + |U|.
\end{align*}
Therefore, $\|J_n\| \le |U| + \epsilon \|u\| + \epsilon$.

Now we can conclude that $T_u(v_n) \to |U|$ as $n \to \infty$. What is left to investigate is whether $|U|$ is attainable by any $v \in M$.
Let's assume that $v \in M$ and $T_u(v) = |U|$. Then

\begin{align*}
|U| = T_u(v) & = \|v - u\| = \int_0^1 \|v - u\| dx \\
& \ge \int_0^1 \left|v(x) - u(x)\right| dx \ge \left|\int_0^1 (v(x) - u(x)) dx\right| = |U|
\end{align*}
and all inequalities must be equalities.
Hence,
\begin{align*}
\int_0^1\left(\|v - u\| - |v(x) - u(x)|\right) dx & =
\int_0^1\Big|\|v - u\| - |v(x) - u(x)|\Big| dx = 0.
\end{align*}
By continuity, we must have $|v(x) - u(x)| = \|v - u\| = |U|$ for all $x$, and so $v(x) = u(x) \pm |U|$. Since $v(0) = 0$ and $u(0) = 0$, we must have $|U| = 0$, which implies $u \in M$.
Hence,

  For $u \in M - X$, the infimum of $T_u$, which is equal to $\left|\int_0^1 u\right|$, is not attainable by functions in $M$.

Assuming the infinity norm of $u$ is $\max_{x \in [0, 1]}u(x)$:

The answer is yes, the infimum is not obtained. I shall give a intuitive answer.

let $u\in X \\ M$. Without loss of generality, let $\int_0^1 u(x)dx$ be $\epsilon$.

Let w be another function. Under the sole restriction $\int_0^1 w(x)dx =0$, we minimize $\| w-u \|$ by having $w = u-\epsilon$. Indeed, $\|w-u \|$ would be $\epsilon$ in this case.

Now, we want $v$ to be a function with another restriction. $v(0) = 0$. However, we can make a v as close to $w$ as we desire. Therefore, the infimum of $\|v-u\|$ is still $\epsilon$, but it cannot be reached.


Prove a certain relation holds for a holomorphic function. Suppose $f(z)$ is holomorphic on the disk $|z|<R$ and $|f(z)|\leq M$ for all $z$ with $|z|<R$.

Let $0<r<R$. Prove that for any $z$ with $|z| < r$ it holds that

$|f^{(n)}(z)| \leq \frac{M \cdot n!}{(R-r)^n}$

Could someone provide a hint? Thanks a lot!

Let $\gamma$ be the circle forming the boundary of the closed disk $D=\{w\ |\ |w|\leq R\}$, then since $|z| <r <R \implies z \in \text{Int}D$. Then by Cauchy's Integral Formula, or more appropriately Cauchy's Differentiation Formula, we have

$$f^{(n)}(z)=\frac{n!}{2\pi i}\int_{\gamma}\frac{f(z)}{(w-z)^{n+1}}dz \\ \implies \left|f^{(n)}(z)\right|=\left|\frac{n!}{2\pi i}\int_{\gamma}\frac{f(z)}{(w-z)^{n+1}}dz\right|=\frac{n!}{2\pi}\cdot\left|\int_{\gamma}\frac{f(z)}{(w-z)^{n+1}}dz\right|\leq \frac{n!}{2\pi}\cdot 2\pi R \cdot \sup_{w \in \gamma}\left|\frac{f(z)}{(w-z)^{n+1}}\right| \\ \implies \left|f^{(n)}(z)\right|\leq n! \cdot R\cdot\frac{M}{(R-r)^{n+1}} \leq \frac{M\cdot n!}{(R-r)^n}$$

The final inequality follows from the fact:

$$|w-z| \geq \left||w|-|z|\right|\geq|R-r|$$


Solving second order difference equations with non-constant coefficients For the difference equation
  $$
2ny_{n+2}+(n^2+1)y_{n+1}-(n+1)^2y_n=0
$$
  find one particular solution by guesswork and use reduction of order to deduce the general solution.

So I'm happy with second order difference equations with constant coefficients, but I have no idea how to find a solution to an example such as this, and I couldn't find anything useful through Google or in my text book.

EDIT: I copied the question wrong, answers make more sense now I realise that ..

Let's look at the coefficients. We have $2n$, $n^2+1$, and $-(n+1)^2 = -n^2 - 2n - 1$. Do you notice anything particular about these three terms? Does that lead to the needed particular solution?


Showing a map from $\Bbb Q$ to the field of fractions of $\Bbb Z 1_{R}$ is well defined. Suppose that I have a field $R$ with characteristic $0$. Let $Q= \{uv^{-1} | u,v \in \Bbb Z 1_{R}, v \neq 0 \}$. I want to show that the map $f :\Bbb Q \rightarrow Q$ defined as $f(n/m) = (n1_{R})(m1_{R})^{-1}$ is well defined.

Suppose that $\frac {a}{b} = \frac{n}{m}$, then $am-nb = 0$ and
$f(n/m)=(n1_{R})(m1_{R})^{-1}$ which I need to show is equal to
$(a1_{R})(b1_{R})^{-1}$

Here I am not sure how to proceed. Hints appreciated.

To show that $f$ is well-defined, let $\frac{a}{b}=\frac{m}{n}$ where $b,n \neq 0$. Then $an-mb=0$. Since $\mathrm{char}R=0$, the homomorphism $\varphi:\mathbb{Z} \to R$ sending $1 \mapsto 1_R$ is injective.

In fact, you can show  that for any field $F$, $\mathrm{char}F=m$ if and only if $\ker\{\varphi: \mathbb{Z} \to F\}=m\mathbb{Z}$. Sometimes this is taken as the definition of $\mathrm{char}F$.

Now consider $\varphi(an-mb)=0$. Since $f$ is a ring homomorphism, we can write

$$\varphi(a)\varphi(n)=\varphi(m)\varphi(b)$$
Injectivity of $\varphi$ implies that $\varphi(b),\varphi(n) \neq 0$. Hence,
$$\frac{\varphi(a)}{\varphi(b)}=\frac{\varphi(m)}{\varphi(n)}$$

Using your notation, $\varphi(t)=t1_R$. Hence, the equality above is the same as

$$f(\frac{a}{b})=\frac{a1_R}{b1_R}=\frac{m1_R}{n1_R}=f(\frac{m}{n})$$
Hence, $f: \mathbb{Q} \to Q$ is well-defined.

More generally, suppose that $f: D_1 \to D_2$ is an injective ring homomorphism between two integral domains $D_1$ and $D_2$. Denote their fields of fractions by $K_1$ and $K_2$, respectively. Then $f$ extends to a ring homomorphism $\hat{f}: K_1 \to K_2$ given by $\frac{a}{b} \mapsto \frac{f(a)}{f(b)}$. The proof is exactly similar and I leave it to you. In your question, $D_1=\mathbb{Z}$ and $D_2=R$. Injectivity of $f$ comes from $\mathrm{char}R=0$. That's all.


Complexity notation (Omega) consequence In my algorithms class, the professor told us that the following holds:
$$ \text{If } f(n) = \Omega(\log_2 n) \implies 2^{f(n)} = \Omega(n)$$

But is this always true ? I couldn't come up with a counter example, but this looks a bit sloppy to me..

It's not just sloppy, but downright false. Please tell your professor that he/she is wrong.

Counter-example:

  Let $f(n) = \frac12 \log_2(n)$. As $n \to \infty$, clearly $f(n) \in Ω(\log_2(n))$ but $2^{f(n)} \in o(n)$.

This seems to be true for non-negative functions, and generally pretty false.

Suppose for all $n\geq N$, we have a constant $c>0$ such that $c\log n \leq |f(n)|$. Since $2^x$ is an increasing function we can apply it across the inequality and preserve the validity of the statement:

\begin{align*}
2^{c\log n} &\leq 2^{|f(n)|} \\
2^cn &\leq 2^{|f(n)|} \\
c'n &\leq 2^{f(n)} \\
c'n &\leq \left|2^{f(n)}\right|
\end{align*}

The next-to-last step requires a bit of justification. It of course holds only if $f(n)$ is non-negative.

For a counterexample in the general case, note that if $f(n)=-\log n$ then $f(n)\in \Omega(\log n)$ but $2^{-\log n} = 1/n$, so it cannot be asymptotically bounded below by any increasing function; $n$ in particular.


How does this definition of curl make sense? In our maths textbook, curl is defined as $\text{curl} \textbf{F} = \nabla \times \textbf{F}$.  If the $\nabla$ operator isn't a vector, but an operation on a vector, how can it be an operand of a cross product?

$$\textbf{F} \in \mathbb R^3 \\ (\nabla) \in \mathbb R^3 \rightarrow \mathbb R^3 \\ (\times) \in \mathbb R^3 \rightarrow \mathbb R^3 \rightarrow \mathbb R^3 \\ \nabla \times \textbf{F} \in \mathbb R^3$$
This seems as silly to me as:
$$2 \in \mathbb R \\ \text{sin} \in \mathbb R \rightarrow \mathbb R \\ (+) \in \mathbb R \rightarrow \mathbb R \rightarrow \mathbb R \\ \text{sin} + 2 \in \mathbb R$$
Obviously, you can't treat sine as a number and add it to 2.  How come you can treat functions as numbers in the definition of curl?  Finding this cross product makes less sense, since you have the determinant of a matrix containing 3 vectors, 3 functions, and 3 scalars.

Think about the cross product.

For two vectors, $\vec{A}$ and $\vec{B}$,
$$\vec{A}\times\vec{B}=\begin{vmatrix}\mathbf{i}&&\mathbf{j}&&\mathbf{k}\\A_x&&A_y&&A_z\\B_x&&B_y&&B_z\end{vmatrix}$$
If we were to replace these instead with $\vec{\nabla}$ and $\vec{F}$, then we have
$$\vec{\nabla}\times\vec{F}=\begin{vmatrix}\mathbf{i}&&\mathbf{j}&&\mathbf{k}\\\frac{\partial}{\partial x}&&\frac{\partial}{\partial y}&&\frac{\partial}{\partial z}\\F_x&&F_y&&F_z\end{vmatrix}$$
If you were to combine the components of $\vec{\nabla}$ with the components of $\vec{F}$ in the same way as you would two vectors in the cross product, you will get the correct formula for the cross product - assuming you are using Cartesian coordinates.

This has simply been carried on as notation, a handy way of remembering the formula - it's not by any means formally correct. The $\times$ doesn't denote a separate operation, like the cross product does.

The same thing goes for the divergence, $\vec{\nabla}\cdot\vec{F}$. The $\cdot$ shouldn't be taken as an extra operation on $\vec{\nabla}$ or $\vec{F}$; the formula for divergence simply happens to be extraordinarily similar to the formula for the dot product.

$
\mathrm{\nabla}
$
can be regard as a vector
$
\left({\frac{}{\mathrm{\partial}{x}}\mathrm{,}\frac{}{\mathrm{\partial}{y}}\mathrm{,}\frac{}{\mathrm{\partial}{z}}}\right)
$
to participate in calculation


Why isn't the completion of $C^0$ wrt. the $L^2$ norm a space of sequences instead of a space of functions? We know that $L^2(\Omega)$ can be defined as the completion of $C^0(\Omega)$ with respect to the norm $$\left(\int_\Omega |u|^2\right)^{\frac 12}.$$
But strictly speaking, $L^2(\Omega)$ is a space of sequences since that is how the completion of a metric space is defined. So why is it people say $f \in L^2(\Omega)$ to mean an actual function (with the a.e. caveat)instead of a sequence?

We can identify a sequence $u=(u_n)$ with $u$ itself if $(u_n)$ is the constant sequence (eg. $u_i = u_1$ for all $i$), which is the case for the subspace $C^0(\Omega)$. But for a general element of $L^2(\Omega)$, we cannot do this.

Because $L^2$ can also be defined as the space of square-integrable functions (up to measure zero), and one can prove both definitions are equivalent. It's not any more economical to represent $L^2$ as a space of sequences than to do so for $\mathbb{R}$: they're each only spaces of sequences up to a rather large equivalence relation, so elements don't have very unique representatives.


Prove $\frac{\partial u}{\partial x}\frac{\partial x}{\partial u}+\frac{\partial v}{\partial x}\frac{\partial x}{\partial v}=1$ If $$u=f(x,y)$$
and
$$v=g(x,y)$$
are differentiable.

Prove $$\frac{\partial u}{\partial x}\frac{\partial x}{\partial u}+\frac{\partial v}{\partial x}\frac{\partial x}{\partial v}=1$$

I knew that for one variable case
$$\frac{du}{dx}=\frac{1}{\frac{dx}{du}}$$
 but I don't know how to do it in two variables. I also tried to differentiate both equations regarding to $x$, still no clue about how to solve it...Any help? Thank you~

The answer by @W.mu is a poorly formulated, but correct.

Assume that the map
$$
(x,y) \mapsto (f(x,y),g(x,y))
$$
is invertible. That is there exist functions $d,e$ such that
$$
(u,v) \mapsto (d(u,v),e(u,v))
$$
is the inverse of the previous map, that is, giving $(x,y)$ as function of $(u,v)$. Thus, we have
$$
(x,y) \mapsto \Bigl(d\bigl(f(x,y),g(x,y)\bigr),e\bigl(f(x,y),g(x,y)\bigr)\Bigr) = (x,y).
$$
Then you can differentiate the first component of this composition with respect to $x$ to get
$$
  \frac{\partial d}{\partial u}\frac{\partial f}{\partial x}
 +\frac{\partial d}{\partial v}\frac{\partial g}{\partial x}
= \frac{\partial x}{\partial u}\frac{\partial u}{\partial x}
 +\frac{\partial x}{\partial v}\frac{\partial v}{\partial x} = 1.
$$
In the last step I have been sloppy in interpreting $x = x(u,v) = d(u,v,)$, etc. This is fairly common in mathematics writing, unfortunately, since otherwise you quickly run out of symbols to denote every new function, and the notation becomes very heavy.

If we can suppose the transformation is invertible.
From IFT, we have:
$$x=x(u,v);y=y(u,v)$$
then we differentiate the first one to x:
$$1=x_uu_x+x_vv_x$$
Isn't it?


Converting a Linear Programming problem for solving using Machine Learning I have a typical linear programming optimization problem with a huge data set (millions of records and upwards of 150 GB data file). The size of the data is causing cost issues for reaching an optimal solution.

Is it possible to convert linear programming problems to machine learning type of problems that can be solved with more cost effective means?

Thanks

Are you using a binary variable to denote whether a medicine is used for a disease or not ? If yes, did you exclude the combinations of medicines-diseases where the medicine does not cure the disease ?

By excluding these combinations, you will be reducing the size of your math program. For example, you have Binary_Input_Data(Medicine, Disease) = 1 if the medicine can treat the disease. Then, your Binary_Variable(Medicine, Disease) must be generated only when Binary_Input_Data(Medicine, Disease) = 1.


Given a set $S$ in a group $G$, how does the smallest normal subgroup containing $S$ look like? In the theory of rings we have clear descriptions of the smallest ideal in a ring $R$ containing a subset $S$ of $R$. I'd like to know if there is such a description in group theory, that is, if $N(S)$ is the smallest normal subgroup of $G$ containing $S$, can you describe $N(S)$ using the operations of groups and the elements of both $S$ and $G$? Is there such description if $S$ is a subgroup? Thanks.

The smallset subgroup of $G$ containing the set $S$ is simply $\langle S \rangle$, the subgroup generated by all elements of $S$, as any smaller subgroup containing $S$ would not be closed.

To describe the smallest normal subgroup containing $S$, we do something similar.  We want for $s^g$ to remain in the group for any $s\in S, g\in G$, so we define $S^G=\{s^g:s\in S, g\in G\}$.  Then $\langle S^G \rangle$ is precisely what we want: the smallest subgroup of $G$ containing $S$ and all conjugates thereof.  As you can see there is no difference in these definitions if $S$ is a subgroup.

This actually has a name: $\langle S^G \rangle$ is the normal closure, or conjugate closure, of $S$ in $G$.  A bit more information on normal closures can be found here, though not much can be said about them in general without looking at specific cases.

It's going to be very complicated, nowhere near as simple as the description of the ideal generated by elements of a ring.  For example, in the free group on 2 letters $a$ and $b$, the smallest normal subgroup containing the single element $aba^{-1}b^{-1}$ consists of all words where the signed total number of $a$'s (i.e. counting $a^{-1}$ as negative) equals the signed total number of $b$'s.  And this is a relatively simple case to determine.  In general, there exist group presentations having unsolvable word problem, i.e., there is no algorithm for determining whether a particular word belongs to the normal subgroup generated by the relations, and those cases will be extremely complicated.


$\sum\frac{(k!)^2}{2k!}$ serie converge or diverge Does the following series diverge or converge.

$\sum\frac{(k!)^2}{2k!}$

I decide to apply the powerful ratio test.

I did

$\frac{(k+1)!^2}{2(k+1)!}$

which then becomes

$\frac{(k+1)!(k+1)!}{(2k+2)!}$*$\frac{2k!}{(k!)(k!)}$

I get the

$k\rightarrow\infty$

$\frac{(k+1)(k+1)}{(2k+2)(2k+2)}$

=$\frac{1}{4}$

$\frac{1}{4}$<1

convergent?

Assuming you're working with the series:

$$\sum\frac{(k!)^2}{(2k)!},$$ then you should be able to reduce the limit of the ratio to $$\lim_{k \to \infty} \frac{(k+1)(k+1)}{(2k+2)(2k+1)}$$

The limit is still $\frac 14$, and so, yes, by the ratio test, we have that the series converges.

Fernando, I took a course on series last year; they taught us how to sum EVERYTHING. Even if a series is divergent, it still may be possible to sum! Sum is $\frac{1}{3} + \frac{2 \pi}{9\sqrt{3}}$ . Remember, you must sum first, converge later.