Computation — flashcards

For positive integers a and b, the remainder sequence is strictly decreasing and non-negative, so it reaches zero after finitely many steps.

For integers a, b there exist integers x, y with ax + by = gcd(a, b). The extended Euclidean algorithm computes them.

The number of division steps in the Euclidean algorithm is at most five times the number of decimal digits of the smaller argument; the worst case is consecutive Fibonacci numbers.

Anthyphairesis on a 1 by √2 rectangle never terminates, which is exactly the statement that √2 is not a ratio of integers.

If f(a) ≡ 0 mod p and f'(a) ≢ 0 mod p, then f has a unique p-adic root congruent to a. It is Newton's method with the ultrametric inequality doing the work that real-analytic estimates do over ℝ.

The sum of the kth powers of the first n integers is a polynomial in n of degree k+1 whose coefficients are the Bernoulli numbers. The defining system is lower triangular and dense: each Bernoulli number depends on every earlier one.

The finite-difference argument that produces a polynomial for positive powers fails for negative ones, because the falling factorials no longer span. The discrete and continuous cases fail for different reasons, which is why the harmonic numbers have an asymptotic expansion but no closed form.

A sign-reversing pairing on partitions that cancels almost every term, leaving the pentagonal number theorem's sparse recurrence. The general principle: a recurrence needing little memory is not an easier problem, it is a harder theorem — the near-total cancellation has to be proved.

Franklin's involution (st/franklin-involution) is a ℤ/2 action on partitions into distinct parts that pairs almost everything freely; its isolated fixed points, at exactly the generalized pentagonal n, are mechanistically identified with the Lefschetz fixed point theorem and Duistermaat–Heckman/Atiyah–Bott localization — a signed sum over a space with a group action reducing to a sum over the fixed locus. This is contrasted, via orbit–stabilizer language, with spontaneous symmetry breaking in physics: a broken vacuum has a reduced stabilizer relative to the full symmetry group, the opposite of Franklin's fixed points, which have full stabilizer (the ℤ/2 action fixes them entirely, rather than moving them to a smaller-symmetry orbit). Goldstone's theorem (every broken continuous symmetry generates a massless mode) is named as physics's standard consequence of the reduced-stabilizer picture, not proved here.

Subbarao's observation that Franklin's involution preserves partition perimeter (λ₁+ℓ(λ)−1) was used to show Franklin's fixed points are exactly the unique perimeter-minimizing partitions into distinct parts — verified for every generalized pentagonal n≤35 — collapsing 'algebraic cancellation' and 'energetic minimization' (st/selection-mechanism-refuted-and-replaced's first and second mechanisms) into one mechanism for this specific case, contradicting the three-way independence claimed there. This collapse was then tested against a second, independently-known Franklin-type involution — Chen and Liu's involution on partitions into distinct parts with odd smallest part, whose fixed points sit at n=k² — by checking five candidate functionals (perimeter, largest part, number of parts, λ₁−ℓ, smallest part) for n≤25; none singles out the squares, with explicit mismatch counts reported for each. The collapse is therefore restricted to the classical Franklin case, not generalized into a new principle: the three-mechanism picture from st/selection-mechanism-refuted-and-replaced is restored, with the explicit caveat that the mechanisms can coincide on particular objects without being identical in general.

Power sums and elementary symmetric polynomials determine each other by a triangular system. This is how information moves between a polynomial's roots and its coefficients without any root ever being computed.

The sum of a function over a lattice equals the sum of its Fourier transform over the dual lattice. It is the bridge back from harmonic analysis to the Bernoulli and zeta material, and the reason the functional equation of ζ looks like a symmetry rather than a coincidence.

If |f(a)|_p < |f′(a)|_p² then f has a unique root α with |α − a|_p < |f′(a)|_p. Dropping the requirement that a be a simple root mod p is what makes the lemma usable in practice.

The freezing transition (st/freezing-transition-log-correlated-extremes) produces Gumbel-distributed extreme-value statistics; the Gumbel distribution's skewness constant, 12√6·ζ(3)/π³, was derived here from first principles rather than looked up, by identifying the Gumbel distribution's moment generating function as literally Γ(1−t) — so its cumulant generating function is the same log-Gamma Taylor series whose coefficients are zeta values at integers. This ties Apéry's constant ζ(3)'s appearance in the freezing transition's maximum-value statistics directly to the digamma/zeta coefficient identity already established for the completed zeta function's log-derivative (st/xi-log-derivative-local-global-split).

Euclid, c. 300 BC.

Claude Bachet, then Étienne Bézout, 1624 (Bachet), 1779 (Bézout).

Gabriel Lamé, 1844.

the Pythagorean school, c. 450 BC.

Kurt Hensel, 1897.

Leonhard Euler, 1735.

Leonhard Euler, 1735.

Fabian Franklin, 1881.

Isaac Newton, c. 1666, published 1707.

