Proof theory and primitive roots

Question

I have had this question on my mind for two decades. We know, after Heath-Brown, that one out (say) of 3, 5, 7 is a primitive root mod p for infinitely many primes p. We just don't know which one. (We presume each is, or some GRH goes wrong per Hooley.)

Now if I invoke proof theory, it must be in terms of the proof of the result, not just that it has been proved. The result is a disjunction "3 is" or "5 is" or "7 is", and a proof according to constructive canons ought to be rendered down to a proof of one such statement.

So we can assume there is an obstruction to making the proof constructive in any facile way. What I'd like to ask is for a friendly logician to point out where the obstruction would be, and if possible name it as some standard issue.

The structure of the proof is in two parts. One analytic part uses Chen's Goldbach technique. It basically locates primes p of type 2qr + 1, if I recall correctly, with q and r primes in certain ranges by magnitude and I suppose in some arithmetic progressions. And an algebraic part, which is at the level of Lagrange's theorem. I have always assumed the trouble is with the second part. Which is relatively so much shallower, prompting my wish to know more.

Answer 1

It's the Pigeonhole Principle in the final step which is not constructively valid, not Heath-Brown's main result which, after inspection, doesn't show any of the tell tale signs of non-constructiveness.

Let $P_t$ be the set of all primes for which $t$ is a primitive root. Heath-Brown shows that if $q$, $r$, $s$ are three non-zero integers which are multiplicatively independent and that $q$, $r$, $s$, $-3qr$, $-3qs$, $-3rs$ and $qrs$ are not squares, then $P_q \cup P_r \cup P_s$ is infinite (and indeed that $\left|(P_q \cup P_r \cup P_s) \cap\lbrace1,\dots,x\rbrace\right| \gg x/(\log x)^2$). It is not constructively valid to draw from this the conclusion that one of $P_q$, $P_r$, $P_s$ is infinite. However, one can draw the more negative conclusion that $P_q$, $P_r$, $P_s$ are not all three finite.

One can see this using a Brouwerian counterexample which is analogous to the above situation. Let $A$ be the set of all $n$ for which there is a string of $333$ consecutive $3$'s in the first $n$ digits of $\pi$, and let $B$ be the complement of $A$. This is legitimate since we can always compute the first $n$ digits of $\pi$ to determine whether $n \in A$ or $n \in B$. Clearly $A \cup B = \lbrace1,2,3,\dots\rbrace$ is infinite. However, we cannot assert that $A$ or $B$ is infinite without knowing whether the digits of $\pi$ do or do not contain $333$ consecutive $3$'s. In the same way that GRH allows us to say that all three sets $P_q$, $P_r$, $P_s$ are infinite, the well-known conjecture that $\pi$ is normal allows us to assert that $A$ is infinite and $B$ is finite, but we don't know yet.

I haven't gone through Heath-Brown's argument in sufficient detail to assert without doubt that it is completely constructive but if there is a non-constructive part it must be hidden somewhere in some of the results he cites and not in the paper itself. In the paper, Heath-Brown explicitly computes an asymptotic lower bound on $\left|(P_q \cup P_r \cup P_s) \cap \lbrace1,\dots,x\rbrace\right|$. The argument is not straightforward but it is not convoluted and looks completely constructive. Instead of considering all primes, he considers a smaller but still large set of well-behaved primes $p$ for which he can break down the three multiplicative subgroups mod $p$ generated by $q$, $r$, $s$ into a handful of cases. He then computes upper bounds for the number of well-behaved primes up to $x$ falling into a case where none of $q,r,s$ are primitive roots. Adding these up and subtracting the result from a lower bound on the number of well-behaved primes up to $x$ gives $\left|(P_q \cup P_r \cup P_s) \cap \lbrace1,\dots,x\rbrace\right| \geq Cx/(\log x)^2$ where $C$ is a constant that may depend on $q, r, s$. Since the multiplicative subgroups of mod $p$ generated by $q$, $r$, $s$ are finite subgroups of a finite group, the various cases are decidable and it is fine to use the law of excluded middle to break into cases that way.

Answer 2

As with most ineffective proofs in number theory, the point is that the reasoning proceeds by assuming that 3, 5, and 7 do not have the desired property. Under this assumption, various estimates are made that are eventually shown to contradict each other. By the law of the excluded middle, we conclude that one of 3, 5, and 7 must have the desired property.

Why can't this proof be reworked into a constructive proof? Well, it's not clear how you would even get started, since the whole chain of logic begins by assuming something that (as we eventually discover) isn't even true. We know that there's no general trick for eliminating uses of the law of excluded middle, so the implicit burden of proof in the question "Why can't" is misplaced; it's the person who thinks there ought to be a constructive proof who needs to provide a reason for that faith.