Wikipedia:Reference desk/Mathematics

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Wikipedia Reference Desk covering the topic of mathematics.

Welcome to the mathematics reference desk.
Want a faster answer?

Main page: Help searching Wikipedia

How can I get my question answered?

  • Provide a short header that gives the general topic of the question.
  • Type ~~~~ (four tildes) at the end – this signs and dates your contribution so we know who wrote what and when.
  • Post your question to only one desk.
  • Don't post personal contact information – it will be removed. We'll answer here within a few days.
  • Note:
    • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
    • We don't answer requests for opinions, predictions or debate.
    • We don't do your homework for you, though we’ll help you past the stuck point.

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

  • The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.
See also:
Help desk
Village pump
Help manual

October 14[edit]

October 18[edit]

Norm identity for a normed *-algebra with B*-identity[edit]


I'm trying to show a claim for a normed *-algebra A that is not necessarily unital or commutative but is non-zero and satisfies the B*-identity: ||x^*x||=||x||^2\;\forall x \in A:

||x||=\sup_{||y||\leq 1}\left\{||xy||\right\} for all x\in A.

One direction is trivial; the required property of a normed *-algebra gives:

\sup_{||y||\leq 1}\left\{||xy||\right\}\leq \sup_{||y||\leq 1}\left\{||x||\cdot ||y||\right\}\leq ||x||

But I can't seem to do the other.


Neuroxic (talk) 14:32, 18 October 2014 (UTC)

Are you allowed to use \|x\|=\|x^*\|? If so, try y=x^*/\|x\|. Then \|y\|=1 and \|xy\| = \|x\|, which gives the opposite inequality. Sławomir Biały (talk) 21:13, 18 October 2014 (UTC)
Yes, one can derive that that B* condition implies the involution is isometric. Many thanks!
Neuroxic (talk) 22:45, 18 October 2014 (UTC)

October 19[edit]

Smallest Polymino whose Convex Hull is not tilable...[edit]

What is the Smallest Polymino whose convex Hull is not tilable? is it the quadmino "T", that one has a convex hull with sides 3-1-root2-1-root2? Naraht (talk) 03:00, 19 October 2014 (UTC)

It looks like all the tretrominos have tilable convex hulls. But the convex hull of the Y-pentomino does not tile. It has one side of length √5 and this can only be placed next to another tile which is rotated 180 degrees. When you then try to match the side with length √2, there are two ways but both leave a bay that can't be filled. There are probably other pentominoes as well, I haven't checked them all, but that's enough to answer the question as to the smallest. --RDBury (talk) 07:28, 19 October 2014 (UTC)
PS & correction. Actually the convex hull of the T-tetromino does not tile. When you place a tile next to the side of length √2, there are two ways to do it but both leave a bay that can't be filled. After a bit of doodling I found that the convex hulls of 5 of the 12 pentominoes, Y, F, T, X and W do not tile, while the convex hulls of the remaining 7, I, L, N, V, P, U, Z, do. Perhaps someone could check this as it would probably take more effort than it's worth to turn my doodles into something rigorous. --RDBury (talk) 07:57, 19 October 2014 (UTC)

Real Analysis: Bounded Sequences[edit]

The question I am having trouble with is Prove that sn is bounded where sn=sin(n)/n.

I know I have to use the definition of bounded sequence. I know sin(n) converges and therefore is bounded and 1/n is bounded, but I am not really sure where to go with this. A suggestion about where to begin would be very helpful. — Preceding unsigned comment added by Pinterc (talkcontribs) 13:44, 19 October 2014 (UTC)

sin(n), although bounded, does not converge. The sequence 1/n converges to zero and so is bounded. sin(n)/n is the product of two bounded sequences, so it's bounded. (In fact, you can prove that it converges to zero.) Sławomir Biały (talk) 14:31, 19 October 2014 (UTC)

Is the following elementary proof of Fermat's Last Theorem correct?[edit]

