User quid - MathOverflow

Answer by quid for What math institutes offer research in pairs/research in teams?

2011-04-23T13:23:57Z

In France:

a. Institut Henri Poincaré (Paris)

'Research in Paris' (yes, Paris not pairs)

http://www.ihp.fr/en (under "Activities" one will find "Research in Paris")

b. CIRM (Marseille/Luminy)

'Recherche en binôme'

http://www.cirm.univ-mrs.fr/index.html/ (under "Events" / "Les rencontres" one will find "research in pairs" / "recherche en binôme")

Answer by quid for Effect of abc conjecture on Fermat's Last Theorem

2013-05-17T17:16:56Z

There is a slight ambiguity what "the ABC conjecture" is as there are some variation. However, the most common and what you likely mean is this fomulation (or something equialent to it):

For every $\epsilon >0$, there is a $C_{\epsilon}$ such that: if $a+b=c$, with positive coprime intergers, then $$c < C_{\epsilon} \ \text{rad}(abc)^{1 +\epsilon}.$$

Now, for the equation $x^n + y^n = z^n$ this means that $$ z^n < C_{\epsilon}\ \text{rad}(x^ny^nz^n)^{1 +\epsilon}. $$ Yet $\text{rad}(x^ny^nz^n) = \text{rad}(xyz)$ so one actually has $$ z^n < C_{\epsilon} \ \text{rad}(xyz)^{1 +\epsilon}. $$ and since $z$ is the largest and since $\text{rad}(a) \le a$ this further means $$ z^n < C_{\epsilon} z^{3 + 3\epsilon}. $$ Now, take $\epsilon =1/4$, say. Then on the one hand this cannot hold for any $z>1$ for $n$ sufficiently large (so no solution for large $n$, what you ask) and also not for any $n \ge 4$ fixed for $z$ sufficiently large (so only finitely many for fixed $n$) or also only finitely many couples $(z,n)$ that fulfill this (for $n \ge 4$).

[Added:] Since the question was changed to remove the gcd condition in Langs's version, I add for completeness, that each solution (for given $n$) implies the existence of a coprime one (for this $n$) so since above establishes there are no coprime solutions for some $n$ then there are none at all. [End Added]

However, to make these things effective/explicit one would need to know something about $C_{\epsilon}$ (in dependence of $\epsilon$).

Regarding "strongest possible": I think this is about what can be said, from the conjecture in the way I stated it. If one assumes stronger conjectures where one would have an explicit dependence of $C_{\epsilon}$ on $\epsilon$ then one could give explicit bounds. But (I think) the argument essentially always passes throught the last displayed equation and checking what this yields.

Answer by quid for A sequence based on Catalan–Mihăilescu problem

2013-05-11T14:56:48Z

Can $f(n)$ take any values except $0$ and $1$ for $n>1$?

Yes, $2^5 - 3^3 = 5 = 2^3 - 3^1$, but this is very exceptional!

Is it possible that $f(n)=\infty$?

No. Indeed, $f(n)$ is $0$ or $1$ for $n\gt 13$ (and for the remaining ones all solutions are also known and I think there are never more than two, but deifinitely only very small, see link below). This was proved by Stroeker and Tijdeman (1982) however that it is only $0,1$ for large $c$ is a lot older (Herschfeld in the thirties).

Are there arbitrary long runs of $0$'s and $1$'s in the sequence?

For $0$ yes, for $1$ I am not sure at the moment but I doubt it (and it might be known, perhaps there is even a direct argument).

What is the asymptotic density of $0$'s in the sequence?

The density is $1$. This follows from the fact that the number of solutions $(x,y)$ of the diophantine inequality $$ 0 \lt 2^x - 3^y \le c$$ is asymptotically $(\log c )^2/ (2 \log 2 \log 3)$. So below $c$ the function $f$ can be (and is, due to above mentioned result) positive only about $(\log c)^2$ times. (This is a special case of a result by Pillai.)

For further details the start of the paper of Waldschmidt "Perfect powers: Pillai's works and their devellopment" is a good starting point. Also you might look at http://oeis.org/A219551 which gives (something equivalent to) the exact values of $f(n)$ and some references (but note this is slightly different as absolute values are considered).

Answer by quid for A question about the second Chebyshev function $\psi(x) = \sum_{m=1}^{\infty}\vartheta(\sqrt[m]{x})$

2013-05-05T19:24:36Z

The inequality is simpler than PNT but also I would not consider it as straightforward; what seems to be needed are results slightly weaker than those of Chebychev.

Suppose we can bound $c_1 y < \psi(y) < c_2 y$. Then for your inequality it would suffice to have $$ c_1/5 \ge c_2/3 - c_1/4 $$
which translates to $$ c_1 \frac{27}{20} \ge c_2 $$ Now Chebychev established such bound with $c_1$ (about $0.92$) and $c_2 = c_1 \frac{6}{5}$, except for some small explicit logarithmic terms, for $y \ge 30$.

Thus starting from quite small $x$ your inequality will already follow from Chebychev's work.

Answer by quid for Does group of 4 equidistant successive prime exists ?

2013-05-01T12:48:36Z

Yes for the lengths you ask for this is known to exist.

The minimal example is $9843019+ 30 n$ for $n=0,1,2,3,4$ (taken from the page at the end).

A more common way to phrase this would be to ask about (five) consecutive primes in arithmetic progression.

Indeed, it is conjectured that there are arbitrarily long (finite) arithmetic progressions of consecutive primes, however this is open. (Without the restriction of the primes being consecutive primes this is known by a well-known result of Green and Tao.)

The longest known arithmetic progression of consecutive primes has length ten.

For further details one could start at http://en.wikipedia.org/wiki/Primes_in_arithmetic_progression (see the section towards the end on consecutive primes in AP) for record data related to this see http://users.cybercity.dk/~dsl522332/math/cpap.htm

Answer by quid for About Goldbach's conjecture

2011-04-18T11:46:33Z

I think it could be a save assumption that this is not equivalent to RH in a simple way (assuming the other assertions of the question are true).

Here is why: to show that RH implies Goldbach (at least asymptotically) is not at all an unatural idea, which however as far as I know is open.

For example, in 'Refinements of Goldbach's Conjecture, and the Generalized Riemann Hypothesis' Granville discusses questions close to this. However, it seems to me that there asymptotic counts of the number of solutions to 'the Goldbach equations' are related to the RH (and GRH).

