20
$\begingroup$

This is a soft question sparked by my curiosity about the intrinsic depth of Goldbach-like conjectures as perceived by current experts in number theory. The incompleteness theorem implies that, if our chosen foundational system is capable of reasoning about basic arithmetic (equivalently basic string manipulation), then there are true $Π_1$-sentences that we will be unable to prove, not by inability but by impossibility. The thing is, this impossibility arises from the ability to prove finite runs of programs (for some fixed Turing-complete language). But many currently open conjectures are also $Π_1$ too (such as Goldbach's conjecture), and hence also can be interpreted as questions about whether or not certain programs halt.

Based on this, it seems to me that it is very easy to make conjectures about primes that hold up under a statistical assumption on the distribution of primes, at least for sufficiently large numbers, and then tweak the conjecture to eliminate what empirically appears to be the only counter-examples. Just for example, I am no expert in number theory but I can 'randomly' create such a conjecture:

PSQ: Every integer $n>5$ of the form $3k+2$ is the sum of a prime and a positive square.

I checked it using a trivial C program up to $30$ million, and one can see that if we assume an integer $x$ to be a prime with probability $\sim 1/\ln(x)$ then the probability that a number $n$ fails to satisfy PSQ is at most $\sim (1-1/\ln(n/4))^{\sqrt{n}/2}$ $\sim \exp(-\sqrt{n}/\ln(n/4)/2)$ $\ll 1/n^2$, implying that the expected total number of failures is finite.

Under the same probabilistic heuristic, Goldbach's conjecture is even more likely to have finitely many counter-examples than PSQ, but my real questions are not about either of them per se, but rather:

  1. Should we expect any deep phenomena concerning such conjectures, given that:

    • The same probabilistic heuristic applies to other very similar conjectures that have 'random' counter-examples. For example, replacing the "$3k+2$" condition by "non-square" seems (empirically) to give rise to just $38$ counter-examples (the last being $21679$). I hence feel it seems to be a matter of coincidence of the same sort as the law of small numbers, that PSQ is true. (And if it so happens that PSQ is false, we could tweak it as I mentioned earlier, such as requiring $n$ to be a $3k+2$ prime.)
    • Even short programs can have complicated behaviour (witness the Busy Beaver function), and if primes are truly distributed 'as randomly as possible', then should we not all the more expect such conjectures about primes to be arising in the same way as coincidental facts concerning long-running programs, namely without any reason?

    • I am aware that there may be simple number theoretic constraints. For instance, it makes sense that PSQ has more counter-examples when the $3k+2$ restriction is removed, since on 'average' we expect primes to be equally likely $1$ or $2$ mod $3$, and so 'half the time' the sum of a prime and a square would be $2$ mod $3$. But that merely changes the constants involved in the probabilistic heuristic estimates, and so do not affect my point.

  2. Are there any uniform explanations (whether theorems or conjectures) that would encompass large classes of such conjectures of sums involving primes? In other words, am I likely wrong in speculating that most such conjectures have coincidental truth values?

$\endgroup$
25
  • 1
    $\begingroup$ If we believe in RH (and I do), primes should not be distributed as randomly as possible but as nicely as possible. $\endgroup$ Mar 3, 2019 at 13:21
  • 2
    $\begingroup$ @SylvainJULIEN: But what does "nice" mean? I used scare-quotes because I'm aware that primes can't be distributed 'randomly' in a real mathematical sense, but the PNT-based heuristic seems to work okay when there are no interfering elementary number theoretic factors. Incidentally, I also saw this post on where it goes wrong, but that feels very different to me because it is about prime gaps, whereas here I'm only talking about sums involving primes. $\endgroup$
    – user21820
    Mar 3, 2019 at 13:44
  • 3
    $\begingroup$ @user21820 Prime number theoren says that if you look at the asymptotic distribution, more specifically the number of primes in (moderately) large intervals, then there are approximately $x/\log n$ primes in an interval of length $x$ around $n$. RH tells us that this approximation is "as good as possible", specifically it works for $x\gtrsim \sqrt{n}\log n$. RH says nothing about small intervals, nor about sets which aren't intervals (like arithmetic progressions). It's expected that in small intervals the distribution is more or less random (subject to divisibility by small primes). $\endgroup$
    – Wojowu
    Mar 3, 2019 at 14:20
  • 3
    $\begingroup$ Right, in general for conjectures of this form (not only in number theory) where one feels that for large $n$ it must be true (unless some undetected conspiracy prevents it) then whether your conjecture is actually true (for all n) is something rather like random luck. In some sense, all the interest is in proving that there is no conspiracy and the statement is true for large n. If tomorrow someone shows us that $10^{4000}$ is a counterexample to Goldbach's conjecture, it won't make people noticeably less interested in proving the statement is still true for large $n$. $\endgroup$
    – user36212
    Mar 3, 2019 at 22:23
  • 2
    $\begingroup$ @user36212 I know you were not serious but... $10^{4000}=31547+(10^{4000}-31547)$ is not a counterexample to Goldbach :) $\endgroup$
    – Wojowu
    Mar 4, 2019 at 21:14

