User t. - MathOverflow

Where does the "Hardy-Littlewood" conjecture that pi(x+y) < pi(x) + pi(y) originate?

2010-07-06T22:43:52Z

The conjecture that $\pi(x+y) \leq \pi(x) + \pi(y)$, with $\pi$ the counting function for prime numbers, is customarily attributed to Hardy and Littlewood in their 1923 paper, third in the Partitio Numerorum series on additive number theory and the circle method. For example, Richard Guy's book Unsolved Problems in Number Theory cites the paper and calls the inequality a "well-known conjecture ... due to Hardy and Littlewood".

Partitio Numerorum III is one of the most widely read papers in number theory, detailing a method for writing down conjectural (but well-defined) asymptotic formulas for the density of solutions in additive number theory problems such as Goldbach, twin primes, prime $k$-tuplets, primes of the form $x^2 + 1$, etc. This formalism in the case of prime $k$-tuplets, with the notion of admissible prime constellations and an asymptotic formula for the number of tuplets, came to be known as the "Hardy-Littlewood [prime k-tuplets] conjecture" and indeed is one of several explicit conjectures in the paper.

However, the matter of whether $\pi(x+y) \leq \pi(x) + \pi(y)$, for all $x$ and $y$, does not actually appear in the Hardy-Littlewood paper. They discuss the inequality only for fixed finite $x$ and for $y \to \infty$, relating the packing density of primes in intervals of length $x$ to the $k$-tuplets conjecture. (The lim-sup density statements that H & L consider were ultimately shown inconsistent with the k-tuplets conjecture by Hensley and Richards in 1973).

The questions:

Are there other works of Hardy or Littlewood where the inequality on $\pi(x+y)$ is discussed, or stated as a conjecture?
Where does the inequality first appear in the literature as a conjecture?
Is there any paper that suggests the inequality (for all finite $x$ and $y$, not the asymptotic statement considered by Hardy-Littlewood) is likely to be correct?

Answer by T. for On the elliptic logarithm and elliptic exponential

2010-08-06T01:41:50Z