Another example would be, Deshouillers, Effinger, te Riele, Zinoviev 'A complete Vinogradov $3$-primes theorem under the Riemann hypothesis. Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 99–104.' who showed that ternary Goldbach follows from GRH. This is less directly related as ternary Goldbach is long known asymptotically, and this is thus about eliminating 'small' counterexamples.

So, it just seems more than a bit unlikely that 'RH implies asymptotic Goldbach' can be solved with a half-page argument and an equivalence argument direct enough that somebody might simply supply it here.

In addition, despite an explicit request (made a while ago) there is still no information/evidence provided why this should be equivalent to RH, which I interpret as the absence of any such evidence.

Finally, since being equivalent is a bit of a vague notion (if both were true they were equivalent even if totally unrelated) and since this is too long for a comment anyway, I thought I give these generalities as an answer.

Answer by quid for Any progress on the Firoozbakht Conjecture?

2012-03-06T14:12:46Z

Significantly rewritten, yet the main message stays the same.

It is quite likely that this conjecture is false yet no counter example was found so far.

The reason why this seems likely is that there seems to be no supporting evidence for this conjecture beyond numerics.

And, there are investigations base on quite natural random models of the primes that contradict it. What is commonly known as Cramér's conjecture, that is that maximal gaps between consecutive primes are of sizes at most $(\log p_n)^2$ (up to lower order terms) does not contradict this conjecture, and one might even think it supports it. However, on the one hand it is not quite clear Cramér even conjectured this in precisely this form; he conjectured gaps are $O((\log p_n)^2)$ and somehow implied that about $(\log p_n)^2$ might be true. On the other hand, and more importantly, Granville note that a finer investigations of Cramér's reasoning rather suggests maximal gaps of size $2 e^{-\gamma} (\log p_n)^2$ (up to lower order terms). And if this were true it would contradict the conjecture mentioned in OP (this is what is referred to in OP as Cramér-Granville conjecture).

It should however be noted that Granville did not conjecture that the gaps are of this size, yet pointed out what taking an additional aspect into account would mean for Cramér's reasoning. For Granville on this matter on MO see http://mathoverflow.net/questions/114399/consequences-of-legendres-conjecture/122939#122939

For details on Granville's arguments see for example http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf

Answer by quid for special primes with p'=4p+1

2013-04-21T13:37:37Z

There are very likely infinitely many primes of this form but this is open.

If one where to count the number of such primes up to $x$, one expects to find $$ \frac{C x}{( \log x)^2} $$ for some constant $C$ that one could compute, so on the one hand not too few but still only a set of relative density (in the primes) $0$, as expected by OP and compatible with the observation that early on there are not too few.

Where does this expectation come from: one can rephrase the problem as the problem of searching solutions in the primes of the linear equation $X = 4 Y +1$.

A linear equation (or a system thereof) is expected to have a infinitely many solutions in the primes if it has in the integers and there is no local restriction, that is there is no congruence relation that 'forbids' all variables to be prime, say $X=Y+3$ cannot have infinitely many solutions as it 'does not work' modulo $2$, and there is no problem due to positivity of the primes, say $X+Y = 1000$ cannot have infinitely many solutions in primes. And, there is also a prediction for the number of solutions.

This circle of ideas goes under the name Generalized Hardy--Littlewood conjectures.

For certain systems it is known that there are infinitely many solutions but for others not. Essentially, what is the case (under currently known results) is governed by the complexity of the system (in a precise technical sense see the reference below).

The equation you are looking at has infinite complexity (in this sense) and therefore it is not known (yet conjectured) that there are infinitely many solutions.

The introduction of 'Linear equations in primes' by Green and Tao gives a good overview; the paper itself makes important progress on these types of problems, note that the results in this paper are formulated conditionally on two conjectures but meawhile these are settled by the same two and Ziegler.

If you want to search for such primes a thing to note are congruence conditions to exclude unecessary test. For example, one can use that if $p$ and $4p +1$ are prime than $p$ can only be congruent $7$, $13$, $19$ modulo $30$, which follows by looking at the problem modulo $3$ and $5$ (and the info one has modulo $2$). One could add info for additional primes but perhaps this mod $30$ is a good balance.

Answer by quid for A "bit" of primes

2013-04-19T19:43:01Z

First, I strongly second the recommendation of Gjergji Zaimi to read the paper by Granville and Martin; here is a link to the arXiv version in addition.

Some initial and partial information:

On a very rough scale the frequency counts of primes with "bit 1" equal to $0$ and $1$, resp., are the same; both counting functions are asymptotic to $\frac{1}{2} \text{li}(x)$ with error terms essentially as commonly know from the prime counting function. This is the well-know Prime Number Theorem for arithmetic progressions, as the condition on the 'bit 1' translates into considering primes congruent to $1$ and $3$ modulo $4$ respectively.

However, if one compares the exact counts of primes congruent to $1$ and $3$ modulo $4$ respectively, let us call the respective counting functions $\pi_1(x)$ and $\pi_3(x)$, then one notes (at least at the start) that there are more congruent to $3$ than congruent to $1$, so $\pi_3(x) > \pi_1(x)$, an observation made by Chebyshev. However, Littlewood showed that the difference $\pi_3(x) - \pi_1(x)$ can also be negative, and even is infinitely often essentially as negative as it can get (under the assumption that both should not deviate from $\text{li}(x)/2$ by more than $\sqrt{x}$ and a little).

So, now one might think that one just came across a phenomenon of small numbers with this initial bias however this is not so there is a bias in the distribution.

If one defines $P$ to be the set of all integers such that $\pi_3(x) > \pi_1(x)$ then these are not "half of the integers". Rubinstein and Sarnak proved (under widely believe conjectures on zeros of L-functions, GRH and GSH) that the logarithmic density of this set, that is the limit of $$ \frac{1}{\log x} \sum_{n \in P} \frac{1}{n} $$
is $0.9959...$, so quite close to $1$.

But, if one would keep to look at the "bit 1" yet restrict to those primes with "bit 2" equal to $1$ this bias goes away!

This might seem quite odd when said like this, it becomes somewhat less mysterious (though of course stays fascinating) if one observes the following:
The primes with "bit 2" equal to $1$ are those congruent to $5$ and $7$ modulo $8$ (except for $2$ of course). And, the bias in the case of $1$ and $3$ modulo $4$ is roughly speaking due to the fact that all squares of odd primes are $1$ modulo $4$, while for $5$ and $7$ modulo $8$ squares of primes are to be found in neither of the two classes.

