Do irrational number contain infinite/every patterns of sequences? I guess the question is

  "does an 'infinite' number of patterns imply 'every' number of
  patterns?"

For instance, if you could quickly calculate the decimal sequence of π, could you not (in theory of course) come up with an algorithm to search that sequence for some pre-determined sequence?

Then you could do this:

start = findInPi(sequence)

So "sequence" in theory could be a decimal representation of the movie "The Life of Pi".  The implication is that all digital knowledge (past, present and future) is bound up in irrational numbers (not just the group of irrational numbers, but each irrational number), and we just need to know the index to pull data out.

Once you know the index and length of data, then  you could simply pass this long.

playMovie(piSequence(start, length))

From an encryption standpoint, you could pass the start, length pair around, and the irrational number would be known only by the private key holder.

Am I off base here?

No, this is not the case for every irrational number. For example, the number

$$ 1.01001000100001000001000000100... $$

where each run of zeroes is one longer, is clearly irrational, since the decimal expansion never repeats. But it just as clearly doesn't contain every pattern of digits, because the only digits it contains are 0 and 1.

$\pi$ in particular is suspected (but not proved) to satisfy a stronger property, namely that it is normal, which means that not only does every pattern of digits occur, but every pattern occurs infinitely many times, with the frequency one would assume in a random string of digits.

In a certain technical sense, most numbers are normal, but there are very few expressions that have been proved to produce a normal number. This is a problem for your cryptography idea, because it is hard for the two parties to agree on a particular number that contains all of the messages they want to exchange.

You can achieve it, its not hard. for instance I assume that
0..4=LOW (0)
5..9=HIGH (1)

I start calculating π  using chudnovski algorithm... and so i start π=3.1415.... (π=0.0001....)

At the same time as I calculate the infinite tail of π, I compare the data that I wish to send to somebody else, until I find a 100% match of length.

So after I find a match, I am telling my  remote friend  "the data that I wish to send you starts at the 9.876.543 digit of pi and its size is 1MB after the starting point. Convert it accordingly (0-4=0; 5-9=1;)

This way you could transmit data just by providing starting point and size.
Also , there will be thousands of ways to optimise the algorithm.

Inside the π lies ANYTHING ! From my dna to the farest multiverse.


Conditional probability and testing twice I am struggling with an interview quiz question which starts with a standard conditional probability part:

  To detect genetic defects, you are in charge of
  performing a test. You know that:

  1% of people have a genetic defect
  99.9% of tests for the gene detect the defect (true positives)
  5% of the tests give a positive result even though there is no defect (false positives)

  Given that the condition of a patient is known, the results of multiple tests are independent

  a)
  If a person gets a positive test result, what is the probability that he/she actually has the genetic defect?

For a), I would argue that this is standard conditional probability and can be solved with Bayes Rule. Let's call the event "$+$" when a person tests positive, "$d$" when a person has the disease and "$\bar{d}$" when a person does not have the disease.

Now we are looking for $P(d\mid+)$, so the conditional probability that someone actually has the disease when he tests positive. Given Bayes, that is

\begin{align}
P(d\mid+) & = \frac{P(+\mid d)}{P(+)}\cdot P(d) = \frac{0.999}{P(+\mid d)\cdot P(d) + P(+\mid\bar{d})\cdot P(\bar{d})}\cdot 0.01 \\[10pt]
& = \frac{0.999}{0.999\cdot 0.01 + 0.05\cdot 0.99}\cdot 0.01 \approx 0.168.
\end{align}

So the probability is roughly 17%.

What is more complicated for me is b):

  b) If a person gets a positive result in his/her first test, what is the probability of having a positive result in his/her second test?

I would argue that we are looking for $P(++|+)$, i.e. the probability that someone tests positive the second time under the condition that he tested positive the first time.

So we can apply Bayes again and get $\frac{P(+|++)}{P(+)}\cdot P(++)$. I'd argue that $P(+|++)$ is always 1 and that $P(++) = P(+)\cdot P(+)$. We can cancel out one $P(+)$ and this leaves us with $P(++|+) = P(+)$.

On the one hand this looks reasonable given the independence proclaimed, on the other hand it feels counter-intuitive that the probability would only be 6% (on the third hand, we are talking about statistics here and that never went well together with common sense for me :-)).

Thoughts?

Denote events $D$, $\bar D$ as the patient having the defect and not having the defect, respectively.  Let $P_i$ denote the event that test $i$ is positive, and $\bar P_i$ the event that test $i$ is negative.

Then the desired probability is $$\Pr[P_2 \mid P_1] = \frac{\Pr[P_2 \cap P_1]}{\Pr[P_1]} = \frac{\Pr[P_2 \cap P_1 \mid D]\Pr[D] + \Pr[P_2 \cap P_1 \mid \bar D]\Pr[\bar D]}{\Pr[P_1 \mid D]\Pr[D] + \Pr[P_1 \mid \bar D]\Pr[\bar D]}.$$  Since $P_i$ are conditionally independent given the defect status, we have $$\Pr[P_2 \cap P_1 \mid D] = (\Pr[P_i \mid D])^2.$$  Then, given $$\Pr[D] = 0.01, \quad \Pr[P_i \mid D] = 0.999, \quad \Pr[P_i \mid \bar D] = 0.05,$$ we easily obtain $$\Pr[P_2 \mid P_1] = \frac{(0.999)^2(0.01) + (0.05)^2(1-0.01)}{(0.999)(0.01) + (0.05)(1-0.01)} \approx 0.209363.$$  This number is small because the prevalence of defects is so rare, and the false positive rate is much higher than the prevalence.  Therefore, a positive result is more likely to result from a false positive, and a second test is not terribly likely to come back positive.

P(++|+) = P(+/++)P(++)/P(+)

P(++|+) =
1*(1%*99.9%+99%*5%)^2/(1%*99.9%+99%*5%)
= 1%*99.9%+99%*5%

This used the conditional probability calculation.
P(+|++) = 1, 1st being positive given both positive

P(++) = P(+)^2, this assumes two measures are independent.

P(+) = 1%*99.9%+99%*5%

So P(++|+) = P(+)

If being positive once increases the odd of being positive again, that increase in odd wasn’t provided in the question.


Existence of variation Let $I[w] =\int_U L(Dw,w,x) dx$. Let $1<q<\infty$, and there exist constants $\alpha>0$,$\beta\ge0$ such that $$L(p,z,x)\ge \alpha |p|^q - \beta$$

This implies that if $I[w]$ exists,
$$I[w] \ge \alpha \|Dw\|_{L^q}^q -\beta |U|$$

Now Evans says that for $w\in W^{1,q}(U)$ that $I[w]$ is defined but possibly infinite. What is the reason for this? Is it true always that functions which are bounded below are integrable (where integral can be $\infty$)?

On a set of finite measure (such as $U$ here) every measurable function that is bounded from below has a well-defined integral, which is either a real number or $+\infty$. Indeed, one can write $f=f^+-f^-$ where $f^+=\max(f,0)$ and $f^-=\max(-f,0)$. Then define $\int_U f=\int_U f^+-\int_U f^-$.  The second integral is finite, the first may be $+\infty$.

In this case, $L(Dw(x),w(x),x)$ is bounded from below by $-\beta$. One still has to check that it's measurable, which requires placing some condition on $L$ (continuity is enough, but there are more general conditions that suffice for this purpose).


Computing the first $n$ values of the Liouville function in linear time Is it possible to compute the first $n$ values of the Liouville function in linear time?  Since we need to output $n$ values we clearly cannot do better than linear time, but the best I can figure out is something like $O(n \cdot \log{\log{n}})$: fill an array of size $n$ with ones, and for each prime power $p^a$, negate the value at the index of each of its multiples.  I think it is possible to identify the prime powers as we count up using another table of $O(n)$ bits, essentially the sieve of Eratosthenes counting powers too, but there are still $\sum_{p^a \le n}{\frac{n}{p^a}} = n \cdot \log{\log{n}} + O(n)$ negation operations.   Is it possible to do better than this?

Your problem is related to the problem of finding all the primes up to $n$, and it can be solved by similar means.

Although the traditional sieve of Eratosthenes has complexity $O(n \log \log n)$, there are improved versions, which work in $O(n)$ time. It is achieved by crossing out each composite number exactly once. For the purpose of finding primes, these algorithms can even be optimized to $O(n /\log \log n)$ time by the so-called wheel optimization. You can find details in e.g. this paper.

In order to solve your problem, you have to calculate the least prime factor function (denoted by $lpf$) during sieving, not only the primes. When the $lpf$ function is ready, you can compute completely multiplicative functions  in $O(n)$ easily by dynamic programming, e.g.:
$$
  \lambda(x) =
  \begin{cases}
    -1 & x = lpf(x) \\
    -\lambda \left( \frac{x}{lpf(x)} \right) & \text{otherwise}
  \end{cases}
$$

One of the algorithms which calculates least prime factors in $O(n)$ time is described here. Below you can see its implementation in C++, with primes being a sorted list of all primes found so far, and lpf being an array representing the same-named function.

vector<int> primes;
vector<int> lpf(n, -1);
for (int x = 2; x < n; x++) {
  if (lpf[x] < 0) { //prime found
    lpf[x] = x;
    primes.push_back(x);
  }
  for (int i = 0; i < primes.size(); i++) {
    int p1 = primes[i], y = p1 * x;
    if (p1 > lpf[x] || y >= n)
        break;
    lpf[y] = p1;
  }
}

Consider a number $x$ having least prime factor $p = lpf(x)$. For each prime $p_1 \le p$, it is easy to see that $lpf(p_1 \cdot x) = p_1$. The algorithm simply applies this crossing-out rule for each number $x$ in increasing order. Of course, it needs the sorted list of primes in order to iterate over all the necessary primes $p_1$.

Every composite number $y$ is crossed out exactly once when considering number $x = \frac{y}{lpf(y)}$, so time complexity is $O(n)$. In practice however, it is slower than the traditional $O(n \log \log n)$ sieve, at least for the purpose of finding primes. I guess your approach would also be faster, especially with bitsets.

If you are interested in practical acceleration of your algorithm, you'd better think about memory/cache optimization, instead of improving asymptotic complexity by a double-log factor =)

Actually this cannot be true because you can't get the prime (power)s in $O(n)$:

The sieve of eratosthenes takes at least $O(nloglogn)$ Operations.

Assume we have a list of all the primes up to $n$ given. Then checking each $k$ for membership in the list takes at least (if we only check the first $\pi(\sqrt{k})$ elements) $\pi(\sqrt{k})$ operations each, which amounts to more than $O(1)$ so that's out. Then we could check each number for primality but the fastest known primality test runs in $O(log(n)^6)$, also more than $O(1)$. Since for each number we either have to run it against a list or check it by hand that amounts to all possibilites and we conclude it's impossible to calculate the value for all $k \leq n$ in $O(n)$


Dense subset on complete metric space Let $(X,d)$ be a metric space and $M$ a dense subset of $X$ with the proterty that every Cauchy sequence of $M$ has a limit inside $X$. Show that $X$ is complete.
With contradiction:
Let $(x_{n})$ be a Cauchy sequence of $X$ such that it doesn't converge on $X$.
We can take a subsequence  $x_{k_{n}}\subseteq M$ and we know that $x_{k_{n}}\rightarrow x,\, x\in X$
and therefore we have that  $x_{n}\rightarrow x$ because $(x_{n})$ is Cauchy and if one subsequence converges to $x$ we know that $(x_{n})$ is also converges to $x$ and that's a contradiction.
Is my proof complete, thank you.

Here's one approach: let $(x_n)_{n\geq 1}$ be a Cauchy sequence in $X$. For each $n\geq 1$, pick $x_n'\in M\cap B(x_n, 1/n)$.

