How do we show that the function which is its own derivative is exponential? In my calculus class, to show that $\frac{d}{dx}e^x=e^x$ we did something like this:

$$\lim_{h \to 0} \frac{a^{x+h} - a^x}{h} = a^x \lim_{h \to 0} \frac{a^h-1} h,$$

and then we defined $e$ to be the base $a$ that makes the limit

$$\lim_{h \to 0} \frac{a^h-1}{h}$$

equal to $1$. Now, my question is this: how can we know beforehand that the function which is its own derivative is an exponential function? In other words, if we have

$$ \lim_{h \to 0} \frac{f(x+h) - f(x)}{h} = f(x),$$

how do we know $f(x)$ is of the form $ka^x$ (ignoring the trivial case $f(x) = 0$)? How can we show that there aren't functions of other forms that give the same result?

Hint. If $f$ is such a function then calculating the derivative of $f(x)/e^x$ provides useful information about $f$.

\mathrm
We want an expression which when differentiated yields itself.
The first possible case is when $f(x)=0.$

Second, let's solve the initial value problem $f(0)=1$ and $f(x)=f'(x)$.
Now taking $f(x)=1,$ and then integrating the previous function and adding the result to obtain a better solution to the initial value problem, we get,
$f(x)=1 + x$, and then further integrating the second element, and repeating we get,
$f(x)=1 + x + (x^2)/2.$
Repeating the process will eventually yield the taylor series expansion for the exponential function as $f(x)=\sum_{i=0}^n (x^n)/k!$
And then we define the nth root of this expression as being the constant e.
Also, by differentiating the inverse of the function $f(x)$, we arrive at $(f^-1)'(x)=1/x$, which is the natural logarithm.

The essence of the exponential function with base e is that it is its own derivative and as such can be taken as its definition.

PS: We can also define e to be the positive upper limit of integration in the integral definition of the natural logarithm, and deduce that $e^x$ is its own derivative.


Evaluate $\lim_{x\to 0} (\frac {(1+x)^{\frac 1x}}{e})^{\frac{1}{\sin x}}$ Can I get a starting hint to solve this? The second index of $\frac{1}{\sin x}$ is throwing me off and I really don’t know what to do. Thanks!

Call this $L$, then evaluate $\ell:=\ln L$ viz.$$\ell=\lim_{x\to0}\frac{\tfrac1x\ln(1+x)-1}{\sin x}.$$Various methods show the numerator (denominator) is asymptotic to $-\tfrac12x$ ($x$), so $\ell=-\tfrac12$ i.e. $L=\tfrac{1}{\sqrt{e}}$.
Edit: as requested, here's an approach not using the Maclaurin series of $\ln(1+x)$. By L'Hôpital's rule,$$\frac{\ln(1+x)-x}{x\sin x}\sim\frac{1/(1+x)-1}{x\cos x+\sin x}=\frac{-1/(1+x)}{\cos x+\tfrac{\sin x}{x}}\to\frac{-1}{1+1}=-\tfrac12.$$

I did the following within my CAS:

Then I did

Limit[((1 + x)^(1/x)/E)^(1/x), x -> 0]

(*   1/Sqrt[Exp1] *)
Limit[((1 + x)^(1/x)/E)^(x/6), x -> 0]
1

Make use of the rule that if a limit is a product of two limits than the limit of the product exists and is the product of the limits. Calculation rules with limits in general. The rest is even more 1 for small x approaching 0.
N@(1/Sqrt[E])
0.606531

Table[((1 + x)^(1/x)/E)^(1/Sin[x]), {x, 0.0001, 0.0003, 0.0001}]
{0.606551, 0.606571, 0.606591}

ListLinePlot@
 Table[{x, ((1 + x)^(1/x)/E)^(1/Sin[x])}, {x, 0.0001, 0.0003, 0.0001}]

For small x this has an affine representation.
Series[((1 + x)^(1/x)/E)^(1/Sin[x]), {x, 0, 2}]
SeriesData[x, 0, {
 E^Rational[-1, 2], Rational[1, 3] E^Rational[-1, 2],
  Rational[-5, 18] E^Rational[-1, 2]}, 0, 3, 1]


Solving for positive reals: $abcd=1$, $a+b+c+d=28$, $ac+bc+cd+da+ac+bd=82/3$ $$a,b,c,d \in \mathbb{R}^{+}$$
$$ a+b+c+d=28$$
$$ ab+bc+cd+da+ac+bd=\frac{82}{3} $$
$$ abcd = 1 $$
One can also look for the roots of polynomial
$$\begin{align}
f(x) &= (x-a)(x-b)(x-c)(x-d) \\[4pt]
&= x^4 - 28x^3 + \frac{82}{3}x^2 - (abc+abd+acd+bcd)x + 1
\end{align}$$
and $f(x)$ has no negative roots... but how else do I proceed?
There is a trivial solution $\frac{1}{3}, \frac{1}{3}, \frac{1}{3}, 27$. We just need to prove it's unique.

The hint.
By your work  $$\frac{x^4-28x^3+\frac{82}{3}x^2+1}{x}-\frac{244}{27}=\frac{(3x-1)^3(x-27)}{27x}$$ because by Rolle $$\left(\frac{x^4-28x^3+\frac{82}{3}x^2+1}{x}\right)'=\frac{(3x-1)^2(x^2-18x-3)}{3x^2}$$ has three positive roots and one of them must be $\frac{1}{3},$ which is also an element of $\{a,b,c,d\}$.
Indeed, let $0<a\leq b\leq c\leq d$.
Thus, $f'$ has positive roots on $[a,b]$ on $[b,c]$ and on $[c,d]$ and we know that one of these roots it's double $\frac{1}{3}$.
Let $\frac{1}{3}\in[a,b]$ and $\frac{1}{3}\in[b,c].$
Thus, $b=\frac{1}{3}$, which says $$abc+abd+acd+bcd=\left(\frac{x^4-28x^3+\frac{82}{3}x^2+1}{x}\right)_{x=\frac{1}{3}}=\frac{244}{27}.$$

Use Mathematica to directly calculate this equation system, there are 4 sets of solutions that meet the requirements:

The output solution is only for comparison, not a substitute for theoretical analysis.


If $f(\frac{x}{y})=\frac{f(x)}{f(y)} \, , f(y),y \neq 0$ and $f'(1)=2$ then $f(x)=$? If $f(\frac{x}{y})=\frac{f(x)}{f(y)} \, , f(y),y \neq 0$ and $f'(1)=2$ then $f(x)=$?

I am not sure where to begin, any hints on starting and steps is apreciated.

Thank you

$f(x/y)=f(x)/f(y),\forall x,y$

if you take $x=y$ you obtain $f(1)=1$. As a consequence $f(1/y)=1/f(y)$.
$x=0$ and $f$ not constant implies $f(0)=0$.
if $a,b \neq 0$ then $f(ab)=f(a/(1/b))=f(a)/(f(1/b))=f(a)f(b)$. If for an element $x \neq 0$ we have $f(x)=0$ then $f$ would be constant, which contradicts $f'(1)=2$.
In particular you have $f(x^2)=(f(x))^2>0$.
Define for $x>0$ $g(x)=\log(f(e^x))$. Then $$g(x+y)=\log(f(e^xe^y))=\log(f(e^x))+\log(f(e^y))=g(x)+g(y)$$
This means that $g$ satisfies a Cauchy functional equation and it is continuous (since you assume $f$ to be differentiable at $1$). This means that there exists $a$ such that $g(x)=ax$.
This leads to: $\log(f(e^x))=ax \Rightarrow f(e^x)=(e^{x})^a \Rightarrow f(x)=x^a$ for $x>0$.
Now the condition $f'(1)=2$ implies that $a=2$ and $f(x)=x^2$ for $x>0$.
Because $f(x^2)=f(x)^2$ even for negative $x$ you have $f(-x)=\pm f(x)$.

Linear functions satisfied this function-equation trivially.

Let $f(x)=2x$ then $f'(x)=2$ for all $x$ and $f\left(\frac{x}{y}\right)=\frac{f(x)}{f(y)}$.

That's all :-)

R


Show that all roots of $z^4+z^3+1$ of of modulus less than $3/2$ by using Rouche's Theorem. I was wondering if you could help me understand how to to apply Rouche's Theorem to this Complex Analysis problem:

Show that all roots of $z^4+z^3+1$ of of modulus less than $3/2$ by using Rouche's Theorem.

There are a few ways to state Rouche's theorem, but here's one that will work in this case: if $f$ and $g$ are holomorphic on a domain containing a circle $C$ and its interior, and if $|f|>|g|$ on $C$, then $f$ and $f+g$ have the same number of zeros inside $C$.

In this case, take $f(z)=z^4$, $g(z)=z^3+1$, and $C=\{|z|=\frac{3}{2}\}$.

Consider the polynomial $P(z)=z^4+z^3+1$ and the curve $\gamma$ that traces out the circle $|z|<3/2$. Define $f(z):=z^4$ and $g(z):=z^3+1$. Then $P(z)=(f+g)(z)$. Since $f$ and $g$ are also polynomials, they are analytic on and inside $\gamma$. Note also that $|f(z)|>|g(z)|$ for all $z\in \gamma$, because:
        \begin{align*}
   |f(z)|&=|z^4|\leq (3/2)^4=81/16\\
   |g(z)|&=|z^3+1|\leq |z^3|+1\leq (3/2)^3+1=70/16
  \end{align*}
        Along the boundary $\gamma$, these upper bounds are maximized. So, along $\gamma$, we have that $|f(z)|>|g(z)|$.
        Recall by Rouche's Theorem that if $f$ and $g$ are analytic inside and on a regular closed curve $\gamma$ and that $|f(z)|>|g(z)|$ for all $z\in \gamma$, then the number of zeros, including order, of $f+g$ inside $\gamma$ is equal to the number of zeros, including order, of $f$ inside gamma.
        Since $f(z)=z^4$, there exists a zero of order $4$ at $z=0$ inside $\gamma$. Hence, $P(z)=(f+g)(z)$ also has $4$ zeros inside of $\gamma$ as well. Since these four zeros are inside the circle $|z|<3/2$, then the zeros are of modulus less than $3/2$. Further, by the Fundamental Theorem of Algebra, we have that since the degree of $P(z)$ equals four, then $P(z)$ has exactly four zeros on in its domain. However, using Rouche's Theorem, we have shown that all four of the zeros of $P(z)$ are of modulus less than $3/2$, as desired.


Find closest point on a plane to a given point. Discrepancy with normal vector. I have a point $(9,5,0)$ and a triangle with points $(1,1,0), (3,3,1), (6,1,0)$, let's label them as $A,B,C$ respectively. In order to get the normal vector, I do the cross product of two vectors. If I do $AB \times AC$ I get $n = \left\langle 0,-5,10\right\rangle$. With this I determine the equation of the plane is $5y - 10z - 5 = 0$. If I project my point onto the plane with this normal vector in mind, the point on the plane I find is $(9, 21/5, 8/5)$.
HOWEVER, if I initially choose to cross two different vectors, I get something different.

Example: If I instead choose to do $BA \times BC$ I get $n = \left\langle 0,5,-10\right\rangle$. Now this in a way makes sense to me since it is the inverse of the other normal I found. Basically the other half of the line through the plane, right? If I continue, I find the equation of the plane to be $-5y + 10z + 5 = 0$. This leads me to a projected point of $(9, -29/5, -8/5)$.
Why do I get two different points based on which normal vector I choose to solve with?
I know the correct answer to this problem, one is right and one is wrong. I am trying to program a general solution to this type of problem. How do I choose the correct normal vector?

Please let me know if I am doing something wrong.

$\vec{AB} = <2,2,1> \quad \quad \vec{AC} = <5,0,0>$.

So, $\vec{AB} \times \vec{AC} = <0,5,-10>$

Then, the plane equation is something like $5y -10z = C$ for some constant $C$.

Plug (for example) the point $(1,1,0)$ into the plane equation to get $C=5$.

Hence, the plane equation is $5y -10z -5 =0$ or equivalently $-5y +10z+5=0$ which is slightly different from the one you found.

Edit: Let's continue with a different approach. The vector $\vec{n} = <0,5,-10>$ is perpendicular to the plane. The line that passes through our point $(9,5,0)$ which is parallel to $\vec n$ is
$$x=9, \quad y=5+5t, \quad z=0-10t, \quad t \in \mathbb R$$

Now let's find where this line cuts the plane. Pick an arbitrary point from the line and put into the plane equation:

$$0= 5y-10z-5 =5(5+5t)-10(0-10t)-5$$

$$125t + 25 -5=0 \quad \implies \quad t=-\frac{4}{25}$$

So, the answer is $(9,5+5t,0-10t)=(9,-\frac{21}{5},\frac{8}{5})$.

Edit2: Now we do the projection. Choose an arbitrary point on the plane, say $A(1,1,0)$ and consider the vector $\vec{AP}$ where $P=P(9,5,0)$. $\vec{AP}=<8,4,0>$.

Then,

\begin{align*}
proj_{\ \vec n \ } \vec{AP} &= |\vec{AP}| \cdot \cos \alpha \cdot \frac{\vec n}{| \vec n |} \\
&= |\vec{AP}| \cdot \frac{\vec{AP} \bullet \vec n}{|\vec{AP}| \cdot |\vec n|} \cdot \frac{\vec n}{| \vec n |} \\
&= \text{ calculations ... find the projection vector} \\
&= \vec u
\end{align*}