The theorem states there exists no integral (all positive integers) solutions for the equation, 1. x^n+y^n=z^n for n > 2. I begin the proof by assuming there exists an integral (positive integer) solution to equation one for some n > 2. Equation one becomes with some algebraic manipulation, 2. x^n=z^n-y^n = (z^(n/2)+y^(n/2))*(z^(n/2)-y^(n/2)).

Now that I have factored the right side of equation two, Fermat, the great French mathematician and respectable jurist, made I believe the next logical and crucial step. He factored the left side as well, x^n, with the help of an extra real variable, Ɛ, such that 0 < Ɛ < n . I have the following equation, x^n = x^(n/2+Ɛ/2)* x^(n/2-Ɛ/2) = (z^(n/2)+y^(n/2))*(z^(n/2)-y^(n/2) ). This equation implies x^(n/2+Ɛ/2)= z^(n/2)+y^(n/2) and x^(n/2-Ɛ/2) = z^(n/2)-y^(n/2). (Note: The latter two equations are of the form, ab = c + d and a/b = c - d, respectively. And they are quite reasonable given the constraints or parameters of this problem and given the reader has a sufficient understanding of high school algebra.)

And next I have, 3. x^(n/2+Ɛ/2)/ x^(n/2-Ɛ/2) = x^Ɛ = (z^(n/2)+y^(n/2) )/(z^(n/2)-y^(n/2) ). Using equation 3 and applying some algebraic manipulation and simplification to it, I generate the equation, 4. z^n=y^n *((x^Ɛ+1)/(x^Ɛ – 1))^2.

And finally, by combining equations one and four, I generate the following equation after some more algebraic manipulation and simplification, 5. y = (1/4)^(1/n)*(x^(n-Ɛ))^(1/n)*(x^Ɛ – 1)^(2/n).

However, (1/4)^(1/n) is not a rational number, a ratio of two whole numbers, for n > 2. This implies the right side of equation five is not a positive integer. This contradicts my assumption that y is a positive integer. Thus, Fermat’s Last Theorem is true, and Fermat was right! Thank God! Praise God!--David Cole, Primesdegold (talk) 19:59, 19 October 2014 (UTC)

There are several very elementary errors in this proof. Are you a troll, or just an idiot? Sławomir Biały (talk) 20:06, 19 October 2014 (UTC)
WP:AGF. There are many people who think they've proved some open problem in math, and presenting their work here is not necessarily a sign of trolling or idiocy. These questions could just as easily be based in naivety and zeal ;) If anyone wants to help OP find their mistakes, I don't think that's a problem. SemanticMantis (talk) 14:45, 20 October 2014 (UTC)
We should not tolerate trolls like this. I think we should just tell the idiot to go away and bother some other corner of the internet. Sławomir Biały (talk) 15:06, 20 October 2014 (UTC)
If any elementary proof were correct, then it would have been found in the eighteenth century (or Fermat could have written it in the margin in the seventeenth century). Robert McClenon (talk) 15:21, 20 October 2014 (UTC)
I absolutely agree! I once worked in Graduate admissions in the math dept, and we had people claiming to trisect angles in their applications, which is even worse, because that is not merely open, but provably impossible... The unsatisfying thing about this reasoning though, is it ends up being basically an appeal to authority, which is of course not how math really works, and not something we really should rely on when answering questions about math. Though I don't have the time or interest to find errors on these so-called 'proofs', I still think others should be allowed to do so if they wish. Sławomir seems certain this is a troll, but I think a crank need not be a troll. It's a distinction of intent. I try not to ascribe malice to online users where simple ignorance and naivety may provide sufficient explanation. Maybe I'm in the minority, but I see it as our goal here to help educate the naive. SemanticMantis (talk) 15:29, 20 October 2014 (UTC)
First, SemanticMantis is obviously referring to trisection with Euclidean tools, where he or she correctly notes that the construction has been proved impossible. Trisection of an angle is easy if one is not limited to Euclidean tools. Archimedes trisected the angle using an expanded toolset. Doubling a cube is similarly impossible with Euclidean tools and easy with better tools. Squaring the circle is a different, more difficult problem. Robert McClenon (talk) 15:42, 20 October 2014 (UTC)
Second, I agree with SemanticMantis that the OP is not a troll, but an editor whose enthusiasm exceeds his knowledge and his knowledge of the limits of his knowledge. Robert McClenon (talk) 15:42, 20 October 2014 (UTC)
I find it funny that the OP has the skill to carry out some elaborate algebraic manipulations correctly, and yet seems to think that ab=cd implies a=b,\ c=d.
This could be a result of a phenomenon that is all too common among students, of treating math too formally - they learn by rote manipulations and problem solving techniques, but they have no idea what the concepts actually mean. -- Meni Rosenfeld (talk) 05:10, 21 October 2014 (UTC)

