What is the probability this Markov chain does not reach state $r$? Consider a random walk on the non-negative integers.

You start at $0$, and in each step you either move $1$ higher, or $2$ lower (but can't go below $0$). The direction is picked w.p. $1/2$ independently at any step.

From $0$ you can either stay at $0$, or go to $1$.

From $1$ you flip a coin and go either to $0$ or to $2$.

From $i>1$, you go to $i-2$ or to $i+1$.

What is the probability that during $n$ steps, the process never reaches state $r$?

If this does not have a simple form (as a function of $n,r$), can we derive an upper bound for it?

This seems to be solvable by a recurrence formula, but I couldn't reach an explicit expression.

Since it is a Markov process, these probabilities satisfy recursive equations. Namely, since in your case reaching $r$ is the same as reaching any number from $r$ till $\infty$ (upwards move are of size $1$), you solve a reachability problem for the interval $[r, +\infty)$. In general you have $V_0(x) = 1_A(x)$ and
$$
  V_{n+1}(x) = 1_A(x) + 1_{A^c}(x) \cdot PV_n(x)
$$
where $1_A$ is an the indicator function of $A$ and $P$ is the stochastic matrix. So over $A$ the solution is obviously $1$ for all $n$, and we can simplify this for $x\notin A$: for those
$$
  V_{n+1}(x) = \sum_{y\notin A}p(x,y)V_n(y) + \sum_{y\in A^c}p(x,y)
$$
here $p(x,y)$ is the probability of going from $x$ to $y$. In your case only two values are probable when departing from $x$, let's say $x^+$ and $x^-$, each with probability $\frac12$. So you get
$$
  V_{n+1}(x) = \frac12\left(V_n(x^-) + V_n(x^+)\right)
$$
with the following boundary conditions: $V_0(x) = 1_A(x)$ and $V_n(x) = 1$ for all $x\in A$. That should be enough for you to carry on computations.

P.S. Just realized you look for the probability of not reaching $r$. In that case, you can compute what I have proposed and subtract it from $1$. Or, if you want to have a neater solution, just substitute $U_n := 1 - V_n$ in the equations above: you'll get an even simpler recurrent scheme.

As I mentioned in my comment, if $n>r$, then we can have atmost $r-1$ steps that move up. So the probability that after $n$ steps, we do not reach $r$ is,

$$P_{n,r} = \sum_{i=0}^{r-1} {n \choose i} {1 \over 2^{n}}$$

To include the constraint that we remain above 0, notice that if we move up $p$ times up, we have to move $q$ times down such that $p+q=n$ and $p-2q>=0$. Solving for minimum value of $p$, we get $p>={2n \over 3}$. This also puts a contraint that $r>=2n/3$. Adjusting the value of $i$ in our original eqution, we get

$$P_{n,r} = \sum_{i={2n \over 3}}^{r-1} {n \choose i} {1 \over 2^{n}}$$


If your 3 points are A, B, C then you may use directly the (half) cross product formula :
$$S=\dfrac{|\mathbf{AB}\times\mathbf{AC}|}2=\dfrac{|\mathbf{AB}||\mathbf{AC}||\sin(\theta)|}2 $$
that is (see the Wikipedia link to get the cross-product in $\mathbb{R}^3$) :
$$S=\frac 12 \sqrt{(y_{AB}\cdot z_{AC}-z_{AB}\cdot  y_{AC})^2+(z_{AB}\cdot  x_{AC}-x_{AB}\cdot  z_{AC})^2+(x_{AB}\cdot  y_{AC}-y_{AB}\cdot  x_{AC})^2}$$
if $\mathbf{AB}=(x_{AB},y_{AB},z_{AB})$ and  $\mathbf{AC}=(x_{AC},y_{AC},z_{AC})$

If a,b,c are the position vectors, use
1/2abs(a×b+b×c+c×a).
Take the magnitude of the area vector to get the solution.


Prove that for a homogeneous function of degree one all directional derivatives exist I am trying to prove that for a function $f:\mathbb{R}^n \rightarrow\mathbb{R}$ that is homogeneous of degree one, all directional derivatives exist. I also want to prove that it is differentiable if and only if $f$ is linear.

I know that since the function is homogeneous, I have $f(\lambda x)=\lambda f(x)$ for $\lambda>0$ and $x$ in $\mathbb{R}^n$, but don't know how to continue from this.

Let $0\ne (a,b)=h\in\mathbb{R}^2$ a direction. $f(0,0)=0\cdot f(1,0)=0$.

$(Df)(0,0)(h)=\lim_{t\rightarrow 0} \frac{f((0,0)+t(a,b))-f(0,0)}{\left \| (a,b) \right \|} =\lim_{t\rightarrow 0}\frac{f(ta,tb)}{t\cdot\sqrt{a^2+b^2}} =\lim_{t\rightarrow 0}\frac{t\cdot f(a,b)}{t\sqrt{a^2+b^2}}=\lim_{t\rightarrow 0}\frac{f(a,b)}{\sqrt{a^2+b^2}}=\frac{f(a,b)}{\sqrt{a^2+b^2}}$.


Image of countable and uncountable sets There are two questions:

  Image of a countable set of real numbers under any continuous function is countable?

My claim is yes. Let $X$ is countable $\implies X=\{x_1,x_2,\ldots,\}$. Now $f(X)=\{f(x_1),f(x_2),\ldots,\}$ which can be atmost countable. Now my question is "What is the role of continuity here?"

  Image of a uncountable set of real numbers under any non-constant continuous function is uncountable?

I feel this is true. But unable to proceed. Please provide me a hint.

There are non-constant continuous functions with an uncountable number of zeroes.

My first thought was to use the Cantor set $C$, and a search for prior art led to this existing example already on this site:

Non-constant continuous function having uncountably many zeros?

The function is:

$$f:[0,1]\to\mathbb{R}, f(x) = \inf_{c \in C}\{ |x - c|\}$$

It can be shown that $f(x) = 0 \quad\forall x \in C$ and that $f$ is continuous on $[0,1$].

To 1, you dont need suppose continuous.

To 2, as the function is not constant, use intermediate value Theorem and get an interval in the image.


How does the max of $\prod_i a_i$ work? Here are two succinct statements of the 'same' question:

Statement 1:
Take $a>0$ and $S \subseteq \mathbb{R}^N; S=\{(x_1,\dots,x_N)| \frac{1}{N}\sum_i x_i = a; x_i>0\}$. Define a 'product function' $f:S\rightarrow \mathbb{R}^N; f(x_1,\dots,x_i)=\prod_ix_i$. There are many proofs that the max of $f$ over all of $S$ occurs at $\vec{v}_a=(a,a,\dots,a)$. But here is the 'extension':

  Consider two points $c,d \in S$ with $||\vec{c}-\vec{v}_a||_1\leq||\vec{d}-\vec{v}_a||_1$ ('taxicab' $\ell_1$ norm). Why does $f(\vec{d})<f(\vec{c})<f(\vec{v}_a)$?

Statement 2:
Take two sets of real numbers $C=\{c_1,\dots, c_N\}, D=\{d_1,\dots,d_N\}$ with $\sum_i c_i=\sum_i d_i = 0$ and $\sum_i|c_i|<\sum_i |d_i|$. Take some $a>0$ great enough so that $a+x_i>0$ for any $x_i\in C \cup D$.

  Why is $\prod_i (a+d_i) < \prod_i(a+c_i)$?

Apparently it is a known result, but after a day of grief on my own I haven't been able to make any useful progress. My most promising approaches seemed to be:

Fiddling with the AM-GM inequality
Halve $C,D$ about their means (or centers?) to get more sets. Then try and somehow use the fact that for $a>b$, $(a-b)(a+b)<a^2$. Iterate recursively until you have the desired product.
Show that $f$'s derivative is largest in the $(1,1,\dots, 1)$ direction, $\vec{c},\vec{d}$. Then show that in $S$ you are 'closest' to this direction the smaller $\ell_1$-distance you are from $\vec{v}_a$. Note that $S$ is a positive hyperplane, but it's shifted so it's not a subspace.
Not-so-promising was expanding the polynomial product into a sum of $2^N$ $N^{\mathrm{th}}$-degree terms.

Your statements are false. Consider for example $\vec{c}=(2,100,498)$ and $\vec{d}=(25,25,550)$. Both $\vec{c}$ and $\vec{d}$ have mean $a=200$. And $||\vec{c}-\vec{a}||_1=596<700=||\vec{d}-\vec{a}||_1$, but $f(\vec{c})=99600<343750=f(\vec{d})$.

You probably forgot some additional conditions.

$\ln x$ is an increasing function. therefore $\arg \max\prod\limits_{i=1}^{x_n}x_i =  \arg \max \ln \prod\limits_{i=1}^N x = \arg\max\sum\limits_{i=1}^n\ln x_i$. Once you've noticed it, it should be easier.


Let $X=\{x|x=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}, n\in \mathbb{N}\}$. Find $X \cap \mathbb{N}$ I am out of hints here. Its trivial to show $1$ is a solution. How to show it's the only solution?

Can someone please give me some hints?

Please do not use congruence, limits or derivatives because they are out of scope of the chapter which has this question.

The harmonic number is never an integer for $n>1$. In fact (as shown in the article), the largest power of $2$ dividing the denominator in the simplest form, is the largest power of $2$ not exceeding $n$


Provide a bijection between power set of natural numbers and the Cantor set in $[0,1]$ Question: I am trying to prove that Cantor Middle Third Set $C$ is uncountable, by establishing a bijection $f$ from $C$ onto the power set of $\mathbb{N}.$

My attempt: We know that every element of Cantor set $C$ has a ternary representation.
Let $\mathcal{P}(\mathbb{N})$ be the power set of $\mathbb{N}.$
Define $f:C\to\mathcal{P}(\mathbb{N})$ by
$$f((a_1,a_2,a_3,...,a_n,...)) = \{n\in\mathbb{N}:a_n\neq 0 \},$$
where $a_n\in\{0,2\}$ for all natural number $n.$
Clearly $f$ is well-defined and injective.
To prove that $f$ is surjective, given any subset $X\in \mathcal{P}(\mathbb{N}),$ we pick $x \in C$ such that non-zero entries of $x$ corresponds to numbers in $X.$
For example, if $X=\{1,4,6\},$ then we pick $x = (2,0,0,2,0,2,0,0,0,...).$
Is my proof correct?

There are, of course, things to nit-pick about your presentation, but the proof itself is entirely correct. Here are the three things that I saw and thought could've been better:

You should be clearer on what $(a_1,a_2,\ldots)$ is. It is the ternary expansion of a point in $C$ with the restriction that $a_i\neq 1$ for all $i$. It's implicitly understood, but I think it is better to state explicitly. The fewer things a reader has to guess (no matter how certain you are that you guessed right), the better.

