Why was the universe in an extraordinarily low-entropy state right after the big bang? Let me start by saying that I have no scientific background whatsoever. I am very interested in science though and I'm currently enjoying Brian Greene's The Fabric of the Cosmos. I'm at chapter 7 and so far I understand most of general ideas he has talked about. Or at least, I think I understand them :-)
There is however one part, at the end of chapter 6 that I can't grasp.
It is about entropy and the state of the universe a few minutes after the big bang.
On page 171 he says:

Our most refined theories of the origin of the universe -our most refined cosmological theories- tell us that by the time the universe was a couple of minutes old, it was filled with a nearly uniform hot gas composed of roughly 75 percent hydrogen, 23 percent helium, and small amounts of deuterium and lithium. The essential point is that this gas filling the universe had extraordinarily low entropy.

And on page 173-174:

We have now come to the place where the buck finally stops. The ultimate source of order, of low entropy, must be the big bang itself. In its earliest moments, rather than being filled with gargantuan containers of entropy such as black holes, as we would expect from probabilistic considerations, for some reason the nascent universe was filled with a hot,
  uniform, gaseous mixture of hydrogen and helium. Although this configuration has high entropy when densities are so low that we can ignore gravity, the situation is otherwise when gravity can't be ignored; then, such a uniform gas has extremely low entropy. In comparison with black holes, the diffuse, nearly uniform gas was in an extraordinarily low-entropy state.