Request permission to add a category to the Fractal subheading 'Common techniques for generating fractals'[edit]

If you don't mind, I'd like to add 'Sirsty-Firsty' to the Fractal subheading 'Common techniques for generating fractals'.

Sirsty-Firsty, as in This is a method for generating designs based on moving points around in spirals.

Any thoughts?

Thanks, --InverseSubstance (talk) 22:40, 19 October 2014 (UTC)

That subsection of the article is not about specific software implementations, but general methods. Is the method used in the software that you linked to discussed in the peer reviewed literature? If not, then it should not be added to the article. Sławomir Biały (talk) 12:53, 20 October 2014 (UTC)
You could perhaps add a link in the section Fractal#Fractal-generating_programs. You could also post this question at Talk:Fractal. SemanticMantis (talk) 14:49, 20 October 2014 (UTC)
Is it obvious that these things are fractals? I can't see that it is self evident that these things exhibit an obvious self similarity across all scales. — Preceding unsigned comment added by (talk) 23:25, 21 October 2014 (UTC)
Well that's the question. Sirsty-Firsty is definitely some kind of design generator. It's based on a simple function repeated over and over again. There is a kind of repeating design, only it happens in terms of the color persistence chosen. If an image sums up a persistence of 1,2,4,8,16... then the design would appear repeatedly at the scale of 1,2,4,8,16... Anyway, if this isn't a fractal, maybe someone could suggest what category of computer design it does fit in? Thanks, --InverseSubstance (talk) 06:35, 22 October 2014 (UTC)
Fractals don't have to be self-similar at all scales, that's a popular misconception. They just have to have fractional dimension. Lots of things are fractal but not self-similar. Heck even the very famous Mandelbrot set "in general is not strictly self-similar but it is quasi-self-similar, as small slightly different versions of itself can be found at arbitrarily small scales." I won't go through the details of this linked algorithm, but I don't think it's unreasonable to think that the red colored regions in the example pics constitute a set whose boundary has fractal dimension. SemanticMantis (talk) 15:28, 22 October 2014 (UTC)

October 21[edit]

Importing equations and pictures from Word[edit]

I'm trying to write an article on the Rollett Stability Factor (my father-in-law Dr JM Rollett discovered it by accident in 1962 and we're trying to get the page ready for his 84th birthday in November). I have it all laid out and referenced etc in Word, however I'm finding it impossible to transfer over the very few equations and diagrams that it contains. Is there any kind of simple Cut and Paste or Save As way that will easily allow me to drop them in to the Wiki format?

The macro converter Word2WikiMedia doesn't help.

Would it be better to ask hand it over to an experienced editor or is that not the done thing in the Wiki community? — Preceding unsigned comment added by Jonhuwmac (talkcontribs) 21:48, 21 October 2014 (UTC)

