Suppose you have a diophantine problem whose solution is connected with the structure of the p-class group of a number field K. Then you have the following options:
- Use ideal arithmetic in the maximal order OK
- Replace OK by a suitable ring of S-integers with trivial p-class group
- Replace K by the Hilbert class field, which (perhaps) has trivial p-class group.
Experience with descent on elliptic curves has shown me that ultimately, the equations you have to solve in methods 1 and 2 are the same; moreover, the approach using ideals is a lot less technical than using factorial domains in S-integers (the class group relations come back in through the larger rank of the group of S-units). I am certain that the route via the Hilbert class field is even more technical: again, the unit group in the class field will produce more difficulties than a trivial class group will eliminate.
Edit. As an example illustrating my point in a very simple example, let me solve the diophantine equation $x^2 + 5y^2 = z^2$ in several different ways. I will always assume that $\gcd(x,y) = 1$.
1. Elementary Number Theory
The basic idea is factoring: from $5y^2 = (z+x)(z-x)$. Since $d = \gcd(z-x,z+x) = \gcd(2z,z+x) \mid 2$ we have $d = 1$ or $d = 2$; moreover we clearly have $z-x > 0$.
This gives $z+x = da^2$, $z-x = 5db^2$ or $z+x = 5da^2$, $z-x = db^2$. Solving for $x$ and $z$ yields
$$ x = \pm \frac d2 (a^2 - 5b^2), \quad y = dab. $$
2. Parametrization
Set $X = \frac xz$ and $Y = \frac yz$; then $X^2 + 5Y^2 = 1$. Take the line $Y = t(X+1)$ through the obvious point $(-1,0)$; the second point of intersection is given by
$$ X = \frac{1-5t^2}{1+5t^2}, \quad Y = \frac{2t}{1+5t^2}. $$
Dehomogenizing using $t = \frac ba$ and $X = \frac xz$ etc. gives
the projective parametrization
$$ (x:y:z) = (a^2-5b^2:2ab:a^2+5b^2). $$
If $ab$ is odd, all coordinates are even, and we find
$$ x = \frac12(a^2 - 5b^2), \quad y = ab; $$
if $a$ or $b$ is even we get
$$ x = a^2 - 5b^2, \quad y = 2ab $$
as above.
3. Algebraic Number Theory
Consider the factorization
$$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$
in the ring of integers of the number field $K = {\mathbb Q}(\sqrt{-5}\,)$.
The class number of $K$ is $2$, and the ideal class is generated by
the prime ideal ${\mathfrak p} = (2,1+\sqrt{-5}\,)$.
The ideal $(x + y\sqrt{-5}, x - y\sqrt{-5}\,)$ is either $(1)$ or
${\mathfrak p}$; thus
$$ (x + y\sqrt{-5}\,) = {\mathfrak a}^2, \quad (x - y\sqrt{-5}\,) =
{\mathfrak b}^2 $$
in the first and
$$ (x + y\sqrt{-5}\,) = {\mathfrak p}{\mathfrak a}^2, \quad
(x - y\sqrt{-5}\,) = {\mathfrak p}{\mathfrak b}^2 $$
in the second case.
The second case is impossible since the left hand side as well as
${\mathfrak a}^2$ are principal, but ${\mathfrak p}$ is not. We
could have seen this immediately since $x$ and $y$ cannot both be odd.
In the first case, assume first that ${\mathfrak a} = (a + b\sqrt{-5}\,)$
is principal. Since the only units in ${\mathcal O}_K$ are $\pm 1$,
this gives $x + y \sqrt{-5} = \pm(a+b\sqrt{-5}\,)^2$ and hence
$$ x = \pm (a^2 - 5b^2), \quad y = \pm 2ab. $$
If ${\mathfrak a}$ is not principal, then
${\mathfrak p}{\mathfrak a} = (a+b\sqrt{-5}\,)$ is,
and from $({\mathfrak p}{\mathfrak a})^2 = 2(x+y\sqrt{-5}\,)$ we
similarly get
$$ x = \pm \frac12(a^2 - 5b^2), \quad y = \pm ab. $$
4. S-Integers
The ring $R = {\mathbb Z}[\sqrt{-5}\,]$ is not a UFD, but $S = R[\frac12]$ is;
in fact, $S$ is even norm-Euclidean for the usual norm in $S$
(the norm is the same as in $R$ except that powers of $2$ are dropped).
It is also easily seen that $S^\times = \langle -1, 2 \rangle$. From
$$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$
and the fact that the factors on the left hand side are
coprime we deduce that $x + y\sqrt{-5} = \varepsilon \alpha^2$ for some unit
$\varepsilon \in S^\times$ and some $\alpha \in S$. Subsuming squares into
$\alpha$ we may assume that $\varepsilon \in \{\pm 1, \pm 2\}$. Setting
$\alpha = \frac{a + b\sqrt{-5}}{2^t}$, where we may assume that $a$
and $b$ are not both even, we get
$$ x + y \sqrt{-5} = \varepsilon \frac{a^2 - 5b^2 + 2ab\sqrt{-5}}{2^{2t}}. $$
It is easily seen that we must have $t = 0$ and $\varepsilon = \pm 1$ or
$t = 1$ and $\varepsilon = \pm 2$; a simple calculation then yields the
same formulas as above.
5. Hilbert Class Fields
The Hilbert class field of $K$ is given by $L = K(i)$. It is not
too difficult to show that $L$ has class number $1$ (actually it is
norm-Euclidean), and that its unit group is generated by $i = \sqrt{-1}$
and $\omega = \frac{1+\sqrt{5}}2$ (we only need to know that these
units and their product are not squares). From
$$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$
and the fact
that the factors on the left hand side are coprime in ${\mathcal O}_K$
we deduce that $x + y \sqrt{-5} = \varepsilon \alpha^2$. Subsuming
squares into $\alpha^2$ we may assume that
$\varepsilon \in \{1, i, \omega, i\omega \}$. Applying the nontrivial
automorphism of $L/K$ to $x + y \sqrt{-5} = \varepsilon \alpha^2$ we find
$\varepsilon \alpha^2 = \varepsilon' {\alpha'}^2$. Since the ideal
${\mathfrak a} = (\alpha)$ is fixed and since $L/K$ is unramified,
the ideal ${\mathfrak a}$ must be an ideal in ${\mathcal O}_K$.
Thus either ${\mathfrak a} = (a+b\sqrt{-5}\,)$ is principal in $K$,
or ${\mathfrak p} {\mathfrak a} = (a+b\sqrt{-5}\,)$ is; in the second
case we observe
that ${\mathfrak p} = (1+i)$ becomes principal in ${\mathcal O}_L$.
Thus either
$$ x + y \sqrt{-5} = (a+b\sqrt{-5}\,)^2 \quad \text{or} \quad
x + y \sqrt{-5} = i \Big(\frac{a+b\sqrt{-5}}{1+i}\,\Big)^2, $$
giving us the same formulas as above.
Avoiding ideal arithmetic in $K$ and only using the fact that
${\mathcal O}_L$ is a UFD seems to complicate the proof even more.
Edit 2 For good measure . . .
6. Hilbert 90
Consider, as above, the equation $X^2 + 5Y^2 = 1$.
It shows that the element $X + Y \sqrt{-5}$ has norm $1$;
by Hilbert 90, we must have
$$ X + Y \sqrt{-5} = \frac{a+b\sqrt{-5}}{a-b\sqrt{-5}}
= \frac{a^2 - 5b^2 + 2ab\sqrt{-5}}{a^2 + 5b^2}. $$
Dehomogenizing via $X = \frac xz$ and $Y = \frac yz$ yields the same
projective parametrization as above, and we end up with the
familiar formulas.
7. Binary Quadratic Forms
The equation $x^2 + 5y^2 = z^2$ tells us that the form $Q_0(X,Y) = X^2 + 5Y^2$
with fundamental discriminant $\Delta = -20$ represents a square;
this implies that $Q_0$ lies in the principal genus (which is trivial
since $Q_0$ is the principal form), and that the representations of
$z^2$ by $Q_0$ come from composing representations of $z$ by forms
$Q_1$ with $Q_1^2 \sim Q_0$ with themselves.
There are only two forms with discriminant $\Delta$ whose square is
equivalent to $Q_0$: the principal form $Q_0$ itself and the form
$Q_1(X,Y) = 2X^2 + 2XY + 3Y^2$. Thus either
$$ z = Q_0(a,b) = a^2 + 5b^2 \quad \text{or} \quad
z = Q_1(a,b) = 2a^2 + 2ab + 3b^2. $$
The formulas for Gauss composition of forms immediately provide us with
expressions for $x$ and $y$ in terms of $a$ and $b$, but they can also
be checked easily by hand. In the first case, we get
$$ x^2 + 5y^2 = (a^2 + 5b^2)^2 = (a^2 - 5b^2)^2 + 5(2ab)^2, $$
and in the second case we can reduce the equations to this one
by observing that $2Q_1(a,b) = A^2 + 5b^2$ with $A = 2a+b$, which gives
$$ x^2 + 5y^2 = \frac14\Big(A^2 + 5b^2\Big)^2
= \Big(\frac{A^2 - 5b^2}2\Big)^2 + 5(Ab)^2. $$
Let me first comment on your examples:
The record is acually $t=n^{0.525}$, due to Baker, Harman and Pintz.
A slightly thinner sequence of this type is $n=a^3+2b^3$, investigated by
Heath-Brown, and also cubic polynomials in two variables,
by Heath-Brown and Moroz,
eprints.maths.ox.ac.uk/00000163/01/morozcub2.pdf
Other polynomials in two or more variables, like those that you suggest,
are certainly not known by today's methods.
- Here is a sketch to obtain primes with a density of
0.7375 one bits (compare also this paper by Eric Naslund
https://arxiv.org/abs/1211.2455
and his answer on mathoverflow, to a question by Gil Kalai
Primes with more ones than zeroes in their Binary expansion
their-binary-expansion/97345#97345
By Baker-Harman-Pintz one can fix the first 0.475n bits as one.
With $x=2^n$
There are $\gg x/\log x$ many primes in the interval [2^n-(2^n)^0.525, 2^n].
For the remaining 0.525n bits about 50% must be 0 and 50% ones.
If the proportion of one bits was smaller, then estimating the tail
(sum of binomial coefficients) would show the number of primes is too small.
So altogether the asymptotic density of one bits can be as large as
$(0.475+1/2\, 0.525)n=0.7375n$.
Here is a paper, where a similar method was used to find quadratic non-squares
or even primitive roots, with only few one-bits (less bits than the least non-square or least primitive root might need).
Now an example for a sequence with quite small
counting function (Problem 1).
Let us first look at large and sparse, but finite sets.
Let $F_n=2^{2^n}+1$ be the $n$-th Fermat number.
Let $D(F_n)$ be the set of its divisors.
Observe that the number of divisors is (by Wigert's bound)
$d(F_n)=O(exp (c \frac{\log F_n}{\log \log F_n})=O(\exp(c' 2^n/n)$.
Let $S(k)=\cup_{n=1}^k D(F_n)\subset [1,2^{2^k}+1]$.
Observe that $|S(k)|= O(k \exp(c' 2^k /k)< (F_k)^{0.499}$.
The set of divisors of the Fermat numbers contains
also the prime factors (for each $F_n$ at least one new prime number,
as the Fermat numbers are coprime).
Well, to extend this to an infinite set we need to take care of the fact
that with $F_{n+1}$ one possibly also adds smaller elements, so that
the counting becomes a bit more tricky.
But these added elements are not very small,
as one can show that the prime factors of $F_n$ are
at least of size $2^n$.
So maybe one can take the union over a thin subset of
the Fermat numbers, such as $\cup_{n=1}^k D(F_{2^n})$ or similar,
Or one only takes the second smallest element $s_n$ of $D(F_n)$,
(which must be a prime!).
$S= \cup_{n=1}^{\infty} s_n$.
Note again, that the $s_n$ are distinct and are (at least)
exponentially increasing, $s_n>2^n$, by properties of the Fermat numbers.
In case anybody thinks this is an artificial sequence, equivalent to writing
down some prime numbers:
well, the prime divisors of sequences such as
$s_n=n^2+1$ or $s_n=\lfloor 2^n/n\rfloor$
might not work, as these might be too dense.
Best Answer
Here is the proof of Gersonides [Levi ben Gershon] (1343) for $2^n-3^m=1$. It uses nothing more that arithmetic modulo $8$.
Case I: $m$ is even. Then $3^m$ is 1 mod 4, so $2^n$ is 2 mod 4, implying $n=1$ and $m=0$.
Case II: $m$ is odd. Then $3^m$ is 3 mod 8, so $2^n$ is 4 mod 8, implying $n=2$ and $m=1$.
The alternative equation $3^m-2^n=1$ follows similarly when $m$ is odd, but is a bit more tricky when $m$ is even (hint, factor $2^n=3^m-1=(3^{m/2}+1)(3^{m/2}-1)$ and argue from there).