ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pending

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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

17 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yun et al., Theorems 2–3 and Appendix A (standard reference, not scraped)