As said the above mentioned paper provides a lot more information related to these phenomena; also the introduction of the paper of Rubinstein and Sarnak provides a very good overview. And, there is also more recent work related to this see for example http://arxiv.org/abs/1108.5342

Also, the result of Rubinstein and Sarnak is conditional; for discussion of getting (partially) rid of these assumptions, or it is perhaps more precise to say working somehow under the negation of the assumtptions, see again the already mentioned paper or, e.g., this recent contribution http://arxiv.org/abs/1204.6715 .

Answer by quid for Why do mathematicians prefer one definition over the other when they both define the same concept?

2013-04-19T00:37:07Z

To give one answer to the question in the title: A reason to prefer one way of defining the same 'idea' over another is that it generalizes better. (Where of course what better means can depend.)

I have notthing to say about equivalence relations but since also other examples are asked for:

The notion 'prime number' can perhaps serve as an example for what I mean.

For the natural numbers one can define this in various ways equivalent ways. In particular (we exclude $1$, and $0$ if one considers it as natural number):

A number $p$ is a prime number if $p=ab$ implies $p=a$ or $p=b$. (Or, put differently, $p$ is only divisible by $1$ and itself)
A number $p$ is a prime number if $p|ab$ implies $p|a$ or $p|b$.

These are equivalent for the natural numbers. But, I am convinced that the latter is the better definition of prime number. (Though, to answer side questions, when teaching introductory things I might use the former, since students might be already familiar with this being the definition and anyway I will not have the time to convey why the other is better. Also, I think this conviction is not universal (now) and certainly was not earlier.)

So, why am I convinced about this. Because, if you part from the natural number/integers to more general things, say rings of algebraic integers, Dedekind domains, domains in general, it is this definition that generalizes better to yield a notion of prime element.

The property given by the former is also interesting in more general situations, but I/one(?) would not call such an element prime but rather irreducible, for example.

Thus, in this case I would not say there are two definition for the 'idea' prime number that are equivalent.

But, rather there are really two 'ideas', the one of an irreducible element and the other of a prime element, and for the natural numbers (and the integers) one can show that they coincide.

The former definition yields the former, and the latter the latter. And, the latter being somehow more pertinent, as also documented by naming, this is the definition of prime number (in the naturals) that I prefer, since it generalizes better.

Answer by quid for Are there refuted analogues of the Riemann hypothesis?

2013-04-14T10:13:30Z

There is a well-known example of Davenport and Heilbronn of a Dirichlet series that in some sense is not so different from the Riemann-zeta function but that has zeros off the critical line.

The function is defined $$\sum_{n=1}^{\infty} \frac{a_n}{n^s}$$ where $a_n$ equals $1, c, -c, -1, 0$ for $n$ equal to $1,2,3,4,5$ modulo $5$, resp., with $c$ a certain algebraic number [see the reference at the end for the actual value].

This function then fulfills a functional equation similarly to the Riemann-zeta-function and (thus) can be continued to the entire plane (for details see again reference below). Yet as mentioned above it has (nontrivial) zeros off the critical line. And, it might be worth adding that for other Dirichlet series with periodic coefficient sequences (for example, Dirichlet L-series) one expects a generalisation of RH to be true.

For some recent computational investigations on the zeros of this function see for example Zeros of the Davenport-Heilbronn Counterexample Mathematics of Computation, 2007.

For an 'axiomatic' framework where no exceptions to (the analog of) the Riemann Hypothesis are currently expected while capturing many/most Dirichlet series that appear in practise see the Selberg class.

Answer by quid for At what point would an elementary generalization of Bertrand's Postulate be interesting?

2013-04-11T15:54:12Z

Current results are able to yield such results. Depending on how generous one is regarding what $X$ is. If it is just the optimal value can be calculated exactly this will work for many more $k$ and if one is happy with an explicit bound for all $k$.

For example Dusart showed that $$
\frac{x}{\log x - 1} \le \pi(x) \le \frac{x}{\log x - 1.1} $$ for $x\ge 60184$. Now for some $k$, write $y=kx$. Then, if the upper bound for $kx=y$ is smaller than the lower bound for $(k+1)x = (1+1/k)y$, that is $$ \frac{y}{\log y - 1.1} \lt \frac{y(1+ 1/k)}{\log( y (1+1/k) )- 1} $$ one has a prime between $kx$ and $(k+1)x$, since then $\pi(kx) \lt \pi((k+1)x)$.

One can check that this inequality holds for (up to potential error in my calculation) $$ y \ge 10 e^{0.1 k}. $$

So, for $x \ge \max \lbrace 10 e^{0.1 k}/k , 60184/k \rbrace $ one always has a prime between $kx$ and $(k+1)x$.

While this grows exponential in $k$, the growth is such that it is well feasible to check 'everything' up to the bound to get an optimal $X$ for not too large $k$. And, one always has an explict value.

This proof is of course not elementary (the non-elementariness being hidden in Dusart's result) and is an application of the PNT in some sense. But what this is meant to show is that for a result around this to be interesting it seems necessary either to be better (and one could still optimize this here) than this or the proof would have to be interesting (or both). [What an interesting proof is is of course a bit subjective.]

Answer by quid for $\sum _{k=0}^{\infty } \frac{1}{(k+m) k!} \equiv 1$ for $m=2$

2013-04-06T23:53:00Z

A way to get this, and also to understand the behavior for other values would be like so (though I do not know if this is not overly indirect):

Recall that $$ e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!} $$ so $$ x^{m-1}e^x = \sum_{k=0}^{\infty} \frac{x^{k+m-1}}{k!} $$ Now 'integerate', then $$ F(x) = \sum_{k=0}^{\infty} \frac{x^{k+m}}{(k+m)k!} $$ where $F$ is some antiderivative of $x^{m-1}e^x$.

For $m=2$ one has the antiderivatives $e^x(x-1) +c$. Setting $x=0$ one finds that $F(x) = e^x(x-1) +1$. Setting $x=1$ one finds $1=\sum_{k=0}^{\infty} \frac{1}{(k+2)k!}$. Now subtract the term for $k=0$, which is $1/2$ to get your result.

(Not sure this is on-topic, but it is weekend and I was bored. Sorry in advance, to those how might mind.)

Answer by quid for The ratio of one digits and all digits in the binary expansions of the square numbers

2013-04-03T21:30:02Z

This answer adresses the first of the two questions (and was originally written, except for minor changes, for a slightly vaguer version of the question; thus the material that might not seem completely fitting now, except that it could be helpful for the second question, so I leave it).

