Hacker News Reader

Comment by sohkamyung | Hacker News Reader

It does say this at the end of the article.

> Because of the probabilistic elements, their proof only works for large enough hypergraphs — those with more than a specific number of vertices. This approach is common in combinatorics, and mathematicians consider it a nearly complete proof since it only omits a finite number of hypergraphs.

View on HN

Ah, I missed that, thanks. That said, I think there's still a big difference between "only omits a finite number of hypergraphs" and "only omits a finite number of hypergraphs of bounded size". I'd regard the latter as nearly a complete proof, not so much the former. (E.g., I don't think anyone would say that we have a nearly complete proof of Artin's primitive root conjecture.) Now, it sounds like this is the latter in the sense that it can be made so, but it also sounds like it's not explicitly the latter and someone needs to actually still do that work.

For any n, there are only a finite number of hypergraphs on n vertices, much less linear hypergraphs. It is therefore correct, and equivalent to say that the proof omits "only a finite number of hypergraphs," when the result is shown for sufficiently large n. I haven't read the paper through, but, I suspect it's even possible to extract some explicit value of n for which the conjecture is true. In any case, it's enough to know that there is such an n.

I looked up Artin's primitive root conjecture on Wiki because I wasn't familiar with the result. I think you may be referencing the result that there are at most 2 primes for which the conjecture fails, no? If so, I would agree that's not close to a complete proof.

The difference here is that, in principle, since hypergraphs are just finite combinatorial objects, one could, in theory just run a generic coloring algorithm over the finite number of things left out of the proof to obtain the complete result with a bow tied around it.

In the case of Artin's conjecture, you have two difficulties: identifying 1 or 2 candidate primes for which it may fail, and verifying the conjecture for those primes. Even if you can somehow overcome the first difficulty and identify the candidate primes for which it may fail, in the absence of machinery that lets us make such a conclusion for those two primes, we are reduced to calculating an infinite number of discrete logarithms, which, obviously doesn't fly.

So, TL;DR: the difference here is literally the difference between finite and infinite. There are a finite number of hypergraphs left out, which can, in theory be tested using a finite number of operations to verify the conjecture. Not so with Artin's conjecture.

https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primit...

There is not a big difference between those two statements. In fact they are identical in meaning.

Reply on news.ycombinator.com