June 26, 2005

Math Links

[Math_] Links to websites with interesting math problems.

www.cut-the-knot.org
Interactive math miscellany and puzzles. Definitely the best.

rec.puzzles
The rec.puzzles newsgroup has an archive and an FAQ page
which contain a wealth of information about many interesting problems.

sci.math
This is the FAQ page for the sci.math newsgroup which
is another place you can search for answers.

Shack's math problems
This is a similar page that contains
interesting math problems.

IMO
This is the
Canadian site for International Mathematical Olympiad which is a
yearly competition for high school students.

Chance
This is a course developed at Dartmouth aiming to make students more informed, critical readers of current news stories that use probability and statistics.


Geopuzzles
This is a database of geometry problems.

Heard on the Street
This is a collection of questions asked in Wall Street job interviews.



Full post...

Unsolved Problems

These are the 24 problems from the wonderful book "Old and new unsolved problems in plane geometry and number theory" by Victor Klee and Stan Wagon, MAA, 1991. Some problems are too cryptic to understand without the book. I'll type more explanations some day...

Plane Geometry

  • Is each reflecting polygonal region illuminable?
    (Imagine a room in a 2-D universe. If the walls form a polygonal shape
    and they reflect light, can you always illuminate the whole room with
    a single light source?)
  • A point P inside a closed convex curve C is called equichordal if every chord of C drawn through point P has the same length. Is there a curve with two equichordal points?
    (Marek Rychlik kindly informed me of his solution to this problem.  His homepage has references for the published work.)
  • When congruent disks are pushed closer together, can the area of their union increase?
  • If a convex body C contains a translate of each plane set of unit diameter, how small can C's area be?
  • What is the smallest number f(n) such that any set of f(n) points (non-collinear) always contains the vertices of some convex n-gon?
  • If n points are not collinear, must one of them lie on at least n/3 connecting lines?
  • Is there a polygon that tiles the plane but cannot do so periodically?
  • What is the minimum number of colors for painting the plane so that no two points at unit distance receive the same color?
  • Can a circle be decomposed into finitely many sets that can be rearranged to form a square?
  • Does the plane contain a dense rational set?
  • Does every simple closed curve in the plane contain all four vertices of some square?
  • Does each nonseparating plane continuum have the fixed-point property?

    Number Theory

  • Do there exist positive integers x, y, and z and an integer n>=3 such that x^n + y^n = z^n?
    (Too late for this one :^) Wiles got it in 1993.  Check out http://www.best.com/~cgd/home/flt/flt01.htm for the proof.
  • Does there exist a box with integer sides such that the three face diagonals and the main diagonal all have integer lengths?
  • Does the greedy algorithm always succeed in expressing a fraction with odd denominator as a sum of unit fractions with odd denominator?
  • Is there an odd perfect number? Are there infinitely many even perfect numbers?
    (A perfect number is one whose factors add up to itself, e.g. 6, 28)
  • Do the nontrivial zeros of the Riemann zeta function all have real part 1/2?
  • Is there a polynomial-time algorithm for obtaining a number's prime factorization?
  • Is every positive integer eventually taken to the value 1 by the 3n+1 function?
    (3n+1 function is defined as f(n) = n/2 (if n even); 3n+1 (if n odd))

  • Is there an algorithm to decide whether a polynomial with integer coefficients has a rational root?

    Interesting Real Numbers

  • Are the digits in the decimal expansion of pi devoid of any pattern?
  • Are pi and e algebraically independent? Is their ratio rational?
  • If an irrational number is real-time computable, is it necessarily transcendental? Is sqrt(2) real-time computable?
    (A number is real-time computable if the amount of time spent computing its digits is linear in the number of digits.)
  • Is 1 + 1/2^5 + 1/3^5 + ... irrational?


  • Full post... Related link

    Mycoplasma genitalium

    [Biology_] I was searching the net for any microarray data for mycoplasma genitalium. I found anything but... Here is a list of some useful links.

    Cell Cycle Regulated Yeast Genes Spellman's yeast microarray paper and data.

    SMD : Microarray Resources : Databases

    EBI Databases - ArrayExpress Home Ebi microarray data. Contains some yeast.

    ExpressDB Database of E.coli and yeast microarray data.

    microarray data List of microarray data sources.

    Expasy 191 out of 486 swiss-prot matches to M.G. are "hypothetical" proteins, i.e. we don't have a clue what they are doing...

    PDB Query Result Only three M.G. proteins are found in PDB.

    Swiss-Prot taxonomic query: Mycoplasma genitalium List of all genes in M.G. with descriptions. Only can get the first 100 for some reason...

    the Gene Ontology website: Tries to organize gene functions.

    2can Bioinformatics Educational Resource: Home Page great site that includes bioinformatics tutorials and a section on protein function.

    Proteomics - Transcription Factors: some info on protein function

    Saccharomyces cerevisiae

    Genome Browser Need to figure out how to use this.

    Genome Sizes:
    E. coli 4,639,221 4,377 4,290 of these genes encode proteins; the rest RNAs
    Mycoplasma genitalium 580,073 483 three of the smallest true organisms
    Ureaplasma urealyticum 751,719 652
    Mycoplasma pneumoniae 816,394 680
    Saccharomyces cerevisiae 12,495,682 5,770 Budding yeast. A eukaryote.

    Mycoplasma genitalium Background

    Entrez PubMed: " The minimal gene complement of Mycoplasma genitalium.

    Fraser CM, Gocayne JD, White O, Adams MD, Clayton RA, Fleischmann RD, Bult CJ, Kerlavage AR, Sutton G, Kelley JM, et al.

    Institute for Genomic Research, Rockville, MD 20850, USA.

    The complete nucleotide sequence (580,070 base pairs) of the Mycoplasma genitalium genome, the smallest known genome of any free-living organism, has been determined by whole-genome random sequencing and assembly. A total of only 470 predicted coding regions were identified that include genes required for DNA replication, transcription and translation, DNA repair, cellular transport, and energy metabolism. Comparison of this genome to that of Haemophilus influenzae suggests that differences in genome content are reflected as profound differences in physiology and metabolic capacity between these two organisms.

    PMID: 7569993 [PubMed - indexed for MEDLINE]

    "
    Mycoplasma genitalium G-37 Information TIGR did the sequencing of MG, this is its homepage.

    Bacteria
    The DNA sequences of the complete genomes of seven mycoplasmas have been determined, including

    * Mycoplasma genitalium has 580,073 base pairs of DNA encoding 517 genes (480 for proteins; the rest for RNAs).
    * Mycoplasma urealyticum has 751,719 base pairs of DNA encoding 651 genes (613 for proteins; 39 for RNAs).
    * Mycoplasma pneumoniae has 816,394 base pairs of DNA encoding 679 genes.

    How many genes does it take to make an organism?
    The scientists at The Institute for Genomic Research (TIGR) who determined the Mycoplasma genitalium sequence followed this work by systematically destroying its genes (by mutating them with insertions) to see which ones are essential to life and which are dispensable. Of the 480 protein-encoding genes, they conclude that only 265–350 of them are essential to life.

    Genome Sizes Here is a page that has the sizes of the smallest genomes.

    NCBI HomePage The site that I found the complete genome of mycoplasma genitalium.


    Full post...

    June 16, 2005

    Analysis cheat sheet

    [Math_] Notes on analysis... --DRAFT--

    • Function spaces
    • Metric spaces
    • Convergence
    • Measure
    • Lebesgue measure
    • Lebesgue integral
    • Riemann integral
    • Lebesgue-Stieltjes integral

    • Dense subsets
    • Separable spaces
    • Complete metric spaces
    • Compact metric spaces
    • Compactness and continuity
    • Linear spaces
    • Linear functionals
    • Norms and semi-norms of linear spaces
    • Convergence revisited
    • Euclidean spaces
    • Orthogonality and bases
    • Hilbert spaces
    • Delta functions
    • Fourier transform
    • Functional derivatives
    • Expectations
    • Law of large numbers


    Full post...

    The Way of Analysis

    [Books_ Math_] I have been looking for a self-study book for Analysis for a while. All the books I have looked at more or less cover the same content. They all define "compact sets" for example. However I hadn't found one that gives any motivation for why such a weird thing should be defined. Mathematicians typically do not dream up unintuitive definitions just to annoy future students. There is a problem and a historical context that makes the definition necessary. I am sure these things are intuitively obvious to the authors but for those of us not lucky enough to have had a math undergrad degree, the lack of necessary background information in textbooks is a problem. I like "The Way of Analysis" because it is the only book I have seen that tries to motivate all its definitions. Best to illustrate with some examples:

    On "Open Sets and Closed Sets" (pp. 86):

    "It may seem a trifling matter whether or not the endpoints are included in the interval, but it makes a significant difference for certain questions. In the open interval, every point is surrounded by a sea of other points. This is the qualitative feature we will want when we define the notion of open sets; it is certainly not true of the endpoints of the closed interval. On the other hand, an open interval (a, b) seems to be "missing" its endpoints. Although they are not points in the interval, they can be approached arbitrarily closely from within the interval. It is as if they had been unfairly omitted. The closed interval has all the points it should from this point of view, and this is the closed aspect that we will generalize when we define a closed set."

    On "Compact Sets" (pp. 99)

    "Infinite sets are more difficult to deal with than finite sets because of the large number of points they contain. Nevertheless, there is a class of infinite sets, called compact sets, that behave in certain limited ways very much like finite sets... In what way can an infinite set behave like a finite set? Consider the infinite pigeon-hole principle: if an infinite number of letters arrive addressed to a finite number of people, then at least one person must receive an infinite number of letters. In more conventional terms, if x1, x2, ... is an infinite sequence of real numbers, and each xj belongs to a finite set A then at least one element of A must be equal to xj for an infinite number of j's. (my note: the sequence contains only a finite number of distinct numbers, so at least one of these numbers must repeat infinite times). Now, if A were an infinite set, this statement is obviously false. However, we could hope for a slightly weaker conclusion: that A contains a limit-point of the sequence. (my note: for any infinite sequence of real numbers x1, x2, ... made up of elements from A, at least one element of A must be arbitrarily close to an infinite number of xj's) ... Let us take this property as the definition of compactness."

    Compare this with the usual definition given for compactness: "A topological space T is said to be compact if every open cover of T has a finite subcover." (from Kolmogorov's Introductory Real Analysis).

    Note: In Prime Obsession John Derbyshire defines Analysis simply as "the study of limits". I am ashamed to admit that this was news to me after winning a bronze medal at IMO and spending 12 years at MIT. Thus Prime Obsession is also highly recommended if you need some light reading which won't strain your brain and give you some insight into how mathematicians think.


    Full post... Related link

    June 03, 2005

    Amino-acid classification terminology

    [Biology_] Meanings of some biochemical terms used to classify amino acids.

    Aliphatic - carbon only chain
    ala, val, ile, leu, pro?, gly?
    Aromatic - carbon ring
    phe, tyr, trp
    Hydroxyl - carbon chain ends with OH
    ser, thr, tyr?
    Amide - carbon chain ends with NH2
    asn, gln
    Basic - carbon chain ends with NHx+
    lys, arg, his?
    Acidic - carbon chain ends with O-
    asp, glu
    Sulphur - carbon chain ends with S
    cys, met


    Full post... Related link

    Bijective Representations of Trees Using Cons Pairs

    [Hacking_ Math_] --DRAFT-- Different ways of representing trees with list structure: We need to distinguish two things: the branching factor of the tree (binary vs variable), and whether internal nodes have any content. We are interested in one-to-one and onto (bijective) representations, any arbitrary list structure should correspond to a unique tree and vice versa.

    1. Binary tree, no internal content: trivial representation with the cons pairs. A tree is a pair of two elements. An element is either an atom or another tree.
    2. Variable branch, no internal content: simple representation given in the 6.001 tree lecture. A tree is a list of children. A list is a null terminated chain of cons pairs. A child is either an atom or another tree.
    3. Binary tree, internal content: typical C representation would use a struct of three elements: left, right, and content. One possibility with cons pairs is to define a node as two pairs: (cons content (cons left right)). (is this bijective?)
    4. Variable branch, internal content: SGF defines a format based on DFS walking (pre-order?) of the tree. Here is an EBNF definition:

    GameTree = "(" Sequence { GameTree } ")"
    Sequence = Node { Node }
    Node = ";" { Property }

    {...} represents 0 or more repetition. So a tree is a list of nodes followed by a list of trees. Each node is an atom.

    A 1-branch tree gives simply a linked list. In terms of cons pairs: there are two types of pairs: node pairs have atom cars and tree pairs have pair cars. The car of a node pair is its content, the cdr may point to any type of pair or nil. The car of a tree pair is a node pair and its cdr is a tree pair or nil. There are never two open parens in a row so this is obviously not bijective.


    Full post... Related link