Hacker News Reader

Maybe I'm being super pedantic and possibly confrontational (I apologise in advance) but it jumped out on me here. I think you've misunderstood the 'famous elementary proof' that there are infinite primes. You do not create a new prime as you have suggested (quoted below).

"Multiply them together and add one. No prime divides the new number (because "every" prime leaves a remainder 1), so you've just produced a new prime. This new prime is larger than the largest prime in your finite set because you multiplied that by the rest of them and added one to get it."

Instead you have created a number that may or may not be prime but definitely requires a new prime number (not in your set) to factorise it. Counter example: Take your set of prime numbers to be {2,3,5,7,11,13} then

(2.3.5.7.11.13)+1 = 30031

30031 factorises into 59.509 so you have found two prime numbers that are not in your original set.

EDIT: Responding to the edit above. The problem is that you claim that you make a new prime number by multiplying them all together and adding one. You didn't multiply all the numbers and added one to get the prime number, you multiplied all the numbers and added one to get a number (POSSIBLY NOT PRIME) whose FACTORS are prime numbers not in your original 'supposed' finite set. Your proof essentially lacks the step: IF new_number is prime: proof finished ELSE: factor new_number and show that at least one of the factors is not in your finite set.

EDIT 2: Counterexample number 2. Suppose your finite set of primes is {2,7} (2.7)+1 = 15 So you have found 3 and 5 as primes that are not in your original set and are SMALLER than the largest prime in your original set. This is now a second mistake in your proof. Whether you are trolling or just too arrogant to see the mistake/error I do not know.

You're entirely correct. A very ironic mistake/misunderstanding for the parent post to make.

Edit: I've thought about this a bit more, and you can save the parent post by prepending a result like "Every number larger than one is either prime, or divisible by a prime smaller than itself". In this case you can then assert that your constructed number is prime. However, this result requires its own proof and was not mentioned by the parent post.

Suppose 2 and 7 are the only primes < 15. Then 15 is prime because its prime factorization couldn't contain any other number (2 * 7+1 makes it relatively prime to both 2 and 7 which under the supposition are the only primes < 15.) This is true if we suppose 2 and 7 are the only primes < 15, and that's just what the word "suppose" asks you to entertain.

This little mental exercise proves that 2 and 7 can't be the only primes in existence. It doesn't really matter what 15 really is or isn't. No need to add noise about it. We only care about the supposition, which you cut out of your quote.

Hope this explains why I didn't deal with the true status of new_number! It just doesn't matter.

However, I'm disappointed in you, in the other respondent, and in the moderation here, and I'm glad I made this alternate account.

Technically, the parent post literally said "No prime divides the new number ... so you've just produced a new prime". It does not make the direct claim that the new prime is equal to the new number.

It is possible that the OP did not make the mistake that you are attributing to them, although best case is that the exposition was simply unclear.

Thanks, very charitable reading but doesn't work because next sentence I said that the new prime is larger than largest. As other poster points out if 2,7 are all your primes you produce 15, whose primes are not larger than 7 so the "new prime" wasn't referring to one of them.

But that's not how I argued. Instead I showed that 15 is the new prime because it's relatively prime to all the primes. (By the assumption we had started from all the primes.) And this is what falsifies the assumption.

I think my argument is fine and I don't need to address whether 15 is really a prime.

Your post says "No prime divides the new number, so you've just produced a new prime." What, exactly, do you mean by "produced"? You say produced, not "established the existence of", so it makes it sound like you are assuming a constructive argument.

Do you mean that the number you've produced is prime? Or do you mean that "the number you have computed is either prime or has a prime factors not in your list of primes, therefore, by computing the factorization of that number, you produce a new prime"?

The former statement is demonstrably false, the latter statement is true. Others have read your proof as stating the former, and I argue that the latter is a generous but not unreasonable interpretation of your phrasing.

