Many Diophantine equations become finite only after arithmetic structure is exposed. S-unit groups restrict where prime factors may occur. Norm equations turn polynomial expressions into multiplicative field data. Thue equations encode homogeneous norm forms. Logarithmic embeddings convert units into lattices, and LLL reduction turns enormous theoretical exponent bounds into ranges that can actually be searched.
This is Guide 40 in the Bukit Timah Tutor Computational Number Theory series. It closes Batch 10 by combining the maximal orders of Guide 37, prime ideals from Guide 38, local valuations from Guide 39, and the lattice-reduction machinery of Guide 15.
1. Units first
An algebraic integer u in O_K is a unit when it has a multiplicative inverse in O_K.
Equivalently,
N_K/Q(u)=±1
for a number field over Q.
Dirichlet’s unit theorem gives
O_K^× ≅ μ_K × Z^(r1+r2−1)
where μ_K is the finite group of roots of unity.
2. S-units
Let S be a finite set of finite prime ideals of O_K.
An S-unit is an element x in K* satisfying
v_P(x)=0
for every finite prime ideal P not in S.
Equivalently, the principal fractional ideal (x) may involve prime factors only from S.
Ordinary units are the case S empty.
3. Rank of the S-unit group
The S-unit theorem gives
O_(K,S)^× ≅ μ_K × Z^(r1+r2−1+|S|).
Each allowed finite prime adds one free valuation direction to the ordinary unit lattice.
This is one reason S-units are computationally manageable: despite allowing denominators, they still form a finitely generated group.
4. Running field Q(√5)
Let
K=Q(√5), ω=(1+√5)/2.
The field has two real embeddings, so
r1=2, r2=0.
The ordinary unit rank is therefore one.
A fundamental unit is ω, with
N(ω)=−1.
5. Allow the prime above 2
In Q(√5), the rational prime2 is inert because
x²−x−1
is irreducible modulo2.
Thus
P=(2)
is a prime ideal of norm4.
Take
S={P}.
The S-unit rank becomes
2+0−1+1=2.
6. Explicit S-unit generators
Modulo torsion ±1, the S-unit group can be generated by
ω and 2.
Thus an S-unit has the form
± ω^a 2^b
with integers a,b.
The element2 is not an ordinary unit of O_K, but it becomes invertible after localisation because the only finite prime in its ideal factorisation is allowed in S.
7. Localisation viewpoint
The ring of S-integers is
O_(K,S)={x in K : v_P(x)≥0 for all P not in S}.
Its unit group is exactly the S-unit group.
Localisation therefore converts selected prime ideals into allowable denominators while preserving integrality everywhere else.
8. S-unit equations
The basic S-unit equation is
x+y=1, x,y in O_(K,S)^×.
For fixed K and S, this equation has only finitely many solutions.
That finiteness is profound: both x and y range through infinite multiplicative groups, yet the additive relation cuts the possibilities down to a finite set.
9. Why S-unit equations matter
Many Diophantine problems can be transformed into S-unit equations after factorising differences, discriminants or ideals.
They appear in:
Thue–Mahler equations integral points on curves unit equations perfect-power problems norm-form equations algorithmic finiteness proofs.
A solver for S-unit equations is therefore a reusable engine rather than one isolated routine.
10. Norm equations
Given a finite extension K/Q and integer m, a norm equation asks for α in O_K satisfying
N_K/Q(α)=m.
More generally one can allow α in K or solve relative norm equations L/K.
The ideal of α must satisfy
N((α))=|m|.
This immediately restricts the prime ideals that can divide (α).
11. A quadratic norm form
In Q(√5) with basis 1,ω and
ω²=ω+1,
the conjugate is
ω'=1−ω.
For
α=a+bω,
the norm is
N(α)=(a+bω)(a+bω') =a²+ab−b².
12. Worked norm equation N(α)=11
Take
a=3, b=1.
Then
N(3+ω)=3²+3·1−1²=11.
So
α=3+ω
is an explicit algebraic integer of norm11.
This matches Guide38’s fact that11 splits in Q(√5): a principal prime ideal of norm11 can be generated by an element of norm ±11 when the corresponding ideal class is principal.
13. Norm equations and ideal factorisation
If
m=±∏p_i^(a_i),
then any α with N(α)=m can involve only prime ideals lying above those p_i.
For each p_i, distribute the required ideal exponents among the primes above p_i in every way compatible with their residue degrees.
This produces candidate principal ideals.
The class group then decides which ideal combinations can actually be principal.
14. Units generate infinite families
If α solves
N(α)=m
and u is a unit of norm1, then
N(uα)=m.
If N(u)=−1, multiplying by u flips the sign of the norm.
Therefore norm-equation solvers often return representatives modulo suitable unit actions rather than an unstructured infinite list.
15. Local norm tests
A global norm must be a norm in every completion.
Thus before a global search, test whether m lies in
N(L_P^×)
at relevant local places.
Valuation congruences and residue-field conditions can reject impossible global norm equations cheaply.
In cyclic extensions, the Hasse norm theorem gives a strong local–global principle, but it should not be applied outside its hypotheses.
16. Thue equations
Let F(X,Y) be an irreducible homogeneous binary form of degree at least3.
A Thue equation is
F(x,y)=m
with x,y integers and m nonzero.
Thue’s theorem states that such an equation has only finitely many integer solutions.
The computational problem is to find all of them and prove completeness.
17. Norm origin of a Thue form
Let θ have irreducible minimal polynomial
f(T)=T^n+c_(n−1)T^(n−1)+...+c0.
Then
N(x−yθ)
is a homogeneous degree-n form in x,y, closely related to
y^n f(x/y).
Thus Thue equations are norm equations with the extra restriction that α has the two-coordinate form x−yθ.
18. Cubic example
Let
θ=∛2, K=Q(θ).
Then
N(x−yθ)=x³−2y³.
The equation
x³−2y³=1
is therefore a Thue equation.
The obvious pair
(x,y)=(1,0)
is a solution. The algorithmic task is not merely to find a solution but to certify the complete finite solution set.
19. Why brute force is not a proof
Searching all |x|,|y|≤10^6 may find many solutions, but it does not prove none exist beyond the search box.
Effective Thue solving requires explicit upper bounds on solution size, followed by reduction techniques that make those bounds small enough for exhaustive completion.
This is where transcendence theory and lattice reduction enter.
20. Logarithmic embeddings of units
For a number field with embeddings σ_i, map a unit u to logarithms of absolute values:
u ↦ (log|σ_1(u)|,...,log|σ_(r1+r2)(u)|)
with complex places weighted appropriately.
The product formula places these vectors in a hyperplane whose coordinate sum is zero.
Fundamental units generate a lattice in that hyperplane. Its covolume is the regulator.
21. S-unit logarithmic lattice
Allowing S-primes adds valuation coordinates
v_P(x) log N(P).
to the logarithmic data.
The S-unit group therefore has an enlarged logarithmic lattice of rank
r1+r2−1+|S|.
This lattice representation is the bridge from multiplicative number-field arithmetic to integer linear algebra.
22. Linear forms in logarithms
Suppose a Diophantine solution implies an expression
u_1^b1 ... u_r^br ≈ c
under one embedding.
Taking logarithms gives a small linear form
b1 log u_1 + ... + br log u_r − log c.
Baker’s theory gives explicit lower bounds for nonzero linear forms in logarithms of algebraic numbers.
Comparing the upper and lower estimates yields an explicit bound on the exponent vector b.
23. The first bound can be enormous
Baker-type estimates are effective but often numerically huge.
A theorem may prove
|b_i| < 10^100
or much larger.
This is a proof of finiteness, but not yet a feasible search plan.
Lattice reduction converts the analytic approximation constraints into a much sharper integer search region.
24. LLL reduction
Construct a lattice whose short vectors correspond to exponent combinations making the logarithmic form unusually small.
Apply LLL to find a reduced basis and derive improved lower bounds on the length of such combinations.
This can shrink exponent bounds by dozens or hundreds of orders of magnitude.
The final remaining search can then be completed exactly.
25. LLL is a reduction tool, not the finiteness theorem
It is important to separate jobs.
Baker theory or arithmetic finiteness theorems establish that only finitely many solutions can occur and provide explicit initial bounds.
LLL improves those bounds computationally.
A lattice reduction alone does not prove that every possible Diophantine solution has been encoded unless the reduction from the original equation has already been justified.
26. p-adic reduction
Archimedean logarithms are not the only source of reduction.
p-adic logarithms and local valuations can produce congruence restrictions on unit exponents.
Combining real and p-adic reductions often cuts the final search dramatically.
Guide39 provides the local-field environment for these computations.
27. Thue–Mahler equations
A Thue–Mahler equation allows the form value to have prime factors only from a prescribed finite set:
F(x,y)=±p_1^z1...p_s^zs.
This is naturally an S-unit problem in the associated number field.
It combines the two central structures of this guide: norm forms and controlled prime support.
28. S-unit equation workflow
A practical solver often follows:
compute maximal order factor relevant rational primes compute class group and unit group compute S-unit generators derive height / exponent bounds apply real and p-adic logarithmic reduction use LLL sieve congruence classes enumerate the final bounded region verify every solution exactly.
Each stage has a mathematical certificate.
29. Norm-equation workflow
For N(α)=m:
factor (m) into prime ideals enumerate compatible ideal exponent patterns use the class group to test principality construct generators of principal candidates multiply by unit representatives apply sign / embedding / integrality restrictions verify norms exactly.
Computer algebra packages compress these steps, but the underlying proof obligations remain.
30. PARI/GP norm solvers
PARI/GP provides routines such as
bnfisintnorm bnfisnorm
for integral and general norm questions in number fields.
Its documentation notes that certification status matters: some class-group/unit data may depend on GRH unless the underlying bnf structure has been certified.
A computational receipt must state whether the result is unconditional or conditional on such assumptions.
31. PARI/GP S-unit tools
PARI/GP provides
bnfsunit / bnfunits
to compute fundamental S-unit data from a number field and a list of prime ideals.
It also supports testing whether an element decomposes in the resulting unit/S-unit basis.
This gives a practical representation of the abstract finitely generated group from the S-unit theorem.
32. PARI/GP Thue solving
PARI/GP provides
thueinit(P) thue(tnf,a)
for equations
P(x/y)y^deg(P)=a.
The documentation describes the output as all integer solutions under the solver’s stated certification conditions.
Initialisation is expensive enough that it should be reused when solving the same form for many right-hand sides.
33. Verification is still elementary at the end
No matter how advanced the search machinery, each returned solution should be checked directly.
For a norm equation:
N(α) ?= m.
For a Thue equation:
F(x,y) ?= m.
For an S-unit decomposition, reconstruct the element from the generator exponents and compare exactly.
34. Proof of completeness needs more than substitution
Direct substitution verifies that listed solutions are genuine.
It does not prove the list is complete.
Completeness depends on the bound derivation, reduction steps, sieving and exhaustive final enumeration—or on a certified library routine whose mathematical assumptions are recorded.
This distinction between witness verification and exhaustive proof is fundamental in computational Diophantine work.
35. Common mistakes
1. Confusing units with S-units. 2. Forgetting the additional |S| rank directions. 3. Treating a norm equation as ordinary integer factorisation only. 4. Ignoring ideal-class obstructions to principality.
5. Calling a bounded brute-force search a proof of completeness. 6. Using LLL without a justified encoding of every solution. 7. Forgetting local obstructions before global search. 8. Reporting software output as unconditional without checking certification assumptions.
36. Practice set
1. Define an S-unit. 2. State the S-unit rank formula. 3. What is the S-unit rank of Q(√5) when S contains the unique prime above2? 4. Give simple generators modulo torsion.
5. Derive N(a+bω). 6. Verify N(3+ω)=11. 7. Explain how prime-ideal factorisation restricts a norm equation. 8. What is a Thue equation?
9. Why is x³−2y³ a norm form? 10. Why is brute force insufficient for completeness? 11. What job does Baker theory perform? 12. What job does LLL perform?
37. Answers
1. An element whose finite valuations vanish outside S. 2. r1+r2−1+|S|. 3. Two. 4. ω and2, together with torsion ±1.
5. (a+bω)(a+bω’)=a²+ab−b². 6. 9+3−1=11. 7. Only primes above rational divisors of m can appear in (α), with norm-compatible exponents. 8. F(x,y)=m for an irreducible homogeneous binary form of degree at least3.
9. It equals N(x−y∛2). 10. It gives no proof that larger solutions do not exist. 11. Explicit exponent/height bounds via lower bounds for linear forms in logarithms. 12. It sharply reduces those bounds using lattice geometry.
Sources and further study
The PARI/GP general number fields catalogue documents integral norm equations, unit decomposition and S-unit routines. The PARI/GP Thue documentation describes thueinit and thue, including certification conditions. Henri Cohen’s computational number-theory texts develop the combination of units, logarithmic forms and lattice reduction used by effective Diophantine solvers.
Computational Number Theory — Batch 10
Guide 37: Integral Bases, Discriminants, Orders and Maximal Orders
Guide 38: Prime-Ideal Decomposition, Ramification, Residue Degrees and Dedekind Factorisation
Guide 39: Local Fields, Completions, p-Adic Extensions and Ramification
Guide 40: S-Units, Norm Equations, Thue Equations and Lattice Reduction