Testing Transformer Learnability on the Arithmetic Sequence of Rooted Trees

Abstract

We study whether a transformer network can learn the deterministic sequence of trees generated by the iterated prime factorization of the natural numbers. Each integer is mapped into a rooted planar tree and the resulting sequence $\mathbb{N}\mathcal{T}$ defines an arithmetic text with measurable statistical structure. A transformer network (the GPT-2 architecture) is trained from scratch on the first $10^{11}$ elements and evaluated on Next-Token and masked-word prediction tasks, with a Hidden Markov Model as baseline and a scaling analysis over context window, dataset size, vocabulary size and model size. The model reaches a word accuracy of about $0.4$, well above the baseline, and its performance remains stable on test blocks located at $10^{13}$--$10^{15}$, far beyond the training interval. Moreover, the likelihood assigned by the model separates the arithmetic text from two controls: synthetic sequences reproducing its word frequencies exactly but carrying no sequential organization, with a separation that widens as the evaluated context grows; and sequences containing more than three consecutive square-free integers, a configuration that arithmetic forbids. These results indicate that the transformer captures regularities of the arithmetic text that go beyond its frequency profile.

33 pages, 15 figures