Q: What would it be like if another planet just barely missed colliding with the Earth?

Posted on October 15, 2013 by The Physicist

Physicist: There’s a long history of big things in the solar system slamming into each other.  Recently (the last 4.5 billion years or so) there haven’t been a lot of planetary collisions, but there are still lots of “minor” collisions like the Chicxulub asteroid 65 million years ago that caused that whole kerfuffle (65,000,000 years is practically this morning compared to the age of the solar system), or comet Shoemaker Levy 9 which uglied up Jupiter back in 1994.

Jupiter after a run-in with Shoemake Levy 9. Each of those black clouds is caused by the impact of a different tiny piece of the comet, and each is bigger than Earth.

Jupiter after a run-in with Shoemaker Levy 9. Each of those black clouds on the lower right is caused by the impact of a different chunk of the same comet, and each is bigger than Earth.

So while planets slamming or nearly slamming into each other isn’t a serious concern today, it was at one time.  Of course, in solar systems where this is still a serious concern, there’s unlikely to be anything alive to do the concerning.

For the sake of this post, let’s say there’s another planet, “Htrae”, that is the same size and approximate composition of Earth (but possibly populated entirely with evil goatee-having doppelgangers with reversed names).

A direct impact, or even a glancing impact, is more or less what you might expect: you start with two planets and end with lots of hot dust.  We’re used to impacts that dent or punch through the crust of the Earth, but really big impacts treat both planets like water droplets.  Rather than crushing together like lumps of clay, Earth and Htrae would “splash” off of each other.  A direct impact of two like-masses tends to destroy them both.  A glancing, well-off-center, impact will “stir” both planets, leaving no none of the original surface on either.  A glancing impact like this is the best modern theory of the origin of the Moon.

If Htrae were to fall out of the sky, it would probably hit the Earth with a speed that’s on the same scale as Earth’s escape velocity: 11 km/s (Probably more).  The time between when Htrae appears to be about the same size as the Sun or Moon, to when it physically hits the surface, would be a couple of weeks (give or take a lot).  The time between hitting the top of the atmosphere and hitting the bottom would be a few seconds.  If you were around, you would see Htrae spanning from one horizon to the other.  A few moments before impact the collective atmospheres of both planets would glow brightly as they are suddenly compressed.  It’s more likely that in those last few seconds/moments you would be vaporized from a distance by the heat and light released by the impact, and less likely that you would be crushed.  People on the far side of Earth wouldn’t fare much better.  They’d get very little warning, and would have to suddenly deal with the ground, and everything on it, suddenly being given a kick from below big enough to go flying into space.

Generally speaking, being slapped by the ground so hard that you find yourself in deep space a few minutes later is seriously fatal.

A near miss is a lot less flashy, but you really wouldn’t want to be around for that either.  When you’re between two equal masses, you’re pulled equally by both.  You may be standing on the surface of Earth, but most of it is still a long way away (about 4,000 miles on average).  So if Htrae’s surface was within spitting distance, then you’d be about 4,000 miles from most of it as well.  Nothing on the surface of Earth has any special “Earth-gravity-solidarity”, so if you were “lucky” enough to be standing right under Htrae as it passed overhead, you’d find yourself in nearly zero gravity.

Earth and Htrae have an extremely near miss. Which way does gravity point in-between them?

Earth and Htrae have an extremely near miss. Which way does the gravity between them point?

Of course, there’s nothing special about stuff that’s on the surface either.  The surface itself would also start floating around, and the local atmosphere would certainly take the opportunity to wander off.  On a large scale this is described by the planets being well within each others’ Roche limit, which means that they literally just kinda fall apart.  It’s not just that the region between the planets is in free fall, it’s that halfway around the worlds gravity will suddenly be pointing sideways quite a bit.  So, what does a land-slide the size of a planet look like?  From a distance it’s likely to be amazing, but you’re gonna want that distance to be pretty big.

Even a near miss, with the planets never quite coming into contact, does a colossal amount of damage.  There would be a cloud of debris between and orbiting around both planets (or rather around both “roiling molten masses”) as well as long streamers of what used to be ocean, crust, and mantle extending between them as they move apart.  This has never been seen on a planetary scale, since all the things doing the impacting these days barely have their own gravity.  The highest vertical leap on a comet would be infinity (if anyone were to try).

But the news gets worse.  Unless both planets have a good reason to be really screaming past each other (maybe they were counter-orbiting or Htrae fell inward from the outer solar system or something), a near miss is usually just a preamble for a direct impact.  All of the damage and scrambling that Earth and Htrae did do each other took energy.  That energy is taken mostly from the kinetic energy, so after a near miss the average speed of the two planets would be less than it was before.  And that means that the planets often can’t escape from each other (at least not forever).  In fact, this is why Shoemaker Levy 9 impacted Jupiter a dozen times instead of all at once.  Before impacting, the comet had passed within Jupiter’s Roche limit (probably several times), been pulled into a streamer of rocks, and slowed down.

Posted in -- By the Physicist, Astronomy, Physics | 21 Comments

Q: What are “delayed choice experiments”? Can “wave function collapse” be used to send information?

Posted on October 4, 2013 by The Physicist

Physicist: There are a lot of big claims made about entanglement, but there are two carved-in-stone facts that help cut through some of the more grandiose claims.  First, (maximally) entangled states always act exactly like a perfectly random state, until you compare the two.  There’s nothing special about one half of an entangled pair of particles, but there’s a lot special about two of them together.  And second, under no circumstances does anything you do to one particle have any effect on the other.  Never.  Never ever, in fact.

Delayed choice experiments are among many attempts (generally successful) to gain a better understanding into the nature of measurements in quantum mechanics, and to ferret out the role of the “observer”.  The results so far are that “observers” and their observations only matter to the observers themselves*, wave function collapse is a mathematical artifact*, and (sadly) there’s still no way to send information faster than light.