Show that $(x_n')_{n\geq 1}$ is a Cauchy sequence too.

By assumption, there is $x\in X$ with $x_n'\to x$.

Show that $x_n \to x$ as well.

Correct me if i am wrong cause i am not sure about my anwser but i couldn't come up with anything else.
Let $x_{n}\epsilon X$ and $x'_{n}\epsilon M\bigcap B(x_{n},\frac{1}{n})$
$\Rightarrow $ $d(x'_{n},x_{n})<\frac{1}{n}$ $\Rightarrow $ $d(x'_{n},x_{n})\rightarrow 0$ (1)
i take $m\geq n\geq n_{0}$ and i have $d(x'_{m},x'_{n})\leq d(x'_{m},x_{n})+d(x_{n},x'_{n})$ $\overset{(1)}{\rightarrow}0$
and that says $x'_{n}$ is Cauchy $\Rightarrow $ $x'_{n}\rightarrow x\epsilon X$
now
$d(x_{n},x)\leq d(x_{n},x'_{n})+d(x'_{n},x)\rightarrow 0$
and that proves that $X$ is complete


Families of curves over number fields Is there known a number field $K$ and a curve $F(x, y) \in K(t)[x, y]$ such that $F(x, y)$ does not have points over the field of rational functions $K(t)$ but for all but finitely many positive integer values of $t$ the respective specialization has a point over $K$?

(I expect the answer to be "such a $K$ is not known" and the problem of similar difficulty as that for $K = \mathbb{Q}$ but have not seen an expert comment on it so far.)

Thank you.

Assuming the parity conjecture (known to be a consequence of the
BSD
conjecture)
for
"congruent
number curves"
$E_d: d \cdot Y^2 = X^3 - X$,
you can even take $K = {\bf Q}$ and
$$
F(x,y) = 4x^2 + 1 + (8t-1) x y^2.
$$

The curve $F(x,y) = 0$ is birational with the elliptic curve
$(8t-1) Y^2 = X^3 + 4X$ (let $x=1/X$ and $y=Y/X$),
which in turn is 2-isogenous with $E_{8t-1}: (8t-1) Y^2 = X^3 - X$.
The only ${\bf Q}(t)$-rational points of the curve $(8t-1) Y^2 = X^3 + 4X$
are the torsion points at $(0,0)$ and infinity, and I chose coordinates
$X,Y$ that put both of these points on the line at infinity, so there are
no finite solutions of $F(x,y) = 0$.  On the other hand, if $t$ is
a positive integer then $|8t-1| \equiv 7 \bmod 8$, so $E_{8t-1}$
has sign $-1$, whence under BSD it has odd (and thus positive) rank
over $\bf Q$, so infinitely many rational points.

[This example has no exceptional $t$, but it's clear a priori
that if there's an example with only finitely many exceptional $t$
then one can translate $t$ to get a "new" $F$ that has none.]

The complexity arises because not solve such equations. Usually use of modular arithmetic. Although quite often it is not able to give the formula of the solution.

We give some examples.

Unique Integer solution of a non-linear equation - sometimes it is possible to write a simple formula.

How to find $a,b\in\mathbb{N}$ such that $c = \frac{(a+b)(a+b+1)}{2} + b$ for a given $c\in\mathbb{N}$ - or like this.

Diophantine equation: $(x-y)^2=x+y$ - or like this.

Perfect Square relationship with no solutions - for some special cases you can get the formula.

How to solve an equation of the form $ax^2 - by^2 + cx - dy + e =0$? - for some special cases you can get the formula.

How can I solve equation $x^2 - y^2 -2xy - x + y = 0$? - you can consider this simple.

Proving a Pellian connection in the divisibility condition $(a^2+b^2+1) \mid 2(2ab+1)$ - you can consider this simple.

Existence of $x,y$ Satisfying Diophantine Equation - you can consider this simple.

The system of genus characters determined by a binary quadratic form - there are written the same formula.

I think enough. There's formula for binary quadratic forms. Usually only for this form can write formulas of solutions.


Determine the set of points $z$ that satisfy the condition $|2z|>|1+z^2|$ Determine the set of points $z$ that satisfy the condition $|2z|>|1+z^2|$

I tried to redo this problem and got to this point

$|2z|>|1+z^2|$ $\Rightarrow$ $2|z|>1+|z^2|$ $\Rightarrow$ $2|z|>1+z\overline z$

Let $z=x+iy$ then

$$2\sqrt{x^2+y^2}>1+(x+iy)(x-iy)$$

$$2\sqrt{x^2+y^2}>1+(x^2+y^2)$$

$$0>1-2\sqrt{x^2+y^2}+(x^2+y^2)$$

$$0>(1-\sqrt{x^2+y^2})^2$$

since $x,y$ are real number , so there is no solution for this inequality?

Let $z=re^{i\theta}$. Then after squaring both sides we have
$$
4r^2 > r^4 + 2r^2\cos(2\theta) + 1\Rightarrow
0>(r^2-2r\sin(\theta)-1)(r^2+2r\sin(\theta)-1)\tag{1}
$$
where I used the following identity $\cos(2\theta) = 1 -2\sin^2(\theta)$. Let's write $(1)$ in Cartesian coordinates so recall that $r^2 = x^2 + y^2$ and $r\sin(\theta) = y$. Then we have
$$
0>(x^2+y^2-2y-1)(x^2+y^2+2y-1)=[x^2+(y-1)^2-2][x^2+(y+1)^2-2]
$$
Then
\begin{align}
x^2+(y-1)^2&< 2\\
x^2+(y+1)^2&< 2
\end{align}
That is, we have two disc of radius $\sqrt{2}$ centered at $(0,\pm i)$. So the solution set is
$$
S=\bigl\{z\in\mathbb{C}\colon \lvert z-i\rvert < \sqrt{2}\text{ or }\lvert z+i\rvert < \sqrt{2}\text{ but not in the intersection}\bigr\}
$$

let $D = \{z \colon 2|z| < |1 + z^2|\}.$ observe that the region $D$ is symmetric with respect to the transformations $z \to -z, z \to \bar z$ and $z \to \dfrac{1}{z}$ therefore it is enough to worry about the portion of $D$ in the first quadrant.

Let $o = 0, a = 1$ and $z = re^{it}, p = 1 + r^2e^{2it}$ so that $z$ is on the boundary of $D.$ applying rule of cosine to the triangle, we have $$\cos 2t = 2 - \frac{1}{2}\left( r^2 + \frac{1}{r^2} \right).$$

looking at the graph of $y = 2 - \frac{1}{2}(x + 1/x),$ you can verify that $-1 \le y \le 1$ for $3 - 2\sqrt 2 \le x \le 3 + 2\sqrt 2$ and $f(1) = 1, f(2 \pm \sqrt 3) = 0$

i plotted the region $D$ it contains the unit circle and has a hole(lens) containing the origin.

so part of $D$ in the first quadrant is given by
$$\{re^{it} \colon t = \frac{1}{2}\cos^{-1}\left(  2 - \frac{1}{2}( r^2 + \frac{1}{r^2} ) \right), \sqrt{3 - 2\sqrt 2} \le r \le \sqrt{3 + 2 \sqrt 2} \}.$$


Is $f(x) \in \mathbb{R}$ if $x \in \mathbb{R}$? Let $f:\Omega\subset\mathbb{C}\rightarrow\mathbb{C}$ be holomorphic with $\Omega$ open. Assume there is an infinite sequence $(x_n)_n$ in $\Omega \cap \mathbb{R}$ that converges to $x_0 \in \Omega \cap \mathbb{R}$ and assume that for every $n$, $f(x_n) \in \mathbb{R}$. Let $D_r$ be the open disk of radius $r>0$ and centre $x_0$ such that $D_r \subseteq \Omega$. Is it true that $f(x) \in \mathbb{R}$ for every $x \in D_r \cap \mathbb{R}$?
I tried proving this by constructing a holomorphic function $g$ such that $g(z)$ is real whenever $z$ is real and $g(x_n)=f(x_n)$. Then by the identity theorem it follows that $g=f$. Unfortunately, I was unable to find such $g$.
Any help would be welcome. Thank you in advance.

Hint: $g(z) = \frac12\big( f(z) + \overline{f(\overline z)} \big)$. (This is the same construction as in a proof of the Schwarz reflection principle.)

First of all, $D_r$ seems not to be part of the question or problem?
Secondly: your assumptions is that there exists a particular sequence $(x_n)$ converging to a particular point $x$ and you want to show a general statement that would be "$f(x)$ is real whenever $x$ is real". There is a clear lack of assumptions to show that.
This is the only thing that can be shown with your assumptions:
Let $f : \Omega \to \mathbb{C}$ be continuous. If $x \in \Omega$ is the limit of the sequence $(x_n) \in (\Omega)^{\mathbb{N}}$ and if for every $n$, $f(x_n) \in \mathbb{R}$, then $f(x)\in \mathbb{R}$. This is because $f$ is continuous at $x$ and because $\mathbb{R}$ is a closed subset of $\mathbb{C}$.


Minimal polynomial of $\sqrt[3]{2} + \sqrt{3}$ Suppose I want to find the minimal polynomial of the number $\sqrt[3]{2} + \sqrt{3}$.

Now that means I want to find a  unique polynomial that is irreducible over $\Bbb Q$ such that $f(x)=0$. Now I know that because   $\sqrt[3]{2} + \sqrt{3}$ belongs to $\Bbb Q( \sqrt[3]{2} , \sqrt{3})$  it might be degree $2$, $3$ or $6$ and does not belong to $\Bbb Q( \sqrt[3]{2})$ so it cannot be of degree $3$ or  $\Bbb Q( \sqrt{3})$ so it cannot be of degree $2$.

So it is of degree $6$. I think my sayings are a bit intuitive and not formal and lack rigorous.
Couldn't it belong to another extension of degree $2$? or $3$? I can't answer that. Why checking only those $2$ is enough? Or is it wrong at all to say that?

You are correct that $\def\Q{\Bbb Q}x=2^{1/3}+3^{1/2}\in \Q( \sqrt[3]{2} , \sqrt{3})$. You are also correct that the degree of the minimal polynomial $f_x$ will equal the extension degree $[\Q(x):\Q]$, and hence $\deg f_x\mid [\Q( \sqrt[3]{2} , \sqrt{3}):\Q]=6$. However, there might be more intermediate fields $\Q( \sqrt[3]{2} , \sqrt{3})\supset \Q(\alpha)\supset \Bbb Q$ then just $\Q(2^{1/3})$ and $\Q(3^{1/2})$. In particular, $\Q(x)$ might just be a third field that is strictly between $\Q( \sqrt[3]{2} , \sqrt{3})$ and $\Q$. Hence your reasoning in incomplete.

One can show however, that $\Q(3^{1/2})\subset \Q(x)$ and $\Q(2^{1/3})\subset \Q(x)$. This would force the degree $[\Q(x):\Q]$ to be six, since now
$$[\Q(x):\Q]=[\Q(x):\Q(3^{1/2})][\Q(3^{1/2}):\Q]=2[\Q(x):\Q(3^{1/2})]$$
$$[\Q(x):\Q]=[\Q(x):\Q(2^{1/3})][\Q(2^{1/3}):\Q]=3[\Q(x):\Q(2^{1/3})]$$
Hence $2\mid [\Q(x):\Q]$ and $3\mid [\Q(x):\Q]$. Also, we already saw $[\Q(x):\Q]\leq [\Q(3^{1/2},2^{1/3}):\Q]=6$. Hence we conclude that $[\Q(x):\Q]=6$.

The number requires a sixth-order polynomial to solve.  The intuition here is that for belonging to $Z(\sqrt{3}, \sqrt[3]{2})$ that it actually belongs to say $Z(1,\sqrt{3})(1,\sqrt[3]{2},\sqrt[3]{4})$.

One might note that these pair of systems are closed to multiplication, addition and subtraction, and that the appending of the $(1,\sqrt{3})$ will either result in an integer, or a number oin this set.  Since the intersection of this set and the second set $(1,\sqrt[3]{2},\sqrt[3]{4})$ is the integers only (ie $Z$), then because the solution is in neither of the axial sets, it is in the union.

This particular set does not provide any means for a subset other than the two axial sets, in that no subset of the six base units make a set closed to multiplication.  And there are six units, and so it must solve a calculation in terms of a sixth order equation.

An example where one might get a possible subset is $Z(1,\sqrt[3]{2},\sqrt[3]{4})(1,\sqrt[3]{2},\sqrt[3]{4})$  which contains possible sets like $Z(1,\sqrt[3]{2},\sqrt[3]{36})$  and $Z(1,\sqrt[3]{12},\sqrt[3]{18})$.


Prove $\gcd(m, n)=\gcd(m, 2n)$ For all integers $m$ and $n$, if $m$ is odd, prove $\gcd(m, n) = \gcd(m, 2n)$. There is an external fact that can be used if both numbers are odd, their product is odd as well. I think I need to prove that every odd factor of $n$ is also a factor of $2n$, as I cannot assume this, but I am stuck with it and cannot get any ideas. Any help is appreciated!

Consider the primes $p_1=2,\ p_2=3,\ p_3=5\dots p_k\le \max(m,n)<p_{k+1}$.

$m=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k};\ \alpha_i \ge 0$. Note that many of the exponents $\alpha$ will be $0$ in this formulation, since it is not possible that $n$ has every prime $\le \max(m,n)$ as a factor. Since $m$ is stated to be odd, we know that $\alpha_1=0$.

Similarly, $n=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$, and $2n=p_1^{\beta_1+1}p_2^{\beta_2}\cdots p_k^{\beta_k}$. Here also, many of the exponents $\beta$ will be $0$.

$\gcd(m,n)=p_1^{\min(\alpha_1,\beta_1)}p_2^{\min(\alpha_2,\beta_2)}\cdots p_k^{\min(\alpha_k,\beta_k)}$ and $\gcd(m,2n)=p_1^{\min(\alpha_1,\beta_1+1)}p_2^{\min(\alpha_2,\beta_2)}\cdots p_k^{\min(\alpha_k,\beta_k)}$

Note that these two products have identical factors except for $p_1^{\min(\alpha_1,\beta_1)}$ and $p_1^{\min(\alpha_1,\beta_1+1)}$. But since $\alpha_1=0$, $\min(\alpha_1,\beta_1)=\min(\alpha_1,\beta_1+1)=0$ and $p_1^{\min(\alpha_1,\beta_1)}=p_1^{\min(\alpha_1,\beta_1+1)}=1$.

Since the non-identical factors are equal, and all other factors are identical, it follows that $\gcd(m,n)=\gcd(m,2n)$

We wish to show that $\gcd(m,n)=\gcd(m,2n)$ where $m$ is odd.  Let $k=\gcd(m,n)$, then the prime factorization of $k$ is the intersection of the set of prime factors of $m$ and $n$.  For example, if $$m=21=\color{red}{3}\cdot7$$ and $$n=36=2\cdot2\cdot \color{red}{3} \cdot3$$ then $$\gcd(21,36)=3$$
Notice here that $\gcd(21,72)$ is still $3$.

Generally, given that $m$ is odd, $2$ is not in its prime factorization, so if $P_{m}$ is the set of prime factors of $m$ and $P_{n}$ is the set of prime factors of $n$, we note that $2 \notin P_{m}$ and therefore
$$
P_{m} \cap P_{n} = P_{m} \cap \{2 \cup P_{n}\}
$$
i.e., $\gcd(m,n)=\gcd(m,2n)$ given that $m$ is odd.


How can we detect if a topological space has "holes". I realize that this question might seem ambiguous, is there a topological notion for what a Hole is? I think it has something to do with the fundamental groups of the topological space but I don't really know, could someone please tell me the basics and what is a basic tool for detecting when a topological space has "holes"?

Background: I am currently taking topology 1 and I am halfway through my second semester of abstract algebra.

Thank you kindly, regards.

My professor exposed me to L.S. Pontryagin's "Foundations of Combinatorial Topolology," just recently, and I would say that I had about the same background as you did when I started it. I struggled at some point, but in general I was able to get through it pretty okay. The main interest of the book is simplicial homology, and this will address your question. The text is short, and relatively dense, but it was possible when I had taken a course in abstract algebra and point-set topology.