Perhaps you should have a short justifying sentence for each of well-definedness and injectivity, just to be safe. Well-definedness hinges on the uniqueness of the ternary expansion (as long as we require no $1$'s), and injectivity on the fact that two real numbers with the same expansion are equal.

Your surjectivity proof is explained via an example. This is better to do generally. Say we have a $U\subseteq \Bbb N$, and we then define $x = \sum_{n = 1}^\infty a_n3^{-n}$ where $a_n =2$ iff $n\in U$ and $0$ otherwise. Then $x\in C$, and we get $f(x) = U$. (Whether you want to prove that $x\in C$ and $f(x) = U$ is completely up to you.) After that you are free to do an example to illustrate.

Here's another proof:
First, note that we can create a bijection between $C$ and all the decimals written using only 0s and 1s by switching all the 2s to 1s. Now consider all those decimals in base 2. Those are precisely all the rational numbers between 0 and 1, so this is a bijection between $C$ and $[0,1]$, which has cardinality $\aleph_1 = |\scr P(\mathbb N)|$.


What is the sum of the digits of the sum of the digits? Problem

  Let $(10^{2016}+5)^2=225N$. If $S$ is the sum of the digits of N, then find the sum of the digits of S

Attempt

Let's look at some smaller cases. We have $\dfrac{(10^{3}+5)^2}{225} = 4489$,$\dfrac{(10^{4}+5)^2}{225} = 444889$, and $\dfrac{(10^{5}+5)^2}{225} = 44448889$. Thus we see the pattern and $S = 4*2015+8*2014+9 = 24181$ and the sum of the digits of $S$ is $\boxed{16}$.

Question

Prove the result in the solution above by induction or some other method. That is, show that for $n > 1$

$$\dfrac{(10^{n}+5)^2}{225} =\underbrace{44\ldots4}_\text{n-1 4's}\underbrace{88\ldots8}_\text{n-2 8's}9.$$


Find the group with presentation $\langle x, y: xy=yx, x^5=y^3\rangle$. Here's the problem:

Find the group with presentation $\langle x, y: xy=yx, x^5=y^3\rangle$.

Here's my answer:

The group is commutative by the first relation, so every "word" is of the form $x^iy^j$ for $i,j \in \mathbb{Z}$. By the second relation we have $x^a y^b $ for $0 \leq a \leq 4$ and $b \in \mathbb{Z}$. Hence the group is  isomorphic to $\mathbb{Z_5} \times \mathbb{Z}$.

Is this correct?

Your answer can't be right, since multiplying any element in $ \mathbb Z/5\mathbb Z \times \mathbb Z $ by $ 5 $ gives you something of the form $ (0, 5x) $, and such an element can't be divided by $ 3 $ in this group, so there's no element to play the role of $ y $.

To find the isomorphism class, note that there is a surjective map $ \mathbb Z^2 \to G $ given by $ (n, m) \to x^n y^m $  (where $ G $ denotes your group) whose kernel is precisely $ \langle (5, -3) \rangle $. In other words, we're trying to find the quotient $ \mathbb Z^2/\langle (5, -3) \rangle $.

This quotient is isomorphic to $ \mathbb Z $, as you can see by noting that $ (5, -3) $ and $ (3, -2) $ form a basis of $ \mathbb Z^2 $, so $ G \cong \mathbb Z $.

Is this correct?

No.

gap> F:=FreeGroup(2);
<free group on the generators [ f1, f2 ]>
gap> rels:=[(F.1)*(F.2)*((F.1)^(-1))*((F.2)^(-1)), (F.1)^5*((F.2)^(-3))];
[ f1*f2*f1^-1*f2^-1, f1^5*f2^-3 ]
gap> G:=F/rels;
<fp group on the generators [ f1, f2 ]>
gap> P:=PresentationFpGroup(G);
<presentation with 2 gens and 2 rels of total length 12>
gap> TzGoGo(P);
#I  there are 2 generators and 2 relators of total length 12
gap> TzPrint(P);
#I  generators: [ f1, f2 ]
#I  relators:
#I  1.  4  [ 1, 2, -1, -2 ]
#I  2.  8  [ -2, 1, 1, 1, 1, 1, -2, -2 ]
gap> Size(G);
infinity
gap> StructureDescription(G);
"C0"
gap>


Arithmetic question about percentages Hi I have a rather basic arithmetic question about percentages which is confusing me:

Let's say you have a variable x that is composed of x1, x2, x3.

You know what (x1 + x2) is, and you also calculated from some other data that x3 is y% of x. How do you now adjust (x1+x2) to get x?

So for example:

(x1+x2)= 55

Y%= .31

Which of the following two is the correct answer for x?

55*(1+.31)   OR   55/(1-.31)

The first one you're adding 31% to the 55, but in the second one you assume that the 55 is 69% of x, and so to get 100% you divide 55/.69.

Which is the right one?

By

  $x_3$ is $y\%$ of $x$

I assume you mean that $x_3$ is $y\%$ of the sum of $x$ (i.e., $x=x_1+x_2+x_3$).

In that case, you know that $x_1+x_2$ is $(1-y)\%$ of the total sum (in your example, that would be $0.69$.

So you have $55=0.69\cdot x$ or $$x=\frac{55}{0.69}$$


Continuous function f such that its inverse takes exactly two values in R except at three points. Let $f:\mathbb{R} \to [1,3]$ be a continuous function such that $f^{-1}(1)$ and $f^{-1}(3)$ are singletons  and $f^{-1}(x)$  consists of exactly two real numbers $\forall x\in (1,2) \cup (2,3)$.Then prove that the cardinality  of $f^{-1}(2)$ is either 1 or uncountable.
I am able to define a function $f(x)$ for the case when $f^{-1}(2)$ is uncountable as shown below :
Let $A(-3,2)\,,B(-2,3)\,,C(1,1)\,,D(3,2)$ be four points.
The function $f(x)=\begin{cases}
2&,x\le -3 \\
\text{line}\,\, AB&,-3\le x \le -2\\
\text{line}\,\, BC&,-2\le x \le 1\\
\text{line} \,\,CD&,1\le x \le 3\\
2&,x\ge 3
\end{cases}$\
For the function $f$, the pre image of 2 is uncountable.
I am not able to draw a graph for the case $f^{-1}(2)$ is singleton.Help please.And how do we prove the two cases analytically ? Thank you for the help.

For the case $f^{-1}(2)$ singleton you could create a graph that goes:

as $x \to -\infty$, $f(x) \to 2+$

as $x \to +\infty$, $f(x) \to 2-$

$f(-1) = 3$

$f(1) = 1$

$f(0) = 2$

and then join it up with a smooth line. As $x$ increases, it goes up from just above $2$ till $3$, then it goes down through $2$ to $1$, and then goes up again slowly till just below $2$.

Is that the sort of thing you had in mind?


Who was the first to use dual space? Who was the first person who used the dual space? In which paper / book did he or she use the dual space?

Who was the first who called it dual space and in which paper / book?

It was Hahn (of Hahn-Banach Theorem) who, in 1927, first introduced the dual of a normed linear space ("polare Raum" was his term.) Hahn had extended previous arguments for separable spaces in order to obtain the existence of general continuous linear functionals on a normed linear space; Hahn did this by introducing methods of transfinite induction. Hahn introduced the idea of regular normed spaces (now called reflexive.) It makes sense that the existence of general classes of continuous linear functionals would lead to a proper notion of a dual space.

Two years later after Hahn, Banach proved the same theorem with the same proof (He later acknowledged the primacy of Hahn's work.) Banach introduced a convex functional and extensions of linear functional bounded by convex functions, which paved the way for locally-convex spaces.

It appears that the understanding gained in Functional Analysis came before a proper understanding of the dual for a finite dimensional vector space!
In History of Functional Analysis, J. Dieudonne writes that "before 1930 nobody had a correct conception of duality between finite dimensional vector spaces; even in van der Waerden's book (1931), such a vector space and its dual are still identified. All this was to weigh heavily on the evolution of a linear Functional Analysis; in particular it followed (over a shorter span of years) the same unfortunate succession of stages through which linear Algebra had to go; and it is only after it was realized that the current conception of vectors as "n-tuples" could not possibly be extended to infinite dimensional function spaces, that this conception was finally abandoned and that geometrical notions won the day."

Stefan Banach in the  "Théorie des opérations linéaires" is a good bet.


limit of sequence transformed random variable Let $f$ be some function with $\lim_{s\to\infty} f(s)=0$. Now consider the following inequality: $$f(s)<e^{-(s x)^2},$$ where $x$ is a random variable that is standard normal distributed. The question is whether the inequality is true for all possible realizations of $x \sim N(0,1)$ as $s\to \infty$. Clearly, both sides go to 0 in the limit. So whether or not this is true depends on the rate at which $f$ goes to 0 compared to the right hand side.

Now suppose we were to do a change of variables to $y=sx$ on the right hand side. Then an equivalent statement would be: Is $$f(s)<e^{-y^2}$$ true for all $y\sim N(0,\sigma^2)$ as $s\to\infty$? Now, however, fixing a particular $y$, the statement seems to be always true...

I find this discrepancy somewhat odd and I suspect that something is wrong how I treat the transformation here. But I am confused about where exactly my reasoning goes wrong.

Here are some thoughts:
I know that the transformation is not well-defined in the limit, so this could be one problem. Another thing is whether one can even fix a particular $y$ and validate the inequality pointwise. E.g., it could be that generally, it is not sufficient to fix a particular $y$ and show that for any such $y$ there exists an $s$ such that the inequality is true. Alternatively, it could also be that just in this context one cannot keep $y$ fixed given that the transformation itself does depend on $s$ (or, equivalently, given that the distribution of $y$ does depend on $s$).

It would be great if someone could clarify where exactly my reasoning goes wrong.

As you said, the answer seems like it depends specifically on the the function f(s). If you really want the answer to hold for every possible realization of the normal distribution however, and not just almost surely or in probability or something like that, then I would have to assume the answer is no for any function that did not go to zero extremely rapidly.

More precisely, N(0,1) can take any real value. So the inequality would literally have to fold for all x in R, which seems implausible to me in most cases.

If you use some function that goes to 0 faster than every conceivable exponential (maybe like the gamma function, since that generalizes the factorials on $R^+$?) it might have a chance of working.

Otherwise if the function is $O(e^{as^2})$ for any $a\in R$, then it does not seem possible this could hold for every realization of N(0,1).

Just to put together what I wrote in the comments:

When you change the variables, the way to think about the second inequality would be in terms of $f(\frac{y}{x})$ and not f(s). I.e. one can not assume that in the second inequality s would be independent of y and still be deterministic.

If you fix y, and then let s go to infinity, you are as a result varying x, which then would no longer have the same N(0,1) distribution, i.e. fixing y is a different problem, since even though s and x are independent, s and y are not.

In other words, if you are fixing y, then s is actually a random variable and not deterministic, i.e. $\frac{y}{x}$, taking values anywhere on ℝ and Cauchy distributed (see https://en.wikipedia.org/wiki/Ratio_distribution#Gaussian_ratio_distribution), for which the probability that |s| is very large (and hence f(s) smaller than any arbitrary number) is 1−ϵ, since the Cauchy distribution has "very thick tails", e.g. enough so that its expectation does not even exist.

Thus the second inequality should be true with very high probability, although it does not mean what you want it to mean.

If you are fixing s, then s is measurable with respect to the trivial sigma algebra (since it is a constant RV), so (y|s) (y given s) would also be measurable with respect to the trivial sigma algebra, so essentially any event corresponding to (y|s), which seems to be your second inequality, is either a.s. true or a.s. false, which corroborates the inequality being a.s. true.

If in the second inequality you are taking s to be fixed, then the random variable you are considering is actually (y|s), which has to be measurable with respect to a trivial sigma algebra (since s is a constant RV), so hence (y|s) would also be a.s. constant ($s\mathbb{E}x = 0$), so the inequality would become f(s) < 1 as s goes to infinity, which is obviously true by assumption.

Changing variables for random variables always requires great care, since RVs are actually real-valued functions from a probability space, not numbers, so the logic involved will always be more complicated and the reasoning used for regular variables unsuited.

EDIT: to address concerns about the notation used in this answer, and to appeal to those who are familiar with the concept of conditional expectation as a random variable, (y|s) is not standard notation, but it is obviously highly suggestive of (and meant to denote) $\mathbb{E}(Y|\sigma(s))$, which is a constant random variable (it is a constant RV because of the conditioning on the trivial sigma algebra, the sigma is being trivial because the RV s is a constant RV).


Followup to my previous question, $M = \text{Image}(u^\infty) \oplus \text{Ker}(u^\infty)$. See my previous question here, Intersection of images and union of kernels.

  Let $A$ be a ring (not necessarily commutative), let $M$ be an $A$-module, and let $u: M \to M$ be an $A$-module morphism. Put $$\text{Image}(u^\infty) := \bigcap_{k=1}^\infty \text{Image}(u^k),\text{ resp. }\text{Ker}(u^\infty) = \bigcup_{k=1}^\infty \text{Ker}(u^k).$$Are $\text{Image}(u^\infty)$ and $\text{Ker}(u^\infty)$ necessarily $A$-submodules in $M$?

My question this time around is, do we moreover have that$$M = \text{Image}(u^\infty) \oplus \text{Ker}(u^\infty)?$$

Since we have$$M \supseteq \text{Im}(u) \supseteq \text{Im}(u^2) \supseteq \dots$$and $M$ is of finite length, we must have some $k \in \mathbb{N}$ such that  for all $k' \ge k$,$$\text{Im}(u^{k'}) = \text{Im}(u^k) = \text{Im}(u^\infty).$$Since we also have$$\text{Ker}(u) \subseteq \text{Ker}(u^2) \subseteq \dots \subseteq M,$$we get that for all $k' \ge k$,$$\text{Ker}(u^{k'}) = \text{Ker}(u^k) = \text{Ker}(u^\infty).$$

Proof that $M = \text{Ker}(u^\infty) \oplus \text{Im}(u^\infty)$. Assume $a \in M$, and let $a_1 = u^k(a) \in \text{Im}(u^\infty)$. So$$u^k(a - a_1) = a_1 - u^k(a_1) = a- u^{2k}(a).$$Since $a_1 \in \text{Im}(u^\infty)$, there is $a_2 \in M$ such that $a = u^{2k}(a_2)$. Hence,$$u^k(a - a_1 - u^k(a_2 - a)) = u^k(a - u^k(a_2)) = 0.$$So$$b_1 = a- u^k(a_2) \in \text{Ker}(u^k) = \text{Ker}(u^\infty),\text{ }b_2 = u^k(a_2) \in \text{Im}(u^k) = \text{Im}(u^\infty).$$Thus,$$a = b_1 \oplus b_2 \in \text{Ker}(u^\infty) \oplus \text{Im}(u^\infty),$$and so$$M = \text{Ker}(u^\infty) \oplus \text{Im}(u^\infty).$$
Proof that $\text{Ker}(u^\infty) \cap \text{Im}(u^\infty) = \{0\}$. Assume that $\lambda \in \text{Ker}(u^\infty) \cap \text{Im}(u^\infty)$. So $u^k(\lambda) = 0$, and there is $\lambda_1 \in M$ such that $\lambda = u^k(\lambda_1)$. Therefore, $$u^{2k}(\lambda_1) = 0 \text{ and }\lambda_1 \in \text{Ker}(u^{2k}) = \text{Ker}(u^\infty) = \text{Ker}(u^k).$$So $\lambda = 0$.


Find function with a degree of 4 from three statements If $f(x)$ is a function/polynomial with a degree of 4 and:
$$f(-1)=1$$
$$f(-2)=4$$
$$f(-3)=9$$
How can I find $f(x)$?

From statement 1, I know $f(x) = (x+1)(...)+1$
With statement 2, I know $f(x) = (x+1)[(x+2)(...)-3]+1$
We can use a similar way to find $f(x)$ with statement 3, but don't we end up with a cubic polynomial?
If my calculations are correct, how can we turn the cubic into a 4 degree polynomial?

This is a plain application of polynomial interpolation.
Three statements make it possible to uniquely define a polynomial of degree $2$. You can still find all the polynomial of degree $n\geq 2$ that satisfy those statements (using the Lagrange basis for example).