4 Answers 4

10
$\begingroup$

There exist surprising counterexamples. Elsholtz and Dietmann found the following: If $p\equiv 7\pmod{8}$ is prime, then the equation $x^2+y^2+z^4=p^2$ has no non-trivial solution. You might argue that this equation is more of Waring then of Goldbach type, but remember that sums of two squares can be described multiplicatively, so it actually is pretty Goldbach like.

$\endgroup$
5
  • $\begingroup$ It is a matter of congruence to show $z = pw$ so we'd like to say this problem wasn't in reduced form $\endgroup$
    – reuns
    Mar 5, 2019 at 2:46
  • $\begingroup$ Thanks for this, but actually it doesn't really address my actual question, which I see has to be clarified a bit. Goldbach-like conjectures assert the existence of roots of some polynomial $Q(n,x[1..k])$ for every natural $n$, with some restrictions on the roots, such as primality of some of $x[1..k]$. My question concerns such conjectures that agree with the probabilitic heuristic. In contrast, your cited theorem asserts the non-existence of roots to some polynomial equation under some restrictions on roots. So we should not be surprised if there were some 'good reason' for it. $\endgroup$
    – user21820
    Mar 5, 2019 at 6:29
  • $\begingroup$ @reuns: I wouldn't say it is a matter of congruence. You need the fact that sums of two squares can be defined in a multiplicative way. $\endgroup$ Mar 5, 2019 at 15:26
  • $\begingroup$ @user21820: The point of this example is that a good reason can be hidden. The equation $x^2+y^2+z^4=p^2$ is solvable in all non-archimedian completions, and there are enough archimedian solutions, so it is not clear how one should formulate a conjecture. $\endgroup$ Mar 5, 2019 at 15:33
  • $\begingroup$ Yes I understand that good reasons can be hidden. But like I said in my comment, my question concerns existence of roots, while your example concerns non-existence of roots. From the logic viewpoint it is clear that they are drastically different in nature. $\endgroup$
    – user21820
    Mar 5, 2019 at 16:00
6
$\begingroup$

This may not answer your question, but if so, perhaps you could clarify in what way it does not. The Cramér model of the primes predicts many statements about the primes, but Maier's theorem shows that it does not always work. So perhaps Maier's theorem is "deep"?

As for uniform explanations, perhaps the Bateman–Horn conjecture qualifies?

