Wikipedia:Reference desk/Archives/Mathematics/2006 December 15

From Wikipedia, the free encyclopedia

You have new messages (last change).
Mathematics desk
< December 14 << Nov | December | Jan >> December 16 >
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.


Contents


[edit] December 15

[edit] Coordinate geometry

Dear Sir/Madame, could you please give me a hint on how to solve the following problem?

The sides of a rhombus ABCD are parallel to the lines y=x+2 and y=7x+3.If the diagonals of the rhombus intersect at the point O(1,2) and the vertex A is on the y-axis,find the possible coordinates of A.

-Sruthi —The preceding unsigned comment was added by 59.93.72.110 (talk • contribs) 03:30, 15 December 2006 (UTC)

See if you can figure out what direction (i.e. slope) each of the diagonals are, based on the angles, etc. in a rhombus, and the slopes of the sides. You also know a point that lies on both diagonals. You also know that A (a vertex) lies on one of the diagonals and on the y-axis. You can figure it out from there. --Spoon! 05:13, 15 December 2006 (UTC)

[edit] Difference between dx and dx

Is there a difference between the dx (both italicized) and dx (only x italicized) notations? If so, what are some appropriates usages for each? Which is the form used in integration? Larry V (talk | contribs) 08:23, 15 December 2006 (UTC)