In this answer, I will determine the necessary and sufficient condition for the polynomial degree to be at least $4.$
I considered your polynomial to be a quartic of at least degree $4.$ But, this is not enough.
Method
For the quartic polynomial, at least value of $f(-4)$ must be known. Let, $f(-4)=p$, then you have
$$f(x)=a(x+1)(x+2)(x+3)+x^2$$
$$\implies a×(-6)+16=p$$
$$\implies a=\dfrac {16-p}{6}$$
$$\implies f(x)=\left(\dfrac {16-p}{6}\right)(x+1)(x+2)(x+3)+x^2$$
But, this is still not enough. Because, we have a cubic polynomial. You still need value of $f(-5).$
Let,
$$f(-5)=\left(\dfrac {16-p}{6}\right)\times (-24)+25\Longrightarrow f(-5)=4p-39$$
So, if $f(-5)=4f(-4)-39$ you still have a cubic polynomial.
Let, $f(-4)=p$ and $f(-5)≠4f(-4)-39$, then our tricky method will not work. So, you need a general method.
$$\begin{cases} a-b+c-d+e=1 \\16a-8b+4c-2d+e=4\\ 81a-27b+9c-3d+e=9 \\ 256a-64b+16c-4d+e=f(-4)\\ 625a-125b+25c-5d+e=f(-5) \end{cases}$$
You can solve this linear system with Gauss method.
A necessary and sufficient condition:
At least the values of  $f(-4)$ and $f(-5)$ must be given and the following condition must be hold:
$$f(-5)-4f(-4)+39≠0.$$
Conclusion
To obtain a polynomial of degree of at least $4$, it is necessary to know at least the values of $f(-4)$ and $f (-5)$, where $f(-5)≠4f(-4)-39$ or $f(-5)-4f(-4)+39≠0.$
To adapt to your circumstances, I wrote $f (-4)$ and $f(-5)$ instead of $f(4)$ and $f(5).$
Let's test the necessary and sufficient condition.
Let,  $$ f(-1)=1 \\ f(-2)=4 \\ f(-3)=9\\ f(-4)=16 \\ f(-5)=25 $$
Then, we have,
$$f(5)-4f(-4)+39 \Longrightarrow 25-4 \times 16+39=0$$
As it seems, the necessary and sufficient condition are not provided.  So, we can find a lower degree polynomial. And we really have such a function:
For example, the function $f(x)=x^2$ is the simplest function that provides the values we give.
Remark
Here we have only examined the requirement to give at least $f(-4)$ and $f(-5)$ values.  However, it is also possible to write it for the cases $f(4)$ and $f(5)$, or $f(7)$ and $f(9)$. However, this can never invalidate the condition $f(-5)-4f(-4)+39≠0.$


Motivation behind matrix diagonalisation I'm going to give a 50 minutes lecture about matrix diagonalization for first year college students and I would like to give some applications of it. I've been thinking about saying the calculation of matrix exponential become simpler in a diagonal matrix, but this subject is a higher level for them and I have only 10-15 minutes to talk about it.

So what do you think I can say to motivate them to study matrix diagonalization?

One application which I think is quite interesting and basic is to calculate the closed form of a recurrence relation.

Let's say we want to find a closed form (Binet's formula) of the Fibonacci sequence $(F_i)_{i \in \mathbb{N}}$. For this we can look at the equation
$$
A \begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} F_{n+1} \\ F_n + F_{n+1} \end{pmatrix} = \begin{pmatrix} F_{n+1} \\ F_{n+2} \end{pmatrix}, \; A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}.
$$
Applying this for $F_0 = 1$ and $F_1 = 1$ repeatedly we get
$$
\begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} = A^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \; n \in \mathbb{N}.
$$
We can diagonalize $A=T^{-1}DT$ with a diagonal matrix $D$ and get
$$
A^n = (T^{-1}DT)^n = T^{-1}DTT^{-1} DT \dots T^{-1}DT = T^{-1} D^n T.
$$
With simple calculations we get $D^n, T$ and $T^{-1}$, so we easily get $A^n$ and $A^n \begin{pmatrix}0 \\ 1 \end{pmatrix}$ gives Binet's formula.

I hope this is an interesting application.

Kind regards!

I'm a bit physics biased, but here's my two cents. Solving an eigenvalue problem is equivalent to diagonalizing an operator, think quantum mechanics, where the time independent Schroedinger equation is $$\hat{H}\psi=E\psi$$ Where $\hat{H}$ is an operator. To find the eigenstates of the system you diagonalize the operator $\hat{H}$, in the sense that you look for the eigenvalues.

More generally, I'd say the practical interest of diagonalization lies in finding the eigenvalues and eigenvectors of an operator. The eigenfunctions of the wave equation are practically the basis for Fourier series decomposition.

These are all generalizations of eigenstuff to operators on functional spaces, but even in finite dimensions, you can diagonalize a system of a given number of degrees of freedom in an even potential to get decoupled harmonic oscillators, you can diagonalize a matrix to find the principal inertial axis of a solid.

A physicist rarely spends a day without diagonalizing an operator, I imagine it's the same for a mathematician.


Integration reduction formula How to create a reduction formula for the integral$$\int x \cos^n x \;\mathrm{d}x$$

I have tried everything i could think of, but I'm not even close to solving it. Really need help.

Let $I_n$ be the integral

$$I_n=\int x\cos^n(x)\,dx$$

Then, we have

$$\begin{align}
I_{n+2}&=\int x\cos^2(x)\cos^n(x)\,dx\\\\
&=I_n-\int x\sin^2(x)\cos^n(x)\,dx\tag 1
\end{align}$$

Integrating by parts the integral on the right-hand side of $(1)$ with $u=x\sin(x)$ and $v=-\frac{\cos^{n+1}(x)}{n+1}$ yields

$$\begin{align}
I_{n+2}&=I_n-\left(x\sin(x)\left(-\frac{\cos^{n+1}(x)}{n+1}\right)+\frac{1}{n+1}\int (x\cos(x)+\sin(x))\cos^{n+1}(x)\,dx\right)\\\\
&=I_n+\frac{x\sin(x)\cos^{n+1}(x)}{n+1}-\frac{1}{n+1}I_{n+2}+\frac{\cos^{n+2}(x)}{(n+1)(n+2)}\\\\
&=\frac{n+1}{n+2}I_n+\frac{x\sin(x)\cos^{n+1}(x)}{n+2}+\frac{\cos^{n+2}(x)}{(n+2)^2}
\end{align}$$

You can actually evaluate this integral for general $n$ in terms of hypergeometric functions.


Find $k$ such that $\frac{1}{(1+x)^k}+\frac{1}{(1+y)^k}+\frac{1}{(1+z)^k}\geq\frac{3}{2^k}$ for $xyz=1$. Find all $k\in\mathbb{R}^+$ such that for all $xyz=1$, $x,y,z\in\mathbb{R}^+$, we
  have
  $$\frac{1}{(1+x)^k}+\frac{1}{(1+y)^k}+\frac{1}{(1+z)^k}\geq\frac{3}{2^k}.$$

If we set $$x=\frac{a}{b},\,y=\frac{b}{c},\,z=\frac{c}{a},$$ where $a,b,c\in\mathbb{R}^+$, then the inequality is equivalent to $$\frac{a^k}{(a+b)^k}+\frac{b^k}{(b+c)^k}+\frac{c^k}{(c+a)^k}\geq\frac{3}{2^k}.$$ For $k=1$ this is obviously false, as we take $b\to0$ and $c\to\infty$. In an olympiad test I saw that the case $k=\sqrt3$ is true (though I do not know how to prove that). I then thought that maybe this is true for all $k>1$. Am I correct and how do I prove it?

I think the answer is $k_{min}=\log_23$.

Let $x=e^a$, $y=e^b$, $z=e^c$ and $f(x)=\frac{1}{(1+e^x)^k}$.

Hence, $a+b+c=0$ and we need to prove that

$$\sum_{cyc}f(a)\geq3f\left(\frac{a+b+c}{3}\right)$$
But $f''(x)=\frac{2ke^x(ke^x-1)}{(1+e^x)^{k+2}}\geq0$ for all $k\geq1$ and $x\geq0$.

Thus, by Vasc's RCF Theorem for all $k\geq1$ it's enough to prove our inequality

for $y=x$ and $z=\frac{1}{x^2}$, which gives $\frac{2}{(1+x)^k}+\frac{1}{\left(1+\frac{1}{x^2}\right)^k}\geq\frac{3}{2^k}$
and for $x\rightarrow+\infty$ we get $k\geq\log_23$.

As shown below, an easy partial result is that $k_{\text{min}} \ge 1$.

Let $k$ be fixed with $0 <  k < 1$.

WIth the substitutions

$$x=\frac{a}{b},\,y=\frac{b}{c},\,z=\frac{c}{a}$$

let $a = b = 1$, and let $c \to 0^{+}$. Then

\begin{align*}
\;&\frac{a^k}{(a+b)^k}+\frac{b^k}{(b+c)^k}+\frac{c^k}{(c+a)^k}\\[6pt]
&\to \;\frac{1}{2^k} + 1 + 0\\[6pt]
&=\;\frac{1 + 2^k}{2^k}\\[6pt]
&<\;\frac{1 + 2}{2^k}\\[6pt]
&=\;\frac{3}{2^k}\\[6pt]
\end{align*}

It follows that $k_{\text{min}} \ge 1$, as claimed.

However, as shown below, the reasoning by which the OP (Yuxiao Xie) excluded the value $k=1$ is not correct.

Suppose $k = 1$. Then as$\;\,b \to 0^{+}$ and $\,c \to \infty$,

\begin{align*}
\;&\frac{a^k}{(a+b)^k}+\frac{b^k}{(b+c)^k}+\frac{c^k}{(c+a)^k}\\[6pt]
&\to\;1+ 0 + 1\\[6pt]
&=\;2\\[6pt]
&>\;\frac{3}{2}\\[6pt]
\end{align*}

which doesn't break the required inequality, hence the value $k=1$ is not automatically excluded.

In fact, I suspect that $k_{\text{min}} = 1$.

Update: It's not true, as I had previously thought, that $k_{\text{min}} = 1$.

As a simple counterexample, let $(x,y,z) = \left(\frac{1}{8},2,4\right)$. Then

$$\frac{1}{(1+x)}+\frac{1}{(1+y)}+\frac{1}{(1+z)} = \frac{64}{45} < \frac{3}{2}$$


How do i solve this equation ${\mathbb{R}}$: $3 \sin^3x+2 \cos^3x=2 \sin x+\cos x$? How do I solve this equation ${\mathbb{R}}$:

$3 \sin^3x+2 \cos^3x=2 \sin x+\cos x $?

Note : I have tried using trigonometric transformation but it seems very complicated to get the result .. may there is a clear variable change or some thing as this ...

Thank you for any help .

One possible way is to rewrite the equality as
$$
3\sin^3(x)-2\sin(x)=-2\cos^3(x)+\cos(x).
$$

WARNING: The following step may introduce extra solutions which will need to be checked at the end.

Now, square both sides.
$$
9\sin^6(x)-12\sin^4(x)+4\sin^2(x)=4\cos^6(x)-4\cos^4(x)+\cos^2(x).
$$
Using the trig identity $\cos^2(x)=1-\sin^2(x)$, you can rewrite this entirely in terms of $\sin^2(x)$.  When I did this on scratch paper, I got
$$
13\sin(x)^6-20\sin(x)^4+9\sin(x)^2-1.
$$
Finally, let $y=\sin^2(x)$ and you have the cubic equation
$$
13y^3-20y^2+9y-1
$$
to solve.

Note: The solutions to this polynomial are not pretty.

To solve: $3\sin^{3}x+2\cos^{3}x=2\sin x+\cos x$.
Use the substitution $\sin x = \frac{2\tan \frac{x}{2}}{1+\tan^{2}\frac{x}{2}}=\frac{2t}{1+t^{2}}$
and $\cos x =\frac{1-t^{2}}{1+t^{2}}$.
We become $t^{6}+4t^{5}-7t^{4}-16t^{3}+7t^{2}+4t-1=0$.
Only to solve numerically, 6 solutions, e.g. $t =\tan\frac{x}{2}=0.212475 \rightarrow x = 0.418722$.

This was not a simple problem, maybe there is a mistake in the question.


Using copper.hat's comment you can easily compute $f^{-1}$ explicitly.

