Wikipedia:Babel
elΜητρική γλώσσα αυτού του χρήστη είναι η ελληνική.
en-3This user can contribute with an advanced level of English.
Mathematics
This user is a mathematician.
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

edit

Statement There exist infinitely many primes in  .

Proof Consider the collection   of subsets of   that consists of all sets of the form  , as well as of any (possibly trivial) union of such sets. Then, it is trivial to see that   induces a topology on  . Furthermore, observe that for all such  , which implies that   is closed, as the complement of a union of open sets.

Suppose, for the sake of contradiction, that there were finitely many primes   in  . Then   would be closed, as a finite union of closed sets. However,  , so its complement is not open, a contradiction. Consequently, there exist infinitely many primes.

Counting in two ways: an application to trigonometry

edit

Statement For any   we have  .

Proof Consider a sequence   of unfair coins, each having probability  ,  , of turning up heads when tossed. Denote by   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  -th toss, all previous tosses must have resulted in tails, which event happens with probability  . Therefore,  . We may, however, calculate   with another method. For   not to happen, each toss must result in a tail, for  . The associated probability is  . Since  , the result follows.

Application This can be applied whenever we can construct a sequence whose range lies in the unit interval  . One particularly interesting application is obtained by setting  , for  , thus establishing the trigonometric identity  .

Counting in two ways: an application to number theory

edit

Lemma If two positive integers   are chosen at random, each number being equally likely to have been selected, then the probability that   are coprime is  

Proof Let us adopt the notion that   is the set of positive integers. Recalling that   denotes the greatest common divisor, we wish to show that  .

First, we claim that  , for any positive integer  . Indeed, it is easy to see that  . If  , being uniformly distributed over  , are both restricted to  , then   are uniformly distributed over  , so the right factor equals  , and thus:  , and the claim follows.

Now, observe that  , so  , and the result follows.

Statement If   denotes the sequence of primes in  , then  

Proof Due to the lemma, it suffices to show that  , where   are random variables uniformly distributed over  . Let us find yet another (easier) way of computing  . Two integers are coprime whenever they share no prime factors. Therefore,   are coprime if, for every  ,   are not both in  , an event whose probability is  . After multiplying the expressions for  , since the events are independent, the result follows.

Isometric embeddings: an application to computational geometry

edit

Lemma Consider the map   defined as  , with   being the normal dot product in  . Then for any two   we have  

Proof Indeed, observe that

 

In fact, equality is achieved for   (in this case, we adopt the notion that  ), and the lemma follows.


Statement Given   points  , it is possible to compute the points' Manhattan diameter,  , in runtime that is linear in  ; specifically, we can achieve a runtime of  .

Proof Let   and   be as in the lemma. Then

 

 

which is easily computed in  .


Uncategorized Problems

edit

Prove that if   is singular with respect to Lebesgue measure on   and   on   for some   irrational, then  . Stanford Qualifying Exams.