User benjamin dickman - MathOverflow

Answer by Benjamin Dickman for Can you prove the Fundamental Theorem of Algebra just using fixed point theory?

2013-05-28T05:50:23Z

Rather than reading the wall of text above, I am basing my reply off of the answer already provided:

The Arnold proof is well known to be erroneous, but a correct (as far as I know) version is cited in an earlier MO post here. In particular, it is a proof of the FTA via the Brouwer Fixed Point Theorem.

The latter source is:

Some Properties of Continuous Functions. M. K. Fort, Jr. The American Mathematical Monthly, Vol. 59, No. 6 (Jun. - Jul., 1952), pp. 372-375. http://www.jstor.org/stable/2306806.

[Edit: Todd Trimble has kindly provided a link to the Fort paper that does not require jstor access.]

Separately, I see the following quotation:

"Recently, there have been very interesting proofs of the Brouwer theorem. Kulpa deduced a generalization of the Brouwer theorem from the Fubini theorem and the Weierstrass approximation theorem, and applied it to give a simple proof of the fundamental theorem of algebra."

The source of this excerpt is:

Park, S. (1999). Ninety years of the Brouwer fixed point theorem. Vietnam Journal of Mathematics, 27(3), 187-222. http://www.math.ac.vn/publications/vjm/vjm_27/No.3/187-222_Park.PDF

And the reference under discussion is:

W. Kulpa, An integral criterion for coincidence property, Radovi Mat.6 (1990) 313-321.

I gathered this information at the request of D. Goroff some time ago, at which point my search for the Kulpa paper was, unfortunately, fruitless. If anyone can find an accessible copy of this paper, I would be most interested in it (and I know he would be as well).

Answer by Benjamin Dickman for Question about tetrahedron decomposition

2013-05-21T18:23:44Z

In the case where the three parts are each congruent to one another, the answer to your question is no: there is no such decomposition of a tetrahedron.

The terminology needed to find such an answer in the literature is "reptile" or "$k$-reptile simplices."

Citation for proof:

Safernová, Z.: Perfect tilings of simplices. Bc. degree thesis. Charles University, Prague (2008).

Unfortunately (for many) this thesis is written in Czech.

Fortunately, though, there is a more general paper on this topic, entitled "On the Nonexistence of $k$-reptile Tetrahedra." In particular, see Theorem 1.1 (p. 600, pdf 2/11) for the citation above; alternatively, see page 2 of the arxiv version here.

The citation for this latter paper is:

Matoušek, J., & Safernová, Z. (2011). On the Nonexistence of k-reptile Tetrahedra. Discrete & Computational Geometry, 46(3), 599-609.

If you relax the condition and require the simplices be similar to one another but not necessarily congruent, then the term "irreptile" is sometimes used (at least in the $2D$ case). Sadly, I do not know of any work on $k$-irreptile tetrahedra.

Similarities between Post's Problem and Cohen's Forcing

2013-03-08T19:55:21Z

Remark: I have since learned that G.H. Moore addresses this question in the third reference listed at the end of this post, beginning on p. 157 in which he cites a letter from Kreisel to Gödel dated 4/15/63, followed by the parenthetical note: Thus Kreisel saw an analogy between forcing and Friedberg's [1957] priority argument. The following page suggests other logicians agree that forcing was implicit in priority arguments from recursion theory (p. 158) and mentions Kunen (who is cited in one of the answers here). On the same page, it is mentioned that Kreisel claimed he had a form of forcing in his interpretation of intuitionism in the 1961 paper "Set-theoretic problems suggested by the notion of potential infinity." However, Moore contends that Cohen was the first to use forcing and related ideas in Set Theory. Nevertheless, I am grateful for the responses thus far, and would warmly welcome further clarification regarding my question below from other experts in the area of Set Theory and/or Mathematical Logic.

Background: Paul Cohen began to think deeply about the Continuum Hypothesis in 1962, and published his proof of its independence (in two parts) by the following year. Of course, there were earlier mathematical moments that led to his "discovery of forcing," including his familiarity with Skolem's work (in particular, the Löwenheim–Skolem theorem) and a desire to think in terms of "decision procedures." I will include a few relevant references at the end of this question, including a retrospective/introspective piece by Cohen himself.

My question concerns an occurrence in 1957, when Richard Friedberg provided a solution to Post's Problem. First, allow me to transcribe an excerpt from Cohen's talk at the 2006 Gödel centennial:

At that time there was great interest among Raymond [Smullyan] and some other people about the Post Problem. And that’s a problem which could have interested me; it had a mathematical flavor to it. But I never thought about it, and occasionally we’d have coffee and I’d hear these people talk about it. But one day, someone came to my office and said, “This problem’s been solved.” And I said, “Really?” “Yes, here’s the letter. I can’t believe it’s true!” And he gave it to me and I read it. I went to the blackboard, took some chalk, and I said, “Well, it seems right.” This is the proof by Friedberg – and so that was my only contact with logic at that point. But I still never lost this idea of somehow thinking about the foundations of mathematics: trying to find some kind of inductive technique for simplifying propositions; perhaps leading to a decision procedure, when impossible.

This talk is summed up in the introduction to a re-printing of "Set Theory and the Continuum Hypothesis" (Cohen, 2008) in which the remarks corresponding to the above excerpt are:

A small group of students were very interested in Emil Post's problem about maximal degree of unsolvability. I did dally with the thought of working on it, but in the end did not. Suddenly, one day a letter arrived containing a sketch of the solution by Richard Friedberg (Friedberg, 1957), and it was brought to my office. Amidst a certain degree of skepticism, I checked the proof and could find nothing wrong. It was exactly the kind of thing I would like to have done. I mentally resolved that I would not let an opportunity like that pass me again.

