All our relations laid bare.

Update: Thank you to Diandra for the kind words about this post!

The Internet is abuzz recently with a depressing bit of news about the state of math education in the United States: the vast majority of adults in the US do not understand what the equals sign means. For a particularly good take on this, please see the excellent article on Cocktail Party Physics. As for my part, I'd like to take this as an opportunity to expand on a point that the author, Diandra Leslie-Pelecky, made in the Cocktail Party post. Specifically, I want to elaborate on the use of the equals sign to indicate a relation.

Fundamental to mathematics is the idea of a relation, which is a formal way of stating that two objects are related in some specific way. For instance, the object "2 + 3" is related to the object "5" by the equality. This notion, however, can hide that something very important has occurred. We have taken a conceptual process, addition, and restated it in terms of a statement about static relations. No matter what I do, I cannot break the relation "2 + 3 = 5." By contrast, if I constrain myself to thinking about the addition process, then it is harder to separate that statement about Platonic ideals from the perhaps imperfect implementation of the addition process. The equality relation, then, tells us about what is.

To take a tangent for a moment, mathematics can be thought of as the process of identifying and abstracting patterns. The concept of addition, for instance, is an abstract way of discussing and modeling a very common pattern in the natural world. We need not specify whether we are adding apples or planets; the pattern is the same. Thus, taking the relational view is a natural step in this methodology of abstraction, as relations tell us about the patterns that we can identify in other patterns. We recognize that the pattern "three objects" is indistinguishable from the pattern "one object and two objects added together," and so we say that these two patterns are equal to each other. In doing so, we make no statement about which pattern precedes which in a process, meaning that we can represent the "three objects" pattern as the "1 + 2 objects" pattern should we find the latter more convenient.

Of course, processes exist, and so mathematics would be much less useful were it not able to describe them. One may well point out, for instance, that the concept of a function has a very clean intuitive description as a mathematical formalization of a process. That is, the expression "f(x)" means "take x and do f to it." Notice, however, that we ultimately rely on the idea of a relation to make sense of functions. We say things like "y = f(x)," meaning that the result of f acting upon x is related to y such that the two objects are indistinguishable. We can thus remove any notion of dynamics from our description, focusing on the pattern that our process introduces. One can even go as far as to think of a function f as a kind of relation between other objects, so that "x f y" means that the objects x and y are related by the action of f.

This shift to relational thinking is very powerful, and underlies not only much of mathematics, but also much of our language. When I say "I am Chris," there is no naming process implied, but only the statement that the concepts "I" and "Chris" are related by the verb "to be." That is, in announcing my name, I am relating the concepts of self and name. Recognizing this has been a boon to the Semantic Web, and is used to express concepts in terms of abstract relations, such as is done in Notation3. The entire concept of the World Wide Web comes back to the concept of a very special relation known as the hyperlink.

Understanding the notion of a relation can be seen to be critical to understanding the means by which we understand and model the world around us. A key part of being human is our capacity to identity patterns and relationships between objects around us, and it is precisely this capacity that we bring to bear in mathematics.

PS: This is why ":=" is often preferred over "=" for indicating "set equal to" by mathematicians.

The Power of Conversation

Today, I had a conversation with a friend of mine. One of those wonderful, roaming conversations that managed to touch both on the merits of various tabletop roleplaying game systems and on the utility of deriving quantum mechanics from quantum field theory. You know, the kinds of conversations that you can have with awesome people. Along the way, we spent a while discussing a topic near and dear to my blogging interests: science and rationality in society.

Perhaps unsurprisingly, we agreed on most of what we talked about with respect to this important topic. Looking back has gotten me thinking about the pragmatic value of keeping the rationality conversation alive, even with like-minded people. There are many reasons that often come up in such meta-discussions, of course. Conversing with others can help you to realize that you aren't alone in everything, just as Darwin fish can serve to raise consciousness about the existence of freethinkers. Such conversations can help one to hone their arguments and develop confidence in their conclusions. Through conversation, we can also expose ourselves to novel motivations and arguments, even for positions we may already take. For the emotional reasons alone, it's worthwhile to keep talking about rationality and science, to say nothing of these kinds of pragmatic benefits.