To be fair, this is probably overkill just to understand a joke about topological holes, but it is a thorough treatment of homology theory.


Constructing Simultaneous Equation for This Problem Suppose we have a rating system where a "thumbs up" equals +1 and a "thumbs down" equals - 1. We know the total number of votes cast and the current score. For example a score of +3 with 5 votes cast.

How can we determine how many "thumbs up" and "thumbs down" there are?

I imagine this would be some sort of simultaneous equation....

$x$: number of up votes

$y$: number of down votes

Now solve

$$x+y=5$$

$$x-y=3$$

Let the number thumbs up be $u$, let the total number of votes be $n$, and let the total score be $t$. Then we can say that the number of thumbs down votes must be $n-u$, so we can write:$$u-(n-u)=t$$$$\therefore 2u-n=t$$$$\therefore u=\frac{t+n}{2}$$


Can someone explain the relation between "Achilles chasing turtle" paradox and monotonic, bounded sequence to me? Recently I have read a book called "Caculus - Basic Concepts for High School"

The possibility of infinite but bounded sets
was not known, for example, to ancient Greeks. Suffice
it to recall the famous paradox about Achilles chasing
a turtle.
Let us assume that Achilles and the turtle are initially
separated by a distance of 1 km. Achilles moves 10 times
faster than the turtle. Ancient Greeks reasoned like this:
during the time Achilles covers 1 km the turtle covers 100 m.
By the time Achilles has covered these 100 m, the turtle
will have made another 10 m, and before Achilles has covered these 10 m, the turtle will have made 1 m more, and
so on. Out of these considerations a paradoxical conclusion
was derived that Achilles could never catch up with the
turtle.
This "paradox" shows that ancient Greeks failed to grasp
the fact that a monotonic sequence may be bounded.

I know how to prove the conclusion of this paradox is incorrect, and understand that the described movement of Achilles and the turtle each is a monotonic, bounded sequence. However, I don't understand author's claim that

This "paradox" shows that ancient Greeks failed to grasp
the fact that a monotonic sequence may be bounded.

Can someone help to explain this part? Thank you very much.
EDIT:
Thank you all so much for your instant replies. However, I still don't get how these two movements being strictly monotonic, bounded sequences, has anything to do with Greek ancient people's conclusion.
For Achilles' movement:
$$ x = \sum_{i=0}^\infty \frac{1000}{10^i}$$
For the turtle's movement:
$$ y = 1000 + \sum_{i=0}^\infty \frac{100}{10^i} $$
So the Greek ancient people are trying to find an $n$ where:
$$ x_n = y_n $$
However, since $ y_n = x_{n+1} $ and $ x_n < x_{n+1} $ so there is no such $n$ exist.
With everything mentioned above, I still don't find anything to do with bounded sequence part.

(For fun)
Greek philosopher:
Now you see, by the time Achille reaches the place where the turtle is right row, the turtle will have gone to another place. So Achill will have to run an extra time to reach turtle again. Clearly, that pattern repeats infinitely to Achille, thus Achille has to run forever.
Greek student
But Philosopher, why does AChille have to run forever?
Greek Philosopher:
Stupid! Because all the instants -at which that pattern happens to Achille - is an infinite increasing sequence. And an infinite increasing sequence cannot be bounded.
Count your cows! Count the houses! Do you see that even though those numbers may be big but you still can count them all. That is because they are bounded. Finite is bounded! Infinite is very very big!
You potato head surely have wasted all the potatoes you have eaten.

I think it means that they did not know that there could be sequences where every value is bigger than the last that themselves have a limit, for example the sequence:
1/2, 2/3, 3/4, 4,5, 5/6, etc
it has a limit of 1 but it always increses, the statement says that the greek did not have the understanding that there where such sequences, where the numbers always increse never get to infinity.


Tell whether $\dfrac{10^{91}-1}{9}$ is prime or not? I really have no idea how to start. The only theorem considering prime numbers I know of is Fermat's little theorem and maybe its related with binomial theorem.

Any help will be appreciated.

Just think through the actual number.

$10^{91}$ is a $1$ with $91$ $0$'s after it.

$10^{91}-1$ is therefore $91$ $9$'s in a row.

$\frac{10^{91}-1}{9}$ is therefore $91$ $1$'s in a row.

Due to the form of this number, $x$ $1$'s in a row will divide it, where $x$ is a divisor of $91$.

For example $1111111$ is a divisor, so is $1111111111111$.

Hence the number is not prime.


How to prove that $A B A^* \leq \|B\| A A^*$ for operators A,B? Let $A$, $B$ bounded operators on a Hilbert space $H$. Further let $B$ be self-adjoint.
Then we have that $A B A^* \leq \|B\| A A^*$.
I wanted to ask how to prove this inequality or where I can find a proof if it is a very common ineuqality.

The usual way to prove this is in two steps. First you prove that for any selfadjoint $B$, you have $\|B\|\,I-B\geq0$. This is easy, because $\|B\|\,I-B$ is selfadjoint and $$\sigma(\|B\|\,I-B)=\{\|B\|-\lambda:\ \lambda\in\sigma(B)\}.$$ As $|\lambda|\leq\|B\|$ for all $\lambda\in\sigma(B)$ and $\sigma(B)$ is real, we have $\sigma(\|B\|\,I-B)\subset[0,\infty)$.

The second part is that if $S\geq0$, then $ASA^*\geq0$. This follows from writing $S=TT^*$ for some $T$, and then $$ASA^*=ATT^*S^*=(AT)(AT)^*\geq0.$$

Then $$A(\|B\|\,I-B)A^*\geq0,$$ so $\|B\|\,AA^*\geq ABA^*$.

Proof: For all $h \in H$, $\langle A^* BA h, h \rangle = \langle BA h, A h \rangle \leq \|B\| \cdot \langle A h, A h \rangle =   \langle \|B\|A^*A h, h \rangle$.


Evaluate $\lim_{x \to 0} \dfrac{\sin(2x)}{8x}$ I need to evaluate
$$\lim_{x \to 0} \dfrac{\sin(2x)}{8x}$$
I'm doing Calculus One course on coursera.org and here is their explanation that doesn't explain anything for me:

Why $\lim_{x \to 0} \dfrac{\sin(x)}{x}=1$ ?

Why do I need to set $y=2x$? And why $y\to 0 as x\to 0$?

Why $\lim_{y \to 0} \dfrac{\sin(y)}{y} \cdot \dfrac{2}{8}$ suddenly became $\lim_{x \to 0} \dfrac{\sin(2x)}{8x}=\dfrac{1}{4}$?

For the first one, why not google it?
Then
$$\lim_{x\to 0}\frac{\sin 2x}{8x}=\lim_{2x\to 0}\frac{\sin 2x}{4\cdot 2x}=\frac14\lim_{2x\to 0}\frac{\sin 2x}{2x}=\frac14\cdot 1=\frac14$$

$\bf hint:$ if you have you a calculator that can compute $\sin,$ then compute $\frac{\sin x}{x}$ for $x = 0.1, 0.01, 0.001$ and see what happens. look at the graphs of $\sin x$ and $x$ in the window $-1 \le x \le 1, -1 \le y \le 1$ make sure your calculator is in radian mode. happy experimenting.


Consider the following system of differential equations Consider the following model. Find the general solution

$\frac{dx}{dt}=-2y$,
$\frac{dy}{dt}=8x$

So far this is what I have:

