George Plya (December 13, 1887 September 7, 1985, in Hungarian Plya Gyrgy) was a Hungarian mathematician.

. He was a professor of mathematics from 1914 to 1940 at ETH Zrich and from 1940 to 1953 at Stanford University. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory. He is also noted for his work in heuristics and mathematics education.

George Plya

George Plya, circa 1973 Born December 13, 1887 Budapest, Austria-Hungary Died September 7, 1985 (aged 97) Palo Alto, California Nationality Hungarian Fields Mathematics Institutions ETH Zrich Stanford University Alma mater Etvs Lornd University Doctoral advisor Lipt Fejr Doctoral students Albert Edrei Albert Pfluger Walter Saxer James J. Stoker Known for Multivariate Plya distribution Plya conjecture Plya enumeration theorem LandauKolmogorov inequality PlyaVinogradov inequality Plya inequality

Life and works

He was born as Plya Gyrgy in Budapest, Austria-Hungary to originally Ashkenazi Jewish parents Anna Deutsch and Jakab Plya who converted to Roman Catholicism in 1886.[1] He was a professor of mathematics from 1914 to 1940 at ETH Zrich in Switzerland and from 1940 to 1953 at Stanford University carrying on as Stanford Professor Emeritus the rest of his life and career. He worked on a great variety of mathematical topics, including series, number theory, mathematical analysis, geometry, algebra, combinatorics, and probability.[2]

Heuristics
In his later days, he spent considerable effort on trying to characterize the methods that people use to solve problems, and to describe how problem-solving should be taught and learned. He wrote four books on the subject: How to Solve It, Mathematical Discovery: On Understanding, Learning, and Teaching Problem Solving; Mathematics and Plausible

Reasoning Volume I: Induction and Analogy in Mathematics, and Mathematics and Plausible Reasoning Volume II: Patterns of Plausible Reasoning. In How to Solve It, Plya provides general heuristics for solving problems of all kinds, not only mathematical ones. The book includes advice for teaching students of mathematics and a mini-encyclopedia of heuristic terms. It was translated into several languages and has sold over a million copies. Russian physicist Zhores I. Alfyorov, (Nobel laureate in 2000) praised it, saying he was very pleased with Plya's famous book. The book is still referred to in mathematical education. Douglas Lenat's Automated Mathematician and Eurisko artificial intelligence programs were inspired by Plya's work. In addition to his works directly addressing problem solving, Plya wrote another short book called Mathematical Methods in Science, based on a 1963 work supported by the National Science Foundation, edited by Leon Bowden, and published by the Mathematical Association of America (MAA) in 1977. As Plya notes in the preface, Professor Bowden carefully followed a tape recording of a course Plya gave several times at Stanford in order to pull a book together. Plya notes in the preface "that the following pages will be useful, yet they should not be regarded as a finished expression." He died in Palo Alto, California, USA.

Legacy
In 1969 the Society for Industrial and Applied Mathematics established the George Plya Prize, given alternately in two categories for "a notable application of combinatorial theory" and for "a notable contribution in another area of interest to George Plya."[3] In 1976 the Mathematical Association of America established the George Plya Award "for articles of expository excellence" published in the College Mathematics Journal.[4] In 1987 the London Mathematical Society established the Plya Prize for "outstanding creativity in, imaginative exposition of, or distinguished contribution to, mathematics within the United Kingdom."[5] A mathematics center has been named in his honor at the University of Idaho in Moscow, Idaho. The mathematics center focuses mainly on tutoring students in the subjects of algebra and calculus.[6]

Multivariate Plya distribution

From Wikipedia, the free encyclopedia The multivariate Plya distribution, named after George Plya, also called the Dirichlet compound multinomial distribution, is a compound probability distribution, where a probability vector p is drawn from a Dirichlet distribution with parameter vector , and a set of discrete samples is drawn from the categorical distribution with probability vector p. The compounding corresponds to a Polya urn scheme. In document classification, for example, the distribution is used to represent probabilities over word counts for different document types.

Probability mass function

We are doing N independent draws from a categorical distribution with K categories. Let x=(n1,n2,...,nK) denote the vector of counts, where nk is the number of times category k was drawn. If the parameter of the categorical distribution is given as p=(p1,p2,...,pK), where pk is the probability to draw value k, the probability distribution for counts, P(x|p) is given by the associated multinomial distribution with parameter p. But now p is not given, but instead considered drawn from a Dirichlet distribution with parameter vector . The resulting compound distribution is obtained by integrating out p:

which results in the following explicit formula:

where is the gamma function, with

Another form
The probability mass function may be written more compactly in terms of the beta function, as follows:

where B is the beta function.

Related distributions
The one-dimensional version of the multivariate Plya distribution is known as the Betabinomial distribution.

Uses
The multivariate Plya distribution is used in automated document classification and clustering, genetics, economy, combat modeling, and quantitative marketing.

