Can We Prove Better Independence Theorems?

An approach to independence with more complexity dependence

Florian Pelupessy recently defended his PhD thesis at the University of Ghent in Belgium. In joint work with Harvey Friedman, he found new short proofs for two independence results from Peano Arithmetic. One result is the famous “natural” Ramsey-theoretic independence result proved by Jeff Paris and Leo Harrington in 1977, while the other is a different Ramsey-type result obtained in 2010 by Friedman. Pelupessy also maintains a page with links on “phase transitions” in proof theory—meaning cases where a slight change in values of parameters makes a statement go from being provable to independent.

Today I want to talk about whether we can prove that some of our open problems are independent of Peano Arithmetic or other theories.

Subset Powers of Graphs

A possible way to extend the idea of matchings?

source—interesting genealogy

Johann Pfaff was a German mathematician of the late 18th and early 19th century. He is best known for the fact that the determinant of a skew-symmetric matrix (that is, where the transpose equals ) is the square of a polynomial in its entries. Actually it is thought that he did not discover this result. Arthur Cayley named the polynomial after Pfaff posthumously in 1852, having published the result in 1847, while was re-discovered and published by Thomas Muir in 1882. At least the polynomial was not named for Carl Gauss. Perhaps this was because Gauss was Pfaff’s student.

Today Ken and I want to talk about a kind of graph powering that may be new, and that may relate in some cases to Pfaffians.

Measures Are Better

The Littlewood conjecture—another drive you crazy conjecture

John Littlewood is the latter half of famous duo of Hardy-Littlewood. I have discussed him before here and only wish to point out that he was, on his own, one of the great analyst of the last century.

Today I will discuss the Littlewood Conjecture, which has been open now for over eighty years.

Zeno Proof Paradox

Another discussion of paradoxes

src

Zeno of Elea was a Greek philosopher who lived almost 2400 years ago. He is famous for the creation of paradoxes at the juncture of mathematics and the real world.

Today Ken and I want to talk about a type of Zeno paradox.

Interstellar Quantum Computation

Proof from the Chelyabinsk bolide fragment

source

Viktor Grokhovsky is a member of the Russian Academy of Science’s Committee on Meteorites. He is on the faculty of Ural Federal University, and specializes in metallurgy. He has been coordinating the recovery of fragments of the bolide that blazed and exploded over the skies of Chelyabinsk in southern Russia on the morning of February 15th. The largest known piece fell into icy Chebarkul Lake about forty miles southwest of the city.

Today we are delighted to convey findings from metallic crystallographic analysis of the interior of the fragment, and discuss their significance for the reality and propsects of scalable quantum computation.

Happy 100th Birthday, Paul Erdős

Fixing our own Erdős discrepancy

By permission of Fan Chung Graham,  artist.

Paul Erdős—Erdős Pál in Hungarian—would have been 100 this past Tuesday. He was a force of nature, a world stimulant. He popularized his colleague Alfred Rényi’s dictum that “a mathematician is a machine for turning coffee into theorems,” while supplying much of the perpetual motion for the world’s theorem-proving machines himself. His Wikipedia page lists his affiliations after leaving Notre Dame in 1952 as “itinerant,” though he was a regular visitor to several institutions around the world. Although known for long travels, he also experienced the shortest possible transit, from Memphis State University to the University of Memphis in 1994. His frequent collaborator Joel Spencer cited words delivered by Ernst Straus to honor Erdős’ 70th birthday, in 1983:

Just as the “special” problems that [Leonhard] Euler solved pointed the way to analytic and algebraic number theory, topology, combinatorics, function spaces, etc., so the methods and results of Erdős’ work already let us see the outline of great new disciplines, such as combinatorial and probabilistic number theory, combinatorial geometry, probabilistic and transfinite combinatorics and graph theory, as well as many more yet to arise from his ideas.

Today Dick and I would like to join others observing this important anniversary.

Win Five Hundred Or A Million Dollars, By Recursion?

The Erdős discrepancy problem and more

source — in memoriam

Raymond Redheffer was an American mathematician. He worked for his PhD under Norman Levinson, who was famous for his work on the Riemann Hypothesis. Redheffer spent his whole career at UCLA and was a great teacher—see this for more details. Redheffer wrote the mathematical content for the IBM-sponsored 50-foot poster “Men of Modern Mathematics,” which IBM last year released as a free I-Pad app.

Today Ken and I wish to talk about a problem that Gil Kalai spoke last month at Tech, and suggest an approach to solving the problem that draws on a matrix studied by Redheffer.