That said, there's one purpose that conversation can serve that I feel deserves special emphasis. Through conversing with other people, whether like-minded or diverse, we can learn quite a bit about when we are wrong. We are all human (I presume, anyway), and are fallible in our applications of logic. As such, it is a wonderful opportunity for self-improvement to be able to hash through our views with those honestly seeking truth. Indeed, just as science is inherently a self-correcting enterprise that must deal with the limitations of human minds, so too must rationality in general co-exist with a self-awareness of our capacity for mistakes. In conversations with others, we are often called upon to defend, explain or otherwise make explicit those private ideas which shape how we understand the world. When we are in the wrong on an issue, this process can be a tremendously helpful mechanism for self-improvement. Even with like-minded people, one's justifications can be flawed in ways discoverable through open and honest debate.

Conversation, then, is an essential tool in the rationalist's toolbox. Without healthy conversation, we are each isolated and limited to the power of our own brains. This is a large part of why I appreciate having a healthy and vibrant discussion take place on articles that I post here, such as that attached to Context Isn't Everything. By the time that you, dear readers, invest in this nascent community, I am given a precious opportunity to discover the depths of my own wrongness, as well as to find points of agreement with my intelligent, rational and compassionate peers. The rationality conversation is everywhere, and I'm glad for what parts of it find their way here, conveyed by vibrant minds.

P ≠ NP?

I don't have much to say on this one yet, but it's too important to stay silent on. Someone is claiming to have proved that P ≠ NP, which wouldn't be new but for the fact that the claimant is actually a credible computer scientist, such that Stephen Cook is saying it may be a correct proof. Since not everyone here is a complexity-head, let me spell out the significance of that: Cook was one of the people behind the Cook-Levin Theorem, which established the existence of NP-complete problems. Without Cook, then, the P vs. NP problem would be much less relevant, so his opinion on the matter should carry no small amount of weight. Of course, this is a science, so that can't be the last word-- hence the question mark in the title. It'll be interesting to see what light the morning brings to this one.

Many others have written on the issue, including: R. J. Lipton, Dave Bacon and Joe Fitzsimmons.

Deciding What Science Is

Recently, someone at a major newspaper wrote an article about science blogging that is perhaps best described as trolling. This article, penned by Virginia Heffernan, has already led to many pixels being spilt over its careless dismissal of the state of science blogging. See, for instance, PZ Myers' post on the matter wherein he dispatches her arguments quite handily. I don't wish to add to this issue, as too much has already been said about her article.

Rather, I want to address one of the more poisonous and wrong attitudes upon which her article seems to have been predicated. This attitude is far from limited to Heffernan's flamebaiting, and has been reflected in much of the writing that has followed. For instance, one blogger writing on "Christian faith, society, science and culture" had this to say:

One of my chief complaints about many science blogs is that there really isn’t much science to be found there. Many of the most popular consist primarily of diatribes about various political issues (gay marriage, immigration, the tea party, etc) and the personal religious beliefs of the blogger (who is more often than not an evangelistic New Atheist). What one will find very little discussion of science, as in information about current research, particular papers, or the state of various scientific fields. [emphasis in original]

The author, Jack Hudson, has implicitly made the same kind of error that so many face when discussion science: he has decided a priori what is and is not within the realms of what can be discussed as science. Let's take gay marriage, for instance, since Hudson seems to think that this issue has no place on a blog about science. It also serves as a very timely example to pick at, seeing as how the fate of the anti-gay marriage amendment Proposition 8 was just found to be unconstitutional in the decision Perry v. Schwarzenegger. Much of the decision came down to deciding if the law had any rational basis, and thus involved a substantive discussion of material claims made by anti-gay advocates. These claims were found to be wanting, as they were not grounded in scientific fact. Thus, we see that the final decision in the case came down to a scientific question: is gay marriage at all quantitatively different from heterosexual marriage?

Gay marriage, then, is a perfect example of something within the purview of science, as in deciding, we must apply the ideals of rationality upon which science ultimately rests. Advocating against gay marriage is simply not rational from any standpoint with which we should find acceptable in society, and so any blogger advocating for the public role of science has not only the right, but the responsibility to speak out against anti-gay actions like Prop 8. If science bloggers stick had by and large stayed out of the issue, then they would have been complicit in the further separation of science and society.