There are a lot of experiments that can be called “delayed choice” experiments (here’s a good one!), but the idea behind delayed choice experiments is fairly straight forward.  The results of the double slit experiment are sometimes described as “if you know what slit a photon goes through, then there is no interference pattern, but if you don’t know which slit it went through, there will be an interference pattern” (details).  The fact that the double slit experiment involves slits is unimportant.  What matters is that there are two paths for photons to take, and that those paths can interfere.

The original double slit experiment (bottom) and a more modern set up (top).

The original double slit experiment (bottom) which produces many light and dark fringes and a more modern set up (top) which produces one dark path and one light path in lieu of fringes.  The squares are beam splitters.  By carefully arranging everything you can get photons to always come out of one side of the last beam splitter

First, introduce a source that produces pairs of entangled photons.  Entangled particles have the property that if the same measurement is made on both particles, then the results will always be the same (there are different kinds of entanglement, but this is the simplest to keep track of).  Generally this only applies to one property of the particles (spin, direction of movement, etc.).  In this case the entangled property is the direction, or the “which path information”.

The source of entangled photons sends them in a combination of "both up" or "both down" (top). Far away from each other, Alice and Bob each receive one of those photons, and can interfere them in very much the same way the double slit experiment does (bottom).

The source of entangled photons sends them in a combination of “both up” or “both down” (top). Far away from each other, Alice and Bob each receive one of those photons, and can interfere them in very much the same way the double slit experiment does (bottom).

So here’s the idea; two people, Alice and Bob, are each sent one of the two entangled particles (each of which arrives on two paths, like the double slit).  If Alice looks at her particle and finds out which path it’s on, then suddenly Bob’s photon will similarly only be on one path*.  But that means no interference, and Bob should be able to tell whether or not there’s interference.  In particular, he’ll start seeing photons in what should be the dark path.  “Holy crap”, he thinks, “Alice must have looked at her photon”.  There are a lot of different versions of “delayed choice” type experiments, but this is the basic idea.

But there’s a huge problem here; at no point did Alice and Bob communicate, and it doesn’t matter how far apart they are, so this is a method for faster-than-light communication.  Supposedly, Alice can send a signal to Bob  just by either looking at, or not looking at, her own photon.  However!  It turns out that exactly like every other “cheat” involving entanglement, it’s impossible to even tell that your particle is entangled with another one until you compare the two.

The following math is pretty easy, it’s just that the notation is scary.  There will be no quiz, so don’t stress.

The state of a photon taking the bottom path is “|b\rangle” and if it’s taking the top path it’s in the state “|t\rangle“.  Beam splitters take |b\rangle to H|b\rangle = \frac{1}{\sqrt{2}}\left(|b\rangle + |t\rangle\right), and take |t\rangle to H|t\rangle = \frac{1}{\sqrt{2}}\left(|b\rangle - |t\rangle\right).

So for example, two beam splitters applied one after the other to a “bottom state” is: H^2|b\rangle=H\frac{1}{\sqrt{2}}\left(|b\rangle+|t\rangle\right)=\frac{1}{\sqrt{2}}\left(H|b\rangle+H|t\rangle\right)=\frac{1}{2}\left(|b\rangle+|t\rangle+|b\rangle-|t\rangle\right)=|b\rangle.  This is exactly the situation in the top most picture!

By the way, the number in front of a state is its “probability amplitude”, and the square of that is the probability of seeing that state.  So that \frac{1}{\sqrt{2}} means that each of the states has a 1/2 chance of being seen if the photon were detected (it has a 50/50 chance of being seen on either path).

That “\frac{1}{\sqrt{2}}\left(|b\rangle+|t\rangle\right)” thing is a superposition of the top and bottom paths, which interferes at the second beam splitter.  So, hopefully, each of the entangled photons will be in that same state and will interfere similarly, with similar results.  Unfortunately, that’s not the case even a little.

The entangled photons are created in the state \frac{1}{\sqrt{2}}\left(|b\rangle_A|b\rangle_B+|t\rangle_A|t\rangle_B\right); a combination of “both up” and “both down”.  The subscripts, A or B, indicate which photon goes to which person, Alice or Bob.

What does Bob see if Alice does nothing?  The state starts as: \frac{1}{\sqrt{2}}\left(|b\rangle_A|b\rangle_B+|t\rangle_A|t\rangle_B\right).  When Bob gets his photon he interferes it in the beam splitter: \begin{array}{ll}H_B\frac{1}{\sqrt{2}}\left(|b\rangle_A|b\rangle_B+|t\rangle_A|t\rangle_B\right)\\=\frac{1}{\sqrt{2}}\left(|b\rangle_AH_B|b\rangle_B+|t\rangle_AH_B|t\rangle_B\right)\\=\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2}}|b\rangle_A(|b\rangle_B+|t\rangle_B)+\frac{1}{\sqrt{2}}|t\rangle_A(|b\rangle_B-|t\rangle_B)\right)\\=\frac{1}{2}\left(|b\rangle_A(|b\rangle_B+|t\rangle_B)+|t\rangle_A(|b\rangle_B-|t\rangle_B)\right)\\=\frac{1}{2}\left(|b\rangle_A|b\rangle_B+|b\rangle_A|t\rangle_B+|t\rangle_A|b\rangle_B-|t\rangle_A|t\rangle_B\right)\\=\frac{1}{2}\left(|b\rangle_A+|t\rangle_A\right)|b\rangle_B+\frac{1}{2}\left(|b\rangle_A-|t\rangle_A\right)|t\rangle_B\end{array}

So here’s what that mess means: there’s a 50/50 chance of the photons being in either of the states \frac{1}{\sqrt{2}}\left(|b\rangle_A+|t\rangle_A\right)|b\rangle_B or \frac{1}{\sqrt{2}}\left(|b\rangle_A-|t\rangle_A\right)|t\rangle_B.  As far as Bob is concerned, that means that there’s a 50/50 chance of detecting it on either path.  No interference.