I find the last sentence of this latter quotation rather interesting, particularly since it concerns a time five years before Cohen's work on ~CH officially commenced. A quick check of Wikipedia gives a problem statement and solution (i.e., the priority method) that sound remarkably similar, at least on the superficial level, to Cohen's subsequent work with forcing. Unfortunately, work on Turing degrees falls well outside of my bailiwick.

Question: Can someone who specializes in Set Theory or Mathematical Logic comment on the similarities between Post's problem/the priority method and ~CH/Cohen's forcing? In particular, is there reason to believe that what was Cohen's "only contact with logic" by 1957 would have contributed in a meaningful (mathematical) way to his work half a decade later?

References:

Cohen, P. (2002). The discovery of forcing. Rocky Mountain Journal of Mathematics, 32(4).

Kanamori, A. (2008). Cohen and set theory. The Bulletin of Symbolic Logic, 351-378.

Moore, G. H. (1988). The origins of forcing, Logic Colloquium ’86. Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 143-173.

Realizable Order Sequences for Finite Groups

2012-09-16T03:17:04Z

My post is motivated at least in part by this MO question.

Has there been any work done on realizable order sequences for finite groups? By an "order sequence" I mean a non-decreasing list of the orders of the elements of the group. By "realizable" I mean there is some finite group that has that particular order sequence.

For example, $(1, 2, 4, 4)$ is a realizable order sequence; it is the order sequence of $\mathbb{Z}/4\mathbb{Z}$.