The trouble that Heffernan, Hudson and other writers run into, then, is that they don't get to set aside some issues as being outside of science. Deciding what science is and is not is not so trivial as to be settled by consulting with one's political positions. We cannot appease the Hudsons of the world by shying away from "whining about creationists," but will only further weaken how science is seen and accepted in society at large.

P. S.: I have to point out that Hudson filed his article under the "Atheist Contradictions" category, begging the question of what exactly is so contradictory here.

Test: a new way to math.

Note: If this test does not work for you in Firefox 3.5 or later, please follow use "about:config" to change "html5.enable" to true. (details)

Trying something out here, so please humor me... $x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$

Two Book Recommendations for QI/QC

Uncharacteristically, this shall be a short entry. Instead of talking about my thoughts on politics or science or anything at all, I'd like to point my readers at a wonderful book that serves as a good introduction to quantum information and computation. I don't claim to be such an expert in these fields as to be able to write a complete book's worth of introductory materials, and so my own writings will be, by comparison, incomplete. If you have an interest in these subjects, then, you will almost certainly want to find a better introduction than that which I have been working on here.

The seminal textbook of the QI/QC research community is undoubtedly Nielsen and Chuang (az, goog), due to it's incredible completeness, depth of content and clear writing. As such, I cannot help but recommend it, as it truly deserves its place as the bible of quantum computation. That said, it can be daunting to read through as a first book on the subject, and so I would also recommend Kaye, Laflamme and Mosca's excellent introductory volume (az, goog). While KLM do not delve nearly so deeply into each topic, their text does a wonderful job of making QI/QC not only concrete, but accessible.

Starting out in a field can be hard, as it is difficult to even know what a first step towards self-education might be. Thus it is that I hope that these recommendations help lower that potential barrier, even if only slightly.

Notes: There are other excellent books, I'm sure. I chose two with which I am sufficiently familiar to make a personal recommendation, but that is not to say that these two books are the only books worth considering. Also, I get a kickback on books purchased via the links to Amazon.com.

Open Source and Science: A match made in pragmatism.

Note: This is an issue I care a lot about, and so I've written about it before. This is kind of a "take two," where I hope to expand on previous writings.

I am an idealist of a peculiar kind, in that one of my highest ideals is that of pragmatism. For instance, I posit that society should not spend immense amounts of resources in efforts that evidence has shown to be futile. As I wrote about in my post on science and faith, this is one of the quintessential features of science. So much so, in fact, that one may define science as the set of those means of learning which expand human knowledge.

This pragmatic ideal is what determines much of the way that we do science. We have found that, as the sphere of human knowledge grows, it has quickly transcended the capacities of any one human brain. Thus, in order to continue to do science, we have recognized that science must be a social enterprise. This then requires that we have some means for accepting that what another scientist tells us accurately reflects reality.

It is this point at which many will claim that science must base itself on faith; specifically, faith in the goodwill and honesty not simply of our peers, but of all who came before us. Through pragmatism, however, we see that this is not the case. Rather, necessity has driven a complicated system of social protocols for communicating science by which everything is reproduced and verified such that errors due to misplaced trust are minimized. A key aspect of this social system is that science is done in the open. While truly taking seriously the ramifications of such a principle is an effort still in its earliest stages, we have long recognized that science cannot go beyond that which is communicated (put differently, science cannot exist in a vacuum). Thus, secrecy has no place in the development of scientific knowledge. In order to truly succeed in the sciences, we must wholly embrace the social and open nature of science.

Of course, science in the abstract is not the only place that we find such concerns. Consider, for instance, a computer. It was not too terribly long ago that a single person could in principle understand every aspect-- perhaps even every circuit component-- of a computer. Despite their immense physical size, computers of this age were small in the sense that they fit into the human mind. Now, however, there has been so much technological progress that it is ludicrous to think that a single person could design a modern computer from first principles. Rather, the development and manufacture of computers is a social enterprise, and not just to the extent that it overlaps with science as we have discussed it so far.

