Wikipedia:Reference desk/Archives/Mathematics/2011 May 12

Mathematics desk
< May 11	<< Apr | May | Jun >>	May 13 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 12

Special Relativity Small Angle Approx.

Given cosθ =(E-3mc²)/(E+mc²) where E is the relativistic energy, how does one show that for v<<c, θ≈π-v/c? I know that it involves Taylor expansion approximation but couldn't quite get it into this form... Thanks! —Preceding unsigned comment added by 131.111.222.12 (talk) 11:04, 12 May 2011 (UTC)

Let $\alpha =\pi -\theta$ and $r=v/c$. Show that $E=mc^{2}(1+r^{2}/2+O(r^{4}))$ and combine it with $\cos \alpha =-\cos \theta$ to show that this is both $1-\alpha ^{2}/2+O(\alpha ^{4})$ and $1-r^{2}/2+O(r^{4})$. Now, intuitively this should imply that $\alpha =r+O(r^{2})$, but I don't know of an easy rigorous way to show it. -- Meni Rosenfeld (talk) 12:37, 12 May 2011 (UTC)

Thanks, Meni! :) —Preceding unsigned comment added by 131.111.222.12 (talk) 13:10, 12 May 2011 (UTC)

Four Point Particles

Hi, I have a solution to this, but I am looking for a more elegant solution. If we are given 4 positively charged particles at the 4 corners of a square, is there a better proof for the stability of the central point of square for a 5th positively charged particle apart from (the clumsy way of) computing the 2nd partial derivatives of the U(x,y)...? Thanks! —Preceding unsigned comment added by 131.111.222.12 (talk) 12:36, 12 May 2011 (UTC)

You can use symmetry to significantly cut down on the work. That this is an equilibrium (zero partial derivatives) is obvious from symmetry. The ${\frac {}{\partial x\partial y}}$ 2nd derivative is 0 by symmetry, so you only need to show that the ${\frac {}{\partial x\partial x}}$ and ${\frac {}{\partial y\partial y}}$ (which are equal because of symmetry) are positive. When calculating ${\frac {}{\partial x\partial x}}$, the force applied by the particles with the same x but different ys have the same x-component, so you can calculate for just one on the left and one on the right. wlog the corners of the square are at +-1, so the x-component of the force the particles apply is ${\frac {1+x}{((1+x)^{2}+1)^{3/2}}}-{\frac {1-x}{((1-x)^{2}+1)^{3/2}}}$, so you just need to show the derivative of this is negative. In fact, because the second summand is the negated reflection of the first, it has the same derivative at 0 as the first, so it's enough to show that the derivative of ${\frac {1+x}{((1+x)^{2}+1)^{3/2}}}$ is negative, or equivalently, that the derivative of ${\frac {t}{(t^{2}+1)^{3/2}}}$ is negative at $t=1$. So the only actual calculation we have to do is the derivative of that last part. -- Meni Rosenfeld (talk) 12:47, 12 May 2011 (UTC)

Thank you!

Density of a sphere packing

In the article Close-packing of spheres and Sphere packing, the density of these packings is mentioned. Yet it is not clear to me how the density of an arbitrary sphere packing is calculated. How does one calculate this? For example, how do I calculate the density of the hcp and the fcc packing (see also File:Close packing box.svg)? Toshio Yamaguchi (talk) 13:25, 12 May 2011 (UTC)

For repeating patterns, you could find a repeating cell and then calculate the fraction of that cell which is "covered" by the spheres. Since the whole lattice is made up from copies of the repeating cell, the density of the lattice as a whole is the same. 86.181.203.129 (talk) 17:25, 12 May 2011 (UTC)

Note that for some patterns, there will be "edge effects", where the density is lower on the faces. However, for a larger structure with millions of cells, this will be insignificant. StuRat (talk) 18:19, 12 May 2011 (UTC)

What particularly strong reasons are there in favor of using equivalence classes?

