OctoInformBeta

OpenAI preprint, September 2026 · §4. A uniquely represented function with intermediate growth

Proposition 4.2: A function gg with δ(log⁡u)2<log⁡g(u)<ulog⁡u\delta(\log u)^2<\log g(u)<u\log u for some δ>0\delta>0 and large uu, built from heights of points on an elliptic curve

A function with a single-fold graph and intermediate growth.

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∈ℕda \in \mathbb{N}^d and an auxiliary tuple w∈ℕkw \in \mathbb{N}^k for some kk, such that for all a∈ℕda \in \mathbb{N}^d and w,w′∈ℕkw, w' \in \mathbb{N}^k a∈R⇔∃z∈ℕkP(a,z)=0,P(a,w)=P(a,w′)=0⟹w=w′.a \in R \iff \exists\, z \in \mathbb{N}^k\ P(a,z) = 0, \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. A function g:ℕ→ℕg\colon \mathbb{N} \to \mathbb{N} has a single-fold graph when the relation {(u,v)∈ℕ2:v=g(u)}\{(u,v) \in \mathbb{N}^2 : v = g(u)\} is single-fold.

A polynomial map p:ℕ→ℕp\colon \mathbb{N} \to \mathbb{N} with integer coefficients has a single-fold graph, represented by v−p(u)v - p(u) with no auxiliary variable. Can a function with a single-fold graph outgrow every polynomial, and by how much?

The library answers with a function read off heights of rational points on an elliptic curve, and states the steps of that construction, on the curve and for integer sequences in general, as claims of their own.

Heights on the Curve

The curve is E:y2=x3−25xE\colon y^2 = x^3 - 25x over ℚ\mathbb{Q}, with point at infinity OO and group of rational points E(ℚ)E(\mathbb{Q}); an affine point QQ has coordinates x(Q)x(Q) and y(Q)y(Q). Fix an isomorphism ff of E(ℚ)E(\mathbb{Q}) onto ℤ×T\mathbb{Z} \times T, with TT a finite group. It gives the splitting E(ℚ)=ℤP⊕TE(\mathbb{Q}) = \mathbb{Z}P \oplus T, where P=f−1(1,0)P = f^{-1}(1,0) is a point of infinite order, and every rational point is Q=nP+t=f−1(n,t)Q = nP + t = f^{-1}(n,t) with n∈ℤn \in \mathbb{Z} and t∈Tt \in T. The integer n(Q)=nn(Q) = n is the index of QQ.✦

The height of a rational number a/da/d in lowest terms with d≥1d \geq 1 is H(a/d)=max⁡(|a|,d)H(a/d) = \max(|a|, d). The height of a rational point QQ of EE is the natural number Hx(O)=1,Hx(Q)=H(x(Q))(Q≠O).H_x(O) = 1, \qquad H_x(Q) = H(x(Q)) \quad (Q \neq O).(2)✦ For a natural number m*m_*, write [m*]Q[m_*]Q for the m*m_*-fold multiple of a rational point QQ of EE; the multiple height W(Q)W(Q) of QQ and the growth sequence (Wj)j∈ℕ(W_j)_{j \in \mathbb{N}} of natural numbers are W(Q)=Hx([m*]Q),Wj=W(jP)(j∈ℕ).W(Q) = H_x([m_*]Q), \qquad W_j = W(jP) \quad (j \in \mathbb{N}).(3)

A representative point is a rational point QQ of EE such that Q≠O,y(Q)≥0,W(Q)>1,andQ+t≠O,x(Q+t)≤x(Q)for every t∈T.Q \neq O, \quad y(Q) \geq 0, \quad W(Q) > 1, \quad\text{and}\quad Q + t \neq O,\ x(Q+t) \leq x(Q) \ \text{for every } t \in T.(4)✦

Brackets, Windows and Growth Pairs

Write M(Q)=max⁡{W(Q+P),W(Q−P)}M(Q) = \max\{W(Q+P), W(Q-P)\} for a rational point QQ. A rational point QQ is bracketed at u∈ℕu \in \mathbb{N} when W(Q)≤u+W(P)<M(Q).W(Q) \leq u + W(P) < M(Q).(5)✦ For κ∈ℕ\kappa \in \mathbb{N}, a pair (Q,R)(Q,R) of rational points lies in the window of κ\kappa when W(2Q)W(R)W(P)≤κW(Q)2M(R)andW(Q)2M(R)≤κW(2Q)W(R)W(P).W(2Q)\,W(R)\,W(P) \leq \kappa\, W(Q)^2 M(R) \quad\text{and}\quad W(Q)^2 M(R) \leq \kappa\, W(2Q)\,W(R)\,W(P).(6)✦ A growth pair at uu for κ\kappa is a pair (Q,R)(Q,R) of representative points such that QQ is bracketed at uu and (Q,R)(Q,R) lies in the window of κ\kappa.✦

Let aa and cc be real numbers, let (Wj)j∈ℕ(W_j)_{j \in \mathbb{N}} be a sequence of natural numbers, such as the growth sequence, and let κ\kappa be a natural number. The sequence satisfies the logarithmic bound with constants aa and cc when the first display holds, and κ\kappa is admissible for aa and cc when the second holds: c≥0,|log⁡Wj−aj2|≤c(j≥1),c \geq 0, \qquad |\log W_j - a j^2| \leq c \quad (j \geq 1),(7) κ>0,6c<log⁡κ<2a−6c.\kappa > 0, \qquad 6c < \log \kappa < 2a - 6c.(8)

The Claim

Theorem 1. There are a function g:ℕ→ℕg\colon \mathbb{N} \to \mathbb{N}, a real number δ>0\delta > 0 and a natural number u0≥4u_0 \geq 4 such that {(u,v)∈ℕ2:v=g(u)} is single-fold,δ(log⁡u)2<log⁡g(u)<ulog⁡u(u≥u0).\{(u,v) \in \mathbb{N}^2 : v = g(u)\} \text{ is single-fold}, \qquad \delta (\log u)^2 < \log g(u) < u \log u \quad (u \geq u_0).(9)✦

Theorem 2. Let E(ℚ)=ℤP⊕TE(\mathbb{Q}) = \mathbb{Z}P \oplus T be the fixed splitting, with TT finite. There are an even m*>0m_* > 0, an integer κ>0\kappa > 0, a function g:ℕ→ℕg\colon \mathbb{N} \to \mathbb{N}, a real number δ>0\delta > 0 and u0≥4u_0 \geq 4 such that for every u∈ℕu \in \mathbb{N} there is exactly one growth pair at uu for κ\kappa, and for all u,v∈ℕu, v \in \mathbb{N} v=g(u)⇔v=W(R) for a growth pair (Q,R) at u,δ(log⁡u)2<log⁡g(u)<ulog⁡u(u≥u0).v = g(u) \iff v = W(R) \text{ for a growth pair } (Q,R) \text{ at } u, \qquad \delta (\log u)^2 < \log g(u) < u \log u \quad (u \geq u_0).(10)✦ For any m*m_* and κ\kappa such that for every u∈ℕu \in \mathbb{N} there is exactly one growth pair at uu for κ\kappa, {(u,v)∈ℕ2:v=W(R) for a growth pair (Q,R) at u for κ} is single-fold.\{(u,v) \in \mathbb{N}^2 : v = W(R) \text{ for a growth pair } (Q,R) \text{ at } u \text{ for } \kappa\} \text{ is single-fold}.(11)✦ Let m*m_* be even and the growth sequence strictly increasing. For every u∈ℕu \in \mathbb{N} and every rational point QQ, Q is bracketed at u⇔W|n(Q)|≤u+W1<W|n(Q)|+1.Q \text{ is bracketed at } u \iff W_{|n(Q)|} \leq u + W_1 < W_{|n(Q)|+1}.(12)✦ If moreover the growth sequence satisfies (7) and κ\kappa satisfies (8), then for all representative points QQ and RR (Q,R) lies in the window of κ⇔|n(R)|=|n(Q)|2,(Q,R) \text{ lies in the window of } \kappa \iff |n(R)| = |n(Q)|^2,(13)✦ and if the growth sequence is also unbounded, then for every u∈ℕu \in \mathbb{N} #{(Q,R)∈E(ℚ)2:(Q,R) is a growth pair at u for κ}=1.\#\{(Q,R) \in E(\mathbb{Q})^2 : (Q,R) \text{ is a growth pair at } u \text{ for } \kappa\} = 1.(14)✦

Theorem 3. Let (Wj)j∈ℕ(W_j)_{j \in \mathbb{N}} be a sequence of natural numbers. If it is strictly increasing and unbounded, then for every u∈ℕu \in \mathbb{N} #{k≥1:Wk≤u+W1<Wk+1}=1.\#\{k \geq 1 : W_k \leq u + W_1 < W_{k+1}\} = 1.(15)✦ Suppose now, in place of monotonicity, that every WjW_j is positive and that (Wj)(W_j) satisfies (7). If κ\kappa satisfies (8), then for all integers k,r≥1k, r \geq 1 (W2kWrW1≤κWk2Wr+1 and Wk2Wr+1≤κW2kWrW1)⇔r=k2.\bigl(W_{2k} W_r W_1 \leq \kappa W_k^2 W_{r+1} \text{ and } W_k^2 W_{r+1} \leq \kappa W_{2k} W_r W_1\bigr) \iff r = k^2.(16)✦ If a>0a > 0, there is u0≥4u_0 \geq 4 such that for every u≥u0u \geq u_0 and every k≥1k \geq 1 with Wk≤u+W1<Wk+1W_k \leq u + W_1 < W_{k+1} (log⁡u)2128a<log⁡Wk2<ulog⁡u.\frac{(\log u)^2}{128a} < \log W_{k^2} < u \log u.(17)✦

What Is Checked

The claims are stated over single-fold relations as in (1); the curve EE, its splitting E(ℚ)=ℤP⊕TE(\mathbb{Q}) = \mathbb{Z}P \oplus T with TT finite, and the index and coordinates of its points; the heights of (2) and (3); representative points, brackets, windows and growth pairs; and sequences of natural numbers under (7) and (8).