It is a result of Lindström (On the Binary Digits of a Power, Journal of Number Theory, 1997) that, using his notation and denoting by $B(\cdot)$ the numer of 1s in the binary expansion in other words the sum of digits, $$ \limsup_{m\to \infty} \frac{B(m^h)}{\log_2 m}= h $$
which means precisely that for fixed $c$ the supremum is indeed $1$; indeed it works for any exponent not just powers of $2$.

I have not studied Lindström's proof in detail, but it seems to be explicit so that one could derive information for the $x_0$ ; and for squares the paper by Dromota and Rivat contains another explicit construction that could also be used.

Even more generally, the same is true for every polynomial of degree $h$ (with integer coeficients and positive leading coefficient).

Yet, it is true that such numbers, powers with many $1$, are in a certain sense rare.

There are various further (in part recent) results around this question. For example: $$ \frac{1}{N} \# \lbrace n \lt N \colon B(n^2) \le \log_2 N + y \sqrt{\frac{\log_2 N}{2}} \rbrace = \Phi(y)+o(1) $$ where $\Phi$ denotes the normal distribution function. In other words, this $B(n^2)$ behaves like the sum of $2 \log_2 N$ independent random variables $0$ and $1$ with equal probability. This result is a special case of a result of Bassily and Kátai (Distribution of the values of q-additive functions on polynomial sequences, Acta Math. Hung. 1995)

For other results related to this, and the above mentioned information in more detail and nice constructions related to the above phonomenon, see for example Drmota and Rivat "The sum of digits function of squares" (Journal LMS, 2005) ; for similar investigations for arbitrary polynomials and q-ary digits see this more recent paper by the same authors and Mauduit

Or, for investiagtions of the ratio of $B(m^h)/B(m)$ see this recent paper by Hare, Laishram, Stoll "Stolarsky's conjecture and the sum of digits of polynomial values"

(Added: I do not know if anything on the second question is known or could be derived from known things; the distribution result seems to support what Aaron Meyerowitz says, it could be worth looking into the results on the ratio I mentioned.)

Answer by quid for A Diophantine equation involving prime powers.

2013-04-02T11:27:05Z

I only answer the (newly) added question (the others being adressed in comments):

Are there infinitely many primes of the form $a2^n + 1$, where $a$ is a fixed number?

Certainly not for each $a$. More precisely, Sierpiński (1060) showed that there exist infinitely many odd $a$ such that all numbers in the set $$ \lbrace a2^n +1 \colon n \in \mathbb{N} \rbrace $$ are composite.

Such an $a$ is called a Sierpiński Number; an explict example is $78557$. Chances are this is the smallest example, and there is some ongoing computing effort to show this. See the link I gave above for further details.

For certain other $a$ there are likely infinitely many, but this is never known. The point is that the most naive heuristic would be to say that the probability of $a2^n+1$ to be prime is proportional to $1/n$ (more precisely $1/\log (a2^n +1)$ by the Prime Number Theorem) and the series over $1/n$ being divergent one expects infinitely many, just like for Mersenne Primes.

However, and necessarily in view of what I said above, there can be problems with this heuristic: Depending on the $a$ there can be 'local' restrictions (that is one finds congruences that impede the number of this form to be prime, see again the site above). Or/and, as in the Fermat case, there is a general factorization that reduces the range of the admissible exponents so much that the relevant series will converge and one thus expects at most finitely many.

One more related key-word: Primes of the form $a2^n + 1$ for $a$ odd not fixed, but $2^n \gt a$ (to avoid trivializing the condition) are called Proth primes.

Following the links on the two pages I gave you will find some more related notions and additional information.

Answer by quid for Mertens function limits using $\phi+2$n

2013-03-30T16:07:56Z

While the specific question appears to be answered, I would like to add a more general one:

The study of the Mertens function $M(x)= \sum_{n \le x} \mu(n)$ is a notorius problem, and (thus) any new insight based on numerical investigations for very small values (in this context) seems most unlikely.

The function $M(x)$ is in a very vague sense about square-root-ish and thus one sometimes writes $q(x)=M(x)/\sqrt{x}$.

