Wikipedia:Reference desk/Archives/Mathematics/2009 November 13

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

November 13

Cartwright's Theorem

Hi Math Deskers. I got a question this afternoon from my mom asking about the importance and significance of Cartwright's theorem. While we have an article about Mary Cartwright, the information is pretty sparse on what the theorem is and why it is relevant; and the main article is currently redlinked. Is this theorem notable enough for its own article? Can an expert help create that article? Nimur (talk) 00:34, 13 November 2009 (UTC)

See this link, perhaps. --PST 00:55, 13 November 2009 (UTC)

Not being a mathematician, this function theory stuff is a bit dense... what is an analytic and p-valent function and why would it be decomposed in what appears to be a z transform? I think that this is actually defined in the chart linked above, but I'm trying to parse out some meaning from this and need some help understanding the terms. How can the function be multi-valued if it is defined by the series decomposition? Nimur (talk) 02:19, 13 November 2009 (UTC)

An analytic function is (essentially) one that can be written as a power series in z as described. The functions in question are not multi-valued; I'm not sure where you got that idea from. The term "p-valent" is defined in that pdf, immediately below the pictures: it means (essentially) that f takes each value no more than p times on the disc |z|<1. So for example, if f was 2-valent, then we could have f(0)=0 and f(1/2)=0 but not f(i/2)=0 as well. Algebraist 02:30, 13 November 2009 (UTC)

Ah. A crucial point I was missing is that the p-valent definition means f yields the same value, but for a different input, z. I think I got it. Nimur (talk) 14:23, 13 November 2009 (UTC)

finding homomorpisms

My first question is whether there exists an onto homomorphism between S₃ and Z/3? I believe there is none. My second question is how to find all homomorphisms between these two groups. Thanks-Shahab (talk) 06:08, 13 November 2009 (UTC)

Never mind the first question. I am only interested in the second.-Shahab (talk) 06:39, 13 November 2009 (UTC)

Suppose $f:S_{3}\to Z_{3}$ is a non-trivial homomorphism. The image of f must be a subgroup of $Z_{3}$. Lagrange's theorem and the fact that f is non-trivial, implies that f is necessarily surjective.

The following (hidden) question may yield some information about f. If you wish to use the information that I have given you to think about f, you may keep the following question hidden (only click the "show" button if you feel that no further attempts at your question will come to any amount).

(Click the "show" button at the right to see the question or the "hide" button to hide it.)

Does there exist a normal subgroup of S₃ with index three? The kernel of f necessarily satisfies this property.

The answer to the above question is hidden below, in case you want to think about the question first.

(Click the "show" button at the right to see the answer to the above (initially hidden) question or the "hide" button to hide it.)

There are three Sylow 2-subgroups of S₃; the answer is therefore no. In particular, we arrive at a contradiction in assuming that f was non-trivial.

Hope this helps. --PST 07:16, 13 November 2009 (UTC)

By the way, we should consider using the "hide and show feature" for answering questions. It allows us to not only hide the answer, but also parts of the method which the OP might like to work out on his/her own. --PST 07:43, 13 November 2009 (UTC)

Thanks for explaining in this unique way. I had arrived at the conclusion on my own as well by figuring that there are no order 2 normal subgroups and the kernel must be necessarily of order 2 by the 1st isomorphism theorem.-Shahab (talk) 08:44, 13 November 2009 (UTC)

Which concept has the most definitions?

Gian-Carlo Rota wrote on a number of occasions that of all concepts in mathematics, the one with the largest number of characterizations is that of a matroid. But I wonder if the concept of algorithm may be a rival for that distinction? Michael Hardy (talk) 06:30, 13 November 2009 (UTC)

I may not understand your question, but how would you formally define an equivalence between two particular characterizations? --PST 07:46, 13 November 2009 (UTC)

Just that they characterize the same thing. For example:

• a parabola is the set of points in a plane equidistant from the focus and the directrix, or
• a parabola is the graph of a quadratic polynomial, or
• a parabola is the intersection of a right circular cone with a plane parallel to one of the generators of the cone.

Those are equivalent. Any of the three could be taken to be the definition and one would get the same theorems on parabolas.

Rota was saying the list of bullet points one could list for matroid would be larger than for any other mathematical concept. My suspicion is that for algorithm one might be able to make a longer list. Thus an algorithm is

• That which is done by Turing machines, or
• What one does when one evaluates partial recursive functions, or
• any of a long list of other proposed characterizations.

Michael Hardy (talk) 18:18, 13 November 2009 (UTC)

Try duality (mathematics) for a non trivial something that may be more what you want Dmcq (talk) 10:54, 13 November 2009 (UTC)

I wasn't looking for the concept with the most characterizations as much as I was wondering how algorithm would do in that competition. Michael Hardy (talk) 18:22, 13 November 2009 (UTC)