Is this something that has been studied in any depth? (Perhaps under a different name?) Are there any non-trivial theorems about realizable order sequences? (Examples of trivial theorems: ones that fall immediately out of Lagrange's Theorem; the degree sequence of $\mathbb{Z}/n\mathbb{Z}$)

I know that there are some nice theorems about degree sequences in graph theory (e.g., Erdős-Gallai theorem; Havel-Hakimi theorem), and though I have seen "order sequence" defined in a few Abstract Algebra texts, I have yet to come across any results of much interest.

I also wonder whether results such as this problem solution (Problem 6636, F. Schmidt, Amer. Math. Monthly, Vol. 98, No. 10 (Dec., 1991), pp. 970-972) or this paper (Isaacs et al (2009). Sums of element orders in finite groups. Commun. Alg. 37(9):2978-2980) contain ideas that would be applicable to such a topic.

Finally, is there an easily accessible (and organized) database that lists order sequences for all finite groups up to a certain not-too-small size?

Edit 1: Is anyone up to computing such a list and posting it somewhere accessible?

Edit 2: Now that Alexander Gruber has kindly posted computations for a fair number of order sequences, I wonder: (a) when does the same order sequence correspond to more than one group? (b) given an order sequence that corresponds to precisely one group, how difficult is it to recover the corresponding group's structure?

Edit 3: Mr. Gruber has most recently pointed me toward a related area of research on "OD-characterizability." One mathematician who has done a fair bit of work in this area is AR Moghaddamfar. See, for example, Recognizing Finite Groups Through Order and Degree Pattern.

Answer by Benjamin Dickman for Elementary examples of the Weil conjectures

2013-01-04T04:52:41Z

Perhaps the following two examples would be of interest to you; my apologies if they are too simple.

Notation: (in accordance with Koblitz's "p-adic Numbers, p-adic Analysis, and Zeta-Functions")

Given $f \in \mathbb{F}_{q}[X_1, \ldots, X_n]$ let us define a sequence $N_s = |(H_{f} (\mathbb{F}_{q^s})|$, where $H_f(K) := ${$(x_1, \ldots, x_n) \in \mathbb{A}^{n}_{K} | f(x_1, \ldots, x_n) = 0$}.

The zeta function is then defined for a hyperplane $H_f$ and field $\mathbb{F}_q$ by

$$Z(T) = \exp\big(\sum_{s=1}^{\infty} N_s T^s /s\big)$$

Before giving a few examples of the rationality of $Z(T)$, we recall the Maclaurin series

$$-\log(1 - T) = \sum_{s=1}^{\infty}T^s / s$$

Example 1. $f(x_1, \ldots, x_n) \equiv 0$. Then $N_s =|{\mathbb{A}}_{\mathbb{F}_{q^s}}^{n}| = q^{ns}$, so that we find $Z(T)$ becomes

$$\exp\big(\sum_{s=1}^{\infty} N_s T^s /s\big) = \exp\big(\sum_{s=1}^{\infty} (q^n T)^s /s\big) = \exp(-\log(1-q^n T)) = 1/(1 - q^n T)$$

Example 2. Let $f = x_1 x_4 - x_2 x_3 - 1$. We now consider two cases:

Case 1. $x_3 = 0$. Then $x_1 x_4 - x_2 x_3 = 1$ becomes $x_1 x_4 = 1$. Since $x_2$ is out of the equation, it can be any element of $\mathbb{F}_{q^s}$. Thus, there are $q^s$ choices for $x_2$. Meanwhile, $x_1$ can be any nonzero element of $\mathbb{F}_{q^s}$, and in each case this will determine $x_4$. Hence there are $q^s(q^s - 1) = q^{2s} - q^s$ points in $H_f$ when $x_3 = 0$.

Case 2. $x_3 \neq 0$. Then $x_1$ and $x_4$ can be any elements of $F_{q^s}$, and $x_3$ can be any nonzero element of $F_{q^s}$. But this completely determines $x_2$, so that there are $q^s q^s (q^s - 1) = q^{3s} - q^{2s}$ points in $H_f$ when $x_3 \neq 0$.

Therefore, $N_s = q^{3s} - q^{2s} + q^{2s} - q^{s} = q^{3s} - q^{s}$, whence the zeta-function $Z(T)$ is

$$\frac{\exp(\sum_{s=1}^{\infty}q^{3s}T^s /s)}{\exp(\sum_{s=1}^{\infty}q^s T^s /s)} = \frac{1 - qT}{1 - q^3 T}$$

Note: The case for an affine variety $H_{f_1, \ldots, f_m}$ follows from the affine hypersurface $H_f$ case by a simple application of the Inclusion/Exclusion Principle. Bearing this in mind, it shouldn't be too hard to construct examples similar to those above over a variety for which the rationality can be witnessed directly. I imagine this would be somewhat tedious, though.

Seeking a Geometric Proof of a Generalized Alternating Series' Convergence

2012-10-14T05:46:00Z

Let $z \in \mathbb{C} \backslash \lbrace 1 \rbrace$ with $|z| = 1$. We consider the following infinite series, which necessarily converges: $$S(z) := \sum_{n = 1}^{\infty}\frac{z^n}{n}$$

Note that $S(-1)$ is the alternating harmonic series.

A straightforward application of the Dirichlet Convergence Test proves any such series converges, but I feel this is a bit like killing a fly with a sledgehammer. (I realize some of you might not think this test is a sledgehammer; I wonder also whether this series is a fly.) In any event, I'm wondering whether there is a way to prove convergence using only a simple geometric argument (with some basic analysis).

For example, we can think of $S(i)$ as taking steps in the plane of length $1/n$, but turning ninety degrees after each one. Then the partial sums correspond to a nested sequence of squares, where the area of the squares is clearly converging to $0$. Thus, an argument using the Nested Interval Property (or really its corresponding $2D$ version) indicates that the series converges.

More generally, I'd think that because we are taking steps of size decreasing to $0$ and rotating by the same amount after each step, there should be a general geometric argument for why $S(z)$ will converge. Ideally, I'd like to have a proof that could be made accessible to early Calculus students, even if not every step is presented in fully rigorous form.

For clarity's sake, I will directly state my question: How does one prove $S(z)$ converges using a simple geometric argument that relies at most on basic analysis (e.g., makes no appeal to stronger theorems from Complex Analysis)?

Permuting Racked Pool Balls with a Single Break

2012-12-27T07:28:30Z

Given reasonable physical assumptions (on friction, collisions, etc.), would it be possible to "break" in a pool game such that when all the balls come to rest, the only difference is that the racked balls have been permuted non-trivially?

Example:

More generally, would any non-trivial permutation be possible?

Answer by Benjamin Dickman for Arithmetic dynamics and dynamics on moduli spaces

2012-12-26T11:22:01Z

Joseph H. Silverman has compiled a long list of articles and books on arithmetic dynamical systems.

It is available for free here. (Plug for myself: I made it in at #82!)

Answer by Benjamin Dickman for Why is Gauss credited with his connection?

2012-11-17T01:48:03Z

The short answer is we call it the Gauss-Manin connection because that's what Grothendieck called it. The name is attributed to Grothendieck in two early, seminal pieces: namely, Katz's thesis and a subsequent article of his ("On the differentiation of De Rham cohomology classes with respect to parameters", Katz & Oda).

If you can read (some) French, look through Yves Andre's chapter in "Geometric Aspects of Dwork Theory". If not, check through the start of this arxiv paper (through the first couple paragraphs of 1.2).

The slightly less short answer is the one Gerhard Paseman alluded to above; quoting from the aforelinked arxiv paper ("Towards a nonlinear Schwarz’s list", Philip Boalch):

"One reason hypergeometric equations are interesting is that they provide the simplest explicit examples of Gauss–Manin connections. Indeed this is one reason Gauss was interested in them: he observed that the periods of a family of elliptic curves satisfy a (Gauss) hypergeometric equation. (The modern interpretation of this is as the explicit form of the natural flat connection on the vector bundle of first cohomologies over the base of the family of elliptic curves, written with respect to the basis given by the holomorphic one forms—and their derivatives—on the fibres.) Nowadays there is still much interest in such linear differential equations “coming from geometry”.

Thus the nonlinear analogue of the Gauss hypergeometric equation should be the explicit form of the simplest nonabelian Gauss–Manin connection (i.e the explicit form of the natural connection on the bundle of first nonabelian cohomologies of some family of varieties). The simplest interesting case corresponds to taking the universal family of four punctured spheres and taking cohomology with coefficients in $SL_2(\mathbb{C})$ (one needs a non-trivial family of varieties with nonabelian fundamental groups)."

Answer by Benjamin Dickman for Origin of the theorem on the existence of the smallest field of definition of an affine variety

2012-10-28T21:57:48Z

I suspect that this theorem is indeed due to Weil.

"Foundations of Algebraic Geometry" by Weil was published in 1946, but the 1944 paper "Some Properties of Ideals in Rings of Power Series" by Claude Chevalley (Transactions of the American Mathematical Society, Vol. 55, No. 1 (Jan., 1944), pp. 68-84) attributes to Weil the development of the theory around "ideals in polynomial rings" over a decade earlier in "Arithmetique et geometrie sur les varietes algebriques" in 1935 (see footnote on p. 83).

Reading the AMS review it seems the only other possible originators would have been Siegel, or perhaps Noether or van der Waeden. I don't have a copy of Weil's 1935 work, but you might track it down and (if you can read enough French) check for this particular result.

Edit: For remarks which are perhaps related/interesting (in terms of Weil's background and his familiarity with Kronecker's work) read from the last paragraph of page 12 here and the referenced ICM address by Weil in 1950.

Answer by Benjamin Dickman for Is there a function that determines the rank of a multiset after inserting another element?

2012-10-27T03:24:31Z

Start by attempting the problem for ordered multisets; once you have found a formula, go back and adjust for non-ordered multisets (if you so desire).

First, re-stating your ranks for ordered multisets: The rank of (1,1) is 6, since it's what you have and (1,0). Similarly, (0,1,1)'s rank is 10, because it has 9 multisets less than it (omitting parentheses and commas): 0, 1, 00, 01, 10, 11, 000, 001, 010.

Next: to find the rank of a lexicographically ordered multiset, concatenate the elements with an extra 1 at the start, view this as a binary number, and subtract 1 from its decimal representation. For example, (1,1) becomes 111 which is binary for 7. Now subtract 1 to get rank 6. Similarly, (0,1,1) becomes 1011 which is binary for 11. Subtract 1 to get rank 10.

I am quite certain the above is sufficient for you to work out $f(2,x,n)$ and - though slightly more difficult - to work out $f(3,x,n)$, after which you can probably figure out $f(r,x,n)$.

Answer by Benjamin Dickman for Seeking a seemingly missing reference of Casson

2012-10-05T23:28:31Z

According to the following paper, this invariant's introduction is sourced as: A. Casson, Lecture notes, MSRI Lectures, Berkeley, 1985.

The first published discussion appears to be found in: S. Akbulut & J. McCarthy, Casson's invariant for oriented homology 3-spheres, an exposition, Math. Notes, No. 36, Princeton Univ. Press, Princeton, 1990.

"I don't know if he [Casson] has ever written his notes. I attended his lectures at MSRI then I went back to MSU and tried to fill in the details together with McCarthy, those notes are the result." S. Akbulut

"Here is a pdf of hand-written notes of T. Cochran's. Page two includes annotated notes by Boyer, and I got the notes from my friend and colleague, A. Nicas." H. Boden

Answer by Benjamin Dickman for Is x*tan(x) integrable in elementary functions?

2012-10-02T06:48:12Z

Some thoughts on this antiderivative:

Attacking $\log(\cos x)$ using integration by parts, we find:

$$\int \log(\cos x) = x\log(\cos x) + \int x \tan x dx$$

So the question has now become: how do we find an antiderivative for log(cos x)?

Next, we observe that

$$\cos x = \frac{1}{2}(e^{ix} + e^{-ix}) = \frac{1}{2}e^{ix}(1 + e^{-2ix})$$

Taking the log of this, we end up with:

$$-\log 2 + ix + \log(1 + e^{-2ix})$$

Recall that we can write

$$\log(1 + y) = \sum_{k = 1}^{\infty} \frac{(-1)^{k+1}y^{k}}{k}$$

We can now apply this with $y = e^{-2ix}$ as above and integrate term by term.

Putting all these pieces together will give you a (nasty) way to integrate $x\tan x$.

As far as showing it's not integrable in elementary functions, I suspect your best bet would be an appeal to a theorem of Liouville. See, for example, this link. (Sorry I can't be of more help here!)

All that said, perhaps you could ask your students some form of the following: show

$$\int x\tan^{2}x dx = x\tan x - \frac{x^2}{2} + \log(\cos x) + C$$

(You can find this latter, more tractable problem and its solution written out in nice detail here.)

Intuition Behind a Decimal Representation with Catalan Numbers

2012-09-27T07:15:28Z

From $0 = 0.5 - 0.5 = 0.5 - \sqrt{0.25}$, we can adjust the subtrahend slightly to obtain

$$0.5 - \sqrt{0.249} = 0.001\ 001\ 002\ 005\ 014\ 042\ldots$$

where the decimal representation contains the first few Catalan numbers: $1, 1, 2, 5, 14, 42 \ldots$

We can see even more Catalan numbers (albeit spaced apart with more $0$s) by using more $9$s.

(For example, check the decimal representation of $0.5 - \sqrt{0.24999999999}$.)

My question is not how to show this formally; it is a straightforward problem to show how one derives, e.g., the decimal representation given above. (I'll include a derivation below for anyone who doesn't want to think this through her/himself.)

Instead, my question is: why would it make sense, intuitively, for the Catalan numbers to show up in these decimal representations?

Derivation:

Recall that the generating function for the Catalan numbers $c(x)$ satisfies $c(x) = 1 + xc(x)^2$. Rearranging, we find that $c(x) = \frac{2}{1 + \sqrt{1 - 4x}}.$ Then

$$\sum_{n = 0}^{\infty}\frac{C_n}{10^{3n + 3}} = \frac{1}{1000}\sum_{n=0}^{\infty}\frac{C_n}{1000^{n}} = x \sum_{n=0}^{\infty}C_n x^n = xc(x) = \frac{2x}{1 + \sqrt{1 - 4x}},$$

where we have simplified our computations by letting $x = \frac{1}{1000}$.

Evaluating at this value of $x$ yields $0.5 - \sqrt{0.249}$.

Answer by Benjamin Dickman for Thurston's senior thesis at New College

2012-09-14T05:32:30Z

I've emailed you a pdf copy of "A Constructive Foundation for Topology" by Bill Thurston (June 14, 1967; New College Senior Thesis; submitted to Roger Renne).

In consideration of the comments above, I'm hesitant to post the file in a publicly accessible location. Perhaps the mathoverflow community can figure out whether such a posting would be appropriate.

Proposed Counterexample to a Theorem of Differential Geometry (on Banach manifolds)

2012-09-04T01:54:46Z

This question stems from Jeff Rubin's earlier MO question and a follow-up that I posted.

The former recalls the following result proved by both Serge Lang (Fundamentals of Differential Geometry, 1999, Springer-Verlag) and Abraham, Marsden, and Ratiu (Manifolds, Tensor Analysis, and Applications, 1988, Springer-Verlag):

Theorem: A connected Hausdorff Banach manifold with a Riemannian metric is a metric space.

That said, consider 27.6 (pdf pp. 262-263) in The convenient setting of global analysis (AMS, 1997), and in particular the example given at the end of it, which concludes with: "Then the same results are valid, but $X$ is now even second countable."

My question: Is this second countable $X$ a counterexample to the above theorem?

I'm hoping someone can shed some light on this matter, either by explaining why it fails as a counterexample (offhand, I'd deem this the more likely scenario) or by proving/sketching why it might actually suffice.

Edit 1: Here's a sketch of why one might even consider this example:

If indeed the proposed space $X$ described in 27.6 of the link above is second-countable, then at least one source I have found claims that $X$ would, as a result, admit a Riemannian metric. [NB: It has been pointed out that this source states its claim strictly in the context of finite-dimensional manifolds.] Furthermore, $X$ is described as a modification (where "the same results are valid") of a space that is a connected Hausdorff Banach manifold that is separable and not regular.

To summarize, we might have $X$ as a connected Hausdorff Banach manifold with a Riemannian metric, which is separable and not regular (hence non-metrizable by Urysohn's Theorem), in which case, $X$ would be a counterexample to the above-stated theorem.

Sub-question 1: can anyone find other sources (preferably with proof) that a second-countable connected Hausdorff manifold necessarily admits a Riemannian metric? Alternatively, can anyone find a counterexample to this? [NB: Particularly in the context of infinite dimensional manifolds.]

Sub-question 2: can anyone prove (or sketch a proof of) the connectedness of $X$? Alternatively, can anyone show that $X$ is not connected? [NB: This has been answered: $X$ is connected.]

I'd appreciate even a partial answer to my original question or either of my sub-questions. Also, if you should know (of) anyone who is doing work in this area of mathematics, perhaps you could direct them to my query.

Thanks!

Edit 2: My second sub-question has been answered in the affirmative by Wolfgang Loehr: $X$ is indeed a connected space.

I see numerous mentions of the result mentioned in my first sub-question (that second-countability alone implies a connected Hausdorff manifold admits a Riemannian metric) but I'm wondering whether this is in fact only a theorem for finite dimensional manifolds.

Nonetheless, my initial question still stands: is the space $X$ described in the AMS book on Global Analysis a counterexample to the theorem stated above?

Edit 3: As time winds down on the question's bounty, I wonder whether anyone has helpful thoughts with regard to non-regular manifolds that admit Riemannian metrics. More precisely, how could one prove that $X$ does or does not admit a Riemannian metric?

Post-bounty Edit: I awarded the bounty since my sub-question 2 was answered entirely. There is still no conclusion as to whether or not the space referenced above is a counterexample to the aforementioned theorem, but it is increasingly clear that there is a fair bit of confusion surrounding when theorems about Banach manifolds do or do not extend from the finite dimensional case to the infinite dimensional one.

Answer by Benjamin Dickman for Who named it the Snake Lemma?

2012-09-11T22:56:48Z

I suspect the name just arose naturally (for obvious reasons) and that it would be tough to trace back to any single person. After Cartan-Eilenberg proved it in 1956 (Homological Algebra, p.40) the first mention I see in English is by Tate in 1966/67 (p-divisible groups, p.178) followed by Hartshorne in 1968 (Cohomological Dimension of Algebraic Varieties, p.446), neither of which bother with a citation, reference, or quotation marks (1). However, it was used a bit earlier - also without citation or quotation marks - by Begueri-Poitou in 1965 (2) as 'lemme du serpent'; mentioned early on in their abstract. [NB: the first page of the linked pdf incorrectly lists the second author's surname as Poiton.]

I realize this answer is a bit unsatisfying, but the best I can say is that the name took hold at some point between 1956 and 1965; though I can't even say for sure whether the first use was in English or French. Each of the references above uses the term so casually that I would guess by the late 50s/early 60s it was already being referred to as such in Algebra classes -- though this is just a hunch.

I also did searches in Russian (and, for fun, Chinese) but could find nothing appearing any earlier than 1965.

If I were to suggest where to look next, it'd be in Cartan's Seminar Notes (reference: H. Cartan, Séminaire E.N.S., 1950-1951) or perhaps in the recently published book of letters between Cartan and Weil (Correspondance entre Henri Cartan et André Weil 1928-1991) to see if the word 'serpent' ever comes up.

Edit: I used numdam to search for 'serpent'. Cartan has a quotation about a snake nearly biting its own tail (1965, pdf p.16/17), but more interesting is a paper by Grothendieck dating to 1964 mentioning a snake diagram ("le diagramme du serpent", pdf p.195/258) that he attributes to (Bourbaki, Alg. comm, chap. I, $\S$1, no 4, prop. 2). You can see the term snake diagram in the much later English translation, but I'm not sure when the original French version was written (I think at least as early as 1961). If someone could dig up that reference, it would probably hold the first published instance (rooted out thus far) that uses the snake terminology.

My guess for the time being: The term snake diagram originated (in French) around 1960 and was first used by one of the Bourbaki members (possibly Cartan, Eilenberg, or Grothendieck). Snake lemma almost certainly has a similar origin.

Non-regular Connected Hausdorff Banach Manifold

2012-08-18T03:02:17Z

After reading this MO post, I am wondering:

Is every (connected) Hausdorff Banach manifold a regular space?

Though unjustified, page 53 of this paper nonchalantly states: "Note that a Hausdorff Banach manifold X is a regular space."

But does anyone know of a proof of this statement (or a counterexample)?

Of course, the real difficulty arises in proving the statement for the infinite-dimensional version, since such a Banach manifold will not be locally compact.

Follow-up: Now that Theo Buehler has kindly pointed to a counterexample (i.e. a connected Hausdorff Banach manifold which is not regular) perhaps it will give someone an idea about how to tackle the question that provided the inspiration for this one.

Extending an assignment property from Q to R (or C)

2012-08-24T17:15:40Z

Property of any odd number of nonnegative integers:

Given $x_1 \leq \ldots \leq x_{2n + 1}$ with each $x_i \in \mathbb{Z}_{\geq 0}$, suppose that for any $x_i$ we remove that the remaining numbers can be assigned to disjoint multisets $A$ and $B$ such that $|A| = |B| (= n)$ and $\sum_{x \in A} A = \sum_{x \in B} B.$ Then all the $x_i$ must be equal.

To prove this, fix any $n \geq 0$ and note that all the $x_i$ must have the same parity. Suppose there were an assignment of values such that the $x_i$ weren't all equal; using the Well-Ordering Principle, consider such a non-trivial assignment with $\sum x_i$ minimal. If $x_1 = 0,$ divide each $x_i$ by $2$ to derive a contradiction; if $x_1 > 0,$ subtract $1$ from each $x_i$ to derive a contradiction. Thus, all the $x_i$ must be equal.

This property extends easily from the nonnegative integers to the rational numbers: if we had a non-trivial assignment of rational values, we could multiply through by their lcd to obtain a non-trivial assignment of integer values, and then subtract from each the smallest integer value to obtain a non-trivial assignment of nonnegative integers, thereby contradicting our earlier conclusion.

Question: Does this property also hold for any odd number of real (or complex) numbers?

Any connections between this question and other areas would, of course, be welcomed.

Question re-stated explicitly: Given $x_1 \leq \ldots \leq x_{2n + 1}$ with each $x_i \in \mathbb{R}$ (or $\mathbb{C}$), suppose that for any $x_i$ we remove that the remaining numbers can be assigned to disjoint multisets $A$ and $B$ such that $|A| = |B| (= n)$ and $\sum_{x \in A} A = \sum_{x \in B} B.$ Is it true that all the $x_i$ must be equal?

Edit 1: An equivalent problem appears as #15.23 in "Problems and Theorems in Classical Set Theory" (solution on pp. 323-324) by Péter Komjáth and Vilmos Totik (2006).

Edit 2: The integer version of this problem was Putnam Problem B1 (1973); the question about extending to the reals is posed at that solution link as well. The integer version (for 2n+1 = 23) is also included as problem #3.4.31 in "The Art and Craft of Problem Solving" (2e, p. 107) by Paul Zeitz. An earlier extension to the positive reals (easily seen as equivalent to the reals) is AMM Problem 11002 (2003), though the solver whose answer is linked to proceeds in a manner quite different from that of Pierre or Péter.

Edit 3: In a 1992 article, Liong-shin Hahn notes the connection between B1/1973 and an article on abelian groups with no nontrivial element of odd order (Respective sources: L.-S. Hahn, "Alternate Solutions to Putnam Competition Problems," Mathematics Magazine, 65(2), 1992; G.A. Martin, "A class of Abelian groups arising from an analysis of a proof," Amer. Math. Monthly, 95, 1988).

Hahn then proceeds to solve the problem over R and C using the sort of approach used above in AMM 11002's solution. This appears to be an English version of Hahn's earlier write-up (1981), in which he claims to have solved this problem (known as Problem 4304 in Mathmedia). I couldn't find his first solution (see Edit 4); however, I did locate another citation for his having solved it, as well as the original problem. All were written in Chinese (Hahn was born in Taiwan; see his AMS Citation for Public Service), so I will type out the original problem and provide an English translation below.

Traditional Chinese:

4304 （編輯部提供）有17個球，假定無論任取一個後，剩下的16個都可以分為重重相等的兩堆，每堆8個。試證此17個球的重量必然相同。

Simplified Chinese:

4304 （编辑部提供）有17个球，假定无论任取一个后，剩下的16个都可以分为重重相等的两堆，每堆8个。试证此17个球的重量必然相同。

English Translation:

4304 (Proposed by the editors) Given 17 balls, suppose that no matter which one is removed, the remaining 16 can be separated into two piles of equal weight, with 8 balls in each pile. Prove that these 17 balls must all be equal in weight.

Edit 4: I managed to obtain a copy of Hahn's original solution (1981) to this problem (over $\mathbb{R}_{+}$, which easily extends to $\mathbb{C}$) by contacting an administrator at Academia Sinica, Taipei, Taiwan. His approach proceeds using only basic linear algebra with an application of Cramer's Rule as the coup de grâce. The solution in Chinese can be viewed here; I will not endeavor to translate it unless it is somehow essential to someone's research. Nonetheless, it's interesting to see a full solution that preceded the AMM solution by 22 years. Though this is nothing like Weil's popularization of the Shimura-Taniyama conjecture from a Japanese journal, it does make one wonder what other gems have been hidden away in Asian journals of mathematics.

Building a Physical Model to Solve Sudoku

2012-08-14T19:22:18Z

Before asking my questions, allow me to begin with a separate example to help clarify what I'm driving at. For terms that are not defined formally, please interpret them as you feel would be most appropriate, and I welcome any attempts to modify this question so as to make it more interesting and/or understandable.

Background Example: Suppose you have Cartesian coordinates for $n$ different points $p_1, \ldots, p_n$ in the plane, and you want to find a point $p$ that minimizes $\sum_{i}^{n}|p-p_i|.$ (In other words, you want to find the "geometric median" for these $n$ points.)

Finding such a $p$ is trivial for $n = 1$ and $n = 2$, and well-known for $n = 3.$

Note that even for $n = 4,$ finding a general approach that leads to an exact answer is tough. For larger values, say, $n = 10,$ we would (in most real life situations) estimate $p$ using a computer.

But here's a way to estimate $p$ using a physical model: take a piece of plexi-glass, draw a grid on it, drill tiny holes corresponding to the $n$ points, thread equally-weighted wires through each of the holes (tie, say, a $10g$ weight to the ends below the plexi-glass), and fuse the tops of all the wires together. Holding the plexi-glass level, a minimal energy argument suggests that the final resting point for this "fused top" will be (approximately, because we're talking about the real world here) at $p.$

Question 1: Is there some way to build a physical model where you start with a $9$x$9$ Sudoku grid and its clues (i.e. the numbers filled in at the start) and then separately have all the numbers yet to be placed, and by "doing something" (dropping balls, something with weighted-strings, I'm not sure -- hence the question) release the non-placed numbers so that they "quickly" fall into place (e.g. as a "minimal energy" or "path of least resistance" consequence)?

Remark: On the one hand, Sudoku is "discrete" in a way that the aforementioned background example is not, which suggests to me that it might be possible to create such a physical model. On the other hand, the $NP$-completeness of Sudoku has me nearly convinced that no such model could be built. However, I haven't the faintest idea as to how one proves the non-existence of this sort of physical model.

Question 2: What would the implications of the existence (or non-existence) of a physical model to "quickly" solve Sudoku be for the question of $P = NP$?

Solving a modified birthday problem at a glance

2012-08-03T19:22:56Z

Modified Birthday Problem: a bunch of people line up, and the winner is the first person who shares his birthday with someone lined up ahead of him. What position in the line is optimal?

Three (similar) approaches: Recall the well known Birthday Problem, and let $b(n)$ denote the likelihood that there is a shared birthday in a collection of $n$ people. Suppose you are the $(n+1)$st person in line, and you want to be the first person to share your birthday with someone ahead of you. 'None of the people ahead of you sharing a birthday' happens with probability $1 - b(n)$, and 'you sharing a birthday with one of them' happens with probability $n/365$. Therefore, we wish to maximize: $(1-b(n))(n/365)$. A computer search (e.g. in WolframAlpha) can find $n$ is about $19$, and so you want position $20$.

Alternatively, we can approximate $1-b(n)$ with $e^{-n(n-1)/730}$ pretty well. Now consider setting $\frac{d}{dx} e^{-x(x-1)/730} (x/365) = 0,$ which ends up requiring only that we solve a quadratic. In particular, we end up with the quadratic $x^2 - x/2 = 365.$ Then $x$ is a little over $19$, and again we guess the optimal position is at $20.$

Finally, we consider the ratio of probabilities of winning for consecutive people in line. Eliding over some details (e.g. showing initial ratio $> 1$, the ratios are decreasing) we can check to see when this ratio drops below $1.$ This will again culminate in solving a quadratic, namely, $x^2 - x = 365.$ Since $x$ is about $19$, we have (for the third time) found the optimal position to be at $20.$

Question 0: Why do the quadratics arrived at in our second and third approach differ? (I suspect this is just an artifact of the rough estimation used in the second approach, although I could not explain the reasoning behind this difference in any greater detail.)

Question 1: Since our third method indicates that solving for $x$ in $x(x-1) = 365$ ultimately leads to the solution, I am wondering: is there a way to have seen "at a glance" the importance of this quadratic? My intuition tells me that there is a much more straightforward way of thinking about this problem, but I am not sure what it would be.

Answer by Benjamin Dickman for Are there any interesting or lesser known proofs related to Bertrand's Postulate

2012-08-02T00:35:48Z

Bertrand's Postulate follows as a direct consequence of the following theorem of J.J. Sylvester:

Theorem (Sylvester, 1892): Let $k$ be a positive integer. Then at least one of any $k$ consecutive integers greater than $k$ is divisible by a prime greater than $k$.

(For comparison: Chebyshev's analytic proof dates to 1850; Erdos' elementary proof dates to 1932.)

See Theorem 6 (p. 6) in http://www.math.sc.edu/~filaseta/papers/schurpaper.pdf, from which I quote:

"The theorem implies immediately that for any positive integer $k$, one of $k+1, k+2, \ldots, 2k$ is a prime (since one of these integers must be divisible by a prime $\geq k+1).$"

Unfortunately, my internet search has not led me to the original paper by Sylvester.

Irrationality proof technique: no factorial in the denominator

2012-07-25T22:43:41Z

Jonathan Sondow elegantly proves the irrationality of e in his aptly titled A Geometric Proof that e Is Irrational and a New Measure of Its Irrationality (The American Mathematical Monthly, Vol. 113, No. 7 (Aug. - Sep., 2006), pp. 637, http://www.jstor.org/stable/27642006).

In his argument, he constructs a sequence of nested intervals $I_n$ for every $n \geq 1$, each of the form $[k/n!, (k+1)/n!]$, such that $\bigcap I_n = ${$e$}, with $e$ lying strictly between the endpoints of each $I_n.$ From this, we conclude that $e$ cannot be written as a fraction with denominator $n!$ for any $n \geq 1.$

Fact: Every rational number $p/q$ can be written as a fraction with a factorial in its denominator: $p/q = p(q-1)!/q!$.

Thus, we conclude that $e$ is irrational.

The reason this proof technique works so well with $e$ is, of course, related to the Maclaurin series for the exponential function, $e^x.$

That any rational number can be written in lowest terms is employed in other irrationality proofs (e.g., the classic proof for that of $\sqrt{2}$) but I had not seen the above fact drawn upon before reading this particular paper.

My question is: are there other examples of real numbers (which are not related to $e$ in some trivial way) whose irrationality can be proved using the Fact above?

Crossing number of the Grötzsch graph

2012-04-17T09:07:45Z

Is the crossing number of the Grötzsch graph known? I have heard it conjectured to be 5 (certainly it is no greater), but came up empty-handed in my search of the literature.

Comment by Benjamin Dickman

2013-06-17T15:54:43Z

[The closed-form at the end has an $n$ term and a $k$ term; perhaps you should change the denominator to $n!^s$.]

Comment by Benjamin Dickman

2013-06-17T11:22:16Z

Cross-posted (under the name Rob): math.stackexchange.com/questions/422449/…

Comment by Benjamin Dickman

2013-06-06T00:13:45Z

@Todd: Yes, it would be nice to see these discrepancies sorted out. (Also, it's `Dickman' not `Dickson'!)

Comment by Benjamin Dickman

2013-06-05T15:05:56Z

@Todd: We were apparently editing the (rather prolix) question simultaneously! I rolled back to your version.

Comment by Benjamin Dickman

2013-06-05T14:29:42Z

@Todd: Thanks! Also, I reiterate here: If anyone can find a copy of Kulpa's paper (cited in my response above) it would be greatly appreciated.

Comment by Benjamin Dickman

2013-05-30T22:55:30Z

Also: to count, e.g., the number of rectangles that can be formed (in the natural way) in an n by n grid of unit squares, turn it into an n by n multiplication table and sum the entries. In particular, the number of squares that can be formed in an n by n grid of unit squares is the sum along the diagonal, n(n+1)(2n+1)/6.

Comment by Benjamin Dickman

2013-05-30T22:52:55Z

One note that comes to mind (and this may not be of any use) is that a square can be decomposed into 1, 4, or 6, 7, 8, ... subsquares (not necessarily of the same size). Showing 2, 3, and 5 are impossible is a nice exercise (especially 5). Once you have 1, 6, and 8, you can take a single subsquare and re-subdivide into a 2x2 for a net gain of 3. E.g., 1 to 4, and then 4 to 7; and then from 6, 7, and 8 you can get all subsequent natural numbers. (There are lots of other fun students activities that can be done with this idea, but that would stray too far from your question.)

Comment by Benjamin Dickman

2013-05-29T07:39:14Z

An answer to my question (see comment above) posed last August: mathoverflow.net/questions/104965/…

Comment by Benjamin Dickman

2013-05-28T06:01:08Z

The idea of blocking a method from being used in a proof is quite interesting in general, but I believe that, in this case, the BFPT can be used to prove the FTA. (See my answer elsewhere in this post.)

Comment by Benjamin Dickman

2013-05-28T02:02:00Z

Perhaps you may wish to edit the post so that Question 1 is emphasized. In terms of literature, it may be that the reverse scenario has been researched in greater depth: namely, finding empty convex regions in tightly packed three-space. Of course, this should be equivalent to what you are asking. I haven't read through carefully, but check out compgeom.com/~piyush/papers/occluder.pdf and some of the sources given in section 2 (`Previous Work').

Comment by Benjamin Dickman

2013-05-28T00:51:29Z

@Joseph: Assuming I have correctly understood your Q2, those three needles suffice. (Clearly it is also necessary to have at least three.) This should indicate your Q3 is answered in the affirmative. Surely Q1 is a bit tougher.

Comment by Benjamin Dickman

2013-05-27T15:50:31Z

There's an interesting piece in: Stewart, I. (1995). Four encounters with sierpińriski’s gasket. The Mathematical Intelligencer, 17(1), 52-64. In particular, see Encounter 3. (Paywall, I think: link.springer.com/article/10.1007%2FBF03024718)

Comment by Benjamin Dickman

2013-05-27T02:28:02Z

@fuzzytron: Jeff Weeks' name comes up after a cursory search through google (e.g., for `binary octahedral space'). See: arxiv.org/pdf/math.SP/0502566.pdf As for some `special role this manifold has', see, e.g., arxiv.org/pdf/astro-ph/0504656v1.pdf Perhaps literature related to the latter link would provide more relevant information.

Comment by Benjamin Dickman

2013-05-24T22:03:18Z

For a particularly nice example of how strangely even quadratics can behave, consider: $f(x) = x^2 - \frac{181}{144}$ and the point $x = \frac{7}{12}$.

Comment by Benjamin Dickman

2013-05-24T21:59:50Z

Unless there is some underlying trick that I do not see, I suspect this problem is very difficult in general. You are asking when certain pairs $(x,y)$ are preperiodic for $f(x,y) = \frac{xy}{x+y-1}$. Even in one variable, questions about preperiodic points of rational functions can be quite tough. See, for example, RL Benedetto's "Heights and Preperiodic Points of Polynomials Over Function Fields" (arxiv.org/abs/math/0510444) or - for the polynomial case in one variable - "Computing points of small height for cubic polynomials" (arxiv.org/abs/0807.0468).