Thecmad

Wikipedia:Babel

elΜητρική γλώσσα αυτού του χρήστη είναι η ελληνική.

en-3This user can contribute with an advanced level of English.

Mathematics

$e^{i\pi \ }$This user is a mathematician.

$\sum _{k=1}^{\infty }{x^{k} \over k!}$This user loves problem solving.

Hardware

This user thinks Apple Inc. products are cool.

MacThis user contributes using a Macintosh computer.

Software

prog-4This user is an expert programmer.

C-4This user is an expert C programmer.

C++-4This user is an expert C++ programmer.

PerlThis user is just another Perl hacker.

This user can program in Python.

This user can program in Scheme.

TeXThis Wikipedian is a TeX user.

This user contributes using Vim.

Topology: an application to number theory

Statement There exist infinitely many primes in $\mathbb {Z}$.

Proof Consider the collection ${\mathcal {O}}$ of subsets of $\mathbb {Z}$ that consists of all sets of the form $\alpha \mathbb {Z} +\beta ,\;\;\alpha ,\beta \in \mathbb {Z} ,\;\;\alpha \neq 0$, as well as of any (possibly trivial) union of such sets. Then, it is trivial to see that ${\mathcal {O}}$ induces a topology on $\mathbb {Z}$. Furthermore, observe that for all such $\alpha ,\beta :\;\;\alpha \mathbb {Z} +\beta =\mathbb {Z} \setminus \bigcup _{\kappa =1}^{|\alpha |-1}\left(\alpha \mathbb {Z} +\beta +\kappa \right)$, which implies that $\alpha \mathbb {Z} +\beta$ is closed, as the complement of a union of open sets.

Suppose, for the sake of contradiction, that there were finitely many primes $\mathbb {P}$ in $\mathbb {Z}$. Then $\mathbb {Z} \setminus \{\pm 1\}=\bigcup _{p\in \mathbb {P} }p\mathbb {Z}$ would be closed, as a finite union of closed sets. However, $\{\pm 1\}\not \in {\mathcal {O}}$, so its complement is not open, a contradiction. Consequently, there exist infinitely many primes.

Counting in two ways: an application to trigonometry

Statement For any $\{a_{i}\}_{i=1}^{\infty }\subseteq [0,1]$ we have $\sum _{i=1}^{\infty }\left(a_{i}\prod _{j=1}^{i-1}(1-a_{j})\right)=1-\prod _{i=1}^{\infty }(1-a_{i})$.

Proof Consider a sequence $\{{\mathcal {C}}_{i}\}_{i=1}^{\infty }$ of unfair coins, each having probability $a_{i}$, $i=1,2,\ldots$, of turning up heads when tossed. Denote by $E$ the event that, upon sequentially tossing the coins, a head eventually turns up; this can happen in one of countably many ways: a head comes up immediately, or a tail comes up first followed by a head, or two tails come up followed by a head, and so on. For a head to first come up on the $i$-th toss, all previous tosses must have resulted in tails, which event happens with probability $a_{i}\prod _{j=1}^{i-1}(1-a_{j})$. Therefore, $P(E)=\sum _{i=1}^{\infty }\left(a_{i}\prod _{j=1}^{i-1}(1-a_{j})\right)$. We may, however, calculate $P(E)$ with another method. For $E$ not to happen, each toss must result in a tail, for $i=1,2,\ldots$. The associated probability is $P(E^{c})=\prod _{i=1}^{\infty }(1-a_{i})$. Since $P(E)=1-P(E^{c})$, the result follows.

Application This can be applied whenever we can construct a sequence whose range lies in the unit interval $[0,1]$. One particularly interesting application is obtained by setting $a_{i}=\cos ^{2}t_{i}$, for $t_{i}\in \mathbb {R} ,i=1,2,\ldots$, thus establishing the trigonometric identity $\sum _{i=1}^{\infty }\left(\cos ^{2}t_{i}\prod _{j=1}^{i-1}\sin ^{2}t_{j}\right)+\prod _{i=1}^{\infty }\sin ^{2}t_{j}=1$.

