Binary Quadratic Forms
Summary: A binary quadratic form is a homogeneous degree-2 polynomial in two integer variables. Lagrange’s Additions Chapter II shows that the minimum of over positive integer is computed by a periodic recursion on auxiliary integers , derived from the continued-fraction expansion of one root of .
Sources: additions-2, additions-7, additions-9
Last updated: 2026-05-10
Definition
A binary quadratic form with integer coefficients is
Its discriminant is . The associated single-variable equation has roots
The form factors over (or ) as
Minimum of Over Positive Integers (Add. II, Art. 31)
Three regimes by the sign and shape of :
| Regime | Roots | Behavior | |
|---|---|---|---|
| Degenerate | square | rational | achievable |
| Definite | imaginary conjugates | minimum positive | |
| Indefinite | , non-square | real irrational conjugates | minimum may be negative |
In the degenerate case, choosing equal to a rational root makes , so there is no positive minimum. In the other two cases, the integer-coefficient assumption forces , and Lagrange’s algorithm finds the actual minimum value.
Definite Case () (Add. II, Art. 32)
The roots are imaginary, conjugate: , . Their common real part is .
Since both summands, minimizing amounts to minimizing , which by Lagrange’s theorem is achieved at the principal convergents of .
Algorithm:
- Compute the continued fraction of .
- List its principal convergents .
- Evaluate for each; the smallest value is the minimum.
Worked example (Art. 32): For , . Convergents and form values:
| 1 | 0 | 49 |
| 2 | 1 | 10 |
| 5 | 2 | 5 |
| 17 | 7 | 49 |
Minimum is 5 at .
Indefinite Case (, non-square) (Add. II, Art. 33)
Let . The roots are real irrational:
Pick one root, say , and let be its CF partial quotients. The auxiliary sequences
P^0 &= A, & Q^0 &= \tfrac{1}{2}B,\\ P' &= A\mu^2 + B\mu + C, & Q' &= A\mu + \tfrac12 B,\\ P^{k+1} &= \mu^{k\,2}\, P^k + 2\mu^k\, Q^k + P^{k-1}, & Q^{k+1} &= \mu^k P^k + Q^k,\\ &\ \ \vdots & &\ \ \vdots \end{aligned}$$ obey the **fundamental identity** $$Q^{k\,2} - P^{k-1} P^k = \tfrac{1}{4}E.$$ Each $|P^k|$ is a candidate for the minimum, and the corresponding $(p, q)$ is given by $$P^k = F(p^k, q^k)$$ where $p^k/q^k$ are the [[convergents]] of $a$. **Sign rule for $\mu^k$**: $\mu^k$ is the largest integer below $$\frac{-Q^k \pm \tfrac{1}{2}\sqrt{E}}{P^k}, \quad \text{sign alternating with } k.$$ **Worked example** (Art. 40): For $9p^2 - 118pq + 378q^2$, $E = 316$, $\sqrt{E}/2 = \sqrt{79}$. The two roots produce two periodic $(P^k, Q^k, \mu^k)$ orbits. In the first ($a = (59+\sqrt{79})/9$): | $k$ | $P^k$ | $Q^k$ | $\mu^k$ | |----:|------:|------:|--------:| | 0 | 9 | −59 | 7 | | 1 | −7 | 4 | 1 | | 2 | 10 | −3 | 1 | | 3 | **−3** | 7 | 5 | | 4 | 5 | −8 | 3 | | 5 | −6 | 7 | 2 | | 6 | 9 | −5 | 1 | | 7 | −7 | 4 | (period closes) | Minimum $P^k = -3$ at $k = 3$, giving $(p, q) = (15, 2)$. The second case (sign $-\sqrt{79}$) reaches $P^{iv} = -3$ at $(p, q) = (39, 7)$. **Overall minimum**: $-3$. --- ## Why Periodicity Matters The $(P^k, Q^k)$ orbit lives in the bounded region $$|P^k| \le E, \quad |Q^k| \le \sqrt{E},$$ an integer lattice with finitely many points. The orbit must therefore revisit a point, after which the entire continuation repeats. See [[periodicity-quadratic-irrationals]] for the precise theorem and bounds. This means every binary quadratic form with positive non-square discriminant has a *finite* algorithm for finding its minimum — the orbit is run until a repetition is detected, and the smallest $|P^k|$ in one period is the answer. --- ## Connection to the Pell Equation The form $F(p, q) = p^2 - Kq^2$ ($K$ non-square positive integer) has $A=1, B=0, C=-K$, so $E = 4K$, $\sqrt{E}/2 = \sqrt{K}$. Its $(P^k, Q^k)$ orbit is exactly the orbit one obtains while computing the CF of $\sqrt{K}$. - **Existence of Pell solutions** (Add. II, Art. 37): Periodicity of the orbit forces $P^{2\rho} = P^0 = 1$ to recur, giving $p^{2\rho\,2} - K q^{2\rho\,2} = 1$. See [[pell-equation]]. - **All small-residue solutions are convergents** (Add. II, Art. 38): If $p^2 - Kq^2 = \pm H$ with $H < \sqrt{K}$, then $p/q$ is necessarily a principal convergent of $\sqrt{K}$. --- ## Reduction of Higher-Degree Forms (Add. II, Art. 28) A homogeneous polynomial $Ap^m + Bp^{m-1}q + \cdots + Vq^m$ factors as a product of linear and quadratic terms via the roots of $A\kappa^m + \cdots + V = 0$. Each linear factor is minimized via the CF of a real root; each quadratic factor is a binary quadratic form treated by the algorithm above. So the present case is the *building block* for all homogeneous binary minimization problems. --- ## Solving $F(p, q) = N$ in Integers (Add. VII) For the form $F = p^2 - Aq^2$ with arbitrary integer right side $N = B$, Lagrange's Additions Chapter VII (see [[add7-integer-quadratic-method]]) gives a complete decision procedure: 1. Reduce to $B$ square-free; assume $q$ prime to $B$. 2. Substitute $p = nq - Bz$ with $n$ chosen so $B \mid n^2 - A$ and $|n| \le B/2$. 3. Get the auxiliary $Cq^2 - 2nqz + Bz^2 = 1$ where $C = (n^2 - A)/B$. 4. Solve the auxiliary by the [[lagrange-reduction-algorithm]] (Art. 70) — succeed in finite time, or certify no integer solution exists. 5. Once one solution $(p_0, q_0)$ is known, generate all others by composition with Pell solutions (Art. 75). Three worked examples treat $\sqrt{30 + 62s - 7s^2}$, $\sqrt{13y^2 + 101}$ (infinite family), and $\sqrt{79y^2 + 101}$ (no solution — disproving Euler's induction rule). --- ## Multiplicative Composition (Add. IX) The form $F(p, q) = p^2 + apq + bq^2$ is a [[norm-forms|norm form]]: it equals the product $(p + \alpha q)(p + \beta q)$ over the roots of $s^2 - as + b = 0$. The composition law (Add. IX, Art. 89) is $$F(p, q) \cdot F(p', q') = F(P, Q),\quad P = pp' - bqq',\ Q = pq' + qp' + aqq'.$$ With $a = 0$ this reduces to the [[brahmagupta-fibonacci-identity]]. With $a = 0, b = -A$ this is the Pell composition $F(P, Q) = (p^2 - Aq^2)(p'^2 - Aq'^2) = (pp' + Aqq')^2 - A(pq' + p'q)^2$. See [[composition-of-forms]]. The squaring law (Art. 90): $F(p, q)^2 = F(p^2 - bq^2,\ 2pq + aq^2)$. The general $m$-th power is given by a Newton-binomial expansion using the recurrence $\alpha^k = A^{(k)}\alpha - B^{(k)}$. --- ## Historical Notes - The factorization $F(p, q) = A(p - aq)(p - bq)$ over $\mathbb{R}$ or $\mathbb{C}$ goes back to Brahmagupta and the *Bhāvanā* composition law (cf. [[brahmagupta-fibonacci-identity]]). - Fermat asked which forms represent which integers, and proved several special cases (e.g. primes $\equiv 1 \pmod 4$ are sums of two squares: see [[sums-of-two-squares]]). - Lagrange's *Additions* and contemporaneous *Mémoires de Berlin* 1768 are the first systematic treatment. - Gauss's *Disquisitiones Arithmeticae* (1801) elevated this to a full theory of equivalence classes and genera. --- ## Related pages - [[add2-arithmetic-problems]] — chapter overview - [[periodicity-quadratic-irrationals]] — periodicity theorem driving the algorithm - [[continued-fractions]] — CF machinery - [[convergents]] — convergent recurrences - [[best-rational-approximations]] — convergents minimize $|p - aq|$ - [[pell-equation]] — special case $A=1, C=-K$ - [[discriminant]] — sign of $B^2 - 4AC$ governs root type - [[ch1.4.9-nature-quadratic-equations]] — Vieta's formulas for the roots - [[brahmagupta-fibonacci-identity]] — composition law for the form $x^2 + cy^2$ - [[sums-of-two-squares]] — historical special case ($A=C=1, B=0$) - [[norm-forms]] — Lagrange's general norm-form construction - [[composition-of-forms]] — composition law in any degree - [[add7-integer-quadratic-method]] — full decision procedure for $p^2 - Aq^2 = B$ - [[add9-norm-forms-composition]] — multiplicative closure of forms - [[lagrange-reduction-algorithm]]