4 ms·

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 p

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_primitive_roots https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primit...

obastani 6y ago
I don't think that's quite right. There are two possible precise statements for such claims: 1) There exists some n such that all integers >= n satisfy the desired property. 2) For n = [a specific constant], all integers >= n satisfy the desired property. I'm not familiar with Artin's conjecture, but from your description, it satisfies (1) but not (2). The reason is that if there are at most 2 such primes, we can take n to be the larger of the two primes plus one. Since all primes are finite, this choice of n is also finite. I think the key question is whether the paper described in this article proves (1) or (2). From the discussion, it sounds like it proves (2), which is the stronger result.
- Sniffnoy 6y ago
  Yup, you came in and said it before I could. Knowing how many counterexamples there could be doesn't help very much if you don't have any bound on their size. pmiller2 seems to assume that there is some way to identify the two candidates, but the problem is that there isn't; the proof is nonconstructive. Nonconstructive proofs are a thing, and it's often important to distinguish whether a given existence proof is constructive or not.

obastani 6y ago

I don't think that's quite right. There are two possible precise statements for such claims: 1) There exists some n such that all integers >= n satisfy the desired property. 2) For n = [a specific constant], all integers >= n satisfy the desired property. I'm not familiar with Artin's conjecture, but from your description, it satisfies (1) but not (2). The reason is that if there are at most 2 such primes, we can take n to be the larger of the two primes plus one. Since all primes are finite, this choice of n is also finite. I think the key question is whether the paper described in this article proves (1) or (2). From the discussion, it sounds like it proves (2), which is the stronger result.

Sniffnoy 6y ago
Yup, you came in and said it before I could. Knowing how many counterexamples there could be doesn't help very much if you don't have any bound on their size. pmiller2 seems to assume that there is some way to identify the two candidates, but the problem is that there isn't; the proof is nonconstructive. Nonconstructive proofs are a thing, and it's often important to distinguish whether a given existence proof is constructive or not.