Plya conjecture
From Wikipedia, the free encyclopedia

Summatory Liouville function L(n) up to n = 107. The readily visible oscillations are due to the first non-trivial zero of the Riemann zeta function.

Closeup of the summatory Liouville function L(n) in the region where the Plya conjecture fails to hold.

Logarithmic graph of the summatory Liouville function L(n) up to n = 2 109. The green bar shows the failure of the conjecture; the blue curve shows the oscillatory contribution of the first Riemann zero. In number theory, the Plya conjecture stated that 'most' (i.e. more than 50%) of the natural numbers less than any given number have an odd number of prime factors. The conjecture was posited by the Hungarian mathematician George Plya in 1919,[1] and proved false in 1958. The size of the smallest counter-example is often used to show how a conjecture can be true for many numbers, and still be false.

Statement
Plya's conjecture states that for any n (> 1), if we partition the natural numbers less than or equal to n (excluding 0) into those with an odd number of prime factors, and those with an even number of prime factors, then the former set has at least as many members as the latter set. (Repeated prime factors are counted the requisite number of timesthus 24 = 23 31 has 3 + 1 = 4 factors i.e. an even number of factors, while 30 = 2 3 5 has 3 factors, i.e. an odd number of factors.) Equivalently, it can be stated in terms of the summatory Liouville function, the conjecture being that

for all n > 1. Here, (k) = (1)(k) is positive if the number of prime factors of the integer k is even, and is negative if it is odd. The big Omega function counts the total number of prime factors of an integer.

Disproof
Plya's conjecture was disproven by C. B. Haselgrove in 1958. He showed that the conjecture has a counterexample, which he estimated to be around 1.845 10361.[2] An explicit counterexample, of n = 906,180,359 was given by R. Sherman Lehman in 1960;[3] the smallest counterexample is n = 906,150,257, found by Minoru Tanaka in 1980.[4] The Plya conjecture fails to hold for most values of n in the region of 906,150,257 n 906,488,079. In this region, the Liouville function reaches a maximum value of 829 at n = 906,316,571.

Plya enumeration theorem

From Wikipedia, the free encyclopedia The Plya enumeration theorem (PET), also known as the RedfieldPlya Theorem, is a theorem in combinatorics that both follows and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. The theorem was first published by John Howard Redfield in 1927. In 1937 it was independently rediscovered by George Plya, who then greatly popularized the result by applying it to many counting problems, in particular to the enumeration of chemical compounds. The Plya enumeration theorem can also be incorporated into symbolic combinatorics and the theory of combinatorial species.

A simplified, unweighted version

Let X be a finite set and let G be a group of permutations of X (or a finite group that acts on X). The set X can be called an arrangement of beads and G is a chosen group of permutations of the beads. For example, if X is a necklace of n beads in a circle, then G is by definition the cyclic group Cn, while if X is a bracelet of n beads in a circle, then G is by definition the dihedral group Dn. Suppose further that Y is a finite set of colors the colors of the beads so that YX is the set of colored arrangements of beads, and suppose that there are |Y| = t colors. (More formally, a "coloring" is a function .) Then the Plya enumeration theorem counts the number of orbits under G of colored arrangements of beads by the following formula:

Here c(g) is the number of cycles of the group element g as a permutation of X.

The full, weighted version

In the more general and more important version of the theorem, the colors are also weighted in one or more ways, and there could be an infinite number of colors provided that the set of colors has a generating function with finite coefficients. In the univariate case, suppose that

is the generating function of the set of colors, so that there are fn colors of weight n for each n 0. In the multivariate case, the weight of each color is a vector of integers and there is a generating function f(a,b,...) that tabulates the number of colors with each given vector of weights. The enumeration theorem employs another multivariate generating function called the cycle index:

Here the kth weight jk(g) is the number of k-cycles of g as a permutation of X. The theorem then says that the generating function F of colored arrangements is the cycle index, composed with the generating function f of the colors, composed with powers of the variables of f:

To reduce to the simplified version, if there are t colors of weight 0, then

In the celebrated application of counting trees (see below) and acyclic molecules, an arrangement of "colored beads" is actually an arrangement of arrangements, such as branches of a rooted tree. Thus the generating function f for the colors is derived from the generating function F for arrangements, and the Plya enumeration theorem becomes a recursive formula.

Examples
Graphs on three and four vertices
A graph on m vertices can be interpreted as an arrangement of colored beads. The arrangement X is the set of possible edges, while the set of colors Y = {black,white} corresponds to edges that are present (black) or absent (white). The Plya enumeration theorem can be used to calculate the number of graphs up to isomorphism with a fixed number of vertices, or the generating function of these graphs according to the number of edges they have. For the latter purpose, we can say that a black or present edge has weight 1, while an absent or white edge has weight 0. Thus f(t) = 1 + t is the generating function for the set of colors. The relevant symmetry group is G = Sm, the symmetric group on m letters; an isomorphism class of graphs is equivalent to an orbit of graphs under this group. It acts as a subgroup of , the group of permutations of all of the edges.