Concerning the Jacobian $J_f$ you can argue as follows: The map $f$ is spherically symmetric, whence $J_f$ depends on $r:=\sqrt{x^2+y^2+z^2}$ only. Since you already have computed the matrix $[df(x,y,z)]$ it is sufficient to look at $$[df(x,0,0)]={\rm diag}\left(-{1\over x^2},{1\over x^2},{1\over x^2}\right)\ .$$
It follows that $J_f(x,0,0)=-{1\over x^6}$, which then implies
$$J_f(x,y,z)=-{1\over r^6}=-{1\over (x^2+y^2+z^2)^3}\ .\tag{1}$$
If you want to avoid computing the matrix $[df(x,y,z)]$ you can consider the spherical shell
$$S:=B(r+h)\setminus B(r)$$ of volume
$${\rm vol}(S)={4\pi\over3}\bigl((r+h)^3-r^3\bigr)\ .$$
Its image $$S':=f(S)=B(1/r)\setminus B\bigl(1/(r+h)\bigr)$$ has volume
$${\rm vol}(S')={4\pi\over3}\left({1\over r^3}-{1\over(r+h)^3}\right)\ .$$
It follows that
$${{\rm vol}(S')\over {\rm vol}(S)}={1\over r^3(r+h)^3}\ \to{1\over r^6}\qquad(h\to 0+)\ .$$
This says that the volume dilatation at radius $r$ is given by ${1\over r^6}$. Since $f$ obviously reverses the orientation we obtain $(1)$.

Here is a complement to Christian's rather nice geometric argument:

Let $n(p) = \|p\|^2$, then $Dn(p) = 2 p^T$.

Let $i(p) = p$, then $Di(p) = I$.

Then $f(p) = (n(p))^{-1} i(p)$, and so, using the product, rule we have
\begin{eqnarray}
Df(p) &=& - (n(p))^{-2} Dn(p) i(p) +  (n(p))^{-1} Di(p) \\
&=& {1 \over \|p\|^2}(I - {2 \over \|p\|^2} p p^T)
\end{eqnarray}
Now, using the fact that $\det(I+AB) = \det (I+BA)$, and $\det (\alpha A) = \alpha^n \det A$, we have
$\det Df(p) = {1 \over (\|p\|^2)^3} (1 - {2 \over \|p\|^2}p^T p) = -{1 \over (\|p\|^2)^3} $.


Span of an empty set is the zero vector I am reading Nering's book on Linear Algebra and in the section on vector spaces he makes the comment, "We also agree that the empty set spans the set consisting of the zero vector alone".

Is Nering defining the span of the empty set to be the set containing the zero vector or is this something you can prove from the definition of span? I sense it is the latter, but the proof seems a bit tricky since you would be saying that {0} = Span of the indexed set of vectors in the empty set. But since the empty set has no vectors, it is not clear to me what its span would be.

Depending on how you define the span, this is either a definition or it follows from the definition of span (and judging by the wording it is probably the former). What's Nering's definition of span?

(One definition of span is the following: the span of a collection of vectors is the intersection of all subspaces containing them. The span of no vectors is therefore the intersection of all subspaces, which is $\{ 0 \}$.)

linear span of an empty set i.e L(0) is taken as the set (O),this is confusing because L(0) is the set of all linear combinations of the elements of 0 but to make a linear combination we need to have at least one vector of the set and empty set contains no vectors in it. Thus it it should have been 0 and not (O).

On the other hand, if possible, let L(0) be a set other than (O). Then then it* either contains at least one non zero element (i.e a vector of V) which is a linear combination of the elements of 0.This leads us to a contradiction that 0 is not empty.Hence the possibility of L(0) to be other than (O) is ruled out.

or is it self 0.Now if this possibility can be ruled out then the proof becomes complete. reader may please comment.**


What does "with respect to the exclusion of a set" mean? I'm not good at English, but I'm studying math in English. Can anyone explain to me what is this sentence means?

  Let $Q$ be an ideal maximal with respect to the exclusion of $T$.

Thank you.

If you are studying multiplicative sets, it is probably in connection with this lemma:

  If $R$ is a commutative ring,  $T$ is a multiplicative subset$^\ast$ and $I$ is an ideal maximal with respect to exclusion of $T$, then $I$ is a prime ideal.

It means that $I$ has the property that if $J$ is another ideal properly containing $I$, then $J\cap T\neq \emptyset$.

$^\ast$ the definition ought to include the clause that $0\notin T\neq\emptyset$, of course

It is an ideal that is the largest without containing any elements of T. That is to say all other ideals that do not contain elements of T are subsets of Q.


Equivalence of $a \rightarrow b$ and $\lnot a \vee b$ Is there a proof for the logical equivalence of $a \rightarrow b$ and $\lnot a \vee b$?

Try using a truth table comparing $p\rightarrow q$ with $\lnot p \lor q$.
That's as good a proof as you need.

$p$ | $q\,$ |$\;p\rightarrow q$ | $\lnot p \lor q$
T | T |$\quad$ T $\quad$|$\quad$ T
T | F |$\quad$ F $\quad$|$\quad$ F
F | T |$\quad$ T $\quad$|$\quad$ T
F | F |$\quad$ T $\quad$|$\quad$ T

Both expressions evaluate false if and only if $\,p\,$ is true and $\,q\,$ is false.

For developing a bit of intuition regarding the conditional (logical implication): see, e.g.,
$(1)$ this post, and
$(2)$ this post.

Source 1 : http://plus.maths.org/content/os/issue36/features/nishiyama/index.
I understand this argument, but it does not feel intuitive.

  We are given that $\color{green}{P \Longrightarrow Q}$.
  $\boxed{\text{Case 1 of 2 : } \color{green}{P \Longrightarrow Q} \text{ true}}$ Substitute the green into the tautology  $\color{green}{P} \vee \lnot P$ to get: $\color{green}{Q} \vee \lnot P$.
  $\boxed{\text{Case 2 of 2 : } \color{green}{P \Longrightarrow Q} \text{ false}}$ Since an argument is valid if the premises cannot all be true without the conclusion being true as well, thus this case means $[\text{$P$ is true $\& \, Q$ is false]} \iff [\text{$\lnot P$ is false $\& \, Q$ is false]} \iff [\text{$\lnot P \vee Q$ is false]}$.

  Altogether, the 2 cases result in:
  $\left\{ \begin{array}{rcl}
\color{green}{P \Longrightarrow Q} \text{ true $\equiv [\lnot$ P $\vee$ Q] is true} \\
\color{green}{P \Longrightarrow Q} \text{ false $\equiv [\lnot$ P $\vee$ Q] is false}
\end{array}\right.$.
  Thus, the Conditional Law has been proven.


What is the sum of the prime factors of $2^{16}-1$? I know $2^{10}=1024$ and $2^6=64$, but it seems they are not very helpful in solving this problem. There must be a trick to solve the problem in an easy way.

  What is the sum of the prime factors of $2^{16}-1$?

Every student should know the powers of two up to $2^{20}$ like the back of his/her hand, or in the case of a student with no hands, like some other familiar body part that would serve my rhetorical purpose.
Therefore we have $$2^{16}-1=65536-1 = 65535$$
Now any schoolchild can tell you that the semiprime $771$ is a factor: $$65535= 771\cdot 85$$
The rest is trivial:
$$65535=771\cdot 85 = 3 \cdot 5 \cdot 17 \cdot 257$$
Get a stray toddler to do the addition for you, to arrive at the final answer of
$$\boxed{282}$$


How does $1/e^{(1/\infty)}$ equal $1$? My professor had us solve an improper integral, the problem or work I did correctly, however, when I got to the final part of the answer, I got $1/e^{1/\infty} - 1/e$.

My professor got this as well, but when she put the actual value, she put $1 - 1/e$.

I thought that $e^{(-1/\infty)}$ equals zero, because anything over infinity equals zero. Am I wrong? Why does it equal 1?

First of all, $\frac{1}{x^{1/\infty}}$ doesn't equal anything because $\infty$ is not a number.

However, $\lim_{x\to\infty} \frac{1}{e^{1/x}}=\frac{1}{e^0}=1$

The bit that reads (-1/inf) is equivalent to zero. So now doing the exponential you have exp(0), which of course is 1.


How to find the last non-zero digit of $50!$ A week ago i made a similar question but nobody help me, i´ve been trying but i still don't get it.

I want to know how to find the last non-zero digit of $50!$.

my try:

First i have to know how much Zeros $50!$ has so i did this:

$$E_{5}50 = \sum _{1\leq k <n} \Bigg[\frac{50}{5^{k}}\Bigg] =\Bigg[\frac{50}{5}\Bigg] + \Bigg[\frac{50 }{25}\Bigg] = 12$$

So $50!$ has $12$ zeros which means that the last digit of $\quad\frac{50!}{10^{12}}\quad$ is the number that i´m looking for.

so if $x = \frac{50!}{10^{12}}$ i need to find $x (mod 10)$ to get it but this is such a big number and i still don't know how to reduce it.

Thanks in advance!!

It is enough to find $x \mod 2$ and $x \mod 5$ in order to know $x \mod 10$. It is easy to show that $x \mod 2 = 0$, so all you really need to do is find $x \mod 5$. Since $2^{12}$ is invertible modulo $5$, it is enough to do this for $2^{12} x \mod 5$ and then divide by $2^{12}$. The number $2^{12} x = \frac{50!}{5^{12}}$ is not too hard to write as a product of several numbers, and after reducing modulo $5$, you'll see that there is a lot of repetition in these numbers, which simplifies the calculation.

My Solution:: calculation of last non zero digit in $50!$

Now first we will calculate number of zeros at the end of $50!$, which is obtained

when we multiplied $2$ and $5$. So we will calculate no. of $2$ and $5$ in $50!$

$\displaystyle 50! = \lfloor \frac{50}{2}\rfloor +\lfloor \frac{50}{2^2} \rfloor+\lfloor \frac{50}{2^3}\rfloor+\lfloor \frac{50}{2^4}\rfloor+\lfloor \frac{50}{2^5}\rfloor+........... = 25+12+6+3+1 = 47$

$\displaystyle 50! = \lfloor \frac{50}{5}\rfloor+\lfloor \frac{50}{5^2}\rfloor+..... = 10+2 = 12$

So Total no. of zeros at the end of $50! = 12$

Now $\displaystyle 50! = \lfloor \frac{50}{3}\rfloor+\lfloor\frac{50}{3^2}\rfloor+\frac{50}{3^3}\rfloor+..... = 16+5+1 = 22$

Now we can write $\displaystyle 50! = 1\times 3^{22}\times 7^8\times 11^4 \times 13^3 \times 17 \times 19\times  23\times 29\times 31 \times  17\times 37 \times 41 \times 43 \times 23 \times 47 \times 10^{12}\times 2^{35} = \bf{last digit\; (6)} = 6$


A finite group of even order with no normal subgroup of index 2. Let $G$ be a finite group of even order and suppose that there exist an element $x\in Z(G)$ of order $2$, i.e $x$ is in the center of $G$ and satisfying $x^2=1$, $x\neq1$.
Is it possible that $G$ does not contains a normal subgroup of index $2$? I guess the answer is yes but I fail to find any examples of such groups.

Take the binary tetrahedral group $2T\cong Q_8\rtimes C_3$.  It clearly has a central element of order $2$.  And it doesn't have an index-2 subgroup (as it must take the form $C_4\rtimes C_3\subset Q_8\rtimes C_3$ but none of the $C_4$ in $Q_8$ is actually normalised by $C_3$).

The alternating groups, $\frak{A}_n$ do not have an index $2$ subgroup for $n\ge 4$.  The alternating group on $4$ letters is the smallest example, with only $12$ elements.


Solving the inequality $-1<\frac{2}{x}$ What is the range of $x$ for inequality $-1<\frac{2}{x}$ ?

My attempt is as follows:

$$-1<\frac{2}{x}$$

$$-1\cdot{x}<2$$

Multiplying by $-1$ on both sides, which changes sign, we get:

$$x>-2$$

So according to this resultant equation lets put some value of x into the first equation.

Let's take $x=-1$

$$-1<\frac{2}{-1}$$

$$-1<-2$$

I am not able to understand what is wrong here, why am I getting contradictory result when I put values of $x$ in the original question.

THE GIVEN INEQUALITY HAS GOT RANGE AS X<-2 AND X>=0.
Reason for it is
                          2/X >-1.
                         Implies two cases 1) if 2/X >0.
                                                               Implies X>=0
                                                           2)if -1<2/X<0.
                                                               Implies X<-2.


Entire functions such that $f(z+\lambda_1)=af(z) \; , \; f(z+\lambda_2)=bf(z) $ Let $\lambda_1$ and $\lambda_2$ be complex numbers with nonreal ratio. Let $f(z)$ be an entire function and assume there are constants $a$ and $b$ such that $$f(z+\lambda_1)=af(z) \;\;\;\;,\;\;\;\; f(z+\lambda_2)=bf(z)  $$ for all $z$. Prove that $f(z)=Ae^{Bz}$ , where $A$ and $B$ are constants.

I think the idea is to build a doubly periodic entire function, but I'm not sure if it is $\displaystyle \frac{f(z)}{e^{Bz}}$.

This is exercise 10 from chapter 1 of the book "Modular forms and Dirichlet series" by Tom Apostol.

Any help would be appreciated.

Hint: show there exists a $B$ such that $e^{B\lambda_1} = a$ and $e^{B\lambda_2} = b$. Then consider the function $f(z)/e^{Bz}$, and use what you know about doubly periodic entire functions.


$L^p$ space is separable if and only if measure space separable I am currently dealing with the following question:

Let $(E,\mathcal{A},\mu)$ be measure space, $p\in[0,+\infty)$. Show that $L^{p}(\mu)$ has a countable dense set iff there exists $(A_n)\in \mathcal{A}^{\mathbb{N}}$ such that $\forall n\in \mathbb{N},\ \mu(A_n)<\infty$ and $\forall \epsilon>0,\ \forall A \in \mathcal{A}\ s.t.\ \mu(A)<\infty, \exists n\in \mathbb{N}\ s.t. \mu(A_n\Delta A)\leq \epsilon$.

For the first part, to show $L^p$separable, I have a sketch of proof that I am not sure of: let $\mathcal{F} = \{ \text{finite sum of functions in the form } f_{n,k} = q_k \mathbb{1}_{A_n}\}$, where $q_k\in \mathbb{Q}$ and $A_n$ is a member of the countable dense set. Then $\mathcal{F}$ would be dense in the set of integrable simple functions. By that simple functions are dense, we could reach that $\mathcal{F}$ is dense in $L^p$. But for the converse way, I really have no idea.

Thanks!

If $L^p$ is separable let $G$ be a countable dense subset. For rational $q,q'$ with $q<q'$ and $0\not \in [q,q']$ and for $g\in G$ let $H(g,q,q')=g^{-1}[q,q').$ Let $\{A_n: n\in \Bbb N\}$ consist of the empty set and  every $H(g,q,q').$

If $A\in \mathcal A$ with $0<\mu(A)<\infty,$ let $f=\chi_A$ be the characteristic (indicator) function of $A.$ Given $\epsilon >0,$ take $g\in G$ with $\int |f-g|^pd\mu<\epsilon^p \mu(A)$   and consider $H(g,1-r,1+r)$ where $r\in \Bbb Q^+$ is arbitrarily small.


Best way to express 2014 In my class, I always write the date using mathematical formulas, or cool little equations. I want to show my students that even the most mundane seeming number often has fascinating features, and its own beauty - that's the reason I got into mathematics, and I want to pass it down.

For example, for 30, I wrote $\frac{6!}{4!}$.

Now, 2014 has kind of stumped me. The best I could come up with was this, using factorials:

$$(2!(2!+2!(4!))+3!)(4!-3!+1!)$$

But, this isn't the most attractive, or interesting, equation.

What do you think the best (nerdiest?) way to write 2014 is?

Looking $2014$ up in the OEIS turns up:

$$2014=13^3-13^2-13^1-13^0$$

In general, looking a number up in the OEIS is probably a reasonable way to turn up pleasing identities.

If anyone went to HCSSiM, we have a tradition of worshiping the number $17$.

So I would say the coolest way to express $2014$ is $$2014=2 \times 19 \times 51$$

It is easy to show that this neat fact: $2014$ is in fact the smallest number that can be expressed as a product of three distinct positive integers that are all congruent modulo $17$.


quadratic residues and prime divisor Prove that exist a many infinitely positive integers $n$  such that $n^2+1$ have a prime divisor greater than $2n + \sqrt{2n}$.

I was trying to solve but without interesting advances.

Any idea would be appreciated. Thanks in advance!

We know that there are infinitely many numbers n  such that n^2+1 is prime. And it is easy to prove that 2n+(2n)^0.5 < n^2+1.


Square three digit numbers, the efficient way I would like to square a three digit number in my head.
Now I know that the formula is

$$ ( X + r )  ( X - r ) + r^2 = X^2 - rX + rX - r^2 + r^2 = X^2
$$
Where $\,r\,$ is a number such that $\,X + r\,$ is divisible by $10$ and/or $100$

Now the problem is that, I would like to first figure out whether finding the $r$ such that the $3$ digit number is divisible by $100$ or $10$ would be more efficient.

If I choose $r < 10$ then the $\,( X + r )  ( X - r )\,$ becomes quite unpleasant. If I choose $r < 100$ then the $r$ itself will have to be broken into pieces such that

$\begin{array}\\
( X + r ) ( X - r ) + [ ( r + j )  ( r - j ) + j^2 ]
&=   ( X + r )  ( X - r ) + ( r^2 - jr + jr - j^2 + j^2 )\\
&=( X + r ) ( X - r ) + r^2\\
&= X^2 - rX + rX - r^2 + r^2\\
& = X^2\\
\end{array}
$

This kind of yields recursive solution where any number squared works. The job is much more easier, but the person has to memorize more numbers while continuing to do more math.

So which method would you recomend? Or if you would have some other method I would love to hear it.

If you choose recursive method how do you memorize numbers in an efficient way without having numbers collide in your brain?

Thanks to anyone for their response, and sorry if tags are off, I am unsure which tag fits my question.

Many mental calculations are easier the more facts you memorize.  Knowing the squares up to $31^2=961$ can make it easier, reducing the need to go all the way to single digits.  Also the fact that $(10n+5)^2=100n(n+1)+25$, for example $65^2=(6\cdot7)25=4225$.  If you break it all the way to individual digits, I find it easier to keep track of my place if I start with the most significant digits and add as I go, so $359^2=300^2+2\cdot300\cdot50+\ldots =90000+30000+\ldots$
$=120000+ 50^2+\ldots = 122500+2\cdot300\cdot9+\ldots=127900+2\cdot50\cdot9+9^2$ where for many purposes you can quit early when you have the precision needed.

to square a 3 digit number: example 237^2

your 37 (the number in the tens and ones position) becomes: a

your 237 (the entire number) becomes: b

your 2 (the digit in the hundreds position) in 237 becomes: x

your 3 (the digit in the tens position) in 237 becomes: y

and your 7 (the digit in the ones position) in 237 becomes: z

The equation to square a 3 digit number is :

(100x)^2 + 200xa + (10y)^2 + 20yz + z^2 = b^2

(100*2)^2 + 200*2*37 + (10*3)^2 + 20*3*7 + 7^2 = 237^2

40 000 + 14 800 + 900 + 420 + 49 = 56 169


Prove that $\sum\limits^\infty_{n=0}\frac{3n^2+2} {n \cdot (5n-1)^2}$ is convergent How can I prove that $\sum\limits^\infty_{n=0}\frac{3n^2+2} {n \cdot (5n-1)^2}$ is convergent? I failed doing it with the comparison test and root test aswell as fraction test seem far too complicated to me. Is there an easy way?

See Limit Comparison Test. As $a_n$ is of order $1/n$ the series will diverge.


How to mathematically describe the number of Element x in a set I am trying to formulate the following.

I have a Set A={x, y, z}, I also have a Set B, C and D, which all are subsets of A. It is not exactly defined which elements are in B, C and D. I only want to define a constraint so that the sum of all elements x in B, C and D equals 1.

What would be the mathematically correct way to describe this constraint? I really have a problem finding the correct notation for something like this.

Since these are sets (as opposed to multisets), an equivalent constraint seems to be that the element $x \in A$ appears in exactly one of the sets in $\mathcal F = \{B,C,D\}$. If this is what we want, then we can formulate this as:
$$
\sum_{S \in \mathcal F} |\{x\} \cap S| = 1
$$

If I understand correctly, your constraint should read

$$ \sum_{x \in B\cup C\cup D} x = 1 $$


Finding the common difference and hence, the sum of an A.P Find the sum to $25$ terms of an A.P with the first four terms as $1, \log_yx, \log_zy,-15\log_x z$.

My attempt:
I started out with,

$2\log_yx = 1+\log_zy$

and,

$2\log_zy = \log_yx -15\log_xz$

Further simplifying the equations led me nowhere. The work was getting too tedious. And since the exam in which I was supposed to solve this question only gives exactly 180 sec to solve this problem, I thought there might be some other, smarter way.

Any help would be appreciated.


Composite Numbers and Divisors Problem 10 What would be all the possible values of $Z$ if $Z$ had to be a positive composite number and if the product $2017\times Z$ would have precisely four divisors?

I thought that there would be no such composite numbers $Z$ because $Z$ has to be a prime number as the divisors would have to be the product itself, $2017$, $1$ and $Z$.

Is this correct?

The only numbers having exactly four divisors are those of the form $p_1p_2$ where the primes are distinct and of the form $p^3$. The only possibility is $Z=2017^2$ because of the given condition that $Z$ be composite.

Let $n$ be a positive integer with prime decomposition $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$

Then the number of divisors of $n$ is $(a_1+1)(a_2+1)(a_3+1)\cdots (a_k+1)$

For a number to have precisely four divisors, then that implies that it will either be of the form $n=p_1^1p_2^1$ or it will be of the form $n=p_1^3$

For your specific problem, you notice first that $2017$ is prime and we want $n=2017\cdot Z$ to be a number with four divisors.  This implies that either $n=2017\cdot p$ for some prime $p\neq 2017$, or that $n=2017^3$ making $Z=2017^2$.

Since the problem had the stipulation that $Z$ must be composite, that rules out the first possibility making the only possibility $Z=2017^2$


Are $\delta(x-5)$ and $\delta(5-x)$ the same function? As the title says, I'm confused whether $\delta(x-5)$ and $\delta(5-x)$ are the same function.

Similarly, are $\delta(x-5,y-6)$ and $\delta(5-x,6-y)$ the same function?

To, me it seems they are! But want a second opinion!

$\delta_t$ produces a distribution, meaning it generates a linear map $T_{\delta_t} : C_c^\infty \mapsto \mathbb{R}$, $\textit{defined}$ by

$$T_{\delta_t} (\phi) = <\delta, \phi > = \int \delta(t) \phi(t)dt :=\phi(0) $$
The first three equalities are all simply the same thing with different notation.The integral is more formal and makes computations more clear. In fact $\delta$ is homogeneous of degree -1 meaning that
$$\delta(\alpha x) = \frac{\delta(x)}{|\alpha|}$$
for $\alpha  \neq 0$. This can be shown by scaling the integral. So $\alpha = -1$ gives $\delta(x) = \delta(-x)$ as a distribution. Thus
$$T_{\delta_{x-5}}(\phi) = \int\delta(x-5)\phi(x)dx = \phi(5) = \int\delta(5-x)\phi(x) = T_{\delta_{5-x}}(\phi)$$
And similarly for the 2 dimensional case.

The expression $\delta(t)$ accepts as input a real number $t$, and returns as output either the number $1$, if $t=0$, or else the number zero, if $t\neq 0$. That is
$$
\delta(t)=\left\{
\begin{aligned}
1 & \quad \text{if}\, t = 0 \\
0 & \quad \text{if}\, t\neq 0
\end{aligned}
\right.
$$
If follows from this definition that $\delta(5-x)$ is equal to $1$ if and only if $5-x=0$, that is, if and only if $5=x$, and $\delta(x-5)$ is equal to $1$ if and only if $x-5=0$, that is, again, if and only $5=x$. Conclusion: $\delta(5-x)=\delta(x-5)$ for every real $x$, and more generally $\delta(a-b)=\delta(b-a)$ for every pair of real numbers $a,b$.


Combinations and Statistics Question A bin with 100 parts contains 8 that are defective. A sample of 10 parts are obtained. How many samples contain exactly 1 defective part?

My answer was 10 as each defective part is mathematically indistinguishable from each other and the same for the non defective parts. Therefor, the defective part can occur in 10 different places in the sample leading to 10 different possible samples. I feel like the information before that was misleading.

Edit: I want to clarify that I think the question was poorly worded and ambiguous which is why I am looking for clarification and maybe my interpretation was flawed.

Your answer is flawed because it doesn't take into account how many defective pieces there are. Also, you are not actually told that the defective pieces are indistinguishable. You could have a bin of 100 different parts, 8 of which are defective.

To count the number of 10-piece samples that contain exactly 1 defective piece, you need to count how many ways there are to choose 1 defective piece, and how many ways there are to choose 9 non-defective pieces, and multiply those numbers together. You do not care what order these pieces are in, by the way. The samples don't have any ordering to them.


Construct a triangle, given the altitude, median, and angle bisector for a vertex. We are given that in a triangle, say $\triangle ABC$, the altitude is dropped from  A to the opposite side of the triangle. Also given is the median from A and it's the angle bisector.
With help of the above conditions, construct $\triangle ABC$.

I tried solving this problem. I know that if it is an equilateral or isosceles triangle the question can be easily done. But there should definitely be a general proof for any triangle.

Construct a triangle, given three distinct lengths of cevians from the
same vertex, say, $A$, the median $m_a$, the angle bisector $\beta_a$
and the altitude $h_a$, $h_a<\beta_a< m_a $.

Known relations between $m_a,\, \beta_a,\, h_a$
and the side lengths $a,b,c$ are:
\begin{align}
2m_a^2&=b^2+c^2-\tfrac12a^2
\tag{1}\label{1}
,\\
\beta_a^2&=
bc\left(1-\frac{a^2}{(b+c)^2}\right)
\tag{2}\label{2}
,\\
h_a^2 &=
\frac{4b^2c^2-(b^2+c^2-a^2)^2}{4\,a^2}
\tag{3}\label{3}
.
\end{align}
Excluding $b,c$ from \eqref{1}-\eqref{3},
we get a quadratic expression in $a^2$
\begin{align}
(a^2)^2-8\,(m_a^2-2h_a^2)\,a^2
&+\frac{16(m_a^2-\beta_a^2)(\beta_a^2\,m_a^2-\beta_a^2\,h_a^2-m_a^2\,h_a^2)}{\beta_a^2-h_a^2}
=0
\tag{4}\label{4}
,
\end{align}
which gives the value of the side length $a$.
Equation \eqref{1} provides the value of $b^2+c^2$ in terms of $a$,
and \eqref{3} provides the value of $b^2c^2$ in terms of $a$,
which gives another quadratic equation with the roots $b^2,c^2$.
So the expressions for
the side length $a$ and
the other two side lengths
in terms of $a$ are
\begin{align}
a_{1,2}&=
2\sqrt{m_a^2-2h_a^2
\pm
(2h_a^2-\beta_a^2)\sqrt{\frac{m_a^2-h_a^2}{\beta_a^2-h_a^2}}}
\tag{5}\label{5}
,\\
b,c&=
\tfrac12\sqrt{4m_a^2+a^2
\pm
4a\sqrt{m_a^2-h_a^2}}
\tag{6}\label{6}
.
\end{align}
Example
\begin{align}
h_a&=3
,\quad
\beta_a=4
,\quad
m_a=5
.
\end{align}
Eq. \eqref{4} gives two roots
\begin{align}
a_1&=
\tfrac27\,\sqrt{343+56\sqrt7}
\approx 6.332
,\\
a_2&=
\tfrac27\,\sqrt{343-56\sqrt7}
\approx 3.988
,
\end{align}
corresponding
\begin{align}
b_1,c_1&=
\tfrac27\,\sqrt{392+14\sqrt7
\pm 14\sqrt{343+56\sqrt7}}
\approx
7.768649668. 3.113762020
,\\
b_2,c_2&=
\tfrac27\,\sqrt{392-14\sqrt7
\pm 14\sqrt{343-56\sqrt7}}
\approx
6.702893563, 3.608848334
.
\end{align}
Verification confirms
that triple $(a_1,b_1,c_1)$
indeed corresponds to
the triangle with given $h_a,\beta_a,m_a$:

Edit
As the
answer
to the follow-up
question
proves,
the only valid root is always $a_1$,
\begin{align}
a_{1}&=
2\sqrt{m_a^2-2h_a^2
+
(2h_a^2-\beta_a^2)\sqrt{\frac{m_a^2-h_a^2}{\beta_a^2-h_a^2}}}
.
\end{align}

In the indicated case it is given that the median $m_a$ from $A$ and the angle bisector $w_A$ at $A$ coincide. In this case the triangle is isosceles, and the altitude from $A$ coincides with the line $m_a=w_A$. It follows that the three occurring lengths coincide, and are equal to the height $h_a=|AM_a|$, where $M_a$ is the midpoint of $BC$ on the base of the triangle. When the given lengths $m_a$, $\beta_a$, and $h_a$ do not coincide there is no triangle having the desired properties.
On the other hand, when $m_a=\beta_a=h_a$, the given information does not determine the two points $B$, $C$ at equal distance from $M_a$ on the base.


pictorial illustration of simplicial complexes Consider the following two complexes (Bruns&Herzog p.215):

By just looking at the complex on the left, i am not sure
how to read its faces. Surely its vertices are $v_1,v_2,v_3,v_4,v_5$.
The fact that e.g. $v_1$
and $v_5$ are connected via an edge, leads me to believe
that $\left\{v_1,v_5\right\}$ is a face. The fact that
the triangle $\left\{v_1,v_2,v_5\right\}$ is dotted leads
me to believe that $\left\{v_1,v_2,v_5\right\}$ is another
face. But how about e.g. $\left\{v_1,v_2,v_4,v_5\right\}$?
Is this a face? Or how about $\left\{v_1,v_2,v_3,v_4,v_5\right\}$?
Is this a face? And how can we distinguish between the two complexes
where e.g. $\left\{v_1,v_2,v_4,v_5\right\}$ is face in the first
but it is not a face in the second?

On the other hand, by looking at the complex on the right, i can tell
that e.g. $\left\{u_2,u_4,u_5\right\}$ is not a face.

they are not faces:
 if $\left\{v_1,v_2,v_4,v_5\right\}$ be a face there was a pyramid ($\left\{v_1,v_4\right\}$ is missing).
 $\left\{v_1,v_2,v_3,v_4,v_5\right\}$ being a face can not be shown in a picture, because it is of dimension 4.
 the complex on the right: $\left\{u_2,u_4,u_5\right\}$ is not a face

USe the definiton of simplicial complex to read the faces. A simplex S of $k+1$ point say $p_i$ is the affine combination with non negative coefficient $\alpha_i$. A face is a subsimplex that is $T\subset S$. Convex hull of T is a simplex that is $\alpha_i=0$ if $p_i$ does not belong to T.
    Definiton: A Simplicial complex is a finite collection  K of simplex such that
1) $\sigma\in K$ and $\tau\leq\sigma$ ($\tau$ is a subsimplex of $\sigma$)implies
$\tau\in K$, and
2) $\sigma$,$\upsilon\in K$implies $\sigma\cap\upsilon\leq\sigma,\upsilon$.


The real part of a complex number such that $|z|=\max\{|z-2|,|z+2|\}$ If |z|=max{|z-2|,|z+2|} then -
INFERRENCE - |Re(z)|=1

Is the inferrence incorrect?

My approach is -
|z|=|z-2| when |z-2| {i.e. distance of z from 2 is greater}is greater OR |z+2| when |z+2| is greater.

|z-2|>|z+2| means Re(z)>0....and so on.

If $\lvert z\rvert=\lvert z-2\rvert,$ then one can show that $\operatorname{Re} z=1,$ and so $\lvert z+2\rvert\gt\lvert z\rvert.$ But then $\lvert z+2\rvert\gt\lvert z-2\rvert$ by assumption, whence $$\lvert z\rvert\lt\max\bigl(\lvert z-2\rvert,\lvert z+2\rvert\bigr).$$

On the other hand, if $\lvert z\rvert=\lvert z+2\rvert,$ then one can show that $\operatorname{Re} z=-1,$ and so $\lvert z-2\rvert\gt\lvert z\rvert.$ But then $\lvert z-2\rvert\gt\lvert z+2\rvert$ by assumption, whence $$\lvert z\rvert\lt\max\bigl(\lvert z-2\rvert,\lvert z+2\rvert\bigr).$$

Hence, there is no $z$ such that $$\lvert z\rvert=\max\bigl(\lvert z-2\rvert,\lvert z+2\rvert\bigr),$$ so (vacuously), if $z$ satisfies said impossible condition, then $\lvert\operatorname{Re} z\rvert=1.$ More interestingly, we can see by the above reasoning that $$\lvert z\rvert=\min\bigl(\lvert z-2\rvert,\lvert z+2\rvert\bigr)$$ if and only if $\lvert\operatorname{Re} z\rvert=1.$

So , the conclusion is the given inference is right (though vacuously) and if max is replaced with min , the INFERENCE is more meaningful and correct


What are some good Fourier analysis books? I have taken real analysis, but never learned Fourier analysis. What is a good book to get started? I'm not sure the Stein book would be good.

"Fourier analysis" by T.W. Körner and its accompanied exercise book are the best.

please don't propose books that are impossible to find on internet, there are enough books and courses that are free to read on internet,

and the scientifics that you are should understand it is a huge social progress that everyone can FREELY  access to the scientific knowledge.

look at any of the first links for :

google / fourier transform pdf

google / discrete fourier transform pdf

google / distribution fourier transform pdf

google / laplace transform pdf

google / filter convolution pdf

google / linear differential equation pdf

but be careful, it can take ~ 5 to 10 years to fully study the subject, it is so vast


The sequence $u_n$ is defined by $u_0 = 0, u_1 =1, u_n = 3u_{n-1}+u_{n-2}$. Calculate $\lim_{n\rightarrow \infty}u_n/u_{n-1}$ The sequence $u_n$ is defined by $u_0 = 0, u_1 =1, u_n = 3u_{n-1}+u_{n-2}$. Calculate $\lim_{n\rightarrow \infty}u_n/u_{n-1}$

The Solution:

$u_n$ is given by a linear combination of powers $\lambda_1^n, \lambda_2^n$ of $\lambda^2=3\lambda+1$ (with nonzero coefficients), so the limit of the ratio $u_n/u_{n-1}$ is the root $(3+\sqrt{13})/2$ of largest absolute value.

Question - without looking at the solution, I would set it up as a matrix equation

\begin{gather}
 \begin{bmatrix} u_{n} \\u_{n-1} \end{bmatrix}
 =
  \begin{bmatrix}
   3 &
   1 \\
   1 &
   0
   \end{bmatrix}
 \begin{bmatrix} u_{n-1} \\u_{n-2} \end{bmatrix}
 =
  \begin{bmatrix}
   3 &
   1 \\
   1 &
   0
   \end{bmatrix}^{n-1}
 \begin{bmatrix} u_{1} \\u_{0} \end{bmatrix}
 =
  \begin{bmatrix}
   3 &
   1 \\
   1 &
   0
   \end{bmatrix}^{n-1}
 \begin{bmatrix} 1 \\0 \end{bmatrix}
\end{gather}

and then I can diagonalize

\begin{gather}
A = \begin{bmatrix}
   3 &
   1 \\
   1 &
   0
   \end{bmatrix} = PDP^{-1}
\end{gather}
where D is the diagonal matrix with the entries $\lambda = (3 \pm \sqrt{13})/2$, solve for $u_n$ and $u_{n-1}$ and presumably reach the same conclusion.

Can someone explain the given solution to me? I see that $u_n$ is given by a linear combination of powers $\lambda_1^n, \lambda_2^n$ of $\lambda^2=3\lambda+1$ (with nonzero coefficients), but not sure how they get to the conclusion.

For such a linear recurrence, the general solution is $\newcommand{\la}{\lambda}a\la_1^n+b\la_2^n$. Here $\la_1>|\la_2|$ and so, if $a\ne0$
$$\frac{u_{n+1}}{u_n}=\frac{a\la_1^{n+1}+b\la_2^{n+1}}
{a\la_1^n+b\la_2^n}
=\la_1\frac{1+(b/a)(\la_2/\la_1)^{n+1}}{1+(b/a)(\la_2/\la_1)^{n}}.
$$
As $|\la_2/\la_1|<1$ this tends to $\la_1$.

Of course, you may be unlucky and have a particular solution with $a=0$,
in which case this argument fails. But here, you don't.

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \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{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#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{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

  Following your result:

\begin{align}
&\text{As}\quad n \to \infty\,,
\\ &\
{u_{n} \choose u_{n - 1}} = \pars{\begin{array}{cc}\ds{3} & \ds{1} \\ \ds{1} & \ds{0}\end{array}}^{n - 1}
{1 \choose 0}
\\[2mm] &\ \sim
\pars{3 + \root{13} \over 2}^{n - 1}
{{3 + \root{13} \choose 2} \over \root{\pars{3 + \root{13}}^{2} + 4}}\,
{\pars{3 + \root{13} \quad 2} \over \root{\pars{3 + \root{13}}^{2} + 4}}
{1 \choose 0}
\\[2mm] &\ \propto
\pars{3 + \root{13} \over 2}^{n - 1}
{3 + \root{13} \choose 2}
\implies
\bbx{\lim_{n \to \infty}{u_{n} \over u_{n - 1}} = {3 + \root{13} \over 2}}
\approx 3.3028
\end{align}


Wrapping my head around different base-number systems this is my first post on this forum, I'm interested in mathematics but don't have any education beyond the high-school level in the subject, so go easy on me.

What I know right now: the base-10 system is a system of number notation that was more or less arbitrary selected over other number systems... if we were to change all the numbers in an equation to a different system, we could calculate the correct answer in that system.  There is no reason why the base 10 system is any more correct than the base 15 or base 5 system.  If this isn't true, please correct me.

Question 1: Firstly, is it possible to have a number system that is below 1?  I would assume no, because to do so would require some sort of notation capable of expressing a fraction, which would require a base-system at least equal to one or greater.  Am I wrong?  is it theoretically possible?

Question 1.5:  Is asking if you can have a base-number system that is not a whole number system an ironic question?  Like is asking if you can have a base 4.5 system a silly question because by saying "4.5" im assuming that I mean four and a half, and the half would be half of ten which implies a base 10 system? Is it possible to have a number-system that is between two integers?  Which leads to my third question

Question 2: what is it for a number to be a "whole number" when we relate the idea of being "whole" to the number system being used to express it?  Are some numbers whole in some systems but not whole in others?

Question 3:  If some numbers are whole in some systems but not in others, what implications does this have on prime numbers??

Thanks, Sam

Regarding number bases less than $1$ (Question 1), suppose you have a base-one-tenth number system. The first few integers in this system would be

$$1,2,3,4,5,6,7,8,9,0.1,1.1,2.1,3.1,4.1,5.1,6.1,7.1,8.1,9.1,0.2$$

The reason $0.1$ is the next integer after $9$ is that the base
of this number system, $b$, has the value we would normally call
$\frac{1}{10}$ (writing in base ten),
and the first place after the decimal point has place value $b^{-1}$.
And of course $\left(\frac 1n\right)^{-1} = n$,
for any $n$.

This is kind of a silly example since you can just write all your numbers
backwards and put the decimal point between the ones' place and the
tens' place. So it is not too surprising that I've never seen this
system explained before.

Moving on to Question 1.5,
a much more interesting system is the base-$\phi$ number system.
The number $\phi$ is also known as the Golden Ratio:
$\phi = \frac12(1 + \sqrt 5)$.

It turns out that all the powers of $\phi$ have the form
$\frac12(a + b\sqrt 5)$ for some integers $a$ and $b$,
and lots of nice cancellation can occur.
So if we allow only the digits $0$ and $1$
in this number system (these are the only non-negative integers
less than $\phi$), we can write the first few integers as

$$1, 10.01, 100.01, 101.01, 1000.1001, 1010.0001$$

But regarding Questions 3 and 4:
whatever system it is written in, a whole number is a whole number.
Since we're so used to using only whole-number-based systems,
the numbers written in base-one-tenth and base-$\phi$ in the lists above
(the "first few integers" in each base)
may not look like whole numbers, but nevertheless
that's what every single one of them is.

Or to put it another way,
each whole number is produced by adding $1$ to the number before it.
That is (essentially) the way the whole numbers are defined.
The numbering system you use may have some bizarre effects on how
you "carry" digits when adding $1$ to the previous whole number
causes the ones' place to "roll over", but as long as you do the
arithmetic operation correctly you will get the same actual number
as you would have gotten in any other base.
Likewise any other mathematical facts involving integers or fractions
are exactly the same in an number base; they may just look different
due to the different numerical notation.

Okay, so first I will mention a different way to think about bases. So for example, say you want to write 471 in base 5. So you start with a "471" in the units place:

471

Now, since we're in base 5, every 5 in the units place is worth 1 in the next place. So we can take 470 out of the units place and turn it into 94 in the next place to the left (Imagine this as repeatedly taking 5 out of the units place and adding 1 to the next place, 94 times). So our number is now:

94 1

Now, take out a 90 and add 18 to the next place to the left:

18 4 1

And once more:

3 3 4 1

So 471 is 3341 in base 5.

Now for question 1.5 (I'll get back to 1 later.) You give the example of base 9/2. What that would mean is that 9 in one place is worth 2 in the place to the left. So let's use our example of 471 again. We start with just a 471, as before:

471

Now, we can repeatedly take 9 out of the units place and add 2 to the next place. We do this 52 times, so we subtract 468 from the units place and add 104 to the next place:

104 3

Now you can take out 99 and put a 22 on the next place:

22 5 3

Take out an 18:

4 4 5 3

So 471 in base 10 is 4453 in base 9/2. Note that digits can be up to 8 in base 9/2. Now, I'll show an example of addition in base 9/2. Say you wanted to calculate 35 + 47, where all numbers are in base 9/2. First, just add all the digits pairwise:

   3   5
+  4   7
--------
   7  12

Now, noticing that 12 is more than 9, we can subtract a 9 and add 2 to the next place. So the number becomes 9 3. But now, notice again that you have a 9, so you can subtract it and add 2 to the next place again. So the final result is 203. So in base 9/2, 35 + 47 = 203.

For question 1, basically what you do when the base is less than 1, e.g. 1/5, is that when you take 5 out of one place, you add 1 to the place to the right instead of the place to the left. So you basically get the reverse of the number in base 5. For example, 48839 in base 5 is 9.3884 in base 1/5.

And for questions 2 and 3. Base systems are just a way of representing numbers, for our own convenience. But the way you represent a number does not change the number itself. So 471 in base 10 and 3341 in base 5 are still the same number. The base representations are just like a name we assign to a number. If you change the name of a number, you don't change its properties. So the concept of a whole number is unchanged. However, the way you tell if a number is a whole number may be different. In base 10 (or in any integer base), you can easily tell if a number is whole by making sure it has nothing after the decimal point (and no negative sign). In base 9/2, for example, it is not as easy to tell. 35, for example, is not whole in base 9/2. (it is equal to 37/2 in base 10).


Explanation of Fundamental Theorem of Algebra From Axler's Linear Algebra Done Right:

Fundamental Theorem of Algebra:
Every nonconstant polynomial with complex coefficients has a zero.

He proves this using complex anaylsis (which I havn't learnt yet). But then he notes:

All proofs of the Fundamental Theorem
of Algebra need to use some analysis, because the result is not true if C is
replaced, for example, with the set of numbers of the form $c+ di$ where $c, d$
are rational numbers.

Does this mean that the theorem isn't true when we restrict our polynomials to having rational complex coefficients?
edit That's how I read it, axler clearly meant the theorem doesn't hold if the roots were restricted to rational complex numbers.

The author possibly means that the theorem cannot be proven by mere algebra, because rational coefficients can generate irrational roots, which require more powerful methods, such as limits.


What are the probabilities of getting a "Straight flush" in a poker game? I'm not a pretty much fun of Poker, but I'd like to study that game.

What are the probabilities of getting a Straight flush in a Poker game considering this factors?

Number of playersHow are cards dealtWho is the first player

If you are dealt five cards, there are $4\times10 =40$ possible straight flushes ($4\times 9 =36$ if you exclude royal flushes) out of the ${52 \choose 5}= 2598960$ possible hands.  So the probability is $\dfrac{40}{2598960} = \dfrac{1}{64974} \approx 0.00001539\ldots$.

The probability will increase if you can have more than five cards to choose from.  The probability that somebody will have a straight flush will increase if the number of players increases.  It may reduce if you might drop out of the betting before seeing all five cards.

Try the book, mathematics of poker by bill chen. Decent read.


Show that the projection moves you closer to the set, i.e. $|P_C(x) - y| \leq |x-y|$ for all $y\in C$ Let $H$ be a Hilbert space with induced norm $|\cdot|$, with $C\subset H$ a closed, convex subset of $H$ and $P_C(x)$ the projection of $x$ onto $C$, i.e.,

$$P_C(x) = \arg\min\limits_{y\in C}|x-y|^2$$

I want to show the following trivial result,

$$\forall y\in C, \quad |P_C(x) - y|^2\leq |x-y|^2$$

I have tried a couple things but none have worked. The first was the following (let $y\in C, x\not\in C$):

$$|P_C(x) -y|^2 = |P_C(x)|^2 - 2\langle P_C(x), y\rangle +|y|^2 = |P_C(x)|^2 - 2\langle x, y\rangle +|y|^2 \\\leq |P_C(x)|^2 + |x-y|^2$$

I also tried this:

$$|P_C(x) - y|\leq |P_C(x) - x| + |x-y|\leq 2|y-x|$$

but the $2$ is ruining things for me. Can someone give me a hint?

Edit: here is what I came up with ultimately,

$$|x-y|^2 = |x-P_C(x) +P_C(x) - y|^2\\ = |x-P_C(x)|^2 -2\langle x-P_C(x), y-P_C(x)\rangle + |y-P_C(x)|^2\\
\geq -2\langle x-P_C(x), y-P_C(x)\rangle + |y-P_C(x)|^2\\
\geq |y-P_C(x)|^2$$

since the inner product is negative. Of course then we should actually show that the inner product is negative in general and this is basically the argument that bananach was referring to, I think.

Split $x-y$ into the path from $x$ through $P_C(x)$ and then in the orthogonal direction after some while. Then use Pythagoras. Let me know if you need details, but try just sketching this down on a piece of paper, it should become obvious.

Algebraically speaking, add and subtract $Px$ in |x-y|^2 and then use Pythagoras. The scalar product that appears is positive because $f(t)= |x-Px+t(y-Px)|^2$ is non decreasing in $t=0$ by definition of $Px$.

As $P_C(y)=y$ for $y\in C$ we know that $P_C(x)-y=P_C(x-y)$.  From here show for all $x\in H$ that $\|P(x)\|\leq \|x\|$.  For that purpose it's enough to prove
$$\|x\|^2=\|P_C(x)\|^2+\|x-P_C(x)\|^2.$$
Now that follows easily from $\langle x-P_C(x),P_C(x)\rangle=0$.


Prove the existence of limit of $x_{n+1}=x_n+\frac{x_n^2}{n^2}$ The problem is: Let $\{x_n\}$ be a sequence such that $0<x_1<1$ and $x_{n+1}=x_n+\dfrac{x_n^2}{n^2}$. Prove that there exists the limit of $\{x_n\}$.

It is easy to show that $x_n$ is increasing, but I cannot prove it is bounded to show the existing of limit. Anyone have any ideas?

Let $x_1 = t \in (0,1)$. For any $n \ge 1$, it is easy to see $x_n \ge 0$.
Since $e^y \ge 1 + y$ for all $y$, we have
$$x_n = x_1 \prod_{k=1}^{n-1} \frac{x_{k+1}}{x_k} = t \prod_{k=1}^{n-1} \left(1 + \frac{x_{k}}{k^2}\right) \le t\exp\left(\sum_{k=1}^{n-1} \frac{x_k}{k^2}\right)\tag{*1}$$

Notice

$x_1 \le t$.
if $x_n \le tn$, then $x_{n+1} \le n t + t^2 \le (n+1)t$.

By induction, we have $x_n \le n t$ for all $n$.

Substitute this into $(*1)$, we get

$$x_n \le t \exp\left(t\sum_{k=1}^{n-1}\frac{1}{k}\right)
\le t\exp\left(t(\log n + \gamma)\right)
\le  e^\gamma n^t$$
where $\gamma$ is
Euler-Mascheroni constant.

Substitute above into $(*1)$ again, we find
$$x_n \le t \exp\left(e^{\gamma} \sum_{k=1}^{n-1}\frac{1}{k^{2-t}}\right)
 \le t \exp\left( e^\gamma \zeta(2-t)\right) < \infty$$
where $\zeta(t)$ is the Riemann Zeta function.

The sequense is obviously monotone increasing since $x_{n+1}>x_n$. To prove that is converging we should show that is bounded.
Expanding $x^n$ and doing the addition we take:
$$
\eqalign{
x_{n+1} &= x_n + {x_n^2 \over n^2} \cr
x_{n} &= x_{n-1} + {x_{n-1}^2 \over {(n-1)}^2} \cr
x_{n-1} &= x_{n-2} + {x_{n-2}^2 \over {(n-2)}^2} \cr
&\cdots \cr
x_2 &= x_1 + {x_1^2 \over 1^2} \cr
&\rightarrow \cr
x_{n+1} &= x_1+ {x_{1}^2 \over {1}^2}+ {x_{2}^2 \over {2}^2}+\cdots+ {x_{n-1}^2 \over {(n-1)}^2}+ {x_{n}^2 \over {n}^2} \cr
&< 1+ {2 \over {1}^2}+ {2 \over {2}^2}+ \cdots+ {2 \over {(n-1)}^2}+ {2 \over {n}^2} \cr
&<1+ {2 \pi^2 \over 6}
}
$$


How to derive the Lambert W function series expansion? How do you use the Lagrange inversion theorem to derive the Taylor Series expansion of W(x)? How else can you derive a series expansion?

There is  a variant of  Lagrange inversion which  I like to  call poor
man's Lagrange  inversion which consists  in using the  Cauchy Residue
Theorem.

In the present case we are looking for the inverse to $ze^z$ so that
$$W(x) e^{W(x)} = x.$$
From the Cauchy Residue Theorem we get
$$[x^n] W(x)
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} W(z) \; dz.$$
Now put $W(z) = w$  so that $w e^w = z$ and $e^w (1+w)  \; dw = dz$ to
obtain (we use the branch that  takes $w=0$ to $z=0$, there is another
that takes $w=-\infty$ to $z=0$)
$$\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{n+1}} e^{-w(n+1)} e^w (w+w^2) \; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{n+1}} e^{-wn} (w+w^2) \; dw.$$
Extracting coefficients now yields
$$\frac{(-1)^{n-1} n^{n-1}}{(n-1)!}
+ \frac{(-1)^{n-2} n^{n-2}}{(n-2)!}
\\ = \frac{(-1)^{n-1}}{n!} n^{n-1}
(n - (n-1)) = \frac{(-1)^{n-1}}{n!} n^{n-1}.$$
We conclude that $$W(x) = \sum_{n\ge 1}
\frac{(-1)^{n-1}}{n!} n^{n-1} x^n.$$
Here is an example I at MSE and another example II at MSE of Lagrange inversion.
Addendum, Sep. 17 2020. For a more compact version use Lagrange
Inversion as presented in Analytic  Combinatorics by Flajolet and
Sedgewick. We first choose the branch  that has $W(0) = 0.$ We then have
$W'(x) e^{W(x)} + W(x) e^{W(x)}  W'(x) = 1$ so that $W'(1) = 1$. This
means we may write for $n\ge 1$ by  the Cauchy Coefficient Formula
$$[x^n] W(x) = \frac{1}{n} [x^{n-1}] W(x) =
\frac{1}{n} \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^n} W'(z) \; dz.$$
Putting $W(z) = w$ we also have $W(z) = z + \cdots$ so that the image  of
the circle in $z$ is a contour in $w$ that makes one turn by the  origin
and may in  turn be deformed to another small circle. We then have
$$[x^n] W(x) =
\frac{1}{n} \frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^n} \exp(-nw) \; dw.$$
This is by inspection
$$\frac{1}{n} [w^{n-1}] \exp(-nw) =
\frac{1}{n} \frac{(-n)^{n-1}}{(n-1)!} =
\frac{(-1)^{n-1}}{n!} n^{n-1}$$
as before.