Now, the point you are looking for is the point $K$ such that $\vec{KP} = \vec u$

"I have a point $(9,5,0)$ and a triangle with points $(1,1,0), (3,3,1), (6,1,0),$ let's label them as $A,B,C$ respectively. In order to get the normal vector, I do the cross product of two vectors."

So you mean a normal vector to the plane determined by the three points.

"If I do $AB \times AC$ I get $n = <0,-5,10>$. With this I determine the equation of the plane is $5y - 10z + 5 = 0.$"

No, that does not contain $(1, 1, 0)$ because $0(1)+ 5(1)- 10(0)+ 5= 10$, not 0.
The equation of the plane is $0(x- 1)-5(y- 1)+ 10z= 0$ or $5y- 10z- 5= 0$.  Perhaps you meant $5y- 10z= 5$.

"If I project my point onto the plane with this normal vector in mind, the point on the plane I find is $(9, 21/5, 8/5)$. HOWEVER, if I initially choose to cross two different vectors, I get something different.
Example: If I instead choose to do $BA \times BC$ I get $n = <0,5,-10>$. Now this in a way makes sense to me since it is the inverse of the other normal I found. Basically the other half of the line through the plane, right? If I continue, I find the equation of the plane to be $-5y + 10z -5 = 0.$"

Which, again, is wrong.  The cross product of $BA \times BC$, as you say is $<0, 5, -10>$ and, since the plane contains the point $(1, 1, 0)$, the plane has the equation $0(x- 1)- 5(y- 1)+ 10(z- 0)= -5y+ 10z+ 5= 0$, not $-5y+ 10z- 5$.

"This leads me to a projected point of $(9, -29/5, -8/5)$. Why do I get two different points based on which normal vector I choose to solve with?"

You don't say how you got two different points.  Since you have exactly the same equation for the plane in both cases (although wrong!), and the same point, you should be doing exactly the same calculations in both cases.

"I know the correct answer to this problem, one is right and one is wrong. I am trying to program a general solution to this type of problem. How do I choose the correct normal vector?
Please let me know if I am doing something wrong."

Yes, if you get different answers projecting the same point onto the same plane, you must have done something wrong!  But since you don't show what you did, it is impossible to say what you might have done wrong.


If $a+b+c=0$ prove that $ 3(a^2+b^2+c^2) \times (a^5+b^5+c^5) = 5(a^3+b^3+c^3) \times (a^4+b^4+c^4) $ If $a+b+c=0$, for $a,b,c \in\mathbb R$, prove

  $$ 3(a^2+b^2+c^2) \times (a^5+b^5+c^5) = 5(a^3+b^3+c^3) \times (a^4+b^4+c^4) $$

I made this question as a more difficult (higher degree) version of this question. My idea was that algebraic brute force methods are easy to distinguish from more sophisticated ones if the degree of the terms in the question is higher.
The question was specifically made using the method from my answer to the linked question.

Let's define
$$S_n=a^n+b^n+c^n$$
and consider the generating function
$$F(t)=\sum_{n=0}^\infty S_nt^n=\frac1{1-at}+\frac1{1-bt}+\frac1{1-ct}.$$
Using $a+b+c=0$ gives
$$(1-at)(1-bt)(1-ct)=1+pt^2+qt^3$$
for some $p$ and $q$, and
$$F(t)=\frac{3+pt^2}{1+pt^2+qt^3}.$$
From this we expand as a power series
$$F(t)=(3+pt^2)(1-(pt^2+qt^3)+(pt^2+qt^3)^2-\cdots)
=3-2pt^2-3qt^3+2p^2t^4+5pqt^5+\cdots$$
and now you can read off this, and several other identities...

plug in the term $$c=-a-b$$ in the left-hand side of the equation we get
$$-30 a b (a+b) \left(a^2+a b+b^2\right)^2$$ and so is the right-hand side
a remark: if we compute the left-hand side minus the right-hand side and factorize, we obtain
$$-(a+b+c) \left(2 a^6-2 a^5 b-2 a^5 c-a^4 b^2+4 a^4 b c-a^4 c^2+6 a^3 b^3-3 a^3 b^2 c-3 a^3 b
   c^2+6 a^3 c^3-a^2 b^4-3 a^2 b^3 c+6 a^2 b^2 c^2-3 a^2 b c^3-a^2 c^4-2 a b^5+4 a b^4 c-3 a
   b^3 c^2-3 a b^2 c^3+4 a b c^4-2 a c^5+2 b^6-2 b^5 c-b^4 c^2+6 b^3 c^3-b^2 c^4-2 b c^5+2
   c^6\right)$$ and it is clear that we get zero


how to find number of sides of an irregular polygon? An irregular polygon has one angle 126 degrees and the rest 162 degrees. how many sides are there in this irregular polygon?

I have tried to find our the sides with the formula of a regular polygon; obviously it doesn't work.

Using the formula of the sum of interior angles

$$162(n-1) + 126 = 180(n-2) \Rightarrow n=18. $$

Remark: I assume a simple and plane polygon.

try this: do the average of 162 and 126. So that would equal 144. Then subtract 180- 144 and you will get 36. Then divide 36 by 360 and get 10. Therefore your polygon has 10 sides.


How to find the ratio for a combination of two chemical solutions Lets say you have a chemical solution $A$ that has a ratio of $4:1$ of water to some chemical substance, and a solution $B$ that has a ratio of $9:1$ of water to some other chemical substance.

If you combine the same amount of each solution, the resulting solution is not in a ratio of $6.5 : 1$ (the average), but is instead $5.6666 : 1$.

Can someone help me understand why one cant just average the two ratios if the same amount of solution is added together? For some reason its just not clicking.

Take 10x litre of each solution, so we are adding 8x & 9x litre of water (not 8x litre each), 2x & x litre of that chemical(not 2x or x litre each).

So, total water = (8x + 9x) litre = 17x litre and total chemical=(2x + x) litre = 3x litre.

So, the resultant ratio is $\frac{17}{3}=5.666...$

Clearly, when we are adding the same amount of the solutions, the same amount of water (or the chemical) are not added.

Trivially, we could take average, only if we had added same amount of water (or the chemical) separately.

Let us assume that the ratio of water and the chemical be a:b in the first solution and c:d in the second.

Let's take (a+b)x litre of the 1st solution  and (c+d)y litre of the second.

So, water taken = (ax + cy) litre and the chemical taken = (bx + dy) litre.

If $\frac{ax+cy}{bx+dy}=\frac{\frac{a+c}{2}}{\frac{b+d}{2}}$

$=>\frac{ax+cy}{bx+dy}=\frac{a+c}{b+d}=>(bc-ad)(x-y)=0$

So if bc=ad=>c:d=a:b (i.e., if the ratios of water & the chemical are same), the ratio of water & the chemical will be the ratio of their average for any values of x,y i.e.,  we can mix the solutions in any ratio.

Here is this question $a=4,b=1,c=9,d=1=>bc-ad=1.9-4.1≠0=>x=y$

So, we need to take (4+1)x and (9+1)x litres of the solutions, respectively to make the  ratio of water and the chemical as the ratio of their average.

Keep in mind that it's the ratio of water/chemical.

If you have 4:1 water/chemical for solution A and 9:1 water/chemical for solution B, then solution A is 4/5 water and solution B is 9/10 water. Then if you mix together $x$ units of solution A with $x$ units of solution B, you get $4x/5 + 9x/10 = 17x/10$ units of water per $2x$ units of mixture. Thus, you know that $17/20$ of the mixture is water, so the ratio of water/chemical is $17/3 = 5.666\ldots$.


Why do we usually quotient a polynomial ring by a monic irreducible polynomial? I'm studying some ring theory, and I'm wondering for a polynomial ring $F[x]$ over a field $F$, if we quotient by some element $f(x) \in F[x]$ to get $F[x]/(f(x))$, why do we usually want $f(x)$ to be monic irreducible? How about arbitrary polynomials $g(x)$?

Quotient by irreducible to get an integral domain because if it is not irreducible say $F[x]/g(x)f(x)$ then $f(x),g(x)$ are non zeros element in the quotient ring such that $f(x)g(x)=0$


How does Raph Levien's Spiro choose angles for the ends of a path? I've read Raph Levien's paper on splines (http://www.levien.com/phd/phd.html), and think I mostly understand chapter 8, the nuts and bolts of fitting a piecewise polynomial spiral to a sequence of points.

For the procedure described, the path has to be a loop. Otherwise it has two degrees of freedom too many: the Newton-like process does not affect the tangent angles at the ends.

Ideally, the end angles should be those that minimize the integral over path length of the square of the first derivative of curvature.  Maybe that solution is hard to find, and Spiro uses a crude rule of thumb instead.  Does someone know?

So I asked Raph Levien.

  You're absolutely right that these are under-determined. Simply, in Spiro the end segments are circular arcs.

  I talk about this a little in section 3.1 of my newer spline research
  paper: https://spline.technology/paper1.pdf

  Thanks for your interest!

You can do pretty much whatever you want. You can clamp endpoint curvature to zero, have it continue the curvature or try to minimize path length like you say. Depending on your solver it may do the latter for you.

The choice of method depends on the application, e.g. graphic designers might not like a strictly "correct" method (in terms of the math).


What does $\frac{d^2 u}{dt^2}$ mean? When it comes to taking a derivative, what does $\displaystyle \frac{d^2 u}{dt^2}$ mean ? Does it mean taking derivative of the function twice with respect to $t$. If yes, why is then $d^2 u$ squared? Thanks in advance!

This basically means that taking the second derivative of any given function.
To elaborate this you can consider some function $$y=f(t)$$ Now lets find its derivative $$y'= \frac{d(f(t))}{dt}$$. Now lets say I want to know what would the derivative of the earlier function $y'$ would be. That will be $$y''=\frac{d(\frac{d(f(t))}{dt})}{dt}$$ and this would be $$y''=\frac{d^2u}{dt^2}$$ where $u=f(t)$

Now in terms of physics you can think this as if i have the position as the function of time if i find its derivative it gives me the velocity and again if i find its derivative it gives me the acceleration . So the second derivative of the position gives me the acceleration

this simply means it is the second derivative of u with respect to t


$\sqrt[n]{ab} = \sqrt[n]{a}\sqrt[n]{b} $ just for a,b>0 The property $\sqrt[n]{ab} = \sqrt[n]{a}\sqrt[n]{b} $ is valid just if $a,b>0$. If this restriction didn't apply $\sqrt{-1}\sqrt{-1} = -1$ would be equal to $\sqrt{(-1)(-1)} = 1$

Beside giving particular examples, how can I show that the $a,b>0$ is required for $\sqrt[n]{ab} = \sqrt[n]{a}\sqrt[n]{b} $  to be true?

The answer to this question really comes down to the definition of $\sqrt[n]{a}$. If this symbol describes any number $x$ so that $x^n = a$, then $\sqrt[n]a$ describes a set. $\sqrt{-1}\sqrt{-1} = \pm i^2 = \pm 1 = \{-1.1\}$, while $\sqrt{(-1)(-1)} = \sqrt{1} = \pm 1 = \{-1,1\}$. So, in fact, the set of values defined by these two expressions are equivalent.

You may want to define $\sqrt[n]a$ as the unique positive real number $x, x>0$ when $a>0$ and the unique positive imaginary number $ix, x>0$ when $a<0$. Then, if $a,b<0$, then $ab>0$, so $\sqrt[n]{ab}>0$ by definition. $\sqrt[n]a\sqrt[n]b = xi\cdot yi = -xy <0$ on the other hand, hence the discrepancy.

When you put a restriction on the definition for $\sqrt[n]a$, you're going to have restrictions on it's properties as well.

apply the nth power to both sides and conclude in a true statement then the first statement must be true because of the double implication in an equality. there is no problem because you have the nth root of two positive numbers and the nth root of the product of two positive numbers which makes it also positive. what is more, you can distribute the n in the right hand side of the equation because of the commutative property.


Solving the problem of conditional probability without using P($A | B$). I was trying to differentiate $A|B$ and $A \cap B$. I think understanding the following problem will clear my doubt.

There are two urns namely $U_1$ and $U_2$. $U_1$ contains three white balls and  five red balls while $U_2$ contains four white balls and five red balls. One Urn is chosen randomly and a white ball is drawn. What is the probability of drawing the white ball from the $U_1$?

If I name the event of choosing the urn is $A$ and drawing a white ball is $B$ , Then what will be the event $A \cap B$ and how the sample space will look like.

I want to determine P($A \cap B$)  by determining  $ \frac{n(A\cap B)}{n(S)} $. $S$ denotes the sample space. I know how to solve it by using conditional probability. I can not see the sample space. Can anyone elaborately explain me what will be the sample space $S$.  I want to solve this problem by the way Bram28 has solved here

Can anyone please help me to understand?

You call $A$ "the event of choosing an urn," but events need to be specific things. As you've stated it, $A=S$, meaning every event in your sample space involves picking an urn. That's just part of the problem setup.

Since you are looking for $P(A|B)$ and the problem is to find the "Probability of picking $U_1$ given that a white ball was drawn," you probably meant that $A$ is the event of picking $U_1$.

