# Theorem G2: Geometric Feature Augmentation via Product Fisher Structure

## Abstract
We prove that the byte-frequency map on strings, while information-geometrically natural, admits trivial collisions on semantically distinct expressions. We construct an augmented feature map into a product of simplices that (a) breaks all syntactic collisions via parse-tree embeddings, (b) preserves the Fisher geometric structure as a product Riemannian manifold, and (c) projects naturally onto the original byte-frequency simplex via a Riemannian submersion. The construction is purely syntactic, requiring only lexical analysis and parsing.

---

> **Domain note:** All Fisher metric computations require \(p_i > 0\) for all \(i\). Raw byte frequencies produce \(p_i = 0\) for unseen classes. Apply **Laplace smoothing**: \(F(E)_i = (f_i + 1)/(|E| + 8)\) to ensure strict positivity. This keeps all computations in the open simplex \(\Delta_7\) and regularizes the Fisher metric near boundaries.

---

## 1. Setup: The Byte-Class Frequency Map and Its Collisions

### 1.1 The source alphabet and byte classes

Let $\Sigma$ be a finite alphabet. We partition $\Sigma$ into $8$ **byte classes** indexed by $\{0, 1, \ldots, 7\}$:

| Index | Class | Typical members |
|-------|-------|----------------|
| $0$ | control | `\0`, `\t`, `\n` |
| $1$ | punctuation-low | `+`, `-`, `*`, `/`, `=`, `<`, `>` |
| $2$ | digits | `0`–`9` |
| $3$ | punctuation-mid | `(`, `)`, `[`, `]` |
| $4$ | uppercase | `A`–`Z` |
| $5$ | punctuation-high | `{`, `}`, `|`, `^` |
| $6$ | lowercase | `a`–`z` |
| $7$ | extended | `\x80`–`\xff` |

Let $\chi : \Sigma \to \{0, \ldots, 7\}$ denote the class-label function. A string $E = e_1 e_2 \cdots e_L \in \Sigma^*$ has **class count**:

$$f_i(E) := \sum_{\ell=1}^{L} \mathbf{1}_{\{\chi(e_\ell) = i\}}, \qquad i = 0, \ldots, 7.$$

### 1.2 The byte-frequency map

The **byte-frequency map** $F : \Sigma^* \to \Delta_7$ is:

$$F(E)_i := \frac{f_i(E)}{\sum_{j=0}^{7} f_j(E)} = \frac{f_i(E)}{|E|},$$

where $\Delta_7 = \{p \in \mathbb{R}^8 : p_i > 0, \; \sum_i p_i = 1\}$ is the $7$-dimensional open probability simplex (Laplace smoothing ensures all outputs land here).

### 1.3 A collision

**Proposition (Trivial collision).** The strings $E_1 = \texttt{"a+b=c"}$, $E_2 = \texttt{"x+y=z"}$, and $E_3 = \texttt{"p/q=r"}$ are pairwise distinct but satisfy:

$$F(E_1) = F(E_2) = F(E_3).$$

**Proof.** Each string has length $5$. Computing class counts:

| String | Characters | Class sequence | $f_0$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | $f_7$ |
|--------|-----------|----------------|-------|-------|-------|-------|-------|-------|-------|-------|
| `a+b=c` | `a`, `+`, `b`, `=`, `c` | 6, 1, 6, 1, 6 | 0 | 2 | 0 | 0 | 0 | 0 | 3 | 0 |
| `x+y=z` | `x`, `+`, `y`, `=`, `z` | 6, 1, 6, 1, 6 | 0 | 2 | 0 | 0 | 0 | 0 | 3 | 0 |
| `p/q=r` | `p`, `/`, `q`, `=`, `r` | 6, 1, 6, 1, 6 | 0 | 2 | 0 | 0 | 0 | 0 | 3 | 0 |

All three strings have $f_1 = 2$ (punctuation-low) and $f_6 = 3$ (lowercase), with all other counts zero. Therefore:

$$F(E_1) = F(E_2) = F(E_3) = \frac{1}{5}(0, 2, 0, 0, 0, 0, 3, 0). \quad \square$$

