Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 3 results · all verified · 1 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Attention, transformer universality, and sequence limits — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck pendingOpen item page →

Position-free versus position-encoded token order

Example

Assume the Axiom of Countable Choice. Let $X = (x_{1}, x_{2}) \in [0, 1]^{1 \times 2}$ and define the constant ordered-output map $f (X) = (0, 1)$ . A position-free unmasked self-attention stack followed by shared tokenwise maps must permute its two output entries when the two input tokens are exchanged, whereas a trainable positional matrix can distinguish the first and second token positions. On the compact square $[0, 1]^{2}$ , the position-encoded fixed-length theorem therefore approximates $f$ in integrated $L_{p}$ error for every $1 \leq p < \infty$ .

Example references

Yun et al., Appendix A: permutation equivariance without positional encoding

Yun et al., Theorem 3: trainable positional encodings on a compact domain

The Axiom of Countable Choice ( ${A C}_{ω}$ ): the inherited premise for the local integrated-Lebesgue approximation theorem.

Facts & Assumptions

Given: Countable Choice, the two-token input $X$ , the coordinate-swap permutation $P$ , the constant map $f$ , and position-free or position-encoded Transformer stacks as in the Example.

[F1]

The row-token theorem gives $R (P Z) = P R (Z)$ . In the column-token convention used here, define $T (X) = R (X^{T})^{T}$ ; transposition gives $T (X P) = T (X) P$ for every unmasked position-free stack with shared tokenwise maps (Position-free unmasked self-attention is permutation equivariant).

[F2]

Assuming Countable Choice, for fixed $n \geq 2$ , $d \geq 1$ , and $1 \leq p < \infty$ , a two-head, head-size-one Transformer with width-four ReLU feedforward layers, no layer normalization, and a trainable positional matrix approximates every continuous map on a compact domain in integrated $L_{p}$ error, for $1 \leq p < \infty$ (Fixed-width Transformer approximation on compact domains).

Proof

1.1givenF1algebra

Let $P$ swap the two columns. Since $f$ is constant, $f (X P) = (0, 1)$ , while $f (X) P = (1, 0)$ . Hence $f (X P) \neq f (X) P$ , so $f$ is not permutation equivariant. By [F1], no position-free stack can equal $f$ on both $X$ and $X P$ .

2.1givenF2∎

The map $f$ is continuous on $K = [0, 1]^{1 \times 2}$ , which is compact, and $n = 2, d = 1$ meet the size hypotheses. Under the assumed Countable Choice, the position-encoded compact-domain branch of [F2] with any prescribed $ε > 0$ gives a position-encoded stack whose integrated $L_{p}$ error from $f$ is less than $ε$ . Thus positional tags remove the equivariance restriction for this fixed-length approximation problem.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck pendingOpen item page →

A two-token causal next-token mask

Example

For two scalar token states $x_{1} = 1$ and $x_{2} = 3$ , take query and key projections equal to zero, value projection equal to the identity, and the causal additive mask

M = (\begin{array}{cc} 0 & - \infty \\ 0 & 0 \end{array}) .

Row-softmax attention assigns the first query all weight to token $1$ and the second query equal weight to tokens $1$ and $2$ , so the output states are $(1, 2)$ .

Example references

Vaswani et al., §3.2.3: decoder masking of future positions

Dive into Deep Learning, §11.7.2: decoder self-attention with causal masking

Facts & Assumptions

Given: Two scalar token states, zero query and key projections, identity value projection, row softmax, and the causal mask in the Example.

[F1]

Masked attention replaces disallowed logits by $- \infty$ , requires at least one allowed key in each row, and normalizes each allowed row by softmax (Scaled dot-product attention).

[F2]

The decoder's causal mask permits key positions $j \leq i$ for query position $i$ (Positional encodings and causal masks).

Verification

1.1givenF1algebra

Both unmasked logits are zero. In the first row the mask leaves logits $(0, - \infty)$ , whose row-softmax is $(1, 0)$ ; multiplying by values $(1, 3)^{T}$ gives output $1$ .

