Math

Universality, primes and space communication

So, in mathematics we have the concept of universality in which we have laws like the law of large numbers, the Benford’s law (that I cited a lot in previous posts), the central limit theorem and many other laws that acts like laws of physics for the world of mathematics. These laws are not our inventions, I mean, the concepts are our inventions but the laws per se are universal, they are true no matter where you are on the earth or if you live far away on the universe. And that is why Frank Drake, one of the founders of SETI and also one of the pioneers in search for extraterrestrial intelligence came with this brilliant idea of using prime numbers (another example of universality) to communicate with distant worlds. The idea that Frank Drake had was the use of prime numbers to hide (not actually hide, but to make self evident, you’ll understand later) the dimension of a transmitted image in the image size itself.

So, imagine you are receiving a message that is a sequence of dashes and dots like “—.-.—.-.——–…-.—” that repeats after a short pause and then again and again. Let’s suppose that this message has the size of 1679 symbols. So you begin analyzing the number, which is in fact a semiprime number (the same used in cryptography, a number that is a product of two prime numbers) that can be factored in prime factors as 23*73=1679, and this is the only way to factor it in prime factors (actually all numbers have only a single set of prime factors that are unique, see Fundamental theorem of arithmetic). So, since there are only two prime factors, you will try to reshape the signal in a 2D image and this image can have the dimension of 23×73 or 73×23, when you arrange the image in one of these dimensions you’ll see that the image makes sense and the other will be just a random and strange sequence. By using prime numbers (or semiprimes) you just used the total image size to define the only two possible ways of arranging the image dimension.

Arecibo Radio Telescope

This idea was actually used in reality in 1974 by the Arecibo radio telescope when a message was broadcast in frequency modulation (FM) aiming the M13 globular star cluster at 25.000 light-years away:

M13 Globular Star Cluster

This message had the size (surprise) of 1679 binary digits and carried a lot of information of your world like: a graphical representation of an human, numbers from 1 to 10, a graphical representation of the Arecibo radio telescope, etc.

The message decoded as 23 rows and 73 columns is this:

Arecibo Message Shifted (Source: Wikipedia)

As you can see, the message looks a lot nonsensical, but when it is decoded as an image with 73 rows and 23 columns, it will show its real significance:

Arecibo Message with the correct dimension (Source: Wikipedia)

Amazing, don’t you think ? I hope you liked it !

- Christian S. Perone

 

The bad good news for optimization

A new published paper called “NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems” brings light (or darkness) into a 20 years-old problem related to the whether or not does exist a polynomial time algorithm that can decide if a multivariate polynomial is globally convex. The answer is: NO.

Convex vs Non Convex Functions

Convex (top) vs Non Convex (bottom) Functions (Source: MIT News)

From the news article:

For complex functions, finding global minima can be very hard. But it’s a lot easier if you know in advance that the function is convex, meaning that the graph of the function slopes everywhere toward the minimum. Convexity is such a useful property that, in 1992, when a major conference on optimization selected the seven most important outstanding problems in the field, one of them was whether the convexity of an arbitrary polynomial function could be efficiently determined.

Almost 20 years later, researchers in MIT’s Laboratory for Information and Decision Systems have finally answered that question. Unfortunately, the answer, which they reported in May with one paper at the Society for Industrial and Applied Mathematics (SIAM) Conference on Optimization, is no. For an arbitrary polynomial function — that is, a function in which variables are raised to integral exponents, such as 13x4 + 7xy2 + yz — determining whether it’s convex is what’s called NP-hard. That means that the most powerful computers in the world couldn’t provide an answer in a reasonable amount of time.

At the same conference, however, MIT Professor of Electrical Engineering and Computer Science Pablo Parrilo and his graduate student Amir Ali Ahmadi, two of the first paper’s four authors, showed that in many cases, a property that can be determined efficiently, known as sum-of-squares convexity, is a viable substitute for convexity. Moreover, they provide an algorithm for determining whether an arbitrary function has that property.

Read the full news article here, or the paper here.

Riemann Zeta function visualizations with Python

While playing with mpmpath and it’s Riemann Zeta function evaluator, I came upon those interesting animated plottings using Matplotlib (the source code is in the end of the post).

Riemann zeta function is an analytic function and is defined over the complex plane with one complex variable denoted as “s“. Riemann zeta is very important to mathematics due it’s deep relation with primes; the zeta function is given by:

\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s} = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \cdots

for Re(s) > 1.

So, let \zeta(s)=v where s = a + b\imath and v = u + k\imath.

The first plot uses the triplet (x,y,z) coordinates to plot a 3D space where each component is given by:

  • x = Re(v) (or x = u, previously defined);
  • y = Im(v) (or y = k, previously defined);
  • z = Im(s) (or z = b, previously defined);
  • The time component used in the animation is called \theta and it’s given by \theta = Re(s) or simply \theta = a.

To plot the animation I’ve used the follow intervals:

  • For Re(s): from \left[0.01, 10.0\right), this were calculated at every 0.01 step – shown in the plot at top right;
  • For Im(s): from \left[0.1, 200.0\right), calculated at every 0.1 step – shown as the z axis.

This plot were done using a fixed interval (no auto scale) for the (x,y,z) coordinates. Where Re(s) = 1/2 (\theta = 1/2) is when the non-trivial zeroes of Riemann Zeta function lies.

Now see the same plot but this time using auto scale (automatically resized x,y coordinates):

Note the (x,y) auto scaling.

See now from another plotting using a 2D space where each component is given by:

  • x = Im(s) (or x = b, previously defined);
  • y = Im(v) (blue) and Re(v) (green);
  • The time component used in the animation is called \theta and it’s given by \theta = Re(s) or simply \theta = a.

To plot the animation I’ve used the follow intervals:

  • For Re(s): from \left[0.01,  10.0\right), this were calculated at every 0.01 step – shown in title of the plot at top;
  • For Im(s): from \left[0.1, 50.0\right), calculated at every 0.1 step – shown as the x axis.

This plot were done using a fixed interval (no auto scale) for the (x,y) coordinates. Where Re(s) = 1/2 (\theta = 1/2) is when the non-trivial zeroes of Riemann Zeta function lies. The first 10 non-trivial zeroes from Riemann Zeta function is shown as a red dot, when the two series, the Im(v) and Re(v) cross each other on the red dot at the critical line (Re(s) = 1/2) is where lies the zeroes of the Zeta Function, note how the real and imaginary part turns away from each other as the Re(s) increases.

Now see the same plot but this time using auto scale (automatically resized y coordinate):

If you are interested in more visualizations of Riemann Zeta function, you’ll like the well-done paper from J. Arias-de-Reyna called “X-Ray of Riemann zeta-function“.

I always liked the way visualization affects the understanding of math functions. Anscombe’s quartet is a clear example of how important visualization is.

The source-code used to create the plot are available here:

Source code for the 2D plots

Source code for the 3D plots

I hope you liked the post ! To make the plots and videos I’ve used matplotlib, mpmath and MEncoder.

- Christian S. Perone