$\endgroup$
7
  • $\begingroup$ Yes, as I commented on my question, I did see this discrepancy with Maier's theorem. But I do not consider that it is a true discrepancy, because prime gaps are not as 'random' as Goldbach-like sums; there is a 'correlation' between a prime and the gap after it. So I do consider Maier's theorem as deep, but it isn't of the same kind as Goldbach-like conjectures. The other conjecture you mention does qualify as a uniform reason for asymptotic behaviour, but doesn't answer my question about the small cases. $\endgroup$
    – user21820
    Mar 5, 2019 at 6:38
  • 1
    $\begingroup$ @user21820 : Thank your for your clarification. I don't understand what you mean by "deep" when it comes to small cases. The sum of the first $k$ squares equals $n^2$ only when $(k,n) = (1,1)$ or $(24,70)$. Is this fact "deep"? It is related to properties of the Leech lattice. Similarly, sporadic counterexamples to other asymptotic number-theoretic statements could have connections to sporadic phenomena in other areas of mathematics. Would that be "deep"? $\endgroup$ Mar 5, 2019 at 14:51
  • 1
    $\begingroup$ @user21820 : I think we're getting into unanswerable philosophical territory. The answer to your question depends on what one deems "interesting," and is highly contingent on the current state of human knowledge rather than on anything intrinsic or objective. Perhaps an extraterrestrial who is much smarter than we are and who has a very different sense of mathematical taste would see lots of deep connections, yet when confronted with the same facts, we might find the connections uninteresting or unintelligible. $\endgroup$ Mar 5, 2019 at 18:06
  • 1
    $\begingroup$ Hmm... does the MRDP theorem make a compelling enough case (to you) that some kind of diophantine equations generally have ad-hoc solution sets? Do you think that Goldbach-like conjectures (i.e. involving primality restrictions) do not suffer from this general phenomenon, or that the ones mathematicians have been historically interested in are somehow special? $\endgroup$
    – user21820
    Mar 6, 2019 at 17:35
  • 1
    $\begingroup$ I'll think about that. I believe it should be possible, just like the answer to the generalized Collatz conjecture is uncomputable, but of course it would have to be simple enough to be convincing that one isn't 'cheating' somehow. In the best case, one might hope for an MRDP-based theorem where the required polynomial is actually simpler when we can include primality restrictions. After all, encoding sequences is often done using prime factorization. $\endgroup$
    – user21820
    Mar 7, 2019 at 16:48
6
$\begingroup$

The "main part" of a conjecture such as Goldbach's is the statement that the number of counterexamples is finite (or even: that the number of ways of expressing a number as a sum of two primes is asymptotically such-and-such). In turn, that statement is a symptom of something deeper but less well-defined - namely, that probabilistic models for the primes (if not Cramér's, then finer models) are sound. One of the chief reasons to care about Goldbach's conjecture, or gaps between primes, etc., is that it is a benchmark for the strength of our methods. Why these conjectures and not others? Well, that's a historical and psychological fact as much as a mathematical one, though, as you might expect for simple, elegant statements, there are some applications, and new ones do arise unexpectedly, now and then.

The same holds for "full" Goldbach. Extending proofs so that they are valid for all integers, and not just for very large ones, is not just a test of strength, but a reality check: we tell ourselves that the bounds that are the bread-and-butter of number theory are pretty good, but are they really? If they only give results valid for $n$ larger than $10^{1000}$, or $10^{10^{10^{10}}}$, or an unspecified constant, then, well...

But would anything change if there were a single counterexample to Goldbach at around $10^{30}$? No, not really, though probabilistic models suggest that that is extremely unlikely, and so we would be well advised to see whether our models need revising.

