A Remarkable Theorem due to Mandelbrojt

Today I read a very beautiful theorem due to S. Mandelbrojt.

First of all, let me give some definitions, which can be understood by every student who have studied elementary mathematical analysis and complex analysis.

Definition 1

Let be an ascending sequence. the upper density of is

The step of is

Definition 2

The generalized Dirichlet series , with is given by

Lemma 1

If does not converge or diverge for all s, there exists such that converges absolutely if and it does not converge absolutely if .

is the abscissa of absolute convergence of .

Theorem due to S. Mendelbrojt

Let be a generalized dirichlet generating function with abscissa of absolute convergence being finite. For and there exists a continuous function with such that for all , has a singular point in the rectangle . One such function is
for .

Corollary

In particular, if and and is finite, then every point on the abscissa of absolute convergence is a singular point. So no analytic continuation of the series from right halfplane to left halfplane is possible.

Challenges for Theoretical Computer Science

http://www.research.att.com/~dsj/nsflist.html

This is a report maintained by Prof. David S. Johnson. I like the following paragraph, and the two "guesses" which I have made it bold:

Challenge: Protein Folding
[Drafted 6/9, Revised 6/22]

In one sense a protein is simply a sequence of amino acids. This is how proteins are encoded in our DNA and how they are initially constructed in our bodies. However, once this linear chain is first constructed, it automatically folds into a complicated shape (determined by the sequence in ways we do not yet fully understand), and it is the geometric properties of this shape that to a large extent determine how the protein functions.

The problem of predicting how a protein folds, given its amino acid sequence, is one of the premier problems of science. Once the 3-dimensional structure of a protein is known, it becomes possible to design drugs that inhibit or enhance a protein's activity by fitting into niches in the surface of the protein. It may also be possible to design new proteins with useful properties. But first we need algorithms both for determining the geometric structure from the sequence and, perhaps even more difficult, to determine sequences that give rise to desired structures (a problem similar in nature to the self-assembly problem listed below). We also need to understand how and which small changes in a gene's sequence can cause major changes in its 3-dimensional structure. Limited progress has been made, but the main challenges remain before us.

One particular theoretical challenge is that, in general, the problem of determining the minimum-energy folded structure for a protein is now known to be NP-hard. This suggests various interesting possibilities:

1) P = NP and Nature knows and exploits this (unlikely, but something with exciting consequences if we can figure out the algorithms Nature uses).

2) Although P does not equal NP, Nature can solve NP-hard problems efficiently using the massively parallel computation inherent in the protein folding process (also unlikely, but something with exciting consequences for biomolecular computing if true).

3) Evolution has given us proteins whose structure is sufficiently restricted so that the folding problem is easier to solve (this suggests trying to discover just what those restrictions are and why they work).

4) Proteins don't necessarily fold to their minimum-energy configurations, but instead just go to a very attractive local optimum in the energy landscape (in which case we also have important design criteria left to discover).

Finite Field

I have been away from algebra for a long time.

A finite field F of order can be represented as , where is an irreducible polynomial (in ) of degree n.

I remember that any finite fields of the same order are isomorphic. Also I remember that the multiplicative group of the field is cyclic. A few questions arise:

1) If I am given two irreducible polynomials and of degree n. Is there any quick way to explicitly find an isomorphism between the field constructed in the two ways?

2) If I am given , how can I quickly check whether x is a primitive element of the multiplicative group of the field? More generally, what property does satisfy in order to have x as a primitive element?

3) This should be an old question. How to count the number of irreducible polynomials over and with degree n?

Striking Fact Concerning Random Graph

A random walk on Internet today.

Went to the website of Prof. Joel Spencer, a professor from Dept. of Computer Science and Dept. of Mathematics in New York University.

Went to his page storing his talk slides. A quote from the slide for his talk in Tianjin in 2007:



is a graph with n vertices and random N(n) edges.

The largest component of is of order for , of order for and of order n for .

This double "jump" when c passes the value 1/2 is one of the most striking facts concerning random graphs.

Symmetric Group S5 and Alternating Group A5

An old familiar question comes into my mind: "How to prove A5 is simple?" But I forgot the answer.

I remember there is a proof in Michael Artin's book, by considering some "concrete" rotation of some polyhedron. But I thought that proof is not nice.

Tried to google the proof on web. Found the good website Groupprops. And then found the page for S5 and A5.

Yes, there is a proof by considering the conjugacy classes of A5. And by induction, one can prove that is simple for .

A question: is there an intuitive way to see that in A5, the conjugacy class containing (1 2 3 4 5) and the conjugacy class containing (1 3 5 2 4) are different?

Four Convex Hull Algorithms

Now I am taking COMP573 in HKUST. The title of the course is "Computational Geometry".

We are using the lecture notes written by Prof. David Mount, who are now visiting HKUST. One interesting fact is that the lecturer, Dr. Sunil Arya, is advised by Prof. Mount for PhD degree, while Prof. Mount is teaching an undergraduate algorithm course...

I think it is one of the few best lecture notes I have ever read.

In the lecture notes there are four algorithms to find the convex hull of a set of given points. They are Graham scan, Divide-and-Conquer Methodology, Quick Hull and Jarvis's March.

Another interesting fact I wanna mention here is that these 4 algorithms are analog (strongly or weakly) to insertiont sort, merge sort, quick sort and selection sort respectively.

Read Timothy Chan's algorithm, which combines Graham scan and Jarvis March to form a quicker output sensitive algorithm. The idea is indeed very simple; but this is real intelligence.

Links for Quantum Computing Materials

Dr. Elad Verbin visited HKUST. He told me that he usually learn a topic by some good lecture notes.

He recommended two links to materials of quantum computing and quantum complexity theory:

http://www.scottaaronson.com/democritus/ - Quantum Computing Since Democritus

http://stellar.mit.edu/S/course/6/fa08/6.896/materials.html - Quantum Complexity Theory

A Quotation from "Analytic Combinatorics"

"Analytic Combinatorics" is a book written by Prof. Philippe Flajolet and Prof. Robert Sedgewick. Prof. Flajolet is the post-doc advisor of my MPhil advisor, while Prof. Sedgewick is the PhD advisor of my MPhil advisor.

Here is a quotation in this book:

It has been written that the shortest and best way between two truths of the real domain often passes through the imaginary one.

- Jacques Hadamard