$$\frac{dx}{dt}=-2y$$
$$x'=-2y$$
$$y=-\frac{x'}{2}$$
$$y=-\frac{x''}{2}$$
and then
$$\frac{dy}{dt}=8x$$
$$y'=8x$$
$$-\frac{x''}{2}=8x$$
$$-x''=16x$$
$$x''+16x=0$$
Is this correct so far? What step should I take next?

Although not the usual way I've seen this done (usually I have seen the eigenvalue/eigenvector method done), your approach works.

Now you need to know that the general solution to $x''+16x=0$ is $c_1 \cos(4x) + c_2 \sin(4x)$. One way to see this is to get the characteristic polynomial $\lambda^2+16$ which has roots $\pm 4i$. So from this you get a general solution of $c_1 e^{4ix} + c_2 e^{-4ix}$ for complex constants $c_1,c_2$. That can then be rearranged into the previous form.

$$\frac{dx}{dt}=-2y$$
$$\frac{dt}{dx}=-\frac{1}{2y}$$
By chain rule:
$$\frac{dy}{dx}=\frac{dy}{dt}\cdot\frac{dt}{dx}$$
$$\frac{dy}{dx}=8x\cdot-\frac{1}{2y}$$
$$\frac{dy}{dx}=-\frac{4x}{y}$$
$$y\cdot\frac{dy}{dx}=-4x$$
$$\int y\cdot\frac{dy}{dx}dx=\int-4xdx$$
$$\int ydy=-4\int xdx$$
$$\frac{y^2}{2}+c_1=-4\cdot\frac{x^2}{2}$$
$$y^2+c_2=-4x^2$$
$$y^2+4x^2+c_2=0$$
Where $2c_1=c_2$, and $c_1$ is a constant of integration.


Why do we ask for *absolute* convergence of a series to define the mean of a discrete random variable? If $X$ is a discrete random variable that can take the values $x_1, x_2, \dots $ and with probability mass function $f_X$, then we define
its mean by the number $$\sum x_i f_X(x_i) $$ (1)
when the series above is absolutely convergent.

That's the definition of mean value of a discrete r.v. I've encountered in my books (Introduction to the Theory of Statistics by Mood A., Probability and Statistics by DeGroot M.).
I know that if a series is absolute convergent then it is convergent, but why do we need to ask for the series (1) to converge absolutely, instead of just asking it to converge? I'm taking my introductory courses of probabilty and so far I haven't found a situation that forces us restrict ourselves this way.
Any comments about the subject are appreciated.

It's because if the series is convergent but not absolutely convergent, you can rearrange the sum to get any value. Any good notion of "mean" or "expectation" should not depend on the ordering of the $x_i$'s.
For a more abstract reason, note that we define the expectation $E[X]$ of a random variable $X$ defined on a probability space $(\Omega, \mathcal{F}, P)$ as the Lebesgue integral $\int_{\Omega} X dP$. By definition of the Lebesgue integral, this is only well-defined if the integrand is absolutely integrable. If you learn more about measure theory, you will also learn why this definition makes sense. It is done to avoid strange situations like $\infty - \infty$ in the theory.

It's a great question, but unfortunately, I'm going to give an advanced probability/a measure theory answer that answers for random variables in general (OP's original title is actually about random variables. It was actually me, who edited it to discrete). However, I really can't imagine an elementary answer that consists of something more than simply 'Because' (or in Tagalog/Filipino 'Kasi'. I guess this is more precise because Tagalog/Filipino also has a word 'dahil' for a different kind of 'because').
Elementary probability peeps (including OP, I guess) may ignore this, except possibly the 'last part'. Or maybe elementary probability peeps can try to skim this and try to get an idea or something instead of understanding the specific details:
Defining expectations of random variables (or Lebesgue integrals of measurable functions) is in steps defined in the standard machine:

Expectation of indicator random variables
Expectation of simple random variables
Expectation of nonnegative random variables
Expectation of general random variables.

After 1 and 2, we get to 3. Let $X$ be a random variable. Here, we can define $E[X^{+}]$ and $E[X^{-}]$ for the nonnegative random variables $X^{+}$ and $X^{-}$, where $X^{+}$ and $X^{-}$ are something like, resp, 'the nonnegative part of $X$' and the negative of the 'nonpositive part of $X$' s.t. $X = X^{+} - X^{-}$. Then, given $|X| = X^{+} + X^{-}$, we can define $E[|X|] := E[X^{+}] + E[X^{-}]$. (Wait I forgot. Maybe you don't define this. Maybe it's really just decomposed by linearity of expectation/integration...)
And then we get to 4:
$$E[X] := E[X^{+}] - E[X^{-}]$$
Now, this is defined for either

$X$ that satisfies $E[|X|] < \infty$ --> Here, we say that $X$ is Lebesgue integrable.

$X$ that satisfies $E[X^{+}] < \infty$ or $E[X^{-}] < \infty$ --> Here, we say that the Lebesgue integral of $X$ exists.

Here, Condition 1 implies ($E[X^{+}] < \infty$ and $E[X^{-}] < \infty$, which implies) Condition 2 but not conversely. I guess analogous to regular limits in elementary calculus it's like: $\lim x^2 = \infty$, so $\lim x^2$ 'exists' but is not 'existable'. Meanwhile, $\lim \frac1x = 0$, so $\lim \frac1x$ is 'existable'. So 'existable' is the same as the usual 'exists' in elementary calculus, but 'exists' here is like including $\pm \infty$.
Finally, the aforementioned 'last part':

Anyway, I believe most texts on measure theory or advanced probability will consider specifically the Lebesgue integrable ones and not all of the Lesbesgue-integral-exists ones. On wiki, it says 'It turns out that this definition gives the desirable properties of the integral.' I assume this statement refers to Lebesgue integrable.

So now this begs the question as to why those texts refer to Lebesgue integrable random variables/measurable functions specifically. Well, there's probably (lol) some properties that Lebesgue integrable's satisfy that not all of the Lesbesgue-integral-exists ones do, but I figure it's just to avoid $\pm \infty$

AlohaSine mentioned about $\infty - \infty$ cases in h answer, but I think it doesn't apply to the Lesbesgue-integral-exists ones:

For $E[X^{+}] < \infty$ and $E[X^{-}] = \infty$, $E[X] = - \infty$

For $E[X^{+}] = \infty$ and $E[X^{-}] < \infty$, $E[X] = \infty$

Wait actually I just realised that even for elementary level probability, we use this kinds of definitions eg St. Petersburg paradox: $E[X]$ doesn't really 'exist' in the sense that $E[|X|] = \infty$, but we do have that $E[X]$ '$=\infty$' under the idea that $E[|X|] = \infty$ because $E[X^{+}] = \infty$ while $E[X^{-}] < \infty$ (specifically $E[X^{-}] =0 $) as I believe.

there's a lot of stuff in comments and answers about rearrangement in re conditional convergence. Not so familiar about this apart from wiki, but I think this (explicitly) explains only the case of discrete random variables and not for random variables in general (whenever their expectations exist...or are 'existable')


Integral of $\int z^3 e^z$ I am not sure how I am suppose to do this so I set it up normally.

$\int z^3 e^z$

$u = z^3 dx$  $du = 3z^2$

$dv = e^z$  $v = e^z$

$e^z z^3 - \int e^z 3z^2$

This then leads to a loop of integration by part and I am not sure what to do.

$$I_n = \int z^n \exp(z) dz = \int z^n d (\exp(z)) = z^n \exp(z) - n \int z^{n-1} \exp(z) dz = z^n \exp(z) - n I_{n-1}$$
Note that $I_0 = \exp(z) + C$. Hence, $$I_1 = z \exp(z) - \exp(z) +C_1$$ Make use of the same idea to compute $I_2$ and $I_3$.

Move your mouse over the gray area for the answer.

   $$I_2 = z^2 \exp(z) - 2 \left(z \exp(z) - \exp(z) \right) + C_2$$
 $$I_3 = z^3 \exp(z) - 3 \left(z^2 \exp(z) - 2 \left(z \exp(z) - \exp(z) \right) \right) + C_2$$ and so on$\ldots$

Continue doing integration by parts until the there is no more z.


IF $f(x) = \int_{0}^{\phi (x)} g(t) dt$, How could we find $f'(x)$? Given $$f(x) = \int_{0}^{\phi (x)} g(t) dt$$ How could we find $f'(x)$? Please explain your answer.

Assume that $\phi (x) $ is a differentiable function. The right hand side is the composition of two simpler functions, each of which we can find the derivative.

$$ f(x) = G( \phi (x) ) $$ where $ G(x) =\displaystyle \int^x_0 g(t) dt.$ By the chain rule, $$ f'(x) = \phi ' (x) \cdot G'( \phi (x) ) .$$

By the Fundamental Theorem of Calculus, we have $ G'(x) = g(x) $ so $ G'( \phi (x) ) = g( \phi (x) ).$

Thus, $$ f'(x) = \phi ' (x) \cdot g( \phi (x) ). $$


Show square matrix, then matrix is invertible Question:
Show that if a square matrix $A$ satisfies the equation $A^2 + 2A + I = 0$, then $A$ must be invertible.

My work: Based on the section I read, I will treat I to be an identity matrix, which is a $1 \times 1$ matrix with a $1$ or as an square matrix with main diagonal is all ones and the rest is zero. I will also treat the $O$ as a zero matrix, which is a matrix with all zeros.

So the question wants me to show that the square matrix $A$ will make the following equation true. Okay so I pick $A$ to be $[-1]$, a $1 \times 1$ matrix with a $-1$ inside. This was out of pure luck.

This makes $A^2 = [1]$. This makes $2A = [-2]$. The identity matrix is $[1]$.

$1 + -2 + 1 = 0$. I satisfied the equation with my choice of $A$ which makes my choice of the matrix $A$ an invertible matrix.

I know matrix $A *$ the inverse of $A$ is the identity matrix.

$[-1] * inverse = [1]$. So the inverse has to be $[-1]$.

So the inverse of $A$ is $A$.

It looks right mathematically speaking.

Anyone can tell me how they would pick the square matrix A because I pick my matrix out of pure luck?

The inverse of $A$ is almost certainly not $A$.  You have $A^2+2A=-I$, or $A(A+2I)=-I$.  Multiplying by $-1$ you get $$A(-A-2I)=I$$

Hence the inverse of $A$ is $-A-2I$.

Since $A^2 + 2A + I = 0$, $(A + I)^2 = 0$.
Hence $A = -I$, for any size square matrix.
Since the $det(-I) = 1$, the inverse exists.

Since $I* I = I$ and $-I * -I = I$

$A = -I * -I = A$

Thus, $A*A = I$, making $A$ its own inverse.

Another solution to this problem is as follows:

$A^2 + 2A = -I$

$A(A+2)= -I$
and thus $A(-A -2I) = I$ (Since the identity is basically 1), and thus $-A -2I$ is the inverse of $A$.

From earlier conclusion $A = -I$, and thus $-(-I) - 2I = -I = A$, so it remains that $A$ is its own inverse.


Fibonacci $\equiv -1 \mod p^2$ Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$?  I know none of the first $1000$ primes $> 3$ qualify.

EDIT: In response to Calvin Lin's comment:
Suppose $n$ is the period mod $p$. Of course the period mod $p^2$ is a multiple of $n$. If $M = \pmatrix{1 & 1\cr 1 & 0\cr}$, so that $M^k = \pmatrix{F_{k+1} & F_k\cr F_k & F_{k-1}\cr}$, that says
$M^n \equiv I \mod p$, so $M^n \equiv I + p A \mod p^2$ for some matrix $A$
with entries in $\mathbb Z_p$.  Then $M^{kn} \equiv I + k p A \mod p^2$.  If $A = 0$, the period mod $p^2$ is $n$, otherwise it is $pn$.

Note that $n$ divides $p-1$ (if $p \equiv \pm 4 \mod 5$) or $2p+2$ (if $p \equiv \pm 3 \mod 5$), and in either case is coprime to $p$.  Thus if the period mod $p^2$ is not $pn$, $p$ must be
a Fibonacci-Wieferich prime (see Noam Elkies' answer).

The set of such primes $p$ is probably infinite but very sparse,
and there are no such $p < 2 \cdot 10^{14}$.

We show that $p$ must be a "Fibonacci-Wieferich prime", i.e. a prime for which
$F_k \equiv 0 \bmod p^2$ for some $k \not\equiv 0 \bmod p$;
as with ordinary Wieferich primes (primes such as $1093$ and $3511$ for which
$2^p \equiv 2 \bmod p^2$), the number of such $p \leq x$ is expected
to grow as $\log \log x$ as $x \rightarrow \infty$.
Conversely, any Fibonacci-Wieferich prime $p$ will admit a congruence
$F_{np} \equiv -1 \bmod p^2$.

Suppose $p>5$.
Recall that $F_m = (\varphi^m - \overline\varphi^m) / \sqrt{5}$,
where $\varphi, \overline\varphi = (1 \pm \sqrt5) / 2$
with $\varphi \overline\varphi = -1$.
Hence if $F_m \equiv -1 \bmod p^2$ then $\varphi^m \bmod p^2$
is a root of $X^2 + \sqrt5 \, X - (-1)^m = 0$.
Thus if $m$ is odd then
$$
\varphi^m = \frac{-1 \pm \sqrt{5}}{2}
= -\varphi \ \ \text{or} \ \ \varphi^{-1},
$$
while if $m$ is even then
$$
\varphi^m = \frac{-3 \pm \sqrt{5}}{2}
= -\varphi^2 \ \ \text{or} \ \ -\!\varphi^{-2}.
$$
[This even case is where we must assume $p \neq 3$, because
the discriminant of $X^2 + \sqrt5 \, X - 1$ is $9 \equiv 0 \bmod 3$,
so $\phi^m$ can be congruent to one of its roots only modulo 3
but still satisfy the quadratic equation modulo 9.]
Thus if $m$ is odd then $\varphi^{m+1}$ or $-\varphi^{m-1}$ is $1 \bmod p^2$,
while if $m$ is even then $-\varphi^{m+2}$ or $-\varphi^{m-2}$ is $1 \bmod p^2$.
In each of these four cases, then,
if $m=np$ then $\varphi^k \equiv 1 \bmod p^2$ for some
$k$ that is not a multiple of $p$ (namely $k = m+1$, $2m-2$, or $2m\pm 4$).
This makes $p$ a Fibonacci-Wieferich prime.  The paper

  Richard J. McIntosh and Eric L Roettger:
  A search for
    Fibonacci-Wieferich and Wolstenholme primes,
  Math. of Computation 76 #260 (2007), 2087-2094.

explains why we expect the $\log \log x$ behavior, and reports on an
exhaustive search over $p < 2 \cdot 10^{14}$ that came up empty.

solutions $m$ of $F_m \equiv -1 \bmod p^2$ should include multiples of $p$.

Conversely, if $p$ is a Fibonacci-Wieferich prime then there exists some
even $k \not\equiv 0 \bmod p$ such that $\varphi^k \equiv 1 \bmod p^2$.
(If the smallest $k$ was odd then double it.)  By "Chinese Remainder"
$k$ has a multiple $k' \equiv 1 \bmod p$, and this $k'$ is again even with
$\varphi^{k'} \equiv 1 \bmod p^2$.  Therefore $F_{np} \equiv -1 \bmod p^2$
with $np = k'-1$ odd, QED.

Let $F_{u_{p^1}}$, denote the least positive Fibonacci number divisible by the prime $p$.

Let $F_{u_{p^2}}$, denote the least positive Fibonacci number divisible by $p^2$.

Let $\prod_{1}^{n\ge 1}$ be a quotient of primitive(characteristic) prime factor(s), ie factors that have not occurred in any earlier Fibonacci numbers.
This may be represented below as an empty product of one, if the quotient divides $F_{p^{e}_{1}},\ e>1$.

$\left \lbrace {n \mid m}\ \text{iff}\ {F_n \mid F_m} \right \rbrace\, n \ge 3 $ David Wells 1986, p.65

$p^2 \mid F_{u_{p^1}}\ \text{iff}\ F_{p^2} \mid F_{F_{u_{p^1}}}$

If an integer $i$, has prime factorization, $p_{1}^{e_{1}}\cdot\ p_{2}^{e_{2}}...p_{n}^{e_{n}}$ then the entry point of $i$ equals, $\left \lbrace u_{i} = \operatorname{lcm}[{ u_{p_{1}^{e_{1}}}, u_{p_{2}^{e_{2}}}, ...u_{p_{n}^{e_{n}}}}] \right \rbrace$.Marc Renault 1996 p.19 theorem 3.3 http//webspace.ship.edu/msrenault/fibonacci/FibThesis.pdf

$\text{If}\ i=F_{F_{u_{p^1}}}\ \text{then, }\ F_{p^2} \nmid\! F_{F_{u_{p^1}}}\text{ because } \left \lbrace u_{(F_{F_{u_{p^1}}})}\neq u_{(F_{F_{u_{p^2}}})} \right \rbrace$.

An abstract example of a Fibonacci-Wieferich prime p, where $p_{1}=p,\ e_{1}\ge 2$.
If $i=F_{F_{u_{p^1}}}=(F_{p_{1}^2}\ \cdot\ F_{p_{2}^{e_{2}}}\ \cdot\ ...\ F_{p_{n}^{e_{n}}}\ \cdot\ \prod{})$ then, can the entry point of $i$ still equal the same index, ie $u_{(F_{F_{u_{p^1}}})}=F_{u_{p^1}}$?
Answer No.
Proof
$u_i=\operatorname{lcm}[p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{u_{p^1}}]=\operatorname{lcm}[p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}}]\neq F_{u_{p^1}}=F_{p\cdot u_{p^1}}$
Since any extra powers of $p_{1}$, produce a later entry point, thus $F_{p^2}$ does not appear as a factor, in this configuration, until a later Fibonacci number, ie $F_{F_{p\cdot u_{p^1}}}=F_{F_{u_{p^2}}}$.
While the factor, $j=(F_{p_{1}^1}\ \cdot\ F_{p_{2}^{e_{2}}}\ \cdot\ ...\ F_{p_{n}^{e_{n}}}\ \cdot\ \prod{})$ always has an entry point of, $u_j=\operatorname{lcm}[p_{1}^1,\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{u_{p^1}}]=\operatorname{lcm}[p_{1}^1,\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}}]=F_{u_{p^1}}$.


Is my reasoning for this probability question correct?: Four fair dice are rolled. What is the probability of getting two different pairs? Four fair dice are rolled. What is the probability of getting two different pairs?

I basically used the multiplication rule here: the first die can have $6$ possible outcomes, while the second one can have only $5$. The last two can only have one outcome each because they have to match the numbers on the first and second dice. Hence the numerator becomes $6 \cdot 5 \cdot 1 \cdot 1$. Then I divided by all possible outcomes, which is $6^4$. So the probability $= 30/6^4 = .023$.