What does Bob see if Alice looks?  Everything works the same right up until the last step, so the state is: \frac{1}{2}\left(|b\rangle_A|b\rangle_B+|b\rangle_A|t\rangle_B+|t\rangle_A|b\rangle_B-|t\rangle_A|t\rangle_B\right).  All 4 of these states are equally likely (since, \left|\frac{1}{2}\right|^2=\left|-\frac{1}{2}\right|^2=\frac{1}{4}).  If Alice looks and sees the photon on either path, then two of those four states will collapse*.  If she sees the photon in the top path, then the state of the system becomes \frac{1}{\sqrt{2}}|t\rangle_A\left(|b\rangle_B-|t\rangle_B\right) and if she see’s it on the bottom path, then the state of the system becomes \frac{1}{\sqrt{2}}|b\rangle_A\left(|b\rangle_B+|t\rangle_B\right).  In both cases, Bob has a 50/50 chance of seeing it on either path.  No interference!

That said, the states \frac{1}{\sqrt{2}}\left(|b\rangle_B+|t\rangle_B\right) and \frac{1}{\sqrt{2}}\left(|b\rangle_B-|t\rangle_B\right) are fundamentally different, it’s just that Bob won’t know which he has until Alice tells him the result of her measurement (by calling or writing or something).  This is actually the basis behind quantum teleportation!

This particular experiment doesn’t in itself prove anything, but every similar experiment has the same result: no communication.  What if Alice and Bob look at different times?  What if whether or not Alice looks is itself decided by some other quantum thing?  What if you use lots of entangled pairs, or other kinds of quantum states, or do the experiment hanging upside-down while yodeling the Beatles?  Really, think of a permutation, and some lab somewhere has tried it.  All of them have verified the Quantum No-Communication Theorem.

*Answer Gravy: The things above with an asterisk are better explained using Relational Quantum Mechanics.  The idea behind RQM is that measurements don’t do anything “special”, and quantum laws always apply (nothing fundamentally changes between the atomic and macroscopic worlds).  I’m a big fan, but please take my opinions (not the math, but the interpretation of the math) with a big grain of salt.  It’s an “interpretation” after all, not a “law”.

Before Alice looks at her photon she’ll be in the state |A(?)\rangle.  If she looks and sees the photon in the top path, then suddenly she’ll be in the state |A(t)\rangle.  That isn’t particularly profound.  When things interact they’re each affected, and in this case the effect on Alice is remembering that the photon took the top path (also maybe a commemorative lab party with top hats).  The “just go ahead and Look at the particle” operation, L, does this: L_A\left(|A(?)\rangle |t\rangle_A\right) = |A(t)\rangle |t\rangle_A.  The same idea for |b\rangle, and of course Bob can look as well.

Now, assume that Alice and Bob are somehow extremely isolated from each other.  No information of any kind can pass between them (no sound, light, particles of any kind, etc.).  This sort of isolation is almost certain to be completely infeasible for people (it’s hard enough to keep just a handful of particles Isolated).  That means that in practice, here on Earth in actual labs, when one person makes a measurement, both do.  So, are you in a superposition of both reading and not reading this post, from the point of view of someone on the opposite side of the Earth?  Very unlikely.  But never mind all that: presume Alice and Bob are Isolated.

Now say each of them have one of the entangled particles (no beam splitters or anything this time) and they haven’t looked at them.  The state they start out in is \frac{1}{\sqrt{2}}|A(?)\rangle\left(|t\rangle_A|t\rangle_B + |b\rangle_A|b\rangle_B\right)|B(?)\rangle.  Alice and Bob are both in one state, from each of their points of view.  Now say Alice looks (that means “apply L_A“).

\begin{array}{ll}L_A\frac{1}{\sqrt{2}}|A(?)\rangle\left(|t\rangle_A|t\rangle_B + |b\rangle_A|b\rangle_B\right)|B(?)\rangle\\[2mm]=L_A\frac{1}{\sqrt{2}}\left(|A(?)\rangle|t\rangle_A|t\rangle_B|B(?)\rangle + |A(?)\rangle|b\rangle_A|b\rangle_B|B(?)\rangle\right)\\[2mm]=\frac{1}{\sqrt{2}}\left(|A(t)\rangle|t\rangle_A|t\rangle_B|B(?)\rangle + |A(b)\rangle|b\rangle_A|b\rangle_B|B(?)\rangle\right)\\[2mm]=\frac{1}{\sqrt{2}}\left(|A(t)\rangle|t\rangle_A|t\rangle_B + |A(b)\rangle|b\rangle_A|b\rangle_B\right)|B(?)\rangle\end{array}

If you’re asking “does this mean that Alice is in two states at the same time, like a particle?”, the answer is yes.  And why not?  Other than being the weirdest thing ever, what’s really wrong with it?  So, from Bob’s perspective, Alice is now in a superposition of states.

But now there’s a problem.  Does it now make sense to consider Alice’s perspective?  In order to ask “what does Alice see?”, you have to consider which “version”.  The “t” version sees the world like this: |A(t)\rangle|t\rangle_A|t\rangle_B|B(?)\rangle.  Bob hasn’t look at his particle yet, but when he does he’ll see it in the top state.  From this Alice’s perspective, the state of Bob’s particle has undergone “wave function collapse” into the top state.  In exactly the same way, the version of Alice that saw her particle in the bottom state will find that Bob’s particle “collapsed” to the bottom state.  They both saw a fundamentally random result, yet immediately learn from it the state of a distant particle.

In case you’re wondering, if Bob then looks, the overall state becomes \begin{array}{ll}L_B\frac{1}{\sqrt{2}}\left(|A(t)\rangle|t\rangle_A|t\rangle_B|B(?)\rangle + |A(b)\rangle|b\rangle_A|b\rangle_B|B(?)\rangle\right)\\[2mm]=|A(t)\rangle|t\rangle_A|t\rangle_B|B(t)\rangle\\[2mm]\end{array}.  For both versions of both Alice and Bob, the whole process was random, and the only thing they’ll notice, if they ever compare notes, is that they measured the same thing.

