How many rationals of the form $\large \frac{2^n+1}{n^2}$ are integers? This was Problem 3 (first day) of the 1990 IMO. A full solution can be found here.

  How many rationals of the form $\large \frac{2^n+1}{n^2},$ $(n \in \mathbb{N} )$ are integers?

The possible values of $n$ that i am able to  find is $n=1$ and $n=3$, so there are two solutions and this seems to be the answer to this problem.

But now we have to prove that no more of such $n$ exists, and thus the proof reduces to: Proving that $n^2$ does not divides $2^n+1$ for any $n \gt 3$.

Does anybody know how to prove this?

It is interesting that everyone is considering that $n$ must be prime.  $2^{55}+1$ and $55^2$ share a common factor of $121$, since when $n$ is composite, there is no need for the period to divide $n-1$.

One can see that $n$ can not be even, because the first number would be odd, and the divisor even.  So, the numbers that divide some $2^e+1$, leave a remainder of '3' or '1', when divided by 8.  In the example above, $121$ is $11^2$, and 11 is 3 modulo 8.

So, for example, $171$ divides $2^{171}+1$, and $171^2$ divides $3 \cdot(2^{171}+1)$.

There could exist several primes, of the form $p=1,3 \mod 8$, where the period divides the product, and thus would completely satisfy this relation.  The proof of 'raising the powers' does not prevent the case of 2, as shown in the examples of $55$ and $171$ above, where one comes from the multiple of $11$, and $19$, and the other comes from the basic period.

 General Proof of $n^2 \mid b^n+1$

$1$.  $n$ is odd for all  $b$

Suppose $n$ is even, say $n=2e$,  then we have $4 \mid 4e^2 \mid  b^{2e}+1$.  However, the last term is never a multiple of $4$, so $n$ must be odd.

$2$.  Rule of descent.

Suppose that $p \mid n$ and $p \mid b^q+1$,  then $q \mid n$.

This is because $p \not\mid b^x+1$ unless $q \mid x$.  q either is 1, or has prime divisors.  Put $p'$, $q'$ for each divisor of $q$, and repeat.

$2a$  The rule of ascent.

If for some $p \not\mid n$, that its $q \mid n$, then $pn$ is a further solution.

This is used to ascend from instances where $q=1$, ie $p \mid b+1$, as a general construction where allowed.

$3$   Rule of sevenites and repeaters.

If $p^m \mid n$, then $p^m \mid (b^n+1) /(b^q+1)$, and for $p^{2m} \mid b^n+1$, then $p^m \mid b^q+1$.

If $p \mid b^x+1$ then $p \mid (b^{px}+1 )/(b^x+1)$.  This and $b^g+1 \mid b^{gh}+1$ for odd $g, h$, means that if $p^m \mid n$ then $p^n \mid (b^n+1)/(b^q+1)$.

$p \mid (b^{px}+1)/(p^x+1)$ repeats some $p$ before it.  It is easy to show that $p^2$ won't work here except in one case of $p=2$.  This means that if $p^m \mid n$, then it is needed that $p^m \mid b^q-1$.  Repeaters are why $p^m$ can have periods.  For example, 3 has a 2-digit period in base 2, and 9 has a 6-digit period, and 27 has an 18 digit period.

A sevenite is where if $p \mid b^n-1$, then so does $p^2$.  See link below for sevenites to bases to $2112$ and $p<144000$.

http://z13.invisionfree.com/DozensOnline/index.php?showtopic=737

 Discussion

We see that the rule of descent means that it is only necessary to start from the divisors of $b+1$, which give $q=1$.  Then we consider the divisors of $b^x+1$, where $x$ is an odd divisor of $b+1$.  This means that $3, 7, 15, 31, \cdots$ have no further action, because there are no odd divisors > 1.

For $b=10$, we see that $b+1=11$, and that $10^{11}$ has divisors $11^2 \cdot 23 \cdot 4093 \cdot 8779$.  The product of $11$ and any of these primes >11, will satisfy this relation.  We also see that by the rule of descent, if $47$ works, then $23$ must also divide $n$.  In fact, 23 brings in $47, 139, 2531$.  $139$ in turn brings in $557$ and $2503$.  The rule of descent applies here.  So if $2531$ divides $n$ in $n^2 \mid 10^n+1$, then so must 23, 11.  So $640343$ is a solution.  It can be further multiplied by $139$ or $47$ or $4093$ or $8779$, because the descent paths are already there.

   1    11
  11    23   4093  8779
  23    47   139   2531
  47   6299
 139    557 2503

When $b+1$ is composite, as in $b=14$, one can descend to any of the divisors of $b+1$. This is the table of descent for $b=14$.   As before, the numbers to the right are $p$ having the first as their $q$.

   1    3   5
   3    61
   5    71  101
  15    811
  61    90281
  71    569  3620291
 183    733  9151
 213    1287799

The marker example here is $80$, where $80+1=3^4$. amd $80^3+1 = 3^5\cdot 7^2 \cdot 43$.  One of the three's in $80^3+1$ is a repeater, but this means that any prime whose $q$ comes to a divisor of $3^4 7^2 43$ can be immediately multiplied to give an additional solution.  Specifically $127 (q=21)$, $163 (q=81)$ and $883 (q=441)$ all work, as does any numner $3 | n | 3^4 7^2 43$.  These, and several very large primes, all work in base $80$, with the usual rule of descent.

    1    3  3 3 3
    3    7  7  43
    7    29  4789 ..
   21    127  ...
   43    1721
   81    163

The rule of descent fails in $b=2$

When we start off with $2$, we have $2+1=3$, which allows us to consider the factors of $2^3+1$, other than $3$.  But there are not any factors.

We could try to follow the rule of descent, noting that if $n$ is odd, then any prime that divides $n$ must be $1, 3$, mod $8$.  The list starts $3$, $11$, $17$, $19$, $41$, $43$, $67$.  If either $p$ or its derived $q$ is not factorised to this list, we can strike it out.

We see here the significance of the test for $55$ and $171$ in the previous posts.  Both of these work for the larger prime, but fail on descent.  This is the magic here.  Their paths are broken, but they open the way for possible unbroken paths.

$11$ fails, since $q=5$ is not in the list.  $19$ has $q=3*3$, both in the list, but we see by the rule of power, that if $3^2 \mid n$, then $3^2 \mid 2^1 +1$, which it doesn't.  $17$ and $41$ yield even $q=4, q=10$.  $67$ yields $33 = 3* 11$, but we see that $11$ implies $5$.  $43$ yields $7$, not in the list.

Larger primes have a period larger than 10, so these $p$ can not divide, because $q$ has been disallowed.

There is no path of descent, so $3$ is the sole example.


How do I find parity check matrix if generator matrix can't be written in standard form? $G=\left ( \begin{matrix}
1 &1  &0 &1&0&0&1\\
 1&0  &1 &0&1&0&1\\
 0&1  &1&0&0&1&1
\end{matrix} \right )$

Is it possible to get parity check matrix if generator matrix is not in the standard form?

Say $C$ is your code with generator matrix $G$. If you reduce $G$ to echelon form, you obtain
$$\begin{bmatrix} 1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\end{bmatrix}$$
which is unfortunately not in standard form.

BUT, we can put it in standard form by swapping the third and fourth column, so we get
$$G^{\prime} =
\begin{bmatrix} 1&0&0&1&1&0&1\\0&1&0&1&0&1&1\\0&0&1&0&1&1&1\end{bmatrix}$$

This $G^{\prime}$ is the generator matrix for a different (but equivalent) code $C^{\prime}$, where the 3rd and 4th positions of our codewords have been swapped. So $C^{\prime}$ has parity check matrix
$$H^{\prime} =
\begin{bmatrix}
 1 & 1 & 0 & 1 & 0 & 0 & 0\\
 1 & 0 & 1 & 0 & 1 & 0 & 0\\
 0 & 1 & 1 & 0 & 0 & 1 & 0\\
 1 & 1 & 1 & 0 & 0 & 0 & 1
\end{bmatrix}$$
And we translate it back to a parity check for $C$ be swapping the third and fourth columns back again
$$H =
\begin{bmatrix}
 1 & 1 & 1 & 0 & 0 & 0 & 0\\
 1 & 0 & 0 & 1 & 1 & 0 & 0\\
 0 & 1 & 0 & 1 & 0 & 1 & 0\\
 1 & 1 & 0 & 1 & 0 & 0 & 1
\end{bmatrix}$$

You can perform elementary row operations on $G$ to produce a row-equivalent generator matrix $G' = EG$ where $E$ is a matrix corresponding to said row operations and $G'$ has the form $G' = [I \mid A]$ (reduced row echelon form). A parity check matrix for $G'$ is $H = [-A^T\mid I]$. Using block matrix multiplication, you can check that $G'H^T = 0$. Since $G' = EG$, $EGH^T = 0$. Since $E$ is invertible, this implies that $GH^T = E^{-1}0 = 0$. So $H$ is parity check matrix for $G$.


Are two square matrices having the same eigenvalues and the same eigenspaces equal matrices? Does possessing the same eigenvalues and the same eigenspaces imply the equality of the matrices? If yes, then is the converse of this implication also true? I mean if the answer is yes, then is having the same eigenvalues and the same eigenspaces only a sufficient condition for the equality of the square matrices or is it the necessary and sufficient condition?

The matrices

$$\left[ \begin{array}{cccc} \lambda & 1 & 0 & 0 \\
 0 & \lambda & 0 & 0 \\
 0 & 0 & \lambda & 1 \\
 0 & 0 & 0 & \lambda \end{array} \right], \left[ \begin{array}{cccc} \lambda & 0 & 0 & 1 \\
 0 & \lambda & 0 & 0 \\
 0 & 1 & \lambda & 0 \\
 0 & 0 & 0 & \lambda \end{array} \right]$$

have the same eigenvalues and eigenspaces, but are different. They can be distinguished by their generalized eigenspaces.

This  would imply any diagonalisable matrix is diagonal, which is absurd, as similar matrices do have the same eigenvalues and the same eigenspaces.


Need help with boundary conditions of a differential equation. QUESTION:

A particle $A$ is moving along the $X$ axis at a constant horizontal velocity $u\hat{i}$. Another particle $B$ is moving such that its velocity vector always points towards the particle $A$. $B$ moves with a constant speed $v$. At time $t = 0$, position of $A$ is $(0,0)$ and that of $B$ is $(0, L)$. What is the time when the particles collide?

What I did:

I set up the differential equations, however I am getting something stupid. This is what I did:

Let the position vector of $A$ be
$$\vec{a}(t) = ut\hat{i}$$

and that of $B$ be $$\vec{b}(t) = x(t)\hat{i} + y(t)\hat{j} = x\hat{i} + y\hat{j}$$ (for notational convenience).

Now, the velocity vector of $B$ is
$$\vec{v}(t) = \lambda(\vec{a}(t) - \vec{b}(t))$$

where we'll $\lambda$ is some constant that we'll figure out later. This equation is true as $\vec{v}$ is collinear with the vector $\vec{BA}$.

So,
$$ \dfrac{d}{dt} \Big(\vec{b}(t)\Big) = \lambda(\vec{a}(t) - \vec{b}(t))$$
$$ \dfrac{d}{dt} \Big(x\hat{i} + y\hat{j}\Big) = \lambda((ut-x)\hat{i} - y\hat{j})$$