Andrew, I perfectly see what you're saying, but I am telling you it is absolutely no problem that there's a false statement.

Remember that we are arguing from the false assumption that you start with the finite set of all primes, up to some largest prime, L. Call this false assumption A. It's fine to make false statements that follow from A, no problem at all. Indeed this is the point.

One definition of a prime is that there are no primes smaller than it in its prime factorization. We'll call this definition NSPIPF - no smaller prime in prime factorization. Is NSPIPF an OK test for primality? Sure.

So when you get to new_number, produce the prime factorization. Does it meet the definition of NSPIPF? Yes, because we made it relatively prime to every prime (under assumption A).

It passes primality test NSPIPF. Under A. And therefore is prime. Under A. (This is the part you and others object to, but it's absolutely flawless application of the NSPIPF primality test.) It doesn't matter that in some other way I could also get to a contradiction. For now this is what we do.

Under A, using NSPIPF primality test, we just proved new_number is prime.

Next we show that this new_number definitely wasn't in the set of all primes, since it's larger than L, having had L and a bunch of other positive integers as factors and then one added to that for good measure. It is at this point that we show explicitly that A cannot be true, because we used A to produce a prime that wasn't in the set of all primes.

It doesn't matter if that was a false statement!

I think all this is in my original comment and it is a flawless proof by contradiction. I asked you to "Suppose there are just finite primes, up to some largest" and you gave up when you started seeing false statements, rather than at the end of the paragraph where I presented the conclusion in black and white.

Nobody is contesting that the conclusion is true, just that the proof is unsound as written.

Here you've introduced a definition of prime that is different than the usual one, and is in fact self-recursive. NSPIPF is "no smaller prime in prime factorization". What is the first "prime" in this definition? Is it a number such that there is "no smaller prime in prime factorization"? What is the second "prime" in that definition? Is that the usual "prime factorization", or is it an NSPIPF factorization? In other words, how would you prove that 2 is prime given the NSPIPF definition?

It is more natural to talk about primality as a test that can be done independent of any assumptions about other primes, but rather as a matter of whether it can be expressed as the multiple of some number other than 1 and itself. That way we can make a precise statement about the product of the finite set of primes plus one without reference to the set of primes.

>It is more natural to talk about primality as a test that can be done independent of any assumptions about other primes, but rather as a matter of whether it can be expressed as the multiple of some number other than 1 and itself

This is clearly not what I was doing. I clearly referred to having no smaller prime factors. Anyway this aside is tiresome, it's like poking me for saying "every positive integer has a prime factorization" and then asking, okay, so what about 1 or something. I think my proof is fine and I'm not going to defend it anymore.

As I suggested above, it looks like you are implicitly using a result something like:

"Any number that is relatively prime to all other primes is itself a prime"

You would need to first state and prove this in order for your original post to constitute a rigorous proof.

I haven't heard of EMH before today and can't really comment on that.

But it seems to me that even in the example from your note the stock price will tend to reflect the the correct price. As you realease new information the factorization becomes more feasible and once it's feasible enough the stock price will get the correct value. Maybe we should amend EMH to say that asset prices fully reflect all the facts that are feasible to compute from the available information.

Anyway, the reason I'm writing this comment is to say that you should no be so sure of your proofs, especially because your proof of the infinitude of primes is wrong. This proof does not show that the new number (the product of primes + 1) is prime. It shows that none of the primes are factors in this new number and from that it follows that there must be more primes, but it does not follow that the new number is necessarily prime (it might be a product of another unknown primer and the others).

Sure, but you can't "amend EMH" to fully reflect all the facts that are "feasible to compute" any more than you can amend it to say that that asset prices fully reflect the "best feasible analysis". That's not EMH.

For the prime proof, the new number is prime as long as as it has no prime factors < itself, which we assumed at the start. This guarantees it's prime under our assumption and this falsifies the assumption. Doesn't matter if it's really prime.

Your proof for the EMH hinges on a very specific technicality -- whether the secret prime, P, is public knowledge, or to what degree it is public knowledge.

I think if we were to approach the EMH from a constructive or computability approach, we'd have to make that definition much crisper. That is, the feasibility of computing the factorization based on limited information determines whether the information is actually "available" in the sense of the EMH.

In the real world we can see things like drug trials that will determine the success of a pharmaceutical company. The information that the drug works or doesn't work, or has side effects, would be "apparent" to a hypothetical "ideal" expert in human biochemistry -- so simply knowing the chemical formula for a new drug, the information about its working is "available" in that sense.

If you can show an inefficient market experimentally whenever you want, that's good enough to disprove EMH. The EMH doesn't say, "All information is normally factored into the price, except for technicalities."

I like your drug trial example but a "hypothetical ideal expert" isn't assured to exist. Do you have an existence proof?

On the other hand, unique prime factorization is assured, we know that given infinite time anyone can factor any large number.

The EMH is usually restricted to "available information". This hinges on what "available" means.

I would argue that until the search space was reduced to the point where it would be feasible to factor the secret before another digit is revealed, the information is not "available" in any useful sense. So maybe, in some sense, this helps us narrow down a definition of what "available" means, but since real-world price signals are rarely something that is deterministically computable, I'm not sure that this would help to clarify the EMH.

In my drug trial example, such an expert does not exist, but if we're dealing with mundane real-world stuff, then the assurances that the proposed $1B gift to a random company would actually go through would have to be factored into any strategy -- why would I bother committing computing resources to factoring the number when in all likelihood the billion dollars would not handed over because why would anyone actually do that?

100 possibilities are really easy to test, though, so P must be fully available near the end. We can all agree it's not available at the beginning (subject to the methodology.) So it becomes more and more available over time, but that is not what the EMH says -- at all. If you are saying market prices will reflect information as a function of how "readily" available it is (for example how smart you have to be to see it), that is just not EMH.

For the drug trial example, again, I like it but perhaps such an expert is theoretically excluded? Your statement might be like saying "suppose there's a hypothetical O(n) halting algorithm that answers the halting problem in constant time for the length of the program it's testing." That's nice but there's a proof that what you've just hypothesized is impossible[1].

I am not exactly saying that an ideal expert in human biochemistry who can predict the results of drug trials is impossible, but how do we know it's possible? I mean, is chemistry guaranteed to be fully computable or something?

For your last point, I think that what I asked to assume (that the $1B transfer is credible, that the computer is secure) are nowhere near the size of assumption of something like "assume there exists someone who can predict biochemical reactions in humans without testing." Basically the legal instruments and secure computers I included are easy, solved problems that I ask the reader to assume are being implemented following best practices.

[1] https://en.wikipedia.org/wiki/Halting_problem

> Have another account here but don't want to take the karma hit for being a crank.

Stop worrying about karma and what some random dudes think about you/your comments on HN or whatever online board.

If you think it is wrong simply don't do it.

You get silenced by karma when you have unpopular opinions.

You know, just how people used to tell homosexuals to not be gay when other people thought they were freaks because of it.

What I’m saying is stop worrying about karma and talk your opinions. Karma is not money or air. Your opinion matters.

And what I'm saying is that you literally can't when you get enough negative karma. I have three HN accounts and two of them have negative karma and can't post without mod approval.

Or it just says: You're posting too fast. Please slow down. Thanks.

Then you must be doing something wrong. I, always, speak my mind. This sometimes backfires karma wise but on the long run i think it was minimal.

It's called having unpopular opinions.

That you're conventional enough to never stand out of the herd says more about you than anything else.

Individual comments effectively get silenced (or at least buried) by downvoting, changing the account you post with won't change that. You can get an account shadowbanned however which does reduce the visibility of all its comments but that's a different issue, I don't think you can trigger a shadowban automatically by downvotes alone (or maybe only in extreme cases).