Unless we're talking about dozens of equations, just throw images (or some web-renderable format like Google Docs—not the Word document) up somewhere and any one of many people with LaTeX experience will probably be willing to type it up. --Tardis (talk) 03:10, 22 October 2014 (UTC)
Agreed, and images are probably most fool proof in this case. Something like pandoc might be of some use in general, but MS word is horrible for interoperability of math. The diagrams will certainly have to be pulled out as image files. In theory they could be traced to svg, but that's also a pain and might not help much. SemanticMantis (talk) 15:19, 22 October 2014 (UTC)
Wikipedia allows registered users to set up a sandbox where one can practice rendering mathematical formulas of any kind. I have used it and found the learning curve rather simple. Also in the Help desk one can ask questions with answers usually forthcoming in less than an hour. I have also tried to move math in the other direction from Wikipedia to MS Word and found it impossible. Many distortions ensue. I think MS Word's math tools are full of bugs. --AboutFace 22 (talk) 16:57, 22 October 2014 (UTC)

October 22[edit]

Optimal strategy for moving on a graph[edit]

This problem originates from one aspect of designing a bot for playing the game of Reeelz, but it seems like a general problem that is worth exploring in abstract terms.

I am given a graph G=(V,E), and a set \{R_1, R_2, \ldots, R_m\} of equivalence relations on V. Additionally I am given a function f:V\to\mathbb{R}. In the original application, |V| = n = 11^7 = 19,487,171, every node is connected to k=14 others, the diameter of the graph is 35, there are m=128 relations, and f is roughly on the range [0, 20]. There is additional structure to the graph and relations in this application, but I doubt it is significant.

I then play a game as follows: I am placed at a random vertex in the graph. On every turn I can either:

  • Step: Choose a vertex connected by an edge to the one I am currently in, and move to it.
  • Spin: Choose a relation R_i, and move to a uniformly random vertex in the same equivalence class as the one I am in.

At any point I can stop the game, and my final score will be the value of f at the vertex on which I terminated, minus the number of turns I took. My goal is to maximize my expected score, and the way to do this is of course to reach a vertex which is as good as possible, in as few moves as possible.

The brute force way to solve this is to assign a score to every vertex, and iteratively update the score of every vertex to be the maximum of the vertex's score, the score of every neighbor minus 1, and for every relation, the average score of all equivalent vertices minus 1. It seems obvious to me that this will converge to the correct scores (from which it is easy to figure out the optimal strategy at every vertex), but every iteration is expensive, and it can take many iterations.

Is there a more efficient way to solve it? -- Meni Rosenfeld (talk) 20:49, 22 October 2014 (UTC)