Separating the components (is this step wrong? I don't know vector calculus, but I believe this must be true) we have:

$$ \dfrac{d}{dt}(x) = \lambda\cdot(ut-x) $$
$$ \dfrac{d}{dt}(y) = \lambda\cdot(-y) $$

I could solve the first differential equation. Solving the second one:
$$ \dfrac{dy}{y} = - \lambda \cdot dt $$
That part was easy but the boundary conditions are the trouble makers:

$$ \text{Intitial: } y = L, t = 0 \\ \text{Final: } y = 0, t = T $$

So,
$$ \ln y\Bigg|_{L}^{0} = -\lambda \cdot t \Bigg|_{0}^T \,\,\,\, \text{Ln(0)?!?!?!} $$

What's wrong?

Or is there any other way to solve the problem? Then Hints are of course welcome :D

$$a(t) = ut i$$
let particle $B$ make an angle $\theta$ with y axis .then you will see
$$B(t) =vtsin\theta i  + (L - tvcos\theta) j$$
hen they collide $a(T) = b(T)$
T is time of collision .we get $$sin\theta = \frac{u}{v}..(1)$$
and$$cos\theta = \frac{L}{vt}...(2)$$
square $(1)$ and $(2)$ and add , further solve for $T$.
we get,
$$T = \frac{L}{ \sqrt{v^2 - u^2} }$$


Intuition: Why is continuous decay expressed as the inverse of the equivalent continuous growth rate? I understand $e$ as $\lim_{n \to \infty} \big(1+\frac{1}{n}\big)^n$. I also (finally) understand the idea that continuous growth is "a rate that is applied constantly to the amount present at any instant" (see Confusion about Continuous Growth being "a rate that is applied constantly to the amount present at any instant").

I'm trying to understand continuous decay in terms of / compared to  (and maybe this is my problem) continuous growth. I think I have decent physical intuition as to what it "means", however what is not obvious to me is why it is expressed as $\frac{1}{e}$. It vaguely seems to make sense (division as opposed to multiplication...), but it's not clear at all.

I've also derived it algebraically as such:

Let $t = -n$, then $$\bigg(1-\frac{1}{n}\bigg)^n = \bigg(1 + \frac{1}{t}\bigg)^{-t} = \Bigg[\bigg(1 + \frac{1}{t}\bigg)^{t}\Bigg]^{-1}$$ so that

$$\lim_{t \to \infty} \Bigg[\bigg(1 + \frac{1}{t}\bigg)^{t}\Bigg]^{-1} = e^{-1} = \frac{1}{e}$$

However, I find little comfort and intuition in the algebra.

Is there a way to think about this that makes it obvious why continuous decay is expressed as the inverse of the equivalent continuous growth rate?

Or in other words, why $\lim_{n \to \infty}\big(1-\frac{1}{n}\big)^n = \frac{1}{e}$

Ok, so this is what I've come up with.

You can express $1+\frac{1}{x}$ as $\frac{x+1}{x}$, such that $\big(1+\frac{1}{x}\big)^x = \big(\frac{x+1}{x}\big)^x$

And you can express $1-\frac{1}{x}$ as $\frac{x-1}{x}$, such that $\big(1-\frac{1}{x}\big)^x = \big(\frac{x-1}{x}\big)^x =\frac{1}{\big(\frac{x}{x-1}\big)^x}$

Now $\big(\frac{x}{x-1}\big)^x$ and $\big(\frac{x+1}{x}\big)^x$ look very similar and you can guess (and see on Mathematica) that $\lim_{x \to \infty} \big(\frac{x}{x-1}\big)^x$ also approaches $e$.

Then,

$$\lim_{x \to \infty} \big(\frac{x}{x-1}\big)^x = \lim_{x \to \infty} \big(\frac{x}{x-1}\big)^{x-1} \cdot \lim_{x \to \infty} \big(\frac{x}{x-1}\big)$$ $$= \lim_{x \to \infty} \big(\frac{x}{x-1}\big)^{x-1} \cdot 1$$ $$=\lim_{x \to \infty} \big(\frac{x+1}{x}\big)^x = e$$

Also, taking actual numbers. At $x=10$ you get $$\bigg(1-\frac{1}{10}\bigg)^{10} = \bigg(\frac{9}{10}\bigg)^{10} = \frac{1}{\big(\frac{10}{9}\big)^9 \cdot \frac{10}{9}} = \frac{1}{\big(1+\frac{1}{9}\big)^9 \cdot \frac{10}{9}}$$

Where you can see that as $x$ grows to infinity, the left factor in the denominator converges towards $e$ as the right factor converges to 1.

If the notion of matter can neither be created nor destroyed is true, but merely changed in state, then if you decay matter over time, it seems this could only occur due to the radiation of energy, thus decaying the element to a lesser element.
This may be the reason 1/e is necessary.
I could be wrong though.

markc


Proof Verification/Doubt: Showing $f(x)=1/x^2$ is not uniformly continuous on $(0,\infty)$ Show that $f(x)=1/x^2$ is not uniformly continuous on $(0,\infty)$

So I was trying to attempt this question and did the proof as follows:

$f(x)$ is not defined at the point $x=0$. Then, by the continuous extension theorem, $f(x)$ is not uniformly continuous on the interval $(0,\infty)$

I checked the answer to this question in the solution manual, and this was not the approach they used. Rather, they used the non uniform continuity sequential criteria.

My question is, is my proof correct? I am particularly concerned about the interval being $(0,\infty)$ rather than some interval $(a,b)$ where $b \in \mathbb{R}$, so I'm now unsure if the continuous extension theorem is even applicable at all in this case.

Thank you.

In a comment, A.Asad has clarified:

  Theorem 1 (The Continuous Extension Theorem): If $I=(a,b)$ is an interval, then $f:I\to\mathbb{R}$ is a uniformly continuous function on $I$ if and only if $f$ can be defined at the endpoints $a$ and $b$ such that $f$ is continuous on $[a,b]$.

Using this theorem, you need to show that $f(0)$ cannot be defined so that $f$ is continuous. Simply saying that "$f(0)$ is not defined" is not quite enough. Something like "$\lim\limits_{x\to0}f(x)$ does not exist, so there is no value of $f(0)$ that would make $f$ continuous at $0$" would be good.

Regarding your concern at the end of your question: if $f$ is not uniformly continuous on $(0,1)$ then it is not uniformly continuous on $(0,\infty)$.

We can simply use the definition of uniform continuity. Note that
$$
f\left(\frac1{\sqrt{n+2}}\right)-f\left(\frac1{\sqrt{n\vphantom{1}}}\right)=2
$$
yet
$$
\begin{align}
\left|\frac1{\sqrt{n\vphantom{1}}}-\frac1{\sqrt{n+2}}\right|
&=\frac2{\sqrt{n\vphantom{1}}\sqrt{n+2}\left(\sqrt{n\vphantom{1}}+\sqrt{n+2}\right)}\\
&\le\frac1{n^{3/2}}
\end{align}
$$
So we can't find a $\delta\gt0$ so that $|x-y|\le\delta\implies|f(x)-f(y)|\le1$.

$f$ is uniformly continuous on $[a,\infty)$ for any $a>0$ so you can concentrate on what happens near $0$. The correct argument is the following: if $f$ is uniformly continuous and $x_n$ decreases to $0$ then $\{f(x_n)\}$ is a Cauchy sequence (as you can see from definition of uniform continuity) hence convergent; since $\frac 1 {x_n^{2}} \to \infty$ we have a contradiction. I believe this is what you had in mind but the way you expressed the idea is not correct.


Fourier transform of partial differential equation How would I find the Fourier Transform of the pde
$$
u_t = u_{xx} + \alpha\cdot u_x,\quad\alpha > 0\,?
$$
I know the definition of the Fourier transform, but I'm not sure how to use it in the context of partial differential equations.

If $f : \mathbb R\to\mathbb C$ is a "nice" function (i.e. $f\in H^1$ or $f\in C^1$ with $f(\pm\infty) = 0$) the Fourier transform of its derivative is by partial integration
$$
\widehat{f'}(\omega) = \int f'(x)e^{-2\pi ix\omega}\,dx = 2\pi i\omega\int f(x)e^{-2\pi ix\omega}\,dx = 2\pi i\omega\cdot\hat f(\omega).
$$
So if $U(\omega,t)$ denotes the Fourier transform of $u(x,t)$ with respect to $x$, applying the Fourier transform with respect to $x$ to $u_t = u_{xx} + \alpha u_x$ gives
$$
U_t = -4\pi^2\omega^2 U + 2\pi i\omega\alpha U = (-2\pi + i\alpha\omega)2\pi U.
$$

Just ignore $t$ and apply the transform as usual, you'll get something like

$$ U_t = -\omega^2 U + i\alpha \omega U $$

where $U(\omega,t)$ is the Fourier transform of $u(x,t)$, given by

$$ U(\omega,t) = \frac{1}{\sqrt{2\pi}}\int_{\Bbb R} u(x,t) e^{-i\omega x}dx $$

Some constants may apply, depending on your definition of the Fourier transform.


From an infinite summation to an integral It is a well known formula that, given a suitably well behaved function, we have
$$
\lim_{n\to\infty} \dfrac{1}{n}\sum_{k=1}^{n} f(k/n) = \int_0^1 f(x)dx.
$$
I am interested in an infinite version of this. Is it true that
$$
\lim_{n\to\infty} \dfrac{1}{n}\sum_{k=-\infty}^{\infty} f(k/n) = \int_{-\infty}^\infty f(x)dx?
$$
Edit: We can assume that the function has sufficient smoothness and decays sufficiently fast for the summations and integrations to make sense.

Let $\varphi_n(t)=f\left(\frac{\lfloor nt\rfloor}{n}\right)$, then
$$ \int_{-\infty}^{+\infty}\varphi_n(t)dt=\sum_{k=-\infty}^{+\infty}\int_{\frac{k}{n}}^{\frac{k+1}{n}}\varphi_n(t)dt=\frac{1}{n}\sum_{k=-\infty}^{+\infty}f\left(\frac{k}{n}\right) $$
However for all $t\in\mathbb{R}$, $\lim\limits_{n\rightarrow +\infty}\varphi_n(t)=f(t)$ (I suppose that $f$ is continuous). If we get an upper bound $|\varphi_n|\leqslant g$ where $g\in L^1(\mathbb{R})$ then we can use the dominated convergence theorem, therefore
$$ \lim\limits_{n\rightarrow+\infty}\int_{-\infty}^{+\infty}\varphi_n(t)dt=\int_{-\infty}^{+\infty}f(t)dt $$
and you get the desired equality. In order to have such an upper bound, we can suppose that $f$ is monotone, thus we have $|\varphi_n(t)|\leqslant |f(t)|$ if $f$ is non-decreasing and $|\varphi_n(t)|\leqslant |f(t-1)|$ if $f$ is decreasing. We can also suppose that there exists $\delta>0$ such that $f(t)=\underset{t\rightarrow\pm\infty}{\mathcal{O}}\left(\frac{1}{t^{1+\delta}}\right)$ because there would exist $M>0$ such that $|f(t)|\leqslant\frac{M}{(1+|t|)^{1+\delta}}$ for all $t\in\mathbb{R}$ and therefore $|\varphi_n(t)|\leqslant\frac{C}{(1+|t|)^{1+\delta}}$ where $C>0$.

In my opinion it would not work.
You should do something like this:
$$\lim_{n\to\infty} \sum_{h=-\infty}^{+\infty}\frac{1}{n}\sum_{k=1}^{n}f\bigg(\frac{k}{n}+h\bigg)$$


Prove $|\mathcal P(A)|+|\mathcal P(B)|= |\mathcal P(A)\cup \mathcal P(B)|$ using addition counting principle Let $A$ and $B$ be subsets of the finite set $S$ with $S = A\cup B$ and $A\cap B=\emptyset$. Denote by $\mathcal{P}(X)$ the power set of $X$ and denote by $|Y|$ the number of elements in the set $Y$.
Given a statement $|\mathcal P(A)|+|\mathcal P(B)|= |\mathcal P(A)\cup \mathcal P(B)|$.
Use the Addition Counting Principle to prove or disprove the statement.

I understand that its asking me to find the elements of $\mathcal P(A)$ and $\mathcal P(B)$, but where does $\mathcal{P}(X)$ and $|Y|$ fit in to solve this question?

Well, by the principle of inclusion-exclusion:

$|X\cup Y| = |X|+|Y|-|X\cap Y|$

for finite sets $X,Y$. So in general, your statements does only hold if $P(A)$ and $P(B)$ are disjoint.

I just had this problem myself, and thought up of an answer.

(also posting this for others looking for it)

the $X$ and $Y$ you are questioning are just general terms to describe the functions of modulus (size) $\lvert Y \rvert$, and power set $P(X)$.

The assumption given is that sets $A$ and $B$ are disjoint (hence, their intersection is the empty set), so they have no items in common. Given what we know about the Addition Counting Principle, if 2 sets are finite and disjoint, $\lvert A \cup  B \rvert = \lvert A \rvert + \lvert B \rvert$, and is finite.

In order to prove/disprove $\lvert P(A) \rvert + \lvert P(B) \rvert =  \lvert P(A) \cup  P(B) \rvert$ we must also think about what $P(A)$ and $P(B)$ have in common, just like with sets $A$ and $B$.
We know that the classes $P(A)$ and $P(B)$ are made of sets that are disjoint, so they will have no subsets that are the same. There is only $1$ element shared in both, because that element is also an element of all sets.

So, because $P(A)$ and $P(B)$ share at most $1$ element, they are not disjoint and we cannot conclude that $ \lvert P(A) \rvert + \lvert P(B) \rvert = \lvert P(A) \cup P(B) \rvert$.

Here's an example that I used to convince myself of this.
$S = \{1,2,3,4,5\}$,
$A = \{1,2,3\}$, $\lvert A \rvert = 3$
$B = \{4,5\}$, $\lvert B \rvert = 2$

$\lvert A∪B \rvert = \lvert A \rvert + \lvert B \rvert = 3 + 2 = 5$
so, $A \cup B = \{1,2,3,4,5\} = S$, $\lvert S \rvert = 5$.

$P(A) = \{\emptyset, A, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{3,2\}\}$,
$\lvert P(A)\rvert = 2^{\lvert A \rvert} = 2^3 = 8$ elements.

$P(B) = \{\emptyset, B, \{4\}, \{5\}\}$,
$\lvert P(B) \rvert = 2^{\lvert B \rvert} = 2^2 = 4$ elements.

$P(A) \cup P(B) = \{∅, A, B, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{3,2\}, \{4\}, \{5\}\}$,
$\lvert P(A) \cup P(B) \rvert = 11$ elements; as union does not take duplicates, as in $\emptyset$.

so $\lvert P(A) \cup P(B)\rvert \neq \lvert P(A)\rvert + \lvert P(B) \rvert$, as in $8 + 4 = 12 \neq 11$.


Finding all real roots of the equation $(x+1) \sqrt{x+2} + (x+6)\sqrt{x+7} = x^2+7x+12$ Find all real roots of the equation
$$(x+1) \sqrt{x+2} + (x+6)\sqrt{x+7} = x^2+7x+12$$

I tried squaring the equation, but the degree of the equation became too high and unmanageable. I also tried substitutions, but it didn't work out correctly. This question was in my weekly class worksheet as were this and this question which I previously asked.
Any help will be appreciated.
Thanks.

Let $\sqrt{x+2}=a$ and $\sqrt{x+7}= b$.

So, $x + 1 = a^2 -1$

$x+6 = b^2 -1$

$ x^2 + 7x + 12= (x+3)(x+4)= (b^2-4)(a^2+2)$

Substituting and solving the system of equations.


The function $f : \mathbb{R} \to \mathbb{R}$ satisfies $f(x) f(y) = f(x + y) + xy$for all real numbers $x$ and $y.$ Find all possible functions $f.$ The function $f : \mathbb{R} \to \mathbb{R}$ satisfies
$f(x) f(y) = f(x + y) + xy$ for all real numbers $x$ and $y.$ Find all possible functions $f.$
I started by letting $x = y = 0$, which made $f(0) = 1$.  I'm not sure what to do now. Any help is appreciated!! :)

Now, let $(x,y)=(1,-1).$
Thus, $f(1)f(-1)=0.$
If $f(1)=0$ so let $y=1.$
We obtain: $$f(x+1)+x=0$$ or $$f(x)=1-x$$ and easy to check that it's a solution.
If $f(-1)=0$ so let $y=-1$.
We obtain:
$$f(x-1)=x,$$ which gives $$f(x)=x+1$$ and we can check again that it's a solution.

Now set $y=-x$ which, since we have established that $f(0)=1$ gives $$f(x)f(-x) = 1-x^2 = (1+x)(1-x)$$ so $f(x) = 1+x$ and by symmetry $f(x) = 1-x$ are both solutions.


St. Petersburg Paradox. Expected value seems wrong. Related: St. Petersburg Paradox
I was reading today the Wikipedia page on the St. Petersburg Paradox.
The posted expected value is: $ 1/2 * 1 + 1/4*2 + 1/8*4 ... $
This seems very wrong to me. Here is a game which would lead to the same expected value calculation:
Flip a coin. If it's heads, you win \$1.
Regardless of result of previous game: Flip 2 coins. If both are heads, you win \$2.
Regardless of result of previous game: Flip 3 coins. If all three are heads, you win \$4.
...
Regardless of result of previous game: Flip N coins. If all are heads, you win $\$2^{N-1}$.
And you take this as N goes to infinity
Now this game obviously has an infinite expected value, and I would pay any amount of money to play it. It's hard to believe that the original game has the same expected value as this one.
Is there a flaw in my reasoning?

I don't think your constructed game and St. Petersburg are equivalent even though they have the same expected value. Consider this: in SP, your payout is always a power of 2; in your game you can have any whole number payout. That is, if you look at the probability of winning \$3 in SP, it's obviously $0$, whereas in your game, it's some finite non-zero value.

And we can't even claim that the expected payout of both the games is same. Sure both tend to infinity, but you can't say that their expected payout is the same on that basis. Consider $E_1$ to be the payout of SP and $E_2$ the payout of your game.
$$E_1= 1 P_1(1)+2 P_1(2) + 3P_1(3) + \cdots  $$
$$E_2= 1 P_2(1)+2 P_2(2) + 3P_2(3) + \cdots$$

Clearly, $P_1(3)=0$ but $P_2(3) \neq0$ and is some finite value. Same goes for the other terms. So you can see that $E_2>E_1$, hence the expected value of your game is more than SP.


How the answer of this question is 4? I'm learning Sets and at current about Power Set. I'm confused in a example given in my book. Please have a look at the image.

I didn't get the last two lines of the solution. Please help. Thankyou in advance.

Probably the clustering of empty set symbols and nested set braces is the most confusing here.

The empty set has only one subset: $\emptyset$ itself, hence $P(\emptyset)$ is a one-element set with $\emptyset$ as only element.
For any one-element set $X=\{a\}$ we have $P(X)=\{\emptyset,X\}$ as the empty set and the full set itself are the only subsets of $X$. Hence $P(P(\emptyset))$ is a two-element set.
For any two-element set $X=\{a,b\}$ (note that $a\ne b$), there are precisely four subsets of $X$, namely $\emptyset$ and $\{a\}$ and $\{b\}$ and $\{a,b\}$. Hence $P(P(P(\emptyset)))$ is a four-element set.
If you recall that $a=\emptyset$ and $b=\{\emptyset\}$ we can expand the enumaration of $P(P(P(\emptyset)))$:
$$ P(P(P(\emptyset)))=\{\emptyset,\{a\},\{b\},\{a,b\}\}=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\}$$

If you want so experience an even more confusing notation, use $\{\}$ for $\emptyset$:
$$ P(P(P(\{\})))=\{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\}\}$$