It can be easily derived by applying the Lagrange inversion formula to $ze^z$ as it satisfies all criterias of the Lagrange inversion theorem, i.e. $f(0)=0$ and $f'(0)$ is non zero.


Showing that a transitive abelian permutation group is necessarily regular I am trying to show that a transitive, abelian permutation group acting on a set $X$ is necessarily regular, given this hint: 'Given $g \in G$, consider the set $X^g:=\{x \in X\,|\,gx=x\}$.  Show that if $G$ is transitive and abelian, then the only possibilities for $X^g$ are $\varnothing$ or $X$.'

I know that $X^g=X$ iff $g$ is the identity of $G$.  And...that's about all I've got.  I don't even see how, once the above is shown to be true, the result follows.

I would really appreciate some hints to help me in the right direction.

This is from Isaacs' Algebra: A Graduate course.  He introduces permutation groups first, but group actions haven't entered the scene yet.  I am alright with a hint in terms of actions though.

Thanks!

Hint: Let $1\not=g \in G$ and suppose $gx=x$ for some $x\in X$.  Then take another element $y\in X$.  Using the fact that $G$ is transitive, we have that some other element $h\in G$ such that $hy=x$.  Now use the fact that $G$ is abelian to derive a contradiction.

Let $gx=y$, $hx=y$, where $g,h$-elements of the group $G$; $x,y$-elements of the set $A$. $G$ acts on $A$
Let $t$ some element of $A$. As $G$-transitive,there exist $f$ in $G$ that
$t=fx$ As $G$ is abelian we have:
$$gt=g(fx)=(gf)x=(fg)x=f(gx)=fy=f(hx)=(fh)x=(hf)x=h(fx)=ht$$
So for any $t$ in $A$ we have $gt=ht$, so $g=t$, then $G$-regular


