Wikipedia:Reference desk/Archives/Mathematics/2022 November 14

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 14

Wall-Sun-Sun primes

Why have we conjectured the existence of infinitely many Wall-Sun-Sun primes even though none are known?? Georgia guy (talk) 17:10, 14 November 2022 (UTC)

Well, one of the oldest (and most important) theorems regarding prime numbers is Euclid's theorem, which has proven that there must be an infinite amount of prime numbers. In general, it is usually conjectured that for any well-defined subset of prime numbers, such as Mersenne primes, there would also be an infinite number of those as well, though these are often in the form of conjecture rather than proof. See, for example, the Lenstra–Pomerance–Wagstaff conjecture about Mersenne primes, or the twin prime conjecture or more generally Polignac's conjecture. It should be noted that proof of existence does not require any actual examples. On the balance, it is likely that Wall-Sun-Sun primes exist, though given that every single finite number, no matter how large, is by definition infinitesimally small compared to actual infinity. Who knows, maybe the first one exists at an order of magnitude so large it cannot be expressed even if we used all of the matter in the universe. But it may still exist. I'm not sure that Wall-Sun-Sub primes have been proven to exist as yet, but often times, if one exists, then it is likely infinitely many do as well. --Jayron32 17:24, 14 November 2022 (UTC)

Courtesy link: Wall–Sun–Sun prime. I'm not saying it's the case here, but sometimes you can make heuristic arguments that the number of certain primes is infinite. For example if you know how fast a sequence grows, you know the "probability" of a number of a certain size being prime, and you can combine this information to produce a series whose sum is an estimate for the number of primes in the sequence. If the series diverges then you might conjecture that the number of primes is infinite. The article isn't too clear on the evidence for and against the conjecture (there is a link though), but one possibility is that there seems to be infinitely many near-Wall–Sun–Sun primes. In the absence of any evidence to the contrary, the "probability" of a near-Wall–Sun–Sun prime being an actual Wall–Sun–Sun prime is 1/3, so one might expect a third of the entries in this seemingly infinite sequence to be primes we're looking for, even though none have shown up to the current limit of calculations. Another piece of evidence on the "for" side is that Wall–Sun–Sun prime are the case k=1 of k-Wall–Sun–Sun primes, and these are known to exist for k=2 through 10, with k=11 being the next k for which the question is open. It would seem odd if there existed k-Wall–Sun–Sun primes for most values of k but not for a few "random" exceptions (through stranger things have happened).

I have a hard time getting enthused about conjectures relating to prime numbers though, there are many of them and it seems that the mathematics needed to resolve them hasn't been invented yet. In cases where weaker versions have been proved, the proofs are so complex and lengthy that it's difficult to follow or appreciate them. Analytic number theory opened up new avenues of proof, and is the key to Dirichlet's theorem on arithmetic progressions. But absent the creation of new branches of mathematics, I think progress will be incremental. --RDBury (talk) 06:47, 15 November 2022 (UTC)

Something regarding a prime p has p possible values: 0 to p-1. If it's 0 then p is a Wall-Sun-Sun prime. The values appear to be randomly distributed and there is no apparent reason to think that 0 is impossible so for a random prime p, the expected chance of a Wall-Sun-Sun prime is 1/p. The estimated number of Wall-Sun-Sun primes is then the sum of 1/p over all primes p and this sum is infinite (this is the divergence of the sum of the reciprocals of the primes). But all primes below 300×10¹⁵ have been tested without finding one, shouldn't we start to suspect there is something unknown which prevents the 0 value? Not really, the sum diverges very slowly. The sum of 1/p for all tested primes is only around 3 and the values keep looking random. If the search limit could be extended to 10³⁰, which is unlikely to ever happen if they still have to be tested one by one, then the expected number of primes only increases by around 0.5. We will probably never find a Wall-Sun-Sun prime but keep expecting there are infinitely many. If we do find one then it will probably be due to new theory and not an increase in computer speed or search time. I don't agree with Jayron32 that we should usually expect infinitely many primes of a given form. When mathematicians make such predictions it is usually because of heuristic arguments like above: Sum "the expected chance" of individual candidates and show this sum is infinite. I use quotation marks because a specific number either has a property or not, and "the expected chance" is a qualified guess based on incomplete information. Maybe it later turns out to not be as qualified as we thought. We usually only talk of "the expected chance" until we have actually tested the number. What is the "expected chance" that 4 is prime? A common general estimate for n says 1/log(n) which is 0.72 for 4. Does that mean 4 has 72% chance of being prime? Some may argue this is actually a fair estimate. Others may say it's obviously composite so the chance is 0. The sum of infinitely many positive numbers can be finite. For example, 1/2 + 1/4 + 1/8 + ... = 1. It's a finite sum similar to this which makes most mathematicians expect that the number of Fermat primes is finite. You will hear more conjectures of the form "There are infinitely many primes of this form" but that's because such forms often seem more "interesting" and we discuss them more. The two main reasons for not expecting infinitely many primes are a little "boring": The sequence grows rapidly (like doubling the number of digits each time), or we can easily prove a factor of each number after the first one or two, e.g. n²-1 = (n-1)×(n+1). Numbers of form 2^k+1 is a combination of these: If k has an odd factor above 1 then we can prove a factor of 2^k+1 so the only primality chance is for the rapidly growing Fermat numbers 2²ⁿ+1. This and the apparent coincidence that it's prime for n = 0 to 4 makes it more interesting. It also has a history going back to the 17th century and remains unsolved. PrimeHunter (talk) 08:41, 15 November 2022 (UTC)