2.1givenF1F2algebra∎

In the second row the mask leaves logits $(0, 0)$ , whose row-softmax is $(1 / 2, 1 / 2)$ ; multiplying by $(1, 3)^{T}$ gives output $2$ . Both rows have at least one allowed key, so the masked attention is defined.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck pendingjudge pass (gpt-6-luna)Open item page →

Fixed-length universality and unbounded sequence limits

Example

Assume the Axiom of Countable Choice and fix an integer maximum length $N \geq 2$ . For each individual integer length $2 \leq n \leq N$ , the fixed-length theorem concerns a compact-domain approximation problem and permits a Transformer chosen for that particular $n$ and error tolerance. The hard-attention language limit instead fixes one finite-depth model, with one set of parameter maps independent of length, and rules out exact recognition of PARITY and 2DYCK for all sufficiently long strings. For each fixed source parameter $p \in (0, 1)$ , the soft-attention parity result fixes one model satisfying the one-symbol influence hypotheses across lengths and bounds the limit inferior of its expected cross-entropy on the stated parity source from below by the sharp unigram chance entropy, attained by a constant predictor. These statements concern different quantifiers and different notions of approximation.

Example references

Yun et al., Theorems 2–3: fixed-length integrated $L_{p}$ approximation

Hahn, §5, Corollary 2: fixed-depth hard-attention language limits

The Axiom of Countable Choice ( ${A C}_{ω}$ ): the inherited premise for the local integrated-Lebesgue approximation theorem.

Facts & Assumptions

Given: Countable Choice, an integer cutoff $N \geq 2$ , the fixed-length Transformer approximation theorem, and the fixed-model hard-attention PARITY theorem.

[F1]

Under Countable Choice, at each fixed $n \geq 2$ , $d \geq 1$ , and $1 \leq p < \infty$ , continuous compactly supported permutation-equivariant maps admit integrated $L_{p}$ approximants with two heads of size one, width-four ReLU feedforward layers, and no layer normalization; trainable positions give the compact-domain non-equivariant version (Fixed-width Transformer approximation on compact domains).

[F2]

No single fixed finite-depth hard-attention model with parameters fixed independently of input length recognizes PARITY or 2DYCK on all sufficiently long strings (Fixed-depth hard attention cannot recognize PARITY or 2DYCK).

[F3]

For the stated parity next-symbol distribution with fixed source parameter $p \in (0, 1)$ , every fixed soft-attention predictor satisfying the one-symbol influence hypotheses has ${lim inf}_{n \to \infty} E CE \geq H (u)$ , where $u = (p / 2, (2 - p) / 4, (2 - p) / 4)$ in the symbol order $(e o s, 0, 1)$ . The constant predictor $u$ attains $H (u)$ at every length; convergence of the expected loss for an arbitrary fixed predictor is not asserted (Fixed soft attention has no parity advantage over the unigram predictor).

Verification

1.1givenF1construct

Under Countable Choice, apply [F1] separately for each integer $2 \leq n \leq N$ , each fixed $d \geq 1$ , each $1 \leq p < \infty$ , and each chosen positive tolerance, to a target satisfying its corresponding continuity, compactness, and symmetry hypotheses. The theorem's existential network may depend on both $n$ and the tolerance; it gives no shared parameter set or depth bound uniform in $n$ .

2.1step 1.1F2F3algebra∎

[F2] fixes one model across all lengths and asserts failure of exact recognition for sufficiently large PARITY and 2DYCK inputs. [F3] likewise fixes one soft model and gives a liminf lower bound for expected cross-entropy on a specified source. Neither statement contradicts the separate fixed-length approximation claims, whose metric is integrated $L_{p}$ error and whose parameters may vary with length.

Attention, transformer universality, and sequence limits — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

Position-free versus position-encoded token order

Example

Example references

Facts & Assumptions

Proof

A two-token causal next-token mask

Example

Example references

Facts & Assumptions

Verification

Fixed-length universality and unbounded sequence limits

Example

Example references

Facts & Assumptions

Verification

Sources