You say you want to find $P(A\cap B)$ (the probability of picking an urn and then picking a white ball) by finding $\frac{n(A\cap B)}{n(S)}$ (the number of ways you can draw a white ball divided by the size of the sample space). You appear to believe that these quantities are equal, but as a general rule,
$$P(A\cap B)\neq\frac{n(A\cap B)}{n(S)}.$$
You can only count on these being equal if each of the ways in which you could draw a white ball is equally likely to occur (for the urn problem, they're not). Let's change the numbers to make this obvious: if $U_1$ had one red, one white and $U_2$ had one red, 100 white, then $n(A\cap B)=1$ because there is 1 way to draw the white ball form $U_1$. The total number of possible outcomes is the number of balls, $n(S)=103$. So
$$\frac{n(A\cap B)}{n(S)}=\frac1{103}.$$
But the probability of drawing the white ball from $U_1$ is $\frac12\times\frac12=\frac14$

You say that you know how to do the problem with conditional probability so you don't want any conditional probability solutions. I am quite certain that there is no correct solution method that does not involve conditional probability. You can get rid of conditional probabilities quickly with Bayes' rule, of course:
$$P(A|B)=\frac{P(A\cap B)}{P(B)}.$$

You might want to post your solution as a comment and ask for help checking its accuracy.

edit:

joriki is correct that $(A|B)$ is not an event. In fact, without talking about probability, $(A|B)$ doesn't really have a meaning. $P(A|B)$ is the probability of the event $A$, but measured in a different way. By putting "$|B$" in there, what you mean is that your experiment has fundamentally changed. $P(A|B)$ means you want the chances of $A$ (picking $U_1$) in an experiment where, if event $B$ does not occur (a red ball is drawn), you ignore the result and start over.

$A\cap B$ is an event: the event that both event $A$ and event $B$ occur.

edit again:

You can't solve this problem in the same way as that example. In Bram28's example, there is a die being thrown, and there are 6 events that each have equal chances of occurring. These are $S=\{1,2,3,4,5,6\}$. Bram28 constructs two more events of interest: $A=\{4,5,6\}$ and $B=\{2,4,6\}$. He then calculates
$$
P(A\cap B)
=\frac{n(A\cap B)}{n(S)}
=\frac{n(\{4,6\})}{n(\{1,2,3,4,5,6\})}
=\frac26
$$
This shortcut is only correct because each event has the same probability of occurring:
$$
P(A\cap B)
=
P(\{4,6\})
=
P(\{4\})+P(\{6\})
=
\frac16+\frac16
=
\frac26.
$$

In my 103 ball example, the events in the sample space do not have equal chances. There is more than one way to write the sample space. I choose to write members of $S$ as pairs with the number of the chosen urn first and a letter for the color of the drawn ball second. I'm going to pretend that every white ball in $U_2$ has a number which will be a subscript, like this:
$$
S=\{(1,W),(1,R),(2,W_1),(2,W_2),\dots,(2,W_{100}),(2,R)\}.
$$

I said that Bram28's calculation method won't work for this example because
$$
\frac{n(A\cap B)}{n(S)}=\frac{n(\{(1,W)\})}{103}=\frac1{103}.
$$

We are all set I have E either ey and use the wishes everything is yes but even E everything eye text me eye roll eeryrhyfyr E we ye eye R Wrobleski I R really eyeyduduyr to E either way ye R to E run errands to run right by the kids are going to be able to get to my we ended up yet eye on right E eueudiey yes eyueeiy to be E either eye is E et you eyeyduduyr eye is ehufyiddh I just can't get over Wednesday unless E either ey eyueeiy I will say u we ye I ey ugh ye I email will E either way easier E it ends up being the kids ejdieydiue you can always be eye is better than nothing ye E everything is going out my E everything is


Finding total number of divisors which divide 2 given numbers Possible Duplicate:
  Number of common divisors between two given numbers

I need to find the total number of divisors which divide both the numbers lets say N and M.
Actually I tried to think about it  a lot and searched at a lot of places for a possible answer. All I could think of was finding the prime factors and generating the actual divisors from the factors ?
However this would take a lot of computation,therefore I need a much faster method performing  much fewer operations?
Is there any well known algorithm or formula for this problem or any derivable formula?
I think the answer should be the number of divisors of the gcd of the 2 numbers.

It is the number of divisors of the greatest common divisor (GCD) of N and M.  You can find the GCD by the Euclidean algorithm, which does not require factoring.  This is generally a smaller number than N or M, but then you need to factor it.  You don't need to generate all the divisors, you can use the divisor function as the product of one more than the power of each prime dividing the GCD.

let x = gcd(n,m) (greatest common devisor)
and then  x - oiler(x)
how to find the gcd u can read here - http://en.wikipedia.org/wiki/Greatest_common_divisor

how to calculate oiler function u can find here http://en.wikipedia.org/wiki/Euler%27s_totient_function

(oiler fuction give you all the number strangers to your number)


A question of formality regarding limits Let $f$ be a differentiable function over $\mathbb{R}$, with its derivative being a continuous function. Let there be a function $g$ s.t. $\lim_{x \to 0} g(x) = 0$.

Now I'm required to show that $f'(0) = \lim_{x \to 0} \frac{f(x+g(x)) - f(g(x))}{x}$

The solution seems almost obvious from the definition yet I find myself dealing with two variables and two limits, my question is how would I formally write the transitions leading to this equality, using the definition of the derivative at $x = 0$?

Thanks a million!

from the principal definition of a derivative we know that :

$$f'(t) = \lim_{x \to 0} \frac{f(t + x) - f(t)}{ x}$$

for $f '(0)$ instead of substituting $0$ in the definition we use $g(x)$ since its limit is zero as $x \to 0$.

we thus get:

$$f '(0) = \lim_{x \to 0} \frac{f(g(x) + x) - f(g(x))}{x}$$


To solve $ y'+y=|x|$ What is the solution to the IVP $$y'+y=|x|, \ x \in \mathbb{R}, \ y(-1)=0$$

The general solution of the above problem is $y_{g}(x)=ce^{-x}$.

How to find the particular solution? As $|x|$ is not differentiable at origin. Is there any alternate way to get the solution?

Hint: using the integrating factor the equation can be rewritten as
$$
(e^{x}y(x))'=e^{x}|x|.
$$
Thus, you are left with writing down the solution to $w'(x)=f(x)$, $w(x_0)=0$ ($f$ continuous).

   $$w(x)=\int_{x_0}^x f(t)\,dt.$$

$$y'+y=|x|$$
Solving without condition :

Case $x>0 \quad:\quad y'+y=x \qquad y=c_1e^{-x}+x-1$

Case $x<0 \quad:\quad y'+y=-x \qquad y=c_2e^{-x}-x+1$
$$y=ce^{-x}+(x-1)\text{ sgn}(x)$$
sgn$(x)$ is the function sign of $x$

The function is discontinuous at $x=0$.

The discontinuous curve represented is only an example for a particular value of $c_1=c_2=c$. Of course they are an infinity of solutions. Don't confuse this general equation with the solution below which is strictly the answer corresponding to the condition $y(-1)=0$.

With condition $\quad y(-1)=0$ :

$y(-1)=0=c_2e^{-(-1)}+((-1)-1)(-1)=c_2e+2\quad;\quad c_2=-\frac{2}{e}$
$$y=-2e^{-x-1}-x+1 \quad \text{in } x\leq 0. \tag 1$$

In $x>0$ :

Condition $y(0)=1-2e^{-1}$

$y(0)=1-2e^{-1}=c_1e^{-0}+0-1=c_1-1\quad;\quad c_1=2-2e^{-1}$
$$y=2(1-e^{-1})e^{-x}+x-1 \quad \text{in } x\geq 0. \tag 2$$

Note after the comments :

The above solution Eqs.$(1)$ and $(2)$ is the same as the LutzL's solution written on a different form :
$$y=ce^{-x}+sign(e^{-x}-1+x)$$
with $c=1+2e^{-1}$.


Distances of points around unit circle $P_1,\cdots , P_{10}$ are ten points on the unit circle
What  is the largest possible value of the quantity
$$\sum_{1\le i<j\le 10} |P_i-P_j|^2$$

We may just use the identity:
$$\|P_1+P_2+\ldots+P_n\|^2 = \sum_{k=1}^{n}\|P_k\|^2+2\sum_{1\leq i < j\leq n}\langle P_i,P_j\rangle \tag{1}$$
from which it follows that:
$$\sum_{1\leq i<j\leq n}\|P_i-P_j\|^2 = 2(n-1)\sum_{k=1}^{n}\|P_k\|^2-2\sum_{1\leq i<j\leq n}\langle P_i,P_j\rangle\tag{2}$$ can be written as:
$$\sum_{1\leq i<j\leq n}\|P_i-P_j\|^2 =\color{red}{-\|P_1+\ldots P_n\|^2}+\color{blue}{(2n-1)\sum_{k=1}^{n}\|P_k\|^2}.\tag{3} $$
If every $P_k$ lies on the boundary of a unit ball, the blue term is just $\color{blue}{n(2n-1)}$.
The red term is always negative, unless the centroid of $P_1,\ldots,P_n$ is the centre of the previous ball.
Now the question is trivial and, interestingly, dimension-independent.

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\mc}[1]{\,\mathcal{#1}}
 \newcommand{\mrm}[1]{\,\mathrm{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\sum_{i = 1}^{9}\sum_{j = i + 1}^{10}
\verts{\expo{\ic\theta_{i}} - \expo{\ic\theta_{j}}}^{\color{#f00}{2}} & =
\sum_{i = 1}^{9}\sum_{j = i + 1}^{10}\pars{\expo{\ic\theta_{i}} - \expo{\ic\theta_{j}}}\pars{\expo{-\ic\theta_{i}} - \expo{-\ic\theta_{j}}}
\\[5mm] & =
\sum_{i = 1}^{9}\sum_{j = i + 1}^{10}\bracks{2 - 2\cos\pars{\theta_{i} - \theta_{j}}}=
4\sum_{i = 1}^{9}\sum_{j = i + 1}^{10}\,\,\,
\sin^{2}\pars{\theta_{i} - \theta_{j} \over 2}
\\[5mm] & \leq
4\sum_{i = 1}^{9}\pars{10 - i} =
4\pars{9 \times 10 - \half \times 9 \times 10} = \color{#f00}{180}
\end{align}


probability statistics If there was a tree randomly distributed in a degraded forest at a rate of $5 \text{ trees}/ 1000 m^2$ (meter squared), then what is the probability of finding one or more of these trees in a randomly selected $100 m^2$ plot ??

I have no idea where to start from, can any one help and explain please.

As Michael Hardy said, this is most naturally modeled with a Poisson distribution.

You are told that the rate is 5 per 1000 m2 and asked to find the probability of finding a tree in 100 m2. You need to scale the rate to 0.5 per 100 m2 and then the probability will be 1-Poisson($0;\lambda=0.5$).

This is a Poisson distributed random variable with a mean of 5/1000.

P(equal to or more than 1 trees in 100 m^2 ) =
1- P(0 trees) =

1 - (5 x 100/1000)^0 x e^(-5 x 100/1000)/0! = 0.3935


Prove $\lambda$ is eigenvalue of $A$ iff $\lambda^*$ is eigenvalue of $A^\dagger$ with kernel I don't know how to prove the statement " $\lambda$ is an eigenvalue of $A$ iff $\lambda^*$ is an eigenvalue of $A^\dagger$" being $A$ an operator in a complex, finite Hilbert space. And only using kernels, images, orthogonality, and inner product concepts to prove it (can't use dimensions).
I think it has to be something similar to the following one:
$$Ax=\lambda x \xrightarrow[]{} (A-\lambda I)x=0$$
Where $x$ is the eigenvector, and then:
$$\ker(A-\lambda I)=(Img(A-\lambda I)^{\dagger})^{\perp} = Img(A^{\dagger}-\lambda^* I)^{\perp}$$
But at that point I get stuck, any hints about how to continue?
Thank you so much!

You're almost there. Think about the dimension of the space
$$\text{ker}(A - \lambda I) = \text{Img}(A^\dagger - \lambda^* I)^\perp$$
We know that it's dimension is nonzero, so in particular this means that the dimension of the $\text{Img}(A^\dagger - \lambda^* I)$ must be strictly less than $n$, which is the order of $A$ and $A^\dagger$. But from rank-nullity, this would imply that
$$\text{dim}(\text{ker}(A^\dagger - \lambda^* I)) = n - \dim(\text{Img}(A^\dagger - \lambda^* I)) > 0$$
which would imply that...


exponential equation $$\sqrt{(5+2\sqrt6)^x}+\sqrt{(5-2\sqrt6)^x}=10$$

So I have squared both sides and got:

$$(5-2\sqrt6)^x+(5+2\sqrt6)^x+2\sqrt{1^x}=100$$

$$(5-2\sqrt6)^x+(5+2\sqrt6)^x+2=100$$

I don't know what to do now

You don't have to square the equation in the first place.

Let $y = \sqrt{(5+2\sqrt{6})^x}$, then $\frac{1}{y} = \sqrt{(5-2\sqrt{6})^x}$. Hence you have $y + \frac{1}{y} = 10$ i.e. $y^2 + 1 = 10y$ i.e. $y^2-10y+1 = 0$.

Hence, $(y-5)^2 =24 \Rightarrow y = 5 \pm 2 \sqrt{6}$.

Hence, $$\sqrt{(5+2\sqrt{6})^x} = 5 \pm 2\sqrt{6} \Rightarrow x = \pm 2$$

(If you plug in $x = \pm 2$, you will get $5+2\sqrt{6} + 5-2\sqrt{6} $ which is nothing but $10$)


Effect of doubly stochastic matrix on vector norm Let $D$ be a $N \times N$ doubly stochastic matrix, $x$ be a $N$ dimensional vector.

What is the relation between $\Vert Dx \Vert_2$ and $\Vert x \Vert_2$?

In addition if $\Vert x \Vert_2=1$, what can I say about $\Vert Dx \Vert_2$?

It's true that a doubly stochastic matrix $D$ has operator norm 1. But that's not
because of its eigenvalues, because $\|P\|=1$  is false for a general stochastic matrix $P$.

Rather, from the Birkhoff–von Neumann theorem
we know that $D$ is a convex combination of permutation (norm one) matrices,
and hence $\|D\|\leq 1$.

Alternatively, if $D$ is doubly stochastic then $D^* D$ is stochastic and therefore
its eigenvalues are bounded by one in modulus. Therefore $\|D\|=1$.

From here, we have that the largest eigenvalue of a stochastic matrix is $1$. Hence, we have
$$\Vert Dx \Vert_2 \leq \Vert x \Vert_2$$


Allowing for jump discontinuites So I'm considering a definition given in one of my real analysis problem sets and trying to understand it a bit more intuitively.
DF:
$$
\lim_{h\to 0}[f(x+h)-f(x-h)]=0
$$
My reasoning is that, this is essentially the same as continuity EXCEPT that we're allowing for jump discontinuities. Is this correct? I.e this definition allows for functions such as
$f(x)=x, \:\:x\in [-\infty,0) f(x)=x+b \:\: x\geq0$

If so, would it still be OK if x was undefined at $0$? EDIT:[SORRY THIS PART IS FALSE.]

Thanks

Ingvar

The property
$$\lim_{h\to 0}\, [f(x+h)−f(x−h)]=0 \tag{1}$$
is implied by continuity at $x$, but does not imply it. For example, any even function of $f$ satisfies at $x=0$, not matter how ugly it is. The Dirichlet function
$f=\chi_{\mathbb Q}$ satisfies (1) at every rational $x$, though its discontinuities are far worse than jump discontinuity.

This definition tends be giving in the following problem in a few analysis books:

  Suppose $f$ is a real function defined on $\mathbb{R}^1$ which satisfies
  $$
  \lim_{h\to 0}\bigl[f(x + h) - f(x - h)\bigr] = 0
$$
  for every $x\in\mathbb{R}^1$. Does this imply $f$ is continuous?

As your question is written, I am not not sure what you are even asking about; however, if your post was spurred by the question I posed above, the answer is no.

Consider
$$
  f(x) =
  \begin{cases}
    1, & x = 0\\
    0, & x\neq 0
  \end{cases}
$$
Then $f$ is continuous at zero if for every $\epsilon > 0$ there exist a $\delta > 0$ such that $d_Y\bigl[f(x),f(0)\bigr] < \epsilon$ for all $x\in\mathbb{R}^1$ for which $0 < d_X(x,0) < \delta$. For $x\neq 0$, $0 < \lvert x - 0\rvert < \delta$. Then $\lvert f(x) - f(0)\rvert = 1$. Take $\epsilon = 1/2$ so $\lvert f(x) - f(0)\rvert > \epsilon$ and $f$ is not continuous at $x = 0$. For $x\neq 0$, $f(x) = 0$. Now for $h < \lvert x\rvert$, $x + h\neq 0\neq x - h$; therefore, $f(x + h) = f(x - h) = 0$.
$$
  \lim_{h\to 0}\bigl[f(x + h) - f(x - h)\bigr] = 0
$$
For $x = 0$ and $h > 0$, $f(x + h) = f(h) = f(-h) = f(x - h)$ and again the limit is zero.


Binary linear codes and weights Let $C$ be a binary $[n,k]$ linear code. If $C$ has a codeword of odd weight
then the codewords of even weightin $C$ form an $[n,k-1]$ binary linear code. Can you prove that?

Hint: Consider the linear mapping $f$ from $C$ to $GF(2)$ defined by
$$
f:(a_1,a_2,\ldots,a_n)\mapsto a_1+a_2+\cdots+a_n.
$$
Show that this is onto. Apply the rank-nullity theorem (familiar from linear algebra) to it.

Let x be an odd codeword so that the cosets x+E and E are distinct. Given any coset y+E we must have y+E=E if y is even. Otherwise y is odd while x+y is even implying x+E = y+E. Therefore, C/E has size 2 and dimension 1. Therefore dim(E) = dim(C) - 1.


A system of quadratic diophantine equations Find $(p,x,y)$, where $p$ is prime and $x,y$ natural numbers, such that:
$p+1=2x^2$
$p^2+1=2y^2$
A solution to this problem is $(7,2,5)$ and I tried to show that it is the only one, but I didn't get far. Can anyone help?

First of all, rule out $p\in\mathbb \{2,3\}$. Hence, $2\mid p-1$. Then, observe that your equations yield $$p\cdot \frac{p-1}2=(y-x)(y+x)$$ We could have $p\mid y-x$, but since $p>\frac{p-1}2$, this would imply that $y-x>y+x$. Contradiction. Thus, we have $p\mid x+y\implies p\leqslant x+y\implies 2p\leqslant 2(x+y)$. At the same time, we infer that $p-1\geqslant 2(y-x)$.
Add these inequalities to obtain $4x\geqslant p+1\iff 4x\geqslant 2x^2\iff x\in\mathbb \{0,1,2\}$. It is easy to see that $(x,y,p)\equiv (2,5,7)$ is the only solution.

From $p+1=2x^2, p^2+1=2y^2$ we have that $$p(p-1)=2(y-x)(y+x).$$ Since $p$ is prime it is $y-x=1$ or $y+x=p.$

If $y-x=1$ then $p=3$ and there is no solution.
If $y+x=p$ then $p+1=4x=2x^2\implies x=2.$ And thus $y=5,p=7.$


How do you solve this recurrence? I have been trying to practice recurrence relations that can be solved by the master theorem and came across this.

Now the $4^{\textrm{th}}$ problem in that file is :

$$T(n) = 2^n T\left(\frac{n}{2}\right) + n^n.$$

The solution says it can't be solved using Master theorem, which is true. But I want to know how to solve it.

I tried thinking of some substitution but I'm not able to get anywhere since the recurrence contains terms $2^n$ and $n^n$ both. And if I expand the tree, it becomes really messy. Any solutions?

Introducing $U(n)=T(n)/4^n$, one sees that $U(n/2)=T(n/2)/2^n$ hence the recursion over $(T(n))_n$ yields $U(n)=U(n/2)+(n/4)^n$.

Roughly speaking, this means that $U(n)=(n/4)^n+(n/8)^{n/2}+(n/16)^{n/4}+\ldots$ More rigorously, the $\ldots$ hides at most $\log_2n$ terms, each less than $(n/8)^{n/2}$, hence
$$
(n/4)^n\leqslant U(n)\leqslant(n/4)^n+\log_2(n)\cdot(n/8)^{n/2},
$$
which implies
$$
n^n\leqslant T(n)\leqslant n^n+\log_2(n)\cdot(2n)^{n/2}.
$$
Since $\log_2(n)\cdot(2n)^{n/2}\ll n^n$, this yields $\lim\limits_{n\to\infty}T(n)/n^n=1$, hence $T(n)=\Theta(n^n)$.


What is $-1$ to the power of a fraction? If I have any negative number (does not have to be $-1$), how would I determine that value to the power of $1/2$?
I learned that $x^\frac{1}{2}$ is equal to $√x,$ so wouldn't $-1^\frac{1}{2}$ be equal to $i$? Why does the calculator return $-1$?

Try not to worry too much about all the notation, and look at this page, DLMF 6.6, from an online reference of special functions.
Notice that in several items we have "$(-1)^n$" and also one "$(-1)^{n-1}$".  These have parentheses in order to accurately express what is meant, a power of $-1$.  Without the parentheses, the order of operations specifies that the power would happen before the negation, so one would not get a power of $-1$.
If one is typing this on a calculator, there are a number of common errors.
-1^1/2     = -((1/1)^2) = -1
-1^(1/2)   = -(1^(1/2)) = -1
(-1)^1/2   = ((-1)^1)/2 = -1/2

If you want the quantity $-1$ raised to the power $1/2$, you need to enter
(-1)^(1/2)

Depending on your calculator (and possibly on a mode setting on your calculator) evaluation of this expression will produce an error (some form of domain error, since $-1$ is not in the domain of the real square root function) or a result that is equivalent to the complex number $0 + 1\mathrm{i}$ produced by the complex square root function.

There are two square roots of $-1$ and no reason to prefer one of them to the other. You can call one of them $i$ and the other $-i,$ or switch those two roles around so that the one that you called $-i$ before is now $+i$ and vice-versa, and nothing changes. And there are three cube roots of $-1,$ one of those being $-1$ itself and the others $(1\pm i\sqrt3)/2.$ If you want $(-1)^x$ to change in a smooth way as $x$ changes, then you'll need to pick one of those latter two to be the value of $(-1)^{1/3}.$ And what then is $(-1)^{2/3}\text{?}$ Should it be the square of $(-1)^{1/3} = \sqrt[3]{-1}= -1\text{?}$ That would make it $+1.$ Or should it be the square of $(1+i\sqrt3)/2,$ which is $(-1+i\sqrt3)/2\text{?}$


Why do we need approximation methods when we have algorithms to find exact roots? While I was studying numerical methods and optimizations recently, I observed that whenever we find a root to an equation or a system of linear equations, we always find approximate roots. However, we already have algorithms for finding exact roots.

For example, the Gauss-Seidel or Gauss-Jacobi methods of iterative solution tend to find the "most correct" approximate root to the system of linear equations, although we can find exact roots to a system of linear equations through algorithms such as Gauss elimination or Gauss-Jordan method.

  What is the reason to use approximation methods when we can find exact roots?

There are at least two important reasons.

First, iterative methods can be significantly faster, and as there are a lot of problems with big systems (hundreds of thousands or more variables), speed can be important. Also, precise methods usually can't take advantage of sparsity, which is common case too.

Second, we usually use finite-precision floating point numbers, so we have to deal with rounding errors, which tend to accumulate in precise methods more. For example, in Gauss elimination, if you get a row slightly wrong, it will affect all subsequent rows. As in iterative methods the "main part" doesn't change, they are (usually) less susceptible to it.

For polynomials: almost no polynomial's roots can be expressed exactly.  All linear, quadratic, cubic and quartic polynomials can be factored exactly.  The generic case for quintics is similar to that for $x^5 + x + 5$, whose five roots are not expressible using any finite expression of sums, differences, products, quotients, or rational powers of rational numbers.  (They can be expressed using Jacobi elliptic functions, which can only be evaluated exactly for very special arguments.)  For more on this see solvability by radicals in Galois theory.  Generically, for degree above four, nearly all polynomials are not solvable by radicals.  As a consequence, the only way forward is to find approximate roots.

Now to linear systems of equations.

There are two resources that any algorithm requires: time and space.  For matrix algorithms, it is typical to express the complexities as functions of the size of the matrix.  For $n \times n$ matrices, the size is $n$.  Also, real implementations of algorithms can increase or decrease the resource usage by nearly constant multiplicative factors.  (Implementing on this hardware may be twice as fast as that hardware.  Using this representation of the numbers may use ten times as much space as using that representation.)  Consequently, constant multipliers are typically ignored when calculating and reporting time complexity -- the "$2$" in "$2 n^2$" is meaningless when we can get a factor of $2$ just by moving to a different computing device.  We indicate that we are ignoring constant multipliers by using big O notation.  Also, efficiency is largely irrelevant for small problem sizes, we typically think of $n$ as being large.  Consequently, although a detailed accounting of resource usage may show, for instance, usage of $\frac{2}{3}n^3 + \frac{3}{2}n^2 - \frac{7}{6}n$ units of a resource, this is reported as $O(n^3)$ because, for large $n$, the lower order terms are irrelevant and as already noted, the leading coefficient is irrelevant.

The following are widely reported, so I don't provide specific citations.  We report space complexity assuming floating point representations.  (Use of exact representations in the worst case lead to exponential space consumption.)

Gaussian elimination and Gauss-Jordan elimination have time complexity $O(n^3)$ and space complexity $O(n^2)$.

(Gauss-)Jacobi iteration has time complexity $O(n^2)$ and space complexity $O(n^2)$.

Gauss-Seidel has time complexity $O(n^2)$ and space complexity $O(n^2)$.

For these algorithms, space complexity is not a concern.  However, time complexity does vary.  So, suppose we have a problem instance with $n = 10^6$.  (This is not actually so large, but is illustrative.)  Then we can expect the ratio of time required for Gauss or Gauss-Jordan to the time required for Gauss-Jacobi or Gauss-Seidel to be
$$  \frac{(10^6)^3}{(10^6)^2} = 10^6  \text{.}  $$
That is, the approximate algorithms are about a million times faster for this problem.

There are additional considerations.  For instance, we are discussing calculations using floating point numbers.  Such representations have finite precision, so long calculations risk accumulation of error, sometimes to the point that the "solution" returned by the algorithm is garbage.  We capture this by describing for which inputs the algorithm is "stable".  If the algorithm is stable for a particular input, accumulated errors do not dominate the output.  Gaussian and Gauss-Jordan are stable for diagonally-dominant matrices.  If your matrix is not diagonally dominant, then the large multiplications to cancel off-diagonal terms amplify the precision errors in those terms (and the subsequent subtractions can lead to catastrophic cancellation).  Gauss-Jacobi requires the spectral radius of the matrix to be less than $1$ to even converge.  One way to ensure the spectral radius is less than $1$ is to be diagonally dominant.  There are symmetric positive-definite matrices for which Gauss-Jacobi does not even converge, e.g. $(\begin{smallmatrix} 1 & 2 \\ 2 & 1 \end{smallmatrix})$.  Gauss-Seidel converges for positive-definite and for diagonally dominant matrices.  Notice that none of the methods you listed are stable/converge if your matrix is far from diagonally dominant.  (So what do you do if you have such a matrix?  Precondition.)

To summarize: We have these many algorithms because (1) the running time can vary substantially, depending on which algorithm you use and (2) different algorithms have different stability requirements.


Is $72!/36! -1$ divisible by 73? Is $\frac{72!}{36!}-1$ divisible by the number 73?

I am not getting a clue in which direction should I go, though I did small amount of work by converting the above expression in the below given form

$$(1.3.5.7.9...69.71).2^{36} - 1$$

and

$$36!\binom{72}{36} -1$$

I am unable to proceed further.

Let $p=73$. $p$ is a prime number. Thus by Wilson's theorem
$$72! = (p-1)!\equiv -1 \mod p$$

Notice that $\forall 1\le n\le 36$, $73-n \equiv -n \mod p$, thus

$$ \frac{72!}{36!}\equiv (37\cdot 38\cdots 72)\equiv (-1\cdot -2\cdots -36) \equiv (1\cdot 2\cdots 36)(-1)^{36} \equiv (1\cdot 2\cdots 36) \equiv 36! \mod p$$

Suppose for the sake of contradiction that $ \frac{72!}{36!} \equiv 1 \mod p$, then $ 36! \equiv 1 \mod p$ and

$$ 72! \equiv (36!)^2 \equiv 1 \mod p$$

which is not true.

So we can conclude that $\frac{72!}{36!} \mod p$ is not $1$.


The staircase paradox, or why $\pi\ne4$ What is wrong with this proof?

Is $\pi=4?$

This question is usually posed as the length of the diagonal of a unit square.  You start going from one corner to the opposite one following the perimeter and observe the length is $2$, then take shorter and shorter stair-steps and the length is $2$ but your path approaches the diagonal. So $\sqrt{2}=2$.

In both cases, you are approaching the area but not the path length. You can make this more rigorous by breaking into increments and following the proof of the Riemann sum. The difference in area between the two curves goes nicely to zero, but the difference in arc length stays constant.

Edit: making the square more explicit.  Imagine dividing the diagonal into $n$ segments and a stairstep approximation.  Each triangle is $(\frac{1}{n},\frac{1}{n},\frac{\sqrt{2}}{n})$.  So the area between the stairsteps and the diagonal is $n \frac{1}{2n^2}$ which converges to $0$.  The path length is $n \frac{2}{n}$, which converges even more nicely to $2$.

If I were asked this question by a first-year calculus student, then the first thing I would do is write the following on the chalkboard:
$$ \sqrt{dx^2 + dy^2} \ne |dx| + |dy| $$
(This is still a common enough mistake among high school math students, but by the time anyone learns calculus, I hope that they would be aware that it is wrong.)

If you consider any infinitesimal element of the circle, the length is
$$d\ell = \sqrt{dx^2 + dy^2}$$
The only relationship between the circle and the "approximating" curve is that they have the same value of $|dx| + |dy|$, which is not a meaningful quantity when talking about length (at least, as has been pointed out, when you are using a Euclidean metric).  The value of $d\ell$ is not equal for any corresponding infinitesimal elements of the two curves, so there is no reason to believe it will be the same for the whole polygon.


Determine stability of the origin in a system with two zero eigenvalues I need to determine whether the fixed point $x^{*}=0$ of the system $$\dot{x} = 0 \\ \dot{y}=x $$

is attracting, Liapunov stable, asymptotically stable, or none of the above.

For reference, a fixed point $x^{*}$ is said to be attracting if any trajectory that starts within a distance $\delta$ of $x^{*}$ is guaranteed to converge to $x^{*}$ eventually. In contrast, Liapunov stability requires that nearby trajectories remain close for all time. Finally, asymptotically stable means that it is both attracting and Liapunov stable.

Here, if I set up the matrix equation $$\begin{pmatrix} \dot{x} \\ \dot{y} \end{pmatrix} = \begin{pmatrix}0 & 0 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} x \\ y\end{pmatrix}$$

Notice that the trace  of the matrix $A = \begin{pmatrix} 0 & 0 \\ 1 & 0\end{pmatrix}$ is $\tau = 0$, and the determinant $\Delta$ $is$0$ as well.

Moreover, both eigenvalues are equal to $0$. My book says that in the case where both eigenvalues are equal to $0$, the entire plane is filled with fixed points, but what does this tell me about what is going on at the fixed point $x^{*} = 0$?

I even solved the system to get $$x(t) = x_{0} \\ y(t) = x_{0}t+y_{0} $$

But I still do not know how to determine the stability of the origin here. Could somebody please help?

Solutions for this problem are available on the Internet, but they all 1) don't contain any explanation as to why the answers are what they are, 2) disagree with each other about what is going on at $x^{*} = 0$ , and  finally 3) even disagree about what the vector field looks like. Our professor didn't really explain to us very well how even to draw vector fields, so I would appreciate if whoever answered this question could please explain how to do so (by hand).

Thank you.

A hand drawn graphical representation of a vector field is constructed by choosing a collection of points in the plane an drawing a short line segment centered on the chosen points that has a slope equal to $\frac{dy}{dx} = \frac{\dot y}{\dot x}$. In your case, all of the slopes away from the $y$-axis are undefined(vertical). The slopes along the $y$-axis are also technically undefined but something drastically different is happening there.

However, consider what happens if your initial conditions are along the $y$-axis. The solution stays fixed at $y_0$. A glance at your solution verifies this to be true. How is this fact related to the stability criteria you have proposed? In other words, if you are displaced a small amount away from the fixed point at the origin in the $y$-direction, what happens?

If you are displaced in any other direction then $x_0$ would not be $0$. What are the properties of your solution now? Look at the asymptotic behavior as $t\to\pm\infty$.

You will ultimately need to classify the stability properties in these two different situations.

Linear systems are very well understood systems. Majority of books state well known facts about linear systems and leave the proofs and any further explanations  about these facts for the readers. You can pick up any control systems undergrad textbooks and you will see why for example, linear systems are stable if and only if the eigenvalues of the system are negative values. If at least one of the eigenvalues is positive, the system is unstable.  If the linear system is stable then it is asymptotically stable.


Prove or disprove: If $n^3$ is odd then $n$ is odd. If $n^3$ is odd, then $n$ is odd.

I need to prove or disprove by means of counterexample why this is true or false.

$\forall x P(x) = x^3$, $x = 1,3,5,7,9$

I am having a very difficult time finding a way to prove this by counterexample!

Suppose $n^3$ is odd, but $n$ is not odd. Then $n$ must be even. The product of any two even numbers is even, so $n^2$ is even. Then $n(n^2)=n^3$ is the product of two even numbers again: and so $n(n^2)=n^3$ is even. This contradicts the assumption that $n^3$ is odd, and so $n$ is not even. So $n$ must be odd.

if $n$ is even, $n^3$ is even.
if $n$ is odd, $n^3$ is odd.

Therefore $n$ is odd iff $n^3$ is odd.


Find possible distances between C and E A, B, C, D and E lies on a line, not necessarily in that order.
  Distance between A and B is $2$, distance between B and C is $3$, distance
  between C and D is $5$ and distance between D and E is $4$.  Find  the possible
  distances between C and E?

I find this type of problems difficult to solve. I don't understand clearly about the orders. In this particular case, I think if A, B, C, and D are placed in order and E is placed in both sides of D, then two possible distances are possible between C and E, which is $9$ and $1$. But what if possible distances between A and E are to be found? Can anyone clearly elaborate the process and concepts behind these line problems?

Let us denote by lower case letters $a,b,c,d,e$ the abscissas of points $A,B,C,D,E$ resp.

Two basic observations about this issue:

it is "up to a translation" which allows to take $E$ as the origin, i.e., $e=0$.
it is "up to a symmetry", which allows $D$ to be set at abscissa $d \geq 0$.

Consider the two last constraints, the other constraints being useless.

$$\begin{cases}|c-d|&=&5\\d&=&4\end{cases} \ \ \Rightarrow \ \ |c-4|=5.$$

Thus 2 cases:

$c=-1$; thus $CE=1$.
$c=9$; thus $CE=9$.

Edit: Here is a tree explaining how the other possible positions of points $A,B,C$ can be found (truly speaking,  it is not exactly a tree because two branches meet in a "leaf"...). Taking a branch in the upwards direction like $(A_3,B_1,C_1,D)$ provides a solution ($E$ being fixed).

given
equation1 $b-a = 2$

equation2 $c-b = 3$

equation3 $d-c = 5$

equation4 $e-d = 4$

need to find $e - c$ and $e - a$
solution:

add equation3 and equation4 and you get $e-c = 9$

add all of them and you get $e - a = 14$


Characterization of polynomial injection from Q to Q? I want to know if we can find (or characterize) all the polynomials $f(x) \in \mathbb{Q}[x]$ that induces an injection $f : \mathbb{Q} \rightarrow \mathbb{Q}$ by evaluation.

Some examples are $x, x^{3}$, and I would like to know how to find all of them. However, please don't hesitate to let me know any useful list of examples that narrow the possibilities of $f(x)$ or references that give ways to attack this problem. Thank you.

When investigating $f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots +a_0$ with $a_n\ne0$ for injectivity on the rationals, you may scale $f$ vertically to ensure $a_n=1$, translate horizontally to ensure $a_{n-1}=0$, and translate vertically to ensure $a_0=0$.
Lastly, we can scale horizontally to ensure that $a_{n-2}$ is a square-free integer (or zero).
Thus wlog. $f(x)=x^n+a_{n-2}x^{n-2}+\cdots +a_1x$ with $a_{n-2}$ a square free integer or zero.

In degree $1$, we thus get $f(x)=x$, which is injective.

In degree $2$, we get $f(x)=x^2$, which is not injective.

In degree $3$, we get $f(x)=x^3+ax$.
If $a\ge 0$, this is injective.
Otherwise note $f(x)-f(y)=(x-y)(x^2+xy+y^2+a)$, so $f$ is injective iff there is no $z=x-y\omega\in\mathbb Q(\omega)$ with $x\ne y$ and $N(z)=|z|^2=-a$, where $\omega=-\frac12+\frac{\sqrt 3}2i$ is a primitive third root of unity.
The condition $x\ne y$, i.e. $z\notin(1-\omega)\mathbb Z$ can be ignored because if $N(z)=-a$ then also $N(\omega z)=-a$.
Consider the prime decomposition of $-a=|a|$ in the principle ideal domain $\mathbb Z[\omega]$.
If $p\in\mathbb Z$ is an inert prime in our extension (that is $p\equiv 2\pmod 3$), then $p|-a$ implies $p|z$, hence $p^2|-a$, contradiction.
If on the other hand all prime factors $p$ are not inert (i.e. split, $p\equiv 1\pmod 3$; or ramify, $p=3$), then taking one of the primes above each $p$ and multiplying these gives us $z$ with $N(z)=|a|$. (This includes the case $a=-1$ that is trivial anyway).
Thus $f(x)=x^3+ax$ with $a$ square-free is injective iff $a\ge 0$ or $a$ is divisible by at least one prime $\in\{2,5,11,17,23,29,41,47,\ldots\}$.

In degree $4$, we get $f(x)=x^4+ax^2+bx$ with $a$ squarefree.
This is even, hence not injective, if $b=0$.
We have
$$\frac{f(x)-f(y)}{x-y}=(x^3+x^2y+xy^2+y^3)+a(x+y)+b=(x+y)(x^2+y^2-a)+b$$
It is again an interesting problem whether this expression can be made $=0$ or not. For example, if $6|a$, $2\not |b$ and $3\Vert b$, we note that $x+y$ or $x^2+y^2-a$ must be divisible by $3$. If the latter, then $3|x$ and $3|y$, hence $f(x)\ne f(y)$ because $9\not | b$. And if the former, then $x^2+y^2-a=2x^2-a$ is even, but $b$ is not. We conclude that $f$ is injective. This looks more like a trick than a theory, but I'm sure something nice can be done - just less easy than in the quadratic case, not to mention degrees $\ge 5$.

For real polynomials, it must pass the horizontal line test. A real polynomial is monotonic iff it is always increasing or always decreasing. Thus, they are the integrals of polynomials that are non-negative or non-positive. So the question is whether a real polynomial is always monotone if its restriction to $\Bbb{Q}$ is monotone under $\Bbb{Q}$'s order.

If a real polynomial intersects a horizontal line at least twice, there is a local minimum or maximum between two of those points, and the height of such a point together with the height of the line give an interval of values which are visited at least twice by the function.

The rationals are a dense subset of the reals, meaning every neighborhood of a real number has at least one rational. Therefore, that interval of values that are repeated contains at least one rational. Therefore if a real polynomial is not monotonic, then the rational polynomial is not monotonic. Therefore if a rational polynomial is monotonic, then the real polynomial is monotonic.

Clearly every monotonic real polynomial is monotonic as a rational polynomial. Therefore a polynomial is monotonic over the rationals iff it is monotonic over the reals iff it passes the horizontal line test.


How should one approach this pde? Say I have $u=u(x,y)$ and I am facing $u_x=-yu_{xy}$. I tried to integrate both side wrt to $x$ but that was without any luck, any help is appreciated!

Try solving $v=-yv_y$ then solve $u_x=v$

When taking the partial derivative of a function, f(x,y), with respect to x, you treat y as a constant.  So when you integrate with respect to a single variable, you treat the other variable as a constant.  One caveat: the "constant of integration" might, in fact, be a function of that other variable.

Here you have $u_x= -yu_{xy}= -y(u_y)_x$.  Integrating with respect to x, $u= -yu_y+ c(x)$ where c(x) can be any differentiable function of x.  We can write that as $-yu_y+ u= c(x)$ and treat it as an ordinary differential in the single variable y with c(x) a constant (with respect to y).  That is a linear equation first order equation and if you are taking partial differential equations you should know how to find an "integrating factor" for a linear first order equation.


${\log}_{a}{x}\neq {\int}^{x}_{1}{\frac{1}{t}}dt$ In most calculus textbooks, $\ln{x}$ is defined to be ${\int}^{x}_{1}{\frac{1}{t}}dt$. Some textbooks validate this definition by demonstrating that this function $\int^{x}_{1}{\frac{1}{t}}dt$ has all the properties of a logarithmic function (I've included pictures of this). I'm skeptical to this particular approach, since we could also define ${\log}_{a}{x}={\int}^{x}_{1}{\frac{1}{t}}dt$. We can still show that the laws of logarithms are properties of this integral, it's also obvious how the algebra will work out. And that means we've justified our claim?

Hell no! The derivative of ${\log}_{a}{x}$ is $\frac{1}{x}{\log}_{a}{e}$. Isn't this approach erroneous then? How then, could we show that this integral does not equal ${\log}_{a}{x}$? We could try showing that some of the properties of the logarithmic functions ($a\neq{e}$) do not hold for ${\int}^{x}_{1}{\frac{1}{t}}dt$. But how do we go about it?

img-1 img-2

Your critique is completely correct: the properties shown in those proofs are not enough to distinguish between $\ln x$ and $\log_a x$ for any $a>1$. Indeed, all of the proofs would go through for the function $\int_1^x \frac Ct\,dt$ for any positive constant $C$ as well. (This is secretly the same ambiguity in disguise....)

So yes, you're right that this is not a proof that $\int_1^x \frac 1t\,dt$ must equal $\ln x$ instead of some other $\log_a x = \frac1{\ln a}\ln x$. To be fair, the textbook didn't claim it was such a proof—only that the integral does have logarithm-like properties.

A proof that we really do get $\ln x$ itself, instead of some multiple of it, would need to use some property of the number $e$—which itself depends on what definition of $e$ you choose. One common definition is of all the exponential functions $a^x$ with $a>1$, the number $e$ is the only base $a$ with the property that $\frac d{dx}(b^x)\big|_{x=0} = 1$.

From this one can derive (using the relationship between the derivatives of a function and its inverse function) that $e$ is the only base $a$ for which the inverse function $\log_a x$ satisfies $\frac d{dx} \log_a x\big|_{x=1}=1$. And this additional property is enough to show that $\int_1^x \frac1t\,dt$ is equal to $\log_e x=\ln x$, since the derivative of $\int_1^x \frac1t\,dt$ equals $\frac 1x$ by the fundamental theorem of calculus.

The function $t \mapsto \to \frac 1t$ is continuous at  the interval $ (0,+\infty)$, it has then many antiderivative at $(0,+\infty)$.
The antiderivative  which takes $ 0 $ at $ x=1 $ and $ 1 $ at $ x=e $ is Nepierian logarithm $ (\ln) $.

The one which takes $ 1$ at $x=a$ is $\log_a$.

$$\ln(x)=\log_e(x)=\int_1^x \frac{dt}{t}$$

$${\log_a(x)=\frac{\displaystyle\int_1^x\frac{dt}{t}}{\displaystyle\int_1^a\frac{dt}{t}}}$$


Conditional Probability: $P(X|Y\leq y)=$ $\sum\limits_{k=1}^{y} P(X|Y=k)$? Suppose $X \sim Binomial (Y,\delta)$.
For the random variable $X$ can I compute the following conditional probability as follows?
$P(X=x|Y\leq y)=$ $\sum\limits_{k=1}^{y} P(X=x|Y=k)$, where Y is a discrete random variable having the value of positive integers.

Yes, you can, provided that the summands are disjoint, i.e. that $$
\left( {X \cap Y = k} \right) \cap \left( {X \cap Y = j} \right) = \emptyset \quad \left| {\;k \ne j} \right.
$$


How to split a quartic into two quadratics? I have a quartic in $\Bbb Z[x]$ with very large coefficients that I know splits into two quadratics in $\Bbb Z[x]$. What is the best way to do find the quadratics?

A general method always available is to first factor the polynomial $F(x)$ modulo some prime $p$ (possible a small one), and then Hensel lift that to a factorization modulo progressively higher powers of that prime. Given that you know there exists a factorization over $\Bbb{Z}$, the sequence of those modulo $p^n$ factorizations will stabilize when $n$ is large enough, and you get a fairly good idea of the actual factors (it is simple to verify a candidate factorization).

For the Hensel lifting to work out, the two factors modulo $p$ should be distinct. Unless the two quadratic factors your polynomial has are equal they will also be distinct modulo most primes. You can detect this by checking whether $\gcd_{\Bbb{Z}[x]}(F(x),F'(x))=1$ or not. A repeated factor of $F(x)$ will show as a common factor of $F(x)$ and $F'(x)$.
For simplicity it may be better not to use a prime $p$ such that your polynomial also has linear factors modulo that prime. You can probably use linear factors as well, but if your pair them up incorrectly, then the Hensel lifting may not converge. If you know that the quadratic factors of $F(x)$ are irreducible over $\Bbb{Z}$, then they will remain so modulo some primes (Note: this does not hold for polynomials of degree $>2$). I admit to not being certain what is best here, if you get four distinct linear factors modulo your chosen $p$. May be it is best to try out lifting all the three quadratic $\times$ quadratic factorizations that you get out of that?
To find the factorization modulo $p$ I would start with Cantor-Zassenhaus algorithm, because it is simple. Any irreducible linear or quadratic polynomial with coefficients in $\Bbb{Z}_p$ is a factor of $x^{p^2}-x=x(x^{p^2-1}-1).$
Furthermore, a factor with the property that its zeros (in the field $\Bbb{F}_{p^2}$) are non-zero squares will also be a factor of $Q(x):=x^{(p^2-1)/2}-1$. With a little bit of luck the zeros of one factor of $F(x)$ are squares and those of the other are not. The zeros of an irreducible quadratic either both are squares or both are non-squares, so this is a 50-50 chance. If that happens, then the factor with zeros in $(\Bbb{F}_{p^2}^*)^2$ is the common factor $\gcd_{\Bbb{F}_p[x]}(F(x),Q(x))$, and can be calculated efficiently with Euclid's algorithm. The other factor can then be found by long division.
To improve the odds of success you can do the following modifications (this is the non-deterministic part in C-Z). Instead of calculating just $\gcd(F(x),Q(x))$ you can also calculate $\gcd(F(x-a),Q(x))$ for several $a\in\Bbb{Z}_p$. If $P(x)$ is an irreducible quadratic factor of $F(x)$ modulo $p$, then for a random choice of $a$ there is next to no correlation between "the zeros of $P(x)$ are squares" and "the zeros of $P(x-a)$ are squares". Therefore, statistically speaking, each try with a different $a$ halves your probability of failure. Of course, $P(x-a)$ is a factor of $F(x-a)$, iff $P(x)$ is a factor of $F(x)$.

Example.

  Find the factors of $F(x)=x^4+2x^3-123x^2+524x-341$

(I know that this too small to be of interest to you, and here trial-and-error would quickly do it. This is just for demonstration).

First we check that $\gcd_{\Bbb{Q}[x]}(F(x),F'(x))=1$, so there are no repeated factors. I skip the runs of (generalized) Euclid's algorithm.

Let's try to factor $F(x)$ modulo $p=5$. First try with $a=0$.
$$
\gcd\nolimits_{\Bbb{F}_5[x]}(F(x),x^{12}-1)=x^4+2x^3+2x^2+4x+4\equiv F(x)\pmod 5.
$$
This was no good. Looks like all the zeros of $F(x)$ are squares in $\Bbb{F}_{25}$. Let's try instead
$$
F(x+1)\equiv x^4+x^3-x^2+3x+3\pmod5.
$$
We get
$$
\gcd\nolimits_{\Bbb{F}_5[x]}(F(x+1),x^{12}-1)=x^2+x+1.
$$
That's more like it! We know that one of the modulo $5$ factors of $F(x)$
is $$G_1(x)=(x-1)^2+(x-1)+1\equiv x^2+4x+1\pmod5.$$ The other factor is gotten by long division, $H_1(x)=F(x)/G_1(X)=x^2+3x+4$, so we got
$$
F(x)\equiv G_1(x)H_1(x)\pmod 5.
$$

An aside: Why $p=5$? Modulo $p=2$ $F(x)\equiv(x^2+x+1)^2$ is a square, and modulo $p=3$ we have $F(x)\equiv(x+2)^4$. Neither of those primes can be used, because Hensel lifting requires coprime factors. The smaller the prime, the higher the chance of repeated factors.

On with the Hensel lifting. Next we want to find a factorization of $F(x)$ modulo $5^2=25$. Because $\gcd_{\Bbb{F}_5}(G_1(x),H_1(x))=1$ Hensel's lemma guarantees the existence of monic polynomials $G_2(x), H_2(x)$ such that $G_2(x)H_2(x)\equiv F(x)\pmod{25}$, and $G_1\equiv G_2, H_1\equiv H_2\pmod5$.
These are found as follows. Interpreting the polynomials $G_1,H_1$ to have integer coefficients we are looking for linear polynomials $K_2,L_2$ with integer coefficients such that
$$
F\equiv(G_1+5K_2)(H_1+5L_2)\equiv G_1H_1+5(K_2H_1+L_2G_1)\pmod{25}.
$$
Because
$$
F-G_1H_1=-5x^3-140x^2+505x-345=5(-x^3-28x^2+101x-69)\equiv 5(4x^3+2x^2+x+1)\pmod{25}
$$
we want to find $K_2,L_2\in\Bbb{F}_5[x]$ such that
$$
K_2H_1+L_2G_1=4x^3+2x^2+x+1:=U(x)\in\Bbb{F}_5[x].
$$
Here $U(x)\equiv 3x\pmod{G_1(x)}$ and $U(x)\equiv 1\pmod{H_1(x)}$, so we
want $L_2G_1\equiv 1\pmod{H_1}$ and $K_2H_1\equiv 3x\pmod{G_1}$.

A run of the Extended Euclid's algorithm in the ring $\Bbb{F}_5[x]$ gives us the identity
$$
1=\gcd(G_1,H_1)=(2x+2)G_1+(3x+1)H_1,
$$
and we can read the inverse of $G_1$ modulo $H_1$ (resp. inverse of $H_1$  modulo $G_1$) from this.
Therefore
$$
K_2\equiv 3xH_1^{-1}=3x(1+3x)\equiv2x+1\pmod{G_1}.
$$
and
$$
L_2\equiv 1\cdot G_1^{-1}=(2x+2)\equiv 2x+2\pmod{H_1},
$$
This gives us the lifts
$$
G_2(x)=G_1(x)+5K_2(x)=x^2+14x+6
$$
and
$$
H_2(x)=H_1(x)+5L_2(x)=x^2+13x+14.
$$
As a check we calculate
$$
F-G_2H_2=-25x^3-325x^2+250x-425,
$$
and see that it is, indeed, a multiple of $25$.

Here we can either continue the lifting to find a factorization modulo $5^3=125$, or do a bit of experimenting. I skip the lifting, and simply observe that
$$
(G_2-25x+25)(H_2-25)=F,
$$
so the factorization is
$$
F(x)=(x^2-11x+31)(x^2+13-11).
$$
A big tip off (to anyone doing pencil and paper work) in the last step is the constant term $-341=-11\cdot31$ of $F(x)$.

Can we assume that all resulting coefficients are integers?  If so, use the rational root theorem to identify a list of possible roots and test them using the factor theorem.  Once you found one root, you can divide it from the quartic to get a cubic.  Repeat one more time and you have your quadratic.  It's not the most efficient if your coefficient are really big.


Straight line , gre prolem $170$ score hard What is the distance between the two straight line represented by the equation

$3x+4y=10$ and $6x+8y=10?$ $$A>1$$ $$B>2$$ $$C>\frac43$$ $$D>\frac12$$ $$E>\frac52$$

I try to solve it , firstly find intercept of both line and then find mid point between of them ,and calculate distance between both line , suggest me where I m wrong

If two lines intersect, then the distance between them is $0$. Otherwise they're parallel and have the same slope, which means the lines can be written as

$ax + by = c$      and
$ax + by = d$

The distance between the lines is then $$\frac{|c-d|}{\sqrt{a^2+b^2}}$$

In your case the two lines are

$3x + 4y = 10$      and
$3x + 4y = 5$

so the distance between them is $\frac{|10-5|}{\sqrt{3^2+4^2}} = 1$.

Since these two lines are parallel lines $( m_{1}=m_{2})$ they would never meet.But their interceptions of Y axis is the constant distance they would maintain.

Just measure that distance $$C_{1}-C_{2} = 2.5-1.25= 1.25 $$
So the ans choice is $A ,>1$.
its not greater than $1.5,1.33,2$ or $2.5$.$(B,C,E)$ though it is greater than $0.5 (1/2)$.


To Prove an undecidable language on halting I am student learning Computational Complexity this semester. The text book is Sanjeev Arora et al. Computational Complexity, Cambridge University Press.
I cannot solve the first problem in Chapter Three(p.77), which may be probably disappointing.
The problem is as follow:

Show that the follow language is undecidable:
{M|M is a machine that runs in $100n^2+200$ time}.

You can reduce the halting problem to your problem. Given a Turing machine $M$ and input $z$, let us design a new machine $N$, which on input $y$, first runs $M$ on input $z$ for $|y|$ steps, and if this doesn't halt yet, then $N$ halts, but if $M$ does halt, then $N$ counts up to $|y|^3$ and then halts. That is, if $M$ doesn't halt on $z$, then $N$ halts quickly, but if $M$ does halt on $z$, then $N$ takes a long time on large input.

Thus, $M$ fails to halt on $z$ if and only if $N$ runs in $100n^2+200$ time on all input of size $n$. So if we could decide the latter property, then we could decide the halting problem, which is impossible.

This argument actually shows more, namely, that the complement of the halting problem is $1$-reducible to the running-in-time-$f$ problem.

(A similar argument could make use of Yuval's suggestion, using the halting-on-empty-string problem instead of the halting problem, which would eliminate the need to consider nontrivial $z$.)

I am wondering if this is a correct answer:

Suppose input x that is provided to Turing machine M is of infinite length and therefore n is infinite. Then for every every pair M and x, the problem becomes an instance of the halting problem and hence is unsolvable.


Solve $4^{9x-4} = 3^{9x-4}$ I am having some trouble trying to solve

$$4^{9x-4} = 3^{9x-4}$$

I tried to make each the same base but then I'm becoming confused as to what to do next.

These are the steps I took:

$$\begin{align}
4^{9x-4} &= 3^{9x-4} \\
\log_4(4^{9x-4}) &= \log_4(3^{9x-4}) \\
\end{align}$$

Where do I go from there?

Thanks!

Note that your equation is equivalent to
$$
\frac{4^{9x - 4}}{3^{9x-4}} = 1
$$
or
$$
\left(\frac{4}{3}\right)^{9x-4} = 1.
$$

Gerry said correctly. Can you solve it for $Q$? Now if $Q \in \mathbb{N}^0$ then the only solution is for $Q=0$. Since $4>3$ it follows that for  $Q \in \mathbb{N}^0$ and $Q>0$ it is true that $4^Q>3^Q$. Actually we can generalize that and we can say that for $Q>0$ and $Q\in\mathbb{R}$ it is still true.

Now for $Q<0$ you can write your equation in this way
$$
\frac{1}{4^{|Q|}} = \frac{1}{3^{|Q|}}
$$
and being $1/4<1/3$ you get the opposite of what we discussed before. That means that the only solution is $Q=0$ and that means $9x-4=0$ or $x=4/9$ as user1772257 has pointed out.

Does it help you?


Binomial expansion infinite series: why need form $a^n(1+\frac{b}{a}x)^n$? I suppose my question is about limits and infinities. I have been considering the expansion of $(a+bx)^n$ for negative and fractional $n$, and my text book says to always factorise out the $a^n$ like so:

$(a+bx)^n =a^n(1+\frac{b}{a}x)^n= a^n[1+n\frac{b}{a}x+\frac{n(n-1)}{2!}(\frac{b}{a}x)^2+...]$

And then the expansion is valid for $|\frac{bx}{a}|<1$

My question is, why is the $a$ term involved in thevalidity requirement? Why is it incorrect to simply expand the binomial as

$(a+bx)^n = a^n+a^{n-1}n(bx)+\frac{a^{n-2}n(n-1)}{2!}(bx)^2+...]$

and say it is valid for $|bx|<1$?

My question is, why is the $a$ term involved in the validity requirement?

The requirement for convergence of this series comes from the ratio test. The absolute value of the ratio of consecutive terms of your series is $$\left|\frac{\binom{n}{k+1}\color{red}{a^{n-k-1}}(bx)^{k+1}}{\binom{n}{k}\color{red}{a^{n-k}}(bx)^k}\right|,$$ or more simply $$\left|\frac{n-k}{1+k}\color{red}{a^{-1}}bx\right|.$$ Take note of the coloured parts. That shows you why $a$ does not disappear from the condition.

This is first of all a matter of book-keeping. The $(1+bx/a)^n$ is
considered a geometric series
$$
(1+y)^n=\sum_{i\ge 0} \binom{n}{i}y^i
$$
where $y=bx/a$ is the free variable, and where
the radius of convergence is known to be $|y|<1$. So instead of
remembering a lot of different subcases of how to approach this,
only a single criterion (parameter) comes into play.


how to solve $\int\frac{x^2}{x^2+1}dx$ by using series I want to solve $\int\frac{x^2}{x^2+1}dx$ by using series, but I did something wrong.
Correct solution:
\begin{align*}
\int\frac{x^2}{x^2+1}dx &= \int\frac{(x^2+1)-1}{x^2+1}dx \\
&= \int\left(1-\frac{1}{x^2+1}\right)dx\\
&= x-\arctan(x)+C\\
&= x-\left(x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}-\frac{x^{12}}{12}+\cdots\right)+C\\
&= C+\frac{x^3}{3}-\frac{x^5}{5}+\frac{x^7}{7}-\frac{x^9}{9}+\frac{x^{12}}{12}-\cdots
\end{align*}
My wrong solution:
\begin{align*}
\int\frac{x^2}{x^2+1}dx &= \int\frac{1}{1+(\frac{1}{x^2})}dx\\
&= \int\frac{1}{1+u}dx\text{ ; }u=\frac{1}{x^2}\\
&= \int\left(1-u+u^2-u^3+u^4-\cdots\right)dx\text{ ; }\frac{1}{x+1}=1-x+x^2-x^3+x^4-\cdots\\
&= \int\left(1-\frac{1}{x^2}+\frac{1}{x^4}-\frac{1}{x^6}+\frac{1}{x^8}-\cdots\right)dx\\
&= C+x+\frac{1}{x}-\frac{1}{3x^3}+\frac{1}{5x^5}-\frac{1}{7x^7}+\cdots\\
\end{align*}
What did I do wrong?
Why didn't I get the correct answer?

Both series are good, but for different domains, Note that when we use this form of binomial expansion:
$$(1+y)^{-1}$$
we require $|y|<1$ and so in the first series it is valid for the domain of the arctan series, whilst the second one is valid for $|x|>1$ which is why there is a difference.

One thing to note is when you integrate make sure it is wrt the correct variable. if you make a substitution $u=f(x)$ you must calculate $du$

$$\frac{x^2}{1+x^2}=1-\frac1{1+x^2},$$ which integrates as $x-\arctan x$.
Or, using Taylor (or a geometric summation),
$$1-1+x^2-x^4+x^6-\cdots$$
which integrates as
$$c+\frac{x^3}3-\frac{x^5}{5!}+\frac{x^7}{7!}-\cdots$$


If G is a group such that $(a.b)^{2}=a^{2}.b^{2}$ for all a and b,Then show that G is abelian This is problem from I.N Herstein Page 35 Q3 .How should i start doing this ?Hints ? Thanks

In groups, you can "cancel", as long as you do it from the same side.

Explicitly:

$ac = bc \implies a = b$, and $ab = ac \implies b = c$

Proof:

$ac = bc \implies (ac)c^{-1} = (bc)c^{-1} \implies a(cc^{-1})= b(cc^{-1}) \implies ae = be \implies a = b$

$ac = bc \implies a^{-1}(ac) = a^{-1}(bc) \implies (a^{-1}a)b = (a^{-1}a)c \implies eb = ec \implies b = c$.

Now you are given that $(ab)^2 = a^2b^2$, that is:

$a(ab)b = a(ab)b$. Use the above.


Prove that the ratio of lengths of parallel segments is invariant under affine trasnformations The complete question is as follows:

  Prove that under an affine transformation the ratio of lengths on
  parallel line segments is an invariant, but that the ratio of two
  lengths that are not parallel is not.

Now, the way I was going to prove is the following but I cannot find a way to continue, so maybe I'm missing something.

We have an affine transformation in the form:
$$H = \begin{matrix}
        a & b & x \\
        c & d & y \\
        0 & 0 & 1 \\
        \end{matrix}$$
I deleted the previous wrong stuff which I had written previously. Now this should be the correct definition of affine transform and clear the confusion.

Now, let's assume we have two lines $l_1$ and $l_2$ and we pick two points lying on each one of them: $p_1$, $p_2$ on $l_1$ and $p_3$, $p_4$ on $l_2$. We calculate the distance of each pair of points:
$$d_1 = \sqrt{(p_{1x} - p_{2x})^2 + (p_{1y} - p_{2y})^2}$$
This is the distance between the points on the first line, we can then calculate the distance $d_2$ between the points on the second line and then the ratio $d_1 / d_2$.

Then I thought I could apply the transformation $H$ to the points and calculate the new distances and thus the new ratio. Constraining the lines to be parallel should now make the ratios equal and prove the sentence. I'm pretty sure this procedure is indeed correct conceptually but I find it very hard to go on since the resulting expressions of the ratios are not that simple (ratios of square roots). Is there a better/simpler way to achieve the same result?

Your $H$ is a linear transformation, not an affine one. Write $H(x) = Ax + b$ with $A\in\mathbb R^{2\times 2}, b\in\mathbb R^2$ instead. Using this directly shouldn't be too hard, noting that the things you describe are given by
$$p_1-p_2 = \lambda (p_3-p_4)$$
and you have to show that
$$H(p_1)-H(p_2) = \lambda (H(p_3)-H(p_4))$$


Products of independent random variables. I want to give a little heads up that this question is very similar to Product of independent random variables.

  Let $X_1,X_2,\ldots,X_d$ be independent r.v.'s with distributions $$P(X_i=1)=P(X_i=-1)=\frac{1}{2}\quad\tag{*}$$. For each $S \in [d]$, define $Y_S = \prod\limits_{i\in S}X_i.$ Show that the variables $\{Y_S\}$ are pairwise independent.

In the other question it has been shown show that $(Z_i)_{i=1}^m$ are  mutually(jointly) independent where $Z_i = X_1X_2\ldots X_i$. The key distinction between the questions is that the sets of $[d]$ that are used to take the product are different and pairwise independence is required instead of joint mutual independence.

Let $T\gt S$, then $P(Y_T=1|Y_S)=\frac{1}{2}=P(Y_T=1)$.  The point being that the product of $X_i$ for $i\in T\ and\ i\notin S$ is independent of $Y_S$.


mapping cylinder contractible iff $H_n(f):H_n(X)\to H_n(Y)$ is an isomorphism The mapping cylinder will be defined as $Z_f=X\times[0,1]\coprod Y/\sim$, where $\sim$  is defined by $(x,1)\sim f(x)$.

Let $f:X\to Y$ a continuous map between topological spaces and the map $i:X\hookrightarrow Z_f$ identifies $X$ with $X\times \{0\}\subset Z_f$ is the inlusion. $R$ is a ring. I want to know

$\forall n\in\mathbb{N}_0\; H_n(f;R):H_n(X;R)\to H_n(Y;R)$ is an isomorphism iff $\forall n\in\mathbb{N}_0 \;H_n(Z_f,X)=0$

Here we consider the singular homology. I don't know how to prove this, sorry. Maybe for the direction $\Leftarrow$ we can consider a map of pairs get a long exact sequence. One of the first thoughts I have that the chain complex $(C_n(Z_f,X),d_n)_{n\in \mathbb{N}_0}$ is contractible (identity is chain homotopic to the zero map). But I don't know why it could be useful.

How to prove the statement? Any help is appreciated. Regards.

Consider $X \rightarrow Z_f \rightarrow (Z_f, X)$. Hint: $Z_f \simeq Y$.


How many times can $p$ divide $F_n$? Given a prime $p$ and a number $n$ (or perhaps just an upper bound $x$ with some unknown $n\le x$), trivially one has
$$
\operatorname{ord}_p F_n\le\frac{\log F_n}{\log p}\approx\frac{n\log\varphi}{\log p}
$$
where $F_n$ is the n-th Fibonacci number and $\operatorname{ord}_qm$ is the greatest $k$ such that $q^k|m.$ I'm looking for a less trivial bound, any suggestions?

It seems that
$$
\operatorname{ord}_p F_n\stackrel{?}{\le}2+\frac{\log(n/3)}{\log 2}
$$
which I believe governs $\operatorname{ord}_2F_n.$ I don't have a proof but this is probably not hard to show. On the other hand I have no idea how to show that this works for all primes $p$, even though they 'should' be smaller.

Since the Fibonacci numbers grow exponentially, it's hard to work with numbers as big as $F_n$ directly, and probably $p^{\operatorname{ord}_pF_n}$ is much smaller than $F_n$. I saw sequence A135939 in the OEIS which unfortunately doesn't have useful information that I could see.

The Fibonacci entry point $n_p$ is the least number with $p|F_{n_p}.$ Unless $p$ is a Wall-Sun-Sun prime, $p^2$ does not divide $F_{n_p}$. $n_p\le p+1,$ with $p$ dividing either $p+1$ or $p-1$ unless $p=5$.

There are four cases to consider. If $p=2$ then either $\operatorname{ord}_2(F_n)\le3$ unless $12|n$ in which case
$$
\operatorname{ord}_2(F_n)=2+\operatorname{ord}_2(n)\le2+\frac{\log(n/3)}{\log2}
$$
(see [1] for details). Checking up to 6 verifies that this bound holds for all $n$.

If $p=5$ then
$$
\operatorname{ord}_5(F_n)=\operatorname{ord}_5(n)\le\frac{\log n}{\log 5}.
$$

Aside from these special cases, $\operatorname{ord}_p(F_n)$ is 0 if $n_p\not|n$ and $\operatorname{ord}_p(n\cdot F_{n_p})$ otherwise, see section 3 in [1]. This forms the basis for the remaining steps.

If $p$ is a Wall-Sun-Sun prime then at worst $F_{n_p}=p^e$ for some $e$. Since $n_p\le p+1,$
$$
\operatorname{ord}_p(F_p)\le \frac{\log F_{p+1}}{\log p}+\frac{\log\left(n/(p+1)\right)}{\log p}\sim\frac{\log n}{\log p}.
$$

In the non-Wall-Sun-Sun case ($p\not\in\{2,5\}$), we can do better. A number $n\le x$ could be, in the worst case, $n_pp^e$ with $F_{n_p}=p$ so that $\operatorname{ord}_p(F_p)=1+e,$ yielding
$$
\operatorname{ord}_p(F_p)\le1+\frac{\log\left(\frac{n}{\operatorname{round}\left(\frac{\log(p\sqrt5)}{\log\varphi}\right)}\right)}{\log p}<1+\frac{\log n-\log(2\log p)}{\log p}.
$$

There are no Wall-Sun-Sun primes less than $1.5\times10^{17}.$ [2] This means that unless $x$ is larger, you can use the better bound.

[1] T. Lengyel, The order of the Fibonacci and Lucas numbers (1993)

[2] PrimeGrid PRPNet, Wall-Sun-Sun Prime Search

[3] N. J. A. Sloane, Sequence A001177 in the OEIS

[4] N. J. A. Sloane, Sequence A001602 in the OEIS

[5] Labos Elemer and Ralf Stephan, Sequence A090740 in the OEIS


Forming Partial Fractions Suppose we have:
$ \dfrac{f(x)}{g(x)h(x)} $
and we want to break it down into:
$$ \frac{I(x)}{g(x)} +  \frac{J(x)}{h(x)}$$
and that
$$\deg(f) \leq \deg(g)+\deg(h),\quad \deg(I) < \deg(g), \quad\deg(J) < \deg(h).$$
What is the general way of doing this?
I don't understand the intuition behind having to express;
$\frac{ax^{2}+bx+c }{(dx+e)(f x^{2}+g) } = \frac{A}{dx+e} + \frac{Bx+C}{fx ^{2}+g }$.
Is there a general rule I'm missing?
Thanks.
Edit: Just to clarify, these are all polynomials.

First what is the generalized theorem?

Theorem Given three polynomials $P,Q,R$such that $\gcd(P,Q)=1$ there exists $U,V$ such that:
$$\frac{R(x)}{P(x)Q(x)}=\frac{U(x)}{P(x)}+\frac{V(x)}{Q(x)} $$
with $\deg(U)+\deg(R)< \deg(P), \deg(V)+\deg(R)<\deg(Q)$

Proof It follows easily from Bézout's identity and extended GCD algorithm
As we observe the condition $P$ and $Q$ being relatively coprime are necessary for the validity of the theorem because we can find simple examples which does not satisfy the theorem.
Second how to compute $U$ and $V$?

Algebraic method using the extended GCD algorithm, which is the general method and it always works

Analytic method, for example, if we want to find $U$ and we know the roots of $P$ we know that $deg(U)\leq deg(P)$ so we only need to find the values of $U$ in at least $deg(P)$ points. This can be done using:
$$I(x)=\frac{R(x)}{Q(x)}=U(x)+\frac{V(x)}{Q(x)}P(x) \tag 1$$
It's easy to see that if we evaluate $I$ in the roots of $P$ we can find the values of $U$, if we have multiple roots we also evaluate the derivatives of $I$.

There are other methods using for example the roots of $Q$ in formula $(1)$ in which case we use limits and evaluating in some remarkable points such as $a,1,-1$ the roots of $P,R,Q$.

Third why we need this decomposition, there are a lot of applications of the decomposition like this in computing integrals and solving differential equations.

As long as the denominator has only simple irreducible factors, it's rather straightforward. Here, for instance, I'll suppose $f,g$ have the same sign, so that $fx^2+g$  is irreducible and it has complex roots. The general strategy is to:

Multiply both sides of equality by $(dx+e)(fx^2+g)$. You obtain a polynomial identity:
$$ax^2+bx+c=A(fx^2+g)+(Bx+C)(dx+e).$$
Set $x=-\dfrac ed\,$ and get an equation for $A$.
Set $x=\mathrm i\mkern 1.5mu\sqrt{-\dfrac gf}$. You get an equation with complex coefficients for $d$ and $e$, i.e. two equations with real coefficients.

Also remember you first have to divide (with remainder) the numerator by the denominator, so as to have a proper  rational function ($\deg$(numerator) $<\deg$(denominator)).
For a proper rational function, the decomposition theorem says they are are sums of proper rational functions with primary denominators (=powers of a single  irreducible polynomial) and $\deg$(numerator) $<\deg($irreducible polynomial). In the case of an irreducible quadratic polynomial, this means the numerator will have degree at most $1$.


Calculating $e^{3x} \pmod{27}$ I am following some notes that say that $\exp(3x) = 1 + 3x + \frac{9}{2}x^2 + \frac{9}{2}x^3 = 1 +3x+18x^2+18x^3 \pmod{27}$

I can't understand this. Firstly why do we stop the expansion after 4 terms? And secondly I don't see why $ \frac{9}{2}x^2 + \frac{9}{2}x^3 = 18x^2+18x^3 \pmod{27}$

Could someone please explain it to me? I wish to follow the same method for $\log(1+5x) \pmod{5^4} $

Thanks in advance

$$e^x = \sum_{n=0}^{\infty}\frac{x^n}{n!}$$
the  terms of degree more than 3 are multiples of 27


Complete solution vs General solution of a PDE I am unable to understand why the general solution is a "bigger set of solutions" than the complete solution.

What is the intuition behind this?

Source of the quotation:

The general solution involves arbitrary function of known function's $u$ and $v$, while the complete solution involves arbitrary constants.
The arbitrary function is more general than arbitrary constants as it include all possible functions of variable and constants, so I think that's the reason.


Does the sequence converge, alternating series fails? Does $\sum_{n=1}^{\infty} (-1)^n \frac{2}{n} \cos^2(\frac{\pi n}{2})$ converge?

The alternating series test fails, because I am unable to prove that $f'(n) < 0$, I can get to $f'(n) = 0$, but that fails the test.

notice that $\cos^2(\frac{\pi n}{2})$ is $1$ if $n$ is odd and $0$ otherwise, so letting $n=2m$ and adding only over even terms our sum is equal to:

$\sum\limits_{m=1}^{\infty}(-1)^{2m} \frac{2}{2m}=\sum\limits_{m=1}^\infty \frac{1}{m}$

No, it doesn't... when $n$ is odd. $\cos^2(\frac {n\pi}{2}) = 0$

and when n is even $\cos^2(\frac {n\pi}{2}) = 1$

So we can re-write this as $\sum \frac 1{n}$ which does not converge.


Topology-book for self study about physical meaning I self study physics, and I have come across some mathematics that are unknown to me. It has to do with helicity, linking numbers and other topological factors.

A friend of mine told me that this is called topology. I want to delve into this subject on a mathematics basis but with some physical meaning in it. So I wanted to know if there are any books that are easy to delve into and can teach me these topological factors (especially stuff that have to do with linking numbers) but also give some intuition and maybe some physics exercises (or more generally have some exercises that are not purely mathematical).

Also, except from books,do you know any other means to learn these topological factors (like web sites)?

Thank you

I think Gauge Fields, Knots, and Gravity by Baez and Munian might be exactly what you're looking for. It is a very good text with plenty of illustrations that conveys good intuition about the mathematical and physical content. As per the title, the book discusses physical applications of knot theory, and the section starting on page 310 discusses linking numbers.

Metric spaces are basic to topological spaces.  There is a book of only 71 pages where one can learn what is a ''distance'' with a high degree of intuition.

Yu. A. Shreider, WHAT IS DISTANCE, The Chicago university press, 1974. ISBN 0-226-75498-7.


Generic elementary group theory problems. This question is about generic group theory problems. here are examples for what I’m referring to:

  Prove that any group of order $p^2$, where $p$ is a prime, is
  abelian.

  Let $G$ be a group of order $2n$. Suppose that half of the elements
  of $G$ are order $2$, and the other half form a subgroup $H$ of order
  $n$. Prove that $H$ is of odd order ($n$ is odd) and that it's
  abelian.

  "Let $G$ be a group with $|G|=pq$ for some $p$, $q$ primes such that
  $p>q,q∤p−1$. Prove $G$ is cyclic."

Most of the time I find myself attacking these kind of problems with no coherent strategy, just throwing all my ammunition (Cauchy theorem, Lagrange theorem, index 2 theorem, intersection unions and multiplication of (normal-) subgroups etc.).

Best case scenario is I manage to prove the statement yet I don't quite get why the statement is true because the proof is so long and involves a lot of cases and assumptions by contradiction that i can't see the forest for the trees.

A lot of the times there are more than one way to prove the statement which are not so similar.

For an excellent example to what I’m referring to, look here.

Since I feel that most of the time I’m just juggling variables I'd like to know what should i do to understand what's really going on?

Another different thing that might ease my mind is an exhaustive list of the theorems that can be used to solve these kind of problems. That way i will at least know what are all the possible techniques that might work for these problems.

ADDED: Although neat proofs for the specific problems i posted are welcome they are not the reason i asked this question. I solved these problems and others too yet my proofs were long and lacked an identifiable idea. What I'm looking for is a general principle that could guide me in constructing proofs for these problems.

I find that, for elementary group theory problems, one of the best places to start is by asking yourself if (how) groups actions could be used to express this. Then you have some very powerful (while still elementary) theorems that you can use.

For your examples, I point you to User-33433's answer.

For another example which was found in a homework problem in the abstract algebra class that I just finished:

  Show that any group (including infinite) that contains a proper subgroup of finite index also contains a proper normal subgroup of finite index.

One way to prove it is to go through all of the motions of proving that the intersection of finite index subsets is, again, finite index, extending this by induction, looking at $N=\bigcap_{g\in G}gHg^{-1}$,  proving that this normal and is actually a finite intersection by the Orbit-Stabilizer Theorem when $G$ acts on the cosets of $H$ by conjugation, and finally using the result on finite intersections of finite index sets that you would have proved.

The easier, and more powerful, way to show this result (and even more, as we'll see) is the following which comes from considering the action of $G$ on the cosets of $H$ by conjugation as the important feature, rather than just a means to show that the previous set $N$ is a finite intersection.

Let $H\leq G$ be of finite index $n$. Then, $G$ acts on the cosets of $H$ by conjugation, and this induces a map $\varphi:G\to\text{Sym}\left(G/H\right)\cong S_{n}$. The kernel of this map is normal, and $G/\ker\varphi$ isomorphic to a subgroup of $S_{n}$, so $|G:\ker\varphi|\leq n!$, as required.

This proves that, not only do we have a proper normal subgroup of finite index, but we have one of index $\leq n!$. So, group actions are very powerful and allow you to go straight to the core of many elementary group theory problems, rather than having you flounder around for a bunch of other results just to scratch the surface.

Solution to $2$:

To prove that $n$ is odd note that if $n$ is even then there exists Sylow $2$ subgroup $S$ of G, easy to see that exist half of elements in $S$ of order $2$ and other half is $S\cap H$ is subgroup of S, but now $|S|=2^k, k\geq 2$, so use induction.

To prove that $G$ is Abelian use: $\forall x\in G\setminus H$, $\forall a_1, a_2\in H$, $xa_2a_1\in G\setminus H$, so $(xa_2a_1)^2=e$, so $xa_2a_1=a_1^{-1}xa_2$, $(a_1^{-1}x)^2=e$, so $a_1^{-1}x=xa_1$ and $xa_2a_1=xa_1a_2$. done