Jump to content

User:Thecmad

From Wikipedia, the free encyclopedia
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.