Counting in two ways: an application to number theory

Lemma If two positive integers ${\mathcal {X}},{\mathcal {Y}}$ are chosen at random, each number being equally likely to have been selected, then the probability that ${\mathcal {X}},{\mathcal {Y}}$ are coprime is ${\frac {6}{\pi ^{2}}}$

Proof Let us adopt the notion that $\mathbb {N}$ is the set of positive integers. Recalling that $(\cdot ,\cdot ):\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ denotes the greatest common divisor, we wish to show that $\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]={\frac {6}{\pi ^{2}}}$.

First, we claim that $\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=k\right]={\frac {1}{k^{2}}}\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]$, for any positive integer $k$. Indeed, it is easy to see that $\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=k\right]=\mathbb {P} \left[\left({\frac {1}{k}}{\mathcal {X}},{\frac {1}{k}}{\mathcal {Y}}\right)=1{\mbox{ and }}{\mathcal {X}},{\mathcal {Y}}\in k\mathbb {N} \right]=\mathbb {P} \left[{\mathcal {X}},{\mathcal {Y}}\in k\mathbb {N} \right]\;\mathbb {P} \left[\left({\frac {1}{k}}{\mathcal {X}},{\frac {1}{k}}{\mathcal {Y}}\right)=1\;\vert \;{\mathcal {X}},{\mathcal {Y}}\in k\mathbb {N} \right]$. If ${\mathcal {X}},{\mathcal {Y}}$, being uniformly distributed over $\mathbb {N}$, are both restricted to $k\mathbb {N}$, then ${\frac {1}{k}}{\mathcal {X}},{\frac {1}{k}}{\mathcal {Y}}$ are uniformly distributed over $\mathbb {N}$, so the right factor equals $\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]$, and thus: $\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=k\right]=\mathbb {P} \left[{\mathcal {X}},{\mathcal {Y}}\in k\mathbb {N} \right]\;\mathbb {P} \left[\left({\frac {1}{k}}{\mathcal {X}},{\frac {1}{k}}{\mathcal {Y}}\right)=1{\mbox{ and }}{\mathcal {X}},{\mathcal {Y}}\in k\mathbb {N} \right]=\mathbb {P} \left[{\mathcal {X}}\in k\mathbb {N} \right]\;\mathbb {P} \left[{\mathcal {Y}}\in k\mathbb {N} \right]\;\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]={\frac {1}{k^{2}}}\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]$, and the claim follows.

Now, observe that $1=\sum _{k=1}^{\infty }\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=k\right]=\sum _{k=1}^{\infty }{\frac {1}{k^{2}}}\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]$, so $\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]={\frac {1}{\sum _{k=1}^{\infty }{\frac {1}{k^{2}}}}}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}$, and the result follows.

Statement If $\{p_{i}\}_{i=1}^{\infty }$ denotes the sequence of primes in $\mathbb {Z}$, then $\prod _{n=1}^{\infty }{\frac {p_{n}^{2}-1}{p_{n}^{2}}}={\frac {6}{\pi ^{2}}}$

Proof Due to the lemma, it suffices to show that $\prod _{n=1}^{\infty }{\frac {p_{n}^{2}-1}{p_{n}^{2}}}=\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]$, where ${\mathcal {X}},{\mathcal {Y}}$ are random variables uniformly distributed over $\mathbb {N}$. Let us find yet another (easier) way of computing $\mathbb {P} \left[({\mathcal {X}},{\mathcal {Y}})=1\right]$. Two integers are coprime whenever they share no prime factors. Therefore, ${\mathcal {X}},{\mathcal {Y}}$ are coprime if, for every $n=1,2,\ldots$, ${\mathcal {X}},{\mathcal {Y}}$ are not both in $p_{n}\mathbb {N}$, an event whose probability is $1-{\frac {1}{p_{n}^{2}}}={\frac {p_{n}^{2}-1}{p_{n}^{2}}}$. After multiplying the expressions for $n=1,2,\ldots$, since the events are independent, the result follows.