I don't doubt the existence of such reasons; they're just not obvious and I feel like the math professors just tell us that this is the way to identify multiple things as being equal, without really justifying it. The way to define integer arithmetic modulo n is to break the integers into n equivalence classes. The alternative is to just compute with integers, with the understanding that certain things are 'equal' according to an equivalence relation. Just as with the equivalence class approach, of course, you would have to show that addition and multiplication are well-behaved wrt the equivalence relation defined on the integers.

One argument for equivalence classes is that you can easily speak of the cardinality of the partition (as in, there are exactly n equivalence classes of integers modulo n), whereas it is more difficult to phrase that same question if you haven't collected the set into equivalence classes. What are some others? One possibility: are there examples of operations or other forms of structure that wouldn't be possible or easy to define without having first collected sets of equivalent elements together? --COVIZAPIBETEFOKY (talk) 14:28, 12 May 2011 (UTC)

There are lots of applications and it's really part of the basic machinery of mathematics in general. One application is the construction of number systems: integers can be defined as equivalence classes of pairs of natural numbers, rationals can be defined as equivalence classes of pairs of integers, reals can be defined as equivalence classes of Cauchy sequences of rationals. Surreal numbers use equivalence classes implicitly. In algebra there are quotient groups, quotient rings, quotient algebras, etc. and in topology there are quotient spaces. There are hundreds of articles that link to our article on them, so I'd say there are really too many examples to list.--RDBury (talk) 17:21, 12 May 2011 (UTC)

I think you missed the point. He's not asking for applications. He's asking for a reason to code the notion into equivalence classes, instead of simply redefining equality and taking care of it at the level of logic.

There are actually lots of problems that show up, at least at a formal level, when you try to make equality be anything other than strict identity. I'm sure people have tried to do that; I'd be interested myself in a pointer to how it goes and what the difficulties are, because I'm not coming up with the details at the moment.

At an informal level, though, it usually is more convenient to work with representatives rather than classes, and just be careful that everything you do with them respects the equivalence relation. So I guess I'd say that in most cases the purpose of equivalence classes is not to help you do the mathematics, but to make it clear how the mathematics would be formalized if you need to. --Trovatore (talk) 17:32, 12 May 2011 (UTC)

If you ask what are the elements of a quotient group, what would the answer be if not equivalence classes? I'm not saying there's no possible answer to that question, but maybe someone should propose one if the wisdom of speaking of equivalence classes is questioned. Michael Hardy (talk) 18:58, 12 May 2011 (UTC)

The answer would be that they're just the elements of the dividend group, except that now you're considering some of them to be the same. --Trovatore (talk) 19:00, 12 May 2011 (UTC)

I'm not questioning the wisdom of equivalence classes. I'm asking for examples where they become an indispensable tool, either in comprehension of a particular concept or in the definitions themselves, rather than merely being a convenient means of description.

I do think this lends itself a good answer to my question, though: if one wants to talk about homomorphisms between groups, such a thing would be much harder to define if you were to allow distinct elements of the set to be considered equivalent.

So, if I may narrow down my question a bit more:

Are there any examples of a set $S$ with an equivalence relation $\sim$, where a map $f:S/\sim \to S/\sim$ is easier to define than a corresponding map $f':S\to S$ inducing the same $f$? It is always easy to define $f$ given a definition for $f'$, but going the other direction would, in general, be trickier, and maybe impossible to do without utilizing the axiom of choice.

To be clear: I'm not asking for an existence result. I'm asking for an explicitly given example of $S,\sim ,f$, where $f$ has a simpler definition than any $f'$ could hope to have. --COVIZAPIBETEFOKY (talk) 03:45, 13 May 2011 (UTC)

I'm not sure that the definition of $f$ is supposed to be simpler than that of $f'$. In fact, often you define a function like $f'$ first and then verify that it is constant on each equivalence class, and so "descends to the quotient". The existence of $f$ tells you that the original function has some structure that may not always be convenient to express explicitly. For instance, consider the quotient $P/L$ of the plane by a one-dimensional subspace. A linear function $f:P/L\to \mathbb {R}$ corresponds to a linear function $f':P\to \mathbb {R}$ that is constant on every line parallel to $L$. Sławomir Biały (talk) 10:30, 13 May 2011 (UTC)

To me, your idea of using elements of S but considering some of them equal is exactly the same as the idea of equivalence classes (but stated informally, and with the details left in the background). It may seem like thinking about the set [s], the equivalence class of s, instead of just thinking about s, is unnecessary baggage; but it really isn't.

As soon as you say you're now considering some elements equal, I'm going to ask you which ones. In particular, which ones are equal to s? You can explain it however you want, but you're defining an equivalence relation. And it has to be reflexive, symmetric, and transitive, or you're speaking nonsense. You recognize the importance of well-definedness, but it's nice to have the details in the open.

You'll also run into some notational trouble if you have different notions of = in the same discussion. For an example of this confusion, working modulo 7, we know that 45+15 = 32, because 45 = 3+6(7) = 3, 15 = 1+2(7) = 1, 32 = 4+4(7) = 4, and 3+1 = 4. Of course, I really mean 45+15 =₂ 32, because 45 =₁ 3+6(7) =₂ 3, 15 =₁ 1+2(7) =₂ 1, 32 =₁ 4+4(7) =₂ 4, and 3+1 =₁ 4, where =₁ is the usual equality in the integers and =₂ is the modulo 7 equivalence relation. Using different symbols for different equivalence relations is fine, but I would prefer using brackets to indicate equivalence classes. Either way, though, you're doing exactly the same thing-- you're working with sets of equivalent elements (whether or not you ever use the word "set") and you have to check the same properties to show it's well-defined. There's no mystery or extra baggage to the notion of equivalence classes; that's just the notation and terminology mathematicians have settled on.71.58.77.50 (talk) 14:21, 13 May 2011 (UTC)

I was always talking about equivalence relations.

I disagree (with "your idea of using elements of S but considering some of them equal is exactly the same as the idea of equivalence classes"); I don't think the notion of an equivalence relation is identical to that of an equivalence class, and there is no immediate reason that you should collect equivalent elements into equivalence classes. I don't know why you confuse the two so easily. I know that a partition induces an equivalence relation and vice-versa, but the use of an equivalence relation does not necessitate the use of equivalence classes, as you seem to want to believe. --COVIZAPIBETEFOKY (talk) 01:07, 14 May 2011 (UTC)

As for your last paragraph, that's exactly my point! As long as you are only speaking of the relationships between individual elements (rather than, say, global questions about the set, such as "how many groups of equivalent elements are there?"), the difference between using an equivalence relation and using equivalence classes is purely one of notation. --COVIZAPIBETEFOKY (talk) 01:20, 14 May 2011 (UTC)

It seems to me that mathematicians get uncomfortable in situations where equivalence classes become infeasible, for no good reason. Case in point: cardinality. Two sets are considered equivalent if they have the same cardinality. You cannot collect these into equivalence classes, because the equivalence classes aren't sets. The most common solution is to pick a choice representative, namely, the smallest ordinal of a given cardinality, and work with those. But why should we bother picking special representatives? Why can't we just discuss cardinality as a feature of a set without giving it a specific representative? --COVIZAPIBETEFOKY (talk) 01:25, 14 May 2011 (UTC)

I don't really know any cases where the function is simpler to define on the classes than on the representatives. Most often it's the other way around. That's how we define reducibility on Borel equivalence relations for example, by talking about the functions on the representatives.

I gave an undergrad colloquium talk at San Jose State a year or so ago talking about some of these things; if you're interested it's called How to have more things by forgetting where you put them --Trovatore (talk) 17:56, 13 May 2011 (UTC)

Thanks for that reference, Trovatore! Quite a fascinating read. --COVIZAPIBETEFOKY (talk) 02:15, 14 May 2011 (UTC)

In the usual argument showing that non-measurable sets exist, can you eliminate the use of equivalence classes? Since you need to appeal to the Axiom of Choice allowing you to pick an element of each of the members of the quotient set, it seems to me that you cannot do that. Count Iblis (talk) 22:12, 13 May 2011 (UTC)

Yes, that does seem to be the case, as far as I can tell. --COVIZAPIBETEFOKY (talk) 01:07, 14 May 2011 (UTC)

Simple puzzle

Hi. A square lattice of side n is made up of n^2 square tiles. The number of tiles around the perimeter is n^2 - (n - 2)^2, or 4n - 4. Can anyone think of an intuitive/visual way to appreciate why, for n = 1, the answer is 0 and not 1? (Note: I am not looking for further mathematical/symbolic justifications. I want to be able to look at a single square and "see" why there are zero squares on its perimeter.) 86.181.203.129 (talk) 17:39, 12 May 2011 (UTC)

Just because you have a formula that says zero doesn't mean it is actually zero. And it most certainly looks like one to me. Dmcq (talk) 17:46, 12 May 2011 (UTC)

Nevertheless, it is strange (in my opinion) that a formula which works perfectly well for all other values of n should fail with n = 1. It is equally hard to think of a plausible formula that gives an answer 1 for n = 1 and correct results for all other values of n. 86.181.203.129 (talk) —Preceding undated comment added 17:53, 12 May 2011 (UTC).

It seems to me that the problem comes down to how you define a "perimeter square". Some possibilities:

1) A square where any portion of that square is on the perimeter. This seems to be the def you are using.

2) A square where any portion of that square is on the perimeter and another portion is not. In other words, you can't have an "outside" if you don't have an "inside". This def seems to match that formula better. StuRat (talk) 17:57, 12 May 2011 (UTC)

Perhaps a better formula would be the total squares (n²) minus the interior squares. The tricky part here is defining the interior squares. (n-2)² is the general formula, but this falls apart when n = 0 or 1. So, the correct formula starts with n², but only subtracts (n-2)² in cases where n-2 ≥ 0. I'm not sure how to write that mathematically. StuRat (talk) 18:15, 12 May 2011 (UTC)

It is typical to write formulas that involve a "choice" like that as piecewise defined functions. You could also achieve the result with an Iverson bracket if you really wanted it to appear as a single formula. (You could probably also hack something together that uses the Heaviside step function or the sign function.) —Bkell (talk) 15:47, 14 May 2011 (UTC)

One could incorporate the cases n=0 and n=1 into the formula for the number of "interior" squares by writing this number as $(n-2)_{+}^{2}$, where $(n-2)_{+}=\max\{0,n-2\}$ is the positive part of n-2. Then a general, and correct, formula for the number of "perimeter" squares would be $n^{2}-(n-2)_{+}^{2}$. Then you would be able to look at the square with n=1 and indeed see that the formula says there is one perimeter square. Nm420 (talk) 17:48, 15 May 2011 (UTC)

Poppit probabilities

There's an online game at Pogo called Poppit. Here are the rules:

1) You start with a 2 dimensional array of balloons, 15 wide and 10 high, for 150 balloons total.

2) These balloons are of random color, from a small number of colors. I'm not quite sure what the range of the number of colors is, but 5 seems typical.

3) When two or more balloons of the same color are adjacent, you may pop the group.

4) When a group is popped, any balloons below an empty space float to the top.

5) If any empty column is formed, the balloons on either side float together, as a group, to close the balloons together. Thus, the balloons always form a single contiguous group.

6) The object is to pop all the balloons.

Now for my questions:

A) How many "games" are possible. That is, how many different ways can the balloons be popped ? In the worst possible case, with only groups of 2 formed, there could be up to 150/2 or 75 groups. This means 75 possible pops the first time, then 74, etc. So, I get 75! games. However, does that logic still apply if groups are forming and dissolving based on which previous groups were popped ?

B) Instead of the worst case, what's the average number of games ?

