User thei - MathOverflow

Answer by thei for Examples of common false beliefs in mathematics.

2011-04-10T18:08:02Z

The cost of multiplying two $n$-digit numbers is of order $n^2$ (because each digit of the first number has to be multiplied with each digit of the second number).

A lot of information is found on http://en.wikipedia.org/wiki/Multiplication_algorithm .

The first faster (and easily understandable) algorithm was http://en.wikipedia.org/wiki/Karatsuba_algorithm with complexity $n^{log_2 3} \sim n^{1.585}$.

Basic idea: To multiply $x_1x_2$ and $y_1y_2$ where all letters refer to $n/2$-digit parts of $n$-digit numbers, calculate $x_1 \cdot y_1$, $x_2\cdot y_2$ and $(x_1+x_2)\cdot(y_1+y_2)$ and note that this is sufficient to calculate the result with three such products instead of four.

Article about partitions with forbidden parts/multiplicities

2011-11-05T14:31:05Z

I am looking for an article, most likely from the 90s, that generalized the bijection between partitions with odd and distinct parts by explaining how a bijection between the forbidden parts could be transformed into a bijection of the partitions.

(So, in the example above, a bijection can be formed using the fact that $(2k)$ is in bijection with $(k,k)$ which form the forbidden parts on both sides.)

Answer by thei for Two rectangular parallelepiped

2011-10-31T21:32:51Z

This version works for all parallelepipeds, not only rectangular ones:

If you replace each parallelepiped by all points that have distance at most $\varepsilon$ to a point in the parallelepiped, you can still place the smaller inside the bigger one. In particular, the smaller object has a smaller volume.

We divide up the extended parallepipeds by extending the planes corresponding to the six faces. This gives the volume of the original solid in the center, parallelepipeds of height $\varepsilon$ on top of each face, partial cylinders (with slanted parallel ends) of radius $\varepsilon$ and length the corresponding edge, and partial spheres of radius $\varepsilon$ around each vertex.

The partial spheres add up to exactly one whole sphere simply by translation. The partial cylinders corresponding to parallel edges add up to one whole cylinder by translation.

Now let $\varepsilon$ tend to infinity (yes, really). The term with $\varepsilon^3$ comes from the sphere of radius $\varepsilon$ and does not depend on the parallelepiped at all, . The coefficient of $\varepsilon^2$ comes from the cylinders and is clearly the sum of the edges times some constant.

So, for the inequality to be valid the sum of the edges of the smaller box must be smaller than the sum of the edges of the larger box.

I don't see any problem with the generalization to higher dimension.

Answer by thei for What are some examples of "chimeras" in mathematics?

2011-04-28T20:28:32Z

I propose $$f(x)=\begin{cases} e^{-\frac 1x} \text{ for } x> 0\\ 0 \text{ else.} \end{cases}$$ which can be used to construct concrete partitions of unity.

What is the relation between hypocycloids and ideals in polynomial rings as alluded to in Arnold's text on teaching mathematics?

2011-04-21T15:18:46Z

While browsing through this site, I came upon the text of Arnold: "On teaching mathematics".

http://pauli.uni-muenster.de/~munsteg/arnold.html

containing the phrase

... it can be said that a hypocycloid is as inexhaustible as an ideal in a polynomial ring. But teaching ideals to students who have never seen a hypocycloid is as ridiculous as teaching addition of fractions to children who have never cut (at least mentally) a cake or an apple into equal parts.

So, here is my question:

What is the relation between the hypocycloid and ideals?

Edited to add in view of the first comment:

The hypocycloid is an algebraic curve and the polynomials that vanish on this curve form an ideal. But is there anything about the hypocycloid that motivates the question of regarding vanishing polynomials (which is clearly the case for cutting cakes and adding fractions or some of the other mathematical/physical examples in the text).

Answer by thei for German mathematical terms like "Nullstellensatz"

2011-04-19T11:28:26Z

An indirect answer:

Klein bottle

which has probably started out as:

Kleinsche Fläche (=Klein surface)

Kleinsche Flache (lost umlaut in English print)

Klein bottle (translation of Flasche instead of Flache)

Answer by thei for Examples of common false beliefs in mathematics.

2011-04-07T12:45:11Z

Regard a reasonably nice surface in $\mathbb R^3$ that can locally be expressed by each of the functions $x(y,z)$, $y(x,z)$ and $z(x,z)$, then obviously

$\frac {dy} {dx} \cdot \frac {dz} {dy} \cdot \frac {dx} {dz} = 1$

(provided everything exists and is evaluated at the same point).

After all, this kind of reasoning works in $\mathbb R^2$ when calculating the derivative of the inverse function, it works for the chain rule and it works for separation of variables.

Note that this product is in fact $-1$ which can either be seen by just thinking about what happens to the equation $ax+by+cz=d$ of a plane / tangent plane or by looking at the expression coming out of the implicit function theorem.

I recall someone claiming that this example proves that $dx$ should be regarded as linear function rather than infinitesimal, but I cannot reconstruct the argument at the moment as this discussion was 15 years ago.

In particular, it is true under appropriate conditions in $\mathbb R^4$ that $\frac {\partial y} {\partial x} \cdot \frac {\partial z} {\partial y} \cdot \frac {\partial w} {\partial z} \cdot \frac {\partial x} {\partial w} = 1$

Answer by thei for Proofs without words

2011-04-10T15:54:03Z

I suggest the videos of Viennot explaining the bijections between different families of objects counted by Catalan numbers:

http://web.mac.com/xgviennot/Cont_Science/vid%C3%A9os.html

Answer by thei for Product of hypergeometric functions/Jacobi Polynomials

2011-04-09T18:23:47Z

Have you tried to look at the recurrence relation satisfied by the product of Jacobi polynomials? (For example, maple/gfun finds product recurrences, but a list of related packages is on the site http://www.mat.univie.ac.at/~slc/divers/software.html of the Seminaire Lotharingien de Combinatoire.)

In general, this will not be a single sum, but a lot of things can be done just by using the recurrence relation instead of a sum representation and there is the Petkovsek algorithm to check if a nice closed-form solution exists.

(A good reference is the book A=B by Petkovsek, Wilf and Zeilberger http://www.math.upenn.edu/~wilf/Downld.html)

(BTW I don't think that your expression for the coefficient is correct but I may have copied it incorrectly.)

Answer by thei for How can I get this paper?

2011-04-09T10:47:28Z

Did you consider looking it up on Mathscinet/Google Scholar/Zentralblatt and then order it through your library?

au:Mathieu, Olivier & ti:demazure & py:1986-1986 on zentralblatt gives

Mathieu, Olivier

Formules de Demazure-Weyl, et généralisation du théorème de Borel-Weil-Bott. (Demazure-Weyl formulas, and generalization of the Borel-Weil-Bott theorem). (French)

[J] C. R. Acad. Sci., Paris, Sér. I 303, 391-394 (1986). ISSN 0764-4442

but I also got this information with a google search.

Edited to add: Look at Willie Wong's comment to the accepted answer. The above reference corresponds to the question, but the actual long article is presumably

MR980506 (90d:17024) 17B67 (14M15 17B10 20G05) Mathieu, Olivier Formules de caractères pour les algèbres de Kac-Moody générales. (French) [Character formulas for general Kac-Moody algebras] Astérisque No. 159-160 (1988), 267 pp.

Answer by thei for What are the lengths that can be constructed with straightedge but without compass?

2011-04-08T14:10:42Z

It depends on what you regard as a starting point.

For ruler and compass, we start with the points 0 and 1.

For an unmarked ruler, this is not a good start, because an unmarked ruler is good at conserving cross-ratios, but if you start with two (or three including $\infty$) points, there is no cross-ratio yet to conserve.

With a marked ruler, this problem disappears because you obviously get all the integers and then are able to construct parallel lines by building a complete quadrilateral over three equidistant points. So you already get all the rational numbers.

Answer by thei for A set with lower density equal to $0$ and upper density different from $0$

2011-04-06T10:56:30Z

For an explicit example, you could use $A= \{ n: \lfloor \log_2 \log_2{n} \rfloor \text{ is even} \} $.

Comment by thei

2012-05-09T18:18:13Z

@Junyan Xu : Thanks, I corrected it.

Comment by thei

2011-11-07T20:07:06Z

Thank you, the last two articles are exactly what I was looking for. I appreciate your useful summaries that makes me recognize them immediately. I also appreciate your other links.

Comment by thei

2011-10-31T23:01:44Z

You are actually trying to calculate the indefinite sum of terms defined by $f$ (just look at the case $a=1$), so you really should narrow down the class of functions to have summation algorithms.

Comment by thei

2011-10-31T21:56:33Z

@David Eppstein: What you write is absolutely correct, but note that in the OP we had rectangular parallelepipeds, so I mentioned the number of vertices to indicate that it is not necessary to think more about this in this case. Sorry for being both too lazy to repeat the word "rectangular" and to give the more general argument. I don't like the English term "rectangular parallelepiped".

Comment by thei

2011-05-01T09:40:51Z

They can also be the eigenvalues of the Laplacian of the graph.

Comment by thei

2011-05-01T08:43:44Z

The largest eigenvalue of which matrix?

Comment by thei

2011-04-28T00:49:29Z

I would agree with you if this were about a decision to only hire researches of B in the future. But in taking on four tenured researchers, the university has expressed an explicit commitment to the geometry group a few years ago.

Comment by thei

2011-04-28T00:26:16Z

I wouldn't concede that "you need to fire two faculty members". I would only concede that "you need to save money".

Comment by thei

2011-04-27T23:51:38Z

@Willie Wong Thanks for the info. It would be interesting to know about precedent. If this loophole is something never used in the Netherlands in practice, I would put much more emphasis in the petition on the perspective that excellent foreign mathematicians (or Dutch mathematicians in other countries) will hesitate to take a position in the Netherlands if tenure means nothing in practice and that this kind of trust will be hard to regain.

Comment by thei

2011-04-27T23:37:54Z

Furthermore, there is something strange about the text: There are two retirements, four potential firings and two new positions. That means that there are four positions eliminated in total, not two.

Comment by thei

2011-04-27T23:26:05Z

Could you explain what "tenure" means in the Netherlands?

Comment by thei

2011-04-24T18:27:09Z

Usually, people woud say that the hypergeometric function is expressed by the product, not the other way around.

Comment by thei

2011-04-23T17:16:26Z

@Spencer I think that in the oral exam case, the main problem is not the homework scenario, but simply the other student's implicit suggestion that since it was no trouble, he would not have to reciprocate in some way.

Comment by thei

2011-04-21T20:02:39Z

You have interchanged some maxs and mins and it is a bit hard to pick out the questions from your text.

Comment by thei

2011-04-21T16:53:06Z

Thanks for your comment, I have added something to the question because I suspect (and could be wrong, of course) that the author had a more exact parallel in mind.