Deeply weird, but deeply unfantastic.

Posted in -- By the Physicist, Entropy/Information, Experiments, Philosophical, Physics, Probability, Quantum Theory, Skepticism | 6 Comments

Q: Why can some creatures walk on water yet I (a human) can’t?

Posted on September 23, 2013 by The Physicist

Physicist: Surface tension.

There are a lot of details and phancy physics behind surface tension, but the main idea behind surface tension comes from what separates liquids from gases.  Small things (like individual molecules) have a tendency to stick to each other.  Electrical forces, like dipole attraction or van der waals forces, completely dominate the world of the small.  The individual molecules in a liquid are attracted to each other, and try to stay as close as possible.  In a gas the molecules have so much kinetic energy that they ricochet off of each other and fly apart.  In a liquid the attractive forces are large enough to keep that kinetic energy reeled in.

Left: atoms in liquids are like this. Right: atoms in gases are like this.

Left: atoms in liquids are like this. Right: atoms in gases are like this.

Water has surprisingly strong “inter-molecular” forces, due to it’s highly polar nature.  Each water molecule is like a bar magnet, only with positive and negative charges instead of north and south magnetic poles.

The fact that all of the atoms in a fluid are attracted to their nearest neighbors means that, for the most part, fluids “don’t like” having surfaces.  Each molecule wants to be surrounded by other molecules, so the surface literally contracts and tries to be as small as possible.  So surface tension is just the liquid trying to have the minimum possible surface area.  Water does this more than most liquids in nature.

On a small enough scale the surface tension is stronger than the water's weight.

On very small scales (insect size) surface tension is the dominating property of water. For example, if you see a water droplet sitting on a surface, then the surface tension is greater than the water’s weight.

A really good way to minimize the surface area is to be flat.  Insects that walk on water have hydrophobic oils on their feet that don’t mix with water, so the water instead has to move out of the way.  But dips aren’t flat, so creating dips means creating more surface, which the water doesn’t want to do, so it pushes back.  A water strider doesn’t float on water, it is literally supported by the stubbornness of the water’s surface.

But this doesn’t amount a lot of force.  Insects, dirt, and even paperclips can be suspended by surface tension, but not much else.  On a large scale the weight of the water, as well as the weight of critters trying to walk on it, is much greater than the surface tension is strong.

There are two ways to run on water: floating and not floating.

There are two ways to stand on water: be tiny or run fast.

There are very few largish creatures that can walk on water.  However, they don’t use surface tension, they hydroplane.  “Hydroplaning” here means pushing on the water faster than the water can move out of the way.  The best way to hydroplane is to be a paradox: a fast runner with gigantic feet.  No person has been able to pull it off, but happily those paradoxes do exist in nature and they’re ridiculous.

Posted in -- By the Physicist, Biology, Physics | 8 Comments

Q: What fair dice can be simulated by adding up other dice?

Posted on September 16, 2013 by The Physicist

The original question was: The five platonic solids (tetrahedron, cube, octahedron, dodecahedron, and icosahedron) are often used in games to make 4, 6,8,12, and 20-sided dice respectively. However, if you renumber the dice using nonnegative whole numbers you can create other pseudo-N-sided dice.

We will  call one or more platonic solid dice a “pseudo-N-sided die” if, when we roll them and find their sum they can add to all numbers 1 through N and do so with equal probability. For example:

A cube can be renumbered to be a pseudo-2-sided die.

Two cubes can be renumbered to be a pseudo-12-sided die

Two icosahedrons can be renumbered to become a pseudo-100-sided die

Using any number of platonic solid dice, what is the smallest pseudo-N-sided die you cannot make?

Physicist: A 7 sided die is the smallest that can’t be made using other relabeled dice added together.  If you’re not familiar with these games, a “d6” (“dee six”) is the completely standard, cubic die that’s labeled 1 through 6.  “2d6” means roll two of these and add them together (like craps).

You’d hope that 1d12 = 2d6, but unfortunately that isn’t the case.  Some numbers are more likely to come up (7) and some are less likely (12) and for fair dice each number should be equally likely.

If a sum of properly labeled polyhedral dice can simulate a fair die that would be labeled (1, 2, …, s), then we’ll call s a “D number”.  So  Right off the bat, labeling the regular polyhedra normally (1,2,3,…), it’s clear that 4, 6, 8, 12, and 20 are D numbers.

The five regular polyhedra: d4, d6, d8, d12, and d20.

The five regular polyhedra: d4, d6, d8, d12, and d20.

Labeling these differently, you get all of their divisors as well.  A d6 labeled (1,1,2,2,3,3) is exactly the same as a d3 (as far as generating random numbers is concerned).  So, the D numbers are D = {1 (a “doom die”), 2, 3, 4, 5, 6, 8, 10, 12, 20}.

A d12 as a d12, d6 as a d1, d6 as a d2, and a d12 as a d3.

From left to right: a d12, d1, d2, and d3.

The trick usually used for making a d100 (rather than getting one of those giant goofy ones), is to multiply one d10 by ten and add the second.  So, 1d100 = 10(1d10-1) + 1d10.

"96" as represented on two d10's. d10's exist because people want to generate numbers between 1 and 10,

“96” as represented on two d10’s. d10’s exist because people want to generate numbers between 1 and 10, but they are not regular polyhedra.  That said, this could be done with two d20’s labeled 1 to 10 twice.

Doing the same to the weirdly labeled dice you can simulate any fair d(xn), where x is any D number.  For example, the dice to get a d81 are: (0, 27, 54), (0, 9, 18), (0, 3, 6), and (1,2,3).

So that expands the list substantially (infinitely).  The D numbers now include D = {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 20, 25, 27, 32, ….}

