OctoInformBeta

OpenAI preprint, September 2026 · §5. A power graph from a growth function

Lemma 5.1: For a≥2a \ge 2, (2a−1)n≤yn+1(a)≤(2a)n(2a-1)^n \le y_{n+1}(a) \le (2a)^n and yn+1(a)≡n+1(mod⁡a−1)y_{n+1}(a) \equiv n+1 \pmod{a-1}; for b,u≥2b, u \ge 2, yn+1(bu)/yn+1(u)y_{n+1}(bu)/y_{n+1}(u) lies between bnb^n and bn(1+1/(2u−1))nb^n(1+1/(2u-1))^n

Pell terms grow between two geometric rates.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The negative answer to Hilbert’s tenth problem turns on exponentiation. By the Davis-Putnam-Robinson theorem every recursively enumerable relation is exponential Diophantine, so a Diophantine representation of the power relation Pow(b,n,c)\mathrm{Pow}(b, n, c), which holds when b≥2b \ge 2 and c=bnc = b^n, yields one for every recursively enumerable relation.

The classical route to Pow\mathrm{Pow} runs through the Pell equation x2−(a2−1)y2=1x^2 - (a^2 - 1)y^2 = 1 with a≥2a \ge 2, whose solutions grow exponentially at a rate set by aa. A construction of c=bnc = b^n from them needs that rate in explicit bounds, for one parameter aa and for the two parameters bubu and uu set against each other, together with a congruence modulo a−1a - 1 that ties each solution to its place in the sequence. In a single-fold representation the quotient of that congruence is an auxiliary unknown, and it must be unique.

The Pell Sequences

Let a≥2a \ge 2 be a natural number and put D=a2−1D = a^2 - 1. The Pell sequences (xi(a))i∈ℕ(x_i(a))_{i \in \mathbb{N}} and (yi(a))i∈ℕ(y_i(a))_{i \in \mathbb{N}} of aa are the sequences of natural numbers given by (a+D)i=xi(a)+yi(a)D(i∈ℕ).(a + \sqrt{D})^i = x_i(a) + y_i(a)\sqrt{D} \qquad (i \in \mathbb{N}).(1)

The Claim

Theorem 1. Let a≥2a \ge 2 and nn be natural numbers. Then yi(a)>0for every i≥1,y_i(a) > 0 \quad \text{for every } i \ge 1,(2)✦ (2a−1)yn+1(a)≤yn+2(a)≤2ayn+1(a),(2a - 1)\, y_{n+1}(a) \le y_{n+2}(a) \le 2a\, y_{n+1}(a),(3)✦ (2a−1)n≤yn+1(a)≤(2a)n,(2a - 1)^n \le y_{n+1}(a) \le (2a)^n,(4)✦ and there is exactly one natural number qq with yn+1(a)=n+1+(a−1)q.y_{n+1}(a) = n + 1 + (a - 1)q.(5)✦ If moreover b≥2b \ge 2 and u≥2u \ge 2 are natural numbers, then bn≤yn+1(bu)yn+1(u)≤bn(1+12u−1)n.b^n \le \frac{y_{n+1}(bu)}{y_{n+1}(u)} \le b^n \Bigl(1 + \frac{1}{2u - 1}\Bigr)^n.(6)✦

In the paper, the result reads: for an integer a≥2a \ge 2, every positive solution of x2−Dy2=1x^2 - Dy^2 = 1 is (xi(a),yi(a))(x_i(a), y_i(a)) for exactly one i≥1i \ge 1; yi(a)≡i(mod⁡a−1)y_i(a) \equiv i \pmod{a - 1} and (2a−1)i−1≤yi(a)≤(2a)i−1(2a - 1)^{i-1} \le y_i(a) \le (2a)^{i-1} for i≥1i \ge 1; and for b,u≥2b, u \ge 2 and n≥0n \ge 0, bn≤yn+1(bu)/yn+1(u)≤bn(1+1/(2u−1))nb^n \le y_{n+1}(bu)/y_{n+1}(u) \le b^n(1 + 1/(2u - 1))^n.

What Is Checked

The claim is stated over the Pell sequence yi(a)y_i(a) of (1), taken at the parameters aa, uu and bubu for natural numbers a≥2a \ge 2, b≥2b \ge 2, u≥2u \ge 2 and an index n∈ℕn \in \mathbb{N}.