Isometric embeddings: an application to computational geometry

Lemma Consider the map $\sigma :\mathbb {R} ^{k}\to \mathbb {R} ^{2^{k}}$ defined as $\sigma (\mathbf {x} ):=\oplus _{\mathbf {q} \in \{\pm 1\}^{k}}\langle \mathbf {x} ,\mathbf {q} \rangle$, with $\langle \cdot ,\cdot \rangle$ being the normal dot product in $\mathbb {R} ^{k}$. Then for any two $\mathbf {x} ,\mathbf {y} \in \mathbb {R} ^{k}$ we have $\Vert \mathbf {x} -\mathbf {y} \Vert _{1}=\Vert \sigma (\mathbf {x} )-\sigma (\mathbf {y} )\Vert _{\text{sup}}$

Proof Indeed, observe that

$\Vert \sigma (\mathbf {x} )-\sigma (\mathbf {y} )\Vert _{\text{sup}}=\max _{\mathbf {q} \in \{\pm 1\}^{k}}\left(\langle \mathbf {x} ,\mathbf {q} \rangle -\langle \mathbf {y} ,\mathbf {q} \rangle \right)=\max _{\mathbf {q} \in \{\pm 1\}^{k}}\langle \mathbf {x} -\mathbf {y} ,\mathbf {q} \rangle =\max _{\mathbf {q} \in \{\pm 1\}^{k}}\sum _{i=1}^{k}(x_{i}-y_{i})q_{i}\leq \sum _{i=1}^{k}\vert x_{i}-y_{i}\vert =\Vert \mathbf {x} -\mathbf {y} \Vert _{1}$

In fact, equality is achieved for $\mathbf {q} =\oplus _{i=1}^{k}{\text{sgn}}(x_{i}-y_{i})$ (in this case, we adopt the notion that ${\text{sgn}}(0)=1$), and the lemma follows.

Statement Given $N$ points $\mathbf {p} _{1},\ldots ,\mathbf {p} _{N}\in \mathbb {R} ^{k},1\leq k<\infty$, it is possible to compute the points' Manhattan diameter, $\max _{1\leq i,j\leq N}\Vert \mathbf {p} _{i}-\mathbf {p} _{j}\Vert _{1}$, in runtime that is linear in $N$; specifically, we can achieve a runtime of $\Theta (k\;2^{k}\;N)$.

Proof Let $\sigma$ and $\langle \cdot ,\cdot \rangle$ be as in the lemma. Then

$\max _{1\leq i,j\leq N}\Vert \mathbf {p} _{i}-\mathbf {p} _{j}\Vert _{1}=\max _{1\leq i,j\leq N}\Vert \sigma (\mathbf {p} _{i})-\sigma (\mathbf {p} _{j})\Vert _{\text{sup}}=\max _{1\leq i,j\leq N}\max _{\mathbf {q} \in \{\pm 1\}^{k}}\left(\langle \mathbf {p} _{i},\mathbf {q} \rangle -\langle \mathbf {p} _{j},\mathbf {q} \rangle \right)=$

$=\max _{\mathbf {q} \in \{\pm 1\}^{k}}\max _{1\leq i,j\leq N}\left(\langle \mathbf {p} _{i},\mathbf {q} \rangle -\langle \mathbf {p} _{j},\mathbf {q} \rangle \right)=\max _{\mathbf {q} \in \{\pm 1\}^{k}}\left(\max _{1\leq i\leq N}\langle \mathbf {p} _{i},\mathbf {q} \rangle -\min _{1\leq j\leq N}\langle \mathbf {p} _{j},\mathbf {q} \rangle \right)$

which is easily computed in $\Theta (k\;2^{k}\;N)$.

Uncategorized Problems

Prove that if $\mu$ is singular with respect to Lebesgue measure on $\mathbb {S} ^{1}$ and $d\mu (x+\alpha \pi )=d\mu (x)$ on $\mathbb {S} ^{1}$ for some $\alpha$ irrational, then $\mu =0$. Stanford Qualifying Exams.