(Imperfect example: Mertens' conjecture ($|\sum_{n\leq x} \mu(n)|\leq \sqrt{x}$) holds in the range that has been checked, but is known to be false for very large $x$. There, however, probabilistic models did show that the conjecture was likely to be incorrect. The disproof came from studying zeroes of $\zeta(s)$, rather than from a direct computation.)

$\endgroup$
12
  • $\begingroup$ Thanks for your answer! So do you agree with user36212 and I that the truth value of such conjectures for small numbers is more or less 'random' (where "small" here depends on the specific conjecture, say less than one billion for Goldbach)? $\endgroup$
    – user21820
    Mar 10, 2019 at 9:54
  • $\begingroup$ Also, I'm not sure I understand your point that if there is a single counter-example to Goldbach at around $10^{30}$, we would be well-advised to see whether we need to revise our models. The whole point of the probabilistic model is that it is based on a assumption that holds for large intervals but not for what we apply it to. So I'm not sure how one could possibly revise it when failures arise by 'random luck'. More precisely, how would we tell if it isn't 'random luck'? Until we see too many conjectures have 'unlikely' large counter-examples, I would believe it is 'random luck'. $\endgroup$
    – user21820
    Mar 10, 2019 at 10:00
  • $\begingroup$ Anyway thanks for the remark about Merten's conjecture, though as you say it isn't an example since the probabilistic models agreed with its eventual failure. $\endgroup$
    – user21820
    Mar 10, 2019 at 10:07
  • $\begingroup$ Well, the probability (according to a given model) that $n$ be a counterexample generally decreases as $n$ increases. In this case, if our models are correct, it is very unlikely that there are any counterexamples of size $n\geq 10^{20}$ (say), and so the appearance of a single counterexample of size about $10^30$ would be strong evidence that the model needs work. $\endgroup$ Mar 12, 2019 at 4:55
  • 1
    $\begingroup$ A heuristic is precisely that: it cannot be proved or disproved. What it tells you is that, in a broad range of situations, primes should behave as if they were random, and that the effect becomes (typically) stronger, much stronger, for larger numbers - to the point that a single very large counterexample would be a strong argument for narrowing the kind of situations to which the heuristic is applicable (or else for refining the model). $\endgroup$ Mar 12, 2019 at 22:49
4
$\begingroup$

The conjecture PSQ is essentially not new. In 1923 Hardy and Littlewood [Acta Math. 44(1923), 1-70] conjectured that every large integer, not being a square, may be expressed as the sum of a prime and a square. See also http://oeis.org/A020495 for the list of non-square positive integers which are not of the form $p+x^2$ with $p$ prime, and http://oeis.org/A065377 for a list of primes not of the form $p+x^2$ with $p$ prime and $x$ a positive integer.

Concerning your second question on uniform explanations, you may consult Conjecture 2.1 of my paper Conjectures on representations involving primes published in 2017 for a General Hypothesis on representations involving primes.

PS: I don't think it is easy to pose new nice conjecures on primes.

$\endgroup$
9
  • $\begingroup$ Thanks, but as with Timothy's cited conjecture, this concerns asymptotic behaviour, whereas I'm asking about the small cases, i.e. below the bound where the asymptotic behaviour takes over. $\endgroup$
    – user21820
    Mar 5, 2019 at 6:41
  • $\begingroup$ It seems that you have not yet visited oeis.org/A020495 which lists all the known 21 terms which are neither squares nor primes plus squares. In the Extension part, it wrotes that "Almost certainly finite; no other terms below 25000000. Search extended to 3000000000 by James Van Buskirk without finding any more terms". - John Robertson (Jpr2718(AT)aol.com) (2009) $\endgroup$ Mar 5, 2019 at 6:57
  • $\begingroup$ Oh thanks yea I didn't see that. My results match theirs for non-primes, but I require a positive square so unfortunately their search doesn't cover primes. $\endgroup$
    – user21820
    Mar 5, 2019 at 7:05
  • 2
    $\begingroup$ Thanks. Anyway I have no idea why you keep saying it's not new. I don't care whether it's new; it was just an example to show how easy it is to come up with conjectures of that kind where minor tweaks have relatively large counter-examples, and as I said in my first comment my question has always been about the small cases, not about the asymptotic behaviour. (And I upvoted your answer so I can't upvote it again...) $\endgroup$
    – user21820
    Mar 5, 2019 at 13:54
  • 6
    $\begingroup$ I think you've misunderstood me from the very beginning. I'm not at all interested in formulating novel interesting conjectures. Neither do I care whether my random conjectures have been investigated before. What I asked clearly was whether there is any reason to believe that there are deep uniform reasons for such conjectures that have no small counter-examples. That's all. $\endgroup$
    – user21820
    Mar 5, 2019 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.