I think that another way to solve the problem is to assume that the outcome of the four dice can be expressed as two pairs, one of them with 6 different outcomes (from 1 to 6) and the other one with just 5 different outcomes (because you can't repeat the outcome you got for the first pair). So, we get 30 results. Then, due to the fact that we will have outcomes that can be expressed as (XX)(YY) or (YY)(XX) which have the same results, we divide the total outcomes by 2, such that we have only outcomes composed by "unique pairs" (e.g. if you have an outcome (XX)(YY), you are not going to consider, by the moment, as a different outcome (YY)(XX)). In every outcome, you have 4 elements, but there are only two different pairs, so you will have $\frac{4!}{2!2!}=6$ different orderings. In the end, you will have $15\times6=90$ different outcomes that meet the rule, so the probability will be $\frac{90}{6^4}$ or 0.069.

Hint:

The event of getting two different pairs have three 'types'.

All four different
Three same, one different
Two same, other two different


Period versus Pixel Width Calculation in Arnold's Cat Map I came across an article regarding Arnold's Cat Map, and it briefly mentions the period of the transformations.

To add some detail, it considers the cat or whatever it may be on a pixel map that is $p$ pixels wide. Since it is a unit square, it has $p^2$ pixels. To identify each point, one can label each pixel by a Cartesian coordinate of the form $(m/p, n/p)$.

To throw it out there, Arnold's Cat map is defined in matrix notation as follows

$\Gamma(\begin{bmatrix}x \\y\end{bmatrix}) =\begin{bmatrix}1 & 1 \\1 & 2\end{bmatrix} \begin{bmatrix}x \\ y\end{bmatrix}mod \hspace{1mm}1$

Knowing the unique position of each pixel, one can find the period of the pixel map. If the point is rational, it will eventually return to its original position. However, each point may have a different period. So the period of the pixel map has to be a multiple of each point's period. To define that relationship, we let $\Pi(p)$ denote the least common multiple of the periods of all the pixel points in the map where $\Pi(p)$ is the smallest integer that is divisible by all of the periods.

The article I was reading was considering a pixel map with width $p=101$. However, it simple says $\Pi(101) = 25$. The only other detail it provides is that if $p=101$ then all the points have period $1, 5, or \hspace{1mm}25.$ That's all the detail I have.

There are a few exercises relating to this. For instance,

$\Pi(p) = 3p$ iff $p=2*5^k$ for $k=1,2,...$

Find $\Pi(250)$, $\Pi(25)$...

Basically, how could I calculate these periods? The article didn't provide any examples.

Any feedback is appreciated.

The eigenvalues of $M=\left[\begin{matrix}1&1\\1&2\end{matrix}\right]$ are $\frac{3\pm \sqrt 5 }2$. Modulo a prime $p$, it depends on whether $5$ is a square modulo $p$. For example, with $p=101$, we have $45^2\equiv 5$, hence the eigenvalues are $\frac{3\pm 45}2$, that is $\equiv24$ and $\equiv 80$ (why?). One can calculate the period (under multiplication) of $24$ and $80$ and will find out that it is $25$ in both cases.
It follows (or one quickly computes) that $M^{25}$ is congruent to the identity matrix $\pmod p$. The only nontrivial divisor of $25$ is $5$, but $M^5$ is not the identity, so not all points have period $5$ (though they can be found via the linear equation $M^5 x \equiv x\pmod p$).

Hints for the exercises: Consider the case $p=2\cdot 5^k$.
Among others, you want to show that $M^{3p}\equiv E\pmod p$.
Note that $M^5=\left[\begin{matrix}34&55\\55&89\end{matrix}\right]=5\left[\begin{matrix}7&11\\11&18\end{matrix}\right]-\left[\begin{matrix}1&0\\0&1\end{matrix}\right]$. By induction, we find
$$M^{5^k}=5^k A_k+(-1)^kE$$
where $A_k$ is a symmetric matrix. Therefore, $M^{p/2}\equiv (-1)^kE\pmod {5^k}$, hence $M^p\equiv E\pmod {5^k}$. Now observe that also $M^5\equiv \left[\begin{matrix}0&1\\1&1\end{matrix}\right] \pmod 2$, hence by induction $M^{5^k}\equiv \left[\begin{matrix}e&1\\1&1-e\end{matrix}\right] \pmod 2$ with $e\in\{0,1\}$ and then $M^{3p}\equiv E\pmod 2$. Together with $M^{3p}\equiv E\pmod {5^k}$, this implies $M^{3p}\equiv E\pmod p$.

In the original version of Arnold's Cat, a modular system (0,1) is employed with non-integers. I like to always use the INTEGER modular system which handles modulo as is usual in whole numbers, over a square image of NxN pixel. The transformation would be:
x <--  (x + y) MOD N  and
y <--  (x + 2y) MOD N.
 My code that I have worked for several months, solves all your doubts and everything you need: periods of all points, complete orbits, maximum period, all images of the transformation, etc.
The difficulty might be that it is written in QB64, a very powerful version of completely free Basic, which is very easy to install and manage. The code is inappropriate to copy now here.
Manuel Sánchez Carrilero;   manuel.carrilero@uca.es


Proper way to determine kernel and show results I am working on a HW assignment for a linear algebra course and I want to make sure that the way I am determining the kernel of a matrix and presenting the results is correct.  Here is the problem and my solution:

For the following matrix, write the kernel as the span of a finite number or vectors.  Is the kernel a point, line, plane or all of $\mathbb{R}^{3}$

$$ \begin{bmatrix} 2 & 6 & -4 \\ -1 & -3 & 2 \end{bmatrix} $$

The first step is to put the matrix into row-echelon form

$$\begin{bmatrix} 2 & 6 & -4 \\ -1 & -3 & 2 \end{bmatrix} \quad \xrightarrow{R_{1} + 2 R_{2}} \quad \begin{bmatrix} 2 & 6 & -4 \\ 0 & 0 & 0 \end{bmatrix} $$

$x_{2}$ and $x_{3}$ are now free, so we need to write an equation for $x_{1}$ in terms of $x_{2}$ and $x_{3}$

$$ 2x_{1} + 6x_{2} - 4x_{3} = 0 \quad\to\quad 2x_{1} = -6x_{2} + 4_{x3} \quad\to\quad x_{1} = -3x_{2} + 2x_{3} $$

this now allows us to determine the kernel

$$ \vec{x} \,\,=\,\, \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix} \,\,=\,\, \begin{bmatrix} -3x_{2} + 2x_{3} \\ x_{2} \\ x_{3} \end{bmatrix} \,\,=\,\, x_{2} \begin{bmatrix} -3 \\ 1 \\ 0 \end{bmatrix} \,\,+ \,\, x_{3} \begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix} $$

the kernel is $\begin{bmatrix} -3 & 1 & 0 \end{bmatrix}^{T} ,\, \begin{bmatrix} 2 & 0 & 1 \end{bmatrix}^{T}$ and is a plane.

As mentioned before, this is a HW assignment so I am simply looking for advice and, if needed, guidance in the right direction.

Thank you in advance for any help

That's certainly correct, you need nothing more!


Given an integer $n$ let $S(n)$ denote the sum of digits of $n$
$$n=a_k\cdots a_1a_0\implies n=\sum_{i=0}^{k}a_i10^i \text{ and } S(n)=\sum_{i=0}^ka_i$$

  Claim 1:
  $n$ is divisible by $3$ if and only if $s(n)$ is divisible by $3$

proof The following congruences are true modulo $3$ because $10^i\equiv 1\mod 3$ for all $i$

$$3\text{ divides }n \Leftrightarrow n \equiv 0\Leftrightarrow \sum_{i=0}^{k}a_i10^i\equiv 0\Leftrightarrow \sum_{i=0}^{k}a_i1^i\equiv 0 \Leftrightarrow S(n)\equiv 0  \Leftrightarrow 3\text{ divides }s(n)$$

  Claim 2:
  $n$ is divisible by $9$ if and only if $s(n)$ is divisible by $9$

Proof (the same as for claim1)

Now we can conclude using claim $1$  and claim $2$ that $s(3\cdot 2^n)$ is divisible by $3$ and not divisible by $9$

For a number to be divisible by $9$ it needs to have two $3$s in it's prime factorization.

With that in mind it's pretty obvious $3\cdot2^n$ doesnt divide $9$.

Or equivalently 3 doesn't divide $2^n$.

Try and see if you can prove that.


Probability of Head in coin flip when coin is flipped two times Probability of getting a head in coin flip is $1/2$.
If the coin is flipped two times what is the probability of getting a head in either of those attempts?

I think both the coin flips are mutually exclusive events, so the probability would be getting head in attempt $1$ or attempt $2$ which is:

$$P(\text{attempt $1$}) + P(\text{attempt $2$}) =  1/2 + 1/2 = 1$$

$100\%$ probability sounds wrong? What am I doing wrong. If I apply the same logic then probability of getting at least $1$ head in $3$ attempt will be $1/2+1/2+1/2 = 3/2 = 1.5$ which I know for sure is wrong. What do I have mixed up?

You are confusing the terms "independent" and "mutually exclusive".  These are not the same thing.  In fact events cannot be both "independent" and "mutually exclusive".  It's either one, the other, or neither.

"Mutually exclusive" simply means that the two events cannot happen together.  If A happens then B does not and if B happens A does not.

"Independent" simply means that the occurrence of one event is not conditional on the occurrence of the other.  The probability of A happening does not depend on whether B happens or not, and vice versa.

Let $H_n$ be the indexed event of getting a head on the $n^{th}$ flip.

Given an unbiased coin, $P(H_1)=P(H_2)=\frac 1 2$

These events are independent so $P(H_1 \cap H_2) = P(H_1)\times P(H_2)$.  The outcome of one coin toss does not influence the outcome of the other.

However they are not mutually exclusive, so $P(H_1 \cup H_2) = P(H_1)+P(H_2) - P(H_1 \cap H_2)$.  Both coins can turn up heads.

Putting it together: $$\therefore P(H_1 \cup H_2) = \frac 12 + \frac 1 2 - \frac 12 \times \frac 12 = \frac 3 4$$

I haven't seen the correct result yet.  This one is easy as it is easy to run the possible results.  They key is that if you get Heads the first time you don't need to flip again.  So when people list 'HH or 'HT' they are wrong.

Options:
H
TH
TT

2 out of 3 possibilities have 'H'   = 2/3  = 66.66%


Improper integral of $\frac{1}{(x^2 + y^2)}$ on $(x-1)^2 + y^2 \leq 1$ Integrate $\frac{1}{(x^2 + y^2)}$
Domain : $(x-1)^2 + y^2 \leq 1$

Hint
$$
{x=r\cos\theta
\\
y=r\sin\theta
}
$$
and
$$
(x-1)^2+y^2\le 1\equiv r\le 2\cos\theta\quad,\quad -\frac{\pi}{2}\le\theta\le \frac{\pi}{2}
$$


A complex integral which shouldn't diverge, where is my mistake? First of all I have a small request. I was banned for a very long time because I got lazy and formulated my questions without any effort. I accept the punishment and I'm happy I got a second chance. From now on I try to put as much effort in my questions as possible. This is my first question after the ban and it would make me happy if you don't down-vote if you think that my question is not good or not understandable since I'm probably getting banned again. Please write suggestions for improvement in the comments. Thank you and sorry for this way too long introduction. So here we go :)
What do I want to solve?
I want to calculate
$$I = \cfrac{1}{2\pi i}\int \limits_{c-i\infty}^{c+i\infty}\cfrac{\log(s-1)}{s^2}\,x^s \mathrm{d}s,$$
where $c>1$ along the same contour as in "Applications of integral theorems", example 5: https://en.wikipedia.org/wiki/Contour_integration#Example_5_–_the_square_of_the_logarithm. To implement our integral $I$ we modify our desired closed contour integral to
$$\oint_\mathcal{C}= \left(\int_{R_1}+\int_{R_2}+\int_M+\int_N+\int_r+\int\limits_{c-i\infty}^{c+i\infty}\right)\cfrac{\log(s-1)}{s^2}\,x^s\mathrm{d}s,$$
where$R_1$ ends at $c+i\infty$ and $R_2$ ends at $c-i\infty$.
The whole integral is actually an Inverse laplace transform, if we define $t=\log(x)$. If we put $\frac{\log(s-1)}{s^2}$in this online calculator https://www.emathhelp.net/calculators/differential-equations/inverse-laplace-transform-calculator/?f=ln%28s-1%29%2Fs%5E2 we get $-t\operatorname{Ei}(t)+e^t-1 \Longleftrightarrow-\log x\operatorname{li}(x)+x-1$.
How I tried to solve it
The integrals $R_1,R_2$ and $r$ tend to zero (I use the same notation as in the Wikipedia link). The closed contour is also equal to zero since $0$ is excluded from the contour. After parameterizing $s=-s_\mathcal{R}+i\varepsilon$ for $M$ and $s=-s_\mathcal{R}-i\varepsilon$ for $N$ we get:
$$I + \int\limits_{0}^{\infty}\cfrac{\log\lvert-s_\mathcal{R}+i\varepsilon-1\rvert + i\pi}{(-s_\mathcal{R}+i\varepsilon)^2}\,x^{-s_\mathcal{R}+i\varepsilon}\mathrm{d}s_\mathcal{R}-
    \int\limits_{0}^{\infty}\cfrac{\log\lvert-s_\mathcal{R}+i\varepsilon-1\rvert - i\pi}{(-s_\mathcal{R}-i\varepsilon)^2}\,x^{-s_\mathcal{R}-i\varepsilon}\mathrm{d}s_\mathcal{R} = 0$$
If we now let $\varepsilon\rightarrow0$ we can also evaluate the absolut value. Our new expression is
$$\begin{align}
    I + \int\limits_{0}^{\infty}\cfrac{\log(s_\mathcal{R}+1) + i\pi}{s_\mathcal{R}^2}\,x^{-s_\mathcal{R}}\mathrm{d}s_\mathcal{R}-
    \int\limits_{0}^{\infty}\cfrac{\log(s_\mathcal{R}+1) - i\pi}{s_\mathcal{R}^2}\,x^{-s_\mathcal{R}}\mathrm{d}s_\mathcal{R}
    =0,
\end{align}$$
which is the same as saying that
$$I = -2\pi i\int\limits_{0}^{\infty}\cfrac{1}{x^{s_\mathcal{R}}s_\mathcal{R}^2}\mathrm{d}s_\mathcal{R}$$
And now the disappointment: If I put "integral from 0 to infinity of 1/(a^x*x^2)" into Wolfram Alpha it returns "(integral does not converge)". I can't find the mistake I did while evaluating. Please give me a small hint what I should correct to get the desired result. Thank you :)!
Edit: I want to thank Maxim for helping me with my question. My mistake was the definition of the branch of $\log(s-1)$. Now I (only) have to solve
$$\lim_{\varepsilon\to0}\left(\int\limits_{0}^{\infty}\cfrac{\log\lvert-s_\mathcal{R}+i\varepsilon-1\rvert + i\pi}{(-s_\mathcal{R}+i\varepsilon)^2}\,x^{-s_\mathcal{R}+i\varepsilon}\mathrm{d}s_\mathcal{R}-
    \int\limits_{0}^{\infty}\cfrac{\log\lvert-s_\mathcal{R}+i\varepsilon-1\rvert - i\pi}{(-s_\mathcal{R}-i\varepsilon)^2}\,x^{-s_\mathcal{R}-i\varepsilon}\mathrm{d}s_\mathcal{R}\right),$$