You can also get dice of the form d(abc…) where a, b, c are D numbers.  For example, to create a d30, you could use either 1d30 = 5(1d6-1) + 1d5, or 6(1d5-1) + 1d6.  The dice you could use to get this might be (0, 5, 10, 15, 20, 25) and (1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5).  You can also get fair d30’s by cheating a little, and building a polyhedra using the same face, but two different kinds of points.

A d30, featuring both 3-edge points and 5-edge points.

A d30, or “rhombic triacontahedron”, is not a regular polyhedron because it features both 3-edge vertices and 5-edge vertices.

So, every divisor of a D number is a D number, and every product of D numbers is a D number.  Rather than listing them, it’s much easier to say: the D numbers are those that can be formed using any combination of the primes 2, 3, and 5.  Numbers like this comprise a lot of the lower numbers (9 out of the first 10), but quickly become more and more uncommon (33 out of the first 100).  Sadly, there’s no way to construct a fair die with any other prime factor.  So, there’s no d7, d11, d13, d14, d17, d21, d22, d23, d26, …  The chance that a random, very large, number is a D number is effectively zero.

It turns out that these are the only D numbers.  The reason is that, ultimately, you’re dealing with the 5 regular polyhedra, and they determine the size of the “state space”.  For example, 2d6 has 36 states (36 = 62).  No matter how cleverly the two dice are labeled, those 36 states can never be fairly divided into, say, 5 or 7 outcomes.

The state space for 2d6. All the probabilities in craps come back to this.

The state space for 2d6.  Each of the blue squares comes up with equal probability.

The same idea holds true for any number that has prime factors other than 2, 3, and 5, so none of them can be D numbers.

There are of course standard tricks to almost simulate other dice.  For example, if you needed to roll a 1d7, what you’d probably do is roll a 1d8 and declare that “8 is a re-roll” (common sense like that is poison to the exotic dice market).  In practice, the “re-roll” technique means that real dice can be used to perfectly simulate any non-D-numbered die.  For example, you can use a coin to choose between three people by flipping it two or more times:  “HH” for Alice, “HT” for Bob, “TH” for Carol, and “TT” for “go again”.

But very technically, it’s impossible to simulate a fair d7 using fair polyhedral dice (same is true for an non-D-number).  The best you can do is have seven possibilities that are all equally likely, and an eighth (or more) that is less likely.  For example, if you allow up to three rolls, then the only way to have not selected a number from 1 to 7 using 1d8 is to have rolled three 8’s in a row; a chance of 1 in 512.  If you could re-roll forever, then the chance that you’ll always roll an 8 is zero.  However, if you plan to do anything with your life (other than to accurately simulate one roll of a single d7 using a d8, while also living forever), then at some point you’ll have to stop rolling dice.  No matter how long you spend trying, there’s a tiny chance that you never stop seeing 8’s.  Therefore, a d8 can never quite simulate a d7, because there’s always a “null-result”.  That said, if you see an 8 more than 15 times in a row, then congratulations: you are now the most lucky person ever!

This has nothing to do with the question, but: In two dimensions every die is available; a square is a d4, a septagon is a d7, a tridecagon is a d13, etc.  But that’s boring.

In four dimensions the D numbers are the same, because the available dice would be a d5, a d8, a d16, a d24, a d120, and a d600.  This is more kinds of dice than can be found in any other dimension!  Four dimensions is kind of a paradise for mathematics; just enough wiggle room that surprising stuff shows up, but not so much that it’s boring.

In the same way that a giant, clear d12 will project a funky shadow

The d120.  If you put a light right above one of the faces of a giant, clear d12 you get a funky shadow on the ground.  If you do the same (analogous) thing to the d120 in four dimensional space, you get a “shadow” that looks like this.  The “faces” of the d120 are the cells contained by the edges and (weirdly enough) the exterior itself.

In X-dimensional space (X=5,6,…), the only dice are the d(X+1), the d(2X), and the d(2^X).  These are the higher-dimensional versions of the d4, d6, and d8.  So, you can have a d13, but you’d have to go to at least 12 dimensions.  In fact, if you want a die with X sides, you just need to be a nerd in (at most) an X-1 dimensional universe.

The purple dice picture is from here.

Posted in -- By the Physicist, Brain Teaser, Combinatorics, Logic, Math, Probability | 14 Comments

Q: How do I encrypt/hide/protect my email?

Posted on September 11, 2013 by The Physicist

Cryptographer: Lots of people have been asking “how do I encrypt my email” or “how can I hide from NSA surveillance”. It turns out that the answer to the first question is fairly straight forward, while the second is not, so lets look at encryption first.

The Physicist wrote about the details of cryptography here. The real magic is in the public key systems like RSA or Elliptic Curve cryptography. Before the invention of public key cryptography, you had to securely exchange secret keys with everyone with whom you might want to communicate. So any time you wanted to communicate with someone new, you had to create a new key, and then somehow get it to the other person in a way that you could be sure would not be intercepted. With public keys, you just need to create one key, or actually a key pair. One of them is called the public key, and the other the private key. The amazing thing about these is that if the public key is used to encrypt something, that same key can not be used to decrypt it. The math on that is kind of amazing, so you might want to go back and read that earlier article.

This is wonderful, because we don’t need to worry about protecting the public key. You could paint it on your house, or publish it in the newspaper. Literally anyone can get it and use it to encrypt a message to you that only you will be able to read. The only trick is, how do they know that the public key is actually yours. What if some evil cryptographer decided to graffiti his key on your wall? Then everyone would be encrypting messages intended for you with his key so he would be able to read them.

Public key cryptography.

Public key cryptography.

In most public key systems, it also works the other way, so if the private key is used to encrypt the message, then only the public key can decrypt it. This might seem like a daft thing to do, to encrypt a message that absolutely anyone can read, because they all have access to your public key.