Your heuristic argument is one I hadn't thought of; it's simple and elegant but I think your point is that it's only an argument, not a proof, and probably not convincing enough to counter the existing evidence to the contrary. Perhaps a more relevant calculation is the probability of getting 0 hits when the probability of a hit is 1/p and trials run over all primes less than 300×10¹⁵. Re-reading the original post, it asks "Why do we conjecture ... ?" I think the OP is under the impression that there is agreement (among "we") on what should be a conjecture and what shouldn't be. A conjecture is just an opinion about what might be true, and if enough prominent people work on resolving it then it may gain some notability, but that doesn't imply everyone agrees with the opinion. On a related note, I was just looking at the article on Landau's problems, a set of 4 conjectures proposed 110 years ago, though most date from earlier. Landau stated they were "unattackable at the present state of mathematics". Math is still 0 for 4 on them, and while some have been "attacked" since, and partial results obtained, I think it's fair to say that no beachheads have been established and significant progress is still doubtful. That's just four of the 60+ unsolved problems on prime numbers in List of unsolved problems in mathematics. --RDBury (talk) 10:13, 15 November 2022 (UTC)

PS. I just did a ball-park estimate on the probability: Assuming that a hit for p is random with probability 1/p then the probability of getting no hits for any p < 300×10¹⁵ is about 1%. This is low, but not so low as to strain credulity when you consider that if there had been a hit then this discussion would probably not be occurring. --RDBury (talk) 10:44, 15 November 2022 (UTC)

@RDBury: I guess you meant to say "not so low as to strain credulity". I view this as an example of the multiple comparisons problem. We look for primes in lots of sequences. Some have a little more primes so far than expected, some a little fewer. This one has 3 fewer which just happens to place it at 0 and cause increased interest. To be more specific than my first post, it is known that if p is prime then a certain number $F_{\alpha (p)}$ is divisible by p. If it's also divisible by p² then p is called a Wall–Sun–Sun prime. ${\frac {F_{\alpha (p)}}{p}}$ is an integer so the question is whether this integer is divisible by p. It appears random so the estimated chance is 1/p. If we try to divide it by p then there are p possible values of the remainder: 0 to p-1. These remainders look random. The wanted 0 value is the one I talked about in the first post. We haven't seen it yet but so what? PrimeHunter (talk) 19:55, 15 November 2022 (UTC)

I inserted "not"; sometimes they get away from me. I guess what I was getting at is that the difference between the observed value and expected value doesn't mean much unless you know the actual distribution. If there expected value is 3 and there is only a .00001% chance to get 0, then a result of 0 is surprising. If it's a 1% chance then result of 0 means perhaps there's some unknown factor, but a coincidence is still plausible. I'm also trying to take Selection bias into account. In any case, yes, this is probably a moot discussion; it's not a proof, merely a lack of disproof. --RDBury (talk) 10:12, 16 November 2022 (UTC)

World-class mathematicians will only publicly venture conjectures as such if they have a strong hunch, based on their experience and expertise, that its dictum is true. It is a reasonable question to ask what makes them think so, but they themselves may not have the answer, just like a chess grandmaster may "feel" a move is strong while unable to explain cogently why.  --Lambiam 10:32, 15 November 2022 (UTC)

Mathematical conjectures in general can be based on different things like the intuition of a mathematician. When mathematicians state conjectures about prime numbers, it is usually based on specific heuristics of the form: "If we assume these numbers behave randomly (possibly apart from a known pattern we compensate for) then the estimate becomes ...". The primality chance 1/log(n) of a random n is central in such conjectures. PrimeHunter (talk) 19:33, 15 November 2022 (UTC)

Such statements about expected chances can be made formal. Let $r_{n}\,{\hat {=}}\,\lceil {\sqrt {n}}\rceil .$ Then the probability that a number drawn at random from the discrete uniform distribution on the interval $[n-r_{n},n+r_{n}]$ is prime is asymptotically equal to ${\tfrac {1}{\log n}}.$  --Lambiam 10:20, 15 November 2022 (UTC)