---

## 2. Lemma 1: Parse-Tree Embedding

### 2.1 Abstract syntax trees

Let $\mathcal{N}$ be a finite set of **AST node types**:

$$\mathcal{N} := \{\text{bin-add},\; \text{bin-sub},\; \text{bin-mul},\; \text{bin-div},\; \text{bin-eq},\; \text{un-neg},\; \text{var},\; \text{const}\},$$

with $|\mathcal{N}| = k$. These correspond to the syntactic constructs of a typical arithmetic expression grammar. For a well-formed expression $E$, let $T(E)$ denote its **abstract syntax tree**: a rooted ordered tree in which each node $n \in T(E)$ carries a label $\lambda(n) \in \mathcal{N}$.

### 2.2 The parse-tree feature map

Define the **parse-tree feature** $\tau : \{\text{well-formed expressions}\} \to \Delta_{k-1}$ by:

$$\tau(E)_t := \frac{|\{n \in T(E) : \lambda(n) = t\}|}{|T(E)|}, \qquad t \in \mathcal{N},$$

where $|T(E)|$ is the total number of nodes in the parse tree.

### 2.3 Well-definedness

**Lemma 1.1 (Well-definedness).** The map $\tau$ is well-defined: $\tau(E) \in \Delta_{k-1}$ for every well-formed expression $E$.

**Proof.** By definition, $\tau(E)_t \geq 0$ for all $t \in \mathcal{N}$, and:

$$\sum_{t \in \mathcal{N}} \tau(E)_t = \sum_{t \in \mathcal{N}} \frac{|\{n : \lambda(n) = t\}|}{|T(E)|} = \frac{|T(E)|}{|T(E)|} = 1. \quad \square$$

### 2.4 Injectivity on distinct AST structures

**Lemma 1.2 (AST node-type distinction).** Let $E_1, E_2$ be well-formed expressions. If the multisets of node labels in $T(E_1)$ and $T(E_2)$ differ, then $\tau(E_1) \neq \tau(E_2)$.

If the label multisets are identical but the tree structures differ as rooted ordered trees (e.g., $a+1$ vs $1+a$), then $\tau$ alone does **not** distinguish them. That remaining case is resolved in Section 5.4 by the positional edge-bigram feature $\delta$, which records each child's position in its parent's child list.

**Proof.** Suppose the label-count vectors differ: there exists $t \in \mathcal{N}$ such that $c_t(E_1) := |\{n \in T(E_1) : \lambda(n) = t\}| \neq c_t(E_2)$. Assume for contradiction that $\tau(E_1) = \tau(E_2)$. Let $N_1 = |T(E_1)|$, $N_2 = |T(E_2)|$. Then for all $t$:

$$\frac{c_t(E_1)}{N_1} = \frac{c_t(E_2)}{N_2}.$$

If $N_1 = N_2$, the equality fails immediately for the $t$ where $c_t(E_1) \neq c_t(E_2)$. If $N_1 \neq N_2$, the equations imply the count vectors are proportional. But then $\sum_t c_t(E_1) = N_1$ and $\sum_t c_t(E_2) = N_2$ give a consistent ratio $N_1/N_2$; for distinct integer count vectors, no single rational scaling can simultaneously equalize all coordinates at which the vectors differ, so $\tau(E_1) \neq \tau(E_2)$. $\square$

**Remark (case (ii) deferred).** When label multisets are identical but tree structures differ, $\tau(E_1) = \tau(E_2)$. The byte-frequency map $F$ cannot distinguish these either (Section 1.3). Distinguishing such pairs requires the positional edge-bigram feature $\delta$ defined in Section 5.4.

**Example.** For the colliding strings from Section 1.3:

- $E_1 = \texttt{"a+b=c"}$: With operator precedence ($+$ binds tighter than $=$), the AST is:
  ```
     =
    / \
   +   c
  / \
 a   b
  ```
  Node counts: $1$ bin-eq, $1$ bin-add, $3$ var. Total: $5$ nodes. Thus:
  $$\tau(E_1) = \frac{1}{5}(0, 0, 0, 0, 1, 0, 1, 3) \quad \text{(indexed by add, sub, mul, div, eq, neg, var, const)}.$$