But wait….. only you could have created that encryption that they all can decrypt, so it acts like a signature. It assures the reader that the sender had access to your private key (and hopefully you have taken care that no one but you does).

This also helps take care of the “is this really your key” problem. If there are some people that we all trust, they can sign a certificate saying that “this key here belongs to this person with this email address” or to a specific website, or whatever. These entities are called Certificate Authorities.

You already use all this all the time when you visit secure websites. If you see the lock icon in your browser, or the URL starts with “https://”. Behind the scenes, the website is using public keys to handle the encryption of the page, and you know you are talking to the real website because the key and the domain name are in a certificate signed by a certificate authority. There are vulnerabilities in all this, but that is a subject for another post.

Email encryption is much less common. Now obviously I am not suggesting that you bust out a calculator and do some really large number exponentiation in a galois field every time you want to send your friend an email. Fortunately, all the heavy lifting has been taken care of for you. There are two widely used standards for email encryption: SMIME and PGP.

SMIME is a standard built into most email clients, including on iOS and Android. All you need to do is get an SMIME key and certificate. Several companies provide free SMIME certificates, of which the best known is Comodo. They only verify that the key you generate corresponds to your email address, by sending a confirmation email. Higher levels of authentication are available at a price.

Once you follow the instructions and install the certificate in your mail client, it will automatically sign all of your outgoing email and include a copy of your public key and certificate. If you receive a certificate from someone else, it will be stored on your computer, and used to encrypt any future emails to that person automatically.

PGP, and its free open source doppelganger GPG, work slightly differently. You will need to download and install the GPG software and plugins for your email clients. PGP / GPG support for mobile devices is a mixed bag at best. There are several advantages to using PGP / GPG however. First, you have complete control over the key generation process, and can create much longer keys than are available from SMIME providers. Second, you don’t need to trust some central certificate authority. Instead PGP / GPG use something called a web of trust. You personally sign the keys that you receive directly and securely from people you know. This make you like a micro certificate authority. You can then decide how much you trust people you know to verify keys from the people they know. This builds up a trust network whereby you can confirm the authenticity of keys without any one central trusted provider.

 

One problem with both of these email encryption solutions is that they leave a lot of information out in the clear. The To: and From: addresses need to be exposed, or the email won’t get delivered, and replies would not work. The Subject: line is also left unencrypted because …. reasons. So, anyone watching your communications can see the subjects you are talking about, and who you are talking with, and probably who they are talking with. This quickly builds up a very detailed and accurate picture of your personal social networks. For example, if you are a dissident, even if the government can’t read your messages, they know you are a dissident because a large fraction of your communications are with other known dissidents.

The same applies to secure web pages. The attacker may not know the contents of the pages your are visiting, but he does know the website you are visiting. If that page is http://deathtotyrants.org you are not leaving them a very hard puzzle to solve.

This kind of threat is called “traffic analysis”. Hiding your traffic patterns turns out to be much more difficult than hiding the contents of your messages.

There are a number of anonymity services which will help with this. TOR is free, and there are many paid options. All of these require a degree of trust in the operators, which is a trick with TOR since you don’t actually know who they are). If you use them to simply access public information, then it is difficult to do traffic analysis, but if you have any accounts out there, then you start giving away a lot of information. If you set up a gmail account through the service, then Google does not know who you are (if you make sure to get rid of all old Google cookies, or use a clean computer just for this). However, all the people you email from that account would be connected to that account and to each other by traffic analysis. Furthermore, if you communicate with the same set of people anonymously as you do under your real name, then that can be used as a very unique fingerprint to connect your anonymous account to your real identity. The same applies to any other kind of social media site.

You could use a different social media or email account for every single person you communicate with, and make sure that you change anonymous addresses and clean up the computer between each one. You would also have to make sure that you never ever make any mistakes, because log files live forever, are easy for governments to obtain, and can undo all your other work.

So, best of luck, and let me know how that tin foil hat is working out for you.

Posted in -- Guest Author, Computer Science, Paranoia | 4 Comments

Q: Where do the weird rules for rational numbers come from? (Dealing with fractions)

Posted on September 4, 2013 by The Physicist

The original question was:  Why is it when we multiply fractions we multiply the numerators across  and the denominators across?  Whereas when we divide we don’t do the same?  Who came up with these rules and why do they work the way they do?

Physicist: For all of these rules, start with addition and then extend and extend and extend, while doing the least damage possible.  At first blush I thought this would be a short and straightforward question, but it really isn’t.  There are wrong ways to construct the rules of arithmetic, but if you get technical there’s not necessarily a right way.  That said, as far as basic arithmetic goes (no highfalutin calculus, or set theory, or anything) there’s really just one “right” way.

Rational numbers (“fractions”) have been in use for thousands of years and they, and their rules, have been independently invented at least dozens of times.  More recently (19th century) a bunch of really A-type mathematicians got together to “put mathematics on a more rigorous footing“.  Those mathematicians (there were many) are responsible for unpleasant statements like “there are exactly as many prime numbers as rational numbers“, and are a big reason behind why modern mathematicians always look just a little pained when they speak.  It was these paragons of compulsivity that established how the rules are stated, and gave everything definite names like “associative”, “commutative”, etc.

Constructing the rational numbers and all of their behavior starts with an innocent statement; that “\frac{1}{A} is the unique number such that A\left(\frac{1}{A}\right) = \left(\frac{1}{A}\right)A = 1“.  This one definition is the headwaters for all of the properties of rational numbers that follow.  If ever you’re totally stuck, and don’t know how to handle fractions, keep this single and tremendously important definition in mind.  Everything else follows (but maybe not immediately).  Just a quick warning for those of you expecting any of the rest of this post be about history or something interesting; everything that follows is a dry-as-bones, utterly literal, derivation of the arithmetic rules for fractions and rational numbers from the ground up.  Definitely boring, but worth seeing once.

Starting with integers, along with regular addition, subtraction, and multiplication (basic arithmetic tools), and the definition of “\frac{1}{A}“, you’ll find that all of the weird properties of rational numbers come tumbling out.