Determine all pairs of $(x,y)$ such that $\frac{x^2y+x+y}{xy^2+y+11}$ is an integer Here is a problem that I got:

  Determine all pairs of positive integer $(x,y)$ such that $\dfrac{x^2y+x+y}{xy^2+y+11}$ is an integer.

My attempt:

First notice that $(11, 11)$ is a solution. And if $\dfrac{x^2y+x+y}{xy^2+y+11}$ is an integer, then $xy^2+y+11|x^2y+x+y$. Hence $x^2y-xy^2+x-11|xy^2+y+11$.

And then I'm stuck from here. Can anyone help me? Thanks.

Hint: Notice that $$xy^2+y+11 \mid x(xy^2+y+11)-y(x^2y+x+y)=11x-y^2$$

Then you have three cases to check: $11x-y^2=0$, $11x-y^2<0$, and $11x-y^2>0$.

From $\dfrac{x^2 y+x+y}{x y^2+y+11}=k$ we get

$x^2 y+x+y=k x y^2+k y+11 k\quad(*)$

from which we deduce that

$x^2 y=k x y^2$ and then $x=ky$

plug this in $(*)$

$k^2 y^3+k y+y=k^2 y^3+k y+11 k$

that is $y=11k$ and then $x=11k^2$

Thus $(11k^2;\;11k)$ for any $k\in\mathbb{N};\;k>0$ satisfy the given equation