what could get a little bit hard since I'm not allowed to set $\varepsilon$ to $0$ immediatly.

$\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{\on}[1]{\operatorname{#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}$
The integral $\ds{\underline{vanishes\ out}}$ when
$\ds{\underline{\Re\pars{\ln\pars{x} < 0}}}$.

When $\ds{\underline{\Re\pars{\ln\pars{x} > 0}},\quad}$ lets $\ds{\tau \equiv \ln\pars{x} >0 }$
\begin{align}
I & \equiv \bbox[5px,#ffd]{\left.%
\int_{c - \ic\infty}^{c + \ic\infty}\
{\ln\pars{s - 1} \over s^{2}}\expo{\tau s}
{\dd s \over 2\pi\ic}\,\right\vert_{\substack{c\ >\ 1
\\[2mm] \Re\pars{\tau\ \equiv\ \ln\pars{x}}\ >\ 0}}}
\\[5mm] & =
-\int_{-\infty}^{1}\
{\ln\pars{1 - s} + \ic\pi \over
\pars{s + \ic 0^{+}}^{2}}\expo{\tau s}{\dd s \over 2\pi\ic}
\\[2mm] & \,\,\,\,-
\int_{1}^{-\infty}\
{\ln\pars{1 - s} - \ic\pi \over
\pars{s - \ic 0^{+}}^{2}}\expo{\tau s}{\dd s \over 2\pi\ic}
\\[5mm] & =
-\int_{-1}^{\infty}\
{\ln\pars{1 + s} + \ic\pi \over
s^{2} - \ic\on{sgn}\pars{s}\,0^{+}}
\expo{-\tau s}{\dd s \over 2\pi\ic}
\\[2mm] &\,\,\,\,\,\,\, -
\int_{-1}^{\infty}\
{\ln\pars{1 + s} - \ic\pi \over
s^{2} + \ic\on{sgn}\pars{s}\,0^{+}}
\expo{-\tau s}{\dd s \over 2\pi\pars{-\ic}}
\\[5mm] & =
-2\,\Re\int_{-1}^{\infty}\
{\ln\pars{1 + s} + \ic\pi \over
s^{2} - \ic\on{sgn}\pars{s}\,0^{+}}
\expo{-\tau s}{\dd s \over 2\pi\ic}
\\[5mm] & =
-{1 \over \pi}\,\Im\int_{-1}^{\infty}\
{\ln\pars{1 + s} - \ic\pi \over
s^{2} - \ic\on{sgn}\pars{s}\,0^{+}}
\expo{-\tau s}\dd s
\\[5mm] & =
-{1 \over \pi}\,\Im\left\{%
\mrm{P.V.}\int_{-1}^{\infty}\
{\ln\pars{1 + s} - \ic\pi \over s^{2}}
\expo{-\tau s}\dd s
\right.
\\[2mm] &\ \left.%
+ \int_{-1}^{\infty}
\bracks{\ln\pars{1 + s} - \ic\pi}\expo{-\tau s}
\bracks{\ic\pi\on{sgn}\pars{s}\,\delta\pars{s^{2}}}\,\dd s\right\}
\\[5mm] & =
\mrm{P.V.}\int_{-1}^{\infty}{\expo{-\tau s} \over s^{2}}\,\dd s
-
{1 \over 2}
\int_{-1}^{\infty}{\ln\pars{1 + s} \over s}
\expo{-\tau s}\,\delta\pars{s}\,\dd s
\\[5mm] & =
2\ \underbrace{\int_{0}^{1}
{\cosh\pars{\tau s} \over s^{2}}\,\dd s}
_{\ds{\color{red}{\mbox{It diverges !!!}}}}
\\[2mm] & +\
\underbrace{\int_{1}^{\infty}{\expo{-\tau s} \over s^{2}}\,\dd s}
_{\ds{{1 \over x} - \ln\pars{x}\on{E}_{1}\pars{\ln\pars{x}}}}\
-\ {1 \over 2}
\end{align}
$\ds{\on{E}_{1}}$ is the
Exponential Integral Function.


Binary Linear Codes of Minimum Distance 3 Let $B_n$ denote the maximum size of a binary linear code (a binary code that is closed under addition) whose codewords have length $n$ and whose minimum distance is $3$. I have been searching for the best-known lower bounds for $A(n,3)$, but I can't seem to find anything. My question is simply: What are some lower bounds for the numbers $B_n$?

The binary Hamming code with parameters $[n,k,d]=[2^m-1,2^m-m-1,3]$ is perfect (no larger code exists) and for the values of $n=2^m-1,$ $m\geq 3$ provides the lower bound $$A_{2^m-1}\geq 2^{(2^m-m-1)}$$.

So $A_7\geq 16,$ etc.

The Gilbert-Varshamov bound states that for alphabet size $q$ a prime power, there exists a linear $[n,k]$ code with minimum distance at least $d$ provided
$$q^{n-k}\geq \sum_{i=0}^{d-2} {n-1 \choose i} (q-1)^i.$$ So you can take $q=2$ and find the largest $k$ satisfying this inequality.

There is a table in Roman's Coding Theory book, which has the following information (but for all, not necessarily linear codes).
$$
\begin{array}{cl}
n & A(n,d) \\
5 & 4\\ 6& 8 \\ 7 & 16\\ 8 & 20\\ 9 & 40 \\ 10 & 72-79 \\ \cdots & \cdots \\ 16 & 2560-3276 \end{array}$$

Let $F$ be the finite field of size $2$ and let $K = F^n$. Of those $K$ subcodes of distance $3$ fix a $K$ subcode $C$ of maximum dimension. The unit $K$ codewords together generate $K$ while the non-trivial quotient code $K/C$ has a Hamel basis $Z$ made of unit $K/C$ codewords; i.e. made of $C$ cosets that contain a unit $K$ codeword.

$Z$ has at most size $2$ or else $K/C$ would have a codeword of weight $3$ which is false. $C$ is not a hyperplane or else for distinct unit $K$ codewords $u,v$ we'd have $u+v$ in $C$ implying there exists a $C$ codeword of weight $2$ which is false.

Therefore, $Z = n - dim(C) = 2$ and $dim(C) = n - 2$ and $B_n = 2^{n-2}$.


Is $\Bbb R^2 -\Bbb Q^2$ connected? I need to prove whether or not $X=\Bbb R^2 -\Bbb Q^2$ is connected. The definition of connectedness I am using is a space X is connected if it is not the union of two disjoint nonempty open sets. This is a very new concept for me so I am not exactly sure how to set it up. I believe we will prove it by contradiction, but I do not know where to start.

Take two points $x,y \in X$. Since $\Bbb{Q}^2$ is countable and the number of lines going through $x$ is uncountable (in bijection with $[0,\pi)$), there are uncountably many lines going through $x$ and contained in $X$. The same applies to $y$. Therefore, you can find lines going through $x$ and $y$ respectivly that are not parralel, and thus intersect each other. This proves that $X$ is connected.

Fix two points $(x,y), (u,v) \in A:= \mathbb{R}^2\setminus \mathbb{Q}^2$.

Suppose $x, v\notin \mathbb{Q}$ then the lines joining $(x,y)\to (x,v)$ and $(x,y) \to (u,v)$ are both in $A$.

Something similar happens if $y,u \notin \mathbb{Q}$.

If $x,u\notin \mathbb{Q}$, then assume WLOG that $v<y, u<x$ and choose $z \in (v,y)\setminus \mathbb{Q}$ and $w\in (u,x)\setminus \mathbb{Q}$. So the lines $(x,y) \to (z,w), (z,w) \to (u,w)$ and $(u,w) \to (u,v)$ are all in $A$.

Similarly if $y,v\notin \mathbb{Q}$. Hence $A$ is path-connected, and so connected.


Why perfect square has odd number of factors can someone please describe me why only the perfect square has odd number of factors.why does other number not has odd numbers of factors? I understand it but don't find any mathmetical proof.Please help me

For a given number $n$ we can group its divisors in pairs $(d,\frac nd)$, except that if $n=m^2$ this would pair $m$ with itself.

Well, without the square root, the square no. would be even. Since the square root is multiplied by itself, then there is only 1 more factor, not 2.

Example: 64. Has 6 factors (excluding 8 (squared)). With 8, there is now 7 factors... but not eight because the root (in this case, 8) will be repeated, and there is simply no point in repeating it.

I hope your question is answered! :)


What does it mean when two functions are "orthogonal", why is it important? I have often come across the concept of orthogonality and orthogonal functions e.g in fourier series the basis functions are cos and sine, and they are orthogonal. For vectors being orthogonal means that they are actually perpendicular such that their dot product is zero. However, I am not sure how sine and cosine are actually orthogonal. They are 90 out of phase, but there must be a different reason why they are considered orthogonal. What is that reason? Does being orthognal really have something to do with geometry i.e 90 degree angels?

Why do we want to have orthogonal things so often in maths? especially with transforms like fourier transform, we want to have orthogonal basis. What does that even mean? Is there something magical about things being orthogonal?

The concept of orthogonality with regards to functions is like a more general way of talking about orthogonality with regards to vectors. Orthogonal vectors are geometrically perpendicular because their dot product is equal to zero. When you take the dot product of two vectors you multiply their entries and add them together; but if you wanted to take the "dot" or inner product of two functions, you would treat them as though they were vectors with infinitely many entries and  taking the dot product would become multiplying the functions together and then integrating over some interval. It turns out that for the inner product (for arbitrary real number L) $$\langle f,g\rangle = \frac{1}{L}\int_{-L}^Lf(x)g(x)dx$$ the functions $\sin(\frac{n\pi x}{L})$ and $\cos(\frac{n\pi x}{L})$ with natural numbers n form an orthogonal basis. That is $\langle \sin(\frac{n\pi x}{L}),\sin(\frac{m\pi x}{L})\rangle = 0$ if $m \neq n$ and equals $1$ otherwise (the same goes for Cosine). So that when you express a function with a Fourier series you are actually performing the Gram-Schimdt process, by projecting a function onto a basis of Sine and Cosine functions. I hope this answers your question!

Here is a way to consider it, for what it's worth.  Plot f and g on separate sheets of paper. For convenience, put the sheet with the graph of f horizontally and the sheet with the graph of g vertically (at a 90 degree angle) to the other sheet.  Take a value of x, and for simplicity, assume that f(x) is positive.  So, you can point your right thumb from the x axis out to f(x).  If g(x) is also positive, you can point your right index finger up to it.  In such a case, the cross product of f(x) and g(x) points in the direction of the third finger of your right hand towards you.  If f(x) is positive but g(x) is negative, then the third finger of your right hand points away from you.  Or, in other words, f(x), g(x), and f(x) cross g(x) form a left-handed system at that x.  Now integrate over the region.  If f, g, and f cross g "on average" (bearing in mind that the magnitude of f(x) cross g(x) is f(x) times g(x)) are left handed just as much as they are right handed, then f and g are orthogonal.  I hope this makes sense.  You might try visualizing it with sine and cosine for a specific example.


Finitely generated field extensions If $F=K(u_1,\ldots,u_n)$ is a finitely generated extension of $K$ and $M$ is an intermediate field, then $M$ is a finitely generated extension of $K$.

I'm not exactly sure how to start this problem. Any help at all would be a tremendous help.

Firstly, I encourage you to simply try this with the tower rule ( $[F:K] = [F:M][M:K]$ ). Remember that you can consider the transcendent degree separately. However, if that is insufficient, I direct you to this answer over at MO.

The accepted answer covers this question very nicely, including the cases for transcendence.

I messed up last time. What I showed was not correct, $F$ need not be finite dimensional over $K$ just because it is finitely generated, counter example would be any transcendental extension.

Let $T = \{u_1,\cdots,u_n\}$. WLOG, let $A = \{u_1,\cdots,u_m\}\subset M$ and $B = \{u_{m+1},\cdots,u_n\}\cap M = \varnothing$. That is we partition $T = A\cup B$ into two sets $A$ and $B$, where $A$ contains all $u_i\in M$ and $B$ contains the rest.

Since $M\subset K(T)$, all elements of $M$ are in the form of $f(u_1,\cdots,u_n)$, where $f\in K(x_1,\cdots,x_n)$, the field of rational functions with coefficients in $F$ with $n$ variables.

But since $M\cap B = \varnothing$, all elements of $M$ are in the form of $f(u_1,\cdots,u_m,0,\cdots,0)$ where from position $m+1$ to $n$ its all $0$. That is all elements of $M$ are the form of $f(u_1,\cdots,u_m)$ where $f\in K(x_1,\cdots,x_m)$. Thus $M\subset K(u_1,\cdots,u_m)$.

Also $M\supset K(u_1,\cdots,u_m)$ because $M\supset K$ and $M\supset A$. That is $M = K(u_1,\cdots,u_m)$.


What is the difference between Set, and Class in object oriented languages? What is the difference between Set in set theory, and Class in object oriented languages?

There are debates about the definition, but, for elementary work, a set is just a collection of things, which are called its "members". So $\{3, \pi, \text{Jupiter}\}$ is a set whose members are two numbers and a planet. The members of a set do not all have to be the same kinds of things, and they do not need to have any relationship to each other.

In object-oriented programming, a class provides a "blueprint" or "template" for objects of a similar type, that have some common set of properties and methods. Specific objects that follow the blueprint are called "instances" of the class.

In programming, the closest thing to a set is a C# ArrayList or a Python tuple. These are both collections whose members can be anything you like. For example

ArrayList a = { 3, System.Math.Pi, "hello" };

is a perfectly legal definition of an ArrayList whose members are two numbers and a string.

But sets and ArrayList-like collections still have some large differences. ArrayLists are finite, and sets are often infinite. Also, the elements of an ArrayList have a specific order, and elements of a set do not. In common programming languages, I can't think of a data structure that represents an unordered collection.

In short, sets and classes have very little in common, so asking how they are different is a somewhat odd question.

In set theory, there are things called equivalence relations which can be used to glob things that are alike into sets called equivalence classes. I think this is where the class idea comes from programming. The objects created by a class in programming all have the same structure and so in some sense they are equivalent!

A class in programming is a "program-code-template" so I don't know what type of "thing" a template even is. This question is way too hard.


Examples of partial functions in which the domain is not known? I was reading this, it mentions about a kind of function in which the exact domain is not known. The only example given is this one - and I'm not really sure I understood it. I got curious about it:

What are examples of these functions? (beyond the one I suggested as an example)
What would be needed to know their exact domain?

I got curious about it because I'm an undergraduate student, every function I've seen had a known domain. The idea of not having a domain is completely alien to me. Notice that It's notvery clear what exact domain is, I have in mind only the discrepancy of domain/image.

Consider the partial function which takes as input a Turing machine and returns as output its halting time if it has one. The exact domain of this function, namely the set of Turing machines which have halting times, is in a pretty strong sense impossible to know because the halting problem is undecidable.

Suppose $f\subset A\times B$. Then $f$ is a partial function if and only if for all $x\in A$ and all $y_1,y_2\in B$, if $(x,y_1)\in f$ and $(x,y_2)\in f$ then $y_1=y_2$. (Unlike others, this definition does not specify a domain for $f$. Implicitly, the domain is some subset of $A$.)

You can still use the functional notation $f(x)=y$, but you cannot assume that $f(x)$ is defined for every $x\in A$.

Examples:

$f= \{(2,9), (5, 7)\}\subset N^2$ is a partial function on $N$ where $f(2)=9$ and $f(5)=7$.

$g= \{(2,9), (2, 7)\}\subset N^2$ is not a partial function on $N$ since $2$ is mapped to different values.

$h= \{(9,2), (7,2)\}\subset N^2$ is a partial function on $N$  even though different elements of $N$ are mapped to the same value, where $h(9)=2$ and $h(7)=2$.


Evaluate: $\csc^2\left(\frac{\pi}{9}\right)+\csc^2\left(\frac{2\pi}{9}\right)+\csc^2\left(\frac{4\pi}{9}\right)$ $$\csc^2\left(\frac{\pi}{9}\right)+\csc^2\left(\frac{2\pi}{9}\right)+\csc^2\left(\frac{4\pi}{9}\right) \;=\; \text{???}$$

$\bf{My\; Try::}$ Let $\displaystyle \frac{\pi}{9} = \theta\;,$ Then $9\theta = \pi\Rightarrow 6\theta = \pi-3\theta$

So $\sin (6\theta) = -\sin (3\theta)\Rightarrow 2\sin 3 \theta \cdot \cos 3 \theta+\sin 3 \theta =0$

So we get $\displaystyle \sin 3 \theta \cdot \left[2\cos 3 \theta +1\right] =0$

So we get $\sin 3\theta = 0$ or $2\cos 3 \theta+1=0$

Now i did not understand how can I convert into $\sin^2$ form, Help me

Thanks

Like my answer here in Sum of tangent functions where arguments are in specific arithmetic series

$$\tan9x=\dfrac{\binom91t-\binom93t^3+\binom95t^5-\binom97t^7+t^9}{\cdots}$$ where $t=\tan x$

If $\tan9x=0,9x=n\pi$ where $n$ is any integer

So, the roots of $$\binom91t-\binom93t^3+\binom95t^5-\binom97t^7+t^9=0$$ are $\tan\dfrac{r\pi}9$ where $n\equiv0,\pm1,\pm2,\pm3,\pm4\pmod9$

As $\tan0=0,$ the roots of $$\binom91-\binom93t^2+\binom95t^4-\binom97t^6+t^8=0$$ are $\tan\dfrac{r\pi}9$ where $r\equiv\pm1,\pm2,\pm3,\pm4\pmod9$

Putting $c=1/t,$ the roots of $$\binom91c^8-\binom93c^6+\binom95c^4-\binom97c^2+1=0$$  are $\cot\dfrac{r\pi}9$ where $r\equiv\pm1,\pm2,\pm3,\pm4\pmod9$

Putting $c^2=d,$  the roots of $$\binom91d^4-\binom93d^3+\binom95d^2-\binom97d+1=0$$  are $\cot^2\dfrac{r\pi}9$ where $r\equiv1,2,3,4\pmod9$

$$\sum_{r=1}^4\cot^2\dfrac{r\pi}9=\dfrac{\binom93}{\binom91}=?$$

But $r=3\implies\cot^2\dfrac{3\pi}9=3$

Use $\csc^2u=1+\cot^2u$

Can you take it from here?

As a partial answer, finding the trig value for $\sin\left(\frac{\pi}{9}\right)$ is discussed here: http://mathworld.wolfram.com/TrigonometryAnglesPi9.html


Triple Integral with spherical coordinates Find the volume of the region bounded by $(x^2 + y^2 + z^2)^2 = x$.

I used spherical coordinates to get $p^3 = \sin \phi \cos \theta$ so does this imply that

$ 0<= p <= (\sin \phi \cos \theta)^{1/3}$. And if so would there be no restrictions to

$\phi $ and $\theta$ other than the regular ($ 0 \leq \phi \leq \pi$ and $ 0 \leq \theta \leq 2\pi$)? I tried this but the maple returns $0$ when it evaluates the triple integral.

The volume is $V = \pi/3$. First observe that, if $(x,y,z)$ belongs to the region, then $0 \leq x \leq 1$. Fix now $0 \leq x_0 \leq 1$. The points on the plane $\{x = x_0\}$ form a circle of radius $r(x_0)$, where
$$
r(x_0)^4+2r(x_0)^2x_0^2+x_0^4 = x_0,
$$
i.e.,
$$
r(x_0)^2 = \sqrt{x_0} - x_0^2.
$$

Now we integrate by sections to get
$$
V = \int_0^1 \pi(\sqrt{x}-x^2) dx = \frac{\pi}{3}.
$$

This is the same as the volume of the region bounded by $$(x^2+y^2+z^2)^2=z$$  You may find this easier to evaluate in spherical coordinates.


Long inverse trignometry If we are given the following equation:
$$y =\arctan \frac{\sqrt{1+x^2}-\sqrt{1-x^2}}{\sqrt{1+x^2}+\sqrt{1-x^2}}$$
Then we have to prove $x^2 = \sin2y$

I tried by multiplying the eqiuation by 2 on both side  then tried to convert arctan into arcsin.

But it becoes too long to solve

Is there any short method.

HINT:

$$\tan y=\dfrac{\sqrt{1+x^2}-\sqrt{1-x^2}}{\sqrt{1+x^2}+\sqrt{1-x^2}}$$

Use  Weierstrass substitution

You may use componendo and divedendo.
Thoughts:-

if $a/b=c/d$ then ($a+b)/(a-b)=(c+d)/(c-d)$ and vice-verca.

so $\frac{\tan y + 1}{\tan y - 1}= - \left(\frac{1+x^2}{1-x^2}\right)^{1/2}$

square both sides and then apply componendo & dividendo again to get the desired result.


Uniformly convergent sequence proof. Prove that if $(f_k)$ is a uniformly convergent sequence of continuous real-valued functions on a compact domain $D\subseteq \mathbb{R}$, then there is some $M\geq 0$ such that $\left|f_k(x)\right|\leq M$ for every $x\in D$ and for every $k\in \mathbb{N}$.

My response: Basically, I am trying to show that uniform convergence on a compact domain implies uniform boundedness. Let $f(x)$ be the limiting function. Then I know that
$\lim_{k\to\infty} \sup_{x \in D} | f_k (x) - f(x) | = 0$. Also, I know that $f$ is continuous, therefore it attains an absolute maximum $\in D$. How can I apply these two things to prove it?

You are very much on the right track. So I'll try to bump you the rest of the way there.

We want to find a bound on all $f_k$ simultaneously.

It is not too hard to simultaneously bound any finite collection of our functions. This means we can control any finite initial segment of our sequence fairly easily.

As you have noted, $f$ is also continuous and hence has a maximum $M$.

Then by uniform convergence have some $N$ large so that for $n\geq N$ we know that $$\lvert f(x) - f_n(x)\rvert < 1$$ for all $x$.

This gives us a bound on the tail of the sequence, they can be no bigger than $M + 1$.

So now can you combine these controls over the tail and initial segment of our sequence to finish the proof?

I think this is quite obvious. Noted that $D$ is compact and $f$ is continuous so $f_k(D)$ is also compact for every $k$ and hence it is bounded for every $k\in\mathbb{N}$ and we can just take $M=\sup\bigcup f_k(D)$ where $M \ne +\infty$ as every $f_k(D)$ are bounded.


Can a mathematical proof always be objectively determined as correct or incorrect? Fields medalist Michael Atiyah claimed a simple proof of the Riemann hypothesis, but many mathematicians rejected his proof. Am I right in saying that Atiyah's proof is either objectively correct (then why did many mathematicians reject it?) or objectively incorrect (then as one of the leading mathematicians, Atiyah failed to find his own mistake(s)). Or is it possible that the truthfulness of Atiyah's proof cannot be determined?

So my question is,

  In a certain axiomatic system, can a mathematical proof always be objectively determined as correct or incorrect? Or is it possible that there exists a proof to a result such that the truthfulness of the proof cannot be determined?

Here I am not considering the cases such as the proof contains typos or gramatical mistakes which can easily be fixed.

If you completely formalize the statement and the proof, it can be, in principle , checked automatically, whether the given proof shows the given statement. This is also true for computer proofs because they must have a finite running time. This does however not at all mean that such a verification can be done in a reasonable time.

A SIMPLE proof of the Riemann hypoethesis is so unlikely, that I heavily doubt every such proof whoever claims to have found it.

For proofs on paper one should always be able to check if its objectively correct.

The situation is different if its a computer proof such as the four-color problem. Here a program checks all the possible cases. Its hard for the individual to check if its objectively correct. At least, its questionable.


$C_c^\infty(\Omega)\subseteq L^p(\Omega)$ for any open $\Omega$? Let $d\in\mathbb N$ and $\Omega\subseteq\mathbb R^d$. Can we show that $$C_c^\infty(\Omega)\subseteq L^p(\Omega)\tag 1$$ for all $p\in [1,\infty]$? It's clear that $(1)$ holds if $\Omega$ has finite Lebesgue measure. And it's clear that $(1)$ holds for $p=\infty$.

Let $f\in C^\infty_c(\Omega)$. Then $f$ is supported in a compact set $K$ and $|f|$ attains a maximum $C$ in this $K$. Thus

$$\int_{\Omega} |f|^p dx = \int_K |f|^p dx \le \int_K C^p dx = \text{Vol}(K) C^p.$$

Thus $f\in L^p$ for all $p$. Indeed $C^\infty_c(\Omega)$ is dense in $L^p$ for all $1\le p <\infty$.

Not sure this is the fastest and most elegant solution, but this fact is rather a standard fact from distribution theory.

$\textbf{First case}:$ If $\Omega$ is bounded than it is obvious (as you wrote), since set has finite Lebesgue measure.

$\textbf{Second case}:$ Set $\Omega$ is open and unbounded. This is not trivial fact (but a good excercise) to show that in $R^d$ every open set can be represented as a countable union of open balls - therefore it is true for $\Omega$. Therefore it can be shown that it is possible to build an increasing sequence of compact sets $\{K_n\}, \, K_i\subset \Omega$
$$
 K_1 \subset K_2 \dots \subset K_n\dots, \, \bigcup_i K_i = \Omega.
$$
Having such sequence it is possible to build $L^p$ approximations of any function $f\in L^p(\Omega)$ by setting $f_n(x) = f(x)\cdot I_{K_n}(x)$. By the Lebesgue Theorem for limits of function sequences, this $\{f_n(x)\}$ will be indeed an approximation in $L^p$ - norm (also as an exercise to show it).
The technical point then is to choose the $K_i$ such that the support of $f_n(x)$ will be $\delta$-inside the $\Omega$ (it is not difficult to do, knowing that $\Omega$ is a countable union of open balls). The last we do - take some function $\phi\in C^{\infty}_c(\Omega)$ from the ``delta-sequence''  with support in the $\delta/2$-ball in $R^d$. Taking a convolution $\phi*f_n$ will give you a function from $C^{\infty}_c(\Omega)$
with desired accuracy in $L^p$ norm.

p.s. Sorry that I didn't wrote what is delta-sequence, but it is rather standard object from distribution theory, same as idea of smoothing through convolution.


If $F$ is closed, does there exist a finite measure on $[0,1]$ with support $F$? If $X$ is a metric space, $\mathcal B$ is the Borel $\sigma$-algebra, and $\mu$ is a measure on $(X, \mathcal B)$, then the $support$ of $\mu$ is the smallest closed set $F$ such that $\mu(F^c) = 0$. Show that if $F$ is a closed subset of $[0,1]$, then there exists a finite measure on $[0,1]$ whose support is $F$.

My Solution:

Let $F$ be a closed subset of $[0,1]$ and $\mu_F$ be defined by $\mu_F(B) = m(B \cap F)$ for any $B \in \mathcal B_{[0,1]}$. Since $F$ is a closed subset of $[0,1]$, it is in $\mathcal B_{[0,1]}$ and $\mu_F$ is a measure. The measure is finite since $\mu_F([0,1]) = m([0,1] \cap F) \leq m([0,1]) = 1$ and since $\mu_F(F^c) = m(F^c\cap F) = m(\emptyset) = 0$, the support of $\mu_F$ is $F$.

My questions:

Why do we need the condition that $X$ is a metric space to define the support?

Is my answer correct?

Second Try:

Let $F$ be a closed subset of $[0,1]$. Since any subset of $[0,1]$ is separable, there exists a countable set $A \subset F$ such that $F$ is the closure of $A$.

If $A = \{a_1, a_2,\dots, a_k\}$ is finite, let $\mu(B) = \frac{1}{k}\cdot n(B \cap A)$ where $n$ is the counting measure. Then $\mu([0,1]) = \frac{1}{k}\cdot n([0,1] \cap A) = \frac{1}{k}\cdot n(A) =  1$ so that $\mu$ is finite, and $\mu(F^c) = \frac{1}{k}\cdot n(F^c \cap A) = \frac{1}{k}\cdot n(\emptyset) =  0$. Since $F$ is the closure of $A$, it is the smallest closed set containing $A$ and thus is the smallest closed set such that $F^c$ has measure zero. So, $F$ is the support of $\mu$.

If $A = \{a_1, a_2, \dots\}$ is infinite, let $\nu(B) = \sum_{n=1}^\infty \frac{1}{2^n}\cdot \delta_{a_n}(B)$ where $\delta_n$ is the dirac-$\delta$ measure. Since the countable sum of measures is a measure, $\nu$ is a measure. Furthermore, it is finite since $\nu([0,1]) = \sum_{n=1}^\infty \frac{1}{2^n}\cdot \delta_{a_n}([0,1]) =\sum_{n=1}^\infty \frac{1}{2^n} = 1$ (because $\delta_{a_n}([0,1]) = 1$ for all $n \in \mathbb N$). Also, since $A \subset F$, $\delta_{a_n}(F^c) = 0$ for all $n \in \mathbb N$, and $\nu(F^c) = \sum_{n=1}^\infty \frac{1}{2^n}\cdot \delta_{a_n}(F^c) = 0$. Again, since $F$ is the closure of $A$, it is the smallest closed set such that $F^c$ has measure zero. So, $F$ is the support of $\nu$.

In any case, there exists a finite measure on $[0,1]$ whose support is $F$.

Your solution is not  true. Note that if $F=\{x_1,x_2\}$, with $x_1,x_2\in[0,1]$, $\mu_F({\{x_1\}^c})=\mu(\{x_2\})=0$. As $\{x_1\}$ is closed and subset of $F$, $F$ is not the support if $\mu_F$.
The solution of dannum is better.


Result of the $9^{9^9}$ So we were given a task for some bonus points to calculate and give the teacher the exact number of $9^{9^9}$. But the number is so big that I couldn't find where to calculate it to receive a precise number. I used python with a gmpy libraby to get a precise number but after almost 4 hours of running it crashed after it ran out of memory. So I am wondering is there actually a way to calculate the precise number?


Fast exponentiation algorithm - How to arrive at it? I've been learning about fast exponentiation when I found this algorithm:

int expo(int a, int b) {
  int result = 1;

  while (b) {
    if (b%2==1) {
      result *= a;
    }
    b /= 2;
    a *= a;
  }

  return result;
}

This is supposed to compute $a^b$ in logarithmic time, but I couldn't understand or find anywhere a way to arrive at this procedure, other than by noting that (this particular formula didn't help me in understanding why the algorithm is correct):