The 8 graphs on three vertices without quotienting by symmetry are shown at the right. There are four isomorphism class of graphs, also shown at the right.

All graphs on three vertices.

Nonisomorphic graphs on three vertices. The cycle index of the permutation group of the edges is

Thus, according to the enumeration theorem, the generating function of graphs on 3 vertices up to isomorphism is

which simplifies to F(t) = t3 + t2 + t + 1. Thus there is one graph each with 0 to 3 edges.

Isomorphism classes of graphs on four vertices. The cycle index of the edge permutation group for graphs on four vertices is:

Hence

which simplifies to F(t) = t6 + t5 + 2t4 + 3t3 + 2t2 + t + 1. These graphs are shown at the right.

Rooted ternary trees

The set T3 of rooted ternary trees consists of rooted trees where every node has exactly three children (leaves or subtrees). Small ternary trees are shown at right. Note that ternary trees with n vertices are equivalent to trees with n vertices of degree at most 3. In general, rooted trees are isomorphic when one can be obtained from the other by permuting the children of its nodes. In other words, the group that acts on the children of a node is the symmetric group S3. We define the weight of such a ternary tree to be the number of nodes (or non-leaf vertices).

Ternary trees on 0, 1, 2, 3 and 4 vertices. (Leaves not shown except for the tree on zero vertices (green)). We can view a rooted, ternary tree as a recursive object which is either a leaf or three branches which are themselves rooted ternary trees. These branches are equivalent to beads; the cycle index of the symmetric group S3 that acts on them is then

The Polya enumeration theorem then yields a functional equation for the generating function T(x) of the rooted ternary trees:

This is equivalent to the following recurrence formula for the number tn of rooted ternary trees with n nodes: t0 = 1 and

where a, b and c are nonnegative integers. The first few values of tn are 1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (sequence A000598 in OEIS)

Colored cubes

How many ways are there to color the sides of a 3-dimensional cube with t colors, up to rotation of the cube? The rotation group C of the cube acts on the six sides of the cube, which are equivalent to beads. Its cycle index is

Thus there are

colorings.

Proof of theorem
The simplified form of the Plya enumeration theorem follows from Burnside's lemma, which says that the number of orbits of colorings is the average of the number of elements of YX fixed by the permutation g of G over all permutations g. The weighted version of the theorem has essentially the same proof, but with a refined form of Burnside's lemma for weighted enumeration. It is equivalent to apply Burnside's lemma separately to orbits of different weight. For clearer notation, let be the variables of the generating function f of Y. Given a vector of weights , let x denote the corresponding monomial term of f. Applying Burnside's lemma to orbits of weight , the number of orbits of this weight is

where (YX),g is the set of colorings of weight that are also fixed by g. If we then sum over all all possible weights, we obtain

Meanwhile g has a cycle structure

which contributes

to the cycle index of G. The element g fixes an element of YX if and only if it is constant on every cycle q of g. The generating function by weight of a cycle q of |q| identical elements from the set of objects enumerated by f is

It follows that the generating function by weight of the points fixed by g is the product of the above term over all cycles of g, i.e.

which equals

Substituting this for index as claimed.

in the sum over all g yields the substituted cycle

Remez inequality
From Wikipedia, the free encyclopedia (Redirected from Plya inequality) In mathematics, the Remez inequality, discovered by the Ukrainian mathematician Evgeny Yakovlevich Remez (Remez 1936), gives a bound on the sup norms of certain polynomials, the bound being attained by the Chebyshev polynomials.

The inequality
Let be an arbitrary fixed positive number. Define the class of polynomials n() to be those polynomials p of the nth degree for which

on some set of measure 2 contained in the closed interval [1, 1+]. Then the Remez inequality states that

where Tn(x) is the Chebyshev polynomial of degree n, and the supremum norm is taken over the interval [1, 1+]. Observe that Tn is increasing on , hence

The R.i., combined with an estimate on Chebyshev polynomials, implies the following corollary: If J R is a finite interval, and E J is an arbitrary measurable set, then

for any polynomial p of degree n. Here C>0 is a numerical constant.

Extensions
Inequalities similar to (*) have been proved for different classes of functions, and are known as Remez-type inequalities. One important example is Nazarov's inequality for exponential sums (Nazarov 1993): Let

be an exponential sum (with arbitrary k C), and let J R be a finite interval, E J an arbitrary measurable set. Then

where C>0 is a numerical constant. In the special case when k are pure imaginary and integer, and the subset E is itself an interval, the inequality was proved by Pl Turn and is known as Turn's lemma.

Plya inequality
One of the corollaries of the R.i. is the Plya inequality, which was proved by George Plya (Plya 1928), and states that the Lebesgue measure of a sub-level set of a polynomial p of degree n is bounded in terms of the leading coefficient LC(p) as follows: