OctoInformBeta

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

Proposition 5.2: A function gg with single-fold graph and δ(log⁡u)2<log⁡g(u)<ulog⁡u\delta(\log u)^2<\log g(u)<u\log u for u≥u0u\ge u_0 makes b≥2,c=bnb\ge 2,\ c=b^n single-fold, through two Pell equations

Exponentiation is single-fold, through a growth function.

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

A single-fold representation of a relation R⊆ℕdR\subseteq\mathbb N^d is a polynomial P(a,w)P(a,w) with integer coefficients in an input tuple a=(a1,…,ad)a=(a_1,\dots,a_d) and finitely many auxiliary variables w=(w1,…,wm)w=(w_1,\dots,w_m) such that, for every a∈ℕda\in\mathbb N^d and all w,w′∈ℕmw,w'\in\mathbb N^m, a∈R⇔P(a,w)=0for somew∈ℕm,P(a,w)=P(a,w′)=0⟹w=w′.a\in R\iff P(a,w)=0\ \text{for some}\ w\in\mathbb N^m, \qquad P(a,w)=P(a,w')=0\implies w=w'.(1) A relation R⊆ℕdR\subseteq\mathbb N^d is single-fold when it has a single-fold representation.

By a theorem of Matiyasevich, every recursively enumerable set has a single-fold exponential Diophantine representation. The relation Pow\mathrm{Pow} is the set of triples (b,n,c)∈ℕ3(b,n,c)\in\mathbb N^3 with b≥2b\ge 2 and c=bnc=b^n. The question is whether Pow\mathrm{Pow} is single-fold, and the route here goes through a function g:ℕ→ℕg\colon\mathbb N\to\mathbb N with a single-fold graph and growth bounded on both sides, and through a system of two Pell equations in nine auxiliaries.

Pell Equations and the System

For a≥2a\ge 2 let D=a2−1D=a^2-1. The solutions in natural numbers of the Pell equation x2−Dy2=1x^2-Dy^2=1 are the pairs (xi(a),yi(a))(x_i(a),y_i(a)), i∈ℕi\in\mathbb N, given by (a+D)i=xi(a)+yi(a)D.(a+\sqrt D)^i=x_i(a)+y_i(a)\sqrt D .(2)

For ℓ,u0∈ℕ\ell,u_0\in\mathbb N, the input value I(b,n,c)I(b,n,c) of a triple (b,n,c)∈ℕ3(b,n,c)\in\mathbb N^3 is the natural number I(b,n,c)=(c+1)ℓ(n+1)(b+1)+u0.I(b,n,c)=(c+1)^\ell(n+1)(b+1)+u_0 .(3)✦

For a function g:ℕ→ℕg\colon\mathbb N\to\mathbb N and the same ℓ\ell and u0u_0, the Pell system for powers Sg,ℓ,u0(b,n,c;w)S_{g,\ell,u_0}(b,n,c;w) is the relation between a triple (b,n,c)∈ℕ3(b,n,c)\in\mathbb N^3 and an auxiliary tuple w=(w0,…,w8)∈ℕ9w=(w_0,\dots,w_8)\in\mathbb N^9 given by the conditions b≥2,w0=I(b,n,c),w1=g(w0),w22−((bw0)2−1)w32=1,w42−(w02−1)w52=1,0<w3<w1,0<w5<w1,w3=n+1+(bw0−1)w6,w5=n+1+(w0−1)w7,w3=cw5+w8,w8<w5.\begin{gathered} b\ge 2,\qquad w_0=I(b,n,c),\qquad w_1=g(w_0),\\ w_2^2-\bigl((bw_0)^2-1\bigr)\,w_3^2=1,\qquad w_4^2-(w_0^2-1)\,w_5^2=1,\\ 0<w_3<w_1,\qquad 0<w_5<w_1,\\ w_3=n+1+(bw_0-1)\,w_6,\qquad w_5=n+1+(w_0-1)\,w_7,\\ w_3=c\,w_5+w_8,\qquad w_8<w_5 . \end{gathered}(4)✦ A solution of Sg,ℓ,u0S_{g,\ell,u_0} for a triple (b,n,c)∈ℕ3(b,n,c)\in\mathbb N^3 is a tuple w∈ℕ9w\in\mathbb N^9 that satisfies the conditions (4).