$$
x^n =
\begin{cases}
  1                                          & \text{if $n=0$} \\
  \frac{1}{x}^{-n}                           & \text{if $n<0$} \\
  x \cdot \left( x^{\frac{n-1}{2}} \right)^2 & \text{if $n$ is odd} \\
  \left( x^{\frac{n}{2}} \right)^2           & \text{if $n$ is even}
\end{cases}
$$

From what I understand, the transition from this particular identity to the actual algorithm is quite obvious, but I honestly don't get it and I've worked by hand quite a few examples for this algorithm.

Can anyone explain?

Write $b = b_0 + b_1 2 + b_2 2^2 + ... + b_n 2^n$ where $b_k$ are the binary digits of the representation of $b$ in base $2$. Note that $n$ varies logarithmically with $b$. Then:

$$
a^b = a^{b_0} \cdot (a^2)^{b_1} \cdot (a^{2^2})^{b_2} \cdot ... \cdot (a^{2^n})^{b_n}
$$

The terms where bits $b_k = 0$ evaluate to $1$ and can be skipped. The terms with $b_k = 1$ are of the form $a^{2^k}$ and can be calculated by repeatedly squaring $a$ $k$ times. This is precisely what the posted code does.

Some comments on performance which sadly were too long for a comment.

You can do bit shifts instead of division :