You can try a Branch and boundish approach.
Rough idea: Ignore, for the moment, the second option offered in every turn to jump to a vertex in the same equivalence class. Now, for any vertex in the set V_{20}=\{v:f(v)=20\}, the max score is clearly 20 (and the optimal strategy is to stay there). For any neighboring vertex v', the score is at least \max(f(v'),19). Similarly for the neighbor-of-the-neighbor etc. This will give you lower bounds on the score for each vertex pretty quickly. Similarly the upper bound for any vertex v is the maximum of f(v); the function evaluated for all of its first order neighbors minus 1; the function evaluated for all of its first order neighbors minus 2 etc (Note that you will get rougher, but usable bounds, even if you you use only the p-neighborhood for any vertex, with p<<35, the diameter of the graph)
Now you can introduce back the second option (perhaps introducing only one R_i at a time), and update these lower bound and upper bounds. May still require a few iterations to determine the true expected score for each vertex, but the bounds will help cull the non-productive branches in the decision tree. That culling should hopefully lead to a faster algorithm than the brute force aproach. Abecedare (talk) 21:35, 22 October 2014 (UTC)
Thanks. Well, the first step can be simplified into using Dijkstra's algorithm for finding the exact score for each vertex (without the equivalence class, which I've renamed "Spin" in the OP).
I'm not sure how exactly to find upper bounds with the possibility of spins, or how to use them for pruning without prohibitive overhead. However, your suggestion of introducing one equivalence at a time made me realize that if I do iterations normally but each time consider only the possibility of one random equivalence, I will probably get a much better ratio of (improvement in score estimates / work done). So with ~1000 easy iterations, plus some optimizations related to the specific application, I could get a good approximation with a reasonable amount of computation. -- Meni Rosenfeld (talk) 12:11, 23 October 2014 (UTC)
Yes, I see why the spin complicates the issue of computing useful/non-trivial upper bounds. Btw, approximately how many classes does an R_{i} partition V into, and what is the range of sizes of these classes? Asking because, if the number of classes is say ~10, then the situation seems hopeless and you may just have to accept that Monte Carlo/probabilistic estimates are the best that can be done. But, if instead the class-size is say <10, maybe there is a some clever way out. Abecedare (talk) 14:24, 23 October 2014 (UTC)
For every j, there are \binom{7}{j} equivalences that subdivide V into 11^j classes of 11^{7-j} elements each. So you have 7 relations with 11 classes of 1771561 elements, 7 relations with 1771561 classes of 11 elements, and everything in between.
I may as well add some more detail about the application: V = (\mathbb{Z}_{11})^7. Every relation is identified with a subset of indices, and two elements are equivalent under the relation if their entries in these indices are equal. Two vertices are connected by an edge if their entries are equal in all but one index, and in this index differ by 1.
In fact, for this instantiation of the problem, it is easy to show that it is never a good idea to do a step before a spin: You first do all of your spins, then all of your steps. This can simplify the solution somewhat (you can find the score of every vertex in absence of spins, and then when you reintroduce spins you can ignore the possibility of steps).
Of course, there are many more intricacies when you take into account all of the rules of the particular game, but the basic problem above is a start. -- Meni Rosenfeld (talk) 15:43, 23 October 2014 (UTC)
Numbers bad. Structure good. :)
Question about "for this instantiation of the problem, it is easy to show that it is never a good idea to do a step before a spin". Is this true for any f, or does it have to do with the particular f you are dealing with ? Don't expect you to provide the proof of course; just asking for my own curiosity and to see if I can derive the result in my own head. Abecedare (talk) 16:01, 23 October 2014 (UTC)
It's true for any f.
In fact, for this application you have to run the process for many different fs; that's the main reason I'm looking for a solution as efficient as possible. -- Meni Rosenfeld (talk) 18:03, 23 October 2014 (UTC)

October 23[edit]

Continuous probability distribution, with finite support, and closed-form quantile function[edit]

For some computational experiments, I need a continuous probability distribution, with finite support, and closed-form quantile function. Kindly list any.

I'm already aware of probability distributions that satisfy my requirements except for finite support: Logistic distribution and Gumbel distribution. Thanks! --RM — Preceding unsigned comment added by (talk) 10:45, 23 October 2014 (UTC)

How about the triangular distribution? Sławomir Biały (talk) 10:55, 23 October 2014 (UTC)
Thanks User:Sławomir Biały! I had missed this simple option. Other suggestions are welcome! --BR — Preceding unsigned comment added by (talk) 11:40, 23 October 2014 (UTC)
It doesn't get simpler than the uniform distribution on [0,1]: Q(p) = p. --Mark viking (talk) 11:44, 23 October 2014 (UTC)
There's loads of probability distributions at List of probability distributions but yes having a closed-form quantile restricts the choices. I don't normally consider that as a problem with a computer though as given a function getting a good enough inverse should be easy enough even if only by tabulating values in a table and then doing a binary chop and interpolation for actual values.
I presume you mean on a finite interval rather than finite support which sounds more like on a finite set of points. Dmcq (talk) 13:40, 23 October 2014 (UTC)
Glancing through List of probability distributions#Supported on a bounded interval, the Irwin–Hall distribution, Kumaraswamy distribution, and raised cosine distribution look promising. -- BenRG (talk) 23:32, 23 October 2014 (UTC)

October 24[edit]