Given a completely positive linear map E: M_n → M_n, its multiplicative domain, denoted MD(E), is an algebra defined as follows:

Roughly speaking, MD(E) is the largest subalgebra of M_n on which E behaves multiplicatively. It will be useful to make this notion precise:

Definition. Let A be a subalgebra of M_n and let π : A → M_n. Then π is said to be a *-homomorphism if π(ab) = π(a)π(b) and π(a^*) = π(a)^* for all a,b ∈ A.

Thus, MD(E) is roughly the largest subalgebra of M_n such that, when E is restricted to it, E is a *-homomorphism (I keep saying “roughly speaking” because of the “∀b ∈ M_n” in the definition of MD(E) — the definition of a *-homomorphism only requires that the multiplicativity hold ∀b ∈ A). Probably the most well-known result about the multiplicative domain is the following theorem of Choi [1,2], which shows how the multiplicative domain simplifies when E is such that E(I) = I (i.e., when E is unital):

Theorem [Choi]. Let E: M_n → M_n be a completely positive map such that E(I) = I. Then

One thing in particular that this theorem shows is that, when E(I) = I, the multiplicative domain of E only needs to be multiplicative within MD(E) (i.e., we can remove the “roughly speaking” that I spoke of earlier).

MD(E) in Quantum Error Correction

Before moving onto how MD(E) plays a role in quantum error correction, let’s consider some examples to get a better feeling for what the multiplicative domain looks like.

• If E is the identity map (that is, it is the map that takes a matrix to itself) then MD(E) = M_n, the entire matrix algebra.
• If E(a) = Diag(a) (i.e., E simply erases all of the off-diagonal entries of the matrix a), then MD(E) = {Diag(a)}, the set of diagonal matrices.

Notice that in the first example, the map E is very well-behaved (as well-behaved as a map ever could be); it preserves all of the information that is put into it. We also see that MD(E) is as large as possible. In the second example, the map E does not preserve information put into it (indeed, one nice way to think about matrices in the quantum information setting is that the diagonal matrices are “classical” and rest of the matrices are “quantum” — thus the map E(a) = Diag(a) is effectively removing all of the “quantumness” of the input data). We also see that MD(E) is tiny in this case (too small to put any quantum data into).

The above examples then hint that if the map E preserves quantum data, then MD(E) should be large enough to store some quantum information safely. This isn’t quite true, but the intuition is right, and we get the following result, which was published as Theorem 11 in this paper:

Theorem. Let E: M_n → M_n be a quantum channel (i.e., a completely positive map such that Tr(E(a)) = Tr(a) for all a ∈ M_n) such that E(I) = I. Then MD(E) = UCC(E), the algebra of unitarily-correctable codes for E.

What this means is that, when E is unital, its multiplicative domain encodes exactly the matrices that we can correct via a unitary operation. This doesn’t tell us anything about correctable codes that are not unitarily-correctable, though (i.e., matrices that can only be corrected by a more complicated correction operation). To capture these codes, we have to generalize a bit.

Generalized Multiplicative Domains

In order to generalize the multiplicative domain, we can require that the map E be multiplicative with another map π that is already a *-homomorphism, rather than require that it be multiplicative with itself. This is the main theme of this paper, which was submitted for publication this week. We define generalized multiplicative domains as follows:

Definition. Let A be a subalgebra of M_n, let E : M_n → M_n be completely positive, and let π : A → M_n be a *-homomorphism. Then the multiplicative domain of E with respect to π, denoted MD_π(E), is the algebra given by

It turns out that these generalized multiplicative domains are reasonably well-behaved and generalize the standard multiplicative domain in exactly the way that we wanted: they capture all correctable codes for arbitrary quantum channels (see Theorem 11 of the last paper I mentioned). Furthermore, there are even some characterizations of MD_π(E) analogous to the theorem of Choi above (see Theorems 5 and 7, as well as Corollary 12).

References:

1. M.-D. Choi, A Schwarz inequality for positive linear maps on C*-algebras. Illinois Journal of Mathematics, 18 (1974), 565-574.
2. V. I. Paulsen, Completely Bounded Maps and Operator Algebras, Cambridge Studies in Advanced Mathematics 78, Cambridge University Press, Cambridge, 2003.

A couple of weeks ago, I posted some intuition that suggested that, in Conway’s Game of Life, the longest-lived patterns should on average be those with density right around 37.5%. To test this hypothesis, I wrote a simple Golly Python script that generated random 20×20 patterns of varying densities and checked how long it took for them to stabilize. One noticeable problem cropped up, however: patterns with density around 90% tended to live for an extremely long time due to edge effects that caused the pattern to explode out of the original 20×20 box initially, even though they would almost entirely die off within the box.

