User feldmann denis - MathOverflow

Translation of a non-standard analysis formulation

2013-01-23T21:39:41Z

Usually, it is quite easy (if cumbersome) to translate a formula like "if $\varepsilon$ is infinitesimal, and if $f$ is differentiable at $a$, $f'(a)$ is the shadow of $\frac{f(a+\varepsilon)-f(a)}{\varepsilon}$". But I cannot find a standard translation of the conjecture :"There exists a galaxy of non-standard integers containing an infinite number of primes", where galaxies are the equivalence classes of $\mathbb N$ by the relation $m\simeq n \iff (m-n)$ is standard. The closest I can find is the k-tuple conjecture (the first of the Hardy-Littlewood conjectures), but it seems obvious this is quite stronger than mine.

Differential equations and axiom of choice

2012-11-12T17:34:43Z

In the most general context, the Picard-Lindelöf theorem (aka Cauchy-Lipschitz in French) asserts the existence of a maximal solution for $\dot{x}(t) = f(t,x(t))$, i.e. of a solution $x(t)$ defined on a interval $I$ such that there exist no other solution whose restriction to $I$ coincide with $x$. The usual proofs of this (when $f$ is such that there is no local unicity) use Zorn's lemma, or some other weaker form of choice. But is this result actually not provable in ZF?

Integration in the surreal numbers

2012-04-24T06:04:47Z

In the appendix to ONAG (2nd edition), Conway points that the definition of integration (using Riemann sums as left and right options) gives the "wrong" answer : $\int_0^\omega \exp(t)\thinspace dt=\exp(\omega)$ (instead of $\exp(\omega)-1$). I wonder if this was not due to lack of some options (presumably right ones), and if a better definition could not be sought by using Kurzweil-Henstock integration (but I was not able to concoct one, of course, else I would not ask here). Has the idea already been tried?

Aronszajn trees and the transfinite subway

2012-12-20T10:15:40Z