If $\mathfrak{c} = 2^\mathbb{N}$ why $|D^\mathfrak{c}|=\mathfrak{c}$ with $D = \{0, 1\}$. Let $\mathfrak{c} = 2^\mathbb{N}$ and $D^\mathfrak{c}$ be the topological product of $\mathfrak{c}$ copies
of the discrete Abelian group $D = \{0, 1\}$. If $D^\mathfrak{c}$ taken as a group is denoted by $G$,
and $D^\mathfrak{c}$ taken as a topological space is denoted by $X$.

Why $|G| = |X| = c$?

I think maybe it has to do with Boolean but I'm not sure.

On the other hand I am correct or I am wrong that $|G| = |D^\mathfrak{c}|=|D|^\mathfrak{c} =2^\mathfrak{c}> \mathfrak{c}$?

I am studying this example of Korovin Orbits in the book Topological groups and related structures of Mikhail Tkachenko.

Thank you for your Help!

It is the case that $|D^{\mathfrak{c}}|=2^{\mathfrak{c}}$. We can find a bijection from the product of $\mathfrak{c}$ copies of $D$, which you have written $D^{\mathfrak{c}} $, to the power set $2^{\mathfrak{c}}$ of $\mathfrak{c}$ as follows.

If $x\in D^{\mathfrak{c}} $, then $x$ essentially consists of a mapping from each element of $\mathfrak{c}$ to either $0$ or $1$, and we may write $x(c)$ to denote the value ($0$ or $1$) corresponding to $c\in\mathfrak{c}$. Let $S(x)$ be the set of all elements $c\in \mathfrak{c}$ for which $x(c)=1$. Then $S: D^{\mathfrak{c}} \mapsto 2^{\mathfrak{c}}$ is a bijection. In essence, $x$ acts as an “indicator function” for every subset of $\mathfrak{c}$ indicating (with a $1$) which elements of $\mathfrak{c}$ the subset contains.


Prove using natural deduction that $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ I ran into some trouble proving the following:

$(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$

My approach thus far:

Honestly I'm really stuck. So basically my hypothesis requires this $R$, hence the first thing that came to my mind is the Law of Excluded Middle. Using $R$ is trivial. The problem comes with $\neg R$. I can't seem to proceed from there.

Any help or insights is deeply appreciated.

Since the conclusion $(Q→P)∨(P→Q)$ is a tautology, one does not need the premise to prove the conclusion. One can prove this using the Law of the Excluded Middle (LEM) in the following manner:

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/

You can use the exportation law

$ ( R \to (P \to Q)) \Leftrightarrow (( R \land P ) \to Q) $

to reduce this question to
prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$

Which you have already asked.


Multiplicative inverse of $x+f(x)$ in $\Bbb Q[x]/(f(x))$ So I have $f(x) = x^3-2$ and I have to find the multiplicative inverse of $x + f(x)$ in $\mathbb{Q}[x]/(f(x))$. I'm slightly confused as to how to represent $x + (f(x))$ in $\mathbb{Q}[x]/(f(x))$. Would I be just finding the inverse of $x+1$? How would I do that? Thanks a lot!

Note $x^3=2$ in the quotient, so $x\cdot x^2=2$ (in the quotient) so $x\cdot {1\over 2}x^2=1$.

$1=(x+1)(\frac{x^2-x+1}{3})-\frac{x^3-2}{3}$, then $\frac{x^2-x+1}{3}$ is the multiplicative inverse of $x+1+\langle f\rangle$ in $\frac{\mathbb{Q}[x]}{\langle f\rangle}.$


Comparing two Standard Normal Correlated Variables Let's say I have two standard normal variables $X, Y$ (both with mean 0 and variance 1) with correlation $\rho > 0$. Can I make any conclusions about their joint distribution?

For example, can I figure out $P(X > c,Y > c)$ for some $c \in \mathbb{R}$? The joint density of $X$ and $Y$ is no longer symmetrical (since they aren't independent) so I can't really do any geometric tricks. Is there a joint CDF or something else I'm missing?

Just consider the function graphically, and all should be clear:

which represents the joint distribution:

$$p(x,y) \propto e^{{\bf x}^t {\bf M} {\bf x}}$$

where ${\bf M} = \{ \{1, \rho\}, \{\rho, 1)\} \}.$

This is joint distribution with correlation $\rho = .5$ highlighted by the criterion $x<.5$ and $y<.5$.  Any moment, or correlation is just over the relevant region.   So if you want to calculate moments (for instance), then just integrate over the appropriate region.

The red is of course symmetrical, as the distribution dictates.


Proving that there doesn't exist a binary code with parameters [6,5,4] I'm new to code theory and I'm having trouble with proving if a code doesn't exist in general.
I found a binary code with the parameters [6,4,4] but I don't really understand why there cant be one with parameters [6,5,4].
It would help a lot having an example of such problems.

Thanks in advance.

Assuming you mean a linear error-correcting code, a common interpretation of "[6,5,4] code" is a code using $6$-bit codewords to represent $5$-bit messages where any two distinct codewords differ in at least $4$ bits.

There are $2^6 = 64$ possible codewords.  We have $2^5 = 32$ messages.  In the lattice $\{0,1\}^6$, each codeword is surrounded by an open ball of radius $4$ containing no other codewords.  One can use the Singleton bound to show that $5 + 4 \leq 6 + 1$ if this code is realizable.  However, $9 \not \leq 7$, so this code is not realizable.

The Singleton bound is a very loose bound.  Generally, for a realizable [c,m,d] linear error-correcting code, the inequality is $m+d \leq c+1$.  The Singleton bound also indicates there is no realizable [6,4,4] linear error-correcting code.

There is another way to show there is no [6,5,4] linear error-correcting code.  We have $64$ codewords and $32$ messages.  By distance 4, there can be no pair of messages assigned to complementary codewords.  By the pigeonhole principle, since there are only $32$ such pairs of codewords, any such pair has exactly one message assigned to it.  This means there is a message assigned to exactly one of $000000_2$ and $111111_2$.  Similarly, there is exactly one message assigned to the codeword pair $000111_2$ and $111000_2$.  However, no such assignment is possible since any member of one pair is only distance three from either member of the other pair.  \begin{align*}
d(000000_2, 111000_2) &= 3 \text{,} \\
d(000000_2, 000111_2) &= 3 \text{,} \\
d(111111_2, 111000_2) &= 3 \text{, and} \\
d(111111_2, 000111_2) &= 3 \text{.}
\end{align*}
Consequently, there is no [6,5,4] linear error-correcting code.

(This counting argument can be adapted to show there is in [6,4,4] linear error-correcting code.  Take the codewords in groups of $4$ having matching first four bits.  This gives 16 groups each member of which differs from the other members of its group in only two bits, so at most one of those codewords is assigned to a message.  There are 16 messages, so each group is assigned exactly one messsage.  Then the groups $0000{*}{*}_2$ and $0001{*}{*}_2$, where "$*$" represents a bit whose value is either $0$ or $1$ (but this is not critical since either choice gives a codeword in the same group), each have a message, but regardless of which codeword is chosen in each group, those codewords differ in at most three bits.)

Assuming you are talking about non-trivial perfect binary codes of the form $[l,x,d]$, we have that the code can correct up to $e=\lfloor\frac{d-1}{2}\rfloor$ errors. If a non-trivial perfect binary code exists, it must hold that $\sum_{i=0}^e\binom{l}{i}$ is a power of $2$.

In our case, $d=4$, so $e=\lfloor\frac{3}{2}\rfloor=1$ and $l=6$. $\binom{6}{0}+\binom{6}{1}=1+6=7$ which is not a power of $2$, so such code cannot exist, unless it's trivial.


Abelian group of order 99 has a subgroup of order 9 Prove that an abelian group $G$ of order 99 has a subgroup of order 9.

I have to prove this, without using  Cauchy theorem. I know every basic fact about the order of a group.

I've distinguished two cases :

if $G$ is cyclic, since $\mathbb Z/99\mathbb Z$ has an element of order $9$, the problem is solved.
if $G$ isn't cyclic, every element of $G$ has order $1,3,9,11,33$. I guess I need to prove the existence of an element of order $9$. How should I do that ?

Note that $G$ is abelian (I haven't used it yet).

Context: This was asked at an undergraduate oral exam where advanced theorems (1 and 2) are not allowed.

There exists an element $a$ of order $3$. If there was not every element would need to have order $11$.

But then a counting argument leads to contradiction.

We take the quotient group $ G/<a>$. Then it has order $33$. The same argument shows that there exists an element $b$ of order $3$. Take the map $p: G \rightarrow G /<a>$ the natural projection. The pre-image of a subgroup is a subgroup, so we take the subgroup of $G$ $p^{-1}(<b>)$. And this subgroup has order $9=|\rm{Ker p}|| <b>| $.

If it's abelian then you know it's a product of cyclic groups.  You know that the order of these cyclic groups can be $3, 9, 11, 33$, or $99$ and their product must be $99$.  You've already seen that if $99$ is in their that you're done, and if $9$ is in their then you're done.  So your left with a product of cyclic subgroups of orders $3, 11$, or $33$ and their product must be $99$.

So show that $\mathbb Z/33$ has a subgroup of order $3$ and you must have either this group and $\mathbb Z/3$ or you must have two copies of $\mathbb Z/3$.  In either case this gives you a subgroup of order $9$.


Convergence of a sequence of functions depending on a sequence of points Let the sequence $(x_k)_{k\in\mathbb{N}}$ converge to $x$, where $x_k\in D\subset \mathbb{R}$.
Let $(f_k)_{k\in\mathbb{N}}$ be a sequence of functions from $D$ to $\mathbb{R}$ such that
$
\lim_{k\to\infty} f_k(x) = f(x),
$ for any fixed $x\in D$.

How do you prove or disprove that
$$
\lim_{k\to\infty} f_k(x_k) = f(x).
$$
(I may guess it is necessary to assume $f(x)$ continuous)

Answer is negative.

Take $D=[0,1]$,$x_k=\frac{1}{k+1}$ and $f_k$ defined by:

$f_k(0)=0$
$f_k(x_k)=1$
$f_k(2 x_k)=0$
$f_k$ linear on $[0,x_k]$ and $[x_k,2 x_k]$
$f_k(x)=0$ for $x \in [2x_k,1]$

$f_k$ converges to the function equal to $0$ on $[0,1]$. However $f_k(x_k)=1$ for $k \in \mathbb{N}$ and $f(0)=0$.


Does a group with exponential growth always have a hyperbolic subgroup which has exponential growth? Does a group with exponential growth always have a hyperbolic subgroup which has exponential growth?

There is a heuristic theorem.
When the group has a hyperbolic subgroup, by Tits' Alternative theorem, the subgroup if doesn't contain degree 2 free group then it is virtually solvable.

Exponential growth and hyperbolicity have overlap to some extent.

I wonder to what extent can this question be answered.

Polycyclic groups that are not virtually nilpotent, such as $\langle x,y,z \mid xy=yz, x^y=z, z^y=yz \rangle$ have exponential growth, but they have no non-elementary hyperbolic subgroups (i.e. all of their hyperbolic subgroups are virtually cyclic).

I totally agree with what Derek said. I think it is a good answer which helps me understand better polynomial growth. The first example I learn in geometric group theorem which is polycyclic but not nilpotent is $Z^2 \rtimes  _ {\varphi}Z$ where ${\varphi}$ is an isomorphism of ${Z}^2$ that has an eigenvalue bigger than 1.


Successive squaring with big exponent I would like to calculate $ 2^{5^{77}}\bmod 113 $.
I solved similar problems but with smaller exponent e.g. $ 2^{185}\bmod 113 $ with successive squaring method. Is there any way to use this method to solve it?

Rather than successive squaring, try successive raising to the $5^{th}$ power:

$2^{5^0}\equiv2\bmod 113$

$2^{5^1}\equiv32\bmod113$

$2^{5^2}\equiv32^5\equiv99\bmod113$

$2^{5^3}\equiv99^5\equiv56\bmod113$

$2^{5^4}\equiv56^5\equiv60\bmod113$

$2^{5^5}\equiv60^5\equiv105\bmod113$

$2^{5^6}\equiv105^5\equiv\color{red}2\bmod113$.

Can you take it from here?   $\;$  Note that $77\equiv5\bmod6$.

You can reduce the exponent by Lil Fermat.  You need $5^{77}\bmod{112}$.

Now by Euler's theorem, since $\varphi(112)=48$, we $5^{48}\cong1\bmod{112}$.  So $5^{77}\cong5^{29}\bmod{112}$ and we can proceed with successive squaring.

$5^3\cong13\bmod{112}\implies5^6\cong57\bmod{112}\implies5^{12}\cong1\bmod{112}\implies5^{24}\cong1\bmod{112}\implies5^{29}\cong5^5\bmod{112}\implies5^{29}\cong-11\bmod{112}\implies5^{29}\cong101\bmod{112}$.

So $2^{5^{77}}\cong2^{101}\bmod{113}$.

Now we do more successive squaring and the like: $2^{10}\cong7\bmod{113}\implies2^{20}\cong49\bmod{113}\implies2^{30}\cong{4}\bmod{113}\implies2^{60}\cong16\bmod{113}\implies2^{90}\cong64\bmod{113}\implies2^{100}\cong-4\bmod{113}\implies2^{101}\cong-8\bmod{113}$.

Thus $2^{5^{77}}\cong105\bmod{113}$.


Abstract algebra: Proving the matrix is a subgroup I'm confusing about this specific problem:

Here, $\Gamma$ is a group of 2x2 - matrices with integer entries, with respect to the usual matrix multiplication, and $det(\Gamma) = 1$.

But will the identity $I = \begin{bmatrix}1&0\\0&1\end{bmatrix}$ fail to prove when $n = 1$ and therefore, $I \not\in \Gamma_n$ ? (Because $1 \equiv 0 \pmod{1}$)

Please, correct me if I'm mistaken.

The excerpt explains for you that $\Gamma_2 $ will be the matrices with main diagonal entries odd and minor diagonal entries even.  ( This is another way of saying $a\equiv d\equiv1\pmod2$ and $b\equiv c\equiv 0\pmod2$).

Thus the identity,  $I=\begin{pmatrix} 1&0\\0&1\end{pmatrix}$ is an element of $\Gamma_2 $.

My problem is I was mistaken about the "congruence": $1 \equiv 1 \pmod{1}$. They are both in the same equivalence class for 0.


What do $\pi$ and $e$ stand for in the normal distribution formula? I'm a beginner in mathematics and there is one thing that I've been wondering about recently. The formula for the normal distribution is:

$$f(x)=\frac{1}{\sqrt{2\pi\sigma^2}}e^{-\displaystyle{\frac{(x-\mu)^2}{2\sigma^2}}},$$

However, what are $e$ and $\pi$ doing there? $\pi$ is about circles and the ratio to its diameter, for example. $e$ is mostly about exponential functions, specifically about the fact that $\frac{\mathrm{d}}{\mathrm{d}x} e^x = e^x$.

It is my firm conviction that proofs and articles are available, but could someone perhaps  shed some light on this and please explain in a more 'informal' language what they stand for here?

I'm very curious to know as those numbers have very different meanings as far as I'm concerned.

So I think you want to know "why" $\pi$ and $e$ appear here based on an explanation that goes back to circles and natural logarithms, which are the usual contexts in which one first sees these.

If you see $\pi$, you think there's a circle hidden somewhere. And in fact there is. As has been pointed out, in order for this expression to give a probability density you need $\int_{-\infty}^\infty f(x) \: dx = 1$. (I'm not sure how much you know about integrals -- this just means that the area between the graph of $f(x)$ and the $x$-axis is 1.) But it turns out that this can be derived from $\int_{-\infty}^\infty e^{-x^2} dx = \sqrt{\pi}$.

And it turns out that this is true because the square of this integral is $\pi$. Now, why should the square of this integral have anything to do with circles? Because it's the total volume between the graph of $e^{-(x^2+y^2)}$ (as a function $g(x,y)$ of two variables) and the $xy$-plane.  And of course $x^2+y^2$ is just the square of the distance of $(x,y)$ from the origin -- so the volume I just mentioned is rotationally symmetric. (If you know about multiple integration, see the Wikipedia article "Gaussian integral", under the heading "brief proof" to see this volume worked out.)

As for where $e$ comes from -- perhaps you've seen that the normal probability density can be used to approximate the binomial distribution. In particular, the probability that if we flip $n$ independent coins, each of which has probability $p$ of coming up heads, we'll get $k$ heads is
$$ {n \choose k} p^{k} (1-p)^{n-k} $$
where ${n \choose k} = n!/(k! (n-k)!)$. And then there's
Stirling's approximation,
$$ n! \approx \sqrt{2\pi n} (n/e)^{n}. $$
So if you can see why $e$ appears here, you see why it appears in the normal. Now, we can take logs of both sides of $n! = 1 \cdot 2 \cdot \ldots \cdot n$ to get
$$ \log (n!) = \log 1 + \log 2 + \cdots + \log n $$
and we can approximate the sum by an integral,
$$ \log (n!) \approx \int_{1}^{n} \log t \: dt. $$
But the indefinite integral here is $t \log t - t$,  and so we get the definite integral
$$ \log (n!) \approx n \log n - n. $$
Exponentiating both sides gives $n! \approx (n/e)^n$. This is off by a factor of $\sqrt{2\pi n}$ but at least explains the appearance of $e$ -- because there are logarithms in the derivation. This often occurs when we deal with probabilities involving lots of events because we have to find products of many terms; we have a well-developed theory for sums of very large numbers of terms (basically, integration) which we can plug into by taking logs.


Why is $\sup_{x∈[0,1]} {|p'(x)|} ≤ A_d\sup_{x∈[0,1]}{|p(x)|}$ for all polynomials $p$ of degree at most $d$? How can one prove that for any positive integer $d$, there is a constant $A_d < 0$ such that
$$
\sup_{x∈[0,1]}
{\lvert\, p'(x)\rvert} ≤ A_d\sup_{x∈[0,1]}{\lvert\, p(x)\rvert},
$$
for all polynomials $p$ of degree at most $d$?

This is equivalent of saying that the differential operator is continuous, which is clear, since the vector space of polynomials of degree at most $d$ is finite-dimensional.

To see a proof that makes this inequality precise, stating that $A_d \leq d^2$, look up Markov's inequality.


if $k$ is a positive integer and $G$ a finite group such that $G=\{x^k:x\in G\}$ , then is it true that g.c.d.$(|G|,k)=1$ ? If $G$ is a finite group of order $n$ and $k$ is a positive integer such that g.c.d.$(n,k)=1$ , then I know that $G=\{x^k:x\in G\}$ ; is the converse true ? that is if $k$ is a positive integer and $G$ is a finite

group such that $G=\{x^k:x\in G\}$  , then is it true that g.c.d.$(|G|,k)=1$ ?

I have a feeling that the converse is true . Say g.c..d$(|G|,k)=d>1$ , then there is a prime $p|d$ , then there is an element $g$ of $G$ of order $p$ , but I don't know what else to do . Please help.

The map $x \to x^k$ is surjective iff the map $x \to x^k$ is injective (because $G$ is finite).

In particular, this property implies that $x^k=1 \Rightarrow x=1$. If $gcd(|G|,k) \neq 1$, there is a prime $p$ dividing $k$ and an element $x$ of order $p$. But then $x^k=1 \Rightarrow x=1$, a contradiction.

Let's denote $G^k:=\{x^k:x\in G\}$. There is a $p$ such that $(|G|, k) = d$ and $p | d$. Using Cauchy theorem there is an element $g \in G$ of order $p$.
$|G| = n = p^sm$ and $(m, p) = 1$. Then $H = G^m \neq \{1\}$ because $g^m \neq 1$.
$\{1\} = G^n = G^{m \cdot p^s} = G^{m \cdot d^s} = ((G^{d})^{d^{s-1}})^m = (G^{d^{s-1}})^m = \dots=G^m \neq \{1\}$.


Fritz John condition Consider the following problem :

$$\min x+y^2$$
$$\text{s.t.}~~x^2-4x+4 \leq 0 $$

The question is : Find all the Fritz-Jons points for this problem.$$$$
Solution : let $f(x,y)=x+y^2$ and $g(x,y)=x^2-4x+4$ we can observe that g is differentiable and continuous at $(\bar x, \bar y)$. And let $(\bar x, \bar y)$ be a feasible solution
\begin{align}
\nabla f(\bar x,\bar y)&=(1,2 \bar y)^T \cr
 \nabla g(\bar x,\bar y)&=(2 \bar x-4,0)^T
\end{align}
Therefore, If $\bar x$ solves the above problem locally, then there exists $\lambda_1,\lambda_2 \in \mathcal{R}$ such that :
$$ \lambda_1(1,2 \bar y)^T+\lambda_2(2 \bar x-4,0)^T=0\Leftrightarrow
\begin{cases}\lambda_1+\lambda_2(2 \bar x-4)=0 \cr
\lambda_12\bar y =0 \end{cases}$$

I'm stuck here

Let $$f(x,y)=x+y^2$$ and $$\frac{\partial f(x,y)}{\partial x}=1$$ so we have to search the extrema on the curve $$x^2-4x+4=(x-2)^2=0$$ and this is $x=2$


General Solution of second order differential equation ${\frac {d^2y}{dx^2}}+{\frac {dy}{dx}} = x^2$ ${\frac {d^2y}{dx^2}}+{\frac {dy}{dx}} = x^2$

I'm not sure how to solve it, in textbook solution for this problem is

$y = \frac13x^3 - x^2 + 2x +c_1+c_2e^{-x}$

A simpler solution would be $v=y'$ and then it becomes $v'+v=x^2$ which has an integrating factor of $e^x$ which makes it $\left (ve^x\right )'=x^2e^x$ and integrating both sides $ve^x=e^x(x^2-2x+2)+C_1$ and then we get $v=y'=x^2-2x+2+C_1e^{-x}$ $$\boxed{y=\frac{1}{3}x^3-x^2+2x+C_1e^{-x}+C_2}$$ I didn't really understand the whole kernel thing from the previous answer. I apologize to the severe incorrectness of my last answer.

Integrate once to get $$\frac{dy}{dx} + y = \frac{1}{3}x^3 + c_1.$$ Formally this is $$(D+I)y = \frac{1}{3}x^3 + c_1$$ with the derivative $D$. Since $(I+D)(I - D + D^2 - D^3) = I - D^4$ acts as $I$ on polynomials of degree $3$ it follows that \begin{align*} y &= (I-D+D^2-D^3) \Big( \frac{1}{3}x^3 + c_1 \Big) + \mathrm{Ker}(D+I) \\ &= \frac{1}{3}x^3 - x^2 + 2x - 2 + c_1 + \mathrm{Ker}(D+I) \\ &= \frac{1}{3}x^3 - x^2 + 2x + c_1 + c_2 e^{-x} \end{align*} since the kernel of $D+I$ is $\{f: f' + f = 0\} = \{c_2 e^{-x}: \, c_2 \in \mathbb{R}\}.$


Let $A,M,$ and $C$ be nonnegative integers such that $A+M+C=10$. What is the maximum value of $AMC+AM+MC+CA$? In 2000 AMC 10

  Let $A,M,$ and $C$ be nonnegative integers such that $A+M+C=10$. What is the maximum value of $AMC+AM+MC+CA$?

My attempt,

$(A+1)(M+1)(C+1)=AMC+AM+AC+A+MC+M+C+1$

$=(AMC+AM+AC+MC)+11$

$AMC+AM+MC+CA=(A+1)(M+1)(C+1)-11$

I stuck at here. I went online and search for the solution in here 2000 AMC Problem, but I don't really understand for it. Hope someone can explain it for me. Thanks in advance.

You can end your solution:

By AM-GM $$AMC+AM+AC+MC=(A+1)(M+1)(C+1)-11\leq$$
$$\leq\left(\frac{3+A+M+C}{3}\right)^3-11=70.3....$$
The equality does not occur because $\{A,M,C\}\subset\mathbb N\cup\{0\}$.

Thus, $(A+1)(M+1)(C+1)\leq81$.

Let $a=A+1$, $b=M+1$ and $c=C+1$.

Hence, $a+b+c=13$ and $\{a,b,c\}\subset\mathbb N$.

We see that $abc=81$ is impossible (if $abc=81$ then $a$, $b$ and $c$ divided by $3$, which is impossible) and $abc=80$ occurs for $a=b=4$ and $b=5$.

Thus, the answer is $69$.

AMC+AM+MC+CA=(A+1)(M+1)(C+1)-11
(this is a little discovery I made)
The product or sum of any sequence of numbers is at its greatest when the numbers are more equal to each other. Sort of like you know that $(A+1)(M+1)(C+1)$ has to equal something but at the same time, $A+M+C=10$. What is the sum of 3 numbers that's equal to 10 and yet the value is closest to each other? After a few attempts, we conclude that 4,4,2 is the set. Thus,
$(4+1)(4+1)(2+1)-11 is AMC+AM+MC+CA$ 's value at its greatest.


Product and Square Root Proof Let $a_1$ and $a_2$ be positive integers and let $m = a_1 a_2$.

Prove that at least one of $a_1$ or $a_2$ is at least $\sqrt m$.

Disclosure:

This is for a homework question, though the question is using the product of three numbers and the cubed root. I am looking more for some direction on solving this then an answer, I am hoping by better understanding how this would work with the product of two numbers I can work out doing this with three.

If neither is at least $\sqrt{m}$, then both are less than $\sqrt{m}$.  If both $a_1$ and $a_2$ are less than $\sqrt{m}$, what does that say about $a_1 a_2$?

(In just the same way, but with the obvious simple changes, you could show that at least one of the two must be less than or equal to $\sqrt{m}$.)

$m$ can be thought of as product of two numbers $d\sqrt m$ and $\frac{\sqrt{m}}{d}$,
where $d\geq0$. So in this way one number has to be greater than or equal to $\sqrt m$ and the other has to be less than or equal to it.


If $X$ is a compact space and $A:X\rightarrow X$ is such that $\rho(Ax,Ay)<\rho(x,y)$, $x\neq y, \Rightarrow A $ have only one fix point on X. I have problems with this demostration can anybody help me please?
If $X$ is a compact space and $A:X\rightarrow X$ is such that $\rho(Ax,Ay)<\rho(x,y)$, $x\neq y,  \Rightarrow A $ have only one fix point on X.

Um, if x and y are two unequal fixed points then $\rho(Ax,Ay)= \rho(x,y)$.

So there can't be more than one fixed point.

Under the lack of the compactness argument you can not assure that the infimum of the function $f(x)=\rho(Ax,x)$ equals zero so that the solution of the equation $Ax=x$ is unique.

In particular, on the metric space endowed by the interval $X=(0,1)$ and the Euclidean metric $\rho(x,y)=|x-y|$, the family of linear functions $Ax=ax$ $(0\leq a<1)$ has no fixed points.

Recall that the compactness argument is not a necessary condition to assure that a function has a unique fixed point: on the metric space $X=(-\frac{1}{2},\frac{1}{2})$, the quadratic function $Ax=x^2$ has a unique fixed point ($x=0$) and at the same time satisfies the condition $|Ax-Ay|<|x-y|$.


The sequence whose limit of difference is zero Let $(x_n)$ be a sequence in $\mathbb{R}^d$ such that

$$\lim_{n\rightarrow\infty} x_{n+1}-x_n = 0$$

First question: what is the name of such sequence and general properties?

Let $F$ be the set of all adherent values of this sequence. I need to find an example such that F is not connected. How can I think about this question?

Suppose $x_n$ is the partial sum of the harmonic series.
$|x_{n+1} - x_n| = \frac{1}{n+1}$
and $\lim_\limits{n\to\infty} |x_{n+1}-x_n| = 0$, However, $\lim_\limits{n\to\infty} x_n = \infty$


Radical equation - can I square both sides with more than 1 radical on one side? I'm familiar with equations like:

$\sqrt{x+1} - \sqrt{x+2} = 0 $

Has no solutions, it's just an example off the top of my head

Just move the negative square root to the other side, square both sides and solve.

$\sqrt{x+1} = \sqrt{x+2}$

$x+1 = x+2$

0 = 1

My question is, if there are two square roots on one side, then can I still square both sides in this way:

$\sqrt{x+1} - \sqrt{x+2} = \sqrt{x+3}$

$x+1 - (x+2) = x+3$

$x+1 - (x-2) = x+3$

$x = -4$

Or does squaring both sides cause something strange to happen on the left hand side?

No, what you did was wrong.
this is because :

$\sqrt{x+1} - \sqrt{x+2} = \sqrt{x+3}$ does not imply $(x+1)-(x+2)=x+3$.

You need to square both sides, which means:

$(\sqrt{x+1} - \sqrt{x+2})^2=x+3$

$(x+1)+(x+2)-2\sqrt{(x+1)(x+2)}=x+3$.

As a sidenote, you can plug x=-4 into the original equation to check whether x=-4 is not a solution.

How I explain it to myself is negative if you want to multiply both sides of the equation by the same number, say 3, you can multiply-across through the pluses and minuses by 3, or take it in stages by putting a bracket around both sides, but the 3 at the start of the brackets on both sides and then multiply across in through the brackets(effectively inflating both sides by the same amount)... but you can’t square across, you need to square both sides, and I find using Brackets here are always a big help.
And if you’ve got say, two square roots (radicals) added together (or subtracted) on one side then it’s an easier calculation to slide one over to the other side, change the plus to a minus , and vice versa, and then square both sides eg $\sqrt{2x-1} + \sqrt{x-1} = 5$   next step $\sqrt{2x-1} = 5 – \sqrt{x-1}$


An identity involving binomial coefficients Prove the following identity
$$\displaystyle \sum_{i+j=m}\frac{(n-1) \binom{ai+n-1}{i} \binom{aj+1}{j}}{(ai+n-1)(aj+1)} =  \frac{n\binom{am+n}{m}}{am+n}$$
where $i = 0,1,\cdots,m$ and $m, n$ are positive integers and $a$ is a positive integer or even a fraction.

One complete proof can be found in that famous book "Concrete Mathematics" by
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik  which is widely used as a textbook in many computer science departments.

Another complete proof can be found in the book written by Egorychev which is directly using the inversion rule of residue, see page 49 in the book "Integral representation and the computation of combinatorial sums". If you are reading that book, keep in mind that the index under $\sum$ can be extended to infinity because the contour integral has no pole when $k>n$.

This is a nice example to apply the inversion rule of formal power series stated as rule 4 in G.P. Egorychevs Integral Representations  and the Computation of Combinatorial Sums section 1.2.2.

I think it's worthwhile to present a complete proof. Here we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a formal power series. We show

  The following is valid for $m,n\geq 1$ and $a\in\mathbb{R}$ appropriate
  \begin{align*}
\sum_{{i+j=m}\atop{i,j\geq 0}}&\frac{n-1}{ai+n-1}\binom{ai+n-1}{i}\frac{1}{aj+1}\binom{aj+1}{j}
=\frac{n}{am+n}\binom{am+n}{m}
\end{align*}

$$ $$

  We obtain
  \begin{align*}
\sum_{{i+j=m}\atop{i,j\geq 0}}&\frac{n-1}{ai+n-1}\binom{ai+n-1}{i}\frac{1}{aj+1}\binom{aj+1}{j}\\
&=\sum_{i=0}^m\frac{n-1}{ai+n-1}\binom{ai+n-1}{i}\frac{1}{am-ai+1}\binom{am-ai+1}{m-i}\\
&=\sum_{i=0}^\infty\left\{\binom{ai+n-1}{i}-a\binom{ai+n-2}{i-1}\right\}\\
&\qquad\qquad\cdot\left\{\binom{am-ai+1}{m-i}-a\binom{am-ai}{m-i-1}\right\}\tag{1}\\
&=\sum_{i=0}^{\infty}\left([z^i](1+z)^{ai+n-1}-a[z^{i-1}](1+z)^{ai+n-2}\right)\\
&\qquad\qquad\cdot\left([w^{m-i}](1+w)^{a(m-i)+1}-a[w^{m-i-1}](1+w)^{a(m-i)}\right)\\
&=[w^m](1+w)^{am}(1+w-aw)\\
&\qquad\qquad\cdot\sum_{i=0}^{\infty}\left(\frac{w}{(1+w)^a}\right)^i[z^i](1+z)^{n-2}(1+z-az)(1+z)^{ai}\tag{2}\\
&=[w^m](1+w)^{am}(1+w-aw)\left.\left((1+z)^{n-1}\right)\right|_{z=w}\tag{3}\\
&=[w^m](1+w)^{am+n}-a[w^{m-1}](1+w)^{am+n-1}\\
&=\binom{am+n}{m}-a\binom{am+n-1}{m-1}\\
&=\frac{n}{am+n}\binom{am+n}{m}
\end{align*}
  and the claim follows.

Comment:

In (1) we use the identity $$\frac{q}{pk+q}\binom{pk+q}{k}=\binom{pk+q}{k}-p\binom{pk+q-1}{k-1}$$ We also set the upper limit of the sum to $\infty$ without changing anything since we are only adding zero.
In (2) we rearrange the sum, use the linearity of the coefficient of operator and the rule $[z^{n-k}]A(z)=[z^n]z^kA(z)$.
In (3) we use the inversion rule

\begin{align*}
\sum_{i=0}^\infty w^i [z^i]A(z)f^i(z)=\left.\left(A(z)\frac{f(z)}{f(z)-zf^{\prime}(z)}\right)\right|_{z=g(w)}
\end{align*}
with $g(w)$ the inverse of $w=\frac{z}{g(z)}$. We get from (2)
\begin{align*}
A(z)&=(1+z)^{n-2}(1+z-az)\\
f(z)&=(1+z)^a
\end{align*}
and obtain
\begin{align*}
A(z)\frac{f(z)}{f(z)-zf^{\prime}(z)}&=(1+z)^{n-2}(1+z-az)\frac{(1+z)^a}{(1+z)^a-az(a+z)^{a-1}}\\
&=(1+z)^{n-1}
\end{align*}
Since $w=\frac{z}{f(z)}=\frac{z}{(1+z)^a}$ we apply in (3) the substitution $z=w$.

Follow the same reasoning when proving this identity,
$$\displaystyle \sum_{i=0}^m\frac{q }{pi+q}\binom{pi+q}{i} \binom{pm-pi}{m-i} = \binom{mp+q}{m}$$
You can just read the book yourself. Too difficult to post the book here!

it can be proved using the inversion rule of residue, see page 49 Integral representation and the computation of combinatorial sums


Using integrating factor I have the following differential equation

$$\frac{dN(t)}{dt} = A - \mu N(t)$$

I understand that I will need to use an integrating factor but am not sure how to proceed. I think I should use $e^{-\mu t}$ as the integrating factor but am not entirely sure.

I believe I should end up with

$$N(t)=N_{0}e^{-\mu t}+\frac{A}{\mu}(1-e^{-\mu t})$$ where $N(0)=N_{0}$ is the initial condition.

Any help would be much appreciated!

You have $N'(t)+\mu N(t)=A$. Multiply by $e^{\mu t}$ to get $$(N(t)e^{\mu t})'=Ae^{\mu t}$$

Why not just separate the variables?

We have $$\frac{dN}{dt}=A-\mu N \iff\int\frac{1}{A-\mu N}dN=\int dt$$
$$\iff \int_{N_0}^{N}\frac{1}{A-\mu \nu}d\nu=\int_0^td\tau$$
$$\iff-\frac{1}{\mu}\bigg[\ln|A-\mu\nu|\bigg]_{N_0}^{N}=\bigg[\tau\bigg]_0^t$$
$$\iff-\frac{1}{\mu} \ln\left| \frac{A-\mu N}{A-\mu N_0}\right|=t \iff \frac{A-\mu N}{A-\mu N_0}=e^{-\mu t}$$
$$\iff \mu N=A-(A-\mu N_0)e^{-\mu t}$$

$$\iff \boxed{N(t)=\frac{A-(A-\mu N_0 ) e^{-\mu t}}{\mu}}$$


How does one prove that if function's partial derivative respect to every variable is zero, function is constant? How does one prove that if function's partial derivative respect to every variable that the function defines over is zero function is constant function? I just noticed it, but I cannot prove it.

Suppose the function $f(x,y)$ is non-constant and its partial derivatives exist everywhere. Then we have some $(x,y)$ and $(x',y')$ such that $f(x,y)\ne f(x',y')$. If $f(x,y)=f(x',y)=f(x,y')$ then these are distinct from $f(x',y')$, otherwise one of $f(x',y)$ or $f(x,y')$ is not $f(x,y)$. This means we only have to worry about one of the two variables! Lets say $f(x,y)\ne f(x',y)$ (the other cases are identical). By the Mean Value Theorem, we have some $c\in (x,x')$ such that
$$\frac{\partial f}{\partial x}(c,y)=\frac{f(x',y)-f(x,y)}{x'-x}\ne 0$$
thus the partial derivatives are not everywhere $0$.

You should be able to extend this to arbitrarily many variables on your own.

Let $f(x_1,x_2,...,x_n)$ be a function such that $\frac{\partial f}{\partial x_i}=0\,\forall i=1,2,\dots,n$.

Because $\frac{\partial f}{\partial x_1}=0$, the function does not depend on $x_1$

Because $\frac{\partial f}{\partial x_2}=0$, the function does not depend on $x_2$ either.

Continuing this, we come to conclusion that the function does not depend on any of the variables, and hence it is a constant.


$f(0) = 1$ and $f(1) = 0$ Show there exists $c$ in $(0, 1)$ such that $f(c) = kc$. Let $f$ be continuous on $[0, 1]$ and differentiable on $(0, 1)$ such that $f(0) = 1$ and $f(1) = 0$ and
let $k$ be a positive constant.

Show that there exists $c$ in $(0, 1)$ such that $f(c) = kc$.

I understand I need to substitute $f$ by another function $g$ and apply Intermediate Value Theorem, but I am clueless how to transform $f$. Any kind soul please help!

Consider $g(x)=f(x)-kx$. Note that $g(0)=1>0$ and $g(1)=-k<0$. Then apply Intermediate Value Theorem.

Define $g(x)=f(x)-kx$ . Then, $g(0)=1$ and $g(1)=-k$. Then apply Intermediate Value Property for $g$ there exists $c \in (0,1)$ such that $g(c)=0$. That is $f(c)=kc$


Advanced complex numbers/roots of unity Let $a, b, c, d$ be real numbers, none of which are equal to $-1$, and let $\omega$ be a complex number such that $\omega^3 = 1$ and $\omega \neq 1.$ Given that,
$$\frac{1}{a + \omega} + \frac{1}{b + \omega} + \frac{1}{c + \omega} + \frac{1}{d + \omega} = \frac{2}{\omega}$$
How can I determine the expression:
$$\frac{1}{a + 1} + \frac{1}{b + 1} + \frac{1}{c +1} + \frac{1}{d + 1}$$.
I have tried clearing the denominators of the first equation, but that just results in a large mess. I don't know how to continue from there.

A calculation by foot. We obtain from
\begin{align*}
\color{blue}{0}&\color{blue}{=\frac{1}{a+\omega}+\frac{1}{b+\omega}
+\frac{1}{c+\omega}+\frac{1}{d+\omega}-\frac{2}{\omega}}\tag{1}\\
\end{align*}
by multiplication with the common denominator $(a+\omega)(b+\omega)(c+\omega)(d+\omega)\omega$:
\begin{align*}
\color{blue}{0}&=(b+\omega)(c+\omega)(d+\omega)\omega\\
&\qquad+(a+\omega)(c+\omega)(d+\omega)\omega\\
&\qquad+(a+\omega)(b+\omega)(d+\omega)\omega\\
&\qquad+(a+\omega)(b+\omega)(c+\omega)\omega\\
&\qquad-2(a+\omega)(b+\omega)(c+\omega)(d+\omega)\\
&=bcd\omega+(bc+bd+cd)\omega^2+(b+c+d)\omega^3+\omega^4\\
&\qquad+acd\omega+(ac+ad+cd)\omega^2+(a+c+d)\omega^3+\omega^4\\
&\qquad+abd\omega+(ab+ad+bd)\omega^2+(a+b+d)\omega^3+\omega^4\\
&\qquad+abc\omega+(ab+ac+bc)\omega^2+(a+b+c)\omega^3+\omega^4\\
&\qquad-2abcd\\
&\qquad-2(abc+abd+acd+bcd)\omega\\
&\qquad-2(ab+ac+ad+bc+bd+cd)\omega^2\\
&\qquad-2(a+b+c+d)\omega^3\\
&\qquad-2\omega^4\\
&\,\,\color{blue}{=\left(2-(abc+abd+acd+bcd)\right)\omega-2abcd+a+b+c+d}\tag{2}
\end{align*}
In the last step (2) we observe that terms with $\omega^2$ cancel away and we also use the identities
\begin{align*}
\omega^3=1,\quad\omega^4=\omega
\end{align*}

We note from (1) and (2) we can write (1) as
\begin{align*}
\color{blue}{0=\frac{A\omega+B}{(a+\omega)(b+\omega)(c+\omega)(d+\omega)\omega}}\tag{3}
\end{align*}
and since $A,B\in\mathbb{R}$ and $\omega\in\mathbb{C}\setminus{\mathbb{R}}$ we conclude $A=B=0$, so that
\begin{align*}
\color{blue}{abc+abd+acd+bcd}&\color{blue}{=2}\tag{4}\\
\color{blue}{a+b+c+d}&\color{blue}{=2abcd}\\
\end{align*}
follows.

On the other hand we consider the expression
\begin{align*}
\color{blue}{\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}+\frac{1}{d+1}}&\color{blue}{=z}
\end{align*}
Multiplication of the LHS with the common denominator $(1+a)(1+b)(1+c)(1+c)$ gives

\begin{align*}
&(b+1)(c+1)(c+1)+(a+1)(c+1)(d+1)\\
&\qquad\quad+(a+1)(b+1)(d+1)+(a+1)(b+1)(c+1)\\
&\quad=1+(b+c+d)+(bc+bd+cd)+bcd\\
&\qquad\quad+1+(a+c+d)+(ac+ad+cd)+acd\\
&\qquad\quad+1+(a+b+d)+(ab+ad+bd)+abd\\
&\qquad\quad+1+(a+b+c)+(ab+ac+bc)+abc\\
&\quad=4+3(a+b+c+d)\\
&\qquad\quad+2(ab+ac+ad+bc+bd+cd)\\
&\qquad\quad+abc+abd+acd+bcd\\
&\,\,\color{blue}{=2\left(3+3abcd+ab+ac+ad+bc+bd+cd\right)}\tag{5}
\end{align*}
In the last line (5) we used the identities from (4).

Similarly, multiplication of the RHS with the common denominator gives

\begin{align*}
&z(a+1)(b+1)(c+1)(d+1)\\
&\qquad=z(1+(a+b+c+d)\\
&\qquad\quad+(ab+ac+ad+bc+bd+cd)\\
&\qquad\quad+(abc+abd+acd+bcd)+abcd)\\
&\,\,\color{blue}{\qquad=z(3+3abcd+ab+ac+ad+bc+bd+cd)}\tag{6}
\end{align*}
Again in the last line (6) we used the identities from (4) for simplification.

Comparing (5) and (6) we conclude
\begin{align*}
\color{blue}{\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}+\frac{1}{d+1}=2}
\end{align*}

The keys is Vieta's formulas.
Let $u$ be a root of $x^3 = 1 $. Then $u+a$ is a root of $(x-a)^3 = 1$ and $\frac{1}{u+a}$ is a root of $(\frac{1}{x}-a)^3=1 $. Multiplying by $x^3$ and expanding the coefficients we have
$$(1+a^3) x^3 -3a^2x^2 + 3ax - 1 = 0$$
Using  Vieta's formulas  we get that $\frac{3a^2}{1+a^3}$ is equal to
$$ \frac{3a^2}{1+a^3} = \sum_{u^3 =1} \frac{1}{(u+a)} \tag{1} $$
We can apply this to our equation. We know that
$$\frac{1}{a + \omega} + \frac{1}{b + \omega} + \frac{1}{c + \omega} + \frac{1}{d + \omega} = \frac{2}{\omega}$$ and by conjugating: $$\frac{1}{a + \overline{\omega}} + \frac{1}{b +\overline{\omega}} + \frac{1}{c +\overline{\omega}} + \frac{1}{d + \overline{\omega}} = \frac{2}{\overline{\omega}}$$
Now $\omega$ and $\overline{\omega}$ are two of the three roots of unity (solutions to $x^3 = 1$), the other being $1$. From this we conclude:
$$\frac{1}{a + 1} + \frac{1}{b + 1} + \frac{1}{c +1} + \frac{1}{d + 1} = \\ = \frac{3a^2}{1+a^3} + \frac{3b^2}{1+b^3} + \frac{3c^2}{1+c^3}  + \frac{3d^2}{1+d^3}  - (\frac{2}{\omega}+\frac{2}{\overline{\omega}}) =\\= 2 + (\frac{3a^2}{1+a^3} + \frac{3b^2}{1+b^3} + \frac{3c^2}{1+c^3}  + \frac{3d^2}{1+d^3})    $$


Describe the maximal integral submanifolds of a distribution spanned by the following vector fields My question:

Describe the maximal integral submanifolds  of a distribution spanned by the vector fields $$X=y \frac{\partial}{\partial z} - z \frac{\partial}{\partial y}, \ \ \ \ \ \ \ \ \ Y=z\frac{\partial}{\partial x}-x\frac{\partial}{\partial z}$$

My Attempt:

I am not sure how to go about trying to solve this problem.

Some background:

A submanifold $(M,\psi)$ of $N$ is an integral submanifold of a distribution $\mathcal{D}$ on $N$ if $$d\psi(M_m)=\mathcal{D}(\psi(m))$$ for each $m \in M$.

A maximal integral manifold $(M,\psi)$ of a distribution $\mathcal{D}$ on a manifold $N$ is a connected integral manifold of $\mathcal{D}$ whose image in $N$ is not a proper subset of any other connected integral manifold of $\mathcal{D}$

Hint: Solve the differentiable equations

$(d/dt x,d/dt y,d/dt z) =(0,-z,y)$. You have:

$x$ is a constant, ${{d^2}\over{dt}}y =-y$ ${{d^2}\over{dt}}z =-z$, thus the flow is $(x_0,acost+bsint,a'cost+b'sint)$.

The other flow is also of the form $(ucost+vsint,y_0,u'cost+v'sint)$ so the maximal integral amifolds are the torus $T^2$.

You have to be more careful. While calculating the flows is the first step, its helpful to also constrain the flows using a boundary condition (like the starting point). This way, while the solution looks like a torus, if you find the magnitude of the flow you'll find that its a different manifold (decidedly not $T^{2}$)


Proof that propositional logic remains consistent after the addition of a single axiom I was wondering if someone might be able to supply a hint for the following exercise:

Let $\mathcal{P}'$ be the system obtained from $\mathcal{P}$ by adding the single wff $[p \to q]$ to the axioms of $\mathcal{P}$. Show that $\mathcal{P}'$ is consistent.

The axiom schemes of $\mathcal{P}$ are

$[[A \lor A] \to A]$

$[A \to [B \lor A]]$

$[[A \to B] \to [[C \lor A] \to [B \lor C]]]$

Modus Ponens is the only primitive rule of inference.

I have been unsuccessfully trying to prove that a contradiction can not be a theorem of $\mathcal{P}'$.

Ref to : Peter Andrews, An Introduction to Mathematical Logic and Type Theory, page 35.

Assueme that $\mathcal P' = \mathcal P \cup \{ p \to q \}$ is inconsistent.

By definition, this means that $\mathcal P'$ proves every formula.

Thus, also : $\mathcal P' \vdash \lnot (p \to q)$ and, by Deduction Theorem [see 1116, page 30] :

  $\mathcal P \vdash (p \to q) \to \lnot (p \to q)$.

But we have that $(p \to q) \to \lnot (p \to q)$ is not a tautology [check with the truth assignment $\varphi : \text {Var} \to \{ \text T, \text F \}$ such that : $\varphi(p)= \text F$ and $\varphi(q)= \text T$].

Thus, we have a contradiction with the Soundness Theorem for $\mathcal P$ [see 1200]: Every theorem of $\mathcal P$ is a tautology.

It suffices to show that there is a model of $\mathcal P$ where $p\to q$ is true.

As $\mathcal P$ is consistent, let $M$ be a model of $\mathcal P$. If $M$ says that $q$ is true or that $p$ is false, we are done. Otherwise (i.e., if it says $q$ is false and $p$ is true), swap $p$ and $q$, i.e., let $M'$ be such that it's truth value for a wff is the truth value $M$ assigns to the same wff wit $p,q$ exchanged. Then $M'$ is still a model of $\mathcal P$, and here $p\to q$ is true.


Can the rank of a module be equal to zero? I try to understand a proof from one of my lectures.

Let $\mathcal{O}_K$ be the ring of integers over a field $K$ and $0 \neq \mathfrak{a} \subseteq \mathcal{O}_K$ an ideal.

I know that $\mathcal{O}_K$ is a free $\mathbb{Z}$-module of rank $r := [\mathcal{O}_K : \mathbb{Q}]$. Hence $rank(\mathfrak{a}) \leq r$ as a free $\mathbb{Z}$-module. On the other side $\mathfrak{a}\mathcal{O}$ is a free $\mathbb{Z}$-module of rank $r$. So in total $rank(\mathfrak{a}) = r$.

Let's observe $rank(\mathcal{O_K}/\mathfrak{a})$. My notes states that this rank is zero, hence $\mathcal{O_K}/\mathfrak{a}$ is finitely generated, but for me this doesn't make any sense. By my definition of rank (counting the number of basis elements), the smallest rank possible is 1, isn't it? Is my definition of rank wrong?

What am I missing here?

Beyond the fact that the zero-module indeed has rank $0$, it is relevant to note that not every module has a basis and thus one needs to be a bit carefull what the rank should be.

Let us take a basic example with $K$ equal to the rationals, then the ring of integers is just the integers $\mathbb{Z}$. Now for some ideal of the integers, say the one generated by $5$, we have that $5 \mathbb{Z}$ has rank $1$. Yet the quotient $\mathbb{Z}/5\mathbb{Z}$ is not free as a  $\mathbb{Z}$-module and thus has no basis and not even any non-trivial free submodule or independent subset.

This is not exceptional. Indeed, the quotient $\mathcal{O_K}/\mathfrak{a}$ is always finite, its cardinality is called the norm of the ideal. Further, a finite $\mathbb{Z}$-module, in other words a finite abelian group, does not have any basis as a $\mathbb{Z}$-module, it does not even have an independent subset.

Thus, its  rank as a $\mathbb{Z}$-module is $0$.
(Note that there are other notions of rank for finite abelian groups, too.)

One can prove that every finitely generated $\mathbb{Z}$-module is of the form $A \oplus \mathbb{Z}^r$ with $A$ a finite abelian group. Thus for finitely generated modules those with rank $0$ are exactly the finite ones.


Where's the foolish part ? Prove that 0/0 = 2 I've been across this on the web:

\begin{align}
\frac{0}{0} & = \frac{100-100}{100-100} \\
& = \frac{10^2-10^2}{10(10-10)} \\
& = \frac{(10-10)(10+10)}{(10)(10-10)} \\
& = \frac{(10+10)}{10} \\
& = \frac{2}{1} \\
& = 2
\end{align}

Of course this is wrong but I can't tell where exactly since there is no obvious (to me at least) atrocity... Is this in the first line $ \frac{0}{0} = \frac{100-100}{100-100}$ ?

I'm going to rewrite this proof by dividing by all powers of ten and what not.

The proof essentially goes:

$$ \frac{0}{0}=\frac{2\cdot 0}{1\cdot 0}=\frac{2}{1}$$

The problem is in the first line, when you write $\frac{0}{0}$, which is undefined. Of course you could define it, but then it would be equal to every fraction since
$$\frac{a}{b}=\frac{c}{d}$$
if $ad=bc$, and if $a=b=0$, then this is always true, since for any $c$ and $d$, $0\cdot d=0\cdot c$.

But then all fractions are equal to each other, so there is only really one fraction: $\frac{0}{0}$. This seems a lot less useful than the system we had before.

You cannot remove the factor
$$
\frac {10-10}{10-10}
$$

and assume that the rest is $0/0$.


Proof of recursion theorem I was going through a real analysis textbook The Real Numbers and Real Analysis this morning, and I encountered a theorem stating that:

Let $H$ be a set, let $e\in H$ and $k:H\rightarrow H$ be a function. Then there always exists a unique function $f:\mathbb{N}\rightarrow H$ such that $f(1)=e$, and that $f(n+1)=k(f(n))$ for all $n\in\mathbb{N}$.

As a 1st year undergrad in maths, I have little knowledge in set theory except for the basics, but I simply couldn't help but wonder why does one have to consider the set $$C=\lbrace W\subseteq \mathbb{N}\times H\mid (1,e) \in W,\,\text{and if}\,(n,y)\in W,\,(n+1,k(y))\in W\rbrace$$ and let $f=\bigcap W\in C$ to prove $f$ does have the desired property and it is indeed a function.

Instead, could I not just define the relation to be $$W=\lbrace (a,b)\in \mathbb{N}\times H\mid (1,e) \in W,\,\text{and if}\,(n,y)\in W,\,(n+1,k(y))\in W\rbrace?$$

I know this sounds rather silly, but is there a reason why I can't define a set in this way? Is it because that the set builder notation actually involves the set itself, so I have to justify the existence of such a set beforehand? Or is it because of some other reason?

You want to prove the existence of a function. This means that you have to come up with the set of ordered pairs which is that function.

In the proof given in the book, we define a collection of relations, whose intersection is the wanted function.

What you suggest suffers from one of two possible problems:

Either this is not a well-formed definition, since it uses $W$ inside the definition of $W$; or
you actually claim that $W$ is a set which is equal to the set defined on the right hand side, but this gives you only the information that $W$ is closed under a certain operation. It, in fact, assumes that $W$ already exists, when you try to prove its existence to begin with.

Instead, the book opts for a different method. First define a collection of relations, then show that they define the wanted function.

Instead, could I not just define the relation to be $$W=\lbrace
 (a,b)\in \mathbb{N}\times H\mid (1,e) \in W,\,\text{and if}\,(n,y)\in
 W,\,(n+1,k(y))\in W\rbrace?$$

  I know this sounds rather silly, but is there a reason why I can't
  define a set in this way? Is it because that the set builder notation
  actually involves the set itself, so I have to justify the existence
  of such a set beforehand?

My opinion is that this is not a definition by itself. What we have here is the bootstrap process used by the Peano axioms for characterisation of the natural numbers. (See below)

You can write it more suggestive as
$$
\begin{matrix}
(1,e) \in W \\
(n,y) \in W \Rightarrow (n+1,k(y)) \in W
\end{matrix}
\quad (*)
$$
this seems a legitimate recursive definition of a set $W$ to me. Note that the inductive clause requires $(n,y) \in W$ and does not permit any choice from $\mathbb{N} \times H$.

Further it seems evident to me that
$$
W = \{ (n, k^{n-1}(e)) \mid n \in \mathbb{N} \} \quad (**)
$$
where $k^m$ means the $m$-fold application of the function $k$,e.g. $k^3 = k \circ k \circ k$, with the special case $k^0 = \mbox{id}$ and that this can be seen as graph of a function $f$:
$$
G_f = \{ (n, f(n)) \mid n \in \mathbb{N} \}  = W
$$
or in other words
$$
f(n) = k^{n-1} (e) \quad (n \in \mathbb{N})
$$

We have $W \subseteq \mathbb{N}\times H$ because for the first component $1 \in \mathbb{N}$ and $n \in \mathbb{N} \Rightarrow n+1 \in \mathbb{N}$ (see Peano axioms). For the second component we have $e \in H$ and due to $k : H \to H$ we have $k^{n-1}(e) \in H$ for any $n \in \mathbb{N}$.

It is my believe that $(*)$ leads to just $(**)$, there are no more elements in $W$. And here I am unsure, if I can get away with just that or not.

The problem I have with your excerpt of that proof is

I lack the imagination for more than one possible set $W$ within $C$. If I am correct that would make the intersection trivial and unnecessary
if there are different $W$ I would really need to be able to imagine them at least to that detail that I am able to perform the intersection


Integration of arctan(x) is itself? Sorry if this seems like a useless question, but I can't seem to work out what's wrong with the following reasoning, which leads to what is definitely an incorrect answer.

so,
$$
\int \arctan(x) dx = x \arctan(x) - \int \frac{x}{1+x^2}dx
$$

Pretty standard so far, then instead of using substitution to evaluate the second integral, I used integration by parts again:

$$
\int \frac{x}{1+x^2}dx=x \int \frac{1}{1+x^2}dx - \int \frac{1}{1+x^2}dx
$$

Which should be true, but must be where the problem is because this leads to

$$
x \arctan(x) - \arctan(x)
$$

which implies

$$
\int \arctan(x) dx = \arctan(x)
$$

Which is clearly wrong as arctan tends to a value whereas the areas under the curve does not, plus loads of other reasons why this is clearly a mistake.

Can somebody help me find out where I've gone wrong

You can't take the $x$ out of the first integral on the right side because $x$ is the integration variable and is not a constant. You would have to handle it differently like this: Let $u = 1+x^2$, and can you continue to the finish?

I figured out the problem pretty much as soon as I posted this, the second integral is a double integral, i.e.

$$
\int \frac{x}{1+x^2}dx=x \int \frac{1}{1+x^2}dx - \int \int \frac{1}{1+x^2}dx^2
$$

Which leads to

$$
\int \arctan(x) dx =x \arctan(x) - x \arctan(x) - \int \arctan(x) dx
$$


Prove that $\lim x_k = a \iff \lim \langle x_k, y \rangle = \langle a, y \rangle$ $\forall$ $y \in \mathbb{R}^n$. Could someone help me prove this real analysis theorem?

Prove that $\lim x_k = a \iff \lim \langle x_k, y \rangle = \langle a, y \rangle$ $\forall$ $y \in \mathbb{R}^n$.

Hint: For the first implication use the fact that the inner product is a continuous function. For the converse, let $y^i$ be zero in all entries and one in the $i_{\mathrm{th}}$ entry then you get $\lim\limits_{k\rightarrow\infty} <x,y^i>=\lim\limits_{k\rightarrow\infty} x^k_i=a_i$ where $x^k_i$ is the $i_{\mathrm{th}}$ entry of the vector $x^k$.

Hint It suffices to prove that

$$\lim x_k - a=0 \iff \lim \langle x_k-a, y \rangle = 0 \,;\, y \in \mathbb{R}^n$$

$\Rightarrow$ follows immediately from $\left| \langle x_k-a, y \rangle \right| \leq \| x_k-a \| \| y\| \,.$

$\Leftarrow$ Write $ x_k-a=y_k u_k$ where $y_k \in [0, \infty)$ and $u_k$ is an unit vector.

Now $u_k$ lives in a compact space. It suffices to prove that the only cluster point of $y_k$ is $0$.

To do this, pick $t$ is a cluster point of $y_k$, pick $y_{k_n} \to t$ and pick a subsequent of $y_{k_n}$ for which $u_{k_n}$ converges to some $u$. Set $y=u$ in

$$\lim \langle x_k-a, y \rangle = 0 $$


How to translate these sentences in discourse representation theory How would you translate these sentences in DRT?

Paul has a donkey. He does not like it.
If a student does not have a cat, she does not have a dog either.

Would that be something like:

Ax[(donkey(x)/\have(paul,x)) -> ~ love(paul,x)]

AxAy[(cat(x) /\ ~have(student,x) <-> (dog(y)/\~have(student,y)

Since you posted here at math.stackexchange.net, I assume you wanted to talk about this as a logic problem. You will need to ask at a https://linguistics.stacktheory.com
if you want to know about modeling this with DRT (Discourse Representation Theory).

You said:

Ax[(donkey(x)/\have(paul,x)) -> ~ love(paul,x)]

which by the way, is totally confusing like and love, so I assume you made a typo.

I'll assume you meant:
Ax[(donkey(x)/\have(paul,x)) -> ~ like(paul,x)]

I read this as meaning the same as:

(for-all x such-that donkey(x) is true
          and where have(paul,x) is true
then
    (not like(paul,x))) is true.

In English, I would say that this means
every donkey X that satisfies have(paul,X)
must also satisfy (not like(paul,X)) also.

when I read the statement:
   •Paul has a donkey. He does not like it.

I see several interpretations:
The first sentence doesn't seem to be subject to
more than one interpretation.
  Paul has a donkey.
  Let's give the name Donkey-01 to that donkey.
  so Paul has Donkey-01.
  ie have(Paul,Donkey-01) is true.

So far so good.

Just for grins and giggles, let's say that Paul has another donkey.
According to the Open World Assumption, we can assume that other facts
are true beyond those we start with.

Let's give the name Donkey-99 to the second donkey.
Since it is "another donkey" from Donkey-01, we know
that Donkey-01 is different from Donkey-99.

so we know have(Paul,Donkey-01) is true and have(Paul,Donkey-99) is true.
and different(Donkey-01,Donkey-99) is also true.

But the statement "He does not like it" could have multiple interpretations.

Conventionally it would be understood as Paul does not like a particular donkey he has.
We called the first donkey Donkey-01. So we can assume that Donkey-01 is the donkey the first sentence speaks about. So we can assume that Donkey-01 is also the donkey that Paul
does not like.  So (not like(Paul,Donkey-01)) is true.

If the second sentence is not talking about Donkey-99, we have no information whether Paul likes Donkey-99 or if (not likes(Paul,Donkey-99)

In passing, Unconventionally, the sentence may be saying the Donkey does not like Paul. We have no idea about what gender Paul may be (could be an "it") and we have no idea if the donkey is a "he". So strictly, we can't guarantee the conventional meaning is meant.

We could use a mu expression to make some of this more formal, but I think just using names is sufficient in this case.

Now technically, "he" and "it" are variables (some folk call them indexicals or even Deictic constructions, but let's not get distracted)
so formally:  the value of the variable he is Paul, and the value of the
variable "it" is "Donkey-01".  and so we know using the variables, the sentence (not like(he,it)) is true.  But maybe bringing in variables is too fast.

The real issue is that you said for-all X when you meant there-exists.
The original sentence did not say Paul does not like all donkeys. Conventionally understood, the sentence said Paul does not like a particular donkey that he has.
It didn't say anything about other donkeys Paul has, so you can't use a for-all.

As to your second sentence, you need a variable for the student. You used a class when you said ~have(student,x)  which doesn't mean what you think it means.

That third variable (let's call it s) must be the same student which you will use with the sentence (cat(x) && have(s,x) iff dog(y) && have(s,y))
and you have said that for-all cats and for-all dogs and should be saying for-all students as well. As well as the obvious that no cat can be a dog and no dog can be a cat. (We assume that is true, but it isn't an axiom in this system)  You also know that the students you care about are female as "she" is mentioned, so you might want to put that in your equation too.

A way to turn this on its head is to use two variables each of which mean all the things that a student may have (let's call the variables h1 and h2), and say that for-all students(s) such-that for-all h1 such-that for-all h2 such-that have(s,h1) && have(s,h2) && different(h1,h2) && not(cat(h1) && dog(h2)).
Note you don't need to say not(cat(h2) && dog(h1)) since you didn't restrict h1 and h2 so much that the statement couldn't be used with a different binding for h1 and h2.


How much math do we need to prove all simple numeric identities? Consider real numeric expressions build only from integers, operators $+,-,\times,/$ and taking a positive expression to a power (no variables involved), e.g.
$$\frac{2}{7},\ 2^{1/2},\ \sqrt[5]{2+\sqrt{11}},\ 2^{\sqrt{3}},\ ...$$
Now we can write identities between such expressions that are either true, e.g. $\sqrt{3+\sqrt{8}}=1+\sqrt{2}$, or false, e.g. $\frac{3}{5}=\frac{2}{7}$.

  Is it possible to prove all such true identities and disprove all false identities using only usual "high-school" algebra rules?

As far as I know, this is an open problem. It might be the case that even $ZFC$ axioms are not sufficient to settle all such questions, or that the problem is even undecidable (although it seems unlikely). The main issue that we know very little about behavior of repeated exponentiation. For example, it is unknown if the following number is an integer:
$$2^{2^{2^{2^{2^{2^{1/2}}}}}}$$
Personally, I expect that there are no surprises to be discovered in the repeated exponentiation, that this number will eventually be proved to be transcendental, and that there are no unexpected identities in your class of expressions that could not be explained using only "high-school" algebra rules. But these are only conjectures.

I'll answer no.

Suppose you could prove all identities using such rules.  Then there could get written  some infinite list of all such identities (you could enumerate all such identities by a characteristic function which returns "true" for each true identity and "false" for each false identity).  But, that would imply you could have a bijection between the set of all natural numbers and all of those identities.  So, you could encode all of those identities via the natural numbers.  Included in this list identities is all identities involving real numbers including pi=pi, e=e, sqrt(2)=sqrt(2).  That set of identities clearly has the same cardinality as the set of all real numbers.  But, there does not exist any bijection between the set of real numbers and the set of natural numbers.  So there does not exist any bijection between the set of all natural numbers and that of all such "high-school" algebra identities.  Therefore, you cannot prove "all such true identities and disprove all false identities using only usual "high-school" algebra rules".


Guessing a number between $1$ and $100$ with 10 distinct questions and 9 honest answers I've been trying to solve this riddle:

  Say I'm thinking of a number between 1 and 100. You can ask me 10 distinct yes/no questions to guess the number, but exactly one of my answers will be a lie and I won't tell you which one.

How can this be done?

We can do it by brute force, assuming that

which questions we ask can depend on the answers to earlier questions, and
it is okay to ask "artless" questions of the form "is it one of 1, 5, 7, 16, 17, 18, 37, 57, 72, 73, 98?"

We can imagine that our opponent starts by choosing both which number he's thinking of and when in the game he's going to lie, combining into a sample space of $100\times 10=1000$ outcomes. At the end we will know both parts of the outcome. This does not make the problem harder: if we have a strategy that produces the secret number, we'll be able to deduce the lie-position too simply by comparing the answers to what they should have been.

At each point in the strategy, let's say that there are

$n$ questions left to ask,
$m$ numbers that the opponent can be thinking of if they have not yet lied (each of these numbers represent multiple outcomes),
$s$ numbers that the opponent can be thinking of if they have lied exactly once (each of these represents a single outcome).

This means that there are $nm+s$ different outcomes still in play. In order to be sure of winning we need to maintain the invariant that $nm+s\le 2^n$. This is certainly true -- but only just barely -- in the initial state where $n=10$, $m=100$, $s=0$.

Actually, let's be generous and allow the opponent to think of $101, 102, \ldots, 124$, but in that case he will not lie. (We don't need to tell him that's an option, but it makes the strategy slightly easier to describe if we imagine this is the case). This gives an initial state of $n=10$, $m=100$, $s=24$, and we can then keep the invariant as
$$ nm+s = 2^n $$
exactly.

An initial observation is that each of the 100 (124) possible numbers can count among the $m$ or among the $s$ (or neither), but not both. This means that we have freedom to tailor our question such that what they do to the $m$ numbers is chosen independently of what they do to the $s$ numbers.

Now, the easy case first: If $m$ is even, then we ask a question about half of the $m$ numbers, and half of the $s$ numbers. No matter whether the answer is yes or no, we're now in a situation where
$$ m_{\rm new} = m/2 \qquad s_{\rm new} = s/2 + m/2 $$
which exactly cuts $nm+s$ in half:
$$ (n-1)m_{\rm new} + s_{\rm new} = nm/2 - m/2 + s/2 + m/2 = \frac{nm+s}2 $$

The case where $m$ is odd is slightly more involved. Then we can't ask any question that cuts $m$ in half. Let's split it as evenly as we can and ask a question that mentions $\frac{m+1}2$ of them. Then in the "yes" case we end up with
$ m_{\rm new} = m/2 + \tfrac 12 $, which contributes more than before to the $(n-1)m_{\rm new}$ term, so we need to ask about correspondingly fewer than $s/2$ of the single outcomes in order to maintain the $mn+s=2^n$ invariant.

Can we do that, however? The risk is that $s$ is so small that we cannot split it unevenly enough to correct for the uneven split of $m$. If we ask about $x$ of the $s$ numbers, we get
$$ s_{\rm new} = x + (m-m_{\rm new}) $$
and so we can solve for $x$ to find
$$ (n-1)m_{\rm new} + s_{\rm new} = \frac{nm+s}2 \iff x = \frac{s-n+2}2 $$
This will automatically be an integer (given that $m$ was odd, $s=2^n-mn$ will have the same parity as $n$), but it also needs to be non-negative, which is the case iff $s\ge n-2$.

Is there a risk that $s<n-2$? This can only happen if $m$ is $\lfloor 2^n/n\rfloor$ -- but the smallest $n$ for which that number is odd is $12$ (the next are $18$ and $25$), so that case cannot possibly arise here where $n$ starts out at $10$.

So the strategy will work.

This generalizes to problems of the form

  Ask $n$ questions to guess one of $m$ numbers, given that the opponent lies exactly once.

Clearly it is a necessary condition for this to be solvable that $nm\le 2^n$. The smallest case where this (and the above strategy) is not sufficient is $n=12, m=341$, where we see from the analysis above that no matter which question we ask first, either "yes" or "no" will lead us to having too many possible outcomes in the next step.

If we manage to ask the first question, though, the fact that $s$ gets a new contribution of about half of $m$ at each step means that we will never again have to worry about $s$ being too small.

Still unsolved: Is it possible to get through if we have to ask all our questions simultaneously without seeing any answers (and the questions cannot explicitly refer to which answers are provided for other questions or where the lie is)?

Intuitively I doubt it; that would need an extremely efficient packing of groups of 10 points in the 10-dimensional hypercube of possible answer sequences.

For each $n$ from 1 to 10 ask "Is Sha-512(your number|n) even?" Now, for each of the number $z$ from 1 to 100 and each $n$ from 1 to 10, check if Sha256(z|n) is even. When $z$ is your number, it will match your answers in exactly 9 cases. Other numbers will match for on average 5 numbers, since Sha-512 models a random oracle.


Kernel of the product homomorphism $A\otimes A\rightarrow A$ Let $R$ be a commutative ring with $1$ and let $A$ be a commutative $R$-algebra. We view $A\otimes A$ also as $R$-algebra, the multiplication on generators being given by $(a\otimes b)(a'\otimes b')= aa'\otimes bb'$.

Denote by $m: A\otimes A\rightarrow A$ the product homomorphism, i.e. the map that maps a generator $a\otimes b$ to $ab$.

My question is:

  Why is the kernel of $m$ generated by the elements $a\otimes 1 - 1\otimes a$ where $a$ runs through $A$?

The answer seems to be so easy that I could not find it anywhere in books. Alas, it is not clear to me :(

Thank you for your help!

Hint: Show that $a\otimes b - ab\otimes 1$ is in $I$, the ideal generated by elements of the form $x\otimes 1 - 1\otimes x$. This can easily be done by noting that $a\otimes b = (a\otimes 1)(1\otimes b)$, then substituting $1\otimes b = b\otimes 1 - (b\otimes 1 - 1\otimes b)$.

From here, show that every element of $A\otimes A/I$ can be written as $x\otimes 1 + I$.

Since $I$ is a sub-ideal of the kernel of your morphism, your morphism factors:

$$A\otimes A \to A\otimes A/I \to A$$

If $I$ is not the kernel, then $A\otimes A/I \to A$ is not $1-1$. But every element of $A\otimes A/I$ can be written as $x\otimes 1 + I$ and it must be sent to $x$. So this is necessarily $1-1$.

Easy: for $a\otimes b$ in the kernel, write $a\otimes b = (a\otimes 1-1\otimes a)(1\otimes b)$ and be done

=)


How to intuitively understand eigenvalue and eigenvector? I'm learning multivariate analysis and I have learnt linear algebra for two semester when I was a freshman.

Eigenvalue and eigenvector is easy to calculate and the concept is not difficult to understand.I found that there are many application of eigenvalue and eigenvector in multivariate analysis. For example

  In principal components, proportion of total population variance due
  to kth principal component equal
  $$\frac{\lambda_k}{\lambda_1+\lambda_2+...\lambda_k}$$

I think eigenvalue product corresponding eigenvector has same effect as the matrix product eigenvector geometrically.

I think my former understanding may be too naive so that I cannot find the link between eigenvalue and its application in principal components and others.

I know how to induce almost every step form the assumption to the result mathematically. I'd like to know how to intuitively or geometrically understand eigenvalue and eigenvector in the context of multivariate analysis(in linear algebra is also good).

Thank you!

Personally, I feel that intuition isn't something which is easily explained. Intuition in mathematics is synonymous with experience and you gain intuition by working numerous examples. With my disclaimer out of the way, let me try to present a very informal way of looking at eigenvalues and eigenvectors.

First, let us forget about principal component analysis for a little bit and ask ourselves exactly what eigenvectors and eigenvalues are. A typical introduction to spectral theory presents eigenvectors as vectors which are fixed in direction under a given linear transformation. The scaling factor of these eigenvectors is then called the eigenvalue. Under such a definition, I imagine that many students regard this as a minor curiosity, convince themselves that it must be a useful concept and then move on. It is not immediately clear, at least to me, why this should serve as such a central subject in linear algebra.

Eigenpairs are a lot like the roots of a polynomial. It is difficult to describe why the concept of a root is useful, not because there are few applications but because there are too many. If you tell me all the roots of a polynomial, then mentally I have an image of how the polynomial must look. For example, all monic cubics with three real roots look more or less the same. So one of the most central facts about the roots of a polynomial is that they ground the polynomial. A root literally roots the polynomial, limiting it's shape.

Eigenvectors are much the same. If you have a line or plane which is invariant then there is only so much you can do to the surrounding space without breaking the limitations. So in a sense eigenvectors are not important because they themselves are fixed but rather they limit the behavior of the linear transformation. Each eigenvector is like a skewer which helps to hold the linear transformation into place.

Very (very, very) roughly then, the eigenvalues of a linear mapping is a measure of the distortion induced by the transformation and the eigenvectors tell you about how the distortion is oriented. It is precisely this rough picture which makes PCA very useful.

Suppose you have a set of data which is distributed as an ellipsoid oriented in $3$-space. If this ellipsoid was very flat in some direction, then in a sense we can recover much of the information that we want even if we ignore the thickness of the ellipse. This what PCA aims to do. The eigenvectors tell you about how the ellipse is oriented and the eigenvalues tell you where the ellipse is distorted (where it's flat). If you choose to ignore the "thickness" of the ellipse then you are effectively compressing the eigenvector in that direction; you are projecting the ellipsoid into the most optimal direction to look at. To quote wiki:

  PCA can supply the user with a lower-dimensional picture, a "shadow" of this object when viewed from its (in some sense) most informative viewpoint

The determinant tells you by how much the linear transformation associated with a matrix scales up or down the area/volume of shapes. Eigenvalues and eigenvectors provide you with another useful piece of information. They tell you by how much the linear transformation scales up or down the sides of certain parallelograms. This also makes clear why the determinant of a matrix is equal to the product of its eigenvalues: e.g., in two-dimensional space, if the linear transformation doubles the length of a couple of parallel sides of a parallelogram (one eigenvalue is equal to 2) and triples the length of the other couple of sides (the other eigenvalue is 3), then the area of the parallelogram is multiplied by $2 \times 3 = 6$. See https://www.statlect.com/matrix-algebra/eigenvalues-and-eigenvectors for more details.