On the one hand, there used to be an old conjecture that $|q(x)|\lt 1$ (Mertens' conjecture), which was refuted by Odlyzko and te Riele (1985), and was already considered very unlikely to be true before, and Mark Lewko mentioned the curent 'record' constants. But it is beleived that $q(x)$ is in fact unbounded.

On the other hand, an estimate $q(x)= O(x^{\varepsilon})$ for every $\varepsilon > 0$ is equivalent to the Riemann Hypothesis. More precisely, by a recent result of Soundararajan it is known that under RH one has $$ q(x)= O(\exp( \sqrt{\log x} (\log \log x)^{14})), $$ and Balazard and de Roton showed that $14$ can be optimized to $5/2 + \varepsilon$ for every $\varepsilon > 0$.

Yet, it seems to be not clear (even conjecturally) how $q(x)$ should actually behave.

Kotnik and van de Lune (Exp. Math. 13.4) made the conjecture that $$ q(x)= \Omega_{\pm}(\sqrt{ \log \log \log x}), $$ and Kotnik and te Riele (mentioned in Mark Lewko's answer) discuss that extremal observed values of $q(x)$ are close to $\pm \frac{1}{2}(\sqrt{ \log \log \log x})$.

However, and as mentioned there, if this would remain (about) true 'forever' this would contradict Ng (2004) [and Gonek (unpublished)] conjecture that limes superior and limes inferior of $$ \frac{q(x)}{( \log \log \log x)^{5/4}} $$ are in fact $\pm B$ for some positive and finite $B$.

Yet, in the in the 70's still other conjectures were made namely that the limit of $$ \frac{|q(x)|}{\sqrt{ \log \log x}} $$ should exist, and even two(!) values were suggested for the limit. [Note: there are only two log's here.]

And, there would still be different contributions to this. For example, Kaczorowski (Journal London Math. Soc. 2007) showed that a 'twisted' version of $M(x)$ is fairly large, namely $$ \sum_{n \le x} \mu(n) (\cos (x/n) -1) = \Omega_{\pm}(\sqrt{x} \log \log \log x) $$ and he derives from this that for every real $a\neq 0$ $$ |\sum_{n \le x} \mu(n)|+|\sum_{n \le x} \mu(n) \cos (ax/n)| = \Omega(\sqrt{x} \log \log \log x) $$ which would, if one could take $a=0$, imply $|q(x)| = \Omega (\log \log \log x)$. Or, put differently, shows that if the $|q(x)|$ is not as large, the sum with the cosine has to be large for every non-zero $a$. In contrast to the idea that $\frac{1}{2}(\sqrt{ \log \log \log x})$ might be about right.

In any case, this problem is complicated in that even detailed and recent investigations can arrive at different conclusions what should or might be the right expectation regarding the behavior of $M(x)$.

Answer by quid for Strassen's algorithm

2013-04-01T13:26:07Z

This $7$ is an absolute lower bound. The result is due to Hopcroft and Kerr "On minimizing the number of multiplications necessary for matrix multiplication." SIAM J. Appl. Math. (1971) and Winograd "On multiplication of $2\times 2$ matrices." Linear Algebra and Appl. (1971). [The former assume that entries of the matrices might not commute; while the latter gets the bound even assuming commutativity of the entries.]

A lot more recently Landsberg showed that not only the rank but even the border rank of multiplication of $2 \times 2$ matrices is $7$, meaning very roughly that also small perturbations cannot lead to a smaller rank and thus saving of a multiplciation (for "approximate" calculations), assuming bilinearity of the algorithm.

The paper establishing this is Landsberg "The border rank of the multiplication of $2\times 2$ matrices is seven", Journal Amer. Math Soc. 2006. The introduction also discusses your question.

See the link at the end for the respective volume of the journal, I think the article is free: http://www.ams.org/journals/jams/2006-19-02/home.html

Answer by quid for product 1+1/p in terms of Chebyshev's theta or psi function

2013-03-30T01:21:27Z

[I undelete my (non-)answer (slightly edited), since Greg Martin's answer refers to part of my comment, and the answer contains some details related to this, which thus are perhaps interesting to have around.]

One has $$ \prod_{p\le x} (1+ 1/p) = \prod_{p\le x} (1- 1/p^2)/(1-1/p) = (\zeta(2)+o(1))^{-1} \prod_{p\le x} 1/(1-1/p) $$ and (essentially Mertens' 3rd Theorem) $$\prod_{p\le x} 1/(1-1/p)= (e^{\gamma} +o(1)) \log x.$$ So $$\prod_{p\le x} (1+ 1/p)$$ is asymtotically $$ \frac{6 e^{\gamma}}{\pi^2 } \log x . $$

Answer by quid for Combining van der Waerden's theorem with Ramsey's theorem

2013-03-22T00:50:19Z

The way I understand the question is that $k$-tuples of integers are considered so that each coordinate lies in $[1,N]$, so in other words one considers $[1,N]^k$ and colors all the elements of this set, so each poin $(a1,...,ak)$ gets some color.

There is a version of Szemerédi's Theorem for $\mathbb{Z}^k$, due to Furstenberg and Katznelson, that asserts that for every subset $A$ of $\mathbb{Z}^k$ of positive upper Banach density and any finite $F\subset \mathbb{Z}^k$ there is some $u \in \mathbb{Z}^k$ and some $n \in \mathbb{N}$ such that $u+nF \subset A$.

For this result see for example Corollary at the start of the paper by Bergelson and Leibman, establishing a polynomial version of Szemerédi's theorem (I failed to properly locate the original paper, thus this reference by proxy).

This result necessarily also has a 'finitary' analogue (to match the question), however the proof being "ergodic" to get explict constants could be a problem. Also, as usual, on would consider for a given coloring the largest set of the same color, which necessarily has positive upper denisty.

Now, this result implies directly the existence of s-term arithmetic progression in such a set $A$ in the sense I understand this word, namely as a set of the form $a, a+d, ..., a+(s-1)d$ with $a,d$ in the relevant structure so in this case $\mathbb{Z}^k$, by taking $F$ some set of points in arithmetic progression.

However, this appears (after the update) not to be what is meant (yet I have to admit in retrospect that my argument for my, and I think the common, use of AP seems overly complicated).

Yet what OP is looking for is an arithemtic progression $S$ in $\mathbb{Z}$ (or rather $[1,N]$) such that $S^k$ is monochromatic. As noted by OP what the mentioned result gives is a monochromatic set of the form $u+S^k$. And, as mentioned in comments to actually get $S^k$ monochromatic is impossible.

(Sorry for the repeated edits.)

Answer by quid for What is a Ramsey Graph?

2013-03-09T12:08:41Z

The form in which you might be familiar with the result is this:

for a pairs of parameters $(r,b)$ there exists an $n$ such that for every (edge-)coloring of the complete graph on $n$ vertices with colors r(ed) and b(lue) there will exist a complete subgraph on $r$ vertices colored red or a complete subgraph on $b$ vertices colored blue.

One can then try to determine the smalles such $n$ and this is the respective Ramsey number.

Now, you can rephrase this problem not as coloring problem but like so:

for a pairs of parameters $(r,b)$ there exists an $n$ such that for every graph on $n$ vertices there will exist a complete subgraph on $r$ vertices or for the complement of the graph there will exist a complete subgrpah on $b$ vertices.

The complement of the graph is precisely the graph with those edges not present in the original graph. In other words, if you color, consider the graph just formed by the red edges, the complement will be the grpah with the blue edges.

Still differently, one says a graph contains a clique of size $r$ if it contains a complete subgraph of that size. Conversely, one says it contains an independent set of size $b$ if there is a set of vertices size $b$ with no edges among these vertices. (In other words in the complement this will be a clique.)

So, one can also state the result above in the form:

For every pair of parameters $(r,b)$ there is an $n$ such that each graph on $n$ vertices will contain a clique of size $r$ or an independent set of size $b$.

Now, this result in particular implies that, given $(r,b)$ there are only a finite number of graphs that do not have a clique of size $r$ or an independent set of size $b$. Such a graph is then called a Ramsey graph for the respective parameters, and sometimes the number of vertices of the graph is given as additional parameter.

So, a Ramsey graph (with certain parameters) is an example of a graph were what is implied by the respective Ramsey theorem (for sufficiently large graphs) does not hold true. (Of course its number of vertices thus is smaller than the relevant Ramsey number.
And, the maximal number of vertices of a Ramsey graph is just one smaller than the respective Ramsey number)

Answer by quid for What exactly does \gg and \ll mean?

2013-03-04T14:22:46Z

I like Frank Thorne's comment-answer, but I would like to stress a detail he mentions in passing, but which does not seem adressed at all on Wikipedia.

What exactly $\ll$ means is not completly uniform even if on just takes the meaning(s) common in Analytic Number Theory (and ignores those informal ones used in some other context like "a lot less than" or "negligible").

One meaning is this: For maps $f: D \to \mathbb{C}$, and $g: D \to \mathbb{R}_{\ge 0}$ one says $f = O(g)$ or equivalenlty $f \ll g$ if there exists some constant $C$ such that $|f(x)| \le C g(x)$ for all $x \in D$.

In particular, this notation is not in itself asymptotic.

Another meaning is this:

For a map $f: D \to \mathbb{C}$, and a function $g: D \to \mathbb{R}_{\ge 0}$ and an accumulation point $x_0$ (possibly infinity) of $D$ one says $f = O(g)$ as $x\to x_0$ or equivalenlty $f \ll g$ as $x \to x_0$ if for each neighborhood $U$ of $x_0$ there exists some constant $C$ such that $|f(x)| \le C g(x)$ for all $x \in D \cap U$.

And not infrequently $f = O(g)$ and $f \ll g$ is used with the second meaning implictly assuming that $x_0$ is "infinity." In particular this is common if the domain of the function is discrete, as it seems to be in you case (positive integers).

A detailed discussion of this can be found for instance in the introduction of Iwaniec and Kowalski's book, who use the first meaning.

Now, after this general discussion for the subscripts. No matter what precise of the two meaning one chooses one always has some constant $C$ called the implied constant.

In practise, it can arise that one uses the above notation not just for one map at a time but rather for a family of maps at the same time, or the map depends on some parameter one choose earlier.

Say, consider $f_t (x) = t x^2/(1+x^2)$ with $D= \mathbb{R}$ and $t$ a real, then for fixed $t$ it is true that there exists a constant $C$ for example $|t|$, such that
$|f_t(x)| \le C \cdot 1$ for all $x$ (or of course also just as $x \to \infty$).

So if $t$ is fixed one has $f_t \ll 1$. However the constant depends on $t$, and you cannot find a constant that works for all $t$ simultaneously. To express this more conveniently and clearly one typically writes this as $f_t \ll_t 1$.

More generally, a subscript or also multiple subscripts of $\ll$ indicate quantities on which the implied constant will (or can) depend.

Finally, the exact expression you give is somewhat unusual as Frank Thorne already explained. I share his opinion, and just would like to over an additional interpretation. It could be that somebody uses the subscripts in a different sense then the one I mentioned namely to indicate which quantitly tends to infinity. So that this could also mean $f(T) \ll 1$ as $T \to \infty$.

I hope this explication sheds some light on the matter, as opposed to causing additional confusion. As Todd Trimble said without additional context it will be impossible to decide what exactly is meant, since the usage is not uniform as Gerald Edgar stressed.

Answer by quid for Why do we choose the standard total order on the integers?

2013-02-27T20:44:01Z

I assume (your) monoids are cancellative.

Then the pre-order you define is a (partial) order if and only of the monoid $M$ is reduced (i.e. has no invertible elements besides the neutral one).

For getting an order on the Grothendieck group $G$ say the element in $M$ are "positive elements" and define on $G$ the relation $g\ge h$ if $g-h \in M$. This extends the preorder of $M$; is transitive and reflexive; and it is anti-symetric if and only if $M$ contains no non-trivial invertible elements.

It is a total order if $g$ or $-g$ in $M$ for each $g \in G$; such a monoid $M$ is sometimes called a valuation monoid (in analogy with valuation rings, which have this property with respect to their quotient field, for multiplication of course; thus also these monoids are more frequently noted multiplicatively).

Answer by quid for Consequences of Legendre's conjecture

2013-02-09T14:59:53Z

In the absence of much other contributions yet this still being open, I promote my slightly expanded comments to an answer:

The Legendre conjecture, while of historical relevance, nowadays does not seem to play too much of a role in research, it is thus unlikely to have many things that are specifically consequences of this conjecture.

On should think of this conjecture of a bound on maximal gaps between consecutive primes. On the one hand it yields directly a bound of size about $4 \sqrt{p} +4$ for the bound between a prime $p$ and the next largest one. On the other hand, would one know that the gap between a prime $p$ and the next one is always at most $2 \sqrt{p} + 1$ the Legendre conjecture would follow.

Now, the study of the maximal size of gaps between primes is an important subject and actively persued and knowledge there has certain implications and consequences. See http://en.wikipedia.org/wiki/Prime_gap for a start.

However, what is known at least conditionally on the Riemann Hypothesis is somewhat close to Legenerdre's conjecture, namely a bound on the gap of order $\sqrt{p} \log p $; and to get a bound just slightly larger than $\sqrt{p}$ say $p^{1/2+\varepsilon}$ is immediate under RH.

Also, unconditionally one knows (by result of Baker, Harman, and Pintz from 2001) that for large $x$ every interval $[x,x + x^{0.525}]$ contains a prime, which in some sense is not too far away from Legendre's conjecture.

This reinforeces the idea that Legendre's conjecture specifically does not have that many consequences, as the margin between what one knows (possibly admitting RH) and Legendre's conjecture is not that large.

Moreover, all the above is far from the expected truth. It is believed that the size of the gaps is bounded by something of the order of $(\log p)^2$, which is a lot smaller than $\sqrt{p}$. A relevant key-word here is 'Cramér conjecture'.

So, in brief results and conjectures on bounds on gaps between primes are relevant, but Legendre's conjecture specifically seems mainly (only?) of historical value.

To also give an example of something where bounds on gaps would have consequences:

Given a prime $p$, can one find the next largest prime in polynomial time (of course, polynomial in $\log p$)?

Admitting a bound of size $O((\log p)^2)$, or any bound polynomial in $\log p$, on prime gaps this would be a direct consequence of the fact that prime-testing can be done in polynomial time (AKS-test) and progressively checking the numbers. However, without this, this is not known. There was a recent Polymath-project on this, see the paper "Deterministic methods to find primes", Math. Comp. 2012

Answer by quid for A formula for a generator of the multiplicative group of $\mathbb{F}_p$ ?

2013-02-19T13:30:29Z

One more update (sorry for the slight sillyness, and hoping I at least got it right, yet it is not optimized):

For $F$ a field of prime cardinality $$1 + \sum_{a=1}^{|F|-1} \prod_{b=1}^{a} (1 - \prod_{d=1}^{|F|-2}(b^d -1)^{|F|-1} )$$ generates the multiplicative group (with usual convention that $n$ is $n \cdot 1_F$).

If one would like to have some "formula"/definition that would give a generator as requested for each field of prime order and always 'the same' for (isomorphic) fields, one could proceed like this:

Let $g_F = n \cdot 1_{F}$ where $$n = \min \{m \in \mathbb{N} \colon \text{ord} ( m \cdot 1_F) = |F|-1\}$$ and $\text{ord}$ denotes the multiplicative order (which one could also write out just using the field operations and quantifiers and the natural numbers).

If I oversee things correctly (which is a lot less clear than usually when I answer) one could define in principle this way a functor from the category with objects fields of prime order and morphism field homomorphisms (or iso would be the same in this case) to the category of "fields of prime order with minimally chosen multiplicative generator" (objects field of prime order plus distinguished element as defined above, and morphisms fields homo/isomorphisms mapping the distinguished element to the distinguished element of the respective fields).

The point being that between fields of different prime cardinality there is no morphism at all, and if the cardinality is the same there is exatly one (as everything is determine by the one-element).

So, it is in principle possible to "select" (in a uniform way for all such fields) some 'distinguished' (which perhaps one might call canonical) multiplicatively generating element. (Of course one could also make other selections than the minimal one.)

I am sorry if this either should not make sense at all, or should miss the point completely. In either case I would be glad for an explication.

Old version:

To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.

A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).

So, if you want some 'canonical' (in a certain sense) choice, take the smallest. Alas no one knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjectured it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).

To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).