Siméon Denis Poisson, 1823.

Hasse, Schnirelmann, Teichmüller and others, 1920s–1930s.

Nat.gcd_eq_gcd_ab — Mathlib.Data.Int.GCD

irrational_sqrt_two — Mathlib.NumberTheory.Real.Irrational

hensels_lemma — Mathlib.NumberTheory.Padics.Hensel

The continued fraction of x is the quotient sequence of the Euclidean algorithm run on x. Identical work; the CF keeps only the quotients and discards the remainders, which is exactly where the magnitude information lived.

Every Bernoulli number depends on all the earlier ones: the defining system is lower triangular and dense. This is the worst case, and it is the baseline the sparse recurrences get compared against.

The partition recurrence needs only a handful of earlier terms, and the reason is Franklin's involution: almost everything cancels in pairs. Sparse memory is not a lighter problem, it is a heavier theorem — the cancellation has to be proved.

A generating function carries an entire sequence in a single expression; which coefficients you can cheaply extract is a statement about how much of the sequence you needed to store to begin with.

Power sums are the symmetric functions you get by fixing a particular basis. Newton's identities convert between the choices, which is what makes the choice visible as a choice.

Sequences ↔ elements of a power series ring; convolution of sequences ↔ multiplication. Counting arguments become ring computations.

An apparent fork that collapsed. Letting the root vary at each stage looks like a new family, but every canonical version is continued fractions conjugated by a logarithm — and the base of that logarithm turns out to be irrelevant, even numerically. Testing whether a fork is real is half the work of this lens.

Recorded as apparent: the resemblance is real, the mechanism is not shared.

The same reframe applied to a different object, and it inverts: a nested radical is a backward orbit. Running the two at once gives the natural extension — an interval crossed with a Cantor set.

From below, succession is an axiom and addition is defined from it. From above, addition is one rung of the hyperoperation ladder and the Peano axioms read as theorems about the bottom of it. Same content, opposite direction of justification.

Euclid's algorithm consumes a pair and reduces it; the continued fraction it produces generates approximations outward. The same recursion read as destruction or as construction depending on which end you stand at.

Moving the recursion up one hyperoperation level buys expressive power and costs base-independence — the property that made continued fractions worth having.

Nested radicals do have a series dual by difference-of-squares telescoping, but it is all-positive. Without alternation the approximations no longer straddle the target, and optimality goes.

Tested directly: nested radicals do have a series dual, via difference-of-squares telescoping, echoing continued fractions' own series representation. The pairing is real, but it isn't the same shape — it comes out all-positive rather than alternating, which is exactly what breaks optimality for nested radicals. A confirmed analogy that differs in a load-bearing way from the thing it was tested against.

Partial. No direct interpretation the way binomial coefficients count something outright, but one step removed — through the Genocchi and zigzag numbers, both of which do have direct combinatorial meanings. A correspondence that holds once you're willing to go via an intermediate object.

Recorded as conjectural: expected, not proved.

Held, and closed a loop rather than opening a new one: Poisson summation is the bridge back from Fourier analysis to the Bernoulli/zeta material, and it's the reason the functional equation of ζ looks like a symmetry instead of a coincidence.

`Mathlib.NumberTheory.Padics.PadicVal.Basic` imports `Mathlib.NumberTheory.Divisors`. Read off Mathlib/NumberTheory/Padics/PadicVal/Basic.html. No human asserted this edge.

`Mathlib.Data.Int.GCD` imports `Mathlib.Algebra.Divisibility.Basic`, `Mathlib.Algebra.GroupWithZero.Semiconj`, `Mathlib.Algebra.GroupWithZero.Divisibility`, `Mathlib.Algebra.GroupWithZero.Nat`. Read off Mathlib/Data/Int/GCD.html. No human asserted this edge.

`Mathlib.Data.Int.GCD` imports `Mathlib.Algebra.Group.Commute.Units`, `Mathlib.Algebra.Group.Int.Defs`, `Mathlib.Algebra.Group.Nat.Defs`, `Mathlib.Algebra.Group.Nat.Units`. Read off Mathlib/Data/Int/GCD.html. No human asserted this edge.

Repeated division to find the gcd of two numbers — the oldest algorithm still in everyday use.

x² − ny² = 1, solved via continued fractions. The classical entry point where number theory starts reaching into algebra, and where continued fractions stop being a curiosity.

Encoding a whole sequence as the coefficients of one formal power series, so counting becomes algebra.

The same recursion one hyperoperation up: roots inside roots rather than divisions inside divisions. Gains a level, loses base-independence.

Succession, addition, multiplication, exponentiation, tetration — each level iterating the one below. Cross-confirmed: this ladder appears in both transcripts as a place to move up and down.

The coefficients that turn a sum of kth powers into a polynomial in n. The defining system is lower triangular and dense — every Bernoulli number depends on all the earlier ones — which makes them the standard against which sparser recurrences get measured.