PS: Lately I keep seeing people use "non" as if it were a stand-alone word rather than a prefix. And no longer only within Wikipedia. Have they stopped teaching that there's such a thing as a prefix? Michael Hardy (talk) 18:23, 13 November 2009 (UTC)

At least be glad it's not spelt as "none". Or usually not: a fairly smart hotel near where I live used to have a sign saying that its restaurant was "open to none residents". AndrewWTaylor (talk) 18:53, 13 November 2009 (UTC)

It's not unreasonable to claim that every programming language gives a different characterization of algorithm, which would allow it to beat matroid hands down. Those probably aren't as interestingly different as some of the definitions of matroid are, though. Algebraist 20:30, 13 November 2009 (UTC)

Actually I think algorithm is missing even a single precise definition. Programming languages don't define algorithms; they define programs. An algorithm, whatever it is, is a higher level of abstraction than that. Yiannis Moschovakis has a candidate definition, involving something called recursors, but I was never fully convinced that it succeeds in capturing the informal notion, though this could be because I don't fully understand what informal notion it's trying to capture. --Trovatore (talk) 20:38, 13 November 2009 (UTC)

I doubt there's any clear single answer to the original question, but one concept that has a lot of equivalent-but-not-obviously-equivalent characterizations is that of an amenable group. Another is zero sharp. --Trovatore (talk) 20:55, 13 November 2009 (UTC)

Also, the complex field has a nice carnet of characterizations, including Gelfand-Mazur theorem. --pma (talk) 21:15, 13 November 2009 (UTC)

How does that work as a characterization? It says that the only complex Banach division algebra is the complex numbers, so it uses the complex numbers to characterize themselves. Is it the case, say, that C is the only field K such that K is the only Banach division algebra over K (whatever a Banach algebra over a general field may be)? Algebraist 22:11, 13 November 2009 (UTC)

I had the same objection for a moment, and maybe still now, but in fact I thought that a characterization needn't to be a definition, if we agree that a characterization of X is just a property satisfied by X and only by X. If that property uses the definition of X, it seems to me that it's a characterization as well -but I admit I've never met a precise definition of what a should be characterization . --pma (talk) 11:06, 14 November 2009 (UTC)

That seems a rather perverse notion of characterization. It allows me to use "is C" as a characterization of C. Algebraist 13:36, 14 November 2009 (UTC)

The trivial characterization, why. --pma (talk) 17:49, 14 November 2009 (UTC)

Another example. I suppose you agree that the completion of a metric space is characterized by a certain universal property. But, in the case of the metric completion of Q there is the small detail that we already need R to define what is a metric, so again we are naturally using an object to characterize itself. You may of course save your definition of "characterization" saying that R as codomain of a distance function is not the same of R as metric completion of Q (for the former is an ordered group, and the latter a metric space). But I think it is simpler to agree that a characterization of X is just a property satisfied uniquely by X (with the remark that there are interesting and less interesting characterizations), even because the restricted acceptance of "characterization" makes it synonymous with "definition". --pma (talk) 09:45, 15 November 2009 (UTC)

Sorry misunderstood question. Yes there's certainly a lot of ways of characterizing an algorithm. It's pretty amazing how simple one can make things and still end up with a universal Turing machine or whatever else equivalent is one's main choice. It's more interesting often just to find something that isn't universal like regular expressions. Dmcq (talk) 22:05, 13 November 2009 (UTC)

I am not sure what a "concept" is, but the axiom of choice is the thing for which I know the most equivalent statements. After this, results in Reverse mathematics give large numbers of equivalent ways of axiomatizing various subsystems of second-order arithmetic. — Carl (CBM · talk) 12:59, 14 November 2009 (UTC)

Regarding algorithms, you want to use the word "computable function" instead, since recursion theorists maintain a strange distinction between these. There are dozens of equivalent definitions of the class of computable functions. — Carl (CBM · talk) 13:04, 14 November 2009 (UTC)

There's a clear distinction between algorithms and computable functions: a computable function is just a function that happens to be computable, while an algorithm is an actual way to compute it. For example, natural multiplication is just one function, but there are a great many algorithms for it. Algebraist 13:36, 14 November 2009 (UTC)

Indeed, but there is no accepted definition of what an algorithm is or when two algorithms are "the same", so the literal answer to "how many characterizations of 'algorithm' exist?" is "zero". — Carl (CBM · talk) 15:37, 14 November 2009 (UTC)

Yes, Trovatore pointed that out already. But if you're going to replace "algorithm" with some more precise notion, then "program" seems closer than "computable function" (though closer in the opposite direction: there are many programs for each algorithm, and many algorithms for each function). Algebraist 17:22, 14 November 2009 (UTC)