The Claim

Theorem 1. Let g:ℕ→ℕg\colon\mathbb N\to\mathbb N be a function whose graph {(u,v)∈ℕ2:v=g(u)}\{(u,v)\in\mathbb N^2 : v=g(u)\} is single-fold, let δ>0\delta>0 be a real number and u0≥4u_0\ge 4 a natural number, and write log\log for the natural logarithm. If gg satisfies the growth condition δ(log⁡u)2<log⁡g(u)<ulog⁡ufor every u≥u0,\delta(\log u)^2<\log g(u)<u\log u\qquad\text{for every } u\ge u_0,(5)✦ then Pow\mathrm{Pow} is single-fold. Without any hypothesis, Powis single-fold.\mathrm{Pow}\ \text{is single-fold}.(6)✦

Let gg, δ\delta and u0u_0 be as in (5), and let ℓ∈ℕ\ell\in\mathbb N. If the Pell system Sg,ℓ,u0S_{g,\ell,u_0} has a solution for (b,n,c)(b,n,c), then (b,n,c)∈Pow.(b,n,c)\in\mathrm{Pow}.(7)✦ Any two solutions ww and w′w' of Sg,ℓ,u0S_{g,\ell,u_0} for a triple (b,n,c)(b,n,c) are equal: w=w′.w=w'.(8)✦ If δℓlog⁡2>3\delta\ell\log 2>3 and b≥2b\ge 2, then for every n∈ℕn\in\mathbb N there is w∈ℕ9w\in\mathbb N^9 with Sg,ℓ,u0(b,n,bn;w).S_{g,\ell,u_0}(b,n,b^n;w).(9)✦

For every function gg whose graph is single-fold and all ℓ,u0∈ℕ\ell,u_0\in\mathbb N, the relation on ℕ12\mathbb N^{12} {(b,n,c,w)∈ℕ3×ℕ9:Sg,ℓ,u0(b,n,c;w)}is single-fold.\{(b,n,c,w)\in\mathbb N^3\times\mathbb N^9 : S_{g,\ell,u_0}(b,n,c;w)\}\ \text{is single-fold}.(10)✦

Each real δ>0\delta>0 admits a natural number ℓ≥1\ell\ge 1 with δℓlog⁡2>3.\delta\ell\log 2>3.(11)✦

Every natural number u≥4u\ge 4 satisfies uu<(2u−1)u−1.u^u<(2u-1)^{u-1}.(12)✦ Let uu, aa and nn be natural numbers with u≥4u\ge 4, a≥ua\ge u and n+1<u−1n+1<u-1. If i,q∈ℕi,q\in\mathbb N satisfy yi(a)<uuy_i(a)<u^u and yi(a)=n+1+(a−1)qy_i(a)=n+1+(a-1)q, then i=n+1.i=n+1.(13)✦ Let b≥2b\ge 2, and let n,c,u∈ℕn,c,u\in\mathbb N satisfy u≥(c+1)(n+1)+4u\ge(c+1)(n+1)+4. If cc is the integer quotient of yn+1(bu)y_{n+1}(bu) by yn+1(u)y_{n+1}(u), then c=bn.c=b^n.(14)✦

What Is Checked

The claims are stated over the single-fold representations of (1), the relation Pow\mathrm{Pow}, the graph of an arbitrary function g:ℕ→ℕg\colon\mathbb N\to\mathbb N with its growth condition (5), the Pell values yi(a)y_i(a) of (2), and the Pell system (4) with its input value (3).