And the question is somewhat closely linked to the discrete logarithm problem which is knwon to be hard.

See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/

Answer by quid for Goormaghtigh equation

2013-02-17T16:46:27Z

Yes for fixed $p,q$ it is know there is at most one solution. Even without the condition $p,q$ prime.

This was proved by He and Togbé, On the number of solutions of Goormaghtigh equation for given x and y (Indagationes Math, 2008)

Answer by quid for Van der Waerden's Theorem Over $\mathbb{Z}_p$

2013-02-15T12:07:53Z

A question that received a lot of attention over the last years are quantitative refinements of Szemerédi's theorem, a generalisation of van der Waerden's Theorem asserting that fixing any positive density $d$ one will find arithemetic progressions in a set of that density provided the initial segment of integers one considers is large enough. (If one has $c$ colors one is certainly guaranteed a set of density $1/c$ with all elements the same color.)

Now, it is known that one even can let the density go to zero (sufficiently slowly depending on the size of the initial segment). How slowly is not quite clear, and this is what these quantitiative refinemenets are about. See also for a conjecture regarding this.

For (recent) contributions on this see, e.g.,

a paper giving much better bounds in general ($k$ arbitrary) than known before, by Gowers for the general case
the to my knowledge currently best bounds for $k=4$ by Green and Tao
the to my knowledge currently best bounds for $k=3$ by Sanders

