User i. j. kennedy - MathOverflow

What Are Some Naturally-Occurring High-Degree Polynomials?

2010-06-07T07:24:38Z

To construct J. H. Conway's look-and-say sequence, begin by putting down a 1 as the first entry. The other entries are found by saying the previous entry aloud, and writing what you hear.

1
11
21
1211
111221
312211  (previous entry was three 1's, two 2's and one 1)
...

Conway provides his usual fantastical analysis in The Weird and Wonderful Chemistry of Audioactive Decay [Eureka 46, 5-18], where he demonstrates several otherworldly properties of this sequence. One was this: the ratio of the lengths of consecutive entries has a limit, $\lambda$. Furthermore, $\lambda$ is the root of a polynomial of degree 71.

Now, when I was in high school we were taught the quadratic formula and told there is a cubic formula, but you don't have to learn it. Why? "You won't be needing it." And mostly I've found that to be true. Am I wrong, or do high-degree polynomials rarely occur (in uncontrived settings)?

What are some other examples of useful roots of polynomials of high degree? Power series and the like can obviously produce useful polynomials of arbitrarily large degree, but I'm looking for surprises such as the degree-71 polynomial at the heart of the look-and-say sequence above.

Have any long-suspected irrational numbers turned out to be rational?

2010-07-22T16:06:17Z

The history of proving numbers irrational is full of interesting stories, from the ancient proofs for $\sqrt{2}$, to Lambert's irrationality proof for $\pi$, to Roger Apéry's surprise demonstration that $\zeta(3)$ is irrational in 1979.

There are many numbers that seem to be waiting in the wings to have their irrationality status resolved. Famous examples are $\pi+e$, $2^e$, $\pi^{\sqrt 2}$, and the Euler–Mascheroni constant $\gamma$. Correct me if I'm wrong, but wouldn't most mathematicians find it a great deal more surprising if any of these numbers turned out to be rational rather than irrational?

Are there examples of numbers that, while their status was unknown, were "assumed" to be irrational, but eventually shown to be rational?

Answer by I. J. Kennedy for Examples of theorems misapplied to non-mathematical contexts

2012-02-24T02:17:28Z

"Therefore, socialist economy is impossible, in every sense of the word."

Robert Murphy comes to this conclusion in Cantor’s Diagonal Argument: An Extension to the Socialist Calculation Debate.

The debate is over whether a Central Planning Board can, even in theory, correctly price goods and services, as it is assumed a market economy can. Socialists such as Dickinson argued that a market economy can, in principle, be simulated by the Board, even if it means solving a large system of simultaneous equations. Hayek, on behalf of the Austrians, agreed, yet maintained the number of equations--presumably one for each product and potential product--is clearly too large in practice. Both sides claimed victory.

In the cited article, the author takes the ball from Hayek and carries it across the goal line: after a decent three-page explanation of the diagonal argument, Murphy concludes the Planning Board’s task would not merely be impractical, but fully impossible because of the requirement to publish an uncountably infinite list of prices.

I suppose if one started with the assumption there are (at least) countably infinite number of products/services $p_1, p_2, \dots$ and also agreed that any possible subset of these products is again a product itself, the price of which is not necessarily the sum of the component prices (let’s ignore issues of convergence!), then one could conclude using Cantor’s Theorem ($2^S>S$) there are an uncountable number of products the Board must “list”. But I’m not sure why, if we take the listing process literally, it matters how large the infinity is.

Answer by I. J. Kennedy for Strengthening the Induction Hypothesis

2012-03-24T20:37:46Z

Here's a simple example I found in Mathematical Miniatures.

$\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} < \frac{1}{\sqrt{3n}}$

The induction step comes down to wanting $$\frac{2n+1}{2(n+1)} < \frac{\sqrt{3n}}{\sqrt{3(n+1)}}$$

which unfortunately is not true. However if the induction hypothesis is slightly strengthened to

$\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} \le \frac{1}{\sqrt{3n+1}}$

the induction runs smoothly.

By the way, it's mentioned in the book that Pólya refers to this phenomenon of strengthening the induction hypothesis as "the researcher's paradox", although it doesn't seem the phrase has caught on.