To make the discussion still more concrete, we can consider the enormity a modern operating system. The Linux kernel alone has grown from 10,000 lines of code to about 13,000,000 lines, representing far more work than any one individual can master. Such a task is undertaken with open collaboration and communication, whereby each contributor can focus on some subset of the immense whole that is the Linux kernel. This is to say nothing of all of the other parts required to make up an operating system, such as a desktop environment and low-level userspace utilities. The modern operating system must be a true community effort, if only due to the proportion of the task.

In order, then, to develop software commercially, one must create within their company a microcosm of this sort of community. Undoubtedly, this can be done, as the evidence exists in the form of closed and proprietary software. Science, however, serves in this instance to show us the value of an open flow of ideas. We spend an immense amount of effort in the sciences on facilitating communication, utilizing everything from conferences to telecommunications as tools to do so. It is, in essence, an openness born primarily of a pragmatic ideal which can be readily seen to apply in society more generally.

The story of openness, however, is far from being a constant push from academia to the rest of society. Indeed, much of the current open science movement relies on the open source movement for its inspiration. There is, in fact, a healthy community on the boundary of the open science and open source movements. This community is a wonderful example of the more general realization that pragmatism can and should drive forward the open exchange of ideas.

Resources
I would be remiss if I did not take the opportunity to share at least a few good links on the subject. In particular, I have provided below links to the work of a small sampling of the people who comprise much of my view of the open science movement.

• Michael Nielsen (blog, twitter)
• Cameron Neylon (blog, twitter)
• DJ Strouse (blog, twitter)

Context Isn't Everything, But It's Quite A Lot

Context. We can think of it as what separates us from the current generation of machine intelligences, floundering around with no memory. Context is the difference between a definition and a connotation, between an innocuous statement and a sly innuendo.

Part of being human is that we have a shared culture, which serves as a context for all that we do. Thus, a statement which is delivered with only good intentions can, in the context of culture, communicate bigotry instead. Recently, in the particular blogging circles in which I run, this effect has reared it's ugly head quite a disturbing number of times.

This most recent run seems to have been set of by a list of "sexy scientists" published with good intentions. Following this list, I saw some threads on the subject that quickly filled with controversy. One particular thread reached almost 700 comments, a good indication of the original list having struck a nerve.

Before going any further, I'd like to stop for a moment and point out something: despite not ever having named the gender of the scientists on the "sexy" list, you probably know the answer. Indeed, women were the subject of that post. In our cultural context, it is predominantly women who get the label of sexy, and so context lets you fill in that missing information. This is precisely where I think that Luke went wrong in posting the list.

Even though there is nothing inherently wrong with noticing the physical attractiveness of those around us, or even commenting on it, in the context of a society where women are unfairly disadvantaged as a consequence of their gender, Luke's list takes on a different meaning. Were women not already judged more on their physical attractiveness, then the intended celebration of beauty may not have been perverted into just another aspect of life in a patriarchal society.

Similar problems have been occurring in discussions all over the Internet, though, and so I don't want to hone in on what is, in many ways, a done deal. Just look at what happened in the comments following another of PZ Myers' posts on feminism. Here, commenters that I can only assume were well-meaning tried to point out ways in which men are hurt by sexism, but in doing so neglected the context of a discussion of male privilege. In turning a thread on male privilege into a discussion of how men suffer, these commenters perpetuated, however inadvertently, the cultural norm that men's problems are somehow more pressing then those of women. Thus, the context turns a well-meaning discussion of sexism into yet another mechanism to perpetuate sexism.