A feature these three papers share is that they take a Fourier analytic approach to the problem. And for this it is advantageous to work over a finite (prime) cyclic group rather then over the integers. Note that while all three papers phrase the main relsult for integers, for the proof they actually pass to a finite (prime) cyclic group.

I am not sure this answer is exactly what you are looking for, as while the problem is in some sense essentially the same it might (or might not) be the case that you are looking for results of a somewhat different flavor (say, less 'asymptotic').

In any case, working over a prime cyclic group certainly has some advantage and the problem in this context was considered a lot; indeed many of the recent works in this context even if at first glance for integers in the end are results for (prime) cyclic groups. Yet, there is not a huge difference in the bounds in the end for the reason Anthony Quas mentioned.

Answer by quid for Is Euler's totient sub-homogeneous of degree 1?

2013-02-02T14:45:03Z

First note that, since $\phi$ is a multiplicative arithmetic function, i.e. $\phi(ab)=\phi(a)\phi(b)$ for coprime $a,b$, and since $\phi(a) \le a$ for every $a$, it suffices to consider the problem for prime powers.

And $$\phi(p^k p^t) = p^{k+t-1}(p-1) = p^k (p^{t-1}(p-1))= p^k\phi(p^t).$$

Answer by quid for divisorial ideals

2013-02-02T13:25:18Z

The question is not quite clear, but in order to avoid its indefinite reappearence here some sort fo answer (info I gave in comments). [I hope noone 'objects' to me answering after voting to close, but the vote expired a long time ago, so.]

Let me first repeat something on the definition of divisorial ideals as it seems not universal known.

For a usual (ring) ideal $I$ of $R$ one defines $I^v = (I^{-1})^{-1}$ where $I^{-1} = (R:I)$ . Then $I^v$ is again a ring ideal and $(I^v)^v = I^v$.

Put differently some ring ideals $J$ have the property $J^v= J$, and such a ring ideal is called a divisorial ideal. (The definition can be/is usually extended to fractional ideals.)

Indeed, for certain domains every ring ideal is a divisorial ideal, Dedekind domains are an example. Such domains of course need to be excluded from considerations as in the question. Also, $I$ in the question needs to be non-diviorial

Now, even if one excludes this it still can happen that there is no ideal between $I$ and $I^v$.

For example, for the (maximal) ideal $I=(X,Y)$ in the polynomial ring $K[X,Y]$, $K$ a field, one has $I^v$ is the full ring, so $I$ is not disorial, but there can be no ideal between $I$ and $I^v$ since $I$ is maximal.

However, for $J=(X,Y^2)$ one would still have that $J^v$ is the full ring, and now there is some ideal in between namely the $I$ above.

Answer by quid for coprime numbers, number theory

2013-01-31T22:52:04Z

For 1 and 3, yes. (For 3 assuming both are positive, technically one positive would suffice but then it is essentially reduced to 1, while of course both negative will not work.)

And, note that this is only interisting for natural coefficients, with integers you can write any integer whatsoever, and this is very classical, not even sure how to call this, a direct consequence of Bezout's identity maybe, or an immediate consequence of results on linear diophantine equations.

For 2. The main keyword (with natural coefficients) here is Frobenius problem, but mainly for more than two numbers. Also Coin Problem, Postage Stamp Problem [though it seems some use this to refer to a realted but distinct problem where there is a restrition on the sum of coefficients, on the grounds that an enveloppe can only hold a given number of stamps] or Chicken McNuggets Problem are common more playful names. See http://en.wikipedia.org/wiki/Coin_problem

The solution for 3 is due to Sylvester.

If you have more than two coprime natural numbers $a_1,\dots , a_k$ for integer coefficients you still can write everything. But for natural number coefficients you can only write everythong starting from a certain number $F(a_1,\dots , a_k)+1$ on. To determine the optimal value here is hard (even algorithmically).