There are three more solutions that do not enter in the previous formula

$(7;\;1)$ which gives $3$

$(10;\;2)$ which gives $4$

$(121;\;1)$ which gives $111$

BTW

plugging $(11k^2;\;11k)$  in the given equation gives $k$ as result

hope this helps


Can a group of order 3000 be a simple group? Can a group of order 3000 be a simple group? How about the case of a group of order 1000?

A group of order 1000 has a normal Sylow 5-subgroup, so it cannot be simple.

A group of order 3000 has either a normal Sylow 5-subgroup or 6 of them. If there are 6 Sylow 5-subgroups, then the normalizer of a Sylow 5-subgroup has order 3000/6 = 500. A subgroup of order 500 cannot have a trivial normal core in a group of order 3000: Index of the normal core in the Sylow 5-subgroup must divide (6 - 1)! but 500 does not divide 120 = 5!.

let $G$ be a group of 3000 .Then by SYLOWS theorem $G$ contain a subgroup $H$ of order 1000. as$ 0(G)$ does not devide factorial of $(i(H))$. $H$ contain a non trivial normal subgroup $K$ of $G$ which contain in $H$. so $G$ is not simple. where $i(H)$ means index set of $H$ in $G$


If $T$ be an invertible linear operator on a finite-dimensional vector space over a finite field , then $T^n$ is the identity operator? If $T$ be an invertible linear operator on a finite-dimensional vector space over a finite field , then is it true that $T^n = I$ ( the identity operator) for some positive integer $n$ ?