Then it would not be clear there are multiple definitions for the same thing. I can define what I mean by a C program, and what I mean by a PERL program, but I don't think these count as different characterizations of "programs" because I am talking about a different set of programs in each case. The original question asked for a single class with multiple characterizations; the class of computable partial functions from the natural numbers to themselves is an example of that. — Carl (CBM · talk) 17:46, 14 November 2009 (UTC)

There was a discussion a bit further up about proof identity, the question of when two mathematical proofs are the same. The Curry-Howard correspondence explains that in a sense, proofs (at least in constructive logic) and algorithms are the same thing. So proof identity and algorithm identity are basically the same question. 69.228.171.150 (talk) 01:00, 15 November 2009 (UTC)

Won't that be just the equivalence for algorithms in λ calculus (which is what intuitionistic proofs correspond to under the Curry–Howard isomorphism)? How would it help with algorithms in Prolog or in x86 assembly language? — Carl (CBM · talk) 02:08, 15 November 2009 (UTC)

Hmm, good point. Though, (some meaningful subset of) x86 asm programs correspond to proofs in Hoare logic and I think there are some theorems showing how to interpret Hoare logic in type theory. I guess though that this does not exhaust the entire set of possible x86 programs. For example, there are functions expressible in x86 asm that are provably total, but only by stronger axioms than those of type theory. So type theory could not tell you whether two such algorithms were the same. 69.228.171.150 (talk) 03:24, 15 November 2009 (UTC)

Actually I don't know what to think of the premise. The paper on proof identify that I linked to was mostly about proofs in linear logic rather than intuitionistic logic, but I get the impression that the Curry-Howard isomorphism is still supposed to apply to it somehow. 69.228.171.150 (talk) 03:41, 15 November 2009 (UTC)

• Looking to the very simplest areas of mathematics reveals concepts with numerous characterisations. For example, take multiplication: it can be thought of in terms of a function, an operator, a magma, as the second hyper-operator, and a group, among many others. I'm only an amateur, but I'd have thought simple objects like functions would have the most characterisations. (The mess of the function (mathematics) article is testament to that.) —Anonymous Dissident^Talk 13:57, 14 November 2009 (UTC)

Oh dear, and I put in some effort trying to reorganize that! That'll teach me for complaining about other maths articles. :) Dmcq (talk) 18:26, 18 November 2009 (UTC)

Largest parliament buildings

This may seem too architecture-related for this page, but I am looking for statistics; after much searching on-line, I haven't been able to find a single list of the largest parliament buildings in the world, either by floor space or by volume. I know that the biggest (and heaviest) is the Palace of the Parliament in Bucharest, but I'd like information on at least the top-five to top-ten. If the source is reliable, that would be a bonus. :-) Waltham, The Duke of 07:13, 13 November 2009 (UTC)

You want WP:RD/M, for miscellaneous questions, or maybe WP:RD/H, for humanities. This is WP:RD/MA, for questions about mathematics. 69.228.171.150 (talk) 09:18, 13 November 2009 (UTC)

I would guess that they posted here in case some calculations are needed to determine the volumes. StuRat (talk) 12:15, 13 November 2009 (UTC)

Nobody can say I didn't try... :-) I've mentioned that I've posted here because I seek information of statistical nature, which has nothing to do with artistic criteria, and the Reference desk main page says that the Mathematics section is for "Mathematics, geometry, probability, and statistics". Therefore, I think I am in the right section. If, however, there are further objections to my asking this question here, I'll go to Humanities.

StuRat, asking people to calculate the volumes themselves, even if it weren't an unreasonable request in terms of the time and labour that would have to go into the task, would break our policies on original research. The results might satisfy my own curiosity, but I was hoping to use the information in an article. Waltham, The Duke of 01:55, 15 November 2009 (UTC)

Question about alternating sum of the product of a binomial coefficient and a polynomial function

On the article "Binomial coefficient" here on Wikipedia, what are the proofs for equations 13a, 13b, and 13c? --199.191.74.20 (talk) 16:35, 13 November 2009 (UTC)

There are proof sketches for all of these directly in the article. Did you try to work them out? — Emil J. 16:46, 13 November 2009 (UTC)

BTW, here's the link for convenience: binomial coefficient#Series involving binomial coefficients. — Emil J. 16:48, 13 November 2009 (UTC)

A simple way to see (13a), is observing that for a polymonial P(x) of degree r, the polimomial $P(x)-P(x+1)$ has degree less than or equal to r-1. If you do this operation twice, you get

$\textstyle \left(P(x)-P(x+1)\right)-\left(P(x+1)-P(x+2)\right)=P(x)-2P(x+1)+P(x+2),$

of degree less than or equal to r-2 and so on: the n-th iteration gives (check)