The solution to the given problem is to emulate the Game of Life not on an infinite planar grid, but rather on a toroidal grid; that is, we fix our 20×20 universe and treat the top row as if it borders the bottom row and the left row as if it borders the right row. Running the simulation in this set-up results in data that matches our intuition more closely:

The results are based on 13592 random patterns of each density 1%, 2%, 3%, …, 99%. As with the previous graph, we notice that the lifespan plateaus in the 25% – 50% range, providing evidence that our intuition for a maximum at 37.5% is probably well-founded. Also, at the request of Elithrion in the comments on the previous post, I have included the median plot for the lifespans this time as well, though the median seems to behave pretty similarly to the average (it’s just more or less uniformly 25% smaller). As we would expect, the average lifespan in the toroidal universe set-up is much lower than the average lifespan in the infinite planar grid set-up, because expanding patterns have nowhere to go. The longest-lived pattern that was found on the torus had a lifespan of 2169 (and an initial density of 30%), whereas the longest-lived pattern that was found on the infinite plane (over significantly fewer trials, I might add) was 14042.

While I’m presenting results, how about we take a look at the final population of patterns of various starting densities?

The behaviour is almost identical to that of the average/median lifespan. The one cool thing is that, in addition to the plateau centred at ~37.5%, here we see that the median final population peaks with a value of 13 at an initial density of 38%. Nevermind the fact that this is almost certainly a statistical anomaly — it helps support my original hypothesis, and if the popular news media has taught me anything, it’s that randomly picking out things like that and claiming that they are significant is always mathematically sound.

Downloads:

• Lifespan and final population raw data [.zip of an Excel spreadsheet — 2.99MB]
• Torus lifespan script [.zip of a Golly Python script]

UPDATE [April 17, 2015]: The Online Life-Like CA Soup Search has been offline for some time now (due to being written in ASP, and me now only running websites on Linux hosts, which means I would have to re-code it entirely in PHP). However, I am happy to announce that Adam P. Goucher has recently released a new distributed soup search script called Catagolue. Not only is this script much faster than mine, but it also has many other improvements, such as being (much) better at distinguishing different objects that are near each other, and being more cryptographically secure.

See this forum thread for the announcement as well as some discussion of discoveries made by the search so far.

Today I’m “officially” announcing the Online Life-Like CA Soup Search, though some of the folks over at the ConwayLife.com forums have been helping me test it out for a couple of weeks now.

As I mentioned in this post, one way to learn about the general behaviour of Conway’s Game of Life (or any other Life-like cellular automaton) is to generate random patterns and see what stable patterns they typically evolve into (if any). If you’ve played around with Conway’s Game of Life, then you more than likely are very familiar with blocks, blinkers, beehives, loaves, and maybe even pulsars, simply as a result of drawing random gibberish on the grid and letting it evolve. This is exactly the idea behind the Online Life-Like CA Soup Search, just on a larger scale — what if we had lots of people’s computers drawing random gibberish on Life grids, letting them evolve, and storing the resulting patterns in a communal database?

This method of collecting patterns in Life is known as a census, and to my knowledge it has been carried out on a relatively large scale twice in the past; once by Achim Flammenkamp (results here), and once by Andrej Okrasinski (results linked in the first paragraph here). As we would expect, the block is by far the most common still life, and the blinker is by far the most common oscillator. If we scroll down a bit, we see that the pulsar is the fourth most common oscillator (which is reasonably surprising, given its size). Scrolling much past that, we get into the interesting stuff — objects that no reasonable person has ever seen from drawing random stuff and seeing what it evolves into, simply because they occur so infrequently.

So why bother doing another census if two rather large-scale censuses (censi?) have already been carried out? My reasons are threefold:

1. There has never (to my knowledge) been a census of any other Life-like cellular automata conducted. The Online Life-Like CA Soup Search is completely general in that it can conduct a census of any Life-like rule (assuming that rule is stable, of course). Censuses have already been started for five other rules, including 2×2, Day & Night, HighLife, and Move. Because some of these other rules have been studied relatively little, this is an easy way of discovering new yet fundamental patterns in them. For example, it didn’t take long for the soup search script to uncover a c/8 line puffer in the 2×2 (B36/S125) rule; the very first known pattern that exhibits infinite growth in 2×2!
   

   Line puffer in 2×2