Often \frac{1}{A} will be multiplied by another integer.  To save room we write: B\left(\frac{1}{A}\right) = \frac{B}{A}.  This is strictly a convention; a standard defined notation that’s agreed upon.

For example: \frac{3}{4} = 3\left(\frac{1}{4}\right).

For example: \frac{x+2}{6} = (x+2)\frac{1}{6}.

Already we can say things like: \left(\frac{3}{4}\right)4 = 3\left(\frac{1}{4}\right)4 = 3\cdot 1 = 3.  We can even do a little better and say B\left(\frac{C}{A}\right) = BC\left(\frac{1}{A}\right) = \frac{BC}{A}.

For example: 7\cdot\frac{3}{4} = 7\cdot3\cdot\frac{1}{4} = 21\cdot\frac{1}{4} = \frac{21}{4}.

How do fractions multiply?  It would be nice to know: \left(\frac{1}{A}\right)\left(\frac{1}{B}\right) = ?.  But check this out: \left(\frac{1}{A}\right)\left(\frac{1}{B}\right)AB = \left(\frac{1}{A}\right)A\left(\frac{1}{B}\right)B = 1\cdot 1 = 1.  This means that \left(\frac{1}{A}\right)\left(\frac{1}{B}\right) does the exact same thing that \frac{1}{AB} does, and (since this is all there is in the definition) in fact is the same.  So, \frac{1}{A}\cdot\frac{1}{B} = \frac{1}{AB}.

For example: \frac{1}{5}\cdot\frac{1}{3}\cdot15 = \frac{1}{5}\cdot\frac{1}{3}\cdot3\cdot5 = \left(\frac{1}{5}\cdot5\right)\left(\frac{1}{3}\cdot3\right) = 1.  But keep in mind that “\frac{1}{15} is the unique number such that 15\left(\frac{1}{15}\right) = \left(\frac{1}{15}\right)15 = 1“, and since \frac{1}{5}\cdot\frac{1}{3} has been shown to have the same property we know that \frac{1}{5}\cdot\frac{1}{3} = \frac{1}{15}.  This may seem anal-retentive and unnecessary, but that’s how math is done.

Now we’ve got the tools to define multiplication in general: \frac{A}{B}\cdot\frac{C}{D} = A\frac{1}{B}C\frac{1}{D} = AC\left(\frac{1}{B}\frac{1}{D}\right) = AC\frac{1}{BD} = \frac{AC}{BD}.  In other words “fractions multiply across”.

For example: \frac{3}{7}\cdot\frac{4}{5} = \frac{3\cdot4}{7\cdot5} = \frac{12}{35}.  Deriving the rules is often complex, but using them isn’t.

Now, again using nothing new, \frac{AC}{BC} = \frac{A}{B}\cdot\frac{C}{C} = \frac{A}{B}\cdot 1 = \frac{A}{B}.  This means two things: fractions can be reduced, and multiplying the top and the bottom by the same thing does nothing.

For example: \frac{9}{6} = \frac{3\cdot3}{2\cdot3} = \frac{3}{2}\cdot\frac{3}{3} = \frac{3}{2}.

It would be great if the addition and subtraction of fractions follow all of the same rules that hold for integers.  As a mathematician, the way you make this happen is to declare that it’s true, and then check for inconsistencies.  The rule most important for defining addition and subtraction of fractions is the “distributive law”, which says that “A(B+C) = AB+AC” (this doesn’t lead to any new inconsistencies).

First, \frac{A}{B} + \frac{C}{B} = \frac{1}{B}A + \frac{1}{B}C = \frac{1}{B}(A +C) = \frac{A+C}{B}.  So now, if the fractions have the same denominator, then they can be added together.

For example: \frac{3}{7} + \frac{5}{7} = \frac{3+5}{7} = \frac{8}{7}

But what about fractions with different denominators?  The trick is to not have them: \frac{A}{B} + \frac{C}{D} = \frac{AD}{BD} + \frac{BC}{BD} = AD\frac{1}{BD} + BC\frac{1}{BD} = (AD + BC)\frac{1}{BD} = \frac{AD+BC}{BD}

For example: \frac{2}{3}+\frac{5}{7}=\frac{2}{3}\cdot\frac{7}{7}+\frac{3}{3}\cdot\frac{5}{7}=\frac{2\cdot7}{3\cdot7}+\frac{3\cdot5}{3\cdot7}=\frac{14}{21}+\frac{15}{21}=\frac{14+15}{21}=\frac{29}{21}

Huzzah!  We can multiply, add, and reduce fractions with ease and impunity!

But what about dividing fractions?  Well, here we have to tread lightly and describe exactly what is meant by “dividing by a fraction”.  So, in a perfectly reasonable extension of the original definition, “\frac{1}{\left(\frac{A}{B}\right)} is the unique number such that \frac{A}{B}\left(\frac{1}{\left(\frac{A}{B}\right)}\right) = \left(\frac{1}{\left(\frac{A}{B}\right)}\right)\frac{A}{B} = 1“.

But check this out: \frac{B}{A}\cdot\frac{A}{B} = \frac{B\cdot A}{A\cdot B} = 1.  Since \frac{B}{A} does exactly what \frac{1}{\left(\frac{A}{B}\right)} is defined to do, we can say that \frac{1}{\left(\frac{A}{B}\right)} = \frac{B}{A}.

Another way to see this is to say \frac{1}{\left(\frac{A}{B}\right)} = \frac{1}{\left(\frac{A}{B}\right)}\cdot\frac{\left(\frac{B}{A}\right)}{\left(\frac{B}{A}\right)} = \frac{1\cdot\frac{B}{A}}{\frac{A}{B}\cdot\frac{B}{A}} = \frac{\frac{B}{A}}{\frac{AB}{BA}} = \frac{B}{A}\cdot\frac{1}{\frac{1}{1}} = \frac{B}{A}\cdot\frac{1}{1}= \frac{B}{A}