$\sum _{j=0}^{n}(-1)^{j}{\tbinom {n}{j}}P(x+j),$

of degree less than or equal to r-n. So it's necessarily 0 if n>r; in particular for x=0 it gives you (13a).--pma (talk) 21:45, 13 November 2009 (UTC)

One way of proving it is to do this sum on each term of degree m of the polynomial and factor the coefficient out to get:

$\sum _{j=0}^{n}{\tbinom {n}{j}}(n-j)^{m}(-1)^{j}=F(m)$

Notice that that is (n-j)^m. To prove the formulae in question, you can try proving that where the integers m and n $0\leq m\leq n$, where $(n)_{m}$ is the Pochammer symbol representing a falling factorial product, and where $0^{0}=1$,

$F(m)=0^{n-m}(n)_{m}.\qquad (1)$

One way I've seen is to define $[x]^{m}=\sum _{j=0}^{n}{\tbinom {n}{j}}(n-j)^{m}x^{n-j-m}(-1)^{j}$ so that $[1]^{m}=F(m)$; to use the rule that $(n)_{m}(x-1)^{n-m}=\sum _{j=0}^{n}{\tbinom {n}{j}}(n-j)_{m}x^{n-j-m}(-1)^{j}$ (notice the exponent in the first one which didn't have a Pochammer symbol and the Pochammer symbol in the second one); to use the rule that $(x)_{m}=\sum _{i=0}^{m}s(m,i)x^{i}$, where $s(m,i)$ is a Stirling number of the first kind; and to use the rule that $x^{m}=\sum _{i=0}^{m}s(m,i)x^{i}-\sum _{i=0}^{m-1}s(m,i)x^{i}$ (because the mth term of the sum is $x^{m}$).

Now using the rules and definitions above, use strong induction to prove (1). Note that this will be a form of strong induction where there is an upper bound as well as the lower bound of 0, essentially you will use:

1.) Prove that (1) is true for $m=0$.

2.) Next, assuming that (1) is true for $m\in [0,u]$ where $u<n$ (but u is not equal to n), show that (1) is also true for u+1, which can be less than or equal to n.

For both steps, you will start with the function $[x]^{m}$, and use the rules above to get the unexpanded binomial form and you can substitute 1 for x to prove that case for F(m). Using the second step, you know that (1) will result in 0 for all $m\in [0,u]$, so you should start with $[x+1]^{m}$ and use the rules regarding the Stirling numbers to to split $[x+1]^{m}$ into 2 sums, changing the one that can be simplified to the unexpanded binomial form (left) and manipulating the other one (right) so it will contain as a sub-sum something very close to $[x]^{m}$ which will encompass all previous cases from 0 to u. Substitute 1 for x, and watch the one on the right become exactly $[1]^{m}$ and go to 0 for each case due to our inductive hypothesis and the fact that 0 to any power greater than 0 is 0, and watch the left one become $0^{n-(u+1)}(n)_{u+1}$.

If you want me to write it out, then I will. Other than that, I hope I at least gave you a good starting point to prove it on your own using a form of strong induction. --Cornince (talk) 04:22, 14 November 2009 (UTC)

Also, it seems like F(m) would do better in the binomial coefficient article, because it is not specific to polynomials, but showing a general alternating binomial sum. —Preceding unsigned comment added by Cornince (talk • contribs) 04:33, 14 November 2009 (UTC)

And, as I see it, the relevant information that the OP should retain is (1) the expansion $(1+T)^{n}=\sum _{j=0}^{n}{\tbinom {n}{j}}T^{j}$, of course, also holds in any commutative ring, for instance when T is a matrix or a linear endomorphism on a vector space. (2) If $T$ is the translation operator taking the function $f$ to the function $Tf:=f(\cdot +1)$, then $T^{j}f=f(\cdot +j)$, and the the expansion of $(I-T)^{n}$ on a function f evaluated in the point x is

$(I-T)^{n}f\,(x)=\sum _{j=0}^{n}(-1)^{j}{\tbinom {n}{j}}f(x+j).$

Moreover, I-T is a "finite difference operator" (unfortunately often denoted Δ), and (I-T)ⁿ kills polynomials of degree less than n in the same way that the n-th derivative does (see my post above). --pma (talk) 07:53, 14 November 2009 (UTC)

That is true, and makes it a somewhat simpler method than doing it algebraically with induction every time. Still, I understand that some of us like that good hard method. :) We're showing it from different angles. --Cornince (talk) 13:49, 14 November 2009 (UTC)

I'm too among the ones who like hard methods! But in this case, I had the impression that the OP would have liked to start with the simpler things ;) --pma (talk) 18:04, 14 November 2009 (UTC)

edited my post for error correction. --Cornince (talk) 13:49, 14 November 2009 (UTC)