Cultural context can be a powerful thing, twisting our words and actions. By necessity, this introduces a double-standard, where the same kinds of jokes and statements that are acceptable to make about men turn poisonous when placed against a backdrop colored by sexism of the most vile kinds. Without the cultural context of religious oppression, a veil would be just another cloth. Without the context of a society in which many women live in constant fear of sexual assault, a flirtatious compliment could be seen as innocuous. Without a context of a society that fetishizes youth, a pole-dancing class for children would be just another dance class divorced from its sexual origins (after all, it's not as if ballet or tango have "innocent" origins).

If we want this to change, then we must all-- men and women alike-- be more inviting and inclusive. We must learn to not play into the problems of our culture. We must recognize that there are limits to how much we can make note of a woman's attractiveness before our message becomes one of objectification. For instance, we can't use phrases like "cry into your underwear with nerdlust" when referring to our colleagues and our peers if we want to change this poisonous cultural context.

Likewise, the men among us must be involved in the conversation in ordder for change to really set in. Here, I'll admit that the story gets much more personal for me than I'd like, so please forgive me if I spend a bit longer on this point than is really appropriate. I'm not always perfect at how I express myself, or always the best at communicating about feminism. It's hard for me, as a man, to truly understand what women go through sometime. Despite this, I do try, not out of expectation of reward, but because I feel downright compelled. It makes it hard to try, however, when speaking out means that vile accusations like this get leveled:

As I read more of your posts about this girl, I begin to see what your motivation is. You're the overprotective geek friend/wannabe lover who thinks by defending her honor on some random geek message board, you will curry favor with her and this will somehow lead to her fucking you. I'm sad to inform you this will never happen.

As long as it is so inconceivable that a man may speak up to try and improve their own community, rather than in a single-minded pursuit of sex, sexism will persist. We must all, men and women alike, understand the context in which we exist if we seek to change it so as to respect each other.

What are the complex numbers?

Now that we have ideas about states and probabilities under our belt, we're ready to build up yet another step towards understanding what a quantum state is: the complex numbers.

First, as is typical for me, I'd like to go off on a tangent. In mathematics, we often consider sets of some kind of object, such as the integers (which we write as ℤ) or the real numbers, written as ℝ. We can then add operations on these sets, such as addition and multiplication. A very useful property for a set to have with respect to an operation is that of closure, by which we mean that an operation doesn't take you outside of a set. For example, if you add any two integers, you get another integer, and so ℤ is said to be closed under addition. Similarly, ℤ is closed under multiplication and subtraction. Where it breaks down, however, is when we consider division; the specific counter-example of ⅔ shows that not all integers can be divided to produce another integer. For that, we must take a step back to the rational numbers, written ℚ. The rational numbers can be taken as the set of numbers produced by dividing integers with each other (except zero, for which we must always make an exception). One can then show by direct calculation that if you divide two rational numbers (that is, two fractions), you get another rational number, and so ℚ is closed under division.

Where, then, do numbers like come into the picture? One can prove that (that is, that there is no way of writing as a fraction), and yet the number comes up in a very natural way from looking at polynomial functions of integers, which we write as ℤ[x]. When we study such functions, we are very often interested in the roots of polynomials, since they tell us quite a lot about how such functions behave. For instance, consider f(x) = x² - 1. We can obviously factor this as f(x) = (x - 1)(x + 1), which gives us by the zero factor theorem that f(x) = 0 has two solutions at x = ±1. Notice that if we have n factors of the form (x - a), we obtain a term like xⁿ from multiplying all of the xs together, and so we should expect that a polynomial of degree n (that is, whose largest power of x is xⁿ) will have n roots. This fails if we restrict ourselves, however, to ℤ, since the function g(x) = x² - 2 has roots , which are not integers or even rationals. The solution, then, is to broaden our perspective to all real numbers, written ℝ.

This idea of including roots of polynomials is related to, but not precisely the same as, the concept of closure. It is often useful to consider sets of numbers such that all polynomials must have roots from within that set. We still, however, cannot say that ℝ has this property. Consider the polynomial x² + 1 as a counter example. Obviously, , but what does mean? As is customary in mathematics, we can generalize our notion of a square root by defining a new number i such that . We shall call this number the imaginary unit, as it has some surprising properties that we may not expect out of real numbers. The set of all complex numbers, that is, numbers that are a sum of a real and an imaginary part, such as z = a + ib, is written as ℂ. It turns out that this set does in fact include all of its polynomial roots, while still remaining closed under all the typical operations, indicating that in some sense, ℂ is large enough to encapsulate all of our typical arithmetic. Any set smaller than ℂ will not be expressive enough to capture all of the arithmetic operations we might wish to perform in our study of quantum states.

While a post on all the wondrous properties of ℂ would be far beyond my modest goal for the afternoon, one property in particular is too wonderful to go unmentioned. When we define the imaginary unit i, we also define how our typical arithmetic carries over, so that (a + ib) + (c + id) = (a + c) + i(b + d) doesn't surprise us. This does not, however, let us immediately make sense of expressions like for some real number θ. For that, we must use a mathematical tool such as power series to extend our typical definition of to include complex exponents. When we do so, we obtain a beautiful formula which serves to define what means:

Notice that this allows us to relate complex numbers to angles in a simple and straightforward way. One immediate consequence of this definition is that complex numbers tell us about rotations, whereas real numbers tell us about scales. Since , the "size" of (which we can define formally as |a + ib|² = a² + b²) is always one. This property shall be very useful to us in considering quantum mechanics and information, where we shall interpret complex rotations as a phase between two wavefunctions.

For now, though, I shall leave off this brief introduction to complex numbers, having (hopefully) demonstrated both a bit of their utility and of their beauty. Until next time!

What is a Probability?

Now that we have somewhat discussed the idea of a state, we can proceed to discuss the next building block for understanding the idea of a quantum state. As quantum states are rather intrinsically tied to the notion of a probability distribution, it is worth talking about classical probability for a few minutes. I won't try to teach all of statistics, or even necessarily the most interesting parts, so much as I will try to communicate a bit about the subset of probability theory that gets used in quantum information.

Imagine that you have a coin. If we plan on using this coin to decide something of value to us, such as the order of play in some game, then we are naturally going to be interested in whether this coin is fair. To do so, we need to understand what we mean by the word "fair" here. One way of defining fair may be to say that no one can predict the outcome of a flip of the coin in any way that is more reliable than just guessing. That is, that there is no information that an observer could have which would give them a leg up on coin prediction. This is a notion which we will return to later.

Another way to capture our intuition about fairness, which turns out to be easier to discuss at first, is to imagine that the coin is flipped a very large number of times. We would then demand that a fair coin give approximately as many "heads" as "tails," so that neither player in a coin flipping game is advantaged over the other.

We can formalize this second notion by defining the fraction p of the coin flips which come up heads and then demanding that p = 0.5. We then say that p  is the probability of obtaining a heads from our coin flip experiment. If the coin is unfair, then we can imagine p taking on any value from 0 to 1 (there can't very well be less than zero heads, nor more heads than flips of the coin). In either case, however, our notion of probability as being a proportion of experiments having a specific outcome depends on considering very large numbers of trials, such that we can mostly ignore unlikely coincidences such as five heads in a row.


Of course, we needn't restrict ourselves to coins. More generally, we can think of a source as being some device or system that produces a series of events drawn from a list of all possible events. Under this view, the fair coin was a source that produced events from the list {heads, tails}, but we can have any number (well, any number in ℕ, anyway) of possible events in such a list. Then, we will have a probability distribution function, written p(x), that tells us the fraction of experiments in which a source X produces the event x. For example, in the coin example, p = p(heads). Of course, summing this function over all possible events must give probability 1, since in all experiments, something happens. Written in symbols:

Once we have this probability distribution function, we can do some very nifty things. The primary one that I wish to talk about here is how to connect the idea of a probability distribution to the earlier intuition about uncertainty. To do this, we exploit the Shannon entropy-- I won't derive it here, but it turns out that the number of bits required to describe (on average) the outcome of an experiment with a particular source, written H(p), is given by a nice and compact formula:

Here, by lg x, we mean the base-2 logarithm of x, which can be obtained by the change of base formula lg x = log x / log 2.

A quick check with a calculator tells us that in the fair coin example, H(p) = 1, which we would expect: no observer can do better at recording coin flips than to simply write down each coin flip as it occurs, using a 0 for heads and a 1 for tails (or vice versa). Another quick check tells us that if we have an unfair coin with p(heads) = 0.9, we get H ≈ 0.46 bits/flip, meaning that someone who knows that the coin is unfair is much less uncertain of the outcome of a coin flip than someone who doesn't. This example shows a close relation between the concepts of probability, uncertainty and entropy, as we shall see more of in the future.

For now, however, I hope you enjoyed a bit of introduction to and philosophizing about probabilities!