Yes. The group of automorphisms of a finite group is finite.

A corrected version of Omnomnomnom's argument is as follows. An element of $T \in \text{GL}_n(\mathbb{F}_q)$ has a decomposition into Jordan blocks over $\overline{\mathbb{F}_q}$ which can be written $J = \lambda + S$ where $\lambda \in \overline{\mathbb{F}_q}$ and $S$ is the off-diagonal part of the Jordan block. We compute that

$$J^{q^i} = \lambda^{q^i} + S^{q^i}$$

and hence that $J^{q^i}$ is diagonal provided that $q^i \ge n$. Let $i$ be the smallest positive integer with this property, and let $j$ be the smallest positive integer such that $\lambda$ lies in $\mathbb{F}_{q^j}$. Since $\lambda$ is a root of the characteristic polynomial of $T$, which has degree $n$, we are guaranteed that $j \le n$. Then we find that

$$J^{q^i (q^j - 1)} = 1.$$

If the characteristic polynomial of $T$ factors into irreducible factors of degrees $n = j_1 + j_2 + \dots + j_k$, then we conclude that $T$ has order dividing

$$q^i \text{ lcm}(q^{j_1} - 1, q^{j_2} - 1, \dots q^{j_k} - 1).$$

The maximum possible value of this function as the $j_i$ vary can be thought of as a $q$-analogue of Landau's function, which is the largest possible order of an element of $S_n$. The term in front $q^i$ is at most $qn$ and can be dropped if $T$ is diagonalizable.

You can get a quicker and easier bound on the order by computing the order of $\text{GL}_n(\mathbb{F}_q)$, which is a standard and entertaining exercise. Since there are $q^{n^2}$ not-necessarily-invertible $n \times n$ matrices over $\mathbb{F}_q$ that gets you an upper bound pretty quickly (but not a divisibility condition).

We note that any field has an algebraic closure.  With that in mind, any operator $T^n$ over a finite field $k$ can be written using Jordan normal form with entries in the closure $\bar k$.

Thus, it suffices to verify that there is a particular $n$ such that $J^n = I$ for each Jordan block $J$.  Suppose that $\bar k$ has characteristic $p$.  Let $J$ be the Jordan block
$$
J = \pmatrix{\lambda&1\\&\lambda&1\\&&\ddots&\\&&&\lambda}
$$
with $\lambda \in \bar k \setminus \{0\}$ we note that
$$
J^n = \pmatrix{\lambda^n& n\lambda^{n-1} & n(n-1)\lambda^{n-2} &\cdots\\
0&\lambda^n & n\lambda^{n-1} & \cdots\\
&&\ddots
}
$$
Verify that $J^p$ is diagonal.  It follows that $(J^p)^{(p-1)} = I$.

So, in summary: if $T$ is an invertible operator on a finite-dimensional vector space over a finite field of characteristic $p$, then $T^{p(p-1)} = I$.


Are the lengths from this recursive construction a geometric sequence? In his 1999 review of Edward Tufte's Visual Explanations in the Notices of the AMS (third page), Bill Casselman gives a very pretty proof of the irrationality of the golden mean.  More precisely, Casselman shows that the side and diagonal of a regular pentagon cannot be commensurable.  The proof assumes the contrary, and thereby constructs a vanishing sequence of commensurable terms, which is a contradiction.

Upon closer inspection, however, I realized that there's a step in the proof that I cannot justify to my satisfaction.  Casselman does show that the commensurability of the side and the diagonal of a regular pentagon implies the existence of a strictly decreasing sequence of commensurable lengths (e.g. the sequence consisting of the lengths of the sides of successively constructed nested regular pentagons).  It is not clear to me, however, that he showed that this sequence converges to 0 (and not to some positive number).

Of course, convergence to 0 would follow immediately if we could establish that the sequence of side lengths is a geometric one, i.e. that successive terms in it are in a constant ratio to each other (which has to be $< 1$, since the sequence is strictly decreasing).  That this ratio is constant seems to me intuitively obvious somehow, but cannot I prove it rigorously.

Any help would be appreciated!

It definitely is a constant ratio. If $P$ and $P^\prime$ are regular pentagons with side lengths $l$ and $l^\prime$ respectively, then any distance $d$ between points $A$ and $B$ in $P$ obeys $d^\prime = d \frac{l^\prime}{l}$, where $d^\prime$ is the distance between points $A^\prime$ and $B^\prime$ in $P^\prime$ isomorphic to $A$ an $B$ in $P$, respectively.  One consequence of this is $a^\prime = \left( \frac{l^\prime}{l} \right)^2$, where $a$ and $a^\prime$ are the areas of $P$ and $P^\prime$, respectively.

Another way to look at it: Draw a schematic with only one iteration of the construction, and define the ratio of side-lengths $l^\prime/l = \rho$. For repeated constructions, redefine the points on your schematic adding a "prime" to everything. Then $l^{\prime\prime}/l^\prime = \rho^\prime$.  Is it possible that $\rho^\prime \neq \rho$?  The schematics are exactly the same.

OK, I think I have a an argument that formalizes my intuition.  (It is, admittedly, pretty tedious, but I guess this is inevitable, since it is formalizing a reasoning that is intuitively obvious to most people.)

Let $p_0$ be the construction's initial regular pentagon, let $s_0$ be the "base" of $p_0$ (namely, the side of $p_0$ that runs horizontally along its bottom), and let $t_0$ be the triangle formed by $s_0$ and the two diagonals of $p_0$ incident on it.  Now, for every $i \in \{1, 2, 3, \dots\}$, let $p_i$ be the first regular pentagon produced by the construction inside of $p_{i - 1}$.  Let $s_i$ be the (unique) side of $p_i$ that is parallel to $s_{i - 1}$, and let $t_i$ be the triangle formed by $s_i$ and the two diagonals of $p_i$ that are incident on it.

Now, define $F$ as the (composite) figure consisting of all the triangles $t_0, t_1, t_2, \dots$.  Likewise, define $G$ as the (composite) figure consisting of all the triangles $t_1, t_2, t_3, \dots$.  It is easy to see that the $i$-th triangle of $F$ (namely $t_{i-1}$) is similar to the $i$-th triangle of $G$ (namely $t_i$).  From this correspondence, and the details of the construction, it follows that $F$ is similar to $G$.1

Therefore, there is a "scaling factor" $\rho$ such that, for every length $l_F$ in $F$ and every corresponding length $l_G$ in $G$, the relation $l_G = \rho l_F$ holds.  In particular, for every side length $s_i$ in $F$ and corresponding side length $s_{i+1}$ in $G$, we have $s_{i+1} = \rho s_i$.

From this it follows immediately that $s_n = \rho^n s_0$, for all $n \in \{0, 1, 2, \dots\}$.

1This implication, admittedly, is not entirely watertight, since one could make a figure $G^\prime$ consisting of triangles $t_1, t_2, t_3, \dots$ that make up $G$, but independently repositioned (translated and/or rotated) such that $G^\prime$ would not be similar to $F$ even though the same pairwise similarity between their component triangles exists.  A more detailed accounting of all the angles involved would have to be made to establish the similarity of $F$ and $G$.  It is clear, however, that the construction fixes the position of each triangle $t_i$ precisely within $t_{i-1}$, and that the vertices of $t_i$ and $t_{i-1}$ together defines 4 other triangles, which, together with $t_i$ fully tile $t_{i-1}$.  The recursive construction preserves this tiling of each triangle, and it is easy to show that, for each $i$, the triangles that tile $t_i$ are similar to the corresponding triangles that tile $t_{i+1}$.  In this way the figures $F$ and $G$ may be construed as similar tilings of the similar triangles $t_0$ and $t_1$.


Efficient way to determine if a number is Perfect Square Is there an efficient method to determine if a very large number (300 - 600 digits) is a perfect square without finding its square root. I tried finding the square root but I realized that even for perfect squares, it wasn't efficient (I used newton's approximation method and it was coded in JAVA). I read somewhere about using modular arithmetic but I'm not quite sure how to do that. Can anyone give me a hint on how to proceed?

Thanks in advance.

Faster than binary search is to use an integer version of Newton's method: for $\sqrt{A}$ and an initial guess $x_0$ of the right order of magnitude, let $x_{n+1} = \left \lfloor \frac{x_n^2 + A}{2 x_n} \right \rfloor$.  I tried a 1200-digit number for $A$, with $x_0$ a 600-digit number, and $x_{10}$ was already correct.   In Maple 15 on a not-very-fast computer, the CPU time was given as 0.

This is my way of finding square roots larger than $100$. Take $1089$ for example. You first find the closest number (without going over) that has a square root divisible by $10$. That would be $900$; $30 \times 30$. The tens digit is a $3$. Next subtract that number leaving me with $189$. Now take the square root of $900$. Take the $10$s digit, multiply from $20$, and add $1$. That would be $61$. Subtract that number from $189; 128$. Now subtract $63, 65, 67$, etc until you reach $0$. Including $61$, count the amount of numbers that you subtracted that is the units digit. For this problem it would be $189-61-63-65=0$, so the units is $3$. Your final answer is $\sqrt{1089}=33$.


Primes for >1 (good expression) Re edited

Can we represent any prime $p \equiv 1 \pmod{5}$ or $p \equiv -1 \pmod{5}$ in terms of $(a+b)^2 + ab$ with $a> b> 0$?

Can we represent any prime $p \equiv 1 \pmod{3}$  in terms of $(a+b)^2 - ab$ with $a> b> 0$?

can we have, any odd integer $> 1$ can be written as $a + b$ where $a$ and $b$ are positive integers with $a^4$ + $b^4$ is prime?

Kindly discuss.
Thanks in advance

As another answer shows, if $p\equiv1\pmod3$, then $-3$ is a quadratic residue modulo $p$. That means there is an integer $x$ such that $$p{\rm\ divides\ }x^2+3$$ Now we pass to ${\cal O}_{-3}$, the ring of integers in the number field $K={\bf Q}(\sqrt{-3})$, and write, $$p{\rm\ divides\ }(x+\sqrt{-3})(x-\sqrt{-3})$$ Now $p$ doesn't divide either one of $x\pm\sqrt{-3}$ since $${x\over p}\pm{1\over p}\sqrt{-3}$$ are not in ${\cal O}_{-3}$. But it is known that ${\cal O}_{-3}$ is a unique factorization domain, implying that if an irreducible divides a product it must divide one of the factors. We deduce that $p$ is not an irreducible in ${\cal O}_{-3}$. Let $$\pi=a+b{1+\sqrt{-3}\over2}$$ be a nontrivial factor of $p$ in ${\cal O}_{-3}$. Then the norm of $\pi$ is a positive nontrivial factor of the norm of $p$, which is $p^2$, so the norm of $\pi$ is $p$. But the norm of $\pi$ is $a^2+ab+b^2$, QED.

EDIT: Similarly, if $p\equiv\pm1\pmod5$, then $5$ is a quadratic residue modulo $p$, so $$p{\rm\ divides\ }x^2-5$$ for some $x$. Going to ${\cal O}_5$, $$p{\rm\ divides\ }(x+\sqrt5)(x-\sqrt5)$$ but $p$ divides neither one of $x\pm\sqrt5$. Now ${\cal O}_5$ is known to be a UFD, so, again, $p$ is not irreducible in ${\cal O}_5$. Let $$\pi=r+s{1+\sqrt5\over2}$$ be a nontrivial factor of $p$ in ${\cal O}_5$. Taking norms, we get $$p=r^2+rs-s^2$$ Now a simple substitution gets us to $(a+b)^2+ab$.

I can answer for your second part. But, you should know about reciprocity. Otherwise, I am sorry. p = 1 (mod 3) is very known. for (-3/p) = (-1/p)(3/p)
=) (-1/p) = (-1)^{(p-1)/2} and (3/p) = (-1)^{(p-1)/2}(p/3)
=) (-3/p) = (-1)^{(p-1)/2}(-1)^{(p-1)/2}(p/3) = (p/3)
i.e., -3 is quadratic residue mod p, if and only of p = 1 (mod 3).
NOTE you can try for p = 2 (mod 3) more easily without using reciprocity. I hope you got it.