Is there a symmetry group lurking behind every WLOG?

2012-01-20T01:39:14Z

Most of us are introduced to "without loss of generality" before encountering formal group theory. To the uninitiated, the phrase almost seems like cheating, but soon we realize how intuitive and useful it is for simplifying and shortening proofs.

Perhaps this is a dumb question (in the sense that the answer might well be obvious), but is it true that behind every WLOG there is an implied symmetry group in play?

A Couple of Examples

(Schur's Inequality) If $a,b,c \ge 0 $ and $r \ge 1$, then$$a^r(a-b)(a-c) + b^r(b-a)(b-c) + c^r(c-a)(c-b) \ge 0$$

Proof: Without loss of generality, assume $a \ge b \ge c$...
We can do this because the expression at hand is symmetric in $a,b,c$.
The group is $S_3$.

(Fundamental Theorem of Algebra) Every $n^{th}$-degree polynomial $a_n z^n + a_{n-1}z^{n-1} + \dots + a_1 z + a_0$ has a root in $\mathbb{C}$.

Proof: Without loss of generality, assume $a_n = 1$, because we can "divide through" by $a_n$...
The group is $\mathbb{R}- 0$ under multiplication.

Answer by I. J. Kennedy for Volumes of n-balls: what is so special about n=5?

2011-10-22T17:22:40Z

Brian Hayes has very nice article about the volume of the n-ball in the current issue of American Scientist (Nov 2011). In particular, he discusses the surprising fact that the maximum volume occurs at $n=5$.

Is there a closed form for this hypergeometric expression?

2010-07-14T03:38:56Z

I am trying to compute the number of distinct ways a $4n$ $\times$ $4n$ chessboard can be colored black and white, with exactly half the squares black and half the squares white. By distinct, I mean not equivalent by rotation or reflection, i.e. with respect to the dihedral group $D_4$.

Of course I wouldn't be too surprised if this has already been computed and the answer already known, but calculating a few terms and looking them up in OEIS didn't lead to anything. FYI, the first three terms are 1674, 229078019084673798, and 185026624806098273753009169783707528668060, corresponding to board sizes of 4$\times$4, 8$\times$8, and 12$\times$12.

Using Burnside and simplifying I've got it down to

$$\frac{1}{8} \left[2 {4 n^2 \choose 2 n^2}+3 {8 n^2 \choose 4 n^2}+{16 n^2 \choose 8 n^2} + 2 \sum _{k=0}^{2 n} {4 n \choose 2 k} {8 n^2-2 n \choose 4 n^2-k}\right]$$ and you can probably guess I would like a closed form for the sum.

With a little research and some help from Mathematica, the sum simplifies to
$$ \frac{(8n^2-2n)!}{(4n^2)!(4n^2-2n)!} \ {}_ {3}F_ 2\biggl(\begin{matrix} \frac{1}{2}-2n,\ -2n,\ -4n^2 \cr \frac{1}{2},\ 4n^2-2n+1\end{matrix};-1\biggr)$$

I know little about hypergeometric functions but apparently some special cases are reducible to closed forms. My question is this, then: Does this particular hypergeometric expression have a closed form? And more generally, is there something akin to a table of integrals where I could look up something like this?

Clarification: Although my sequence does not appear in OEIS, it does appear as a subsequence of A0892963, where two of three terms I computed are given. Unfortunately there is no formula given, closed or otherwise; nor is there any generating function mentioned, nor references cited. This is what I meant by my lookup in OEIS not leading to anything. Sorry to those I confused with my remark. The only reason I mentioned OEIS in the first place was to spare those kind enough to take interest in my question the time of looking there.

Are some numbers more irrational than others?

2011-01-29T16:11:17Z

Some irrational numbers are transcendental, which makes them in some sense "more irrational" than algebraic numbers. There are also numbers, such as the golden ratio $\varphi$, which are poorly approximable by rationals. But I wonder if there is another sense in which one number is more irrational than another.

Consider the following well known irrationals: $\sqrt{2}$, $\varphi$, $\log_2{3}$, $e$, $\pi$, $\zeta(3)$.

The proofs of irrationality of these numbers increase in difficulty from grade-school arguments, to calculus, to advanced methods. Other probable irrationals such as $\gamma$ most likely have very difficult proofs.

Can this notion be made precise? Is there a well defined way in which, for example, $\pi$ is more irrational than $e?$

Answer by I. J. Kennedy for Sexy vacuity ....

2010-11-15T01:21:36Z

If you've ever written code to convert an integer into a string of decimal digits, you may have come to the conclusion that the integer 0 should map not to the string 0, but to the empty string instead. Most algorithms I've seen need to introduce a kludge to make 0 come out right. After all, when we write 0 we are violating the usual rule of "no leading zeros".

A nice, natural recursive expression of the conversion process is

def itoa(n):
  if n==0: return ""
  return itoa(n/10) + chr(ord('0') + n%10)

which can be thought of as
The string representation of an integer consists of its leading digits (n/10) followed by its last digit (n%10).

Trying to fix this by returning "0" instead of "" would result in everything getting a superfluous leading zero.

On the other hand writing 0 as the empty string would be rather annoying.

Answer by I. J. Kennedy for Generalizing a problem to make it easier

2010-11-10T07:09:19Z

Sometime around 25 years ago, Dr. Jeffrey Vaaler at UT Austin gave me the following problem.. He needed the result as a lemma for a paper he was working on.

Let $n$ be a square-free integer with $k$ distinct prime factors and thus $\sigma(n) = 2^k$ divisors. Split the divisors into two sets of equal size: the small divisors $S$ and the large divisors $T$. The statement he was trying to prove was: $$\text{There exists a bijection}\ f: S \rightarrow T \hspace{2mm} \text{such that} \hspace{2mm} d \hspace{1mm} | \hspace{1mm} f(d) \hspace{2mm} \text{for every} \hspace{2mm} d \in S.$$ I was an undergraduate and highly motivated to demonstrate my usefulness, but I didn't really have many ideas about how to go about it. The obvious approach is by induction on $k$, but I never really got anywhere despite spending many hours on the problem.

A year later I ran into Dr. Vaaler in the hall and asked if he ever solved it. Of course, he had, by induction on $k$. He went on to explain the "trick" to making the induction work. He proved a more general result. Introduce a parameter $0 \le r \le \frac{1}{2}$ and consider $S_r$ and $T_r$, the smallest $\lfloor r \cdot 2^k \rfloor$ divisors and the largest $\lfloor r \cdot 2^k \rfloor$ divisors respectively, and instead prove the above statement with $S_r$ and $T_r$ in place of $S$ and $T$.

The lemma is then the special case with $r = \frac{1}{2}$.

This example stuck with me. How could it be easier to prove something more general? Though I understand the concept better today, it still surprises me.

Answer by I. J. Kennedy for Most helpful math resources on the web

2010-10-27T01:35:55Z

http://functions.wolfram.com/

Is Fürstenberg's topology useful?

2010-10-18T06:32:29Z

It's hard not to be amused and perhaps even amazed when first encountering Fürstenberg's clever "topological" proof that there are infinitely many primes. Closer inspection, however, reveals the disappointing truth that there really isn't anything topological going on there, as pointed out by BCnrd in a comment to this answer.

Nevertheless, the topology on $\mathbb{Z}$ introduced in the proof, where an open set is defined as any union of arithmetic sequences, does seem both natural and interesting.

My question is this: Can anything useful be done with this topology? Useful would include a new theorem, a simplification to a proof of a known result, or even fresh insight into standard material.

Answer by I. J. Kennedy for How do I explain the number e to a ten year old?

2010-10-09T15:54:02Z

I learned about the "secretary problem" when I was about 10 years old from one of Martin Gardner's books. Though I thought is was cool and amazing, I don't think it gave me much insight into $e$.

Here's a way to introduce $e$ with only addition and multiplication, in the form of a game.

Tell him he's got a "budget" of say, 100 to work with, and his goal is to pick a bunch of (positive) numbers, not necessarily whole numbers, that add up to 100, where he tries to make the product as large as possible.

In his mind, he might first think to break his 100 as 50$\times$50, then realize that 25$\times$25$\times$25$\times$25 is even better, then 10$\times$10$\times$10$\times$10$\times$10$\times$10$\times$10$\times$10$\times$10$\times$10 is even better, and so on. The more numbers you split it into, the better!

But wait...

Answer by I. J. Kennedy for Jokes in the sense of Littlewood: examples?

2010-09-28T16:43:53Z

I suppose this is a silly example, but as far back as grade school I found it amusing (and maybe a little profound) that to invert a fraction $\frac{a}{b}$, you literally invert it! As I learned about more and more mathematical objects through the years, I kept waiting for this kind of thing to happen again, but it never really did.

Why does this sum depend on the Axiom of Choice?

2010-04-23T01:54:39Z

On page 168 of Mathematical Fallacies and Paradoxes, it states that the fact that the series

$1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \cdots $

has a sum depends on the Axiom of Choice. Where does the AC come in to play? I know that if the terms are permuted, we can get any sum we want, and I can see how the AC might be involved there, but just the fact that $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \cdots $ converges?

What is a universal function?

2010-04-19T19:46:06Z

This question stems from Dick Lipton's recent blog post on the Axiom of Choice. I asked there but got no takers. I promise I'm not an inept Googler, but I couldn't find a satisfactory answer. I suspect universal in this context means computable by a universal Turing machine, or something close to that, but I'd like to know for sure.

Is there a tool for finding probability distributions given some samples?

2009-10-21T01:50:01Z

I'm looking for a tool that does "probability distribution fitting" given a set of data points. Sort of like curve fitting, but tries to fit to standard density distributions.

For example if I input

(0, 0.0497871), (1, 0.149361), (2, 0.224042), (3, 0.224042), (4,0.168031), (5, 0.100819), (6, 0.0504094)

I would hope that it would tell me these data points fit a Poisson distribution.

Where to find nice diagrams of trees and other graphs?

2009-11-12T18:56:18Z

Are there some publicly available, vector format diagrams of trees and other graphs? They aren't hard to make, but they sure do take a lot of time (for me).

Comment by I. J. Kennedy

2012-11-05T02:18:39Z

Apparently it is a Britishism meaning "used in earnest". See english.stackexchange.com/questions/30939/….

Comment by I. J. Kennedy

2012-10-28T16:54:07Z

There's no reason to insist $n > 0$; works for $n = 0$ as well!

Comment by I. J. Kennedy

2012-10-24T14:16:24Z

The link should now be oeis.org/DUNNE/TEMPERAMENT.HTML.

Comment by I. J. Kennedy

2012-09-28T17:09:08Z

@Qiaochu "This paper has been withdrawn by the authors; Proposition 3.10 fails in general. The result still holds for nilpotent groups -- a weaker version will follow."

Comment by I. J. Kennedy

2012-09-12T01:48:15Z

And mathoverflow.net/questions/55200/…

Comment by I. J. Kennedy

2012-09-04T22:36:40Z

See On Functions Increasing at a Point at clem.mscd.edu/~talmanl/PDFs/APCalculus/….

Comment by I. J. Kennedy

2012-04-29T03:17:52Z

The places where Boyle is mentioned in the answer, is it supposed to by Boole?

Comment by I. J. Kennedy

2012-02-23T17:35:55Z

Alas, images are now gone.

Comment by I. J. Kennedy

2012-01-05T06:14:18Z

@Chris Eagle: Do you have a cite to the proof that white wins such a variant?

Comment by I. J. Kennedy

2012-01-02T23:41:30Z

Your kinship with mathematics parallels my own nearly exactly.

Comment by I. J. Kennedy

2011-06-15T21:39:45Z

Show me a proof that it's not!

Comment by I. J. Kennedy

2011-05-24T15:07:58Z

That's an old joke.

Comment by I. J. Kennedy

2011-05-15T15:27:38Z

Comment by I. J. Kennedy

2011-04-30T17:39:58Z

This proof without words has an awful lot of them!

Comment by I. J. Kennedy

2011-04-30T17:21:49Z

All the links in this post appear to be broken.