C) To solve the puzzle, and get a perfect game with no balloons left (assuming one is possible), how many possible pops must be considered, on average ? Note that there may be many possible perfect games (orders in which the balloons can be popped to leave none), for any initial arrangement.

My motivation is to write a program to solve Poppit games. (I've already done so for the much smaller (4×4 - 7×7) versions in Pop Fu.) However, my initial assessment is that there are just too many combos to take the brute force approach, as I did with the smaller boards. Am I correct ? What other approach might work ? StuRat (talk) 18:46, 12 May 2011 (UTC)

For searchability, this game is called SameGame. – b_jonas 19:33, 12 May 2011 (UTC)

In A, when you ask "how many different ways can the balloons be popped?", I guess you mean how many different ways can all the balloons be cleared for a given starting grid? (When I first read it, I thought you meant over all possible grids.) What constitutes a "different way"? Suppose all the balloons are initially numbered so they can be uniquely identified as the game progresses. Are games identical only if balloons are popped in the same numerical sequence and they are in the same grid position when popped? 86.181.203.129 (talk) 20:11, 12 May 2011 (UTC)

Yes. StuRat (talk) 20:18, 12 May 2011 (UTC)

Clearly I'm missing something here; I don't even see how you get 75 to begin the 75! calculation. I see 14 * 10 horizontal groups of two, and 15 * 9 vertical groups of two, so the first two balloons can be popped in 275 ways. 86.181.203.129 (talk) 22:14, 12 May 2011 (UTC)

I don't understand. Can you show me what you mean ? Perhaps you're missing that all vertically or horizontally (but not diagonally) connected balloons in a group always pop whenever you pick one. StuRat (talk) 01:02, 13 May 2011 (UTC)

Here's one possible "worst case" configuration, with 75 groups (I used spaces and blank lines to show the groups, they aren't really there):

Y G R B P  Y G R B P  Y G R B P  
Y G R B P  Y G R B P  Y G R B P  

G R B P Y  G R B P Y  G R B P Y  
G R B P Y  G R B P Y  G R B P Y  

Y G R B P  Y G R B P  Y G R B P  
Y G R B P  Y G R B P  Y G R B P  

G R B P Y  G R B P Y  G R B P Y  
G R B P Y  G R B P Y  G R B P Y  

Y G R B P  Y G R B P  Y G R B P  
Y G R B P  Y G R B P  Y G R B P

The colors used are Yellow, Green, Red, Blue and Purple. So, any of the 75 groups could be popped first, leaving 74 groups. Any of those could then be popped, leaving 73 groups, etc. StuRat (talk) 01:02, 13 May 2011 (UTC)

Sorry, ignore me. When I first read your question "How many 'games' are possible" I thought you meant total number of games across all starting grids. Although this was later corrected, I somehow carried on thinking that was the question. If you allow any starting grid, then a pair of poppable balloons can be in any of 275 positions, but that isn't what you're asking. Apologies for the confusion. 86.181.203.129 (talk) 01:32, 13 May 2011 (UTC)

OK, thanks. StuRat (talk) 03:34, 13 May 2011 (UTC)

Some (possibly banal) suggestions for optimizing the program:

• Compute and keep in memory as large an endgame tablebase as possible.
• Try to come up with some easy to calculate heuristic which provides some information on the plausibility of a solution existing (eg, the proportion of adjacent balloon pairs which are of the same color). You can calibrate it by running simulations with number of pieces slightly above what you have in your endgame table. Then use this as a proxy for the optimal move when you can't brute-force deep enough.
• Use a transposition table.
• I don't know if pruning methods like alpha-beta apply for one-player games, but they might be worth thinking about.

-- Meni Rosenfeld (talk) 09:23, 15 May 2011 (UTC)

Some interesting suggestions. I might try the endgame tablebase. I really want to find the best possible solution, though, and using heuristics isn't guaranteed to do that. Then again, what I want may not be possible. StuRat (talk) 04:25, 16 May 2011 (UTC)