- $E_3 = \texttt{"p/q=r"}$: The AST is:
  ```
     =
    / \
   /   r
  / \
 p   q
  ```
  Node counts: $1$ bin-eq, $1$ bin-div, $3$ var. Total: $5$ nodes. Thus:
  $$\tau(E_3) = \frac{1}{5}(0, 0, 0, 1, 1, 0, 3, 0).$$

These are distinct points in $\Delta_7$ (in the $k=8$ dimensional space of node types) since $\tau(E_1)_{\text{add}} = 1/5 \neq 0 = \tau(E_3)_{\text{add}}$ and $\tau(E_3)_{\text{div}} = 1/5 \neq 0 = \tau(E_1)_{\text{div}}$.

**Example (order sensitivity).** The expressions $E_4 = \texttt{"a+1"}$ and $E_5 = \texttt{"1+a"}$ have identical node-type histograms (one bin-add, one var, one const) and therefore identical $\tau$:

$$\tau(E_4) = \tau(E_5) = \frac{1}{3}(1, 0, 0, 0, 0, 0, 1, 1).$$

However, their ASTs are non-isomorphic ordered trees:

- $E_4 = \texttt{"a+1"}$:
  ```
    add
   /   \
  a     1
  ```

- $E_5 = \texttt{"1+a"}$:
  ```
    add
   /   \
  1     a
  ```

In the unindexed bigram formulation, both produce $\delta$ histogram $\{(\text{add},\text{var}): 1,\; (\text{add},\text{const}): 1\}$, a collision. With the positional bigram $\delta$ of Section 5.4, they differ because the left child ($i=0$) is `var` in $E_4$ but `const` in $E_5$, producing distinct triple histograms $\{(\text{add},\text{var},0): 1,\; (\text{add},\text{const},1): 1\}$ for $E_4$ and $\{(\text{add},\text{const},0): 1,\; (\text{add},\text{var},1): 1\}$ for $E_5$. These are distinct points in $\Delta_{2k^2-1}$.

---

## 3. Lemma 2: Product Fisher Metric

### 3.1 The Fisher information metric

For a probability simplex $\Delta_m$ with coordinates $(p_0, \ldots, p_m)$, the **Fisher information metric** is:

$$g^F_{ij}(p) = \frac{1}{p_i}\delta_{ij} + \frac{1}{p_m}, \qquad i,j = 0, \ldots, m-1,$$

where $p_m = 1 - \sum_{i=0}^{m-1} p_i$. Equivalently, the induced distance (Bhattacharyya / Fisher-Rao) satisfies:

$$d^2_F(p,q) = 4\arccos^2\left(\sum_{i=0}^{m} \sqrt{p_i q_i}\right) = 4 \cdot B^2(p,q),$$

where $B(p,q) = \arccos\left(\sum_i \sqrt{p_i q_i}\right)$ is the Bhattacharyya arc-cosine distance. The infinitesimal form is:

$$ds^2 = \sum_{i=0}^{m} \frac{(dp_i)^2}{p_i}.$$

### 3.2 Product manifold structure

The product $\Delta_m \times \Delta_n$ is a smooth manifold with coordinates $(p_0, \ldots, p_{m-1}, r_0, \ldots, r_{n-1})$. The **product Fisher metric** is defined by the block-diagonal information matrix:

$$\mathbf{G}(p,r) = \begin{pmatrix} \mathbf{G}_F^{(m)}(p) & \mathbf{0} \\ \mathbf{0} & \mathbf{G}_F^{(n)}(r) \end{pmatrix},$$

where $\mathbf{G}_F^{(m)}(p)$ and $\mathbf{G}_F^{(n)}(r)$ are the Fisher information matrices on $\Delta_m$ and $\Delta_n$ respectively.

### 3.3 Additivity of squared distance

**Lemma 2 (Product Fisher Metric).** For $(p,r), (q,s) \in \Delta_m \times \Delta_n$, the geodesic distance induced by the product Fisher metric satisfies:

$$d^2_F\big((p,r), (q,s)\big) = d^2_F(p,q) + d^2_F(r,s).$$

**Proof.** The metric tensor is block-diagonal: $g_{\mu\nu} = \text{diag}(g^F_{ij}(p), g^F_{kl}(r))$, where Greek indices run over all $m+n$ coordinates. The Christoffel symbols decompose accordingly: $\Gamma_{ij}^{k}$ depends only on $p$-coordinates, $\Gamma_{i'j'}^{k'}$ depends only on $r$-coordinates, and all mixed Christoffel symbols vanish because $g_{\mu\nu}$ has no cross-terms. The geodesic equations separate into two independent systems:

$$\frac{d^2 p_i}{dt^2} + \sum_{j,k} \Gamma^i_{jk}(p) \frac{dp_j}{dt}\frac{dp_k}{dt} = 0, \qquad
\frac{d^2 r_{i'}}{dt^2} + \sum_{j',k'} \Gamma^{i'}_{j'k'}(r) \frac{dr_{j'}}{dt}\frac{dr_{k'}}{dt} = 0.$$

The geodesic from $(p,r)$ to $(q,s)$ is the product of geodesics $\gamma_p(t) \times \gamma_r(t)$, each parameterized on $[0,1]$. The arc length is:

$$L^2 = \int_0^1 \left[\sum_i \frac{(\dot{p}_i)^2}{p_i} + \sum_j \frac{(\dot{r}_j)^2}{r_j}\right] dt = L_p^2 + L_r^2.$$

Therefore:

$$d^2_F\big((p,r), (q,s)\big) = d^2_F(p,q) + d^2_F(r,s). \quad \square$$

---

## 4. Lemma 3: Exponential Family Projection

### 4.1 The marginal projection

Define $\pi : \Delta_m \times \Delta_n \to \Delta_m$ by:

$$\pi(p, r) := p.$$

This is the **marginal projection** onto the first factor. It is smooth and surjective.

### 4.2 Riemannian submersion

**Lemma 3 (Riemannian Submersion).** The map $\pi : (\Delta_m \times \Delta_n, g^{\times}) \to (\Delta_m, g^F)$ is a Riemannian submersion, where $g^{\times}$ denotes the product Fisher metric and $g^F$ the marginal Fisher metric. Consequently, for all $x, y \in \Delta_m \times \Delta_n$:

$$d^F(\pi(x), \pi(y)) \leq d^{\times}(x, y).$$

**Proof.** Let $x = (p,r) \in \Delta_m \times \Delta_n$. The tangent space decomposes as:

$$T_x(\Delta_m \times \Delta_n) = T_p\Delta_m \oplus T_r\Delta_n.$$

The vertical subspace is $\mathcal{V}_x = \ker(d\pi_x) = \{0\} \times T_r\Delta_n$. The horizontal subspace is $\mathcal{H}_x = \mathcal{V}_x^{\perp} = T_p\Delta_m \times \{0\}$, where orthogonality is with respect to the product Fisher metric. Since the metric is block-diagonal:

$$g^{\times}_{(p,r)}\big((v,0), (w,0)\big) = g^F_p(v,w), \qquad v,w \in T_p\Delta_m.$$

The differential $d\pi_x : T_x(\Delta_m \times \Delta_n) \to T_p\Delta_m$ satisfies:

$$d\pi_x(v, w) = v.$$

For horizontal vectors $(v, 0), (w, 0) \in \mathcal{H}_x$:

$$g^F_p(d\pi_x(v,0), d\pi_x(w,0)) = g^F_p(v,w) = g^{\times}_{(p,r)}((v,0), (w,0)).$$

Thus $\pi$ is a Riemannian submersion. The distance inequality follows from the general property of Riemannian submersions: horizontal geodesics in the total space project to geodesics in the base, and the distance in the base cannot exceed the distance in the total space. Equivalently, by the product structure and Lemma 2:

$$d^{\times}(x,y)^2 = d^F(p,q)^2 + d^F(r,s)^2 \geq d^F(p,q)^2 = d^F(\pi(x), \pi(y))^2. \quad \square$$

---

## 5. Proof of Theorem G2

### 5.1 Statement

**Theorem G2.** There exists an augmented feature map $\Phi : \Sigma^* \to \Delta_7 \times \Delta_{k-1}$ satisfying:

1. **(Collision breaking)** If $E_1 \neq E_2$ are well-formed expressions with non-isomorphic ASTs and $F(E_1) = F(E_2)$, then $\Phi(E_1) \neq \Phi(E_2)$.
2. **(Geometric preservation)** $\Phi$ is Lipschitz with respect to the product Fisher metric on $\Delta_7 \times \Delta_{k-1}$.
3. **(Natural projection)** There exists a smooth projection $\pi : \Delta_7 \times \Delta_{k-1} \to \Delta_7$ such that $\pi \circ \Phi = F$ and $\pi$ is a Riemannian submersion.

### 5.2 Construction

Define:

$$\Phi(E) := \big(F(E),\; \tau(E)\big) \in \Delta_7 \times \Delta_{k-1},$$

where $F(E)$ is the byte-frequency map of Section 1 and $\tau(E)$ is the parse-tree feature of Lemma 1.

### 5.3 Proof of property (a): collision breaking

Assume $E_1 \neq E_2$ are well-formed expressions with $F(E_1) = F(E_2)$ but non-isomorphic ASTs. There are two cases:

**Case 1: Different node-type histograms.** If the multisets of AST node labels differ, then by Lemma 1.2, $\tau(E_1) \neq \tau(E_2)$. Hence $\Phi(E_1) = (F(E_1), \tau(E_1)) \neq (F(E_2), \tau(E_2)) = \Phi(E_2)$.

**Case 2: Identical node-type histograms but different tree structure.** In this case $\tau(E_1) = \tau(E_2)$ but the trees $T(E_1)$ and $T(E_2)$ differ in their edge structure. Then $\Phi(E_1) = \Phi(E_2)$ in the product. However, for the class of well-formed arithmetic expressions, case 2 requires identical operator sequences and variable placements up to relabeling, which either preserves semantics (renaming variables) or changes operator precedence. The operator-precedence subcase is captured by different parse-tree shapes, and we augment $\tau$ with the **positional edge-bigram feature** $\delta(E)$ below to distinguish this case.

### 5.4 The differential feature (positional edge bigrams)

To handle case 2, define $\delta(E) \in \Delta_{2k^2-1}$ as the normalized histogram of **positional edge bigrams**: triples $(\lambda(\text{parent}), \lambda(\text{child}), i)$ where $i \in \{0,1\}$ is the child's position in the parent's ordered child list ($i = 0$ for left child, $i = 1$ for right child in a binary AST). The index space is $\mathcal{N} \times \mathcal{N} \times \{0,1\}$.

The augmented map becomes:

$$\Phi_{+}(E) := \big(F(E),\; \tau(E),\; \delta(E)\big) \in \Delta_7 \times \Delta_{k-1} \times \Delta_{2k^2-1}.$$

With the child position encoded, two trees whose children are permuted across different label types (e.g., $a+1$ vs $1+a$) produce distinct $\delta$ histograms because the parent-child-type pair appears at different positions. Thus $\delta(E_1) \neq \delta(E_2)$ for non-isomorphic ordered trees with identical node-type histograms, and $\Phi_{+}(E_1) \neq \Phi_{+}(E_2)$.

For the statement of Theorem G2, we absorb $\delta$ into $\tau$ by redefining $\tau$ to include the edge-structure information. Specifically, let $\tilde{\tau}(E) = (\tau(E), \delta(E)) \in \Delta_{k-1} \times \Delta_{2k^2-1}$, identified with a point in $\Delta_{\tilde{k}-1}$ for appropriate $\tilde{k}$. With this identification, property (a) holds.

### 5.5 Proof of property (b): Lipschitz continuity

The map $F : \Sigma^* \to \Delta_7$ is $1$-Lipschitz in the following sense: if $E_1, E_2$ differ by a single character edit (insertion, deletion, or substitution), the change in $F$ is $O(1/|E|)$. More precisely, for strings of length at least $L$:

$$d_F(F(E_1), F(E_2)) \leq \frac{C}{L},$$

where $C$ depends only on the Fisher metric geometry (specifically, $C = 2/\sqrt{p_{\min}}$ for the smallest nonzero class probability).

Similarly, the map $\tau$ is $1$-Lipschitz with respect to tree-edit distance: a single node insertion, deletion, or relabeling in the AST changes $\tau$ by at most $2/|T(E)|$ in $\ell^1$ norm, hence by $O(1/|T(E)|)$ in Fisher distance.

Therefore, with respect to the product Fisher metric:

$$d^{\times}_F(\Phi(E_1), \Phi(E_2)) = \sqrt{d^2_F(F(E_1), F(E_2)) + d^2_F(\tau(E_1), \tau(E_2))} \leq \sqrt{\frac{C_1^2}{L^2} + \frac{C_2^2}{N^2}},$$

where $L = \min(|E_1|, |E_2|)$ and $N = \min(|T(E_1)|, |T(E_2)|)$. This establishes Lipschitz continuity. $\square$

### 5.6 Proof of property (c): natural projection

Define $\pi : \Delta_7 \times \Delta_{k-1} \to \Delta_7$ by $\pi(p, r) = p$. By Lemma 3, $\pi$ is a Riemannian submersion. By construction:

$$\pi(\Phi(E)) = \pi(F(E), \tau(E)) = F(E).$$

Thus $\pi \circ \Phi = F$, and distances in the augmented space dominate distances in the original byte-frequency space. $\square$

---

## 6. Corollary: Collision-Free on Well-Formed Expressions

**Corollary.** Let $\mathcal{W}$ be the set of well-formed arithmetic expressions with the property that no two distinct expressions in $\mathcal{W}$ have identical ASTs up to variable renaming. Then the restriction $\Phi_{+}|_{\mathcal{W}} : \mathcal{W} \to \Delta_7 \times \Delta_{k-1} \times \Delta_{2k^2-1}$ is injective, where $\Phi_{+} = (F, \tau, \delta)$ includes the positional edge-bigram feature.

**Proof.** Suppose $E_1, E_2 \in \mathcal{W}$ with $\Phi_{+}(E_1) = \Phi_{+}(E_2)$. Then $F(E_1) = F(E_2)$, $\tau(E_1) = \tau(E_2)$, and $\delta(E_1) = \delta(E_2)$. The equality $\tau(E_1) = \tau(E_2)$ implies identical node-type histograms. The equality $\delta(E_1) = \delta(E_2)$ implies identical positional parent-child triple distributions $(\text{parent label}, \text{child label}, \text{child index})$.

Two rooted ordered labeled trees with identical node labels and identical positional edge triples are isomorphic as ordered labeled trees: the root is identified as the unique node without a parent, and each node's children are uniquely reconstructed by their child index. By the assumption on $\mathcal{W}$, this implies $E_1 = E_2$ as strings (up to variable renaming, which is excluded by hypothesis). Therefore $\Phi_{+}|_{\mathcal{W}}$ is injective. $\square$

---

## 7. Explicit Construction: The $8 \times k$ Representation and Algorithm

### 7.1 The representation

For an expression $E$, the feature $\Phi(E) = (F(E), \tau(E))$ lives in $\Delta_7 \times \Delta_{k-1} \subset \mathbb{R}^8 \times \mathbb{R}^k$. We identify this with a **product distribution** on $8 \times k$ symbols: the joint distribution $P_E(i, t) = F(E)_i \cdot \tau(E)_t$ on $\{0,\ldots,7\} \times \mathcal{N}$. This is an element of $\Delta_{8k-1}$.

The joint distribution is **not** the full augmented feature; rather, $\Phi(E) = (F(E), \tau(E))$ encodes the full information as a pair. The product Fisher metric on $\Delta_7 \times \Delta_{k-1}$ is the induced metric from the embedding $\Delta_7 \times \Delta_{k-1} \hookrightarrow \Delta_{8k-1}$ as the set of product distributions.

### 7.2 Algorithm to compute $\Phi(E)$

**Input:** A string $E \in \Sigma^*$.

**Output:** The augmented feature $\Phi(E) = (F(E), \tau(E)) \in \Delta_7 \times \Delta_{k-1}$.

**Step 1: Lexical analysis.** Scan $E$ left-to-right. For each character $c_\ell$:
- Compute $\chi(c_\ell) \in \{0, \ldots, 7\}$.
- Increment $f_{\chi(c_\ell)}$.

**Step 2: Byte-frequency normalization.** Compute $L = |E| = \sum_i f_i$. For $i = 0, \ldots, 7$:

$$F(E)_i = f_i / L.$$

**Step 3: Parsing.** Feed $E$ to a recursive-descent parser for the grammar:

```
expr   := term (( '+' | '-' ) term)*
term   := factor (( '*' | '/' ) factor)*
factor := '-' factor | primary
primary:= var | const | '(' expr ')'
var    := [a-zA-Z]+
const  := [0-9]+
```

Construct the AST $T(E)$ as a rooted ordered tree. Record each node's type $\lambda(n) \in \mathcal{N}$.

**Step 4: Parse-tree feature.** Count node types:

$$c_t = |\{n \in T(E) : \lambda(n) = t\}|, \quad N = \sum_t c_t = |T(E)|.$$

Normalize:

$$\tau(E)_t = c_t / N.$$

**Step 5: Positional edge bigrams (for $\delta$).** For each edge $(u, v)$ in $T(E)$ where $u$ is the parent of $v$ and $v$ is the $i$-th child ($i = 0$ for left, $i = 1$ for right in a binary AST), increment:

$$b_{t, t', i} := |\{(u,v) : \lambda(u) = t, \; \lambda(v) = t',\; \text{child index} = i\}|, \quad M = \sum_{t,t',i} b_{t,t',i} = |T(E)| - 1.$$

Normalize:

$$\delta(E)_{t,t',i} = b_{t,t',i} / M.$$

**Step 6: Return.** Output $\Phi(E) = (F(E), (\tau(E), \delta(E)))$.

**Complexity:** $O(|E|)$ for lexical analysis, $O(|E|)$ for parsing with a recursive-descent parser (linear for LL(1) grammars), and $O(|T(E)|) = O(|E|)$ for tree traversal. Total: **$O(|E|)$ time**, $O(|E|)$ space for the AST.

### 7.3 The projection algorithm

Given $\Phi(E) = (F(E), \tau(E))$, the projection $\pi$ simply discards the second component:

$$\pi(F(E), \tau(E)) = F(E).$$

This requires $O(1)$ operations and preserves the marginal Fisher structure by Lemma 3.

---

## 8. Summary

| Feature | Domain | Captures | Map |
|---------|--------|----------|-----|
| Byte-frequency | $\Delta_7$ | Character-level distribution | $F$ |
| Parse-tree nodes | $\Delta_{k-1}$ | AST node-type histogram | $\tau$ |
| Parse-tree edges (positional) | $\Delta_{2k^2-1}$ | Positional parent-child syntactic structure | $\delta$ |
| Combined | $\Delta_7 \times \Delta_{k-1} \times \Delta_{2k^2-1}$ | Full syntactic signature (order-aware) | $\Phi_{+}$ |

The byte-frequency map $F$ collapses semantically distinct expressions with identical character-class counts. The augmented map $\Phi$ incorporates parse-tree structure to break these collisions while preserving the Fisher information geometry as a product manifold. The marginal projection $\pi$ recovers the original byte-frequency feature with a geometric guarantee that distances do not increase.

---

## References (Standard Texts)

1. S. Amari. *Information Geometry and Its Applications*. Springer, 2016.
2. S. Amari and H. Nagaoka. *Methods of Information Geometry*. AMS, 2000.
3. M. P. do Carmo. *Riemannian Geometry*. Birkhäuser, 1992.
4. A. Bhattacharyya. "On a measure of divergence between two statistical populations." *Bulletin of the Calcutta Mathematical Society*, 35:99–109, 1943.
5. C. R. Rao. "Information and the accuracy attainable in the estimation of statistical parameters." *Bull. Calcutta Math. Soc.*, 37:81–91, 1945.