In the first part of the chapter Brian Greene explains the concept of entropy with tossing the 693 pages of War and Peace in the air.
At first, the pages are ordered. The specific order they are in make sense and are required to recognize the pages as a readable book called War and Peace. This is low entropy. It is very highly ordered and there is no chaos.
Now, when you throw the pages in the air, let them fall and then pick them up one by one and put them on top of each other, the chances you get the exact same order as the initial state are extremely small. The chance you get another order (no matter what order, just not the one from the beginning) is extremely big. When the pages are in the wrong order, there is high entropy and a high amount of chaos. The pages are not ordered and when they are not ordered you would not notice the difference between one unordered state and another one.
However, should you swap two pages in the ordered, low entropy version, you would notice the difference.
So I understand low entropy as a highly ordered state with low chaos in which a reordering of the elements would be noticeable.
I hope I'm still correct here :-)
Now, what I don't understand is how a uniform mixture of hydrogen and helium can by highly ordered? I'd say you wouldn't notice it if some particles traded places. I'd say that a uniform mixture is actually in a state of high entropy because you wouldn't notice it if you swapped some hydrogen atoms.
Brian Greene explains this would indeed be the case when gravity plays no important role, but that things change when gravity does play a role; and in the universe right after the big bang, gravity plays a big role.
Is that because a reordering of the particles would change the effects of gravity? Or is there something else that I'm missing here?
 A: Here is the simplest explanation I have found: "Contrary to popular opinion, uniformly distributed matter is unstable in presence of gravitation and is actually the least likely state with very low entropy. Most probable high-entropy states are those where matter is all lumped together in massive objects, culminating in the creation of black holes." (https://www.physicsforums.com/threads/why-did-entropy-decrease-after-the-big-bang.573619/)
In short, having uniformly distributed matter/energy in a universe with gravity is extremely unlikely. It would be like trying to balance the tip of a sharpened pencil on the blade of a sharpened knife. It's going to fall one way or another, and it's not going to go back to that state ever again. The evenly distributed matter in the universe is going to "fall", in one direction or another, into clumps of energy (mass), and it can never go back (at least, it's extremely unlikely).
Therefore, the uniformly distributed matter in a universe with gravity is extremely low in entropy. The matter being clumped together randomly is much more likely than all matter being perfectly evenly distributed. 
If the universe ever became uniformly distributed, then entropy has reversed and the second law of thermodynamics is wrong. But it's more likely that everything in the universe is going to eventually fall into a bunch of black holes.
Entropy is poorly defined in most discussions. Entropy is not the increase in "disorder", nor is it simply the spreading out of energy. Entropy is best described as the tendency towards the most likely state (or equilibrium/resting state) of energy/matter given certain laws of physics.
TLDR - Gravity clumps things together, and doesn't let them spread evenly. With gravity, being spread evenly is difficult/rare and therefore low-entropy, and being clumped is easy/common and therefore high-entropy. The energy of the universe was spread evenly after the big bang, and therefore, with gravity, it was low entropy.
A: To say that the universe had a very low entropy just after the big bang is a bit misleading without saying what you're comparing it with.
We know (well we're pretty sure) that black holes have an entropy, and that this entropy is enormous. Have a look at http://en.wikipedia.org/wiki/Black_hole_thermodynamics for how to calculate the entropy of a black hole. If you take some region of a uniform hot gas and you compress it into a black hole then the entropy goes up enormously, so the entropy of the universe just after the big bang was much much lower as a hot gas than as a assortment of black holes. This isn't the same as saying the entropy was low in any absolute sense.
It's certainly true that the entropy of for example a given (small) mass of ice is a lot lower than the entropy of the same mass of steam, so you'd expect that if you take some mass of the early universe and allow it to condense into e.g. a planet, then the entropy should go down. Brian Greene's point is that this is only true if you ignore the fact that by concentrating the mass into a small area you are increasing the gravitational potential in that area. The increased gravitational potential makes another contribution to the entropy that you need to include when working out the total entropy.
It's entirely reasonable to ask what is the physical mechanism for gravity's contribution to the energy, but no-one knows. In both string theory and loop quantum gravity you can construct models for the entropy of a black hole and come up with the correct answer, but of course the physical origins of the entropy are different in these two cases, so which do you believe (if either)?
A: The above answers are very interesting and informative, but not all perhaps ideally suited to someone with, by their own admission, no scientific background.
Kristof, you can think of entropy as a measure of the "typicalness" of a system's arrangement, be it a pack of cards or a bottle (or universe) full of gas molecules. There are a relatively small number of "special" arrangements, such as cards ascending order, and many orders of magnitude more typical or random arrangements.
In the absence of gravity, the typical arrangement of gas after the Big Bang is a fairly uniform distribution, as it would be in a bottle in thermal equilibrium. But introduce gravity and the tables are turned - What was high entropy, or a typical distribution, suddenly becomes anything but! The reason of course is that with gravity the typical distribution is more clumpy, and in an equilibrium state comprises merely black holes.
A: I think the following definition of entropy might be enlightening in the statistical thermodynamics paragraph:
$$S=k_b\ln(\Omega)$$
$S$, the entropy, is proportional to the natural logarithm of the number of microstates, $\Omega$.
You could think of it this way: At the Big Bang there is only one microstate, since everything is a point in space and time. At some time after the Bang microstates appear. In the model you are discussing these are the number of states that  the hydrogen and helium atoms can have. The complexity of these states, and therefore the number of possible microstates, is much smaller than if the full nuclear spectrum were available, for example,  or the present extent in space time . The more phase space the more microstates are available to be counted in $\Omega$.
Now the comment you quote:

Although this configuration has high entropy when densities are so low that we can ignore gravity, the situation is otherwise when gravity can't be ignored; then, such a uniform gas has extremely low entropy. In comparison with black holes, the diffuse, nearly uniform gas was in an extraordinarily low-entropy state.

is cryptic for me. Certainly with respect to black holes a uniform gas has lower entropy, and certainly the existence of a strong gravitational field will constrain and stratify a diffuse gas, and stratification reduces the number of available microstates, so that is what I would keep from this quote.
If you keep in mind that order means less available microstates because of the constraints order introduces, and disorder more available microstates because constraints are loosened you cannot go  wrong.
A: Your specific question is about why uniform gas is a low entropy state for the universe. The reason is that you make entropy by allowing the gas to self-gravitate and compress, releasing heat to the environment in the process. The end result is a black hole where the gas is compressed maximally, and these are the maximum entropy gravitational states.
But the uniform gas comes from a nearly uniform inflaton field shaking over all space after inflation. This inflaton produces uniform denisty of matter, which then becomes uniform baryons and hydrogen. Ultimately, it is the uniformity of the energy density in the inflaton field which is responsible for the low entropy of the initial conditions, and this is linked to the dynamics of inflation.
The dynamics of inflation produce low entropy initial conditions without fine tuning. This seems like a paradox, because low entropy is fine tuning by definition, don't you need to choose a special state to have low entropy? The answer in inflation is that the state is only special in that there is a large positive cosmological constant, but it is otherwise generic, in that it is a maximum entropy state given the large cosmological constant.
The theory of inflation explains the specialness of the initial conditions completely. This was proposed by Davies in 1983, but it is rejected by cosmologists. The rest of this answer discusses arguments that support Davies' position.
deSitter space
If you consider a deSitter space with some mass density added, and you look in a causal patch (meaning what one observer can see), the mass density gives an additional curvature without (significant) pressure and turns deSitter into more like a sphere. There is a continuous deformation of deSitter space into the Einstein static universe, which is obtained by making the density of matter as large as possible.
Any matter you add reduces the horizon area of the cosmological horizon, and this is true for black holes as well. If you consider the ds-Schwartschild exact solution, for example, you can have an isolated black hole in deSitter space:
$$ \rm ds^2 = - f(r) \rm dt^2 + {\rm dr^2\over f(r) } + r^2 \rm d\Omega^2 $$
$$ f(r) = 1 - {2m\over r} - {\Lambda r^2\over 3} $$
but there are two horizons, and the causal patch is the region between the black hole and the cosmological horizon. It is easy to check that the total horizon area, cosmological plus black-hole is maximum for m=0. It is also easy to check that there is a certain value of m where the black hole radius and the cosmological radius degenerate. At this degeneration, the distance between the black hole and cosmological horizon stays constant, they do not collide except in the bad r coordinate, and the space turns into AdS_2 x S_2.
Nariai dynamics
Imagine starting near a Nariai solution with additional matter between the two horizons. These are both still black holes, neither is a cosmological horizon, as you can see by adding more matter with a uniform density, until you approach the limit of the Einstein static universe with two antipodal black holes.
This is a physical configuration of the static cosmology. So you can start with an Einstein static universe, and evolve it forward in time, you will produce black holes, and they will merge and grow.
If you take all the matter in the static universe and push it into one of the black holes, this black hole area will increase past the Nariai limit and it will become the cosmological horizon. At this point, the singularity runs away to infinity. If you push the matter into another black hole, the other black hole will be the cosmological horizon. It's up to you.
So if you start with the Einstein static universe, the black holes compete for mattter, until eventually the biggest black hole will surround all the others, and become the cosmological horizon.
The lessons are the following:


*

*Cosmological horizons are the same stuff as black hole horizons. Their other side is described by black hole complementarity, just as for black holes. It is wrong to think of the universe in a global picture.

*deSitter space is the maximum entropy configuration of a positive cosmological constant universe, everything else eventually thermalizes into deSitter space.

*The global picture of black holes is not particularly physical, because the singularity of the Nariai solution runs away to infinity in the Nariai limit. There are cases where black hole interior structure degenerates.


Inflation Produces Low Entropy Initial Conditions
The second point answers your question, because the early universe is in a deSitter phase. So given a large positive value of the cosmological constant in the early universe, the maximum entropy state is a deSitter space with a cosmological horizon of small area, and this is necessarily a low entropy initial condition for later times, during which the cosmological horizon grows.
There is no further explanation required for the low-entropy initial conditions. This is the same explanation as for all the other miracles of inflation, the killing of fluctuations, the flatness condition, the monopole problem. The whole point of inflation is to produce a theory of low entropy initial conditions, including gravity, and it does so naturally, because deSitter space is the only low entropy maximal entropy gravitational state. This answer was first given by Davies, and it is just plain correct.
This plain-as-the-nose-on-your-face idea is not accepted despite the nearly thirty years since Davies' paper. I should add that Tom Banks and Leonard Susskind both now say similar things, although I don't want to put words in their mouths.
A: The war and peace book was, of course, a very crude and very rough analogy. You can't derive any meaningful understanding from it. 
For entropy to be truly low and non-zero at the same time, you need to add a very strong pattern arrangement of things. Maybe the gas was in a shock wave, which we know the decompression must have triggered an extreme shock wave in a very well defined form, not random at all. In the book analogy, if war and peace book was written as alphabetic ordered abcdefghijklmnopurstuvwxyz through out the book and pages cut the pattern in a periodic pattern, say, each page has 261 letter , so, every 26 pages the z aligns with the page margin. That looks roughly like a shock wave. Now, if you swap pages, you notice the difference without learning English. Now, if you swap particles in the shock waves, you notice the difference.
The war and peace is an extreme example of pattern, only the author's conception makes the writing, and you have to have the mentality to know whether 2 paragraphs are swapped. The conception is a very consistent and strong pattern permeating the entire book. Lets not start with war and peace because it confuses pattern with information. For the gas to have a very strong natural world pattern, some physical conception needs to be imposed on the gas. I can think of bullet shock waves, but the shock waves needed to come from all directions uniformly to all directions uniformly, but the extreme physics of the big bang calls for even stronger pattern than bullet shock waves. It is just all together not described by Newtonian math or any math, and hence the endless research effort to probe the physics processes near the big bang.
At the near big bang, it was not just a tank of hot gas, it was the huge mass of gas undergoing a "decompression" all together, completely in sync, nearly every particle was at the same phase of transforming from some primordial thing to hydrogen. And that happened at an instant through out the trillion trillion trillion miles of space. That was the complete opposite of the image of a tank of hot gas. It was a strong beautiful pattern to be held. War and peace is an extreme beauty, but not as extreme as the big bang, which has no competition.
A: I don't think he's correct about the entropy being low in this case. If the gravity were distributed unevenly, that could be different, but with the uniform gas distribution, gravity must have been uniform as well.
I'm not even sure that we could talk about this weird world we had in the beginning of times in nowadays terms. After all, "order" is a human concept (War and Peace is readable only by humans, "objectively" the "ordered" pages are just as good as "unordered").