The usual logarithm can be thought of as a function on the multiplicative group $\mathbb{C}^*$. The multiplicative group is a degeneration of an elliptic curve, so a natural idea is to "deform" the logarithm (or other given function) to one that makes sense on any given elliptic curve. Usually this is done by averaging over the lattice L for which $\mathbb{C}/L$ is the given curve. (It's not obvious or trivial that an elliptic analogue of any given construct exists. But one looks for it.)

Answer by T. for Meaning of Kronecker's comment to Lindemann

2010-08-04T02:24:14Z

As written, Kronecker's statement [the one quoted by Gerry] is very similar to the idea of doing analysis in "weak" formal systems, such as first order Peano arithmetic, primitive recursive arithmetic, hereditarily finite ZF, or based on informal principles that roughly correspond to such systems. That is, "completed infinite" constructs (such as the totality of Cauchy sequences, or a single unspecified Cauchy sequence, or manipulations of infinite sets) may have a nebulous status but are OK as a heuristic or a formalism as long as in each case, such as formulas involving $e$ and $\pi$, the resulting manipulations are seen to ultimately reduce to calculations that can be performed and proved in PA, or whatever the acceptable theory of finitary constructions.

This is interpreting the posted question, "what might have been the intended meaning of Kronecker", as what is a sensible reading of Kronecker's statement, and not as the historical question of what he truly, originally, demonstrably did intend.

(Added: to put this another way, Kronecker might say that $\pi$ is fine as a formalism for organizing finite computations about explicit finitely presented objects such as algebraic numbers or matrices with integer entries, but that $\pi$ by itself is more ontologically dubious. Transcendence proofs, from this perspective, are a sequence of estimates about finite integer calculations, similar to irrationality estimates of $\sqrt{d}$ using continued fractions, which are interpretable as Diophantine inequalities between positive integers. There is some sense to this insofar as, even with a modern theory of algorithmic objects --- finite computer programs such as those computing $\pi$ approximations --- $\pi$ is inevitably a higher-type object than integers; verifying any given integer formula such as 2+2=4 is a finite calculation but $e^{i \pi} = -1$ requires some form of induction, no matter how explicitly one constructs $e$ and $\pi$.)

Answer by T. for Guess a number with at most one wrong answer

2010-08-03T06:30:31Z

Some more references.

Joel Spencer's web page has several downloadable papers on searching with lies:

http://cs.nyu.edu/spencer/papers/papers.html

Ivan Niven, "Coding Theory applied to a Problem of Ulam", http://www.jstor.org/pss/2689543 , gives the Hamming code approach.

Andrszej Pelc, who solved the original Ulam liar problem with $n=10^6$ and one optional lie, also has a number of papers on extensions of the problem to more lies and to other models of searching with noisy queries: http://w3.uqo.ca/pelc/search.html

Answer by T. for What happens when we print the digits of a real number?

2010-07-30T05:55:39Z

I'm not sure what this has to do with classical versus constructive.

Classically or otherwise, you can't (today) write down a specific program and give a proof that it calculates the decimal expansion of $\zeta(5)$, a number which is defined as a Cauchy sequence with a known rate of convergence. This and similar observations are just the usual incompatibility between decimals (totally disconnected space) and the usual topology on real numbers.

Classically or otherwise, operations that don't respect equality (so are not "extensional" functions) are commonplace, as soon as one works with quotients. Examples:

Find a section of the ratio map from $Z \times (Z - 0) \to Q$: given a rational number $a/b$ (a pair of integers) compute a pair of integers whose ratio (a rational fraction) is equal to $a/b$. Here we have two options. One is to output $(a,b)$, but this doesn't respect equality in $Q$. The other is to compute a canonical form by eliminating common factors of $a$ and $b$; output $(a/g, b/g)$ where $g = \gcd(a,b)$. This does respect equality in $Q$, but I see no reason why the other procedure that doesn't give a function on $Q$ should be considered exotic.
Find a section of the quotient map of abelian groups $R \to R/Q$: given a real number $r$ (considered as equal to $r+q$ for any rational $q$) output a real number $f(r)$ with $r - f(r)$ rational. Here there is only one option: take $f(r)=r$, or $f(r)=r + q_0$ for fixed rational $q_0$. (I'm pretty sure that is the only definable or $ZF$ constructible section, for example.) Because there is no canonical form of a real number modulo rationals, there is no section that respects the equality in $R/Q$. If you like you can say that there is an operation but not a function on $R/Q$ that sections the map. But there is nothing complicated about the operation and it doesn't present any logical difficulties.

As long as a program operating on Cauchy sequences is well-defined, it "is what it is". Given a strong enough notion of Cauchy sequence one can also have a terminating program that approximates the limit to any given accuracy. On the other hand, anything that involves decimals and computations can't be done with a specific program (classically).

Answer by T. for Arctangents and the golden ratio

2010-07-29T08:36:43Z

"Welcome to $K_1( \mathbb{C}(t))$!"

The identity instantiates the fact that if $f(z)$ is a rational function, the complex, multivalued $\log(f(z))$ is a sum of logarithms of the linear factors of $f(z)$. This fact can be made single-valued (by differentiating the identity) and real (by taking the real or, in this case, imaginary part of the formula, i.e., symmetrizing under Gal(C/R) which replaces logarithm with arctangent).

Specializing the fact to $f(x)=g(ix)$, where $g(x) = x^2 - x - 1$ and $x$ is real, produces the identity with the golden ratio. The imaginary part of $\log(f)$ is $(1/2i)\log(g(ix)/g(-ix))$, which can be expanded as a sum over the roots and differentiated.

(Remember also that $\arctan t = \arg (q+itq)$ for real $t$ and $q$, so that $\log f(x)$ can be evaluated without factorization, by computing real and imaginary parts of $g(ix)$. Equating the two expressions for the imaginary part of ($d\log(f)$) gives the formula in the question.)

Answer by T. for What is a reasonable finitary analogue of the statement that harmonic functions are smooth?

2010-07-28T03:44:39Z

There are quite a few properties shared by discrete and continuous harmonic functions. They also generalize in various forms to graphs. I don't know if the analogy is so close that there is a unique concept of smoothness for the discrete case, but see the last item for one point of contact.

Poisson formula: $f(p)$ is a weighted average of the values of $f$ on a "curve" of points surrounding $p$ (that is, a minimal set of points disconnecting it from infinity). As in the continuous case the weighting is the distribution of hitting probabilities, $h_p(x,y)$ = probability that a random walk started at $p$ first hits the curve at $(x,y)$.
Maximum principle. Because values in the interior are weighted averages of values on the boundary.
Growth constraints. A bounded discrete-harmonic function is constant. More generally there is a discrete analogue of the theorem that if a harmonic $f(x,y)$ has polynomial-bounded growth, $|f(x,y)| < C(|x|+|y|+1)^n$ then $f(x,y)$ is a (harmonic) polynomial in $x$ and $y$, of degree at most $n$.
Harnack inequalities. It is these that are a form of smoothness. They say that if $a$ and $b$ are nearby points far away from the boundary curve used in the Poisson formula, $f(a) - f(b)$ is small (relative to $|f|$ on the boundary). There are many expressions of this principle, see for example papers of Fan Chung and her collaborators ( www.math.ucsd.edu/~fan ) for inequalities in the case of graphs with a vertex-transitive symmetry group. By phrasing the theory in terms of eigenfunctions of the Laplacian one can give the discrete and continuous Harnack inequalities a very parallel form. But in the discrete case they also seem to play a more basic role of showing that smoothness is present in some form, which in the continuous case is automatic because $f$ is assumed to have at least two derivatives.

Answer by T. for The unprecedented success of the “intersection” operator

2010-07-26T08:42:52Z

When property P is universal ($\forall ...$) it is likely to correspond to closed sets, and thus be preserved under intersection. Examples: axioms of a group, ring, field, directed graph; having symmetry under a given group.

However, if P is existential ($\exists ...$) it corresponds to open sets and is more likely to be preserved by unions (or products), not intersections. Examples: being algebraically closed, having at least 53 elements. (Well, algebraic closure is $\forall \exists$ so of course it is even more complicated. But falling out of the pure $\forall$ class it fails the intersection property.)

The first situation is possibly more common because we want structures to satisfy some, well, structural properties. Properties expressed by equations usually correspond to closed sets.

To some extent this is formalized in Birkhoff's theorem On equational presentations. Any book on Universal Algebra will discuss it.

Also, the sample of concepts is biased, because definitions that become standard are often selected for their useful formal properties. Concepts not having stability under intersection (or union, or inheritance by sub- or super-structures) are less likely to be used.

Answer by T. for Looking for a probability distribution

2010-07-25T23:55:40Z

This is equivalent to (among other names) the Coupon Collector problem. Your are asking about the distribution of the number of coupons collected after $t$ steps, when the total number of possible coupons is $n$.

http://en.wikipedia.org/wiki/Coupon_collector%27s_problem

ADDED: this and related distributions are also studied under other names such as Birthday Problem, random mappings, and random hashing. Kolchin-Sevastyanov-Chistyakov Random Allocations, Knuth The Art Of Computer Programming, vol. 2, and Flajolet & Sedgwick Analytic Combinatorics all discuss these problems and may contain the precise asymptotics of the distribution you are looking for.

Answer by T. for Implications of the abc conjecture in Arakelov theory

2010-07-25T19:31:41Z

ABC is equivalent to the conjectured height inequality that Lang (or more precisely Vojta, in an appendix to Lang's book, following the ABC appendix he wrote for his own book) uses. This is shown in several papers by van Frankenhuijsen.

http://research.uvu.edu/machiel/papers/abcrvhi.pdf

http://research.uvu.edu/machiel/papers/ABCRothMord.pdf

http://research.uvu.edu/machiel/bibliography.html

So ABC is equivalent to some of Vojta's conjectures in arithmetic geometry.

Also, Elkies' "ABC implies effective Mordell" is a sort of counter-application in that it shows that, given the ABC conjecture, one does not need Arakelov methods to prove the Mordell conjecture.

http://imrn.oxfordjournals.org/cgi/pdf_extract/1991/7/99

Lang wrote an article on Diophantine inequalities related to ABC that outlines some of the relationships between conjectures that were known 20 years ago.

http://www.ams.org/bull/1990-23-01/S0273-0979-1990-15899-9/S0273-0979-1990-15899-9.pdf

Answer by T. for Limit of a discrete time dynamical system

2010-07-21T20:07:32Z

The continuous model of the problem suggests that the limit does depend on $f$ (and $u$). More precisely, it depends on how fast the parameter $f$ is suppressed in the expression whose limit you are taking; behavior of $\lim y(nt, f_n)/n$ will depend on the limit of $nf_n$ as $n \to \infty$. The answer will be a function of the limit of $nuf_n$. Only when this limit is zero does one get the proposed formula.

The associated differential equation is $Y' = 1/(1+Ae^{BY})$ where $A = e^z$ and $B=uf$. Its solution vanishing at 0 is $Y(t) = H^{-1}(t)$ where $H(t) = t + (A/B)(e^{Bt} - 1)$. It does look like this matches the asymptotic behavior of your sequence for $y$ both in the large and small range. For small $t$, the expansion $Y(t) = t/(1+A) + O(t^2)$ corresponds to your formula, but I think the answer is not quite that simple: you have to establish whether the expression whose limit is calculated belongs to the small regime where $Y(t)$ is approximately linear, or the large regime where $Y(t)$ is logarithmic, $Y(t)=O(\log(t))$. The limit uses $n$ iterations so we want to know, as a function of $B \sim 1/n$, whether the transition between regimes happens at a point much larger than $1/B$. However, it's easy to calculate that the ratio $H(t)/t$ moves away from 1 (the difference is larger than some constant independent of $B$) as soon as $Bt$ is of order 1 (i.e., bounded below by a given positive constant) and this would spoil the limit if the differential equation is a good model of the difference equation.

(ADDED: for comparison of $Y$ predictions with $y$ simulations, in the phase transition where $Bt$ is of order 1, $Y(t) \sim t/C$ and $H(t) \sim Ct$, with $C = 1 + A(e^q - 1)/q$, and $q = Bt =uft$. That is, $Y$ stays approximately linear but the coefficient goes to zero, consistent with the idea that it's turning into a logarithmic function. Let $t=nt_0, \quad f=f_0/n$, for some constant $f_0$ and with $u$ and $t_0$ also held constant while $f$ varies with $n$, so that the phase transition parameter is $q=uf_0 t_0$ and the predicted value of the limit, if $Y$ is a good approximation for $y$, is $L_{pred} = \lim Y(nt_0,f_0/n)/n = \lim nt_0/nC = t_0/C = t_0(q/(q + Ae^q - A))$. In the original notation of the question, $L = t/(1+{e^z}F(uft))$ where $F(x)=(e^x-1)/x$. Does this match the simulations?)

To see the small-$y$ behavior directly in the difference equation, it can be expanded in powers of $y$.

$y(t+1) - y(t) = 1/(1+A) - (AB)/(1+A)^2)y + O(y^2)$

Your formula proposes that when $B \sim 1/n$, the effect of the $y^{\geq 1}$ terms is of order smaller than $n$ for $t \in [0,n]$. The sum of the first $t$ values of the $y^1$ term will be of order $t^2$, so one expects these corrections to be suppressed only on a short interval, $t << n^{1/2}$. The calculation with the differential equation suggests that $f_n = f/n$ is too large a parameter ; this calculation with the truncated difference equation can be used to prove that $f_n = f/n^k$ is small enough for any $k > 2$. Adding higher degree terms to the approximate difference equation would, I suppose, only get closer to the picture suggested by the differential equation.

To prove rigorously the predictions from the differential equation you could try to control $y$ by trapping the sequence $y(n)$ between two trajectories of the ODE. If simulations are consistent with a heuristically "wrong" formula it would be very interesting to sort out what the truth is.

Answer by T. for Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?

2010-07-15T02:32:58Z

One can write a program that, given enough time, will eventually detect the presence of zeros off the critical line if any exist, by computing contour integrals of $\zeta' (s)/ \zeta(s)$ on a sequence of small squares (with rational vertices) exhausting increasingly fine finite grids that cover more and more of the critical strip to greater and greater height.

From the formulae for analytic continuation of $\zeta (s) $ one can extract effective moduli of uniform continuity and from that one can approximate the integral by dividing each side of the square into some large number of equal pieces, approximating the function at those rational points, and calculating the Riemann sum. The necessary accuracy can be determined from the modulus of continuity and formulas for $\zeta$.

(The grids I have in mind come within $1/n$ of the sides of the critical strip, with height going from $0$ to $n$, and are divided into squares of size $1/n^2$, so eventually any zero will be isolated inside one such square.)

EDIT: to express RH in Peano Arithmetic, there are two ways.

One is to use Matiyasevich (sp?) theorem that for any halting problem one can construct a Diophantine equation whose solvability is equivalent to halting. Or in the same vein, use Matiyasevich/Robinson approach to Diophantine encode an elementary inequality equivalent to RH, as was done in Matiyasevich-Davis-Robinson's paper on Hilbert's 10th Problem: Positive Aspects of a Negative Solution. Another way is to express enough complex analysis in Peano Arithmetic to carry the contour integral argument above, which can be done because ultimately everything involves formulas and estimates that can be made sufficiently explicit. How to do this is explained in Gaisi Takeuti's essay Two Applications Of Logic to Mathematics.

EDIT-2: re: verifications of RH, the ZetaGrid distributed computation checked that at least the first 100 billion (10^11) zeros, ordered by imaginary part, are on the critical line. The zero computations are opposite to the $\Pi_1$ approach: instead of falsifying RH if it's wrong, if run for unlimited time they would validate RH as far as the program can reach, but could get stuck if there are double zeros anywhere. The algorithms assume RH and whatever other conjectures are useful for finding zeros, such as the absence of multiple roots, or GUE spacings between zeros. Every time they locate another zero, a contour integral then verifies that there are no other zeros up to that height, and RH continues to hold. But if there is a double zero the program could get stuck in an endless attempt to show that it's a single zero. Single zeros off the line would be detected by most algorithms, but not necessarily localized: once you know one is there you can take a big gulp and run a separate program to find it precisely.

(Concerning the philosophical interest of the $\Pi_1$ formulation of RH, see also the comments under the question.)

Answer by T. for Does anyone know a polynomial whose lack of roots can't be proved?

2010-07-22T05:33:23Z

This question is frequently asked, usually in relation to the Riemann hypothesis or the consistency of set theory. I suppose this is as good a place as any to collect references to explicit arithmetizations of initially non-Diophantine problems, as (systems of) Diophantine equations.

In one of his earlier papers, Matijasevich gives an example of a Diophantine equation expressing a number-theoretic statement, different from the ones on the path to Hilbert's 10th problem. The ones on the path were his breakthrough "$m = F_{2n}$" and the universal Diophantine predicate, "machine $m$ halts in time $t$ on input $n$". The illustrative example was something like "is a prime number", not anything as complicated as consistency of ZFC. The universal equation can be specialized by a choice of $m$ and $n$ to an equation expressing inconsistency of ZFC, but actually writing down specific values accomplishing that translation would be a formidable task. (ADDED: the paper is online at http://www.springerlink.com/content/m5k0281k67r46325/ )

J.P. Jones has several papers, some with Matijasevich, providing Diophantine encodings of other number theoretic statements. Website: http://math.ucalgary.ca/~jpjones/papers.htm

The long paper by Davis, Robinson and Matijasevich gives Diophantine representations of the Riemann Hypothesis and of "$p$ is a prime number" from which one can write down the Goldbach conjecture, or near-equivalents of the Twin Primes conjecture. Most of it is online at: http://books.google.com/books?id=4lT3M6F745sC&pg=PA323

I don't know if (in)consistency of ZFC has been displayed in print as a Diophantine equation. There may be computer programs available to perform the transformations from ZFC parser to Turing machine to Diophantine representation, and if so, their possibly very large output would answer the question. If you are willing to allow exponentiation as a primitive, as Goedel did in his paper, Gregory Chaitin made software available to construct a huge exponential Diophantine equation, similar to the one printed in his book, whose solution set is algorithmically random when projected onto one of its variables. The Matijasevich-Robinson encoding of $a=b^c$ could then be applied, to produce an ordinary, but even larger, Diophantine statement.

Answer by T. for When is something too big to be a set?

2010-07-20T23:39:39Z

This has nothing to do with being "too big to be a set". There is no logical difference between the tensor product construction for vector spaces, and constructions such as $X \times Y$ or $S \to 2^S$ for sets. The latter don't raise questions of being unsetlike due to quantifying over all sets, because they aren't construed as extensional functions with domain the set-of-all-sets. Instead, they are function definitions in set theory, i.e., provable formulas of the form "for all $X,Y$, there exists a unique $Z$ such that ...".

For any sets $U,V$ and $W$ the collection of maps from $U \times V \to W$ is a set. The same is true if the sets have the additional data of vector spaces and the maps are required to be bilinear. "Bilinear maps from $U \times V$" can be construed as a function, or a functor, taking a set $W$ as input and producing the set of bilinear maps into $W$ as an output. This is well-defined and well within the realm of sets. (ADDED: this means that set theory can prove a set of maps exists as a function of $U,V$ and $W$; "for all $U, V, W$ there exists a unique $H$ such that ...".) There is also the construction of a universal object $W_0$ as the target of such bilinear maps, and the discussion of whether an unspecified collection of bilinear maps is too big may be just a way of motivating the generators-and-relations construction (which is big, but not too big or too vague to be a set).

Constructions that seem like they might bump against the ceiling of the universe of sets are dealt with by more technical means, such as Quillen's small object argument, or explicitly tracking the cardinalities that can arise. In this case it is a matter of pure linguistics and not of any object being gargantuan.

Answer by T. for Are there more Nullstellensätze?

2010-07-21T03:40:05Z

Pete, a Nullstellensatz-like result for finite fields is the "Combinatorial Nullstellensatz" formulated by Noga Alon, and it does imply the Chevalley-Warning theorem. Searching for CN will produce Alon's paper and several others on the first page of results.

Answer by T. for What is the standard notation for a multiplicative integral?

2010-07-20T23:17:11Z

This type of construction also arises in topology and algebraic geometry as "iterated integrals" or "Chen's iterated integrals". There are many sources of which a famous one by Chen himself is: http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.bams/1183539443 .

Path-ordered (or time-ordered) exponential, as suggested in the other answer, is the most common term, or at least would get the most hits in a search, but this is due to the usage in physics.

ADDED: this paper by Hain (Chen's student) calls the construction "iterated line integrals". http://arxiv.org/abs/math.AG/0109204 . Another paper calls it "iterated integrals" in a more specific context matching that of the question: p.21 of http://www.math.toronto.edu/drorbn/papers/OnVassiliev/OnVassiliev.pdf .

Answer by T. for On a theorem of Jacobson

2010-07-15T21:13:47Z

Herstein proved that $S$ can be enlarged to the set of all $a^2 p(a) - a$ with $p$ a polynomial (with integer coefficients).

EDIT. Herstein's set may be maximal. The set can't contain any polynomials whose vanishing would be consistent with the ring containing (nonzero) nilpotent elements, so nothing in $S$ can be divisible by $a^2$. The lower degree terms are also highly constrained by the condition that if there is $p$-torsion then no $p^2$-torsion.

Answer by T. for Theorems which say "such and such method cannot possibly prove FLT"

2010-07-14T22:25:46Z

There is also the relative approach, which is to show that making Method X work is at least as difficult as solving some set of known hard problems, due to relatively simple reductions between the problems. This is what has been done for the P=NP problem --- thousands of NP problems are computationally equivalent to each other --- as well as the Riemann Hypothesis which has a large number of known equivalents. If you had the bright idea of replacing the non-elementary Riemann zeta function and statements about its zeroes by statements about the distribution of primes, or sums of the Moebius function, then the translation between those contexts is known and much easier than the theory of the zeta function itself, so there would have to be some elementary idea that people had missed in each and every one of those equivalent environments.

For example, if Method X = "prove an effective form of the ABC conjecture" (the non-effective form implies FLT for large exponents using a few lines of algebra), then solutions of dozens of hard unsolved problems, and easier proofs of very hard theorems, would be assured as soon as one could carry out Method X. Because the reductions of these problems to the ABC conjecture are often quite simple, any elementary idea used to carry forward Method X would immediately translate into elementary methods for the dozens of other problems, and it is less likely that nobody would have ever noticed this in any of the other actively studied problems.

Answer by T. for Bourbaki's epsilon-calculus notation

2010-07-14T00:22:37Z

Matthias' polemics are funny at points but also misleading in several respects:

ZFC also has enormous length and depth of deductions for trivial material. According to Norman Megill's metamath page, "complete proof of 2 + 2 = 4 involves 2,452 subtheorems including the 150 [depth of the proof tree] above. ... These have a total of 25,933 steps — this is how many steps you would have to examine if you wanted to verify the proof by hand in complete detail all the way back to the axioms." Megill's system is based on a formalism for substitutions so there may be an enormous savings here compared to the way in which Matthias performs the counts (i.e., the full expanded size in symbols) for Bourbaki's system. If I correctly recall other information from Megill about the proof length he estimated for various results in ZFC, the number of symbols required can be orders of magnitude larger and this is what should be compared to Matthias' numbers.
The proof sizes are enormously implementation dependent. Bourbaki proof length could be a matter of inessential design decisions. Matthias claims at the end of the article that there is a problem using Hilbert epsilon-notation for incomplete or undecidable systems, but he gives no indication that this or any other problem is insurmountable in the Bourbaki approach.
Indeed, Matthias himself appears to have surmounted the problem in his other papers, by expressing Bourbaki set theory as a subsystem of ZFC. So either he has demonstrated that some reasonably powerful subsystems of ZFC have proofs and definitions that get radically shorter upon adding Replacement, or that the enormous "term" he attributes to the Theorie des Ensembles shrinks to a more ZFC-like size when implemented in a different framework.

EDIT. A search for Norman Megill's calculations of proof lengths in ZFC found the following:

"even trivial proofs require an astonishing number of steps directly from axioms. Existence of the empty set can be proved with 11,225,997 steps and transfinite recursion can be proved with 11,777,866,897,976 steps."

and

"The proofs exist only in principle, of course, but their lengths were backcomputed from what would result from more traditional proofs were they fully expanded. ..... In the current version of my proof database which has been reorganized somewhat, the numbers are:

empty set = 6,175,677 steps

transf. rec. = 24,326,750,185,446 steps"

That's only the number of steps. The number of symbols would be much, much higher.

Answer by T. for Correlation and Causation. When can we believe correlation (reasonably, at least) imply causation

2010-07-13T20:07:28Z

Correlation (assuming its existence is correctly detected) does imply shared dependency on one or more other variables. From enough data you can also detect whether $Y$ is (close enough to being) a function of $X$ alone, and absence of causation, where some sets of variables are independent of others. Beyond that you need to consider specific mechanical models of what-causes-what and the data available may or may not be enough to answer that. As others mentioned there are formal analyses of this problem by people doing statistics and machine learning, e.g., in Pearl's book.

Answer by T. for Strengthening the Induction Hypothesis

2010-07-13T19:25:10Z

I think the role of the base case of the induction is crucial and should be separated from the analysis.

Conceivably you could get some proof-theoretic understanding of "induction without the base", i.e., the phenomenon of how strengthening property $P_{\rm weak}$ to $P_{\rm strong}$ can make the implication $P(n) \to P(n+1)$ easier to prove. However, $P_{\rm strong}(1)$ and $P_{\rm weak}(1)$ are different, and it is hard to imagine how a theory of the base case could possibly be set up. Maybe when considering families of $P$ something could be said, but otherwise one is up against the full strangeness of the finite and accidental.

Answer by T. for Theorems which say "such and such method cannot possibly prove FLT"

2010-07-13T06:44:57Z

Ruling out Method X is generally much harder than Method X itself, so one shouldn't necessarily expect that for any method that won't work a "certificate" can be found establishing its insufficiency. With that said:

There are plenty of environments (rings) where the algebraic equation in FLT makes sense, but has solutions. If the ingredients of Method X apply in one such environment, they aren't using specific enough properties of the integers to prove FLT. It is well known that if Method X = congruences (reduction modulo $t$ for different values of $t$), then this argument works in rings of $p$-adic numbers where FLT has solutions. Similarly, if Method X = inequalities, then it would have to rule out the positive real solutions of $x^n + y^n = z^n$.

Another possibility, requiring much more knowledge, would be to use the close relations between FLT and elliptic curves (Frey, Wiles, etc) to project method X onto the canvas of Wiles' proof and see how much of it can be understood and delimited in those terms. It could be that X is in effect trying to construct nontrivial objects of a certain kind (esp. cohomology classes) and one can see in light of Wiles methods that the relevant classes are zero, necessary field extensions or coverings are trivial, important obstructions are not killed, etc. This approach stays within environments where FLT is true, but tries to subsume Method X within existing lines of attack, and show that it only includes a part of what is needed.

Another idea is "reverse mathematics", to represent Method X as formal derivations in some weak system Y of arithmetic, and show that FLT is of higher proof theoretic strength (because it implies all the theorems of an even stronger system Z). This is unlikely because FLT is too specialized a statement and the proof-theoretic calibrations of strength only work for reasonably generic theorems with a lot of parameters that can be varied.

EDIT: I should add that each of these approaches has been pursued for showing that the P=NP problem doesn't have elementary solutions. The Baker-Gill-Solovay theorem demonstrated that environments (oracles) exist where P=NP has a different answer but simple methods of proof would continue to work. The Razborov-Rudich "natural proofs" paper showed that any proof sharing certain features of all the arguments then known (for proving lower bounds on circuit complexity) couldn't produce bounds growing faster than any polynomial. And there are weak formal systems whose most general class of definable languages or constructible functions is exactly P or NP; Stephen Cook himself has many papers on the logic/formal-systems approach to P=NP.

Answer by T. for Statistics for mathematicians

2010-07-13T07:52:43Z

Wasserman's All Of Statistics seems concise and useful.

Answer by T. for How would you solve this tantalizing Halmos problem?

2010-07-12T19:19:27Z

Denote by $R$ the ring containing $a,b$ and a solution $X$ of $(1-ab)X = X(1-ab) = 1$.

The subring of polynomial expressions in $a$, $b$ and $x$ (let us keep it flexible initially whether we want $Z$ or $R$ coefficients) is a quotient of the universal example: the polynomial ring on $a,b$ modulo the equations stating that $X$ inverts $1-ab$. If $(1-ba)$ is invertible in the universal ring this fact will descend to the quotient. The universal example embeds into the same universal gadget made using formal power series in place of polynomials, as the set of series whose terms are eventually zero for large enough degree. In the larger universal ring the inverses of $(1-ab)$ and $(1-ba)$ can be identified explicitly as series in $a$ and $b$, the formal calculations are legitimate, and they show that these two inverses satisfy a relation with coefficients in $Z\langle a,b \rangle$. This relation allows one to define an element $Y$ in $Z\langle a,b,X \rangle$ which is inverse to $(1-ba)$.

Possibly there are buried subtleties one needs to overcome in passing between the different rings, subrings and quotients involved. But at a minimum, this argument shows that convergence questions are superfluous and the series calculations rigorizable.

Answer by T. for Heuristic justification for Goldbach's conjecture

2010-07-12T18:10:27Z

A few thoughts.

The $\mu$-ratio statement, assuming it can be formalized, does not lead to quantitative predictions. In this sense it is not comparable to the density heuristics leading to Goldbach and a host of other asymptotic predictions in number theory.
It seems overwhelmingly likely that the $\mu$-ratio, if it exists in a suitable sense, is 1 or 0. I would guess that the value is $1$ and that this is an elaboration of the existing probability arguments for Goldbach.
For the state of the art in Goldbach heuristics, see Andrew Granville's paper "Refinements of Goldbach's conjecture,and the generalized Riemann hypothesis" and subsequent corrigendum.

Answer by T. for When did the career of 1 as a prime number begin and when did it end?

2010-07-07T00:01:00Z

Not a historical answer, but...

Ruminations on the "field with one element" are in a sense including 1 (and powers of 1) in the set of prime powers.

Also, in quantum groups (loosely speaking, one-parameter deformations of groups) the $q=1$ limit recovers the group while $q$ a root of unity is related to phenomena in prime characteristic $p$ > 0.

There is also the Krasner - Kazhdan - Deligne philosophy of "fields of characteristic $p$ as limits of fields of characteristic 0", recently and somewhat speculatively related to the field of one element in arxiv papers of Connes and Consani.

Answer by T. for Is there a progress on a solution of the inequality $\pi (m+n)<= \pi (m) + \pi (n)$

2010-07-05T19:12:56Z

The historical highlights for this conjecture are:

1923 : Hardy and Littlewood's classic paper, Partitio Numerorum III, elevates an obvious question to a conjecture. More precisely, H & L note that $\pi(x+y) \leq \pi(x) + \pi(y)$ (for large enough $y$) is "forcibly suggested" by the data for $x,y \leq 200$; prove some upper and lower bounds on the (lim sup) densest packing of primes in an interval of length $x$; calculate the densest packing for $x=35, 59$ and $97$; and finish with the remark that "beyond $x=97$ it would seem that [the densest packing] falls further below $\pi(x)$, at least within any range in which calculation is practicable". These speculative comments from the paper become known as a conjecture.

1973 : Ian Richards and his doctoral student Douglas Hensley explode the conjecture by showing that it contradicts the (much more plausible) prime k-tuplets conjecture

2004 to today: Green-Tao theorem and later developments lead to proofs of statements similar to the k-tuplets conjecture, giving hope that "moral certainty that H-L 1923 is false" can be replaced by "a proof that k-tuplets conjecture is true (and HL1923 is therefore false)".

The $\pi(x+y)$ conjecture never had much evidence for it. Hensley and Richards set out to disprove it by a computer calculation. They ended up proving the existence of subsets $D$ of {1,2,...,$n$} denser than the first $n$ primes ($|D| > \pi(n)$) and with no congruence obstruction to $x + D$ being a set of primes for infinitely many $x$ (for no prime $p$ do the elements of $D$ fill all congruence classes modulo $p$). Sets free of congruence obstructions are called "admissible prime constellations" and the other more credible conjecture of Hardy and Littlewood is that for any admissible constellation, infinitely many copies exist in the primes. For $D$ this implies that for infinitely many $x$,

$\pi(x+|D|) - \pi(x) \geq |D| > \pi (D)$.

The optimal example (according to http://www.opertech.com/primes/k-tuples.html ) is with $n = 3159, |D| = 447 > \pi(n) = 446$, so conjecturally,

$\pi(x+3159) > \pi(x) + \pi(3159)$ infinitely often, with the number of examples less than $N$ being of order $cN/(\log N)^{447}$

Hensley and Richards' technique for constructing dense constellations of primes is to take all the primes and their negatives in a symmetrical interval $[-K,K]$, and delete enough of the first few primes to prevent congruence obstructions. They proved that this construction is, infinitely often, denser than $\pi(2K+1)$.

Answer by T. for Why is a topology made up of 'open' sets?

2010-07-02T01:42:36Z

Topology can be defined directly, without open sets, as the study of "metric spaces without the metric", i.e., modulo metric deformations or homeomorphism. This matches reasonably well the intuition of a qualitative geometry, insensitive to stretching and bending.

One can then prove that the structure of open sets is a complete invariant (since we start from metrizable spaces), and one can observe, with some experience, that reasoning about the topology of metric spaces (i.e., proofs of properties that are invariant under deformation or homeomorphism) can be formulated directly in terms of this invariant. In other words, not only the topologically invariant maps but the constructions of those maps descend to the category of topological spaces in terms of open sets. This means that we can work natively in manifestly topologically invariant terms provided that the invariant thing --- the structure of open sets --- is taken as the object of study. This is a rare case of a total or near-total success of the Erlangen program, where thinking in terms of that which is invariant really suffices for the original purposes of the subject.

(I say near-total, but don't know of any example where topologically invariant properties of a metric spaces are most easily proved using one or more metrics.)

Once topology is set up in terms of open sets one can look at examples beyond the motivating intuition, such as Zariski topology, the long line or pathological spaces. As far as those extensions start to challenge the adequacy of the open-set formalism it is because they are based on phenomena different from the stretching and bending ideas abstracted from picturesque low-dimensional situations.

Answer by T. for Do there exist nonconstant functions such that...

2010-06-30T20:33:40Z

The following calculation suggests that a nice probability interpretation may exist for any solution one can construct.

$u(x) = f(x) - v/g(x)$ and all its $x$ derivatives are linear functions of $v$ with coefficients that are functions of $x$.

Thus, to have an extremum at $x=v$ the first derivative $u'$ must be of the form $(v-x)M(x)$. Integrating the $v$-degree 0 and 1 parts of this equation produces $f$ and (the reciprocal of) $g$. Algebraically this will be equivalent to Gerry's solution.

The interesting points are that:

To have a maximum we need $M(x) \geq 0$, so $M$ can be interpreted as a density.
The total mass $\int M$ has to be finite in order for $g(x)$ to exist on the whole real line. This is so that we can choose a constant of integration larger (in absolute value) than the total mass, when computing $1/g = C + \int M$. Thus, $M$ is a sort of probability measure, and literally is one when $\int M = 1$.
$f$ is calculated as integral of $xM$, ie., an expected value of $x$.
$1/g$ is calculated using the integral of $M$, ie., a probability.

So there might be a simple probability inequality lurking behind most of the solutions.

Answer by T. for Origin of symbol l for a prime different from a fixed prime?

2010-06-30T18:36:56Z

The possibly incorrect folk understanding (which may be just the background you assume for your question) is that Weil set the tradition in place by choosing $\ell$ or $l$ as the prime different from $p$. He did this (at least) when considering Galois action on torsion (or cohomology) of elliptic curves and/or Abelian varieties and through the French school of algebraic geometry and number theory it propagated universally. Or so the folklore goes.

Comment by T.

2011-01-04T07:20:45Z

I'm not assuming any specific model, but pointing out that differences between your answer and 1/2 arise from artificial (i.e., gender-asymmetric) conditioning of the problem. Assuming $k$ families as in Zare's model or your present suggestion, is equivalent to assuming "at most $k$ boys in population", or exactly $k$ boys if it is also assumed the families complete their reproduction. No such asymmetric conditioning was part of the Google problem. Your calculations show that a symmetrical distribution can be approximated by asymmetric ones, not that the Google problem is asymmetric.

Comment by T.

2011-01-04T06:05:40Z

Steven, that is incorrect. The issue is whether the proportion of boys, denoted $f(B,G)$ above, is convex as a function of two variables so that $E[f(B,G)] > f(E[B],E[G]) = 1/2$. It isn't convex, as simple calculations demonstrate. (See the comments on convexity and Jensen's inequality under Douglas Zare's posting). It is convex if you condition on B (i.e., restrict f to lines B=constant), and concave if you condition on G. Such conditioning is foreign to the Google problem and imposed artificially in Doug's model.

Comment by T.

2011-01-04T05:40:23Z

Ratios versus differences doesn't address the main point, which is whether the family reproduction rule can break boy/girl symmetry in the underlying distribution of $(B,G)$. [It does gender-asymmetrize the allocation of boys and girls into sets called "families", but this extra structure does not play a role in the calculation requested by Google.] If the distribution is symmetrical then the proportion of girls will have expected value 1/2, because the random variables "proportion of girls" and "proportion of boys" will have the same probability distribution, and their sum is equal to 1.

Comment by T.

2011-01-03T14:17:59Z

@DZ: the statement "[allowing unfinished families] ... there is a higher proportion of girls when the population is larger" is in general false. It is true only in your a priori asymmetrical model conditioned on the number of families. The asymmetry arises not from the stopping rule, but because the stopping rule allows phrasing of boy/girl asymmetric conditions ("the number of boys is at most $k$") in equivalent terms without direct reference to $B$ or $G$ (i.e., "the number of families is $k$", as in your model allowing unfinished families). This asymmetry is foreign to the Google puzzle.

Comment by T.

2010-09-18T07:08:36Z

As a point of comparison, there was recently a 60-70 year old who solved a notorious open problem in graph theory, the Road Coloring Problem. However, this man held a doctorate and a professorship in mathematics, and although he may not have solved any major problems before age 60 (or maybe he did, I don't know), he was known, as evidenced by publications, to have been working on the problem for years earlier with partial results, and on other mathematical problems. He did not suddenly take up engineering after no sign of interest in 30 yrs and claim to build an ultra-efficient automobile.

Comment by T.

2010-09-18T06:38:57Z

@Pete, @BCnrd: I'm seeing this a few days late, and am not yet a user of meta.MO. Age by itself is irrelevant but in conjunction with the other data does contribute to an initial assessment of the work, for reasons that have nothing to do with pejorative or discriminatory attitudes toward the elderly. When someone has no known training or publication in the field (but does in antigravity "physics") claims a breakthrough as the first visible sign of math research, at age 60 it suggests that 30+ years of prior opportunity to engage with math were not taken. Which is another warning sign.

Comment by T.

2010-09-09T18:35:58Z

Leading indicators on the paper: uninformative abstract. "Interesting" search engine results for the author's name (antigravity propulsion, degrees not in math, 60 years old, etc). Breakthrough if correct, but was not publicized. Appears in an obscure journal.

Comment by T.

2010-09-04T08:15:50Z

Historical examples tend to retroactively attribute stupid errors that were not the original, and still subtle, issue. In 3 and 7 the equivalences are not geometric (see Feynman's deconstruction of Banach-Tarski as "So-and-So's Theorem of Immeasurable Measure"). For #1, Riemannian geometry doesn't address historical/conceptual issue of non-Euclidean geometry, which was about logical status of the Parallel Axiom, categoricity of the axioms, and lack of 20th-century mathematical logic framework. Zeno's contention that motion is mysterious remains true today, despite theory of infinite sums.

Comment by T.

2010-09-04T07:58:53Z

In physics, having a formula or approximation scheme depending on N parameters (= dim. of phase space) shows existence and uniqueness locally, with global questions of singularities, attractors, topology etc understood by calculation and simulation. For classical ODE this is almost always enough and there are very few cases where careful analysis and error estimates overturned accepted physics ideas. There are more cases where physics heuristics drove the mathematics and some where they changed intuitions that prevailed in the math community.

Comment by T.

2010-08-10T05:01:29Z

duplicate of mathoverflow.net/questions/33055/…

Comment by T.

2010-08-06T04:54:39Z

Gerry, Kronecker's quotation that you cited is in effect saying that (1) "general" irrational numbers don't exist [i.e., are not meaningful mathematically], but (2) specific constructs like $\pi$ and $exp(\sqrt{163}$ are not problematic, insofar as they are a shorthand for explicit controlled sequences of finite calculations, and (3) it is harmless but optional to construe those "specific" irrationals as numbers that genuinely exist.

Comment by T.

2010-08-06T04:39:01Z

The elliptic objects don't parametrize elliptic curves, they are parameterized by elliptic curves. For each lattice L in the complex plane one gets a logarithm function Log(L,z). When the elliptic curve (genus 1) is varied so as to tend to a singular curve (genus 0) the elliptic object is supposed to degenerate to the usual, non-elliptic object. In this paradigm, the "object" can mean: logarithm, exponential, gamma function, quantum group, integrable model, etc. These all have elliptic analogues.

Comment by T.

2010-08-05T22:13:32Z

I don't think anyone but Wolfram uses the term or the letters NKS. A "wolfram" tag would be more recognizable for those wanting to seek or avoid this content.

Comment by T.

2010-08-04T22:36:16Z

+$n$; thanks for the debunking. However, there remains the same question for Kronecker's non-apocryphal comment quoted by Gerry, in which he expresses reservations about "irrationals" and "the concept of infinite series".

Comment by T.

2010-08-01T18:59:00Z

(or are you referring to the proof of the full modularity conjecture which used heavier p-adic technology?)

User t. - MathOverflow

Where does the "Hardy-Littlewood" conjecture that pi(x+y) < pi(x) + pi(y) originate?

Answer by T. for On the elliptic logarithm and elliptic exponential

Answer by T. for Meaning of Kronecker's comment to Lindemann

Answer by T. for Guess a number with at most one wrong answer

Answer by T. for What happens when we print the digits of a real number?

Answer by T. for Arctangents and the golden ratio

Answer by T. for What is a reasonable finitary analogue of the statement that harmonic functions are smooth?

Answer by T. for The unprecedented success of the “intersection” operator

Answer by T. for Looking for a probability distribution

Answer by T. for Implications of the abc conjecture in Arakelov theory

Answer by T. for Limit of a discrete time dynamical system

Answer by T. for Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?

Answer by T. for Does anyone know a polynomial whose lack of roots can't be proved?

Answer by T. for When is something too big to be a set?

Answer by T. for Are there more Nullstellensätze?

Answer by T. for What is the standard notation for a multiplicative integral?

Answer by T. for On a theorem of Jacobson

Answer by T. for Theorems which say "such and such method cannot possibly prove FLT"

Answer by T. for Bourbaki's epsilon-calculus notation

Answer by T. for Correlation and Causation. When can we believe correlation (reasonably, at least) imply causation

Answer by T. for Strengthening the Induction Hypothesis

Answer by T. for Theorems which say "such and such method cannot possibly prove FLT"

Answer by T. for Statistics for mathematicians

Answer by T. for How would you solve this tantalizing Halmos problem?

Answer by T. for Heuristic justification for Goldbach's conjecture

Answer by T. for When did the career of 1 as a prime number begin and when did it end?

Answer by T. for Is there a progress on a solution of the inequality $\pi (m+n)<= \pi (m) + \pi (n)$

Answer by T. for Why is a topology made up of 'open' sets?

Answer by T. for Do there exist nonconstant functions such that...

Answer by T. for Origin of symbol *l* for a prime different from a fixed prime?

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Comment by T.

Answer by T. for Origin of symbol l for a prime different from a fixed prime?