Check carefully if you are speaking about dx and ∂x. They're two different operations, as one involves a one-variable function and the other one involves functions of several variables. Titoxd(?!?) 08:25, 15 December 2006 (UTC)
Both are notations are widely used. Basically, roman versus italic d in integration is an aesthetic choice, depending how you want to typeset integrals. If you write
\int_0^1 f(x)\mathrm{d}x
you emphasize that the d is something different from the functions and variables. However, everybody knows what you mean anyway, so many mathematicians are lazy and just type
\int_0^1 f(x)dx
and both mean absolutely the same thing. (Of course individual authors may have their own notation and might define other meanings for roman and italic d). Kusma (討論) 09:02, 15 December 2006 (UTC)
In one textbook I had, the author (without really mentioning it, so it took the lecturer asking him to get the full story) used "d" and "'d'" to distinguish between stochastic calculus equations and normal ones, but I don't know if that's standard usage anywhere else. Confusing Manifestation 13:14, 15 December 2006 (UTC)
In my experience, the d in dx is routinely italicized. When editing an article, dx is the standard version for use in an integral (and should be preceeded by "\,".
\int f(x) \, dx
A major textbook on general relativity, Gravitation (ISBN 978-0-7167-0344-0), uses a variety of typographic conventions for different meanings of "d". However, these theoretic physicists are a fun-loving bunch, and are trying to cover a broad range of topics, including ordinary differentials/integrals, differential forms, and covariant derivatives. Without the typographic distinctions the reader could easily get lost (and may, anyway!). --KSmrqT 22:19, 15 December 2006 (UTC)


I have a vague memory that this may be a Yank/Brit difference, or maybe Anglophone/Continental. Does that ring a bell with anyone? --Trovatore 06:28, 16 December 2006 (UTC)

How do you pronounce ∂? Black Carrot 16:31, 19 December 2006 (UTC)
I think it's usually pronounced the same as the ordinary letter d. I think "curly d" can also be used for disambiguation. -- Meni Rosenfeld (talk) 17:07, 19 December 2006 (UTC)
I learned it as pronounced "die" from my calculus professor, but that may have been to distinguish between it and the standard derivative in one dimension (dx). -- Sir Escher talk 01:09, 24 December 2006 (UTC)

[edit] board games

Since game theory seems to fit the category of mathematics best I'm asking this question here. Although the rules for each piece as well as other rules, if followed, prevent a board from being invalid a board can be or is invalid when any of these rules are not followed. Consequently boards may be divided into two classes, one called valid and the other invalid. My question is whether there is an online list of boards which are known to be valid (such as a list of played games) and known to be invalid (to demonstrate an invalid move)? Adaptron 13:33, 15 December 2006 (UTC)

My guess is that no, because, for example, if you take a game like Chess, there would be a total of something like 1070 board positions (I'm including obviously invalid ones in this count), so any attempt to make such a list would not be meaningful. There might be something similar, but I don't know about it. -- Meni Rosenfeld (talk) 14:10, 15 December 2006 (UTC)
For the game of Chess I think Shannon computed 10120 but I disagree that a list of known valid and invalid moves even though only a fraction of those possible still provide meaningful information in that such a list would represent boards which did not have to be determined by replaying a game or redemonstrating an invalid move but rather only looked up. Its the same reason we have Sin and Cos tables, etc. A lookup is in general faster than a computation. Adaptron 14:32, 15 December 2006 (UTC)
Also ...out of 256 possible syllogisms only 15 to 24 are valid. Adaptron 14:37, 15 December 2006 (UTC)
(After double checking - it's been a long time - syllogisms 16 to 24 violate rule #6) Adaptron 15:37, 15 December 2006 (UTC)
Another word about this since I've had correspondence with the author, Mark Andrews, who published 16 to 24 without referencing Stephen Barker's "The elements of Logic" (1965) which adds 16 to 24 by ignoring rule #6 on the basis of the "existential viewpoint", the deciding factor being that rule #6 was not made optional by Aristotle. Adaptron 03:09, 17 December 2006 (UTC)

How do you define valid vs invalid? In chess there are some simple rules of thumb (e.g. it's not possible for the king of the player who just moved to be in check) but determining whether a position could have resulted from a valid sequence of moves from the starting position can be very nontrivial — see retrograde analysis. —David Eppstein 16:15, 15 December 2006 (UTC)

In terms of a list of valid and invalid boards I am defining valid and invalid strictly by the board being the result of the last move or by stand alone boards. A stand alone board would be for instance a board that had been turned a quarter turn and the populated with pieces such that a8 was in the lower left hand corner instead of a1. Adaptron 22:09, 15 December 2006 (UTC)
For chess, bishops can never move to a square of the opposite color, and pawns can never move backwards or sideways (though a diagonal capture is legal). --KSmrqT 22:25, 15 December 2006 (UTC)
We had logarithmic tables. These days, the cost of computing these values is negligible compared to the cost of storing these tables. And you didn't seem to understand my concern, where are you going to find over 10^50 Terabytes of storage space? Not to mention that each of those will have to be calculated before it can be stored. Humanity just doesn't have (yet) enough computational power for such a project. -- Meni Rosenfeld (talk) 23:48, 15 December 2006 (UTC)
All modern chess programs use a hash table as well as a tornenement table as well as an end game table, etc. The tables are used to eliminate unecessary computation just as bitboards are used for the same thing. In terms of rules, however, compliance is in general verified by computation rather than by looking up positions in a table. But that is not the point. The point is that such tables can prevent games that have already been played from being repeated. Adaptron 04:43, 16 December 2006 (UTC)
Yes, tables are used, but they are not even nearly exhaustive. I think it's common to have exhaustive tables for something like 5-6 piece endings, and a database of tournament games (which I don't think are more than the order of hunderds of thousands). That is a very different thing from having a database of every thinkable position. But I'm still not sure about your motivation - do you expect players, before making their move, to look at the database to make sure it hasn't ever been played? Or that if a player wants to do a move which was played before, he will be told, "sorry, you can't do that"? Will that also mean that the white player won't be able to play "e4" for his first move? -- Meni Rosenfeld (talk) 15:41, 16 December 2006 (UTC)
Any player should have the option of playing a game that is unique and so application of such a database for that purpose would only rule out games at the point where the game provided no more options according to the database rather than at the point of the first move of a game such as "e4." However, my motivation is not to accommodate the human player but rather the machine. Adaptron 02:55, 17 December 2006 (UTC)
Okay, so you're suggesting that this should be used to limit the possibilities of an AI opponent. I still didn't understand where do you draw the line between moves which obviously should be allowed and those that should be forbidden. And I still don't agree that this is a good thing to do - machines have feelings too (well, not really, but...), and if a program decides that it wants to do some move, it should be allowed to do it. And finally, I don't see how this is necessary - all it takes to prevent repetition of games (with high probability and excluding trivial games) is a good pseudorandom generator and a proper weighting scheme for moves (and this will also strengthen the AI). -- Meni Rosenfeld (talk) 12:30, 17 December 2006 (UTC)

[edit] How to write simple p > 1?

I could not figure out how to write this very simple expression as a math formula...

p > 1.

I could write p \ge 1 no problem.

But the wiki parser could not figure out p > 1.

Could someone please show me how to write this simple math expression? —The preceding unsigned comment was added by 24.28.66.254 (talk • contribs).

\qquad p>1 yandman 15:27, 15 December 2006 (UTC)
There is a setting where, by default, "simple" formulas appear as normal text; adding something like \qquad seems to make it not simple anymore. —AySz88\^-^ 18:49, 15 December 2006 (UTC)
Though you should really just change your own settings. --h2g2bob 18:51, 15 December 2006 (UTC)
Ah, what you want is to force PNG rendering. The trick is to use a space plus a negative space. See Help:Displaying_a_formula#Quadratic_Polynomial_.28Force_PNG_Rendering.29 for instructions. ☢ Ҡi∊ff⌇↯ 20:07, 15 December 2006 (UTC)
I don't understand why anyone would ever want to do that. —Keenan Pepper 20:08, 15 December 2006 (UTC)
Consistency. Say you want to develop a proof in several steps, and a few steps will be rendered in HTML and others as PNG. That'll look inconsistent and distracting, so we force PNG rendering and everything looks alike. ☢ Ҡi∊ff⌇↯ 20:10, 15 December 2006 (UTC)

[edit] measures of time

name some imprtnat terms - (century,daid) —The preceding unsigned comment was added by 59.94.138.135 (talk • contribs).

See Units of time. Gandalf61 17:38, 15 December 2006 (UTC)
Plus the relevent prefixes - gives many more eg second, millisecond, microsecond etc. SI prefix 87.102.8.6 18:20, 15 December 2006 (UTC)

[edit] Regular symmetry around a point

Does anyone know how (if it is possible) to arrange 7 'objects' around a point so that their positions can be considered equivalent. So far I have succeeded with 2,3,4,5,6,8,10,12,20 objects (eg 4 points of a tetrahedron). The 'objects' do not have to be single points.

So far I have not succeeded and think it impossible - can anyone enlighten me?87.102.8.6 17:58, 15 December 2006 (UTC) (Three dimensions please - no 2D heptagons/heptagonal tops please)87.102.8.6 18:11, 15 December 2006 (UTC)

Do you mean you want to arrange 7 points (or other objects) on the surface of a sphere so the points are all equidistant from their nearest neighbors ? StuRat 18:05, 15 December 2006 (UTC)
Effectively yes(sort of), if they were points I would expect them to be the same distance - but each point must also experience the same symmetry enviroment as well, (can't quite think of the correct term.)87.102.8.6 18:11, 15 December 2006 (UTC)
The only point groups in three dimensions with a 7-fold symmetry axis are polar ones, which means your seven points are in a planar heptagon. So what you're asking for is impossible. —Keenan Pepper 20:06, 15 December 2006 (UTC)
In three dimensions, you've got platonic solids, which have even spacing across their surface and are "symmetrical". Then there's the archimedean solids, where any vertex could be rotated to look like any other (but now the spacing is uneven). Same for any prisms. This only covers even numbers of points. (3 is exempt because it's not a solid) How'd you space 5 symmetrically, though? That sort of puzzles me. - Rainwarrior 20:29, 15 December 2006 (UTC)
I took me a while to find but one example is 5 tetrahedrons - the vertices pointing to the vertices of a dodecahedron (that's why I said objects and not necessarily points) If you want to see this suggest searching for somehting like "tetrahedron inscribed in dodecahedron" example here http://www.uwgb.edu/dutchs/symmetry/polycpd.htm see "Five Tetrahedra in a Dodecahedron" note that if the coloured tetrahedra were the same colour they could not be distinguished from each other.87.102.3.159 22:30, 15 December 2006 (UTC)
If you take equivilent to be vertex-regular you can also get 24, 30, 48, 60, 120 List of uniform polyhedra by vertex figure. Its know that there are no more uniform-polyhedron than these. The Compound of five tetrahedra is closely related to the Dodecahedron both sharing the same set of 12 verticies. There are a few more Polyhedral compounds.--Salix alba (talk) 23:59, 15 December 2006 (UTC)
In 6 dimensions, the 6-simplex (6-dimensional equivalent of a triangle or tetrahedron) has 7 vertices, each of which is equidistant from the other 6 and equidistant from the centre of the figure. Gandalf61 10:11, 16 December 2006 (UTC)

Thanks to all who responded, I sort of knew 7 would be impossible in 3 dimensions, but couldn't prove it.87.102.4.180 11:59, 16 December 2006 (UTC) In fact I still can't prove this - unless by exhuastion - it seems that all the possible symetric shapes have been mentioned.87.102.4.180 13:30, 16 December 2006 (UTC)

Proof can be acheived by considering the uniform polyhedra. Theres a know set of these, you just need to observe that 7 does not divide any of the posible numbers of vertices. Consider the case of the compound of five tetrahedron. Observe 20 (number of verticies on a dodecahedon)=4*5. --Salix alba (talk) 14:20, 16 December 2006 (UTC)

Thanks eveyone.83.100.132.121 18:04, 17 December 2006 (UTC)

[edit] Summation

How do you evaluate something like this (without a calculator):

\sum_{n=0}^\infty\frac{1}{(-2)^n}

--Yanwen 21:59, 15 December 2006 (UTC)

See Geometric progression#Geometric series.  --LambiamTalk 22:25, 15 December 2006 (UTC)

You could start with a chart. Let me demonstrate with a similar problem:

\sum_{n=0}^\infty\frac{1}{(2)^n}

 n  value      sum    decimal sum
==  ======  ========= ===========
 0   1          1       1.000
 1  1/2        3/2      1.500
 2  1/4        7/4      1.750
 3  1/8       15/8      1.875
 4  1/16      31/16     1.934
 5  1/32      63/32     1.969
 6  1/64     127/64     1.984
 7  1/128    255/128    1.992
 8  1/256    511/256    1.996
 9  1/512   1023/512    1.998
10  1/1024  2047/1024   1.999

This makes it pretty clear that we are approaching 2. Of course, this isn't a proof, more formal methods are needed for that. StuRat 07:09, 16 December 2006 (UTC)

...and the values of the first few partial sums may suggest a general formula for the sum of the first m terms. So in StuRat's example, the table suggests the general formula
\sum_{n=0}^m\frac{1}{(2)^n}=2-\frac{1}{(2)^m}
Once you have a conjecture like this, you can try to prove it using, say, proof by induction. Then see what happens as m becomes very large. Gandalf61 10:22, 16 December 2006 (UTC)

[edit] Number of frequent subtrees

For complicated reasons related to the nature of my doctoral thesis, I am confronted with this problem that goes beyond my immediate math skills. Consider a collection of trees - connected, directed, acyclic graphs where every node has an indegree of 0 or 1. Furthermore, every node and edge in the tree collection has a label that forms part of a finite alphabet.

I have learned of an algorithm, of fairly recent vintage, that counts all the embedded subtrees within the collection above a certain frequency threshold. So, using this algorithm, I have written a program that can extract every subtree in the tree collection with a frequency of at least two. The underlying algorithm is called FREQT, and it has a small literature that can be found on the 'Net.

The program, unfortunately, doesn't run very quickly. This algorithm has a worst case run time of O(kbn) where "n" is the number of nodes in the tree collection, "b" is the maximum branching factor, and "k" is the number of frequent subtrees trees extracted.

Question 1: Is there any way to calculate the worst case upper bound runtime of the algorithm without reference to "k" by knowing the maximum number of possible frequent subtrees given a fixed node count and a fixed alphabet size? Is there some way I can replace "k" by more easily calculated variables?

The best I've managed to do is to look at the problem like this: Assume that you have a single tree of size n containing k subtrees, including subtrees with a frequency of 1. Adding an additional node can never more than double the number of subtrees. Ergo, each node added to the tree collection can never more than double the number of subtrees with a frequency above any fixed number. Therefore, the worst case runtime is O(2nbn).

Question 2: Is there some glaring flaw in that logic I ought to know about before I present it at a conference next month?

Anybody out there with enough graph theory to help me out? I'm a linguist by trade, and while I like to think I'm pretty mathematically sophisticated for a linguist, I have never studied graph theory formally.

--Diderot 22:10, 15 December 2006 (UTC)

I would recommend asking computational complexity questions on the computing reference desk. You should find more expertise, and it will provide welcome relief from all the "Windows is broken" traffic there. --KSmrqT 22:32, 15 December 2006 (UTC)
It's not actually a computational complexity problem, although the result is a complexity calculation. What I need to find is an upper bound for the number of frequent subtrees in a tree of size n with nodes labelled from an alphabet of fixed size. Or, failing that, is 2n a valid upper bound estimate?
I took a look at the computer help desk and thought the odds were good that anybody up to the problem over there was also over here. But now that you bring it up, I'll cross-post it to throw fear into the newbies. :^) --Diderot 22:58, 15 December 2006 (UTC)
If you mean subtree the way this notion is usually defined, then each subtree is uniquely defined by the position of its node in the original tree. If there are n nodes in the original tree, it has n subtrees (including the tree itself). --LambiamTalk 23:19, 15 December 2006 (UTC)
I'm assuming that a subtree means a connected subgraph of the tree. That is, unlike what Lambiam suggests, including a node in a subtree does not imply including all its descendants. With that assumption, the 2n bound is valid, but easier to prove than you suggest: any subtree is determined by its set of nodes, there are 2n sets of nodes, QED. And if you don't have a bound on the degree of the nodes in the tree, that bound is close to tight: a star with one root and n-1 leaves has 2n-1+n-1 connected subtrees. I think, though, that for each b there should be some constant (b-1)/b < c < 1 such that a tree with branching factor b has at most 2cn subtrees. But I don't see a simple proof at this point and I'm at a bit of a loss for the right keywords to do a proper literature search. —David Eppstein 07:23, 16 December 2006 (UTC)
Or rather, it's easy to prove that there exists a constant c as above: in any tree, find a maximal set of three-vertex paths; if b is bounded there must be a linear number of paths and each such path can only have seven out of eight possible states. But this will lead to a bound that is much closer to 2n than it needs to be. What seems harder to prove is some formula for the correct value of c (whatever that is). I don't have time for much more now but I found a paper that mentions four more papers (its references [18],[25],[33],[37]) on something to do with numbers of subtrees of bounded degree trees. Of these, the last one has a MathSciNet review (MR2102279) that makes it seem the most likely to be relevant. —David Eppstein 07:53, 16 December 2006 (UTC)
I'm assuming that a subtree means a connected subgraph of the tree. That is, unlike what Lambiam suggests, including a node in a subtree does not imply including all its descendants. - yes. The version of this problem for cases where you are only interested in tress that consist of some node and all its children and their labels is called the bottom-up subtree search problem and can be solved in linear time. This is the embedded subtree problem, which means we're looking at all subtrees that are connected.
I should have seen that the set of sets of nodes was 2n in size. I've been trying to find some way to identify a lower upper bound because it seems intuitively quite obvious that given an upper limit to the branching factor, some far smaller number of uniquely labeled trees must exist.
--Diderot 09:03, 16 December 2006 (UTC)

With some searching I found (sequence A092781 in OEIS). I don't think it's exactly what you want because in it n is the number of leaves while you want it to be the number of nodes. Using the number of nodes instead, I calculated the sequence of maximum numbers of subtrees of n-node binary trees to be

1, 3, 6, 11, 17, 28, 40, 63, 90, 143, 197, 304, 436, 699, 963, 1490, 2147, 3460, 4816, 7527, 10914, 17687, 24461, 38008, 54940, 88803, 124011, 194426, 282443, 458476, 634510, 986577, 1426659, 2306822, 3222182, 5052901, 7341298, 11918091, 16501395, 25668002, 37126259, 60042772, 83875936, 131542263, 191125170, 310290983, 429456797, 667788424, 965702956, 1561532019, 2181194235, 3420518666, 4969674203, 8067985276, 11170879390, 17376667617, 25133902899, 40648373462, 56783422838, 89053521589, 129391145026, 210066391899, 290741638773, 452092132520, 653780249702, 1057156484065, 1476667767793, 2315690335248, 3364468544565, 5462024963198, 7562684275682, 11764002900649, 17015651181856, 27518947744269, 38442376169169, 60289233018968, 87597804081215, 142214946205708, 196832207319982, 306066729548529, 442609882334211, 715696187905574, 999705945699782, 1567725461288197, 2277749855773714, 3697798644744747, 5119948097604531, 7964247003324098, 11519620635473555, 18630367899772468, 26025545054643328, 40815899364385047, 59303842251562194, 96279728025916487, 133255613800270781, 207207385348979368, 299647099784865100, 484526528656636563, 676801134683278875

(Submitted to OEIS; note that every other value in this sequence matches a value in A092781.) It seems to be roughly asymptotic to 0.4×1.5n but there are some oscillations in the asymptotics that I don't understand, even if one ignores the even-odd differences. I don't know whether the 1.5 here is a precise value or instead some other number that is close to 1.5. And I still have no proof that this is an accurate description of the asymptotics, though apparently Szekely and Wang have a proof that the worst-case trees have a certain shape described in their paper from which the other sequence is derived. —David Eppstein 07:43, 17 December 2006 (UTC)

The values (3(n+1)/(2n))^n form an upper bound to this initial segment of the sequence, but get very close – too close for comfort – near the end for values of n that satisfy n ≡ 6 mod 8. --LambiamTalk 16:56, 17 December 2006 (UTC)

Thanks, all. This actually helps a great deal. I can at least use the negative result as an example - I can't offer any useful analytical method to estimate upper bounds. Alas, one of the things it tells me is that since my results are far, far, far below any such upper threshold, I'll have to estimate them empirically. My actual runtime over real world data is something like O(n2), but the variance is unbelievable. I have a lot of additional constraints on search that radically reduce the effective size of the search space, but it's much harder to estimate their effect on order. But, there is one useful thing that comes up - the distribution of subtrees and counts follows a power law distribution given all my added constraints. I should be able to use that to estimate a useful average runtime.

I just can't figure out why the variance in the number of trees I extract is so large. --Diderot 09:47, 18 December 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../r/e/f/Wikipedia%7EReference_desk_Archives_Mathematics_2006_December_15_0efe.html"