This is the Frobenius Problem, and $F(a_1,\dots , a_k)$, the largest number that cannot be written in this form, is called the Frobenius number of $a_1, \dots, a_k$ (or also of the numerical semigroup generated by $a_1, \dots, a_k$ that is just the additive semigroup generated by the $a_i$ )

It was in a certain sense solved recently for three numbers by Fel .

There are numerous other contributions on this problem and a lot of literature on numerical semigroups (that appear naturally in other areas of math, see the link above for some info), in particular there is a rather recent (2005) monograph on this subject by J. Ramírez Alfonsín "The Diophantine Frobenius problem."

Answer by quid for Mersenne primes problem

2013-01-29T14:07:44Z

No programming skills are needed, not even a computer, or even pocket-calculator ;)

Look, $M_p = 2^p - 1$ is congruent $1$ or $13$ modulo $18$ (which is what you are asking) if and only if $2^p$ is $2$ or $14$ modulo $18$.

Now, modulo $18$, one has $2^1=2$, $2^2=4$, $2^3= 8$, $2^4= 16$, $2^5= 14$, $2^6=10$, $2^7=2$.

Thus, $2^n$ is congruent $2$ modulo $18$ if and only if $n$ is $1$ modulo $6$, and $2^n$ is congruent $14$ modulo $18$ if and only if $n$ is $5$ modulo $6$.

Since every prime (except $2,3$) is $1$ or $5$ modulo $6$, and the exponent for a Mersenne-prime is a prime number the claim follows.

Comment by quid

2013-05-19T19:19:21Z

While Paul Taylor's comment also clarifies the situation, and it thus might not be necessary, you could edit the question to implement the suggestion by clicking the link 'edit' just below the question.

Comment by quid

2013-05-19T18:52:43Z

It seems you have several unregistered accounts. If you prefer this, this is of course up to you. But if you should not yet know: you can register an account so that all your contributions would be conveniently attached to one account. You then also could ask on 'meta' (link at the top) for all your accounts to be merged into that one.

Comment by quid

2013-05-19T12:34:50Z

This appears to be a duplicate of Anatoly Kochubei's answer, which likely explains the downvotes (none from me).

Comment by quid

2013-05-19T01:46:21Z

Pierre Grillet's Commutative Semigroups (2001) seems like (another) good place to start.

Comment by quid

2013-05-17T20:13:58Z

@Dietrich Burde: I think even for $n \ge 6$, as the inequality is strict.

Comment by quid

2013-05-17T17:49:06Z

You are welcome. Yes in some sense one can consider so to say "two limits" (in $z$ and in $n$) and thus there are in some sense different versions. Yet the finiteness of all solutions (under n> 3) contains all, as if there are only finitely many in total then there is a largest $n$ and a largest $z$ and so on. And, while I read it differently at first, thus my edit, I think the version you link to actually is meant to assert the finiteness of the set of all solutions , ie couples $(z,n)$ and thus contains Lang's.

Comment by quid

2013-05-14T19:44:31Z

First, it was said (in some sense even twice!) before your answer and is mentioned very prominently in the paper itself (by line 8 or so). Second, if you are so little informed about the actual content of the paper as to not even being able to give any type of substantive information that might remotely qualify as an answer to the (first) question, it is really unclear to me why anybody should care about your impression. (If you could but did not this seems even worse.)

Comment by quid

2013-05-14T17:24:59Z

..and rather consider the interpretaion of, eg, SL more natural. The question asks for the ratio. For this to make any sense at all one needs to understand some expected value is meant, I think we agree on this. But then which one. The default in my opinion is to simply take the expected value what is asked for. So the extepected value of the ratio, as opposed to the the ratio of the expected values (what you do). There is also the side question whether ratio is should mean B/G (and G/B) or B/(G+B) (and G/(G+B)). But also here when pressed I'd nominate the latter as better.

Comment by quid

2013-05-14T17:18:36Z

I am not sure what you refer to when you say that I agreed that the original question is whether E(B)/E(G) = 1. Mainly, I think I said I agreed with Kevin Buzzard that the question is unclear needing interpretation. To what I agree is that it seems in view of the "official" solution that the intended meaning is to aks for E(B)/E(G) or somethinng equivalent. But I also think (and I think disagree with you here) that this is not the only reasonable interpretation and when pressed I would say it is not clear (without 'official' solution) that one should understand this like so..

Comment by quid

2013-05-14T13:13:36Z

@Christi Stoica: if you disagree with a closure the best thing to do is to start a thread on meta. (Link at the top; extra sign up necessary, but easy and instant. Sign-up, top right, then 'apply for membership' which is granted instantly.)

Comment by quid

2013-05-14T10:36:49Z

I am not well placed to comment on details (and am sceptical regarding such questions in general) but in view of some other contributions I would like to say that since Vinogradov there were a number of contrib. towards getting the full conjecture, so if it is (and this seems likely) now fully settled this seems like quite an achievement. I have no time to write in detail but just a remark: only recently it was shown that all odd numbers (except minimal exceptions) are sum of 5 primes (Tao) improving on Ramaré (6 primes, for even). So now 3 (not 'only' 4) IMO is impressive.

Comment by quid

2013-05-14T10:15:49Z

"It needs to be iterated once again,..." Why? And, you do not answer the question.

Comment by quid

2013-05-14T01:13:39Z

Regarding MathJax: it does not work for me either. But, also the meta board is down and AFAIK both depend on the same server (which is not the one on which the main site depends). So I strondly assume this is a general problem (of that server).

Comment by quid

2013-05-13T21:21:00Z

...and in the lim (to go back to your title question) of an infinite number of families it would even yield 1/2. (So limits should make it right not wrong, in your view ;D) But if one follows this model (a formalization of the question) with any finite number of families one would stay slightly below 1/2. And some found this interesting and Steven Landsburg continued on this on his blog, being very clear what precise question he considers (and why). If you find this useless or uninteresting fine, but your continued insistence on others not understanding something is a bit annoying.

Comment by quid

2013-05-13T21:11:21Z

...you will notice that the thing started out as somebody (neither S.L. nor D.Z. nor me) suggestion a ratio of 60% or something like this based on considering one family, which contained a minor error, that when rectified yields the 30% we are now discussing. And then Douglas Zare (besides correcting the minor error) explained that this is not a good way to calculate the answer as if one considers more than one family one gets other answeres ever closer to 1/2 (what you want). And with a realistic number of families for a nation something very close to 1/2...