For example: \frac{\left(\frac{3}{4}\right)}{\left(\frac{7}{2}\right)} = \frac{3}{4}\cdot\frac{1}{\left(\frac{7}{2}\right)} = \frac{3}{4}\cdot\frac{2}{7} = \frac{3\cdot2}{4\cdot7} = \frac{6}{28}.

Just a quick note on behalf of whoever grades your tests or homework: Please reduce fractions, \frac{6}{28} = \frac{2\cdot3}{2\cdot14} = \frac{2}{2}\cdot\frac{3}{14} = \frac{3}{14}.

For example: \frac{x+7}{\frac{1}{2}} = (x+7)\frac{1}{\frac{1}{2}} = (x+7)\cdot2 = 2x+14

What about subtraction and negative numbers? In general, in every case, without exception of any kind, whenever you see “-A” you can exchange it with “(-1)A” and exchange “B-A” with “B+(-1)A”.  After that, treat “(-1)” just like any other number or variable*.

So (still using no new rules!), we can say \frac{A}{B} - \frac{C}{D} = \frac{A}{B} + (-1)\frac{C}{D} = \frac{A}{B} + \frac{(-1)C}{D} = \frac{AD}{BD} + \frac{(-1)BC}{BD} = \frac{AD+(-1)BC}{BD} = \frac{AD-BC}{BD}

For example: -\frac{3}{7} + \frac{9}{2} = \frac{-3}{7} + \frac{9}{2} = \frac{-3\cdot2}{7\cdot2} + \frac{9\cdot7}{2\cdot7} = \frac{-3\cdot2+9\cdot7}{2\cdot7} = \frac{-6+63}{14} = \frac{-57}{14} = -\frac{57}{14}

For those of you who’ve read this far, you can show using the same definitions and tricks above that:

\frac{1}{(-A)} = -\frac{1}{A}.

Using the fact that A^n=\overbrace{A\cdot A\cdots A}^{n\textrm{ times}}, you can get \left(\frac{A}{B}\right)^n = \frac{A^n}{B^n}.

Similarly, you can show that \left(\frac{A}{B}\right)^{-n} = \left(\frac{B}{A}\right)^n.

There are big issues with \frac{1}{0}, because it’s defined as the number that, when multiplied by 0, gives 1.  But of course that number doesn’t exist*.  In practice, if you ever see a “1/0”, stop mathing.  And every time you divide by something that could be zero, make a note on the side of the paper.  The short answer to almost every question about “1/0” is “doesn’t”.

For example: If x+1 = x-1, then \frac{x+1}{x-1} = 1 and by the way only when x\ne1.

It’s also worth pointing out that when things are added in the denominator, there’s not much that can be done with it.  So, if you’ve got something like \frac{3}{x+2}, then you’re stuck.  That’s as simplified as it can get.  The one and only thing you can say about \frac{3}{x+2} is that \frac{3}{x+2}\cdot(x+2) = 3 (so long as x\ne-2).

Also, for those of you wondering (this is a bit technical), the rational numbers also inherit their positions in the number line very naturally.  Using only the fact that “if A<B and C>0, then AC<BC” and the fact that we know how to order integers, you can figure out which rational number is bigger than which other rational numbers.  Since \frac{A}{B}<\frac{C}{D}\Leftrightarrow AD<BC, if you can figure out which of AD and BC is bigger (they’re both integers), then you can figure out which of \frac{A}{B} and \frac{C}{D} is bigger.

For example:

\begin{array}{ll}\frac{7}{4}\,[?]\,\frac{5}{3}\\\Rightarrow 3\cdot4\cdot\frac{7}{4}\,[?]\,\frac{5}{3}\cdot3\cdot4\\\Rightarrow 3\cdot7\,[?]\,5\cdot4\\\Rightarrow 21\,[?]\,20\\\Rightarrow 21>20\\\Rightarrow\frac{7}{4}>\frac{5}{3}\end{array}

Even better, we can describe exactly where the rational numbers are!

For example: You can show that \frac{1}{2} is just as far from 1 as it is from 0.  1-\frac{1}{2} = \frac{2}{2}-\frac{1}{2} = \frac{2}{2}+\frac{-1}{2} = \frac{2-1}{2} = \frac{1}{2} and \frac{1}{2}-0 = \frac{1}{2}.

Just to get ahead of the most obvious follow up questions:  There’s a lot of weird emphasis on how exactly mathematical notation is used in text.  The first key to dealing with complicated text-based notation is: don’t.  Writing equations using the symbols found only on a keyboard is something our unfortunate and sadly limited ancestors had to consider.  If you’re reading this now, then you’re in a bigger and better-notated world.

In general, you can always write A/B = A(1/B), and A/B/C = A(1/B)(1/C), and so on.  A little fancier: A/B/C = A\cdot\frac{1}{B}\cdot\frac{1}{C} = \frac{A}{BC}.  If for some horrifying, bizarre reason you find yourself looking at a string of numbers or variables being multiplied together, with no parentheses in sight, just replace “A/B” with “A\frac{1}{B}” and go*.

For example: 2/3\cdot7A/4/2/D = 2\cdot\frac{1}{3}\cdot7\cdot A\cdot\frac{1}{4}\cdot\frac{1}{2}\cdot\frac{1}{D} = \frac{2\cdot7\cdot A}{3\cdot4\cdot2\cdot D} = \frac{7A}{12D}.

That (way too long of a post) all said, if you’re reading this because you’re presently panic-studying the night before a test, and actually needed a short answer, memorize this:

“A/B is A times 1/B.  1/B times B is one.  There’s nothing else to say about 1/B.”

and go to sleep sooner rather than later.

*If your math background is extensive enough to know some exceptions, then… be cool, you know what I mean.

Posted in -- By the Physicist, Conventions, Math | 7 Comments