Growth of $H(n)$, least $l$ with $\gcd(k^n\!-\!1,l^n\!-\!1)=1$ for some $k<l$: is $H(n)=3$ i.o.? (Erdős #820)

For a positive integer $n$, let $H(n)$ be the smallest integer $l$ for which there exists $k<l$ with $\gcd(k^n-1,\,l^n-1)=1$. Erdős posed several questions: (i) is $H(n)=3$ infinitely often — equivalently, is $\gcd(2^n-1,3^n-1)=1$ for infinitely many $n$; (ii) estimate the growth of $H(n)$: is there a constant $c>0$ such that, for every $\epsilon>0$, $$H(n)>\exp\!\big(n^{(c-\epsilon)/\log\log n}\big)\ \text{for infinitely many }n\quad\text{and}\quad H(n)<\exp\!\big(n^{(c+\epsilon)/\log\log n}\big)\ \text{for all large }n;$$ and (iii) does a similar upper bound hold for the least $k$ with $\gcd(k^n-1,2^n-1)=1$?

Acceptance. FULLY RESOLVES: complete proofs (Lean/Coq preferred, else full written) settling the stated questions — proving or refuting that $H(n)=3$ infinitely often; proving the matching upper and lower growth bounds $\exp\!\big(n^{(c\mp\epsilon)/\log\log n}\big)$ for some explicit $c>0$ (thereby determining the growth law of $H(n)$); and settling the base-2 variant (iii). A proof of any one named sub-question resolves that sub-question. ADVANCES: improve, with proof, the best proven lower bound — currently $H(n)>\exp\!\big(n^{c/(\log\log n)^2}\big)$ infinitely often (Erdős), or the sketched $H(n)>\exp\!\big(n^{c/\log\log n}\big)$ infinitely often (van Doorn) if made rigorous; prove any nontrivial upper bound of the form $H(n)<\exp(n^{o(1)})$; or a reproducible computation extending the $H(n)$ table and OEIS A263647 to a new certified range, with the search code and a fitted estimate of the growth constant $c$. Deliver the proof, the improved bound with proof, or the computation code plus certified extended tables and the fitted constant.