b >>= 1; // same effect as b/=2, but uses logic instead of expensive integer div instr.

shift all bits left one step. You may need to make sure integers are positive (unsigned int) but will def be faster than risk issuing integer "div" instructions.
If your hardware has a "find first set bit" instruction (for some reason called ffs), you can use that to get deterministic bound for your loop which will remove branchery at cost of like one pipelineable cpu cycle.
Avoid ifs in loops, may well be better to do

result *= a*(b&0x1);

replacing the if with logic and arithmetics. Multiplications are very pipelineable and branches risk breaking pipelines. Help the compiler to make the instructions as predictable as possible.


Differential Geometry review questions. Need help I have a final coming up in Differential Geometry and we got a review worksheet and I am having serious trouble with two problems. I'm still chugging along at them but I need help understanding. I know we learned the 2nd problem (#5) while I was sick last week, so I'm deep in my book trying to comprehend what i missed. Any help would be appreciated!

I have been working on 5 and I have come up with the following, which makes it seem way easier than it should be so I'm probably wrong

plug in t=0 which leads to both being (0,0). I end up using the equation cosx=F/sqrt(EG) and plugging in the values for the first fundamental form i get pi/2, which i remember reading if F=0 then all curves are orthogonal at their intersections. Am i right about any of this?

I'm stuck on 2, but i Haven't put much effort into it yet compared to 5.

The counter example I have in mind is a curve you built in two steps. Consider a smooth curve $\alpha$ defined on $[0,5]$ that satisfies $$\alpha(t)=\begin{cases} (t,0,0) & \text{for }t\in[0,1] \\(2,1+t,0) & \text{for }t\in[2,3] \\(2,3,1+t) & \text{for }t\in[4,5] \end{cases}$$
and has $\alpha([0,3])\subset\lbrace z=0\rbrace$ and $\alpha([2,5])\subset\lbrace x=2\rbrace$. Smooth curves satisfying these constraints can be constructed, one could even give explicit formulas using integrals of smooth bump functions for the parts of the curve that I have not described.

Such a regular curve (in your sense) will satisfy $(\alpha'\times\alpha'')\cdot\alpha'''\equiv0$ yet is manifestly not planar. The reason that quantity is constant equal to $0$ is that for every point $x\in[0,5]$, there is an open neighborhood $V$ of $x$ with $\alpha(V)\subset\mathcal{P}$ where $\mathcal{P}$ is one of the planes $\lbrace z=0\rbrace$ and $\lbrace x=2\rbrace$. The problem should disappear if we impose that at every point $x$ of the domain of $\alpha$, the first and second derivative $\alpha'(x)$ and $\alpha''(x)$ be linearly independent.


What is the difference between "singular value" and "eigenvalue"? I am trying to prove some statements about singular value decomposition, but I am not sure what the difference between singular value and eigenvalue is.

Is "singular value" just another name for eigenvalue?

The singular values of a $M\times N$ matrix $X$ are the square roots of the eigenvalues of the $N\times N$ matrix $X^*\,X$ (where $^*$ stands for the transpose-conjugate matrix if it has complex coefficients, or the transpose if it has real coefficients).

Thus, if $X$ is $N\times N$ real symmetric matrix with non-negative eigenvalues, then eigenvalues and singular values coincide, but it is not generally the case!

The eigenvalues $\mathbf{\Lambda}$ of the sample matrix $\mathbf{X}$ can be obtained applying SVD to the covariance of $\mathbf{X}$:

$$\mathbf{S} = cov(\mathbf{X}) \mapsto \mathbf{S}=\mathbf{U}\mathbf{\Lambda}\mathbf{V}^{T} $$


Finding solution for congruences Find the solution, if any exist, of:
$1)\quad 7x ≡ 3\pmod 9 $
$2)\quad 17x ≡ 4\pmod {36}$

1 and 2 are completely separate problems. Can anyone point me in the right direction? I don't get how to solve this.

For the first equation:

Find the inverse of $7$ modulo $9$ using Extended Euclidean algoritm, then multiply the whole equation by the inverse to get the result.

For example the inverse of $7$ modulo $9$ is $4$ (I found it by trying each number instead of the Euclidean algorithm since $9$ is small).

Then multiply $7x\equiv3(\text{mod } 9)$ by $4$ and get:

$x\equiv 3(\text{mod } 9)$

The second equation is solved the same. The application of Extended Euclidean algorithm gives $17^{-1}\equiv 17(\text{mod } 36)$ so by multiplying both terms by $17$ one gets:

$x\equiv 32(\text{mod } 36)$

This method works only if the coefficient of x is relatively prime to the modulo, which is your case $\gcd(7,9)=\gcd(17,36)=1$. If they are not prime, then more care is required when solving.

mod is just another way of saying when you divide, what is the remainder you get. For example $5mod2=1$ because when you divide you get one as a remainder. So $$3mod9\equiv3\equiv7x$$ so then you just solve for x


Inequality involving AM-GM Given  $a,\ b,\ c,\ d>0$, prove that
$$\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{d}+\frac{d^2}{a} ≥ a + b + c + d.$$
I got this question from Basics of Olympiad Inequalities, Samin Riasat, and it's supposed to use the inequality of arithmetic and geometric means (AM ≥ GM), but I can't figure how.

Could you guys please help?

Thanks in advance.

Greetings from your Brazilian fellow.

Note that this is an application of $\text{AM} \ge \text{GM}$, which  says that $$a^2+b^2 \ge 2ab$$

So we have $$a^2+b^2 \ge 2ab \iff \frac{a^2}{b} +b \ge 2a$$
From this, $$\sum_{cyc} \frac{a^2}{b}+\sum_{cyc} b=\sum_{cyc}\left(\frac{a^2}{b} +b\right) \ge \sum_{cyc} 2a =2\sum_{cyc} b\iff \sum_{cyc} \frac{a^2}{b} \ge \sum_{cyc} a$$ as desired.


Absolute Value Derivatives Let's say I have the function $f(x) = 10|x-2| - x^2 $ and I want to find the derivative. Since I can rewrite $ |x| $ as $\sqrt(x^2) $, can I also rewrite $ |x-2| $ as $ \sqrt{(x-2)^2}$ ?   (sorry for weird formatting Im new here)

Generally we introduce the sign function $\operatorname{sgn(x)}=\dfrac x{|x|}=\pm 1$ for $x\neq 0$ and $\operatorname{sgn}(0)=0$

[ The value in zero is a convention but we can also choose to let it undefined. ]

This way we can derivate $f(x)=|x-2|$

$f(x):\begin{cases}x-2 & \text{for } x\ge 2\\ 2-x & \text{for } x\le 2\end{cases}\quad$ thus $\quad f'(x):\begin{cases}+1 & \text{for } x> 2\\ -1 & \text{for } x< 2\end{cases}$

Or similarly $f'(x)=\operatorname{sgn}(x-2)$ for $x\neq 2$

Your remark about using the square root, leads indeed to that same result:

$f(x)=|x-2|=\sqrt{(x-2)^2}$

$f'(x)=\dfrac{\frac 12\times2\times(x-2)}{\sqrt{(x-2)^2}}=\dfrac{x-2}{|x-2|}=\operatorname{sgn}(x-2)\quad$ as defined above for $x\neq 2$.

[ Again, the derivative in $x=2$ does not exists, in the strict functional sense since there is a discontinuity there, it only exists as a distribution, but this is another subject. ]

Absolute Value can be viewed as finding the magnitude, or radius of a vector.
So using Pythagorean Theorem:$|x+y|=\sqrt{x^2+y^2}$ for $x+y\in \Bbb R^{2}$. Since your term is in $\Bbb R^{1}$, one of the vector components is necessarily $0$.

Letting $y=0$ and $x=u-2$:

You get $|u-2|=\sqrt{(u-2)^2}$

You can also view the Absolute Value as a piece-wise function $|x-a|=x-a$, for $x>a$ and $|x-a|=a-x$, for $x<a$.

Differentiating:$$\frac{d|x-a|}{dx}=1,x>a$$
and $$\frac{d|x-a|}{dx}=-1, x<a$$


How can I find the integers $x,y$? $$ax+by=c$$
$$ax^2+by^2=d$$
where $ab\neq 0$ and $x,y$ are coprime?

You can solve this by talking the first equation and solving for y. Then substituting y in the second equation, as so:

$$ax+by=c$$

$$ax-c=-by$$

$$(ax-c)/(-b)=y$$

Now substitute into second equation:

$$ax^{2}+\frac{b\left(ax-c\right)^{2}}{b^{2}}=d$$

Expand:

$$ax^{2}+\frac{a^{2}x^{2}-2acx+c^{2}}{b}=d$$

Simplify:

$$\frac{bax^{2}}{b}+\frac{a^{2}x^{2}-2acx+c^{2}}{b}=d$$

$$\frac{bax^{2}+a^{2}x^{2}-2acx+c^{2}}{b}=d$$

Subtract d from both sides:

$$\frac{bax^{2}+a^{2}x^{2}-2acx+c^{2}-bd}{b}=0$$

Simplify more...

$$\frac{\left(a^{2}+ba\right)}{b}x^{2}-\frac{2ac}{b}x+\frac{\left(c^{2}-bd\right)}{b}=0$$

This is just a quadratic. You can solve it with the quadratic equation:

$$x=\frac{-g+\sqrt{g^{2}-4fh}}{2f}$$

And

$$x=\frac{-g-\sqrt{g^{2}-4fh}}{2f}$$

Where $$f=\frac{\left(a^{2}+ba\right)}{b}$$

$$g=-\frac{2ac}{b}$$

$$h=\frac{\left(c^{2}-bd\right)}{b}$$

Try it out: https://www.desmos.com/calculator/dw9xe3ppxe

Above simultaneous equation shown below:

$ax^2+by^2=d$

$ax+by=c$

Taking, $(a,b,c,d)=(4,5,22,56)$ we get:

$(x,y)=(3,2)$ & $(x,y)=(17/9,26/9)$