2. Previous soup searches were limited in that they only looked for very specific types of objects — usually still lifes and oscillators (though Achim Flammenkamp did a search for spaceships and puffers that can be viewed here). The Online Life-Like CA Soup Search searches for still lifes, oscillators, spaceships and puffers all at once, and even gets pseudo objects (such as the bi-block) as well.
3. Multiple users can run the script and contribute to the results simultaneously. Rather than just having one person run a script that they themself wrote, the Online Life-Like CA Soup Search works by having users download a script and that script uploads results to the central database. This obviously provides a huge speed-up, and allows the census to continuously improve and expand.

So what are you waiting for? Visit the Online Life-Like CA Soup Search, download the script, and put your computer’s CPU cycles to good use!

Census results in Conway’s Game of Life

This month’s Lemma of the Month comes all the way from the Summer School and Advanced Workshop on Trends and Developments in Linear Algebra in Trieste, Italy, where Professor Rajendra Bhatia presented a lecture that introduced several simple yet endlessly interesting matrix inequalities. I will briefly present the various results here without proof, though the proof of the first “stepping stone” lemma is provided in the PDF attached to the bottom of this post. The truly interested reader can find full proofs in Professor Bhatia’s notes (follow the link above) or in [1].

Recall that one of the defining properties of a matrix norm is that it satisfies the triangle inequality:

So what can we say about generalizing the backward triangle inequality to matrices? We can of course replace A by A – B in the above equation to find the following backward triangle inequality:

However, what happens if we swap the roles of the absolute value and the matrix norm on the left-hand side? That is, if we recall that |A| is the positive semidefinite part of A (i.e., the square root of A^*A), then can we say something like

It turns out that the answer to this question is heavily norm-dependent, so we will focus on the norm that gives the simplest answer: the Frobenius norm, which I will denote by ||•||₂.

Theorem [Araki-Yamagami]. Let A, B ∈ M_n. Then

Building Up to the Result

In order to prove the result, one can proceed by proving a series of simple commutant-type matrix norm inequalities, which are interesting in their own right.

Lemma. Let A, B ∈ M_n be positive semi-definite and let X ∈ M_n be arbitrary. Then

Lemma. Let A ∈ M_n be Hermitian. Then

Lemma. Let A, B ∈ M_n be Hermitian. Then

Finally, it just wouldn’t seem right to post from Italy without sharing a bit of it. Thus, I leave you with a taste of the highlight of the trip (excepting the mathematics, of course).

The colosseum as of eight hours ago

Related Links

• Lemma of the Month #2: A Backward Triangle Inequality for Matrices [pdf]

References

1. H. Araki and S. Yamagami, An inequality for the Hilbert-Schmidt norm, Commun. Math. Phys., 81 (1981) 89-98.

In Conway’s Game of Life, a simple way to learn about the general dynamics of the game are to study what happens to soup – patterns made up of a random assortment of ON and OFF cells. Two particularly interesting questions that we can ask are “What types of stable patterns arise most frequently from soup?” and “How long does soup generally last before stabilizing?” I will focus on the latter question for today’s post, as the former has become the bud of a more ambitious project that I will announce in the near future.

The question of how long soup generally lasts before stabilizing is quite vague, because there are two important considerations that we have not specified:

1. How dense should the soup be? Clearly soup with ON density of 5% will survive only a fraction as long as soup with ON density of 50%.
2. How large of a region of soup should we let evolve? Smaller regions will stabilize much more quickly than large regions, and infinite regions will likely never stabilize(?), not to mention we can’t effectively simulate an infinite field of random cells.

For #2, I will choose the region to be of size 20×20. This decision is pretty arbitrary, but part of the reason I chose such a small size is as a desire to make this script kill two birds with one stone; any particularly long-lived patterns of this size that are discovered can likely be considered methuselahs, while larger patterns can not.

For #1, we might naively expect that patterns will live longest if they have density 37.5%, since cells are born if and only if they have exactly three ON neighbours (out of a possible eight = 37.5%). To test this theory, I created a Golly script that creates regions of varying density and checks how long it takes for them to stabilize. The following graph shows the average lifespan of 20×20 patterns with densities ranging from 1% to 99%, based on 5000 generated patterns for each percentage point.

Indeed, it looks like the longest-lived density estimate of 37.5% isn’t too far off. The true maximum in this set-up might actually be slightly higher, but that is most likely caused by the same thing that is causing the hump centered at 90%: edge effects. Roughly speaking, because we are simulating a finite region of soup on an infinite grid (as opposed to on a toroidal universe), patterns of higher density will tend to expand out very quickly in their first few generations, giving them longer lifespans in general than they would have on a toroidal universe. Alas, Golly doesn’t support toroidal universes, so the toroidal lifespan results will have to wait for another day.