The transfinite subway puzzle (see http://mathforum.org/kb/message.jspa?messageID=229112) is one of those clever puzzle only mathematicians can enjoy (other ones being the blue-eyed islanders puzzle (see http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/ ), or the use of axiom of choice to guess almost always the content of all but a finite number of boxes, see (in French) http://www.madore.org/~david/weblog/2009-05.html#d.2009-05-16.1643). My question (about the tranfinite subway) is : is there any relationship between this strange property of $\omega_1$ (i.e. that the subway arrives always empty) and the existence of $\aleph_1$-Aronszajn trees ?

Positive results coming from paradoxes

2012-12-15T12:11:12Z

Many examples comes to mind, the most famous being the Gödel's theorems viewed as formalisations of the Liar's paradox. I just realised that the proof of non-calculability of Kolmogorov complexity is a positive rewriting of Berry's paradox. My question (perhaps to be made into collective mode) is a) what are the best examples you know ? b) (more important) is there some explication of this productivity of paradoxes (or, conversely, do you know of paradoxes with no interesting follow-up) ?

Answer by Feldmann Denis for Examples where adding complexity made a problem simpler

2012-11-26T02:43:27Z

Quasi-periodic tilings as projections of periodic ones from a higher-dimensional space

Answer by Feldmann Denis for A question about the Axiom of Choice and straight lines in the Euclidean plane.

2012-11-22T20:46:42Z

Let $C$ the curve defined by $y=x^x$ (for $x>0$) union the point $x=0,y=1$. The set of tangents to $C$ (including the $y$ axis) satisfies the hypothesis, as the slope of those tangents grow continuously from $-\infty$ to $+\infty$, and it is impossible to draw three distinct tangents from any point of the plane. So what is wrong with this example?

I just forgot the union of the lines must be $E$ . Time to go to bed ; please delete this answer if you can. On the other hand, in this case, the union of the lines is a closed subset of $E$, so it may still be worth something

Answer by Feldmann Denis for The half-life of a theorem, or Arnold's principle at work

2012-11-15T03:21:56Z

The discovery of the Mandelbrot set by Udo of Aachen circa 1250 should perhaps count for something, no ? (see http://en.wikipedia.org/wiki/Udo_of_Aachen).

Characteristic polynomial of hypercube graph

2012-11-10T21:11:40Z

This is probably well-known, but... Define the $n$-dimensional hypercube graph $H_n$ as having for vertices the integers between 0 and $2^n-1$, and edges between integers differing by a power of 2. The characteristic polynomial of $H_n$ is then $\prod_{k=0}^n(x-n+2k)^{\frac {n!}{k!(n-k)!}}$, i.e. $(x-3)(x-1)^3(x+1)^3(x+3)$ for a cube, $(x-4)(x-2)^4x^6(x+2)^4(x+4)$ for a tesseract, etc. Is there a graph-theoretic proof of this result?

Is there a closed form for the characteristic polynomial of the graph cycle (of n edges and n summits) ?

2012-11-07T18:38:08Z

Is there a closed form for the characteristic polynomial of the graph cycle (of $n$ edges and $n$ summits)?

I know it for the graph path (it is a Chebyschev polynomial), but I couldn't find a closed form when adding the missing edge.

Tarski monster groups : which ones dont exist ?

2012-10-18T05:20:43Z

Is there any large $p$ for which it is proven that an infinite group with all non-trivial subgroups cyclical of order $p$ doesn't exist? And (if there is), which is the largest such $p$ ? All I could find is the $10^{75}$ upper bound, but I admit I didn"t look very far...

Are all compact groups amenable ?

2012-10-18T09:16:38Z

Wikipedia states that the Haar measure on a compact group is a mean (and that every compact group is amenable). But, obviously, the Haar mesure on the group of unit quaternions cannot be defined on every subset, else the Banach-Tarski paradox would not happen. What am I missing?

Banach-Tarski vs von Neumann

2012-10-03T14:09:02Z

While not so well known, the von Neumann paradox is built among the same lines, in dimension 2 and with transforms within the special linear group. But what is wrong with the following "proof" : it is not very hard to show that the group generated by the two rotations of angle $\alpha$ around $O$ and $C$, with $OC<1/100$, say, and $\alpha/\pi$ irrational and small (say $<1/100$ too), is non-abelian and free. The von Neumann construction applied to two disjoint unit discs then split them in four sets (plus a few fixed points) and sends those sets injectively, by rotations and translations, to disjoint sets included in the union of four copies of the unit disc, this union having something like 1.04 area of the disc. Obviously, this is very wrong, as the Banach-Tarski construction of a full additive measure invariant by isometries of the plane preclude such a thing. Where am I mistaken?

How large is TREE(3) ?

2012-04-12T06:35:54Z

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation denotes iteration). But actually, using the fast-growing hierarchy, $n(p)$ is smaller than $f_{\omega^{\omega^\omega}}(p)$ (shown by Friedman in http://www.math.osu.edu/~friedman.8/pdf/finiteseq10_8_98.pdf), while it seems that TREE grows faster than $f_{\Gamma_0}$ (${\Gamma_0}$ being the Feferman-Schütte ordinal). So it could well be that in fact TREE(3) is larger than, say, n(n(4)), or even any number expressible by iterations of n. What is known on this question?

Answer by Feldmann Denis for What grows faster?

2012-09-14T09:39:04Z

Much too easy for this site, and already answered. Anyway, BusyBeaver grows faster that any computable function (almost by definition); as the other two are computable... (btw, TREE grows inimaginably faster that the recursive functions you cite next). All these questions tend to show that you have not studied the fast-growing hierarchy : in this notation, Conway's $n\rightarrow n \rightarrow\dots\rightarrow n$ (with $n$ arrows) is (much) smaller than $f_{\omega^2+1}(n)$, and any "recursive" construction in the line of BEAF grows slower than $f_{\omega^\omega}$, while TREE grows much faster than $f_{\epsilon_0}$, or even $f_{\Gamma_0}$...

Is Monsky's theorem depending on axiom of choice ?

2012-09-12T20:55:41Z

The extension of the 2-adic valuation to the reals used in the usual proof uses clearly AC. But is this really necessary ? After all, given a equidissection in $n$ triangles, it is finite, so it should be possible to construct a valuation for only the algebraic numbers, and the coordinates of the summits (with a finite number of "choices"), and then follow the proof to show that $n$ must be even. Or am I badly mistaken ?

Topologies on the field of rationals

2012-09-05T16:44:35Z

Ostrowski's theorem give the answer for valuations, but is there a complete classification of (at least separated) topologies on Q (compatible with the field operations, obviously)?

Answer by Feldmann Denis for Homeomorphism of the rationals

2012-08-28T21:23:01Z

Not a really complete answer, but look at the question mark fonction (see http://en.wikipedia.org/wiki/Minkowski%27s_question_mark_function) to a counter-example satisfying 1,2,3 and 4 : $?(\sqrt2)=7/5$, for instance.

Functions with null derivative

2012-08-28T13:26:37Z

I am not here referring to the devil staircase, but to the question mark function. This is a strictly increasing function from $\mathbb{Q}$ to $\mathbb{Q}$, with derivative always $0$. I have two questions:

Is this a surprising result (in the same way that continuous functions nowhere differentiable were thought surprising when discovered)?
What are the properties preventing this (obviously, we need a topological field to speak of derivative; are there exemples of connected topological fields with non constant functions having everywhere a null derivative?)

Answer by Feldmann Denis for integrating 1/(x*sin(1/x))

2012-08-26T18:09:41Z

Try Liouville theorem ; as the obvious $u=1/x$ lend to integration of $\frac 1{u\sin u}$, it seems impossible indeed in elementary terms ; actually, Maple isn't even able to integrate it using special functions

Hales work on Kepler conjecture

2012-08-22T10:28:24Z

It seems that the Fulkerson prize has been attributed to Thomas Hales for this work. What is the present status of the conjecture, then?

Fast-growing hierarchy and Turing machines

2012-08-02T05:50:58Z

Is it possible to get an estimate of the size of a Turing machine computing $f_\alpha(n)$, for a given $\alpha$ (I am especialy interested in moderately large $\alpha$ like the ordinal of Fefferman-Schütte, or the small Veblen ordinal)? The idea is to get an idea of the size of the BusyBeaver function $BB(n)$ for moderate values of $n$, as the litterature usually only mention the exact known values (for $n\le 6$) and the fact that such values will probably never be known for $n=10$, say.

Mandelbrot set and analytic functions such that $f(az)=f(z)^2+c$

2012-05-01T16:29:57Z

It is well known that the function $f(z)=2\cos(\sqrt {-z})$ (or more accurately the entire function $f(z)=2\sum_{n=0}^\infty \frac{z^n}{(2n)!}$) satisfies such a functional equation, i.e. $f(4z)= f(z)^2-2$ ; it is not hard to show that this is the unique solution with $c=-2$ and $f'(0)=-1$. Patient calculations (see for instance this note in french), or the classical results of Tan Lei, show that this implies that the small cardioids on the left main antenna of the Mandelbrot set (on the real axis near $-2$) are in position $-2+3\pi^2/2^{2n+1}+o(4^{-n})$. It would be easy to generalise this result to other Misiurewicz points, if similar functions were known for other values of $c$, as the small copies of the $M$-set lie similarly near the zeros of these functions (after appropriate rescaling) ; it is not hard to show their existence and unicity, but have they been studied, and what is known on their zeros?

Cantor theorem on orders

2012-07-11T21:53:24Z

It is "a well-known theorem of Cantor", said Sierpinski (circa 1920), that every countable total order can be imbedded in the rationals, and he proceeds to demonstrate that, assuming the continuum hypothesis, it is possible to construct a similar "universal order" of cardinal $\aleph_1$. I have two questions : 1) Where did Cantor prove his theorem 2) Can CH be weakened in the previous result ? For reference, Sierpinski construct an ordering on binary sequences indexed by countable ordinals (up to some ordinal $<\omega_1$), having the desired property than any countable Dedekind cut is separated by some element ; this is actually the same order than the one on surreal numbers born before day $\omega_1$ (as easily shown by the Gondor construction)

Answer by Feldmann Denis for Cantor theorem on orders

2012-07-11T22:28:18Z

Sorry, almost all pertinent answers (even with the exact reference of the Sierpinski article) were given in the article http://mathoverflow.net/questions/57597/universal-order-type ; so the only question I have left is "where did Cantor state it ?"

Answer by Feldmann Denis for Computational complexity of calculating the nth root of a real number

2012-06-13T11:05:23Z

The Newton-Raphson algorithm uses, for computation of $A^{1/p}$, the sequence $u_0=A$, $u_{n+1}=u_n-\frac {u_n^p-A}{pu_n^{p-1}}$, whose speed of convergence , always quadratic, is essentially independent of $p$ (and $A$). So, mostly, it asks for $\ln p$ multiplications and 1 division at each step.

Answer by Feldmann Denis for Is the sum sin(n) bounded?

2012-06-09T11:24:34Z

In this particular case, use $s_n(\theta)=\sum_{k=0}^n\sin(k\theta)=\Im(\sum_{k=0}^n\exp(ki\theta))=\dots=\frac{\sin(n\theta/2)\sin((n+1)\theta/2)}{\sin (\theta/2)}$

Faa di Bruno's formula for inverse functions ?

2012-05-31T15:59:19Z

It is easy to get a expression for the nth-derivative of an inverse fuction ; starting from $(f^{-1})'=\frac{1}{f'\circ f^{-1}}$, one gets things like $(f^{-1})^{(n)}=\frac{\sum a_k\prod (f^{(n_j)}\circ f^{-1})^j}{(f'\circ f^{-1})^{2n-1}}$, with reasonably easy constraints on the $n_j$. But what are the values of the $a_k$? I believe I read somewhere this was an application of umbral calculus, but I dont see how, and inverting Faa di Bruno's formula on the identity $f\circ f^{-1}=id$ dont seem to get anywhere.

Answer by Feldmann Denis for Faa di Bruno's formula for inverse functions ?

2012-06-02T15:47:49Z

To precise my question, I was asking for the exact values of the $a_k$. Thanks to Tom Copeland, I could find the sequence A176740 of OEIS, giving a complete answer (with useful links) to this problem.

Answer by Feldmann Denis for The problem of finding the first digit in Graham's number

2012-05-08T05:21:43Z

Similarly, it is 1 if the base is of the shape $3^n$, with $n$ a power of 3 (less than $\ln G$) ; other cases are easy for small powers of 3. On the other hand, Graham's number is much too large for the question to be really interesting ; the determination of the first digit in base 10 of $A(9,9)$ (where $A$ is the Ackermann function) should already be inaccessible.

Comment by Feldmann Denis

2013-04-07T16:56:44Z

Have you stop beating your wife ? I would appreciate at least a yes or no

Comment by Feldmann Denis

2013-01-26T05:59:15Z

Don't you really mean "whose domain is $A$ and range $B$" ? (then, of course, you have to think of the objects of your category as sets). But of course, the answer is negative, as different morphisms can correspond to the same function.

Comment by Feldmann Denis

2013-01-21T21:14:17Z

Well, you can check if they dont have as minor one of the 16000 already known obstructions (for not too large graphs, this is less absurd than it sounds...)

Comment by Feldmann Denis

2013-01-21T18:11:37Z

"Proofs from the Book" gives the nice ($P(1)$ and ($P(n)$ implies $P(2n)$) and ($P(n)$ implies $P(n−1)$)) implies $\forall n, P(n)$ as a way to prove the general inequality between geometric and arithmetic mean (due to Artin, or perhaps Cauchy) – Feldmann Denis 0 secs ago

Comment by Feldmann Denis

2013-01-18T13:00:46Z

Inappropriate for MO. Think of cases like $a_n=1$ and $b_n=-1$.

Comment by Feldmann Denis

2013-01-07T04:35:32Z

Something is very wrong here.If any formula of this shape was correct, it would give a fast way to calculate $\pi(x)$. Check it for not too small values of $n$...

Comment by Feldmann Denis

2012-12-08T10:11:31Z

You should read the previous comments to your posts (the key word is "read")

Comment by Feldmann Denis

2012-12-01T20:50:35Z

Actually, the Grothendieck axiom of universe U is much stronger than existence of a strongly inaccessible cardinal, being equivalent to the exoistence of a proper class of inaccessibles (but it is weaker than the existence of a 1-inaccessible cardinal)

Comment by Feldmann Denis

2012-11-30T14:47:06Z

And I cannot resist to add a reference to the <a href="en.wikipedia.org/wiki/Long_line"; rel="nofollow">long line</a>, locally isomorphic to R, sequentially compact, but not compact.

Comment by Feldmann Denis

2012-11-23T13:31:33Z

$\frac{F+F^H}2$ is indeed hermitian, but why should it have the same characteristic polynomial than $F$?

Comment by Feldmann Denis

2012-11-21T12:36:28Z

As Pari/gp has been developped by Henri Cohen, I would expect it is reasonably optimal for this kind of task...

Comment by Feldmann Denis

2012-11-10T22:34:56Z

Well, actually, I am looking for things like calculations of the characteristic polynomial by manipulations of the graph (addig edges or vertices, product of graphes, ans so on), and trying to get some intuition by using well-known families of graphs. But I may be completely on the wrong track

Comment by Feldmann Denis

2012-11-08T16:33:16Z

Sorry for the misunderstanding. Yes, I wanted a closed form for the coefficients of the characteristic polynomial, but my main question was : is there a simple relation between the polynomials for graphs differing only by one edge, as in this case.

Comment by Feldmann Denis

2012-10-25T08:29:14Z

And the preface to the logic part of Nicolas Bourbaki's treaty (Ens, ch.I) says "we will not discuss here the possibility of teaching (or describing) mathematics to someone who couldn't read, write or count"

Comment by Feldmann Denis

2012-10-23T22:47:28Z

Probably, Gulbenkian thinks that the only reason a series has radius of convergence $r$ is that there must be a pole at this distance. Alas, other kinds of singularity (such as branch points) exists...