Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• 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.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

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:

• Teahouse
• Help desk
• Village pump
• Help manual

December 17

Induction and integration by parts

Consider the proposition P(n):

$\int _{0}^{x}{\frac {f(u)(x-u)^{n}}{n!}}du=\int _{0}^{x}{\Bigg (}\int _{0}^{u_{n}}{\Bigg (}\dots {\Bigg (}\int _{0}^{u_{1}}f(t)dt{\Bigg )}\dots {\Bigg )}du_{n}.$

P(1) was simple enough to prove, but I'm having trouble with the inductive step, P(k) implies P(k + 1). It seems to necessarily involve differentiating something of the form of the original left-hand side. Interestingly, this is possible but long-winded if you expand with the binomial theorem, extract each power of x from the resulting sum of integrals, and apply the fundamental theorem of calculus along with the product rule to differentiate each term of the sum one by one. If I'm not wrong, it is true that

${\frac {d}{dx}}\left[\int _{0}^{x}{\frac {f(u)(x-u)^{n}}{n!}}du\right]=\int _{0}^{x}{\frac {f(u)(x-u)^{n-1}}{(n-1)!}}du,$

which looks deviously simple. My question: is there some easy way of differentiating $\textstyle \int _{0}^{x}g(x,u)du$ without multivariable calculus, or was my example exceptional (or exceptionally clean) for some reason? My observation is that it is only possible because the integral is reducible to something of the form $\textstyle \Sigma \int h(x)k(u)du$; i.e., x and u can be separated sufficiently. This all falls under the general query of how best to pull out the induction; I'd be interested in a more elegant way if one exists. Thanks in advance. —Anonymous Dissident^Talk 12:15, 17 December 2011 (UTC)

I think the whole approach is making too much out of the problem. If you apply another integral to the P(k) case you get

$\int _{0}^{t}\int _{0}^{x}{\frac {f(u)(x-u)^{n}}{n!}}dudx=\int _{0}^{t}\int _{0}^{x}{\Bigg (}\int _{0}^{u_{n}}{\Bigg (}\dots {\Bigg (}\int _{0}^{u_{1}}f(t)dt{\Bigg )}\dots {\Bigg )}du_{n}dx$

and th job is to simplify the lhs. But if you swap the order of integration as in first year calculus the lhs of the P(k+1) pops right out.--RDBury (talk) 16:16, 17 December 2011 (UTC)

I've never learned about swapping order of integration, but I suppose that makes sense and simplifies the induction considerably. I'm still interested in the differentiation question though. —Anonymous Dissident^Talk 00:14, 18 December 2011 (UTC)

I can't help with your actual question, but you may be interested in Fubini's theorem. Perhaps you already know about it - you just mentioned changing the order of integration, and this covers it. IBE (talk) 05:23, 18 December 2011 (UTC)

I'm not sure I do understand this idea about changing the order of integration. I tried to prove my idea of what it means using integration by parts, but failed. Maybe Rdbury could be more explicit about what it means in this context, or how to derive it from integration by parts. —Anonymous Dissident^Talk 11:15, 18 December 2011 (UTC)

I don't want to do an exposition on swapping the order of integration when it should be given in any calculus textbook, so I'll just give this link to a public domain source. Quoting from Leibniz integral rule.

${\frac {d}{d\alpha }}\int _{a(\alpha )}^{b(\alpha )}f(x,\alpha )\,dx={\frac {db(\alpha )}{d\alpha }}\,f(b(\alpha ),\alpha )-{\frac {da(\alpha )}{d\alpha }}\,f(a(\alpha ),\alpha )+\int _{a(\alpha )}^{b(\alpha )}{\frac {\partial }{\partial \alpha }}\,f(x,\alpha )\,dx\,$

which in your case gives

${\frac {d}{dx}}\int _{0}^{x}{\frac {f(u)(x-u)^{n}}{n!}}du={\frac {f(x)(x-x)^{n}}{n!}}-0+\int _{0}^{x}{\frac {f(u)(x-u)^{n-1}}{(n-1)!}}du.$

In other words the formula you gave is valid for integrals from a constant to x when the integrand is 0 at the upper limit of integration.--RDBury (talk) 14:51, 18 December 2011 (UTC)

The following may be already clear and obvious for you; anyway: The iterated integral on the RHS, as a function of $x,$ is an $(n+1)$-th antiderivative $F(x)$ of $f$, $F^{(n+1}(x)=0$ (let's assume $f$ continuous so the fundamental theorem of calculus applies smoothly). Two antiderivatives of a function defined on an interval differ by a constant, and for the same reason, two $(n+1)$-th antiderivatives differ by a polynomial of degree $n.$ This $F(x)$ is precisely the $(n+1)$-th antiderivative of $f$ with $F(0)=F'(0)=\dots F^{(n)}(0)=0$, because we always started the integration from 0. In other words, the $n$-th Taylor polynomial of $F$ is $0$ . So $F(x)$ coincides with its $n$-th remainder $R_{n}(x)$, which is exactly given in integral form on the LH. In conclusion, whether or not you use the Leibnitz integral rule as shown by RDBury, a proof of your identity is essentially the proof of the integral remainder formula itself. For instance: Fix $x$, then, as a function of $u$, $F^{(n+1}(u)(x-u)^{n}/n!$ is exactly the derivative wrto $u$ of the $n$-th Taylor polynomial of $F$ in $x$ centred at $u$ (by direct computation); then the remainder formula follows immediately by the FTC integrating from $0$ to $x$. --pma 09:37, 23 December 2011 (UTC)

December 19

Platonism vs formalism

As no doubt most of you know, in the philosophy of mathematics there is an ongoing debate between formalists and Platonists. I've often wondered whether the following has any relevance. The success of formal systems explains in part the popularity of formalism, but the axioms in any system consist of information. If the system is powerful enough to generate information theory, it must therefore relate back to the information in the axioms, insofar as it provides a mathematical foundation for the amount of information they contain. The ability to define information theory is fairly basic, I think, and at any rate is found in ZFC. It must be impossible to create two incompatible versions of information theory, for otherwise there would be two different ways of reading the information in the axioms. As a result, different systems must still produce the one theory of information. This at least appears to suggest that mathematics is already present before we define axiom systems, because information theory provides a necessary foundation for interpreting axioms in the first place. Can this put a dent in formalism, or is it going too far? IBE (talk) 17:25, 19 December 2011 (UTC)

I don't see why it would be impossible to create two incompatible versions of information theory. Really I don't even understand what that statement means, in any precise way. As Wolfgang Pauli once put it (talking about something else), not only is this not right, it is not even wrong. Looie496 (talk) 17:41, 19 December 2011 (UTC)

A second version of information theory might state, for example, that the wordcount until now for this thread, about 270 words, could be condensed into 5 characters. Of course no such theory is possible, but that's what I'm saying. If you could come up with any other information theory that has theorems that are false as we know them, I would be interested. IBE (talk) 17:55, 19 December 2011 (UTC)

If you can come up with formal criteria for calling a body of statements an "information theory", and a schema for translating those statements into ordinary English (so that we can decide whether they are true), then your problem will be well-specified. Currently it is not. Looie496 (talk) 17:59, 19 December 2011 (UTC)

I confess I should have linked the article information theory, but I did not anticipate the objection. I thought it had clear statements mathematically speaking, and as understood in normal English. I don't know what more is required other than to note that the information contained in a random variable is defined as the expected value of the informativeness of each outcome, which itself equals -log(p); p being its probability. This gives more. Claude Shannon's 1948 paper established the discipline, and I thought until now it was sufficiently rigorous, precise and clear. IBE (talk) 18:22, 19 December 2011 (UTC)

If I had to wager a guess, I'd say that you are confusing what it means to say that axioms contain information (which I imagine to be an informal notion about how well they capture some system- mental or physical) and information in information theory, which has nothing to do with having meaning. Moreover, taken in the most sensible fashion possible, you would at best be talking about applying information theory to a system of axioms, which wouldn't say anything either way about philosophy (if it could say anything about anything). Phoenixia1177 (talk) 22:23, 19 December 2011 (UTC)

I had considered this problem, and I confess it is a genuine one. I believe the best way to show that the claim is nevertheless relevant is as follows. Basically, imagine we have one axiom for a system, that is 100 letters long. Information theory tells us how many bits it contains. Irrespective of its exact meaning, that places limits on what can be expressed in that much space. A bogus information theory, produced by a different 100 letter axiom, might say that all 100 letter axioms can be compressed into one bit. Then it would be saying that either a 1 or a 0 can express each system - for any three axioms, two would be the same. The point is that if it gave any different theory of the amount of information that can be represented in a string of characters, regardless of what those characters were, it would allow different forms of data compression, and hence, using one theory, you could condense the axioms and they would say the same thing, and using another theory, you couldn't. We can read the axioms, and do data compression on computers, so it is a fact of the real world, and presumably can only have one theory of information behind it. IBE (talk) 18:28, 20 December 2011 (UTC)

You're crossing the very blurred edge between science and mathematics. The idea of a "correct" information theory you are using is relating to the idea of what captures information as we humans see information; I'm sure some creative author could think up a world based on some other weird type of information (I can consistently write down rules that allow for languages with 1.38 symbols, I just can't tell you what such a language could be. However, I can half imagine a world where there is some sort of property that, magically, allows such concepts to have application.) Another, better, example of this is with computers: a lot of people think of computers as abstract things that actually obey the rules of boolean logic in their circuits and computation theory is their running; however, they are really a physical system, the correspondence is only an empirical one. Just as we can find out tomorrow that gravity isn't modeled by Riemannian Geometry, so too can we find some goofy circuit that doesn't do as expected by the Boolean stuff; and we would, then, revise our ideas. Now, of course, you might argue that difference here is that you can talk about compression, and what not, being applied to the axioms themselves. However, we are still talking empirically, how do you know what will happen when you compress axioms? We know, inductively, that it should behave like our abstract theory tells us; but, again, nothing forbid there being some physical representation of the axioms that just doesn't do what it should, or some set of axioms and compression that don't actually agree with the theory (this sounds far fetched, but that doesn't mean it is mathematically impossible.)

You could also mean that information theory is correct not based on empirical considerations, but because it works out just right even if done abstractly. However, the problem is that any abstract theory of information using the term compression would have to satisfy basic things if we want it to, again an empirical idea, relate to what we mean by compression. I could just say that any theory of information has a set of maps called compressions that act on strings, nothing forbids this. Indeed, we could do this for every term involved, we might say that entropy is a function such that some properties hold and so forth. So, in this case, saying that our information theory is correct because it works is like saying the integers under addition is the correct group because it adds things up right; or, better, like saying the category of Sets (ZFC) is the correct topos because we can define category theory using set theory. But, that doesn't really work, at the end of the day we just have a bunch of functions with fancy names and meaning we have given to them.

Finally, one could also say that when you apply information theory to a system of axioms, you are really just working with corresponding strings. I'm pretty sure you could redefine language and the meaning of symbols, etc. in a way that would get you different results.Phoenixia1177 (talk) 09:41, 21 December 2011 (UTC)

When you say compression, are you talking about compressing the axioms down to the smallest string that generates the exact same theory? If you mean it in this sense, then this is not information theory, but Logic, and that's a different ball game altogether:-) Phoenixia1177 (talk) 09:44, 21 December 2011 (UTC)

Thanks very much for the help, since it gives me a chance to clarify my thoughts, and see what I'm missing. Basically the last sentence is correct, so I don't totally understand the rest of what you wrote - I think we were talking at cross-purposes there. Yes, information theory and logic are totally different areas, but I am trying to draw a connection between them. The axioms are, no matter what, expressed using information. Consequently, there are rules about how much can be expressed using a particular alphabet and a certain amount of space, so let's say it's just 1s and 0s. Then compression involves maximising entropy for a particular string, or making the bits all independent, and 50% likely to be either a 1 or a 0. If a different set of axioms resulted in a different calculation for the entropy for an expression, there would be a different amount of data that could be represented on my hard drive. Using a set corpus of text (including all the axioms we are interested in), and also using a single algorithm for compression, imagine what happens if we have two different axiom sets in the corpus, producing two incompatible theories of information. They would arrive at different descriptions of how random each bit is, or different descriptions of how much information can be stored in the compressed format. I regard this as a contradiction, although I do not know how to express it as a theorem. I know that means it is not in itself revolutionary, but I have read that mathematicians don't attempt to prove any theorems unless they are already convinced of them on other grounds (intuition or experimentation). I'm saying that such a set of axioms creating a new information theory couldn't exist, because it would affect the description of the axioms themselves. I assume compressed data to still be perfectly valid, even if a human cannot read it. I'm interested in your alternative system, with non-integer numbers of symbols. Is it your own? If not, where can I read more? If so, let me read more here, or on my talk page. IBE (talk) 18:53, 21 December 2011 (UTC)

NB: of course I mean lossless data compression IBE (talk) 18:55, 21 December 2011 (UTC)

The problem is that information theory is "really" just a collection of functions with fancy names that operate on some objects that we call "bit strings". That there are physical systems in our world that happen to correspond to these is empirical, that information theory says anything about your hard drive is a matter of physics, not of mathematics; if electromagnetism worked differently, then that correspondance, probably, wouldn't hold. When we are talking about applying information theory to axioms, we are talking about applying it to strings that can be used to represent the axioms, not the axioms themselves; information theory, if it can be said to actually talk about something conceptual at all, talks about how many alternative things could be expressed, not the content of those things. In a certain sense, what you are saying sounds almost like saying that you couldn't have a theory of geometry in which the shape "R" didn't exist if the axioms used the letter "R", but that wouldn't really be a problem. (What I just said is stupider than what you are talking about, but I think some of the essential ideas are the same; perhaps not all, so please don't take that as an insulting strawman.)Phoenixia1177 (talk) 20:19, 21 December 2011 (UTC)

Now, what I was saying in the last sentence of my last post does not sound like what you are talking about. I was asking if you were talking about "compressing" the axioms into the smallest collection of formulas that say the same thing. However, this would be a matter of logic for two reasons: the idea that two sets of axioms are the same means they entail the same things, this is purely logical, information theory says nothing about the content of the strings; second, there is definitely no algorithm that could do this since there is no algorithm that can tell us if some other axiom set if equivalent to ZFC (suppose there was, then, let P be some wff we want to prove. If ZFC proves P, then ZFC+P = ZFC, and conversely. Hence, given any P; check ZFC+P = ZFC, if yes, declare P a theorem; if not, check ZFC+notP = ZFC, if yes, declare notP a theorem; if not, declare P undecidable. Obviously, no such process exists.)Phoenixia1177 (talk) 20:19, 21 December 2011 (UTC)

If the above doesn't answer your question. Are you talking about information theory in the same sense that someone might point to my above rant about algorithms and say that any axiom system that gave a different theory of computation would have to be wrong because of that? If yes, then that is interesting, but not quite right. The content of the axioms or, at least something with formal strings that acts a lot like the content, can be discussed with computation theory; this is not true of information theory, it would be discussing the names of the axioms. But, in a larger view, the thing about computation theory wouldn't really be right either; we would either be talking about formal objects called "proofs" and "algorithms" or talking philosophically about computation and truth (when I make this distinction I am referring to the exact analogus statement I made, I think there is much much more to discuss in the general case of such statements.)Phoenixia1177 (talk) 20:19, 21 December 2011 (UTC)

I would also like to point out a few random things (I'm not 100% sure I have your intended meaning pinned down, so I want to cover all of the bases.) First, there is no mathematical objects that are "information theories", hence you cannot produce axioms that give a different theory of information; just axioms that give the theory of information; so, on a superficial level, there is no way to define a wrong information theory. Second, relating to the analogy with computation theory in the last paragraph; there are different theories of computation coresponding to other ordinals, if we chose to use another one, I don't think that mathematics would fail; we just wouldn't be able to do it anymore. Third, you might want to look up Skolem's Paradox, "If set theory is consistent, it has a countable model that satisfies, 'There are uncountable sets.'." Interestingly, this is not an actual problem; it is only seemingly a problem when you start to blur the line between statements about set theory and statements of set theory (I think you might be making a mistake along these lines.) Finally, my point about 1.63 symbol alphabets was just that if you muck around with a bit with probability and go around changing integers to 1.63's in information theory, you could do so and avoid contradictions; the problem would be that you couldn't exhibit a 1.63 symbol alphabet, that doesn't mean you couldn't talk about one. The point being that information theory need not refer to any "real" thing, it just happens to because we limit the expressions in a way that makes it (we don't allow 1.63's for the number of symbols becuase that seems kind of stupid to us.)Phoenixia1177 (talk) 20:19, 21 December 2011 (UTC)

I signed each paragraph and indented differently to try and break everything up a little better. If anything sounds terse, or rushed, I find it hard to type well in the edit box and was trying not to take up too much space to say it in.Phoenixia1177 (talk) 20:19, 21 December 2011 (UTC)

By the way (I promise I'll quit yammering) I just wanted to point out, since it seems related, that I am actually a Platonist; I'm just very accepting in my ontology. I don't think that there is a correct "Set Theory", but that every "set theory" we come up with/or really any axiom system just describes some section of the objects that exist; so ZFC+CH and ZFC+~CH both refer to different parts of the universe. On that topic, while some of my above sounds formalist or a rejection of Platonism, I am only saying that I don't think that what we physically call computation needs be an instantiation of "The Theory of Computation" nor do I accept that there is only one such theory. Finally, when I mention "Formal mathematical objects", I don't mean to say that they are just meaningless strings, but that the content we ascribe to the mathematical objects (which I take as real) is not a part of the objects themselves; in other words, I'm meaning that they are formal in so far as relative to meaningful nonmathematical content that we ascribe to the objects. In a sense, we are talking about names of objects, objects, and an intuitive conceptual framework built by mathematicians, somewhere in all of this, I think I come off as sounding like I'm in the opposite camp. At any rate, I think some of this relates back to the original idea of their being a "right" "Information Theory".Phoenixia1177 (talk) 21:09, 21 December 2011 (UTC)

Thanks, that does help overall. Basically, your par 1. is very clever, with the stuff about the letter R - I'll have to have a think about it. Also I always assume good faith, especially when someone spares their time. Par 2: Now I understand you. Par 3: I think this is basically my drift. Par 4: Thanks for suggesting Skolem's paradox. Is there a good book I could read on this? I've done most of Schaum's Set Theory, which covers uncountable sets and so forth, but I haven't done mathematical logic except for its elements. I'm not too dumb (I was usually near the top of university maths units, and have won a couple of prizes in maths competitions) but I can't stand purely cerebral textbooks without questions (I almost certainly need answers as well). This seems to be very much your area, although I'll leave it to you to declare your expertise. As far as the discussion goes, I think I am just extremely resistant to detaching strings from their meaning, more so than you. I agree with most of what you say about Platonism. In fact, I can see no reason why a new claim like the axiom of choice should be proven one way or the other in ZFC, after all, a statement like "Oranges are blue" is neither true nor false in ZFC (though that might be overdoing the point), so I would think without doubt there are two "universes" for each unprovable assertion. All in all, a very interesting and helpful discussion. IBE (talk) 21:23, 21 December 2011 (UTC)

Thank you, I'm happy that I could be helpful:-) As for books, I am unfortunately, not with my book collection at the moment; I won't be until after Christmas, so I only have a limited off my head list of things you might want to check out; none specifically about the Skolem Paradox, though all helpful to thinking on matters like the above. First, I would recommend Computability and Logic by George Boolos, I think its very readable and it covers many good topics. A great book to work through for set theory stuff in general (I think, at least) is Set Theory by Thomas Jech, specifically the first part; there is a book called the Joy of Sets by Devlin that is not that bad, but I'm not the biggest fan of that might worth looking at. A good book that covers a range of topics is A First Course in Logic by Hedman. I'm sure that there are numerous articles and books that I've left out (there's a few I can almost think of). When I get back to my books, I'll look through them and leave a few really good one's on your talk page if you'd like; if you give me an email address, I can send you some resources after Christmas. All of the above, by the way, are textbooks (good ones though, in my opinion); there are also a couple more informal books that would be the worth the read on such topics, as well as a few books on philosophy, I'll give you their names too. Have a great holiday:-) Phoenixia1177 (talk) 05:12, 22 December 2011 (UTC)

December 20

Marcus Hutter versus Yuri Matiyasevich

Marcus Hutter claims to have found an algorithm for all well defined problems, but such an algorithm would be able to ascertain if a given Diophantine equation is solvable, and it could do this for any Diophantine equation. Yet, as Yuri Matiyasevich showed, no such algorithm exists - see Hilbert's tenth problem. How is this contradiction resolved?

At first I thought that it was because Marcus Hutter's algorithm M could only solve problems p for which there exists another algorithm (and could only do so five times slower too, as per the link), and since there is no algorithm for ascertaining if a general Diophantine equation has solutions, M would be unable to do so too. That makes no sense though - for any particular Diophantine equation, there exists an algorithm which can determine if it has solutions - a very trivial one in fact: simply the algorithm which ignores the input and just prints out the correct answer! That would imply that not only could M solve p for any p, but it could do so in constant time (if his claim in the link is correct) but of course this still contradicts Matiyasevich's solution to Hilbert's tenth problem. Widener (talk) 06:17, 20 December 2011 (UTC)

Without reading more than the abstract, it looks like he's only considering algorithms with correctness proofs. While the algorithm for solving a Diophantine equation you describe exists, it lacks (in general) a correctness proof. This just seems to be a particularly efficient dovetailing.--121.74.123.159 (talk) 10:41, 20 December 2011 (UTC)

Statistical test for Gender, Race, and Socioeconomic status (three options) and a three-scale likert

Hi, I was wondering if there is a test for significance to see if Gender, Race, and Socioeconomic status (with 3 options of below poverty, around poverty, and above poverty) all being used a separate IVs cam be seen as having an effect on the DV being the results of a three option likert? What is the best option. Thanks. (By the way n=35 with some responses lacking, I know that isn't the best but the population was already extremely small... --109.66.119.146 (talk) 12:42, 20 December 2011 (UTC))--109.66.119.146 (talk) 12:28, 20 December 2011 (UTC)

The phrase "below poverty" seems odd. "Below the poverty line" is clearer. StuRat (talk) 20:38, 20 December 2011 (UTC)

What you appear to want to know is how correlated is gender to poverty, race to poverty, and socioeconomic status to poverty (and I think you are using socioeconomic status as the name of "poverty status" - which means you only have three variables). It doesn't matter what the values of poverty are. You just want correlation. I'd use a forest plot. It graphically represents how confident you can be that, according to your data, gender is correlated with poverty and/or race is correlated with poverty. SAS, R, and any respectable statistics program (and even Excel, I believe) can produce a forest plot. -- kainaw™ 20:50, 20 December 2011 (UTC)

OP here. Called it below poverty because it is based on an assumption of being below poverty whether one is below the poverty line or not. Also has to do with the fact the data is international and I can't give people one poverty line to work with. Would love to actually see if there is a correlation with the three scale likert (which is called 'positivity index' but I don't think an explanation is needed here). I guess still correlation would be accurate or not, this is where I am not sure.--109.66.119.146 (talk) 07:59, 21 December 2011 (UTC)

I regularly do studies which have factors of race, gender, and poverty. It is all about correlation. For example, hypertension control with medications is heavily correlated with race. When mixing multiple factors, you have to do a multivariate analysis to take all other factors (and combinations of factors) into account. That is why I use SAS. I don't have to do the work. I just supply the data and select the analysis. Even if you don't use complex analysis, you still need to calculate the correlation between each factor. -- kainaw™ 14:20, 21 December 2011 (UTC)

Going between hexagonal and parallelogram tilings

Giving any parallelogram or hexagonal tiling of the plane (where the hexagon has parallel opposite sides, of equal length), we can form a lattice, whose action on the plane produces the torus, with fundamental domain the primitive tile. An induced flat metric can be put on the torus, via the hexagon or parallelogram. However, any lattice in the plane can be uniquely determined by just two vectors, i.e. we may convert any hexagonal lattice into an equivalent parallelogram lattice (producing a torus with the same, flat metric). I can see how to get from a hexagonal tile to a parallelogram tile (by taking three mutually non-adjacent vertices in the hexagon, joining two lines between them, then cutting along these, while gluing opposite sides of the hexagon). However, when I try to pass from a parallelogram tile to a hexagon, I seem to have too many degrees of freedom, so I can't come up with a canonical (up to lattice isometries) hexagonal tile to send it to. Is this possible? It seems like it should be, when thinking about the metrics induced on the torus -- non-equivalent parallelogram (or hexagonal) lattices give rise to different metrics on the torus, so it seems like there should be a bijection between the two sets of lattices/tilings. Any help much appreciated! Icthyos (talk) 12:33, 20 December 2011 (UTC)

In a rather similar problem that I worked on long ago, to go from one lattice to another, I first went to a square grid lattice, then to the other lattice. Mapping to and from squares was much easier because the vectors are based on Euclidean space. The trick is to make the square lattice with smaller tiles (you won't be able to map to them all) so you can easily map back and forth between lattices where the borders don't line up easily. -- kainaw™ 16:09, 20 December 2011 (UTC)

(ec) I'm not sure if this is what you want, but if I got it properly it is enough to mark any point P inside a parallelogram L, join P with lines to arbitrary three vertices of L, and then copy that in all parallelograms... --CiaPan (talk) 16:18, 20 December 2011 (UTC)

That was my approach, except I require that the angles between each pair of lines meeting at P be $2\pi /3$, so my hexagons are always regular . (Edit: I fear I'm talking nonsense, I forgot I'm interested in a particular class of hexagons, which I've just realised are woefully indeterminate at this point. I will do some thinking...) I was just finding it difficult to show that the (finite?) number of points P for which this held, all produced the same hexagonal lattice/tiling (up to isometries) when regluing. I suppose if I could do it for the bog-standard equal sided regular hexagon, then I could argue using something like shear transformations (is there a unique shear transformation mapping one parallelogram to another?) Icthyos (talk) 17:29, 20 December 2011 (UTC)

I'm afraid you can not transform an arbitrary parallelogram onto another one with a shear mapping alone. However, if you compose it with scaling and rotation, then you'll get an (almost) general affine transformation which, of course, allows to map them as you need.
If you manage to transform your parallelogram into squares, then chose the point P in 1/3 of the square'a diagonal and join it to three nearest corners (and copy that over the whole tiling). Then a simple shear of the square by 1/2 of its side makes hexagons regular. HTH. --CiaPan (talk) 19:29, 20 December 2011 (UTC)

Sorry, I should've made clear - I'm really working with equivalence classes of lattices, up to rotation/scaling. It's because I'm actually interested in the (unit volume) flat metrics on the torus, so rotating/scaling are irrelevant. I think I'm getting slightly bogged down in specifics - at the end of the day, all I care is that the metric is flat. It just surprised me that taking a hexagonal lattice, there is a unique (or maybe not, is that my problem?) parallelogram lattice whose action produces the same metric torus, and yet given a parallelogram lattice, there is not a single hexagonal lattice whose action produces the same metric torus (...or is there?) Icthyos (talk) 20:27, 20 December 2011 (UTC)

For the sake of closure: it turns out, I was asking the wrong question. Taking a (fixed) parallelogram tiling, and using CiaPan's approach with the three lines meeting at point P, you get an uncountable number of different hexagonal tilings...but they all give the same hexagonal lattice (given by the two parallelogram vectors, and their sum), which is what is used (not the tiling) to produce the torus and its metric. This is a satisfying resolution. Thanks all! Icthyos (talk) 15:05, 21 December 2011 (UTC)

ZFC being consistent if a proper sub-set of ZFC is consistent

It has already been proved, that there is a proper sub-set A of ZFC, satisfying that - if A is consistent - then ZFC is consistent as well (Of course, A=ZF). Is there any other proper sub-set A of ZFC, satisfying that property? (I don't count the Axiom of Regularity) 77.127.51.217 (talk) 13:04, 20 December 2011 (UTC)

Well, you can certainly take out axioms that are actually proved by other axioms. For example, in the traditional presentation of axioms, the axiom of separation is actually redundant as it follows from the axiom of replacement. Why don't you count the axiom of foundation (btw this is the more usual name than "regularity")? --Trovatore (talk) 19:15, 20 December 2011 (UTC)

I don't count the Axiom of Foundation, because it has already been proved that if ZFC - {Axiom of Foundation} is consistent then ZFC is consistent as well. Anyways, by ZFC I mean: {Axiom of extensionality, Axiom of Union, Axiom of Power set, Axiom of Replacement, Axiom of infinity, Axiom of Choice}. 77.126.184.79 (talk) 23:41, 20 December 2011 (UTC)

The Axiom of replacement is not a single axiom, but an axiom schema. You might be able to select sub-schema from them. Aside from that, the axiom of infinity clearly is needed, as $V_{\omega }$ is a set which is a model of ZFC-infinity. A little more subtly, Power set is clearly needed. I don't know about Union or Extensionality. And, again, obviouly, some form of Replacement is needed, or $V_{\omega _{1}}$ would be a model. — Arthur Rubin (talk) 19:57, 25 December 2011 (UTC)

December 22

Linear Programming and Graph theory

Can someone suggest a good resource (book, or online notes) which I can read to learn about applying linear programming to optimization problems in graph theory? I am currently reading from Schrijver's Combinatorial Optimization but that book is very big (around 2000 pages) and has a lot of other stuff. I am not sure I will be able to wade through all of that. Does someone have any other recommendation? Thanks -Shahab (talk) 04:57, 22 December 2011 (UTC)

Primitive Roots

Given a prime p, which is known to be one more than a power of two, is there an analytic way of finding a primitive root mod p? Thanks. 92.19.236.79 (talk) 21:59, 22 December 2011 (UTC)

The only known primes of the form $2^{n}+1$ for n > 0 are the Fermat primes 3, 5, 17, 257, 65537. Of these, trial and error shows that 2 is a primitive root of 3 and 5, and 3 is a primitive root of 17, 257 and 65537. There is no known simple formula for finding primitive roots in the general case. Gandalf61 (talk) 13:33, 23 December 2011 (UTC)

Thanks. 92.19.231.140 (talk) 14:12, 23 December 2011 (UTC)

You might also want to think about the multiplicative group; the order and structure of that group; the possible orders of the elements of the group; and what the order of a quadratic non-residue might be. Ansatz (talk) 22:24, 23 December 2011 (UTC)

December 23

Help understanding an algorithm

I have to use an algorithm to solve a congruence and am struggling to understand what is going. Could someone please take a look and help me fill in the gaps?

Suppose that p − 1, where p is prime, is a power of 2 and let g be a primitive root mod p, i.e. a generator for the multiplicative group of non-zero residues mod p. To solve the congruence $x^{2}\equiv a{\pmod {p}}$we substitute $x\equiv g^{r}{\pmod {p}}$ where $r=\sum _{j\geq 0}r_{j}2^{j}$ with rj ∈ {0,1}. Raising each side of the original congruence to suitable powers it is possible to solve for the binary digits r0,r1,r2,... in turn. The first step is then listed as being used to determine r_0, whereby r_0 is equal to one if $a^{(p-1)/4}\equiv -1{\pmod {p}}$ or zero if $a^{(p-1)/4}\equiv 1{\pmod {p}}$.

My problem is that I don't see the motivation behind this algorithm. I don't understand how raising each side to appropriate powers gives you any information and I don't see where this expression for r_0 has come from, to name my most clearly defined issues. Thanks. 92.19.231.140 (talk) 14:29, 23 December 2011 (UTC)

As mentioned above, there are only a few primes known that are one more than a power of 2 so the algorithm would have very limited applicability. But in such a case the multiplicative group would be cyclic of order 2ⁿ. We want to find r so g^r=a, raise both sides to the power of 2^n-1. The lhs becomes g^2n-1r₀=(-1)^r₀, and the rhs is ±1. Now raise both sides to the power of 2^n-2 to get g^{2n-1r₁+2n-2r₀}=a2^n-2. If g^2n-2r₀=a2^n-2 then take r₁=0 else r₁=1. At each step if you know last k digits then raise both sides to 2^n-k-1; there are then two choices for the next digit and you can find which one is correct by evaluating. Once you have r, a solution to x²=a is g^r/2, with no solution if r is odd.--RDBury (talk) 15:56, 23 December 2011 (UTC)

That's very instructive, thank you. One question though; after raising both sides to the power 2^n-1, should the rhs not be g^{2n-2r₁+2n-1r₀}? 92.19.231.140 (talk) 17:05, 23 December 2011 (UTC)

Also, just to sum up the algorithm I want to work with, I start with g^r=a. I then raise to the power 2^n-1, giving g^2n-1r₀=(-1)^r₀ = (-1)^r₀, giving r₀ is one if we have minus one and zero if we have one. Then, at each subsequent stage, we raise the previous stage to the power 2^n-k-1 and test whether or not g^2n-k-1r_k-1=a^2n-k-1, taking r_k as zero if they are equal and one otherwise. Have I understood the procedure correctly? 92.19.231.140 (talk) 19:21, 23 December 2011 (UTC)

First question: The rhs would a^2n-1 which is ±1 since if you square it you get 1. Second question, that sound like what I have in mind. It might help to try an example, say p=17 and g=5, a=11.--RDBury (talk) 14:01, 24 December 2011 (UTC)

Tensegrity

What simple shape / construction contains a tensegrity of ten struts? Kittybrewster ☎ 21:53, 23 December 2011 (UTC)

December 24

Duck question?

How many ducks(minimum) is required for following arrangement: 1.there should be 2 ducks in front. 2.there should be 2 ducks in back 3.there should be a duck between two ducks.

dear frens,pls quote your logic in coming to conclusion

-Regards, — Preceding unsigned comment added by Abcappu (talk • contribs) 11:58, 24 December 2011 (UTC)

The meaning of "there should be a duck between two ducks" is not clear. Looie496 (talk) 15:40, 24 December 2011 (UTC)

Google search "two ducks in front behind between" Kittybrewster ☎ 15:47, 24 December 2011 (UTC)

Methinks it is retarded to say "It's amazing how many people got this one wrong" when the question as posed is ambiguous (Yahoo! Answers). Here's what I had pictured:

Duck Duck

Duck

Duck Duck

Didn't realize it was supposed to be single file line. --COVIZAPIBETEFOKY (talk) 16:33, 24 December 2011 (UTC)

The formulation posted here is particularly ambiguous and I wouldn't have thought it allowed three ducks in a row. "2 ducks in front" sounds like they should be equally in front when it isn't said they just both have to be in front of another duck. Many versions elsewhere are less ambiguous but still open to some interpretation. PrimeHunter (talk) 15:31, 25 December 2011 (UTC)

I see it as a single file:

 DUCK DUCK DUCK

The first two are in front, the last two are in back, and the center duck is between two ducks. StuRat (talk) 15:44, 25 December 2011 (UTC)

StuRat: I linked to a page where that was explained already. --COVIZAPIBETEFOKY (talk) 17:49, 25 December 2011 (UTC)

This question is as daft as the ducks that feature in it. 86.179.114.20 (talk) 21:47, 25 December 2011 (UTC)

number of jordan decomposition

let {A} be a set of nxn matrices over F, and let the characteristic polynomial of each element be $(x-a_{1})^{b_{1}}...(x-a_{m})^{b_{m}}$.

Is there a formula for the amount of differnet possible jordan forms for elements of {A}?

If not, is there somewhere in the internet where I can let a computer do this? (enter different polynomials and get the answer without actually doing that work?) --84.228.160.190 (talk) 19:37, 24 December 2011 (UTC)

If A is given then the Jordan normal form is unique so the formula is 1. I think what you meant is that the characteristic polynomial is given and you want the number of possible JNF's for matrices with that polynomial. If the polynomial has the form (x-a)^b then I believe the answer is P(b)=the number of integer partitions of b. In the general case it would be the product of P(b_i) where b_i runs over the exponents in the factorization.--RDBury (talk) 20:58, 24 December 2011 (UTC)

Actually the Jordan form of a given A is unique, up to permutations of its Jordan blocks. --pma 10:04, 25 December 2011 (UTC)

Why is it true?--77.124.235.177 (talk) 19:05, 26 December 2011 (UTC)

December 25

Even numbers among intervals of primes

i conjecture that all even numbers can be found among the intervals of primes. ie, there is no value for n such that p+2n is composite for all p. has this been proven. ther are three stronger possible conjectures

1)the difference between consecutive primes would give all even numbers

2) all even numbers can be found an infinite number of times among theintervals of the primes

3) the difference between consecutive primes would give each even number an infinite number of times

what work has beeen done on any of these. thanks — Preceding unsigned comment added by 86.174.173.187 (talk) 11:48, 25 December 2011 (UTC)

See Polignac's conjecture. Gandalf61 (talk) 13:27, 25 December 2011 (UTC)

The following is only about computational results which prove nothing about larger intervals. If we allow probable primes as gap ends for consecutive primes then 38888 is the smallest even interval with currently no known occurrence in the tables of first known occurrence prime gaps at http://www.trnicely.net/index.html#TPG. My program was first to find many thousands of the intervals and could probably easily fill the hole at 38888 and many later holes. The program found a gap of exactly 100000.[1] Many of my original gaps have since been replaced by gaps by Michiel Jansen and others.

If we demand proven primes then in 2007 I proved all gap ends of all intervals up to 20000 which were listed with probable primes at the time. This proved there is an occurrence of all gaps below 20000. Since 2007 many of the gaps with proven primes have been replaced in the tables by gaps between smaller probable primes. I haven't bothered to prove those.

For intervals between non-consecutive proven primes, in 2004 I found an occurrence for all even intervals up to 10¹².[2] The largest initial prime required for this was 3307 for an interval of 496562420542. PrimeHunter (talk) 15:23, 25 December 2011 (UTC)

As Gandalf61 rightly said: see Polignac's conjecture. — Fly by Night (talk) 00:38, 26 December 2011 (UTC)

it doesnt talk about the other conjectures, or really provide any decent evidence for it. in other words, its a stub.

Arc length in polar form

Why is the arc length formula for a function in (r(θ),θ) form what it is on your page arc length and not simply $\int _{\theta _{0}}^{\theta _{n}}r(\theta )d\theta$? Since the formula for the arc length of a circle through an angle Δθ is rΔθ so shouldn't the arc length of a polar function be as close as desired to r_iΔθ_i through a small enough choice of Δθ_i / fine enough partition of the theta interval? And by adding all these r_iΔθ_i don't we have a normal Riemannian integral of r wrt theta? THanks. 24.92.85.35 (talk) 18:28, 25 December 2011 (UTC)

Your method assumes that r is constant over the interval Δθ, whereas in general it will vary. This cannot be ignored. Your method is a bit like measuring the length of diagonal ramp by approximating it as a staircase and then summing the lengths of all the treads. No matter how tiny you make the steps, you will never get the right answer. 86.179.114.20 (talk) 18:46, 25 December 2011 (UTC)

If you go to the Arc length article and navigate to the Finding arc lengths by integrating section, then you'll find what you need to know. — Fly by Night (talk) 20:20, 25 December 2011 (UTC)

when can we say that we've found the root of an equation?

It's been some days that I've been having a discussion with a friend about a problem: assume we want to solve the equation f(x)=0(and we know what f(x) is). Now if we say x=f^-1(0) have we solved the equation? Well if not, what is its difference with the following solution for the equation below:

x²-2=0

x²=2

x=${\sqrt {2}}$, x=_${\sqrt {2}}$

because if one asks what is ${\sqrt {2}}$, we answer "it's the number whose square is 2", in other words, we really didn't solve the equation, we just chose a symbol for its answer!So this led me to the conclusion that we can only say that we solved an equation if we can present a way to approximate its answer with rational numbers, and that led me to the conclusion that if we can find a way to approximate the answer of an equation(newton's method and stuff like that), we can claim that we solved it (It's the case with ${\sqrt {2}}$ too, we can approximate ${\sqrt {2}}$ with rational numbers).Now since I'm not a mathematician, I know there's got to be something wrong with my conclusion, can anyone explain this subject for me?(and please don't ONLY link Wikipedia articles, I wanna understand it...)--Irrational number (talk) 19:14, 25 December 2011 (UTC)

In a sense it's true that "we just chose a symbol for the answer". There is no way to write sqrt(2) exactly using decimal notation (or any similar notation), so there isn't really any other choice. "solving" an equation normally means representing the answer using some fairly small set of standard operators and functions (which includes the square root function or, more generally, raising numbers to non-integral powers). The sorts of things that are allowed in a "solution" may vary depending on the context, and in more specialised areas new exotic functions may be defined as the root of some equation and then used in further results. Numerical approximations to an answer are fine for practical applications, but mathematically there's a world of difference between a numerical approximation and the mathematically exact answer. 86.179.114.20 (talk) 20:23, 25 December 2011 (UTC)

It's a very interesting idea. Think of a square with sides of length one. It's diagonal will have length √2. Just as there is a number whose square is 25 – namely five – there is a number whose square is two. Just because you can't write it down doesn't mean it doesn't exist. What about π? You can't write that number down, but it is a real number. Take a look at the article Completeness of the real numbers. — Fly by Night (talk) 20:46, 25 December 2011 (UTC)

Perhaps you've solved it when it's in its simplest possible form? so if you don't know fx then you're above solution would work, but if you do, you have to simplify it. — Preceding unsigned comment added by 86.174.173.187 (talk) 21:22, 25 December 2011 (UTC)

http://www.wolframalpha.com/input/?i=x^5%3Dx%2B1 says: x = root of x^5-x-1 near x = 1.1673. That's a nice way of expressing the useless exact solution together with the useful approximate solution. Bo Jacoby (talk) 07:04, 26 December 2011 (UTC).

well my problem is when we ask what is the square root of 25 they say five, but when we ask what is the square root of two, they say it's the square root of two!:D(irrational number)--81.31.188.252 (talk) 07:27, 26 December 2011 (UTC)

Yes, but √2 is just as real of a number as √25. The number √25 is the unique positive number that when multiplied by itself gives 25 as the answer, while √2 is the unique positive number that when multiplied by itself gives 2 as the answer. The only difference is that √25 has a simple form and can be written as 5, while √2 isn't so pretty. To save space, we write √2. Like I said: read Completeness of the real numbers. — Fly by Night (talk) 23:31, 26 December 2011 (UTC)

You have highlighted the difference between the algebraic and the analytic approaches to solving equations. The algebraic approach tells us that there are (at most) two solutions to x²= 2 and that they must sum to 0 (because the coefficient of x is 0). However, it does not tell us anything about where the solutions are in relation to other numbers because "nearness" or "distance" are not algebraic concepts. The analytic approach tells us that one solution can be found between 1 and 2 (because 1² - 2 = -1 and 2² - 2 = 2) and so the other solution must lie between -1 and -2. By convention we call the positive solution ${\sqrt {2}}$ and so the negative solutuon is $-{\sqrt {2}}$.Gandalf61 (talk) 12:05, 26 December 2011 (UTC)

December 26

Confused about complex exponentiation

The article on exponentiation says that, if a, b, and c are complex numbers, then in general, $(a^{b})^{c}/=a^{bc}$. But there are obvious times when the rule does work, like when computing exponentials: eg $i^{i}=(e^{i{\frac {\pi }{2}}})^{i}=e^{(i)(i{\frac {\pi }{2}})}=e^{-{\frac {\pi }{2}}}$. So my questions are, 1) when does the rule work?, and 2) when it does work, why does it work? Is it an axiom, or can it be proven? And final question: does $a^{b+c}=a^{b}a^{c}$ always? Thanks. 65.92.7.9 (talk) 06:09, 26 December 2011 (UTC)

See Exponentiation#Computing complex powers about your 'obvious times when the rule does work'. The problem is that complex exponentiation doesn't have a unique value. It has a generally agreed principal value and that's about it. For the second part the principal value is the same and you don't get any different set of values from either side so in that sense they are equal. Dmcq (talk) 08:31, 26 December 2011 (UTC)

I was assuming the principle value was taken during exponentiation. 65.92.7.9 (talk) 08:48, 26 December 2011 (UTC)

If c is irrational then all is rather simple: The rule $(a^{b})^{c}=a^{bc}$ works, if and only if $-\pi <Im(b\ln(a))\leq \pi$. However, if c is rational, then that's more complicated: The rule $(a^{b})^{c}=a^{bc}$ works, if and only if there is an integer k such that $Im(cb\ln(a))\mod 2\pi =c(Im(b\ln(a))\mod 2\pi )+2k\pi$.

As you see, it's not recommended to use the rule $(a^{b})^{c}=a^{bc}$ in the complex plane, even when referring to the principle values only. However, when referring to the principle values only - you can use the other rule: $a^{b+c}=a^{b}a^{c}$, which directly derives from the very definition of the power function: $a^{1}=a$, and $a^{n}=a^{n-1}*a$, as well as from some trivial holomorphic considerations.

Hope this helps. 87.68.254.218 (talk) 14:14, 26 December 2011 (UTC)

I don't think the article is making the claim that (a^b)^c = a^bc for arbitrary complex numbers. If it was then it would be wrong and I'd fix it but I've gone through the article several times and can't find what the OP is referring to.--RDBury (talk) 13:51, 26 December 2011 (UTC)

The OP hasn't claimed what you think they claimed. On the contrary: they claimed: "The article on exponentiation says that, if a, b, and c are complex numbers, then in general, $(a^{b})^{c}\neq a^{bc}$. But there are obvious times when the rule does work".

I think they just replaced (not on purpose) the sign ≠ by the sign /=. 87.68.254.218 (talk) 14:14, 26 December 2011 (UTC)

You're right, I was misreading it.--RDBury (talk) 19:45, 26 December 2011 (UTC)

December 27

in what way is the sum of all positive integers -1/12

per hardy and ramajamanan. I don't know much math but it's pretty obvoius to me that no amount of positive integers can add up to a negative number. — Preceding unsigned comment added by 80.98.112.4 (talk) 01:45, 27 December 2011 (UTC)

Well, it depends on what sort of addition you have in mind. We have an article on 1 + 2 + 3 + 4 + …. You're certainly correct that, in the usual sense in which infinite sums are interpreted in mathematics, this sum is infinite. --Trovatore (talk) 01:58, 27 December 2011 (UTC)

Right that article doesn't specify the special way/approach under which it isn't. I do understand infinities can be weird, for example in one partcular approach there are as many positive integers as positive and negative integers (1:1, 2:-1, 3:2, 4:-2 and and infinitum) but in another way there is one more positive integer than positive and negative integers: (1: no correspondence, 2:1, 3:-1, 4:2, 5:-2 etc.) it dependa on how you count.

so how can you count sch that you converge on 1/12? 188.156.156.39 (talk) 02:10, 27 December 2011 (UTC)

sorry, not 1/12 (weird enough, since they're all whole numbers and no operation like division is involved, just adding, but it's not even 1/12, but -1/12. how? (under what approach). 188.156.156.39 (talk) 02:14, 27 December 2011 (UTC)

You can't, in the ordinary sense. Any finite subset of the terms has positive sum, and in any usually applied topology, those sums either do not converge on anything, or converge to +∞

However, there is a function called the Riemann zeta function, that in certain parts of the complex plane equals the following sum:

$\zeta (s)=1^{-s}+2^{-s}+3^{-s}+\ldots$

Now, if you substitute −1 in for s, of course the series diverges. However, if you take the function where the series does converge, and travel around the complex plane to get to −1, avoiding poles, you get to the value

$\zeta (-1)={\frac {-1}{12}}$

Now, is this enough to say that the sum is −1/12? In my opinion, no, usually. But there are a few special circumstances where it seems to make sense. --Trovatore (talk) 02:22, 27 December 2011 (UTC)

(edit conflict) By Zeta function regularization. The idea is that the sum $\sum _{n=1}^{\infty }n^{-s}$ defines an analytic function of s. This can be analytically continued to points outside the domain of where the summation makes sense. In particular, the value of its analytic continuation at $s=-1$ is $-1/12$. It's not, however, the same thing as the infinite series $\sum _{n=1}^{\infty }n$, since this properly diverges to infinity. Sławomir Biały (talk) 02:23, 27 December 2011 (UTC)

The thing that really needs to be explained is, why should anyone interpret the sum as an instance of $\sum _{n=1}^{\infty }n^{-s}$ at s=−1, rather than, say, $\sum _{n=1}^{\infty }n^{-{\frac {s}{2}}}{\frac {s^{n}}{(-2)^{n}}}$ at s=−2? I haven't checked but I assume that gives you a different answer. Seems very ad hoc, not remotely natural. The surprising thing is that there are a few contexts, not obviously related, where it seems to be the right answer. --Trovatore (talk) 02:32, 27 December 2011 (UTC)

There's some sense it which the zeta function is the natural regularization from the point of view of Fourier analysis and spectral theory. The zeta function of an elliptic operator A is the trace of the kernel of A^s. (Here A^s is usually already defined by analytic continuation. The trace is regarded in a suitable distribution sense which effectively means that the trace operation commutes with analytic continuation.) The zeta function is natural because it contains most of the asymptotic information of the spectrum (think the prime number theorem). For instance, the Atiyah-Singer index is expressible in terms of zeta functions, and the Wiener–Ikehara theorem describes the asymptotics of the eigenvalues. Sławomir Biały (talk) 13:02, 27 December 2011 (UTC)

What is it called when an irrelevant outcome between 3rd place and 4th place determines who finishes 1st or 2nd?

I took a creative mathematics class back in high school that discussed how in ice skating, that depending on how well (or how badly) the last contestant performs--even if that candidate has no possibility of finishing first or second place--can flip the ranking of other ice skaters. I looked for it on the article Apportionment paradox but I don't know what it is called, or where to begin looking. It's when an athlete indirectly influences the ranking system in bizarre ways, such as if Alex is in first place, Brad is in second place, Charlie is in third place, and if Donald moves from 4th place to 3rd place, then suddenly Brad has more points then Alex. (I think it has to do with competitions which have a running total, and points are awarded based by relative ranking in the component events) I found it fascinating because it is something similar to what's actually happening in a company I do business with regarding how it awards contracting, so any guidance would be tremendously appreciated! Thank you all, 완젬스 (talk) 06:24, 27 December 2011 (UTC)

See Independence of irrelevant alternatives. Additionally, see Arrow's impossibility theorem. 77.125.138.22 (talk) 10:45, 27 December 2011 (UTC)

Yes! Thank you very much, that's it. 완젬스 (talk) 12:31, 27 December 2011 (UTC)

December 28

Optional stopping

Say I want to convince people that I can predict the result of a coin flip to better than 50% accuracy. I set up an experiment where I call heads or tails, flip the coin to determine whether I'm right, and repeat the process. However, I have the right to stop the experiment whenever I want, and if I stop the experiment while I'm ahead, I could get an accuracy higher than 50%.

If I want to get the highest expected percentage accuracy, what is the optimal strategy? Using this strategy, what accuracy can I obtain? What happens if I'm only allowed to stop the experiment after at least 10 coin flips, or after at least N coin flips, where N approaches infinity? --99.237.252.228 (talk) 00:12, 28 December 2011 (UTC)

I would guess that the best approach would be to stop flipping whenever more than 50% of the flips are in your favor. Half the time the first flip should go your way, and, of the half of the times it doesn't, in 1/4 of those you will get the next two flips your way. So, that's 5/8 of the time in your favour with just 3 flips. StuRat (talk) 00:17, 28 December 2011 (UTC)

Don't guess. If you've identified the dynamic, then why not give a general expression and its subsequent conclusion/s? — Fly by Night (talk) 01:22, 28 December 2011 (UTC)

I expect a rapid regression to the mean. Others can do the math. StuRat (talk) 01:31, 28 December 2011 (UTC)

One has to be careful about how to phrase such a question. The expectation value of the accuracy will be 50%, regardless of what optional stopping protocol is used. This is the optional stopping theorem. By implementing a protocol such as the one Stu suggest, you will increase the likelihood of having slightly above average runs at the expense of having some very bad runs as well. In other words, you should not "expect" to look like you are able to predict the outcome of coin tosses. Sławomir Biały (talk) 01:35, 28 December 2011 (UTC)

It doesn't work as a betting strategy, due to the assumption that the bet must be doubled each time you continue. Thus, the few losses cost you as much as the far greater number of wins. However, in this setup, there's no monetary bet to double, so the few losses are not weighted more heavily than the many wins. StuRat (talk) 03:47, 28 December 2011 (UTC)

Again, you missed the nuance in my reply. I indicated that it is true that you can increase the chances of slightly-above-50% runs, but in doing so you both kill some very good runs while not eliminating some very poor runs. This tradeoff ensures that the expectation value of your accuracy remains 50%. Note that the original poster's question was specifically about expected value. Now, the optional stopping theorem states that a martingale stopped at a stopping time is a martingale. In this case, the original martingale is the discrete random walk obtained by computing time-averages of the process $X_{i}=+1$ if the ith toss is heads, $-1$ if it's a tails. Letting $Y_{i}$ be the stopped process. Since $Y$ is a martingale, the expectation value of $Y$ at time $i=0$ is $Y_{0}=0$. So regardless of what protocol you use, you can only have even chances. (A basic meta-axiom of probability is that you can't get something for nothing.) Sławomir Biały (talk) 13:30, 28 December 2011 (UTC)

Two observations.

• There's no strategy that guarantees a win, because there's an infinitesimal but nonzero probability that you'll go below 50% with the first toss and remain below 50% as long as you keep playing
• The only strategy that maximizes the likelihood of a win is to stop playing as soon as more than 50% flips are in your favor, because, if you don't stop, there's an infinitesimal but nonzero chance of losing, as before.--Itinerant1 (talk) 01:45, 28 December 2011 (UTC)

That argument doesn't seem too rigorous. There's no strategy that guarantees a win, but the probability of losing is 0%, so I'm almost certain to win. I'm also not convinced that I should stop after getting at least 50%. There's an infinitesimal chance of losing, but there's a non-infinitesimal chance of increasing my accuracy, so why not continue? --99.237.252.228 (talk) 04:11, 28 December 2011 (UTC)

Is correctly predicting 1 toss out of 1 (100%) deemed better than, for example, correctly predicting 99 tosses out of 100 (99%)? That doesn't seem a very sensible scoring method... 81.159.105.243 (talk) 03:20, 28 December 2011 (UTC)

Yes, it is. That's why I introduced the condition that I can only stop after at least 10 tosses. Also, if my strategy is to always stop after the 1st flip, my expected accuracy would only be 50%, so that doesn't work. --99.237.252.228 (talk) 04:11, 28 December 2011 (UTC)

I wasn't suggesting that the strategy should be to always stop after the first flip. 81.159.105.243 (talk) 13:35, 28 December 2011 (UTC)

I ran some simulations. Here's the results of a run where I stop whenever more than 50% of the tosses have been heads, with no minimum number of flips allowed, and the maximum number allowed listed (I skipped even numbers since those would have lots of ties):

 MAX      WIN 
FLIPS      %
=====  =========  
  1    50.000000
  3    62.500000
  5    68.750000
  7    72.656250
  9    75.390625
 11    77.441406
 13    79.052734
 15    80.361938
 17    81.452942
 19    82.380295
 21    83.181190
 23    83.881973

Here's another run, but this time the minimum number of flips is 11:

 MAX      WIN 
FLIPS      %
=====  =========  
  11   50.000000
  13   55.639648
  15   59.466553
  17   62.361908
  19   64.676094
  21   66.590591
  23   68.213211

So, not only does setting a minimum number of flips mean more flips are required to do better than 50%, it also means that the rate at which the winning percentage grows is reduced from then on. StuRat (talk) 06:22, 28 December 2011 (UTC)

Next I repeated the above runs, but set the goal as winning at least 55% of the flips instead of 50%. Here it is with no minimum number of flips:

 MAX    OVER 55% 
FLIPS  PERCENTAGE
=====  ==========
   1   50.000000
   3   62.500000
   5   68.750000
   7   72.656250
   9   75.390625
  11   75.390625
  13   76.416016
  15   77.478027
  17   78.462219
  19   79.352188
  21   79.752640
  23   80.213654

And here it is with the minimum number of flips set to 11:

 MAX    OVER 55% 
FLIPS  PERCENTAGE
=====  ========== 
  11   27.441406
  13   38.720703
  15   44.360352
  17   48.388672
  19   51.548386
  21   52.846050
  23   54.267372

As you can see, if you want a higher percentage of heads, it requires more flips. If you actually wanted to do this for real, the time it takes to do all these flips would soon become a serious constraint. You could probably get 99% of the flips to be heads every time, except that the coin flipping would be interrupted by the death of the universe. In other words, the optimal strategy is entirely dependent on how much time you have. StuRat (talk) 06:35, 28 December 2011 (UTC)

(i) Is your "WIN %" measuring the probability that 50% heads was exceeded at any point? Is that what the question asked? I thought it was asking about the expected proportion of correct predictions in the run. (ii) I'm not sure about "You could probably get 99% of the flips to be heads every time", if I'm understanding it correctly. Any given surplus of heads over tails (or vice versa), however large, is certain to be achieved (in the "probability tends to one" sense) if we continue long enough, but is the same true for proportions? If we continue long enough, are we guaranteed to always eventually achieve 99% heads? It sounds very unlikely to me. In fact, it is not at all obvious to me that we are always guaranteed to even achieve 50.000001%. (iii) It seems plausible to me that the optimum strategy is to always stop if the number of heads is one more than the number of tails, but I don't think that has been anything like proved so far in this thread. (Note: in case not obvious, I'm using "heads" synonymously with "successful predictions" because we may assume that you always predict heads, since it makes no difference what you predict.) 81.159.105.243 (talk) 13:34, 28 December 2011 (UTC)

Let me make this very black and white: There is no optimal strategy that will maximize the expected proportion of heads to tails. This is a mathematical theorem. If you don't believe mathematics, trust casinos: go play roulette and bet $1 on black each time. You think you can expect to beat the house? Sławomir Biały (talk) 13:52, 28 December 2011 (UTC)

It's always possible to get ahead if you go on for long enough, in the sense that the probability of doing so tends to one. It may not be practical because you may have to go on playing for years (potentially even millions of years). 81.159.105.243 (talk) 14:02, 28 December 2011 (UTC)

But your question is not about the probability of exceeding 50%. It's about expected value. The probability of exceeding 50% can approach 1 while the expected value remains the same. This has nothing to do with practicality. There are some very poor runs in the tail of the distribution that average out with the modest slightly-above-50% runs. See my replies above. Sławomir Biały (talk) 14:06, 28 December 2011 (UTC)

See also Gambler's ruin. Sławomir Biały (talk) 14:14, 28 December 2011 (UTC)

Actually it's not my question (I'm not the OP). But, as I understand it, the question is about when to stop so as to maximise one's proportion of successful predictions. If we go on long enough, we are "certain", in the appropriate probabilistic sense, to reach the point where the number of successes exceeds the number of failures by one. Clearly it is advantageous* to continue to that point if we have not yet reached it. We next need to show (assuming it's true) that it is never advantageous to continue beyond that -- even though, if we continue, we are "certain" to eventually reach the point where our successes outnumber our failures by any stated fixed (i.e. not proportional) amount. 81.159.105.243 (talk) 14:24, 28 December 2011 (UTC) *advantageous in principle, but not necessarily in real life, since we don't have an indefinite amount of time...

In the original post, the game is stopped after a large number N. The expected proportion of heads (regardless of the stopping protocol) is 50%, even if the probability of being less than this is very small. (There is a difference between expected value and probability.) Now let N tend to infinity. Sławomir Biały (talk) 14:47, 28 December 2011 (UTC)

I'm envisaging that we do not stop tossing until we are are one ahead, so your "poor runs in the tail of the distribution" simply never happen to even out the expectation. Perhaps the legitimacy of that is more of a philosophical question? Actually, though, there are possibly some more prosaic quirks thrown up by this "highest expected percentage accuracy" measurement. Suppose our strategy is to (always guess heads and) stop if the first toss is heads, otherwise continue for two more tosses. Unless I have just made some silly mistake, this gives 1/2 chance of 100% accuracy, 1/8 chance of 2/3 accuracy, 1/4 chance of 1/3 accuracy and 1/8 chance of 0 accuracy, for an "expected" accuracy of 2/3 -- even though obviously we cannot make money at roulette this way! Is that how we're meant to calculate it? 81.159.105.243 (talk) 15:22, 28 December 2011 (UTC)

Good point. Sławomir Biały (talk) 15:33, 28 December 2011 (UTC)

in an infinite amount of time you will get any possible percentage, so you could stop whenever you have some arbitrarily high percentage. — Preceding unsigned comment added by 86.174.173.187 (talk) 15:35, 28 December 2011 (UTC)

Is there an algorithm which - for every first-order proposition (with identity and predicate symbols) - determines whether that propostion is consistent?

77.124.12.169 (talk) 10:22, 28 December 2011 (UTC)

Consistent with what?

But, basically, no, whatever you might mean, even if you just mean "consistent with itself". A proposition "inconsistent with itself" would be the negation of a logical validity, and if there were an algorithm to determine whether the negation of a sentence is a validity, then there would also be one to determine if a sentence is a validity, and there isn't. --Trovatore (talk) 10:27, 28 December 2011 (UTC)

Yes, consistent with itself. 77.124.12.169 (talk) 11:17, 28 December 2011 (UTC)

Is there an algorithm which - for every consistent first-order proposition (with identity and predicate symbols) - determines that the propostion is consistent?

77.124.12.169 (talk) 11:16, 28 December 2011 (UTC)

Is there an algorithm which - for every inconsistent first-order proposition (with identity and predicate symbols) - determines that the propostion is inconsistent?

77.124.12.169 (talk) 11:16, 28 December 2011 (UTC)

betting game

we throw a dice. if i get a 1 i lose all my money, but if i get a any other number i double my money. the laws of probability suggest that i should always continue playing as it is more likely i will gain then lose. yet obviously i will eventually get a 1 and lose all my money. i assume this is a case of gamblers ruin. so whats the best strategy? — Preceding unsigned comment added by 86.174.173.187 (talk) 15:39, 28 December 2011 (UTC)

This is a variant of the St. Petersburg paradox. The game has infinite expectation value, yet at some point it is absurd to continue playing. Sławomir Biały (talk) 16:14, 28 December 2011 (UTC)

mathematically though the st petersburg paradox makes sense to pay any value for. mathamatically here it is stupid to continue playing indefinately. anyway the solutions to the st petersburg dont help here. — Preceding unsigned comment added by 86.174.173.187 (talk) 17:50, 28 December 2011 (UTC)

Why is it "mathematically" stupid to continue playing indefinitely? You have a 5/6 chance of doubling your money with no risk but your initial investment. Surely "mathematically" the most rational thing to do is to continue playing the game. Actually, you would probably want to sell shares in this game. This hedges some of your own risk. Sławomir Biały (talk) 19:30, 28 December 2011 (UTC)