Update [July 8, 2009]: I have attached to the end of this post the Python script used to generate these results.

Update [July 11, 2009]: See this post, which deals with the “more ambitious project” that I mentioned.

Update [July 19, 2009]: See this post, which deals with soup longevity on a torus.

Downloads:

• Methuselah 14042 – A methuselah with lifespan 14042 found during the search [.zip of an RLE file]
• Methuselah Search Script [.zip of a Golly Python script]
• Soup Density Data [Excel spreadsheet — 26.0kB]

The Collatz conjecture (or hailstone problem or 3n+1 problem) is a problem that is so simple to state that grade-schoolers can understand it, yet has been approached from an innumerable variety of angles and has resisted mathematicians for decades now. The problem is as follows:

Pick a positive integer. If it’s even then divide it by 2. If it’s odd, multiply it by 3 and add 1. Now apply this procedure to the result. Repeat. Will you always eventually hit 1 if you continue in this way?

For example, if you start with 11 then you multiply by 3 and add 1 to get 34, divide by 2 to get 17, and continuing similarly gets you the rest of the sequence: 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Before you go trying to find a counterexample to the conjecture, know that it has been verified by computer search for all starting numbers up to 20 × 2⁵⁸ ≈ 5.764 × 10¹⁸. The way that we are going to look at this problem today is the “pretty” approach; we’re going to extend the Collatz conjecture over the complex plane and look at the fractal defined by its iteration.

Define the Collatz function f(x) as follows:

Take a moment or two to convinve yourself that if x is a positive integer, then f(x) is the next number after x in its Collatz sequence (e.g., f(11) = 34, f(34) = 17, and so on). To extend this function to the real numbers, simply recall that (-1)^x = cos(πx). In fact, this gets us an extension to the complex numbers at the same time, and after some simplification we arrive at:

Well hey, that’s a holomorphic function so it has a notion of a Julia set and we can study the fractal that its iterates induce. Indeed, we can obtain the following image pretty easily with standard fractal-generation software:

The Collatz f(z) fractal

The fractal is located on the complex plane, and the horizontal line through the middle of the image is the real line. Black regions are regions in which the orbit of that number is bounded, while other colours indicate that the orbit of that number is unbounded (notice the large region of bounded numbers around z = 0). The big “spikes” that occur along the real line are, as we would expect, located at the integers (the image above is wide enough that you can see the spikes at z = -2, -1, 1, and 2). Instead of proceeding with the Collatz function as I have defined it, I’m going to introduce a modified Collatz function g(z) as follows:

Observe that this function, like f(z), always maps natural numbers to terms that appear later in their Collatz sequence (e.g., g(11) = 17, g(17) = 13). The benefit of this function is that it has the additional property that g(1) = 1. That is, 1 is a fixed point of g(z), whereas it is part of a period-3 cycle of f(z). The fractal induced by g(z) is:

The Collatz g(z) fractal

Close-up of the g(z) fractal at z = 1

I originally moved to using g(z) instead of f(z) because the plot of the f(z) fractal from earlier indicated to me that there may be a ball of black (i.e., boundedness) of non-zero radius around each of the integers, but proving this for f(z) seemed to be quite difficult (as we would expect, since it would basically imply half of the Collatz conjecture). Somewhat strangely, even though there appear to be balls around the integers in the fractal induced by f(z), these balls vanish in the fractal induced by g(z). The image to the right is a close-up of the above fractal (the point of convergence is z = 1).

Nonetheless, the real line still seems to behave reasonably nicely under the action of g(z); it’s not difficult to prove that the fractal contains the real line segment [0,N] for some large number N that is similar in magnitude to the least M such that the conjecture is true for all n ≤ M (known to be at least 5×10¹⁸ or so, as mentioned earlier). However, many (non-natural number) points in that interval do not converge to 1.

So what now? If the Collatz conjecture is true, then z = 1 is the unique natural number fixed point of g(z), yet there seem to be points arbitrarily close to z = 1 that don’t even converge under iteration of g(z). Why are there smaller spikes between the integers in both of these fractals, and where are the spikes centered? Does the restriction of the Collatz function to the numbers at the center of those spikes have any simple interpretation? Who knows, I’ll explore some more in the future. Until then, enjoy some pretty pictures.

g(z) fractal at z = 4

g(z) fractal at z = 8

g(z) fractal at z = 16

g(z) fractal at z = -8